You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

arith_uint256.h 8.7KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. // Copyright (c) 2009-2010 Satoshi Nakamoto
  2. // Copyright (c) 2009-2016 The Starwels developers
  3. // Distributed under the MIT software license, see the accompanying
  4. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5. #ifndef STARWELS_ARITH_UINT256_H
  6. #define STARWELS_ARITH_UINT256_H
  7. #include <assert.h>
  8. #include <cstring>
  9. #include <stdexcept>
  10. #include <stdint.h>
  11. #include <string>
  12. #include <vector>
  13. class uint256;
  14. class uint_error : public std::runtime_error {
  15. public:
  16. explicit uint_error(const std::string& str) : std::runtime_error(str) {}
  17. };
  18. /** Template base class for unsigned big integers. */
  19. template<unsigned int BITS>
  20. class base_uint
  21. {
  22. protected:
  23. enum { WIDTH=BITS/32 };
  24. uint32_t pn[WIDTH];
  25. public:
  26. base_uint()
  27. {
  28. static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
  29. for (int i = 0; i < WIDTH; i++)
  30. pn[i] = 0;
  31. }
  32. base_uint(const base_uint& b)
  33. {
  34. static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
  35. for (int i = 0; i < WIDTH; i++)
  36. pn[i] = b.pn[i];
  37. }
  38. base_uint& operator=(const base_uint& b)
  39. {
  40. for (int i = 0; i < WIDTH; i++)
  41. pn[i] = b.pn[i];
  42. return *this;
  43. }
  44. base_uint(uint64_t b)
  45. {
  46. static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
  47. pn[0] = (unsigned int)b;
  48. pn[1] = (unsigned int)(b >> 32);
  49. for (int i = 2; i < WIDTH; i++)
  50. pn[i] = 0;
  51. }
  52. explicit base_uint(const std::string& str);
  53. bool operator!() const
  54. {
  55. for (int i = 0; i < WIDTH; i++)
  56. if (pn[i] != 0)
  57. return false;
  58. return true;
  59. }
  60. const base_uint operator~() const
  61. {
  62. base_uint ret;
  63. for (int i = 0; i < WIDTH; i++)
  64. ret.pn[i] = ~pn[i];
  65. return ret;
  66. }
  67. const base_uint operator-() const
  68. {
  69. base_uint ret;
  70. for (int i = 0; i < WIDTH; i++)
  71. ret.pn[i] = ~pn[i];
  72. ret++;
  73. return ret;
  74. }
  75. double getdouble() const;
  76. base_uint& operator=(uint64_t b)
  77. {
  78. pn[0] = (unsigned int)b;
  79. pn[1] = (unsigned int)(b >> 32);
  80. for (int i = 2; i < WIDTH; i++)
  81. pn[i] = 0;
  82. return *this;
  83. }
  84. base_uint& operator^=(const base_uint& b)
  85. {
  86. for (int i = 0; i < WIDTH; i++)
  87. pn[i] ^= b.pn[i];
  88. return *this;
  89. }
  90. base_uint& operator&=(const base_uint& b)
  91. {
  92. for (int i = 0; i < WIDTH; i++)
  93. pn[i] &= b.pn[i];
  94. return *this;
  95. }
  96. base_uint& operator|=(const base_uint& b)
  97. {
  98. for (int i = 0; i < WIDTH; i++)
  99. pn[i] |= b.pn[i];
  100. return *this;
  101. }
  102. base_uint& operator^=(uint64_t b)
  103. {
  104. pn[0] ^= (unsigned int)b;
  105. pn[1] ^= (unsigned int)(b >> 32);
  106. return *this;
  107. }
  108. base_uint& operator|=(uint64_t b)
  109. {
  110. pn[0] |= (unsigned int)b;
  111. pn[1] |= (unsigned int)(b >> 32);
  112. return *this;
  113. }
  114. base_uint& operator<<=(unsigned int shift);
  115. base_uint& operator>>=(unsigned int shift);
  116. base_uint& operator+=(const base_uint& b)
  117. {
  118. uint64_t carry = 0;
  119. for (int i = 0; i < WIDTH; i++)
  120. {
  121. uint64_t n = carry + pn[i] + b.pn[i];
  122. pn[i] = n & 0xffffffff;
  123. carry = n >> 32;
  124. }
  125. return *this;
  126. }
  127. base_uint& operator-=(const base_uint& b)
  128. {
  129. *this += -b;
  130. return *this;
  131. }
  132. base_uint& operator+=(uint64_t b64)
  133. {
  134. base_uint b;
  135. b = b64;
  136. *this += b;
  137. return *this;
  138. }
  139. base_uint& operator-=(uint64_t b64)
  140. {
  141. base_uint b;
  142. b = b64;
  143. *this += -b;
  144. return *this;
  145. }
  146. base_uint& operator*=(uint32_t b32);
  147. base_uint& operator*=(const base_uint& b);
  148. base_uint& operator/=(const base_uint& b);
  149. base_uint& operator++()
  150. {
  151. // prefix operator
  152. int i = 0;
  153. while (i < WIDTH && ++pn[i] == 0)
  154. i++;
  155. return *this;
  156. }
  157. const base_uint operator++(int)
  158. {
  159. // postfix operator
  160. const base_uint ret = *this;
  161. ++(*this);
  162. return ret;
  163. }
  164. base_uint& operator--()
  165. {
  166. // prefix operator
  167. int i = 0;
  168. while (i < WIDTH && --pn[i] == (uint32_t)-1)
  169. i++;
  170. return *this;
  171. }
  172. const base_uint operator--(int)
  173. {
  174. // postfix operator
  175. const base_uint ret = *this;
  176. --(*this);
  177. return ret;
  178. }
  179. int CompareTo(const base_uint& b) const;
  180. bool EqualTo(uint64_t b) const;
  181. friend inline const base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
  182. friend inline const base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
  183. friend inline const base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
  184. friend inline const base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
  185. friend inline const base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
  186. friend inline const base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
  187. friend inline const base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
  188. friend inline const base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
  189. friend inline const base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
  190. friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
  191. friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
  192. friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
  193. friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
  194. friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
  195. friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
  196. friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
  197. friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
  198. friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
  199. std::string GetHex() const;
  200. void SetHex(const char* psz);
  201. void SetHex(const std::string& str);
  202. std::string ToString() const;
  203. unsigned int size() const
  204. {
  205. return sizeof(pn);
  206. }
  207. /**
  208. * Returns the position of the highest bit set plus one, or zero if the
  209. * value is zero.
  210. */
  211. unsigned int bits() const;
  212. uint64_t GetLow64() const
  213. {
  214. assert(WIDTH >= 2);
  215. return pn[0] | (uint64_t)pn[1] << 32;
  216. }
  217. };
  218. /** 256-bit unsigned big integer. */
  219. class arith_uint256 : public base_uint<256> {
  220. public:
  221. arith_uint256() {}
  222. arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
  223. arith_uint256(uint64_t b) : base_uint<256>(b) {}
  224. explicit arith_uint256(const std::string& str) : base_uint<256>(str) {}
  225. /**
  226. * The "compact" format is a representation of a whole
  227. * number N using an unsigned 32bit number similar to a
  228. * floating point format.
  229. * The most significant 8 bits are the unsigned exponent of base 256.
  230. * This exponent can be thought of as "number of bytes of N".
  231. * The lower 23 bits are the mantissa.
  232. * Bit number 24 (0x800000) represents the sign of N.
  233. * N = (-1^sign) * mantissa * 256^(exponent-3)
  234. *
  235. * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
  236. * MPI uses the most significant bit of the first byte as sign.
  237. * Thus 0x1234560000 is compact (0x05123456)
  238. * and 0xc0de000000 is compact (0x0600c0de)
  239. *
  240. * Starwels only uses this "compact" format for encoding difficulty
  241. * targets, which are unsigned 256bit quantities. Thus, all the
  242. * complexities of the sign bit and using base 256 are probably an
  243. * implementation accident.
  244. */
  245. arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr);
  246. uint32_t GetCompact(bool fNegative = false) const;
  247. friend uint256 ArithToUint256(const arith_uint256 &);
  248. friend arith_uint256 UintToArith256(const uint256 &);
  249. };
  250. uint256 ArithToUint256(const arith_uint256 &);
  251. arith_uint256 UintToArith256(const uint256 &);
  252. #endif // STARWELS_ARITH_UINT256_H