5111374265

Committed 29 May 2023 11:19AM UTC coverage: 92.227% (+0.5%) from 91.723%

Build # 5111374265

Build Type

push

github

Committed by

randombit

Commit Message

Next release will be 3.1.0. Update release notes

Run Details

75588 of 81959 relevant lines covered (92.23%)

11886470.91 hits per line

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

90.82

/src/lib/math/bigint/big_ops3.cpp

/*
* BigInt Binary Operators
* (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/divide.h>
#include <botan/internal/mp_core.h>
#include <algorithm>

namespace Botan {

//static
BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_words, BigInt::Sign y_sign) {
   const size_t x_sw = x.sig_words();

   BigInt z = BigInt::with_capacity(std::max(x_sw, y_words) + 1);

   if(x.sign() == y_sign) {
      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
      z.set_sign(x.sign());
   } else {
      const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);

      //z.sign_fixup(relative_size, y_sign);
      if(relative_size < 0)
         z.set_sign(y_sign);
      else if(relative_size == 0)
         z.set_sign(BigInt::Positive);
      else
         z.set_sign(x.sign());
   }

   return z;
}

/*
* Multiplication Operator
*/
BigInt operator*(const BigInt& x, const BigInt& y) {
   const size_t x_sw = x.sig_words();
   const size_t y_sw = y.sig_words();

   BigInt z = BigInt::with_capacity(x.size() + y.size());

   if(x_sw == 1 && y_sw)
      bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
   else if(y_sw == 1 && x_sw)
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
   else if(x_sw && y_sw) {
      secure_vector<word> workspace(z.size());

      bigint_mul(z.mutable_data(),
                 z.size(),
                 x.data(),
                 x.size(),
                 x_sw,
                 y.data(),
                 y.size(),
                 y_sw,
                 workspace.data(),
                 workspace.size());
   }

   z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());

   return z;
}

/*
* Multiplication Operator
*/
BigInt operator*(const BigInt& x, word y) {
   const size_t x_sw = x.sig_words();

   BigInt z = BigInt::with_capacity(x_sw + 1);

   if(x_sw && y) {
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
      z.set_sign(x.sign());
   }

   return z;
}

/*
* Division Operator
*/
BigInt operator/(const BigInt& x, const BigInt& y) {
   if(y.sig_words() == 1) {
      return x / y.word_at(0);
   }

   BigInt q, r;
   vartime_divide(x, y, q, r);
   return q;
}

/*
* Division Operator
*/
BigInt operator/(const BigInt& x, word y) {
   if(y == 0)
      throw Invalid_Argument("BigInt::operator/ divide by zero");

   BigInt q;
   word r;
   ct_divide_word(x, y, q, r);
   return q;
}

/*
* Modulo Operator
*/
BigInt operator%(const BigInt& n, const BigInt& mod) {
   if(mod.is_zero())
      throw Invalid_Argument("BigInt::operator% divide by zero");
   if(mod.is_negative())
      throw Invalid_Argument("BigInt::operator% modulus must be > 0");
   if(n.is_positive() && mod.is_positive() && n < mod)
      return n;

   if(mod.sig_words() == 1) {
      return BigInt::from_word(n % mod.word_at(0));
   }

   BigInt q, r;
   vartime_divide(n, mod, q, r);
   return r;
}

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

   if(mod == 1)
      return 0;

   word remainder = 0;

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

   if(remainder && n.sign() == BigInt::Negative)
      return mod - remainder;
   return remainder;
}

/*
* Left Shift Operator
*/
BigInt operator<<(const BigInt& x, size_t shift) {
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS, shift_bits = shift % BOTAN_MP_WORD_BITS;

   const size_t x_sw = x.sig_words();

   BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0));
   bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
   y.set_sign(x.sign());
   return y;
}

/*
* Right Shift Operator
*/
BigInt operator>>(const BigInt& x, size_t shift) {
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
   const size_t x_sw = x.sig_words();

   if(shift_words >= x_sw)
      return BigInt::zero();

   BigInt y = BigInt::with_capacity(x_sw - shift_words);
   bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);

   if(x.is_negative() && y.is_zero())
      y.set_sign(BigInt::Positive);
   else
      y.set_sign(x.sign());

   return y;
}

}  // namespace Botan

