// Frames and blocks (RFC 8878 sections 3.1 and 3.1.1.2): the units of the
// state machine outside compressed blocks.

///|
/// The magic number that starts every frame, or a skippable one.
fn Decoder::magic(self : Decoder) -> Unit raise Stop {
  // The bytes are refused as soon as they begin no magic number, so that
  // a byte after the last frame is trailing data even when it is alone.
  let take = (4 - 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 !magic_prefix(self.hdr, self.hdr_len) {
    if self.frames == 0 {
      raise corrupt("not a zstd stream")
    }
    // The stream ends where these bytes begin, if in this step's input.
    self.in_pos = (self.in_pos - self.hdr_len).max(0)
    raise Fail(TrailingData, "data after the last frame")
  }
  if self.hdr_len < 4 {
    raise NeedInput
  }
  let magic = self.hdr_le(0, 4).to_uint()
  if magic == FRAME_MAGIC {
    self.hdr_len = 0
    self.state = FrameHeader
  } else {
    // `magic_prefix` has let only the two kinds through.
    self.state = SkippableSize
  }
}

///|
/// Whether the first `n` bytes of `hdr` begin a magic number, little-endian:
/// a frame's (28 B5 2F FD) or a skippable frame's (5x 2A 4D 18).
fn magic_prefix(hdr : FixedArray[Byte], n : Int32) -> Bool {
  let frame : FixedArray[Byte] = [b'\x28', b'\xB5', b'\x2F', b'\xFD']
  let skippable : FixedArray[Byte] = [b'\x50', b'\x2A', b'\x4D', b'\x18']
  let mut is_frame = true
  let mut is_skippable = true
  for i in 0.. Unit raise Stop {
  self.fill(8)
  self.remaining = self.hdr_le(4, 4).reinterpret_as_int64()
  self.hdr_len = 0
  self.state = SkippableData
}

///|
/// Skips a skippable frame's data without keeping it.
fn Decoder::skippable_data(self : Decoder) -> Unit raise Stop {
  let take = self.remaining.min((self.view.length() - self.in_pos).to_int64())
  self.in_pos += take.to_int()
  self.remaining -= take
  if self.remaining > 0 {
    raise NeedInput
  }
  self.end_member()
}

///|
/// The frame header: what the frame holds and the window it needs.
fn Decoder::frame_header(self : Decoder) -> Unit raise Stop {
  self.fill(1)
  let len = checked(@header.frame_header_len(self.hdr[0].to_int()))
  self.fill(len)
  let header = checked(@header.parse_frame_header(self.hdr[0:len]))
  if header.dictionary_id != 0 {
    let id = header.dictionary_id
    match self.dictionary {
      None =>
        raise Fail(
          DictionaryRequired(Some(id)),
          "the frame needs dictionary \{id}",
        )
      Some(dict) if dict.id != id =>
        raise Fail(
          DictionaryMismatch,
          "the frame needs dictionary \{id}, not \{dict.id}",
        )
      Some(_) => ()
    }
  }
  self.content_size = header.content_size
  // Computed in 64 bits: a descriptor may ask for up to 2^41 + 7 * 2^38.
  let window = header.window_size
  let limit = 1UL << self.max_window_bits
  if window > limit {
    raise Fail(
      LimitExceeded({ resource: Memory, needed: Some(window), limit, }),
      "the frame needs a \{window}-byte window, over the \{limit}-byte limit",
    )
  }
  self.window = window.to_int()
  self.block_max = self.window.min(MAX_BLOCK_SIZE)
  self.has_checksum = header.has_checksum
  self.frame_out = 0
  self.xxh.reset()
  match self.dictionary {
    Some({ entropy: Some(e), .. }) => {
      // A formatted dictionary's tables and repeat offsets, as if from a
      // block before the frame. Decoding only reads the sequence tables (it
      // builds new ones in its own stores), so they are shared; the
      // Huffman table, which a new tree overwrites, is copied.
      self.huffman.copy_from(e.huffman)
      self.huffman_valid = true
      self.ll_table = Some(e.ll)
      self.of_table = Some(e.of)
      self.ml_table = Some(e.ml)
      self.rep.set(e.rep[0], e.rep[1], e.rep[2])
    }
    _ => {
      self.huffman_valid = false
      self.ll_table = None
      self.of_table = None
      self.ml_table = None
      self.rep.reset()
    }
  }
  self.new_frame = true
  self.hdr_len = 0
  self.state = BlockHeader
}

///|
/// Sets the window up for a new frame once the last frame's output is all
/// handed out; false until then.
fn Decoder::start_window(self : Decoder) -> Bool {
  if self.pending > 0 {
    self.drain()
    if self.pending > 0 {
      return false
    }
  }
  if self.ring.length() > self.window {
    self.ring = FixedArray::make(0, b'\x00')
  }
  self.ring_max = self.window
  self.wpos = 0
  self.filled = 0
  self.new_frame = false
  true
}

///|
fn Decoder::block_header(self : Decoder) -> Status? raise Stop {
  if self.new_frame && !self.start_window() {
    return Some(NeedMoreOutput)
  }
  self.fill(3)
  let value = self.hdr_le(0, 3).to_int()
  self.hdr_len = 0
  let header = checked(
    @header.parse_block_header(value).bind(h => h.check(self.block_max)),
  )
  let size = header.size
  self.last_block = header.last
  self.block_size = size
  self.block_out = 0
  match header.block_type {
    Raw => {
      self.remaining = size.to_int64()
      self.state = RawBlock
    }
    Rle => self.state = RleByte
    Compressed => {
      if self.block.length() < size {
        self.block = FixedArray::make(size, b'\x00')
      }
      self.block_len = 0
      self.state = CompressedBlock
    }
  }
  None
}

///|
fn Decoder::raw_block(self : Decoder) -> Status? raise Stop {
  while self.remaining > 0 {
    let available = self.view.length() - self.in_pos
    if available == 0 {
      raise NeedInput
    }
    let n = self.room(self.remaining.to_int().min(available))
    if n == 0 {
      return Some(NeedMoreOutput)
    }
    self.copy_input(n)
    self.remaining -= n.to_int64()
  }
  self.end_block()
  None
}

///|
fn Decoder::rle_byte(self : Decoder) -> Unit raise Stop {
  self.fill(1)
  self.rle_byte = self.hdr[0]
  self.hdr_len = 0
  self.remaining = self.block_size.to_int64()
  self.state = RleRun
}

///|
fn Decoder::rle_run(self : Decoder) -> Status? raise Stop {
  while self.remaining > 0 {
    let n = self.room(self.remaining.to_int())
    if n == 0 {
      return Some(NeedMoreOutput)
    }
    self.put_run(self.rle_byte, n)
    self.remaining -= n.to_int64()
  }
  self.end_block()
  None
}

///|
/// Gathers a compressed block, then decodes it once earlier output is all
/// handed out.
fn Decoder::compressed_block(self : Decoder) -> Status? raise Stop {
  let take = (self.block_size - self.block_len).min(
    self.view.length() - self.in_pos,
  )
  if take > 0 {
    self.block.blit_from_bytesview(
      self.block_len,
      self.view[self.in_pos:self.in_pos + take],
    )
    self.block_len += take
    self.in_pos += take
  }
  if self.block_len < self.block_size {
    raise NeedInput
  }
  if self.pending > 0 {
    self.drain()
    if self.pending > 0 {
      return Some(NeedMoreOutput)
    }
  }
  self.decode_block()
  self.end_block()
  None
}

///|
fn Decoder::end_block(self : Decoder) -> Unit raise Stop {
  self.count_block()
  if self.content_size is Some(size) && self.frame_out > size {
    raise corrupt("the frame holds more than its declared content size")
  }
  if !self.last_block {
    self.state = BlockHeader
  } else if self.has_checksum {
    self.state = Checksum
  } else {
    self.end_frame()
  }
}

///|
fn Decoder::checksum(self : Decoder) -> Unit raise Stop {
  self.fill(4)
  let stored = self.hdr_le(0, 4).to_uint()
  self.hdr_len = 0
  if stored != self.xxh.digest().to_uint() {
    raise Fail(ChecksumMismatch, "the frame's content checksum does not match")
  }
  self.end_frame()
}

///|
fn Decoder::end_frame(self : Decoder) -> Unit raise Stop {
  if self.content_size is Some(size) && self.frame_out != size {
    raise corrupt("the frame holds less than its declared content size")
  }
  self.end_member()
}

///|
/// Counts a whole frame, skippable or not. Under `EndOfMember` the stream
/// ends here; otherwise another frame may follow.
fn Decoder::end_member(self : Decoder) -> Unit {
  self.frames += 1
  self.state = if self.until is EndOfMember { Done } else { Magic }
}