home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 5 / FreshFish_July-August1994.bin / bbs / gnu / flex-2.4.6-src.lha / src / amiga / flex-2.4.6 / tblcmp.c < prev    next >
C/C++ Source or Header  |  1993-12-07  |  24KB  |  889 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. /* $Header: /home/daffy/u0/vern/flex/RCS/tblcmp.c,v 2.10 93/12/07 10:18:30 vern Exp $ */
  30.  
  31. #include "flexdef.h"
  32.  
  33.  
  34. /* declarations for functions that have forward references */
  35.  
  36. void mkentry PROTO((register int*, int, int, int, int));
  37. void mkprot PROTO((int[], int, int));
  38. void mktemplate PROTO((int[], int, int));
  39. void mv2front PROTO((int));
  40. int tbldiff PROTO((int[], int, int[]));
  41.  
  42.  
  43. /* bldtbl - build table entries for dfa state
  44.  *
  45.  * synopsis
  46.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  47.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  48.  *
  49.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  50.  * gives the number of the state to enter for a given equivalence class.
  51.  * totaltrans is the total number of transitions out of the state.  Comstate
  52.  * is that state which is the destination of the most transitions out of State.
  53.  * Comfreq is how many transitions there are out of State to Comstate.
  54.  *
  55.  * A note on terminology:
  56.  *    "protos" are transition tables which have a high probability of
  57.  * either being redundant (a state processed later will have an identical
  58.  * transition table) or nearly redundant (a state processed later will have
  59.  * many of the same out-transitions).  A "most recently used" queue of
  60.  * protos is kept around with the hope that most states will find a proto
  61.  * which is similar enough to be usable, and therefore compacting the
  62.  * output tables.
  63.  *    "templates" are a special type of proto.  If a transition table is
  64.  * homogeneous or nearly homogeneous (all transitions go to the same
  65.  * destination) then the odds are good that future states will also go
  66.  * to the same destination state on basically the same character set.
  67.  * These homogeneous states are so common when dealing with large rule
  68.  * sets that they merit special attention.  If the transition table were
  69.  * simply made into a proto, then (typically) each subsequent, similar
  70.  * state will differ from the proto for two out-transitions.  One of these
  71.  * out-transitions will be that character on which the proto does not go
  72.  * to the common destination, and one will be that character on which the
  73.  * state does not go to the common destination.  Templates, on the other
  74.  * hand, go to the common state on EVERY transition character, and therefore
  75.  * cost only one difference.
  76.  */
  77.  
  78. void bldtbl( state, statenum, totaltrans, comstate, comfreq )
  79. int state[], statenum, totaltrans, comstate, comfreq;
  80.     {
  81.     int extptr, extrct[2][CSIZE + 1];
  82.     int mindiff, minprot, i, d;
  83.  
  84.     /* If extptr is 0 then the first array of extrct holds the result
  85.      * of the "best difference" to date, which is those transitions
  86.      * which occur in "state" but not in the proto which, to date,
  87.      * has the fewest differences between itself and "state".  If
  88.      * extptr is 1 then the second array of extrct hold the best
  89.      * difference.  The two arrays are toggled between so that the
  90.      * best difference to date can be kept around and also a difference
  91.      * just created by checking against a candidate "best" proto.
  92.      */
  93.  
  94.     extptr = 0;
  95.  
  96.     /* If the state has too few out-transitions, don't bother trying to
  97.      * compact its tables.
  98.      */
  99.  
  100.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  101.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  102.  
  103.     else
  104.         {
  105.         /* "checkcom" is true if we should only check "state" against
  106.          * protos which have the same "comstate" value.
  107.          */
  108.         int checkcom =
  109.             comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  110.  
  111.         minprot = firstprot;
  112.         mindiff = totaltrans;
  113.  
  114.         if ( checkcom )
  115.             {
  116.             /* Find first proto which has the same "comstate". */
  117.             for ( i = firstprot; i != NIL; i = protnext[i] )
  118.                 if ( protcomst[i] == comstate )
  119.                     {
  120.                     minprot = i;
  121.                     mindiff = tbldiff( state, minprot,
  122.                             extrct[extptr] );
  123.                     break;
  124.                     }
  125.             }
  126.  
  127.         else
  128.             {
  129.             /* Since we've decided that the most common destination
  130.              * out of "state" does not occur with a high enough
  131.              * frequency, we set the "comstate" to zero, assuring
  132.              * that if this state is entered into the proto list,
  133.              * it will not be considered a template.
  134.              */
  135.             comstate = 0;
  136.  
  137.             if ( firstprot != NIL )
  138.                 {
  139.                 minprot = firstprot;
  140.                 mindiff = tbldiff( state, minprot,
  141.                         extrct[extptr] );
  142.                 }
  143.             }
  144.  
  145.         /* We now have the first interesting proto in "minprot".  If
  146.          * it matches within the tolerances set for the first proto,
  147.          * we don't want to bother scanning the rest of the proto list
  148.          * to see if we have any other reasonable matches.
  149.          */
  150.  
  151.         if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  152.             {
  153.             /* Not a good enough match.  Scan the rest of the
  154.              * protos.
  155.              */
  156.             for ( i = minprot; i != NIL; i = protnext[i] )
  157.                 {
  158.                 d = tbldiff( state, i, extrct[1 - extptr] );
  159.                 if ( d < mindiff )
  160.                     {
  161.                     extptr = 1 - extptr;
  162.                     mindiff = d;
  163.                     minprot = i;
  164.                     }
  165.                 }
  166.             }
  167.  
  168.         /* Check if the proto we've decided on as our best bet is close
  169.          * enough to the state we want to match to be usable.
  170.          */
  171.  
  172.         if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  173.             {
  174.             /* No good.  If the state is homogeneous enough,
  175.              * we make a template out of it.  Otherwise, we
  176.              * make a proto.
  177.              */
  178.  
  179.             if ( comfreq * 100 >=
  180.                  totaltrans * TEMPLATE_SAME_PERCENTAGE )
  181.                 mktemplate( state, statenum, comstate );
  182.  
  183.             else
  184.                 {
  185.                 mkprot( state, statenum, comstate );
  186.                 mkentry( state, numecs, statenum,
  187.                     JAMSTATE, totaltrans );
  188.                 }
  189.             }
  190.  
  191.         else
  192.             { /* use the proto */
  193.             mkentry( extrct[extptr], numecs, statenum,
  194.                 prottbl[minprot], mindiff );
  195.  
  196.             /* If this state was sufficiently different from the
  197.              * proto we built it from, make it, too, a proto.
  198.              */
  199.  
  200.             if ( mindiff * 100 >=
  201.                  totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  202.                 mkprot( state, statenum, comstate );
  203.  
  204.             /* Since mkprot added a new proto to the proto queue,
  205.              * it's possible that "minprot" is no longer on the
  206.              * proto queue (if it happened to have been the last
  207.              * entry, it would have been bumped off).  If it's
  208.              * not there, then the new proto took its physical
  209.              * place (though logically the new proto is at the
  210.              * beginning of the queue), so in that case the
  211.              * following call will do nothing.
  212.              */
  213.  
  214.             mv2front( minprot );
  215.             }
  216.         }
  217.     }
  218.  
  219.  
  220. /* cmptmps - compress template table entries
  221.  *
  222.  * Template tables are compressed by using the 'template equivalence
  223.  * classes', which are collections of transition character equivalence
  224.  * classes which always appear together in templates - really meta-equivalence
  225.  * classes.
  226.  */
  227.  
  228. void cmptmps()
  229.     {
  230.     int tmpstorage[CSIZE + 1];
  231.     register int *tmp = tmpstorage, i, j;
  232.     int totaltrans, trans;
  233.  
  234.     peakpairs = numtemps * numecs + tblend;
  235.  
  236.     if ( usemecs )
  237.         {
  238.         /* Create equivalence classes based on data gathered on
  239.          * template transitions.
  240.          */
  241.         nummecs = cre8ecs( tecfwd, tecbck, numecs );
  242.         }
  243.  
  244.     el