/* tblcmp - table compression routines *//*- * Copyright (c) 1990 The Regents of the University of California. * All rights reserved. * * This code is derived from software contributed to Berkeley by * Vern Paxson. *  * The United States Government has rights in this work pursuant * to contract no. DE-AC03-76SF00098 between the United States * Department of Energy and the University of California. * * Redistribution and use in source and binary forms with or without * modification are permitted provided that: (1) source distributions retain * this entire copyright notice and comment, and (2) distributions including * binaries display the following acknowledgement:  ``This product includes * software developed by the University of California, Berkeley and its * contributors'' in the documentation or other materials provided with the * distribution and in all advertising materials mentioning features or use * of this software.  Neither the name of the University nor the names of * its contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. *//* $Header: /home/daffy/u0/vern/flex/RCS/tblcmp.c,v 2.11 94/11/05 17:08:28 vern Exp $ */#include "flexdef.h"/* declarations for functions that have forward references */void mkentry PROTO((register int*, int, int, int, int));void mkprot PROTO((int[], int, int));void mktemplate PROTO((int[], int, int));void mv2front PROTO((int));int tbldiff PROTO((int[], int, int[]));/* bldtbl - build table entries for dfa state * * synopsis *   int state[numecs], statenum, totaltrans, comstate, comfreq; *   bldtbl( state, statenum, totaltrans, comstate, comfreq ); * * State is the statenum'th dfa state.  It is indexed by equivalence class and * gives the number of the state to enter for a given equivalence class. * totaltrans is the total number of transitions out of the state.  Comstate * is that state which is the destination of the most transitions out of State. * Comfreq is how many transitions there are out of State to Comstate. * * A note on terminology: *    "protos" are transition tables which have a high probability of * either being redundant (a state processed later will have an identical * transition table) or nearly redundant (a state processed later will have * many of the same out-transitions).  A "most recently used" queue of * protos is kept around with the hope that most states will find a proto * which is similar enough to be usable, and therefore compacting the * output tables. *    "templates" are a special type of proto.  If a transition table is * homogeneous or nearly homogeneous (all transitions go to the same * destination) then the odds are good that future states will also go * to the same destination state on basically the same character set. * These homogeneous states are so common when dealing with large rule * sets that they merit special attention.  If the transition table were * simply made into a proto, then (typically) each subsequent, similar * state will differ from the proto for two out-transitions.  One of these * out-transitions will be that character on which the proto does not go * to the common destination, and one will be that character on which the * state does not go to the common destination.  Templates, on the other * hand, go to the common state on EVERY transition character, and therefore * cost only one difference. */void bldtbl( state, statenum, totaltrans, comstate, comfreq )int state[], statenum, totaltrans, comstate, comfreq;	{	int extptr, extrct[2][CSIZE + 1];	int mindiff, minprot, i, d;	/* If extptr is 0 then the first array of extrct holds the result	 * of the "best difference" to date, which is those transitions	 * which occur in "state" but not in the proto which, to date,	 * has the fewest differences between itself and "state".  If	 * extptr is 1 then the second array of extrct hold the best	 * difference.  The two arrays are toggled between so that the	 * best difference to date can be kept around and also a difference	 * just created by checking against a candidate "best" proto.	 */	extptr = 0;	/* If the state has too few out-transitions, don't bother trying to	 * compact its tables.	 */	if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )		mkentry( state, numecs, statenum, JAMSTATE, totaltrans );	else		{		/* "checkcom" is true if we should only check "state" against		 * protos which have the same "comstate" value.		 */		int checkcom =			comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;		minprot = firstprot;		mindiff = totaltrans;		if ( checkcom )			{			/* Find first proto which has the same "comstate". */			for ( i = firstprot; i != NIL; i = protnext[i] )				if ( protcomst[i] == comstate )					{					minprot = i;					mindiff = tbldiff( state, minprot,							extrct[extptr] );					break;					}			}		else			{			/* Since we've decided that the most common destination			 * out of "state" does not occur with a high enough			 * frequency, we set the "comstate" to zero, assuring			 * that if this state is entered into the proto list,			 * it will not be considered a template.			 */			comstate = 0;			if ( firstprot != NIL )				{				minprot = firstprot;				mindiff = tbldiff( state, minprot,						extrct[extptr] );				}			}		/* We now have the first interesting proto in "minprot".  If		 * it matches within the tolerances set for the first proto,		 * we don't want to bother scanning the rest of the proto list		 * to see if we have any other reasonable matches.		 */		if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )			{			/* Not a good enough match.  Scan the rest of the			 * protos.			 */			for ( i = minprot; i != NIL; i = protnext[i] )				{				d = tbldiff( state, i, extrct[1 - extptr] );				if ( d < mindiff )					{					extptr = 1 - extptr;					mindiff = d;					minprot = i;					}				}			}		/* Check if the proto we've decided on as our best bet is close		 * enough to the state we want to match to be usable.		 */		if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )			{			/* No good.  If the state is homogeneous enough,			 * we make a template out of it.  Otherwise, we			 * make a proto.			 */			if ( comfreq * 100 >=			     totaltrans * TEMPLATE_SAME_PERCENTAGE )				mktemplate( state, statenum, comstate );			else				{				mkprot( state, statenum, comstate );				mkentry( state, numecs, statenum,					JAMSTATE, totaltrans );				}			}		else			{ /* use the proto */			mkentry( extrct[extptr], numecs, statenum,				prottbl[minprot], mindiff );			/* If this state was sufficiently different from the			 * proto we built it from, make it, too, a proto.			 */			if ( mindiff * 100 >=			     totaltrans * NEW_PROTO_DIFF_PERCENTAGE )				mkprot( state, statenum, comstate );			/* Since mkprot added a new proto to the proto queue,			 * it's possible that "minprot" is no longer on the			 * proto queue (if it happened to have been the last			 * entry, it would have been bumped off).  If it's			 * not there, then the new proto took its physical			 * place (though logically the new proto is at the			 * beginning of the queue), so in that case the			 * following call will do nothing.			 */			mv2front( minprot );			}		}	}/* cmptmps - compress template table entries * * Template tables are compressed by using the 'template equivalence * classes', which are collections of transition character equivalence * classes which always appear together in templates - really meta-equivalence * classes. */void cmptmps()	{	int tmpstorage[CSIZE + 1];	register int *tmp = tmpstorage, i, j;	int totaltrans, trans;	peakpairs = numtemps * numecs + tblend;	if ( usemecs )		{		/* Create equivalence classes based on data gathered on		 * template transitions.		 */		nummecs = cre8ecs( tecfwd, tecbck, numecs );		}	else		nummecs = numecs;	while ( lastdfa + numtemps + 1 >= current_max_dfas )		increase_max_dfas();	/* Loop through each template. */	for ( i = 1; i <= numtemps; ++i )		{		/* Number of non-jam transitions out of this template. */		totaltrans = 0;		for ( j = 1; j <= numecs; ++j )			{			trans = tnxt[numecs * i + j];			if ( usemecs )				{				/* The absolute value of tecbck is the				 * meta-equivalence class of a given				 * equivalence class, as set up by cre8ecs().				 */				if ( tecbck[j] > 0 )					{					tmp[tecbck[j]] = trans;					if ( trans > 0 )						++totaltrans;					}				}			else				{				tmp[j] = trans;				if ( trans > 0 )					++totaltrans;				}			}		/* It is assumed (in a rather subtle way) in the skeleton		 * that if we're using meta-equivalence classes, the def[]		 * entry for all templates is the jam template, i.e.,		 * templates never default to other non-jam table entries		 * (e.g., another template)		 */		/* Leave room for the jam-state after the last real state. */		mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );		}	}/* expand_nxt_chk - expand the next check arrays */void expand_nxt_chk()	{	register int old_max = current_max_xpairs;	current_max_xpairs += MAX_XPAIRS_INCREMENT;	++num_reallocs;	nxt = reallocate_integer_array( nxt, current_max_xpairs );	chk = reallocate_integer_array( chk, current_max_xpairs );	zero_out( (char *) (chk + old_max),		(size_t) (MAX_XPAIRS_INCREMENT * sizeof( int )) );	}/* find_table_space - finds a space in the table for a state to be placed * * synopsis *     int *state, numtrans, block_start; *     int find_table_space(); * *     block_start = find_table_space( state, numtrans ); * * State is the state to be added to the full speed transition table. * Numtrans is the number of out-transitions for the state. * * find_table_space() returns the position of the start of the first block (in * chk) able to accommodate the state * * In determining if a state will or will not fit, find_table_space() must take * into account the fact that an end-of-buffer state will be added at [0], * and an action number will be added in [-1]. */int find_table_space( state, numtrans )int *state, numtrans;	{	/* Firstfree is the position of the first possible occurrence of two	 * consecutive unused records in the chk and nxt arrays.	 */	register int i;	register int *state_ptr, *chk_ptr;	register int *ptr_to_last_entry_in_state;	/* If there are too many out-transitions, put the state at the end of	 * nxt and chk.	 */	if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )		{		/* If table is empty, return the first available spot in		 * chk/nxt, which should be 1.		 */		if ( tblend < 2 )			return 1;		/* Start searching for table space near the end of		 * chk/nxt arrays.		 */		i = tblend - numecs;		}	else		/* Start searching for table space from the beginning		 * (skipping only the elements which will definitely not		 * hold the new state).		 */		i = firstfree;	while ( 1 )	/* loops until a space is found */		{		while ( i + numecs >= current_max_xpairs )			expand_nxt_chk();		/* Loops until space for end-of-buffer and action number		 * are found.		 */		while ( 1 )			{			/* Check for action number space. */			if ( chk[i - 1] == 0 )				{				/* Check for end-of-buffer space. */				if ( chk[i] == 0 )					break;				else					/* Since i != 0, there is no use					 * checking to see if (++i) - 1 == 0,					 * because that's the same as i == 0,					 * so we skip a space.					 */					i += 2;				}			else				++i;			while ( i + numecs >= current_max_xpairs )				expand_nxt_chk();			}		/* If we started search from the beginning, store the new		 * firstfree for the next call of find_table_space().		 */		if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )			firstfree = i + 1;		/* Check to see if all elements in chk (and therefore nxt)		 * that are needed for the new state have not yet been taken.		 */		state_ptr = &state[1];		ptr_to_last_entry_in_state = &chk[i + numecs + 1];		for ( chk_ptr = &chk[i + 1];		      chk_ptr != ptr_to_last_entry_in_state; ++chk_ptr )			if ( *(state_ptr++) != 0 && *chk_ptr != 0 )				break;		if ( chk_ptr == ptr_to_last_entry_in_state )			return i;		else		++i;		}	}/* inittbl - initialize transition tables * * Initializes "firstfree" to be one beyond the end of the table.  Initializes * all "chk" entries to be zero. */void inittbl()	{	register int i;	zero_out( (char *) chk, (size_t) (current_max_xpairs * sizeof( int )) );	tblend = 0;	firstfree = tblend + 1;	numtemps = 0;