[PATCH 2/2] Port strnstr.c to newlib.

[PATCH 2/2] Port strnstr.c to newlib.

[Sichen Zhao]

---
 newlib/libc/string/Makefile.am | 1 +
 newlib/libc/string/strnstr.c   | 2 +-
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/newlib/libc/string/Makefile.am b/newlib/libc/string/Makefile.am
index e62f286..f8bd41e 100644
--- a/newlib/libc/string/Makefile.am
+++ b/newlib/libc/string/Makefile.am
@@ -40,6 +40,7 @@ GENERAL_SOURCES = \
 	strncmp.c \
 	strncpy.c \
 	strnlen.c \
+	strnstr.c \
 	strpbrk.c \
 	strrchr.c \
 	strsep.c \
diff --git a/newlib/libc/string/strnstr.c b/newlib/libc/string/strnstr.c
index 4de757d..da5e5bd 100644
--- a/newlib/libc/string/strnstr.c
+++ b/newlib/libc/string/strnstr.c
@@ -35,7 +35,7 @@
 static char sccsid[] = "@(#)strstr.c	8.1 (Berkeley) 6/4/93";
 #endif /* LIBC_SCCS and not lint */
 #include <sys/cdefs.h>
-__FBSDID("$FreeBSD$");
+__FBSDID("$FreeBSD: head/lib/libc/string/strnstr.c 251069 2013-05-28 20:57:40Z emaste $");
 
 #include <string.h>
 
-- 
2.7.4

[PATCH 1/2] Import strnstr.c from FreeBSD.

[Sichen Zhao]

---
 newlib/libc/string/strnstr.c | 65 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 65 insertions(+)
 create mode 100644 newlib/libc/string/strnstr.c

diff --git a/newlib/libc/string/strnstr.c b/newlib/libc/string/strnstr.c
new file mode 100644
index 0000000..4de757d
--- /dev/null
+++ b/newlib/libc/string/strnstr.c
@@ -0,0 +1,65 @@
+/*-
+ * Copyright (c) 2001 Mike Barcroft <mike@FreeBSD.org>
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Chris Torek.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)strstr.c	8.1 (Berkeley) 6/4/93";
+#endif /* LIBC_SCCS and not lint */
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <string.h>
+
+/*
+ * Find the first occurrence of find in s, where the search is limited to the
+ * first slen characters of s.
+ */
+char *
+strnstr(const char *s, const char *find, size_t slen)
+{
+	char c, sc;
+	size_t len;
+
+	if ((c = *find++) != '\0') {
+		len = strlen(find);
+		do {
+			do {
+				if (slen-- < 1 || (sc = *s++) == '\0')
+					return (NULL);
+			} while (sc != c);
+			if (len > slen)
+				return (NULL);
+		} while (strncmp(s, find, len) != 0);
+		s--;
+	}
+	return ((char *)s);
+}
-- 
2.7.4

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Corinna Vinschen]

[-- Attachment #1: Type: text/plain, Size: 254 bytes --]

Hi Sichen,

On Aug 24 10:14, Sichen Zhao wrote:
> ---
>  newlib/libc/string/strnstr.c | 65 +++++++++++++++++++++++++++++++++++++++++++

Isn't there a header patch missing?


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Sichen Zhao]

> Hi Sichen,
>
> On Aug 24 10:14, Sichen Zhao wrote:
>> ---
>>   newlib/libc/string/strnstr.c | 65 +++++++++++++++++++++++++++++++++++++++++++
> Isn't there a header patch missing?
You mean the string.h patch? So i need add the prototype declaration 
about strnstr.c in string.h, just something like:
#if __POSIX_VISIBLE >= 200809
size_t     _EXFUN(strnlen,(const char *, size_t));
#endif
#if __BSD_VISIBLE
char     *_EXFUN(strsep,(char **, const char *));
#endif

right?
>
>
> Thanks,
> Corinna
>

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Eric Blake]

