5123321399

Committed 30 May 2023 04:06PM UTC coverage: 92.213% (+0.004%) from 92.209%

Build # 5123321399

Build Type

Pull #3558

github

Committed by

web-flow

Commit Message

Merge dd72f7389 into 057bcbc35

Pull Request Pull Request #3558: Add braces around all if/else statements

Run Details

75602 of 81986 relevant lines covered (92.21%)

11859779.3 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.64

/src/lib/math/bigint/divide.cpp

/*
* Division Algorithms
* (C) 1999-2007,2012,2018,2021 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/divide.h>

#include <botan/internal/bit_ops.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/mp_core.h>

namespace Botan {

namespace {

/*
* Handle signed operands, if necessary
*/
void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {
   q.cond_flip_sign(x.sign() != y.sign());

   if(x.is_negative() && r.is_nonzero()) {
      q -= 1;
      r = y.abs() - r;
   }
}

inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {
   /*
   Compute (y3,y2,y1) = (y2,y1) * q
   and return true if (y3,y2,y1) > (x3,x2,x1)
   */

   word y3 = 0;
   y1 = word_madd2(q, y1, &y3);
   y2 = word_madd2(q, y2, &y3);

   const word x[3] = {x1, x2, x3};
   const word y[3] = {y1, y2, y3};

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

}  // namespace

void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {
   if(y.is_zero()) {
      throw Invalid_Argument("ct_divide: cannot divide by zero");
   }

   const size_t x_words = x.sig_words();
   const size_t y_words = y.sig_words();

   const size_t x_bits = x.bits();

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

   for(size_t i = 0; i != x_bits; ++i) {
      const size_t b = x_bits - 1 - i;
      const bool x_b = x.get_bit(b);

      r *= 2;
      r.conditionally_set_bit(0, x_b);

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

      q.conditionally_set_bit(b, r_gte_y);
      r.ct_cond_swap(r_gte_y, t);
   }

   sign_fixup(x, y, q, r);
   r_out = r;
   q_out = q;
}

void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {
   if(y == 0) {
      throw Invalid_Argument("ct_divide_word: cannot divide by zero");
   }

   const size_t x_words = x.sig_words();
   const size_t x_bits = x.bits();

   BigInt q = BigInt::with_capacity(x_words);
   word r = 0;

   for(size_t i = 0; i != x_bits; ++i) {
      const size_t b = x_bits - 1 - i;
      const bool x_b = x.get_bit(b);

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

      r *= 2;
      r += x_b;

      const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;
      q.conditionally_set_bit(b, r_gte_y.is_set());
      r = r_gte_y.select(r - y, r);
   }

   if(x.is_negative()) {
      q.flip_sign();
      if(r != 0) {
         --q;
         r = y - r;
      }
   }

   r_out = r;
   q_out = q;
}

BigInt ct_modulo(const BigInt& x, const BigInt& y) {
   if(y.is_negative() || y.is_zero()) {
      throw Invalid_Argument("ct_modulo requires y > 0");
   }

   const size_t y_words = y.sig_words();

   const size_t x_bits = x.bits();

   BigInt r = BigInt::with_capacity(y_words);
   BigInt t = BigInt::with_capacity(y_words);

   for(size_t i = 0; i != x_bits; ++i) {
      const size_t b = x_bits - 1 - i;
      const bool x_b = x.get_bit(b);

      r *= 2;
      r.conditionally_set_bit(0, x_b);

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

      r.ct_cond_swap(r_gte_y, t);
   }

   if(x.is_negative()) {
      if(r.is_nonzero()) {
         r = y - r;
      }
   }

   return r;
}

/*
* Solve x = q * y + r
*
* See Handbook of Applied Cryptography section 14.2.5
*/
void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {
   if(y_arg.is_zero()) {
      throw Invalid_Argument("vartime_divide: cannot divide by zero");
   }

   const size_t y_words = y_arg.sig_words();

   BOTAN_ASSERT_NOMSG(y_words > 0);

   BigInt y = y_arg;

   BigInt r = x;
   BigInt q = BigInt::zero();
   secure_vector<word> ws;

   r.set_sign(BigInt::Positive);
   y.set_sign(BigInt::Positive);

   // Calculate shifts needed to normalize y with high bit set
   const size_t shifts = y.top_bits_free();

   y <<= shifts;
   r <<= shifts;

   // we know y has not changed size, since we only shifted up to set high bit
   const size_t t = y_words - 1;
   const size_t n = std::max(y_words, r.sig_words()) - 1;  // r may have changed size however

   BOTAN_ASSERT_NOMSG(n >= t);

   q.grow_to(n - t + 1);

   word* q_words = q.mutable_data();

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

   // Set q_{n-t} to number of times r > shifted_y
   q_words[n - t] = r.reduce_below(shifted_y, ws);

   const word y_t0 = y.word_at(t);
   const word y_t1 = y.word_at(t - 1);
   BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS - 1)) == 1);

   for(size_t j = n; j != t; --j) {
      const word x_j0 = r.word_at(j);
      const word x_j1 = r.word_at(j - 1);
      const word x_j2 = r.word_at(j - 2);

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

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

      // Per HAC 14.23, this operation is required at most twice
      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
      qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
      BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);

      shifted_y >>= BOTAN_MP_WORD_BITS;
      // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))

      // TODO this sequence could be better
      r -= qjt * shifted_y;
      qjt -= r.is_negative();
      r += static_cast<word>(r.is_negative()) * shifted_y;

      q_words[j - t - 1] = qjt;
   }

   r >>= shifts;

   sign_fixup(x, y_arg, q, r);

   r_out = r;
   q_out = q;
}

}  // namespace Botan

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

randombit / botan / 5123321399

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