1	/*
2	* BigInt Binary Operators
3	* (C) 1999-2007,2018 Jack Lloyd
4	* 2016 Matthias Gierlings
5	*
6	* Botan is released under the Simplified BSD License (see license.txt)
7	*/
8
9	#include <botan/bigint.h>
10
11	#include <botan/internal/bit_ops.h>
12	#include <botan/internal/divide.h>
13	#include <botan/internal/mp_core.h>
14	#include <algorithm>
15
16	namespace Botan {
17
18	//static
19	BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_words, BigInt::Sign y_sign) {	3,366,657✔
20	const size_t x_sw = x.sig_words();	3,366,657✔
21
22	BigInt z = BigInt::with_capacity(std::max(x_sw, y_words) + 1);	3,635,414✔
23
24	if(x.sign() == y_sign) {	3,366,657✔
25	bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);	2,420,208✔
26	z.set_sign(x.sign());	2,420,208✔
27	} else {
28	const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);	946,449✔
29
30	//z.sign_fixup(relative_size, y_sign);
31	if(relative_size < 0)	946,449✔
32	z.set_sign(y_sign);	332,873✔
33	else if(relative_size == 0)	613,576✔
34	z.set_sign(BigInt::Positive);	456✔
35	else
36	z.set_sign(x.sign());	613,120✔
37	}
38
39	return z;	3,366,657✔
40	}	×
41
42	/*
43	* Multiplication Operator
44	*/
45	BigInt operator*(const BigInt& x, const BigInt& y) {	2,778,114✔
46	const size_t x_sw = x.sig_words();	2,778,114✔
47	const size_t y_sw = y.sig_words();	2,778,114✔
48
49	BigInt z = BigInt::with_capacity(x.size() + y.size());	2,778,114✔
50
51	if(x_sw == 1 && y_sw)	2,778,114✔
52	bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));	3,878,818✔
53	else if(y_sw == 1 && x_sw)	838,705✔
54	bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));	626,010✔
55	else if(x_sw && y_sw) {	525,700✔
56	secure_vector<word> workspace(z.size());	483,705✔
57
58	bigint_mul(z.mutable_data(),	483,705✔
59	z.size(),
60	x.data(),
61	x.size(),
62	x_sw,
63	y.data(),
64	y.size(),
65	y_sw,
66	workspace.data(),
67	workspace.size());
68	}	483,705✔
69
70	z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());	4,799,195✔
71
72	return z;	2,778,114✔
73	}	×
74
75	/*
76	* Multiplication Operator
77	*/
78	BigInt operator*(const BigInt& x, word y) {	1,840,742✔
79	const size_t x_sw = x.sig_words();	1,840,742✔
80
81	BigInt z = BigInt::with_capacity(x_sw + 1);	1,840,742✔
82
83	if(x_sw && y) {	1,840,742✔
84	bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);	921,172✔
85	z.set_sign(x.sign());	921,172✔
86	}
87
88	return z;	1,840,742✔
89	}	×
90
91	/*
92	* Division Operator
93	*/
94	BigInt operator/(const BigInt& x, const BigInt& y) {	3,298✔
95	if(y.sig_words() == 1) {	5,752✔
96	return x / y.word_at(0);	5,004✔
97	}
98
99	BigInt q, r;	796✔
100	vartime_divide(x, y, q, r);	796✔
101	return q;	796✔
102	}	4,094✔
103
104	/*
105	* Division Operator
106	*/
107	BigInt operator/(const BigInt& x, word y) {	927,295✔
108	if(y == 0)	927,295✔
109	throw Invalid_Argument("BigInt::operator/ divide by zero");	×
110
111	BigInt q;	927,295✔
112	word r;	927,295✔
113	ct_divide_word(x, y, q, r);	927,295✔
114	return q;	927,295✔
115	}	×
116
117	/*
118	* Modulo Operator
119	*/
120	BigInt operator%(const BigInt& n, const BigInt& mod) {	1,126,076✔
121	if(mod.is_zero())	1,126,152✔
122	throw Invalid_Argument("BigInt::operator% divide by zero");	×
123	if(mod.is_negative())	1,126,076✔
124	throw Invalid_Argument("BigInt::operator% modulus must be > 0");	×
125	if(n.is_positive() && mod.is_positive() && n < mod)	2,221,252✔
126	return n;	188,876✔
127
128	if(mod.sig_words() == 1) {	937,200✔
129	return BigInt::from_word(n % mod.word_at(0));	575,806✔
130	}
131
132	BigInt q, r;	649,297✔
133	vartime_divide(n, mod, q, r);	649,297✔
134	return r;	649,297✔
135	}	1,775,373✔
136
137	/*
138	* Modulo Operator
139	*/
140	word operator%(const BigInt& n, word mod) {	2,658,443✔
141	if(mod == 0)	2,658,443✔
142	throw Invalid_Argument("BigInt::operator% divide by zero");	×
143
144	if(mod == 1)	2,658,443✔
145	return 0;
146
147	word remainder = 0;	2,658,279✔
148
149	if(is_power_of_2(mod)) {	2,658,279✔
150	remainder = (n.word_at(0) & (mod - 1));	3,951,846✔
151	} else {
152	const size_t sw = n.sig_words();	682,356✔
153	for(size_t i = sw; i > 0; --i) {	6,265,445✔
154	remainder = bigint_modop(remainder, n.word_at(i - 1), mod);	11,166,178✔
155	}
156	}
157
158	if(remainder && n.sign() == BigInt::Negative)	2,658,279✔
159	return mod - remainder;	29,968✔
160	return remainder;
161	}
162
163	/*
164	* Left Shift Operator
165	*/
166	BigInt operator<<(const BigInt& x, size_t shift) {	653,105✔
167	const size_t shift_words = shift / BOTAN_MP_WORD_BITS, shift_bits = shift % BOTAN_MP_WORD_BITS;	653,105✔
168
169	const size_t x_sw = x.sig_words();	653,105✔
170
171	BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0));	1,305,498✔
172	bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);	653,105✔
173	y.set_sign(x.sign());	653,105✔
174	return y;	653,105✔
175	}	×
176
177	/*
178	* Right Shift Operator
179	*/
180	BigInt operator>>(const BigInt& x, size_t shift) {	187,817✔
181	const size_t shift_words = shift / BOTAN_MP_WORD_BITS;	187,817✔
182	const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;	187,817✔
183	const size_t x_sw = x.sig_words();	187,817✔
184
185	if(shift_words >= x_sw)	187,817✔
186	return BigInt::zero();	2,062✔
187
188	BigInt y = BigInt::with_capacity(x_sw - shift_words);	185,755✔
189	bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);	185,755✔
190
191	if(x.is_negative() && y.is_zero())	185,780✔
192	y.set_sign(BigInt::Positive);	3✔
193	else
194	y.set_sign(x.sign());	185,752✔
195
196	return y;	185,755✔
197	}	187,817✔
198
199	} // namespace Botan

randombit / botan / 5111374265

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