randombit/botan | Build 17301257033 | source/src/lib/math/bigint/divide.cpp | Coveralls

21

void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {

297,259✔

22

   q.cond_flip_sign(x.sign() != y.sign());

297,259✔

24

   if(x.is_negative() && r.is_nonzero()) {

298,478✔

25

      q -= 1;

1,215✔

26

      r = y.abs() - r;

1,215✔

28

297,259✔

30

inline bool division_check_vartime(word q, word y2, word y1, word x3, word x2, word x1) {

4,520,062✔

36

   word y3 = 0;

4,520,062✔

37

   y1 = word_madd2(q, y1, &y3);

4,520,062✔

38

   y2 = word_madd2(q, y2, &y3);

4,520,062✔

40

   if(x3 != y3) {

4,520,062✔

41

      return (y3 > x3);

1,566,544✔

43

   if(x2 != y2) {

2,953,518✔

44

      return (y2 > x2);

2,833,177✔

46

   return (y1 > x1);

120,341✔

51

void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {

6,652✔

52

   if(y.is_zero()) {

11,284✔

56

   const size_t x_words = x.sig_words();

6,652✔

57

   const size_t y_words = y.sig_words();

6,652✔

59

   const size_t x_bits = x.bits();

6,652✔

61

   BigInt q = BigInt::with_capacity(x_words);

6,652✔

62

   BigInt r = BigInt::with_capacity(y_words);

6,652✔

63

   BigInt t = BigInt::with_capacity(y_words);  // a temporary

6,652✔

65

   for(size_t i = 0; i != x_bits; ++i) {

6,078,068✔

66

      const size_t b = x_bits - 1 - i;

6,071,416✔

67

      const bool x_b = x.get_bit(b);

6,071,416✔

69

      r <<= 1;

6,071,416✔

70

      r.conditionally_set_bit(0, x_b);

6,071,416✔

72

      const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;

6,071,416✔

74

      q.conditionally_set_bit(b, r_gte_y);

6,071,416✔

75

      r.ct_cond_swap(r_gte_y, t);

6,071,416✔

78

   sign_fixup(x, y, q, r);

6,652✔

79

   r_out = r;

6,652✔

80

   q_out = q;

6,652✔

81

6,652✔

83

BigInt ct_divide_pow2k(size_t k, const BigInt& y) {

111,905✔

84

   BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");

112,283✔

85

   BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");

111,905✔

86

   BOTAN_ARG_CHECK(k > 1, "Invalid k");

111,905✔

88

   const size_t x_bits = k + 1;

111,905✔

89

   const size_t y_bits = y.bits();

111,905✔

91

   if(x_bits < y_bits) {

111,905✔

92

      return BigInt::zero();

248✔

95

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

111,657✔

96

   const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;

111,657✔

97

   const size_t y_words = y.sig_words();

111,657✔

99

   BigInt q = BigInt::with_capacity(x_words);

111,657✔

100

   BigInt r = BigInt::with_capacity(y_words + 1);

111,657✔

101

   BigInt t = BigInt::with_capacity(y_words + 1);  // a temporary

111,657✔

103

   r.set_bit(y_bits - 1);

111,657✔

104

   for(size_t i = y_bits - 1; i != x_bits; ++i) {

30,662,785✔

105

      const size_t b = x_bits - 1 - i;

30,551,128✔

107

      if(i >= y_bits) {

30,551,128✔

108

         bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);

30,439,471✔

111

      const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;

30,551,128✔

113

      q.conditionally_set_bit(b, r_gte_y);

30,551,128✔

115

      bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);

30,551,128✔

120

   return q;

111,657✔

121

111,657✔

123

void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {

12,476✔

124

   if(y == 0) {

12,476✔

128

   const size_t x_words = x.sig_words();

12,476✔

129

   const size_t x_bits = x.bits();

12,476✔

131

   BigInt q = BigInt::with_capacity(x_words);

12,476✔

134

   for(size_t i = 0; i != x_bits; ++i) {

6,571,502✔

135

      const size_t b = x_bits - 1 - i;

6,559,026✔

136

      const bool x_b = x.get_bit(b);

6,559,026✔

138

      const auto r_carry = CT::Mask<word>::expand_top_bit(r);

6,559,026✔

140

      r <<= 1;

6,559,026✔

141

      r += static_cast<word>(x_b);

6,559,026✔

143

      const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;

6,559,026✔

144

      q.conditionally_set_bit(b, r_gte_y.as_bool());

6,559,026✔

145

      r = r_gte_y.select(r - y, r);

6,559,026✔

148

   if(x.is_negative()) {

12,476✔

149

      q.flip_sign();

23✔

150

      if(r != 0) {

23✔

151

         --q;

19✔

152

         r = y - r;

19✔

156

   r_out = r;

12,476✔

157

   q_out = q;

12,476✔

158

12,476✔

160

BigInt ct_divide_word(const BigInt& x, word y) {

4,340✔

161

   BigInt q;

4,340✔

162

   word r = 0;

4,340✔

163

   ct_divide_word(x, y, q, r);

4,340✔

164

   BOTAN_UNUSED(r);

4,340✔

165

   return q;

4,340✔

168

word ct_mod_word(const BigInt& x, word y) {

4,340✔

169

   BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");

4,340✔

170

   BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");

4,340✔

172

   const size_t x_bits = x.bits();

4,340✔

174

   word r = 0;

4,340✔

176

   for(size_t i = 0; i != x_bits; ++i) {

3,028,635✔

177

      const size_t b = x_bits - 1 - i;

3,024,295✔

178

      const bool x_b = x.get_bit(b);

3,024,295✔

180

      const auto r_carry = CT::Mask<word>::expand_top_bit(r);

3,024,295✔

182

      r <<= 1;

3,024,295✔

183

      r += static_cast<word>(x_b);

3,024,295✔

185

      const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;

3,024,295✔

186

      r = r_gte_y.select(r - y, r);

3,024,295✔

189

   return r;

4,340✔

192

BigInt ct_modulo(const BigInt& x, const BigInt& y) {

3,585✔

193

   if(y.is_negative() || y.is_zero()) {

7,170✔

197

   const size_t y_words = y.sig_words();

3,585✔

199

   const size_t x_bits = x.bits();

3,585✔

201

   BigInt r = BigInt::with_capacity(y_words);

3,585✔

202

   BigInt t = BigInt::with_capacity(y_words);

3,585✔

204

   for(size_t i = 0; i != x_bits; ++i) {

5,383,476✔

205

      const size_t b = x_bits - 1 - i;

5,379,891✔

206

      const bool x_b = x.get_bit(b);

5,379,891✔

208

      r <<= 1;

5,379,891✔

209

      r.conditionally_set_bit(0, x_b);

5,379,891✔

211

      const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;

5,379,891✔

213

      r.ct_cond_swap(r_gte_y, t);

5,379,891✔

216

   if(x.is_negative()) {

3,585✔

217

      if(r.is_nonzero()) {

94✔

218

         r = y - r;

45✔

222

   return r;

3,585✔

223

3,585✔

225

BigInt vartime_divide_pow2k(size_t k, const BigInt& y_arg) {

153,139✔

226

   constexpr size_t WB = WordInfo<word>::bits;

153,139✔

228

   BOTAN_ARG_CHECK(!y_arg.is_zero(), "Cannot divide by zero");

153,139✔

229

   BOTAN_ARG_CHECK(!y_arg.is_negative(), "Negative divisor not supported");

153,139✔

230

   BOTAN_ARG_CHECK(k > 1, "Invalid k");

153,139✔

232

   BigInt y = y_arg;

153,139✔

234

   const size_t y_words = y.sig_words();

153,139✔

236

   BOTAN_ASSERT_NOMSG(y_words > 0);

153,139✔

239

   const size_t shifts = y.top_bits_free();

153,139✔

241

   if(shifts > 0) {

153,139✔

242

      y <<= shifts;

131,825✔

245

   BigInt r;

153,139✔

246

   r.set_bit(k + shifts);  // (2^k) << shifts

153,139✔

249

   const size_t t = y_words - 1;

153,139✔

250

   const size_t n = std::max(y_words, r.sig_words()) - 1;

306,278✔

252

   BOTAN_ASSERT_NOMSG(n >= t);

153,139✔

254

   BigInt q = BigInt::zero();

153,139✔

255

   q.grow_to(n - t + 1);

153,139✔

257

   word* q_words = q.mutable_data();

153,139✔

259

   BigInt shifted_y = y << (WB * (n - t));

153,139✔

262

   secure_vector<word> ws;

153,139✔

263

   q_words[n - t] = r.reduce_below(shifted_y, ws);

153,139✔

265

   const word y_t0 = y.word_at(t);

153,139✔

266

   const word y_t1 = y.word_at(t - 1);

153,139✔

267

   BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);

153,139✔

269

   divide_precomp div_y_t0(y_t0);

153,139✔

271

   for(size_t i = n; i != t; --i) {

1,339,443✔

272

      const word x_i0 = r.word_at(i);

1,186,304✔

273

      const word x_i1 = r.word_at(i - 1);

1,186,304✔

274

      const word x_i2 = r.word_at(i - 2);

1,186,304✔

276

      word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);

2,372,366✔

279

      for(size_t j = 0; j != 2; ++j) {

1,476,638✔

280

         if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {

2,934,584✔

281

            BOTAN_ASSERT_NOMSG(qit > 0);

290,334✔

282

            qit--;

290,334✔

288

      shifted_y >>= WB;

1,186,304✔

299

      if(qit != 0) {

1,186,304✔

300

         if(qit == 1) {

1,077,516✔

301

            r -= shifted_y;

21,847✔

303

            r -= qit * shifted_y;

1,055,669✔

306

         if(r.is_negative()) {

1,077,516✔

307

            BOTAN_ASSERT_NOMSG(qit > 0);

2,407✔

308

            qit--;

2,407✔

309

            r += shifted_y;

2,407✔

310

            BOTAN_ASSERT_NOMSG(r.is_positive());

2,407✔

314

      q_words[i - t - 1] = qit;

1,186,304✔

317

   return q;

306,278✔

318

153,139✔

325

void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {

290,607✔

326

   constexpr size_t WB = WordInfo<word>::bits;

290,607✔

328

   if(y_arg.is_zero()) {

290,685✔

332

   const size_t y_words = y_arg.sig_words();

290,607✔

334

   BOTAN_ASSERT_NOMSG(y_words > 0);

290,607✔

336

   BigInt y = y_arg;

290,607✔

338

   BigInt r = x;

290,607✔

339

   BigInt q = BigInt::zero();

290,607✔

340

   secure_vector<word> ws;

290,607✔

342

   r.set_sign(BigInt::Positive);

290,607✔

343

   y.set_sign(BigInt::Positive);

290,607✔

346

   const size_t shifts = y.top_bits_free();

290,607✔

348

   if(shifts > 0) {

290,607✔

349

      y <<= shifts;

277,999✔

350

      r <<= shifts;

277,999✔

354

   const size_t t = y_words - 1;

290,607✔

355

   const size_t n = std::max(y_words, r.sig_words()) - 1;  // r may have changed size however

569,724✔

357

   BOTAN_ASSERT_NOMSG(n >= t);

290,607✔

359

   q.grow_to(n - t + 1);

290,607✔

361

   word* q_words = q.mutable_data();

290,607✔

363

   BigInt shifted_y = y << (WB * (n - t));

290,607✔

366

   q_words[n - t] = r.reduce_below(shifted_y, ws);

290,607✔

368

   const word y_t0 = y.word_at(t);

290,607✔

369

   const word y_t1 = y.word_at(t - 1);

290,607✔

370

   BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);

290,607✔

372

   divide_precomp div_y_t0(y_t0);

290,607✔

374

   for(size_t i = n; i != t; --i) {

2,829,939✔

375

      const word x_i0 = r.word_at(i);

2,539,332✔

376

      const word x_i1 = r.word_at(i - 1);

2,539,332✔

377

      const word x_i2 = r.word_at(i - 2);

2,539,332✔

379

      word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);

5,078,498✔

382

      for(size_t j = 0; j != 2; ++j) {

3,062,785✔

383

         if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {

6,105,540✔

384

            BOTAN_ASSERT_NOMSG(qit > 0);

523,453✔

385

            qit--;

523,453✔

391

      shifted_y >>= WB;

2,539,332✔

394

      if(qit != 0) {

2,539,332✔

395

         r -= qit * shifted_y;

2,538,761✔

396

         if(r.is_negative()) {

2,538,761✔

397

            BOTAN_ASSERT_NOMSG(qit > 0);

531✔

398

            qit--;

531✔

399

            r += shifted_y;

531✔

400

            BOTAN_ASSERT_NOMSG(r.is_positive());

531✔

404

      q_words[i - t - 1] = qit;

2,539,332✔

407

   if(shifts > 0) {

290,607✔

408

      r >>= shifts;

277,999✔

411

   sign_fixup(x, y_arg, q, r);

290,607✔

413

   r_out = r;

290,607✔

414

   q_out = q;

290,607✔

415

581,214✔

randombit / botan / 17301257033

Source File
Press 'n' to go to next uncovered line, 'b' for previous

1	/*
2	* Division Algorithms
3	* (C) 1999-2007,2012,2018,2021 Jack Lloyd
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*/
7
8	#include <botan/internal/divide.h>
9
10	#include <botan/internal/bit_ops.h>
11	#include <botan/internal/ct_utils.h>
12	#include <botan/internal/mp_core.h>
13
14	namespace Botan {
15
16	namespace {
17
18	/*
19	* Handle signed operands, if necessary
20	*/
21	void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {	297,259✔
22	q.cond_flip_sign(x.sign() != y.sign());	297,259✔
23
24	if(x.is_negative() && r.is_nonzero()) {	298,478✔
25	q -= 1;	1,215✔
26	r = y.abs() - r;	1,215✔
27	}
28	}	297,259✔
29
30	inline bool division_check_vartime(word q, word y2, word y1, word x3, word x2, word x1) {	4,520,062✔
31	/*
32	Compute (y3,y2,y1) = (y2,y1) * q
33	and return true if (y3,y2,y1) > (x3,x2,x1)
34	*/
35
36	word y3 = 0;	4,520,062✔
37	y1 = word_madd2(q, y1, &y3);	4,520,062✔
38	y2 = word_madd2(q, y2, &y3);	4,520,062✔
39
40	if(x3 != y3) {	4,520,062✔
41	return (y3 > x3);	1,566,544✔
42	}
43	if(x2 != y2) {	2,953,518✔
44	return (y2 > x2);	2,833,177✔
45	}
46	return (y1 > x1);	120,341✔
47	}
48
49	} // namespace
50
51	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	6,652✔
52	if(y.is_zero()) {	11,284✔
53	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
54	}
55
56	const size_t x_words = x.sig_words();	6,652✔
57	const size_t y_words = y.sig_words();	6,652✔
58
59	const size_t x_bits = x.bits();	6,652✔
60
61	BigInt q = BigInt::with_capacity(x_words);	6,652✔
62	BigInt r = BigInt::with_capacity(y_words);	6,652✔
63	BigInt t = BigInt::with_capacity(y_words); // a temporary	6,652✔
64
65	for(size_t i = 0; i != x_bits; ++i) {	6,078,068✔
66	const size_t b = x_bits - 1 - i;	6,071,416✔
67	const bool x_b = x.get_bit(b);	6,071,416✔
68
69	r <<= 1;	6,071,416✔
70	r.conditionally_set_bit(0, x_b);	6,071,416✔
71
72	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	6,071,416✔
73
74	q.conditionally_set_bit(b, r_gte_y);	6,071,416✔
75	r.ct_cond_swap(r_gte_y, t);	6,071,416✔
76	}
77
78	sign_fixup(x, y, q, r);	6,652✔
79	r_out = r;	6,652✔
80	q_out = q;	6,652✔
81	}	6,652✔
82
83	BigInt ct_divide_pow2k(size_t k, const BigInt& y) {	111,905✔
84	BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");	112,283✔
85	BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");	111,905✔
86	BOTAN_ARG_CHECK(k > 1, "Invalid k");	111,905✔
87
88	const size_t x_bits = k + 1;	111,905✔
89	const size_t y_bits = y.bits();	111,905✔
90
91	if(x_bits < y_bits) {	111,905✔
92	return BigInt::zero();	248✔
93	}
94
95	BOTAN_ASSERT_NOMSG(y_bits >= 1);	111,657✔
96	const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	111,657✔
97	const size_t y_words = y.sig_words();	111,657✔
98
99	BigInt q = BigInt::with_capacity(x_words);	111,657✔
100	BigInt r = BigInt::with_capacity(y_words + 1);	111,657✔
101	BigInt t = BigInt::with_capacity(y_words + 1); // a temporary	111,657✔
102
103	r.set_bit(y_bits - 1);	111,657✔
104	for(size_t i = y_bits - 1; i != x_bits; ++i) {	30,662,785✔
105	const size_t b = x_bits - 1 - i;	30,551,128✔
106
107	if(i >= y_bits) {	30,551,128✔
108	bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);	30,439,471✔
109	}
110
111	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	30,551,128✔
112
113	q.conditionally_set_bit(b, r_gte_y);	30,551,128✔
114
115	bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);	30,551,128✔
116	}
117
118	// No need for sign fixup
119
120	return q;	111,657✔
121	}	111,657✔
122
123	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	12,476✔
124	if(y == 0) {	12,476✔
125	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
126	}
127
128	const size_t x_words = x.sig_words();	12,476✔
129	const size_t x_bits = x.bits();	12,476✔
130
131	BigInt q = BigInt::with_capacity(x_words);	12,476✔
132	word r = 0;
133
134	for(size_t i = 0; i != x_bits; ++i) {	6,571,502✔
135	const size_t b = x_bits - 1 - i;	6,559,026✔
136	const bool x_b = x.get_bit(b);	6,559,026✔
137
138	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	6,559,026✔
139
140	r <<= 1;	6,559,026✔
141	r += static_cast<word>(x_b);	6,559,026✔
142
143	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	6,559,026✔
144	q.conditionally_set_bit(b, r_gte_y.as_bool());	6,559,026✔
145	r = r_gte_y.select(r - y, r);	6,559,026✔
146	}
147
148	if(x.is_negative()) {	12,476✔
149	q.flip_sign();	23✔
150	if(r != 0) {	23✔
151	--q;	19✔
152	r = y - r;	19✔
153	}
154	}
155
156	r_out = r;	12,476✔
157	q_out = q;	12,476✔
158	}	12,476✔
159
160	BigInt ct_divide_word(const BigInt& x, word y) {	4,340✔
161	BigInt q;	4,340✔
162	word r = 0;	4,340✔
163	ct_divide_word(x, y, q, r);	4,340✔
164	BOTAN_UNUSED(r);	4,340✔
165	return q;	4,340✔
166	}	×
167
168	word ct_mod_word(const BigInt& x, word y) {	4,340✔
169	BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");	4,340✔
170	BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");	4,340✔
171
172	const size_t x_bits = x.bits();	4,340✔
173
174	word r = 0;	4,340✔
175
176	for(size_t i = 0; i != x_bits; ++i) {	3,028,635✔
177	const size_t b = x_bits - 1 - i;	3,024,295✔
178	const bool x_b = x.get_bit(b);	3,024,295✔
179
180	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	3,024,295✔
181
182	r <<= 1;	3,024,295✔
183	r += static_cast<word>(x_b);	3,024,295✔
184
185	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	3,024,295✔
186	r = r_gte_y.select(r - y, r);	3,024,295✔
187	}
188
189	return r;	4,340✔
190	}
191
192	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	3,585✔
193	if(y.is_negative() \|\| y.is_zero()) {	7,170✔
194	throw Invalid_Argument("ct_modulo requires y > 0");	×
195	}
196
197	const size_t y_words = y.sig_words();	3,585✔
198
199	const size_t x_bits = x.bits();	3,585✔
200
201	BigInt r = BigInt::with_capacity(y_words);	3,585✔
202	BigInt t = BigInt::with_capacity(y_words);	3,585✔
203
204	for(size_t i = 0; i != x_bits; ++i) {	5,383,476✔
205	const size_t b = x_bits - 1 - i;	5,379,891✔
206	const bool x_b = x.get_bit(b);	5,379,891✔
207
208	r <<= 1;	5,379,891✔
209	r.conditionally_set_bit(0, x_b);	5,379,891✔
210
211	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	5,379,891✔
212
213	r.ct_cond_swap(r_gte_y, t);	5,379,891✔
214	}
215
216	if(x.is_negative()) {	3,585✔
217	if(r.is_nonzero()) {	94✔
218	r = y - r;	45✔
219	}
220	}
221
222	return r;	3,585✔
223	}	3,585✔
224
225	BigInt vartime_divide_pow2k(size_t k, const BigInt& y_arg) {	153,139✔
226	constexpr size_t WB = WordInfo<word>::bits;	153,139✔
227
228	BOTAN_ARG_CHECK(!y_arg.is_zero(), "Cannot divide by zero");	153,139✔
229	BOTAN_ARG_CHECK(!y_arg.is_negative(), "Negative divisor not supported");	153,139✔
230	BOTAN_ARG_CHECK(k > 1, "Invalid k");	153,139✔
231
232	BigInt y = y_arg;	153,139✔
233
234	const size_t y_words = y.sig_words();	153,139✔
235
236	BOTAN_ASSERT_NOMSG(y_words > 0);	153,139✔
237
238	// Calculate shifts needed to normalize y with high bit set
239	const size_t shifts = y.top_bits_free();	153,139✔
240
241	if(shifts > 0) {	153,139✔
242	y <<= shifts;	131,825✔
243	}
244
245	BigInt r;	153,139✔
246	r.set_bit(k + shifts); // (2^k) << shifts	153,139✔
247
248	// we know y has not changed size, since we only shifted up to set high bit
249	const size_t t = y_words - 1;	153,139✔
250	const size_t n = std::max(y_words, r.sig_words()) - 1;	306,278✔
251
252	BOTAN_ASSERT_NOMSG(n >= t);	153,139✔
253
254	BigInt q = BigInt::zero();	153,139✔
255	q.grow_to(n - t + 1);	153,139✔
256
257	word* q_words = q.mutable_data();	153,139✔
258
259	BigInt shifted_y = y << (WB * (n - t));	153,139✔
260
261	// Set q_{n-t} to number of times r > shifted_y
262	secure_vector<word> ws;	153,139✔
263	q_words[n - t] = r.reduce_below(shifted_y, ws);	153,139✔
264
265	const word y_t0 = y.word_at(t);	153,139✔
266	const word y_t1 = y.word_at(t - 1);	153,139✔
267	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	153,139✔
268
269	divide_precomp div_y_t0(y_t0);	153,139✔
270
271	for(size_t i = n; i != t; --i) {	1,339,443✔
272	const word x_i0 = r.word_at(i);	1,186,304✔
273	const word x_i1 = r.word_at(i - 1);	1,186,304✔
274	const word x_i2 = r.word_at(i - 2);	1,186,304✔
275
276	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	2,372,366✔
277
278	// Per HAC 14.23, this operation is required at most twice
279	for(size_t j = 0; j != 2; ++j) {	1,476,638✔
280	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	2,934,584✔
281	BOTAN_ASSERT_NOMSG(qit > 0);	290,334✔
282	qit--;	290,334✔
283	} else {
284	break;
285	}
286	}
287
288	shifted_y >>= WB;	1,186,304✔
289	// Now shifted_y == y << (WB * (i-t-1))
290
291	/*
292	* Special case qit == 0 and qit == 1 which occurs relatively often here due to a
293	* combination of the fixed 2^k and in many cases the typical structure of
294	* public moduli (as this function is called by Barrett_Reduction::for_public_modulus).
295	*
296	* Over the test suite, about 5% of loop iterations have qit == 1 and 10% have qit == 0
297	*/
298
299	if(qit != 0) {	1,186,304✔
300	if(qit == 1) {	1,077,516✔
301	r -= shifted_y;	21,847✔
302	} else {
303	r -= qit * shifted_y;	1,055,669✔
304	}
305
306	if(r.is_negative()) {	1,077,516✔
307	BOTAN_ASSERT_NOMSG(qit > 0);	2,407✔
308	qit--;	2,407✔
309	r += shifted_y;	2,407✔
310	BOTAN_ASSERT_NOMSG(r.is_positive());	2,407✔
311	}
312	}
313
314	q_words[i - t - 1] = qit;	1,186,304✔
315	}
316
317	return q;	306,278✔
318	}	153,139✔
319
320	/*
321	* Solve x = q * y + r
322	*
323	* See Handbook of Applied Cryptography algorithm 14.20
324	*/
325	void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {	290,607✔
326	constexpr size_t WB = WordInfo<word>::bits;	290,607✔
327
328	if(y_arg.is_zero()) {	290,685✔
329	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
330	}
331
332	const size_t y_words = y_arg.sig_words();	290,607✔
333
334	BOTAN_ASSERT_NOMSG(y_words > 0);	290,607✔
335
336	BigInt y = y_arg;	290,607✔
337
338	BigInt r = x;	290,607✔
339	BigInt q = BigInt::zero();	290,607✔
340	secure_vector<word> ws;	290,607✔
341
342	r.set_sign(BigInt::Positive);	290,607✔
343	y.set_sign(BigInt::Positive);	290,607✔
344
345	// Calculate shifts needed to normalize y with high bit set
346	const size_t shifts = y.top_bits_free();	290,607✔
347
348	if(shifts > 0) {	290,607✔
349	y <<= shifts;	277,999✔
350	r <<= shifts;	277,999✔
351	}
352
353	// we know y has not changed size, since we only shifted up to set high bit
354	const size_t t = y_words - 1;	290,607✔
355	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	569,724✔
356
357	BOTAN_ASSERT_NOMSG(n >= t);	290,607✔
358
359	q.grow_to(n - t + 1);	290,607✔
360
361	word* q_words = q.mutable_data();	290,607✔
362
363	BigInt shifted_y = y << (WB * (n - t));	290,607✔
364
365	// Set q_{n-t} to number of times r > shifted_y
366	q_words[n - t] = r.reduce_below(shifted_y, ws);	290,607✔
367
368	const word y_t0 = y.word_at(t);	290,607✔
369	const word y_t1 = y.word_at(t - 1);	290,607✔
370	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	290,607✔
371
372	divide_precomp div_y_t0(y_t0);	290,607✔
373
374	for(size_t i = n; i != t; --i) {	2,829,939✔
375	const word x_i0 = r.word_at(i);	2,539,332✔
376	const word x_i1 = r.word_at(i - 1);	2,539,332✔
377	const word x_i2 = r.word_at(i - 2);	2,539,332✔
378
379	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	5,078,498✔
380
381	// Per HAC 14.23, this operation is required at most twice
382	for(size_t j = 0; j != 2; ++j) {	3,062,785✔
383	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	6,105,540✔
384	BOTAN_ASSERT_NOMSG(qit > 0);	523,453✔
385	qit--;	523,453✔
386	} else {
387	break;
388	}
389	}
390
391	shifted_y >>= WB;	2,539,332✔
392	// Now shifted_y == y << (WB * (i-t-1))
393
394	if(qit != 0) {	2,539,332✔
395	r -= qit * shifted_y;	2,538,761✔
396	if(r.is_negative()) {	2,538,761✔
397	BOTAN_ASSERT_NOMSG(qit > 0);	531✔
398	qit--;	531✔
399	r += shifted_y;	531✔
400	BOTAN_ASSERT_NOMSG(r.is_positive());	531✔
401	}
402	}
403
404	q_words[i - t - 1] = qit;	2,539,332✔
405	}
406
407	if(shifts > 0) {	290,607✔
408	r >>= shifts;	277,999✔
409	}
410
411	sign_fixup(x, y_arg, q, r);	290,607✔
412
413	r_out = r;	290,607✔
414	q_out = q;	290,607✔
415	}	581,214✔
416
417	} // namespace Botan

randombit / botan / 17301257033

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous