| /* $OpenBSD: util.c,v 1.36 2007/10/02 17:59:18 otto Exp $ */ | |
| /* $FreeBSD: head/usr.bin/grep/fastgrep.c 211496 2010-08-19 09:28:59Z des $ */ | |
| /*- | |
| * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav | |
| * Copyright (C) 2008 Gabor Kovesdan <gabor@FreeBSD.org> | |
| * All rights reserved. | |
| * | |
| * Redistribution and use in source and binary forms, with or without | |
| * modification, are permitted provided that the following conditions | |
| * are met: | |
| * 1. Redistributions of source code must retain the above copyright | |
| * notice, this list of conditions and the following disclaimer. | |
| * 2. Redistributions in binary form must reproduce the above copyright | |
| * notice, this list of conditions and the following disclaimer in the | |
| * documentation and/or other materials provided with the distribution. | |
| * | |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | |
| * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |
| * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
| * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
| * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
| * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
| * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
| * SUCH DAMAGE. | |
| */ | |
| /* | |
| * XXX: This file is a speed up for grep to cover the defects of the | |
| * regex library. These optimizations should practically be implemented | |
| * there keeping this code clean. This is a future TODO, but for the | |
| * meantime, we need to use this workaround. | |
| */ | |
| #if HAVE_NBTOOL_CONFIG_H | |
| #include "nbtool_config.h" | |
| #endif | |
| #include <sys/cdefs.h> | |
| __RCSID("$NetBSD: fastgrep.c,v 1.5 2011/04/18 03:27:40 joerg Exp $"); | |
| #include <limits.h> | |
| #include <stdbool.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| #include <wchar.h> | |
| #include <wctype.h> | |
| #include "grep.h" | |
| static inline int grep_cmp(const unsigned char *, const unsigned char *, size_t); | |
| static inline void grep_revstr(unsigned char *, int); | |
| void | |
| fgrepcomp(fastgrep_t *fg, const char *pat) | |
| { | |
| unsigned int i; | |
| /* Initialize. */ | |
| fg->len = strlen(pat); | |
| fg->bol = false; | |
| fg->eol = false; | |
| fg->reversed = false; | |
| fg->pattern = (unsigned char *)grep_strdup(pat); | |
| /* Preprocess pattern. */ | |
| for (i = 0; i <= UCHAR_MAX; i++) | |
| fg->qsBc[i] = fg->len; | |
| for (i = 1; i < fg->len; i++) | |
| fg->qsBc[fg->pattern[i]] = fg->len - i; | |
| } | |
| /* | |
| * Returns: -1 on failure, 0 on success | |
| */ | |
| int | |
| fastcomp(fastgrep_t *fg, const char *pat) | |
| { | |
| unsigned int i; | |
| int firstHalfDot = -1; | |
| int firstLastHalfDot = -1; | |
| int hasDot = 0; | |
| int lastHalfDot = 0; | |
| int shiftPatternLen; | |
| /* Initialize. */ | |
| fg->len = strlen(pat); | |
| fg->bol = false; | |
| fg->eol = false; | |
| fg->reversed = false; | |
| fg->word = wflag; | |
| /* Remove end-of-line character ('$'). */ | |
| if (fg->len > 0 && pat[fg->len - 1] == '$') { | |
| fg->eol = true; | |
| fg->len--; | |
| } | |
| /* Remove beginning-of-line character ('^'). */ | |
| if (pat[0] == '^') { | |
| fg->bol = true; | |
| fg->len--; | |
| pat++; | |
| } | |
| if (fg->len >= 14 && | |
| memcmp(pat, "[[:<:]]", 7) == 0 && | |
| memcmp(pat + fg->len - 7, "[[:>:]]", 7) == 0) { | |
| fg->len -= 14; | |
| pat += 7; | |
| /* Word boundary is handled separately in util.c */ | |
| fg->word = true; | |
| } | |
| /* | |
| * pat has been adjusted earlier to not include '^', '$' or | |
| * the word match character classes at the beginning and ending | |
| * of the string respectively. | |
| */ | |
| fg->pattern = grep_malloc(fg->len + 1); | |
| memcpy(fg->pattern, pat, fg->len); | |
| fg->pattern[fg->len] = '\0'; | |
| /* Look for ways to cheat...er...avoid the full regex engine. */ | |
| for (i = 0; i < fg->len; i++) { | |
| /* Can still cheat? */ | |
| if (fg->pattern[i] == '.') { | |
| hasDot = i; | |
| if (i < fg->len / 2) { | |
| if (firstHalfDot < 0) | |
| /* Closest dot to the beginning */ | |
| firstHalfDot = i; | |
| } else { | |
| /* Closest dot to the end of the pattern. */ | |
| lastHalfDot = i; | |
| if (firstLastHalfDot < 0) | |
| firstLastHalfDot = i; | |
| } | |
| } else { | |
| /* Free memory and let others know this is empty. */ | |
| free(fg->pattern); | |
| fg->pattern = NULL; | |
| return (-1); | |
| } | |
| } | |
| /* | |
| * Determine if a reverse search would be faster based on the placement | |
| * of the dots. | |
| */ | |
| if ((!(lflag || cflag)) && ((!(fg->bol || fg->eol)) && | |
| ((lastHalfDot) && ((firstHalfDot < 0) || | |
| ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) && | |
| !oflag && !color) { | |
| fg->reversed = true; | |
| hasDot = fg->len - (firstHalfDot < 0 ? | |
| firstLastHalfDot : firstHalfDot) - 1; | |
| grep_revstr(fg->pattern, fg->len); | |
| } | |
| /* | |
| * Normal Quick Search would require a shift based on the position the | |
| * next character after the comparison is within the pattern. With | |
| * wildcards, the position of the last dot effects the maximum shift | |
| * distance. | |
| * The closer to the end the wild card is the slower the search. A | |
| * reverse version of this algorithm would be useful for wildcards near | |
| * the end of the string. | |
| * | |
| * Examples: | |
| * Pattern Max shift | |
| * ------- --------- | |
| * this 5 | |
| * .his 4 | |
| * t.is 3 | |
| * th.s 2 | |
| * thi. 1 | |
| */ | |
| /* Adjust the shift based on location of the last dot ('.'). */ | |
| shiftPatternLen = fg->len - hasDot; | |
| /* Preprocess pattern. */ | |
| for (i = 0; i <= (signed)UCHAR_MAX; i++) | |
| fg->qsBc[i] = shiftPatternLen; | |
| for (i = hasDot + 1; i < fg->len; i++) { | |
| fg->qsBc[fg->pattern[i]] = fg->len - i; | |
| } | |
| /* | |
| * Put pattern back to normal after pre-processing to allow for easy | |
| * comparisons later. | |
| */ | |
| if (fg->reversed) | |
| grep_revstr(fg->pattern, fg->len); | |
| return (0); | |
| } | |
| int | |
| grep_search(fastgrep_t *fg, const unsigned char *data, size_t len, regmatch_t *pmatch) | |
| { | |
| unsigned int j; | |
| int ret = REG_NOMATCH; | |
| if (pmatch->rm_so == (ssize_t)len) | |
| return (ret); | |
| if (fg->bol && pmatch->rm_so != 0) { | |
| pmatch->rm_so = len; | |
| pmatch->rm_eo = len; | |
| return (ret); | |
| } | |
| /* No point in going farther if we do not have enough data. */ | |
| if (len < fg->len) | |
| return (ret); | |
| /* Only try once at the beginning or ending of the line. */ | |
| if (fg->bol || fg->eol) { | |
| /* Simple text comparison. */ | |
| /* Verify data is >= pattern length before searching on it. */ | |
| if (len >= fg->len) { | |
| /* Determine where in data to start search at. */ | |
| j = fg->eol ? len - fg->len : 0; | |
| if (!((fg->bol && fg->eol) && (len != fg->len))) | |
| if (grep_cmp(fg->pattern, data + j, | |
| fg->len) == -1) { | |
| pmatch->rm_so = j; | |
| pmatch->rm_eo = j + fg->len; | |
| ret = 0; | |
| } | |
| } | |
| } else if (fg->reversed) { | |
| /* Quick Search algorithm. */ | |
| j = len; | |
| do { | |
| if (grep_cmp(fg->pattern, data + j - fg->len, | |
| fg->len) == -1) { | |
| pmatch->rm_so = j - fg->len; | |
| pmatch->rm_eo = j; | |
| ret = 0; | |
| break; | |
| } | |
| /* Shift if within bounds, otherwise, we are done. */ | |
| if (j == fg->len) | |
| break; | |
| j -= fg->qsBc[data[j - fg->len - 1]]; | |
| } while (j >= fg->len); | |
| } else { | |
| /* Quick Search algorithm. */ | |
| j = pmatch->rm_so; | |
| do { | |
| if (grep_cmp(fg->pattern, data + j, fg->len) == -1) { | |
| pmatch->rm_so = j; | |
| pmatch->rm_eo = j + fg->len; | |
| ret = 0; | |
| break; | |
| } | |
| /* Shift if within bounds, otherwise, we are done. */ | |
| if (j + fg->len == len) | |
| break; | |
| else | |
| j += fg->qsBc[data[j + fg->len]]; | |
| } while (j <= (len - fg->len)); | |
| } | |
| return (ret); | |
| } | |
| /* | |
| * Returns: i >= 0 on failure (position that it failed) | |
| * -1 on success | |
| */ | |
| static inline int | |
| grep_cmp(const unsigned char *pat, const unsigned char *data, size_t len) | |
| { | |
| size_t size; | |
| wchar_t *wdata, *wpat; | |
| unsigned int i; | |
| if (iflag) { | |
| if ((size = mbstowcs(NULL, (const char *)data, 0)) == | |
| ((size_t) - 1)) | |
| return (-1); | |
| wdata = grep_malloc(size * sizeof(wint_t)); | |
| if (mbstowcs(wdata, (const char *)data, size) == | |
| ((size_t) - 1)) | |
| return (-1); | |
| if ((size = mbstowcs(NULL, (const char *)pat, 0)) == | |
| ((size_t) - 1)) | |
| return (-1); | |
| wpat = grep_malloc(size * sizeof(wint_t)); | |
| if (mbstowcs(wpat, (const char *)pat, size) == ((size_t) - 1)) | |
| return (-1); | |
| for (i = 0; i < len; i++) { | |
| if ((towlower(wpat[i]) == towlower(wdata[i])) || | |
| ((grepbehave != GREP_FIXED) && wpat[i] == L'.')) | |
| continue; | |
| free(wpat); | |
| free(wdata); | |
| return (i); | |
| } | |
| } else { | |
| for (i = 0; i < len; i++) { | |
| if ((pat[i] == data[i]) || ((grepbehave != GREP_FIXED) && | |
| pat[i] == '.')) | |
| continue; | |
| return (i); | |
| } | |
| } | |
| return (-1); | |
| } | |
| static inline void | |
| grep_revstr(unsigned char *str, int len) | |
| { | |
| int i; | |
| char c; | |
| for (i = 0; i < len / 2; i++) { | |
| c = str[i]; | |
| str[i] = str[len - i - 1]; | |
| str[len - i - 1] = c; | |
| } | |
| } |