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 charactes
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 neddle 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 neddle 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 /**
81  * \brief Basic search with a bad characters array. The array badchars contains
82  * flags at character's ascii index that can't be inside the needle. So the skips can be
83  * faster
84  *
85  * \param haystack pointer to the buffer to search in
86  * \param haystack_len length limit of the buffer
87  * \param neddle pointer to the pattern we ar searching for
88  * \param needle_len length limit of the needle
89  * \param badchars pointer to an array of bachars prepared by Bs2BmBadchars()
90  *
91  * \retval ptr to start of the match; NULL if no match
92  */
93 uint8_t *Bs2Bm(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle,
94  uint16_t needle_len, const uint8_t badchars[])
95 {
96  const uint8_t *h, *n;
97  const uint8_t *hmax = haystack + haystack_len;
98  const uint8_t *nmax = needle + needle_len;
99 
100  if (needle_len == 0 || needle_len > haystack_len)
101  return NULL;
102 
103  for (n = needle; nmax - n <= hmax - haystack; haystack++) {
104  if (*haystack != *n) {
105  continue;
106  }
107  /* one byte needles */
108  if (needle_len == 1)
109  return (uint8_t *)haystack;
110 
111  for (h = haystack+1, n++; nmax - n <= hmax - haystack; h++, n++) {
112  if (*h != *n) {
113  if (badchars[*h] == 1) {
114  /* skip it! */
115  haystack = h;
116  }
117  break;
118  }
119  /* if we run out of needle we fully matched */
120  if (n == nmax - 1 ) {
121  return (uint8_t *)haystack;
122  }
123  }
124  n = needle;
125  }
126 
127  return NULL;
128 }
129 
130 /**
131  * \brief Basic search case less with a bad characters array. The array badchars contains
132  * flags at character's ascii index that can't be inside the needle. So the skips can be
133  * faster
134  *
135  * \param haystack pointer to the buffer to search in
136  * \param haystack_len length limit of the buffer
137  * \param neddle pointer to the pattern we ar searching for
138  * \param needle_len length limit of the needle
139  * \param badchars pointer to an array of bachars prepared by Bs2BmBadchars()
140  *
141  * \retval ptr to start of the match; NULL if no match
142  */
143 uint8_t *Bs2BmNocase(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle,
144  uint16_t needle_len, const uint8_t badchars[])
145 {
146  const uint8_t *h, *n;
147  const uint8_t *hmax = haystack + haystack_len;
148  const uint8_t *nmax = needle + needle_len;
149 
150  if (needle_len == 0 || needle_len > haystack_len)
151  return NULL;
152 
153  for (n = needle; nmax - n <= hmax - haystack; haystack++) {
154  if (u8_tolower(*haystack) != u8_tolower(*n)) {
155  continue;
156  }
157  /* one byte needles */
158  if (needle_len == 1)
159  return (uint8_t *)haystack;
160 
161  for (h = haystack+1, n++; nmax - n <= hmax - haystack; h++, n++) {
162  if (u8_tolower(*h) != u8_tolower(*n)) {
163  if (badchars[u8_tolower(*h)] == 1) {
164  /* skip it! */
165  haystack = h;
166  }
167  break;
168  }
169  /* if we run out of needle we fully matched */
170  if (n == nmax - 1) {
171  return (uint8_t *)haystack;
172  }
173  }
174  n = needle;
175  }
176 
177  return NULL;
178 }
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:425
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:93
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:143
util-spm-bs2bm.h
suricata.h