[-- Attachment #1.1: Type: text/plain, Size: 1473 bytes --]

On 08/23/2017 09:14 PM, Sichen Zhao wrote:

> +/*
> + * Find the first occurrence of find in s, where the search is limited to the
> + * first slen characters of s.
> + */
> +char *
> +strnstr(const char *s, const char *find, size_t slen)
> +{
> +	char c, sc;
> +	size_t len;
> +
> +	if ((c = *find++) != '\0') {
> +		len = strlen(find);
> +		do {
> +			do {
> +				if (slen-- < 1 || (sc = *s++) == '\0')
> +					return (NULL);
> +			} while (sc != c);
> +			if (len > slen)
> +				return (NULL);
> +		} while (strncmp(s, find, len) != 0);
> +		s--;
> +	}

This is a poor algorithm (O(n^2) because it is is calling an O(n)
strncmp() over every byte of haystack).  It also calls strlen() instead
of strnlen(), which (when the needle is bigger than the haystack, and
therefore the function must return NULL) is wasted effort.

Instead of copying the poor BSD implementation, why not just open-code
it yourself to take advantage of our O(n) memmem(), which has already
been optimized to take advantage of a better algorithm that is not
quadratic?

char *
strnstr(const char *haystack, const char *needle, size_t haystack_len)
{
  size_t needle_len = strnlen(needle, slen);
  if (needle_len < slen || !needle[needle_len])
    return memmem(haystack, haystack_len, needle, needle_len);
  return NULL;
}

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Eric Blake]

[-- Attachment #1.1: Type: text/plain, Size: 1461 bytes --]

On 08/25/2017 01:07 PM, Eric Blake wrote:
> This is a poor algorithm (O(n^2) because it is is calling an O(n)
> strncmp() over every byte of haystack).  It also calls strlen() instead
> of strnlen(), which (when the needle is bigger than the haystack, and
> therefore the function must return NULL) is wasted effort.
> 
> Instead of copying the poor BSD implementation, why not just open-code
> it yourself to take advantage of our O(n) memmem(), which has already
> been optimized to take advantage of a better algorithm that is not
> quadratic?
> 
> char *
> strnstr(const char *haystack, const char *needle, size_t haystack_len)
> {
>   size_t needle_len = strnlen(needle, slen);
>   if (needle_len < slen || !needle[needle_len])
>     return memmem(haystack, haystack_len, needle, needle_len);
>   return NULL;
> }

Hmm, I guess you also have to double-check that there is no NUL byte in
haystack prior to the result returned by memmem(). But that is still O(n):

char *
strnstr(const char *haystack, const char *needle, size_t haystack_len)
{
  size_t needle_len = strnlen(needle, slen);
  if (needle_len < slen || !needle[needle_len]) {
    char *x = memmem(haystack, haystack_len, needle, needle_len);
    if (x && !memchr(haystack, 0, x - haystack))
      return x;
  }
  return NULL;
}

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Sichen Zhao]

> On 08/25/2017 01:07 PM, Eric Blake wrote:
>> This is a poor algorithm (O(n^2) because it is is calling an O(n)
>> strncmp() over every byte of haystack).  It also calls strlen() instead
>> of strnlen(), which (when the needle is bigger than the haystack, and
>> therefore the function must return NULL) is wasted effort.
>>
>> Instead of copying the poor BSD implementation, why not just open-code
>> it yourself to take advantage of our O(n) memmem(), which has already
>> been optimized to take advantage of a better algorithm that is not
>> quadratic?
>>
>> char *
>> strnstr(const char *haystack, const char *needle, size_t haystack_len)
>> {
>>    size_t needle_len = strnlen(needle, slen);
>>    if (needle_len < slen || !needle[needle_len])
>>      return memmem(haystack, haystack_len, needle, needle_len);
>>    return NULL;
>> }
> Hmm, I guess you also have to double-check that there is no NUL byte in
> haystack prior to the result returned by memmem(). But that is still O(n):
>
> char *
> strnstr(const char *haystack, const char *needle, size_t haystack_len)
> {
>    size_t needle_len = strnlen(needle, slen);
>    if (needle_len < slen || !needle[needle_len]) {
>      char *x = memmem(haystack, haystack_len, needle, needle_len);
>      if (x && !memchr(haystack, 0, x - haystack))
>        return x;
>    }
>    return NULL;
> }
Ok, So just modify the strnstr like that, right?

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Gedare Bloom]

