513 /* Cygwin's newlib does not have strcasestr() */

   514 /* The author of the code before the endif is

   515  *    Jeffrey Stedfast <fejj@ximian.com>

   516  * and this code is reusable in compliance with the GPL v2. -- somian */

   517 

   518 #if !defined(HAVE_STRCASESTR)

   519 

   520 #  define lowercase(c)  (isupper ((int) (c)) ? tolower ((int) (c)) : (int) (c))

   521 #  define bm_index(c, icase)      ((icase) ? lowercase (c) : (int) (c))

   522 #  define bm_equal(c1, c2, icase) ((icase) ? lowercase (c1) == lowercase (c2) : (c1) == (c2))

   523 

   524 /* FIXME: this is just a guess... should really do some performace tests to get an accurate measure */

   525 #  define bm_optimal(hlen, nlen)  (((hlen) ? (hlen) > 20 : 1) && (nlen) > 10 ? 1 : 0)

   526 

   527 static unsigned char *

   528 __boyer_moore (const unsigned char *haystack, size_t haystacklen,

   529                const unsigned char *needle, size_t needlelen, int icase)

   530 {

   531   register unsigned char *hc_ptr, *nc_ptr;

   532   unsigned char *he_ptr, *ne_ptr, *h_ptr;

   533   size_t skiptable[256], n;

   534   register int i;

   535 

   536 #ifdef BOYER_MOORE_CHECKS

   537   /* we don't need to do these checks since memmem/strstr/etc do it already */

   538   /* if the haystack is shorter than the needle then we can't possibly match */

   539   if (haystacklen < needlelen)

   540     return NULL;

   541 

   542   /* instant match if the pattern buffer is 0-length */

   543   if (needlelen == 0)

   544     return (unsigned char *) haystack;

   545 #endif /* BOYER_MOORE_CHECKS */

   546 

   547   /* set a pointer at the end of each string */

   548   ne_ptr = (unsigned char *) needle + needlelen - 1;

   549   he_ptr = (unsigned char *) haystack + haystacklen - 1;

   550 

   551   /* create our skip table */

   552   for (i = 0; i < 256; i++)

   553     skiptable[i] = needlelen;

   554   for (nc_ptr = (unsigned char *) needle; nc_ptr < ne_ptr; nc_ptr++)

   555     skiptable[bm_index (*nc_ptr, icase)] = (size_t) (ne_ptr - nc_ptr);

   556 

   557   h_ptr = (unsigned char *) haystack;

   558   while (haystacklen >= needlelen) {

   559     hc_ptr = h_ptr + needlelen - 1;   /* set the haystack compare pointer */

   560     nc_ptr = ne_ptr;                  /* set the needle compare pointer */

   561 

   562     /* work our way backwards till they don't match */

   563     for (i = 0; nc_ptr > (unsigned char *) needle; nc_ptr--, hc_ptr--, i++)

   564       if (!bm_equal (*nc_ptr, *hc_ptr, icase))

   565         break;

   566 

   567     if (!bm_equal (*nc_ptr, *hc_ptr, icase)) {

   568       n = skiptable[bm_index (*hc_ptr, icase)];

   569       if (n == needlelen && i)

   570         if (bm_equal (*ne_ptr, ((unsigned char *) needle)[0], icase))

   571           n--;

   572       h_ptr += n;

   573       haystacklen -= n;

   574     } else

   575       return (unsigned char *) h_ptr;

   576   }

   577 

   578   return NULL;

   579 }

   580 

   581 /*

   582  * strcasestr:

   583  * @haystack: string to search

   584  * @needle: substring to search for

   585  *

   586  * Finds the first occurence of the substring @needle within the

   587  * string @haystack ignoring case.

   588  *

   589  * Returns a pointer to the beginning of the substring match within

   590  * @haystack, or NULL if the substring is not found.

   591  **/

   592 char *

   593 strcasestr (const char *haystack, const char *needle)

   594 {

   595   register unsigned char *h, *n, *hc, *nc;

   596   size_t needlelen;

   597 

   598   needlelen = strlen (needle);

   599 

   600   if (needlelen == 0) {

   601     return (char *) haystack;

   602   } else if (bm_optimal (0, needlelen)) {

   603     return (char *) __boyer_moore ((const unsigned char *) haystack,

   604                                    strlen (haystack),

   605                                    (const unsigned char *) needle,

   606                                    needlelen, 1);

   607   }

   608 

   609   h = (unsigned char *) haystack;

   610   n = (unsigned char *) needle;

   611 

   612   while (*(h + needlelen - 1)) {

   613     if (lowercase (*h) == lowercase (*n)) {

   614       for (hc = h + 1, nc = n + 1; *hc && *nc; hc++, nc++)

   615         if (lowercase (*hc) != lowercase (*nc))

   616           break;

   617 

   618       if (!*nc)

   619         return (char *) h;

   620     }

   621     h++;

   622   }

   623   return NULL;

   624 }

   625 #endif /* !HAVE_STRCASESTR */

   626