dymokomi/luce-obj
Source of release 0.10.1
## Eisel-Lemire decimal-to-binary64 conversion (Lemire, "Number Parsing at a
## Gigabyte per Second", 2021; the form of Go's strconv): a u64 decimal
## mantissa times a 128-bit power of ten, rounded once. It declines (none) the
## rare inputs it cannot decide, subnormals, overflow and exponents beyond the
## table, which the caller then hands to strings.parse_f64.
import memory
## Decimal exponents the table covers; OBJ coordinates sit well inside.
let smallest_exponent: i64 = -64
let largest_exponent: i64 = 64
## 10^q for q in smallest_exponent..=largest_exponent as a 128-bit mantissa,
## rounded down and normalized so its top bit is set: high word, low word.
## Each is floor(5^q * 2^s) for q >= 0 and floor(2^s / 5^-q) for q < 0, with
## s chosen for exactly 128 bits (10^q and 5^q differ only in the exponent).
let powers: u64[258] = [
0xA87FEA27A539E9A5, 0x3F2398D747B36224,
0xD29FE4B18E88640E, 0x8EEC7F0D19A03AAD,
0x83A3EEEEF9153E89, 0x1953CF68300424AC,
0xA48CEAAAB75A8E2B, 0x5FA8C3423C052DD7,
0xCDB02555653131B6, 0x3792F412CB06794D,
0x808E17555F3EBF11, 0xE2BBD88BBEE40BD0,
0xA0B19D2AB70E6ED6, 0x5B6ACEAEAE9D0EC4,
0xC8DE047564D20A8B, 0xF245825A5A445275,
0xFB158592BE068D2E, 0xEED6E2F0F0D56712,
0x9CED737BB6C4183D, 0x55464DD69685606B,
0xC428D05AA4751E4C, 0xAA97E14C3C26B886,
0xF53304714D9265DF, 0xD53DD99F4B3066A8,
0x993FE2C6D07B7FAB, 0xE546A8038EFE4029,
0xBF8FDB78849A5F96, 0xDE98520472BDD033,
0xEF73D256A5C0F77C, 0x963E66858F6D4440,
0x95A8637627989AAD, 0xDDE7001379A44AA8,
0xBB127C53B17EC159, 0x5560C018580D5D52,
0xE9D71B689DDE71AF, 0xAAB8F01E6E10B4A6,
0x9226712162AB070D, 0xCAB3961304CA70E8,
0xB6B00D69BB55C8D1, 0x3D607B97C5FD0D22,
0xE45C10C42A2B3B05, 0x8CB89A7DB77C506A,
0x8EB98A7A9A5B04E3, 0x77F3608E92ADB242,
0xB267ED1940F1C61C, 0x55F038B237591ED3,
0xDF01E85F912E37A3, 0x6B6C46DEC52F6688,
0x8B61313BBABCE2C6, 0x2323AC4B3B3DA015,
0xAE397D8AA96C1B77, 0xABEC975E0A0D081A,
0xD9C7DCED53C72255, 0x96E7BD358C904A21,
0x881CEA14545C7575, 0x7E50D64177DA2E54,
0xAA242499697392D2, 0xDDE50BD1D5D0B9E9,
0xD4AD2DBFC3D07787, 0x955E4EC64B44E864,
0x84EC3C97DA624AB4, 0xBD5AF13BEF0B113E,
0xA6274BBDD0FADD61, 0xECB1AD8AEACDD58E,
0xCFB11EAD453994BA, 0x67DE18EDA5814AF2,
0x81CEB32C4B43FCF4, 0x80EACF948770CED7,
0xA2425FF75E14FC31, 0xA1258379A94D028D,
0xCAD2F7F5359A3B3E, 0x096EE45813A04330,
0xFD87B5F28300CA0D, 0x8BCA9D6E188853FC,
0x9E74D1B791E07E48, 0x775EA264CF55347D,
0xC612062576589DDA, 0x95364AFE032A819D,
0xF79687AED3EEC551, 0x3A83DDBD83F52204,
0x9ABE14CD44753B52, 0xC4926A9672793542,
0xC16D9A0095928A27, 0x75B7053C0F178293,
0xF1C90080BAF72CB1, 0x5324C68B12DD6338,
0x971DA05074DA7BEE, 0xD3F6FC16EBCA5E03,
0xBCE5086492111AEA, 0x88F4BB1CA6BCF584,
0xEC1E4A7DB69561A5, 0x2B31E9E3D06C32E5,
0x9392EE8E921D5D07, 0x3AFF322E62439FCF,
0xB877AA3236A4B449, 0x09BEFEB9FAD487C2,
0xE69594BEC44DE15B, 0x4C2EBE687989A9B3,
0x901D7CF73AB0ACD9, 0x0F9D37014BF60A10,
0xB424DC35095CD80F, 0x538484C19EF38C94,
0xE12E13424BB40E13, 0x2865A5F206B06FB9,
0x8CBCCC096F5088CB, 0xF93F87B7442E45D3,
0xAFEBFF0BCB24AAFE, 0xF78F69A51539D748,
0xDBE6FECEBDEDD5BE, 0xB573440E5A884D1B,
0x89705F4136B4A597, 0x31680A88F8953030,
0xABCC77118461CEFC, 0xFDC20D2B36BA7C3D,
0xD6BF94D5E57A42BC, 0x3D32907604691B4C,
0x8637BD05AF6C69B5, 0xA63F9A49C2C1B10F,
0xA7C5AC471B478423, 0x0FCF80DC33721D53,
0xD1B71758E219652B, 0xD3C36113404EA4A8,
0x83126E978D4FDF3B, 0x645A1CAC083126E9,
0xA3D70A3D70A3D70A, 0x3D70A3D70A3D70A3,
0xCCCCCCCCCCCCCCCC, 0xCCCCCCCCCCCCCCCC,
0x8000000000000000, 0x0000000000000000,
0xA000000000000000, 0x0000000000000000,
0xC800000000000000, 0x0000000000000000,
0xFA00000000000000, 0x0000000000000000,
0x9C40000000000000, 0x0000000000000000,
0xC350000000000000, 0x0000000000000000,
0xF424000000000000, 0x0000000000000000,
0x9896800000000000, 0x0000000000000000,
0xBEBC200000000000, 0x0000000000000000,
0xEE6B280000000000, 0x0000000000000000,
0x9502F90000000000, 0x0000000000000000,
0xBA43B74000000000, 0x0000000000000000,
0xE8D4A51000000000, 0x0000000000000000,
0x9184E72A00000000, 0x0000000000000000,
0xB5E620F480000000, 0x0000000000000000,
0xE35FA931A0000000, 0x0000000000000000,
0x8E1BC9BF04000000, 0x0000000000000000,
0xB1A2BC2EC5000000, 0x0000000000000000,
0xDE0B6B3A76400000, 0x0000000000000000,
0x8AC7230489E80000, 0x0000000000000000,
0xAD78EBC5AC620000, 0x0000000000000000,
0xD8D726B7177A8000, 0x0000000000000000,
0x878678326EAC9000, 0x0000000000000000,
0xA968163F0A57B400, 0x0000000000000000,
0xD3C21BCECCEDA100, 0x0000000000000000,
0x84595161401484A0, 0x0000000000000000,
0xA56FA5B99019A5C8, 0x0000000000000000,
0xCECB8F27F4200F3A, 0x0000000000000000,
0x813F3978F8940984, 0x4000000000000000,
0xA18F07D736B90BE5, 0x5000000000000000,
0xC9F2C9CD04674EDE, 0xA400000000000000,
0xFC6F7C4045812296, 0x4D00000000000000,
0x9DC5ADA82B70B59D, 0xF020000000000000,
0xC5371912364CE305, 0x6C28000000000000,
0xF684DF56C3E01BC6, 0xC732000000000000,
0x9A130B963A6C115C, 0x3C7F400000000000,
0xC097CE7BC90715B3, 0x4B9F100000000000,
0xF0BDC21ABB48DB20, 0x1E86D40000000000,
0x96769950B50D88F4, 0x1314448000000000,
0xBC143FA4E250EB31, 0x17D955A000000000,
0xEB194F8E1AE525FD, 0x5DCFAB0800000000,
0x92EFD1B8D0CF37BE, 0x5AA1CAE500000000,
0xB7ABC627050305AD, 0xF14A3D9E40000000,
0xE596B7B0C643C719, 0x6D9CCD05D0000000,
0x8F7E32CE7BEA5C6F, 0xE4820023A2000000,
0xB35DBF821AE4F38B, 0xDDA2802C8A800000,
0xE0352F62A19E306E, 0xD50B2037AD200000,
0x8C213D9DA502DE45, 0x4526F422CC340000,
0xAF298D050E4395D6, 0x9670B12B7F410000,
0xDAF3F04651D47B4C, 0x3C0CDD765F114000,
0x88D8762BF324CD0F, 0xA5880A69FB6AC800,
0xAB0E93B6EFEE0053, 0x8EEA0D047A457A00,
0xD5D238A4ABE98068, 0x72A4904598D6D880,
0x85A36366EB71F041, 0x47A6DA2B7F864750,
0xA70C3C40A64E6C51, 0x999090B65F67D924,
0xD0CF4B50CFE20765, 0xFFF4B4E3F741CF6D,
0x82818F1281ED449F, 0xBFF8F10E7A8921A4,
0xA321F2D7226895C7, 0xAFF72D52192B6A0D,
0xCBEA6F8CEB02BB39, 0x9BF4F8A69F764490,
0xFEE50B7025C36A08, 0x02F236D04753D5B4,
0x9F4F2726179A2245, 0x01D762422C946590,
0xC722F0EF9D80AAD6, 0x424D3AD2B7B97EF5,
0xF8EBAD2B84E0D58B, 0xD2E0898765A7DEB2,
0x9B934C3B330C8577, 0x63CC55F49F88EB2F,
0xC2781F49FFCFA6D5, 0x3CBF6B71C76B25FB
]
## `mantissa * 10^exponent`, correctly rounded, or none when undecided.
pub func convert(mantissa: u64, exponent: i64, negative: bool) -> f64?:
if exponent < smallest_exponent or exponent > largest_exponent:
return none
let zeros = leading_zeros(mantissa)
let man = mantissa << zeros
# floor(log2(10^exponent)) + 64 + the bias, less the normalization; positive
# over the table's range.
var binary = (u64)(((217706 * exponent) >> 16) + 64 + 1023 - (i64)zeros)
let row = (usize)(exponent - smallest_exponent) * 2
var low: u64 = 0
var high = product(man, 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 = product(man, 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 full 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 memory.read[f64](&bits)
## The 128-bit product a * b: the high word, with the low word stored in `low`.
inline func product(a: u64, b: u64, low: u64*) -> u64:
let a0 = a & 0xFFFFFFFF
let a1 = a >> 32
let b0 = b & 0xFFFFFFFF
let b1 = b >> 32
let p00 = a0 * b0
let p01 = a0 * b1
let p10 = a1 * b0
let p11 = a1 * b1
let middle = (p00 >> 32) + (p01 & 0xFFFFFFFF) + (p10 & 0xFFFFFFFF)
*low = (middle << 32) | (p00 & 0xFFFFFFFF)
return p11 + (p01 >> 32) + (p10 >> 32) + (middle >> 32)
## 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