chiark / gitweb /
Test universal hashing and fix bugs.
[mLib] / 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 -------------------------------------------------*/