linux/lib/ts_kmp.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * lib/ts_kmp.c		Knuth-Morris-Pratt text search implementation
 *
 * Authors:	Thomas Graf <[email protected]>
 *
 * ==========================================================================
 * 
 *   Implements a linear-time string-matching algorithm due to Knuth,
 *   Morris, and Pratt [1]. Their algorithm avoids the explicit
 *   computation of the transition function DELTA altogether. Its
 *   matching time is O(n), for n being length(text), using just an
 *   auxiliary function PI[1..m], for m being length(pattern),
 *   precomputed from the pattern in time O(m). The array PI allows
 *   the transition function DELTA to be computed efficiently
 *   "on the fly" as needed. Roughly speaking, for any state
 *   "q" = 0,1,...,m and any character "a" in SIGMA, the value
 *   PI["q"] contains the information that is independent of "a" and
 *   is needed to compute DELTA("q", "a") [2]. Since the array PI
 *   has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
 *   save a factor of |SIGMA| in the preprocessing time by computing
 *   PI rather than DELTA.
 *
 *   [1] Cormen, Leiserson, Rivest, Stein
 *       Introdcution to Algorithms, 2nd Edition, MIT Press
 *   [2] See finite automaton theory
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/string.h>
#include <linux/ctype.h>
#include <linux/textsearch.h>

struct ts_kmp
{ … };

static unsigned int kmp_find(struct ts_config *conf, struct ts_state *state)
{ … }

static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len,
				      unsigned int *prefix_tbl, int flags)
{ … }

static struct ts_config *kmp_init(const void *pattern, unsigned int len,
				  gfp_t gfp_mask, int flags)
{ … }

static void *kmp_get_pattern(struct ts_config *conf)
{ … }

static unsigned int kmp_get_pattern_len(struct ts_config *conf)
{ … }

static struct ts_ops kmp_ops = …;

static int __init init_kmp(void)
{ … }

static void __exit exit_kmp(void)
{ … }

MODULE_DESCRIPTION(…) …;
MODULE_LICENSE(…) …;

module_init(…) …;
module_exit(exit_kmp);