1 /* $OpenBSD: tblcmp.c,v 1.12 2024/11/09 18:03:44 op Exp $ */ 2 3 /* tblcmp - table compression routines */ 4 5 /* Copyright (c) 1990 The Regents of the University of California. */ 6 /* All rights reserved. */ 7 8 /* This code is derived from software contributed to Berkeley by */ 9 /* Vern Paxson. */ 10 11 /* The United States Government has rights in this work pursuant */ 12 /* to contract no. DE-AC03-76SF00098 between the United States */ 13 /* Department of Energy and the University of California. */ 14 15 /* This file is part of flex. */ 16 17 /* Redistribution and use in source and binary forms, with or without */ 18 /* modification, are permitted provided that the following conditions */ 19 /* are met: */ 20 21 /* 1. Redistributions of source code must retain the above copyright */ 22 /* notice, this list of conditions and the following disclaimer. */ 23 /* 2. Redistributions in binary form must reproduce the above copyright */ 24 /* notice, this list of conditions and the following disclaimer in the */ 25 /* documentation and/or other materials provided with the distribution. */ 26 27 /* Neither the name of the University nor the names of its contributors */ 28 /* may be used to endorse or promote products derived from this software */ 29 /* without specific prior written permission. */ 30 31 /* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 32 /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 33 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 34 /* PURPOSE. */ 35 36 #include "flexdef.h" 37 38 39 /* declarations for functions that have forward references */ 40 41 void mkentry PROTO((int *, int, int, int, int)); 42 void mkprot PROTO((int[], int, int)); 43 void mktemplate PROTO((int[], int, int)); 44 void mv2front PROTO((int)); 45 int tbldiff PROTO((int[], int, int[])); 46 47 48 /* bldtbl - build table entries for dfa state 49 * 50 * synopsis 51 * int state[numecs], statenum, totaltrans, comstate, comfreq; 52 * bldtbl( state, statenum, totaltrans, comstate, comfreq ); 53 * 54 * State is the statenum'th dfa state. It is indexed by equivalence class and 55 * gives the number of the state to enter for a given equivalence class. 56 * totaltrans is the total number of transitions out of the state. Comstate 57 * is that state which is the destination of the most transitions out of State. 58 * Comfreq is how many transitions there are out of State to Comstate. 59 * 60 * A note on terminology: 61 * "protos" are transition tables which have a high probability of 62 * either being redundant (a state processed later will have an identical 63 * transition table) or nearly redundant (a state processed later will have 64 * many of the same out-transitions). A "most recently used" queue of 65 * protos is kept around with the hope that most states will find a proto 66 * which is similar enough to be usable, and therefore compacting the 67 * output tables. 68 * "templates" are a special type of proto. If a transition table is 69 * homogeneous or nearly homogeneous (all transitions go to the same 70 * destination) then the odds are good that future states will also go 71 * to the same destination state on basically the same character set. 72 * These homogeneous states are so common when dealing with large rule 73 * sets that they merit special attention. If the transition table were 74 * simply made into a proto, then (typically) each subsequent, similar 75 * state will differ from the proto for two out-transitions. One of these 76 * out-transitions will be that character on which the proto does not go 77 * to the common destination, and one will be that character on which the 78 * state does not go to the common destination. Templates, on the other 79 * hand, go to the common state on EVERY transition character, and therefore 80 * cost only one difference. 81 */ 82 83 void 84 bldtbl(int state[], int statenum, int totaltrans, int comstate, int comfreq) 85 { 86 int extptr, extrct[2][CSIZE + 1]; 87 int mindiff, minprot, i, d; 88 89 /* 90 * If extptr is 0 then the first array of extrct holds the result of 91 * the "best difference" to date, which is those transitions which 92 * occur in "state" but not in the proto which, to date, has the 93 * fewest differences between itself and "state". If extptr is 1 94 * then the second array of extrct hold the best difference. The two 95 * arrays are toggled between so that the best difference to date can 96 * be kept around and also a difference just created by checking 97 * against a candidate "best" proto. 98 */ 99 100 extptr = 0; 101 102 /* 103 * If the state has too few out-transitions, don't bother trying to 104 * compact its tables. 105 */ 106 107 if ((totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE)) 108 mkentry(state, numecs, statenum, JAMSTATE, totaltrans); 109 110 else { 111 /* 112 * "checkcom" is true if we should only check "state" against 113 * protos which have the same "comstate" value. 114 */ 115 int checkcom = 116 117 comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE; 118 119 minprot = firstprot; 120 mindiff = totaltrans; 121 122 if (checkcom) { 123 /* Find first proto which has the same "comstate". */ 124 for (i = firstprot; i != NIL; i = protnext[i]) 125 if (protcomst[i] == comstate) { 126 minprot = i; 127 mindiff = tbldiff(state, minprot, 128 extrct[extptr]); 129 break; 130 } 131 } else { 132 /* 133 * Since we've decided that the most common 134 * destination out of "state" does not occur with a 135 * high enough frequency, we set the "comstate" to 136 * zero, assuring that if this state is entered into 137 * the proto list, it will not be considered a 138 * template. 139 */ 140 comstate = 0; 141 142 if (firstprot != NIL) { 143 minprot = firstprot; 144 mindiff = tbldiff(state, minprot, 145 extrct[extptr]); 146 } 147 } 148 149 /* 150 * We now have the first interesting proto in "minprot". If 151 * it matches within the tolerances set for the first proto, 152 * we don't want to bother scanning the rest of the proto 153 * list to see if we have any other reasonable matches. 154 */ 155 156 if (mindiff * 100 > 157 totaltrans * FIRST_MATCH_DIFF_PERCENTAGE) { 158 /* 159 * Not a good enough match. Scan the rest of the 160 * protos. 161 */ 162 for (i = minprot; i != NIL; i = protnext[i]) { 163 d = tbldiff(state, i, extrct[1 - extptr]); 164 if (d < mindiff) { 165 extptr = 1 - extptr; 166 mindiff = d; 167 minprot = i; 168 } 169 } 170 } 171 /* 172 * Check if the proto we've decided on as our best bet is 173 * close enough to the state we want to match to be usable. 174 */ 175 176 if (mindiff * 100 > 177 totaltrans * ACCEPTABLE_DIFF_PERCENTAGE) { 178 /* 179 * No good. If the state is homogeneous enough, we 180 * make a template out of it. Otherwise, we make a 181 * proto. 182 */ 183 184 if (comfreq * 100 >= 185 totaltrans * TEMPLATE_SAME_PERCENTAGE) 186 mktemplate(state, statenum, 187 comstate); 188 189 else { 190 mkprot(state, statenum, comstate); 191 mkentry(state, numecs, statenum, 192 JAMSTATE, totaltrans); 193 } 194 } else { /* use the proto */ 195 mkentry(extrct[extptr], numecs, statenum, 196 prottbl[minprot], mindiff); 197 198 /* 199 * If this state was sufficiently different from the 200 * proto we built it from, make it, too, a proto. 201 */ 202 203 if (mindiff * 100 >= 204 totaltrans * NEW_PROTO_DIFF_PERCENTAGE) 205 mkprot(state, statenum, comstate); 206 207 /* 208 * Since mkprot added a new proto to the proto queue, 209 * it's possible that "minprot" is no longer on the 210 * proto queue (if it happened to have been the last 211 * entry, it would have been bumped off). If it's 212 * not there, then the new proto took its physical 213 * place (though logically the new proto is at the 214 * beginning of the queue), so in that case the 215 * following call will do nothing. 216 */ 217 218 mv2front(minprot); 219 } 220 } 221 } 222 223 224 /* cmptmps - compress template table entries 225 * 226 * Template tables are compressed by using the 'template equivalence 227 * classes', which are collections of transition character equivalence 228 * classes which always appear together in templates - really meta-equivalence 229 * classes. 230 */ 231 232 void 233 cmptmps(void) 234 { 235 int tmpstorage[CSIZE + 1]; 236 int *tmp = tmpstorage, i, j; 237 int totaltrans, trans; 238 239 peakpairs = numtemps * numecs + tblend; 240 241 if (usemecs) { 242 /* 243 * Create equivalence classes based on data gathered on 244 * template transitions. 245 */ 246 nummecs = cre8ecs(tecfwd, tecbck, numecs); 247 } else 248 nummecs = numecs; 249 250 while (lastdfa + numtemps + 1 >= current_max_dfas) 251 increase_max_dfas(); 252 253 /* Loop through each template. */ 254 255 for (i = 1; i <= numtemps; ++i) { 256 /* Number of non-jam transitions out of this template. */ 257 totaltrans = 0; 258 259 for (j = 1; j <= numecs; ++j) { 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 tmp[tecbck[j]] = trans; 270 271 if (trans > 0) 272 ++totaltrans; 273 } 274 } else { 275 tmp[j] = trans; 276 277 if (trans > 0) 278 ++totaltrans; 279 } 280 } 281 282 /* 283 * It is assumed (in a rather subtle way) in the skeleton 284 * that if we're using meta-equivalence classes, the def[] 285 * entry for all templates is the jam template, i.e., 286 * templates never default to other non-jam table entries 287 * (e.g., another template) 288 */ 289 290 /* Leave room for the jam-state after the last real state. */ 291 mkentry(tmp, nummecs, lastdfa + i + 1, JAMSTATE, 292 totaltrans); 293 } 294 } 295 296 297 298 /* expand_nxt_chk - expand the next check arrays */ 299 300 void 301 expand_nxt_chk(void) 302 { 303 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 memset((chk + old_max), 0, MAX_XPAIRS_INCREMENT * sizeof(int)); 313 } 314 315 316 /* find_table_space - finds a space in the table for a state to be placed 317 * 318 * synopsis 319 * int *state, numtrans, block_start; 320 * int find_table_space(); 321 * 322 * block_start = find_table_space( state, numtrans ); 323 * 324 * State is the state to be added to the full speed transition table. 325 * Numtrans is the number of out-transitions for the state. 326 * 327 * find_table_space() returns the position of the start of the first block (in 328 * chk) able to accommodate the state 329 * 330 * In determining if a state will or will not fit, find_table_space() must take 331 * into account the fact that an end-of-buffer state will be added at [0], 332 * and an action number will be added in [-1]. 333 */ 334 335 int 336 find_table_space(int *state, int numtrans) 337 { 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 int i; 343 int *state_ptr, *chk_ptr; 344 int *ptr_to_last_entry_in_state; 345 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 /* 359 * Start searching for table space near the end of chk/nxt 360 * arrays. 361 */ 362 i = tblend - numecs; 363 } else 364 /* 365 * Start searching for table space from the beginning 366 * (skipping only the elements which will definitely not hold 367 * the new state). 368 */ 369 i = firstfree; 370 371 while (1) { /* loops until a space is found */ 372 while (i + numecs >= current_max_xpairs) 373 expand_nxt_chk(); 374 375 /* 376 * Loops until space for end-of-buffer and action number are 377 * found. 378 */ 379 while (1) { 380 /* Check for action number space. */ 381 if (chk[i - 1] == 0) { 382 /* Check for end-of-buffer space. */ 383 if (chk[i] == 0) 384 break; 385 386 else 387 /* 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 } else 395 ++i; 396 397 while (i + numecs >= current_max_xpairs) 398 expand_nxt_chk(); 399 } 400 401 /* 402 * If we started search from the beginning, store the new 403 * firstfree for the next call of find_table_space(). 404 */ 405 if (numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT) 406 firstfree = i + 1; 407 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 */ 435 void 436 inittbl(void) 437 { 438 int i; 439 440 memset(chk, 0, 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 are 449 * 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 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 467 void 468 mkdeftbl(void) 469 { 470 int i; 471 472 jamstate = lastdfa + 1; 473 474 ++tblend; /* room for transition on end-of-buffer 475 * 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 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 wherever "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 518 void 519 mkentry(int *state, int numchars, int statenum, int deflink, int totaltrans) 520 { 521 int minec, maxec, i, baseaddr; 522 int tblbase, tbllast; 523 524 if (totaltrans == 0) { /* there are no out-transitions */ 525 if (deflink == JAMSTATE) 526 base[statenum] = JAMSTATE; 527 else 528 base[statenum] = 0; 529 530 def[statenum] = deflink; 531 return; 532 } 533 for (minec = 1; minec <= numchars; ++minec) { 534 if (state[minec] != SAME_TRANS) 535 if (state[minec] != 0 || deflink != JAMSTATE) 536 break; 537 } 538 539 if (totaltrans == 1) { 540 /* 541 * There's only one out-transition. Save it for later to 542 * fill in holes in the tables. 543 */ 544 stack1(statenum, minec, state[minec], deflink); 545 return; 546 } 547 for (maxec = numchars; maxec > 0; --maxec) { 548 if (state[maxec] != SAME_TRANS) 549 if (state[maxec] != 0 || deflink != JAMSTATE) 550 break; 551 } 552 553 /* 554 * Whether we try to fit the state table in the middle of the table 555 * entries we have already generated, or if we just take the state 556 * table at the end of the nxt/chk tables, we must make sure that we 557 * have a valid base address (i.e., non-negative). Note that 558 * negative base addresses dangerous at run-time (because indexing 559 * the nxt array with one and a low-valued character will access 560 * memory before the start of the array. 561 */ 562 563 /* Find the first transition of state that we need to worry about. */ 564 if (totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE) { 565 /* Attempt to squeeze it into the middle of the tables. */ 566 baseaddr = firstfree; 567 568 while (baseaddr < minec) { 569 /* 570 * Using baseaddr would result in a negative base 571 * address below; find the next free slot. 572 */ 573 for (++baseaddr; chk[baseaddr] != 0; ++baseaddr); 574 } 575 576 while (baseaddr + maxec - minec + 1 >= current_max_xpairs) 577 expand_nxt_chk(); 578 579 for (i = minec; i <= maxec; ++i) 580 if (state[i] != SAME_TRANS && 581 (state[i] != 0 || deflink != JAMSTATE) && 582 chk[baseaddr + i - minec] != 0) { /* baseaddr unsuitable - 583 * find another */ 584 for (++baseaddr; 585 baseaddr < current_max_xpairs && 586 chk[baseaddr] != 0; ++baseaddr); 587 588 while (baseaddr + maxec - minec + 1 >= 589 current_max_xpairs) 590 expand_nxt_chk(); 591 592 /* 593 * Reset the loop counter so we'll start all 594 * over again next time it's incremented. 595 */ 596 597 i = minec - 1; 598 } 599 } else { 600 /* 601 * Ensure that the base address we eventually generate is 602 * non-negative. 603 */ 604 baseaddr = MAX(tblend + 1, minec); 605 } 606 607 tblbase = baseaddr - minec; 608 tbllast = tblbase + maxec; 609 610 while (tbllast + 1 >= current_max_xpairs) 611 expand_nxt_chk(); 612 613 base[statenum] = tblbase; 614 def[statenum] = deflink; 615 616 for (i = minec; i <= maxec; ++i) 617 if (state[i] != SAME_TRANS) 618 if (state[i] != 0 || deflink != JAMSTATE) { 619 nxt[tblbase + i] = state[i]; 620 chk[tblbase + i] = statenum; 621 } 622 if (baseaddr == firstfree) 623 /* Find next free slot in tables. */ 624 for (++firstfree; chk[firstfree] != 0; ++firstfree); 625 626 tblend = MAX(tblend, tbllast); 627 } 628 629 630 /* mk1tbl - create table entries for a state (or state fragment) which 631 * has only one out-transition 632 */ 633 634 void 635 mk1tbl(int state, int sym, int onenxt, int onedef) 636 { 637 if (firstfree < sym) 638 firstfree = sym; 639 640 while (chk[firstfree] != 0) 641 if (++firstfree >= current_max_xpairs) 642 expand_nxt_chk(); 643 644 base[state] = firstfree - sym; 645 def[state] = onedef; 646 chk[firstfree] = state; 647 nxt[firstfree] = onenxt; 648 649 if (firstfree > tblend) { 650 tblend = firstfree++; 651 652 if (firstfree >= current_max_xpairs) 653 expand_nxt_chk(); 654 } 655 } 656 657 658 /* mkprot - create new proto entry */ 659 660 void 661 mkprot(int state[], int statenum, int comstate) 662 { 663 int i, slot, tblbase; 664 665 if (++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE) { 666 /* 667 * Gotta make room for the new proto by dropping last entry 668 * in the queue. 669 */ 670 slot = lastprot; 671 lastprot = protprev[lastprot]; 672 protnext[lastprot] = NIL; 673 } else 674 slot = numprots; 675 676 protnext[slot] = firstprot; 677 678 if (firstprot != NIL) 679 protprev[firstprot] = slot; 680 681 firstprot = slot; 682 prottbl[slot] = statenum; 683 protcomst[slot] = comstate; 684 685 /* Copy state into save area so it can be compared with rapidly. */ 686 tblbase = numecs * (slot - 1); 687 688 for (i = 1; i <= numecs; ++i) 689 protsave[tblbase + i] = state[i]; 690 } 691 692 693 /* mktemplate - create a template entry based on a state, and connect the state 694 * to it 695 */ 696 697 void 698 mktemplate(int state[], int statenum, int comstate) 699 { 700 int i, numdiff, tmpbase, tmp[CSIZE + 1]; 701 u_char transset[CSIZE + 1]; 702 int tsptr; 703 704 ++numtemps; 705 706 tsptr = 0; 707 708 /* 709 * Calculate where we will temporarily store the transition table of 710 * the template in the tnxt[] array. The final transition table gets 711 * created by cmptmps(). 712 */ 713 714 tmpbase = numtemps * numecs; 715 716 if (tmpbase + numecs >= current_max_template_xpairs) { 717 current_max_template_xpairs += 718 MAX_TEMPLATE_XPAIRS_INCREMENT; 719 720 ++num_reallocs; 721 722 tnxt = reallocate_integer_array(tnxt, 723 current_max_template_xpairs); 724 } 725 for (i = 1; i <= numecs; ++i) 726 if (state[i] == 0) 727 tnxt[tmpbase + i] = 0; 728 else { 729 transset[tsptr++] = i; 730 tnxt[tmpbase + i] = comstate; 731 } 732 733 if (usemecs) 734 mkeccl(transset, tsptr, tecfwd, tecbck, numecs, 0); 735 736 mkprot(tnxt + tmpbase, -numtemps, comstate); 737 738 /* 739 * We rely on the fact that mkprot adds things to the beginning of 740 * the proto queue. 741 */ 742 743 numdiff = tbldiff(state, firstprot, tmp); 744 mkentry(tmp, numecs, statenum, -numtemps, numdiff); 745 } 746 747 748 /* mv2front - move proto queue element to front of queue */ 749 750 void 751 mv2front(int qelm) 752 { 753 if (firstprot != qelm) { 754 if (qelm == lastprot) 755 lastprot = protprev[lastprot]; 756 757 protnext[protprev[qelm]] = protnext[qelm]; 758 759 if (protnext[qelm] != NIL) 760 protprev[protnext[qelm]] = protprev[qelm]; 761 762 protprev[qelm] = NIL; 763 protnext[qelm] = firstprot; 764 protprev[firstprot] = qelm; 765 firstprot = qelm; 766 } 767 } 768 769 770 /* place_state - place a state into full speed transition table 771 * 772 * State is the statenum'th state. It is indexed by equivalence class and 773 * gives the number of the state to enter for a given equivalence class. 774 * Transnum is the number of out-transitions for the state. 775 */ 776 777 void 778 place_state(int *state, int statenum, int transnum) 779 { 780 int i; 781 int *state_ptr; 782 int position = find_table_space(state, transnum); 783 784 /* "base" is the table of start positions. */ 785 base[statenum] = position; 786 787 /* 788 * Put in action number marker; this non-zero number makes sure that 789 * find_table_space() knows that this position in chk/nxt is taken 790 * and should not be used for another accepting number in another 791 * state. 792 */ 793 chk[position - 1] = 1; 794 795 /* 796 * Put in end-of-buffer marker; this is for the same purposes as 797 * above. 798 */ 799 chk[position] = 1; 800 801 /* Place the state into chk and nxt. */ 802 state_ptr = &state[1]; 803 804 for (i = 1; i <= numecs; ++i, ++state_ptr) 805 if (*state_ptr != 0) { 806 chk[position + i] = i; 807 nxt[position + i] = *state_ptr; 808 } 809 if (position + numecs > tblend) 810 tblend = position + numecs; 811 } 812 813 814 /* stack1 - save states with only one out-transition to be processed later 815 * 816 * If there's room for another state on the "one-transition" stack, the 817 * state is pushed onto it, to be processed later by mk1tbl. If there's 818 * no room, we process the sucker right now. 819 */ 820 821 void 822 stack1(int statenum, int sym, int nextstate, int deflink) 823 { 824 if (onesp >= ONE_STACK_SIZE - 1) 825 mk1tbl(statenum, sym, nextstate, deflink); 826 827 else { 828 ++onesp; 829 onestate[onesp] = statenum; 830 onesym[onesp] = sym; 831 onenext[onesp] = nextstate; 832 onedef[onesp] = deflink; 833 } 834 } 835 836 837 /* tbldiff - compute differences between two state tables 838 * 839 * "state" is the state array which is to be extracted from the pr'th 840 * proto. "pr" is both the number of the proto we are extracting from 841 * and an index into the save area where we can find the proto's complete 842 * state table. Each entry in "state" which differs from the corresponding 843 * entry of "pr" will appear in "ext". 844 * 845 * Entries which are the same in both "state" and "pr" will be marked 846 * as transitions to "SAME_TRANS" in "ext". The total number of differences 847 * between "state" and "pr" is returned as function value. Note that this 848 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". 849 */ 850 851 int 852 tbldiff(int state[], int pr, int ext[]) 853 { 854 int i, *sp = state, *ep = ext, *protp; 855 int numdiff = 0; 856 857 protp = &protsave[numecs * (pr - 1)]; 858 859 for (i = numecs; i > 0; --i) { 860 if (*++protp == *++sp) 861 *++ep = SAME_TRANS; 862 else { 863 *++ep = *sp; 864 ++numdiff; 865 } 866 } 867 868 return numdiff; 869 } 870