evlMgr.c

Go to the documentation of this file.

/** \file evlMgr.c

 \brief Routines for creating data structure containing everything needed to evaluate rules. 

Content searches come in several flavors:
<pre>
  - raw checks for strings (possibly a set of strings)

  - strings in specific places (or range of places)

    o these are specified using depth and offset

      + most are of the form 

        content:"HTTP/1.1 403"; depth:12 OR

        content:"|2a 02|"; offset:0; depth:2; content:"|00 04 00 06|"; offset:6; depth:4;
        which specify exactly where to look

        Note this contradicts what the manual says is the semantics
        of depth, it appears to be relative to the offset, not to the 
        start of payload. 

     + some are like
 
       content:"|01 87 8B 00 00|"; offset:40; depth:8; 

       which means look for this content string starting at 40 bytes
       into the payload, and only at locations 40 41 42 43

     + with one exception (750) no depth exceeds 128, and offsets
       are in the set {300, 200, 83, 45, 43, ... }  (the 750 and 300 are the
       same)  

   o strings that have within/distance constraints

     complete set of values: distance:0 :1 :16 :32 :4 :5 
     within:1 :100 :1024 :12 :128 :150 :2 :255 :256 :3 :4 :50 :500 :512 :600

     there are 8 rules that mix depth/offset and within/distance

     There is some confusion as to whether within/distance is anchored to 
     the START of the last match, or the end of the last match (or the
     beginning of the new match for distance)

     content:"SITE "; nocase; content:"EXEC "; distance:0;
     content:"RETR"; nocase; content:"file_id.diz"; nocase; distance:1;
     content:"|00 01 86 A0|"; content:"|00 00 00 04|"; distance:4; within:4;
     content:"From\:"; content:"<><><><><><><><><><><><><><><><><><><><><><>"; 
             distance:0; content:"("; distance:1; content:")"; distance:1; 

Some strings are very short (e.g. 1 char, and using a 
generic automaton for all strings will lead to huge 
numbers of hits in the automaton.

there are many singletons:

0x0 0x1 0x4 0x9 0x10 0x19 % & () * .  0 1 : ; > ?  @ A [ ] { | 
 
doubles:

0x0 0x0 0x0 0x1 0x0 0x2 0x-76 0x-76 0x0 0x20 00 02 03 04 0x0 # 07 ?& 
09 0x2 0x0 -- ST 20 21 22 23 24 25 70 26 71 *0x1 *0x2 0x4 0x0 / A B 
C 40 41 91 92 S ` %p 10 12 13 14 15 60 16 17 63 64 @/ @@ ..  .0 30 
31 32 33 34 35 36 =+ 37 38 39 88

triples:

0x0 0x0 0x-4 %00 911 121 FC 125 %0a %5c 0x0 0x2 0x0 %20 c:\ 0x0 
_0x2 MKD CWD B0x0 0x2 0x10 D/ !@# ~0x10 %%% 199 l44 1MB 110 PWD 
117 118 000 0x0 0x6 0x0 /%% db= /// ;id 0x0 0x1 / 130 ../ 0x0 
0x1 C 0x5 0x0 > 370 et= %1u ..\ 0x4 0x1 0x0 100 0x0 0x-53 0x0 %p 

There are several ways in which to avoid this:

  - disallow strings of length 2 or less (the prob of matching
    one of 50 random length 3 strings in a 1000 byte packet
    is < 50 * 1000 * 2^{-24} ~ 2^6 * 2^10 * 2^{-24} = 2^{-8})

  - disallow strings on length 2 or less in the first thing being checked
    then we have two automata, one for the initial strings, and if that's 
    active, we use the global automata.  

    this seems unreasonable, since we won't know the state of the 
    global automaton, unless we run from scratch.

  - allow strings of length 2 or less but only for very restricted
    checks on source/destination port.  we have a check to see if 
    the flow matches the conditions for using the "special" automaton,
    and switch to it if needed.

    more generally, we could have a seperate automaton per equivalence
    class - there are a relatively small number of classes after we
    partition.  we'll need 300 automata, each over an avg of 2 layer 4 rules,
    each of which is ~20 rules. this might be too high a memory overhead. 

    in addition we'd have 3 automata simulations to do per packet (plus
    the no case automata).
</pre>

One solution is to have for each rule, the longest string appearing in
it. Then build a table/fsm over these strings.  
Then run the payload over the table/fsm and see which strings are
present in the payload.  The specific set of strings that match is used
to find corresponding rules; each of these rules is then invoked on a 
1-by-1 basis. 

We can do pretty much the same thing - first of all determine
which rules are potentially applicable by running the automaton,
and for each matching string, seeing the rules associated with it.
We have the layer 4 information, so we can automatically do some
pruning here.

It should be pretty simple to check a single rule on a packet;
infact all we are checking is the optional checks (ttl, icmp, etc.)
The payload checks will be either a intersection of strings, or a
sequence of strings (need to check if there's also a possibility of
mixed checks, e.g., abc U pqr OR xyz).  For each string we're checking
for, we can pre-compute the BM jump table, should be pretty quick.

One concern that remains is short strings - 1 or 2 chars.  What
do we do if they are the longest string appearing in a rule? 

Since these strings will appear only in rules that are very qualified
(src port = 6000, dest port = 2121), we can keep a BDD encoding 
the L4 conditions for these rules (call the set S) , and just 
check the rules directly.

It's likely that there will be few rules per class for the 
ECs engendered by S. (Most of the packets won't even satisfy
S.)  So a brute force evaluation of all the rules in the class should
be simple enough.

*/

#include "evl.h"

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

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

static void computeNumberOfPreprocessRules (Evl_Manager_t * mgr);
static bool checkLegalRule (char *aRule);
static void populateL4Manager (Evl_Manager_t * mgr, char *mode);
static bdd_t *offsetVars (bdd_t * aBdd, bdd_manager * bddMgr, int numVars,
              int offset);
static bdd_t *listToBdd (Rlp_Formula_t * srcIp, bdd_manager * bddMgr,
             st_table * defineTable);
static bdd_t *ipToBdd (u_int32_t anIp, u_int32_t mask, bdd_manager * bddMgr);
static bdd_t *buildBddPort (int lowPort, bdd_manager * bddMgr, int index);
static void populateLookupTables (Evl_L4Manager_t * mgr);
static Evl_L4LookupTable_t *createLookupTable (Evl_L4Manager_t * mgr,
                           array_t * L4BddArray,
                           array_t * ruleVarArray);
static int longestPathToOne (bdd_t * aBdd, int descend);
static void printCubes (bdd_t * aBdd);
static int populateDecisionNodeTable (Evl_BddLevelPair_t * aBddLevelPair,
                      st_table * allDecisionNodes,
                      st_table * canonicalMap);
static bdd_t *getCofactorCube (int decisionLevel, int value,
                   bdd_manager * bddMgr, bool clearCache);
static void populateNodeToIdTable (Evl_BddLevelPair_t * root,
                   st_table * allDecisionNodes,
                   st_table * nodeToIdTable);
static var_set_t *classBddToSet (bdd_t * leafBdd, Evl_L4Manager_t * L4Mgr);
static Evl_GenericManager_t *Evl_GenericManagerAlloc (Evl_Manager_t * mgr);
static int addQueue (st_table * queueNameToQueueTable, char *anEntry);
static int populateL4BddInfo (Evl_L4Manager_t * L4Mgr);
static int bddArrayFree (array_t * bdds);
static int updateIdToRules (array_t * idToRules, int contentId,
                int ruleIndex);
static void populateContentManager (Evl_L4Manager_t * L4Mgr);
static int buildShortStringLookupTable (Evl_L4Manager_t * mgr);
static int printRuleSet (Evl_L4Manager_t * mgr, var_set_t * ruleSet);
static void populateLongStringsFsm (Evl_L4Manager_t * mgr);
static void populateMgrFsmAcceptingStates (Evl_L4Manager_t * L4Mgr,
                       st_table * longByteArrayHash);
static int populateRawRulesAndMacros (Evl_Manager_t * mgr, char *ruleFile);
static int buildNoContentCheckTable (Evl_L4Manager_t * mgr);
static bool checkRuleMode (char *rawRule, char *mode);

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


/**
  * \brief  Build basic evl data structures from a rule-set
  */

Evl_Manager_t *
Evl_BuildManager (char *ruleFileString, Tcl_Interp * interp, ClientData cd)
{
  Evl_Manager_t *result = Evl_ManagerAlloc ();
  result->interp = interp;
  result->cd = cd;

  populateRawRulesAndMacros (result, ruleFileString);

  // iterate through all the text lines, do basic parsing
  int i;
  for (i = 0; i < array_n (result->rawRulesAndMacrosArray); i++)
    {
      char *anEntry = array_fetch (char *, result->rawRulesAndMacrosArray, i);
      if (util_strequalN (anEntry, "var", 3))
    {
      Rlp_UpdateDefineTable (result->defineTable, anEntry);
    }
      else if (util_strequalN (anEntry, "queue", 5))
    {
      addQueue (result->queueTable, anEntry);
    }
      else
    {
      checkLegalRule (anEntry);
      array_insert_last (char *, result->rawRules, anEntry);
      char *actionComponent = Rlp_GetActionComponentFromRawRule (anEntry);
      Rlp_Action_t *parsedAction =
        Rlp_CreateActionFromRawText (actionComponent);
      array_insert_last (Rlp_Action_t *, result->rlpActionArray,
                 parsedAction);
      Evl_Action_t *action = Evl_AllocAction (parsedAction);
      array_insert_last (Evl_Action_t *, result->actionArray, action);
      result->numAllRules++;
    }
    }

  computeNumberOfPreprocessRules (result);

  populateL4Manager (result, "tcp");
  populateL4Manager (result, "udp");
  populateL4Manager (result, "icmp");
  populateL4Manager (result, "ip");
  populateL4Manager (result, "generic");

  return result;
}


/**
  * \brief Check that a string is a legal rule.  Incomplete, just
  * looks for gross errors.
  */

static bool
checkLegalRule (char *aRule)
{
  bool prefixCheck = false;
  if (util_strequalN (aRule, "generic", strlen ("generic")) ||
      util_strequalN (aRule, "udp", strlen ("udp")) ||
      util_strequalN (aRule, "tcp", strlen ("tcp")) ||
      util_strequalN (aRule, "icmp", strlen ("ip")) ||
      util_strequalN (aRule, "ip", strlen ("ip")))
    {
      prefixCheck = true;
    }
  if (prefixCheck == false)
    {
      return false;
    }
  // at some later point we can add individual
  // checks for generic, udp, tcp, etc. rules
  return true;
}


/**
  * \brief Create the action structured from the parsed entries
  */

Evl_Action_t *
Evl_AllocAction (Rlp_Action_t * parsedAction)
{
  Evl_Action_t *result = (Evl_Action_t *) malloc (sizeof (Evl_Action_t));
  result->parsedAction = parsedAction;
  result->queue = NIL (Q_Q_t);
  result->outIf = NIL (Pkt_LibNet_t);

  return result;
}


