+++ /dev/null
-/* -*-c-*-
- *
- * Simple and efficient universal hashing for hashtables
- *
- * (c) 2003 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of the mLib utilities library.
- *
- * mLib is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Library General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or (at your option) any later version.
- *
- * mLib is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with mLib; if not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
- */
-
-/*----- Header files ------------------------------------------------------*/
-
-#include <assert.h>
-#include <stdlib.h>
-
-#include "unihash.h"
-
-/*----- Main code ---------------------------------------------------------*/
-
-/* --- @unihash_setkey@ --- *
- *
- * Arguments: @unihash_info *i@ = where to store the precomputed tables
- * @uint32 k@ = the key to set, randomly chosen
- *
- * Returns: ---
- *
- * Use: Calculates the tables required for efficient hashing.
- */
-
-static uint32 mul(uint32 x, uint32 y)
-{
- uint32 z = 0;
- while (y) {
- if (y & 1) z ^= x;
- if (x & (1 << 31))
- x = U32(x << 1) ^ UNIHASH_POLY;
- else
- x = U32(x << 1);
- y = U32(y >> 1);
- }
- return (z);
-}
-
-void unihash_setkey(unihash_info *i, uint32 k)
-{
- size_t a;
- size_t b;
- uint32 x = 1;
-
- for (a = 0; a < UNIHASH_NBATCH; a++) {
- x = mul(x, k);
- for (b = 0; b < 256; b++) {
- i->s[a][0][b] = mul(x, b << 0);
- i->s[a][1][b] = mul(x, b << 8);
- i->s[a][2][b] = mul(x, b << 16);
- i->s[a][3][b] = mul(x, b << 24);
- }
- }
-}
-
-/* --- @unihash_hash@ --- *
- *
- * Arguments: @const unihash_info *i@ = pointer to precomputed table
- * @uint32 a@ = @i->[0][0][1]@ or value from previous call
- * @const void *p@ = pointer to data to hash
- * @size_t sz@ = size of the data
- *
- * Returns: Hash of data so far.
- *
- * Use: Hashes data. Call this as many times as needed.
- */
-
-uint32 unihash_hash(const unihash_info *i, uint32 a,
- const void *p, size_t sz)
-{
- const octet *pp = p;
-
- assert(UNIHASH_NBATCH == 4);
-
-#define FULLMULT(u, x) \
- (i->s[u][0][U8((x) >> 0)] ^ i->s[u][1][U8((x) >> 8)] ^ \
- i->s[u][2][U8((x) >> 16)] ^ i->s[u][3][U8((x) >> 24)]);
-
-#define BYTEMULT(u, x) i->s[u][0][x]
-
- /* --- Do the main bulk in batches of %$n$% bytes --- *
- *
- * We have %$a$% and %$m_{n-1}, \ldots, m_1, m_0$%; we want
- *
- * %$a' = (a + m_{n-1}) k^n + m_{n-2} k^{n-1} + \cdots + m_1 k^2 + m_0 k$%
- */
-
- while (sz >= UNIHASH_NBATCH) {
- a ^= *pp++;
- a = FULLMULT(3, a);
- a ^= BYTEMULT(2, *pp++);
- a ^= BYTEMULT(1, *pp++);
- a ^= BYTEMULT(0, *pp++);
- sz -= UNIHASH_NBATCH;
- }
-
- /* --- The tail end is a smaller batch --- */
-
- switch (sz) {
- case 3: a ^= *pp++; a = FULLMULT(2, a); goto batch_2;
- case 2: a ^= *pp++; a = FULLMULT(1, a); goto batch_1;
- case 1: a ^= *pp++; a = FULLMULT(0, a); goto batch_0;
- batch_2: a ^= BYTEMULT(1, *pp++);
- batch_1: a ^= BYTEMULT(0, *pp++);
- batch_0: break;
- }
-
- return (a);
-}
-
-/* --- @unihash@ --- *
- *
- * Arguments: @const unihash_info *i@ = precomputed tables
- * @const void *p@ = pointer to data to hash
- * @size_t sz@ = size of the data
- *
- * Returns: The hash value computed.
- *
- * Use: All-in-one hashing function. No faster than using the
- * separate calls, but more convenient.
- */
-
-uint32 unihash(const unihash_info *i, const void *p, size_t sz)
-{
- return (UNIHASH(i, p, sz));
-}
-
-/*----- Test rig ----------------------------------------------------------*/
-
-#ifdef TEST_RIG
-
-#include "testrig.h"
-
-static int verify(dstr *v)
-{
- unihash_info ui;
- uint32 k;
- uint32 h, hh;
- size_t n;
- int i, c;
- const char *p;
- int ok = 1;
-
- static const int step[] = { 0, 1, 5, 6, 7, 8, 23, -1 };
-
- /* --- Set up for using this key --- */
-
- k = *(uint32 *)v[0].buf;
- h = *(uint32 *)v[2].buf;
- unihash_setkey(&ui, k);
-
- /* --- Hash the data a lot --- */
-
- for (i = 0; step[i] >= 0; i++) {
- c = step[i];
- if (!c)
- hh = unihash(&ui, v[1].buf, v[1].len);
- else {
- hh = UNIHASH_INIT(&ui);
- p = v[1].buf;
- n = v[1].len;
- while (n) {
- if (c > n) c = n;
- hh = unihash_hash(&ui, hh, p, c);
- p += c;
- n -= c;
- }
- }
- if (h != hh) {
- ok = 0;
- fprintf(stderr, "\nunihash failed\n");
- fprintf(stderr, " key = %08lx\n", (unsigned long)k);
- fprintf(stderr, " data = %s\n", v[1].buf);
- fprintf(stderr, " step = %d\n", step[i]);
- fprintf(stderr, " expected = %08lx\n", (unsigned long)h);
- fprintf(stderr, " computed = %08lx\n", (unsigned long)hh);
- }
- }
- return (ok);
-}
-
-static const test_chunk tests[] = {
- { "hash", verify, { &type_uint32, &type_string, &type_uint32 } },
- { 0, 0, { 0 } }
-};
-
-int main(int argc, char *argv[])
-{
- test_run(argc, argv, tests, "unihash.in");
- return (0);
-}
-
-#endif
-
-/*----- That's all, folks -------------------------------------------------*/
~mdw / mLib / blobdiff