tests/test-memmem.c

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