///|
/// Quantised gradient pairs, one per row: (g << 32) + h. Sums over all rows
/// keep h inside 32 bits, so the packed sums never carry between halves.
type QArr = FixedArray[Int64]

///|
/// Histogram slots of packed quantised sums.
type Hist = FixedArray[Int64]

///|
/// Two-byte bins.
type U16s = FixedArray[UInt16]

///|
fn u16s_make(n : Int32) -> U16s {
  FixedArray::make(n, 0)
}

///|
/// Row numbers and positions.
type I32s = FixedArray[Int32]

///|
fn i32s_make(n : Int32) -> I32s {
  FixedArray::make(n, 0)
}

///|
/// Exact gradient pairs, g at 2r and h at 2r + 1.
type F32s = FixedArray[Float]

///|
fn f32s_make(n : Int32) -> F32s {
  FixedArray::make(n, 0.0)
}

///|
/// Whether bins may be packed eight to a 64-bit word.
let narrow_bins : Bool = true

///|
/// One-byte bins, eight to a 64-bit word.
type Words = FixedArray[UInt64]

///|
let word_bins : Int32 = 8

///|
fn words_make(n : Int32) -> Words {
  FixedArray::make(n, 0UL)
}

///|
/// The byte of a word at bit `shift`.
fn word_byte(x : UInt64, shift : Int32) -> Int32 {
  ((x >> shift) & 255UL).to_int()
}

///|
/// A word with byte `b` set at bit `shift` (which was zero).
fn word_put(x : UInt64, b : Byte, shift : Int32) -> UInt64 {
  x | (b.to_int().to_uint64() << shift)
}

///|
fn qarr_make(n : Int32) -> QArr {
  FixedArray::make(n, 0L)
}

///|
fn q_copy(dst : QArr, p : Int32, src : QArr, r : Int32) -> Unit {
  dst.unsafe_set(p, src.unsafe_get(r))
}

///|
fn hist_len(hist : Hist) -> Int32 {
  hist.length()
}

///|
/// The quantised gradient sum of a slot, as an integer-valued Double.
fn hist_g(hist : Hist, slot : Int32) -> Double {
  let q = hist.unsafe_get(slot)
  ((q - (q & 0xFFFFFFFFL)) >> 32).to_double()
}

///|
/// The quantised hessian sum of a slot.
fn hist_h(hist : Hist, slot : Int32) -> Double {
  (hist.unsafe_get(slot) & 0xFFFFFFFFL).to_double()
}

