/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * diagcode library, Sun Private API (PSARC/2004/601)
 *
 * undocumented debugging interface:
 *      set environment variable _FM_DC_DEBUG for debug prints to stderr.
 *      set it to 1 for extended error messages only.
 *      set it to 2 to include success info too on interesting functions.
 *      set it to 3 to include success info on trivial functions too.
 * note that this environment variable is only examined in fm_dc_opendict().
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <alloca.h>
#include <errno.h>

#include <fm/diagcode.h>

/* private (opaque to callers) handle information */
struct fm_dc_handle {
        const char *dictname;
        FILE *fp;
        unsigned maxkey;
        int version;
        int debug;
        /* name/value pairs from .dict header */
        struct fm_dc_prop {
                struct fm_dc_prop *next;
                const char *lhs;
                const char *rhs;
        } *props;
};

/*
 * parameters of the various sizes of diagcodes
 *
 * table must be in ascending order from smallest databits value to largest.
 * when faced with more databits than the last entry, we know we have
 * something that won't fit into a diagcode.
 */
static const struct info {
        int databits;   /* number of bits used to hold dictionary value */
        int numx;       /* number of digits (also called X's) in code */
        int csumbits;   /* number of bits used for checksum */
        int sizeval;    /* value encoded into "size" field of code */
        unsigned long long offset;      /* databits==0 stands for this value */
} Info[] = {
        /*  diagcode is: dictname-XXXX-XX */
        { 21, 6, 5, 0, 0ULL },

        /*  diagcode is: dictname-XXXX-XXXX-XX */
        { 38, 10, 8, 1, 2097152ULL },

        /*  diagcode is: dictname-XXXX-XXXX-XXXX-XX */
        { 55, 14, 11, 2, 274880004096ULL },

        /*  diagcode is: dictname-XXXX-XXXX-XXXX-XXXX-XX */
        { 72, 18, 14, 3, 36029071898968064ULL }
};
#define MAXDATABITS 72  /* highest entry in table above */
#define MAXCODELEN 25   /* big enough to hold the X's, dashes, and \0 */

/* forward references for functions private to this file */
typedef struct bitv bitv;
static const struct info *dictval2info(const bitv *bv);
static const struct info *numx2info(int numx);
static void sortkey(const char *key[]);
static const char *keymatch(const char *linebuf, const char *key[]);
static int buildcode(fm_dc_handle_t *dhp, const char *rhsp,
    char *code, size_t maxcode, char *debugstr);
static bitv *code2dictval(fm_dc_handle_t *dhp, const char *code);
struct parsestate {
        char *parseptr; /* next unparsed character in buffer */
        char *rhsp;     /* rhs associated with last lhs (or NULL) */
};
static void startparse(struct parsestate *ps, char *ptr);
static char *nextlhs(struct parsestate *ps);
static char *nextrhs(struct parsestate *ps);
static bitv *bitv_alloc(void);
static void bitv_free(bitv *bv);
static void bitv_shift(bitv *bv, unsigned bits);
static void bitv_setlo(bitv *bv, unsigned bits, unsigned val);
static void bitv_shiftin(bitv *bv, unsigned bits, unsigned val);
static void bitv_shiftinv(bitv *bv, unsigned bits, const bitv *inbv);
static int bitv_bits(const bitv *bv);
static unsigned bitv_chunk(const bitv *bv, unsigned limbit, unsigned lobit);
static int bitv_mul(bitv *bv, unsigned long long val);
static int bitv_add(bitv *bv, unsigned long long val);
static int bitv_sub(bitv *bv, unsigned long long val);
static int bitv_ge(const bitv *bv, unsigned long long val);
static bitv *bitv_strparse(const char *s, int bits);
static int bitv_cmp(const bitv *bv1, const bitv *bv2);
static void crc(unsigned long *crcp, unsigned val);

#define DICTMAXLINE     10240   /* maximum expected dictionary line length */

#define MAXDEBUGSTR     100     /* for debug messages */

static const char Suffix[] = ".dict";   /* suffix on dictionary filename */
static const char Defaultpath[] = "/usr/lib/fm/dict";
static const char Debugenv[] = "_FM_DC_DEBUG";  /* debug environment var */

/* properties we look for at top of dictionary */
static const char Header[] = "FMDICT: ";
static const char Name[] = "name";
static const char Version[] = "version";
static const char Maxkey[] = "maxkey";

/* the alphabet used to encode information in a diagcode (base32 digits) */
static const char Alphabet[] = "0123456789ACDEFGHJKLMNPQRSTUVWXY";

