bmgsubs

Subject: bmgsubs - Boyer-Moore-Gosper fast string search subroutines
Newsgroups: mod.sources
Approved: jpn@panda.UUCP

Mod.sources:  Volume 5, Issue 14
Submitted by: Jeff Mogul <talcott!su-navajo.arpa:mogul>

: Run this shell script with "sh" not "csh"
PATH=:/bin:/usr/bin:/usr/ucb
export PATH
all=FALSE
if [ $1x = -ax ]; then
	all=TRUE
fi
/bin/echo 'Extracting README'
sed 's/^X//' <<'//go.sysin dd *' >README
Here are routines to perform fast string searches using the
Boyer-Moore-Gosper algorithm; they can be used in any Unix program (and
should be portable to non-Unix systems).  You can search either a file
or a buffer in memory.

The code is mostly due to James A. Woods (jaw@ames-aurora.arpa)
although I have modified it heavily, so all bugs are my fault.  The
original code is from his sped-up version of egrep, recently posted on
mod.sources and available via anonymous FTP from ames-aurora.arpa as
pub/egrep.one and pub/egrep.two.  That code handles regular
expressions; mine does not.

The files included here are
    README		This file
    Makefile		Can be modified for 4.xBSD or Sys V compilation
    bmgsubs.3l		Manual page
    bmgsubs.c		The search code
    bmgtest.c		Test program (example of file searching)
    bmgtest2.c		Another test program, showing buffer searching

These have only been tested on 4.2BSD Vax systems.

-Jeff Mogul
mogul@navajo.stanford.edu
decwrl!glacier!navajo!mogul
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	/bin/chmod 664 README
	/bin/echo -n '	'; /bin/ls -ld README
fi
/bin/echo 'Extracting Makefile'
sed 's/^X//' <<'//go.sysin dd *' >Makefile
# Makefile for bmgsubs (Boyer-Moore-Gosper subroutines)
#

#
# Define BSD if you're compiling this for a 4.xBSD system
#	(BSD has bcopy, has index() instead of strchr().)
#
ENV = -DBSD

CFLAGS = -O

bmgsubs.o: bmgsubs.c

bmgtest: bmgsubs.o bmgtest.o
	cc -o bmgtest bmgsubs.o bmgtest.o

bmgtest2: bmgsubs.o bmgtest2.o
	cc -o bmgtest2 bmgsubs.o bmgtest2.o

clean:
	rm -f bmgtest bmgtest2 *.o *.BAK *.CKP
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	/bin/chmod 664 Makefile
	/bin/echo -n '	'; /bin/ls -ld Makefile
