xref: /titanic_41/usr/src/lib/fm/libdiagcode/common/diagcode.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
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