ref: f922a2c6dfb9a8043f82a19946a06b85469b3be1
parent: bbe534857ed16647c1cba467dbf0db5f16cdf91d
parent: 964632bdffbee7760477e2faa3c862a18528f518
author: Ori Bernstein <[email protected]>
date: Wed Jan 22 16:23:26 EST 2014
Merge branch 'master' of git+ssh://mimir.eigenstate.org/git/ori/mc
--- a/TODO
+++ b/TODO
@@ -2,10 +2,7 @@
- Closures [Tests: closure]
- Not-boneheaded asm [Tests: ]
- Optimized asm [Tests: ]
- - Generic types [Tests: generictype, genericrec]
- - Floating point support [Tests: float]
- Use-def analysis [Tests: usedef]
- Deferred code [Tests: ]
- Module-mains [Tests: ]
- User defined traits [Tests: ]
- - Foreach loops [Tests: ]
--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -32,6 +32,8 @@
const bigsub : (a : bigint#, b : bigint# -> bigint#)
const bigmul : (a : bigint#, b : bigint# -> bigint#)
const bigdiv : (a : bigint#, b : bigint# -> bigint#)
+ const bigmod : (a : bigint#, b : bigint# -> bigint#)
+ const bigdivmod : (a : bigint#, b : bigint# -> [bigint#, bigint#])
const bigshl : (a : bigint#, b : bigint# -> bigint#)
const bigshr : (a : bigint#, b : bigint# -> bigint#)
const bigshra : (a : bigint#, b : bigint# -> bigint#)
@@ -78,31 +80,38 @@
/* for now, just dump out something for debugging... */
const bigfmt = {buf, valconst digitchars = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f']
- var n, i, pow
+ var v
+ var n, i
+ var tmp
+ var rem
n = 0
- if val.sign == -1
+ if val.sign == 0
+ n += encode(buf, '0')
+ -> n
+ elif val.sign == -1
n += encode(buf, '-')
;;
- pow = 0
- for v in val.dig
- if pow > 0
- n += bfmt(buf[n:], "(")- for i = 0; i < pow; i++
- n += bfmt(buf[n:], "4294967296")
- if i != pow - 1
- n += bfmt(buf[n:], "*")
- ;;
- ;;
- n += bfmt(buf[n:], ")*")
+ val = bigdup(val)
+ /* generate the digits in reverse order */
+ while !bigiszero(val)
+ (v, rem) = bigdivmod(val, mkbigint(10))
+ if rem.dig.len > 0
+ n += bfmt(buf[n:], "%c", digitchars[rem.dig[0]])
+ else
+ n += bfmt(buf[n:], "0")
;;
- pow++
- n += bfmt(buf[n:], "%ui + ", v)
+ bigfree(val)
+ bigfree(rem)
+ val = v
;;
-
- if val.sign == 0
- n += encode(buf, '0')
+ bigfree(val)
+ /* we only generated ascii digits, so this works. ugh. */
+ for i = 0; i < n/2; i++
+ tmp = buf[i]
+ buf[i] = buf[n - i - 1]
+ buf[n - i - 1] = tmp
;;
-> n
}
@@ -284,20 +293,66 @@
-> trim(a)
}
+const bigdiv = {a : bigint#, b : bigint# -> bigint#+ var q, r
+
+ (q, r) = bigdivmod(a, b)
+ bigfree(r)
+ slfree(a.dig)
+ a.dig = q.dig
+ free(q)
+ -> a
+}
+const bigmod = {a : bigint#, b : bigint# -> bigint#+ var q, r
+
+ (q, r) = bigdivmod(a, b)
+ bigfree(q)
+ slfree(a.dig)
+ a.dig = r.dig
+ free(r)
+ -> a
+}
+
/* a /= b */
-const bigdiv = {a, b+const bigdivmod = {a : bigint#, b : bigint# -> [bigint#, bigint#]+ /*var u, v /* normalized a and b */*/
+ var q/*, qhat /* quotient and estimated quotient */*/
+ /*
+ var rhat /* remainder */
+ var s, i, j, t
+ var p
+ */
+ var j
+ var carry, b0, aj
+
if bigiszero(b)
die("divide by zero\n");;
+ q = zalloc()
+ q.dig = slzalloc(max(a.dig.len, b.dig.len))
if a.sign != b.sign
- a.sign = -1
+ q.sign = -1
else
- a.sign = 1
+ q.sign = 1
;;
- die("big division not yet implemented\n")- -> trim(a)
+ /* handle single digit divisor separately for performance */
+ if b.dig.len == 1
+ carry = 0
+ b0 = (b.dig[0] castto(uint64))
+ for j = a.dig.len; j > 0; j--
+ aj = (a.dig[j - 1] castto(uint64))
+ q.dig[j - 1] = (((carry << 32) + aj)/b0) castto(uint32)
+ carry = (carry << 32) + aj - (q.dig[j-1] castto(uint64))*b0
+ ;;
+ for v in q.dig
+ ;;
+ -> (trim(q), trim(mkbigint(carry castto(int32))))
+ ;;
+ die("big bigint division not implemented\n")+ -> (trim(a), mkbigint(carry castto(int32)))
}
/* a <<= b */
--- a/myrbuild/myrbuild.c
+++ b/myrbuild/myrbuild.c
@@ -157,7 +157,7 @@
void getdeps(char *file, char **deps, size_t depsz, size_t *ndeps)
{- char buf[2048]; /* if you hit this limit, shoot yourself */
+ char buf[2048];
regmatch_t m[2];
size_t i;
--- a/parse/gram.y
+++ b/parse/gram.y
@@ -654,10 +654,13 @@
{$$ = mkexprl($1->line, Otup, $2.nl, $2.nn);} littok : Tstrlit {$$ = mkstr($1->line, $1->str);}- | Tintlit {$$ = mkint($1->line, $1->intval);} | Tchrlit {$$ = mkchar($1->line, $1->chrval);} | Tfloatlit {$$ = mkfloat($1->line, $1->fltval);} | Tboollit {$$ = mkbool($1->line, !strcmp($1->str, "true"));}+ | Tintlit
+ {$$ = mkint($1->line, $1->intval);+ if ($1->inttype)
+ $$->lit.type = mktype($1->line, $1->inttype);}
;
funclit : Tobrace params Tendln blkbody Tcbrace
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -84,6 +84,7 @@
/* values parsed out */
vlong intval;
+ Ty inttype; /* for explicitly specified suffixes */
double fltval;
uint32_t chrval;
};
--- a/parse/tok.c
+++ b/parse/tok.c
@@ -623,6 +623,7 @@
int start;
int c;
int isfloat;
+ int unsignedval;
t = NULL;
isfloat = 0;
@@ -646,6 +647,55 @@
t = mktok(Tintlit);
t->str = strdupn(&fbuf[start], fidx - start);
t->intval = strtol(t->str, NULL, base);
+ /* check suffixes:
+ * u -> unsigned
+ * l -> 64 bit
+ * i -> 32 bit
+ * w -> 16 bit
+ * b -> 8 bit
+ */
+ unsignedval = 0;
+nextsuffix:
+ switch (peek()) {+ case 'u':
+ if (unsignedval == 1)
+ fatal(line, "Duplicate 'u' integer specifier");
+ next();
+ unsignedval = 1;
+ goto nextsuffix;
+ case 'l':
+ next();
+ if (unsignedval)
+ t->inttype = Tyuint64;
+ else
+ t->inttype = Tyint64;
+ break;
+ case 'i':
+ next();
+ if (unsignedval)
+ t->inttype = Tyuint32;
+ else
+ t->inttype = Tyint32;
+ break;
+ case 's':
+ next();
+ if (unsignedval)
+ t->inttype = Tyuint16;
+ else
+ t->inttype = Tyint16;
+ break;
+ case 'b':
+ next();
+ if (unsignedval)
+ t->inttype = Tyuint8;
+ else
+ t->inttype = Tyint8;
+ break;
+ default:
+ if (unsignedval)
+ fatal(line, "Unrecognized character int type specifier after 'u'");
+ break;
+ }
}
return t;
--- /dev/null
+++ b/test/bigint.myr
@@ -1,0 +1,26 @@
+use std
+
+const main = {+ var a, b, c, d, e
+ var buf : byte[1024], n
+
+ a = std.mkbigint(1234)
+ b = std.mkbigint(0x7fffffff)
+ c = std.mkbigint(7919)
+ d = std.mkbigint(113051)
+ e = std.mkbigint(11)
+
+ std.bigmul(a, b)
+ std.bigmul(a, b)
+ std.bigadd(a, c)
+ std.bigsub(a, d)
+ std.bigdiv(a, e)
+
+ std.bigfree(b)
+ std.bigfree(c)
+ std.bigfree(d)
+ std.bigfree(e)
+
+ n = std.bigfmt(buf[:], a)
+ std.put("%s\n", buf[:n])+}
--- a/test/tests
+++ b/test/tests
@@ -116,6 +116,7 @@
B strsplit C
B strfind C
B strjoin C
+B bigint P 517347321949036993306
# B local-labels E 10 ## BUGGERED
F declmismatch
F infermismatch