/**
  * \brief Build manager for tcp rules.  Returns mapping from id of local rule to all rules
  *
  * Even though it refers to portsm this structure can be used for tcp, udp, icmp, and even ip rules.
  * E.g., the rules ip 192.168.1.1/24 any -> any any (...)
  *     will lead to the right lookup table being created.
  *
  * \param mgr is the top level mananger
  * \param mode is used to indicate whether this is going to be built for tcp, udp, icmp, ip.
  */

static void
populateL4Manager (Evl_Manager_t * mgr, char *mode)
{
  if (util_strequal (mode, "generic"))
    {
      mgr->genericMgr = Evl_GenericManagerAlloc (mgr);
      return;           // no content checks
    }

  Evl_L4Manager_t *L4Mgr = Evl_L4ManagerAlloc (mgr, mode);

  if (util_strequal (mode, "tcp"))
    {
      mgr->tcpMgr = L4Mgr;
    }
  else if (util_strequal (mode, "udp"))
    {
      mgr->udpMgr = L4Mgr;
    }
  else if (util_strequal (mode, "icmp"))
    {
      mgr->icmpMgr = L4Mgr;
    }
  else if (util_strequal (mode, "ip"))
    {
      mgr->ipMgr = L4Mgr;
    }
  else
    {
      assert (0);
    }

  populateContentManager (L4Mgr);
  Evl_ContentMgr_t *aCM = L4Mgr->cm;

  Evl_ContentMgr_t *lowerCaseCM =
    Evl_BuildContentMgrForLowerCaseStrings (aCM);
  L4Mgr->cm = lowerCaseCM;

  populateLongStringsFsm (L4Mgr);
  populateL4BddInfo (L4Mgr);
  populateLookupTables (L4Mgr);
}


/**
  * \brief  Build a bdd for the L4 check
  */

bdd_t *
Evl_BuildBddFromL4Formula (Rlp_L4Check_t * L4Check,
               st_table * defineTable, bdd_manager * bddMgr)
{
  bdd_t *tmpSrcIpBdd =
    Evl_BuildBddForIps (L4Check->srcIp, bddMgr, defineTable);
  bdd_t *tmpDestIpBdd =
    Evl_BuildBddForIps (L4Check->destIp, bddMgr, defineTable);

  bdd_t *tmpSrcPortBdd =
    Evl_BuildBddForPorts (L4Check->srcPort, bddMgr, defineTable);
  bdd_t *tmpDestPortBdd =
    Evl_BuildBddForPorts (L4Check->destPort, bddMgr, defineTable);

  bdd_t *destIpBdd = offsetVars (tmpDestIpBdd, bddMgr, 32, 32);
  bdd_t *srcIpBdd = offsetVars (tmpSrcIpBdd, bddMgr, 32, 64);

  // wasteful, but stays symmetric
  bdd_t *destPortBdd = offsetVars (tmpDestPortBdd, bddMgr, 16, 0);

  bdd_t *srcPortBdd = offsetVars (tmpSrcPortBdd, bddMgr, 16, 16);

  bdd_t *t1 = bdd_and (destIpBdd, srcIpBdd, 1, 1);
  bdd_t *t2 = bdd_and (destPortBdd, srcPortBdd, 1, 1);
  bdd_t *t3 = bdd_and (t1, t2, 1, 1);

  bdd_free (tmpSrcIpBdd);
  bdd_free (tmpDestIpBdd);
  bdd_free (tmpSrcPortBdd);
  bdd_free (tmpDestPortBdd);

  bdd_free (destIpBdd);
  bdd_free (srcIpBdd);
  bdd_free (destPortBdd);
  bdd_free (srcPortBdd);

  bdd_free (t1);
  bdd_free (t2);

  return t3;
}


/**
  * \brief  Take an existing BDD over some vars, and substitute
  * those vars by some later in the order.
  */

static bdd_t *
offsetVars (bdd_t * aBdd, bdd_manager * bddMgr, int numVars, int offset)
{
  array_t *origVars = array_alloc (bdd_t *, 0);
  array_t *newVars = array_alloc (bdd_t *, 0);

  int i;
  for (i = 0; i < numVars; i++)
    {
      bdd_t *aVar = bdd_get_variable (bddMgr, i);
      bdd_t *aNewVar = bdd_get_variable (bddMgr, i + offset);
      array_insert_last (bdd_t *, origVars, aVar);
      array_insert_last (bdd_t *, newVars, aNewVar);
    }
  bdd_t *result = bdd_substitute (aBdd, origVars, newVars);
  for (i = 0; i < numVars; i++)
    {
      bdd_t *aVar = array_fetch (bdd_t *, origVars, i);
      bdd_t *aNewVar = array_fetch (bdd_t *, newVars, i);
      bdd_free (aVar);
      bdd_free (aNewVar);
    }
  array_free (origVars);
  array_free (newVars);
  return result;
}


/**
  * \brief  Build a bdd for an ip formula
  * 
  * Variables are starting from 0,
  * which is the LSB of the IP address.
  */

bdd_t *
Evl_BuildBddForIps (Rlp_Formula_t * srcIp,
            bdd_manager * bddMgr, st_table * defineTable)
{
  bdd_t *t1;
  bdd_t *t2;
  bdd_t *result = NIL (bdd_t);
  char *defineValue;
  Rlp_Formula_t *defineFormula;

  switch (srcIp->type)
    {
    case Rlp_Any_c:
      result = bdd_one (bddMgr);
      break;
    case Rlp_Negation_c:
      t1 = Evl_BuildBddForIps (srcIp->lchild, bddMgr, defineTable);
      result = bdd_not (t1);
      bdd_free (t1);
      break;
    case Rlp_List_c:

      // recursion kills performance on very long lists, do in a loop
      // t1 = Evl_BuildBddForIps( srcIp->lchild, bddMgr, defineTable );
      // t2 = Evl_BuildBddForIps( srcIp->rchild, bddMgr, defineTable );
      // result = bdd_or( t1, t2, 1, 1 );
      // bdd_free( t1 ); bdd_free( t2 );

      // loop solution:
      result = listToBdd (srcIp, bddMgr, defineTable);
      break;
    case Rlp_IpEntry_c:
      result =
    ipToBdd ((u_int32_t) srcIp->lchild, (u_int32_t) srcIp->rchild,
         bddMgr);
      break;
    case Rlp_Define_c:
      if (!Hash_Lookup
      (defineTable, (char *) srcIp->lchild, (char **) &defineValue))
    {
      printf ("Could not find the defined symbol %s\n",
          (char *) srcIp->lchild);
      assert (0);
    }
      defineFormula = Rlp_ComputeIpFormulaFromString (defineValue);
      result = Evl_BuildBddForIps (defineFormula, bddMgr, defineTable);
      break;
    default:
      printf ("Invalid type of ip node in formula\n");
      assert (0);
    }

  /* useful for debugging:
     printf("Result bdd has %d nodes\n", bdd_size( result ) );
     array_t *ipVarArray = array_alloc( bdd_t *, 0 );

     int i;
     for ( i = 0 ; i < 32; i++ ) {
     bdd_t *anIpVar = bdd_get_variable( bddMgr, i );
     array_insert_last( bdd_t *, ipVarArray, anIpVar );
     }
     printf("Number of minterms = %.0f\n", bdd_count_onset( result, ipVarArray ) );
   */

  return result;
}


/** \brief Build a BDD from a list */

static bdd_t *
listToBdd (Rlp_Formula_t * srcIp,
       bdd_manager * bddMgr, st_table * defineTable)
{
  bdd_t *t1;
  bdd_t *t2;
  bdd_t *result = bdd_zero (bddMgr);
  Rlp_Formula_t *iterFormula = srcIp;
  while (iterFormula != NIL (Rlp_Formula_t))
    {
      assert (iterFormula->type == Rlp_List_c);
      t1 = Evl_BuildBddForIps (iterFormula->lchild, bddMgr, defineTable);
      t2 = bdd_or (result, t1, 1, 1);
      bdd_free (t1);
      bdd_free (result);
      result = t2;
      iterFormula = cdr (iterFormula);
    }
  return result;

}


/** \brief  Build a bdd from a ip/mask */

static bdd_t *
ipToBdd (u_int32_t anIp, u_int32_t mask, bdd_manager * bddMgr)
{

  bdd_t *t1;
  bdd_t *result = bdd_one (bddMgr);

  int i;
  int ipAddrLen = 32;
  for (i = (ipAddrLen - 1); i >= 0; i--)
    {
      int testBit = (1 << i) & mask;
      if (testBit)
    {
      bdd_t *tmpBdd = bdd_get_variable (bddMgr, 31 - i);
      bdd_t *notTmpBdd = bdd_not (tmpBdd);
      if (anIp & (1 << i))
        {
          t1 = bdd_and (tmpBdd, result, 1, 1);
        }
      else
        {
          t1 = bdd_and (notTmpBdd, result, 1, 1);
        }
      bdd_free (result);
      bdd_free (tmpBdd);
      bdd_free (notTmpBdd);
      result = t1;
    }
    }
  return result;
}


/** \brief  Create a BDD from a port formula */

bdd_t *
Evl_BuildBddForPorts (Rlp_Formula_t * portFormula,
              bdd_manager * bddMgr, st_table * defineTable)
{
  bdd_t *t1;
  bdd_t *result = NIL (bdd_t);
  char *defineValue;
  Rlp_Formula_t *defineFormula;

  switch (portFormula->type)
    {
    case Rlp_Any_c:
      result = bdd_one (bddMgr);
      break;
    case Rlp_Negation_c:
      t1 = Evl_BuildBddForPorts (portFormula->lchild, bddMgr, defineTable);
      result = bdd_not (t1);
      bdd_free (t1);
      break;
    case Rlp_PortRange_c:
      result = Evl_BuildBddForPortRange ((u_int32_t) portFormula->lchild,
                     (u_int32_t) portFormula->rchild,
                     bddMgr);
      break;
    case Rlp_Define_c:
      if (!Hash_Lookup
      (defineTable, (char *) portFormula->lchild, (char **) &defineValue))
    {
      printf ("Could not find the defined symbol %s\n",
          (char *) portFormula->lchild);
      assert (0);
    }
      defineFormula = Rlp_ComputePortFormulaFromString (defineValue);
      result = Evl_BuildBddForPorts (defineFormula, bddMgr, defineTable);
      break;
    default:
      printf ("Invalid type of port node in formula\n");
      assert (0);
    }

  /* useful for debugging
     printf("Result bdd has %d nodes\n", bdd_size( result ) );
     array_t *portVarArray = array_alloc( bdd_t *, 0 );
     int i;
     for ( i = 0 ; i < 16; i++ ) {
     bdd_t *aPortVar = bdd_get_variable( bddMgr, i );
     array_insert_last( bdd_t *, portVarArray, aPortVar );
     }
     printf("Number of minterms = %.0f\n", bdd_count_onset( result, portVarArray ) );

   */
  return result;
}


/**
  * \brief  Build Bdd for a port interval [low,high], inclusive of end-points
  */

