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