tests/test-strstr.c

   1 /*
   2  * Copyright (C) 2004, 2007-2013 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 <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include <string.h>
  21
  22 #include "signature.h"
  23 SIGNATURE_CHECK (strstr, char *, (char const *, char const *));
  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 have
  38      a quadratic strstr, and the replacement strstr is known to not
  39      take too long.  */
  40   signal (SIGALRM, SIG_DFL);
  41   alarm (50);
  42 #endif
  43
  44   {
  45     const char input[] = "foo";
  46     const char *result = strstr (input, "");
  47     ASSERT (result == input);
  48   }
  49
  50   {
  51     const char input[] = "foo";
  52     const char *result = strstr (input, "o");
  53     ASSERT (result == input + 1);
  54   }
  55
  56   {
  57     /* On some platforms, the memchr() functions reads past the first
  58        occurrence of the byte to be searched, leading to an out-of-bounds
  59        read access for strstr().
  60        See <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=521737>.
  61        This is a bug in memchr(), see the Austin Group's clarification
  62        <http://www.opengroup.org/austin/docs/austin_454.txt>.  */
  63     const char *fix = "aBaaaaaaaaaaax";
  64     char *page_boundary = (char *) zerosize_ptr ();
  65     size_t len = strlen (fix) + 1;
  66     char *input = page_boundary ? page_boundary - len : malloc (len);
  67     const char *result;
  68
  69     strcpy (input, fix);
  70     result = strstr (input, "B1x");
  71     ASSERT (result == NULL);
  72     if (!page_boundary)
  73       free (input);
  74   }
  75
  76   {
  77     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  78     const char *result = strstr (input, "ABCDABD");
  79     ASSERT (result == input + 15);
  80   }
  81
  82   {
  83     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  84     const char *result = strstr (input, "ABCDABE");
  85     ASSERT (result == NULL);
  86   }
  87
  88   {
  89     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  90     const char *result = strstr (input, "ABCDABCD");
  91     ASSERT (result == input + 11);
  92   }
  93
  94   /* Check that a long periodic needle does not cause false positives.  */
  95   {
  96     const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
  97                          "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
  98                          "_C3_A7_20_EF_BF_BD";
  99     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 100     const char *result = strstr (input, need);
 101     ASSERT (result == NULL);
 102   }
 103   {
 104     const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 105                          "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 106                          "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
 107                          "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 108     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 109     const char *result = strstr (input, need);
 110     ASSERT (result == input + 115);
 111   }
 112
 113   /* Check that a very long haystack is handled quickly if the needle is
 114      short and occurs near the beginning.  */
 115   {
 116     size_t repeat = 10000;
 117     size_t m = 1000000;
 118     const char *needle =
 119       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 120       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
 121     char *haystack = (char *) malloc (m + 1);
 122     if (haystack != NULL)
 123       {
 124         memset (haystack, 'A', m);
 125         haystack[0] = 'B';
 126         haystack[m] = '\0';
 127
 128         for (; repeat > 0; repeat--)
 129           {
 130             ASSERT (strstr (haystack, needle) == haystack + 1);
 131           }
 132
 133         free (haystack);
 134       }
 135   }
 136
 137   /* Check that a very long needle is discarded quickly if the haystack is
 138      short.  */
 139   {
 140     size_t repeat = 10000;
 141     size_t m = 1000000;
 142     const char *haystack =
 143       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 144       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
 145     char *needle = (char *) malloc (m + 1);
 146     if (needle != NULL)
 147       {
 148         memset (needle, 'A', m);
 149         needle[m] = '\0';
 150
 151         for (; repeat > 0; repeat--)
 152           {
 153             ASSERT (strstr (haystack, needle) == NULL);
 154           }
 155
 156         free (needle);
 157       }
 158   }
 159
 160   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 161   {
 162     size_t m = 1000000;
 163     char *haystack = (char *) malloc (2 * m + 2);
 164     char *needle = (char *) malloc (m + 2);
 165     if (haystack != NULL && needle != NULL)
 166       {
 167         const char *result;
 168
 169         memset (haystack, 'A', 2 * m);
 170         haystack[2 * m] = 'B';
 171         haystack[2 * m + 1] = '\0';
 172
 173         memset (needle, 'A', m);
 174         needle[m] = 'B';
 175         needle[m + 1] = '\0';
 176
 177         result = strstr (haystack, needle);
 178         ASSERT (result == haystack + m);
 179       }
 180     free (needle);
 181     free (haystack);
 182   }
 183
 184   /* Sublinear speed is only possible in memmem; strstr must examine
 185      every character of haystack to find its length.  */
 186
 187
 188   {
 189     /* Ensure that with a barely periodic "short" needle, strstr's
 190        search does not mistakenly skip just past the match point.
 191        This use of strstr would mistakenly return NULL before
 192        gnulib v0.0-4927.  */
 193     const char *haystack =
 194       "\n"
 195       "with_build_libsubdir\n"
 196       "with_local_prefix\n"
 197       "with_gxx_include_dir\n"
 198       "with_cpp_install_dir\n"
 199       "enable_generated_files_in_srcdir\n"
 200       "with_gnu_ld\n"
 201       "with_ld\n"
 202       "with_demangler_in_ld\n"
 203       "with_gnu_as\n"
 204       "with_as\n"
 205       "enable_largefile\n"
 206       "enable_werror_always\n"
 207       "enable_checking\n"
 208       "enable_coverage\n"
 209       "enable_gather_detailed_mem_stats\n"
 210       "enable_build_with_cxx\n"
 211       "with_stabs\n"
 212       "enable_multilib\n"
 213       "enable___cxa_atexit\n"
 214       "enable_decimal_float\n"
 215       "enable_fixed_point\n"
 216       "enable_threads\n"
 217       "enable_tls\n"
 218       "enable_objc_gc\n"
 219       "with_dwarf2\n"
 220       "enable_shared\n"
 221       "with_build_sysroot\n"
 222       "with_sysroot\n"
 223       "with_specs\n"
 224       "with_pkgversion\n"
 225       "with_bugurl\n"
 226       "enable_languages\n"
 227       "with_multilib_list\n";
 228     const char *needle = "\n"
 229       "with_gnu_ld\n";
 230     const char* p = strstr (haystack, needle);
 231     ASSERT (p - haystack == 114);
 232   }
 233
 234   {
 235     /* Same bug, shorter trigger.  */
 236     const char *haystack = "..wi.d.";
 237     const char *needle = ".d.";
 238     const char* p = strstr (haystack, needle);
 239     ASSERT (p - haystack == 4);
 240   }
 241
 242   {
 243     /* Like the above, but trigger the flaw in two_way_long_needle
 244        by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
 245        Rather than trying to find the right alignment manually, I've
 246        arbitrarily chosen the following needle and template for the
 247        haystack, and ensure that for each placement of the needle in
 248        that haystack, strstr finds it.  */
 249     const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
 250     const char *h =
 251       "\n"
 252       "with_build_libsubdir\n"
 253       "with_local_prefix\n"
 254       "with_gxx_include_dir\n"
 255       "with_cpp_install_dir\n"
 256       "with_e_\n"
 257       "..............................\n"
 258       "with_FGHIJKLMNOPQRSTUVWXYZ\n"
 259       "with_567890123456789\n"
 260       "with_multilib_list\n";
 261     size_t h_len = strlen (h);
 262     char *haystack = malloc (h_len + 1);
 263     size_t i;
 264     ASSERT (haystack);
 265     for (i = 0; i < h_len - strlen (needle); i++)
 266       {
 267         const char *p;
 268         memcpy (haystack, h, h_len + 1);
 269         memcpy (haystack + i, needle, strlen (needle) + 1);
 270         p = strstr (haystack, needle);
 271         ASSERT (p);
 272         ASSERT (p - haystack == i);
 273       }
 274   }
 275
 276   return 0;
 277 }