From 59120c330330467c9e6aaec6d4ca8295baa653af Mon Sep 17 00:00:00 2001 From: Ron Yorston Date: Fri, 29 Jan 2021 13:22:48 +0000 Subject: libbb: code shrink and speed up find_applet_by_name() 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 Signed-off-by: Denys Vlasenko --- 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 } -- cgit v1.2.3