kernel/linux
0
Fork 0
mirror of https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ synced 2026-10-14 05:55:17 +00:00
Code Issues Releases Packages Activity
linux/lib/ts_bm.c

203 lines
5.1 KiB
Raw Permalink Normal View History

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 152 Based on 1 normalized pattern(s): this program is free software you can redistribute it and or modify it under the terms of the gnu general public license as published by the free software foundation either version 2 of the license or at your option any later version extracted by the scancode license scanner the SPDX license identifier GPL-2.0-or-later has been chosen to replace the boilerplate/reference in 3029 file(s). Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Reviewed-by: Allison Randal <allison@lohutok.net> Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190527070032.746973796@linutronix.de Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-05-27 08:55:01 +02:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: fix Boyer-Moore text search bug The current logic has a bug which cannot find matching pattern, if the pattern is matched from the first character of target string. for example: pattern=abc, string=abcdefg pattern=a, string=abcdefg Searching algorithm should return 0 for those things. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-06-30 12:42:23 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
[TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore The current logic does not calculate correctly the good shift array: Let x be the pattern that is being searched. Let y be the block of data. The good shift array aligns the segment: x[i+1 ... m-1] = y[i+j+1 ... j+m-1] with its rightmost occurrence in x that fulfils x[i] neq y[i+j]. In previous version, the good shift array for the pattern ANPANMAN is: [1, 8, 3, 8, 8, 8, 8, 8] and should be: [1, 8, 3, 6, 6, 6, 6, 6] Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-02-02 17:15:41 -08:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
[TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore The current logic does not calculate correctly the good shift array: Let x be the pattern that is being searched. Let y be the block of data. The good shift array aligns the segment: x[i+1 ... m-1] = y[i+j+1 ... j+m-1] with its rightmost occurrence in x that fulfils x[i] neq y[i+j]. In previous version, the good shift array for the pattern ANPANMAN is: [1, 8, 3, 8, 8, 8, 8, 8] and should be: [1, 8, 3, 6, 6, 6, 6, 6] Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-02-02 17:15:41 -08:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
[TEXTSEARCH]: Fix Boyer Moore initialization bug The pattern is set after trying to compute the prefix table, which tries to use it. Initialize it before calling compute_prefix_tbl, make compute_prefix_tbl consistently use only the data from struct ts_bm and remove the now unnecessary arguments. Signed-off-by: Michael Rash <mbr@cipherdyne.org> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-08-22 00:45:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[TEXTSEARCH]: Fix Boyer Moore initialization bug The pattern is set after trying to compute the prefix table, which tries to use it. Initialize it before calling compute_prefix_tbl, make compute_prefix_tbl consistently use only the data from struct ts_bm and remove the now unnecessary arguments. Signed-off-by: Michael Rash <mbr@cipherdyne.org> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-08-22 00:45:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
[TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore The current logic does not calculate correctly the good shift array: Let x be the pattern that is being searched. Let y be the block of data. The good shift array aligns the segment: x[i+1 ... m-1] = y[i+j+1 ... j+m-1] with its rightmost occurrence in x that fulfils x[i] neq y[i+j]. In previous version, the good shift array for the pattern ANPANMAN is: [1, 8, 3, 8, 8, 8, 8, 8] and should be: [1, 8, 3, 6, 6, 6, 6, 6] Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-02-02 17:15:41 -08:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00
textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2008-07-08 02:37:54 -07:00
[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2 Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-25 16:12:22 -07:00