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