// Number scanning for LightGBM model text.
//
// LightGBM writes doubles with up to 17 significant digits. This scans one
// token straight into a decimal mantissa and exponent, then converts with
// Clinger's exact fast path or the Eisel-Lemire algorithm, and hands anything
// it cannot certify to `@string.parse_double`, so every result is the
// correctly rounded double.
//
// The 128-bit powers of ten below are the slice 10^-64..10^40 of the table
// in moonbitlang/core (internal/strconv, generated from Go's
// internal/strconv/pow10tab.go), Apache-2.0.

///|
const LGB_POW10_MIN : Int32 = -64

///|
const LGB_POW10_MAX : Int32 = 40

///|
let lgb_pow10 : FixedArray[UInt64] = [
  0xa87fea27a539e9a5UL, 0x3f2398d747b36224UL, 0xd29fe4b18e88640eUL, 0x8eec7f0d19a03aadUL,
  0x83a3eeeef9153e89UL, 0x1953cf68300424acUL, 0xa48ceaaab75a8e2bUL, 0x5fa8c3423c052dd7UL,
  0xcdb02555653131b6UL, 0x3792f412cb06794dUL, 0x808e17555f3ebf11UL, 0xe2bbd88bbee40bd0UL,
  0xa0b19d2ab70e6ed6UL, 0x5b6aceaeae9d0ec4UL, 0xc8de047564d20a8bUL, 0xf245825a5a445275UL,
  0xfb158592be068d2eUL, 0xeed6e2f0f0d56712UL, 0x9ced737bb6c4183dUL, 0x55464dd69685606bUL,
  0xc428d05aa4751e4cUL, 0xaa97e14c3c26b886UL, 0xf53304714d9265dfUL, 0xd53dd99f4b3066a8UL,
  0x993fe2c6d07b7fabUL, 0xe546a8038efe4029UL, 0xbf8fdb78849a5f96UL, 0xde98520472bdd033UL,
  0xef73d256a5c0f77cUL, 0x963e66858f6d4440UL, 0x95a8637627989aadUL, 0xdde7001379a44aa8UL,
  0xbb127c53b17ec159UL, 0x5560c018580d5d52UL, 0xe9d71b689dde71afUL, 0xaab8f01e6e10b4a6UL,
  0x9226712162ab070dUL, 0xcab3961304ca70e8UL, 0xb6b00d69bb55c8d1UL, 0x3d607b97c5fd0d22UL,
  0xe45c10c42a2b3b05UL, 0x8cb89a7db77c506aUL, 0x8eb98a7a9a5b04e3UL, 0x77f3608e92adb242UL,
  0xb267ed1940f1c61cUL, 0x55f038b237591ed3UL, 0xdf01e85f912e37a3UL, 0x6b6c46dec52f6688UL,
  0x8b61313bbabce2c6UL, 0x2323ac4b3b3da015UL, 0xae397d8aa96c1b77UL, 0xabec975e0a0d081aUL,
  0xd9c7dced53c72255UL, 0x96e7bd358c904a21UL, 0x881cea14545c7575UL, 0x7e50d64177da2e54UL,
  0xaa242499697392d2UL, 0xdde50bd1d5d0b9e9UL, 0xd4ad2dbfc3d07787UL, 0x955e4ec64b44e864UL,
  0x84ec3c97da624ab4UL, 0xbd5af13bef0b113eUL, 0xa6274bbdd0fadd61UL, 0xecb1ad8aeacdd58eUL,
  0xcfb11ead453994baUL, 0x67de18eda5814af2UL, 0x81ceb32c4b43fcf4UL, 0x80eacf948770ced7UL,
  0xa2425ff75e14fc31UL, 0xa1258379a94d028dUL, 0xcad2f7f5359a3b3eUL, 0x096ee45813a04330UL,
  0xfd87b5f28300ca0dUL, 0x8bca9d6e188853fcUL, 0x9e74d1b791e07e48UL, 0x775ea264cf55347dUL,
  0xc612062576589ddaUL, 0x95364afe032a819dUL, 0xf79687aed3eec551UL, 0x3a83ddbd83f52204UL,
  0x9abe14cd44753b52UL, 0xc4926a9672793542UL, 0xc16d9a0095928a27UL, 0x75b7053c0f178293UL,
  0xf1c90080baf72cb1UL, 0x5324c68b12dd6338UL, 0x971da05074da7beeUL, 0xd3f6fc16ebca5e03UL,
  0xbce5086492111aeaUL, 0x88f4bb1ca6bcf584UL, 0xec1e4a7db69561a5UL, 0x2b31e9e3d06c32e5UL,
  0x9392ee8e921d5d07UL, 0x3aff322e62439fcfUL, 0xb877aa3236a4b449UL, 0x09befeb9fad487c2UL,
  0xe69594bec44de15bUL, 0x4c2ebe687989a9b3UL, 0x901d7cf73ab0acd9UL, 0x0f9d37014bf60a10UL,
  0xb424dc35095cd80fUL, 0x538484c19ef38c94UL, 0xe12e13424bb40e13UL, 0x2865a5f206b06fb9UL,
  0x8cbccc096f5088cbUL, 0xf93f87b7442e45d3UL, 0xafebff0bcb24aafeUL, 0xf78f69a51539d748UL,
  0xdbe6fecebdedd5beUL, 0xb573440e5a884d1bUL, 0x89705f4136b4a597UL, 0x31680a88f8953030UL,
  0xabcc77118461cefcUL, 0xfdc20d2b36ba7c3dUL, 0xd6bf94d5e57a42bcUL, 0x3d32907604691b4cUL,
  0x8637bd05af6c69b5UL, 0xa63f9a49c2c1b10fUL, 0xa7c5ac471b478423UL, 0x0fcf80dc33721d53UL,
  0xd1b71758e219652bUL, 0xd3c36113404ea4a8UL, 0x83126e978d4fdf3bUL, 0x645a1cac083126e9UL,
  0xa3d70a3d70a3d70aUL, 0x3d70a3d70a3d70a3UL, 0xccccccccccccccccUL, 0xccccccccccccccccUL,
  0x8000000000000000UL, 0x0000000000000000UL, 0xa000000000000000UL, 0x0000000000000000UL,
  0xc800000000000000UL, 0x0000000000000000UL, 0xfa00000000000000UL, 0x0000000000000000UL,
  0x9c40000000000000UL, 0x0000000000000000UL, 0xc350000000000000UL, 0x0000000000000000UL,
  0xf424000000000000UL, 0x0000000000000000UL, 0x9896800000000000UL, 0x0000000000000000UL,
  0xbebc200000000000UL, 0x0000000000000000UL, 0xee6b280000000000UL, 0x0000000000000000UL,
  0x9502f90000000000UL, 0x0000000000000000UL, 0xba43b74000000000UL, 0x0000000000000000UL,
  0xe8d4a51000000000UL, 0x0000000000000000UL, 0x9184e72a00000000UL, 0x0000000000000000UL,
  0xb5e620f480000000UL, 0x0000000000000000UL, 0xe35fa931a0000000UL, 0x0000000000000000UL,
  0x8e1bc9bf04000000UL, 0x0000000000000000UL, 0xb1a2bc2ec5000000UL, 0x0000000000000000UL,
  0xde0b6b3a76400000UL, 0x0000000000000000UL, 0x8ac7230489e80000UL, 0x0000000000000000UL,
  0xad78ebc5ac620000UL, 0x0000000000000000UL, 0xd8d726b7177a8000UL, 0x0000000000000000UL,
  0x878678326eac9000UL, 0x0000000000000000UL, 0xa968163f0a57b400UL, 0x0000000000000000UL,
  0xd3c21bcecceda100UL, 0x0000000000000000UL, 0x84595161401484a0UL, 0x0000000000000000UL,
  0xa56fa5b99019a5c8UL, 0x0000000000000000UL, 0xcecb8f27f4200f3aUL, 0x0000000000000000UL,
  0x813f3978f8940984UL, 0x4000000000000000UL, 0xa18f07d736b90be5UL, 0x5000000000000000UL,
  0xc9f2c9cd04674edeUL, 0xa400000000000000UL, 0xfc6f7c4045812296UL, 0x4d00000000000000UL,
  0x9dc5ada82b70b59dUL, 0xf020000000000000UL, 0xc5371912364ce305UL, 0x6c28000000000000UL,
  0xf684df56c3e01bc6UL, 0xc732000000000000UL, 0x9a130b963a6c115cUL, 0x3c7f400000000000UL,
  0xc097ce7bc90715b3UL, 0x4b9f100000000000UL, 0xf0bdc21abb48db20UL, 0x1e86d40000000000UL,
  0x96769950b50d88f4UL, 0x1314448000000000UL, 0xbc143fa4e250eb31UL, 0x17d955a000000000UL,
  0xeb194f8e1ae525fdUL, 0x5dcfab0800000000UL,
]

