//// SpookyHash - 128-bit noncryptographic hash function//// Written in 2012 by Bob Jenkins//// Converted to C in 2015 by Joergen Ibsen//// To the extent possible under law, the author(s) have dedicated all// copyright and related and neighboring rights to this software to the// public domain worldwide. This software is distributed without any// warranty. <http://creativecommons.org/publicdomain/zero/1.0/>//// Original comment from SpookyV2.cpp by Bob Jenkins://// Spooky Hash// A 128-bit noncryptographic hash, for checksums and table lookup// By Bob Jenkins.  Public domain.//   Oct 31 2010: published framework, disclaimer ShortHash isn't right//   Nov 7 2010: disabled ShortHash//   Oct 31 2011: replace End, ShortMix, ShortEnd, enable ShortHash again//   April 10 2012: buffer overflow on platforms without unaligned reads//   July 12 2012: was passing out variables in final to in/out in short//   July 30 2012: I reintroduced the buffer overflow//   August 5 2012: SpookyV2: d = should be d += in short hash, and remove extra mix from long hash #include "platform.h"#include "spooky.h" #if defined(MEM_UNALIGNED_ACCESS)#define ALLOW_UNALIGNED_READS 1#else#define ALLOW_UNALIGNED_READS 0#endif //// SC_CONST: a constant which://  - is not zero//  - is odd//  - is a not-very-regular mix of 1's and 0's//  - does not need any other special mathematical properties//#define SC_CONST 0xDEADBEEFDEADBEEFULL #define ROTL64(x, k) (((x) << (k)) | ((x) >> (64 - (k)))) #ifdef _MSC_VER# define restrict __restrict# define inline __forceinline#endif #define spooky_is_aligned(p, size) ((uintptr)(p) % (size) == 0) //// Read u64int in little-endian order.//sl_purefnstatic inline u64intspooky_read_le64(const u64int *s){#if BYTE_ORDER == LITTLE_ENDIAN && defined(MEM_UNALIGNED_ACCESS)	return *s;#else	const u8int *p = (const u8int *) s;	return (u64int) p[0]	    | ((u64int) p[1] << 8)	    | ((u64int) p[2] << 16)	    | ((u64int) p[3] << 24)	    | ((u64int) p[4] << 32)	    | ((u64int) p[5] << 40)	    | ((u64int) p[6] << 48)	    | ((u64int) p[7] << 56);#endif} //// This is used if the input is 96 bytes long or longer.//// The internal state is fully overwritten every 96 bytes.// Every input bit appears to cause at least 128 bits of entropy// before 96 other bytes are combined, when run forward or backward//   For every input bit,//   Two inputs differing in just that input bit//   Where "differ" means xor or subtraction//   And the base value is random//   When run forward or backwards one Mix// I tried 3 pairs of each; they all differed by at least 212 bits.//static inline voidspooky_mix(const u64int *restrict data, u64int *restrict s){	s[0] += spooky_read_le64(&data[0]);          s[2] ^= s[10];	s[11] ^= s[0];   s[0] = ROTL64(s[0], 11);    s[11] += s[1];	s[1] += spooky_read_le64(&data[1]);          s[3] ^= s[11];	s[0] ^= s[1];    s[1] = ROTL64(s[1], 32);    s[0] += s[2];	s[2] += spooky_read_le64(&data[2]);          s[4] ^= s[0];	s[1] ^= s[2];    s[2] = ROTL64(s[2], 43);    s[1] += s[3];	s[3] += spooky_read_le64(&data[3]);          s[5] ^= s[1];	s[2] ^= s[3];    s[3] = ROTL64(s[3], 31);    s[2] += s[4];	s[4] += spooky_read_le64(&data[4]);          s[6] ^= s[2];	s[3] ^= s[4];    s[4] = ROTL64(s[4], 17);    s[3] += s[5];	s[5] += spooky_read_le64(&data[5]);          s[7] ^= s[3];	s[4] ^= s[5];    s[5] = ROTL64(s[5], 28);    s[4] += s[6];	s[6] += spooky_read_le64(&data[6]);          s[8] ^= s[4];	s[5] ^= s[6];    s[6] = ROTL64(s[6], 39);    s[5] += s[7];	s[7] += spooky_read_le64(&data[7]);          s[9] ^= s[5];	s[6] ^= s[7];    s[7] = ROTL64(s[7], 57);    s[6] += s[8];	s[8] += spooky_read_le64(&data[8]);          s[10] ^= s[6];	s[7] ^= s[8];    s[8] = ROTL64(s[8], 55);    s[7] += s[9];	s[9] += spooky_read_le64(&data[9]);          s[11] ^= s[7];	s[8] ^= s[9];    s[9] = ROTL64(s[9], 54);    s[8] += s[10];	s[10] += spooky_read_le64(&data[10]);        s[0] ^= s[8];	s[9] ^= s[10];   s[10] = ROTL64(s[10], 22);  s[9] += s[11];	s[11] += spooky_read_le64(&data[11]);        s[1] ^= s[9];	s[10] ^= s[11];  s[11] = ROTL64(s[11], 46);  s[10] += s[0];} //// Mix all 12 inputs together so that h0, h1 are a hash of them all.//// For two inputs differing in just the input bits// Where "differ" means xor or subtraction// And the base value is random, or a counting value starting at that bit// The final result will have each bit of h0, h1 flip// For every input bit,// with probability 50 +- .3%// For every pair of input bits,// with probability 50 +- 3%//// This does not rely on the last Mix() call having already mixed some.// Two iterations was almost good enough for a 64-bit result, but a// 128-bit result is reported, so End() does three iterations.//static inline voidspooky_end_partial(u64int *h){	h[11] += h[1];  h[2] ^= h[11];  h[1] = ROTL64(h[1], 44);	h[0] += h[2];   h[3] ^= h[0];   h[2] = ROTL64(h[2], 15);	h[1] += h[3];   h[4] ^= h[1];   h[3] = ROTL64(h[3], 34);	h[2] += h[4];   h[5] ^= h[2];   h[4] = ROTL64(h[4], 21);	h[3] += h[5];   h[6] ^= h[3];   h[5] = ROTL64(h[5], 38);	h[4] += h[6];   h[7] ^= h[4];   h[6] = ROTL64(h[6], 33);	h[5] += h[7];   h[8] ^= h[5];   h[7] = ROTL64(h[7], 10);	h[6] += h[8];   h[9] ^= h[6];   h[8] = ROTL64(h[8], 13);	h[7] += h[9];   h[10] ^= h[7];  h[9] = ROTL64(h[9], 38);	h[8] += h[10];  h[11] ^= h[8];  h[10] = ROTL64(h[10], 53);	h[9] += h[11];  h[0] ^= h[9];   h[11] = ROTL64(h[11], 42);	h[10] += h[0];  h[1] ^= h[10];  h[0] = ROTL64(h[0], 54);} static inline voidspooky_end(const u64int *restrict data, u64int *restrict h){	h[0] += spooky_read_le64(&data[0]);	h[1] += spooky_read_le64(&data[1]);	h[2] += spooky_read_le64(&data[2]);	h[3] += spooky_read_le64(&data[3]);	h[4] += spooky_read_le64(&data[4]);	h[5] += spooky_read_le64(&data[5]);	h[6] += spooky_read_le64(&data[6]);	h[7] += spooky_read_le64(&data[7]);	h[8] += spooky_read_le64(&data[8]);	h[9] += spooky_read_le64(&data[9]);	h[10] += spooky_read_le64(&data[10]);	h[11] += spooky_read_le64(&data[11]);	spooky_end_partial(h);	spooky_end_partial(h);	spooky_end_partial(h);} //// The goal is for each bit of the input to expand into 128 bits of//   apparent entropy before it is fully overwritten.// n trials both set and cleared at least m bits of h0 h1 h2 h3//   n: 2   m: 29//   n: 3   m: 46//   n: 4   m: 57//   n: 5   m: 107//   n: 6   m: 146//   n: 7   m: 152// when run forwards or backwards// for all 1-bit and 2-bit diffs// with diffs defined by either xor or subtraction// with a base of all zeros plus a counter, or plus another bit, or random//static inline voidspooky_short_mix(u64int *h){	h[2] = ROTL64(h[2], 50);  h[2] += h[3];  h[0] ^= h[2];	h[3] = ROTL64(h[3], 52);  h[3] += h[0];  h[1] ^= h[3];	h[0] = ROTL64(h[0], 30);  h[0] += h[1];  h[2] ^= h[0];	h[1] = ROTL64(h[1], 41);  h[1] += h[2];  h[3] ^= h[1];	h[2] = ROTL64(h[2], 54);  h[2] += h[3];  h[0] ^= h[2];	h[3] = ROTL64(h[3], 48);  h[3] += h[0];  h[1] ^= h[3];	h[0] = ROTL64(h[0], 38);  h[0] += h[1];  h[2] ^= h[0];	h[1] = ROTL64(h[1], 37);  h[1] += h[2];  h[3] ^= h[1];	h[2] = ROTL64(h[2], 62);  h[2] += h[3];  h[0] ^= h[2];	h[3] = ROTL64(h[3], 34);  h[3] += h[0];  h[1] ^= h[3];	h[0] = ROTL64(h[0], 5);   h[0] += h[1];  h[2] ^= h[0];	h[1] = ROTL64(h[1], 36);  h[1] += h[2];  h[3] ^= h[1];} //// Mix all 4 inputs together so that h0, h1 are a hash of them all.//// For two inputs differing in just the input bits// Where "differ" means xor or subtraction// And the base value is random, or a counting value starting at that bit// The final result will have each bit of h0, h1 flip// For every input bit,// with probability 50 +- .3% (it is probably better than that)// For every pair of input bits,// with probability 50 +- .75% (the worst case is approximately that)//static inline voidspooky_short_end(u64int *h){	h[3] ^= h[2];  h[2] = ROTL64(h[2], 15);  h[3] += h[2];	h[0] ^= h[3];  h[3] = ROTL64(h[3], 52);  h[0] += h[3];	h[1] ^= h[0];  h[0] = ROTL64(h[0], 26);  h[1] += h[0];	h[2] ^= h[1];  h[1] = ROTL64(h[1], 51);  h[2] += h[1];	h[3] ^= h[2];  h[2] = ROTL64(h[2], 28);  h[3] += h[2];	h[0] ^= h[3];  h[3] = ROTL64(h[3], 9);   h[0] += h[3];	h[1] ^= h[0];  h[0] = ROTL64(h[0], 47);  h[1] += h[0];	h[2] ^= h[1];  h[1] = ROTL64(h[1], 54);  h[2] += h[1];	h[3] ^= h[2];  h[2] = ROTL64(h[2], 32);  h[3] += h[2];	h[0] ^= h[3];  h[3] = ROTL64(h[3], 25);  h[0] += h[3];	h[1] ^= h[0];  h[0] = ROTL64(h[0], 63);  h[1] += h[0];} //// short hash ... it could be used on any message,// but it's used by Spooky just for short messages.//static voidspooky_short(const void *restrict message, usize length,             u64int *restrict hash1, u64int *restrict hash2){	u64int buf[2 * SC_NUMVARS];	union {		const u8int *p8;		u64int *p64;	} u; 	u.p8 = (const u8int *) message; 	if (ALLOW_UNALIGNED_READS == 0 && !spooky_is_aligned(u.p8, 8)) {		memcpy(buf, message, length);		u.p64 = buf;	} 	usize left = length % 32;	u64int h[4];	h[0] = *hash1;	h[1] = *hash2;	h[2] = SC_CONST;	h[3] = SC_CONST; 	if (length > 15) {		const u64int *end = u.p64 + (length / 32) * 4; 		// handle all complete sets of 32 bytes		for (; u.p64 < end; u.p64 += 4) {			h[2] += spooky_read_le64(&u.p64[0]);			h[3] += spooky_read_le64(&u.p64[1]);			spooky_short_mix(h);			h[0] += spooky_read_le64(&u.p64[2]);			h[1] += spooky_read_le64(&u.p64[3]);		} 		//Handle the case of 16+ remaining bytes.		if (left >= 16) {			h[2] += spooky_read_le64(&u.p64[0]);			h[3] += spooky_read_le64(&u.p64[1]);			spooky_short_mix(h);			u.p64 += 2;			left -= 16;		}	} 	// Handle the last 0..15 bytes, and its length	h[3] += ((u64int) length) << 56;	switch (left) {	case 15:		h[3] += ((u64int) u.p8[14]) << 48; sl_fallthrough;	case 14:		h[3] += ((u64int) u.p8[13]) << 40; sl_fallthrough;	case 13:		h[3] += ((u64int) u.p8[12]) << 32; sl_fallthrough;	case 12:		h[3] += ((u64int) u.p8[11]) << 24; sl_fallthrough;	case 11:		h[3] += ((u64int) u.p8[10]) << 16; sl_fallthrough;	case 10:		h[3] += ((u64int) u.p8[9]) << 8; sl_fallthrough;	case 9:		h[3] += (u64int) u.p8[8]; sl_fallthrough;	case 8:		h[2] += spooky_read_le64(&u.p64[0]);		break;	case 7:		h[2] += ((u64int) u.p8[6]) << 48; sl_fallthrough;	case 6:		h[2] += ((u64int) u.p8[5]) << 40; sl_fallthrough;	case 5:		h[2] += ((u64int) u.p8[4]) << 32; sl_fallthrough;	case 4:		h[2] += ((u64int) u.p8[3]) << 24; sl_fallthrough;	case 3:		h[2] += ((u64int) u.p8[2]) << 16; sl_fallthrough;	case 2:		h[2] += ((u64int) u.p8[1]) << 8; sl_fallthrough;	case 1:		h[2] += (u64int) u.p8[0];		break;	case 0:		h[2] += SC_CONST;		h[3] += SC_CONST;	}	spooky_short_end(h);	*hash1 = h[0];	*hash2 = h[1];} u64intspooky_hash64(const void *message, usize length, u64int seed){	u64int hash1 = seed;	spooky_hash128(message, length, &hash1, &seed);	return hash1;} u32intspooky_hash32(const void *message, usize length, u32int seed){	u64int hash1 = seed, hash2 = seed;	spooky_hash128(message, length, &hash1, &hash2);	return (u32int) hash1;} // do the whole hash in one callvoidspooky_hash128(const void *restrict message, usize length,               u64int *restrict hash1, u64int *restrict hash2){	if (length < SC_BUFSIZE) {		spooky_short(message, length, hash1, hash2);		return;	} 	u64int h[SC_NUMVARS];	u64int buf[SC_NUMVARS];	u64int *end;	union {		const u8int *p8;		u64int *p64;	} u;	usize left; 	h[0] = *hash1;	h[1] = *hash2;	h[2] = SC_CONST;	h[3] = *hash1;	h[4] = *hash2;	h[5] = SC_CONST;	h[6] = *hash1;	h[7] = *hash2;	h[8] = SC_CONST;	h[9] = *hash1;	h[10] = *hash2;	h[11] = SC_CONST; 	u.p8 = (const u8int *) message;	end = u.p64 + (length / SC_BLOCKSIZE) * SC_NUMVARS; 	// handle all whole SC_BLOCKSIZE blocks of bytes	if (ALLOW_UNALIGNED_READS || spooky_is_aligned(u.p8, 8)) {		do {			spooky_mix(u.p64, h);			u.p64 += SC_NUMVARS;		} while (u.p64 < end);	}	else {		do {			memcpy(buf, u.p64, SC_BLOCKSIZE);			spooky_mix(buf, h);			u.p64 += SC_NUMVARS;		} while (u.p64 < end);	} 	// handle the last partial block of SC_BLOCKSIZE bytes	left = length - ((const u8int *) end - (const u8int *) message);	memcpy(buf, end, left);	memset(((u8int *) buf) + left, 0, SC_BLOCKSIZE - left);	((u8int *) buf)[SC_BLOCKSIZE - 1] = (u8int) left; 	// do some final mixing	spooky_end(buf, h);	*hash1 = h[0];	*hash2 = h[1];} /*// init spooky statevoidspooky_init(struct spooky_state *state, u64int seed1, u64int seed2){	state->length = 0;	state->left = 0;	state->state[0] = seed1;	state->state[1] = seed2;} // add a message fragment to the statevoidspooky_update(struct spooky_state *restrict state,              const void *restrict message, usize length){	u64int h[SC_NUMVARS];	usize newLength = length + state->left;	u8int left;	union {		const u8int *p8;		u64int *p64;	} u;	const u64int *end; 	// Is this message fragment too short?  If it is, stuff it away.	if (newLength < SC_BUFSIZE) {		memcpy(&((u8int *) state->data)[state->left], message, length);		state->length = length + state->length;		state->left = (u8int) newLength;		return;	} 	// init the variables	if (state->length < SC_BUFSIZE) {		h[0] = h[3] = h[6] = h[9] = state->state[0];		h[1] = h[4] = h[7] = h[10] = state->state[1];		h[2] = h[5] = h[8] = h[11] = SC_CONST;	}	else {		memcpy(h, state->state, sizeof(state->state));	}	state->length = length + state->length; 	// if we've got anything stuffed away, use it now	if (state->left) {		u8int prefix = SC_BUFSIZE - state->left;		memcpy(&(((u8int *) state->data)[state->left]), message, prefix);		u.p64 = state->data;		spooky_mix(u.p64, h);		spooky_mix(&u.p64[SC_NUMVARS], h);		u.p8 = ((const u8int *) message) + prefix;		length -= prefix;	}	else {		u.p8 = (const u8int *) message;	} 	// handle all whole blocks of SC_BLOCKSIZE bytes	end = u.p64 + (length / SC_BLOCKSIZE) * SC_NUMVARS;	left = (u8int) (length - ((const u8int *) end - u.p8));	if (ALLOW_UNALIGNED_READS || spooky_is_aligned(u.p8, 8)) {		while (u.p64 < end) {			spooky_mix(u.p64, h);			u.p64 += SC_NUMVARS;		}	}	else {		while (u.p64 < end) {			memcpy(state->data, u.p8, SC_BLOCKSIZE);			spooky_mix(state->data, h);			u.p64 += SC_NUMVARS;		}	} 	// stuff away the last few bytes	state->left = left;	memcpy(state->data, end, left); 	// stuff away the variables	memcpy(state->state, h, sizeof(state->state));} // report the hash for the concatenation of all message fragments so farvoidspooky_final(struct spooky_state *restrict state,             u64int *restrict hash1, u64int *restrict hash2){	// init the variables	if (state->length < SC_BUFSIZE) {		*hash1 = state->state[0];		*hash2 = state->state[1];		spooky_short(state->data, state->length, hash1, hash2);		return;	} 	const u64int *data = (const u64int *) state->data;	u8int left = state->left; 

Lines 1–500 of 522. Load more