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

   1 /* -*-c-*-
   2  *
   3  * $Id: crc-mktab.c,v 1.6 2004/04/08 01:36:11 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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include "config.h"
  33
  34 #include <ctype.h>
  35 #include <errno.h>
  36 #include <limits.h>
  37 #include <stdarg.h>
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41
  42 #include "mdwopt.h"
  43 #include "quis.h"
  44 #include "report.h"
  45
  46 /*----- Static variables --------------------------------------------------*/
  47
  48 static unsigned long poly = 0;
  49 static const char *guard = 0;
  50 static unsigned bits = 0;
  51 static unsigned chunk = 8;
  52 static const char *file = 0;
  53 static unsigned flags = 0;
  54 static const char *sym = 0;
  55 static const char *type = 0;
  56 static const char *inc = 0;
  57 static FILE *fp;
  58
  59 #define f_bogus 1u
  60 #define f_ctab 2u
  61 #define f_reverse 4u
  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: $ [-cr] [-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 -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 = 1 << (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       { "symbol",       OPTF_ARGREQ,    0,      's' },
 149       { "type",         OPTF_ARGREQ,    0,      't' },
 150       { "include",      OPTF_ARGREQ,    0,      'i' },
 151       { "guard",        OPTF_ARGREQ,    0,      'g' },
 152
 153       { "bits",         OPTF_ARGREQ,    0,      'b' },
 154       { "bit-chunk",    OPTF_ARGREQ,    0,      'B' },
 155       { "polynomial",   OPTF_ARGREQ,    0,      'p' },
 156       { "reverse",      0,              0,      'r' },
 157
 158       { 0,              0,              0,      0 }
 159     };
 160     int i = mdwopt(argc, argv, "hvu o:cs:t:i:g: b:B:p:r", opts, 0, 0, 0);
 161
 162     if (i < 0)
 163       break;
 164     switch (i) {
 165       case 'h':
 166         help(stdout);
 167         exit(0);
 168       case 'v':
 169         version(stdout);
 170         exit(0);
 171       case 'u':
 172         usage(stdout);
 173         exit(0);
 174
 175       case 'o':
 176         file = optarg;
 177         break;
 178       case 'c':
 179         flags |= f_ctab;
 180         break;
 181       case 's':
 182         sym = optarg;
 183         break;
 184       case 't':
 185         type = optarg;
 186         break;
 187       case 'i':
 188         inc = optarg;
 189         break;
 190       case 'g':
 191         guard = optarg;
 192         break;
 193
 194       case 'b':
 195         bits = getint(optarg, 32, "CRC width");
 196         break;
 197       case 'B':
 198         chunk = getint(optarg, 32, "chunk size");
 199         break;
 200       case 'p':
 201         poly = getint(optarg, 0xffffffff, "CRC poly");
 202         break;
 203       case 'r':
 204         flags |= f_reverse;
 205         break;
 206
 207       default:
 208         flags |= f_bogus;
 209         break;
 210     }
 211   }
 212   if ((flags & f_bogus) || optind != argc) {
 213     usage(stderr);
 214     exit(EXIT_FAILURE);
 215   }
 216
 217   /* --- Sort out the various parameters --- */
 218
 219   if (!poly) {
 220     switch (bits) {
 221       case 16:
 222         if (flags & f_reverse)
 223           poly = 0x8408;
 224         else
 225           poly = 0x1021;
 226         break;
 227       case 32:
 228         poly = 0x04c11db7;
 229         flags |= f_reverse;
 230         bits = 32;
 231         break;
 232       case 0:
 233         die(EXIT_FAILURE, "no polynomial or bit width set");
 234         break;
 235       default:
 236         die(EXIT_FAILURE, "no standard polynomials for %u bits", bits);
 237         break;
 238     }
 239   }
 240
 241   if (!bits) {
 242     unsigned long x = poly;
 243     while (x > 1) {
 244       x >>= 8;
 245       bits += 8;
 246     }
 247   }
 248   nw = (bits + 3)/4;
 249
 250   if ((flags & f_ctab) && !type)
 251     type = bits > 16 ? "unsigned long" : "unsigned short";
 252
 253   /* --- Start output --- */
 254
 255   if (!file)
 256     fp = stdout;
 257   else {
 258     if (!(flags & f_ctab) && !guard) {
 259       char *p;
 260       const char *q;
 261       if ((p = malloc(strlen(file) + 1)) == 0)
 262         die(EXIT_FAILURE, "not enough memory");
 263       guard = p;
 264       for (q = file; *q; p++, q++) {
 265         if (isalnum((unsigned char)*q))
 266           *p = toupper((unsigned char)*q);
 267         else
 268           *p = '_';
 269       }
 270       *p++ = 0;
 271     }
 272     if ((fp = fopen(file, "w")) == 0)
 273       die(EXIT_FAILURE, "couldn't write `%s': %s", file, strerror(errno));
 274   }
 275
 276   if (!sym)
 277     sym = (flags & f_ctab) ? "crctab" : "CRC_TAB";
 278
 279   /* --- Dump out the first chunk of the file --- */
 280
 281   fprintf(fp, "\
 282 /* -*-c-*-\n\
 283  *\n\
 284  * CRC table (poly = %0*lx%s) [generated]\n\
 285  */\n\
 286 \n",
 287           nw, poly, flags & f_reverse ? "; reversed" : "");
 288
 289   if (flags & f_ctab) {
 290     if (inc)
 291       fprintf(fp, "#include \"%s\"\n\n", inc);
 292     fprintf(fp, "%s %s[] = {\n", type, sym);
 293   } else {
 294     int n;
 295     if (guard)
 296       fprintf(fp, "#ifndef %s\n#define %s\n\n", guard, guard);
 297     n = fprintf(fp, "#define %s {", sym);
 298     while (n < BSCOL) {
 299       fputc('\t', fp);
 300       n = (n + 8) & ~7;
 301     }
 302     fputc('\n', fp);
 303   }
 304
 305   /* --- Sort out the line width --- */
 306
 307   n = 1;
 308   while (2 + n * (nw + 4) < BSCOL)
 309     n <<= 1;
 310   n >>= 1;
 311   max = 1 << chunk;
 312   if (n > max)
 313     n = max;
 314   t = 0;
 315   while (((1 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
 316     t++;
 317
 318   /* --- Start grinding --- */
 319
 320   mask = 0xffffffff >> (32 - bits);
 321   fputc(' ', fp);
 322   for (i = 0; i < max; i++) {
 323     unsigned long x, y, z;
 324     unsigned j;
 325     unsigned ni, nn;
 326
 327     x = reflect(i, chunk);
 328     y = 0;
 329     nn = chunk;
 330     while (nn) {
 331       ni = bits;
 332       if (ni > nn)
 333         ni = nn;
 334       z = (x >> (nn - ni)) & (0xffffffff >> (32 - ni));
 335       y ^= z << (bits - ni);
 336       for (j = 0; j < ni; j++)
 337         y = ((y << 1) ^ (y & (1 << (bits - 1)) ? poly : 0)) & mask;
 338       nn -= ni;
 339     }
 340     x = reflect(y, bits);
 341
 342     fprintf(fp, " 0x%0*lx", nw, x);
 343     if (i == max - 1) {
 344       if (!(flags & f_ctab) && ((2 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
 345         fputc('\t', fp);
 346     } else
 347       fputc(',', fp);
 348     if (i + 1 == max || (i + 1)%n == 0) {
 349       if (!(flags & f_ctab)) {
 350         for (j = 0; j < t; j++)
 351           fputc('\t', fp);
 352         fputc('\\', fp);
 353       }
 354       fputc('\n', fp);
 355       if (i + 1 != max)
 356         fputc(' ', fp);
 357     }
 358   }
 359
 360   /* --- Done --- */
 361
 362   fputs(flags & f_ctab ? "};\n" : "}\n", fp);
 363   if (!(flags & f_ctab) && guard)
 364     fputs("\n#endif\n", fp);
 365
 366   return (0);
 367 }
 368
 369 /*----- That's all, folks -------------------------------------------------*/