File indexing completed on 2024-05-12 04:45:13

 /*
 Copyright (C) 1999-2007 The Botan Project. All rights reserved.
 
 Redistribution and use in source and binary forms, for any use, with or without
 modification, is permitted provided that the following conditions are met:
 
 1. Redistributions of source code must retain the above copyright notice, this
 list of conditions, and the following disclaimer.
 
 2. Redistributions in binary form must reproduce the above copyright notice,
 this list of conditions, and the following disclaimer in the documentation
 and/or other materials provided with the distribution.
 
 THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED
 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED.
 
 IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT,
 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 // LICENSEHEADER_END
 namespace QCA { // WRAPNS_LINE
 /*************************************************
  * BigInt Base Source File                        *
  * (C) 1999-2007 The Botan Project                *
  *************************************************/
 
 } // WRAPNS_LINE
 #include <botan/bigint.h>
 namespace QCA { // WRAPNS_LINE
 } // WRAPNS_LINE
 #include <botan/mp_core.h>
 namespace QCA { // WRAPNS_LINE
 } // WRAPNS_LINE
 #include <botan/bit_ops.h>
 namespace QCA { // WRAPNS_LINE
 } // WRAPNS_LINE
 #include <botan/parsing.h>
 namespace QCA { // WRAPNS_LINE
 } // WRAPNS_LINE
 #include <botan/util.h>
 namespace QCA { // WRAPNS_LINE
 
 namespace Botan {
 
 /*************************************************
  * Construct a BigInt from a regular number       *
  *************************************************/
 BigInt::BigInt(u64bit n)
 {
     set_sign(Positive);
 
     if (n == 0)
         return;
 
     const u32bit limbs_needed = sizeof(u64bit) / sizeof(word);
 
     reg.create(4 * limbs_needed);
     for (u32bit j = 0; j != limbs_needed; ++j)
         reg[j] = (word)((n >> (j * MP_WORD_BITS)) & MP_WORD_MASK);
 }
 
 /*************************************************
  * Construct a BigInt of the specified size       *
  *************************************************/
 BigInt::BigInt(Sign s, u32bit size)
 {
     reg.create(round_up(size, 8));
     signedness = s;
 }
 
 /*************************************************
  * Construct a BigInt from a "raw" BigInt         *
  *************************************************/
 BigInt::BigInt(const BigInt &b)
 {
     const u32bit b_words = b.sig_words();
 
     if (b_words) {
         reg.create(round_up(b_words, 8));
         reg.copy(b.data(), b_words);
         set_sign(b.sign());
     } else {
         reg.create(2);
         set_sign(Positive);
     }
 }
 
 BigInt &BigInt::operator=(const BigInt &) = default;
 
 /*************************************************
  * Construct a BigInt from a string               *
  *************************************************/
 BigInt::BigInt(const std::string &str)
 {
     Base   base     = Decimal;
     u32bit markers  = 0;
     bool   negative = false;
     if (str.length() > 0 && str[0] == '-') {
         markers += 1;
         negative = true;
     }
 
     if (str.length() > markers + 2 && str[markers] == '0' && str[markers + 1] == 'x') {
         markers += 2;
         base = Hexadecimal;
     } else if (str.length() > markers + 1 && str[markers] == '0') {
         markers += 1;
         base = Octal;
     }
 
     *this = decode((const byte *)str.data() + markers, str.length() - markers, base);
 
     if (negative)
         set_sign(Negative);
     else
         set_sign(Positive);
 }
 
 /*************************************************
  * Construct a BigInt from an encoded BigInt      *
  *************************************************/
 BigInt::BigInt(const byte input[], u32bit length, Base base)
 {
     set_sign(Positive);
     *this = decode(input, length, base);
 }
 
 /*************************************************
  * Swap this BigInt with another                  *
  *************************************************/
 void BigInt::swap(BigInt &other)
 {
     std::swap(reg, other.reg);
     std::swap(signedness, other.signedness);
 }
 
 /*************************************************
  * Grow the internal storage                      *
  *************************************************/
 void BigInt::grow_reg(u32bit n) const
 {
     reg.grow_to(round_up(size() + n, 8));
 }
 
 /*************************************************
  * Grow the internal storage                      *
  *************************************************/
 void BigInt::grow_to(u32bit n) const
 {
     if (n > size())
         reg.grow_to(round_up(n, 8));
 }
 
 /*************************************************
  * Comparison Function                            *
  *************************************************/
 s32bit BigInt::cmp(const BigInt &n, bool check_signs) const
 {
     if (check_signs) {
         if (n.is_positive() && this->is_negative())
             return -1;
         if (n.is_negative() && this->is_positive())
             return 1;
         if (n.is_negative() && this->is_negative())
             return (-bigint_cmp(data(), sig_words(), n.data(), n.sig_words()));
     }
     return bigint_cmp(data(), sig_words(), n.data(), n.sig_words());
 }
 
 /*************************************************
  * Convert this number to a u32bit, if possible   *
  *************************************************/
 u32bit BigInt::to_u32bit() const
 {
     if (is_negative())
         throw Encoding_Error("BigInt::to_u32bit: Number is negative");
     if (bits() >= 32)
         throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
 
     u32bit out = 0;
     for (u32bit j = 0; j != 4; ++j)
         out = (out << 8) | byte_at(3 - j);
     return out;
 }
 
 /*************************************************
  * Return byte n of this number                   *
  *************************************************/
 byte BigInt::byte_at(u32bit n) const
 {
     const u32bit WORD_BYTES = sizeof(word);
     u32bit       word_num = n / WORD_BYTES, byte_num = n % WORD_BYTES;
     if (word_num >= size())
         return 0;
     else
         return get_byte(WORD_BYTES - byte_num - 1, reg[word_num]);
 }
 
 /*************************************************
  * Return bit n of this number                    *
  *************************************************/
 bool BigInt::get_bit(u32bit n) const
 {
     return ((word_at(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
 }
 
 /*************************************************
  * Return bits {offset...offset+length}           *
  *************************************************/
 u32bit BigInt::get_substring(u32bit offset, u32bit length) const
 {
     if (length > 32)
         throw Invalid_Argument("BigInt::get_substring: Substring size too big");
 
     u64bit piece = 0;
     for (u32bit j = 0; j != 8; ++j)
         piece = (piece << 8) | byte_at((offset / 8) + (7 - j));
 
     u64bit mask  = (1 << length) - 1;
     u32bit shift = (offset % 8);
 
     return static_cast<u32bit>((piece >> shift) & mask);
 }
 
 /*************************************************
  * Set bit number n                               *
  *************************************************/
 void BigInt::set_bit(u32bit n)
 {
     const u32bit which = n / MP_WORD_BITS;
     const word   mask  = (word)1 << (n % MP_WORD_BITS);
     if (which >= size())
         grow_to(which + 1);
     reg[which] |= mask;
 }
 
 /*************************************************
  * Clear bit number n                             *
  *************************************************/
 void BigInt::clear_bit(u32bit n)
 {
     const u32bit which = n / MP_WORD_BITS;
     const word   mask  = (word)1 << (n % MP_WORD_BITS);
     if (which < size())
         reg[which] &= ~mask;
 }
 
 /*************************************************
  * Clear all but the lowest n bits                *
  *************************************************/
 void BigInt::mask_bits(u32bit n)
 {
     if (n == 0) {
         clear();
         return;
     }
     if (n >= bits())
         return;
 
     const u32bit top_word = n / MP_WORD_BITS;
     const word   mask     = ((word)1 << (n % MP_WORD_BITS)) - 1;
 
     if (top_word < size())
         for (u32bit j = top_word + 1; j != size(); ++j)
             reg[j] = 0;
 
     reg[top_word] &= mask;
 }
 
 /*************************************************
  * Count the significant words                    *
  *************************************************/
 u32bit BigInt::sig_words() const
 {
     const word *x       = data();
     u32bit      top_set = size();
 
     while (top_set >= 4) {
         word sum = x[top_set - 1] | x[top_set - 2] | x[top_set - 3] | x[top_set - 4];
         if (sum)
             break;
         else
             top_set -= 4;
     }
     while (top_set && (x[top_set - 1] == 0))
         top_set--;
     return top_set;
 }
 
 /*************************************************
  * Count how many bytes are being used            *
  *************************************************/
 u32bit BigInt::bytes() const
 {
     return (bits() + 7) / 8;
 }
 
 /*************************************************
  * Count how many bits are being used             *
  *************************************************/
 u32bit BigInt::bits() const
 {
     if (sig_words() == 0)
         return 0;
 
     u32bit full_words = sig_words() - 1, top_bits = MP_WORD_BITS;
     word   top_word = word_at(full_words), mask = MP_WORD_TOP_BIT;
 
     while (top_bits && ((top_word & mask) == 0)) {
         mask >>= 1;
         top_bits--;
     }
 
     return (full_words * MP_WORD_BITS + top_bits);
 }
 
 /*************************************************
  * Calcluate the size in a certain base           *
  *************************************************/
 u32bit BigInt::encoded_size(Base base) const
 {
     static const double LOG_2_BASE_10 = 0.30102999566;
 
     if (base == Binary)
         return bytes();
     else if (base == Hexadecimal)
         return 2 * bytes();
     else if (base == Octal)
         return ((bits() + 2) / 3);
     else if (base == Decimal)
         return (u32bit)((bits() * LOG_2_BASE_10) + 1);
     else
         throw Invalid_Argument("Unknown base for BigInt encoding");
 }
 
 /*************************************************
  * Return true if this number is zero             *
  *************************************************/
 bool BigInt::is_zero() const
 {
     for (u32bit j = 0; j != size(); ++j)
         if (reg[j])
             return false;
     return true;
 }
 
 /*************************************************
  * Set the sign                                   *
  *************************************************/
 void BigInt::set_sign(Sign s)
 {
     if (is_zero())
         signedness = Positive;
     else
         signedness = s;
 }
 
 /*************************************************
  * Reverse the value of the sign flag             *
  *************************************************/
 void BigInt::flip_sign()
 {
     set_sign(reverse_sign());
 }
 
 /*************************************************
  * Return the opposite value of the current sign  *
  *************************************************/
 BigInt::Sign BigInt::reverse_sign() const
 {
     if (sign() == Positive)
         return Negative;
     return Positive;
 }
 
 /*************************************************
  * Return the negation of this number             *
  *************************************************/
 BigInt BigInt::operator-() const
 {
     BigInt x = (*this);
     x.flip_sign();
     return x;
 }
 
 /*************************************************
  * Return the absolute value of this number       *
  *************************************************/
 BigInt BigInt::abs() const
 {
     BigInt x = (*this);
     x.set_sign(Positive);
     return x;
 }
 
 /*************************************************
  * Encode this number into bytes                  *
  *************************************************/
 void BigInt::binary_encode(byte output[]) const
 {
     const u32bit sig_bytes = bytes();
     for (u32bit j = 0; j != sig_bytes; ++j)
         output[sig_bytes - j - 1] = byte_at(j);
 }
 
 /*************************************************
  * Set this number to the value in buf            *
  *************************************************/
 void BigInt::binary_decode(const byte buf[], u32bit length)
 {
     const u32bit WORD_BYTES = sizeof(word);
     reg.create(round_up((length / WORD_BYTES) + 1, 8));
 
     for (u32bit j = 0; j != length / WORD_BYTES; ++j) {
         u32bit top = length - WORD_BYTES * j;
         for (u32bit k = WORD_BYTES; k > 0; --k)
             reg[j] = (reg[j] << 8) | buf[top - k];
     }
     for (u32bit j = 0; j != length % WORD_BYTES; ++j)
         reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[j];
 }
 
 }
 } // WRAPNS_LINE