// Port of jxl-coding/src/lib.rs
//
// This package provides [Decoder], an entropy decoder, implemented as
// specified in the JPEG XL specification.
//
// This also provides [read_permutation] and [read_clusters], which are used in
// some parts of the specification.

///|
/// An entropy decoder.
///
/// Integer types: contexts and clusters are `Int`; decoded values are `UInt`
/// (Rust `u32`), so they can be passed to `@bitstream.unpack_signed`.
struct Decoder {
  lz77 : Lz77
  inner : DecoderInner
}

///|
/// Create a decoder by reading symbol distribution, integer configurations and
/// LZ77 configuration from the bitstream.
pub fn Decoder::parse(
  bitstream : @bitstream.Bitstream,
  num_dist : Int32,
) -> Decoder raise @bitstream.JxlError {
  let lz77 = Lz77::parse(bitstream)
  let num_dist = if lz77 is Disabled { num_dist } else { num_dist + 1 }
  let inner = DecoderInner::parse(bitstream, num_dist)
  { lz77, inner, }
}

///|
fn Decoder::parse_assume_no_lz77(
  bitstream : @bitstream.Bitstream,
  num_dist : Int32,
) -> Decoder raise @bitstream.JxlError {
  let lz77_enabled = bitstream.read_bool()
  if lz77_enabled {
    raise coding_error("Lz77NotAllowed")
  }
  let inner = DecoderInner::parse(bitstream, num_dist)
  { lz77: Disabled, inner, }
}

///|
/// An independent copy of the decoder (Rust `Clone`): distributions are
/// shared, the ANS state and the LZ77 window are copied.
pub fn Decoder::clone(self : Decoder) -> Decoder {
  { lz77: self.lz77.clone(), inner: self.inner.clone(), }
}

///|
/// Read an integer from the bitstream with the given context.
#inline
pub fn Decoder::read_varint(
  self : Decoder,
  bitstream : @bitstream.Bitstream,
  ctx : Int32,
) -> UInt32 raise @bitstream.JxlError {
  self.read_varint_with_multiplier(bitstream, ctx, 0)
}

///|
/// Read an integer from the bitstream with the given context and LZ77 distance
/// multiplier.
#inline
pub fn Decoder::read_varint_with_multiplier(
  self : Decoder,
  bitstream : @bitstream.Bitstream,
  ctx : Int32,
  dist_multiplier : Int32,
) -> UInt32 raise @bitstream.JxlError {
  let cluster = self.inner.clusters[ctx]
  self.read_varint_with_multiplier_clustered(
    bitstream, cluster, dist_multiplier,
  )
}

///|
/// Read an integer from the bitstream with the given *cluster* and LZ77
/// distance multiplier.
///
/// Contexts can be converted to clusters using [the cluster map][Decoder::cluster_map].
#inline
pub fn Decoder::read_varint_with_multiplier_clustered(
  self : Decoder,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
  dist_multiplier : Int32,
) -> UInt32 raise @bitstream.JxlError {
  match self.lz77 {
    Enabled(min_symbol~, min_length~, state~) =>
      self.inner.read_varint_with_multiplier_clustered_lz77(
        bitstream, cluster, dist_multiplier, state, min_symbol, min_length,
      )
    Disabled =>
      self.inner.read_varint_with_multiplier_clustered(bitstream, cluster)
  }
}

///|
/// Converts the decoder to one in RLE mode.
pub fn Decoder::as_rle(self : Decoder) -> DecoderRleMode? {
  guard self.lz77 is Enabled(state~, min_symbol~, min_length~) else {
    return None
  }
  let lz_cluster = self.inner.lz_dist_cluster()
  let lz_conf = self.inner.configs[lz_cluster]
  let sym = self.inner.code.single_symbol(lz_cluster)
  if sym < 0 {
    return None
  }
  if sym == 1 && lz_conf.split_exponent == 0 {
    Some({
      inner: self.inner,
      min_symbol,
      min_length,
      len_config: state.lz_len_conf,
    })
  } else {
    None
  }
}

