1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "apr_strmatch.h"
18#include "apr_lib.h"
19#define APR_WANT_STRFUNC
20#include "apr_want.h"
21
22
23#define NUM_CHARS  256
24
25/*
26 * String searching functions
27 */
28static const char *match_no_op(const apr_strmatch_pattern *this_pattern,
29                               const char *s, apr_size_t slen)
30{
31    return s;
32}
33
34static const char *match_boyer_moore_horspool(
35                               const apr_strmatch_pattern *this_pattern,
36                               const char *s, apr_size_t slen)
37{
38    const char *s_end = s + slen;
39    apr_size_t *shift = (apr_size_t *)(this_pattern->context);
40    const char *s_next = s + this_pattern->length - 1;
41    const char *p_start = this_pattern->pattern;
42    const char *p_end = p_start + this_pattern->length - 1;
43    while (s_next < s_end) {
44        const char *s_tmp = s_next;
45        const char *p_tmp = p_end;
46        while (*s_tmp == *p_tmp) {
47            p_tmp--;
48            if (p_tmp < p_start) {
49                return s_tmp;
50            }
51            s_tmp--;
52        }
53        s_next += shift[(int)*((const unsigned char *)s_next)];
54    }
55    return NULL;
56}
57
58static const char *match_boyer_moore_horspool_nocase(
59                               const apr_strmatch_pattern *this_pattern,
60                               const char *s, apr_size_t slen)
61{
62    const char *s_end = s + slen;
63    apr_size_t *shift = (apr_size_t *)(this_pattern->context);
64    const char *s_next = s + this_pattern->length - 1;
65    const char *p_start = this_pattern->pattern;
66    const char *p_end = p_start + this_pattern->length - 1;
67    while (s_next < s_end) {
68        const char *s_tmp = s_next;
69        const char *p_tmp = p_end;
70        while (apr_tolower(*s_tmp) == apr_tolower(*p_tmp)) {
71            p_tmp--;
72            if (p_tmp < p_start) {
73                return s_tmp;
74            }
75            s_tmp--;
76        }
77        s_next += shift[(unsigned char)apr_tolower(*s_next)];
78    }
79    return NULL;
80}
81
82APU_DECLARE(const apr_strmatch_pattern *) apr_strmatch_precompile(
83                                              apr_pool_t *p, const char *s,
84                                              int case_sensitive)
85{
86    apr_strmatch_pattern *pattern;
87    apr_size_t i;
88    apr_size_t *shift;
89
90    pattern = apr_palloc(p, sizeof(*pattern));
91    pattern->pattern = s;
92    pattern->length = strlen(s);
93    if (pattern->length == 0) {
94        pattern->compare = match_no_op;
95        pattern->context = NULL;
96        return pattern;
97    }
98
99    shift = (apr_size_t *)apr_palloc(p, sizeof(apr_size_t) * NUM_CHARS);
100    for (i = 0; i < NUM_CHARS; i++) {
101        shift[i] = pattern->length;
102    }
103    if (case_sensitive) {
104        pattern->compare = match_boyer_moore_horspool;
105        for (i = 0; i < pattern->length - 1; i++) {
106            shift[(unsigned char)s[i]] = pattern->length - i - 1;
107        }
108    }
109    else {
110        pattern->compare = match_boyer_moore_horspool_nocase;
111        for (i = 0; i < pattern->length - 1; i++) {
112            shift[(unsigned char)apr_tolower(s[i])] = pattern->length - i - 1;
113        }
114    }
115    pattern->context = shift;
116
117    return pattern;
118}
119