2 * Copyright (C) 2004, 2007-2019 Free Software Foundation, Inc.
3 * Written by Bruno Haible and Eric Blake
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>. */
22 #include "signature.h"
23 SIGNATURE_CHECK (memmem
, void *, (void const *, size_t, void const *, size_t));
30 #include "zerosize-ptr.h"
34 main (int argc
, char *argv
[])
37 /* Declare failure if test takes too long, by using default abort
38 caused by SIGALRM. All known platforms that lack alarm also lack
39 memmem, and the replacement memmem is known to not take too
41 int alarm_value
= 100;
42 signal (SIGALRM
, SIG_DFL
);
47 const char input
[] = "foo";
48 const char *result
= memmem (input
, strlen (input
), "", 0);
49 ASSERT (result
== input
);
53 const char input
[] = "foo";
54 const char *result
= memmem (input
, strlen (input
), "o", 1);
55 ASSERT (result
== input
+ 1);
59 const char input
[] = "ABC ABCDAB ABCDABCDABDE";
60 const char *result
= memmem (input
, strlen (input
), "ABCDABD", 7);
61 ASSERT (result
== input
+ 15);
65 const char input
[] = "ABC ABCDAB ABCDABCDABDE";
66 const char *result
= memmem (input
, strlen (input
), "ABCDABE", 7);
67 ASSERT (result
== NULL
);
71 const char input
[] = "ABC ABCDAB ABCDABCDABDE";
72 const char *result
= memmem (input
, strlen (input
), "ABCDABCD", 8);
73 ASSERT (result
== input
+ 11);
76 /* Check that length 0 does not dereference the pointer. */
78 const char *result
= memmem (zerosize_ptr (), 0, "foo", 3);
79 ASSERT (result
== NULL
);
83 const char input
[] = "foo";
84 const char *result
= memmem (input
, strlen (input
), null_ptr (), 0);
85 ASSERT (result
== input
);
88 /* Check that a long periodic needle does not cause false positives. */
90 const char input
[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
91 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
92 "_C3_A7_20_EF_BF_BD");
93 const char need
[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
94 const char *result
= memmem (input
, strlen (input
), need
, strlen (need
));
95 ASSERT (result
== NULL
);
98 const char input
[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
99 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
100 "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
101 "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
102 const char need
[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
103 const char *result
= memmem (input
, strlen (input
), need
, strlen (need
));
104 ASSERT (result
== input
+ 115);
107 /* Check that a very long haystack is handled quickly if the needle is
108 short and occurs near the beginning. */
110 size_t repeat
= 10000;
113 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
114 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
115 size_t n
= strlen (needle
);
116 char *haystack
= (char *) malloc (m
+ 1);
117 if (haystack
!= NULL
)
119 memset (haystack
, 'A', m
);
122 for (; repeat
> 0; repeat
--)
124 ASSERT (memmem (haystack
, m
, needle
, n
) == haystack
+ 1);
131 /* Check that a very long needle is discarded quickly if the haystack is
134 size_t repeat
= 10000;
136 const char *haystack
=
137 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
138 "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
139 size_t n
= strlen (haystack
);
140 char *needle
= (char *) malloc (m
+ 1);
143 memset (needle
, 'A', m
);
145 for (; repeat
> 0; repeat
--)
147 ASSERT (memmem (haystack
, n
, needle
, m
) == NULL
);
154 /* Check that the asymptotic worst-case complexity is not quadratic. */
157 char *haystack
= (char *) malloc (2 * m
+ 1);
158 char *needle
= (char *) malloc (m
+ 1);
159 if (haystack
!= NULL
&& needle
!= NULL
)
163 memset (haystack
, 'A', 2 * m
);
164 haystack
[2 * m
] = 'B';
166 memset (needle
, 'A', m
);
169 result
= memmem (haystack
, 2 * m
+ 1, needle
, m
+ 1);
170 ASSERT (result
== haystack
+ m
);
176 /* Check that long needles not present in a haystack can be handled
177 with sublinear speed. */
179 size_t repeat
= 10000;
182 char *haystack
= (char *) malloc (m
);
183 char *needle
= (char *) malloc (n
);
184 if (haystack
!= NULL
&& needle
!= NULL
)
188 memset (haystack
, 'A', m
);
189 memset (needle
, 'B', n
);
191 for (; repeat
> 0; repeat
--)
193 result
= memmem (haystack
, m
, needle
, n
);
194 ASSERT (result
== NULL
);
202 /* Ensure that with a barely periodic "short" needle, memmem's
203 search does not mistakenly skip just past the match point.
204 This use of memmem would mistakenly return NULL before
206 const char *haystack
=
208 "with_build_libsubdir\n"
209 "with_local_prefix\n"
210 "with_gxx_include_dir\n"
211 "with_cpp_install_dir\n"
212 "enable_generated_files_in_srcdir\n"
215 "with_demangler_in_ld\n"
219 "enable_werror_always\n"
222 "enable_gather_detailed_mem_stats\n"
223 "enable_build_with_cxx\n"
226 "enable___cxa_atexit\n"
227 "enable_decimal_float\n"
228 "enable_fixed_point\n"
234 "with_build_sysroot\n"
240 "with_multilib_list\n";
241 const char *needle
= "\n"
243 const char* p
= memmem (haystack
, strlen (haystack
),
244 needle
, strlen (needle
));
245 ASSERT (p
- haystack
== 114);
249 /* Same bug, shorter trigger. */
250 const char *haystack
= "..wi.d.";
251 const char *needle
= ".d.";
252 const char* p
= memmem (haystack
, strlen (haystack
),
253 needle
, strlen (needle
));
254 ASSERT (p
- haystack
== 4);
258 /* Like the above, but trigger the flaw in two_way_long_needle
259 by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
260 Rather than trying to find the right alignment manually, I've
261 arbitrarily chosen the following needle and template for the
262 haystack, and ensure that for each placement of the needle in
263 that haystack, memmem finds it. */
264 const char *needle
= "\nwith_gnu_ld-extend-to-len-32-b\n";
267 "with_build_libsubdir\n"
268 "with_local_prefix\n"
269 "with_gxx_include_dir\n"
270 "with_cpp_install_dir\n"
272 "..............................\n"
273 "with_FGHIJKLMNOPQRSTUVWXYZ\n"
274 "with_567890123456789\n"
275 "with_multilib_list\n";
276 size_t h_len
= strlen (h
);
277 char *haystack
= malloc (h_len
+ 1);
280 for (i
= 0; i
< h_len
- strlen (needle
); i
++)
283 memcpy (haystack
, h
, h_len
+ 1);
284 memcpy (haystack
+ i
, needle
, strlen (needle
) + 1);
285 p
= memmem (haystack
, strlen (haystack
), needle
, strlen (needle
));
287 ASSERT (p
- haystack
== i
);
292 /* Test long needles. */
295 char *haystack
= (char *) malloc (2 * m
+ 1);
296 char *needle
= (char *) malloc (m
+ 1);
297 if (haystack
!= NULL
&& needle
!= NULL
)
301 memset (haystack
+ 1, ' ', m
- 1);
302 memset (haystack
+ m
, 'x', m
);
303 haystack
[2 * m
] = '\0';
304 memset (needle
, 'x', m
);
306 p
= memmem (haystack
, strlen (haystack
), needle
, strlen (needle
));
308 ASSERT (p
- haystack
== m
);