/* open a dictionary, return opaque handle */
fm_dc_handle_t *
fm_dc_opendict(int version, const char *dirpath, const char *dictname)
{
        int debug = 0;                  /* set by environment variable */
        char *debugstr = "";            /* error path debug prefix text */
        fm_dc_handle_t *dhp = NULL;
        char *fname;                    /* full dict file name */
        char linebuf[DICTMAXLINE];      /* line read from dict */
        int line = 0;                   /* line number in dict */
        unsigned prop_version = 0;      /* version property from dict */
        char *prop_name = "";           /* name property from dict */
        char *lhsp;                     /* prop left-hand-side */
        char *rhsp;                     /* prop right-hand-side */
        struct parsestate pstate;       /* for startparse(), nextlhs(), etc */

        /* undocumented flag, given via environment variable */
        if ((rhsp = getenv(Debugenv)) != NULL)
                debug = atoi(rhsp);

        if (debug > 1)
                (void) fprintf(stderr,
                    "fm_dc_opendict: ver %d path \"%s\" dict \"%s\": ",
                    version, (dirpath == NULL) ? "NULL" : dirpath, dictname);
        else if (debug)
                debugstr = "fm_dc_opendict: ";  /* used in error paths */

        /* verify caller expects an API version we support */
        if (version < 0 || version > FM_DC_VERSION) {
                if (debug)
                        (void) fprintf(stderr, "%sENOTSUP ver not in [0-%d]\n",
                            debugstr, FM_DC_VERSION);
                errno = ENOTSUP;
                return (NULL);
        }

        /* caller can pass in NULL for default dirpath */
        if (dirpath == NULL)
                dirpath = Defaultpath;

        /*
         * allocate buffer for dirpath, slash, dictname, and suffix
         * (sizeof (Suffix) includes the null).
         */
        fname = alloca(strlen(dirpath) + 1 +
            strlen(dictname) + sizeof (Suffix));

        /*
         * allocate the handle.
         *
         * allocate the dictname copy kept in the handle.
         *
         * if any of these fail, send back ENOMEM.
         */
        if ((dhp = malloc(sizeof (*dhp))) == NULL ||
            (dhp->dictname = strdup(dictname)) == NULL) {
                if (dhp)
                        free(dhp);
                if (debug)
                        (void) fprintf(stderr, "%sENOMEM\n", debugstr);
                errno = ENOMEM;
                return (NULL);
        }

        /* initialize the handle */
        (void) strcpy(fname, dirpath);
        (void) strcat(fname, "/");
        (void) strcat(fname, dictname);
        (void) strcat(fname, Suffix);
        dhp->fp = NULL;
        dhp->maxkey = 0;
        dhp->version = version;
        dhp->debug = debug;
        dhp->props = NULL;

        /* open the dictionary */
        if (debug > 1)
                (void) fprintf(stderr, "\"%s\": ", fname);
        if ((dhp->fp = fopen(fname, "r")) == NULL) {
                int oerrno = errno;     /* fopen() set errno to something */

                if (debug > 1)
                        perror("fopen");
                else if (debug) {
                        (void) fprintf(stderr, "%s%s: ", debugstr, fname);
                        errno = oerrno;
                        perror("fopen");
                }
                fm_dc_closedict(dhp);
                errno = oerrno;
                return (NULL);
        }

        /* pull in the header line and parse it */
        while (fgets(linebuf, DICTMAXLINE, dhp->fp) != NULL) {
                line++;
                if (*linebuf == '\n' || *linebuf == '#')
                        continue;

                /* first non-comment, non-blank line must be header */
                if (strncmp(linebuf, Header, sizeof (Header) - 1)) {
                        fm_dc_closedict(dhp);
                        if (debug)
                                (void) fprintf(stderr,
                                    "%sEINVAL: line %d: header expected.\n",
                                    debugstr, line);
                        errno = EINVAL;
                        return (NULL);
                }

                /* just wanted header line for now */
                break;
        }

        /* walk through name=value pairs in line after Header string */
        startparse(&pstate, &linebuf[sizeof (Header) - 1]);
        while ((lhsp = nextlhs(&pstate)) != NULL) {
                struct fm_dc_prop *propp;

                if ((rhsp = nextrhs(&pstate)) == NULL) {
                        if (debug)
                                (void) fprintf(stderr, "%sEINVAL "
                                    "%s prop has no value\n", debugstr, lhsp);
                        fm_dc_closedict(dhp);
                        errno = EINVAL;
                        return (NULL);
                }

                propp = malloc(sizeof (*propp));
                if (propp == NULL ||
                    (propp->lhs = strdup(lhsp)) == NULL ||
                    (propp->rhs = strdup(rhsp)) == NULL) {
                        if (debug)
                                (void) fprintf(stderr, "%sENOMEM\n", debugstr);
                        if (propp != NULL) {
                                if (propp->lhs != NULL)
                                        free((void *) propp->lhs);
                                free((void *) propp);
                        }
                        fm_dc_closedict(dhp);
                        errno = ENOMEM;
                        return (NULL);
                }
                propp->next = dhp->props;
                dhp->props = propp;

                if (strcmp(lhsp, Name) == 0)
                        prop_name = rhsp;
                else if (strcmp(lhsp, Version) == 0)
                        prop_version = strtoul(rhsp, NULL, 0);
                else if (strcmp(lhsp, Maxkey) == 0)
                        dhp->maxkey = strtoul(rhsp, NULL, 0);
        }

        /*
         * require version 1, expected dict name, and maxkey values
         * (note we use "1" here and not FM_DC_VERSION because this code
         * implements version 1, so the check below should not float to
         * newer version numbers if the header file defines them.)
         */
        if (prop_version != 1UL || strcmp(prop_name, dictname) ||
            dhp->maxkey == 0) {
                fm_dc_closedict(dhp);
                if (debug)
                        (void) fprintf(stderr,
                            "%sEINVAL ver %d name \"%s\" maxkey %d\n",
                            debugstr, prop_version, prop_name, dhp->maxkey);
                errno = EINVAL;
                return (NULL);
        }

        if (debug > 1)
                (void) fprintf(stderr, "fm_dc_opendict: dhp 0x%p\n",
                    (void *)dhp);
        return (dhp);
}

/* close a dictionary */
void
fm_dc_closedict(fm_dc_handle_t *dhp)
{
        struct fm_dc_prop *props;
        struct fm_dc_prop *oprops;

        if (dhp->debug > 1)
                (void) fprintf(stderr, "fm_dc_closedict: dhp 0x%p\n",
                    (void *)dhp);
        if (dhp->fp)
                (void) fclose(dhp->fp);

        free((void *) dhp->dictname);

        props = dhp->props;
        while (props) {
                if (props->lhs != NULL)
                        free((void *) props->lhs);
                if (props->rhs != NULL)
                        free((void *) props->rhs);
                oprops = props;
                props = props->next;
                free((void *) oprops);
        }

        free(dhp);
}

/* return maximum length (in bytes) of diagcodes for a given dictionary */
size_t
fm_dc_codelen(fm_dc_handle_t *dhp)
{
        size_t len = strlen(dhp->dictname);

        /* only one version so far, so dhp->version isn't checked */

        if (dhp->debug > 2)
                (void) fprintf(stderr, "fm_dc_codelen: dhp 0x%p: %d\n",
                    (void *)dhp, (int)(len + MAXCODELEN));
        return (len + MAXCODELEN);
}

/* return number of strings in key for a given dictionary */
int
fm_dc_maxkey(fm_dc_handle_t *dhp)
{
        /* only one version so far, so dhp->version isn't checked */

        /* this interface counts the NULL entry */
        if (dhp->debug > 2)
                (void) fprintf(stderr, "fm_dc_maxkey: dhp 0x%p: maxkey %d\n",
                    (void *)dhp, dhp->maxkey + 1);
        return (dhp->maxkey + 1);
}

