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

21

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

368,325✔

22

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

368,325✔

24

   if(x.signum() < 0 && r.signum() != 0) {

368,325✔

25

      if(y.signum() > 0) {

730✔

26

         q -= 1;

718✔

28

         q += 1;

12✔

30

      r = y.abs() - r;

730✔

32

368,325✔

34

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

4,670,720✔

40

   word y3 = 0;

4,670,720✔

41

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

4,670,720✔

42

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

4,670,720✔

44

   if(x3 != y3) {

4,670,720✔

45

      return (y3 > x3);

1,589,388✔

47

   if(x2 != y2) {

3,081,332✔

48

      return (y2 > x2);

2,967,857✔

50

   return (y1 > x1);

113,475✔

55

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

6,745✔

56

   if(y.is_zero()) {

11,384✔

60

   const size_t x_words = x.sig_words();

6,745✔

61

   const size_t y_words = y.sig_words();

6,745✔

63

   const size_t x_bits = x.bits();

6,745✔

65

   const size_t r_words = y_words + 1;

6,745✔

67

   BigInt q = BigInt::with_capacity(x_words);

6,745✔

68

   BigInt r = BigInt::with_capacity(r_words);

6,745✔

69

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

6,745✔

71

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

6,106,413✔

72

      const size_t b = x_bits - 1 - i;

6,099,668✔

73

      const bool x_b = x.get_bit(b);

6,099,668✔

75

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

6,099,668✔

76

      r.conditionally_set_bit(0, x_b);

6,099,668✔

78

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

6,099,668✔

80

      q.conditionally_set_bit(b, r_gte_y);

6,099,668✔

81

      bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), r_words);

6,099,668✔

84

   sign_fixup(x, y, q, r);

6,745✔

85

   r_out = r;

6,745✔

86

   q_out = q;

6,745✔

87

6,745✔

89

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

108,646✔

90

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

108,646✔

91

   BOTAN_ARG_CHECK(y.signum() >= 0, "Negative divisor not supported");

108,646✔

92

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

108,646✔

94

   const size_t x_bits = k + 1;

108,646✔

95

   const size_t y_bits = y.bits();

108,646✔

97

   if(x_bits < y_bits) {

108,646✔

98

      return BigInt::zero();

250✔

101

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

108,396✔

102

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

108,396✔

103

   const size_t y_words = y.sig_words();

108,396✔

105

   BigInt q = BigInt::with_capacity(x_words);

108,396✔

106

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

108,396✔

107

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

108,396✔

109

   r.set_bit(y_bits - 1);

108,396✔

110

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

24,595,787✔

111

      const size_t b = x_bits - 1 - i;

24,487,391✔

113

      if(i >= y_bits) {

24,487,391✔

114

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

24,378,995✔

117

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

24,487,391✔

119

      q.conditionally_set_bit(b, r_gte_y);

24,487,391✔

121

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

24,487,391✔

126

   return q;

108,396✔

127

108,396✔

129

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

12,263✔

130

   if(y == 0) {

12,263✔

134

   const size_t x_words = x.sig_words();

12,263✔

135

   const size_t x_bits = x.bits();

12,263✔

137

   BigInt q = BigInt::with_capacity(x_words);

12,263✔

140

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

6,500,108✔

141

      const size_t b = x_bits - 1 - i;

6,487,845✔

142

      const bool x_b = x.get_bit(b);

6,487,845✔

144

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

6,487,845✔

146

      r <<= 1;

6,487,845✔

147

      r += static_cast<word>(x_b);

6,487,845✔

149

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

6,487,845✔

150

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

6,487,845✔

151

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

6,487,845✔

154

   if(x.signum() < 0) {

12,263✔

155

      q.flip_sign();

23✔

156

      if(r != 0) {

23✔

157

         --q;

19✔

158

         r = y - r;

19✔

162

   r_out = r;

12,263✔

163

   q_out = q;

12,263✔

164

12,263✔

166

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

4,341✔

167

   BigInt q;

4,341✔

168

   word r = 0;

4,341✔

169

   ct_divide_word(x, y, q, r);

4,341✔

170

   BOTAN_UNUSED(r);

4,341✔

171

   return q;

4,341✔

174

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

278,850✔

175

   BOTAN_ARG_CHECK(x.signum() >= 0, "The argument x must be non-negative");

278,850✔

176

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

278,850✔

178

   const size_t x_bits = x.bits();

278,850✔

180

   word r = 0;

278,850✔

182

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

149,448,364✔

183

      const size_t b = x_bits - 1 - i;

149,169,514✔

184

      const bool x_b = x.get_bit(b);

149,169,514✔

186

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

149,169,514✔

188

      r <<= 1;

149,169,514✔

189

      r += static_cast<word>(x_b);

149,169,514✔

191

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

149,169,514✔

192

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

149,169,514✔

195

   return r;

278,850✔

198

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

3,682✔

199

   if(y.signum() <= 0) {

3,682✔

203

   const size_t y_words = y.sig_words();

3,682✔

204

   const size_t r_words = y_words + 1;

3,682✔

206

   const size_t x_bits = x.bits();

3,682✔

208

   BigInt r = BigInt::with_capacity(r_words);

3,682✔

209

   BigInt t = BigInt::with_capacity(r_words);

3,682✔

211

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

5,422,719✔

212

      const size_t b = x_bits - 1 - i;

5,419,037✔

213

      const bool x_b = x.get_bit(b);

5,419,037✔

215

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

5,419,037✔

216

      r.conditionally_set_bit(0, x_b);

5,419,037✔

218

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

5,419,037✔

220

      bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), r_words);

5,419,037✔

223

   if(x.signum() < 0) {

3,682✔

224

      if(r.signum() != 0) {

72✔

225

         r = y - r;

70✔

229

   return r;

3,682✔

230

3,682✔

232

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

148,940✔

233

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

148,940✔

235

   BOTAN_ARG_CHECK(y_arg.signum() != 0, "Cannot divide by zero");

148,940✔

236

   BOTAN_ARG_CHECK(y_arg.signum() >= 0, "Negative divisor not supported");

148,940✔

237

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

148,940✔

239

   BigInt y = y_arg;

148,940✔

241

   const size_t y_words = y.sig_words();

148,940✔

243

   BOTAN_ASSERT_NOMSG(y_words > 0);

148,940✔

246

   const size_t shifts = y.top_bits_free();

148,940✔

248

   if(shifts > 0) {

148,940✔

249

      y <<= shifts;

130,044✔

252

   BigInt r;

148,940✔

253

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

148,940✔

256

   const size_t t = y_words - 1;

148,940✔

257

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

297,880✔

259

   BOTAN_ASSERT_NOMSG(n >= t);

148,940✔

261

   BigInt q = BigInt::zero();

148,940✔

262

   q.grow_to(n - t + 1);

148,940✔

264

   word* q_words = q.mutable_data();

148,940✔

266

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

148,940✔

269

   secure_vector<word> ws;

148,940✔

270

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

148,940✔

272

   const word y_t0 = y.word_at(t);

148,940✔

273

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

148,940✔

274

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

148,940✔

276

   const divide_precomp div_y_t0(y_t0);

148,940✔

278

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

1,135,906✔

279

      const word x_i0 = r.word_at(i);

986,966✔

280

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

986,966✔

281

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

986,966✔

283

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

986,966✔

286

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

1,233,680✔

287

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

2,442,072✔

288

            BOTAN_ASSERT_NOMSG(qit > 0);

246,714✔

289

            qit--;

246,714✔

295

      shifted_y >>= WB;

986,966✔

306

      if(qit != 0) {

986,966✔

307

         if(qit == 1) {

880,979✔

308

            r -= shifted_y;

19,480✔

310

            r -= qit * shifted_y;

861,499✔

313

         if(r.signum() < 0) {

880,979✔

314

            BOTAN_ASSERT_NOMSG(qit > 0);

2,345✔

315

            qit--;

2,345✔

316

            r += shifted_y;

2,345✔

317

            BOTAN_ASSERT_NOMSG(r.signum() >= 0);

2,345✔

321

      q_words[i - t - 1] = qit;

986,966✔

324

   return q;

297,880✔

325

148,940✔

332

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

361,580✔

333

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

361,580✔

335

   if(y_arg.is_zero()) {

361,688✔

339

   const size_t y_words = y_arg.sig_words();

361,580✔

341

   BOTAN_ASSERT_NOMSG(y_words > 0);

361,580✔

343

   BigInt y = y_arg;

361,580✔

345

   BigInt r = x;

361,580✔

346

   BigInt q = BigInt::zero();

361,580✔

347

   secure_vector<word> ws;

361,580✔

349

   r.set_sign(BigInt::Positive);

361,580✔

350

   y.set_sign(BigInt::Positive);

361,580✔

353

   const size_t shifts = y.top_bits_free();

361,580✔

355

   if(shifts > 0) {

361,580✔

356

      y <<= shifts;

344,328✔

357

      r <<= shifts;

344,328✔

361

   const size_t t = y_words - 1;

361,580✔

362

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

707,047✔

364

   BOTAN_ASSERT_NOMSG(n >= t);

361,580✔

366

   q.grow_to(n - t + 1);

361,580✔

368

   word* q_words = q.mutable_data();

361,580✔

370

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

361,580✔

373

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

361,580✔

375

   const word y_t0 = y.word_at(t);

361,580✔

376

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

361,580✔

377

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

361,580✔

379

   const divide_precomp div_y_t0(y_t0);

361,580✔

381

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

3,202,893✔

382

      const word x_i0 = r.word_at(i);

2,841,313✔

383

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

2,841,313✔

384

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

2,841,313✔

386

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

2,841,313✔

389

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

3,465,448✔

390

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

6,899,368✔

391

            BOTAN_ASSERT_NOMSG(qit > 0);

624,135✔

392

            qit--;

624,135✔

398

      shifted_y >>= WB;

2,841,313✔

401

      if(qit != 0) {

2,841,313✔

402

         r -= qit * shifted_y;

2,840,740✔

403

         if(r.signum() < 0) {

2,840,740✔

404

            BOTAN_ASSERT_NOMSG(qit > 0);

531✔

405

            qit--;

531✔

406

            r += shifted_y;

531✔

407

            BOTAN_ASSERT_NOMSG(r.signum() >= 0);

531✔

411

      q_words[i - t - 1] = qit;

2,841,313✔

414

   if(shifts > 0) {

361,580✔

415

      r >>= shifts;

344,328✔

418

   sign_fixup(x, y_arg, q, r);

361,580✔

420

   r_out = r;

361,580✔

421

   q_out = q;

361,580✔

422

723,160✔

randombit / botan / 25650639339

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

randombit / botan / 25650639339

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