src/parser/srp.c

/*
 * This file is part of DGD, https://github.com/dworkin/dgd
 * Copyright (C) 1993-2010 Dworkin B.V.
 * Copyright (C) 2010,2012 DGD Authors (see the commit log for details)
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

# include "dgd.h"
# include "srp.h"

typedef struct _item_ {
    char *ref;			/* pointer to rule in grammar */
    unsigned short ruleno;	/* rule number */
    unsigned short offset;	/* offset in rule */
    struct _item_ *next;	/* next in linked list */
} item;

# define ITCHUNKSZ	32

typedef struct _itchunk_ {
    int chunksz;		/* size of this chunk */
    item *flist;		/* list of free items */
    struct _itchunk_ *next;	/* next in linked list */
    item it[ITCHUNKSZ];		/* chunk of items */
} itchunk;

/*
 * NAME:	item->new()
 * DESCRIPTION:	create a new item
 */
static item *it_new(itchunk **c, char *ref, unsigned short ruleno, unsigned short offset, item *next)
{
    item *it;

    if (*c == (itchunk *) NULL ||
	((*c)->flist == (item *) NULL && (*c)->chunksz == ITCHUNKSZ)) {
	itchunk *x;

	x = ALLOC(itchunk, 1);
	x->flist = (*c != (itchunk *) NULL) ? (*c)->flist : (item *) NULL;
	x->next = *c;
	*c = x;
	x->chunksz = 0;
    }
    if ((*c)->flist != (item *) NULL) {
	it = (*c)->flist;
	(*c)->flist = it->next;
    } else {
	it = &(*c)->it[(*c)->chunksz++];
    }

    it->ref = ref;
    it->ruleno = ruleno;
    it->offset = offset;
    it->next = next;

    return it;
}

/*
 * NAME:	item->del()
 * DESCRIPTION:	delete an item
 */
static item *it_del(itchunk *c, item *it)
{
    item *next;

    next = it->next;
    it->next = c->flist;
    c->flist = it;
    return next;
}

/*
 * NAME:	item->clear()
 * DESCRIPTION:	free all items in memory
 */
static void it_clear(itchunk *c)
{
    itchunk *f;

    while (c != (itchunk *) NULL) {
	f = c;
	c = c->next;
	FREE(f);
    }
}

/*
 * NAME:	item->add()
 * DESCRIPTION:	add an item to a set
 */
static void it_add(itchunk **c, item **ri, char *ref, unsigned short ruleno, unsigned short offset, bool sort)
{
    /*
     * add item to set
     */
    if (offset == UCHAR(ref[0]) << 1) {
	offset = UCHAR(ref[1]);	/* skip possible function at the end */
    }

    if (sort) {
	while (*ri != (item *) NULL &&
	       ((*ri)->ref < ref ||
		((*ri)->ref == ref && (*ri)->offset <= offset))) {
	    if ((*ri)->ref == ref && (*ri)->offset == offset) {
		return;	/* already in set */
	    }
	    ri = &(*ri)->next;
	}
    } else {
	while (*ri != (item *) NULL) {
	    if ((*ri)->ref == ref && (*ri)->offset == offset) {
		return;	/* already in set */
	    }
	    ri = &(*ri)->next;
	}
    }

    *ri = it_new(c, ref, ruleno, offset, *ri);
}

/*
 * NAME:	item->load()
 * DESCRIPTION:	load an item
 */
static item *it_load(itchunk **c, unsigned short n, char **buf, char *grammar)
{
    char *p;
    item **ri;
    item *it;
    char *ref;
    unsigned short ruleno;

    ri = &it;
    p = *buf;
    do {
	ref = grammar + (UCHAR(p[0]) << 8) + UCHAR(p[1]);
	p += 2;
	ruleno = (UCHAR(p[0]) << 8) + UCHAR(p[1]);
	p += 2;
	*ri = it_new(c, ref, ruleno, UCHAR(*p++), (item *) NULL);
	ri = &(*ri)->next;
    } while (--n != 0);
    *buf = p;

    return it;
}

/*
 * NAME:	item->save()
 * DESCRIPTION:	save an item
 */
static char *it_save(item *it, char *buf, char *grammar)
{
    int offset;

    while (it != (item *) NULL) {
	offset = it->ref - grammar;
	*buf++ = offset >> 8;
	*buf++ = offset;
	*buf++ = it->ruleno >> 8;
	*buf++ = it->ruleno;
	*buf++ = it->offset;
	it = it->next;
    }

    return buf;
}


