///|
/// A signed 128-bit integer, stored as a high signed 64-bit word and a low
/// unsigned 64-bit word in two's complement form.
///
/// Temporal needs 128-bit arithmetic: epoch nanoseconds span
/// `±8.64e21`, and normalized time durations reach
/// `±9.007199254740991999999999e24`, both well beyond `Int64`.
///
/// Arithmetic wraps on overflow, matching the machine-integer semantics of the
/// Rust `i128` this port mirrors. Use the `checked_*` variants where overflow
/// must be detected.
pub struct Int128 {
  hi : Int64
  lo : UInt64
} derive(Eq, Hash, Default)

///|
/// The value `0`.
pub let zero : Int128 = { hi: 0, lo: 0 }

///|
/// The value `1`.
pub let one : Int128 = { hi: 0, lo: 1 }

///|
/// The largest representable value, `2^127 - 1`.
pub let max_value : Int128 = {
  hi: 0x7fff_ffff_ffff_ffffL,
  lo: 0xffff_ffff_ffff_ffffUL,
}

///|
/// The smallest representable value, `-2^127`.
pub let min_value : Int128 = { hi: 0x8000_0000_0000_0000L, lo: 0UL }

///|
/// Builds an `Int128` from its raw high and low words.
pub fn Int128::from_words(hi : Int64, lo : UInt64) -> Int128 {
  { hi, lo }
}

///|
/// Returns the high (most significant, signed) 64-bit word.
pub fn Int128::high(self : Int128) -> Int64 {
  self.hi
}

///|
/// Returns the low (least significant, unsigned) 64-bit word.
pub fn Int128::low(self : Int128) -> UInt64 {
  self.lo
}

///|
/// Sign-extends an `Int64`.
///
/// ```mbt check
/// test {
///   inspect(@int128.of_int64(-5L), content="-5")
/// }
/// ```
pub fn of_int64(v : Int64) -> Int128 {
  { hi: v >> 63, lo: v.reinterpret_as_uint64() }
}

///|
/// Sign-extends an `Int`.
pub fn of_int(v : Int) -> Int128 {
  of_int64(v.to_int64())
}

///|
/// Zero-extends a `UInt64`.
pub fn of_uint64(v : UInt64) -> Int128 {
  { hi: 0, lo: v }
}

///|
/// Returns whether the value is zero.
pub fn Int128::is_zero(self : Int128) -> Bool {
  self.hi == 0L && self.lo == 0UL
}

///|
/// Returns whether the value is strictly negative.
pub fn Int128::is_negative(self : Int128) -> Bool {
  self.hi < 0L
}

///|
/// Returns `-1`, `0`, or `1` according to the sign of the value.
pub fn Int128::signum(self : Int128) -> Int {
  if self.is_zero() {
    0
  } else if self.is_negative() {
    -1
  } else {
    1
  }
}

///|
/// Bitwise complement.
pub fn Int128::lnot(self : Int128) -> Int128 {
  { hi: self.hi.lnot(), lo: self.lo.lnot() }
}

///|
/// Two's-complement negation. `min_value` negates to itself.
pub fn Int128::neg(self : Int128) -> Int128 {
  self.lnot().add(one)
}

///|
/// Absolute value. `min_value` maps to itself, mirroring `i128::wrapping_abs`.
pub fn Int128::abs(self : Int128) -> Int128 {
  if self.is_negative() {
    self.neg()
  } else {
    self
  }
}

///|
/// Wrapping addition.
pub fn Int128::add(self : Int128, other : Int128) -> Int128 {
  let lo = self.lo + other.lo
  // Unsigned wraparound in the low word means a carry into the high word.
  let carry : Int64 = if lo < self.lo { 1L } else { 0L }
  { hi: self.hi + other.hi + carry, lo }
}

///|
/// Wrapping subtraction.
pub fn Int128::sub(self : Int128, other : Int128) -> Int128 {
  let lo = self.lo - other.lo
  let borrow : Int64 = if self.lo < other.lo { 1L } else { 0L }
  { hi: self.hi - other.hi - borrow, lo }
}

///|
/// Wrapping multiplication.
pub fn Int128::mul(self : Int128, other : Int128) -> Int128 {
  let lo = self.lo * other.lo
  let cross = self.hi.reinterpret_as_uint64() * other.lo +
    self.lo * other.hi.reinterpret_as_uint64()
  let hi = umulhi(self.lo, other.lo) + cross
  { hi: hi.reinterpret_as_int64(), lo }
}

