Line data Source code
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 PIVX_ARITH_UINT256_H 7 : #define PIVX_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 : class uint512; 18 : 19 : class uint_error : public std::runtime_error { 20 : public: 21 8 : explicit uint_error(const std::string& str) : std::runtime_error(str) {} 22 : }; 23 : 24 : /** Template base class for unsigned big integers. */ 25 : template<unsigned int BITS> 26 : class base_uint 27 : { 28 : protected: 29 : static constexpr int WIDTH = BITS / 32; 30 : uint32_t pn[WIDTH]; 31 : 32 : public: 33 3243564 : base_uint() 34 : { 35 30343659 : for (int i = 0; i < WIDTH; i++) 36 27025151 : pn[i] = 0; 37 : } 38 : 39 3277807 : base_uint(const base_uint& b) 40 : { 41 32820065 : for (int i = 0; i < WIDTH; i++) 42 34000998 : pn[i] = b.pn[i]; 43 : } 44 : 45 465 : base_uint& operator=(const base_uint& b) 46 : { 47 3878076 : for (int i = 0; i < WIDTH; i++) 48 4532608 : pn[i] = b.pn[i]; 49 : return *this; 50 : } 51 : 52 1275382 : base_uint(uint64_t b) 53 : { 54 1275382 : pn[0] = (unsigned int)b; 55 1275382 : pn[1] = (unsigned int)(b >> 32); 56 8950324 : for (int i = 2; i < WIDTH; i++) 57 7756532 : pn[i] = 0; 58 : } 59 : 60 : explicit base_uint(const std::string& str); 61 : explicit base_uint(const std::vector<unsigned char>& vch); 62 : 63 2 : bool operator!() const 64 : { 65 1657 : for (int i = 0; i < WIDTH; i++) 66 1655 : if (pn[i] != 0) 67 : return false; 68 : return true; 69 : } 70 : 71 2 : const base_uint operator~() const 72 : { 73 675057 : base_uint ret; 74 675057 : for (int i = 0; i < WIDTH; i++) 75 600034 : ret.pn[i] = ~pn[i]; 76 : return ret; 77 : } 78 : 79 367384 : const base_uint operator-() const 80 : { 81 3303432 : base_uint ret; 82 3303432 : for (int i = 0; i < WIDTH; i++) 83 2936048 : ret.pn[i] = ~pn[i]; 84 367384 : ret++; 85 367384 : return ret; 86 : } 87 : 88 : double getdouble() const; 89 : 90 245206 : base_uint& operator=(uint64_t b) 91 : { 92 245206 : pn[0] = (unsigned int)b; 93 245206 : pn[1] = (unsigned int)(b >> 32); 94 1715927 : for (int i = 2; i < WIDTH; i++) 95 1470717 : pn[i] = 0; 96 : return *this; 97 : } 98 : 99 : base_uint& operator^=(const base_uint& b) 100 : { 101 126 : for (int i = 0; i < WIDTH; i++) 102 6006 : pn[i] ^= b.pn[i]; 103 : return *this; 104 : } 105 : 106 : base_uint& operator&=(const base_uint& b) 107 : { 108 660224 : for (int i = 0; i < WIDTH; i++) 109 320306 : pn[i] &= b.pn[i]; 110 : return *this; 111 : } 112 : 113 : base_uint& operator|=(const base_uint& b) 114 : { 115 3455 : for (int i = 0; i < WIDTH; i++) 116 3138 : pn[i] |= b.pn[i]; 117 : return *this; 118 : } 119 : 120 2 : base_uint& operator^=(uint64_t b) 121 : { 122 2 : pn[0] ^= (unsigned int)b; 123 2 : pn[1] ^= (unsigned int)(b >> 32); 124 : return *this; 125 : } 126 : 127 2 : base_uint& operator|=(uint64_t b) 128 : { 129 2 : pn[0] |= (unsigned int)b; 130 2 : pn[1] |= (unsigned int)(b >> 32); 131 : return *this; 132 : } 133 : 134 : base_uint& operator<<=(unsigned int shift); 135 : base_uint& operator>>=(unsigned int shift); 136 : 137 366112 : base_uint& operator+=(const base_uint& b) 138 : { 139 366538 : uint64_t carry = 0; 140 15197346 : for (int i = 0; i < WIDTH; i++) 141 : { 142 9488667 : uint64_t n = carry + pn[i] + b.pn[i]; 143 9488667 : pn[i] = n & 0xffffffff; 144 9488667 : carry = n >> 32; 145 : } 146 : return *this; 147 : } 148 : 149 366538 : base_uint& operator-=(const base_uint& b) 150 : { 151 366538 : *this += -b; 152 366538 : return *this; 153 : } 154 : 155 150810 : base_uint& operator+=(uint64_t b64) 156 : { 157 150810 : base_uint b; 158 1356808 : b = b64; 159 150810 : *this += b; 160 150810 : return *this; 161 : } 162 : 163 2 : base_uint& operator-=(uint64_t b64) 164 : { 165 2 : base_uint b; 166 2 : b = b64; 167 2 : *this += -b; 168 2 : return *this; 169 : } 170 : 171 : base_uint& operator*=(uint32_t b32); 172 : base_uint& operator*=(const base_uint& b); 173 : base_uint& operator/=(const base_uint& b); 174 : 175 : base_uint& operator++() 176 : { 177 : // prefix operator 178 : int i = 0; 179 5089 : while (++pn[i] == 0 && i < WIDTH-1) 180 5085 : i++; 181 : return *this; 182 : } 183 : 184 : const base_uint operator++(int) 185 : { 186 : // postfix operator 187 372883 : const base_uint ret = *this; 188 366112 : ++(*this); 189 : return ret; 190 : } 191 : 192 2 : base_uint& operator--() 193 : { 194 : // prefix operator 195 : int i = 0; 196 2848 : while (--pn[i] == (uint32_t)-1 && i < WIDTH-1) 197 2432 : i++; 198 : return *this; 199 : } 200 : 201 : const base_uint operator--(int) 202 : { 203 : // postfix operator 204 1630 : const base_uint ret = *this; 205 414 : --(*this); 206 : return ret; 207 : } 208 : 209 : int CompareTo(const base_uint& b) const; 210 : bool EqualTo(uint64_t b) const; 211 : 212 12156062 : friend inline const base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; } 213 89054 : friend inline const base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; } 214 204 : friend inline const base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; } 215 943868 : friend inline const base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; } 216 513 : friend inline const base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; } 217 680544 : friend inline const base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; } 218 13620 : friend inline const base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; } 219 539811 : friend inline const base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; } 220 569721 : friend inline const base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; } 221 6268 : friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; } 222 62328 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; } 223 21261 : friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; } 224 96230956 : friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; } 225 65355915 : friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; } 226 32344309 : friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; } 227 1469 : friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; } 228 12 : friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); } 229 416 : friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); } 230 : 231 : std::string GetHex() const; 232 : void SetHex(const char* psz); 233 : void SetHex(const std::string& str); 234 : std::string ToString() const; 235 : std::string ToStringReverseEndian() const; 236 : 237 6 : unsigned char* begin() 238 : { 239 : return (unsigned char*)&pn[0]; 240 : } 241 : 242 2 : unsigned char* end() 243 : { 244 : return (unsigned char*)&pn[WIDTH]; 245 : } 246 : 247 6676 : const unsigned char* begin() const 248 : { 249 6668 : return (unsigned char*)&pn[0]; 250 : } 251 : 252 8 : const unsigned char* end() const 253 : { 254 : return (unsigned char*)&pn[WIDTH]; 255 : } 256 : 257 8 : unsigned int size() const 258 : { 259 : return sizeof(pn); 260 : } 261 : 262 : uint64_t Get64(int n = 0) const 263 : { 264 : return pn[2 * n] | (uint64_t)pn[2 * n + 1] << 32; 265 : } 266 : 267 0 : uint32_t Get32(int n = 0) const 268 : { 269 0 : return pn[2 * n]; 270 : } 271 : /** 272 : * Returns the position of the highest bit set plus one, or zero if the 273 : * value is zero. 274 : */ 275 : unsigned int bits() const; 276 : 277 198400 : uint64_t GetLow64() const 278 : { 279 : assert(WIDTH >= 2); 280 196991 : return pn[0] | (uint64_t)pn[1] << 32; 281 : } 282 : 283 : template<typename Stream> 284 43651 : void Serialize(Stream& s) const 285 : { 286 43647 : s.write((char*)pn, sizeof(pn)); 287 : } 288 : 289 : template<typename Stream> 290 6 : void Unserialize(Stream& s) 291 : { 292 6 : s.read((char*)pn, sizeof(pn)); 293 : } 294 : 295 : void SetNull() 296 : { 297 : memset(pn, 0, sizeof(pn)); 298 : } 299 : 300 : bool IsNull() const 301 : { 302 2032325 : for (int i = 0; i < WIDTH; i++) 303 2032325 : if (pn[i] != 0) 304 : return false; 305 : return true; 306 : } 307 : 308 : friend class uint160; 309 : friend class uint256; 310 : friend class uint512; 311 : 312 : friend class arith_uint160; 313 : friend class arith_uint256; 314 : friend class arith_uint512; 315 : }; 316 : 317 : /** 160-bit unsigned big integer. */ 318 11723 : class arith_uint160 : public base_uint<160> { 319 : public: 320 334 : arith_uint160() {} 321 6719 : arith_uint160(const base_uint<160>& b) : base_uint<160>(b) {} 322 349 : arith_uint160(uint64_t b) : base_uint<160>(b) {} 323 14 : explicit arith_uint160(const std::string& str) : base_uint<160>(str) {} 324 824 : explicit arith_uint160(const std::vector<unsigned char>& vch) : base_uint<160>(vch) {} 325 : }; 326 : 327 : /** 256-bit unsigned big integer. */ 328 5444736 : class arith_uint256 : public base_uint<256> { 329 : public: 330 18887322 : arith_uint256() {} 331 2275600 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {} 332 3250842 : arith_uint256(uint64_t b) : base_uint<256>(b) {} 333 20 : explicit arith_uint256(const std::string& str) : base_uint<256>(str) {} 334 1304 : explicit arith_uint256(const std::vector<unsigned char>& vch) : base_uint<256>(vch) {} 335 : 336 : /** 337 : * The "compact" format is a representation of a whole 338 : * number N using an unsigned 32bit number similar to a 339 : * floating point format. 340 : * The most significant 8 bits are the unsigned exponent of base 256. 341 : * This exponent can be thought of as "number of bytes of N". 342 : * The lower 23 bits are the mantissa. 343 : * Bit number 24 (0x800000) represents the sign of N. 344 : * N = (-1^sign) * mantissa * 256^(exponent-3) 345 : * 346 : * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn(). 347 : * MPI uses the most significant bit of the first byte as sign. 348 : * Thus 0x1234560000 is compact (0x05123456) 349 : * and 0xc0de000000 is compact (0x0600c0de) 350 : * 351 : * Bitcoin only uses this "compact" format for encoding difficulty 352 : * targets, which are unsigned 256bit quantities. Thus, all the 353 : * complexities of the sign bit and using base 256 are probably an 354 : * implementation accident. 355 : */ 356 : arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr); 357 : uint32_t GetCompact(bool fNegative = false) const; 358 0 : uint32_t Get32(int n = 0) const { return pn[2 * n]; } 359 : 360 : friend arith_uint256 UintToArith256(const uint256 &a); 361 : friend uint256 ArithToUint256(const arith_uint256 &a); 362 : }; 363 : 364 : /** 512-bit unsigned big integer. */ 365 51 : class arith_uint512 : public base_uint<512> { 366 : public: 367 120028 : arith_uint512() {} 368 54 : arith_uint512(const base_uint<512>& b) : base_uint<512>(b) {} 369 80016 : arith_uint512(uint64_t b) : base_uint<512>(b) {} 370 2 : explicit arith_uint512(const std::string& str) : base_uint<512>(str) {} 371 : explicit arith_uint512(const std::vector<unsigned char>& vch) : base_uint<512>(vch) {} 372 : 373 : uint256 trim256() const; 374 : 375 : friend arith_uint512 UintToArith512(const uint512 &a); 376 : friend uint512 ArithToUint512(const arith_uint512 &a); 377 : 378 : }; 379 : 380 : uint256 ArithToUint256(const arith_uint256 &); 381 : arith_uint256 UintToArith256(const uint256 &); 382 : uint512 ArithToUint512(const arith_uint512 &); 383 : arith_uint512 UintToArith512(const uint512 &); 384 : 385 : const arith_uint256 ARITH_UINT256_ZERO = arith_uint256(); 386 : const arith_uint256 ARITH_UINT256_ONE = arith_uint256(1); 387 : 388 : #endif // PIVX_ARITH_UINT256_H