src/arith_uint256.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #ifndef BITCOIN_ARITH_UINT256_H
   7 #define BITCOIN_ARITH_UINT256_H
   8
   9 #include <assert.h>
  10 #include <cstring>
  11 #include <stdexcept>
  12 #include <stdint.h>
  13 #include <string>
  14 #include <vector>
  15
  16 class uint256;
  17
  18 class uint_error : public std::runtime_error {
  19 public:
  20     explicit uint_error(const std::string& str) : std::runtime_error(str) {}
  21 };
  22
  23 /** Template base class for unsigned big integers. */
  24 template<unsigned int BITS>
  25 class base_uint
  26 {
  27 protected:
  28     enum { WIDTH=BITS/32 };
  29     uint32_t pn[WIDTH];
  30 public:
  31
  32     base_uint()
  33     {
  34         for (int i = 0; i < WIDTH; i++)
  35             pn[i] = 0;
  36     }
  37
  38     base_uint(const base_uint& b)
  39     {
  40         for (int i = 0; i < WIDTH; i++)
  41             pn[i] = b.pn[i];
  42     }
  43
  44     base_uint& operator=(const base_uint& b)
  45     {
  46         for (int i = 0; i < WIDTH; i++)
  47             pn[i] = b.pn[i];
  48         return *this;
  49     }
  50
  51     base_uint(uint64_t b)
  52     {
  53         pn[0] = (unsigned int)b;
  54         pn[1] = (unsigned int)(b >> 32);
  55         for (int i = 2; i < WIDTH; i++)
  56             pn[i] = 0;
  57     }
  58
  59     explicit base_uint(const std::string& str);
  60
  61     bool operator!() const
  62     {
  63         for (int i = 0; i < WIDTH; i++)
  64             if (pn[i] != 0)
  65                 return false;
  66         return true;
  67     }
  68
  69     const base_uint operator~() const
  70     {
  71         base_uint ret;
  72         for (int i = 0; i < WIDTH; i++)
  73             ret.pn[i] = ~pn[i];
  74         return ret;
  75     }
  76
  77     const base_uint operator-() const
  78     {
  79         base_uint ret;
  80         for (int i = 0; i < WIDTH; i++)
  81             ret.pn[i] = ~pn[i];
  82         ret++;
  83         return ret;
  84     }
  85
  86     double getdouble() const;
  87
  88     base_uint& operator=(uint64_t b)
  89     {
  90         pn[0] = (unsigned int)b;
  91         pn[1] = (unsigned int)(b >> 32);
  92         for (int i = 2; i < WIDTH; i++)
  93             pn[i] = 0;
  94         return *this;
  95     }
  96
  97     base_uint& operator^=(const base_uint& b)
  98     {
  99         for (int i = 0; i < WIDTH; i++)
 100             pn[i] ^= b.pn[i];
 101         return *this;
 102     }
 103
 104     base_uint& operator&=(const base_uint& b)
 105     {
 106         for (int i = 0; i < WIDTH; i++)
 107             pn[i] &= b.pn[i];
 108         return *this;
 109     }
 110
 111     base_uint& operator|=(const base_uint& b)
 112     {
 113         for (int i = 0; i < WIDTH; i++)
 114             pn[i] |= b.pn[i];
 115         return *this;
 116     }
 117
 118     base_uint& operator^=(uint64_t b)
 119     {
 120         pn[0] ^= (unsigned int)b;
 121         pn[1] ^= (unsigned int)(b >> 32);
 122         return *this;
 123     }
 124
 125     base_uint& operator|=(uint64_t b)
 126     {
 127         pn[0] |= (unsigned int)b;
 128         pn[1] |= (unsigned int)(b >> 32);
 129         return *this;
 130     }
 131
 132     base_uint& operator<<=(unsigned int shift);
 133     base_uint& operator>>=(unsigned int shift);
 134
 135     base_uint& operator+=(const base_uint& b)
 136     {
 137         uint64_t carry = 0;
 138         for (int i = 0; i < WIDTH; i++)
 139         {
 140             uint64_t n = carry + pn[i] + b.pn[i];
 141             pn[i] = n & 0xffffffff;
 142             carry = n >> 32;
 143         }
 144         return *this;
 145     }
 146
 147     base_uint& operator-=(const base_uint& b)
 148     {
 149         *this += -b;
 150         return *this;
 151     }
 152
 153     base_uint& operator+=(uint64_t b64)
 154     {
 155         base_uint b;
 156         b = b64;
 157         *this += b;
 158         return *this;
 159     }
 160
 161     base_uint& operator-=(uint64_t b64)
 162     {
 163         base_uint b;
 164         b = b64;
 165         *this += -b;
 166         return *this;
 167     }
 168
 169     base_uint& operator*=(uint32_t b32);
 170     base_uint& operator*=(const base_uint& b);
 171     base_uint& operator/=(const base_uint& b);
 172
 173     base_uint& operator++()
 174     {
 175         // prefix operator
 176         int i = 0;
 177         while (++pn[i] == 0 && i < WIDTH-1)
 178             i++;
 179         return *this;
 180     }
 181
 182     const base_uint operator++(int)
 183     {
 184         // postfix operator
 185         const base_uint ret = *this;
 186         ++(*this);
 187         return ret;
 188     }
 189
 190     base_uint& operator--()
 191     {
 192         // prefix operator
 193         int i = 0;
 194         while (--pn[i] == (uint32_t)-1 && i < WIDTH-1)
 195             i++;
 196         return *this;
 197     }
 198
 199     const base_uint operator--(int)
 200     {
 201         // postfix operator
 202         const base_uint ret = *this;
 203         --(*this);
 204         return ret;
 205     }
 206
 207     int CompareTo(const base_uint& b) const;
 208     bool EqualTo(uint64_t b) const;
 209
 210     friend inline const base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
 211     friend inline const base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
 212     friend inline const base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
 213     friend inline const base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
 214     friend inline const base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
 215     friend inline const base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
 216     friend inline const base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
 217     friend inline const base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
 218     friend inline const base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
 219     friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
 220     friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
 221     friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
 222     friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
 223     friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
 224     friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
 225     friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
 226     friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
 227     friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
 228
 229     std::string GetHex() const;
 230     void SetHex(const char* psz);
 231     void SetHex(const std::string& str);
 232     std::string ToString() const;
 233
 234     unsigned int size() const
 235     {
 236         return sizeof(pn);
 237     }
 238
 239     /**
 240      * Returns the position of the highest bit set plus one, or zero if the
 241      * value is zero.
 242      */
 243     unsigned int bits() const;
 244
 245     uint64_t GetLow64() const
 246     {
 247         assert(WIDTH >= 2);
 248         return pn[0] | (uint64_t)pn[1] << 32;
 249     }
 250 };
 251
 252 /** 256-bit unsigned big integer. */
 253 class arith_uint256 : public base_uint<256> {
 254 public:
 255     arith_uint256() {}
 256     arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
 257     arith_uint256(uint64_t b) : base_uint<256>(b) {}
 258     explicit arith_uint256(const std::string& str) : base_uint<256>(str) {}
 259
 260     /**
 261      * The "compact" format is a representation of a whole
 262      * number N using an unsigned 32bit number similar to a
 263      * floating point format.
 264      * The most significant 8 bits are the unsigned exponent of base 256.
 265      * This exponent can be thought of as "number of bytes of N".
 266      * The lower 23 bits are the mantissa.
 267      * Bit number 24 (0x800000) represents the sign of N.
 268      * N = (-1^sign) * mantissa * 256^(exponent-3)
 269      *
 270      * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
 271      * MPI uses the most significant bit of the first byte as sign.
 272      * Thus 0x1234560000 is compact (0x05123456)
 273      * and  0xc0de000000 is compact (0x0600c0de)
 274      *
 275      * Bitcoin only uses this "compact" format for encoding difficulty
 276      * targets, which are unsigned 256bit quantities.  Thus, all the
 277      * complexities of the sign bit and using base 256 are probably an
 278      * implementation accident.
 279      */
 280     arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = NULL, bool *pfOverflow = NULL);
 281     uint32_t GetCompact(bool fNegative = false) const;
 282
 283     friend uint256 ArithToUint256(const arith_uint256 &);
 284     friend arith_uint256 UintToArith256(const uint256 &);
 285 };
 286
 287 uint256 ArithToUint256(const arith_uint256 &);
 288 arith_uint256 UintToArith256(const uint256 &);
 289
 290 #endif // BITCOIN_ARITH_UINT256_H