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

21

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

768,694✔

22

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

768,694✔

24

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

769,650✔

25

      q -= 1;

952✔

26

      r = y.abs() - r;

2,856✔

28

768,694✔

30

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

1,839,022✔

36

   word y3 = 0;

1,839,022✔

37

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

1,839,022✔

38

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

1,839,022✔

40

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

1,839,022✔

41

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

1,839,022✔

43

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

1,839,022✔

48

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

116,302✔

49

   if(y.is_zero())

116,792✔

52

   const size_t x_words = x.sig_words();

116,302✔

53

   const size_t y_words = y.sig_words();

116,302✔

55

   const size_t x_bits = x.bits();

116,302✔

57

   BigInt q = BigInt::with_capacity(x_words);

116,302✔

58

   BigInt r = BigInt::with_capacity(y_words);

116,302✔

59

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

116,302✔

61

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

137,381,063✔

62

      const size_t b = x_bits - 1 - i;

137,264,761✔

63

      const bool x_b = x.get_bit(b);

137,264,761✔

65

      r *= 2;

137,264,761✔

66

      r.conditionally_set_bit(0, x_b);

137,264,761✔

68

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

137,264,761✔

70

      q.conditionally_set_bit(b, r_gte_y);

137,264,761✔

71

      r.ct_cond_swap(r_gte_y, t);

137,264,761✔

74

   sign_fixup(x, y, q, r);

116,302✔

75

   r_out = r;

116,302✔

76

   q_out = q;

116,302✔

77

348,901✔

79

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

929,379✔

80

   if(y == 0)

929,379✔

83

   const size_t x_words = x.sig_words();

929,379✔

84

   const size_t x_bits = x.bits();

929,379✔

86

   BigInt q = BigInt::with_capacity(x_words);

929,379✔

89

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

147,783,137✔

90

      const size_t b = x_bits - 1 - i;

146,853,758✔

91

      const bool x_b = x.get_bit(b);

146,853,758✔

93

      const auto r_carry = CT::Mask<word>::expand(r >> (BOTAN_MP_WORD_BITS - 1));

146,853,758✔

95

      r *= 2;

146,853,758✔

96

      r += x_b;

146,853,758✔

98

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

146,853,758✔

99

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

146,853,758✔

100

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

146,853,758✔

