// The streaming decoder.
//
// Suspension model: zstd is byte-aligned outside compressed blocks, so the
// decoder works in coarse units. Header fields gather in `hdr` (at most 14
// bytes) and a compressed block gathers whole in `block` (at most 128 KiB)
// before it is decoded in one go: its bitstreams are read backwards from its
// end. Raw and RLE blocks stream straight to the window. A unit takes every
// input byte it is offered, so the caller may drop each chunk; when the
// input runs out a unit raises `NeedInput`.
//
// Decoded bytes go to the window, a ring of at most `Window_Size` bytes,
// and are copied out to the caller's buffer, so output can be handed out in
// slices of any size. A compressed block is decoded only once all earlier
// output is handed out, so its output never overwrites bytes still pending.

///|
priv enum State {
  Magic
  SkippableSize
  SkippableData
  FrameHeader
  BlockHeader
  RawBlock
  RleByte
  RleRun
  CompressedBlock
  Checksum
  Done
}

///|
/// The zstd frame magic number.
const FRAME_MAGIC : UInt32 = 0xFD2FB528

///|
/// The largest block a frame may hold, compressed or not.
const MAX_BLOCK_SIZE : Int32 = 1 << 17

///|
/// The first window allocation; it doubles as output grows, up to the
/// frame's window.
const INITIAL_WINDOW : Int32 = 1024

///|
/// A streaming Zstandard decoder (RFC 8878). Feed it input in chunks of any
/// size with `step` and collect output in slices of any size; it keeps the
/// window (no more than a frame's `Window_Size`, and no more than its output
/// so far), one compressed block and fixed-size tables, never the whole
/// input or output.
pub struct Decoder {
  priv max_window_bits : Int32
  // The input of the current step.
  priv mut view : BytesView
  priv mut in_pos : Int32
  // Header bytes gathered so far.
  priv hdr : FixedArray[Byte]
  priv mut hdr_len : Int32
  // The caller's output buffer for the current step.
  priv mut out : MutArrayView[Byte]
  priv mut fixed_out : FixedArray[Byte]?
  priv mut out_pos : Int32
  priv empty_out : FixedArray[Byte]
  // The window: a ring of up to `ring_max` bytes, allocated as output
  // grows; it wraps only once it is `ring_max` long. `pending` bytes before
  // `wpos` are not handed out yet; `filled` is how far back an offset may
  // reach, min(frame output, window).
  priv mut ring : FixedArray[Byte]
  priv mut ring_max : Int32
  priv mut wpos : Int32
  priv mut pending : Int32
  priv mut filled : Int32
  // Stream state.
  priv mut state : State
  priv mut frames : Int32
  priv mut failure : ZstdError?
  priv mut step_consumed : Int32
  priv mut step_produced : Int32
  // The current frame.
  priv mut new_frame : Bool
  priv mut window : Int32
  priv mut block_max : Int32
  priv mut has_checksum : Bool
  priv mut content_size : UInt64?
  priv mut frame_out : UInt64
  priv xxh : @xxhash.Xxh64
  // The current block.
  priv mut last_block : Bool
  priv mut block_size : Int32
  priv mut remaining : Int64
  priv mut rle_byte : Byte
  priv mut block : FixedArray[Byte]
  priv mut block_len : Int32
  priv mut block_out : Int32
  // Compressed blocks: literals, the tables kept from block to block, and
  // the repeat offsets.
  priv mut literals : FixedArray[Byte]
  priv mut literals_len : Int32
  priv huffman : Huffman
  priv mut huffman_valid : Bool
  priv ll_store : Fse
  priv of_store : Fse
  priv ml_store : Fse
  priv mut ll_table : Fse?
  priv mut of_table : Fse?
  priv mut ml_table : Fse?
  priv scratch : FseScratch
  priv rep : FixedArray[Int32]
}

