[perl5.git] / stadtx_hash.h

#ifndef STADTX_HASH_H
#define STADTX_HASH_H

#ifndef DEBUG_STADTX_HASH
#define DEBUG_STADTX_HASH 0
#endif

#ifndef PERL_SEEN_HV_FUNC_H

#if !defined(U64)
    #include <stdint.h>
    #define U64 uint64_t
#endif

#if !defined(U32)
  #define U32 uint32_t
#endif

#if !defined(U8)
    #define U8 unsigned char
#endif

#if !defined(U16)
    #define U16 uint16_t
#endif

#ifndef STRLEN
#define STRLEN int
#endif

#endif

#ifndef STADTX_STATIC_INLINE
#ifdef PERL_STATIC_INLINE
#define STADTX_STATIC_INLINE PERL_STATIC_INLINE
#else
#define STADTX_STATIC_INLINE static inline
#endif
#endif

#ifndef STMT_START
#define STMT_START do
#define STMT_END while(0)
#endif

#ifndef STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
/* STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN only matters if nothing has defined U8TO64_LE etc,
 * and when built with Perl these should be defined before this file is loaded.
 */
#ifdef U32_ALIGNMENT_REQUIRED
#define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 0
#else
#define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 1
#endif
#endif

#ifndef U8TO64_LE
#if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
#define U8TO64_LE(ptr)  (*((const U64 *)(ptr)))
#else
#define U8TO64_LE(ptr)  (\
    (U64)(ptr)[7] << 56 | \
    (U64)(ptr)[6] << 48 | \
    (U64)(ptr)[5] << 40 | \
    (U64)(ptr)[4] << 32 | \
    (U64)(ptr)[3] << 24 | \
    (U64)(ptr)[2] << 16 | \
    (U64)(ptr)[1] << 8  | \
    (U64)(ptr)[0]         \
)
#endif
#endif

#ifndef U8TO32_LE
#if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
#define U8TO32_LE(ptr)  (*((const U32 *)(ptr)))
#else
#define U8TO32_LE(ptr)  (\
    (U32)(ptr)[3] << 24 | \
    (U32)(ptr)[2] << 16 | \
    (U32)(ptr)[1] << 8  | \
    (U32)(ptr)[0]         \
)
#endif
#endif

#ifndef U8TO16_LE
#if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
#define U8TO16_LE(ptr)  (*((const U16 *)(ptr)))
#else
#define U8TO16_LE(ptr)  (\
    (U16)(ptr)[1] << 8  | \
    (U16)(ptr)[0]         \
)
#endif
#endif

/* Find best way to ROTL32/ROTL64 */
#if defined(_MSC_VER)
  #include <stdlib.h>  /* Microsoft put _rotl declaration in here */
  #define ROTL32(x,r)  _rotl(x,r)
  #define ROTR32(x,r)  _rotr(x,r)
  #define ROTL64(x,r)  _rotl64(x,r)
  #define ROTR64(x,r)  _rotr64(x,r)
#else
  /* gcc recognises this code and generates a rotate instruction for CPUs with one */
  #define ROTL32(x,r)  (((U32)(x) << (r)) | ((U32)(x) >> (32 - (r))))
  #define ROTR32(x,r)  (((U32)(x) << (32 - (r))) | ((U32)(x) >> (r)))
  #define ROTL64(x,r)  ( ( (U64)(x) << (r) ) | ( (U64)(x) >> ( 64 - (r) ) ) )
  #define ROTR64(x,r)  ( ( (U64)(x) << ( 64 - (r) ) ) | ( (U64)(x) >> (r) ) )
#endif


/* do a marsaglia xor-shift permutation followed by a
 * multiply by a prime (presumably large) and another
 * marsaglia xor-shift permutation.
 * One of these thoroughly changes the bits of the input.
 * Two of these with different primes passes the Strict Avalanche Criteria
 * in all the tests I did.
 *
 * Note that v cannot end up zero after a scramble64 unless it
 * was zero in the first place.
 */
#define STADTX_SCRAMBLE64(v,prime) STMT_START {    \
    v ^= (v >> 13);                         \
    v ^= (v << 35);                         \
    v ^= (v >> 30);                         \
    v *= prime;                             \
    v ^= (v >> 19);                         \
    v ^= (v << 15);                         \
    v ^= (v >> 46);                         \
} STMT_END


