src/arith_uint256.cpp

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