Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / std / strings / floats.lucb

#==============================================================================================
#
#   floats - Floating-point text: correctly rounded parsing, shortest formatting
#
#   DESCRIPTION:
#       Decimal text to f64 and f32, correctly rounded to nearest with ties to even, and
#       back as the shortest digits that read back to the same value. Parsing takes a
#       mantissa and a power of ten that are both exact (up to 2^53 and 10^22) through one
#       float multiplication or division (Clinger's fast path, correctly rounded in the
#       default rounding mode Luce never changes), and the rest through Eisel-Lemire
#       (Lemire, "Number Parsing at a Gigabyte per Second", 2021, in the form of Go's
#       strconv) over float_tables' 128-bit powers of ten; what that cannot decide (a tie,
#       a subnormal, digits past the 19th that matter) goes to a decimal of up to 800 digits
#       scaled by powers of two (strconv's slow path), in integer arithmetic. Formatting is
#       float_text's shortest digits (Ryu), in integers. No C library and no locale.
#
#==============================================================================================

# mark: Parsing ================================================================================

## Parse `text`, all of it, as the f64 nearest its value, ties to even: an optional sign, then
## digits with an optional point (`1`, `1.5`, `.5`, `5.`) and an optional exponent (`e` or
## `E`, an optional sign, digits), or `inf`, `infinity` or `nan` in any case. NaN is the
## quiet NaN with the written sign. Fails with invalid_number when `text` is not a number or
## goes on past one (scan_f64 says where it ends), and with number_out_of_range when it
## rounds past the largest finite f64; a smaller magnitude than the least subnormal is a
## signed zero. No locale, whitespace, underscore or hex form is read.
pub func parse_f64(text: str) -> f64!:
    let (value, used) = try scan_f64(text.bytes)
    if used != text.length:
        error(invalid_number, "the text goes on past the number")
    return value

## The f32 counterpart of parse_f64, rounded once from the decimal (never through f64).
pub func parse_f32(text: str) -> f32!:
    let (value, used) = try scan_f32(text.bytes)
    if used != text.length:
        error(invalid_number, "the text goes on past the number")
    return value

## The number that starts `text`, read as parse_f64 reads one, and how many bytes spell it:
## the longest prefix that is a number (`1e` is the number `1`, one byte). A reader continues
## from there, and names that position when what follows is not what it expects. Fails with
## invalid_number when no number starts `text`, number_out_of_range as parse_f64 does.
pub func scan_f64(text: const u8[]) -> (f64, usize)!:
    let number = scan(text)
    if number.kind == nothing_kind:
        error(invalid_number, "no number starts the text")
    let sign: u64 = 0x8000000000000000 if number.negative else 0
    if number.kind == infinity_kind:
        return (f64.bits(sign | 0x7FF0000000000000), number.used)
    if number.kind == nan_kind:
        return (f64.bits(sign | 0x7FF8000000000000), number.used)
    if number.mantissa == 0:
        return (f64.bits(sign), number.used)
    if not number.truncated and number.mantissa <= 0x20000000000000 and number.exponent >= -22 and number.exponent <= 22:
        # Clinger's fast path: the mantissa and the power of ten are both exact, so one
        # correctly rounded multiplication or division is the nearest f64
        var exact = (f64)number.mantissa
        if number.exponent > 0:
            exact = exact * exact_powers[(usize)number.exponent]
        elif number.exponent < 0:
            exact = exact / exact_powers[(usize)(-number.exponent)]
        return (-exact if number.negative else exact, number.used)
    let magnitude = number.exponent + number.digits - 1
    if magnitude > 309:
        error(number_out_of_range, "the number is beyond the largest f64")
    if magnitude < -330:
        return (f64.bits(sign), number.used)
    if let value = lemire64(number.mantissa, number.exponent, number.negative):
        # digits past the 19th: the value lies between mantissa and mantissa + 1 units
        if not number.truncated:
            return (value, number.used)
        if let above = lemire64(number.mantissa + 1, number.exponent, number.negative):
            if above.bits() == value.bits():
                return (value, number.used)
    var slow = Decimal()
    slow.read(text[..<number.used])
    let (bits, overflow) = slow.float_bits(52, 11, -1023)
    if overflow:
        error(number_out_of_range, "the number is beyond the largest f64")
    return (f64.bits(bits | sign), number.used)