/* given a key, construct a diagcode */
int
fm_dc_key2code(fm_dc_handle_t *dhp,
    const char *key[], char *code, size_t maxcode)
{
        char *debugstr = "";            /* error path debug prefix text */
        int line = 0;                   /* line number in dict */
        char linebuf[DICTMAXLINE];      /* line read from dict */
        const char *rhsp;               /* right-hand-side of entry */

        /* only one version so far, so dhp->version isn't checked */

        if (dhp->debug > 1) {
                int nel;

                (void) fprintf(stderr,
                    "fm_dc_key2code: dhp 0x%p maxcode %lu ", (void *)dhp,
                    (ulong_t)maxcode);
                for (nel = 0; key[nel]; nel++)
                        (void) fprintf(stderr, "\"%s\" ", key[nel]);
        } else if (dhp->debug)
                debugstr = "fm_dc_key2code: ";

        /* sort the keys */
        sortkey(key);

        rewind(dhp->fp);

        while (fgets(linebuf, DICTMAXLINE, dhp->fp) != NULL) {
                line++;
                if (*linebuf == '\n' || *linebuf == '#')
                        continue;

                /* first non-comment, non-blank line must be header */
                if (strncmp(linebuf, Header, sizeof (Header) - 1) == 0)
                        continue;

                if ((rhsp = keymatch(linebuf, key)) != NULL) {
                        char ndebugstr[MAXDEBUGSTR];

                        if (dhp->debug > 1)
                                (void) fprintf(stderr, "match line %d: ", line);
                        else {
                                (void) snprintf(ndebugstr, MAXDEBUGSTR,
                                    "fm_dc_key2code: dictionary line %d",
                                    line);
                                debugstr = ndebugstr;
                        }

                        return (buildcode(dhp, rhsp, code, maxcode, debugstr));
                }
        }

        /* no match */
        if (dhp->debug)
                (void) fprintf(stderr, "%sENOMSG no match\n", debugstr);
        errno = ENOMSG;
        return (-1);
}

/* given a diagcode, return the key (array of strings) */
int
fm_dc_code2key(fm_dc_handle_t *dhp, const char *code,
    char *key[], int maxkey)
{
        char *debugstr = "";            /* error path debug prefix text */
        int line = 0;
        char linebuf[DICTMAXLINE];
        bitv *dictval;

        /* only one version so far, so dhp->version isn't checked */

        if (dhp->debug > 1)
                (void) fprintf(stderr,
                    "fm_dc_code2key: dhp 0x%p code \"%s\" maxkey %d: ",
                    (void *)dhp, code, maxkey);
        else if (dhp->debug)
                debugstr = "fm_dc_code2key: ";

        /* convert code back to bit vector */
        if ((dictval = code2dictval(dhp, code)) == NULL) {
                /* code2dictval() sets errno */
                if (dhp->debug) {
                        int oerrno = errno;

                        /* handle expected types without printing a number */
                        if (errno == ENOMEM)
                                (void) fprintf(stderr,
                                    "%sENOMEM code2dictval\n",
                                    debugstr);
                        else if (errno == EINVAL)
                                (void) fprintf(stderr,
                                    "%sEINVAL code2dictval\n",
                                    debugstr);
                        else
                                (void) fprintf(stderr,
                                    "%scode2dictval error %d\n",
                                    debugstr, oerrno);
                        errno = oerrno;
                }
                return (-1);
        }

        rewind(dhp->fp);

        while (fgets(linebuf, DICTMAXLINE, dhp->fp) != NULL) {
                char *ptr;
                bitv *thisval;
                char *beginp;
                char *endp;
                int nel;

                line++;
                if (*linebuf == '\n' || *linebuf == '#')
                        continue;

                /* first non-comment, non-blank line must be header */
                if (strncmp(linebuf, Header, sizeof (Header) - 1) == 0)
                        continue;

                if ((ptr = strchr(linebuf, '=')) == NULL)
                        continue;       /* ignore malformed entries */

                *ptr++ = '\0';

                /* pull in value from dictionary */
                if ((thisval = bitv_strparse(ptr, MAXDATABITS)) == NULL) {
                        /* bitv_strparse() sets errno */
                        if (errno == ENOMEM) {
                                bitv_free(dictval);
                                if (dhp->debug)
                                        (void) fprintf(stderr,
                                            "%sENOMEM bitv_strparse\n",
                                            debugstr);
                                errno = ENOMEM;
                                return (-1);
                        }
                        /* other than ENOMEM, trudge on... */
                        continue;
                }

                if (bitv_cmp(thisval, dictval)) {
                        bitv_free(thisval);
                        continue;
                }

                /* if we got here, we found the match */
                bitv_free(thisval);
                bitv_free(dictval);
                beginp = linebuf;
                nel = 0;
                for (;;) {
                        while (*beginp && isspace(*beginp))
                                beginp++;
                        if (*beginp == '\0') {
                                /* all done */
                                key[nel] = NULL;
                                return (0);
                        }
                        if (nel >= maxkey - 1) {
                                if (dhp->debug)
                                        (void) fprintf(stderr,
                                            "%sENOMEM maxkey %d\n",
                                            debugstr, maxkey);
                                errno = ENOMEM;
                                return (-1);
                        }
                        for (endp = beginp; *endp && !isspace(*endp); endp++)
                                ;
                        if (*endp)
                                *endp++ = '\0';
                        if ((key[nel++] = strdup(beginp)) == NULL) {
                                if (dhp->debug)
                                        (void) fprintf(stderr,
                                            "%sENOMEM strdup\n", debugstr);
                                errno = ENOMEM;
                                return (-1);
                        }
                        beginp = endp;
                }
        }

        bitv_free(dictval);
        if (dhp->debug)
                (void) fprintf(stderr, "%sENOMSG\n", debugstr);
        errno = ENOMSG;
        return (-1);
}

