[RFC] strrstr function in libbb failes on some corner cases

[Tito]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: strrstr.c
Type: text/x-csrc
Size: 2810 bytes
Desc: not available
Url : http://lists.busybox.net/pipermail/busybox/attachments/20080615/ea5de4a5/attachment-0002.c