///|
/// A decoder at the start of a stream. It refuses, with `WindowTooLarge`,
/// a frame whose `Window_Size` exceeds `1 << max_window_bits` bytes (the
/// window memory it would need). The default 27 is the reference decoder's
/// default limit; RFC 9659 asks HTTP clients to accept 23 (8 MiB). Values
/// are clamped to 10..30.
pub fn Decoder::Decoder(max_window_bits~ : Int32 = 27) -> Decoder {
  let empty_out = FixedArray::make(0, b'\x00')
  {
    max_window_bits: max_window_bits.clamp(min=10, max=30),
    view: b""[:],
    in_pos: 0,
    hdr: FixedArray::make(14, b'\x00'),
    hdr_len: 0,
    out: empty_out.mut_view(),
    fixed_out: None,
    out_pos: 0,
    empty_out,
    ring: FixedArray::make(0, b'\x00'),
    ring_max: 0,
    wpos: 0,
    pending: 0,
    filled: 0,
    state: Magic,
    frames: 0,
    failure: None,
    step_consumed: 0,
    step_produced: 0,
    new_frame: false,
    window: 0,
    block_max: 0,
    has_checksum: false,
    content_size: None,
    frame_out: 0,
    xxh: @xxhash.Xxh64(),
    last_block: false,
    block_size: 0,
    remaining: 0,
    rle_byte: b'\x00',
    block: FixedArray::make(0, b'\x00'),
    block_len: 0,
    block_out: 0,
    literals: FixedArray::make(0, b'\x00'),
    literals_len: 0,
    huffman: Huffman::new(),
    huffman_valid: false,
    ll_store: Fse::new(9),
    of_store: Fse::new(8),
    ml_store: Fse::new(9),
    ll_table: None,
    of_table: None,
    ml_table: None,
    scratch: FseScratch::new(),
    rep: [1, 4, 8],
  }
}

///|
/// Starts a new stream, keeping the tables' memory. The window and the
/// block buffers are released.
pub fn Decoder::reset(self : Decoder) -> Unit {
  self.release_step()
  self.hdr_len = 0
  self.ring = FixedArray::make(0, b'\x00')
  self.ring_max = 0
  self.wpos = 0
  self.pending = 0
  self.filled = 0
  self.state = Magic
  self.frames = 0
  self.failure = None
  self.step_consumed = 0
  self.step_produced = 0
  self.new_frame = false
  self.block = FixedArray::make(0, b'\x00')
  self.block_len = 0
  self.literals = FixedArray::make(0, b'\x00')
  self.literals_len = 0
}

///|
/// Whether the stream has ended and all its output has been handed out.
pub fn Decoder::is_finished(self : Decoder) -> Bool {
  self.state is Done && self.pending == 0
}

///|
/// Input bytes the latest `step` accepted: all of them on `NeedMoreInput`.
/// Zero after a step that raised.
pub fn Decoder::last_consumed(self : Decoder) -> Int32 {
  self.step_consumed
}

///|
/// Output bytes the latest `step` wrote. Zero after a step that raised.
pub fn Decoder::last_produced(self : Decoder) -> Int32 {
  self.step_produced
}

///|
/// Decodes from `input` into `output`; see `last_consumed` and
/// `last_produced` for how much of each it used.
///
/// A stream is one or more frames, and nothing marks its last one, so pass
/// `end=true` once `input` holds the last bytes: the stream then ends after
/// the frame in progress, and a stream cut short raises `Truncated`. Without
/// `end`, the decoder answers `NeedMoreInput` between frames. Bytes after the
/// last frame that start no frame raise `Corrupt`. After an error the
/// decoder raises it again until `reset`.
pub fn Decoder::step(
  self : Decoder,
  input : BytesView,
  output : MutArrayView[Byte],
  end~ : Bool = false,
) -> Status raise ZstdError {
  self.step_with(input, output, None, end~)
}

///|
/// `step` into a whole `FixedArray`, with bulk copies.
pub fn Decoder::step_into(
  self : Decoder,
  input : BytesView,
  output : FixedArray[Byte],
  end~ : Bool = false,
) -> Status raise ZstdError {
  self.step_with(input, output.mut_view(), Some(output), end~)
}

