1 /* Copyright (C) 2007-2010 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Pablo Rincon Crespo <pablo.rincon.crespo@gmail.com>
22  */
23 
24 #ifndef __UTIL_SPM_H__
25 #define __UTIL_SPM_H__
26 
27 #include "util-spm-bs.h"
28 #include "util-spm-bs2bm.h"
29 #include "util-spm-bm.h"
30 
31 enum {
32     SPM_BM, /* Boyer-Moore */
33     SPM_HS, /* Hyperscan */
34     /* Other SPM matchers will go here. */
35     SPM_TABLE_SIZE
36 };
37 
38 uint16_t SinglePatternMatchDefaultMatcher(void);
39 
40 /** Structure holding an immutable "built" SPM matcher (such as the Boyer-Moore
41  * tables, Hyperscan database etc) that is passed to the Scan call. */
42 typedef struct SpmCtx_ {
43     uint16_t matcher;
44     void *ctx;
45 } SpmCtx;
46 
47 /** Structure holding a global prototype for per-thread scratch space, passed
48  * to each InitCtx call. */
49 typedef struct SpmGlobalThreadCtx_ {
50     uint16_t matcher;
51     void *ctx;
52 } SpmGlobalThreadCtx;
53 
54 /** Structure holding some mutable per-thread space for use by a matcher at
55  * scan time. Constructed from SpmGlobalThreadCtx by the MakeThreadCtx call. */
56 typedef struct SpmThreadCtx_ {
57     uint16_t matcher;
58     void *ctx;
59 } SpmThreadCtx;
60 
61 typedef struct SpmTableElmt_ {
62     const char *name;
63     SpmGlobalThreadCtx *(*InitGlobalThreadCtx)(void);
64     void (*DestroyGlobalThreadCtx)(SpmGlobalThreadCtx *g_thread_ctx);
65     SpmThreadCtx *(*MakeThreadCtx)(const SpmGlobalThreadCtx *g_thread_ctx);
66     void (*DestroyThreadCtx)(SpmThreadCtx *thread_ctx);
67     SpmCtx *(*InitCtx)(const uint8_t *needle, uint16_t needle_len, int nocase,
68                        SpmGlobalThreadCtx *g_thread_ctx);
69     void (*DestroyCtx)(SpmCtx *);
70     uint8_t *(*Scan)(const SpmCtx *ctx, SpmThreadCtx *thread_ctx,
71                      const uint8_t *haystack, uint32_t haystack_len);
72 } SpmTableElmt;
73 
74 extern SpmTableElmt spm_table[SPM_TABLE_SIZE];
75 
76 void SpmTableSetup(void);
77 
78 SpmGlobalThreadCtx *SpmInitGlobalThreadCtx(uint16_t matcher);
79 
80 void SpmDestroyGlobalThreadCtx(SpmGlobalThreadCtx *g_thread_ctx);
81 
82 SpmThreadCtx *SpmMakeThreadCtx(const SpmGlobalThreadCtx *g_thread_ctx);
83 
84 void SpmDestroyThreadCtx(SpmThreadCtx *thread_ctx);
85 
86 SpmCtx *SpmInitCtx(const uint8_t *needle, uint16_t needle_len, int nocase,
87                    SpmGlobalThreadCtx *g_thread_ctx);
88 
89 void SpmDestroyCtx(SpmCtx *ctx);
90 
91 uint8_t *SpmScan(const SpmCtx *ctx, SpmThreadCtx *thread_ctx,
92                  const uint8_t *haystack, uint32_t haystack_len);
93 
94 /** Default algorithm to use: Boyer Moore */
95 uint8_t *Bs2bmSearch(const uint8_t *text, uint32_t textlen, const uint8_t *needle, uint16_t needlelen);
96 uint8_t *Bs2bmNocaseSearch(const uint8_t *text, uint32_t textlen, const uint8_t *needle, uint16_t needlelen);
97 uint8_t *BoyerMooreSearch(const uint8_t *text, uint32_t textlen, const uint8_t *needle, uint16_t needlelen);
98 uint8_t *BoyerMooreNocaseSearch(const uint8_t *text, uint32_t textlen, uint8_t *needle, uint16_t needlelen);
99 
100 /* Macros for automatic algorithm selection (use them only when you can't store the context) */
101 #define SpmSearch(text, textlen, needle, needlelen) ({\
102     uint8_t *mfound; \
103     if (needlelen < 4 && textlen < 512) \
104           mfound = BasicSearch(text, textlen, needle, needlelen); \
105     else if (needlelen < 4) \
106           mfound = BasicSearch(text, textlen, needle, needlelen); \
107     else \
108           mfound = BoyerMooreSearch(text, textlen, needle, needlelen); \
109     mfound; \
110     })
111 
112 #define SpmNocaseSearch(text, textlen, needle, needlelen) ({\
113     uint8_t *mfound; \
114     if (needlelen < 4 && textlen < 512) \
115           mfound = BasicSearchNocase(text, textlen, needle, needlelen); \
116     else if (needlelen < 4) \
117           mfound = BasicSearchNocase(text, textlen, needle, needlelen); \
118     else \
119           mfound = BoyerMooreNocaseSearch(text, textlen, needle, needlelen); \
120     mfound; \
121     })
122 
123 void UtilSpmSearchRegistertests(void);
124 #endif /* __UTIL_SPM_H__ */
125