///|
let lgb_exact_pow10 : FixedArray[Double] = [
  1.0e0, 1.0e1, 1.0e2, 1.0e3, 1.0e4, 1.0e5, 1.0e6, 1.0e7, 1.0e8, 1.0e9, 1.0e10, 1.0e11,
  1.0e12, 1.0e13, 1.0e14, 1.0e15, 1.0e16, 1.0e17, 1.0e18, 1.0e19, 1.0e20, 1.0e21,
  1.0e22,
]

///|
fn lgb_umul128_hi(a : UInt64, b : UInt64) -> UInt64 {
  let a_lo = a & 0xffffffffUL
  let a_hi = a >> 32
  let b_lo = b & 0xffffffffUL
  let b_hi = b >> 32
  let x = a_lo * b_lo
  let y = a_hi * b_lo + (x >> 32)
  let z = a_lo * b_hi + (y & 0xffffffffUL)
  a_hi * b_hi + (y >> 32) + (z >> 32)
}

///|
/// Eisel-Lemire for `mantissa * 10^exponent`; NaN when it cannot certify the
/// rounding (the caller then falls back to the exact parser).
fn lgb_eisel_lemire(
  mantissa : UInt64,
  exponent : Int32,
  negative : Bool,
) -> Double {
  let nan = 0x7FF8000000000000UL.reinterpret_as_double()
  if exponent < LGB_POW10_MIN || exponent > LGB_POW10_MAX {
    return nan
  }
  let ix = (exponent - LGB_POW10_MIN) * 2
  let pow_hi = lgb_pow10[ix]
  let pow_lo = lgb_pow10[ix + 1]
  let pow_exp2 = 1 + ((exponent * 108853) >> 15)
  let lz = mantissa.clz()
  let normalized = mantissa << lz
  let mut result_exp2 = pow_exp2 + 63 + 1023 - lz
  let mut product_hi = lgb_umul128_hi(normalized, pow_hi)
  let mut product_lo = normalized * pow_hi
  if (product_hi & 0x1ffUL) == 0x1ffUL && product_lo + normalized < normalized {
    let wider_hi = lgb_umul128_hi(normalized, pow_lo)
    let wider_lo = normalized * pow_lo
    let mut merged_hi = product_hi
    let merged_lo = product_lo + wider_hi
    if merged_lo < product_lo {
      merged_hi += 1UL
    }
    if (merged_hi & 0x1ffUL) == 0x1ffUL &&
      merged_lo + 1UL == 0UL &&
      wider_lo + normalized < normalized {
      return nan
    }
    product_hi = merged_hi
    product_lo = merged_lo
  }
  let top_bit = (product_hi >> 63).to_int()
  let mut result_mantissa = product_hi >> (top_bit + 9)
  result_exp2 -= 1 - top_bit
  if product_lo == 0UL &&
    (product_hi & 0x1ffUL) == 0UL &&
    (result_mantissa & 3UL) == 1UL {
    return nan
  }
  result_mantissa += result_mantissa & 1UL
  result_mantissa = result_mantissa >> 1
  if result_mantissa >> 53 > 0UL {
    result_mantissa = result_mantissa >> 1
    result_exp2 += 1
  }
  if result_exp2 <= 0 || result_exp2 >= 0x7ff {
    return nan
  }
  let mut bits = (result_exp2.to_uint64() << 52) |
    (result_mantissa & 0x000fffffffffffffUL)
  if negative {
    bits = bits | 0x8000000000000000UL
  }
  bits.reinterpret_as_double()
}

