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.11 94/11/05 17:08:28 vern Exp $ */ 30#include <sys/cdefs.h> 31__FBSDID("$FreeBSD$"); 32 33#include "flexdef.h" 34 35 36/* declarations for functions that have forward references */ 37 38void mkentry PROTO((int*, int, int, int, int)); 39void mkprot PROTO((int[], int, int)); 40void mktemplate PROTO((int[], int, int)); 41void mv2front PROTO((int)); 42int tbldiff PROTO((int[], int, int[])); 43 44 45/* bldtbl - build table entries for dfa state 46 * 47 * synopsis 48 * int state[numecs], statenum, totaltrans, comstate, comfreq; 49 * bldtbl( state, statenum, totaltrans, comstate, comfreq ); 50 * 51 * State is the statenum'th dfa state. It is indexed by equivalence class and 52 * gives the number of the state to enter for a given equivalence class. 53 * totaltrans is the total number of transitions out of the state. Comstate 54 * is that state which is the destination of the most transitions out of State. 55 * Comfreq is how many transitions there are out of State to Comstate. 56 * 57 * A note on terminology: 58 * "protos" are transition tables which have a high probability of 59 * either being redundant (a state processed later will have an identical 60 * transition table) or nearly redundant (a state processed later will have 61 * many of the same out-transitions). A "most recently used" queue of 62 * protos is kept around with the hope that most states will find a proto 63 * which is similar enough to be usable, and therefore compacting the 64 * output tables. 65 * "templates" are a special type of proto. If a transition table is 66 * homogeneous or nearly homogeneous (all transitions go to the same 67 * destination) then the odds are good that future states will also go 68 * to the same destination state on basically the same character set. 69 * These homogeneous states are so common when dealing with large rule 70 * sets that they merit special attention. If the transition table were 71 * simply made into a proto, then (typically) each subsequent, similar 72 * state will differ from the proto for two out-transitions. One of these 73 * out-transitions will be that character on which the proto does not go 74 * to the common destination, and one will be that character on which the 75 * state does not go to the common destination. Templates, on the other 76 * hand, go to the common state on EVERY transition character, and therefore 77 * cost only one difference. 78 */ 79 80void bldtbl( state, statenum, totaltrans, comstate, comfreq ) 81int state[], statenum, totaltrans, comstate, comfreq; 82 { 83 int extptr, extrct[2][CSIZE + 1]; 84 int mindiff, minprot, i, d; 85 86 /* If extptr is 0 then the first array of extrct holds the result 87 * of the "best difference" to date, which is those transitions 88 * which occur in "state" but not in the proto which, to date, 89 * has the fewest differences between itself and "state". If 90 * extptr is 1 then the second array of extrct hold the best 91 * difference. The two arrays are toggled between so that the 92 * best difference to date can be kept around and also a difference 93 * just created by checking against a candidate "best" proto. 94 */ 95 96 extptr = 0; 97 98 /* If the state has too few out-transitions, don't bother trying to 99 * compact its tables. 100 */ 101 102 if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) ) 103 mkentry( state, numecs, statenum, JAMSTATE, totaltrans ); 104 105 else 106 { 107 /* "checkcom" is true if we should only check "state" against 108 * protos which have the same "comstate" value. 109 */ 110 int checkcom = 111 comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE; 112 113 minprot = firstprot; 114 mindiff = totaltrans; 115 116 if ( checkcom ) 117 { 118 /* Find first proto which has the same "comstate". */ 119 for ( i = firstprot; i != NIL; i = protnext[i] ) 120 if ( protcomst[i] == comstate ) 121 { 122 minprot = i; 123 mindiff = tbldiff( state, minprot, 124 extrct[extptr] ); 125 break; 126 } 127 } 128 129 else 130 { 131 /* Since we've decided that the most common destination 132 * out of "state" does not occur with a high enough 133 * frequency, we set the "comstate" to zero, assuring 134 * that if this state is entered into the proto list, 135 * it will not be considered a template. 136 */ 137 comstate = 0; 138 139 if ( firstprot != NIL ) 140 { 141 minprot = firstprot; 142 mindiff = tbldiff( state, minprot, 143 extrct[extptr] ); 144 } 145 } 146 147 /* We now have the first interesting proto in "minprot". If 148 * it matches within the tolerances set for the first proto, 149 * we don't want to bother scanning the rest of the proto list 150 * to see if we have any other reasonable matches. 151 */ 152 153 if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE ) 154 { 155 /* Not a good enough match. Scan the rest of the 156 * protos. 157 */ 158 for ( i = minprot; i != NIL; i = protnext[i] ) 159 { 160 d = tbldiff( state, i, extrct[1 - extptr] ); 161 if ( d < mindiff ) 162 { 163 extptr = 1 - extptr; 164 mindiff = d; 165 minprot = i; 166 } 167 } 168 } 169 170 /* Check if the proto we've decided on as our best bet is close 171 * enough to the state we want to match to be usable. 172 */ 173 174 if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE ) 175 { 176 /* No good. If the state is homogeneous enough, 177 * we make a template out of it. Otherwise, we 178 * make a proto. 179 */ 180 181 if ( comfreq * 100 >= 182 totaltrans * TEMPLATE_SAME_PERCENTAGE ) 183 mktemplate( state, statenum, comstate ); 184 185 else 186 { 187 mkprot( state, statenum, comstate ); 188 mkentry( state, numecs, statenum, 189 JAMSTATE, totaltrans ); 190 } 191 } 192 193 else 194 { /* use the proto */ 195 mkentry( extrct[extptr], numecs, statenum, 196 prottbl[minprot], mindiff ); 197 198 /* If this state was sufficiently different from the 199 * proto we built it from, make it, too, a proto. 200 */ 201 202 if ( mindiff * 100 >= 203 totaltrans * NEW_PROTO_DIFF_PERCENTAGE ) 204 mkprot( state, statenum, comstate ); 205 206 /* Since mkprot added a new proto to the proto queue, 207 * it's possible that "minprot" is no longer on the 208 * proto queue (if it happened to have been the last 209 * entry, it would have been bumped off). If it's 210 * not there, then the new proto took its physical 211 * place (though logically the new proto is at the 212 * beginning of the queue), so in that case the 213 * following call will do nothing. 214 */ 215 216 mv2front( minprot ); 217 } 218 } 219 } 220 221 222/* cmptmps - compress template table entries 223 * 224 * Template tables are compressed by using the 'template equivalence 225 * classes', which are collections of transition character equivalence 226 * classes which always appear together in templates - really meta-equivalence 227 * classes. 228 */ 229 230void cmptmps() 231 { 232 int tmpstorage[CSIZE + 1]; 233 int *tmp = tmpstorage, i, j; 234 int totaltrans, trans; 235 236 peakpairs = numtemps * numecs + tblend; 237 238 if ( usemecs ) 239 { 240 /* Create equivalence classes based on data gathered on 241 * template transitions. 242 */ 243 nummecs = cre8ecs( tecfwd, tecbck, numecs ); 244 } 245 246 else 247 nummecs = numecs; 248 249 while ( lastdfa + numtemps + 1 >= current_max_dfas ) 250 increase_max_dfas(); 251 252 /* Loop through each template. */ 253 254 for ( i = 1; i <= numtemps; ++i ) 255 { 256 /* Number of non-jam transitions out of this template. */ 257 totaltrans = 0; 258 259 for ( j = 1; j <= numecs; ++j ) 260 { 261 trans = tnxt[numecs * i + j]; 262 263 if ( usemecs ) 264 { 265 /* The absolute value of tecbck is the 266 * meta-equivalence class of a given 267 * equivalence class, as set up by cre8ecs(). 268 */ 269 if ( tecbck[j] > 0 ) 270 { 271 tmp[tecbck[j]] = trans; 272 273 if ( trans > 0 ) 274 ++totaltrans; 275 } 276 } 277 278 else 279 { 280 tmp[j] = trans; 281 282 if ( trans > 0 ) 283 ++totaltrans; 284 } 285 } 286 287 /* It is assumed (in a rather subtle way) in the skeleton 288 * that if we're using meta-equivalence classes, the def[] 289 * entry for all templates is the jam template, i.e., 290 * templates never default to other non-jam table entries 291 * (e.g., another template) 292 */ 293 294 /* Leave room for the jam-state after the last real state. */ 295 mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans ); 296 } 297 } 298 299 300 301/* expand_nxt_chk - expand the next check arrays */ 302 303void expand_nxt_chk() 304 { 305 int old_max = current_max_xpairs; 306 307 current_max_xpairs += MAX_XPAIRS_INCREMENT; 308 309 ++num_reallocs; 310 311 nxt = reallocate_integer_array( nxt, current_max_xpairs ); 312 chk = reallocate_integer_array( chk, current_max_xpairs ); 313 314 zero_out( (char *) (chk + old_max), 315 (size_t) (MAX_XPAIRS_INCREMENT * sizeof( int )) ); 316 } 317 318 319/* find_table_space - finds a space in the table for a state to be placed 320 * 321 * synopsis 322 * int *state, numtrans, block_start; 323 * int find_table_space(); 324 * 325 * block_start = find_table_space( state, numtrans ); 326 * 327 * State is the state to be added to the full speed transition table. 328 * Numtrans is the number of out-transitions for the state. 329 * 330 * find_table_space() returns the position of the start of the first block (in 331 * chk) able to accommodate the state 332 * 333 * In determining if a state will or will not fit, find_table_space() must take 334 * into account the fact that an end-of-buffer state will be added at [0], 335 * and an action number will be added in [-1]. 336 */ 337 338int find_table_space( state, numtrans ) 339int *state, numtrans; 340 { 341 /* Firstfree is the position of the first possible occurrence of two 342 * consecutive unused records in the chk and nxt arrays. 343 */ 344 int i; 345 int *state_ptr, *chk_ptr; 346 int *ptr_to_last_entry_in_state; 347 348 /* If there are too many out-transitions, put the state at the end of 349 * nxt and chk. 350 */ 351 if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT ) 352 { 353 /* If table is empty, return the first available spot in 354 * chk/nxt, which should be 1. 355 */ 356 if ( tblend < 2 ) 357 return 1; 358 359 /* Start searching for table space near the end of 360 * chk/nxt arrays. 361 */ 362 i = tblend - numecs; 363 } 364 365 else 366 /* Start searching for table space from the beginning 367 * (skipping only the elements which will definitely not 368 * hold the new state). 369 */ 370 i = firstfree; 371 372 while ( 1 ) /* loops until a space is found */ 373 { 374 while ( i + numecs >= current_max_xpairs ) 375 expand_nxt_chk(); 376 377 /* Loops until space for end-of-buffer and action number 378 * are found. 379 */ 380 while ( 1 ) 381 { 382 /* Check for action number space. */ 383 if ( chk[i - 1] == 0 ) 384 { 385 /* Check for end-of-buffer space. */ 386 if ( chk[i] == 0 ) 387 break; 388 389 else 390 /* Since i != 0, there is no use 391 * checking to see if (++i) - 1 == 0, 392 * because that's the same as i == 0, 393 * so we skip a space. 394 */ 395 i += 2; 396 } 397 398 else 399 ++i; 400 401 while ( i + numecs >= current_max_xpairs ) 402 expand_nxt_chk(); 403 } 404 405 /* If we started search from the beginning, store the new 406 * firstfree for the next call of find_table_space(). 407 */ 408 if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT ) 409 firstfree = i + 1; 410 411 /* Check to see if all elements in chk (and therefore nxt) 412 * that are needed for the new state have not yet been taken. 413 */ 414 415 state_ptr = &state[1]; 416 ptr_to_last_entry_in_state = &chk[i + numecs + 1]; 417 418 for ( chk_ptr = &chk[i + 1]; 419 chk_ptr != ptr_to_last_entry_in_state; ++chk_ptr ) 420 if ( *(state_ptr++) != 0 && *chk_ptr != 0 ) 421 break; 422 423 if ( chk_ptr == ptr_to_last_entry_in_state ) 424 return i; 425 426 else 427 ++i; 428 } 429 } 430 431 432/* inittbl - initialize transition tables 433 * 434 * Initializes "firstfree" to be one beyond the end of the table. Initializes 435 * all "chk" entries to be zero. 436 */ 437void inittbl() 438 { 439 int i; 440 441 zero_out( (char *) chk, (size_t) (current_max_xpairs * sizeof( int )) ); 442 443 tblend = 0; 444 firstfree = tblend + 1; 445 numtemps = 0; 446 447 if ( usemecs ) 448 { 449 /* Set up doubly-linked meta-equivalence classes; these 450 * are sets of equivalence classes which all have identical 451 * transitions out of TEMPLATES. 452 */ 453 454 tecbck[1] = NIL; 455 456 for ( i = 2; i <= numecs; ++i ) 457 { 458 tecbck[i] = i - 1; 459 tecfwd[i - 1] = i; 460 } 461 462 tecfwd[numecs] = NIL; 463 } 464 } 465 466 467/* mkdeftbl - make the default, "jam" table entries */ 468 469void mkdeftbl() 470 { 471 int i; 472 473 jamstate = lastdfa + 1; 474 475 ++tblend; /* room for transition on end-of-buffer character */ 476 477 while ( tblend + numecs >= current_max_xpairs ) 478 expand_nxt_chk(); 479 480 /* Add in default end-of-buffer transition. */ 481 nxt[tblend] = end_of_buffer_state; 482 chk[tblend] = jamstate; 483 484 for ( i = 1; i <= numecs; ++i ) 485 { 486 nxt[tblend + i] = 0; 487 chk[tblend + i] = jamstate; 488 } 489 490 jambase = tblend; 491 492 base[jamstate] = jambase; 493 def[jamstate] = 0; 494 495 tblend += numecs; 496 ++numtemps; 497 } 498 499 500/* mkentry - create base/def and nxt/chk entries for transition array 501 * 502 * synopsis 503 * int state[numchars + 1], numchars, statenum, deflink, totaltrans; 504 * mkentry( state, numchars, statenum, deflink, totaltrans ); 505 * 506 * "state" is a transition array "numchars" characters in size, "statenum" 507 * is the offset to be used into the base/def tables, and "deflink" is the 508 * entry to put in the "def" table entry. If "deflink" is equal to 509 * "JAMSTATE", then no attempt will be made to fit zero entries of "state" 510 * (i.e., jam entries) into the table. It is assumed that by linking to 511 * "JAMSTATE" they will be taken care of. In any case, entries in "state" 512 * marking transitions to "SAME_TRANS" are treated as though they will be 513 * taken care of by whereever "deflink" points. "totaltrans" is the total 514 * number of transitions out of the state. If it is below a certain threshold, 515 * the tables are searched for an interior spot that will accommodate the 516 * state array. 517 */ 518 519void mkentry( state, numchars, statenum, deflink, totaltrans ) 520int *state; 521int numchars, statenum, deflink, totaltrans; 522 { 523 int minec, maxec, i, baseaddr; 524 int tblbase, tbllast; 525 526 if ( totaltrans == 0 ) 527 { /* there are no out-transitions */ 528 if ( deflink == JAMSTATE ) 529 base[statenum] = JAMSTATE; 530 else 531 base[statenum] = 0; 532 533 def[statenum] = deflink; 534 return; 535 } 536 537 for ( minec = 1; minec <= numchars; ++minec ) 538 { 539 if ( state[minec] != SAME_TRANS ) 540 if ( state[minec] != 0 || deflink != JAMSTATE ) 541 break; 542 } 543 544 if ( totaltrans == 1 ) 545 { 546 /* There's only one out-transition. Save it for later to fill 547 * in holes in the tables. 548 */ 549 stack1( statenum, minec, state[minec], deflink ); 550 return; 551 } 552 553 for ( maxec = numchars; maxec > 0; --maxec ) 554 { 555 if ( state[maxec] != SAME_TRANS ) 556 if ( state[maxec] != 0 || deflink != JAMSTATE ) 557 break; 558 } 559 560 /* Whether we try to fit the state table in the middle of the table 561 * entries we have already generated, or if we just take the state 562 * table at the end of the nxt/chk tables, we must make sure that we 563 * have a valid base address (i.e., non-negative). Note that 564 * negative base addresses dangerous at run-time (because indexing 565 * the nxt array with one and a low-valued character will access 566 * memory before the start of the array. 567 */ 568 569 /* Find the first transition of state that we need to worry about. */ 570 if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE ) 571 { 572 /* Attempt to squeeze it into the middle of the tables. */ 573 baseaddr = firstfree; 574 575 while ( baseaddr < minec ) 576 { 577 /* Using baseaddr would result in a negative base 578 * address below; find the next free slot. 579 */ 580 for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr ) 581 ; 582 } 583 584 while ( baseaddr + maxec - minec + 1 >= current_max_xpairs ) 585 expand_nxt_chk(); 586 587 for ( i = minec; i <= maxec; ++i ) 588 if ( state[i] != SAME_TRANS && 589 (state[i] != 0 || deflink != JAMSTATE) && 590 chk[baseaddr + i - minec] != 0 ) 591 { /* baseaddr unsuitable - find another */ 592 for ( ++baseaddr; 593 baseaddr < current_max_xpairs && 594 chk[baseaddr] != 0; ++baseaddr ) 595 ; 596 597 while ( baseaddr + maxec - minec + 1 >= 598 current_max_xpairs ) 599 expand_nxt_chk(); 600 601 /* Reset the loop counter so we'll start all 602 * over again next time it's incremented. 603 */ 604 605 i = minec - 1; 606 } 607 } 608 609 else 610 { 611 /* Ensure that the base address we eventually generate is 612 * non-negative. 613 */ 614 baseaddr = MAX( tblend + 1, minec ); 615 } 616 617 tblbase = baseaddr - minec; 618 tbllast = tblbase + maxec; 619 620 while ( tbllast + 1 >= current_max_xpairs ) 621 expand_nxt_chk(); 622 623 base[statenum] = tblbase; 624 def[statenum] = deflink; 625 626 for ( i = minec; i <= maxec; ++i ) 627 if ( state[i] != SAME_TRANS ) 628 if ( state[i] != 0 || deflink != JAMSTATE ) 629 { 630 nxt[tblbase + i] = state[i]; 631 chk[tblbase + i] = statenum; 632 } 633 634 if ( baseaddr == firstfree ) 635 /* Find next free slot in tables. */ 636 for ( ++firstfree; chk[firstfree] != 0; ++firstfree ) 637 ; 638 639 tblend = MAX( tblend, tbllast ); 640 } 641 642 643/* mk1tbl - create table entries for a state (or state fragment) which 644 * has only one out-transition 645 */ 646 647void mk1tbl( state, sym, onenxt, onedef ) 648int state, sym, onenxt, onedef; 649 { 650 if ( firstfree < sym ) 651 firstfree = sym; 652 653 while ( chk[firstfree] != 0 ) 654 if ( ++firstfree >= current_max_xpairs ) 655 expand_nxt_chk(); 656 657 base[state] = firstfree - sym; 658 def[state] = onedef; 659 chk[firstfree] = state; 660 nxt[firstfree] = onenxt; 661 662 if ( firstfree > tblend ) 663 { 664 tblend = firstfree++; 665 666 if ( firstfree >= current_max_xpairs ) 667 expand_nxt_chk(); 668 } 669 } 670 671 672/* mkprot - create new proto entry */ 673 674void mkprot( state, statenum, comstate ) 675int state[], statenum, comstate; 676 { 677 int i, slot, tblbase; 678 679 if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE ) 680 { 681 /* Gotta make room for the new proto by dropping last entry in 682 * the queue. 683 */ 684 slot = lastprot; 685 lastprot = protprev[lastprot]; 686 protnext[lastprot] = NIL; 687 } 688 689 else 690 slot = numprots; 691 692 protnext[slot] = firstprot; 693 694 if ( firstprot != NIL ) 695 protprev[firstprot] = slot; 696 697 firstprot = slot; 698 prottbl[slot] = statenum; 699 protcomst[slot] = comstate; 700 701 /* Copy state into save area so it can be compared with rapidly. */ 702 tblbase = numecs * (slot - 1); 703 704 for ( i = 1; i <= numecs; ++i ) 705 protsave[tblbase + i] = state[i]; 706 } 707 708 709/* mktemplate - create a template entry based on a state, and connect the state 710 * to it 711 */ 712 713void mktemplate( state, statenum, comstate ) 714int state[], statenum, comstate; 715 { 716 int i, numdiff, tmpbase, tmp[CSIZE + 1]; 717 Char transset[CSIZE + 1]; 718 int tsptr; 719 720 ++numtemps; 721 722 tsptr = 0; 723 724 /* Calculate where we will temporarily store the transition table 725 * of the template in the tnxt[] array. The final transition table 726 * gets created by cmptmps(). 727 */ 728 729 tmpbase = numtemps * numecs; 730 731 if ( tmpbase + numecs >= current_max_template_xpairs ) 732 { 733 current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT; 734 735 ++num_reallocs; 736 737 tnxt = reallocate_integer_array( tnxt, 738 current_max_template_xpairs ); 739 } 740 741 for ( i = 1; i <= numecs; ++i ) 742 if ( state[i] == 0 ) 743 tnxt[tmpbase + i] = 0; 744 else 745 { 746 transset[tsptr++] = i; 747 tnxt[tmpbase + i] = comstate; 748 } 749 750 if ( usemecs ) 751 mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 ); 752 753 mkprot( tnxt + tmpbase, -numtemps, comstate ); 754 755 /* We rely on the fact that mkprot adds things to the beginning 756 * of the proto queue. 757 */ 758 759 numdiff = tbldiff( state, firstprot, tmp ); 760 mkentry( tmp, numecs, statenum, -numtemps, numdiff ); 761 } 762 763 764/* mv2front - move proto queue element to front of queue */ 765 766void mv2front( qelm ) 767int qelm; 768 { 769 if ( firstprot != qelm ) 770 { 771 if ( qelm == lastprot ) 772 lastprot = protprev[lastprot]; 773 774 protnext[protprev[qelm]] = protnext[qelm]; 775 776 if ( protnext[qelm] != NIL ) 777 protprev[protnext[qelm]] = protprev[qelm]; 778 779 protprev[qelm] = NIL; 780 protnext[qelm] = firstprot; 781 protprev[firstprot] = qelm; 782 firstprot = qelm; 783 } 784 } 785 786 787/* place_state - place a state into full speed transition table 788 * 789 * State is the statenum'th state. It is indexed by equivalence class and 790 * gives the number of the state to enter for a given equivalence class. 791 * Transnum is the number of out-transitions for the state. 792 */ 793 794void place_state( state, statenum, transnum ) 795int *state, statenum, transnum; 796 { 797 int i; 798 int *state_ptr; 799 int position = find_table_space( state, transnum ); 800 801 /* "base" is the table of start positions. */ 802 base[statenum] = position; 803 804 /* Put in action number marker; this non-zero number makes sure that 805 * find_table_space() knows that this position in chk/nxt is taken 806 * and should not be used for another accepting number in another 807 * state. 808 */ 809 chk[position - 1] = 1; 810 811 /* Put in end-of-buffer marker; this is for the same purposes as 812 * above. 813 */ 814 chk[position] = 1; 815 816 /* Place the state into chk and nxt. */ 817 state_ptr = &state[1]; 818 819 for ( i = 1; i <= numecs; ++i, ++state_ptr ) 820 if ( *state_ptr != 0 ) 821 { 822 chk[position + i] = i; 823 nxt[position + i] = *state_ptr; 824 } 825 826 if ( position + numecs > tblend ) 827 tblend = position + numecs; 828 } 829 830 831/* stack1 - save states with only one out-transition to be processed later 832 * 833 * If there's room for another state on the "one-transition" stack, the 834 * state is pushed onto it, to be processed later by mk1tbl. If there's 835 * no room, we process the sucker right now. 836 */ 837 838void stack1( statenum, sym, nextstate, deflink ) 839int statenum, sym, nextstate, deflink; 840 { 841 if ( onesp >= ONE_STACK_SIZE - 1 ) 842 mk1tbl( statenum, sym, nextstate, deflink ); 843 844 else 845 { 846 ++onesp; 847 onestate[onesp] = statenum; 848 onesym[onesp] = sym; 849 onenext[onesp] = nextstate; 850 onedef[onesp] = deflink; 851 } 852 } 853 854 855/* tbldiff - compute differences between two state tables 856 * 857 * "state" is the state array which is to be extracted from the pr'th 858 * proto. "pr" is both the number of the proto we are extracting from 859 * and an index into the save area where we can find the proto's complete 860 * state table. Each entry in "state" which differs from the corresponding 861 * entry of "pr" will appear in "ext". 862 * 863 * Entries which are the same in both "state" and "pr" will be marked 864 * as transitions to "SAME_TRANS" in "ext". The total number of differences 865 * between "state" and "pr" is returned as function value. Note that this 866 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". 867 */ 868 869int tbldiff( state, pr, ext ) 870int state[], pr, ext[]; 871 { 872 int i, *sp = state, *ep = ext, *protp; 873 int numdiff = 0; 874 875 protp = &protsave[numecs * (pr - 1)]; 876 877 for ( i = numecs; i > 0; --i ) 878 { 879 if ( *++protp == *++sp ) 880 *++ep = SAME_TRANS; 881 else 882 { 883 *++ep = *sp; 884 ++numdiff; 885 } 886 } 887 888 return numdiff; 889 } 890