STADTX_STATIC_INLINE void stadtx_seed_state (
    const U8 *seed_ch,
    U8 *state_ch
) {
    const U64 *seed= (const U64 *)seed_ch;
    U64 *state= (U64 *)state_ch;
    /* first we apply two masks to each word of the seed, this means that
     * a) at least one of state[0] and state[2] is nonzero,
     * b) at least one of state[1] and state[3] is nonzero
     * c) that state[0] and state[2] are different
     * d) that state[1] and state[3] are different
     * e) that the replacement value for any zero's is a totally different from the seed value.
     *    (iow, if seed[0] is 0x43f6a8885a308d31UL then state[0] becomes 0, which is the replaced
     *    with 1, which is totally different.). */
    /* hex expansion of pi, skipping first two digits. pi= 3.2[43f6...]*/
    /* pi value in hex from here:
     * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html*/
    state[0]= seed[0] ^ UINT64_C(0x43f6a8885a308d31);
    state[1]= seed[1] ^ UINT64_C(0x3198a2e03707344a);
    state[2]= seed[0] ^ UINT64_C(0x4093822299f31d00);
    state[3]= seed[1] ^ UINT64_C(0x82efa98ec4e6c894);
    if (!state[0]) state[0]=1;
    if (!state[1]) state[1]=2;
    if (!state[2]) state[2]=4;
    if (!state[3]) state[3]=8;
    /* and now for good measure we double scramble all four -
     * a double scramble guarantees a complete avalanche of all the
     * bits in the seed - IOW, by the time we are hashing the
     * four state vectors should be completely different and utterly
     * uncognizable from the input seed bits */
    STADTX_SCRAMBLE64(state[0],UINT64_C(0x801178846e899d17));
    STADTX_SCRAMBLE64(state[0],UINT64_C(0xdd51e5d1c9a5a151));
    STADTX_SCRAMBLE64(state[1],UINT64_C(0x93a7d6c8c62e4835));
    STADTX_SCRAMBLE64(state[1],UINT64_C(0x803340f36895c2b5));
    STADTX_SCRAMBLE64(state[2],UINT64_C(0xbea9344eb7565eeb));
    STADTX_SCRAMBLE64(state[2],UINT64_C(0xcd95d1e509b995cd));
    STADTX_SCRAMBLE64(state[3],UINT64_C(0x9999791977e30c13));
    STADTX_SCRAMBLE64(state[3],UINT64_C(0xaab8b6b05abfc6cd));
}

#define STADTX_K0_U64 UINT64_C(0xb89b0f8e1655514f)
#define STADTX_K1_U64 UINT64_C(0x8c6f736011bd5127)
#define STADTX_K2_U64 UINT64_C(0x8f29bd94edce7b39)
#define STADTX_K3_U64 UINT64_C(0x9c1b8e1e9628323f)

#define STADTX_K2_U32 0x802910e3
#define STADTX_K3_U32 0x819b13af
#define STADTX_K4_U32 0x91cb27e5
#define STADTX_K5_U32 0xc1a269c1

