linux-6.12.1/lib/ts_kmp.c

1 // SPDX-License-Identifier: GPL-2.0-or-later
3  * lib/ts_kmp.c		Knuth-Morris-Pratt text search implementation
9  *   Implements a linear-time string-matching algorithm due to Knuth,
11  *   computation of the transition function DELTA altogether. Its
15  *   the transition function DELTA to be computed efficiently
17  *   "q" = 0,1,...,m and any character "a" in SIGMA, the value
19  *   is needed to compute DELTA("q", "a") [2]. Since the array PI
20  *   has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
21  *   save a factor of |SIGMA| in the preprocessing time by computing
22  *   PI rather than DELTA.
45 	unsigned int i, q = 0, text_len, consumed = state->offset;  in kmp_find()
47 	const int icase = conf->flags & TS_IGNORECASE;  in kmp_find()
50 		text_len = conf->get_next_block(consumed, &text, conf, state);  in kmp_find()
56 			while (q > 0 && kmp->pattern[q]  in kmp_find()
58 				q = kmp->prefix_tbl[q - 1];  in kmp_find()
59 			if (kmp->pattern[q]  in kmp_find()
62 			if (unlikely(q == kmp->pattern_len)) {  in kmp_find()
63 				state->offset = consumed + i + 1;  in kmp_find()
64 				return state->offset - kmp->pattern_len;  in kmp_find()
83 			k = prefix_tbl[k-1];  in compute_prefix_tbl()
104 	conf->flags = flags;  in kmp_init()
106 	kmp->pattern_len = len;  in kmp_init()
107 	compute_prefix_tbl(pattern, len, kmp->prefix_tbl, flags);  in kmp_init()
108 	kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len;  in kmp_init()
111 			kmp->pattern[i] = toupper(((u8 *)pattern)[i]);  in kmp_init()
113 		memcpy(kmp->pattern, pattern, len);  in kmp_init()
121 	return kmp->pattern;  in kmp_get_pattern()
127 	return kmp->pattern_len;  in kmp_get_pattern_len()
150 MODULE_DESCRIPTION("Knuth-Morris-Pratt text search implementation");