-
+ 6ACE91913A6A5CC0D6597258EE536D0BF22C5D0FE4066117AA3D31331E5ADA7FAA8098006B3F36AD4843A28D13E896D45C0F2036B123A3B117DA4E510B4745C3bitcoin/src/bignum.h(0 . 0)(1 . 569)
473 // /****************************\
474 // * EXPERIMENTAL BRANCH. *
475 // * FOR LABORATORY USE ONLY. *
476 // ********************************
477 // ************
478 // **************
479 // ****************
480 // **** **** ****
481 // *** *** ***
482 // *** *** ***
483 // *** * * **
484 // ******** ********
485 // ******* ******
486 // *** **
487 // * ******* **
488 // ** * * * * *
489 // ** * * ***
490 // **** * * * * ****
491 // **** *** * * ** ***
492 // **** ********* ******
493 // ******* ***** *******
494 // ********* ****** **
495 // ** ****** ******
496 // ** ******* **
497 // ** ******* ***
498 // **** ******** ************
499 // ************ ************
500 // ******** *******
501 // ****** ****
502 // *** ***
503 // ********************************
504 // Copyright (c) 2009-2010 Satoshi Nakamoto
505 // Copyright (c) 2011 The Bitcoin developers
506 // Distributed under the MIT/X11 software license, see the accompanying
507 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
508 #ifndef BITCOIN_BIGNUM_H
509 #define BITCOIN_BIGNUM_H
510
511 #include <stdexcept>
512 #include <vector>
513 #include <openssl/bn.h>
514
515 #include "util.h"
516
517 class bignum_error : public std::runtime_error
518 {
519 public:
520 explicit bignum_error(const std::string& str) : std::runtime_error(str) {}
521 };
522
523
524
525 class CAutoBN_CTX
526 {
527 protected:
528 BN_CTX* pctx;
529 BN_CTX* operator=(BN_CTX* pnew) { return pctx = pnew; }
530
531 public:
532 CAutoBN_CTX()
533 {
534 pctx = BN_CTX_new();
535 if (pctx == NULL)
536 throw bignum_error("CAutoBN_CTX : BN_CTX_new() returned NULL");
537 }
538
539 ~CAutoBN_CTX()
540 {
541 if (pctx != NULL)
542 BN_CTX_free(pctx);
543 }
544
545 operator BN_CTX*() { return pctx; }
546 BN_CTX& operator*() { return *pctx; }
547 BN_CTX** operator&() { return &pctx; }
548 bool operator!() { return (pctx == NULL); }
549 };
550
551
552
553 class CBigNum : public BIGNUM
554 {
555 public:
556 CBigNum()
557 {
558 BN_init(this);
559 }
560
561 CBigNum(const CBigNum& b)
562 {
563 BN_init(this);
564 if (!BN_copy(this, &b))
565 {
566 BN_clear_free(this);
567 throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_copy failed");
568 }
569 }
570
571 CBigNum& operator=(const CBigNum& b)
572 {
573 if (!BN_copy(this, &b))
574 throw bignum_error("CBigNum::operator= : BN_copy failed");
575 return (*this);
576 }
577
578 ~CBigNum()
579 {
580 BN_clear_free(this);
581 }
582
583 CBigNum(char n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
584 CBigNum(short n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
585 CBigNum(int n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
586 CBigNum(long n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
587 CBigNum(int64 n) { BN_init(this); setint64(n); }
588 CBigNum(unsigned char n) { BN_init(this); setulong(n); }
589 CBigNum(unsigned short n) { BN_init(this); setulong(n); }
590 CBigNum(unsigned int n) { BN_init(this); setulong(n); }
591 CBigNum(unsigned long n) { BN_init(this); setulong(n); }
592 CBigNum(uint64 n) { BN_init(this); setuint64(n); }
593 explicit CBigNum(uint256 n) { BN_init(this); setuint256(n); }
594
595 explicit CBigNum(const std::vector<unsigned char>& vch)
596 {
597 BN_init(this);
598 setvch(vch);
599 }
600
601 void setulong(unsigned long n)
602 {
603 if (!BN_set_word(this, n))
604 throw bignum_error("CBigNum conversion from unsigned long : BN_set_word failed");
605 }
606
607 unsigned long getulong() const
608 {
609 return BN_get_word(this);
610 }
611
612 unsigned int getuint() const
613 {
614 return BN_get_word(this);
615 }
616
617 int getint() const
618 {
619 unsigned long n = BN_get_word(this);
620 if (!BN_is_negative(this))
621 return (n > INT_MAX ? INT_MAX : n);
622 else
623 return (n > INT_MAX ? INT_MIN : -(int)n);
624 }
625
626 void setint64(int64 n)
627 {
628 unsigned char pch[sizeof(n) + 6];
629 unsigned char* p = pch + 4;
630 bool fNegative = false;
631 if (n < (int64)0)
632 {
633 n = -n;
634 fNegative = true;
635 }
636 bool fLeadingZeroes = true;
637 for (int i = 0; i < 8; i++)
638 {
639 unsigned char c = (n >> 56) & 0xff;
640 n <<= 8;
641 if (fLeadingZeroes)
642 {
643 if (c == 0)
644 continue;
645 if (c & 0x80)
646 *p++ = (fNegative ? 0x80 : 0);
647 else if (fNegative)
648 c |= 0x80;
649 fLeadingZeroes = false;
650 }
651 *p++ = c;
652 }
653 unsigned int nSize = p - (pch + 4);
654 pch[0] = (nSize >> 24) & 0xff;
655 pch[1] = (nSize >> 16) & 0xff;
656 pch[2] = (nSize >> 8) & 0xff;
657 pch[3] = (nSize) & 0xff;
658 BN_mpi2bn(pch, p - pch, this);
659 }
660
661 void setuint64(uint64 n)
662 {
663 unsigned char pch[sizeof(n) + 6];
664 unsigned char* p = pch + 4;
665 bool fLeadingZeroes = true;
666 for (int i = 0; i < 8; i++)
667 {
668 unsigned char c = (n >> 56) & 0xff;
669 n <<= 8;
670 if (fLeadingZeroes)
671 {
672 if (c == 0)
673 continue;
674 if (c & 0x80)
675 *p++ = 0;
676 fLeadingZeroes = false;
677 }
678 *p++ = c;
679 }
680 unsigned int nSize = p - (pch + 4);
681 pch[0] = (nSize >> 24) & 0xff;
682 pch[1] = (nSize >> 16) & 0xff;
683 pch[2] = (nSize >> 8) & 0xff;
684 pch[3] = (nSize) & 0xff;
685 BN_mpi2bn(pch, p - pch, this);
686 }
687
688 void setuint256(uint256 n)
689 {
690 unsigned char pch[sizeof(n) + 6];
691 unsigned char* p = pch + 4;
692 bool fLeadingZeroes = true;
693 unsigned char* pbegin = (unsigned char*)&n;
694 unsigned char* psrc = pbegin + sizeof(n);
695 while (psrc != pbegin)
696 {
697 unsigned char c = *(--psrc);
698 if (fLeadingZeroes)
699 {
700 if (c == 0)
701 continue;
702 if (c & 0x80)
703 *p++ = 0;
704 fLeadingZeroes = false;
705 }
706 *p++ = c;
707 }
708 unsigned int nSize = p - (pch + 4);
709 pch[0] = (nSize >> 24) & 0xff;
710 pch[1] = (nSize >> 16) & 0xff;
711 pch[2] = (nSize >> 8) & 0xff;
712 pch[3] = (nSize >> 0) & 0xff;
713 BN_mpi2bn(pch, p - pch, this);
714 }
715
716 uint256 getuint256()
717 {
718 unsigned int nSize = BN_bn2mpi(this, NULL);
719 if (nSize < 4)
720 return 0;
721 std::vector<unsigned char> vch(nSize);
722 BN_bn2mpi(this, &vch[0]);
723 if (vch.size() > 4)
724 vch[4] &= 0x7f;
725 uint256 n = 0;
726 for (int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
727 ((unsigned char*)&n)[i] = vch[j];
728 return n;
729 }
730
731 void setvch(const std::vector<unsigned char>& vch)
732 {
733 std::vector<unsigned char> vch2(vch.size() + 4);
734 unsigned int nSize = vch.size();
735 // BIGNUM's byte stream format expects 4 bytes of
736 // big endian size data info at the front
737 vch2[0] = (nSize >> 24) & 0xff;
738 vch2[1] = (nSize >> 16) & 0xff;
739 vch2[2] = (nSize >> 8) & 0xff;
740 vch2[3] = (nSize >> 0) & 0xff;
741 // swap data to big endian
742 reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
743 BN_mpi2bn(&vch2[0], vch2.size(), this);
744 }
745
746 std::vector<unsigned char> getvch() const
747 {
748 unsigned int nSize = BN_bn2mpi(this, NULL);
749 if (nSize < 4)
750 return std::vector<unsigned char>();
751 std::vector<unsigned char> vch(nSize);
752 BN_bn2mpi(this, &vch[0]);
753 vch.erase(vch.begin(), vch.begin() + 4);
754 reverse(vch.begin(), vch.end());
755 return vch;
756 }
757
758 CBigNum& SetCompact(unsigned int nCompact)
759 {
760 unsigned int nSize = nCompact >> 24;
761 std::vector<unsigned char> vch(4 + nSize);
762 vch[3] = nSize;
763 if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff;
764 if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff;
765 if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff;
766 BN_mpi2bn(&vch[0], vch.size(), this);
767 return *this;
768 }
769
770 unsigned int GetCompact() const
771 {
772 unsigned int nSize = BN_bn2mpi(this, NULL);
773 std::vector<unsigned char> vch(nSize);
774 nSize -= 4;
775 BN_bn2mpi(this, &vch[0]);
776 unsigned int nCompact = nSize << 24;
777 if (nSize >= 1) nCompact |= (vch[4] << 16);
778 if (nSize >= 2) nCompact |= (vch[5] << 8);
779 if (nSize >= 3) nCompact |= (vch[6] << 0);
780 return nCompact;
781 }
782
783 void SetHex(const std::string& str)
784 {
785 // skip 0x
786 const char* psz = str.c_str();
787 while (isspace(*psz))
788 psz++;
789 bool fNegative = false;
790 if (*psz == '-')
791 {
792 fNegative = true;
793 psz++;
794 }
795 if (psz[0] == '0' && tolower(psz[1]) == 'x')
796 psz += 2;
797 while (isspace(*psz))
798 psz++;
799
800 // hex string to bignum
801 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 };
802 *this = 0;
803 while (isxdigit(*psz))
804 {
805 *this <<= 4;
806 int n = phexdigit[*psz++];
807 *this += n;
808 }
809 if (fNegative)
810 *this = 0 - *this;
811 }
812
813 std::string ToString(int nBase=10) const
814 {
815 CAutoBN_CTX pctx;
816 CBigNum bnBase = nBase;
817 CBigNum bn0 = 0;
818 std::string str;
819 CBigNum bn = *this;
820 BN_set_negative(&bn, false);
821 CBigNum dv;
822 CBigNum rem;
823 if (BN_cmp(&bn, &bn0) == 0)
824 return "0";
825 while (BN_cmp(&bn, &bn0) > 0)
826 {
827 if (!BN_div(&dv, &rem, &bn, &bnBase, pctx))
828 throw bignum_error("CBigNum::ToString() : BN_div failed");
829 bn = dv;
830 unsigned int c = rem.getulong();
831 str += "0123456789abcdef"[c];
832 }
833 if (BN_is_negative(this))
834 str += "-";
835 reverse(str.begin(), str.end());
836 return str;
837 }
838
839 std::string GetHex() const
840 {
841 return ToString(16);
842 }
843
844 unsigned int GetSerializeSize(int nType=0, int nVersion=VERSION) const
845 {
846 return ::GetSerializeSize(getvch(), nType, nVersion);
847 }
848
849 template<typename Stream>
850 void Serialize(Stream& s, int nType=0, int nVersion=VERSION) const
851 {
852 ::Serialize(s, getvch(), nType, nVersion);
853 }
854
855 template<typename Stream>
856 void Unserialize(Stream& s, int nType=0, int nVersion=VERSION)
857 {
858 std::vector<unsigned char> vch;
859 ::Unserialize(s, vch, nType, nVersion);
860 setvch(vch);
861 }
862
863
864 bool operator!() const
865 {
866 return BN_is_zero(this);
867 }
868
869 CBigNum& operator+=(const CBigNum& b)
870 {
871 if (!BN_add(this, this, &b))
872 throw bignum_error("CBigNum::operator+= : BN_add failed");
873 return *this;
874 }
875
876 CBigNum& operator-=(const CBigNum& b)
877 {
878 *this = *this - b;
879 return *this;
880 }
881
882 CBigNum& operator*=(const CBigNum& b)
883 {
884 CAutoBN_CTX pctx;
885 if (!BN_mul(this, this, &b, pctx))
886 throw bignum_error("CBigNum::operator*= : BN_mul failed");
887 return *this;
888 }
889
890 CBigNum& operator/=(const CBigNum& b)
891 {
892 *this = *this / b;
893 return *this;
894 }
895
896 CBigNum& operator%=(const CBigNum& b)
897 {
898 *this = *this % b;
899 return *this;
900 }
901
902 CBigNum& operator<<=(unsigned int shift)
903 {
904 if (!BN_lshift(this, this, shift))
905 throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
906 return *this;
907 }
908
909 CBigNum& operator>>=(unsigned int shift)
910 {
911 // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
912 // if built on ubuntu 9.04 or 9.10, probably depends on version of openssl
913 CBigNum a = 1;
914 a <<= shift;
915 if (BN_cmp(&a, this) > 0)
916 {
917 *this = 0;
918 return *this;
919 }
920
921 if (!BN_rshift(this, this, shift))
922 throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
923 return *this;
924 }
925
926
927 CBigNum& operator++()
928 {
929 // prefix operator
930 if (!BN_add(this, this, BN_value_one()))
931 throw bignum_error("CBigNum::operator++ : BN_add failed");
932 return *this;
933 }
934
935 const CBigNum operator++(int)
936 {
937 // postfix operator
938 const CBigNum ret = *this;
939 ++(*this);
940 return ret;
941 }
942
943 CBigNum& operator--()
944 {
945 // prefix operator
946 CBigNum r;
947 if (!BN_sub(&r, this, BN_value_one()))
948 throw bignum_error("CBigNum::operator-- : BN_sub failed");
949 *this = r;
950 return *this;
951 }
952
953 const CBigNum operator--(int)
954 {
955 // postfix operator
956 const CBigNum ret = *this;
957 --(*this);
958 return ret;
959 }
960
961
962 friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
963 friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
964 friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
965 };
966
967
968
969 inline const CBigNum operator+(const CBigNum& a, const CBigNum& b)
970 {
971 CBigNum r;
972 if (!BN_add(&r, &a, &b))
973 throw bignum_error("CBigNum::operator+ : BN_add failed");
974 return r;
975 }
976
977 inline const CBigNum operator-(const CBigNum& a, const CBigNum& b)
978 {
979 CBigNum r;
980 if (!BN_sub(&r, &a, &b))
981 throw bignum_error("CBigNum::operator- : BN_sub failed");
982 return r;
983 }
984
985 inline const CBigNum operator-(const CBigNum& a)
986 {
987 CBigNum r(a);
988 BN_set_negative(&r, !BN_is_negative(&r));
989 return r;
990 }
991
992 inline const CBigNum operator*(const CBigNum& a, const CBigNum& b)
993 {
994 CAutoBN_CTX pctx;
995 CBigNum r;
996 if (!BN_mul(&r, &a, &b, pctx))
997 throw bignum_error("CBigNum::operator* : BN_mul failed");
998 return r;
999 }
1000
1001 inline const CBigNum operator/(const CBigNum& a, const CBigNum& b)
1002 {
1003 CAutoBN_CTX pctx;
1004 CBigNum r;
1005 if (!BN_div(&r, NULL, &a, &b, pctx))
1006 throw bignum_error("CBigNum::operator/ : BN_div failed");
1007 return r;
1008 }
1009
1010 inline const CBigNum operator%(const CBigNum& a, const CBigNum& b)
1011 {
1012 CAutoBN_CTX pctx;
1013 CBigNum r;
1014 if (!BN_mod(&r, &a, &b, pctx))
1015 throw bignum_error("CBigNum::operator% : BN_div failed");
1016 return r;
1017 }
1018
1019 inline const CBigNum operator<<(const CBigNum& a, unsigned int shift)
1020 {
1021 CBigNum r;
1022 if (!BN_lshift(&r, &a, shift))
1023 throw bignum_error("CBigNum:operator<< : BN_lshift failed");
1024 return r;
1025 }
1026
1027 inline const CBigNum operator>>(const CBigNum& a, unsigned int shift)
1028 {
1029 CBigNum r = a;
1030 r >>= shift;
1031 return r;
1032 }
1033
1034 inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) == 0); }
1035 inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) != 0); }
1036 inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) <= 0); }
1037 inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) >= 0); }
1038 inline bool operator<(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) < 0); }
1039 inline bool operator>(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) > 0); }
1040
1041 #endif