// Port of jxl-coding/src/ans.rs

///|
/// An ANS distribution of one cluster (`ans::Histogram`), stored as an alias
/// table.
///
/// Ported from libjxl. log_alphabet_size <= 8 and log_bucket_size <= 7, so 8
/// bits are sufficient for symbols and cutoffs. alias_dist_xor allows
/// branchless dist computation for alias symbol.
///
/// Each bucket is packed into a `UInt64` with the same layout as the Rust
/// `#[repr(C)] struct Bucket` read as a little-endian `u64`:
/// `alias_symbol | alias_cutoff << 8 | dist << 16 | alias_offset << 32 | alias_dist_xor << 48`.
priv struct AnsHistogram {
  buckets : FixedArray[UInt64]
  log_bucket_size : Int32
  bucket_mask : UInt32
  /// The single symbol, or -1 (`None`).
  single_symbol : Int32
}

///|
fn pack_bucket(
  alias_symbol : Int32,
  alias_cutoff : Int32,
  dist : Int32,
  alias_offset : Int32,
  alias_dist_xor : Int32,
) -> UInt64 {
  (alias_symbol & 0xff).to_uint64() |
  ((alias_cutoff & 0xff).to_uint64() << 8) |
  ((dist & 0xffff).to_uint64() << 16) |
  ((alias_offset & 0xffff).to_uint64() << 32) |
  ((alias_dist_xor & 0xffff).to_uint64() << 48)
}

///|
/// log_alphabet_size: 5 + u(2)
fn AnsHistogram::parse(
  bitstream : @bitstream.Bitstream,
  log_alphabet_size : Int32,
) -> AnsHistogram raise @bitstream.JxlError {
  let table_size = 1 << log_alphabet_size
  // 4 <= log_bucket_size <= 7
  let log_bucket_size = 12 - log_alphabet_size
  let bucket_size = 1 << log_bucket_size
  let mut alphabet_size = 0
  let dist = FixedArray::make(table_size, 0)
  if bitstream.read_bool() {
    if bitstream.read_bool() {
      // binary
      let v0 = ans_read_u8(bitstream)
      let v1 = ans_read_u8(bitstream)
      if v0 == v1 {
        raise coding_error("InvalidAnsHistogram")
      }
      alphabet_size = (if v0 > v1 { v0 } else { v1 }) + 1
      if alphabet_size > table_size {
        raise coding_error("InvalidAnsHistogram")
      }
      let prob = bitstream.read_bits_int(12)
      dist[v0] = prob
      dist[v1] = (1 << 12) - prob
    } else {
      // unary
      let val = ans_read_u8(bitstream)
      alphabet_size = val + 1
      if alphabet_size > table_size {
        raise coding_error("InvalidAnsHistogram")
      }
      dist[val] = 1 << 12
    }
  } else if bitstream.read_bool() {
    // evenly distributed
    alphabet_size = ans_read_u8(bitstream) + 1
    if alphabet_size > table_size {
      raise coding_error("InvalidAnsHistogram")
    }
    let base = (1 << 12) / alphabet_size
    let leftover = (1 << 12) % alphabet_size
    for i in 0.. 13 {
      raise coding_error("InvalidAnsHistogram")
    }
    alphabet_size = ans_read_u8(bitstream) + 3
    if alphabet_size > table_size {
      raise coding_error("InvalidAnsHistogram")
    }
    // (start, end) pairs
    let repeat_ranges : Array[Int32] = []
    let mut omit_log = 0
    let mut omit_pos = -1
    let mut idx = 0
    while idx < alphabet_size {
      dist[idx] = ans_read_prefix(bitstream)
      if dist[idx] == 13 {
        let repeat_count = ans_read_u8(bitstream) + 4
        if idx + repeat_count > alphabet_size {
          raise coding_error("InvalidAnsHistogram")
        }
        repeat_ranges.push(idx)
        repeat_ranges.push(idx + repeat_count)
        idx += repeat_count
        continue
      }
      if omit_pos >= 0 {
        if dist[idx] > omit_log {
          omit_log = dist[idx]
          omit_pos = idx
        }
      } else {
        omit_log = dist[idx]
        omit_pos = idx
      }
      idx += 1
    }
    if omit_pos < 0 {
      raise coding_error("InvalidAnsHistogram")
    }
    if omit_pos + 1 < table_size && dist[omit_pos + 1] == 13 {
      raise coding_error("InvalidAnsHistogram")
    }
    let num_ranges = repeat_ranges.length() / 2
    let mut repeat_range_idx = 0
    let mut acc = 0
    let mut prev_dist = 0
    for idx in 0.. 1 << 12 {
            raise coding_error("InvalidAnsHistogram")
          }
          continue
        }
      }
      let code = dist[idx]
      if code == 0 {
        prev_dist = 0
        continue
      }
      if idx == omit_pos {
        prev_dist = 0
        continue
      }
      let code = if code > 1 {
        let zeros = code - 1
        let mut bitcount = shift - ((12 - zeros) >> 1)
        if bitcount < 0 {
          bitcount = 0
        }
        if bitcount > zeros {
          bitcount = zeros
        }
        let v = (1 << zeros) +
          (bitstream.read_bits_int(bitcount) << (zeros - bitcount))
        v & 0xffff
      } else {
        code
      }
      dist[idx] = code
      prev_dist = code
      acc += code
      if acc > 1 << 12 {
        raise coding_error("InvalidAnsHistogram")
      }
    }
    dist[omit_pos] = (1 << 12) - acc
  }
  let mut single_sym_idx = -1
  for i in 0..= 0 {
    let buckets = FixedArray::make(table_size, 0UL)
    for i in 0.. bucket_size {
      overfull.push(idx)
    }
  }
  while true {
    // Mirrors `while let (Some(o), Some(u)) = (overfull.pop(), underfull.pop())`
    let o = overfull.pop()
    let u = underfull.pop()
    guard o is Some(o) && u is Some(u) else { break }
    let by = bucket_size - alias_cutoff[u]
    alias_cutoff[o] = (alias_cutoff[o] - by) & 0xffff
    alias_symbol[u] = o
    alias_offset[u] = alias_cutoff[o]
    let c = alias_cutoff[o]
    if c < bucket_size {
      underfull.push(o)
    } else if c > bucket_size {
      overfull.push(o)
    }
  }
  let buckets = FixedArray::make(table_size, 0UL)
  for idx in 0.. Int32 raise @bitstream.JxlError {
  if bitstream.read_bool() {
    let n = bitstream.read_bits_int(3)
    ((1 << n) + bitstream.read_bits_int(n)) & 0xff
  } else {
    0
  }
}

