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