path: root/src/math/bigint/bigint.h

/*
* BigInt
* (C) 1999-2008 Jack Lloyd
*     2007 FlexSecure
*
* Distributed under the terms of the Botan license
*/

#ifndef BOTAN_BIGINT_H__
#define BOTAN_BIGINT_H__

#include <botan/rng.h>
#include <botan/secmem.h>
#include <botan/mp_types.h>
#include <iosfwd>

namespace Botan {

/**
* Arbitrary precision integer
*/
class BOTAN_DLL BigInt
   {
   public:
     /**
     * Base enumerator for encoding and decoding
     */
     enum Base { Octal = 8, Decimal = 10, Hexadecimal = 16, Binary = 256 };

     /**
     * Sign symbol definitions for positive and negative numbers
     */
     enum Sign { Negative = 0, Positive = 1 };

     /**
     * Number types (currently only power-of-2 supported)
     */
     enum NumberType { Power2 };

     /**
     * DivideByZero Exception
     */
     struct BOTAN_DLL DivideByZero : public Exception
        { DivideByZero() : Exception("BigInt divide by zero") {} };

     /**
     * += Operator
     * @param y the BigInt to add to this
     */
     BigInt& operator+=(const BigInt& y);

     /**
     * -= Operator
     * @param y the BigInt to subtract from this
     */
     BigInt& operator-=(const BigInt& y);

     /**
     * *= Operator
     * @param y the BigInt to multiply with this
     */
     BigInt& operator*=(const BigInt& y);

     /**
     * /= Operator
     * @param y the BigInt to divide this by
     */
     BigInt& operator/=(const BigInt& y);

     /**
     * %= Operator, modulo operator.
     * @param y the modulus to reduce this by
     */
     BigInt& operator%=(const BigInt& y);

     /**
     * %= Operator
     * @param y the modulus (word) to reduce this by
     */
     word    operator%=(word y);

     /**
     * <<= Operator
     * @param y the amount of bits to shift this left
     */
     BigInt& operator<<=(u32bit y);

     /**
     * >>= Operator
     * @param y the amount of bits to shift this right
     */
     BigInt& operator>>=(u32bit y);

     /**
     * ++ Operator
     */
     BigInt& operator++() { return (*this += 1); }

     /**
     * -- Operator
     */
     BigInt& operator--() { return (*this -= 1); }

     /**
     * ++ Operator (postfix)
     */
     BigInt  operator++(int) { BigInt x = (*this); ++(*this); return x; }

     /**
     * -- Operator (postfix)
     */
     BigInt  operator--(int) { BigInt x = (*this); --(*this); return x; }

     /**
     * Unary - Operator
     */
     BigInt operator-() const;

     /**
     * ! Operator
     */
     bool operator !() const { return (!is_nonzero()); }

     /**
     * [] Operator (array access)
     */
     word& operator[](u32bit i) { return reg[i]; }

     /**
     * [] Operator (array access)
     */
     word operator[](u32bit i) const { return reg[i]; }

     /**
     * Zeroize the BigInt
     */
     void clear() { get_reg().clear(); }

     /**
     * Compare *this to another BigInt.
     * @param n the BigInt value to compare to this.
     * @param check_signs include sign in comparison?
     * @result if (this<n) return -1, if (this>n) return 1, if both
     * values are identical return 0 [like Perl's <=> operator]
     */
     s32bit cmp(const BigInt& n, bool check_signs = true) const;

     /**
     * Test if the integer has an even value
     * @result true if the integer is even, false otherwise
     */
     bool is_even() const { return (get_bit(0) == 0); }

     /**
     * Test if the integer has an odd value
     * @result true if the integer is odd, false otherwise
     */
     bool is_odd()  const { return (get_bit(0) == 1); }

     /**
     * Test if the integer is not zero.
     * @result true if the integer is non-zero, false otherwise
     */
     bool is_nonzero() const { return (!is_zero()); }

     /**
     * Test if the integer is zero.
     * @result true if the integer is zero, false otherwise
     */
     bool is_zero() const
        {
        const u32bit sw = sig_words();

        for(u32bit i = 0; i != sw; ++i)
           if(reg[i])
              return false;
        return true;
        }

