src/hash.cpp

   1 // Copyright (c) 2013-2016 The Bitcoin Core developers
   2 // Distributed under the MIT software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #include "hash.h"
   6 #include "crypto/common.h"
   7 #include "crypto/hmac_sha512.h"
   8 #include "pubkey.h"
   9
  10
  11 inline uint32_t ROTL32(uint32_t x, int8_t r)
  12 {
  13     return (x << r) | (x >> (32 - r));
  14 }
  15
  16 unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char>& vDataToHash)
  17 {
  18     // The following is MurmurHash3 (x86_32), see http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
  19     uint32_t h1 = nHashSeed;
  20     const uint32_t c1 = 0xcc9e2d51;
  21     const uint32_t c2 = 0x1b873593;
  22
  23     const int nblocks = vDataToHash.size() / 4;
  24
  25     //----------
  26     // body
  27     const uint8_t* blocks = vDataToHash.data();
  28
  29     for (int i = 0; i < nblocks; ++i) {
  30         uint32_t k1 = ReadLE32(blocks + i*4);
  31
  32         k1 *= c1;
  33         k1 = ROTL32(k1, 15);
  34         k1 *= c2;
  35
  36         h1 ^= k1;
  37         h1 = ROTL32(h1, 13);
  38         h1 = h1 * 5 + 0xe6546b64;
  39     }
  40
  41     //----------
  42     // tail
  43     const uint8_t* tail = vDataToHash.data() + nblocks * 4;
  44
  45     uint32_t k1 = 0;
  46
  47     switch (vDataToHash.size() & 3) {
  48         case 3:
  49             k1 ^= tail[2] << 16;
  50         case 2:
  51             k1 ^= tail[1] << 8;
  52         case 1:
  53             k1 ^= tail[0];
  54             k1 *= c1;
  55             k1 = ROTL32(k1, 15);
  56             k1 *= c2;
  57             h1 ^= k1;
  58     }
  59
  60     //----------
  61     // finalization
  62     h1 ^= vDataToHash.size();
  63     h1 ^= h1 >> 16;
  64     h1 *= 0x85ebca6b;
  65     h1 ^= h1 >> 13;
  66     h1 *= 0xc2b2ae35;
  67     h1 ^= h1 >> 16;
  68
  69     return h1;
  70 }
  71
  72 void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char header, const unsigned char data[32], unsigned char output[64])
  73 {
  74     unsigned char num[4];
  75     num[0] = (nChild >> 24) & 0xFF;
  76     num[1] = (nChild >> 16) & 0xFF;
  77     num[2] = (nChild >>  8) & 0xFF;
  78     num[3] = (nChild >>  0) & 0xFF;
  79     CHMAC_SHA512(chainCode.begin(), chainCode.size()).Write(&header, 1).Write(data, 32).Write(num, 4).Finalize(output);
  80 }
  81
  82 #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
  83
  84 #define SIPROUND do { \
  85     v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; \
  86     v0 = ROTL(v0, 32); \
  87     v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2; \
  88     v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0; \
  89     v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; \
  90     v2 = ROTL(v2, 32); \
  91 } while (0)
  92
  93 CSipHasher::CSipHasher(uint64_t k0, uint64_t k1)
  94 {
  95     v[0] = 0x736f6d6570736575ULL ^ k0;
  96     v[1] = 0x646f72616e646f6dULL ^ k1;
  97     v[2] = 0x6c7967656e657261ULL ^ k0;
  98     v[3] = 0x7465646279746573ULL ^ k1;
  99     count = 0;
 100     tmp = 0;
 101 }
 102
 103 CSipHasher& CSipHasher::Write(uint64_t data)
 104 {
 105     uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
 106
 107     assert(count % 8 == 0);
 108
 109     v3 ^= data;
 110     SIPROUND;
 111     SIPROUND;
 112     v0 ^= data;
 113
 114     v[0] = v0;
 115     v[1] = v1;
 116     v[2] = v2;
 117     v[3] = v3;
 118
 119     count += 8;
 120     return *this;
 121 }
 122
 123 CSipHasher& CSipHasher::Write(const unsigned char* data, size_t size)
 124 {
 125     uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
 126     uint64_t t = tmp;
 127     int c = count;
 128
 129     while (size--) {
 130         t |= ((uint64_t)(*(data++))) << (8 * (c % 8));
 131         c++;
 132         if ((c & 7) == 0) {
 133             v3 ^= t;
 134             SIPROUND;
 135             SIPROUND;
 136             v0 ^= t;
 137             t = 0;
 138         }
 139     }
 140
 141     v[0] = v0;
 142     v[1] = v1;
 143     v[2] = v2;
 144     v[3] = v3;
 145     count = c;
 146     tmp = t;
 147
 148     return *this;
 149 }
 150
 151 uint64_t CSipHasher::Finalize() const
 152 {
 153     uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
 154
 155     uint64_t t = tmp | (((uint64_t)count) << 56);
 156
 157     v3 ^= t;
 158     SIPROUND;
 159     SIPROUND;
 160     v0 ^= t;
 161     v2 ^= 0xFF;
 162     SIPROUND;
 163     SIPROUND;
 164     SIPROUND;
 165     SIPROUND;
 166     return v0 ^ v1 ^ v2 ^ v3;
 167 }
 168
 169 uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
 170 {
 171     /* Specialized implementation for efficiency */
 172     uint64_t d = val.GetUint64(0);
 173
 174     uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
 175     uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
 176     uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
 177     uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ d;
 178
 179     SIPROUND;
 180     SIPROUND;
 181     v0 ^= d;
 182     d = val.GetUint64(1);
 183     v3 ^= d;
 184     SIPROUND;
 185     SIPROUND;
 186     v0 ^= d;
 187     d = val.GetUint64(2);
 188     v3 ^= d;
 189     SIPROUND;
 190     SIPROUND;
 191     v0 ^= d;
 192     d = val.GetUint64(3);
 193     v3 ^= d;
 194     SIPROUND;
 195     SIPROUND;
 196     v0 ^= d;
 197     v3 ^= ((uint64_t)4) << 59;
 198     SIPROUND;
 199     SIPROUND;
 200     v0 ^= ((uint64_t)4) << 59;
 201     v2 ^= 0xFF;
 202     SIPROUND;
 203     SIPROUND;
 204     SIPROUND;
 205     SIPROUND;
 206     return v0 ^ v1 ^ v2 ^ v3;
 207 }
 208
 209 uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra)
 210 {
 211     /* Specialized implementation for efficiency */
 212     uint64_t d = val.GetUint64(0);
 213
 214     uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
 215     uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
 216     uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
 217     uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ d;
 218
 219     SIPROUND;
 220     SIPROUND;
 221     v0 ^= d;
 222     d = val.GetUint64(1);
 223     v3 ^= d;
 224     SIPROUND;
 225     SIPROUND;
 226     v0 ^= d;
 227     d = val.GetUint64(2);
 228     v3 ^= d;
 229     SIPROUND;
 230     SIPROUND;
 231     v0 ^= d;
 232     d = val.GetUint64(3);
 233     v3 ^= d;
 234     SIPROUND;
 235     SIPROUND;
 236     v0 ^= d;
 237     d = (((uint64_t)36) << 56) | extra;
 238     v3 ^= d;
 239     SIPROUND;
 240     SIPROUND;
 241     v0 ^= d;
 242     v2 ^= 0xFF;
 243     SIPROUND;
 244     SIPROUND;
 245     SIPROUND;
 246     SIPROUND;
 247     return v0 ^ v1 ^ v2 ^ v3;
 248 }