1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *  * Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 *  * Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in
12 *    the documentation and/or other materials provided with the
13 *    distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28/*
29 * This uses the "Not So Naive" algorithm, a very simple but
30 * usually effective algorithm, see:
31 * http://www-igm.univ-mlv.fr/~lecroq/string/
32 */
33#include <string.h>
34
35void *memmem(const void *haystack, size_t n, const void *needle, size_t m)
36{
37    if (m > n || !m || !n)
38        return NULL;
39
40    if (__builtin_expect((m > 1), 1)) {
41        const unsigned char*  y = (const unsigned char*) haystack;
42        const unsigned char*  x = (const unsigned char*) needle;
43        size_t                j = 0;
44        size_t                k = 1, l = 2;
45
46        if (x[0] == x[1]) {
47            k = 2;
48            l = 1;
49        }
50        while (j <= n-m) {
51            if (x[1] != y[j+1]) {
52                j += k;
53            } else {
54                if (!memcmp(x+2, y+j+2, m-2) && x[0] == y[j])
55                    return (void*) &y[j];
56                j += l;
57            }
58        }
59    } else {
60        /* degenerate case */
61        return memchr(haystack, ((unsigned char*)needle)[0], n);
62    }
63    return NULL;
64}
65