Botan  1.10.9
bigint.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Base
3 * (C) 1999-2011 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/bigint.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/get_byte.h>
11 #include <botan/parsing.h>
12 #include <botan/internal/rounding.h>
13 
14 namespace Botan {
15 
16 /*
17 * Construct a BigInt from a regular number
18 */
20  {
22 
23  if(n == 0)
24  return;
25 
26  const size_t limbs_needed = sizeof(u64bit) / sizeof(word);
27 
28  reg.resize(4*limbs_needed);
29  for(size_t i = 0; i != limbs_needed; ++i)
30  reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
31  }
32 
33 /*
34 * Construct a BigInt of the specified size
35 */
36 BigInt::BigInt(Sign s, size_t size)
37  {
38  reg.resize(round_up<size_t>(size, 8));
39  signedness = s;
40  }
41 
42 /*
43 * Construct a BigInt from a "raw" BigInt
44 */
46  {
47  const size_t b_words = b.sig_words();
48 
49  if(b_words)
50  {
51  reg.resize(round_up<size_t>(b_words, 8));
52  reg.copy(b.data(), b_words);
53  set_sign(b.sign());
54  }
55  else
56  {
57  reg.resize(2);
59  }
60  }
61 
62 /*
63 * Construct a BigInt from a string
64 */
65 BigInt::BigInt(const std::string& str)
66  {
67  Base base = Decimal;
68  size_t markers = 0;
69  bool negative = false;
70  if(str.length() > 0 && str[0] == '-') { markers += 1; negative = true; }
71 
72  if(str.length() > markers + 2 && str[markers ] == '0' &&
73  str[markers + 1] == 'x')
74  { markers += 2; base = Hexadecimal; }
75  else if(str.length() > markers + 1 && str[markers] == '0')
76  { markers += 1; base = Octal; }
77 
78  *this = decode(reinterpret_cast<const byte*>(str.data()) + markers,
79  str.length() - markers, base);
80 
81  if(negative) set_sign(Negative);
82  else set_sign(Positive);
83  }
84 
85 /*
86 * Construct a BigInt from an encoded BigInt
87 */
88 BigInt::BigInt(const byte input[], size_t length, Base base)
89  {
91  *this = decode(input, length, base);
92  }
93 
94 /*
95 * Construct a BigInt from an encoded BigInt
96 */
98  {
100  randomize(rng, bits);
101  }
102 
103 /*
104 * Swap this BigInt with another
105 */
106 void BigInt::swap(BigInt& other)
107  {
108  reg.swap(other.reg);
109  std::swap(signedness, other.signedness);
110  }
111 
112 /*
113 * Grow the internal storage
114 */
115 void BigInt::grow_reg(size_t n)
116  {
117  reg.resize(round_up<size_t>(size() + n, 8));
118  }
119 
120 /*
121 * Grow the internal storage
122 */
123 void BigInt::grow_to(size_t n)
124  {
125  if(n > size())
126  reg.resize(round_up<size_t>(n, 8));
127  }
128 
129 /*
130 * Comparison Function
131 */
132 s32bit BigInt::cmp(const BigInt& n, bool check_signs) const
133  {
134  if(check_signs)
135  {
136  if(n.is_positive() && this->is_negative()) return -1;
137  if(n.is_negative() && this->is_positive()) return 1;
138  if(n.is_negative() && this->is_negative())
139  return (-bigint_cmp(data(), sig_words(), n.data(), n.sig_words()));
140  }
141  return bigint_cmp(data(), sig_words(), n.data(), n.sig_words());
142  }
143 
144 /*
145 * Return byte n of this number
146 */
147 byte BigInt::byte_at(size_t n) const
148  {
149  const size_t WORD_BYTES = sizeof(word);
150  size_t word_num = n / WORD_BYTES, byte_num = n % WORD_BYTES;
151  if(word_num >= size())
152  return 0;
153  else
154  return get_byte(WORD_BYTES - byte_num - 1, reg[word_num]);
155  }
156 
157 /*
158 * Return bit n of this number
159 */
160 bool BigInt::get_bit(size_t n) const
161  {
162  return ((word_at(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
163  }
164 
165 /*
166 * Return bits {offset...offset+length}
167 */
168 u32bit BigInt::get_substring(size_t offset, size_t length) const
169  {
170  if(length > 32)
171  throw Invalid_Argument("BigInt::get_substring: Substring size too big");
172 
173  u64bit piece = 0;
174  for(size_t i = 0; i != 8; ++i)
175  {
176  const byte part = byte_at((offset / 8) + (7-i));
177  piece = (piece << 8) | part;
178  }
179 
180  const u64bit mask = (static_cast<u64bit>(1) << length) - 1;
181  const size_t shift = (offset % 8);
182 
183  return static_cast<u32bit>((piece >> shift) & mask);
184  }
185 
186 /*
187 * Convert this number to a u32bit, if possible
188 */
190  {
191  if(is_negative())
192  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
193  if(bits() >= 32)
194  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
195 
196  u32bit out = 0;
197  for(u32bit j = 0; j != 4; ++j)
198  out = (out << 8) | byte_at(3-j);
199  return out;
200  }
201 
202 /*
203 * Set bit number n
204 */
205 void BigInt::set_bit(size_t n)
206  {
207  const size_t which = n / MP_WORD_BITS;
208  const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
209  if(which >= size()) grow_to(which + 1);
210  reg[which] |= mask;
211  }
212 
213 /*
214 * Clear bit number n
215 */
216 void BigInt::clear_bit(size_t n)
217  {
218  const size_t which = n / MP_WORD_BITS;
219  const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
220  if(which < size())
221  reg[which] &= ~mask;
222  }
223 
224 /*
225 * Clear all but the lowest n bits
226 */
227 void BigInt::mask_bits(size_t n)
228  {
229  if(n == 0) { clear(); return; }
230  if(n >= bits()) return;
231 
232  const size_t top_word = n / MP_WORD_BITS;
233  const word mask = (static_cast<word>(1) << (n % MP_WORD_BITS)) - 1;
234 
235  if(top_word < size())
236  for(size_t i = top_word + 1; i != size(); ++i)
237  reg[i] = 0;
238 
239  reg[top_word] &= mask;
240  }
241 
242 /*
243 * Count how many bytes are being used
244 */
245 size_t BigInt::bytes() const
246  {
247  return (bits() + 7) / 8;
248  }
249 
250 /*
251 * Count how many bits are being used
252 */
253 size_t BigInt::bits() const
254  {
255  const size_t words = sig_words();
256 
257  if(words == 0)
258  return 0;
259 
260  size_t full_words = words - 1, top_bits = MP_WORD_BITS;
261  word top_word = word_at(full_words), mask = MP_WORD_TOP_BIT;
262 
263  while(top_bits && ((top_word & mask) == 0))
264  { mask >>= 1; top_bits--; }
265 
266  return (full_words * MP_WORD_BITS + top_bits);
267  }
268 
269 /*
270 * Calcluate the size in a certain base
271 */
273  {
274  static const double LOG_2_BASE_10 = 0.30102999566;
275 
276  if(base == Binary)
277  return bytes();
278  else if(base == Hexadecimal)
279  return 2*bytes();
280  else if(base == Octal)
281  return ((bits() + 2) / 3);
282  else if(base == Decimal)
283  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
284  else
285  throw Invalid_Argument("Unknown base for BigInt encoding");
286  }
287 
288 /*
289 * Set the sign
290 */
292  {
293  if(is_zero())
294  signedness = Positive;
295  else
296  signedness = s;
297  }
298 
299 /*
300 * Reverse the value of the sign flag
301 */
303  {
305  }
306 
307 /*
308 * Return the opposite value of the current sign
309 */
311  {
312  if(sign() == Positive)
313  return Negative;
314  return Positive;
315  }
316 
317 /*
318 * Return the negation of this number
319 */
321  {
322  BigInt x = (*this);
323  x.flip_sign();
324  return x;
325  }
326 
327 /*
328 * Return the absolute value of this number
329 */
331  {
332  BigInt x = (*this);
333  x.set_sign(Positive);
334  return x;
335  }
336 
337 /*
338 * Encode this number into bytes
339 */
340 void BigInt::binary_encode(byte output[]) const
341  {
342  const size_t sig_bytes = bytes();
343  for(size_t i = 0; i != sig_bytes; ++i)
344  output[sig_bytes-i-1] = byte_at(i);
345  }
346 
347 /*
348 * Set this number to the value in buf
349 */
350 void BigInt::binary_decode(const byte buf[], size_t length)
351  {
352  const size_t WORD_BYTES = sizeof(word);
353 
354  clear();
355  reg.resize(round_up<size_t>((length / WORD_BYTES) + 1, 8));
356 
357  for(size_t i = 0; i != length / WORD_BYTES; ++i)
358  {
359  const size_t top = length - WORD_BYTES*i;
360  for(size_t j = WORD_BYTES; j > 0; --j)
361  reg[i] = (reg[i] << 8) | buf[top - j];
362  }
363 
364  for(size_t i = 0; i != length % WORD_BYTES; ++i)
365  reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[i];
366  }
367 
368 /*
369 * Set this number to the value in buf
370 */
372  {
373  binary_decode(buf, buf.size());
374  }
375 
376 }
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:272
word word_at(size_t n) const
Definition: bigint.h:238
size_t sig_words() const
Definition: bigint.h:290
void resize(size_t n)
Definition: secmem.h:211
void binary_encode(byte buf[]) const
Definition: bigint.cpp:340
BigInt n
Definition: numthry.cpp:26
s32bit cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:132
void binary_decode(const byte buf[], size_t length)
Definition: bigint.cpp:350
void set_bit(size_t n)
Definition: bigint.cpp:205
Sign reverse_sign() const
Definition: bigint.cpp:310
byte byte_at(size_t n) const
Definition: bigint.cpp:147
BigInt abs() const
Definition: bigint.cpp:330
bool is_negative() const
Definition: bigint.h:245
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
size_t size() const
Definition: bigint.h:284
void swap(BigInt &other)
Definition: bigint.cpp:106
byte get_byte(size_t byte_num, T input)
Definition: get_byte.h:21
void mask_bits(size_t n)
Definition: bigint.cpp:227
void copy(const T in[], size_t n)
Definition: secmem.h:120
signed int s32bit
Definition: types.h:37
unsigned char byte
Definition: types.h:22
unsigned long long u64bit
Definition: types.h:49
void grow_reg(size_t n)
Definition: bigint.cpp:115
u32bit get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:168
size_t bits() const
Definition: bigint.cpp:253
u32bit to_u32bit() const
Definition: bigint.cpp:189
RandomNumberGenerator * rng
Definition: global_rng.cpp:165
void randomize(RandomNumberGenerator &rng, size_t bitsize=0)
Definition: big_rand.cpp:29
const word * data() const
Definition: bigint.h:317
size_t size() const
Definition: secmem.h:29
void clear()
Definition: bigint.h:143
const word MP_WORD_MASK
Definition: mp_types.h:27
void swap(MemoryRegion< T > &other)
Definition: secmem.h:254
void grow_to(size_t n)
Definition: bigint.cpp:123
static BigInt decode(const byte buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:102
bool is_positive() const
Definition: bigint.h:251
BigInt operator-() const
Definition: bigint.cpp:320
void swap(Botan::MemoryRegion< T > &x, Botan::MemoryRegion< T > &y)
Definition: secmem.h:425
bool get_bit(size_t n) const
Definition: bigint.cpp:160
void flip_sign()
Definition: bigint.cpp:302
bool is_zero() const
Definition: bigint.h:176
void clear_bit(size_t n)
Definition: bigint.cpp:216
void set_sign(Sign sign)
Definition: bigint.cpp:291
const word MP_WORD_TOP_BIT
Definition: mp_types.h:28
s32bit bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_misc.cpp:41
unsigned int u32bit
Definition: types.h:32
size_t s
Definition: numthry.cpp:27
GMP_MPZ base
Definition: gmp_powm.cpp:29
const size_t MP_WORD_BITS
Definition: mp_core.h:18
Sign sign() const
Definition: bigint.h:257
size_t bytes() const
Definition: bigint.cpp:245