com32/lib/memmem.c

   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 }