typedef struct {
    item *items;		/* rules and offsets */
    union {
	char e[4];		/* 1 */
	char *a;		/* > 1 */
    } reds;			/* reductions */
    unsigned short nitem;	/* # items */
    short nred;			/* # reductions, -1 if unexpanded */
    Int shoffset;		/* offset for shifts */
    Int gtoffset;		/* offset for gotos */
    unsigned short shcheck;	/* shift offset check */
    unsigned short next;	/* next in linked list */
    bool alloc;			/* reductions allocated? */
} srpstate;

# define REDA(state)   (((state)->nred == 1) ? \
			(state)->reds.e : (state)->reds.a)
# define UNEXPANDED	-1
# define NOSHIFT	((Int) 0xff800000L)

/*
 * NAME:	srpstate->hash()
 * DESCRIPTION:	put a new state in the hash table, or return an old one
 */
static unsigned short ss_hash(unsigned short *htab, Uint htabsize, srpstate *states, unsigned short idx)
{
    Uint h;
    srpstate *newstate;
    item *it, *it2;
    srpstate *s;
    unsigned short *sr;

    /* hash on items */
    newstate = &states[idx];
    h = 0;
    for (it = newstate->items; it != (item *) NULL; it = it->next) {
	h ^= (uintptr_t) it->ref;
	h = (h >> 3) ^ (h << 29) ^ it->offset;
    }

    /* check state hash table */
    sr = &htab[(Uint) h % htabsize];
    s = &states[*sr];
    while (s != states) {
	it = newstate->items;
	it2 = s->items;
	while (it != (item *) NULL && it2 != (item *) NULL &&
	       it->ref == it2->ref && it->offset == it2->offset) {
	    it = it->next;
	    it2 = it2->next;
	}
	if (it == it2) {
	    return *sr;	/* state already exists */
	}
	sr = &s->next;
	s = &states[*sr];
    }

    newstate->next = *sr;
    return *sr = idx;
}

/*
 * NAME:	srpstate->load()
 * DESCRIPTION:	load a srpstate
 */
static char *ss_load(char *buf, char **rbuf, srpstate *state)
{
    state->items = (item *) NULL;
    state->nitem = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]);
    buf += 2;
    state->nred = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]);
    buf += 2;
    state->shoffset = ((Int) SCHAR(buf[0]) << 16) + (UCHAR(buf[1]) << 8) +
		      UCHAR(buf[2]);
    buf += 3;
    state->gtoffset = ((Int) SCHAR(buf[0]) << 16) + (UCHAR(buf[1]) << 8) +
		      UCHAR(buf[2]);
    buf += 3;
    state->shcheck = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]);
    buf += 2;

    if (state->nred > 0) {
	if (state->nred == 1) {
	    memcpy(state->reds.e, *rbuf, 4);
	} else {
	    state->reds.a = *rbuf;
	}
	*rbuf += 4 * state->nred;
    }
    state->alloc = FALSE;

    return buf;
}

/*
 * NAME:	srpstate->save()
 * DESCRIPTION:	save a srpstate
 */
static char *ss_save(srpstate *state, char *buf, char **rbuf)
{
    *buf++ = state->nitem >> 8;
    *buf++ = state->nitem;
    *buf++ = state->nred >> 8;
    *buf++ = state->nred;
    *buf++ = state->shoffset >> 16;
    *buf++ = state->shoffset >> 8;
    *buf++ = state->shoffset;
    *buf++ = state->gtoffset >> 16;
    *buf++ = state->gtoffset >> 8;
    *buf++ = state->gtoffset;
    *buf++ = state->shcheck >> 8;
    *buf++ = state->shcheck;

    if (state->nred > 0) {
	memcpy(*rbuf, REDA(state), state->nred * 4);
	*rbuf += state->nred * 4;
    }

    return buf;
}


typedef struct _shlink_ {
    Int shifts;			/* offset in shift table */
    struct _shlink_ *next;	/* next in linked list */
} shlink;

# define SLCHUNKSZ	64

typedef struct _slchunk_ {
    int chunksz;		/* size of chunk */
    struct _slchunk_ *next;	/* next in linked list */
    shlink sl[SLCHUNKSZ];	/* shlinks */
} slchunk;

/*
 * NAME:	shlink->hash()
 * DESCRIPTION:	put a new shlink in the hash table, or return an old one
 */
