ff656c003a4e271839d85af5146646ec5f2817f5
[people/lynusvaz/gpxe.git] / 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