Azinix

evlFsm.c

Go to the documentation of this file.
00001 /** \file evlFsm.c
00002 
00003 
00004   \brief    Build an FSM from a collection of rules
00005 
00006 ******************************************************************************/
00007 
00008 #include "nm.h"
00009 #include "evl.h"
00010 
00011 /**AutomaticStart*************************************************************/
00012 
00013 /*---------------------------------------------------------------------------*/
00014 /* Static function prototypes                                                */
00015 /*---------------------------------------------------------------------------*/
00016 
00017 static int maxPrefixSuffixOverlap (char *aString, char *bString);
00018 static char *byteArrayToString (util_byte_array_t * aByteArray);
00019 static int fsmPrintBlifLogEncode (Evl_Fsm_t * fsm);
00020 static int computeIndexCount (bdd_t * aBdd, st_table * computedTable,
00021                   int *countArray);
00022 static int computeAcceptingStates (Evl_Fsm_t * fsm);
00023 
00024 /**AutomaticEnd***************************************************************/
00025 
00026 /*---------------------------------------------------------------------------*/
00027 /* Definition of exported functions                                          */
00028 /*---------------------------------------------------------------------------*/
00029 
00030 
00031 /**
00032   * \brief  Compute the length of the longest prefix of aString
00033   * that's a suffix of bString.
00034   */
00035 
00036 static int
00037 maxPrefixSuffixOverlap (char *aString, char *bString)
00038 {
00039   int i;
00040   int N = strlen (bString);
00041   int maxOverlap = 0;
00042   // printf("a = %s, b = %s ; N (strlen bString ) = %d\n" , aString, bString, N );
00043   for (i = 1; i < N; i++)
00044     {
00045       if (util_strequalN (aString, bString + N - i, i))
00046     {
00047       maxOverlap = i;
00048       // printf("Got an overlap of length %d\n", i);
00049     }
00050       else
00051     {
00052       // printf("No overlap of length %d\n", i);
00053     }
00054     }
00055   return maxOverlap;
00056 }
00057 
00058 
00059 /**
00060   * \brief  Build a prefix automaton for a set of byte arrays.
00061   */
00062 
00063 Evl_Fsm_t *
00064 Evl_BuildPrefixAutomaton (array_t * byteArrayArray)
00065 {
00066   Evl_Fsm_t *resultFsm = (Evl_Fsm_t *) malloc (sizeof (Evl_Fsm_t));
00067   char tmpBuf[1000];
00068 
00069   st_table *prefixHash =
00070     Hash_InitTable ( ( int(*)()) util_byte_array_cmp,  ( int(*)()) util_byte_array_hash);
00071 
00072   int i, j;
00073   util_byte_array_t *aByteArray;
00074   for (i = 0; i < array_n (byteArrayArray); i++)
00075     {
00076       aByteArray = array_fetch (util_byte_array_t *, byteArrayArray, i);
00077       // full strings are id'd by their position in the array passed in
00078       Hash_Insert (prefixHash, (char *) aByteArray, (char *) i);
00079     }
00080 
00081   int tmpState;
00082 
00083   util_byte_array_t *tmp1 =
00084     (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
00085   util_byte_array_t *tmp2;
00086 
00087   util_byte_array_t *prefix =
00088     (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
00089   util_byte_array_t *suffix =
00090     (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
00091 
00092   for (i = 0; i < array_n (byteArrayArray); i++)
00093     {
00094       aByteArray = array_fetch (util_byte_array_t *, byteArrayArray, i);
00095       for (j = 0; j < aByteArray->length; j++)
00096     {
00097       tmp1->bytes = aByteArray->bytes;
00098       tmp1->length = j;
00099       if (Hash_Lookup (prefixHash, (char *) tmp1, (char **) 0))
00100         {
00101           continue;
00102         }
00103       else
00104         {
00105           tmp2 =
00106         (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
00107           tmp2->bytes = aByteArray->bytes;
00108           tmp2->length = j;
00109           tmpState = st_count (prefixHash);
00110           Hash_Insert (prefixHash, (char *) tmp2, (char *) tmpState);
00111         }
00112     }
00113     }
00114   st_generator *stGen;
00115   int numStates = st_count (prefixHash);
00116   resultFsm->stateIdToPrefix =
00117     (util_byte_array_t **) malloc (numStates * sizeof (util_byte_array_t *));
00118   st_foreach_item (prefixHash, stGen, (char **) &prefix, (char **) &tmpState)
00119   {
00120     resultFsm->stateIdToPrefix[tmpState] = prefix;
00121   }
00122 
00123   const int numInputValues = 256;
00124   // trying to align on 64 byte addresses
00125   // remember to add to fsm struct so we can free it later
00126   u_int16_t *transitionTableRaw =
00127     (u_int16_t *) malloc (numInputValues * numStates * sizeof (u_int16_t) +
00128               64);
00129   u_int16_t *transitionTable =
00130     (u_int16_t
00131      *) ((char *) ((((u_int32_t) transitionTableRaw) & ~(u_int32_t) 0x3f)) +
00132      64);
00133   for (i = 0; i < numStates; i++)
00134     {
00135       for (j = 0; j < numInputValues; j++)
00136     {
00137       transitionTable[numInputValues * i + j] = -1;
00138     }
00139     }
00140 
00141   int aState;
00142   for (aState = 0; aState < numStates; aState++)
00143     {
00144       prefix = resultFsm->stateIdToPrefix[aState];
00145       int prefixLength = prefix->length;
00146       memcpy (tmpBuf, prefix->bytes, prefixLength);
00147       unsigned char aChar;
00148       int l;
00149       for (l = 0; l < numInputValues; l++)
00150     {
00151       aChar = l;
00152       tmpBuf[prefixLength] = aChar;
00153       int nextState = -1;
00154       int k;
00155       for (k = 0; k <= prefixLength + 1; k++)
00156         {
00157           suffix->bytes = &tmpBuf[prefixLength + 1 - k];
00158           suffix->length = k;
00159           if (Hash_Lookup
00160           (prefixHash, (char *) suffix, (char **) &tmpState))
00161         {
00162           nextState = tmpState;
00163         }
00164         }
00165       assert (nextState != -1);
00166       transitionTable[aState * numInputValues + l] = nextState;
00167     }
00168     }
00169 
00170   resultFsm->N = numStates;
00171   resultFsm->stateCount = (int *) calloc (sizeof (int), numStates);
00172   resultFsm->numStrings = array_n (byteArrayArray);
00173   resultFsm->nextStateFunction = transitionTable;
00174   resultFsm->numInputValues = numInputValues;
00175   resultFsm->prefixHash = prefixHash;
00176 
00177   resultFsm->finalStates = array_alloc (array_t *, numStates);
00178   // resultFsm->finalStatesVarSet = var_set_new( numStates );
00179   char *finalStatesVarSetRaw = (char *) calloc (numStates + 64, sizeof (u_int8_t));
00180   // trying to align pointers on 64 byte bndries
00181   // remember to free appropriately
00182   resultFsm->finalStatesVarSet =
00183     ((((u_int8_t *) ((u_int32_t) finalStatesVarSetRaw & ~(u_int32_t) 0x3f))) +
00184      64);
00185   for (i = 0; i < numStates; i++)
00186     {
00187       array_insert (array_t *, resultFsm->finalStates, i, NIL (array_t));
00188     }
00189   computeAcceptingStates (resultFsm);
00190 
00191   return resultFsm;
00192 
00193 }
00194 
00195 
00196 /**
00197   * \brief  Print an FSM, meant for debugging purposes
00198   */
00199 
00200 int
00201 Evl_FsmPrint (Evl_Fsm_t * anFsm)
00202 {
00203   int i, k;
00204 
00205   printf ("Number of strings = %d, number of states = %d\n",
00206       anFsm->numStrings, anFsm->N);
00207   util_byte_array_t **sortedStrings =
00208     (util_byte_array_t **) malloc (anFsm->N * sizeof (util_byte_array_t *));
00209   for (i = 0; i < anFsm->N; i++)
00210     {
00211       sortedStrings[i] = anFsm->stateIdToPrefix[i];
00212     }
00213   // qsort(sortedStrings, anFsm->N, sizeof(util_byte_array_t *), util_byte_array_cmp );
00214   int tmpState;
00215   printf ("Printing all states:\n");
00216   for (i = 0; i < anFsm->N; i++)
00217     {
00218       printf ("\tstate %d = %s\n", i,
00219           byteArrayToString (anFsm->stateIdToPrefix[i]));
00220     }
00221   printf ("Printing transition table:\n");
00222   for (i = 0; i < anFsm->N; i++)
00223     {
00224       Hash_Lookup (anFsm->prefixHash, (char *) sortedStrings[i],
00225          (char **) &tmpState);
00226       printf ("Printing transitions out of state %d\n", tmpState);
00227       printf ("\twhich is: %s\n", byteArrayToString (sortedStrings[i]));
00228       printf ("\n");
00229       for (k = 0; k < 256; k++)
00230     {
00231       if (anFsm->
00232           nextStateFunction[tmpState * anFsm->numInputValues + k] !=
00233           anFsm->numStrings)
00234         {
00235           // anFsm->numStrings is the initial state (assuming \epsilon is not
00236           // a valid string
00237           printf ("%s goes to %s on %c\n",
00238               byteArrayToString (anFsm->stateIdToPrefix[tmpState]),
00239               byteArrayToString (anFsm->
00240                      stateIdToPrefix[anFsm->
00241                              nextStateFunction
00242                              [tmpState *
00243                               anFsm->
00244                               numInputValues +
00245                               k]]), k);
00246         }
00247     }
00248     }
00249   return 0;
00250 }
00251 
00252 
00253 /**
00254   * \brief  Return a string encoding a byte array - replace non printable chars by .
00255   */
00256 
00257 static char *
00258 byteArrayToString (util_byte_array_t * aByteArray)
00259 {
00260   char *result = (char *) malloc (sizeof (char) * aByteArray->length + 1);
00261   int j;
00262   for (j = 0; j < aByteArray->length; j++)
00263     {
00264       result[j] = isalnum (aByteArray->bytes[j]) ? aByteArray->bytes[j] : '.';
00265     }
00266   result[aByteArray->length] = '\0';
00267 
00268   return result;
00269 }
00270 
00271 
00272 /**
00273   * \brief  Code for building BDD of TR for an fsm
00274   * 
00275   */
00276 
00277 static int
00278 fsmPrintBlifLogEncode (Evl_Fsm_t * fsm)
00279 {
00280   int i;
00281   int j;
00282   int k, l, b;
00283 
00284   printf ("BDD: entering LogEncode\n");
00285 
00286   int stateCount = fsm->N;
00287 
00288   double u = log10 ((double) fsm->N);
00289   double v = log10 ((double) 2.0);
00290   double w = (double) ((double) u / (double) v);
00291   int numRegs = (int) (ceil (w));
00292 
00293   int numInputValues = fsm->numInputValues;
00294   u = log10 ((double) numInputValues);
00295   v = log10 ((double) 2.0);
00296   w = (double) ((double) u / (double) v);
00297   int numInputBits = (int) (ceil (w));
00298 
00299 
00300   bdd_t *t1;
00301   bdd_t *t2;
00302   bdd_t *cube;
00303   bdd_manager *manager = bdd_start (numRegs + numInputBits);
00304 
00305   printf ("# BDD FSM has %d states, using %d registers for log coding\n",
00306       stateCount, numRegs);
00307 
00308   printf ("\n.inputs ");
00309   for (i = 0; i < numInputBits; i++)
00310     {
00311       printf ("in_%d ", i);
00312     }
00313   printf ("\n.outputs ");
00314   for (i = 0; i < numRegs; i++)
00315     {
00316       printf ("ns_%d ", i);
00317     }
00318   printf ("\n\n");
00319 
00320   array_t **prevStateArray =
00321     (array_t **) malloc (fsm->N * sizeof (array_t *));
00322   for (i = 0; i < fsm->N; i++)
00323     {
00324       prevStateArray[i] = array_alloc (int, 0);
00325     }
00326 
00327   for (i = 0; i < fsm->N; i++)
00328     {
00329       for (j = 0; j < fsm->N; j++)
00330     {
00331       for (k = 0; k < numInputValues; k++)
00332         {
00333           if (fsm->nextStateFunction[j * fsm->numInputValues + k] == i)
00334         {
00335           array_insert_last (int, prevStateArray[i], j);
00336           array_insert_last (int, prevStateArray[i], k);
00337         }
00338         }
00339     }
00340     }
00341   // now prevStateArray[i] is an array_t of all tuples (ps, ip) which lead 
00342   // to state i
00343 
00344   printf ("BDD: now entering BDD build code\n");
00345 
00346   bdd_t **nsFunctionArray = (bdd_t **) malloc (numRegs * sizeof (bdd_t *));
00347   for (l = 0; l < numRegs; l++)
00348     {
00349 
00350       // lsb to msb then input
00351       printf (".latch ns_%d ps_%d 0\n\n", l, l);
00352       printf (".names ");
00353       for (b = 0; b < numRegs; b++)
00354     {
00355       printf ("ps_%d ", b);
00356     }
00357       for (b = 0; b < numInputBits; b++)
00358     {
00359       printf ("in_%d ", b);
00360     }
00361       printf (" ns_%d\n", l);
00362 
00363       nsFunctionArray[l] = bdd_zero (manager);
00364       for (i = 0; i < fsm->N; i++)
00365     {
00366       if ((i & (1 << l)) == 0)
00367         {
00368           continue;
00369         }
00370       for (j = 0; j < array_n (prevStateArray[i]) / 2; j++)
00371         {
00372           int prevState = array_fetch (int, prevStateArray[i], 2 * j);
00373           int input = array_fetch (int, prevStateArray[i], 2 * j + 1);
00374           cube = bdd_one (manager);
00375           for (b = 0; b < numRegs; b++)
00376         {
00377           printf ("%d", (prevState & (1 << b)) ? 1 : 0);
00378           t1 = bdd_get_variable (manager, b);
00379           if (prevState & (1 << b))
00380             {
00381               t2 = bdd_dup (t1);
00382             }
00383           else
00384             {
00385               t2 = bdd_not (t1);
00386             }
00387           bdd_free (t1);
00388           t1 = bdd_and (cube, t2, 1, 1);
00389           bdd_free (t2);
00390           bdd_free (cube);
00391           cube = t1;
00392         }
00393           for (b = 0; b < numInputBits; b++)
00394         {
00395           // printf("%d", ( input & ( 1 << b ) ) ? 1 : 0 );
00396           t1 = bdd_get_variable (manager, numRegs + b);
00397           if (input & (1 << b))
00398             {
00399               t2 = bdd_dup (t1);
00400             }
00401           else
00402             {
00403               t2 = bdd_not (t1);
00404             }
00405           bdd_free (t1);
00406           t1 = bdd_and (cube, t2, 1, 1);
00407           bdd_free (t2);
00408           bdd_free (cube);
00409           cube = t1;
00410         }
00411           // printf(" 1\n");
00412           t2 = bdd_or (cube, nsFunctionArray[l], 1, 1);
00413           bdd_free (cube);
00414           bdd_free (nsFunctionArray[l]);
00415           nsFunctionArray[l] = t2;
00416         }
00417     }
00418       printf ("BDD size for nsFunctionArray[%d] is %d\n",
00419           l, bdd_size (nsFunctionArray[l]));
00420       printf ("\n\n# end .names\n\n");
00421 
00422       cube = bdd_one (manager);
00423       for (i = 0; i < numRegs; i++)
00424     {
00425       t1 = bdd_get_variable (manager, i);
00426       t2 = (i % 2) ? bdd_dup (t1) : bdd_not (t1);
00427       // t2 = bdd_not( t1 ) ;
00428       bdd_free (t1);
00429       t1 = bdd_and (t2, cube, 1, 1);
00430       bdd_free (t2);
00431       bdd_free (cube);
00432       cube = t1;
00433     }
00434       t1 = bdd_cofactor (nsFunctionArray[l], cube);
00435       if (!bdd_is_tautology (t1, 0))
00436     {
00437       printf ("We got a live one!\n");
00438     }
00439       array_t *tmpArray = array_alloc (bdd_t *, 0);
00440       for (i = 0; i < numRegs + numInputBits; i++)
00441     {
00442       array_insert_last (bdd_t *, tmpArray,
00443                  bdd_get_variable (manager, i));
00444     }
00445     }
00446 
00447   printf ("\n.end\n");
00448 
00449   bdd_t *TR = bdd_one (manager);
00450   for (l = 0; l < numRegs; l++)
00451     {
00452       printf ("TR BDD size is %d\n", bdd_size (TR));
00453       bdd_t *nextStateVarBdd =
00454     bdd_get_variable (manager, numRegs + numInputBits + l);
00455       bdd_t *nextStateRelation =
00456     bdd_xnor (nextStateVarBdd, nsFunctionArray[l]);
00457       bdd_free (nextStateVarBdd);
00458       t1 = bdd_and (TR, nextStateRelation, 1, 1);
00459       bdd_free (TR);
00460       bdd_free (nextStateRelation);
00461       TR = t1;
00462     }
00463   printf ("TR BDD final size is %d\n", bdd_size (TR));
00464 
00465   st_table *computedTable = Hash_InitTable ( ( int(*)()) Evl_BddCmp,  ( int(*)()) Evl_BddHash);
00466   int *countArray = (int *) calloc (bdd_num_vars (manager), (sizeof (int)));
00467   computeIndexCount (TR, computedTable, countArray);
00468   for (i = 0; i < (int) bdd_num_vars (manager); i++)
00469     {
00470       printf ("Level %d has BDD %d nodes\n", i, countArray[i]);
00471     }
00472 
00473   cube = bdd_one (manager);
00474   array_t *ps_vars = array_alloc (bdd_t *, 0);
00475   array_t *ns_vars = array_alloc (bdd_t *, 0);
00476   array_t *smoothingArray = array_alloc (bdd_t *, 0);
00477   for (l = 0; l < numRegs; l++)
00478     {
00479       t1 = bdd_get_variable (manager, l);
00480       t2 = bdd_get_variable (manager, numRegs + numInputBits + l);
00481       array_insert_last (bdd_t *, ps_vars, t1);
00482       array_insert_last (bdd_t *, smoothingArray, t1);
00483       array_insert_last (bdd_t *, ns_vars, t2);
00484       // t2 = bdd_not( t1 );
00485       t2 = (i % 2) ? bdd_dup (t1) : bdd_not (t1);
00486       t1 = bdd_and (t2, cube, 1, 1);
00487       bdd_free (cube);
00488       cube = t1;
00489     }
00490   for (l = 0; l < numInputBits; l++)
00491     {
00492       t1 = bdd_get_variable (manager, numRegs + l);
00493       array_insert_last (bdd_t *, smoothingArray, t1);
00494     }
00495 
00496   bdd_t *A0 = bdd_zero (manager);
00497   bdd_t *A1 = cube;
00498   printf ("Printing initial state BDD\n");
00499   bdd_print (A1);
00500 
00501   printf ("Trying cofactor of TR by initial state\n");
00502   t1 = bdd_cofactor (TR, A1);
00503   bdd_print (t1);
00504 
00505   i = 0;
00506   while (!bdd_equal (A0, A1))
00507     {
00508       i++;
00509       printf ("Iteation %d: There are %.0f minterms in the \
00510 BDD reached state set\n", i, bdd_count_onset (A1, ps_vars));
00511       bdd_free (A0);
00512       A0 = A1;
00513       t1 = bdd_and_smooth (TR, A1, smoothingArray);
00514       t2 = bdd_substitute (t1, ns_vars, ps_vars);
00515       A1 = bdd_or (A1, t2, 1, 1);
00516       bdd_free (t2);
00517       bdd_free (t1);
00518     }
00519 
00520   return 1;
00521 }
00522 
00523 
00524 /**
00525   * \brief  Compute the number of nodes on each level of a BDD
00526   * 
00527   */
00528 
00529 static int
00530 computeIndexCount (bdd_t * aBdd, st_table * computedTable, int *countArray)
00531 {
00532   if (bdd_is_tautology (aBdd, 0) || bdd_is_tautology (aBdd, 1))
00533     {
00534       return 0;
00535     }
00536   if (Hash_Lookup (computedTable, (char *) aBdd, 0))
00537     {
00538       return 0;
00539     }
00540   Hash_Insert (computedTable, (char *) aBdd, 0);
00541   int id = bdd_top_var_id (aBdd);
00542   countArray[id]++;
00543   computeIndexCount (bdd_then (aBdd), computedTable, countArray);
00544   computeIndexCount (bdd_else (aBdd), computedTable, countArray);
00545 
00546   return 0;
00547 }
00548 
00549 
00550 /**
00551   * \brief  Function to be called on hitting an accepting state
00552   * 
00553   */
00554 
00555 int
00556 Evl_FsmProcessAcceptingState (Evl_Fsm_t * fsm,
00557                   u_int32_t ps,
00558                   st_table * stringToId,
00559                   array_t * idToRules,
00560                   var_set_t * set1,
00561                   var_set_t * set2,
00562                   var_set_t * set3, array_t * resultPtr)
00563 {
00564   int j, k;
00565   array_t *finalStateArray = array_fetch (array_t *, fsm->finalStates, ps);
00566   for (j = 0; j < array_n (finalStateArray); j++)
00567     {
00568       int stringId = array_fetch (int, finalStateArray, j);
00569       util_byte_array_t *tmp = fsm->stateIdToPrefix[stringId];
00570       int contentId;
00571       bool found = Hash_Lookup (stringToId, (char *) tmp, (char **) &contentId);
00572       assert (found);
00573       array_t *rulesForThisString =
00574     array_fetch (array_t *, idToRules, contentId);
00575       int numRulesForThisString = array_n (rulesForThisString);
00576       for (k = 0; k < numRulesForThisString; k++)
00577     {
00578       int ruleId = array_fetch (int, rulesForThisString, k);
00579       if ((set1 && var_set_get_elt (set1, ruleId)) ||
00580           (set2 && var_set_get_elt (set2, ruleId)) ||
00581           (set3 && var_set_get_elt (set3, ruleId)))
00582         {
00583           array_insert_last (int, resultPtr, ruleId);
00584         }
00585     }
00586     }
00587   return 0;
00588 }
00589 
00590 
00591 /**
00592   * \brief  Simulate an FSM on a given string.  Return 
00593   * a hash table of strings that occurred, and where
00594   * they most recently occured.
00595   *
00596   *     Checks are case-insensitive, to merge the checks for
00597   * case-specific and case-insensitive strings.  In the final
00598   * check using evalContentCheck this is resolved - the FSM search
00599   * merely serves as a pre-processor.
00600   * 
00601   * \arg idToRules is an 
00602   * array of ints that has length at least equal to the
00603   * number of rules.
00604   */
00605 
00606 // int foo=0;
00607 // int bar=0;
00608 // int widget=0;
00609 
00610 void
00611 Evl_FsmComputeRules (Evl_Fsm_t * fsm,
00612              st_table * stringToId,
00613              array_t * idToRules,
00614              var_set_t * set1,
00615              var_set_t * set2,
00616              var_set_t * set3,
00617              char *payload, int length, array_t * result)
00618 {
00619   if (length == 0)
00620     {
00621       return;
00622     }
00623 
00624   int initialState = fsm->numStrings;
00625   register u_int16_t *nextStateFunction = fsm->nextStateFunction;
00626   register u_int8_t *finalStatesVarSet = fsm->finalStatesVarSet;
00627   register u_int32_t psLong = initialState;
00628   register u_int32_t aByteLong;
00629   u_int8_t *payloadReg = (u_int8_t *) payload;
00630   register int lengthReg = length;
00631   register int i;
00632 
00633   for (i = 0; i < lengthReg; i++)
00634     {
00635       // fsm->stateCount[psLong]++;
00636 
00637       // saves ~10% to use an array of u_int8_t rather than 
00638       // a bit vector
00639 
00640       // strangely, it saves about 25% (14.88 to 11.36) to change
00641       // test from if ( fsm->finalStatesVarSet[ps] )
00642       // to the test below: (something to do with unsigned?)
00643       // note - this issue seems to have gone away with 
00644       // the various changes made to the code
00645 
00646       // saves 5% to break the following line:
00647       // ps = nextStateFunction[ ( ps << 8) + (u_int8_t) payload[i] ];
00648     label2:
00649       psLong = psLong << 8;
00650       aByteLong = payloadReg[i];
00651       if (my_isupper (aByteLong))
00652     {
00653       aByteLong = my_uppertolower (aByteLong);
00654     }
00655       psLong = psLong + aByteLong;
00656       psLong = nextStateFunction[psLong];
00657       // perform check here, since otherwise miss the case
00658       // where string terminates in an accepting state
00659       if (finalStatesVarSet[psLong] == 1)
00660     {
00661 
00662       // with the increment to foo rather than
00663       // the more complex code for walking through
00664       // the finalStateArray, and its associated
00665       // strings performance is much better (17.5 vs 11.8)
00666       //
00667       // i am guessing this is because the icache doesnt have
00668       // enough space for the loop.  
00669       // moving the complex code to a goto has the following effect
00670       // if the code is commented out of the goto,
00671       // we take 10.92 sec; with the full code in the goto it takes 
00672       //  17.41 secs 
00673       // 
00674       // this is quite puzzling, since we never see an accepting
00675       // state!
00676       // printf("Hit accepting state\n");
00677 
00678       goto label1;
00679       // there are dictionary strings associated with this state
00680     }           // if 
00681     }               // for 
00682 
00683   return;
00684   // return result;
00685 
00686 label1:
00687   // foo++;
00688   Evl_FsmProcessAcceptingState (fsm, psLong, stringToId, idToRules, set1,
00689                 set2, set3, result);
00690   // with a nested loop, performance goes from 11.63 to 18.25
00691   // for ( k = 0 ; k < ps ; k++ ) {
00692   //    for ( j = 0 ; j < foo; j++ ) {
00693   //     mybar+= ps - k  + j ;
00694   //    }
00695   // }
00696   // with the goto below, time is 11.637072
00697   // without it, it's 17.42  
00698   // goto label2;
00699 
00700   goto label2;
00701 }
00702 
00703 
00704 /**
00705   * \brief  Traverse the state of an FSM and see which should
00706   * be treated as special, i.e., corresponding to 
00707   * states where a string in the given set should be accepted.
00708   * 
00709   */
00710 
00711 static int
00712 computeAcceptingStates (Evl_Fsm_t * fsm)
00713 {
00714   int i, j;
00715   util_byte_array_t *givenString, *state_j;
00716 
00717   for (i = 0; i < fsm->numStrings; i++)
00718     {
00719       for (j = 0; j < fsm->N; j++)
00720     {
00721       givenString = fsm->stateIdToPrefix[i];
00722       state_j = fsm->stateIdToPrefix[j];
00723       if (givenString->length > state_j->length)
00724         {
00725           continue;
00726         }
00727 
00728       if (0 ==
00729           memcmp (givenString->bytes,
00730               state_j->bytes + (state_j->length -
00731                     givenString->length),
00732               givenString->length))
00733         {
00734           // state with id j accepts givenString, whose id is i
00735           array_t *acceptedStrings =
00736         array_fetch (array_t *, fsm->finalStates, j);
00737           if (acceptedStrings == NIL (array_t))
00738         {
00739           acceptedStrings = array_alloc (int, 0);
00740           array_insert (array_t *, fsm->finalStates, j,
00741                 acceptedStrings);
00742           // var_set_set_elt( fsm->finalStatesVarSet, j );
00743           fsm->finalStatesVarSet[j] = 1;
00744         }
00745           array_insert_last (int, acceptedStrings, i);
00746         }
00747     }
00748     }
00749   return 0;
00750 }