1 # Rules providing basic arithmetic operations
6 HAIKU_PAD_9 = 0 1 2 3 4 5 6 7 8 ;
8 # a > b <==> $(HAIKU_DIGIT_GREATER_$(a)[1$(b)])
9 HAIKU_DIGIT_GREATER_0 = $(HAIKU_PAD_9) ;
10 HAIKU_DIGIT_GREATER_1 = $(HAIKU_PAD_9) 1 ;
11 HAIKU_DIGIT_GREATER_2 = $(HAIKU_PAD_9) 1 1 ;
12 HAIKU_DIGIT_GREATER_3 = $(HAIKU_PAD_9) 1 1 1 ;
13 HAIKU_DIGIT_GREATER_4 = $(HAIKU_PAD_9) 1 1 1 1 ;
14 HAIKU_DIGIT_GREATER_5 = $(HAIKU_PAD_9) 1 1 1 1 1 ;
15 HAIKU_DIGIT_GREATER_6 = $(HAIKU_PAD_9) 1 1 1 1 1 1 ;
16 HAIKU_DIGIT_GREATER_7 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 ;
17 HAIKU_DIGIT_GREATER_8 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 1 ;
18 HAIKU_DIGIT_GREATER_9 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 1 1 ;
20 # a + b == $(HAIKU_DIGIT_ADD_$(a)[1$(b)]) (carry ignored)
21 HAIKU_DIGIT_ADD_0 = $(HAIKU_PAD_9) 0 1 2 3 4 5 6 7 8 9 ;
22 HAIKU_DIGIT_ADD_1 = $(HAIKU_PAD_9) 1 2 3 4 5 6 7 8 9 0 ;
23 HAIKU_DIGIT_ADD_2 = $(HAIKU_PAD_9) 2 3 4 5 6 7 8 9 0 1 ;
24 HAIKU_DIGIT_ADD_3 = $(HAIKU_PAD_9) 3 4 5 6 7 8 9 0 1 2 ;
25 HAIKU_DIGIT_ADD_4 = $(HAIKU_PAD_9) 4 5 6 7 8 9 0 1 2 3 ;
26 HAIKU_DIGIT_ADD_5 = $(HAIKU_PAD_9) 5 6 7 8 9 0 1 2 3 4 ;
27 HAIKU_DIGIT_ADD_6 = $(HAIKU_PAD_9) 6 7 8 9 0 1 2 3 4 5 ;
28 HAIKU_DIGIT_ADD_7 = $(HAIKU_PAD_9) 7 8 9 0 1 2 3 4 5 6 ;
29 HAIKU_DIGIT_ADD_8 = $(HAIKU_PAD_9) 8 9 0 1 2 3 4 5 6 7 ;
30 HAIKU_DIGIT_ADD_9 = $(HAIKU_PAD_9) 9 0 1 2 3 4 5 6 7 8 ;
32 # a - b == $(HAIKU_DIGIT_SUB_$(a)[1$(b)]) (carry ignored)
33 HAIKU_DIGIT_SUB_0 = $(HAIKU_PAD_9) 0 9 8 7 6 5 4 3 2 1 ;
34 HAIKU_DIGIT_SUB_1 = $(HAIKU_PAD_9) 1 0 9 8 7 6 5 4 3 2 ;
35 HAIKU_DIGIT_SUB_2 = $(HAIKU_PAD_9) 2 1 0 9 8 7 6 5 4 3 ;
36 HAIKU_DIGIT_SUB_3 = $(HAIKU_PAD_9) 3 2 1 0 9 8 7 6 5 4 ;
37 HAIKU_DIGIT_SUB_4 = $(HAIKU_PAD_9) 4 3 2 1 0 9 8 7 6 5 ;
38 HAIKU_DIGIT_SUB_5 = $(HAIKU_PAD_9) 5 4 3 2 1 0 9 8 7 6 ;
39 HAIKU_DIGIT_SUB_6 = $(HAIKU_PAD_9) 6 5 4 3 2 1 0 9 8 7 ;
40 HAIKU_DIGIT_SUB_7 = $(HAIKU_PAD_9) 7 6 5 4 3 2 1 0 9 8 ;
41 HAIKU_DIGIT_SUB_8 = $(HAIKU_PAD_9) 8 7 6 5 4 3 2 1 0 9 ;
42 HAIKU_DIGIT_SUB_9 = $(HAIKU_PAD_9) 9 8 7 6 5 4 3 2 1 0 ;
44 # a * b == $(HAIKU_DIGIT_MULT_CARRY_$(a)[1$(b)]) $(HAIKU_DIGIT_MULT_$(a)[1$(b)])
45 HAIKU_DIGIT_MULT_0 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ;
46 HAIKU_DIGIT_MULT_1 = $(HAIKU_PAD_9) 0 1 2 3 4 5 6 7 8 9 ;
47 HAIKU_DIGIT_MULT_2 = $(HAIKU_PAD_9) 0 2 4 6 8 0 2 4 6 8 ;
48 HAIKU_DIGIT_MULT_3 = $(HAIKU_PAD_9) 0 3 6 9 2 5 8 1 4 7 ;
49 HAIKU_DIGIT_MULT_4 = $(HAIKU_PAD_9) 0 4 8 2 6 0 4 8 2 6 ;
50 HAIKU_DIGIT_MULT_5 = $(HAIKU_PAD_9) 0 5 0 5 0 5 0 5 0 5 ;
51 HAIKU_DIGIT_MULT_6 = $(HAIKU_PAD_9) 0 6 2 8 4 0 6 2 8 4 ;
52 HAIKU_DIGIT_MULT_7 = $(HAIKU_PAD_9) 0 7 4 1 8 5 2 9 6 3 ;
53 HAIKU_DIGIT_MULT_8 = $(HAIKU_PAD_9) 0 8 6 4 2 0 8 6 4 2 ;
54 HAIKU_DIGIT_MULT_9 = $(HAIKU_PAD_9) 0 9 8 7 6 5 4 3 2 1 ;
56 HAIKU_DIGIT_MULT_CARRY_0 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ;
57 HAIKU_DIGIT_MULT_CARRY_1 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ;
58 HAIKU_DIGIT_MULT_CARRY_2 = $(HAIKU_PAD_9) 0 0 0 0 0 1 1 1 1 1 ;
59 HAIKU_DIGIT_MULT_CARRY_3 = $(HAIKU_PAD_9) 0 0 0 0 1 1 1 2 2 2 ;
60 HAIKU_DIGIT_MULT_CARRY_4 = $(HAIKU_PAD_9) 0 0 0 1 1 2 2 2 3 3 ;
61 HAIKU_DIGIT_MULT_CARRY_5 = $(HAIKU_PAD_9) 0 0 1 1 2 2 3 3 4 4 ;
62 HAIKU_DIGIT_MULT_CARRY_6 = $(HAIKU_PAD_9) 0 0 1 1 2 3 3 4 4 5 ;
63 HAIKU_DIGIT_MULT_CARRY_7 = $(HAIKU_PAD_9) 0 0 1 2 2 3 4 4 5 6 ;
64 HAIKU_DIGIT_MULT_CARRY_8 = $(HAIKU_PAD_9) 0 0 1 2 3 4 4 5 6 7 ;
65 HAIKU_DIGIT_MULT_CARRY_9 = $(HAIKU_PAD_9) 0 0 1 2 3 4 5 6 7 8 ;
68 # pragma mark - Number Operations
71 rule NormalizeNum number
73 # NormalizeNum <number> ;
76 if $(number[1]) = "-" || $(number[1] = "+" {
78 number = $(number[2-]) ;
83 # cut off leading zeros
84 local number = [ FReverse $(number) ] ;
85 while $(number[1]) = 0 {
86 number = $(number[2-]) ;
88 number = [ FReverse $(number) ] ;
90 # zero is respresented as + 0
96 return $(sign) $(number) ;
99 rule Num string : dontExit
101 # Num <number string> [ : <dontExit> ] ;
103 # split the string into three parts: sign, digits, and remainder
104 local temp = [ Match ([^0-9]*)([0-9]+)(.*) : $(string) ] ;
106 # there must be digits, but there must not be a remainder
107 if ! $(temp[2]) || $(temp[3]) {
111 Exit "Not a number" ;
118 } else if $(temp[1]) = "+" || $(temp[1]) = "-" {
119 number = $(temp[1]) ;
124 Exit "Not a number (sign)" ;
130 # split off the last digit
131 temp = [ Match (.*)([0-9]) : $(temp[1]) ] ;
132 number += $(temp[2]) ;
136 return [ NormalizeNum $(number) ] ;
139 rule Num2String number
141 # Num2String <number> ;
143 local sign = $(number[1]) ;
148 number = [ FReverse $(number[2-]) ] ;
150 return $(sign)$(number:J=) ;
153 rule NumGreaterAbs a : b
155 # NumGreaterAbs <a> : <b> ;
157 # we compare from least to most significant digit
160 # chop off the first digit
161 local da = $(a[1]:E=0) ;
162 local db = $(b[1]:E=0) ;
167 if $(HAIKU_DIGIT_GREATER_$(da)[1$(db)]) {
175 # a is greater, if b is not longer and a is either longer or equally long
176 # and greater according to the digits comparison
177 if ! $(b) && ( $(a) || $(cmp) = 1 ) {
189 while $(a) || $(b) || $(carry) {
190 # chop off the first digit
191 local da = $(a[1]:E=0) ;
192 local db = $(b[1]:E=0) ;
196 # add carry to the first digit
198 local daa = $(HAIKU_DIGIT_ADD_1[1$(da)]) ;
199 carry = $(HAIKU_DIGIT_GREATER_$(da)[1$(daa)]) ;
204 local dr = $(HAIKU_DIGIT_ADD_$(da)[1$(db)]) ;
205 if $(HAIKU_DIGIT_GREATER_$(da)[1$(dr)]) {
221 while $(a) && ( $(b) || $(carry) ) {
222 # chop off the first digit
223 local da = $(a[1]:E=0) ;
224 local db = $(b[1]:E=0) ;
228 # sub carry from the first digit
230 local daa = $(HAIKU_DIGIT_SUB_$(da)[11]) ;
231 carry = $(HAIKU_DIGIT_GREATER_$(daa)[1$(da)]) ;
236 local dr = $(HAIKU_DIGIT_SUB_$(da)[1$(db)]) ;
237 if $(HAIKU_DIGIT_GREATER_$(dr)[1$(da)]) {
244 if $(b) || $(carry) {
245 Exit "Error: SubNumAbs: Can't subtract greater from smaller number." ;
256 if $(a) = $(HAIKU_ZERO) {
259 return "-" $(a[2-]) ;
261 return "+" $(a[2-]) ;
269 local signa = $(a[1]) ;
270 local signb = $(b[1]) ;
274 if $(signa) = $(signb) {
275 return $(signa) [ AddNumAbs $(a) : $(b) ] ;
278 if [ NumGreaterAbs $(a) : $(b) ] {
279 result = $(signa) [ SubNumAbs $(a) : $(b) ] ;
281 result = $(signb) [ SubNumAbs $(b) : $(a) ] ;
283 return [ NormalizeNum $(result) ] ;
290 return [ AddNum $(a) : [ NegNum $(b) ] ] ;
293 rule MultNumAbsDigit a : digit
295 # MultNumAbsDigit <a> : <digit> ;
297 local digitMultiples = $(HAIKU_DIGIT_MULT_$(digit)) ;
298 local digitCarries = $(HAIKU_DIGIT_MULT_CARRY_$(digit)) ;
302 while $(a) || $(carry) != 0 {
303 # chop off the first digit
304 local da = $(a[1]:E=0) ;
307 local dr = $(digitMultiples[1$(da)]) ;
309 # add carry to the resulting digit
311 local dra = $(HAIKU_DIGIT_ADD_$(dr)[1$(carry)]) ;
312 carry = $(HAIKU_DIGIT_GREATER_$(dr)[1$(dra)]:E=0) ;
317 carry = $(HAIKU_DIGIT_ADD_$(carry:E=0)[1$(digitCarries[1$(da)])]) ;
327 # MultNum <a> : <b> ;
329 # If one of the factors is 0, we save us computation and normalization.
330 if $(a) = $(HAIKU_ZERO) || $(b) = $(HAIKU_ZERO) {
331 return $(HAIKU_ZERO) ;
334 # get the sign for the result
336 if $(a[1]) != $(b[1]) {
343 # multiply the individual digits of b with a and add up the result
350 local adb = $(prefix) [ MultNumAbsDigit $(a) : $(db) ] ;
351 result = [ AddNumAbs $(result) : $(adb) ] ;
356 return $(sign) $(result) ;
359 rule NumGreater a : b
361 local signa = $(a[1]) ;
362 local signb = $(b[1]) ;
366 if $(signa) = $(signb) {
368 return [ NumGreaterAbs $(a) : $(b) ] ;
370 return [ NumGreaterAbs $(b) : $(a) ] ;
382 # pragma mark - Number String Operations
387 # Inc <number string a> ;
388 return [ Num2String [ AddNum [ Num $(a) ] : + 1 ] ] ;
393 # Dec <number string a> ;
394 return [ Num2String [ AddNum [ Num $(a) ] : - 1 ] ] ;
399 # Neg <number string a> ;
400 return [ Num2String [ NegNum [ Num $(a) ] ] ] ;
405 # Add <number string a> : <number string b> ;
406 return [ Num2String [ AddNum [ Num $(a) ] : [ Num $(b) ] ] ] ;
411 # Sub <number string a> : <number string b> ;
412 return [ Num2String [ SubNum [ Num $(a) ] : [ Num $(b) ] ] ] ;
417 # Mult <number string a> : <number string b> ;
418 return [ Num2String [ MultNum [ Num $(a) ] : [ Num $(b) ] ] ] ;
423 # Equal <number string a> : <number string b> ;
424 if [ Num $(a) ] = [ Num $(b) ] {
433 # Less <number string a> : <number string b> ;
434 return [ NumGreater [ Num $(b) ] : [ Num $(a) ] ] ;
439 # Greater <number string a> : <number string b> ;
440 return [ NumGreater [ Num $(a) ] : [ Num $(b) ] ] ;
443 rule LessOrEqual a : b
445 # LessOrEqual <number string a> : <number string b> ;
446 if [ NumGreater [ Num $(a) ] : [ Num $(b) ] ] {
452 rule GreaterOrEqual a : b
454 # GreaterOrEqual <number string a> : <number string b> ;
455 if [ NumGreater [ Num $(b) ] : [ Num $(a) ] ] {
462 # pragma mark - Expression Parser
465 rule ParseAtom expression
467 # ParseAtom <expression> ;
469 # expression: '(' expression ')' | number
471 if $(expression[1]) = "(" {
472 local result = [ ParseExpression $(expression[2-]) ] ;
473 if $(result[2]) != ")" {
474 Exit "ParseAtom: Parse error: Expected \")\"." ;
476 return $(result[1]) $(result[3-]) ;
479 Exit "ParseAtom: Parse error: Unexpected end of expression." ;
482 local num = [ Num $(expression[1]) : 1 ] ;
484 Exit "ParseAtom: Parse error: Expected number instead of:"
488 return [ Num2String $(num) ] $(expression[2-]) ;
492 rule ParseUnary expression
494 # ParseUnary <expression> ;
496 # expression: ('+'/'-')* atom
499 Exit "ParseUnary: Parse error: Unexpected end of expression." ;
502 # eat all unary "+" and "-" operations
504 while $(expression[1]) = "+" || $(expression[1]) = "-" {
505 if $(expression[1]) = "-" {
513 expression = $(expression[2-]) ;
516 local result = [ ParseAtom $(expression) ] ;
519 return [ Neg $(result[1]) ] $(result[2-]) ;
524 rule ParseTerm expression
526 # ParseTerm <expression> ;
528 # expression: unary ('*' unary)*
530 local result = [ ParseUnary $(expression) ] ;
531 local product = $(result[1]) ;
532 expression = $(result[2-]) ;
534 while $(expression[1]) = "*" {
539 # parse the next operand
540 result = [ ParseUnary $(expression[2-]) ] ;
541 expression = $(result[2-]) ;
543 # compute the product
544 product = [ $(operation) $(product) : $(result[1]) ] ;
547 return $(product) $(expression) ;
550 rule ParseExpression expression
552 # ParseExpression <expression> ;
554 # expression: term ('+'/'-' term)*
556 local result = [ ParseTerm $(expression) ] ;
557 local sum = $(result[1]) ;
558 expression = $(result[2-]) ;
560 while $(expression[1]) = "+" || $(expression[1]) = "-" {
563 if $(expression[1]) = "+" {
569 # parse the next operand
570 result = [ ParseTerm $(expression[2-]) ] ;
571 expression = $(result[2-]) ;
574 sum = [ $(operation) $(sum) : $(result[1]) ] ;
577 return $(sum) $(expression) ;
583 # Expr <expression> ;
585 # tokenize the expression
588 for string in $(expression) {
590 local split = [ Match "[ \t]*(-|[()+*]|[0-9]*)(.*)" : $(string) ] ;
592 Exit "Expr: Syntax error: Invalid token: \"$(string)\"." ;
595 tokens += $(split[1]) ;
596 string = $(split[2]) ;
600 local result = [ ParseExpression $(tokens) ] ;
602 Exit "Expr: Garbage at end of expression:" $(result[2-]) ;
605 return $(result[1]) ;