///|
fn Decoder::step_with(
  self : Decoder,
  input : BytesView,
  output : MutArrayView[Byte],
  fixed_output : FixedArray[Byte]?,
  end~ : Bool,
) -> Status raise ZstdError {
  self.step_consumed = 0
  self.step_produced = 0
  if self.failure is Some(err) {
    raise err
  }
  self.view = input
  self.in_pos = 0
  self.out = output
  self.fixed_out = fixed_output
  self.out_pos = 0
  let status = self.run() catch { err => self.fail(err) }
  let status = match status {
    NeedMoreInput if end =>
      if !(self.state is Magic && self.hdr_len == 0) {
        self.fail(ZstdError(Truncated, "the stream ends inside a frame"))
      } else if self.frames == 0 {
        self.fail(ZstdError(Truncated, "the stream holds no frame"))
      } else {
        self.state = Done
        Status::Done
      }
    status => status
  }
  self.drain()
  self.finish_step(if self.pending > 0 { NeedMoreOutput } else { status })
}

///|
fn Decoder::finish_step(self : Decoder, status : Status) -> Status {
  self.step_consumed = self.in_pos
  self.step_produced = self.out_pos
  self.release_step()
  status
}

///|
/// Records a terminal error and raises it.
fn[T] Decoder::fail(self : Decoder, err : ZstdError) -> T raise ZstdError {
  self.failure = Some(err)
  self.release_step()
  raise err
}

///|
/// Drops the caller's buffers so a suspended decoder holds neither.
fn Decoder::release_step(self : Decoder) -> Unit {
  self.view = b""[:]
  self.in_pos = 0
  self.out = self.empty_out.mut_view()
  self.fixed_out = None
  self.out_pos = 0
}

// ---- input ----

///|
/// Gathers header bytes until `hdr` holds `n`.
fn Decoder::fill(self : Decoder, n : Int32) -> Unit raise Stop {
  let take = (n - self.hdr_len).min(self.view.length() - self.in_pos)
  if take > 0 {
    self.hdr.blit_from_bytesview(
      self.hdr_len,
      self.view[self.in_pos:self.in_pos + take],
    )
    self.hdr_len += take
    self.in_pos += take
  }
  if self.hdr_len < n {
    raise NeedInput
  }
}

///|
/// The little-endian value of `hdr[at:at + n]`, up to 8 bytes.
fn Decoder::hdr_le(self : Decoder, at : Int32, n : Int32) -> UInt64 {
  let mut v : UInt64 = 0
  for i = n - 1; i >= 0; i = i - 1 {
    v = (v << 8) | self.hdr[at + i].to_uint64()
  }
  v
}

// ---- window ----

///|
/// Makes `k` bytes writable, growing the window or handing out pending
/// output; false when the caller's buffer is full first.
fn Decoder::ensure_space(self : Decoder, k : Int32) -> Bool {
  let cap = self.ring.length()
  if cap == self.ring_max {
    if self.pending + k <= cap {
      return true
    }
    self.drain()
    return self.pending + k <= cap
  }
  if self.wpos + k <= cap {
    return true
  }
  let mut grown = cap.max(INITIAL_WINDOW)
  while grown < self.wpos + k && grown < self.ring_max {
    grown = grown * 2
  }
  let ring = FixedArray::make(grown.min(self.ring_max), b'\x00')
  FixedArray::unsafe_blit(ring, 0, self.ring, 0, self.wpos)
  self.ring = ring
  self.ensure_space(k)
}

///|
/// How many of `k` bytes can be written now: `k`, or fewer once the window
/// is full of pending output and the caller's buffer is full.
fn Decoder::room(self : Decoder, k : Int32) -> Int32 {
  if self.ensure_space(k) {
    k
  } else {
    self.ring.length() - self.pending
  }
}

