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

21

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

200,107✔

22

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

200,107✔

24

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

201,707✔

25

      q -= 1;

1,596✔

26

      r = y.abs() - r;

1,596✔

28

200,107✔

30

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

1,571,391✔

36

   word y3 = 0;

1,571,391✔

37

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

1,571,391✔

38

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

1,571,391✔

40

   if(x3 != y3) {

1,571,391✔

41

      return (y3 > x3);

588,225✔

43

   if(x2 != y2) {

983,166✔

44

      return (y2 > x2);

968,416✔

46

   return (y1 > x1);

14,750✔

51

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

6,662✔

52

   if(y.is_zero()) {

11,290✔

56

   const size_t x_words = x.sig_words();

6,662✔

57

   const size_t y_words = y.sig_words();

6,662✔

59

   const size_t x_bits = x.bits();

6,662✔

61

   BigInt q = BigInt::with_capacity(x_words);

6,662✔

62

   BigInt r = BigInt::with_capacity(y_words);

6,662✔

63

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

6,662✔

65

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

6,084,280✔

66

      const size_t b = x_bits - 1 - i;

6,077,618✔

67

      const bool x_b = x.get_bit(b);

6,077,618✔

69

      r <<= 1;

6,077,618✔

70

      r.conditionally_set_bit(0, x_b);

6,077,618✔

72

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

6,077,618✔

74

      q.conditionally_set_bit(b, r_gte_y);

6,077,618✔

75

      r.ct_cond_swap(r_gte_y, t);

6,077,618✔

78

   sign_fixup(x, y, q, r);

6,662✔

79

   r_out = r;

6,662✔

80

   q_out = q;

6,662✔

81

6,662✔

83

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

114,405✔

84

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

114,783✔

85

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

114,405✔

86

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

114,405✔

88

   const size_t x_bits = k + 1;

114,405✔

89

   const size_t y_bits = y.bits();

114,405✔

91

   if(x_bits < y_bits) {

114,405✔

92

      return BigInt::zero();

262✔

95

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

114,143✔

96

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

114,143✔

97

   const size_t y_words = y.sig_words();

114,143✔

99

   BigInt q = BigInt::with_capacity(x_words);

114,143✔

100

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

114,143✔

101

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

114,143✔

103

   r.set_bit(y_bits - 1);

114,143✔

104

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

33,659,610✔

105

      const size_t b = x_bits - 1 - i;

33,545,467✔

107

      if(i >= y_bits) {

33,545,467✔

108

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

33,431,324✔

111

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

33,545,467✔

113

      q.conditionally_set_bit(b, r_gte_y);

33,545,467✔

115

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

33,545,467✔

120

   return q;

114,143✔

121

114,143✔

123

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

388,085✔

124

   if(y == 0) {

388,085✔

128

   const size_t x_words = x.sig_words();

388,085✔

129

   const size_t x_bits = x.bits();

388,085✔

131

   BigInt q = BigInt::with_capacity(x_words);

388,085✔

134

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

30,954,847✔

135

      const size_t b = x_bits - 1 - i;

30,566,762✔

136

      const bool x_b = x.get_bit(b);

30,566,762✔

138

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

30,566,762✔

140

      r <<= 1;

30,566,762✔

141

      r += x_b;

30,566,762✔

143

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

30,566,762✔

144

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

30,566,762✔

145

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

30,566,762✔

148

   if(x.is_negative()) {

388,085✔

149

      q.flip_sign();

19✔

150

      if(r != 0) {

19✔

151

         --q;

15✔

152

         r = y - r;

15✔

156

   r_out = r;

388,085✔

157

   q_out = q;

388,085✔

158

388,085✔

160

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

4,336✔

161

   BigInt q;

4,336✔

162

   word r;

4,336✔

163

   ct_divide_word(x, y, q, r);

4,336✔

164

   BOTAN_UNUSED(r);

4,336✔

165

   return q;

4,336✔

168

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

4,336✔

169

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

4,336✔

170

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

4,336✔

172

   const size_t x_bits = x.bits();

4,336✔

174

   word r = 0;

4,336✔

176

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

3,034,741✔

177

      const size_t b = x_bits - 1 - i;

3,030,405✔

178

      const bool x_b = x.get_bit(b);

3,030,405✔

180

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

3,030,405✔

182

      r <<= 1;

3,030,405✔

183

      r += x_b;

3,030,405✔

185

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

3,030,405✔

186

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

3,030,405✔

189

   return r;

4,336✔

192

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

5,424✔

193

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

10,848✔

197

   const size_t y_words = y.sig_words();

5,424✔

199

   const size_t x_bits = x.bits();

5,424✔

201

   BigInt r = BigInt::with_capacity(y_words);

5,424✔

202

   BigInt t = BigInt::with_capacity(y_words);

5,424✔

204

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

7,516,599✔

205

      const size_t b = x_bits - 1 - i;

7,511,175✔

206

      const bool x_b = x.get_bit(b);

7,511,175✔

208

      r <<= 1;

7,511,175✔

209

      r.conditionally_set_bit(0, x_b);

7,511,175✔

211

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

7,511,175✔

213

      r.ct_cond_swap(r_gte_y, t);

7,511,175✔

216

   if(x.is_negative()) {

5,424✔

217

      if(r.is_nonzero()) {

1,224✔

218

         r = y - r;

610✔

222

   return r;

5,424✔

223

5,424✔

230

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

193,445✔

231

   if(y_arg.is_zero()) {

193,521✔

235

   const size_t y_words = y_arg.sig_words();

193,445✔

237

   BOTAN_ASSERT_NOMSG(y_words > 0);

193,445✔

239

   BigInt y = y_arg;

193,445✔

241

   BigInt r = x;

193,445✔

242

   BigInt q = BigInt::zero();

193,445✔

243

   secure_vector<word> ws;

193,445✔

245

   r.set_sign(BigInt::Positive);

193,445✔

246

   y.set_sign(BigInt::Positive);

193,445✔

249

   const size_t shifts = y.top_bits_free();

193,445✔

251

   if(shifts > 0) {

193,445✔

252

      y <<= shifts;

162,738✔

253

      r <<= shifts;

162,738✔

257

   const size_t t = y_words - 1;

193,445✔

258

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

377,207✔

260

   BOTAN_ASSERT_NOMSG(n >= t);

193,445✔

262

   q.grow_to(n - t + 1);

193,445✔

264

   word* q_words = q.mutable_data();

193,445✔

266

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

193,445✔

269

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

193,445✔

271

   const word y_t0 = y.word_at(t);

193,445✔

272

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

193,445✔

273

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

193,445✔

275

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

1,420,326✔

276

      const word x_j0 = r.word_at(j);

1,226,881✔

277

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

1,226,881✔

278

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

1,226,881✔

280

      word qjt = (x_j0 == y_t0) ? WordInfo<word>::max : bigint_divop_vartime(x_j0, x_j1, y_t0);

1,226,881✔

283

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

1,584,654✔

284

         if(division_check_vartime(qjt, y_t0, y_t1, x_j0, x_j1, x_j2)) {

3,142,782✔

285

            qjt--;

357,773✔

291

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

1,226,881✔

295

      r -= qjt * shifted_y;

1,226,881✔

296

      if(r.is_negative()) {

1,226,881✔

297

         qjt--;

608✔

298

         r += shifted_y;

608✔

302

      q_words[j - t - 1] = qjt;

1,226,881✔

305

   if(shifts > 0) {

193,445✔

306

      r >>= shifts;

162,738✔

309

   sign_fixup(x, y_arg, q, r);

193,445✔

311

   r_out = r;

193,445✔

312

   q_out = q;

193,445✔

313

386,890✔

randombit / botan / 14138547150

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

randombit / botan / 14138547150

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