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