libbobcat-dev 4.08.02-2build1 / usr / include / bobcat / bigint

#ifndef INCLUDED_BOBCAT_BIGINT_
#define INCLUDED_BOBCAT_BIGINT_

#include <iosfwd>
#include <vector>

#include <openssl/bn.h>

namespace FBB
{

class BigInt
{
    friend std::ostream &operator<<(std::ostream &out, BigInt const &bn);

    BIGNUM *d_bn;

    enum
    {
        WordMask = (1 << BN_BYTES) - 1
    };

    public:
        typedef BN_ULONG Word;

        enum Msb
        {
            MSB_UNKNOWN = -1,
            MSB_IS_ONE,
            TOP_TWO_BITS_ONE
        };
 
        enum Lsb
        {
            EVEN,
            ODD,
        };
 
        enum PrimeType
        {
            ANY = false,
            SAFE = true
        };

        BigInt();                               // 1
        BigInt(BigInt const &other);            // 3
                                                
        template<typename Type>                 // promotion OK
        BigInt(Type value);              
                                                
        explicit BigInt(BIGNUM const &bignum);  // 2 
        explicit BigInt(BIGNUM const *bignum);  // 4
        explicit BigInt(BIGNUM *bignum);        // .f   (avoids selection of
                                                //       the template)

        BigInt(char const *bigEndian, size_t length, bool negative = false);
                                                            // 5
        explicit BigInt(std::string const &bigEndian, bool negative = false);
                                                            // 6
        ~BigInt();

        BigInt &operator=(BigInt const &other);

        BigInt operator-() const;
        BigInt &negate();
        BigInt negatec() const;

        BigInt &setNegative(bool negative);
        BigInt setNegativec(bool negative) const;

        bool isNegative() const;                        // .f


        BigInt &tildeBits();
        BigInt tildeBitsc() const;

        BigInt &tildeInt();
        BigInt tildeIntc() const;

        BigInt &operator--();                   // opdec.f
        BigInt operator--(int);

        BigInt &operator++();                   // opinc.f
        BigInt operator++(int);


        class Bit;

        Bit operator[](size_t idx);             // opindex.f
                                                //  non-const BigInts:
                                                //  distinguishes lhs/rhs

        int operator[](size_t idx) const;       // opindexc.f 
                                                //  only rhs for const BigInts

        class Bit
        {
            friend Bit BigInt::operator[](size_t idx);
            friend std::ostream &operator<<(std::ostream &out, 
                                                            Bit const &bit);
            BigInt &d_bi;
            size_t d_idx;

            public:
                operator bool() const;
                Bit &operator=(bool rhs);       // assign   a bit
                Bit &operator&=(bool rhs);      // bit_and  a bit
                Bit &operator|=(bool rhs);      // bit_or   a bit
                Bit &operator^=(bool rhs);      // bit_xor  a bit

            private:
                Bit(BigInt &bi, size_t idx);
        };

        char *bigEndian() const;
        
        BigInt &operator+=(BigInt const &rhs);                  // opaddis.f
        BigInt &addMod(BigInt const &rhs, BigInt const &mod);   // .f
        BigInt addModc(BigInt const &rhs, BigInt const &mod) const;

        BigInt &operator-=(BigInt const &rhs);                  // opsubis.f
        BigInt &subMod(BigInt const &rhs, BigInt const &mod);   // .f
        BigInt subModc(BigInt const &rhs, BigInt const &mod) const;

        BigInt &operator*=(BigInt const &rhs);
        BigInt &mulMod(BigInt const &rhs, BigInt const &mod);   // .f
        BigInt mulModc(BigInt const &rhs, BigInt const &mod) const;

        BigInt &operator%=(BigInt const &rhs);
        BigInt &operator/=(BigInt const &rhs);      // integer division,

                                                    // integer division, also
                                                    // returning remainder
        BigInt &div(BigInt *remainder, BigInt const &rhs);
        BigInt divc(BigInt *remainder, BigInt const &rhs) const;

        BigInt &sqr();
        BigInt sqrc() const;

        BigInt &sqrMod(BigInt const &mod);                      // .f
        BigInt sqrModc(BigInt const &mod) const;

        BigInt &operator&=(BigInt const &rhs);
        BigInt &operator|=(BigInt const &rhs);
        BigInt &operator^=(BigInt const &rhs);

        bool isZero() const;                                    // .f
        bool isOne() const;                                     // .f
        bool isOdd() const;                                     // .f

        unsigned long ulong() const;                            // .f
        BIGNUM const &bignum() const;                           // .f

