(** Bitstream - Bit-level I/O for binary formats.

    This library provides efficient bit-level reading and writing for parsing
    and generating binary formats. It supports both forward (start-to-end) and
    backward (end-to-start) operations, as required by various compression
    algorithms.

    {1 Overview}

    {[
      (* Forward reading from a slice (zero-copy) *)
      let slice = { Bitstream.Slice.bytes = data; first = 0; length = n } in
      let r = Bitstream.Forward_reader.of_slice slice in
      let magic = Bitstream.Forward_reader.read_bits r 32 in
      let flags = Bitstream.Forward_reader.read_bits r 8 in

      (* Get remaining data as a slice (zero-copy) *)
      let remaining = Bitstream.Forward_reader.to_slice r in

      (* Backward reading - for FSE/ANS entropy decoding *)
      let r = Bitstream.Backward_reader.of_slice slice in
      let symbol = Bitstream.Backward_reader.read_bits r num_bits
    ]}

    {1 Bytesrw Compatibility}

    The {!Slice} type is structurally compatible with [Bytesrw.Bytes.Slice.t],
    enabling zero-copy integration with bytesrw-based streaming. All reader
    and writer constructors accept slices as the primary input type.

    {1 Error Handling}

    Operations raise exceptions on error:
    - {!End_of_stream}: Reading past end of stream
    - {!Invalid_state}: Operation requires specific state (e.g., byte alignment)
    - {!Corrupted_stream}: Malformed stream data *)

(** {1 Slice Type}

    A slice is a view into a byte buffer. This type is structurally compatible
    with [Bytesrw.Bytes.Slice.t], enabling zero-copy interop. *)

module Slice : sig
  type t = {
    bytes : bytes;
    first : int;
    length : int;
  }
  (** A slice referencing [length] bytes starting at [first] in [bytes].
      This is structurally identical to [Bytesrw.Bytes.Slice.t]. *)

  val make : bytes -> first:int -> length:int -> t
  (** [make bytes ~first ~length] creates a slice. *)

  val of_bytes : ?first:int -> ?length:int -> bytes -> t
  (** [of_bytes bytes] creates a slice for the entire buffer.
      Optional [first] and [length] can restrict the range. *)

  val to_bytes : t -> bytes
  (** [to_bytes t] copies the slice contents to a new buffer. *)

  val is_empty : t -> bool
  (** [is_empty t] returns true if the slice has zero length. *)

  val sub : t -> first:int -> length:int -> t
  (** [sub t ~first ~length] creates a sub-slice. [first] is relative to [t]. *)
end

(** {1 Exceptions} *)

exception End_of_stream
(** Raised when attempting to read past the end of the stream. *)

exception Invalid_state of string
(** Raised when an operation requires a specific state (e.g., byte alignment). *)

exception Corrupted_stream of string
(** Raised when stream data is malformed (e.g., invalid padding marker). *)

(** {1 Forward Bitstream Reader} *)

module Forward_reader : sig
  (** Forward bitstream reader state. *)
  type t

  val of_slice : Slice.t -> t
  (** [of_slice slice] creates a reader from a slice. Zero-copy. *)

  val of_bytes : bytes -> t
  (** [of_bytes src] creates a reader for the entire byte buffer. *)

  val create : bytes -> pos:int -> len:int -> t
  (** [create src ~pos ~len] creates a reader for [len] bytes starting at [pos]. *)

  val remaining : t -> int
  (** [remaining t] returns the number of unread bits. *)

  val is_byte_aligned : t -> bool
  (** [is_byte_aligned t] returns true if the reader is at a byte boundary. *)

  val read_bits : t -> int -> int
  (** [read_bits t n] reads and returns [n] bits (1-57) in little-endian order.
      @raise End_of_stream if not enough data available.
      @raise Invalid_argument if [n > 57]. *)

  val read_byte : t -> int
  (** [read_byte t] reads and returns the next byte (0-255).
      @raise Invalid_state if not byte aligned.
      @raise End_of_stream if at end of stream. *)

  val rewind_bits : t -> int -> unit
  (** [rewind_bits t n] rewinds the stream by [n] bits.
      @raise End_of_stream if rewinding past the start. *)

  val align : t -> unit
  (** [align t] advances to the next byte boundary if not already aligned. *)

  val byte_position : t -> int
  (** [byte_position t] returns the current byte position.
      @raise Invalid_state if not byte aligned. *)

  val get_slice : t -> int -> Slice.t
  (** [get_slice t n] returns the next [n] bytes as a slice (zero-copy).
      The slice references the underlying buffer directly.
      @raise Invalid_state if not byte aligned.
      @raise End_of_stream if not enough data. *)

  val get_bytes : t -> int -> bytes
  (** [get_bytes t n] reads and returns the next [n] bytes as a new buffer.
      Equivalent to [Slice.to_bytes (get_slice t n)].
      @raise Invalid_state if not byte aligned.
      @raise End_of_stream if not enough data. *)

  val to_slice : t -> Slice.t
  (** [to_slice t] returns the remaining data as a slice (zero-copy).
      @raise Invalid_state if not byte aligned. *)

  val advance : t -> int -> unit
  (** [advance t n] skips [n] bytes without returning them.
      @raise Invalid_state if not byte aligned.
      @raise End_of_stream if not enough data. *)

  val sub : t -> int -> t
  (** [sub t n] creates a sub-reader for the next [n] bytes and advances [t].
      @raise Invalid_state if not byte aligned.
      @raise End_of_stream if not enough data. *)

  val remaining_bytes : t -> int
  (** [remaining_bytes t] returns the number of unread bytes.
      @raise Invalid_state if not byte aligned. *)

  val skip_bits : t -> int -> unit
  (** [skip_bits t n] skips [n] bits without returning them.
      @raise End_of_stream if not enough data. *)
