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

22

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

357,992✔

23

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

357,992✔

25

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

358,928✔

26

      q -= 1;

932✔

27

      r = y.abs() - r;

932✔

29

357,992✔

31

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

4,749,927✔

37

   word y3 = 0;

4,749,927✔

38

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

4,749,927✔

39

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

4,749,927✔

41

   if(x3 != y3) {

4,749,927✔

42

      return (y3 > x3);

1,643,866✔

44

   if(x2 != y2) {

3,106,061✔

45

      return (y2 > x2);

2,990,072✔

47

   return (y1 > x1);

115,989✔

52

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

6,667✔

53

   if(y.is_zero()) {

11,306✔

57

   const size_t x_words = x.sig_words();

6,667✔

58

   const size_t y_words = y.sig_words();

6,667✔

60

   const size_t x_bits = x.bits();

6,667✔

62

   BigInt q = BigInt::with_capacity(x_words);

6,667✔

63

   BigInt r = BigInt::with_capacity(y_words);

6,667✔

64

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

6,667✔

66

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

6,079,816✔

67

      const size_t b = x_bits - 1 - i;

6,073,149✔

68

      const bool x_b = x.get_bit(b);

6,073,149✔

70

      r <<= 1;

6,073,149✔

71

      r.conditionally_set_bit(0, x_b);

6,073,149✔

73

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

6,073,149✔

75

      q.conditionally_set_bit(b, r_gte_y);

6,073,149✔

76

      r.ct_cond_swap(r_gte_y, t);

6,073,149✔

79

   sign_fixup(x, y, q, r);

6,667✔

80

   r_out = r;

6,667✔

81

   q_out = q;

6,667✔

82

6,667✔

84

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

111,091✔

85

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

111,469✔

86

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

111,091✔

87

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

111,091✔

89

   const size_t x_bits = k + 1;

111,091✔

90

   const size_t y_bits = y.bits();

111,091✔

92

   if(x_bits < y_bits) {

111,091✔

93

      return BigInt::zero();

274✔

96

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

110,817✔

97

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

110,817✔

98

   const size_t y_words = y.sig_words();

110,817✔

100

   BigInt q = BigInt::with_capacity(x_words);

110,817✔

101

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

110,817✔

102

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

110,817✔

104

   r.set_bit(y_bits - 1);

110,817✔

105

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

27,756,745✔

106

      const size_t b = x_bits - 1 - i;

27,645,928✔

108

      if(i >= y_bits) {

27,645,928✔

109

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

27,535,111✔

112

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

27,645,928✔

114

      q.conditionally_set_bit(b, r_gte_y);

27,645,928✔

116

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

27,645,928✔

121

   return q;

110,817✔

122

110,817✔

124

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

12,386✔

125

   if(y == 0) {

12,386✔

129

   const size_t x_words = x.sig_words();

12,386✔

130

   const size_t x_bits = x.bits();

12,386✔

132

   BigInt q = BigInt::with_capacity(x_words);

12,386✔

135

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

6,515,046✔

136

      const size_t b = x_bits - 1 - i;

6,502,660✔

137

      const bool x_b = x.get_bit(b);

6,502,660✔

139

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

6,502,660✔

141

      r <<= 1;

6,502,660✔

142

      r += static_cast<word>(x_b);

6,502,660✔

144

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

6,502,660✔

145

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

6,502,660✔

146

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

6,502,660✔

149

   if(x.is_negative()) {

12,386✔

150

      q.flip_sign();

23✔

151

      if(r != 0) {

23✔

152

         --q;

19✔

153

         r = y - r;

19✔

157

   r_out = r;

12,386✔

158

   q_out = q;

12,386✔

159

12,386✔

161

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

4,341✔

162

   BigInt q;

4,341✔

163

   word r = 0;

4,341✔

164

   ct_divide_word(x, y, q, r);

4,341✔

165

   BOTAN_UNUSED(r);

4,341✔

166

   return q;

4,341✔

169

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

389,506✔

170

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

389,506✔

171

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

389,506✔

173

   const size_t x_bits = x.bits();

389,506✔

175

   word r = 0;

389,506✔

177

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

262,808,782✔

178

      const size_t b = x_bits - 1 - i;

262,419,276✔

179

      const bool x_b = x.get_bit(b);

262,419,276✔

181

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

262,419,276✔

183

      r <<= 1;

262,419,276✔

184

      r += static_cast<word>(x_b);

262,419,276✔

186

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

262,419,276✔

187

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

262,419,276✔

190

   return r;

389,506✔

193

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

3,657✔

194

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

7,314✔

198

   const size_t y_words = y.sig_words();

3,657✔

200

   const size_t x_bits = x.bits();

3,657✔

202

   BigInt r = BigInt::with_capacity(y_words);

3,657✔

203

   BigInt t = BigInt::with_capacity(y_words);

3,657✔

205

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

5,419,542✔

206

      const size_t b = x_bits - 1 - i;

5,415,885✔

207

      const bool x_b = x.get_bit(b);

5,415,885✔

209

      r <<= 1;

5,415,885✔

210

      r.conditionally_set_bit(0, x_b);

5,415,885✔

212

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

5,415,885✔

214

      r.ct_cond_swap(r_gte_y, t);

5,415,885✔

217

   if(x.is_negative()) {

3,657✔

218

      if(r.is_nonzero()) {

114✔

219

         r = y - r;

55✔

223

   return r;

3,657✔

224

3,657✔

228

size_t reduce_below(BigInt& r, const BigInt& y, secure_vector<word>& ws) {

507,807✔

229

   BOTAN_ARG_CHECK(r.is_negative() == false, "Invalid r");

507,807✔

230

   BOTAN_ARG_CHECK(y.is_negative() == false, "Invalid y");

507,807✔

232

   const size_t y_words = y.sig_words();

507,807✔

234

   if(r.size() < y_words + 1) {

507,807✔

235

      r.grow_to(y_words + 1);

39,023✔

238

   if(ws.size() < y_words + 1) {

507,807✔

239

      ws.resize(y_words + 1);

507,807✔

242

   clear_mem(ws);

507,807✔

244

   size_t reductions = 0;

507,807✔

246

   for(;;) {

27,910✔

247

      const word borrow = bigint_sub3(ws.data(), r._data(), y_words + 1, y._data(), y_words);

535,717✔

248

      if(borrow > 0) {

535,717✔

252

      ++reductions;

27,910✔

253

      r.swap_reg(ws);

27,910✔

256

   return reductions;

507,807✔

261

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

156,482✔

262

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

156,482✔

264

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

156,482✔

265

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

156,482✔

266

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

156,482✔

268

   BigInt y = y_arg;

156,482✔

270

   const size_t y_words = y.sig_words();

156,482✔

272

   BOTAN_ASSERT_NOMSG(y_words > 0);

156,482✔

275

   const size_t shifts = y.top_bits_free();

156,482✔

277

   if(shifts > 0) {

156,482✔

278

      y <<= shifts;

131,704✔

281

   BigInt r;

156,482✔

282

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

156,482✔

285

   const size_t t = y_words - 1;

156,482✔

286

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

312,964✔

288

   BOTAN_ASSERT_NOMSG(n >= t);

156,482✔

290

   BigInt q = BigInt::zero();

156,482✔

291

   q.grow_to(n - t + 1);

156,482✔

293

   word* q_words = q.mutable_data();

156,482✔

295

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

156,482✔

298

   secure_vector<word> ws;

156,482✔

299

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

156,482✔

301

   const word y_t0 = y.word_at(t);

156,482✔

302

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

156,482✔

303

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

156,482✔

305

   const divide_precomp div_y_t0(y_t0);

156,482✔

307

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

1,446,307✔

308

      const word x_i0 = r.word_at(i);

1,289,825✔

309

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

1,289,825✔

310

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

1,289,825✔

312

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

1,289,825✔

315

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

1,638,732✔

316

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

3,247,734✔

317

            BOTAN_ASSERT_NOMSG(qit > 0);

348,907✔

318

            qit--;

348,907✔

324

      shifted_y >>= WB;

1,289,825✔

335

      if(qit != 0) {

1,289,825✔

336

         if(qit == 1) {

1,181,114✔

337

            r -= shifted_y;

25,286✔

339

            r -= qit * shifted_y;

1,155,828✔

342

         if(r.is_negative()) {

1,181,114✔

343

            BOTAN_ASSERT_NOMSG(qit > 0);

2,401✔

344

            qit--;

2,401✔

345

            r += shifted_y;

2,401✔

346

            BOTAN_ASSERT_NOMSG(r.is_positive());

2,401✔

350

      q_words[i - t - 1] = qit;

1,289,825✔

353

   return q;

312,964✔

354

156,482✔

361

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

351,325✔

362

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

351,325✔

364

   if(y_arg.is_zero()) {

351,391✔

368

   const size_t y_words = y_arg.sig_words();

351,325✔

370

   BOTAN_ASSERT_NOMSG(y_words > 0);

351,325✔

372

   BigInt y = y_arg;

351,325✔

374

   BigInt r = x;

351,325✔

375

   BigInt q = BigInt::zero();

351,325✔

376

   secure_vector<word> ws;

351,325✔

378

   r.set_sign(BigInt::Positive);

351,325✔

379

   y.set_sign(BigInt::Positive);

351,325✔

382

   const size_t shifts = y.top_bits_free();

351,325✔

384

   if(shifts > 0) {

351,325✔

385

      y <<= shifts;

337,835✔

386

      r <<= shifts;

337,835✔

390

   const size_t t = y_words - 1;

351,325✔

391

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

699,682✔

393

   BOTAN_ASSERT_NOMSG(n >= t);

351,325✔

395

   q.grow_to(n - t + 1);

351,325✔

397

   word* q_words = q.mutable_data();

351,325✔

399

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

351,325✔

402

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

351,325✔

404

   const word y_t0 = y.word_at(t);

351,325✔

405

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

351,325✔

406

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

351,325✔

408

   const divide_precomp div_y_t0(y_t0);

351,325✔

410

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

2,955,797✔

411

      const word x_i0 = r.word_at(i);

2,604,472✔

412

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

2,604,472✔

413

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

2,604,472✔

415

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

2,604,472✔

418

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

3,135,916✔

419

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

6,252,120✔

420

            BOTAN_ASSERT_NOMSG(qit > 0);

531,444✔

421

            qit--;

531,444✔

427

      shifted_y >>= WB;

2,604,472✔

430

      if(qit != 0) {

2,604,472✔

431

         r -= qit * shifted_y;

2,603,901✔

432

         if(r.is_negative()) {

2,603,901✔

433

            BOTAN_ASSERT_NOMSG(qit > 0);

531✔

434

            qit--;

531✔

435

            r += shifted_y;

531✔

436

            BOTAN_ASSERT_NOMSG(r.is_positive());

531✔

440

      q_words[i - t - 1] = qit;

2,604,472✔

443

   if(shifts > 0) {

351,325✔

444

      r >>= shifts;

337,835✔

447

   sign_fixup(x, y_arg, q, r);

351,325✔

449

   r_out = r;

351,325✔

450

   q_out = q;

351,325✔

451

702,650✔

randombit / botan / 22852547126

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/mem_ops.h>
12	#include <botan/internal/ct_utils.h>
13	#include <botan/internal/mp_core.h>
14
15	namespace Botan {
16
17	namespace {
18
19	/*
20	* Handle signed operands, if necessary
21	*/
22	void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {	357,992✔
23	q.cond_flip_sign(x.sign() != y.sign());	357,992✔
24
25	if(x.is_negative() && r.is_nonzero()) {	358,928✔
26	q -= 1;	932✔
27	r = y.abs() - r;	932✔
28	}
29	}	357,992✔
30
31	inline bool division_check_vartime(word q, word y2, word y1, word x3, word x2, word x1) {	4,749,927✔
32	/*
33	Compute (y3,y2,y1) = (y2,y1) * q
34	and return true if (y3,y2,y1) > (x3,x2,x1)
35	*/
36
37	word y3 = 0;	4,749,927✔
38	y1 = word_madd2(q, y1, &y3);	4,749,927✔
39	y2 = word_madd2(q, y2, &y3);	4,749,927✔
40
41	if(x3 != y3) {	4,749,927✔
42	return (y3 > x3);	1,643,866✔
43	}
44	if(x2 != y2) {	3,106,061✔
45	return (y2 > x2);	2,990,072✔
46	}
47	return (y1 > x1);	115,989✔
48	}
49
50	} // namespace
51
52	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	6,667✔
53	if(y.is_zero()) {	11,306✔
54	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
55	}
56
57	const size_t x_words = x.sig_words();	6,667✔
58	const size_t y_words = y.sig_words();	6,667✔
59
60	const size_t x_bits = x.bits();	6,667✔
61
62	BigInt q = BigInt::with_capacity(x_words);	6,667✔
63	BigInt r = BigInt::with_capacity(y_words);	6,667✔
64	BigInt t = BigInt::with_capacity(y_words); // a temporary	6,667✔
65
66	for(size_t i = 0; i != x_bits; ++i) {	6,079,816✔
67	const size_t b = x_bits - 1 - i;	6,073,149✔
68	const bool x_b = x.get_bit(b);	6,073,149✔
69
70	r <<= 1;	6,073,149✔
71	r.conditionally_set_bit(0, x_b);	6,073,149✔
72
73	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	6,073,149✔
74
75	q.conditionally_set_bit(b, r_gte_y);	6,073,149✔
76	r.ct_cond_swap(r_gte_y, t);	6,073,149✔
77	}
78
79	sign_fixup(x, y, q, r);	6,667✔
80	r_out = r;	6,667✔
81	q_out = q;	6,667✔
82	}	6,667✔
83
84	BigInt ct_divide_pow2k(size_t k, const BigInt& y) {	111,091✔
85	BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");	111,469✔
86	BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");	111,091✔
87	BOTAN_ARG_CHECK(k > 1, "Invalid k");	111,091✔
88
89	const size_t x_bits = k + 1;	111,091✔
90	const size_t y_bits = y.bits();	111,091✔
91
92	if(x_bits < y_bits) {	111,091✔
93	return BigInt::zero();	274✔
94	}
95
96	BOTAN_ASSERT_NOMSG(y_bits >= 1);	110,817✔
97	const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	110,817✔
98	const size_t y_words = y.sig_words();	110,817✔
99
100	BigInt q = BigInt::with_capacity(x_words);	110,817✔
101	BigInt r = BigInt::with_capacity(y_words + 1);	110,817✔
102	BigInt t = BigInt::with_capacity(y_words + 1); // a temporary	110,817✔
103
104	r.set_bit(y_bits - 1);	110,817✔
105	for(size_t i = y_bits - 1; i != x_bits; ++i) {	27,756,745✔
106	const size_t b = x_bits - 1 - i;	27,645,928✔
107
108	if(i >= y_bits) {	27,645,928✔
109	bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);	27,535,111✔
110	}
111
112	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	27,645,928✔
113
114	q.conditionally_set_bit(b, r_gte_y);	27,645,928✔
115
116	bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);	27,645,928✔
117	}
118
119	// No need for sign fixup
120
121	return q;	110,817✔
122	}	110,817✔
123
124	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	12,386✔
125	if(y == 0) {	12,386✔
126	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
127	}
128
129	const size_t x_words = x.sig_words();	12,386✔
130	const size_t x_bits = x.bits();	12,386✔
131
132	BigInt q = BigInt::with_capacity(x_words);	12,386✔
133	word r = 0;
134
135	for(size_t i = 0; i != x_bits; ++i) {	6,515,046✔
136	const size_t b = x_bits - 1 - i;	6,502,660✔
137	const bool x_b = x.get_bit(b);	6,502,660✔
138
139	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	6,502,660✔
140
141	r <<= 1;	6,502,660✔
142	r += static_cast<word>(x_b);	6,502,660✔
143
144	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	6,502,660✔
145	q.conditionally_set_bit(b, r_gte_y.as_bool());	6,502,660✔
146	r = r_gte_y.select(r - y, r);	6,502,660✔
147	}
148
149	if(x.is_negative()) {	12,386✔
150	q.flip_sign();	23✔
151	if(r != 0) {	23✔
152	--q;	19✔
153	r = y - r;	19✔
154	}
155	}
156
157	r_out = r;	12,386✔
158	q_out = q;	12,386✔
159	}	12,386✔
160
161	BigInt ct_divide_word(const BigInt& x, word y) {	4,341✔
162	BigInt q;	4,341✔
163	word r = 0;	4,341✔
164	ct_divide_word(x, y, q, r);	4,341✔
165	BOTAN_UNUSED(r);	4,341✔
166	return q;	4,341✔
167	}	×
168
169	word ct_mod_word(const BigInt& x, word y) {	389,506✔
170	BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");	389,506✔
171	BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");	389,506✔
172
173	const size_t x_bits = x.bits();	389,506✔
174
175	word r = 0;	389,506✔
176
177	for(size_t i = 0; i != x_bits; ++i) {	262,808,782✔
178	const size_t b = x_bits - 1 - i;	262,419,276✔
179	const bool x_b = x.get_bit(b);	262,419,276✔
180
181	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	262,419,276✔
182
183	r <<= 1;	262,419,276✔
184	r += static_cast<word>(x_b);	262,419,276✔
185
186	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	262,419,276✔
187	r = r_gte_y.select(r - y, r);	262,419,276✔
188	}
189
190	return r;	389,506✔
191	}
192
193	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	3,657✔
194	if(y.is_negative() \|\| y.is_zero()) {	7,314✔
195	throw Invalid_Argument("ct_modulo requires y > 0");	×
196	}
197
198	const size_t y_words = y.sig_words();	3,657✔
199
200	const size_t x_bits = x.bits();	3,657✔
201
202	BigInt r = BigInt::with_capacity(y_words);	3,657✔
203	BigInt t = BigInt::with_capacity(y_words);	3,657✔
204
205	for(size_t i = 0; i != x_bits; ++i) {	5,419,542✔
206	const size_t b = x_bits - 1 - i;	5,415,885✔
207	const bool x_b = x.get_bit(b);	5,415,885✔
208
209	r <<= 1;	5,415,885✔
210	r.conditionally_set_bit(0, x_b);	5,415,885✔
211
212	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	5,415,885✔
213
214	r.ct_cond_swap(r_gte_y, t);	5,415,885✔
215	}
216
217	if(x.is_negative()) {	3,657✔
218	if(r.is_nonzero()) {	114✔
219	r = y - r;	55✔
220	}
221	}
222
223	return r;	3,657✔
224	}	3,657✔
225
226	namespace {
227
228	size_t reduce_below(BigInt& r, const BigInt& y, secure_vector<word>& ws) {	507,807✔
229	BOTAN_ARG_CHECK(r.is_negative() == false, "Invalid r");	507,807✔
230	BOTAN_ARG_CHECK(y.is_negative() == false, "Invalid y");	507,807✔
231
232	const size_t y_words = y.sig_words();	507,807✔
233
234	if(r.size() < y_words + 1) {	507,807✔
235	r.grow_to(y_words + 1);	39,023✔
236	}
237
238	if(ws.size() < y_words + 1) {	507,807✔
239	ws.resize(y_words + 1);	507,807✔
240	}
241
242	clear_mem(ws);	507,807✔
243
244	size_t reductions = 0;	507,807✔
245
246	for(;;) {	27,910✔
247	const word borrow = bigint_sub3(ws.data(), r._data(), y_words + 1, y._data(), y_words);	535,717✔
248	if(borrow > 0) {	535,717✔
249	break;
250	}
251
252	++reductions;	27,910✔
253	r.swap_reg(ws);	27,910✔
254	}
255
256	return reductions;	507,807✔
257	}
258
259	} // namespace
260
261	BigInt vartime_divide_pow2k(size_t k, const BigInt& y_arg) {	156,482✔
262	constexpr size_t WB = WordInfo<word>::bits;	156,482✔
263
264	BOTAN_ARG_CHECK(!y_arg.is_zero(), "Cannot divide by zero");	156,482✔
265	BOTAN_ARG_CHECK(!y_arg.is_negative(), "Negative divisor not supported");	156,482✔
266	BOTAN_ARG_CHECK(k > 1, "Invalid k");	156,482✔
267
268	BigInt y = y_arg;	156,482✔
269
270	const size_t y_words = y.sig_words();	156,482✔
271
272	BOTAN_ASSERT_NOMSG(y_words > 0);	156,482✔
273
274	// Calculate shifts needed to normalize y with high bit set
275	const size_t shifts = y.top_bits_free();	156,482✔
276
277	if(shifts > 0) {	156,482✔
278	y <<= shifts;	131,704✔
279	}
280
281	BigInt r;	156,482✔
282	r.set_bit(k + shifts); // (2^k) << shifts	156,482✔
283
284	// we know y has not changed size, since we only shifted up to set high bit
285	const size_t t = y_words - 1;	156,482✔
286	const size_t n = std::max(y_words, r.sig_words()) - 1;	312,964✔
287
288	BOTAN_ASSERT_NOMSG(n >= t);	156,482✔
289
290	BigInt q = BigInt::zero();	156,482✔
291	q.grow_to(n - t + 1);	156,482✔
292
293	word* q_words = q.mutable_data();	156,482✔
294
295	BigInt shifted_y = y << (WB * (n - t));	156,482✔
296
297	// Set q_{n-t} to number of times r > shifted_y
298	secure_vector<word> ws;	156,482✔
299	q_words[n - t] = reduce_below(r, shifted_y, ws);	156,482✔
300
301	const word y_t0 = y.word_at(t);	156,482✔
302	const word y_t1 = y.word_at(t - 1);	156,482✔
303	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	156,482✔
304
305	const divide_precomp div_y_t0(y_t0);	156,482✔
306
307	for(size_t i = n; i != t; --i) {	1,446,307✔
308	const word x_i0 = r.word_at(i);	1,289,825✔
309	const word x_i1 = r.word_at(i - 1);	1,289,825✔
310	const word x_i2 = r.word_at(i - 2);	1,289,825✔
311
312	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	1,289,825✔
313
314	// Per HAC 14.23, this operation is required at most twice
315	for(size_t j = 0; j != 2; ++j) {	1,638,732✔
316	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	3,247,734✔
317	BOTAN_ASSERT_NOMSG(qit > 0);	348,907✔
318	qit--;	348,907✔
319	} else {
320	break;
321	}
322	}
323
324	shifted_y >>= WB;	1,289,825✔
325	// Now shifted_y == y << (WB * (i-t-1))
326
327	/*
328	* Special case qit == 0 and qit == 1 which occurs relatively often here due to a
329	* combination of the fixed 2^k and in many cases the typical structure of
330	* public moduli (as this function is called by Barrett_Reduction::for_public_modulus).
331	*
332	* Over the test suite, about 5% of loop iterations have qit == 1 and 10% have qit == 0
333	*/
334
335	if(qit != 0) {	1,289,825✔
336	if(qit == 1) {	1,181,114✔
337	r -= shifted_y;	25,286✔
338	} else {
339	r -= qit * shifted_y;	1,155,828✔
340	}
341
342	if(r.is_negative()) {	1,181,114✔
343	BOTAN_ASSERT_NOMSG(qit > 0);	2,401✔
344	qit--;	2,401✔
345	r += shifted_y;	2,401✔
346	BOTAN_ASSERT_NOMSG(r.is_positive());	2,401✔
347	}
348	}
349
350	q_words[i - t - 1] = qit;	1,289,825✔
351	}
352
353	return q;	312,964✔
354	}	156,482✔
355
356	/*
357	* Solve x = q * y + r
358	*
359	* See Handbook of Applied Cryptography algorithm 14.20
360	*/
361	void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {	351,325✔
362	constexpr size_t WB = WordInfo<word>::bits;	351,325✔
363
364	if(y_arg.is_zero()) {	351,391✔
365	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
366	}
367
368	const size_t y_words = y_arg.sig_words();	351,325✔
369
370	BOTAN_ASSERT_NOMSG(y_words > 0);	351,325✔
371
372	BigInt y = y_arg;	351,325✔
373
374	BigInt r = x;	351,325✔
375	BigInt q = BigInt::zero();	351,325✔
376	secure_vector<word> ws;	351,325✔
377
378	r.set_sign(BigInt::Positive);	351,325✔
379	y.set_sign(BigInt::Positive);	351,325✔
380
381	// Calculate shifts needed to normalize y with high bit set
382	const size_t shifts = y.top_bits_free();	351,325✔
383
384	if(shifts > 0) {	351,325✔
385	y <<= shifts;	337,835✔
386	r <<= shifts;	337,835✔
387	}
388
389	// we know y has not changed size, since we only shifted up to set high bit
390	const size_t t = y_words - 1;	351,325✔
391	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	699,682✔
392
393	BOTAN_ASSERT_NOMSG(n >= t);	351,325✔
394
395	q.grow_to(n - t + 1);	351,325✔
396
397	word* q_words = q.mutable_data();	351,325✔
398
399	BigInt shifted_y = y << (WB * (n - t));	351,325✔
400
401	// Set q_{n-t} to number of times r > shifted_y
402	q_words[n - t] = reduce_below(r, shifted_y, ws);	351,325✔
403
404	const word y_t0 = y.word_at(t);	351,325✔
405	const word y_t1 = y.word_at(t - 1);	351,325✔
406	BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);	351,325✔
407
408	const divide_precomp div_y_t0(y_t0);	351,325✔
409
410	for(size_t i = n; i != t; --i) {	2,955,797✔
411	const word x_i0 = r.word_at(i);	2,604,472✔
412	const word x_i1 = r.word_at(i - 1);	2,604,472✔
413	const word x_i2 = r.word_at(i - 2);	2,604,472✔
414
415	word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);	2,604,472✔
416
417	// Per HAC 14.23, this operation is required at most twice
418	for(size_t j = 0; j != 2; ++j) {	3,135,916✔
419	if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {	6,252,120✔
420	BOTAN_ASSERT_NOMSG(qit > 0);	531,444✔
421	qit--;	531,444✔
422	} else {
423	break;
424	}
425	}
426
427	shifted_y >>= WB;	2,604,472✔
428	// Now shifted_y == y << (WB * (i-t-1))
429
430	if(qit != 0) {	2,604,472✔
431	r -= qit * shifted_y;	2,603,901✔
432	if(r.is_negative()) {	2,603,901✔
433	BOTAN_ASSERT_NOMSG(qit > 0);	531✔
434	qit--;	531✔
435	r += shifted_y;	531✔
436	BOTAN_ASSERT_NOMSG(r.is_positive());	531✔
437	}
438	}
439
440	q_words[i - t - 1] = qit;	2,604,472✔
441	}
442
443	if(shifts > 0) {	351,325✔
444	r >>= shifts;	337,835✔
445	}
446
447	sign_fixup(x, y_arg, q, r);	351,325✔
448
449	r_out = r;	351,325✔
450	q_out = q;	351,325✔
451	}	702,650✔
452
453	} // namespace Botan

randombit / botan / 22852547126

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