bdd_t *
Evl_BuildBddForPortRange (int lowPort, int highPort, bdd_manager * bddMgr)
{
  assert (!(lowPort > highPort));
  assert ((0 <= lowPort) && (lowPort < 65536) &&
      (0 <= highPort) && (highPort < 65536));
  // use the following relation:
  // a <= x <= b  <-> (a <= x) && ( !( b + 1 <= x ) )
  bdd_t *t1 = buildBddPort (lowPort, bddMgr, 15);
  bdd_t *t2 = buildBddPort (highPort + 1, bddMgr, 15);
  bdd_t *t3 = bdd_not (t2);
  bdd_t *result = bdd_and (t1, t3, 1, 1);
  bdd_free (t1);
  bdd_free (t2);
  bdd_free (t3);
  return result;
}


/**
  * \brief  Build bdd for the relation X >= A looking 
  * at the k least signifincat bits
  */

static bdd_t *
buildBddPort (int lowPort, bdd_manager * bddMgr, int index)
{
  bdd_t *t1, *t2, *t3, *t4;
  bdd_t *result;

  if (lowPort == 65536)
    {
      // this is possible, since we do call with highPort + 1 
      return bdd_zero (bddMgr);
    }
  bdd_t *indexVar = bdd_get_variable (bddMgr, 15 - index);

  unsigned int val = (lowPort & ((unsigned int) 1 << index) ? 1 : 0);

  // code implements the following logic:
  //
  // compute X[index] > a[index]  +  
  // X[index] == a[index] . ( X_{index-1} >= a_{index-1} )

  if (index == 0)
    {
      if (val == 0)
    {
      bdd_free (indexVar);
      return bdd_one (bddMgr);
    }
      else
    {
      result = indexVar;
      return result;
    }
    }

  // not looking at index 0
  // t1 is  X[index] > a[index]
  // t2 is X[index] == a[index]
  if (val == 0)
    {
      t1 = bdd_dup (indexVar);
      t2 = bdd_not (indexVar);
    }
  else
    {
      t1 = bdd_zero (bddMgr);
      t2 = bdd_dup (indexVar);
    }
  // t3 is ( X_{index-1} >= a_{index-1} )
  t3 = buildBddPort (lowPort, bddMgr, index - 1);
  t4 = bdd_and (t2, t3, 1, 1);
  result = bdd_or (t1, t4, 1, 1);
  bdd_free (t1);
  bdd_free (t2);
  bdd_free (t3);
  bdd_free (t4);
  bdd_free (indexVar);

  return result;
}


/** \brief  Compare function for bdd_t */

int
Evl_BddCmp (char *aBdd, char *bBdd)
{
  int is_complemented;
  bdd_node *aNode = bdd_get_node ((bdd_t *) aBdd, &is_complemented);
  if (is_complemented)
    {
      aNode = (bdd_node *) ((unsigned int) aNode ^ (unsigned int) 0x1);
    }
  bdd_node *bNode = bdd_get_node ((bdd_t *) bBdd, &is_complemented);
  if (is_complemented)
    {
      bNode = (bdd_node *) ((unsigned int) bNode ^ (unsigned int) 0x1);
    }
  int result = st_numcmp ( (int) aNode, (int) bNode );
  return result;
}


/**
  * \brief Hash function for bdd_t.
  * 
  *
  * Makes use of the bdd_node structure, here's the info from the bdd.doc:
  *
  * bdd_node *
  * bdd_get_node(f, is_complemented)
  * bdd_t *f;
  * boolean *is_complemented;    
  * 
  * Return the regularized (i.e. uncomplemented) pointer to the bdd_node
  * to which `f' refers.  Also, returns whether or not the bdd_node pointer
  * is complemented.  Note well: the address of a bdd_node changes upon
  * garbage collection.  If your code is sensitive to the addresses of
  * bdd_nodes, and you invoke BDD routines which cause new bdd_nodes to be
  * created, then a garbage collection may automatically be triggered.  To
  * prevent a garbage collection from automatically occurring, use
  * bdd_set_gc_mode to turn off garbage collection before a sensitive piece
  * of code is executed.
  */

int
Evl_BddHash (char *aBdd, int modulus)
{
  int is_complemented;
  bdd_node *aNode = bdd_get_node ((bdd_t *) aBdd, &is_complemented);
  if (is_complemented)
    {
      aNode = (bdd_node *) ((unsigned int) aNode ^ (unsigned int) 0x1);
    }
  int result = st_numhash ((char *) aNode, modulus);
  return result;
}


/**
  * \brief  Create a lookup table for a set of L4 BDDs.
  */

static void
populateLookupTables (Evl_L4Manager_t * mgr)
{
  bdd_t *L4Bdd;
  int L4Id;

  array_t *destPortRuleArray = array_alloc (bdd_t *, 0);
  array_t *srcPortRuleArray = array_alloc (bdd_t *, 0);
  array_t *noPortRuleArray = array_alloc (bdd_t *, 0);

  array_t *destPortRuleVarsArray = array_alloc (bdd_t *, 0);
  array_t *srcPortRuleVarsArray = array_alloc (bdd_t *, 0);
  array_t *noPortRuleVarsArray = array_alloc (bdd_t *, 0);

  Hash_ForEachItemNew (mgr->distinctL4RulesTable, (char **) &L4Bdd,
           (char **) &L4Id)
  {
    int bddTopVar = bdd_top_var_id (L4Bdd);
    if (bddTopVar < 16)
      {
    // this rule depends on dest port
    array_insert_last (bdd_t *, destPortRuleArray, L4Bdd);
    bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4Id + 96);
    array_insert_last (bdd_t *, destPortRuleVarsArray, ruleVar);
      }
    else if (bdd_top_var_id (L4Bdd) < 32)
      {
    // this rule depends on src port but not dest port
    array_insert_last (bdd_t *, srcPortRuleArray, L4Bdd);
    bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4Id + 96);
    array_insert_last (bdd_t *, srcPortRuleVarsArray, ruleVar);
      }
    else
      {
    array_insert_last (bdd_t *, noPortRuleArray, L4Bdd);
    bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4Id + 96);
    array_insert_last (bdd_t *, noPortRuleVarsArray, ruleVar);
      }
  }

  if (array_n (destPortRuleVarsArray) > 0)
    {
      mgr->destPortRuleTable =
    createLookupTable (mgr, destPortRuleArray, destPortRuleVarsArray);
    }
  if (array_n (srcPortRuleVarsArray) > 0)
    {
      mgr->srcPortRuleTable =
    createLookupTable (mgr, srcPortRuleArray, srcPortRuleVarsArray);
    }
  if (array_n (noPortRuleVarsArray) > 0)
    {
      mgr->noPortRuleTable =
    createLookupTable (mgr, noPortRuleArray, noPortRuleVarsArray);
    }

  buildNoContentCheckTable (mgr);
  buildShortStringLookupTable (mgr);
}


/**
  * \brief  Build the actual lookup table
  */

static Evl_L4LookupTable_t *
createLookupTable (Evl_L4Manager_t * mgr,
           array_t * L4BddArray, array_t * ruleVarArray)
{
  bdd_t *L4Rule;
  int L4Id;
  bdd_t *TR = bdd_one (mgr->bddMgr);
  bdd_t *t1;

  int i;
  for (i = 0; i < array_n (L4BddArray); i++)
    {
      L4Rule = array_fetch (bdd_t *, L4BddArray, i);
      Hash_Lookup (mgr->distinctL4RulesTable, (char *) L4Rule, (char **) &L4Id);
      bdd_t *L4RuleVar = bdd_get_variable (mgr->bddMgr, 96 + L4Id);

      bdd_t *thisRelation = bdd_xnor (L4RuleVar, L4Rule);
      t1 = bdd_and (TR, thisRelation, 1, 1);
      bdd_free (thisRelation);
      bdd_free (TR);
      bdd_free (L4RuleVar);
      TR = t1;
    }

  Evl_L4LookupTable_t *result =
    Evl_RuleRelationToLookupTable (TR, mgr, ruleVarArray);

  return result;
}


/**
  * \brief  Find the longest path to 1 terminal in a BDD, length
  * is the number of then-edges.
  */

static int
longestPathToOne (bdd_t * aBdd, int descend)
{
  if (bdd_is_tautology (aBdd, 1))
    {
      return 0;
    }
  if (bdd_is_tautology (aBdd, 0))
    {
      return -100000;
    }
  bdd_t *bddThen = bdd_then (aBdd);
  bdd_t *bddElse = bdd_else (aBdd);

  int left = longestPathToOne (bdd_else (aBdd), 0);
  int right = longestPathToOne (bdd_then (aBdd), 0);

  // aBdd cannot be a 0/1 if we're here
  int aBddId = bdd_top_var_id (aBdd);

  if (bdd_is_tautology (bddElse, 1))
    {
      int totalNumVars = bdd_num_vars (bdd_get_manager (aBdd));
      left = (left) + ((totalNumVars - aBddId) - 1);
    }
  else
    {
      int bddElseId = bdd_top_var_id (bddElse);
      left = (left) + ((bddElseId - aBddId) - 1);
    }
  if (bdd_is_tautology (bddThen, 1))
    {
      int totalNumVars = bdd_num_vars (bdd_get_manager (aBdd));
      right = (right) + ((totalNumVars - aBddId) - 1);
    }
  else
    {
      int bddThenId = bdd_top_var_id (bddThen);
      right = (right) + ((bddThenId - aBddId) - 1);
    }

  if (left < right + 1)
    {
      if (descend == 1)
    {
      printf ("Take r_%d to be 1\n", bdd_top_var_id (aBdd));
      longestPathToOne (bdd_then (aBdd), 1);
    }
      return right + 1;
    }
  else
    {
      if (descend == 1)
    {
      printf ("Take r_%d to be 0\n", bdd_top_var_id (aBdd));
      longestPathToOne (bdd_else (aBdd), 1);
    }
      return left;
    }
}


/**
  * \brief  Print all the cubes in a BDD
  * 
  * Useful for debugging, e.g., seeing all classes.
  */

static void
printCubes (bdd_t * aBdd)
{
  bdd_gen *bddGen;
  array_t *cube;
  int i;
  int literal;
  int count = 0;
  int start;

  bddGen = bdd_first_cube (aBdd, &cube);
  int totalLiteralsEqOne = 0;

  while (1)
    {
      count++;
      start = 0;
      for (i = 0; i < array_n (cube); i++)
    {
      literal = array_fetch (int, cube, i);
      if (literal == 1 || literal == 0)
        {
          printf ("%s", literal ? "1" : "");
          totalLiteralsEqOne += (literal == 1) ? 1 : 0;
          start = 1;
        }
    }
      printf ("\n");
      if (count % 1000 == 0)
    printf ("Completed %d cubes\n", count);
      if (!bdd_next_cube (bddGen, &cube))
    {
      break;
    }
    }
  printf ("Counted %d cubes, with a total of %d literals\n", count,
      totalLiteralsEqOne);
}


/**
  * \brief  Build a lookup table from the rule relation BDD
  * 
  * \pre First 96 vars are dest port, src port, dest ip, src ip. 
  * 
  * We're going to return an array that will be used
  * to represent a 256-ary tree mapping IP headers to 
  * bit-vectors whose length is equal to the number of
  * distinct L4 rules.
  */

