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

21

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

289,548✔

22

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

289,548✔

24

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

290,296✔

25

      q -= 1;

744✔

26

      r = y.abs() - r;

744✔

28

289,548✔

30

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

4,659,441✔

36

   word y3 = 0;

4,659,441✔

37

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

4,659,441✔

38

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

4,659,441✔

40

   if(x3 != y3) {

4,659,441✔

41

      return (y3 > x3);

1,606,809✔

43

   if(x2 != y2) {

3,052,632✔

44

      return (y2 > x2);

2,937,026✔

46

   return (y1 > x1);

115,606✔

51

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

6,540✔

52

   if(y.is_zero()) {

11,149✔

56

   const size_t x_words = x.sig_words();

6,540✔

57

   const size_t y_words = y.sig_words();

6,540✔

59

   const size_t x_bits = x.bits();

6,540✔

61

   BigInt q = BigInt::with_capacity(x_words);

6,540✔

62

   BigInt r = BigInt::with_capacity(y_words);

6,540✔

63

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

6,540✔

65

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

6,001,077✔

66

      const size_t b = x_bits - 1 - i;

5,994,537✔

67

      const bool x_b = x.get_bit(b);

5,994,537✔

69

      r <<= 1;

5,994,537✔

70

      r.conditionally_set_bit(0, x_b);

5,994,537✔

72

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

5,994,537✔

74

      q.conditionally_set_bit(b, r_gte_y);

5,994,537✔

75

      r.ct_cond_swap(r_gte_y, t);

5,994,537✔

78

   sign_fixup(x, y, q, r);

6,540✔

79

   r_out = r;

6,540✔

80

   q_out = q;

6,540✔

81

6,540✔

83

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

102,165✔

84

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

102,543✔

85

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

102,165✔

86

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

102,165✔

88

   const size_t x_bits = k + 1;

102,165✔

89

   const size_t y_bits = y.bits();

102,165✔

91

   if(x_bits < y_bits) {

102,165✔

92

      return BigInt::zero();

248✔

95

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

101,917✔

96

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

101,917✔

97

   const size_t y_words = y.sig_words();

101,917✔

99

   BigInt q = BigInt::with_capacity(x_words);

101,917✔

100

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

101,917✔

101

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

101,917✔

103

   r.set_bit(y_bits - 1);

101,917✔

104

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

18,944,041✔

105

      const size_t b = x_bits - 1 - i;

18,842,124✔

107

      if(i >= y_bits) {

18,842,124✔

108

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

18,740,207✔

111

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

18,842,124✔

113

      q.conditionally_set_bit(b, r_gte_y);

18,842,124✔

115

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

18,842,124✔

120

   return q;

101,917✔

121

101,917✔

123

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

11,725✔

124

   if(y == 0) {

11,725✔

128

   const size_t x_words = x.sig_words();

11,725✔

129

   const size_t x_bits = x.bits();

11,725✔

131

   BigInt q = BigInt::with_capacity(x_words);

11,725✔

134

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

5,979,466✔

135

      const size_t b = x_bits - 1 - i;

5,967,741✔

136

      const bool x_b = x.get_bit(b);

5,967,741✔

138

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

5,967,741✔

140

      r <<= 1;

5,967,741✔

141

      r += static_cast<word>(x_b);

5,967,741✔

143

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

5,967,741✔

144

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

5,967,741✔

145

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

5,967,741✔

148

   if(x.is_negative()) {

11,725✔

149

      q.flip_sign();

23✔

150

      if(r != 0) {

23✔

151

         --q;

19✔

152

         r = y - r;

19✔

156

   r_out = r;

11,725✔

157

   q_out = q;

11,725✔

158

11,725✔

160

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

4,321✔

161

   BigInt q;

4,321✔

162

   word r = 0;

4,321✔

163

   ct_divide_word(x, y, q, r);

4,321✔

164

   BOTAN_UNUSED(r);

4,321✔

165

   return q;

4,321✔

168

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

234,862✔

169

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

234,862✔

170

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

234,862✔

172

   const size_t x_bits = x.bits();

234,862✔

174

   word r = 0;

234,862✔

176

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

110,252,163✔

177

      const size_t b = x_bits - 1 - i;

110,017,301✔

178

      const bool x_b = x.get_bit(b);

110,017,301✔

180

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

110,017,301✔

182

      r <<= 1;

110,017,301✔

183

      r += static_cast<word>(x_b);

110,017,301✔

185

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

110,017,301✔

186

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

110,017,301✔

189

   return r;

234,862✔

192

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

3,475✔

193

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

6,950✔

197

   const size_t y_words = y.sig_words();

3,475✔

199

   const size_t x_bits = x.bits();

3,475✔

201

   BigInt r = BigInt::with_capacity(y_words);

3,475✔

202

   BigInt t = BigInt::with_capacity(y_words);

3,475✔

204

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

5,242,989✔

205

      const size_t b = x_bits - 1 - i;

5,239,514✔

206

      const bool x_b = x.get_bit(b);

5,239,514✔

208

      r <<= 1;

5,239,514✔

209

      r.conditionally_set_bit(0, x_b);

5,239,514✔

211

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

5,239,514✔

213

      r.ct_cond_swap(r_gte_y, t);

5,239,514✔

216

   if(x.is_negative()) {

3,475✔

217

      if(r.is_nonzero()) {

74✔

218

         r = y - r;

37✔

222

   return r;

3,475✔

223

3,475✔

225

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

156,216✔

226

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

156,216✔

228

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

156,216✔

229

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

156,216✔

230

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

156,216✔

232

   BigInt y = y_arg;

156,216✔

234

   const size_t y_words = y.sig_words();

156,216✔

236

   BOTAN_ASSERT_NOMSG(y_words > 0);

156,216✔

239

   const size_t shifts = y.top_bits_free();

156,216✔

241

   if(shifts > 0) {

156,216✔

242

      y <<= shifts;

131,759✔

245

   BigInt r;

156,216✔

246

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

156,216✔

249

   const size_t t = y_words - 1;

156,216✔

250

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

312,432✔

252

   BOTAN_ASSERT_NOMSG(n >= t);

156,216✔

254

   BigInt q = BigInt::zero();

156,216✔

255

   q.grow_to(n - t + 1);

156,216✔

257

   word* q_words = q.mutable_data();

156,216✔

259

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

156,216✔

262

   secure_vector<word> ws;

156,216✔

263

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

156,216✔

265

   const word y_t0 = y.word_at(t);

156,216✔

266

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

156,216✔

267

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

156,216✔

269

   const divide_precomp div_y_t0(y_t0);

156,216✔

271

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

1,442,144✔

272

      const word x_i0 = r.word_at(i);

1,285,928✔

273

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

1,285,928✔

274

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

1,285,928✔

276

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

1,285,928✔

279

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

1,634,073✔

280

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

3,238,562✔

281

            BOTAN_ASSERT_NOMSG(qit > 0);

348,145✔

282

            qit--;

348,145✔

288

      shifted_y >>= WB;

1,285,928✔

299

      if(qit != 0) {

1,285,928✔

300

         if(qit == 1) {

1,177,414✔

301

            r -= shifted_y;

25,060✔

303

            r -= qit * shifted_y;

1,152,354✔

306

         if(r.is_negative()) {

1,177,414✔

307

            BOTAN_ASSERT_NOMSG(qit > 0);

2,401✔

308

            qit--;

2,401✔

309

            r += shifted_y;

2,401✔

310

            BOTAN_ASSERT_NOMSG(r.is_positive());

2,401✔

314

      q_words[i - t - 1] = qit;

1,285,928✔

317

   return q;

312,432✔

318

156,216✔

325

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

283,008✔

326

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

283,008✔

328

   if(y_arg.is_zero()) {

283,008✔

332

   const size_t y_words = y_arg.sig_words();

283,008✔

334

   BOTAN_ASSERT_NOMSG(y_words > 0);

283,008✔

336

   BigInt y = y_arg;

283,008✔

338

   BigInt r = x;

283,008✔

339

   BigInt q = BigInt::zero();

283,008✔

340

   secure_vector<word> ws;

283,008✔

342

   r.set_sign(BigInt::Positive);

283,008✔

343

   y.set_sign(BigInt::Positive);

283,008✔

346

   const size_t shifts = y.top_bits_free();

283,008✔

348

   if(shifts > 0) {

283,008✔

349

      y <<= shifts;

270,730✔

350

      r <<= shifts;

270,730✔

354

   const size_t t = y_words - 1;

283,008✔

355

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

554,725✔

357

   BOTAN_ASSERT_NOMSG(n >= t);

283,008✔

359

   q.grow_to(n - t + 1);

283,008✔

361

   word* q_words = q.mutable_data();

283,008✔

363

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

283,008✔

366

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

283,008✔

368

   const word y_t0 = y.word_at(t);

283,008✔

369

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

283,008✔

370

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

283,008✔

372

   const divide_precomp div_y_t0(y_t0);

283,008✔

374

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

2,811,071✔

375

      const word x_i0 = r.word_at(i);

2,528,063✔

376

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

2,528,063✔

377

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

2,528,063✔

379

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

2,528,063✔

382

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

3,050,416✔

383

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

6,080,320✔

384

            BOTAN_ASSERT_NOMSG(qit > 0);

522,353✔

385

            qit--;

522,353✔

391

      shifted_y >>= WB;

2,528,063✔

394

      if(qit != 0) {

2,528,063✔

395

         r -= qit * shifted_y;

2,527,492✔

396

         if(r.is_negative()) {

2,527,492✔

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,528,063✔

407

   if(shifts > 0) {

283,008✔

408

      r >>= shifts;

270,730✔

411

   sign_fixup(x, y_arg, q, r);

283,008✔

413

   r_out = r;

283,008✔

414

   q_out = q;

283,008✔

415

566,016✔

randombit / botan / 21768358452

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/exceptn.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) {	289,548✔
22	q.cond_flip_sign(x.sign() != y.sign());	289,548✔
23
24	if(x.is_negative() && r.is_nonzero()) {	290,296✔
25	q -= 1;	744✔
26	r = y.abs() - r;	744✔
27	}
28	}	289,548✔
29
30	inline bool division_check_vartime(word q, word y2, word y1, word x3, word x2, word x1) {	4,659,441✔
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,659,441✔
37	y1 = word_madd2(q, y1, &y3);	4,659,441✔
38	y2 = word_madd2(q, y2, &y3);	4,659,441✔
39
40	if(x3 != y3) {	4,659,441✔
41	return (y3 > x3);	1,606,809✔
42	}
43	if(x2 != y2) {	3,052,632✔
44	return (y2 > x2);	2,937,026✔
45	}
46	return (y1 > x1);	115,606✔
47	}
48
49	} // namespace
50
51	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	6,540✔
52	if(y.is_zero()) {	11,149✔
53	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
54	}
55
56	const size_t x_words = x.sig_words();	6,540✔
57	const size_t y_words = y.sig_words();	6,540✔
58
59	const size_t x_bits = x.bits();	6,540✔
60
61	BigInt q = BigInt::with_capacity(x_words);	6,540✔
62	BigInt r = BigInt::with_capacity(y_words);	6,540✔
63	BigInt t = BigInt::with_capacity(y_words); // a temporary	6,540✔
64
65	for(size_t i = 0; i != x_bits; ++i) {	6,001,077✔
66	const size_t b = x_bits - 1 - i;	5,994,537✔
67	const bool x_b = x.get_bit(b);	5,994,537✔
68
69	r <<= 1;	5,994,537✔
70	r.conditionally_set_bit(0, x_b);	5,994,537✔
71
72	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	5,994,537✔
73
74	q.conditionally_set_bit(b, r_gte_y);	5,994,537✔
75	r.ct_cond_swap(r_gte_y, t);	5,994,537✔
76	}
77
78	sign_fixup(x, y, q, r);	6,540✔
79	r_out = r;	6,540✔
80	q_out = q;	6,540✔
81	}	6,540✔
82
83	BigInt ct_divide_pow2k(size_t k, const BigInt& y) {	102,165✔
84	BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");	102,543✔
85	BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");	102,165✔
86	BOTAN_ARG_CHECK(k > 1, "Invalid k");	102,165✔
87
88	const size_t x_bits = k + 1;	102,165✔
89	const size_t y_bits = y.bits();	102,165✔
90
91	if(x_bits < y_bits) {	102,165✔
92	return BigInt::zero();	248✔
93	}
94
95	BOTAN_ASSERT_NOMSG(y_bits >= 1);	101,917✔
96	const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	101,917✔
97	const size_t y_words = y.sig_words();	101,917✔
98
99	BigInt q = BigInt::with_capacity(x_words);	101,917✔
100	BigInt r = BigInt::with_capacity(y_words + 1);	101,917✔
101	BigInt t = BigInt::with_capacity(y_words + 1); // a temporary	101,917✔
102
103	r.set_bit(y_bits - 1);	101,917✔
104	for(size_t i = y_bits - 1; i != x_bits; ++i) {	18,944,041✔
105	const size_t b = x_bits - 1 - i;	18,842,124✔
106
107	if(i >= y_bits) {	18,842,124✔
108	bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);	18,740,207✔
109	}
110
111	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	18,842,124✔
112
113	q.conditionally_set_bit(b, r_gte_y);	18,842,124✔
114
115	bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);	18,842,124✔
116	}
117
118	// No need for sign fixup
119
120	return q;	101,917✔
121	}	101,917✔
122
123	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	11,725✔
124	if(y == 0) {	11,725✔
125	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
126	}
127
128	const size_t x_words = x.sig_words();	11,725✔
129	const size_t x_bits = x.bits();	11,725✔
130
131	BigInt q = BigInt::with_capacity(x_words);	11,725✔
132	word r = 0;
133
134	for(size_t i = 0; i != x_bits; ++i) {	5,979,466✔
135	const size_t b = x_bits - 1 - i;	5,967,741✔
136	const bool x_b = x.get_bit(b);	5,967,741✔
137
138	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	5,967,741✔
139
140	r <<= 1;	5,967,741✔
141	r += static_cast<word>(x_b);	5,967,741✔
142
143	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	5,967,741✔
144	q.conditionally_set_bit(b, r_gte_y.as_bool());	5,967,741✔
145	r = r_gte_y.select(r - y, r);	5,967,741✔
146	}
147
148	if(x.is_negative()) {	11,725✔
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;	11,725✔
157	q_out = q;	11,725✔
158	}	11,725✔
159
160	BigInt ct_divide_word(const BigInt& x, word y) {	4,321✔
161	BigInt q;	4,321✔
162	word r = 0;	4,321✔
163	ct_divide_word(x, y, q, r);	4,321✔
164	BOTAN_UNUSED(r);	4,321✔
165	return q;	4,321✔
166	}	×
167
168	word ct_mod_word(const BigInt& x, word y) {	234,862✔
169	BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");	234,862✔
170	BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");	234,862✔
171
172	const size_t x_bits = x.bits();	234,862✔
173
174	word r = 0;	234,862✔
175
176	for(size_t i = 0; i != x_bits; ++i) {	110,252,163✔
177	const size_t b = x_bits - 1 - i;	110,017,301✔
178	const bool x_b = x.get_bit(b);	110,017,301✔
179
180	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	110,017,301✔
181
182	r <<= 1;	110,017,301✔
183	r += static_cast<word>(x_b);	110,017,301✔
184
185	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	110,017,301✔
186	r = r_gte_y.select(r - y, r);	110,017,301✔
187	}
188
189	return r;	234,862✔
190	}
191
192	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	3,475✔
193	if(y.is_negative() \|\| y.is_zero()) {	6,950✔
194	throw Invalid_Argument("ct_modulo requires y > 0");	×
195	}
196
197	const size_t y_words = y.sig_words();	3,475✔
198
199	const size_t x_bits = x.bits();	3,475✔
200
201	BigInt r = BigInt::with_capacity(y_words);	3,475✔
202	BigInt t = BigInt::with_capacity(y_words);	3,475✔
203
204	for(size_t i = 0; i != x_bits; ++i) {	5,242,989✔
205	const size_t b = x_bits - 1 - i;	5,239,514✔
206	const bool x_b = x.get_bit(b);	5,239,514✔
207
208	r <<= 1;	5,239,514✔
209	r.conditionally_set_bit(0, x_b);	5,239,514✔
210
211	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	5,239,514✔
212
213	r.ct_cond_swap(r_gte_y, t);	5,239,514✔
214	}
215
216	if(x.is_negative()) {	3,475✔
217	if(r.is_nonzero()) {	74✔
218	r = y - r;	37✔
219	}
220	}
221
222	return r;	3,475✔
223	}	3,475✔
224
225	BigInt vartime_divide_pow2k(size_t k, const BigInt& y_arg) {	156,216✔
226	constexpr size_t WB = WordInfo<word>::bits;	156,216✔
227
228	BOTAN_ARG_CHECK(!y_arg.is_zero(), "Cannot divide by zero");	156,216✔
229	BOTAN_ARG_CHECK(!y_arg.is_negative(), "Negative divisor not supported");	156,216✔
230	BOTAN_ARG_CHECK(k > 1, "Invalid k");	156,216✔
231
232	BigInt y = y_arg;	156,216✔
233
234	const size_t y_words = y.sig_words();	156,216✔
235
236	BOTAN_ASSERT_NOMSG(y_words > 0);	156,216✔
237
238	// Calculate shifts needed to normalize y with high bit set
239	const size_t shifts = y.top_bits_free();	156,216✔
240
241	if(shifts > 0) {	156,216✔
242	y <<= shifts;	131,759✔
243	}
244
245	BigInt r;	156,216✔
246	r.set_bit(k + shifts); // (2^k) << shifts	156,216✔
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;	156,216✔
250	const size_t n = std::max(y_words, r.sig_words()) - 1;	312,432✔
251
252	BOTAN_ASSERT_NOMSG(n >= t);	156,216✔
253
254	BigInt q = BigInt::zero();	156,216✔
255	q.grow_to(n - t + 1);	156,216✔
256
257	word* q_words = q.mutable_data();	156,216✔
258
259	BigInt shifted_y = y << (WB * (n - t));	156,216✔
260
261	// Set q_{n-t} to number of times r > shifted_y
262	secure_vector<word> ws;	156,216✔
263	q_words[n - t] = r.reduce_below(shifted_y, ws);	156,216✔
264
265	const word y_t0 = y.word_at(t);	156,216✔
266	const word y_t1 = y.word_at(t - 1);	156,216✔
267	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	156,216✔
268
269	const divide_precomp div_y_t0(y_t0);	156,216✔
270
271	for(size_t i = n; i != t; --i) {	1,442,144✔
272	const word x_i0 = r.word_at(i);	1,285,928✔
273	const word x_i1 = r.word_at(i - 1);	1,285,928✔
274	const word x_i2 = r.word_at(i - 2);	1,285,928✔
275
276	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	1,285,928✔
277
278	// Per HAC 14.23, this operation is required at most twice
279	for(size_t j = 0; j != 2; ++j) {	1,634,073✔
280	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	3,238,562✔
281	BOTAN_ASSERT_NOMSG(qit > 0);	348,145✔
282	qit--;	348,145✔
283	} else {
284	break;
285	}
286	}
287
288	shifted_y >>= WB;	1,285,928✔
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,285,928✔
300	if(qit == 1) {	1,177,414✔
301	r -= shifted_y;	25,060✔
302	} else {
303	r -= qit * shifted_y;	1,152,354✔
304	}
305
306	if(r.is_negative()) {	1,177,414✔
307	BOTAN_ASSERT_NOMSG(qit > 0);	2,401✔
308	qit--;	2,401✔
309	r += shifted_y;	2,401✔
310	BOTAN_ASSERT_NOMSG(r.is_positive());	2,401✔
311	}
312	}
313
314	q_words[i - t - 1] = qit;	1,285,928✔
315	}
316
317	return q;	312,432✔
318	}	156,216✔
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) {	283,008✔
326	constexpr size_t WB = WordInfo<word>::bits;	283,008✔
327
328	if(y_arg.is_zero()) {	283,008✔
329	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
330	}
331
332	const size_t y_words = y_arg.sig_words();	283,008✔
333
334	BOTAN_ASSERT_NOMSG(y_words > 0);	283,008✔
335
336	BigInt y = y_arg;	283,008✔
337
338	BigInt r = x;	283,008✔
339	BigInt q = BigInt::zero();	283,008✔
340	secure_vector<word> ws;	283,008✔
341
342	r.set_sign(BigInt::Positive);	283,008✔
343	y.set_sign(BigInt::Positive);	283,008✔
344
345	// Calculate shifts needed to normalize y with high bit set
346	const size_t shifts = y.top_bits_free();	283,008✔
347
348	if(shifts > 0) {	283,008✔
349	y <<= shifts;	270,730✔
350	r <<= shifts;	270,730✔
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;	283,008✔
355	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	554,725✔
356
357	BOTAN_ASSERT_NOMSG(n >= t);	283,008✔
358
359	q.grow_to(n - t + 1);	283,008✔
360
361	word* q_words = q.mutable_data();	283,008✔
362
363	BigInt shifted_y = y << (WB * (n - t));	283,008✔
364
365	// Set q_{n-t} to number of times r > shifted_y
366	q_words[n - t] = r.reduce_below(shifted_y, ws);	283,008✔
367
368	const word y_t0 = y.word_at(t);	283,008✔
369	const word y_t1 = y.word_at(t - 1);	283,008✔
370	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	283,008✔
371
372	const divide_precomp div_y_t0(y_t0);	283,008✔
373
374	for(size_t i = n; i != t; --i) {	2,811,071✔
375	const word x_i0 = r.word_at(i);	2,528,063✔
376	const word x_i1 = r.word_at(i - 1);	2,528,063✔
377	const word x_i2 = r.word_at(i - 2);	2,528,063✔
378
379	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	2,528,063✔
380
381	// Per HAC 14.23, this operation is required at most twice
382	for(size_t j = 0; j != 2; ++j) {	3,050,416✔
383	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	6,080,320✔
384	BOTAN_ASSERT_NOMSG(qit > 0);	522,353✔
385	qit--;	522,353✔
386	} else {
387	break;
388	}
389	}
390
391	shifted_y >>= WB;	2,528,063✔
392	// Now shifted_y == y << (WB * (i-t-1))
393
394	if(qit != 0) {	2,528,063✔
395	r -= qit * shifted_y;	2,527,492✔
396	if(r.is_negative()) {	2,527,492✔
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,528,063✔
405	}
406
407	if(shifts > 0) {	283,008✔
408	r >>= shifts;	270,730✔
409	}
410
411	sign_fixup(x, y_arg, q, r);	283,008✔
412
413	r_out = r;	283,008✔
414	q_out = q;	283,008✔
415	}	566,016✔
416
417	} // namespace Botan

randombit / botan / 21768358452

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