diff options
| author | cgd <cgd@NetBSD.org> | 1994-06-22 00:15:22 +0000 |
|---|---|---|
| committer | cgd <cgd@NetBSD.org> | 1994-06-22 00:15:22 +0000 |
| commit | 7f79e48c1a96f9fe3ce6e7fc2fef2399f86fec3b (patch) | |
| tree | 8086571832c6d1c8fedb06f3fdcb7b3f4391e12d /lib/libc/string | |
| parent | 2d77dbfd70128b28b3ff729a2a9ff3ccfc7ad161 (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.inc | 13 | ||||
| -rw-r--r-- | lib/libc/string/bm.3 | 113 | ||||
| -rw-r--r-- | lib/libc/string/bm.c | 219 |
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); +} |
