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

16

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

12,174,135✔

17

   const size_t x_sw = sig_words();

12,174,135✔

19

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

20,788,151✔

21

   if(sign() == y_sign) {

12,174,135✔

22

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

11,119,286✔

24

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

1,054,849✔

26

      if(relative_size >= 0) {

1,054,849✔

28

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

987,324✔

31

         bigint_sub2_rev(mutable_data(), y, y_words);

67,525✔

35

      if(relative_size < 0) {

1,054,849✔

36

         set_sign(y_sign);

67,525✔

37

      } else if(relative_size == 0) {

987,324✔

38

         set_sign(Positive);

309✔

42

   return (*this);

12,174,135✔

45

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

6,212,171✔

46

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

6,212,171✔

50

   BOTAN_DEBUG_ASSERT(*this < mod);

6,212,171✔

51

   BOTAN_DEBUG_ASSERT(s < mod);

6,212,171✔

63

   const size_t mod_sw = mod.sig_words();

6,212,171✔

64

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

6,212,171✔

66

   this->grow_to(mod_sw);

6,212,171✔

67

   s.grow_to(mod_sw);

6,212,171✔

70

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

6,212,171✔

71

      ws.resize(3 * mod_sw);

3,866,822✔

74

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

6,212,171✔

75

   BOTAN_DEBUG_ASSERT(borrow == 0);

6,212,171✔

76

   BOTAN_UNUSED(borrow);

6,212,171✔

79

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

6,212,171✔

82

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

6,212,171✔

84

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

6,212,171✔

85

   set_words(&ws[0], mod_sw);

6,212,171✔

87

   return (*this);

6,212,171✔

90

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

58,544,776✔

91

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

58,544,776✔

96

   BOTAN_DEBUG_ASSERT(*this < mod);

58,544,776✔

97

   BOTAN_DEBUG_ASSERT(s < mod);

58,544,776✔

99

   const size_t mod_sw = mod.sig_words();

58,544,776✔

101

   this->grow_to(mod_sw);

58,544,776✔

102

   s.grow_to(mod_sw);

58,544,776✔

104

   if(ws.size() < mod_sw) {

58,544,776✔

108

   if(mod_sw == 4) {

58,544,776✔

109

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

24,932,830✔

110

   } else if(mod_sw == 6) {

33,611,946✔

111

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

16,399,575✔

113

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

17,212,371✔

116

   return (*this);

58,544,776✔

119

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

25,511,312✔

120

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

25,511,312✔

121

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

25,511,312✔

123

   BOTAN_DEBUG_ASSERT(*this < mod);

25,511,312✔

125

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

25,511,312✔

126

   this->reduce_below(mod, ws);

25,511,312✔

127

   return (*this);

25,511,312✔

130

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

8,595,971✔

131

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

8,595,971✔

135

   const size_t x_sw = this->sig_words();

8,595,971✔

137

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

11,504,813✔

138

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

8,595,971✔

140

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

8,595,971✔

142

   this->cond_flip_sign(relative_size > 0);

8,595,971✔

143

   this->swap_reg(ws);

8,595,971✔

145

   return (*this);

8,595,971✔

151

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

617✔

152

   secure_vector<word> ws;

617✔

153

   return this->mul(y, ws);

617✔

154

617✔

156

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

17,196,692✔

157

   const size_t x_sw = sig_words();

17,196,692✔

158

   const size_t y_sw = y.sig_words();

17,196,692✔

159

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

17,196,762✔

161

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

17,196,692✔

162

      clear();

2,831,720✔

163

      set_sign(Positive);

2,831,720✔

164

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

14,364,972✔

165

      grow_to(y_sw + 1);

8,957,974✔

166

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

17,915,948✔

167

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

5,406,998✔

168

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

52✔

169

      set_word_at(x_sw, carry);

26✔

171

      const size_t new_size = x_sw + y_sw + 1;

5,406,972✔

172

      ws.resize(new_size);

5,406,972✔

173

      secure_vector<word> z_reg(new_size);

5,406,972✔

175

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

5,406,972✔

177

      this->swap_reg(z_reg);

5,406,972✔

178

5,406,972✔

180

   return (*this);

17,196,692✔

183

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

3,115,889✔

184

   const size_t sw = sig_words();

3,115,889✔

186

   secure_vector<word> z(2 * sw);

3,115,889✔

187

   ws.resize(z.size());

3,115,889✔

189

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

3,115,889✔

191

   swap_reg(z);

3,115,889✔

192

   set_sign(BigInt::Positive);

3,115,889✔

194

   return (*this);

3,115,889✔

195

3,115,889✔

197

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

168,617,024✔

198

   if(y == 0) {

168,617,024✔

203

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

168,617,024✔

204

   set_word_at(size(), carry);

168,617,024✔

206

   return (*this);

168,617,024✔

212

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

929✔

213

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

1,622✔

214

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

85✔

216

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

1,688✔

218

   return (*this);

929✔

224

BigInt& BigInt::operator%=(const BigInt& mod) {

942,154✔

225

   return (*this = (*this) % mod);

942,154✔

231

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

30✔

232

   if(mod == 0) {

30✔

236

   word remainder = 0;

30✔

238

   if(is_power_of_2(mod)) {

30✔

239

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

8✔

241

      const size_t sw = sig_words();

26✔

242

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

75✔

243

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

98✔

247

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

30✔

248

      remainder = mod - remainder;

12✔

251

   m_data.set_to_zero();

30✔

252

   m_data.set_word_at(0, remainder);

30✔

253

   set_sign(BigInt::Positive);

30✔

254

   return remainder;

30✔

260

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

1,759,788✔

261

   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;

1,759,788✔

262

   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;

1,759,788✔

263

   const size_t size = sig_words();

1,759,788✔

265

   const size_t bits_free = top_bits_free();

1,759,788✔

267

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

1,759,788✔

269

   m_data.grow_to(new_size);

1,759,788✔

271

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

1,759,788✔

273

   return (*this);

1,759,788✔

279

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

27,977,374✔

280

   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;

27,977,374✔

281

   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;

27,977,374✔

283

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

27,977,374✔

285

   if(is_negative() && is_zero()) {

28,075,935✔

286

      set_sign(Positive);

8✔

289

   return (*this);

27,977,374✔

randombit / botan / 5230455705

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) {	12,174,135✔
17	const size_t x_sw = sig_words();	12,174,135✔
18
19	grow_to(std::max(x_sw, y_words) + 1);	20,788,151✔
20
21	if(sign() == y_sign) {	12,174,135✔
22	bigint_add2(mutable_data(), size() - 1, y, y_words);	11,119,286✔
23	} else {
24	const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);	1,054,849✔
25
26	if(relative_size >= 0) {	1,054,849✔
27	// *this >= y
28	bigint_sub2(mutable_data(), x_sw, y, y_words);	987,324✔
29	} else {
30	// *this < y
31	bigint_sub2_rev(mutable_data(), y, y_words);	67,525✔
32	}
33
34	//this->sign_fixup(relative_size, y_sign);
35	if(relative_size < 0) {	1,054,849✔
36	set_sign(y_sign);	67,525✔
37	} else if(relative_size == 0) {	987,324✔
38	set_sign(Positive);	309✔
39	}
40	}
41
42	return (*this);	12,174,135✔
43	}
44
45	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	6,212,171✔
46	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	6,212,171✔
47	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
48	}
49
50	BOTAN_DEBUG_ASSERT(*this < mod);	6,212,171✔
51	BOTAN_DEBUG_ASSERT(s < mod);	6,212,171✔
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();	6,212,171✔
64	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	6,212,171✔
65
66	this->grow_to(mod_sw);	6,212,171✔
67	s.grow_to(mod_sw);	6,212,171✔
68
69	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
70	if(ws.size() < 3 * mod_sw) {	6,212,171✔
71	ws.resize(3 * mod_sw);	3,866,822✔
72	}
73
74	word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);	6,212,171✔
75	BOTAN_DEBUG_ASSERT(borrow == 0);	6,212,171✔
76	BOTAN_UNUSED(borrow);	6,212,171✔
77
78	// Compute t - ws
79	borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);	6,212,171✔
80
81	// Compute t + s
82	bigint_add3_nc(&ws[mod_sw * 2], this->data(), mod_sw, s.data(), mod_sw);	6,212,171✔
83
84	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	6,212,171✔
85	set_words(&ws[0], mod_sw);	6,212,171✔
86
87	return (*this);	6,212,171✔
88	}
89
90	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	58,544,776✔
91	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	58,544,776✔
92	throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");	×
93	}
94
95	// We are assuming in this function that *this and s are no more than mod_sw words long
96	BOTAN_DEBUG_ASSERT(*this < mod);	58,544,776✔
97	BOTAN_DEBUG_ASSERT(s < mod);	58,544,776✔
98
99	const size_t mod_sw = mod.sig_words();	58,544,776✔
100
101	this->grow_to(mod_sw);	58,544,776✔
102	s.grow_to(mod_sw);	58,544,776✔
103
104	if(ws.size() < mod_sw) {	58,544,776✔
105	ws.resize(mod_sw);	×
106	}
107
108	if(mod_sw == 4) {	58,544,776✔
109	bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());	24,932,830✔
110	} else if(mod_sw == 6) {	33,611,946✔
111	bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());	16,399,575✔
112	} else {
113	bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());	17,212,371✔
114	}
115
116	return (*this);	58,544,776✔
117	}
118
119	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	25,511,312✔
120	BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");	25,511,312✔
121	BOTAN_ARG_CHECK(y < 16, "y too large");	25,511,312✔
122
123	BOTAN_DEBUG_ASSERT(*this < mod);	25,511,312✔
124
125	this = static_cast<word>(y);	25,511,312✔
126	this->reduce_below(mod, ws);	25,511,312✔
127	return (*this);	25,511,312✔
128	}
129
130	BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {	8,595,971✔
131	if(this->sign() != BigInt::Positive) {	8,595,971✔
132	throw Invalid_State("BigInt::sub_rev requires this is positive");	×
133	}
134
135	const size_t x_sw = this->sig_words();	8,595,971✔
136
137	ws.resize(std::max(x_sw, y_sw));	11,504,813✔
138	clear_mem(ws.data(), ws.size());	8,595,971✔
139
140	const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);	8,595,971✔
141
142	this->cond_flip_sign(relative_size > 0);	8,595,971✔
143	this->swap_reg(ws);	8,595,971✔
144
145	return (*this);	8,595,971✔
146	}
147
148	/*
149	* Multiplication Operator
150	*/
151	BigInt& BigInt::operator*=(const BigInt& y) {	617✔
152	secure_vector<word> ws;	617✔
153	return this->mul(y, ws);	617✔
154	}	617✔
155
156	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	17,196,692✔
157	const size_t x_sw = sig_words();	17,196,692✔
158	const size_t y_sw = y.sig_words();	17,196,692✔
159	set_sign((sign() == y.sign()) ? Positive : Negative);	17,196,762✔
160
161	if(x_sw == 0 \|\| y_sw == 0) {	17,196,692✔
162	clear();	2,831,720✔
163	set_sign(Positive);	2,831,720✔
164	} else if(x_sw == 1 && y_sw) {	14,364,972✔
165	grow_to(y_sw + 1);	8,957,974✔
166	bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));	17,915,948✔
167	} else if(y_sw == 1 && x_sw) {	5,406,998✔
168	word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));	52✔
169	set_word_at(x_sw, carry);	26✔
170	} else {
171	const size_t new_size = x_sw + y_sw + 1;	5,406,972✔
172	ws.resize(new_size);	5,406,972✔
173	secure_vector<word> z_reg(new_size);	5,406,972✔
174
175	bigint_mul(z_reg.data(), z_reg.size(), data(), size(), x_sw, y.data(), y.size(), y_sw, ws.data(), ws.size());	5,406,972✔
176
177	this->swap_reg(z_reg);	5,406,972✔
178	}	5,406,972✔
179
180	return (*this);	17,196,692✔
181	}
182
183	BigInt& BigInt::square(secure_vector<word>& ws) {	3,115,889✔
184	const size_t sw = sig_words();	3,115,889✔
185
186	secure_vector<word> z(2 * sw);	3,115,889✔
187	ws.resize(z.size());	3,115,889✔
188
189	bigint_sqr(z.data(), z.size(), data(), size(), sw, ws.data(), ws.size());	3,115,889✔
190
191	swap_reg(z);	3,115,889✔
192	set_sign(BigInt::Positive);	3,115,889✔
193
194	return (*this);	3,115,889✔
195	}	3,115,889✔
196
197	BigInt& BigInt::operator*=(word y) {	168,617,024✔
198	if(y == 0) {	168,617,024✔
199	clear();	×
200	set_sign(Positive);	×
201	}
202
203	const word carry = bigint_linmul2(mutable_data(), size(), y);	168,617,024✔
204	set_word_at(size(), carry);	168,617,024✔
205
206	return (*this);	168,617,024✔
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,622✔
214	(*this) >>= (y.bits() - 1);	85✔
215	} else {
216	(this) = (this) / y;	1,688✔
217	}
218	return (*this);	929✔
219	}
220
221	/*
222	* Modulo Operator
223	*/
224	BigInt& BigInt::operator%=(const BigInt& mod) {	942,154✔
225	return (this = (this) % mod);	942,154✔
226	}
227
228	/*
229	* Modulo Operator
230	*/
231	word BigInt::operator%=(word mod) {	30✔
232	if(mod == 0) {	30✔
233	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
234	}
235
236	word remainder = 0;	30✔
237
238	if(is_power_of_2(mod)) {	30✔
239	remainder = (word_at(0) & (mod - 1));	8✔
240	} else {
241	const size_t sw = sig_words();	26✔
242	for(size_t i = sw; i > 0; --i) {	75✔
243	remainder = bigint_modop(remainder, word_at(i - 1), mod);	98✔
244	}
245	}
246
247	if(remainder && sign() == BigInt::Negative) {	30✔
248	remainder = mod - remainder;	12✔
249	}
250
251	m_data.set_to_zero();	30✔
252	m_data.set_word_at(0, remainder);	30✔
253	set_sign(BigInt::Positive);	30✔
254	return remainder;	30✔
255	}
256
257	/*
258	* Left Shift Operator
259	*/
260	BigInt& BigInt::operator<<=(size_t shift) {	1,759,788✔
261	const size_t shift_words = shift / BOTAN_MP_WORD_BITS;	1,759,788✔
262	const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;	1,759,788✔
263	const size_t size = sig_words();	1,759,788✔
264
265	const size_t bits_free = top_bits_free();	1,759,788✔
266
267	const size_t new_size = size + shift_words + (bits_free < shift_bits);	1,759,788✔
268
269	m_data.grow_to(new_size);	1,759,788✔
270
271	bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);	1,759,788✔
272
273	return (*this);	1,759,788✔
274	}
275
276	/*
277	* Right Shift Operator
278	*/
279	BigInt& BigInt::operator>>=(size_t shift) {	27,977,374✔
280	const size_t shift_words = shift / BOTAN_MP_WORD_BITS;	27,977,374✔
281	const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;	27,977,374✔
282
283	bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);	27,977,374✔
284
285	if(is_negative() && is_zero()) {	28,075,935✔
286	set_sign(Positive);	8✔
287	}
288
289	return (*this);	27,977,374✔
290	}
291
292	} // namespace Botan

randombit / botan / 5230455705

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