]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - lib/ts_bm.c
2 * lib/ts_bm.c Boyer-Moore text search implementation
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.
9 * Authors: Pablo Neira Ayuso <pablo@eurodev.net>
11 * ==========================================================================
13 * Implements Boyer-Moore string matching algorithm:
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
20 * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004
21 * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
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.
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.
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.
38 #include <linux/kernel.h>
39 #include <linux/module.h>
40 #include <linux/types.h>
41 #include <linux/string.h>
42 #include <linux/textsearch.h>
44 /* Alphabet size, use ASCII */
50 #define DEBUGP(args, format...)
57 unsigned int bad_shift
[ASIZE
];
58 unsigned int good_shift
[0];
61 static unsigned int bm_find(struct ts_config
*conf
, struct ts_state
*state
)
63 struct ts_bm
*bm
= ts_config_priv(conf
);
64 unsigned int i
, text_len
, consumed
= state
->offset
;
66 int shift
= bm
->patlen
- 1, bs
;
69 text_len
= conf
->get_next_block(consumed
, &text
, conf
, state
);
71 if (unlikely(text_len
== 0))
74 while (shift
< text_len
) {
75 DEBUGP("Searching in position %d (%c)\n",
77 for (i
= 0; i
< bm
->patlen
; i
++)
78 if (text
[shift
-i
] != bm
->pattern
[bm
->patlen
-1-i
])
81 /* London calling... */
83 return consumed
+= (shift
-(bm
->patlen
-1));
85 next
: bs
= bm
->bad_shift
[text
[shift
-i
]];
87 /* Now jumping to... */
88 shift
= max_t(int, shift
-i
+bs
, shift
+bm
->good_shift
[i
]);
96 static int subpattern(u8
*pattern
, int i
, int j
, int g
)
98 int x
= i
+g
-1, y
= j
+g
-1, ret
= 0;
100 while(pattern
[x
--] == pattern
[y
--]) {
106 ret
= pattern
[i
-1] != pattern
[j
-1];
114 static void compute_prefix_tbl(struct ts_bm
*bm
)
118 for (i
= 0; i
< ASIZE
; i
++)
119 bm
->bad_shift
[i
] = bm
->patlen
;
120 for (i
= 0; i
< bm
->patlen
- 1; i
++)
121 bm
->bad_shift
[bm
->pattern
[i
]] = bm
->patlen
- 1 - i
;
123 /* Compute the good shift array, used to match reocurrences
125 bm
->good_shift
[0] = 1;
126 for (i
= 1; i
< bm
->patlen
; i
++)
127 bm
->good_shift
[i
] = bm
->patlen
;
128 for (i
= bm
->patlen
-1, g
= 1; i
> 0; g
++, i
--) {
129 for (j
= i
-1; j
>= 1-g
; j
--)
130 if (subpattern(bm
->pattern
, i
, j
, g
)) {
131 bm
->good_shift
[g
] = bm
->patlen
-j
-g
;
137 static struct ts_config
*bm_init(const void *pattern
, unsigned int len
,
140 struct ts_config
*conf
;
142 unsigned int prefix_tbl_len
= len
* sizeof(unsigned int);
143 size_t priv_size
= sizeof(*bm
) + len
+ prefix_tbl_len
;
145 conf
= alloc_ts_config(priv_size
, gfp_mask
);
149 bm
= ts_config_priv(conf
);
151 bm
->pattern
= (u8
*) bm
->good_shift
+ prefix_tbl_len
;
152 memcpy(bm
->pattern
, pattern
, len
);
153 compute_prefix_tbl(bm
);
158 static void *bm_get_pattern(struct ts_config
*conf
)
160 struct ts_bm
*bm
= ts_config_priv(conf
);
164 static unsigned int bm_get_pattern_len(struct ts_config
*conf
)
166 struct ts_bm
*bm
= ts_config_priv(conf
);
170 static struct ts_ops bm_ops
= {
174 .get_pattern
= bm_get_pattern
,
175 .get_pattern_len
= bm_get_pattern_len
,
176 .owner
= THIS_MODULE
,
177 .list
= LIST_HEAD_INIT(bm_ops
.list
)
180 static int __init
init_bm(void)
182 return textsearch_register(&bm_ops
);
185 static void __exit
exit_bm(void)
187 textsearch_unregister(&bm_ops
);
190 MODULE_LICENSE("GPL");
192 module_init(init_bm
);
193 module_exit(exit_bm
);