From 18756bee6a2b8aa06f001bce6843bce5b2dfb0b0 Mon Sep 17 00:00:00 2001 Message-Id: <18756bee6a2b8aa06f001bce6843bce5b2dfb0b0.1715204671.git.mdw@distorted.org.uk> From: Mark Wooding Date: Mon, 15 Dec 2003 20:53:08 +0000 Subject: [PATCH] New program to make fixed tables for universal hashing. Organization: Straylight/Edgeware From: mdw --- Makefile.am | 24 +++- man/Makefile.am | 7 +- man/unihash-mkstatic.1 | 120 +++++++++++++++++++ unihash-mkstatic.c | 266 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 410 insertions(+), 7 deletions(-) create mode 100644 man/unihash-mkstatic.1 create mode 100644 unihash-mkstatic.c diff --git a/Makefile.am b/Makefile.am index 08aeed3..32ef349 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,6 +1,6 @@ ## -*-Makefile-*- ## -## $Id: Makefile.am,v 1.44 2003/12/14 14:56:57 mdw Exp $ +## $Id: Makefile.am,v 1.45 2003/12/15 20:53:08 mdw Exp $ ## ## Building the distribution ## @@ -29,6 +29,9 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.am,v $ +## Revision 1.45 2003/12/15 20:53:08 mdw +## New program to make fixed tables for universal hashing. +## ## Revision 1.44 2003/12/14 14:56:57 mdw ## Fix distribution. ## @@ -150,7 +153,7 @@ AUTOMAKE_OPTIONS = foreign SUBDIRS = man bin_SCRIPTS = mLib-config -bin_PROGRAMS = crc-mktab +bin_PROGRAMS = crc-mktab unihash-mkstatic lib_LTLIBRARIES = libmLib.la pkglibexecdir = $(libexecdir)/$(PACKAGE) @@ -175,10 +178,11 @@ libmLib_la_LDFLAGS = -version-info 2:3:0 libmLib_la_SOURCES = \ alloc.c arena.c exc.c quis.c pquis.c report.c sub.c trace.c \ - traceopt.c track.c unihash.c \ + traceopt.c track.c \ pool.c pool-file.c pool-sub.c \ atom.c assoc.c darray.c dstr.c dputf.c dspool.c hash.c sym.c \ crc32.c crc32-tab.c \ + unihash.c unihash-global.c \ env.c fdflags.c fdpass.c fwatch.c lock.c \ @BRES_SOURCE@.c \ conn.c lbuf.c ident.c pkbuf.c sel.c selbuf.c selpk.c sig.c \ @@ -187,7 +191,7 @@ libmLib_la_SOURCES = \ EXTRA_libmLib_la_SOURCES = bres.c bres-adns.c libmLib_la_LIBADD = @DEPLIBS@ -BUILT_SOURCES = crc32-tab.c +BUILT_SOURCES = crc32-tab.c unihash-global.c crc32-tab.c: crc-mktab ./crc-mktab \ @@ -195,7 +199,17 @@ crc32-tab.c: crc-mktab -c -scrc32_table -icrc32.h -tuint32 -ocrc32-tab.c.new mv crc32-tab.c.new crc32-tab.c -crc_mktab_SOURCES = crc-mktab.c mdwopt.c quis.c pquis.c report.c str.c +unihash-global.c: unihash-mkstatic + ./unihash-mkstatic \ + -c -sunihash_global -iunihash.h -ounihash-global.c.new + mv unihash-global.c.new unihash-global.c + +crc_mktab_SOURCES = \ + crc-mktab.c \ + mdwopt.c quis.c pquis.c report.c str.c +unihash_mkstatic_SOURCES = \ + unihash-mkstatic.c \ + mdwopt.c quis.c pquis.c report.c str.c unihash.c ## --- Test code --- diff --git a/man/Makefile.am b/man/Makefile.am index 41d8065..1927f4b 100644 --- a/man/Makefile.am +++ b/man/Makefile.am @@ -1,6 +1,6 @@ ## -*-makefile-*- ## -## $Id: Makefile.am,v 1.7 2003/12/14 14:57:35 mdw Exp $ +## $Id: Makefile.am,v 1.8 2003/12/15 20:53:08 mdw Exp $ ## ## Makefile for mLib's manual pages ## @@ -29,6 +29,9 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.am,v $ +## Revision 1.8 2003/12/15 20:53:08 mdw +## New program to make fixed tables for universal hashing. +## ## Revision 1.7 2003/12/14 14:57:35 mdw ## Distribute unihash manpage. ## @@ -64,7 +67,7 @@ manext = @manext@ ## --- Manual pages --- MANPAGES = \ - crc-mktab.1 + crc-mktab.1 unihash-mkstatic.1 MANPAGESEXT = \ alloc.3 arena.3 assoc.3 atom.3 base64.3 bits.3 bres.3 conn.3 \ diff --git a/man/unihash-mkstatic.1 b/man/unihash-mkstatic.1 new file mode 100644 index 0000000..94d2c44 --- /dev/null +++ b/man/unihash-mkstatic.1 @@ -0,0 +1,120 @@ +.\" nroff +.ie t \{\ +. ds ss \s8\u +. ds se \d\s0 +.\} +.el \{\ +. ds ss ^ +. ds se +.\} +.TH unihash-mkstatic 1 "14 December 2003" "Straylight/Edgeware" "mLib utilities library" +.SH NAME +unihash-mkstatic \- construct tables for universal hashing +.SH SYNOPSIS +.B unihash-mkstatic +.RB [ \-c ] +.RB [ \-s +.IR symbol ] +.RB [ \-i +.IR header ] +.RB [ \-g +.IR macro ] +.br + \c +.RB [ \-k +.IR key ] +.RB [ \-o +.IR filename ] +.SH DESCRIPTION +The +.B unihash-mkstatic +program constructs tables for efficient universal hashing (see +.BR unihash (3)). +It will produce the table as either an array defined in a C source file +or as an initializer macro defined in a C header file. +.SS "Options" +The program accepts no non-option arguments. The options are as +follows. +.TP +.B "\-h, \-\-help" +Print a help message to standard output and exit successfully. +.TP +.B "\-v, \-\-version" +Print the program's version number to standard output and exit +successfully. +.TP +.B "\-u, \-\-usage" +Print a one-line usage summary to standard output and exit successfully. +.TP +.B "\-c, \-\-c-source" +Produce a C source file which exports a symbol naming the array, instead +of a C header file. +.TP +.BI "\-s, \-\-symbol=" symbol +Name the table +.IR symbol . +This is the name of the macro defined by a header file, or the array +exported by a C source. The default macro name is +.BR UHI_INIT ; +the default array name is +.BR uhi . +.TP +.BI "\-i, \-\-include=" header +Request that generated C source include the named +.I header +file. Inserts a +line of the form +.PP +.nf +.BI " #include """ header """" +.fi +.IP +at the top of the generated C source. The default is not to include +.BR , +which is necessary to declare the +.B unihash_info +type. This option does nothing without the +.B \-c +option. +.TP +.BI "\-g, \-\-guard=" macro +Use the named +.I macro +as a guard against multiple inclusion of the generated header file. +Inserts a pair of lines of the form +.PP +.nf +.BI " #ifndef " macro +.BI " #define " macro +.fi +.IP +at the top of the generated header, and a line +.PP +.nf +.BI " #endif" +.fi +.IP +at the end. The default guard macro name is built from the output file +name specified with +.B \-o +by uppercasing all alphabetic characters in the name and replacing +nonalphanumeric characters by underscores +.RB ` _ '. +This option does nothing with the +.B \-c +option. +.TP +.BI "\-k, \-\-key=" key +Specifies the hashing key as an integer. Note that if you want to +specify the key in hexadecimal, you must prefix it with +.BR 0x . +The default key is +.BR 0xe07e5bd1 , +which is, as far as the author knows, as good as any other fixed value. +.TP +.SH "SEE ALSO" +.BR crc-mktab (1), +.BR unihash (3). +.SH "AUTHOR" +Mark Wooding, + diff --git a/unihash-mkstatic.c b/unihash-mkstatic.c new file mode 100644 index 0000000..ba074e6 --- /dev/null +++ b/unihash-mkstatic.c @@ -0,0 +1,266 @@ +/* -*-c-*- + * + * $Id: unihash-mkstatic.c,v 1.1 2003/12/15 20:52:56 mdw Exp $ + * + * Build static universal hash tables + * + * (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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: unihash-mkstatic.c,v $ + * Revision 1.1 2003/12/15 20:52:56 mdw + * New program to make fixed tables for universal hashing. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include +#include +#include + +#include "macros.h" +#include "mdwopt.h" +#include "quis.h" +#include "report.h" +#include "unihash.h" + +/*----- Main code ---------------------------------------------------------*/ + +#define BSCOL 72 + +static unsigned long getint(const char *p, unsigned long max, + const char *what) +{ + char *pp; + unsigned long x = strtoul(p, &pp, 0); + if (*pp || (max && x > max)) + die(EXIT_FAILURE, "bad %s `%s'", what, p); + return (x); +} + +static void version(FILE *fp) +{ + pquis(fp, "$, mLib version " VERSION "\n"); +} + +static void usage(FILE *fp) +{ + pquis(fp, "Usage: $ [-c] [-o FILE] [-g GUARD] [-i HEADER] [-s SYM]\n\ + [-k KEY]\n"); +} + +static void help(FILE *fp) +{ + version(fp); + putc('\n', stdout); + usage(fp); + fputs("\n\ +Emits a precomputed unihash_info structure for a given key.\n\ +\n\ +-h, --help Show this help text.\n\ +-v, --version Show the program's version number.\n\ +-u, --usage Show a terse usage message.\n\ +\n\ +-c, --c-source Emit a C source file rather than a header.\n\ +-k, --key=KEY Use KEY as the universal hashing key.\n\ +-g, --guard=GUARD Use GUARD as a multiple-inclusion guard constant.\n\ +-i, --include=HEADER Include HEADER at top of C source file.\n\ +-s, --symbol=SYM Name the generated table SYM.\n\ +-o, --output=FILE Write the output to FILE.\n\ +", stdout); +} + +int main(int argc, char *argv[]) +{ + uint32 key = 0xe07e5bd1; + unsigned flags = 0; + const char *sym = 0; + const char *inc = 0; + const char *guard = 0; + const char *file = 0; + FILE *fp; + unihash_info u; + int i, j, k; + +#define f_bogus 1u +#define f_ctab 2u + + ego(argv[0]); + + for (;;) { + static struct option opts[] = { + { "help", 0, 0, 'h' }, + { "version", 0, 0, 'v' }, + { "usage", 0, 0, 'u' }, + + { "output", OPTF_ARGREQ, 0, 'o' }, + { "c-source", 0, 0, 'c' }, + { "key", OPTF_ARGREQ, 0, 'k' }, + { "symbol", OPTF_ARGREQ, 0, 's' }, + { "include", OPTF_ARGREQ, 0, 'i' }, + { "guard", OPTF_ARGREQ, 0, 'g' }, + + { 0, 0, 0, 0 } + }; + int i = mdwopt(argc, argv, "hvu o:ck:s:i:g:", opts, 0, 0, 0); + + if (i < 0) + break; + switch (i) { + case 'h': + help(stdout); + exit(0); + case 'v': + version(stdout); + exit(0); + case 'u': + usage(stdout); + exit(0); + + case 'o': + file = optarg; + break; + case 'c': + flags |= f_ctab; + break; + case 's': + sym = optarg; + break; + case 'i': + inc = optarg; + break; + case 'g': + guard = optarg; + break; + case 'k': + key = getint(optarg, 0xffffffff, "key"); + break; + + default: + flags |= f_bogus; + break; + } + } + if ((flags & f_bogus) || optind != argc) { + usage(stderr); + exit(EXIT_FAILURE); + } + + /* --- Sort stuff out --- */ + + unihash_setkey(&u, key); + if (!sym) + sym = (flags & f_ctab) ? "uhi" : "UHI_INIT"; + + /* --- Start output --- */ + + if (!file) + fp = stdout; + else { + if (!(flags & f_ctab) && !guard) { + char *p; + const char *q; + if ((p = malloc(strlen(file) + 1)) == 0) + die(EXIT_FAILURE, "not enough memory"); + guard = p; + for (q = file; *q; p++, q++) { + if (isalnum((unsigned char)*q)) + *p = toupper((unsigned char)*q); + else + *p = '_'; + } + *p++ = 0; + } + if ((fp = fopen(file, "w")) == 0) + die(EXIT_FAILURE, "couldn't write `%s': %s", file, strerror(errno)); + } + + /* --- Dump out the first chunk of the file --- */ + + fprintf(fp, "\ +/* -*-c-*-\n\ + *\n\ + * Unihash table (key = %08lx) [generated]\n\ + */\n\ +\n", + (unsigned long)key); + + if (flags & f_ctab) { + if (inc) + fprintf(fp, "#include \"%s\"\n\n", inc); + else + fputs("#include \n\n", fp); + fprintf(fp, "unihash_info %s = { {\n", sym); + } else { + int n; + if (guard) + fprintf(fp, "#ifndef %s\n#define %s\n\n", guard, guard); + n = fprintf(fp, "#define %s { {", sym); + while (n < BSCOL) { + fputc('\t', fp); + n = (n + 8) & ~7; + } + fputc('\n', fp); + } + + /* --- Main output --- */ + + for (i = 0; i < N(u.s); i++) { + fputs(" {", fp); + for (j = 0; j < N(u.s[i]); j++) { + fputs(" {", fp); + for (k = 0; k < N(u.s[i][j]); k++) { + fprintf(fp, " 0x%08lx", (unsigned long)u.s[i][j][k]); + if (k < N(u.s[i][j]) - 1) { + fputc(',', fp); + if (k % 4 == 3) + fputs(flags & f_ctab ? "\n " : "\t\t\t\\\n ", fp); + } + } + if (j < N(u.s[i]) - 1) { + fputs(flags & f_ctab ? " },\n\n " : + " },\t\t\t\\\n\t\t\t\t\t\t\t\t\t\\\n ", fp); + } + } + if (i < N(u.s) - 1) { + fputs(flags & f_ctab ? " } },\n\n" : + " } },\t\t\\\n\t\t\t\t\t\t\t\t\t\\\n", fp); + } + } + + /* --- Done --- */ + + fputs(flags & f_ctab ? " } }\n} };\n" : + " } }\t\t\\\n} }\n", fp); + if (!(flags & f_ctab) && guard) + fputs("\n#endif\n", fp); + + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ -- [mdw]