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

16

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

11,877,431✔

17

   const size_t x_sw = sig_words();

11,877,431✔

19

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

20,276,294✔

21

   if(sign() == y_sign) {

11,877,431✔

22

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

10,850,818✔

24

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

1,026,613✔

26

      if(relative_size >= 0) {

1,026,613✔

28

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

966,595✔

31

         bigint_sub2_rev(mutable_data(), y, y_words);

60,018✔

35

      if(relative_size < 0) {

1,026,613✔

36

         set_sign(y_sign);

60,018✔

37

      } else if(relative_size == 0) {

966,595✔

38

         set_sign(Positive);

269✔

42

   return (*this);

11,877,431✔

45

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

5,990,331✔

46

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

5,990,331✔

50

   BOTAN_DEBUG_ASSERT(*this < mod);

5,990,331✔

51

   BOTAN_DEBUG_ASSERT(s < mod);

5,990,331✔

63

   const size_t mod_sw = mod.sig_words();

5,990,331✔

64

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

5,990,331✔

66

   this->grow_to(mod_sw);

5,990,331✔

67

   s.grow_to(mod_sw);

5,990,331✔

70

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

5,990,331✔

71

      ws.resize(3 * mod_sw);

3,700,123✔

74

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

5,990,331✔

75

   BOTAN_DEBUG_ASSERT(borrow == 0);

5,990,331✔

76

   BOTAN_UNUSED(borrow);

5,990,331✔

79

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

5,990,331✔

82

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

5,990,331✔

84

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

5,990,331✔

85

   set_words(&ws[0], mod_sw);

5,990,331✔

87

   return (*this);

5,990,331✔

90

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

54,876,658✔

91

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

54,876,658✔

96

   BOTAN_DEBUG_ASSERT(*this < mod);

54,876,658✔

97

   BOTAN_DEBUG_ASSERT(s < mod);

54,876,658✔

99

   const size_t mod_sw = mod.sig_words();

54,876,658✔

101

   this->grow_to(mod_sw);

54,876,658✔

102

   s.grow_to(mod_sw);

54,876,658✔

104

   if(ws.size() < mod_sw) {

54,876,658✔

108

   if(mod_sw == 4) {

54,876,658✔

109

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

24,193,731✔

110

   } else if(mod_sw == 6) {

30,682,927✔

111

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

16,079,520✔

113

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

14,603,407✔

116

   return (*this);

54,876,658✔

119

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

24,446,348✔

120

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

24,446,348✔

121

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

24,446,348✔

123

   BOTAN_DEBUG_ASSERT(*this < mod);

24,446,348✔

125

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

24,446,348✔

126

   this->reduce_below(mod, ws);

24,446,348✔

127

   return (*this);

24,446,348✔

130

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

8,380,975✔

131

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

8,380,975✔

135

   const size_t x_sw = this->sig_words();

8,380,975✔

137

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

11,261,172✔

138

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

8,380,975✔

140

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

8,380,975✔

142

   this->cond_flip_sign(relative_size > 0);

8,380,975✔

143

   this->swap_reg(ws);

8,380,975✔

145

   return (*this);

8,380,975✔

151

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

611✔

152

   secure_vector<word> ws;

611✔

153

   return this->mul(y, ws);

611✔

154

611✔

156

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

16,766,266✔

157

   const size_t x_sw = sig_words();

16,766,266✔

158

   const size_t y_sw = y.sig_words();

16,766,266✔

159

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

16,766,336✔

161

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

16,766,266✔

162

      clear();

2,810,360✔

163

      set_sign(Positive);

2,810,360✔

164

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

13,955,906✔

165

      grow_to(y_sw + 1);

8,910,238✔

166

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

17,820,476✔

167

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

5,045,668✔

168

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

54✔

169

      set_word_at(x_sw, carry);

27✔

171

      const size_t new_size = x_sw + y_sw + 1;

5,045,641✔

172

      ws.resize(new_size);

5,045,641✔

173

      secure_vector<word> z_reg(new_size);

5,045,641✔

175

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

5,045,641✔

177

      this->swap_reg(z_reg);

5,045,641✔

178

5,045,641✔

180

   return (*this);

16,766,266✔

183

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

2,964,855✔

184

   const size_t sw = sig_words();

2,964,855✔

186

   secure_vector<word> z(2 * sw);

2,964,855✔

187

   ws.resize(z.size());

2,964,855✔

189

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

2,964,855✔

191

   swap_reg(z);

2,964,855✔

192

   set_sign(BigInt::Positive);

2,964,855✔

194

   return (*this);

2,964,855✔

195

2,964,855✔

197

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

166,825,478✔

198

   if(y == 0) {

166,825,478✔

203

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

166,825,478✔

204

   set_word_at(size(), carry);

166,825,478✔

206

   return (*this);

166,825,478✔

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) { return (*this = (*this) % mod); }

926,854✔

229

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

30✔

230

   if(mod == 0) {

30✔

234

   word remainder = 0;

30✔

236

   if(is_power_of_2(mod)) {

30✔

237

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

8✔

239

      const size_t sw = sig_words();

26✔

240

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

75✔

241

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

98✔

245

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

30✔

246

      remainder = mod - remainder;

12✔

249

   m_data.set_to_zero();

30✔

250

   m_data.set_word_at(0, remainder);

30✔

251

   set_sign(BigInt::Positive);

30✔

252

   return remainder;

30✔

258

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

1,737,512✔

259

   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;

1,737,512✔

260

   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;

1,737,512✔

261

   const size_t size = sig_words();

1,737,512✔

263

   const size_t bits_free = top_bits_free();

1,737,512✔

265

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

1,737,512✔

267

   m_data.grow_to(new_size);

1,737,512✔

269

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

1,737,512✔

271

   return (*this);

1,737,512✔

277

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

27,456,863✔

278

   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;

27,456,863✔

279

   const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;

27,456,863✔

281

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

27,456,863✔

283

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

27,547,773✔

284

      set_sign(Positive);

8✔

287

   return (*this);

27,456,863✔

randombit / botan / 5123321399

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,877,431✔
17	const size_t x_sw = sig_words();	11,877,431✔
18
19	grow_to(std::max(x_sw, y_words) + 1);	20,276,294✔
20
21	if(sign() == y_sign) {	11,877,431✔
22	bigint_add2(mutable_data(), size() - 1, y, y_words);	10,850,818✔
23	} else {
24	const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);	1,026,613✔
25
26	if(relative_size >= 0) {	1,026,613✔
27	// *this >= y
28	bigint_sub2(mutable_data(), x_sw, y, y_words);	966,595✔
29	} else {
30	// *this < y
31	bigint_sub2_rev(mutable_data(), y, y_words);	60,018✔
32	}
33
34	//this->sign_fixup(relative_size, y_sign);
35	if(relative_size < 0) {	1,026,613✔
36	set_sign(y_sign);	60,018✔
37	} else if(relative_size == 0) {	966,595✔
38	set_sign(Positive);	269✔
39	}
40	}
41
42	return (*this);	11,877,431✔
43	}
44
45	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	5,990,331✔
46	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	5,990,331✔
47	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
48	}
49
50	BOTAN_DEBUG_ASSERT(*this < mod);	5,990,331✔
51	BOTAN_DEBUG_ASSERT(s < mod);	5,990,331✔
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();	5,990,331✔
64	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	5,990,331✔
65
66	this->grow_to(mod_sw);	5,990,331✔
67	s.grow_to(mod_sw);	5,990,331✔
68
69	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
70	if(ws.size() < 3 * mod_sw) {	5,990,331✔
71	ws.resize(3 * mod_sw);	3,700,123✔
72	}
73
74	word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);	5,990,331✔
75	BOTAN_DEBUG_ASSERT(borrow == 0);	5,990,331✔
76	BOTAN_UNUSED(borrow);	5,990,331✔
77
78	// Compute t - ws
79	borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);	5,990,331✔
80
81	// Compute t + s
82	bigint_add3_nc(&ws[mod_sw * 2], this->data(), mod_sw, s.data(), mod_sw);	5,990,331✔
83
84	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	5,990,331✔
85	set_words(&ws[0], mod_sw);	5,990,331✔
86
87	return (*this);	5,990,331✔
88	}
89
90	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	54,876,658✔
91	if(this->is_negative() \|\| s.is_negative() \|\| mod.is_negative()) {	54,876,658✔
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);	54,876,658✔
97	BOTAN_DEBUG_ASSERT(s < mod);	54,876,658✔
98
99	const size_t mod_sw = mod.sig_words();	54,876,658✔
100
101	this->grow_to(mod_sw);	54,876,658✔
102	s.grow_to(mod_sw);	54,876,658✔
103
104	if(ws.size() < mod_sw) {	54,876,658✔
105	ws.resize(mod_sw);	×
106	}
107
108	if(mod_sw == 4) {	54,876,658✔
109	bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());	24,193,731✔
110	} else if(mod_sw == 6) {	30,682,927✔
111	bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());	16,079,520✔
112	} else {
113	bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());	14,603,407✔
114	}
115
116	return (*this);	54,876,658✔
117	}
118
119	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	24,446,348✔
120	BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");	24,446,348✔
121	BOTAN_ARG_CHECK(y < 16, "y too large");	24,446,348✔
122
123	BOTAN_DEBUG_ASSERT(*this < mod);	24,446,348✔
124
125	this = static_cast<word>(y);	24,446,348✔
126	this->reduce_below(mod, ws);	24,446,348✔
127	return (*this);	24,446,348✔
128	}
129
130	BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {	8,380,975✔
131	if(this->sign() != BigInt::Positive) {	8,380,975✔
132	throw Invalid_State("BigInt::sub_rev requires this is positive");	×
133	}
134
135	const size_t x_sw = this->sig_words();	8,380,975✔
136
137	ws.resize(std::max(x_sw, y_sw));	11,261,172✔
138	clear_mem(ws.data(), ws.size());	8,380,975✔
139
140	const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);	8,380,975✔
141
142	this->cond_flip_sign(relative_size > 0);	8,380,975✔
143	this->swap_reg(ws);	8,380,975✔
144
145	return (*this);	8,380,975✔
146	}
147
148	/*
149	* Multiplication Operator
150	*/
151	BigInt& BigInt::operator*=(const BigInt& y) {	611✔
152	secure_vector<word> ws;	611✔
153	return this->mul(y, ws);	611✔
154	}	611✔
155
156	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	16,766,266✔
157	const size_t x_sw = sig_words();	16,766,266✔
158	const size_t y_sw = y.sig_words();	16,766,266✔
159	set_sign((sign() == y.sign()) ? Positive : Negative);	16,766,336✔
160
161	if(x_sw == 0 \|\| y_sw == 0) {	16,766,266✔
162	clear();	2,810,360✔
163	set_sign(Positive);	2,810,360✔
164	} else if(x_sw == 1 && y_sw) {	13,955,906✔
165	grow_to(y_sw + 1);	8,910,238✔
166	bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));	17,820,476✔
167	} else if(y_sw == 1 && x_sw) {	5,045,668✔
168	word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));	54✔
169	set_word_at(x_sw, carry);	27✔
170	} else {
171	const size_t new_size = x_sw + y_sw + 1;	5,045,641✔
172	ws.resize(new_size);	5,045,641✔
173	secure_vector<word> z_reg(new_size);	5,045,641✔
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,045,641✔
176
177	this->swap_reg(z_reg);	5,045,641✔
178	}	5,045,641✔
179
180	return (*this);	16,766,266✔
181	}
182
183	BigInt& BigInt::square(secure_vector<word>& ws) {	2,964,855✔
184	const size_t sw = sig_words();	2,964,855✔
185
186	secure_vector<word> z(2 * sw);	2,964,855✔
187	ws.resize(z.size());	2,964,855✔
188
189	bigint_sqr(z.data(), z.size(), data(), size(), sw, ws.data(), ws.size());	2,964,855✔
190
191	swap_reg(z);	2,964,855✔
192	set_sign(BigInt::Positive);	2,964,855✔
193
194	return (*this);	2,964,855✔
195	}	2,964,855✔
196
197	BigInt& BigInt::operator*=(word y) {	166,825,478✔
198	if(y == 0) {	166,825,478✔
199	clear();	×
200	set_sign(Positive);	×
201	}
202
203	const word carry = bigint_linmul2(mutable_data(), size(), y);	166,825,478✔
204	set_word_at(size(), carry);	166,825,478✔
205
206	return (*this);	166,825,478✔
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) { return (this = (this) % mod); }	926,854✔
225
226	/*
227	* Modulo Operator
228	*/
229	word BigInt::operator%=(word mod) {	30✔
230	if(mod == 0) {	30✔
231	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
232	}
233
234	word remainder = 0;	30✔
235
236	if(is_power_of_2(mod)) {	30✔
237	remainder = (word_at(0) & (mod - 1));	8✔
238	} else {
239	const size_t sw = sig_words();	26✔
240	for(size_t i = sw; i > 0; --i) {	75✔
241	remainder = bigint_modop(remainder, word_at(i - 1), mod);	98✔
242	}
243	}
244
245	if(remainder && sign() == BigInt::Negative) {	30✔
246	remainder = mod - remainder;	12✔
247	}
248
249	m_data.set_to_zero();	30✔
250	m_data.set_word_at(0, remainder);	30✔
251	set_sign(BigInt::Positive);	30✔
252	return remainder;	30✔
253	}
254
255	/*
256	* Left Shift Operator
257	*/
258	BigInt& BigInt::operator<<=(size_t shift) {	1,737,512✔
259	const size_t shift_words = shift / BOTAN_MP_WORD_BITS;	1,737,512✔
260	const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;	1,737,512✔
261	const size_t size = sig_words();	1,737,512✔
262
263	const size_t bits_free = top_bits_free();	1,737,512✔
264
265	const size_t new_size = size + shift_words + (bits_free < shift_bits);	1,737,512✔
266
267	m_data.grow_to(new_size);	1,737,512✔
268
269	bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);	1,737,512✔
270
271	return (*this);	1,737,512✔
272	}
273
274	/*
275	* Right Shift Operator
276	*/
277	BigInt& BigInt::operator>>=(size_t shift) {	27,456,863✔
278	const size_t shift_words = shift / BOTAN_MP_WORD_BITS;	27,456,863✔
279	const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;	27,456,863✔
280
281	bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);	27,456,863✔
282
283	if(is_negative() && is_zero()) {	27,547,773✔
284	set_sign(Positive);	8✔
285	}
286
287	return (*this);	27,456,863✔
288	}
289
290	} // namespace Botan

randombit / botan / 5123321399

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