     /**
     * Set bit at specified position
     * @param n bit position to set
     */
     void set_bit(u32bit n);

     /**
     * Clear bit at specified position
     * @param n bit position to clear
     */
     void clear_bit(u32bit n);

     /**
     * Clear all but the lowest n bits
     * @param n amount of bits to keep
     */
     void mask_bits(u32bit n);

     /**
     * Return bit value at specified position
     * @param n the bit offset to test
     * @result true, if the bit at position n is set, false otherwise
     */
     bool get_bit(u32bit n) const;

     /**
     * Return (a maximum of) 32 bits of the complete value
     * @param offset the offset to start extracting
     * @param length amount of bits to extract (starting at offset)
     * @result the integer extracted from the register starting at
     * offset with specified length
     */
     u32bit get_substring(u32bit offset, u32bit length) const;

     /**
     * @param n the offset to get a byte from
     * @result byte at offset n
     */
     byte byte_at(u32bit n) const;

     /**
     * Return the word at a specified position of the internal register
     * @param n position in the register
     * @return the value at position n
     */
     word word_at(u32bit n) const
        { return ((n < size()) ? reg[n] : 0); }

     /**
     * Return the integer as an unsigned 32bit-integer-value. If the
     * value is negative OR to big to be stored in 32bits, this
     * function will throw an exception.
     * @result a 32bit-integer
     */
     u32bit to_u32bit() const;

     /**
     * Tests if the sign of the integer is negative.
     * @result true, if the integer has a negative sign,
     */
     bool is_negative() const { return (sign() == Negative); }

     /**
     * Tests if the sign of the integer is positive.
     * @result true, if the integer has a positive sign,
     */
     bool is_positive() const { return (sign() == Positive); }

     /**
     * Return the sign of the integer
     * @result the sign of the integer
     */
     Sign sign() const { return (signedness); }

     /**
     * Return the opposite sign of the represented integer value
     * @result the opposite sign of the represented integer value
     */
     Sign reverse_sign() const;

     /**
     * Flip (mutate) the sign of the integer to its opposite value
     */
     void flip_sign();

     /**
     * Set sign of the integer
     * @param sign new Sign to set
     */
     void set_sign(Sign sign);

     /**
     * @result absolute (positive) value of this
     */
     BigInt abs() const;

     /**
     * Give size of internal register
     * @result size of internal register in words
     */
     u32bit size() const { return get_reg().size(); }

     /**
     * Give significant words of the represented integer value
     * @result significant words of the represented integer value
     */
     u32bit sig_words() const
        {
        const word* x = reg.begin();
        u32bit sig = reg.size();

        while(sig && (x[sig-1] == 0))
           sig--;
        return sig;
        }

     /**
     * Give byte-length of the integer
     * @result byte-length of the represented integer value
     */
     u32bit bytes() const;

     /**
     * Get the bit-length of the integer.
     * @result bit-length of the represented integer value
     */
     u32bit bits() const;

     /**
     * Return a pointer to the big integer word register.
     * @result a pointer to the start of the internal register of
     * the integer value
     */
     const word* data() const { return reg.begin(); }

     /**
     * return a reference to the internal register containing the value
     * @result a reference to the word-array (SecureVector<word>)
     * with the internal register value (containing the integer
     * value)
     */
     SecureVector<word>& get_reg() { return reg; }

     /**
     * return a const reference to the internal register containing the value
     * @result a const reference to the word-array (SecureVector<word>)
     * with the internal register value (containing the integer value)
     */
     const SecureVector<word>& get_reg() const { return reg; }

     /**
     * Increase internal register buffer by n words
     * @param n increase by n words
     */
     void grow_reg(u32bit n);

     void grow_to(u32bit n);

     /**
     * Fill BigInt with a random number with size of bitsize
     * @param rng the random number generator to use
     * @param bitsize number of bits the created random value should have
     */
     void randomize(RandomNumberGenerator& rng, u32bit bitsize = 0);

     /**
     * Store BigInt-value in a given byte array
     * @param buf destination byte array for the integer value
     */
     void binary_encode(byte buf[]) const;

     /**
     * Read integer value from a byte array with given size
     * @param buf byte array buffer containing the integer
     * @param length size of buf
     */
     void binary_decode(const byte buf[], u32bit length);

