summaryrefslogtreecommitdiff
path: root/libstd/bigint.myr
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2014-01-21 23:47:54 -0500
committerOri Bernstein <ori@eigenstate.org>2014-01-21 23:47:54 -0500
commit9661b205b1d932f96693376bc920cfa6060fbed4 (patch)
tree484b6edb49a065a764de3d1b78836c06aa7116b8 /libstd/bigint.myr
parent5d9e71b6e4724f04b04fdb70452a2459f545ec98 (diff)
downloadmc-9661b205b1d932f96693376bc920cfa6060fbed4.tar.gz
Implement bigint shifts.
Diffstat (limited to 'libstd/bigint.myr')
-rw-r--r--libstd/bigint.myr62
1 files changed, 55 insertions, 7 deletions
diff --git a/libstd/bigint.myr b/libstd/bigint.myr
index 593a4a4..291e15f 100644
--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -33,15 +33,17 @@ pkg std =
const bigmul : (a : bigint#, b : bigint# -> bigint#)
const bigdiv : (a : bigint#, b : bigint# -> bigint#)
const bigshl : (a : bigint#, b : bigint# -> bigint#)
+ const bigsrl : (a : bigint#, b : bigint# -> bigint#)
+ const bigsra : (a : bigint#, b : bigint# -> bigint#)
/* bigint*int -> bigint ops */
const bigaddi : (a : bigint#, b : int64 -> bigint#)
const bigsubi : (a : bigint#, b : int64 -> bigint#)
const bigmuli : (a : bigint#, b : int64 -> bigint#)
const bigdivi : (a : bigint#, b : int64 -> bigint#)
- const bigshli : (a : bigint#, b : uint64 -> bigint#)
- const bigshri : (a : bigint#, b : uint64 -> bigint#)
- const bigsari : (a : bigint#, b : uint64 -> bigint#)
+ const bigslli : (a : bigint#, b : uint64 -> bigint#)
+ const bigsrli : (a : bigint#, b : uint64 -> bigint#)
+ const bigsrai : (a : bigint#, b : uint64 -> bigint#)
;;
const mkbigint = {v
@@ -307,13 +309,23 @@ const bigshl = {a, b
;;
}
-/*
-const bigsll = {a, b
+/* a >>= b, unsigned */
+const bigsrl = {a, b
+ match b.dig.len
+ | 0: -> a
+ | 1: -> bigsrli(a, b.dig[0] castto(uint64))
+ | n: die("shift by way too much\n")
+ ;;
}
-const bigshr = {a, b
+/* a >>= b, sign extending */
+const bigsra = {a, b
+ match b.dig.len
+ | 0: -> a
+ | 1: -> bigsrai(a, b.dig[0] castto(uint64))
+ | n: die("shift by way too much\n")
+ ;;
}
-*/
const trim = {a
var i
@@ -354,3 +366,39 @@ const bigshli = {a, s
;;
-> trim(a)
}
+
+const bigshri = {a, s
+ -> bigshrfill(a, s, 0)
+}
+
+const bigsari = {a, s
+ if a.sign == -1
+ bigshrfill(a, s, ~0)
+ else
+ bigshrfill(a, s, 0)
+ ;;
+}
+
+const bigshrfill = {a, s, fill
+ var off, shift
+ var t, carry
+ var i
+
+ off = s/32
+ shift = s % 32
+
+ /* blit over the base values */
+ for i = 0; i < a.dig.len - off; i++
+ a.dig[i] = a.dig[i + off]
+ ;;
+ for i = a.dig.len; i < a.dig.len + off; i++
+ a.dig[i] = fill
+ ;;
+ /* and shift over by the remainder */
+ for i = a.dig.len; i > 0; i--
+ t = (a.dig[i] castto(uint64))
+ a.dig[i] = (carry | (t >> shift)) castto(uint32)
+ carry = t << (32 - shift)
+ ;;
+ -> trim(a)
+}