apache2/acmp.c

   1 /*
   2  * ModSecurity for Apache 2.x, http://www.modsecurity.org/
   3  * Copyright (c) 2004-2009 Breach Security, Inc. (http://www.breach.com/)
   4  *
   5  * This product is released under the terms of the General Public Licence,
   6  * version 2 (GPLv2). Please refer to the file LICENSE (included with this
   7  * distribution) which contains the complete text of the licence.
   8  *
   9  * There are special exceptions to the terms and conditions of the GPL
  10  * as it is applied to this software. View the full text of the exception in
  11  * file MODSECURITY_LICENSING_EXCEPTION in the directory of this software
  12  * distribution.
  13  *
  14  * If any of the files related to licensing are missing or if you have any
  15  * other questions related to licensing please contact Breach Security, Inc.
  16  * directly using the email address support@breach.com.
  17  *
  18  */
  19
  20 /* Aho-Corasick Matching  */
  21
  22 #include "acmp.h"
  23
  24 #ifdef ACMP_USE_UTF8
  25 /* UTF support */
  26 #include "utf8tables.h"
  27 #else
  28 /* No UTF support */
  29 #define acmp_utf8_char_t long
  30 #include <apr_lib.h>
  31 #define utf8_lcase(a) apr_tolower(a)
  32 #endif
  33
  34 #include <apr_tables.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37
  38
  39 /*
  40  *******************************************************************************
  41  *******************************************************************************
  42  * Data structures for acmp parser
  43  */
  44
  45  /**
  46   * One node in trie
  47   */
  48 typedef struct acmp_node_t acmp_node_t;
  49 typedef struct acmp_btree_node_t acmp_btree_node_t;
  50 struct acmp_node_t {
  51     acmp_utf8_char_t letter;
  52     int  is_last;
  53     acmp_callback_t callback;
  54     void *callback_data;
  55     int depth;
  56
  57     acmp_node_t *child;
  58     acmp_node_t *sibling;
  59     acmp_node_t *fail;
  60     acmp_node_t *parent;
  61     acmp_node_t *o_match;
  62
  63     acmp_btree_node_t *btree;
  64
  65     apr_size_t hit_count;
  66
  67     char *text;
  68     char *pattern;
  69 };
  70
  71 struct acmp_btree_node_t {
  72     acmp_utf8_char_t letter;
  73     acmp_btree_node_t *left;
  74     acmp_btree_node_t *right;
  75     acmp_node_t *node;
  76 };
  77
  78 /**
  79  * Data related to parser, not to individual nodes
  80  */
  81 struct ACMP {
  82     #ifdef ACMP_USE_UTF8
  83     int is_utf8;
  84     #endif
  85     int is_case_sensitive;
  86     apr_pool_t *parent_pool;
  87     apr_pool_t *pool;
  88
  89     int dict_count;
  90     apr_size_t longest_entry;
  91
  92     acmp_node_t *root_node;
  93
  94     const char *data_start;
  95     const char *data_end;
  96     const char *data_pos;
  97     apr_size_t data_len;
  98
  99     apr_size_t *bp_buffer;
 100     apr_size_t bp_buff_len;
 101
 102     acmp_node_t *active_node;
 103     char u8_buff[6];
 104     apr_size_t  u8buff_len;
 105     apr_size_t  hit_count;
 106     int  is_failtree_done;
 107     int  is_active;
 108     apr_size_t  byte_pos;
 109     apr_size_t  char_pos;
 110 };
 111
 112 /*
 113  *******************************************************************************
 114  *******************************************************************************
 115  * Functions for UTF-8 support
 116  */
 117
 118 #ifdef ACMP_USE_UTF8
 119 /**
 120  * Returns length of utf-8 sequence based on its first byte
 121  */
 122 static int utf8_seq_len(const char *first_byte) {
 123     return utf8_seq_lengths[(unsigned int)(unsigned char)first_byte[0]];
 124 }
 125
 126 /**
 127  * Returns length of utf8-encoded text
 128  */
 129 static size_t utf8_strlen(const char *str) {
 130     int len = 0;
 131     const char *c = str;
 132     while (*c != 0) {
 133         c += utf8_seq_len(c);
 134         len++;
 135     }
 136     return len;
 137 }
 138
 139 /**
 140  * Returns ucs code for given utf-8 sequence
 141  */
 142 static acmp_utf8_char_t utf8_decodechar(const char *str) {
 143     int len = utf8_seq_len(str);
 144     acmp_utf8_char_t ch = 0;
 145     switch (len) {
 146         case 6: ch += (unsigned char)*str++; ch <<= 6;
 147         case 5: ch += (unsigned char)*str++; ch <<= 6;
 148         case 4: ch += (unsigned char)*str++; ch <<= 6;
 149         case 3: ch += (unsigned char)*str++; ch <<= 6;
 150         case 2: ch += (unsigned char)*str++; ch <<= 6;
 151         case 1: ch += (unsigned char)*str++;
 152     }
 153     ch -= utf8_offsets[len - 1];
 154     return ch;
 155 }
 156
 157 /**
 158  * Returns lowercase for given unicode character. Searches through
 159  *   utf8_lcase_map table, if it doesn't find the code assumes
 160  *   it doesn't have a lowercase variant and returns code itself.
 161  */
 162 static long utf8_lcase(acmp_utf8_char_t ucs_code) {
 163     long mid, left, right;
 164     left = 1;
 165     right = UTF8_LCASEMAP_LEN * 2 + 1;
 166
 167     while (left <= right) {
 168         mid = (left + right) >> 1;
 169         mid -= (mid % 2); mid++;
 170         if (ucs_code > utf8_lcase_map[mid])
 171             left = mid + 2;
 172         else if (ucs_code < utf8_lcase_map[mid])
 173             right = mid - 2;
 174         else if (ucs_code == utf8_lcase_map[mid])
 175             return utf8_lcase_map[mid - 1];
 176     }
 177     return ucs_code;
 178 }
 179 #endif
 180
 181 /*
 182  *******************************************************************************
 183  *******************************************************************************
 184  * Code for local / static utility functions
 185  */
 186
 187 /**
 188  * Returns length of given string for parser's encoding
 189  */
 190 static size_t acmp_strlen(ACMP *parser, const char *str) {
 191     #ifdef ACMP_USE_UTF8
 192     return (parser->is_utf8 == 0) ? strlen(str) : utf8_strlen(str);
 193     #else
 194     return strlen(str);
 195     #endif
 196 }
 197
 198 /**
 199  * Turns string to array of ucs values, depending on parser's encoding
 200  *       str - string to convert, doesn't have to be NULL-terminated
 201  * ucs_chars - where to write ucs values
 202  *       len - length of input string
 203  */
 204 static void acmp_strtoucs(ACMP *parser, const char *str, acmp_utf8_char_t *ucs_chars, int len) {
 205     int i;
 206     const char *c = str;
 207
 208     #ifdef ACMP_USE_UTF8
 209     if (parser->is_utf8) {
 210         for (i = 0; i < len; i++) {
 211             *(ucs_chars++) = utf8_decodechar(c);
 212             c += utf8_seq_len(c);
 213         }
 214     } else
 215     #endif
 216     {
 217         for (i = 0; i < len; i++) {
 218             *(ucs_chars++) = *(c++);
 219         }
 220     }
 221 }
 222
 223 /**
 224  * Returns node with given letter, or null if not found
 225  */
 226 static acmp_node_t *acmp_child_for_code(acmp_node_t *parent_node, acmp_utf8_char_t ucs_code) {
 227     acmp_node_t *node = parent_node->child;
 228     if (node == NULL) return NULL;
 229     for (;;) {
 230         if (node->letter == ucs_code) return node;
 231         node = node->sibling;
 232         if (node == NULL) return NULL;
 233     }
 234 }
 235
 236 /**
 237  * Adds node to parent node, if it is not already there
 238  */
 239 static void acmp_add_node_to_parent(acmp_node_t *parent, acmp_node_t *child) {
 240     acmp_node_t *node = NULL;
 241
 242     child->parent = parent;
 243     if (parent->child == NULL) {
 244         parent->child = child;
 245         return;
 246     }
 247
 248     node = parent->child;
 249     for (;;) {
 250         if (node == child) return;
 251         if (node->sibling == NULL) {
 252             node->sibling = child;
 253             return;
 254         }
 255         node = node->sibling;
 256     }
 257 }
 258
 259 /**
 260  * Copies values from one node to another, without child/sibling/fail pointers
 261  * and without state variables.
 262  */
 263 static void acmp_clone_node_no_state(acmp_node_t *from, acmp_node_t *to) {
 264     memcpy(to, from, sizeof(acmp_node_t));
 265     to->child = NULL;
 266     to->sibling = NULL;
 267     to->fail = NULL;
 268     to->hit_count = 0;
 269 }
 270
 271 /**
 272  * Copies sibling nodes and child node for from given "from" node to "to" node.
 273  *   Both nodes must already exist.
 274  */
 275 static void acmp_copy_nodes_recursive(acmp_node_t *from, acmp_node_t *to, apr_pool_t *pool) {
 276     acmp_node_t *old_node = from->child, *new_node, *nn2;
 277     if (old_node == NULL) return;
 278     nn2 = apr_pcalloc(pool, sizeof(acmp_node_t));
 279     /* ENH: Check alloc succeded */
 280     acmp_clone_node_no_state(old_node, nn2);
 281     nn2->parent = to;
 282     to->child = nn2;
 283     acmp_copy_nodes_recursive(from->child, to->child, pool);
 284
 285     for (;;) {
 286         old_node = old_node->sibling;
 287         if (old_node == NULL) break;
 288         new_node = apr_pcalloc(pool, sizeof(acmp_node_t));
 289         /* ENH: Check alloc succeded */
 290         acmp_clone_node_no_state(old_node, new_node);
 291         new_node->parent = to;
 292         nn2->sibling = new_node;
 293         nn2 = new_node;
 294         acmp_copy_nodes_recursive(old_node, new_node, pool);
 295     }
 296 }
 297
 298 static inline acmp_node_t *acmp_btree_find(acmp_node_t *node, acmp_utf8_char_t letter) {
 299     acmp_btree_node_t *bnode = node->btree;
 300     for (;;) {
 301         if (bnode == NULL) return NULL;
 302         if (bnode->letter == letter) return bnode->node;
 303         if (bnode->letter > letter) {
 304             bnode = bnode->left;
 305         } else {
 306             bnode = bnode->right;
 307         }
 308     }
 309 }
 310
 311 /**
 312  *
 313  */
 314 static inline acmp_node_t *acmp_goto(acmp_node_t *node, acmp_utf8_char_t letter) {
 315     return acmp_btree_find(node, letter);
 316 }
 317
 318 /**
 319  * Connects each node with its first fail node that is end of a phrase.
 320  */
 321 static void acmp_connect_other_matches(ACMP *parser, acmp_node_t *node) {
 322     acmp_node_t *child, *om;
 323
 324     for (child = node->child; child != NULL; child = child->sibling) {
 325         if (child->fail == NULL) continue;
 326         for (om = child->fail; om != parser->root_node; om = om->fail) {
 327             if (om->is_last) {
 328                 child->o_match = om;
 329                 break;
 330             }
 331         }
 332     }
 333
 334     /* Go recursively through children of this node that have a child node */
 335     for(child = node->child; child != NULL; child = child->sibling) {
 336         if (child->child != NULL) acmp_connect_other_matches(parser, child);
 337     }
 338 }
 339
 340 /**
 341  * Adds leaves to binary tree, working from sorted array of keyword tree nodes
 342  */
 343 static void acmp_add_btree_leaves(acmp_btree_node_t *node, acmp_node_t *nodes[],
 344     int pos, int lb, int rb, apr_pool_t *pool) {
 345
 346     int left = 0, right = 0;
 347     if ((pos - lb) > 1) {
 348         left = lb + (pos - lb) / 2;
 349         node->left = apr_pcalloc(pool, sizeof(acmp_btree_node_t));
 350         /* ENH: Check alloc succeded */
 351         node->left->node = nodes[left];
 352         node->left->letter = nodes[left]->letter;
 353         #ifdef DEBUG_ACMP
 354         fprintf(stderr, "%lc ->left %lc\n", (wint_t)node->node->letter, (wint_t)node->left->node->letter);
 355         #endif
 356     }
 357     if ((rb - pos) > 1) {
 358         right = pos + (rb - pos) / 2;
 359         node->right = apr_pcalloc(pool, sizeof(acmp_btree_node_t));
 360         /* ENH: Check alloc succeded */
 361         node->right->node = nodes[right];
 362         node->right->letter = nodes[right]->letter;
 363         #ifdef DEBUG_ACMP
 364         fprintf(stderr, "%lc ->right %lc\n", (wint_t)node->node->letter, (wint_t)node->right->node->letter);
 365         #endif
 366     }
 367     if (node->right != NULL) {
 368         acmp_add_btree_leaves(node->right, nodes, right, pos, rb, pool);
 369     }
 370     if (node->left != NULL) {
 371         acmp_add_btree_leaves(node->left, nodes, left, lb, pos, pool);
 372     }
 373 }
 374
 375 /**
 376  * Builds balanced binary tree from children nodes of given node.
 377  */
 378 static void acmp_build_binary_tree(ACMP *parser, acmp_node_t *node) {
 379     apr_size_t count, i, j;
 380     acmp_node_t *child = node->child;
 381     acmp_node_t **nodes;
 382     apr_size_t pos;
 383
 384     /* Build an array big enough */
 385     for (count = 0; child != NULL; child = child->sibling) count++;
 386     nodes = apr_pcalloc(parser->pool, count * sizeof(acmp_node_t *));
 387     /* ENH: Check alloc succeded */
 388
 389     /* ENH: Combine this in the loop below - we do not need two loops */
 390     child = node->child;
 391     for (i = 0; i < count; i++) {
 392         nodes[i] = child;
 393         child = child->sibling;
 394     };
 395
 396     /* We have array with all children of the node and number of those children
 397      */
 398     for (i = 0; i < count - 1; i++)
 399         for (j = i + 1; j < count; j++) {
 400             acmp_node_t *tmp;
 401
 402             if (nodes[i]->letter < nodes[j]->letter) continue;
 403
 404             tmp = nodes[i];
 405             nodes[i] = nodes[j];
 406             nodes[j] = tmp;
 407         }
 408     node->btree = apr_pcalloc(parser->pool, sizeof(acmp_btree_node_t));
 409     /* ENH: Check alloc succeded */
 410     pos = count / 2;
 411     node->btree->node = nodes[pos];
 412     node->btree->letter = nodes[pos]->letter;
 413     acmp_add_btree_leaves(node->btree, nodes, pos, -1, count, parser->pool);
 414     for (i = 0; i < count; i++) {
 415         if (nodes[i]->child != NULL) acmp_build_binary_tree(parser, nodes[i]);
 416     }
 417 }
 418
 419 /**
 420  * Constructs fail paths on keyword trie
 421  */
 422 static apr_status_t acmp_connect_fail_branches(ACMP *parser) {
 423     /* Already connected ? */
 424     acmp_node_t *child, *node, *goto_node;
 425     apr_array_header_t *arr, *arr2, *tmp;
 426
 427     if (parser->is_failtree_done != 0) return APR_SUCCESS;
 428
 429     parser->root_node->text = "";
 430     arr  = apr_array_make(parser->pool, 32, sizeof(acmp_node_t *));
 431     arr2 = apr_array_make(parser->pool, 32, sizeof(acmp_node_t *));
 432
 433     parser->root_node->fail = parser->root_node;
 434
 435     /* All first-level children will fail back to root node */
 436     for (child = parser->root_node->child; child != NULL; child = child->sibling) {
 437         child->fail = parser->root_node;
 438         *(acmp_node_t **)apr_array_push(arr) = child;
 439         #ifdef DEBUG_ACMP
 440         fprintf(stderr, "fail direction: *%s* => *%s*\n", child->text, child->fail->text);
 441         #endif
 442     }
 443
 444     for (;;) {
 445         while (apr_is_empty_array(arr) == 0) {
 446             node = *(acmp_node_t **)apr_array_pop(arr);
 447             node->fail = parser->root_node;
 448             if (node->parent != parser->root_node) {
 449                 goto_node = acmp_child_for_code(node->parent->fail, node->letter);
 450                 node->fail = (goto_node != NULL) ? goto_node : parser->root_node;
 451             }
 452             #ifdef DEBUG_ACMP
 453             fprintf(stderr, "fail direction: *%s* => *%s*\n", node->text, node->fail->text);
 454             #endif
 455             child = node->child;
 456             while (child != NULL) {
 457                 *(acmp_node_t **)apr_array_push(arr2) = child;
 458                 child = child->sibling;
 459             }
 460         }
 461         if (apr_is_empty_array(arr2) != 0) break;
 462
 463         tmp = arr;
 464         arr = arr2;
 465         arr2 = tmp;
 466     }
 467     acmp_connect_other_matches(parser, parser->root_node);
 468     if (parser->root_node->child != NULL) acmp_build_binary_tree(parser, parser->root_node);
 469     parser->is_failtree_done = 1;
 470     return APR_SUCCESS;
 471 }
 472
 473 /**
 474  * Clears hit count of each node, called from acmp_reset()
 475  */
 476 static void acmp_clear_hit_count_recursive(acmp_node_t *node) {
 477     for (; node != NULL; node = node->sibling) {
 478         node->hit_count = 0;
 479         if (node->child != NULL) acmp_clear_hit_count_recursive(node->child);
 480     }
 481 }
 482
 483 /**
 484  * Called when a match is found
 485  */
 486 static void acmp_found(ACMP *parser, acmp_node_t *node) {
 487     if (node->callback) {
 488         node->callback(parser, node->callback_data,
 489             parser->bp_buffer[(parser->char_pos - node->depth - 1) % parser->bp_buff_len],
 490             parser->char_pos - node->depth - 1);
 491     }
 492     node->hit_count++;
 493     parser->hit_count++;
 494 }
 495
 496 /*
 497  *******************************************************************************
 498  *******************************************************************************
 499  * Code for functions from header file
 500  */
 501
 502
 503 /**
 504  * flags - OR-ed values of ACMP_FLAG constants
 505  * pool  - apr_pool to use as parent pool, can be set to NULL
 506  */
 507 ACMP *acmp_create(int flags, apr_pool_t *pool) {
 508     apr_status_t rc;
 509     apr_pool_t *p;
 510     ACMP *parser;
 511
 512     rc = apr_pool_create(&p, pool);
 513     if (rc != APR_SUCCESS) return NULL;
 514
 515     parser = apr_pcalloc(p, sizeof(ACMP));
 516     /* ENH: Check alloc succeded */
 517     parser->pool = p;
 518     parser->parent_pool = pool;
 519     #ifdef ACMP_USE_UTF8
 520     parser->is_utf8 = (flags & ACMP_FLAG_UTF8) == 0 ? 0 : 1;
 521     #endif
 522     parser->is_case_sensitive = (flags & ACMP_FLAG_CASE_SENSITIVE) == 0 ? 0 : 1;
 523     parser->root_node = apr_pcalloc(p, sizeof(acmp_node_t));
 524     /* ENH: Check alloc succeded */
 525     return parser;
 526 }
 527
 528 /**
 529  * Destroys previously created parser
 530  */
 531 void acmp_destroy(ACMP *parser) {
 532     /*
 533      * All data is kept in parser's pool (including parser struct itself), so
 534      * destroying the pool will destroy everything
 535      */
 536     apr_pool_destroy(parser->pool);
 537 }
 538
 539 /**
 540  * Creates parser with same options and same patterns
 541  * parser - ACMP parser to duplicate
 542  * pool - parent pool to use, if left as NULL original parser's parent pool is used
 543  */
 544 ACMP *acmp_duplicate(ACMP *parser, apr_pool_t *pool) {
 545     apr_status_t rc;
 546     apr_pool_t *p;
 547     ACMP *new_parser;
 548
 549     if (pool == NULL) pool = parser->parent_pool;
 550     rc = apr_pool_create(&p, pool);
 551     if (rc != APR_SUCCESS) return NULL;
 552
 553     new_parser = apr_pcalloc(p, sizeof(ACMP));
 554     /* ENH: Check alloc succeded */
 555     new_parser->pool = p;
 556     new_parser->parent_pool = pool;
 557     #ifdef ACMP_USE_UTF8
 558     new_parser->is_utf8 = parser->is_utf8;
 559     #endif
 560     new_parser->is_case_sensitive = parser->is_case_sensitive;
 561     new_parser->root_node = apr_pcalloc(p, sizeof(acmp_node_t));
 562     /* ENH: Check alloc succeded */
 563     new_parser->dict_count = parser->dict_count;
 564     new_parser->longest_entry = parser->longest_entry;
 565     acmp_copy_nodes_recursive(parser->root_node, new_parser->root_node, new_parser->pool);
 566     acmp_prepare(new_parser);
 567     return new_parser;
 568 }
 569
 570 /**
 571  * Creates fail tree and initializes buffer
 572  */
 573 apr_status_t acmp_prepare(ACMP *parser) {
 574     apr_status_t st;
 575
 576     if (parser->bp_buff_len < parser->longest_entry) {
 577         parser->bp_buff_len = parser->longest_entry * 2;
 578         parser->bp_buffer = apr_pcalloc(parser->pool, sizeof(apr_size_t) * parser->bp_buff_len);
 579         /* ENH: Check alloc succeded */
 580     }
 581
 582     st = acmp_connect_fail_branches(parser);
 583     parser->active_node = parser->root_node;
 584     if (st != APR_SUCCESS) return st;
 585     parser->is_active = 1;
 586     return APR_SUCCESS;
 587 }
 588
 589 /**
 590  * Adds pattern to parser
 591  * parser - ACMP parser
 592  * pattern - string with pattern to match
 593  * callback - Optional, pointer to an acmp_callback_t function
 594  * data - pointer to data that will be passed to callback function, only used if callback
 595  *   is supplied
 596  * len - Length of pattern in characters, if zero string length is used.
 597  */
 598 apr_status_t acmp_add_pattern(ACMP *parser, const char *pattern,
 599     acmp_callback_t callback, void *data, apr_size_t len)
 600 {
 601     size_t length, i, j;
 602     acmp_utf8_char_t *ucs_chars;
 603     acmp_node_t *parent, *child;
 604
 605     if (parser->is_active != 0) return APR_EGENERAL;
 606
 607     length = (len == 0) ? acmp_strlen(parser, pattern) : len;
 608     ucs_chars = apr_pcalloc(parser->pool, length * sizeof(acmp_utf8_char_t));
 609     /* ENH: Check alloc succeded */
 610
 611     parent = parser->root_node;
 612     acmp_strtoucs(parser, pattern, ucs_chars, length);
 613
 614     for (i = 0; i < length; i++) {
 615         acmp_utf8_char_t letter = ucs_chars[i];
 616         if (parser->is_case_sensitive == 0) {
 617             letter = utf8_lcase(letter);
 618         }
 619         child = acmp_child_for_code(parent, letter);
 620         if (child == NULL) {
 621             child = apr_pcalloc(parser->pool, sizeof(acmp_node_t));
 622             /* ENH: Check alloc succeded */
 623             child->pattern = "";
 624             child->letter = letter;
 625             child->depth = i;
 626             child->text = apr_pcalloc(parser->pool, strlen(pattern) + 2);
 627             /* ENH: Check alloc succeded */
 628             for (j = 0; j <= i; j++) child->text[j] = pattern[j];
 629         }
 630         if (i == length - 1) {
 631             if (child->is_last == 0) {
 632                 parser->dict_count++;
 633                 child->is_last = 1;
 634                 child->pattern = apr_pcalloc(parser->pool, strlen(pattern) + 2);
 635                 /* ENH: Check alloc succeded */
 636                 strcpy(child->pattern, pattern);
 637             }
 638             child->callback = callback;
 639             child->callback_data = data;
 640         }
 641         acmp_add_node_to_parent(parent, child);
 642         parent = child;
 643     }
 644     if (length > parser->longest_entry) parser->longest_entry = length;
 645     parser->is_failtree_done = 0;
 646
 647     return APR_SUCCESS;
 648 }
 649
 650 /**
 651  * Called to process incoming data stream
 652  * data - ptr to incoming data
 653  * len - size of data in bytes
 654  */
 655 apr_status_t acmp_process(ACMP *parser, const char *data, apr_size_t len) {
 656     acmp_node_t *node, *go_to;
 657     #ifdef ACMP_USE_UTF8
 658     apr_size_t seq_length;
 659     #endif
 660     const char *end;
 661
 662     if (parser->is_failtree_done == 0) acmp_prepare(parser);
 663
 664     node = parser->active_node;
 665     end = data + len;
 666
 667     while (data < end) {
 668         acmp_utf8_char_t letter;
 669
 670         parser->bp_buffer[parser->char_pos % parser->bp_buff_len] = parser->byte_pos;
 671         #ifdef ACMP_USE_UTF8
 672         if (parser->is_utf8) {
 673             if (parser->u8buff_len > 0) {
 674                 /* Resuming partial utf-8 sequence */
 675                 seq_length = utf8_seq_len(parser->u8_buff);
 676                 for (;;) {
 677                     parser->u8_buff[parser->u8buff_len++] = *data++;
 678                     if (parser->u8buff_len == seq_length) {
 679                         parser->u8buff_len = 0;
 680                         letter = utf8_decodechar(parser->u8_buff);
 681                         parser->byte_pos += seq_length;
 682                         parser->char_pos++;
 683                         break;
 684                     }
 685                 }
 686             } else {
 687                 /* not resuming partial sequence, reading from the stream */
 688                 seq_length = utf8_seq_len(data);
 689                 if ((data + seq_length) > end) {
 690                     while (data < end) parser->u8_buff[parser->u8buff_len++] = *data++;
 691                     return APR_SUCCESS;
 692                 } else {
 693                     letter = utf8_decodechar(data);
 694                     data += seq_length;
 695                     parser->byte_pos += seq_length;
 696                     parser->char_pos++;
 697                 }
 698             }
 699         } else
 700         #endif
 701         {
 702             letter = *data++;
 703             parser->byte_pos++;
 704             parser->char_pos++;
 705         }
 706         if (parser->is_case_sensitive == 0) letter = utf8_lcase(letter);
 707
 708         go_to = NULL;
 709         while (go_to == NULL) {
 710             acmp_node_t *n2 = acmp_goto(node, letter);
 711             go_to = acmp_child_for_code(node, letter);
 712             if (n2 != go_to) {
 713                 n2 = acmp_goto(node, letter);
 714             };
 715             if (go_to != NULL) {
 716                 if (go_to->is_last) {
 717                     acmp_found(parser, go_to);
 718                 }
 719             }
 720             if (node == parser->root_node) break;
 721             if (go_to == NULL) node = node->fail;
 722         }
 723         if (go_to != NULL) node = go_to;
 724
 725         /* We need to collect other nodes that are last letters of phrase. These
 726          *   will be fail node of current node if it has is_last flag set, and
 727          *   fail node of that node, recursively down to root node.
 728          */
 729         go_to = node;
 730         if (go_to != parser->root_node) {
 731             for (go_to = go_to->o_match; go_to != NULL; go_to = go_to->o_match) {
 732                 acmp_found(parser, go_to);
 733             }
 734         }
 735     }
 736     parser->active_node = node;
 737     return parser->hit_count > 0 ? 1 : 0;
 738 }
 739
 740 /**
 741  * Resets the state of parser so you can start using it with new set of data.
 742  *
 743  * No need to clear buffer since it will be re-initialized at first run of
 744  * acmp_process
 745  */
 746 void acmp_reset(ACMP *parser) {
 747     parser->is_active = 0;
 748     parser->byte_pos = 0;
 749     parser->char_pos = 0;
 750     parser->hit_count = 0;
 751     parser->u8buff_len = 0;
 752     acmp_clear_hit_count_recursive(parser->root_node);
 753 }
 754
 755 /**
 756  * Creates an ACMPT struct that will use parser's tree, without duplicating its data
 757  */
 758 ACMPT *acmp_duplicate_quick(ACMP *parser, apr_pool_t *pool) {
 759     apr_pool_t *p = (pool != NULL) ? pool : parser->pool;
 760     ACMPT *dup = apr_pcalloc(p, sizeof(ACMPT));
 761     /* ENH: Check alloc succeded */
 762     dup->parser = parser;
 763     return dup;
 764 }
 765
 766 /**
 767  * Process the data using ACMPT to keep state, and ACMPT's parser to keep the tree
 768  */
 769 apr_status_t acmp_process_quick(ACMPT *acmpt, const char **match, const char *data, apr_size_t len) {
 770     ACMP *parser;
 771     acmp_node_t *node, *go_to;
 772     const char *end;
 773
 774     if (acmpt->parser->is_failtree_done == 0) {
 775         acmp_prepare(acmpt->parser);
 776     };
 777
 778     parser = acmpt->parser;
 779     if (acmpt->ptr == NULL) acmpt->ptr = parser->root_node;
 780     node = acmpt->ptr;
 781     end = data + len;
 782
 783     while (data < end) {
 784         acmp_utf8_char_t letter = (unsigned char)*data++;
 785
 786         if (parser->is_case_sensitive == 0) letter = utf8_lcase(letter);
 787
 788         go_to = NULL;
 789         while (go_to == NULL) {
 790             go_to = acmp_goto(node, letter);
 791             if (go_to != NULL) {
 792                 if (go_to->is_last) {
 793                     *match = go_to->text;
 794                     return 1;
 795                 }
 796             }
 797             if (node == parser->root_node) break;
 798             if (go_to == NULL) node = node->fail;
 799         }
 800         if (go_to != NULL) node = go_to;
 801
 802         /* If node has o_match, then we found a pattern */
 803         if (node->o_match != NULL) {
 804             *match = node->text;
 805             return 1;
 806         }
 807     }
 808     acmpt->ptr = node;
 809     return 0;
 810 }