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

21

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

773,244✔

22

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

773,244✔

24

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

774,386✔

25

      q -= 1;

1,138✔

26

      r = y.abs() - r;

3,414✔

28

773,244✔

30

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

1,842,104✔

36

   word y3 = 0;

1,842,104✔

37

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

1,842,104✔

38

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

1,842,104✔

40

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

1,842,104✔

41

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

1,842,104✔

43

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

1,842,104✔

48

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

119,827✔

49

   if(y.is_zero())

120,317✔

52

   const size_t x_words = x.sig_words();

119,827✔

53

   const size_t y_words = y.sig_words();

119,827✔

55

   const size_t x_bits = x.bits();

119,827✔

57

   BigInt q = BigInt::with_capacity(x_words);

119,827✔

58

   BigInt r = BigInt::with_capacity(y_words);

119,827✔

59

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

119,827✔

61

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

144,710,549✔

62

      const size_t b = x_bits - 1 - i;

144,590,722✔

63

      const bool x_b = x.get_bit(b);

144,590,722✔

65

      r *= 2;

144,590,722✔

66

      r.conditionally_set_bit(0, x_b);

144,590,722✔

68

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

144,590,722✔

70

      q.conditionally_set_bit(b, r_gte_y);

144,590,722✔

71

      r.ct_cond_swap(r_gte_y, t);

144,590,722✔

74

   sign_fixup(x, y, q, r);

119,827✔

75

   r_out = r;

119,827✔

76

   q_out = q;

119,827✔

77

359,476✔

79

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

931,076✔

80

   if(y == 0)

931,076✔

83

   const size_t x_words = x.sig_words();

931,076✔

84

   const size_t x_bits = x.bits();

931,076✔

86

   BigInt q = BigInt::with_capacity(x_words);

931,076✔

89

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

148,194,422✔

90

      const size_t b = x_bits - 1 - i;

147,263,346✔

91

      const bool x_b = x.get_bit(b);

147,263,346✔

93

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

147,263,346✔

95

      r *= 2;

147,263,346✔

96

      r += x_b;

147,263,346✔

98

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

147,263,346✔

99

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

147,263,346✔

100

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

147,263,346✔