     /**
     * Read integer value from a byte array (MemoryRegion<byte>)
     * @param buf the BigInt value to compare to this.
     */
     void binary_decode(const MemoryRegion<byte>& buf);

     u32bit encoded_size(Base = Binary) const;

     /**
     @param rng a random number generator
     @result a random integer between min and max
     */
     static BigInt random_integer(RandomNumberGenerator& rng,
                                  const BigInt& min, const BigInt& max);

     /**
     * Encode the integer value from a BigInt to a SecureVector of bytes
     * @param n the BigInt to use as integer source
     * @param base number-base of resulting byte array representation
     * @result SecureVector of bytes containing the integer with given base
     */
     static SecureVector<byte> encode(const BigInt& n, Base base = Binary);

     /**
     * Encode the integer value from a BigInt to a byte array
     * @param buf destination byte array for the encoded integer
     * value with given base
     * @param n the BigInt to use as integer source
     * @param base number-base of resulting byte array representation
     */
     static void encode(byte buf[], const BigInt& n, Base base = Binary);

     /**
     * Create a BigInt from an integer in a byte array
     * @param buf the BigInt value to compare to this.
     * @param length size of buf
     * @param base number-base of the integer in buf
     * @result BigInt-representing the given integer read from the byte array
     */
     static BigInt decode(const byte buf[], u32bit length,
                          Base base = Binary);

     static BigInt decode(const MemoryRegion<byte>&, Base = Binary);

     /**
     * Encode a BigInt to a byte array according to IEEE 1363
     * @param n the BigInt to encode
     * @param bytes the length of the resulting SecureVector<byte>
     * @result a SecureVector<byte> containing the encoded BigInt
     */
     static SecureVector<byte> encode_1363(const BigInt& n, u32bit bytes);

     /**
     * Swap BigInt-value with given BigInt.
     * @param bigint the BigInt to swap values with
     */
     void swap(BigInt& bigint);

     /**
     * Create empty BigInt
     */
     BigInt() { signedness = Positive; }

     /**
     * Create BigInt from 64bit-Integer value
     * @param n 64bit-integer
     */
     BigInt(u64bit n);

     /**
     * Copy-Constructor: clone given BigInt
     * @param bigint the BigInt to clone
     */
     BigInt(const BigInt& bigint);

     /**
     * Create BigInt from a string.
     * If the string starts with 0x the rest of the string will be
     * interpreted as hexadecimal digits.
     * If the string starts with 0 and the second character is NOT
     * an 'x' the string will be interpreted as octal digits.
     * If the string starts with non-zero digit, it will be
     * interpreted as a decimal number.
     * @param str the string to parse for an integer value
     */
     BigInt(const std::string& str);

     /**
     * Create a BigInt from an integer in a byte array
     * @param buf the BigInt value to compare to this.
     * @param length size of buf
     * @param base number-base of the integer in buf
     */
     BigInt(const byte buf[], u32bit length, Base base = Binary);

     /**
     * Create a random BigInt of the specified size
     * @param rng random number generator
     * @param bits size in bits
     */
     BigInt(RandomNumberGenerator& rng, u32bit bits);

     /**
     * Create BigInt of specified size, all zeros
     * @param sign the sign
     * @param n integer value
     */
     BigInt(Sign sign, u32bit n);

     /**
     * Create a number of the specified type and size
     * @param type the type of number to create
     * @param n the size
     */
     BigInt(NumberType type, u32bit n);

   private:
      SecureVector<word> reg;
      Sign signedness;
   };

/*
* Arithmetic Operators
*/
BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
word   BOTAN_DLL operator%(const BigInt& x, word m);
BigInt BOTAN_DLL operator<<(const BigInt& x, u32bit n);
BigInt BOTAN_DLL operator>>(const BigInt& x, u32bit n);

/*
* Comparison Operators
*/
inline bool operator==(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) == 0); }
inline bool operator!=(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) != 0); }
inline bool operator<=(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) <= 0); }
inline bool operator>=(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) >= 0); }
inline bool operator<(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) < 0); }
inline bool operator>(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) > 0); }

/*
* I/O Operators
*/
BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);

}

namespace std {

inline void swap(Botan::BigInt& a, Botan::BigInt& b) { a.swap(b); }

}

#endif