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