// Bit readers over a buffered block. FSE and Huffman streams are read
// backwards from their end mark (RFC 8878 section 4.1); table descriptions
// are read forwards. Both read little-endian values.

///|
/// `len` bits of `data` starting at bit `lo` from `start`, least significant
/// first. `len` is at most 24 and may be zero; the caller keeps every bit it
/// reads inside the stream.
#inline
fn bits_at(
  data : FixedArray[Byte],
  start : Int32,
  lo : Int32,
  len : Int32,
) -> Int32 {
  let i = start + (lo >> 3)
  // Four bytes hold the at most 7 + 24 bits: one load, no branch on how
  // many bytes the bits span. A zero `len` masks everything off.
  if i >= 0 && i + 4 <= data.length() {
    ((load32(data, i) >> (lo & 7)) & ((1U << len) - 1)).reinterpret_as_int()
  } else {
    bits_near_end(data, start, lo, len)
  }
}

///|
/// `bits_at` within the last three bytes of `data`, a byte at a time.
fn bits_near_end(
  data : FixedArray[Byte],
  start : Int32,
  lo : Int32,
  len : Int32,
) -> Int32 {
  guard len > 0 else { return 0 }
  let i = start + (lo >> 3)
  let shift = lo & 7
  let mut v = data[i].to_uint()
  let last = start + ((lo + len - 1) >> 3)
  if last > i {
    v = v | (data[i + 1].to_uint() << 8)
    if last > i + 1 {
      // Fewer than four bytes are left from i (else `bits_at` reads them
      // at once), and the bits are within them.
      v = v | (data[i + 2].to_uint() << 16)
    }
  }
  ((v >> shift) & ((1U << len) - 1)).reinterpret_as_int()
}

///|
/// A stream read backwards: `pos` bits are left before the read position.
/// Reads past the start give zero bits and make `pos` negative, which the
/// caller treats as corruption once the stream should be used up.
priv struct BackwardBits {
  data : FixedArray[Byte]
  start : Int32
  mut pos : Int32
}

///|
/// The stream in `data[start:end]`, positioned after its end mark: the
/// highest set bit of the last byte.
fn BackwardBits::new(
  data : FixedArray[Byte],
  start : Int32,
  end : Int32,
) -> BackwardBits raise Stop {
  if end <= start {
    raise corrupt("an empty bitstream")
  }
  let last = data[end - 1]
  if last == 0 {
    raise corrupt("a bitstream without its end mark")
  }
  let pos = (end - start - 1) * 8 + (31 - last.to_int().clz())
  { data, start, pos, }
}

///|
/// The next `n` (at most 24) bits without consuming them.
#inline
fn BackwardBits::peek(self : BackwardBits, n : Int32) -> Int32 {
  let lo = self.pos - n
  if lo >= 0 {
    bits_at(self.data, self.start, lo, n)
  } else if self.pos <= 0 {
    0
  } else {
    bits_at(self.data, self.start, 0, self.pos) << -lo
  }
}

///|
/// The next `n` (at most 24) bits.
#inline
fn BackwardBits::read(self : BackwardBits, n : Int32) -> Int32 {
  let v = self.peek(n)
  self.pos -= n
  v
}

///|
/// `BackwardBits::peek(n)` of a stream in `data` from `start` with `pos`
/// bits left, for loops that keep `pos` in a local. The common case, bits
/// at or after the stream's start and four bytes before the end of `data`,
/// is written out here so that it is inlined into those loops.
#inline
fn back_bits(
  data : FixedArray[Byte],
  start : Int32,
  pos : Int32,
  n : Int32,
) -> Int32 {
  let lo = pos - n
  let i = start + (lo >> 3)
  if lo >= 0 && i + 4 <= data.length() {
    ((load32(data, i) >> (lo & 7)) & ((1U << n) - 1)).reinterpret_as_int()
  } else {
    back_bits_edge(data, start, pos, n)
  }
}

///|
/// `back_bits` near either end of the stream.
fn back_bits_edge(
  data : FixedArray[Byte],
  start : Int32,
  pos : Int32,
  n : Int32,
) -> Int32 {
  let lo = pos - n
  if lo >= 0 {
    bits_at(data, start, lo, n)
  } else if pos <= 0 {
    0
  } else {
    bits_at(data, start, 0, pos) << -lo
  }
}

