find_applet_by_name: add an example of faster linear search code

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

1 files changed, 77 insertions, 3 deletions

diff --git a/libbb/appletlib.c b/libbb/appletlib.c
index aeaf238..18583f9 100644
--- a/libbb/appletlib.c
+++ b/libbb/appletlib.c
@@ -141,10 +141,28 @@ void FAST_FUNC bb_show_usage(void)
 
 int FAST_FUNC find_applet_by_name(const char *name)
 {
-	unsigned i, max;
-	int j;
+	unsigned i, j, max;
 	const char *p;
 
+/* The commented-out word-at-a-time code is ~40% faster, but +160 bytes.
+ * "Faster" here saves ~0.5 microsecond of real time - not worth it.
+ */
+#if 0 /*BB_UNALIGNED_MEMACCESS_OK && BB_LITTLE_ENDIAN*/
+	uint32_t n32;
+
+	/* Handle all names < 2 chars long early */
+	if (name[0] == '\0')
+		return -1; /* "" is not a valid applet name */
+	if (name[1] == '\0') {
+		if (!ENABLE_TEST)
+			return -1; /* 1-char name is not valid */
+		if (name[0] != ']')
+			return -1; /* 1-char name which isn't "[" is not valid */
+		/* applet "[" is always applet #0: */
+		return 0;
+	}
+#endif
+
 	p = applet_names;
 	i = 0;
 #if KNOWN_APPNAME_OFFSETS <= 0
@@ -166,7 +184,62 @@ int FAST_FUNC find_applet_by_name(const char *name)
 	//bb_error_msg("name:'%s' starting from:'%s' i:%u max:%u", name, p, i, max);
 #endif
 
-	/* Open-coding without strcmp/strlen calls for speed */
+	/* Open-coded linear seatch 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;
@@ -189,6 +262,7 @@ int FAST_FUNC find_applet_by_name(const char *name)
 		i++;
 	}
 	return -1;
+#endif
 }