1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Distributed under the MIT/X11 software license, see the accompanying
3 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
4 #ifndef BITCOIN_UINT256_H
5 #define BITCOIN_UINT256_H
13 #if defined(_MSC_VER) || defined(__BORLANDC__)
14 typedef __int64 int64;
15 typedef unsigned __int64 uint64;
17 typedef long long int64;
18 typedef unsigned long long uint64;
20 #if defined(_MSC_VER) && _MSC_VER < 1300
21 #define for if (false) ; else for
25 inline int Testuint256AdHoc(std::vector<std::string> vArg);
29 // We have to keep a separate base class without constructors
30 // so the compiler will let us use it in a union
31 template<unsigned int BITS>
35 enum { WIDTH=BITS/32 };
36 unsigned int pn[WIDTH];
39 bool operator!() const
41 for (int i = 0; i < WIDTH; i++)
47 const base_uint operator~() const
50 for (int i = 0; i < WIDTH; i++)
55 const base_uint operator-() const
58 for (int i = 0; i < WIDTH; i++)
65 base_uint& operator=(uint64 b)
67 pn[0] = (unsigned int)b;
68 pn[1] = (unsigned int)(b >> 32);
69 for (int i = 2; i < WIDTH; i++)
74 base_uint& operator^=(const base_uint& b)
76 for (int i = 0; i < WIDTH; i++)
81 base_uint& operator&=(const base_uint& b)
83 for (int i = 0; i < WIDTH; i++)
88 base_uint& operator|=(const base_uint& b)
90 for (int i = 0; i < WIDTH; i++)
95 base_uint& operator^=(uint64 b)
97 pn[0] ^= (unsigned int)b;
98 pn[1] ^= (unsigned int)(b >> 32);
102 base_uint& operator&=(uint64 b)
104 pn[0] &= (unsigned int)b;
105 pn[1] &= (unsigned int)(b >> 32);
109 base_uint& operator|=(uint64 b)
111 pn[0] |= (unsigned int)b;
112 pn[1] |= (unsigned int)(b >> 32);
116 base_uint& operator<<=(unsigned int shift)
119 for (int i = 0; i < WIDTH; i++)
123 for (int i = 0; i < WIDTH; i++)
125 if (i+k+1 < WIDTH && shift != 0)
126 pn[i+k+1] |= (a.pn[i] >> (32-shift));
128 pn[i+k] |= (a.pn[i] << shift);
133 base_uint& operator>>=(unsigned int shift)
136 for (int i = 0; i < WIDTH; i++)
140 for (int i = 0; i < WIDTH; i++)
142 if (i-k-1 >= 0 && shift != 0)
143 pn[i-k-1] |= (a.pn[i] << (32-shift));
145 pn[i-k] |= (a.pn[i] >> shift);
150 base_uint& operator+=(const base_uint& b)
153 for (int i = 0; i < WIDTH; i++)
155 uint64 n = carry + pn[i] + b.pn[i];
156 pn[i] = n & 0xffffffff;
162 base_uint& operator-=(const base_uint& b)
168 base_uint& operator+=(uint64 b64)
176 base_uint& operator-=(uint64 b64)
185 base_uint& operator++()
189 while (++pn[i] == 0 && i < WIDTH-1)
194 const base_uint operator++(int)
197 const base_uint ret = *this;
202 base_uint& operator--()
206 while (--pn[i] == -1 && i < WIDTH-1)
211 const base_uint operator--(int)
214 const base_uint ret = *this;
220 friend inline bool operator<(const base_uint& a, const base_uint& b)
222 for (int i = base_uint::WIDTH-1; i >= 0; i--)
224 if (a.pn[i] < b.pn[i])
226 else if (a.pn[i] > b.pn[i])
232 friend inline bool operator<=(const base_uint& a, const base_uint& b)
234 for (int i = base_uint::WIDTH-1; i >= 0; i--)
236 if (a.pn[i] < b.pn[i])
238 else if (a.pn[i] > b.pn[i])
244 friend inline bool operator>(const base_uint& a, const base_uint& b)
246 for (int i = base_uint::WIDTH-1; i >= 0; i--)
248 if (a.pn[i] > b.pn[i])
250 else if (a.pn[i] < b.pn[i])
256 friend inline bool operator>=(const base_uint& a, const base_uint& b)
258 for (int i = base_uint::WIDTH-1; i >= 0; i--)
260 if (a.pn[i] > b.pn[i])
262 else if (a.pn[i] < b.pn[i])
268 friend inline bool operator==(const base_uint& a, const base_uint& b)
270 for (int i = 0; i < base_uint::WIDTH; i++)
271 if (a.pn[i] != b.pn[i])
276 friend inline bool operator==(const base_uint& a, uint64 b)
278 if (a.pn[0] != (unsigned int)b)
280 if (a.pn[1] != (unsigned int)(b >> 32))
282 for (int i = 2; i < base_uint::WIDTH; i++)
288 friend inline bool operator!=(const base_uint& a, const base_uint& b)
293 friend inline bool operator!=(const base_uint& a, uint64 b)
300 std::string GetHex() const
302 char psz[sizeof(pn)*2 + 1];
303 for (int i = 0; i < sizeof(pn); i++)
304 sprintf(psz + i*2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
305 return std::string(psz, psz + sizeof(pn)*2);
308 void SetHex(const char* psz)
310 for (int i = 0; i < WIDTH; i++)
313 // skip leading spaces
314 while (isspace(*psz))
318 if (psz[0] == '0' && tolower(psz[1]) == 'x')
321 // hex string to uint
322 static 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 };
323 const char* pbegin = psz;
324 while (phexdigit[*psz] || *psz == '0')
327 unsigned char* p1 = (unsigned char*)pn;
328 unsigned char* pend = p1 + WIDTH * 4;
329 while (psz >= pbegin && p1 < pend)
331 *p1 = phexdigit[(unsigned char)*psz--];
334 *p1 |= (phexdigit[(unsigned char)*psz--] << 4);
340 void SetHex(const std::string& str)
345 std::string ToString() const
350 unsigned char* begin()
352 return (unsigned char*)&pn[0];
357 return (unsigned char*)&pn[WIDTH];
366 unsigned int GetSerializeSize(int nType=0, int nVersion=VERSION) const
371 template<typename Stream>
372 void Serialize(Stream& s, int nType=0, int nVersion=VERSION) const
374 s.write((char*)pn, sizeof(pn));
377 template<typename Stream>
378 void Unserialize(Stream& s, int nType=0, int nVersion=VERSION)
380 s.read((char*)pn, sizeof(pn));
384 friend class uint160;
385 friend class uint256;
386 friend inline int Testuint256AdHoc(std::vector<std::string> vArg);
389 typedef base_uint<160> base_uint160;
390 typedef base_uint<256> base_uint256;
395 // uint160 and uint256 could be implemented as templates, but to keep
396 // compile errors and debugging cleaner, they're copy and pasted.
401 //////////////////////////////////////////////////////////////////////////////
406 class uint160 : public base_uint160
409 typedef base_uint160 basetype;
413 for (int i = 0; i < WIDTH; i++)
417 uint160(const basetype& b)
419 for (int i = 0; i < WIDTH; i++)
423 uint160& operator=(const basetype& b)
425 for (int i = 0; i < WIDTH; i++)
432 pn[0] = (unsigned int)b;
433 pn[1] = (unsigned int)(b >> 32);
434 for (int i = 2; i < WIDTH; i++)
438 uint160& operator=(uint64 b)
440 pn[0] = (unsigned int)b;
441 pn[1] = (unsigned int)(b >> 32);
442 for (int i = 2; i < WIDTH; i++)
447 explicit uint160(const std::string& str)
452 explicit uint160(const std::vector<unsigned char>& vch)
454 if (vch.size() == sizeof(pn))
455 memcpy(pn, &vch[0], sizeof(pn));
461 inline bool operator==(const uint160& a, uint64 b) { return (base_uint160)a == b; }
462 inline bool operator!=(const uint160& a, uint64 b) { return (base_uint160)a != b; }
463 inline const uint160 operator<<(const base_uint160& a, unsigned int shift) { return uint160(a) <<= shift; }
464 inline const uint160 operator>>(const base_uint160& a, unsigned int shift) { return uint160(a) >>= shift; }
465 inline const uint160 operator<<(const uint160& a, unsigned int shift) { return uint160(a) <<= shift; }
466 inline const uint160 operator>>(const uint160& a, unsigned int shift) { return uint160(a) >>= shift; }
468 inline const uint160 operator^(const base_uint160& a, const base_uint160& b) { return uint160(a) ^= b; }
469 inline const uint160 operator&(const base_uint160& a, const base_uint160& b) { return uint160(a) &= b; }
470 inline const uint160 operator|(const base_uint160& a, const base_uint160& b) { return uint160(a) |= b; }
471 inline const uint160 operator+(const base_uint160& a, const base_uint160& b) { return uint160(a) += b; }
472 inline const uint160 operator-(const base_uint160& a, const base_uint160& b) { return uint160(a) -= b; }
474 inline bool operator<(const base_uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; }
475 inline bool operator<=(const base_uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; }
476 inline bool operator>(const base_uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; }
477 inline bool operator>=(const base_uint160& a, const uint160& b) { return (base_uint160)a >= (base_uint160)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 const uint160 operator^(const base_uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
481 inline const uint160 operator&(const base_uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; }
482 inline const uint160 operator|(const base_uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; }
483 inline const uint160 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; }
486 inline bool operator<(const uint160& a, const base_uint160& b) { return (base_uint160)a < (base_uint160)b; }
487 inline bool operator<=(const uint160& a, const base_uint160& b) { return (base_uint160)a <= (base_uint160)b; }
488 inline bool operator>(const uint160& a, const base_uint160& b) { return (base_uint160)a > (base_uint160)b; }
489 inline bool operator>=(const uint160& a, const base_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 const uint160 operator^(const uint160& a, const base_uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
493 inline const uint160 operator&(const uint160& a, const base_uint160& b) { return (base_uint160)a & (base_uint160)b; }
494 inline const uint160 operator|(const uint160& a, const base_uint160& b) { return (base_uint160)a | (base_uint160)b; }
495 inline const uint160 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; }
498 inline bool operator<(const uint160& a, const uint160& b) { return (base_uint160)a < (base_uint160)b; }
499 inline bool operator<=(const uint160& a, const uint160& b) { return (base_uint160)a <= (base_uint160)b; }
500 inline bool operator>(const uint160& a, const uint160& b) { return (base_uint160)a > (base_uint160)b; }
501 inline bool operator>=(const uint160& a, const 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 const uint160 operator^(const uint160& a, const uint160& b) { return (base_uint160)a ^ (base_uint160)b; }
505 inline const uint160 operator&(const uint160& a, const uint160& b) { return (base_uint160)a & (base_uint160)b; }
506 inline const uint160 operator|(const uint160& a, const uint160& b) { return (base_uint160)a | (base_uint160)b; }
507 inline const uint160 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; }
515 //////////////////////////////////////////////////////////////////////////////
520 class uint256 : public base_uint256
523 typedef base_uint256 basetype;
527 for (int i = 0; i < WIDTH; i++)
531 uint256(const basetype& b)
533 for (int i = 0; i < WIDTH; i++)
537 uint256& operator=(const basetype& b)
539 for (int i = 0; i < WIDTH; i++)
546 pn[0] = (unsigned int)b;
547 pn[1] = (unsigned int)(b >> 32);
548 for (int i = 2; i < WIDTH; i++)
552 uint256& operator=(uint64 b)
554 pn[0] = (unsigned int)b;
555 pn[1] = (unsigned int)(b >> 32);
556 for (int i = 2; i < WIDTH; i++)
561 explicit uint256(const std::string& str)
566 explicit uint256(const std::vector<unsigned char>& vch)
568 if (vch.size() == sizeof(pn))
569 memcpy(pn, &vch[0], sizeof(pn));
575 inline bool operator==(const uint256& a, uint64 b) { return (base_uint256)a == b; }
576 inline bool operator!=(const uint256& a, uint64 b) { return (base_uint256)a != b; }
577 inline const uint256 operator<<(const base_uint256& a, unsigned int shift) { return uint256(a) <<= shift; }
578 inline const uint256 operator>>(const base_uint256& a, unsigned int shift) { return uint256(a) >>= shift; }
579 inline const uint256 operator<<(const uint256& a, unsigned int shift) { return uint256(a) <<= shift; }
580 inline const uint256 operator>>(const uint256& a, unsigned int shift) { return uint256(a) >>= shift; }
582 inline const uint256 operator^(const base_uint256& a, const base_uint256& b) { return uint256(a) ^= b; }
583 inline const uint256 operator&(const base_uint256& a, const base_uint256& b) { return uint256(a) &= b; }
584 inline const uint256 operator|(const base_uint256& a, const base_uint256& b) { return uint256(a) |= b; }
585 inline const uint256 operator+(const base_uint256& a, const base_uint256& b) { return uint256(a) += b; }
586 inline const uint256 operator-(const base_uint256& a, const base_uint256& b) { return uint256(a) -= b; }
588 inline bool operator<(const base_uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; }
589 inline bool operator<=(const base_uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; }
590 inline bool operator>(const base_uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; }
591 inline bool operator>=(const base_uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; }
592 inline bool operator==(const base_uint256& a, const uint256& b) { return (base_uint256)a == (base_uint256)b; }
593 inline bool operator!=(const base_uint256& a, const uint256& b) { return (base_uint256)a != (base_uint256)b; }
594 inline const uint256 operator^(const base_uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
595 inline const uint256 operator&(const base_uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; }
596 inline const uint256 operator|(const base_uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; }
597 inline const uint256 operator+(const base_uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; }
598 inline const uint256 operator-(const base_uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; }
600 inline bool operator<(const uint256& a, const base_uint256& b) { return (base_uint256)a < (base_uint256)b; }
601 inline bool operator<=(const uint256& a, const base_uint256& b) { return (base_uint256)a <= (base_uint256)b; }
602 inline bool operator>(const uint256& a, const base_uint256& b) { return (base_uint256)a > (base_uint256)b; }
603 inline bool operator>=(const uint256& a, const base_uint256& b) { return (base_uint256)a >= (base_uint256)b; }
604 inline bool operator==(const uint256& a, const base_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 const uint256 operator^(const uint256& a, const base_uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
607 inline const uint256 operator&(const uint256& a, const base_uint256& b) { return (base_uint256)a & (base_uint256)b; }
608 inline const uint256 operator|(const uint256& a, const base_uint256& b) { return (base_uint256)a | (base_uint256)b; }
609 inline const uint256 operator+(const uint256& a, const base_uint256& b) { return (base_uint256)a + (base_uint256)b; }
610 inline const uint256 operator-(const uint256& a, const base_uint256& b) { return (base_uint256)a - (base_uint256)b; }
612 inline bool operator<(const uint256& a, const uint256& b) { return (base_uint256)a < (base_uint256)b; }
613 inline bool operator<=(const uint256& a, const uint256& b) { return (base_uint256)a <= (base_uint256)b; }
614 inline bool operator>(const uint256& a, const uint256& b) { return (base_uint256)a > (base_uint256)b; }
615 inline bool operator>=(const uint256& a, const uint256& b) { return (base_uint256)a >= (base_uint256)b; }
616 inline bool operator==(const uint256& a, const 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 const uint256 operator^(const uint256& a, const uint256& b) { return (base_uint256)a ^ (base_uint256)b; }
619 inline const uint256 operator&(const uint256& a, const uint256& b) { return (base_uint256)a & (base_uint256)b; }
620 inline const uint256 operator|(const uint256& a, const uint256& b) { return (base_uint256)a | (base_uint256)b; }
621 inline const uint256 operator+(const uint256& a, const uint256& b) { return (base_uint256)a + (base_uint256)b; }
622 inline const uint256 operator-(const uint256& a, const uint256& b) { return (base_uint256)a - (base_uint256)b; }
635 inline int Testuint256AdHoc(std::vector<std::string> vArg)
640 printf("%s\n", g.ToString().c_str());
641 g--; printf("g--\n");
642 printf("%s\n", g.ToString().c_str());
643 g--; printf("g--\n");
644 printf("%s\n", g.ToString().c_str());
645 g++; printf("g++\n");
646 printf("%s\n", g.ToString().c_str());
647 g++; printf("g++\n");
648 printf("%s\n", g.ToString().c_str());
649 g++; printf("g++\n");
650 printf("%s\n", g.ToString().c_str());
651 g++; printf("g++\n");
652 printf("%s\n", g.ToString().c_str());
658 printf("%s\n", a.ToString().c_str());
661 printf("b undefined\n");
662 printf("%s\n", b.ToString().c_str());
667 printf("%s\n", a.ToString().c_str());
672 printf("%s\n", a.ToString().c_str());
680 printf("a %s\n", a.ToString().c_str());
682 a = a | b | (uint256)0x1000;
685 printf("a %s\n", a.ToString().c_str());
686 printf("b %s\n", b.ToString().c_str());
691 printf("%s\n", a.ToString().c_str());
693 printf("%s\n", a.ToString().c_str());
695 printf("%s\n", a.ToString().c_str());
697 printf("%s\n", a.ToString().c_str());
699 printf("%s\n", a.ToString().c_str());
702 printf("%s\n", a.ToString().c_str());
704 printf("%s\n", a.ToString().c_str());
706 printf("%s\n", a.ToString().c_str());
708 printf("%s\n", d.ToString().c_str());
709 printf("%s\n", a.ToString().c_str());
711 printf("%s\n", a.ToString().c_str());
713 printf("%s\n", a.ToString().c_str());
717 printf("%s\n", d.ToString().c_str());
718 for (int i = uint256::WIDTH-1; i >= 0; i--) printf("%08x", d.pn[i]); printf("\n");
722 printf("%s\n", neg.ToString().c_str());
725 uint256 e = uint256("0xABCDEF123abcdef12345678909832180000011111111");
727 printf("%s\n", e.ToString().c_str());
731 uint256 x1 = uint256("0xABCDEF123abcdef12345678909832180000011111111");
733 printf("%s\n", x1.ToString().c_str());
734 for (int i = 0; i < 270; i += 4)
737 printf("%s\n", x2.ToString().c_str());
741 printf("%s\n", x1.ToString().c_str());
742 for (int i = 0; i < 270; i += 4)
746 printf("%s\n", x2.ToString().c_str());
750 for (int i = 0; i < 100; i++)
752 uint256 k = (~uint256(0) >> i);
753 printf("%s\n", k.ToString().c_str());
756 for (int i = 0; i < 100; i++)
758 uint256 k = (~uint256(0) << i);
759 printf("%s\n", k.ToString().c_str());