///|
/// Parses one token `s[start:end]` as a double, correctly rounded.
fn lgb_parse_double(s : StringView, start : Int32, end : Int32) -> Double raise {
  let mut i = start
  let negative = i < end && s.unsafe_get(i) == '-'
  if negative || (i < end && s.unsafe_get(i) == '+') {
    i += 1
  }
  let mut mantissa = 0UL
  let mut sig = 0 // significant digits taken into `mantissa`
  let mut exp = 0
  let mut any = false
  while i < end {
    let c = s.unsafe_get(i).to_int() - 48
    if c < 0 || c > 9 {
      break
    }
    any = true
    if sig > 0 || c != 0 {
      mantissa = mantissa * 10UL + c.to_uint64()
      sig += 1
    }
    i += 1
  }
  if i < end && s.unsafe_get(i) == '.' {
    i += 1
    while i < end {
      let c = s.unsafe_get(i).to_int() - 48
      if c < 0 || c > 9 {
        break
      }
      any = true
      if sig > 0 || c != 0 {
        mantissa = mantissa * 10UL + c.to_uint64()
        sig += 1
      }
      exp -= 1
      i += 1
    }
  }
  if i < end && (s.unsafe_get(i) == 'e' || s.unsafe_get(i) == 'E') && any {
    i += 1
    let eneg = i < end && s.unsafe_get(i) == '-'
    if eneg || (i < end && s.unsafe_get(i) == '+') {
      i += 1
    }
    let mut e = 0
    let mut edigits = 0
    while i < end && edigits < 6 {
      let c = s.unsafe_get(i).to_int() - 48
      if c < 0 || c > 9 {
        break
      }
      e = e * 10 + c
      edigits += 1
      i += 1
    }
    if edigits == 0 {
      i = -1 // malformed: let the general parser report it
    }
    exp += if eneg { -e } else { e }
  }
  if i == end && any && sig <= 19 {
    if mantissa == 0UL {
      return if negative { -0.0 } else { 0.0 }
    }
    if mantissa <= 0x20000000000000UL && exp >= -22 && exp <= 22 {
      let m = mantissa.to_double()
      let v = if exp >= 0 {
        m * lgb_exact_pow10[exp]
      } else {
        m / lgb_exact_pow10[-exp]
      }
      return if negative { -v } else { v }
    }
    let v = lgb_eisel_lemire(mantissa, exp, negative)
    if !v.is_nan() {
      return v
    }
  }
  @string.parse_double(s.unsafe_view(start~, end~))
}