15513462830

Committed 08 Jun 2025 01:16AM UTC coverage: 90.563% (+0.006%) from 90.557%

Build # 15513462830

Build Type

Pull #4255

github

Committed by

web-flow

Commit Message

Merge 7a5af0998 into 595e05267

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

Run Details

98873 of 109176 relevant lines covered (90.56%)

12459353.84 hits per line

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

88.97

/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) {
      bigint_add2(mutable_data(), size() - 1, y, y_words);
   } 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
         bigint_sub2_rev(mutable_data(), y, y_words);
      }

      //this->sign_fixup(relative_size, y_sign);
      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);
   }

   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_nc(&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);

   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);
   }

   bigint_mod_sub(mutable_data(), s._data(), mod._data(), mod_sw, ws.data());

   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) {
   if(this->sign() != BigInt::Positive) {
      throw Invalid_State("BigInt::sub_rev requires this is positive");
   }

   const size_t x_sw = this->sig_words();

   ws.resize(std::max(x_sw, y_sw));
   clear_mem(ws.data(), ws.size());

   const int32_t relative_size = bigint_sub_abs(ws.data(), _data(), x_sw, y, y_sw);

   this->cond_flip_sign(relative_size > 0);
   this->swap_reg(ws);

   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) {
      grow_to(y_sw + 1);
      bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
   } else if(y_sw == 1 && x_sw) {
      word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
      set_word_at(x_sw, carry);
   } 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 && 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,453,617✔