## The f32 counterpart of scan_f64.
pub func scan_f32(text: const u8[]) -> (f32, usize)!:
    let number = scan(text)
    if number.kind == nothing_kind:
        error(invalid_number, "no number starts the text")
    let sign: u32 = 0x80000000 if number.negative else 0
    if number.kind == infinity_kind:
        return (f32.bits(sign | 0x7F800000), number.used)
    if number.kind == nan_kind:
        return (f32.bits(sign | 0x7FC00000), number.used)
    if number.mantissa == 0:
        return (f32.bits(sign), number.used)
    if not number.truncated and number.exponent == 0 and number.mantissa <= 0x1000000:
        let exact = (f32)number.mantissa
        return (-exact if number.negative else exact, number.used)
    let magnitude = number.exponent + number.digits - 1
    if magnitude > 39:
        error(number_out_of_range, "the number is beyond the largest f32")
    if magnitude < -66:
        return (f32.bits(sign), number.used)
    if let value = lemire32(number.mantissa, number.exponent, number.negative):
        if not number.truncated:
            return (value, number.used)
        if let above = lemire32(number.mantissa + 1, number.exponent, number.negative):
            if above.bits() == value.bits():
                return (value, number.used)
    var slow = Decimal()
    slow.read(text[..<number.used])
    let (bits, overflow) = slow.float_bits(23, 8, -127)
    if overflow:
        error(number_out_of_range, "the number is beyond the largest f32")
    return (f32.bits((u32)bits | sign), number.used)

## Every power of ten an f64 holds exactly, 10^0 to 10^22.
let exact_powers: f64[23] = [1.0, 10.0, 100.0, 1000.0, 10000.0, 100000.0, 1000000.0, 10000000.0,
                             100000000.0, 1000000000.0, 10000000000.0, 100000000000.0, 1000000000000.0, 10000000000000.0,
                             100000000000000.0, 1000000000000000.0, 10000000000000000.0, 100000000000000000.0,
                             1000000000000000000.0, 10000000000000000000.0, 100000000000000000000.0,
                             1000000000000000000000.0, 10000000000000000000000.0]

let finite_kind: u8 = 0
let infinity_kind: u8 = 1
let nan_kind: u8 = 2
let nothing_kind: u8 = 3

## A number as scanned: `mantissa * 10^exponent` from its first 19 significant digits.
struct Scanned:
    var negative: bool = false
    var kind: u8 = 0
    var mantissa: u64 = 0
    var digits: i64 = 0
    var exponent: i64 = 0
    ## Whether a nonzero digit past the 19th was left out of `mantissa`.
    var truncated: bool = false
    var used: usize = 0

