17281389884

Committed 25 Aug 2025 03:59PM UTC coverage: 90.666% (-0.001%) from 90.667%

Build # 17281389884

Build Type

push

github

Committed by

geekrun

Commit Message

init

Run Details

100200 of 110516 relevant lines covered (90.67%)

12215638.67 hits per line

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

90.23

/src/lib/math/bigint/big_ops2.cpp

/*
* (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/mp_core.h>
#include <algorithm>

/* This hack works around an undefined reference to __udivti3() when compiling for 64-bit Windows
 * using clang-cl, see:
 *
 * https://github.com/llvm/llvm-project/issues/25679
 * https://stackoverflow.com/questions/68676184/clang-cl-error-lld-link-error-undefined-symbol-divti3
 *
 * I couldn't come up with a way to embed this into the build info files without extending
 * configure.py to allow cpu-specific libs in the compiler info or os+cc+arch-specific libs in the
 * module info. Hopefully this can go away when the above Clang issue is fixed anyway.
*/
#if defined(_WIN64) && defined(BOTAN_BUILD_COMPILER_IS_CLANGCL)
   #pragma comment(lib, "clang_rt.builtins-x86_64.lib")
#endif

namespace Botan {

BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {
   const size_t x_sw = sig_words();

   grow_to(std::max(x_sw, y_words) + 1);

   if(sign() == y_sign) {
      word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);
      mutable_data()[size() - 1] += carry;
   } else {
      const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);

      if(relative_size >= 0) {
         // *this >= y
         bigint_sub2(mutable_data(), x_sw, y, y_words);
      } else {
         // *this < y: compute *this = y - *this
         bigint_sub2_rev(mutable_data(), y, y_words);
      }

      if(relative_size < 0) {
         set_sign(y_sign);
      } else if(relative_size == 0) {
         set_sign(Positive);
      }
   }

   return (*this);
}

BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {
   if(this->is_negative() || s.is_negative() || mod.is_negative()) {
      throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
   }

   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);

   /*
   t + s or t + s - p == t - (p - s)

   So first compute ws = p - s

   Then compute t + s and t - ws

   If t - ws does not borrow, then that is the correct valued
   */

   const size_t mod_sw = mod.sig_words();
   BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");

   this->grow_to(mod_sw);
   s.grow_to(mod_sw);

   // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
   if(ws.size() < 3 * mod_sw) {
      ws.resize(3 * mod_sw);
   }

   // NOLINTBEGIN(readability-container-data-pointer)

   word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
   BOTAN_DEBUG_ASSERT(borrow == 0);
   BOTAN_UNUSED(borrow);

   // Compute t - ws
   borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);

   // Compute t + s
   bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);

   CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
   set_words(&ws[0], mod_sw);

   // NOLINTEND(readability-container-data-pointer)

   return (*this);
}

BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {
   if(this->is_negative() || s.is_negative() || mod.is_negative()) {
      throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
   }

   // We are assuming in this function that *this and s are no more than mod_sw words long
   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);

   const size_t mod_sw = mod.sig_words();

   this->grow_to(mod_sw);
   s.grow_to(mod_sw);

   if(ws.size() < mod_sw) {
      ws.resize(mod_sw);
   }

   const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);

   // Conditionally add back the modulus
   bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);

   copy_mem(mutable_data(), ws.data(), mod_sw);

   return (*this);
}

BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {
   BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
   BOTAN_ARG_CHECK(y < 16, "y too large");

   BOTAN_DEBUG_ASSERT(*this < mod);

   *this *= static_cast<word>(y);
   this->reduce_below(mod, ws);
   return (*this);
}

BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {
   BOTAN_UNUSED(ws);
   BigInt y_bn;
   y_bn.m_data.set_words(y, y_sw);
   *this = y_bn - *this;
   return (*this);
}

/*
* Multiplication Operator
*/
BigInt& BigInt::operator*=(const BigInt& y) {
   secure_vector<word> ws;
   return this->mul(y, ws);
}

BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {
   const size_t x_sw = sig_words();
   const size_t y_sw = y.sig_words();
   set_sign((sign() == y.sign()) ? Positive : Negative);

   if(x_sw == 0 || y_sw == 0) {
      clear();
      set_sign(Positive);
   } else if(x_sw == 1 && y_sw > 0) {
      grow_to(y_sw + 1);
      bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
   } else {
      const size_t new_size = x_sw + y_sw + 1;
      if(ws.size() < new_size) {
         ws.resize(new_size);
      }
      secure_vector<word> z_reg(new_size);

      bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());

      this->swap_reg(z_reg);
   }

   return (*this);
}

BigInt& BigInt::square(secure_vector<word>& ws) {
   const size_t sw = sig_words();

   secure_vector<word> z(2 * sw);
   ws.resize(z.size());

   bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());

   swap_reg(z);
   set_sign(BigInt::Positive);

   return (*this);
}

BigInt& BigInt::operator*=(word y) {
   if(y == 0) {
      clear();
      set_sign(Positive);
   }

   const word carry = bigint_linmul2(mutable_data(), size(), y);
   set_word_at(size(), carry);

   return (*this);
}

/*
* Division Operator
*/
BigInt& BigInt::operator/=(const BigInt& y) {
   if(y.sig_words() == 1 && is_positive() && y.is_positive() && is_power_of_2(y.word_at(0))) {
      (*this) >>= (y.bits() - 1);
   } else {
      (*this) = (*this) / y;
   }
   return (*this);
}

/*
* Modulo Operator
*/
BigInt& BigInt::operator%=(const BigInt& mod) {
   return (*this = (*this) % mod);
}

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

   word remainder = 0;

   if(is_power_of_2(mod)) {
      remainder = (word_at(0) & (mod - 1));
   } else {
      const size_t sw = sig_words();
      for(size_t i = sw; i > 0; --i) {
         remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);
      }
   }

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

   m_data.set_to_zero();
   m_data.set_word_at(0, remainder);
   set_sign(BigInt::Positive);
   return remainder;
}

/*
* Left Shift Operator
*/
BigInt& BigInt::operator<<=(size_t shift) {
   const size_t sw = sig_words();
   const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;

   m_data.grow_to(new_size);

   bigint_shl1(m_data.mutable_data(), new_size, sw, shift);

   return (*this);
}

/*
* Right Shift Operator
*/
BigInt& BigInt::operator>>=(size_t shift) {
   bigint_shr1(m_data.mutable_data(), m_data.size(), shift);

   if(is_negative() && is_zero()) {
      set_sign(Positive);
   }

   return (*this);
}

}  // namespace Botan

