1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2019 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5
6 #include <arith_uint256.h>
7
8 #include <uint256.h>
9 #include <crypto/common.h>
10
11
12 template <unsigned int BITS>
base_uint(const std::string & str)13 base_uint<BITS>::base_uint(const std::string& str)
14 {
15 static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
16
17 SetHex(str);
18 }
19
20 template <unsigned int BITS>
operator <<=(unsigned int shift)21 base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
22 {
23 base_uint<BITS> a(*this);
24 for (int i = 0; i < WIDTH; i++)
25 pn[i] = 0;
26 int k = shift / 32;
27 shift = shift % 32;
28 for (int i = 0; i < WIDTH; i++) {
29 if (i + k + 1 < WIDTH && shift != 0)
30 pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
31 if (i + k < WIDTH)
32 pn[i + k] |= (a.pn[i] << shift);
33 }
34 return *this;
35 }
36
37 template <unsigned int BITS>
operator >>=(unsigned int shift)38 base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
39 {
40 base_uint<BITS> a(*this);
41 for (int i = 0; i < WIDTH; i++)
42 pn[i] = 0;
43 int k = shift / 32;
44 shift = shift % 32;
45 for (int i = 0; i < WIDTH; i++) {
46 if (i - k - 1 >= 0 && shift != 0)
47 pn[i - k - 1] |= (a.pn[i] << (32 - shift));
48 if (i - k >= 0)
49 pn[i - k] |= (a.pn[i] >> shift);
50 }
51 return *this;
52 }
53
54 template <unsigned int BITS>
operator *=(uint32_t b32)55 base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
56 {
57 uint64_t carry = 0;
58 for (int i = 0; i < WIDTH; i++) {
59 uint64_t n = carry + (uint64_t)b32 * pn[i];
60 pn[i] = n & 0xffffffff;
61 carry = n >> 32;
62 }
63 return *this;
64 }
65
66 template <unsigned int BITS>
operator *=(const base_uint & b)67 base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
68 {
69 base_uint<BITS> a;
70 for (int j = 0; j < WIDTH; j++) {
71 uint64_t carry = 0;
72 for (int i = 0; i + j < WIDTH; i++) {
73 uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
74 a.pn[i + j] = n & 0xffffffff;
75 carry = n >> 32;
76 }
77 }
78 *this = a;
79 return *this;
80 }
81
82 template <unsigned int BITS>
operator /=(const base_uint & b)83 base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
84 {
85 base_uint<BITS> div = b; // make a copy, so we can shift.
86 base_uint<BITS> num = *this; // make a copy, so we can subtract.
87 *this = 0; // the quotient.
88 int num_bits = num.bits();
89 int div_bits = div.bits();
90 if (div_bits == 0)
91 throw uint_error("Division by zero");
92 if (div_bits > num_bits) // the result is certainly 0.
93 return *this;
94 int shift = num_bits - div_bits;
95 div <<= shift; // shift so that div and num align.
96 while (shift >= 0) {
97 if (num >= div) {
98 num -= div;
99 pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
100 }
101 div >>= 1; // shift back.
102 shift--;
103 }
104 // num now contains the remainder of the division.
105 return *this;
106 }
107
108 template <unsigned int BITS>
CompareTo(const base_uint<BITS> & b) const109 int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
110 {
111 for (int i = WIDTH - 1; i >= 0; i--) {
112 if (pn[i] < b.pn[i])
113 return -1;
114 if (pn[i] > b.pn[i])
115 return 1;
116 }
117 return 0;
118 }
119
120 template <unsigned int BITS>
EqualTo(uint64_t b) const121 bool base_uint<BITS>::EqualTo(uint64_t b) const
122 {
123 for (int i = WIDTH - 1; i >= 2; i--) {
124 if (pn[i])
125 return false;
126 }
127 if (pn[1] != (b >> 32))
128 return false;
129 if (pn[0] != (b & 0xfffffffful))
130 return false;
131 return true;
132 }
133
134 template <unsigned int BITS>
getdouble() const135 double base_uint<BITS>::getdouble() const
136 {
137 double ret = 0.0;
138 double fact = 1.0;
139 for (int i = 0; i < WIDTH; i++) {
140 ret += fact * pn[i];
141 fact *= 4294967296.0;
142 }
143 return ret;
144 }
145
146 template <unsigned int BITS>
GetHex() const147 std::string base_uint<BITS>::GetHex() const
148 {
149 return ArithToUint256(*this).GetHex();
150 }
151
152 template <unsigned int BITS>
SetHex(const char * psz)153 void base_uint<BITS>::SetHex(const char* psz)
154 {
155 *this = UintToArith256(uint256S(psz));
156 }
157
158 template <unsigned int BITS>
SetHex(const std::string & str)159 void base_uint<BITS>::SetHex(const std::string& str)
160 {
161 SetHex(str.c_str());
162 }
163
164 template <unsigned int BITS>
ToString() const165 std::string base_uint<BITS>::ToString() const
166 {
167 return (GetHex());
168 }
169
170 template <unsigned int BITS>
bits() const171 unsigned int base_uint<BITS>::bits() const
172 {
173 for (int pos = WIDTH - 1; pos >= 0; pos--) {
174 if (pn[pos]) {
175 for (int nbits = 31; nbits > 0; nbits--) {
176 if (pn[pos] & 1U << nbits)
177 return 32 * pos + nbits + 1;
178 }
179 return 32 * pos + 1;
180 }
181 }
182 return 0;
183 }
184
185 // Explicit instantiations for base_uint<256>
186 template base_uint<256>::base_uint(const std::string&);
187 template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
188 template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
189 template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
190 template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b);
191 template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b);
192 template int base_uint<256>::CompareTo(const base_uint<256>&) const;
193 template bool base_uint<256>::EqualTo(uint64_t) const;
194 template double base_uint<256>::getdouble() const;
195 template std::string base_uint<256>::GetHex() const;
196 template std::string base_uint<256>::ToString() const;
197 template void base_uint<256>::SetHex(const char*);
198 template void base_uint<256>::SetHex(const std::string&);
199 template unsigned int base_uint<256>::bits() const;
200
201 // This implementation directly uses shifts instead of going
202 // through an intermediate MPI representation.
SetCompact(uint32_t nCompact,bool * pfNegative,bool * pfOverflow)203 arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
204 {
205 int nSize = nCompact >> 24;
206 uint32_t nWord = nCompact & 0x007fffff;
207 if (nSize <= 3) {
208 nWord >>= 8 * (3 - nSize);
209 *this = nWord;
210 } else {
211 *this = nWord;
212 *this <<= 8 * (nSize - 3);
213 }
214 if (pfNegative)
215 *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
216 if (pfOverflow)
217 *pfOverflow = nWord != 0 && ((nSize > 34) ||
218 (nWord > 0xff && nSize > 33) ||
219 (nWord > 0xffff && nSize > 32));
220 return *this;
221 }
222
GetCompact(bool fNegative) const223 uint32_t arith_uint256::GetCompact(bool fNegative) const
224 {
225 int nSize = (bits() + 7) / 8;
226 uint32_t nCompact = 0;
227 if (nSize <= 3) {
228 nCompact = GetLow64() << 8 * (3 - nSize);
229 } else {
230 arith_uint256 bn = *this >> 8 * (nSize - 3);
231 nCompact = bn.GetLow64();
232 }
233 // The 0x00800000 bit denotes the sign.
234 // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
235 if (nCompact & 0x00800000) {
236 nCompact >>= 8;
237 nSize++;
238 }
239 assert((nCompact & ~0x007fffff) == 0);
240 assert(nSize < 256);
241 nCompact |= nSize << 24;
242 nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
243 return nCompact;
244 }
245
ArithToUint256(const arith_uint256 & a)246 uint256 ArithToUint256(const arith_uint256 &a)
247 {
248 uint256 b;
249 for(int x=0; x<a.WIDTH; ++x)
250 WriteLE32(b.begin() + x*4, a.pn[x]);
251 return b;
252 }
UintToArith256(const uint256 & a)253 arith_uint256 UintToArith256(const uint256 &a)
254 {
255 arith_uint256 b;
256 for(int x=0; x<b.WIDTH; ++x)
257 b.pn[x] = ReadLE32(a.begin() + x*4);
258 return b;
259 }
260