17279736665

Committed 27 Aug 2025 06:26PM UTC coverage: 90.667% (+0.009%) from 90.658%

Build # 17279736665

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5077 from randombit/jack/opt-word-div

Refactorings to support optimized word level division/modulus

Run Details

100205 of 110520 relevant lines covered (90.67%)

12125331.55 hits per line

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

91.26

/src/lib/math/bigint/big_ops3.cpp

/*
* BigInt Binary Operators
* (C) 1999-2007,2018 Jack Lloyd
*     2016 Matthias Gierlings
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/bigint.h>

#include <botan/internal/bit_ops.h>
#include <botan/internal/divide.h>
#include <botan/internal/mp_core.h>
#include <algorithm>

namespace Botan {

//static
BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_size, BigInt::Sign y_sign) {
   const size_t x_sw = x.sig_words();

   BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);

   if(x.sign() == y_sign) {
      word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);
      z.mutable_data()[std::max(x_sw, y_size)] += carry;
      z.set_sign(x.sign());
   } else {
      const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);

      if(relative_size < 0) {
         // x < y so z = abs(y - x)
         // NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
         bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);
         z.set_sign(y_sign);
      } else if(relative_size == 0) {
         // Positive zero (nothing to do in this case)
      } else {
         /*
         * We know at this point that x >= y so if y_size is larger than
         * x_sw, we are guaranteed they are just leading zeros which can
         * be ignored
         */
         y_size = std::min(x_sw, y_size);
         bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);
         z.set_sign(x.sign());
      }
   }

   return z;
}

/*
* Multiplication Operator
*/
BigInt operator*(const BigInt& x, const BigInt& y) {
   const size_t x_sw = x.sig_words();
   const size_t y_sw = y.sig_words();

   BigInt z = BigInt::with_capacity(x.size() + y.size());

   if(x_sw == 1 && y_sw > 0) {
      bigint_linmul3(z.mutable_data(), y._data(), y_sw, x.word_at(0));
   } else if(y_sw == 1 && x_sw > 0) {
      bigint_linmul3(z.mutable_data(), x._data(), x_sw, y.word_at(0));
   } else if(x_sw > 0 && y_sw > 0) {
      secure_vector<word> workspace(z.size());

      bigint_mul(z.mutable_data(),
                 z.size(),
                 x._data(),
                 x.size(),
                 x_sw,
                 y._data(),
                 y.size(),
                 y_sw,
                 workspace.data(),
                 workspace.size());
   }

   z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());

   return z;
}

/*
* Multiplication Operator
*/
BigInt operator*(const BigInt& x, word y) {
   const size_t x_sw = x.sig_words();

   BigInt z = BigInt::with_capacity(x_sw + 1);

   if(x_sw > 0 && y > 0) {
      bigint_linmul3(z.mutable_data(), x._data(), x_sw, y);
      z.set_sign(x.sign());
   }

   return z;
}

/*
* Division Operator
*/
BigInt operator/(const BigInt& x, const BigInt& y) {
   if(y.sig_words() == 1 && y.is_positive()) {
      return x / y.word_at(0);
   }

   BigInt q;
   BigInt r;
   vartime_divide(x, y, q, r);
   return q;
}

/*
* Division Operator
*/
BigInt operator/(const BigInt& x, word y) {
   if(y == 0) {
      throw Invalid_Argument("BigInt::operator/ divide by zero");
   }

   BigInt q;
   word r = 0;
   ct_divide_word(x, y, q, r);
   return q;
}

/*
* Modulo Operator
*/
BigInt operator%(const BigInt& n, const BigInt& mod) {
   if(mod.is_zero()) {
      throw Invalid_Argument("BigInt::operator% divide by zero");
   }
   if(mod.is_negative()) {
      throw Invalid_Argument("BigInt::operator% modulus must be > 0");
   }
   if(n.is_positive() && mod.is_positive() && n < mod) {
      return n;
   }

   if(mod.sig_words() == 1) {
      return BigInt::from_word(n % mod.word_at(0));
   }

   BigInt q;
   BigInt r;
   vartime_divide(n, mod, q, r);
   return r;
}

/*
* Modulo Operator
*/
word operator%(const BigInt& n, word mod) {
   if(mod == 0) {
      throw Invalid_Argument("BigInt::operator% divide by zero");
   }

   if(mod == 1) {
      return 0;
   }

   word remainder = 0;

   if(n.is_positive() && is_power_of_2(mod)) {
      remainder = (n.word_at(0) & (mod - 1));
   } else {
      divide_precomp redc_mod(mod);
      const size_t sw = n.sig_words();
      for(size_t i = sw; i > 0; --i) {
         remainder = redc_mod.vartime_mod_2to1(remainder, n.word_at(i - 1));
      }
   }

   if(remainder != 0 && n.sign() == BigInt::Negative) {
      return mod - remainder;
   }
   return remainder;
}