///|
/// A stream read forwards, `pos` bits after `start`, ending at `end`.
priv struct ForwardBits {
  data : FixedArray[Byte]
  start : Int32
  end : Int32
  mut pos : Int32
}

///|
fn ForwardBits::new(
  data : FixedArray[Byte],
  start : Int32,
  end : Int32,
) -> ForwardBits {
  { data, start, end, pos: 0, }
}

///|
/// The next `n` (at most 16) bits without consuming them; bits past `end`
/// read as zero, as in the reference decoder.
fn ForwardBits::peek(self : ForwardBits, n : Int32) -> Int32 {
  let total = (self.end - self.start) * 8
  if self.pos + n <= total {
    bits_at(self.data, self.start, self.pos, n)
  } else if self.pos >= total {
    0
  } else {
    bits_at(self.data, self.start, self.pos, total - self.pos)
  }
}

///|
fn ForwardBits::read(self : ForwardBits, n : Int32) -> Int32 {
  let v = self.peek(n)
  self.pos += n
  v
}

///|
/// Whether the reads so far stayed within `end`.
fn ForwardBits::in_bounds(self : ForwardBits) -> Bool {
  self.pos <= (self.end - self.start) * 8
}

///|
/// Whole bytes used so far.
fn ForwardBits::bytes_used(self : ForwardBits) -> Int32 {
  (self.pos + 7) >> 3
}

///|
/// The four bytes at `i`, little-endian; the caller has checked
/// `0 <= i` and `i + 4 <= data.length()`.
#cfg(any(target="native", target="wasm"))
#inline
fn load32(data : FixedArray[Byte], i : Int32) -> UInt32 {
  data.unsafe_reinterpret_as_bytes().unsafe_read_uint32_le(i)
}

///|
/// The four bytes at `i`, little-endian; the caller has checked
/// `0 <= i` and `i + 4 <= data.length()`.
#cfg(not(any(target="native", target="wasm")))
fn load32(data : FixedArray[Byte], i : Int32) -> UInt32 {
  data.unsafe_get(i).to_uint() |
  (data.unsafe_get(i + 1).to_uint() << 8) |
  (data.unsafe_get(i + 2).to_uint() << 16) |
  (data.unsafe_get(i + 3).to_uint() << 24)
}

///|
/// Whether `top_bits` may read at `pos`: at least 57 bits after the
/// stream's start. Never on JS, where 64-bit integers are slow.
#cfg(not(target="js"))
#inline
fn wide_reads(pos : Int32) -> Bool {
  pos >= 57
}

///|
#cfg(target="js")
#inline
fn wide_reads(_pos : Int32) -> Bool {
  false
}

///|
/// The bits before `pos` of the stream in `data` from `start`, the last of
/// them (bit `pos - 1`) as the top bit: at least 57 valid bits, for
/// `pos >= 57`. The eight bytes loaded end with the byte of bit `pos - 1`,
/// which is within the stream.
#inline
fn top_bits(data : FixedArray[Byte], start : Int32, pos : Int32) -> UInt64 {
  let q = pos - 57
  let k = start + (q >> 3)
  load64(data, k) << (7 - (q & 7))
}

///|
/// The top `n` (at most 31) bits of `w`: none when `n` is 0.
#inline
fn take_bits(w : UInt64, n : Int32) -> Int32 {
  (w >> 1 >> (63 - n)).to_int()
}

///|
/// The eight bytes at `i`, little-endian; the caller has checked
/// `0 <= i` and `i + 8 <= data.length()`.
#cfg(any(target="native", target="wasm"))
#inline
fn load64(data : FixedArray[Byte], i : Int32) -> UInt64 {
  data.unsafe_reinterpret_as_bytes().unsafe_read_uint64_le(i)
}

///|
#cfg(not(any(target="native", target="wasm")))
fn load64(data : FixedArray[Byte], i : Int32) -> UInt64 {
  load32(data, i).to_uint64() | (load32(data, i + 4).to_uint64() << 32)
}