Coverage Report

Created: 2023-03-26 06:28

/src/httpd/srclib/apr/strmatch/apr_strmatch.c
Line
Count
Source (jump to first uncovered line)
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
224k
#define NUM_CHARS  256
24
25
/*
26
 * String searching functions
27
 */
28
static const char *match_no_op(const apr_strmatch_pattern *this_pattern,
29
                               const char *s, apr_size_t slen)
30
0
{
31
0
    return s;
32
0
}
33
34
static const char *match_boyer_moore_horspool(
35
                               const apr_strmatch_pattern *this_pattern,
36
                               const char *s, apr_size_t slen)
37
453
{
38
453
    const char *s_end = s + slen;
39
453
    apr_size_t *shift = (apr_size_t *)(this_pattern->context);
40
453
    const char *s_next = s + this_pattern->length - 1;
41
453
    const char *p_start = this_pattern->pattern;
42
453
    const char *p_end = p_start + this_pattern->length - 1;
43
2.59k
    while (s_next < s_end) {
44
2.30k
        const char *s_tmp = s_next;
45
2.30k
        const char *p_tmp = p_end;
46
5.68k
        while (*s_tmp == *p_tmp) {
47
3.54k
            p_tmp--;
48
3.54k
            if (p_tmp < p_start) {
49
170
                return s_tmp;
50
170
            }
51
3.37k
            s_tmp--;
52
3.37k
        }
53
2.13k
        s_next += shift[(int)*((const unsigned char *)s_next)];
54
2.13k
    }
55
283
    return NULL;
56
453
}
57
58
static const char *match_boyer_moore_horspool_nocase(
59
                               const apr_strmatch_pattern *this_pattern,
60
                               const char *s, apr_size_t slen)
61
0
{
62
0
    const char *s_end = s + slen;
63
0
    apr_size_t *shift = (apr_size_t *)(this_pattern->context);
64
0
    const char *s_next = s + this_pattern->length - 1;
65
0
    const char *p_start = this_pattern->pattern;
66
0
    const char *p_end = p_start + this_pattern->length - 1;
67
0
    while (s_next < s_end) {
68
0
        const char *s_tmp = s_next;
69
0
        const char *p_tmp = p_end;
70
0
        while (apr_tolower(*s_tmp) == apr_tolower(*p_tmp)) {
71
0
            p_tmp--;
72
0
            if (p_tmp < p_start) {
73
0
                return s_tmp;
74
0
            }
75
0
            s_tmp--;
76
0
        }
77
0
        s_next += shift[(unsigned char)apr_tolower(*s_next)];
78
0
    }
79
0
    return NULL;
80
0
}
81
82
APR_DECLARE(const apr_strmatch_pattern *) apr_strmatch_precompile(
83
                                              apr_pool_t *p, const char *s,
84
                                              int case_sensitive)
85
874
{
86
874
    apr_strmatch_pattern *pattern;
87
874
    apr_size_t i;
88
874
    apr_size_t *shift;
89
90
874
    pattern = apr_palloc(p, sizeof(*pattern));
91
874
    pattern->pattern = s;
92
874
    pattern->length = strlen(s);
93
874
    if (pattern->length == 0) {
94
0
        pattern->compare = match_no_op;
95
0
        pattern->context = NULL;
96
0
        return pattern;
97
0
    }
98
99
874
    shift = (apr_size_t *)apr_palloc(p, sizeof(apr_size_t) * NUM_CHARS);
100
224k
    for (i = 0; i < NUM_CHARS; i++) {
101
223k
        shift[i] = pattern->length;
102
223k
    }
103
874
    if (case_sensitive) {
104
874
        pattern->compare = match_boyer_moore_horspool;
105
8.28k
        for (i = 0; i < pattern->length - 1; i++) {
106
7.41k
            shift[(unsigned char)s[i]] = pattern->length - i - 1;
107
7.41k
        }
108
874
    }
109
0
    else {
110
0
        pattern->compare = match_boyer_moore_horspool_nocase;
111
0
        for (i = 0; i < pattern->length - 1; i++) {
112
0
            shift[(unsigned char)apr_tolower(s[i])] = pattern->length - i - 1;
113
0
        }
114
0
    }
115
874
    pattern->context = shift;
116
117
874
    return pattern;
118
874
}