Change in coreboot[master]: lib/string: Add standard strstr() function

[Jes Klinke (Code Review)]

Hello Jes Klinke,

I'd like you to do a code review. Please visit

https://review.coreboot.org/c/coreboot/+/44085

to review the following change.

Change subject: lib/string: Add standard strstr() function
......................................................................

lib/string: Add standard strstr() function

Adding implementation of standard library strstr()

See https://review.coreboot.org/c/coreboot/+/43741 for context.

Change-Id: I63e26e98ed2dd15542f81c0a3a5e353bb93b7350
Signed-off-by: [e-mail]
---
M src/include/string.h
M src/lib/string.c
2 files changed, 11 insertions(+), 0 deletions(-)

git pull ssh://review.coreboot.org:29418/coreboot refs/changes/85/44085/1

diff --git a/src/include/string.h b/src/include/string.h
index 8eef068..3cfa18d 100644
--- a/src/include/string.h
+++ b/src/include/string.h
@@ -29,6 +29,7 @@
 int strncmp(const char *s1, const char *s2, int maxlen);
 int strspn(const char *str, const char *spn);
 int strcspn(const char *str, const char *spn);
+char *strstr(const char *haystack, const char *needle);
 char *strtok_r(char *str, const char *delim, char **ptr);
 char *strtok(char *str, const char *delim);
 long atol(const char *str);
diff --git a/src/lib/string.c b/src/lib/string.c
index e8f72a2..9677520 100644
--- a/src/lib/string.c
+++ b/src/lib/string.c
@@ -163,6 +163,16 @@
    return ret;
 }

