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 #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 }
 293
 294 static void inline HashMix(uint32_t& a, uint32_t& b, uint32_t& c)
 295 {
 296     // Taken from lookup3, by Bob Jenkins.
 297     a -= c; a ^= ((c <<  4) | (c >> 28)); c += b;
 298     b -= a; b ^= ((a <<  6) | (a >> 26)); a += c;
 299     c -= b; c ^= ((b <<  8) | (b >> 24)); b += a;
 300     a -= c; a ^= ((c << 16) | (c >> 16)); c += b;
 301     b -= a; b ^= ((a << 19) | (a >> 13)); a += c;
 302     c -= b; c ^= ((b <<  4) | (b >> 28)); b += a;
 303 }
 304
 305 static void inline HashFinal(uint32_t& a, uint32_t& b, uint32_t& c)
 306 {
 307     // Taken from lookup3, by Bob Jenkins.
 308     c ^= b; c -= ((b << 14) | (b >> 18));
 309     a ^= c; a -= ((c << 11) | (c >> 21));
 310     b ^= a; b -= ((a << 25) | (a >>  7));
 311     c ^= b; c -= ((b << 16) | (b >> 16));
 312     a ^= c; a -= ((c <<  4) | (c >> 28));
 313     b ^= a; b -= ((a << 14) | (a >> 18));
 314     c ^= b; c -= ((b << 24) | (b >>  8));
 315 }
 316
 317 uint64_t uint256::GetHash(const uint256 &salt) const
 318 {
 319     uint32_t a, b, c;
 320     a = b = c = 0xdeadbeef + (WIDTH << 2);
 321
 322     a += pn[0] ^ salt.pn[0];
 323     b += pn[1] ^ salt.pn[1];
 324     c += pn[2] ^ salt.pn[2];
 325     HashMix(a, b, c);
 326     a += pn[3] ^ salt.pn[3];
 327     b += pn[4] ^ salt.pn[4];
 328     c += pn[5] ^ salt.pn[5];
 329     HashMix(a, b, c);
 330     a += pn[6] ^ salt.pn[6];
 331     b += pn[7] ^ salt.pn[7];
 332     HashFinal(a, b, c);
 333
 334     return ((((uint64_t)b) << 32) | c);
 335 }