1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /*
28 * diagcode library, Sun Private API (PSARC/2004/601)
29 *
30 * undocumented debugging interface:
31 * set environment variable _FM_DC_DEBUG for debug prints to stderr.
32 * set it to 1 for extended error messages only.
33 * set it to 2 to include success info too on interesting functions.
34 * set it to 3 to include success info on trivial functions too.
35 * note that this environment variable is only examined in fm_dc_opendict().
36 */
37
38 #pragma ident "%Z%%M% %I% %E% SMI"
39
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43 #include <ctype.h>
44 #include <alloca.h>
45 #include <errno.h>
46
47 #include <fm/diagcode.h>
48
49 /* private (opaque to callers) handle information */
50 struct fm_dc_handle {
51 const char *dictname;
52 FILE *fp;
53 unsigned maxkey;
54 int version;
55 int debug;
56 /* name/value pairs from .dict header */
57 struct fm_dc_prop {
58 struct fm_dc_prop *next;
59 const char *lhs;
60 const char *rhs;
61 } *props;
62 };
63
64 /*
65 * parameters of the various sizes of diagcodes
66 *
67 * table must be in ascending order from smallest databits value to largest.
68 * when faced with more databits than the last entry, we know we have
69 * something that won't fit into a diagcode.
70 */
71 static const struct info {
72 int databits; /* number of bits used to hold dictionary value */
73 int numx; /* number of digits (also called X's) in code */
74 int csumbits; /* number of bits used for checksum */
75 int sizeval; /* value encoded into "size" field of code */
76 unsigned long long offset; /* databits==0 stands for this value */
77 } Info[] = {
78 /* diagcode is: dictname-XXXX-XX */
79 { 21, 6, 5, 0, 0ULL },
80
81 /* diagcode is: dictname-XXXX-XXXX-XX */
82 { 38, 10, 8, 1, 2097152ULL },
83
84 /* diagcode is: dictname-XXXX-XXXX-XXXX-XX */
85 { 55, 14, 11, 2, 274880004096ULL },
86
87 /* diagcode is: dictname-XXXX-XXXX-XXXX-XXXX-XX */
88 { 72, 18, 14, 3, 36029071898968064ULL }
89 };
90 #define MAXDATABITS 72 /* highest entry in table above */
91 #define MAXCODELEN 25 /* big enough to hold the X's, dashes, and \0 */
92
93 /* forward references for functions private to this file */
94 typedef struct bitv bitv;
95 static const struct info *dictval2info(const bitv *bv);
96 static const struct info *numx2info(int numx);
97 static void sortkey(const char *key[]);
98 static const char *keymatch(const char *linebuf, const char *key[]);
99 static int buildcode(fm_dc_handle_t *dhp, const char *rhsp,
100 char *code, size_t maxcode, char *debugstr);
101 static bitv *code2dictval(fm_dc_handle_t *dhp, const char *code);
102 struct parsestate {
103 char *parseptr; /* next unparsed character in buffer */
104 char *rhsp; /* rhs associated with last lhs (or NULL) */
105 };
106 static void startparse(struct parsestate *ps, char *ptr);
107 static char *nextlhs(struct parsestate *ps);
108 static char *nextrhs(struct parsestate *ps);
109 static bitv *bitv_alloc(void);
110 static void bitv_free(bitv *bv);
111 static void bitv_shift(bitv *bv, unsigned bits);
112 static void bitv_setlo(bitv *bv, unsigned bits, unsigned val);
113 static void bitv_shiftin(bitv *bv, unsigned bits, unsigned val);
114 static void bitv_shiftinv(bitv *bv, unsigned bits, const bitv *inbv);
115 static int bitv_bits(const bitv *bv);
116 static unsigned bitv_chunk(const bitv *bv, unsigned limbit, unsigned lobit);
117 static int bitv_mul(bitv *bv, unsigned long long val);
118 static int bitv_add(bitv *bv, unsigned long long val);
119 static int bitv_sub(bitv *bv, unsigned long long val);
120 static int bitv_ge(const bitv *bv, unsigned long long val);
121 static bitv *bitv_strparse(const char *s, int bits);
122 static int bitv_cmp(const bitv *bv1, const bitv *bv2);
123 static void crc(unsigned long *crcp, unsigned val);
124
125 #define DICTMAXLINE 10240 /* maximum expected dictionary line length */
126
127 #define MAXDEBUGSTR 100 /* for debug messages */
128
129 static const char Suffix[] = ".dict"; /* suffix on dictionary filename */
130 static const char Defaultpath[] = "/usr/lib/fm/dict";
131 static const char Debugenv[] = "_FM_DC_DEBUG"; /* debug environment var */
132
133 /* properties we look for at top of dictionary */
134 static const char Header[] = "FMDICT: ";
135 static const char Name[] = "name";
136 static const char Version[] = "version";
137 static const char Maxkey[] = "maxkey";
138
139 /* the alphabet used to encode information in a diagcode (base32 digits) */
140 static const char Alphabet[] = "0123456789ACDEFGHJKLMNPQRSTUVWXY";
141
142 /* open a dictionary, return opaque handle */
143 fm_dc_handle_t *
fm_dc_opendict(int version,const char * dirpath,const char * dictname)144 fm_dc_opendict(int version, const char *dirpath, const char *dictname)
145 {
146 int debug = 0; /* set by environment variable */
147 char *debugstr = ""; /* error path debug prefix text */
148 fm_dc_handle_t *dhp = NULL;
149 char *fname; /* full dict file name */
150 char linebuf[DICTMAXLINE]; /* line read from dict */
151 int line = 0; /* line number in dict */
152 unsigned prop_version = 0; /* version property from dict */
153 char *prop_name = ""; /* name property from dict */
154 char *lhsp; /* prop left-hand-side */
155 char *rhsp; /* prop right-hand-side */
156 struct parsestate pstate; /* for startparse(), nextlhs(), etc */
157
158 /* undocumented flag, given via environment variable */
159 if ((rhsp = getenv(Debugenv)) != NULL)
160 debug = atoi(rhsp);
161
162 if (debug > 1)
163 (void) fprintf(stderr,
164 "fm_dc_opendict: ver %d path \"%s\" dict \"%s\": ",
165 version, (dirpath == NULL) ? "NULL" : dirpath, dictname);
166 else if (debug)
167 debugstr = "fm_dc_opendict: "; /* used in error paths */
168
169 /* verify caller expects an API version we support */
170 if (version < 0 || version > FM_DC_VERSION) {
171 if (debug)
172 (void) fprintf(stderr, "%sENOTSUP ver not in [0-%d]\n",
173 debugstr, FM_DC_VERSION);
174 errno = ENOTSUP;
175 return (NULL);
176 }
177
178 /* caller can pass in NULL for default dirpath */
179 if (dirpath == NULL)
180 dirpath = Defaultpath;
181
182 /*
183 * allocate buffer for dirpath, slash, dictname, and suffix
184 * (sizeof (Suffix) includes the null).
185 */
186 fname = alloca(strlen(dirpath) + 1 +
187 strlen(dictname) + sizeof (Suffix));
188
189 /*
190 * allocate the handle.
191 *
192 * allocate the dictname copy kept in the handle.
193 *
194 * if any of these fail, send back ENOMEM.
195 */
196 if ((dhp = malloc(sizeof (*dhp))) == NULL ||
197 (dhp->dictname = strdup(dictname)) == NULL) {
198 if (dhp)
199 free(dhp);
200 if (debug)
201 (void) fprintf(stderr, "%sENOMEM\n", debugstr);
202 errno = ENOMEM;
203 return (NULL);
204 }
205
206 /* initialize the handle */
207 (void) strcpy(fname, dirpath);
208 (void) strcat(fname, "/");
209 (void) strcat(fname, dictname);
210 (void) strcat(fname, Suffix);
211 dhp->fp = NULL;
212 dhp->maxkey = 0;
213 dhp->version = version;
214 dhp->debug = debug;
215 dhp->props = NULL;
216
217 /* open the dictionary */
218 if (debug > 1)
219 (void) fprintf(stderr, "\"%s\": ", fname);
220 if ((dhp->fp = fopen(fname, "r")) == NULL) {
221 int oerrno = errno; /* fopen() set errno to something */
222
223 if (debug > 1)
224 perror("fopen");
225 else if (debug) {
226 (void) fprintf(stderr, "%s%s: ", debugstr, fname);
227 errno = oerrno;
228 perror("fopen");
229 }
230 fm_dc_closedict(dhp);
231 errno = oerrno;
232 return (NULL);
233 }
234
235 /* pull in the header line and parse it */
236 while (fgets(linebuf, DICTMAXLINE, dhp->fp) != NULL) {
237 line++;
238 if (*linebuf == '\n' || *linebuf == '#')
239 continue;
240
241 /* first non-comment, non-blank line must be header */
242 if (strncmp(linebuf, Header, sizeof (Header) - 1)) {
243 fm_dc_closedict(dhp);
244 if (debug)
245 (void) fprintf(stderr,
246 "%sEINVAL: line %d: header expected.\n",
247 debugstr, line);
248 errno = EINVAL;
249 return (NULL);
250 }
251
252 /* just wanted header line for now */
253 break;
254 }
255
256 /* walk through name=value pairs in line after Header string */
257 startparse(&pstate, &linebuf[sizeof (Header) - 1]);
258 while ((lhsp = nextlhs(&pstate)) != NULL) {
259 struct fm_dc_prop *propp;
260
261 if ((rhsp = nextrhs(&pstate)) == NULL) {
262 if (debug)
263 (void) fprintf(stderr, "%sEINVAL "
264 "%s prop has no value\n", debugstr, lhsp);
265 fm_dc_closedict(dhp);
266 errno = EINVAL;
267 return (NULL);
268 }
269
270 propp = malloc(sizeof (*propp));
271 if (propp == NULL ||
272 (propp->lhs = strdup(lhsp)) == NULL ||
273 (propp->rhs = strdup(rhsp)) == NULL) {
274 if (debug)
275 (void) fprintf(stderr, "%sENOMEM\n", debugstr);
276 if (propp != NULL) {
277 if (propp->lhs != NULL)
278 free((void *) propp->lhs);
279 free((void *) propp);
280 }
281 fm_dc_closedict(dhp);
282 errno = ENOMEM;
283 return (NULL);
284 }
285 propp->next = dhp->props;
286 dhp->props = propp;
287
288 if (strcmp(lhsp, Name) == 0)
289 prop_name = rhsp;
290 else if (strcmp(lhsp, Version) == 0)
291 prop_version = strtoul(rhsp, NULL, 0);
292 else if (strcmp(lhsp, Maxkey) == 0)
293 dhp->maxkey = strtoul(rhsp, NULL, 0);
294 }
295
296 /*
297 * require version 1, expected dict name, and maxkey values
298 * (note we use "1" here and not FM_DC_VERSION because this code
299 * implements version 1, so the check below should not float to
300 * newer version numbers if the header file defines them.)
301 */
302 if (prop_version != 1UL || strcmp(prop_name, dictname) ||
303 dhp->maxkey == 0) {
304 fm_dc_closedict(dhp);
305 if (debug)
306 (void) fprintf(stderr,
307 "%sEINVAL ver %d name \"%s\" maxkey %d\n",
308 debugstr, prop_version, prop_name, dhp->maxkey);
309 errno = EINVAL;
310 return (NULL);
311 }
312
313 if (debug > 1)
314 (void) fprintf(stderr, "fm_dc_opendict: dhp 0x%p\n",
315 (void *)dhp);
316 return (dhp);
317 }
318
319 /* close a dictionary */
320 void
fm_dc_closedict(fm_dc_handle_t * dhp)321 fm_dc_closedict(fm_dc_handle_t *dhp)
322 {
323 struct fm_dc_prop *props;
324 struct fm_dc_prop *oprops;
325
326 if (dhp->debug > 1)
327 (void) fprintf(stderr, "fm_dc_closedict: dhp 0x%p\n",
328 (void *)dhp);
329 if (dhp->fp)
330 (void) fclose(dhp->fp);
331
332 free((void *) dhp->dictname);
333
334 props = dhp->props;
335 while (props) {
336 if (props->lhs != NULL)
337 free((void *) props->lhs);
338 if (props->rhs != NULL)
339 free((void *) props->rhs);
340 oprops = props;
341 props = props->next;
342 free((void *) oprops);
343 }
344
345 free(dhp);
346 }
347
348 /* return maximum length (in bytes) of diagcodes for a given dictionary */
349 size_t
fm_dc_codelen(fm_dc_handle_t * dhp)350 fm_dc_codelen(fm_dc_handle_t *dhp)
351 {
352 size_t len = strlen(dhp->dictname);
353
354 /* only one version so far, so dhp->version isn't checked */
355
356 if (dhp->debug > 2)
357 (void) fprintf(stderr, "fm_dc_codelen: dhp 0x%p: %d\n",
358 (void *)dhp, (int)(len + MAXCODELEN));
359 return (len + MAXCODELEN);
360 }
361
362 /* return number of strings in key for a given dictionary */
363 int
fm_dc_maxkey(fm_dc_handle_t * dhp)364 fm_dc_maxkey(fm_dc_handle_t *dhp)
365 {
366 /* only one version so far, so dhp->version isn't checked */
367
368 /* this interface counts the NULL entry */
369 if (dhp->debug > 2)
370 (void) fprintf(stderr, "fm_dc_maxkey: dhp 0x%p: maxkey %d\n",
371 (void *)dhp, dhp->maxkey + 1);
372 return (dhp->maxkey + 1);
373 }
374
375 /* given a key, construct a diagcode */
376 int
fm_dc_key2code(fm_dc_handle_t * dhp,const char * key[],char * code,size_t maxcode)377 fm_dc_key2code(fm_dc_handle_t *dhp,
378 const char *key[], char *code, size_t maxcode)
379 {
380 char *debugstr = ""; /* error path debug prefix text */
381 int line = 0; /* line number in dict */
382 char linebuf[DICTMAXLINE]; /* line read from dict */
383 const char *rhsp; /* right-hand-side of entry */
384
385 /* only one version so far, so dhp->version isn't checked */
386
387 if (dhp->debug > 1) {
388 int nel;
389
390 (void) fprintf(stderr,
391 "fm_dc_key2code: dhp 0x%p maxcode %lu ", (void *)dhp,
392 (ulong_t)maxcode);
393 for (nel = 0; key[nel]; nel++)
394 (void) fprintf(stderr, "\"%s\" ", key[nel]);
395 } else if (dhp->debug)
396 debugstr = "fm_dc_key2code: ";
397
398 /* sort the keys */
399 sortkey(key);
400
401 rewind(dhp->fp);
402
403 while (fgets(linebuf, DICTMAXLINE, dhp->fp) != NULL) {
404 line++;
405 if (*linebuf == '\n' || *linebuf == '#')
406 continue;
407
408 /* first non-comment, non-blank line must be header */
409 if (strncmp(linebuf, Header, sizeof (Header) - 1) == 0)
410 continue;
411
412 if ((rhsp = keymatch(linebuf, key)) != NULL) {
413 char ndebugstr[MAXDEBUGSTR];
414
415 if (dhp->debug > 1)
416 (void) fprintf(stderr, "match line %d: ", line);
417 else {
418 (void) snprintf(ndebugstr, MAXDEBUGSTR,
419 "fm_dc_key2code: dictionary line %d",
420 line);
421 debugstr = ndebugstr;
422 }
423
424 return (buildcode(dhp, rhsp, code, maxcode, debugstr));
425 }
426 }
427
428 /* no match */
429 if (dhp->debug)
430 (void) fprintf(stderr, "%sENOMSG no match\n", debugstr);
431 errno = ENOMSG;
432 return (-1);
433 }
434
435 /* given a diagcode, return the key (array of strings) */
436 int
fm_dc_code2key(fm_dc_handle_t * dhp,const char * code,char * key[],int maxkey)437 fm_dc_code2key(fm_dc_handle_t *dhp, const char *code,
438 char *key[], int maxkey)
439 {
440 char *debugstr = ""; /* error path debug prefix text */
441 int line = 0;
442 char linebuf[DICTMAXLINE];
443 bitv *dictval;
444
445 /* only one version so far, so dhp->version isn't checked */
446
447 if (dhp->debug > 1)
448 (void) fprintf(stderr,
449 "fm_dc_code2key: dhp 0x%p code \"%s\" maxkey %d: ",
450 (void *)dhp, code, maxkey);
451 else if (dhp->debug)
452 debugstr = "fm_dc_code2key: ";
453
454 /* convert code back to bit vector */
455 if ((dictval = code2dictval(dhp, code)) == NULL) {
456 /* code2dictval() sets errno */
457 if (dhp->debug) {
458 int oerrno = errno;
459
460 /* handle expected types without printing a number */
461 if (errno == ENOMEM)
462 (void) fprintf(stderr,
463 "%sENOMEM code2dictval\n",
464 debugstr);
465 else if (errno == EINVAL)
466 (void) fprintf(stderr,
467 "%sEINVAL code2dictval\n",
468 debugstr);
469 else
470 (void) fprintf(stderr,
471 "%scode2dictval error %d\n",
472 debugstr, oerrno);
473 errno = oerrno;
474 }
475 return (-1);
476 }
477
478 rewind(dhp->fp);
479
480 while (fgets(linebuf, DICTMAXLINE, dhp->fp) != NULL) {
481 char *ptr;
482 bitv *thisval;
483 char *beginp;
484 char *endp;
485 int nel;
486
487 line++;
488 if (*linebuf == '\n' || *linebuf == '#')
489 continue;
490
491 /* first non-comment, non-blank line must be header */
492 if (strncmp(linebuf, Header, sizeof (Header) - 1) == 0)
493 continue;
494
495 if ((ptr = strchr(linebuf, '=')) == NULL)
496 continue; /* ignore malformed entries */
497
498 *ptr++ = '\0';
499
500 /* pull in value from dictionary */
501 if ((thisval = bitv_strparse(ptr, MAXDATABITS)) == NULL) {
502 /* bitv_strparse() sets errno */
503 if (errno == ENOMEM) {
504 bitv_free(dictval);
505 if (dhp->debug)
506 (void) fprintf(stderr,
507 "%sENOMEM bitv_strparse\n",
508 debugstr);
509 errno = ENOMEM;
510 return (-1);
511 }
512 /* other than ENOMEM, trudge on... */
513 continue;
514 }
515
516 if (bitv_cmp(thisval, dictval)) {
517 bitv_free(thisval);
518 continue;
519 }
520
521 /* if we got here, we found the match */
522 bitv_free(thisval);
523 bitv_free(dictval);
524 beginp = linebuf;
525 nel = 0;
526 for (;;) {
527 while (*beginp && isspace(*beginp))
528 beginp++;
529 if (*beginp == '\0') {
530 /* all done */
531 key[nel] = NULL;
532 return (0);
533 }
534 if (nel >= maxkey - 1) {
535 if (dhp->debug)
536 (void) fprintf(stderr,
537 "%sENOMEM maxkey %d\n",
538 debugstr, maxkey);
539 errno = ENOMEM;
540 return (-1);
541 }
542 for (endp = beginp; *endp && !isspace(*endp); endp++)
543 ;
544 if (*endp)
545 *endp++ = '\0';
546 if ((key[nel++] = strdup(beginp)) == NULL) {
547 if (dhp->debug)
548 (void) fprintf(stderr,
549 "%sENOMEM strdup\n", debugstr);
550 errno = ENOMEM;
551 return (-1);
552 }
553 beginp = endp;
554 }
555 }
556
557 bitv_free(dictval);
558 if (dhp->debug)
559 (void) fprintf(stderr, "%sENOMSG\n", debugstr);
560 errno = ENOMSG;
561 return (-1);
562 }
563
564 /* return the right-hand side of a names property from the dict header */
565 const char *
fm_dc_getprop(fm_dc_handle_t * dhp,const char * name)566 fm_dc_getprop(fm_dc_handle_t *dhp, const char *name)
567 {
568 struct fm_dc_prop *props;
569
570 /* only one version so far, so dhp->version isn't checked */
571
572 if (dhp->debug > 2)
573 (void) fprintf(stderr, "fm_dc_getprop: dhp 0x%p: \"%s\"",
574 (void *)dhp, name);
575
576 for (props = dhp->props; props; props = props->next)
577 if (strcmp(name, props->lhs) == 0)
578 break;
579
580 if (dhp->debug > 2)
581 (void) fprintf(stderr, "= \"%s\"\n",
582 (props == NULL) ? "NULL" : props->rhs);
583
584 return ((props == NULL) ? NULL : props->rhs);
585 }
586
587 /* find the appropriate diagcode format for a given dictval */
588 static const struct info *
dictval2info(const bitv * bv)589 dictval2info(const bitv *bv)
590 {
591 int i;
592
593 for (i = 0; i < sizeof (Info) / sizeof (*Info) - 1; i++)
594 if (!bitv_ge(bv, Info[i + 1].offset))
595 return (&Info[i]);
596
597 /* return largest format */
598 return (&Info[sizeof (Info) / sizeof (*Info) - 1]);
599 }
600
601 /* lookup the diagcode parameters given the number of X's used */
602 static const struct info *
numx2info(int numx)603 numx2info(int numx)
604 {
605 int i;
606
607 for (i = 0; i < sizeof (Info) / sizeof (*Info); i++)
608 if (numx == Info[i].numx)
609 return (&Info[i]);
610
611 return (NULL);
612 }
613
614 /* for use with qsort() */
615 static int
mycmp(const void * a,const void * b)616 mycmp(const void *a, const void *b)
617 {
618 return (strcmp(*(char **)a, *(char **)b));
619 }
620
621 /*
622 * sortkey -- make sure key[] array is lexically sorted and without repeats
623 */
624 static void
sortkey(const char * key[])625 sortkey(const char *key[])
626 {
627 int nel;
628 int srci; /* source index when iterating through key[] */
629 int dsti; /* dest index when storing elements in key[] */
630
631 /* count the number of elements in key[] */
632 for (nel = 0; key[nel]; nel++)
633 ;
634
635 if (nel < 2)
636 return; /* nothing to sort */
637
638 qsort((void *)key, nel, sizeof (char *), mycmp);
639
640 /* go through array and remove repeats */
641 dsti = 1;
642 for (srci = 1; srci < nel; srci++)
643 if (strcmp(key[srci], key[dsti - 1]) != 0)
644 key[dsti++] = key[srci];
645 key[dsti] = NULL;
646 }
647
648 /*
649 * keymatch -- check for matching line from the dictionary
650 *
651 * assumes that the key[] array has already been lexically sorted.
652 * returns NULL if no match, otherwise pointer to first character of RHS.
653 */
654 static const char *
keymatch(const char * linebuf,const char * key[])655 keymatch(const char *linebuf, const char *key[])
656 {
657 int keynum = 0;
658 const char *ptr;
659
660 while (linebuf) {
661 /* skip any initial whitespace in front of name */
662 while (*linebuf && isspace(*linebuf))
663 linebuf++;
664
665 ptr = key[keynum];
666
667 if (ptr == NULL && *linebuf == '=') {
668 /* match */
669 linebuf++;
670 while (*linebuf && isspace(*linebuf))
671 linebuf++;
672 return (linebuf);
673 } else if (ptr == NULL)
674 return (NULL); /* dict had more strings for key */
675
676 /* match the string */
677 while (*linebuf)
678 if (*ptr == '\0') {
679 if (isspace(*linebuf) || *linebuf == '=')
680 break; /* match */
681 else
682 return (NULL); /* dict string longer */
683 } else if (*linebuf != *ptr)
684 return (NULL); /* string don't match */
685 else {
686 linebuf++;
687 ptr++;
688 }
689
690 keynum++;
691 }
692
693 return (NULL); /* no match */
694 }
695
696 /*
697 * buildcode -- given the val from the dictionary, create the diagcode
698 */
699 static int
buildcode(fm_dc_handle_t * dhp,const char * rhsp,char * code,size_t maxcode,char * debugstr)700 buildcode(fm_dc_handle_t *dhp, const char *rhsp,
701 char *code, size_t maxcode, char *debugstr)
702 {
703 char *codebegin = code; /* remember start of code buffer */
704 const struct info *infop; /* Info[] table entry */
705 unsigned long csum = 0; /* checksum (CRC) of diagcode */
706 const char *ptr;
707 bitv *dictval; /* value from dictionary */
708 bitv *allbits; /* assembled diagcode in binary */
709 int bit; /* for looping through bits */
710 int limbit; /* upper bit limit when looping */
711
712 /* sanity check that buffer is large enough for diagcode */
713 if (maxcode < fm_dc_codelen(dhp)) {
714 if (dhp->debug)
715 (void) fprintf(stderr,
716 "%sENOMEM maxcode %lu < codelen %lu\n",
717 debugstr, (ulong_t)maxcode,
718 (ulong_t)fm_dc_codelen(dhp));
719 errno = ENOMEM;
720 return (-1);
721 }
722
723 /* handle dictname part of checksum */
724 for (ptr = dhp->dictname; *ptr; ptr++) {
725 crc(&csum, (unsigned)*ptr);
726 *code++ = *ptr;
727 }
728
729 /* pull in value from dictionary */
730 if ((dictval = bitv_strparse(rhsp, MAXDATABITS)) == NULL) {
731 /* bitv_strparse() sets errno */
732 if (dhp->debug) {
733 int oerrno = errno;
734
735 /* handle expected types without printing a number */
736 if (errno == ENOMEM)
737 (void) fprintf(stderr,
738 "%sENOMEM bitv_strparse\n",
739 debugstr);
740 else if (errno == ERANGE)
741 (void) fprintf(stderr,
742 "%sERANGE bitv_strparse\n",
743 debugstr);
744 else
745 (void) fprintf(stderr,
746 "%sbitv_strparse error %d\n",
747 debugstr, oerrno);
748 errno = oerrno;
749 }
750 return (-1);
751 }
752
753 /* determine which format of code we're using */
754 infop = dictval2info(dictval);
755
756 /* subtract off the offset appropriate for format of code */
757 if (dhp->debug > 3)
758 (void) fprintf(stderr,
759 "%ssubtract offset %llu\n", debugstr, infop->offset);
760 if (bitv_sub(dictval, infop->offset) < 0) {
761 /*
762 * this "cannot happen" since code format was chosen
763 * so that offset will be smaller than dictval, and
764 * dictval cannot be out of range since bitv_strparse()
765 * should have caught it.
766 */
767 if (dhp->debug)
768 (void) fprintf(stderr,
769 "%sERANGE from bitv_sub\n", debugstr);
770 bitv_free(dictval);
771 errno = ERANGE;
772 return (-1);
773 }
774
775 /* assemble all the bits for the diagcode */
776 if ((allbits = bitv_alloc()) == NULL) {
777 bitv_free(dictval);
778 if (dhp->debug)
779 (void) fprintf(stderr,
780 "%sENOMEM from bitv_alloc\n", debugstr);
781 errno = ENOMEM;
782 return (-1);
783 }
784
785 /*
786 * construct the full diagcode by shifting in information:
787 * - 2 bit code type, set to 01
788 * - 2 bit size field
789 * - the databits of the dictionary code itself
790 */
791
792 bitv_shiftin(allbits, 2, 1);
793 bitv_shiftin(allbits, 2, infop->sizeval);
794 bitv_shiftinv(allbits, infop->databits, dictval);
795
796 /* insert zeros for checksum */
797 bitv_shiftin(allbits, infop->csumbits, 0);
798
799 /* compute checksum */
800 limbit = infop->numx * 5;
801 for (bit = 0; bit < infop->numx; bit++) {
802 crc(&csum, bitv_chunk(allbits, limbit, limbit - 5));
803 limbit -= 5;
804 }
805
806 /* insert the computed checksum */
807 bitv_setlo(allbits, infop->csumbits, (unsigned)csum);
808
809 /* encode binary values according to alphabet */
810 limbit = infop->numx * 5;
811 for (bit = 0; bit < infop->numx; bit++) {
812 if (bit % 4 == 0)
813 *code++ = '-';
814 *code++ = Alphabet[bitv_chunk(allbits, limbit, limbit - 5)];
815 limbit -= 5;
816 }
817
818 *code = '\0';
819 bitv_free(allbits);
820 bitv_free(dictval);
821
822 if (dhp->debug > 1)
823 (void) fprintf(stderr, "code \"%s\"\n", codebegin);
824 return (0);
825 }
826
827 /*
828 * code2dictval -- convert a diagcode back to a bit vector
829 */
830 static bitv *
code2dictval(fm_dc_handle_t * dhp,const char * code)831 code2dictval(fm_dc_handle_t *dhp, const char *code)
832 {
833 const struct info *infop;
834 int len = strlen(dhp->dictname);
835 bitv *allbits;
836 bitv *dictval;
837 int numx; /* number of X's we count */
838 unsigned long ocsum; /* original checksum in code */
839 unsigned long csum; /* our computed checksum */
840 int bit; /* for looping through bits */
841 int limbit; /* upper bit limit when looping */
842 const char *ptr;
843
844 /* check dictname part of code */
845 if (strncasecmp(code, dhp->dictname, len) ||
846 code[len] != '-') {
847 errno = EINVAL;
848 return (NULL);
849 }
850
851 /* convert code back to a bit vector */
852 if ((allbits = bitv_alloc()) == NULL) {
853 errno = ENOMEM;
854 return (NULL);
855 }
856
857 /* we verified it began with dictname and a dash, so skip it */
858 code = &code[len + 1];
859 numx = 0;
860 /* be forgiving about misplaced dashes */
861 for (; *code; code++)
862 if (*code == '-')
863 continue;
864 else {
865 unsigned val;
866
867 for (val = 0; Alphabet[val]; val++)
868 if (*code == Alphabet[val])
869 break;
870 if (Alphabet[val] == '\0') {
871 bitv_free(allbits);
872 errno = EINVAL;
873 return (NULL);
874 }
875 bitv_shiftin(allbits, 5, val);
876 numx++;
877 }
878
879 if ((infop = numx2info(numx)) == NULL) {
880 bitv_free(allbits);
881 errno = EINVAL;
882 return (NULL);
883 }
884
885 /* now pull out the csum */
886 ocsum = bitv_chunk(allbits, infop->csumbits, 0);
887
888 /* set the csum bits to zero */
889 bitv_setlo(allbits, infop->csumbits, 0);
890
891 /* calculate the checksum and see if it matches */
892 csum = 0;
893 for (ptr = dhp->dictname; *ptr; ptr++)
894 crc(&csum, (unsigned)*ptr);
895 limbit = numx * 5;
896 for (bit = 0; bit < numx; bit++) {
897 crc(&csum, bitv_chunk(allbits, limbit, limbit - 5));
898 limbit -= 5;
899 }
900 csum &= (1 << infop->csumbits) - 1;
901
902 if (csum != ocsum) {
903 bitv_free(allbits);
904 errno = EINVAL;
905 return (NULL);
906 }
907
908 /* code looks okay, just return dictval portion */
909 if ((dictval = bitv_alloc()) == NULL) {
910 bitv_free(allbits);
911 errno = ENOMEM;
912 return (NULL);
913 }
914 limbit = infop->csumbits + infop->databits;
915 while (limbit > infop->csumbits) {
916 bitv_shiftin(dictval, 1,
917 bitv_chunk(allbits, limbit, limbit - 1));
918 limbit--;
919 }
920 bitv_free(allbits);
921
922 /* add in the offset appropriate for the length of code being used */
923 if (bitv_add(dictval, infop->offset) < 0) {
924 /*
925 * overflow "cannot happen" since we've pulled in
926 * a given number of bits from the code and the offset
927 * is designed not to overflow...
928 */
929 bitv_free(dictval);
930 errno = ERANGE;
931 return (NULL);
932 }
933
934 return (dictval);
935 }
936
937
938 /*
939 * private routines to parse a line into name/value pairs...
940 *
941 */
942
943 /*
944 * startparse -- record starting of buffer containing name=value pairs
945 */
946 static void
startparse(struct parsestate * ps,char * ptr)947 startparse(struct parsestate *ps, char *ptr)
948 {
949 ps->parseptr = ptr;
950 }
951
952 /*
953 * nextlhs -- return next left-hand-side of name=value pair, or NULL
954 *
955 * whitespace around the '=' is allowed for, but not required. the
956 * lhs is a simple string that does not contain any whitespace or an
957 * embedded equals sign. no escaped characters, quotes, etc. are
958 * honored here.
959 *
960 * this routine also parses the rhs and saves a pointer to it
961 * in Rhsp so that nextrhs() can return it. if nextrhs() never
962 * gets called, we continue looking for the next lhs *after* any
963 * rhs that was there.
964 */
965 static char *
nextlhs(struct parsestate * ps)966 nextlhs(struct parsestate *ps)
967 {
968 char *lhsp;
969 char *copyto;
970 int equals = 0;
971 int quote = 0;
972 int backslash = 0;
973
974 /* skip whitespace */
975 while (*ps->parseptr && isspace(*ps->parseptr))
976 ps->parseptr++;
977
978 /* anything left? */
979 if (*ps->parseptr == '\0')
980 return (NULL);
981
982 /* remember start of lhs, assume no rhs until we see '=' */
983 lhsp = ps->parseptr;
984
985 /* find end of token, no escaped chars, quotes, etc. on lhs */
986 while (*ps->parseptr && !isspace(*ps->parseptr))
987 if (*ps->parseptr == '=') {
988 equals = 1;
989 break;
990 } else
991 ps->parseptr++;
992
993 /* null terminate the token, possibly nuking the '=' itself */
994 *ps->parseptr++ = '\0';
995
996 /* if we haven't seen an '=', see if it happens after whitespace */
997 if (!equals) {
998 while (*ps->parseptr && isspace(*ps->parseptr))
999 ps->parseptr++;
1000 if (*ps->parseptr == '=') {
1001 equals = 1;
1002 ps->parseptr++;
1003 }
1004 }
1005
1006 /* skip whitespace */
1007 while (*ps->parseptr && isspace(*ps->parseptr))
1008 ps->parseptr++;
1009
1010 /* isolate the rhs if it is there */
1011 if (!equals || *ps->parseptr == '\0') {
1012 ps->rhsp = NULL;
1013 return (lhsp);
1014 }
1015
1016 if (*ps->parseptr == '"') {
1017 quote = 1;
1018 ps->parseptr++;
1019 }
1020
1021 /* remember the beginning of the rhs */
1022 ps->rhsp = copyto = ps->parseptr;
1023
1024 /* now scan to the end of the rhs */
1025 while (*ps->parseptr) {
1026 if (backslash) {
1027 switch (*ps->parseptr) {
1028 case 't':
1029 *copyto++ = '\t';
1030 break;
1031
1032 case 'r':
1033 *copyto++ = '\r';
1034 break;
1035
1036 case 'n':
1037 *copyto++ = '\n';
1038 break;
1039
1040 case 'f':
1041 *copyto++ = '\f';
1042 break;
1043
1044 default:
1045 *copyto++ = *ps->parseptr;
1046 break;
1047 }
1048
1049 backslash = 0;
1050 } else if (*ps->parseptr == '\\')
1051 backslash = 1;
1052 else if (quote) {
1053 if (*ps->parseptr == '"') {
1054 ps->parseptr++;
1055 break; /* end of quoted string */
1056 } else
1057 *copyto++ = *ps->parseptr;
1058 } else if (!isspace(*ps->parseptr))
1059 *copyto++ = *ps->parseptr;
1060 else {
1061 ps->parseptr++;
1062 break; /* rhs terminated by whitespace */
1063 }
1064
1065 ps->parseptr++;
1066 }
1067 *copyto = '\0';
1068
1069 return (lhsp);
1070 }
1071
1072 /*
1073 * nextrhs -- return right-hand-side of name=value pair, or NULL
1074 *
1075 * this routine can only be used after a lhs has been found with
1076 * nextlhs(). the rhs consists of a string with no whitespace in it,
1077 * unless the whitespace is escaped with a backslash. surrounding
1078 * a string with double quotes is also supported here, as are the
1079 * common C escape sequences like \t and \n.
1080 *
1081 * nextlhs() actually does all the hard work. we just return any
1082 * rhs that was found by that routine.
1083 */
1084 static char *
nextrhs(struct parsestate * ps)1085 nextrhs(struct parsestate *ps)
1086 {
1087 return (ps->rhsp);
1088 }
1089
1090
1091 /*
1092 * private routines to manipulate bit vectors (i.e. large integers)
1093 *
1094 * if these bit vector routines are ever supposed to be more
1095 * general, the desired length should be passed in to bitv_alloc()
1096 * instead of defining a maximum here. but knowing the max ahead
1097 * of time allows for simpler code and we know the max that will
1098 * fit into a diagcode. on the minimum side, the below define
1099 * must be at least sizeof (unsigned).
1100 */
1101 #define BITV_MAX_BYTES 15
1102
1103 /* data structure used to hold a bit vector */
1104 struct bitv {
1105 unsigned char v[BITV_MAX_BYTES];
1106 };
1107
1108 /* allocate a new, zeroed out bit vector */
1109 static bitv *
bitv_alloc(void)1110 bitv_alloc(void)
1111 {
1112 int i;
1113 struct bitv *bv = malloc(sizeof (*bv));
1114
1115 if (bv)
1116 for (i = 0; i < BITV_MAX_BYTES; i++)
1117 bv->v[i] = 0;
1118
1119 return (bv);
1120 }
1121
1122 /* free a bit vector that was allocated with bitv_alloc() */
1123 static void
bitv_free(bitv * bv)1124 bitv_free(bitv *bv)
1125 {
1126 free(bv);
1127 }
1128
1129 /* shift left a bit vector by a given number of bits. fill with zeros. */
1130 static void
bitv_shift(bitv * bv,unsigned bits)1131 bitv_shift(bitv *bv, unsigned bits)
1132 {
1133 while (bits > 0) {
1134 unsigned iterbits = bits;
1135 int i;
1136
1137 /* how many bits this iteration? 8 max. */
1138 if (iterbits > 8)
1139 iterbits = 8;
1140
1141 for (i = BITV_MAX_BYTES - 1; i > 0; i--) {
1142 bv->v[i] <<= iterbits;
1143 bv->v[i] |= bv->v[i - 1] >> (8 - iterbits);
1144 }
1145 bv->v[0] <<= iterbits;
1146
1147 bits -= iterbits;
1148 }
1149 }
1150
1151 /* force a given number of bits to a specific value */
1152 static void
bitv_setlo(bitv * bv,unsigned bits,unsigned val)1153 bitv_setlo(bitv *bv, unsigned bits, unsigned val)
1154 {
1155 int i = 0;
1156
1157 /* assumption: bits * 8 <= sizeof (val) */
1158
1159 while (bits > 0) {
1160 unsigned iterbits = bits;
1161 unsigned mask;
1162
1163 if (iterbits > 8)
1164 iterbits = 8;
1165
1166 mask = (1 << iterbits) - 1;
1167
1168 bv->v[i] &= ~mask;
1169 bv->v[i] |= val & mask;
1170
1171 val >>= iterbits;
1172 bits -= iterbits;
1173 /*
1174 * the following can't go off end of bv->v[] since
1175 * BITV_MAX_BYTES is assumed to be at least sizeof
1176 * unsigned and val can't be more than sizeof unsigned
1177 * bytes long.
1178 */
1179 i++;
1180 }
1181 }
1182
1183 /* given a value and number of bits, shift it in from the right */
1184 static void
bitv_shiftin(bitv * bv,unsigned bits,unsigned val)1185 bitv_shiftin(bitv *bv, unsigned bits, unsigned val)
1186 {
1187 bitv_shift(bv, bits);
1188 bitv_setlo(bv, bits, val);
1189 }
1190
1191 /* given a bit vector and a number of bits, shift it in from the right */
1192 static void
bitv_shiftinv(bitv * bv,unsigned bits,const bitv * inbv)1193 bitv_shiftinv(bitv *bv, unsigned bits, const bitv *inbv)
1194 {
1195 int byteindex = bits / 8;
1196 int iterbits = bits % 8;
1197
1198 /* first handle partial byte shift in */
1199 bitv_shiftin(bv, iterbits, inbv->v[byteindex--]);
1200
1201 /* now handle any remaining full byte shift ins */
1202 while (byteindex >= 0)
1203 bitv_shiftin(bv, 8, inbv->v[byteindex--]);
1204 }
1205
1206 /* return the number of bits required to hold the current bit vector's value */
1207 static int
bitv_bits(const bitv * bv)1208 bitv_bits(const bitv *bv)
1209 {
1210 int i;
1211
1212 for (i = BITV_MAX_BYTES - 1; i >= 0; i--)
1213 if (bv->v[i]) {
1214 int bit;
1215
1216 for (bit = 7; bit >= 0; bit--)
1217 if ((bv->v[i] >> bit) & 1)
1218 return (i * 8 + bit + 1);
1219
1220 /* this can't happen, so do *something* */
1221 return ((i + 1) * 8);
1222 }
1223
1224 return (0);
1225 }
1226
1227 /* extract chunks of bits from bit vector */
1228 static unsigned
bitv_chunk(const bitv * bv,unsigned limbit,unsigned lobit)1229 bitv_chunk(const bitv *bv, unsigned limbit, unsigned lobit)
1230 {
1231 unsigned retval = 0;
1232 int bit;
1233
1234 /*
1235 * entry assumptions:
1236 * limbit > lobit
1237 * limbit - lobit <= sizeof (unsigned) * 8
1238 */
1239
1240 for (bit = limbit - 1; bit >= 0 && bit >= lobit; bit--) {
1241 retval <<= 1;
1242 retval |= (bv->v[bit / 8] >> (bit % 8)) & 1;
1243 }
1244
1245 return (retval);
1246 }
1247
1248 /*
1249 * multiply by a given value
1250 *
1251 * on overflow, bit vector will hold least significant BITV_MAX_BYTES,
1252 * return value will be -1, and errno will be ERANGE. otherwise
1253 * return is zero and bit vector holds the product.
1254 */
1255 static int
bitv_mul(bitv * bv,unsigned long long val)1256 bitv_mul(bitv *bv, unsigned long long val)
1257 {
1258 unsigned short result;
1259 unsigned char prod[BITV_MAX_BYTES];
1260 unsigned k = 0;
1261 int valbyte;
1262 int bvbyte;
1263 int i;
1264
1265 /* start with a zeroed out bit vector to hold result */
1266 for (i = 0; i < BITV_MAX_BYTES; i++)
1267 prod[i] = 0;
1268
1269 /* from most-significant byte of val to least... */
1270 for (valbyte = 0; valbyte < sizeof (val); valbyte++)
1271 /* from most significant byte of bv to least */
1272 for (bvbyte = 0; bvbyte < BITV_MAX_BYTES; bvbyte++) {
1273 result = ((val >> (valbyte * 8)) & 0xff) *
1274 bv->v[bvbyte] + k;
1275
1276 if (valbyte + bvbyte >= BITV_MAX_BYTES) {
1277 /*
1278 * we're not storing digits past
1279 * BITV_MAX_BYTES, so if they aren't
1280 * zeros, then signal an overflow.
1281 */
1282 if (result & 0xff) {
1283 errno = ERANGE;
1284 return (-1);
1285 }
1286 } else
1287 prod[valbyte + bvbyte] += result & 0xff;
1288
1289 /* "carry the 1..." */
1290 k = result >> 8;
1291 }
1292
1293 /* store result in bv */
1294 for (i = 0; i < BITV_MAX_BYTES; i++)
1295 bv->v[i] = prod[i];
1296
1297 return (0);
1298 }
1299
1300 /*
1301 * add in a given value
1302 *
1303 * on overflow, bit vector will hold least significant BITV_MAX_BYTES,
1304 * return value will be -1, and errno will be ERANGE. otherwise
1305 * return is zero and bit vector holds the sum.
1306 */
1307 static int
bitv_add(bitv * bv,unsigned long long val)1308 bitv_add(bitv *bv, unsigned long long val)
1309 {
1310 int cf = 0; /* carry flag */
1311 unsigned short result;
1312 int i;
1313
1314 for (i = 0; i < BITV_MAX_BYTES; i++) {
1315 if (i < sizeof (val))
1316 result = cf + bv->v[i] + ((val >> (i * 8)) & 0xff);
1317 else
1318 result = cf + bv->v[i];
1319
1320 cf = (result >> 8) & 1;
1321 bv->v[i] = result & 0xff;
1322 }
1323
1324 if (cf) {
1325 errno = ERANGE;
1326 return (-1);
1327 }
1328 return (0);
1329 }
1330
1331 /*
1332 * subtract out a given value
1333 *
1334 * on underflow, bit vector will hold least significant BITV_MAX_BYTES,
1335 * return value will be -1, and errno will be ERANGE. otherwise
1336 * return is zero and bit vector holds the difference.
1337 */
1338 static int
bitv_sub(bitv * bv,unsigned long long val)1339 bitv_sub(bitv *bv, unsigned long long val)
1340 {
1341 int bf = 0; /* borrow flag */
1342 unsigned short minuend;
1343 unsigned short subtrahend;
1344 int i;
1345
1346 for (i = 0; i < BITV_MAX_BYTES; i++) {
1347 minuend = bv->v[i];
1348 if (i < sizeof (val))
1349 subtrahend = bf + ((val >> (i * 8)) & 0xff);
1350 else
1351 subtrahend = bf;
1352 if (subtrahend > minuend) {
1353 bf = 1;
1354 minuend += 1 << 8;
1355 } else
1356 bf = 0;
1357
1358 bv->v[i] = minuend - subtrahend;
1359 }
1360
1361 if (bf) {
1362 errno = ERANGE;
1363 return (-1);
1364 }
1365 return (0);
1366 }
1367
1368 /*
1369 * see if bv is greater than or equal to a given value
1370 */
1371 static int
bitv_ge(const bitv * bv,unsigned long long val)1372 bitv_ge(const bitv *bv, unsigned long long val)
1373 {
1374 int bf = 0; /* borrow flag */
1375 unsigned short minuend;
1376 unsigned short subtrahend;
1377 int i;
1378
1379 for (i = 0; i < BITV_MAX_BYTES; i++) {
1380 minuend = bv->v[i];
1381 if (i < sizeof (val))
1382 subtrahend = bf + ((val >> (i * 8)) & 0xff);
1383 else
1384 subtrahend = bf;
1385 if (subtrahend > minuend)
1386 bf = 1;
1387 else
1388 bf = 0;
1389 }
1390
1391 return (!bf);
1392 }
1393
1394 /* parse a string into bit vector, honor leading 0/0x for octal/hex */
1395 static bitv *
bitv_strparse(const char * s,int bits)1396 bitv_strparse(const char *s, int bits)
1397 {
1398 unsigned long long base = 10;
1399 unsigned long long val;
1400 bitv *bv = bitv_alloc();
1401
1402 if (bv == NULL) {
1403 errno = ENOMEM;
1404 return (NULL);
1405 }
1406
1407 if (*s == '0') {
1408 s++;
1409 if (*s == 'x') {
1410 s++;
1411 base = 16;
1412 } else
1413 base = 8;
1414 }
1415
1416 while (isxdigit(*s)) {
1417 /* isxdigit() let's in too much, depending on base */
1418 if (base == 8 && (*s < '0' || *s > '7'))
1419 break;
1420 else if (base == 10 && !isdigit(*s))
1421 break;
1422
1423 /* convert the digit to binary */
1424 if (isdigit(*s))
1425 val = *s - '0';
1426 else
1427 val = tolower(*s) - 'a' + 10;
1428
1429 /*
1430 * multiply our big integer by base,
1431 * add in the most recent digit,
1432 * and check for overflow
1433 */
1434 if (bitv_mul(bv, base) < 0 ||
1435 bitv_add(bv, val) < 0 ||
1436 bitv_bits(bv) > bits) {
1437 bitv_free(bv);
1438 errno = ERANGE;
1439 return (NULL);
1440 }
1441
1442 s++;
1443 }
1444
1445 return (bv);
1446 }
1447
1448 /* return 0 if two bit vectors represent the same number */
1449 static int
bitv_cmp(const bitv * bv1,const bitv * bv2)1450 bitv_cmp(const bitv *bv1, const bitv *bv2)
1451 {
1452 int i;
1453
1454 for (i = BITV_MAX_BYTES - 1; i >= 0; i--)
1455 if (bv1->v[i] < bv2->v[i])
1456 return (-1);
1457 else if (bv1->v[i] > bv2->v[i])
1458 return (1);
1459 return (0);
1460 }
1461
1462
1463 /* CRC code... */
1464 static unsigned crctab[256] = {
1465 0x00000000,
1466 0x04C11DB7, 0x09823B6E, 0x0D4326D9, 0x130476DC, 0x17C56B6B,
1467 0x1A864DB2, 0x1E475005, 0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6,
1468 0x2B4BCB61, 0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD,
1469 0x4C11DB70, 0x48D0C6C7, 0x4593E01E, 0x4152FDA9, 0x5F15ADAC,
1470 0x5BD4B01B, 0x569796C2, 0x52568B75, 0x6A1936C8, 0x6ED82B7F,
1471 0x639B0DA6, 0x675A1011, 0x791D4014, 0x7DDC5DA3, 0x709F7B7A,
1472 0x745E66CD, 0x9823B6E0, 0x9CE2AB57, 0x91A18D8E, 0x95609039,
1473 0x8B27C03C, 0x8FE6DD8B, 0x82A5FB52, 0x8664E6E5, 0xBE2B5B58,
1474 0xBAEA46EF, 0xB7A96036, 0xB3687D81, 0xAD2F2D84, 0xA9EE3033,
1475 0xA4AD16EA, 0xA06C0B5D, 0xD4326D90, 0xD0F37027, 0xDDB056FE,
1476 0xD9714B49, 0xC7361B4C, 0xC3F706FB, 0xCEB42022, 0xCA753D95,
1477 0xF23A8028, 0xF6FB9D9F, 0xFBB8BB46, 0xFF79A6F1, 0xE13EF6F4,
1478 0xE5FFEB43, 0xE8BCCD9A, 0xEC7DD02D, 0x34867077, 0x30476DC0,
1479 0x3D044B19, 0x39C556AE, 0x278206AB, 0x23431B1C, 0x2E003DC5,
1480 0x2AC12072, 0x128E9DCF, 0x164F8078, 0x1B0CA6A1, 0x1FCDBB16,
1481 0x018AEB13, 0x054BF6A4, 0x0808D07D, 0x0CC9CDCA, 0x7897AB07,
1482 0x7C56B6B0, 0x71159069, 0x75D48DDE, 0x6B93DDDB, 0x6F52C06C,
1483 0x6211E6B5, 0x66D0FB02, 0x5E9F46BF, 0x5A5E5B08, 0x571D7DD1,
1484 0x53DC6066, 0x4D9B3063, 0x495A2DD4, 0x44190B0D, 0x40D816BA,
1485 0xACA5C697, 0xA864DB20, 0xA527FDF9, 0xA1E6E04E, 0xBFA1B04B,
1486 0xBB60ADFC, 0xB6238B25, 0xB2E29692, 0x8AAD2B2F, 0x8E6C3698,
1487 0x832F1041, 0x87EE0DF6, 0x99A95DF3, 0x9D684044, 0x902B669D,
1488 0x94EA7B2A, 0xE0B41DE7, 0xE4750050, 0xE9362689, 0xEDF73B3E,
1489 0xF3B06B3B, 0xF771768C, 0xFA325055, 0xFEF34DE2, 0xC6BCF05F,
1490 0xC27DEDE8, 0xCF3ECB31, 0xCBFFD686, 0xD5B88683, 0xD1799B34,
1491 0xDC3ABDED, 0xD8FBA05A, 0x690CE0EE, 0x6DCDFD59, 0x608EDB80,
1492 0x644FC637, 0x7A089632, 0x7EC98B85, 0x738AAD5C, 0x774BB0EB,
1493 0x4F040D56, 0x4BC510E1, 0x46863638, 0x42472B8F, 0x5C007B8A,
1494 0x58C1663D, 0x558240E4, 0x51435D53, 0x251D3B9E, 0x21DC2629,
1495 0x2C9F00F0, 0x285E1D47, 0x36194D42, 0x32D850F5, 0x3F9B762C,
1496 0x3B5A6B9B, 0x0315D626, 0x07D4CB91, 0x0A97ED48, 0x0E56F0FF,
1497 0x1011A0FA, 0x14D0BD4D, 0x19939B94, 0x1D528623, 0xF12F560E,
1498 0xF5EE4BB9, 0xF8AD6D60, 0xFC6C70D7, 0xE22B20D2, 0xE6EA3D65,
1499 0xEBA91BBC, 0xEF68060B, 0xD727BBB6, 0xD3E6A601, 0xDEA580D8,
1500 0xDA649D6F, 0xC423CD6A, 0xC0E2D0DD, 0xCDA1F604, 0xC960EBB3,
1501 0xBD3E8D7E, 0xB9FF90C9, 0xB4BCB610, 0xB07DABA7, 0xAE3AFBA2,
1502 0xAAFBE615, 0xA7B8C0CC, 0xA379DD7B, 0x9B3660C6, 0x9FF77D71,
1503 0x92B45BA8, 0x9675461F, 0x8832161A, 0x8CF30BAD, 0x81B02D74,
1504 0x857130C3, 0x5D8A9099, 0x594B8D2E, 0x5408ABF7, 0x50C9B640,
1505 0x4E8EE645, 0x4A4FFBF2, 0x470CDD2B, 0x43CDC09C, 0x7B827D21,
1506 0x7F436096, 0x7200464F, 0x76C15BF8, 0x68860BFD, 0x6C47164A,
1507 0x61043093, 0x65C52D24, 0x119B4BE9, 0x155A565E, 0x18197087,
1508 0x1CD86D30, 0x029F3D35, 0x065E2082, 0x0B1D065B, 0x0FDC1BEC,
1509 0x3793A651, 0x3352BBE6, 0x3E119D3F, 0x3AD08088, 0x2497D08D,
1510 0x2056CD3A, 0x2D15EBE3, 0x29D4F654, 0xC5A92679, 0xC1683BCE,
1511 0xCC2B1D17, 0xC8EA00A0, 0xD6AD50A5, 0xD26C4D12, 0xDF2F6BCB,
1512 0xDBEE767C, 0xE3A1CBC1, 0xE760D676, 0xEA23F0AF, 0xEEE2ED18,
1513 0xF0A5BD1D, 0xF464A0AA, 0xF9278673, 0xFDE69BC4, 0x89B8FD09,
1514 0x8D79E0BE, 0x803AC667, 0x84FBDBD0, 0x9ABC8BD5, 0x9E7D9662,
1515 0x933EB0BB, 0x97FFAD0C, 0xAFB010B1, 0xAB710D06, 0xA6322BDF,
1516 0xA2F33668, 0xBCB4666D, 0xB8757BDA, 0xB5365D03, 0xB1F740B4
1517 };
1518
1519 static void
crc(unsigned long * crcp,unsigned val)1520 crc(unsigned long *crcp, unsigned val)
1521 {
1522 *crcp = (*crcp<<8) ^ crctab[(unsigned char)((*crcp>>24)^val)];
1523 }
1524