        size_t sizeInBytes() const;                             // .f
        size_t size() const;                                    // .f

        size_t nWords() const;                                  // .f
        static size_t constexpr sizeOfWord();                   // .f

        Word at(size_t index) const;
        void setWord(size_t index, Word value);

        int compare(BigInt const &other) const;                 // .f
        int uCompare(BigInt const &other) const;                // .f

        long long diophantus(long long *factor1, long long *factor2, 
                             long long const &value1, 
                             long long const &value2);
        BigInt diophantus(BigInt *factor1, BigInt *factor2, 
                          BigInt const &value1, BigInt const &value2);

        BigInt &exp(BigInt const &exponent);
        BigInt expc(BigInt const &exponent) const;
        BigInt &expMod(BigInt const &exponent, BigInt const &mod);
        BigInt expModc(BigInt const &exponent, BigInt const &mod) const;

        BigInt &gcd(BigInt const &rhs);
        BigInt gcdc(BigInt const &rhs) const;

        BigInt &inverseMod(BigInt const &mod);
        BigInt inverseModc(BigInt const &mod) const;

        BigInt &isqrt();
        BigInt isqrtc() const;

        static BigInt rand(size_t bitsSize, 
                           Msb msb = MSB_IS_ONE, Lsb lsb = ODD);

        static BigInt randRange(BigInt const &max);

        static BigInt setBigEndian(std::string const &bytes);

        static BigInt pseudoRand(size_t bitsSize, 
                           Msb msb = MSB_IS_ONE, Lsb lsb = ODD);
        static BigInt pseudoRandRange(BigInt const &max);

        static BigInt prime(size_t nBits, 
                            BigInt const *add = 0, BigInt const *rem = 0,
                            PrimeType primeType = ANY);


        static BigInt fromText(std::string const &text, int mode = 0);

        BigInt &clearBit(size_t index);
        BigInt clearBit(size_t index) const;

        bool hasBit(size_t index) const;                        // .f

        BigInt &maskBits(size_t lowerNBits);
        BigInt maskBitsc(size_t lowerNBits) const;

        BigInt &setBit(size_t index);
        BigInt setBitc(size_t index) const;

        BigInt &setBit(size_t index, bool value);
        BigInt setBitc(size_t index, bool value) const;

        BigInt &lshift();
        BigInt lshiftc() const;

        BigInt &lshift(size_t nBits);
        BigInt lshiftc(size_t nBits) const;

        BigInt &operator<<=(size_t nBits);                  // opshlis.f

        BigInt &rshift();
        BigInt rshiftc() const;

        BigInt &rshift(size_t nBits);
        BigInt rshiftc(size_t nBits) const;

        BigInt &operator>>=(size_t nBits);                  // opshris.f

        void swap(BigInt &other);

    private:
        void mod_inverse(BigInt *ret, BigInt const &mod) const;

        std::ostream &insertInto(std::ostream &out) const;
        static char *bn2oct(BIGNUM const *bn);

        void copy(BIGNUM *lhs, BIGNUM const &rhs);

        void nWordsCheck(size_t index) const;

        BigInt &checked1(
                int (*BN_op)(BIGNUM *, 
                             BIGNUM const *, BIGNUM const *), 
                BigInt const &rhs, char const *op);

        BigInt &checked2(int (*BN_op)(BIGNUM *, 
                                           BIGNUM const *, BIGNUM const *, 
                                           BIGNUM const *, 
                                           BN_CTX *),
                              BigInt const &rhs, BigInt const &mod, 
                              char const *op);

        void checked3(BIGNUM *div, BIGNUM *rem, 
                                   BigInt const &rhs, char const *op) const;

        BigInt &checked4(int (*BN_op)(BIGNUM *, 
                                     BIGNUM const *, BIGNUM const *, 
                                     BN_CTX *), 
                        BigInt const &rhs, char const *op);