///|
/// Converts the decoder to LZ77-enabled one.
pub fn Decoder::as_with_lz77(self : Decoder) -> DecoderWithLz77? {
  match self.lz77 {
    Enabled(state~, min_symbol~, min_length~) =>
      Some({ inner: self.inner, state, min_symbol, min_length, })
    Disabled => None
  }
}

///|
/// Converts the decoder to one without LZ77.
pub fn Decoder::as_no_lz77(self : Decoder) -> DecoderNoLz77? {
  match self.lz77 {
    Disabled => Some({ inner: self.inner, })
    Enabled(..) => None
  }
}

///|
/// Returns the token to be decoded if the decoder always emits single token
/// repeatedly.
#inline
pub fn Decoder::single_token(self : Decoder, cluster : Int32) -> UInt32? {
  if self.lz77 is Enabled(..) {
    return None
  }
  self.inner.single_token(cluster)
}

///|
/// Explicitly start reading an entropy encoded stream.
///
/// This involves reading an initial state for the ANS stream. It's okay to skip
/// this method, as the state will be initialized on the first read.
pub fn Decoder::begin(
  self : Decoder,
  bitstream : @bitstream.Bitstream,
) -> Unit raise @bitstream.JxlError {
  self.inner.code.begin(bitstream)
}

///|
/// Finalizes the stream, and check whether the stream was valid.
///
/// For prefix code stream, this method will always succeed. For ANS streams,
/// this method checks if the final state matches expected state, which is
/// specified in the specification.
pub fn Decoder::finalize(self : Decoder) -> Unit raise @bitstream.JxlError {
  self.inner.code.finalize()
}

///|
/// Returns the cluster mapping of distributions (context -> cluster). Do not
/// modify the returned array.
#inline
pub fn Decoder::cluster_map(self : Decoder) -> FixedArray[Int32] {
  self.inner.clusters
}

///|
/// An entropy decoder in RLE mode. It shares the state of the [Decoder] it
/// was created from.
struct DecoderRleMode {
  inner : DecoderInner
  min_symbol : Int32
  min_length : Int32
  len_config : IntegerConfig
}

///|
/// Decoded token from an entropy decoder in RLE mode.
#derive(Eq, Debug)
pub(all) enum RleToken {
  /// Emit the given value once.
  Value(UInt32)
  /// Repeat previously decoded value by the given number of times.
  Repeat(UInt32)
}

///|
/// Read an integer from the bitstream with the given *cluster*.
///
/// Contexts can be converted to clusters using [the cluster map][DecoderRleMode::cluster_map].
pub fn DecoderRleMode::read_varint_clustered(
  self : DecoderRleMode,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
) -> RleToken raise @bitstream.JxlError {
  let packed = self.read_varint_clustered_packed(bitstream, cluster)
  if packed < 0L {
    Repeat((-1L - packed).to_uint())
  } else {
    Value(packed.to_uint())
  }
}

///|
/// Allocation-free variant of [DecoderRleMode::read_varint_clustered]:
/// returns `v` (>= 0) for `Value(v)` and `-1 - n` (< 0) for `Repeat(n)`.
#inline
pub fn DecoderRleMode::read_varint_clustered_packed(
  self : DecoderRleMode,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
) -> Int64 raise @bitstream.JxlError {
  let token = self.inner.code.read_symbol(bitstream, cluster)
  if token >= self.min_symbol {
    let n = self.inner.read_uint_prefilled(
        bitstream,
        self.len_config,
        token - self.min_symbol,
      ) +
      self.min_length.reinterpret_as_uint()
    -1L - n.to_uint64().reinterpret_as_int64()
  } else {
    self.inner
    .read_uint_prefilled(bitstream, self.inner.configs[cluster], token)
    .to_uint64()
    .reinterpret_as_int64()
  }
}

///|
/// Returns the cluster mapping of distributions.
pub fn DecoderRleMode::cluster_map(self : DecoderRleMode) -> FixedArray[Int32] {
  self.inner.clusters
}

///|
/// A LZ77-enabled entropy decoder. It shares the state of the [Decoder] it was
/// created from.
struct DecoderWithLz77 {
  inner : DecoderInner
  state : Lz77State
  min_symbol : Int32
  min_length : Int32
}