///|
/// The high 64 bits of the 128-bit product of two `UInt64` values.
fn umulhi(a : UInt64, b : UInt64) -> UInt64 {
  let mask : UInt64 = 0xffff_ffffUL
  let (a_lo, a_hi) = (a & mask, a >> 32)
  let (b_lo, b_hi) = (b & mask, b >> 32)
  let ll = a_lo * b_lo
  let lh = a_lo * b_hi
  let hl = a_hi * b_lo
  let hh = a_hi * b_hi
  // Accumulate the middle terms, keeping the carry out of bit 63.
  let mid = (ll >> 32) + (lh & mask) + (hl & mask)
  hh + (lh >> 32) + (hl >> 32) + (mid >> 32)
}

///|
/// Logical left shift by `n` bits, where `n` is taken modulo 128.
pub fn Int128::shl(self : Int128, n : Int) -> Int128 {
  let n = n % 128
  if n == 0 {
    self
  } else if n < 64 {
    {
      hi: (self.lo >> (64 - n)).reinterpret_as_int64() + (self.hi << n),
      lo: self.lo << n,
    }
  } else {
    { hi: (self.lo << (n - 64)).reinterpret_as_int64(), lo: 0 }
  }
}

///|
/// Arithmetic (sign-propagating) right shift by `n` bits, `n` taken modulo 128.
pub fn Int128::shr(self : Int128, n : Int) -> Int128 {
  let n = n % 128
  if n == 0 {
    self
  } else if n < 64 {
    {
      hi: self.hi >> n,
      lo: (self.lo >> n) | (self.hi << (64 - n)).reinterpret_as_uint64(),
    }
  } else {
    { hi: self.hi >> 63, lo: (self.hi >> (n - 64)).reinterpret_as_uint64() }
  }
}

///|
/// Bitwise and.
pub fn Int128::land(self : Int128, other : Int128) -> Int128 {
  { hi: self.hi & other.hi, lo: self.lo & other.lo }
}

///|
/// Bitwise or.
pub fn Int128::lor(self : Int128, other : Int128) -> Int128 {
  { hi: self.hi | other.hi, lo: self.lo | other.lo }
}

///|
/// Signed three-way comparison.
pub impl Compare for Int128 with fn compare(self, other) {
  let c = self.hi.compare(other.hi)
  if c != 0 {
    c
  } else {
    self.lo.compare(other.lo)
  }
}

///|
/// Unsigned three-way comparison of the raw 128-bit patterns.
fn ucompare(a : Int128, b : Int128) -> Int {
  let c = a.hi.reinterpret_as_uint64().compare(b.hi.reinterpret_as_uint64())
  if c != 0 {
    c
  } else {
    a.lo.compare(b.lo)
  }
}

///|
/// Index of the most significant set bit, or `-1` when the value is zero.
fn ubit_length(v : Int128) -> Int {
  if v.hi != 0L {
    127 - v.hi.reinterpret_as_uint64().clz()
  } else if v.lo != 0UL {
    63 - v.lo.clz()
  } else {
    -1
  }
}

///|
/// Unsigned division of the raw bit patterns, returning `(quotient, remainder)`.
///
/// Uses restoring shift-subtract long division, which needs no 128-bit
/// hardware support and is exact for every input.
fn udivmod(n : Int128, d : Int128) -> (Int128, Int128) {
  if ucompare(n, d) < 0 {
    return (zero, n)
  }
  let shift = ubit_length(n) - ubit_length(d)
  let mut rem = n
  let mut quot = zero
  for i = shift; i >= 0; i = i - 1 {
    let shifted = d.shl(i)
    if ucompare(shifted, rem) <= 0 {
      rem = rem.sub(shifted)
      quot = quot.lor(one.shl(i))
    }
  }
  (quot, rem)
}

///|
/// Returns the number of significant bits in the magnitude, or `0` for zero.
///
/// ```mbt check
/// test {
///   inspect(@int128.of_int(0).bit_length(), content="0")
///   inspect(@int128.of_int(1).bit_length(), content="1")
///   inspect(@int128.of_int(-255).bit_length(), content="8")
/// }
/// ```
pub fn Int128::bit_length(self : Int128) -> Int {
  ubit_length(self.abs()) + 1
}

///|
/// Truncating division and remainder, as Rust's `/` and `%` on `i128`.
///
/// The remainder takes the sign of the dividend.
///
/// # Panics
/// Panics when `other` is zero.
pub fn Int128::div_rem(self : Int128, other : Int128) -> (Int128, Int128) {
  if other.is_zero() {
    abort("Int128: division by zero")
  }
  let (n, n_neg) = (self.abs(), self.is_negative())
  let (d, d_neg) = (other.abs(), other.is_negative())
  let (q, r) = udivmod(n, d)
  let q = if n_neg != d_neg { q.neg() } else { q }
  let r = if n_neg { r.neg() } else { r }
  (q, r)
}

///|
/// Truncating division.
pub fn Int128::div(self : Int128, other : Int128) -> Int128 {
  self.div_rem(other).0
}

///|
/// Remainder of truncating division; takes the sign of the dividend.
pub fn Int128::rem(self : Int128, other : Int128) -> Int128 {
  self.div_rem(other).1
}

///|
/// Euclidean division and remainder, as Rust's `div_euclid` / `rem_euclid`.
///
/// The remainder is always non-negative. Temporal's spec text is written in
/// terms of `floor` and `modulo`, so this is the variant most of the port uses.
pub fn Int128::div_rem_euclid(
  self : Int128,
  other : Int128,
) -> (Int128, Int128) {
  let (q, r) = self.div_rem(other)
  if r.is_negative() {
    if other.is_negative() {
      (q.add(one), r.sub(other))
    } else {
      (q.sub(one), r.add(other))
    }
  } else {
    (q, r)
  }
}

///|
/// Euclidean division: rounds toward negative infinity for a positive divisor.
pub fn Int128::div_euclid(self : Int128, other : Int128) -> Int128 {
  self.div_rem_euclid(other).0
}

///|
/// Euclidean remainder; always in `0 ..< other.abs()`.
pub fn Int128::rem_euclid(self : Int128, other : Int128) -> Int128 {
  self.div_rem_euclid(other).1
}

///|
/// Addition that reports overflow instead of wrapping.
pub fn Int128::checked_add(self : Int128, other : Int128) -> Int128? {
  let result = self.add(other)
  // Overflow happened iff both operands share a sign that the result does not.
  if self.is_negative() == other.is_negative() &&
    result.is_negative() != self.is_negative() {
    None
  } else {
    Some(result)
  }
}

///|
/// Subtraction that reports overflow instead of wrapping.
pub fn Int128::checked_sub(self : Int128, other : Int128) -> Int128? {
  let result = self.sub(other)
  if self.is_negative() != other.is_negative() &&
    result.is_negative() != self.is_negative() {
    None
  } else {
    Some(result)
  }
}

///|
/// Multiplication that reports overflow instead of wrapping.
pub fn Int128::checked_mul(self : Int128, other : Int128) -> Int128? {
  if self.is_zero() || other.is_zero() {
    return Some(zero)
  }
  let neg_one = of_int(-1)
  // `-min_value` is not representable, so this pair always overflows and would
  // otherwise slip past the divide-back check below.
  if (self == min_value && other == neg_one) ||
    (other == min_value && self == neg_one) {
    return None
  }
  let result = self.mul(other)
  // Recover an operand by dividing back out; a mismatch means it wrapped.
  if result.div(other) == self {
    Some(result)
  } else {
    None
  }
}

///|
/// Converts to `Int64`, returning `None` when the value does not fit.
pub fn Int128::to_int64(self : Int128) -> Int64? {
  let lo = self.lo.reinterpret_as_int64()
  if self.hi == lo >> 63 {
    Some(lo)
  } else {
    None
  }
}

///|
/// Converts to `Int`, returning `None` when the value does not fit.
pub fn Int128::to_int(self : Int128) -> Int? {
  match self.to_int64() {
    Some(v) if v >= -2147483648L && v <= 2147483647L => Some(v.to_int())
    _ => None
  }
}

///|
/// Converts to `Int64`, saturating at the `Int64` bounds.
pub fn Int128::to_int64_saturating(self : Int128) -> Int64 {
  match self.to_int64() {
    Some(v) => v
    None => if self.is_negative() { @int64.MIN_VALUE } else { @int64.MAX_VALUE }
  }
}

///|
/// Converts to the nearest `Double`, rounding to nearest with ties to even.
///
/// Values beyond `2^53` cannot be represented exactly; the result is the
/// correctly rounded neighbour, matching Rust's `i128 as f64`.
pub fn Int128::to_double(self : Int128) -> Double {
  if self.is_negative() {
    -unsigned_to_double(self.neg())
  } else {
    unsigned_to_double(self)
  }
}

///|
/// Correctly rounded conversion of a non-negative value to `Double`.
fn unsigned_to_double(v : Int128) -> Double {
  let hi = v.hi.reinterpret_as_uint64()
  if hi == 0UL {
    // A single 64-bit word converts correctly in one step.
    return v.lo.to_double()
  }
  // Normalize so the top 64 bits of the value land in `top`, then fold
  // everything below into a sticky bit. `top` always has its most significant
  // bit set, so it carries 64 significant bits: 53 for the mantissa and 11
  // spare, which leaves bit 0 free to hold the sticky bit without disturbing
  // round-to-nearest-even.
  let s = hi.clz()
  let (top, rest) = if s == 0 {
    (hi, v.lo)
  } else {
    ((hi << s) | (v.lo >> (64 - s)), v.lo & ((1UL << (64 - s)) - 1UL))
  }
  let sticky = if rest == 0UL { 0UL } else { 1UL }
  let rounded = (top & 0xffff_ffff_ffff_fffeUL) | sticky
  // Scaling by a power of two is exact.
  rounded.to_double() * two_pow(64 - s)
}