/* return the right-hand side of a names property from the dict header */
const char *
fm_dc_getprop(fm_dc_handle_t *dhp, const char *name)
{
        struct fm_dc_prop *props;

        /* only one version so far, so dhp->version isn't checked */

        if (dhp->debug > 2)
                (void) fprintf(stderr, "fm_dc_getprop: dhp 0x%p: \"%s\"",
                    (void *)dhp, name);

        for (props = dhp->props; props; props = props->next)
                if (strcmp(name, props->lhs) == 0)
                        break;

        if (dhp->debug > 2)
                (void) fprintf(stderr, "= \"%s\"\n",
                    (props == NULL) ? "NULL" : props->rhs);

        return ((props == NULL) ? NULL : props->rhs);
}

/* find the appropriate diagcode format for a given dictval */
static const struct info *
dictval2info(const bitv *bv)
{
        int i;

        for (i = 0; i < sizeof (Info) / sizeof (*Info) - 1; i++)
                if (!bitv_ge(bv, Info[i + 1].offset))
                        return (&Info[i]);

        /* return largest format */
        return (&Info[sizeof (Info) / sizeof (*Info) - 1]);
}

/* lookup the diagcode parameters given the number of X's used */
static const struct info *
numx2info(int numx)
{
        int i;

        for (i = 0; i < sizeof (Info) / sizeof (*Info); i++)
                if (numx == Info[i].numx)
                        return (&Info[i]);

        return (NULL);
}

/* for use with qsort() */
static int
mycmp(const void *a, const void *b)
{
        return (strcmp(*(char **)a, *(char **)b));
}

/*
 * sortkey -- make sure key[] array is lexically sorted and without repeats
 */
static void
sortkey(const char *key[])
{
        int nel;
        int srci;       /* source index when iterating through key[] */
        int dsti;       /* dest index when storing elements in key[] */

        /* count the number of elements in key[] */
        for (nel = 0; key[nel]; nel++)
                ;

        if (nel < 2)
                return;         /* nothing to sort */

        qsort((void *)key, nel, sizeof (char *), mycmp);

        /* go through array and remove repeats */
        dsti = 1;
        for (srci = 1; srci < nel; srci++)
                if (strcmp(key[srci], key[dsti - 1]) != 0)
                        key[dsti++] = key[srci];
        key[dsti] = NULL;
}

/*
 * keymatch -- check for matching line from the dictionary
 *
 * assumes that the key[] array has already been lexically sorted.
 * returns NULL if no match, otherwise pointer to first character of RHS.
 */
static const char *
keymatch(const char *linebuf, const char *key[])
{
        int keynum = 0;
        const char *ptr;

        while (linebuf) {
                /* skip any initial whitespace in front of name */
                while (*linebuf && isspace(*linebuf))
                        linebuf++;

                ptr = key[keynum];

                if (ptr == NULL && *linebuf == '=') {
                        /* match */
                        linebuf++;
                        while (*linebuf && isspace(*linebuf))
                                linebuf++;
                        return (linebuf);
                } else if (ptr == NULL)
                        return (NULL);  /* dict had more strings for key */

                /* match the string */
                while (*linebuf)
                        if (*ptr == '\0') {
                                if (isspace(*linebuf) || *linebuf == '=')
                                        break;  /* match */
                                else
                                        return (NULL);  /* dict string longer */
                        } else if (*linebuf != *ptr)
                                return (NULL);  /* string don't match */
                        else {
                                linebuf++;
                                ptr++;
                        }

                keynum++;
        }

        return (NULL);  /* no match */
}

/*
 * buildcode -- given the val from the dictionary, create the diagcode
 */
static int
buildcode(fm_dc_handle_t *dhp, const char *rhsp,
    char *code, size_t maxcode, char *debugstr)
{
        char *codebegin = code; /* remember start of code buffer */
        const struct info *infop;       /* Info[] table entry */
        unsigned long csum = 0; /* checksum (CRC) of diagcode */
        const char *ptr;
        bitv *dictval;          /* value from dictionary */
        bitv *allbits;          /* assembled diagcode in binary */
        int bit;                /* for looping through bits */
        int limbit;             /* upper bit limit when looping */

        /* sanity check that buffer is large enough for diagcode */
        if (maxcode < fm_dc_codelen(dhp)) {
                if (dhp->debug)
                        (void) fprintf(stderr,
                            "%sENOMEM maxcode %lu < codelen %lu\n",
                            debugstr, (ulong_t)maxcode,
                            (ulong_t)fm_dc_codelen(dhp));
                errno = ENOMEM;
                return (-1);
        }

        /* handle dictname part of checksum */
        for (ptr = dhp->dictname; *ptr; ptr++) {
                crc(&csum, (unsigned)*ptr);
                *code++ = *ptr;
        }

        /* pull in value from dictionary */
        if ((dictval = bitv_strparse(rhsp, MAXDATABITS)) == NULL) {
                /* bitv_strparse() sets errno */
                if (dhp->debug) {
                        int oerrno = errno;

                        /* handle expected types without printing a number */
                        if (errno == ENOMEM)
                                (void) fprintf(stderr,
                                    "%sENOMEM bitv_strparse\n",
                                    debugstr);
                        else if (errno == ERANGE)
                                (void) fprintf(stderr,
                                    "%sERANGE bitv_strparse\n",
                                    debugstr);
                        else
                                (void) fprintf(stderr,
                                    "%sbitv_strparse error %d\n",
                                    debugstr, oerrno);
                        errno = oerrno;
                }
                return (-1);
        }

        /* determine which format of code we're using */
        infop = dictval2info(dictval);

        /* subtract off the offset appropriate for format of code */
        if (dhp->debug > 3)
                (void) fprintf(stderr,
                    "%ssubtract offset %llu\n", debugstr, infop->offset);
        if (bitv_sub(dictval, infop->offset) < 0) {
                /*
                 * this "cannot happen" since code format was chosen
                 * so that offset will be smaller than dictval, and
                 * dictval cannot be out of range since bitv_strparse()
                 * should have caught it.
                 */
                if (dhp->debug)
                        (void) fprintf(stderr,
                            "%sERANGE from bitv_sub\n", debugstr);
                bitv_free(dictval);
                errno = ERANGE;
                return (-1);
        }

        /* assemble all the bits for the diagcode */
        if ((allbits = bitv_alloc()) == NULL) {
                bitv_free(dictval);
                if (dhp->debug)
                        (void) fprintf(stderr,
                            "%sENOMEM from bitv_alloc\n", debugstr);
                errno = ENOMEM;
                return (-1);
        }

        /*
         * construct the full diagcode by shifting in information:
         *      - 2 bit code type, set to 01
         *      - 2 bit size field
         *      - the databits of the dictionary code itself
         */

        bitv_shiftin(allbits, 2, 1);
        bitv_shiftin(allbits, 2, infop->sizeval);
        bitv_shiftinv(allbits, infop->databits, dictval);

        /* insert zeros for checksum */
        bitv_shiftin(allbits, infop->csumbits, 0);

        /* compute checksum */
        limbit = infop->numx * 5;
        for (bit = 0; bit < infop->numx; bit++) {
                crc(&csum, bitv_chunk(allbits, limbit, limbit - 5));
                limbit -= 5;
        }

        /* insert the computed checksum */
        bitv_setlo(allbits, infop->csumbits, (unsigned)csum);

        /* encode binary values according to alphabet */
        limbit = infop->numx * 5;
        for (bit = 0; bit < infop->numx; bit++) {
                if (bit % 4 == 0)
                        *code++ = '-';
                *code++ = Alphabet[bitv_chunk(allbits, limbit, limbit - 5)];
                limbit -= 5;
        }

        *code = '\0';
        bitv_free(allbits);
        bitv_free(dictval);

        if (dhp->debug > 1)
                (void) fprintf(stderr, "code \"%s\"\n", codebegin);
        return (0);
}

