randombit/botan | Build 5111374265 | source/src/lib/math/bigint/big_ops2.cpp | Coveralls

16

BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {

11,827,711✔

17

   const size_t x_sw = sig_words();

11,827,711✔

19

   grow_to(std::max(x_sw, y_words) + 1);

20,182,689✔

21

   if(sign() == y_sign) {

11,827,711✔

22

      bigint_add2(mutable_data(), size() - 1, y, y_words);

10,794,152✔

24

      const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);

1,033,559✔

26

      if(relative_size >= 0) {

1,033,559✔

28

         bigint_sub2(mutable_data(), x_sw, y, y_words);

969,425✔

31

         bigint_sub2_rev(mutable_data(), y, y_words);

64,134✔

35

      if(relative_size < 0)

1,033,559✔

36

         set_sign(y_sign);

64,134✔

37

      else if(relative_size == 0)

969,425✔

38

         set_sign(Positive);

310✔

41

   return (*this);

11,827,711✔

44

BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {

5,986,950✔

45

   if(this->is_negative() || s.is_negative() || mod.is_negative())

5,986,950✔

48

   BOTAN_DEBUG_ASSERT(*this < mod);

5,986,950✔

49

   BOTAN_DEBUG_ASSERT(s < mod);

5,986,950✔

61

   const size_t mod_sw = mod.sig_words();

5,986,950✔

62

   BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");

5,986,950✔

64

   this->grow_to(mod_sw);

5,986,950✔

65

   s.grow_to(mod_sw);

5,986,950✔

68

   if(ws.size() < 3 * mod_sw)

5,986,950✔

69

      ws.resize(3 * mod_sw);

3,695,809✔

71

   word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);

5,986,950✔

72

   BOTAN_DEBUG_ASSERT(borrow == 0);

5,986,950✔

73

   BOTAN_UNUSED(borrow);

5,986,950✔

76

   borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);

5,986,950✔

79

   bigint_add3_nc(&ws[mod_sw * 2], this->data(), mod_sw, s.data(), mod_sw);

5,986,950✔

81

   CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);

5,986,950✔

82

   set_words(&ws[0], mod_sw);

5,986,950✔

84

   return (*this);

5,986,950✔

87

BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {

54,867,977✔

88

   if(this->is_negative() || s.is_negative() || mod.is_negative())

54,867,977✔

92

   BOTAN_DEBUG_ASSERT(*this < mod);

54,867,977✔

93

   BOTAN_DEBUG_ASSERT(s < mod);

54,867,977✔

95

   const size_t mod_sw = mod.sig_words();

54,867,977✔

97

   this->grow_to(mod_sw);

54,867,977✔

98

   s.grow_to(mod_sw);

54,867,977✔

100

   if(ws.size() < mod_sw)

54,867,977✔

103

   if(mod_sw == 4)

54,867,977✔

104

      bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());

24,239,790✔

105

   else if(mod_sw == 6)

30,628,187✔

106

      bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());

16,030,679✔

108

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

14,597,508✔

110

   return (*this);

54,867,977✔

113

BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {

24,432,960✔

114

   BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");

24,432,960✔

115

   BOTAN_ARG_CHECK(y < 16, "y too large");

24,432,960✔

117

   BOTAN_DEBUG_ASSERT(*this < mod);

24,432,960✔

119

   *this *= static_cast<word>(y);

24,432,960✔

120

   this->reduce_below(mod, ws);

24,432,960✔

121

   return (*this);

24,432,960✔

124

BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {

8,337,499✔

125

   if(this->sign() != BigInt::Positive)

8,337,499✔

128

   const size_t x_sw = this->sig_words();

8,337,499✔

130

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

11,199,034✔

131

   clear_mem(ws.data(), ws.size());

8,337,499✔

133

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

8,337,499✔

135

   this->cond_flip_sign(relative_size > 0);

8,337,499✔

136

   this->swap_reg(ws);

8,337,499✔

138

   return (*this);

8,337,499✔

144

BigInt& BigInt::operator*=(const BigInt& y) {

614✔

145

   secure_vector<word> ws;

614✔

146

   return this->mul(y, ws);

614✔

147

614✔

149

BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {

16,680,123✔

150

   const size_t x_sw = sig_words();

16,680,123✔

151

   const size_t y_sw = y.sig_words();

16,680,123✔

152

   set_sign((sign() == y.sign()) ? Positive : Negative);

16,680,193✔

154

   if(x_sw == 0 || y_sw == 0) {

16,680,123✔

155

      clear();

2,796,628✔

156

      set_sign(Positive);

2,796,628✔

157

   } else if(x_sw == 1 && y_sw) {

13,883,495✔

158

      grow_to(y_sw + 1);

8,878,406✔

159

      bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));

17,756,812✔

160

   } else if(y_sw == 1 && x_sw) {

5,005,089✔

161

      word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));

52✔

162

      set_word_at(x_sw, carry);

26✔

164

      const size_t new_size = x_sw + y_sw + 1;

5,005,063✔

165

      ws.resize(new_size);

5,005,063✔

166

      secure_vector<word> z_reg(new_size);

5,005,063✔

168

      bigint_mul(z_reg.data(), z_reg.size(), data(), size(), x_sw, y.data(), y.size(), y_sw, ws.data(), ws.size());

5,005,063✔

170

      this->swap_reg(z_reg);

5,005,063✔

171

5,005,063✔

173

   return (*this);

16,680,123✔

176

BigInt& BigInt::square(secure_vector<word>& ws) {

2,955,589✔

177

   const size_t sw = sig_words();

2,955,589✔

179

   secure_vector<word> z(2 * sw);

2,955,589✔

180

   ws.resize(z.size());

2,955,589✔

182

   bigint_sqr(z.data(), z.size(), data(), size(), sw, ws.data(), ws.size());

2,955,589✔

184

   swap_reg(z);

2,955,589✔

185

   set_sign(BigInt::Positive);

2,955,589✔

187

   return (*this);

2,955,589✔

188

2,955,589✔

190

BigInt& BigInt::operator*=(word y) {

169,735,992✔

191

   if(y == 0) {

169,735,992✔

196

   const word carry = bigint_linmul2(mutable_data(), size(), y);

169,735,992✔

197

   set_word_at(size(), carry);

169,735,992✔

199

   return (*this);

169,735,992✔

205

BigInt& BigInt::operator/=(const BigInt& y) {

929✔

206

   if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))

1,622✔

207

      (*this) >>= (y.bits() - 1);

85✔

209

      (*this) = (*this) / y;

1,688✔

210

   return (*this);

929✔

216

BigInt& BigInt::operator%=(const BigInt& mod) { return (*this = (*this) % mod); }

924,615✔

221

word BigInt::operator%=(word mod) {

30✔

222

   if(mod == 0)

30✔

225

   word remainder = 0;

30✔

227

   if(is_power_of_2(mod)) {

30✔

228

      remainder = (word_at(0) & (mod - 1));

8✔

230

      const size_t sw = sig_words();

26✔

231

      for(size_t i = sw; i > 0; --i)

75✔

232

         remainder = bigint_modop(remainder, word_at(i - 1), mod);

98✔

235

   if(remainder && sign() == BigInt::Negative)

30✔

236

      remainder = mod - remainder;

12✔

238

   m_data.set_to_zero();

30✔

239

   m_data.set_word_at(0, remainder);

30✔

240

   set_sign(BigInt::Positive);

30✔

241

   return remainder;

30✔

247

BigInt& BigInt::operator<<=(size_t shift) {

1,733,794✔

248

   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;

1,733,794✔

249

   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;

1,733,794✔

250

   const size_t size = sig_words();

1,733,794✔

252

   const size_t bits_free = top_bits_free();

1,733,794✔

254

   const size_t new_size = size + shift_words + (bits_free < shift_bits);

1,733,794✔

256

   m_data.grow_to(new_size);

1,733,794✔

258

   bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);

1,733,794✔

260

   return (*this);

1,733,794✔

266

BigInt& BigInt::operator>>=(size_t shift) {

27,360,451✔

267

   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;

27,360,451✔

268

   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;

27,360,451✔

270

   bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);

27,360,451✔

272

   if(is_negative() && is_zero())

27,456,141✔

273

      set_sign(Positive);

8✔

275

   return (*this);

27,360,451✔

randombit / botan / 5111374265

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

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