← Commit list

701e127f7

Denys Vlasenko
Denys Vlasenko
2010-09-04
FAILED Duration: 324s

Subject

hush: optimize #[#] and %[%] for speed. size -2 bytes.

Binary

No binary (build failed)

Architecture & Compiler Flags

Architecture: x86_64-linux-gnu Compiler: gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0

—

Build Log

(log yok)

Commit Diff GitHub →

shell/hush.c +10 -12shell/match.c +62 -44shell/match.h +15 -14
shell/hush.c+10 -12
@@ -2829,23 +2829,21 @@ static NOINLINE int expand_vars_to_list(o_string *output, int n, char *arg, char
* Then var's value is matched to it and matching part removed.
*/
if (val) {
- bool match_at_left;
+ char *exp_exp_word;
char *loc;
- scan_t scan = pick_scan(exp_op, *exp_word, &match_at_left);
+ unsigned scan_flags = pick_scan(exp_op, *exp_word);
if (exp_op == *exp_word) /* ## or %% */
exp_word++;
val = to_be_freed = xstrdup(val);
- {
- char *exp_exp_word = expand_pseudo_dquoted(exp_word);
- if (exp_exp_word)
- exp_word = exp_exp_word;
- loc = scan(to_be_freed, exp_word, match_at_left);
- //bb_error_msg("op:%c str:'%s' pat:'%s' res:'%s'",
- // exp_op, to_be_freed, exp_word, loc);
- free(exp_exp_word);
- }
+ exp_exp_word = expand_pseudo_dquoted(exp_word);
+ if (exp_exp_word)
+ exp_word = exp_exp_word;
+ loc = scan_and_match(to_be_freed, exp_word, scan_flags);
+ //bb_error_msg("op:%c str:'%s' pat:'%s' res:'%s'",
+ // exp_op, to_be_freed, exp_word, loc);
+ free(exp_exp_word);
if (loc) { /* match was found */
- if (match_at_left) /* # or ## */
+ if (scan_flags & SCAN_MATCH_LEFT_HALF) /* # or ## */
val = loc;
else /* % or %% */
*loc = '\0';
shell/match.c+62 -44
@@ -18,6 +18,9 @@
# include <stdlib.h>
# include <string.h>
# include <unistd.h>
+# define FAST_FUNC /* nothing */
+# define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */
+# define POP_SAVED_FUNCTION_VISIBILITY /* nothing */
#else
# include "libbb.h"
#endif
@@ -26,16 +29,48 @@
#define pmatch(a, b) !fnmatch((a), (b), 0)
-char *scanleft(char *string, char *pattern, bool match_at_left)
+char* FAST_FUNC scan_and_match(char *string, const char *pattern, unsigned flags)
{
- char c;
- char *loc = string;
+ char *loc;
+ char *end;
+ unsigned len = strlen(string);
+ int early_exit;
+
+ /* We can stop the scan early only if the string part
+ * we are matching against is shrinking, and the pattern has
+ * an unquoted "star" at the corresponding end. There are two cases.
+ * Case 1:
+ * "qwerty" does not match against pattern "*zy",
+ * no point in trying to match "werty", "erty" etc:
+ */
+ early_exit = (flags == (SCAN_MOVE_FROM_LEFT + SCAN_MATCH_RIGHT_HALF) && pattern[0] == '*');
+
+ if (flags & SCAN_MOVE_FROM_LEFT) {
+ loc = string;
+ end = string + len + 1;
+ } else {
+ loc = string + len;
+ end = string - 1;
+ if (flags == (SCAN_MOVE_FROM_RIGHT + SCAN_MATCH_LEFT_HALF)) {
+ /* Case 2:
+ * "qwerty" does not match against pattern "qz*",
+ * no point in trying to match "qwert", "qwer" etc:
+ */
+ const char *p = pattern + strlen(pattern);
+ if (--p >= pattern && *p == '*') {
+ early_exit = 1;
+ while (--p >= pattern && *p == '\\')
+ early_exit ^= 1;
+ }
+ }
+ }
- while (1) {
+ while (loc != end) {
+ char c;
int match;
c = *loc;
- if (match_at_left) {
+ if (flags & SCAN_MATCH_LEFT_HALF) {
*loc = '\0';
match = pmatch(pattern, string);
*loc = c;
@@ -44,33 +79,19 @@ char *scanleft(char *string, char *pattern, bool match_at_left)
}
if (match)
return loc;
- if (!c)
- return NULL;
- loc++;
- }
-}
-
-char *scanright(char *string, char *pattern, bool match_at_left)
-{
- char c;
- char *loc = string + strlen(string);
-
- while (loc >= string) {
- int match;
+ if (early_exit) {
+#ifdef STANDALONE
+ printf("(early exit) ");
+#endif
+ break;
+ }
- c = *loc;
- if (match_at_left) {
- *loc = '\0';
- match = pmatch(pattern, string);
- *loc = c;
+ if (flags & SCAN_MOVE_FROM_LEFT) {
+ loc++;
} else {
- match = pmatch(pattern, loc);
+ loc--;
}
- if (match)
- return loc;
- loc--;
}
-
return NULL;
}
@@ -80,12 +101,11 @@ int main(int argc, char *argv[])
char *string;
char *op;
char *pattern;
- bool match_at_left;
char *loc;
- int i;
+ setvbuf(stdout, NULL, _IONBF, 0);
- if (argc == 1) {
+ if (!argv[1]) {
puts(
"Usage: match <test> [test...]\n\n"
"Where a <test> is the form: <string><op><match>\n"
@@ -95,36 +115,34 @@ int main(int argc, char *argv[])
return 1;
}
- for (i = 1; i < argc; ++i) {
+ while (*++argv) {
size_t off;
- scan_t scan;
-
- printf("'%s': ", argv[i]);
+ unsigned scan_flags;
- string = strdup(argv[i]);
+ string = *argv;
off = strcspn(string, "#%");
if (!off) {
printf("invalid format\n");
- free(string);
continue;
}
op = string + off;
- scan = pick_scan(op[0], op[1], &match_at_left);
+ scan_flags = pick_scan(op[0], op[1]);
+
+ printf("'%s': flags:%x, ", string, scan_flags);
pattern = op + 1;
if (op[0] == op[1])
- op[1] = '\0', ++pattern;
+ pattern++;
op[0] = '\0';
- loc = scan(string, pattern, match_at_left);
+ loc = scan_and_match(string, pattern, scan_flags);
- if (match_at_left) {
+ if (scan_flags & SCAN_MATCH_LEFT_HALF) {
printf("'%s'\n", loc);
} else {
- *loc = '\0';
+ if (loc)
+ *loc = '\0';
printf("'%s'\n", string);
}
-
- free(string);
}
return 0;
shell/match.h+15 -14
@@ -7,25 +7,26 @@ PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN
//TODO! Why ash.c still uses internal version?!
-typedef char *(*scan_t)(char *string, char *match, bool match_at_left);
+enum {
+ SCAN_MOVE_FROM_LEFT = (1 << 0),
+ SCAN_MOVE_FROM_RIGHT = (1 << 1),
+ SCAN_MATCH_LEFT_HALF = (1 << 2),
+ SCAN_MATCH_RIGHT_HALF = (1 << 3),
+};
-char *scanleft(char *string, char *match, bool match_at_left);
-char *scanright(char *string, char *match, bool match_at_left);
+char* FAST_FUNC scan_and_match(char *string, const char *pattern, unsigned flags);
-static inline scan_t pick_scan(char op1, char op2, bool *match_at_left)
+static inline unsigned pick_scan(char op1, char op2)
{
- /* # - scanleft
- * ## - scanright
- * % - scanright
- * %% - scanleft
- */
+ unsigned scan_flags;
if (op1 == '#') {
- *match_at_left = true;
- return op1 == op2 ? scanright : scanleft;
- } else {
- *match_at_left = false;
- return op1 == op2 ? scanleft : scanright;
+ scan_flags = SCAN_MATCH_LEFT_HALF +
+ (op1 == op2 ? SCAN_MOVE_FROM_RIGHT : SCAN_MOVE_FROM_LEFT);
+ } else { /* % */
+ scan_flags = SCAN_MATCH_RIGHT_HALF +
+ (op1 == op2 ? SCAN_MOVE_FROM_LEFT : SCAN_MOVE_FROM_RIGHT);
}
+ return scan_flags;
}
POP_SAVED_FUNCTION_VISIBILITY