Linux内核中BM字符串查找算法的一个小BUG

本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，

严禁用于任何商业用途。

msn:[email protected]

来源：http://yfydz.cublog.cn

在内核的lib/ts_bm.c文件中,实现了Boyer-Moore字符串查找算法, 但有一个小BUG:
 
static unsigned int bm_find(struct ts_config *conf, struct ts_state *state)
{
 struct ts_bm *bm = ts_config_priv(conf);
 unsigned int i, text_len, consumed = state->offset;
 const u8 *text;
 int shift = bm->patlen, bs;
...
 
shift的值应该初始化为:
 int shift = bm->patlen-1, bs;
 
 
否则的话如果text最前面就匹配了pattern的话,是找不到的, 如:
char text[]="patternsdfsfgsfsf";
char pattern[]="pattern";
 
按shift = bm->patlen就不能找到.
 
另外在较老内核版本(如2.6.15)的bm_init函数中, 复制bm->pattern放在compute_prefix_tbl(bm)之后,这也是不对的,应该先拷贝后计算, 不过新点的版本中已经改过来了.