// FSE decoding tables (RFC 8878 section 4.1): reading a table description
// and building the table from its normalized distribution.

///|
/// An FSE decoding table of `1 << log` states, at most `1 << 9`. Each state
/// gives a symbol and how to reach the next state: `base` plus `nbits` bits.
/// The three are packed in one entry, `base | nbits << 16 | symbol << 24`,
/// so that a state costs one load.
priv struct Fse {
  entry : FixedArray[Int32]
  mut log : Int32
}

///|
fn Fse::new(max_log : Int32) -> Fse {
  { entry: FixedArray::make(1 << max_log, 0), log: 0, }
}

///|
/// The table's bytes.
fn Fse::memory_usage(self : Fse) -> Int32 {
  4 * self.entry.length()
}

///|
/// The table that always gives `symbol` and reads no bits (`RLE_Mode`).
fn Fse::set_rle(self : Fse, symbol : Byte) -> Unit {
  self.log = 0
  self.entry[0] = symbol.to_int() << 24
}

///|
/// The entry of `state`.
#inline
fn Fse::entry_of(self : Fse, state : Int32) -> Int32 {
  self.entry[state]
}

///|
/// The symbol of `state`.
fn Fse::symbol_of(self : Fse, state : Int32) -> Int32 {
  entry_symbol(self.entry[state])
}

///|
/// The state after `state`, reading its bits from `bits`.
fn Fse::next(self : Fse, state : Int32, bits : BackwardBits) -> Int32 {
  let e = self.entry[state]
  entry_base(e) + bits.read(entry_nbits(e))
}

///|
#inline
fn entry_symbol(e : Int32) -> Int32 {
  (e >> 24) & 0xFF
}

///|
#inline
fn entry_nbits(e : Int32) -> Int32 {
  (e >> 16) & 0xFF
}

///|
#inline
fn entry_base(e : Int32) -> Int32 {
  e & 0xFFFF
}

///|
/// Scratch for building tables: a distribution and the next state of each
/// symbol.
priv struct FseScratch {
  // The last description's normalized counts, `probs[0:count]`.
  mut count : Int32
  probs : FixedArray[Int32]
  next : FixedArray[Int32]
  symbols : FixedArray[Byte]
}

///|
fn FseScratch::new() -> FseScratch {
  {
    count: 0,
    probs: FixedArray::make(256, 0),
    next: FixedArray::make(256, 0),
    symbols: FixedArray::make(1 << 9, b'\x00'),
  }
}

///|
/// The scratch space's bytes.
fn FseScratch::memory_usage(self : FseScratch) -> Int32 {
  4 * (self.probs.length() + self.next.length()) + self.symbols.length()
}

///|
/// Builds `self` from `probs[0:count]`, a distribution summing to
/// `1 << log` in which -1 stands for "less than 1" (RFC 8878 section
/// 4.1.1). The symbols go on the states where `@fse.spread`, which the
/// encoder's tables share, puts them. False when the rows do not come out
/// exactly filled, which only a corrupt description can cause.
fn Fse::build(
  self : Fse,
  probs : FixedArray[Int32],
  count : Int32,
  log : Int32,
  scratch : FseScratch,
) -> Bool {
  let size = 1 << log
  self.log = log
  let symbols = scratch.symbols
  let next = scratch.next
  guard @fse.spread(probs, count, log, symbols) else { return false }
  // Each symbol's states, in order, decode the values from its probability
  // up to twice it, less one.
  for s in 0.. Int32 raise Stop {
  let bits = ForwardBits::new(data, start, end)
  let log = bits.read(4) + 5
  if log > max_log {
    raise corrupt("an FSE accuracy log above \{max_log}")
  }
  let probs = scratch.probs
  let mut remaining = 1 << log
  let mut count = 0
  while remaining > 0 {
    if count > max_symbol {
      raise corrupt("an FSE probability for a symbol out of range")
    }
    // Values 0..remaining + 1, in `width` bits or one fewer for the smaller
    // values.
    let width = 32 - (remaining + 1).clz()
    let low_mask = (1 << (width - 1)) - 1
    let threshold = (1 << width) - 1 - (remaining + 1)
    let mut value = bits.peek(width)
    if (value & low_mask) < threshold {
      value = value & low_mask
      bits.pos += width - 1
    } else {
      if value > low_mask {
        value -= threshold
      }
      bits.pos += width
    }
    if !bits.in_bounds() {
      raise corrupt("a table description runs past its section")
    }
    let prob = value - 1
    remaining -= if prob < 0 { 1 } else { prob }
    probs[count] = prob
    count += 1
    if prob == 0 {
      for ;; {
        let repeat = bits.read(2)
        if !bits.in_bounds() {
          raise corrupt("a table description runs past its section")
        }
        if count + repeat > max_symbol + 1 {
          raise corrupt("an FSE probability for a symbol out of range")
        }
        for _ in 0.. Fse {
  let table = Fse::new(log)
  table.build(probs, probs.length(), log, FseScratch::new()) |> ignore
  table
}

///|
/// The default tables of RFC 8878 section 3.1.1.3.2.2.
let ll_predefined : Fse = Fse::predefined(ll_default, 6)

///|
let ml_predefined : Fse = Fse::predefined(ml_default, 6)

///|
let of_predefined : Fse = Fse::predefined(of_default, 5)