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
'baaabaaaab' 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.
*/
char* strrstr(const char *haystack, const char *needle)
{
char *p = (char *)haystack;
char *s1;
char *s2;
if (!haystack || !needle)
return NULL;
while (*p++)
/* VOID */;
p--;
while (p-- != haystack) {
s1 = p;
s2 = (char *)needle;
while (*s1 && *s1++ == *s2++) {
if (!*s2)
return p;
}
}
return NULL;
}
This function passes all of the test cases I could think about:
./test
'baaabaaab' vs. 'aaa' : PASSED
'baaabaaaab' 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
'NULL' vs. 'NULL' : PASSED
'' vs. 'NULL' : PASSED
'NULL' vs. '' : PASSED
'aaa' vs. 'NULL' : PASSED
'NULL' vs. 'aaa' : PASSED
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:
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.
Hints, critics and improvements are ,as always, welcome.
Ciao,
Tito
/* vi: set sw=4 ts=4: */
/*
* Utility routines.
*
* Copyright (C) 2008 Bernhard Fischer
* Copyright (C) 2008 Tito Ragusa
*
* Licensed under GPLv2 or later, see file License in this tarball for details.
*/
#include "libbb.h"
/*
* 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.
*/
char* strrstr(const char *haystack, const char *needle)
{
char *p = (char *)haystack;
char *s1;
char *s2;
if (!haystack || !needle)
return NULL;
while (*p++)
/* VOID */;
p--;
while (p-- != haystack) {
s1 = p;
s2 = (char *)needle;
while (*s1 && *s1++ == *s2++) {
if (!*s2)
return p;
}
}
return NULL;
}
#ifdef STRRSTR_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("baaabaaaab", "aaa")) != NULL && strcmp(tmp, "aaab") == 0));
printf("'baaabaaaab' 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 = (strrstr("aaa", "") == NULL));
printf("'aaa' vs. '' : %s\n", n ? "PASSED" : "FAILED");
ret |= !(n = (strrstr("", "aaa") == NULL));
printf("'' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED");
ret |= !(n = (strrstr("", "") == NULL));
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
