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 #define _GNU_SOURCE
63 #include <string.h>
64 #include <stdint.h>
65
66 #if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
67
68 /* Small and efficient memmem implementation (quadratic worst-case). */
69 void *
memmem(const void * haystack,size_t hs_len,const void * needle,size_t ne_len)70 memmem (const void *haystack, size_t hs_len, const void *needle, size_t ne_len)
71 {
72 const char *hs = haystack;
73 const char *ne = needle;
74
75 if (ne_len == 0)
76 return (void *)hs;
77 int i;
78 int c = ne[0];
79 const char *end = hs + hs_len - ne_len;
80
81 for ( ; hs <= end; hs++)
82 {
83 if (hs[0] != c)
84 continue;
85 for (i = ne_len - 1; i != 0; i--)
86 if (hs[i] != ne[i])
87 break;
88 if (i == 0)
89 return (void *)hs;
90 }
91
92 return NULL;
93 }
94
95 #else
96
97 # define RETURN_TYPE void *
98 # define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
99 # include "str-two-way.h"
100
101 #define hash2(p) (((size_t)(p)[0] - ((size_t)(p)[-1] << 3)) % sizeof (shift))
102
103 /* Fast memmem algorithm with guaranteed linear-time performance.
104 Small needles up to size 2 use a dedicated linear search. Longer needles
105 up to size 256 use a novel modified Horspool algorithm. It hashes pairs
106 of characters to quickly skip past mismatches. The main search loop only
107 exits if the last 2 characters match, avoiding unnecessary calls to memcmp
108 and allowing for a larger skip if there is no match. A self-adapting
109 filtering check is used to quickly detect mismatches in long needles.
110 By limiting the needle length to 256, the shift table can be reduced to 8
111 bits per entry, lowering preprocessing overhead and minimizing cache effects.
112 The limit also implies worst-case performance is linear.
113 Needles larger than 256 characters use the linear-time Two-Way algorithm. */
114 void *
memmem(const void * haystack,size_t hs_len,const void * needle,size_t ne_len)115 memmem (const void *haystack, size_t hs_len, const void *needle, size_t ne_len)
116 {
117 const unsigned char *hs = haystack;
118 const unsigned char *ne = needle;
119
120 if (ne_len == 0)
121 return (void *) hs;
122 if (ne_len == 1)
123 return (void *) memchr (hs, ne[0], hs_len);
124
125 /* Ensure haystack length is >= needle length. */
126 if (hs_len < ne_len)
127 return NULL;
128
129 const unsigned char *end = hs + hs_len - ne_len;
130
131 if (ne_len == 2)
132 {
133 uint32_t nw = (uint32_t) ne[0] << 16 | ne[1], hw = (uint32_t) hs[0] << 16 | hs[1];
134 for (hs++; hs <= end && hw != nw; )
135 hw = hw << 16 | *++hs;
136 return hw == nw ? (void *)(hs - 1) : NULL;
137 }
138
139 /* Use Two-Way algorithm for very long needles. */
140 if (__builtin_expect (ne_len > 256, 0))
141 return two_way_long_needle (hs, hs_len, ne, ne_len);
142
143 uint8_t shift[256];
144 size_t tmp, shift1;
145 size_t m1 = ne_len - 1;
146 size_t offset = 0;
147 size_t i;
148
149 /* Initialize bad character shift hash table. */
150 memset (shift, 0, sizeof (shift));
151 for (i = 1; i < m1; i++)
152 shift[hash2 (ne + i)] = i;
153 shift1 = m1 - shift[hash2 (ne + m1)];
154 shift[hash2 (ne + m1)] = m1;
155
156 for ( ; hs <= end; )
157 {
158 /* Skip past character pairs not in the needle. */
159 do
160 {
161 hs += m1;
162 tmp = shift[hash2 (hs)];
163 }
164 while (hs <= end && tmp == 0);
165
166 /* If the match is not at the end of the needle, shift to the end
167 and continue until we match the last 2 characters. */
168 hs -= tmp;
169 if (tmp < m1)
170 continue;
171
172 /* The last 2 characters match. If the needle is long, check a
173 fixed number of characters first to quickly filter out mismatches. */
174 if (m1 <= 15 || memcmp (hs + offset, ne + offset, sizeof (long)) == 0)
175 {
176 if (memcmp (hs, ne, m1) == 0)
177 return (void *) hs;
178
179 /* Adjust filter offset when it doesn't find the mismatch. */
180 offset = (offset >= sizeof (long) ? offset : m1) - sizeof (long);
181 }
182
183 /* Skip based on matching the last 2 characters. */
184 hs += shift1;
185 }
186 return NULL;
187 }
188 #endif /* Compilation for speed. */
189
