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