Subversion Repositories test_project

/*

 * lib/ts_kmp.c         Knuth-Morris-Pratt text search implementation

 *

 *              This program is free software; you can redistribute it and/or

 *              modify it under the terms of the GNU General Public License

 *              as published by the Free Software Foundation; either version

 *              2 of the License, or (at your option) any later version.

 *

 * Authors:     Thomas Graf <tgraf@suug.ch>

 *

 * ==========================================================================

 *

 *   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 automation theory

 */

#include <linux/module.h>

#include <linux/types.h>

#include <linux/string.h>

#include <linux/textsearch.h>

struct ts_kmp

{

        u8 *            pattern;

        unsigned int    pattern_len;

        unsigned int    prefix_tbl[0];

};

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

{

        struct ts_kmp *kmp = ts_config_priv(conf);

        unsigned int i, q = 0, text_len, consumed = state->offset;

        const u8 *text;

        for (;;) {

                text_len = conf->get_next_block(consumed, &text, conf, state);

                if (unlikely(text_len == 0))

                        break;

                for (i = 0; i < text_len; i++) {

                        while (q > 0 && kmp->pattern[q] != text[i])

                                q = kmp->prefix_tbl[q - 1];

                        if (kmp->pattern[q] == text[i])

                                q++;

                        if (unlikely(q == kmp->pattern_len)) {

                                state->offset = consumed + i + 1;

                                return state->offset - kmp->pattern_len;

                        }

                }

                consumed += text_len;

        }

        return UINT_MAX;

}

static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len,

                                      unsigned int *prefix_tbl)

{

        unsigned int k, q;

        for (k = 0, q = 1; q < len; q++) {

                while (k > 0 && pattern[k] != pattern[q])

                        k = prefix_tbl[k-1];

                if (pattern[k] == pattern[q])

                        k++;

                prefix_tbl[q] = k;

        }

}

static struct ts_config *kmp_init(const void *pattern, unsigned int len,

                                  gfp_t gfp_mask)

{

        struct ts_config *conf;

        struct ts_kmp *kmp;

        unsigned int prefix_tbl_len = len * sizeof(unsigned int);

        size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len;

        conf = alloc_ts_config(priv_size, gfp_mask);

        if (IS_ERR(conf))

                return conf;

        kmp = ts_config_priv(conf);

        kmp->pattern_len = len;

        compute_prefix_tbl(pattern, len, kmp->prefix_tbl);

        kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len;

        memcpy(kmp->pattern, pattern, len);

        return conf;

}

static void *kmp_get_pattern(struct ts_config *conf)

{

        struct ts_kmp *kmp = ts_config_priv(conf);

        return kmp->pattern;

}

static unsigned int kmp_get_pattern_len(struct ts_config *conf)

{

        struct ts_kmp *kmp = ts_config_priv(conf);

        return kmp->pattern_len;

}

static struct ts_ops kmp_ops = {

        .name             = "kmp",

        .find             = kmp_find,

        .init             = kmp_init,

        .get_pattern      = kmp_get_pattern,

        .get_pattern_len  = kmp_get_pattern_len,

        .owner            = THIS_MODULE,

        .list             = LIST_HEAD_INIT(kmp_ops.list)

};

static int __init init_kmp(void)

{

        return textsearch_register(&kmp_ops);

}

static void __exit exit_kmp(void)

{

        textsearch_unregister(&kmp_ops);

}

MODULE_LICENSE("GPL");

module_init(init_kmp);

module_exit(exit_kmp);