end

(** {1 Backward Bitstream Reader}

    Reads bits from the end of a buffer towards the start. The stream format
    includes a padding marker: the highest 1-bit in the final byte indicates
    where actual data begins.

    This format is used by FSE and ANS entropy coders. *)

module Backward_reader : sig
  (** Backward bitstream reader state. *)
  type t

  val of_slice : Slice.t -> t
  (** [of_slice slice] creates a backward reader from a slice. Zero-copy.
      @raise End_of_stream if slice is empty.
      @raise Corrupted_stream if padding marker is invalid. *)

  val of_bytes : bytes -> pos:int -> len:int -> t
  (** [of_bytes src ~pos ~len] creates a backward reader.
      The stream is read from position [pos + len - 1] towards [pos].
      @raise End_of_stream if [len = 0].
      @raise Corrupted_stream if padding marker is invalid. *)

  val remaining : t -> int
  (** [remaining t] returns the number of bits remaining. *)

  val is_empty : t -> bool
  (** [is_empty t] returns true if no more bits are available. *)

  val read_bits : t -> int -> int
  (** [read_bits t n] reads and returns [n] bits (1-57).
      Returns 0 bits when reading past the beginning.
      @raise Invalid_argument if [n > 57]. *)

  val peek_bits : t -> int -> int
  (** [peek_bits t n] returns the next [n] bits without consuming them.
      @raise Invalid_argument if [n > 57]. *)
end

(** {1 Forward Bitstream Writer} *)

module Forward_writer : sig
  (** Forward bitstream writer state. *)
  type t

  val of_slice : Slice.t -> t
  (** [of_slice slice] creates a writer into a slice. Zero-copy. *)

  val of_bytes : bytes -> t
  (** [of_bytes dst] creates a writer starting at position 0. *)

  val create : bytes -> pos:int -> t
  (** [create dst ~pos] creates a writer starting at [pos] in buffer [dst]. *)

  val write_bits : t -> int -> int -> unit
  (** [write_bits t value n] writes the lower [n] bits (1-57) of [value]
      in little-endian order.
      @raise Invalid_argument if [n > 57]. *)

  val write_byte : t -> int -> unit
  (** [write_byte t value] writes a single byte. Flushes any partial bits first. *)

  val write_slice : t -> Slice.t -> unit
  (** [write_slice t slice] writes bytes from a slice. Flushes any partial bits first. *)

  val write_bytes : t -> bytes -> unit
  (** [write_bytes t src] writes all bytes from [src]. Flushes any partial bits first. *)

  val byte_position : t -> int
  (** [byte_position t] returns the current output position including any partial byte. *)

  val flush : t -> unit
  (** [flush t] writes any accumulated bits as a partial byte. *)

  val finalize : t -> int
  (** [finalize t] flushes and returns the total number of bytes written. *)

  val to_slice : t -> Slice.t
  (** [to_slice t] flushes and returns the written data as a slice (zero-copy).
      The slice references the underlying destination buffer. *)
end

(** {1 Backward Bitstream Writer}

    Accumulates bits to produce output that will be read backwards.
    Used for FSE and Huffman encoding. *)

module Backward_writer : sig
  (** Backward bitstream writer state. *)
  type t

  val create : int -> t
  (** [create size] creates a writer with an internal buffer of [size] bytes. *)

  val write_bits : t -> int -> int -> unit
  (** [write_bits t value n] accumulates [n] bits from [value]. *)

  val flush_bytes : t -> unit
  (** [flush_bytes t] flushes complete bytes to the internal buffer. *)

  val finalize_to_slice : t -> Slice.t
  (** [finalize_to_slice t] adds the padding marker, flushes, and returns output
      as a slice (zero-copy). The slice references the internal buffer. *)

  val finalize : t -> bytes
  (** [finalize t] adds the padding marker, flushes, and returns the output.
      Equivalent to [Slice.to_bytes (finalize_to_slice t)]. *)

  val current_size : t -> int
  (** [current_size t] returns the current output size estimate. *)
end