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

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