chiark - git - mdw - mLib/blob - unihash.h

   1 /* -*-c-*-
   2  *
   3  * $Id: unihash.h,v 1.1 2003/10/12 14:43:24 mdw Exp $
   4  *
   5  * Simple and efficient universal hashing for hashtables
   6  *
   7  * (c) 2003 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of the mLib utilities library.
  13  *
  14  * mLib is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * mLib is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with mLib; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: unihash.h,v $
  33  * Revision 1.1  2003/10/12 14:43:24  mdw
  34  * Universal hashing.
  35  *
  36  */
  37
  38 #ifndef MLIB_UNIHASH_H
  39 #define MLIB_UNIHASH_H
  40
  41 #ifdef __cplusplus
  42   extern "C" {
  43 #endif
  44
  45
  46 /*----- Concept -----------------------------------------------------------*
  47  *
  48  * Let %$\gf{q}$% be a finite field.  Choose an arbitrary %$k \inr \gf{q}$%.
  49  * Let %$M$% be a message.  Injectively pad %$M$% and split it into blocks
  50  * $m_{n-1}, m_{n-2}, \ldots, m_2, m_1, m_0$% in %$\gf{q}%.
  51  * Then we compute
  52  *
  53  *   %$H_k(M) = k^{n+1} \sum_{0\le i<n} m_i k^{i+1}.$%
  54  *
  55  * Note that %$H_0(M) = 0$% for all messages %$M$%.
  56  *
  57  * If we deal with messages at most %$\ell$% blocks long then %$H_k(\cdot)$%
  58  * is %$(\ell + 1)/q$%-almost universal.  Moreover, if %$q = 2^f$% then
  59  * %$H_k(\cdot)$% is %$(\ell + 1)/q$%-almost XOR-universal.
  60  *
  61  * Proof.  Let %$A$% and %$B$% be two messages, represented by
  62  * %$a_{n-1}, \ldots, a_0$% and %$b_{m-1}, \ldots, b_0$% respectively; and
  63  * choose any %$\delta \in \gf{q}$%.  We must bound the probability that
  64  *
  65  * %$k^{n+1} + a_{n-1} k^{n} + \cdots + a_1 k^2 + a_0 k - {}$%
  66  *   %$k^{m+1} - b_{m-1} k^{m} - \cdots - b_1 k^2 - b_0 k = \delta$%.
  67  *
  68  * Firstly, we claim that if %$A$% and %$B$% are distinct, there is some
  69  * nonzero coefficient of %$k$%.  For if %$n \ne m$% then, without loss of
  70  * generality, let %$n > m$%, and hence the coefficient of %$k_n$% is
  71  * nonzero.  Alternatively, if %$n = m$% then there must be some
  72  * %$i \in \{ 0, \ldots, n - 1 \}$% with %$a_i \ne b_i$%, for otherwise the
  73  * messages would be identical; but then the coefficient of %$k^{i+1}$% is
  74  * %$a_i - b_i \ne 0$%.
  75  *
  76  * Hence we have a polynomial equation with degree at most %$\ell + 1$%;
  77  * there must be at most %$\ell + 1$% solutions for %$k$%; but we choose
  78  * %$k$% at random from a set of %$q$%; so the equation is true with
  79  * probability at most %$(\ell + 1)/q$%.
  80  *
  81  * This function can be used as a simple MAC with provable security against
  82  * computationally unbounded adversaries.  Simply XOR the hash with a random
  83  * string indexed from a large random pad by some nonce sent with the
  84  * message.  The probability of a forgery attempt being successful is then
  85  * %$(\ell + 1)/2^t$%, where %$t$% is the tag length and %$n$% is the longest
  86  * message permitted.
  87  */
  88
  89 /*----- Practicalities ----------------------------------------------------*
  90  *
  91  * We work in %$\gf{2^32}$%, represented as a field of polynomials modulo
  92  * %$\{104c11db7}_x$% (this is the standard CRC-32 polynomial).  Our blocks
  93  * are bytes.  We append a big-endian byte length.
  94  *
  95  * The choice of a 32-bit hash is made for pragmatic reasons: we're never
  96  * likely to actually want all 32 bits for a real hashtable anyway.  The
  97  * truncation result is needed to keep us afloat with smaller tables.
  98  *
  99  * We compute hashes using a slightly unrolled version of Horner's rule,
 100  * using the recurrence:
 101  *
 102  *   %$a_{i+b} = (a_i + m_i) k^b + m_{i+1} k^{b-1} + \cdots + m_{i+b-1} k$%
 103  *
 104  * which involves one full-width multiply and %$b - 1$% one-byte multiplies;
 105  * the latter may be efficiently computed using a table lookup.  Start with
 106  * %$a_0 = k$%.
 107  *
 108  * We precompute tables %$S[\cdot][\cdot][\cdot]$%, where
 109  *
 110  *   %$S[u][v][w] = k^{u+1} x^{8v} w$%
 111  *     for %$0 \le u < b$%, %$0 \le v < 4$%, %$0 \le w < 256)$%.
 112  *
 113  * A one-byte multiply is one lookup; a full-width multiply is four lookups
 114  * and three XORs.  The processing required is then %$b + 3$% lookups and
 115  * %$b + 3$% XORs per batch, or %$(b + 3)/b$% lookups and XORs per byte, at
 116  * the expense of %$4 b$% kilobytes of tables.  This compares relatively
 117  * favorably with CRC32.  Indeed, in tests, this implementation with $b = 4$%
 118  * is faster than a 32-bit CRC.
 119  */
 120
 121 /*----- Header files ------------------------------------------------------*/
 122
 123 #include <stddef.h>
 124
 125 #ifndef MLIB_BITS_H
 126 #  include "bits.h"
 127 #endif
 128
 129 /*----- Data structures ---------------------------------------------------*/
 130
 131 #define UNIHASH_NBATCH 4
 132 #define UNIHASH_POLY 0x04c11db7         /* From CRC32 */
 133
 134 typedef struct unihash_info {
 135   uint32 s[UNIHASH_NBATCH][4][256];     /* S-tables as described */
 136 } unihash_info;
 137
 138 /*----- Functions provided ------------------------------------------------*/
 139
 140 /* --- @unihash_setkey@ --- *
 141  *
 142  * Arguments:   @unihash_info *i@ = where to store the precomputed tables
 143  *              @uint32 k@ = the key to set, randomly chosen
 144  *
 145  * Returns:     ---
 146  *
 147  * Use:         Calculates the tables required for efficient hashing.
 148  */
 149
 150 extern void unihash_setkey(unihash_info */*i*/, uint32 /*k*/);
 151
 152 /* --- @unihash_hash@ --- *
 153  *
 154  * Arguments:   @const unihash_info *i@ = pointer to precomputed table
 155  *              @uint32 a@ = @UNIHASH_INIT(i)@ or value from previous call
 156  *              @const void *p@ = pointer to data to hash
 157  *              @size_t sz@ = size of the data
 158  *
 159  * Returns:     ---
 160  *
 161  * Use:         Hashes data.  Call this as many times as needed.
 162  */
 163
 164 #define UNIHASH_INIT(i) ((i)->s[0][0][1]) /* %$k$% */
 165
 166 extern uint32 unihash_hash(const unihash_info */*i*/, uint32 /*a*/,
 167                            const void */*p*/, size_t /*sz*/);
 168
 169 /* --- @unihash@ --- *
 170  *
 171  * Arguments:   @const unihash_info *i@ = precomputed tables
 172  *              @const void *p@ = pointer to data to hash
 173  *              @size_t sz@ = size of the data
 174  *
 175  * Returns:     The hash value computed.
 176  *
 177  * Use:         All-in-one hashing function.  No faster than using the
 178  *              separate calls, but more convenient.
 179  */
 180
 181 #define UNIHASH(i, p, sz) (unihash_hash((i), UNIHASH_INIT((i)), (p), (sz)))
 182
 183 extern uint32 unihash(const unihash_info */*i*/,
 184                       const void */*p*/, size_t /*sz*/);
 185
 186 /*----- That's all, folks -------------------------------------------------*/
 187
 188 #ifdef __cplusplus
 189   }
 190 #endif
 191
 192 #endif