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 */
match_no_op(const apr_strmatch_pattern * this_pattern,const char * s,apr_size_t slen)28 static 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
match_boyer_moore_horspool(const apr_strmatch_pattern * this_pattern,const char * s,apr_size_t slen)34 static 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
match_boyer_moore_horspool_nocase(const apr_strmatch_pattern * this_pattern,const char * s,apr_size_t slen)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 {
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
apr_strmatch_precompile(apr_pool_t * p,const char * s,int case_sensitive)82 APU_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