"Fossies" - the Fresh Open Source Software Archive

Member "install-tl-20200916/tlpkg/tlperl/lib/CORE/stadtx_hash.h" (10 Mar 2019, 10477 Bytes) of package /windows/misc/install-tl.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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 
    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
   30 
   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 
   46 #ifndef STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
   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
   53 #define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 1
   54 #endif
   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
   73 
   74 #ifndef U8TO32_LE
   75 #if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
   76 #define U8TO32_LE(ptr)  (*((const U32 *)(ptr)))
   77 #else
   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 )
   84 #endif
   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 
  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 ) {
  139     const U64 *seed= (const U64 *)seed_ch;
  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*/
  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);
  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 */
  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));
  173 }
  174 
  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)
  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;
  191     STRLEN len = key_len;
  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;
  201             /* FALLTHROUGH */
  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;
  207             /* FALLTHROUGH */
  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;
  213             /* FALLTHROUGH */
  214             case 0:
  215             default: break;
  216         }
  217         switch ( len & 0x7 ) {
  218             case 7: v0 += (U64)key[6] << 32;
  219             /* FALLTHROUGH */
  220             case 6: v1 += (U64)key[5] << 48;
  221             /* FALLTHROUGH */
  222             case 5: v0 += (U64)key[4] << 16;
  223             /* FALLTHROUGH */
  224             case 4: v1 += (U64)U8TO32_LE(key);
  225                     break;
  226             case 3: v0 += (U64)key[2] << 48;
  227             /* FALLTHROUGH */
  228             case 2: v1 += (U64)U8TO16_LE(key);
  229                     break;
  230             case 1: v0 += (U64)key[0];
  231             /* FALLTHROUGH */
  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;
  264             /* FALLTHROUGH */
  265             case 2: v1 += ((U64)U8TO64_LE(key) * STADTX_K3_U32); key += 8; v1= ROTL64(v1,63) ^ v2;
  266             /* FALLTHROUGH */
  267             case 1: v2 += ((U64)U8TO64_LE(key) * STADTX_K4_U32); key += 8; v2= ROTR64(v2,47) + v0;
  268             /* FALLTHROUGH */
  269             case 0: v3 = ROTR64(v3,11) - v1;
  270             /* FALLTHROUGH */
  271         }
  272         v0 ^= (len+1) * STADTX_K3_U64;
  273         switch ( len & 0x7 ) {
  274             case 7: v1 += (U64)key[6];
  275             /* FALLTHROUGH */
  276             case 6: v2 += (U64)U8TO16_LE(key+4);
  277                     v3 += (U64)U8TO32_LE(key);
  278                     break;
  279             case 5: v1 += (U64)key[4];
  280             /* FALLTHROUGH */
  281             case 4: v2 += (U64)U8TO32_LE(key);
  282                     break;
  283             case 3: v3 += (U64)key[2];
  284             /* FALLTHROUGH */
  285             case 2: v1 += (U64)U8TO16_LE(key);
  286                     break;
  287             case 1: v2 += (U64)key[0];
  288             /* FALLTHROUGH */
  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