Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-js

Source of release 0.6.1

0.6.1 / src / engine / math_sum_precise.lucb

#==============================================================================================
#
#   math_sum_precise - Math.sumPrecise: the exact sum of an iterable of numbers
#
#   DESCRIPTION:
#       Port of quickjs.c lines 47104-47358: the sum is accumulated exactly in a fixed-point
#       accumulator of 56-bit limbs covering the whole double range, renormalized every
#       SUM_PRECISE_COUNTER_INIT additions, and rounded once to the nearest double (ties to
#       even) at the end. Infinities and NaN are tracked in a state beside it.
#
#==============================================================================================

# mark: The accumulator =========================================================================

## The special values met so far (SumPreciseStateEnum).
enum SumPreciseStateEnum as i32:
    finite = 0
    infinity = 1
    ## must be after infinity
    minus_infinity = 2
    ## must be after minus_infinity
    nan = 3

let sp_limb_bits: u32 = 56
let sp_rnd_bits: u32 = sp_limb_bits - 53
# we add one extra limb to avoid having to test for overflows during the sum
let sum_precise_acc_len: i32 = 39

let sum_precise_counter_init: u32 = 250

## The state of an exact sum (SumPreciseState).
struct SumPreciseState:
    var state: SumPreciseStateEnum
    var counter: u32
    ## 'acc' contains n_limbs and is not necessarily normalized: acc[n_limbs - 1] may be
    ## 0. 0 indicates minus zero result when state = finite
    var n_limbs: i32
    var acc: i64[39]

# The mask of a limb's bits.
func sp_limb_mask() -> u64:
    return ((u64)1 << sp_limb_bits) - 1

func sum_precise_init(s: SumPreciseState*):
    for i in 0..<s.acc.length:
        s.acc[i] = 0
    s.state = SumPreciseStateEnum.finite
    s.counter = sum_precise_counter_init
    s.n_limbs = 0

# Propagate the carries so that every limb but the last is in [0, 2^56).
func sum_precise_renorm(s: SumPreciseState*):
    var carry: i64 = 0
    for i: i32 in 0..<s.n_limbs:
        let v = s.acc[(usize)i] +% carry
        s.acc[(usize)i] = (i64)((u64)v & sp_limb_mask())
        carry = v >> (i64)sp_limb_bits
    # we add a failsafe but it should be never reached in a
    # reasonnable amount of time
    if carry != 0 and s.n_limbs < sum_precise_acc_len:
        s.acc[(usize)s.n_limbs] = carry
        s.n_limbs += 1