///|
/// Reads a symbol, updating the ANS `state`. Returns the symbol.
/// (`ans::Histogram::read_symbol`; the state lives in [AnsCoder].)
fn AnsCoder::read_symbol_from(
  self : AnsCoder,
  hist : AnsHistogram,
  bitstream : @bitstream.Bitstream,
) -> Int32 raise @bitstream.JxlError {
  let state = self.state
  let idx = state & 0xfff
  let i = (idx >> hist.log_bucket_size).reinterpret_as_int()
  let pos = idx & hist.bucket_mask
  let bucket = hist.buckets[i]
  let alias_symbol = (bucket & 0xff).to_int()
  let alias_cutoff = ((bucket >> 8) & 0xff).to_uint()
  let dist = ((bucket >> 16) & 0xffff).to_uint()
  let map_to_alias = pos >= alias_cutoff
  let cond_bucket = if map_to_alias { bucket } else { 0 }
  let offset = (cond_bucket >> 32).to_uint() & 0xffff
  let dist_xor = (cond_bucket >> 48).to_uint()
  let dist = dist ^ dist_xor
  let symbol = if map_to_alias { alias_symbol } else { i }
  let offset = offset + pos
  let next_state = (state >> 12) * dist + offset
  let appended_state = (next_state << 16) | bitstream.peek_bits(16)
  if next_state < 0x10000 {
    self.state = appended_state
    bitstream.consume_bits(16)
  } else {
    self.state = next_state
  }
  symbol
}

///|
fn ans_read_prefix(
  bitstream : @bitstream.Bitstream,
) -> Int32 raise @bitstream.JxlError {
  match bitstream.read_bits(3) {
    0 => 10
    1 => {
      if bitstream.read_bool() {
        return 4
      }
      if bitstream.read_bool() {
        return 0
      }
      if bitstream.read_bool() {
        return 11
      }
      if bitstream.read_bool() {
        return 13
      }
      12
    }
    2 => 7
    3 => if bitstream.read_bool() { 1 } else { 3 }
    4 => 6
    5 => 8
    6 => 9
    _ => if bitstream.read_bool() { 2 } else { 5 }
  }
}