chiark / gitweb /
Generate the CRC table rather than hardcoding it.
authormdw <mdw>
Fri, 21 Jul 2000 19:01:33 +0000 (19:01 +0000)
committermdw <mdw>
Fri, 21 Jul 2000 19:01:33 +0000 (19:01 +0000)
Makefile.am
crc-mktab.c [new file with mode: 0644]
crc32.c

index 0f8155d..3fe766a 100644 (file)
@@ -1,6 +1,6 @@
 ## -*-Makefile-*-
 ##
-## $Id: Makefile.am,v 1.21 2000/07/16 18:57:52 mdw Exp $
+## $Id: Makefile.am,v 1.22 2000/07/21 19:01:33 mdw Exp $
 ##
 ## Building the distribution
 ##
@@ -29,6 +29,9 @@
 ##----- Revision history ----------------------------------------------------
 ##
 ## $Log: Makefile.am,v $
+## Revision 1.22  2000/07/21 19:01:33  mdw
+## Generate the CRC table rather than hardcoding it.
+##
 ## Revision 1.21  2000/07/16 18:57:52  mdw
 ## New files.  Test cases for `bits.h'.
 ##
@@ -79,6 +82,7 @@ AUTOMAKE_OPTIONS = foreign
 SUBDIRS = man
 
 bin_SCRIPTS = mLib-config
+bin_PROGRAMS = crc-mktab
 
 lib_LTLIBRARIES = libmLib.la
 libexec_PROGRAMS = bres
@@ -102,12 +106,21 @@ libmLib_la_SOURCES = \
        alloc.c arena.c exc.c quis.c pquis.c report.c sub.c trace.c \
                traceopt.c track.c \
        pool.c pool-file.c pool-sub.c \
-       darray.c dstr.c dputf.c dspool.c hash.c sym.c crc32.c \
+       darray.c dstr.c dputf.c dspool.c hash.c sym.c crc32.c crc32-tab.c \
        env.c fdflags.c lock.c \
        bres.c conn.c lbuf.c ident.c pkbuf.c sel.c selbuf.c selpk.c sig.c \
        tv.c \
        base64.c mdwopt.c str.c testrig.c url.c
 
+BUILT_SOURCES = crc32-tab.c
+
+crc32-tab.c: crc-mktab
+       ./crc-mktab \
+               -p0x04c11db7 -b32 -B8 -r \
+               -c -scrc32_table -icrc32.h -tuint32 -ocrc32-tab.c
+
+crc_mktab_SOURCES = crc-mktab.c mdwopt.c quis.c pquis.c report.c
+
 ## --- Test code ---
 
 noinst_PROGRAMS = da-test sym-test bits.t