static shlink *sl_hash(shlink **htab, Uint htabsize, slchunk **c, char *shtab, char *shifts, Uint n)
{
    unsigned long h;
    Uint i;
    shlink **ssl, *sl;

    /* search in hash table */
    shifts += 5;
    n -= 5;
    h = 0;
    for (i = n; i > 0; --i) {
	h = (h >> 3) ^ (h << 29) ^ UCHAR(*shifts++);
    }
    shifts -= n;
    ssl = &htab[h % htabsize];
    while (*ssl != (shlink *) NULL) {
	if (memcmp(shtab + (*ssl)->shifts + 5, shifts, n) == 0) {
	    /* seen this one before */
	    return *ssl;
	}
	ssl = &(*ssl)->next;
    }

    if (*c == (slchunk *) NULL || (*c)->chunksz == SLCHUNKSZ) {
	slchunk *x;

	x = ALLOC(slchunk, 1);
	x->next = *c;
	*c = x;
	x->chunksz = 0;
    }
    sl = &(*c)->sl[(*c)->chunksz++];
    sl->next = *ssl;
    *ssl = sl;
    sl->shifts = NOSHIFT;

    return sl;
}

/*
 * NAME:	shlink->clear()
 * DESCRIPTION:	clean up shlinks
 */
static void sl_clear(slchunk *c)
{
    slchunk *f;

    while (c != (slchunk *) NULL) {
	f = c;
	c = c->next;
	FREE(f);
    }
}


struct _srp_ {
    char *grammar;		/* grammar */
    unsigned short nsstring;	/* # of source grammar strings */
    unsigned short ntoken;	/* # of tokens (regexp & string) */
    unsigned short nprod;	/* # of nonterminals */

    Uint nred;			/* # of reductions */
    Uint nitem;			/* # of items */
    Uint srpsize;		/* size of shift/reduce parser */
    Uint tmpsize;		/* size of temporary data */
    bool modified;		/* srp needs saving */
    bool allocated;		/* srp allocated */
    char *srpstr;		/* srp string */
    char *tmpstr;		/* tmp string */

    unsigned short nstates;	/* number of states */
    unsigned short nexpanded;	/* number of expanded states */
    Uint sttsize;		/* state table size */
    Uint sthsize;		/* state hash table size */
    srpstate *states;		/* state array */
    unsigned short *sthtab;	/* state hash table */

    itchunk *itc;		/* item chunk */

    Uint gap;			/* first gap in packed mapping */
    Uint spread;		/* max spread in packed mapping */
    Uint mapsize;		/* packed mapping size */
    char *data;			/* packed shifts */
    char *check;		/* packed check for shift validity */
    bool alloc;			/* data and check allocated separately? */

    slchunk *slc;		/* shlink chunk */
    Uint nshift;		/* number of shifts (from/to pairs) */
    Uint shtsize;		/* shift table size */
    Uint shhsize;		/* shift hash table size */
    char *shtab;		/* shift (from/to) table */
    shlink **shhtab;		/* shift hash table */
};

# define SRP_VERSION	1

/*
 * NAME:	srp->new()
 * DESCRIPTION:	create new shift/reduce parser
 */
srp *srp_new(char *grammar)
{
    srp *lr;
    char *p;
    Uint nrule;

    lr = ALLOC(srp, 1);

    /* grammar info */
    lr->grammar = grammar;
    lr->nsstring = (UCHAR(grammar[9]) << 8) + UCHAR(grammar[10]);
    lr->ntoken = lr->nsstring +
		 ((UCHAR(grammar[5]) + UCHAR(grammar[11])) << 8) +
		 UCHAR(grammar[6]) + UCHAR(grammar[12]);
    lr->nprod = (UCHAR(grammar[13]) << 8) + UCHAR(grammar[14]);
    nrule = (UCHAR(grammar[15]) << 8) + UCHAR(grammar[16]);

    /* sizes */
    lr->srpstr = (char *) NULL;
    lr->tmpstr = (char *) NULL;
    lr->nred = lr->nitem = 0;
    lr->srpsize = 14 + 12 + 4;	/* srp header + 1 state + data/check overhead */
    lr->tmpsize = 7 + 5;	/* tmp header + 1 item */
    lr->modified = TRUE;
    lr->allocated = FALSE;

    /* states */
    lr->nstates = 1;
    lr->nexpanded = 0;
    lr->sttsize = nrule << 1;
    lr->sthsize = nrule << 2;
    lr->states = ALLOC(srpstate, lr->sttsize);
    lr->sthtab = ALLOC(unsigned short, lr->sthsize);
    memset(lr->sthtab, '\0', lr->sthsize * sizeof(unsigned short));
    lr->itc = (itchunk *) NULL;

    /* state 0 */
    p = grammar + 17 + ((lr->ntoken + lr->nsstring) << 1);
    p = grammar + (UCHAR(p[0]) << 8) + UCHAR(p[1]);
    lr->states[0].items = it_new(&lr->itc, p + 2, lr->ntoken, 0, (item *) NULL);
    lr->states[0].nitem = 1;
    lr->states[0].nred = UNEXPANDED;
    lr->states[0].shoffset = NOSHIFT;
    lr->states[0].gtoffset = 0;
    lr->states[0].shcheck = 0;
    lr->states[0].alloc = FALSE;

    /* packed mapping for shift */
    lr->gap = lr->spread = 0;
    lr->mapsize = (Uint) (lr->ntoken + lr->nprod) << 2;
    lr->data = ALLOC(char, lr->mapsize);
    memset(lr->data, '\0', lr->mapsize);
    lr->check = ALLOC(char, lr->mapsize);
    memset(lr->check, '\xff', lr->mapsize);
    lr->alloc = TRUE;

    /* shift hash table */
    lr->slc = (slchunk *) NULL;
    lr->nshift = 0;
    lr->shtsize = lr->mapsize;
    lr->shhsize = nrule << 2;
    lr->shtab = ALLOC(char, lr->shtsize);
    lr->shhtab = ALLOC(shlink*, lr->shhsize);
    memset(lr->shhtab, '\0', lr->shhsize * sizeof(shlink*));

    return lr;
}

