chiark / gitweb /
Version bump.
[mLib] / unihash.c
1 /* -*-c-*-
2  *
3  * $Id: unihash.c,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.c,v $
33  * Revision 1.1  2003/10/12 14:43:24  mdw
34  * Universal hashing.
35  *
36  */
37
38 /*----- Header files ------------------------------------------------------*/
39
40 #include <assert.h>
41 #include <stdlib.h>
42
43 #include "unihash.h"
44
45 /*----- Main code ---------------------------------------------------------*/
46
47 /* --- @unihash_setkey@ --- *
48  *
49  * Arguments:   @unihash_info *i@ = where to store the precomputed tables
50  *              @uint32 k@ = the key to set, randomly chosen
51  *
52  * Returns:     ---
53  *
54  * Use:         Calculates the tables required for efficient hashing.
55  */
56
57 static uint32 mul(uint32 x, uint32 y)
58 {
59   uint32 z = 0;
60   while (y) {
61     if (y & 1) z ^= x;
62     if (x & (1 << 31))
63       x = U32(x << 1) ^ UNIHASH_POLY;
64     else
65       x = U32(x << 1);
66     y = U32(y >> 1);
67   }
68   return (z);
69 }
70
71 void unihash_setkey(unihash_info *i, uint32 k)
72 {
73   size_t a;
74   size_t b;
75   uint32 x = 1;
76
77   for (a = 0; a < UNIHASH_NBATCH; a++) {
78     x = mul(x, k);
79     for (b = 0; b < 256; b++) {
80       i->s[a][0][b] = mul(x, b <<  0);
81       i->s[a][1][b] = mul(x, b <<  8);
82       i->s[a][2][b] = mul(x, b << 16);
83       i->s[a][3][b] = mul(x, b << 24);
84     }
85   }
86 }
87
88 /* --- @unihash_hash@ --- *
89  *
90  * Arguments:   @const unihash_info *i@ = pointer to precomputed table
91  *              @uint32 a@ = @i->[0][0][1]@ or value from previous call
92  *              @const void *p@ = pointer to data to hash
93  *              @size_t sz@ = size of the data
94  *
95  * Returns:     ---
96  *
97  * Use:         Hashes data.  Call this as many times as needed.  
98  */
99
100 uint32 unihash_hash(const unihash_info *i, uint32 a,
101                     const void *p, size_t sz)
102 {
103   const octet *pp = p;
104
105   assert(UNIHASH_NBATCH == 4);
106
107 #define FULLMULT(u, x)                                                  \
108   (i->s[u][0][U8((x) >>  0)] ^ i->s[u][1][U8((x) >>  8)] ^              \
109    i->s[u][2][U8((x) >> 16)] ^ i->s[u][3][U8((x) >> 24)]);
110
111 #define BYTEMULT(u, x) i->s[u][0][x]
112
113   /* --- Do the main bulk in batches of %$n$% bytes --- *
114    *
115    * We have %$a$% and %$m_{n-1}, \ldots, m_1, m_0$%; we want
116    *
117    * %$a' = (a + m_{n-1}) k^n + m_{n-2} k^{n-1} + \cdots + m_1 k^2 + m_0 k$%
118    */
119
120   while (sz >= UNIHASH_NBATCH) {
121     a ^= *pp++;
122     a = FULLMULT(3, a);
123     a ^= BYTEMULT(2, *pp++);
124     a ^= BYTEMULT(1, *pp++);
125     a ^= BYTEMULT(0, *pp++);
126   }
127
128   /* --- The tail end is a smaller batch --- */
129
130   switch (sz) {
131     case  3: a ^= *pp++; a = FULLMULT(2, a); goto batch_2;
132     case  2: a ^= *pp++; a = FULLMULT(1, a); goto batch_1;
133     case  1: a ^= *pp++; a = FULLMULT(0, a); goto batch_0;
134     batch_2: a ^= BYTEMULT(1, *pp++);
135     batch_1: a ^= BYTEMULT(0, *pp++);
136     batch_0: break;
137   }
138
139   return (a);
140 }
141
142 /* --- @unihash@ --- *
143  *
144  * Arguments:   @const unihash_info *i@ = precomputed tables
145  *              @const void *p@ = pointer to data to hash
146  *              @size_t sz@ = size of the data
147  *
148  * Returns:     The hash value computed.
149  *
150  * Use:         All-in-one hashing function.  No faster than using the
151  *              separate calls, but more convenient.
152  */
153
154 uint32 unihash(const unihash_info *i, const void *p, size_t sz)
155 {
156   return (UNIHASH(i, p, sz));
157 }
158
159 /*----- That's all, folks -------------------------------------------------*/