///|
/// hist -= small, slot by slot.
fn hist_sub(hist : Hist, small : Hist) -> Unit {
  for i in 0.. Int64 = "%f64_to_i64"

///|
/// Quantises a gradient pair, rounding half away from zero (h is never
/// negative), and packs it as (g << 32) + h.
fn Grower::pack_at(
  self : Grower,
  qa : QArr,
  r : Int32,
  g : Double,
  h : Double,
) -> Unit {
  let x = g * self.gs
  // 0.5 with the sign of x, from its bits: the sign of a gradient is
  // unpredictable, so a branch on it would often be mispredicted
  let half = ((x.reinterpret_as_int64() & (1L << 63)) | 0x3FE0000000000000L).reinterpret_as_double()
  let gi = trunc64(x + half)
  qa.unsafe_set(r, (gi << 32) + trunc64(h * self.hs + 0.5))
}

///|
/// exp to about 1e-9 relative error, ample for gradients that are rounded
/// to float32: x = k ln2 + r with |r| <= ln2 / 2, a degree-7 polynomial for
/// e^r, and 2^k built from its exponent bits. x is clamped to +-80, where
/// the losses are saturated.
fn train_exp(x : Double) -> Double {
  let x = if x > 80.0 { 80.0 } else if x < -80.0 { -80.0 } else { x }
  // k = round(x / ln2) by the 1.5 * 2^52 trick, without a branch or a
  // checked conversion
  let kd = x * 1.4426950408889634 + 6755399441055744.0
  let ki = kd.reinterpret_as_int64() - 0x4338000000000000L
  let kf = kd - 6755399441055744.0
  let r = x - kf * 0.6931471803691238 - kf * 1.9082149292705877e-10
  // Estrin's scheme: a shorter dependency chain than Horner's
  let r2 = r * r
  let r4 = r2 * r2
  let p = 1.0 +
    r +
    r2 * (0.5 + r * (1.0 / 6.0)) +
    r4 *
    (1.0 / 24.0 + r * (1.0 / 120.0) + r2 * (1.0 / 720.0 + r * (1.0 / 5040.0)))
  p * ((ki + 1023L) << 52).reinterpret_as_double()
}

///|
/// Gradient and hessian sums per bin for rows[lo:hi], for a node at
/// `depth` (unused here: each histogram is a fresh allocation).
fn Grower::histogram(
  self : Grower,
  lo : Int32,
  hi : Int32,
  level : Int32,
  depth : Int32,
) -> Hist {
  ignore(depth)
  let rows = self.rows
  if self.narrow {
    let hist = FixedArray::make(self.nbins + 8, 0L)
    let (cb, cq) = if level > 0 {
      (self.cbins[level - 1], self.cq[level - 1])
    } else {
      (self.bins8, self.gq)
    }
    let wb = self.wbase
    let words = self.words
    if words == 1 {
      // the slot bases in locals: hist stores could alias wbase for the C
      // compiler, which would reload it for every byte
      let b0 = wb[0]
      let b1 = wb[1]
      let b2 = wb[2]
      let b3 = wb[3]
      let b4 = wb[4]
      let b5 = wb[5]
      let b6 = wb[6]
      let b7 = wb[7]
      for i in lo..> 8) & 255UL).to_int() + b1
        let s2 = ((x >> 16) & 255UL).to_int() + b2
        let s3 = ((x >> 24) & 255UL).to_int() + b3
        let s4 = ((x >> 32) & 255UL).to_int() + b4
        let s5 = ((x >> 40) & 255UL).to_int() + b5
        let s6 = ((x >> 48) & 255UL).to_int() + b6
        let s7 = (x >> 56).to_int() + b7
        hist.unsafe_set(s0, hist.unsafe_get(s0) + q)
        hist.unsafe_set(s1, hist.unsafe_get(s1) + q)
        hist.unsafe_set(s2, hist.unsafe_get(s2) + q)
        hist.unsafe_set(s3, hist.unsafe_get(s3) + q)
        hist.unsafe_set(s4, hist.unsafe_get(s4) + q)
        hist.unsafe_set(s5, hist.unsafe_get(s5) + q)
        hist.unsafe_set(s6, hist.unsafe_get(s6) + q)
        hist.unsafe_set(s7, hist.unsafe_get(s7) + q)
      }
      return hist
    }
    for i in lo..> 8) & 255UL).to_int() + wb.unsafe_get(o + 1)
        let s2 = ((x >> 16) & 255UL).to_int() + wb.unsafe_get(o + 2)
        let s3 = ((x >> 24) & 255UL).to_int() + wb.unsafe_get(o + 3)
        hist.unsafe_set(s0, hist.unsafe_get(s0) + q)
        hist.unsafe_set(s1, hist.unsafe_get(s1) + q)
        hist.unsafe_set(s2, hist.unsafe_get(s2) + q)
        hist.unsafe_set(s3, hist.unsafe_get(s3) + q)
        let s4 = ((x >> 32) & 255UL).to_int() + wb.unsafe_get(o + 4)
        let s5 = ((x >> 40) & 255UL).to_int() + wb.unsafe_get(o + 5)
        let s6 = ((x >> 48) & 255UL).to_int() + wb.unsafe_get(o + 6)
        let s7 = (x >> 56).to_int() + wb.unsafe_get(o + 7)
        hist.unsafe_set(s4, hist.unsafe_get(s4) + q)
        hist.unsafe_set(s5, hist.unsafe_get(s5) + q)
        hist.unsafe_set(s6, hist.unsafe_get(s6) + q)
        hist.unsafe_set(s7, hist.unsafe_get(s7) + q)
      }
    }
    return hist
  }
  let hist = FixedArray::make(self.nbins, 0L)
  let cols = self.data.cols
  let bins = if level > 0 { self.cbins16[level - 1] } else { self.data.bins }
  let gq = if level > 0 { self.cq[level - 1] } else { self.gq }
  // indices are in range by construction: rows hold row numbers and bins
  // hold histogram slots
  for i in lo..