/*
 * NAME:	srp->del()
 * DESCRIPTION:	delete shift/reduce parser
 */
void srp_del(srp *lr)
{
    unsigned short i;
    srpstate *state;

    if (lr->allocated) {
	FREE(lr->srpstr);
    }
    it_clear(lr->itc);
    if (lr->sthtab != (unsigned short *) NULL) {
	FREE(lr->sthtab);
    }
    for (i = lr->nstates, state = lr->states; i > 0; --i, state++) {
	if (state->alloc) {
	    FREE(state->reds.a);
	}
    }
    FREE(lr->states);
    if (lr->alloc) {
	FREE(lr->data);
	FREE(lr->check);
    }
    sl_clear(lr->slc);
    if (lr->shtab != (char *) NULL) {
	FREE(lr->shtab);
    }
    if (lr->shhtab != (shlink **) NULL) {
	FREE(lr->shhtab);
    }
    FREE(lr);
}

/*
 * format of SRP permanent data:
 *
 * header	[1]		version number
 *		[x][y]		# states
 *		[x][y]		# expanded states
 *		[x][y][z]	# reductions
 *		[x][y][z]	initial gap in packed mapping
 *		[x][y][z]	max spread of packed mapping
 *
 * state	[x][y]		# items				}
 *		[x][y]		# reductions			}
 *		[x][y][z]	shift offset in packed mapping	} ...
 *		[x][y][z]	goto offset in packed mapping	}
 *		[x][y]		shift check			}
 *
 * reduction	[x][y]		rule offset in grammar		} ...
 *		[x][y]		rule number			}
 *
 * mapping	[...]		data table (spread + 2)
 *		[...]		check table (spread + 2)
 *
 *
 * format of SRP temporary data:
 *
 * header	[0]		version number
 *		[x][y][z]	# items
 *		[x][y][z]	shift table size
 *
 * item		[x][y]		rule offset in grammar		}
 *		[x][y]		rule number			} ...
 *		[x]		offset in rule			}
 *
 * shift	[...]		shift table
 */

/*
 * NAME:	srp->load()
 * DESCRIPTION:	load a shift/reduce parser from string
 */
srp *srp_load(char *grammar, char *str, Uint len)
{
    srp *lr;
    char *buf;
    Uint i;
    srpstate *state;
    char *rbuf;

    if (UCHAR(str[0]) != SRP_VERSION) {
	return srp_new(grammar);
    }

    lr = ALLOC(srp, 1);

    /* grammar info */
    lr->grammar = grammar;
    lr->nsstring = (UCHAR(grammar[9]) << 8) + UCHAR(grammar[10]);
    lr->ntoken = lr->nsstring +
		 ((UCHAR(grammar[5]) + UCHAR(grammar[11])) << 8) +
		 UCHAR(grammar[6]) + UCHAR(grammar[12]);
    lr->nprod = (UCHAR(grammar[13]) << 8) + UCHAR(grammar[14]);

    lr->srpstr = buf = str;

    /* header */
    lr->nstates = (UCHAR(buf[1]) << 8) + UCHAR(buf[2]);
    lr->nexpanded = (UCHAR(buf[3]) << 8) + UCHAR(buf[4]);
    lr->nred = ((Uint) UCHAR(buf[5]) << 16) + (UCHAR(buf[6]) << 8) +
	       UCHAR(buf[7]);
    lr->gap = ((Uint) UCHAR(buf[8]) << 16) + (UCHAR(buf[9]) << 8) +
	      UCHAR(buf[10]);
    lr->spread = ((Uint) UCHAR(buf[11]) << 16) + (UCHAR(buf[12]) << 8) +
		 UCHAR(buf[13]);
    buf += 14;

    /* states */
    lr->sttsize = lr->nstates + 1;
    lr->sthsize = 0;
    lr->states = ALLOC(srpstate, lr->sttsize);
    lr->sthtab = (unsigned short *) NULL;
    lr->itc = (itchunk *) NULL;

    /* load states */
    rbuf = buf + lr->nstates * 12;
    for (i = lr->nstates, state = lr->states; i > 0; --i, state++) {
	buf = ss_load(buf, &rbuf, state);
    }
    buf = rbuf;

    /* load packed mapping */
    lr->mapsize = lr->spread + 2;
    lr->data = buf;
    buf += lr->spread + 2;
    lr->check = buf;
    buf += lr->spread + 2;
    lr->alloc = FALSE;

    lr->tmpstr = buf;

    /* sizes */
    lr->nitem = 0;
    lr->srpsize = (intptr_t) buf - (intptr_t) str;
    lr->tmpsize = len - lr->srpsize;
    lr->modified = lr->allocated = FALSE;

    /* shift hash table */
    lr->slc = (slchunk *) NULL;
    lr->nshift = 0;
    lr->shtsize = 0;
    lr->shhsize = 0;
    lr->shtab = (char *) NULL;
    lr->shhtab = (shlink **) NULL;

    return lr;
}

