16788529396

Committed 06 Aug 2025 09:04PM UTC coverage: 90.677%. Remained the same

Build # 16788529396

Build Type

Pull #4255

github

Committed by

web-flow

Commit Message

Merge 09544fbc3 into 1f9987555

Pull Request Pull Request #4255: Add support for building with clang-cl

Run Details

99983 of 110263 relevant lines covered (90.68%)

24310874.08 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_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) {	11,193,833✔
31	const size_t x_sw = sig_words();	11,193,833✔
32
33	grow_to(std::max(x_sw, y_words) + 1);	11,335,153✔
34
35	if(sign() == y_sign) {	11,193,833✔
36	word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);	3,951,345✔
37	mutable_data()[size() - 1] += carry;	3,951,345✔
38	} else {
39	const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);	7,242,488✔
40
41	if(relative_size >= 0) {	7,242,488✔
42	// *this >= y
43	bigint_sub2(mutable_data(), x_sw, y, y_words);	7,117,245✔
44	} else {
45	// this < y: compute this = y - *this
46	bigint_sub2_rev(mutable_data(), y, y_words);	125,243✔
47	}
48
49	if(relative_size < 0) {	7,242,488✔
50	set_sign(y_sign);	125,243✔
51	} else if(relative_size == 0) {	7,117,245✔
52	set_sign(Positive);	106,293✔
53	}
54	}
55
56	return (*this);	11,193,833✔
57	}
58
59	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	1,941,911✔
60	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	1,941,911✔
61	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
62	}
63
64	BOTAN_DEBUG_ASSERT(*this < mod);	1,941,911✔
65	BOTAN_DEBUG_ASSERT(s < mod);	1,941,911✔
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();	1,941,911✔
78	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	1,941,911✔
79
80	this->grow_to(mod_sw);	1,941,911✔
81	s.grow_to(mod_sw);	1,941,911✔
82
83	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
84	if(ws.size() < 3 * mod_sw) {	1,941,911✔
85	ws.resize(3 * mod_sw);	1,231,589✔
86	}
87
88	// NOLINTBEGIN(readability-container-data-pointer)
89
90	word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);	1,941,911✔
91	BOTAN_DEBUG_ASSERT(borrow == 0);	1,941,911✔
92	BOTAN_UNUSED(borrow);	1,941,911✔
93
94	// Compute t - ws
95	borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);	1,941,911✔
96
97	// Compute t + s
98	bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);	1,941,911✔
99
100	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	1,941,911✔
101	set_words(&ws[0], mod_sw);	1,941,911✔
102
103	// NOLINTEND(readability-container-data-pointer)
104
105	return (*this);	1,941,911✔
106	}
107
108	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	31,436,170✔
109	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	31,436,170✔
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);	31,436,170✔
115	BOTAN_DEBUG_ASSERT(s < mod);	31,436,170✔
116
117	const size_t mod_sw = mod.sig_words();	31,436,170✔
118
119	this->grow_to(mod_sw);	31,436,170✔
120	s.grow_to(mod_sw);	31,436,170✔
121
122	if(ws.size() < mod_sw) {	31,436,170✔
123	ws.resize(mod_sw);	×
124	}
125
126	const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);	31,436,170✔
127
128	// Conditionally add back the modulus
129	bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);	31,436,170✔
130
131	copy_mem(mutable_data(), ws.data(), mod_sw);	31,436,170✔
132
133	return (*this);	31,436,170✔
134	}
135
136	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	13,821,456✔
137	BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");	13,821,456✔
138	BOTAN_ARG_CHECK(y < 16, "y too large");	13,821,456✔
139
140	BOTAN_DEBUG_ASSERT(*this < mod);	13,821,456✔
141
142	this = static_cast<word>(y);	13,821,456✔
143	this->reduce_below(mod, ws);	13,821,456✔
144	return (*this);	13,821,456✔
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) {	1,049✔
159	secure_vector<word> ws;	1,049✔
160	return this->mul(y, ws);	1,049✔
161	}	1,049✔
162
163	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	19,352✔
164	const size_t x_sw = sig_words();	19,352✔
165	const size_t y_sw = y.sig_words();	19,352✔
166	set_sign((sign() == y.sign()) ? Positive : Negative);	19,492✔
167
168	if(x_sw == 0 \|\| y_sw == 0) {	19,352✔
169	clear();	65✔
170	set_sign(Positive);	65✔
171	} else if(x_sw == 1 && y_sw > 0) {	19,287✔
172	grow_to(y_sw + 1);	654✔
173	bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));	1,308✔
174	} else {
175	const size_t new_size = x_sw + y_sw + 1;	18,633✔
176	if(ws.size() < new_size) {	18,633✔
177	ws.resize(new_size);	18,633✔
178	}
179	secure_vector<word> z_reg(new_size);	18,633✔
180
181	bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());	18,633✔
182
183	this->swap_reg(z_reg);	18,633✔
184	}	18,633✔
185
186	return (*this);	19,352✔
187	}
188
189	BigInt& BigInt::square(secure_vector<word>& ws) {	20,345✔
190	const size_t sw = sig_words();	20,345✔
191
192	secure_vector<word> z(2 * sw);	20,345✔
193	ws.resize(z.size());	20,345✔
194
195	bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());	20,345✔
196
197	swap_reg(z);	20,345✔
198	set_sign(BigInt::Positive);	20,345✔
199
200	return (*this);	20,345✔
201	}	20,345✔
202
203	BigInt& BigInt::operator*=(word y) {	14,579,713✔
204	if(y == 0) {	14,579,713✔
205	clear();	×
206	set_sign(Positive);	×
207	}
208
209	const word carry = bigint_linmul2(mutable_data(), size(), y);	14,579,713✔
210	set_word_at(size(), carry);	14,579,713✔
211
212	return (*this);	14,579,713✔
213	}
214
215	/*
216	* Division Operator
217	*/
218	BigInt& BigInt::operator/=(const BigInt& y) {	1,858✔
219	if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) {	3,240✔
220	(*this) >>= (y.bits() - 1);	170✔
221	} else {
222	(this) = (this) / y;	1,688✔
223	}
224	return (*this);	1,858✔
225	}
226
227	/*
228	* Modulo Operator
229	*/
230	BigInt& BigInt::operator%=(const BigInt& mod) {	652,420✔
231	return (this = (this) % mod);	652,420✔
232	}
233
234	/*
235	* Modulo Operator
236	*/
237	word BigInt::operator%=(word mod) {	66✔
238	if(mod == 0) {	66✔
239	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
240	}
241
242	word remainder = 0;	66✔
243
244	if(is_power_of_2(mod)) {	66✔
245	remainder = (word_at(0) & (mod - 1));	20✔
246	} else {
247	const size_t sw = sig_words();	56✔
248	for(size_t i = sw; i > 0; --i) {	158✔
249	remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);	204✔
250	}
251	}
252
253	if(remainder != 0 && sign() == BigInt::Negative) {	66✔
254	remainder = mod - remainder;	24✔
255	}
256
257	m_data.set_to_zero();	66✔
258	m_data.set_word_at(0, remainder);	66✔
259	set_sign(BigInt::Positive);	66✔
260	return remainder;	66✔
261	}
262
263	/*
264	* Left Shift Operator
265	*/
266	BigInt& BigInt::operator<<=(size_t shift) {	24,295,522✔
267	const size_t sw = sig_words();	24,295,522✔
268	const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	24,295,522✔
269
270	m_data.grow_to(new_size);	24,295,522✔
271
272	bigint_shl1(m_data.mutable_data(), new_size, sw, shift);	24,295,522✔
273
274	return (*this);	24,295,522✔
275	}
276
277	/*
278	* Right Shift Operator
279	*/
280	BigInt& BigInt::operator>>=(size_t shift) {	15,132,497✔
281	bigint_shr1(m_data.mutable_data(), m_data.size(), shift);	15,132,497✔
282
283	if(is_negative() && is_zero()) {	15,331,108✔
284	set_sign(Positive);	16✔
285	}
286
287	return (*this);	15,132,497✔
288	}
289
290	} // namespace Botan

randombit / botan / 16788529396

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