suricata
util-spm-bs.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 Victor Julien <victor@inliniac.net>
22  * \author Pablo Rincon Crespo <pablo.rincon.crespo@gmail.com>
23  *
24  * bs is a bruteforce search. It will try to search the pattern
25  * from all characters until the available text len is less
26  * than the length of the pattern. It needs no context but it
27  * time cost is not good.
28  */
29 
30 #include "suricata-common.h"
31 #include "suricata.h"
32 
33 #include "util-debug.h"
34 #include "util-spm-bs.h"
35 
36 /**
37  * \brief Basic search improved. Limits are better handled, so
38  * it doesn't start searches that wont fit in the remaining buffer
39  *
40  * \param haystack pointer to the buffer to search in
41  * \param haystack_len length limit of the buffer
42  * \param needle pointer to the pattern we ar searching for
43  * \param needle_len length limit of the needle
44  *
45  * \retval ptr to start of the match; NULL if no match
46  */
47 uint8_t *BasicSearch(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len)
48 {
49  SCEnter();
50 
51  const uint8_t *h, *n;
52  const uint8_t *hmax = haystack + haystack_len;
53  const uint8_t *nmax = needle + needle_len;
54 
55  if (needle_len == 0 || needle_len > haystack_len) {
56  SCReturnPtr(NULL, "uint8_t");
57  }
58 
59  //PrintRawDataFp(stdout,needle,needle_len);
60 
61  //PrintRawDataFp(stdout,haystack,haystack_len);
62 
63  for (n = needle; nmax - n <= hmax - haystack; haystack++) {
64  if (*haystack != *n) {
65  continue;
66  }
67 
68  SCLogDebug("*haystack == *n, %c == %c", *haystack, *n);
69 
70  /* one byte needles */
71  if (needle_len == 1) {
72  SCReturnPtr((uint8_t *)haystack, "uint8_t");
73  }
74 
75  for (h = haystack+1, n++; nmax - n <= hmax - haystack; h++, n++) {
76  if (*h != *n) {
77  break;
78  }
79  SCLogDebug("*haystack == *n, %c == %c", *haystack, *n);
80  /* if we run out of needle we fully matched */
81  if (n == nmax - 1) {
82  SCReturnPtr((uint8_t *)haystack, "uint8_t");
83  }
84  }
85  n = needle;
86  }
87 
88  SCReturnPtr(NULL, "uint8_t");
89 }
90 
91 /**
92  * \brief Basic search case less
93  *
94  * \param haystack pointer to the buffer to search in
95  * \param haystack_len length limit of the buffer
96  * \param needle pointer to the pattern we ar searching for
97  * \param needle_len length limit of the needle
98  *
99  * \retval ptr to start of the match; NULL if no match
100  */
101 uint8_t *BasicSearchNocase(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len)
102 {
103  const uint8_t *h, *n;
104  const uint8_t *hmax = haystack + haystack_len;
105  const uint8_t *nmax = needle + needle_len;
106 
107  if (needle_len == 0 || needle_len > haystack_len)
108  return NULL;
109 
110  for (n = needle; nmax - n <= hmax - haystack; haystack++) {
111  if (u8_tolower(*haystack) != u8_tolower(*n)) {
112  continue;
113  }
114  /* one byte needles */
115  if (needle_len == 1) {
116  return (uint8_t *)haystack;
117  }
118 
119  for (h = haystack+1, n++; nmax - n <= hmax - h ; h++, n++) {
120  if (u8_tolower(*h) != u8_tolower(*n)) {
121  break;
122  }
123  /* if we run out of needle we fully matched */
124  if (n == nmax - 1) {
125  return (uint8_t *)haystack;
126  }
127  }
128  n = needle;
129  }
130 
131  return NULL;
132 }
133 
135  const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len)
136 {
137  uint8_t *r = BasicSearchNocase(haystack, haystack_len, needle, needle_len);
138  if (r == NULL) {
139  return haystack_len;
140  }
141  return (uint32_t)(r - haystack);
142 }
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:269
u8_tolower
#define u8_tolower(c)
Definition: suricata-common.h:436
util-spm-bs.h
util-debug.h
BasicSearchNocase
uint8_t * BasicSearchNocase(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len)
Basic search case less.
Definition: util-spm-bs.c:101
BasicSearchNocaseIndex
uint32_t BasicSearchNocaseIndex(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len)
Definition: util-spm-bs.c:134
SCEnter
#define SCEnter(...)
Definition: util-debug.h:271
BasicSearch
uint8_t * BasicSearch(const uint8_t *haystack, uint32_t haystack_len, const uint8_t *needle, uint16_t needle_len)
Basic search improved. Limits are better handled, so it doesn't start searches that wont fit in the r...
Definition: util-spm-bs.c:47
SCReturnPtr
#define SCReturnPtr(x, type)
Definition: util-debug.h:287
suricata-common.h
suricata.h