Botan
1.11.15
|
00001 /* 00002 * BigInt Base 00003 * (C) 1999-2011,2012,2014 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/bigint.h> 00009 #include <botan/internal/mp_core.h> 00010 #include <botan/get_byte.h> 00011 #include <botan/parsing.h> 00012 #include <botan/internal/rounding.h> 00013 #include <botan/internal/bit_ops.h> 00014 00015 namespace Botan { 00016 00017 /* 00018 * Construct a BigInt from a regular number 00019 */ 00020 BigInt::BigInt(u64bit n) 00021 { 00022 if(n == 0) 00023 return; 00024 00025 const size_t limbs_needed = sizeof(u64bit) / sizeof(word); 00026 00027 m_reg.resize(4*limbs_needed); 00028 for(size_t i = 0; i != limbs_needed; ++i) 00029 m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK); 00030 } 00031 00032 /* 00033 * Construct a BigInt of the specified size 00034 */ 00035 BigInt::BigInt(Sign s, size_t size) 00036 { 00037 m_reg.resize(round_up<size_t>(size, 8)); 00038 m_signedness = s; 00039 } 00040 00041 /* 00042 * Copy constructor 00043 */ 00044 BigInt::BigInt(const BigInt& other) 00045 { 00046 m_reg = other.m_reg; 00047 m_signedness = other.m_signedness; 00048 } 00049 00050 /* 00051 * Construct a BigInt from a string 00052 */ 00053 BigInt::BigInt(const std::string& str) 00054 { 00055 Base base = Decimal; 00056 size_t markers = 0; 00057 bool negative = false; 00058 00059 if(str.length() > 0 && str[0] == '-') 00060 { 00061 markers += 1; 00062 negative = true; 00063 } 00064 00065 if(str.length() > markers + 2 && str[markers ] == '0' && 00066 str[markers + 1] == 'x') 00067 { 00068 markers += 2; 00069 base = Hexadecimal; 00070 } 00071 00072 *this = decode(reinterpret_cast<const byte*>(str.data()) + markers, 00073 str.length() - markers, base); 00074 00075 if(negative) set_sign(Negative); 00076 else set_sign(Positive); 00077 } 00078 00079 /* 00080 * Construct a BigInt from an encoded BigInt 00081 */ 00082 BigInt::BigInt(const byte input[], size_t length, Base base) 00083 { 00084 *this = decode(input, length, base); 00085 } 00086 00087 /* 00088 * Construct a BigInt from an encoded BigInt 00089 */ 00090 BigInt::BigInt(RandomNumberGenerator& rng, size_t bits) 00091 { 00092 randomize(rng, bits); 00093 } 00094 00095 /* 00096 * Comparison Function 00097 */ 00098 s32bit BigInt::cmp(const BigInt& other, bool check_signs) const 00099 { 00100 if(check_signs) 00101 { 00102 if(other.is_positive() && this->is_negative()) 00103 return -1; 00104 00105 if(other.is_negative() && this->is_positive()) 00106 return 1; 00107 00108 if(other.is_negative() && this->is_negative()) 00109 return (-bigint_cmp(this->data(), this->sig_words(), 00110 other.data(), other.sig_words())); 00111 } 00112 00113 return bigint_cmp(this->data(), this->sig_words(), 00114 other.data(), other.sig_words()); 00115 } 00116 00117 /* 00118 * Return bits {offset...offset+length} 00119 */ 00120 u32bit BigInt::get_substring(size_t offset, size_t length) const 00121 { 00122 if(length > 32) 00123 throw Invalid_Argument("BigInt::get_substring: Substring size too big"); 00124 00125 u64bit piece = 0; 00126 for(size_t i = 0; i != 8; ++i) 00127 { 00128 const byte part = byte_at((offset / 8) + (7-i)); 00129 piece = (piece << 8) | part; 00130 } 00131 00132 const u64bit mask = (static_cast<u64bit>(1) << length) - 1; 00133 const size_t shift = (offset % 8); 00134 00135 return static_cast<u32bit>((piece >> shift) & mask); 00136 } 00137 00138 /* 00139 * Convert this number to a u32bit, if possible 00140 */ 00141 u32bit BigInt::to_u32bit() const 00142 { 00143 if(is_negative()) 00144 throw Encoding_Error("BigInt::to_u32bit: Number is negative"); 00145 if(bits() >= 32) 00146 throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert"); 00147 00148 u32bit out = 0; 00149 for(size_t i = 0; i != 4; ++i) 00150 out = (out << 8) | byte_at(3-i); 00151 return out; 00152 } 00153 00154 /* 00155 * Set bit number n 00156 */ 00157 void BigInt::set_bit(size_t n) 00158 { 00159 const size_t which = n / MP_WORD_BITS; 00160 const word mask = static_cast<word>(1) << (n % MP_WORD_BITS); 00161 if(which >= size()) grow_to(which + 1); 00162 m_reg[which] |= mask; 00163 } 00164 00165 /* 00166 * Clear bit number n 00167 */ 00168 void BigInt::clear_bit(size_t n) 00169 { 00170 const size_t which = n / MP_WORD_BITS; 00171 const word mask = static_cast<word>(1) << (n % MP_WORD_BITS); 00172 if(which < size()) 00173 m_reg[which] &= ~mask; 00174 } 00175 00176 /* 00177 * Count how many bits are being used 00178 */ 00179 size_t BigInt::bits() const 00180 { 00181 const size_t words = sig_words(); 00182 00183 if(words == 0) 00184 return 0; 00185 00186 const size_t full_words = words - 1; 00187 return (full_words * MP_WORD_BITS + high_bit(word_at(full_words))); 00188 } 00189 00190 /* 00191 * Calcluate the size in a certain base 00192 */ 00193 size_t BigInt::encoded_size(Base base) const 00194 { 00195 static const double LOG_2_BASE_10 = 0.30102999566; 00196 00197 if(base == Binary) 00198 return bytes(); 00199 else if(base == Hexadecimal) 00200 return 2*bytes(); 00201 else if(base == Decimal) 00202 return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1); 00203 else 00204 throw Invalid_Argument("Unknown base for BigInt encoding"); 00205 } 00206 00207 /* 00208 * Set the sign 00209 */ 00210 void BigInt::set_sign(Sign s) 00211 { 00212 if(is_zero()) 00213 m_signedness = Positive; 00214 else 00215 m_signedness = s; 00216 } 00217 00218 /* 00219 * Reverse the value of the sign flag 00220 */ 00221 void BigInt::flip_sign() 00222 { 00223 set_sign(reverse_sign()); 00224 } 00225 00226 /* 00227 * Return the opposite value of the current sign 00228 */ 00229 BigInt::Sign BigInt::reverse_sign() const 00230 { 00231 if(sign() == Positive) 00232 return Negative; 00233 return Positive; 00234 } 00235 00236 /* 00237 * Return the negation of this number 00238 */ 00239 BigInt BigInt::operator-() const 00240 { 00241 BigInt x = (*this); 00242 x.flip_sign(); 00243 return x; 00244 } 00245 00246 /* 00247 * Return the absolute value of this number 00248 */ 00249 BigInt BigInt::abs() const 00250 { 00251 BigInt x = (*this); 00252 x.set_sign(Positive); 00253 return x; 00254 } 00255 00256 /* 00257 * Encode this number into bytes 00258 */ 00259 void BigInt::binary_encode(byte output[]) const 00260 { 00261 const size_t sig_bytes = bytes(); 00262 for(size_t i = 0; i != sig_bytes; ++i) 00263 output[sig_bytes-i-1] = byte_at(i); 00264 } 00265 00266 /* 00267 * Set this number to the value in buf 00268 */ 00269 void BigInt::binary_decode(const byte buf[], size_t length) 00270 { 00271 const size_t WORD_BYTES = sizeof(word); 00272 00273 clear(); 00274 m_reg.resize(round_up<size_t>((length / WORD_BYTES) + 1, 8)); 00275 00276 for(size_t i = 0; i != length / WORD_BYTES; ++i) 00277 { 00278 const size_t top = length - WORD_BYTES*i; 00279 for(size_t j = WORD_BYTES; j > 0; --j) 00280 m_reg[i] = (m_reg[i] << 8) | buf[top - j]; 00281 } 00282 00283 for(size_t i = 0; i != length % WORD_BYTES; ++i) 00284 m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i]; 00285 } 00286 00287 }