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 35 void *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