/*
 * code2dictval -- convert a diagcode back to a bit vector
 */
static bitv *
code2dictval(fm_dc_handle_t *dhp, const char *code)
{
        const struct info *infop;
        int len = strlen(dhp->dictname);
        bitv *allbits;
        bitv *dictval;
        int numx;               /* number of X's we count */
        unsigned long ocsum;    /* original checksum in code */
        unsigned long csum;     /* our computed checksum */
        int bit;                /* for looping through bits */
        int limbit;             /* upper bit limit when looping */
        const char *ptr;

        /* check dictname part of code */
        if (strncasecmp(code, dhp->dictname, len) ||
            code[len] != '-') {
                errno = EINVAL;
                return (NULL);
        }

        /* convert code back to a bit vector */
        if ((allbits = bitv_alloc()) == NULL) {
                errno = ENOMEM;
                return (NULL);
        }

        /* we verified it began with dictname and a dash, so skip it */
        code = &code[len + 1];
        numx = 0;
        /* be forgiving about misplaced dashes */
        for (; *code; code++)
                if (*code == '-')
                        continue;
                else {
                        unsigned val;

                        for (val = 0; Alphabet[val]; val++)
                                if (*code == Alphabet[val])
                                        break;
                        if (Alphabet[val] == '\0') {
                                bitv_free(allbits);
                                errno = EINVAL;
                                return (NULL);
                        }
                        bitv_shiftin(allbits, 5, val);
                        numx++;
                }

        if ((infop = numx2info(numx)) == NULL) {
                bitv_free(allbits);
                errno = EINVAL;
                return (NULL);
        }

        /* now pull out the csum */
        ocsum = bitv_chunk(allbits, infop->csumbits, 0);

        /* set the csum bits to zero */
        bitv_setlo(allbits, infop->csumbits, 0);

        /* calculate the checksum and see if it matches */
        csum = 0;
        for (ptr = dhp->dictname; *ptr; ptr++)
                crc(&csum, (unsigned)*ptr);
        limbit = numx * 5;
        for (bit = 0; bit < numx; bit++) {
                crc(&csum, bitv_chunk(allbits, limbit, limbit - 5));
                limbit -= 5;
        }
        csum &= (1 << infop->csumbits) - 1;

        if (csum != ocsum) {
                bitv_free(allbits);
                errno = EINVAL;
                return (NULL);
        }

        /* code looks okay, just return dictval portion */
        if ((dictval = bitv_alloc()) == NULL) {
                bitv_free(allbits);
                errno = ENOMEM;
                return (NULL);
        }
        limbit = infop->csumbits + infop->databits;
        while (limbit > infop->csumbits) {
                bitv_shiftin(dictval, 1,
                    bitv_chunk(allbits, limbit, limbit - 1));
                limbit--;
        }
        bitv_free(allbits);

        /* add in the offset appropriate for the length of code being used */
        if (bitv_add(dictval, infop->offset) < 0) {
                /*
                 * overflow "cannot happen" since we've pulled in
                 * a given number of bits from the code and the offset
                 * is designed not to overflow...
                 */
                bitv_free(dictval);
                errno = ERANGE;
                return (NULL);
        }

        return (dictval);
}


/*
 * private routines to parse a line into name/value pairs...
 *
 */

/*
 * startparse -- record starting of buffer containing name=value pairs
 */
static void
startparse(struct parsestate *ps, char *ptr)
{
        ps->parseptr = ptr;
}

/*
 * nextlhs -- return next left-hand-side of name=value pair, or NULL
 *
 * whitespace around the '=' is allowed for, but not required.  the
 * lhs is a simple string that does not contain any whitespace or an
 * embedded equals sign.  no escaped characters, quotes, etc. are
 * honored here.
 *
 * this routine also parses the rhs and saves a pointer to it
 * in Rhsp so that nextrhs() can return it.  if nextrhs() never
 * gets called, we continue looking for the next lhs *after* any
 * rhs that was there.
 */
