///|
pub struct BitReader {
  data : Bytes
  mut byte_pos : Int
  mut bit_buffer : UInt
  mut bits : Int
} derive(Show)

///|
pub fn BitReader::new(data : Bytes) -> BitReader {
  { data, byte_pos: 0, bit_buffer: 0, bits: 0, }
}

///|
pub fn BitReader::read(self : BitReader, count : Int) -> Int raise MspackError {
  if count < 0 || count > 24 {
    raise MspackError("invalid bit count")
  }
  while self.bits < count {
    if self.byte_pos >= self.data.length() {
      raise MspackError("truncated LZX bitstream")
    }
    self.bit_buffer = self.bit_buffer |
      (self.data[self.byte_pos].to_uint() << self.bits)
    self.bits = self.bits + 8
    self.byte_pos = self.byte_pos + 1
  }
  let mask = if count == 0 { 0 } else { (1 << count) - 1 }
  let value = (self.bit_buffer & mask.to_uint()).to_int()
  self.bit_buffer = self.bit_buffer >> count
  self.bits = self.bits - count
  value
}

///|
pub fn BitReader::align_word(self : BitReader) -> Unit raise MspackError {
  let discard = self.bits % 16
  ignore(self.read(discard))
}

///|
pub struct HuffmanTable {
  lengths : Array[Int]
  codes : Array[Int]
  max_bits : Int
} derive(Show)

///|
/// Reverse the low `width` bits of a canonical Huffman code.
fn reverse_huffman_bits(value : Int, width : Int) -> Int {
  let mut source = value
  let mut result = 0
  for _ in 0..> 1
  }
  result
}

///|
pub fn HuffmanTable::build(
  lengths : Array[Int],
) -> HuffmanTable raise MspackError {
  let max_bits = lengths.fold(init=0, fn(max, n) {
    if n > max {
      n
    } else {
      max
    }
  })
  if max_bits > 16 {
    raise MspackError("LZX huffman code is too long")
  }
  let counts : Array[Int] = Array::make(max_bits + 1, 0)
  for n in lengths {
    if n < 0 {
      raise MspackError("negative huffman length")
    }
    if n > 0 {
      counts[n] = counts[n] + 1
    }
  }
  let next : Array[Int] = Array::make(max_bits + 1, 0)
  let mut code = 0
  for bits in 1..<(max_bits + 1) {
    code = (code + counts[bits - 1]) << 1
    next[bits] = code
  }
  let codes : Array[Int] = Array::make(lengths.length(), 0)
  for i in 0.. 0 {
      codes[i] = reverse_huffman_bits(next[n], n)
      next[n] = next[n] + 1
    }
  }
  { lengths, codes, max_bits, }
}

