1.\" Copyright (c) 1994
2.\"	The Regents of the University of California.  All rights reserved.
3.\"
4.\" This code is derived from software contributed to Berkeley by
5.\" Andrew Hume of AT&T Bell Laboratories.
6.\"
7.\" Redistribution and use in source and binary forms, with or without
8.\" modification, are permitted provided that the following conditions
9.\" are met:
10.\" 1. Redistributions of source code must retain the above copyright
11.\"    notice, this list of conditions and the following disclaimer.
12.\" 2. Redistributions in binary form must reproduce the above copyright
13.\"    notice, this list of conditions and the following disclaimer in the
14.\"    documentation and/or other materials provided with the distribution.
15.\" 3. Neither the name of the University nor the names of its contributors
16.\"    may be used to endorse or promote products derived from this software
17.\"    without specific prior written permission.
18.\"
19.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29.\" SUCH DAMAGE.
30.\"
31.\"	$OpenBSD: bm.3,v 1.8 2005/08/06 03:19:23 jaredy Exp $
32.\"
33.Dd June 29, 1999
34.Dt BM 3
35.Os
36.Sh NAME
37.Nm bm_comp ,
38.Nm bm_exec ,
39.Nm bm_free
40.Nd Boyer-Moore string search
41.Sh SYNOPSIS
42.Fd #include <sys/types.h>
43.Fd #include <bm.h>
44.Ft bm_pat *
45.Fn bm_comp "const unsigned char *pattern" "size_t patlen" \
46    "const unsigned char freq[256]"
47.Ft unsigned char *
48.Fn bm_exec "bm_pat *pdesc" "unsigned char *text" "size_t len"
49.Ft void
50.Fn bm_free "bm_pat *pdesc"
51.Sh DESCRIPTION
52These routines implement an efficient mechanism to find an
53occurrence of a byte string within another byte string.
54.Pp
55.Fn bm_comp
56evaluates
57.Fa patlen
58bytes starting at
59.Fa pattern
60and returns a pointer to a structure describing them.
61The bytes referenced by
62.Fa pattern
63may be of any value.
64.Pp
65The search takes advantage of the frequency distribution of the
66bytes in the text to be searched.
67If specified,
68.Ar freq
69should be an array of 256 values,
70with higher values indicating that the corresponding character occurs
71more frequently.
72(A less than optimal frequency distribution can only result in less
73than optimal performance, not incorrect results.)
74If
75.Ar freq
76is
77.Dv NULL ,
78a system default table is used.
79.Pp
80.Fn bm_exec
81returns a pointer to the leftmost occurrence of the string given to
82.Fn bm_comp
83within
84.Ar text ,
85or
86.Dv NULL
87if none occurs.
88The number of bytes in
89.Ar text
90must be specified by
91.Ar len .
92.Pp
93Space allocated for the returned description is discarded
94by calling
95.Fn bm_free
96with the returned description as an argument.
97.Pp
98The asymptotic speed of
99.Fn bm_exec
100is
101.Pf O Ns Pq len / patlen .
102.Sh SEE ALSO
103.Xr regexp 3 ,
104.Xr strstr 3
105.Rs
106.%R "Fast String Searching"
107.%A Andrew Hume
108.%A Daniel Sunday
109.%J "Software Practice and Experience"
110.%V Volume 21, 11 (November 1991)
111.%P 1221-48
112.Re
113