diff options
| -rw-r--r-- | shell/Config.in | 32 | ||||
| -rw-r--r-- | shell/Kbuild | 1 | ||||
| -rw-r--r-- | shell/ash.c | 734 | ||||
| -rw-r--r-- | shell/hush.c | 102 | ||||
| -rw-r--r-- | shell/math.c | 701 | ||||
| -rw-r--r-- | shell/math.h | 101 |
6 files changed, 945 insertions, 726 deletions
diff --git a/shell/Config.in b/shell/Config.in index afc429667..7daf17ff6 100644 --- a/shell/Config.in +++ b/shell/Config.in @@ -84,22 +84,6 @@ config ASH_ALIAS help Enable alias support in the ash shell. -config ASH_MATH_SUPPORT - bool "Posix math support" - default y - depends on ASH - help - Enable math support in the ash shell. - -config ASH_MATH_SUPPORT_64 - bool "Extend Posix math support to 64 bit" - default n - depends on ASH_MATH_SUPPORT - help - Enable 64-bit math support in the ash shell. This will make - the shell slightly larger, but will allow computation with very - large numbers. - config ASH_GETOPTS bool "Builtin getopt to parse positional parameters" default n @@ -267,6 +251,22 @@ config MSH comment "Bourne Shell Options" depends on MSH || LASH || HUSH || ASH +config SH_MATH_SUPPORT + bool "POSIX math support" + default y + depends on ASH || HUSH + help + Enable math support in the shell via $((...)) syntax. + +config SH_MATH_SUPPORT_64 + bool "Extend POSIX math support to 64 bit" + default n + depends on SH_MATH_SUPPORT + help + Enable 64-bit math support in the shell. This will make the shell + slightly larger, but will allow computation with very large numbers. + This is not in POSIX, so do not rely on this in portable code. + config FEATURE_SH_EXTRA_QUIET bool "Hide message on interactive shell startup" default n diff --git a/shell/Kbuild b/shell/Kbuild index deedc24f3..2b461b3bd 100644 --- a/shell/Kbuild +++ b/shell/Kbuild @@ -9,3 +9,4 @@ lib-$(CONFIG_ASH) += ash.o ash_ptr_hack.o lib-$(CONFIG_HUSH) += hush.o lib-$(CONFIG_MSH) += msh.o lib-$(CONFIG_CTTYHACK) += cttyhack.o +lib-$(CONFIG_SH_MATH_SUPPORT) += math.o diff --git a/shell/ash.c b/shell/ash.c index 4f7f38f6d..0d3ab0ff5 100644 --- a/shell/ash.c +++ b/shell/ash.c @@ -17,19 +17,6 @@ */ /* - * rewrite arith.y to micro stack based cryptic algorithm by - * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com> - * - * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support - * dynamic variables. - * - * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be - * used in busybox and size optimizations, - * rewrote arith (see notes to this), added locale support, - * rewrote dynamic variables. - */ - -/* * The following should be set to reflect the type of system you have: * JOBS -> 1 if you have Berkeley job control, 0 otherwise. * define SYSV if you are running under System V. @@ -63,6 +50,7 @@ #include <paths.h> #include <setjmp.h> #include <fnmatch.h> +#include "math.h" #if defined SINGLE_APPLET_MAIN /* STANDALONE does not make sense, and won't compile */ @@ -197,6 +185,10 @@ struct globals_misc { #define debug optlist[15] #endif +#if ENABLE_SH_MATH_SUPPORT + arith_eval_hooks_t math_hooks; +#endif + /* trap handler commands */ /* * Sigmode records the current value of the signal handlers for the various @@ -246,6 +238,7 @@ extern struct globals_misc *const ash_ptr_to_globals_misc; #define random_LCG (G_misc.random_LCG ) #define backgndpid (G_misc.backgndpid ) #define job_warning (G_misc.job_warning) +#define math_hooks (G_misc.math_hooks ) #define INIT_G_misc() do { \ (*(struct globals_misc**)&ash_ptr_to_globals_misc) = xzalloc(sizeof(G_misc)); \ barrier(); \ @@ -1998,7 +1991,7 @@ findvar(struct var **vpp, const char *name) /* * Find the value of a variable. Returns NULL if not set. */ -static char * +static const char * lookupvar(const char *name) { struct var *v; @@ -2024,7 +2017,7 @@ lookupvar(const char *name) /* * Search the environment of a builtin command. */ -static char * +static const char * bltinlookup(const char *name) { struct strlist *sp; @@ -2637,7 +2630,7 @@ pwdcmd(int argc UNUSED_PARAM, char **argv UNUSED_PARAM) #define USE_SIT_FUNCTION #endif -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT static const char S_I_T[][4] = { #if ENABLE_ASH_ALIAS { CSPCL, CIGN, CIGN, CIGN }, /* 0, PEOA */ @@ -2681,7 +2674,7 @@ static const char S_I_T[][3] = { { CCTL, CCTL, CCTL } /* 14, CTLESC ... */ #endif }; -#endif /* ASH_MATH_SUPPORT */ +#endif /* SH_MATH_SUPPORT */ #ifdef USE_SIT_FUNCTION @@ -4273,7 +4266,7 @@ cmdputs(const char *s) case CTLBACKQ+CTLQUOTE: str = "\"$(...)\""; goto dostr; -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT case CTLARI: str = "$(("; goto dostr; @@ -5258,17 +5251,8 @@ redirectsafe(union node *redir, int flags) * We have to deal with backquotes, shell variables, and file metacharacters. */ -#if ENABLE_ASH_MATH_SUPPORT_64 -typedef int64_t arith_t; -#define arith_t_type long long -#else -typedef long arith_t; -#define arith_t_type long -#endif - -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT static arith_t dash_arith(const char *); -static arith_t arith(const char *expr, int *perrcode); #endif /* @@ -5328,11 +5312,7 @@ cvtnum(arith_t num) int len; expdest = makestrspace(32, expdest); -#if ENABLE_ASH_MATH_SUPPORT_64 - len = fmtstr(expdest, 32, "%lld", (long long) num); -#else - len = fmtstr(expdest, 32, "%ld", num); -#endif + len = fmtstr(expdest, 32, arith_t_fmt, num); STADJUST(len, expdest); return len; } @@ -5696,7 +5676,7 @@ expbackq(union node *cmd, int quoted, int quotes) stackblock() + startloc)); } -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT /* * Expand arithmetic expression. Backup to start of expression, * evaluate, place result in (backed up) result, adjust string position. @@ -5782,7 +5762,7 @@ argstr(char *p, int flag, struct strlist *var_str_list) CTLVAR, CTLBACKQ, CTLBACKQ | CTLQUOTE, -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT CTLENDARI, #endif 0 @@ -5819,7 +5799,7 @@ argstr(char *p, int flag, struct strlist *var_str_list) length += strcspn(p + length, reject); c = p[length]; if (c && (!(c & 0x80) -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT || c == CTLENDARI #endif )) { @@ -5897,7 +5877,7 @@ argstr(char *p, int flag, struct strlist *var_str_list) expbackq(argbackq->n, c, quotes); argbackq = argbackq->next; goto start; -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT case CTLENDARI: p--; expari(quotes); @@ -6291,7 +6271,7 @@ static ssize_t varvalue(char *name, int varflags, int flags, struct strlist *var_str_list) { int num; - char *p; + const char *p; int i; int sep = 0; int sepq = 0; @@ -6324,14 +6304,13 @@ varvalue(char *name, int varflags, int flags, struct strlist *var_str_list) len = cvtnum(num); break; case '-': - p = makestrspace(NOPTS, expdest); + expdest = makestrspace(NOPTS, expdest); for (i = NOPTS - 1; i >= 0; i--) { if (optlist[i]) { - USTPUTC(optletters(i), p); + USTPUTC(optletters(i), expdest); len++; } } - expdest = p; break; case '@': if (sep) @@ -8710,7 +8689,7 @@ static int getoptscmd(int, char **); #if !ENABLE_FEATURE_SH_EXTRA_QUIET static int helpcmd(int, char **); #endif -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT static int letcmd(int, char **); #endif static int readcmd(int, char **); @@ -8792,7 +8771,7 @@ static const struct builtincmd builtintab[] = { { BUILTIN_REGULAR "jobs", jobscmd }, { BUILTIN_REGULAR "kill", killcmd }, #endif -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT { BUILTIN_NOSPEC "let", letcmd }, #endif { BUILTIN_ASSIGN "local", localcmd }, @@ -10935,7 +10914,7 @@ readtoken1(int firstc, int syntax, char *eofmark, int striptabs) USTPUTC(c, out); } break; -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT case CLP: /* '(' in arithmetic */ parenlevel++; USTPUTC(c, out); @@ -10991,7 +10970,7 @@ readtoken1(int firstc, int syntax, char *eofmark, int striptabs) } /* for (;;) */ } endword: -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT if (syntax == ARISYNTAX) raise_error_syntax("missing '))'"); #endif @@ -11168,7 +11147,7 @@ parsesub: { pungetc(); } else if (c == '(') { /* $(command) or $((arith)) */ if (pgetc() == '(') { -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT PARSEARITH(); #else raise_error_syntax("you disabled math support for $((arith)) syntax"); @@ -11423,7 +11402,7 @@ parsebackq: { goto parsebackq_newreturn; } -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT /* * Parse an arithmetic expansion (indicate start of one and set state) */ @@ -12384,7 +12363,7 @@ timescmd(int argc UNUSED_PARAM, char **argv UNUSED_PARAM) return 0; } -#if ENABLE_ASH_MATH_SUPPORT +#if ENABLE_SH_MATH_SUPPORT static arith_t dash_arith(const char *s) { @@ -12392,7 +12371,7 @@ dash_arith(const char *s) int errcode = 0; INT_OFF; - result = arith(s, &errcode); + result = arith(s, &errcode, &math_hooks); if (errcode < 0) { if (errcode == -3) ash_msg_and_raise_error("exponent less than 0"); @@ -12427,7 +12406,7 @@ letcmd(int argc UNUSED_PARAM, char **argv) return !i; } -#endif /* ASH_MATH_SUPPORT */ +#endif /* SH_MATH_SUPPORT */ /* ============ miscbltin.c @@ -12951,654 +12930,6 @@ ulimitcmd(int argc UNUSED_PARAM, char **argv UNUSED_PARAM) return 0; } - -/* ============ Math support */ - -#if ENABLE_ASH_MATH_SUPPORT - -/* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com> - - Permission is hereby granted, free of charge, to any person obtaining - a copy of this software and associated documentation files (the - "Software"), to deal in the Software without restriction, including - without limitation the rights to use, copy, modify, merge, publish, - distribute, sublicense, and/or sell copies of the Software, and to - permit persons to whom the Software is furnished to do so, subject to - the following conditions: - - The above copyright notice and this permission notice shall be - included in all copies or substantial portions of the Software. - - THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -*/ - -/* This is my infix parser/evaluator. It is optimized for size, intended - * as a replacement for yacc-based parsers. However, it may well be faster - * than a comparable parser written in yacc. The supported operators are - * listed in #defines below. Parens, order of operations, and error handling - * are supported. This code is thread safe. The exact expression format should - * be that which POSIX specifies for shells. */ - -/* The code uses a simple two-stack algorithm. See - * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html - * for a detailed explanation of the infix-to-postfix algorithm on which - * this is based (this code differs in that it applies operators immediately - * to the stack instead of adding them to a queue to end up with an - * expression). */ - -/* To use the routine, call it with an expression string and error return - * pointer */ - -/* - * Aug 24, 2001 Manuel Novoa III - * - * Reduced the generated code size by about 30% (i386) and fixed several bugs. - * - * 1) In arith_apply(): - * a) Cached values of *numptr and &(numptr[-1]). - * b) Removed redundant test for zero denominator. - * - * 2) In arith(): - * a) Eliminated redundant code for processing operator tokens by moving - * to a table-based implementation. Also folded handling of parens - * into the table. - * b) Combined all 3 loops which called arith_apply to reduce generated - * code size at the cost of speed. - * - * 3) The following expressions were treated as valid by the original code: - * 1() , 0! , 1 ( *3 ) . - * These bugs have been fixed by internally enclosing the expression in - * parens and then checking that all binary ops and right parens are - * preceded by a valid expression (NUM_TOKEN). - * - * Note: It may be desirable to replace Aaron's test for whitespace with - * ctype's isspace() if it is used by another busybox applet or if additional - * whitespace chars should be considered. Look below the "#include"s for a - * precompiler test. - */ - -/* - * Aug 26, 2001 Manuel Novoa III - * - * Return 0 for null expressions. Pointed out by Vladimir Oleynik. - * - * Merge in Aaron's comments previously posted to the busybox list, - * modified slightly to take account of my changes to the code. - * - */ - -/* - * (C) 2003 Vladimir Oleynik <dzo@simtreas.ru> - * - * - allow access to variable, - * used recursive find value indirection (c=2*2; a="c"; $((a+=2)) produce 6) - * - realize assign syntax (VAR=expr, +=, *= etc) - * - realize exponentiation (** operator) - * - realize comma separated - expr, expr - * - realise ++expr --expr expr++ expr-- - * - realise expr ? expr : expr (but, second expr calculate always) - * - allow hexadecimal and octal numbers - * - was restored loses XOR operator - * - remove one goto label, added three ;-) - * - protect $((num num)) as true zero expr (Manuel`s error) - * - always use special isspace(), see comment from bash ;-) - */ - -#define arith_isspace(arithval) \ - (arithval == ' ' || arithval == '\n' || arithval == '\t') - -typedef unsigned char operator; - -/* An operator's token id is a bit of a bitfield. The lower 5 bits are the - * precedence, and 3 high bits are an ID unique across operators of that - * precedence. The ID portion is so that multiple operators can have the - * same precedence, ensuring that the leftmost one is evaluated first. - * Consider * and /. */ - -#define tok_decl(prec,id) (((id)<<5)|(prec)) -#define PREC(op) ((op) & 0x1F) - -#define TOK_LPAREN tok_decl(0,0) - -#define TOK_COMMA tok_decl(1,0) - -#define TOK_ASSIGN tok_decl(2,0) -#define TOK_AND_ASSIGN tok_decl(2,1) -#define TOK_OR_ASSIGN tok_decl(2,2) -#define TOK_XOR_ASSIGN tok_decl(2,3) -#define TOK_PLUS_ASSIGN tok_decl(2,4) -#define TOK_MINUS_ASSIGN tok_decl(2,5) -#define TOK_LSHIFT_ASSIGN tok_decl(2,6) -#define TOK_RSHIFT_ASSIGN tok_decl(2,7) - -#define TOK_MUL_ASSIGN tok_decl(3,0) -#define TOK_DIV_ASSIGN tok_decl(3,1) -#define TOK_REM_ASSIGN tok_decl(3,2) - -/* all assign is right associativity and precedence eq, but (7+3)<<5 > 256 */ -#define convert_prec_is_assing(prec) do { if (prec == 3) prec = 2; } while (0) - -/* conditional is right associativity too */ -#define TOK_CONDITIONAL tok_decl(4,0) -#define TOK_CONDITIONAL_SEP tok_decl(4,1) - -#define TOK_OR tok_decl(5,0) - -#define TOK_AND tok_decl(6,0) - -#define TOK_BOR tok_decl(7,0) - -#define TOK_BXOR tok_decl(8,0) - -#define TOK_BAND tok_decl(9,0) - -#define TOK_EQ tok_decl(10,0) -#define TOK_NE tok_decl(10,1) - -#define TOK_LT tok_decl(11,0) -#define TOK_GT tok_decl(11,1) -#define TOK_GE tok_decl(11,2) -#define TOK_LE tok_decl(11,3) - -#define TOK_LSHIFT tok_decl(12,0) -#define TOK_RSHIFT tok_decl(12,1) - -#define TOK_ADD tok_decl(13,0) -#define TOK_SUB tok_decl(13,1) - -#define TOK_MUL tok_decl(14,0) -#define TOK_DIV tok_decl(14,1) -#define TOK_REM tok_decl(14,2) - -/* exponent is right associativity */ -#define TOK_EXPONENT tok_decl(15,1) - -/* For now unary operators. */ -#define UNARYPREC 16 -#define TOK_BNOT tok_decl(UNARYPREC,0) -#define TOK_NOT tok_decl(UNARYPREC,1) - -#define TOK_UMINUS tok_decl(UNARYPREC+1,0) -#define TOK_UPLUS tok_decl(UNARYPREC+1,1) - -#define PREC_PRE (UNARYPREC+2) - -#define TOK_PRE_INC tok_decl(PREC_PRE, 0) -#define TOK_PRE_DEC tok_decl(PREC_PRE, 1) - -#define PREC_POST (UNARYPREC+3) - -#define TOK_POST_INC tok_decl(PREC_POST, 0) -#define TOK_POST_DEC tok_decl(PREC_POST, 1) - -#define SPEC_PREC (UNARYPREC+4) - -#define TOK_NUM tok_decl(SPEC_PREC, 0) -#define TOK_RPAREN tok_decl(SPEC_PREC, 1) - -#define NUMPTR (*numstackptr) - -static int -tok_have_assign(operator op) -{ - operator prec = PREC(op); - - convert_prec_is_assing(prec); - return (prec == PREC(TOK_ASSIGN) || - prec == PREC_PRE || prec == PREC_POST); -} - -static int -is_right_associativity(operator prec) -{ - return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT) - || prec == PREC(TOK_CONDITIONAL)); -} - -typedef struct { - arith_t val; - arith_t contidional_second_val; - char contidional_second_val_initialized; - char *var; /* if NULL then is regular number, - else is variable name */ -} v_n_t; - -typedef struct chk_var_recursive_looped_t { - const char *var; - struct chk_var_recursive_looped_t *next; -} chk_var_recursive_looped_t; - -static chk_var_recursive_looped_t *prev_chk_var_recursive; - -static int -arith_lookup_val(v_n_t *t) -{ - if (t->var) { - const char * p = lookupvar(t->var); - - if (p) { - int errcode; - - /* recursive try as expression */ - chk_var_recursive_looped_t *cur; - chk_var_recursive_looped_t cur_save; - - for (cur = prev_chk_var_recursive; cur; cur = cur->next) { - if (strcmp(cur->var, t->var) == 0) { - /* expression recursion loop detected */ - return -5; - } - } - /* save current lookuped var name */ - cur = prev_chk_var_recursive; - cur_save.var = t->var; - cur_save.next = cur; - prev_chk_var_recursive = &cur_save; - - t->val = arith (p, &errcode); - /* restore previous ptr after recursiving */ - prev_chk_var_recursive = cur; - return errcode; - } - /* allow undefined var as 0 */ - t->val = 0; - } - return 0; -} - -/* "applying" a token means performing it on the top elements on the integer - * stack. For a unary operator it will only change the top element, but a - * binary operator will pop two arguments and push a result */ -static int -arith_apply(operator op, v_n_t *numstack, v_n_t **numstackptr) -{ - v_n_t *numptr_m1; - arith_t numptr_val, rez; - int ret_arith_lookup_val; - - /* There is no operator that can work without arguments */ - if (NUMPTR == numstack) goto err; - numptr_m1 = NUMPTR - 1; - - /* check operand is var with noninteger value */ - ret_arith_lookup_val = arith_lookup_val(numptr_m1); - if (ret_arith_lookup_val) - return ret_arith_lookup_val; - - rez = numptr_m1->val; - if (op == TOK_UMINUS) - rez *= -1; - else if (op == TOK_NOT) - rez = !rez; - else if (op == TOK_BNOT) - rez = ~rez; - else if (op == TOK_POST_INC || op == TOK_PRE_INC) - rez++; - else if (op == TOK_POST_DEC || op == TOK_PRE_DEC) - rez--; - else if (op != TOK_UPLUS) { - /* Binary operators */ - - /* check and binary operators need two arguments */ - if (numptr_m1 == numstack) goto err; - - /* ... and they pop one */ - --NUMPTR; - numptr_val = rez; - if (op == TOK_CONDITIONAL) { - if (!numptr_m1->contidional_second_val_initialized) { - /* protect $((expr1 ? expr2)) without ": expr" */ - goto err; - } - rez = numptr_m1->contidional_second_val; - } else if (numptr_m1->contidional_second_val_initialized) { - /* protect $((expr1 : expr2)) without "expr ? " */ - goto err; - } - numptr_m1 = NUMPTR - 1; - if (op != TOK_ASSIGN) { - /* check operand is var with noninteger value for not '=' */ - ret_arith_lookup_val = arith_lookup_val(numptr_m1); - if (ret_arith_lookup_val) - return ret_arith_lookup_val; - } - if (op == TOK_CONDITIONAL) { - numptr_m1->contidional_second_val = rez; - } - rez = numptr_m1->val; - if (op == TOK_BOR || op == TOK_OR_ASSIGN) - rez |= numptr_val; - else if (op == TOK_OR) - rez = numptr_val || rez; - else if (op == TOK_BAND || op == TOK_AND_ASSIGN) - rez &= numptr_val; - else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN) - rez ^= numptr_val; - else if (op == TOK_AND) - rez = rez && numptr_val; - else if (op == TOK_EQ) - rez = (rez == numptr_val); - else if (op == TOK_NE) - rez = (rez != numptr_val); - else if (op == TOK_GE) - rez = (rez >= numptr_val); - else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN) - rez >>= numptr_val; - else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN) - rez <<= numptr_val; - else if (op == TOK_GT) - rez = (rez > numptr_val); - else if (op == TOK_LT) - rez = (rez < numptr_val); - else if (op == TOK_LE) - rez = (rez <= numptr_val); - else if (op == TOK_MUL || op == TOK_MUL_ASSIGN) - rez *= numptr_val; - else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN) - rez += numptr_val; - else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN) - rez -= numptr_val; - else if (op == TOK_ASSIGN || op == TOK_COMMA) - rez = numptr_val; - else if (op == TOK_CONDITIONAL_SEP) { - if (numptr_m1 == numstack) { - /* protect $((expr : expr)) without "expr ? " */ - goto err; - } - numptr_m1->contidional_second_val_initialized = op; - numptr_m1->contidional_second_val = numptr_val; - } else if (op == TOK_CONDITIONAL) { - rez = rez ? - numptr_val : numptr_m1->contidional_second_val; - } else if (op == TOK_EXPONENT) { - if (numptr_val < 0) - return -3; /* exponent less than 0 */ - else { - arith_t c = 1; - - if (numptr_val) - while (numptr_val--) - c *= rez; - rez = c; - } - } else if (numptr_val==0) /* zero divisor check */ - return -2; - else if (op == TOK_DIV || op == TOK_DIV_ASSIGN) - rez /= numptr_val; - else if (op == TOK_REM || op == TOK_REM_ASSIGN) - rez %= numptr_val; - } - if (tok_have_assign(op)) { - char buf[sizeof(arith_t_type)*3 + 2]; - - if (numptr_m1->var == NULL) { - /* Hmm, 1=2 ? */ - goto err; - } - /* save to shell variable */ -#if ENABLE_ASH_MATH_SUPPORT_64 - snprintf(buf, sizeof(buf), "%lld", (arith_t_type) rez); -#else - snprintf(buf, sizeof(buf), "%ld", (arith_t_type) rez); -#endif - setvar(numptr_m1->var, buf, 0); - /* after saving, make previous value for v++ or v-- */ - if (op == TOK_POST_INC) - rez--; - else if (op == TOK_POST_DEC) - rez++; - } - numptr_m1->val = rez; - /* protect geting var value, is number now */ - numptr_m1->var = NULL; - return 0; - err: - return -1; -} - -/* longest must be first */ -static const char op_tokens[] ALIGN1 = { - '<','<','=',0, TOK_LSHIFT_ASSIGN, - '>','>','=',0, TOK_RSHIFT_ASSIGN, - '<','<', 0, TOK_LSHIFT, - '>','>', 0, TOK_RSHIFT, - '|','|', 0, TOK_OR, - '&','&', 0, TOK_AND, - '!','=', 0, TOK_NE, - '<','=', 0, TOK_LE, - '>','=', 0, TOK_GE, - '=','=', 0, TOK_EQ, - '|','=', 0, TOK_OR_ASSIGN, - '&','=', 0, TOK_AND_ASSIGN, - '*','=', 0, TOK_MUL_ASSIGN, - '/','=', 0, TOK_DIV_ASSIGN, - '%','=', 0, TOK_REM_ASSIGN, - '+','=', 0, TOK_PLUS_ASSIGN, - '-','=', 0, TOK_MINUS_ASSIGN, - '-','-', 0, TOK_POST_DEC, - '^','=', 0, TOK_XOR_ASSIGN, - '+','+', 0, TOK_POST_INC, - '*','*', 0, TOK_EXPONENT, - '!', 0, TOK_NOT, - '<', 0, TOK_LT, - '>', 0, TOK_GT, - '=', 0, TOK_ASSIGN, - '|', 0, TOK_BOR, - '&', 0, TOK_BAND, - '*', 0, TOK_MUL, - '/', 0, TOK_DIV, - '%', 0, TOK_REM, - '+', 0, TOK_ADD, - '-', 0, TOK_SUB, - '^', 0, TOK_BXOR, - /* uniq */ - '~', 0, TOK_BNOT, - ',', 0, TOK_COMMA, - '?', 0, TOK_CONDITIONAL, - ':', 0, TOK_CONDITIONAL_SEP, - ')', 0, TOK_RPAREN, - '(', 0, TOK_LPAREN, - 0 -}; -/* ptr to ")" */ -#define endexpression (&op_tokens[sizeof(op_tokens)-7]) - -static arith_t -arith(const char *expr, int *perrcode) -{ - char arithval; /* Current character under analysis */ - operator lasttok, op; - operator prec; - operator *stack, *stackptr; - const char *p = endexpression; - int errcode; - v_n_t *numstack, *numstackptr; - unsigned datasizes = strlen(expr) + 2; - - /* Stack of integers */ - /* The proof that there can be no more than strlen(startbuf)/2+1 integers - * in any given correct or incorrect expression is left as an exercise to - * the reader. */ - numstackptr = numstack = alloca((datasizes / 2) * sizeof(numstack[0])); - /* Stack of operator tokens */ - stackptr = stack = alloca(datasizes * sizeof(stack[0])); - - *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */ - *perrcode = errcode = 0; - - while (1) { - arithval = *expr; - if (arithval == 0) { - if (p == endexpression) { - /* Null expression. */ - return 0; - } - - /* This is only reached after all tokens have been extracted from the - * input stream. If there are still tokens on the operator stack, they - * are to be applied in order. At the end, there should be a final - * result on the integer stack */ - - if (expr != endexpression + 1) { - /* If we haven't done so already, */ - /* append a closing right paren */ - expr = endexpression; - /* and let the loop process it. */ - continue; - } - /* At this point, we're done with the expression. */ - if (numstackptr != numstack+1) { - /* ... but if there isn't, it's bad */ - err: - *perrcode = -1; - return *perrcode; - } - if (numstack->var) { - /* expression is $((var)) only, lookup now */ - errcode = arith_lookup_val(numstack); - } - ret: - *perrcode = errcode; - return numstack->val; - } - - /* Continue processing the expression. */ - if (arith_isspace(arithval)) { - /* Skip whitespace */ - goto prologue; - } - p = endofname(expr); - if (p != expr) { - size_t var_name_size = (p-expr) + 1; /* trailing zero */ - - numstackptr->var = alloca(var_name_size); - safe_strncpy(numstackptr->var, expr, var_name_size); - expr = p; - num: - numstackptr->contidional_second_val_initialized = 0; - numstackptr++; - lasttok = TOK_NUM; - continue; - } - if (isdigit(arithval)) { - numstackptr->var = NULL; -#if ENABLE_ASH_MATH_SUPPORT_64 - numstackptr->val = strtoll(expr, (char **) &expr, 0); -#else - numstackptr->val = strtol(expr, (char **) &expr, 0); -#endif - goto num; - } - for (p = op_tokens; ; p++) { - const char *o; - - if (*p == 0) { - /* strange operator not found */ - goto err; - } - for (o = expr; *p && *o == *p; p++) - o++; - if (!*p) { - /* found */ - expr = o - 1; - break; - } - /* skip tail uncompared token */ - while (*p) - p++; - /* skip zero delim */ - p++; - } - op = p[1]; - - /* post grammar: a++ reduce to num */ - if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC) - lasttok = TOK_NUM; - - /* Plus and minus are binary (not unary) _only_ if the last - * token was as number, or a right paren (which pretends to be - * a number, since it evaluates to one). Think about it. - * It makes sense. */ - if (lasttok != TOK_NUM) { - switch (op) { - case TOK_ADD: - op = TOK_UPLUS; - break; - case TOK_SUB: - op = TOK_UMINUS; - break; - case TOK_POST_INC: - op = TOK_PRE_INC; - break; - case TOK_POST_DEC: - op = TOK_PRE_DEC; - break; - } - } - /* We don't want a unary operator to cause recursive descent on the - * stack, because there can be many in a row and it could cause an - * operator to be evaluated before its argument is pushed onto the - * integer stack. */ - /* But for binary operators, "apply" everything on the operator - * stack until we find an operator with a lesser priority than the - * one we have just extracted. */ - /* Left paren is given the lowest priority so it will never be - * "applied" in this way. - * if associativity is right and priority eq, applied also skip - */ - prec = PREC(op); - if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) { - /* not left paren or unary */ - if (lasttok != TOK_NUM) { - /* binary op must be preceded by a num */ - goto err; - } - while (stackptr != stack) { - if (op == TOK_RPAREN) { - /* The algorithm employed here is simple: while we don't - * hit an open paren nor the bottom of the stack, pop - * tokens and apply them */ - if (stackptr[-1] == TOK_LPAREN) { - --stackptr; - /* Any operator directly after a */ - lasttok = TOK_NUM; - /* close paren should consider itself binary */ - goto prologue; - } - } else { - operator prev_prec = PREC(stackptr[-1]); - - convert_prec_is_assing(prec); - convert_prec_is_assing(prev_prec); - if (prev_prec < prec) - break; - /* check right assoc */ - if (prev_prec == prec && is_right_associativity(prec)) - break; - } - errcode = arith_apply(*--stackptr, numstack, &numstackptr); - if (errcode) goto ret; - } - if (op == TOK_RPAREN) { - goto err; - } - } - - /* Push this operator to the stack and remember it. */ - *stackptr++ = lasttok = op; - prologue: - ++expr; - } /* while */ -} -#endif /* ASH_MATH_SUPPORT */ - - /* ============ main() and helpers */ /* @@ -13786,7 +13117,7 @@ extern int etext(); int ash_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; int ash_main(int argc UNUSED_PARAM, char **argv) { - char *shinit; + const char *shinit; volatile smallint state; struct jmploc jmploc; struct stackmark smark; @@ -13799,6 +13130,11 @@ int ash_main(int argc UNUSED_PARAM, char **argv) INIT_G_alias(); #endif INIT_G_cmdtable(); +#if ENABLE_SH_MATH_SUPPORT + math_hooks.lookupvar = lookupvar; + math_hooks.setvar = setvar; + math_hooks.endofname = endofname; +#endif #if PROFILE monitor(4, etext, profile_buf, sizeof(profile_buf), 50); diff --git a/shell/hush.c b/shell/hush.c index af6763517..e93e5a9a0 100644 --- a/shell/hush.c +++ b/shell/hush.c @@ -76,6 +76,8 @@ #include <fnmatch.h> #endif +#include "math.h" + #define HUSH_VER_STR "0.92" #if defined SINGLE_APPLET_MAIN @@ -452,6 +454,9 @@ struct globals { #if ENABLE_FEATURE_EDITING line_input_t *line_input_state; #endif +#if ENABLE_SH_MATH_SUPPORT + arith_eval_hooks_t hooks; +#endif pid_t root_pid; pid_t last_bg_pid; #if ENABLE_HUSH_JOB @@ -1164,6 +1169,31 @@ static int unset_local_var(const char *name) return EXIT_SUCCESS; } +#if ENABLE_SH_MATH_SUPPORT +#define is_name(c) ((c) == '_' || isalpha((unsigned char)(c))) +#define is_in_name(c) ((c) == '_' || isalnum((unsigned char)(c))) +static char *endofname(const char *name) +{ + char *p; + + p = (char *) name; + if (!is_name(*p)) + return p; + while (*++p) { + if (!is_in_name(*p)) + break; + } + return p; +} + +static void arith_set_local_var(const char *name, const char *val, int flags) +{ + /* arith code doesnt malloc space, so do it for it */ + char *var = xmalloc(strlen(name) + 1 + strlen(val) + 1); + sprintf(var, "%s=%s", name, val); + set_local_var(var, flags); +} +#endif /* * in_str support @@ -1374,6 +1404,11 @@ static void o_addstr(o_string *o, const char *str, int len) o->data[o->length] = '\0'; } +static void o_addstrauto(o_string *o, const char *str) +{ + o_addstr(o, str, strlen(str) + 1); +} + static void o_addstr_duplicate_backslash(o_string *o, const char *str, int len) { while (len) { @@ -1564,7 +1599,7 @@ static int o_glob(o_string *o, int n) char **argv = globdata.gl_pathv; o->length = pattern - o->data; /* "forget" pattern */ while (1) { - o_addstr(o, *argv, strlen(*argv) + 1); + o_addstrauto(o, *argv); n = o_save_ptr_helper(o, n); argv++; if (!*argv) @@ -1770,6 +1805,28 @@ static int expand_vars_to_list(o_string *output, int n, char *arg, char or_mask) goto store_val; } #endif +#if ENABLE_SH_MATH_SUPPORT + case '+': { /* <SPECIAL_VAR_SYMBOL>(cmd<SPECIAL_VAR_SYMBOL> */ + arith_t res; + char buf[30]; + int errcode; + *p = '\0'; + ++arg; + debug_printf_subst("ARITH '%s' first_ch %x\n", arg, first_ch); + res = arith(arg, &errcode, &G.hooks); + if (errcode < 0) + switch (errcode) { + case -3: maybe_die("arith", "exponent less than 0"); break; + case -2: maybe_die("arith", "divide by zero"); break; + case -5: maybe_die("arith", "expression recursion loop detected"); break; + default: maybe_die("arith", "syntax error"); + } + sprintf(buf, arith_t_fmt, res); + o_addstrauto(output, buf); + debug_printf_subst("ARITH RES '"arith_t_fmt"'\n", res); + break; + } +#endif default: /* <SPECIAL_VAR_SYMBOL>varname<SPECIAL_VAR_SYMBOL> */ case_default: { bool exp_len = false, exp_null = false; @@ -1877,7 +1934,7 @@ static int expand_vars_to_list(o_string *output, int n, char *arg, char or_mask) debug_print_list("expand_vars_to_list[a]", output, n); /* this part is literal, and it was already pre-quoted * if needed (much earlier), do not use o_addQstr here! */ - o_addstr(output, arg, strlen(arg) + 1); + o_addstrauto(output, arg); debug_print_list("expand_vars_to_list[b]", output, n); } else if (output->length == o_get_last_ptr(output, n) /* expansion is empty */ && !(ored_ch & 0x80) /* and all vars were not quoted. */ @@ -3754,7 +3811,7 @@ static int parse_group(o_string *dest, struct parse_context *ctx, /* command remains "open", available for possible redirects */ } -#if ENABLE_HUSH_TICK +#if ENABLE_HUSH_TICK || ENABLE_SH_MATH_SUPPORT /* Subroutines for copying $(...) and `...` things */ static void add_till_backquote(o_string *dest, struct in_str *input); /* '...' */ @@ -3834,7 +3891,7 @@ static void add_till_backquote(o_string *dest, struct in_str *input) * echo $(echo 'TEST)' BEST) TEST) BEST * echo $(echo \(\(TEST\) BEST) ((TEST) BEST */ -static void add_till_closing_curly_brace(o_string *dest, struct in_str *input) +static void add_till_closing_paren(o_string *dest, struct in_str *input, bool dbl) { int count = 0; while (1) { @@ -3844,8 +3901,14 @@ static void add_till_closing_curly_brace(o_string *dest, struct in_str *input) if (ch == '(') count++; if (ch == ')') - if (--count < 0) - break; + if (--count < 0) { + if (!dbl) + break; + if (i_peek(input) == ')') { + i_getch(input); + break; + } + } o_addchr(dest, ch); if (ch == '\'') { add_till_single_quote(dest, input); @@ -3866,7 +3929,7 @@ static void add_till_closing_curly_brace(o_string *dest, struct in_str *input) } } } -#endif /* ENABLE_HUSH_TICK */ +#endif /* ENABLE_HUSH_TICK || ENABLE_SH_MATH_SUPPORT */ /* Return code: 0 for OK, 1 for syntax error */ static int handle_dollar(o_string *dest, struct in_str *input) @@ -3983,18 +4046,30 @@ static int handle_dollar(o_string *dest, struct in_str *input) o_addchr(dest, SPECIAL_VAR_SYMBOL); break; } -#if ENABLE_HUSH_TICK case '(': { - //int pos = dest->length; i_getch(input); + +#if ENABLE_SH_MATH_SUPPORT + if (i_peek(input) == '(') { + i_getch(input); + o_addchr(dest, SPECIAL_VAR_SYMBOL); + o_addchr(dest, quote_mask | '+'); + add_till_closing_paren(dest, input, true); + o_addchr(dest, SPECIAL_VAR_SYMBOL); + break; + } +#endif + +#if ENABLE_HUSH_TICK + //int pos = dest->length; o_addchr(dest, SPECIAL_VAR_SYMBOL); o_addchr(dest, quote_mask | '`'); - add_till_closing_curly_brace(dest, input); + add_till_closing_paren(dest, input, false); //debug_printf_subst("SUBST RES2 '%s'\n", dest->data + pos); o_addchr(dest, SPECIAL_VAR_SYMBOL); +#endif break; } -#endif case '_': i_getch(input); ch = i_peek(input); @@ -4526,6 +4601,11 @@ int hush_main(int argc, char **argv) #if ENABLE_FEATURE_EDITING G.line_input_state = new_line_input_t(FOR_SHELL); #endif +#if ENABLE_SH_MATH_SUPPORT + G.hooks.lookupvar = lookup_param; + G.hooks.setvar = arith_set_local_var; + G.hooks.endofname = endofname; +#endif /* XXX what should these be while sourcing /etc/profile? */ G.global_argc = argc; G.global_argv = argv; diff --git a/shell/math.c b/shell/math.c new file mode 100644 index 000000000..9a46a937e --- /dev/null +++ b/shell/math.c @@ -0,0 +1,701 @@ +/* + * arithmetic code ripped out of ash shell for code sharing + * + * Copyright (c) 1989, 1991, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au> + * was re-ported from NetBSD and debianized. + * + * This code is derived from software contributed to Berkeley by + * Kenneth Almquist. + * + * Licensed under the GPL v2 or later, see the file LICENSE in this tarball. + * + * Original BSD copyright notice is retained at the end of this file. + */ +/* + * rewrite arith.y to micro stack based cryptic algorithm by + * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com> + * + * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support + * dynamic variables. + * + * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be + * used in busybox and size optimizations, + * rewrote arith (see notes to this), added locale support, + * rewrote dynamic variables. + */ + +#include "busybox.h" +#include "math.h" + +#define a_e_h_t arith_eval_hooks_t +#define lookupvar (math_hooks->lookupvar) +#define setvar (math_hooks->setvar) +#define endofname (math_hooks->endofname) + +/* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com> + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY + CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +*/ + +/* This is my infix parser/evaluator. It is optimized for size, intended + * as a replacement for yacc-based parsers. However, it may well be faster + * than a comparable parser written in yacc. The supported operators are + * listed in #defines below. Parens, order of operations, and error handling + * are supported. This code is thread safe. The exact expression format should + * be that which POSIX specifies for shells. */ + +/* The code uses a simple two-stack algorithm. See + * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html + * for a detailed explanation of the infix-to-postfix algorithm on which + * this is based (this code differs in that it applies operators immediately + * to the stack instead of adding them to a queue to end up with an + * expression). */ + +/* To use the routine, call it with an expression string and error return + * pointer */ + +/* + * Aug 24, 2001 Manuel Novoa III + * + * Reduced the generated code size by about 30% (i386) and fixed several bugs. + * + * 1) In arith_apply(): + * a) Cached values of *numptr and &(numptr[-1]). + * b) Removed redundant test for zero denominator. + * + * 2) In arith(): + * a) Eliminated redundant code for processing operator tokens by moving + * to a table-based implementation. Also folded handling of parens + * into the table. + * b) Combined all 3 loops which called arith_apply to reduce generated + * code size at the cost of speed. + * + * 3) The following expressions were treated as valid by the original code: + * 1() , 0! , 1 ( *3 ) . + * These bugs have been fixed by internally enclosing the expression in + * parens and then checking that all binary ops and right parens are + * preceded by a valid expression (NUM_TOKEN). + * + * Note: It may be desirable to replace Aaron's test for whitespace with + * ctype's isspace() if it is used by another busybox applet or if additional + * whitespace chars should be considered. Look below the "#include"s for a + * precompiler test. + */ + +/* + * Aug 26, 2001 Manuel Novoa III + * + * Return 0 for null expressions. Pointed out by Vladimir Oleynik. + * + * Merge in Aaron's comments previously posted to the busybox list, + * modified slightly to take account of my changes to the code. + * + */ + +/* + * (C) 2003 Vladimir Oleynik <dzo@simtreas.ru> + * + * - allow access to variable, + * used recursive find value indirection (c=2*2; a="c"; $((a+=2)) produce 6) + * - realize assign syntax (VAR=expr, +=, *= etc) + * - realize exponentiation (** operator) + * - realize comma separated - expr, expr + * - realise ++expr --expr expr++ expr-- + * - realise expr ? expr : expr (but, second expr calculate always) + * - allow hexadecimal and octal numbers + * - was restored loses XOR operator + * - remove one goto label, added three ;-) + * - protect $((num num)) as true zero expr (Manuel`s error) + * - always use special isspace(), see comment from bash ;-) + */ + +#define arith_isspace(arithval) \ + (arithval == ' ' || arithval == '\n' || arithval == '\t') + +typedef unsigned char operator; + +/* An operator's token id is a bit of a bitfield. The lower 5 bits are the + * precedence, and 3 high bits are an ID unique across operators of that + * precedence. The ID portion is so that multiple operators can have the + * same precedence, ensuring that the leftmost one is evaluated first. + * Consider * and /. */ + +#define tok_decl(prec,id) (((id)<<5)|(prec)) +#define PREC(op) ((op) & 0x1F) + +#define TOK_LPAREN tok_decl(0,0) + +#define TOK_COMMA tok_decl(1,0) + +#define TOK_ASSIGN tok_decl(2,0) +#define TOK_AND_ASSIGN tok_decl(2,1) +#define TOK_OR_ASSIGN tok_decl(2,2) +#define TOK_XOR_ASSIGN tok_decl(2,3) +#define TOK_PLUS_ASSIGN tok_decl(2,4) +#define TOK_MINUS_ASSIGN tok_decl(2,5) +#define TOK_LSHIFT_ASSIGN tok_decl(2,6) +#define TOK_RSHIFT_ASSIGN tok_decl(2,7) + +#define TOK_MUL_ASSIGN tok_decl(3,0) +#define TOK_DIV_ASSIGN tok_decl(3,1) +#define TOK_REM_ASSIGN tok_decl(3,2) + +/* all assign is right associativity and precedence eq, but (7+3)<<5 > 256 */ +#define convert_prec_is_assing(prec) do { if (prec == 3) prec = 2; } while (0) + +/* conditional is right associativity too */ +#define TOK_CONDITIONAL tok_decl(4,0) +#define TOK_CONDITIONAL_SEP tok_decl(4,1) + +#define TOK_OR tok_decl(5,0) + +#define TOK_AND tok_decl(6,0) + +#define TOK_BOR tok_decl(7,0) + +#define TOK_BXOR tok_decl(8,0) + +#define TOK_BAND tok_decl(9,0) + +#define TOK_EQ tok_decl(10,0) +#define TOK_NE tok_decl(10,1) + +#define TOK_LT tok_decl(11,0) +#define TOK_GT tok_decl(11,1) +#define TOK_GE tok_decl(11,2) +#define TOK_LE tok_decl(11,3) + +#define TOK_LSHIFT tok_decl(12,0) +#define TOK_RSHIFT tok_decl(12,1) + +#define TOK_ADD tok_decl(13,0) +#define TOK_SUB tok_decl(13,1) + +#define TOK_MUL tok_decl(14,0) +#define TOK_DIV tok_decl(14,1) +#define TOK_REM tok_decl(14,2) + +/* exponent is right associativity */ +#define TOK_EXPONENT tok_decl(15,1) + +/* For now unary operators. */ +#define UNARYPREC 16 +#define TOK_BNOT tok_decl(UNARYPREC,0) +#define TOK_NOT tok_decl(UNARYPREC,1) + +#define TOK_UMINUS tok_decl(UNARYPREC+1,0) +#define TOK_UPLUS tok_decl(UNARYPREC+1,1) + +#define PREC_PRE (UNARYPREC+2) + +#define TOK_PRE_INC tok_decl(PREC_PRE, 0) +#define TOK_PRE_DEC tok_decl(PREC_PRE, 1) + +#define PREC_POST (UNARYPREC+3) + +#define TOK_POST_INC tok_decl(PREC_POST, 0) +#define TOK_POST_DEC tok_decl(PREC_POST, 1) + +#define SPEC_PREC (UNARYPREC+4) + +#define TOK_NUM tok_decl(SPEC_PREC, 0) +#define TOK_RPAREN tok_decl(SPEC_PREC, 1) + +#define NUMPTR (*numstackptr) + +static int +tok_have_assign(operator op) +{ + operator prec = PREC(op); + + convert_prec_is_assing(prec); + return (prec == PREC(TOK_ASSIGN) || + prec == PREC_PRE || prec == PREC_POST); +} + +static int +is_right_associativity(operator prec) +{ + return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT) + || prec == PREC(TOK_CONDITIONAL)); +} + +typedef struct { + arith_t val; + arith_t contidional_second_val; + char contidional_second_val_initialized; + char *var; /* if NULL then is regular number, + else is variable name */ +} v_n_t; + +typedef struct chk_var_recursive_looped_t { + const char *var; + struct chk_var_recursive_looped_t *next; +} chk_var_recursive_looped_t; + +static chk_var_recursive_looped_t *prev_chk_var_recursive; + +static int +arith_lookup_val(v_n_t *t, a_e_h_t *math_hooks) +{ + if (t->var) { + const char * p = lookupvar(t->var); + + if (p) { + int errcode; + + /* recursive try as expression */ + chk_var_recursive_looped_t *cur; + chk_var_recursive_looped_t cur_save; + + for (cur = prev_chk_var_recursive; cur; cur = cur->next) { + if (strcmp(cur->var, t->var) == 0) { + /* expression recursion loop detected */ + return -5; + } + } + /* save current lookuped var name */ + cur = prev_chk_var_recursive; + cur_save.var = t->var; + cur_save.next = cur; + prev_chk_var_recursive = &cur_save; + + t->val = arith (p, &errcode, math_hooks); + /* restore previous ptr after recursiving */ + prev_chk_var_recursive = cur; + return errcode; + } + /* allow undefined var as 0 */ + t->val = 0; + } + return 0; +} + +/* "applying" a token means performing it on the top elements on the integer + * stack. For a unary operator it will only change the top element, but a + * binary operator will pop two arguments and push a result */ +static int +arith_apply(operator op, v_n_t *numstack, v_n_t **numstackptr, a_e_h_t *math_hooks) +{ + v_n_t *numptr_m1; + arith_t numptr_val, rez; + int ret_arith_lookup_val; + + /* There is no operator that can work without arguments */ + if (NUMPTR == numstack) goto err; + numptr_m1 = NUMPTR - 1; + + /* check operand is var with noninteger value */ + ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks); + if (ret_arith_lookup_val) + return ret_arith_lookup_val; + + rez = numptr_m1->val; + if (op == TOK_UMINUS) + rez *= -1; + else if (op == TOK_NOT) + rez = !rez; + else if (op == TOK_BNOT) + rez = ~rez; + else if (op == TOK_POST_INC || op == TOK_PRE_INC) + rez++; + else if (op == TOK_POST_DEC || op == TOK_PRE_DEC) + rez--; + else if (op != TOK_UPLUS) { + /* Binary operators */ + + /* check and binary operators need two arguments */ + if (numptr_m1 == numstack) goto err; + + /* ... and they pop one */ + --NUMPTR; + numptr_val = rez; + if (op == TOK_CONDITIONAL) { + if (!numptr_m1->contidional_second_val_initialized) { + /* protect $((expr1 ? expr2)) without ": expr" */ + goto err; + } + rez = numptr_m1->contidional_second_val; + } else if (numptr_m1->contidional_second_val_initialized) { + /* protect $((expr1 : expr2)) without "expr ? " */ + goto err; + } + numptr_m1 = NUMPTR - 1; + if (op != TOK_ASSIGN) { + /* check operand is var with noninteger value for not '=' */ + ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks); + if (ret_arith_lookup_val) + return ret_arith_lookup_val; + } + if (op == TOK_CONDITIONAL) { + numptr_m1->contidional_second_val = rez; + } + rez = numptr_m1->val; + if (op == TOK_BOR || op == TOK_OR_ASSIGN) + rez |= numptr_val; + else if (op == TOK_OR) + rez = numptr_val || rez; + else if (op == TOK_BAND || op == TOK_AND_ASSIGN) + rez &= numptr_val; + else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN) + rez ^= numptr_val; + else if (op == TOK_AND) + rez = rez && numptr_val; + else if (op == TOK_EQ) + rez = (rez == numptr_val); + else if (op == TOK_NE) + rez = (rez != numptr_val); + else if (op == TOK_GE) + rez = (rez >= numptr_val); + else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN) + rez >>= numptr_val; + else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN) + rez <<= numptr_val; + else if (op == TOK_GT) + rez = (rez > numptr_val); + else if (op == TOK_LT) + rez = (rez < numptr_val); + else if (op == TOK_LE) + rez = (rez <= numptr_val); + else if (op == TOK_MUL || op == TOK_MUL_ASSIGN) + rez *= numptr_val; + else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN) + rez += numptr_val; + else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN) + rez -= numptr_val; + else if (op == TOK_ASSIGN || op == TOK_COMMA) + rez = numptr_val; + else if (op == TOK_CONDITIONAL_SEP) { + if (numptr_m1 == numstack) { + /* protect $((expr : expr)) without "expr ? " */ + goto err; + } + numptr_m1->contidional_second_val_initialized = op; + numptr_m1->contidional_second_val = numptr_val; + } else if (op == TOK_CONDITIONAL) { + rez = rez ? + numptr_val : numptr_m1->contidional_second_val; + } else if (op == TOK_EXPONENT) { + if (numptr_val < 0) + return -3; /* exponent less than 0 */ + else { + arith_t c = 1; + + if (numptr_val) + while (numptr_val--) + c *= rez; + rez = c; + } + } else if (numptr_val==0) /* zero divisor check */ + return -2; + else if (op == TOK_DIV || op == TOK_DIV_ASSIGN) + rez /= numptr_val; + else if (op == TOK_REM || op == TOK_REM_ASSIGN) + rez %= numptr_val; + } + if (tok_have_assign(op)) { + char buf[sizeof(arith_t_type)*3 + 2]; + + if (numptr_m1->var == NULL) { + /* Hmm, 1=2 ? */ + goto err; + } + /* save to shell variable */ + snprintf(buf, sizeof(buf), arith_t_fmt, (arith_t_type) rez); + setvar(numptr_m1->var, buf, 0); + /* after saving, make previous value for v++ or v-- */ + if (op == TOK_POST_INC) + rez--; + else if (op == TOK_POST_DEC) + rez++; + } + numptr_m1->val = rez; + /* protect geting var value, is number now */ + numptr_m1->var = NULL; + return 0; + err: + return -1; +} + +/* longest must be first */ +static const char op_tokens[] ALIGN1 = { + '<','<','=',0, TOK_LSHIFT_ASSIGN, + '>','>','=',0, TOK_RSHIFT_ASSIGN, + '<','<', 0, TOK_LSHIFT, + '>','>', 0, TOK_RSHIFT, + '|','|', 0, TOK_OR, + '&','&', 0, TOK_AND, + '!','=', 0, TOK_NE, + '<','=', 0, TOK_LE, + '>','=', 0, TOK_GE, + '=','=', 0, TOK_EQ, + '|','=', 0, TOK_OR_ASSIGN, + '&','=', 0, TOK_AND_ASSIGN, + '*','=', 0, TOK_MUL_ASSIGN, + '/','=', 0, TOK_DIV_ASSIGN, + '%','=', 0, TOK_REM_ASSIGN, + '+','=', 0, TOK_PLUS_ASSIGN, + '-','=', 0, TOK_MINUS_ASSIGN, + '-','-', 0, TOK_POST_DEC, + '^','=', 0, TOK_XOR_ASSIGN, + '+','+', 0, TOK_POST_INC, + '*','*', 0, TOK_EXPONENT, + '!', 0, TOK_NOT, + '<', 0, TOK_LT, + '>', 0, TOK_GT, + '=', 0, TOK_ASSIGN, + '|', 0, TOK_BOR, + '&', 0, TOK_BAND, + '*', 0, TOK_MUL, + '/', 0, TOK_DIV, + '%', 0, TOK_REM, + '+', 0, TOK_ADD, + '-', 0, TOK_SUB, + '^', 0, TOK_BXOR, + /* uniq */ + '~', 0, TOK_BNOT, + ',', 0, TOK_COMMA, + '?', 0, TOK_CONDITIONAL, + ':', 0, TOK_CONDITIONAL_SEP, + ')', 0, TOK_RPAREN, + '(', 0, TOK_LPAREN, + 0 +}; +/* ptr to ")" */ +#define endexpression (&op_tokens[sizeof(op_tokens)-7]) + +arith_t +arith(const char *expr, int *perrcode, a_e_h_t *math_hooks) +{ + char arithval; /* Current character under analysis */ + operator lasttok, op; + operator prec; + operator *stack, *stackptr; + const char *p = endexpression; + int errcode; + v_n_t *numstack, *numstackptr; + unsigned datasizes = strlen(expr) + 2; + + /* Stack of integers */ + /* The proof that there can be no more than strlen(startbuf)/2+1 integers + * in any given correct or incorrect expression is left as an exercise to + * the reader. */ + numstackptr = numstack = alloca((datasizes / 2) * sizeof(numstack[0])); + /* Stack of operator tokens */ + stackptr = stack = alloca(datasizes * sizeof(stack[0])); + + *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */ + *perrcode = errcode = 0; + + while (1) { + arithval = *expr; + if (arithval == 0) { + if (p == endexpression) { + /* Null expression. */ + return 0; + } + + /* This is only reached after all tokens have been extracted from the + * input stream. If there are still tokens on the operator stack, they + * are to be applied in order. At the end, there should be a final + * result on the integer stack */ + + if (expr != endexpression + 1) { + /* If we haven't done so already, */ + /* append a closing right paren */ + expr = endexpression; + /* and let the loop process it. */ + continue; + } + /* At this point, we're done with the expression. */ + if (numstackptr != numstack+1) { + /* ... but if there isn't, it's bad */ + err: + *perrcode = -1; + return *perrcode; + } + if (numstack->var) { + /* expression is $((var)) only, lookup now */ + errcode = arith_lookup_val(numstack, math_hooks); + } + ret: + *perrcode = errcode; + return numstack->val; + } + + /* Continue processing the expression. */ + if (arith_isspace(arithval)) { + /* Skip whitespace */ + goto prologue; + } + p = endofname(expr); + if (p != expr) { + size_t var_name_size = (p-expr) + 1; /* trailing zero */ + + numstackptr->var = alloca(var_name_size); + safe_strncpy(numstackptr->var, expr, var_name_size); + expr = p; + num: + numstackptr->contidional_second_val_initialized = 0; + numstackptr++; + lasttok = TOK_NUM; + continue; + } + if (isdigit(arithval)) { + numstackptr->var = NULL; + numstackptr->val = strto_arith_t(expr, (char **) &expr, 0); + goto num; + } + for (p = op_tokens; ; p++) { + const char *o; + + if (*p == 0) { + /* strange operator not found */ + goto err; + } + for (o = expr; *p && *o == *p; p++) + o++; + if (!*p) { + /* found */ + expr = o - 1; + break; + } + /* skip tail uncompared token */ + while (*p) + p++; + /* skip zero delim */ + p++; + } + op = p[1]; + + /* post grammar: a++ reduce to num */ + if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC) + lasttok = TOK_NUM; + + /* Plus and minus are binary (not unary) _only_ if the last + * token was as number, or a right paren (which pretends to be + * a number, since it evaluates to one). Think about it. + * It makes sense. */ + if (lasttok != TOK_NUM) { + switch (op) { + case TOK_ADD: + op = TOK_UPLUS; + break; + case TOK_SUB: + op = TOK_UMINUS; + break; + case TOK_POST_INC: + op = TOK_PRE_INC; + break; + case TOK_POST_DEC: + op = TOK_PRE_DEC; + break; + } + } + /* We don't want a unary operator to cause recursive descent on the + * stack, because there can be many in a row and it could cause an + * operator to be evaluated before its argument is pushed onto the + * integer stack. */ + /* But for binary operators, "apply" everything on the operator + * stack until we find an operator with a lesser priority than the + * one we have just extracted. */ + /* Left paren is given the lowest priority so it will never be + * "applied" in this way. + * if associativity is right and priority eq, applied also skip + */ + prec = PREC(op); + if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) { + /* not left paren or unary */ + if (lasttok != TOK_NUM) { + /* binary op must be preceded by a num */ + goto err; + } + while (stackptr != stack) { + if (op == TOK_RPAREN) { + /* The algorithm employed here is simple: while we don't + * hit an open paren nor the bottom of the stack, pop + * tokens and apply them */ + if (stackptr[-1] == TOK_LPAREN) { + --stackptr; + /* Any operator directly after a */ + lasttok = TOK_NUM; + /* close paren should consider itself binary */ + goto prologue; + } + } else { + operator prev_prec = PREC(stackptr[-1]); + + convert_prec_is_assing(prec); + convert_prec_is_assing(prev_prec); + if (prev_prec < prec) + break; + /* check right assoc */ + if (prev_prec == prec && is_right_associativity(prec)) + break; + } + errcode = arith_apply(*--stackptr, numstack, &numstackptr, math_hooks); + if (errcode) goto ret; + } + if (op == TOK_RPAREN) { + goto err; + } + } + + /* Push this operator to the stack and remember it. */ + *stackptr++ = lasttok = op; + prologue: + ++expr; + } /* while */ +} + +/*- + * Copyright (c) 1989, 1991, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Kenneth Almquist. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ diff --git a/shell/math.h b/shell/math.h new file mode 100644 index 000000000..a52680923 --- /dev/null +++ b/shell/math.h @@ -0,0 +1,101 @@ +/* math.h - interface to shell math "library" -- this allows shells to share + * the implementation of arithmetic $((...)) expansions. + * + * This aims to be a POSIX shell math library as documented here: + * http://www.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_06_04 + * + * See math.c for internal documentation. + */ + +/* The math library has just one function: + * + * arith_t arith(const char *expr, int *perrcode, arith_eval_hooks_t *hooks); + * + * The first argument is the math string to parse. All normal expansions must + * be done already. i.e. no dollar symbols should be present. + * + * The second argument is a semi-detailed error description in case something + * goes wrong in the parsing steps. Currently, those values are (for + * compatibility, you should assume all negative values are errors): + * 0 - no errors (yay!) + * -1 - unspecified problem + * -2 - divide by zero + * -3 - exponent less than 0 + * -5 - expression recursion loop detected + * + * The third argument is a struct pointer of hooks for your shell (see below). + * + * The function returns the answer to the expression. So if you called it + * with the expression: + * "1 + 2 + 3" + * You would obviously get back 6. + */ + +/* To add support to a shell, you need to implement three functions: + * + * lookupvar() - look up and return the value of a variable + * + * If the shell does: + * foo=123 + * Then the code: + * const char *val = lookupvar("foo"); + * Will result in val pointing to "123" + * + * setvar() - set a variable to some value + * + * If the arithmetic expansion does something like: + * $(( i = 1)) + * Then the math code will make a call like so: + * setvar("i", "1", 0); + * The storage for the first two parameters are not allocated, so your + * shell implementation will most likely need to strdup() them to save. + * + * endofname() - return the end of a variable name from input + * + * The arithmetic code does not know about variable naming conventions. + * So when it is given an experession, it knows something is not numeric, + * but it is up to the shell to dictate what is a valid identifiers. + * So when it encounters something like: + * $(( some_var + 123 )) + * It will make a call like so: + * end = endofname("some_var + 123"); + * So the shell needs to scan the input string and return a pointer to the + * first non-identifier string. In this case, it should return the input + * pointer with an offset pointing to the first space. The typical + * implementation will return the offset of first char that does not match + * the regex (in C locale): ^[a-zA-Z_][a-zA-Z_0-9]* + */ + +/* To make your life easier when dealing with optional 64bit math support, + * rather than assume that the type is "signed long" and you can always + * use "%ld" to scan/print the value, use the arith_t helper defines. See + * below for the exact things that are available. + */ + +#ifndef _SHELL_MATH_ +#define _SHELL_MATH_ + +#if ENABLE_SH_MATH_SUPPORT_64 +typedef int64_t arith_t; +#define arith_t_type long long +#define arith_t_fmt "%lld" +#define strto_arith_t strtoll +#else +typedef long arith_t; +#define arith_t_type long +#define arith_t_fmt "%ld" +#define strto_arith_t strtol +#endif + +typedef const char *(*arith_var_lookup_t)(const char *name); +typedef void (*arith_var_set_t)(const char *name, const char *val, int flags); +typedef char *(*arith_var_endofname_t)(const char *name); +typedef struct arith_eval_hooks { + arith_var_lookup_t lookupvar; + arith_var_set_t setvar; + arith_var_endofname_t endofname; +} arith_eval_hooks_t; + +arith_t arith(const char *expr, int *perrcode, arith_eval_hooks_t*); + +#endif |