Evl_L4LookupTable_t *
Evl_RuleRelationToLookupTable (bdd_t * TR,
                   Evl_L4Manager_t * L4Mgr,
                   array_t * ruleVarArray)
{
  int offset = 96;
  array_t *origVarArray = array_alloc (bdd_t *, 0);
  int i;
  bdd_manager *bddMgr = L4Mgr->bddMgr;

  for (i = 0; i < offset; i++)
    {
      array_insert_last (bdd_t *, origVarArray, bdd_get_variable (bddMgr, i));
    }

  bdd_t *classBdd = bdd_smooth (TR, origVarArray);
  // printf("Class mdd has %d nodes\n", bdd_size( classBdd ) );
  bddArrayFree (origVarArray);

  int numClasses = (int) bdd_count_onset (classBdd, ruleVarArray);
  // printf("Number of classes = %.d\n", numClasses );
  bddArrayFree (ruleVarArray);

  // bdd_print(  classBdd  );
  // printCubes(  classBdd  );
  // printf("---\n");
  // printf("Longest path to 1 has %d terms\n", longestPathToOne( classBdd, 1 ) );

  bdd_set_gc_mode (bddMgr, 1);

  st_table *allDecisionNodes =
    Hash_InitTable (  (int(*)() ) Evl_BddLevelPairCmp, (int(*)() ) Evl_BddLevelPairHash);
  st_table *canonicalMap =
    Hash_InitTable ( (int(*)() ) Evl_BddLevelPairCmp, (int(*)())  Evl_BddLevelPairHash);
  Evl_BddLevelPair_t *root = Evl_CreateBddLevelPair (TR, 0);
  populateDecisionNodeTable (root, allDecisionNodes, canonicalMap);
  // printf("Total number of nodes in the final tree = %d\n", st_count( allDecisionNodes ) );

  // clear out the cache
  getCofactorCube (0, 0, bddMgr, true);
  // clear out the canonical map
  Hash_FreeTable (canonicalMap);

  Evl_L4LookupTable_t *result =
    Evl_L4BuildLookup (root, numClasses, L4Mgr, allDecisionNodes);

  st_generator *stGen;
  Evl_BddLevelPair_t *tmpPair;
  Evl_BddLevelPair_t **tmpChildArray;
  st_foreach_item (allDecisionNodes, stGen, (char **) &tmpPair,
           (char **) &tmpChildArray)
  {
    if (tmpPair->level == 88)
      {
    // if they are at level 88, then their children are not in the 
    // table, and must be freed explicilty 
    int l;
    for (l = 0; l < 256; l++)
      {
        bdd_free (tmpChildArray[l]->bdd);
        free (tmpChildArray[l]);
      }
      }
    bdd_free (tmpPair->bdd);
    free (tmpPair);
    free (tmpChildArray);
  }
  Hash_FreeTable (allDecisionNodes);

  return result;
}


/**
  * \brief  Get bdd_t's for all distinct BDD nodes at levels
  * 0,8,...,88 in the given BDD.
  * 
  * Return 1 if the node
  * is already present in the all decision noes table, 
  * 0 if its a terminal level 96) or was not present.
  */

static int
populateDecisionNodeTable (Evl_BddLevelPair_t * aBddLevelPair,
               st_table * allDecisionNodes,
               st_table * canonicalMap)
{
  static int totalCalls = 0;
  if (false && (totalCalls % 100000) == 0)
    {
      printf ("Total calls to populateDecisionNodeTable = %d\n",
          totalCalls++);
    }
  totalCalls++;
  bdd_t *aRelation = aBddLevelPair->bdd;
  int decisionLevel = aBddLevelPair->level;

  static int cacheHits = 0;
  if (Hash_Lookup (allDecisionNodes, (char *) aBddLevelPair, (char **) 0))
    {
      if (false && (cacheHits % 10000) == 0)
    printf
      ("Cache hit: %d total calls of which %d cache hits, table has %d entries, decision level %d\n",
       totalCalls, cacheHits, st_count (allDecisionNodes), decisionLevel);
      cacheHits++;
      return 1;
    }
  if (decisionLevel > 88)
    {
      return 0;
    }
  Evl_BddLevelPair_t **childrenArray =
    (Evl_BddLevelPair_t **) malloc (256 * sizeof (Evl_BddLevelPair_t));
  Hash_Insert (allDecisionNodes, (char *) aBddLevelPair,
         (char *) childrenArray);
  Hash_Insert (canonicalMap, (char *) aBddLevelPair, (char *) aBddLevelPair);
  bdd_manager *bddMgr = bdd_get_manager (aRelation);
  int i;
  for (i = 0; i < 256; i++)
    {
      bdd_t *cofactorCube = getCofactorCube (decisionLevel, i, bddMgr, false);
      bdd_t *aCofactor = bdd_cofactor (aRelation, cofactorCube);
      // printf("Printing a cofactored BDD at level %d, number %d\n", decisionLevel, i);
      // bdd_print( aCofactor );
      // don't free since we're caching  
      // bdd_free( cofactorCube );
      // cannot free aCofactor either since it's in the bdd-level pair struct
      Evl_BddLevelPair_t *aCofactorLevelPair =
    Evl_CreateBddLevelPair (aCofactor, decisionLevel + 8);
      if (populateDecisionNodeTable
      (aCofactorLevelPair, allDecisionNodes, canonicalMap))
    {
      // it was already in the cache, so free it
      Evl_BddLevelPair_t *tmpPair;
      Hash_Lookup (canonicalMap, (char *) aCofactorLevelPair,
             (char **) &tmpPair);
      bdd_free (aCofactorLevelPair->bdd);
      free (aCofactorLevelPair);
      // set aCofactorLevelPair to the canonical entry
      aCofactorLevelPair = tmpPair;
    }
      childrenArray[i] = aCofactorLevelPair;
    }
  return 0;
}


/**
  * \brief  Build a bdd cube based on the level and value information 
  * passed in
  */

static bdd_t *
getCofactorCube (int decisionLevel,
         int value, bdd_manager * bddMgr, bool clearCache)
{
  int i;
  bdd_t *result;
  bdd_t *t1;
  static st_table *cache = NIL (st_table);
  unsigned int key;

  if (clearCache)
    {
      st_generator *stGen;
      st_foreach_item (cache, stGen, (char **) &key, (char **) &t1)
      {
    bdd_free (t1);
      }
      Hash_FreeTable (cache);
      cache = NIL (st_table);
      return NIL (bdd_t);
    }

  if (!cache)
    {
      cache = Hash_InitTable ( (int(*)() ) st_numcmp, (int(*)() ) st_numhash);
    }
  key = decisionLevel * 256 + value;
  if (Hash_Lookup (cache, (char *) key, (char **) &result))
    {
      // printf("Cache hit in cofactor cache, level %d, value %d\n", 
      //         decisionLevel, value );
      return result;
    }
  // printf("No cache hit in cofactor cache, processing level %d, value %d\n", 
  //           decisionLevel, value );

  result = bdd_one (bddMgr);
  for (i = 0; i < 8; i++)
    {
      bdd_t *var = bdd_get_variable (bddMgr, decisionLevel + (7 - i));
      bdd_t *notVar = bdd_not (var);
      bool bitI = (((1 << i) & value) == 0) ? false : true;
      if (bitI)
    {
      t1 = bdd_and (result, var, 1, 1);
    }
      else
    {
      t1 = bdd_and (result, notVar, 1, 1);
    }
      bdd_free (result);
      bdd_free (var);
      bdd_free (notVar);
      result = t1;
    }
  Hash_Insert (cache, (char *) key, (char *) result);
  // printf("Printing result of getCofactorCube at decision level %d"
  // "and value %d\n", decisionLevel, value );
  // bdd_print( result );
  return result;
}


/**
  * \brief  Build the L4 lookup array
  */

Evl_L4LookupTable_t *
Evl_L4BuildLookup (Evl_BddLevelPair_t * root,
           int numClasses,
           Evl_L4Manager_t * L4Mgr, st_table * allDecisionNodes)
{
  Evl_L4LookupTable_t *result =
    (Evl_L4LookupTable_t *) malloc (sizeof (Evl_L4LookupTable_t));

  result->tree =
    (int *) malloc (256 * st_count (allDecisionNodes) * sizeof (int));
  result->numClasses = numClasses;
  result->ruleSets =
    (var_set_t **) malloc (numClasses * sizeof (var_set_t *));
  result->ruleArrays = NIL (util_int_array_t *);

  st_table *nodeToIdTable =
    Hash_InitTable ( (int(*)() ) Evl_BddLevelPairCmp,  (int(*)() ) Evl_BddLevelPairHash);
  populateNodeToIdTable (root, allDecisionNodes, nodeToIdTable);
  // printf("Size of allDecisionNodes table is %d\n", st_count( allDecisionNodes ) );

  st_table *leafNodeToIdTable =
    Hash_InitTable ( (int(*)() ) Evl_BddLevelPairCmp, (int(*)() ) Evl_BddLevelPairHash);
  st_table *idToLeafNodeTable = Hash_InitTable ( (int(*)() ) st_numcmp, (int(*)() ) st_numhash);

  int i;
  int childId;
  int leafId;
  int aNodeId;
  Evl_BddLevelPair_t *aNodeLevelPair;
  Evl_BddLevelPair_t *child;
  Evl_BddLevelPair_t **childrenArray;
  st_generator *stGen;

  st_foreach_item (allDecisionNodes, stGen, (char **) &aNodeLevelPair,
           (char **) &childrenArray)
  {
    Hash_Lookup (nodeToIdTable, (char *) aNodeLevelPair, (char **) &aNodeId);
    for (i = 0; i < 256; i++)
      {
    child = childrenArray[i];
    if (Hash_Lookup (nodeToIdTable, (char *) child, (char **) &childId))
      {
        // it's an internal node
        result->tree[aNodeId * 256 + i] = childId;
      }
    else
      {
        // must be a leaf node
        if (!Hash_Lookup
        (leafNodeToIdTable, (char *) child, (char **) &leafId))
          {
        // create an id for it 
        leafId = st_count (leafNodeToIdTable);
        Hash_Insert (leafNodeToIdTable, (char *) child,
               (char *) leafId);
        Hash_Insert (idToLeafNodeTable, (char *) leafId,
               (char *) child);
          }
        result->tree[aNodeId * 256 + i] = leafId;
      }
      }             // st_foreach_item
  }

  // now set each leaf node to the set of rules in that equivalence class
  Evl_BddLevelPair_t *leafBddLevelPair;
  var_set_t **ruleSets = result->ruleSets;
  for (i = 0; i < numClasses; i++)
    {
      Hash_Lookup (idToLeafNodeTable, (char *) i, (char **) &leafBddLevelPair);
      ruleSets[i] = classBddToSet (leafBddLevelPair->bdd, L4Mgr);
    }

  // printf("The table has %d classes\n", numClasses );
  // printf("Total number of nodes in the final table = %d\n",
  //     st_count( allDecisionNodes ) );

  Hash_FreeTable (nodeToIdTable);
  Hash_FreeTable (leafNodeToIdTable);
  Hash_FreeTable (idToLeafNodeTable);

  return result;
}


