monotone

monotone Mtn Source Tree

Root/botan/big_base.cpp

1/*************************************************
2* BigInt Base Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/bigint.h>
7#include <botan/numthry.h>
8#include <botan/mp_core.h>
9#include <botan/bit_ops.h>
10#include <botan/parsing.h>
11#include <botan/rng.h>
12
13namespace Botan {
14
15/*************************************************
16* Construct a BigInt from a regular number *
17*************************************************/
18BigInt::BigInt(u64bit n)
19 {
20 set_sign(Positive);
21
22 if(n == 0)
23 return;
24
25 const u32bit limbs_needed = sizeof(u64bit) / sizeof(word);
26
27 reg.create(2*limbs_needed + 2);
28 for(u32bit j = 0; j != limbs_needed; j++)
29 reg[j] = (word)((n >> (j*MP_WORD_BITS)) & MP_WORD_MASK);
30 }
31
32/*************************************************
33* Construct a BigInt of the specified size *
34*************************************************/
35BigInt::BigInt(Sign s, u32bit size)
36 {
37 reg.create(size);
38 signedness = s;
39 }
40
41/*************************************************
42* Construct a BigInt from a "raw" BigInt *
43*************************************************/
44BigInt::BigInt(const BigInt& b)
45 {
46 if(b.sig_words())
47 {
48 reg.set(b.data(), b.sig_words());
49 set_sign(b.sign());
50 }
51 else
52 {
53 reg.create(2);
54 set_sign(Positive);
55 }
56 }
57
58/*************************************************
59* Construct a BigInt from a string *
60*************************************************/
61BigInt::BigInt(const std::string& str)
62 {
63 Base base = Decimal;
64 u32bit markers = 0;
65 bool negative = false;
66 if(str.length() > 0 && str[0] == '-') { markers += 1; negative = true; }
67
68 if(str.length() > markers + 2 && str[markers ] == '0' &&
69 str[markers + 1] == 'x')
70 { markers += 2; base = Hexadecimal; }
71 else if(str.length() > markers + 1 && str[markers] == '0')
72 { markers += 1; base = Octal; }
73
74 *this = decode((const byte*)str.data() + markers,
75 str.length() - markers, base);
76
77 if(negative) set_sign(Negative);
78 else set_sign(Positive);
79 }
80
81/*************************************************
82* Construct a BigInt from an encoded BigInt *
83*************************************************/
84BigInt::BigInt(const byte input[], u32bit length, Base base)
85 {
86 set_sign(Positive);
87 *this = decode(input, length, base);
88 }
89
90/*************************************************
91* Construct a Random BigInt *
92*************************************************/
93BigInt::BigInt(NumberType type, u32bit bits)
94 {
95 set_sign(Positive);
96 if(type == Random && bits)
97 randomize(bits);
98 else if(type == Power2)
99 set_bit(bits);
100 }
101
102/*************************************************
103* Swap this BigInt with another *
104*************************************************/
105void BigInt::swap(BigInt& other)
106 {
107 std::swap(reg, other.reg);
108 std::swap(signedness, other.signedness);
109 }
110
111/*************************************************
112* Comparison Function *
113*************************************************/
114s32bit BigInt::cmp(const BigInt& n, bool check_signs) const
115 {
116 if(check_signs)
117 {
118 if(n.is_positive() && this->is_negative()) return -1;
119 if(n.is_negative() && this->is_positive()) return 1;
120 if(n.is_negative() && this->is_negative())
121 return (-bigint_cmp(data(), sig_words(), n.data(), n.sig_words()));
122 }
123 return bigint_cmp(data(), sig_words(), n.data(), n.sig_words());
124 }
125
126/*************************************************
127* Add n to this number *
128*************************************************/
129void BigInt::add(word n)
130 {
131 if(!n) return;
132 word temp = reg[0];
133 reg[0] += n;
134 if(reg[0] > temp)
135 return;
136 for(u32bit j = 1; j != size(); j++)
137 if(++reg[j]) return;
138 grow_to(2*size());
139 reg[size() / 2] = 1;
140 }
141
142/*************************************************
143* Subtract n from this number *
144*************************************************/
145void BigInt::sub(word n)
146 {
147 if(!n) return;
148 word temp = reg[0];
149 reg[0] -= n;
150 if(reg[0] < temp)
151 return;
152 for(u32bit j = 1; j != size(); j++)
153 if(reg[j]--) return;
154 reg.create(2);
155 flip_sign();
156 reg[0] = n - temp;
157 }
158
159/*************************************************
160* Prefix Increment Operator *
161*************************************************/
162BigInt& BigInt::operator++()
163 {
164 if(is_negative()) sub(1);
165 else add(1);
166 return (*this);
167 }
168
169/*************************************************
170* Prefix Decrement Operator *
171*************************************************/
172BigInt& BigInt::operator--()
173 {
174 if(is_negative()) add(1);
175 else sub(1);
176 return (*this);
177 }
178
179/*************************************************
180* Return word n of this number *
181*************************************************/
182word BigInt::word_at(u32bit n) const
183 {
184 if(n >= size()) return 0;
185 else return reg[n];
186 }
187
188/*************************************************
189* Convert this number to a u32bit, if possible *
190*************************************************/
191u32bit BigInt::to_u32bit() const
192 {
193 if(is_negative())
194 throw Encoding_Error("BigInt::to_u32bit: Number is negative");
195 if(bits() >= 32)
196 throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
197
198 u32bit out = 0;
199 for(u32bit j = 0; j != 4; j++)
200 out = (out << 8) | byte_at(3-j);
201 return out;
202 }
203
204/*************************************************
205* Return byte n of this number *
206*************************************************/
207byte BigInt::byte_at(u32bit n) const
208 {
209 const u32bit WORD_BYTES = sizeof(word);
210 u32bit word_num = n / WORD_BYTES, byte_num = n % WORD_BYTES;
211 if(word_num >= size())
212 return 0;
213 else
214 return get_byte(WORD_BYTES - byte_num - 1, reg[word_num]);
215 }
216
217/*************************************************
218* Return bit n of this number *
219*************************************************/
220bool BigInt::get_bit(u32bit n) const
221 {
222 return ((word_at(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
223 }
224
225/*************************************************
226* Return nibble n of this number *
227*************************************************/
228u32bit BigInt::get_nibble(u32bit n, u32bit nibble_size) const
229 {
230 if(nibble_size > 32)
231 throw Invalid_Argument("BigInt::get_nibble: Nibble size too large");
232
233 u32bit nibble = 0;
234 for(s32bit j = (s32bit)nibble_size-1; j >= 0; j--)
235 {
236 nibble <<= 1;
237 if(get_bit(n * nibble_size + j))
238 nibble |= 1;
239 }
240 return nibble;
241 }
242
243/*************************************************
244* Set bit number n *
245*************************************************/
246void BigInt::set_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()) grow_to(which + 1);
251 reg[which] |= mask;
252 }
253
254/*************************************************
255* Clear bit number n *
256*************************************************/
257void BigInt::clear_bit(u32bit n)
258 {
259 const u32bit which = n / MP_WORD_BITS;
260 const word mask = (word)1 << (n % MP_WORD_BITS);
261 if(which < size())
262 reg[which] &= ~mask;
263 }
264
265/*************************************************
266* Clear all but the lowest n bits *
267*************************************************/
268void BigInt::mask_bits(u32bit n)
269 {
270 if(n == 0) { clear(); return; }
271 if(n >= bits()) return;
272
273 const u32bit top_word = n / MP_WORD_BITS;
274 const word mask = ((word)1 << (n % MP_WORD_BITS)) - 1;
275
276 if(top_word < size())
277 for(u32bit j = top_word + 1; j != size(); j++)
278 reg[j] = 0;
279
280 reg[top_word] &= mask;
281 }
282
283/*************************************************
284* Count the significant words *
285*************************************************/
286u32bit BigInt::sig_words() const
287 {
288 const word* x = data();
289 u32bit top_set = size();
290
291 while(top_set >= 4)
292 {
293 word sum = x[top_set-1] | x[top_set-2] | x[top_set-3] | x[top_set-4];
294 if(sum) break;
295 else top_set -= 4;
296 }
297 while(top_set && (x[top_set-1] == 0))
298 top_set--;
299 return top_set;
300 }
301
302/*************************************************
303* Count how many bytes are being used *
304*************************************************/
305u32bit BigInt::bytes() const
306 {
307 return (bits() + 7) / 8;
308 }
309
310/*************************************************
311* Count how many bits are being used *
312*************************************************/
313u32bit BigInt::bits() const
314 {
315 if(sig_words() == 0) return 0;
316 u32bit full_words = sig_words() - 1, top_bits = MP_WORD_BITS;
317 word top_word = word_at(full_words), mask = MP_WORD_TOP_BIT;
318 while(top_bits && ((top_word & mask) == 0))
319 { mask >>= 1; top_bits--; }
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 if(base == Binary)
330 return bytes();
331 else if(base == Hexadecimal)
332 return 2*bytes();
333 else if(base == Octal)
334 return ((bits() + 2) / 3);
335 else if(base == Decimal)
336 return (u32bit)((bits() * LOG_2_BASE_10) + 1);
337 else
338 throw Invalid_Argument("Unknown base for BigInt encoding");
339 }
340
341/*************************************************
342* Return true if this number is zero *
343*************************************************/
344bool BigInt::is_zero() const
345 {
346 for(u32bit j = 0; j != size(); j++)
347 if(reg[j]) return false;
348 return true;
349 }
350
351/*************************************************
352* Set the sign *
353*************************************************/
354void BigInt::set_sign(Sign s)
355 {
356 if(is_zero())
357 signedness = Positive;
358 else
359 signedness = s;
360 }
361
362/*************************************************
363* Reverse the value of the sign flag *
364*************************************************/
365void BigInt::flip_sign()
366 {
367 set_sign(reverse_sign());
368 }
369
370/*************************************************
371* Return the opposite value of the current sign *
372*************************************************/
373BigInt::Sign BigInt::reverse_sign() const
374 {
375 if(sign() == Positive)
376 return Negative;
377 return Positive;
378 }
379
380/*************************************************
381* Return the negation of this number *
382*************************************************/
383BigInt BigInt::operator-() const
384 {
385 BigInt x = (*this);
386 x.flip_sign();
387 return x;
388 }
389
390/*************************************************
391* Return the absolute value of this number *
392*************************************************/
393BigInt BigInt::abs() const
394 {
395 BigInt x = (*this);
396 x.set_sign(Positive);
397 return x;
398 }
399
400/*************************************************
401* Randomize this number *
402*************************************************/
403void BigInt::randomize(u32bit bitsize, RNG_Quality level)
404 {
405 set_sign(Positive);
406
407 if(bitsize == 0)
408 clear();
409 else
410 {
411 SecureVector<byte> array((bitsize + 7) / 8);
412 Global_RNG::randomize(array, array.size(), level);
413 if(bitsize % 8)
414 array[0] &= 0xFF >> (8 - (bitsize % 8));
415 array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
416 binary_decode(array, array.size());
417 }
418 }
419
420/*************************************************
421* Encode this number into bytes *
422*************************************************/
423void BigInt::binary_encode(byte output[]) const
424 {
425 const u32bit sig_bytes = bytes();
426 for(u32bit j = 0; j != sig_bytes; j++)
427 output[sig_bytes-j-1] = byte_at(j);
428 }
429
430/*************************************************
431* Set this number to the value in buf *
432*************************************************/
433void BigInt::binary_decode(const byte buf[], u32bit length)
434 {
435 const u32bit WORD_BYTES = sizeof(word);
436 reg.create(length / WORD_BYTES + 1);
437
438 for(u32bit j = 0; j != length / WORD_BYTES; j++)
439 {
440 u32bit top = length - WORD_BYTES*j;
441 for(u32bit k = WORD_BYTES; k > 0; k--)
442 reg[j] = (reg[j] << 8) | buf[top - k];
443 }
444 for(u32bit j = 0; j != length % WORD_BYTES; j++)
445 reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[j];
446 }
447
448/*************************************************
449* Generate a random integer *
450*************************************************/
451BigInt random_integer(u32bit bits, RNG_Quality level)
452 {
453 BigInt x;
454 x.randomize(bits, level);
455 return x;
456 }
457
458/*************************************************
459* Generate a random integer within given range *
460*************************************************/
461BigInt random_integer(const BigInt& min, const BigInt& max, RNG_Quality level)
462 {
463 BigInt range = max - min;
464
465 if(range <= 0)
466 throw Invalid_Argument("random_integer: invalid min/max values");
467
468 return (min + (random_integer(range.bits() + 2, level) % range));
469 }
470
471/*************************************************
472* Generate a random safe prime *
473*************************************************/
474BigInt random_safe_prime(u32bit bits, RNG_Quality level)
475 {
476 if(bits <= 64)
477 throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
478 to_string(bits) + " bits");
479
480 BigInt p;
481 do
482 p = (random_prime(bits - 1, level) << 1) + 1;
483 while(!is_prime(p));
484 return p;
485 }
486
487}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status