///|
/// Read an integer from the bitstream with the given *cluster* and LZ77
/// distance multiplier.
#inline
pub fn DecoderWithLz77::read_varint_with_multiplier_clustered(
  self : DecoderWithLz77,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
  dist_multiplier : Int32,
) -> UInt32 raise @bitstream.JxlError {
  self.inner.read_varint_with_multiplier_clustered_lz77(
    bitstream,
    cluster,
    dist_multiplier,
    self.state,
    self.min_symbol,
    self.min_length,
  )
}

///|
/// Returns the cluster mapping of distributions.
pub fn DecoderWithLz77::cluster_map(
  self : DecoderWithLz77,
) -> FixedArray[Int32] {
  self.inner.clusters
}

///|
/// An entropy decoder without LZ77. It shares the state of the [Decoder] it
/// was created from.
struct DecoderNoLz77 {
  inner : DecoderInner
}

///|
/// Read an integer from the bitstream with the given *cluster*.
#inline
pub fn DecoderNoLz77::read_varint_clustered(
  self : DecoderNoLz77,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
) -> UInt32 raise @bitstream.JxlError {
  self.inner.read_varint_with_multiplier_clustered(bitstream, cluster)
}

///|
/// Returns the token to be decoded if the decoder always emits single token
/// repeatedly.
#inline
pub fn DecoderNoLz77::single_token(
  self : DecoderNoLz77,
  cluster : Int32,
) -> UInt32? {
  self.inner.single_token(cluster)
}

///|
/// Returns the cluster mapping of distributions.
pub fn DecoderNoLz77::cluster_map(self : DecoderNoLz77) -> FixedArray[Int32] {
  self.inner.clusters
}

///|
priv enum Lz77 {
  Disabled
  Enabled(min_symbol~ : Int32, min_length~ : Int32, state~ : Lz77State)
}

///|
fn Lz77::parse(
  bitstream : @bitstream.Bitstream,
) -> Lz77 raise @bitstream.JxlError {
  if bitstream.read_bool() {
    // enabled
    let min_symbol = bitstream
      .read_u32(
        @bitstream.c(224),
        @bitstream.c(512),
        @bitstream.c(4096),
        @bitstream.cu(8, 15),
      )
      .reinterpret_as_int()
    let min_length = bitstream
      .read_u32(
        @bitstream.c(3),
        @bitstream.c(4),
        @bitstream.cu(5, 2),
        @bitstream.cu(9, 8),
      )
      .reinterpret_as_int()
    let lz_len_conf = IntegerConfig::parse(bitstream, 8)
    Enabled(min_symbol~, min_length~, state=Lz77State::new(lz_len_conf))
  } else {
    Disabled
  }
}

///|
fn Lz77::clone(self : Lz77) -> Lz77 {
  match self {
    Disabled => Disabled
    Enabled(min_symbol~, min_length~, state~) =>
      Enabled(min_symbol~, min_length~, state=state.clone())
  }
}

///|
priv struct Lz77State {
  lz_len_conf : IntegerConfig
  window : Array[UInt32]
  mut num_to_copy : UInt32
  mut copy_pos : UInt32
  mut num_decoded : UInt32
}

///|
fn Lz77State::new(lz_len_conf : IntegerConfig) -> Lz77State {
  { lz_len_conf, window: [], num_to_copy: 0, copy_pos: 0, num_decoded: 0, }
}

///|
fn Lz77State::clone(self : Lz77State) -> Lz77State {
  {
    lz_len_conf: self.lz_len_conf,
    window: self.window.copy(),
    num_to_copy: self.num_to_copy,
    copy_pos: self.copy_pos,
    num_decoded: self.num_decoded,
  }
}

///|
/// Hybrid integer configuration.
priv struct IntegerConfig {
  split_exponent : Int32
  split : Int32
  msb_in_token : Int32
  lsb_in_token : Int32
}

