|
Packit |
284210 |
/*
|
|
Packit |
284210 |
* ModSecurity for Apache 2.x, http://www.modsecurity.org/
|
|
Packit |
284210 |
* Copyright (c) 2004-2013 Trustwave Holdings, Inc. (http://www.trustwave.com/)
|
|
Packit |
284210 |
*
|
|
Packit |
284210 |
* You may not use this file except in compliance with
|
|
Packit |
284210 |
* the License. You may obtain a copy of the License at
|
|
Packit |
284210 |
*
|
|
Packit |
284210 |
* http://www.apache.org/licenses/LICENSE-2.0
|
|
Packit |
284210 |
*
|
|
Packit |
284210 |
* If any of the files related to licensing are missing or if you have any
|
|
Packit |
284210 |
* other questions related to licensing please contact Trustwave Holdings, Inc.
|
|
Packit |
284210 |
* directly using the email address security@modsecurity.org.
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* Aho-Corasick Matching */
|
|
Packit |
284210 |
|
|
Packit |
284210 |
#include "acmp.h"
|
|
Packit |
284210 |
|
|
Packit |
284210 |
#ifdef ACMP_USE_UTF8
|
|
Packit |
284210 |
/* UTF support */
|
|
Packit |
284210 |
#include "utf8tables.h"
|
|
Packit |
284210 |
#else
|
|
Packit |
284210 |
/* No UTF support */
|
|
Packit |
284210 |
#define acmp_utf8_char_t long
|
|
Packit |
284210 |
#include <apr_lib.h>
|
|
Packit |
284210 |
#define utf8_lcase(a) apr_tolower(a)
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
|
|
Packit |
284210 |
#include <apr_tables.h>
|
|
Packit |
284210 |
#include <stdio.h>
|
|
Packit |
284210 |
#include <string.h>
|
|
Packit |
284210 |
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/*
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
* Data structures for acmp parser
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* One node in trie
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
typedef struct acmp_node_t acmp_node_t;
|
|
Packit |
284210 |
typedef struct acmp_btree_node_t acmp_btree_node_t;
|
|
Packit |
284210 |
struct acmp_node_t {
|
|
Packit |
284210 |
acmp_utf8_char_t letter;
|
|
Packit |
284210 |
int is_last;
|
|
Packit |
284210 |
acmp_callback_t callback;
|
|
Packit |
284210 |
void *callback_data;
|
|
Packit |
284210 |
int depth;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
acmp_node_t *child;
|
|
Packit |
284210 |
acmp_node_t *sibling;
|
|
Packit |
284210 |
acmp_node_t *fail;
|
|
Packit |
284210 |
acmp_node_t *parent;
|
|
Packit |
284210 |
acmp_node_t *o_match;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
acmp_btree_node_t *btree;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
apr_size_t hit_count;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
char *text;
|
|
Packit |
284210 |
char *pattern;
|
|
Packit |
284210 |
};
|
|
Packit |
284210 |
|
|
Packit |
284210 |
struct acmp_btree_node_t {
|
|
Packit |
284210 |
acmp_utf8_char_t letter;
|
|
Packit |
284210 |
acmp_btree_node_t *left;
|
|
Packit |
284210 |
acmp_btree_node_t *right;
|
|
Packit |
284210 |
acmp_node_t *node;
|
|
Packit |
284210 |
};
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Data related to parser, not to individual nodes
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
struct ACMP {
|
|
Packit |
284210 |
#ifdef ACMP_USE_UTF8
|
|
Packit |
284210 |
int is_utf8;
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
int is_case_sensitive;
|
|
Packit |
284210 |
apr_pool_t *parent_pool;
|
|
Packit |
284210 |
apr_pool_t *pool;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
int dict_count;
|
|
Packit |
284210 |
apr_size_t longest_entry;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
acmp_node_t *root_node;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
const char *data_start;
|
|
Packit |
284210 |
const char *data_end;
|
|
Packit |
284210 |
const char *data_pos;
|
|
Packit |
284210 |
apr_size_t data_len;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
apr_size_t *bp_buffer;
|
|
Packit |
284210 |
apr_size_t bp_buff_len;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
acmp_node_t *active_node;
|
|
Packit |
284210 |
char u8_buff[6];
|
|
Packit |
284210 |
apr_size_t u8buff_len;
|
|
Packit |
284210 |
apr_size_t hit_count;
|
|
Packit |
284210 |
int is_failtree_done;
|
|
Packit |
284210 |
int is_active;
|
|
Packit |
284210 |
apr_size_t byte_pos;
|
|
Packit |
284210 |
apr_size_t char_pos;
|
|
Packit |
284210 |
};
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/*
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
* Functions for UTF-8 support
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
|
|
Packit |
284210 |
#ifdef ACMP_USE_UTF8
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Returns length of utf-8 sequence based on its first byte
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static int utf8_seq_len(const char *first_byte) {
|
|
Packit |
284210 |
return utf8_seq_lengths[(unsigned int)(unsigned char)first_byte[0]];
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Returns length of utf8-encoded text
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static size_t utf8_strlen(const char *str) {
|
|
Packit |
284210 |
int len = 0;
|
|
Packit |
284210 |
const char *c = str;
|
|
Packit |
284210 |
while (*c != 0) {
|
|
Packit |
284210 |
c += utf8_seq_len(c);
|
|
Packit |
284210 |
len++;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
return len;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Returns ucs code for given utf-8 sequence
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static acmp_utf8_char_t utf8_decodechar(const char *str) {
|
|
Packit |
284210 |
int len = utf8_seq_len(str);
|
|
Packit |
284210 |
acmp_utf8_char_t ch = 0;
|
|
Packit |
284210 |
switch (len) {
|
|
Packit |
284210 |
case 6: ch += (unsigned char)*str++; ch <<= 6;
|
|
Packit |
284210 |
case 5: ch += (unsigned char)*str++; ch <<= 6;
|
|
Packit |
284210 |
case 4: ch += (unsigned char)*str++; ch <<= 6;
|
|
Packit |
284210 |
case 3: ch += (unsigned char)*str++; ch <<= 6;
|
|
Packit |
284210 |
case 2: ch += (unsigned char)*str++; ch <<= 6;
|
|
Packit |
284210 |
case 1: ch += (unsigned char)*str++;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
ch -= utf8_offsets[len - 1];
|
|
Packit |
284210 |
return ch;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Returns lowercase for given unicode character. Searches through
|
|
Packit |
284210 |
* utf8_lcase_map table, if it doesn't find the code assumes
|
|
Packit |
284210 |
* it doesn't have a lowercase variant and returns code itself.
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static long utf8_lcase(acmp_utf8_char_t ucs_code) {
|
|
Packit |
284210 |
long mid, left, right;
|
|
Packit |
284210 |
left = 1;
|
|
Packit |
284210 |
right = UTF8_LCASEMAP_LEN * 2 + 1;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
while (left <= right) {
|
|
Packit |
284210 |
mid = (left + right) >> 1;
|
|
Packit |
284210 |
mid -= (mid % 2); mid++;
|
|
Packit |
284210 |
if (ucs_code > utf8_lcase_map[mid])
|
|
Packit |
284210 |
left = mid + 2;
|
|
Packit |
284210 |
else if (ucs_code < utf8_lcase_map[mid])
|
|
Packit |
284210 |
right = mid - 2;
|
|
Packit |
284210 |
else if (ucs_code == utf8_lcase_map[mid])
|
|
Packit |
284210 |
return utf8_lcase_map[mid - 1];
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
return ucs_code;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/*
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
* Code for local / static utility functions
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Returns length of given string for parser's encoding
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static size_t acmp_strlen(ACMP *parser, const char *str) {
|
|
Packit |
284210 |
#ifdef ACMP_USE_UTF8
|
|
Packit |
284210 |
return (parser->is_utf8 == 0) ? strlen(str) : utf8_strlen(str);
|
|
Packit |
284210 |
#else
|
|
Packit |
284210 |
return strlen(str);
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Turns string to array of ucs values, depending on parser's encoding
|
|
Packit |
284210 |
* str - string to convert, doesn't have to be NULL-terminated
|
|
Packit |
284210 |
* ucs_chars - where to write ucs values
|
|
Packit |
284210 |
* len - length of input string
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static void acmp_strtoucs(ACMP *parser, const char *str, acmp_utf8_char_t *ucs_chars, int len) {
|
|
Packit |
284210 |
int i;
|
|
Packit |
284210 |
const char *c = str;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
#ifdef ACMP_USE_UTF8
|
|
Packit |
284210 |
if (parser->is_utf8) {
|
|
Packit |
284210 |
for (i = 0; i < len; i++) {
|
|
Packit |
284210 |
*(ucs_chars++) = utf8_decodechar(c);
|
|
Packit |
284210 |
c += utf8_seq_len(c);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
} else
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
{
|
|
Packit |
284210 |
for (i = 0; i < len; i++) {
|
|
Packit |
284210 |
*(ucs_chars++) = *(c++);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Returns node with given letter, or null if not found
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static acmp_node_t *acmp_child_for_code(acmp_node_t *parent_node, acmp_utf8_char_t ucs_code) {
|
|
Packit |
284210 |
acmp_node_t *node = parent_node->child;
|
|
Packit |
284210 |
if (node == NULL) return NULL;
|
|
Packit |
284210 |
for (;;) {
|
|
Packit |
284210 |
if (node->letter == ucs_code) return node;
|
|
Packit |
284210 |
node = node->sibling;
|
|
Packit |
284210 |
if (node == NULL) return NULL;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Adds node to parent node, if it is not already there
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static void acmp_add_node_to_parent(acmp_node_t *parent, acmp_node_t *child) {
|
|
Packit |
284210 |
acmp_node_t *node = NULL;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
child->parent = parent;
|
|
Packit |
284210 |
if (parent->child == NULL) {
|
|
Packit |
284210 |
parent->child = child;
|
|
Packit |
284210 |
return;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
node = parent->child;
|
|
Packit |
284210 |
for (;;) {
|
|
Packit |
284210 |
if (node == child) return;
|
|
Packit |
284210 |
if (node->sibling == NULL) {
|
|
Packit |
284210 |
node->sibling = child;
|
|
Packit |
284210 |
return;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
node = node->sibling;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Copies values from one node to another, without child/sibling/fail pointers
|
|
Packit |
284210 |
* and without state variables.
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static void acmp_clone_node_no_state(acmp_node_t *from, acmp_node_t *to) {
|
|
Packit |
284210 |
memcpy(to, from, sizeof(acmp_node_t));
|
|
Packit |
284210 |
to->child = NULL;
|
|
Packit |
284210 |
to->sibling = NULL;
|
|
Packit |
284210 |
to->fail = NULL;
|
|
Packit |
284210 |
to->hit_count = 0;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
static inline acmp_node_t *acmp_btree_find(acmp_node_t *node, acmp_utf8_char_t letter) {
|
|
Packit |
284210 |
acmp_btree_node_t *bnode = node->btree;
|
|
Packit |
284210 |
for (;;) {
|
|
Packit |
284210 |
if (bnode == NULL) return NULL;
|
|
Packit |
284210 |
if (bnode->letter == letter) return bnode->node;
|
|
Packit |
284210 |
if (bnode->letter > letter) {
|
|
Packit |
284210 |
bnode = bnode->left;
|
|
Packit |
284210 |
} else {
|
|
Packit |
284210 |
bnode = bnode->right;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
*
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static inline acmp_node_t *acmp_goto(acmp_node_t *node, acmp_utf8_char_t letter) {
|
|
Packit |
284210 |
return acmp_btree_find(node, letter);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Connects each node with its first fail node that is end of a phrase.
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static void acmp_connect_other_matches(ACMP *parser, acmp_node_t *node) {
|
|
Packit |
284210 |
acmp_node_t *child, *om;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
for (child = node->child; child != NULL; child = child->sibling) {
|
|
Packit |
284210 |
if (child->fail == NULL) continue;
|
|
Packit |
284210 |
for (om = child->fail; om != parser->root_node; om = om->fail) {
|
|
Packit |
284210 |
if (om->is_last) {
|
|
Packit |
284210 |
child->o_match = om;
|
|
Packit |
284210 |
break;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* Go recursively through children of this node that have a child node */
|
|
Packit |
284210 |
for(child = node->child; child != NULL; child = child->sibling) {
|
|
Packit |
284210 |
if (child->child != NULL) acmp_connect_other_matches(parser, child);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Adds leaves to binary tree, working from sorted array of keyword tree nodes
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static void acmp_add_btree_leaves(acmp_btree_node_t *node, acmp_node_t *nodes[],
|
|
Packit |
284210 |
int pos, int lb, int rb, apr_pool_t *pool) {
|
|
Packit |
284210 |
|
|
Packit |
284210 |
int left = 0, right = 0;
|
|
Packit |
284210 |
if ((pos - lb) > 1) {
|
|
Packit |
284210 |
left = lb + (pos - lb) / 2;
|
|
Packit |
284210 |
node->left = apr_pcalloc(pool, sizeof(acmp_btree_node_t));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
node->left->node = nodes[left];
|
|
Packit |
284210 |
node->left->letter = nodes[left]->letter;
|
|
Packit |
284210 |
#ifdef DEBUG_ACMP
|
|
Packit |
284210 |
fprintf(stderr, "%lc ->left %lc\n", (wint_t)node->node->letter, (wint_t)node->left->node->letter);
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if ((rb - pos) > 1) {
|
|
Packit |
284210 |
right = pos + (rb - pos) / 2;
|
|
Packit |
284210 |
node->right = apr_pcalloc(pool, sizeof(acmp_btree_node_t));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
node->right->node = nodes[right];
|
|
Packit |
284210 |
node->right->letter = nodes[right]->letter;
|
|
Packit |
284210 |
#ifdef DEBUG_ACMP
|
|
Packit |
284210 |
fprintf(stderr, "%lc ->right %lc\n", (wint_t)node->node->letter, (wint_t)node->right->node->letter);
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (node->right != NULL) {
|
|
Packit |
284210 |
acmp_add_btree_leaves(node->right, nodes, right, pos, rb, pool);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (node->left != NULL) {
|
|
Packit |
284210 |
acmp_add_btree_leaves(node->left, nodes, left, lb, pos, pool);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Builds balanced binary tree from children nodes of given node.
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static void acmp_build_binary_tree(ACMP *parser, acmp_node_t *node) {
|
|
Packit |
284210 |
apr_size_t count, i, j;
|
|
Packit |
284210 |
acmp_node_t *child = node->child;
|
|
Packit |
284210 |
acmp_node_t **nodes;
|
|
Packit |
284210 |
apr_size_t pos;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* Build an array big enough */
|
|
Packit |
284210 |
for (count = 0; child != NULL; child = child->sibling) count++;
|
|
Packit |
284210 |
nodes = apr_pcalloc(parser->pool, count * sizeof(acmp_node_t *));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* ENH: Combine this in the loop below - we do not need two loops */
|
|
Packit |
284210 |
child = node->child;
|
|
Packit |
284210 |
for (i = 0; i < count; i++) {
|
|
Packit |
284210 |
nodes[i] = child;
|
|
Packit |
284210 |
child = child->sibling;
|
|
Packit |
284210 |
};
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* We have array with all children of the node and number of those children
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
for (i = 0; i < count - 1; i++)
|
|
Packit |
284210 |
for (j = i + 1; j < count; j++) {
|
|
Packit |
284210 |
acmp_node_t *tmp;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
if (nodes[i]->letter < nodes[j]->letter) continue;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
tmp = nodes[i];
|
|
Packit |
284210 |
nodes[i] = nodes[j];
|
|
Packit |
284210 |
nodes[j] = tmp;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
node->btree = apr_pcalloc(parser->pool, sizeof(acmp_btree_node_t));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
pos = count / 2;
|
|
Packit |
284210 |
node->btree->node = nodes[pos];
|
|
Packit |
284210 |
node->btree->letter = nodes[pos]->letter;
|
|
Packit |
284210 |
acmp_add_btree_leaves(node->btree, nodes, pos, -1, count, parser->pool);
|
|
Packit |
284210 |
for (i = 0; i < count; i++) {
|
|
Packit |
284210 |
if (nodes[i]->child != NULL) acmp_build_binary_tree(parser, nodes[i]);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Constructs fail paths on keyword trie
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
static apr_status_t acmp_connect_fail_branches(ACMP *parser) {
|
|
Packit |
284210 |
/* Already connected ? */
|
|
Packit |
284210 |
acmp_node_t *child, *node, *goto_node;
|
|
Packit |
284210 |
apr_array_header_t *arr, *arr2, *tmp;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
if (parser->is_failtree_done != 0) return APR_SUCCESS;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
parser->root_node->text = "";
|
|
Packit |
284210 |
arr = apr_array_make(parser->pool, 32, sizeof(acmp_node_t *));
|
|
Packit |
284210 |
arr2 = apr_array_make(parser->pool, 32, sizeof(acmp_node_t *));
|
|
Packit |
284210 |
|
|
Packit |
284210 |
parser->root_node->fail = parser->root_node;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* All first-level children will fail back to root node */
|
|
Packit |
284210 |
for (child = parser->root_node->child; child != NULL; child = child->sibling) {
|
|
Packit |
284210 |
child->fail = parser->root_node;
|
|
Packit |
284210 |
*(acmp_node_t **)apr_array_push(arr) = child;
|
|
Packit |
284210 |
#ifdef DEBUG_ACMP
|
|
Packit |
284210 |
fprintf(stderr, "fail direction: *%s* => *%s*\n", child->text, child->fail->text);
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
for (;;) {
|
|
Packit |
284210 |
while (apr_is_empty_array(arr) == 0) {
|
|
Packit |
284210 |
node = *(acmp_node_t **)apr_array_pop(arr);
|
|
Packit |
284210 |
node->fail = parser->root_node;
|
|
Packit |
284210 |
if (node->parent != parser->root_node) {
|
|
Packit |
284210 |
goto_node = acmp_child_for_code(node->parent->fail, node->letter);
|
|
Packit |
284210 |
node->fail = (goto_node != NULL) ? goto_node : parser->root_node;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
#ifdef DEBUG_ACMP
|
|
Packit |
284210 |
fprintf(stderr, "fail direction: *%s* => *%s*\n", node->text, node->fail->text);
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
child = node->child;
|
|
Packit |
284210 |
while (child != NULL) {
|
|
Packit |
284210 |
*(acmp_node_t **)apr_array_push(arr2) = child;
|
|
Packit |
284210 |
child = child->sibling;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (apr_is_empty_array(arr2) != 0) break;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
tmp = arr;
|
|
Packit |
284210 |
arr = arr2;
|
|
Packit |
284210 |
arr2 = tmp;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
acmp_connect_other_matches(parser, parser->root_node);
|
|
Packit |
284210 |
if (parser->root_node->child != NULL) acmp_build_binary_tree(parser, parser->root_node);
|
|
Packit |
284210 |
parser->is_failtree_done = 1;
|
|
Packit |
284210 |
return APR_SUCCESS;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/*
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
*******************************************************************************
|
|
Packit |
284210 |
* Code for functions from header file
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* flags - OR-ed values of ACMP_FLAG constants
|
|
Packit |
284210 |
* pool - apr_pool to use as parent pool, can be set to NULL
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
ACMP *acmp_create(int flags, apr_pool_t *pool) {
|
|
Packit |
284210 |
apr_status_t rc;
|
|
Packit |
284210 |
apr_pool_t *p;
|
|
Packit |
284210 |
ACMP *parser;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
rc = apr_pool_create(&p, pool);
|
|
Packit |
284210 |
if (rc != APR_SUCCESS) return NULL;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
parser = apr_pcalloc(p, sizeof(ACMP));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
parser->pool = p;
|
|
Packit |
284210 |
parser->parent_pool = pool;
|
|
Packit |
284210 |
#ifdef ACMP_USE_UTF8
|
|
Packit |
284210 |
parser->is_utf8 = (flags & ACMP_FLAG_UTF8) == 0 ? 0 : 1;
|
|
Packit |
284210 |
#endif
|
|
Packit |
284210 |
parser->is_case_sensitive = (flags & ACMP_FLAG_CASE_SENSITIVE) == 0 ? 0 : 1;
|
|
Packit |
284210 |
parser->root_node = apr_pcalloc(p, sizeof(acmp_node_t));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
return parser;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Creates fail tree and initializes buffer
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
apr_status_t acmp_prepare(ACMP *parser) {
|
|
Packit |
284210 |
apr_status_t st;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
if (parser->bp_buff_len < parser->longest_entry) {
|
|
Packit |
284210 |
parser->bp_buff_len = parser->longest_entry * 2;
|
|
Packit |
284210 |
parser->bp_buffer = apr_pcalloc(parser->pool, sizeof(apr_size_t) * parser->bp_buff_len);
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
st = acmp_connect_fail_branches(parser);
|
|
Packit |
284210 |
parser->active_node = parser->root_node;
|
|
Packit |
284210 |
if (st != APR_SUCCESS) return st;
|
|
Packit |
284210 |
parser->is_active = 1;
|
|
Packit |
284210 |
return APR_SUCCESS;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Adds pattern to parser
|
|
Packit |
284210 |
* parser - ACMP parser
|
|
Packit |
284210 |
* pattern - string with pattern to match
|
|
Packit |
284210 |
* callback - Optional, pointer to an acmp_callback_t function
|
|
Packit |
284210 |
* data - pointer to data that will be passed to callback function, only used if callback
|
|
Packit |
284210 |
* is supplied
|
|
Packit |
284210 |
* len - Length of pattern in characters, if zero string length is used.
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
apr_status_t acmp_add_pattern(ACMP *parser, const char *pattern,
|
|
Packit |
284210 |
acmp_callback_t callback, void *data, apr_size_t len)
|
|
Packit |
284210 |
{
|
|
Packit |
284210 |
size_t length, i, j;
|
|
Packit |
284210 |
acmp_utf8_char_t *ucs_chars;
|
|
Packit |
284210 |
acmp_node_t *parent, *child;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
if (parser->is_active != 0) return APR_EGENERAL;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
length = (len == 0) ? acmp_strlen(parser, pattern) : len;
|
|
Packit |
284210 |
ucs_chars = apr_pcalloc(parser->pool, length * sizeof(acmp_utf8_char_t));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
|
|
Packit |
284210 |
parent = parser->root_node;
|
|
Packit |
284210 |
acmp_strtoucs(parser, pattern, ucs_chars, length);
|
|
Packit |
284210 |
|
|
Packit |
284210 |
for (i = 0; i < length; i++) {
|
|
Packit |
284210 |
acmp_utf8_char_t letter = ucs_chars[i];
|
|
Packit |
284210 |
if (parser->is_case_sensitive == 0) {
|
|
Packit |
284210 |
letter = utf8_lcase(letter);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
child = acmp_child_for_code(parent, letter);
|
|
Packit |
284210 |
if (child == NULL) {
|
|
Packit |
284210 |
child = apr_pcalloc(parser->pool, sizeof(acmp_node_t));
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
child->pattern = "";
|
|
Packit |
284210 |
child->letter = letter;
|
|
Packit |
284210 |
child->depth = i;
|
|
Packit |
284210 |
child->text = apr_pcalloc(parser->pool, strlen(pattern) + 2);
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
for (j = 0; j <= i; j++) child->text[j] = pattern[j];
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (i == length - 1) {
|
|
Packit |
284210 |
if (child->is_last == 0) {
|
|
Packit |
284210 |
parser->dict_count++;
|
|
Packit |
284210 |
child->is_last = 1;
|
|
Packit |
284210 |
child->pattern = apr_pcalloc(parser->pool, strlen(pattern) + 2);
|
|
Packit |
284210 |
/* ENH: Check alloc succeded */
|
|
Packit |
284210 |
strcpy(child->pattern, pattern);
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
child->callback = callback;
|
|
Packit |
284210 |
child->callback_data = data;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
acmp_add_node_to_parent(parent, child);
|
|
Packit |
284210 |
parent = child;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (length > parser->longest_entry) parser->longest_entry = length;
|
|
Packit |
284210 |
parser->is_failtree_done = 0;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
return APR_SUCCESS;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/**
|
|
Packit |
284210 |
* Process the data using ACMPT to keep state, and ACMPT's parser to keep the tree
|
|
Packit |
284210 |
*/
|
|
Packit |
284210 |
apr_status_t acmp_process_quick(ACMPT *acmpt, const char **match, const char *data, apr_size_t len) {
|
|
Packit |
284210 |
ACMP *parser;
|
|
Packit |
284210 |
acmp_node_t *node, *go_to;
|
|
Packit |
284210 |
const char *end;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
if (acmpt->parser->is_failtree_done == 0) {
|
|
Packit |
284210 |
acmp_prepare(acmpt->parser);
|
|
Packit |
284210 |
};
|
|
Packit |
284210 |
|
|
Packit |
284210 |
parser = acmpt->parser;
|
|
Packit |
284210 |
if (acmpt->ptr == NULL) acmpt->ptr = parser->root_node;
|
|
Packit |
284210 |
node = acmpt->ptr;
|
|
Packit |
284210 |
end = data + len;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
while (data < end) {
|
|
Packit |
284210 |
acmp_utf8_char_t letter = (unsigned char)*data++;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
if (parser->is_case_sensitive == 0) letter = utf8_lcase(letter);
|
|
Packit |
284210 |
|
|
Packit |
284210 |
go_to = NULL;
|
|
Packit |
284210 |
while (go_to == NULL) {
|
|
Packit |
284210 |
go_to = acmp_goto(node, letter);
|
|
Packit |
284210 |
if (go_to != NULL) {
|
|
Packit |
284210 |
if (go_to->is_last) {
|
|
Packit |
284210 |
*match = go_to->text;
|
|
Packit |
284210 |
return 1;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (node == parser->root_node) break;
|
|
Packit |
284210 |
if (go_to == NULL) node = node->fail;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
if (go_to != NULL) node = go_to;
|
|
Packit |
284210 |
|
|
Packit |
284210 |
/* If node has o_match, then we found a pattern */
|
|
Packit |
284210 |
if (node->o_match != NULL) {
|
|
Packit |
284210 |
*match = node->text;
|
|
Packit |
284210 |
return 1;
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
}
|
|
Packit |
284210 |
acmpt->ptr = node;
|
|
Packit |
284210 |
return 0;
|
|
Packit |
284210 |
}
|