2 * Copyright © 2011, 2014
3 * Thorsten Glaser <tg@mirbsd.org>
5 * Provided that these terms and disclaimer and all copyright notices
6 * are retained or reproduced in an accompanying document, permission
7 * is granted to deal in this work without restriction, including un‐
8 * limited rights to use, publicly perform, distribute, sell, modify,
9 * merge, give away, or sublicence.
11 * This work is provided “AS IS” and WITHOUT WARRANTY of any kind, to
12 * the utmost extent permitted by applicable law, neither express nor
13 * implied; without malicious intent or gross negligence. In no event
14 * may a licensor, author or contributor be held liable for indirect,
15 * direct, other damage, loss, or other issues arising in any way out
16 * of dealing in the work, even if advised of the possibility of such
17 * damage or existence of a defect, except proven that it results out
18 * of said person’s immediate fault when using the work as intended.
20 * This file provides BAFH (Better Avalanche for the Jenkins Hash) as
21 * inline macro bodies that operate on “register uint32_t” variables,
22 * with variants that use their local intermediate registers.
24 * Usage note for BAFH with entropy distribution: input up to 4 bytes
25 * is best combined into a 32-bit unsigned integer, which is then run
26 * through BAFHFinish_reg for mixing and then used as context instead
27 * of 0. Longer input should be handled the same: take the first four
28 * bytes as IV after mixing then add subsequent bytes the same way.
29 * This needs counting input bytes and is endian-dependent, thus not,
30 * for speed reasons, specified for the regular stable hash, but very
31 * much recommended if the actual output value may differ across runs
32 * (so is using a random value instead of 0 for the IV).
35 * We are looking into it. Changing the core
36 * hash function in PHP isn't a trivial change
37 * and will take us some time.
41 #ifndef SYSKERN_MIRHASH_H
42 #define SYSKERN_MIRHASH_H 1
43 #define SYSKERN_MIRHASH_BAFH
45 #include <sys/types.h>
47 __RCSID("$MirOS: src/bin/mksh/mirhash.h,v 1.3 2014/10/02 19:34:06 tg Exp $");
50 * BAFH itself is defined by the following primitives:
52 * • BAFHInit(ctx) initialises the hash context, which consists of a
53 * sole 32-bit unsigned integer (ideally in a register), to 0.
54 * It is possible to use any initial value out of [0; 2³²[ – which
55 * is, in fact, recommended if using BAFH for entropy distribution
56 * – but for a regular stable hash, the IV 0 is needed.
58 * • BAFHUpdateOctet(ctx,val) compresses the unsigned 8-bit quantity
59 * into the hash context. The algorithm used is Jenkins’ one-at-a-
60 * time, except that an additional constant 1 is added so that, if
61 * the context is (still) zero, adding a NUL byte is not ignored.
63 * • BAFHror(eax,cl) evaluates to the unsigned 32-bit integer “eax”,
64 * rotated right by “cl” ∈ [0;31]; no casting, be careful!
66 * • BAFHFinish(ctx) avalanches the context around so every sub-byte
67 * depends on all input octets; afterwards, the context variable’s
68 * value is the hash output. BAFH does not use any padding, nor is
69 * the input length added; this is due to the common use case (for
70 * quick entropy distribution and use with a hashtable).
71 * Warning: BAFHFinish uses the MixColumn algorithm of AES – which
72 * is reversible (to avoid introducing funnels and reducing entro‐
73 * py), so blinding may need to be employed for some uses, e.g. in
76 * The BAFHUpdateOctet and BAFHFinish are available in two flavours:
77 * suffixed with _reg (assumes the context is in a register) or _mem
80 * The following high-level macros (with _reg and _mem variants) are
83 * • BAFHUpdateMem(ctx,buf,len) adds a memory block to a context.
84 * • BAFHUpdateStr(ctx,buf) is equivalent to using len=strlen(buf).
85 * • BAFHHostMem(ctx,buf,len) calculates the hash of the memory buf‐
86 * fer using the first 4 octets (mixed) for IV, as outlined above;
87 * the result is endian-dependent; “ctx” assumed to be a register.
88 * • BAFHHostStr(ctx,buf) does the same for C strings.
90 * All macros may use ctx multiple times in their expansion, but all
91 * other arguments are always evaluated at most once.
93 * To stay portable, never use the BAFHHost*() macros (these are for
94 * host-local entropy shuffling), and encode numbers using ULEB128.
97 #define BAFHInit(h) do { \
99 } while (/* CONSTCOND */ 0)
101 #define BAFHUpdateOctet_reg(h,b) do { \
102 (h) += (uint8_t)(b); \
106 } while (/* CONSTCOND */ 0)
108 #define BAFHUpdateOctet_mem(m,b) do { \
109 register uint32_t BAFH_h = (m); \
111 BAFHUpdateOctet_reg(BAFH_h, (b)); \
113 } while (/* CONSTCOND */ 0)
115 #define BAFHror(eax,cl) (((eax) >> (cl)) | ((eax) << (32 - (cl))))
117 #define BAFHFinish_reg(h) do { \
118 register uint32_t BAFHFinish_v; \
120 BAFHFinish_v = ((h) >> 7) & 0x01010101U; \
121 BAFHFinish_v += BAFHFinish_v << 1; \
122 BAFHFinish_v += BAFHFinish_v << 3; \
123 BAFHFinish_v ^= ((h) << 1) & 0xFEFEFEFEU; \
125 BAFHFinish_v ^= BAFHror(BAFHFinish_v, 8); \
126 BAFHFinish_v ^= ((h) = BAFHror((h), 8)); \
127 BAFHFinish_v ^= ((h) = BAFHror((h), 8)); \
128 (h) = BAFHror((h), 8) ^ BAFHFinish_v; \
129 } while (/* CONSTCOND */ 0)
131 #define BAFHFinish_mem(m) do { \
132 register uint32_t BAFHFinish_v, BAFH_h = (m); \
134 BAFHFinish_v = (BAFH_h >> 7) & 0x01010101U; \
135 BAFHFinish_v += BAFHFinish_v << 1; \
136 BAFHFinish_v += BAFHFinish_v << 3; \
137 BAFHFinish_v ^= (BAFH_h << 1) & 0xFEFEFEFEU; \
139 BAFHFinish_v ^= BAFHror(BAFHFinish_v, 8); \
140 BAFHFinish_v ^= (BAFH_h = BAFHror(BAFH_h, 8)); \
141 BAFHFinish_v ^= (BAFH_h = BAFHror(BAFH_h, 8)); \
142 (m) = BAFHror(BAFH_h, 8) ^ BAFHFinish_v; \
143 } while (/* CONSTCOND */ 0)
145 #define BAFHUpdateMem_reg(h,p,z) do { \
146 register const uint8_t *BAFHUpdate_p; \
147 register size_t BAFHUpdate_z = (z); \
149 BAFHUpdate_p = (const void *)(p); \
150 while (BAFHUpdate_z--) \
151 BAFHUpdateOctet_reg((h), *BAFHUpdate_p++); \
152 } while (/* CONSTCOND */ 0)
154 /* meh should have named them _r/m but that’s not valid C */
155 #define BAFHUpdateMem_mem(m,p,z) do { \
156 register uint32_t BAFH_h = (m); \
158 BAFHUpdateMem_reg(BAFH_h, (p), (z)); \
160 } while (/* CONSTCOND */ 0)
162 #define BAFHUpdateStr_reg(h,s) do { \
163 register const uint8_t *BAFHUpdate_s; \
164 register uint8_t BAFHUpdate_c; \
166 BAFHUpdate_s = (const void *)(s); \
167 while ((BAFHUpdate_c = *BAFHUpdate_s++) != 0) \
168 BAFHUpdateOctet_reg((h), BAFHUpdate_c); \
169 } while (/* CONSTCOND */ 0)
171 #define BAFHUpdateStr_mem(m,s) do { \
172 register uint32_t BAFH_h = (m); \
174 BAFHUpdateStr_reg(BAFH_h, (s)); \
176 } while (/* CONSTCOND */ 0)
178 #define BAFHHostMem(h,p,z) do { \
179 register const uint8_t *BAFHUpdate_p; \
180 register size_t BAFHUpdate_z = (z); \
187 BAFHUpdate_p = (const void *)(p); \
188 BAFHHost_v.as_u32 = 0; \
189 BAFHHost_z = BAFHUpdate_z < 4 ? BAFHUpdate_z : 4; \
190 memcpy(BAFHHost_v.as_u8, BAFHUpdate_p, BAFHHost_z); \
191 BAFHUpdate_p += BAFHHost_z; \
192 BAFHUpdate_z -= BAFHHost_z; \
193 (h) = BAFHHost_v.as_u32; \
195 while (BAFHUpdate_z--) \
196 BAFHUpdateOctet_reg((h), *BAFHUpdate_p++); \
198 } while (/* CONSTCOND */ 0)
200 #define BAFHHostStr(h,s) do { \
201 register const uint8_t *BAFHUpdate_s; \
202 register uint8_t BAFHUpdate_c; \
208 BAFHUpdate_s = (const void *)(s); \
209 if ((BAFHHost_v.as_u8[0] = *BAFHUpdate_s) != 0) \
211 if ((BAFHHost_v.as_u8[1] = *BAFHUpdate_s) != 0) \
213 if ((BAFHHost_v.as_u8[2] = *BAFHUpdate_s) != 0) \
215 if ((BAFHHost_v.as_u8[3] = *BAFHUpdate_s) != 0) \
217 (h) = BAFHHost_v.as_u32; \
219 while ((BAFHUpdate_c = *BAFHUpdate_s++) != 0) \
220 BAFHUpdateOctet_reg((h), BAFHUpdate_c); \
222 } while (/* CONSTCOND */ 0)