1
// Copyright © 2016 Stephan Brumme. All rights reserved, see http://create.stephan-brumme.com/disclaimer.html
2
// Copyright © 2017-2020 Trust Wallet.
3
//
4
// This file is part of Trust. The full Trust copyright notice, including
5
// terms governing use, modification, and redistribution, is contained in the
6
// file LICENSE at the root of the source code distribution tree.
7

8
#pragma once
9
#include <stdint.h> // for uint32_t and uint64_t
10

11
/// XXHash (64 bit), based on Yann Collet's descriptions, see http://cyan4973.github.io/xxHash/
12
/** How to use:
13
    uint64_t myseed = 0;
14
    XXHash64 myhash(myseed);
15
    myhash.add(pointerToSomeBytes,     numberOfBytes);
16
    myhash.add(pointerToSomeMoreBytes, numberOfMoreBytes); // call add() as often as you like to ...
17
    // and compute hash:
18
    uint64_t result = myhash.hash();
19

20
    // or all of the above in one single line:
21
    uint64_t result2 = XXHash64::hash(mypointer, numBytes, myseed);
22

23
    Note: my code is NOT endian-aware !
24
**/
25
class XXHash64
26
{
27
public:
28
  /// create new XXHash (64 bit)
29
  /** @param seed your seed value, even zero is a valid seed **/
30 1
  explicit XXHash64(uint64_t seed)
31
  {
32 1
    state[0] = seed + Prime1 + Prime2;
33 1
    state[1] = seed + Prime2;
34 1
    state[2] = seed;
35 1
    state[3] = seed - Prime1;
36 1
    buffer[0] = 0;
37 1
    bufferSize  = 0;
38 1
    totalLength = 0;
39
  }
40

41
  /// add a chunk of bytes
42
  /** @param  input  pointer to a continuous block of data
43
      @param  length number of bytes
44
      @return false if parameters are invalid / zero **/
45 1
  bool add(const void* input, uint64_t length)
46
  {
47
    // no data ?
48 1
    if (!input || length == 0)
49 1
      return false;
50

51 1
    totalLength += length;
52
    // byte-wise access
53 1
    const unsigned char* data = (const unsigned char*)input;
54

55
    // unprocessed old data plus new data still fit in temporary buffer ?
56 1
    if (bufferSize + length < MaxBufferSize)
57
    {
58
      // just add new data
59 1
      while (length-- > 0)
60 1
        buffer[bufferSize++] = *data++;
61 1
      return true;
62
    }
63

64
    // point beyond last byte
65 1
    const unsigned char* stop      = data + length;
66 1
    const unsigned char* stopBlock = stop - MaxBufferSize;
67

68
    // some data left from previous update ?
69 1
    if (bufferSize > 0)
70
    {
71
      // make sure temporary buffer is full (16 bytes)
72 0
      while (bufferSize < MaxBufferSize)
73 0
        buffer[bufferSize++] = *data++;
74

75
      // process these 32 bytes (4x8)
76 0
      process(buffer, state[0], state[1], state[2], state[3]);
77
    }
78

79
    // copying state to local variables helps optimizer A LOT
80 1
    uint64_t s0 = state[0], s1 = state[1], s2 = state[2], s3 = state[3];
81
    // 32 bytes at once
82 1
    while (data <= stopBlock)
83
    {
84
      // local variables s0..s3 instead of state[0]..state[3] are much faster
85 1
      process(data, s0, s1, s2, s3);
86 1
      data += 32;
87
    }
88
    // copy back
89 1
    state[0] = s0; state[1] = s1; state[2] = s2; state[3] = s3;
90

91
    // copy remainder to temporary buffer
92 1
    bufferSize = uint32_t(stop - data);
93 1
    for (unsigned int i = 0; i < bufferSize; i++)
94 1
      buffer[i] = data[i];
95

96
    // done
97 1
    return true;
98
  }
99

100
  /// get current hash
101
  /** @return 64 bit XXHash **/
102 1
  uint64_t hash() const
103
  {
104
    // fold 256 bit state into one single 64 bit value
105
    uint64_t result;
106 1
    if (totalLength >= MaxBufferSize)
107
    {
108 1
      result = rotateLeft(state[0],  1) +
109 1
               rotateLeft(state[1],  7) +
110 1
               rotateLeft(state[2], 12) +
111 1
               rotateLeft(state[3], 18);
112 1
      result = (result ^ processSingle(0, state[0])) * Prime1 + Prime4;
113 1
      result = (result ^ processSingle(0, state[1])) * Prime1 + Prime4;
114 1
      result = (result ^ processSingle(0, state[2])) * Prime1 + Prime4;
115 1
      result = (result ^ processSingle(0, state[3])) * Prime1 + Prime4;
116
    }
117
    else
118
    {
119
      // internal state wasn't set in add(), therefore original seed is still stored in state2
120 1
      result = state[2] + Prime5;
121
    }
122

123 1
    result += totalLength;
124

125
    // process remaining bytes in temporary buffer
126 1
    const unsigned char* data = buffer;
127
    // point beyond last byte
128 1
    const unsigned char* stop = data + bufferSize;
129

130
    // at least 8 bytes left ? => eat 8 bytes per step
131 1
    for (; data + 8 <= stop; data += 8)
132 1
      result = rotateLeft(result ^ processSingle(0, *(uint64_t*)data), 27) * Prime1 + Prime4;
133

134
    // 4 bytes left ? => eat those
135 1
    if (data + 4 <= stop)
136
    {
137 1
      result = rotateLeft(result ^ (*(uint32_t*)data) * Prime1,   23) * Prime2 + Prime3;
138 1
      data  += 4;
139
    }
140

141
    // take care of remaining 0..3 bytes, eat 1 byte per step
142 1
    while (data != stop)
143 1
      result = rotateLeft(result ^ (*data++) * Prime5,            11) * Prime1;
144

145
    // mix bits
146 1
    result ^= result >> 33;
147 1
    result *= Prime2;
148 1
    result ^= result >> 29;
149 1
    result *= Prime3;
150 1
    result ^= result >> 32;
151 1
    return result;
152
  }
153

154

155
  /// combine constructor, add() and hash() in one static function (C style)
156
  /** @param  input  pointer to a continuous block of data
157
      @param  length number of bytes
158
      @param  seed your seed value, e.g. zero is a valid seed
159
      @return 64 bit XXHash **/
160 1
  static uint64_t hash(const void* input, uint64_t length, uint64_t seed)
161
  {
162 1
    XXHash64 hasher(seed);
163 1
    hasher.add(input, length);
164 1
      return hasher.hash();
165
  }
166

167
private:
168
  /// magic constants :-)
169
  static const uint64_t Prime1 = 11400714785074694791ULL;
170
  static const uint64_t Prime2 = 14029467366897019727ULL;
171
  static const uint64_t Prime3 =  1609587929392839161ULL;
172
  static const uint64_t Prime4 =  9650029242287828579ULL;
173
  static const uint64_t Prime5 =  2870177450012600261ULL;
174

175
  /// temporarily store up to 31 bytes between multiple add() calls
176
  static const uint64_t MaxBufferSize = 31+1;
177

178
  uint64_t      state[4];
179
  unsigned char buffer[MaxBufferSize];
180
  uint32_t      bufferSize;
181
  uint64_t      totalLength;
182

183
  /// rotate bits, should compile to a single CPU instruction (ROL)
184 1
  static inline uint64_t rotateLeft(uint64_t x, unsigned char bits)
185
  {
186 1
    return (x << bits) | (x >> (64 - bits));
187
  }
188

189
  /// process a single 64 bit value
190 1
  static inline uint64_t processSingle(uint64_t previous, uint64_t input)
191
  {
192 1
    return rotateLeft(previous + input * Prime2, 31) * Prime1;
193
  }
194

195
  /// process a block of 4x4 bytes, this is the main part of the XXHash32 algorithm
196 1
  static inline void process(const void* data, uint64_t& state0, uint64_t& state1, uint64_t& state2, uint64_t& state3)
197
  {
198 1
    const uint64_t* block = (const uint64_t*) data;
199 1
    state0 = processSingle(state0, block[0]);
200 1
    state1 = processSingle(state1, block[1]);
201 1
    state2 = processSingle(state2, block[2]);
202 1
    state3 = processSingle(state3, block[3]);
203
  }
204
};

Read our documentation on viewing source code .

Loading