## The number at the start of `text`: its sign, kind, leading digits and length. The digits
## before the point and after it are read by a loop each, as the digits come: a number of
## a usda array or a JSON document costs a compare and a multiply-add a digit.
inline func scan(text: const u8[]) -> Scanned:
    var number = Scanned()
    let end = text.length
    var at: usize = 0
    if at < end and (text[at] == '-' or text[at] == '+'):
        number.negative = text[at] == '-'
        at += 1
    if at < end and text[at] > '9':
        # a letter: only the special words start with one
        if let length = special_word(text[at..]):
            number.kind = infinity_kind if length != 3 or ascii_lower(text[at]) == 'i' else nan_kind
            number.used = at + length
            return number
        number.kind = nothing_kind
        return number
    let whole = at
    # leading zeros say nothing
    while at < end and text[at] == '0':
        at += 1
    # counts, not checked: none can pass the text's length
    var mantissa: u64 = 0
    var digits: usize = 0
    var dropped: usize = 0
    var scaled: usize = 0
    var truncated = false
    while at < end:
        let digit = text[at] -% '0'
        if digit > 9:
            break
        if digits < 19:
            # nineteen digits stay below 2^64
            mantissa = mantissa *% 10 +% (u64)digit
            digits = digits +% 1
        else:
            if digit != 0:
                truncated = true
            dropped = dropped +% 1
        at = at +% 1
    var seen = at > whole
    if at < end and text[at] == '.':
        at += 1
        let fraction = at
        if digits == 0:
            # zeros after the point and before the first digit scale what follows
            while at < end and text[at] == '0':
                at = at +% 1
            scaled = at -% fraction
        while at < end:
            let digit = text[at] -% '0'
            if digit > 9:
                break
            if digits < 19:
                mantissa = mantissa *% 10 +% (u64)digit
                digits = digits +% 1
                scaled = scaled +% 1
            elif digit != 0:
                truncated = true
            at = at +% 1
        seen = seen or at > fraction
    if not seen:
        number.kind = nothing_kind
        return number
    let exponent = (i64)dropped - (i64)scaled
    number.mantissa = mantissa
    number.digits = (i64)digits
    number.exponent = exponent
    number.truncated = truncated
    number.used = at
    if at < end and (text[at] == 'e' or text[at] == 'E'):
        var after = at + 1
        var down = false
        if after < end and (text[after] == '-' or text[after] == '+'):
            down = text[after] == '-'
            after += 1
        var power: i64 = 0
        let first = after
        while after < end and text[after] >= '0' and text[after] <= '9':
            # beyond any f64 either way; the cap keeps the sum from wrapping
            if power < 100000:
                power = power * 10 + (i64)(text[after] - '0')
            after += 1
        if after > first:
            number.exponent += -power if down else power
            number.used = after
    return number

## The length of `inf`, `infinity` or `nan` (any case) at the start of `word`, the longest.
noinline func special_word(word: const u8[]) -> usize?:
    if starts_word(word, "infinity"):
        return 8
    if starts_word(word, "inf") or starts_word(word, "nan"):
        return 3
    return none

func starts_word(text: const u8[], word: str) -> bool:
    if text.length < word.length:
        return false
    var at: usize = 0
    while at < word.length:
        if ascii_lower(text[at]) != word.bytes[at]:
            return false
        at += 1
    return true

func ascii_lower(byte: u8) -> u8:
    return byte + 32 if byte >= 'A' and byte <= 'Z' else byte

# mark: Eisel-Lemire ===========================================================================

## The decimal exponents lemire_powers covers.
let smallest_power: i64 = -348
let largest_power: i64 = 347

## `mantissa * 10^exponent` as the nearest f64, or none when the 128-bit product cannot
## decide it (a tie, a subnormal, past the range): the slow path decides then.
func lemire64(mantissa: u64, exponent: i64, negative: bool) -> f64?:
    if exponent < smallest_power or exponent > largest_power:
        return none
    let zeros = leading_zeros(mantissa)
    let man = mantissa << zeros
    var binary = (u64)(((217706 * exponent) >> 16) + 64 + 1023 - (i64)zeros)
    let row = (usize)(exponent - smallest_power) * 2
    var low: u64 = 0
    var high = float_text.product(man, lemire_powers[row], &low)
    # the top 55 bits may be off by the truncated low word: widen when unsure
    if high & 0x1FF == 0x1FF and low +% man < man:
        var extra_low: u64 = 0
        let extra_high = float_text.product(man, lemire_powers[row + 1], &extra_low)
        var merged_high = high
        let merged_low = low +% extra_high
        if merged_low < low:
            merged_high = merged_high +% 1
        if merged_high & 0x1FF == 0x1FF and merged_low +% 1 == 0 and extra_low +% man < man:
            return none
        high = merged_high
        low = merged_low
    let top = high >> 63
    var result = high >> (top + 9)
    binary = binary -% (1 ^ top)
    # an exact halfway case needs the whole decimal to break the tie
    if low == 0 and high & 0x1FF == 0 and result & 3 == 1:
        return none
    result = (result + (result & 1)) >> 1
    if (result >> 53) > 0:
        result >>= 1
        binary = binary +% 1
    # zero or wrapped: subnormal; 0x7FF or more: infinite
    if binary -% 1 >= 0x7FF - 1:
        return none
    var bits = (binary << 52) | (result & 0xFFFFFFFFFFFFF)
    if negative:
        bits |= 0x8000000000000000
    return f64.bits(bits)