/**
  * \brief  Instantiate a table of bddNodes to int id.
  */

static void
populateNodeToIdTable (Evl_BddLevelPair_t * root,
               st_table * allDecisionNodes, st_table * nodeToIdTable)
{
  // static int numCalls=0;
  // if ( numCalls % 1000 == 0 ) {
  //  printf("There have been %d calls to populateNodeToIdTable, and" 
  //            "the table size is %d\n", numCalls, st_count( allDecisionNodes ) );
  // }
  // numCalls++;

  // static int numCacheHits = 0;
  // if ( numCacheHits % 1000 == 0 ) {
  //  printf("There have been %d"
  //            "cache hits (out of %d calls),"
  //            "the table size is %d\n", 
  //             numCacheHits, numCalls, st_count( allDecisionNodes ) );
  // }

  if (Hash_Lookup (nodeToIdTable, (char *) root, (char **) 0))
    {
      return;
    }

  if (root->level > 88)
    {
      // this is a terminal, hence we return
      return;
    }

  Evl_BddLevelPair_t **childrenArray;
  Hash_Lookup (allDecisionNodes, (char *) root, (char **) &childrenArray);
  int id = st_count (nodeToIdTable);
  Hash_Insert (nodeToIdTable, (char *) root, (char *) id);

  int i;
  for (i = 0; i < 256; i++)
    {
      Evl_BddLevelPair_t *aChild = childrenArray[i];
      populateNodeToIdTable (aChild, allDecisionNodes, nodeToIdTable);
    }
}


/**
  * \brief  Create a var set representing the set of rules that
  * are encoded by a given BDD
  * 
  * BDD is assumed to be
  * only over the rule vars, and encodes a SINGLE minterm.
  * The result a var_set over the set of all rules, not 
  * just distinct L4 rules.
  */

static var_set_t *
classBddToSet (bdd_t * leafBdd, Evl_L4Manager_t * L4Mgr)
{
  int numL4Rules = L4Mgr->numDistinctL4Rules;
  assert (L4Mgr->numDistinctL4Rules ==
      st_count (L4Mgr->distinctL4RulesTable));

  var_set_t *L4Rules = var_set_new (numL4Rules);
  int i;
  bdd_t *t1 = bdd_dup (leafBdd);
  // printf("Printing what's supposed to be a leafBdd\n");
  // bdd_print( t1 );
  while (1)
    {
      if (bdd_is_tautology (t1, 1))
    {
      break;
    }
      bdd_t *bddThen = bdd_then (t1);
      bdd_t *bddElse = bdd_else (t1);
      assert (bdd_is_tautology (bddThen, 0) || bdd_is_tautology (bddElse, 0));
      if (!bdd_is_tautology (bddThen, 0))
    {
      // the rule corresponding to t1 is in the set
      int thisRule = bdd_top_var_id (t1);
      var_set_set_elt (L4Rules, thisRule - 96);
      bdd_free (t1);
      t1 = bddThen;
      bdd_free (bddElse);
    }
      else
    {
      bdd_free (t1);
      t1 = bddElse;
      bdd_free (bddThen);
    }
    }
  bdd_free (t1);

  var_set_t *result = var_set_new (L4Mgr->numAllRules);
  for (i = 0; i < numL4Rules; i++)
    {
      if (var_set_get_elt (L4Rules, i))
    {
      var_set_t *L7rulesForThisL4Rule =
        array_fetch (var_set_t *, L4Mgr->L4RuleIdToL7ruleSetTable, i);
      result = var_set_or (result, result, L7rulesForThisL4Rule);
    }
    }
  var_set_free (L4Rules);

  return result;
}


/**
  * \brief  Allocate and populate a bdd-and-level struct.
  */

Evl_BddLevelPair_t *
Evl_CreateBddLevelPair (bdd_t * aBdd, int level)
{
  Evl_BddLevelPair_t *result =
    (Evl_BddLevelPair_t *) malloc (sizeof (Evl_BddLevelPair_t));

  result->bdd = aBdd;
  result->level = level;
  return result;
}


/**
  * \brief  Hash function for a bdd-level pair
  */

int
Evl_BddLevelPairHash (char *aPtr, int modulus)
{
  Evl_BddLevelPair_t *aBddAndLevelObj = (Evl_BddLevelPair_t *) aPtr;
  int bddHashCode = Evl_BddHash ((char *) aBddAndLevelObj->bdd, modulus);
  int levelHash = st_numhash ((char *) aBddAndLevelObj->level, modulus);

  int result =
    st_numhash ((char *) (3 * bddHashCode + 5 * levelHash), modulus);

  return result;
}


/**
  * \brief  Compare function for a bdd-level pair
  */

int
Evl_BddLevelPairCmp (char *aPtr, char *bPtr)
{
  Evl_BddLevelPair_t *aBddLevelPair = (Evl_BddLevelPair_t *) aPtr;
  Evl_BddLevelPair_t *bBddLevelPair = (Evl_BddLevelPair_t *) bPtr;

  if (aBddLevelPair->level < bBddLevelPair->level)
    {
      return -1;
    }
  if (aBddLevelPair->level > bBddLevelPair->level)
    {
      return 1;
    }
  return Evl_BddCmp ((char *) aBddLevelPair->bdd,
             (char *) bBddLevelPair->bdd);
}


/**
  * \brief  Allocate and initialize manager for generic rules
  */

static Evl_GenericManager_t *
Evl_GenericManagerAlloc (Evl_Manager_t * mgr)
{
  Evl_GenericManager_t *result =
    (Evl_GenericManager_t *) malloc (sizeof (Evl_GenericManager_t));
  result->mgr = mgr;
  result->numAllRules = 0;
  result->tcpIdToGlobalId = array_alloc (int, 0);
  result->L7RuleArray = array_alloc (int, 0);

  int i;
  for (i = 0; i < array_n (mgr->rawRules); i++)
    {
      char *rawRule = array_fetch (char *, mgr->rawRules, i);
      while (*rawRule == ' ')
    {
      rawRule++;
    }
      if (!util_strequalN (rawRule, "generic", strlen ("generic")))
    {
      continue;
    }
      array_insert_last (int, result->tcpIdToGlobalId, i);
      char *L7component = Rlp_GetL7ComponentFromRawRule (rawRule);
      Rlp_Formula_t *L7Formula = Rlp_CreateParseTreeFromText (L7component);
      array_insert_last (Rlp_Formula_t *, result->L7RuleArray, L7Formula);
      result->numAllRules++;
    }

  return result;
}


/**
  * \brief  Allocate and initialize a TCP manager
  */

Evl_L4Manager_t *
Evl_L4ManagerAlloc (Evl_Manager_t * mgr, char *mode)
{
  Evl_L4Manager_t *result =
    (Evl_L4Manager_t *) malloc (sizeof (Evl_L4Manager_t));
  result->mgr = mgr;

  result->tcpIdToGlobalId = array_alloc (int, 0);

  result->L4RuleArray = array_alloc (Rlp_L4Check_t *, 0);
  result->L7RuleArray = array_alloc (Rlp_Formula_t *, 0);
  result->cm = NIL (Evl_ContentMgr_t);

  result->numAllRules = 0;
  int i;
  for (i = 0; i < array_n (mgr->rawRules); i++)
    {
      char *rawRule = array_fetch (char *, mgr->rawRules, i);
      while (*rawRule == ' ')
    {
      rawRule++;
    }
      // if ( !util_strequalN( rawRule, mode, strlen( mode ) ) ) {
      if (!checkRuleMode (rawRule, mode))
    {
      continue;
    }
      array_insert_last (int, result->tcpIdToGlobalId, i);
      result->numAllRules++;

      char *L4component = Rlp_GetL4ComponentFromRawRule (rawRule);
      char *L7component = Rlp_GetL7ComponentFromRawRule (rawRule);
      Rlp_L4Check_t *L4Formula =
    Rlp_CreateL4CheckFromRawFormula (L4component);
      array_insert_last (Rlp_L4Check_t *, result->L4RuleArray, L4Formula);
      Rlp_Formula_t *L7Formula = Rlp_CreateParseTreeFromText (L7component);
      array_insert_last (Rlp_Formula_t *, result->L7RuleArray, L7Formula);
    }

  result->bddMgr = bdd_start (32 + 16 + 32 + 16);

  result->numDistinctL4Rules = 0;
  result->distinctL4RulesTable = Hash_InitTable ( (int(*)() ) Evl_BddCmp, (int(*)() ) Evl_BddHash);
  result->L4RuleIdToL7ruleSetTable = array_alloc (var_set_t *, 0);
  result->ruleToL4Bdd = array_alloc (bdd_t *, 0);

  result->destPortRuleTable = NIL (Evl_L4LookupTable_t);
  result->srcPortRuleTable = NIL (Evl_L4LookupTable_t);
  result->noPortRuleTable = NIL (Evl_L4LookupTable_t);

  result->noContentCheckTable = NIL (Evl_L4LookupTable_t);
  result->shortStringRuleTable = NIL (Evl_L4LookupTable_t);

  result->potentialRulesFromFsm = NIL (array_t);
  result->rulesFromFsm = NIL (array_t);
  result->rulesFromShortStringTable = NIL (array_t);
  result->rulesFromNoContentTable = NIL (array_t);

  return result;
}


/**
  * \brief  Allocate and initialize a manager
  */

Evl_Manager_t *
Evl_ManagerAlloc ()
{
  Evl_Manager_t *result = (Evl_Manager_t *) malloc (sizeof (Evl_Manager_t));

  result->rawRules = array_alloc (char *, 0);
  result->rlpActionArray = array_alloc (Rlp_Action_t *, 0);
  result->actionArray = array_alloc (Evl_Action_t *, 0);
  result->ucodeNameToFunction = Hash_InitTable ( (int(*)() ) strcmp, (int(*)() ) st_strhash);
  result->defineTable = Hash_InitTable ( (int(*)() ) strcmp, (int(*)() ) st_strhash);

  result->numPreprocessRules = 0;
  result->indexFirstContentRule = -1;
  result->indexLastContentRule = -1;

  result->numAllRules = 0;
  result->bridge = NIL (Evl_Bridge_t);

  result->queueTable = Hash_InitTable ( (int(*)() ) strcmp, (int(*)() ) st_strhash);
  result->qHeap = NIL (Heap_t);

  result->preprocessorResult = NIL (array_t);
  result->genericResult = NIL (array_t);
  result->layer3Result = NIL (array_t);
  result->layer4Result = NIL (array_t);

  return result;
}


/**
  * \brief  Add a queue to the set of queues.
  * 
  * anEntry looks like "queue qname classes:5
  * 
  */

