1 /* 2 * lib/ts_kmp.c Knuth-Morris-Pratt 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: Thomas Graf <tgraf@suug.ch> 10 * 11 * ========================================================================== 12 * 13 * Implements a linear-time string-matching algorithm due to Knuth, 14 * Morris, and Pratt [1]. Their algorithm avoids the explicit 15 * computation of the transition function DELTA altogether. Its 16 * matching time is O(n), for n being length(text), using just an 17 * auxiliary function PI[1..m], for m being length(pattern), 18 * precomputed from the pattern in time O(m). The array PI allows 19 * the transition function DELTA to be computed efficiently 20 * "on the fly" as needed. Roughly speaking, for any state 21 * "q" = 0,1,...,m and any character "a" in SIGMA, the value 22 * PI["q"] contains the information that is independent of "a" and 23 * is needed to compute DELTA("q", "a") [2]. Since the array PI 24 * has only m entries, whereas DELTA has O(m|SIGMA|) entries, we 25 * save a factor of |SIGMA| in the preprocessing time by computing 26 * PI rather than DELTA. 27 * 28 * [1] Cormen, Leiserson, Rivest, Stein 29 * Introdcution to Algorithms, 2nd Edition, MIT Press 30 * [2] See finite automaton theory 31 */ 32 33 #include <linux/module.h> 34 #include <linux/types.h> 35 #include <linux/string.h> 36 #include <linux/ctype.h> 37 #include <linux/textsearch.h> 38 39 struct ts_kmp 40 { 41 u8 * pattern; 42 unsigned int pattern_len; 43 unsigned int prefix_tbl[0]; 44 }; 45 46 static unsigned int kmp_find(struct ts_config *conf, struct ts_state *state) 47 { 48 struct ts_kmp *kmp = ts_config_priv(conf); 49 unsigned int i, q = 0, text_len, consumed = state->offset; 50 const u8 *text; 51 const int icase = conf->flags & TS_IGNORECASE; 52 53 for (;;) { 54 text_len = conf->get_next_block(consumed, &text, conf, state); 55 56 if (unlikely(text_len == 0)) 57 break; 58 59 for (i = 0; i < text_len; i++) { 60 while (q > 0 && kmp->pattern[q] 61 != (icase ? toupper(text[i]) : text[i])) 62 q = kmp->prefix_tbl[q - 1]; 63 if (kmp->pattern[q] 64 == (icase ? toupper(text[i]) : text[i])) 65 q++; 66 if (unlikely(q == kmp->pattern_len)) { 67 state->offset = consumed + i + 1; 68 return state->offset - kmp->pattern_len; 69 } 70 } 71 72 consumed += text_len; 73 } 74 75 return UINT_MAX; 76 } 77 78 static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len, 79 unsigned int *prefix_tbl, int flags) 80 { 81 unsigned int k, q; 82 const u8 icase = flags & TS_IGNORECASE; 83 84 for (k = 0, q = 1; q < len; q++) { 85 while (k > 0 && (icase ? toupper(pattern[k]) : pattern[k]) 86 != (icase ? toupper(pattern[q]) : pattern[q])) 87 k = prefix_tbl[k-1]; 88 if ((icase ? toupper(pattern[k]) : pattern[k]) 89 == (icase ? toupper(pattern[q]) : pattern[q])) 90 k++; 91 prefix_tbl[q] = k; 92 } 93 } 94 95 static struct ts_config *kmp_init(const void *pattern, unsigned int len, 96 gfp_t gfp_mask, int flags) 97 { 98 struct ts_config *conf; 99 struct ts_kmp *kmp; 100 int i; 101 unsigned int prefix_tbl_len = len * sizeof(unsigned int); 102 size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len; 103 104 conf = alloc_ts_config(priv_size, gfp_mask); 105 if (IS_ERR(conf)) 106 return conf; 107 108 conf->flags = flags; 109 kmp = ts_config_priv(conf); 110 kmp->pattern_len = len; 111 compute_prefix_tbl(pattern, len, kmp->prefix_tbl, flags); 112 kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len; 113 if (flags & TS_IGNORECASE) 114 for (i = 0; i < len; i++) 115 kmp->pattern[i] = toupper(((u8 *)pattern)[i]); 116 else 117 memcpy(kmp->pattern, pattern, len); 118 119 return conf; 120 } 121 122 static void *kmp_get_pattern(struct ts_config *conf) 123 { 124 struct ts_kmp *kmp = ts_config_priv(conf); 125 return kmp->pattern; 126 } 127 128 static unsigned int kmp_get_pattern_len(struct ts_config *conf) 129 { 130 struct ts_kmp *kmp = ts_config_priv(conf); 131 return kmp->pattern_len; 132 } 133 134 static struct ts_ops kmp_ops = { 135 .name = "kmp", 136 .find = kmp_find, 137 .init = kmp_init, 138 .get_pattern = kmp_get_pattern, 139 .get_pattern_len = kmp_get_pattern_len, 140 .owner = THIS_MODULE, 141 .list = LIST_HEAD_INIT(kmp_ops.list) 142 }; 143 144 static int __init init_kmp(void) 145 { 146 return textsearch_register(&kmp_ops); 147 } 148 149 static void __exit exit_kmp(void) 150 { 151 textsearch_unregister(&kmp_ops); 152 } 153 154 MODULE_LICENSE("GPL"); 155 156 module_init(init_kmp); 157 module_exit(exit_kmp); 158