///|
fn IntegerConfig::parse(
  bitstream : @bitstream.Bitstream,
  log_alphabet_size : Int32,
) -> IntegerConfig raise @bitstream.JxlError {
  let split_exponent_bits = add_log2_ceil(
    log_alphabet_size.reinterpret_as_uint(),
  )
  let split_exponent = bitstream.read_bits_int(split_exponent_bits)
  let mut msb_in_token = 0
  let mut lsb_in_token = 0
  if split_exponent != log_alphabet_size {
    let msb_bits = add_log2_ceil(split_exponent.reinterpret_as_uint())
    msb_in_token = bitstream.read_bits_int(msb_bits)
    if msb_in_token > split_exponent {
      raise coding_error("InvalidIntegerConfig")
    }
    let lsb_bits = add_log2_ceil(
      (split_exponent - msb_in_token).reinterpret_as_uint(),
    )
    lsb_in_token = bitstream.read_bits_int(lsb_bits)
  }
  if lsb_in_token + msb_in_token > split_exponent {
    raise coding_error("InvalidIntegerConfig")
  }
  { split_exponent, split: 1 << split_exponent, msb_in_token, lsb_in_token, }
}

///|
priv struct DecoderInner {
  /// num_dist, [0, num_clusters)
  clusters : FixedArray[Int32]
  /// num_clusters
  configs : FixedArray[IntegerConfig]
  code : Coder
}

///|
fn DecoderInner::clone(self : DecoderInner) -> DecoderInner {
  { clusters: self.clusters, configs: self.configs, code: self.code.clone(), }
}

