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

21

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

394,524✔

22

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

394,524✔

24

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

396,187✔

25

      q -= 1;

1,659✔

26

      r = y.abs() - r;

4,977✔

28

394,524✔

30

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

1,111,690✔

36

   word y3 = 0;

1,111,690✔

37

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

1,111,690✔

38

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

1,111,690✔

40

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

1,111,690✔

41

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

1,111,690✔

43

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

1,111,690✔

48

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

137,395✔

49

   if(y.is_zero()) {

142,012✔

53

   const size_t x_words = x.sig_words();

137,395✔

54

   const size_t y_words = y.sig_words();

137,395✔

56

   const size_t x_bits = x.bits();

137,395✔

58

   BigInt q = BigInt::with_capacity(x_words);

137,395✔

59

   BigInt r = BigInt::with_capacity(y_words);

137,395✔

60

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

137,395✔

62

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

177,081,527✔

63

      const size_t b = x_bits - 1 - i;

176,944,132✔

64

      const bool x_b = x.get_bit(b);

176,944,132✔

66

      r *= 2;

176,944,132✔

67

      r.conditionally_set_bit(0, x_b);

176,944,132✔

69

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

176,944,132✔

71

      q.conditionally_set_bit(b, r_gte_y);

176,944,132✔

72

      r.ct_cond_swap(r_gte_y, t);

176,944,132✔

75

   sign_fixup(x, y, q, r);

137,395✔

76

   r_out = r;

137,395✔

77

   q_out = q;

137,395✔

78

412,180✔

80

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

542,474✔

81

   if(y == 0) {

542,474✔

85

   const size_t x_words = x.sig_words();

542,474✔

86

   const size_t x_bits = x.bits();

542,474✔

88

   BigInt q = BigInt::with_capacity(x_words);

542,474✔

91

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

52,554,561✔

92

      const size_t b = x_bits - 1 - i;

52,012,087✔

93

      const bool x_b = x.get_bit(b);

52,012,087✔

95

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

52,012,087✔

97

      r *= 2;

52,012,087✔

98

      r += x_b;

52,012,087✔

100

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

52,012,087✔

101

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

52,012,087✔

102

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

52,012,087✔

105

   if(x.is_negative()) {

542,474✔

106

      q.flip_sign();

19✔

107

      if(r != 0) {

19✔

108

         --q;

15✔

109

         r = y - r;

15✔

113

   r_out = r;

542,474✔

114

   q_out = q;

542,474✔

115

542,474✔

117

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

4,333✔

118

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

4,333✔

119

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

4,333✔

121

   const size_t x_bits = x.bits();

4,333✔

123

   word r = 0;

4,333✔

125

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

3,023,847✔

126

      const size_t b = x_bits - 1 - i;

3,019,514✔

127

      const bool x_b = x.get_bit(b);

3,019,514✔

129

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

3,019,514✔

131

      r *= 2;

3,019,514✔

132

      r += x_b;

3,019,514✔

134

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

3,019,514✔

135

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

3,019,514✔

138

   return r;

4,333✔

141

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

4,943✔

142

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

9,886✔

146

   const size_t y_words = y.sig_words();

4,943✔

148

   const size_t x_bits = x.bits();

4,943✔

150

   BigInt r = BigInt::with_capacity(y_words);

4,943✔

151

   BigInt t = BigInt::with_capacity(y_words);

4,943✔

153

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

6,985,402✔

154

      const size_t b = x_bits - 1 - i;

6,980,459✔

155

      const bool x_b = x.get_bit(b);

6,980,459✔

157

      r *= 2;

6,980,459✔

158

      r.conditionally_set_bit(0, x_b);

6,980,459✔

160

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

6,980,459✔

162

      r.ct_cond_swap(r_gte_y, t);

6,980,459✔

165

   if(x.is_negative()) {

4,943✔

166

      if(r.is_nonzero()) {

1,268✔

167

         r = y - r;

1,264✔

171

   return r;

4,943✔

172

4,943✔

179

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

257,129✔

180

   if(y_arg.is_zero()) {

257,233✔

184

   const size_t y_words = y_arg.sig_words();

257,129✔

186

   BOTAN_ASSERT_NOMSG(y_words > 0);

257,129✔

188

   BigInt y = y_arg;

257,129✔

190

   BigInt r = x;

257,129✔

191

   BigInt q = BigInt::zero();

257,129✔

192

   secure_vector<word> ws;

257,129✔

194

   r.set_sign(BigInt::Positive);

257,129✔

195

   y.set_sign(BigInt::Positive);

257,129✔

198

   const size_t shifts = y.top_bits_free();

257,129✔

200

   y <<= shifts;

257,129✔

201

   r <<= shifts;

257,129✔

204

   const size_t t = y_words - 1;

257,129✔

205

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

514,258✔

207

   BOTAN_ASSERT_NOMSG(n >= t);

257,129✔

209

   q.grow_to(n - t + 1);

257,129✔

211

   word* q_words = q.mutable_data();

257,129✔

213

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

257,129✔

216

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

257,129✔

218

   const word y_t0 = y.word_at(t);

257,129✔

219

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

257,129✔

220

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

257,129✔

222

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

812,974✔

223

      const word x_j0 = r.word_at(j);

555,845✔

224

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

555,845✔

225

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

555,845✔

227

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

555,845✔

229

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

555,845✔

232

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

555,845✔

233

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

555,845✔

234

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

555,845✔

236

      shifted_y >>= BOTAN_MP_WORD_BITS;

555,845✔

240

      r -= qjt * shifted_y;

555,845✔

241

      qjt -= r.is_negative();

555,845✔

242

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

555,845✔

244

      q_words[j - t - 1] = qjt;

555,845✔

247

   r >>= shifts;

257,129✔

249

   sign_fixup(x, y_arg, q, r);

257,129✔

251

   r_out = r;

257,129✔

252

   q_out = q;

257,129✔

253

1,285,645✔

randombit / botan / 12869303872

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) {	394,524✔
22	q.cond_flip_sign(x.sign() != y.sign());	394,524✔
23
24	if(x.is_negative() && r.is_nonzero()) {	396,187✔
25	q -= 1;	1,659✔
26	r = y.abs() - r;	4,977✔
27	}
28	}	394,524✔
29
30	inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {	1,111,690✔
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,111,690✔
37	y1 = word_madd2(q, y1, &y3);	1,111,690✔
38	y2 = word_madd2(q, y2, &y3);	1,111,690✔
39
40	const word x[3] = {x1, x2, x3};	1,111,690✔
41	const word y[3] = {y1, y2, y3};	1,111,690✔
42
43	return bigint_ct_is_lt(x, 3, y, 3).as_bool();	1,111,690✔
44	}
45
46	} // namespace
47
48	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	137,395✔
49	if(y.is_zero()) {	142,012✔
50	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
51	}
52
53	const size_t x_words = x.sig_words();	137,395✔
54	const size_t y_words = y.sig_words();	137,395✔
55
56	const size_t x_bits = x.bits();	137,395✔
57
58	BigInt q = BigInt::with_capacity(x_words);	137,395✔
59	BigInt r = BigInt::with_capacity(y_words);	137,395✔
60	BigInt t = BigInt::with_capacity(y_words); // a temporary	137,395✔
61
62	for(size_t i = 0; i != x_bits; ++i) {	177,081,527✔
63	const size_t b = x_bits - 1 - i;	176,944,132✔
64	const bool x_b = x.get_bit(b);	176,944,132✔
65
66	r *= 2;	176,944,132✔
67	r.conditionally_set_bit(0, x_b);	176,944,132✔
68
69	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	176,944,132✔
70
71	q.conditionally_set_bit(b, r_gte_y);	176,944,132✔
72	r.ct_cond_swap(r_gte_y, t);	176,944,132✔
73	}
74
75	sign_fixup(x, y, q, r);	137,395✔
76	r_out = r;	137,395✔
77	q_out = q;	137,395✔
78	}	412,180✔
79
80	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	542,474✔
81	if(y == 0) {	542,474✔
82	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
83	}
84
85	const size_t x_words = x.sig_words();	542,474✔
86	const size_t x_bits = x.bits();	542,474✔
87
88	BigInt q = BigInt::with_capacity(x_words);	542,474✔
89	word r = 0;
90
91	for(size_t i = 0; i != x_bits; ++i) {	52,554,561✔
92	const size_t b = x_bits - 1 - i;	52,012,087✔
93	const bool x_b = x.get_bit(b);	52,012,087✔
94
95	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	52,012,087✔
96
97	r *= 2;	52,012,087✔
98	r += x_b;	52,012,087✔
99
100	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	52,012,087✔
101	q.conditionally_set_bit(b, r_gte_y.as_bool());	52,012,087✔
102	r = r_gte_y.select(r - y, r);	52,012,087✔
103	}
104
105	if(x.is_negative()) {	542,474✔
106	q.flip_sign();	19✔
107	if(r != 0) {	19✔
108	--q;	15✔
109	r = y - r;	15✔
110	}
111	}
112
113	r_out = r;	542,474✔
114	q_out = q;	542,474✔
115	}	542,474✔
116
117	word ct_mod_word(const BigInt& x, word y) {	4,333✔
118	BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");	4,333✔
119	BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");	4,333✔
120
121	const size_t x_bits = x.bits();	4,333✔
122
123	word r = 0;	4,333✔
124
125	for(size_t i = 0; i != x_bits; ++i) {	3,023,847✔
126	const size_t b = x_bits - 1 - i;	3,019,514✔
127	const bool x_b = x.get_bit(b);	3,019,514✔
128
129	const auto r_carry = CT::Mask<word>::expand_top_bit(r);	3,019,514✔
130
131	r *= 2;	3,019,514✔
132	r += x_b;	3,019,514✔
133
134	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	3,019,514✔
135	r = r_gte_y.select(r - y, r);	3,019,514✔
136	}
137
138	return r;	4,333✔
139	}
140
141	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	4,943✔
142	if(y.is_negative() \|\| y.is_zero()) {	9,886✔
143	throw Invalid_Argument("ct_modulo requires y > 0");	×
144	}
145
146	const size_t y_words = y.sig_words();	4,943✔
147
148	const size_t x_bits = x.bits();	4,943✔
149
150	BigInt r = BigInt::with_capacity(y_words);	4,943✔
151	BigInt t = BigInt::with_capacity(y_words);	4,943✔
152
153	for(size_t i = 0; i != x_bits; ++i) {	6,985,402✔
154	const size_t b = x_bits - 1 - i;	6,980,459✔
155	const bool x_b = x.get_bit(b);	6,980,459✔
156
157	r *= 2;	6,980,459✔
158	r.conditionally_set_bit(0, x_b);	6,980,459✔
159
160	const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;	6,980,459✔
161
162	r.ct_cond_swap(r_gte_y, t);	6,980,459✔
163	}
164
165	if(x.is_negative()) {	4,943✔
166	if(r.is_nonzero()) {	1,268✔
167	r = y - r;	1,264✔
168	}
169	}
170
171	return r;	4,943✔
172	}	4,943✔
173
174	/*
175	* Solve x = q * y + r
176	*
177	* See Handbook of Applied Cryptography section 14.2.5
178	*/
179	void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {	257,129✔
180	if(y_arg.is_zero()) {	257,233✔
181	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
182	}
183
184	const size_t y_words = y_arg.sig_words();	257,129✔
185
186	BOTAN_ASSERT_NOMSG(y_words > 0);	257,129✔
187
188	BigInt y = y_arg;	257,129✔
189
190	BigInt r = x;	257,129✔
191	BigInt q = BigInt::zero();	257,129✔
192	secure_vector<word> ws;	257,129✔
193
194	r.set_sign(BigInt::Positive);	257,129✔
195	y.set_sign(BigInt::Positive);	257,129✔
196
197	// Calculate shifts needed to normalize y with high bit set
198	const size_t shifts = y.top_bits_free();	257,129✔
199
200	y <<= shifts;	257,129✔
201	r <<= shifts;	257,129✔
202
203	// we know y has not changed size, since we only shifted up to set high bit
204	const size_t t = y_words - 1;	257,129✔
205	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	514,258✔
206
207	BOTAN_ASSERT_NOMSG(n >= t);	257,129✔
208
209	q.grow_to(n - t + 1);	257,129✔
210
211	word* q_words = q.mutable_data();	257,129✔
212
213	BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n - t));	257,129✔
214
215	// Set q_{n-t} to number of times r > shifted_y
216	q_words[n - t] = r.reduce_below(shifted_y, ws);	257,129✔
217
218	const word y_t0 = y.word_at(t);	257,129✔
219	const word y_t1 = y.word_at(t - 1);	257,129✔
220	BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS - 1)) == 1);	257,129✔
221
222	for(size_t j = n; j != t; --j) {	812,974✔
223	const word x_j0 = r.word_at(j);	555,845✔
224	const word x_j1 = r.word_at(j - 1);	555,845✔
225	const word x_j2 = r.word_at(j - 2);	555,845✔
226
227	word qjt = bigint_divop_vartime(x_j0, x_j1, y_t0);	555,845✔
228
229	qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(WordInfo<word>::max, qjt);	555,845✔
230
231	// Per HAC 14.23, this operation is required at most twice
232	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	555,845✔
233	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	555,845✔
234	BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);	555,845✔
235
236	shifted_y >>= BOTAN_MP_WORD_BITS;	555,845✔
237	// Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))
238
239	// TODO this sequence could be better
240	r -= qjt * shifted_y;	555,845✔
241	qjt -= r.is_negative();	555,845✔
242	r += static_cast<word>(r.is_negative()) * shifted_y;	555,845✔
243
244	q_words[j - t - 1] = qjt;	555,845✔
245	}
246
247	r >>= shifts;	257,129✔
248
249	sign_fixup(x, y_arg, q, r);	257,129✔
250
251	r_out = r;	257,129✔
252	q_out = q;	257,129✔
253	}	1,285,645✔
254
255	} // namespace Botan

randombit / botan / 12869303872

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