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

21

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

296,702✔

22

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

296,702✔

24

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

298,087✔

25

      q -= 1;

1,381✔

26

      r = y.abs() - r;

1,381✔

28

296,702✔

30

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

4,523,824✔

36

   word y3 = 0;

4,523,824✔

37

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

4,523,824✔

38

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

4,523,824✔

40

   if(x3 != y3) {

4,523,824✔

41

      return (y3 > x3);

1,569,043✔

43

   if(x2 != y2) {

2,954,781✔

44

      return (y2 > x2);

2,834,300✔

46

   return (y1 > x1);

120,481✔

51

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

6,660✔

52

   if(y.is_zero()) {

11,292✔

56

   const size_t x_words = x.sig_words();

6,660✔

57

   const size_t y_words = y.sig_words();

6,660✔

59

   const size_t x_bits = x.bits();

6,660✔

61

   BigInt q = BigInt::with_capacity(x_words);

6,660✔

62

   BigInt r = BigInt::with_capacity(y_words);

6,660✔

63

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

6,660✔

65

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

6,064,332✔

66

      const size_t b = x_bits - 1 - i;

6,057,672✔

67

      const bool x_b = x.get_bit(b);

6,057,672✔

69

      r <<= 1;

6,057,672✔

70

      r.conditionally_set_bit(0, x_b);

6,057,672✔

72

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

6,057,672✔

74

      q.conditionally_set_bit(b, r_gte_y);

6,057,672✔

75

      r.ct_cond_swap(r_gte_y, t);

6,057,672✔

78

   sign_fixup(x, y, q, r);

6,660✔

79

   r_out = r;

6,660✔

80

   q_out = q;

6,660✔

81

6,660✔

83

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

117,513✔

84

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

117,891✔

85

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

117,513✔

86

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

117,513✔

88

   const size_t x_bits = k + 1;

117,513✔

89

   const size_t y_bits = y.bits();

117,513✔

91

   if(x_bits < y_bits) {

117,513✔

92

      return BigInt::zero();

239✔

95

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

117,274✔

96

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

117,274✔

97

   const size_t y_words = y.sig_words();

117,274✔

99

   BigInt q = BigInt::with_capacity(x_words);

117,274✔

100

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

117,274✔

101

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

117,274✔

103

   r.set_bit(y_bits - 1);

117,274✔

104

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

36,641,721✔

105

      const size_t b = x_bits - 1 - i;

36,524,447✔

107

      if(i >= y_bits) {

36,524,447✔

108

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

36,407,173✔

111

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

36,524,447✔

113

      q.conditionally_set_bit(b, r_gte_y);

36,524,447✔

115

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

36,524,447✔

120

   return q;

117,274✔

121

117,274✔

123

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

12,457✔

124

   if(y == 0) {

12,457✔

128

   const size_t x_words = x.sig_words();

12,457✔

129

   const size_t x_bits = x.bits();

12,457✔

131

   BigInt q = BigInt::with_capacity(x_words);

12,457✔

134

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

6,545,013✔

135

      const size_t b = x_bits - 1 - i;

6,532,556✔

136

      const bool x_b = x.get_bit(b);

6,532,556✔

138

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

6,532,556✔

140

      r <<= 1;

6,532,556✔

141

      r += static_cast<word>(x_b);

6,532,556✔

143

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

6,532,556✔

144

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

6,532,556✔

145

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

6,532,556✔

148

   if(x.is_negative()) {

12,457✔

149

      q.flip_sign();

23✔

150

      if(r != 0) {

23✔

151

         --q;

19✔

152

         r = y - r;

19✔

156

   r_out = r;

12,457✔

157

   q_out = q;

12,457✔

158

12,457✔

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,015,562✔

177

      const size_t b = x_bits - 1 - i;

3,011,222✔

178

      const bool x_b = x.get_bit(b);

3,011,222✔

180

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

3,011,222✔

182

      r <<= 1;

3,011,222✔

183

      r += static_cast<word>(x_b);

3,011,222✔

185

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

3,011,222✔

186

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

3,011,222✔

189

   return r;

4,340✔

192

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

3,591✔

193

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

7,182✔

197

   const size_t y_words = y.sig_words();

3,591✔

199

   const size_t x_bits = x.bits();

3,591✔

201

   BigInt r = BigInt::with_capacity(y_words);

3,591✔

202

   BigInt t = BigInt::with_capacity(y_words);

3,591✔

204

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

5,385,052✔

205

      const size_t b = x_bits - 1 - i;

5,381,461✔

206

      const bool x_b = x.get_bit(b);

5,381,461✔

208

      r <<= 1;

5,381,461✔

209

      r.conditionally_set_bit(0, x_b);

5,381,461✔

211

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

5,381,461✔

213

      r.ct_cond_swap(r_gte_y, t);

5,381,461✔

216

   if(x.is_negative()) {

3,591✔

217

      if(r.is_nonzero()) {

104✔

218

         r = y - r;

50✔

222

   return r;

3,591✔

223

3,591✔

225

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

153,116✔

226

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

153,116✔

228

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

153,116✔

229

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

153,116✔

230

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

153,116✔

232

   BigInt y = y_arg;

153,116✔

234

   const size_t y_words = y.sig_words();

153,116✔

236

   BOTAN_ASSERT_NOMSG(y_words > 0);

153,116✔

239

   const size_t shifts = y.top_bits_free();

153,116✔

241

   if(shifts > 0) {

153,116✔

242

      y <<= shifts;

131,865✔

245

   BigInt r;

153,116✔

246

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

153,116✔

249

   const size_t t = y_words - 1;

153,116✔

250

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

306,232✔

252

   BOTAN_ASSERT_NOMSG(n >= t);

153,116✔

254

   BigInt q = BigInt::zero();

153,116✔

255

   q.grow_to(n - t + 1);

153,116✔

257

   word* q_words = q.mutable_data();

153,116✔

259

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

153,116✔

262

   secure_vector<word> ws;

153,116✔

263

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

153,116✔

265

   const word y_t0 = y.word_at(t);

153,116✔

266

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

153,116✔

267

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

153,116✔

269

   divide_precomp div_y_t0(y_t0);

153,116✔

271

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

1,339,028✔

272

      const word x_i0 = r.word_at(i);

1,185,912✔

273

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

1,185,912✔

274

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

1,185,912✔

276

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

2,371,582✔

279

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

1,477,115✔

280

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

2,935,496✔

281

            BOTAN_ASSERT_NOMSG(qit > 0);

291,203✔

282

            qit--;

291,203✔

288

      shifted_y >>= WB;

1,185,912✔

299

      if(qit != 0) {

1,185,912✔

300

         if(qit == 1) {

1,077,131✔

301

            r -= shifted_y;

21,808✔

303

            r -= qit * shifted_y;

1,055,323✔

306

         if(r.is_negative()) {

1,077,131✔

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,185,912✔

317

   return q;

306,232✔

318

153,116✔

325

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

290,042✔

326

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

290,042✔

328

   if(y_arg.is_zero()) {

290,118✔

332

   const size_t y_words = y_arg.sig_words();

290,042✔

334

   BOTAN_ASSERT_NOMSG(y_words > 0);

290,042✔

336

   BigInt y = y_arg;

290,042✔

338

   BigInt r = x;

290,042✔

339

   BigInt q = BigInt::zero();

290,042✔

340

   secure_vector<word> ws;

290,042✔

342

   r.set_sign(BigInt::Positive);

290,042✔

343

   y.set_sign(BigInt::Positive);

290,042✔

346

   const size_t shifts = y.top_bits_free();

290,042✔

348

   if(shifts > 0) {

290,042✔

349

      y <<= shifts;

277,367✔

350

      r <<= shifts;

277,367✔

354

   const size_t t = y_words - 1;

290,042✔

355

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

568,479✔

357

   BOTAN_ASSERT_NOMSG(n >= t);

290,042✔

359

   q.grow_to(n - t + 1);

290,042✔

361

   word* q_words = q.mutable_data();

290,042✔

363

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

290,042✔

366

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

290,042✔

368

   const word y_t0 = y.word_at(t);

290,042✔

369

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

290,042✔

370

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

290,042✔

372

   divide_precomp div_y_t0(y_t0);

290,042✔

374

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

2,829,025✔

375

      const word x_i0 = r.word_at(i);

2,538,983✔

376

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

2,538,983✔

377

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

2,538,983✔

379

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

5,077,800✔

382

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

3,066,162✔

383

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

6,112,152✔

384

            BOTAN_ASSERT_NOMSG(qit > 0);

527,179✔

385

            qit--;

527,179✔

391

      shifted_y >>= WB;

2,538,983✔

394

      if(qit != 0) {

2,538,983✔

395

         r -= qit * shifted_y;

2,538,412✔

396

         if(r.is_negative()) {

2,538,412✔

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,538,983✔

407

   if(shifts > 0) {

290,042✔

408

      r >>= shifts;

277,367✔

411

   sign_fixup(x, y_arg, q, r);

290,042✔

413

   r_out = r;

290,042✔

414

   q_out = q;

290,042✔

415

580,084✔

randombit / botan / 17299850072

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) {	296,702✔
22	q.cond_flip_sign(x.sign() != y.sign());	296,702✔
23
24	if(x.is_negative() && r.is_nonzero()) {	298,087✔
25	q -= 1;	1,381✔
26	r = y.abs() - r;	1,381✔
27	}
28	}	296,702✔
29
30	inline bool division_check_vartime(word q, word y2, word y1, word x3, word x2, word x1) {	4,523,824✔
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,523,824✔
37	y1 = word_madd2(q, y1, &y3);	4,523,824✔
38	y2 = word_madd2(q, y2, &y3);	4,523,824✔
39
40	if(x3 != y3) {	4,523,824✔
41	return (y3 > x3);	1,569,043✔
42	}
43	if(x2 != y2) {	2,954,781✔
44	return (y2 > x2);	2,834,300✔
45	}
46	return (y1 > x1);	120,481✔
47	}
48
49	} // namespace
50
51	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	6,660✔
52	if(y.is_zero()) {	11,292✔
53	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
54	}
55
56	const size_t x_words = x.sig_words();	6,660✔
57	const size_t y_words = y.sig_words();	6,660✔
58
59	const size_t x_bits = x.bits();	6,660✔
60
61	BigInt q = BigInt::with_capacity(x_words);	6,660✔
62	BigInt r = BigInt::with_capacity(y_words);	6,660✔
63	BigInt t = BigInt::with_capacity(y_words); // a temporary	6,660✔
64
65	for(size_t i = 0; i != x_bits; ++i) {	6,064,332✔
66	const size_t b = x_bits - 1 - i;	6,057,672✔
67	const bool x_b = x.get_bit(b);	6,057,672✔
68
69	r <<= 1;	6,057,672✔
70	r.conditionally_set_bit(0, x_b);	6,057,672✔
71
72	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	6,057,672✔
73
74	q.conditionally_set_bit(b, r_gte_y);	6,057,672✔
75	r.ct_cond_swap(r_gte_y, t);	6,057,672✔
76	}
77
78	sign_fixup(x, y, q, r);	6,660✔
79	r_out = r;	6,660✔
80	q_out = q;	6,660✔
81	}	6,660✔
82
83	BigInt ct_divide_pow2k(size_t k, const BigInt& y) {	117,513✔
84	BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");	117,891✔
85	BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");	117,513✔
86	BOTAN_ARG_CHECK(k > 1, "Invalid k");	117,513✔
87
88	const size_t x_bits = k + 1;	117,513✔
89	const size_t y_bits = y.bits();	117,513✔
90
91	if(x_bits < y_bits) {	117,513✔
92	return BigInt::zero();	239✔
93	}
94
95	BOTAN_ASSERT_NOMSG(y_bits >= 1);	117,274✔
96	const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	117,274✔
97	const size_t y_words = y.sig_words();	117,274✔
98
99	BigInt q = BigInt::with_capacity(x_words);	117,274✔
100	BigInt r = BigInt::with_capacity(y_words + 1);	117,274✔
101	BigInt t = BigInt::with_capacity(y_words + 1); // a temporary	117,274✔
102
103	r.set_bit(y_bits - 1);	117,274✔
104	for(size_t i = y_bits - 1; i != x_bits; ++i) {	36,641,721✔
105	const size_t b = x_bits - 1 - i;	36,524,447✔
106
107	if(i >= y_bits) {	36,524,447✔
108	bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);	36,407,173✔
109	}
110
111	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	36,524,447✔
112
113	q.conditionally_set_bit(b, r_gte_y);	36,524,447✔
114
115	bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);	36,524,447✔
116	}
117
118	// No need for sign fixup
119
120	return q;	117,274✔
121	}	117,274✔
122
123	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	12,457✔
124	if(y == 0) {	12,457✔
125	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
126	}
127
128	const size_t x_words = x.sig_words();	12,457✔
129	const size_t x_bits = x.bits();	12,457✔
130
131	BigInt q = BigInt::with_capacity(x_words);	12,457✔
132	word r = 0;
133
134	for(size_t i = 0; i != x_bits; ++i) {	6,545,013✔
135	const size_t b = x_bits - 1 - i;	6,532,556✔
136	const bool x_b = x.get_bit(b);	6,532,556✔
137
138	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	6,532,556✔
139
140	r <<= 1;	6,532,556✔
141	r += static_cast<word>(x_b);	6,532,556✔
142
143	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	6,532,556✔
144	q.conditionally_set_bit(b, r_gte_y.as_bool());	6,532,556✔
145	r = r_gte_y.select(r - y, r);	6,532,556✔
146	}
147
148	if(x.is_negative()) {	12,457✔
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,457✔
157	q_out = q;	12,457✔
158	}	12,457✔
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,015,562✔
177	const size_t b = x_bits - 1 - i;	3,011,222✔
178	const bool x_b = x.get_bit(b);	3,011,222✔
179
180	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	3,011,222✔
181
182	r <<= 1;	3,011,222✔
183	r += static_cast<word>(x_b);	3,011,222✔
184
185	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	3,011,222✔
186	r = r_gte_y.select(r - y, r);	3,011,222✔
187	}
188
189	return r;	4,340✔
190	}
191
192	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	3,591✔
193	if(y.is_negative() \|\| y.is_zero()) {	7,182✔
194	throw Invalid_Argument("ct_modulo requires y > 0");	×
195	}
196
197	const size_t y_words = y.sig_words();	3,591✔
198
199	const size_t x_bits = x.bits();	3,591✔
200
201	BigInt r = BigInt::with_capacity(y_words);	3,591✔
202	BigInt t = BigInt::with_capacity(y_words);	3,591✔
203
204	for(size_t i = 0; i != x_bits; ++i) {	5,385,052✔
205	const size_t b = x_bits - 1 - i;	5,381,461✔
206	const bool x_b = x.get_bit(b);	5,381,461✔
207
208	r <<= 1;	5,381,461✔
209	r.conditionally_set_bit(0, x_b);	5,381,461✔
210
211	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	5,381,461✔
212
213	r.ct_cond_swap(r_gte_y, t);	5,381,461✔
214	}
215
216	if(x.is_negative()) {	3,591✔
217	if(r.is_nonzero()) {	104✔
218	r = y - r;	50✔
219	}
220	}
221
222	return r;	3,591✔
223	}	3,591✔
224
225	BigInt vartime_divide_pow2k(size_t k, const BigInt& y_arg) {	153,116✔
226	constexpr size_t WB = WordInfo<word>::bits;	153,116✔
227
228	BOTAN_ARG_CHECK(!y_arg.is_zero(), "Cannot divide by zero");	153,116✔
229	BOTAN_ARG_CHECK(!y_arg.is_negative(), "Negative divisor not supported");	153,116✔
230	BOTAN_ARG_CHECK(k > 1, "Invalid k");	153,116✔
231
232	BigInt y = y_arg;	153,116✔
233
234	const size_t y_words = y.sig_words();	153,116✔
235
236	BOTAN_ASSERT_NOMSG(y_words > 0);	153,116✔
237
238	// Calculate shifts needed to normalize y with high bit set
239	const size_t shifts = y.top_bits_free();	153,116✔
240
241	if(shifts > 0) {	153,116✔
242	y <<= shifts;	131,865✔
243	}
244
245	BigInt r;	153,116✔
246	r.set_bit(k + shifts); // (2^k) << shifts	153,116✔
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,116✔
250	const size_t n = std::max(y_words, r.sig_words()) - 1;	306,232✔
251
252	BOTAN_ASSERT_NOMSG(n >= t);	153,116✔
253
254	BigInt q = BigInt::zero();	153,116✔
255	q.grow_to(n - t + 1);	153,116✔
256
257	word* q_words = q.mutable_data();	153,116✔
258
259	BigInt shifted_y = y << (WB * (n - t));	153,116✔
260
261	// Set q_{n-t} to number of times r > shifted_y
262	secure_vector<word> ws;	153,116✔
263	q_words[n - t] = r.reduce_below(shifted_y, ws);	153,116✔
264
265	const word y_t0 = y.word_at(t);	153,116✔
266	const word y_t1 = y.word_at(t - 1);	153,116✔
267	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	153,116✔
268
269	divide_precomp div_y_t0(y_t0);	153,116✔
270
271	for(size_t i = n; i != t; --i) {	1,339,028✔
272	const word x_i0 = r.word_at(i);	1,185,912✔
273	const word x_i1 = r.word_at(i - 1);	1,185,912✔
274	const word x_i2 = r.word_at(i - 2);	1,185,912✔
275
276	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	2,371,582✔
277
278	// Per HAC 14.23, this operation is required at most twice
279	for(size_t j = 0; j != 2; ++j) {	1,477,115✔
280	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	2,935,496✔
281	BOTAN_ASSERT_NOMSG(qit > 0);	291,203✔
282	qit--;	291,203✔
283	} else {
284	break;
285	}
286	}
287
288	shifted_y >>= WB;	1,185,912✔
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,185,912✔
300	if(qit == 1) {	1,077,131✔
301	r -= shifted_y;	21,808✔
302	} else {
303	r -= qit * shifted_y;	1,055,323✔
304	}
305
306	if(r.is_negative()) {	1,077,131✔
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,185,912✔
315	}
316
317	return q;	306,232✔
318	}	153,116✔
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,042✔
326	constexpr size_t WB = WordInfo<word>::bits;	290,042✔
327
328	if(y_arg.is_zero()) {	290,118✔
329	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
330	}
331
332	const size_t y_words = y_arg.sig_words();	290,042✔
333
334	BOTAN_ASSERT_NOMSG(y_words > 0);	290,042✔
335
336	BigInt y = y_arg;	290,042✔
337
338	BigInt r = x;	290,042✔
339	BigInt q = BigInt::zero();	290,042✔
340	secure_vector<word> ws;	290,042✔
341
342	r.set_sign(BigInt::Positive);	290,042✔
343	y.set_sign(BigInt::Positive);	290,042✔
344
345	// Calculate shifts needed to normalize y with high bit set
346	const size_t shifts = y.top_bits_free();	290,042✔
347
348	if(shifts > 0) {	290,042✔
349	y <<= shifts;	277,367✔
350	r <<= shifts;	277,367✔
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,042✔
355	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	568,479✔
356
357	BOTAN_ASSERT_NOMSG(n >= t);	290,042✔
358
359	q.grow_to(n - t + 1);	290,042✔
360
361	word* q_words = q.mutable_data();	290,042✔
362
363	BigInt shifted_y = y << (WB * (n - t));	290,042✔
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,042✔
367
368	const word y_t0 = y.word_at(t);	290,042✔
369	const word y_t1 = y.word_at(t - 1);	290,042✔
370	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	290,042✔
371
372	divide_precomp div_y_t0(y_t0);	290,042✔
373
374	for(size_t i = n; i != t; --i) {	2,829,025✔
375	const word x_i0 = r.word_at(i);	2,538,983✔
376	const word x_i1 = r.word_at(i - 1);	2,538,983✔
377	const word x_i2 = r.word_at(i - 2);	2,538,983✔
378
379	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	5,077,800✔
380
381	// Per HAC 14.23, this operation is required at most twice
382	for(size_t j = 0; j != 2; ++j) {	3,066,162✔
383	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	6,112,152✔
384	BOTAN_ASSERT_NOMSG(qit > 0);	527,179✔
385	qit--;	527,179✔
386	} else {
387	break;
388	}
389	}
390
391	shifted_y >>= WB;	2,538,983✔
392	// Now shifted_y == y << (WB * (i-t-1))
393
394	if(qit != 0) {	2,538,983✔
395	r -= qit * shifted_y;	2,538,412✔
396	if(r.is_negative()) {	2,538,412✔
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,538,983✔
405	}
406
407	if(shifts > 0) {	290,042✔
408	r >>= shifts;	277,367✔
409	}
410
411	sign_fixup(x, y_arg, q, r);	290,042✔
412
413	r_out = r;	290,042✔
414	q_out = q;	290,042✔
415	}	580,084✔
416
417	} // namespace Botan

randombit / botan / 17299850072

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