/*
 * NAME:	srp->loadtmp()
 * DESCRIPTION:	load the temporary data for a shift/reduce parser
 */
static void srp_loadtmp(srp *lr)
{
    Uint i, n;
    srpstate *state;
    char *p;
    Uint nrule;
    char *buf;

    nrule = (UCHAR(lr->grammar[15]) << 8) + UCHAR(lr->grammar[16]);

    buf = lr->tmpstr;
    lr->nitem = ((Uint) UCHAR(buf[1]) << 16) + (UCHAR(buf[2]) << 8) +
		UCHAR(buf[3]);
    lr->nshift = ((Uint) UCHAR(buf[4]) << 16) + (UCHAR(buf[5]) << 8) +
		 UCHAR(buf[6]);
    buf += 7;

    /* states */
    lr->sthsize = nrule << 2;
    lr->sthtab = ALLOC(unsigned short, lr->sthsize);
    memset(lr->sthtab, '\0', lr->sthsize * sizeof(unsigned short));
    for (i = 0, state = lr->states; i < lr->nstates; i++, state++) {
	if (state->nitem != 0) {
	    state->items = it_load(&lr->itc, state->nitem, &buf, lr->grammar);
	}
	ss_hash(lr->sthtab, lr->sthsize, lr->states, (unsigned short) i);
    }

    /* shifts */
    lr->shtsize = lr->nshift * 2;
    lr->shhsize = nrule << 2;
    lr->shtab = ALLOC(char, lr->shtsize);
    memcpy(lr->shtab, buf, lr->nshift);
    lr->shhtab = ALLOC(shlink*, lr->shhsize);
    memset(lr->shhtab, '\0', lr->shhsize * sizeof(shlink*));
    for (i = 0, p = buf; i != lr->nshift; i += n, p += n) {
	n = (Uint) 4 * ((UCHAR(p[5]) << 8) + UCHAR(p[6])) + 7;
	sl_hash(lr->shhtab, lr->shhsize, &lr->slc, lr->shtab, p, n)->shifts =
						(intptr_t) p - (intptr_t) buf;
    }
}

/*
 * NAME:	srp->save()
 * DESCRIPTION:	save a shift/reduce parser to string
 */
