/***** $Id$**** mwm.c   - A Modified Wu-Manber Style Multi-Pattern Matcher**** Copyright (C) 2002 Sourcefire,Inc** Marc Norton****  ** This program is free software; you can redistribute it and/or modify** it under the terms of the GNU General Public License as published by** the Free Software Foundation; either version 2 of the License, or** (at your option) any later version.**** This program is distributed in the hope that it will be useful,** but WITHOUT ANY WARRANTY; without even the implied warranty of** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the** GNU General Public License for more details.**** You should have received a copy of the GNU General Public License** along with this program; if not, write to the Free Software** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.********** A Fast Multi-Pattern Search Engine** ** This algorithm is based on the Wu & Manber '94 paper. This algorithm is not an ** exact implementation in that it uses a standard one or 2 byte Bad Character shift table,** whereas Wu & Manber used a 2 byte Bad Characeter shift table. This implementation** also uses a fixed 2 byte prefix hash table, Wu & Manber used a variable size  ** 2 byte hash. Hash groups are defined as in Wu & Manber.  The Pattern groups are searched ** using a reverse string compare as in Wu & Manber. **** A pattern match tracking mechanism has been added to reduce the effect of DOS attacks, ** and generally improve the worst case performanmce scenario.  This feature is ** enabled/disabled via BITOP_TEST and requires the bitop.h file.**** ** Initial Version - Marc Norton - April 2002 ****   Algorithm:       This is a simplified implementation of Wu & Manber's '92 and '94 papers.       1) A multi-pattern Boyer-Moore style bad character or word shift is done until      a possible pattern is detected.         2) Hashing is used on the 2 character prefix of the current text to index into a      group of patterns with the same prefix. Patterns must be sorted. Wu & Manber used      the last 2 characters of the psuedo multi-pattern minimum length. Either works fine.          3) A reverse string compare is performed against each pattern in the      group to see if any of the patterns match the current text prefix.                 Algorithm Steps     Preprocess:            a) Sort The Patterns, forming a sorted list of patterns.     b) Build a hash table of the patterns as follows: For each pattern find it's        hash, in the hash index vector save this patterns index, now count how         many patterns following this one have the same hash as it, save this value         with the 1st pattern that has this hash.     c) Build a Boyer-Moore style bad Character shift table, using the min shift from         all patterns for the shift value for each characters in the shift table. For the 	purposes of the Bad Character Shift we assume all patterns are the same length as the        shortest pattern.  This works quite well in practice.  Also build a Bad Word        shift table.   Search:    a) Perform Boyer-Moore Bad Character or Bad Word Shift loop to find a possible        pattern match.    b) Check if a hashed pattern group entry exists for this possible patterns prefix,        If no pattern hash exists for this suffix shift go to d)    c) If a hash exists, test all of the patterns in the pattern group to see       which ones if any match the text suffix.  Use a reverse string comparison       to benefit from the increased likelihood of misses at the ends of the string.       This tidbit is based on Boyer-Moore searching.  Uses bit flags to eliminate       previously hit matches from contention.  This provides a better worst case       scenario for this setwise pattern matching.     d) Use a one character shift and go back to a)   Pattern Matcher Selection Heuristics:      We can use A Boyer-Moore for small sets of patterns.  We can use one of 3 matchers   for larger sets.  When the minimum pattern size within the pattern group is one   character we use the version without a Boyer-Moore bad character or bad word    shift.  When we have groups with a minimum pattern size of 2 or more characters    we use the version with the bad character shift.  When we have groups with a minimum   pattern size of 2 or more characters and the number of patterns small-medium we can use   the version with the bad word shift.  More testing is needed to help determine the optimal   switching points between these algorithms.         Case vs NoCase:     We convert all patterns and search texts to one case, find a match, and if case is     important we retest just the pattern characters against the text in exact mode.   Algorithm Strengths:    Performance is limited by the minimum pattern length of the group. The bigger    the minumum, the more the bad character shift helps, and the faster the search.      The minimum pattern length also determines whether a tree based search is faster or slower.        Small groups of patterns 10-100 with a large minimum pattern size (3+ chars) get the best    performanc.  Oh, if it were all that simple.     Improvements or Variations:       where to start ...much more to come...   Notes:    Observations:       This algorithm is CPU cache sensitive, aren't they all.            Ancestory:   The structure of the API interface is based on the interface used by the samples    from Dan Gusfields book.   Some References:    Boyer-Moore   - The original and still one of the best.    Horspool      - Boyer-Moore-Horspool.    Sunday        - Quicksearch and the Tuned Boyer-Moore algorithm.    Wu and Manber - A Fast Multi-Pattern Matcher '94   -- agrep, fgrep, sgrep    Aho & Corasick- State machine approach, very slick as well.    Dan Gusfield  - Algorithms on strings, trees, and sequences.    Steven Graham -     Crochemere    -      NOTES:     4-2002    - Marc Norton               Initial implementation      5/23/2002 - Marc Norton -                Added Boyer-Moore-Horspool locally, so it's inlined.               We use a simple <5 pattern count to decide to use the               BMH method over the MWM method.  This is not always right               but close enough for now. This may get replaced with the standard               Boyer-Moore in mString - the standard Boyer Moore may protect                better against some types of DOS'ing attempts.   11/02    -  Fixed bug for multiple duplicate one byte patterns.    10/03    -  Changed ID to a void * for better 64 bit compatability.	    -  Added BITOP_TEST to make testing rotuines easier.	    -  Added Windows __inline command back into bitops.	    -  Added Standalone Windows support for UNIT64 for standalone testing            -  modified mwm.c, mwm.h, bitop.h   10/28/03 -  Fixed bug in mwmPrepHashedPatternGroups(), it was setting resetting psIID               as it walked through the patterns counting the number of patterns in each group.	       This caused an almost random occurrence of an already tested rule's bitop	       flag to cause another rule to never get tested.   12/08/03 -  Removed the usage of NumArray1, it was unneccessary, reverted back to NumArray                mwmPrepHashedPatternGroups:               When counting one byte patterns in 'ningroup' added a check for psLen==1               Broke out common search code into an inline routine ..group2()   07/08/05 - Steven Sturges -               Fixed issue when a case-sensitive pattern was missed when               a incorrect case instance occurs before the correct case               instance.*//***  INCLUDES*/#ifdef HAVE_CONFIG_H#include "config.h"#endif#include <stdio.h>#include <string.h>#include <stdlib.h>#include <ctype.h>#include "mwm.h"int FatalError( char *, ... );/**   Count of how many byte have been scanned,*   this gets reset each time a user requests this tidbit,*   this counts across all pattern groups.*/static UINT64  iPatCount=0;UINT64 mwmGetPatByteCount(){   return  iPatCount;}void mwmResetByteCount(){   iPatCount=0;}/*** Translation Table */static unsigned char xlatcase[256];/*** NoCase Buffer -This must be protected by a mutex if multithreaded calls to** the pattern matcher occur or else we could have the user pass one of these ** for each pattern matcher instance from his stack or heap.*/static unsigned char S[65536];/***/static void init_xlatcase(){   int i;   for(i=0;i<256;i++)   {     xlatcase[ i ] =  toupper(i);   }}/***/static INLINE void ConvCaseToUpper( unsigned char *s, int m ){     int  i;     for( i=0; i < m; i++ )     {       s[i] = xlatcase[ s[i] ];     }}/***/static INLINE void ConvCaseToUpperEx( unsigned char * d, unsigned char *s, int m ){     int i;     for( i=0; i < m; i++ )     {        d[i] = xlatcase[ s[i] ];     }}/***  Boyer-Moore-Horsepool for small pattern groups*    */#undef COPY_PATTERNSHBM_STRUCT * hbm_prepx(HBM_STRUCT *p, unsigned char * pat, int m){     int     k;     if( !m ) return 0;     if( !p ) return 0;#ifdef COPYPATTERN     p->P = (unsigned char*)malloc( m + 1 )     if( !p->P ) return 0;     memcpy(p->P,pat,m);#else     p->P = pat;#endif     p->M = m;     /* Compute normal Boyer-Moore Bad Character Shift */     for(k = 0; k < 256; k++) p->bcShift[k] = m;     for(k = 0; k < m; k++)   p->bcShift[pat[k]] = m - k - 1;     return p;}/***/HBM_STRUCT * hbm_prep(unsigned char * pat, int m){     HBM_STRUCT    *p;     p = (HBM_STRUCT*)malloc( sizeof(HBM_STRUCT) );     if( !p ) return 0;     return hbm_prepx( p, pat, m );}#ifdef XXX_NOT_USED/***/static void hbm_free( HBM_STRUCT *p ){    if(p)    {#ifdef COPYPATTERN       if( p->P )free(p->P);#endif       free(p);    }}#endif/**   Boyer-Moore Horspool*   Does NOT use Sentinel Byte(s)*   Scan and Match Loops are unrolled and separated*   Optimized for 1 byte patterns as well*/static INLINE unsigned char * hbm_match(HBM_STRUCT * px, unsigned char * text, int n){  unsigned char *pat, *t, *et, *q;  int            m1, k;  short    *bcShift;  m1     = px->M-1;  pat    = px->P;  bcShift= px->bcShift;  t  = text + m1;    et = text + n;   /* Handle 1 Byte patterns - it's a faster loop */  if( !m1 )  {    for( ;t<et; t++ )       if( *t == *pat ) return t;    return 0;  }   /* Handle MultiByte Patterns */  while( t < et )  {    /* Scan Loop - Bad Character Shift */    do     {      t += bcShift[*t];      if( t >= et )return 0;;      t += (k=bcShift[*t]);            if( t >= et )return 0;    } while( k );    /* Unrolled Match Loop */    k = m1;    q = t - m1;    while( k >= 4 )    {      if( pat[k] != q[k] )goto NoMatch;  k--;      if( pat[k] != q[k] )goto NoMatch;  k--;      if( pat[k] != q[k] )goto NoMatch;  k--;      if( pat[k] != q[k] )goto NoMatch;  k--;    }    /* Finish Match Loop */    while( k >= 0 )    {      if( pat[k] != q[k] )goto NoMatch;  k--;    }    /* If matched - return 1st char of pattern in text */    return q;NoMatch:        /* Shift by 1, this replaces the good suffix shift */    t++;   }  return 0;}/***     mwmAlloc:: Allocate and Init Big hash Table Verions****     maxpats - max number of patterns to support***/void * mwmNew(){   MWM_STRUCT * p = (MWM_STRUCT * )calloc( sizeof(MWM_STRUCT),1 );   if( !p )   {      return 0;   }      init_xlatcase();   p->msSmallest = 32000;   return (void*)p;}/****/void mwmFree( void * pv ){   MWM_STRUCT * p = (MWM_STRUCT * )pv;   if( p )   {     if( p->msPatArray ) free( p->msPatArray );     if( p->msNumArray ) free( p->msNumArray );     if( p->msHash     ) free( p->msHash );     if( p->msShift2   ) free( p->msShift2 );     free( p );   }}/*** mwmAddPatternEx::**** returns -1: max patterns exceeded**          0: already present, uniqueness compiled in**          1: added*/int mwmAddPatternEx( void *pv, unsigned char * P, int m,        unsigned noCase,  unsigned offset, unsigned depth , void * id, int iid ){    MWM_STRUCT *ps = (MWM_STRUCT*)pv;    MWM_PATTERN_STRUCT *plist=0;    MWM_PATTERN_STRUCT *p = (MWM_PATTERN_STRUCT*)calloc(sizeof(MWM_PATTERN_STRUCT),1);    if( !p ) return -1;#ifdef REQUIRE_UNIQUE_PATTERNS    for( plist=ps->plist; plist!=NULL; plist=plist->next )    {       if( plist->psLen == m )       {           if( memcmp(P,plist->psPat,m) == 0 )            {               return 0;  /*already added */           }       }    }#endif    if( ps->plist )    {       for( plist=ps->plist; plist->next!=NULL; plist=plist->next )         ;        plist->next = p;    }    else        ps->plist = p;        /* Allocate and store the Pattern  'P' with NO CASE info*/    p->psPat =  (unsigned char*)malloc( m );    if( !p->psPat ) return -1;    memcpy(p->psPat, P, m );    ConvCaseToUpper( p->psPat, m );    /* Allocate and store the Pattern  'P' with CASE info*/    p->psPatCase =  (unsigned char*)malloc( m );    if( !p->psPatCase ) return -1;    memcpy( p->psPatCase, P, m );    p->psLen    = m;    p->psID     = id;     p->psIID    = iid;    p->psNoCase = noCase;    p->psOffset = offset;    p->psDepth  = depth;    ps->msNoCase += noCase;        ps->msNumPatterns++;    if( p->psLen < (unsigned)ps->msSmallest ) ps->msSmallest= p->psLen;    if( p->psLen > (unsigned)ps->msLargest  ) ps->msLargest = p->psLen;     ps->msTotal   += p->psLen;    ps->msAvg      = ps->msTotal / ps->msNumPatterns;    return 1;}#ifdef OLDSHIT/*** mwmAddPatternEx::**** returns -1: max patterns exceeded**          0: already present, uniqueness compiled in**          1: added*/int mwmAddPatternExOrig( MWM_STRUCT *ps, unsigned char * P, int m,        unsigned noCase,  unsigned offset, unsigned depth ,unsigned id, int iid ){    int kk;    MWM_PATTERN_STRUCT *p;    if( ps->msNumPatterns >= ps->msMaxPatterns )    {        return -1;    }#ifdef REQUIRE_UNIQUE_PATTERNS    for(i=0;i<ps->msNumPatterns;i++)    {       if( ps->msPatArray[i].psLen == m )       {           if( memcmp(P,ps->msPatArray[i].psPat,m) == 0 )            {               return 0;  /*already added */           }       }    }#endif    p = &ps->msPatArray[ ps->msNumPatterns ];    /* Allocate and store the Pattern  'P' with NO CASE info*/    p->psPat =  (unsigned char*)malloc( m );    memcpy(p->psPat, P, m );    ConvCaseToUpper( p->psPat, m );    /* Allocate and store the Pattern  'P' with CASE info*/    p->psPatCase =  (unsigned char*)malloc( m );    memcpy( p->psPatCase, P, m );    p->psLen    = m;    p->psID     = id;     p->psIID    = iid;    p->psNoCase = noCase;    p->psOffset = offset;    p->psDepth  = depth;    ps->msNoCase += noCase;    kk = ps->msNumPatterns;    ps->msNumPatterns++;    if( ps->msPatArray[kk].psLen < (unsigned)ps->msSmallest ) ps->msSmallest= ps->msPatArray[kk].psLen;    if( ps->msPatArray[kk].psLen > (unsigned)ps->msLargest  ) ps->msLargest = ps->msPatArray[kk].psLen;     ps->msTotal   += ps->msPatArray[kk].psLen;