103

   if(x.is_negative()) {

929,379✔

104

      q.flip_sign();

19✔

105

      if(r != 0) {

19✔

106

         --q;

15✔

107

         r = y - r;

15✔

111

   r_out = r;

929,379✔

112

   q_out = q;

929,379✔

113

929,379✔

115

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

5,613✔

116

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

11,226✔

119

   const size_t y_words = y.sig_words();

5,613✔

121

   const size_t x_bits = x.bits();

5,613✔

123

   BigInt r = BigInt::with_capacity(y_words);

5,613✔

124

   BigInt t = BigInt::with_capacity(y_words);

5,613✔

126

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

7,653,340✔

127

      const size_t b = x_bits - 1 - i;

7,647,727✔

128

      const bool x_b = x.get_bit(b);

7,647,727✔

130

      r *= 2;

7,647,727✔

131

      r.conditionally_set_bit(0, x_b);

7,647,727✔

133

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

7,647,727✔

135

      r.ct_cond_swap(r_gte_y, t);

7,647,727✔

138

   if(x.is_negative()) {

5,613✔

139

      if(r.is_nonzero()) {

1,178✔

140

         r = y - r;

1,174✔

144

   return r;

5,613✔

145

5,613✔

152

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

652,392✔

153

   if(y_arg.is_zero())

652,437✔

156

   const size_t y_words = y_arg.sig_words();

652,392✔

158

   BOTAN_ASSERT_NOMSG(y_words > 0);

652,392✔

160

   BigInt y = y_arg;

652,392✔

162

   BigInt r = x;

652,392✔

163

   BigInt q = BigInt::zero();

652,392✔

164

   secure_vector<word> ws;

652,392✔

166

   r.set_sign(BigInt::Positive);

652,392✔

167

   y.set_sign(BigInt::Positive);

652,392✔

170

   const size_t shifts = y.top_bits_free();

652,392✔

172

   y <<= shifts;

652,392✔

173

   r <<= shifts;

652,392✔

176

   const size_t t = y_words - 1;

652,392✔

177

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

1,304,784✔

179

   BOTAN_ASSERT_NOMSG(n >= t);

652,392✔

181

   q.grow_to(n - t + 1);

652,392✔

183

   word* q_words = q.mutable_data();

652,392✔

185

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

652,392✔

188

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

652,392✔

190

   const word y_t0 = y.word_at(t);

652,392✔

191

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

652,392✔

192

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

652,392✔

194

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

1,571,903✔

195

      const word x_j0 = r.word_at(j);

919,511✔

196

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

919,511✔

197

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

919,511✔

199

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

919,511✔

201

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

919,511✔

204

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

919,511✔

205

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

919,511✔

206

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

919,511✔

208

      shifted_y >>= BOTAN_MP_WORD_BITS;

919,511✔

212

      r -= qjt * shifted_y;

919,511✔

213

      qjt -= r.is_negative();

919,511✔

214

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

919,511✔

216

      q_words[j - t - 1] = qjt;

919,511✔

219

   r >>= shifts;

652,392✔

221

   sign_fixup(x, y_arg, q, r);

652,392✔

223

   r_out = r;

652,392✔

224

   q_out = q;

652,392✔

225

3,261,960✔

randombit / botan / 5111374265

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) {	768,694✔
22	q.cond_flip_sign(x.sign() != y.sign());	768,694✔
23
24	if(x.is_negative() && r.is_nonzero()) {	769,650✔
25	q -= 1;	952✔
26	r = y.abs() - r;	2,856✔
27	}
28	}	768,694✔
29
30	inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {	1,839,022✔
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,839,022✔
37	y1 = word_madd2(q, y1, &y3);	1,839,022✔
38	y2 = word_madd2(q, y2, &y3);	1,839,022✔
39
40	const word x[3] = {x1, x2, x3};	1,839,022✔
41	const word y[3] = {y1, y2, y3};	1,839,022✔
42
43	return bigint_ct_is_lt(x, 3, y, 3).is_set();	1,839,022✔
44	}
45
46	} // namespace
47
48	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	116,302✔
49	if(y.is_zero())	116,792✔
50	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
51
52	const size_t x_words = x.sig_words();	116,302✔
53	const size_t y_words = y.sig_words();	116,302✔
54
55	const size_t x_bits = x.bits();	116,302✔
56
57	BigInt q = BigInt::with_capacity(x_words);	116,302✔
58	BigInt r = BigInt::with_capacity(y_words);	116,302✔
59	BigInt t = BigInt::with_capacity(y_words); // a temporary	116,302✔
60
61	for(size_t i = 0; i != x_bits; ++i) {	137,381,063✔
62	const size_t b = x_bits - 1 - i;	137,264,761✔
63	const bool x_b = x.get_bit(b);	137,264,761✔
64
65	r *= 2;	137,264,761✔
66	r.conditionally_set_bit(0, x_b);	137,264,761✔
67
68	const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;	137,264,761✔
69
70	q.conditionally_set_bit(b, r_gte_y);	137,264,761✔
71	r.ct_cond_swap(r_gte_y, t);	137,264,761✔
72	}
73
74	sign_fixup(x, y, q, r);	116,302✔
75	r_out = r;	116,302✔
76	q_out = q;	116,302✔
77	}	348,901✔
78
79	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	929,379✔
80	if(y == 0)	929,379✔
81	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
82
83	const size_t x_words = x.sig_words();	929,379✔
84	const size_t x_bits = x.bits();	929,379✔
85
86	BigInt q = BigInt::with_capacity(x_words);	929,379✔
87	word r = 0;
88
89	for(size_t i = 0; i != x_bits; ++i) {	147,783,137✔
90	const size_t b = x_bits - 1 - i;	146,853,758✔
91	const bool x_b = x.get_bit(b);	146,853,758✔
92
93	const auto r_carry = CT::Mask<word>::expand(r >> (BOTAN_MP_WORD_BITS - 1));	146,853,758✔
94
95	r *= 2;	146,853,758✔
96	r += x_b;	146,853,758✔
97
98	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	146,853,758✔
99	q.conditionally_set_bit(b, r_gte_y.is_set());	146,853,758✔
100	r = r_gte_y.select(r - y, r);	146,853,758✔
101	}
102
103	if(x.is_negative()) {	929,379✔
104	q.flip_sign();	19✔
105	if(r != 0) {	19✔
106	--q;	15✔
107	r = y - r;	15✔
108	}
109	}
110
111	r_out = r;	929,379✔
112	q_out = q;	929,379✔
113	}	929,379✔
114
115	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	5,613✔
116	if(y.is_negative() \|\| y.is_zero())	11,226✔
117	throw Invalid_Argument("ct_modulo requires y > 0");	×
118
119	const size_t y_words = y.sig_words();	5,613✔
120
121	const size_t x_bits = x.bits();	5,613✔
122
123	BigInt r = BigInt::with_capacity(y_words);	5,613✔
124	BigInt t = BigInt::with_capacity(y_words);	5,613✔
125
126	for(size_t i = 0; i != x_bits; ++i) {	7,653,340✔
127	const size_t b = x_bits - 1 - i;	7,647,727✔
128	const bool x_b = x.get_bit(b);	7,647,727✔
129
130	r *= 2;	7,647,727✔
131	r.conditionally_set_bit(0, x_b);	7,647,727✔
132
133	const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;	7,647,727✔
134
135	r.ct_cond_swap(r_gte_y, t);	7,647,727✔
136	}
137
138	if(x.is_negative()) {	5,613✔
139	if(r.is_nonzero()) {	1,178✔
140	r = y - r;	1,174✔
141	}
142	}
143
144	return r;	5,613✔
145	}	5,613✔
146
147	/*
148	* Solve x = q * y + r
149	*
150	* See Handbook of Applied Cryptography section 14.2.5
151	*/
152	void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {	652,392✔
153	if(y_arg.is_zero())	652,437✔
154	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
155
156	const size_t y_words = y_arg.sig_words();	652,392✔
157
158	BOTAN_ASSERT_NOMSG(y_words > 0);	652,392✔
159
160	BigInt y = y_arg;	652,392✔
161
162	BigInt r = x;	652,392✔
163	BigInt q = BigInt::zero();	652,392✔
164	secure_vector<word> ws;	652,392✔
165
166	r.set_sign(BigInt::Positive);	652,392✔
167	y.set_sign(BigInt::Positive);	652,392✔
168
169	// Calculate shifts needed to normalize y with high bit set
170	const size_t shifts = y.top_bits_free();	652,392✔
171
172	y <<= shifts;	652,392✔
173	r <<= shifts;	652,392✔
174
175	// we know y has not changed size, since we only shifted up to set high bit
176	const size_t t = y_words - 1;	652,392✔
177	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	1,304,784✔
178
179	BOTAN_ASSERT_NOMSG(n >= t);	652,392✔
180
181	q.grow_to(n - t + 1);	652,392✔
182
183	word* q_words = q.mutable_data();	652,392✔
184
185	BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n - t));	652,392✔
186
187	// Set q_{n-t} to number of times r > shifted_y
188	q_words[n - t] = r.reduce_below(shifted_y, ws);	652,392✔
189
190	const word y_t0 = y.word_at(t);	652,392✔
191	const word y_t1 = y.word_at(t - 1);	652,392✔
192	BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS - 1)) == 1);	652,392✔
193
194	for(size_t j = n; j != t; --j) {	1,571,903✔
195	const word x_j0 = r.word_at(j);	919,511✔
196	const word x_j1 = r.word_at(j - 1);	919,511✔
197	const word x_j2 = r.word_at(j - 2);	919,511✔
198
199	word qjt = bigint_divop(x_j0, x_j1, y_t0);	919,511✔
200
201	qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt);	919,511✔
202
203	// Per HAC 14.23, this operation is required at most twice
204	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	919,511✔
205	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	919,511✔
206	BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);	919,511✔
207
208	shifted_y >>= BOTAN_MP_WORD_BITS;	919,511✔
209	// Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))
210
211	// TODO this sequence could be better
212	r -= qjt * shifted_y;	919,511✔
213	qjt -= r.is_negative();	919,511✔
214	r += static_cast<word>(r.is_negative()) * shifted_y;	919,511✔
215
216	q_words[j - t - 1] = qjt;	919,511✔
217	}
218
219	r >>= shifts;	652,392✔
220
221	sign_fixup(x, y_arg, q, r);	652,392✔
222
223	r_out = r;	652,392✔
224	q_out = q;	652,392✔
225	}	3,261,960✔
226
227	} // namespace Botan

randombit / botan / 5111374265

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