suricata
util-spm-bs2bm.c
Go to the documentation of this file.
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  * Bs2Bm use a simple context array to determine the characters
24  * that are not present on the pattern. This way on partial matches
25  * broken by a char not present, we can skip to the next character
26  * making less checks
27  */
28 
29 #include "suricata-common.h"
30 #include "suricata.h"
31 
32 #include "util-spm-bs2bm.h"
33 
34 /**
35  * \brief Array setup function for Bs2Bm of bad characters index (not found at the needle)
36  *
37  * \param needle pointer to the pattern we ar searching for
38  * \param needle_len length limit of the needle
39  * \param badchars pointer to an empty array of bachars. The array prepared contains
40  * characters that can't be inside the needle_len. So the skips can be
41  * faster
42  */
43 void Bs2BmBadchars(const uint8_t *needle, uint16_t needle_len, uint8_t *badchars)
44 {
45  uint32_t i;
46  for (i = 0; i < ALPHABET_SIZE; i++)
47  badchars[i] = 1;
48 
49  /* set to 0 the values where index as ascii is present
50  * because they are not badchars
51  */
52  for (i = 0; i < needle_len; i++)
53  badchars[needle[i]] = 0;
54 }
55 
56 /**
57  * \brief Array setup function for Bs2BmNocase of bad characters index (not found at the needle)
58  *
59  * \param needle pointer to the pattern we ar searching for
60  * \param needle_len length limit of the needle
61  * \param badchars pointer to an empty array of bachars. The array prepared contains
62  * characters that can't be inside the needle_len. So the skips can be
63  * faster
64  */
65 void Bs2BmBadcharsNocase(const uint8_t *needle, uint16_t needle_len, uint8_t *badchars)
66 {
67  uint32_t i;
68  for (i = 0; i < ALPHABET_SIZE; i++)
69  badchars[i] = 1;
70 
71  /* set to 0 the values where index as ascii is present
72  * because they are not badchars
73  */
74  for (i = 0; i < needle_len; i++) {
75  badchars[u8_tolower(needle[i])] = 0;
76  }
77 }
78 
79 /**
80  * \brief Basic search with a bad characters array. The array badchars contains
81  * flags at character's ascii index that can't be inside the needle. So the skips can be
82  * faster
83  *
84  * \param haystack pointer to the buffer to search in
85  * \param haystack_len length limit of the buffer
86  * \param needle pointer to the pattern we ar searching for
87  * \param needle_len length limit of the needle
88  * \param badchars pointer to an array of bachars prepared by Bs2BmBadchars()
89  *
90  * \retval ptr to start of the match; NULL if no match
91  */
92 uint8_t *Bs2Bm(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle,
93  uint16_t needle_len, const uint8_t badchars[])
94 {
95  const uint8_t *h, *n;
96  const uint8_t *hmax = haystack + haystack_len;
97  const uint8_t *nmax = needle + needle_len;
98 
99  if (needle_len == 0 || needle_len > haystack_len)
100  return NULL;
101 
102  for (n = needle; nmax - n <= hmax - haystack; haystack++) {
103  if (*haystack != *n) {
104  continue;
105  }
106  /* one byte needles */
107  if (needle_len == 1)
108  return (uint8_t *)haystack;
109 
110  for (h = haystack+1, n++; nmax - n <= hmax - haystack; h++, n++) {
111  if (*h != *n) {
112  if (badchars[*h] == 1) {
113  /* skip it! */
114  haystack = h;
115  }
116  break;
117  }
118  /* if we run out of needle we fully matched */
119  if (n == nmax - 1 ) {
120  return (uint8_t *)haystack;
121  }
122  }
123  n = needle;
124  }
125 
126  return NULL;
127 }
128 
129 /**
130  * \brief Basic search case less with a bad characters array. The array badchars contains
131  * flags at character's ascii index that can't be inside the needle. So the skips can be
132  * faster
133  *
134  * \param haystack pointer to the buffer to search in
135  * \param haystack_len length limit of the buffer
136  * \param needle pointer to the pattern we ar searching for
137  * \param needle_len length limit of the needle
138  * \param badchars pointer to an array of bachars prepared by Bs2BmBadchars()
139  *
140  * \retval ptr to start of the match; NULL if no match
141  */
142 uint8_t *Bs2BmNocase(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle,
143  uint16_t needle_len, const uint8_t badchars[])
144 {
145  const uint8_t *h, *n;
146  const uint8_t *hmax = haystack + haystack_len;
147  const uint8_t *nmax = needle + needle_len;
148 
149  if (needle_len == 0 || needle_len > haystack_len)
150  return NULL;
151 
152  for (n = needle; nmax - n <= hmax - haystack; haystack++) {
153  if (u8_tolower(*haystack) != u8_tolower(*n)) {
154  continue;
155  }
156  /* one byte needles */
157  if (needle_len == 1)
158  return (uint8_t *)haystack;
159 
160  for (h = haystack+1, n++; nmax - n <= hmax - haystack; h++, n++) {
161  if (u8_tolower(*h) != u8_tolower(*n)) {
162  if (badchars[u8_tolower(*h)] == 1) {
163  /* skip it! */
164  haystack = h;
165  }
166  break;
167  }
168  /* if we run out of needle we fully matched */
169  if (n == nmax - 1) {
170  return (uint8_t *)haystack;
171  }
172  }
173  n = needle;
174  }
175 
176  return NULL;
177 }
Bs2BmBadchars
void Bs2BmBadchars(const uint8_t *needle, uint16_t needle_len, uint8_t *badchars)
Array setup function for Bs2Bm of bad characters index (not found at the needle)
Definition: util-spm-bs2bm.c:43
u8_tolower
#define u8_tolower(c)
Definition: suricata-common.h:431
ALPHABET_SIZE
#define ALPHABET_SIZE
Definition: util-spm-bm.h:30
Bs2BmBadcharsNocase
void Bs2BmBadcharsNocase(const uint8_t *needle, uint16_t needle_len, uint8_t *badchars)
Array setup function for Bs2BmNocase of bad characters index (not found at the needle)
Definition: util-spm-bs2bm.c:65
Bs2Bm
uint8_t * Bs2Bm(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len, const uint8_t badchars[])
Basic search with a bad characters array. The array badchars contains flags at character's ascii inde...
Definition: util-spm-bs2bm.c:92
suricata-common.h
Bs2BmNocase
uint8_t * Bs2BmNocase(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len, const uint8_t badchars[])
Basic search case less with a bad characters array. The array badchars contains flags at character's ...
Definition: util-spm-bs2bm.c:142
util-spm-bs2bm.h
suricata.h