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 "null-ptr.h"
  30 #include "zerosize-ptr.h"
  31 #include "macros.h"
  32
  33 int
  34 main (int argc, char *argv[])
  35 {
  36 #if HAVE_DECL_ALARM
  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
  40      long.  */
  41   int alarm_value = 100;
  42   signal (SIGALRM, SIG_DFL);
  43   alarm (alarm_value);
  44 #endif
  45
  46   {
  47     const char input[] = "foo";
  48     const char *result = memmem (input, strlen (input), "", 0);
  49     ASSERT (result == input);
  50   }
  51
  52   {
  53     const char input[] = "foo";
  54     const char *result = memmem (input, strlen (input), "o", 1);
  55     ASSERT (result == input + 1);
  56   }
  57
  58   {
  59     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  60     const char *result = memmem (input, strlen (input), "ABCDABD", 7);
  61     ASSERT (result == input + 15);
  62   }
  63
  64   {
  65     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  66     const char *result = memmem (input, strlen (input), "ABCDABE", 7);
  67     ASSERT (result == NULL);
  68   }
  69
  70   {
  71     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  72     const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
  73     ASSERT (result == input + 11);
  74   }
  75
  76   /* Check that length 0 does not dereference the pointer.  */
  77   {
  78     const char *result = memmem (zerosize_ptr (), 0, "foo", 3);
  79     ASSERT (result == NULL);
  80   }
  81
  82   {
  83     const char input[] = "foo";
  84     const char *result = memmem (input, strlen (input), null_ptr (), 0);
  85     ASSERT (result == input);
  86   }
  87
  88   /* Check that a long periodic needle does not cause false positives.  */
  89   {
  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);
  96   }
  97   {
  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);
 105   }
 106
 107   /* Check that a very long haystack is handled quickly if the needle is
 108      short and occurs near the beginning.  */
 109   {
 110     size_t repeat = 10000;
 111     size_t m = 1000000;
 112     const char *needle =
 113       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 114       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
 115     size_t n = strlen (needle);
 116     char *haystack = (char *) malloc (m + 1);
 117     if (haystack != NULL)
 118       {
 119         memset (haystack, 'A', m);
 120         haystack[0] = 'B';
 121
 122         for (; repeat > 0; repeat--)
 123           {
 124             ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
 125           }
 126
 127         free (haystack);
 128       }
 129   }
 130
 131   /* Check that a very long needle is discarded quickly if the haystack is
 132      short.  */
 133   {
 134     size_t repeat = 10000;
 135     size_t m = 1000000;
 136     const char *haystack =
 137       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 138       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
 139     size_t n = strlen (haystack);
 140     char *needle = (char *) malloc (m + 1);
 141     if (needle != NULL)
 142       {
 143         memset (needle, 'A', m);
 144
 145         for (; repeat > 0; repeat--)
 146           {
 147             ASSERT (memmem (haystack, n, needle, m) == NULL);
 148           }
 149
 150         free (needle);
 151       }
 152   }
 153
 154   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 155   {
 156     size_t m = 1000000;
 157     char *haystack = (char *) malloc (2 * m + 1);
 158     char *needle = (char *) malloc (m + 1);
 159     if (haystack != NULL && needle != NULL)
 160       {
 161         const char *result;
 162
 163         memset (haystack, 'A', 2 * m);
 164         haystack[2 * m] = 'B';
 165
 166         memset (needle, 'A', m);
 167         needle[m] = 'B';
 168
 169         result = memmem (haystack, 2 * m + 1, needle, m + 1);
 170         ASSERT (result == haystack + m);
 171       }
 172     free (needle);
 173     free (haystack);
 174   }
 175
 176   /* Check that long needles not present in a haystack can be handled
 177      with sublinear speed.  */
 178   {
 179     size_t repeat = 10000;
 180     size_t m = 1000000;
 181     size_t n = 1000;
 182     char *haystack = (char *) malloc (m);
 183     char *needle = (char *) malloc (n);
 184     if (haystack != NULL && needle != NULL)
 185       {
 186         const char *result;
 187
 188         memset (haystack, 'A', m);
 189         memset (needle, 'B', n);
 190
 191         for (; repeat > 0; repeat--)
 192           {
 193             result = memmem (haystack, m, needle, n);
 194             ASSERT (result == NULL);
 195           }
 196       }
 197     free (haystack);
 198     free (needle);
 199   }
 200
 201   {
 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
 205        gnulib v0.0-4927.  */
 206     const char *haystack =
 207       "\n"
 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"
 213       "with_gnu_ld\n"
 214       "with_ld\n"
 215       "with_demangler_in_ld\n"
 216       "with_gnu_as\n"
 217       "with_as\n"
 218       "enable_largefile\n"
 219       "enable_werror_always\n"
 220       "enable_checking\n"
 221       "enable_coverage\n"
 222       "enable_gather_detailed_mem_stats\n"
 223       "enable_build_with_cxx\n"
 224       "with_stabs\n"
 225       "enable_multilib\n"
 226       "enable___cxa_atexit\n"
 227       "enable_decimal_float\n"
 228       "enable_fixed_point\n"
 229       "enable_threads\n"
 230       "enable_tls\n"
 231       "enable_objc_gc\n"
 232       "with_dwarf2\n"
 233       "enable_shared\n"
 234       "with_build_sysroot\n"
 235       "with_sysroot\n"
 236       "with_specs\n"
 237       "with_pkgversion\n"
 238       "with_bugurl\n"
 239       "enable_languages\n"
 240       "with_multilib_list\n";
 241     const char *needle = "\n"
 242       "with_gnu_ld\n";
 243     const char* p = memmem (haystack, strlen (haystack),
 244                             needle, strlen (needle));
 245     ASSERT (p - haystack == 114);
 246   }
 247
 248   {
 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);
 255   }
 256
 257   {
 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";
 265     const char *h =
 266       "\n"
 267       "with_build_libsubdir\n"
 268       "with_local_prefix\n"
 269       "with_gxx_include_dir\n"
 270       "with_cpp_install_dir\n"
 271       "with_e_\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);
 278     size_t i;
 279     ASSERT (haystack);
 280     for (i = 0; i < h_len - strlen (needle); i++)
 281       {
 282         const char *p;
 283         memcpy (haystack, h, h_len + 1);
 284         memcpy (haystack + i, needle, strlen (needle) + 1);
 285         p = memmem (haystack, strlen (haystack), needle, strlen (needle));
 286         ASSERT (p);
 287         ASSERT (p - haystack == i);
 288       }
 289     free (haystack);
 290   }
 291
 292   /* Test long needles.  */
 293   {
 294     size_t m = 1024;
 295     char *haystack = (char *) malloc (2 * m + 1);
 296     char *needle = (char *) malloc (m + 1);
 297     if (haystack != NULL && needle != NULL)
 298       {
 299         const char *p;
 300         haystack[0] = 'x';
 301         memset (haystack + 1, ' ', m - 1);
 302         memset (haystack + m, 'x', m);
 303         haystack[2 * m] = '\0';
 304         memset (needle, 'x', m);
 305         needle[m] = '\0';
 306         p = memmem (haystack, strlen (haystack), needle, strlen (needle));
 307         ASSERT (p);
 308         ASSERT (p - haystack == m);
 309       }
 310     free (needle);
 311     free (haystack);
 312   }
 313
 314   return 0;
 315 }