On Fri, Aug 25, 2017 at 10:18 PM, Sichen Zhao <1473996754@qq.com> wrote:
>> On 08/25/2017 01:07 PM, Eric Blake wrote:
>>>
>>> This is a poor algorithm (O(n^2) because it is is calling an O(n)
>>> strncmp() over every byte of haystack).  It also calls strlen() instead
>>> of strnlen(), which (when the needle is bigger than the haystack, and
>>> therefore the function must return NULL) is wasted effort.
>>>
>>> Instead of copying the poor BSD implementation, why not just open-code
>>> it yourself to take advantage of our O(n) memmem(), which has already
>>> been optimized to take advantage of a better algorithm that is not
>>> quadratic?
>>>
>>> char *
>>> strnstr(const char *haystack, const char *needle, size_t haystack_len)
>>> {
>>>    size_t needle_len = strnlen(needle, slen);
>>>    if (needle_len < slen || !needle[needle_len])
>>>      return memmem(haystack, haystack_len, needle, needle_len);
>>>    return NULL;
>>> }
>>
>> Hmm, I guess you also have to double-check that there is no NUL byte in
>> haystack prior to the result returned by memmem(). But that is still O(n):
>>
>> char *
>> strnstr(const char *haystack, const char *needle, size_t haystack_len)
>> {
>>    size_t needle_len = strnlen(needle, slen);
>>    if (needle_len < slen || !needle[needle_len]) {
>>      char *x = memmem(haystack, haystack_len, needle, needle_len);
>>      if (x && !memchr(haystack, 0, x - haystack))
>>        return x;
>>    }
>>    return NULL;
>> }
>
> Ok, So just modify the strnstr like that, right?
>
Sichen,

Yes, you can optimize the algorithm in this function to utilize memmem
and memchr. This is a good idea, and nice catch on the NUL byte.
Please also provide a test case in RTEMS.

-Gedare

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Sichen Zhao]

> On Fri, Aug 25, 2017 at 10:18 PM, Sichen Zhao <1473996754@qq.com> wrote:
>>> On 08/25/2017 01:07 PM, Eric Blake wrote:
>>>> This is a poor algorithm (O(n^2) because it is is calling an O(n)
>>>> strncmp() over every byte of haystack).  It also calls strlen() instead
>>>> of strnlen(), which (when the needle is bigger than the haystack, and
>>>> therefore the function must return NULL) is wasted effort.
>>>>
>>>> Instead of copying the poor BSD implementation, why not just open-code
>>>> it yourself to take advantage of our O(n) memmem(), which has already
>>>> been optimized to take advantage of a better algorithm that is not
>>>> quadratic?
>>>>
>>>> char *
>>>> strnstr(const char *haystack, const char *needle, size_t haystack_len)
>>>> {
>>>>     size_t needle_len = strnlen(needle, slen);
>>>>     if (needle_len < slen || !needle[needle_len])
>>>>       return memmem(haystack, haystack_len, needle, needle_len);
>>>>     return NULL;
>>>> }
>>> Hmm, I guess you also have to double-check that there is no NUL byte in
>>> haystack prior to the result returned by memmem(). But that is still O(n):
>>>
>>> char *
>>> strnstr(const char *haystack, const char *needle, size_t haystack_len)
>>> {
>>>     size_t needle_len = strnlen(needle, slen);
>>>     if (needle_len < slen || !needle[needle_len]) {
>>>       char *x = memmem(haystack, haystack_len, needle, needle_len);
>>>       if (x && !memchr(haystack, 0, x - haystack))
>>>         return x;
>>>     }
>>>     return NULL;
>>> }
>> Ok, So just modify the strnstr like that, right?
>>
> Sichen,
>
> Yes, you can optimize the algorithm in this function to utilize memmem
> and memchr. This is a good idea, and nice catch on the NUL byte.
> Please also provide a test case in RTEMS.
>
> -Gedare
Ok, but how to provide a test case? i dont understand that.

Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Craig Howland]

In addition to a header patch being missing, the documentation/man page is also 
missing.  (It might make sense to add it to strstr.c, since strnstr() is just a 
length-limited version of strstr().  If it does end up there, delete that 
TRAD_SYNOPSIS section as long as it is being edited, as they have been unused 
for years.)
Craig

On 08/24/2017 04:48 AM, Corinna Vinschen wrote:
> Hi Sichen,
>
> On Aug 24 10:14, Sichen Zhao wrote:
>> ---
>>   newlib/libc/string/strnstr.c | 65 +++++++++++++++++++++++++++++++++++++++++++
> Isn't there a header patch missing?
>
>
> Thanks,
> Corinna
>