tests/test-memmem.c

   1 /*
   2  * Copyright (C) 2004, 2007-2024 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
  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 case from Yves Bastide.
 296      <https://www.openwall.com/lists/musl/2014/04/18/2>  */
 297   {
 298     const char input[] = "playing play play play always";
 299     const char *result = memmem (input, strlen (input), "play play play", 14);
 300     ASSERT (result == input + 8);
 301   }
 302
 303   /* Test long needles.  */
 304   {
 305     size_t m = 1024;
 306     char *haystack = (char *) malloc (2 * m + 1);
 307     char *needle = (char *) malloc (m + 1);
 308     if (haystack != NULL && needle != NULL)
 309       {
 310         const char *p;
 311         haystack[0] = 'x';
 312         memset (haystack + 1, ' ', m - 1);
 313         memset (haystack + m, 'x', m);
 314         haystack[2 * m] = '\0';
 315         memset (needle, 'x', m);
 316         needle[m] = '\0';
 317         p = memmem (haystack, strlen (haystack), needle, strlen (needle));
 318         ASSERT (p);
 319         ASSERT (p - haystack == m);
 320       }
 321     free (needle);
 322     free (haystack);
 323   }
 324
 325   return test_exit_status;
 326 }