diff options
author | Ashlee Young <ashlee@onosfw.com> | 2015-09-09 22:21:41 -0700 |
---|---|---|
committer | Ashlee Young <ashlee@onosfw.com> | 2015-09-09 22:21:41 -0700 |
commit | 8879b125d26e8db1a5633de5a9c692eb2d1c4f83 (patch) | |
tree | c7259d85a991b83dfa85ab2e339360669fc1f58e /framework/src/suricata/src/util-binsearch.c | |
parent | 13d05bc8458758ee39cb829098241e89616717ee (diff) |
suricata checkin based on commit id a4bce14770beee46a537eda3c3f6e8e8565d5d0a
Change-Id: I9a214fa0ee95e58fc640e50bd604dac7f42db48f
Diffstat (limited to 'framework/src/suricata/src/util-binsearch.c')
-rw-r--r-- | framework/src/suricata/src/util-binsearch.c | 112 |
1 files changed, 112 insertions, 0 deletions
diff --git a/framework/src/suricata/src/util-binsearch.c b/framework/src/suricata/src/util-binsearch.c new file mode 100644 index 00000000..59627759 --- /dev/null +++ b/framework/src/suricata/src/util-binsearch.c @@ -0,0 +1,112 @@ +/* Copyright (C) 2007-2010 Open Information Security Foundation + * + * You can copy, redistribute or modify this Program under the terms of + * the GNU General Public License version 2 as published by the Free + * Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * version 2 along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + +/** + * \file + * + * \author Victor Julien <victor@inliniac.net> + * + * Binary search utility functions + * + * \todo replace this by a better algo + */ + +#include "suricata-common.h" +#include "suricata.h" + +void BinSearchInit (void) +{ + /* nothing no more */ +} + +/* Binary search. + * + * Returns: + * - ptr to start of the match + * - null if no match + */ +/* simple bin search modelled loosely after strstr */ +uint8_t * +BinSearch(const uint8_t *haystack, size_t haystack_len, + const uint8_t *needle, size_t needle_len) +{ + const uint8_t *h, *n; + const uint8_t *hmax = haystack + haystack_len; + const uint8_t *nmax = needle + (needle_len - 1); + + if (needle_len == 0) + return NULL; + + for (n = needle; haystack != hmax; haystack++) { + if (*haystack != *n) { + continue; + } + /* one byte needles */ + if (needle_len == 1) + return (uint8_t *)haystack; + + for (h = haystack+1, n++; h != hmax; h++, n++) { + //printf("h %c n %c\n", isprint(*h) ? *h : 'X', *n); + if (*h != *n) { + break; + } + /* if we run out of needle we fully matched */ + if (n == nmax) { + return (uint8_t *)haystack; + } + } + n = needle; + } + return NULL; +} + +/* Caseless binary search. More expensive that the one that + * respects case. + * + * Returns: + * - ptr to start of the match + * - null if no match + */ +uint8_t * +BinSearchNocase(const uint8_t *haystack, size_t haystack_len, + const uint8_t *needle, size_t needle_len) +{ + const uint8_t *h, *n; + const uint8_t *hmax = haystack + haystack_len; + const uint8_t *nmax = needle + (needle_len - 1); + + if (needle_len == 0) + return NULL; + + for (n = needle; haystack != hmax; haystack++) { + if (*haystack != *n && *haystack != u8_tolower(*n)) { + continue; + } + for (h = haystack+1, n++; h != hmax; h++, n++) { + if (*h != *n && *h != u8_tolower(*n)) { + break; + } + /* if we run out of needle we fully matched */ + if (n == nmax) { + return (uint8_t *)haystack; + } + } + n = needle; + } + return NULL; +} + |