From bfc6070342b9f43bcf125526e6a3c8ed34e29a71 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Mon, 15 Dec 2014 10:22:19 +0100 Subject: uint256->arith_uint256 blob256->uint256 Introduce new opaque implementation of `uint256`, move old "arithmetic" implementation to `arith_uint256. --- src/arith_uint256.cpp | 357 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 357 insertions(+) create mode 100644 src/arith_uint256.cpp (limited to 'src/arith_uint256.cpp') diff --git a/src/arith_uint256.cpp b/src/arith_uint256.cpp new file mode 100644 index 000000000..0dba429a8 --- /dev/null +++ b/src/arith_uint256.cpp @@ -0,0 +1,357 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2014 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "arith_uint256.h" + +#include "utilstrencodings.h" + +#include +#include + +template +base_uint::base_uint(const std::string& str) +{ + SetHex(str); +} + +template +base_uint::base_uint(const std::vector& vch) +{ + if (vch.size() != sizeof(pn)) + throw uint_error("Converting vector of wrong size to base_uint"); + memcpy(pn, &vch[0], sizeof(pn)); +} + +template +base_uint& base_uint::operator<<=(unsigned int shift) +{ + base_uint a(*this); + for (int i = 0; i < WIDTH; i++) + pn[i] = 0; + int k = shift / 32; + shift = shift % 32; + for (int i = 0; i < WIDTH; i++) { + if (i + k + 1 < WIDTH && shift != 0) + pn[i + k + 1] |= (a.pn[i] >> (32 - shift)); + if (i + k < WIDTH) + pn[i + k] |= (a.pn[i] << shift); + } + return *this; +} + +template +base_uint& base_uint::operator>>=(unsigned int shift) +{ + base_uint a(*this); + for (int i = 0; i < WIDTH; i++) + pn[i] = 0; + int k = shift / 32; + shift = shift % 32; + for (int i = 0; i < WIDTH; i++) { + if (i - k - 1 >= 0 && shift != 0) + pn[i - k - 1] |= (a.pn[i] << (32 - shift)); + if (i - k >= 0) + pn[i - k] |= (a.pn[i] >> shift); + } + return *this; +} + +template +base_uint& base_uint::operator*=(uint32_t b32) +{ + uint64_t carry = 0; + for (int i = 0; i < WIDTH; i++) { + uint64_t n = carry + (uint64_t)b32 * pn[i]; + pn[i] = n & 0xffffffff; + carry = n >> 32; + } + return *this; +} + +template +base_uint& base_uint::operator*=(const base_uint& b) +{ + base_uint a = *this; + *this = 0; + for (int j = 0; j < WIDTH; j++) { + uint64_t carry = 0; + for (int i = 0; i + j < WIDTH; i++) { + uint64_t n = carry + pn[i + j] + (uint64_t)a.pn[j] * b.pn[i]; + pn[i + j] = n & 0xffffffff; + carry = n >> 32; + } + } + return *this; +} + +template +base_uint& base_uint::operator/=(const base_uint& b) +{ + base_uint div = b; // make a copy, so we can shift. + base_uint num = *this; // make a copy, so we can subtract. + *this = 0; // the quotient. + int num_bits = num.bits(); + int div_bits = div.bits(); + if (div_bits == 0) + throw uint_error("Division by zero"); + if (div_bits > num_bits) // the result is certainly 0. + return *this; + int shift = num_bits - div_bits; + div <<= shift; // shift so that div and num align. + while (shift >= 0) { + if (num >= div) { + num -= div; + pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result. + } + div >>= 1; // shift back. + shift--; + } + // num now contains the remainder of the division. + return *this; +} + +template +int base_uint::CompareTo(const base_uint& b) const +{ + for (int i = WIDTH - 1; i >= 0; i--) { + if (pn[i] < b.pn[i]) + return -1; + if (pn[i] > b.pn[i]) + return 1; + } + return 0; +} + +template +bool base_uint::EqualTo(uint64_t b) const +{ + for (int i = WIDTH - 1; i >= 2; i--) { + if (pn[i]) + return false; + } + if (pn[1] != (b >> 32)) + return false; + if (pn[0] != (b & 0xfffffffful)) + return false; + return true; +} + +template +double base_uint::getdouble() const +{ + double ret = 0.0; + double fact = 1.0; + for (int i = 0; i < WIDTH; i++) { + ret += fact * pn[i]; + fact *= 4294967296.0; + } + return ret; +} + +template +std::string base_uint::GetHex() const +{ + char psz[sizeof(pn) * 2 + 1]; + for (unsigned int i = 0; i < sizeof(pn); i++) + sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]); + return std::string(psz, psz + sizeof(pn) * 2); +} + +template +void base_uint::SetHex(const char* psz) +{ + memset(pn, 0, sizeof(pn)); + + // skip leading spaces + while (isspace(*psz)) + psz++; + + // skip 0x + if (psz[0] == '0' && tolower(psz[1]) == 'x') + psz += 2; + + // hex string to uint + const char* pbegin = psz; + while (::HexDigit(*psz) != -1) + psz++; + psz--; + unsigned char* p1 = (unsigned char*)pn; + unsigned char* pend = p1 + WIDTH * 4; + while (psz >= pbegin && p1 < pend) { + *p1 = ::HexDigit(*psz--); + if (psz >= pbegin) { + *p1 |= ((unsigned char)::HexDigit(*psz--) << 4); + p1++; + } + } +} + +template +void base_uint::SetHex(const std::string& str) +{ + SetHex(str.c_str()); +} + +template +std::string base_uint::ToString() const +{ + return (GetHex()); +} + +template +unsigned int base_uint::bits() const +{ + for (int pos = WIDTH - 1; pos >= 0; pos--) { + if (pn[pos]) { + for (int bits = 31; bits > 0; bits--) { + if (pn[pos] & 1 << bits) + return 32 * pos + bits + 1; + } + return 32 * pos + 1; + } + } + return 0; +} + +// Explicit instantiations for base_uint<160> +template base_uint<160>::base_uint(const std::string&); +template base_uint<160>::base_uint(const std::vector&); +template base_uint<160>& base_uint<160>::operator<<=(unsigned int); +template base_uint<160>& base_uint<160>::operator>>=(unsigned int); +template base_uint<160>& base_uint<160>::operator*=(uint32_t b32); +template base_uint<160>& base_uint<160>::operator*=(const base_uint<160>& b); +template base_uint<160>& base_uint<160>::operator/=(const base_uint<160>& b); +template int base_uint<160>::CompareTo(const base_uint<160>&) const; +template bool base_uint<160>::EqualTo(uint64_t) const; +template double base_uint<160>::getdouble() const; +template std::string base_uint<160>::GetHex() const; +template std::string base_uint<160>::ToString() const; +template void base_uint<160>::SetHex(const char*); +template void base_uint<160>::SetHex(const std::string&); +template unsigned int base_uint<160>::bits() const; + +// Explicit instantiations for base_uint<256> +template base_uint<256>::base_uint(const std::string&); +template base_uint<256>::base_uint(const std::vector&); +template base_uint<256>& base_uint<256>::operator<<=(unsigned int); +template base_uint<256>& base_uint<256>::operator>>=(unsigned int); +template base_uint<256>& base_uint<256>::operator*=(uint32_t b32); +template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b); +template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b); +template int base_uint<256>::CompareTo(const base_uint<256>&) const; +template bool base_uint<256>::EqualTo(uint64_t) const; +template double base_uint<256>::getdouble() const; +template std::string base_uint<256>::GetHex() const; +template std::string base_uint<256>::ToString() const; +template void base_uint<256>::SetHex(const char*); +template void base_uint<256>::SetHex(const std::string&); +template unsigned int base_uint<256>::bits() const; + +// This implementation directly uses shifts instead of going +// through an intermediate MPI representation. +arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow) +{ + int nSize = nCompact >> 24; + uint32_t nWord = nCompact & 0x007fffff; + if (nSize <= 3) { + nWord >>= 8 * (3 - nSize); + *this = nWord; + } else { + *this = nWord; + *this <<= 8 * (nSize - 3); + } + if (pfNegative) + *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0; + if (pfOverflow) + *pfOverflow = nWord != 0 && ((nSize > 34) || + (nWord > 0xff && nSize > 33) || + (nWord > 0xffff && nSize > 32)); + return *this; +} + +uint32_t arith_uint256::GetCompact(bool fNegative) const +{ + int nSize = (bits() + 7) / 8; + uint32_t nCompact = 0; + if (nSize <= 3) { + nCompact = GetLow64() << 8 * (3 - nSize); + } else { + arith_uint256 bn = *this >> 8 * (nSize - 3); + nCompact = bn.GetLow64(); + } + // The 0x00800000 bit denotes the sign. + // Thus, if it is already set, divide the mantissa by 256 and increase the exponent. + if (nCompact & 0x00800000) { + nCompact >>= 8; + nSize++; + } + assert((nCompact & ~0x007fffff) == 0); + assert(nSize < 256); + nCompact |= nSize << 24; + nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0); + return nCompact; +} + +static void inline HashMix(uint32_t& a, uint32_t& b, uint32_t& c) +{ + // Taken from lookup3, by Bob Jenkins. + a -= c; + a ^= ((c << 4) | (c >> 28)); + c += b; + b -= a; + b ^= ((a << 6) | (a >> 26)); + a += c; + c -= b; + c ^= ((b << 8) | (b >> 24)); + b += a; + a -= c; + a ^= ((c << 16) | (c >> 16)); + c += b; + b -= a; + b ^= ((a << 19) | (a >> 13)); + a += c; + c -= b; + c ^= ((b << 4) | (b >> 28)); + b += a; +} + +static void inline HashFinal(uint32_t& a, uint32_t& b, uint32_t& c) +{ + // Taken from lookup3, by Bob Jenkins. + c ^= b; + c -= ((b << 14) | (b >> 18)); + a ^= c; + a -= ((c << 11) | (c >> 21)); + b ^= a; + b -= ((a << 25) | (a >> 7)); + c ^= b; + c -= ((b << 16) | (b >> 16)); + a ^= c; + a -= ((c << 4) | (c >> 28)); + b ^= a; + b -= ((a << 14) | (a >> 18)); + c ^= b; + c -= ((b << 24) | (b >> 8)); +} + +uint64_t arith_uint256::GetHash(const arith_uint256& salt) const +{ + uint32_t a, b, c; + a = b = c = 0xdeadbeef + (WIDTH << 2); + + a += pn[0] ^ salt.pn[0]; + b += pn[1] ^ salt.pn[1]; + c += pn[2] ^ salt.pn[2]; + HashMix(a, b, c); + a += pn[3] ^ salt.pn[3]; + b += pn[4] ^ salt.pn[4]; + c += pn[5] ^ salt.pn[5]; + HashMix(a, b, c); + a += pn[6] ^ salt.pn[6]; + b += pn[7] ^ salt.pn[7]; + HashFinal(a, b, c); + + return ((((uint64_t)b) << 32) | c); +} -- cgit v1.2.3 From 92cdb1aace3c7343e9c9472061508d3b01d9883d Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Tue, 16 Dec 2014 17:29:51 +0100 Subject: Add conversion functions arith_uint256<->uint_256 --- src/arith_uint256.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'src/arith_uint256.cpp') diff --git a/src/arith_uint256.cpp b/src/arith_uint256.cpp index 0dba429a8..f0b6a6a3b 100644 --- a/src/arith_uint256.cpp +++ b/src/arith_uint256.cpp @@ -5,6 +5,7 @@ #include "arith_uint256.h" +#include "uint256.h" #include "utilstrencodings.h" #include @@ -355,3 +356,18 @@ uint64_t arith_uint256::GetHash(const arith_uint256& salt) const return ((((uint64_t)b) << 32) | c); } + +uint256 ArithToUint256(const arith_uint256 &a) +{ + uint256 b; + // TODO: needs bswap32 on big-endian + memcpy(b.begin(), a.pn, a.size()); + return b; +} +arith_uint256 UintToArith256(const uint256 &a) +{ + arith_uint256 b; + // TODO: needs bswap32 on big-endian + memcpy(b.pn, a.begin(), a.size()); + return b; +} -- cgit v1.2.3 From edc720479d0749a000d5a6970da6d2d72657cf38 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Tue, 16 Dec 2014 15:44:57 +0100 Subject: Remove arith_uint160 We never do 160-bit arithmetic. --- src/arith_uint256.cpp | 17 ----------------- 1 file changed, 17 deletions(-) (limited to 'src/arith_uint256.cpp') diff --git a/src/arith_uint256.cpp b/src/arith_uint256.cpp index f0b6a6a3b..12f9e7d1b 100644 --- a/src/arith_uint256.cpp +++ b/src/arith_uint256.cpp @@ -216,23 +216,6 @@ unsigned int base_uint::bits() const return 0; } -// Explicit instantiations for base_uint<160> -template base_uint<160>::base_uint(const std::string&); -template base_uint<160>::base_uint(const std::vector&); -template base_uint<160>& base_uint<160>::operator<<=(unsigned int); -template base_uint<160>& base_uint<160>::operator>>=(unsigned int); -template base_uint<160>& base_uint<160>::operator*=(uint32_t b32); -template base_uint<160>& base_uint<160>::operator*=(const base_uint<160>& b); -template base_uint<160>& base_uint<160>::operator/=(const base_uint<160>& b); -template int base_uint<160>::CompareTo(const base_uint<160>&) const; -template bool base_uint<160>::EqualTo(uint64_t) const; -template double base_uint<160>::getdouble() const; -template std::string base_uint<160>::GetHex() const; -template std::string base_uint<160>::ToString() const; -template void base_uint<160>::SetHex(const char*); -template void base_uint<160>::SetHex(const std::string&); -template unsigned int base_uint<160>::bits() const; - // Explicit instantiations for base_uint<256> template base_uint<256>::base_uint(const std::string&); template base_uint<256>::base_uint(const std::vector&); -- cgit v1.2.3 From 30007fda76aa7ba4e4090f7a16298874a7722926 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Tue, 16 Dec 2014 15:47:29 +0100 Subject: Remove now-unused methods from arith_uint256 and base_uint - Methods that access the guts of arith_uint256 are removed, as these are incompatible between endians. Use uint256 instead - Serialization is no longer needed as arith_uint256's are never read or written - GetHash is never used on arith_uint256 --- src/arith_uint256.cpp | 62 --------------------------------------------------- 1 file changed, 62 deletions(-) (limited to 'src/arith_uint256.cpp') diff --git a/src/arith_uint256.cpp b/src/arith_uint256.cpp index 12f9e7d1b..11df3b05c 100644 --- a/src/arith_uint256.cpp +++ b/src/arith_uint256.cpp @@ -278,68 +278,6 @@ uint32_t arith_uint256::GetCompact(bool fNegative) const return nCompact; } -static void inline HashMix(uint32_t& a, uint32_t& b, uint32_t& c) -{ - // Taken from lookup3, by Bob Jenkins. - a -= c; - a ^= ((c << 4) | (c >> 28)); - c += b; - b -= a; - b ^= ((a << 6) | (a >> 26)); - a += c; - c -= b; - c ^= ((b << 8) | (b >> 24)); - b += a; - a -= c; - a ^= ((c << 16) | (c >> 16)); - c += b; - b -= a; - b ^= ((a << 19) | (a >> 13)); - a += c; - c -= b; - c ^= ((b << 4) | (b >> 28)); - b += a; -} - -static void inline HashFinal(uint32_t& a, uint32_t& b, uint32_t& c) -{ - // Taken from lookup3, by Bob Jenkins. - c ^= b; - c -= ((b << 14) | (b >> 18)); - a ^= c; - a -= ((c << 11) | (c >> 21)); - b ^= a; - b -= ((a << 25) | (a >> 7)); - c ^= b; - c -= ((b << 16) | (b >> 16)); - a ^= c; - a -= ((c << 4) | (c >> 28)); - b ^= a; - b -= ((a << 14) | (a >> 18)); - c ^= b; - c -= ((b << 24) | (b >> 8)); -} - -uint64_t arith_uint256::GetHash(const arith_uint256& salt) const -{ - uint32_t a, b, c; - a = b = c = 0xdeadbeef + (WIDTH << 2); - - a += pn[0] ^ salt.pn[0]; - b += pn[1] ^ salt.pn[1]; - c += pn[2] ^ salt.pn[2]; - HashMix(a, b, c); - a += pn[3] ^ salt.pn[3]; - b += pn[4] ^ salt.pn[4]; - c += pn[5] ^ salt.pn[5]; - HashMix(a, b, c); - a += pn[6] ^ salt.pn[6]; - b += pn[7] ^ salt.pn[7]; - HashFinal(a, b, c); - - return ((((uint64_t)b) << 32) | c); -} - uint256 ArithToUint256(const arith_uint256 &a) { uint256 b; -- cgit v1.2.3 From 6bd0dc2a845b4d17d5ffabbdadda80d47d6c2dc3 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Fri, 19 Dec 2014 13:07:07 +0100 Subject: arith_uint256: remove initialization from byte vector Remove initialization from vector (as this is only used in the tests). Also implement SetHex and GetHex in terms of uint256, to avoid duplicate code as well as avoid endianness issues (as they work in term of bytes). --- src/arith_uint256.cpp | 39 ++------------------------------------- 1 file changed, 2 insertions(+), 37 deletions(-) (limited to 'src/arith_uint256.cpp') diff --git a/src/arith_uint256.cpp b/src/arith_uint256.cpp index 11df3b05c..1243823da 100644 --- a/src/arith_uint256.cpp +++ b/src/arith_uint256.cpp @@ -17,14 +17,6 @@ base_uint::base_uint(const std::string& str) SetHex(str); } -template -base_uint::base_uint(const std::vector& vch) -{ - if (vch.size() != sizeof(pn)) - throw uint_error("Converting vector of wrong size to base_uint"); - memcpy(pn, &vch[0], sizeof(pn)); -} - template base_uint& base_uint::operator<<=(unsigned int shift) { @@ -154,39 +146,13 @@ double base_uint::getdouble() const template std::string base_uint::GetHex() const { - char psz[sizeof(pn) * 2 + 1]; - for (unsigned int i = 0; i < sizeof(pn); i++) - sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]); - return std::string(psz, psz + sizeof(pn) * 2); + return ArithToUint256(*this).GetHex(); } template void base_uint::SetHex(const char* psz) { - memset(pn, 0, sizeof(pn)); - - // skip leading spaces - while (isspace(*psz)) - psz++; - - // skip 0x - if (psz[0] == '0' && tolower(psz[1]) == 'x') - psz += 2; - - // hex string to uint - const char* pbegin = psz; - while (::HexDigit(*psz) != -1) - psz++; - psz--; - unsigned char* p1 = (unsigned char*)pn; - unsigned char* pend = p1 + WIDTH * 4; - while (psz >= pbegin && p1 < pend) { - *p1 = ::HexDigit(*psz--); - if (psz >= pbegin) { - *p1 |= ((unsigned char)::HexDigit(*psz--) << 4); - p1++; - } - } + *this = UintToArith256(uint256S(psz)); } template @@ -218,7 +184,6 @@ unsigned int base_uint::bits() const // Explicit instantiations for base_uint<256> template base_uint<256>::base_uint(const std::string&); -template base_uint<256>::base_uint(const std::vector&); template base_uint<256>& base_uint<256>::operator<<=(unsigned int); template base_uint<256>& base_uint<256>::operator>>=(unsigned int); template base_uint<256>& base_uint<256>::operator*=(uint32_t b32); -- cgit v1.2.3