提取Python stringlib中的"BMHBNFS"字符串查找算法
Python中的stringlib字符串查找算法是Boyer-Moore,Horspool, Sunday, Bloom Filter几种算法的合成体, 大概的原理如下:
def find(s, p):# find first occurrence of p in sn = len(s)m = len(p)skip = delta1(p)]i = 0while i <= n-m:if s == p: # (boyer-moore)# potential matchif s == p[:m-1]:return iif s not in p:i = i + m + 1 # (sunday)else:i = i + skip # (horspool)else:# skipif s not in p:i = i + m + 1 # (sunday)else:i = i + 1return -1 # not found
以下是具体实现:
/* stringlib: fastsearch implementation */#ifndef STRINGLIB_FASTSEARCH_H#define STRINGLIB_FASTSEARCH_H#include <stdint.h>#include <unistd.h>#include <stdio.h>#include <stdlib.h>#include <string.h>/* fast search/count implementation, based on a mix between boyer-moore and horspool, with a few more bells and whistles on the top.for some more background, see: http://effbot.org/zone/stringlib.htm *//* note: fastsearch may access s, which isn't a problem when usingPython's ordinary string types, but may cause problems if you'reusing this code in other contexts.also, the count mode returns -1if there cannot possible be a match in the target string, and 0 ifit has actually checked for matches, but didn't find any.callersbeware! */#define FAST_COUNT 0#define FAST_SEARCH 1#define FAST_RSEARCH 2#ifndef LONG_BIT#define LONG_BIT 32#endif#if LONG_BIT >= 128#define STRINGLIB_BLOOM_WIDTH 128#elif LONG_BIT >= 64#define STRINGLIB_BLOOM_WIDTH 64#elif LONG_BIT >= 32#define STRINGLIB_BLOOM_WIDTH 32#else#error "LONG_BIT is smaller than 32"#endif#define STRINGLIB_BLOOM_ADD(mask, ch) \((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))#define STRINGLIB_BLOOM(mask, ch) \((mask &(1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))ssize_t fastsearch(const char *s, ssize_t n,const char *p, ssize_t m,ssize_t maxcount, int mode){unsigned long mask;ssize_t skip, count = 0;ssize_t i, j, mlast, w;w = n - m;if (w < 0 || (mode == FAST_COUNT && maxcount == 0)) {return -1;}/* look for special cases */if (m <= 1) {if (m <= 0) {return -1;}/* use special case for 1-character strings */if (mode == FAST_COUNT) {for (i = 0; i < n; i++)if (s == p) {count++;if (count == maxcount) {return maxcount;}}return count;}else if (mode == FAST_SEARCH) {for (i = 0; i < n; i++)if (s == p) {return i;}}else { /* FAST_RSEARCH */for (i = n - 1; i > -1; i--)if (s == p) {return i;}}return -1;}mlast = m - 1;skip = mlast - 1;mask = 0;if (mode != FAST_RSEARCH) {/* create compressed boyer-moore delta 1 table *//* process pattern[:-1] */for (i = 0; i < mlast; i++) {STRINGLIB_BLOOM_ADD(mask, p);if (p == p) {skip = mlast - i - 1;}}/* process pattern[-1] outside the loop */STRINGLIB_BLOOM_ADD(mask, p);for (i = 0; i <= w; i++) {/* note: using mlast in the skip path slows things down on x86 */if (s == p) {/* candidate match */for (j = 0; j < mlast; j++)if (s != p) {break;}if (j == mlast) {/* got a match! */if (mode != FAST_COUNT) {return i;}count++;if (count == maxcount) {return maxcount;}i = i + mlast;continue;}/* miss: check if next character is part of pattern */if (!STRINGLIB_BLOOM(mask, s)) {i = i + m;}else {i = i + skip;}}else {/* skip: check if next character is part of pattern */if (!STRINGLIB_BLOOM(mask, s)) {i = i + m;}}}}else { /* FAST_RSEARCH *//* create compressed boyer-moore delta 1 table *//* process pattern outside the loop */STRINGLIB_BLOOM_ADD(mask, p);/* process pattern[:0:-1] */for (i = mlast; i > 0; i--) {STRINGLIB_BLOOM_ADD(mask, p);if (p == p) {skip = i - 1;}}for (i = w; i >= 0; i--) {if (s == p) {/* candidate match */for (j = mlast; j > 0; j--)if (s != p) {break;}if (j == 0)/* got a match! */{return i;}/* miss: check if previous character is part of pattern */if (!STRINGLIB_BLOOM(mask, s)) {i = i - m;}else {i = i - skip;}}else {/* skip: check if previous character is part of pattern */if (!STRINGLIB_BLOOM(mask, s)) {i = i - m;}}}}if (mode != FAST_COUNT) {return -1;}return count;}#endif
测试代码
#include <arch/cycle.h>int main(int argc, char **argv){char *str = "GET / HTTP 1.0\r\nHost: www.xxx.com\r\nCache: \r\nCache:\r\n Length:\r\n";ssize_t rc = 0;uint64_t start, end;start = get_cycle_count();rc = fastsearch(str, strlen(str), "Cache:", 6, 2, FAST_SEARCH);end = get_cycle_count();printf("fastsearch return %u cost %llu \n", rc, end - start);printf("result = %s\n", str + rc);rc = fastsearch(str, strlen(str), "Cache:", 6, -1, FAST_COUNT);printf("result = %u\n", rc);return 0;}
看stringlib测试数据, 还是蛮可以的. 我在tile平台上测试发现还没有snort中的BMH算法速度快.
不过这个只是单一测试, 没有考虑到cache的情况, 仅供参考.
原文参考:
The stringlibLibrary有详细的描叙.
页:
[1]