maint/gnulib/tests/test-memmem.c

/* */
This source file includes following definitions.
main
   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
  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 }
/* */
root/maint/gnulib/tests/test-memmem.c

DEFINITIONS
