fc37899b21c0196aaaebffd25733221f3d0cad2a
[people/lynusvaz/gpxe.git] / src / hci / arith.c
1 /*
2  * Recursive descent arithmetic calculator:
3  *   + - * / ( )
4  */
5
6 /*
7 Ops: !, ~                               (Highest)
8         *, /, %
9         +, -
10         <<, >>
11         <, <=, >, >=
12         !=, ==
13         &
14         |
15         ^
16         &&
17         ||                              (Lowest)
18 */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <ctype.h>
23 #include <string.h>
24
25 #ifndef __ARITH_TEST__
26 #include <lib.h>
27 #endif
28
29 #define NUM_OPS         20
30 #define MAX_PRIO                11
31 #define MIN_TOK         258
32 #define TOK_PLUS                (MIN_TOK + 5)
33 #define TOK_MINUS       (MIN_TOK + 6)
34 #define TOK_NUMBER      256
35 #define TOK_STRING      257
36 #define TOK_TOTAL               20
37
38 char *inp, *prev;
39 int tok;
40 int err_val;            //skip, parse_num, eval
41 long tok_value;
42
43 char *op_table = "!@@" "~@@" "*@@" "/@@" "%@@" "+@@" "-@@" "<@@" "<=@" "<<@" ">@@" ">=@" ">>@" "!=@" "==@" "&@@" "|@@" "^@@" "&&@" "||@";
44 char *keyword_table = " \t\v()!~*/%+-<=>&|^";                   //Characters that cannot appear in a string
45 signed char op_prio[NUM_OPS]    = { 10, 10, 9, 9, 9, 8, 8, 6, 6, 7, 6, 6, 7, 5, 5, 4, 3, 2, 1, 0 };
46
47 /*
48         Changes:
49         1. Common function for all operators.
50         2. Common input function.
51         
52         Notes:
53         1. Better way to store operators of > 1 characters? I have tried to keep handling operators consistent.
54 */      
55         
56 static void ignore_whitespace(void);
57 //static long get_value(char *var, int size);
58
59 static void input()
60 {
61         char t_op[3] = { '\0', '\0', '\0'};
62         char *p1, *p2;
63         size_t len;
64         
65         if(tok == -1)
66                 return;
67
68         prev = inp;
69         ignore_whitespace();
70         
71         if(*inp != '\0')
72         {
73                 if(isdigit(*inp))
74                 {
75                         tok_value = 0;
76                         tok = TOK_NUMBER;
77                         tok_value = strtoul(inp, &inp, 0);
78                         return;
79                 }
80                 
81                 len = strcspn(inp, keyword_table);
82                 
83                 if(len > 0)
84                 {
85                         char str_val[len + 1];
86                         strncpy(str_val, inp, len);
87                         str_val[len] = '\0';
88                         asprintf((char **)&tok_value, "%s", str_val);
89                         inp += len;
90                         tok = TOK_STRING;
91                         return;
92                 }
93                 
94                 t_op[0] = *inp++;
95                 p1 = strstr(op_table, t_op);
96                 if(!p1)
97                 {
98                         tok = *t_op;
99                         return;
100                 }
101                 t_op[1] = *inp;
102                 p2 = strstr(op_table, t_op);
103                 if(!p2 || p1 == p2)
104                 {
105                         tok = MIN_TOK + (p1 - op_table)/3;
106                         return;
107                 }
108                 inp++;
109                 tok = MIN_TOK + (p2 - op_table)/3;
110         }
111         else
112                 tok = -1;       
113 }
114
115 static int parse_expr(char **buffer);
116
117 static void ignore_whitespace(void)
118 {
119         while (isspace(*inp)) {
120                 inp++;
121         }
122 }
123
124 static int accept(int ch)
125 {
126         if (tok == ch) {
127                 input();
128                 return 1;
129         }
130         return 0;
131 }
132
133 static void skip(int ch)
134 {
135         if (!accept(ch)) {
136                 err_val = -1;
137                 printf("expected '%c', got '%c'\n", ch, tok);
138         }
139 }
140
141 static int parse_num(char **buffer)
142 {
143         long num = 0;
144         int flag = 1;
145         
146         if(accept(TOK_MINUS))                           //Handle -NUM and +NUM
147                 flag = -1;
148         else if(accept(TOK_PLUS)) {}
149         
150         if (accept('(')) {
151                 parse_expr(buffer);
152                 skip(')');
153                 if(flag < 0)
154                 {
155                         if(**buffer == '-')
156                                 **buffer = '+';
157                         else
158                         {
159                                 char t[strlen(*buffer) + 2];
160                                 t[0] = '-';
161                                 strcpy(t + 1, *buffer);
162                                 free(*buffer);
163                                 return asprintf(buffer, "%s", t);
164                         }                               
165                 }
166                 return strlen(*buffer);
167         }
168         
169         if(tok == TOK_NUMBER)
170         {
171                 num = flag * tok_value;
172                 input();
173                 return asprintf(buffer, "%ld", num);
174         } else if (tok == TOK_STRING)
175         {
176                 *buffer = (char *)tok_value;
177                 input();
178                 return strlen(*buffer);
179         }
180                 err_val = -1;
181         return 0;
182 }
183
184 //"!" "~" "*" "/" "%" "+" "-" "<" "<=" "<<" ">" ">=" ">>" "!=" "==" "&" "|" "^" "&&" "||";
185 static int eval(int op, char *op1, char *op2, char **buffer)
186 {
187         long value;
188         
189         long lhs, rhs;
190         int flag1 = 0, flag2 = 0;
191         
192         if(*op1 == '-')
193         {
194                 flag1 = 1;
195                 op1++;
196         }
197         if(*op2 == '-')
198         {
199                 flag2 = 1;
200                 op2++;
201         }
202         lhs = strtoul(op1, NULL, 0);
203         if(flag1) lhs = -lhs;
204         rhs = strtoul(op2, NULL, 0);
205         if(flag2) rhs = -rhs;
206         
207         switch(op)
208         {
209                 case 0:
210                         value = !rhs;
211                         break;
212                 case 1: 
213                         value = ~rhs;
214                         break;
215                 case 2: 
216                         value = lhs * rhs;
217                         break;
218                 case 3: 
219                         value = lhs / rhs;
220                         break;
221                 case 4: 
222                         value = lhs % rhs;
223                         break;
224                 case 5:
225                         value = lhs + rhs;
226                         break;
227                 case 6: 
228                         value = lhs - rhs;
229                         break;
230                 case 7: 
231                         value = lhs < rhs;
232                         break;
233                 case 8: 
234                         value = lhs <= rhs;
235                         break;
236                 case 9: 
237                         value = lhs << rhs;
238                         break;
239                 case 10: 
240                         value = lhs > rhs;
241                         break;
242                 case 11: 
243                         value = lhs >= rhs;
244                         break;
245                 case 12: 
246                         value = lhs >> rhs;
247                         break;
248                 case 13:
249                         value = strcmp(op1, op2) ? 1 : 0;
250                         break;
251                 case 14:
252                         value = !strcmp(op1, op2);
253                         break;
254                 case 15:
255                         value = lhs & rhs;
256                         break;
257                 case 16: 
258                         value = lhs | rhs;
259                         break;
260                 case 17:
261                         value = lhs ^ rhs;
262                         break;
263                 case 18: 
264                         value = lhs && rhs;
265                         break;
266                 case 19: 
267                         value = lhs || rhs;
268                         break;
269                 
270                 default: 
271                         err_val = -1;
272                         return 0;
273                         //printf("Undefined operator\n");
274         }
275         return asprintf(buffer, "%ld", value);
276 }
277
278 static int parse_prio(int prio, char **buffer)
279 {
280         int op;
281         char *lc, *rc;
282         
283         if(tok < MIN_TOK || tok == TOK_MINUS || tok == TOK_PLUS)                //All operators are >= 128. If it is not an operator, look for number
284         {
285                 parse_num(&lc);
286         }
287         else asprintf(&lc, " ");
288         if(err_val)
289                 return 0;
290         while(tok != -1 && tok >= MIN_TOK && (op_prio[tok - MIN_TOK] > prio - (tok - MIN_TOK <= 1) ? 1 : 0) ) 
291         {
292                 long lhs;
293                 op  = tok;
294                 input();
295                 parse_prio(op_prio[op - MIN_TOK], &rc);
296                 
297                 if(err_val)
298                         return 0;
299                 
300                 lhs = eval(op - MIN_TOK, lc, rc, buffer);
301                 free(rc);
302                 free(lc);
303                 lc = *buffer;
304                 
305                 if(err_val)
306                         return 0;
307         }
308         *buffer = lc;
309         return strlen(*buffer);
310 }
311
312 static int parse_expr(char **buffer)
313 {
314         return parse_prio(-1, buffer);
315 }
316
317 int parse_arith(char *inp_string, char **end, char **buffer)
318 {
319         err_val = tok = 0;
320         inp = inp_string;
321         input();
322         
323         parse_expr(buffer);
324         
325         if(err_val)                             //Read till we get a ')'
326         {
327                 *end = strchr(inp, ')');
328                 if(!*end)
329                         *end = inp;
330                 else    end++;
331         }
332         else
333         *end = prev;
334         
335         if(err_val)
336         {
337                 printf("parse error\n");
338                 return 0;
339         }
340         
341         return strlen(*buffer);
342         
343         return -1;
344 }
345
346 #ifdef __ARITH_TEST__
347 int main(int argc, char *argv[])
348 {
349         char *ret_val;
350         int r;
351         char *tail;
352         r = parse_arith(argv[1], &tail, &ret_val);
353         if(r < 0)
354                 printf("%d Tail: %s\n", r, tail);
355         else
356                 printf("%s Tail:%s\n", ret_val, tail);
357         return 0;
358 }
359 #endif