src/uint256.cpp

   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
   8 #include "utilstrencodings.h"
   9
  10 #include <stdio.h>
  11 #include <string.h>
  12
  13 template <unsigned int BITS>
  14 base_uint<BITS>::base_uint(const std::string& str)
  15 {
  16     SetHex(str);
  17 }
  18
  19 template <unsigned int BITS>
  20 base_uint<BITS>::base_uint(const std::vector<unsigned char>& vch)
  21 {
  22     if (vch.size() != sizeof(pn))
  23         throw uint_error("Converting vector of wrong size to base_uint");
  24     memcpy(pn, &vch[0], sizeof(pn));
  25 }
  26
  27 template <unsigned int BITS>
  28 base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
  29 {
  30     base_uint<BITS> a(*this);
  31     for (int i = 0; i < WIDTH; i++)
  32         pn[i] = 0;
  33     int k = shift / 32;
  34     shift = shift % 32;
  35     for (int i = 0; i < WIDTH; i++) {
  36         if (i + k + 1 < WIDTH && shift != 0)
  37             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
  38         if (i + k < WIDTH)
  39             pn[i + k] |= (a.pn[i] << shift);
  40     }
  41     return *this;
  42 }
  43
  44 template <unsigned int BITS>
  45 base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
  46 {
  47     base_uint<BITS> a(*this);
  48     for (int i = 0; i < WIDTH; i++)
  49         pn[i] = 0;
  50     int k = shift / 32;
  51     shift = shift % 32;
  52     for (int i = 0; i < WIDTH; i++) {
  53         if (i - k - 1 >= 0 && shift != 0)
  54             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
  55         if (i - k >= 0)
  56             pn[i - k] |= (a.pn[i] >> shift);
  57     }
  58     return *this;
  59 }
  60
  61 template <unsigned int BITS>
  62 base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
  63 {
  64     uint64_t carry = 0;
  65     for (int i = 0; i < WIDTH; i++) {
  66         uint64_t n = carry + (uint64_t)b32 * pn[i];
  67         pn[i] = n & 0xffffffff;
  68         carry = n >> 32;
  69     }
  70     return *this;
  71 }
  72
  73 template <unsigned int BITS>
  74 base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
  75 {
  76     base_uint<BITS> a = *this;
  77     *this = 0;
  78     for (int j = 0; j < WIDTH; j++) {
  79         uint64_t carry = 0;
  80         for (int i = 0; i + j < WIDTH; i++) {
  81             uint64_t n = carry + pn[i + j] + (uint64_t)a.pn[j] * b.pn[i];
  82             pn[i + j] = n & 0xffffffff;
  83             carry = n >> 32;
  84         }
  85     }
  86     return *this;
  87 }
  88
  89 template <unsigned int BITS>
  90 base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
  91 {
  92     base_uint<BITS> div = b;     // make a copy, so we can shift.
  93     base_uint<BITS> num = *this; // make a copy, so we can subtract.
  94     *this = 0;                   // the quotient.
  95     int num_bits = num.bits();
  96     int div_bits = div.bits();
  97     if (div_bits == 0)
  98         throw uint_error("Division by zero");
  99     if (div_bits > num_bits) // the result is certainly 0.
 100         return *this;
 101     int shift = num_bits - div_bits;
 102     div <<= shift; // shift so that div and nun align.
 103     while (shift >= 0) {
 104         if (num >= div) {
 105             num -= div;
 106             pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
 107         }
 108         div >>= 1; // shift back.
 109         shift--;
 110     }
 111     // num now contains the remainder of the division.
 112     return *this;
 113 }
 114
 115 template <unsigned int BITS>
 116 int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
 117 {
 118     for (int i = WIDTH - 1; i >= 0; i--) {
 119         if (pn[i] < b.pn[i])
 120             return -1;
 121         if (pn[i] > b.pn[i])
 122             return 1;
 123     }
 124     return 0;
 125 }
 126
 127 template <unsigned int BITS>
 128 bool base_uint<BITS>::EqualTo(uint64_t b) const
 129 {
 130     for (int i = WIDTH - 1; i >= 2; i--) {
 131         if (pn[i])
 132             return false;
 133     }
 134     if (pn[1] != (b >> 32))
 135         return false;
 136     if (pn[0] != (b & 0xfffffffful))
 137         return false;
 138     return true;
 139 }
 140
 141 template <unsigned int BITS>
 142 double base_uint<BITS>::getdouble() const
 143 {
 144     double ret = 0.0;
 145     double fact = 1.0;
 146     for (int i = 0; i < WIDTH; i++) {
 147         ret += fact * pn[i];
 148         fact *= 4294967296.0;
 149     }
 150     return ret;
 151 }
 152
 153 template <unsigned int BITS>
 154 std::string base_uint<BITS>::GetHex() const
 155 {
 156     char psz[sizeof(pn) * 2 + 1];
 157     for (unsigned int i = 0; i < sizeof(pn); i++)
 158         sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
 159     return std::string(psz, psz + sizeof(pn) * 2);
 160 }
 161
 162 template <unsigned int BITS>
 163 void base_uint<BITS>::SetHex(const char* psz)
 164 {
 165     memset(pn, 0, sizeof(pn));
 166
 167     // skip leading spaces
 168     while (isspace(*psz))
 169         psz++;
 170
 171     // skip 0x
 172     if (psz[0] == '0' && tolower(psz[1]) == 'x')
 173         psz += 2;
 174
 175     // hex string to uint
 176     const char* pbegin = psz;
 177     while (::HexDigit(*psz) != -1)
 178         psz++;
 179     psz--;
 180     unsigned char* p1 = (unsigned char*)pn;
 181     unsigned char* pend = p1 + WIDTH * 4;
 182     while (psz >= pbegin && p1 < pend) {
 183         *p1 = ::HexDigit(*psz--);
 184         if (psz >= pbegin) {
 185             *p1 |= ((unsigned char)::HexDigit(*psz--) << 4);
 186             p1++;
 187         }
 188     }
 189 }
 190
 191 template <unsigned int BITS>
 192 void base_uint<BITS>::SetHex(const std::string& str)
 193 {
 194     SetHex(str.c_str());
 195 }
 196
 197 template <unsigned int BITS>
 198 std::string base_uint<BITS>::ToString() const
 199 {
 200     return (GetHex());
 201 }
 202
 203 template <unsigned int BITS>
 204 unsigned int base_uint<BITS>::bits() const
 205 {
 206     for (int pos = WIDTH - 1; pos >= 0; pos--) {
 207         if (pn[pos]) {
 208             for (int bits = 31; bits > 0; bits--) {
 209                 if (pn[pos] & 1 << bits)
 210                     return 32 * pos + bits + 1;
 211             }
 212             return 32 * pos + 1;
 213         }
 214     }
 215     return 0;
 216 }
 217
 218 // Explicit instantiations for base_uint<160>
 219 template base_uint<160>::base_uint(const std::string&);
 220 template base_uint<160>::base_uint(const std::vector<unsigned char>&);
 221 template base_uint<160>& base_uint<160>::operator<<=(unsigned int);
 222 template base_uint<160>& base_uint<160>::operator>>=(unsigned int);
 223 template base_uint<160>& base_uint<160>::operator*=(uint32_t b32);
 224 template base_uint<160>& base_uint<160>::operator*=(const base_uint<160>& b);
 225 template base_uint<160>& base_uint<160>::operator/=(const base_uint<160>& b);
 226 template int base_uint<160>::CompareTo(const base_uint<160>&) const;
 227 template bool base_uint<160>::EqualTo(uint64_t) const;
 228 template double base_uint<160>::getdouble() const;
 229 template std::string base_uint<160>::GetHex() const;
 230 template std::string base_uint<160>::ToString() const;
 231 template void base_uint<160>::SetHex(const char*);
 232 template void base_uint<160>::SetHex(const std::string&);
 233 template unsigned int base_uint<160>::bits() const;
 234
 235 // Explicit instantiations for base_uint<256>
 236 template base_uint<256>::base_uint(const std::string&);
 237 template base_uint<256>::base_uint(const std::vector<unsigned char>&);
 238 template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
 239 template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
 240 template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
 241 template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b);
 242 template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b);
 243 template int base_uint<256>::CompareTo(const base_uint<256>&) const;
 244 template bool base_uint<256>::EqualTo(uint64_t) const;
 245 template double base_uint<256>::getdouble() const;
 246 template std::string base_uint<256>::GetHex() const;
 247 template std::string base_uint<256>::ToString() const;
 248 template void base_uint<256>::SetHex(const char*);
 249 template void base_uint<256>::SetHex(const std::string&);
 250 template unsigned int base_uint<256>::bits() const;
 251
 252 // This implementation directly uses shifts instead of going
 253 // through an intermediate MPI representation.
 254 uint256& uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
 255 {
 256     int nSize = nCompact >> 24;
 257     uint32_t nWord = nCompact & 0x007fffff;
 258     if (nSize <= 3) {
 259         nWord >>= 8 * (3 - nSize);
 260         *this = nWord;
 261     } else {
 262         *this = nWord;
 263         *this <<= 8 * (nSize - 3);
 264     }
 265     if (pfNegative)
 266         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
 267     if (pfOverflow)
 268         *pfOverflow = nWord != 0 && ((nSize > 34) ||
 269                                      (nWord > 0xff && nSize > 33) ||
 270                                      (nWord > 0xffff && nSize > 32));
 271     return *this;
 272 }
 273
 274 uint32_t uint256::GetCompact(bool fNegative) const
 275 {
 276     int nSize = (bits() + 7) / 8;
 277     uint32_t nCompact = 0;
 278     if (nSize <= 3) {
 279         nCompact = GetLow64() << 8 * (3 - nSize);
 280     } else {
 281         uint256 bn = *this >> 8 * (nSize - 3);
 282         nCompact = bn.GetLow64();
 283     }
 284     // The 0x00800000 bit denotes the sign.
 285     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
 286     if (nCompact & 0x00800000) {
 287         nCompact >>= 8;
 288         nSize++;
 289     }
 290     assert((nCompact & ~0x007fffff) == 0);
 291     assert(nSize < 256);
 292     nCompact |= nSize << 24;
 293     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
 294     return nCompact;
 295 }
 296
 297 static void inline HashMix(uint32_t& a, uint32_t& b, uint32_t& c)
 298 {
 299     // Taken from lookup3, by Bob Jenkins.
 300     a -= c;
 301     a ^= ((c << 4) | (c >> 28));
 302     c += b;
 303     b -= a;
 304     b ^= ((a << 6) | (a >> 26));
 305     a += c;
 306     c -= b;
 307     c ^= ((b << 8) | (b >> 24));
 308     b += a;
 309     a -= c;
 310     a ^= ((c << 16) | (c >> 16));
 311     c += b;
 312     b -= a;
 313     b ^= ((a << 19) | (a >> 13));
 314     a += c;
 315     c -= b;
 316     c ^= ((b << 4) | (b >> 28));
 317     b += a;
 318 }
 319
 320 static void inline HashFinal(uint32_t& a, uint32_t& b, uint32_t& c)
 321 {
 322     // Taken from lookup3, by Bob Jenkins.
 323     c ^= b;
 324     c -= ((b << 14) | (b >> 18));
 325     a ^= c;
 326     a -= ((c << 11) | (c >> 21));
 327     b ^= a;
 328     b -= ((a << 25) | (a >> 7));
 329     c ^= b;
 330     c -= ((b << 16) | (b >> 16));
 331     a ^= c;
 332     a -= ((c << 4) | (c >> 28));
 333     b ^= a;
 334     b -= ((a << 14) | (a >> 18));
 335     c ^= b;
 336     c -= ((b << 24) | (b >> 8));
 337 }
 338
 339 uint64_t uint256::GetHash(const uint256& salt) const
 340 {
 341     uint32_t a, b, c;
 342     a = b = c = 0xdeadbeef + (WIDTH << 2);
 343
 344     a += pn[0] ^ salt.pn[0];
 345     b += pn[1] ^ salt.pn[1];
 346     c += pn[2] ^ salt.pn[2];
 347     HashMix(a, b, c);
 348     a += pn[3] ^ salt.pn[3];
 349     b += pn[4] ^ salt.pn[4];
 350     c += pn[5] ^ salt.pn[5];
 351     HashMix(a, b, c);
 352     a += pn[6] ^ salt.pn[6];
 353     b += pn[7] ^ salt.pn[7];
 354     HashFinal(a, b, c);
 355
 356     return ((((uint64_t)b) << 32) | c);
 357 }