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