1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2012 The Bitcoin developers
3 // Distributed under the MIT/X11 software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 #ifndef BITCOIN_UINT256_H
6 #define BITCOIN_UINT256_H
15 /** Base class without constructors for uint256 and uint160.
16 * This makes the compiler let u use it in a union.
18 template<unsigned int BITS>
22 enum { WIDTH=BITS/32 };
29 for (int i = 0; i < WIDTH; i++)
30 ret.pn[i] = std::numeric_limits<uint32_t>::max();
34 bool operator!() const
36 for (int i = 0; i < WIDTH; i++)
42 const base_uint operator~() const
45 for (int i = 0; i < WIDTH; i++)
50 const base_uint operator-() const
53 for (int i = 0; i < WIDTH; i++)
59 double getdouble() const
63 for (int i = 0; i < WIDTH; i++) {
70 base_uint& operator=(uint64_t b)
73 pn[1] = (uint32_t)(b >> 32);
74 for (int i = 2; i < WIDTH; i++)
79 base_uint& operator^=(const base_uint& b)
81 for (int i = 0; i < WIDTH; i++)
86 base_uint& operator&=(const base_uint& b)
88 for (int i = 0; i < WIDTH; i++)
93 base_uint& operator|=(const base_uint& b)
95 for (int i = 0; i < WIDTH; i++)
100 base_uint& operator^=(uint64_t b)
102 pn[0] ^= (uint32_t)b;
103 pn[1] ^= (uint32_t)(b >> 32);
107 base_uint& operator|=(uint64_t b)
109 pn[0] |= (uint32_t)b;
110 pn[1] |= (uint32_t)(b >> 32);
114 base_uint& operator<<=(unsigned int shift)
117 for (int i = 0; i < WIDTH; i++)
121 for (int i = 0; i < WIDTH; i++)
123 if (i+k+1 < WIDTH && shift != 0)
124 pn[i+k+1] |= (a.pn[i] >> (32-shift));
126 pn[i+k] |= (a.pn[i] << shift);
131 base_uint& operator>>=(unsigned int shift)
134 for (int i = 0; i < WIDTH; i++)
138 for (int i = 0; i < WIDTH; i++)
140 if (i-k-1 >= 0 && shift != 0)
141 pn[i-k-1] |= (a.pn[i] << (32-shift));
143 pn[i-k] |= (a.pn[i] >> shift);
148 base_uint& operator+=(const base_uint& b)
151 for (int i = 0; i < WIDTH; i++)
153 uint64_t n = carry + pn[i] + b.pn[i];
154 pn[i] = n & 0xffffffff;
160 base_uint& operator-=(const base_uint& b)
166 base_uint& operator+=(uint64_t b64)
174 base_uint& operator-=(uint64_t b64)
183 base_uint& operator++()
187 while (++pn[i] == 0 && i < WIDTH-1)
192 const base_uint operator++(int)
195 const base_uint ret = *this;
200 base_uint& operator--()
204 while (--pn[i] == -1 && i < WIDTH-1)
209 const base_uint operator--(int)
212 const base_uint ret = *this;
218 friend inline bool operator<(const base_uint& a, const base_uint& b)
220 for (int i = base_uint::WIDTH-1; i >= 0; i--)
222 if (a.pn[i] < b.pn[i])
224 else if (a.pn[i] > b.pn[i])
230 friend inline bool operator<=(const base_uint& a, const base_uint& b)
232 for (int i = base_uint::WIDTH-1; i >= 0; i--)
234 if (a.pn[i] < b.pn[i])
236 else if (a.pn[i] > b.pn[i])
242 friend inline bool operator>(const base_uint& a, const base_uint& b)
244 for (int i = base_uint::WIDTH-1; i >= 0; i--)
246 if (a.pn[i] > b.pn[i])
248 else if (a.pn[i] < b.pn[i])
254 friend inline bool operator>=(const base_uint& a, const base_uint& b)
256 for (int i = base_uint::WIDTH-1; i >= 0; i--)
258 if (a.pn[i] > b.pn[i])
260 else if (a.pn[i] < b.pn[i])
266 friend inline bool operator==(const base_uint& a, const base_uint& b)
268 for (int i = 0; i < base_uint::WIDTH; i++)
269 if (a.pn[i] != b.pn[i])
274 friend inline bool operator==(const base_uint& a, uint64_t b)
276 if (a.pn[0] != (uint32_t)b)
278 if (a.pn[1] != (uint32_t)(b >> 32))
280 for (int i = 2; i < base_uint::WIDTH; i++)
286 friend inline bool operator!=(const base_uint& a, const base_uint& b)
291 friend inline bool operator!=(const base_uint& a, uint64_t b)
296 std::string GetHex() const
298 std::stringstream ss;
299 size_t pn_size = sizeof(pn) / sizeof(pn[0]);
300 for (size_t i = 1; i <= pn_size; i++)
301 ss << std::setfill('0') << std::setw(8) << std::setbase(16) << pn[pn_size-i];
305 void SetHex(const char* psz)
307 for (int i = 0; i < WIDTH; i++)
310 // skip leading spaces
311 while (isspace(*psz))
315 if (psz[0] == '0' && tolower(psz[1]) == 'x')
318 // hex string to uint
319 static const unsigned char phexdigit[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0 };
320 const char* pbegin = psz;
321 while (phexdigit[(unsigned char)*psz] || *psz == '0')
324 unsigned char* p1 = (unsigned char*)pn;
325 unsigned char* pend = p1 + WIDTH * 4;
326 while (psz >= pbegin && p1 < pend)
328 *p1 = phexdigit[(unsigned char)*psz--];
331 *p1 |= (phexdigit[(unsigned char)*psz--] << 4);
337 void SetHex(const std::string& str)
342 std::string ToString() const
347 unsigned char* begin() const
349 return (unsigned char*)&pn[0];
352 unsigned char* end() const
354 return (unsigned char*)&pn[WIDTH];
357 std::vector<unsigned char> getBytes()
359 return std::vector<unsigned char>(begin(), end());
367 uint64_t Get64(int n=0) const
369 return pn[2*n] | (uint64_t)pn[2*n+1] << 32;
372 uint32_t Get32(int n=0) const
377 unsigned int GetSerializeSize(int nType, int nVersion) const
382 unsigned int bits() const
384 for (int pos = WIDTH - 1; pos >= 0; pos--) {
386 for (int bits = 31; bits > 0; bits--) {
387 if (pn[pos] & 1 << bits)
388 return 32 * pos + bits + 1;
396 template<typename Stream>
397 void Serialize(Stream& s, int nType, int nVersion) const
399 s.write((char*)pn, sizeof(pn));
402 template<typename Stream>
403 void Unserialize(Stream& s, int nType, int nVersion)
405 s.read((char*)pn, sizeof(pn));
408 friend class uint160;
409 friend class uint256;
412 typedef base_uint<160> base_uint160;
413 typedef base_uint<256> base_uint256;
416 // uint160 and uint256 could be implemented as templates, but to keep
417 // compile errors and debugging cleaner, they're copy and pasted.
422 //////////////////////////////////////////////////////////////////////////////
427 /** 160-bit unsigned integer */
428 class uint160 : public base_uint160
431 typedef base_uint160 basetype;
434 uint160(const basetype& b);
435 uint160& operator=(const basetype& b);
437 uint160& operator=(uint64_t b);
438 explicit uint160(const std::string& str);
439 explicit uint160(const std::vector<unsigned char>& vch);
442 inline bool operator==(const uint160& a, uint64_t b) { return (base_uint160)a == b; }
443 inline bool operator!=(const uint160& a, uint64_t b) { return (base_uint160)a != b; }
444 inline const uint160 operator<<(const base_uint160& a, unsigned int shift) { return uint160(a) <<= shift; }
445 inline const uint160 operator>>(const base_uint160& a, unsigned int shift) { return uint160(a) >>= shift; }
446 inline const uint160 operator<<(const uint160& a, unsigned int shift) { return uint160(a) <<= shift; }
447 inline const uint160 operator>>(const uint160& a, unsigned int shift) { return uint160(a) >>= shift; }
449 inline const uint160 operator^(const base_uint160& a, const base_uint160& b) { return uint160(a) ^= b; }
450 inline const uint160 operator&(const base_uint160& a, const base_uint160& b) { return uint160(a) &= b; }
451 inline const uint160 operator|(const base_uint160& a, const base_uint160& b) { return uint160(a) |= b; }
452 inline const uint160 operator+(const base_uint160& a, const base_uint160& b) { return uint160(a) += b; }
453 inline const uint160 operator-(const base_uint160& a, const base_uint160& b) { return uint160(a) -= b; }
455 inline bool operator<(const base_uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; }
456 inline bool operator<=(const base_uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; }
457 inline bool operator>(const base_uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; }
458 inline bool operator>=(const base_uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)b; }
459 inline bool operator==(const base_uint160& a, const uint160& b) { return (base_uint160)a == (base_uint160)b; }
460 inline bool operator!=(const base_uint160& a, const uint160& b) { return (base_uint160)a != (base_uint160)b; }
461 inline const uint160 operator^(const base_uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
462 inline const uint160 operator&(const base_uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; }
463 inline const uint160 operator|(const base_uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; }
464 inline const uint160 operator+(const base_uint160& a, const uint160& b) { return (base_uint160)a + (base_uint160)b; }
465 inline const uint160 operator-(const base_uint160& a, const uint160& b) { return (base_uint160)a - (base_uint160)b; }
467 inline bool operator<(const uint160& a, const base_uint160& b) { return (base_uint160)a < (base_uint160)b; }
468 inline bool operator<=(const uint160& a, const base_uint160& b) { return (base_uint160)a <= (base_uint160)b; }
469 inline bool operator>(const uint160& a, const base_uint160& b) { return (base_uint160)a > (base_uint160)b; }
470 inline bool operator>=(const uint160& a, const base_uint160& b) { return (base_uint160)a >= (base_uint160)b; }
471 inline bool operator==(const uint160& a, const base_uint160& b) { return (base_uint160)a == (base_uint160)b; }
472 inline bool operator!=(const uint160& a, const base_uint160& b) { return (base_uint160)a != (base_uint160)b; }
473 inline const uint160 operator^(const uint160& a, const base_uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
474 inline const uint160 operator&(const uint160& a, const base_uint160& b) { return (base_uint160)a & (base_uint160)b; }
475 inline const uint160 operator|(const uint160& a, const base_uint160& b) { return (base_uint160)a | (base_uint160)b; }
476 inline const uint160 operator+(const uint160& a, const base_uint160& b) { return (base_uint160)a + (base_uint160)b; }
477 inline const uint160 operator-(const uint160& a, const base_uint160& b) { return (base_uint160)a - (base_uint160)b; }
479 inline bool operator<(const uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; }
480 inline bool operator<=(const uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; }
481 inline bool operator>(const uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; }
482 inline bool operator>=(const uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)b; }
483 inline bool operator==(const uint160& a, const uint160& b) { return (base_uint160)a == (base_uint160)b; }
484 inline bool operator!=(const uint160& a, const uint160& b) { return (base_uint160)a != (base_uint160)b; }
485 inline const uint160 operator^(const uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
486 inline const uint160 operator&(const uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; }
487 inline const uint160 operator|(const uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; }
488 inline const uint160 operator+(const uint160& a, const uint160& b) { return (base_uint160)a + (base_uint160)b; }
489 inline const uint160 operator-(const uint160& a, const uint160& b) { return (base_uint160)a - (base_uint160)b; }
496 //////////////////////////////////////////////////////////////////////////////
502 /** Errors thrown by the uint256 class */
503 class uint256_error : public std::exception
506 explicit uint256_error(const std::string& error_message) : what_(error_message) {}
508 virtual const char* what() const throw () { return what_.c_str(); }
509 virtual ~uint256_error() throw () {}
514 /** 256-bit unsigned integer */
515 class uint256 : public base_uint256
518 typedef base_uint256 basetype;
521 uint256(const basetype& b);
522 uint256& operator=(const basetype& b);
524 uint256& operator=(uint64_t b);
525 uint256& SetCompact(uint32_t nCompact, bool *pfNegative = NULL, bool *pfOverflow = NULL);
526 uint32_t GetCompact(bool fNegative = false) const;
527 uint256& operator*=(uint32_t b32);
528 uint256& operator*=(const uint256& b);
529 uint256& operator/=(const uint256& b);
530 explicit uint256(const std::string& str);
531 explicit uint256(const std::vector<unsigned char>& vch);
534 inline bool operator==(const uint256& a, uint64_t b) { return (base_uint256)a == b; }
535 inline bool operator!=(const uint256& a, uint64_t b) { return (base_uint256)a != b; }
536 inline const uint256 operator<<(const base_uint256& a, unsigned int shift) { return uint256(a) <<= shift; }
537 inline const uint256 operator>>(const base_uint256& a, unsigned int shift) { return uint256(a) >>= shift; }
538 inline const uint256 operator<<(const uint256& a, unsigned int shift) { return uint256(a) <<= shift; }
539 inline const uint256 operator>>(const uint256& a, unsigned int shift) { return uint256(a) >>= shift; }
541 inline const uint256 operator^(const base_uint256& a, const base_uint256& b) { return uint256(a) ^= b; }
542 inline const uint256 operator&(const base_uint256& a, const base_uint256& b) { return uint256(a) &= b; }
543 inline const uint256 operator|(const base_uint256& a, const base_uint256& b) { return uint256(a) |= b; }
544 inline const uint256 operator+(const base_uint256& a, const base_uint256& b) { return uint256(a) += b; }
545 inline const uint256 operator*(const base_uint256& a, const base_uint256& b) { return uint256(a) *= b; }
546 inline const uint256 operator/(const base_uint256& a, const base_uint256& b) { return uint256(a) /= b; }
547 inline const uint256 operator-(const base_uint256& a, const base_uint256& b) { return uint256(a) -= b; }
549 inline bool operator<(const base_uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; }
550 inline bool operator<=(const base_uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; }
551 inline bool operator>(const base_uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; }
552 inline bool operator>=(const base_uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; }
553 inline bool operator==(const base_uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; }
554 inline bool operator!=(const base_uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; }
555 inline const uint256 operator^(const base_uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
556 inline const uint256 operator&(const base_uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; }
557 inline const uint256 operator|(const base_uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; }
558 inline const uint256 operator+(const base_uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; }
559 inline const uint256 operator*(const base_uint256& a, const uint256& b) { return (base_uint256)a * (base_uint256)b; }
560 inline const uint256 operator/(const base_uint256& a, const uint256& b) { return (base_uint256)a / (base_uint256)b; }
561 inline const uint256 operator-(const base_uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; }
563 inline bool operator<(const uint256& a, const base_uint256& b) { return (base_uint256)a < (base_uint256)b; }
564 inline bool operator<=(const uint256& a, const base_uint256& b) { return (base_uint256)a <= (base_uint256)b; }
565 inline bool operator>(const uint256& a, const base_uint256& b) { return (base_uint256)a > (base_uint256)b; }
566 inline bool operator>=(const uint256& a, const base_uint256& b) { return (base_uint256)a >= (base_uint256)b; }
567 inline bool operator==(const uint256& a, const base_uint256& b) { return (base_uint256)a == (base_uint256)b; }
568 inline bool operator!=(const uint256& a, const base_uint256& b) { return (base_uint256)a != (base_uint256)b; }
569 inline const uint256 operator^(const uint256& a, const base_uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
570 inline const uint256 operator&(const uint256& a, const base_uint256& b) { return (base_uint256)a & (base_uint256)b; }
571 inline const uint256 operator|(const uint256& a, const base_uint256& b) { return (base_uint256)a | (base_uint256)b; }
572 inline const uint256 operator+(const uint256& a, const base_uint256& b) { return (base_uint256)a + (base_uint256)b; }
573 inline const uint256 operator-(const uint256& a, const base_uint256& b) { return (base_uint256)a - (base_uint256)b; }
575 inline bool operator<(const uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; }
576 inline bool operator<=(const uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; }
577 inline bool operator>(const uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; }
578 inline bool operator>=(const uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; }
579 inline bool operator==(const uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; }
580 inline bool operator!=(const uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; }
581 inline const uint256 operator^(const uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
582 inline const uint256 operator&(const uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; }
583 inline const uint256 operator|(const uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; }
584 inline const uint256 operator+(const uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; }
585 inline const uint256 operator-(const uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; }