GCS  0.2.3
gu_fnv.h
Go to the documentation of this file.
1 // Copyright (C) 2012 Codership Oy <info@codership.com>
2 
23 #ifndef _gu_fnv_h_
24 #define _gu_fnv_h_
25 
26 #include "gu_int128.h"
27 
28 #include <stdio.h>
29 #include <stdint.h>
30 #include <inttypes.h>
31 #include <stdlib.h> // ssize_t
32 #include <assert.h>
33 
34 #define GU_FNV32_PRIME 16777619UL
35 #define GU_FNV32_SEED 2166136261UL
36 
37 #if !defined(GU_FNVBITSHIFT_OPTIMIZATION)
38 # define GU_FNV32_MUL(_x) _x *= GU_FNV32_PRIME
39 #else /* GU_FNVBITSHIFT_OPTIMIZATION */
40 # define GU_FNV32_MUL(_x) \
41  _x += (_x << 1) + (_x << 4) + (_x << 7) + (_x << 8) + (_x << 24)
42 #endif /* GU_FNVBITSHIFT_OPTIMIZATION */
43 
44 #if !defined(GU_FNV_NORMAL)
45 # define GU_FNV32_ITERATION(_s,_b) _s ^= _b; GU_FNV32_MUL(_s);
46 #else
47 # define GU_FNV32_ITERATION(_s,_b) GU_FNV32_MUL(_s); _s ^= _b;
48 #endif
49 
50 static GU_FORCE_INLINE void
51 gu_fnv32a_internal (const void* buf, ssize_t const len, uint32_t* seed)
52 {
53  const uint8_t* bp = (const uint8_t*)buf;
54  const uint8_t* const be = bp + len;
55 
56  while (bp + 2 <= be)
57  {
58  GU_FNV32_ITERATION(*seed,*bp++);
59  GU_FNV32_ITERATION(*seed,*bp++);
60  }
61 
62  if (bp < be)
63  {
64  GU_FNV32_ITERATION(*seed,*bp++);
65  }
66 
67  assert(be == bp);
68 }
69 
70 #define GU_FNV64_PRIME 1099511628211ULL
71 #define GU_FNV64_SEED 14695981039346656037ULL
72 
73 #if !defined(GU_FNVBITSHIFT_OPTIMIZATION)
74 # define GU_FNV64_MUL(_x) _x *= GU_FNV64_PRIME
75 #else /* GU_FNVBITSHIFT_OPTIMIZATION */
76 # define GU_FNV64_MUL(_x) \
77  _x +=(_x << 1) + (_x << 4) + (_x << 5) + (_x << 7) + (_x << 8) + (_x << 40);
78 #endif /* GU_FNVBITSHIFT_OPTIMIZATION */
79 
80 #if !defined(GU_FNV_NORMAL)
81 # define GU_FNV64_ITERATION(_s,_b) _s ^= _b; GU_FNV64_MUL(_s);
82 #else
83 # define GU_FNV64_ITERATION(_s,_b) GU_FNV64_MUL(_s); _s ^= _b;
84 #endif
85 
86 static GU_FORCE_INLINE void
87 gu_fnv64a_internal (const void* buf, ssize_t const len, uint64_t* seed)
88 {
89  const uint8_t* bp = (const uint8_t*)buf;
90  const uint8_t* const be = bp + len;
91 
92  while (bp + 2 <= be)
93  {
94  GU_FNV64_ITERATION(*seed,*bp++);
95  GU_FNV64_ITERATION(*seed,*bp++);
96  }
97 
98  if (bp < be)
99  {
100  GU_FNV64_ITERATION(*seed,*bp++);
101  }
102 
103  assert(be == bp);
104 }
105 
106 static gu_uint128_t const
107 GU_SET128(GU_FNV128_PRIME, 0x0000000001000000ULL, 0x000000000000013BULL);
108 
109 static gu_uint128_t const
110 GU_SET128(GU_FNV128_SEED, 0x6C62272E07BB0142ULL, 0x62B821756295C58DULL);
111 
112 #if defined(__SIZEOF_INT128__)
113 
114 #define GU_FNV128_XOR(_s,_b) _s ^= _b
115 
116 #if !defined(GU_FNVBITSHIFT_OPTIMIZATION)
117 # define GU_FNV128_MUL(_x) _x *= GU_FNV128_PRIME
118 #else /* GU_FNVBITSHIFT_OPTIMIZATION */
119 # define GU_FNV128_MUL(_x) \
120  _x +=(_x << 1) + (_x << 3) + (_x << 4) + (_x << 5) + (_x << 8) + (_x << 88);
121 #endif /* GU_FNVBITSHIFT_OPTIMIZATION */
122 
123 #else /* ! __SIZEOF_INT128__ */
124 
125 #define GU_FNV128_XOR(_s,_b) (_s).u32[GU_32LO] ^= _b
126 
127 #if defined(GU_FNV128_FULL_MULTIPLICATION)
128 # define GU_FNV128_MUL(_x) GU_MUL128_INPLACE(_x, GU_FNV128_PRIME)
129 #else /* no FULL_MULTIPLICATION */
130 # define GU_FNV128_MUL(_x) { \
131  uint32_t carry = \
132  (((_x).u64[GU_64LO] & 0x00000000ffffffffULL) * 0x013b) >> 32; \
133  carry = (((_x).u64[GU_64LO] >> 32) * 0x013b + carry) >> 32; \
134  (_x).u64[GU_64HI] *= 0x013b; \
135  (_x).u64[GU_64HI] += ((_x).u64[GU_64LO] << 24) + carry; \
136  (_x).u64[GU_64LO] *= 0x013b; \
137  }
138 #endif /* FULL_MULTIPLICATION */
139 
140 #endif /* ! __SIZEOF_INT128__ */
141 
142 
143 #if !defined(GU_FNV_NORMAL)
144 # define GU_FNV128_ITERATION(_s,_b) GU_FNV128_XOR(_s,_b); GU_FNV128_MUL(_s);
145 #else
146 # define GU_FNV128_ITERATION(_s,_b) GU_FNV128_MUL(_s); GU_FNV128_XOR(_s,_b);
147 #endif
148 
149 inline static void
150 gu_fnv128a_internal (const void* buf, ssize_t const len, gu_uint128_t* seed)
151 {
152  const uint8_t* bp = (const uint8_t*)buf;
153  const uint8_t* const be = bp + len;
154 
155  /* this manual loop unrolling seems to be essential */
156  while (bp + 8 <= be)
157  {
158  GU_FNV128_ITERATION(*seed, *bp++);
159  GU_FNV128_ITERATION(*seed, *bp++);
160  GU_FNV128_ITERATION(*seed, *bp++);
161  GU_FNV128_ITERATION(*seed, *bp++);
162  GU_FNV128_ITERATION(*seed, *bp++);
163  GU_FNV128_ITERATION(*seed, *bp++);
164  GU_FNV128_ITERATION(*seed, *bp++);
165  GU_FNV128_ITERATION(*seed, *bp++);
166  }
167 
168  if (bp + 4 <= be)
169  {
170  GU_FNV128_ITERATION(*seed, *bp++);
171  GU_FNV128_ITERATION(*seed, *bp++);
172  GU_FNV128_ITERATION(*seed, *bp++);
173  GU_FNV128_ITERATION(*seed, *bp++);
174  }
175 
176  if (bp + 2 <= be)
177  {
178  GU_FNV128_ITERATION(*seed, *bp++);
179  GU_FNV128_ITERATION(*seed, *bp++);
180  }
181 
182  if (bp < be)
183  {
184  GU_FNV128_ITERATION(*seed, *bp++);
185  }
186 
187  assert(be == bp);
188 }
189 
190 #endif /* _gu_fnv_h_ */
191 
Definition: gu_int128.h:105