static char *
nextlhs(struct parsestate *ps)
{
        char *lhsp;
        char *copyto;
        int equals = 0;
        int quote = 0;
        int backslash = 0;

        /* skip whitespace */
        while (*ps->parseptr && isspace(*ps->parseptr))
                ps->parseptr++;

        /* anything left? */
        if (*ps->parseptr == '\0')
                return (NULL);

        /* remember start of lhs, assume no rhs until we see '=' */
        lhsp = ps->parseptr;

        /* find end of token, no escaped chars, quotes, etc. on lhs */
        while (*ps->parseptr && !isspace(*ps->parseptr))
                if (*ps->parseptr == '=') {
                        equals = 1;
                        break;
                } else
                        ps->parseptr++;

        /* null terminate the token, possibly nuking the '=' itself */
        *ps->parseptr++ = '\0';

        /* if we haven't seen an '=', see if it happens after whitespace */
        if (!equals) {
                while (*ps->parseptr && isspace(*ps->parseptr))
                        ps->parseptr++;
                if (*ps->parseptr == '=') {
                        equals = 1;
                        ps->parseptr++;
                }
        }

        /* skip whitespace */
        while (*ps->parseptr && isspace(*ps->parseptr))
                ps->parseptr++;

        /* isolate the rhs if it is there */
        if (!equals || *ps->parseptr == '\0') {
                ps->rhsp = NULL;
                return (lhsp);
        }

        if (*ps->parseptr == '"') {
                quote = 1;
                ps->parseptr++;
        }

        /* remember the beginning of the rhs */
        ps->rhsp = copyto = ps->parseptr;

        /* now scan to the end of the rhs */
        while (*ps->parseptr) {
                if (backslash) {
                        switch (*ps->parseptr) {
                        case 't':
                                *copyto++ = '\t';
                                break;

                        case 'r':
                                *copyto++ = '\r';
                                break;

                        case 'n':
                                *copyto++ = '\n';
                                break;

                        case 'f':
                                *copyto++ = '\f';
                                break;

                        default:
                                *copyto++ = *ps->parseptr;
                                break;
                        }

                        backslash = 0;
                } else if (*ps->parseptr == '\\')
                        backslash = 1;
                else if (quote) {
                        if (*ps->parseptr == '"') {
                                ps->parseptr++;
                                break;          /* end of quoted string */
                        } else
                                *copyto++ = *ps->parseptr;
                } else if (!isspace(*ps->parseptr))
                        *copyto++ = *ps->parseptr;
                else {
                        ps->parseptr++;
                        break;  /* rhs terminated by whitespace */
                }

                ps->parseptr++;
        }
        *copyto = '\0';

        return (lhsp);
}

/*
 * nextrhs -- return right-hand-side of name=value pair, or NULL
 *
 * this routine can only be used after a lhs has been found with
 * nextlhs().  the rhs consists of a string with no whitespace in it,
 * unless the whitespace is escaped with a backslash.  surrounding
 * a string with double quotes is also supported here, as are the
 * common C escape sequences like \t and \n.
 *
 * nextlhs() actually does all the hard work.  we just return any
 * rhs that was found by that routine.
 */
static char *
nextrhs(struct parsestate *ps)
{
        return (ps->rhsp);
}


/*
 * private routines to manipulate bit vectors (i.e. large integers)
 *
 * if these bit vector routines are ever supposed to be more
 * general, the desired length should be passed in to bitv_alloc()
 * instead of defining a maximum here.  but knowing the max ahead
 * of time allows for simpler code and we know the max that will
 * fit into a diagcode.  on the minimum side, the below define
 * must be at least sizeof (unsigned).
 */
#define BITV_MAX_BYTES 15

/* data structure used to hold a bit vector */
struct bitv {
        unsigned char v[BITV_MAX_BYTES];
};

/* allocate a new, zeroed out bit vector */
static bitv *
bitv_alloc(void)
{
        int i;
        struct bitv *bv = malloc(sizeof (*bv));

        if (bv)
                for (i = 0; i < BITV_MAX_BYTES; i++)
                        bv->v[i] = 0;

        return (bv);
}

/* free a bit vector that was allocated with bitv_alloc() */
static void
bitv_free(bitv *bv)
{
        free(bv);
}

/* shift left a bit vector by a given number of bits.  fill with zeros. */
static void
bitv_shift(bitv *bv, unsigned bits)
{
        while (bits > 0) {
                unsigned iterbits = bits;
                int i;

                /* how many bits this iteration?  8 max. */
                if (iterbits > 8)
                        iterbits = 8;

                for (i = BITV_MAX_BYTES - 1; i > 0; i--) {
                        bv->v[i] <<= iterbits;
                        bv->v[i] |= bv->v[i - 1] >> (8 - iterbits);
                }
                bv->v[0] <<= iterbits;

                bits -= iterbits;
        }
}

/* force a given number of bits to a specific value */
static void
bitv_setlo(bitv *bv, unsigned bits, unsigned val)
{
        int i = 0;

        /* assumption: bits * 8 <= sizeof (val) */

        while (bits > 0) {
                unsigned iterbits = bits;
                unsigned mask;

                if (iterbits > 8)
                        iterbits = 8;

                mask = (1 << iterbits) - 1;

                bv->v[i] &= ~mask;
                bv->v[i] |= val & mask;

                val >>= iterbits;
                bits -= iterbits;
                /*
                 * the following can't go off end of bv->v[] since
                 * BITV_MAX_BYTES is assumed to be at least sizeof
                 * unsigned and val can't be more than sizeof unsigned
                 * bytes long.
                 */
                i++;
        }
}

/* given a value and number of bits, shift it in from the right */
static void
bitv_shiftin(bitv *bv, unsigned bits, unsigned val)
{
        bitv_shift(bv, bits);
        bitv_setlo(bv, bits, val);
}

/* given a bit vector and a number of bits, shift it in from the right */
static void
bitv_shiftinv(bitv *bv, unsigned bits, const bitv *inbv)
{
        int byteindex = bits / 8;
        int iterbits = bits % 8;

        /* first handle partial byte shift in */
        bitv_shiftin(bv, iterbits, inbv->v[byteindex--]);

        /* now handle any remaining full byte shift ins */
        while (byteindex >= 0)
                bitv_shiftin(bv, 8, inbv->v[byteindex--]);
}

/* return the number of bits required to hold the current bit vector's value */
static int
bitv_bits(const bitv *bv)
{
        int i;

        for (i = BITV_MAX_BYTES - 1; i >= 0; i--)
                if (bv->v[i]) {
                        int bit;

                        for (bit = 7; bit >= 0; bit--)
                                if ((bv->v[i] >> bit) & 1)
                                        return (i * 8 + bit + 1);

                        /* this can't happen, so do *something* */
                        return ((i + 1) * 8);
                }

        return (0);
}