///|
pub fn HuffmanTable::decode(
  self : HuffmanTable,
  bits : BitReader,
) -> (BitReader, Int) raise MspackError {
  let mut code = 0
  for width in 1..<(self.max_bits + 1) {
    let bit = bits.read(1)
    code = code | (bit << (width - 1))
    for i in 0.. LzxWindow raise MspackError {
  if window_bits < 15 || window_bits > 21 {
    raise MspackError("unsupported LZX window size")
  }
  let size = 1 << window_bits
  { size, position: 0, data: Array::make(size, 0), }
}

///|
pub fn LzxWindow::put(self : LzxWindow, value : Byte) -> Unit {
  self.data[self.position % self.size] = value
  self.position = self.position + 1
}

///|
pub fn LzxWindow::copy(
  self : LzxWindow,
  distance : Int,
  length : Int,
) -> Unit raise MspackError {
  if distance <= 0 || distance > self.size {
    raise MspackError("invalid LZX match distance")
  }
  if length < 0 || length > self.size {
    raise MspackError("invalid LZX match length")
  }
  for _ in 0.. Bytes raise MspackError {
  let window = LzxWindow::new(window_bits)
  if expected < 0 || expected > limits.max_output {
    raise MspackError("LZX output exceeds limit")
  }
  if data.length() == 0 && expected != 0 {
    raise MspackError("empty LZX block")
  }
  if expected == 0 {
    ignore(window)
    b""
  } else {
    let bits = BitReader::new(data)
    let block_type = bits.read(3)
    let block_length_low = bits.read(16)
    let block_length_high = bits.read(8)
    let block_length = block_length_low | (block_length_high << 16)
    if block_length != expected {
      raise MspackError("LZX block length does not match expected output")
    }
    if block_type == 3 {
      bits.align_word()
      ignore(bits.read(32))
      ignore(bits.read(32))
      ignore(bits.read(32))
      let (bits, raw) = bits.bytes(expected)
      ignore(bits)
      raw
    } else {
      raise MspackError("compressed LZX block decoder is not yet complete")
    }
  }
}

///|
/// Read whole bytes after the current bit cursor is byte aligned.
pub fn BitReader::bytes(
  self : BitReader,
  count : Int,
) -> (BitReader, Bytes) raise MspackError {
  if count < 0 || self.bits != 0 || self.byte_pos + count > self.data.length() {
    raise MspackError("truncated LZX uncompressed block")
  }
  let out : Array[Byte] = []
  for i in 0.. Int raise MspackError {
  if window_bits < 15 || window_bits > 21 {
    raise MspackError("unsupported LZX window size")
  }
  if window_bits == 15 {
    30
  } else if window_bits == 16 {
    32
  } else {
    32 + (window_bits - 17) * 8
  }
}

///|
/// Build the extra-bit table for the LZX position slots.
pub fn lzx_position_extra_bits(
  window_bits : Int,
) -> Array[Int] raise MspackError {
  let slots = lzx_position_slots(window_bits)
  let result : Array[Int] = []
  for slot in 0.. Int raise MspackError {
  if symbol < 0 || symbol >= lzx_secondary_lengths {
    raise MspackError("invalid LZX length symbol")
  }
  if symbol < lzx_primary_lengths {
    lzx_min_match + symbol
  } else {
    lzx_min_match + symbol
  }
}

///|
/// Decode a run of LZX code lengths using a pretree.
pub fn decode_lzx_code_lengths(
  bits : BitReader,
  pretree : HuffmanTable,
  count : Int,
  previous? : Int = 0,
) -> (BitReader, Array[Int]) raise MspackError {
  if count < 0 || count > 4096 {
    raise MspackError("invalid LZX code length count")
  }
  let result : Array[Int] = []
  let mut cursor = bits
  let mut last = previous
  while result.length() < count {
    let (next, symbol) = pretree.decode(cursor)
    cursor = next
    if symbol <= 16 {
      let delta = cursor.read(4)
      let value = (last - delta + 17) % 17
      result.push(value)
      last = value
    } else if symbol == 17 {
      let extra = cursor.read(4)
      let run = extra + 4
      if result.length() + run > count {
        raise MspackError("LZX code length run exceeds tree")
      }
      for _ in 0.. count {
        raise MspackError("LZX code length run exceeds tree")
      }
      for _ in 0.. count {
        raise MspackError("LZX code length run exceeds tree")
      }
      for _ in 0.. Unit raise MspackError {
  if lengths.length() == 0 || lengths.length() > 4096 {
    raise MspackError("invalid LZX tree size")
  }
  let mut nonzero = 0
  for length in lengths {
    if length < 0 || length > 16 {
      raise MspackError("invalid LZX tree code length")
    }
    if length > 0 {
      nonzero = nonzero + 1
    }
  }
  if nonzero == 0 {
    raise MspackError("empty LZX huffman tree")
  }
}

///|
/// Build and validate a decoding tree from serialized code lengths.
pub fn build_lzx_tree(lengths : Array[Int]) -> HuffmanTable raise MspackError {
  validate_lzx_tree(lengths)
  HuffmanTable::build(lengths)
}

///|
/// Decode a complete tree from a pretree-coded length stream.
pub fn decode_lzx_tree(
  bits : BitReader,
  pretree : HuffmanTable,
  symbols : Int,
) -> (BitReader, HuffmanTable) raise MspackError {
  let (bits, lengths) = decode_lzx_code_lengths(bits, pretree, symbols)
  let tree = build_lzx_tree(lengths)
  (bits, tree)
}

///|
/// Return whether a block type uses the aligned offset tree.
pub fn lzx_uses_aligned_tree(block_type : Int) -> Bool {
  block_type == lzx_block_aligned
}

///|
/// Convert an LZX slot and footer into a match distance.
pub fn lzx_match_distance(
  slot : Int,
  footer : Int,
  recent0 : Int,
  recent1 : Int,
  recent2 : Int,
  window_bits : Int,
) -> Int raise MspackError {
  let extra = lzx_position_extra_bits(window_bits)
  if slot < 0 || slot >= extra.length() {
    raise MspackError("invalid LZX position slot")
  }
  if slot == 0 {
    recent0
  } else if slot == 1 {
    recent1
  } else if slot == 2 {
    recent2
  } else {
    let distance = (1 << extra[slot]) + footer - 1
    if distance <= 0 {
      raise MspackError("invalid LZX match distance")
    }
    distance
  }
}

///|
/// A decoded LZX token, either a literal byte or a window match.
pub enum LzxToken {
  Literal(Byte)
  Match(distance~ : Int, length~ : Int)
} derive(Show, Eq)

///|
/// Emit decoded tokens into a sliding LZX window.
pub fn emit_lzx_tokens(
  window : LzxWindow,
  tokens : Array[LzxToken],
  limits? : Limits = default_limits,
) -> Bytes raise MspackError {
  let output : Array[Byte] = []
  for token in tokens {
    match token {
      Literal(byte) => {
        if output.length() >= limits.max_output {
          raise MspackError("LZX output exceeds limit")
        }
        window.put(byte)
        output.push(byte)
      }
      Match(distance~, length~) => {
        if length < lzx_min_match || length > lzx_max_match {
          raise MspackError("invalid LZX match length")
        }
        if output.length() + length > limits.max_output {
          raise MspackError("LZX output exceeds limit")
        }
        let start = window.position
        window.copy(distance, length)
        for i in 0.. LzxToken raise MspackError {
  if main_symbol < 0 || main_symbol >= lzx_num_chars {
    let length = lzx_match_length(length_symbol)
    Match(distance~, length~)
  } else {
    Literal(main_symbol.to_byte())
  }
}

///|
/// Validate a token stream before emission.
pub fn validate_lzx_tokens(tokens : Array[LzxToken]) -> Unit raise MspackError {
  for token in tokens {
    match token {
      Literal(_) => ()
      Match(distance~, length~) =>
        if distance <= 0 || length < lzx_min_match || length > lzx_max_match {
          raise MspackError("invalid LZX token")
        }
    }
  }
}

///|
/// Construct a literal token for callers outside the package.
pub fn lzx_literal(byte : Byte) -> LzxToken {
  Literal(byte)
}

///|
/// Construct a match token for callers outside the package.
pub fn lzx_match(distance~ : Int, length~ : Int) -> LzxToken {
  Match(distance~, length~)
}

///|
/// Parsed LZX block header.
pub struct LzxBlockHeader {
  pub kind : Int
  pub length : Int
  pub aligned : Bool
} derive(Show, Eq)

///|
/// Read an LZX block header from a bit reader.
pub fn read_lzx_block_header(
  bits : BitReader,
) -> (BitReader, LzxBlockHeader) raise MspackError {
  let kind = bits.read(3)
  let low = bits.read(16)
  let high = bits.read(8)
  let length = low | (high << 16)
  if kind < lzx_block_verbatim || kind > lzx_block_uncompressed {
    raise MspackError("invalid LZX block type")
  }
  let header = { kind, length, aligned: kind == lzx_block_aligned, }
  (bits, header)
}

///|
/// Return the LZX block header size in bytes for diagnostics.
pub fn lzx_header_bytes() -> Int {
  4
}

///|
/// Validate an LZX block header against configured output limits.
pub fn validate_lzx_block_header(
  header : LzxBlockHeader,
  limits? : Limits = default_limits,
) -> Unit raise MspackError {
  if header.length < 0 || header.length > limits.max_output {
    raise MspackError("LZX block exceeds output limit")
  }
  if header.kind == lzx_block_aligned && !header.aligned {
    raise MspackError("invalid aligned LZX block")
  }
}

///|
/// Read and validate a bounded LZX block header.
pub fn inspect_lzx_block(
  data : Bytes,
  limits? : Limits = default_limits,
) -> LzxBlockHeader raise MspackError {
  let bits = BitReader::new(data)
  let (bits, header) = read_lzx_block_header(bits)
  ignore(bits)
  validate_lzx_block_header(header, limits~)
  header
}