This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Import perl5321delta.pod
[perl5.git] / perl_siphash.h
1 /* This is SipHash by Jean-Philippe Aumasson and Daniel J. Bernstein.
2  * The authors claim it is relatively secure compared to the alternatives
3  * and that performance wise it is a suitable hash for languages like Perl.
4  * See:
5  *
6  * https://www.131002.net/siphash/
7  *
8  * This implementation seems to perform slightly slower than one-at-a-time for
9  * short keys, but degrades slower for longer keys. Murmur Hash outperforms it
10  * regardless of keys size.
11  *
12  * It is 64 bit only.
13  */
14
15 #ifdef CAN64BITHASH
16
17 #define SIPROUND            \
18   STMT_START {              \
19     v0 += v1; v1=ROTL64(v1,13); v1 ^= v0; v0=ROTL64(v0,32); \
20     v2 += v3; v3=ROTL64(v3,16); v3 ^= v2;     \
21     v0 += v3; v3=ROTL64(v3,21); v3 ^= v0;     \
22     v2 += v1; v1=ROTL64(v1,17); v1 ^= v2; v2=ROTL64(v2,32); \
23   } STMT_END
24
25 #define SIPHASH_SEED_STATE(key,v0,v1,v2,v3) \
26 do {                                    \
27     v0 = v2 = U8TO64_LE(key + 0);       \
28     v1 = v3 = U8TO64_LE(key + 8);       \
29   /* "somepseudorandomlygeneratedbytes" */  \
30     v0 ^= UINT64_C(0x736f6d6570736575);  \
31     v1 ^= UINT64_C(0x646f72616e646f6d);      \
32     v2 ^= UINT64_C(0x6c7967656e657261);      \
33     v3 ^= UINT64_C(0x7465646279746573);      \
34 } while (0)
35
36 PERL_STATIC_INLINE
37 void S_perl_siphash_seed_state(const unsigned char * const seed_buf, unsigned char * state_buf) {
38     U64 *v= (U64*) state_buf;
39     SIPHASH_SEED_STATE(seed_buf, v[0],v[1],v[2],v[3]);
40 }
41
42 #define PERL_SIPHASH_FNC(FNC,SIP_ROUNDS,SIP_FINAL_ROUNDS) \
43 PERL_STATIC_INLINE U64 \
44 FNC ## _with_state_64 \
45   (const unsigned char * const state, const unsigned char *in, const STRLEN inlen) \
46 {                                           \
47   const int left = inlen & 7;               \
48   const U8 *end = in + inlen - left;        \
49                                             \
50   U64 b = ( ( U64 )(inlen) ) << 56;         \
51   U64 m;                                    \
52   U64 v0 = U8TO64_LE(state);                \
53   U64 v1 = U8TO64_LE(state+8);              \
54   U64 v2 = U8TO64_LE(state+16);             \
55   U64 v3 = U8TO64_LE(state+24);             \
56                                             \
57   for ( ; in != end; in += 8 )              \
58   {                                         \
59     m = U8TO64_LE( in );                    \
60     v3 ^= m;                                \
61                                             \
62     SIP_ROUNDS;                             \
63                                             \
64     v0 ^= m;                                \
65   }                                         \
66                                             \
67   switch( left )                            \
68   {                                         \
69   case 7: b |= ( ( U64 )in[ 6] )  << 48; /*FALLTHROUGH*/    \
70   case 6: b |= ( ( U64 )in[ 5] )  << 40; /*FALLTHROUGH*/    \
71   case 5: b |= ( ( U64 )in[ 4] )  << 32; /*FALLTHROUGH*/    \
72   case 4: b |= ( ( U64 )in[ 3] )  << 24; /*FALLTHROUGH*/    \
73   case 3: b |= ( ( U64 )in[ 2] )  << 16; /*FALLTHROUGH*/    \
74   case 2: b |= ( ( U64 )in[ 1] )  <<  8; /*FALLTHROUGH*/    \
75   case 1: b |= ( ( U64 )in[ 0] ); break;    \
76   case 0: break;                            \
77   }                                         \
78                                             \
79   v3 ^= b;                                  \
80                                             \
81   SIP_ROUNDS;                               \
82                                             \
83   v0 ^= b;                                  \
84                                             \
85   v2 ^= 0xff;                               \
86                                             \
87   SIP_FINAL_ROUNDS                          \
88                                             \
89   b = v0 ^ v1 ^ v2  ^ v3;                   \
90   return b;                                 \
91 }                                           \
92                                             \
93 PERL_STATIC_INLINE U32                      \
94 FNC ## _with_state                          \
95   (const unsigned char * const state, const unsigned char *in, const STRLEN inlen) \
96 {                                           \
97     union {                                 \
98         U64 h64;                            \
99         U32 h32[2];                         \
100     } h;                                    \
101     h.h64= FNC ## _with_state_64(state,in,inlen); \
102     return h.h32[0] ^ h.h32[1];             \
103 }                                           \
104                                             \
105                                             \
106 PERL_STATIC_INLINE U32                      \
107 FNC (const unsigned char * const seed, const unsigned char *in, const STRLEN inlen) \
108 {                                                                   \
109     U64 state[4];                                                   \
110     SIPHASH_SEED_STATE(seed,state[0],state[1],state[2],state[3]);   \
111     return FNC ## _with_state((U8*)state,in,inlen);                 \
112 }
113
114
115 PERL_SIPHASH_FNC(
116     S_perl_hash_siphash_1_3
117     ,SIPROUND;
118     ,SIPROUND;SIPROUND;SIPROUND;
119 )
120
121 PERL_SIPHASH_FNC(
122     S_perl_hash_siphash_2_4
123     ,SIPROUND;SIPROUND;
124     ,SIPROUND;SIPROUND;SIPROUND;SIPROUND;
125 )
126
127 #endif /* defined(CAN64BITHASH) */