src/arith_uint256.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2014 The Bitcoin 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     explicit base_uint(const std::vector<unsigned char>& vch);
  61
  62     bool operator!() const
  63     {
  64         for (int i = 0; i < WIDTH; i++)
  65             if (pn[i] != 0)
  66                 return false;
  67         return true;
  68     }
  69
  70     const base_uint operator~() const
  71     {
  72         base_uint ret;
  73         for (int i = 0; i < WIDTH; i++)
  74             ret.pn[i] = ~pn[i];
  75         return ret;
  76     }
  77
  78     const base_uint operator-() const
  79     {
  80         base_uint ret;
  81         for (int i = 0; i < WIDTH; i++)
  82             ret.pn[i] = ~pn[i];
  83         ret++;
  84         return ret;
  85     }
  86
  87     double getdouble() const;
  88
  89     base_uint& operator=(uint64_t b)
  90     {
  91         pn[0] = (unsigned int)b;
  92         pn[1] = (unsigned int)(b >> 32);
  93         for (int i = 2; i < WIDTH; i++)
  94             pn[i] = 0;
  95         return *this;
  96     }
  97
  98     base_uint& operator^=(const base_uint& b)
  99     {
 100         for (int i = 0; i < WIDTH; i++)
 101             pn[i] ^= b.pn[i];
 102         return *this;
 103     }
 104
 105     base_uint& operator&=(const base_uint& b)
 106     {
 107         for (int i = 0; i < WIDTH; i++)
 108             pn[i] &= b.pn[i];
 109         return *this;
 110     }
 111
 112     base_uint& operator|=(const base_uint& b)
 113     {
 114         for (int i = 0; i < WIDTH; i++)
 115             pn[i] |= b.pn[i];
 116         return *this;
 117     }
 118
 119     base_uint& operator^=(uint64_t b)
 120     {
 121         pn[0] ^= (unsigned int)b;
 122         pn[1] ^= (unsigned int)(b >> 32);
 123         return *this;
 124     }
 125
 126     base_uint& operator|=(uint64_t b)
 127     {
 128         pn[0] |= (unsigned int)b;
 129         pn[1] |= (unsigned int)(b >> 32);
 130         return *this;
 131     }
 132
 133     base_uint& operator<<=(unsigned int shift);
 134     base_uint& operator>>=(unsigned int shift);
 135
 136     base_uint& operator+=(const base_uint& b)
 137     {
 138         uint64_t carry = 0;
 139         for (int i = 0; i < WIDTH; i++)
 140         {
 141             uint64_t n = carry + pn[i] + b.pn[i];
 142             pn[i] = n & 0xffffffff;
 143             carry = n >> 32;
 144         }
 145         return *this;
 146     }
 147
 148     base_uint& operator-=(const base_uint& b)
 149     {
 150         *this += -b;
 151         return *this;
 152     }
 153
 154     base_uint& operator+=(uint64_t b64)
 155     {
 156         base_uint b;
 157         b = b64;
 158         *this += b;
 159         return *this;
 160     }
 161
 162     base_uint& operator-=(uint64_t b64)
 163     {
 164         base_uint b;
 165         b = b64;
 166         *this += -b;
 167         return *this;
 168     }
 169
 170     base_uint& operator*=(uint32_t b32);
 171     base_uint& operator*=(const base_uint& b);
 172     base_uint& operator/=(const base_uint& b);
 173
 174     base_uint& operator++()
 175     {
 176         // prefix operator
 177         int i = 0;
 178         while (++pn[i] == 0 && i < WIDTH-1)
 179             i++;
 180         return *this;
 181     }
 182
 183     const base_uint operator++(int)
 184     {
 185         // postfix operator
 186         const base_uint ret = *this;
 187         ++(*this);
 188         return ret;
 189     }
 190
 191     base_uint& operator--()
 192     {
 193         // prefix operator
 194         int i = 0;
 195         while (--pn[i] == (uint32_t)-1 && i < WIDTH-1)
 196             i++;
 197         return *this;
 198     }
 199
 200     const base_uint operator--(int)
 201     {
 202         // postfix operator
 203         const base_uint ret = *this;
 204         --(*this);
 205         return ret;
 206     }
 207
 208     int CompareTo(const base_uint& b) const;
 209     bool EqualTo(uint64_t b) const;
 210
 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, const base_uint& b) { return base_uint(a) ^= b; }
 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, int shift) { return base_uint(a) <<= shift; }
 220     friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
 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 memcmp(a.pn, b.pn, sizeof(a.pn)) != 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, const base_uint& b) { return a.CompareTo(b) <= 0; }
 227     friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
 228     friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
 229
 230     std::string GetHex() const;
 231     void SetHex(const char* psz);
 232     void SetHex(const std::string& str);
 233     std::string ToString() const;
 234
 235     unsigned char* begin()
 236     {
 237         return (unsigned char*)&pn[0];
 238     }
 239
 240     unsigned char* end()
 241     {
 242         return (unsigned char*)&pn[WIDTH];
 243     }
 244
 245     const unsigned char* begin() const
 246     {
 247         return (unsigned char*)&pn[0];
 248     }
 249
 250     const unsigned char* end() const
 251     {
 252         return (unsigned char*)&pn[WIDTH];
 253     }
 254
 255     unsigned int size() const
 256     {
 257         return sizeof(pn);
 258     }
 259
 260     /**
 261      * Returns the position of the highest bit set plus one, or zero if the
 262      * value is zero.
 263      */
 264     unsigned int bits() const;
 265
 266     uint64_t GetLow64() const
 267     {
 268         assert(WIDTH >= 2);
 269         return pn[0] | (uint64_t)pn[1] << 32;
 270     }
 271
 272     unsigned int GetSerializeSize(int nType, int nVersion) const
 273     {
 274         return sizeof(pn);
 275     }
 276
 277     template<typename Stream>
 278     void Serialize(Stream& s, int nType, int nVersion) const
 279     {
 280         s.write((char*)pn, sizeof(pn));
 281     }
 282
 283     template<typename Stream>
 284     void Unserialize(Stream& s, int nType, int nVersion)
 285     {
 286         s.read((char*)pn, sizeof(pn));
 287     }
 288
 289     // Temporary for migration to blob160/256
 290     uint64_t GetCheapHash() const
 291     {
 292         return GetLow64();
 293     }
 294     void SetNull()
 295     {
 296         memset(pn, 0, sizeof(pn));
 297     }
 298     bool IsNull() const
 299     {
 300         for (int i = 0; i < WIDTH; i++)
 301             if (pn[i] != 0)
 302                 return false;
 303         return true;
 304     }
 305 };
 306
 307 /** 160-bit unsigned big integer. */
 308 class arith_uint160 : public base_uint<160> {
 309 public:
 310     arith_uint160() {}
 311     arith_uint160(const base_uint<160>& b) : base_uint<160>(b) {}
 312     arith_uint160(uint64_t b) : base_uint<160>(b) {}
 313     explicit arith_uint160(const std::string& str) : base_uint<160>(str) {}
 314     explicit arith_uint160(const std::vector<unsigned char>& vch) : base_uint<160>(vch) {}
 315 };
 316
 317 /** 256-bit unsigned big integer. */
 318 class arith_uint256 : public base_uint<256> {
 319 public:
 320     arith_uint256() {}
 321     arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
 322     arith_uint256(uint64_t b) : base_uint<256>(b) {}
 323     explicit arith_uint256(const std::string& str) : base_uint<256>(str) {}
 324     explicit arith_uint256(const std::vector<unsigned char>& vch) : base_uint<256>(vch) {}
 325
 326     /**
 327      * The "compact" format is a representation of a whole
 328      * number N using an unsigned 32bit number similar to a
 329      * floating point format.
 330      * The most significant 8 bits are the unsigned exponent of base 256.
 331      * This exponent can be thought of as "number of bytes of N".
 332      * The lower 23 bits are the mantissa.
 333      * Bit number 24 (0x800000) represents the sign of N.
 334      * N = (-1^sign) * mantissa * 256^(exponent-3)
 335      *
 336      * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
 337      * MPI uses the most significant bit of the first byte as sign.
 338      * Thus 0x1234560000 is compact (0x05123456)
 339      * and  0xc0de000000 is compact (0x0600c0de)
 340      *
 341      * Bitcoin only uses this "compact" format for encoding difficulty
 342      * targets, which are unsigned 256bit quantities.  Thus, all the
 343      * complexities of the sign bit and using base 256 are probably an
 344      * implementation accident.
 345      */
 346     arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = NULL, bool *pfOverflow = NULL);
 347     uint32_t GetCompact(bool fNegative = false) const;
 348
 349     uint64_t GetHash(const arith_uint256& salt) const;
 350
 351     friend uint256 ArithToUint256(const arith_uint256 &);
 352     friend arith_uint256 UintToArith256(const uint256 &);
 353 };
 354
 355 uint256 ArithToUint256(const arith_uint256 &);
 356 arith_uint256 UintToArith256(const uint256 &);
 357
 358 #endif // BITCOIN_UINT256_H