31	const size_t x_sw = sig_words();	5,453,617✔
32
33	grow_to(std::max(x_sw, y_words) + 1);	5,524,452✔
34
35	if(sign() == y_sign) {	5,453,617✔
36	bigint_add2(mutable_data(), size() - 1, y, y_words);	1,835,957✔
37	} else {
38	const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);	3,617,660✔
39
40	if(relative_size >= 0) {	3,617,660✔
41	// *this >= y
42	bigint_sub2(mutable_data(), x_sw, y, y_words);	3,555,841✔
43	} else {
44	// *this < y
45	bigint_sub2_rev(mutable_data(), y, y_words);	61,819✔
46	}
47
48	//this->sign_fixup(relative_size, y_sign);
49	if(relative_size < 0) {	3,617,660✔
50	set_sign(y_sign);	61,819✔
51	} else if(relative_size == 0) {	3,555,841✔
52	set_sign(Positive);	53,162✔
53	}
54	}
55
56	return (*this);	5,453,617✔
57	}
58
59	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	1,117,340✔
60	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	1,117,340✔
61	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
62	}
63
64	BOTAN_DEBUG_ASSERT(*this < mod);	1,117,340✔
65	BOTAN_DEBUG_ASSERT(s < mod);	1,117,340✔
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,117,340✔
78	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	1,117,340✔
79
80	this->grow_to(mod_sw);	1,117,340✔
81	s.grow_to(mod_sw);	1,117,340✔
82
83	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
84	if(ws.size() < 3 * mod_sw) {	1,117,340✔
85	ws.resize(3 * mod_sw);	616,901✔
86	}
87
88	word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);	1,117,340✔
89	BOTAN_DEBUG_ASSERT(borrow == 0);	1,117,340✔
90	BOTAN_UNUSED(borrow);	1,117,340✔
91
92	// Compute t - ws
93	borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);	1,117,340✔
94
95	// Compute t + s
96	bigint_add3_nc(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);	1,117,340✔
97
98	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	1,117,340✔
99	set_words(&ws[0], mod_sw);	1,117,340✔
100
101	return (*this);	1,117,340✔
102	}
103
104	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	15,863,375✔
105	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	15,863,375✔
106	throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");	×
107	}
108
109	// We are assuming in this function that *this and s are no more than mod_sw words long
110	BOTAN_DEBUG_ASSERT(*this < mod);	15,863,375✔
111	BOTAN_DEBUG_ASSERT(s < mod);	15,863,375✔
112
113	const size_t mod_sw = mod.sig_words();	15,863,375✔
114
115	this->grow_to(mod_sw);	15,863,375✔
116	s.grow_to(mod_sw);	15,863,375✔
117
118	if(ws.size() < mod_sw) {	15,863,375✔
119	ws.resize(mod_sw);	6,007✔
120	}
121
122	bigint_mod_sub(mutable_data(), s._data(), mod._data(), mod_sw, ws.data());	15,863,375✔
123
124	return (*this);	15,863,375✔
125	}
126
127	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	6,907,060✔
128	BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");	6,907,060✔
129	BOTAN_ARG_CHECK(y < 16, "y too large");	6,907,060✔
130
131	BOTAN_DEBUG_ASSERT(*this < mod);	6,907,060✔
132
133	this = static_cast<word>(y);	6,907,060✔
134	this->reduce_below(mod, ws);	6,907,060✔
135	return (*this);	6,907,060✔
136	}
137
138	BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {	×
139	if(this->sign() != BigInt::Positive) {	×
140	throw Invalid_State("BigInt::sub_rev requires this is positive");	×
141	}
142
143	const size_t x_sw = this->sig_words();	×
144
145	ws.resize(std::max(x_sw, y_sw));	×
146	clear_mem(ws.data(), ws.size());	×
147
148	const int32_t relative_size = bigint_sub_abs(ws.data(), _data(), x_sw, y, y_sw);	×
149
150	this->cond_flip_sign(relative_size > 0);	×
151	this->swap_reg(ws);	×
152
153	return (*this);	×
154	}
155
156	/*
157	* Multiplication Operator
158	*/
159	BigInt& BigInt::operator*=(const BigInt& y) {	535✔
160	secure_vector<word> ws;	535✔
161	return this->mul(y, ws);	535✔
162	}	535✔
163
164	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	9,795✔
165	const size_t x_sw = sig_words();	9,795✔
166	const size_t y_sw = y.sig_words();	9,795✔
167	set_sign((sign() == y.sign()) ? Positive : Negative);	9,865✔
168
169	if(x_sw == 0 \|\| y_sw == 0) {	9,795✔
170	clear();	32✔
171	set_sign(Positive);	32✔
172	} else if(x_sw == 1 && y_sw) {	9,763✔
173	grow_to(y_sw + 1);	338✔
174	bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));	676✔
175	} else if(y_sw == 1 && x_sw) {	9,425✔
176	word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));	42✔
177	set_word_at(x_sw, carry);	21✔
178	} else {
179	const size_t new_size = x_sw + y_sw + 1;	9,404✔
180	if(ws.size() < new_size) {	9,404✔
181	ws.resize(new_size);	9,404✔
182	}
183	secure_vector<word> z_reg(new_size);	9,404✔
184
185	bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());	9,404✔
186
187	this->swap_reg(z_reg);	9,404✔
188	}	9,404✔
189
190	return (*this);	9,795✔
191	}
192
193	BigInt& BigInt::square(secure_vector<word>& ws) {	10,281✔
194	const size_t sw = sig_words();	10,281✔
195
196	secure_vector<word> z(2 * sw);	10,281✔
197	ws.resize(z.size());	10,281✔
198
199	bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());	10,281✔
200
201	swap_reg(z);	10,281✔
202	set_sign(BigInt::Positive);	10,281✔
203
204	return (*this);	10,281✔
205	}	10,281✔
206
207	BigInt& BigInt::operator*=(word y) {	7,286,187✔
208	if(y == 0) {	7,286,187✔
209	clear();	×
210	set_sign(Positive);	×
211	}
212
213	const word carry = bigint_linmul2(mutable_data(), size(), y);	7,286,187✔
214	set_word_at(size(), carry);	7,286,187✔
215
216	return (*this);	7,286,187✔
217	}
218
219	/*
220	* Division Operator
221	*/
222	BigInt& BigInt::operator/=(const BigInt& y) {	929✔
223	if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) {	1,622✔
224	(*this) >>= (y.bits() - 1);	85✔
225	} else {
226	(this) = (this) / y;	844✔
227	}
228	return (*this);	929✔
229	}
230
231	/*
232	* Modulo Operator
233	*/
234	BigInt& BigInt::operator%=(const BigInt& mod) {	328,119✔
235	return (this = (this) % mod);	328,119✔
236	}
237
238	/*
239	* Modulo Operator
240	*/
241	word BigInt::operator%=(word mod) {	33✔
242	if(mod == 0) {	33✔
243	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
244	}
245
246	word remainder = 0;	33✔
247
248	if(is_power_of_2(mod)) {	33✔
249	remainder = (word_at(0) & (mod - 1));	10✔
250	} else {
251	const size_t sw = sig_words();	28✔
252	for(size_t i = sw; i > 0; --i) {	79✔
253	remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);	102✔
254	}
255	}
256
257	if(remainder && sign() == BigInt::Negative) {	33✔
258	remainder = mod - remainder;	12✔
259	}
260
261	m_data.set_to_zero();	33✔
262	m_data.set_word_at(0, remainder);	33✔
263	set_sign(BigInt::Positive);	33✔
264	return remainder;	33✔
265	}
266
267	/*
268	* Left Shift Operator
269	*/
270	BigInt& BigInt::operator<<=(size_t shift) {	12,169,840✔
271	const size_t sw = sig_words();	12,169,840✔
272	const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	12,169,840✔
273
274	m_data.grow_to(new_size);	12,169,840✔
275
276	bigint_shl1(m_data.mutable_data(), new_size, sw, shift);	12,169,840✔
277
278	return (*this);	12,169,840✔
279	}
280
281	/*
282	* Right Shift Operator
283	*/
284	BigInt& BigInt::operator>>=(size_t shift) {	7,388,402✔
285	bigint_shr1(m_data.mutable_data(), m_data.size(), shift);	7,388,402✔
286
287	if(is_negative() && is_zero()) {	7,487,982✔
288	set_sign(Positive);	8✔
289	}
290
291	return (*this);	7,388,402✔
292	}
293
294	} // namespace Botan

randombit / botan / 15513462830

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