1 /* $OpenBSD: util.c,v 1.36 2007/10/02 17:59:18 otto Exp $ */ 2 /* $FreeBSD: head/usr.bin/grep/fastgrep.c 211496 2010-08-19 09:28:59Z des $ */ 3 4 /*- 5 * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav 6 * Copyright (C) 2008 Gabor Kovesdan <gabor@FreeBSD.org> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31 /* 32 * XXX: This file is a speed up for grep to cover the defects of the 33 * regex library. These optimizations should practically be implemented 34 * there keeping this code clean. This is a future TODO, but for the 35 * meantime, we need to use this workaround. 36 */ 37 38 #include <sys/cdefs.h> 39 __RCSID("$NetBSD: fastgrep.c,v 1.4 2011/02/27 17:33:37 joerg Exp $"); 40 41 #include <limits.h> 42 #include <stdbool.h> 43 #include <stdlib.h> 44 #include <string.h> 45 #include <wchar.h> 46 #include <wctype.h> 47 48 #include "grep.h" 49 50 static inline int grep_cmp(const unsigned char *, const unsigned char *, size_t); 51 static inline void grep_revstr(unsigned char *, int); 52 53 void 54 fgrepcomp(fastgrep_t *fg, const char *pat) 55 { 56 unsigned int i; 57 58 /* Initialize. */ 59 fg->len = strlen(pat); 60 fg->bol = false; 61 fg->eol = false; 62 fg->reversed = false; 63 64 fg->pattern = (unsigned char *)grep_strdup(pat); 65 66 /* Preprocess pattern. */ 67 for (i = 0; i <= UCHAR_MAX; i++) 68 fg->qsBc[i] = fg->len; 69 for (i = 1; i < fg->len; i++) 70 fg->qsBc[fg->pattern[i]] = fg->len - i; 71 } 72 73 /* 74 * Returns: -1 on failure, 0 on success 75 */ 76 int 77 fastcomp(fastgrep_t *fg, const char *pat) 78 { 79 unsigned int i; 80 int firstHalfDot = -1; 81 int firstLastHalfDot = -1; 82 int hasDot = 0; 83 int lastHalfDot = 0; 84 int shiftPatternLen; 85 86 /* Initialize. */ 87 fg->len = strlen(pat); 88 fg->bol = false; 89 fg->eol = false; 90 fg->reversed = false; 91 fg->word = wflag; 92 93 /* Remove end-of-line character ('$'). */ 94 if (fg->len > 0 && pat[fg->len - 1] == '$') { 95 fg->eol = true; 96 fg->len--; 97 } 98 99 /* Remove beginning-of-line character ('^'). */ 100 if (pat[0] == '^') { 101 fg->bol = true; 102 fg->len--; 103 pat++; 104 } 105 106 if (fg->len >= 14 && 107 memcmp(pat, "[[:<:]]", 7) == 0 && 108 memcmp(pat + fg->len - 7, "[[:>:]]", 7) == 0) { 109 fg->len -= 14; 110 pat += 7; 111 /* Word boundary is handled separately in util.c */ 112 fg->word = true; 113 } 114 115 /* 116 * pat has been adjusted earlier to not include '^', '$' or 117 * the word match character classes at the beginning and ending 118 * of the string respectively. 119 */ 120 fg->pattern = grep_malloc(fg->len + 1); 121 memcpy(fg->pattern, pat, fg->len); 122 fg->pattern[fg->len] = '\0'; 123 124 /* Look for ways to cheat...er...avoid the full regex engine. */ 125 for (i = 0; i < fg->len; i++) { 126 /* Can still cheat? */ 127 if (fg->pattern[i] == '.') { 128 hasDot = i; 129 if (i < fg->len / 2) { 130 if (firstHalfDot < 0) 131 /* Closest dot to the beginning */ 132 firstHalfDot = i; 133 } else { 134 /* Closest dot to the end of the pattern. */ 135 lastHalfDot = i; 136 if (firstLastHalfDot < 0) 137 firstLastHalfDot = i; 138 } 139 } else { 140 /* Free memory and let others know this is empty. */ 141 free(fg->pattern); 142 fg->pattern = NULL; 143 return (-1); 144 } 145 } 146 147 /* 148 * Determine if a reverse search would be faster based on the placement 149 * of the dots. 150 */ 151 if ((!(lflag || cflag)) && ((!(fg->bol || fg->eol)) && 152 ((lastHalfDot) && ((firstHalfDot < 0) || 153 ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) && 154 !oflag && !color) { 155 fg->reversed = true; 156 hasDot = fg->len - (firstHalfDot < 0 ? 157 firstLastHalfDot : firstHalfDot) - 1; 158 grep_revstr(fg->pattern, fg->len); 159 } 160 161 /* 162 * Normal Quick Search would require a shift based on the position the 163 * next character after the comparison is within the pattern. With 164 * wildcards, the position of the last dot effects the maximum shift 165 * distance. 166 * The closer to the end the wild card is the slower the search. A 167 * reverse version of this algorithm would be useful for wildcards near 168 * the end of the string. 169 * 170 * Examples: 171 * Pattern Max shift 172 * ------- --------- 173 * this 5 174 * .his 4 175 * t.is 3 176 * th.s 2 177 * thi. 1 178 */ 179 180 /* Adjust the shift based on location of the last dot ('.'). */ 181 shiftPatternLen = fg->len - hasDot; 182 183 /* Preprocess pattern. */ 184 for (i = 0; i <= (signed)UCHAR_MAX; i++) 185 fg->qsBc[i] = shiftPatternLen; 186 for (i = hasDot + 1; i < fg->len; i++) { 187 fg->qsBc[fg->pattern[i]] = fg->len - i; 188 } 189 190 /* 191 * Put pattern back to normal after pre-processing to allow for easy 192 * comparisons later. 193 */ 194 if (fg->reversed) 195 grep_revstr(fg->pattern, fg->len); 196 197 return (0); 198 } 199 200 int 201 grep_search(fastgrep_t *fg, const unsigned char *data, size_t len, regmatch_t *pmatch) 202 { 203 unsigned int j; 204 int ret = REG_NOMATCH; 205 206 if (pmatch->rm_so == (ssize_t)len) 207 return (ret); 208 209 if (fg->bol && pmatch->rm_so != 0) { 210 pmatch->rm_so = len; 211 pmatch->rm_eo = len; 212 return (ret); 213 } 214 215 /* No point in going farther if we do not have enough data. */ 216 if (len < fg->len) 217 return (ret); 218 219 /* Only try once at the beginning or ending of the line. */ 220 if (fg->bol || fg->eol) { 221 /* Simple text comparison. */ 222 /* Verify data is >= pattern length before searching on it. */ 223 if (len >= fg->len) { 224 /* Determine where in data to start search at. */ 225 j = fg->eol ? len - fg->len : 0; 226 if (!((fg->bol && fg->eol) && (len != fg->len))) 227 if (grep_cmp(fg->pattern, data + j, 228 fg->len) == -1) { 229 pmatch->rm_so = j; 230 pmatch->rm_eo = j + fg->len; 231 ret = 0; 232 } 233 } 234 } else if (fg->reversed) { 235 /* Quick Search algorithm. */ 236 j = len; 237 do { 238 if (grep_cmp(fg->pattern, data + j - fg->len, 239 fg->len) == -1) { 240 pmatch->rm_so = j - fg->len; 241 pmatch->rm_eo = j; 242 ret = 0; 243 break; 244 } 245 /* Shift if within bounds, otherwise, we are done. */ 246 if (j == fg->len) 247 break; 248 j -= fg->qsBc[data[j - fg->len - 1]]; 249 } while (j >= fg->len); 250 } else { 251 /* Quick Search algorithm. */ 252 j = pmatch->rm_so; 253 do { 254 if (grep_cmp(fg->pattern, data + j, fg->len) == -1) { 255 pmatch->rm_so = j; 256 pmatch->rm_eo = j + fg->len; 257 ret = 0; 258 break; 259 } 260 261 /* Shift if within bounds, otherwise, we are done. */ 262 if (j + fg->len == len) 263 break; 264 else 265 j += fg->qsBc[data[j + fg->len]]; 266 } while (j <= (len - fg->len)); 267 } 268 269 return (ret); 270 } 271 272 /* 273 * Returns: i >= 0 on failure (position that it failed) 274 * -1 on success 275 */ 276 static inline int 277 grep_cmp(const unsigned char *pat, const unsigned char *data, size_t len) 278 { 279 size_t size; 280 wchar_t *wdata, *wpat; 281 unsigned int i; 282 283 if (iflag) { 284 if ((size = mbstowcs(NULL, (const char *)data, 0)) == 285 ((size_t) - 1)) 286 return (-1); 287 288 wdata = grep_malloc(size * sizeof(wint_t)); 289 290 if (mbstowcs(wdata, (const char *)data, size) == 291 ((size_t) - 1)) 292 return (-1); 293 294 if ((size = mbstowcs(NULL, (const char *)pat, 0)) == 295 ((size_t) - 1)) 296 return (-1); 297 298 wpat = grep_malloc(size * sizeof(wint_t)); 299 300 if (mbstowcs(wpat, (const char *)pat, size) == ((size_t) - 1)) 301 return (-1); 302 for (i = 0; i < len; i++) { 303 if ((towlower(wpat[i]) == towlower(wdata[i])) || 304 ((grepbehave != GREP_FIXED) && wpat[i] == L'.')) 305 continue; 306 free(wpat); 307 free(wdata); 308 return (i); 309 } 310 } else { 311 for (i = 0; i < len; i++) { 312 if ((pat[i] == data[i]) || ((grepbehave != GREP_FIXED) && 313 pat[i] == '.')) 314 continue; 315 return (i); 316 } 317 } 318 return (-1); 319 } 320 321 static inline void 322 grep_revstr(unsigned char *str, int len) 323 { 324 int i; 325 char c; 326 327 for (i = 0; i < len / 2; i++) { 328 c = str[i]; 329 str[i] = str[len - i - 1]; 330 str[len - i - 1] = c; 331 } 332 } 333