lib/libc/string/bm.c

   1 /*      $NetBSD: bm.c,v 1.13 2014/06/23 10:43:25 shm Exp $      */
   2
   3 /*-
   4  * Copyright (c) 1994
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Andrew Hume of AT&T Bell Laboratories.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #if defined(LIBC_SCCS) && !defined(lint)
  37 #if 0
  38 static char sccsid[] = "@(#)bm.c        8.7 (Berkeley) 6/21/94";
  39 #else
  40 __RCSID("$NetBSD: bm.c,v 1.13 2014/06/23 10:43:25 shm Exp $");
  41 #endif
  42 #endif /* LIBC_SCCS && not lint */
  43
  44 #include "namespace.h"
  45 #include <sys/types.h>
  46
  47 #include <assert.h>
  48 #include <bm.h>
  49 #include <errno.h>
  50 #include <stdlib.h>
  51 #include <string.h>
  52
  53 #ifdef __weak_alias
  54 __weak_alias(bm_comp,_bm_comp)
  55 __weak_alias(bm_exec,_bm_exec)
  56 __weak_alias(bm_free,_bm_free)
  57 #endif
  58
  59 /*
  60  * XXX
  61  * The default frequency table starts at 99 and counts down.  The default
  62  * table should probably be oriented toward text, and will necessarily be
  63  * locale specific.  This one is for English.  It was derived from the
  64  * OSF/1 and 4.4BSD formatted and unformatted manual pages, and about 100Mb
  65  * of email and random text.  Change it if you can find something better.
  66  */
  67 static u_char const freq_def[256] = {
  68          0,  0,  0,  0,  0,  0,  0,  0,
  69          0, 77, 90,  0,  0,  0,  0,  0,
  70          0,  0,  0,  0,  0,  0,  0,  0,
  71          0,  0,  0,  0,  0,  0,  0,  0,
  72         99, 28, 42, 27, 16, 14, 20, 51,
  73         66, 65, 59, 24, 75, 76, 84, 56,
  74         72, 74, 64, 55, 54, 47, 41, 37,
  75         44, 61, 70, 43, 23, 53, 49, 22,
  76         33, 58, 40, 46, 45, 57, 60, 26,
  77         30, 63, 21, 12, 32, 50, 38, 39,
  78         34, 11, 48, 67, 62, 35, 15, 29,
  79         71, 18,  9, 17, 25, 13, 10, 52,
  80         36, 95, 78, 86, 87, 98, 82, 80,
  81         88, 94, 19, 68, 89, 83, 93, 96,
  82         81,  7, 91, 92, 97, 85, 69, 73,
  83         31, 79,  8,  5,  4,  6,  3,  0,
  84          0,  0,  0,  0,  0,  0,  0,  0,
  85          0,  0,  0,  0,  0,  0,  0,  0,
  86          0,  0,  0,  0,  0,  0,  0,  0,
  87          0,  0,  0,  0,  0,  0,  0,  0,
  88          0,  0,  0,  0,  0,  0,  0,  0,
  89          0,  0,  0,  0,  0,  0,  0,  0,
  90          0,  0,  0,  0,  0,  0,  0,  0,
  91          0,  0,  0,  0,  0,  0,  0,  0,
  92          0,  0,  0,  0,  0,  0,  0,  0,
  93          0,  0,  0,  0,  0,  0,  0,  0,
  94          0,  0,  0,  0,  0,  0,  0,  0,
  95          0,  0,  0,  0,  0,  0,  0,  0,
  96          0,  0,  0,  0,  0,  0,  0,  0,
  97          0,  0,  0,  0,  0,  0,  0,  0,
  98          0,  0,  0,  0,  0,  0,  0,  0,
  99          0,  0,  0,  0,  0,  0,  0,  0,
 100 };
 101
 102 bm_pat *
 103 bm_comp(u_char const *pb, size_t len, u_char const *freq)
 104 {
 105         u_char const *pe, *p;
 106         size_t *d, r;
 107         int j;
 108         int sv_errno;
 109         bm_pat *pat;
 110
 111         _DIAGASSERT(pb != NULL);
 112         /* freq may be NULL */
 113
 114         if (len == 0) {
 115                 errno = EINVAL;
 116                 return (NULL);
 117         }
 118         if ((pat = malloc(sizeof(*pat))) == NULL)
 119                 return (NULL);
 120         pat->pat = NULL;
 121         pat->delta = NULL;
 122
 123         pat->patlen = len;                      /* copy pattern */
 124         if ((pat->pat = malloc(pat->patlen)) == NULL)
 125                 goto mem;
 126         memcpy(pat->pat, pb, pat->patlen);
 127                                                 /* get skip delta */
 128         if ((pat->delta = malloc(256 * sizeof(*d))) == NULL)
 129                 goto mem;
 130         for (j = 0, d = pat->delta; j < 256; j++)
 131                 d[j] = pat->patlen;
 132         for (pe = pb + pat->patlen - 1; pb <= pe; pb++)
 133                 d[*pb] = pe - pb;
 134
 135         if (freq == NULL)                       /* default freq table */
 136                 freq = freq_def;
 137         r = 0;                                  /* get guard */
 138         for (pb = pat->pat, pe = pb + pat->patlen - 1; pb < pe; pb++)
 139                 if (freq[*pb] < freq[pat->pat[r]])
 140                         r = pb - pat->pat;
 141         pat->rarec = pat->pat[r];
 142         pat->rareoff = r - (pat->patlen - 1);
 143
 144                                                 /* get md2 shift */
 145         for (pe = pat->pat + pat->patlen - 1, p = pe - 1; p >= pat->pat; p--)
 146                 if (*p == *pe)
 147                         break;
 148
 149         /* *p is first leftward reoccurrence of *pe */
 150         pat->md2 = pe - p;
 151         return (pat);
 152
 153 mem:    sv_errno = errno;
 154         bm_free(pat);
 155         errno = sv_errno;
 156         return (NULL);
 157 }
 158
 159 void
 160 bm_free(bm_pat *pat)
 161 {
 162
 163         _DIAGASSERT(pat != NULL);
 164
 165         free(pat->pat);
 166         free(pat->delta);
 167         free(pat);
 168 }
 169
 170 u_char *
 171 bm_exec(bm_pat *pat, u_char *base, size_t n)
 172 {
 173         u_char *e, *ep, *p, *q, *s;
 174         size_t *d0, k, md2, n1, ro;
 175         int rc;
 176
 177         _DIAGASSERT(pat != NULL);
 178         _DIAGASSERT(base != NULL);
 179
 180         if (n == 0)
 181                 return (NULL);
 182
 183         d0 = pat->delta;
 184         n1 = pat->patlen - 1;
 185         md2 = pat->md2;
 186         ro = pat->rareoff;
 187         rc = pat->rarec;
 188         ep = pat->pat + pat->patlen - 1;
 189         s = base + (pat->patlen - 1);
 190
 191         /* fast loop up to n - 3 * patlen */
 192         e = base + n - 3 * pat->patlen;
 193         while (s < e) {
 194                 k = d0[*s];             /* ufast skip loop */
 195                 while (k && s < e) {
 196                         k = d0[*(s += k)];
 197                         k = d0[*(s += k)];
 198                 }
 199                 if (s >= e)
 200                         break;
 201                 if (s[ro] != rc)        /* guard test */
 202                         goto mismatch1;
 203                                         /* fwd match */
 204                 for (p = pat->pat, q = s - n1; p < ep;)
 205                         if (*q++ != *p++)
 206                                 goto mismatch1;
 207                 return (s - n1);
 208
 209 mismatch1:      s += md2;               /* md2 shift */
 210         }
 211
 212         /* slow loop up to end */
 213         e = base + n;
 214         while (s < e) {
 215                 s += d0[*s];            /* step */
 216                 if (s >= e)
 217                         break;
 218                 if (s[ro] != rc)        /* guard test */
 219                         goto mismatch2;
 220                                         /* fwd match */
 221                 for (p = pat->pat, q = s - n1; p <= ep;)
 222                         if (*q++ != *p++)
 223                                 goto mismatch2;
 224                 return (s - n1);
 225
 226 mismatch2:      s += md2;               /* md2 shift */
 227         }
 228
 229         return (NULL);
 230 }