# Add `d` to the sum. As in C, the limbs are two's complement words that wrap between
# renormalizations.
func sum_precise_add(s: SumPreciseState*, d: f64):
    let a = cutils.float64_as_uint64(d)
    let sgn = (i32)(a >> 63)
    let e = (i32)((a >> 52) & ((1 << 11) - 1))
    var m = a & (((u64)1 << 52) - 1)
    var p: i32 = 0
    var shift: u32 = 0
    if e == 2047:
        if m == 0:
            # +/- infinity
            if (s.state == SumPreciseStateEnum.nan or (s.state == SumPreciseStateEnum.minus_infinity and sgn == 0) or (s.state == SumPreciseStateEnum.infinity and sgn != 0)):
                s.state = SumPreciseStateEnum.nan
            else:
                s.state = (SumPreciseStateEnum)((i32)SumPreciseStateEnum.infinity + sgn)
        else:
            # NaN
            s.state = SumPreciseStateEnum.nan
        return
    elif e == 0:
        if m == 0:
            # zero
            if s.n_limbs == 0 and sgn == 0:
                s.n_limbs = 1
            return
        # subnormal
        p = 0
        shift = 0
    else:
        # Note: we sum even if state != finite to avoid tests
        m |= (u64)1 << 52
        shift = (u32)(e - 1)
        # 'p' is the position of a0 in acc. The division is normally
        # implementation as a multiplication by the compiler.
        p = (i32)(shift // sp_limb_bits)
        shift %= sp_limb_bits
    # add:
    let a0 = (m << shift) & sp_limb_mask()
    let a1 = m >> (sp_limb_bits - shift)
    let lo = (usize)p
    if sgn == 0:
        s.acc[lo] = s.acc[lo] +% (i64)a0
        s.acc[lo + 1] = s.acc[lo + 1] +% (i64)a1
    else:
        s.acc[lo] = s.acc[lo] -% (i64)a0
        s.acc[lo + 1] = s.acc[lo + 1] -% (i64)a1
    s.n_limbs = cutils.max_int(s.n_limbs, p + 2)

    s.counter -= 1
    if s.counter == 0:
        s.counter = sum_precise_counter_init
        sum_precise_renorm(s)

# The sum rounded to the nearest double, ties to even.
func sum_precise_get_result(s: SumPreciseState*) -> f64:
    if s.state != SumPreciseStateEnum.finite:
        match s.state:
            .minus_infinity:
                return -math.infinity
            .nan:
                return math.nan
            _:
                return math.infinity

    sum_precise_renorm(s)

    # extract the sign and absolute value
    var n = s.n_limbs
    # minus zero result
    if n == 0:
        return -0.0

    # normalize
    while n > 0 and s.acc[(usize)(n - 1)] == 0:
        n -= 1
    # zero result. The spec tells it is always positive in the finite case
    if n == 0:
        return 0.0
    let is_neg = s.acc[(usize)(n - 1)] < 0
    if is_neg:
        # negate
        # XXX: do it only when needed
        var carry: u64 = 1
        for i: i32 in 0..<(n - 1):
            let v = (sp_limb_mask() -% (u64)s.acc[(usize)i]) +% carry
            carry = v >> sp_limb_bits
            s.acc[(usize)i] = (i64)(v & sp_limb_mask())
        let top = (usize)(n - 1)
        s.acc[top] = (i64)(((-%(u64)s.acc[top]) +% carry) -% 1)
        while n > 1 and s.acc[(usize)(n - 1)] == 0:
            n -= 1
    let sign_bit = (u64)is_neg << 63
    # subnormal case
    if n == 1 and (u64)s.acc[0] < ((u64)1 << 52):
        return cutils.uint64_as_float64(sign_bit | (u64)s.acc[0])
    # normal case
    var e = n * (i32)sp_limb_bits
    var p = n - 1
    var m = (u64)s.acc[(usize)p]
    let shift = cutils.clz64(m) - (64 - (i32)sp_limb_bits)
    e = e - shift - 52
    if shift != 0:
        m <<= (u64)shift
        if p > 0:
            p -= 1
            let shift1 = sp_limb_bits - (u32)shift
            let nz = (u64)s.acc[(usize)p] & (((u64)1 << shift1) - 1)
            m = m | ((u64)s.acc[(usize)p] >> shift1) | (u64)(nz != 0)
    if (m & (((u64)1 << sp_rnd_bits) - 1)) == ((u64)1 << (sp_rnd_bits - 1)):
        # see if the LSB part is non zero for the final rounding
        while p > 0:
            p -= 1
            if s.acc[(usize)p] != 0:
                m |= 1
                break
    # rounding to nearest with ties to even
    let addend = ((u64)1 << (sp_rnd_bits - 1)) - 1 + ((m >> sp_rnd_bits) & 1)
    m = (m + addend) >> sp_rnd_bits
    # handle overflow in the rounding
    if m == ((u64)1 << 53):
        e += 1
    if e >= 2047:
        # infinity
        return cutils.uint64_as_float64(sign_bit | ((u64)2047 << 52))
    m &= ((u64)1 << 52) - 1
    return cutils.uint64_as_float64(sign_bit | ((u64)e << 52) | m)

# mark: Math.sumPrecise =========================================================================

func js_math_sum_precise(ctx: Context*, this_val: Value, argc: i32, argv: Value*) -> Value!:
    var s_s: SumPreciseState
    let s = &s_s

    let iter = try js_get_iterator(ctx, argv[0], false)
    defer js_free_value(ctx, iter)
    let next = try js_get_property(ctx, iter, atom_next)
    defer js_free_value(ctx, next)
    sum_precise_init(s)
    while true:
        var done = false
        # no arguments: any valid pointer for argv
        var no_args = js_undefined()
        let item = try js_iterator_next(ctx, iter, next, 0, &no_args, &done)
        if done:
            break
        var d: f64 = 0.0
        if item.tag == Tag.float64:
            d = js_value_get_float64(item)
        elif item.tag == Tag.int:
            d = f64(js_value_get_int(item))
        else:
            js_free_value(ctx, item)
            # the iterator is closed with the TypeError pending
            errdefer js_iterator_close(ctx, iter, true) catch failure: recover ()
            try js_throw_type_error(ctx, "not a number")
        sum_precise_add(s, d)
    return js_new_float64_raw(sum_precise_get_result(s))