arith_uint256.h
1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2022 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 <compare> 10 #include <cstdint> 11 #include <cstring> 12 #include <limits> 13 #include <stdexcept> 14 #include <string> 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 static_assert(BITS / 32 > 0 && BITS % 32 == 0, "Template parameter BITS must be a positive multiple of 32."); 29 static constexpr int WIDTH = BITS / 32; 30 /** Big integer represented with 32-bit digits, least-significant first. */ 31 uint32_t pn[WIDTH]; 32 public: 33 34 base_uint() 35 { 36 for (int i = 0; i < WIDTH; i++) 37 pn[i] = 0; 38 } 39 40 base_uint(const base_uint& b) 41 { 42 for (int i = 0; i < WIDTH; i++) 43 pn[i] = b.pn[i]; 44 } 45 46 base_uint& operator=(const base_uint& b) 47 { 48 if (this != &b) { 49 for (int i = 0; i < WIDTH; i++) 50 pn[i] = b.pn[i]; 51 } 52 return *this; 53 } 54 55 base_uint(uint64_t b) 56 { 57 pn[0] = (unsigned int)b; 58 pn[1] = (unsigned int)(b >> 32); 59 for (int i = 2; i < WIDTH; i++) 60 pn[i] = 0; 61 } 62 63 base_uint operator~() const 64 { 65 base_uint ret; 66 for (int i = 0; i < WIDTH; i++) 67 ret.pn[i] = ~pn[i]; 68 return ret; 69 } 70 71 base_uint operator-() const 72 { 73 base_uint ret; 74 for (int i = 0; i < WIDTH; i++) 75 ret.pn[i] = ~pn[i]; 76 ++ret; 77 return ret; 78 } 79 80 double getdouble() const; 81 82 base_uint& operator=(uint64_t b) 83 { 84 pn[0] = (unsigned int)b; 85 pn[1] = (unsigned int)(b >> 32); 86 for (int i = 2; i < WIDTH; i++) 87 pn[i] = 0; 88 return *this; 89 } 90 91 base_uint& operator^=(const base_uint& b) 92 { 93 for (int i = 0; i < WIDTH; i++) 94 pn[i] ^= b.pn[i]; 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^=(uint64_t b) 113 { 114 pn[0] ^= (unsigned int)b; 115 pn[1] ^= (unsigned int)(b >> 32); 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<<=(unsigned int shift); 127 base_uint& operator>>=(unsigned int shift); 128 129 base_uint& operator+=(const base_uint& b) 130 { 131 uint64_t carry = 0; 132 for (int i = 0; i < WIDTH; i++) 133 { 134 uint64_t n = carry + pn[i] + b.pn[i]; 135 pn[i] = n & 0xffffffff; 136 carry = n >> 32; 137 } 138 return *this; 139 } 140 141 base_uint& operator-=(const base_uint& b) 142 { 143 *this += -b; 144 return *this; 145 } 146 147 base_uint& operator+=(uint64_t b64) 148 { 149 base_uint b; 150 b = b64; 151 *this += b; 152 return *this; 153 } 154 155 base_uint& operator-=(uint64_t b64) 156 { 157 base_uint b; 158 b = b64; 159 *this += -b; 160 return *this; 161 } 162 163 base_uint& operator*=(uint32_t b32); 164 base_uint& operator*=(const base_uint& b); 165 base_uint& operator/=(const base_uint& b); 166 167 base_uint& operator++() 168 { 169 // prefix operator 170 int i = 0; 171 while (i < WIDTH && ++pn[i] == 0) 172 i++; 173 return *this; 174 } 175 176 base_uint operator++(int) 177 { 178 // postfix operator 179 const base_uint ret = *this; 180 ++(*this); 181 return ret; 182 } 183 184 base_uint& operator--() 185 { 186 // prefix operator 187 int i = 0; 188 while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max()) 189 i++; 190 return *this; 191 } 192 193 base_uint operator--(int) 194 { 195 // postfix operator 196 const base_uint ret = *this; 197 --(*this); 198 return ret; 199 } 200 201 /** Numeric ordering (unlike \ref base_blob::Compare) */ 202 int CompareTo(const base_uint& b) const; 203 bool EqualTo(uint64_t b) const; 204 205 friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; } 206 friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; } 207 friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; } 208 friend inline base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; } 209 friend inline base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; } 210 friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; } 211 friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; } 212 friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; } 213 friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; } 214 friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; } 215 friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; } 216 friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; } 217 friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); } 218 219 /** Hex encoding of the number (with the most significant digits first). */ 220 std::string GetHex() const; 221 std::string ToString() const; 222 223 unsigned int size() const 224 { 225 return sizeof(pn); 226 } 227 228 /** 229 * Returns the position of the highest bit set plus one, or zero if the 230 * value is zero. 231 */ 232 unsigned int bits() const; 233 234 uint64_t GetLow64() const 235 { 236 static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter."); 237 return pn[0] | (uint64_t)pn[1] << 32; 238 } 239 }; 240 241 /** 256-bit unsigned big integer. */ 242 class arith_uint256 : public base_uint<256> { 243 public: 244 arith_uint256() = default; 245 arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {} 246 arith_uint256(uint64_t b) : base_uint<256>(b) {} 247 248 /** 249 * The "compact" format is a representation of a whole 250 * number N using an unsigned 32bit number similar to a 251 * floating point format. 252 * The most significant 8 bits are the unsigned exponent of base 256. 253 * This exponent can be thought of as "number of bytes of N". 254 * The lower 23 bits are the mantissa. 255 * Bit number 24 (0x800000) represents the sign of N. 256 * N = (-1^sign) * mantissa * 256^(exponent-3) 257 * 258 * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn(). 259 * MPI uses the most significant bit of the first byte as sign. 260 * Thus 0x1234560000 is compact (0x05123456) 261 * and 0xc0de000000 is compact (0x0600c0de) 262 * 263 * Bitcoin only uses this "compact" format for encoding difficulty 264 * targets, which are unsigned 256bit quantities. Thus, all the 265 * complexities of the sign bit and using base 256 are probably an 266 * implementation accident. 267 */ 268 arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr); 269 uint32_t GetCompact(bool fNegative = false) const; 270 271 friend uint256 ArithToUint256(const arith_uint256 &); 272 friend arith_uint256 UintToArith256(const uint256 &); 273 }; 274 275 uint256 ArithToUint256(const arith_uint256 &); 276 arith_uint256 UintToArith256(const uint256 &); 277 278 extern template class base_uint<256>; 279 280 #endif // BITCOIN_ARITH_UINT256_H