## lemire64 for f32: 24 bits kept of the product's top 64.
func lemire32(mantissa: u64, exponent: i64, negative: bool) -> f32?:
    if exponent < smallest_power or exponent > largest_power:
        return none
    let zeros = leading_zeros(mantissa)
    let man = mantissa << zeros
    var binary = (u64)(((217706 * exponent) >> 16) + 64 + 127 - (i64)zeros)
    let row = (usize)(exponent - smallest_power) * 2
    var low: u64 = 0
    var high = float_text.product(man, lemire_powers[row], &low)
    if high & 0x3FFFFFFFFF == 0x3FFFFFFFFF and low +% man < man:
        var extra_low: u64 = 0
        let extra_high = float_text.product(man, lemire_powers[row + 1], &extra_low)
        var merged_high = high
        let merged_low = low +% extra_high
        if merged_low < low:
            merged_high = merged_high +% 1
        if merged_high & 0x3FFFFFFFFF == 0x3FFFFFFFFF and merged_low +% 1 == 0 and extra_low +% man < man:
            return none
        high = merged_high
        low = merged_low
    let top = high >> 63
    var result = high >> (top + 38)
    binary = binary -% (1 ^ top)
    if low == 0 and high & 0x3FFFFFFFFF == 0 and result & 3 == 1:
        return none
    result = (result + (result & 1)) >> 1
    if (result >> 24) > 0:
        result >>= 1
        binary = binary +% 1
    if binary -% 1 >= 0xFF - 1:
        return none
    var bits = (u32)((binary << 23) | (result & 0x7FFFFF))
    if negative:
        bits |= 0x80000000
    return f32.bits(bits)

## Leading zero bits of a nonzero value.
inline func leading_zeros(value: u64) -> u64:
    var v = value
    var count: u64 = 0
    if v & 0xFFFFFFFF00000000 == 0:
        count += 32
        v <<= 32
    if v & 0xFFFF000000000000 == 0:
        count += 16
        v <<= 16
    if v & 0xFF00000000000000 == 0:
        count += 8
        v <<= 8
    if v & 0xF000000000000000 == 0:
        count += 4
        v <<= 4
    if v & 0xC000000000000000 == 0:
        count += 2
        v <<= 2
    if v & 0x8000000000000000 == 0:
        count += 1
    return count

# mark: The slow path ==========================================================================

## How many digits a Decimal keeps; a nonzero digit past them only marks it truncated.
let decimal_capacity: usize = 800
## The most a Decimal shifts by in one pass: nine times 2^60 and a carry fit a u64.
let largest_shift: u32 = 60
## For a decimal point at d, 10^d < 2^powers_of_two[d]: how far a shift brings it down.
let powers_of_two: i64[9] = [1, 3, 6, 9, 13, 16, 19, 23, 26]