103

   if(x.is_negative()) {

931,076✔

104

      q.flip_sign();

19✔

105

      if(r != 0) {

19✔

106

         --q;

15✔

107

         r = y - r;

15✔

111

   r_out = r;

931,076✔

112

   q_out = q;

931,076✔

113

931,076✔

115

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

4,865✔

116

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

9,730✔

119

   const size_t y_words = y.sig_words();

4,865✔

121

   const size_t x_bits = x.bits();

4,865✔

123

   BigInt r = BigInt::with_capacity(y_words);

4,865✔

124

   BigInt t = BigInt::with_capacity(y_words);

4,865✔

126

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

6,892,493✔

127

      const size_t b = x_bits - 1 - i;

6,887,628✔

128

      const bool x_b = x.get_bit(b);

6,887,628✔

130

      r *= 2;

6,887,628✔

131

      r.conditionally_set_bit(0, x_b);

6,887,628✔

133

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

6,887,628✔

135

      r.ct_cond_swap(r_gte_y, t);

6,887,628✔

138

   if(x.is_negative()) {

4,865✔

139

      if(r.is_nonzero()) {

1,224✔

140

         r = y - r;

1,220✔

144

   return r;

4,865✔

145

4,865✔

152

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

653,417✔

153

   if(y_arg.is_zero())

653,464✔

156

   const size_t y_words = y_arg.sig_words();

653,417✔

158

   BOTAN_ASSERT_NOMSG(y_words > 0);

653,417✔

160

   BigInt y = y_arg;

653,417✔

162

   BigInt r = x;

653,417✔

163

   BigInt q = BigInt::zero();

653,417✔

164

   secure_vector<word> ws;

653,417✔

166

   r.set_sign(BigInt::Positive);

653,417✔

167

   y.set_sign(BigInt::Positive);

653,417✔

170

   const size_t shifts = y.top_bits_free();

653,417✔

172

   y <<= shifts;

653,417✔

173

   r <<= shifts;

653,417✔

176

   const size_t t = y_words - 1;

653,417✔

177

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

1,306,834✔

179

   BOTAN_ASSERT_NOMSG(n >= t);

653,417✔

181

   q.grow_to(n - t + 1);

653,417✔

183

   word* q_words = q.mutable_data();

653,417✔

185

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

653,417✔

188

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

653,417✔

190

   const word y_t0 = y.word_at(t);

653,417✔

191

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

653,417✔

192

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

653,417✔

194

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

1,574,469✔

195

      const word x_j0 = r.word_at(j);

921,052✔

196

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

921,052✔

197

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

921,052✔

199

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

921,052✔

201

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

921,052✔

204

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

921,052✔

205

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

921,052✔

206

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

921,052✔

208

      shifted_y >>= BOTAN_MP_WORD_BITS;

921,052✔

212

      r -= qjt * shifted_y;

921,052✔

213

      qjt -= r.is_negative();

921,052✔

214

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

921,052✔

216

      q_words[j - t - 1] = qjt;

921,052✔

219

   r >>= shifts;

653,417✔

221

   sign_fixup(x, y_arg, q, r);

653,417✔

223

   r_out = r;

653,417✔

224

   q_out = q;

653,417✔

225

3,267,085✔

randombit / botan / 5079590438

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) {	773,244✔
22	q.cond_flip_sign(x.sign() != y.sign());	773,244✔
23
24	if(x.is_negative() && r.is_nonzero()) {	774,386✔
25	q -= 1;	1,138✔
26	r = y.abs() - r;	3,414✔
27	}
28	}	773,244✔
29
30	inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {	1,842,104✔
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,842,104✔
37	y1 = word_madd2(q, y1, &y3);	1,842,104✔
38	y2 = word_madd2(q, y2, &y3);	1,842,104✔
39
40	const word x[3] = {x1, x2, x3};	1,842,104✔
41	const word y[3] = {y1, y2, y3};	1,842,104✔
42
43	return bigint_ct_is_lt(x, 3, y, 3).is_set();	1,842,104✔
44	}
45
46	}
47
48	void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {	119,827✔
49	if(y.is_zero())	120,317✔
50	throw Invalid_Argument("ct_divide: cannot divide by zero");	×
51
52	const size_t x_words = x.sig_words();	119,827✔
53	const size_t y_words = y.sig_words();	119,827✔
54
55	const size_t x_bits = x.bits();	119,827✔
56
57	BigInt q = BigInt::with_capacity(x_words);	119,827✔
58	BigInt r = BigInt::with_capacity(y_words);	119,827✔
59	BigInt t = BigInt::with_capacity(y_words); // a temporary	119,827✔
60
61	for(size_t i = 0; i != x_bits; ++i) {	144,710,549✔
62	const size_t b = x_bits - 1 - i;	144,590,722✔
63	const bool x_b = x.get_bit(b);	144,590,722✔
64
65	r *= 2;	144,590,722✔
66	r.conditionally_set_bit(0, x_b);	144,590,722✔
67
68	const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;	144,590,722✔
69
70	q.conditionally_set_bit(b, r_gte_y);	144,590,722✔
71	r.ct_cond_swap(r_gte_y, t);	144,590,722✔
72	}
73
74	sign_fixup(x, y, q, r);	119,827✔
75	r_out = r;	119,827✔
76	q_out = q;	119,827✔
77	}	359,476✔
78
79	void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {	931,076✔
80	if(y == 0)	931,076✔
81	throw Invalid_Argument("ct_divide_word: cannot divide by zero");	×
82
83	const size_t x_words = x.sig_words();	931,076✔
84	const size_t x_bits = x.bits();	931,076✔
85
86	BigInt q = BigInt::with_capacity(x_words);	931,076✔
87	word r = 0;
88
89	for(size_t i = 0; i != x_bits; ++i) {	148,194,422✔
90	const size_t b = x_bits - 1 - i;	147,263,346✔
91	const bool x_b = x.get_bit(b);	147,263,346✔
92
93	const auto r_carry = CT::Mask<word>::expand(r >> (BOTAN_MP_WORD_BITS - 1));	147,263,346✔
94
95	r *= 2;	147,263,346✔
96	r += x_b;	147,263,346✔
97
98	const auto r_gte_y = CT::Mask<word>::is_gte(r, y) \| r_carry;	147,263,346✔
99	q.conditionally_set_bit(b, r_gte_y.is_set());	147,263,346✔
100	r = r_gte_y.select(r - y, r);	147,263,346✔
101	}
102
103	if(x.is_negative()) {	931,076✔
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;	931,076✔
112	q_out = q;	931,076✔
113	}	931,076✔
114
115	BigInt ct_modulo(const BigInt& x, const BigInt& y) {	4,865✔
116	if(y.is_negative() \|\| y.is_zero())	9,730✔
117	throw Invalid_Argument("ct_modulo requires y > 0");	×
118
119	const size_t y_words = y.sig_words();	4,865✔
120
121	const size_t x_bits = x.bits();	4,865✔
122
123	BigInt r = BigInt::with_capacity(y_words);	4,865✔
124	BigInt t = BigInt::with_capacity(y_words);	4,865✔
125
126	for(size_t i = 0; i != x_bits; ++i) {	6,892,493✔
127	const size_t b = x_bits - 1 - i;	6,887,628✔
128	const bool x_b = x.get_bit(b);	6,887,628✔
129
130	r *= 2;	6,887,628✔
131	r.conditionally_set_bit(0, x_b);	6,887,628✔
132
133	const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;	6,887,628✔
134
135	r.ct_cond_swap(r_gte_y, t);	6,887,628✔
136	}
137
138	if(x.is_negative()) {	4,865✔
139	if(r.is_nonzero()) {	1,224✔
140	r = y - r;	1,220✔
141	}
142	}
143
144	return r;	4,865✔
145	}	4,865✔
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) {	653,417✔
153	if(y_arg.is_zero())	653,464✔
154	throw Invalid_Argument("vartime_divide: cannot divide by zero");	×
155
156	const size_t y_words = y_arg.sig_words();	653,417✔
157
158	BOTAN_ASSERT_NOMSG(y_words > 0);	653,417✔
159
160	BigInt y = y_arg;	653,417✔
161
162	BigInt r = x;	653,417✔
163	BigInt q = BigInt::zero();	653,417✔
164	secure_vector<word> ws;	653,417✔
165
166	r.set_sign(BigInt::Positive);	653,417✔
167	y.set_sign(BigInt::Positive);	653,417✔
168
169	// Calculate shifts needed to normalize y with high bit set
170	const size_t shifts = y.top_bits_free();	653,417✔
171
172	y <<= shifts;	653,417✔
173	r <<= shifts;	653,417✔
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;	653,417✔
177	const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however	1,306,834✔
178
179	BOTAN_ASSERT_NOMSG(n >= t);	653,417✔
180
181	q.grow_to(n - t + 1);	653,417✔
182
183	word* q_words = q.mutable_data();	653,417✔
184
185	BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n - t));	653,417✔
186
187	// Set q_{n-t} to number of times r > shifted_y
188	q_words[n - t] = r.reduce_below(shifted_y, ws);	653,417✔
189
190	const word y_t0 = y.word_at(t);	653,417✔
191	const word y_t1 = y.word_at(t - 1);	653,417✔
192	BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS - 1)) == 1);	653,417✔
193
194	for(size_t j = n; j != t; --j) {	1,574,469✔
195	const word x_j0 = r.word_at(j);	921,052✔
196	const word x_j1 = r.word_at(j - 1);	921,052✔
197	const word x_j2 = r.word_at(j - 2);	921,052✔
198
199	word qjt = bigint_divop(x_j0, x_j1, y_t0);	921,052✔
200
201	qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt);	921,052✔
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);	921,052✔
205	qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);	921,052✔
206	BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);	921,052✔
207
208	shifted_y >>= BOTAN_MP_WORD_BITS;	921,052✔
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;	921,052✔
213	qjt -= r.is_negative();	921,052✔
214	r += static_cast<word>(r.is_negative()) * shifted_y;	921,052✔
215
216	q_words[j - t - 1] = qjt;	921,052✔
217	}
218
219	r >>= shifts;	653,417✔
220
221	sign_fixup(x, y_arg, q, r);	653,417✔
222
223	r_out = r;	653,417✔
224	q_out = q;	653,417✔
225	}	3,267,085✔
226
227	}

randombit / botan / 5079590438

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