+char *strstr(const char *haystack, const char *needle)
+{
+	size_t needle_len = strlen(needle);
+	for (; *haystack; haystack++) {
+		if (!strncmp(haystack, needle, needle_len))
+			return (char *)haystack;
+	}
+	return NULL;
+}
+
 char *strtok_r(char *str, const char *delim, char **ptr)
 {
    char *start;

[Angel Pons (Code Review)]

Angel Pons has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

Patch Set 1:

(1 comment)

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c 
File src/lib/string.c:

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@169 
PS1, Line 169: 	for (; *haystack; haystack++) {
We should bail if `strlen(haystack) < strlen(needle)`

[Julius Werner (Code Review)]

Julius Werner has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

Patch Set 1:

(1 comment)

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c 
File src/lib/string.c:

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@169 
PS1, Line 169: 	for (; *haystack; haystack++) {
> We should bail if `strlen(haystack) < strlen(needle)`

I mean, it's gonna do that automatically (strncmp() still stops at '\0' on either string). In the common case needle will be much shorter than haystack. By adding a strlen(haystack) here you are iterating one extra time through the whole (commonly) large haystack, and all you gain is that if someone calls the function with incorrect input, it will terminate slightly earlier (but if haystack is shorter than needle that probably means they're both extremely short in most cases, so it would finish quite quickly anyway). I don't think that trade-off is worth it.

[Julius Werner (Code Review)]

Julius Werner has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

Patch Set 1:

(1 comment)

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c 
File src/lib/string.c:

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@170 
PS1, Line 170: 		if (!strncmp(haystack, needle, needle_len))
I still think you should just use strcmp() here so you can avoid the strlen(needle) as well, btw (already mentioned on other CL).

[Angel Pons (Code Review)]

Angel Pons has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

Patch Set 1:

(1 comment)

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c 
File src/lib/string.c:

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@169 
PS1, Line 169: 	for (; *haystack; haystack++) {
> I mean, it's gonna do that automatically (strncmp() still stops at '\0' on either string). […]

Ack. I'm not friends with pointers nor undefined behavior, so I'm usually paranoid when handling these.

[Jes Klinke (Code Review)]

Jes Klinke has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

Patch Set 1:

(2 comments)

Please clarify what modifications you are suggesting.

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c 
File src/lib/string.c:

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@169 
PS1, Line 169: 	for (; *haystack; haystack++) {
> Ack. […]

I am not sure if the suggestion is to make a one-time comparison, and bail out before the for loop in case needle is longer, or whether the suggestion is to replace the exit condition of the for loop with the length comparison.

The latter is only an improvement if haystack is shorter than about double the size of the needle, which it will rarely be, and the former only improves the even more unlikely case of the given haystack being shorter than the needle.  I think as Julius, that it is not worth optimizing for such degenerate cases.  In particular when the cost of the latter interpretation being repeated strlen over the potentially long haystack, making the runtime O(h^2) instead of O(h*n) for the rather common case of the haystack being significantly longer than the needle.

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@170 
PS1, Line 170: 		if (!strncmp(haystack, needle, needle_len))
> I still think you should just use strcmp() here so you can avoid the strlen(needle) as well, btw (al […]

In the other cl you ask "Why not just strcmp()?".  I have to say, I do not see how this can be implemented using strcmp().  We are trying to find our if a null terminated string, needle, is equal to a number of characters in the middle of a longer string.  That is, there will not be any null termination after the "window" of the haystack string that we are interested in, so naively calling strcmp() will never return a match, unless the needle happens to be found at the very end of the haystack.

Are you proposing mutating the haystack, to add zeros "in the middle" of the string, and put back the original character afterwards, that we cannot do as the input is const.

Am I missing something obvious?

[Julius Werner (Code Review)]

Julius Werner has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

Patch Set 1: Code-Review+2

(1 comment)

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c 
File src/lib/string.c:

https://review.coreboot.org/c/coreboot/+/44085/1/src/lib/string.c@170 
PS1, Line 170: 		if (!strncmp(haystack, needle, needle_len))
> Am I missing something obvious?

No, sorry, I'm just dumb. ^^ Thanks for reminding me how strcmp() actually works.

[Patrick Georgi (Code Review)]

Patrick Georgi has submitted this change. ( https://review.coreboot.org/c/coreboot/+/44085 )

Change subject: lib/string: Add standard strstr() function
......................................................................

lib/string: Add standard strstr() function

Adding implementation of standard library strstr()

See https://review.coreboot.org/c/coreboot/+/43741 for context.

Change-Id: I63e26e98ed2dd15542f81c0a3a5e353bb93b7350
Signed-off-by: [e-mail]
Reviewed-on: https://review.coreboot.org/c/coreboot/+/44085
Tested-by: build bot (Jenkins) 
Reviewed-by: Julius Werner 
---
M src/include/string.h
M src/lib/string.c
2 files changed, 11 insertions(+), 0 deletions(-)

Approvals:
  build bot (Jenkins): Verified
  Julius Werner: Looks good to me, approved

diff --git a/src/include/string.h b/src/include/string.h
index 8eef068..3cfa18d 100644
--- a/src/include/string.h
+++ b/src/include/string.h
@@ -29,6 +29,7 @@
 int strncmp(const char *s1, const char *s2, int maxlen);
 int strspn(const char *str, const char *spn);
 int strcspn(const char *str, const char *spn);
+char *strstr(const char *haystack, const char *needle);
 char *strtok_r(char *str, const char *delim, char **ptr);
 char *strtok(char *str, const char *delim);
 long atol(const char *str);
diff --git a/src/lib/string.c b/src/lib/string.c
index e8f72a2..9677520 100644
--- a/src/lib/string.c
+++ b/src/lib/string.c
@@ -163,6 +163,16 @@
    return ret;
 }

+char *strstr(const char *haystack, const char *needle)
+{
+	size_t needle_len = strlen(needle);
+	for (; *haystack; haystack++) {
+		if (!strncmp(haystack, needle, needle_len))
+			return (char *)haystack;
+	}
+	return NULL;
+}
+
 char *strtok_r(char *str, const char *delim, char **ptr)
 {
    char *start;