/*
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