224 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*3 * lib/ts_bm.c Boyer-Moore text search implementation4 *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.14 * https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf15 *16 * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 200417 * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf18 *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 the24 * 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 apply30 * Quality of Service (QoS) policies, and you don't mind about possible31 * matchings spread over multiple fragments, then go BM.32 */33 34#include <linux/kernel.h>35#include <linux/module.h>36#include <linux/types.h>37#include <linux/string.h>38#include <linux/ctype.h>39#include <linux/textsearch.h>40 41/* Alphabet size, use ASCII */42#define ASIZE 25643 44#if 045#define DEBUGP printk46#else47#define DEBUGP(args, format...)48#endif49 50struct ts_bm51{52 u8 * pattern;53 unsigned int patlen;54 unsigned int bad_shift[ASIZE];55 unsigned int good_shift[];56};57 58static 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 76static 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;81 int bs;82 const u8 icase = conf->flags & TS_IGNORECASE;83 84 for (;;) {85 int shift = bm->patlen - 1;86 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) {93 DEBUGP("Searching in position %d (%c)\n",94 shift, text[shift]);95 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 }103 104 bs = bm->bad_shift[text[shift-i]];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 115static 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 133static void compute_prefix_tbl(struct ts_bm *bm, int flags)134{135 int i, j, g;136 137 for (i = 0; i < ASIZE; i++)138 bm->bad_shift[i] = bm->patlen;139 for (i = 0; i < bm->patlen - 1; i++) {140 bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i;141 if (flags & TS_IGNORECASE)142 bm->bad_shift[tolower(bm->pattern[i])]143 = bm->patlen - 1 - i;144 }145 146 /* Compute the good shift array, used to match reocurrences 147 * of a subpattern */148 bm->good_shift[0] = 1;149 for (i = 1; i < bm->patlen; i++)150 bm->good_shift[i] = bm->patlen;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 }157 }158}159 160static struct ts_config *bm_init(const void *pattern, unsigned int len,161 gfp_t gfp_mask, int flags)162{163 struct ts_config *conf;164 struct ts_bm *bm;165 int i;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 173 conf->flags = flags;174 bm = ts_config_priv(conf);175 bm->patlen = len;176 bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;177 if (flags & TS_IGNORECASE)178 for (i = 0; i < len; i++)179 bm->pattern[i] = toupper(((u8 *)pattern)[i]);180 else181 memcpy(bm->pattern, pattern, len);182 compute_prefix_tbl(bm, flags);183 184 return conf;185}186 187static void *bm_get_pattern(struct ts_config *conf)188{189 struct ts_bm *bm = ts_config_priv(conf);190 return bm->pattern;191}192 193static 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 199static 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 209static int __init init_bm(void)210{211 return textsearch_register(&bm_ops);212}213 214static void __exit exit_bm(void)215{216 textsearch_unregister(&bm_ops);217}218 219MODULE_DESCRIPTION("Boyer-Moore text search implementation");220MODULE_LICENSE("GPL");221 222module_init(init_bm);223module_exit(exit_bm);224