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