STADTX_STATIC_INLINE U64 stadtx_hash_with_state(
    const U8 *state_ch,
    const U8 *key,
    const STRLEN key_len
) {
    U64 *state= (U64 *)state_ch;
    STRLEN len = key_len;
    U64 v0= state[0] ^ ((key_len+1) * STADTX_K0_U64);
    U64 v1= state[1] ^ ((key_len+2) * STADTX_K1_U64);
    if (len < 32) {
        switch(len >> 3) {
            case 3:
            v0 += U8TO64_LE(key) * STADTX_K3_U64;
            v0= ROTR64(v0, 17) ^ v1;
            v1= ROTR64(v1, 53) + v0;
            key += 8;
            /* FALLTHROUGH */
            case 2:
            v0 += U8TO64_LE(key) * STADTX_K3_U64;
            v0= ROTR64(v0, 17) ^ v1;
            v1= ROTR64(v1, 53) + v0;
            key += 8;
            /* FALLTHROUGH */
            case 1:
            v0 += U8TO64_LE(key) * STADTX_K3_U64;
            v0= ROTR64(v0, 17) ^ v1;
            v1= ROTR64(v1, 53) + v0;
            key += 8;
            /* FALLTHROUGH */
            case 0:
            default: break;
        }
        switch ( len & 0x7 ) {
            case 7: v0 += (U64)key[6] << 32;
            /* FALLTHROUGH */
            case 6: v1 += (U64)key[5] << 48;
            /* FALLTHROUGH */
            case 5: v0 += (U64)key[4] << 16;
            /* FALLTHROUGH */
            case 4: v1 += (U64)U8TO32_LE(key);
                    break;
            case 3: v0 += (U64)key[2] << 48;
            /* FALLTHROUGH */
            case 2: v1 += (U64)U8TO16_LE(key);
                    break;
            case 1: v0 += (U64)key[0];
            /* FALLTHROUGH */
            case 0: v1 = ROTL64(v1, 32) ^ 0xFF;
                    break;
        }
        v1 ^= v0;
        v0 = ROTR64(v0,33) + v1;
        v1 = ROTL64(v1,17) ^ v0;
        v0 = ROTL64(v0,43) + v1;
        v1 = ROTL64(v1,31) - v0;
        v0 = ROTL64(v0,13) ^ v1;
        v1 -= v0;
        v0 = ROTL64(v0,41) + v1;
        v1 = ROTL64(v1,37) ^ v0;
        v0 = ROTR64(v0,39) + v1;
        v1 = ROTR64(v1,15) + v0;
        v0 = ROTL64(v0,15) ^ v1;
        v1 = ROTR64(v1, 5);
        return v0 ^ v1;
    } else {
        U64 v2= state[2] ^ ((key_len+3) * STADTX_K2_U64);
        U64 v3= state[3] ^ ((key_len+4) * STADTX_K3_U64);

        do {
            v0 += (U64)U8TO64_LE(key+ 0) * STADTX_K2_U32; v0= ROTL64(v0,57) ^ v3;
            v1 += (U64)U8TO64_LE(key+ 8) * STADTX_K3_U32; v1= ROTL64(v1,63) ^ v2;
            v2 += (U64)U8TO64_LE(key+16) * STADTX_K4_U32; v2= ROTR64(v2,47) + v0;
            v3 += (U64)U8TO64_LE(key+24) * STADTX_K5_U32; v3= ROTR64(v3,11) - v1;
            key += 32;
            len -= 32;
        } while ( len >= 32 );

        switch ( len >> 3 ) {
            case 3: v0 += ((U64)U8TO64_LE(key) * STADTX_K2_U32); key += 8; v0= ROTL64(v0,57) ^ v3;
            /* FALLTHROUGH */
            case 2: v1 += ((U64)U8TO64_LE(key) * STADTX_K3_U32); key += 8; v1= ROTL64(v1,63) ^ v2;
            /* FALLTHROUGH */
            case 1: v2 += ((U64)U8TO64_LE(key) * STADTX_K4_U32); key += 8; v2= ROTR64(v2,47) + v0;
            /* FALLTHROUGH */
            case 0: v3 = ROTR64(v3,11) - v1;
            /* FALLTHROUGH */
        }
        v0 ^= (len+1) * STADTX_K3_U64;
        switch ( len & 0x7 ) {
            case 7: v1 += (U64)key[6];
            /* FALLTHROUGH */
            case 6: v2 += (U64)U8TO16_LE(key+4);
                    v3 += (U64)U8TO32_LE(key);
                    break;
            case 5: v1 += (U64)key[4];
            /* FALLTHROUGH */
            case 4: v2 += (U64)U8TO32_LE(key);
                    break;
            case 3: v3 += (U64)key[2];
            /* FALLTHROUGH */
            case 2: v1 += (U64)U8TO16_LE(key);
                    break;
            case 1: v2 += (U64)key[0];
            /* FALLTHROUGH */
            case 0: v3 = ROTL64(v3, 32) ^ 0xFF;
                    break;
        }

        v1 -= v2;
        v0 = ROTR64(v0,19);
        v1 -= v0;
        v1 = ROTR64(v1,53);
        v3 ^= v1;
        v0 -= v3;
        v3 = ROTL64(v3,43);
        v0 += v3;
        v0 = ROTR64(v0, 3);
        v3 -= v0;
        v2 = ROTR64(v2,43) - v3;
        v2 = ROTL64(v2,55) ^ v0;
        v1 -= v2;
        v3 = ROTR64(v3, 7) - v2;
        v2 = ROTR64(v2,31);
        v3 += v2;
        v2 -= v1;
        v3 = ROTR64(v3,39);
        v2 ^= v3;
        v3 = ROTR64(v3,17) ^ v2;
        v1 += v3;
        v1 = ROTR64(v1, 9);
        v2 ^= v1;
        v2 = ROTL64(v2,24);
        v3 ^= v2;
        v3 = ROTR64(v3,59);
        v0 = ROTR64(v0, 1) - v1;

        return v0 ^ v1 ^ v2 ^ v3;
    }
}