1	/*
2	* (C) 1999-2007,2018 Jack Lloyd
3	* 2016 Matthias Gierlings
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*/
7
8	#include <botan/bigint.h>
9
10	#include <botan/internal/bit_ops.h>
11	#include <botan/internal/mp_core.h>
12	#include <algorithm>
13
14	/* This hack works around an undefined reference to __udivti3() when compiling for 64-bit Windows
15	* using clang-cl, see:
16	*
17	* https://github.com/llvm/llvm-project/issues/25679
18	* https://stackoverflow.com/questions/68676184/clang-cl-error-lld-link-error-undefined-symbol-divti3
19	*
20	* I couldn't come up with a way to embed this into the build info files without extending
21	* configure.py to allow cpu-specific libs in the compiler info or os+cc+arch-specific libs in the
22	* module info. Hopefully this can go away when the above Clang issue is fixed anyway.
23	*/
24	#if defined(_WIN64) && defined(BOTAN_BUILD_COMPILER_IS_CLANGCL)
25	#pragma comment(lib, "clang_rt.builtins-x86_64.lib")
26	#endif
27
28	namespace Botan {
29
30	BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {	5,495,794✔
31	const size_t x_sw = sig_words();	5,495,794✔
32
33	grow_to(std::max(x_sw, y_words) + 1);	5,566,284✔
34
35	if(sign() == y_sign) {	5,495,794✔
36	word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);	1,867,860✔
37	mutable_data()[size() - 1] += carry;	1,867,860✔
38	} else {
39	const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);	3,627,934✔
40
41	if(relative_size >= 0) {	3,627,934✔
42	// *this >= y
43	bigint_sub2(mutable_data(), x_sw, y, y_words);	3,568,198✔
44	} else {
45	// this < y: compute this = y - *this
46	bigint_sub2_rev(mutable_data(), y, y_words);	59,736✔
47	}
48
49	if(relative_size < 0) {	3,627,934✔
50	set_sign(y_sign);	59,736✔
51	} else if(relative_size == 0) {	3,568,198✔
52	set_sign(Positive);	53,140✔
53	}
54	}
55
56	return (*this);	5,495,794✔
57	}
58
59	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	971,702✔
60	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	971,702✔
61	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
62	}
63
64	BOTAN_DEBUG_ASSERT(*this < mod);	971,702✔
65	BOTAN_DEBUG_ASSERT(s < mod);	971,702✔
66
67	/*
68	t + s or t + s - p == t - (p - s)
69
70	So first compute ws = p - s
71
72	Then compute t + s and t - ws
73
74	If t - ws does not borrow, then that is the correct valued
75	*/
76
77	const size_t mod_sw = mod.sig_words();	971,702✔
78	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	971,702✔
79
80	this->grow_to(mod_sw);	971,702✔
81	s.grow_to(mod_sw);	971,702✔
82
83	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
84	if(ws.size() < 3 * mod_sw) {	971,702✔
85	ws.resize(3 * mod_sw);	617,198✔
86	}
87
88	// NOLINTBEGIN(readability-container-data-pointer)
89
90	word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);	971,702✔
91	BOTAN_DEBUG_ASSERT(borrow == 0);	971,702✔
92	BOTAN_UNUSED(borrow);	971,702✔
93
94	// Compute t - ws
95	borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);	971,702✔
96
97	// Compute t + s
98	bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);	971,702✔
99
100	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	971,702✔
101	set_words(&ws[0], mod_sw);	971,702✔
102
103	// NOLINTEND(readability-container-data-pointer)
104
105	return (*this);	971,702✔
106	}
107
108	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	15,714,259✔
109	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	15,714,259✔
110	throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");	×
111	}
112
113	// We are assuming in this function that *this and s are no more than mod_sw words long
114	BOTAN_DEBUG_ASSERT(*this < mod);	15,714,259✔
115	BOTAN_DEBUG_ASSERT(s < mod);	15,714,259✔
116
117	const size_t mod_sw = mod.sig_words();	15,714,259✔
118
119	this->grow_to(mod_sw);	15,714,259✔
120	s.grow_to(mod_sw);	15,714,259✔
121
122	if(ws.size() < mod_sw) {	15,714,259✔
123	ws.resize(mod_sw);	×
124	}
125
126	const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);	15,714,259✔
127
128	// Conditionally add back the modulus
129	bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);	15,714,259✔
130
131	copy_mem(mutable_data(), ws.data(), mod_sw);	15,714,259✔
132
133	return (*this);	15,714,259✔
134	}
135
136	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	6,910,476✔
137	BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");	6,910,476✔
138	BOTAN_ARG_CHECK(y < 16, "y too large");	6,910,476✔
139
140	BOTAN_DEBUG_ASSERT(*this < mod);	6,910,476✔
141
142	this = static_cast<word>(y);	6,910,476✔
143	this->reduce_below(mod, ws);	6,910,476✔
144	return (*this);	6,910,476✔
145	}
146
147	BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {	×
148	BOTAN_UNUSED(ws);	×
149	BigInt y_bn;	×
150	y_bn.m_data.set_words(y, y_sw);	×
151	this = y_bn - this;	×
152	return (*this);	×
153	}	×
154
155	/*
156	* Multiplication Operator
157	*/
158	BigInt& BigInt::operator*=(const BigInt& y) {	526✔
159	secure_vector<word> ws;	526✔
160	return this->mul(y, ws);	526✔
161	}	526✔
162
163	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	8,565✔
164	const size_t x_sw = sig_words();	8,565✔
165	const size_t y_sw = y.sig_words();	8,565✔
166	set_sign((sign() == y.sign()) ? Positive : Negative);	8,635✔
167
168	if(x_sw == 0 \|\| y_sw == 0) {	8,565✔
169	clear();	35✔
170	set_sign(Positive);	35✔
171	} else if(x_sw == 1 && y_sw > 0) {	8,530✔
172	grow_to(y_sw + 1);	326✔
173	bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));	652✔
174	} else {
175	const size_t new_size = x_sw + y_sw + 1;	8,204✔
176	if(ws.size() < new_size) {	8,204✔
177	ws.resize(new_size);	8,204✔
178	}
179	secure_vector<word> z_reg(new_size);	8,204✔
180
181	bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());	8,204✔
182
183	this->swap_reg(z_reg);	8,204✔
184	}	8,204✔
185
186	return (*this);	8,565✔
187	}
188
189	BigInt& BigInt::square(secure_vector<word>& ws) {	9,060✔
190	const size_t sw = sig_words();	9,060✔
191
192	secure_vector<word> z(2 * sw);	9,060✔
193	ws.resize(z.size());	9,060✔
194
195	bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());	9,060✔
196
197	swap_reg(z);	9,060✔
198	set_sign(BigInt::Positive);	9,060✔
199
200	return (*this);	9,060✔
201	}	9,060✔
202
203	BigInt& BigInt::operator*=(word y) {	7,289,402✔
204	if(y == 0) {	7,289,402✔
205	clear();	×
206	set_sign(Positive);	×
207	}
208
209	const word carry = bigint_linmul2(mutable_data(), size(), y);	7,289,402✔
210	set_word_at(size(), carry);	7,289,402✔
211
212	return (*this);	7,289,402✔
213	}
214
215	/*
216	* Division Operator
217	*/
218	BigInt& BigInt::operator/=(const BigInt& y) {	932✔
219	if(y.sig_words() == 1 && is_positive() && y.is_positive() && is_power_of_2(y.word_at(0))) {	1,622✔
220	(*this) >>= (y.bits() - 1);	85✔
221	} else {
222	(this) = (this) / y;	847✔
223	}
224	return (*this);	932✔
225	}
226
227	/*
228	* Modulo Operator
229	*/
230	BigInt& BigInt::operator%=(const BigInt& mod) {	333,663✔
231	return (this = (this) % mod);	333,663✔
232	}
233
234	/*
235	* Modulo Operator
236	*/
237	word BigInt::operator%=(word mod) {	34✔
238	if(mod == 0) {	34✔
239	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
240	}
241
242	word remainder = 0;	34✔
243
244	if(is_power_of_2(mod)) {	34✔
245	remainder = (word_at(0) & (mod - 1));	10✔
246	} else {
247	const size_t sw = sig_words();	29✔
248	for(size_t i = sw; i > 0; --i) {	81✔
249	remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);	104✔
250	}
251	}
252
253	if(remainder != 0 && sign() == BigInt::Negative) {	34✔
254	remainder = mod - remainder;	13✔
255	}
256
257	m_data.set_to_zero();	34✔
258	m_data.set_word_at(0, remainder);	34✔
259	set_sign(BigInt::Positive);	34✔
260	return remainder;	34✔
261	}
262
263	/*
264	* Left Shift Operator
265	*/
266	BigInt& BigInt::operator<<=(size_t shift) {	12,187,333✔
267	const size_t sw = sig_words();	12,187,333✔
268	const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	12,187,333✔
269
270	m_data.grow_to(new_size);	12,187,333✔
271
272	bigint_shl1(m_data.mutable_data(), new_size, sw, shift);	12,187,333✔
273
274	return (*this);	12,187,333✔
275	}
276
277	/*
278	* Right Shift Operator
279	*/
280	BigInt& BigInt::operator>>=(size_t shift) {	7,561,891✔
281	bigint_shr1(m_data.mutable_data(), m_data.size(), shift);	7,561,891✔
282
283	if(is_negative() && is_zero()) {	7,657,531✔
284	set_sign(Positive);	8✔
285	}
286
287	return (*this);	7,561,891✔
288	}
289
290	} // namespace Botan

randombit / botan / 17281389884

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