[git commit] libbb: code shrink and speed up find_applet_by_name()

[Denys Vlasenko]

commit: https://git.busybox.net/busybox/commit/?id=59120c330330467c9e6aaec6d4ca8295baa653af
branch: https://git.busybox.net/busybox/commit/?id=refs/heads/master

find_applet_by_name() determines the appropriate range of applet
indices to check for the given name and performs a linear search in
applet_names[].

Revise the code so the index of the upper bound of the range, 'max',
isn't calculated.  Instead check the value of the first non-matching
character to see if we've reached the end of the range.

This new code speeds up the time to find a valid applet name by 6%
and halves the time to detect that a given name is invalid.  The
average time to detect an invalid name is now the same as for a valid
one.

function                                             old     new   delta
find_applet_by_name                                  155     133     -22
------------------------------------------------------------------------------
(add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-22)             Total: -22 bytes

Signed-off-by: Ron Yorston <rmy at pobox.com>
Signed-off-by: Denys Vlasenko <vda.linux at googlemail.com>
---
 libbb/appletlib.c | 96 ++++++++++---------------------------------------------
 1 file changed, 17 insertions(+), 79 deletions(-)

diff --git a/libbb/appletlib.c b/libbb/appletlib.c
index 5f59f1273..542211255 100644
--- a/libbb/appletlib.c
+++ b/libbb/appletlib.c
@@ -176,7 +176,7 @@ void FAST_FUNC bb_show_usage(void)
 
 int FAST_FUNC find_applet_by_name(const char *name)
 {
-	unsigned i, max;
+	unsigned i;
 	int j;
 	const char *p;
 
@@ -200,105 +200,43 @@ int FAST_FUNC find_applet_by_name(const char *name)
 #endif
 
 	p = applet_names;
-	i = 0;
 #if KNOWN_APPNAME_OFFSETS <= 0
-	max = NUM_APPLETS;
+	i = 0;
 #else
-	max = NUM_APPLETS * KNOWN_APPNAME_OFFSETS;
+	i = NUM_APPLETS * (KNOWN_APPNAME_OFFSETS - 1);
 	for (j = ARRAY_SIZE(applet_nameofs)-1; j >= 0; j--) {
 		const char *pp = applet_names + applet_nameofs[j];
 		if (strcmp(name, pp) >= 0) {
 			//bb_error_msg("name:'%s' >= pp:'%s'", name, pp);
 			p = pp;
-			i = max - NUM_APPLETS;
 			break;
 		}
-		max -= NUM_APPLETS;
+		i -= NUM_APPLETS;
 	}
-	max /= (unsigned)KNOWN_APPNAME_OFFSETS;
 	i /= (unsigned)KNOWN_APPNAME_OFFSETS;
-	//bb_error_msg("name:'%s' starting from:'%s' i:%u max:%u", name, p, i, max);
+	//bb_error_msg("name:'%s' starting from:'%s' i:%u", name, p, i);
 #endif
 
 	/* Open-coded linear search without strcmp/strlen calls for speed */
-
-#if 0 /*BB_UNALIGNED_MEMACCESS_OK && BB_LITTLE_ENDIAN*/
-	/* skip "[\0" name, it's surely not it */
-	if (ENABLE_TEST && LONE_CHAR(p, '['))
-		i++, p += 2;
-	/* All remaining applet names in p[] are at least 2 chars long */
-	/* name[] is also at least 2 chars long */
-
-	n32 = (name[0] << 0) | (name[1] << 8) | (name[2] << 16);
-	while (i < max) {
-		uint32_t p32;
-		char ch;
-
-		/* Quickly check match of the first 3 bytes */
-		move_from_unaligned32(p32, p);
-		p += 3;
-		if ((p32 & 0x00ffffff) != n32) {
-			/* Most likely case: 3 first bytes do not match */
-			i++;
-			if ((p32 & 0x00ff0000) == '\0')
-				continue; // p[2] was NUL
-			p++;
-			if ((p32 & 0xff000000) == '\0')
-				continue; // p[3] was NUL
-			/* p[0..3] aren't matching and none is NUL, check the rest */
-			while (*p++ != '\0')
-				continue;
-			continue;
-		}
-
-		/* Unlikely branch: first 3 bytes ([0..2]) match */
-		if ((p32 & 0x00ff0000) == '\0') {
-			/* name is 2-byte long, it is full match */
-			//bb_error_msg("found:'%s' i:%u", name, i);
-			return i;
-		}
-		/* Check remaining bytes [3..NUL] */
-		ch = (p32 >> 24);
-		j = 3;
-		while (ch == name[j]) {
-			if (ch == '\0') {
-				//bb_error_msg("found:'%s' i:%u", name, i);
-				return i;
-			}
-			ch = *++p;
-			j++;
-		}
-		/* Not a match. Skip it, including NUL */
-		while (ch != '\0')
-			ch = *++p;
-		p++;
-		i++;
-	}
-	return -1;
-#else
-	while (i < max) {
-		char ch;
-		j = 0;
-		/* Do we see "name\0" in applet_names[p] position? */
-		while ((ch = *p) == name[j]) {
-			if (ch == '\0') {
+	while (*p) {
+		/* Do we see "name\0" at current position in applet_names? */
+		for (j = 0; *p == name[j]; ++j) {
+			if (*p++ == '\0') {
 				//bb_error_msg("found:'%s' i:%u", name, i);
 				return i; /* yes */
 			}
-			p++;
-			j++;
 		}
-		/* No.
-		 * p => 1st non-matching char in applet_names[],
-		 * skip to and including NUL.
-		 */
-		while (ch != '\0')
-			ch = *++p;
-		p++;
+		/* No. Have we gone too far, alphabetically? */
+		if (*p > name[j]) {
+			//bb_error_msg("break:'%s' i:%u", name, i);
+			break;
+		}
+		/* No. Move to the start of the next applet name. */
+		while (*p++ != '\0')
+			continue;
 		i++;
 	}
 	return -1;
-#endif
 }