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 #include <string.h> 30 31 void* memmem(const void* void_haystack, size_t n, const void* void_needle, size_t m) { 32 const unsigned char* haystack = reinterpret_cast<const unsigned char*>(void_haystack); 33 const unsigned char* needle = reinterpret_cast<const unsigned char*>(void_needle); 34 35 if (n < m) return nullptr; 36 37 if (m == 0) return const_cast<void*>(void_haystack); 38 if (m == 1) return const_cast<void*>(memchr(haystack, needle[0], n)); 39 40 // This uses the "Not So Naive" algorithm, a very simple but usually effective algorithm. 41 // http://www-igm.univ-mlv.fr/~lecroq/string/ 42 const unsigned char* y = haystack; 43 const unsigned char* x = needle; 44 size_t j = 0; 45 size_t k = 1, l = 2; 46 47 if (x[0] == x[1]) { 48 k = 2; 49 l = 1; 50 } 51 while (j <= n-m) { 52 if (x[1] != y[j+1]) { 53 j += k; 54 } else { 55 if (!memcmp(x+2, y+j+2, m-2) && x[0] == y[j]) return const_cast<unsigned char*>(&y[j]); 56 j += l; 57 } 58 } 59 return nullptr; 60 } 61
