src/hci/arith.c

   1 /* Recursive descent arithmetic calculator:
   2  * Ops: !, ~                            (Highest)
   3  *      *, /, %
   4  *      +, -
   5  *      <<, >>
   6  *      <, <=, >, >=
   7  *      !=, ==
   8  *      &
   9  *      |
  10  *      ^
  11  *      &&
  12  *      ||                              (Lowest)
  13 */
  14
  15 #include <ctype.h>
  16 #include <stdint.h>
  17 #include <string.h>
  18 #include <stdlib.h>
  19 #include <stdio.h>
  20 #include <errno.h>
  21
  22 #include <gpxe/parse.h>
  23
  24 #define NUM_OPS         20
  25 #define MAX_PRIO                11
  26 #define MIN_TOK         258
  27 #define TOK_PLUS                (MIN_TOK + 5)
  28 #define TOK_MINUS       (MIN_TOK + 6)
  29 #define TOK_NUMBER      256
  30 #define TOK_STRING      257
  31 #define TOK_TOTAL               20
  32
  33 #define SEP1                    -1
  34 #define SEP2                    -1, -1
  35
  36 #define EPARSE          (EINVAL | EUNIQ_01)
  37 #define EDIV0                   (EINVAL | EUNIQ_02)
  38 #define ENOOP           (EINVAL | EUNIQ_03)
  39 #define EWRONGOP        (EINVAL | EUNIQ_04)
  40
  41 static struct string *input_str;
  42 static char *inp_ptr = NULL;
  43 static int tok;
  44 static int err_val;
  45 static union {
  46         long num_value;
  47         char *str_value;
  48 }tok_value;
  49
  50 /* Here is a table of the operators */
  51 static const char op_table[NUM_OPS * 3 + 1] = { '!', SEP2 ,  '~', SEP2, '*', SEP2, '/', SEP2, '%', SEP2, '+', SEP2, '-', SEP2,
  52                                                 '<', SEP2, '<', '=', SEP1, '<', '<', SEP1, '>', SEP2, '>', '=', SEP1, '>', '>', SEP1,  '&', SEP2,
  53                                                 '|', SEP2, '^', SEP2, '&', '&', SEP1, '|', '|', SEP1, '!', '=', SEP1, '=', '=', SEP1, '\0'
  54 };
  55
  56 static signed const char op_prio[NUM_OPS]       = { 10, 10, 9, 9, 9, 8, 8, 6, 6, 7, 6, 6, 7, 4, 3, 2, 1, 0, 5, 5 };
  57
  58 static void ignore_whitespace ( void );
  59 static int parse_expr ( char **buffer );
  60
  61 struct char_table table[21] = {
  62         { .token = '\\', .type = FUNC, .next.parse_func = parse_escape },
  63         { .token = '"', .type = TABLE, .next = { .next_table = { .ntable = dquote_table, .len = 3 } } },
  64         { .token = '$', .type = FUNC, .next.parse_func = dollar_expand },
  65         { .token = '\'', .type = TABLE, .next = { .next_table = { .ntable = squote_table, .len = 1 } } },
  66         { .token = ' ', .type = ENDQUOTES },
  67         { .token = '\t', .type = ENDQUOTES },
  68         { .token = '~', .type = ENDTOK },
  69         { .token = '!', .type = ENDTOK },
  70         { .token = '*', .type = ENDTOK },
  71         { .token = '/', .type = ENDTOK },
  72         { .token = '%', .type = ENDTOK },
  73         { .token = '+', .type = ENDTOK },
  74         { .token = '-', .type = ENDTOK },
  75         { .token = '<', .type = ENDTOK },
  76         { .token = '=', .type = ENDTOK },
  77         { .token = '>', .type = ENDTOK },
  78         { .token = '&', .type = ENDTOK },
  79         { .token = '|', .type = ENDTOK },
  80         { .token = '^', .type = ENDTOK },
  81         { .token = '(', .type = ENDTOK },
  82         { .token = ')', .type = ENDTOK }
  83 };
  84
  85 static void input ( void ) {
  86         char t_op[3] = { '\0', '\0', '\0'};
  87         char *p1, *p2;
  88         char *tmp, *strtmp = NULL;
  89         char *end;
  90         int success;
  91
  92         if ( tok == -1 )
  93                 return;
  94
  95         ignore_whitespace();
  96
  97         if ( *inp_ptr == '\0' ) {
  98                 tok = -1;
  99                 return;
 100         }
 101         tok = 0;
 102
 103         tmp = expand_string ( input_str, &inp_ptr, &end, table, 21, 0, &success );
 104         if ( !tmp ) {
 105                 tok = -1;
 106                 err_val = -ENOMEM;
 107                 return;
 108         }
 109
 110         if ( success ) {
 111                 strtmp = strndup ( inp_ptr, end - inp_ptr );
 112                 if ( isnum ( strtmp, &tok_value.num_value ) ) {
 113                         free ( strtmp );
 114                         tok = TOK_NUMBER;
 115                 } else {
 116                         tok_value.str_value = strtmp;
 117                         tok = TOK_STRING;
 118                 }
 119                 inp_ptr = end;
 120                 return;
 121         }
 122
 123         /* Check for an operator */
 124         t_op[0] = *inp_ptr++;
 125         p1 = strstr ( op_table, t_op );
 126         if ( !p1 ) {                    /* The character is not present in the list of operators */
 127                 tok = *t_op;
 128                 return;
 129         }
 130
 131         t_op[1] = *inp_ptr;
 132         p2 = strstr ( op_table, t_op );
 133         if ( !p2 || p1 == p2 ) {
 134                 if ( ( p1 - op_table ) % 3 ) {                  /* Without this, it would take '=' as '<=' */
 135                         tok = *t_op;
 136                         return;
 137                 }
 138
 139                 tok = MIN_TOK + ( p1 - op_table ) / 3;
 140                 return;
 141         }
 142         inp_ptr++;
 143         tok = MIN_TOK + ( p2 - op_table ) / 3;
 144
 145 }
 146
 147 /* Check if a string is a number: "-1" and "+42" is accepted, but not "-1a". If so, place it in num and return 1 else num = 0 and return 0 */
 148 int isnum ( char *string, long *num ) {
 149         int flag = 0;
 150
 151         *num = 0;
 152         if ( *string == '+' ) {
 153                 string++;
 154         } else if ( *string == '-' ) {
 155                 flag = 1;
 156                 string++;
 157         }
 158         *num = strtoul ( string, &string, 0 );
 159         if ( *string != 0 ) {
 160                 *num = 0;
 161                 return 0;
 162         }
 163         if ( flag )
 164                 *num = -*num;
 165         return 1;
 166 }
 167
 168 static void ignore_whitespace ( void ) {
 169         while ( isspace ( *inp_ptr ) ) {
 170                 inp_ptr++;
 171         }
 172 }
 173
 174 static int accept ( int ch ) {
 175         if ( tok == ch ) {
 176                 input();
 177                 return 1;
 178         }
 179         return 0;
 180 }
 181
 182 static void skip ( int ch ) {
 183         if ( !accept ( ch ) ) {
 184                 err_val = -EPARSE;
 185         }
 186 }
 187
 188 static int parse_num ( char **buffer ) {
 189         long num = 0;
 190         int flag = 0;
 191
 192         if ( tok == TOK_MINUS || tok == TOK_PLUS || tok == '(' || tok == TOK_NUMBER ) {
 193
 194                 if ( accept ( TOK_MINUS ) )                             //Handle -NUM and +NUM
 195                         flag = 1;
 196                 else if ( accept ( TOK_PLUS ) ) {
 197                 }
 198
 199                 if ( accept ( '(' ) ) {
 200                         parse_expr ( buffer );
 201                         if ( err_val )  {
 202                                 return ( err_val );
 203                         }
 204                         skip ( ')' );
 205                         if ( err_val )  {
 206                                 free ( *buffer );
 207                                 return (err_val );
 208                         }
 209                         if ( flag ) {
 210                                 int t;
 211                                 t = isnum ( *buffer, &num );
 212                                 free ( *buffer );
 213                                 if ( t == 0 ) {         /* Trying to do a -string, which should not be permitted */
 214                                         return ( err_val = -EWRONGOP );
 215                                 }
 216                                 return ( ( asprintf ( buffer, "%ld", -num )  < 0 ) ? (err_val = -ENOMEM ) : 0 );
 217                         }
 218                         return 0;
 219                 }
 220
 221                 if ( tok == TOK_NUMBER ) {
 222                         if ( flag )
 223                                 num = -tok_value.num_value;
 224                         else
 225                                 num = tok_value.num_value;
 226                         input();
 227                         return ( ( asprintf ( buffer, "%ld", num ) < 0) ? (err_val = -ENOMEM ) : 0 );
 228                 }
 229                 return ( err_val = -EPARSE );
 230         }
 231         if ( tok == TOK_STRING ) {
 232                 *buffer = tok_value.str_value;
 233                 input();
 234                 return 0;
 235         }
 236         return ( err_val = -EPARSE );
 237 }
 238
 239 static int eval(int op, char *op1, char *op2, char **buffer) {
 240         long value;
 241         int bothints = 1;
 242         long lhs, rhs;
 243
 244         if ( op1 ) {
 245                 if ( ! isnum ( op1, &lhs ) )
 246                         bothints = 0;
 247         }
 248
 249         if ( ! isnum (op2, &rhs ) )
 250                 bothints = 0;
 251
 252         if ( op <= 17 && ! bothints ) {
 253                 return ( err_val = -EWRONGOP );
 254         }
 255
 256         switch(op)
 257         {
 258                 case 0:
 259                         value = !rhs;
 260                         break;
 261                 case 1:
 262                         value = ~rhs;
 263                         break;
 264                 case 2:
 265                         value = lhs * rhs;
 266                         break;
 267                 case 3:
 268                         if(rhs != 0)
 269                                 value = lhs / rhs;
 270                         else {
 271                                 return ( err_val = -EDIV0 );
 272                         }
 273                         break;
 274                 case 4:
 275                         value = lhs % rhs;
 276                         break;
 277                 case 5:
 278                         value = lhs + rhs;
 279                         break;
 280                 case 6:
 281                         value = lhs - rhs;
 282                         break;
 283                 case 7:
 284                         value = lhs < rhs;
 285                         break;
 286                 case 8:
 287                         value = lhs <= rhs;
 288                         break;
 289                 case 9:
 290                         value = lhs << rhs;
 291                         break;
 292                 case 10:
 293                         value = lhs > rhs;
 294                         break;
 295                 case 11:
 296                         value = lhs >= rhs;
 297                         break;
 298                 case 12:
 299                         value = lhs >> rhs;
 300                         break;
 301                 case 13:
 302                         value = lhs & rhs;
 303                         break;
 304                 case 14:
 305                         value = lhs | rhs;
 306                         break;
 307                 case 15:
 308                         value = lhs ^ rhs;
 309                         break;
 310                 case 16:
 311                         value = lhs && rhs;
 312                         break;
 313                 case 17:
 314                         value = lhs || rhs;
 315                         break;
 316                 case 18:
 317                         value = strcmp ( op1, op2 ) != 0;
 318                         break;
 319                 case 19:
 320                         value = strcmp ( op1, op2 ) == 0;
 321                         break;
 322                 default:                /* This means the operator is in the op_table, but not defined in this switch statement */
 323                         return ( err_val = -ENOOP );
 324         }
 325         return ( ( asprintf(buffer, "%ld", value)  < 0) ? ( err_val = -ENOMEM ) : 0 );
 326 }
 327
 328 static int parse_prio(int prio, char **buffer) {
 329         int op;
 330         char *lc, *rc;
 331
 332         if ( tok < MIN_TOK || tok == TOK_MINUS || tok == TOK_PLUS ) {
 333                 parse_num ( &lc );
 334         } else {
 335                 if ( tok < MIN_TOK + 2 ) {
 336                         lc = NULL;
 337                 } else {
 338                         return ( err_val = -EPARSE );
 339                 }
 340         }
 341
 342         if ( err_val ) {
 343                 return err_val;
 344         }
 345         while( tok != -1 && tok != ')' ) {
 346                 long lhs;
 347                 if ( tok < MIN_TOK ) {
 348                         if ( lc )
 349                                 free(lc);
 350                         return ( err_val = -EPARSE );
 351                 }
 352                 if ( op_prio[tok - MIN_TOK] <= prio - ( tok - MIN_TOK <= 1 ) ? 1 : 0 ) {
 353                         break;
 354                 }
 355
 356                 op  = tok;
 357                 input();
 358                 parse_prio ( op_prio[op - MIN_TOK], &rc );
 359
 360                 if ( err_val )  {
 361                         if ( lc )
 362                                 free ( lc );
 363                         return err_val;
 364                 }
 365
 366                 lhs = eval ( op - MIN_TOK, lc, rc, buffer );
 367                 free ( rc );
 368                 if ( lc )
 369                         free ( lc );
 370                 if ( err_val ) {
 371                         return err_val;
 372                 }
 373                 lc = *buffer;
 374         }
 375         *buffer = lc;
 376         return 0;
 377 }
 378
 379 static int parse_expr ( char **buffer ) {
 380         return parse_prio ( -1, buffer );
 381 }
 382
 383 int parse_arith ( struct string *inp, char *orig, char **end ) {
 384         char *buffer = NULL;
 385         int start;
 386
 387         start = orig - inp->value;
 388
 389         input_str = inp;
 390         err_val = tok = 0;
 391         inp_ptr = orig + 1;
 392
 393         input();
 394
 395         skip ( '(' );
 396         parse_expr ( &buffer );
 397         if ( !err_val ) {
 398
 399                 if ( tok != ')' ) {
 400                         free ( buffer );
 401                         err_val = -EPARSE;
 402                 } else {
 403                         orig = inp->value + start;
 404                         *orig = 0;
 405                         *end = inp_ptr;
 406                         orig = string3cat ( inp, buffer, *end );
 407                         *end = orig + start + strlen ( buffer );
 408                 }
 409         }
 410
 411         if ( err_val )  {
 412                 if ( tok == TOK_STRING )
 413                         free ( tok_value.str_value );
 414                 switch ( err_val ) {
 415                         case -EPARSE:
 416                                 printf ( "parse error\n" );
 417                                 break;
 418                         case -EDIV0:
 419                                 printf ( "division by 0\n" );
 420                                 break;
 421                         case -ENOOP:
 422                                 printf ( "operator undefined\n" );
 423                                 break;
 424                         case -EWRONGOP:
 425                                 printf ( "wrong type of operand\n" );
 426                                 break;
 427                         case -ENOMEM:
 428                                 printf("out of memory\n");
 429                                 break;
 430                 }
 431                 free_string ( inp );
 432                 return err_val;
 433         }
 434
 435         return 0;
 436 }
 437