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
14 typedef long long int64;
15 typedef unsigned long long uint64;
18 inline int Testuint256AdHoc(std::vector<std::string> vArg);
22 /** Base class without constructors for uint256 and uint160.
23 * This makes the compiler let u use it in a union.
25 template<unsigned int BITS>
29 enum { WIDTH=BITS/32 };
30 unsigned int pn[WIDTH];
33 bool operator!() const
35 for (int i = 0; i < WIDTH; i++)
41 const base_uint operator~() const
44 for (int i = 0; i < WIDTH; i++)
49 const base_uint operator-() const
52 for (int i = 0; i < WIDTH; i++)
58 double getdouble() const
62 for (int i = 0; i < WIDTH; i++) {
69 base_uint& operator=(uint64 b)
71 pn[0] = (unsigned int)b;
72 pn[1] = (unsigned int)(b >> 32);
73 for (int i = 2; i < WIDTH; i++)
78 base_uint& operator^=(const base_uint& b)
80 for (int i = 0; i < WIDTH; i++)
85 base_uint& operator&=(const base_uint& b)
87 for (int i = 0; i < WIDTH; i++)
92 base_uint& operator|=(const base_uint& b)
94 for (int i = 0; i < WIDTH; i++)
99 base_uint& operator^=(uint64 b)
101 pn[0] ^= (unsigned int)b;
102 pn[1] ^= (unsigned int)(b >> 32);
106 base_uint& operator|=(uint64 b)
108 pn[0] |= (unsigned int)b;
109 pn[1] |= (unsigned int)(b >> 32);
113 base_uint& operator<<=(unsigned int shift)
116 for (int i = 0; i < WIDTH; i++)
120 for (int i = 0; i < WIDTH; i++)
122 if (i+k+1 < WIDTH && shift != 0)
123 pn[i+k+1] |= (a.pn[i] >> (32-shift));
125 pn[i+k] |= (a.pn[i] << shift);
130 base_uint& operator>>=(unsigned int shift)
133 for (int i = 0; i < WIDTH; i++)
137 for (int i = 0; i < WIDTH; i++)
139 if (i-k-1 >= 0 && shift != 0)
140 pn[i-k-1] |= (a.pn[i] << (32-shift));
142 pn[i-k] |= (a.pn[i] >> shift);
147 base_uint& operator+=(const base_uint& b)
150 for (int i = 0; i < WIDTH; i++)
152 uint64 n = carry + pn[i] + b.pn[i];
153 pn[i] = n & 0xffffffff;
159 base_uint& operator-=(const base_uint& b)
165 base_uint& operator+=(uint64 b64)
173 base_uint& operator-=(uint64 b64)
182 base_uint& operator++()
186 while (++pn[i] == 0 && i < WIDTH-1)
191 const base_uint operator++(int)
194 const base_uint ret = *this;
199 base_uint& operator--()
203 while (--pn[i] == -1 && i < WIDTH-1)
208 const base_uint operator--(int)
211 const base_uint ret = *this;
217 friend inline bool operator<(const base_uint& a, const base_uint& b)
219 for (int i = base_uint::WIDTH-1; i >= 0; i--)
221 if (a.pn[i] < b.pn[i])
223 else if (a.pn[i] > b.pn[i])
229 friend inline bool operator<=(const base_uint& a, const base_uint& b)
231 for (int i = base_uint::WIDTH-1; i >= 0; i--)
233 if (a.pn[i] < b.pn[i])
235 else if (a.pn[i] > b.pn[i])
241 friend inline bool operator>(const base_uint& a, const base_uint& b)
243 for (int i = base_uint::WIDTH-1; i >= 0; i--)
245 if (a.pn[i] > b.pn[i])
247 else if (a.pn[i] < b.pn[i])
253 friend inline bool operator>=(const base_uint& a, const base_uint& b)
255 for (int i = base_uint::WIDTH-1; i >= 0; i--)
257 if (a.pn[i] > b.pn[i])
259 else if (a.pn[i] < b.pn[i])
265 friend inline bool operator==(const base_uint& a, const base_uint& b)
267 for (int i = 0; i < base_uint::WIDTH; i++)
268 if (a.pn[i] != b.pn[i])
273 friend inline bool operator==(const base_uint& a, uint64 b)
275 if (a.pn[0] != (unsigned int)b)
277 if (a.pn[1] != (unsigned int)(b >> 32))
279 for (int i = 2; i < base_uint::WIDTH; i++)
285 friend inline bool operator!=(const base_uint& a, const base_uint& b)
290 friend inline bool operator!=(const base_uint& a, uint64 b)
297 std::string GetHex() const
299 char psz[sizeof(pn)*2 + 1];
300 for (unsigned int i = 0; i < sizeof(pn); i++)
301 sprintf(psz + i*2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
302 return std::string(psz, psz + sizeof(pn)*2);
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()
349 return (unsigned char*)&pn[0];
354 return (unsigned char*)&pn[WIDTH];
357 std::vector<unsigned char> getBytes()
359 return std::vector<unsigned char>(begin(), end());
367 uint64 Get64(int n=0) const
369 return pn[2*n] | (uint64)pn[2*n+1] << 32;
372 unsigned int GetSerializeSize(int nType, int nVersion) const
377 template<typename Stream>
378 void Serialize(Stream& s, int nType, int nVersion) const
380 s.write((char*)pn, sizeof(pn));
383 template<typename Stream>
384 void Unserialize(Stream& s, int nType, int nVersion)
386 s.read((char*)pn, sizeof(pn));
389 friend class uint160;
390 friend class uint256;
391 friend inline int Testuint256AdHoc(std::vector<std::string> vArg);
394 typedef base_uint<160> base_uint160;
395 typedef base_uint<256> base_uint256;
398 // uint160 and uint256 could be implemented as templates, but to keep
399 // compile errors and debugging cleaner, they're copy and pasted.
404 //////////////////////////////////////////////////////////////////////////////
409 /** 160-bit unsigned integer */
410 class uint160 : public base_uint160
413 typedef base_uint160 basetype;
417 for (int i = 0; i < WIDTH; i++)
421 uint160(const basetype& b)
423 for (int i = 0; i < WIDTH; i++)
427 uint160& operator=(const basetype& b)
429 for (int i = 0; i < WIDTH; i++)
436 pn[0] = (unsigned int)b;
437 pn[1] = (unsigned int)(b >> 32);
438 for (int i = 2; i < WIDTH; i++)
442 uint160& operator=(uint64 b)
444 pn[0] = (unsigned int)b;
445 pn[1] = (unsigned int)(b >> 32);
446 for (int i = 2; i < WIDTH; i++)
451 explicit uint160(const std::string& str)
456 explicit uint160(const std::vector<unsigned char>& vch)
458 if (vch.size() == sizeof(pn))
459 memcpy(pn, &vch[0], sizeof(pn));
465 inline bool operator==(const uint160& a, uint64 b) { return (base_uint160)a == b; }
466 inline bool operator!=(const uint160& a, uint64 b) { return (base_uint160)a != b; }
467 inline const uint160 operator<<(const base_uint160& a, unsigned int shift) { return uint160(a) <<= shift; }
468 inline const uint160 operator>>(const base_uint160& a, unsigned int shift) { return uint160(a) >>= shift; }
469 inline const uint160 operator<<(const uint160& a, unsigned int shift) { return uint160(a) <<= shift; }
470 inline const uint160 operator>>(const uint160& a, unsigned int shift) { return uint160(a) >>= shift; }
472 inline const uint160 operator^(const base_uint160& a, const base_uint160& b) { return uint160(a) ^= b; }
473 inline const uint160 operator&(const base_uint160& a, const base_uint160& b) { return uint160(a) &= b; }
474 inline const uint160 operator|(const base_uint160& a, const base_uint160& b) { return uint160(a) |= b; }
475 inline const uint160 operator+(const base_uint160& a, const base_uint160& b) { return uint160(a) += b; }
476 inline const uint160 operator-(const base_uint160& a, const base_uint160& b) { return uint160(a) -= b; }
478 inline bool operator<(const base_uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; }
479 inline bool operator<=(const base_uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; }
480 inline bool operator>(const base_uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; }
481 inline bool operator>=(const base_uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)b; }
482 inline bool operator==(const base_uint160& a, const uint160& b) { return (base_uint160)a == (base_uint160)b; }
483 inline bool operator!=(const base_uint160& a, const uint160& b) { return (base_uint160)a != (base_uint160)b; }
484 inline const uint160 operator^(const base_uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
485 inline const uint160 operator&(const base_uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; }
486 inline const uint160 operator|(const base_uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; }
487 inline const uint160 operator+(const base_uint160& a, const uint160& b) { return (base_uint160)a + (base_uint160)b; }
488 inline const uint160 operator-(const base_uint160& a, const uint160& b) { return (base_uint160)a - (base_uint160)b; }
490 inline bool operator<(const uint160& a, const base_uint160& b) { return (base_uint160)a < (base_uint160)b; }
491 inline bool operator<=(const uint160& a, const base_uint160& b) { return (base_uint160)a <= (base_uint160)b; }
492 inline bool operator>(const uint160& a, const base_uint160& b) { return (base_uint160)a > (base_uint160)b; }
493 inline bool operator>=(const uint160& a, const base_uint160& b) { return (base_uint160)a >= (base_uint160)b; }
494 inline bool operator==(const uint160& a, const base_uint160& b) { return (base_uint160)a == (base_uint160)b; }
495 inline bool operator!=(const uint160& a, const base_uint160& b) { return (base_uint160)a != (base_uint160)b; }
496 inline const uint160 operator^(const uint160& a, const base_uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
497 inline const uint160 operator&(const uint160& a, const base_uint160& b) { return (base_uint160)a & (base_uint160)b; }
498 inline const uint160 operator|(const uint160& a, const base_uint160& b) { return (base_uint160)a | (base_uint160)b; }
499 inline const uint160 operator+(const uint160& a, const base_uint160& b) { return (base_uint160)a + (base_uint160)b; }
500 inline const uint160 operator-(const uint160& a, const base_uint160& b) { return (base_uint160)a - (base_uint160)b; }
502 inline bool operator<(const uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; }
503 inline bool operator<=(const uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; }
504 inline bool operator>(const uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; }
505 inline bool operator>=(const uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)b; }
506 inline bool operator==(const uint160& a, const uint160& b) { return (base_uint160)a == (base_uint160)b; }
507 inline bool operator!=(const uint160& a, const uint160& b) { return (base_uint160)a != (base_uint160)b; }
508 inline const uint160 operator^(const uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
509 inline const uint160 operator&(const uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; }
510 inline const uint160 operator|(const uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; }
511 inline const uint160 operator+(const uint160& a, const uint160& b) { return (base_uint160)a + (base_uint160)b; }
512 inline const uint160 operator-(const uint160& a, const uint160& b) { return (base_uint160)a - (base_uint160)b; }
519 //////////////////////////////////////////////////////////////////////////////
524 /** 256-bit unsigned integer */
525 class uint256 : public base_uint256
528 typedef base_uint256 basetype;
532 for (int i = 0; i < WIDTH; i++)
536 uint256(const basetype& b)
538 for (int i = 0; i < WIDTH; i++)
542 uint256& operator=(const basetype& b)
544 for (int i = 0; i < WIDTH; i++)
551 pn[0] = (unsigned int)b;
552 pn[1] = (unsigned int)(b >> 32);
553 for (int i = 2; i < WIDTH; i++)
557 uint256& operator=(uint64 b)
559 pn[0] = (unsigned int)b;
560 pn[1] = (unsigned int)(b >> 32);
561 for (int i = 2; i < WIDTH; i++)
566 explicit uint256(const std::string& str)
571 explicit uint256(const std::vector<unsigned char>& vch)
573 if (vch.size() == sizeof(pn))
574 memcpy(pn, &vch[0], sizeof(pn));
580 inline bool operator==(const uint256& a, uint64 b) { return (base_uint256)a == b; }
581 inline bool operator!=(const uint256& a, uint64 b) { return (base_uint256)a != b; }
582 inline const uint256 operator<<(const base_uint256& a, unsigned int shift) { return uint256(a) <<= shift; }
583 inline const uint256 operator>>(const base_uint256& a, unsigned int shift) { return uint256(a) >>= shift; }
584 inline const uint256 operator<<(const uint256& a, unsigned int shift) { return uint256(a) <<= shift; }
585 inline const uint256 operator>>(const uint256& a, unsigned int shift) { return uint256(a) >>= shift; }
587 inline const uint256 operator^(const base_uint256& a, const base_uint256& b) { return uint256(a) ^= b; }
588 inline const uint256 operator&(const base_uint256& a, const base_uint256& b) { return uint256(a) &= b; }
589 inline const uint256 operator|(const base_uint256& a, const base_uint256& b) { return uint256(a) |= b; }
590 inline const uint256 operator+(const base_uint256& a, const base_uint256& b) { return uint256(a) += b; }
591 inline const uint256 operator-(const base_uint256& a, const base_uint256& b) { return uint256(a) -= b; }
593 inline bool operator<(const base_uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; }
594 inline bool operator<=(const base_uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; }
595 inline bool operator>(const base_uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; }
596 inline bool operator>=(const base_uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; }
597 inline bool operator==(const base_uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; }
598 inline bool operator!=(const base_uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; }
599 inline const uint256 operator^(const base_uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
600 inline const uint256 operator&(const base_uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; }
601 inline const uint256 operator|(const base_uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; }
602 inline const uint256 operator+(const base_uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; }
603 inline const uint256 operator-(const base_uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; }
605 inline bool operator<(const uint256& a, const base_uint256& b) { return (base_uint256)a < (base_uint256)b; }
606 inline bool operator<=(const uint256& a, const base_uint256& b) { return (base_uint256)a <= (base_uint256)b; }
607 inline bool operator>(const uint256& a, const base_uint256& b) { return (base_uint256)a > (base_uint256)b; }
608 inline bool operator>=(const uint256& a, const base_uint256& b) { return (base_uint256)a >= (base_uint256)b; }
609 inline bool operator==(const uint256& a, const base_uint256& b) { return (base_uint256)a == (base_uint256)b; }
610 inline bool operator!=(const uint256& a, const base_uint256& b) { return (base_uint256)a != (base_uint256)b; }
611 inline const uint256 operator^(const uint256& a, const base_uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
612 inline const uint256 operator&(const uint256& a, const base_uint256& b) { return (base_uint256)a & (base_uint256)b; }
613 inline const uint256 operator|(const uint256& a, const base_uint256& b) { return (base_uint256)a | (base_uint256)b; }
614 inline const uint256 operator+(const uint256& a, const base_uint256& b) { return (base_uint256)a + (base_uint256)b; }
615 inline const uint256 operator-(const uint256& a, const base_uint256& b) { return (base_uint256)a - (base_uint256)b; }
617 inline bool operator<(const uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; }
618 inline bool operator<=(const uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; }
619 inline bool operator>(const uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; }
620 inline bool operator>=(const uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; }
621 inline bool operator==(const uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; }
622 inline bool operator!=(const uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; }
623 inline const uint256 operator^(const uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
624 inline const uint256 operator&(const uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; }
625 inline const uint256 operator|(const uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; }
626 inline const uint256 operator+(const uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; }
627 inline const uint256 operator-(const uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; }
640 inline int Testuint256AdHoc(std::vector<std::string> vArg)
645 printf("%s\n", g.ToString().c_str());
646 g--; printf("g--\n");
647 printf("%s\n", g.ToString().c_str());
648 g--; printf("g--\n");
649 printf("%s\n", g.ToString().c_str());
650 g++; printf("g++\n");
651 printf("%s\n", g.ToString().c_str());
652 g++; printf("g++\n");
653 printf("%s\n", g.ToString().c_str());
654 g++; printf("g++\n");
655 printf("%s\n", g.ToString().c_str());
656 g++; printf("g++\n");
657 printf("%s\n", g.ToString().c_str());
663 printf("%s\n", a.ToString().c_str());
666 printf("b undefined\n");
667 printf("%s\n", b.ToString().c_str());
672 printf("%s\n", a.ToString().c_str());
677 printf("%s\n", a.ToString().c_str());
685 printf("a %s\n", a.ToString().c_str());
687 a = a | b | (uint256)0x1000;
690 printf("a %s\n", a.ToString().c_str());
691 printf("b %s\n", b.ToString().c_str());
696 printf("%s\n", a.ToString().c_str());
698 printf("%s\n", a.ToString().c_str());
700 printf("%s\n", a.ToString().c_str());
702 printf("%s\n", a.ToString().c_str());
704 printf("%s\n", a.ToString().c_str());
707 printf("%s\n", a.ToString().c_str());
709 printf("%s\n", a.ToString().c_str());
711 printf("%s\n", a.ToString().c_str());
713 printf("%s\n", d.ToString().c_str());
714 printf("%s\n", a.ToString().c_str());
716 printf("%s\n", a.ToString().c_str());
718 printf("%s\n", a.ToString().c_str());
722 printf("%s\n", d.ToString().c_str());
723 for (int i = uint256::WIDTH-1; i >= 0; i--) printf("%08x", d.pn[i]); printf("\n");
727 printf("%s\n", neg.ToString().c_str());
730 uint256 e = uint256("0xABCDEF123abcdef12345678909832180000011111111");
732 printf("%s\n", e.ToString().c_str());
736 uint256 x1 = uint256("0xABCDEF123abcdef12345678909832180000011111111");
738 printf("%s\n", x1.ToString().c_str());
739 for (int i = 0; i < 270; i += 4)
742 printf("%s\n", x2.ToString().c_str());
746 printf("%s\n", x1.ToString().c_str());
747 for (int i = 0; i < 270; i += 4)
751 printf("%s\n", x2.ToString().c_str());
755 for (int i = 0; i < 100; i++)
757 uint256 k = (~uint256(0) >> i);
758 printf("%s\n", k.ToString().c_str());
761 for (int i = 0; i < 100; i++)
763 uint256 k = (~uint256(0) << i);
764 printf("%s\n", k.ToString().c_str());