1179187Sjb/* tblcmp - table compression routines */ 2179187Sjb 3179187Sjb/* Copyright (c) 1990 The Regents of the University of California. */ 4179187Sjb/* All rights reserved. */ 5179187Sjb 6179187Sjb/* This code is derived from software contributed to Berkeley by */ 7179187Sjb/* Vern Paxson. */ 8179187Sjb 9179187Sjb/* The United States Government has rights in this work pursuant */ 10179187Sjb/* to contract no. DE-AC03-76SF00098 between the United States */ 11179187Sjb/* Department of Energy and the University of California. */ 12179187Sjb 13179187Sjb/* This file is part of flex. */ 14179187Sjb 15179187Sjb/* Redistribution and use in source and binary forms, with or without */ 16179187Sjb/* modification, are permitted provided that the following conditions */ 17179187Sjb/* are met: */ 18179187Sjb 19179187Sjb/* 1. Redistributions of source code must retain the above copyright */ 20179187Sjb/* notice, this list of conditions and the following disclaimer. */ 21179187Sjb/* 2. Redistributions in binary form must reproduce the above copyright */ 22179187Sjb/* notice, this list of conditions and the following disclaimer in the */ 23179187Sjb/* documentation and/or other materials provided with the distribution. */ 24179187Sjb 25179187Sjb/* Neither the name of the University nor the names of its contributors */ 26179187Sjb/* may be used to endorse or promote products derived from this software */ 27179187Sjb/* without specific prior written permission. */ 28179187Sjb 29179187Sjb/* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 30179187Sjb/* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 31179187Sjb/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 32179187Sjb/* PURPOSE. */ 33179187Sjb 34179187Sjb#include "flexdef.h" 35179187Sjb 36179187Sjb 37179187Sjb/* declarations for functions that have forward references */ 38179187Sjb 39179187Sjbvoid mkentry PROTO ((int *, int, int, int, int)); 40179187Sjbvoid mkprot PROTO ((int[], int, int)); 41179187Sjbvoid mktemplate PROTO ((int[], int, int)); 42179187Sjbvoid mv2front PROTO ((int)); 43179187Sjbint tbldiff PROTO ((int[], int, int[])); 44179187Sjb 45179187Sjb 46179187Sjb/* bldtbl - build table entries for dfa state 47179187Sjb * 48179187Sjb * synopsis 49252430Skaiw * int state[numecs], statenum, totaltrans, comstate, comfreq; 50179187Sjb * bldtbl( state, statenum, totaltrans, comstate, comfreq ); 51179187Sjb * 52179187Sjb * State is the statenum'th dfa state. It is indexed by equivalence class and 53179187Sjb * gives the number of the state to enter for a given equivalence class. 54179187Sjb * totaltrans is the total number of transitions out of the state. Comstate 55179187Sjb * is that state which is the destination of the most transitions out of State. 56179187Sjb * Comfreq is how many transitions there are out of State to Comstate. 57179187Sjb * 58179187Sjb * A note on terminology: 59179187Sjb * "protos" are transition tables which have a high probability of 60179187Sjb * either being redundant (a state processed later will have an identical 61179187Sjb * transition table) or nearly redundant (a state processed later will have 62179187Sjb * many of the same out-transitions). A "most recently used" queue of 63179187Sjb * protos is kept around with the hope that most states will find a proto 64179187Sjb * which is similar enough to be usable, and therefore compacting the 65179187Sjb * output tables. 66179187Sjb * "templates" are a special type of proto. If a transition table is 67179187Sjb * homogeneous or nearly homogeneous (all transitions go to the same 68179187Sjb * destination) then the odds are good that future states will also go 69179187Sjb * to the same destination state on basically the same character set. 70179187Sjb * These homogeneous states are so common when dealing with large rule 71179187Sjb * sets that they merit special attention. If the transition table were 72179187Sjb * simply made into a proto, then (typically) each subsequent, similar 73179187Sjb * state will differ from the proto for two out-transitions. One of these 74179187Sjb * out-transitions will be that character on which the proto does not go 75179187Sjb * to the common destination, and one will be that character on which the 76179187Sjb * state does not go to the common destination. Templates, on the other 77179187Sjb * hand, go to the common state on EVERY transition character, and therefore 78179187Sjb * cost only one difference. 79179187Sjb */ 80179187Sjb 81179187Sjbvoid bldtbl (state, statenum, totaltrans, comstate, comfreq) 82179187Sjb int state[], statenum, totaltrans, comstate, comfreq; 83179187Sjb{ 84179187Sjb int extptr, extrct[2][CSIZE + 1]; 85179187Sjb int mindiff, minprot, i, d; 86179187Sjb 87179187Sjb /* If extptr is 0 then the first array of extrct holds the result 88179187Sjb * of the "best difference" to date, which is those transitions 89179187Sjb * which occur in "state" but not in the proto which, to date, 90179187Sjb * has the fewest differences between itself and "state". If 91179187Sjb * extptr is 1 then the second array of extrct hold the best 92179187Sjb * difference. The two arrays are toggled between so that the 93179187Sjb * best difference to date can be kept around and also a difference 94179187Sjb * just created by checking against a candidate "best" proto. 95179187Sjb */ 96179187Sjb 97179187Sjb extptr = 0; 98179187Sjb 99179187Sjb /* If the state has too few out-transitions, don't bother trying to 100179187Sjb * compact its tables. 101179187Sjb */ 102179187Sjb 103179187Sjb if ((totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE)) 104179187Sjb mkentry (state, numecs, statenum, JAMSTATE, totaltrans); 105179187Sjb 106179187Sjb else { 107179187Sjb /* "checkcom" is true if we should only check "state" against 108179187Sjb * protos which have the same "comstate" value. 109179187Sjb */ 110179187Sjb int checkcom = 111179187Sjb 112179187Sjb comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE; 113179187Sjb 114179187Sjb minprot = firstprot; 115179187Sjb mindiff = totaltrans; 116179187Sjb 117179187Sjb if (checkcom) { 118179187Sjb /* Find first proto which has the same "comstate". */ 119179187Sjb for (i = firstprot; i != NIL; i = protnext[i]) 120179187Sjb if (protcomst[i] == comstate) { 121179187Sjb minprot = i; 122179187Sjb mindiff = tbldiff (state, minprot, 123179187Sjb extrct[extptr]); 124179187Sjb break; 125179187Sjb } 126179187Sjb } 127179187Sjb 128179187Sjb else { 129179187Sjb /* Since we've decided that the most common destination 130179187Sjb * out of "state" does not occur with a high enough 131179187Sjb * frequency, we set the "comstate" to zero, assuring 132179187Sjb * that if this state is entered into the proto list, 133179187Sjb * it will not be considered a template. 134179187Sjb */ 135179187Sjb comstate = 0; 136179187Sjb 137179187Sjb if (firstprot != NIL) { 138179187Sjb minprot = firstprot; 139179187Sjb mindiff = tbldiff (state, minprot, 140179187Sjb extrct[extptr]); 141179187Sjb } 142179187Sjb } 143179187Sjb 144179187Sjb /* We now have the first interesting proto in "minprot". If 145179187Sjb * it matches within the tolerances set for the first proto, 146179187Sjb * we don't want to bother scanning the rest of the proto list 147179187Sjb * to see if we have any other reasonable matches. 148179187Sjb */ 149179187Sjb 150179187Sjb if (mindiff * 100 > 151179187Sjb totaltrans * FIRST_MATCH_DIFF_PERCENTAGE) { 152179187Sjb /* Not a good enough match. Scan the rest of the 153179187Sjb * protos. 154179187Sjb */ 155179187Sjb for (i = minprot; i != NIL; i = protnext[i]) { 156179187Sjb d = tbldiff (state, i, extrct[1 - extptr]); 157179187Sjb if (d < mindiff) { 158179187Sjb extptr = 1 - extptr; 159179187Sjb mindiff = d; 160179187Sjb minprot = i; 161179187Sjb } 162179187Sjb } 163179187Sjb } 164179187Sjb 165179187Sjb /* Check if the proto we've decided on as our best bet is close 166179187Sjb * enough to the state we want to match to be usable. 167179187Sjb */ 168179187Sjb 169179187Sjb if (mindiff * 100 > 170179187Sjb totaltrans * ACCEPTABLE_DIFF_PERCENTAGE) { 171179187Sjb /* No good. If the state is homogeneous enough, 172179187Sjb * we make a template out of it. Otherwise, we 173179187Sjb * make a proto. 174179187Sjb */ 175179187Sjb 176179187Sjb if (comfreq * 100 >= 177179187Sjb totaltrans * TEMPLATE_SAME_PERCENTAGE) 178179187Sjb mktemplate (state, statenum, 179179187Sjb comstate); 180179187Sjb 181179187Sjb else { 182179187Sjb mkprot (state, statenum, comstate); 183179187Sjb mkentry (state, numecs, statenum, 184179187Sjb JAMSTATE, totaltrans); 185179187Sjb } 186179187Sjb } 187179187Sjb 188179187Sjb else { /* use the proto */ 189179187Sjb mkentry (extrct[extptr], numecs, statenum, 190179187Sjb prottbl[minprot], mindiff); 191179187Sjb 192179187Sjb /* If this state was sufficiently different from the 193179187Sjb * proto we built it from, make it, too, a proto. 194179187Sjb */ 195179187Sjb 196179187Sjb if (mindiff * 100 >= 197179187Sjb totaltrans * NEW_PROTO_DIFF_PERCENTAGE) 198179187Sjb mkprot (state, statenum, comstate); 199179187Sjb 200179187Sjb /* Since mkprot added a new proto to the proto queue, 201179187Sjb * it's possible that "minprot" is no longer on the 202179187Sjb * proto queue (if it happened to have been the last 203179187Sjb * entry, it would have been bumped off). If it's 204179187Sjb * not there, then the new proto took its physical 205179187Sjb * place (though logically the new proto is at the 206179187Sjb * beginning of the queue), so in that case the 207179187Sjb * following call will do nothing. 208179187Sjb */ 209179187Sjb 210179187Sjb mv2front (minprot); 211179187Sjb } 212179187Sjb } 213179187Sjb} 214179187Sjb 215179187Sjb 216179187Sjb/* cmptmps - compress template table entries 217179187Sjb * 218179187Sjb * Template tables are compressed by using the 'template equivalence 219179187Sjb * classes', which are collections of transition character equivalence 220179187Sjb * classes which always appear together in templates - really meta-equivalence 221179187Sjb * classes. 222179187Sjb */ 223179187Sjb 224179187Sjbvoid cmptmps () 225179187Sjb{ 226179187Sjb int tmpstorage[CSIZE + 1]; 227179187Sjb int *tmp = tmpstorage, i, j; 228179187Sjb int totaltrans, trans; 229179187Sjb 230179187Sjb peakpairs = numtemps * numecs + tblend; 231179187Sjb 232179187Sjb if (usemecs) { 233179187Sjb /* Create equivalence classes based on data gathered on 234179187Sjb * template transitions. 235179187Sjb */ 236179187Sjb nummecs = cre8ecs (tecfwd, tecbck, numecs); 237179187Sjb } 238179187Sjb 239195747Snp else 240179187Sjb nummecs = numecs; 241179187Sjb 242179187Sjb while (lastdfa + numtemps + 1 >= current_max_dfas) 243179187Sjb increase_max_dfas (); 244179187Sjb 245179187Sjb /* Loop through each template. */ 246179187Sjb 247179187Sjb for (i = 1; i <= numtemps; ++i) { 248179187Sjb /* Number of non-jam transitions out of this template. */ 249179187Sjb totaltrans = 0; 250179187Sjb 251179187Sjb for (j = 1; j <= numecs; ++j) { 252179187Sjb trans = tnxt[numecs * i + j]; 253179187Sjb 254179187Sjb if (usemecs) { 255179187Sjb /* The absolute value of tecbck is the 256179187Sjb * meta-equivalence class of a given 257179187Sjb * equivalence class, as set up by cre8ecs(). 258179187Sjb */ 259179187Sjb if (tecbck[j] > 0) { 260179187Sjb tmp[tecbck[j]] = trans; 261179187Sjb 262179187Sjb if (trans > 0) 263179187Sjb ++totaltrans; 264179187Sjb } 265179187Sjb } 266179187Sjb 267179187Sjb else { 268179187Sjb tmp[j] = trans; 269179187Sjb 270179187Sjb if (trans > 0) 271179187Sjb ++totaltrans; 272179187Sjb } 273179187Sjb } 274179187Sjb 275179187Sjb /* It is assumed (in a rather subtle way) in the skeleton 276179187Sjb * that if we're using meta-equivalence classes, the def[] 277179187Sjb * entry for all templates is the jam template, i.e., 278179187Sjb * templates never default to other non-jam table entries 279179187Sjb * (e.g., another template) 280179187Sjb */ 281179187Sjb 282179187Sjb /* Leave room for the jam-state after the last real state. */ 283179187Sjb mkentry (tmp, nummecs, lastdfa + i + 1, JAMSTATE, 284179187Sjb totaltrans); 285179187Sjb } 286179187Sjb} 287179187Sjb 288179187Sjb 289179187Sjb 290179187Sjb/* expand_nxt_chk - expand the next check arrays */ 291179187Sjb 292179187Sjbvoid expand_nxt_chk () 293179187Sjb{ 294179187Sjb int old_max = current_max_xpairs; 295179187Sjb 296179187Sjb current_max_xpairs += MAX_XPAIRS_INCREMENT; 297179187Sjb 298179187Sjb ++num_reallocs; 299179187Sjb 300179187Sjb nxt = reallocate_integer_array (nxt, current_max_xpairs); 301179187Sjb chk = reallocate_integer_array (chk, current_max_xpairs); 302179187Sjb 303179187Sjb zero_out ((char *) (chk + old_max), 304179187Sjb (size_t) (MAX_XPAIRS_INCREMENT * sizeof (int))); 305179187Sjb} 306179187Sjb 307179187Sjb 308179187Sjb/* find_table_space - finds a space in the table for a state to be placed 309179187Sjb * 310179187Sjb * synopsis 311179187Sjb * int *state, numtrans, block_start; 312179187Sjb * int find_table_space(); 313179187Sjb * 314179187Sjb * block_start = find_table_space( state, numtrans ); 315179187Sjb * 316179187Sjb * State is the state to be added to the full speed transition table. 317179187Sjb * Numtrans is the number of out-transitions for the state. 318179187Sjb * 319179187Sjb * find_table_space() returns the position of the start of the first block (in 320179187Sjb * chk) able to accommodate the state 321179187Sjb * 322179187Sjb * In determining if a state will or will not fit, find_table_space() must take 323179187Sjb * into account the fact that an end-of-buffer state will be added at [0], 324179187Sjb * and an action number will be added in [-1]. 325179187Sjb */ 326179187Sjb 327179187Sjbint find_table_space (state, numtrans) 328179187Sjb int *state, numtrans; 329179187Sjb{ 330179187Sjb /* Firstfree is the position of the first possible occurrence of two 331179187Sjb * consecutive unused records in the chk and nxt arrays. 332179187Sjb */ 333179187Sjb int i; 334179187Sjb int *state_ptr, *chk_ptr; 335179187Sjb int *ptr_to_last_entry_in_state; 336179187Sjb 337179187Sjb /* If there are too many out-transitions, put the state at the end of 338179187Sjb * nxt and chk. 339179187Sjb */ 340179187Sjb if (numtrans > MAX_XTIONS_FULL_INTERIOR_FIT) { 341179187Sjb /* If table is empty, return the first available spot in 342179187Sjb * chk/nxt, which should be 1. 343179187Sjb */ 344179187Sjb if (tblend < 2) 345179187Sjb return 1; 346179187Sjb 347179187Sjb /* Start searching for table space near the end of 348179187Sjb * chk/nxt arrays. 349179187Sjb */ 350179187Sjb i = tblend - numecs; 351179187Sjb } 352179187Sjb 353179187Sjb else 354179187Sjb /* Start searching for table space from the beginning 355179187Sjb * (skipping only the elements which will definitely not 356179187Sjb * hold the new state). 357179187Sjb */ 358179187Sjb i = firstfree; 359179187Sjb 360179187Sjb while (1) { /* loops until a space is found */ 361179187Sjb while (i + numecs >= current_max_xpairs) 362179187Sjb expand_nxt_chk (); 363179187Sjb 364179187Sjb /* Loops until space for end-of-buffer and action number 365179187Sjb * are found. 366179187Sjb */ 367179187Sjb while (1) { 368179187Sjb /* Check for action number space. */ 369179187Sjb if (chk[i - 1] == 0) { 370179187Sjb /* Check for end-of-buffer space. */ 371179187Sjb if (chk[i] == 0) 372179187Sjb break; 373179187Sjb 374179187Sjb else 375179187Sjb /* Since i != 0, there is no use 376179187Sjb * checking to see if (++i) - 1 == 0, 377179187Sjb * because that's the same as i == 0, 378179187Sjb * so we skip a space. 379179187Sjb */ 380179187Sjb i += 2; 381179187Sjb } 382179187Sjb 383179187Sjb else 384179187Sjb ++i; 385179187Sjb 386179187Sjb while (i + numecs >= current_max_xpairs) 387179187Sjb expand_nxt_chk (); 388179187Sjb } 389179187Sjb 390179187Sjb /* If we started search from the beginning, store the new 391179187Sjb * firstfree for the next call of find_table_space(). 392179187Sjb */ 393179187Sjb if (numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT) 394179187Sjb firstfree = i + 1; 395179187Sjb 396179187Sjb /* Check to see if all elements in chk (and therefore nxt) 397179187Sjb * that are needed for the new state have not yet been taken. 398179187Sjb */ 399179187Sjb 400179187Sjb state_ptr = &state[1]; 401179187Sjb ptr_to_last_entry_in_state = &chk[i + numecs + 1]; 402179187Sjb 403179187Sjb for (chk_ptr = &chk[i + 1]; 404179187Sjb chk_ptr != ptr_to_last_entry_in_state; ++chk_ptr) 405179187Sjb if (*(state_ptr++) != 0 && *chk_ptr != 0) 406179187Sjb break; 407179187Sjb 408179187Sjb if (chk_ptr == ptr_to_last_entry_in_state) 409179187Sjb return i; 410179187Sjb 411179187Sjb else 412179187Sjb ++i; 413179187Sjb } 414179187Sjb} 415179187Sjb 416179187Sjb 417179187Sjb/* inittbl - initialize transition tables 418179187Sjb * 419179187Sjb * Initializes "firstfree" to be one beyond the end of the table. Initializes 420179187Sjb * all "chk" entries to be zero. 421179187Sjb */ 422179187Sjbvoid inittbl () 423179187Sjb{ 424179187Sjb int i; 425179187Sjb 426179187Sjb zero_out ((char *) chk, 427179187Sjb 428179187Sjb (size_t) (current_max_xpairs * sizeof (int))); 429179187Sjb 430179187Sjb tblend = 0; 431179187Sjb firstfree = tblend + 1; 432179187Sjb numtemps = 0; 433179187Sjb 434179187Sjb if (usemecs) { 435179187Sjb /* Set up doubly-linked meta-equivalence classes; these 436179187Sjb * are sets of equivalence classes which all have identical 437179187Sjb * transitions out of TEMPLATES. 438179187Sjb */ 439179187Sjb 440179187Sjb tecbck[1] = NIL; 441179187Sjb 442179187Sjb for (i = 2; i <= numecs; ++i) { 443179187Sjb tecbck[i] = i - 1; 444179187Sjb tecfwd[i - 1] = i; 445179187Sjb } 446179187Sjb 447179187Sjb tecfwd[numecs] = NIL; 448179187Sjb } 449179187Sjb} 450179187Sjb 451179187Sjb 452179187Sjb/* mkdeftbl - make the default, "jam" table entries */ 453179187Sjb 454179187Sjbvoid mkdeftbl () 455179187Sjb{ 456179187Sjb int i; 457179187Sjb 458179187Sjb jamstate = lastdfa + 1; 459179187Sjb 460179187Sjb ++tblend; /* room for transition on end-of-buffer character */ 461195747Snp 462179187Sjb while (tblend + numecs >= current_max_xpairs) 463179187Sjb expand_nxt_chk (); 464179187Sjb 465179187Sjb /* Add in default end-of-buffer transition. */ 466179187Sjb nxt[tblend] = end_of_buffer_state; 467179187Sjb chk[tblend] = jamstate; 468179187Sjb 469179187Sjb for (i = 1; i <= numecs; ++i) { 470179187Sjb nxt[tblend + i] = 0; 471179187Sjb chk[tblend + i] = jamstate; 472179187Sjb } 473179187Sjb 474179187Sjb jambase = tblend; 475179187Sjb 476179187Sjb base[jamstate] = jambase; 477179187Sjb def[jamstate] = 0; 478179187Sjb 479179187Sjb tblend += numecs; 480179187Sjb ++numtemps; 481179187Sjb} 482179187Sjb 483179187Sjb 484179187Sjb/* mkentry - create base/def and nxt/chk entries for transition array 485179187Sjb * 486179187Sjb * synopsis 487179187Sjb * int state[numchars + 1], numchars, statenum, deflink, totaltrans; 488179187Sjb * mkentry( state, numchars, statenum, deflink, totaltrans ); 489179187Sjb * 490179187Sjb * "state" is a transition array "numchars" characters in size, "statenum" 491179187Sjb * is the offset to be used into the base/def tables, and "deflink" is the 492179187Sjb * entry to put in the "def" table entry. If "deflink" is equal to 493179187Sjb * "JAMSTATE", then no attempt will be made to fit zero entries of "state" 494179187Sjb * (i.e., jam entries) into the table. It is assumed that by linking to 495179187Sjb * "JAMSTATE" they will be taken care of. In any case, entries in "state" 496179187Sjb * marking transitions to "SAME_TRANS" are treated as though they will be 497179187Sjb * taken care of by wherever "deflink" points. "totaltrans" is the total 498179187Sjb * number of transitions out of the state. If it is below a certain threshold, 499179187Sjb * the tables are searched for an interior spot that will accommodate the 500179187Sjb * state array. 501179187Sjb */ 502179187Sjb 503179187Sjbvoid mkentry (state, numchars, statenum, deflink, totaltrans) 504179187Sjb int *state; 505179187Sjb int numchars, statenum, deflink, totaltrans; 506179187Sjb{ 507179187Sjb int minec, maxec, i, baseaddr; 508179187Sjb int tblbase, tbllast; 509179187Sjb 510179187Sjb if (totaltrans == 0) { /* there are no out-transitions */ 511179187Sjb if (deflink == JAMSTATE) 512179187Sjb base[statenum] = JAMSTATE; 513179187Sjb else 514179187Sjb base[statenum] = 0; 515179187Sjb 516179187Sjb def[statenum] = deflink; 517179187Sjb return; 518179187Sjb } 519179187Sjb 520179187Sjb for (minec = 1; minec <= numchars; ++minec) { 521179187Sjb if (state[minec] != SAME_TRANS) 522179187Sjb if (state[minec] != 0 || deflink != JAMSTATE) 523179187Sjb break; 524179187Sjb } 525179187Sjb 526179187Sjb if (totaltrans == 1) { 527179187Sjb /* There's only one out-transition. Save it for later to fill 528179187Sjb * in holes in the tables. 529179187Sjb */ 530179187Sjb stack1 (statenum, minec, state[minec], deflink); 531179187Sjb return; 532179187Sjb } 533179187Sjb 534179187Sjb for (maxec = numchars; maxec > 0; --maxec) { 535179187Sjb if (state[maxec] != SAME_TRANS) 536179187Sjb if (state[maxec] != 0 || deflink != JAMSTATE) 537179187Sjb break; 538179187Sjb } 539179187Sjb 540179187Sjb /* Whether we try to fit the state table in the middle of the table 541179187Sjb * entries we have already generated, or if we just take the state 542179187Sjb * table at the end of the nxt/chk tables, we must make sure that we 543179187Sjb * have a valid base address (i.e., non-negative). Note that 544179187Sjb * negative base addresses dangerous at run-time (because indexing 545179187Sjb * the nxt array with one and a low-valued character will access 546179187Sjb * memory before the start of the array. 547179187Sjb */ 548179187Sjb 549179187Sjb /* Find the first transition of state that we need to worry about. */ 550179187Sjb if (totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE) { 551179187Sjb /* Attempt to squeeze it into the middle of the tables. */ 552179187Sjb baseaddr = firstfree; 553179187Sjb 554179187Sjb while (baseaddr < minec) { 555179187Sjb /* Using baseaddr would result in a negative base 556179187Sjb * address below; find the next free slot. 557179187Sjb */ 558179187Sjb for (++baseaddr; chk[baseaddr] != 0; ++baseaddr) ; 559179187Sjb } 560179187Sjb 561179187Sjb while (baseaddr + maxec - minec + 1 >= current_max_xpairs) 562179187Sjb expand_nxt_chk (); 563179187Sjb 564179187Sjb for (i = minec; i <= maxec; ++i) 565179187Sjb if (state[i] != SAME_TRANS && 566179187Sjb (state[i] != 0 || deflink != JAMSTATE) && 567179187Sjb chk[baseaddr + i - minec] != 0) { /* baseaddr unsuitable - find another */ 568179187Sjb for (++baseaddr; 569179187Sjb baseaddr < current_max_xpairs && 570179187Sjb chk[baseaddr] != 0; ++baseaddr) ; 571179187Sjb 572179187Sjb while (baseaddr + maxec - minec + 1 >= 573179187Sjb current_max_xpairs) 574179187Sjb expand_nxt_chk (); 575179187Sjb 576179187Sjb /* Reset the loop counter so we'll start all 577179187Sjb * over again next time it's incremented. 578179187Sjb */ 579179187Sjb 580179187Sjb i = minec - 1; 581179187Sjb } 582179187Sjb } 583179187Sjb 584179187Sjb else { 585179187Sjb /* Ensure that the base address we eventually generate is 586179187Sjb * non-negative. 587179187Sjb */ 588179187Sjb baseaddr = MAX (tblend + 1, minec); 589179187Sjb } 590179187Sjb 591179187Sjb tblbase = baseaddr - minec; 592179187Sjb tbllast = tblbase + maxec; 593179187Sjb 594179187Sjb while (tbllast + 1 >= current_max_xpairs) 595179187Sjb expand_nxt_chk (); 596179187Sjb 597179187Sjb base[statenum] = tblbase; 598179187Sjb def[statenum] = deflink; 599179187Sjb 600179187Sjb for (i = minec; i <= maxec; ++i) 601179187Sjb if (state[i] != SAME_TRANS) 602179187Sjb if (state[i] != 0 || deflink != JAMSTATE) { 603179187Sjb nxt[tblbase + i] = state[i]; 604179187Sjb chk[tblbase + i] = statenum; 605179187Sjb } 606179187Sjb 607179187Sjb if (baseaddr == firstfree) 608179187Sjb /* Find next free slot in tables. */ 609179187Sjb for (++firstfree; chk[firstfree] != 0; ++firstfree) ; 610179187Sjb 611179187Sjb tblend = MAX (tblend, tbllast); 612179187Sjb} 613179187Sjb 614 615/* mk1tbl - create table entries for a state (or state fragment) which 616 * has only one out-transition 617 */ 618 619void mk1tbl (state, sym, onenxt, onedef) 620 int state, sym, onenxt, onedef; 621{ 622 if (firstfree < sym) 623 firstfree = sym; 624 625 while (chk[firstfree] != 0) 626 if (++firstfree >= current_max_xpairs) 627 expand_nxt_chk (); 628 629 base[state] = firstfree - sym; 630 def[state] = onedef; 631 chk[firstfree] = state; 632 nxt[firstfree] = onenxt; 633 634 if (firstfree > tblend) { 635 tblend = firstfree++; 636 637 if (firstfree >= current_max_xpairs) 638 expand_nxt_chk (); 639 } 640} 641 642 643/* mkprot - create new proto entry */ 644 645void mkprot (state, statenum, comstate) 646 int state[], statenum, comstate; 647{ 648 int i, slot, tblbase; 649 650 if (++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE) { 651 /* Gotta make room for the new proto by dropping last entry in 652 * the queue. 653 */ 654 slot = lastprot; 655 lastprot = protprev[lastprot]; 656 protnext[lastprot] = NIL; 657 } 658 659 else 660 slot = numprots; 661 662 protnext[slot] = firstprot; 663 664 if (firstprot != NIL) 665 protprev[firstprot] = slot; 666 667 firstprot = slot; 668 prottbl[slot] = statenum; 669 protcomst[slot] = comstate; 670 671 /* Copy state into save area so it can be compared with rapidly. */ 672 tblbase = numecs * (slot - 1); 673 674 for (i = 1; i <= numecs; ++i) 675 protsave[tblbase + i] = state[i]; 676} 677 678 679/* mktemplate - create a template entry based on a state, and connect the state 680 * to it 681 */ 682 683void mktemplate (state, statenum, comstate) 684 int state[], statenum, comstate; 685{ 686 int i, numdiff, tmpbase, tmp[CSIZE + 1]; 687 Char transset[CSIZE + 1]; 688 int tsptr; 689 690 ++numtemps; 691 692 tsptr = 0; 693 694 /* Calculate where we will temporarily store the transition table 695 * of the template in the tnxt[] array. The final transition table 696 * gets created by cmptmps(). 697 */ 698 699 tmpbase = numtemps * numecs; 700 701 if (tmpbase + numecs >= current_max_template_xpairs) { 702 current_max_template_xpairs += 703 MAX_TEMPLATE_XPAIRS_INCREMENT; 704 705 ++num_reallocs; 706 707 tnxt = reallocate_integer_array (tnxt, 708 current_max_template_xpairs); 709 } 710 711 for (i = 1; i <= numecs; ++i) 712 if (state[i] == 0) 713 tnxt[tmpbase + i] = 0; 714 else { 715 transset[tsptr++] = i; 716 tnxt[tmpbase + i] = comstate; 717 } 718 719 if (usemecs) 720 mkeccl (transset, tsptr, tecfwd, tecbck, numecs, 0); 721 722 mkprot (tnxt + tmpbase, -numtemps, comstate); 723 724 /* We rely on the fact that mkprot adds things to the beginning 725 * of the proto queue. 726 */ 727 728 numdiff = tbldiff (state, firstprot, tmp); 729 mkentry (tmp, numecs, statenum, -numtemps, numdiff); 730} 731 732 733/* mv2front - move proto queue element to front of queue */ 734 735void mv2front (qelm) 736 int qelm; 737{ 738 if (firstprot != qelm) { 739 if (qelm == lastprot) 740 lastprot = protprev[lastprot]; 741 742 protnext[protprev[qelm]] = protnext[qelm]; 743 744 if (protnext[qelm] != NIL) 745 protprev[protnext[qelm]] = protprev[qelm]; 746 747 protprev[qelm] = NIL; 748 protnext[qelm] = firstprot; 749 protprev[firstprot] = qelm; 750 firstprot = qelm; 751 } 752} 753 754 755/* place_state - place a state into full speed transition table 756 * 757 * State is the statenum'th state. It is indexed by equivalence class and 758 * gives the number of the state to enter for a given equivalence class. 759 * Transnum is the number of out-transitions for the state. 760 */ 761 762void place_state (state, statenum, transnum) 763 int *state, statenum, transnum; 764{ 765 int i; 766 int *state_ptr; 767 int position = find_table_space (state, transnum); 768 769 /* "base" is the table of start positions. */ 770 base[statenum] = position; 771 772 /* Put in action number marker; this non-zero number makes sure that 773 * find_table_space() knows that this position in chk/nxt is taken 774 * and should not be used for another accepting number in another 775 * state. 776 */ 777 chk[position - 1] = 1; 778 779 /* Put in end-of-buffer marker; this is for the same purposes as 780 * above. 781 */ 782 chk[position] = 1; 783 784 /* Place the state into chk and nxt. */ 785 state_ptr = &state[1]; 786 787 for (i = 1; i <= numecs; ++i, ++state_ptr) 788 if (*state_ptr != 0) { 789 chk[position + i] = i; 790 nxt[position + i] = *state_ptr; 791 } 792 793 if (position + numecs > tblend) 794 tblend = position + numecs; 795} 796 797 798/* stack1 - save states with only one out-transition to be processed later 799 * 800 * If there's room for another state on the "one-transition" stack, the 801 * state is pushed onto it, to be processed later by mk1tbl. If there's 802 * no room, we process the sucker right now. 803 */ 804 805void stack1 (statenum, sym, nextstate, deflink) 806 int statenum, sym, nextstate, deflink; 807{ 808 if (onesp >= ONE_STACK_SIZE - 1) 809 mk1tbl (statenum, sym, nextstate, deflink); 810 811 else { 812 ++onesp; 813 onestate[onesp] = statenum; 814 onesym[onesp] = sym; 815 onenext[onesp] = nextstate; 816 onedef[onesp] = deflink; 817 } 818} 819 820 821/* tbldiff - compute differences between two state tables 822 * 823 * "state" is the state array which is to be extracted from the pr'th 824 * proto. "pr" is both the number of the proto we are extracting from 825 * and an index into the save area where we can find the proto's complete 826 * state table. Each entry in "state" which differs from the corresponding 827 * entry of "pr" will appear in "ext". 828 * 829 * Entries which are the same in both "state" and "pr" will be marked 830 * as transitions to "SAME_TRANS" in "ext". The total number of differences 831 * between "state" and "pr" is returned as function value. Note that this 832 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". 833 */ 834 835int tbldiff (state, pr, ext) 836 int state[], pr, ext[]; 837{ 838 int i, *sp = state, *ep = ext, *protp; 839 int numdiff = 0; 840 841 protp = &protsave[numecs * (pr - 1)]; 842 843 for (i = numecs; i > 0; --i) { 844 if (*++protp == *++sp) 845 *++ep = SAME_TRANS; 846 else { 847 *++ep = *sp; 848 ++numdiff; 849 } 850 } 851 852 return numdiff; 853} 854