///|
fn DecoderInner::parse(
  bitstream : @bitstream.Bitstream,
  num_dist : Int32,
) -> DecoderInner raise @bitstream.JxlError {
  let (num_clusters, clusters) = read_clusters(bitstream, num_dist)
  let use_prefix_code = bitstream.read_bool()
  let log_alphabet_size = if use_prefix_code {
    15
  } else {
    bitstream.read_bits_int(2) + 5
  }
  let configs_arr : Array[IntegerConfig] = Array(capacity=num_clusters)
  for _ in 0.. 1 << 15 {
        raise coding_error("InvalidPrefixHistogram")
      }
      counts[i] = count
    }
    let dist : Array[PrefixHistogram] = Array(capacity=num_clusters)
    for count in counts {
      dist.push(PrefixHistogram::parse(bitstream, count))
    }
    PrefixCode(FixedArray::from_array(dist))
  } else {
    let dist : Array[AnsHistogram] = Array(capacity=num_clusters)
    for _ in 0.. UInt32? {
  let single_symbol = self.code.single_symbol(cluster)
  if single_symbol >= 0 && single_symbol < self.configs[cluster].split {
    Some(single_symbol.reinterpret_as_uint())
  } else {
    None
  }
}

///|
#inline
fn DecoderInner::read_varint_with_multiplier_clustered(
  self : DecoderInner,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
) -> UInt32 raise @bitstream.JxlError {
  let token = self.code.read_symbol(bitstream, cluster)
  self.read_uint_prefilled(bitstream, self.configs[cluster], token)
}

///|
/// `SPECIAL_DISTANCES: [[i8; 2]; 120]`, flattened.
let special_distances : FixedArray[Int32] = [
  0, 1, 1, 0, 1, 1, -1, 1, 0, 2, 2, 0, 1, 2, -1, 2, 2, 1, -2, 1, 2, 2, -2, 2, 0,
  3, 3, 0, 1, 3, -1, 3, 3, 1, -3, 1, 2, 3, -2, 3, 3, 2, -3, 2, 0, 4, 4, 0, 1, 4,
  -1, 4, 4, 1, -4, 1, 3, 3, -3, 3, 2, 4, -2, 4, 4, 2, -4, 2, 0, 5, 3, 4, -3, 4, 4,
  3, -4, 3, 5, 0, 1, 5, -1, 5, 5, 1, -5, 1, 2, 5, -2, 5, 5, 2, -5, 2, 4, 4, -4, 4,
  3, 5, -3, 5, 5, 3, -5, 3, 0, 6, 6, 0, 1, 6, -1, 6, 6, 1, -6, 1, 2, 6, -2, 6, 6,
  2, -6, 2, 4, 5, -4, 5, 5, 4, -5, 4, 3, 6, -3, 6, 6, 3, -6, 3, 0, 7, 7, 0, 1, 7,
  -1, 7, 5, 5, -5, 5, 7, 1, -7, 1, 4, 6, -4, 6, 6, 4, -6, 4, 2, 7, -2, 7, 7, 2, -7,
  2, 3, 7, -3, 7, 7, 3, -7, 3, 5, 6, -5, 6, 6, 5, -6, 5, 8, 0, 4, 7, -4, 7, 7, 4,
  -7, 4, 8, 1, 8, 2, 6, 6, -6, 6, 8, 3, 5, 7, -5, 7, 7, 5, -7, 5, 8, 4, 6, 7, -6,
  7, 7, 6, -7, 6, 8, 5, 7, 7, -7, 7, 8, 6, 8, 7,
]

///|
fn DecoderInner::read_varint_with_multiplier_clustered_lz77(
  self : DecoderInner,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
  dist_multiplier : Int32,
  state : Lz77State,
  min_symbol : Int32,
  min_length : Int32,
) -> UInt32 raise @bitstream.JxlError {
  let r = if state.num_to_copy > 0 {
    let r = state.window[(state.copy_pos & 0xfffff).reinterpret_as_int()]
    state.copy_pos += 1
    state.num_to_copy -= 1
    r
  } else {
    let token = self.code.read_symbol(bitstream, cluster)
    if token >= min_symbol {
      if state.num_decoded == 0 {
        // LZ77 repeat symbol encountered without decoding any symbols
        raise coding_error("UnexpectedLz77Repeat")
      }
      let lz_dist_cluster = self.lz_dist_cluster()
      let num_to_copy = self.read_uint_prefilled(
        bitstream,
        state.lz_len_conf,
        token - min_symbol,
      )
      let sum = num_to_copy + min_length.reinterpret_as_uint()
      if sum < num_to_copy {
        // LZ77 num_to_copy overflow
        raise coding_error("InvalidLz77Symbol")
      }
      state.num_to_copy = sum
      let token = self.code.read_symbol(bitstream, lz_dist_cluster)
      let distance = self.read_uint_prefilled(
        bitstream,
        self.configs[lz_dist_cluster],
        token,
      )
      let distance : UInt32 = if dist_multiplier == 0 {
        distance
      } else if distance < 120 {
        let d = distance.reinterpret_as_int()
        let offset = special_distances[2 * d]
        let dist = special_distances[2 * d + 1]
        let dist = offset + dist_multiplier * dist
        let dist = dist - 1
        (if dist < 0 { 0 } else { dist }).reinterpret_as_uint()
      } else {
        distance - 120
      }
      let distance = if distance < 0xfffff { distance } else { 0xfffff }
      let distance = distance + 1
      let distance = if distance < state.num_decoded {
        distance
      } else {
        state.num_decoded
      }
      state.copy_pos = state.num_decoded - distance
      let r = state.window[(state.copy_pos & 0xfffff).reinterpret_as_int()]
      state.copy_pos += 1
      state.num_to_copy -= 1
      r
    } else {
      self.read_uint_prefilled(bitstream, self.configs[cluster], token)
    }
  }
  let offset = (state.num_decoded & 0xfffff).reinterpret_as_int()
  if state.window.length() <= offset {
    state.window.push(r)
  } else {
    state.window[offset] = r
  }
  state.num_decoded += 1
  r
}

///|
/// Decodes the rest of a hybrid integer whose token was just read; the bit
/// buffer has been refilled by the symbol read.
#inline
fn DecoderInner::read_uint_prefilled(
  self : DecoderInner,
  bitstream : @bitstream.Bitstream,
  config : IntegerConfig,
  token : Int32,
) -> UInt32 {
  ignore(self)
  if token < config.split {
    return token.reinterpret_as_uint()
  }
  let msb_in_token = config.msb_in_token
  let lsb_in_token = config.lsb_in_token
  let ml = msb_in_token + lsb_in_token
  let n = config.split_exponent - ml + ((token - config.split) >> ml)
  // n < 32.
  let n = n & 31
  let rest_bits = bitstream.peek_bits_prefilled(n)
  bitstream.consume_bits(n) catch {
    _ => ()
  }
  let low_bits = (token & ((1 << lsb_in_token) - 1)).reinterpret_as_uint()
  let token = token >> lsb_in_token
  let token = token & ((1 << msb_in_token) - 1)
  let token = (token | (1 << msb_in_token)).reinterpret_as_uint()
  // The result fits in u32 (computed as u64 upstream, then truncated).
  (((token << n) | rest_bits) << lsb_in_token) | low_bits
}

///|
#inline
fn DecoderInner::lz_dist_cluster(self : DecoderInner) -> Int32 {
  self.clusters[self.clusters.length() - 1]
}

///|
priv enum Coder {
  PrefixCode(FixedArray[PrefixHistogram])
  Ans(AnsCoder)
}

///|
priv struct AnsCoder {
  dist : FixedArray[AnsHistogram]
  mut state : UInt32
  mut initial : Bool
}

///|
fn Coder::clone(self : Coder) -> Coder {
  match self {
    PrefixCode(_) => self
    Ans(a) => Ans({ dist: a.dist, state: a.state, initial: a.initial, })
  }
}

///|
#inline
fn Coder::read_symbol(
  self : Coder,
  bitstream : @bitstream.Bitstream,
  cluster : Int32,
) -> Int32 raise @bitstream.JxlError {
  match self {
    PrefixCode(dist) => dist[cluster].read_symbol(bitstream)
    Ans(a) => {
      if a.initial {
        a.state = bitstream.read_bits(32)
        a.initial = false
      }
      a.read_symbol_from(a.dist[cluster], bitstream)
    }
  }
}

///|
/// The single symbol of the cluster, or -1.
fn Coder::single_symbol(self : Coder, cluster : Int32) -> Int32 {
  match self {
    PrefixCode(dist) => dist[cluster].single_symbol()
    Ans(a) => a.dist[cluster].single_symbol
  }
}

///|
fn Coder::begin(
  self : Coder,
  bitstream : @bitstream.Bitstream,
) -> Unit raise @bitstream.JxlError {
  match self {
    PrefixCode(_) => ()
    Ans(a) => {
      a.state = bitstream.read_bits(32)
      a.initial = false
    }
  }
}

///|
fn Coder::finalize(self : Coder) -> Unit raise @bitstream.JxlError {
  match self {
    PrefixCode(_) => ()
    Ans(a) => if a.state != 0x130000 { raise coding_error("InvalidAnsStream") }
  }
}

///|
/// `(x + 1).next_power_of_two().trailing_zeros()`, i.e. the bit length of x.
fn add_log2_ceil(x : UInt32) -> Int32 {
  if x >= 0x80000000 {
    32
  } else {
    32 - x.clz()
  }
}

///|
/// Read a distribution clustering from the bitstream.
///
/// Returns `(num_clusters, cluster map)`.
pub fn read_clusters(
  bitstream : @bitstream.Bitstream,
  num_dist : Int32,
) -> (Int32, FixedArray[Int32]) raise @bitstream.JxlError {
  if num_dist == 1 {
    return (1, [0])
  }
  let cluster = FixedArray::make(num_dist, 0)
  if bitstream.read_bool() {
    // simple dist
    let nbits = bitstream.read_bits_int(2)
    for i in 0.. 255 {
        raise coding_error("InvalidCluster")
      }
      cluster[i] = b.reinterpret_as_int()
    }
    decoder.finalize()
    if use_mtf {
      let mtfmap = FixedArray::makei(256, i => i)
      for i in 0.. 0; j = j - 1 {
          mtfmap[j] = mtfmap[j - 1]
        }
        mtfmap[0] = v
      }
    }
  }
  let mut max = 0
  let seen = FixedArray::make(256, false)
  let mut num_actual_clusters = 0
  for c in cluster {
    if c > max {
      max = c
    }
    if !seen[c] {
      seen[c] = true
      num_actual_clusters += 1
    }
  }
  let num_clusters = max + 1
  if num_actual_clusters != num_clusters {
    // distribution cluster has a hole
    raise coding_error("ClusterHole")
  }
  (num_clusters, cluster)
}