static int
addQueue (st_table * queueNameToQueueTable, char *anEntry)
{
  char varBuf[1000];
  // need the + 1 to get past the blank space
  char *beginSymbolPtr = anEntry + strlen ("queue") + 1;
  char *endSymbolPtr = strchr (beginSymbolPtr, ' ');
  int length = endSymbolPtr - beginSymbolPtr;
  strncpy (varBuf, beginSymbolPtr, length);
  varBuf[length] = '\0';
  char *queueName = strdup (varBuf);

  while (isspace (*endSymbolPtr))
    {
      endSymbolPtr++;
    }
  char *queueDefn = strdup (endSymbolPtr);
  // remove any trailing whitespace
  char *tmpPtr = queueDefn + strlen (queueDefn) - 1;
  while (isspace (*tmpPtr))
    {
      *tmpPtr = '\0';
      tmpPtr--;
    }
  // need to parse queueDefn and create the Q_Q_t struct
  Q_Q_t *aQ = Q_AllocQ (queueName);
  // overkill to call Rlp_L7StringParse, (no quotes/escapes) but it's easier this way
  array_t *attributesArray = Rlp_L7StringParse (queueDefn);
  int i;
  for (i = 0; i < array_n (attributesArray); i++)
    {
      Rlp_RuleComponent_t *aComponent = array_fetch (Rlp_RuleComponent_t *,
                             attributesArray, i);
      char *attribute = aComponent->rawAttribute;
      char *value = aComponent->rawValue;

      if (util_strequal (attribute, "type"))
    {
      if (util_strequal (value, "cos"))
        {
          aQ->type = Q_QueueTypeCos_c;
        }
      else if (util_strequal (value, "flow"))
        {
          aQ->type = Q_QueueTypeFlow_c;
        }
      else
        {
          printf ("Unrecognized type of queue - %s\n", value);
          assert (0);
        }
    }
      else if (util_strequal (attribute, "numclasses"))
    {
      sscanf (value, "%d", &aQ->numClasses);
    }
      else if (util_strequal (attribute, "priority"))
    {
      sscanf (value, "%d", &aQ->assignedPriority);
    }
      else if (util_strequal (attribute, "windowduration"))
    {
      sscanf (value, "%lf", &aQ->timeWindowDuration);
    }
      else if (util_strequal (attribute, "maxrate"))
    {
      sscanf (value, "%d", &aQ->maxRate);
    }
      else if (util_strequal (attribute, "flowmaxrate"))
    {
      sscanf (value, "%d", &aQ->flowMaxRate);
    }
      else if (util_strequal (attribute, "maxbytes"))
    {
      sscanf (value, "%d", &aQ->maxAllowedBytes);
    }
      else if (util_strequal (attribute, "maxflows"))
    {
      sscanf (value, "%d", &aQ->maxFlows);
    }
      else if (util_strequal (attribute, "maxbytesperflow"))
    {
      sscanf (value, "%d", &aQ->maxBytesPerFlow);
    }
      else if (util_strequal (attribute, "flowdrop"))
    {
      if (util_strequal (value, "red"))
        {
          aQ->flowDropMethod = Q_DropRed_c;
        }
      else if (util_strequal (value, "tail"))
        {
          aQ->flowDropMethod = Q_DropTail_c;
        }
      else
        {
          fprintf (stderr, "Don't support flow drop method %s\n", value);
          assert (0);
        }
    }
      else if (util_strequal (attribute, "drop"))
    {
      if (util_strequal (value, "red"))
        {
          aQ->dropMethod = Q_DropRed_c;
        }
      else if (util_strequal (value, "tail"))
        {
          aQ->dropMethod = Q_DropTail_c;
        }
      else
        {
          fprintf (stderr, "Don't support drop method %s\n", value);
          assert (0);
        }
    }
      else if (util_strequal (attribute, "flowtype"))
    {
      if (util_strequal (value, "srcip"))
        {
          aQ->flowType = Pkt_SrcIpFlow_c;
        }
      else if (util_strequal (value, "destip"))
        {
          aQ->flowType = Pkt_DestIpFlow_c;
        }
      else if (util_strequal (value, "srcdestip"))
        {
          aQ->flowType = Pkt_SrcDestIpFlow_c;
        }
      else if (util_strequal (value, "srcdesttcpip"))
        {
          aQ->flowType = Pkt_SrcDestTcpIpFlow_c;
        }
      else if (util_strequal (value, "desttcpip"))
        {
          aQ->flowType = Pkt_DestTcpIpFlow_c;
        }
      else
        {
          printf ("Unknown flowtype:%s\n", value);
          assert (0);
        }
    }
      else
    {
      printf ("PANIC: Don't support construct %s in queue definition\n",
          attribute);
      assert (0);
    }
    }

  if (aQ->type == Q_QueueTypeCos_c)
    {
      if (aQ->numClasses == -1)
    {
      printf ("Panic, did not assigned number of classes for queue\n");
      assert (0);
    }
      else
    {
      aQ->cosQ = Q_CosAlloc (aQ->numClasses);
    }
    }
  else if (aQ->type == Q_QueueTypeFlow_c)
    {
      if (aQ->flowType == Pkt_SrcIpFlow_c)
    {
      aQ->flowQ = Q_DrrAlloc (Pkt_SrcIpFlowCmp, Pkt_SrcIpFlowHash);
    }
      else if (aQ->flowType == Pkt_DestIpFlow_c)
    {
      aQ->flowQ = Q_DrrAlloc (Pkt_DestIpFlowCmp, Pkt_DestIpFlowHash);
    }
      else if (aQ->flowType == Pkt_SrcDestIpFlow_c)
    {
      aQ->flowQ =
        Q_DrrAlloc (Pkt_SrcDestIpFlowCmp, Pkt_SrcDestIpFlowHash);
    }
      else if (aQ->flowType == Pkt_DestTcpIpFlow_c)
    {
      aQ->flowQ =
        Q_DrrAlloc (Pkt_DestTcpIpFlowCmp, Pkt_DestTcpIpFlowHash);
    }
      else if (aQ->flowType == Pkt_SrcDestTcpIpFlow_c)
    {
      aQ->flowQ =
        Q_DrrAlloc (Pkt_SrcDestTcpIpFlowCmp, Pkt_SrcDestTcpIpFlowHash);
    }
      else
    {
      assert (0);
    }
    }
  else
    {
      printf ("Panic, queue %s does not have meaningful type\n", aQ->name);
    }
  Hash_Insert (queueNameToQueueTable, (char *) queueName, (char *) aQ);

  return 0;
}


/**
  * \brief Iterate over all distinct L4 rules, build BDDs
  * 
  */

static int
populateL4BddInfo (Evl_L4Manager_t * L4Mgr)
{
  int i;
  int L4id;
  var_set_t *thisL4RulesL7Set;
  bdd_t *L4Bdd;
  Rlp_L4Check_t *L4Check;

  for (i = 0; i < array_n (L4Mgr->L4RuleArray); i++)
    {

      L4Check = array_fetch (Rlp_L4Check_t *, L4Mgr->L4RuleArray, i);
      L4Bdd =
    Evl_BuildBddFromL4Formula (L4Check, L4Mgr->mgr->defineTable,
                   L4Mgr->bddMgr);
      array_insert_last (bdd_t *, L4Mgr->ruleToL4Bdd, L4Bdd);

      if (Hash_Lookup
      (L4Mgr->distinctL4RulesTable, (char *) L4Bdd, (char **) &L4id))
    {
      // we've seen this L4 rule before, so just update the set
      // of corresp rules
      thisL4RulesL7Set =
        array_fetch (var_set_t *, L4Mgr->L4RuleIdToL7ruleSetTable, L4id);
      var_set_set_elt (thisL4RulesL7Set, i);
    }
      else
    {
      // this is a new L4 rule
      L4id = L4Mgr->numDistinctL4Rules;
      Hash_Insert (L4Mgr->distinctL4RulesTable, (char *) L4Bdd,
             (char *) L4id);
      L4Mgr->numDistinctL4Rules++;
      thisL4RulesL7Set = var_set_new (L4Mgr->numAllRules);
      var_set_set_elt (thisL4RulesL7Set, i);
      array_insert_last (var_set_t *, L4Mgr->L4RuleIdToL7ruleSetTable,
                 thisL4RulesL7Set);
    }
    }
  return 0;
}


/**
  * \brief  Free an array of BDDs
  * 
  */

static int
bddArrayFree (array_t * bdds)
{
  int i;
  for (i = 0; i < array_n (bdds); i++)
    {
      bdd_t *aBdd = array_fetch (bdd_t *, bdds, i);
      bdd_free (aBdd);
    }
  array_free (bdds);
  return 0;
}


/**
  * \brief  Free an L4 Manager
  * 
  */

int
Evl_ManagerFree (Evl_Manager_t * result )
{
  /// \todo implement this function
  return 0;
}


/**
  * \brief  Given an array of Rlp_Formula_t's, assumed to be L7 rules,
  * return an Evl_ContentMgr_t.
  * 
  */

Evl_ContentMgr_t *
Evl_BuildContentMgr (array_t * L7CheckArray)
{
  Evl_ContentMgr_t *result = Evl_AllocContentMgr ();

  int contentId = 0;        // this var indexes the distinct byte strings
  st_table *stringToId = result->stringToId;
  st_table *idToString = result->idToString;
  array_t *idToRules = result->idToRules;

  st_generator *stGen;

  st_table *contentChecks;  // this will hold content entries in a formula
  int ruleIndex;

  for (ruleIndex = 0; ruleIndex < array_n (L7CheckArray); ruleIndex++)
    {

      array_t *L7ContentChecks =
    array_fetch (array_t *, L7CheckArray, ruleIndex);

      /// \todo: ignore nocase directive for now
      contentChecks = Rlp_L7CheckGetContentChecks (L7ContentChecks);

      Rlp_ContentCheck_t *contentCheck;
      util_byte_array_t *content;
      int maxLength = -1;
      util_byte_array_t *maxString = NIL (util_byte_array_t);
      st_foreach_item (contentChecks, stGen, (char **) &contentCheck,
               (char **) 0)
      {
    content = contentCheck->content;
    // if the check is negated, we don't want to consider the string - 
    // it should not appear in the DFA mappping to this rule, since
    // that will lead to a wasted check.  we also don't want to 
    // consider its length towards deciding whether or not to attach it
    // to the short strings
    if (!contentCheck->negated)
      {
        if (!Hash_Lookup
        (stringToId, (char *) content, (char **) &contentId))
          {

        contentId = st_count (stringToId);
        Hash_Insert (stringToId, (char *) content, (char *) contentId);
        Hash_Insert (idToString, (char *) contentId, (char *) content);

        array_t *rulesForThisString = array_alloc (int, 0);
        array_insert_last (int, rulesForThisString, ruleIndex);
        array_insert_last (array_t *, idToRules, rulesForThisString);
          }
        else
          {
        updateIdToRules (idToRules, contentId, ruleIndex);
          }
        if (maxLength < content->length)
          {
        maxLength = content->length;
        maxString = content;
          }
      }
      }
      array_insert_last (int, result->maxLengthArray, maxLength);
      array_insert_last (util_byte_array_t *, result->maxLengthStringsArray,
             maxString);
    }
  result->numStrings = st_count (stringToId);
  result->stringArray = array_alloc (util_byte_array_t *, result->numStrings);

  int id;
  util_byte_array_t *string;
  st_foreach_item (stringToId, stGen, (char **) &string, (char **) &id)
  {
    array_insert (util_byte_array_t *, result->stringArray, id, string);
  }

  return result;
}


