chiark - git - mdw - mLib/blob - crc-mktab.c

   1 /* -*-c-*-
   2  *
   3  * $Id: crc-mktab.c,v 1.5 2003/12/15 20:53:47 mdw Exp $
   4  *
   5  * Build CRC tables
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of the mLib utilities library.
  13  *
  14  * mLib is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * mLib is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with mLib; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: crc-mktab.c,v $
  33  * Revision 1.5  2003/12/15 20:53:47  mdw
  34  * Add global unihash table; use universal hashing instead of CRC.
  35  *
  36  * Revision 1.4  2001/03/10 10:59:21  mdw
  37  * Fix generating tables where the chunk size is longer than the
  38  * polynomial.  Also fix output formatting when there aren't enough entries
  39  * to fill a line.
  40  *
  41  * Revision 1.3  2001/01/20 12:06:01  mdw
  42  * Define flags with macros, to ensure unsignedness.
  43  *
  44  * Revision 1.2  2000/10/08 11:07:21  mdw
  45  * With no arguments, give an error rather than spewing a big table at the
  46  * user.
  47  *
  48  * Revision 1.1  2000/07/21 19:01:33  mdw
  49  * Generate the CRC table rather than hardcoding it.
  50  *
  51  */
  52
  53 /*----- Header files ------------------------------------------------------*/
  54
  55 #include <ctype.h>
  56 #include <errno.h>
  57 #include <limits.h>
  58 #include <stdarg.h>
  59 #include <stdio.h>
  60 #include <stdlib.h>
  61 #include <string.h>
  62
  63 #include "mdwopt.h"
  64 #include "quis.h"
  65 #include "report.h"
  66
  67 /*----- Static variables --------------------------------------------------*/
  68
  69 static unsigned long poly = 0;
  70 static const char *guard = 0;
  71 static unsigned bits = 0;
  72 static unsigned chunk = 8;
  73 static const char *file = 0;
  74 static unsigned flags = 0;
  75 static const char *sym = 0;
  76 static const char *type = 0;
  77 static const char *inc = 0;
  78 static FILE *fp;
  79
  80 #define f_bogus 1u
  81 #define f_ctab 2u
  82 #define f_reverse 4u
  83
  84 #define BSCOL 72
  85
  86 /*----- Main code ---------------------------------------------------------*/
  87
  88 static unsigned long getint(const char *p, unsigned long max,
  89                             const char *what)
  90 {
  91   char *pp;
  92   unsigned long x = strtoul(p, &pp, 0);
  93   if (*pp || (max && x > max))
  94     die(EXIT_FAILURE, "bad %s `%s'", what, p);
  95   return (x);
  96 }
  97
  98 static void version(FILE *fp)
  99 {
 100   pquis(fp, "$, mLib version " VERSION "\n");
 101 }
 102
 103 static void usage(FILE *fp)
 104 {
 105   pquis(fp, "Usage: $ [-cr] [-o FILE] [-g GUARD] [-s SYM] [-i HEADER]\n\
 106         [-t TYPE] [-b BITS] [-B BITS] [-p POLY]\n");
 107 }
 108
 109 static void help(FILE *fp)
 110 {
 111   version(fp);
 112   putc('\n', stdout);
 113   usage(fp);
 114   fputs("\n\
 115 Emits a table containing precomuted values for CRC algorithms.  A number\n\
 116 of options are provided:\n\
 117 \n\
 118 -h, --help              Show this help text.\n\
 119 -v, --version           Show the program's version number.\n\
 120 -u, --usage             Show a terse usage message.\n\
 121 \n\
 122 -c, --c-source          Emit a C source file rather than a header.\n\
 123 -b, --bits=BITS         Emit a table for a BITS bits-wide CRC.\n\
 124 -B, --bit-chunk=BITS    Emit a table to process BITS bits at a time.\n\
 125 -p, --polynomial=POLY   Use the POLY as the dividing polynomial.\n\
 126 -r, --reverse           Create a `reversed' CRC table.\n\
 127 -g, --guard=GUARD       Use GUARD as a multiple-inclusion guard constant.\n\
 128 -i, --include=HEADER    Include HEADER at top of C source file.\n\
 129 -s, --symbol=SYM        Name the generated table SYM.\n\
 130 -t, --type=TYPE         Give the table entries type TYPE in C source.\n\
 131 -o, --output=FILE       Write the output to FILE.\n\
 132 ", stdout);
 133 }
 134
 135 unsigned long reflect(unsigned long x, unsigned b)
 136 {
 137   unsigned long y = 0;
 138   unsigned long xm, ym;
 139   unsigned i;
 140   if (!(flags & f_reverse))
 141     return (x);
 142   xm = 1;
 143   ym = 1 << (b - 1);
 144   for (i = 0; i < b; i++) {
 145     if (x & xm)
 146       y |= ym;
 147     xm <<= 1;
 148     ym >>= 1;
 149   }
 150   return (y);
 151 }
 152
 153 int main(int argc, char *argv[])
 154 {
 155   unsigned n, t, nw;
 156   unsigned max, i;
 157   unsigned long mask;
 158
 159   ego(argv[0]);
 160
 161   for (;;) {
 162     static struct option opts[] = {
 163       { "help",         0,              0,      'h' },
 164       { "version",      0,              0,      'v' },
 165       { "usage",        0,              0,      'u' },
 166
 167       { "output",       OPTF_ARGREQ,    0,      'o' },
 168       { "c-source",     0,              0,      'c' },
 169       { "symbol",       OPTF_ARGREQ,    0,      's' },
 170       { "type",         OPTF_ARGREQ,    0,      't' },
 171       { "include",      OPTF_ARGREQ,    0,      'i' },
 172       { "guard",        OPTF_ARGREQ,    0,      'g' },
 173
 174       { "bits",         OPTF_ARGREQ,    0,      'b' },
 175       { "bit-chunk",    OPTF_ARGREQ,    0,      'B' },
 176       { "polynomial",   OPTF_ARGREQ,    0,      'p' },
 177       { "reverse",      0,              0,      'r' },
 178
 179       { 0,              0,              0,      0 }
 180     };
 181     int i = mdwopt(argc, argv, "hvu o:cs:t:i:g: b:B:p:r", opts, 0, 0, 0);
 182
 183     if (i < 0)
 184       break;
 185     switch (i) {
 186       case 'h':
 187         help(stdout);
 188         exit(0);
 189       case 'v':
 190         version(stdout);
 191         exit(0);
 192       case 'u':
 193         usage(stdout);
 194         exit(0);
 195
 196       case 'o':
 197         file = optarg;
 198         break;
 199       case 'c':
 200         flags |= f_ctab;
 201         break;
 202       case 's':
 203         sym = optarg;
 204         break;
 205       case 't':
 206         type = optarg;
 207         break;
 208       case 'i':
 209         inc = optarg;
 210         break;
 211       case 'g':
 212         guard = optarg;
 213         break;
 214
 215       case 'b':
 216         bits = getint(optarg, 32, "CRC width");
 217         break;
 218       case 'B':
 219         chunk = getint(optarg, 32, "chunk size");
 220         break;
 221       case 'p':
 222         poly = getint(optarg, 0xffffffff, "CRC poly");
 223         break;
 224       case 'r':
 225         flags |= f_reverse;
 226         break;
 227
 228       default:
 229         flags |= f_bogus;
 230         break;
 231     }
 232   }
 233   if ((flags & f_bogus) || optind != argc) {
 234     usage(stderr);
 235     exit(EXIT_FAILURE);
 236   }
 237
 238   /* --- Sort out the various parameters --- */
 239
 240   if (!poly) {
 241     switch (bits) {
 242       case 16:
 243         if (flags & f_reverse)
 244           poly = 0x8408;
 245         else
 246           poly = 0x1021;
 247         break;
 248       case 32:
 249         poly = 0x04c11db7;
 250         flags |= f_reverse;
 251         bits = 32;
 252         break;
 253       case 0:
 254         die(EXIT_FAILURE, "no polynomial or bit width set");
 255         break;
 256       default:
 257         die(EXIT_FAILURE, "no standard polynomials for %u bits", bits);
 258         break;
 259     }
 260   }
 261
 262   if (!bits) {
 263     unsigned long x = poly;
 264     while (x > 1) {
 265       x >>= 8;
 266       bits += 8;
 267     }
 268   }
 269   nw = (bits + 3)/4;
 270
 271   if ((flags & f_ctab) && !type)
 272     type = bits > 16 ? "unsigned long" : "unsigned short";
 273
 274   /* --- Start output --- */
 275
 276   if (!file)
 277     fp = stdout;
 278   else {
 279     if (!(flags & f_ctab) && !guard) {
 280       char *p;
 281       const char *q;
 282       if ((p = malloc(strlen(file) + 1)) == 0)
 283         die(EXIT_FAILURE, "not enough memory");
 284       guard = p;
 285       for (q = file; *q; p++, q++) {
 286         if (isalnum((unsigned char)*q))
 287           *p = toupper((unsigned char)*q);
 288         else
 289           *p = '_';
 290       }
 291       *p++ = 0;
 292     }
 293     if ((fp = fopen(file, "w")) == 0)
 294       die(EXIT_FAILURE, "couldn't write `%s': %s", file, strerror(errno));
 295   }
 296
 297   if (!sym)
 298     sym = (flags & f_ctab) ? "crctab" : "CRC_TAB";
 299
 300   /* --- Dump out the first chunk of the file --- */
 301
 302   fprintf(fp, "\
 303 /* -*-c-*-\n\
 304  *\n\
 305  * CRC table (poly = %0*lx%s) [generated]\n\
 306  */\n\
 307 \n",
 308           nw, poly, flags & f_reverse ? "; reversed" : "");
 309
 310   if (flags & f_ctab) {
 311     if (inc)
 312       fprintf(fp, "#include \"%s\"\n\n", inc);
 313     fprintf(fp, "%s %s[] = {\n", type, sym);
 314   } else {
 315     int n;
 316     if (guard)
 317       fprintf(fp, "#ifndef %s\n#define %s\n\n", guard, guard);
 318     n = fprintf(fp, "#define %s {", sym);
 319     while (n < BSCOL) {
 320       fputc('\t', fp);
 321       n = (n + 8) & ~7;
 322     }
 323     fputc('\n', fp);
 324   }
 325
 326   /* --- Sort out the line width --- */
 327
 328   n = 1;
 329   while (2 + n * (nw + 4) < BSCOL)
 330     n <<= 1;
 331   n >>= 1;
 332   max = 1 << chunk;
 333   if (n > max)
 334     n = max;
 335   t = 0;
 336   while (((1 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
 337     t++;
 338
 339   /* --- Start grinding --- */
 340
 341   mask = 0xffffffff >> (32 - bits);
 342   fputc(' ', fp);
 343   for (i = 0; i < max; i++) {
 344     unsigned long x, y, z;
 345     unsigned j;
 346     unsigned ni, nn;
 347
 348     x = reflect(i, chunk);
 349     y = 0;
 350     nn = chunk;
 351     while (nn) {
 352       ni = bits;
 353       if (ni > nn)
 354         ni = nn;
 355       z = (x >> (nn - ni)) & (0xffffffff >> (32 - ni));
 356       y ^= z << (bits - ni);
 357       for (j = 0; j < ni; j++)
 358         y = ((y << 1) ^ (y & (1 << (bits - 1)) ? poly : 0)) & mask;
 359       nn -= ni;
 360     }
 361     x = reflect(y, bits);
 362
 363     fprintf(fp, " 0x%0*lx", nw, x);
 364     if (i == max - 1) {
 365       if (!(flags & f_ctab) && ((2 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
 366         fputc('\t', fp);
 367     } else
 368       fputc(',', fp);
 369     if (i + 1 == max || (i + 1)%n == 0) {
 370       if (!(flags & f_ctab)) {
 371         for (j = 0; j < t; j++)
 372           fputc('\t', fp);
 373         fputc('\\', fp);
 374       }
 375       fputc('\n', fp);
 376       if (i + 1 != max)
 377         fputc(' ', fp);
 378     }
 379   }
 380
 381   /* --- Done --- */
 382
 383   fputs(flags & f_ctab ? "};\n" : "}\n", fp);
 384   if (!(flags & f_ctab) && guard)
 385     fputs("\n#endif\n", fp);
 386
 387   return (0);
 388 }
 389
 390 /*----- That's all, folks -------------------------------------------------*/