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