bool srp_save(srp *lr, char **str, Uint *len)
{
    char *buf;
    unsigned short i;
    srpstate *state;
    char *rbuf;

    if (!lr->modified) {
	*str = lr->srpstr;
	*len = lr->srpsize + lr->tmpsize;
	return FALSE;
    }

    if (lr->nstates == lr->nexpanded) {
	lr->tmpsize = 0;
    }
    if (lr->allocated) {
	FREE(lr->srpstr);
    }
    lr->srpstr = buf = *str = ALLOC(char, *len = lr->srpsize + lr->tmpsize);

    /* header */
    *buf++ = SRP_VERSION;
    *buf++ = lr->nstates >> 8;
    *buf++ = lr->nstates;
    *buf++ = lr->nexpanded >> 8;
    *buf++ = lr->nexpanded;
    *buf++ = lr->nred >> 16;
    *buf++ = lr->nred >> 8;
    *buf++ = lr->nred;
    *buf++ = lr->gap >> 16;
    *buf++ = lr->gap >> 8;
    *buf++ = lr->gap;
    *buf++ = lr->spread >> 16;
    *buf++ = lr->spread >> 8;
    *buf++ = lr->spread;

    /* save states */
    rbuf = buf + lr->nstates * 12;
    for (i = lr->nstates, state = lr->states; i > 0; --i, state++) {
	buf = ss_save(state, buf, &rbuf);
    }
    buf = rbuf;

    /* save packed mapping */
    memcpy(buf, lr->data, lr->spread + 2);
    buf += lr->spread + 2;
    memcpy(buf, lr->check, lr->spread + 2);
    buf += lr->spread + 2;

    lr->modified = FALSE;
    lr->allocated = TRUE;
    if (lr->tmpsize == 0) {
	/* no tmp data */
	return TRUE;
    }

    lr->tmpstr = buf;

    /* tmp header */
    *buf++ = 0;
    *buf++ = lr->nitem >> 16;
    *buf++ = lr->nitem >> 8;
    *buf++ = lr->nitem;
    *buf++ = lr->nshift >> 16;
    *buf++ = lr->nshift >> 8;
    *buf++ = lr->nshift;

    /* save items */
    for (i = lr->nstates, state = lr->states; i > 0; --i, state++) {
	buf = it_save(state->items, buf, lr->grammar);
    }

    /* shift data */
    memcpy(buf, lr->shtab, lr->nshift);

    return TRUE;
}

/*
 * NAME:	srp->pack()
 * DESCRIPTION:	add a new set of shifts and gotos to the packed mapping
 */
static Int srp_pack(srp *lr, unsigned short *check, unsigned short *from, unsigned short *to, unsigned short n)
{
    Uint i, j;
    char *p;
    char *shifts;
    shlink *sl;
    Uint range, *offstab;
    Int offset;

    /*
     * check hash table
     */
    shifts = ALLOCA(char, j = (Uint) 4 * n + 7);
    p = shifts + 5;
    *p++ = n >> 8;
    *p++ = n;
    for (i = 0; i < n; i++) {
	*p++ = from[i] >> 8;
	*p++ = from[i];
	*p++ = to[i] >> 8;
	*p++ = to[i];
    }
    sl = sl_hash(lr->shhtab, lr->shhsize, &lr->slc, lr->shtab, shifts, j);
    if (sl->shifts != NOSHIFT) {
	/* same as before */
	AFREE(shifts);
	p = lr->shtab + sl->shifts;
	*check = (UCHAR(p[0]) << 8) + UCHAR(p[1]);
	return ((Int) SCHAR(p[2]) << 16) + ((UCHAR(p[3]) << 8) + UCHAR(p[4]));
    }

    /* not in hash table */
    if (lr->nshift + j > lr->shtsize) {
	/* grow shift table */
	i = (lr->nshift + j) * 2;
	lr->shtab = REALLOC(lr->shtab, char, lr->shtsize, i);
	lr->shtsize = i;
    }
    sl->shifts = lr->nshift;
    lr->nshift += j;
    lr->tmpsize += j;
    memcpy(lr->shtab + sl->shifts, shifts, j);
    AFREE(shifts);

    /* create offset table */
    offstab = ALLOCA(Uint, n);
    for (i = 0; i < n; i++) {
	offstab[i] = from[i] * 2;
    }
    j = offset = offstab[0];
    for (i = 1; i < n; i++) {
	offstab[i] -= j;
	j += offstab[i];
    }
    range = j - offset + 2;

    /*
     * add from/to pairs to packed mapping
     */
    for (i = lr->gap, p = &lr->check[i];
	 UCHAR(p[0]) != 0xff || UCHAR(p[1]) != 0xff;
	 i += 2, p += 2) ;
    lr->gap = i;

next:
    if (i + range >= lr->mapsize) {
	/* grow tables */
	j = (i + range) << 1;
	if (lr->alloc) {
	    lr->data = REALLOC(lr->data, char, lr->mapsize, j);
	    lr->check = REALLOC(lr->check, char, lr->mapsize, j);
	} else {
	    char *table;

	    table = ALLOC(char, j);
	    memcpy(table, lr->data, lr->mapsize);
	    lr->data = table;
	    table = ALLOC(char, j);
	    memcpy(table, lr->check, lr->mapsize);
	    lr->check = table;
	    lr->alloc = TRUE;
	}
	memset(lr->data + lr->mapsize, '\0', j - lr->mapsize);
	memset(lr->check + lr->mapsize, '\xff', j - lr->mapsize);
	lr->mapsize = j;
    }

    /* match each symbol with free slot */
    for (j = 1; j < n; j++) {
	p += offstab[j];
	if (UCHAR(p[0]) != 0xff || UCHAR(p[1]) != 0xff) {
	    p = &lr->check[i];
	    do {
		i += 2;
		p += 2;
	    } while (UCHAR(p[0]) != 0xff || UCHAR(p[1]) != 0xff);
	    goto next;
	}
    }
    AFREE(offstab);

    /* free slots found: adjust spread */
    if (i + range > lr->spread) {
	lr->srpsize += 2 * (i + range - lr->spread);
	lr->spread = i + range;
    }

    /* add to packed mapping */
    offset = i - offset;
    do {
	j = from[--n] * 2 + offset;
	p = &lr->data[j];
	*p++ = to[n] >> 8;
	*p = to[n];
	p = &lr->check[j];
	*p++ = *check >> 8;
	*p = *check;
    } while (n != 0);

    p = lr->shtab + sl->shifts;
    offset /= 2;
    *p++ = *check >> 8;
    *p++ = *check;
    *p++ = offset >> 16;
    *p++ = offset >> 8;
    *p = offset;
    return offset;
}

