summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTed Unangst <tedu@cvs.openbsd.org>2014-03-23 23:16:49 +0000
committerTed Unangst <tedu@cvs.openbsd.org>2014-03-23 23:16:49 +0000
commit3c8e7d12a100f01c891c526512c9e4294e284243 (patch)
tree08f880428da88551ee4470c699399651473b2899
parent15f4b66570ccd026d6e07c4b4990ce4ea88d04db (diff)
remove the never used bm string functions
-rw-r--r--lib/libc/string/Makefile.inc7
-rw-r--r--lib/libc/string/bm.3120
-rw-r--r--lib/libc/string/bm.c205
3 files changed, 3 insertions, 329 deletions
diff --git a/lib/libc/string/Makefile.inc b/lib/libc/string/Makefile.inc
index 1cbb54b3b5c..1f6d756182b 100644
--- a/lib/libc/string/Makefile.inc
+++ b/lib/libc/string/Makefile.inc
@@ -1,9 +1,9 @@
-# $OpenBSD: Makefile.inc,v 1.33 2014/01/22 21:06:45 tedu Exp $
+# $OpenBSD: Makefile.inc,v 1.34 2014/03/23 23:16:48 tedu Exp $
# string sources
.PATH: ${LIBCSRCDIR}/arch/${MACHINE_CPU}/string ${LIBCSRCDIR}/string
-SRCS+= bm.c explicit_bzero.c memccpy.c memmem.c memrchr.c stpcpy.c stpncpy.c \
+SRCS+= explicit_bzero.c memccpy.c memmem.c memrchr.c stpcpy.c stpncpy.c \
strcasecmp.c strcasestr.c strcoll.c strdup.c \
strerror.c strerror_r.c strlcat.c strmode.c strndup.c strnlen.c \
strsignal.c strtok.c strxfrm.c \
@@ -144,7 +144,7 @@ strrchr.do: rindex.c
@mv ${.TARGET}.tmp ${.TARGET}
.endif
-MAN+= bm.3 bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 memccpy.3 memchr.3 \
+MAN+= bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 memccpy.3 memchr.3 \
memcmp.3 memcpy.3 memmem.3 memmove.3 memset.3 stpcpy.3 strcasecmp.3 \
strcat.3 strchr.3 strcmp.3 strcoll.3 strcpy.3 strcspn.3 strdup.3 \
strerror.3 string.3 strlen.3 strmode.3 strncat.3 strncpy.3 strpbrk.3 \
@@ -154,7 +154,6 @@ MAN+= bm.3 bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 memccpy.3 memchr.3 \
wcsstr.3 wcstok.3 wcswidth.3 wmemchr.3 wmemcmp.3 wmemcpy.3 wmemmove.3 \
wmemset.3
-MLINKS+=bm.3 bm_comp.3 bm.3 bm_exec.3 bm.3 bm_free.3
MLINKS+=bzero.3 explicit_bzero.3
MLINKS+=memchr.3 memrchr.3
MLINKS+=stpcpy.3 stpncpy.3
diff --git a/lib/libc/string/bm.3 b/lib/libc/string/bm.3
deleted file mode 100644
index 82f59175940..00000000000
--- a/lib/libc/string/bm.3
+++ /dev/null
@@ -1,120 +0,0 @@
-.\" 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. 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.
-.\"
-.\" $OpenBSD: bm.3,v 1.12 2013/12/05 07:43:20 jmc Exp $
-.\"
-.Dd $Mdocdate: December 5 2013 $
-.Dt BM 3
-.Os
-.Sh NAME
-.Nm bm_comp ,
-.Nm bm_exec ,
-.Nm bm_free
-.Nd Boyer-Moore string search
-.Sh SYNOPSIS
-.In sys/types.h
-.In bm.h
-.Ft bm_pat *
-.Fn bm_comp "const unsigned char *pattern" "size_t patlen" \
- "const unsigned char freq[256]"
-.Ft unsigned char *
-.Fn bm_exec "bm_pat *pdesc" "unsigned char *text" "size_t len"
-.Ft void
-.Fn 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
-.Fn bm_comp
-evaluates
-.Fa patlen
-bytes starting at
-.Fa pattern
-and returns a pointer to a structure describing them.
-The bytes referenced by
-.Fa 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,
-.Ar 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
-.Ar freq
-is
-.Dv NULL ,
-a system default table is used.
-.Pp
-.Fn bm_exec
-returns a pointer to the leftmost occurrence of the string given to
-.Fn bm_comp
-within
-.Ar text ,
-or
-.Dv NULL
-if none occurs.
-The number of bytes in
-.Ar text
-must be specified by
-.Ar len .
-.Pp
-Space allocated for the returned description is discarded
-by calling
-.Fn bm_free
-with the returned description as an argument.
-.Pp
-The asymptotic speed of
-.Fn bm_exec
-is
-.Pf O Ns Pq len / patlen .
-.Sh SEE ALSO
-.Xr regex 3 ,
-.Xr strstr 3
-.Rs
-.%R "Fast String Searching"
-.%A Andrew Hume
-.%A Daniel Sunday
-.%J "Software Practice and Experience"
-.%V Volume 21, 11 (November 1991)
-.%P 1221-48
-.Re
-.Sh HISTORY
-The
-.Fn bm_comp ,
-.Fn bm_exec ,
-and
-.Fn bm_free
-functions first appeared in
-.Nx 1.0 .
diff --git a/lib/libc/string/bm.c b/lib/libc/string/bm.c
deleted file mode 100644
index 2c4c6ca7207..00000000000
--- a/lib/libc/string/bm.c
+++ /dev/null
@@ -1,205 +0,0 @@
-/* $OpenBSD: bm.c,v 1.7 2007/09/02 15:19:18 deraadt Exp $ */
-/*-
- * 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. 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.
- */
-
-#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(u_char const *pb, size_t len, u_char const *freq)
-{
- u_char const *pe, *p;
- size_t *d, r;
- 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 = calloc(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(bm_pat *pat)
-{
- if (pat->pat != NULL)
- free(pat->pat);
- if (pat->delta != NULL)
- free(pat->delta);
- free(pat);
-}
-
-u_char *
-bm_exec(bm_pat *pat, u_char *base, size_t n)
-{
- u_char *e, *ep, *p, *q, *s;
- size_t *d0, k, md2, n1, ro;
- 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);
-}