Botan  1.11.15
src/lib/math/bigint/bigint.cpp
Go to the documentation of this file.
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 }