LXR syslinux/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
  14void *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