Ported "grep" from NetBSD to toolbox.
Bug: 6798417
Change-Id: I581c496a726a4814edaaa3672849c090bac8552c
diff --git a/toolbox/grep/fastgrep.c b/toolbox/grep/fastgrep.c
new file mode 100644
index 0000000..2fcd864
--- /dev/null
+++ b/toolbox/grep/fastgrep.c
@@ -0,0 +1,336 @@
+/* $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;
+ }
+}