///|
/// Returns `2^exp` for `0 <= exp <= 64`.
fn two_pow(exp : Int) -> Double {
  let mut result = 1.0
  for _ in 0.. Int128? {
  if value.is_nan() || value.is_inf() {
    return None
  }
  let truncated = value.trunc()
  if truncated >= 170141183460469231731687303715884105728.0 ||
    truncated < -170141183460469231731687303715884105728.0 {
    return None
  }
  let negative = truncated < 0.0
  let magnitude = truncated.abs()
  // Split at the word boundary; both halves are exact because a `Double` of
  // this size is already an integer.
  let hi_part = (magnitude / 18446744073709551616.0).trunc()
  let hi = UInt64::trunc_double(hi_part)
  let lo = UInt64::trunc_double(magnitude - hi_part * 18446744073709551616.0)
  let result : Int128 = { hi: hi.reinterpret_as_int64(), lo }
  Some(if negative { result.neg() } else { result })
}

///|
/// Debug rendering: the same decimal form as `Show`.
pub impl Debug for Int128 with fn to_repr(self) {
  Repr::integer(self.to_dec_string())
}

///|
/// Decimal rendering, matching Rust's `Display` for `i128`.
pub impl Show for Int128 with fn output(self, logger) {
  logger.write_string(self.to_dec_string())
}

///|
fn Int128::to_dec_string(self : Int128) -> String {
  if self.is_zero() {
    return "0"
  }
  if self == min_value {
    return "-170141183460469231731687303715884105728"
  }
  let negative = self.is_negative()
  let mut v = self.abs()
  // Chunk by 10^19, the largest power of ten a UInt64 chunk can hold, so the
  // inner formatting is plain 64-bit work.
  let chunk = of_uint64(10_000_000_000_000_000_000UL)
  let parts = []
  while !v.is_zero() {
    let (q, r) = udivmod(v, chunk)
    parts.push(r.lo)
    v = q
  }
  let buf = StringBuilder::new()
  if negative {
    buf.write_string("-")
  }
  for i = parts.length() - 1; i >= 0; i = i - 1 {
    let s = parts[i].to_string()
    if i == parts.length() - 1 {
      buf.write_string(s)
    } else {
      for _ in 0..<(19 - s.length()) {
        buf.write_string("0")
      }
      buf.write_string(s)
    }
  }
  buf.to_string()
}

///|
/// Parse failure for [`of_string`].
pub suberror ParseInt128Error {
  /// The input was empty, had a lone sign, or held a non-digit character.
  InvalidDigit
  /// The value does not fit in 128 bits.
  OutOfRange
} derive(Eq, Debug)

///|
/// Parses a decimal integer, with an optional leading `+` or `-`.
///
/// ```mbt check
/// test {
///   inspect(
///     @int128.of_string("-170141183460469231731687303715884105728"),
///     content="-170141183460469231731687303715884105728",
///   )
/// }
/// ```
pub fn of_string(s : String) -> Int128 raise ParseInt128Error {
  let view = s[:]
  let (negative, digits) = match view {
    ['-', .. rest] => (true, rest)
    ['+', .. rest] => (false, rest)
    _ => (false, view)
  }
  if digits.is_empty() {
    raise InvalidDigit
  }
  let ten = of_int(10)
  let mut acc = zero
  for c in digits {
    if c < '0' || c > '9' {
      raise InvalidDigit
    }
    let digit = of_int(c.to_int() - '0'.to_int())
    // Accumulate the magnitude negatively so that `min_value` is reachable.
    acc = match acc.checked_mul(ten) {
      Some(v) => v
      None => raise OutOfRange
    }
    acc = match acc.checked_sub(digit) {
      Some(v) => v
      None => raise OutOfRange
    }
  }
  if negative {
    acc
  } else if acc == min_value {
    // The magnitude is 2^127, which is only representable as a negative.
    raise OutOfRange
  } else {
    acc.neg()
  }
}

///|
/// Returns the larger of two values.
pub fn Int128::max(self : Int128, other : Int128) -> Int128 {
  if self.compare(other) >= 0 {
    self
  } else {
    other
  }
}

///|
/// Returns the smaller of two values.
pub fn Int128::min(self : Int128, other : Int128) -> Int128 {
  if self.compare(other) <= 0 {
    self
  } else {
    other
  }
}

///|
/// Clamps the value into `low ..= high`.
pub fn Int128::clamp(self : Int128, low : Int128, high : Int128) -> Int128 {
  self.max(low).min(high)
}