7187483eb103cf610b29036713a4c59f000247e7
[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 #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