/*
* Left Shift Operator
*/
BigInt operator<<(const BigInt& x, size_t shift) {
   const size_t x_sw = x.sig_words();

   const size_t new_size = x_sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
   BigInt y = BigInt::with_capacity(new_size);
   bigint_shl2(y.mutable_data(), x._data(), x_sw, shift);
   y.set_sign(x.sign());
   return y;
}

/*
* Right Shift Operator
*/
BigInt operator>>(const BigInt& x, size_t shift) {
   const size_t shift_words = shift / WordInfo<word>::bits;
   const size_t x_sw = x.sig_words();

   if(shift_words >= x_sw) {
      return BigInt::zero();
   }

   BigInt y = BigInt::with_capacity(x_sw - shift_words);
   bigint_shr2(y.mutable_data(), x._data(), x_sw, shift);

   if(x.is_negative() && y.is_zero()) {
      y.set_sign(BigInt::Positive);
   } else {
      y.set_sign(x.sign());
   }

   return y;
}

}  // namespace Botan

1	/*
2	* BigInt Binary Operators
3	* (C) 1999-2007,2018 Jack Lloyd
4	* 2016 Matthias Gierlings
5	*
6	* Botan is released under the Simplified BSD License (see license.txt)
7	*/
8
9	#include <botan/bigint.h>
10
11	#include <botan/internal/bit_ops.h>
12	#include <botan/internal/divide.h>
13	#include <botan/internal/mp_core.h>
14	#include <algorithm>
15
16	namespace Botan {
17
18	//static
19	BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_size, BigInt::Sign y_sign) {	3,967,265✔
20	const size_t x_sw = x.sig_words();	3,967,265✔
21
22	BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);	4,143,951✔
23
24	if(x.sign() == y_sign) {	3,967,265✔
25	word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);	3,516,186✔
26	z.mutable_data()[std::max(x_sw, y_size)] += carry;	3,516,186✔
27	z.set_sign(x.sign());	3,516,186✔
28	} else {
29	const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);	451,079✔
30
31	if(relative_size < 0) {	451,079✔
32	// x < y so z = abs(y - x)
33	// NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
34	bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);	6,774✔
35	z.set_sign(y_sign);	6,774✔
36	} else if(relative_size == 0) {	444,305✔
37	// Positive zero (nothing to do in this case)
38	} else {
39	/*
40	* We know at this point that x >= y so if y_size is larger than
41	* x_sw, we are guaranteed they are just leading zeros which can
42	* be ignored
43	*/
44	y_size = std::min(x_sw, y_size);	444,194✔
45	bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);	444,194✔
46	z.set_sign(x.sign());	444,194✔
47	}
48	}
49
50	return z;	3,967,265✔
51	}	×
52
53	/*
54	* Multiplication Operator
55	*/
56	BigInt operator*(const BigInt& x, const BigInt& y) {	46,857✔
57	const size_t x_sw = x.sig_words();	46,857✔
58	const size_t y_sw = y.sig_words();	46,857✔
59
60	BigInt z = BigInt::with_capacity(x.size() + y.size());	46,857✔
61
62	if(x_sw == 1 && y_sw > 0) {	46,857✔
63	bigint_linmul3(z.mutable_data(), y._data(), y_sw, x.word_at(0));	47,818✔
64	} else if(y_sw == 1 && x_sw > 0) {	22,948✔
65	bigint_linmul3(z.mutable_data(), x._data(), x_sw, y.word_at(0));	7,692✔
66	} else if(x_sw > 0 && y_sw > 0) {	19,102✔
67	secure_vector<word> workspace(z.size());	18,330✔
68
69	bigint_mul(z.mutable_data(),	18,330✔
70	z.size(),
71	x._data(),
72	x.size(),
73	x_sw,
74	y._data(),
75	y.size(),
76	y_sw,
77	workspace.data(),
78	workspace.size());
79	}	18,330✔
80
81	z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());	93,344✔
82
83	return z;	46,857✔
84	}	×
85
86	/*
87	* Multiplication Operator
88	*/
89	BigInt operator*(const BigInt& x, word y) {	3,508,990✔
90	const size_t x_sw = x.sig_words();	3,508,990✔
91
92	BigInt z = BigInt::with_capacity(x_sw + 1);	3,508,990✔
93
94	if(x_sw > 0 && y > 0) {	3,508,990✔
95	bigint_linmul3(z.mutable_data(), x._data(), x_sw, y);	3,399,901✔
96	z.set_sign(x.sign());	3,399,901✔
97	}
98
99	return z;	3,508,990✔
100	}	×
101
102	/*
103	* Division Operator
104	*/
105	BigInt operator/(const BigInt& x, const BigInt& y) {	156,029✔
106	if(y.sig_words() == 1 && y.is_positive()) {	158,487✔
107	return x / y.word_at(0);	110,890✔
108	}
109
110	BigInt q;	100,584✔
111	BigInt r;	100,584✔
112	vartime_divide(x, y, q, r);	100,584✔
113	return q;	100,584✔
114	}	100,584✔
115
116	/*
117	* Division Operator
118	*/
119	BigInt operator/(const BigInt& x, word y) {	56,039✔
120	if(y == 0) {	56,039✔
121	throw Invalid_Argument("BigInt::operator/ divide by zero");	×
122	}
123
124	BigInt q;	56,039✔
125	word r = 0;	56,039✔
126	ct_divide_word(x, y, q, r);	56,039✔
127	return q;	56,039✔
128	}	×
129
130	/*
131	* Modulo Operator
132	*/
133	BigInt operator%(const BigInt& n, const BigInt& mod) {	462,782✔
134	if(mod.is_zero()) {	462,893✔
135	throw Invalid_Argument("BigInt::operator% divide by zero");	×
136	}
137	if(mod.is_negative()) {	462,782✔
138	throw Invalid_Argument("BigInt::operator% modulus must be > 0");	×
139	}
140	if(n.is_positive() && mod.is_positive() && n < mod) {	894,397✔
141	return n;	374✔
142	}
143
144	if(mod.sig_words() == 1) {	462,408✔
145	return BigInt::from_word(n % mod.word_at(0));	483,016✔
146	}
147
148	BigInt q;	220,900✔
149	BigInt r;	220,900✔
150	vartime_divide(n, mod, q, r);	220,900✔
151	return r;	220,900✔
152	}	220,900✔
153
154	/*
155	* Modulo Operator
156	*/
157	word operator%(const BigInt& n, word mod) {	995,925✔
158	if(mod == 0) {	995,925✔
159	throw Invalid_Argument("BigInt::operator% divide by zero");	×
160	}
161
162	if(mod == 1) {	995,925✔
163	return 0;
164	}
165
166	word remainder = 0;	995,909✔
167
168	if(n.is_positive() && is_power_of_2(mod)) {	995,909✔
169	remainder = (n.word_at(0) & (mod - 1));	382,380✔
170	} else {
171	divide_precomp redc_mod(mod);	804,719✔
172	const size_t sw = n.sig_words();	804,719✔
173	for(size_t i = sw; i > 0; --i) {	7,468,685✔
174	remainder = redc_mod.vartime_mod_2to1(remainder, n.word_at(i - 1));	13,327,932✔
175	}
176	}
177
178	if(remainder != 0 && n.sign() == BigInt::Negative) {	995,909✔
179	return mod - remainder;	29,967✔
180	}
181	return remainder;
182	}
183
184	/*
185	* Left Shift Operator
186	*/
187	BigInt operator<<(const BigInt& x, size_t shift) {	324,697✔
188	const size_t x_sw = x.sig_words();	324,697✔
189
190	const size_t new_size = x_sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	324,697✔
191	BigInt y = BigInt::with_capacity(new_size);	324,697✔
192	bigint_shl2(y.mutable_data(), x._data(), x_sw, shift);	324,697✔
193	y.set_sign(x.sign());	324,697✔
194	return y;	324,697✔
195	}	×
196
197	/*
198	* Right Shift Operator
199	*/
200	BigInt operator>>(const BigInt& x, size_t shift) {	214,876✔
201	const size_t shift_words = shift / WordInfo<word>::bits;	214,876✔
202	const size_t x_sw = x.sig_words();	214,876✔
203
204	if(shift_words >= x_sw) {	214,876✔
205	return BigInt::zero();	2,062✔
206	}
207
208	BigInt y = BigInt::with_capacity(x_sw - shift_words);	212,814✔
209	bigint_shr2(y.mutable_data(), x._data(), x_sw, shift);	212,814✔
210
211	if(x.is_negative() && y.is_zero()) {	212,839✔
212	y.set_sign(BigInt::Positive);	3✔
213	} else {
214	y.set_sign(x.sign());	212,811✔
215	}
216
217	return y;	212,814✔
218	}	212,814✔
219
220	} // namespace Botan

randombit / botan / 17279736665

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