hi_util_hbm.c

Go to the documentation of this file.

/**
**  @file       hi_hbm.c
**  
**  @author     Marc Norton <mnorton@sourcefire.com>
**  
**  @brief      Implementation of a Horspool method of Boyer-Moore
**  
*/

#include <stdlib.h>

#include "hi_util_hbm.h"

/*
*
*  Boyer-Moore-Horspool for small pattern groups
*    
*/
#ifndef WIN32  /* To avoid naming conflict, Win32 will use the hbm_prepx() in mwm.c */
HBM_STRUCT * hbm_prepx(HBM_STRUCT *p, unsigned char * pat, int m)
{
     int     k;

     if( !m ) return 0;
     if( !p ) return 0;


     p->P = pat;

     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;
}
#endif

/*
*
*/
#ifndef WIN32  /* To avoid naming conflict, Win32 will use the hbm_prep() in mwm.c */
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 );
}
#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
*/
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;
}

---