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