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