## A decimal `0.d[0]d[1]... * 10^point`, digits 0 through 9, no trailing zeros: exact for
## any text up to 800 significant digits, and scaled by powers of two to find the binary
## value when Eisel-Lemire cannot (strconv's slow path).
struct Decimal:
    var digits: u8[800]
    var count: usize = 0
    var point: i64 = 0
    var truncated: bool = false

    ## The finite number `text` spells, which scan has read already.
    func read(text: const u8[]):
        var at: usize = 0
        if at < text.length and (text[at] == '-' or text[at] == '+'):
            at += 1
        var after_point = false
        while at < text.length:
            let byte = text[at]
            if byte == '.':
                after_point = true
            elif byte >= '0' and byte <= '9':
                let digit = byte - '0'
                if self.count == 0 and digit == 0:
                    if after_point:
                        self.point -= 1
                else:
                    if not after_point:
                        self.point += 1
                    if self.count < decimal_capacity:
                        self.digits[self.count] = digit
                        self.count += 1
                    elif digit != 0:
                        self.truncated = true
            else:
                break
            at += 1
        if at < text.length and (text[at] == 'e' or text[at] == 'E'):
            at += 1
            var down = false
            if at < text.length and (text[at] == '-' or text[at] == '+'):
                down = text[at] == '-'
                at += 1
            var power: i64 = 0
            while at < text.length and text[at] >= '0' and text[at] <= '9':
                if power < 100000:
                    power = power * 10 + (i64)(text[at] - '0')
                at += 1
            self.point += -power if down else power
        self.trim()

    ## The value's bits in a format of `mantissa_bits` stored mantissa bits, `exponent_bits`
    ## exponent bits and exponent bias `-bias`, rounded to nearest, ties to even; and
    ## whether it overflowed to infinity (then the bits are infinity's).
    func float_bits(mantissa_bits: u32, exponent_bits: u32, bias: i64) -> (u64, bool):
        let largest = ((i64)1 << (i64)exponent_bits) - 1
        var exponent: i64 = 0
        var mantissa: u64 = 0
        var overflow = false
        if self.count == 0 or self.point < -330:
            exponent = bias
        elif self.point > 310:
            overflow = true
        else:
            # into [0.5, 1) by powers of two
            while self.point > 0:
                let n = 27 if self.point >= 9 else powers_of_two[(usize)self.point]
                self.shift(-n)
                exponent += n
            while self.point < 0 or (self.point == 0 and self.digits[0] < 5):
                let n = 27 if -self.point >= 9 else powers_of_two[(usize)(-self.point)]
                self.shift(n)
                exponent -= n
            # the format's range is [1, 2)
            exponent -= 1
            # below the least normal exponent: a subnormal, with fewer bits
            if exponent < bias + 1:
                let n = bias + 1 - exponent
                self.shift(-n)
                exponent += n
            if exponent - bias >= largest:
                overflow = true
            else:
                self.shift((i64)mantissa_bits + 1)
                mantissa = self.rounded_integer()
                # rounding carried into a new bit
                if mantissa == (u64)2 << (u64)mantissa_bits:
                    mantissa >>= 1
                    exponent += 1
                    if exponent - bias >= largest:
                        overflow = true
                if mantissa & ((u64)1 << (u64)mantissa_bits) == 0:
                    exponent = bias
        if overflow:
            mantissa = 0
            exponent = largest + bias
        var bits = mantissa & (((u64)1 << (u64)mantissa_bits) - 1)
        bits |= (u64)((exponent - bias) & largest) << (u64)mantissa_bits
        return (bits, overflow)

    ## Multiply by 2^k, or divide by 2^-k when k is negative.
    func shift(k: i64):
        if self.count == 0:
            return
        var left = k
        while left > (i64)largest_shift:
            self.shift_left(largest_shift)
            left -= (i64)largest_shift
        while left < -(i64)largest_shift:
            self.shift_right(largest_shift)
            left += (i64)largest_shift
        if left > 0:
            self.shift_left((u32)left)
        elif left < 0:
            self.shift_right((u32)(-left))

    ## Multiply by 2^k, k at most largest_shift: the digits times 2^k written right to left.
    func shift_left(k: u32):
        var scratch: u8[820] = ---
        let end = self.count + 20
        var write = end
        var carry: u64 = 0
        var read = self.count
        while read > 0:
            read -= 1
            carry += (u64)self.digits[read] << (u64)k
            let quotient = carry // 10
            write -= 1
            scratch[write] = (u8)(carry - quotient * 10)
            carry = quotient
        while carry > 0:
            let quotient = carry // 10
            write -= 1
            scratch[write] = (u8)(carry - quotient * 10)
            carry = quotient
        let produced = end - write
        let kept = produced if produced < decimal_capacity else decimal_capacity
        var at: usize = 0
        while at < produced:
            if at < kept:
                self.digits[at] = scratch[write + at]
            elif scratch[write + at] != 0:
                self.truncated = true
            at += 1
        self.point += (i64)produced - (i64)self.count
        self.count = kept
        self.trim()

    ## Divide by 2^k, k at most largest_shift.
    func shift_right(k: u32):
        var read: usize = 0
        var write: usize = 0
        var n: u64 = 0
        # enough leading digits to cover the first quotient digit
        while (n >> (u64)k) == 0:
            if read >= self.count:
                if n == 0:
                    self.count = 0
                    return
                while (n >> (u64)k) == 0:
                    n = n * 10
                    read += 1
                break
            n = n * 10 + (u64)self.digits[read]
            read += 1
        self.point -= (i64)read - 1
        let mask = ((u64)1 << (u64)k) - 1
        while read < self.count:
            let next = self.digits[read]
            self.digits[write] = (u8)(n >> (u64)k)
            write += 1
            n = (n & mask) * 10 + (u64)next
            read += 1
        while n > 0:
            let digit = n >> (u64)k
            n &= mask
            if write < decimal_capacity:
                self.digits[write] = (u8)digit
                write += 1
            elif digit > 0:
                self.truncated = true
            n = n * 10
        self.count = write
        self.trim()

    ## The integer part, rounded to nearest, ties to even (a truncated tail breaks a tie up).
    func rounded_integer() -> u64:
        if self.point > 20:
            return 0xFFFFFFFFFFFFFFFF
        var n: u64 = 0
        var at: i64 = 0
        while at < self.point and at < (i64)self.count:
            n = n * 10 + (u64)self.digits[(usize)at]
            at += 1
        while at < self.point:
            n *= 10
            at += 1
        if self.rounds_up(self.point):
            n += 1
        return n

    func rounds_up(at: i64) -> bool:
        if at < 0 or at >= (i64)self.count:
            return false
        let digit = self.digits[(usize)at]
        if digit == 5 and at + 1 == (i64)self.count:
            # exactly half, unless digits were dropped past the capacity
            if self.truncated:
                return true
            return at > 0 and self.digits[(usize)(at - 1)] % 2 == 1
        return digit >= 5

    func trim():
        while self.count > 0 and self.digits[self.count - 1] == 0:
            self.count -= 1
        if self.count == 0:
            self.point = 0

