Botan  2.1.0
Crypto and TLS for C++11
bigint.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Base
3 * (C) 1999-2011,2012,2014 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/bigint.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/loadstor.h>
11 #include <botan/parsing.h>
12 #include <botan/internal/rounding.h>
13 #include <botan/internal/bit_ops.h>
14 
15 namespace Botan {
16 
17 /*
18 * Construct a BigInt from a regular number
19 */
20 BigInt::BigInt(uint64_t n)
21  {
22  if(n == 0)
23  return;
24 
25  const size_t limbs_needed = sizeof(uint64_t) / sizeof(word);
26 
27  m_reg.resize(4*limbs_needed);
28  for(size_t i = 0; i != limbs_needed; ++i)
29  m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
30  }
31 
32 /*
33 * Construct a BigInt of the specified size
34 */
35 BigInt::BigInt(Sign s, size_t size)
36  {
37  m_reg.resize(round_up(size, 8));
38  m_signedness = s;
39  }
40 
41 /*
42 * Copy constructor
43 */
44 BigInt::BigInt(const BigInt& other)
45  {
46  m_reg = other.m_reg;
47  m_signedness = other.m_signedness;
48  }
49 
50 /*
51 * Construct a BigInt from a string
52 */
53 BigInt::BigInt(const std::string& str)
54  {
55  Base base = Decimal;
56  size_t markers = 0;
57  bool negative = false;
58 
59  if(str.length() > 0 && str[0] == '-')
60  {
61  markers += 1;
62  negative = true;
63  }
64 
65  if(str.length() > markers + 2 && str[markers ] == '0' &&
66  str[markers + 1] == 'x')
67  {
68  markers += 2;
69  base = Hexadecimal;
70  }
71 
72  *this = decode(reinterpret_cast<const uint8_t*>(str.data()) + markers,
73  str.length() - markers, base);
74 
75  if(negative) set_sign(Negative);
76  else set_sign(Positive);
77  }
78 
79 /*
80 * Construct a BigInt from an encoded BigInt
81 */
82 BigInt::BigInt(const uint8_t input[], size_t length, Base base)
83  {
84  *this = decode(input, length, base);
85  }
86 
87 /*
88 * Construct a BigInt from an encoded BigInt
89 */
90 BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
91  {
92  randomize(rng, bits, set_high_bit);
93  }
94 
95 /*
96 * Comparison Function
97 */
98 int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
99  {
100  if(check_signs)
101  {
102  if(other.is_positive() && this->is_negative())
103  return -1;
104 
105  if(other.is_negative() && this->is_positive())
106  return 1;
107 
108  if(other.is_negative() && this->is_negative())
109  return (-bigint_cmp(this->data(), this->sig_words(),
110  other.data(), other.sig_words()));
111  }
112 
113  return bigint_cmp(this->data(), this->sig_words(),
114  other.data(), other.sig_words());
115  }
116 
117 /*
118 * Return bits {offset...offset+length}
119 */
120 uint32_t BigInt::get_substring(size_t offset, size_t length) const
121  {
122  if(length > 32)
123  throw Invalid_Argument("BigInt::get_substring: Substring size too big");
124 
125  uint64_t piece = 0;
126  for(size_t i = 0; i != 8; ++i)
127  {
128  const uint8_t part = byte_at((offset / 8) + (7-i));
129  piece = (piece << 8) | part;
130  }
131 
132  const uint64_t mask = (static_cast<uint64_t>(1) << length) - 1;
133  const size_t shift = (offset % 8);
134 
135  return static_cast<uint32_t>((piece >> shift) & mask);
136  }
137 
138 /*
139 * Convert this number to a uint32_t, if possible
140 */
141 uint32_t BigInt::to_u32bit() const
142  {
143  if(is_negative())
144  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
145  if(bits() > 32)
146  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
147 
148  uint32_t out = 0;
149  for(size_t i = 0; i != 4; ++i)
150  out = (out << 8) | byte_at(3-i);
151  return out;
152  }
153 
154 /*
155 * Set bit number n
156 */
157 void BigInt::set_bit(size_t n)
158  {
159  const size_t which = n / MP_WORD_BITS;
160  const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
161  if(which >= size()) grow_to(which + 1);
162  m_reg[which] |= mask;
163  }
164 
165 /*
166 * Clear bit number n
167 */
168 void BigInt::clear_bit(size_t n)
169  {
170  const size_t which = n / MP_WORD_BITS;
171  const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
172  if(which < size())
173  m_reg[which] &= ~mask;
174  }
175 
176 size_t BigInt::bytes() const
177  {
178  return round_up(bits(), 8) / 8;
179  }
180 
181 /*
182 * Count how many bits are being used
183 */
184 size_t BigInt::bits() const
185  {
186  const size_t words = sig_words();
187 
188  if(words == 0)
189  return 0;
190 
191  const size_t full_words = words - 1;
192  return (full_words * MP_WORD_BITS + high_bit(word_at(full_words)));
193  }
194 
195 /*
196 * Calcluate the size in a certain base
197 */
198 size_t BigInt::encoded_size(Base base) const
199  {
200  static const double LOG_2_BASE_10 = 0.30102999566;
201 
202  if(base == Binary)
203  return bytes();
204  else if(base == Hexadecimal)
205  return 2*bytes();
206  else if(base == Decimal)
207  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
208  else
209  throw Invalid_Argument("Unknown base for BigInt encoding");
210  }
211 
212 /*
213 * Set the sign
214 */
216  {
217  if(is_zero())
218  m_signedness = Positive;
219  else
220  m_signedness = s;
221  }
222 
223 /*
224 * Reverse the value of the sign flag
225 */
227  {
229  }
230 
231 /*
232 * Return the opposite value of the current sign
233 */
235  {
236  if(sign() == Positive)
237  return Negative;
238  return Positive;
239  }
240 
241 /*
242 * Return the negation of this number
243 */
245  {
246  BigInt x = (*this);
247  x.flip_sign();
248  return x;
249  }
250 
251 /*
252 * Return the absolute value of this number
253 */
255  {
256  BigInt x = (*this);
257  x.set_sign(Positive);
258  return x;
259  }
260 
261 void BigInt::grow_to(size_t n)
262  {
263  if(n > size())
264  m_reg.resize(round_up(n, 8));
265  }
266 
267 /*
268 * Encode this number into bytes
269 */
270 void BigInt::binary_encode(uint8_t output[]) const
271  {
272  const size_t sig_bytes = bytes();
273  for(size_t i = 0; i != sig_bytes; ++i)
274  output[sig_bytes-i-1] = byte_at(i);
275  }
276 
277 /*
278 * Set this number to the value in buf
279 */
280 void BigInt::binary_decode(const uint8_t buf[], size_t length)
281  {
282  const size_t WORD_BYTES = sizeof(word);
283 
284  clear();
285  m_reg.resize(round_up((length / WORD_BYTES) + 1, 8));
286 
287  for(size_t i = 0; i != length / WORD_BYTES; ++i)
288  {
289  const size_t top = length - WORD_BYTES*i;
290  for(size_t j = WORD_BYTES; j > 0; --j)
291  m_reg[i] = (m_reg[i] << 8) | buf[top - j];
292  }
293 
294  for(size_t i = 0; i != length % WORD_BYTES; ++i)
295  m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
296  }
297 
298 }
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:198
word word_at(size_t n) const
Definition: bigint.h:335
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:270
size_t sig_words() const
Definition: bigint.h:393
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
uint32_t to_u32bit() const
Definition: bigint.cpp:141
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
void set_bit(size_t n)
Definition: bigint.cpp:157
Sign reverse_sign() const
Definition: bigint.cpp:234
BigInt abs() const
Definition: bigint.cpp:254
bool is_negative() const
Definition: bigint.h:348
size_t size() const
Definition: bigint.h:387
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:98
size_t bits() const
Definition: bigint.cpp:184
const word * data() const
Definition: bigint.h:425
size_t high_bit(T n)
Definition: bit_ops.h:37
Definition: alg_id.cpp:13
void clear()
Definition: bigint.h:217
const word MP_WORD_MASK
Definition: mp_types.h:27
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:120
void grow_to(size_t n)
Definition: bigint.cpp:261
bool is_positive() const
Definition: bigint.h:354
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:280
BigInt operator-() const
Definition: bigint.cpp:244
BigInt()=default
void flip_sign()
Definition: bigint.cpp:226
bool is_zero() const
Definition: bigint.h:250
void clear_bit(size_t n)
Definition: bigint.cpp:168
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:22
void set_sign(Sign sign)
Definition: bigint.cpp:215
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114
uint8_t byte_at(size_t n) const
Definition: bigint.h:324
const size_t MP_WORD_BITS
Definition: mp_core.h:21
Sign sign() const
Definition: bigint.h:360
size_t bytes() const
Definition: bigint.cpp:176