klibc/klibc/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         return NULL;
  52 }