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