chiark / gitweb /
New program to make fixed tables for universal hashing.
authormdw <mdw>
Mon, 15 Dec 2003 20:53:08 +0000 (20:53 +0000)
committermdw <mdw>
Mon, 15 Dec 2003 20:53:08 +0000 (20:53 +0000)
Makefile.am
man/Makefile.am
man/unihash-mkstatic.1 [new file with mode: 0644]
unihash-mkstatic.c [new file with mode: 0644]

index 08aeed3..32ef349 100644 (file)
@@ -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 ---
 
index 41d8065..1927f4b 100644 (file)
@@ -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 (file)
index 0000000..94d2c44
--- /dev/null
@@ -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 <mLib/unihash.h> ,
+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, <mdw@nsict.org>
+
diff --git a/unihash-mkstatic.c b/unihash-mkstatic.c
new file mode 100644 (file)
index 0000000..ba074e6
--- /dev/null
@@ -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 <ctype.h>
+#include <errno.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#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 <mLib/unihash.h>\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 -------------------------------------------------*/