Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 The Bitcoin 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 "utilstrencodings.h"
10 : #include "crypto/common.h"
11 :
12 : #include <stdio.h>
13 : #include <string.h>
14 :
15 : template <unsigned int BITS>
16 16 : base_uint<BITS>::base_uint(const std::string& str)
17 : {
18 : SetHex(str);
19 16 : }
20 :
21 : template <unsigned int BITS>
22 173501 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
23 : {
24 : base_uint<BITS> a(*this);
25 1388008 : for (int i = 0; i < WIDTH; i++)
26 1388008 : pn[i] = 0;
27 173501 : int k = shift / 32;
28 173501 : shift = shift % 32;
29 1561509 : for (int i = 0; i < WIDTH; i++) {
30 1388008 : if (i + k + 1 < WIDTH && shift != 0)
31 219592 : pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
32 1388008 : if (i + k < WIDTH)
33 544522 : pn[i + k] |= (a.pn[i] << shift);
34 : }
35 173501 : return *this;
36 : }
37 :
38 : template <unsigned int BITS>
39 99752 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
40 : {
41 : base_uint<BITS> a(*this);
42 798016 : for (int i = 0; i < WIDTH; i++)
43 798016 : pn[i] = 0;
44 99752 : int k = shift / 32;
45 99752 : shift = shift % 32;
46 897768 : for (int i = 0; i < WIDTH; i++) {
47 798016 : if (i - k - 1 >= 0 && shift != 0)
48 604828 : pn[i - k - 1] |= (a.pn[i] << (32 - shift));
49 798016 : if (i - k >= 0)
50 705341 : pn[i - k] |= (a.pn[i] >> shift);
51 : }
52 99752 : return *this;
53 : }
54 :
55 : template <unsigned int BITS>
56 92 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
57 : {
58 92 : uint64_t carry = 0;
59 828 : for (int i = 0; i < WIDTH; i++) {
60 736 : uint64_t n = carry + (uint64_t)b32 * pn[i];
61 736 : pn[i] = n & 0xffffffff;
62 736 : carry = n >> 32;
63 : }
64 92 : return *this;
65 : }
66 :
67 : template <unsigned int BITS>
68 1012 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
69 : {
70 : base_uint<BITS> a = *this;
71 : *this = 0;
72 8096 : for (int j = 0; j < WIDTH; j++) {
73 : uint64_t carry = 0;
74 36432 : for (int i = 0; i + j < WIDTH; i++) {
75 36432 : uint64_t n = carry + pn[i + j] + (uint64_t)a.pn[j] * b.pn[i];
76 36432 : pn[i + j] = n & 0xffffffff;
77 36432 : carry = n >> 32;
78 : }
79 : }
80 1012 : return *this;
81 : }
82 :
83 : template <unsigned int BITS>
84 28774 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
85 : {
86 : base_uint<BITS> div = b; // make a copy, so we can shift.
87 : base_uint<BITS> num = *this; // make a copy, so we can subtract.
88 : *this = 0; // the quotient.
89 28774 : int num_bits = num.bits();
90 28774 : int div_bits = div.bits();
91 28774 : if (div_bits == 0)
92 6 : throw uint_error("Division by zero");
93 28772 : if (div_bits > num_bits) // the result is certainly 0.
94 : return *this;
95 28771 : int shift = num_bits - div_bits;
96 28771 : div <<= shift; // shift so that div and num align.
97 111456 : while (shift >= 0) {
98 82685 : if (num >= div) {
99 38001 : num -= div;
100 38001 : pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
101 : }
102 82685 : div >>= 1; // shift back.
103 82685 : shift--;
104 : }
105 : // num now contains the remainder of the division.
106 : return *this;
107 : }
108 :
109 : template <unsigned int BITS>
110 9221155 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
111 : {
112 73117685 : for (int i = WIDTH - 1; i >= 0; i--) {
113 73059873 : if (pn[i] < b.pn[i])
114 : return -1;
115 67298105 : if (pn[i] > b.pn[i])
116 : return 1;
117 : }
118 : return 0;
119 : }
120 :
121 : template <unsigned int BITS>
122 91647 : bool base_uint<BITS>::EqualTo(uint64_t b) const
123 : {
124 105837 : for (int i = WIDTH - 1; i >= 2; i--) {
125 103593 : if (pn[i])
126 : return false;
127 : }
128 2244 : if (pn[1] != (b >> 32))
129 : return false;
130 2212 : if (pn[0] != (b & 0xfffffffful))
131 : return false;
132 208 : return true;
133 : }
134 :
135 : template <unsigned int BITS>
136 6136 : double base_uint<BITS>::getdouble() const
137 : {
138 6136 : double ret = 0.0;
139 6136 : double fact = 1.0;
140 55224 : for (int i = 0; i < WIDTH; i++) {
141 49088 : ret += fact * pn[i];
142 49088 : fact *= 4294967296.0;
143 : }
144 6136 : return ret;
145 : }
146 :
147 : template <unsigned int BITS>
148 83 : std::string base_uint<BITS>::GetHex() const
149 : {
150 83 : return ArithToUint256(*this).GetHex();
151 : }
152 :
153 : template <unsigned int BITS>
154 20 : void base_uint<BITS>::SetHex(const char* psz)
155 : {
156 20 : *this = UintToArith256(uint256S(psz));
157 20 : }
158 :
159 : template <unsigned int BITS>
160 4 : void base_uint<BITS>::SetHex(const std::string& str)
161 : {
162 20 : SetHex(str.c_str());
163 4 : }
164 :
165 : template <unsigned int BITS>
166 38 : std::string base_uint<BITS>::ToString() const
167 : {
168 38 : return (GetHex());
169 : }
170 :
171 : template <unsigned int BITS>
172 68096 : unsigned int base_uint<BITS>::bits() const
173 : {
174 89598 : for (int pos = WIDTH - 1; pos >= 0; pos--) {
175 89585 : if (pn[pos]) {
176 88832 : for (int bits = 31; bits > 0; bits--) {
177 156913 : if (pn[pos] & 1 << bits)
178 68081 : return 32 * pos + bits + 1;
179 : }
180 2 : return 32 * pos + 1;
181 : }
182 : }
183 : return 0;
184 : }
185 :
186 : // Explicit instantiations for base_uint<256>
187 : template base_uint<256>::base_uint(const std::string&);
188 : template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
189 : template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
190 : template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
191 : template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b);
192 : template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b);
193 : template int base_uint<256>::CompareTo(const base_uint<256>&) const;
194 : template bool base_uint<256>::EqualTo(uint64_t) const;
195 : template double base_uint<256>::getdouble() const;
196 : template std::string base_uint<256>::GetHex() const;
197 : template std::string base_uint<256>::ToString() const;
198 : template void base_uint<256>::SetHex(const char*);
199 : template void base_uint<256>::SetHex(const std::string&);
200 : template unsigned int base_uint<256>::bits() const;
201 :
202 : // This implementation directly uses shifts instead of going
203 : // through an intermediate MPI representation.
204 89235 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
205 : {
206 89235 : int nSize = nCompact >> 24;
207 89235 : uint32_t nWord = nCompact & 0x007fffff;
208 89235 : if (nSize <= 3) {
209 13 : nWord >>= 8 * (3 - nSize);
210 26 : *this = nWord;
211 : } else {
212 178444 : *this = nWord;
213 89222 : *this <<= 8 * (nSize - 3);
214 : }
215 89235 : if (pfNegative)
216 89231 : *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
217 89235 : if (pfOverflow)
218 178450 : *pfOverflow = nWord != 0 && ((nSize > 34) ||
219 178438 : (nWord > 0xff && nSize > 33) ||
220 178450 : (nWord > 0xffff && nSize > 32));
221 89235 : return *this;
222 : }
223 :
224 9548 : uint32_t arith_uint256::GetCompact(bool fNegative) const
225 : {
226 9548 : int nSize = (bits() + 7) / 8;
227 9548 : uint32_t nCompact = 0;
228 9548 : if (nSize <= 3) {
229 32 : nCompact = GetLow64() << 8 * (3 - nSize);
230 : } else {
231 19064 : arith_uint256 bn = *this >> 8 * (nSize - 3);
232 19064 : nCompact = bn.GetLow64();
233 : }
234 : // The 0x00800000 bit denotes the sign.
235 : // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
236 9548 : if (nCompact & 0x00800000) {
237 144 : nCompact >>= 8;
238 144 : nSize++;
239 : }
240 9548 : assert((nCompact & ~0x007fffff) == 0);
241 9548 : assert(nSize < 256);
242 9548 : nCompact |= nSize << 24;
243 9548 : nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
244 9548 : return nCompact;
245 : }
246 :
247 152191 : uint256 ArithToUint256(const arith_uint256 &a)
248 : {
249 : uint256 b;
250 1370466 : for(int x=0; x<a.WIDTH; ++x)
251 1218192 : WriteLE32(b.begin() + x*4, a.pn[x]);
252 152191 : return b;
253 : }
254 294208 : arith_uint256 UintToArith256(const uint256 &a)
255 : {
256 : arith_uint256 b;
257 2353824 : for(int x=0; x<b.WIDTH; ++x)
258 7061312 : b.pn[x] = ReadLE32(a.begin() + x*4);
259 294208 : return b;
260 : }
|