fi
/bin/echo 'Extracting bmgsubs.3l'
sed 's/^X//' <<'//go.sysin dd *' >bmgsubs.3l
X.TH BMGSUBS 3L "16 May 1986"
X.SH NAME
(bmgsubs) bmg_setup, bmg_search, bmg_fsearch \- Boyer-Moore-Gosper string search routines
X.SH SYNOPSIS
bmg_setup(search_string, case_fold_flag)
X.br
char *search_string;
X.br
int case_fold_flag;
X.sp
bmg_fsearch(file_des, action_func)
X.br
int file_des;
X.br
int (*action_func)();
X.sp
bmg_search(buffer_base, buffer_length, action_func)
X.br
char *buffer_base;
X.br
int buffer_length;
X.br
int (*action_func)();
X.SH DESCRIPTION
These routines perform fast searches for strings, using the
Boyer-Moore-Gosper algorithm.  No meta-characters
(such as `*' or `.')
are interpreted, and the search string cannot contain newlines.
X.PP
X.I Bmg_setup
must be called as the first step in performing a search.  The
X.I search_string
parameter is the string to be searched for.
X.I Case_fold_flag
should be false (zero) if characters should match exactly, and
true (non-zero) if case should be ignored when checking for
matches.
X.PP
Once a search string has been specified using
X.IR bmg_setup ,
one or more searches for that string may be performed.
X.PP
X.I Bmg_fsearch
searches a file, open for reading on file descriptor
X.I file_des
(this is
X.I not
a
X.I stdio
file.)
For each line that contains the search string,
X.I bmg_fsearch
will call the
X.I action_func
function specified by the caller as
action_func(matching_line, byte_offset).
The
X.I matching_line
parameter is a (char *) pointer to a temporary copy of the line;
X.I byte_offset
is the offset from the beginning of the file to the first occurence
of the search string in that line.
X.I Action_func
should return true (non-zero) if the search should continue, or
false (zero) if the search should terminate at this point.
X.PP
X.I Bmg_search
is like
X.IR bmg_fsearch ,
except that instead of searching a file, it searches the buffer
pointed to by
X.IR buffer_base ;
X.I buffer_length
specifies the number of bytes in the buffer.
The
X.I byte_offset
parameter to
X.I action_func
gives the offset from the beginning of the buffer.
X.PP
If the user merely wants the matching lines printed on the
standard output, the
X.I action_func
parameter
to
X.I bmg_fsearch
or
X.I bmg_search
can be NULL.
X.SH AUTHOR
Jeffrey Mogul (Stanford University), based on code written
by James A. Woods (NASA Ames)
X.SH BUGS
Might be nice to have a version of this that handles regular expressions.
X.PP
There are large, but finite, limits on the length of both pattern
strings and text lines.  When these limits are exceeded, all bets are off.
X.PP
The string pointer passed to
X.I action_func
points to a temporary copy of the matching line, and must be
copied elsewhere before
X.I action_func
returns.
X.PP
X.I Bmg_search
does not
X.I permanently
modify the buffer in any way, but during its execution (and therefore
when
X.I action_func
is called), the last byte of the buffer may be temporarily changed.
X.PP
The Boyer-Moore algorithm cannot find lines that do not contain
a given pattern (like "grep -v") or count lines ("grep -n").
Although it is fast even for short search strings, it gets faster as
the search string length increases.
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	/bin/chmod 664 bmgsubs.3l
	/bin/echo -n '	'; /bin/ls -ld bmgsubs.3l
fi
/bin/echo 'Extracting bmgsubs.c'
sed 's/^X//' <<'//go.sysin dd *' >bmgsubs.c
X/*
 * bmgsubs.c
 *
 * Subroutines for fast string searching; no regular expressions
 *
 * Entries:
 *
 * bmg_setup(pattern_string, case_fold_flag)
 * char *pattern_string;	-- the string you are searching for
 * int case_fold_flag;		-- true if you want search to ignore case
 *
 * bmg_fsearch(file_des, action_func)
 * int file_des;		-- file descriptor to read on
 * int (*action_func)();	-- called on each hit
 *
 * bmg_search(buffer, buflen, action_func)
 * char *buffer;		-- buffer to search
 * int buflen;			-- bytes in buffer
 * int (*action_func)();	-- called on each hit
 *
 * Usage:
 *	Start by calling bmg_setup() to specify a pattern.  Then open
 * the file you want to search and pass the file descriptor (NOT a
 * stdio file pointer) to bmg_fsearch().  For each line that contains
 * the pattern, bmg_fsearch() will call action_func(string, position)
 * with string being a static copy of the matching line and position
 * being the disntance in bytes from the beginning of the search to the
 * matching substring.
 *	action_func() should return a non-zero integer unless the
 * search should be terminated, in which case it should return 0.
 *	bmg_search() works the same as bmg_fsearch(), but searches
 * a buffer rather than a file.
 *
 * Adapted from:
 *
     Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
     original paper (CACM, October, 1977).  No delta1 or delta2.  According to
     experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
     practical value.  However, to improve for worst case input, integrating
     the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
     February 1986) deserves consideration.

     James A. Woods					Copyright (c) 1986
     NASA Ames Research Center
 *
 * 29 April 1986	Jeff Mogul	Stanford
 *	Adapted as a set of subroutines for use by a program. No
 *	regular-expression support.
 */

#include <stdio.h>
#include <ctype.h>
#include <sys/types.h>

#ifdef	BSD
#define	strchr	index
#endif
#ifndef	BUFSIZE
#define BUFSIZE	8192
#endif	BUFSIZE
#ifndef	PATSIZE
#define PATSIZE 1000
#endif	PATSIZE
#define LARGE 	BUFSIZE + PATSIZE
#define NL	'\n'
#define	EOS	'\0'

struct bmg_data {
	int     bmg_delta0[256];		/* ascii only */
	char    bmg_cmap[256];		/* (un)folded characters */
	char    bmg_str[BUFSIZE + 2];
	char    bmg_linetemp[BUFSIZE];
	char	bmg_pattern[PATSIZE];
	int	bmg_patlen;
	int	bmg_nsuccess;
} bmdata;
#define delta0	bmdata.bmg_delta0
#define cmap	bmdata.bmg_cmap
#define str	bmdata.bmg_str
#define linetemp	bmdata.bmg_linetemp
#define	pattern	bmdata.bmg_pattern
#define	patlen	bmdata.bmg_patlen
#define	nsuccess	bmdata.bmg_nsuccess

char   *strcpy(), *strncpy(), *malloc();

bmg_search(buffer, buflen, action)
char	*buffer;
int	buflen;
int	(*action)();
{
	register char  *k,
	               *strend,
	               *s;
	register int    j;
	char   *t;
	char   *strbegin;
	char   *gotamatch();
	int     byte_offset = 0;
	char	last_byte = buffer[buflen - 1];

	nsuccess = 0;

	/* make sure that buffer ends with NL */
	if (last_byte != NL)
	    buffer[buflen - 1] = NL;

	/*
	 * We must process the buffer in chunks of BUFSIZE to make
	 * "LARGE" hack work right.
	 */
	for (strbegin = buffer;
		strbegin < &buffer[buflen]; strbegin += BUFSIZE) {
	    strend = strbegin + BUFSIZE;

	    if (strend > &buffer[buflen])	/* stay inside buffer */
		strend = &buffer[buflen];
	    
	    /* find end of last full line in this chunk of the buffer */
	    s = strbegin;
	    while ((strend[-1]) != NL && (strend > s))
		strend--;
	    if (strend <= strbegin)	/* line longer than BUFSIZE, punt */
		continue;

	    k = strbegin + patlen - 1;

	    for (;;) {
		/* 
		 for a large class of patterns, upwards of 80% of 
		 match time is spent on the next line.  
		 we beat existing microcode (vax 'matchc') this way.
		 */
		while ((k += delta0[*(unsigned char *) k]) < strend)
			;
		if (k < (strbegin + LARGE))
		    break;
		k -= LARGE;
    
		j = patlen - 1;
		s = k - 1;
		while (cmap[*s--] == pattern[--j]);
		/* 
		 * delta-less shortcut for literati, but 
		 * short shrift for genetic engineers.
		 */
		if (j >= 0)
		    k++;
		else {		/* submatch */
		    t = k;
		    s = k - patlen + 1;
		    do
			;
		    while (*s != NL && --s >= strbegin);
		    k = s + 1;	/* at line start */
    
		    if ((k = gotamatch( k,
					(t - buffer),
					action)) == NULL)
			return;
		    if (k >= strend)
			break;
		}
	    }
	}
	if (buffer[buflen - 1] != last_byte)
		buffer[buflen - 1] = last_byte;
	return(nsuccess);
}

bmg_fsearch(fd, action)
int	fd;
int	(*action)();
{
	register char  *k,
	               *strend,
	               *s;
	register int    j;
	char   *t;
	char   *gotamatch();
	int     nleftover,
	        count,
		file_offset = 0;

	nleftover  = 0;
	nsuccess = 0;

	while ((count = read(fd, str + nleftover, BUFSIZE - nleftover)) > 0) {
	    count += nleftover;
	    if (count != BUFSIZE && fd != 0) {
		str[count++] = NL;	/* insurance for broken last line */
	    }
	    str[count] = 0;
	    for (j = count - 1; str[j] != NL && j >= 0;)
		j--;
	    if (j < 0) {	/* break up long line */
		str[count] = NL;
		str[++count] = EOS;
		strend = str + count;
		linetemp[0] = EOS;
		nleftover = 0;
	    }
	    else {		/* save partial line */
		strend = str + j;
		nleftover = count - j - 1;
		strncpy(linetemp, str + j + 1, nleftover);
	    }
	    k = str + patlen - 1;

	    for (;;) {
		/* 
		 for a large class of patterns, upwards of 80% of 
		 match time is spent on the next line.  
		 we beat existing microcode (vax 'matchc') this way.
		 */
		while ((k += delta0[*(unsigned char *) k]) < strend)
			;
		if (k < (str + LARGE))
		    break;
		k -= LARGE;

		j = patlen - 1;
		s = k - 1;
		while (cmap[*s--] == pattern[--j]);
		/* 
		 * delta-less shortcut for literati, but 
		 * short shrift for genetic engineers.
		 */
		if (j >= 0)
		    k++;
		else {		/* submatch */
		    t = k;
		    s = k - patlen + 1;
		    do
		        ;
		    while (*s != NL && --s >= str);
		    k = s + 1;	/* at line start */

		    if ((k = gotamatch( k,
		    			(file_offset + (t - str)),
					action)) == NULL)
			return;
		    if (k >= strend)
			break;
		}
	    }
	    file_offset += ( 1 + (strend - str));
	    strncpy(str, linetemp, nleftover);
	}
	return(nsuccess);
}

bmg_setup(pat, folded)		/* compute "boyer-moore" delta table */
char   *pat;		/* ... HAKMEM lives ... */
int	folded;
{
	register int    j;
	/* 
	 for multibyte characters (e.g. kanji), there are ways.
	 extrapolating 256 to 64K may be unwise, in favor of more
	 dynamics within boyermoore() itself. 
	 */
	patlen = strlen(pat);
	if (folded) {	/* fold case while saving pattern */
	    for (j = 0; j < patlen; j++) {
		pattern[j] = (isupper((int) pat[j]) 
				? (char) tolower((int) pat[j]) : pat[j]);
	    }
	}
	else
	    bcopy(pat, pattern, patlen);

	for (j = 0; j < 256; j++) {
	    delta0[j] = patlen;
	    cmap[j] = (char) j;	/* could be done at compile time */
	}
	for (j = 0; j < patlen - 1; j++)
	    delta0[pattern[j]] = patlen - j - 1;
	delta0[pattern[patlen - 1]] = LARGE;

	if (folded) {
	    for (j = 0; j < patlen - 1; j++)
		if (islower((int) pattern[j]))
		    delta0[toupper((int) pattern[j])] = patlen - j - 1;
	    if (islower((int) pattern[patlen - 1]))
		delta0[toupper((int) pattern[patlen - 1])] = LARGE;
	    for (j = 'A'; j <= 'Z'; j++)
		cmap[j] = (char) tolower((int) j);
	}
}

static char *gotamatch(s, pos, action)
register char *s;
register int pos;
int (*action)();
{
	static char	result[BUFSIZE];
	register char *r = result;

	nsuccess++;
	do
	    *r++ = *s;
	while (*s++ != NL);
	*r = 0;
	if (action == NULL) {
	    printf("%s", result);
	    return(s);
	}
	else
	    if (action(result, pos))
		return(s);
	    else
	    	return(NULL);
}

#ifndef	BSD
bcopy(from, to, len)
register char *from;
register char *to;
register int len;
{
	while (len-- > 0) {
		*to++ = *from++;
	}
}
#endif	BSD
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	/bin/chmod 664 bmgsubs.c
	/bin/echo -n '	'; /bin/ls -ld bmgsubs.c
fi
/bin/echo 'Extracting bmgtest.c'
sed 's/^X//' <<'//go.sysin dd *' >bmgtest.c
X/*
 * bmgtest.c
 *
 * Test driver/example program for Boyer-Moore-Gosper search routines
 *
 * Works like a stupid grep; takes only a few flags (-i, -n)
 */

#include <stdio.h>
#include <ctype.h>
#include <sys/types.h>

#ifdef	BSD
#define	strchr	index
#endif

int     iflag = 0,
        nflag = 0;

X/*
 * Called by bmg_fsearch for each line that matches the pattern
 */
printit(string, pos)
char   *string;			/* pointer to temporary copy of line */
int     pos;			/* byte offset from beginning of file */
{
	if (nflag)
	    printf("%d: %s", pos, string);
	else
	    printf("%s", string);
	return(1);	/* tells bmg_fsearch to continue the search */
}

main(argc, argv)
int     argc;
char  **argv;
{
	int     nsuccess,
	        fd;
	char   *pattern;

	while ((argc > 1) && (argv[1][0] == '-')) {
	    switch (argv[1][1]) {
		case 'i': 
		    iflag++;
		    break;
		case 'n': 
		    nflag++;
		    break;
		default: 
		    oops("usage: bmgtest [-i] [-n] pattern [file ...]");
	    }
	    argc--;
	    argv++;
	}
	argv++;
	if (argc <= 1)
	     oops("bmgtest: pattern argument missing");
	pattern = *argv;
	argc--;
	argv++;

	bmg_setup(pattern, iflag);

	if (argc <= 1) {	/* process stdin */
	    fd = 0;
	    bmg_fsearch(fd, printit);
	}
	else {
	    while (--argc > 0) {
		if ((fd = open(*argv, 0)) <= 0) {
		    fprintf(stderr, "bmgtest: can't open %s\n", *argv);
		    nsuccess = 2;
		    argv++;
		    continue;
		}
		bmg_fsearch(fd, printit);
		close(fd);
		argv++;
	    }
	}
	exit((nsuccess == 2) ? 2 : (nsuccess == 0));
}

oops(message)
char   *message;
{
	fprintf(stderr, "%s\n", message);
	exit(2);
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	/bin/chmod 664 bmgtest.c
	/bin/echo -n '	'; /bin/ls -ld bmgtest.c
fi
/bin/echo 'Extracting bmgtest2.c'
sed 's/^X//' <<'//go.sysin dd *' >bmgtest2.c
X/*
 * bmgtest2.c
 *
 * Test driver/example program for Boyer-Moore-Gosper search routines
 *	does buffer search instead of file search.
 *
 * Works like a very stupid grep; takes only a few flags (-i, -n)
 */

#include <stdio.h>
#include <ctype.h>
#include <sys/types.h>
#include <sys/stat.h>

char *malloc();

#ifdef	BSD
#define	strchr	index
#endif

int     iflag = 0,
        nflag = 0;

X/*
 * Called by bmg_search for each line that matches the pattern
 */
printit(string, pos)
char   *string;			/* pointer to temporary copy of line */
int     pos;			/* byte offset from beginning of file */
{
	if (nflag)
	    printf("%d: %s", pos, string);
	else
	    printf("%s", string);
	return(1);	/* tells bmg_fsearch to continue the search */
}

main(argc, argv)
int     argc;
char  **argv;
{
	int     nsuccess,
	        fd;
	char   *pattern;
	struct stat statbuf;
	char    *buffer;

	while ((argc > 1) && (argv[1][0] == '-')) {
	    switch (argv[1][1]) {
		case 'i': 
		    iflag++;
		    break;
		case 'n': 
		    nflag++;
		    break;
		default: 
		    oops("usage: bmgtest [-i] [-n] pattern [file ...]");
	    }
	    argc--;
	    argv++;
	}
	argv++;
	if (argc <= 1)
	     oops("bmgtest: pattern argument missing");
	pattern = *argv;
	argc--;
	argv++;

	bmg_setup(pattern, iflag);

	if (argc <= 1) {	/* process stdin */
	    fd = 0;
	    bmg_fsearch(fd, printit);
	}
	else {
	    while (--argc > 0) {
		if ((fd = open(*argv, 0)) <= 0) {
		    fprintf(stderr, "bmgtest: can't open %s\n", *argv);
		    nsuccess = 2;
		    argv++;
		    continue;
		}
		fstat(fd, &statbuf);
		buffer = malloc(statbuf.st_size);
		if (buffer == 0)
			oops("malloc failure");
		read(fd, buffer, statbuf.st_size);
		bmg_search(buffer, statbuf.st_size, printit);
		close(fd);
		free(buffer);
		argv++;
	    }
	}
	exit((nsuccess == 2) ? 2 : (nsuccess == 0));
}

oops(message)
char   *message;
{
	fprintf(stderr, "%s\n", message);
	exit(2);
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	/bin/chmod 664 bmgtest2.c
	/bin/echo -n '	'; /bin/ls -ld bmgtest2.c
fi