STADTX_STATIC_INLINE U64 stadtx_hash(
    const U8 *seed_ch,
    const U8 *key,
    const STRLEN key_len
) {
    U64 state[4];
    stadtx_seed_state(seed_ch,(U8*)state);
    return stadtx_hash_with_state((U8*)state,key,key_len);
}

#endif
Commit	Line	Data
9d5e3f1a YO	1	#ifndef STADTX_HASH_H
	2	#define STADTX_HASH_H
	3
	4	#ifndef DEBUG_STADTX_HASH
	5	#define DEBUG_STADTX_HASH 0
	6	#endif
	7
9d5e3f1a YO	8	#ifndef PERL_SEEN_HV_FUNC_H
	9
	10	#if !defined(U64)
	11	#include <stdint.h>
	12	#define U64 uint64_t
	13	#endif
	14
	15	#if !defined(U32)
	16	#define U32 uint32_t
	17	#endif
	18
	19	#if !defined(U8)
	20	#define U8 unsigned char
	21	#endif
	22
	23	#if !defined(U16)
	24	#define U16 uint16_t
	25	#endif
	26
	27	#ifndef STRLEN
	28	#define STRLEN int
	29	#endif
d939098c	30
9d5e3f1a YO	31	#endif
	32
	33	#ifndef STADTX_STATIC_INLINE
	34	#ifdef PERL_STATIC_INLINE
	35	#define STADTX_STATIC_INLINE PERL_STATIC_INLINE
	36	#else
	37	#define STADTX_STATIC_INLINE static inline
	38	#endif
	39	#endif
	40
	41	#ifndef STMT_START
	42	#define STMT_START do
	43	#define STMT_END while(0)
	44	#endif
	45
9995b99e	46	#ifndef STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
d939098c YO	47	/* STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN only matters if nothing has defined U8TO64_LE etc,
	48	* and when built with Perl these should be defined before this file is loaded.
	49	*/
	50	#ifdef U32_ALIGNMENT_REQUIRED
	51	#define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 0
	52	#else
9995b99e	53	#define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 1
9d5e3f1a	54	#endif
d939098c YO	55	#endif
	56
	57	#ifndef U8TO64_LE
	58	#if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
	59	#define U8TO64_LE(ptr) (((const U64 )(ptr)))
	60	#else
	61	#define U8TO64_LE(ptr) (\
	62	(U64)(ptr)[7] << 56 \| \
	63	(U64)(ptr)[6] << 48 \| \
	64	(U64)(ptr)[5] << 40 \| \
	65	(U64)(ptr)[4] << 32 \| \
	66	(U64)(ptr)[3] << 24 \| \
	67	(U64)(ptr)[2] << 16 \| \
	68	(U64)(ptr)[1] << 8 \| \
	69	(U64)(ptr)[0] \
	70	)
	71	#endif
	72	#endif
9d5e3f1a	73
d939098c	74	#ifndef U8TO32_LE
9d5e3f1a	75	#if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
d939098c	76	#define U8TO32_LE(ptr) (((const U32 )(ptr)))
9d5e3f1a	77	#else
d939098c YO	78	#define U8TO32_LE(ptr) (\
	79	(U32)(ptr)[3] << 24 \| \
	80	(U32)(ptr)[2] << 16 \| \
	81	(U32)(ptr)[1] << 8 \| \
	82	(U32)(ptr)[0] \
	83	)
