Thomas Gleixner | 2874c5f | 2019-05-27 08:55:01 +0200 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 2 | /* |
| 3 | * lib/ts_bm.c Boyer-Moore text search implementation |
| 4 | * |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 5 | * Authors: Pablo Neira Ayuso <pablo@eurodev.net> |
| 6 | * |
| 7 | * ========================================================================== |
| 8 | * |
| 9 | * Implements Boyer-Moore string matching algorithm: |
| 10 | * |
| 11 | * [1] A Fast String Searching Algorithm, R.S. Boyer and Moore. |
| 12 | * Communications of the Association for Computing Machinery, |
| 13 | * 20(10), 1977, pp. 762-772. |
Alexander A. Klimov | d89775f | 2020-08-11 18:34:50 -0700 | [diff] [blame] | 14 | * https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 15 | * |
| 16 | * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 |
| 17 | * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf |
| 18 | * |
| 19 | * Note: Since Boyer-Moore (BM) performs searches for matchings from right |
| 20 | * to left, it's still possible that a matching could be spread over |
| 21 | * multiple blocks, in that case this algorithm won't find any coincidence. |
| 22 | * |
| 23 | * If you're willing to ensure that such thing won't ever happen, use the |
| 24 | * Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose |
| 25 | * the proper string search algorithm depending on your setting. |
| 26 | * |
| 27 | * Say you're using the textsearch infrastructure for filtering, NIDS or |
| 28 | * any similar security focused purpose, then go KMP. Otherwise, if you |
| 29 | * really care about performance, say you're classifying packets to apply |
| 30 | * Quality of Service (QoS) policies, and you don't mind about possible |
| 31 | * matchings spread over multiple fragments, then go BM. |
| 32 | */ |
| 33 | |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 34 | #include <linux/kernel.h> |
| 35 | #include <linux/module.h> |
| 36 | #include <linux/types.h> |
| 37 | #include <linux/string.h> |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 38 | #include <linux/ctype.h> |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 39 | #include <linux/textsearch.h> |
| 40 | |
| 41 | /* Alphabet size, use ASCII */ |
| 42 | #define ASIZE 256 |
| 43 | |
| 44 | #if 0 |
| 45 | #define DEBUGP printk |
| 46 | #else |
| 47 | #define DEBUGP(args, format...) |
| 48 | #endif |
| 49 | |
| 50 | struct ts_bm |
| 51 | { |
| 52 | u8 * pattern; |
| 53 | unsigned int patlen; |
| 54 | unsigned int bad_shift[ASIZE]; |
Gustavo A. R. Silva | c6e2ac3 | 2020-04-06 20:10:00 -0700 | [diff] [blame] | 55 | unsigned int good_shift[]; |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 56 | }; |
| 57 | |
Jeremy Sowden | 86e9c9a | 2023-06-20 19:11:00 +0100 | [diff] [blame] | 58 | static unsigned int matchpat(const u8 *pattern, unsigned int patlen, |
| 59 | const u8 *text, bool icase) |
| 60 | { |
| 61 | unsigned int i; |
| 62 | |
| 63 | for (i = 0; i < patlen; i++) { |
| 64 | u8 t = *(text-i); |
| 65 | |
| 66 | if (icase) |
| 67 | t = toupper(t); |
| 68 | |
| 69 | if (t != *(pattern-i)) |
| 70 | break; |
| 71 | } |
| 72 | |
| 73 | return i; |
| 74 | } |
| 75 | |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 76 | static unsigned int bm_find(struct ts_config *conf, struct ts_state *state) |
| 77 | { |
| 78 | struct ts_bm *bm = ts_config_priv(conf); |
| 79 | unsigned int i, text_len, consumed = state->offset; |
| 80 | const u8 *text; |
Jeremy Sowden | 6f67fbf | 2023-06-19 20:06:57 +0100 | [diff] [blame] | 81 | int bs; |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 82 | const u8 icase = conf->flags & TS_IGNORECASE; |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 83 | |
| 84 | for (;;) { |
Jeremy Sowden | 6f67fbf | 2023-06-19 20:06:57 +0100 | [diff] [blame] | 85 | int shift = bm->patlen - 1; |
| 86 | |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 87 | text_len = conf->get_next_block(consumed, &text, conf, state); |
| 88 | |
| 89 | if (unlikely(text_len == 0)) |
| 90 | break; |
| 91 | |
| 92 | while (shift < text_len) { |
Jeremy Sowden | 86e9c9a | 2023-06-20 19:11:00 +0100 | [diff] [blame] | 93 | DEBUGP("Searching in position %d (%c)\n", |
| 94 | shift, text[shift]); |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 95 | |
Jeremy Sowden | 86e9c9a | 2023-06-20 19:11:00 +0100 | [diff] [blame] | 96 | i = matchpat(&bm->pattern[bm->patlen-1], bm->patlen, |
| 97 | &text[shift], icase); |
| 98 | if (i == bm->patlen) { |
| 99 | /* London calling... */ |
| 100 | DEBUGP("found!\n"); |
| 101 | return consumed + (shift-(bm->patlen-1)); |
| 102 | } |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 103 | |
Jeremy Sowden | 86e9c9a | 2023-06-20 19:11:00 +0100 | [diff] [blame] | 104 | bs = bm->bad_shift[text[shift-i]]; |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 105 | |
| 106 | /* Now jumping to... */ |
| 107 | shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]); |
| 108 | } |
| 109 | consumed += text_len; |
| 110 | } |
| 111 | |
| 112 | return UINT_MAX; |
| 113 | } |
| 114 | |
Pablo Neira Ayuso | 3f33031 | 2006-02-02 17:15:41 -0800 | [diff] [blame] | 115 | static int subpattern(u8 *pattern, int i, int j, int g) |
| 116 | { |
| 117 | int x = i+g-1, y = j+g-1, ret = 0; |
| 118 | |
| 119 | while(pattern[x--] == pattern[y--]) { |
| 120 | if (y < 0) { |
| 121 | ret = 1; |
| 122 | break; |
| 123 | } |
| 124 | if (--g == 0) { |
| 125 | ret = pattern[i-1] != pattern[j-1]; |
| 126 | break; |
| 127 | } |
| 128 | } |
| 129 | |
| 130 | return ret; |
| 131 | } |
| 132 | |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 133 | static void compute_prefix_tbl(struct ts_bm *bm, int flags) |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 134 | { |
Pablo Neira Ayuso | 3f33031 | 2006-02-02 17:15:41 -0800 | [diff] [blame] | 135 | int i, j, g; |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 136 | |
| 137 | for (i = 0; i < ASIZE; i++) |
Michael Rash | 3ffaa8c7 | 2006-08-22 00:45:22 -0700 | [diff] [blame] | 138 | bm->bad_shift[i] = bm->patlen; |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 139 | for (i = 0; i < bm->patlen - 1; i++) { |
Michael Rash | 3ffaa8c7 | 2006-08-22 00:45:22 -0700 | [diff] [blame] | 140 | bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i; |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 141 | if (flags & TS_IGNORECASE) |
| 142 | bm->bad_shift[tolower(bm->pattern[i])] |
| 143 | = bm->patlen - 1 - i; |
| 144 | } |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 145 | |
| 146 | /* Compute the good shift array, used to match reocurrences |
| 147 | * of a subpattern */ |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 148 | bm->good_shift[0] = 1; |
| 149 | for (i = 1; i < bm->patlen; i++) |
| 150 | bm->good_shift[i] = bm->patlen; |
Pablo Neira Ayuso | 3f33031 | 2006-02-02 17:15:41 -0800 | [diff] [blame] | 151 | for (i = bm->patlen-1, g = 1; i > 0; g++, i--) { |
| 152 | for (j = i-1; j >= 1-g ; j--) |
| 153 | if (subpattern(bm->pattern, i, j, g)) { |
| 154 | bm->good_shift[g] = bm->patlen-j-g; |
| 155 | break; |
| 156 | } |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 157 | } |
| 158 | } |
| 159 | |
| 160 | static struct ts_config *bm_init(const void *pattern, unsigned int len, |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 161 | gfp_t gfp_mask, int flags) |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 162 | { |
| 163 | struct ts_config *conf; |
| 164 | struct ts_bm *bm; |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 165 | int i; |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 166 | unsigned int prefix_tbl_len = len * sizeof(unsigned int); |
| 167 | size_t priv_size = sizeof(*bm) + len + prefix_tbl_len; |
| 168 | |
| 169 | conf = alloc_ts_config(priv_size, gfp_mask); |
| 170 | if (IS_ERR(conf)) |
| 171 | return conf; |
| 172 | |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 173 | conf->flags = flags; |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 174 | bm = ts_config_priv(conf); |
| 175 | bm->patlen = len; |
| 176 | bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len; |
Joonwoo Park | 3b76d08 | 2008-07-08 02:37:54 -0700 | [diff] [blame] | 177 | if (flags & TS_IGNORECASE) |
| 178 | for (i = 0; i < len; i++) |
| 179 | bm->pattern[i] = toupper(((u8 *)pattern)[i]); |
| 180 | else |
| 181 | memcpy(bm->pattern, pattern, len); |
| 182 | compute_prefix_tbl(bm, flags); |
Pablo Neira Ayuso | 8082e4e | 2005-08-25 16:12:22 -0700 | [diff] [blame] | 183 | |
| 184 | return conf; |
| 185 | } |
| 186 | |
| 187 | static void *bm_get_pattern(struct ts_config *conf) |
| 188 | { |
| 189 | struct ts_bm *bm = ts_config_priv(conf); |
| 190 | return bm->pattern; |
| 191 | } |
| 192 | |
| 193 | static unsigned int bm_get_pattern_len(struct ts_config *conf) |
| 194 | { |
| 195 | struct ts_bm *bm = ts_config_priv(conf); |
| 196 | return bm->patlen; |
| 197 | } |
| 198 | |
| 199 | static struct ts_ops bm_ops = { |
| 200 | .name = "bm", |
| 201 | .find = bm_find, |
| 202 | .init = bm_init, |
| 203 | .get_pattern = bm_get_pattern, |
| 204 | .get_pattern_len = bm_get_pattern_len, |
| 205 | .owner = THIS_MODULE, |
| 206 | .list = LIST_HEAD_INIT(bm_ops.list) |
| 207 | }; |
| 208 | |
| 209 | static int __init init_bm(void) |
| 210 | { |
| 211 | return textsearch_register(&bm_ops); |
| 212 | } |
| 213 | |
| 214 | static void __exit exit_bm(void) |
| 215 | { |
| 216 | textsearch_unregister(&bm_ops); |
| 217 | } |
| 218 | |
| 219 | MODULE_LICENSE("GPL"); |
| 220 | |
| 221 | module_init(init_bm); |
| 222 | module_exit(exit_bm); |