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