/* extract chunks of bits from bit vector */
static unsigned
bitv_chunk(const bitv *bv, unsigned limbit, unsigned lobit)
{
        unsigned retval = 0;
        int bit;

        /*
         * entry assumptions:
         *      limbit > lobit
         *      limbit - lobit <= sizeof (unsigned) * 8
         */

        for (bit = limbit - 1; bit >= 0 && bit >= lobit; bit--) {
                retval <<= 1;
                retval |= (bv->v[bit / 8] >> (bit % 8)) & 1;
        }

        return (retval);
}

/*
 * multiply by a given value
 *
 *      on overflow, bit vector will hold least significant BITV_MAX_BYTES,
 *      return value will be -1, and errno will be ERANGE.  otherwise
 *      return is zero and bit vector holds the product.
 */
static int
bitv_mul(bitv *bv, unsigned long long val)
{
        unsigned short result;
        unsigned char prod[BITV_MAX_BYTES];
        unsigned k = 0;
        int valbyte;
        int bvbyte;
        int i;

        /* start with a zeroed out bit vector to hold result */
        for (i = 0; i < BITV_MAX_BYTES; i++)
                prod[i] = 0;

        /* from most-significant byte of val to least... */
        for (valbyte = 0; valbyte < sizeof (val); valbyte++)
                /* from most significant byte of bv to least */
                for (bvbyte = 0; bvbyte < BITV_MAX_BYTES; bvbyte++) {
                        result = ((val >> (valbyte * 8)) & 0xff) *
                            bv->v[bvbyte] + k;

                        if (valbyte + bvbyte >= BITV_MAX_BYTES) {
                                /*
                                 * we're not storing digits past
                                 * BITV_MAX_BYTES, so if they aren't
                                 * zeros, then signal an overflow.
                                 */
                                if (result & 0xff) {
                                        errno = ERANGE;
                                        return (-1);
                                }
                        } else
                                prod[valbyte + bvbyte] += result & 0xff;

                        /* "carry the 1..." */
                        k = result >> 8;
                }

        /* store result in bv */
        for (i = 0; i < BITV_MAX_BYTES; i++)
                bv->v[i] = prod[i];

        return (0);
}

/*
 * add in a given value
 *
 *      on overflow, bit vector will hold least significant BITV_MAX_BYTES,
 *      return value will be -1, and errno will be ERANGE.  otherwise
 *      return is zero and bit vector holds the sum.
 */
static int
bitv_add(bitv *bv, unsigned long long val)
{
        int cf = 0;     /* carry flag */
        unsigned short result;
        int i;

        for (i = 0; i < BITV_MAX_BYTES; i++) {
                if (i < sizeof (val))
                        result = cf + bv->v[i] + ((val >> (i * 8)) & 0xff);
                else
                        result = cf + bv->v[i];

                cf = (result >> 8) & 1;
                bv->v[i] = result & 0xff;
        }

        if (cf) {
                errno = ERANGE;
                return (-1);
        }
        return (0);
}

/*
 * subtract out a given value
 *
 *      on underflow, bit vector will hold least significant BITV_MAX_BYTES,
 *      return value will be -1, and errno will be ERANGE.  otherwise
 *      return is zero and bit vector holds the difference.
 */
static int
bitv_sub(bitv *bv, unsigned long long val)
{
        int bf = 0;     /* borrow flag */
        unsigned short minuend;
        unsigned short subtrahend;
        int i;

        for (i = 0; i < BITV_MAX_BYTES; i++) {
                minuend = bv->v[i];
                if (i < sizeof (val))
                        subtrahend = bf + ((val >> (i * 8)) & 0xff);
                else
                        subtrahend = bf;
                if (subtrahend > minuend) {
                        bf = 1;
                        minuend += 1 << 8;
                } else
                        bf = 0;

                bv->v[i] = minuend - subtrahend;
        }

        if (bf) {
                errno = ERANGE;
                return (-1);
        }
        return (0);
}

/*
 * see if bv is greater than or equal to a given value
 */
static int
bitv_ge(const bitv *bv, unsigned long long val)
{
        int bf = 0;     /* borrow flag */
        unsigned short minuend;
        unsigned short subtrahend;
        int i;

        for (i = 0; i < BITV_MAX_BYTES; i++) {
                minuend = bv->v[i];
                if (i < sizeof (val))
                        subtrahend = bf + ((val >> (i * 8)) & 0xff);
                else
                        subtrahend = bf;
                if (subtrahend > minuend)
                        bf = 1;
                else
                        bf = 0;
        }

        return (!bf);
}

/* parse a string into bit vector, honor leading 0/0x for octal/hex */
static bitv *
bitv_strparse(const char *s, int bits)
{
        unsigned long long base = 10;
        unsigned long long val;
        bitv *bv = bitv_alloc();

        if (bv == NULL) {
                errno = ENOMEM;
                return (NULL);
        }

        if (*s == '0') {
                s++;
                if (*s == 'x') {
                        s++;
                        base = 16;
                } else
                        base = 8;
        }

        while (isxdigit(*s)) {
                /* isxdigit() let's in too much, depending on base */
                if (base == 8 && (*s < '0' || *s > '7'))
                        break;
                else if (base == 10 && !isdigit(*s))
                        break;

                /* convert the digit to binary */
                if (isdigit(*s))
                        val = *s - '0';
                else
                        val = tolower(*s) - 'a' + 10;

                /*
                 * multiply our big integer by base,
                 * add in the most recent digit,
                 * and check for overflow
                 */
                if (bitv_mul(bv, base) < 0 ||
                    bitv_add(bv, val) < 0 ||
                    bitv_bits(bv) > bits) {
                        bitv_free(bv);
                        errno = ERANGE;
                        return (NULL);
                }

                s++;
        }

        return (bv);
}

/* return 0 if two bit vectors represent the same number */
static int
bitv_cmp(const bitv *bv1, const bitv *bv2)
{
        int i;

        for (i = BITV_MAX_BYTES - 1; i >= 0; i--)
                if (bv1->v[i] < bv2->v[i])
                        return (-1);
                else if (bv1->v[i] > bv2->v[i])
                        return (1);
        return (0);
}


