Root/
Source at commit b386be689295730688885552666ea40b2e639b14 created 11 years 11 months ago. By Maarten ter Huurne, Revert "MIPS: JZ4740: reset: Initialize hibernate wakeup counters." | |
---|---|
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 | |
38 | #include <linux/kernel.h> |
39 | #include <linux/module.h> |
40 | #include <linux/types.h> |
41 | #include <linux/string.h> |
42 | #include <linux/ctype.h> |
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; |
67 | int shift = bm->patlen - 1, bs; |
68 | const u8 icase = conf->flags & TS_IGNORECASE; |
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++) |
80 | if ((icase ? toupper(text[shift-i]) |
81 | : text[shift-i]) |
82 | != bm->pattern[bm->patlen-1-i]) |
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 | |
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 | |
118 | static void compute_prefix_tbl(struct ts_bm *bm, int flags) |
119 | { |
120 | int i, j, g; |
121 | |
122 | for (i = 0; i < ASIZE; i++) |
123 | bm->bad_shift[i] = bm->patlen; |
124 | for (i = 0; i < bm->patlen - 1; i++) { |
125 | bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i; |
126 | if (flags & TS_IGNORECASE) |
127 | bm->bad_shift[tolower(bm->pattern[i])] |
128 | = bm->patlen - 1 - i; |
129 | } |
130 | |
131 | /* Compute the good shift array, used to match reocurrences |
132 | * of a subpattern */ |
133 | bm->good_shift[0] = 1; |
134 | for (i = 1; i < bm->patlen; i++) |
135 | bm->good_shift[i] = bm->patlen; |
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 | } |
142 | } |
143 | } |
144 | |
145 | static struct ts_config *bm_init(const void *pattern, unsigned int len, |
146 | gfp_t gfp_mask, int flags) |
147 | { |
148 | struct ts_config *conf; |
149 | struct ts_bm *bm; |
150 | int i; |
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 | |
158 | conf->flags = flags; |
159 | bm = ts_config_priv(conf); |
160 | bm->patlen = len; |
161 | bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len; |
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); |
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); |
208 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9