src/mirhash.h

   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