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         static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
  35
  36         for (int i = 0; i < WIDTH; i++)
  37             pn[i] = 0;
  38     }
  39
  40     base_uint(const base_uint& b)
  41     {
  42         static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
  43
  44         for (int i = 0; i < WIDTH; i++)
  45             pn[i] = b.pn[i];
  46     }
  47
  48     base_uint& operator=(const base_uint& b)
  49     {
  50         for (int i = 0; i < WIDTH; i++)
  51             pn[i] = b.pn[i];
  52         return *this;
  53     }
  54
  55     base_uint(uint64_t b)
  56     {
  57         static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
  58
  59         pn[0] = (unsigned int)b;
  60         pn[1] = (unsigned int)(b >> 32);
  61         for (int i = 2; i < WIDTH; i++)
  62             pn[i] = 0;
  63     }
  64
  65     explicit base_uint(const std::string& str);
  66
  67     bool operator!() const
  68     {
  69         for (int i = 0; i < WIDTH; i++)
  70             if (pn[i] != 0)
  71                 return false;
  72         return true;
  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         return ret;
  81     }
  82
  83     const base_uint operator-() const
  84     {
  85         base_uint ret;
  86         for (int i = 0; i < WIDTH; i++)
  87             ret.pn[i] = ~pn[i];
  88         ret++;
  89         return ret;
  90     }
  91
  92     double getdouble() const;
  93
  94     base_uint& operator=(uint64_t b)
  95     {
  96         pn[0] = (unsigned int)b;
  97         pn[1] = (unsigned int)(b >> 32);
  98         for (int i = 2; i < WIDTH; i++)
  99             pn[i] = 0;
 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|=(const base_uint& b)
 118     {
 119         for (int i = 0; i < WIDTH; i++)
 120             pn[i] |= b.pn[i];
 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|=(uint64_t b)
 132     {
 133         pn[0] |= (unsigned int)b;
 134         pn[1] |= (unsigned int)(b >> 32);
 135         return *this;
 136     }
 137
 138     base_uint& operator<<=(unsigned int shift);
 139     base_uint& operator>>=(unsigned int shift);
 140
 141     base_uint& operator+=(const base_uint& b)
 142     {
 143         uint64_t carry = 0;
 144         for (int i = 0; i < WIDTH; i++)
 145         {
 146             uint64_t n = carry + pn[i] + b.pn[i];
 147             pn[i] = n & 0xffffffff;
 148             carry = n >> 32;
 149         }
 150         return *this;
 151     }
 152
 153     base_uint& operator-=(const base_uint& b)
 154     {
 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-=(uint64_t b64)
 168     {
 169         base_uint b;
 170         b = b64;
 171         *this += -b;
 172         return *this;
 173     }
 174
 175     base_uint& operator*=(uint32_t b32);
 176     base_uint& operator*=(const base_uint& b);
 177     base_uint& operator/=(const base_uint& b);
 178
 179     base_uint& operator++()
 180     {
 181         // prefix operator
 182         int i = 0;
 183         while (i < WIDTH && ++pn[i] == 0)
 184             i++;
 185         return *this;
 186     }
 187
 188     const base_uint operator++(int)
 189     {
 190         // postfix operator
 191         const base_uint ret = *this;
 192         ++(*this);
 193         return ret;
 194     }
 195
 196     base_uint& operator--()
 197     {
 198         // prefix operator
 199         int i = 0;
 200         while (i < WIDTH && --pn[i] == (uint32_t)-1)
 201             i++;
 202         return *this;
 203     }
 204
 205     const base_uint operator--(int)
 206     {
 207         // postfix operator
 208         const base_uint ret = *this;
 209         --(*this);
 210         return ret;
 211     }
 212
 213     int CompareTo(const base_uint& b) const;
 214     bool EqualTo(uint64_t b) const;
 215
 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, const base_uint& b) { return base_uint(a) *= b; }
 219     friend inline const base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
 220     friend inline const base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
 221     friend inline const base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
 222     friend inline const base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
 223     friend inline const base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
 224     friend inline const base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
 225     friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
 226     friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
 227     friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
 228     friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
 229     friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
 230     friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
 231     friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
 232     friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
 233     friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
 234
 235     std::string GetHex() const;
 236     void SetHex(const char* psz);
 237     void SetHex(const std::string& str);
 238     std::string ToString() const;
 239
 240     unsigned int size() const
 241     {
 242         return sizeof(pn);
 243     }
 244
 245     /**
 246      * Returns the position of the highest bit set plus one, or zero if the
 247      * value is zero.
 248      */
 249     unsigned int bits() const;
 250
 251     uint64_t GetLow64() const
 252     {
 253         static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
 254         return pn[0] | (uint64_t)pn[1] << 32;
 255     }
 256 };
 257
 258 /** 256-bit unsigned big integer. */
 259 class arith_uint256 : public base_uint<256> {
 260 public:
 261     arith_uint256() {}
 262     arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
 263     arith_uint256(uint64_t b) : base_uint<256>(b) {}
 264     explicit arith_uint256(const std::string& str) : base_uint<256>(str) {}
 265
 266     /**
 267      * The "compact" format is a representation of a whole
 268      * number N using an unsigned 32bit number similar to a
 269      * floating point format.
 270      * The most significant 8 bits are the unsigned exponent of base 256.
 271      * This exponent can be thought of as "number of bytes of N".
 272      * The lower 23 bits are the mantissa.
 273      * Bit number 24 (0x800000) represents the sign of N.
 274      * N = (-1^sign) * mantissa * 256^(exponent-3)
 275      *
 276      * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
 277      * MPI uses the most significant bit of the first byte as sign.
 278      * Thus 0x1234560000 is compact (0x05123456)
 279      * and  0xc0de000000 is compact (0x0600c0de)
 280      *
 281      * Bitcoin only uses this "compact" format for encoding difficulty
 282      * targets, which are unsigned 256bit quantities.  Thus, all the
 283      * complexities of the sign bit and using base 256 are probably an
 284      * implementation accident.
 285      */
 286     arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr);
 287     uint32_t GetCompact(bool fNegative = false) const;
 288
 289     friend uint256 ArithToUint256(const arith_uint256 &);
 290     friend arith_uint256 UintToArith256(const uint256 &);
 291 };
 292
 293 uint256 ArithToUint256(const arith_uint256 &);
 294 arith_uint256 UintToArith256(const uint256 &);
 295
 296 #endif // BITCOIN_ARITH_UINT256_H