9d5e3f1a	84	#endif
d939098c YO	85	#endif
	86
	87	#ifndef U8TO16_LE
	88	#if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
	89	#define U8TO16_LE(ptr) (((const U16 )(ptr)))
	90	#else
	91	#define U8TO16_LE(ptr) (\
	92	(U16)(ptr)[1] << 8 \| \
	93	(U16)(ptr)[0] \
	94	)
	95	#endif
	96	#endif
	97
	98	/* Find best way to ROTL32/ROTL64 */
	99	#if defined(_MSC_VER)
	100	#include <stdlib.h> /* Microsoft put _rotl declaration in here */
	101	#define ROTL32(x,r) _rotl(x,r)
	102	#define ROTR32(x,r) _rotr(x,r)
	103	#define ROTL64(x,r) _rotl64(x,r)
	104	#define ROTR64(x,r) _rotr64(x,r)
	105	#else
	106	/* gcc recognises this code and generates a rotate instruction for CPUs with one */
	107	#define ROTL32(x,r) (((U32)(x) << (r)) \| ((U32)(x) >> (32 - (r))))
	108	#define ROTR32(x,r) (((U32)(x) << (32 - (r))) \| ((U32)(x) >> (r)))
	109	#define ROTL64(x,r) ( ( (U64)(x) << (r) ) \| ( (U64)(x) >> ( 64 - (r) ) ) )
	110	#define ROTR64(x,r) ( ( (U64)(x) << ( 64 - (r) ) ) \| ( (U64)(x) >> (r) ) )
	111	#endif
	112
9d5e3f1a YO	113
	114	/* do a marsaglia xor-shift permutation followed by a
	115	* multiply by a prime (presumably large) and another
	116	* marsaglia xor-shift permutation.
	117	* One of these thoroughly changes the bits of the input.
	118	* Two of these with different primes passes the Strict Avalanche Criteria
	119	* in all the tests I did.
	120	*
	121	* Note that v cannot end up zero after a scramble64 unless it
	122	* was zero in the first place.
	123	*/
	124	#define STADTX_SCRAMBLE64(v,prime) STMT_START { \
	125	v ^= (v >> 13); \
	126	v ^= (v << 35); \
	127	v ^= (v >> 30); \
	128	v *= prime; \
	129	v ^= (v >> 19); \
	130	v ^= (v << 15); \
	131	v ^= (v >> 46); \
	132	} STMT_END
	133
	134
	135	STADTX_STATIC_INLINE void stadtx_seed_state (
	136	const U8 *seed_ch,
	137	U8 *state_ch
	138	) {
20e4c2ed	139	const U64 seed= (const U64 )seed_ch;
9d5e3f1a YO	140	U64 state= (U64 )state_ch;
	141	/* first we apply two masks to each word of the seed, this means that
	142	* a) at least one of state[0] and state[2] is nonzero,
	143	* b) at least one of state[1] and state[3] is nonzero
	144	* c) that state[0] and state[2] are different
	145	* d) that state[1] and state[3] are different
	146	* e) that the replacement value for any zero's is a totally different from the seed value.
	147	* (iow, if seed[0] is 0x43f6a8885a308d31UL then state[0] becomes 0, which is the replaced
	148	* with 1, which is totally different.). */
	149	/* hex expansion of pi, skipping first two digits. pi= 3.2[43f6...]*/
	150	/* pi value in hex from here:
	151	* http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html*/
d68aa7aa JH	152	state[0]= seed[0] ^ UINT64_C(0x43f6a8885a308d31);
	153	state[1]= seed[1] ^ UINT64_C(0x3198a2e03707344a);
	154	state[2]= seed[0] ^ UINT64_C(0x4093822299f31d00);
	155	state[3]= seed[1] ^ UINT64_C(0x82efa98ec4e6c894);
9d5e3f1a YO	156	if (!state[0]) state[0]=1;
	157	if (!state[1]) state[1]=2;
	158	if (!state[2]) state[2]=4;
	159	if (!state[3]) state[3]=8;
	160	/* and now for good measure we double scramble all four -
	161	* a double scramble guarantees a complete avalanche of all the
	162	* bits in the seed - IOW, by the time we are hashing the
	163	* four state vectors should be completely different and utterly
	164	* uncognizable from the input seed bits */
d68aa7aa JH	165	STADTX_SCRAMBLE64(state[0],UINT64_C(0x801178846e899d17));
	166	STADTX_SCRAMBLE64(state[0],UINT64_C(0xdd51e5d1c9a5a151));
	167	STADTX_SCRAMBLE64(state[1],UINT64_C(0x93a7d6c8c62e4835));
	168	STADTX_SCRAMBLE64(state[1],UINT64_C(0x803340f36895c2b5));
	169	STADTX_SCRAMBLE64(state[2],UINT64_C(0xbea9344eb7565eeb));
	170	STADTX_SCRAMBLE64(state[2],UINT64_C(0xcd95d1e509b995cd));
	171	STADTX_SCRAMBLE64(state[3],UINT64_C(0x9999791977e30c13));
	172	STADTX_SCRAMBLE64(state[3],UINT64_C(0xaab8b6b05abfc6cd));
9d5e3f1a YO	173	}
9d5e3f1a YO	174
d68aa7aa JH	175	#define STADTX_K0_U64 UINT64_C(0xb89b0f8e1655514f)
	176	#define STADTX_K1_U64 UINT64_C(0x8c6f736011bd5127)
	177	#define STADTX_K2_U64 UINT64_C(0x8f29bd94edce7b39)
	178	#define STADTX_K3_U64 UINT64_C(0x9c1b8e1e9628323f)
