/* hash a key
*--------------------------------------------------------------------------------------
* The "hash seed" feature was added in Perl 5.8.1 to perturb the results
* to avoid "algorithmic complexity attacks".
*
* If USE_HASH_SEED is defined, hash randomisation is done by default
* If USE_HASH_SEED_EXPLICIT is defined, hash randomisation is done
* only if the environment variable PERL_HASH_SEED is set.
* (see also perl.c:perl_parse() and S_init_tls_and_interp() and util.c:get_hash_seed())
*/
#ifndef PERL_SEEN_HV_FUNC_H /* compile once */
#define PERL_SEEN_HV_FUNC_H
#if !( 0 \
|| defined(PERL_HASH_FUNC_SIPHASH) \
|| defined(PERL_HASH_FUNC_SIPHASH13) \
|| defined(PERL_HASH_FUNC_HYBRID_OAATHU_SIPHASH13) \
|| defined(PERL_HASH_FUNC_ONE_AT_A_TIME_HARD) \
)
#if IVSIZE == 8
#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_ONE_AT_A_TIME_HARD)
# define PERL_HASH_FUNC "ONE_AT_A_TIME_HARD"
# define PERL_HASH_SEED_BYTES 8
# define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_one_at_a_time_hard((seed),(U8*)(str),(len))
#endif
#ifndef PERL_HASH_WITH_SEED
#error "No hash function defined!"
#endif
#ifndef PERL_HASH_SEED_BYTES
#error "PERL_HASH_SEED_BYTES not defined"
#endif
#ifndef PERL_HASH_FUNC
#error "PERL_HASH_FUNC not defined"
#endif
#ifndef PERL_HASH_SEED
# if defined(USE_HASH_SEED) || defined(USE_HASH_SEED_EXPLICIT)
# define PERL_HASH_SEED PL_hash_seed
# elif PERL_HASH_SEED_BYTES == 4
# define PERL_HASH_SEED ((const U8 *)"PeRl")
# elif PERL_HASH_SEED_BYTES == 8
# define PERL_HASH_SEED ((const U8 *)"PeRlHaSh")
# elif PERL_HASH_SEED_BYTES == 16
# define PERL_HASH_SEED ((const U8 *)"PeRlHaShhAcKpErl")
# else
# error "No PERL_HASH_SEED definition for " PERL_HASH_FUNC
# endif
#endif
#define PERL_HASH(hash,str,len) PERL_HASH_WITH_SEED(PERL_HASH_SEED,hash,str,len)
/* 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)
#endif
/*-----------------------------------------------------------------------------
* Endianess, misalignment capabilities and util macros
*
* The following 3 macros are defined in this section. The other macros defined
* are only needed to help derive these 3.
*
* U8TO32_LE(x) Read a little endian unsigned 32-bit int
* UNALIGNED_SAFE Defined if unaligned access is safe
* ROTL32(x,r) Rotate x left by r bits
*/
#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
|| defined(_MSC_VER) || defined (__TURBOC__)
#define U8TO16_LE(d) (*((const U16 *) (d)))
#endif
#if !defined (U8TO16_LE)
#define U8TO16_LE(d) ((((const U8 *)(d))[1] << 8)\
+((const U8 *)(d))[0])
#endif
#if (BYTEORDER == 0x1234 || BYTEORDER == 0x12345678) && U32SIZE == 4
/* CPU endian matches murmurhash algorithm, so read 32-bit word directly */
#define U8TO32_LE(ptr) (*((const U32*)(ptr)))
#elif BYTEORDER == 0x4321 || BYTEORDER == 0x87654321
/* TODO: Add additional cases below where a compiler provided bswap32 is available */
#if defined(__GNUC__) && (__GNUC__>4 || (__GNUC__==4 && __GNUC_MINOR__>=3))
#define U8TO32_LE(ptr) (__builtin_bswap32(*((U32*)(ptr))))
#else
/* Without a known fast bswap32 we're just as well off doing this */
#define U8TO32_LE(ptr) (ptr[0]|ptr[1]<<8|ptr[2]<<16|ptr[3]<<24)
#define UNALIGNED_SAFE
#endif
#else
/* Unknown endianess so last resort is to read individual bytes */
#define U8TO32_LE(ptr) (ptr[0]|ptr[1]<<8|ptr[2]<<16|ptr[3]<<24)
/* Since we're not doing word-reads we can skip the messing about with realignment */
#define UNALIGNED_SAFE
#endif
#ifdef HAS_QUAD
#ifndef U64TYPE
/* This probably isn't going to work, but failing with a compiler error due to
lack of uint64_t is no worse than failing right now with an #error. */
#define U64 uint64_t
#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)
#ifdef HAS_QUAD
#define ROTL64(x,r) _rotl64(x,r)
#endif
#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)))
#ifdef HAS_QUAD
#define ROTL64(x,r) (((U64)x << r) | ((U64)x >> (64 - r)))
#endif
#endif
#ifdef UV_IS_QUAD
#define ROTL_UV(x,r) ROTL64(x,r)
#else
#define ROTL_UV(x,r) ROTL32(x,r)
#endif
/* This is SipHash by Jean-Philippe Aumasson and Daniel J. Bernstein.
* The authors claim it is relatively secure compared to the alternatives
* and that performance wise it is a suitable hash for languages like Perl.
* See:
*
* https://www.131002.net/siphash/
*
* This implementation seems to perform slightly slower than one-at-a-time for
* short keys, but degrades slower for longer keys. Murmur Hash outperforms it
* regardless of keys size.
*
* It is 64 bit only.
*/
#ifdef HAS_QUAD
#define U8TO64_LE(p) \
(((U64)((p)[0]) ) | \
((U64)((p)[1]) << 8) | \
((U64)((p)[2]) << 16) | \
((U64)((p)[3]) << 24) | \
((U64)((p)[4]) << 32) | \
((U64)((p)[5]) << 40) | \
((U64)((p)[6]) << 48) | \
((U64)((p)[7]) << 56))
#define SIPROUND \
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); \
} STMT_END
/* SipHash-2-4 */
#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) */
/* - ONE_AT_A_TIME_HARD is the 5.17+ recommend ONE_AT_A_TIME variant */
/* This is derived from the "One-at-a-Time" algorithm by Bob Jenkins
* from requirements by Colin Plumb.
* (http://burtleburtle.net/bob/hash/doobs.html)
* Modified by Yves Orton to increase security for Perl 5.17 and later.
*/
PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time_hard(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
const unsigned char * const end = (const unsigned char *)str + len;
U32 hash = *((const U32*)seed) + (U32)len;
while (str < end) {
hash += (hash << 10);
hash ^= (hash >> 6);
hash += *str++;
}
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));
}
#ifdef HAS_QUAD
/* Hybrid hash function
*
* 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.
*
* The optimisation of One At A Time Hard means we read the key in
* reverse from normal, but by doing so we avoid the loop overhead.
*/
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) */
#endif /*compile once*/
/*
* ex: set ts=8 sts=4 sw=4 et:
*/