Skip to content

Commit ac26571

Browse files
laanwjlaanwj
committed
Merge pull request #4437
de79aaa Move non-trivial uint256.h methods to uint256.cpp (Pieter Wuille)
2 parents eba8c44 + de79aaa commit ac26571

File tree

5 files changed

+316
-245
lines changed

5 files changed

+316
-245
lines changed

‎src/Makefile.am

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -192,6 +192,7 @@ libbitcoin_util_a_SOURCES = \
192192
chainparamsbase.cpp \
193193
rpcprotocol.cpp \
194194
sync.cpp \
195+
uint256.cpp \
195196
util.cpp \
196197
version.cpp \
197198
compat/glibc_sanity.cpp \

‎src/uint256.cpp

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

0 commit comments

Comments
 (0)