/* CRC code... */
static unsigned crctab[256] = {
        0x00000000,
        0x04C11DB7, 0x09823B6E, 0x0D4326D9, 0x130476DC, 0x17C56B6B,
        0x1A864DB2, 0x1E475005, 0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6,
        0x2B4BCB61, 0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD,
        0x4C11DB70, 0x48D0C6C7, 0x4593E01E, 0x4152FDA9, 0x5F15ADAC,
        0x5BD4B01B, 0x569796C2, 0x52568B75, 0x6A1936C8, 0x6ED82B7F,
        0x639B0DA6, 0x675A1011, 0x791D4014, 0x7DDC5DA3, 0x709F7B7A,
        0x745E66CD, 0x9823B6E0, 0x9CE2AB57, 0x91A18D8E, 0x95609039,
        0x8B27C03C, 0x8FE6DD8B, 0x82A5FB52, 0x8664E6E5, 0xBE2B5B58,
        0xBAEA46EF, 0xB7A96036, 0xB3687D81, 0xAD2F2D84, 0xA9EE3033,
        0xA4AD16EA, 0xA06C0B5D, 0xD4326D90, 0xD0F37027, 0xDDB056FE,
        0xD9714B49, 0xC7361B4C, 0xC3F706FB, 0xCEB42022, 0xCA753D95,
        0xF23A8028, 0xF6FB9D9F, 0xFBB8BB46, 0xFF79A6F1, 0xE13EF6F4,
        0xE5FFEB43, 0xE8BCCD9A, 0xEC7DD02D, 0x34867077, 0x30476DC0,
        0x3D044B19, 0x39C556AE, 0x278206AB, 0x23431B1C, 0x2E003DC5,
        0x2AC12072, 0x128E9DCF, 0x164F8078, 0x1B0CA6A1, 0x1FCDBB16,
        0x018AEB13, 0x054BF6A4, 0x0808D07D, 0x0CC9CDCA, 0x7897AB07,
        0x7C56B6B0, 0x71159069, 0x75D48DDE, 0x6B93DDDB, 0x6F52C06C,
        0x6211E6B5, 0x66D0FB02, 0x5E9F46BF, 0x5A5E5B08, 0x571D7DD1,
        0x53DC6066, 0x4D9B3063, 0x495A2DD4, 0x44190B0D, 0x40D816BA,
        0xACA5C697, 0xA864DB20, 0xA527FDF9, 0xA1E6E04E, 0xBFA1B04B,
        0xBB60ADFC, 0xB6238B25, 0xB2E29692, 0x8AAD2B2F, 0x8E6C3698,
        0x832F1041, 0x87EE0DF6, 0x99A95DF3, 0x9D684044, 0x902B669D,
        0x94EA7B2A, 0xE0B41DE7, 0xE4750050, 0xE9362689, 0xEDF73B3E,
        0xF3B06B3B, 0xF771768C, 0xFA325055, 0xFEF34DE2, 0xC6BCF05F,
        0xC27DEDE8, 0xCF3ECB31, 0xCBFFD686, 0xD5B88683, 0xD1799B34,
        0xDC3ABDED, 0xD8FBA05A, 0x690CE0EE, 0x6DCDFD59, 0x608EDB80,
        0x644FC637, 0x7A089632, 0x7EC98B85, 0x738AAD5C, 0x774BB0EB,
        0x4F040D56, 0x4BC510E1, 0x46863638, 0x42472B8F, 0x5C007B8A,
        0x58C1663D, 0x558240E4, 0x51435D53, 0x251D3B9E, 0x21DC2629,
        0x2C9F00F0, 0x285E1D47, 0x36194D42, 0x32D850F5, 0x3F9B762C,
        0x3B5A6B9B, 0x0315D626, 0x07D4CB91, 0x0A97ED48, 0x0E56F0FF,
        0x1011A0FA, 0x14D0BD4D, 0x19939B94, 0x1D528623, 0xF12F560E,
        0xF5EE4BB9, 0xF8AD6D60, 0xFC6C70D7, 0xE22B20D2, 0xE6EA3D65,
        0xEBA91BBC, 0xEF68060B, 0xD727BBB6, 0xD3E6A601, 0xDEA580D8,
        0xDA649D6F, 0xC423CD6A, 0xC0E2D0DD, 0xCDA1F604, 0xC960EBB3,
        0xBD3E8D7E, 0xB9FF90C9, 0xB4BCB610, 0xB07DABA7, 0xAE3AFBA2,
        0xAAFBE615, 0xA7B8C0CC, 0xA379DD7B, 0x9B3660C6, 0x9FF77D71,
        0x92B45BA8, 0x9675461F, 0x8832161A, 0x8CF30BAD, 0x81B02D74,
        0x857130C3, 0x5D8A9099, 0x594B8D2E, 0x5408ABF7, 0x50C9B640,
        0x4E8EE645, 0x4A4FFBF2, 0x470CDD2B, 0x43CDC09C, 0x7B827D21,
        0x7F436096, 0x7200464F, 0x76C15BF8, 0x68860BFD, 0x6C47164A,
        0x61043093, 0x65C52D24, 0x119B4BE9, 0x155A565E, 0x18197087,
        0x1CD86D30, 0x029F3D35, 0x065E2082, 0x0B1D065B, 0x0FDC1BEC,
        0x3793A651, 0x3352BBE6, 0x3E119D3F, 0x3AD08088, 0x2497D08D,
        0x2056CD3A, 0x2D15EBE3, 0x29D4F654, 0xC5A92679, 0xC1683BCE,
        0xCC2B1D17, 0xC8EA00A0, 0xD6AD50A5, 0xD26C4D12, 0xDF2F6BCB,
        0xDBEE767C, 0xE3A1CBC1, 0xE760D676, 0xEA23F0AF, 0xEEE2ED18,
        0xF0A5BD1D, 0xF464A0AA, 0xF9278673, 0xFDE69BC4, 0x89B8FD09,
        0x8D79E0BE, 0x803AC667, 0x84FBDBD0, 0x9ABC8BD5, 0x9E7D9662,
        0x933EB0BB, 0x97FFAD0C, 0xAFB010B1, 0xAB710D06, 0xA6322BDF,
        0xA2F33668, 0xBCB4666D, 0xB8757BDA, 0xB5365D03, 0xB1F740B4
};

static void
crc(unsigned long *crcp, unsigned val)
{
        *crcp = (*crcp<<8) ^ crctab[(unsigned char)((*crcp>>24)^val)];
}