ref: def799e175eb9cd20b9cab16dcdca22e1d0bbc29
parent: f5da3fe38642020090709cd8f76d54d399d7d3b2
author: Ori Bernstein <[email protected]>
date: Wed Jan 22 13:22:47 EST 2014
Add single digit division, and make bigint output use it.
--- 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,67 @@
-> 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#]+ const B = (1ul << 32)
+ /*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*B + 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/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;