9d5e3f1a YO	179
	180	#define STADTX_K2_U32 0x802910e3
	181	#define STADTX_K3_U32 0x819b13af
	182	#define STADTX_K4_U32 0x91cb27e5
	183	#define STADTX_K5_U32 0xc1a269c1
	184
	185	STADTX_STATIC_INLINE U64 stadtx_hash_with_state(
	186	const U8 *state_ch,
	187	const U8 *key,
	188	const STRLEN key_len
	189	) {
	190	U64 state= (U64 )state_ch;
9995b99e	191	STRLEN len = key_len;
9d5e3f1a YO	192	U64 v0= state[0] ^ ((key_len+1) * STADTX_K0_U64);
	193	U64 v1= state[1] ^ ((key_len+2) * STADTX_K1_U64);
	194	if (len < 32) {
	195	switch(len >> 3) {
	196	case 3:
	197	v0 += U8TO64_LE(key) * STADTX_K3_U64;
	198	v0= ROTR64(v0, 17) ^ v1;
	199	v1= ROTR64(v1, 53) + v0;
	200	key += 8;
b2733f8f	201	/* FALLTHROUGH */
9d5e3f1a YO	202	case 2:
	203	v0 += U8TO64_LE(key) * STADTX_K3_U64;
	204	v0= ROTR64(v0, 17) ^ v1;
	205	v1= ROTR64(v1, 53) + v0;
	206	key += 8;
b2733f8f	207	/* FALLTHROUGH */
9d5e3f1a YO	208	case 1:
	209	v0 += U8TO64_LE(key) * STADTX_K3_U64;
	210	v0= ROTR64(v0, 17) ^ v1;
	211	v1= ROTR64(v1, 53) + v0;
	212	key += 8;
b2733f8f	213	/* FALLTHROUGH */
9d5e3f1a YO	214	case 0:
	215	default: break;
	216	}
	217	switch ( len & 0x7 ) {
	218	case 7: v0 += (U64)key[6] << 32;
b2733f8f	219	/* FALLTHROUGH */
9d5e3f1a	220	case 6: v1 += (U64)key[5] << 48;
b2733f8f	221	/* FALLTHROUGH */
9d5e3f1a	222	case 5: v0 += (U64)key[4] << 16;
b2733f8f	223	/* FALLTHROUGH */
9d5e3f1a YO	224	case 4: v1 += (U64)U8TO32_LE(key);
	225	break;
	226	case 3: v0 += (U64)key[2] << 48;
b2733f8f	227	/* FALLTHROUGH */
9d5e3f1a YO	228	case 2: v1 += (U64)U8TO16_LE(key);
	229	break;
	230	case 1: v0 += (U64)key[0];
b2733f8f	231	/* FALLTHROUGH */
9d5e3f1a YO	232	case 0: v1 = ROTL64(v1, 32) ^ 0xFF;
	233	break;
	234	}
	235	v1 ^= v0;
	236	v0 = ROTR64(v0,33) + v1;
	237	v1 = ROTL64(v1,17) ^ v0;
	238	v0 = ROTL64(v0,43) + v1;
	239	v1 = ROTL64(v1,31) - v0;
	240	v0 = ROTL64(v0,13) ^ v1;
	241	v1 -= v0;
	242	v0 = ROTL64(v0,41) + v1;
	243	v1 = ROTL64(v1,37) ^ v0;
	244	v0 = ROTR64(v0,39) + v1;
	245	v1 = ROTR64(v1,15) + v0;
	246	v0 = ROTL64(v0,15) ^ v1;
	247	v1 = ROTR64(v1, 5);
	248	return v0 ^ v1;
	249	} else {
	250	U64 v2= state[2] ^ ((key_len+3) * STADTX_K2_U64);
	251	U64 v3= state[3] ^ ((key_len+4) * STADTX_K3_U64);
	252
	253	do {
	254	v0 += (U64)U8TO64_LE(key+ 0) * STADTX_K2_U32; v0= ROTL64(v0,57) ^ v3;
	255	v1 += (U64)U8TO64_LE(key+ 8) * STADTX_K3_U32; v1= ROTL64(v1,63) ^ v2;
	256	v2 += (U64)U8TO64_LE(key+16) * STADTX_K4_U32; v2= ROTR64(v2,47) + v0;
	257	v3 += (U64)U8TO64_LE(key+24) * STADTX_K5_U32; v3= ROTR64(v3,11) - v1;
	258	key += 32;
	259	len -= 32;
	260	} while ( len >= 32 );
	261
	262	switch ( len >> 3 ) {
	263	case 3: v0 += ((U64)U8TO64_LE(key) * STADTX_K2_U32); key += 8; v0= ROTL64(v0,57) ^ v3;
b2733f8f	264	/* FALLTHROUGH */
9d5e3f1a	265	case 2: v1 += ((U64)U8TO64_LE(key) * STADTX_K3_U32); key += 8; v1= ROTL64(v1,63) ^ v2;
b2733f8f	266	/* FALLTHROUGH */
9d5e3f1a	267	case 1: v2 += ((U64)U8TO64_LE(key) * STADTX_K4_U32); key += 8; v2= ROTR64(v2,47) + v0;
b2733f8f	268	/* FALLTHROUGH */
9d5e3f1a	269	case 0: v3 = ROTR64(v3,11) - v1;
b2733f8f	270	/* FALLTHROUGH */
9d5e3f1a YO	271	}
	272	v0 ^= (len+1) * STADTX_K3_U64;
	273	switch ( len & 0x7 ) {
	274	case 7: v1 += (U64)key[6];
b2733f8f	275	/* FALLTHROUGH */
9d5e3f1a YO	276	case 6: v2 += (U64)U8TO16_LE(key+4);
	277	v3 += (U64)U8TO32_LE(key);
	278	break;
	279	case 5: v1 += (U64)key[4];
b2733f8f	280	/* FALLTHROUGH */
9d5e3f1a YO	281	case 4: v2 += (U64)U8TO32_LE(key);
	282	break;
	283	case 3: v3 += (U64)key[2];
b2733f8f	284	/* FALLTHROUGH */
9d5e3f1a YO	285	case 2: v1 += (U64)U8TO16_LE(key);
	286	break;
	287	case 1: v2 += (U64)key[0];
b2733f8f	288	/* FALLTHROUGH */
9d5e3f1a YO	289	case 0: v3 = ROTL64(v3, 32) ^ 0xFF;
	290	break;
	291	}
	292
	293	v1 -= v2;
	294	v0 = ROTR64(v0,19);
	295	v1 -= v0;
	296	v1 = ROTR64(v1,53);
	297	v3 ^= v1;
	298	v0 -= v3;
	299	v3 = ROTL64(v3,43);
	300	v0 += v3;
	301	v0 = ROTR64(v0, 3);
	302	v3 -= v0;
	303	v2 = ROTR64(v2,43) - v3;
	304	v2 = ROTL64(v2,55) ^ v0;
	305	v1 -= v2;
	306	v3 = ROTR64(v3, 7) - v2;
	307	v2 = ROTR64(v2,31);
	308	v3 += v2;
	309	v2 -= v1;
	310	v3 = ROTR64(v3,39);
	311	v2 ^= v3;
	312	v3 = ROTR64(v3,17) ^ v2;
	313	v1 += v3;
	314	v1 = ROTR64(v1, 9);
	315	v2 ^= v1;
	316	v2 = ROTL64(v2,24);
	317	v3 ^= v2;
	318	v3 = ROTR64(v3,59);
	319	v0 = ROTR64(v0, 1) - v1;
	320
	321	return v0 ^ v1 ^ v2 ^ v3;
	322	}
	323	}
	324
	325	STADTX_STATIC_INLINE U64 stadtx_hash(
	326	const U8 *seed_ch,
	327	const U8 *key,
	328	const STRLEN key_len
	329	) {
	330	U64 state[4];
	331	stadtx_seed_state(seed_ch,(U8*)state);
	332	return stadtx_hash_with_state((U8*)state,key,key_len);
	333	}
	334
	335	#endif