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