16434247345

Committed 22 Jul 2025 12:16AM UTC coverage: 90.698% (+0.003%) from 90.695%

Build # 16434247345

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5010 from randombit/jack/monty-not-bigint

Modify Montygomery_Int to not store the value as a BigInt

Run Details

99972 of 110225 relevant lines covered (90.7%)

12208720.94 hits per line

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

88.24

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

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

   // 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_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);

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

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

randombit / botan / 16434247345

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