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 with or without
15 * modification are permitted provided that: (1) source distributions retain
16 * this entire copyright notice and comment, and (2) distributions including
17 * binaries display the following acknowledgement: ``This product includes
18 * software developed by the University of California, Berkeley and its
19 * contributors'' in the documentation or other materials provided with the
20 * distribution and in all advertising materials mentioning features or use
21 * of this software. Neither the name of the University nor the names of
22 * its contributors may be used to endorse or promote products derived from
23 * this software without 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.11 94/11/05 17:08:28 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
bldtbl(state,statenum,totaltrans,comstate,comfreq)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
cmptmps()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 else
245 nummecs = numecs;
246
247 while ( lastdfa + numtemps + 1 >= current_max_dfas )
248 increase_max_dfas();
249
250 /* Loop through each template. */
251
252 for ( i = 1; i <= numtemps; ++i )
253 {
254 /* Number of non-jam transitions out of this template. */
255 totaltrans = 0;
256
257 for ( j = 1; j <= numecs; ++j )
258 {
259 trans = tnxt[numecs * i + j];
260
261 if ( usemecs )
262 {
263 /* The absolute value of tecbck is the
264 * meta-equivalence class of a given
265 * equivalence class, as set up by cre8ecs().
266 */
267 if ( tecbck[j] > 0 )
268 {
269 tmp[tecbck[j]] = trans;
270
271 if ( trans > 0 )
272 ++totaltrans;
273 }
274 }
275
276 else
277 {
278 tmp[j] = trans;
279
280 if ( trans > 0 )
281 ++totaltrans;
282 }
283 }
284
285 /* It is assumed (in a rather subtle way) in the skeleton
286 * that if we're using meta-equivalence classes, the def[]
287 * entry for all templates is the jam template, i.e.,
288 * templates never default to other non-jam table entries
289 * (e.g., another template)
290 */
291
292 /* Leave room for the jam-state after the last real state. */
293 mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
294 }
295 }
296
297
298
299 /* expand_nxt_chk - expand the next check arrays */
300
expand_nxt_chk()301 void expand_nxt_chk()
302 {
303 register int old_max = current_max_xpairs;
304
305 current_max_xpairs += MAX_XPAIRS_INCREMENT;
306
307 ++num_reallocs;
308
309 nxt = reallocate_integer_array( nxt, current_max_xpairs );
310 chk = reallocate_integer_array( chk, current_max_xpairs );
311
312 zero_out( (char *) (chk + old_max),
313 (size_t) (MAX_XPAIRS_INCREMENT * sizeof( int )) );
314 }
315
316
317 /* find_table_space - finds a space in the table for a state to be placed
318 *
319 * synopsis
320 * int *state, numtrans, block_start;
321 * int find_table_space();
322 *
323 * block_start = find_table_space( state, numtrans );
324 *
325 * State is the state to be added to the full speed transition table.
326 * Numtrans is the number of out-transitions for the state.
327 *
328 * find_table_space() returns the position of the start of the first block (in
329 * chk) able to accommodate the state
330 *
331 * In determining if a state will or will not fit, find_table_space() must take
332 * into account the fact that an end-of-buffer state will be added at [0],
333 * and an action number will be added in [-1].
334 */
335
find_table_space(state,numtrans)336 int find_table_space( state, numtrans )
337 int *state, numtrans;
338 {
339 /* Firstfree is the position of the first possible occurrence of two
340 * consecutive unused records in the chk and nxt arrays.
341 */
342 register int i;
343 register int *state_ptr, *chk_ptr;
344 register int *ptr_to_last_entry_in_state;
345
346 /* If there are too many out-transitions, put the state at the end of
347 * nxt and chk.
348 */
349 if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
350 {
351 /* If table is empty, return the first available spot in
352 * chk/nxt, which should be 1.
353 */
354 if ( tblend < 2 )
355 return 1;
356
357 /* Start searching for table space near the end of
358 * chk/nxt arrays.
359 */
360 i = tblend - numecs;
361 }
362
363 else
364 /* Start searching for table space from the beginning
365 * (skipping only the elements which will definitely not
366 * hold the new state).
367 */
368 i = firstfree;
369
370 while ( 1 ) /* loops until a space is found */
371 {
372 while ( i + numecs >= current_max_xpairs )
373 expand_nxt_chk();
374
375 /* Loops until space for end-of-buffer and action number
376 * are found.
377 */
378 while ( 1 )
379 {
380 /* Check for action number space. */
381 if ( chk[i - 1] == 0 )
382 {
383 /* Check for end-of-buffer space. */
384 if ( chk[i] == 0 )
385 break;
386
387 else
388 /* Since i != 0, there is no use
389 * checking to see if (++i) - 1 == 0,
390 * because that's the same as i == 0,
391 * so we skip a space.
392 */
393 i += 2;
394 }
395
396 else
397 ++i;
398
399 while ( i + numecs >= current_max_xpairs )
400 expand_nxt_chk();
401 }
402
403 /* If we started search from the beginning, store the new
404 * firstfree for the next call of find_table_space().
405 */
406 if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
407 firstfree = i + 1;
408
409 /* Check to see if all elements in chk (and therefore nxt)
410 * that are needed for the new state have not yet been taken.
411 */
412
413 state_ptr = &state[1];
414 ptr_to_last_entry_in_state = &chk[i + numecs + 1];
415
416 for ( chk_ptr = &chk[i + 1];
417 chk_ptr != ptr_to_last_entry_in_state; ++chk_ptr )
418 if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
419 break;
420
421 if ( chk_ptr == ptr_to_last_entry_in_state )
422 return i;
423
424 else
425 ++i;
426 }
427 }
428
429
430 /* inittbl - initialize transition tables
431 *
432 * Initializes "firstfree" to be one beyond the end of the table. Initializes
433 * all "chk" entries to be zero.
434 */
inittbl()435 void inittbl()
436 {
437 register int i;
438
439 zero_out( (char *) chk, (size_t) (current_max_xpairs * sizeof( int )) );
440
441 tblend = 0;
442 firstfree = tblend + 1;
443 numtemps = 0;
444
445 if ( usemecs )
446 {
447 /* Set up doubly-linked meta-equivalence classes; these
448 * are sets of equivalence classes which all have identical
449 * transitions out of TEMPLATES.
450 */
451
452 tecbck[1] = NIL;
453
454 for ( i = 2; i <= numecs; ++i )
455 {
456 tecbck[i] = i - 1;
457 tecfwd[i - 1] = i;
458 }
459
460 tecfwd[numecs] = NIL;
461 }
462 }
463
464
465 /* mkdeftbl - make the default, "jam" table entries */
466
mkdeftbl()467 void mkdeftbl()
468 {
469 int i;
470
471 jamstate = lastdfa + 1;
472
473 ++tblend; /* room for transition on end-of-buffer character */
474
475 while ( tblend + numecs >= current_max_xpairs )
476 expand_nxt_chk();
477
478 /* Add in default end-of-buffer transition. */
479 nxt[tblend] = end_of_buffer_state;
480 chk[tblend] = jamstate;
481
482 for ( i = 1; i <= numecs; ++i )
483 {
484 nxt[tblend + i] = 0;
485 chk[tblend + i] = jamstate;
486 }
487
488 jambase = tblend;
489
490 base[jamstate] = jambase;
491 def[jamstate] = 0;
492
493 tblend += numecs;
494 ++numtemps;
495 }
496
497
498 /* mkentry - create base/def and nxt/chk entries for transition array
499 *
500 * synopsis
501 * int state[numchars + 1], numchars, statenum, deflink, totaltrans;
502 * mkentry( state, numchars, statenum, deflink, totaltrans );
503 *
504 * "state" is a transition array "numchars" characters in size, "statenum"
505 * is the offset to be used into the base/def tables, and "deflink" is the
506 * entry to put in the "def" table entry. If "deflink" is equal to
507 * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
508 * (i.e., jam entries) into the table. It is assumed that by linking to
509 * "JAMSTATE" they will be taken care of. In any case, entries in "state"
510 * marking transitions to "SAME_TRANS" are treated as though they will be
511 * taken care of by whereever "deflink" points. "totaltrans" is the total
512 * number of transitions out of the state. If it is below a certain threshold,
513 * the tables are searched for an interior spot that will accommodate the
514 * state array.
515 */
516
mkentry(state,numchars,statenum,deflink,totaltrans)517 void mkentry( state, numchars, statenum, deflink, totaltrans )
518 register int *state;
519 int numchars, statenum, deflink, totaltrans;
520 {
521 register int minec, maxec, i, baseaddr;
522 int tblbase, tbllast;
523
524 if ( totaltrans == 0 )
525 { /* there are no out-transitions */
526 if ( deflink == JAMSTATE )
527 base[statenum] = JAMSTATE;
528 else
529 base[statenum] = 0;
530
531 def[statenum] = deflink;
532 return;
533 }
534
535 for ( minec = 1; minec <= numchars; ++minec )
536 {
537 if ( state[minec] != SAME_TRANS )
538 if ( state[minec] != 0 || deflink != JAMSTATE )
539 break;
540 }
541
542 if ( totaltrans == 1 )
543 {
544 /* There's only one out-transition. Save it for later to fill
545 * in holes in the tables.
546 */
547 stack1( statenum, minec, state[minec], deflink );
548 return;
549 }
550
551 for ( maxec = numchars; maxec > 0; --maxec )
552 {
553 if ( state[maxec] != SAME_TRANS )
554 if ( state[maxec] != 0 || deflink != JAMSTATE )
555 break;
556 }
557
558 /* Whether we try to fit the state table in the middle of the table
559 * entries we have already generated, or if we just take the state
560 * table at the end of the nxt/chk tables, we must make sure that we
561 * have a valid base address (i.e., non-negative). Note that
562 * negative base addresses dangerous at run-time (because indexing
563 * the nxt array with one and a low-valued character will access
564 * memory before the start of the array.
565 */
566
567 /* Find the first transition of state that we need to worry about. */
568 if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
569 {
570 /* Attempt to squeeze it into the middle of the tables. */
571 baseaddr = firstfree;
572
573 while ( baseaddr < minec )
574 {
575 /* Using baseaddr would result in a negative base
576 * address below; find the next free slot.
577 */
578 for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
579 ;
580 }
581
582 while ( baseaddr + maxec - minec + 1 >= current_max_xpairs )
583 expand_nxt_chk();
584
585 for ( i = minec; i <= maxec; ++i )
586 if ( state[i] != SAME_TRANS &&
587 (state[i] != 0 || deflink != JAMSTATE) &&
588 chk[baseaddr + i - minec] != 0 )
589 { /* baseaddr unsuitable - find another */
590 for ( ++baseaddr;
591 baseaddr < current_max_xpairs &&
592 chk[baseaddr] != 0; ++baseaddr )
593 ;
594
595 while ( baseaddr + maxec - minec + 1 >=
596 current_max_xpairs )
597 expand_nxt_chk();
598
599 /* Reset the loop counter so we'll start all
600 * over again next time it's incremented.
601 */
602
603 i = minec - 1;
604 }
605 }
606
607 else
608 {
609 /* Ensure that the base address we eventually generate is
610 * non-negative.
611 */
612 baseaddr = MAX( tblend + 1, minec );
613 }
614
615 tblbase = baseaddr - minec;
616 tbllast = tblbase + maxec;
617
618 while ( tbllast + 1 >= current_max_xpairs )
619 expand_nxt_chk();
620
621 base[statenum] = tblbase;
622 def[statenum] = deflink;
623
624 for ( i = minec; i <= maxec; ++i )
625 if ( state[i] != SAME_TRANS )
626 if ( state[i] != 0 || deflink != JAMSTATE )
627 {
628 nxt[tblbase + i] = state[i];
629 chk[tblbase + i] = statenum;
630 }
631
632 if ( baseaddr == firstfree )
633 /* Find next free slot in tables. */
634 for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
635 ;
636
637 tblend = MAX( tblend, tbllast );
638 }
639
640
641 /* mk1tbl - create table entries for a state (or state fragment) which
642 * has only one out-transition
643 */
644
mk1tbl(state,sym,onenxt,onedef)645 void mk1tbl( state, sym, onenxt, onedef )
646 int state, sym, onenxt, onedef;
647 {
648 if ( firstfree < sym )
649 firstfree = sym;
650
651 while ( chk[firstfree] != 0 )
652 if ( ++firstfree >= current_max_xpairs )
653 expand_nxt_chk();
654
655 base[state] = firstfree - sym;
656 def[state] = onedef;
657 chk[firstfree] = state;
658 nxt[firstfree] = onenxt;
659
660 if ( firstfree > tblend )
661 {
662 tblend = firstfree++;
663
664 if ( firstfree >= current_max_xpairs )
665 expand_nxt_chk();
666 }
667 }
668
669
670 /* mkprot - create new proto entry */
671
mkprot(state,statenum,comstate)672 void mkprot( state, statenum, comstate )
673 int state[], statenum, comstate;
674 {
675 int i, slot, tblbase;
676
677 if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
678 {
679 /* Gotta make room for the new proto by dropping last entry in
680 * the queue.
681 */
682 slot = lastprot;
683 lastprot = protprev[lastprot];
684 protnext[lastprot] = NIL;
685 }
686
687 else
688 slot = numprots;
689
690 protnext[slot] = firstprot;
691
692 if ( firstprot != NIL )
693 protprev[firstprot] = slot;
694
695 firstprot = slot;
696 prottbl[slot] = statenum;
697 protcomst[slot] = comstate;
698
699 /* Copy state into save area so it can be compared with rapidly. */
700 tblbase = numecs * (slot - 1);
701
702 for ( i = 1; i <= numecs; ++i )
703 protsave[tblbase + i] = state[i];
704 }
705
706
707 /* mktemplate - create a template entry based on a state, and connect the state
708 * to it
709 */
710
mktemplate(state,statenum,comstate)711 void mktemplate( state, statenum, comstate )
712 int state[], statenum, comstate;
713 {
714 int i, numdiff, tmpbase, tmp[CSIZE + 1];
715 Char transset[CSIZE + 1];
716 int tsptr;
717
718 ++numtemps;
719
720 tsptr = 0;
721
722 /* Calculate where we will temporarily store the transition table
723 * of the template in the tnxt[] array. The final transition table
724 * gets created by cmptmps().
725 */
726
727 tmpbase = numtemps * numecs;
728
729 if ( tmpbase + numecs >= current_max_template_xpairs )
730 {
731 current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
732
733 ++num_reallocs;
734
735 tnxt = reallocate_integer_array( tnxt,
736 current_max_template_xpairs );
737 }
738
739 for ( i = 1; i <= numecs; ++i )
740 if ( state[i] == 0 )
741 tnxt[tmpbase + i] = 0;
742 else
743 {
744 transset[tsptr++] = i;
745 tnxt[tmpbase + i] = comstate;
746 }
747
748 if ( usemecs )
749 mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );
750
751 mkprot( tnxt + tmpbase, -numtemps, comstate );
752
753 /* We rely on the fact that mkprot adds things to the beginning
754 * of the proto queue.
755 */
756
757 numdiff = tbldiff( state, firstprot, tmp );
758 mkentry( tmp, numecs, statenum, -numtemps, numdiff );
759 }
760
761
762 /* mv2front - move proto queue element to front of queue */
763
mv2front(qelm)764 void mv2front( qelm )
765 int qelm;
766 {
767 if ( firstprot != qelm )
768 {
769 if ( qelm == lastprot )
770 lastprot = protprev[lastprot];
771
772 protnext[protprev[qelm]] = protnext[qelm];
773
774 if ( protnext[qelm] != NIL )
775 protprev[protnext[qelm]] = protprev[qelm];
776
777 protprev[qelm] = NIL;
778 protnext[qelm] = firstprot;
779 protprev[firstprot] = qelm;
780 firstprot = qelm;
781 }
782 }
783
784
785 /* place_state - place a state into full speed transition table
786 *
787 * State is the statenum'th state. It is indexed by equivalence class and
788 * gives the number of the state to enter for a given equivalence class.
789 * Transnum is the number of out-transitions for the state.
790 */
791
place_state(state,statenum,transnum)792 void place_state( state, statenum, transnum )
793 int *state, statenum, transnum;
794 {
795 register int i;
796 register int *state_ptr;
797 int position = find_table_space( state, transnum );
798
799 /* "base" is the table of start positions. */
800 base[statenum] = position;
801
802 /* Put in action number marker; this non-zero number makes sure that
803 * find_table_space() knows that this position in chk/nxt is taken
804 * and should not be used for another accepting number in another
805 * state.
806 */
807 chk[position - 1] = 1;
808
809 /* Put in end-of-buffer marker; this is for the same purposes as
810 * above.
811 */
812 chk[position] = 1;
813
814 /* Place the state into chk and nxt. */
815 state_ptr = &state[1];
816
817 for ( i = 1; i <= numecs; ++i, ++state_ptr )
818 if ( *state_ptr != 0 )
819 {
820 chk[position + i] = i;
821 nxt[position + i] = *state_ptr;
822 }
823
824 if ( position + numecs > tblend )
825 tblend = position + numecs;
826 }
827
828
829 /* stack1 - save states with only one out-transition to be processed later
830 *
831 * If there's room for another state on the "one-transition" stack, the
832 * state is pushed onto it, to be processed later by mk1tbl. If there's
833 * no room, we process the sucker right now.
834 */
835
stack1(statenum,sym,nextstate,deflink)836 void stack1( statenum, sym, nextstate, deflink )
837 int statenum, sym, nextstate, deflink;
838 {
839 if ( onesp >= ONE_STACK_SIZE - 1 )
840 mk1tbl( statenum, sym, nextstate, deflink );
841
842 else
843 {
844 ++onesp;
845 onestate[onesp] = statenum;
846 onesym[onesp] = sym;
847 onenext[onesp] = nextstate;
848 onedef[onesp] = deflink;
849 }
850 }
851
852
853 /* tbldiff - compute differences between two state tables
854 *
855 * "state" is the state array which is to be extracted from the pr'th
856 * proto. "pr" is both the number of the proto we are extracting from
857 * and an index into the save area where we can find the proto's complete
858 * state table. Each entry in "state" which differs from the corresponding
859 * entry of "pr" will appear in "ext".
860 *
861 * Entries which are the same in both "state" and "pr" will be marked
862 * as transitions to "SAME_TRANS" in "ext". The total number of differences
863 * between "state" and "pr" is returned as function value. Note that this
864 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
865 */
866
tbldiff(state,pr,ext)867 int tbldiff( state, pr, ext )
868 int state[], pr, ext[];
869 {
870 register int i, *sp = state, *ep = ext, *protp;
871 register int numdiff = 0;
872
873 protp = &protsave[numecs * (pr - 1)];
874
875 for ( i = numecs; i > 0; --i )
876 {
877 if ( *++protp == *++sp )
878 *++ep = SAME_TRANS;
879 else
880 {
881 *++ep = *sp;
882 ++numdiff;
883 }
884 }
885
886 return numdiff;
887 }
888