        static void primeCallback(int reason, int primeNr, void *primeBase);
        static bool addDigit(char ch, BigInt &ret, BigInt const &radix, 
                                                   int (*pConv)(int));
};

template<typename Type>
BigInt::BigInt(Type value)
:
    d_bn(BN_new())
{
    bool negative = value < 0;
    if (negative)
        value = -value;

    BN_set_word(d_bn, static_cast<unsigned long>(value));

    if (negative)
        negate();
}    

inline size_t BigInt::nWords() const
{
    return (size() + BN_BYTES - 1) / BN_BYTES;
}
inline BigInt &BigInt::addMod(BigInt const &rhs, BigInt const &mod)
{
    return checked2(BN_mod_add, rhs, mod, "addMod");
}
inline BIGNUM const &BigInt::bignum() const
{
    return *d_bn;
}
inline int BigInt::compare(BigInt const &other) const
{
    return BN_cmp(d_bn, other.d_bn);
}
inline bool BigInt::hasBit(size_t index) const
{
    return BN_is_bit_set(this->d_bn, index);
}
inline bool BigInt::isNegative() const
{
    return BN_is_negative(this->d_bn);
}
inline bool BigInt::isOdd() const
{
    return BN_is_odd(d_bn);
}
inline bool BigInt::isOne() const
{
    return BN_is_one(d_bn);
}
inline bool BigInt::isZero() const
{
    return BN_is_zero(d_bn);
}
inline BigInt &BigInt::mulMod(BigInt const &rhs, BigInt const &mod)
{
    return checked2(BN_mod_mul, rhs, mod, "mulMod");
}
inline BigInt &BigInt::operator+=(BigInt const &rhs)
{
    return checked1(BN_add, rhs, "+");
}
inline BigInt::Bit::operator bool() const
{
    return d_bi.hasBit(d_idx);
}
inline BigInt &BigInt::operator--()
{
    return *this -= 1;
}
inline BigInt &BigInt::operator++()
{
    return *this += 1;
}
inline BigInt::Bit BigInt::operator[](size_t idx)
{
    Bit bit(*this, idx);
    return bit;
}
inline int BigInt::operator[](size_t idx) const
{
    return hasBit(idx);
}
inline BigInt &BigInt::operator<<=(size_t nBits)
{
    return lshift(nBits);
}
inline BigInt &BigInt::operator>>=(size_t nBits)
{
    return rshift(nBits);
}
inline BigInt &BigInt::operator-=(BigInt const &rhs)
{
    return checked1(BN_sub, rhs, "-");
}
inline size_t BigInt::size() const
{
    return BN_num_bits(d_bn);
}
inline size_t BigInt::sizeInBytes() const
{
    return BN_num_bytes(d_bn);
}
size_t constexpr BigInt::sizeOfWord()
{
    return sizeof(Word);
}
inline BigInt &BigInt::sqrMod(BigInt const &mod)
{
    return checked4(BN_mod_sqr, mod, "sqrMod");
}
inline BigInt &BigInt::subMod(BigInt const &rhs, BigInt const &mod)
{
    return checked2(BN_mod_sub, rhs, mod, "subMod");
}
inline unsigned long BigInt::ulong() const
{
    return BN_get_word(d_bn);
}
inline int BigInt::uCompare(BigInt const &other) const
{
    return BN_ucmp(d_bn, other.d_bn);
}

// Free functions

BigInt operator*(BigInt const &lhs, BigInt const &rhs);
BigInt operator/(BigInt const &lhs, BigInt const &rhs);
BigInt operator%(BigInt const &lhs, BigInt const &rhs);
BigInt operator+(BigInt const &lhs, BigInt const &rhs);
BigInt operator-(BigInt const &lhs, BigInt const &rhs);
BigInt operator>>(BigInt const &lhs, size_t rhs);
BigInt operator<<(BigInt const &lhs, size_t rhs);
BigInt operator|(BigInt const &lhs, BigInt const &rhs);
BigInt operator&(BigInt const &lhs, BigInt const &rhs);
BigInt operator^(BigInt const &lhs, BigInt const &rhs);

BigInt gcd(BigInt const &lhs, BigInt const &rhs);
BigInt inverseMod(BigInt const &lhs, BigInt const &mod);

std::istream &operator>>(std::istream &out, BigInt &bn);

int isoctdigit(int ch);

inline bool operator>(BigInt const &lhs, BigInt const &rhs) 
{
    return lhs.compare(rhs) > 0;
}
inline bool operator>=(BigInt const &lhs, BigInt const &rhs)
{
    return lhs.compare(rhs) >= 0;
}
inline std::ostream &operator<<(std::ostream &out, BigInt const &bn)
{
    return bn.insertInto(out);
}
inline bool operator==(BigInt const &lhs, BigInt const &rhs) 
{
    return lhs.compare(rhs) == 0;
}
inline bool operator!=(BigInt const &lhs, BigInt const &rhs)
{
    return lhs.compare(rhs) != 0;
}
inline bool operator<(BigInt const &lhs, BigInt const &rhs) 
{
    return lhs.compare(rhs) < 0;
}
inline bool operator<=(BigInt const &lhs, BigInt const &rhs)
{
    return lhs.compare(rhs) <= 0;
}


}   // namespace FBB


#endif