newlib/libc/string/memmem.c

   1 /* Optimized memmem function.
   2    Copyright (c) 2018 Arm Ltd.  All rights reserved.
   3
   4    SPDX-License-Identifier: BSD-3-Clause
   5
   6    Redistribution and use in source and binary forms, with or without
   7    modification, are permitted provided that the following conditions
   8    are met:
   9    1. Redistributions of source code must retain the above copyright
  10       notice, this list of conditions and the following disclaimer.
  11    2. Redistributions in binary form must reproduce the above copyright
  12       notice, this list of conditions and the following disclaimer in the
  13       documentation and/or other materials provided with the distribution.
  14    3. The name of the company may not be used to endorse or promote
  15       products derived from this software without specific prior written
  16       permission.
  17
  18    THIS SOFTWARE IS PROVIDED BY ARM LTD ``AS IS'' AND ANY EXPRESS OR IMPLIED
  19    WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  20    MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21    IN NO EVENT SHALL ARM LTD BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  23    TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  24    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  25    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  26    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  27    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
  28
  29 /*
  30 FUNCTION
  31         <<memmem>>---find memory segment
  32
  33 INDEX
  34         memmem
  35
  36 SYNOPSIS
  37         #include <string.h>
  38         void *memmem(const void *<[s1]>, size_t <[l1]>, const void *<[s2]>,
  39                      size_t <[l2]>);
  40
  41 DESCRIPTION
  42
  43         Locates the first occurrence in the memory region pointed to
  44         by <[s1]> with length <[l1]> of the sequence of bytes pointed
  45         to by <[s2]> of length <[l2]>.  If you already know the
  46         lengths of your haystack and needle, <<memmem>> is much faster
  47         than <<strstr>>.
  48
  49 RETURNS
  50         Returns a pointer to the located segment, or a null pointer if
  51         <[s2]> is not found. If <[l2]> is 0, <[s1]> is returned.
  52
  53 PORTABILITY
  54 <<memmem>> is a newlib extension.
  55
  56 <<memmem>> requires no supporting OS subroutines.
  57
  58 QUICKREF
  59         memmem pure
  60 */
  61
  62 #include <string.h>
  63 #include <stdint.h>
  64
  65 #if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
  66
  67 /* Small and efficient memmem implementation (quadratic worst-case).  */
  68 void *
  69 memmem (const void *haystack, size_t hs_len, const void *needle, size_t ne_len)
  70 {
  71   const char *hs = haystack;
  72   const char *ne = needle;
  73
  74   if (ne_len == 0)
  75     return (void *)hs;
  76   int i;
  77   int c = ne[0];
  78   const char *end = hs + hs_len - ne_len;
  79
  80   for ( ; hs <= end; hs++)
  81   {
  82     if (hs[0] != c)
  83       continue;
  84     for (i = ne_len - 1; i != 0; i--)
  85       if (hs[i] != ne[i])
  86         break;
  87     if (i == 0)
  88       return (void *)hs;
  89   }
  90
  91   return NULL;
  92 }
  93
  94 #else
  95
  96 # define RETURN_TYPE void *
  97 # define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
  98 # include "str-two-way.h"
  99
 100 #define hash2(p) (((size_t)(p)[0] - ((size_t)(p)[-1] << 3)) % sizeof (shift))
 101
 102 /* Fast memmem algorithm with guaranteed linear-time performance.
 103    Small needles up to size 2 use a dedicated linear search.  Longer needles
 104    up to size 256 use a novel modified Horspool algorithm.  It hashes pairs
 105    of characters to quickly skip past mismatches.  The main search loop only
 106    exits if the last 2 characters match, avoiding unnecessary calls to memcmp
 107    and allowing for a larger skip if there is no match.  A self-adapting
 108    filtering check is used to quickly detect mismatches in long needles.
 109    By limiting the needle length to 256, the shift table can be reduced to 8
 110    bits per entry, lowering preprocessing overhead and minimizing cache effects.
 111    The limit also implies worst-case performance is linear.
 112    Needles larger than 256 characters use the linear-time Two-Way algorithm.  */
 113 void *
 114 memmem (const void *haystack, size_t hs_len, const void *needle, size_t ne_len)
 115 {
 116   const unsigned char *hs = haystack;
 117   const unsigned char *ne = needle;
 118
 119   if (ne_len == 0)
 120     return (void *) hs;
 121   if (ne_len == 1)
 122     return (void *) memchr (hs, ne[0], hs_len);
 123
 124   /* Ensure haystack length is >= needle length.  */
 125   if (hs_len < ne_len)
 126     return NULL;
 127
 128   const unsigned char *end = hs + hs_len - ne_len;
 129
 130   if (ne_len == 2)
 131     {
 132       uint32_t nw = ne[0] << 16 | ne[1], hw = hs[0] << 16 | hs[1];
 133       for (hs++; hs <= end && hw != nw; )
 134         hw = hw << 16 | *++hs;
 135       return hw == nw ? (void *)(hs - 1) : NULL;
 136     }
 137
 138   /* Use Two-Way algorithm for very long needles.  */
 139   if (__builtin_expect (ne_len > 256, 0))
 140     return two_way_long_needle (hs, hs_len, ne, ne_len);
 141
 142   uint8_t shift[256];
 143   size_t tmp, shift1;
 144   size_t m1 = ne_len - 1;
 145   size_t offset = 0;
 146   int i;
 147
 148   /* Initialize bad character shift hash table.  */
 149   memset (shift, 0, sizeof (shift));
 150   for (i = 1; i < m1; i++)
 151     shift[hash2 (ne + i)] = i;
 152   shift1 = m1 - shift[hash2 (ne + m1)];
 153   shift[hash2 (ne + m1)] = m1;
 154
 155   for ( ; hs <= end; )
 156     {
 157       /* Skip past character pairs not in the needle.  */
 158       do
 159         {
 160           hs += m1;
 161           tmp = shift[hash2 (hs)];
 162         }
 163       while (hs <= end && tmp == 0);
 164
 165       /* If the match is not at the end of the needle, shift to the end
 166          and continue until we match the last 2 characters.  */
 167       hs -= tmp;
 168       if (tmp < m1)
 169         continue;
 170
 171       /* The last 2 characters match.  If the needle is long, check a
 172          fixed number of characters first to quickly filter out mismatches.  */
 173       if (m1 <= 15 || memcmp (hs + offset, ne + offset, sizeof (long)) == 0)
 174         {
 175           if (memcmp (hs, ne, m1) == 0)
 176             return (void *) hs;
 177
 178           /* Adjust filter offset when it doesn't find the mismatch.  */
 179           offset = (offset >= sizeof (long) ? offset : m1) - sizeof (long);
 180         }
 181
 182       /* Skip based on matching the last 2 characters.  */
 183       hs += shift1;
 184     }
 185   return NULL;
 186 }
 187 #endif /* Compilation for speed.  */