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

21

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

352,220✔

22

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

352,220✔

24

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

353,772✔

25

      q -= 1;

1,548✔

26

      r = y.abs() - r;

1,548✔

28

352,220✔

30

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

2,817,740✔

36

   word y3 = 0;

2,817,740✔

37

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

2,817,740✔

38

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

2,817,740✔

40

   const word x[3] = {x1, x2, x3};

2,817,740✔

41

   const word y[3] = {y1, y2, y3};

2,817,740✔

43

   return bigint_ct_is_lt(x, 3, y, 3).as_bool();

2,817,740✔

48

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

6,664✔

49

   if(y.is_zero()) {

11,297✔

53

   const size_t x_words = x.sig_words();

6,664✔

54

   const size_t y_words = y.sig_words();

6,664✔

56

   const size_t x_bits = x.bits();

6,664✔

58

   BigInt q = BigInt::with_capacity(x_words);

6,664✔

59

   BigInt r = BigInt::with_capacity(y_words);

6,664✔

60

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

6,664✔

62

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

6,076,623✔

63

      const size_t b = x_bits - 1 - i;

6,069,959✔

64

      const bool x_b = x.get_bit(b);

6,069,959✔

66

      r <<= 1;

6,069,959✔

67

      r.conditionally_set_bit(0, x_b);

6,069,959✔

69

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

6,069,959✔

71

      q.conditionally_set_bit(b, r_gte_y);

6,069,959✔

72

      r.ct_cond_swap(r_gte_y, t);

6,069,959✔

75

   sign_fixup(x, y, q, r);

6,664✔

76

   r_out = r;

6,664✔

77

   q_out = q;

6,664✔

78

6,664✔

80

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

111,877✔

81

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

112,255✔

82

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

111,877✔

83

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

111,877✔

85

   const size_t x_bits = k + 1;

111,877✔

86

   const size_t y_bits = y.bits();

111,877✔

88

   if(x_bits < y_bits) {

111,877✔

89

      return BigInt::zero();

240✔

92

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

111,637✔

93

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

111,637✔

94

   const size_t y_words = y.sig_words();

111,637✔

96

   BigInt q = BigInt::with_capacity(x_words);

111,637✔

97

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

111,637✔

98

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

111,637✔

100

   r.set_bit(y_bits - 1);

111,637✔

101

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

32,226,676✔

102

      const size_t b = x_bits - 1 - i;

32,115,039✔

104

      if(i >= y_bits) {

32,115,039✔

105

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

32,003,402✔

108

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

32,115,039✔

110

      q.conditionally_set_bit(b, r_gte_y);

32,115,039✔

112

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

32,115,039✔

117

   return q;

111,637✔

118

111,637✔

120

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

589,931✔

121

   if(y == 0) {

589,931✔

125

   const size_t x_words = x.sig_words();

589,931✔

126

   const size_t x_bits = x.bits();

589,931✔

128

   BigInt q = BigInt::with_capacity(x_words);

589,931✔

131

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

58,501,644✔

132

      const size_t b = x_bits - 1 - i;

57,911,713✔

133

      const bool x_b = x.get_bit(b);

57,911,713✔

135

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

57,911,713✔

137

      r <<= 1;

57,911,713✔

138

      r += x_b;

57,911,713✔

140

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

57,911,713✔

141

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

57,911,713✔

142

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

57,911,713✔

145

   if(x.is_negative()) {

589,931✔

146

      q.flip_sign();

19✔

147

      if(r != 0) {

19✔

148

         --q;

15✔

149

         r = y - r;

15✔

153

   r_out = r;

589,931✔

154

   q_out = q;

589,931✔

155

589,931✔

157

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

4,341✔

158

   BigInt q;

4,341✔

159

   word r;

4,341✔

160

   ct_divide_word(x, y, q, r);

4,341✔

161

   BOTAN_UNUSED(r);

4,341✔

162

   return q;

4,341✔

165

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

4,341✔

166

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

4,341✔

167

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

4,341✔

169

   const size_t x_bits = x.bits();

4,341✔

171

   word r = 0;

4,341✔

173

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

3,028,266✔

174

      const size_t b = x_bits - 1 - i;

3,023,925✔

175

      const bool x_b = x.get_bit(b);

3,023,925✔

177

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

3,023,925✔

179

      r <<= 1;

3,023,925✔

180

      r += x_b;

3,023,925✔

182

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

3,023,925✔

183

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

3,023,925✔

186

   return r;

4,341✔

189

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

5,629✔

190

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

11,258✔

194

   const size_t y_words = y.sig_words();

5,629✔

196

   const size_t x_bits = x.bits();

5,629✔

198

   BigInt r = BigInt::with_capacity(y_words);

5,629✔

199

   BigInt t = BigInt::with_capacity(y_words);

5,629✔

201

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

7,749,998✔

202

      const size_t b = x_bits - 1 - i;

7,744,369✔

203

      const bool x_b = x.get_bit(b);

7,744,369✔

205

      r <<= 1;

7,744,369✔

206

      r.conditionally_set_bit(0, x_b);

7,744,369✔

208

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

7,744,369✔

210

      r.ct_cond_swap(r_gte_y, t);

7,744,369✔

213

   if(x.is_negative()) {

5,629✔

214

      if(r.is_nonzero()) {

1,236✔

215

         r = y - r;

616✔

219

   return r;

5,629✔

220

5,629✔

227

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

345,556✔

228

   if(y_arg.is_zero()) {

345,629✔

232

   const size_t y_words = y_arg.sig_words();

345,556✔

234

   BOTAN_ASSERT_NOMSG(y_words > 0);

345,556✔

236

   BigInt y = y_arg;

345,556✔

238

   BigInt r = x;

345,556✔

239

   BigInt q = BigInt::zero();

345,556✔

240

   secure_vector<word> ws;

345,556✔

242

   r.set_sign(BigInt::Positive);

345,556✔

243

   y.set_sign(BigInt::Positive);

345,556✔

246

   const size_t shifts = y.top_bits_free();

345,556✔

248

   y <<= shifts;

345,556✔

249

   r <<= shifts;

345,556✔

252

   const size_t t = y_words - 1;

345,556✔

253

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

691,112✔

255

   BOTAN_ASSERT_NOMSG(n >= t);

345,556✔

257

   q.grow_to(n - t + 1);

345,556✔

259

   word* q_words = q.mutable_data();

345,556✔

261

   BigInt shifted_y = y << (WordInfo<word>::bits * (n - t));

345,556✔

264

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

345,556✔

266

   const word y_t0 = y.word_at(t);

345,556✔

267

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

345,556✔

268

   BOTAN_DEBUG_ASSERT((y_t0 >> (WordInfo<word>::bits - 1)) == 1);

345,556✔

270

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

1,754,426✔

271

      const word x_j0 = r.word_at(j);

1,408,870✔

272

      const word x_j1 = r.word_at(j - 1);

1,408,870✔

273

      const word x_j2 = r.word_at(j - 2);

1,408,870✔

275

      word qjt = bigint_divop_vartime(x_j0, x_j1, y_t0);

1,408,870✔

277

      qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(WordInfo<word>::max, qjt);

1,408,870✔

280

      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);

1,408,870✔

281

      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);

1,408,870✔

282

      BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);

1,408,870✔

284

      shifted_y >>= WordInfo<word>::bits;

1,408,870✔

288

      r -= qjt * shifted_y;

1,408,870✔

289

      qjt -= r.is_negative();

1,408,870✔

290

      r += static_cast<word>(r.is_negative()) * shifted_y;

1,408,870✔

292

      q_words[j - t - 1] = qjt;

1,408,870✔

295

   r >>= shifts;

345,556✔

297

   sign_fixup(x, y_arg, q, r);

345,556✔

299

   r_out = r;

345,556✔

300

   q_out = q;

345,556✔

301

691,112✔

randombit / botan / 13235046472

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/internal/bit_ops.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) {	352,220✔
22	q.cond_flip_sign(x.sign() != y.sign());	352,220✔
23
24	if(x.is_negative() && r.is_nonzero()) {	353,772✔
25	q -= 1;	1,548✔
26	r = y.abs() - r;	1,548✔
27	}
28	}	352,220✔
29
30	inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {	2,817,740✔
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;	2,817,740✔
37	y1 = word_madd2(q, y1, &y3);	2,817,740✔
38	y2 = word_madd2(q, y2, &y3);	2,817,740✔
39
40	const word x[3] = {x1, x2, x3};	2,817,740✔
41	const word y[3] = {y1, y2, y3};	2,817,740✔
42
43	return bigint_ct_is_lt(x, 3, y, 3).as_bool();	2,817,740✔
44	}
45
46	} // namespace
47
48	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	6,664✔
49	if(y.is_zero()) {	11,297✔
50	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
51	}
52
53	const size_t x_words = x.sig_words();	6,664✔
54	const size_t y_words = y.sig_words();	6,664✔
55
56	const size_t x_bits = x.bits();	6,664✔
57
58	BigInt q = BigInt::with_capacity(x_words);	6,664✔
59	BigInt r = BigInt::with_capacity(y_words);	6,664✔
60	BigInt t = BigInt::with_capacity(y_words); // a temporary	6,664✔
61
62	for(size_t i = 0; i != x_bits; ++i) {	6,076,623✔
63	const size_t b = x_bits - 1 - i;	6,069,959✔
64	const bool x_b = x.get_bit(b);	6,069,959✔
65
66	r <<= 1;	6,069,959✔
67	r.conditionally_set_bit(0, x_b);	6,069,959✔
68
69	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	6,069,959✔
70
71	q.conditionally_set_bit(b, r_gte_y);	6,069,959✔
72	r.ct_cond_swap(r_gte_y, t);	6,069,959✔
73	}
74
75	sign_fixup(x, y, q, r);	6,664✔
76	r_out = r;	6,664✔
77	q_out = q;	6,664✔
78	}	6,664✔
79
80	BigInt ct_divide_pow2k(size_t k, const BigInt& y) {	111,877✔
81	BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");	112,255✔
82	BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");	111,877✔
83	BOTAN_ARG_CHECK(k > 1, "Invalid k");	111,877✔
84
85	const size_t x_bits = k + 1;	111,877✔
86	const size_t y_bits = y.bits();	111,877✔
87
88	if(x_bits < y_bits) {	111,877✔
89	return BigInt::zero();	240✔
90	}
91
92	BOTAN_ASSERT_NOMSG(y_bits >= 1);	111,637✔
93	const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	111,637✔
94	const size_t y_words = y.sig_words();	111,637✔
95
96	BigInt q = BigInt::with_capacity(x_words);	111,637✔
97	BigInt r = BigInt::with_capacity(y_words + 1);	111,637✔
98	BigInt t = BigInt::with_capacity(y_words + 1); // a temporary	111,637✔
99
100	r.set_bit(y_bits - 1);	111,637✔
101	for(size_t i = y_bits - 1; i != x_bits; ++i) {	32,226,676✔
102	const size_t b = x_bits - 1 - i;	32,115,039✔
103
104	if(i >= y_bits) {	32,115,039✔
105	bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);	32,003,402✔
106	}
107
108	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	32,115,039✔
109
110	q.conditionally_set_bit(b, r_gte_y);	32,115,039✔
111
112	bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);	32,115,039✔
113	}
114
115	// No need for sign fixup
116
117	return q;	111,637✔
118	}	111,637✔
119
120	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	589,931✔
121	if(y == 0) {	589,931✔
122	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
123	}
124
125	const size_t x_words = x.sig_words();	589,931✔
126	const size_t x_bits = x.bits();	589,931✔
127
128	BigInt q = BigInt::with_capacity(x_words);	589,931✔
129	word r = 0;
130
131	for(size_t i = 0; i != x_bits; ++i) {	58,501,644✔
132	const size_t b = x_bits - 1 - i;	57,911,713✔
133	const bool x_b = x.get_bit(b);	57,911,713✔
134
135	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	57,911,713✔
136
137	r <<= 1;	57,911,713✔
138	r += x_b;	57,911,713✔
139
140	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	57,911,713✔
141	q.conditionally_set_bit(b, r_gte_y.as_bool());	57,911,713✔
142	r = r_gte_y.select(r - y, r);	57,911,713✔
143	}
144
145	if(x.is_negative()) {	589,931✔
146	q.flip_sign();	19✔
147	if(r != 0) {	19✔
148	--q;	15✔
149	r = y - r;	15✔
150	}
151	}
152
153	r_out = r;	589,931✔
154	q_out = q;	589,931✔
155	}	589,931✔
156
157	BigInt ct_divide_word(const BigInt& x, word y) {	4,341✔
158	BigInt q;	4,341✔
159	word r;	4,341✔
160	ct_divide_word(x, y, q, r);	4,341✔
161	BOTAN_UNUSED(r);	4,341✔
162	return q;	4,341✔
163	}	×
164
165	word ct_mod_word(const BigInt& x, word y) {	4,341✔
166	BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");	4,341✔
167	BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");	4,341✔
168
169	const size_t x_bits = x.bits();	4,341✔
170
171	word r = 0;	4,341✔
172
173	for(size_t i = 0; i != x_bits; ++i) {	3,028,266✔
174	const size_t b = x_bits - 1 - i;	3,023,925✔
175	const bool x_b = x.get_bit(b);	3,023,925✔
176
177	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	3,023,925✔
178
179	r <<= 1;	3,023,925✔
180	r += x_b;	3,023,925✔
181
182	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	3,023,925✔
183	r = r_gte_y.select(r - y, r);	3,023,925✔
184	}
185
186	return r;	4,341✔
187	}
188
189	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	5,629✔
190	if(y.is_negative() \|\| y.is_zero()) {	11,258✔
191	throw Invalid_Argument("ct_modulo requires y > 0");	×
192	}
193
194	const size_t y_words = y.sig_words();	5,629✔
195
196	const size_t x_bits = x.bits();	5,629✔
197
198	BigInt r = BigInt::with_capacity(y_words);	5,629✔
199	BigInt t = BigInt::with_capacity(y_words);	5,629✔
200
201	for(size_t i = 0; i != x_bits; ++i) {	7,749,998✔
202	const size_t b = x_bits - 1 - i;	7,744,369✔
203	const bool x_b = x.get_bit(b);	7,744,369✔
204
205	r <<= 1;	7,744,369✔
206	r.conditionally_set_bit(0, x_b);	7,744,369✔
207
208	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	7,744,369✔
209
210	r.ct_cond_swap(r_gte_y, t);	7,744,369✔
211	}
212
213	if(x.is_negative()) {	5,629✔
214	if(r.is_nonzero()) {	1,236✔
215	r = y - r;	616✔
216	}
217	}
218
219	return r;	5,629✔
220	}	5,629✔
221
222	/*
223	* Solve x = q * y + r
224	*
225	* See Handbook of Applied Cryptography section 14.2.5
226	*/
227	void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {	345,556✔
228	if(y_arg.is_zero()) {	345,629✔
229	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
230	}
231
232	const size_t y_words = y_arg.sig_words();	345,556✔
233
234	BOTAN_ASSERT_NOMSG(y_words > 0);	345,556✔
235
236	BigInt y = y_arg;	345,556✔
237
238	BigInt r = x;	345,556✔
239	BigInt q = BigInt::zero();	345,556✔
240	secure_vector<word> ws;	345,556✔
241
242	r.set_sign(BigInt::Positive);	345,556✔
243	y.set_sign(BigInt::Positive);	345,556✔
244
245	// Calculate shifts needed to normalize y with high bit set
246	const size_t shifts = y.top_bits_free();	345,556✔
247
248	y <<= shifts;	345,556✔
249	r <<= shifts;	345,556✔
250
251	// we know y has not changed size, since we only shifted up to set high bit
252	const size_t t = y_words - 1;	345,556✔
253	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	691,112✔
254
255	BOTAN_ASSERT_NOMSG(n >= t);	345,556✔
256
257	q.grow_to(n - t + 1);	345,556✔
258
259	word* q_words = q.mutable_data();	345,556✔
260
261	BigInt shifted_y = y << (WordInfo<word>::bits * (n - t));	345,556✔
262
263	// Set q_{n-t} to number of times r > shifted_y
264	q_words[n - t] = r.reduce_below(shifted_y, ws);	345,556✔
265
266	const word y_t0 = y.word_at(t);	345,556✔
267	const word y_t1 = y.word_at(t - 1);	345,556✔
268	BOTAN_DEBUG_ASSERT((y_t0 >> (WordInfo<word>::bits - 1)) == 1);	345,556✔
269
270	for(size_t j = n; j != t; --j) {	1,754,426✔
271	const word x_j0 = r.word_at(j);	1,408,870✔
272	const word x_j1 = r.word_at(j - 1);	1,408,870✔
273	const word x_j2 = r.word_at(j - 2);	1,408,870✔
274
275	word qjt = bigint_divop_vartime(x_j0, x_j1, y_t0);	1,408,870✔
276
277	qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(WordInfo<word>::max, qjt);	1,408,870✔
278
279	// Per HAC 14.23, this operation is required at most twice
280	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	1,408,870✔
281	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	1,408,870✔
282	BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);	1,408,870✔
283
284	shifted_y >>= WordInfo<word>::bits;	1,408,870✔
285	// Now shifted_y == y << (WordInfo<word>::bits * (j-t-1))
286
287	// TODO this sequence could be better
288	r -= qjt * shifted_y;	1,408,870✔
289	qjt -= r.is_negative();	1,408,870✔
290	r += static_cast<word>(r.is_negative()) * shifted_y;	1,408,870✔
291
292	q_words[j - t - 1] = qjt;	1,408,870✔
293	}
294
295	r >>= shifts;	345,556✔
296
297	sign_fixup(x, y_arg, q, r);	345,556✔
298
299	r_out = r;	345,556✔
300	q_out = q;	345,556✔
301	}	691,112✔
302
303	} // namespace Botan

randombit / botan / 13235046472

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