suricata
util-spm-bm.c File Reference
#include "suricata-common.h"
#include "suricata.h"
#include "util-spm-bm.h"
#include "util-spm.h"
#include "util-debug.h"
#include "util-error.h"
#include "util-memcpy.h"
Include dependency graph for util-spm-bm.c:

Go to the source code of this file.

Data Structures

struct  SpmBmCtx_
 

Typedefs

typedef struct SpmBmCtx_ SpmBmCtx
 

Functions

void BoyerMooreCtxToNocase (BmCtx *bm_ctx, uint8_t *needle, uint16_t needle_len)
 Given a BmCtx structure, recreate the pre/suffixes for nocase. More...
 
BmCtxBoyerMooreCtxInit (const uint8_t *needle, uint16_t needle_len)
 Setup a Booyer Moore context. More...
 
BmCtxBoyerMooreNocaseCtxInit (uint8_t *needle, uint16_t needle_len)
 Setup a Booyer Moore context for nocase search. More...
 
void BoyerMooreCtxDeInit (BmCtx *bmctx)
 Free the memory allocated to Booyer Moore context. More...
 
uint8_t * BoyerMoore (const uint8_t *x, uint16_t m, const uint8_t *y, uint32_t n, BmCtx *bm_ctx)
 Boyer Moore search algorithm Is better as the pattern length increases and for big buffers to search in. The algorithm needs a context of two arrays already prepared by prep_bad_chars() and prep_good_suffix() More...
 
uint8_t * BoyerMooreNocase (const uint8_t *x, uint16_t m, const uint8_t *y, uint32_t n, BmCtx *bm_ctx)
 Boyer Moore search algorithm Is better as the pattern length increases and for big buffers to search in. The algorithm needs a context of two arrays already prepared by prep_bad_chars() and prep_good_suffix() More...
 
void SpmBMRegister (void)
 

Detailed Description

Author
Pablo Rincon Crespo pablo.nosp@m..rin.nosp@m.con.c.nosp@m.resp.nosp@m.o@gma.nosp@m.il.c.nosp@m.om

Boyer Moore simple pattern matcher implementation

Boyer Moore algorithm has a really good performance. It need two arrays of context for each pattern that hold applicable shifts on the text to seach in, based on characters not available in the pattern and combinations of characters that start a sufix of the pattern. If possible, we should store the context of patterns that we are going to search for multiple times, so we don't spend time on rebuilding them.

Definition in file util-spm-bm.c.

Typedef Documentation

typedef struct SpmBmCtx_ SpmBmCtx

Function Documentation

uint8_t* BoyerMoore ( const uint8_t *  x,
uint16_t  m,
const uint8_t *  y,
uint32_t  n,
BmCtx bm_ctx 
)

Boyer Moore search algorithm Is better as the pattern length increases and for big buffers to search in. The algorithm needs a context of two arrays already prepared by prep_bad_chars() and prep_good_suffix()

Parameters
ypointer to the buffer to search in
nlength limit of the buffer
xpointer to the pattern we ar searching for
mlength limit of the needle
bmBcpointer to an array of BoyerMooreSuffixes prepared by prep_good_suffix()
bmGspointer to an array of bachars prepared by prep_bad_chars()
Return values
ptrto start of the match; NULL if no match

Definition at line 299 of file util-spm-bm.c.

References ALPHABET_SIZE, BmCtx_::bmBc, BmCtx_::bmGs, m, and unlikely.

Referenced by BoyerMooreSearch().

Here is the caller graph for this function:

void BoyerMooreCtxDeInit ( BmCtx bmctx)

Free the memory allocated to Booyer Moore context.

Parameters
bmCtxpointer to the Context for the pattern

Definition at line 120 of file util-spm-bm.c.

References m, SCEnter, SCFree, SCReturn, u8_tolower, and u8_toupper.

Referenced by BoyerMooreNocaseSearch(), BoyerMooreSearch(), DetectFilemagicRegister(), and DetectFilenameRegister().

Here is the caller graph for this function:

BmCtx* BoyerMooreCtxInit ( const uint8_t *  needle,
uint16_t  needle_len 
)

Setup a Booyer Moore context.

Parameters
strpointer to the pattern string
sizelength of the string
Return values
BmCtxpointer to the newly created Context for the pattern BoyerMoore contexts should be created at init

Definition at line 77 of file util-spm-bm.c.

References SC_ERR_FATAL, SCLogError, SCMalloc, and unlikely.

Referenced by BoyerMooreNocaseCtxInit(), and BoyerMooreSearch().

Here is the caller graph for this function:

void BoyerMooreCtxToNocase ( BmCtx bm_ctx,
uint8_t *  needle,
uint16_t  needle_len 
)

Given a BmCtx structure, recreate the pre/suffixes for nocase.

Return values
BmCtxpointer to the already created BmCtx (with BoyerMooreCtxInit())
Parameters
strpointer to the pattern string
sizelength of the string

Definition at line 57 of file util-spm-bm.c.

References BmCtx_::bmBc, and BmCtx_::bmGs.

Referenced by BoyerMooreNocaseCtxInit().

Here is the caller graph for this function:

uint8_t* BoyerMooreNocase ( const uint8_t *  x,
uint16_t  m,
const uint8_t *  y,
uint32_t  n,
BmCtx bm_ctx 
)

Boyer Moore search algorithm Is better as the pattern length increases and for big buffers to search in. The algorithm needs a context of two arrays already prepared by prep_bad_chars() and prep_good_suffix()

Parameters
ypointer to the buffer to search in
nlength limit of the buffer
xpointer to the pattern we ar searching for
mlength limit of the needle
bmBcpointer to an array of BoyerMooreSuffixes prepared by prep_good_suffix()
bmGspointer to an array of bachars prepared by prep_bad_chars()
Return values
ptrto start of the match; NULL if no match

Definition at line 350 of file util-spm-bm.c.

References ALPHABET_SIZE, BmCtx_::bmBc, BmCtx_::bmGs, m, u8_tolower, and unlikely.

Referenced by BoyerMooreNocaseSearch(), DetectFilemagicRegister(), and DetectFilenameRegister().

Here is the caller graph for this function:

BmCtx* BoyerMooreNocaseCtxInit ( uint8_t *  needle,
uint16_t  needle_len 
)

Setup a Booyer Moore context for nocase search.

Parameters
strpointer to the pattern string
sizelength of the string
Return values
BmCtxpointer to the newly created Context for the pattern BoyerMoore contexts should be created at init

Definition at line 106 of file util-spm-bm.c.

References BoyerMooreCtxInit(), and BoyerMooreCtxToNocase().

Referenced by BoyerMooreNocaseSearch(), DetectFilemagicRegister(), and DetectFilenameRegister().

Here is the call graph for this function:

Here is the caller graph for this function: