dymokomi/luce-base
Source of release 0.45.0
0.45.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]