/* -*-c-*-
*
- * $Id: atom.c,v 1.3 2001/01/25 21:13:15 mdw Exp $
+ * $Id: atom.c,v 1.4 2003/12/15 20:53:47 mdw Exp $
*
* Atom management
*
/*----- Revision history --------------------------------------------------*
*
* $Log: atom.c,v $
+ * Revision 1.4 2003/12/15 20:53:47 mdw
+ * Add global unihash table; use universal hashing instead of CRC.
+ *
* Revision 1.3 2001/01/25 21:13:15 mdw
* New function allowing an atom's length to be specified at intern time.
*
#include "alloc.h"
#include "atom.h"
-#include "crc32.h"
#include "hash.h"
#include "sym.h"
+#include "unihash.h"
/*----- Static variables --------------------------------------------------*/
a->b.name = (char *)(a + 1);
memcpy(a->b.name, buf, sz);
a->b.len = sz;
- CRC32(a->b.b.hash, 0, buf, sz);
+ a->b.b.hash = UNIHASH(&unihash_global, buf, sz);
a->f = ATOMF_GENSYM;
a->b.b.next = t->g;
t->g = &a->b.b;
/* -*-c-*-
*
- * $Id: crc-mktab.c,v 1.4 2001/03/10 10:59:21 mdw Exp $
+ * $Id: crc-mktab.c,v 1.5 2003/12/15 20:53:47 mdw Exp $
*
* Build CRC tables
*
/*----- Revision history --------------------------------------------------*
*
* $Log: crc-mktab.c,v $
+ * Revision 1.5 2003/12/15 20:53:47 mdw
+ * Add global unihash table; use universal hashing instead of CRC.
+ *
* Revision 1.4 2001/03/10 10:59:21 mdw
* Fix generating tables where the chunk size is longer than the
* polynomial. Also fix output formatting when there aren't enough entries
static void usage(FILE *fp)
{
- pquis(fp, "Usage: $ [-cr] [-g guard] [-o file] [-b bits] [-p poly]\n");
+ pquis(fp, "Usage: $ [-cr] [-o FILE] [-g GUARD] [-s SYM] [-i HEADER]\n\
+ [-t TYPE] [-b BITS] [-B BITS] [-p POLY]\n");
}
static void help(FILE *fp)
-p, --polynomial=POLY Use the POLY as the dividing polynomial.\n\
-r, --reverse Create a `reversed' CRC table.\n\
-g, --guard=GUARD Use GUARD as a multiple-inclusion guard constant.\n\
--s, --symbol=SYM Name the generated table SYM\n\
+-i, --include=HEADER Include HEADER at top of C source file.\n\
+-s, --symbol=SYM Name the generated table SYM.\n\
-t, --type=TYPE Give the table entries type TYPE in C source.\n\
-o, --output=FILE Write the output to FILE.\n\
", stdout);
mlib (2.0.3) experimental; urgency=low
* Document hex encoding/decoding.
-
* Add file descriptor passing.
+ * Add ADNS-based background resolver.
+ * Split binaries off into their own package.
+ * Document, fix and test universal hashing; use it in symbol tables.
- * Add ADNS-based background resolver.
-
- -- Mark Wooding <mdw@nsict.org> Sat, 13 Dec 2003 19:54:22 +0000
+ -- Mark Wooding <mdw@nsict.org> Mon, 15 Dec 2003 20:54:16 +0000
mlib (2.0.2) experimental; urgency=low
Description: A library of miscellaneous stuff
The mLib library provides various handy utilities, including
* yet another options parser, like GNU getopt but more so;
+ * a simple but efficient universal hashing family;
* a suite for writing event-driven select-based servers;
* a simple exception-handling system, based on longjmp;
* dynamically resizing strings and arrays;
Description: A library of miscellaneous stuff
The mLib library provides various handy utilities, including
* yet another options parser, like GNU getopt but more so;
+ * a simple but efficient universal hashing family;
* a suite for writing event-driven select-based servers;
* a simple exception-handling system, based on longjmp;
* dynamically resizing strings and arrays;
Architecture: any
Depends: mlib2 (= ${Source-Version}) | mlib2-adns (= ${Source-Version}),
libc6-dev
+Recommends: mlib-bin
Description: A library of miscellaneous stuff
The mLib library provides various handy utilities, including
* yet another options parser, like GNU getopt but more so;
+ * a simple but efficient universal hashing family;
* a suite for writing event-driven select-based servers;
* a simple exception-handling system, based on longjmp;
* dynamically resizing strings and arrays;
* a simple background DNS resolver.
This package contains the header files and static libraries needed to
compile programs which use mLib.
+
+Package: mlib-bin
+Architecture: any
+Depends: ${shlibs:Depends}
+Recommends: mlib-dev
+Description: A library of miscellaneous stuff
+ The mLib library provides various handy utilities, including
+ * yet another options parser, like GNU getopt but more so;
+ * a simple but efficient universal hashing family;
+ * a suite for writing event-driven select-based servers;
+ * a simple exception-handling system, based on longjmp;
+ * dynamically resizing strings and arrays;
+ * a resizing hashtable;
+ * base64 and hex encoding and decoding; and
+ * a simple background DNS resolver.
+ This package contains some utility programs: in particular, to generate
+ static tables for efficient CRC and universal hashing computations.
mv debian/mlib2/usr/lib/*.so debian/mlib-dev/usr/lib
mv debian/mlib2/usr/lib/*.la debian/mlib-dev/usr/lib
mv debian/mlib2/usr/include debian/mlib-dev/usr
+ mkdir -p debian/mlib-bin/usr/share/man
+ mv debian/mlib2/usr/bin debian/mlib-bin/usr
+ mv debian/mlib2/usr/share/man/man1 debian/mlib-bin/usr/share/man
make -C deb-build install DESTDIR=`pwd`/debian/mlib2-adns
- rm debian/mlib2-adns/usr/bin/mLib-config
- rm -r debian/mlib2-adns/usr/share/man/man3
+ rmdir debian/mlib2-adns/usr/lib/mLib
+ rm -rf debian/mlib2-adns/usr/bin
+ rm -rf debian/mlib2-adns/usr/share/man
+ rm -rf debian/mlib2-adns/usr/include
rm debian/mlib2-adns/usr/lib/*.a
rm debian/mlib2-adns/usr/lib/*.so
rm debian/mlib2-adns/usr/lib/*.la
- rm -rf debian/mlib2-adns/usr/include
dh_strip -a
binary-indep:
Produce a C source file which exports a symbol naming the array, instead
of a C header file.
.TP
-.BI "\s, \-\-symbol=" symbol
+.BI "\-s, \-\-symbol=" symbol
Name the table
.IR symbol .
This is the name of the macro defined by a header file, or the array
.SS "Miscellaneous utilities"
The
.BR crc32 (3)
-module calculates CRC values for strings. It's used by the symbol table
-manager as a hash function.
+module calculates CRC values for strings. It used to be used by the
+symbol table manager as a hash function.
+.PP
+The
+.BR unihash (3)
+module implements a simple but efficient universal hashing family. This
+is a keyed hash function which provides security against an adversary
+choosing input to a hash table deliberately to cause collisions.
.PP
The
.BR lock (3)
.VE
That ought to be enough examples to be getting on with.
.SS Implementation
-The symbol table is an extensible hashtable, using a 32-bit CRC as the
-hash function. The hash chains are kept very short (probably too short,
-actually). Every time a symbol is found, its block is promoted to the
-front of its bin chain so it gets found faster next time.
+The symbol table is an extensible hashtable, using the universal hash
+function described in
+.BR unihash (3)
+and the global hashing key. The hash chains are kept very short
+(probably too short, actually). Every time a symbol is found, its block
+is promoted to the front of its bin chain so it gets found faster next
+time.
.SH SEE ALSO
.BR hash (3),
.BR mLib (3).
.nf
.B "#include <mLib/unihash.h>"
+.B "unihash_info unihash_global;"
+
.BI "void unihash_setkey(unihash_info *" i ", uint32 " k );
.BI "uint32 UNIHASH_INIT(const unihash_info *" i );
.BI "void unihash_hash(const unihash_info *" st ", uint32 " a ,
are convenient interfaces to
.B unihash_hash
if you only wanted to hash one chunk.
+.SS "Global hash info table"
+There's no problem with using the same key for several purposes, as long
+as it's secret from all of your adversaries. Therefore, there is a
+global
+.B unihash_info
+table define, called
+.BR unihash_global .
+This initially contains information for a fixed key which the author
+chose at random, but if you need to you can set a different key into it
+.I before
+it gets used to hash any data (otherwise your hash tables will become
+messed up).
.SS "Theoretical issues"
The hash function implemented by
.B unihash
cryptographic security, which actually reduce the security of some
construction to the security of its components). It's just a fact.
.SH SEE ALSO
+.BR unihash-mkstatic (3),
.BR crc32 (3),
.BR mLib (3).
.SH AUTHOR
/* -*-c-*-
*
- * $Id: sym.c,v 1.13 2001/01/25 21:14:49 mdw Exp $
+ * $Id: sym.c,v 1.14 2003/12/15 20:53:47 mdw Exp $
*
* Symbol table management
*
/*----- Revision history --------------------------------------------------*
*
* $Log: sym.c,v $
+ * Revision 1.14 2003/12/15 20:53:47 mdw
+ * Add global unihash table; use universal hashing instead of CRC.
+ *
* Revision 1.13 2001/01/25 21:14:49 mdw
* Always add a terminating null, and don't count it in the length.
*
#include "alloc.h"
#include "arena.h"
#include "bits.h"
-#include "crc32.h"
#include "exc.h"
#include "hash.h"
#include "sub.h"
#include "sym.h"
+#include "unihash.h"
/*----- Main code ---------------------------------------------------------*/
/* --- @sym_find@ --- *
*
* Arguments: @sym_table *t@ = pointer to symbol table in question
- * @const char *n@ = pointer to symbol table to look up
+ * @const char *n@ = pointer to symbol name to look up
* @long l@ = length of the name string or negative to measure
* @size_t sz@ = size of desired symbol object, or zero
* @unsigned *f@ = pointer to a flag, or null.
/* --- Find the correct bin --- */
len = l < 0 ? strlen(n) : l;
- CRC32(hash, 0, n, len);
+ hash = UNIHASH(&unihash_global, n, len);
bin = HASH_BIN(&t->t, hash);
/* --- Search the bin list --- */
/* -*-c-*-
*
- * $Id: sym.h,v 1.12 2001/01/20 11:49:37 mdw Exp $
+ * $Id: sym.h,v 1.13 2003/12/15 20:53:47 mdw Exp $
*
* Symbol table management
*
/*----- Revision history --------------------------------------------------*
*
* $Log: sym.h,v $
+ * Revision 1.13 2003/12/15 20:53:47 mdw
+ * Add global unihash table; use universal hashing instead of CRC.
+ *
* Revision 1.12 2001/01/20 11:49:37 mdw
* Export tuning parameters from header file, for the benefit of other
* hashtable implementations. Change the storage of symbol names: store
/* --- @sym_find@ --- *
*
* Arguments: @sym_table *t@ = pointer to symbol table in question
- * @const char *n@ = pointer to symbol table to look up
+ * @const char *n@ = pointer to symbol name to look up
* @long l@ = length of the name string or negative to measure
* @size_t sz@ = size of desired symbol object, or zero
* @unsigned *f@ = pointer to a flag, or null.
/* -*-c-*-
*
- * $Id: unihash.h,v 1.2 2003/12/14 14:45:30 mdw Exp $
+ * $Id: unihash.h,v 1.3 2003/12/15 20:53:47 mdw Exp $
*
* Simple and efficient universal hashing for hashtables
*
/*----- Revision history --------------------------------------------------*
*
* $Log: unihash.h,v $
+ * Revision 1.3 2003/12/15 20:53:47 mdw
+ * Add global unihash table; use universal hashing instead of CRC.
+ *
* Revision 1.2 2003/12/14 14:45:30 mdw
* Test universal hashing and fix bugs.
*
uint32 s[UNIHASH_NBATCH][4][256]; /* S-tables as described */
} unihash_info;
+/*----- A global hash-info table ------------------------------------------*/
+
+extern unihash_info unihash_global; /* Key this if you like */
+
/*----- Functions provided ------------------------------------------------*/
/* --- @unihash_setkey@ --- *
~mdw / mLib / commitdiff