summaryrefslogtreecommitdiff
path: root/lib/libc/string
diff options
context:
space:
mode:
authorcgd <cgd@NetBSD.org>1994-06-22 00:15:22 +0000
committercgd <cgd@NetBSD.org>1994-06-22 00:15:22 +0000
commit7f79e48c1a96f9fe3ce6e7fc2fef2399f86fec3b (patch)
tree8086571832c6d1c8fedb06f3fdcb7b3f4391e12d /lib/libc/string
parent2d77dbfd70128b28b3ff729a2a9ff3ccfc7ad161 (diff)
add Boyer-Moore string search routines, from Bostic. man page
needs to be fixed for mandoc, and RCSID's need to be added.
Diffstat (limited to 'lib/libc/string')
-rw-r--r--lib/libc/string/Makefile.inc13
-rw-r--r--lib/libc/string/bm.3113
-rw-r--r--lib/libc/string/bm.c219
3 files changed, 339 insertions, 6 deletions
diff --git a/lib/libc/string/Makefile.inc b/lib/libc/string/Makefile.inc
index 24672490b69..415ab314bef 100644
--- a/lib/libc/string/Makefile.inc
+++ b/lib/libc/string/Makefile.inc
@@ -1,10 +1,10 @@
# from: @(#)Makefile.inc 5.6 (Berkeley) 3/5/91
-# $Id: Makefile.inc,v 1.26 1994/02/25 07:42:01 phil Exp $
+# $Id: Makefile.inc,v 1.27 1994/06/22 00:15:22 cgd Exp $
# string sources
.PATH: ${.CURDIR}/arch/${MACHINE_ARCH}/string ${.CURDIR}/string
-SRCS+= memccpy.c strcasecmp.c strcoll.c strdup.c strerror.c \
+SRCS+= bm.c memccpy.c strcasecmp.c strcoll.c strdup.c strerror.c \
strftime.c strmode.c strtok.c strxfrm.c
.if (${MACHINE_ARCH} == "m68k")
@@ -120,12 +120,13 @@ strrchr.so: rindex.c
-o ${.TARGET}
.endif
-MAN3+= bcmp.0 bcopy.0 bstring.0 bzero.0 ffs.0 index.0 memccpy.0 memchr.0 \
+MAN3+= bm.0 bcmp.0 bcopy.0 bstring.0 bzero.0 ffs.0 index.0 memccpy.0 memchr.0 \
memcmp.0 memcpy.0 memmove.0 memset.0 rindex.0 strcasecmp.0 strcat.0 \
- strchr.0 strcmp.0 strcoll.0 strcpy.0 strcspn.0 strerror.0 strftime.0 string.0 \
- strlen.0 strmode.0 strdup.0 strpbrk.0 strrchr.0 strsep.0 strspn.0 \
- strstr.0 strtok.0 strxfrm.0 swab.0
+ strchr.0 strcmp.0 strcoll.0 strcpy.0 strcspn.0 strerror.0 strftime.0 \
+ string.0 strlen.0 strmode.0 strdup.0 strpbrk.0 strrchr.0 strsep.0 \
+ strspn.0 strstr.0 strtok.0 strxfrm.0 swab.0
+MLINKS+=bm.3 bm_comp.3 bm.3 bm_exec.3 bm.3 bm_free.3
MLINKS+=strcasecmp.3 strncasecmp.3
MLINKS+=strcat.3 strncat.3
MLINKS+=strcmp.3 strncmp.3
diff --git a/lib/libc/string/bm.3 b/lib/libc/string/bm.3
new file mode 100644
index 00000000000..11f09ea944c
--- /dev/null
+++ b/lib/libc/string/bm.3
@@ -0,0 +1,113 @@
+.\" Copyright (c) 1994
+.\" The Regents of the University of California. All rights reserved.
+.\"
+.\" This code is derived from software contributed to Berkeley by
+.\" Andrew Hume of AT&T Bell Laboratories.
+.\"
+.\" 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.
+.\" 3. All advertising materials mentioning features or use of this software
+.\" must display the following acknowledgement:
+.\" This product includes software developed by the University of
+.\" California, Berkeley and its contributors.
+.\" 4. Neither the name of the University nor the names of its contributors
+.\" may be used to endorse or promote products derived from this software
+.\" without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+.\"
+.\" @(#)bm.3 8.4 (Berkeley) 6/21/94
+.\"
+.TH BM 3
+.SH NAME
+bm_comp, bm_exec, bm_free \- Boyer-Moore string search
+.SH SYNOPSIS
+.ft B
+#include <sys/types.h>
+.br
+#include <bm.h>
+.sp
+bm_pat *
+.br
+bm_comp(u_char *pattern, size_t patlen, u_char freq[256]);
+.sp
+u_char *
+.br
+bm_exec(bm_pat *pdesc, u_char *text, size_t len);
+.sp
+void
+.br
+bm_free(bm_pat *pdesc);
+.SH DESCRIPTION
+These routines implement an efficient mechanism to find an
+occurrence of a byte string within another byte string.
+.PP
+.I Bm_comp
+evaluates the
+.I patlen
+bytes starting at
+.IR pattern ,
+and returns a pointer to a structure describing them.
+The bytes referenced by
+.I pattern
+may be of any value.
+.PP
+The search takes advantage of the frequency distribution of the
+bytes in the text to be searched.
+If specified,
+.I freq
+should be an array of 256 values,
+with higher values indicating that the corresponding character occurs
+more frequently.
+(A less than optimal frequency distribution can only result in less
+than optimal performance, not incorrect results.)
+If
+.I freq
+is NULL,
+a system default table is used.
+.PP
+.I Bm_exec
+returns a pointer to the leftmost occurrence of the string given to
+.I bm_comp
+within
+.IR text ,
+or NULL if none occurs.
+The number of bytes in
+.I text
+must be specified by
+.IR len .
+.PP
+Space allocated for the returned description is discarded
+by calling
+.I bm_free
+with the returned description as an argument.
+.PP
+The asymptotic speed of
+.I bm_exec
+is
+.RI O( len / patlen ).
+.PP
+.SH "SEE ALSO"
+.IR regexp (3),
+.IR strstr (3)
+.sp
+.IR "Fast String Searching" ,
+Hume and Sunday,
+Software Practice and Experience,
+Vol. 21, 11 (November 1991) pp. 1221-48.
diff --git a/lib/libc/string/bm.c b/lib/libc/string/bm.c
new file mode 100644
index 00000000000..7e61a8eb5b9
--- /dev/null
+++ b/lib/libc/string/bm.c
@@ -0,0 +1,219 @@
+/*-
+ * Copyright (c) 1994
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Andrew Hume of AT&T Bell Laboratories.
+ *
+ * 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.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)bm.c 8.7 (Berkeley) 6/21/94";
+#endif /* not lint */
+
+#include <sys/types.h>
+
+#include <bm.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * XXX
+ * The default frequency table starts at 99 and counts down. The default
+ * table should probably be oriented toward text, and will necessarily be
+ * locale specific. This one is for English. It was derived from the
+ * OSF/1 and 4.4BSD formatted and unformatted manual pages, and about 100Mb
+ * of email and random text. Change it if you can find something better.
+ */
+static u_char const freq_def[256] = {
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 77, 90, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 99, 28, 42, 27, 16, 14, 20, 51,
+ 66, 65, 59, 24, 75, 76, 84, 56,
+ 72, 74, 64, 55, 54, 47, 41, 37,
+ 44, 61, 70, 43, 23, 53, 49, 22,
+ 33, 58, 40, 46, 45, 57, 60, 26,
+ 30, 63, 21, 12, 32, 50, 38, 39,
+ 34, 11, 48, 67, 62, 35, 15, 29,
+ 71, 18, 9, 17, 25, 13, 10, 52,
+ 36, 95, 78, 86, 87, 98, 82, 80,
+ 88, 94, 19, 68, 89, 83, 93, 96,
+ 81, 7, 91, 92, 97, 85, 69, 73,
+ 31, 79, 8, 5, 4, 6, 3, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+};
+
+bm_pat *
+bm_comp(pb, len, freq)
+ u_char const *pb;
+ size_t len;
+ u_char const *freq;
+{
+ register u_char const *pe, *p;
+ register size_t *d, r;
+ register int j;
+ int sv_errno;
+ bm_pat *pat;
+
+ if (len == 0) {
+ errno = EINVAL;
+ return (NULL);
+ }
+ if ((pat = malloc(sizeof(*pat))) == NULL)
+ return (NULL);
+ pat->pat = NULL;
+ pat->delta = NULL;
+
+ pat->patlen = len; /* copy pattern */
+ if ((pat->pat = malloc(pat->patlen)) == NULL)
+ goto mem;
+ memcpy(pat->pat, pb, pat->patlen);
+ /* get skip delta */
+ if ((pat->delta = malloc(256 * sizeof(*d))) == NULL)
+ goto mem;
+ for (j = 0, d = pat->delta; j < 256; j++)
+ d[j] = pat->patlen;
+ for (pe = pb + pat->patlen - 1; pb <= pe; pb++)
+ d[*pb] = pe - pb;
+
+ if (freq == NULL) /* default freq table */
+ freq = freq_def;
+ r = 0; /* get guard */
+ for (pb = pat->pat, pe = pb + pat->patlen - 1; pb < pe; pb++)
+ if (freq[*pb] < freq[pat->pat[r]])
+ r = pb - pat->pat;
+ pat->rarec = pat->pat[r];
+ pat->rareoff = r - (pat->patlen - 1);
+
+ /* get md2 shift */
+ for (pe = pat->pat + pat->patlen - 1, p = pe - 1; p >= pat->pat; p--)
+ if (*p == *pe)
+ break;
+
+ /* *p is first leftward reoccurrence of *pe */
+ pat->md2 = pe - p;
+ return (pat);
+
+mem: sv_errno = errno;
+ bm_free(pat);
+ errno = sv_errno;
+ return (NULL);
+}
+
+void
+bm_free(pat)
+ bm_pat *pat;
+{
+ if (pat->pat != NULL)
+ free(pat->pat);
+ if (pat->delta != NULL)
+ free(pat->delta);
+ free(pat);
+}
+
+u_char *
+bm_exec(pat, base, n)
+ bm_pat *pat;
+ u_char *base;
+ size_t n;
+{
+ register u_char *e, *ep, *p, *q, *s;
+ register size_t *d0, k, md2, n1, ro;
+ register int rc;
+
+ if (n == 0)
+ return (NULL);
+
+ d0 = pat->delta;
+ n1 = pat->patlen - 1;
+ md2 = pat->md2;
+ ro = pat->rareoff;
+ rc = pat->rarec;
+ ep = pat->pat + pat->patlen - 1;
+ s = base + (pat->patlen - 1);
+
+ /* fast loop up to n - 3 * patlen */
+ e = base + n - 3 * pat->patlen;
+ while (s < e) {
+ k = d0[*s]; /* ufast skip loop */
+ while (k) {
+ k = d0[*(s += k)];
+ k = d0[*(s += k)];
+ }
+ if (s >= e)
+ break;
+ if (s[ro] != rc) /* guard test */
+ goto mismatch1;
+ /* fwd match */
+ for (p = pat->pat, q = s - n1; p < ep;)
+ if (*q++ != *p++)
+ goto mismatch1;
+ return (s - n1);
+
+mismatch1: s += md2; /* md2 shift */
+ }
+
+ /* slow loop up to end */
+ e = base + n;
+ while (s < e) {
+ s += d0[*s]; /* step */
+ if (s >= e)
+ break;
+ if (s[ro] != rc) /* guard test */
+ goto mismatch2;
+ /* fwd match */
+ for (p = pat->pat, q = s - n1; p < ep;)
+ if (*q++ != *p++)
+ goto mismatch2;
+ return (s - n1);
+
+mismatch2: s += md2; /* md2 shift */
+ }
+
+ return (NULL);
+}