diff options
Diffstat (limited to 'src/uint256.h')
-rw-r--r-- | src/uint256.h | 530 |
1 files changed, 111 insertions, 419 deletions
diff --git a/src/uint256.h b/src/uint256.h index ba903bc8fc..82db7758c9 100644 --- a/src/uint256.h +++ b/src/uint256.h @@ -1,35 +1,61 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2013 The Bitcoin developers +// Copyright (c) 2009-2014 The Bitcoin developers // Distributed under the MIT/X11 software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_UINT256_H #define BITCOIN_UINT256_H +#include <assert.h> +#include <stdexcept> #include <stdint.h> -#include <stdio.h> #include <string> -#include <string.h> #include <vector> -extern const signed char p_util_hexdigit[256]; // defined in util.cpp - -inline signed char HexDigit(char c) -{ - return p_util_hexdigit[(unsigned char)c]; -} +class uint_error : public std::runtime_error { +public: + explicit uint_error(const std::string& str) : std::runtime_error(str) {} +}; -/** Base class without constructors for uint256 and uint160. - * This makes the compiler let you use it in a union. - */ +/** Template base class for unsigned big integers. */ template<unsigned int BITS> class base_uint { -protected: +private: enum { WIDTH=BITS/32 }; uint32_t pn[WIDTH]; public: + base_uint() + { + for (int i = 0; i < WIDTH; i++) + pn[i] = 0; + } + + base_uint(const base_uint& b) + { + for (int i = 0; i < WIDTH; i++) + pn[i] = b.pn[i]; + } + + base_uint& operator=(const base_uint& b) + { + for (int i = 0; i < WIDTH; i++) + pn[i] = b.pn[i]; + return *this; + } + + base_uint(uint64_t b) + { + pn[0] = (unsigned int)b; + pn[1] = (unsigned int)(b >> 32); + for (int i = 2; i < WIDTH; i++) + pn[i] = 0; + } + + explicit base_uint(const std::string& str); + explicit base_uint(const std::vector<unsigned char>& vch); + bool operator!() const { for (int i = 0; i < WIDTH; i++) @@ -55,16 +81,7 @@ public: return ret; } - double getdouble() const - { - double ret = 0.0; - double fact = 1.0; - for (int i = 0; i < WIDTH; i++) { - ret += fact * pn[i]; - fact *= 4294967296.0; - } - return ret; - } + double getdouble() const; base_uint& operator=(uint64_t b) { @@ -110,39 +127,8 @@ public: return *this; } - base_uint& operator<<=(unsigned int shift) - { - base_uint a(*this); - for (int i = 0; i < WIDTH; i++) - pn[i] = 0; - int k = shift / 32; - shift = shift % 32; - for (int i = 0; i < WIDTH; i++) - { - if (i+k+1 < WIDTH && shift != 0) - pn[i+k+1] |= (a.pn[i] >> (32-shift)); - if (i+k < WIDTH) - pn[i+k] |= (a.pn[i] << shift); - } - return *this; - } - - base_uint& operator>>=(unsigned int shift) - { - base_uint a(*this); - for (int i = 0; i < WIDTH; i++) - pn[i] = 0; - int k = shift / 32; - shift = shift % 32; - for (int i = 0; i < WIDTH; i++) - { - if (i-k-1 >= 0 && shift != 0) - pn[i-k-1] |= (a.pn[i] << (32-shift)); - if (i-k >= 0) - pn[i-k] |= (a.pn[i] >> shift); - } - return *this; - } + base_uint& operator<<=(unsigned int shift); + base_uint& operator>>=(unsigned int shift); base_uint& operator+=(const base_uint& b) { @@ -178,6 +164,9 @@ public: return *this; } + base_uint& operator*=(uint32_t b32); + base_uint& operator*=(const base_uint& b); + base_uint& operator/=(const base_uint& b); base_uint& operator++() { @@ -213,134 +202,32 @@ public: return ret; } - - friend inline bool operator<(const base_uint& a, const base_uint& b) - { - for (int i = base_uint::WIDTH-1; i >= 0; i--) - { - if (a.pn[i] < b.pn[i]) - return true; - else if (a.pn[i] > b.pn[i]) - return false; - } - return false; - } - - friend inline bool operator<=(const base_uint& a, const base_uint& b) - { - for (int i = base_uint::WIDTH-1; i >= 0; i--) - { - if (a.pn[i] < b.pn[i]) - return true; - else if (a.pn[i] > b.pn[i]) - return false; - } - return true; - } - - friend inline bool operator>(const base_uint& a, const base_uint& b) - { - for (int i = base_uint::WIDTH-1; i >= 0; i--) - { - if (a.pn[i] > b.pn[i]) - return true; - else if (a.pn[i] < b.pn[i]) - return false; - } - return false; - } - - friend inline bool operator>=(const base_uint& a, const base_uint& b) - { - for (int i = base_uint::WIDTH-1; i >= 0; i--) - { - if (a.pn[i] > b.pn[i]) - return true; - else if (a.pn[i] < b.pn[i]) - return false; - } - return true; - } - - friend inline bool operator==(const base_uint& a, const base_uint& b) - { - for (int i = 0; i < base_uint::WIDTH; i++) - if (a.pn[i] != b.pn[i]) - return false; - return true; - } - - friend inline bool operator==(const base_uint& a, uint64_t b) - { - if (a.pn[0] != (unsigned int)b) - return false; - if (a.pn[1] != (unsigned int)(b >> 32)) - return false; - for (int i = 2; i < base_uint::WIDTH; i++) - if (a.pn[i] != 0) - return false; - return true; - } - - friend inline bool operator!=(const base_uint& a, const base_uint& b) - { - return (!(a == b)); - } - - friend inline bool operator!=(const base_uint& a, uint64_t b) - { - return (!(a == b)); - } - - - - std::string GetHex() const - { - char psz[sizeof(pn)*2 + 1]; - for (unsigned int i = 0; i < sizeof(pn); i++) - sprintf(psz + i*2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]); - return std::string(psz, psz + sizeof(pn)*2); - } - - void SetHex(const char* psz) - { - memset(pn,0,sizeof(pn)); - - // skip leading spaces - while (isspace(*psz)) - psz++; - - // skip 0x - if (psz[0] == '0' && tolower(psz[1]) == 'x') - psz += 2; - - // hex string to uint - const char* pbegin = psz; - while (::HexDigit(*psz) != -1) - psz++; - psz--; - unsigned char* p1 = (unsigned char*)pn; - unsigned char* pend = p1 + WIDTH * 4; - while (psz >= pbegin && p1 < pend) - { - *p1 = ::HexDigit(*psz--); - if (psz >= pbegin) - { - *p1 |= ((unsigned char)::HexDigit(*psz--) << 4); - p1++; - } - } - } - - void SetHex(const std::string& str) - { - SetHex(str.c_str()); - } - - std::string ToString() const - { - return (GetHex()); - } + int CompareTo(const base_uint& b) const; + bool EqualTo(uint64_t b) const; + + friend inline const base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; } + friend inline const base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; } + friend inline const base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; } + friend inline const base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; } + friend inline const base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; } + friend inline const base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; } + friend inline const base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; } + friend inline const base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; } + friend inline const base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; } + friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; } + friend inline bool operator==(const base_uint& a, const base_uint& b) { return a.CompareTo(b) == 0; } + friend inline bool operator!=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) != 0; } + friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; } + friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; } + friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; } + friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; } + friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); } + friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); } + + std::string GetHex() const; + void SetHex(const char* psz); + void SetHex(const std::string& str); + std::string ToString() const; unsigned char* begin() { @@ -367,269 +254,74 @@ public: return sizeof(pn); } + // Returns the position of the highest bit set plus one, or zero if the + // value is zero. + unsigned int bits() const; + uint64_t GetLow64() const { assert(WIDTH >= 2); return pn[0] | (uint64_t)pn[1] << 32; } -// unsigned int GetSerializeSize(int nType=0, int nVersion=PROTOCOL_VERSION) const unsigned int GetSerializeSize(int nType, int nVersion) const { return sizeof(pn); } template<typename Stream> -// void Serialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION) const void Serialize(Stream& s, int nType, int nVersion) const { s.write((char*)pn, sizeof(pn)); } template<typename Stream> -// void Unserialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION) void Unserialize(Stream& s, int nType, int nVersion) { s.read((char*)pn, sizeof(pn)); } - - - friend class uint160; - friend class uint256; }; -typedef base_uint<160> base_uint160; -typedef base_uint<256> base_uint256; - - - -// -// uint160 and uint256 could be implemented as templates, but to keep -// compile errors and debugging cleaner, they're copy and pasted. -// - - - -////////////////////////////////////////////////////////////////////////////// -// -// uint160 -// - -/** 160-bit unsigned integer */ -class uint160 : public base_uint160 -{ +/** 160-bit unsigned big integer. */ +class uint160 : public base_uint<160> { public: - typedef base_uint160 basetype; - - uint160() - { - for (int i = 0; i < WIDTH; i++) - pn[i] = 0; - } - - uint160(const basetype& b) - { - for (int i = 0; i < WIDTH; i++) - pn[i] = b.pn[i]; - } - - uint160& operator=(const basetype& b) - { - for (int i = 0; i < WIDTH; i++) - pn[i] = b.pn[i]; - return *this; - } - - uint160(uint64_t b) - { - pn[0] = (unsigned int)b; - pn[1] = (unsigned int)(b >> 32); - for (int i = 2; i < WIDTH; i++) - pn[i] = 0; - } - - uint160& operator=(uint64_t b) - { - pn[0] = (unsigned int)b; - pn[1] = (unsigned int)(b >> 32); - for (int i = 2; i < WIDTH; i++) - pn[i] = 0; - return *this; - } - - explicit uint160(const std::string& str) - { - SetHex(str); - } - - explicit uint160(const std::vector<unsigned char>& vch) - { - if (vch.size() == sizeof(pn)) - memcpy(pn, &vch[0], sizeof(pn)); - else - *this = 0; - } + uint160() {} + uint160(const base_uint<160>& b) : base_uint<160>(b) {} + uint160(uint64_t b) : base_uint<160>(b) {} + explicit uint160(const std::string& str) : base_uint<160>(str) {} + explicit uint160(const std::vector<unsigned char>& vch) : base_uint<160>(vch) {} }; -inline bool operator==(const uint160& a, uint64_t b) { return (base_uint160)a == b; } -inline bool operator!=(const uint160& a, uint64_t b) { return (base_uint160)a != b; } -inline const uint160 operator<<(const base_uint160& a, unsigned int shift) { return uint160(a) <<= shift; } -inline const uint160 operator>>(const base_uint160& a, unsigned int shift) { return uint160(a) >>= shift; } -inline const uint160 operator<<(const uint160& a, unsigned int shift) { return uint160(a) <<= shift; } -inline const uint160 operator>>(const uint160& a, unsigned int shift) { return uint160(a) >>= shift; } - -inline const uint160 operator^(const base_uint160& a, const base_uint160& b) { return uint160(a) ^= b; } -inline const uint160 operator&(const base_uint160& a, const base_uint160& b) { return uint160(a) &= b; } -inline const uint160 operator|(const base_uint160& a, const base_uint160& b) { return uint160(a) |= b; } -inline const uint160 operator+(const base_uint160& a, const base_uint160& b) { return uint160(a) += b; } -inline const uint160 operator-(const base_uint160& a, const base_uint160& b) { return uint160(a) -= b; } - -inline bool operator<(const base_uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; } -inline bool operator<=(const base_uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; } -inline bool operator>(const base_uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; } -inline bool operator>=(const base_uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)b; } -inline bool operator==(const base_uint160& a, const uint160& b) { return (base_uint160)a == (base_uint160)b; } -inline bool operator!=(const base_uint160& a, const uint160& b) { return (base_uint160)a != (base_uint160)b; } -inline const uint160 operator^(const base_uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; } -inline const uint160 operator&(const base_uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; } -inline const uint160 operator|(const base_uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; } -inline const uint160 operator+(const base_uint160& a, const uint160& b) { return (base_uint160)a + (base_uint160)b; } -inline const uint160 operator-(const base_uint160& a, const uint160& b) { return (base_uint160)a - (base_uint160)b; } - -inline bool operator<(const uint160& a, const base_uint160& b) { return (base_uint160)a < (base_uint160)b; } -inline bool operator<=(const uint160& a, const base_uint160& b) { return (base_uint160)a <= (base_uint160)b; } -inline bool operator>(const uint160& a, const base_uint160& b) { return (base_uint160)a > (base_uint160)b; } -inline bool operator>=(const uint160& a, const base_uint160& b) { return (base_uint160)a >= (base_uint160)b; } -inline bool operator==(const uint160& a, const base_uint160& b) { return (base_uint160)a == (base_uint160)b; } -inline bool operator!=(const uint160& a, const base_uint160& b) { return (base_uint160)a != (base_uint160)b; } -inline const uint160 operator^(const uint160& a, const base_uint160& b) { return (base_uint160)a ^ (base_uint160)b; } -inline const uint160 operator&(const uint160& a, const base_uint160& b) { return (base_uint160)a & (base_uint160)b; } -inline const uint160 operator|(const uint160& a, const base_uint160& b) { return (base_uint160)a | (base_uint160)b; } -inline const uint160 operator+(const uint160& a, const base_uint160& b) { return (base_uint160)a + (base_uint160)b; } -inline const uint160 operator-(const uint160& a, const base_uint160& b) { return (base_uint160)a - (base_uint160)b; } - -inline bool operator<(const uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; } -inline bool operator<=(const uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; } -inline bool operator>(const uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; } -inline bool operator>=(const uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)b; } -inline bool operator==(const uint160& a, const uint160& b) { return (base_uint160)a == (base_uint160)b; } -inline bool operator!=(const uint160& a, const uint160& b) { return (base_uint160)a != (base_uint160)b; } -inline const uint160 operator^(const uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; } -inline const uint160 operator&(const uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; } -inline const uint160 operator|(const uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; } -inline const uint160 operator+(const uint160& a, const uint160& b) { return (base_uint160)a + (base_uint160)b; } -inline const uint160 operator-(const uint160& a, const uint160& b) { return (base_uint160)a - (base_uint160)b; } - - - -////////////////////////////////////////////////////////////////////////////// -// -// uint256 -// - -/** 256-bit unsigned integer */ -class uint256 : public base_uint256 -{ +/** 256-bit unsigned big integer. */ +class uint256 : public base_uint<256> { public: - typedef base_uint256 basetype; - - uint256() - { - for (int i = 0; i < WIDTH; i++) - pn[i] = 0; - } - - uint256(const basetype& b) - { - for (int i = 0; i < WIDTH; i++) - pn[i] = b.pn[i]; - } - - uint256& operator=(const basetype& b) - { - for (int i = 0; i < WIDTH; i++) - pn[i] = b.pn[i]; - return *this; - } - - uint256(uint64_t b) - { - pn[0] = (unsigned int)b; - pn[1] = (unsigned int)(b >> 32); - for (int i = 2; i < WIDTH; i++) - pn[i] = 0; - } - - uint256& operator=(uint64_t b) - { - pn[0] = (unsigned int)b; - pn[1] = (unsigned int)(b >> 32); - for (int i = 2; i < WIDTH; i++) - pn[i] = 0; - return *this; - } - - explicit uint256(const std::string& str) - { - SetHex(str); - } - - explicit uint256(const std::vector<unsigned char>& vch) - { - if (vch.size() == sizeof(pn)) - memcpy(pn, &vch[0], sizeof(pn)); - else - *this = 0; - } + uint256() {} + uint256(const base_uint<256>& b) : base_uint<256>(b) {} + uint256(uint64_t b) : base_uint<256>(b) {} + explicit uint256(const std::string& str) : base_uint<256>(str) {} + explicit uint256(const std::vector<unsigned char>& vch) : base_uint<256>(vch) {} + + // The "compact" format is a representation of a whole + // number N using an unsigned 32bit number similar to a + // floating point format. + // The most significant 8 bits are the unsigned exponent of base 256. + // This exponent can be thought of as "number of bytes of N". + // The lower 23 bits are the mantissa. + // Bit number 24 (0x800000) represents the sign of N. + // N = (-1^sign) * mantissa * 256^(exponent-3) + // + // Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn(). + // MPI uses the most significant bit of the first byte as sign. + // Thus 0x1234560000 is compact (0x05123456) + // and 0xc0de000000 is compact (0x0600c0de) + // (0x05c0de00) would be -0x40de000000 + // + // Bitcoin only uses this "compact" format for encoding difficulty + // targets, which are unsigned 256bit quantities. Thus, all the + // complexities of the sign bit and using base 256 are probably an + // implementation accident. + uint256& SetCompact(uint32_t nCompact, bool *pfNegative = NULL, bool *pfOverflow = NULL); + uint32_t GetCompact(bool fNegative = false) const; }; -inline bool operator==(const uint256& a, uint64_t b) { return (base_uint256)a == b; } -inline bool operator!=(const uint256& a, uint64_t b) { return (base_uint256)a != b; } -inline const uint256 operator<<(const base_uint256& a, unsigned int shift) { return uint256(a) <<= shift; } -inline const uint256 operator>>(const base_uint256& a, unsigned int shift) { return uint256(a) >>= shift; } -inline const uint256 operator<<(const uint256& a, unsigned int shift) { return uint256(a) <<= shift; } -inline const uint256 operator>>(const uint256& a, unsigned int shift) { return uint256(a) >>= shift; } - -inline const uint256 operator^(const base_uint256& a, const base_uint256& b) { return uint256(a) ^= b; } -inline const uint256 operator&(const base_uint256& a, const base_uint256& b) { return uint256(a) &= b; } -inline const uint256 operator|(const base_uint256& a, const base_uint256& b) { return uint256(a) |= b; } -inline const uint256 operator+(const base_uint256& a, const base_uint256& b) { return uint256(a) += b; } -inline const uint256 operator-(const base_uint256& a, const base_uint256& b) { return uint256(a) -= b; } - -inline bool operator<(const base_uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; } -inline bool operator<=(const base_uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; } -inline bool operator>(const base_uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; } -inline bool operator>=(const base_uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; } -inline bool operator==(const base_uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; } -inline bool operator!=(const base_uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; } -inline const uint256 operator^(const base_uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; } -inline const uint256 operator&(const base_uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; } -inline const uint256 operator|(const base_uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; } -inline const uint256 operator+(const base_uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; } -inline const uint256 operator-(const base_uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; } - -inline bool operator<(const uint256& a, const base_uint256& b) { return (base_uint256)a < (base_uint256)b; } -inline bool operator<=(const uint256& a, const base_uint256& b) { return (base_uint256)a <= (base_uint256)b; } -inline bool operator>(const uint256& a, const base_uint256& b) { return (base_uint256)a > (base_uint256)b; } -inline bool operator>=(const uint256& a, const base_uint256& b) { return (base_uint256)a >= (base_uint256)b; } -inline bool operator==(const uint256& a, const base_uint256& b) { return (base_uint256)a == (base_uint256)b; } -inline bool operator!=(const uint256& a, const base_uint256& b) { return (base_uint256)a != (base_uint256)b; } -inline const uint256 operator^(const uint256& a, const base_uint256& b) { return (base_uint256)a ^ (base_uint256)b; } -inline const uint256 operator&(const uint256& a, const base_uint256& b) { return (base_uint256)a & (base_uint256)b; } -inline const uint256 operator|(const uint256& a, const base_uint256& b) { return (base_uint256)a | (base_uint256)b; } -inline const uint256 operator+(const uint256& a, const base_uint256& b) { return (base_uint256)a + (base_uint256)b; } -inline const uint256 operator-(const uint256& a, const base_uint256& b) { return (base_uint256)a - (base_uint256)b; } - -inline bool operator<(const uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; } -inline bool operator<=(const uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; } -inline bool operator>(const uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; } -inline bool operator>=(const uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; } -inline bool operator==(const uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; } -inline bool operator!=(const uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; } -inline const uint256 operator^(const uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; } -inline const uint256 operator&(const uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; } -inline const uint256 operator|(const uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; } -inline const uint256 operator+(const uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; } -inline const uint256 operator-(const uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; } - #endif |