TOTO

#include <string.h>
#include <limits.h>

static inline ssize_t max(ssize_t a, ssize_t b) { return a > b ? a : b; }

/* This helper function checks, whether the last "portion" bytes
 * of "needle" (which is "nlen" bytes long) exist within the "needle"
 * at offset "offset" (counted from the end of the string),
 * and whether the character preceding "offset" is not a match.
 * Notice that the range being checked may reach beyond the
 * beginning of the string. Such range is ignored.
 */
static inline int boyermoore_needlematch(
    const unsigned char* needle, size_t nlen,
    size_t portion, size_t offset)
{
    ssize_t virtual_begin = nlen - offset - portion;
    ssize_t ignore = 0;

    if (virtual_begin < 0) {
        ignore = -virtual_begin;
        virtual_begin = 0;
    }
    if (virtual_begin > 0 && needle[virtual_begin - 1] == needle[nlen-portion - 1])
        return 0;
    return memcmp(
        needle + nlen - portion + ignore,
        needle + virtual_begin,
        portion - ignore) == 0;
}

/* Returns a pointer to the first occurrence of "needle"
 * within "haystack", or NULL if not found.
 */
const unsigned char* memmem_boyermoore(
    const unsigned char* haystack, size_t hlen,
    const unsigned char* needle,   size_t nlen)
{
    size_t *skip; /* Array of shifts with self-substring match check */
    size_t a, hpos;
    ssize_t occ[UCHAR_MAX + 1]; /* Array of last occurrence of each character */

    if (nlen > hlen || nlen <= 0 || !haystack || !needle)
        return NULL;

    /* Preprocess #1: init occ[] */
    /* Initialize the table to default value */
    for (a = UCHAR_MAX + 1; --a >= 0)
        occ[a] = -1;
    /* Then populate it with the analysis of the needle */
    /* But ignoring the last letter */
    for (a = 0 ; a < nlen - 1 ; a++)
        occ[needle[a]] = a;

    /* Preprocess #2: init skip[] */
    /* Note: This step could be made a lot faster.
     * A simple implementation is shown here. */
    skip = (size_t *) malloc(nlen * sizeof(size_t));
    /* We should check here if skip is NULL (allocation failed) ! */
    for (a = 0; a < nlen; ++a) {
        size_t value = 0;
        while (value < nlen && !boyermoore_needlematch(needle, nlen, a, value))
            ++value;
        skip[nlen - a - 1] = value;
    }

    /* Search */
    for (hpos = 0; hpos <= hlen - nlen; ) {
        size_t npos = nlen - 1;
        while (needle[npos] == haystack[npos + hpos]) {
            if (npos == 0) {
                free(skip);
                return haystack + hpos;
            }
            --npos;
        }
        hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
    }
    free(skip);
    return NULL;
}