123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336 |
- /* $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;
- }
- }
|