Linux kernel BM string search algorithm, a small BUG

2011-01-10  来源:本站原创  分类:Internet  人气:60 

This document Copyleft owned yfydz all use under the GPL, can be freely copied, reproduced, reprinted, please maintain the integrity of the document,
Be used for any commercial purposes is strictly prohibited.
msn: [email protected]
Source: http://yfydz.cublog.cn

In the lib/ts_bm.c file in the kernel , Implements Boyer-Moore string searching algorithm ,  But there is a small 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 Values should be initialized :
 int shift = bm->patlen-1, bs;

 Otherwise if the text matches the first pattern So, is not found ,  If :
char text[]="patternsdfsfgsfsf";
char pattern[]="pattern";

 Press shift = bm->patlen Cannot find .

 Also in older kernel version ( If 2.6.15) Bm_init function ,  Copy bm->pattern Placed in compute_prefix_tbl(bm) , This is not right , Should be evaluated before copy, but in a new point release has changed over the .
相关文章
  • Linux kernel BM string search algorithm, a small BUG 2011-01-10

    This document Copyleft owned yfydz all use under the GPL, can be freely copied, reproduced, reprinted, please maintain the integrity of the document, Be used for any commercial purposes is strictly prohibited. msn: [email protected] Source: http:

  • Linux kernel in the BM string search algorithm, a small BUG 2011-01-10

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, Used for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.cublog.cn In th

  • String search algorithm summary 2010-04-26

    Hash algorithm for online search of knowledge, they inadvertently found some string search algorithm. Before the study because some search algorithm, that should be classified as a class. So write an article on to record the learning process. Questio

  • String search algorithm 2011-01-10

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.cublog.cn References

  • View Linux kernel. CPU. Memory and other components version of the commands and methods 2010-10-14

    This article comes from, " Wong Po's blog "blog, be sure to keep this source http://huangbao.blog.51cto.com/725279/152679 View Kernel version: uname-a more / etc / * release more / etc / redhat-release more / proc / version View CPU Information:

  • See the Linux kernel. CPU. Memory and the version of the component commands and methods 2010-10-14

    This article comes from " yellow treasure of the blog "blog, be sure to keep this source http://huangbao.blog.51cto.com/725279/152679 Check kernel version: uname-a more / etc / * release more / etc / redhat-release more / proc / version View CPU

  • Linux kernel in the red-black tree 2010-07-03

    Red-black tree is a balanced binary tree, it has good properties, tree nodes are ordered, but also because it itself is balanced, so there will not look very bad situation, based on binary operation time complexity is O (log (N)). Linux kernel is use

  • How to install custom Linux kernel [change] 2010-07-31

    1. Ready 2. Access to source code 3. Unpacking the source code 4. Configuring the kernel 5. To create the kernel 1. Make-kpkg 2. - Append-to-version 3. - Revision 4. Kernel package names 5. Fakeroot 6. Generate the kernel image 6. Installing the kern

  • Linux kernel file Cache management mechanism introduced 2010-08-18

    1 Introduction Since its inception, Linux was continuously improved and popularity, now it has become one of the mainstream of general operating system, used well or very broad, Ta with Windows, UNIX Together account for nearly all the operating syst

  • IPSEC Linux kernel implementation (1) --- reserved 2010-11-15

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, for any commercial purposes is strictly prohibited. MSN: [email protected] Source: http://yfydz.cublog.cn 1. Introdu

  • IPSEC Linux kernel implementation (4) --- reserved 2010-11-15

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, for any commercial purposes is strictly prohibited. MSN: [email protected] Source: http://yfydz.cublog.cn 6. XFRM of

  • Linux kernel traffic control (1) 2011-01-10

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, Used for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.cublog.cn 1. Pr

  • Linux kernel in some of the basic operations 2011-01-10

    This document Copyleft owned yfydz all use under the GPL, can be freely copied, reproduced, reprinted, please maintain the integrity of the document, for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.

  • Linux Kernel IPSEC implementation (1) 2011-01-10

    This document Copyleft owned yfydz all use under the GPL, can be freely copied, reproduced, reprinted, please maintain the integrity of the document, for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.

  • Linux Kernel IPSEC implementation (4) 2011-01-10

    This document Copyleft owned yfydz all use under the GPL, can be freely copied, reproduced, reprinted, please maintain the integrity of the document, for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.

  • Linux kernel configuration file. Config and Makefile 2011-04-09

    ========================================== Preliminary Makefile ========================================== Linux kernel configuration file there are two, one is implied. Config files, embedded in the main Makefile; the other include / linux / autocon

  • linux kernel tcp congestion handling (1) 2010-03-12

    This time we analyze tcp congestion control, we need to know the protocol stack is very conservative, meaning that as long as there is a missing segment have been determined, it will think that the congestion occurred. And now there is another, that

  • linux kernel learning materials 2010-04-02

    Recent self-Linux kernel side of things, the past two days under the shallow of the kernel boot process, in this record. Here, the Linux boot loader is not involved in virtual environment, that system does not run on top of the hypervisor. Linux thro

  • JDK learning search algorithm 2010-04-13

    Today we learn of two commonly used search algorithms: sequential search and binary search, no BS, the first on the code, later analysis: 1. Here are two kinds of search algorithm, in which the second taken from the JDK source code: Sequential search

  • String matching algorithm [z] 2010-06-17

    From: http://www.yuanma.org/data/2008/0806/article_3128.htm Abstract: With the Internet increasingly large, more information is, how vast amounts of information quickly find their desired information is the hot topic of Web search, in this one, the s