Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 */
215 void BigInt::set_sign(Sign s)
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 */
226 void BigInt::flip_sign()
227 {
228 set_sign(reverse_sign());
229 }
230
231 /*
232 * Return the opposite value of the current sign
233 */
234 BigInt::Sign BigInt::reverse_sign() const
235 {
236 if(sign() == Positive)
237 return Negative;
238 return Positive;
239 }
240
241 /*
242 * Return the negation of this number
243 */
244 BigInt BigInt::operator-() const
245 {
246 BigInt x = (*this);
247 x.flip_sign();
248 return x;
249 }
250
251 /*
252 * Return the absolute value of this number
253 */
254 BigInt BigInt::abs() const
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 }
Botan::BigInt::encoded_size
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:198
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:335
Botan::BigInt::binary_encode
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:270
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:393
Botan::Invalid_Argument
Definition: exceptn.h:34
Botan::BigInt::Hexadecimal
Definition: bigint.h:29
Botan::BigInt
Definition: bigint.h:23
Botan::BigInt::Positive
Definition: bigint.h:34
Botan::BigInt::Decimal
Definition: bigint.h:29
Botan::RandomNumberGenerator
Definition: rng.h:25
Botan::bigint_cmp
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
Botan::BigInt::to_u32bit
uint32_t to_u32bit() const
Definition: bigint.cpp:141
Botan::BigInt::randomize
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
Botan::BigInt::set_bit
void set_bit(size_t n)
Definition: bigint.cpp:157
Botan::BigInt::reverse_sign
Sign reverse_sign() const
Definition: bigint.cpp:234
Botan::BigInt::abs
BigInt abs() const
Definition: bigint.cpp:254
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:348
Botan::BigInt::size
size_t size() const
Definition: bigint.h:387
Botan::BigInt::Negative
Definition: bigint.h:34
Botan::BigInt::cmp
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:98
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:184
Botan::BigInt::Sign
Sign
Definition: bigint.h:34
Botan::BigInt::data
const word * data() const
Definition: bigint.h:425
Botan::high_bit
size_t high_bit(T n)
Definition: bit_ops.h:37
Botan
Definition: alg_id.cpp:13
Botan::BigInt::Binary
Definition: bigint.h:29
Botan::BigInt::clear
void clear()
Definition: bigint.h:217
Botan::MP_WORD_MASK
const word MP_WORD_MASK
Definition: mp_types.h:27
Botan::BigInt::Base
Base
Definition: bigint.h:29
Botan::BigInt::get_substring
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:120
Botan::BigInt::grow_to
void grow_to(size_t n)
Definition: bigint.cpp:261
Botan::BigInt::is_positive
bool is_positive() const
Definition: bigint.h:354
Botan::BigInt::binary_decode
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:280
Botan::BigInt::operator-
BigInt operator-() const
Definition: bigint.cpp:244
Botan::BigInt::BigInt
BigInt()=default
Botan::BigInt::flip_sign
void flip_sign()
Definition: bigint.cpp:226
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:250
Botan::BigInt::clear_bit
void clear_bit(size_t n)
Definition: bigint.cpp:168
Botan::round_up
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:22
Botan::BigInt::set_sign
void set_sign(Sign sign)
Definition: bigint.cpp:215
Botan::Encoding_Error
Definition: exceptn.h:180
Botan::BigInt::decode
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114
Botan::BigInt::byte_at
uint8_t byte_at(size_t n) const
Definition: bigint.h:324
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21
Botan::BigInt::sign
Sign sign() const
Definition: bigint.h:360
Botan::BigInt::bytes
size_t bytes() const
Definition: bigint.cpp:176