src/hash.cpp

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