/*
 * NAME:	cmp()
 * DESCRIPTION:	compare two unsigned shorts
 */
static int cmp(cvoid *sh1, cvoid *sh2)
{
    return (*(unsigned short *) sh1 < *(unsigned short *) sh2) ?
	    -1 : (*(unsigned short *) sh1 == *(unsigned short *) sh2) ? 0 : 1;
}

/*
 * NAME:	srp->expand()
 * DESCRIPTION:	expand a state
 */
static srpstate *srp_expand(srp *lr, srpstate *state)
{
    unsigned short i, n;
    char *p;
    item *it;
    item **itemtab, *next;
    unsigned short *tokens, *symbols, *targets;
    srpstate *newstate;
    unsigned short nred, nshift, ngoto;

    lr->modified = TRUE;
    if (state - lr->states == 1) {
	/* final state */
	state->nred = 0;
	lr->nexpanded++;
	return state;
    }

    if (lr->sthtab == (unsigned short *) NULL) {
	srp_loadtmp(lr);	/* load tmp info */
    }

    n = lr->ntoken + lr->nprod;
    itemtab = ALLOCA(item*, n);
    memset(itemtab, '\0', n * sizeof(item*));
    symbols = ALLOCA(unsigned short, n);
    targets = ALLOCA(unsigned short, n);
    tokens = ALLOCA(unsigned short, lr->ntoken);
    nred = nshift = ngoto = 0;

    /*
     * compute closure of kernel item set
     */
    for (it = state->items; it != (item *) NULL; it = it->next) {
	i = it->offset;
	p = it->ref + 1;
	if (i == UCHAR(*p++)) {
	    /* end of production */
	    nred++;
	} else {
	    p += i;
	    n = (UCHAR(p[0]) << 8) + UCHAR(p[1]);
	    if (n >= lr->ntoken) {
		p = lr->grammar + 17 + ((n + lr->nsstring) << 1);
		p = lr->grammar + (UCHAR(p[0]) << 8) + UCHAR(p[1]);
		for (i = (UCHAR(p[0]) << 8) + UCHAR(p[1]), p += 2; i > 0; --i) {
		    it_add(&lr->itc, &state->items, p, n, 0, FALSE);
		    p += UCHAR(p[1]) + 2;
		}
	    }
	}
    }

    state->nred = nred;
    if (nred != 0) {
	if (nred > 1) {
	    state->reds.a = ALLOC(char, (Uint) nred << 2);
	    state->alloc = TRUE;
	}
	lr->nred += nred;
	lr->srpsize += (Uint) nred << 2;
	nred = 0;
    }

    /*
     * compute reductions and shifts
     */
    if (state == lr->states) {
	symbols[ngoto++] = lr->ntoken;
    }
    for (it = state->items; it != (item *) NULL; it = it->next) {
	p = it->ref;
	if (it->offset == UCHAR(p[1])) {
	    /* reduction */
	    n = p - lr->grammar;
	    p = &REDA(state)[(Uint) nred++ << 2];
	    *p++ = n >> 8;
	    *p++ = n;
	    *p++ = it->ruleno >> 8;
	    *p = it->ruleno;
	} else {
	    /* shift/goto */
	    p += 2 + it->offset;
	    n = (UCHAR(p[0]) << 8) + UCHAR(p[1]);
	    if (itemtab[n] == (item *) NULL) {
		if (n < lr->ntoken) {
		    tokens[nshift++] = n;
		} else {
		    symbols[ngoto++] = n;
		}
	    }
	    it_add(&lr->itc, &itemtab[n], it->ref, it->ruleno, it->offset + 2,
		   TRUE);
	}
    }

    /*
     * delete non-kernel items
     */
    for (it = state->items, i = state->nitem; --i > 0; it = it->next) ;
    next = it->next;
    it->next = (item *) NULL;
    for (it = next; it != (item *) NULL; it = it_del(lr->itc, it)) ;

    /*
     * sort and merge token and goto tables
     */
    qsort(symbols, ngoto, sizeof(unsigned short), cmp);
    memcpy(symbols + ngoto, tokens, nshift * sizeof(unsigned short));
    AFREE(tokens);
    tokens = symbols + ngoto;
    qsort(tokens, nshift, sizeof(unsigned short), cmp);

    /*
     * create target table
     */
    for (i = 0; i < nshift + ngoto; i++) {
	newstate = &lr->states[lr->nstates];
	newstate->items = itemtab[symbols[i]];

	n = ss_hash(lr->sthtab, lr->sthsize, lr->states,
		    (unsigned short) lr->nstates);
	targets[i] = n;
	if (n == lr->nstates) {
	    /*
	     * new state
	     */
	    n = 0;
	    for (it = newstate->items; it != (item *) NULL; it = it->next) {
		n++;
	    }
	    lr->srpsize += 12;
	    lr->nitem += n;
	    lr->tmpsize += (Uint) 5 * n;
	    newstate->nitem = n;
	    newstate->nred = UNEXPANDED;
	    newstate->shoffset = NOSHIFT;
	    newstate->gtoffset = 0;
	    newstate->shcheck = 0;
	    newstate->alloc = FALSE;

	    if (++lr->nstates == lr->sttsize) {
		unsigned short save;

		/* grow table */
		save = state - lr->states;
		lr->states = REALLOC(lr->states, srpstate, lr->nstates,
				     lr->sttsize <<= 1);
		state = lr->states + save;
	    }
	}
    }

    /*
     * add shifts and gotos to packed mapping
     */
    if (nshift != 0) {
	state->shcheck = state - lr->states;
	state->shoffset = srp_pack(lr, &state->shcheck, tokens, targets + ngoto,
				   nshift);
    }
    if (ngoto != 0) {
	unsigned short dummy;

	dummy = -258;
	state->gtoffset = srp_pack(lr, &dummy, symbols, targets, ngoto);
    }
    AFREE(targets);
    AFREE(symbols);
    AFREE(itemtab);

    lr->nexpanded++;
    return state;
}

