hv_func.h revision 1.11
1/* hash a key 2 *-------------------------------------------------------------------------------------- 3 * The "hash seed" feature was added in Perl 5.8.1 to perturb the results 4 * to avoid "algorithmic complexity attacks". 5 * 6 * If USE_HASH_SEED is defined, hash randomisation is done by default 7 * (see also perl.c:perl_parse() and S_init_tls_and_interp() and util.c:get_hash_seed()) 8 */ 9#ifndef PERL_SEEN_HV_FUNC_H /* compile once */ 10#define PERL_SEEN_HV_FUNC_H 11#include "hv_macro.h" 12 13#if !( 0 \ 14 || defined(PERL_HASH_FUNC_SIPHASH) \ 15 || defined(PERL_HASH_FUNC_SIPHASH13) \ 16 || defined(PERL_HASH_FUNC_STADTX) \ 17 || defined(PERL_HASH_FUNC_ZAPHOD32) \ 18 ) 19# ifdef CAN64BITHASH 20# define PERL_HASH_FUNC_STADTX 21# else 22# define PERL_HASH_FUNC_ZAPHOD32 23# endif 24#endif 25 26#ifndef PERL_HASH_USE_SBOX32_ALSO 27#define PERL_HASH_USE_SBOX32_ALSO 1 28#endif 29 30#ifndef SBOX32_MAX_LEN 31#define SBOX32_MAX_LEN 24 32#endif 33 34/* this must be after the SBOX32_MAX_LEN define */ 35#include "sbox32_hash.h" 36 37#if defined(PERL_HASH_FUNC_SIPHASH) 38# define __PERL_HASH_FUNC "SIPHASH_2_4" 39# define __PERL_HASH_WORD_TYPE U64 40# define __PERL_HASH_WORD_SIZE sizeof(__PERL_HASH_WORD_TYPE) 41# define __PERL_HASH_SEED_BYTES (__PERL_HASH_WORD_SIZE * 2) 42# define __PERL_HASH_STATE_BYTES (__PERL_HASH_WORD_SIZE * 4) 43# define __PERL_HASH_SEED_STATE(seed,state) S_perl_siphash_seed_state(seed,state) 44# define __PERL_HASH_WITH_STATE(state,str,len) S_perl_hash_siphash_2_4_with_state((state),(U8*)(str),(len)) 45#elif defined(PERL_HASH_FUNC_SIPHASH13) 46# define __PERL_HASH_FUNC "SIPHASH_1_3" 47# define __PERL_HASH_WORD_TYPE U64 48# define __PERL_HASH_WORD_SIZE sizeof(__PERL_HASH_WORD_TYPE) 49# define __PERL_HASH_SEED_BYTES (__PERL_HASH_WORD_SIZE * 2) 50# define __PERL_HASH_STATE_BYTES (__PERL_HASH_WORD_SIZE * 4) 51# define __PERL_HASH_SEED_STATE(seed,state) S_perl_siphash_seed_state(seed,state) 52# define __PERL_HASH_WITH_STATE(state,str,len) S_perl_hash_siphash_1_3_with_state((state),(U8*)(str),(len)) 53#elif defined(PERL_HASH_FUNC_STADTX) 54# define __PERL_HASH_FUNC "STADTX" 55# define __PERL_HASH_WORD_TYPE U64 56# define __PERL_HASH_WORD_SIZE sizeof(__PERL_HASH_WORD_TYPE) 57# define __PERL_HASH_SEED_BYTES (__PERL_HASH_WORD_SIZE * 2) 58# define __PERL_HASH_STATE_BYTES (__PERL_HASH_WORD_SIZE * 4) 59# define __PERL_HASH_SEED_STATE(seed,state) stadtx_seed_state(seed,state) 60# define __PERL_HASH_WITH_STATE(state,str,len) (U32)stadtx_hash_with_state((state),(U8*)(str),(len)) 61# include "stadtx_hash.h" 62#elif defined(PERL_HASH_FUNC_ZAPHOD32) 63# define __PERL_HASH_FUNC "ZAPHOD32" 64# define __PERL_HASH_WORD_TYPE U32 65# define __PERL_HASH_WORD_SIZE sizeof(__PERL_HASH_WORD_TYPE) 66# define __PERL_HASH_SEED_BYTES (__PERL_HASH_WORD_SIZE * 3) 67# define __PERL_HASH_STATE_BYTES (__PERL_HASH_WORD_SIZE * 3) 68# define __PERL_HASH_SEED_STATE(seed,state) zaphod32_seed_state(seed,state) 69# define __PERL_HASH_WITH_STATE(state,str,len) (U32)zaphod32_hash_with_state((state),(U8*)(str),(len)) 70# include "zaphod32_hash.h" 71#endif 72 73#ifndef __PERL_HASH_WITH_STATE 74#error "No hash function defined!" 75#endif 76#ifndef __PERL_HASH_SEED_BYTES 77#error "__PERL_HASH_SEED_BYTES not defined" 78#endif 79#ifndef __PERL_HASH_FUNC 80#error "__PERL_HASH_FUNC not defined" 81#endif 82 83 84#define __PERL_HASH_SEED_roundup(x, y) ( ( ( (x) + ( (y) - 1 ) ) / (y) ) * (y) ) 85#define _PERL_HASH_SEED_roundup(x) __PERL_HASH_SEED_roundup(x,__PERL_HASH_WORD_SIZE) 86 87#define PL_hash_seed ((U8 *)PL_hash_seed_w) 88#define PL_hash_state ((U8 *)PL_hash_state_w) 89 90#if PERL_HASH_USE_SBOX32_ALSO != 1 91# define _PERL_HASH_FUNC __PERL_HASH_FUNC 92# define _PERL_HASH_SEED_BYTES __PERL_HASH_SEED_BYTES 93# define _PERL_HASH_STATE_BYTES __PERL_HASH_STATE_BYTES 94# define _PERL_HASH_SEED_STATE(seed,state) __PERL_HASH_SEED_STATE(seed,state) 95# define _PERL_HASH_WITH_STATE(state,str,len) __PERL_HASH_WITH_STATE(state,str,len) 96#else 97 98#define _PERL_HASH_FUNC "SBOX32_WITH_" __PERL_HASH_FUNC 99/* note the 3 in the below code comes from the fact the seed to initialize the SBOX is 96 bits */ 100#define _PERL_HASH_SEED_BYTES ( __PERL_HASH_SEED_BYTES + (int)( 3 * sizeof(U32)) ) 101 102#define _PERL_HASH_STATE_BYTES \ 103 ( __PERL_HASH_STATE_BYTES + ( ( 1 + ( 256 * SBOX32_MAX_LEN ) ) * sizeof(U32) ) ) 104 105#define _PERL_HASH_SEED_STATE(seed,state) STMT_START { \ 106 __PERL_HASH_SEED_STATE(seed,state); \ 107 sbox32_seed_state96(seed + __PERL_HASH_SEED_BYTES, state + __PERL_HASH_STATE_BYTES); \ 108} STMT_END 109 110#define _PERL_HASH_WITH_STATE(state,str,len) \ 111 (LIKELY(len <= SBOX32_MAX_LEN) \ 112 ? sbox32_hash_with_state((state + __PERL_HASH_STATE_BYTES),(U8*)(str),(len)) \ 113 : __PERL_HASH_WITH_STATE((state),(str),(len))) 114 115#endif 116 117#define PERL_HASH_WITH_SEED(seed,hash,str,len) \ 118 (hash) = S_perl_hash_with_seed((const U8 *) seed, (const U8 *) str,len) 119#define PERL_HASH_WITH_STATE(state,hash,str,len) \ 120 (hash) = _PERL_HASH_WITH_STATE((state),(U8*)(str),(len)) 121 122#define PERL_HASH_SEED_STATE(seed,state) _PERL_HASH_SEED_STATE(seed,state) 123#define PERL_HASH_SEED_BYTES _PERL_HASH_SEED_roundup(_PERL_HASH_SEED_BYTES) 124#define PERL_HASH_STATE_BYTES _PERL_HASH_SEED_roundup(_PERL_HASH_STATE_BYTES) 125#define PERL_HASH_FUNC _PERL_HASH_FUNC 126 127#define PERL_HASH_SEED_WORDS (PERL_HASH_SEED_BYTES/__PERL_HASH_WORD_SIZE) 128#define PERL_HASH_STATE_WORDS (PERL_HASH_STATE_BYTES/__PERL_HASH_WORD_SIZE) 129 130#ifdef PERL_USE_SINGLE_CHAR_HASH_CACHE 131#define PERL_HASH(state,str,len) \ 132 (hash) = ((len) < 2 ? ( (len) == 0 ? PL_hash_chars[256] : PL_hash_chars[(U8)(str)[0]] ) \ 133 : _PERL_HASH_WITH_STATE(PL_hash_state,(U8*)(str),(len))) 134#else 135#define PERL_HASH(hash,str,len) \ 136 PERL_HASH_WITH_STATE(PL_hash_state,hash,(U8*)(str),(len)) 137#endif 138 139/* Setup the hash seed, either we do things dynamically at start up, 140 * including reading from the environment, or we randomly setup the 141 * seed. The seed will be passed into the PERL_HASH_SEED_STATE() function 142 * defined for the configuration defined for this perl, which will then 143 * initialize whatever state it might need later in hashing. */ 144 145#ifndef PERL_HASH_SEED 146# if defined(USE_HASH_SEED) 147# define PERL_HASH_SEED PL_hash_seed 148# else 149 /* this is a 512 bit seed, which should be more than enough for the 150 * configuration of any of our hash functions (with or without sbox). 151 * If you actually use a hard coded seed, you are strongly encouraged 152 * to replace this with something else of the correct length 153 * for the hash function you are using (24-32 bytes depending on build 154 * options). Repeat, you are *STRONGLY* encouraged not to use the value 155 * provided here. 156 */ 157# define PERL_HASH_SEED \ 158 ((const U8 *)"A long string of pseudorandomly " \ 159 "chosen bytes for hashing in Perl") 160# endif 161#endif 162 163/* legacy - only mod_perl should be doing this. */ 164#ifdef PERL_HASH_INTERNAL_ACCESS 165#define PERL_HASH_INTERNAL(hash,str,len) PERL_HASH(hash,str,len) 166#endif 167 168/* This is SipHash by Jean-Philippe Aumasson and Daniel J. Bernstein. 169 * The authors claim it is relatively secure compared to the alternatives 170 * and that performance wise it is a suitable hash for languages like Perl. 171 * See: 172 * 173 * https://www.131002.net/siphash/ 174 * 175 * This implementation seems to perform slightly slower than one-at-a-time for 176 * short keys, but degrades slower for longer keys. Murmur Hash outperforms it 177 * regardless of keys size. 178 * 179 * It is 64 bit only. 180 */ 181 182#ifdef CAN64BITHASH 183 184#define SIPROUND \ 185 STMT_START { \ 186 v0 += v1; v1=ROTL64(v1,13); v1 ^= v0; v0=ROTL64(v0,32); \ 187 v2 += v3; v3=ROTL64(v3,16); v3 ^= v2; \ 188 v0 += v3; v3=ROTL64(v3,21); v3 ^= v0; \ 189 v2 += v1; v1=ROTL64(v1,17); v1 ^= v2; v2=ROTL64(v2,32); \ 190 } STMT_END 191 192#define SIPHASH_SEED_STATE(key,v0,v1,v2,v3) \ 193do { \ 194 v0 = v2 = U8TO64_LE(key + 0); \ 195 v1 = v3 = U8TO64_LE(key + 8); \ 196 /* "somepseudorandomlygeneratedbytes" */ \ 197 v0 ^= UINT64_C(0x736f6d6570736575); \ 198 v1 ^= UINT64_C(0x646f72616e646f6d); \ 199 v2 ^= UINT64_C(0x6c7967656e657261); \ 200 v3 ^= UINT64_C(0x7465646279746573); \ 201} while (0) 202 203PERL_STATIC_INLINE 204void S_perl_siphash_seed_state(const unsigned char * const seed_buf, unsigned char * state_buf) { 205 U64 *v= (U64*) state_buf; 206 SIPHASH_SEED_STATE(seed_buf, v[0],v[1],v[2],v[3]); 207} 208 209#define PERL_SIPHASH_FNC(FNC,SIP_ROUNDS,SIP_FINAL_ROUNDS) \ 210PERL_STATIC_INLINE U64 \ 211FNC ## _with_state_64 \ 212 (const unsigned char * const state, const unsigned char *in, const STRLEN inlen) \ 213{ \ 214 const int left = inlen & 7; \ 215 const U8 *end = in + inlen - left; \ 216 \ 217 U64 b = ( ( U64 )(inlen) ) << 56; \ 218 U64 m; \ 219 U64 v0 = U8TO64_LE(state); \ 220 U64 v1 = U8TO64_LE(state+8); \ 221 U64 v2 = U8TO64_LE(state+16); \ 222 U64 v3 = U8TO64_LE(state+24); \ 223 \ 224 for ( ; in != end; in += 8 ) \ 225 { \ 226 m = U8TO64_LE( in ); \ 227 v3 ^= m; \ 228 \ 229 SIP_ROUNDS; \ 230 \ 231 v0 ^= m; \ 232 } \ 233 \ 234 switch( left ) \ 235 { \ 236 case 7: b |= ( ( U64 )in[ 6] ) << 48; /*FALLTHROUGH*/ \ 237 case 6: b |= ( ( U64 )in[ 5] ) << 40; /*FALLTHROUGH*/ \ 238 case 5: b |= ( ( U64 )in[ 4] ) << 32; /*FALLTHROUGH*/ \ 239 case 4: b |= ( ( U64 )in[ 3] ) << 24; /*FALLTHROUGH*/ \ 240 case 3: b |= ( ( U64 )in[ 2] ) << 16; /*FALLTHROUGH*/ \ 241 case 2: b |= ( ( U64 )in[ 1] ) << 8; /*FALLTHROUGH*/ \ 242 case 1: b |= ( ( U64 )in[ 0] ); break; \ 243 case 0: break; \ 244 } \ 245 \ 246 v3 ^= b; \ 247 \ 248 SIP_ROUNDS; \ 249 \ 250 v0 ^= b; \ 251 \ 252 v2 ^= 0xff; \ 253 \ 254 SIP_FINAL_ROUNDS \ 255 \ 256 b = v0 ^ v1 ^ v2 ^ v3; \ 257 return b; \ 258} \ 259 \ 260PERL_STATIC_INLINE U32 \ 261FNC ## _with_state \ 262 (const unsigned char * const state, const unsigned char *in, const STRLEN inlen) \ 263{ \ 264 union { \ 265 U64 h64; \ 266 U32 h32[2]; \ 267 } h; \ 268 h.h64= FNC ## _with_state_64(state,in,inlen); \ 269 return h.h32[0] ^ h.h32[1]; \ 270} \ 271 \ 272 \ 273PERL_STATIC_INLINE U32 \ 274FNC (const unsigned char * const seed, const unsigned char *in, const STRLEN inlen) \ 275{ \ 276 U64 state[4]; \ 277 SIPHASH_SEED_STATE(seed,state[0],state[1],state[2],state[3]); \ 278 return FNC ## _with_state((U8*)state,in,inlen); \ 279} 280 281 282PERL_SIPHASH_FNC( 283 S_perl_hash_siphash_1_3 284 ,SIPROUND; 285 ,SIPROUND;SIPROUND;SIPROUND; 286) 287 288PERL_SIPHASH_FNC( 289 S_perl_hash_siphash_2_4 290 ,SIPROUND;SIPROUND; 291 ,SIPROUND;SIPROUND;SIPROUND;SIPROUND; 292) 293 294#endif /* defined(CAN64BITHASH) */ 295 296 297PERL_STATIC_INLINE U32 298S_perl_hash_with_seed(const U8 * seed, const U8 *str, STRLEN len) { 299 __PERL_HASH_WORD_TYPE state[PERL_HASH_STATE_WORDS]; 300 _PERL_HASH_SEED_STATE(seed,(U8*)state); 301 return _PERL_HASH_WITH_STATE((U8*)state,str,len); 302} 303 304#endif /*compile once*/ 305 306/* 307 * ex: set ts=8 sts=4 sw=4 et: 308 */ 309