| 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 -------------------------------------------------*/ |