1251876Speter/* Licensed to the Apache Software Foundation (ASF) under one or more 2251876Speter * contributor license agreements. See the NOTICE file distributed with 3251876Speter * this work for additional information regarding copyright ownership. 4251876Speter * The ASF licenses this file to You under the Apache License, Version 2.0 5251876Speter * (the "License"); you may not use this file except in compliance with 6251876Speter * the License. You may obtain a copy of the License at 7251876Speter * 8251876Speter * http://www.apache.org/licenses/LICENSE-2.0 9251876Speter * 10251876Speter * Unless required by applicable law or agreed to in writing, software 11251876Speter * distributed under the License is distributed on an "AS IS" BASIS, 12251876Speter * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13251876Speter * See the License for the specific language governing permissions and 14251876Speter * limitations under the License. 15251876Speter */ 16251876Speter 17251876Speter#include "apr_strmatch.h" 18251876Speter#include "apr_lib.h" 19251876Speter#define APR_WANT_STRFUNC 20251876Speter#include "apr_want.h" 21251876Speter 22251876Speter 23251876Speter#define NUM_CHARS 256 24251876Speter 25251876Speter/* 26251876Speter * String searching functions 27251876Speter */ 28251876Speterstatic const char *match_no_op(const apr_strmatch_pattern *this_pattern, 29251876Speter const char *s, apr_size_t slen) 30251876Speter{ 31251876Speter return s; 32251876Speter} 33251876Speter 34251876Speterstatic const char *match_boyer_moore_horspool( 35251876Speter const apr_strmatch_pattern *this_pattern, 36251876Speter const char *s, apr_size_t slen) 37251876Speter{ 38251876Speter const char *s_end = s + slen; 39251876Speter apr_size_t *shift = (apr_size_t *)(this_pattern->context); 40251876Speter const char *s_next = s + this_pattern->length - 1; 41251876Speter const char *p_start = this_pattern->pattern; 42251876Speter const char *p_end = p_start + this_pattern->length - 1; 43251876Speter while (s_next < s_end) { 44251876Speter const char *s_tmp = s_next; 45251876Speter const char *p_tmp = p_end; 46251876Speter while (*s_tmp == *p_tmp) { 47251876Speter p_tmp--; 48251876Speter if (p_tmp < p_start) { 49251876Speter return s_tmp; 50251876Speter } 51251876Speter s_tmp--; 52251876Speter } 53251876Speter s_next += shift[(int)*((const unsigned char *)s_next)]; 54251876Speter } 55251876Speter return NULL; 56251876Speter} 57251876Speter 58251876Speterstatic const char *match_boyer_moore_horspool_nocase( 59251876Speter const apr_strmatch_pattern *this_pattern, 60251876Speter const char *s, apr_size_t slen) 61251876Speter{ 62251876Speter const char *s_end = s + slen; 63251876Speter apr_size_t *shift = (apr_size_t *)(this_pattern->context); 64251876Speter const char *s_next = s + this_pattern->length - 1; 65251876Speter const char *p_start = this_pattern->pattern; 66251876Speter const char *p_end = p_start + this_pattern->length - 1; 67251876Speter while (s_next < s_end) { 68251876Speter const char *s_tmp = s_next; 69251876Speter const char *p_tmp = p_end; 70251876Speter while (apr_tolower(*s_tmp) == apr_tolower(*p_tmp)) { 71251876Speter p_tmp--; 72251876Speter if (p_tmp < p_start) { 73251876Speter return s_tmp; 74251876Speter } 75251876Speter s_tmp--; 76251876Speter } 77251876Speter s_next += shift[(unsigned char)apr_tolower(*s_next)]; 78251876Speter } 79251876Speter return NULL; 80251876Speter} 81251876Speter 82251876SpeterAPU_DECLARE(const apr_strmatch_pattern *) apr_strmatch_precompile( 83251876Speter apr_pool_t *p, const char *s, 84251876Speter int case_sensitive) 85251876Speter{ 86251876Speter apr_strmatch_pattern *pattern; 87251876Speter apr_size_t i; 88251876Speter apr_size_t *shift; 89251876Speter 90251876Speter pattern = apr_palloc(p, sizeof(*pattern)); 91251876Speter pattern->pattern = s; 92251876Speter pattern->length = strlen(s); 93251876Speter if (pattern->length == 0) { 94251876Speter pattern->compare = match_no_op; 95251876Speter pattern->context = NULL; 96251876Speter return pattern; 97251876Speter } 98251876Speter 99251876Speter shift = (apr_size_t *)apr_palloc(p, sizeof(apr_size_t) * NUM_CHARS); 100251876Speter for (i = 0; i < NUM_CHARS; i++) { 101251876Speter shift[i] = pattern->length; 102251876Speter } 103251876Speter if (case_sensitive) { 104251876Speter pattern->compare = match_boyer_moore_horspool; 105251876Speter for (i = 0; i < pattern->length - 1; i++) { 106251876Speter shift[(unsigned char)s[i]] = pattern->length - i - 1; 107251876Speter } 108251876Speter } 109251876Speter else { 110251876Speter pattern->compare = match_boyer_moore_horspool_nocase; 111251876Speter for (i = 0; i < pattern->length - 1; i++) { 112251876Speter shift[(unsigned char)apr_tolower(s[i])] = pattern->length - i - 1; 113251876Speter } 114251876Speter } 115251876Speter pattern->context = shift; 116251876Speter 117251876Speter return pattern; 118251876Speter} 119