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

20

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

293,887✔

21

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

293,887✔

23

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

295,146✔

24

      q -= 1;

1,255✔

25

      r = y.abs() - r;

1,255✔

27

293,887✔

29

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

4,534,855✔

35

   word y3 = 0;

4,534,855✔

36

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

4,534,855✔

37

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

4,534,855✔

39

   if(x3 != y3) {

4,534,855✔

40

      return (y3 > x3);

1,572,206✔

42

   if(x2 != y2) {

2,962,649✔

43

      return (y2 > x2);

2,842,276✔

45

   return (y1 > x1);

120,373✔

50

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

6,663✔

51

   if(y.is_zero()) {

11,288✔

55

   const size_t x_words = x.sig_words();

6,663✔

56

   const size_t y_words = y.sig_words();

6,663✔

58

   const size_t x_bits = x.bits();

6,663✔

60

   BigInt q = BigInt::with_capacity(x_words);

6,663✔

61

   BigInt r = BigInt::with_capacity(y_words);

6,663✔

62

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

6,663✔

64

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

6,070,235✔

65

      const size_t b = x_bits - 1 - i;

6,063,572✔

66

      const bool x_b = x.get_bit(b);

6,063,572✔

68

      r <<= 1;

6,063,572✔

69

      r.conditionally_set_bit(0, x_b);

6,063,572✔

71

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

6,063,572✔

73

      q.conditionally_set_bit(b, r_gte_y);

6,063,572✔

74

      r.ct_cond_swap(r_gte_y, t);

6,063,572✔

77

   sign_fixup(x, y, q, r);

6,663✔

78

   r_out = r;

6,663✔

79

   q_out = q;

6,663✔

80

6,663✔

82

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

113,657✔

83

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

114,035✔

84

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

113,657✔

85

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

113,657✔

87

   const size_t x_bits = k + 1;

113,657✔

88

   const size_t y_bits = y.bits();

113,657✔

90

   if(x_bits < y_bits) {

113,657✔

91

      return BigInt::zero();

266✔

94

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

113,391✔

95

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

113,391✔

96

   const size_t y_words = y.sig_words();

113,391✔

98

   BigInt q = BigInt::with_capacity(x_words);

113,391✔

99

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

113,391✔

100

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

113,391✔

102

   r.set_bit(y_bits - 1);

113,391✔

103

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

32,301,782✔

104

      const size_t b = x_bits - 1 - i;

32,188,391✔

106

      if(i >= y_bits) {

32,188,391✔

107

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

32,075,000✔

110

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

32,188,391✔

112

      q.conditionally_set_bit(b, r_gte_y);

32,188,391✔

114

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

32,188,391✔

119

   return q;

113,391✔

120

113,391✔

122

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

12,450✔

123

   if(y == 0) {

12,450✔

127

   const size_t x_words = x.sig_words();

12,450✔

128

   const size_t x_bits = x.bits();

12,450✔

130

   BigInt q = BigInt::with_capacity(x_words);

12,450✔

133

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

6,546,714✔

134

      const size_t b = x_bits - 1 - i;

6,534,264✔

135

      const bool x_b = x.get_bit(b);

6,534,264✔

137

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

6,534,264✔

139

      r <<= 1;

6,534,264✔

140

      r += static_cast<word>(x_b);

6,534,264✔

142

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

6,534,264✔

143

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

6,534,264✔

144

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

6,534,264✔

147

   if(x.is_negative()) {

12,450✔

148

      q.flip_sign();

23✔

149

      if(r != 0) {

23✔

150

         --q;

19✔

151

         r = y - r;

19✔

155

   r_out = r;

12,450✔

156

   q_out = q;

12,450✔

157

12,450✔

159

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

4,333✔

160

   BigInt q;

4,333✔

161

   word r = 0;

4,333✔

162

   ct_divide_word(x, y, q, r);

4,333✔

163

   BOTAN_UNUSED(r);

4,333✔

164

   return q;

4,333✔

167

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

4,333✔

168

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

4,333✔

169

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

4,333✔

171

   const size_t x_bits = x.bits();

4,333✔

173

   word r = 0;

4,333✔

175

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

3,021,202✔

176

      const size_t b = x_bits - 1 - i;

3,016,869✔

177

      const bool x_b = x.get_bit(b);

3,016,869✔

179

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

3,016,869✔

181

      r <<= 1;

3,016,869✔

182

      r += static_cast<word>(x_b);

3,016,869✔

184

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

3,016,869✔

185

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

3,016,869✔

188

   return r;

4,333✔

191

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

3,586✔

192

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

7,172✔

196

   const size_t y_words = y.sig_words();

3,586✔

198

   const size_t x_bits = x.bits();

3,586✔

200

   BigInt r = BigInt::with_capacity(y_words);

3,586✔

201

   BigInt t = BigInt::with_capacity(y_words);

3,586✔

203

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

5,371,558✔

204

      const size_t b = x_bits - 1 - i;

5,367,972✔

205

      const bool x_b = x.get_bit(b);

5,367,972✔

207

      r <<= 1;

5,367,972✔

208

      r.conditionally_set_bit(0, x_b);

5,367,972✔

210

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

5,367,972✔

212

      r.ct_cond_swap(r_gte_y, t);

5,367,972✔

215

   if(x.is_negative()) {

3,586✔

216

      if(r.is_nonzero()) {

114✔

217

         r = y - r;

55✔

221

   return r;

3,586✔

222

3,586✔

224

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

153,102✔

225

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

153,102✔

227

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

153,102✔

228

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

153,102✔

229

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

153,102✔

231

   BigInt y = y_arg;

153,102✔

233

   const size_t y_words = y.sig_words();

153,102✔

235

   BOTAN_ASSERT_NOMSG(y_words > 0);

153,102✔

238

   const size_t shifts = y.top_bits_free();

153,102✔

240

   if(shifts > 0) {

153,102✔

241

      y <<= shifts;

131,792✔

244

   BigInt r;

153,102✔

245

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

153,102✔

248

   const size_t t = y_words - 1;

153,102✔

249

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

306,204✔

251

   BOTAN_ASSERT_NOMSG(n >= t);

153,102✔

253

   BigInt q = BigInt::zero();

153,102✔

254

   q.grow_to(n - t + 1);

153,102✔

256

   word* q_words = q.mutable_data();

153,102✔

258

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

153,102✔

261

   secure_vector<word> ws;

153,102✔

262

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

153,102✔

264

   const word y_t0 = y.word_at(t);

153,102✔

265

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

153,102✔

266

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

153,102✔

268

   divide_precomp div_y_t0(y_t0);

153,102✔

270

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

1,338,809✔

271

      const word x_i0 = r.word_at(i);

1,185,707✔

272

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

1,185,707✔

273

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

1,185,707✔

275

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

2,371,172✔

278

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

1,476,436✔

279

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

2,934,390✔

280

            BOTAN_ASSERT_NOMSG(qit > 0);

290,729✔

281

            qit--;

290,729✔

287

      shifted_y >>= WB;

1,185,707✔

298

      if(qit != 0) {

1,185,707✔

299

         if(qit == 1) {

1,076,924✔

300

            r -= shifted_y;

21,828✔

302

            r -= qit * shifted_y;

1,055,096✔

305

         if(r.is_negative()) {

1,076,924✔

306

            BOTAN_ASSERT_NOMSG(qit > 0);

2,407✔

307

            qit--;

2,407✔

308

            r += shifted_y;

2,407✔

309

            BOTAN_ASSERT_NOMSG(r.is_positive());

2,407✔

313

      q_words[i - t - 1] = qit;

1,185,707✔

316

   return q;

306,204✔

317

153,102✔

324

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

287,224✔

325

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

287,224✔

327

   if(y_arg.is_zero()) {

287,300✔

331

   const size_t y_words = y_arg.sig_words();

287,224✔

333

   BOTAN_ASSERT_NOMSG(y_words > 0);

287,224✔

335

   BigInt y = y_arg;

287,224✔

337

   BigInt r = x;

287,224✔

338

   BigInt q = BigInt::zero();

287,224✔

339

   secure_vector<word> ws;

287,224✔

341

   r.set_sign(BigInt::Positive);

287,224✔

342

   y.set_sign(BigInt::Positive);

287,224✔

345

   const size_t shifts = y.top_bits_free();

287,224✔

347

   if(shifts > 0) {

287,224✔

348

      y <<= shifts;

274,638✔

349

      r <<= shifts;

274,638✔

353

   const size_t t = y_words - 1;

287,224✔

354

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

563,011✔

356

   BOTAN_ASSERT_NOMSG(n >= t);

287,224✔

358

   q.grow_to(n - t + 1);

287,224✔

360

   word* q_words = q.mutable_data();

287,224✔

362

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

287,224✔

365

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

287,224✔

367

   const word y_t0 = y.word_at(t);

287,224✔

368

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

287,224✔

369

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

287,224✔

371

   divide_precomp div_y_t0(y_t0);

287,224✔

373

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

2,834,385✔

374

      const word x_i0 = r.word_at(i);

2,547,161✔

375

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

2,547,161✔

376

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

2,547,161✔

378

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

5,094,156✔

381

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

3,077,920✔

382

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

6,135,320✔

383

            BOTAN_ASSERT_NOMSG(qit > 0);

530,759✔

384

            qit--;

530,759✔

390

      shifted_y >>= WB;

2,547,161✔

393

      if(qit != 0) {

2,547,161✔

394

         r -= qit * shifted_y;

2,546,590✔

395

         if(r.is_negative()) {

2,546,590✔

396

            BOTAN_ASSERT_NOMSG(qit > 0);

531✔

397

            qit--;

531✔

398

            r += shifted_y;

531✔

399

            BOTAN_ASSERT_NOMSG(r.is_positive());

531✔

403

      q_words[i - t - 1] = qit;

2,547,161✔

406

   if(shifts > 0) {

287,224✔

407

      r >>= shifts;

274,638✔

410

   sign_fixup(x, y_arg, q, r);

287,224✔

412

   r_out = r;

287,224✔

413

   q_out = q;

287,224✔

414

574,448✔

randombit / botan / 19012754211

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

randombit / botan / 19012754211

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