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