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

21

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

291,282✔

22

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

291,282✔

24

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

292,808✔

25

      q -= 1;

1,522✔

26

      r = y.abs() - r;

4,566✔

28

291,282✔

30

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

2,553,950✔

36

   word y3 = 0;

2,553,950✔

37

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

2,553,950✔

38

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

2,553,950✔

40

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

2,553,950✔

41

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

2,553,950✔

43

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

2,553,950✔

48

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

6,658✔

49

   if(y.is_zero()) {

11,280✔

53

   const size_t x_words = x.sig_words();

6,658✔

54

   const size_t y_words = y.sig_words();

6,658✔

56

   const size_t x_bits = x.bits();

6,658✔

58

   BigInt q = BigInt::with_capacity(x_words);

6,658✔

59

   BigInt r = BigInt::with_capacity(y_words);

6,658✔

60

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

6,658✔

62

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

6,045,944✔

63

      const size_t b = x_bits - 1 - i;

6,039,286✔

64

      const bool x_b = x.get_bit(b);

6,039,286✔

66

      r <<= 1;

6,039,286✔

67

      r.conditionally_set_bit(0, x_b);

6,039,286✔

69

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

6,039,286✔

71

      q.conditionally_set_bit(b, r_gte_y);

6,039,286✔

72

      r.ct_cond_swap(r_gte_y, t);

6,039,286✔

75

   sign_fixup(x, y, q, r);

6,658✔

76

   r_out = r;

6,658✔

77

   q_out = q;

6,658✔

78

19,969✔

80

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

45,372✔

81

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

45,372✔

82

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

45,372✔

83

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

45,372✔

85

   const size_t x_bits = k + 1;

45,372✔

86

   const size_t y_bits = y.bits();

45,372✔

87

   BOTAN_ASSERT_NOMSG(y_bits >= 1);

45,372✔

88

   const size_t x_words = (x_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS;

45,372✔

89

   const size_t y_words = y.sig_words();

45,372✔

91

   BigInt q = BigInt::with_capacity(x_words);

45,372✔

92

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

45,372✔

93

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

45,372✔

95

   r.set_bit(y_bits - 1);

45,372✔

96

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

26,632,154✔

97

      const size_t b = x_bits - 1 - i;

26,586,782✔

99

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

26,586,782✔

101

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

26,586,782✔

103

      q.conditionally_set_bit(b, r_gte_y);

26,586,782✔

105

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

26,586,782✔

110

   return q;

45,372✔

111

90,744✔

113

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

593,687✔

114

   if(y == 0) {

593,687✔

118

   const size_t x_words = x.sig_words();

593,687✔

119

   const size_t x_bits = x.bits();

593,687✔

121

   BigInt q = BigInt::with_capacity(x_words);

593,687✔

124

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

59,199,068✔

125

      const size_t b = x_bits - 1 - i;

58,605,381✔

126

      const bool x_b = x.get_bit(b);

58,605,381✔

128

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

58,605,381✔

130

      r <<= 1;

58,605,381✔

131

      r += x_b;

58,605,381✔

133

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

58,605,381✔

134

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

58,605,381✔

135

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

58,605,381✔

138

   if(x.is_negative()) {

593,687✔

139

      q.flip_sign();

19✔

140

      if(r != 0) {

19✔

141

         --q;

15✔

142

         r = y - r;

15✔

146

   r_out = r;

593,687✔

147

   q_out = q;

593,687✔

148

593,687✔

150

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

4,338✔

151

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

4,338✔

152

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

4,338✔

154

   const size_t x_bits = x.bits();

4,338✔

156

   word r = 0;

4,338✔

158

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

3,020,528✔

159

      const size_t b = x_bits - 1 - i;

3,016,190✔

160

      const bool x_b = x.get_bit(b);

3,016,190✔

162

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

3,016,190✔

164

      r <<= 1;

3,016,190✔

165

      r += x_b;

3,016,190✔

167

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

3,016,190✔

168

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

3,016,190✔

171

   return r;

4,338✔

174

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

5,578✔

175

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

11,156✔

179

   const size_t y_words = y.sig_words();

5,578✔

181

   const size_t x_bits = x.bits();

5,578✔

183

   BigInt r = BigInt::with_capacity(y_words);

5,578✔

184

   BigInt t = BigInt::with_capacity(y_words);

5,578✔

186

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

7,640,888✔

187

      const size_t b = x_bits - 1 - i;

7,635,310✔

188

      const bool x_b = x.get_bit(b);

7,635,310✔

190

      r <<= 1;

7,635,310✔

191

      r.conditionally_set_bit(0, x_b);

7,635,310✔

193

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

7,635,310✔

195

      r.ct_cond_swap(r_gte_y, t);

7,635,310✔

198

   if(x.is_negative()) {

5,578✔

199

      if(r.is_nonzero()) {

1,188✔

200

         r = y - r;

1,184✔

204

   return r;

5,578✔

205

5,578✔

212

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

284,624✔

213

   if(y_arg.is_zero()) {

284,702✔

217

   const size_t y_words = y_arg.sig_words();

284,624✔

219

   BOTAN_ASSERT_NOMSG(y_words > 0);

284,624✔

221

   BigInt y = y_arg;

284,624✔

223

   BigInt r = x;

284,624✔

224

   BigInt q = BigInt::zero();

284,624✔

225

   secure_vector<word> ws;

284,624✔

227

   r.set_sign(BigInt::Positive);

284,624✔

228

   y.set_sign(BigInt::Positive);

284,624✔

231

   const size_t shifts = y.top_bits_free();

284,624✔

233

   y <<= shifts;

284,624✔

234

   r <<= shifts;

284,624✔

237

   const size_t t = y_words - 1;

284,624✔

238

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

569,248✔

240

   BOTAN_ASSERT_NOMSG(n >= t);

284,624✔

242

   q.grow_to(n - t + 1);

284,624✔

244

   word* q_words = q.mutable_data();

284,624✔

246

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

284,624✔

249

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

284,624✔

251

   const word y_t0 = y.word_at(t);

284,624✔

252

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

284,624✔

253

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

284,624✔

255

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

1,561,599✔

256

      const word x_j0 = r.word_at(j);

1,276,975✔

257

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

1,276,975✔

258

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

1,276,975✔

260

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

1,276,975✔

262

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

1,276,975✔

265

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

1,276,975✔

266

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

1,276,975✔

267

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

1,276,975✔

269

      shifted_y >>= BOTAN_MP_WORD_BITS;

1,276,975✔

273

      r -= qjt * shifted_y;

1,276,975✔

274

      qjt -= r.is_negative();

1,276,975✔

275

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

1,276,975✔

277

      q_words[j - t - 1] = qjt;

1,276,975✔

280

   r >>= shifts;

284,624✔

282

   sign_fixup(x, y_arg, q, r);

284,624✔

284

   r_out = r;

284,624✔

285

   q_out = q;

284,624✔

286

1,423,120✔

randombit / botan / 12976375427

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

randombit / botan / 12976375427

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