From e3adb96fc71c48e1d3e638e7e1afadcd3ac0d840 Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Sat, 5 Jan 2008 04:47:24 -0700 Subject: [PATCH] Avoid quadratic system memmem. * m4/memmem.m4 (gl_FUNC_MEMMEM): Check for quadratic memmem. Reported by Ralf Wildenhues. Signed-off-by: Eric Blake --- ChangeLog | 4 ++++ m4/memmem.m4 | 29 ++++++++++++++++++++++++----- 2 files changed, 28 insertions(+), 5 deletions(-) diff --git a/ChangeLog b/ChangeLog index b4be78eca..bdc357aca 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,9 @@ 2008-01-05 Eric Blake + Avoid quadratic system memmem. + * m4/memmem.m4 (gl_FUNC_MEMMEM): Check for quadratic memmem. + Reported by Ralf Wildenhues. + Fix memmem test for mingw. * modules/memmem-tests (configure.ac): Check for alarm. * tests/test-memmem.c (main): Avoid alarm on platforms that lack diff --git a/m4/memmem.m4 b/m4/memmem.m4 index a529af3be..9767354ad 100644 --- a/m4/memmem.m4 +++ b/m4/memmem.m4 @@ -1,5 +1,5 @@ -# memmem.m4 serial 6 -dnl Copyright (C) 2002, 2003, 2004, 2007 Free Software Foundation, Inc. +# memmem.m4 serial 7 +dnl Copyright (C) 2002, 2003, 2004, 2007, 2008 Free Software Foundation, Inc. dnl This file is free software; the Free Software Foundation dnl gives unlimited permission to copy and/or distribute it, dnl with or without modifications, as long as this notice is preserved. @@ -15,9 +15,28 @@ AC_DEFUN([gl_FUNC_MEMMEM], if test $ac_cv_have_decl_memmem = no; then HAVE_DECL_MEMMEM=0 else - AC_CACHE_CHECK([whether memmem works], [gl_cv_func_memmem_works], - [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include ], - [return !memmem ("a", 1, NULL, 0);])], + AC_CACHE_CHECK([whether memmem works in linear time], + [gl_cv_func_memmem_works], + [AC_RUN_IFELSE([AC_LANG_PROGRAM([ +#include /* for memmem */ +#include /* for malloc */ +#include /* for alarm */ +], [[size_t m = 1000000; + char *haystack = (char *) malloc (2 * m + 1); + char *needle = (char *) malloc (m + 1); + void *result = 0; + /* Failure to compile this test due to missing alarm is okay, + since all such platforms (mingw) also lack memmem. */ + alarm (5); + if (haystack && needle) + { + memset (haystack, 'A', 2 * m); + haystack[2 * m] = 'B'; + memset (needle, 'A', m); + needle[m] = 'B'; + result = memmem (haystack, 2 * m + 1, needle, m + 1); + } + return !result || !memmem ("a", 1, 0, 0);]])], [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no], [dnl pessimistically assume the worst, since even glibc 2.6.1 dnl has quadratic complexity in its memmem -- 2.11.0