lib/mbscasestr.c

   1 /* Case-insensitive searching in a string.
   2    Copyright (C) 2005-2007 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2005.
   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 /* Specification.  */
  21 #include <string.h>
  22
  23 #include <ctype.h>
  24 #include <stdbool.h>
  25 #include <stddef.h>  /* for NULL, in case a nonstandard string.h lacks it */
  26
  27 #include "malloca.h"
  28 #if HAVE_MBRTOWC
  29 # include "mbuiter.h"
  30 #endif
  31
  32 #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
  33
  34 /* Knuth-Morris-Pratt algorithm.
  35    See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  36    Return a boolean indicating success.  */
  37
  38 static bool
  39 knuth_morris_pratt_unibyte (const char *haystack, const char *needle,
  40                             const char **resultp)
  41 {
  42   size_t m = strlen (needle);
  43
  44   /* Allocate the table.  */
  45   size_t *table = (size_t *) nmalloca (m, sizeof (size_t));
  46   if (table == NULL)
  47     return false;
  48   /* Fill the table.
  49      For 0 < i < m:
  50        0 < table[i] <= i is defined such that
  51        forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
  52        and table[i] is as large as possible with this property.
  53      This implies:
  54      1) For 0 < i < m:
  55           If table[i] < i,
  56           needle[table[i]..i-1] = needle[0..i-1-table[i]].
  57      2) For 0 < i < m:
  58           rhaystack[0..i-1] == needle[0..i-1]
  59           and exists h, i <= h < m: rhaystack[h] != needle[h]
  60           implies
  61           forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
  62      table[0] remains uninitialized.  */
  63   {
  64     size_t i, j;
  65
  66     /* i = 1: Nothing to verify for x = 0.  */
  67     table[1] = 1;
  68     j = 0;
  69
  70     for (i = 2; i < m; i++)
  71       {
  72         /* Here: j = i-1 - table[i-1].
  73            The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
  74            for x < table[i-1], by induction.
  75            Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
  76         unsigned char b = TOLOWER ((unsigned char) needle[i - 1]);
  77
  78         for (;;)
  79           {
  80             /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
  81                is known to hold for x < i-1-j.
  82                Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
  83             if (b == TOLOWER ((unsigned char) needle[j]))
  84               {
  85                 /* Set table[i] := i-1-j.  */
  86                 table[i] = i - ++j;
  87                 break;
  88               }
  89             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
  90                for x = i-1-j, because
  91                  needle[i-1] != needle[j] = needle[i-1-x].  */
  92             if (j == 0)
  93               {
  94                 /* The inequality holds for all possible x.  */
  95                 table[i] = i;
  96                 break;
  97               }
  98             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
  99                for i-1-j < x < i-1-j+table[j], because for these x:
 100                  needle[x..i-2]
 101                  = needle[x-(i-1-j)..j-1]
 102                  != needle[0..j-1-(x-(i-1-j))]  (by definition of table[j])
 103                     = needle[0..i-2-x],
 104                hence needle[x..i-1] != needle[0..i-1-x].
 105                Furthermore
 106                  needle[i-1-j+table[j]..i-2]
 107                  = needle[table[j]..j-1]
 108                  = needle[0..j-1-table[j]]  (by definition of table[j]).  */
 109             j = j - table[j];
 110           }
 111         /* Here: j = i - table[i].  */
 112       }
 113   }
 114
 115   /* Search, using the table to accelerate the processing.  */
 116   {
 117     size_t j;
 118     const char *rhaystack;
 119     const char *phaystack;
 120
 121     *resultp = NULL;
 122     j = 0;
 123     rhaystack = haystack;
 124     phaystack = haystack;
 125     /* Invariant: phaystack = rhaystack + j.  */
 126     while (*phaystack != '\0')
 127       if (TOLOWER ((unsigned char) needle[j])
 128           == TOLOWER ((unsigned char) *phaystack))
 129         {
 130           j++;
 131           phaystack++;
 132           if (j == m)
 133             {
 134               /* The entire needle has been found.  */
 135               *resultp = rhaystack;
 136               break;
 137             }
 138         }
 139       else if (j > 0)
 140         {
 141           /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 142           rhaystack += table[j];
 143           j -= table[j];
 144         }
 145       else
 146         {
 147           /* Found a mismatch at needle[0] already.  */
 148           rhaystack++;
 149           phaystack++;
 150         }
 151   }
 152
 153   freea (table);
 154   return true;
 155 }
 156
 157 #if HAVE_MBRTOWC
 158 static bool
 159 knuth_morris_pratt_multibyte (const char *haystack, const char *needle,
 160                               const char **resultp)
 161 {
 162   size_t m = mbslen (needle);
 163   mbchar_t *needle_mbchars;
 164   size_t *table;
 165
 166   /* Allocate room for needle_mbchars and the table.  */
 167   char *memory = (char *) nmalloca (m, sizeof (mbchar_t) + sizeof (size_t));
 168   if (memory == NULL)
 169     return false;
 170   needle_mbchars = (mbchar_t *) memory;
 171   table = (size_t *) (memory + m * sizeof (mbchar_t));
 172
 173   /* Fill needle_mbchars.  */
 174   {
 175     mbui_iterator_t iter;
 176     size_t j;
 177
 178     j = 0;
 179     for (mbui_init (iter, needle); mbui_avail (iter); mbui_advance (iter), j++)
 180       {
 181         mb_copy (&needle_mbchars[j], &mbui_cur (iter));
 182         if (needle_mbchars[j].wc_valid)
 183           needle_mbchars[j].wc = towlower (needle_mbchars[j].wc);
 184       }
 185   }
 186
 187   /* Fill the table.
 188      For 0 < i < m:
 189        0 < table[i] <= i is defined such that
 190        forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
 191        and table[i] is as large as possible with this property.
 192      This implies:
 193      1) For 0 < i < m:
 194           If table[i] < i,
 195           needle[table[i]..i-1] = needle[0..i-1-table[i]].
 196      2) For 0 < i < m:
 197           rhaystack[0..i-1] == needle[0..i-1]
 198           and exists h, i <= h < m: rhaystack[h] != needle[h]
 199           implies
 200           forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
 201      table[0] remains uninitialized.  */
 202   {
 203     size_t i, j;
 204
 205     /* i = 1: Nothing to verify for x = 0.  */
 206     table[1] = 1;
 207     j = 0;
 208
 209     for (i = 2; i < m; i++)
 210       {
 211         /* Here: j = i-1 - table[i-1].
 212            The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
 213            for x < table[i-1], by induction.
 214            Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
 215         mbchar_t *b = &needle_mbchars[i - 1];
 216
 217         for (;;)
 218           {
 219             /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
 220                is known to hold for x < i-1-j.
 221                Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
 222             if (mb_equal (*b, needle_mbchars[j]))
 223               {
 224                 /* Set table[i] := i-1-j.  */
 225                 table[i] = i - ++j;
 226                 break;
 227               }
 228             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
 229                for x = i-1-j, because
 230                  needle[i-1] != needle[j] = needle[i-1-x].  */
 231             if (j == 0)
 232               {
 233                 /* The inequality holds for all possible x.  */
 234                 table[i] = i;
 235                 break;
 236               }
 237             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
 238                for i-1-j < x < i-1-j+table[j], because for these x:
 239                  needle[x..i-2]
 240                  = needle[x-(i-1-j)..j-1]
 241                  != needle[0..j-1-(x-(i-1-j))]  (by definition of table[j])
 242                     = needle[0..i-2-x],
 243                hence needle[x..i-1] != needle[0..i-1-x].
 244                Furthermore
 245                  needle[i-1-j+table[j]..i-2]
 246                  = needle[table[j]..j-1]
 247                  = needle[0..j-1-table[j]]  (by definition of table[j]).  */
 248             j = j - table[j];
 249           }
 250         /* Here: j = i - table[i].  */
 251       }
 252   }
 253
 254   /* Search, using the table to accelerate the processing.  */
 255   {
 256     size_t j;
 257     mbui_iterator_t rhaystack;
 258     mbui_iterator_t phaystack;
 259
 260     *resultp = NULL;
 261     j = 0;
 262     mbui_init (rhaystack, haystack);
 263     mbui_init (phaystack, haystack);
 264     /* Invariant: phaystack = rhaystack + j.  */
 265     while (mbui_avail (phaystack))
 266       {
 267         mbchar_t c;
 268
 269         mb_copy (&c, &mbui_cur (phaystack));
 270         if (c.wc_valid)
 271           c.wc = towlower (c.wc);
 272         if (mb_equal (needle_mbchars[j], c))
 273           {
 274             j++;
 275             mbui_advance (phaystack);
 276             if (j == m)
 277               {
 278                 /* The entire needle has been found.  */
 279                 *resultp = mbui_cur_ptr (rhaystack);
 280                 break;
 281               }
 282           }
 283         else if (j > 0)
 284           {
 285             /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 286             size_t count = table[j];
 287             j -= count;
 288             for (; count > 0; count--)
 289               {
 290                 if (!mbui_avail (rhaystack))
 291                   abort ();
 292                 mbui_advance (rhaystack);
 293               }
 294           }
 295         else
 296           {
 297             /* Found a mismatch at needle[0] already.  */
 298             if (!mbui_avail (rhaystack))
 299               abort ();
 300             mbui_advance (rhaystack);
 301             mbui_advance (phaystack);
 302           }
 303       }
 304   }
 305
 306   freea (memory);
 307   return true;
 308 }
 309 #endif
 310
 311 /* Find the first occurrence of the character string NEEDLE in the character
 312    string HAYSTACK, using case-insensitive comparison.
 313    Note: This function may, in multibyte locales, return success even if
 314    strlen (haystack) < strlen (needle) !  */
 315 char *
 316 mbscasestr (const char *haystack, const char *needle)
 317 {
 318   /* Be careful not to look at the entire extent of haystack or needle
 319      until needed.  This is useful because of these two cases:
 320        - haystack may be very long, and a match of needle found early,
 321        - needle may be very long, and not even a short initial segment of
 322          needle may be found in haystack.  */
 323 #if HAVE_MBRTOWC
 324   if (MB_CUR_MAX > 1)
 325     {
 326       mbui_iterator_t iter_needle;
 327
 328       mbui_init (iter_needle, needle);
 329       if (mbui_avail (iter_needle))
 330         {
 331           /* Minimizing the worst-case complexity:
 332              Let n = mbslen(haystack), m = mbslen(needle).
 333              The naïve algorithm is O(n*m) worst-case.
 334              The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 335              memory allocation.
 336              To achieve linear complexity and yet amortize the cost of the
 337              memory allocation, we activate the Knuth-Morris-Pratt algorithm
 338              only once the naïve algorithm has already run for some time; more
 339              precisely, when
 340                - the outer loop count is >= 10,
 341                - the average number of comparisons per outer loop is >= 5,
 342                - the total number of comparisons is >= m.
 343              But we try it only once.  If the memory allocation attempt failed,
 344              we don't retry it.  */
 345           bool try_kmp = true;
 346           size_t outer_loop_count = 0;
 347           size_t comparison_count = 0;
 348           size_t last_ccount = 0;                  /* last comparison count */
 349           mbui_iterator_t iter_needle_last_ccount; /* = needle + last_ccount */
 350
 351           mbchar_t b;
 352           mbui_iterator_t iter_haystack;
 353
 354           mbui_init (iter_needle_last_ccount, needle);
 355
 356           mb_copy (&b, &mbui_cur (iter_needle));
 357           if (b.wc_valid)
 358             b.wc = towlower (b.wc);
 359
 360           mbui_init (iter_haystack, haystack);
 361           for (;; mbui_advance (iter_haystack))
 362             {
 363               mbchar_t c;
 364
 365               if (!mbui_avail (iter_haystack))
 366                 /* No match.  */
 367                 return NULL;
 368
 369               /* See whether it's advisable to use an asymptotically faster
 370                  algorithm.  */
 371               if (try_kmp
 372                   && outer_loop_count >= 10
 373                   && comparison_count >= 5 * outer_loop_count)
 374                 {
 375                   /* See if needle + comparison_count now reaches the end of
 376                      needle.  */
 377                   size_t count = comparison_count - last_ccount;
 378                   for (;
 379                        count > 0 && mbui_avail (iter_needle_last_ccount);
 380                        count--)
 381                     mbui_advance (iter_needle_last_ccount);
 382                   last_ccount = comparison_count;
 383                   if (!mbui_avail (iter_needle_last_ccount))
 384                     {
 385                       /* Try the Knuth-Morris-Pratt algorithm.  */
 386                       const char *result;
 387                       bool success =
 388                         knuth_morris_pratt_multibyte (haystack, needle,
 389                                                       &result);
 390                       if (success)
 391                         return (char *) result;
 392                       try_kmp = false;
 393                     }
 394                 }
 395
 396               outer_loop_count++;
 397               comparison_count++;
 398               mb_copy (&c, &mbui_cur (iter_haystack));
 399               if (c.wc_valid)
 400                 c.wc = towlower (c.wc);
 401               if (mb_equal (c, b))
 402                 /* The first character matches.  */
 403                 {
 404                   mbui_iterator_t rhaystack;
 405                   mbui_iterator_t rneedle;
 406
 407                   memcpy (&rhaystack, &iter_haystack, sizeof (mbui_iterator_t));
 408                   mbui_advance (rhaystack);
 409
 410                   mbui_init (rneedle, needle);
 411                   if (!mbui_avail (rneedle))
 412                     abort ();
 413                   mbui_advance (rneedle);
 414
 415                   for (;; mbui_advance (rhaystack), mbui_advance (rneedle))
 416                     {
 417                       if (!mbui_avail (rneedle))
 418                         /* Found a match.  */
 419                         return (char *) mbui_cur_ptr (iter_haystack);
 420                       if (!mbui_avail (rhaystack))
 421                         /* No match.  */
 422                         return NULL;
 423                       comparison_count++;
 424                       if (!mb_caseequal (mbui_cur (rhaystack),
 425                                          mbui_cur (rneedle)))
 426                         /* Nothing in this round.  */
 427                         break;
 428                     }
 429                 }
 430             }
 431         }
 432       else
 433         return (char *) haystack;
 434     }
 435   else
 436 #endif
 437     {
 438       if (*needle != '\0')
 439         {
 440           /* Minimizing the worst-case complexity:
 441              Let n = strlen(haystack), m = strlen(needle).
 442              The naïve algorithm is O(n*m) worst-case.
 443              The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 444              memory allocation.
 445              To achieve linear complexity and yet amortize the cost of the
 446              memory allocation, we activate the Knuth-Morris-Pratt algorithm
 447              only once the naïve algorithm has already run for some time; more
 448              precisely, when
 449                - the outer loop count is >= 10,
 450                - the average number of comparisons per outer loop is >= 5,
 451                - the total number of comparisons is >= m.
 452              But we try it only once.  If the memory allocation attempt failed,
 453              we don't retry it.  */
 454           bool try_kmp = true;
 455           size_t outer_loop_count = 0;
 456           size_t comparison_count = 0;
 457           size_t last_ccount = 0;                  /* last comparison count */
 458           const char *needle_last_ccount = needle; /* = needle + last_ccount */
 459
 460           /* Speed up the following searches of needle by caching its first
 461              character.  */
 462           unsigned char b = TOLOWER ((unsigned char) *needle);
 463
 464           needle++;
 465           for (;; haystack++)
 466             {
 467               if (*haystack == '\0')
 468                 /* No match.  */
 469                 return NULL;
 470
 471               /* See whether it's advisable to use an asymptotically faster
 472                  algorithm.  */
 473               if (try_kmp
 474                   && outer_loop_count >= 10
 475                   && comparison_count >= 5 * outer_loop_count)
 476                 {
 477                   /* See if needle + comparison_count now reaches the end of
 478                      needle.  */
 479                   if (needle_last_ccount != NULL)
 480                     {
 481                       needle_last_ccount +=
 482                         strnlen (needle_last_ccount,
 483                                  comparison_count - last_ccount);
 484                       if (*needle_last_ccount == '\0')
 485                         needle_last_ccount = NULL;
 486                       last_ccount = comparison_count;
 487                     }
 488                   if (needle_last_ccount == NULL)
 489                     {
 490                       /* Try the Knuth-Morris-Pratt algorithm.  */
 491                       const char *result;
 492                       bool success =
 493                         knuth_morris_pratt_unibyte (haystack, needle - 1,
 494                                                     &result);
 495                       if (success)
 496                         return (char *) result;
 497                       try_kmp = false;
 498                     }
 499                 }
 500
 501               outer_loop_count++;
 502               comparison_count++;
 503               if (TOLOWER ((unsigned char) *haystack) == b)
 504                 /* The first character matches.  */
 505                 {
 506                   const char *rhaystack = haystack + 1;
 507                   const char *rneedle = needle;
 508
 509                   for (;; rhaystack++, rneedle++)
 510                     {
 511                       if (*rneedle == '\0')
 512                         /* Found a match.  */
 513                         return (char *) haystack;
 514                       if (*rhaystack == '\0')
 515                         /* No match.  */
 516                         return NULL;
 517                       comparison_count++;
 518                       if (TOLOWER ((unsigned char) *rhaystack)
 519                           != TOLOWER ((unsigned char) *rneedle))
 520                         /* Nothing in this round.  */
 521                         break;
 522                     }
 523                 }
 524             }
 525         }
 526       else
 527         return (char *) haystack;
 528     }
 529 }