#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 "util-validate.h"

Include dependency graph for util-spm-bm.c:

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...

BmCtx *	BoyerMooreCtxInit (const uint8_t *needle, uint16_t needle_len)
	Setup a Boyer Moore context. More...

BmCtx *	BoyerMooreNocaseCtxInit (uint8_t *needle, uint16_t needle_len)
	Setup a Boyer Moore context for nocase search. More...

void	BoyerMooreCtxDeInit (BmCtx *bmctx)
	Free the memory allocated to Boyer Moore context. More...

uint8_t *	BoyerMoore (const uint8_t x, const uint16_t m, const uint8_t y, const uint32_t n, const 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, const uint16_t m, const uint8_t y, const uint32_t n, const 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 search in, based on characters not available in the pattern and combinations of characters that start a suffix 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

◆ SpmBmCtx

typedef struct SpmBmCtx_ SpmBmCtx

Function Documentation

◆ BoyerMoore()

uint8_t* BoyerMoore	(	const uint8_t *	x,
		const uint16_t	m,
		const uint8_t *	y,
		const uint32_t	n,
		const 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

y	pointer to the buffer to search in
n	length limit of the buffer
x	pointer to the pattern we ar searching for
m	length limit of the needle
bmBc	pointer to an array of BoyerMooreSuffixes prepared by prep_good_suffix()
bmGs	pointer to an array of bachars prepared by prep_bad_chars()

Return values

ptr	to start of the match; NULL if no match

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

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

Referenced by BoyerMooreSearch().

Here is the caller graph for this function:

◆ BoyerMooreCtxDeInit()

void BoyerMooreCtxDeInit ( BmCtx * bmctx )

Free the memory allocated to Boyer Moore context.

Parameters

bmCtx pointer to the Context for the pattern

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

References SCEnter, SCFree, and SCReturn.

Referenced by BoyerMooreNocaseSearch(), and BoyerMooreSearch().

Here is the caller graph for this function:

◆ BoyerMooreCtxInit()

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

Setup a Boyer Moore context.

Parameters

str	pointer to the pattern string
size	length of the string

Return values

BmCtx pointer to the newly created Context for the pattern \initonly BoyerMoore contexts should be created at init

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

References FatalError, SCMalloc, and unlikely.

Referenced by BoyerMooreNocaseCtxInit(), and BoyerMooreSearch().

Here is the caller graph for this function:

◆ BoyerMooreCtxToNocase()

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

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

Return values

BmCtx pointer to the already created BmCtx (with BoyerMooreCtxInit())

Parameters

str	pointer to the pattern string
size	length of the string

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

Referenced by BoyerMooreNocaseCtxInit().

Here is the caller graph for this function:

◆ BoyerMooreNocase()

uint8_t* BoyerMooreNocase	(	const uint8_t *	x,
		const uint16_t	m,
		const uint8_t *	y,
		const uint32_t	n,
		const 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

y	pointer to the buffer to search in
n	length limit of the buffer
x	pointer to the pattern we ar searching for
m	length limit of the needle
bmBc	pointer to an array of BoyerMooreSuffixes prepared by prep_good_suffix()
bmGs	pointer to an array of bachars prepared by prep_bad_chars()