diff options
Diffstat (limited to 'hv_func.h')
-rw-r--r-- | hv_func.h | 240 |
1 files changed, 184 insertions, 56 deletions
@@ -14,6 +14,8 @@ #if !( 0 \ || defined(PERL_HASH_FUNC_SIPHASH) \ + || defined(PERL_HASH_FUNC_SIPHASH13) \ + || defined(PERL_HASH_FUNC_HYBRID_OAATHU_SIPHASH13) \ || defined(PERL_HASH_FUNC_SDBM) \ || defined(PERL_HASH_FUNC_DJB2) \ || defined(PERL_HASH_FUNC_SUPERFAST) \ @@ -24,13 +26,25 @@ || defined(PERL_HASH_FUNC_MURMUR_HASH_64A) \ || defined(PERL_HASH_FUNC_MURMUR_HASH_64B) \ ) +#ifdef HAS_QUAD +#define PERL_HASH_FUNC_HYBRID_OAATHU_SIPHASH13 +#else #define PERL_HASH_FUNC_ONE_AT_A_TIME_HARD #endif +#endif #if defined(PERL_HASH_FUNC_SIPHASH) # define PERL_HASH_FUNC "SIPHASH_2_4" # define PERL_HASH_SEED_BYTES 16 # define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_siphash_2_4((seed),(U8*)(str),(len)) +#elif defined(PERL_HASH_FUNC_SIPHASH13) +# define PERL_HASH_FUNC "SIPHASH_1_3" +# define PERL_HASH_SEED_BYTES 16 +# define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_siphash_1_3((seed),(U8*)(str),(len)) +#elif defined(PERL_HASH_FUNC_HYBRID_OAATHU_SIPHASH13) +# define PERL_HASH_FUNC "HYBRID_OAATHU_SIPHASH_1_3" +# define PERL_HASH_SEED_BYTES 24 +# define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_oaathu_siphash_1_3((seed),(U8*)(str),(len)) #elif defined(PERL_HASH_FUNC_SUPERFAST) # define PERL_HASH_FUNC "SUPERFAST" # define PERL_HASH_SEED_BYTES 4 @@ -192,72 +206,89 @@ ((U64)((p)[7]) << 56)) #define SIPROUND \ - do { \ + STMT_START { \ v0 += v1; v1=ROTL64(v1,13); v1 ^= v0; v0=ROTL64(v0,32); \ v2 += v3; v3=ROTL64(v3,16); v3 ^= v2; \ v0 += v3; v3=ROTL64(v3,21); v3 ^= v0; \ v2 += v1; v1=ROTL64(v1,17); v1 ^= v2; v2=ROTL64(v2,32); \ - } while(0) + } STMT_END /* SipHash-2-4 */ -PERL_STATIC_INLINE U32 -S_perl_hash_siphash_2_4(const unsigned char * const seed, const unsigned char *in, const STRLEN inlen) { - /* "somepseudorandomlygeneratedbytes" */ - U64 v0 = UINT64_C(0x736f6d6570736575); - U64 v1 = UINT64_C(0x646f72616e646f6d); - U64 v2 = UINT64_C(0x6c7967656e657261); - U64 v3 = UINT64_C(0x7465646279746573); - - U64 b; - U64 k0 = ((const U64*)seed)[0]; - U64 k1 = ((const U64*)seed)[1]; - U64 m; - const int left = inlen & 7; - const U8 *end = in + inlen - left; - - b = ( ( U64 )(inlen) ) << 56; - v3 ^= k1; - v2 ^= k0; - v1 ^= k1; - v0 ^= k0; - - for ( ; in != end; in += 8 ) - { - m = U8TO64_LE( in ); - v3 ^= m; - SIPROUND; - SIPROUND; - v0 ^= m; - } - - switch( left ) - { - case 7: b |= ( ( U64 )in[ 6] ) << 48; - case 6: b |= ( ( U64 )in[ 5] ) << 40; - case 5: b |= ( ( U64 )in[ 4] ) << 32; - case 4: b |= ( ( U64 )in[ 3] ) << 24; - case 3: b |= ( ( U64 )in[ 2] ) << 16; - case 2: b |= ( ( U64 )in[ 1] ) << 8; - case 1: b |= ( ( U64 )in[ 0] ); break; - case 0: break; - } - - v3 ^= b; - SIPROUND; - SIPROUND; - v0 ^= b; - - v2 ^= 0xff; - SIPROUND; - SIPROUND; - SIPROUND; - SIPROUND; - b = v0 ^ v1 ^ v2 ^ v3; - return (U32)(b & U32_MAX); + +#define PERL_SIPHASH_FNC(FNC,SIP_ROUNDS,SIP_FINAL_ROUNDS) \ +PERL_STATIC_INLINE U32 \ +FNC(const unsigned char * const seed, const unsigned char *in, const STRLEN inlen) { \ + /* "somepseudorandomlygeneratedbytes" */ \ + U64 v0 = UINT64_C(0x736f6d6570736575); \ + U64 v1 = UINT64_C(0x646f72616e646f6d); \ + U64 v2 = UINT64_C(0x6c7967656e657261); \ + U64 v3 = UINT64_C(0x7465646279746573); \ + \ + U64 b; \ + U64 k0 = ((const U64*)seed)[0]; \ + U64 k1 = ((const U64*)seed)[1]; \ + U64 m; \ + const int left = inlen & 7; \ + const U8 *end = in + inlen - left; \ + \ + b = ( ( U64 )(inlen) ) << 56; \ + v3 ^= k1; \ + v2 ^= k0; \ + v1 ^= k1; \ + v0 ^= k0; \ + \ + for ( ; in != end; in += 8 ) \ + { \ + m = U8TO64_LE( in ); \ + v3 ^= m; \ + \ + SIP_ROUNDS; \ + \ + v0 ^= m; \ + } \ + \ + switch( left ) \ + { \ + case 7: b |= ( ( U64 )in[ 6] ) << 48; \ + case 6: b |= ( ( U64 )in[ 5] ) << 40; \ + case 5: b |= ( ( U64 )in[ 4] ) << 32; \ + case 4: b |= ( ( U64 )in[ 3] ) << 24; \ + case 3: b |= ( ( U64 )in[ 2] ) << 16; \ + case 2: b |= ( ( U64 )in[ 1] ) << 8; \ + case 1: b |= ( ( U64 )in[ 0] ); break; \ + case 0: break; \ + } \ + \ + v3 ^= b; \ + \ + SIP_ROUNDS; \ + \ + v0 ^= b; \ + \ + v2 ^= 0xff; \ + \ + SIP_FINAL_ROUNDS \ + \ + b = v0 ^ v1 ^ v2 ^ v3; \ + return (U32)(b & U32_MAX); \ } + +PERL_SIPHASH_FNC( + S_perl_hash_siphash_1_3 + ,SIPROUND; + ,SIPROUND;SIPROUND;SIPROUND; +) + +PERL_SIPHASH_FNC( + S_perl_hash_siphash_2_4 + ,SIPROUND;SIPROUND; + ,SIPROUND;SIPROUND;SIPROUND;SIPROUND; +) + #endif /* defined(HAS_QUAD) */ + /* FYI: This is the "Super-Fast" algorithm mentioned by Bob Jenkins in * (http://burtleburtle.net/bob/hash/doobs.html) * It is by Paul Hsieh (c) 2004 and is analysed here @@ -550,6 +581,102 @@ S_perl_hash_one_at_a_time_hard(const unsigned char * const seed, const unsigned return (hash + (hash << 15)); } +#ifdef HAS_QUAD +/* For short strings, 16 bytes or shorter, we use an optimised variant + * of One At A Time Hard, and for longer strings, we use siphash_1_3. + */ +PERL_STATIC_INLINE U32 +S_perl_hash_oaathu_siphash_1_3(const unsigned char * const seed, const unsigned char *str, const STRLEN len) { + U32 hash = *((const U32*)seed) + (U32)len; + switch (len) { + case 16: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[15]; + case 15: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[14]; + case 14: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[13]; + case 13: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[12]; + case 12: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[11]; + case 11: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[10]; + case 10: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[9]; + case 9: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[8]; + case 8: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[7]; + case 7: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[6]; + case 6: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[5]; + case 5: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[4]; + case 4: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[3]; + case 3: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[2]; + case 2: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[1]; + case 1: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += str[0]; + case 0: + hash += (hash << 10); + hash ^= (hash >> 6); + hash += seed[4]; + hash += (hash << 10); + hash ^= (hash >> 6); + hash += seed[5]; + hash += (hash << 10); + hash ^= (hash >> 6); + hash += seed[6]; + hash += (hash << 10); + hash ^= (hash >> 6); + hash += seed[7]; + hash += (hash << 10); + hash ^= (hash >> 6); + + hash += (hash << 3); + hash ^= (hash >> 11); + return (hash + (hash << 15)); + } + return S_perl_hash_siphash_1_3(seed+8, str, len); +} +#endif /* defined(HAS_QUAD) */ + PERL_STATIC_INLINE U32 S_perl_hash_old_one_at_a_time(const unsigned char * const seed, const unsigned char *str, const STRLEN len) { const unsigned char * const end = (const unsigned char *)str + len; @@ -692,6 +819,7 @@ S_perl_hash_murmur_hash_64b (const unsigned char * const seed, const unsigned ch } #endif + /* legacy - only mod_perl should be doing this. */ #ifdef PERL_HASH_INTERNAL_ACCESS #define PERL_HASH_INTERNAL(hash,str,len) PERL_HASH(hash,str,len) |