diff --git a/crc-mktab.c b/crc-mktab.c
new file mode 100644 (file)
index 0000000..887315b
--- /dev/null
@@ -0,0 +1,360 @@
+/* -*-c-*-
+ *
+ * $Id: crc-mktab.c,v 1.1 2000/07/21 19:01:33 mdw Exp $
+ *
+ * Build CRC tables
+ *
+ * (c) 2000 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: crc-mktab.c,v $
+ * Revision 1.1  2000/07/21 19:01:33  mdw
+ * Generate the CRC table rather than hardcoding it.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <ctype.h>
+#include <errno.h>
+#include <limits.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "mdwopt.h"
+#include "quis.h"
+#include "report.h"
+
+/*----- Static variables --------------------------------------------------*/
+
+static unsigned long poly = 0;
+static const char *guard = 0;
+static unsigned bits = 0;
+static unsigned chunk = 8;
+static const char *file = 0;
+static unsigned flags = 0;
+static const char *sym = 0;
+static const char *type = 0;
+static const char *inc = 0;
+static FILE *fp;
+
+enum {
+  f_bogus = 1,
+  f_ctab = 2,
+  f_reverse = 4
+};
+
+#define BSCOL 72
+
+/*----- Main code ---------------------------------------------------------*/
+
+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: $ [-cr] [-g guard] [-o file] [-b bits] [-p poly]\n");
+}
+
+static void help(FILE *fp)
+{
+  version(fp);
+  putc('\n', stdout);
+  usage(fp);
+  fputs("\n\
+Emits a table containing precomuted values for CRC algorithms.  A number\n\
+of options are provided:\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\
+-b, --bits=BITS                Emit a table for a BITS bits-wide CRC.\n\
+-B, --bit-chunk=BITS   Emit a table to process BITS bits at a time.\n\
+-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\
+-t, --type=TYPE                Give the table entries type TYPE in C source.\n\
+-o, --output=FILE      Write the output to FILE.\n\
+", stdout);
+}
+
+unsigned long reflect(unsigned long x, unsigned b)
+{
+  unsigned long y = 0;
+  unsigned long xm, ym;
+  unsigned i;
+  if (!(flags & f_reverse))
+    return (x);
+  xm = 1;
+  ym = 1 << (b - 1);
+  for (i = 0; i < b; i++) {
+    if (x & xm)
+      y |= ym;
+    xm <<= 1;
+    ym >>= 1;
+  }
+  return (y);
+}
+
+int main(int argc, char *argv[])
+{
+  unsigned n, t, nw;
+  unsigned max, i;
+  unsigned long mask;
+
+  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' },
+      { "symbol",      OPTF_ARGREQ,    0,      's' },
+      { "type",                OPTF_ARGREQ,    0,      't' },
+      { "include",     OPTF_ARGREQ,    0,      'i' },
+      { "guard",       OPTF_ARGREQ,    0,      'g' },
+
+      { "bits",                OPTF_ARGREQ,    0,      'b' },
+      { "bit-chunk",   OPTF_ARGREQ,    0,      'B' },
+      { "polynomial",  OPTF_ARGREQ,    0,      'p' },
+      { "reverse",     0,              0,      'r' },
+
+      { 0,             0,              0,      0 }
+    };
+    int i = mdwopt(argc, argv, "hvu o:cs:t:i:g: b:B:p:r", 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 't':
+       type = optarg;
+       break;
+      case 'i':
+       inc = optarg;
+       break;
+      case 'g':
+       guard = optarg;
+       break;
+
+      case 'b':
+       bits = getint(optarg, 32, "CRC width");
+       break;
+      case 'B':
+       chunk = getint(optarg, 32, "chunk size");
+       break;
+      case 'p':
+       poly = getint(optarg, 0xffffffff, "CRC poly");
+       break;
+      case 'r':
+       flags |= f_reverse;
+       break;
+
+      default:
+       flags |= f_bogus;
+       break;
+    }
+  }
+  if ((flags & f_bogus) || optind != argc) {
+    usage(stderr);
+    exit(EXIT_FAILURE);
+  }
+
+  /* --- Sort out the various parameters --- */
+
+  if (!poly) {
+    switch (bits) {
+      case 16:
+       if (flags & f_reverse)
+         poly = 0x8408;
+       else
+         poly = 0x1021;
+       break;
+      case 32:
+      case 0:
+       poly = 0x04c11db7;
+       flags |= f_reverse;
+       bits = 32;
+       break;
+      default:
+       die(EXIT_FAILURE, "no standard polynomials for %u bits", bits);
+       break;
+    }
+  }
+
+  if (!bits) {
+    unsigned long x = poly;
+    while (x > 1) {
+      x >>= 8;
+      bits += 8;
+    }
+  }
+  nw = bits/4;
+
+  if ((flags & f_ctab) && !type)
+    type = bits > 16 ? "unsigned long" : "unsigned short";
+
+  /* --- 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 = *q;
+       else
+         *p = '_';
+      }
+      *p++ = 0;
+    }
+    if ((fp = fopen(file, "w")) == 0)
+      die(EXIT_FAILURE, "couldn't write `%s': %s", file, strerror(errno));
+  }
+
+  if (!sym)
+    sym = (flags & f_ctab) ? "crctab" : "CRC_TAB";
+
+  /* --- Dump out the first chunk of the file --- */
+
+  fprintf(fp, "\
+/* -*-c-*-\n\
+ *\n\
+ * CRC table (poly = %0*lx%s) [generated]\n\
+ */\n\
+\n",
+         nw, poly, flags & f_reverse ? "; reversed" : "");
+
+  if (flags & f_ctab) {
+    if (inc)
+      fprintf(fp, "#include \"%s\"\n\n", inc);
+    fprintf(fp, "%s %s[] = {\n", type, 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);
+  }
+
+  /* --- Sort out the line width --- */
+
+  n = 1;
+  while (2 + n * (nw + 4) < BSCOL)
+    n <<= 1;
+  n >>= 1;
+  t = 0;
+  while (((1 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
+    t++;
+
+  /* --- Start grinding --- */
+
+  max = 1 << chunk;
+  mask = 0xffffffff >> (32 - bits);
+  fputc(' ', fp);
+  for (i = 0; i < max; i++) {
+    unsigned long x;
+    unsigned j;
+
+    x = reflect(i, chunk) << (bits - chunk);
+    for (j = 0; j < chunk; j++)
+      x = ((x << 1) ^ (x & (1 << (bits - 1)) ? poly : 0)) & mask;
+    x = reflect(x, bits);
+
+    fprintf(fp, " 0x%0*lx", nw, x);
+    if (i == max - 1) {
+      if (!(flags & f_ctab) && ((2 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
+       fputc('\t', fp);
+    } else
+      fputc(',', fp);
+    if (i + 1 == max || (i + 1)%n == 0) {
+      if (!(flags & f_ctab)) {
+       for (j = 0; j < t; j++)
+         fputc('\t', fp);
+       fputc('\\', fp);
+      }
+      fputc('\n', fp);
+      if (i + 1 != max)
+       fputc(' ', fp);
+    }
+  }
+
+  /* --- Done --- */
+
+  fputs(flags & f_ctab ? "};\n" : "}\n", fp);
+  if (!(flags & f_ctab) && guard)
+    fputs("\n#endif\n", fp);
+
+  return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
diff --git a/crc32.c b/crc32.c
index 5f47665..a24c909 100644 (file)
--- a/crc32.c
+++ b/crc32.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: crc32.c,v 1.4 1999/06/01 09:47:22 mdw Exp $
+ * $Id: crc32.c,v 1.5 2000/07/21 19:01:33 mdw Exp $
  *
  * Calculating cyclic redundancy values (non-cryptographic!)
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: crc32.c,v $
+ * Revision 1.5  2000/07/21 19:01:33  mdw
+ * Generate the CRC table rather than hardcoding it.
+ *
  * Revision 1.4  1999/06/01 09:47:22  mdw
  * Make the return type of `crc32' a `uint32' now that we have `bits.h'.
  *
 #include "bits.h"
 #include "crc32.h"
 
-/*----- CRC table ---------------------------------------------------------*/
-
-/* --- Acknowledgements and information --- *
- *
- * This table was generated using a derivative of the Rocksoft Model CRC
- * generator.  The parameters given are:
- *
- *   width = 32bits
- *   poly = 0x04C11DB7
- *   init = -1
- *   xorout = -1
- *   reverse = yes
- *   check = crc(123456789) = 0xCBF43926
- */
-
-uint32 crc32_table[256] = {
-  0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
-  0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
-  0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
-  0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
-  0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
-  0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
-  0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
-  0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
-  0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
-  0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
-  0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
-  0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
-  0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
-  0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
-  0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
-  0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
-  0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
-  0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
-  0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
-  0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
-  0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
-  0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
-  0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
-  0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
-  0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
-  0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
-  0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
-  0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
-  0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
-  0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
-  0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
-  0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
-  0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
-  0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
-  0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
-  0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
-  0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
-  0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
-  0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
-  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
-  0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
-  0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
-  0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
-  0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
-  0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
-  0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
-  0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
-  0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
-  0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
-  0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
-  0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
-  0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
-  0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
-  0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
-  0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
-  0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
-  0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
-  0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
-  0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
-  0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
-  0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
-  0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
-  0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
-  0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
-};
-
 /*----- Functionc provided ------------------------------------------------*/
 
 /* --- @crc32@ --- *