dymokomi/luce-js
Source of release 0.6.1
0.6.1 / src / engine / bigint_ops.lucb
#==============================================================================================
#
# bigint_ops - BigInt arithmetic: add, sub, neg, mul, div, rem, logic, shifts and pow
#
# DESCRIPTION:
# Port of quickjs.c "bigint support" lines 11811-12188. Every operation allocates
# a new, normalized JSBigInt and leaves its operands alone; the operands may be
# stack buffers (JSBigIntBuf). A function that returns NULL in C (a RangeError or
# an out-of-memory exception pending) fails here.
#
#==============================================================================================
# mark: Addition and multiplication =============================================================
# Compute a + b (b_neg = false) or a - b (b_neg = true).
# XXX: optimize
func js_bigint_add(ctx: Context*, a: const BigInt*, b: const BigInt*, b_neg: bool) -> BigInt*!:
let n2 = cutils.max_int((i32)a.len, (i32)b.len)
let n1 = cutils.min_int((i32)a.len, (i32)b.len)
let r = try js_bigint_new(ctx, n2)
let r_tab = js_bigint_tab(r)
let a_tab = js_bigint_tab(a)
let b_tab = js_bigint_tab(b)
# -b_neg: all ones when subtracting
let b_mask: u32 = 0xffffffff if b_neg else 0
# XXX: optimize
# common part
var carry = (u32)b_neg
var i: i32 = 0
while i < n1:
let op1 = a_tab[i]
let op2 = b_tab[i] ^ b_mask
let (v, c) = addc(op1, op2, carry)
r_tab[i] = v
carry = c
i += 1
let a_sign = -%(u32)js_bigint_sign(a)
let b_sign = (-%(u32)js_bigint_sign(b)) ^ b_mask
# part with sign extension of one operand
if a.len > b.len:
i = n1
while i < n2:
let op1 = a_tab[i]
let (v, c) = addc(op1, b_sign, carry)
r_tab[i] = v
carry = c
i += 1
elif a.len < b.len:
i = n1
while i < n2:
let op2 = b_tab[i] ^ b_mask
let (v, c) = addc(a_sign, op2, carry)
r_tab[i] = v
carry = c
i += 1
# part with sign extension for both operands. Extend the result if necessary
return try js_bigint_extend(ctx, r, a_sign +% b_sign +% carry)
# XXX: optimize
func js_bigint_neg(ctx: Context*, a: const BigInt*) -> BigInt*!:
var buf: BigIntBuf
let b = js_bigint_set_si(&buf, 0)
return try js_bigint_add(ctx, b, a, true)
func js_bigint_mul(ctx: Context*, a: const BigInt*, b: const BigInt*) -> BigInt*!:
let r = try js_bigint_new(ctx, (i32)(a.len + b.len))
let r_tab = js_bigint_tab(r)
let a_tab = js_bigint_tab(a)
let b_tab = js_bigint_tab(b)
mp_mul_basecase(r_tab, a_tab, a.len, b_tab, b.len)
# correct the result if negative operands (no overflow is possible)
if js_bigint_sign(a) != 0:
_ = mp_sub(r_tab + (usize)a.len, r_tab + (usize)a.len, b_tab, (i32)b.len, 0)
if js_bigint_sign(b) != 0:
_ = mp_sub(r_tab + (usize)b.len, r_tab + (usize)b.len, a_tab, (i32)a.len, 0)
return js_bigint_normalize(ctx, r)
# mark: Division ================================================================================
# return the division or the remainder. 'b' must be != 0. Fails in case of exception
# (division by zero or memory error)
func js_bigint_divrem(ctx: Context*, a: const BigInt*, b: const BigInt*, is_rem: bool) -> BigInt*!:
let a_tab = js_bigint_tab(a)
let b_tab = js_bigint_tab(b)
if b.len == 1 and b_tab[0] == 0:
try js_throw_range_error(ctx, "BigInt division by zero")
let a_sign = js_bigint_sign(a)
let b_sign = js_bigint_sign(b)
var na = (i32)a.len
var nb = (i32)b.len
let r = try js_bigint_new(ctx, na + 2)
let r_tab = js_bigint_tab(r)
if a_sign != 0:
_ = mp_neg(r_tab, a_tab, na)
else:
_ = cutils.memcpy(r_tab, a_tab, (usize)na * memory.size_of(u32))
# normalize
while na > 1 and r_tab[na - 1] == 0:
na -= 1
let tabb_block = js_malloc(ctx, (usize)nb * memory.size_of(u32)) catch failure:
js_free(ctx, r)
error(failure.code, failure.message)
let tabb = (u32*)tabb_block
if b_sign != 0:
_ = mp_neg(tabb, b_tab, nb)
else:
_ = cutils.memcpy(tabb, b_tab, (usize)nb * memory.size_of(u32))
# normalize
while nb > 1 and tabb[nb - 1] == 0:
nb -= 1
# trivial case if 'a' is small
if na < nb:
js_free(ctx, r)
js_free(ctx, tabb)
if is_rem:
# r = a
let r1 = try js_bigint_new(ctx, (i32)a.len)
_ = cutils.memcpy(js_bigint_tab(r1), a_tab, (usize)a.len * memory.size_of(u32))
return r1
else:
# q = 0
return try js_bigint_new_si(ctx, 0)
# normalize 'b'
let shift = (i32)js_limb_clz(tabb[nb - 1])
if shift != 0:
_ = mp_shl(tabb, tabb, nb, shift)
let h = mp_shl(r_tab, r_tab, na, shift)
if h != 0:
r_tab[na] = h
na += 1
# one more limb for the sign
let q = js_bigint_new(ctx, na - nb + 2) catch failure:
js_free(ctx, r)
js_free(ctx, tabb)
error(failure.code, failure.message)
let q_tab = js_bigint_tab(q)
mp_divnorm(q_tab, r_tab, (u32)na, tabb, (u32)nb)
js_free(ctx, tabb)
if is_rem:
js_free(ctx, q)
if shift != 0:
_ = mp_shr(r_tab, r_tab, nb, shift, 0)
r_tab[nb] = 0
nb += 1
if a_sign != 0:
_ = mp_neg(r_tab, r_tab, nb)
return js_bigint_normalize1(ctx, r, nb)
else:
js_free(ctx, r)
q_tab[na - nb + 1] = 0
if (a_sign ^ b_sign) != 0:
_ = mp_neg(q_tab, q_tab, (i32)q.len)
return js_bigint_normalize(ctx, q)
# mark: Bitwise operations ======================================================================
# and, or, xor
func js_bigint_logic(ctx: Context*, a0: const BigInt*, b0: const BigInt*, op: Op) -> BigInt*!:
var a = a0
var b = b0
if a.len < b.len:
let tmp = a
a = b
b = tmp
# a_len >= b_len
let a_len = (i32)a.len
let b_len = (i32)b.len
let a_tab = js_bigint_tab(a)
let b_tab = js_bigint_tab(b)
let b_sign = -%(u32)js_bigint_sign(b)
let r = try js_bigint_new(ctx, a_len)
let r_tab = js_bigint_tab(r)
var i: i32 = 0
match op:
.or_:
while i < b_len:
r_tab[i] = a_tab[i] | b_tab[i]
i += 1
while i < a_len:
r_tab[i] = a_tab[i] | b_sign
i += 1
.and_:
while i < b_len:
r_tab[i] = a_tab[i] & b_tab[i]
i += 1
while i < a_len:
r_tab[i] = a_tab[i] & b_sign
i += 1
.xor:
while i < b_len:
r_tab[i] = a_tab[i] ^ b_tab[i]
i += 1
while i < a_len:
r_tab[i] = a_tab[i] ^ b_sign
i += 1
_:
trap("js_bigint_logic: not a logic opcode")
return js_bigint_normalize(ctx, r)
func js_bigint_not(ctx: Context*, a: const BigInt*) -> BigInt*!:
let r = try js_bigint_new(ctx, (i32)a.len)
let r_tab = js_bigint_tab(r)
let a_tab = js_bigint_tab(a)
for i in 0..<(usize)a.len:
r_tab[i] = ~a_tab[i]
# no normalization is needed
return r
# mark: Shifts ==================================================================================
func js_bigint_shl(ctx: Context*, a: const BigInt*, shift1: u32) -> BigInt*!:
let a_tab = js_bigint_tab(a)
if a.len == 1 and a_tab[0] == 0:
return try js_bigint_new_si(ctx, 0) # zero case
let d = (i32)(shift1 // (u32)js_limb_bits)
let shift = (i32)(shift1 % (u32)js_limb_bits)
var r = try js_bigint_new(ctx, (i32)a.len + d)
let r_tab = js_bigint_tab(r)
var i: i32 = 0
while i < d:
r_tab[i] = 0
i += 1
if shift == 0:
for j in 0..<(usize)a.len:
r_tab[j + (usize)d] = a_tab[j]
else:
var l = mp_shl(r_tab + (usize)d, a_tab, (i32)a.len, shift)
if js_bigint_sign(a) != 0:
l |= (u32)0xffffffff << (u32)shift
r = try js_bigint_extend(ctx, r, l)
return r
func js_bigint_shr(ctx: Context*, a: const BigInt*, shift1: u32) -> BigInt*!:
let d = (i32)(shift1 // (u32)js_limb_bits)
let shift = (i32)(shift1 % (u32)js_limb_bits)
let a_sign = js_bigint_sign(a)
if d >= (i32)a.len:
return try js_bigint_new_si(ctx, -a_sign)
let n1 = (i32)a.len - d
var r = try js_bigint_new(ctx, n1)
let r_tab = js_bigint_tab(r)
let a_tab = js_bigint_tab(a)
if shift == 0:
var i: i32 = 0
while i < n1:
r_tab[i] = a_tab[i + d]
i += 1
# no normalization is needed
else:
_ = mp_shr(r_tab, a_tab + (usize)d, n1, shift, -%(u32)a_sign)
r = js_bigint_normalize(ctx, r)
return r
# mark: Exponentiation ==========================================================================
# Note: as in C, a failing multiplication in the square-and-multiply loop leaks 'r'.
func js_bigint_pow(ctx: Context*, a: const BigInt*, b: const BigInt*) -> BigInt*!:
let a_tab = js_bigint_tab(a)
let b_tab = js_bigint_tab(b)
# b must be >= 0
if js_bigint_sign(b) != 0:
try js_throw_range_error(ctx, "BigInt negative exponent")
if b.len == 1 and b_tab[0] == 0:
# a^0 = 1
return try js_bigint_new_si(ctx, 1)
elif a.len == 1:
var v = a_tab[0]
if v <= 1:
return try js_bigint_new_si(ctx, (i32)v)
elif v == 0xffffffff:
return try js_bigint_new_si(ctx, 1 - 2 * (i32)(b_tab[0] & 1))
var is_neg = (i32)v < 0
if is_neg:
v = -%v
if (v & (v -% 1)) == 0:
# v = 2^n
let n = js_limb_bits - 1 - (i32)js_limb_clz(v)
if b.len > 1:
try js_throw_range_error(ctx, "BigInt is too large") # overflow
if b_tab[0] > 0x7fffffff:
try js_throw_range_error(ctx, "BigInt is too large") # overflow
let e1 = (u64)b_tab[0] * (u64)n
if e1 > (u64)(bigint_max_size * js_limb_bits):
try js_throw_range_error(ctx, "BigInt is too large") # overflow
let e = (u32)e1
if is_neg:
is_neg = (b_tab[0] & 1) != 0
let r = try js_bigint_new(ctx,
(i32)((e + (u32)js_limb_bits + 1 - (u32)is_neg) // (u32)js_limb_bits))
let r_tab = js_bigint_tab(r)
_ = cutils.memset(r_tab, 0, memory.size_of(u32) * (usize)r.len)
let top = (u32)(1 - 2 * (i32)is_neg) << (e % (u32)js_limb_bits)
r_tab[e // (u32)js_limb_bits] = top
return r
if b.len > 1:
try js_throw_range_error(ctx, "BigInt is too large") # overflow
if b_tab[0] > 0x7fffffff:
try js_throw_range_error(ctx, "BigInt is too large") # overflow
let e = b_tab[0]
let n_bits = 32 - cutils.clz32(e)
var r = try js_bigint_new(ctx, (i32)a.len)
# not in QuickJS, which leaks 'r' when a multiplication fails
errdefer js_free(ctx, r)
_ = cutils.memcpy(js_bigint_tab(r), a_tab, (usize)a.len * memory.size_of(u32))
var i = n_bits - 2
while i >= 0:
var r1 = try js_bigint_mul(ctx, r, r)
js_free(ctx, r)
r = r1
if ((e >> (u32)i) & 1) != 0:
r1 = try js_bigint_mul(ctx, r, a)
js_free(ctx, r)
r = r1
i -= 1
return r