1/*
2Copyright (C) 1999-2007 The Botan Project. All rights reserved.
3
4Redistribution and use in source and binary forms, for any use, with or without
5modification, is permitted provided that the following conditions are met:
6
71. Redistributions of source code must retain the above copyright notice, this
8list of conditions, and the following disclaimer.
9
102. Redistributions in binary form must reproduce the above copyright notice,
11this list of conditions, and the following disclaimer in the documentation
12and/or other materials provided with the distribution.
13
14THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED
15WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED.
17
18IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT,
19INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
22LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
23OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
24ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*/
26// LICENSEHEADER_END
27namespace QCA { // WRAPNS_LINE
28/*************************************************
29 * BigInt Base Source File *
30 * (C) 1999-2007 The Botan Project *
31 *************************************************/
32
33} // WRAPNS_LINE
34#include <botan/bigint.h>
35namespace QCA { // WRAPNS_LINE
36} // WRAPNS_LINE
37#include <botan/mp_core.h>
38namespace QCA { // WRAPNS_LINE
39} // WRAPNS_LINE
40#include <botan/bit_ops.h>
41namespace QCA { // WRAPNS_LINE
42} // WRAPNS_LINE
43#include <botan/parsing.h>
44namespace QCA { // WRAPNS_LINE
45} // WRAPNS_LINE
46#include <botan/util.h>
47namespace QCA { // WRAPNS_LINE
48
49namespace Botan {
50
51/*************************************************
52 * Construct a BigInt from a regular number *
53 *************************************************/
54BigInt::BigInt(u64bit n)
55{
56 set_sign(Positive);
57
58 if (n == 0)
59 return;
60
61 const u32bit limbs_needed = sizeof(u64bit) / sizeof(word);
62
63 reg.create(n: 4 * limbs_needed);
64 for (u32bit j = 0; j != limbs_needed; ++j)
65 reg[j] = (word)((n >> (j * MP_WORD_BITS)) & MP_WORD_MASK);
66}
67
68/*************************************************
69 * Construct a BigInt of the specified size *
70 *************************************************/
71BigInt::BigInt(Sign s, u32bit size)
72{
73 reg.create(n: round_up(size, 8));
74 signedness = s;
75}
76
77/*************************************************
78 * Construct a BigInt from a "raw" BigInt *
79 *************************************************/
80BigInt::BigInt(const BigInt &b)
81{
82 const u32bit b_words = b.sig_words();
83
84 if (b_words) {
85 reg.create(n: round_up(b_words, 8));
86 reg.copy(in: b.data(), n: b_words);
87 set_sign(b.sign());
88 } else {
89 reg.create(n: 2);
90 set_sign(Positive);
91 }
92}
93
94BigInt &BigInt::operator=(const BigInt &) = default;
95
96/*************************************************
97 * Construct a BigInt from a string *
98 *************************************************/
99BigInt::BigInt(const std::string &str)
100{
101 Base base = Decimal;
102 u32bit markers = 0;
103 bool negative = false;
104 if (str.length() > 0 && str[0] == '-') {
105 markers += 1;
106 negative = true;
107 }
108
109 if (str.length() > markers + 2 && str[markers] == '0' && str[markers + 1] == 'x') {
110 markers += 2;
111 base = Hexadecimal;
112 } else if (str.length() > markers + 1 && str[markers] == '0') {
113 markers += 1;
114 base = Octal;
115 }
116
117 *this = decode((const byte *)str.data() + markers, str.length() - markers, base);
118
119 if (negative)
120 set_sign(Negative);
121 else
122 set_sign(Positive);
123}
124
125/*************************************************
126 * Construct a BigInt from an encoded BigInt *
127 *************************************************/
128BigInt::BigInt(const byte input[], u32bit length, Base base)
129{
130 set_sign(Positive);
131 *this = decode(input, length, base);
132}
133
134/*************************************************
135 * Swap this BigInt with another *
136 *************************************************/
137void BigInt::swap(BigInt &other)
138{
139 std::swap(a&: reg, b&: other.reg);
140 std::swap(a&: signedness, b&: other.signedness);
141}
142
143/*************************************************
144 * Grow the internal storage *
145 *************************************************/
146void BigInt::grow_reg(u32bit n) const
147{
148 reg.grow_to(n: round_up(size() + n, 8));
149}
150
151/*************************************************
152 * Grow the internal storage *
153 *************************************************/
154void BigInt::grow_to(u32bit n) const
155{
156 if (n > size())
157 reg.grow_to(n: round_up(n, 8));
158}
159
160/*************************************************
161 * Comparison Function *
162 *************************************************/
163s32bit BigInt::cmp(const BigInt &n, bool check_signs) const
164{
165 if (check_signs) {
166 if (n.is_positive() && this->is_negative())
167 return -1;
168 if (n.is_negative() && this->is_positive())
169 return 1;
170 if (n.is_negative() && this->is_negative())
171 return (-bigint_cmp(data(), sig_words(), n.data(), n.sig_words()));
172 }
173 return bigint_cmp(data(), sig_words(), n.data(), n.sig_words());
174}
175
176/*************************************************
177 * Convert this number to a u32bit, if possible *
178 *************************************************/
179u32bit BigInt::to_u32bit() const
180{
181 if (is_negative())
182 throw Encoding_Error("BigInt::to_u32bit: Number is negative");
183 if (bits() >= 32)
184 throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
185
186 u32bit out = 0;
187 for (u32bit j = 0; j != 4; ++j)
188 out = (out << 8) | byte_at(3 - j);
189 return out;
190}
191
192/*************************************************
193 * Return byte n of this number *
194 *************************************************/
195byte BigInt::byte_at(u32bit n) const
196{
197 const u32bit WORD_BYTES = sizeof(word);
198 u32bit word_num = n / WORD_BYTES, byte_num = n % WORD_BYTES;
199 if (word_num >= size())
200 return 0;
201 else
202 return get_byte(byte_num: WORD_BYTES - byte_num - 1, input: reg[word_num]);
203}
204
205/*************************************************
206 * Return bit n of this number *
207 *************************************************/
208bool BigInt::get_bit(u32bit n) const
209{
210 return ((word_at(n: n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
211}
212
213/*************************************************
214 * Return bits {offset...offset+length} *
215 *************************************************/
216u32bit BigInt::get_substring(u32bit offset, u32bit length) const
217{
218 if (length > 32)
219 throw Invalid_Argument("BigInt::get_substring: Substring size too big");
220
221 u64bit piece = 0;
222 for (u32bit j = 0; j != 8; ++j)
223 piece = (piece << 8) | byte_at(n: (offset / 8) + (7 - j));
224
225 u64bit mask = (1 << length) - 1;
226 u32bit shift = (offset % 8);
227
228 return static_cast<u32bit>((piece >> shift) & mask);
229}
230
231/*************************************************
232 * Set bit number n *
233 *************************************************/
234void BigInt::set_bit(u32bit n)
235{
236 const u32bit which = n / MP_WORD_BITS;
237 const word mask = (word)1 << (n % MP_WORD_BITS);
238 if (which >= size())
239 grow_to(n: which + 1);
240 reg[which] |= mask;
241}
242
243/*************************************************
244 * Clear bit number n *
245 *************************************************/
246void BigInt::clear_bit(u32bit n)
247{
248 const u32bit which = n / MP_WORD_BITS;
249 const word mask = (word)1 << (n % MP_WORD_BITS);
250 if (which < size())
251 reg[which] &= ~mask;
252}
253
254/*************************************************
255 * Clear all but the lowest n bits *
256 *************************************************/
257void BigInt::mask_bits(u32bit n)
258{
259 if (n == 0) {
260 clear();
261 return;
262 }
263 if (n >= bits())
264 return;
265
266 const u32bit top_word = n / MP_WORD_BITS;
267 const word mask = ((word)1 << (n % MP_WORD_BITS)) - 1;
268
269 if (top_word < size())
270 for (u32bit j = top_word + 1; j != size(); ++j)
271 reg[j] = 0;
272
273 reg[top_word] &= mask;
274}
275
276/*************************************************
277 * Count the significant words *
278 *************************************************/
279u32bit BigInt::sig_words() const
280{
281 const word *x = data();
282 u32bit top_set = size();
283
284 while (top_set >= 4) {
285 word sum = x[top_set - 1] | x[top_set - 2] | x[top_set - 3] | x[top_set - 4];
286 if (sum)
287 break;
288 else
289 top_set -= 4;
290 }
291 while (top_set && (x[top_set - 1] == 0))
292 top_set--;
293 return top_set;
294}
295
296/*************************************************
297 * Count how many bytes are being used *
298 *************************************************/
299u32bit BigInt::bytes() const
300{
301 return (bits() + 7) / 8;
302}
303
304/*************************************************
305 * Count how many bits are being used *
306 *************************************************/
307u32bit BigInt::bits() const
308{
309 if (sig_words() == 0)
310 return 0;
311
312 u32bit full_words = sig_words() - 1, top_bits = MP_WORD_BITS;
313 word top_word = word_at(n: full_words), mask = MP_WORD_TOP_BIT;
314
315 while (top_bits && ((top_word & mask) == 0)) {
316 mask >>= 1;
317 top_bits--;
318 }
319
320 return (full_words * MP_WORD_BITS + top_bits);
321}
322
323/*************************************************
324 * Calcluate the size in a certain base *
325 *************************************************/
326u32bit BigInt::encoded_size(Base base) const
327{
328 static const double LOG_2_BASE_10 = 0.30102999566;
329
330 if (base == Binary)
331 return bytes();
332 else if (base == Hexadecimal)
333 return 2 * bytes();
334 else if (base == Octal)
335 return ((bits() + 2) / 3);
336 else if (base == Decimal)
337 return (u32bit)((bits() * LOG_2_BASE_10) + 1);
338 else
339 throw Invalid_Argument("Unknown base for BigInt encoding");
340}
341
342/*************************************************
343 * Return true if this number is zero *
344 *************************************************/
345bool BigInt::is_zero() const
346{
347 for (u32bit j = 0; j != size(); ++j)
348 if (reg[j])
349 return false;
350 return true;
351}
352
353/*************************************************
354 * Set the sign *
355 *************************************************/
356void BigInt::set_sign(Sign s)
357{
358 if (is_zero())
359 signedness = Positive;
360 else
361 signedness = s;
362}
363
364/*************************************************
365 * Reverse the value of the sign flag *
366 *************************************************/
367void BigInt::flip_sign()
368{
369 set_sign(reverse_sign());
370}
371
372/*************************************************
373 * Return the opposite value of the current sign *
374 *************************************************/
375BigInt::Sign BigInt::reverse_sign() const
376{
377 if (sign() == Positive)
378 return Negative;
379 return Positive;
380}
381
382/*************************************************
383 * Return the negation of this number *
384 *************************************************/
385BigInt BigInt::operator-() const
386{
387 BigInt x = (*this);
388 x.flip_sign();
389 return x;
390}
391
392/*************************************************
393 * Return the absolute value of this number *
394 *************************************************/
395BigInt BigInt::abs() const
396{
397 BigInt x = (*this);
398 x.set_sign(Positive);
399 return x;
400}
401
402/*************************************************
403 * Encode this number into bytes *
404 *************************************************/
405void BigInt::binary_encode(byte output[]) const
406{
407 const u32bit sig_bytes = bytes();
408 for (u32bit j = 0; j != sig_bytes; ++j)
409 output[sig_bytes - j - 1] = byte_at(n: j);
410}
411
412/*************************************************
413 * Set this number to the value in buf *
414 *************************************************/
415void BigInt::binary_decode(const byte buf[], u32bit length)
416{
417 const u32bit WORD_BYTES = sizeof(word);
418 reg.create(n: round_up((length / WORD_BYTES) + 1, 8));
419
420 for (u32bit j = 0; j != length / WORD_BYTES; ++j) {
421 u32bit top = length - WORD_BYTES * j;
422 for (u32bit k = WORD_BYTES; k > 0; --k)
423 reg[j] = (reg[j] << 8) | buf[top - k];
424 }
425 for (u32bit j = 0; j != length % WORD_BYTES; ++j)
426 reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[j];
427}
428
429}
430} // WRAPNS_LINE
431

source code of qca/src/botantools/botan/big_base.cpp