evlFsm.c

Go to the documentation of this file.

/** \file evlFsm.c


  \brief    Build an FSM from a collection of rules

******************************************************************************/

#include "nm.h"
#include "evl.h"

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static int maxPrefixSuffixOverlap (char *aString, char *bString);
static char *byteArrayToString (util_byte_array_t * aByteArray);
static int fsmPrintBlifLogEncode (Evl_Fsm_t * fsm);
static int computeIndexCount (bdd_t * aBdd, st_table * computedTable,
                  int *countArray);
static int computeAcceptingStates (Evl_Fsm_t * fsm);

/**AutomaticEnd***************************************************************/

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


/**
  * \brief  Compute the length of the longest prefix of aString
  * that's a suffix of bString.
  */

static int
maxPrefixSuffixOverlap (char *aString, char *bString)
{
  int i;
  int N = strlen (bString);
  int maxOverlap = 0;
  // printf("a = %s, b = %s ; N (strlen bString ) = %d\n" , aString, bString, N );
  for (i = 1; i < N; i++)
    {
      if (util_strequalN (aString, bString + N - i, i))
    {
      maxOverlap = i;
      // printf("Got an overlap of length %d\n", i);
    }
      else
    {
      // printf("No overlap of length %d\n", i);
    }
    }
  return maxOverlap;
}


/**
  * \brief  Build a prefix automaton for a set of byte arrays.
  */

