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

21

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

287,081✔

22

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

287,081✔

24

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

287,868✔

25

      q -= 1;

783✔

26

      r = y.abs() - r;

783✔

28

287,081✔

30

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

4,669,010✔

36

   word y3 = 0;

4,669,010✔

37

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

4,669,010✔

38

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

4,669,010✔

40

   if(x3 != y3) {

4,669,010✔

41

      return (y3 > x3);

1,606,983✔

43

   if(x2 != y2) {

3,062,027✔

44

      return (y2 > x2);

2,946,385✔

46

   return (y1 > x1);

115,642✔

51

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

6,544✔

52

   if(y.is_zero()) {

11,157✔

56

   const size_t x_words = x.sig_words();

6,544✔

57

   const size_t y_words = y.sig_words();

6,544✔

59

   const size_t x_bits = x.bits();

6,544✔

61

   BigInt q = BigInt::with_capacity(x_words);

6,544✔

62

   BigInt r = BigInt::with_capacity(y_words);

6,544✔

63

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

6,544✔

65

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

5,989,734✔

66

      const size_t b = x_bits - 1 - i;

5,983,190✔

67

      const bool x_b = x.get_bit(b);

5,983,190✔

69

      r <<= 1;

5,983,190✔

70

      r.conditionally_set_bit(0, x_b);

5,983,190✔

72

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

5,983,190✔

74

      q.conditionally_set_bit(b, r_gte_y);

5,983,190✔

75

      r.ct_cond_swap(r_gte_y, t);

5,983,190✔

78

   sign_fixup(x, y, q, r);

6,544✔

79

   r_out = r;

6,544✔

80

   q_out = q;

6,544✔

81

6,544✔

83

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

103,629✔

84

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

104,007✔

85

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

103,629✔

86

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

103,629✔

88

   const size_t x_bits = k + 1;

103,629✔

89

   const size_t y_bits = y.bits();

103,629✔

91

   if(x_bits < y_bits) {

103,629✔

92

      return BigInt::zero();

264✔

95

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

103,365✔

96

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

103,365✔

97

   const size_t y_words = y.sig_words();

103,365✔

99

   BigInt q = BigInt::with_capacity(x_words);

103,365✔

100

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

103,365✔

101

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

103,365✔

103

   r.set_bit(y_bits - 1);

103,365✔

104

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

20,324,453✔

105

      const size_t b = x_bits - 1 - i;

20,221,088✔

107

      if(i >= y_bits) {

20,221,088✔

108

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

20,117,723✔

111

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

20,221,088✔

113

      q.conditionally_set_bit(b, r_gte_y);

20,221,088✔

115

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

20,221,088✔

120

   return q;

103,365✔

121

103,365✔

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,972,088✔

135

      const size_t b = x_bits - 1 - i;

5,960,361✔

136

      const bool x_b = x.get_bit(b);

5,960,361✔

138

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

5,960,361✔

140

      r <<= 1;

5,960,361✔

141

      r += static_cast<word>(x_b);

5,960,361✔

143

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

5,960,361✔

144

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

5,960,361✔

145

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

5,960,361✔

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,325✔

161

   BigInt q;

4,325✔

162

   word r = 0;

4,325✔

163

   ct_divide_word(x, y, q, r);

4,325✔

164

   BOTAN_UNUSED(r);

4,325✔

165

   return q;

4,325✔

168

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

248,818✔

169

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

248,818✔

170

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

248,818✔

172

   const size_t x_bits = x.bits();

248,818✔

174

   word r = 0;

248,818✔

176

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

124,910,304✔

177

      const size_t b = x_bits - 1 - i;

124,661,486✔

178

      const bool x_b = x.get_bit(b);

124,661,486✔

180

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

124,661,486✔

182

      r <<= 1;

124,661,486✔

183

      r += static_cast<word>(x_b);

124,661,486✔

185

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

124,661,486✔

186

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

124,661,486✔

189

   return r;

248,818✔

192

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

3,484✔

193

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

6,968✔

197

   const size_t y_words = y.sig_words();

3,484✔

199

   const size_t x_bits = x.bits();

3,484✔

201

   BigInt r = BigInt::with_capacity(y_words);

3,484✔

202

   BigInt t = BigInt::with_capacity(y_words);

3,484✔

204

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

5,245,858✔

205

      const size_t b = x_bits - 1 - i;

5,242,374✔

206

      const bool x_b = x.get_bit(b);

5,242,374✔

208

      r <<= 1;

5,242,374✔

209

      r.conditionally_set_bit(0, x_b);

5,242,374✔

211

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

5,242,374✔

213

      r.ct_cond_swap(r_gte_y, t);

5,242,374✔

216

   if(x.is_negative()) {

3,484✔

217

      if(r.is_nonzero()) {

74✔

218

         r = y - r;

37✔

222

   return r;

3,484✔

223

3,484✔

225

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

156,227✔

226

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

156,227✔

228

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

156,227✔

229

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

156,227✔

230

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

156,227✔

232

   BigInt y = y_arg;

156,227✔

234

   const size_t y_words = y.sig_words();

156,227✔

236

   BOTAN_ASSERT_NOMSG(y_words > 0);

156,227✔

239

   const size_t shifts = y.top_bits_free();

156,227✔

241

   if(shifts > 0) {

156,227✔

242

      y <<= shifts;

131,712✔

245

   BigInt r;

156,227✔

246

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

156,227✔

249

   const size_t t = y_words - 1;

156,227✔

250

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

312,454✔

252

   BOTAN_ASSERT_NOMSG(n >= t);

156,227✔

254

   BigInt q = BigInt::zero();

156,227✔

255

   q.grow_to(n - t + 1);

156,227✔

257

   word* q_words = q.mutable_data();

156,227✔

259

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

156,227✔

262

   secure_vector<word> ws;

156,227✔

263

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

156,227✔

265

   const word y_t0 = y.word_at(t);

156,227✔

266

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

156,227✔

267

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

156,227✔

269

   const divide_precomp div_y_t0(y_t0);

156,227✔

271

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

1,442,406✔

272

      const word x_i0 = r.word_at(i);

1,286,179✔

273

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

1,286,179✔

274

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

1,286,179✔

276

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

1,286,179✔

279

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

1,634,628✔

280

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

3,239,646✔

281

            BOTAN_ASSERT_NOMSG(qit > 0);

348,449✔

282

            qit--;

348,449✔

288

      shifted_y >>= WB;

1,286,179✔

299

      if(qit != 0) {

1,286,179✔

300

         if(qit == 1) {

1,177,660✔

301

            r -= shifted_y;

25,057✔

303

            r -= qit * shifted_y;

1,152,603✔

306

         if(r.is_negative()) {

1,177,660✔

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,179✔

317

   return q;

312,454✔

318

156,227✔

325

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

280,537✔

326

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

280,537✔

328

   if(y_arg.is_zero()) {

280,537✔

332

   const size_t y_words = y_arg.sig_words();

280,537✔

334

   BOTAN_ASSERT_NOMSG(y_words > 0);

280,537✔

336

   BigInt y = y_arg;

280,537✔

338

   BigInt r = x;

280,537✔

339

   BigInt q = BigInt::zero();

280,537✔

340

   secure_vector<word> ws;

280,537✔

342

   r.set_sign(BigInt::Positive);

280,537✔

343

   y.set_sign(BigInt::Positive);

280,537✔

346

   const size_t shifts = y.top_bits_free();

280,537✔

348

   if(shifts > 0) {

280,537✔

349

      y <<= shifts;

268,244✔

350

      r <<= shifts;

268,244✔

354

   const size_t t = y_words - 1;

280,537✔

355

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

549,828✔

357

   BOTAN_ASSERT_NOMSG(n >= t);

280,537✔

359

   q.grow_to(n - t + 1);

280,537✔

361

   word* q_words = q.mutable_data();

280,537✔

363

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

280,537✔

366

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

280,537✔

368

   const word y_t0 = y.word_at(t);

280,537✔

369

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

280,537✔

370

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

280,537✔

372

   const divide_precomp div_y_t0(y_t0);

280,537✔

374

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

2,810,026✔

375

      const word x_i0 = r.word_at(i);

2,529,489✔

376

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

2,529,489✔

377

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

2,529,489✔

379

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

2,529,489✔

382

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

3,059,477✔

383

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

6,098,374✔

384

            BOTAN_ASSERT_NOMSG(qit > 0);

529,988✔

385

            qit--;

529,988✔

391

      shifted_y >>= WB;

2,529,489✔

394

      if(qit != 0) {

2,529,489✔

395

         r -= qit * shifted_y;

2,528,918✔

396

         if(r.is_negative()) {

2,528,918✔

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,529,489✔

407

   if(shifts > 0) {

280,537✔

408

      r >>= shifts;

268,244✔

411

   sign_fixup(x, y_arg, q, r);

280,537✔

413

   r_out = r;

280,537✔

414

   q_out = q;

280,537✔

415

561,074✔

randombit / botan / 21780140538

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

randombit / botan / 21780140538

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