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

21

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

290,850✔

22

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

290,850✔

24

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

291,646✔

25

      q -= 1;

792✔

26

      r = y.abs() - r;

792✔

28

290,850✔

30

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

4,676,518✔

36

   word y3 = 0;

4,676,518✔

37

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

4,676,518✔

38

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

4,676,518✔

40

   if(x3 != y3) {

4,676,518✔

41

      return (y3 > x3);

1,612,212✔

43

   if(x2 != y2) {

3,064,306✔

44

      return (y2 > x2);

2,948,665✔

46

   return (y1 > x1);

115,641✔

51

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

6,545✔

52

   if(y.is_zero()) {

11,159✔

56

   const size_t x_words = x.sig_words();

6,545✔

57

   const size_t y_words = y.sig_words();

6,545✔

59

   const size_t x_bits = x.bits();

6,545✔

61

   BigInt q = BigInt::with_capacity(x_words);

6,545✔

62

   BigInt r = BigInt::with_capacity(y_words);

6,545✔

63

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

6,545✔

65

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

6,003,210✔

66

      const size_t b = x_bits - 1 - i;

5,996,665✔

67

      const bool x_b = x.get_bit(b);

5,996,665✔

69

      r <<= 1;

5,996,665✔

70

      r.conditionally_set_bit(0, x_b);

5,996,665✔

72

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

5,996,665✔

74

      q.conditionally_set_bit(b, r_gte_y);

5,996,665✔

75

      r.ct_cond_swap(r_gte_y, t);

5,996,665✔

78

   sign_fixup(x, y, q, r);

6,545✔

79

   r_out = r;

6,545✔

80

   q_out = q;

6,545✔

81

6,545✔

83

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

104,232✔

84

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

104,610✔

85

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

104,232✔

86

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

104,232✔

88

   const size_t x_bits = k + 1;

104,232✔

89

   const size_t y_bits = y.bits();

104,232✔

91

   if(x_bits < y_bits) {

104,232✔

92

      return BigInt::zero();

231✔

95

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

104,001✔

96

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

104,001✔

97

   const size_t y_words = y.sig_words();

104,001✔

99

   BigInt q = BigInt::with_capacity(x_words);

104,001✔

100

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

104,001✔

101

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

104,001✔

103

   r.set_bit(y_bits - 1);

104,001✔

104

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

20,374,163✔

105

      const size_t b = x_bits - 1 - i;

20,270,162✔

107

      if(i >= y_bits) {

20,270,162✔

108

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

20,166,161✔

111

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

20,270,162✔

113

      q.conditionally_set_bit(b, r_gte_y);

20,270,162✔

115

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

20,270,162✔

120

   return q;

104,001✔

121

104,001✔

123

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

11,727✔

124

   if(y == 0) {

11,727✔

128

   const size_t x_words = x.sig_words();

11,727✔

129

   const size_t x_bits = x.bits();

11,727✔

131

   BigInt q = BigInt::with_capacity(x_words);

11,727✔

134

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

5,988,032✔

135

      const size_t b = x_bits - 1 - i;

5,976,305✔

136

      const bool x_b = x.get_bit(b);

5,976,305✔

138

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

5,976,305✔

140

      r <<= 1;

5,976,305✔

141

      r += static_cast<word>(x_b);

5,976,305✔

143

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

5,976,305✔

144

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

5,976,305✔

145

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

5,976,305✔

148

   if(x.is_negative()) {

11,727✔

149

      q.flip_sign();

23✔

150

      if(r != 0) {

23✔

151

         --q;

19✔

152

         r = y - r;

19✔

156

   r_out = r;

11,727✔

157

   q_out = q;

11,727✔

158

11,727✔

160

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

4,326✔

161

   BigInt q;

4,326✔

162

   word r = 0;

4,326✔

163

   ct_divide_word(x, y, q, r);

4,326✔

164

   BOTAN_UNUSED(r);

4,326✔

165

   return q;

4,326✔

168

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

239,987✔

169

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

239,987✔

170

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

239,987✔

172

   const size_t x_bits = x.bits();

239,987✔

174

   word r = 0;

239,987✔

176

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

115,502,765✔

177

      const size_t b = x_bits - 1 - i;

115,262,778✔

178

      const bool x_b = x.get_bit(b);

115,262,778✔

180

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

115,262,778✔

182

      r <<= 1;

115,262,778✔

183

      r += static_cast<word>(x_b);

115,262,778✔

185

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

115,262,778✔

186

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

115,262,778✔

189

   return r;

239,987✔

192

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

3,485✔

193

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

6,970✔

197

   const size_t y_words = y.sig_words();

3,485✔

199

   const size_t x_bits = x.bits();

3,485✔

201

   BigInt r = BigInt::with_capacity(y_words);

3,485✔

202

   BigInt t = BigInt::with_capacity(y_words);

3,485✔

204

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

5,247,035✔

205

      const size_t b = x_bits - 1 - i;

5,243,550✔

206

      const bool x_b = x.get_bit(b);

5,243,550✔

208

      r <<= 1;

5,243,550✔

209

      r.conditionally_set_bit(0, x_b);

5,243,550✔

211

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

5,243,550✔

213

      r.ct_cond_swap(r_gte_y, t);

5,243,550✔

216

   if(x.is_negative()) {

3,485✔

217

      if(r.is_nonzero()) {

74✔

218

         r = y - r;

37✔

222

   return r;

3,485✔

223

3,485✔

225

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

156,228✔

226

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

156,228✔

228

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

156,228✔

229

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

156,228✔

230

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

156,228✔

232

   BigInt y = y_arg;

156,228✔

234

   const size_t y_words = y.sig_words();

156,228✔

236

   BOTAN_ASSERT_NOMSG(y_words > 0);

156,228✔

239

   const size_t shifts = y.top_bits_free();

156,228✔

241

   if(shifts > 0) {

156,228✔

242

      y <<= shifts;

131,670✔

245

   BigInt r;

156,228✔

246

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

156,228✔

249

   const size_t t = y_words - 1;

156,228✔

250

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

312,456✔

252

   BOTAN_ASSERT_NOMSG(n >= t);

156,228✔

254

   BigInt q = BigInt::zero();

156,228✔

255

   q.grow_to(n - t + 1);

156,228✔

257

   word* q_words = q.mutable_data();

156,228✔

259

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

156,228✔

262

   secure_vector<word> ws;

156,228✔

263

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

156,228✔

265

   const word y_t0 = y.word_at(t);

156,228✔

266

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

156,228✔

267

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

156,228✔

269

   const divide_precomp div_y_t0(y_t0);

156,228✔

271

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

1,442,544✔

272

      const word x_i0 = r.word_at(i);

1,286,316✔

273

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

1,286,316✔

274

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

1,286,316✔

276

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

1,286,316✔

279

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

1,635,375✔

280

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

3,240,984✔

281

            BOTAN_ASSERT_NOMSG(qit > 0);

349,059✔

282

            qit--;

349,059✔

288

      shifted_y >>= WB;

1,286,316✔

299

      if(qit != 0) {

1,286,316✔

300

         if(qit == 1) {

1,177,794✔

301

            r -= shifted_y;

25,076✔

303

            r -= qit * shifted_y;

1,152,718✔

306

         if(r.is_negative()) {

1,177,794✔

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,286,316✔

317

   return q;

312,456✔

318

156,228✔

325

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

284,305✔

326

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

284,305✔

328

   if(y_arg.is_zero()) {

284,305✔

332

   const size_t y_words = y_arg.sig_words();

284,305✔

334

   BOTAN_ASSERT_NOMSG(y_words > 0);

284,305✔

336

   BigInt y = y_arg;

284,305✔

338

   BigInt r = x;

284,305✔

339

   BigInt q = BigInt::zero();

284,305✔

340

   secure_vector<word> ws;

284,305✔

342

   r.set_sign(BigInt::Positive);

284,305✔

343

   y.set_sign(BigInt::Positive);

284,305✔

346

   const size_t shifts = y.top_bits_free();

284,305✔

348

   if(shifts > 0) {

284,305✔

349

      y <<= shifts;

271,974✔

350

      r <<= shifts;

271,974✔

354

   const size_t t = y_words - 1;

284,305✔

355

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

557,361✔

357

   BOTAN_ASSERT_NOMSG(n >= t);

284,305✔

359

   q.grow_to(n - t + 1);

284,305✔

361

   word* q_words = q.mutable_data();

284,305✔

363

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

284,305✔

366

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

284,305✔

368

   const word y_t0 = y.word_at(t);

284,305✔

369

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

284,305✔

370

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

284,305✔

372

   const divide_precomp div_y_t0(y_t0);

284,305✔

374

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

2,818,662✔

375

      const word x_i0 = r.word_at(i);

2,534,357✔

376

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

2,534,357✔

377

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

2,534,357✔

379

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

2,534,357✔

382

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

3,066,198✔

383

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

6,112,052✔

384

            BOTAN_ASSERT_NOMSG(qit > 0);

531,841✔

385

            qit--;

531,841✔

391

      shifted_y >>= WB;

2,534,357✔

394

      if(qit != 0) {

2,534,357✔

395

         r -= qit * shifted_y;

2,533,786✔

396

         if(r.is_negative()) {

2,533,786✔

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,534,357✔

407

   if(shifts > 0) {

284,305✔

408

      r >>= shifts;

271,974✔

411

   sign_fixup(x, y_arg, q, r);

284,305✔

413

   r_out = r;

284,305✔

414

   q_out = q;

284,305✔

415

568,610✔

randombit / botan / 21753596263

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

randombit / botan / 21753596263

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