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

21

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

366,161✔

22

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

366,161✔

24

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

366,161✔

25

      if(y.signum() > 0) {

871✔

26

         q -= 1;

859✔

28

         q += 1;

12✔

30

      r = y.abs() - r;

871✔

32

366,161✔

34

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

4,641,944✔

40

   word y3 = 0;

4,641,944✔

41

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

4,641,944✔

42

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

4,641,944✔

44

   if(x3 != y3) {

4,641,944✔

45

      return (y3 > x3);

1,581,416✔

47

   if(x2 != y2) {

3,060,528✔

48

      return (y2 > x2);

2,947,908✔

50

   return (y1 > x1);

112,620✔

55

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

6,683✔

56

   if(y.is_zero()) {

11,323✔

60

   const size_t x_words = x.sig_words();

6,683✔

61

   const size_t y_words = y.sig_words();

6,683✔

63

   const size_t x_bits = x.bits();

6,683✔

65

   BigInt q = BigInt::with_capacity(x_words);

6,683✔

66

   BigInt r = BigInt::with_capacity(y_words);

6,683✔

67

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

6,683✔

69

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

6,066,681✔

70

      const size_t b = x_bits - 1 - i;

6,059,998✔

71

      const bool x_b = x.get_bit(b);

6,059,998✔

73

      r <<= 1;

6,059,998✔

74

      r.conditionally_set_bit(0, x_b);

6,059,998✔

76

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

6,059,998✔

78

      q.conditionally_set_bit(b, r_gte_y);

6,059,998✔

79

      r.ct_cond_swap(r_gte_y, t);

6,059,998✔

82

   sign_fixup(x, y, q, r);

6,683✔

83

   r_out = r;

6,683✔

84

   q_out = q;

6,683✔

85

6,683✔

87

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

105,661✔

88

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

105,661✔

89

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

105,661✔

90

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

105,661✔

92

   const size_t x_bits = k + 1;

105,661✔

93

   const size_t y_bits = y.bits();

105,661✔

95

   if(x_bits < y_bits) {

105,661✔

96

      return BigInt::zero();

257✔

99

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

105,404✔

100

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

105,404✔

101

   const size_t y_words = y.sig_words();

105,404✔

103

   BigInt q = BigInt::with_capacity(x_words);

105,404✔

104

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

105,404✔

105

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

105,404✔

107

   r.set_bit(y_bits - 1);

105,404✔

108

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

22,402,978✔

109

      const size_t b = x_bits - 1 - i;

22,297,574✔

111

      if(i >= y_bits) {

22,297,574✔

112

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

22,192,170✔

115

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

22,297,574✔

117

      q.conditionally_set_bit(b, r_gte_y);

22,297,574✔

119

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

22,297,574✔

124

   return q;

105,404✔

125

105,404✔

127

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

12,238✔

128

   if(y == 0) {

12,238✔

132

   const size_t x_words = x.sig_words();

12,238✔

133

   const size_t x_bits = x.bits();

12,238✔

135

   BigInt q = BigInt::with_capacity(x_words);

12,238✔

138

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

6,533,946✔

139

      const size_t b = x_bits - 1 - i;

6,521,708✔

140

      const bool x_b = x.get_bit(b);

6,521,708✔

142

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

6,521,708✔

144

      r <<= 1;

6,521,708✔

145

      r += static_cast<word>(x_b);

6,521,708✔

147

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

6,521,708✔

148

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

6,521,708✔

149

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

6,521,708✔

152

   if(x.signum() < 0) {

12,238✔

153

      q.flip_sign();

23✔

154

      if(r != 0) {

23✔

155

         --q;

19✔

156

         r = y - r;

19✔

160

   r_out = r;

12,238✔

161

   q_out = q;

12,238✔

162

12,238✔

164

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

4,342✔

165

   BigInt q;

4,342✔

166

   word r = 0;

4,342✔

167

   ct_divide_word(x, y, q, r);

4,342✔

168

   BOTAN_UNUSED(r);

4,342✔

169

   return q;

4,342✔

172

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

285,827✔

173

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

285,827✔

174

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

285,827✔

176

   const size_t x_bits = x.bits();

285,827✔

178

   word r = 0;

285,827✔

180

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

156,764,479✔

181

      const size_t b = x_bits - 1 - i;

156,478,652✔

182

      const bool x_b = x.get_bit(b);

156,478,652✔

184

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

156,478,652✔

186

      r <<= 1;

156,478,652✔

187

      r += static_cast<word>(x_b);

156,478,652✔

189

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

156,478,652✔

190

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

156,478,652✔

193

   return r;

285,827✔

196

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

3,661✔

197

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

3,661✔

201

   const size_t y_words = y.sig_words();

3,661✔

203

   const size_t x_bits = x.bits();

3,661✔

205

   BigInt r = BigInt::with_capacity(y_words);

3,661✔

206

   BigInt t = BigInt::with_capacity(y_words);

3,661✔

208

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

5,418,092✔

209

      const size_t b = x_bits - 1 - i;

5,414,431✔

210

      const bool x_b = x.get_bit(b);

5,414,431✔

212

      r <<= 1;

5,414,431✔

213

      r.conditionally_set_bit(0, x_b);

5,414,431✔

215

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

5,414,431✔

217

      r.ct_cond_swap(r_gte_y, t);

5,414,431✔

220

   if(x.signum() < 0) {

3,661✔

221

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

57✔

222

         r = y - r;

55✔

226

   return r;

3,661✔

227

3,661✔

229

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

148,082✔

230

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

148,082✔

232

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

148,082✔

233

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

148,082✔

234

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

148,082✔

236

   BigInt y = y_arg;

148,082✔

238

   const size_t y_words = y.sig_words();

148,082✔

240

   BOTAN_ASSERT_NOMSG(y_words > 0);

148,082✔

243

   const size_t shifts = y.top_bits_free();

148,082✔

245

   if(shifts > 0) {

148,082✔

246

      y <<= shifts;

129,952✔

249

   BigInt r;

148,082✔

250

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

148,082✔

253

   const size_t t = y_words - 1;

148,082✔

254

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

296,164✔

256

   BOTAN_ASSERT_NOMSG(n >= t);

148,082✔

258

   BigInt q = BigInt::zero();

148,082✔

259

   q.grow_to(n - t + 1);

148,082✔

261

   word* q_words = q.mutable_data();

148,082✔

263

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

148,082✔

266

   secure_vector<word> ws;

148,082✔

267

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

148,082✔

269

   const word y_t0 = y.word_at(t);

148,082✔

270

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

148,082✔

271

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

148,082✔

273

   const divide_precomp div_y_t0(y_t0);

148,082✔

275

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

1,129,647✔

276

      const word x_i0 = r.word_at(i);

981,565✔

277

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

981,565✔

278

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

981,565✔

280

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

981,565✔

283

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

1,229,109✔

284

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

2,432,812✔

285

            BOTAN_ASSERT_NOMSG(qit > 0);

247,544✔

286

            qit--;

247,544✔

292

      shifted_y >>= WB;

981,565✔

303

      if(qit != 0) {

981,565✔

304

         if(qit == 1) {

876,983✔

305

            r -= shifted_y;

18,525✔

307

            r -= qit * shifted_y;

858,458✔

310

         if(r.signum() < 0) {

876,983✔

311

            BOTAN_ASSERT_NOMSG(qit > 0);

2,342✔

312

            qit--;

2,342✔

313

            r += shifted_y;

2,342✔

314

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

2,342✔

318

      q_words[i - t - 1] = qit;

981,565✔

321

   return q;

296,164✔

322

148,082✔

329

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

359,478✔

330

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

359,478✔

332

   if(y_arg.is_zero()) {

359,553✔

336

   const size_t y_words = y_arg.sig_words();

359,478✔

338

   BOTAN_ASSERT_NOMSG(y_words > 0);

359,478✔

340

   BigInt y = y_arg;

359,478✔

342

   BigInt r = x;

359,478✔

343

   BigInt q = BigInt::zero();

359,478✔

344

   secure_vector<word> ws;

359,478✔

346

   r.set_sign(BigInt::Positive);

359,478✔

347

   y.set_sign(BigInt::Positive);

359,478✔

350

   const size_t shifts = y.top_bits_free();

359,478✔

352

   if(shifts > 0) {

359,478✔

353

      y <<= shifts;

342,142✔

354

      r <<= shifts;

342,142✔

358

   const size_t t = y_words - 1;

359,478✔

359

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

702,726✔

361

   BOTAN_ASSERT_NOMSG(n >= t);

359,478✔

363

   q.grow_to(n - t + 1);

359,478✔

365

   word* q_words = q.mutable_data();

359,478✔

367

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

359,478✔

370

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

359,478✔

372

   const word y_t0 = y.word_at(t);

359,478✔

373

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

359,478✔

374

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

359,478✔

376

   const divide_precomp div_y_t0(y_t0);

359,478✔

378

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

3,185,126✔

379

      const word x_i0 = r.word_at(i);

2,825,648✔

380

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

2,825,648✔

381

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

2,825,648✔

383

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

2,825,648✔

386

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

3,441,189✔

387

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

6,851,076✔

388

            BOTAN_ASSERT_NOMSG(qit > 0);

615,541✔

389

            qit--;

615,541✔

395

      shifted_y >>= WB;

2,825,648✔

398

      if(qit != 0) {

2,825,648✔

399

         r -= qit * shifted_y;

2,825,077✔

400

         if(r.signum() < 0) {

2,825,077✔

401

            BOTAN_ASSERT_NOMSG(qit > 0);

531✔

402

            qit--;

531✔

403

            r += shifted_y;

531✔

404

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

531✔

408

      q_words[i - t - 1] = qit;

2,825,648✔

411

   if(shifts > 0) {

359,478✔

412

      r >>= shifts;

342,142✔

415

   sign_fixup(x, y_arg, q, r);

359,478✔

417

   r_out = r;

359,478✔

418

   q_out = q;

359,478✔

419

718,956✔

randombit / botan / 25591581242

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

randombit / botan / 25591581242

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