Re: [RFC] strrstr function in libbb failes on some corner cases
On Mon, Jun 16, 2008 at 09:48:07PM +0200, Tito wrote:
On Monday 16 June 2008 09:47:31 Bernhard Fischer wrote:
On Mon, Jun 16, 2008 at 08:45:18AM +0200, Tito wrote:
On Monday 16 June 2008 06:33:35 you wrote:
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
Hi, just for fun,
one more variant that seems to pass the tests as modified (for )
char* strrstr(const char *haystack, const char *needle)
{
char *s = NULL;
while (*haystack) {
s = (strstr(haystack++, needle)) ? : s;
}
return s;
}
but size on my system is the same as Denys' version :(
scripts/bloat-o-meter busybox_old busybox_unstripped
function old new delta
strrstr 53 42 -11
--
(add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-11) Total: -11 bytes
Tito, can you pick one (your decision) and send me the full file
(including your nice testcases)?
TIA and cheers,
___
busybox mailing list
busybox@busybox.net
http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Tuesday 17 June 2008 09:43:54 Bernhard Fischer wrote:
On Mon, Jun 16, 2008 at 09:48:07PM +0200, Tito wrote:
On Monday 16 June 2008 09:47:31 Bernhard Fischer wrote:
On Mon, Jun 16, 2008 at 08:45:18AM +0200, Tito wrote:
On Monday 16 June 2008 06:33:35 you wrote:
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
Hi, just for fun,
one more variant that seems to pass the tests as modified (for )
char* strrstr(const char *haystack, const char *needle)
{
char *s = NULL;
while (*haystack) {
s = (strstr(haystack++, needle)) ? : s;
}
return s;
}
but size on my system is the same as Denys' version :(
scripts/bloat-o-meter busybox_old busybox_unstripped
function old new delta
strrstr 53 42 -11
--
(add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-11) Total: -11
bytes
Tito, can you pick one (your decision) and send me the full file
(including your nice testcases)?
TIA and cheers,
HI,
Attached you can find a test.c file with both strrstr, mine and Denys', they
show little
differences on vs. test case.
The test cases are improved and checked against the real strstr for consistency.
As you and Denys are more experienced it is up yo you to decide what to do.
Ciao,
Tito
/* vi: set sw=4 ts=4: */
/*
* Utility routines.
*
* Copyright (C) 2008 Bernhard Fischer
*
* Licensed under GPLv2 or later, see file License in this tarball for details.
*/
#include string.h
#include stdio.h
#define STRRSTR_TEST
/*#define DENYS*/
/*
* The strrstr() function finds the last occurrence of th substring needle
* in the string haystack. The terminating nul characters are not compared.
*/
#ifdef DENYS
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
}
}
#else
char* strrstr(const char *haystack, const char *needle)
{
char *s = NULL;
do {
s = (strstr(haystack, needle)) ? : s;
} while (*haystack++);
//printf(%s\n, (s) ? s : NULL);
return s;
}
#endif
#ifdef STRRSTR_TEST
/* Test */
int main(int argc, char **argv)
{
int ret = 0;
int n;
char *tmp;
ret |= !(n = ((tmp = strrstr(baaabaaab, aaa)) != NULL strcmp(tmp, aaab) == 0));
printf('baaabaaab' vs. 'aaa' : %s\n, n ? PASSED : FAILED);
ret |= !(n = ((tmp = strrstr(baaabb, aaa)) != NULL strcmp(tmp, aaab) == 0));
printf('baaabb' vs. 'aaa' : %s\n, n ? PASSED : FAILED);
ret |= !(n = ((tmp = strrstr(baaabaab, aaa)) != NULL strcmp(tmp, aaabaab) == 0));
printf('baaabaab' vs. 'aaa' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(aaa, aaa) != NULL));
printf('aaa'vs. 'aaa' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(aaa, a) != NULL));
printf('aaa'vs. 'a' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(aaa, bbb) == NULL));
printf('aaa'vs. 'bbb' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(a, aaa) == NULL));
printf('a' vs. 'aaa' : %s\n, n ? PASSED : FAILED);
ret |= !(n = ((tmp = strrstr(aaa, )) != NULL strcmp(tmp, aaa) == 0));
printf('aaa'vs. '' : %s\n, n ? FAILED : PASSED);
ret |= !(n = (strrstr(, aaa) == NULL));
printf('' vs. 'aaa' : %s\n, n ? PASSED : FAILED);
ret |= !(n = ((tmp = strrstr(, )) != NULL strcmp(tmp, ) == 0));
printf('' vs. '' : %s\n, n ? PASSED : FAILED);
/*ret |= !(n = (strrstr(NULL, NULL) == NULL));
printf('NULL' vs. 'NULL' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(, NULL) == NULL));
printf('' vs. 'NULL' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(NULL, ) == NULL));
printf('NULL' vs. '' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(aaa, NULL) == NULL));
printf('aaa'vs. 'NULL' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(NULL, aaa) == NULL));
printf('NULL' vs. 'aaa' : %s\n, n ? PASSED : FAILED);*/
return ret;
}
#endif
___
busybox mailing list
busybox@busybox.net
http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Tue, Jun 17, 2008 at 01:52:20PM +0200, Tito wrote: HI, Attached you can find a test.c file with both strrstr, mine and Denys', they show little differences on vs. test case. The test cases are improved and checked against the real strstr for consistency. I picked vda's since yours used the non-standard foo?:bar extension. Thanks! ___ busybox mailing list busybox@busybox.net http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Monday 16 June 2008 06:33:35 you wrote:
On Sunday 15 June 2008 23:06, Tito wrote:
Hi,
while inspecting the last changes in busybox code I hit some issues in
libbb/strrstr.c. The strrtstr function fails on some corner cases of a
little
test program I wrote (and bombs out on NULL pointers):
char* strrstr(const char *haystack, const char *needle)
{
char *tmp = strrchr(haystack, *needle);
if (tmp == NULL || strcmp(tmp, needle) != 0)
return NULL;
return tmp;
}
./test
'baaabaaab' vs. 'aaa' : FAILED
'baaabb' vs. 'aaa' : FAILED
'baaabaab' vs. 'aaa' : FAILED
'aaa'vs. 'aaa' : FAILED
'aaa'vs. 'a' : PASSED
'aaa'vs. 'bbb' : PASSED
'a' vs. 'aaa' : PASSED
'aaa'vs. '' : FAILED
'' vs. 'aaa' : PASSED
'' vs. '' : FAILED
Segmentation fault
I've tried to write a more robust variant:
/*
* The strrstr() function finds the last occurrence of the nul terminated
* substring needle in the nul terminated string haystack. The terminating
* nul characters or NULL pointers are not compared.
*/
Why is it important to work with NULLs?
E.g. strlen would SEGV on NULL.
Hi,
It is just my way of doing things, I don't like functions that segfault
on NULL as usually most of the times you have to add guards in the calling
code, but as said this part of the code could easily be removed
so that the size is almost the same as before.
There was one more reason to avoid strlen, but it was just my personal stupid
paranoia:
as we don't know the lenght of the strings it was difficult to decide
the correct type for the result to avoid possible overflows
OTOH using the biggest looked like overkill,
so I decided to walk to the end of the string instead.
Mine version is:
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
}
}
# ./a.out
'baaabaaab' vs. 'aaa' : PASSED
'baaabb' vs. 'aaa' : PASSED
'baaabaab' vs. 'aaa' : PASSED
'aaa'vs. 'aaa' : PASSED
'aaa'vs. 'a' : PASSED
'aaa'vs. 'bbb' : PASSED
'a' vs. 'aaa' : PASSED
'aaa'vs. '' : PASSED
'' vs. 'aaa' : PASSED
'' vs. '' : PASSED
(cases with NULLs are not tested)
Comparing with current busybox:
function old new delta
strrstr 53 42 -11
BTW, is it normal:
ret |= !(n = (strrstr(aaa, ) == NULL));
printf('aaa'vs. '' : %s\n, n ? PASSED :
FAILED);
ret |= !(n = (strrstr(, ) == NULL));
printf('' vs. '' : %s\n, n ? PASSED :
FAILED);
needle definitely CAN be found in (any) haystack. Why we return NULL?!
I misunderstood the man page:
DESCRIPTION
The strstr() function finds the first occurrence of the substring needle
in the string haystack. The terminating ’\0’ characters are not
compared.
I thought is '\0' and should not be compared. But by running a little
test program the behaviour of strstr seems to be different, so this certainly
needs to be fixed :
int main(int argc, char **argv)
{
printf(strstr(aaa,'') returns %sNULL\n, (strstr(aaa, ) == NULL) ?
:not-);
printf(%s\n, strstr(aaa, ));
printf(strstr('','') returns %sNULL\n, (strstr(, ) == NULL) ?
:not-);
printf(%s\n, strstr(, ));
return 0;
}
./test2
strstr(aaa,) returns not-NULL
aaa
strstr(,) returns not-NULL
debian:~/Desktop#
Ciao,
Tito
--
vda
___
busybox mailing list
busybox@busybox.net
http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Mon, Jun 16, 2008 at 08:45:18AM +0200, Tito wrote:
On Monday 16 June 2008 06:33:35 you wrote:
There was one more reason to avoid strlen, but it was just my personal stupid
paranoia:
as we don't know the lenght of the strings it was difficult to decide
the correct type for the result to avoid possible overflows
OTOH using the biggest looked like overkill,
so I decided to walk to the end of the string instead.
Mine version is:
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
}
}
# ./a.out
'baaabaaab' vs. 'aaa' : PASSED
'baaabb' vs. 'aaa' : PASSED
'baaabaab' vs. 'aaa' : PASSED
'aaa'vs. 'aaa' : PASSED
'aaa'vs. 'a' : PASSED
'aaa'vs. 'bbb' : PASSED
'a' vs. 'aaa' : PASSED
'aaa'vs. '' : PASSED
'' vs. 'aaa' : PASSED
'' vs. '' : PASSED
(cases with NULLs are not tested)
Comparing with current busybox:
function old new delta
strrstr 53 42 -11
Sounds good. Please apply.
./test2
strstr(aaa,) returns not-NULL
aaa
strstr(,) returns not-NULL
For practical reasons i would return NULL if one of them is NULL or
to avoid checks in the callers.
___
busybox mailing list
busybox@busybox.net
http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Monday 16 June 2008 09:47:31 Bernhard Fischer wrote:
On Mon, Jun 16, 2008 at 08:45:18AM +0200, Tito wrote:
On Monday 16 June 2008 06:33:35 you wrote:
There was one more reason to avoid strlen, but it was just my personal
stupid paranoia:
as we don't know the lenght of the strings it was difficult to decide
the correct type for the result to avoid possible overflows
OTOH using the biggest looked like overkill,
so I decided to walk to the end of the string instead.
Mine version is:
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
}
}
# ./a.out
'baaabaaab' vs. 'aaa' : PASSED
'baaabb' vs. 'aaa' : PASSED
'baaabaab' vs. 'aaa' : PASSED
'aaa'vs. 'aaa' : PASSED
'aaa'vs. 'a' : PASSED
'aaa'vs. 'bbb' : PASSED
'a' vs. 'aaa' : PASSED
'aaa'vs. '' : PASSED
'' vs. 'aaa' : PASSED
'' vs. '' : PASSED
(cases with NULLs are not tested)
Comparing with current busybox:
function old new delta
strrstr 53 42 -11
Sounds good. Please apply.
./test2
strstr(aaa,) returns not-NULL
aaa
strstr(,) returns not-NULL
For practical reasons i would return NULL if one of them is NULL or
to avoid checks in the callers.
Hi, just for fun,
one more variant that seems to pass the tests as modified (for )
char* strrstr(const char *haystack, const char *needle)
{
char *s = NULL;
while (*haystack) {
s = (strstr(haystack++, needle)) ? : s;
}
return s;
}
but size on my system is the same as Denys' version :(
scripts/bloat-o-meter busybox_old busybox_unstripped
function old new delta
strrstr 53 42 -11
--
(add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-11) Total: -11 bytes
Ciao,
Tito
___
busybox mailing list
busybox@busybox.net
http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Sun, Jun 15, 2008 at 11:06:17PM +0200, Tito wrote: Hi, while inspecting the last changes in busybox code I hit some issues in libbb/strrstr.c. The strrtstr function fails on some corner cases of a little test program I wrote (and bombs out on NULL pointers): This was intended, see below. For the moment there is no diff but just a drop in replacement for strrstr.c for testing and improvement by the list members. There is a little size increase: heh, i wouldn't call 50% a little, but ok. Ultimately i don't care, though. I just put in the smallest version for depmod knowing that it will segfault left and right if somebody throws NULL on it, since it was enough for depmod. Doesn't it suffice if we just if (haystack == NULL || needle == NULL) return NULL and keep the strcmp? scripts/bloat-o-meter busybox_old busybox_unstripped function old new delta strrstr 53 73 +20 -- (add/remove: 0/0 grow/shrink: 1/0 up/down: 20/0) Total: 20 bytes The strrstr function at the moment is used only in depmod so the depmod author should check if this new implementation is suitable to be used. ___ busybox mailing list busybox@busybox.net http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Sunday 15 June 2008 23:21:43 Bernhard Fischer wrote: On Sun, Jun 15, 2008 at 11:06:17PM +0200, Tito wrote: Hi, while inspecting the last changes in busybox code I hit some issues in libbb/strrstr.c. The strrtstr function fails on some corner cases of a little test program I wrote (and bombs out on NULL pointers): This was intended, see below. For the moment there is no diff but just a drop in replacement for strrstr.c for testing and improvement by the list members. There is a little size increase: heh, i wouldn't call 50% a little, but ok. Ultimately i don't care, though. I just put in the smallest version for depmod knowing that it will segfault left and right if somebody throws NULL on it, since it was enough for depmod. Hi, To be honest I was tempted to remove the code that handles NULL pointers in which case the size is about the same as before. scripts/bloat-o-meter busybox_old busybox_unstripped function old new delta strrstr 53 61 +8 -- (add/remove: 0/0 grow/shrink: 1/0 up/down: 8/0) Total: 8 bytes My point was that: 1) actually it fails to detect aa in aaa 2) this and other limitations shown by my test program are not described in the code nor in the function name so people in the future will think they have a correct working implementation of strrstr 3) if it is good enough for depmod and used only by depmod then move it into depmod.c or fix it for future use. Ciao, Tito Doesn't it suffice if we just if (haystack == NULL || needle == NULL) return NULL and keep the strcmp? scripts/bloat-o-meter busybox_old busybox_unstripped function old new delta strrstr 53 73 +20 -- (add/remove: 0/0 grow/shrink: 1/0 up/down: 20/0) Total: 20 bytes The strrstr function at the moment is used only in depmod so the depmod author should check if this new implementation is suitable to be used. ___ busybox mailing list busybox@busybox.net http://busybox.net/cgi-bin/mailman/listinfo/busybox
Re: [RFC] strrstr function in libbb failes on some corner cases
On Sunday 15 June 2008 23:06, Tito wrote:
Hi,
while inspecting the last changes in busybox code I hit some issues in
libbb/strrstr.c. The strrtstr function fails on some corner cases of a little
test program I wrote (and bombs out on NULL pointers):
char* strrstr(const char *haystack, const char *needle)
{
char *tmp = strrchr(haystack, *needle);
if (tmp == NULL || strcmp(tmp, needle) != 0)
return NULL;
return tmp;
}
./test
'baaabaaab' vs. 'aaa' : FAILED
'baaabb' vs. 'aaa' : FAILED
'baaabaab' vs. 'aaa' : FAILED
'aaa'vs. 'aaa' : FAILED
'aaa'vs. 'a' : PASSED
'aaa'vs. 'bbb' : PASSED
'a' vs. 'aaa' : PASSED
'aaa'vs. '' : FAILED
'' vs. 'aaa' : PASSED
'' vs. '' : FAILED
Segmentation fault
I've tried to write a more robust variant:
/*
* The strrstr() function finds the last occurrence of the nul terminated
* substring needle in the nul terminated string haystack. The terminating
* nul characters or NULL pointers are not compared.
*/
Why is it important to work with NULLs?
E.g. strlen would SEGV on NULL.
Mine version is:
char* strrstr(const char *haystack, const char *needle)
{
char *r = NULL;
if (!needle[0])
return r;
while (1) {
char *p = strstr(haystack, needle);
if (!p)
return r;
r = p;
haystack = p + 1;
}
}
# ./a.out
'baaabaaab' vs. 'aaa' : PASSED
'baaabb' vs. 'aaa' : PASSED
'baaabaab' vs. 'aaa' : PASSED
'aaa'vs. 'aaa' : PASSED
'aaa'vs. 'a' : PASSED
'aaa'vs. 'bbb' : PASSED
'a' vs. 'aaa' : PASSED
'aaa'vs. '' : PASSED
'' vs. 'aaa' : PASSED
'' vs. '' : PASSED
(cases with NULLs are not tested)
Comparing with current busybox:
function old new delta
strrstr 53 42 -11
BTW, is it normal:
ret |= !(n = (strrstr(aaa, ) == NULL));
printf('aaa'vs. '' : %s\n, n ? PASSED : FAILED);
ret |= !(n = (strrstr(, ) == NULL));
printf('' vs. '' : %s\n, n ? PASSED : FAILED);
needle definitely CAN be found in (any) haystack. Why we return NULL?!
--
vda
___
busybox mailing list
busybox@busybox.net
http://busybox.net/cgi-bin/mailman/listinfo/busybox
