Home | History | Annotate | Download | only in lib
      1 /*
      2  * memmem.c
      3  *
      4  * Find a byte string inside a longer byte string
      5  *
      6  * This uses the "Not So Naive" algorithm, a very simple but
      7  * usually effective algorithm, see:
      8  *
      9  * http://www-igm.univ-mlv.fr/~lecroq/string/
     10  */
     11 
     12 #include <string.h>
     13 
     14 void *memmem(const void *haystack, size_t n, const void *needle, size_t m)
     15 {
     16     const unsigned char *y = (const unsigned char *)haystack;
     17     const unsigned char *x = (const unsigned char *)needle;
     18 
     19     size_t j, k, l;
     20 
     21     if (m > n || !m || !n)
     22         return NULL;
     23 
     24     if (1 != m) {
     25         if (x[0] == x[1]) {
     26             k = 2;
     27             l = 1;
     28         } else {
     29             k = 1;
     30             l = 2;
     31         }
     32 
     33         j = 0;
     34         while (j <= n - m) {
     35             if (x[1] != y[j + 1]) {
     36                 j += k;
     37             } else {
     38                 if (!memcmp(x + 2, y + j + 2, m - 2)
     39                     && x[0] == y[j])
     40                     return (void *)&y[j];
     41                 j += l;
     42             }
     43         }
     44     } else {
     45         do {
     46             if (*y == *x)
     47                 return (void *)y;
     48             y++;
     49         } while (--n);
     50     }
     51 
     52     return NULL;
     53 }
     54