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 *
memmem(const void * haystack,size_t hs_len,const void * needle,size_t ne_len)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 *
memmem(const void * haystack,size_t hs_len,const void * needle,size_t ne_len)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 = (uint32_t) ne[0] << 16 | ne[1], hw = (uint32_t) 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 size_t 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. */
188