/**
  * \brief  Update the id to rules array
  * 
  */

static int
updateIdToRules (array_t * idToRules, int contentId, int ruleIndex)
{
  array_t *rules = array_fetch (array_t *, idToRules, contentId);
  // there is a chance that a string may appear more then once
  // in a rule, so we have to make sure ruleIndex is not already
  // in rules
  int i;
  for (i = 0; i < array_n (rules); i++)
    {
      int tmpIndex = array_fetch (int, rules, i);
      if (tmpIndex == ruleIndex)
    {
      // it's already present, so return
      return 1;
    }
    }
  array_insert_last (int, rules, ruleIndex);
  return 0;
}


/**
  * \brief  Allocate a content manager structure
  * 
  */

Evl_ContentMgr_t *
Evl_AllocContentMgr ()
{
  Evl_ContentMgr_t *result =
    (Evl_ContentMgr_t *) malloc (sizeof (Evl_ContentMgr_t));
  result->numStrings = 0;
  result->stringToId =
    Hash_InitTable ( (int(*)() ) util_byte_array_cmp, (int(*)() ) util_byte_array_hash);
  result->idToString = Hash_InitTable ( (int(*)() ) st_numcmp, (int(*)()) st_numhash);
  result->idToRules = array_alloc (array_t *, 0);
  result->maxLengthArray = array_alloc (int, 0);
  result->maxLengthStringsArray = array_alloc (util_byte_array_t *, 0);

  return result;
}


/**
  * \brief  Print a content manager
  * 
  */

void
Evl_PrintContentMgr (Evl_ContentMgr_t * aCM)
{
/*
  printf("Printing a content manager\n");
  printf("There are %d distinct strings\n", aCM->numStrings );
  printf("Here are the strings to ids\n");
  st_generator *stGen;
  st_foreach_item( aCM->stringToId, stGen, (char **) & aString, (char **) & id ) {
    printf("String: ");
    util_byte_array_print( aString );
    printf(" has id %d\n", id );
  }
*/
  int i, j;
  int maxNumOfRules = 0;
  int indexOfMaxRules = -1;
  for (i = 0; i < array_n (aCM->idToRules); i++)
    {
      // printf("String with id %d is associated with rules:\n", i );
      array_t *rules = array_fetch (array_t *, aCM->idToRules, i);
      for (j = 0; j < array_n (rules); j++)
    {
      // int aRule = array_fetch( int, rules, j );
      // printf(" %d ", aRule );
      // char *text = array_fetch( char *, aMgr->rawRules, aRule );
      // printf("\nin text this is %s\n", text );
    }

      if (array_n (rules) > maxNumOfRules)
    {
      maxNumOfRules = array_n (rules);
      indexOfMaxRules = i;
    }
      printf ("\n\n");
      printf ("There are %d distinct strings\n", aCM->numStrings);
    }
  printf
    ("The most rules associated with any string is %d and the string's id is %d\n",
     maxNumOfRules, indexOfMaxRules);
  if (indexOfMaxRules != -1)
    {
      printf ("The rules are \n");
      array_t *rules =
    array_fetch (array_t *, aCM->idToRules, indexOfMaxRules);
      for (j = 0; j < array_n (rules); j++)
    {
      int aRule = array_fetch (int, rules, j);
      printf (" %d ", aRule);
    }
      printf ("The string is :\n");
      util_byte_array_t *aString;
      Hash_Lookup (aCM->idToString, (char *) indexOfMaxRules,
         (char **) &aString);
      util_byte_array_print (aString);
    }
}


/**
  * \brief  Initialize the content manager field of the manager
  * 
  */

static void
populateContentManager (Evl_L4Manager_t * L4Mgr)
{
  L4Mgr->contentChecks = array_alloc (array_t *, 0);

  int i;
  for (i = 0; i < array_n (L4Mgr->L7RuleArray); i++)
    {
      Rlp_Formula_t *aFormula =
    array_fetch (Rlp_Formula_t *, L4Mgr->L7RuleArray, i);
      array_t *aContentCheckArray =
    Rlp_BuildContentCheckArrayFromL7Formula (aFormula);
      array_insert_last (array_t *, L4Mgr->contentChecks, aContentCheckArray);
    }
  L4Mgr->cm = Evl_BuildContentMgr (L4Mgr->contentChecks);
}


/**
  * \brief  Build the lookup table for rules with short strings
  * 
  * Right now we could merge it with the table
  * for rules with no content checks, but that has many 
  * more rules per equiv class, and at some point a custom
  * structure will be needed for it.
  * 
  */

static int
buildShortStringLookupTable (Evl_L4Manager_t * mgr)
{
  int i;

  var_set_t *shortStringsRulesSet = var_set_new (mgr->numAllRules);
  for (i = 0; i < mgr->numAllRules; i++)
    {
      int maxLength = array_fetch (int, mgr->cm->maxLengthArray, i);
      // check against -1 to remove all the no-content checks
      // e.g., the icmp checks, sameip, etc
      if (maxLength < Evl_MinLengthFsmString && maxLength != -1)
    {
      var_set_set_elt (shortStringsRulesSet, i);
    }
    }

  st_table *processedTable = Hash_InitTable ( (int(*)() ) Evl_BddCmp, (int(*)() ) Evl_BddHash);
  array_t *shortStringRuleArray = array_alloc (bdd_t *, 0);
  array_t *shortStringRuleVarsArray = array_alloc (int, 0);
  int L4id;
  for (i = 0; i < mgr->numAllRules; i++)
    {
      bdd_t *L4Bdd = array_fetch (bdd_t *, mgr->ruleToL4Bdd, i);
      bool found = Hash_Lookup (mgr->distinctL4RulesTable, (char *) L4Bdd,
                  (char **) &L4id);
      assert (found != false);
      if (Hash_Lookup (processedTable, (char *) L4Bdd, (char **) 0))
    {
      continue;
    }
      Hash_Insert (processedTable, (char *) L4Bdd, (char *) 0);
      var_set_t *thisL4RulesL7Set =
    array_fetch (var_set_t *, mgr->L4RuleIdToL7ruleSetTable, L4id);
      var_set_t *tmpSet = var_set_new (mgr->numAllRules);
      var_set_and (tmpSet, shortStringsRulesSet, thisL4RulesL7Set);
      if (var_set_is_empty (tmpSet))
    {
      var_set_free (tmpSet);
      continue;
    }
      var_set_free (tmpSet);

      array_insert_last (bdd_t *, shortStringRuleArray, L4Bdd);
      bdd_t *ruleVar = bdd_get_variable (mgr->bddMgr, L4id + 96);
      array_insert_last (bdd_t *, shortStringRuleVarsArray, ruleVar);
    }
  if (array_n (shortStringRuleArray) > 0)
    {
      mgr->shortStringRuleTable =
    createLookupTable (mgr, shortStringRuleArray,
               shortStringRuleVarsArray);
      // intersect out rules from shortStringRuleTable
      int j;
      for (j = 0; j < mgr->shortStringRuleTable->numClasses; j++)
    {
      var_set_t *tmpSet = var_set_new (mgr->numAllRules);
      var_set_and (tmpSet, mgr->shortStringRuleTable->ruleSets[j],
               shortStringsRulesSet);
      var_set_free (mgr->shortStringRuleTable->ruleSets[j]);
      mgr->shortStringRuleTable->ruleSets[j] = tmpSet;
      /* if ( evlDebug ) {
         printf("Short string class %d has %d elements\n", 
         j, 
         var_set_n_elts( mgr->shortStringRuleTable->ruleSets[j] ) );
         printRuleSet( mgr, mgr->shortStringRuleTable->ruleSets[j] );
         }
       */
    }
      // we'll traverse the short string lookup table via the
      // rule array entries, rather than the varsets
      Evl_L4LookupTableAddRuleArrays (mgr->shortStringRuleTable);
    }
  Hash_FreeTable (processedTable);
  return 0;
}


/**
  * \brief  Code for printing a ruleset
  * 
  */

static int
printRuleSet (Evl_L4Manager_t * mgr, var_set_t * ruleSet)
{
  int i;
  assert (mgr->numAllRules == ruleSet->n_elts);
  for (i = 0; i < mgr->numAllRules; i++)
    {
      if (!var_set_get_elt (ruleSet, i))
    {
      continue;
    }
      int globalIndex = array_fetch (int, mgr->tcpIdToGlobalId, i);
      char *rawRule = array_fetch (char *, mgr->mgr->rawRules, globalIndex);
      printf ("Rule %d is %s\n", i, rawRule);
    }
  return 0;
}


/**
  * \brief  Function for building an FSM over the long strings
  * in a manager.
  */

static void
populateLongStringsFsm (Evl_L4Manager_t * mgr)
{
  int i;
  var_set_t *aSet;
  array_t *byteArrayArray = array_alloc (util_byte_array_t *, 0);
  st_table *longByteArrayHash =
    Hash_InitTable ( (int(*)() ) util_byte_array_cmp, (int(*)() ) util_byte_array_hash);
  for (i = 0; i < mgr->numAllRules; i++)
    {
      int maxLength = array_fetch (int, mgr->cm->maxLengthArray, i);
      util_byte_array_t *maxString =
    array_fetch (util_byte_array_t *, mgr->cm->maxLengthStringsArray, i);
      if (maxLength >= Evl_MinLengthFsmString)
    {
      if (Hash_Lookup
          (longByteArrayHash, (char *) maxString, (char **) &aSet))
        {
          var_set_set_elt (aSet, i);
        }
      else
        {
          var_set_t *newSet = var_set_new (mgr->numAllRules);
          var_set_set_elt (newSet, i);
          Hash_Insert (longByteArrayHash, (char *) maxString,
             (char *) newSet);
          array_insert_last (util_byte_array_t *, byteArrayArray,
                 maxString);
        }
    }
    }
  Evl_Fsm_t *fsm = Evl_BuildPrefixAutomaton (byteArrayArray);
  mgr->fsm = fsm;
  populateMgrFsmAcceptingStates (mgr, longByteArrayHash);
}


/**
  * \brief  Create mapping from fsm accepting states to rules
  */

