1 /** xxHash is an extremely fast non-cryptographic hash algorithm, working at
2 	speeds close to RAM limits. It is proposed in two flavors, 32 and 64 bits.
3 
4 	Original implementation by Stephan Brumme.
5 
6 	See_Also: http://cyan4973.github.io/xxHash/
7 	See_Also: http://create.stephan-brumme.com/xxhash/
8 
9 	TODO: merge into xxhash-d
10 */
11 module nxt.xxhash64;
12 
13 pure nothrow @safe @nogc:
14 
15 /** xxHash-64, based on Yann Collet's descriptions
16 
17 	How to use:
18 
19 		ulong myseed = 0;
20 		XXHash64 myhash(myseed);
21 		myhash.put(pointerToSomeBytes,	 numberOfBytes);
22 		myhash.put(pointerToSomeMoreBytes, numberOfMoreBytes); // call put() as often as you like to ...
23 
24 	and compute hash:
25 
26 		ulong result = myhash.hash();
27 
28 	or all of the above in one single line:
29 
30 		ulong result2 = XXHash64::hashOf(mypointer, numBytes, myseed);
31 
32 	See_Also: http://cyan4973.github.io/xxHash/
33 	See_Also: http://create.stephan-brumme.com/xxhash/
34 
35 	TODO: make endian-aware
36 **/
37 struct XXHash64
38 {
39 	pure nothrow @safe @nogc:
40 
41 	/**
42 	 * Constructs XXHash64 with `seed`.
43 	 */
44 	this(ulong seed)
45 	{
46 		_seed = seed;
47 	}
48 
49 	/** (Re)initialize.
50 	 */
51 	void start()
52 	{
53 		_state[0] = _seed + prime1 + prime2;
54 		_state[1] = _seed + prime2;
55 		_state[2] = _seed;
56 		_state[3] = _seed - prime1;
57 		_bufferSize  = 0;
58 		_totalLength = 0;
59 	}
60 
61 	/** Use this to feed the hash with data.
62 
63 		Also implements the $(XREF range, OutputRange) interface for $(D ubyte) and $(D const(ubyte)[]).
64 	 */
65 	void put(scope const(ubyte)[] data...) @trusted
66 	{
67 		auto ptr = data.ptr;
68 		auto length = data.length;
69 
70 		_totalLength += length;
71 
72 		// unprocessed old data plus new data still fit in temporary buffer ?
73 		if (_bufferSize + length < bufferMaxSize)
74 		{
75 			// just add new data
76 			while (length-- > 0)
77 				_buffer[_bufferSize++] = *ptr++;
78 			return;
79 		}
80 
81 		// point beyond last byte
82 		const(ubyte)* end	  = ptr + length;
83 		const(ubyte)* endBlock = end - bufferMaxSize;
84 
85 		// some data left from previous update ?
86 		if (_bufferSize > 0)
87 		{
88 			// make sure temporary buffer is full (16 bytes)
89 			while (_bufferSize < bufferMaxSize)
90 				_buffer[_bufferSize++] = *ptr++;
91 
92 			// process these 32 bytes (4x8)
93 			process(_buffer.ptr, _state[0], _state[1], _state[2], _state[3]);
94 		}
95 
96 		// copying _state to local variables helps optimizer A LOT
97 		ulong s0 = _state[0], s1 = _state[1], s2 = _state[2], s3 = _state[3];
98 		// 32 bytes at once
99 		while (ptr <= endBlock)
100 		{
101 			// local variables s0..s3 instead of _state[0].._state[3] are much faster
102 			process(ptr, s0, s1, s2, s3);
103 			ptr += 32;
104 		}
105 		// copy back
106 		_state[0] = s0; _state[1] = s1; _state[2] = s2; _state[3] = s3;
107 
108 		// copy remainder to temporary buffer
109 		_bufferSize = end - ptr;
110 		foreach (const i; 0 .. _bufferSize)
111 			_buffer[i] = ptr[i];
112 	}
113 
114 	/** Returns: the finished XXHash64 hash.
115 		This also calls $(LREF start) to reset the internal _state.
116 	*/
117 	ulong finishUlong() @trusted
118 	{
119 		// fold 256 bit _state into one single 64 bit value
120 		ulong result;
121 		if (_totalLength >= bufferMaxSize)
122 		{
123 			result = (rol(_state[0],  1) +
124 					  rol(_state[1],  7) +
125 					  rol(_state[2], 12) +
126 					  rol(_state[3], 18));
127 			result = (result ^ processSingle(0, _state[0])) * prime1 + prime4;
128 			result = (result ^ processSingle(0, _state[1])) * prime1 + prime4;
129 			result = (result ^ processSingle(0, _state[2])) * prime1 + prime4;
130 			result = (result ^ processSingle(0, _state[3])) * prime1 + prime4;
131 		}
132 		else
133 			// internal _state wasn't set in put(), therefore original seed is still stored in state2
134 			result = _state[2] + prime5;
135 
136 		result += _totalLength;
137 
138 		// process remaining bytes in temporary buffer
139 		const(ubyte)* data = _buffer.ptr;
140 
141 		// point beyond last byte
142 		const(ubyte)* end = data + _bufferSize;
143 
144 		// at least 8 bytes left ? => eat 8 bytes per step
145 		for (; data + 8 <= end; data += 8)
146 			result = rol(result ^ processSingle(0, *cast(ulong*)data), 27) * prime1 + prime4;
147 
148 		// 4 bytes left ? => eat those
149 		if (data + 4 <= end)
150 		{
151 			result = rol(result ^ (*cast(uint*)data) * prime1, 23) * prime2 + prime3;
152 			data += 4;
153 		}
154 
155 		// take care of remaining 0..3 bytes, eat 1 byte per step
156 		while (data != end)
157 			result = rol(result ^ (*data++) * prime5, 11) * prime1;
158 
159 		// mix bits
160 		result ^= result >> 33;
161 		result *= prime2;
162 		result ^= result >> 29;
163 		result *= prime3;
164 		result ^= result >> 32;
165 
166 		start();
167 
168 		return result;
169 	}
170 
171 	/** Returns: the finished XXHash64 hash.
172 		This also calls $(LREF start) to reset the internal _state.
173 	*/
174 	ubyte[8] finish() @trusted
175 	{
176 		import std.bitmanip : swapEndian;
177 		_result = swapEndian(finishUlong());
178 		return (cast(ubyte*)&_result)[0 .. typeof(return).sizeof];
179 	}
180 
181 	ulong get()
182 	{
183 		return _result;
184 	}
185 
186 private:
187 	/// magic constants
188 	enum ulong prime1 = 11400714785074694791UL;
189 	enum ulong prime2 = 14029467366897019727UL;
190 	enum ulong prime3 =  1609587929392839161UL;
191 	enum ulong prime4 =  9650029242287828579UL;
192 	enum ulong prime5 =  2870177450012600261UL;
193 
194 	/// temporarily store up to 31 bytes between multiple put() calls
195 	enum bufferMaxSize = 31+1;
196 
197 	ulong[4] _state;
198 	ulong _bufferSize;
199 	ulong _totalLength;
200 	ulong _seed;
201 	ubyte[bufferMaxSize] _buffer;
202 	ulong _result;
203 
204 	import core.bitop : rol;
205 	/// rotate bits, should compile to a single CPU instruction (ROL)
206 	version (none)
207 	static ulong rol(ulong x, ubyte bits)
208 	{
209 		return (x << bits) | (x >> (64 - bits));
210 	}
211 
212 	/// process a single 64 bit value
213 	static ulong processSingle(ulong previous, ulong data)
214 	{
215 		return rol(previous + data * prime2, 31) * prime1;
216 	}
217 
218 	/// process a block of 4x4 bytes, this is the main part of the XXHash32 algorithm
219 	static void process(const(ubyte)* data,
220 						out ulong state0,
221 						out ulong state1,
222 						out ulong state2,
223 						out ulong state3) @trusted
224 	{
225 		const(ulong)* block = cast(const(ulong)*)data;
226 		state0 = processSingle(state0, block[0]);
227 		state1 = processSingle(state1, block[1]);
228 		state2 = processSingle(state2, block[2]);
229 		state3 = processSingle(state3, block[3]);
230 	}
231 }
232 
233 /** Compute xxHash-64 of input `data`, with optional seed `seed`.
234  */
235 ulong xxhash64Of(in ubyte[] data, ulong seed = 0)
236 {
237 	auto xh = XXHash64(seed);
238 	xh.start();
239 	xh.put(data);
240 	return xh.finishUlong();
241 }
242 
243 /** Compute xxHash-64 of input string `data`, with optional seed `seed`.
244  */
245 ulong xxhash64Of(in char[] data, ulong seed = 0) @trusted
246 {
247 	return xxhash64Of(cast(ubyte[])data, seed);
248 }
249 
250 /// test simple `xxhash64Of`
251 unittest {
252 	assert(xxhash64Of("") == 17241709254077376921UL);
253 
254 	ubyte[8] x = [1, 2, 3, 4, 5, 6, 7, 8];
255 	assert(xxhash64Of(x[]) == 9316896406413536788UL);
256 
257 	// tests copied from https://pypi.python.org/pypi/xxhash/0.6.0
258 	assert(xxhash64Of(`xxhash`) == 3665147885093898016UL);
259 	assert(xxhash64Of(`xxhash`, 20141025) == 13067679811253438005UL);
260 }
261 
262 version (unittest)
263 {
264 	import std.digest : hexDigest, isDigest;
265 	static assert(isDigest!(XXHash64));
266 }
267 
268 /// `std.digest` conformance
269 unittest {
270 	import std.digest;
271 	assert(hexDigest!XXHash64(`xxhash`) == `32DD38952C4BC720`);
272 }