toolbox/grep/fastgrep.c - android_system_core - Gitiles

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