/*
 * NAME:	srp->check()
 * DESCRIPTION:	fetch reductions for a given state, possibly first expanding it
 */
short srp_check(srp *lr, unsigned int num, unsigned short *nredp, char **redp)
{
    srpstate *state;

    state = &lr->states[num];
    if (state->nred < 0) {
	state = srp_expand(lr, state);
	if (lr->srpsize + lr->tmpsize > (Uint) MAX_AUTOMSZ * USHRT_MAX) {
	    unsigned short save;

	    /*
	     * too much temporary data: attempt to expand all states
	     */
	    save = state - lr->states;
	    for (state = lr->states; lr->nstates != lr->nexpanded; state++) {
		if (lr->nstates > SHRT_MAX ||
		    lr->srpsize > (Uint) MAX_AUTOMSZ * USHRT_MAX) {
		    return -1;	/* too big */
		}
		if (state->nred < 0) {
		    state = srp_expand(lr, state);
		}
	    }
	    state = &lr->states[save];
	}
	if (lr->nstates > SHRT_MAX ||
	    lr->srpsize > (Uint) MAX_AUTOMSZ * USHRT_MAX) {
	    return -1;	/* too big */
	}
    }

    *nredp = state->nred;
    *redp = REDA(state);
    return lr->nstates;
}

/*
 * NAME:	srp->shift()
 * DESCRIPTION:	shift to a new state, if possible
 */
short srp_shift(srp *lr, unsigned int num, unsigned int token)
{
    Int n;
    char *p;
    srpstate *state;

    state = &lr->states[num];
    n = state->shoffset;
    if (n != NOSHIFT) {
	n = (n + (Int) token) * 2;
	if (n >= 0 && n < lr->mapsize) {
	    p = &lr->check[n];
	    if ((UCHAR(p[0]) << 8) + UCHAR(p[1]) == state->shcheck) {
		/* shift works: return new state */
		p = &lr->data[n];
		return (UCHAR(p[0]) << 8) + UCHAR(p[1]);
	    }
	}
    }

    /* shift failed */
    return -1;
}

/*
 * NAME:	srp->goto()
 * DESCRIPTION:	goto a new state
 */
short srp_goto(srp *lr, unsigned int num, unsigned int symb)
{
    char *p;

    p = &lr->data[(lr->states[num].gtoffset + symb) * 2];
    return (UCHAR(p[0]) << 8) + UCHAR(p[1]);
}