src/uint256.h

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