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.3 2011/02/17 22:03:25 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 92 /* Remove end-of-line character ('$'). */ 93 if (fg->len > 0 && pat[fg->len - 1] == '$') { 94 fg->eol = true; 95 fg->len--; 96 } 97 98 /* Remove beginning-of-line character ('^'). */ 99 if (pat[0] == '^') { 100 fg->bol = true; 101 fg->len--; 102 pat++; 103 } 104 105 if (fg->len >= 14 && 106 memcmp(pat, "[[:<:]]", 7) == 0 && 107 memcmp(pat + fg->len - 7, "[[:>:]]", 7) == 0) { 108 fg->len -= 14; 109 pat += 7; 110 /* Word boundary is handled separately in util.c */ 111 wflag = true; 112 } 113 114 /* 115 * pat has been adjusted earlier to not include '^', '$' or 116 * the word match character classes at the beginning and ending 117 * of the string respectively. 118 */ 119 fg->pattern = grep_malloc(fg->len + 1); 120 memcpy(fg->pattern, pat, fg->len); 121 fg->pattern[fg->len] = '\0'; 122 123 /* Look for ways to cheat...er...avoid the full regex engine. */ 124 for (i = 0; i < fg->len; i++) { 125 /* Can still cheat? */ 126 if (fg->pattern[i] == '.') { 127 hasDot = i; 128 if (i < fg->len / 2) { 129 if (firstHalfDot < 0) 130 /* Closest dot to the beginning */ 131 firstHalfDot = i; 132 } else { 133 /* Closest dot to the end of the pattern. */ 134 lastHalfDot = i; 135 if (firstLastHalfDot < 0) 136 firstLastHalfDot = i; 137 } 138 } else { 139 /* Free memory and let others know this is empty. */ 140 free(fg->pattern); 141 fg->pattern = NULL; 142 return (-1); 143 } 144 } 145 146 /* 147 * Determine if a reverse search would be faster based on the placement 148 * of the dots. 149 */ 150 if ((!(lflag || cflag)) && ((!(fg->bol || fg->eol)) && 151 ((lastHalfDot) && ((firstHalfDot < 0) || 152 ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) && 153 !oflag && !color) { 154 fg->reversed = true; 155 hasDot = fg->len - (firstHalfDot < 0 ? 156 firstLastHalfDot : firstHalfDot) - 1; 157 grep_revstr(fg->pattern, fg->len); 158 } 159 160 /* 161 * Normal Quick Search would require a shift based on the position the 162 * next character after the comparison is within the pattern. With 163 * wildcards, the position of the last dot effects the maximum shift 164 * distance. 165 * The closer to the end the wild card is the slower the search. A 166 * reverse version of this algorithm would be useful for wildcards near 167 * the end of the string. 168 * 169 * Examples: 170 * Pattern Max shift 171 * ------- --------- 172 * this 5 173 * .his 4 174 * t.is 3 175 * th.s 2 176 * thi. 1 177 */ 178 179 /* Adjust the shift based on location of the last dot ('.'). */ 180 shiftPatternLen = fg->len - hasDot; 181 182 /* Preprocess pattern. */ 183 for (i = 0; i <= (signed)UCHAR_MAX; i++) 184 fg->qsBc[i] = shiftPatternLen; 185 for (i = hasDot + 1; i < fg->len; i++) { 186 fg->qsBc[fg->pattern[i]] = fg->len - i; 187 } 188 189 /* 190 * Put pattern back to normal after pre-processing to allow for easy 191 * comparisons later. 192 */ 193 if (fg->reversed) 194 grep_revstr(fg->pattern, fg->len); 195 196 return (0); 197 } 198 199 int 200 grep_search(fastgrep_t *fg, const unsigned char *data, size_t len, regmatch_t *pmatch) 201 { 202 unsigned int j; 203 int ret = REG_NOMATCH; 204 205 if (pmatch->rm_so == (ssize_t)len) 206 return (ret); 207 208 if (fg->bol && pmatch->rm_so != 0) { 209 pmatch->rm_so = len; 210 pmatch->rm_eo = len; 211 return (ret); 212 } 213 214 /* No point in going farther if we do not have enough data. */ 215 if (len < fg->len) 216 return (ret); 217 218 /* Only try once at the beginning or ending of the line. */ 219 if (fg->bol || fg->eol) { 220 /* Simple text comparison. */ 221 /* Verify data is >= pattern length before searching on it. */ 222 if (len >= fg->len) { 223 /* Determine where in data to start search at. */ 224 j = fg->eol ? len - fg->len : 0; 225 if (!((fg->bol && fg->eol) && (len != fg->len))) 226 if (grep_cmp(fg->pattern, data + j, 227 fg->len) == -1) { 228 pmatch->rm_so = j; 229 pmatch->rm_eo = j + fg->len; 230 ret = 0; 231 } 232 } 233 } else if (fg->reversed) { 234 /* Quick Search algorithm. */ 235 j = len; 236 do { 237 if (grep_cmp(fg->pattern, data + j - fg->len, 238 fg->len) == -1) { 239 pmatch->rm_so = j - fg->len; 240 pmatch->rm_eo = j; 241 ret = 0; 242 break; 243 } 244 /* Shift if within bounds, otherwise, we are done. */ 245 if (j == fg->len) 246 break; 247 j -= fg->qsBc[data[j - fg->len - 1]]; 248 } while (j >= fg->len); 249 } else { 250 /* Quick Search algorithm. */ 251 j = pmatch->rm_so; 252 do { 253 if (grep_cmp(fg->pattern, data + j, fg->len) == -1) { 254 pmatch->rm_so = j; 255 pmatch->rm_eo = j + fg->len; 256 ret = 0; 257 break; 258 } 259 260 /* Shift if within bounds, otherwise, we are done. */ 261 if (j + fg->len == len) 262 break; 263 else 264 j += fg->qsBc[data[j + fg->len]]; 265 } while (j <= (len - fg->len)); 266 } 267 268 return (ret); 269 } 270 271 /* 272 * Returns: i >= 0 on failure (position that it failed) 273 * -1 on success 274 */ 275 static inline int 276 grep_cmp(const unsigned char *pat, const unsigned char *data, size_t len) 277 { 278 size_t size; 279 wchar_t *wdata, *wpat; 280 unsigned int i; 281 282 if (iflag) { 283 if ((size = mbstowcs(NULL, (const char *)data, 0)) == 284 ((size_t) - 1)) 285 return (-1); 286 287 wdata = grep_malloc(size * sizeof(wint_t)); 288 289 if (mbstowcs(wdata, (const char *)data, size) == 290 ((size_t) - 1)) 291 return (-1); 292 293 if ((size = mbstowcs(NULL, (const char *)pat, 0)) == 294 ((size_t) - 1)) 295 return (-1); 296 297 wpat = grep_malloc(size * sizeof(wint_t)); 298 299 if (mbstowcs(wpat, (const char *)pat, size) == ((size_t) - 1)) 300 return (-1); 301 for (i = 0; i < len; i++) { 302 if ((towlower(wpat[i]) == towlower(wdata[i])) || 303 ((grepbehave != GREP_FIXED) && wpat[i] == L'.')) 304 continue; 305 free(wpat); 306 free(wdata); 307 return (i); 308 } 309 } else { 310 for (i = 0; i < len; i++) { 311 if ((pat[i] == data[i]) || ((grepbehave != GREP_FIXED) && 312 pat[i] == '.')) 313 continue; 314 return (i); 315 } 316 } 317 return (-1); 318 } 319 320 static inline void 321 grep_revstr(unsigned char *str, int len) 322 { 323 int i; 324 char c; 325 326 for (i = 0; i < len / 2; i++) { 327 c = str[i]; 328 str[i] = str[len - i - 1]; 329 str[len - i - 1] = c; 330 } 331 } 332