Branch data Line data Source code
1 : : /*
2 : : * Copyright (C) 2004, 2007-2012 Free Software Foundation, Inc.
3 : : * Written by Bruno Haible and Eric Blake
4 : : *
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.
9 : : *
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.
14 : : *
15 : : * You should have received a copy of the GNU General Public License
16 : : * along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 : :
18 : : #include <config.h>
19 : :
20 : : #include <string.h>
21 : :
22 : : #include "signature.h"
23 : : SIGNATURE_CHECK (memmem, void *, (void const *, size_t, void const *, size_t));
24 : :
25 : : #include <signal.h>
26 : : #include <stdlib.h>
27 : : #include <unistd.h>
28 : :
29 : : #include "zerosize-ptr.h"
30 : : #include "macros.h"
31 : :
32 : : static void *
33 : 1 : null_ptr (void)
34 : : {
35 : 1 : return NULL;
36 : : }
37 : :
38 : : int
39 : 1 : main (int argc, char *argv[])
40 : : {
41 : : #if HAVE_DECL_ALARM
42 : : /* Declare failure if test takes too long, by using default abort
43 : : caused by SIGALRM. All known platforms that lack alarm also lack
44 : : memmem, and the replacement memmem is known to not take too
45 : : long. */
46 : 1 : signal (SIGALRM, SIG_DFL);
47 : 1 : alarm (100);
48 : : #endif
49 : :
50 : : {
51 : 1 : const char input[] = "foo";
52 : 1 : const char *result = memmem (input, strlen (input), "", 0);
53 [ - + ]: 1 : ASSERT (result == input);
54 : : }
55 : :
56 : : {
57 : 1 : const char input[] = "foo";
58 : 1 : const char *result = memmem (input, strlen (input), "o", 1);
59 [ - + ]: 1 : ASSERT (result == input + 1);
60 : : }
61 : :
62 : : {
63 : 1 : const char input[] = "ABC ABCDAB ABCDABCDABDE";
64 : 1 : const char *result = memmem (input, strlen (input), "ABCDABD", 7);
65 [ - + ]: 1 : ASSERT (result == input + 15);
66 : : }
67 : :
68 : : {
69 : 1 : const char input[] = "ABC ABCDAB ABCDABCDABDE";
70 : 1 : const char *result = memmem (input, strlen (input), "ABCDABE", 7);
71 [ - + ]: 1 : ASSERT (result == NULL);
72 : : }
73 : :
74 : : {
75 : 1 : const char input[] = "ABC ABCDAB ABCDABCDABDE";
76 : 1 : const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
77 [ - + ]: 1 : ASSERT (result == input + 11);
78 : : }
79 : :
80 : : /* Check that length 0 does not dereference the pointer. */
81 : : {
82 : 1 : const char *result = memmem (zerosize_ptr (), 0, "foo", 3);
83 [ - + ]: 1 : ASSERT (result == NULL);
84 : : }
85 : :
86 : : {
87 : 1 : const char input[] = "foo";
88 : 1 : const char *result = memmem (input, strlen (input), null_ptr (), 0);
89 [ - + ]: 1 : ASSERT (result == input);
90 : : }
91 : :
92 : : /* Check that a long periodic needle does not cause false positives. */
93 : : {
94 : 1 : const char input[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
95 : : "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
96 : : "_C3_A7_20_EF_BF_BD");
97 : 1 : const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
98 : 1 : const char *result = memmem (input, strlen (input), need, strlen (need));
99 [ - + ]: 1 : ASSERT (result == NULL);
100 : : }
101 : : {
102 : 1 : const char input[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
103 : : "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
104 : : "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
105 : : "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
106 : 1 : const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
107 : 1 : const char *result = memmem (input, strlen (input), need, strlen (need));
108 [ - + ]: 1 : ASSERT (result == input + 115);
109 : : }
110 : :
111 : : /* Check that a very long haystack is handled quickly if the needle is
112 : : short and occurs near the beginning. */
113 : : {
114 : 1 : size_t repeat = 10000;
115 : 1 : size_t m = 1000000;
116 : 1 : const char *needle =
117 : : "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
118 : : "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
119 : 1 : size_t n = strlen (needle);
120 : 1 : char *haystack = (char *) malloc (m + 1);
121 [ + - ]: 1 : if (haystack != NULL)
122 : : {
123 : 1 : memset (haystack, 'A', m);
124 : 1 : haystack[0] = 'B';
125 : :
126 [ + + ]: 10001 : for (; repeat > 0; repeat--)
127 : : {
128 [ - + ]: 10000 : ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
129 : : }
130 : :
131 : 1 : free (haystack);
132 : : }
133 : : }
134 : :
135 : : /* Check that a very long needle is discarded quickly if the haystack is
136 : : short. */
137 : : {
138 : 1 : size_t repeat = 10000;
139 : 1 : size_t m = 1000000;
140 : 1 : const char *haystack =
141 : : "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
142 : : "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
143 : 1 : size_t n = strlen (haystack);
144 : 1 : char *needle = (char *) malloc (m + 1);
145 [ + - ]: 1 : if (needle != NULL)
146 : : {
147 : 1 : memset (needle, 'A', m);
148 : :
149 [ + + ]: 10001 : for (; repeat > 0; repeat--)
150 : : {
151 [ - + ]: 10000 : ASSERT (memmem (haystack, n, needle, m) == NULL);
152 : : }
153 : :
154 : 1 : free (needle);
155 : : }
156 : : }
157 : :
158 : : /* Check that the asymptotic worst-case complexity is not quadratic. */
159 : : {
160 : 1 : size_t m = 1000000;
161 : 1 : char *haystack = (char *) malloc (2 * m + 1);
162 : 1 : char *needle = (char *) malloc (m + 1);
163 [ + - ][ + - ]: 1 : if (haystack != NULL && needle != NULL)
164 : : {
165 : : const char *result;
166 : :
167 : 1 : memset (haystack, 'A', 2 * m);
168 : 1 : haystack[2 * m] = 'B';
169 : :
170 : 1 : memset (needle, 'A', m);
171 : 1 : needle[m] = 'B';
172 : :
173 : 1 : result = memmem (haystack, 2 * m + 1, needle, m + 1);
174 [ - + ]: 1 : ASSERT (result == haystack + m);
175 : : }
176 : 1 : free (needle);
177 : 1 : free (haystack);
178 : : }
179 : :
180 : : /* Check that long needles not present in a haystack can be handled
181 : : with sublinear speed. */
182 : : {
183 : 1 : size_t repeat = 10000;
184 : 1 : size_t m = 1000000;
185 : 1 : size_t n = 1000;
186 : 1 : char *haystack = (char *) malloc (m);
187 : 1 : char *needle = (char *) malloc (n);
188 [ + - ][ + - ]: 1 : if (haystack != NULL && needle != NULL)
189 : : {
190 : : const char *result;
191 : :
192 : 1 : memset (haystack, 'A', m);
193 : 1 : memset (needle, 'B', n);
194 : :
195 [ + + ]: 10001 : for (; repeat > 0; repeat--)
196 : : {
197 : 10000 : result = memmem (haystack, m, needle, n);
198 [ - + ]: 10000 : ASSERT (result == NULL);
199 : : }
200 : : }
201 : 1 : free (haystack);
202 : 1 : free (needle);
203 : : }
204 : :
205 : : {
206 : : /* Ensure that with a barely periodic "short" needle, memmem's
207 : : search does not mistakenly skip just past the match point.
208 : : This use of memmem would mistakenly return NULL before
209 : : gnulib v0.0-4927. */
210 : 1 : const char *haystack =
211 : : "\n"
212 : : "with_build_libsubdir\n"
213 : : "with_local_prefix\n"
214 : : "with_gxx_include_dir\n"
215 : : "with_cpp_install_dir\n"
216 : : "enable_generated_files_in_srcdir\n"
217 : : "with_gnu_ld\n"
218 : : "with_ld\n"
219 : : "with_demangler_in_ld\n"
220 : : "with_gnu_as\n"
221 : : "with_as\n"
222 : : "enable_largefile\n"
223 : : "enable_werror_always\n"
224 : : "enable_checking\n"
225 : : "enable_coverage\n"
226 : : "enable_gather_detailed_mem_stats\n"
227 : : "enable_build_with_cxx\n"
228 : : "with_stabs\n"
229 : : "enable_multilib\n"
230 : : "enable___cxa_atexit\n"
231 : : "enable_decimal_float\n"
232 : : "enable_fixed_point\n"
233 : : "enable_threads\n"
234 : : "enable_tls\n"
235 : : "enable_objc_gc\n"
236 : : "with_dwarf2\n"
237 : : "enable_shared\n"
238 : : "with_build_sysroot\n"
239 : : "with_sysroot\n"
240 : : "with_specs\n"
241 : : "with_pkgversion\n"
242 : : "with_bugurl\n"
243 : : "enable_languages\n"
244 : : "with_multilib_list\n";
245 : 1 : const char *needle = "\n"
246 : : "with_gnu_ld\n";
247 : 1 : const char* p = memmem (haystack, strlen (haystack),
248 : : needle, strlen (needle));
249 [ - + ]: 1 : ASSERT (p - haystack == 114);
250 : : }
251 : :
252 : : {
253 : : /* Same bug, shorter trigger. */
254 : 1 : const char *haystack = "..wi.d.";
255 : 1 : const char *needle = ".d.";
256 : 1 : const char* p = memmem (haystack, strlen (haystack),
257 : : needle, strlen (needle));
258 [ - + ]: 1 : ASSERT (p - haystack == 4);
259 : : }
260 : :
261 : : {
262 : : /* Like the above, but trigger the flaw in two_way_long_needle
263 : : by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
264 : : Rather than trying to find the right alignment manually, I've
265 : : arbitrarily chosen the following needle and template for the
266 : : haystack, and ensure that for each placement of the needle in
267 : : that haystack, memmem finds it. */
268 : 1 : const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
269 : 1 : const char *h =
270 : : "\n"
271 : : "with_build_libsubdir\n"
272 : : "with_local_prefix\n"
273 : : "with_gxx_include_dir\n"
274 : : "with_cpp_install_dir\n"
275 : : "with_e_\n"
276 : : "..............................\n"
277 : : "with_FGHIJKLMNOPQRSTUVWXYZ\n"
278 : : "with_567890123456789\n"
279 : : "with_multilib_list\n";
280 : 1 : size_t h_len = strlen (h);
281 : 1 : char *haystack = malloc (h_len + 1);
282 : : size_t i;
283 [ - + ]: 1 : ASSERT (haystack);
284 [ + + ]: 157 : for (i = 0; i < h_len - strlen (needle); i++)
285 : : {
286 : : const char *p;
287 : 156 : memcpy (haystack, h, h_len + 1);
288 : 156 : memcpy (haystack + i, needle, strlen (needle) + 1);
289 : 156 : p = memmem (haystack, strlen (haystack), needle, strlen (needle));
290 [ - + ]: 156 : ASSERT (p);
291 [ - + ]: 156 : ASSERT (p - haystack == i);
292 : : }
293 : : }
294 : :
295 : 1 : return 0;
296 : : }
|
