20300409060

Committed 17 Dec 2025 10:55AM UTC coverage: 90.526% (+0.2%) from 90.36%

Build # 20300409060

Build Type

Pull #5167

github

Committed by

web-flow

Commit Message

Merge b37a2cfb3 into 3d96b675e

Pull Request Pull Request #5167: Changes to reduce unnecessary inclusions

Run Details

101175 of 111763 relevant lines covered (90.53%)

12570909.12 hits per line

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

90.3

/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>

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) {
      const 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 divide_precomp redc_mod(mod);
      const size_t sw = sig_words();
      for(size_t i = sw; i > 0; --i) {
         remainder = redc_mod.vartime_mod_2to1(remainder, word_at(i - 1));
      }
   }

   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
13	namespace Botan {
14
15	BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {	5,686,619✔
16	const size_t x_sw = sig_words();	5,686,619✔
17
18	grow_to(std::max(x_sw, y_words) + 1);	5,756,775✔
19
20	if(sign() == y_sign) {	5,686,619✔
21	const word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);	1,857,136✔
22	mutable_data()[size() - 1] += carry;	1,857,136✔
23	} else {
24	const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);	3,829,483✔
25
26	if(relative_size >= 0) {	3,829,483✔
27	// *this >= y
28	bigint_sub2(mutable_data(), x_sw, y, y_words);	3,770,842✔
29	} else {
30	// this < y: compute this = y - *this
31	bigint_sub2_rev(mutable_data(), y, y_words);	58,641✔
32	}
33
34	if(relative_size < 0) {	3,829,483✔
35	set_sign(y_sign);	58,641✔
36	} else if(relative_size == 0) {	3,770,842✔
37	set_sign(Positive);	3,210✔
38	}
39	}
40
41	return (*this);	5,686,619✔
42	}
43
44	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	970,748✔
45	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	970,748✔
46	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
47	}
48
49	BOTAN_DEBUG_ASSERT(*this < mod);	970,748✔
50	BOTAN_DEBUG_ASSERT(s < mod);	970,748✔
51
52	/*
53	t + s or t + s - p == t - (p - s)
54
55	So first compute ws = p - s
56
57	Then compute t + s and t - ws
58
59	If t - ws does not borrow, then that is the correct valued
60	*/
61
62	const size_t mod_sw = mod.sig_words();	970,748✔
63	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	970,748✔
64
65	this->grow_to(mod_sw);	970,748✔
66	s.grow_to(mod_sw);	970,748✔
67
68	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
69	if(ws.size() < 3 * mod_sw) {	970,748✔
70	ws.resize(3 * mod_sw);	616,771✔
71	}
72
73	// NOLINTBEGIN(readability-container-data-pointer)
74
75	word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);	970,748✔
76	BOTAN_DEBUG_ASSERT(borrow == 0);	970,748✔
77	BOTAN_UNUSED(borrow);	970,748✔
78
79	// Compute t - ws
80	borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);	970,748✔
81
82	// Compute t + s
83	bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);	970,748✔
84
85	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	970,748✔
86	set_words(&ws[0], mod_sw);	970,748✔
87
88	// NOLINTEND(readability-container-data-pointer)
89
90	return (*this);	970,748✔
91	}
92
93	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	15,720,374✔
94	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	15,720,374✔
95	throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");	×
96	}
97
98	// We are assuming in this function that *this and s are no more than mod_sw words long
99	BOTAN_DEBUG_ASSERT(*this < mod);	15,720,374✔
100	BOTAN_DEBUG_ASSERT(s < mod);	15,720,374✔
101
102	const size_t mod_sw = mod.sig_words();	15,720,374✔
103
104	this->grow_to(mod_sw);	15,720,374✔
105	s.grow_to(mod_sw);	15,720,374✔
106
107	if(ws.size() < mod_sw) {	15,720,374✔
108	ws.resize(mod_sw);	×
109	}
110
111	const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);	15,720,374✔
112
113	// Conditionally add back the modulus
114	bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);	15,720,374✔
115
116	copy_mem(mutable_data(), ws.data(), mod_sw);	15,720,374✔
117
118	return (*this);	15,720,374✔
119	}
120
121	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	6,910,152✔
122	BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");	6,910,152✔
123	BOTAN_ARG_CHECK(y < 16, "y too large");	6,910,152✔
124
125	BOTAN_DEBUG_ASSERT(*this < mod);	6,910,152✔
126
127	this = static_cast<word>(y);	6,910,152✔
128	this->reduce_below(mod, ws);	6,910,152✔
129	return (*this);	6,910,152✔
130	}
131
132	BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {	×
133	BOTAN_UNUSED(ws);	×
134	BigInt y_bn;	×
135	y_bn.m_data.set_words(y, y_sw);	×
136	this = y_bn - this;	×
137	return (*this);	×
138	}	×
139
140	/*
141	* Multiplication Operator
142	*/
143	BigInt& BigInt::operator*=(const BigInt& y) {	519✔
144	secure_vector<word> ws;	519✔
145	return this->mul(y, ws);	519✔
146	}	519✔
147
148	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	9,595✔
149	const size_t x_sw = sig_words();	9,595✔
150	const size_t y_sw = y.sig_words();	9,595✔
151	set_sign((sign() == y.sign()) ? Positive : Negative);	9,665✔
152
153	if(x_sw == 0 \|\| y_sw == 0) {	9,595✔
154	clear();	33✔
155	set_sign(Positive);	33✔
156	} else if(x_sw == 1 && y_sw > 0) {	9,562✔
157	grow_to(y_sw + 1);	321✔
158	bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));	642✔
159	} else {
160	const size_t new_size = x_sw + y_sw + 1;	9,241✔
161	if(ws.size() < new_size) {	9,241✔
162	ws.resize(new_size);	9,241✔
163	}
164	secure_vector<word> z_reg(new_size);	9,241✔
165
166	bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());	9,241✔
167
168	this->swap_reg(z_reg);	9,241✔
169	}	9,241✔
170
171	return (*this);	9,595✔
172	}
173
174	BigInt& BigInt::square(secure_vector<word>& ws) {	10,097✔
175	const size_t sw = sig_words();	10,097✔
176
177	secure_vector<word> z(2 * sw);	10,097✔
178	ws.resize(z.size());	10,097✔
179
180	bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());	10,097✔
181
182	swap_reg(z);	10,097✔
183	set_sign(BigInt::Positive);	10,097✔
184
185	return (*this);	10,097✔
186	}	10,097✔
187
188	BigInt& BigInt::operator*=(word y) {	7,289,084✔
189	if(y == 0) {	7,289,084✔
190	clear();	×
191	set_sign(Positive);	×
192	}
193
194	const word carry = bigint_linmul2(mutable_data(), size(), y);	7,289,084✔
195	set_word_at(size(), carry);	7,289,084✔
196
197	return (*this);	7,289,084✔
198	}
199
200	/*
201	* Division Operator
202	*/
203	BigInt& BigInt::operator/=(const BigInt& y) {	932✔
204	if(y.sig_words() == 1 && is_positive() && y.is_positive() && is_power_of_2(y.word_at(0))) {	1,622✔
205	(*this) >>= (y.bits() - 1);	85✔
206	} else {
207	(this) = (this) / y;	847✔
208	}
209	return (*this);	932✔
210	}
211
212	/*
213	* Modulo Operator
214	*/
215	BigInt& BigInt::operator%=(const BigInt& mod) {	334,262✔
216	return (this = (this) % mod);	334,262✔
217	}
218
219	/*
220	* Modulo Operator
221	*/
222	word BigInt::operator%=(word mod) {	34✔
223	if(mod == 0) {	34✔
224	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
225	}
226
227	word remainder = 0;	34✔
228
229	if(is_power_of_2(mod)) {	34✔
230	remainder = (word_at(0) & (mod - 1));	10✔
231	} else {
232	const divide_precomp redc_mod(mod);	29✔
233	const size_t sw = sig_words();	29✔
234	for(size_t i = sw; i > 0; --i) {	81✔
235	remainder = redc_mod.vartime_mod_2to1(remainder, word_at(i - 1));	104✔
236	}
237	}
238
239	if(remainder != 0 && sign() == BigInt::Negative) {	34✔
240	remainder = mod - remainder;	13✔
241	}
242
243	m_data.set_to_zero();	34✔
244	m_data.set_word_at(0, remainder);	34✔
245	set_sign(BigInt::Positive);	34✔
246	return remainder;	34✔
247	}
248
249	/*
250	* Left Shift Operator
251	*/
252	BigInt& BigInt::operator<<=(size_t shift) {	12,254,522✔
253	const size_t sw = sig_words();	12,254,522✔
254	const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	12,254,522✔
255
256	m_data.grow_to(new_size);	12,254,522✔
257
258	bigint_shl1(m_data.mutable_data(), new_size, sw, shift);	12,254,522✔
259
260	return (*this);	12,254,522✔
261	}
262
263	/*
264	* Right Shift Operator
265	*/
266	BigInt& BigInt::operator>>=(size_t shift) {	7,815,352✔
267	bigint_shr1(m_data.mutable_data(), m_data.size(), shift);	7,815,352✔
268
269	if(is_negative() && is_zero()) {	7,908,840✔
270	set_sign(Positive);	8✔
271	}
272
273	return (*this);	7,815,352✔
274	}
275
276	} // namespace Botan

randombit / botan / 20300409060

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