Evl_Fsm_t *
Evl_BuildPrefixAutomaton (array_t * byteArrayArray)
{
  Evl_Fsm_t *resultFsm = (Evl_Fsm_t *) malloc (sizeof (Evl_Fsm_t));
  char tmpBuf[1000];

  st_table *prefixHash =
    Hash_InitTable ( ( int(*)()) util_byte_array_cmp,  ( int(*)()) util_byte_array_hash);

  int i, j;
  util_byte_array_t *aByteArray;
  for (i = 0; i < array_n (byteArrayArray); i++)
    {
      aByteArray = array_fetch (util_byte_array_t *, byteArrayArray, i);
      // full strings are id'd by their position in the array passed in
      Hash_Insert (prefixHash, (char *) aByteArray, (char *) i);
    }

  int tmpState;

  util_byte_array_t *tmp1 =
    (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
  util_byte_array_t *tmp2;

  util_byte_array_t *prefix =
    (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
  util_byte_array_t *suffix =
    (util_byte_array_t *) malloc (sizeof (util_byte_array_t));

  for (i = 0; i < array_n (byteArrayArray); i++)
    {
      aByteArray = array_fetch (util_byte_array_t *, byteArrayArray, i);
      for (j = 0; j < aByteArray->length; j++)
    {
      tmp1->bytes = aByteArray->bytes;
      tmp1->length = j;
      if (Hash_Lookup (prefixHash, (char *) tmp1, (char **) 0))
        {
          continue;
        }
      else
        {
          tmp2 =
        (util_byte_array_t *) malloc (sizeof (util_byte_array_t));
          tmp2->bytes = aByteArray->bytes;
          tmp2->length = j;
          tmpState = st_count (prefixHash);
          Hash_Insert (prefixHash, (char *) tmp2, (char *) tmpState);
        }
    }
    }
  st_generator *stGen;
  int numStates = st_count (prefixHash);
  resultFsm->stateIdToPrefix =
    (util_byte_array_t **) malloc (numStates * sizeof (util_byte_array_t *));
  st_foreach_item (prefixHash, stGen, (char **) &prefix, (char **) &tmpState)
  {
    resultFsm->stateIdToPrefix[tmpState] = prefix;
  }

  const int numInputValues = 256;
  // trying to align on 64 byte addresses
  // remember to add to fsm struct so we can free it later
  u_int16_t *transitionTableRaw =
    (u_int16_t *) malloc (numInputValues * numStates * sizeof (u_int16_t) +
              64);
  u_int16_t *transitionTable =
    (u_int16_t
     *) ((char *) ((((u_int32_t) transitionTableRaw) & ~(u_int32_t) 0x3f)) +
     64);
  for (i = 0; i < numStates; i++)
    {
      for (j = 0; j < numInputValues; j++)
    {
      transitionTable[numInputValues * i + j] = -1;
    }
    }

  int aState;
  for (aState = 0; aState < numStates; aState++)
    {
      prefix = resultFsm->stateIdToPrefix[aState];
      int prefixLength = prefix->length;
      memcpy (tmpBuf, prefix->bytes, prefixLength);
      unsigned char aChar;
      int l;
      for (l = 0; l < numInputValues; l++)
    {
      aChar = l;
      tmpBuf[prefixLength] = aChar;
      int nextState = -1;
      int k;
      for (k = 0; k <= prefixLength + 1; k++)
        {
          suffix->bytes = &tmpBuf[prefixLength + 1 - k];
          suffix->length = k;
          if (Hash_Lookup
          (prefixHash, (char *) suffix, (char **) &tmpState))
        {
          nextState = tmpState;
        }
        }
      assert (nextState != -1);
      transitionTable[aState * numInputValues + l] = nextState;
    }
    }

  resultFsm->N = numStates;
  resultFsm->stateCount = (int *) calloc (sizeof (int), numStates);
  resultFsm->numStrings = array_n (byteArrayArray);
  resultFsm->nextStateFunction = transitionTable;
  resultFsm->numInputValues = numInputValues;
  resultFsm->prefixHash = prefixHash;

  resultFsm->finalStates = array_alloc (array_t *, numStates);
  // resultFsm->finalStatesVarSet = var_set_new( numStates );
  char *finalStatesVarSetRaw = (char *) calloc (numStates + 64, sizeof (u_int8_t));
  // trying to align pointers on 64 byte bndries
  // remember to free appropriately
  resultFsm->finalStatesVarSet =
    ((((u_int8_t *) ((u_int32_t) finalStatesVarSetRaw & ~(u_int32_t) 0x3f))) +
     64);
  for (i = 0; i < numStates; i++)
    {
      array_insert (array_t *, resultFsm->finalStates, i, NIL (array_t));
    }
  computeAcceptingStates (resultFsm);

  return resultFsm;

}


/**
  * \brief  Print an FSM, meant for debugging purposes
  */

int
Evl_FsmPrint (Evl_Fsm_t * anFsm)
{
  int i, k;

  printf ("Number of strings = %d, number of states = %d\n",
      anFsm->numStrings, anFsm->N);
  util_byte_array_t **sortedStrings =
    (util_byte_array_t **) malloc (anFsm->N * sizeof (util_byte_array_t *));
  for (i = 0; i < anFsm->N; i++)
    {
      sortedStrings[i] = anFsm->stateIdToPrefix[i];
    }
  // qsort(sortedStrings, anFsm->N, sizeof(util_byte_array_t *), util_byte_array_cmp );
  int tmpState;
  printf ("Printing all states:\n");
  for (i = 0; i < anFsm->N; i++)
    {
      printf ("\tstate %d = %s\n", i,
          byteArrayToString (anFsm->stateIdToPrefix[i]));
    }
  printf ("Printing transition table:\n");
  for (i = 0; i < anFsm->N; i++)
    {
      Hash_Lookup (anFsm->prefixHash, (char *) sortedStrings[i],
         (char **) &tmpState);
      printf ("Printing transitions out of state %d\n", tmpState);
      printf ("\twhich is: %s\n", byteArrayToString (sortedStrings[i]));
      printf ("\n");
      for (k = 0; k < 256; k++)
    {
      if (anFsm->
          nextStateFunction[tmpState * anFsm->numInputValues + k] !=
          anFsm->numStrings)
        {
          // anFsm->numStrings is the initial state (assuming \epsilon is not
          // a valid string
          printf ("%s goes to %s on %c\n",
              byteArrayToString (anFsm->stateIdToPrefix[tmpState]),
              byteArrayToString (anFsm->
                     stateIdToPrefix[anFsm->
                             nextStateFunction
                             [tmpState *
                              anFsm->
                              numInputValues +
                              k]]), k);
        }
    }
    }
  return 0;
}


/**
  * \brief  Return a string encoding a byte array - replace non printable chars by .
  */

static char *
byteArrayToString (util_byte_array_t * aByteArray)
{
  char *result = (char *) malloc (sizeof (char) * aByteArray->length + 1);
  int j;
  for (j = 0; j < aByteArray->length; j++)
    {
      result[j] = isalnum (aByteArray->bytes[j]) ? aByteArray->bytes[j] : '.';
    }
  result[aByteArray->length] = '\0';

  return result;
}


/**
  * \brief  Code for building BDD of TR for an fsm
  * 
  */

static int
fsmPrintBlifLogEncode (Evl_Fsm_t * fsm)
{
  int i;
  int j;
  int k, l, b;

  printf ("BDD: entering LogEncode\n");

  int stateCount = fsm->N;

  double u = log10 ((double) fsm->N);
  double v = log10 ((double) 2.0);
  double w = (double) ((double) u / (double) v);
  int numRegs = (int) (ceil (w));

  int numInputValues = fsm->numInputValues;
  u = log10 ((double) numInputValues);
  v = log10 ((double) 2.0);
  w = (double) ((double) u / (double) v);
  int numInputBits = (int) (ceil (w));


  bdd_t *t1;
  bdd_t *t2;
  bdd_t *cube;
  bdd_manager *manager = bdd_start (numRegs + numInputBits);

  printf ("# BDD FSM has %d states, using %d registers for log coding\n",
      stateCount, numRegs);

  printf ("\n.inputs ");
  for (i = 0; i < numInputBits; i++)
    {
      printf ("in_%d ", i);
    }
  printf ("\n.outputs ");
  for (i = 0; i < numRegs; i++)
    {
      printf ("ns_%d ", i);
    }
  printf ("\n\n");

  array_t **prevStateArray =
    (array_t **) malloc (fsm->N * sizeof (array_t *));
  for (i = 0; i < fsm->N; i++)
    {
      prevStateArray[i] = array_alloc (int, 0);
    }

  for (i = 0; i < fsm->N; i++)
    {
      for (j = 0; j < fsm->N; j++)
    {
      for (k = 0; k < numInputValues; k++)
        {
          if (fsm->nextStateFunction[j * fsm->numInputValues + k] == i)
        {
          array_insert_last (int, prevStateArray[i], j);
          array_insert_last (int, prevStateArray[i], k);
        }
        }
    }
    }
  // now prevStateArray[i] is an array_t of all tuples (ps, ip) which lead 
  // to state i

  printf ("BDD: now entering BDD build code\n");

  bdd_t **nsFunctionArray = (bdd_t **) malloc (numRegs * sizeof (bdd_t *));
  for (l = 0; l < numRegs; l++)
    {

      // lsb to msb then input
      printf (".latch ns_%d ps_%d 0\n\n", l, l);
      printf (".names ");
      for (b = 0; b < numRegs; b++)
    {
      printf ("ps_%d ", b);
    }
      for (b = 0; b < numInputBits; b++)
    {
      printf ("in_%d ", b);
    }
      printf (" ns_%d\n", l);

      nsFunctionArray[l] = bdd_zero (manager);
      for (i = 0; i < fsm->N; i++)
    {
      if ((i & (1 << l)) == 0)
        {
          continue;
        }
      for (j = 0; j < array_n (prevStateArray[i]) / 2; j++)
        {
          int prevState = array_fetch (int, prevStateArray[i], 2 * j);
          int input = array_fetch (int, prevStateArray[i], 2 * j + 1);
          cube = bdd_one (manager);
          for (b = 0; b < numRegs; b++)
        {
          printf ("%d", (prevState & (1 << b)) ? 1 : 0);
          t1 = bdd_get_variable (manager, b);
          if (prevState & (1 << b))
            {
              t2 = bdd_dup (t1);
            }
          else
            {
              t2 = bdd_not (t1);
            }
          bdd_free (t1);
          t1 = bdd_and (cube, t2, 1, 1);
          bdd_free (t2);
          bdd_free (cube);
          cube = t1;
        }
          for (b = 0; b < numInputBits; b++)
        {
          // printf("%d", ( input & ( 1 << b ) ) ? 1 : 0 );
          t1 = bdd_get_variable (manager, numRegs + b);
          if (input & (1 << b))
            {
              t2 = bdd_dup (t1);
            }
          else
            {
              t2 = bdd_not (t1);
            }
          bdd_free (t1);
          t1 = bdd_and (cube, t2, 1, 1);
          bdd_free (t2);
          bdd_free (cube);
          cube = t1;
        }
          // printf(" 1\n");
          t2 = bdd_or (cube, nsFunctionArray[l], 1, 1);
          bdd_free (cube);
          bdd_free (nsFunctionArray[l]);
          nsFunctionArray[l] = t2;
        }
    }
      printf ("BDD size for nsFunctionArray[%d] is %d\n",
          l, bdd_size (nsFunctionArray[l]));
      printf ("\n\n# end .names\n\n");

      cube = bdd_one (manager);
      for (i = 0; i < numRegs; i++)
    {
      t1 = bdd_get_variable (manager, i);
      t2 = (i % 2) ? bdd_dup (t1) : bdd_not (t1);
      // t2 = bdd_not( t1 ) ;
      bdd_free (t1);
      t1 = bdd_and (t2, cube, 1, 1);
      bdd_free (t2);
      bdd_free (cube);
      cube = t1;
    }
      t1 = bdd_cofactor (nsFunctionArray[l], cube);
      if (!bdd_is_tautology (t1, 0))
    {
      printf ("We got a live one!\n");
    }
      array_t *tmpArray = array_alloc (bdd_t *, 0);
      for (i = 0; i < numRegs + numInputBits; i++)
    {
      array_insert_last (bdd_t *, tmpArray,
                 bdd_get_variable (manager, i));
    }
    }

  printf ("\n.end\n");

  bdd_t *TR = bdd_one (manager);
  for (l = 0; l < numRegs; l++)
    {
      printf ("TR BDD size is %d\n", bdd_size (TR));
      bdd_t *nextStateVarBdd =
    bdd_get_variable (manager, numRegs + numInputBits + l);
      bdd_t *nextStateRelation =
    bdd_xnor (nextStateVarBdd, nsFunctionArray[l]);
      bdd_free (nextStateVarBdd);
      t1 = bdd_and (TR, nextStateRelation, 1, 1);
      bdd_free (TR);
      bdd_free (nextStateRelation);
      TR = t1;
    }
  printf ("TR BDD final size is %d\n", bdd_size (TR));

  st_table *computedTable = Hash_InitTable ( ( int(*)()) Evl_BddCmp,  ( int(*)()) Evl_BddHash);
  int *countArray = (int *) calloc (bdd_num_vars (manager), (sizeof (int)));
  computeIndexCount (TR, computedTable, countArray);
  for (i = 0; i < (int) bdd_num_vars (manager); i++)
    {
      printf ("Level %d has BDD %d nodes\n", i, countArray[i]);
    }

  cube = bdd_one (manager);
  array_t *ps_vars = array_alloc (bdd_t *, 0);
  array_t *ns_vars = array_alloc (bdd_t *, 0);
  array_t *smoothingArray = array_alloc (bdd_t *, 0);
  for (l = 0; l < numRegs; l++)
    {
      t1 = bdd_get_variable (manager, l);
      t2 = bdd_get_variable (manager, numRegs + numInputBits + l);
      array_insert_last (bdd_t *, ps_vars, t1);
      array_insert_last (bdd_t *, smoothingArray, t1);
      array_insert_last (bdd_t *, ns_vars, t2);
      // t2 = bdd_not( t1 );
      t2 = (i % 2) ? bdd_dup (t1) : bdd_not (t1);
      t1 = bdd_and (t2, cube, 1, 1);
      bdd_free (cube);
      cube = t1;
    }
  for (l = 0; l < numInputBits; l++)
    {
      t1 = bdd_get_variable (manager, numRegs + l);
      array_insert_last (bdd_t *, smoothingArray, t1);
    }

  bdd_t *A0 = bdd_zero (manager);
  bdd_t *A1 = cube;
  printf ("Printing initial state BDD\n");
  bdd_print (A1);

  printf ("Trying cofactor of TR by initial state\n");
  t1 = bdd_cofactor (TR, A1);
  bdd_print (t1);

  i = 0;
  while (!bdd_equal (A0, A1))
    {
      i++;
      printf ("Iteation %d: There are %.0f minterms in the \
BDD reached state set\n", i, bdd_count_onset (A1, ps_vars));
      bdd_free (A0);
      A0 = A1;
      t1 = bdd_and_smooth (TR, A1, smoothingArray);
      t2 = bdd_substitute (t1, ns_vars, ps_vars);
      A1 = bdd_or (A1, t2, 1, 1);
      bdd_free (t2);
      bdd_free (t1);
    }

  return 1;
}


/**
  * \brief  Compute the number of nodes on each level of a BDD
  * 
  */

static int
computeIndexCount (bdd_t * aBdd, st_table * computedTable, int *countArray)
{
  if (bdd_is_tautology (aBdd, 0) || bdd_is_tautology (aBdd, 1))
    {
      return 0;
    }
  if (Hash_Lookup (computedTable, (char *) aBdd, 0))
    {
      return 0;
    }
  Hash_Insert (computedTable, (char *) aBdd, 0);
  int id = bdd_top_var_id (aBdd);
  countArray[id]++;
  computeIndexCount (bdd_then (aBdd), computedTable, countArray);
  computeIndexCount (bdd_else (aBdd), computedTable, countArray);

  return 0;
}


/**
  * \brief  Function to be called on hitting an accepting state
  * 
  */

int
Evl_FsmProcessAcceptingState (Evl_Fsm_t * fsm,
                  u_int32_t ps,
                  st_table * stringToId,
                  array_t * idToRules,
                  var_set_t * set1,
                  var_set_t * set2,
                  var_set_t * set3, array_t * resultPtr)
{
  int j, k;
  array_t *finalStateArray = array_fetch (array_t *, fsm->finalStates, ps);
  for (j = 0; j < array_n (finalStateArray); j++)
    {
      int stringId = array_fetch (int, finalStateArray, j);
      util_byte_array_t *tmp = fsm->stateIdToPrefix[stringId];
      int contentId;
      bool found = Hash_Lookup (stringToId, (char *) tmp, (char **) &contentId);
      assert (found);
      array_t *rulesForThisString =
    array_fetch (array_t *, idToRules, contentId);
      int numRulesForThisString = array_n (rulesForThisString);
      for (k = 0; k < numRulesForThisString; k++)
    {
      int ruleId = array_fetch (int, rulesForThisString, k);
      if ((set1 && var_set_get_elt (set1, ruleId)) ||
          (set2 && var_set_get_elt (set2, ruleId)) ||
          (set3 && var_set_get_elt (set3, ruleId)))
        {
          array_insert_last (int, resultPtr, ruleId);
        }
    }
    }
  return 0;
}


/**
  * \brief  Simulate an FSM on a given string.  Return 
  * a hash table of strings that occurred, and where
  * they most recently occured.
  *
  *     Checks are case-insensitive, to merge the checks for
  * case-specific and case-insensitive strings.  In the final
  * check using evalContentCheck this is resolved - the FSM search
  * merely serves as a pre-processor.
  * 
  * \arg idToRules is an 
  * array of ints that has length at least equal to the
  * number of rules.
  */

// int foo=0;
// int bar=0;
// int widget=0;

void
Evl_FsmComputeRules (Evl_Fsm_t * fsm,
             st_table * stringToId,
             array_t * idToRules,
             var_set_t * set1,
             var_set_t * set2,
             var_set_t * set3,
             char *payload, int length, array_t * result)
{
  if (length == 0)
    {
      return;
    }

  int initialState = fsm->numStrings;
  register u_int16_t *nextStateFunction = fsm->nextStateFunction;
  register u_int8_t *finalStatesVarSet = fsm->finalStatesVarSet;
  register u_int32_t psLong = initialState;
  register u_int32_t aByteLong;
  u_int8_t *payloadReg = (u_int8_t *) payload;
  register int lengthReg = length;
  register int i;

  for (i = 0; i < lengthReg; i++)
    {
      // fsm->stateCount[psLong]++;

      // saves ~10% to use an array of u_int8_t rather than 
      // a bit vector

      // strangely, it saves about 25% (14.88 to 11.36) to change
      // test from if ( fsm->finalStatesVarSet[ps] )
      // to the test below: (something to do with unsigned?)
      // note - this issue seems to have gone away with 
      // the various changes made to the code

      // saves 5% to break the following line:
      // ps = nextStateFunction[ ( ps << 8) + (u_int8_t) payload[i] ];
    label2:
      psLong = psLong << 8;
      aByteLong = payloadReg[i];
      if (my_isupper (aByteLong))
    {
      aByteLong = my_uppertolower (aByteLong);
    }
      psLong = psLong + aByteLong;
      psLong = nextStateFunction[psLong];
      // perform check here, since otherwise miss the case
      // where string terminates in an accepting state
      if (finalStatesVarSet[psLong] == 1)
    {

      // with the increment to foo rather than
      // the more complex code for walking through
      // the finalStateArray, and its associated
      // strings performance is much better (17.5 vs 11.8)
      //
      // i am guessing this is because the icache doesnt have
      // enough space for the loop.  
      // moving the complex code to a goto has the following effect
      // if the code is commented out of the goto,
      // we take 10.92 sec; with the full code in the goto it takes 
      //  17.41 secs 
      // 
      // this is quite puzzling, since we never see an accepting
      // state!
      // printf("Hit accepting state\n");

      goto label1;
      // there are dictionary strings associated with this state
    }           // if 
    }               // for 

  return;
  // return result;

label1:
  // foo++;
  Evl_FsmProcessAcceptingState (fsm, psLong, stringToId, idToRules, set1,
                set2, set3, result);
  // with a nested loop, performance goes from 11.63 to 18.25
  // for ( k = 0 ; k < ps ; k++ ) {
  //    for ( j = 0 ; j < foo; j++ ) {
  //     mybar+= ps - k  + j ;
  //    }
  // }
  // with the goto below, time is 11.637072
  // without it, it's 17.42  
  // goto label2;

  goto label2;
}


/**
  * \brief  Traverse the state of an FSM and see which should
  * be treated as special, i.e., corresponding to 
  * states where a string in the given set should be accepted.
  * 
  */

static int
computeAcceptingStates (Evl_Fsm_t * fsm)
{
  int i, j;
  util_byte_array_t *givenString, *state_j;

  for (i = 0; i < fsm->numStrings; i++)
    {
      for (j = 0; j < fsm->N; j++)
    {
      givenString = fsm->stateIdToPrefix[i];
      state_j = fsm->stateIdToPrefix[j];
      if (givenString->length > state_j->length)
        {
          continue;
        }

      if (0 ==
          memcmp (givenString->bytes,
              state_j->bytes + (state_j->length -
                    givenString->length),
              givenString->length))
        {
          // state with id j accepts givenString, whose id is i
          array_t *acceptedStrings =
        array_fetch (array_t *, fsm->finalStates, j);
          if (acceptedStrings == NIL (array_t))
        {
          acceptedStrings = array_alloc (int, 0);
          array_insert (array_t *, fsm->finalStates, j,
                acceptedStrings);
          // var_set_set_elt( fsm->finalStatesVarSet, j );
          fsm->finalStatesVarSet[j] = 1;
        }
          array_insert_last (int, acceptedStrings, i);
        }
    }
    }
  return 0;
}