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

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