static void
populateMgrFsmAcceptingStates (Evl_L4Manager_t * L4Mgr,
                   st_table * longByteArrayHash)
{
  Evl_Fsm_t *fsm = L4Mgr->fsm;
  var_set_t *aRuleSet;
  L4Mgr->fsmAcceptingStates = (var_set_t *) var_set_new (fsm->N);
  L4Mgr->fsmStateToRuleSet =
    (var_set_t **) malloc (sizeof (var_set_t *) * fsm->N);
  int i;
  for (i = 0; i < fsm->N; i++)
    {
      array_t *acceptedStrings = array_fetch (array_t *, fsm->finalStates, i);
      if (acceptedStrings == NIL (array_t))
    {
      L4Mgr->fsmStateToRuleSet[i] = NIL (var_set_t);
    }
      else
    {
      var_set_set_elt (L4Mgr->fsmAcceptingStates, i);
      L4Mgr->fsmStateToRuleSet[i] = var_set_new (L4Mgr->numAllRules);
      int j;
      for (j = 0; j < array_n (acceptedStrings); j++)
        {
          int aStringId = array_fetch (int, acceptedStrings, j);
          util_byte_array_t *aString = fsm->stateIdToPrefix[aStringId];
          bool found = Hash_Lookup (longByteArrayHash, (char *) aString,
                      (char **) &aRuleSet);
          assert (found != false);
          var_set_or (L4Mgr->fsmStateToRuleSet[i],
              L4Mgr->fsmStateToRuleSet[i], aRuleSet);
        }
    }
    }

/*
  if ( evlDebug) {
    for ( i = 0 ; i < fsm->N ; i++ ) {
      if ( ( L4Mgr->fsmStateToRuleSet[i] != NIL( var_set_t ) ) &&
             var_set_n_elts( L4Mgr->fsmStateToRuleSet[i] ) > 0 ) {
        printf("State %d corresponds to %d rules\n", i, var_set_n_elts( L4Mgr->fsmStateToRuleSet[i] ) );
        if ( var_set_n_elts( L4Mgr->fsmStateToRuleSet[i] ) > 5 ) {
          printf("Lots of rules here - they are \n");
          int j;
          for ( j = 0 ; j < L4Mgr->numAllRules; j++ ) {   
            if ( var_set_get_elt( L4Mgr->fsmStateToRuleSet[i], j ) ) {
          int globalIndex = array_fetch( int, L4Mgr->tcpIdToGlobalId, j );
              printf("\t%s\n", array_fetch( char *, L4Mgr->mgr->rawRules, globalIndex ) );
            }
          }
        }
      }
    }
  }
*/
}


/**
  * \brief  Populate raw rules and macros array
  */

static int
populateRawRulesAndMacros (Evl_Manager_t * mgr, char *ruleFile)
{
  mgr->rawRulesAndMacrosArray = util_process_file (ruleFile);
  return 0;
}


/**
  * \brief  Iterate over rules to find the ones that have no
  * content checks.
  * 
  */

static int
buildNoContentCheckTable (Evl_L4Manager_t * mgr)
{
  int i;
  var_set_t *noContentChecksSet = var_set_new (mgr->numAllRules);
  array_t *bddArray = array_alloc (bdd_t *, 0);
  array_t *bddVarArray = array_alloc (bdd_t *, 0);
  st_table *processedTable = Hash_InitTable ( (int(*)() ) Evl_BddCmp, (int(*)() ) Evl_BddHash);
  for (i = 0; i < mgr->numAllRules; i++)
    {
      int maxLength = array_fetch (int, mgr->cm->maxLengthArray, i);
      if (maxLength != -1)
    {
      continue;
    }
      // this rule has no content checks
      var_set_set_elt (noContentChecksSet, i);
      // Rlp_L4Check_t *l4Entry = array_fetch( Rlp_L4Check_t *, mgr->L4RuleArray, i );
      bdd_t *thisRuleBdd = array_fetch (bdd_t *, mgr->ruleToL4Bdd, i);
      if (Hash_Lookup (processedTable, (char *) thisRuleBdd, (char **) 0))
    {
      continue;
    }
      Hash_Insert (processedTable, (char *) thisRuleBdd, (char *) 0);
      array_insert_last (bdd_t *, bddArray, thisRuleBdd);
      int bddId;
      bool found = Hash_Lookup (mgr->distinctL4RulesTable, (char *) thisRuleBdd,
                  (char **) &bddId);
      assert (found != false);
      bdd_t *ruleVarBdd = bdd_get_variable (mgr->bddMgr, bddId + 96);
      array_insert_last (bdd_t *, bddVarArray, ruleVarBdd);
    }

  Evl_L4LookupTable_t *noContentCheckTable =
    createLookupTable (mgr, bddArray, bddVarArray);

  for (i = 0; i < noContentCheckTable->numClasses; i++)
    {
      /// \todo: this code looks redundant, since noContentCheckTable is a subset of coContentCheckSet
      var_set_and (noContentCheckTable->ruleSets[i],
           noContentCheckTable->ruleSets[i], noContentChecksSet);
    }


  // need to do after the ANDING is done!
  Evl_L4LookupTableAddRuleArrays (noContentCheckTable);
  mgr->noContentCheckTable = noContentCheckTable;
  return 0;
}


/**
  * \brief  Add rule arrays in addition to the sets
  * 
  */

int
Evl_L4LookupTableAddRuleArrays (Evl_L4LookupTable_t * table)
{
  if (table == NIL (Evl_L4LookupTable_t))
    {
      return 0;
    }
  table->ruleArrays =
    (util_int_array_t **) malloc (table->numClasses *
                  sizeof (util_int_array_t *));

  table->ruleArrayMin = (int *) malloc (table->numClasses * sizeof (int));

  table->ruleArrayMax = (int *) malloc (table->numClasses * sizeof (int));

  int i;
  for (i = 0; i < table->numClasses; i++)
    {
      table->ruleArrayMin[i] = -1;
      table->ruleArrayMax[i] = -1;
      table->ruleArrays[i] = var_set_to_int_array (table->ruleSets[i]);
      int length = table->ruleArrays[i]->length;
      if (length > 0)
    {
      table->ruleArrayMin[i] = (table->ruleArrays[i]->entries)[0];
      table->ruleArrayMax[i] = (table->ruleArrays[i]->entries)[length-1];
    }
    }
  return 0;
}


/**
  * \brief  Build the content manager with all strings projected down to lower case.
  * 
  * We use this in the following way:  we have a number of checks that are
  * case-insensitive, and a number that are case-sensitive.  We could
  * build two DFA, and then run the checks twice.  On the other hand
  *     we could make ALL of the DFA checks case-insensitive, and
  * then in the final detailed check, take case into account.  We choose the
  * latter since it means only a single pass over the packet. There is a 
  * possibility of false positives from this scheme, e.g., a case specific search
  * search for "abc" will be matched by "ABC"; I don't have a detailed analysis/study
  * of this pheonomenon, but it seems to be unlikely.
  *
  * \sa evalContentCheck
  */

Evl_ContentMgr_t *
Evl_BuildContentMgrForLowerCaseStrings (Evl_ContentMgr_t * aCM)
{
  Evl_ContentMgr_t *result = Evl_AllocContentMgr ();

  st_generator *stGen;
  util_byte_array_t *aString, *lowerCaseString;
  int i, anId, tmpId, lowerCaseStringId;

  array_t *newArray, *existingArray;
  st_foreach_item (aCM->stringToId, stGen, (char **) &aString,
           (char **) &anId)
  {
    util_byte_array_t *lowerCaseString =
      util_byte_array_to_lower_case (aString);
    if (!
    (Hash_Lookup
     (result->stringToId, (char *) lowerCaseString,
      (char **) &lowerCaseStringId)))
      {
    lowerCaseStringId = st_count (result->stringToId);
    result->numStrings++;
    Hash_Insert (result->stringToId, (char *) lowerCaseString,
           (char *) lowerCaseStringId);
    Hash_Insert (result->idToString, (char *) lowerCaseStringId,
           (char *) lowerCaseString);
    newArray = array_alloc (int, 0);
    array_insert_last (array_t *, result->idToRules, newArray);
      }
    else
      {
    // printf("\nDUP: ");
    // util_byte_array_print( lowerCaseString );
    // printf("\t:\t");
    // util_byte_array_print( aString );
    // printf("\n");
    util_byte_array_free (lowerCaseString);
      }
    newArray = array_fetch (array_t *, result->idToRules, lowerCaseStringId);
    existingArray = array_fetch (array_t *, aCM->idToRules, anId);
    for (i = 0; i < array_n (existingArray); i++)
      {
    tmpId = array_fetch (int, existingArray, i);
    array_insert_last (int, newArray, tmpId);
      }
  }

  result->stringArray = array_alloc (util_byte_array_t *,
                     st_count (result->stringToId));
  st_foreach_item (result->stringToId,
           stGen,
           (char **) &lowerCaseString, (char **) &lowerCaseStringId)
  {
    array_insert (util_byte_array_t *, result->stringArray,
          lowerCaseStringId, lowerCaseString);
  }
  for (i = 0; i < array_n (aCM->maxLengthArray); i++)
    {
      int length = array_fetch (int, aCM->maxLengthArray, i);
      util_byte_array_t *longString = array_fetch (util_byte_array_t *,
                           aCM->maxLengthStringsArray,
                           i);
      array_insert_last (int, result->maxLengthArray, length);
      if (longString == NIL (util_byte_array_t))
    {
      array_insert_last (util_byte_array_t *,
                 result->maxLengthStringsArray,
                 NIL (util_byte_array_t));
      continue;
    }
      int tmpStringId;
      lowerCaseString = util_byte_array_to_lower_case (longString);
      Hash_Lookup (result->stringToId, (char *) lowerCaseString,
         (char **) &tmpStringId);
      util_byte_array_free (lowerCaseString);
      Hash_Lookup (result->idToString, (char *) tmpStringId,
         (char **) &lowerCaseString);
      array_insert_last (util_byte_array_t *, result->maxLengthStringsArray,
             lowerCaseString);
    }

  // st_foreach_item( aCM->stringToId, stGen, (char **) & aString, (char **) & anId ) {
  //   printf("\nUPPER:");
  //   util_byte_array_print( aString );
  // }
  // st_foreach_item( result->stringToId, stGen, (char **) & aString, (char **) & anId ) {
  //   printf("\nLOWER:");
  //   util_byte_array_print( aString );
  // }

  return result;
}


/**
  * \brief Check to see what type of rule this is.
  */

static bool
checkRuleMode (char *rawRule, char *mode)
{
  while (isspace (*rawRule))
    {
      rawRule++;
    }

  // first check to see if it's a preprocessing rule 
  if (util_strequalN ("preprocess", mode, strlen ("preprocess")) &&
      util_strequalN ("preprocess", rawRule, strlen ("preprocess")))
    {
      return 1;
    }

  // we're not checking for a preprocessing rule
  if (util_strequalN ("preprocess", rawRule, strlen ("preprocess")))
    {
      rawRule += strlen ("preprocess");
      while (isspace (*rawRule))
    {
      rawRule++;
    }
    }

  bool result = util_strequalN (rawRule, mode, strlen (mode));
  return result;
}


/**
  * \brief Determine the number of preprocessing rules.
  */

static void
computeNumberOfPreprocessRules (Evl_Manager_t * mgr)
{
  int i;
  for (i = 0; i < array_n (mgr->rawRules); i++)
    {
      char *rawRule = array_fetch (char *, mgr->rawRules, i);
      while (*rawRule == ' ')
    {
      rawRule++;
    }
      if (!util_strequalN (rawRule, "preprocess", strlen ("preprocess")))
    {
      continue;
    }
      else
    {
      mgr->numPreprocessRules++;
    }
    }
}