///|
/// Accounts for `n` bytes just written at `wpos`.
fn Decoder::advance(self : Decoder, n : Int32) -> Unit {
  if self.has_checksum {
    self.xxh.update(self.ring, self.wpos, n)
  }
  self.wpos += n
  if self.wpos == self.ring_max {
    self.wpos = 0
  }
  self.pending += n
  self.filled = (self.filled + n).min(self.window)
  self.frame_out += n.to_uint64()
  self.block_out += n
}

///|
/// Writes `n` copies of `b`; `ensure_space(n)` has made room.
fn Decoder::put_run(self : Decoder, b : Byte, n : Int32) -> Unit {
  let mut remaining = n
  while remaining > 0 {
    let chunk = remaining.min(self.ring.length() - self.wpos)
    self.ring.fill(b, start=self.wpos, end=self.wpos + chunk)
    self.advance(chunk)
    remaining -= chunk
  }
}

///|
/// Copies `n` bytes of `src` from `at`; `ensure_space(n)` has made room.
fn Decoder::put_array(
  self : Decoder,
  src : FixedArray[Byte],
  at : Int32,
  n : Int32,
) -> Unit {
  let mut remaining = n
  let mut from = at
  while remaining > 0 {
    let chunk = remaining.min(self.ring.length() - self.wpos)
    FixedArray::unsafe_blit(self.ring, self.wpos, src, from, chunk)
    self.advance(chunk)
    from += chunk
    remaining -= chunk
  }
}

///|
/// Copies `n` input bytes from the view; `ensure_space(n)` has made room.
fn Decoder::copy_input(self : Decoder, n : Int32) -> Unit {
  let mut remaining = n
  while remaining > 0 {
    let chunk = remaining.min(self.ring.length() - self.wpos)
    self.ring.blit_from_bytesview(
      self.wpos,
      self.view[self.in_pos:self.in_pos + chunk],
    )
    self.in_pos += chunk
    self.advance(chunk)
    remaining -= chunk
  }
}

///|
/// Copies `n` bytes from `dist` back, `dist <= filled`; `ensure_space(n)`
/// has made room.
fn Decoder::copy_back(self : Decoder, dist : Int32, n : Int32) -> Unit {
  let ring = self.ring
  let cap = ring.length()
  let mut remaining = n
  while remaining > 0 {
    let mut src = self.wpos - dist
    if src < 0 {
      src += cap
    }
    let dst = self.wpos
    let chunk = remaining.min(cap - src).min(cap - dst)
    if dist >= chunk {
      FixedArray::unsafe_blit(ring, dst, ring, src, chunk)
    } else {
      // Overlapping: each byte may repeat one written in this copy.
      for i in 0.. Unit {
  let n = self.pending.min(self.out.length() - self.out_pos)
  guard n > 0 else { return }
  let cap = self.ring.length()
  let mut read = self.wpos - self.pending
  if read < 0 {
    read += cap
  }
  let first = n.min(cap - read)
  self.write_out(read, first)
  self.write_out(0, n - first)
  self.pending -= n
}

///|
fn Decoder::write_out(self : Decoder, start : Int32, n : Int32) -> Unit {
  match self.fixed_out {
    Some(out) => FixedArray::unsafe_blit(out, self.out_pos, self.ring, start, n)
    None =>
      for i in 0.. Status raise ZstdError {
  for ;; {
    let status = self.unit() catch {
      NeedInput => return NeedMoreInput
      Fail(kind, message) => raise ZstdError(kind, message)
    }
    if status is Some(status) {
      return status
    }
  }
}

///|
/// One unit; `Some` stops the run.
fn Decoder::unit(self : Decoder) -> Status? raise Stop {
  match self.state {
    Magic => self.magic()
    SkippableSize => self.skippable_size()
    SkippableData => self.skippable_data()
    FrameHeader => self.frame_header()
    BlockHeader => return self.block_header()
    RawBlock => return self.raw_block()
    RleByte => self.rle_byte()
    RleRun => return self.rle_run()
    CompressedBlock => return self.compressed_block()
    Checksum => self.checksum()
    Done => {
      if self.in_pos < self.view.length() {
        raise corrupt("data after the end of the stream")
      }
      return Some(Done)
    }
  }
  None
}