bmgsubs - Boyer-Moore-Gosper fast string search subroutines
sources-request at panda.UUCP
sources-request at panda.UUCP
Fri May 23 08:02:47 AEST 1986
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 at 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 at 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
More information about the Mod.sources
mailing list