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