summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDenys Vlasenko2016-04-02 22:54:23 +0200
committerDenys Vlasenko2016-04-02 22:54:23 +0200
commita93e4fd376d990ead254657228e75715b74ca0ac (patch)
tree0b5a12034639058875befb5f2146c67c9fd95173
parent8b0f459af7aa108089d0f87b0be81ccadb8638cb (diff)
downloadbusybox-a93e4fd376d990ead254657228e75715b74ca0ac.zip
busybox-a93e4fd376d990ead254657228e75715b74ca0ac.tar.gz
find_applet_by_name: add an example of faster linear search code
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
-rw-r--r--libbb/appletlib.c80
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
}