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 )
  22     return NULL;
  23
  24   if ( x[0] == x[1] ) {
  25     k = 2;
  26     l = 1;
  27   } else {
  28     k = 1;
  29     l = 2;
  30   }
  31
  32   j = 0;
  33   while ( j <= n-m ) {
  34     if (x[1] != y[j+1]) {
  35       j += k;
  36     } else {
  37       if ( !memcmp(x+2, y+j+2, m-2) && x[0] == y[j] )
  38         return (void *)&y[j];
  39       j += l;
  40     }
  41   }
  42
  43   return NULL;
  44 }