src/arith_uint256.cpp

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