• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*-
2  * Copyright © 2011, 2014, 2015
3  *	mirabilos <m@mirbsd.org>
4  *
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.
10  *
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.
19  *-
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.
23  *
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).
33  *-
34  * Little quote gem:
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.
38  * -- Rasmus Lerdorf
39  */
40 
41 #ifndef SYSKERN_MIRHASH_H
42 #define SYSKERN_MIRHASH_H 1
43 #define SYSKERN_MIRHASH_BAFH
44 
45 #include <sys/types.h>
46 
47 __RCSID("$MirOS: src/bin/mksh/mirhash.h,v 1.6 2015/11/29 17:05:02 tg Exp $");
48 
49 /*-
50  * BAFH itself is defined by the following primitives:
51  *
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.
57  *
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.
62  *
63  * • BAFHror(eax,cl) evaluates to the unsigned 32-bit integer “eax”,
64  *   rotated right by “cl” ∈ [0; 31] (no casting, be careful!) where
65  *   “eax” must be uint32_t and “cl” an in-range integer.
66  *
67  * • BAFHFinish(ctx) avalanches the context around so every sub-byte
68  *   depends on all input octets; afterwards, the context variable’s
69  *   value is the hash output. BAFH does not use any padding, nor is
70  *   the input length added; this is due to the common use case (for
71  *   quick entropy distribution and use with a hashtable).
72  *   Warning: BAFHFinish uses the MixColumn algorithm of AES – which
73  *   is reversible (to avoid introducing funnels and reducing entro‐
74  *   py), so blinding may need to be employed for some uses, e.g. in
75  *   mksh, after a fork.
76  *
77  * The BAFHUpdateOctet and BAFHFinish are available in two flavours:
78  * suffixed with _reg (assumes the context is in a register) or _mem
79  * (which doesn’t).
80  *
81  * The following high-level macros (with _reg and _mem variants) are
82  * available:
83  *
84  * • BAFHUpdateMem(ctx,buf,len) adds a memory block to a context.
85  * • BAFHUpdateStr(ctx,buf) is equivalent to using len=strlen(buf).
86  * • BAFHHostMem(ctx,buf,len) calculates the hash of the memory buf‐
87  *   fer using the first 4 octets (mixed) for IV, as outlined above;
88  *   the result is endian-dependent; “ctx” assumed to be a register.
89  * • BAFHHostStr(ctx,buf) does the same for C strings.
90  *
91  * All macros may use ctx multiple times in their expansion, but all
92  * other arguments are always evaluated at most once except BAFHror.
93  *
94  * To stay portable, never use the BAFHHost*() macros (these are for
95  * host-local entropy shuffling), and encode numbers using ULEB128.
96  */
97 
98 #define BAFHInit(h) do {					\
99 	(h) = 0;						\
100 } while (/* CONSTCOND */ 0)
101 
102 #define BAFHUpdateOctet_reg(h,b) do {				\
103 	(h) += (uint8_t)(b);					\
104 	++(h);							\
105 	(h) += (h) << 10;					\
106 	(h) ^= (h) >> 6;					\
107 } while (/* CONSTCOND */ 0)
108 
109 #define BAFHUpdateOctet_mem(m,b) do {				\
110 	register uint32_t BAFH_h = (m);				\
111 								\
112 	BAFHUpdateOctet_reg(BAFH_h, (b));			\
113 	(m) = BAFH_h;						\
114 } while (/* CONSTCOND */ 0)
115 
116 #define BAFHror(eax,cl) (((eax) >> (cl)) | ((eax) << (32 - (cl))))
117 
118 #define BAFHFinish_reg(h) do {					\
119 	register uint32_t BAFHFinish_v;				\
120 								\
121 	BAFHFinish_v = ((h) >> 7) & 0x01010101U;		\
122 	BAFHFinish_v += BAFHFinish_v << 1;			\
123 	BAFHFinish_v += BAFHFinish_v << 3;			\
124 	BAFHFinish_v ^= ((h) << 1) & 0xFEFEFEFEU;		\
125 								\
126 	BAFHFinish_v ^= BAFHror(BAFHFinish_v, 8);		\
127 	BAFHFinish_v ^= ((h) = BAFHror((h), 8));		\
128 	BAFHFinish_v ^= ((h) = BAFHror((h), 8));		\
129 	(h) = BAFHror((h), 8) ^ BAFHFinish_v;			\
130 } while (/* CONSTCOND */ 0)
131 
132 #define BAFHFinish_mem(m) do {					\
133 	register uint32_t BAFHFinish_v, BAFH_h = (m);		\
134 								\
135 	BAFHFinish_v = (BAFH_h >> 7) & 0x01010101U;		\
136 	BAFHFinish_v += BAFHFinish_v << 1;			\
137 	BAFHFinish_v += BAFHFinish_v << 3;			\
138 	BAFHFinish_v ^= (BAFH_h << 1) & 0xFEFEFEFEU;		\
139 								\
140 	BAFHFinish_v ^= BAFHror(BAFHFinish_v, 8);		\
141 	BAFHFinish_v ^= (BAFH_h = BAFHror(BAFH_h, 8));		\
142 	BAFHFinish_v ^= (BAFH_h = BAFHror(BAFH_h, 8));		\
143 	(m) = BAFHror(BAFH_h, 8) ^ BAFHFinish_v;		\
144 } while (/* CONSTCOND */ 0)
145 
146 #define BAFHUpdateMem_reg(h,p,z) do {				\
147 	register const uint8_t *BAFHUpdate_p;			\
148 	register size_t BAFHUpdate_z = (z);			\
149 								\
150 	BAFHUpdate_p = (const void *)(p);			\
151 	while (BAFHUpdate_z--)					\
152 		BAFHUpdateOctet_reg((h), *BAFHUpdate_p++);	\
153 } while (/* CONSTCOND */ 0)
154 
155 /* meh should have named them _r/m but that’s not valid C */
156 #define BAFHUpdateMem_mem(m,p,z) do {				\
157 	register uint32_t BAFH_h = (m);				\
158 								\
159 	BAFHUpdateMem_reg(BAFH_h, (p), (z));			\
160 	(m) = BAFH_h;						\
161 } while (/* CONSTCOND */ 0)
162 
163 #define BAFHUpdateStr_reg(h,s) do {				\
164 	register const uint8_t *BAFHUpdate_s;			\
165 	register uint8_t BAFHUpdate_c;				\
166 								\
167 	BAFHUpdate_s = (const void *)(s);			\
168 	while ((BAFHUpdate_c = *BAFHUpdate_s++) != 0)		\
169 		BAFHUpdateOctet_reg((h), BAFHUpdate_c);		\
170 } while (/* CONSTCOND */ 0)
171 
172 #define BAFHUpdateStr_mem(m,s) do {				\
173 	register uint32_t BAFH_h = (m);				\
174 								\
175 	BAFHUpdateStr_reg(BAFH_h, (s));				\
176 	(m) = BAFH_h;						\
177 } while (/* CONSTCOND */ 0)
178 
179 #define BAFHHostMem(h,p,z) do {					\
180 	register const uint8_t *BAFHUpdate_p;			\
181 	register size_t BAFHUpdate_z = (z);			\
182 	size_t BAFHHost_z;					\
183 	union {							\
184 		uint8_t as_u8[4];				\
185 		uint32_t as_u32;				\
186 	} BAFHHost_v;						\
187 								\
188 	BAFHUpdate_p = (const void *)(p);			\
189 	BAFHHost_v.as_u32 = 0;					\
190 	BAFHHost_z = BAFHUpdate_z < 4 ? BAFHUpdate_z : 4;	\
191 	memcpy(BAFHHost_v.as_u8, BAFHUpdate_p, BAFHHost_z);	\
192 	BAFHUpdate_p += BAFHHost_z;				\
193 	BAFHUpdate_z -= BAFHHost_z;				\
194 	(h) = BAFHHost_v.as_u32;				\
195 	BAFHFinish_reg(h);					\
196 	while (BAFHUpdate_z--)					\
197 		BAFHUpdateOctet_reg((h), *BAFHUpdate_p++);	\
198 	BAFHFinish_reg(h);					\
199 } while (/* CONSTCOND */ 0)
200 
201 #define BAFHHostStr(h,s) do {					\
202 	register const uint8_t *BAFHUpdate_s;			\
203 	register uint8_t BAFHUpdate_c;				\
204 	union {							\
205 		uint8_t as_u8[4];				\
206 		uint32_t as_u32;				\
207 	} BAFHHost_v;						\
208 								\
209 	BAFHUpdate_s = (const void *)(s);			\
210 	BAFHHost_v.as_u32 = 0;					\
211 	if ((BAFHHost_v.as_u8[0] = *BAFHUpdate_s) != 0)		\
212 		++BAFHUpdate_s;					\
213 	if ((BAFHHost_v.as_u8[1] = *BAFHUpdate_s) != 0)		\
214 		++BAFHUpdate_s;					\
215 	if ((BAFHHost_v.as_u8[2] = *BAFHUpdate_s) != 0)		\
216 		++BAFHUpdate_s;					\
217 	if ((BAFHHost_v.as_u8[3] = *BAFHUpdate_s) != 0)		\
218 		++BAFHUpdate_s;					\
219 	(h) = BAFHHost_v.as_u32;				\
220 	BAFHFinish_reg(h);					\
221 	while ((BAFHUpdate_c = *BAFHUpdate_s++) != 0)		\
222 		BAFHUpdateOctet_reg((h), BAFHUpdate_c);		\
223 	BAFHFinish_reg(h);					\
224 } while (/* CONSTCOND */ 0)
225 
226 #endif
227