LCOV - code coverage report
Current view: top level - lib/gltests - test-memmem.c (source / functions) Hit Total Coverage
Test: GNU SASL Lines: 99 99 100.0 %
Date: 2012-05-28 Functions: 2 2 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 32 56 57.1 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (C) 2004, 2007-2012 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 (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                 :            : static void *
      33                 :          1 : null_ptr (void)
      34                 :            : {
      35                 :          1 :   return NULL;
      36                 :            : }
      37                 :            : 
      38                 :            : int
      39                 :          1 : main (int argc, char *argv[])
      40                 :            : {
      41                 :            : #if HAVE_DECL_ALARM
      42                 :            :   /* Declare failure if test takes too long, by using default abort
      43                 :            :      caused by SIGALRM.  All known platforms that lack alarm also lack
      44                 :            :      memmem, and the replacement memmem is known to not take too
      45                 :            :      long.  */
      46                 :          1 :   signal (SIGALRM, SIG_DFL);
      47                 :          1 :   alarm (100);
      48                 :            : #endif
      49                 :            : 
      50                 :            :   {
      51                 :          1 :     const char input[] = "foo";
      52                 :          1 :     const char *result = memmem (input, strlen (input), "", 0);
      53         [ -  + ]:          1 :     ASSERT (result == input);
      54                 :            :   }
      55                 :            : 
      56                 :            :   {
      57                 :          1 :     const char input[] = "foo";
      58                 :          1 :     const char *result = memmem (input, strlen (input), "o", 1);
      59         [ -  + ]:          1 :     ASSERT (result == input + 1);
      60                 :            :   }
      61                 :            : 
      62                 :            :   {
      63                 :          1 :     const char input[] = "ABC ABCDAB ABCDABCDABDE";
      64                 :          1 :     const char *result = memmem (input, strlen (input), "ABCDABD", 7);
      65         [ -  + ]:          1 :     ASSERT (result == input + 15);
      66                 :            :   }
      67                 :            : 
      68                 :            :   {
      69                 :          1 :     const char input[] = "ABC ABCDAB ABCDABCDABDE";
      70                 :          1 :     const char *result = memmem (input, strlen (input), "ABCDABE", 7);
      71         [ -  + ]:          1 :     ASSERT (result == NULL);
      72                 :            :   }
      73                 :            : 
      74                 :            :   {
      75                 :          1 :     const char input[] = "ABC ABCDAB ABCDABCDABDE";
      76                 :          1 :     const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
      77         [ -  + ]:          1 :     ASSERT (result == input + 11);
      78                 :            :   }
      79                 :            : 
      80                 :            :   /* Check that length 0 does not dereference the pointer.  */
      81                 :            :   {
      82                 :          1 :     const char *result = memmem (zerosize_ptr (), 0, "foo", 3);
      83         [ -  + ]:          1 :     ASSERT (result == NULL);
      84                 :            :   }
      85                 :            : 
      86                 :            :   {
      87                 :          1 :     const char input[] = "foo";
      88                 :          1 :     const char *result = memmem (input, strlen (input), null_ptr (), 0);
      89         [ -  + ]:          1 :     ASSERT (result == input);
      90                 :            :   }
      91                 :            : 
      92                 :            :   /* Check that a long periodic needle does not cause false positives.  */
      93                 :            :   {
      94                 :          1 :     const char input[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
      95                 :            :                           "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
      96                 :            :                           "_C3_A7_20_EF_BF_BD");
      97                 :          1 :     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
      98                 :          1 :     const char *result = memmem (input, strlen (input), need, strlen (need));
      99         [ -  + ]:          1 :     ASSERT (result == NULL);
     100                 :            :   }
     101                 :            :   {
     102                 :          1 :     const char input[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
     103                 :            :                           "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
     104                 :            :                           "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
     105                 :            :                           "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
     106                 :          1 :     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
     107                 :          1 :     const char *result = memmem (input, strlen (input), need, strlen (need));
     108         [ -  + ]:          1 :     ASSERT (result == input + 115);
     109                 :            :   }
     110                 :            : 
     111                 :            :   /* Check that a very long haystack is handled quickly if the needle is
     112                 :            :      short and occurs near the beginning.  */
     113                 :            :   {
     114                 :          1 :     size_t repeat = 10000;
     115                 :          1 :     size_t m = 1000000;
     116                 :          1 :     const char *needle =
     117                 :            :       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
     118                 :            :       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
     119                 :          1 :     size_t n = strlen (needle);
     120                 :          1 :     char *haystack = (char *) malloc (m + 1);
     121         [ +  - ]:          1 :     if (haystack != NULL)
     122                 :            :       {
     123                 :          1 :         memset (haystack, 'A', m);
     124                 :          1 :         haystack[0] = 'B';
     125                 :            : 
     126         [ +  + ]:      10001 :         for (; repeat > 0; repeat--)
     127                 :            :           {
     128         [ -  + ]:      10000 :             ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
     129                 :            :           }
     130                 :            : 
     131                 :          1 :         free (haystack);
     132                 :            :       }
     133                 :            :   }
     134                 :            : 
     135                 :            :   /* Check that a very long needle is discarded quickly if the haystack is
     136                 :            :      short.  */
     137                 :            :   {
     138                 :          1 :     size_t repeat = 10000;
     139                 :          1 :     size_t m = 1000000;
     140                 :          1 :     const char *haystack =
     141                 :            :       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
     142                 :            :       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
     143                 :          1 :     size_t n = strlen (haystack);
     144                 :          1 :     char *needle = (char *) malloc (m + 1);
     145         [ +  - ]:          1 :     if (needle != NULL)
     146                 :            :       {
     147                 :          1 :         memset (needle, 'A', m);
     148                 :            : 
     149         [ +  + ]:      10001 :         for (; repeat > 0; repeat--)
     150                 :            :           {
     151         [ -  + ]:      10000 :             ASSERT (memmem (haystack, n, needle, m) == NULL);
     152                 :            :           }
     153                 :            : 
     154                 :          1 :         free (needle);
     155                 :            :       }
     156                 :            :   }
     157                 :            : 
     158                 :            :   /* Check that the asymptotic worst-case complexity is not quadratic.  */
     159                 :            :   {
     160                 :          1 :     size_t m = 1000000;
     161                 :          1 :     char *haystack = (char *) malloc (2 * m + 1);
     162                 :          1 :     char *needle = (char *) malloc (m + 1);
     163 [ +  - ][ +  - ]:          1 :     if (haystack != NULL && needle != NULL)
     164                 :            :       {
     165                 :            :         const char *result;
     166                 :            : 
     167                 :          1 :         memset (haystack, 'A', 2 * m);
     168                 :          1 :         haystack[2 * m] = 'B';
     169                 :            : 
     170                 :          1 :         memset (needle, 'A', m);
     171                 :          1 :         needle[m] = 'B';
     172                 :            : 
     173                 :          1 :         result = memmem (haystack, 2 * m + 1, needle, m + 1);
     174         [ -  + ]:          1 :         ASSERT (result == haystack + m);
     175                 :            :       }
     176                 :          1 :     free (needle);
     177                 :          1 :     free (haystack);
     178                 :            :   }
     179                 :            : 
     180                 :            :   /* Check that long needles not present in a haystack can be handled
     181                 :            :      with sublinear speed.  */
     182                 :            :   {
     183                 :          1 :     size_t repeat = 10000;
     184                 :          1 :     size_t m = 1000000;
     185                 :          1 :     size_t n = 1000;
     186                 :          1 :     char *haystack = (char *) malloc (m);
     187                 :          1 :     char *needle = (char *) malloc (n);
     188 [ +  - ][ +  - ]:          1 :     if (haystack != NULL && needle != NULL)
     189                 :            :       {
     190                 :            :         const char *result;
     191                 :            : 
     192                 :          1 :         memset (haystack, 'A', m);
     193                 :          1 :         memset (needle, 'B', n);
     194                 :            : 
     195         [ +  + ]:      10001 :         for (; repeat > 0; repeat--)
     196                 :            :           {
     197                 :      10000 :             result = memmem (haystack, m, needle, n);
     198         [ -  + ]:      10000 :             ASSERT (result == NULL);
     199                 :            :           }
     200                 :            :       }
     201                 :          1 :     free (haystack);
     202                 :          1 :     free (needle);
     203                 :            :   }
     204                 :            : 
     205                 :            :   {
     206                 :            :     /* Ensure that with a barely periodic "short" needle, memmem's
     207                 :            :        search does not mistakenly skip just past the match point.
     208                 :            :        This use of memmem would mistakenly return NULL before
     209                 :            :        gnulib v0.0-4927.  */
     210                 :          1 :     const char *haystack =
     211                 :            :       "\n"
     212                 :            :       "with_build_libsubdir\n"
     213                 :            :       "with_local_prefix\n"
     214                 :            :       "with_gxx_include_dir\n"
     215                 :            :       "with_cpp_install_dir\n"
     216                 :            :       "enable_generated_files_in_srcdir\n"
     217                 :            :       "with_gnu_ld\n"
     218                 :            :       "with_ld\n"
     219                 :            :       "with_demangler_in_ld\n"
     220                 :            :       "with_gnu_as\n"
     221                 :            :       "with_as\n"
     222                 :            :       "enable_largefile\n"
     223                 :            :       "enable_werror_always\n"
     224                 :            :       "enable_checking\n"
     225                 :            :       "enable_coverage\n"
     226                 :            :       "enable_gather_detailed_mem_stats\n"
     227                 :            :       "enable_build_with_cxx\n"
     228                 :            :       "with_stabs\n"
     229                 :            :       "enable_multilib\n"
     230                 :            :       "enable___cxa_atexit\n"
     231                 :            :       "enable_decimal_float\n"
     232                 :            :       "enable_fixed_point\n"
     233                 :            :       "enable_threads\n"
     234                 :            :       "enable_tls\n"
     235                 :            :       "enable_objc_gc\n"
     236                 :            :       "with_dwarf2\n"
     237                 :            :       "enable_shared\n"
     238                 :            :       "with_build_sysroot\n"
     239                 :            :       "with_sysroot\n"
     240                 :            :       "with_specs\n"
     241                 :            :       "with_pkgversion\n"
     242                 :            :       "with_bugurl\n"
     243                 :            :       "enable_languages\n"
     244                 :            :       "with_multilib_list\n";
     245                 :          1 :     const char *needle = "\n"
     246                 :            :       "with_gnu_ld\n";
     247                 :          1 :     const char* p = memmem (haystack, strlen (haystack),
     248                 :            :                             needle, strlen (needle));
     249         [ -  + ]:          1 :     ASSERT (p - haystack == 114);
     250                 :            :   }
     251                 :            : 
     252                 :            :   {
     253                 :            :     /* Same bug, shorter trigger.  */
     254                 :          1 :     const char *haystack = "..wi.d.";
     255                 :          1 :     const char *needle = ".d.";
     256                 :          1 :     const char* p = memmem (haystack, strlen (haystack),
     257                 :            :                             needle, strlen (needle));
     258         [ -  + ]:          1 :     ASSERT (p - haystack == 4);
     259                 :            :   }
     260                 :            : 
     261                 :            :   {
     262                 :            :     /* Like the above, but trigger the flaw in two_way_long_needle
     263                 :            :        by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
     264                 :            :        Rather than trying to find the right alignment manually, I've
     265                 :            :        arbitrarily chosen the following needle and template for the
     266                 :            :        haystack, and ensure that for each placement of the needle in
     267                 :            :        that haystack, memmem finds it.  */
     268                 :          1 :     const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
     269                 :          1 :     const char *h =
     270                 :            :       "\n"
     271                 :            :       "with_build_libsubdir\n"
     272                 :            :       "with_local_prefix\n"
     273                 :            :       "with_gxx_include_dir\n"
     274                 :            :       "with_cpp_install_dir\n"
     275                 :            :       "with_e_\n"
     276                 :            :       "..............................\n"
     277                 :            :       "with_FGHIJKLMNOPQRSTUVWXYZ\n"
     278                 :            :       "with_567890123456789\n"
     279                 :            :       "with_multilib_list\n";
     280                 :          1 :     size_t h_len = strlen (h);
     281                 :          1 :     char *haystack = malloc (h_len + 1);
     282                 :            :     size_t i;
     283         [ -  + ]:          1 :     ASSERT (haystack);
     284         [ +  + ]:        157 :     for (i = 0; i < h_len - strlen (needle); i++)
     285                 :            :       {
     286                 :            :         const char *p;
     287                 :        156 :         memcpy (haystack, h, h_len + 1);
     288                 :        156 :         memcpy (haystack + i, needle, strlen (needle) + 1);
     289                 :        156 :         p = memmem (haystack, strlen (haystack), needle, strlen (needle));
     290         [ -  + ]:        156 :         ASSERT (p);
     291         [ -  + ]:        156 :         ASSERT (p - haystack == i);
     292                 :            :       }
     293                 :            :   }
     294                 :            : 
     295                 :          1 :   return 0;
     296                 :            : }

Generated by: LCOV version 1.9