25619874939

Committed 09 May 2026 05:34PM UTC coverage: 89.328% (-0.002%) from 89.33%

Build # 25619874939

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5591 from randombit/jack/gha-cache-cleanup

In GH Actions clean up branch caches after the PRs are merged

Coverage Stats

107641 of 120501 relevant lines covered (89.33%)

11279629.67 hits per line

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

91.67

/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/exceptn.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) {
      const 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.signum() >= 0) {
      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.signum() < 0) {
      throw Invalid_Argument("BigInt::operator% modulus must be > 0");
   }
   if(n.signum() >= 0 && mod.signum() >= 0 && 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.signum() >= 0 && is_power_of_2(mod)) {
      remainder = (n.word_at(0) & (mod - 1));
   } else {
      const 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) {
   if(shift >= 65536) {
      throw Invalid_Argument("BigInt left shift count too large");
   }

   if(x.is_zero()) {
      return BigInt::zero();
   }

   const size_t x_sw = x.sig_words();

   const size_t new_size = x_sw + shift / WordInfo<word>::bits + 1;
   BigInt y = BigInt::with_capacity(new_size);
   bigint_shl2(y.mutable_data(), new_size, 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();
   }

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

   if(x.signum() < 0 && 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/exceptn.h>
12	#include <botan/internal/bit_ops.h>
13	#include <botan/internal/divide.h>
14	#include <botan/internal/mp_core.h>
15	#include <algorithm>
16
17	namespace Botan {
18
19	//static
20	BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_size, BigInt::Sign y_sign) {	3,203,136✔
21	const size_t x_sw = x.sig_words();	3,203,136✔
22
23	BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);	3,366,032✔
24
25	if(x.sign() == y_sign) {	3,203,136✔
26	const word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);	2,769,434✔
27	z.mutable_data()[std::max(x_sw, y_size)] += carry;	2,769,434✔
28	z.set_sign(x.sign());	2,769,434✔
29	} else {
30	const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);	433,702✔
31
32	if(relative_size < 0) {	433,702✔
33	// x < y so z = abs(y - x)
34	// NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
35	bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);	6,717✔
36	z.set_sign(y_sign);	6,717✔
37	} else if(relative_size == 0) {	426,985✔
38	// Positive zero (nothing to do in this case)
39	} else {
40	/*
41	* We know at this point that x >= y so if y_size is larger than
42	* x_sw, we are guaranteed they are just leading zeros which can
43	* be ignored
44	*/
45	y_size = std::min(x_sw, y_size);	426,875✔
46	bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);	426,875✔
47	z.set_sign(x.sign());	426,875✔
48	}
49	}
50
51	return z;	3,203,136✔
52	}	×
53
54	/*
55	* Multiplication Operator
56	*/
57	BigInt operator*(const BigInt& x, const BigInt& y) {	45,226✔
58	const size_t x_sw = x.sig_words();	45,226✔
59	const size_t y_sw = y.sig_words();	45,226✔
60
61	BigInt z = BigInt::with_capacity(x.size() + y.size());	45,226✔
62
63	if(x_sw == 1 && y_sw > 0) {	45,226✔
64	bigint_linmul3(z.mutable_data(), y._data(), y_sw, x.word_at(0));	40,934✔
65	} else if(y_sw == 1 && x_sw > 0) {	24,759✔
66	bigint_linmul3(z.mutable_data(), x._data(), x_sw, y.word_at(0));	7,686✔
67	} else if(x_sw > 0 && y_sw > 0) {	20,916✔
68	secure_vector<word> workspace(z.size());	20,116✔
69
70	bigint_mul(z.mutable_data(),	20,116✔
71	z.size(),
72	x._data(),
73	x.size(),
74	x_sw,
75	y._data(),
76	y.size(),
77	y_sw,
78	workspace.data(),
79	workspace.size());
80	}	20,116✔
81
82	z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());	90,075✔
83
84	return z;	45,226✔
85	}	×
86
87	/*
88	* Multiplication Operator
89	*/
90	BigInt operator*(const BigInt& x, word y) {	3,676,604✔
91	const size_t x_sw = x.sig_words();	3,676,604✔
92
93	BigInt z = BigInt::with_capacity(x_sw + 1);	3,676,604✔
94
95	if(x_sw > 0 && y > 0) {	3,676,604✔
96	bigint_linmul3(z.mutable_data(), x._data(), x_sw, y);	3,676,604✔
97	z.set_sign(x.sign());	3,676,604✔
98	}
99
100	return z;	3,676,604✔
101	}	×
102
103	/*
104	* Division Operator
105	*/
106	BigInt operator/(const BigInt& x, const BigInt& y) {	70,755✔
107	if(y.sig_words() == 1 && y.signum() >= 0) {	73,215✔
108	return x / y.word_at(0);	10,540✔
109	}
110
111	BigInt q;	65,485✔
112	BigInt r;	65,485✔
113	vartime_divide(x, y, q, r);	65,485✔
114	return q;	65,485✔
115	}	65,485✔
116
117	/*
118	* Division Operator
119	*/
120	BigInt operator/(const BigInt& x, word y) {	5,587✔
121	if(y == 0) {	5,587✔
122	throw Invalid_Argument("BigInt::operator/ divide by zero");	×
123	}
124
125	BigInt q;	5,587✔
126	word r = 0;	5,587✔
127	ct_divide_word(x, y, q, r);	5,587✔
128	return q;	5,587✔
129	}	×
130
131	/*
132	* Modulo Operator
133	*/
134	BigInt operator%(const BigInt& n, const BigInt& mod) {	541,312✔
135	if(mod.is_zero()) {	541,424✔
136	throw Invalid_Argument("BigInt::operator% divide by zero");	×
137	}
138	if(mod.signum() < 0) {	541,312✔
139	throw Invalid_Argument("BigInt::operator% modulus must be > 0");	×
140	}
141	if(n.signum() >= 0 && mod.signum() >= 0 && n < mod) {	1,051,787✔
142	return n;	576✔
143	}
144
145	if(mod.sig_words() == 1) {	540,736✔
146	return BigInt::from_word(n % mod.word_at(0));	499,768✔
147	}
148
149	BigInt q;	290,852✔
150	BigInt r;	290,852✔
151	vartime_divide(n, mod, q, r);	290,852✔
152	return r;	290,852✔
153	}	290,852✔
154
155	/*
156	* Modulo Operator
157	*/
158	word operator%(const BigInt& n, word mod) {	537,200✔
159	if(mod == 0) {	537,200✔
160	throw Invalid_Argument("BigInt::operator% divide by zero");	×
161	}
162
163	if(mod == 1) {	537,200✔
164	return 0;
165	}
166
167	word remainder = 0;	537,031✔
168
169	if(n.signum() >= 0 && is_power_of_2(mod)) {	537,031✔
170	remainder = (n.word_at(0) & (mod - 1));	379,652✔
171	} else {
172	const divide_precomp redc_mod(mod);	347,205✔
173	const size_t sw = n.sig_words();	347,205✔
174	for(size_t i = sw; i > 0; --i) {	709,092✔
175	remainder = redc_mod.vartime_mod_2to1(remainder, n.word_at(i - 1));	723,774✔
176	}
177	}
178
179	if(remainder != 0 && n.sign() == BigInt::Negative) {	537,031✔
180	return mod - remainder;	30,000✔
181	}
182	return remainder;
183	}
184
185	/*
186	* Left Shift Operator
187	*/
188	BigInt operator<<(const BigInt& x, size_t shift) {	507,999✔
189	if(shift >= 65536) {	507,999✔
190	throw Invalid_Argument("BigInt left shift count too large");	×
191	}
192
193	if(x.is_zero()) {	979,737✔
194	return BigInt::zero();	2✔
195	}
196
197	const size_t x_sw = x.sig_words();	507,997✔
198
199	const size_t new_size = x_sw + shift / WordInfo<word>::bits + 1;	507,997✔
200	BigInt y = BigInt::with_capacity(new_size);	507,997✔
201	bigint_shl2(y.mutable_data(), new_size, x._data(), x_sw, shift);	507,997✔
202	y.set_sign(x.sign());	507,997✔
203	return y;	507,997✔
204	}	507,997✔
205
206	/*
207	* Right Shift Operator
208	*/
209	BigInt operator>>(const BigInt& x, size_t shift) {	205,091✔
210	const size_t shift_words = shift / WordInfo<word>::bits;	205,091✔
211	const size_t x_sw = x.sig_words();	205,091✔
212
213	if(shift_words >= x_sw) {	205,091✔
214	return BigInt::zero();	2,063✔
215	}
216
217	const size_t new_size = x_sw - shift_words;	203,028✔
218	BigInt y = BigInt::with_capacity(new_size);	203,028✔
219	bigint_shr2(y.mutable_data(), new_size, x._data(), x_sw, shift);	203,028✔
220
221	if(x.signum() < 0 && y.is_zero()) {	203,053✔
222	y.set_sign(BigInt::Positive);	3✔
223	} else {
224	y.set_sign(x.sign());	203,025✔
225	}
226
227	return y;	203,028✔
228	}	203,028✔
229
230	} // namespace Botan

randombit / botan / 25619874939

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