# mark: Formatting =============================================================================

## The shortest decimal text that parse_f64 reads back as `value`, the closest to it of
## those, as double-conversion's ToShortest lays it out: decimal notation for a decimal
## exponent from -6 to 14 (`0.000001`, `123456789012345`, `1.5`), otherwise one digit, the
## rest after a point, and `e` with the exponent (`1e-7`, `1.2345e15`, `5e-324`); `-0`,
## `inf`, `-inf`, `nan` (no sign, no payload). Written into `buffer` (32 bytes always
## suffice), and a view of it; io.full when it does not fit, the buffer unchanged. Neither
## allocates, locale or rounding mode (float_text).
pub func format_f64(value: f64, buffer: u8[]) -> str!:
    var text: u8[32] = ---
    let length = float_text.write_f64(value, text[0..])
    return try deliver(text[..<length], buffer)

## The f32 counterpart of format_f64: the f32's own shortest digits (`0.1` for 0.1f32, not
## the digits of its f64 value).
pub func format_f32(value: f32, buffer: u8[]) -> str!:
    var text: u8[32] = ---
    let length = float_text.write_f32(value, text[0..])
    return try deliver(text[..<length], buffer)

func deliver(text: const u8[], buffer: u8[]) -> str!:
    if buffer.length < text.length:
        error(io.full, "the destination cannot hold the formatted floating-point value")
    memory.copy(buffer, text, text.length)
    return (str)buffer[..<text.length]