Repository: mirage/decompress (ocaml)

Issue:
Compression support
The current implementation of the `GZIP` interface exposes a `compress` function. However, the encoder does not handle any compression level (see `Gz.Def.encoder` interface documentation).

Is it planned to fully implement compression features through this library? 

Pull request:
First shot about a new Lz77 algorithm
It's a new implementation of the Lz77 algorithm. This rewrite updates a bit the interface (where the needed _window_ is larger than before - to be able to _lookup_). I will do some benchmarks. This PR wants to fix #104.

Patch:
diff --git a/bench/dune b/bench/dune
index 2980367..e9b55ce 100644
--- a/bench/dune
+++ b/bench/dune
@@ -30,3 +30,22 @@
   (chdir
    %{workspace_root}
    (run %{run} -o %{targets}))))
+
+(library
+ (name lz_landmarks)
+ (optional)
+ (modules lz_landmarks)
+ (libraries landmarks de)
+ (preprocess
+  (pps landmarks.ppx --auto)))
+
+(rule
+ (copy ../lib/lz.ml lz_landmarks.ml))
+
+(rule
+ (copy ../lib/lz.mli lz_landmarks.mli))
+
+(executable
+ (name lzld)
+ (modules lzld)
+ (libraries lz_landmarks))
diff --git a/bench/lzld.ml b/bench/lzld.ml
new file mode 100644
index 0000000..da61943
--- /dev/null
+++ b/bench/lzld.ml
@@ -0,0 +1,13 @@
+open Lz_landmarks
+
+let q = De.Queue.create 0x1000
+let w = make_window ~bits:15
+
+let () =
+  let state = state ~q ~w (`Channel stdin) in
+  let rec go state =
+    match compress state with
+    | `Flush -> De.Queue.reset q ; go state
+    | `End -> ()
+    | `Await -> assert false in
+  go state
diff --git a/bin/dune b/bin/dune
index be01201..1fb0878 100644
--- a/bin/dune
+++ b/bin/dune
@@ -1,4 +1,10 @@
 (executable
  (name pipe)
+ (modules pipe)
  (libraries checkseum.c bigstringaf fmt rresult mtime mtime.clock.os
    decompress.de decompress.zl decompress.gz cmdliner))
+
+(executable
+ (name lz)
+ (modules lz)
+ (libraries checkseum.c decompress.lz))
diff --git a/bin/lz.ml b/bin/lz.ml
new file mode 100644
index 0000000..2507f9a
--- /dev/null
+++ b/bin/lz.ml
@@ -0,0 +1,15 @@
+let () = Printexc.record_backtrace true
+
+open Lz
+
+let q = De.Queue.create 0x4000
+let w = make_window ~bits:15
+
+let () =
+  let state = state ~q ~w (`Channel stdin) in
+  let rec go state =
+    match compress state with
+    | `Flush -> De.Queue.reset q ; go state
+    | `End -> ()
+    | `Await -> assert false in
+  go state
diff --git a/bin/pipe.ml b/bin/pipe.ml
index 182d7bd..df54c46 100644
--- a/bin/pipe.ml
+++ b/bin/pipe.ml
@@ -1,4 +1,5 @@
 let w = De.make_window ~bits:15
+let l = De.Lz77.make_window ~bits:15
 let o = De.bigstring_create De.io_buffer_size
 let i = De.bigstring_create De.io_buffer_size
 let q = De.Queue.create 4096
@@ -35,54 +36,33 @@ let run_inflate () =
 
 let run_deflate () =
   let open De in
-  let state = Lz77.state `Manual ~w ~q in
-  let kind = ref Def.Fixed in
-  let encoder = Def.encoder `Manual ~q in
+  let state = Lz77.state ~level:4 ~q ~w:l (`Channel stdin) in
+  let encoder = Def.encoder (`Channel stdout) ~q in
 
+  let rec compress () =
+    match De.Lz77.compress state with
+    | `Await -> assert false
+    | `Flush ->
+      let literals = Lz77.literals state in
+      let distances = Lz77.distances state in
+      encode
+      @@ Def.encode encoder
+           (`Block
+             {
+               Def.kind=
+                 Dynamic (Def.dynamic_of_frequencies ~literals ~distances)
+             ; last= false
+             })
+    | `End ->
+      Queue.push_exn q Queue.eob
+      ; pending @@ Def.encode encoder (`Block {Def.kind= Fixed; last= true})
+  and pending = function `Partial | `Block -> assert false | `Ok -> ()
+  and encode = function
+    | `Partial -> assert false
+    | `Ok | `Block -> compress () in
   Def.dst encoder o 0 io_buffer_size
-
-  ; let partial k encoder =
-      let len = io_buffer_size - Def.dst_rem encoder in
-      let tmp = Bigstringaf.substring o ~off:0 ~len in
-
-      if len > 0 then output_string stdout tmp
-      ; Def.dst encoder o 0 io_buffer_size
-      ; k @@ Def.encode encoder `Await in
-
-    let rec compress () =
-      match Lz77.compress state with
-      | `Await ->
-        let len = bigstring_input stdin i 0 io_buffer_size in
-        Lz77.src state i 0 len ; compress ()
-      | `End ->
-        Queue.push_exn q Queue.eob
-        ; pending
-          @@ Def.encode encoder (`Block {Def.kind= Def.Fixed; last= true})
-      | `Flush ->
-        kind :=
-          Def.Dynamic
-            (Def.dynamic_of_frequencies ~literals:(Lz77.literals state)
-               ~distances:(Lz77.distances state))
-        ; encode @@ Def.encode encoder (`Block {Def.kind= !kind; last= false})
-    and encode = function
-      | `Partial -> partial encode encoder
-      | `Ok -> compress ()
-      | `Block ->
-        kind :=
-          Def.Dynamic
-            (Def.dynamic_of_frequencies ~literals:(Lz77.literals state)
-               ~distances:(Lz77.distances state))
-        ; encode @@ Def.encode encoder (`Block {Def.kind= !kind; last= false})
-    and pending = function
-      | `Partial -> partial pending encoder
-      | `Block -> assert false (* never occur! *)
-      | `Ok -> last @@ Def.encode encoder `Flush
-    and last = function
-      | `Partial -> partial last encoder
-      | `Ok -> `Ok ()
-      | `Block -> assert false in
-
-    compress ()
+  ; compress ()
+  ; `Ok ()
 
 let run_zlib_inflate () =
   let open Zl in
@@ -92,39 +72,39 @@ let run_zlib_inflate () =
   let rec go decoder =
     match Inf.decode decoder with
     | `Await decoder ->
-      let len = bigstring_input stdin i 0 io_buffer_size in
+      let len = bigstring_input stdin i 0 De.io_buffer_size in
       Inf.src decoder i 0 len |> go
     | `Flush decoder ->
-      let len = io_buffer_size - Inf.dst_rem decoder in
+      let len = De.io_buffer_size - Inf.dst_rem decoder in
       bigstring_output stdout o 0 len
       ; Inf.flush decoder |> go
     | `Malformed err ->
       Fmt.epr "%si (remaining byte(s): %d)\n%!" err (Inf.dst_rem decoder)
       ; `Error err
     | `End decoder ->
-      let len = io_buffer_size - Inf.dst_rem decoder in
+      let len = De.io_buffer_size - Inf.dst_rem decoder in
       if len > 0 then bigstring_output stdout o 0 len
       ; `Ok () in
   go decoder
 
 let run_zlib_deflate () =
   let open Zl in
-  let encoder = Def.encoder `Manual `Manual ~q ~w ~level:0 in
+  let encoder = Def.encoder `Manual `Manual ~q ~w:l ~level:0 in
 
   let rec go encoder =
     match Def.encode encoder with
     | `Await encoder ->
-      let len = bigstring_input stdin i 0 io_buffer_size in
+      let len = bigstring_input stdin i 0 De.io_buffer_size in
       Def.src encoder i 0 len |> go
     | `Flush encoder ->
-      let len = io_buffer_size - Def.dst_rem encoder in
+      let len = De.io_buffer_size - Def.dst_rem encoder in
       bigstring_output stdout o 0 len
-      ; Def.dst encoder o 0 io_buffer_size |> go
+      ; Def.dst encoder o 0 De.io_buffer_size |> go
     | `End encoder ->
-      let len = io_buffer_size - Def.dst_rem encoder in
+      let len = De.io_buffer_size - Def.dst_rem encoder in
       if len > 0 then bigstring_output stdout o 0 len
       ; `Ok () in
-  Def.dst encoder o 0 io_buffer_size |> go
+  Def.dst encoder o 0 De.io_buffer_size |> go
 
 let run_gzip_inflate () =
   let open Gz in
@@ -156,7 +136,7 @@ let now () =
 let run_gzip_deflate () =
   let open Gz in
   let encoder =
-    Def.encoder `Manual `Manual ~q ~w ~level:0 ~mtime:(now ()) Gz.Unix in
+    Def.encoder `Manual `Manual ~q ~w:l ~level:0 ~mtime:(now ()) Gz.Unix in
 
   let rec go encoder =
     match Def.encode encoder with
diff --git a/fuzz/fuzz.ml b/fuzz/fuzz.ml
index 738cd38..66f5fb1 100644
--- a/fuzz/fuzz.ml
+++ b/fuzz/fuzz.ml
@@ -1,6 +1,7 @@
 open De
 
 let w = make_window ~bits:15
+let l = Lz77.make_window ~bits:15
 let i = bigstring_create io_buffer_size
 let o = bigstring_create io_buffer_size
 let q = Queue.create 4096
@@ -237,7 +238,7 @@ let () =
   Crowbar.add_test ~name:"lz77" [Crowbar.list (non_empty_bytes 1024)]
   @@ fun inputs ->
   Queue.reset q
-  ; let state = Lz77.state `Manual ~w ~q in
+  ; let state = Lz77.state `Manual ~w:l ~q in
     let res = ref [] in
     let rec go inputs =
       match Lz77.compress state with
diff --git a/lib/de.ml b/lib/de.ml
index defe86e..7c31ade 100644
--- a/lib/de.ml
+++ b/lib/de.ml
@@ -2271,10 +2271,12 @@ module Def = struct
         ; e.o_pos <- e.o_pos + 1)
 
     ; if bits + e.bits > 31 then flush (flush_bits ~bits ~hold k) e
-      else if bits > 0 then (
-        e.hold <- ((hold land 0xffff) lsl e.bits) lor e.hold
-        ; e.bits <- e.bits + min bits 16
-        ; flush_bits ~bits:(min 0 (bits - 16)) ~hold:(hold lsr 16) k e)
+      else if bits > 0 then
+        (e.hold <- ((hold land 0xffff) lsl e.bits) lor e.hold
+         ; let len = min bits 16 in
+           e.bits <- e.bits + len
+           ; flush_bits ~bits:(bits - len) ~hold:(hold lsr len) k)
+          e
       else k e
 
   and write e =
@@ -2605,126 +2607,148 @@ module Def = struct
   let encode e = e.k e
 end
 
-module WDef = struct
-  type t = {raw: bigstring; mutable r: int; mutable w: int; mutable c: optint}
-
-  let max = 1 lsl 15
-  let mask = max - 1
-  let ( = ) (a : int) b = a == b
-  let mask v = v land mask
-  let empty t = t.r = t.w
-  let size t = t.w - t.r
-  let available t = max - (t.w - t.r)
-  let is_empty t = empty t
-
-  let[@warning "-32"] make () =
-    {
-      raw= Bigarray.Array1.create Bigarray.char Bigarray.c_layout max
-    ; r= 0
-    ; w= 0
-    ; c= Checkseum.Adler32.default
-    }
-
-  let from raw = {raw; r= 0; w= 0; c= Checkseum.Adler32.default}
-
-  let update w =
-    let c = Checkseum.Adler32.unsafe_digest_bigstring w.raw 0 max w.c in
-    w.c <- c
-
-  let iter t f =
-    let len = size t in
-    let msk = mask t.r in
-    let pre = max - msk in
-    let rst = len - pre in
-
-    if rst > 0 then (
-      for i = 0 to pre - 1 do
-        f (unsafe_get_char t.raw (msk + i))
-      done
-      ; for i = 0 to rst - 1 do
-          f (unsafe_get_char t.raw i)
-        done)
-    else
-      for i = 0 to len - 1 do
-        f (unsafe_get_char t.raw (msk + i))
-      done
-
-  (* XXX(dinosaure): [unsafe_] means that [i] can be out of [r] and [w] - but
-     still is a valid index in [raw]. *)
-  let unsafe_get_char t i = unsafe_get_char t.raw (mask i) [@@inline always]
-  let m = max - 1
-
-  let unsafe_get_uint16 t i =
-    if mask i == m then
-      if Sys.big_endian then
-        (unsafe_get_uint8 t.raw 0 lsl 8) lor unsafe_get_uint8 t.raw m
-      else (unsafe_get_uint8 t.raw m lsl 8) lor unsafe_get_uint8 t.raw 0
-    else unsafe_get_uint16 t.raw (mask i)
-    [@@inline always]
-
-  let unsafe_get_uint8 t i = unsafe_get_uint8 t.raw (mask i) [@@inline always]
-
-  let tail w =
-    let msk = mask w.w in
-    if msk > 0 then (
-      let c = Checkseum.Adler32.unsafe_digest_bigstring w.raw 0 msk w.c in
-      w.w <- 0
-      ; w.r <- 0 (* XXX(dinosaure): reset! *)
-      ; w.c <- c)
-
-  let feed t buf off len =
-    let msk = mask t.w in
-    let pre = max - msk in
-    let rst = len - pre in
-    if rst > 0 then (
-      unsafe_blit buf off t.raw msk pre
-      ; update t
-      ; unsafe_blit buf (off + pre) t.raw 0 rst)
-    else (
-      unsafe_blit buf off t.raw msk len
-      ; if mask (t.w + len) == 0 && len > 0 then update t)
-    ; t.w <- t.w + len
-
-  let junk t len = t.r <- t.r + len
-  let checksum w = w.c
-end
-
 module Lz77 = struct
-  type decode = [ `Await | `Flush | `End ]
-  type src = [ `Channel of in_channel | `String of string | `Manual ]
-
   let _max_match = 258
   let _min_match = 3
-  let _lookahead = _max_match + _min_match + 1
-  let _hash_bits = 15
-  let _hash_shift = (_hash_bits + _min_match - 1) / _min_match
+  let _min_lookahead = _max_match + _min_match + 1
+  let ( .!() ) buf pos = unsafe_get_uint32 buf pos
+  let ( .![] ) buf pos = unsafe_get_uint16 buf pos
+  let ( .!{} ) buf pos = unsafe_get_uint8 buf pos
+
+  type configuration = {
+      max_chain: int
+    ; max_lazy: int
+    ; good_length: int
+    ; nice_length: int
+  }
+
+  let _1 = {good_length= 4; max_lazy= 4; nice_length= 8; max_chain= 4}
+  let _2 = {good_length= 4; max_lazy= 5; nice_length= 16; max_chain= 8}
+  let _3 = {good_length= 4; max_lazy= 6; nice_length= 32; max_chain= 32}
+  let _4 = {good_length= 4; max_lazy= 4; nice_length= 16; max_chain= 16}
+  let _5 = {good_length= 8; max_lazy= 16; nice_length= 32; max_chain= 32}
+  let _6 = {good_length= 8; max_lazy= 16; nice_length= 128; max_chain= 128}
+  let _7 = {good_length= 8; max_lazy= 32; nice_length= 128; max_chain= 256}
+  let _8 = {good_length= 32; max_lazy= 128; nice_length= 258; max_chain= 1024}
+  let _9 = {good_length= 32; max_lazy= 258; nice_length= 258; max_chain= 4096}
+  let _mem_level = 8 (* default *)
+
+  let _hash_bits = _mem_level + 7
   let _hash_size = 1 lsl _hash_bits
   let _hash_mask = _hash_size - 1
+  let _hash_shift = (_hash_bits + _min_match - 1) / _min_match
+  let _too_far = 4096
+  let update_hash hash chr = (hash lsl _hash_shift) lxor chr land _hash_mask
+
+  type src = [ `Channel of in_channel | `String of string | `Manual ]
+  type decode = [ `Await | `Flush | `End ]
 
   type state = {
       src: src
+    ; cfg: configuration
+    ; level: int
     ; mutable i: bigstring
     ; mutable i_pos: int
     ; mutable i_len: int
     ; l: literals
     ; d: distances
-    ; w: WDef.t
-    ; h: int array
-    ; h_msk: int
-    ; b: Queue.t
-    ; mutable k: state -> decode
+    ; w: bigstring
+    ; wbits: int
+    ; mutable lookahead: int
+    ; mutable strstart: int
+    ; prev: int array
+    ; head: int array
+    ; mutable hash: int
+    ; mutable match_start: int
+    ; mutable match_length: int
+    ; mutable match_available: bool
+    ; mutable insert: int
+    ; mutable prev_length: int
+    ; mutable prev_match: int
+    ; q: Queue.t
+    ; mutable crc: optint
+    ; mutable k: configuration -> state -> decode
   }
 
-  let literals s = s.l
-  let distances s = s.d
-  let checksum s = WDef.checksum s.w
+  let max_dist s = (1 lsl s.wbits) - _min_lookahead
+
+  exception Break
+
+  (* cur is the head of the hash chain for the current string
+   * and its distance is <= _max_dist
+   * prev_length >= 1
+   * len >= _min_lookahead *)
+  let longest_match cfg s cur_match =
+    let wmask = (1 lsl s.wbits) - 1 in
+    let str_end = s.strstart + (_max_match - 1) in
+    let limit = if s.strstart > max_dist s then s.strstart - max_dist s else 0 in
+
+    (* Stop when !cur becomes <= limit. To somplify the code,
+     * we prevent matches with the string of window index 0. *)
+    let cur_match = ref cur_match in
+    (* current match *)
+    let chain_length =
+      ref
+        (if s.prev_length >= cfg.good_length then cfg.max_chain asr 2
+        else cfg.max_chain) in
+    (* max hash chain length *)
+    let scan = ref s.strstart in
+    (* current string *)
+    let scan_start = s.w.![s.strstart] in
+    let scan_end = ref s.w.![s.strstart + s.prev_length - 1] in
+    let best_len = ref s.prev_length in
+
+    (* best match length so far *)
+    (try
+       while
+         let match' = ref !cur_match in
+         if
+           s.w.![!match' + !best_len - 1] <> !scan_end
+           || s.w.![!match'] <> scan_start
+         then begin
+           cur_match := s.prev.(!cur_match land wmask)
+           ; decr chain_length
+           ; !cur_match > limit && !chain_length != 0
+         end
+         else begin
+           incr scan
+           ; incr match'
+           ; while !scan < str_end && s.w.!(!scan) = s.w.!(!match') do
+               scan := !scan + 4
+               ; match' := !match' + 4
+             done
+           ; while !scan < str_end && s.w.![!scan] == s.w.![!match'] do
+               scan := !scan + 2
+               ; match' := !match' + 2
+             done
+           ; while !scan < str_end && s.w.!{!scan} == s.w.!{!match'} do
+               scan := !scan + 1
+               ; match' := !match' + 1
+             done
+           ; if s.w.!{!scan} == s.w.!{!match'} then incr scan
+           ; let len = _max_match - 1 - (str_end - !scan) in
+             scan := str_end - (_max_match - 1)
+             ; if len > !best_len then begin
+                 s.match_start <- !cur_match
+                 ; best_len := len
+                 ; if len >= cfg.nice_length then raise Break
+                 ; scan_end := s.w.![!scan + !best_len - 1]
+               end
+             ; cur_match := s.prev.(!cur_match land wmask)
+             ; decr chain_length
+             ; !cur_match > limit && !chain_length != 0
+         end
+       do
+         ()
+       done
+     with Break -> ())
+    ; if !best_len <= s.lookahead then !best_len else s.lookahead
 
   let eoi s =
     s.i <- bigstring_empty
     ; s.i_pos <- 0
     ; s.i_len <- min_int
 
-  (* set [s.i] with [s]. *)
   let src d s j l =
     if j < 0 || l < 0 || j + l > bigstring_length s then invalid_bounds j l
     ; if l == 0 then eoi d
@@ -2733,195 +2757,317 @@ module Lz77 = struct
         ; d.i_pos <- j
         ; d.i_len <- j + l - 1)
 
+  let i_rem s = s.i_len - s.i_pos + 1 [@@inline]
+  let src_rem s = i_rem s
+  let io_buffer_size = 16384
+
   let refill k s =
     match s.src with
-    | `String _ -> eoi s ; k s
+    | `String _ -> eoi s ; k s.cfg s
     | `Channel ic ->
       let res = input_bigstring ic s.i 0 (bigstring_length s.i) in
-      src s s.i 0 res ; k s
+      src s s.i 0 res ; k s.cfg s
     | `Manual ->
       s.k <- k
       ; `Await
 
-  let flush k s =
-    s.k <- k
-    ; `Flush
-
-  (* remaining bytes to read [s.i]. *)
-  let i_rem s = s.i_len - s.i_pos + 1 [@@inline]
-  let src_rem s = i_rem s
-
-  (* XXX(dinoaure): [lt] is not very safe! *)
-
-  let rec nothing s =
-    s.k <- nothing
-    ; `End
+  let memcpy src ~src_off dst ~dst_off ~len =
+    let len0 = len land 3 in
+    let len1 = len asr 2 in
+    for i = 0 to len1 - 1 do
+      let i = i * 4 in
+      let v = unsafe_get_uint32 src (src_off + i) in
+      unsafe_set_uint32 dst (dst_off + i) v
+    done
+    ; for i = 0 to len0 - 1 do
+        let i = (len1 * 4) + i in
+        let v = unsafe_get_uint8 src (src_off + i) in
+        unsafe_set_uint8 dst (dst_off + i) v
+      done
 
-  let rec pending s =
-    let len = min (Queue.available s.b) (WDef.size s.w) in
+  let update_crc s len =
+    s.crc <- Checkseum.Adler32.digest_bigstring s.i s.i_pos len s.crc
 
-    let msk = WDef.mask s.w.r in
-    let pre = WDef.max - msk in
-    let rst = len - pre in
+  let insert_string s str =
+    let wmask = (1 lsl s.wbits) - 1 in
+    s.hash <- update_hash s.hash s.w.!{str + (_min_match - 1)}
+    ; let res = s.head.(s.hash) in
+      s.prev.(str land wmask) <- res
+      ; s.head.(s.hash) <- str
+      ; res
 
-    if rst > 0 then (
-      Queue.blit s.b s.w.raw msk pre
-      ; Queue.blit s.b s.w.raw 0 rst)
-    else Queue.blit s.b s.w.raw msk len
+  let succ_length literals length =
+    literals.(256 + 1 + _length.(length - 3)) <-
+      literals.(256 + 1 + _length.(length - 3)) + 1
 
-    ; WDef.iter s.w (succ_literal s.l)
-    ; WDef.junk s.w len
+  let succ_distance distances distance =
+    distances.(_distance (pred distance)) <-
+      distances.(_distance (pred distance)) + 1
 
-    ; if WDef.is_empty s.w then (
-        WDef.tail s.w
-        ; s.k <- nothing
-        ; `End)
-      else flush pending s
+  let emit_match s ~off ~len =
+    Queue.push_exn s.q (Queue.cmd (`Copy (off, len)))
+    ; succ_length (s.l :> int array) len
+    ; succ_distance (s.d :> int array) off
+    ; if Queue.available s.q = 1 then (
+        Queue.push_exn s.q Queue.eob
+        ; true)
+      else false
+
+  let succ_literal literals chr =
+    literals.(Char.code chr) <- literals.(Char.code chr) + 1
+
+  let emit_literal s chr =
+    Queue.push_exn s.q (Queue.cmd (`Literal chr))
+    ; succ_literal (s.l :> int array) chr
+    ; if Queue.available s.q = 1 then (
+        Queue.push_exn s.q Queue.eob
+        ; true)
+      else false
+
+  (* XXX(dinosaure): it's possible that it remains one literal. *)
+  let trailing s =
+    if s.match_available then (
+      let _ = emit_literal s (unsafe_get_char s.w (s.strstart - 1)) in
+      s.insert <-
+        (if s.strstart < _min_match - 1 then s.strstart else _min_match - 1)
+      ; `End)
+    else `End
+
+  let slide_hash s =
+    let wsize = 1 lsl s.wbits in
+    let m = ref 0 in
+    let n = ref _hash_size in
+    let p = ref !n in
+    while
+      decr p
+      ; m := s.head.(!p)
+      ; s.head.(!p) <- (if !m >= wsize then !m - wsize else 0)
+      ; decr n
+      ; !n != 0
+    do
+      ()
+    done
+    ; n := wsize
+    ; p := !n
+    ; while
+        decr p
+        ; m := s.prev.(!p)
+        ; s.prev.(!p) <- (if !m >= wsize then !m - wsize else 0)
+        ; decr n
+        ; !n != 0
+      do
+        ()
+      done
 
-  let rec fill s =
+  let rec fill_window (cfg : configuration) s =
+    let wsize = 1 lsl s.wbits in
+    let wmask = wsize - 1 in
+    let more = (wsize * 2) - s.lookahead - s.strstart in
+    let deflate =
+      match s.level with 1 | 2 | 3 -> deflate_fast | _ -> deflate_slow in
+    (* max *)
+    let more =
+      if s.strstart >= wsize + max_dist s then begin
+        memcpy s.w ~src_off:wsize s.w ~dst_off:0 ~len:(wsize - more)
+        ; s.match_start <- s.match_start - wsize
+        ; s.strstart <- s.strstart - wsize
+        ; slide_hash s
+        ; more + wsize
+      end
+      else more in
     let rem = i_rem s in
-
-    if rem <= 0 then if rem < 0 then pending s else refill fill s
+    if rem <= 0 (* if (s->strm->avail_in == 0) break; *) then
+      if rem < 0 then if s.lookahead > 0 then deflate cfg s else trailing s
+      else refill fill_window s
     else
-      let len = min (WDef.available s.w) rem in
-      WDef.feed s.w s.i s.i_pos len
-      ; s.i_pos <- s.i_pos + len
-
-      ; let k s = if i_rem s == 0 then refill fill s else fill s in
-
-        (* XXX(dinosaure): optimize this branch. TODO! *)
-        if WDef.size s.w >= 2 then
-          if Queue.available s.b < 2 then flush fill s else deffast k s
-        else refill fill s
-
-  and deffast k s =
-    assert (Queue.available s.b >= 2)
-    ; assert (WDef.size s.w >= 2)
-    ; assert (WDef.size s.w <= WDef.max)
-
-    ; let i = ref s.w.r in
-      let len = ref 0 in
-      let dst = ref 0 in
-
-      let exception Match in
-      let exception Literal in
-      (* XXX(dinosaure): prelude, a [match] is >= 3.  *)
-      let chr = WDef.unsafe_get_char s.w !i in
-      Queue.push_exn s.b (Queue.cmd (`Literal chr))
-      ; incr i
-      ; succ_literal s.l chr
-      ; let chr = WDef.unsafe_get_char s.w !i in
-        Queue.push_exn s.b (Queue.cmd (`Literal (WDef.unsafe_get_char s.w !i)))
-        ; incr i
-        ; succ_literal s.l chr
-
-        ; while s.w.w - !i >= 3 && not (Queue.is_full s.b) do
-            try
-              if
-                WDef.unsafe_get_uint8 s.w !i
-                == WDef.unsafe_get_uint8 s.w (!i - 1)
-                && WDef.unsafe_get_uint16 s.w (!i - 1)
-                   == WDef.unsafe_get_uint16 s.w (!i + 1)
-              then (
-                len := 3
-                ; dst := 1
-                ; raise_notrace Match)
-
-              ; let hash =
-                  let v = WDef.unsafe_get_uint16 s.w !i in
-                  WDef.unsafe_get_uint16 s.w (!i + 1) lxor v in
-                let source = s.h.(hash land s.h_msk) in
-                s.h.(hash land s.h_msk) <- !i
-
-                ; dst := !i - source
-
-                ; (* XXX(dinosaure): should be safe where [!i] is the newest indice in [w]. *)
-                  if
-                    !dst == 0
-                    || !dst >= WDef.max
-                    (* XXX(dinosaure): deliver only valid distance *)
-                    || source + 3 - min_int >= !i - min_int
-                    (* XXX(dinosaure): [source] ∈ no emitted characters *)
-                    || source - min_int < s.w.r - min_int
-                    (* XXX(dinosaure): too old! *)
-                    || WDef.unsafe_get_uint16 s.w !i
-                       <> WDef.unsafe_get_uint16 s.w source
-                    || WDef.unsafe_get_uint16 s.w (!i + 1)
-                       <> WDef.unsafe_get_uint16 s.w (source + 1)
-                  then raise_notrace Literal
-
-                ; len := 3
-
-                ; raise_notrace Match
-            with
-            | Literal ->
-              let chr = WDef.unsafe_get_char s.w !i in
-              Queue.push_exn s.b (Queue.cmd (`Literal chr))
-              ; incr i
-              ; succ_literal s.l chr
-            | Match ->
-              if !dst == 1 then (
-                let vv = WDef.unsafe_get_uint16 s.w !i in
-                let v = WDef.unsafe_get_uint8 s.w !i in
-
-                while
-                  !len + 2 <= _max_match
-                  && s.w.w - (!i + !len + 2) > 0
-                  (* XXX(dinosaure): stay under write cursor. *)
-                  && WDef.unsafe_get_uint16 s.w (!i + !len) == vv
-                do
-                  len := !len + 2
-                done
-
-                ; if
-                    !len + 1 <= _max_match
-                    && s.w.w - (!i + !len + 1) > 0
-                    && WDef.unsafe_get_uint8 s.w (!i + !len) == v
-                  then incr len
-
-                ; Queue.push_exn s.b (Queue.cmd (`Copy (!dst, !len)))
-                ; i := !i + !len
-                ; succ_length s.l !len
-                ; succ_distance s.d !dst)
-              else
-                let source = !i - !dst in
-
-                (* XXX(dinosaure): try to go furthermore. *)
-                while
-                  !len + 2 <= _max_match
-                  && source + !len + 2 - min_int < !i + !len + 2 - min_int
-                  (* XXX(dinosaure): stay outside non-emitted characters. *)
-                  && s.w.w - (!i + !len + 2) > 0
-                  (* XXX(dinosaure): stay under write cursor. *)
-                  && WDef.unsafe_get_uint16 s.w (!i + !len)
-                     == WDef.unsafe_get_uint16 s.w (source + !len)
-                do
-                  len := !len + 2
-                done
-
-                ; if
-                    !len + 1 <= _max_match
-                    && source + !len + 1 - min_int < !i - !len + 1 - min_int
-                    && s.w.w - (!i + !len + 1) > 0
-                    && WDef.unsafe_get_uint8 s.w (!i + !len)
-                       == WDef.unsafe_get_uint8 s.w (source + !len)
-                  then incr len
-
-                ; Queue.push_exn s.b (Queue.cmd (`Copy (!dst, !len)))
-                ; i := !i + !len
-                ; succ_length s.l !len
-                ; succ_distance s.d !dst
+      try
+        let len = min more rem in
+        memcpy s.i ~src_off:s.i_pos s.w ~dst_off:(s.strstart + s.lookahead) ~len
+        ; (*d*) update_crc s len
+        ; s.lookahead <- s.lookahead + len
+        ; (*d*) s.i_pos <- s.i_pos + len
+        ; if s.lookahead + s.insert >= _min_match then begin
+            let str = ref (s.strstart - s.insert) in
+            let insert = ref s.insert in
+            s.hash <- s.w.!{!str}
+            ; s.hash <- update_hash s.hash s.w.!{!str + 1}
+            ; while s.lookahead + !insert >= _min_match && !insert != 0 do
+                s.hash <- update_hash s.hash s.w.!{!str + _min_match - 1}
+                ; s.prev.(!str land wmask) <- s.head.(s.hash)
+                ; s.head.(s.hash) <- !str
+                ; incr str
+                ; decr insert
+                ; if s.lookahead + !insert < _min_match then (
+                    s.insert <- !insert
+                    ; raise Break)
+              done
+            ; s.insert <- !insert
+          end
+        ; if s.lookahead < _min_lookahead && i_rem s >= 0 then
+            refill fill_window s
+          else deflate cfg s
+      with Break -> deflate cfg s
+
+  and enough cfg s =
+    if s.lookahead < _min_lookahead then fill_window cfg s
+    else
+      match s.level with
+      | 1 | 2 | 3 -> deflate_fast cfg s
+      | _ -> deflate_slow cfg s
+
+  and deflate_fast cfg s =
+    let hash_head = ref 0 in
+    let flush = ref false in
+    if s.lookahead >= _min_match then hash_head := insert_string s s.strstart
+    ; if !hash_head != 0 && s.strstart - !hash_head <= max_dist s then
+        s.match_length <- longest_match cfg s !hash_head
+    ; if s.match_length >= _min_match then begin
+        flush :=
+          emit_match s ~off:(s.strstart - s.match_start) ~len:s.match_length
+        ; s.lookahead <- s.lookahead - s.match_length
+        ; if s.match_length <= cfg.max_lazy && s.lookahead >= _min_match then begin
+            s.match_length <- s.match_length - 1
+            ; while
+                s.strstart <- s.strstart + 1
+                ; hash_head := insert_string s s.strstart
+                ; s.match_length <- s.match_length - 1
+                ; s.match_length != 0
+              do
+                ()
+              done
+            ; s.strstart <- s.strstart + 1
+          end
+          else begin
+            s.strstart <- s.strstart + s.match_length
+            ; s.match_length <- 0
+            ; s.hash <- s.w.!{s.strstart}
+            ; s.hash <- update_hash s.hash s.w.!{s.strstart + 1}
+          end
+      end
+      else begin
+        flush := emit_literal s (unsafe_get_char s.w s.strstart)
+        ; s.lookahead <- s.lookahead - 1
+        ; s.strstart <- s.strstart + 1
+      end
+    ; match !flush with
+      | true ->
+        s.k <- enough
+        ; `Flush
+      | false -> enough cfg s
+
+  and deflate_slow cfg s =
+    let hash_head = ref 0 in
+    if s.lookahead >= _min_match then hash_head := insert_string s s.strstart
+    ; s.prev_length <- s.match_length
+    ; s.prev_match <- s.match_start
+    ; s.match_length <- _min_match - 1
+    ; (if
+       !hash_head != 0
+       && s.prev_length < cfg.max_lazy
+       && s.strstart - !hash_head <= max_dist s
+      then
+       let match_length = longest_match cfg s !hash_head in
+       if
+         match_length <= 5
+         && match_length == _min_match
+         && s.strstart - s.match_start > _too_far
+       then s.match_length <- _min_match - 1
+       else s.match_length <- match_length)
+    ; if s.prev_length >= _min_match && s.match_length <= s.prev_length then begin
+        let max_insert = s.strstart + s.lookahead - _min_match in
+        let flush =
+          emit_match s ~off:(s.strstart - 1 - s.prev_match) ~len:s.prev_length
+        in
+        s.lookahead <- s.lookahead - (s.prev_length - 1)
+        ; s.prev_length <- s.prev_length - 2
+        ; while
+            s.strstart <- s.strstart + 1
+            ; if s.strstart <= max_insert then
+                hash_head := insert_string s s.strstart
+            ; s.prev_length <- s.prev_length - 1
+            ; s.prev_length <> 0
+          do
+            ()
           done
-
-        ; WDef.junk s.w (!i - s.w.r)
-
-        ; if Queue.is_full s.b then flush k s
-          else if i_rem s == 0 then refill fill s
-          else k s
-
-  let compress s = s.k s
-
-  let state src ~w ~q =
+        ; s.match_available <- false
+        ; s.match_length <- _min_match - 1
+        ; s.strstart <- s.strstart + 1
+        ; if flush then (
+            s.k <- enough
+            ; `Flush)
+          else enough cfg s
+      end
+      else if s.match_available then begin
+        match emit_literal s (unsafe_get_char s.w (s.strstart - 1)) with
+        | true ->
+          s.strstart <- s.strstart + 1
+          ; s.lookahead <- s.lookahead - 1
+          ; s.k <- enough
+          ; `Flush
+        | false ->
+          s.strstart <- s.strstart + 1
+          ; s.lookahead <- s.lookahead - 1
+          ; enough cfg s
+      end
+      else begin
+        s.match_available <- true
+        ; s.strstart <- s.strstart + 1
+        ; s.lookahead <- s.lookahead - 1
+        ; enough cfg s
+      end
+
+  let _literals = 256
+  let _length_codes = 29
+  let _l_codes = _literals + 1 + _length_codes
+  let _d_codes = 30
+  let checksum {crc; _} = crc
+  let distances {d; _} = d
+  let literals {l; _} = l
+
+  let ctz x =
+    let n = ref 0 and x = ref x and y = ref 0 in
+    if Sys.word_size = 64 then (
+      n := 63
+      ; y := !x lsl 32
+      ; if !y != 0 then (
+          n := !n - 32
+          ; x := !y))
+    else n := 31
+    ; y := !x lsl 16
+    ; if !y != 0 then (
+        n := !n - 16
+        ; x := !y)
+    ; y := !x lsl 8
+    ; if !y != 0 then (
+        n := !n - 8
+        ; x := !y)
+    ; y := !x lsl 4
+    ; if !y != 0 then (
+        n := !n - 4
+        ; x := !y)
+    ; y := !x lsl 2
+    ; if !y != 0 then (
+        n := !n - 2
+        ; x := !y)
+    ; y := !x lsl 1
+    ; if !y != 0 then n := !n - 1
+    ; !n
+
+  let state ?(level = 4) ~q ~w src =
+    let wbits = ctz (bigstring_length w / 2) - 1 in
+    let wsize = 1 lsl wbits in
+    let cfg =
+      match level with
+      | 0 | 1 -> _1
+      | 2 -> _2
+      | 3 -> _3
+      | 4 -> _4
+      | 5 -> _5
+      | 6 -> _6
+      | 7 -> _7
+      | 8 -> _8
+      | 9 -> _9
+      | _ -> invalid_arg "Invalid level of compression: %d" level in
     let i, i_pos, i_len =
       match src with
       | `Manual -> bigstring_empty, 1, 0
@@ -2932,14 +3078,33 @@ module Lz77 = struct
     ; i
     ; i_pos
     ; i_len
+    ; cfg
+    ; level
     ; l= make_literals ()
     ; d= make_distances ()
-    ; w= WDef.from w
-    ; h= Array.make (1 lsl 8) 0
-    ; h_msk= (1 lsl 8) - 1
-    ; b= q
-    ; k= fill
+    ; w
+    ; wbits
+    ; lookahead= 0
+    ; strstart= 0
+    ; prev= Array.make wsize 0
+    ; head= Array.make _hash_size 0
+    ; hash= 0
+    ; match_start= 0
+    ; match_length= 0
+    ; match_available= false
+    ; insert= 0
+    ; prev_length= 0
+    ; prev_match= 0
+    ; q
+    ; crc= Checkseum.Adler32.default
+    ; k= enough
     }
+
+  let compress s = s.k s.cfg s
+
+  type window = bigstring
+
+  let make_window ~bits = bigstring_create ((1 lsl bits) * 2)
 end
 
 module Higher = struct
diff --git a/lib/de.mli b/lib/de.mli
index bdf4b66..461450e 100644
--- a/lib/de.mli
+++ b/lib/de.mli
@@ -388,7 +388,11 @@ module Lz77 : sig
       {- [`End] if [s] compressed all input. Given shared-queue [q] is possibly
      not empty.}} *)
 
-  val state : src -> w:window -> q:Queue.t -> state
+  type window
+
+  val make_window : bits:int -> window
+
+  val state : ?level:int -> q:Queue.t -> w:window -> src -> state
   (** [state src ~w ~q] is an state that inputs from [src] and that outputs to [q].
 
       {b Window.}
diff --git a/lib/dune b/lib/dune
index 2e655d0..fdc89de 100644
--- a/lib/dune
+++ b/lib/dune
@@ -5,6 +5,13 @@
  (ocamlopt_flags -O3 -unbox-closures -unbox-closures-factor 20)
  (libraries checkseum bigarray-compat))
 
+(library
+ (name lz)
+ (public_name decompress.lz)
+ (modules lz)
+ (ocamlopt_flags -O3 -unbox-closures -unbox-closures-factor 20)
+ (libraries de))
+
 (library
  (name rfc1951)
  (public_name rfc1951)
diff --git a/lib/gz.ml b/lib/gz.ml
index 8718ed9..7dfc451 100644
--- a/lib/gz.ml
+++ b/lib/gz.ml
@@ -654,7 +654,7 @@ module Def = struct
     ; q: De.Queue.t
     ; s: De.Lz77.state
     ; e: De.Def.encoder
-    ; w: De.window
+    ; w: De.Lz77.window
     ; state: state
     ; flg: int
     ; xfl: int
diff --git a/lib/gz.mli b/lib/gz.mli
index f4b3871..c7f8025 100644
--- a/lib/gz.mli
+++ b/lib/gz.mli
@@ -185,7 +185,7 @@ module Def : sig
     -> mtime:int32
     -> os
     -> q:De.Queue.t
-    -> w:window
+    -> w:De.Lz77.window
     -> level:int
     -> encoder
   (** [encoder src dst ~mtime os ~q ~w ~level] is an encoder that inputs from
@@ -271,7 +271,7 @@ module Higher : sig
        ?level:int
     -> ?filename:string
     -> ?comment:string
-    -> w:window
+    -> w:De.Lz77.window
     -> q:De.Queue.t
     -> refill:(bigstring -> int)
     -> flush:(bigstring -> int -> unit)
diff --git a/lib/lz.ml b/lib/lz.ml
new file mode 100644
index 0000000..3d3c39d
--- /dev/null
+++ b/lib/lz.ml
@@ -0,0 +1,580 @@
+[@@@landmark "auto"]
+
+module Bigarray = Bigarray_compat (* XXX(dinosaure): MirageOS compatibility. *)
+
+type bigstring =
+  (char, Bigarray.int8_unsigned_elt, Bigarray.c_layout) Bigarray.Array1.t
+
+let bigstring_empty = Bigarray.Array1.create Bigarray.char Bigarray.c_layout 0
+let bigstring_length x = Bigarray.Array1.dim x [@@inline]
+
+let bigstring_create l =
+  Bigarray.Array1.create Bigarray.char Bigarray.c_layout l
+
+let invalid_arg fmt = Format.kasprintf invalid_arg fmt
+
+let invalid_bounds off len =
+  invalid_arg "Out of bounds (off: %d, len: %d)" off len
+
+external unsafe_get_uint8 : bigstring -> int -> int = "%caml_ba_ref_1"
+external unsafe_get_char : bigstring -> int -> char = "%caml_ba_ref_1"
+external unsafe_set_uint8 : bigstring -> int -> int -> unit = "%caml_ba_set_1"
+external unsafe_get_uint16 : bigstring -> int -> int = "%caml_bigstring_get16"
+external unsafe_get_uint32 : bigstring -> int -> int32 = "%caml_bigstring_get32"
+
+external unsafe_set_uint32 : bigstring -> int -> int32 -> unit
+  = "%caml_bigstring_set32"
+
+external bytes_unsafe_get_uint32 : bytes -> int -> int32 = "%caml_bytes_get32"
+
+let bytes_unsafe_get_uint8 : bytes -> int -> int =
+ fun buf off -> Char.code (Bytes.get buf off)
+
+let input_bigstring ic buf off len =
+  let tmp = Bytes.create len in
+  let res = input ic tmp 0 len in
+
+  let len0 = res land 3 in
+  let len1 = res asr 2 in
+
+  for i = 0 to len1 - 1 do
+    let i = i * 4 in
+    let v = bytes_unsafe_get_uint32 tmp i in
+    unsafe_set_uint32 buf (off + i) v
+  done
+
+  ; for i = 0 to len0 - 1 do
+      let i = (len1 * 4) + i in
+      let v = bytes_unsafe_get_uint8 tmp i in
+      unsafe_set_uint8 buf (off + i) v
+    done
+  ; res
+
+external string_unsafe_get_uint32 : string -> int -> int32
+  = "%caml_string_get32"
+
+let string_unsafe_get_uint8 : string -> int -> int =
+ fun buf off -> Char.code buf.[off]
+
+let bigstring_of_string v =
+  let len = String.length v in
+  let res = bigstring_create len in
+  let len0 = len land 3 in
+  let len1 = len asr 2 in
+
+  for i = 0 to len1 - 1 do
+    let i = i * 4 in
+    let v = string_unsafe_get_uint32 v i in
+    unsafe_set_uint32 res i v
+  done
+
+  ; for i = 0 to len0 - 1 do
+      let i = (len1 * 4) + i in
+      let v = string_unsafe_get_uint8 v i in
+      unsafe_set_uint8 res i v
+    done
+  ; res
+
+let _length =
+  [|
+     0; 1; 2; 3; 4; 5; 6; 7; 8; 8; 9; 9; 10; 10; 11; 11; 12; 12; 12; 12; 13; 13
+   ; 13; 13; 14; 14; 14; 14; 15; 15; 15; 15; 16; 16; 16; 16; 16; 16; 16; 16; 17
+   ; 17; 17; 17; 17; 17; 17; 17; 18; 18; 18; 18; 18; 18; 18; 18; 19; 19; 19; 19
+   ; 19; 19; 19; 19; 20; 20; 20; 20; 20; 20; 20; 20; 20; 20; 20; 20; 20; 20; 20
+   ; 20; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 21; 22; 22
+   ; 22; 22; 22; 22; 22; 22; 22; 22; 22; 22; 22; 22; 22; 22; 23; 23; 23; 23; 23
+   ; 23; 23; 23; 23; 23; 23; 23; 23; 23; 23; 23; 24; 24; 24; 24; 24; 24; 24; 24
+   ; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24
+   ; 24; 24; 24; 24; 24; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25
+   ; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 25; 26
+   ; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26
+   ; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 27; 27; 27; 27; 27; 27; 27
+   ; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27
+   ; 27; 27; 27; 27; 27; 28
+  |]
+
+let _distance =
+  [|
+     0; 1; 2; 3; 4; 4; 5; 5; 6; 6; 6; 6; 7; 7; 7; 7; 8; 8; 8; 8; 8; 8; 8; 8; 9; 9
+   ; 9; 9; 9; 9; 9; 9; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10
+   ; 10; 10; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 12
+   ; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12
+   ; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 13; 13; 13; 13; 13; 13; 13
+   ; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13
+   ; 13; 13; 13; 13; 13; 13; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14
+   ; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14
+   ; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14
+   ; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 15; 15; 15; 15; 15; 15
+   ; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15
+   ; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15
+   ; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15; 15
+   ; 15; 0; 0; 16; 17; 18; 18; 19; 19; 20; 20; 20; 20; 21; 21; 21; 21; 22; 22
+   ; 22; 22; 22; 22; 22; 22; 23; 23; 23; 23; 23; 23; 23; 23; 24; 24; 24; 24; 24
+   ; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 24; 25; 25; 25; 25; 25; 25; 25; 25
+   ; 25; 25; 25; 25; 25; 25; 25; 25; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26
+   ; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26; 26
+   ; 26; 26; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27
+   ; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 27; 28; 28; 28; 28
+   ; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28
+   ; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28
+   ; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28; 28
+   ; 28; 28; 28; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29
+   ; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29
+   ; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29
+   ; 29; 29; 29; 29; 29; 29; 29; 29; 29; 29
+  |]
+
+let _distance code =
+  if code < 256 then _distance.(code) else _distance.(256 + (code lsr 7))
+  [@@inline]
+
+let _max_match = 258
+let _min_match = 3
+let _min_lookahead = _max_match + _min_match + 1
+let ( .!() ) buf pos = unsafe_get_uint32 buf pos
+let ( .![] ) buf pos = unsafe_get_uint16 buf pos
+let ( .!{} ) buf pos = unsafe_get_uint8 buf pos
+
+type configuration = {
+    max_chain: int
+  ; max_lazy: int
+  ; good_length: int
+  ; nice_length: int
+}
+
+let _4 = {good_length= 4; max_lazy= 4; nice_length= 16; max_chain= 16}
+let _5 = {good_length= 8; max_lazy= 16; nice_length= 32; max_chain= 32}
+let _6 = {good_length= 8; max_lazy= 16; nice_length= 128; max_chain= 128}
+let _7 = {good_length= 8; max_lazy= 32; nice_length= 128; max_chain= 256}
+let _8 = {good_length= 32; max_lazy= 128; nice_length= 258; max_chain= 1024}
+let _9 = {good_length= 32; max_lazy= 258; nice_length= 258; max_chain= 4096}
+let _mem_level = 8 (* default *)
+
+let _hash_bits = _mem_level + 7
+let _hash_size = 1 lsl _hash_bits
+let _hash_mask = _hash_size - 1
+let _hash_shift = (_hash_bits + _min_match - 1) / _min_match
+let _too_far = 4096
+let update_hash hash chr = (hash lsl _hash_shift) lxor chr land _hash_mask
+
+type src = [ `Channel of in_channel | `String of string | `Manual ]
+type decode = [ `Await | `Flush | `End ]
+type literals = De.literals
+type distances = De.distances
+type optint = Optint.t
+
+type state = {
+    src: src
+  ; cfg: configuration
+  ; mutable i: bigstring
+  ; mutable i_pos: int
+  ; mutable i_len: int
+  ; l: literals
+  ; d: distances
+  ; w: bigstring
+  ; wbits: int
+  ; mutable lookahead: int
+  ; mutable strstart: int
+  ; prev: int array
+  ; head: int array
+  ; mutable hash: int
+  ; mutable match_start: int
+  ; mutable match_length: int
+  ; mutable match_available: bool
+  ; mutable insert: int
+  ; mutable prev_length: int
+  ; mutable prev_match: int
+  ; q: De.Queue.t
+  ; mutable crc: optint
+  ; mutable k: configuration -> state -> decode
+}
+
+let max_dist s = (1 lsl s.wbits) - _min_lookahead
+
+exception Break
+
+(* cur is the head of the hash chain for the current string
+ * and its distance is <= _max_dist
+ * prev_length >= 1
+ * len >= _min_lookahead *)
+let longest_match cfg s cur_match =
+  let wsize = 1 lsl s.wbits in
+  let wmask = wsize - 1 in
+  let str_end = s.strstart + (_max_match - 1) in
+  let limit = if s.strstart > max_dist s then s.strstart - max_dist s else 0 in
+
+  (* Stop when !cur becomes <= limit. To somplify the code,
+   * we prevent matches with the string of window index 0. *)
+  let cur_match = ref cur_match in
+  (* current match *)
+  let chain_length =
+    ref
+      (if s.prev_length >= cfg.good_length then cfg.max_chain asr 2
+      else cfg.max_chain) in
+  (* max hash chain length *)
+  let scan = ref s.strstart in
+  (* current string *)
+  let scan_start = s.w.![s.strstart] in
+  let scan_end = ref s.w.![s.strstart + s.prev_length - 1] in
+  let best_len = ref s.prev_length in
+
+  (* best match length so far *)
+  (try
+     while
+       let match' = ref !cur_match in
+       if
+         s.w.![!match' + !best_len - 1] <> !scan_end
+         || s.w.![!match'] <> scan_start
+       then begin
+         cur_match := s.prev.(!cur_match land wmask)
+         ; decr chain_length
+         ; !cur_match > limit && !chain_length != 0
+       end
+       else begin
+         incr scan
+         ; incr match'
+         ; while !scan < str_end && s.w.!(!scan) = s.w.!(!match') do
+             scan := !scan + 4
+             ; match' := !match' + 4
+           done
+         ; while !scan < str_end && s.w.![!scan] == s.w.![!match'] do
+             scan := !scan + 2
+             ; match' := !match' + 2
+           done
+         ; while !scan < str_end && s.w.!{!scan} == s.w.!{!match'} do
+             scan := !scan + 1
+             ; match' := !match' + 1
+           done
+         ; if s.w.!{!scan} == s.w.!{!match'} then incr scan
+         ; let len = _max_match - 1 - (str_end - !scan) in
+           scan := str_end - (_max_match - 1)
+           ; if len > !best_len then begin
+               s.match_start <- !cur_match
+               ; best_len := len
+               ; if len >= cfg.nice_length then raise Break
+               ; scan_end := s.w.![!scan + !best_len - 1]
+             end
+           ; cur_match := s.prev.(!cur_match land wmask)
+           ; decr chain_length
+           ; !cur_match > limit && !chain_length != 0
+       end
+     do
+       ()
+     done
+   with Break -> ())
+  ; if !best_len <= s.lookahead then !best_len else s.lookahead
+
+let eoi s =
+  s.i <- bigstring_empty
+  ; s.i_pos <- 0
+  ; s.i_len <- min_int
+
+let src d s j l =
+  if j < 0 || l < 0 || j + l > bigstring_length s then invalid_bounds j l
+  ; if l == 0 then eoi d
+    else (
+      d.i <- s
+      ; d.i_pos <- j
+      ; d.i_len <- j + l - 1)
+
+let i_rem s = s.i_len - s.i_pos + 1 [@@inline]
+let src_rem s = i_rem s
+let io_buffer_size = 16384
+
+let refill k s =
+  match s.src with
+  | `String _ -> eoi s ; k s.cfg s
+  | `Channel ic ->
+    let res = input_bigstring ic s.i 0 (bigstring_length s.i) in
+    src s s.i 0 res ; k s.cfg s
+  | `Manual ->
+    s.k <- k
+    ; `Await
+
+let memcpy src ~src_off dst ~dst_off ~len =
+  let len0 = len land 3 in
+  let len1 = len asr 2 in
+  for i = 0 to len1 - 1 do
+    let i = i * 4 in
+    let v = unsafe_get_uint32 src (src_off + i) in
+    unsafe_set_uint32 dst (dst_off + i) v
+  done
+  ; for i = 0 to len0 - 1 do
+      let i = (len1 * 4) + i in
+      let v = unsafe_get_uint8 src (src_off + i) in
+      unsafe_set_uint8 dst (dst_off + i) v
+    done
+
+let update_crc s len =
+  s.crc <- Checkseum.Adler32.digest_bigstring s.i s.i_pos len s.crc
+
+let insert_string s str =
+  let wsize = 1 lsl s.wbits in
+  let wmask = wsize - 1 in
+  s.hash <- update_hash s.hash s.w.!{str + (_min_match - 1)}
+  ; let res = s.head.(s.hash) in
+    s.prev.(str land wmask) <- res
+    ; s.head.(s.hash) <- str
+    ; res
+
+let succ_length literals length =
+  assert (length >= 3 && length <= 255 + 3)
+  ; literals.(256 + 1 + _length.(length - 3)) <-
+      literals.(256 + 1 + _length.(length - 3)) + 1
+
+let succ_distance distances distance =
+  assert (distance >= 1 && distance <= 32767 + 1)
+  ; distances.(_distance (pred distance)) <-
+      distances.(_distance (pred distance)) + 1
+
+let emit_match s ~off ~len =
+  De.Queue.push_exn s.q (De.Queue.cmd (`Copy (off, len)))
+  ; succ_length (s.l :> int array) len
+  ; succ_distance (s.d :> int array) off
+  ; if De.Queue.available s.q = 1 then (
+      De.Queue.push_exn s.q De.Queue.eob
+      ; true)
+    else false
+
+let succ_literal literals chr =
+  literals.(Char.code chr) <- literals.(Char.code chr) + 1
+
+let emit_literal s chr =
+  De.Queue.push_exn s.q (De.Queue.cmd (`Literal chr))
+  ; succ_literal (s.l :> int array) chr
+  ; if De.Queue.available s.q = 1 then (
+      De.Queue.push_exn s.q De.Queue.eob
+      ; true)
+    else false
+
+(* XXX(dinosaure): it's possible that it remains one literal. *)
+let trailing s =
+  if s.match_available then (
+    let _ = emit_literal s (unsafe_get_char s.w (s.strstart - 1)) in
+    s.insert <-
+      (if s.strstart < _min_match - 1 then s.strstart else _min_match - 1)
+    ; `End)
+  else `End
+
+let slide_hash s =
+  let wsize = 1 lsl s.wbits in
+  let m = ref 0 in
+  let n = ref _hash_size in
+  let p = ref !n in
+  while
+    decr p
+    ; m := s.head.(!p)
+    ; s.head.(!p) <- (if !m >= wsize then !m - wsize else 0)
+    ; decr n
+    ; !n != 0
+  do
+    ()
+  done
+  ; n := wsize
+  ; p := !n
+  ; while
+      decr p
+      ; m := s.prev.(!p)
+      ; s.prev.(!p) <- (if !m >= wsize then !m - wsize else 0)
+      ; decr n
+      ; !n != 0
+    do
+      ()
+    done
+
+let rec fill_window (cfg : configuration) s =
+  let wsize = 1 lsl s.wbits in
+  let wmask = wsize - 1 in
+  let more = (wsize * 2) - s.lookahead - s.strstart in
+  (* max *)
+  let more =
+    if s.strstart >= wsize + max_dist s then begin
+      memcpy s.w ~src_off:wsize s.w ~dst_off:0 ~len:(wsize - more)
+      ; s.match_start <- s.match_start - wsize
+      ; s.strstart <- s.strstart - wsize
+      ; slide_hash s
+      ; more + wsize
+    end
+    else more in
+  let rem = i_rem s in
+  if rem <= 0 (* if (s->strm->avail_in == 0) break; *) then
+    if rem < 0 then if s.lookahead > 0 then deflate_slow cfg s else trailing s
+    else refill fill_window s
+  else
+    try
+      let len = min more rem in
+      memcpy s.i ~src_off:s.i_pos s.w ~dst_off:(s.strstart + s.lookahead) ~len
+      ; (*d*) update_crc s len
+      ; s.lookahead <- s.lookahead + len
+      ; (*d*) s.i_pos <- s.i_pos + len
+      ; if s.lookahead + s.insert >= _min_match then begin
+          let str = ref (s.strstart - s.insert) in
+          let insert = ref s.insert in
+          s.hash <- s.w.!{!str}
+          ; s.hash <- update_hash s.hash s.w.!{!str + 1}
+          ; while s.lookahead + !insert >= _min_match && !insert != 0 do
+              s.hash <- update_hash s.hash s.w.!{!str + _min_match - 1}
+              ; s.prev.(!str land wmask) <- s.head.(s.hash)
+              ; s.head.(s.hash) <- !str
+              ; incr str
+              ; decr insert
+              ; if s.lookahead + !insert < _min_match then (
+                  s.insert <- !insert
+                  ; raise Break)
+            done
+          ; s.insert <- !insert
+        end
+      ; if s.lookahead < _min_lookahead && i_rem s >= 0 then
+          refill fill_window s
+        else deflate_slow cfg s
+    with Break -> deflate_slow cfg s
+
+and enough cfg s =
+  if s.lookahead < _min_lookahead then fill_window cfg s else deflate_slow cfg s
+
+and deflate_slow cfg s =
+  let hash_head = ref 0 in
+  if s.lookahead >= _min_match then hash_head := insert_string s s.strstart
+  ; s.prev_length <- s.match_length
+  ; s.prev_match <- s.match_start
+  ; s.match_length <- _min_match - 1
+  ; (if
+     !hash_head != 0
+     && s.prev_length < cfg.max_lazy
+     && s.strstart - !hash_head <= max_dist s
+    then
+     let match_length = longest_match cfg s !hash_head in
+     if
+       match_length <= 5
+       && match_length == _min_match
+       && s.strstart - s.match_start > _too_far
+     then s.match_length <- _min_match - 1
+     else s.match_length <- match_length)
+  ; if s.prev_length >= _min_match && s.match_length <= s.prev_length then begin
+      let max_insert = s.strstart + s.lookahead - _min_match in
+      let flush =
+        emit_match s ~off:(s.strstart - 1 - s.prev_match) ~len:s.prev_length
+      in
+      s.lookahead <- s.lookahead - (s.prev_length - 1)
+      ; s.prev_length <- s.prev_length - 2
+      ; while
+          s.strstart <- s.strstart + 1
+          ; if s.strstart <= max_insert then
+              hash_head := insert_string s s.strstart
+          ; s.prev_length <- s.prev_length - 1
+          ; s.prev_length <> 0
+        do
+          ()
+        done
+      ; s.match_available <- false
+      ; s.match_length <- _min_match - 1
+      ; s.strstart <- s.strstart + 1
+      ; if flush then (
+          s.k <- enough
+          ; `Flush)
+        else enough cfg s
+    end
+    else if s.match_available then begin
+      match emit_literal s (unsafe_get_char s.w (s.strstart - 1)) with
+      | true ->
+        s.strstart <- s.strstart + 1
+        ; s.lookahead <- s.lookahead - 1
+        ; s.k <- enough
+        ; `Flush
+      | false ->
+        s.strstart <- s.strstart + 1
+        ; s.lookahead <- s.lookahead - 1
+        ; enough cfg s
+    end
+    else begin
+      s.match_available <- true
+      ; s.strstart <- s.strstart + 1
+      ; s.lookahead <- s.lookahead - 1
+      ; enough cfg s
+    end
+
+let _literals = 256
+let _length_codes = 29
+let _l_codes = _literals + 1 + _length_codes
+let _d_codes = 30
+let checksum {crc; _} = crc
+let distances {d; _} = d
+let literals {l; _} = l
+
+let ctz x =
+  let n = ref 0 and x = ref x and y = ref 0 in
+  if Sys.word_size = 64 then (
+    n := 63
+    ; y := !x lsl 32
+    ; if !y != 0 then (
+        n := !n - 32
+        ; x := !y))
+  else n := 31
+  ; y := !x lsl 16
+  ; if !y != 0 then (
+      n := !n - 16
+      ; x := !y)
+  ; y := !x lsl 8
+  ; if !y != 0 then (
+      n := !n - 8
+      ; x := !y)
+  ; y := !x lsl 4
+  ; if !y != 0 then (
+      n := !n - 4
+      ; x := !y)
+  ; y := !x lsl 2
+  ; if !y != 0 then (
+      n := !n - 2
+      ; x := !y)
+  ; y := !x lsl 1
+  ; if !y != 0 then n := !n - 1
+  ; !n
+
+let state ?(level = 4) ~q ~w src =
+  let wbits = ctz (bigstring_length w / 2) - 1 in
+  let wsize = 1 lsl wbits in
+  let cfg =
+    match level with
+    | 0 | 1 | 2 | 3 | 4 -> _4
+    | 5 -> _5
+    | 6 -> _6
+    | 7 -> _7
+    | 8 -> _8
+    | 9 -> _9
+    | _ -> invalid_arg "Invalid compression level: %d" level in
+  let i, i_pos, i_len =
+    match src with
+    | `Manual -> bigstring_empty, 1, 0
+    | `String x -> bigstring_of_string x, 0, String.length x - 1
+    | `Channel _ -> bigstring_create io_buffer_size, 1, 0 in
+  {
+    src
+  ; i
+  ; i_pos
+  ; i_len
+  ; cfg
+  ; l= De.make_literals ()
+  ; d= De.make_distances ()
+  ; w
+  ; wbits
+  ; lookahead= 0
+  ; strstart= 0
+  ; prev= Array.make wsize 0
+  ; head= Array.make _hash_size 0
+  ; hash= 0
+  ; match_start= 0
+  ; match_length= _min_match - 1
+  ; match_available= false
+  ; insert= 0
+  ; prev_length= _min_match - 1
+  ; prev_match= 0
+  ; q
+  ; crc= Checkseum.Adler32.default
+  ; k= enough
+  }
+
+let compress s = s.k s.cfg s
+
+type window = bigstring
+
+let make_window ~bits = bigstring_create ((1 lsl bits) * 2)
diff --git a/lib/lz.mli b/lib/lz.mli
new file mode 100644
index 0000000..4f0b3ff
--- /dev/null
+++ b/lib/lz.mli
@@ -0,0 +1,21 @@
+module Bigarray = Bigarray_compat
+
+type bigstring =
+  (char, Bigarray.int8_unsigned_elt, Bigarray.c_layout) Bigarray.Array1.t
+
+type optint = Optint.t
+type src = [ `Channel of in_channel | `String of string | `Manual ]
+type decode = [ `Flush | `Await | `End ]
+type state
+type literals = De.literals
+type distances = De.distances
+type window
+
+val literals : state -> literals
+val distances : state -> distances
+val checksum : state -> optint
+val src : state -> bigstring -> int -> int -> unit
+val src_rem : state -> int
+val make_window : bits:int -> window
+val compress : state -> decode
+val state : ?level:int -> q:De.Queue.t -> w:window -> src -> state
diff --git a/lib/zl.ml b/lib/zl.ml
index 65eb5e2..db27623 100644
--- a/lib/zl.ml
+++ b/lib/zl.ml
@@ -376,6 +376,7 @@ module Def = struct
       src: src
     ; dst: dst
     ; level: int
+    ; dynamic: bool
     ; i: bigstring
     ; i_pos: int
     ; i_len: int
@@ -385,7 +386,7 @@ module Def = struct
     ; q: De.Queue.t
     ; s: De.Lz77.state
     ; e: De.Def.encoder
-    ; w: De.window
+    ; w: De.Lz77.window
     ; state: state
     ; k: encoder -> [ `Await of encoder | `Flush of encoder | `End of encoder ]
   }
@@ -447,7 +448,7 @@ module Def = struct
     if o_rem e >= 4 then k e else flush checksum e
 
   let make_block ?(last = false) e =
-    if last = false then
+    if last = false && e.dynamic then
       let literals = De.Lz77.literals e.s in
       let distances = De.Lz77.distances e.s in
       let dynamic = De.Def.dynamic_of_frequencies ~literals ~distances in
@@ -458,7 +459,8 @@ module Def = struct
     match e.state with
     | Hd ->
       let k e =
-        let header = (_deflated + ((De.window_bits e.w - 8) lsl 4)) lsl 8 in
+        let window_bits = 15 in
+        let header = (_deflated + ((window_bits - 8) lsl 4)) lsl 8 in
         let header = header lor (e.level lsl 6) in
         let header = header + (31 - (header mod 31)) in
         unsafe_set_uint16_be e.o e.o_pos header
@@ -502,7 +504,7 @@ module Def = struct
   let src_rem = i_rem
   let dst_rem = o_rem
 
-  let encoder src dst ~q ~w ~level =
+  let encoder ?(dynamic = true) ~q ~w ~level src dst =
     let i, i_pos, i_len =
       match src with
       | `Manual -> bigstring_empty, 1, 0
@@ -513,33 +515,32 @@ module Def = struct
       | `Manual -> bigstring_empty, 1, 0
       | `Buffer _ | `Channel _ ->
         bigstring_create io_buffer_size, 0, io_buffer_size - 1 in
-    if level < 0 || level > 3 then
-      invalid_arg "Invalid compression level %d (must be in the range 0...3)"
-        level
-    ; {
-        src
-      ; dst
-      ; i
-      ; i_pos
-      ; i_len
-      ; o
-      ; o_pos
-      ; o_len
-      ; level
-      ; e= De.Def.encoder `Manual ~q
-      ; s= De.Lz77.state `Manual ~q ~w
-      ; q
-      ; w
-      ; state= Hd
-      ; k= encode
-      }
+    {
+      src
+    ; dst
+    ; i
+    ; i_pos
+    ; i_len
+    ; o
+    ; o_pos
+    ; o_len
+    ; level=
+        (match level with 0 | 1 -> 0 | 2 | 3 | 4 | 5 -> 1 | 6 -> 2 | _ -> 3)
+    ; dynamic
+    ; e= De.Def.encoder `Manual ~q
+    ; s= De.Lz77.state ~level `Manual ~q ~w
+    ; q
+    ; w
+    ; state= Hd
+    ; k= encode
+    }
 
   let encode e = e.k e
 end
 
 module Higher = struct
-  let compress ?(level = 0) ~w ~q ~refill ~flush i o =
-    let encoder = Def.encoder `Manual `Manual ~q ~w ~level in
+  let compress ?(level = 6) ?dynamic ~w ~q ~refill ~flush i o =
+    let encoder = Def.encoder `Manual `Manual ?dynamic ~q ~w ~level in
     let rec go encoder =
       match Def.encode encoder with
       | `Await encoder ->
diff --git a/lib/zl.mli b/lib/zl.mli
index f74b13b..71bfd65 100644
--- a/lib/zl.mli
+++ b/lib/zl.mli
@@ -138,8 +138,15 @@ module Def : sig
 
   type ret = [ `Await of encoder | `End of encoder | `Flush of encoder ]
 
-  val encoder : src -> dst -> q:De.Queue.t -> w:window -> level:int -> encoder
-  (** [encoder src dst ~q ~w ~level] is an encoder that inputs from [src] and
+  val encoder :
+       ?dynamic:bool
+    -> q:De.Queue.t
+    -> w:De.Lz77.window
+    -> level:int
+    -> src
+    -> dst
+    -> encoder
+  (** [encoder ~q ~w ~level src dst] is an encoder that inputs from [src] and
      that outputs to [dst].
 
       {b Internal queue.}
@@ -201,7 +208,8 @@ end
 module Higher : sig
   val compress :
        ?level:int
-    -> w:window
+    -> ?dynamic:bool
+    -> w:De.Lz77.window
     -> q:De.Queue.t
     -> refill:(bigstring -> int)
     -> flush:(bigstring -> int -> unit)


Test patch:
diff --git a/test/.ocamlformat b/test/.ocamlformat
deleted file mode 100644
index c753b8d..0000000
--- a/test/.ocamlformat
+++ /dev/null
@@ -1,1 +0,0 @@
-break-collection-expressions=fit-or-vertical
diff --git a/test/dune b/test/dune
index 07193cf..bcac898 100644
--- a/test/dune
+++ b/test/dune
@@ -4,6 +4,20 @@
  (libraries base64 camlzip hxd.string bigstringaf checkseum.c de zl gz lzo
    alcotest))
 
+(executable
+ (name test_deflate)
+ (modules test_deflate)
+ (libraries de bigstringaf alcotest))
+
+(rule
+ (alias runtest)
+ (package decompress)
+ (deps
+  (:test test_deflate.exe)
+  (source_tree corpus))
+ (action
+  (run %{test} --color=always)))
+
 (rule
  (alias runtest)
  (package decompress)
diff --git a/test/test.ml b/test/test.ml
index 2e4ff51..5f598ea 100644
--- a/test/test.ml
+++ b/test/test.ml
@@ -18,6 +18,7 @@ let random len =
 open De (* au detail *)
 
 let w = make_window ~bits:15
+let l = Lz77.make_window ~bits:15
 let i = bigstring_create io_buffer_size
 let o = bigstring_create io_buffer_size
 let q = Queue.create 4096
@@ -314,8 +315,7 @@ let fuzz2 () =
     ; "\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e"
       (* ~~~~~~~~~~~~~~~~ *)
     ; "\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e"
-      (* ~~~~~~~~~~~~~~~~ *)
-    ; "\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x3a\x2c\x50"
+      (* ~~~~~~~~~~~~~~~~ *); "\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x7e\x3a\x2c\x50"
       (* ~~~~~~~~:,P *)
     ] in
   Alcotest.test_case "fuzz2" `Quick @@ fun () ->
@@ -365,9 +365,7 @@ let fuzz3 () =
     ; "\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76"
       (* .v.v.v.v.v.v.v.v *)
     ; "\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76\xc8\x76"
-      (* .v.v.v.v.v.v.v.v *)
-    ; "\xc8\x76\xc8\x76"
-      (* .v.v *)
+      (* .v.v.v.v.v.v.v.v *); "\xc8\x76\xc8\x76" (* .v.v *)
     ] in
   Alcotest.test_case "fuzz3" `Quick @@ fun () ->
   let decoder =
@@ -384,9 +382,7 @@ let fuzz4 () =
     ; "\xca\x7e\x1a\xca\x7e\x1a\xca\x7e\x1a\xca\x7e\x1a\xca\x7e\x1a\xca"
       (* .~..~..~..~..~.. *)
     ; "\x7e\x1a\xca\x7e\x1a\xca\x7e\x1a\xca\x7e\x1a\xca\x7e\x1a\xca\x7e"
-      (* ~..~..~..~..~..~ *)
-    ; "\xc8\x76\x75\x75\x75\x75\x75\x75"
-      (* .vuuuuuu *)
+      (* ~..~..~..~..~..~ *); "\xc8\x76\x75\x75\x75\x75\x75\x75" (* .vuuuuuu *)
     ] in
   Alcotest.test_case "fuzz4" `Quick @@ fun () ->
   let decoder =
@@ -399,15 +395,12 @@ let fuzz5 () =
   let input =
     [
       "\x93\x3a\x55\x01\x01\x01\x01\xe6\x01\x01\x01\x01\x01\x01\x01\x01"
-      (* .:U............. *)
-    ; "\x01\x01\x01\x01\x01\x00\x00"
-      (* ....... *)
+      (* .:U............. *); "\x01\x01\x01\x01\x01\x00\x00" (* ....... *)
     ] in
   let expected_output =
     [
       "\x1a\xca\x78\x78\x78\x78\x78\x78\x78\x50\x50\x37\x50\x50\x50\x50"
-      (* ..xxxxxxxPP7PPPP *)
-    ; "\x50\x50\x50\x50\x50\x50\x50\x50\x50"
+      (* ..xxxxxxxPP7PPPP *); "\x50\x50\x50\x50\x50\x50\x50\x50\x50"
       (* PPPPPPPPP *)
     ] in
   Alcotest.test_case "fuzz5" `Quick @@ fun () ->
@@ -419,9 +412,7 @@ let fuzz6 () =
   let expected_output =
     [
       "\x19\x59\x59\x59\x5e\xe3\x59\x5e\xe3\x59\x5e\xe3\x59\x5e\xe3\x59"
-      (* .YYY^.Y^.Y^.Y^.Y *)
-    ; "\x5e\xe3\x33"
-      (* ^.3 *)
+      (* .YYY^.Y^.Y^.Y^.Y *); "\x5e\xe3\x33" (* ^.3 *)
     ] in
   Alcotest.test_case "fuzz6" `Quick @@ fun () ->
   let decoder =
@@ -466,8 +457,7 @@ let fuzz9 () =
       "\x9b\x01\x95\xfc\x51\xd2\xed\xc8\xce\xc8\xff\x80\x00\x00\x7f\xff"
       (* ....Q........... *)
     ; "\x79\x2f\xe9\x51\x88\x7b\xb8\x2f\xef\xa5\x8c\xf8\xf1\xb6\xce\xc8"
-      (* y/.Q.{./........ *)
-    ; "\xb8\xc8\xff\x2f\x00\x7f\x88\x7b\xbc"
+      (* y/.Q.{./........ *); "\xb8\xc8\xff\x2f\x00\x7f\x88\x7b\xbc"
       (* .../...{. *)
     ] in
   let decoder = Inf.decoder (`String (String.concat "" inputs)) ~o ~w in
@@ -488,10 +478,7 @@ let huffman_length_extra () =
       let res =
         encode ~block:(Def.Dynamic dynamic)
           [
-            `Literal '\000'
-          ; `Literal '\000'
-          ; `Copy (1, 258)
-          ; `Copy (1, 256)
+            `Literal '\000'; `Literal '\000'; `Copy (1, 258); `Copy (1, 256)
           ; `End
           ] in
       Alcotest.(check str)
@@ -505,11 +492,8 @@ let fuzz10 () =
   Alcotest.test_case "fuzz10" `Quick @@ fun () ->
   let lst =
     [
-      `Literal (Char.chr 231)
-    ; `Literal (Char.chr 60)
-    ; `Literal (Char.chr 128)
-    ; `Copy (1, 19)
-    ; `End
+      `Literal (Char.chr 231); `Literal (Char.chr 60); `Literal (Char.chr 128)
+    ; `Copy (1, 19); `End
     ] in
   let res = encode_dynamic lst in
   let decoder = Inf.decoder (`String res) ~o ~w in
@@ -536,11 +520,8 @@ let fuzz12 () =
   Alcotest.test_case "fuzz12" `Quick @@ fun () ->
   let lst =
     [
-      `Literal (Char.chr 71)
-    ; `Literal (Char.chr 0)
-    ; `Literal (Char.chr 255)
-    ; `Copy (2, 249)
-    ; `End
+      `Literal (Char.chr 71); `Literal (Char.chr 0); `Literal (Char.chr 255)
+    ; `Copy (2, 249); `End
     ] in
   let res = encode_dynamic lst in
   let decoder = Inf.decoder (`String res) ~o ~w in
@@ -596,8 +577,7 @@ let fuzz14 () =
       "\x0b\xff\x7f\x0c\x0c\x8f\xcd\x0e\x02\x21\x64\x0c\x04\x73\xff\x80"
       (* .........!d..s.. *)
     ; "\x20\x0c\x8f\x1c\x1c\x1c\x1c\x0c\x0c\x0c\x0c\x64\x1c\x7f\x0c\x0c"
-      (*  ..........d.... *)
-    ; "\x8f\xcd\x0e\x02\x21\xff\xff\x80" (* ....!... *)
+      (*  ..........d.... *); "\x8f\xcd\x0e\x02\x21\xff\xff\x80" (* ....!... *)
     ] in
   let input = String.concat "" inputs in
   let decoder = Inf.decoder (`String input) ~o ~w in
@@ -671,13 +651,8 @@ let fuzz16 () =
   Alcotest.test_case "fuzz16" `Quick @@ fun () ->
   let lst =
     [
-      `Literal '@'
-    ; `Copy (1, 212)
-    ; `Copy (129, 258)
-    ; `Copy (7, 131)
-    ; `Copy (527, 208)
-    ; `Copy (129, 258)
-    ; `End
+      `Literal '@'; `Copy (1, 212); `Copy (129, 258); `Copy (7, 131)
+    ; `Copy (527, 208); `Copy (129, 258); `End
     ] in
   let res = encode_dynamic lst in
   Fmt.epr "> %S.\n%!" res
@@ -689,12 +664,8 @@ let fuzz17 () =
   Alcotest.test_case "fuzz17" `Quick @@ fun () ->
   let lst =
     [
-      `Literal (Char.chr 218)
-    ; `Copy (1, 21)
-    ; `Literal (Char.chr 190)
-    ; `Literal (Char.chr 218)
-    ; `Literal (Char.chr 0)
-    ; `End
+      `Literal (Char.chr 218); `Copy (1, 21); `Literal (Char.chr 190)
+    ; `Literal (Char.chr 218); `Literal (Char.chr 0); `End
     ] in
   let res = encode_dynamic lst in
   let decoder = Inf.decoder (`String res) ~o ~w in
@@ -731,8 +702,7 @@ let fuzz18 () =
     ; "\x20\x67\x6e\x60\x5e\x28\x20\x5d\x6e\x0a\x63\x29\x67\x6e\x60\x20"
       (*  gn`^( ]n.c)gn`  *)
     ; "\x67\x6e\x60\x20\x67\x6e\x63\x29\x67\x6e\x60\x20\x67\x73\x60\x69"
-      (* gn` gnc)gn` gs`i *)
-    ; "\x63" (* c *)
+      (* gn` gnc)gn` gs`i *); "\x63" (* c *)
     ] in
   let output = String.concat "" outputs in
   Alcotest.(check str) "result" res output
@@ -755,7 +725,7 @@ let cmds = Alcotest.list cmd
 let lz77_0 () =
   Alcotest.test_case "simple match" `Quick @@ fun () ->
   Queue.reset q
-  ; let state = Lz77.state (`String "aaaaa") ~w ~q in
+  ; let state = Lz77.state (`String "aaaaa") ~w:l ~q in
     match Lz77.compress state with
     | `End ->
       let lst = Queue.to_list q in
@@ -768,7 +738,7 @@ let lz77_0 () =
 let lz77_1 () =
   Alcotest.test_case "no match" `Quick @@ fun () ->
   Queue.reset q
-  ; let state = Lz77.state (`String "abcde") ~w ~q in
+  ; let state = Lz77.state (`String "abcde") ~w:l ~q in
     match Lz77.compress state with
     | `End ->
       let lst = Queue.to_list q in
@@ -810,7 +780,7 @@ let lz77_2 () =
       ; "\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x19\x38\x80" (* ........8. *)
       ] in
     let input = String.concat "" inputs in
-    let state = Lz77.state (`String input) ~w ~q in
+    let state = Lz77.state (`String input) ~w:l ~q in
     match Lz77.compress state with
     | `End ->
       let lst = Queue.to_list q in
@@ -826,7 +796,7 @@ let lz77_3 () =
   ; let inputs =
       ["\xf6\x21\xff\x7f\x00\x9d\x0d\xf6\x21\xff\x7f" (* .!......!.. *)] in
     let input = String.concat "" inputs in
-    let state = Lz77.state (`String input) ~w ~q in
+    let state = Lz77.state (`String input) ~w:l ~q in
     match Lz77.compress state with
     | `End ->
       let lst = Queue.to_list q in
@@ -846,11 +816,10 @@ let lz77_4 () =
       ; "\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53\x53"
         (* SSSSSSSSSSSSSSSS *)
       ; "\x53\x53\x53\x53\x53\x53\x53\x7f\x0e\xff\xe8\x03\x00\x00\x00\xff"
-        (* SSSSSSS......... *)
-      ; "\xff\x57\xff\xe8\x03\x00" (* .W.... *)
+        (* SSSSSSS......... *); "\xff\x57\xff\xe8\x03\x00" (* .W.... *)
       ] in
     let input = String.concat "" inputs in
-    let state = Lz77.state (`String input) ~w ~q in
+    let state = Lz77.state (`String input) ~w:l ~q in
     match Lz77.compress state with
     | `End ->
       let lst = Queue.to_list q in
@@ -864,13 +833,8 @@ let hang0 () =
   Alcotest.test_case "hang" `Quick @@ fun () ->
   let lst =
     [
-      `Literal '\003'
-    ; `Literal '\012'
-    ; `Copy (1, 247)
-    ; `Literal 'W'
-    ; `Literal '\243'
-    ; `Copy (244, 15)
-    ; `End
+      `Literal '\003'; `Literal '\012'; `Copy (1, 247); `Literal 'W'
+    ; `Literal '\243'; `Copy (244, 15); `End
     ] in
   let res = encode_dynamic lst in
   Fmt.epr "> %S.\n%!" res
@@ -905,11 +869,9 @@ let dynamic_and_fixed () =
         | `Ok -> go r) in
     go
       [
-        `Block {Def.kind= Def.Dynamic dynamic_a; Def.last= false}
-      ; `Flush
+        `Block {Def.kind= Def.Dynamic dynamic_a; Def.last= false}; `Flush
       ; `Fill [`Literal 'b'; `Copy (1, 3); `End]
-      ; `Block {Def.kind= Def.Fixed; Def.last= true}
-      ; `Flush
+      ; `Block {Def.kind= Def.Fixed; Def.last= true}; `Flush
       ]
     ; let decoder = Inf.decoder (`String (Buffer.contents res)) ~w ~o in
       let res = unroll_inflate decoder in
@@ -940,10 +902,8 @@ let fixed_and_dynamic () =
         | `Ok -> go r) in
     go
       [
-        `Flush
-      ; `Block {Def.kind= Def.Dynamic dynamic_b; last= true}
-      ; `Fill [`Literal 'b'; `Copy (1, 3); `End]
-      ; `Flush
+        `Flush; `Block {Def.kind= Def.Dynamic dynamic_b; last= true}
+      ; `Fill [`Literal 'b'; `Copy (1, 3); `End]; `Flush
       ]
     ; Fmt.epr "> %S.\n%!" (Buffer.contents res)
     ; let decoder = Inf.decoder (`String (Buffer.contents res)) ~w ~o in
@@ -985,8 +945,7 @@ let dynamic_and_dynamic () =
       go
         [
           `Block {Def.kind= Def.Dynamic dynamic_a; Def.last= false}
-        ; `Block {Def.kind= Def.Dynamic dynamic_b; Def.last= true}
-        ; `Flush
+        ; `Block {Def.kind= Def.Dynamic dynamic_b; Def.last= true}; `Flush
         ]
 
       ; Fmt.epr "> %S.\n%!" (Buffer.contents res)
@@ -1030,13 +989,8 @@ let fixed_and_flat () =
   let q =
     Queue.of_list
       [
-        `Literal 'a'
-      ; `Copy (1, 3)
-      ; `End
-      ; `Literal '\xDE'
-      ; `Literal '\xAD'
-      ; `Literal '\xBE'
-      ; `Literal '\xEF'
+        `Literal 'a'; `Copy (1, 3); `End; `Literal '\xDE'; `Literal '\xAD'
+      ; `Literal '\xBE'; `Literal '\xEF'
       ] in
   let b = Buffer.create 16 in
   let encoder = Def.encoder (`Buffer b) ~q in
@@ -1058,13 +1012,8 @@ let flat_and_fixed () =
   let q =
     Queue.of_list
       [
-        `Literal '\xDE'
-      ; `Literal '\xAD'
-      ; `Literal '\xBE'
-      ; `Literal '\xEF'
-      ; `Literal 'a'
-      ; `Copy (1, 3)
-      ; `End
+        `Literal '\xDE'; `Literal '\xAD'; `Literal '\xBE'; `Literal '\xEF'
+      ; `Literal 'a'; `Copy (1, 3); `End
       ] in
   let b = Buffer.create 16 in
   let encoder = Def.encoder (`Buffer b) ~q in
@@ -1112,7 +1061,7 @@ let lz77_corpus_rfc5322 () =
   Alcotest.test_case "rfc5322" `Quick @@ fun () ->
   let ic = open_in "corpus/rfc5322.txt" in
   Queue.reset q
-  ; let state = Lz77.state (`Channel ic) ~w ~q in
+  ; let state = Lz77.state (`Channel ic) ~w:l ~q in
     let res = ref "" in
     let rec go () =
       match Lz77.compress state with
@@ -1176,579 +1125,35 @@ let tree_rfc5322_corpus () =
      This test want to check if we generate the same literals/lengths tree than [zlib]. *)
   let literals =
     [|
-       0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 236
-     ; 0
-     ; 27
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 5446
-     ; 1
-     ; 311
-     ; 1
-     ; 1
-     ; 10
-     ; 1
-     ; 7
-     ; 127
-     ; 128
-     ; 30
-     ; 11
-     ; 273
-     ; 175
-     ; 1180
-     ; 73
-     ; 67
-     ; 111
-     ; 169
-     ; 137
-     ; 60
-     ; 66
-     ; 45
-     ; 26
-     ; 41
-     ; 37
-     ; 57
-     ; 32
-     ; 6
-     ; 44
-     ; 6
-     ; 1
-     ; 7
-     ; 96
-     ; 21
-     ; 115
-     ; 61
-     ; 32
-     ; 127
-     ; 9
-     ; 45
-     ; 108
-     ; 3
-     ; 2
-     ; 66
-     ; 66
-     ; 46
-     ; 81
-     ; 31
-     ; 7
-     ; 104
-     ; 169
-     ; 118
-     ; 60
-     ; 3
-     ; 49
-     ; 1
-     ; 5
-     ; 0
-     ; 54
-     ; 9
-     ; 74
-     ; 1
-     ; 1
-     ; 1
-     ; 2126
-     ; 318
-     ; 1060
-     ; 1119
-     ; 3330
-     ; 666
-     ; 377
-     ; 800
-     ; 2005
-     ; 9
-     ; 81
-     ; 970
-     ; 729
-     ; 1808
-     ; 1802
-     ; 615
-     ; 40
-     ; 1612
-     ; 1991
-     ; 2201
-     ; 537
-     ; 158
-     ; 251
-     ; 127
-     ; 389
-     ; 12
-     ; 1
-     ; 62
-     ; 1
-     ; 1
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 1
-     ; 1594
-     ; 1153
-     ; 698
-     ; 345
-     ; 326
-     ; 229
-     ; 150
-     ; 107
-     ; 172
-     ; 111
-     ; 97
-     ; 23
-     ; 100
-     ; 44
-     ; 24
-     ; 10
-     ; 20
-     ; 14
-     ; 3
-     ; 7
-     ; 17
-     ; 1
-     ; 1
-     ; 1
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 2
-     ; 2
-     ; 2
-     ; 2
-     ; 2
-     ; 2
-     ; 2
-     ; 2
-     ; 3
-     ; 4
-     ; 4
-     ; 4
-     ; 5
-     ; 6
-     ; 7
-     ; 8
-     ; 9
-     ; 10
-     ; 13
-     ; 14
-     ; 14
-     ; 15
-     ; 18
-     ; 18
-     ; 20
-     ; 23
-     ; 27
-     ; 28
-     ; 31
-     ; 35
-     ; 37
-     ; 39
-     ; 47
-     ; 48
-     ; 55
-     ; 57
-     ; 59
-     ; 66
-     ; 73
-     ; 75
-     ; 77
-     ; 80
-     ; 82
-     ; 90
-     ; 95
-     ; 103
-     ; 110
-     ; 115
-     ; 119
-     ; 124
-     ; 128
-     ; 132
-     ; 140
-     ; 144
-     ; 152
-     ; 162
-     ; 180
-     ; 183
-     ; 190
-     ; 196
-     ; 204
-     ; 212
-     ; 219
-     ; 230
-     ; 239
-     ; 241
-     ; 252
-     ; 263
-     ; 278
-     ; 284
-     ; 300
-     ; 311
-     ; 324
-     ; 363
-     ; 384
-     ; 400
-     ; 425
-     ; 444
-     ; 469
-     ; 485
-     ; 515
-     ; 559
-     ; 565
-     ; 591
-     ; 619
-     ; 655
-     ; 711
-     ; 784
-     ; 869
-     ; 954
-     ; 1000
-     ; 1109
-     ; 1145
-     ; 1210
-     ; 1279
-     ; 1366
-     ; 1510
-     ; 1740
-     ; 1922
-     ; 1972
-     ; 2121
-     ; 2298
-     ; 2489
-     ; 2773
-     ; 2936
-     ; 3206
-     ; 3519
-     ; 3702
-     ; 3886
-     ; 4093
-     ; 4787
-     ; 5709
-     ; 6198
-     ; 7221
-     ; 7979
-     ; 9758
-     ; 11907
-     ; 15200
-     ; 21665
-     ; 36865
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
-     ; 0
+       0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 236; 0; 27; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 5446; 1; 311; 1; 1; 10; 1; 7; 127; 128; 30; 11
+     ; 273; 175; 1180; 73; 67; 111; 169; 137; 60; 66; 45; 26; 41; 37; 57; 32; 6
+     ; 44; 6; 1; 7; 96; 21; 115; 61; 32; 127; 9; 45; 108; 3; 2; 66; 66; 46; 81
+     ; 31; 7; 104; 169; 118; 60; 3; 49; 1; 5; 0; 54; 9; 74; 1; 1; 1; 2126; 318
+     ; 1060; 1119; 3330; 666; 377; 800; 2005; 9; 81; 970; 729; 1808; 1802; 615
+     ; 40; 1612; 1991; 2201; 537; 158; 251; 127; 389; 12; 1; 62; 1; 1; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 1; 1594; 1153; 698; 345; 326; 229; 150; 107; 172; 111; 97; 23; 100; 44
+     ; 24; 10; 20; 14; 3; 7; 17; 1; 1; 1; 0; 0; 0; 0; 0; 2; 2; 2; 2; 2; 2; 2; 2
+     ; 3; 4; 4; 4; 5; 6; 7; 8; 9; 10; 13; 14; 14; 15; 18; 18; 20; 23; 27; 28; 31
+     ; 35; 37; 39; 47; 48; 55; 57; 59; 66; 73; 75; 77; 80; 82; 90; 95; 103; 110
+     ; 115; 119; 124; 128; 132; 140; 144; 152; 162; 180; 183; 190; 196; 204; 212
+     ; 219; 230; 239; 241; 252; 263; 278; 284; 300; 311; 324; 363; 384; 400; 425
+     ; 444; 469; 485; 515; 559; 565; 591; 619; 655; 711; 784; 869; 954; 1000
+     ; 1109; 1145; 1210; 1279; 1366; 1510; 1740; 1922; 1972; 2121; 2298; 2489
+     ; 2773; 2936; 3206; 3519; 3702; 3886; 4093; 4787; 5709; 6198; 7221; 7979
+     ; 9758; 11907; 15200; 21665; 36865; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0
+     ; 0; 0; 0; 0
     |] in
   Alcotest.(check int)
     "length of freqs"
@@ -1761,95 +1166,83 @@ let tree_rfc5322_corpus () =
     Alcotest.(check (pair int int)) "literal 6" (10, 0x35f) (len_6, code_6)
     ; Alcotest.(check (pair int int)) "eob" (15, 0x6fff) (len_eob, code_eob)
 
-let w0 = make_window ~bits:15
+let w0 = Lz77.make_window ~bits:15
 let w1 = make_window ~bits:15
-let s = bigstring_create io_buffer_size
+let t = bigstring_create io_buffer_size
 let o = bigstring_create io_buffer_size
-let q = Queue.create (2 * 2 * 4096)
+let q = Queue.create 0x4000
 let b = Buffer.create 4096
 
 let compress_and_uncompress ic =
-  let state = Lz77.state (`Channel ic) ~w:w0 ~q in
-  let kind = ref Def.Fixed in
+  let state = Lz77.state ~q ~w:w0 (`Channel ic) in
   let encoder = Def.encoder `Manual ~q in
-  let decoder = Inf.decoder `Manual ~w:w1 ~o in
+  let decoder = Inf.decoder `Manual ~o ~w:w1 in
 
-  Buffer.clear b
-  ; Queue.reset q
-  ; Def.dst encoder s 0 io_buffer_size
+  let rec compress () =
+    match De.Lz77.compress state with
+    | `Await -> assert false
+    | `Flush ->
+      let literals = Lz77.literals state in
+      let distances = Lz77.distances state in
+      Fmt.epr "[compress]: `Flush.\n%!"
+      ; encode
+        @@ Def.encode encoder
+             (`Block
+               {
+                 Def.kind=
+                   Dynamic (Def.dynamic_of_frequencies ~literals ~distances)
+               ; last= false
+               })
+    | `End ->
+      Fmt.epr "[compress]: `End.\n%!"
+      ; Queue.push_exn q Queue.eob
+      ; pending @@ Def.encode encoder (`Block {Def.kind= Fixed; last= true})
+  and pending = function
+    | `Partial | `Ok ->
+      let len = bigstring_length t - Def.dst_rem encoder in
+      Fmt.epr "[pending]: `Partial (%d byte(s)).\n%!" len
+      ; Inf.src decoder t 0 len
+      ; decode @@ Inf.decode decoder
+    | `Block -> assert false
+  and encode = function
+    | `Partial ->
+      let len = bigstring_length t - Def.dst_rem encoder in
+      Fmt.epr "[encode]: `Partial (%d byte(s)).\n%!" len
+      ; Inf.src decoder t 0 len
+      ; decode @@ Inf.decode decoder
+    | `Ok ->
+      Fmt.epr "[encode] `Ok.\n%!"
+      ; compress ()
+    | `Block ->
+      Fmt.epr "[encode] `Ok.\n%!"
+      ; compress ()
+  and decode = function
+    | `Await ->
+      Def.dst encoder t 0 (bigstring_length t)
+      ; encode @@ Def.encode encoder `Await
+    | (`Flush | `End) as state ->
+      let len = bigstring_length o - Inf.dst_rem decoder in
+      let str = Bigstringaf.substring o ~off:0 ~len in
+      Fmt.epr "[decode] `Flush | `End (%d byte(s)).\n%!" len
+      ; Buffer.add_string b str
+      ; if state = `Flush then (
+          Inf.flush decoder
+          ; decode @@ Inf.decode decoder)
+        else Fmt.epr "[decode] `End.\n%!"
+    | `Malformed err -> Alcotest.failf "Malformed compressed input: %S" err
+  in
 
-  ; let rec partial k = function
-      | `Await -> k @@ Def.encode encoder `Await
-      | `End ->
-        for i = 0 to io_buffer_size - Inf.dst_rem decoder - 1 do
-          Buffer.add_char b (Char.unsafe_chr (unsafe_get_uint8 o i))
-        done
-      | `Flush ->
-        for i = 0 to io_buffer_size - Inf.dst_rem decoder - 1 do
-          Buffer.add_char b (Char.unsafe_chr (unsafe_get_uint8 o i))
-        done
-        ; Inf.flush decoder
-        ; Def.dst encoder s 0 io_buffer_size
-        ; partial k @@ Inf.decode decoder
-      | `Malformed err -> invalid_arg err
-    and compress () =
-      match Lz77.compress state with
-      | `Await -> assert false
-      | `End ->
-        Queue.push_exn q Queue.eob
-        ; pending
-          @@ Def.encode encoder (`Block {Def.kind= Def.Fixed; last= true})
-      | `Flush ->
-        kind :=
-          Def.Dynamic
-            (Def.dynamic_of_frequencies ~literals:(Lz77.literals state)
-               ~distances:(Lz77.distances state))
-        ; encode @@ Def.encode encoder (`Block {Def.kind= !kind; last= false})
-    and encode = function
-      | `Partial ->
-        let len = io_buffer_size - Def.dst_rem encoder in
-        Inf.src decoder s 0 len
-        ; partial encode @@ Inf.decode decoder
-      | `Ok -> compress ()
-      | `Block ->
-        kind :=
-          Def.Dynamic
-            (Def.dynamic_of_frequencies ~literals:(Lz77.literals state)
-               ~distances:(Lz77.distances state))
-        ; encode @@ Def.encode encoder (`Block {Def.kind= !kind; last= false})
-    and pending = function
-      | `Partial ->
-        let len = io_buffer_size - Def.dst_rem encoder in
-        Inf.src decoder s 0 len
-        ; partial pending @@ Inf.decode decoder
-      | `Ok -> last @@ Def.encode encoder `Flush
-      | `Block -> assert false
-    and last = function
-      | `Partial ->
-        let len = io_buffer_size - Def.dst_rem encoder in
-        Inf.src decoder s 0 len
-        ; partial pending @@ Inf.decode decoder
-      | `Ok -> partial pending @@ Inf.decode decoder
-      | `Block -> assert false in
-
-    compress ()
-    ; Stdlib.seek_in ic 0
-    ; let contents = Buffer.contents b in
-
-      let rec slow_compare pos =
-        match input_char ic with
-        | chr ->
-          if pos >= String.length contents then
-            Fmt.invalid_arg "Reach end of contents"
-          ; if contents.[pos] <> chr then
-              Fmt.invalid_arg "Contents differ at %08x\n%!" pos
-          ; slow_compare (succ pos)
-        | exception End_of_file ->
-          if pos <> String.length contents then
-            Fmt.invalid_arg "Lengths differ: (contents: %d, file: %d)"
-              (String.length contents) pos in
+  Def.dst encoder t 0 (bigstring_length t)
+  ; Buffer.clear b
+  ; Queue.reset q
+  ; compress ()
 
-      slow_compare 0
+  ; Fmt.epr "End of compress/decompress.\n%!"
+  ; Stdlib.seek_in ic 0
+  ; let a0 = Buffer.contents b in
+    let ln = Stdlib.in_channel_length ic in
+    let a1 = really_input_string ic ln in
+    Alcotest.(check string) "contents" a0 a1
 
 let test_corpus filename =
   Alcotest.test_case filename `Slow @@ fun () ->
@@ -1861,7 +1254,7 @@ let gzip_compress_and_uncompress ~filename ic =
   ; let os = bigstring_create io_buffer_size in
     let bf = Buffer.create 4096 in
     let encoder =
-      Gz.Def.encoder (`Channel ic) `Manual ~filename ~mtime:0l Gz.Unix ~q ~w
+      Gz.Def.encoder (`Channel ic) `Manual ~filename ~mtime:0l Gz.Unix ~q ~w:l
         ~level:0 in
     let decoder = Gz.Inf.decoder `Manual ~o in
 
@@ -1920,7 +1313,7 @@ let gzip_compress_and_uncompress ~filename ic =
 
 let zlib_compress_and_uncompress ic =
   De.Queue.reset q
-  ; let encoder = Zl.Def.encoder (`Channel ic) `Manual ~q ~w ~level:0 in
+  ; let encoder = Zl.Def.encoder (`Channel ic) `Manual ~q ~w:l ~level:0 in
     let decoder =
       Zl.Inf.decoder `Manual ~o ~allocate:(fun bits -> De.make_window ~bits)
     in
@@ -1989,8 +1382,9 @@ let git_object () =
   Alcotest.test_case "git object" `Quick @@ fun () ->
   let inputs =
     [
-      "\x78\x01\x01\x1e\x00\xe1\xff"
-    ; "\x9d\x02\x9d\x02\x90\xad\x14\x72\xb9\xb4\x44\x59\x5d\x21\x05\xb7\x34\x4f\x64\xe9\xa8\x5a\x3e\xd9\x91\x1f\x44\x91\xc1\x5c\xbd\xe5\x0c\xd1"
+      "\x78\x01\x01\x1e\x00\xe1\xff"; "\x9d\x02\x9d\x02\x90\xad\x14"
+    ; "\x72\xb9\xb4\x44\x59\x5d\x21"; "\x05\xb7\x34\x4f\x64\xe9\xa8"
+    ; "\x5a\x3e\xd9\x91\x1f\x44\x91"; "\xc1\x5c\xbd\xe5\x0c\xd1"
     ] in
   let decoder =
     Zl.Inf.decoder (`String (String.concat "" inputs)) ~o ~allocate:(fun _ -> w)
@@ -2002,10 +1396,12 @@ let git_object () =
     | `Malformed err -> failwith err
     | `End _ -> () in
   go decoder
-  ; let[@warning "-8"] [i0; i1] =
+  ; let[@warning "-8"] (i0 :: i1) = inputs in
+    let i1 = String.concat "" i1 in
+    let[@warning "-8"] [i0; i1] =
       List.map
         (fun x -> Bigstringaf.of_string ~off:0 ~len:(String.length x) x)
-        inputs in
+        [i0; i1] in
     let decoder = Zl.Inf.decoder `Manual ~o ~allocate:(fun _ -> w) in
     let decoder = Zl.Inf.src decoder i0 0 (Bigstringaf.length i0) in
     let rec go_i0 decoder =
@@ -2050,7 +1446,7 @@ let higher_zlib input =
   Queue.reset q
   ; let refill = emitter_from_string input in
     let flush, contents = producer_to_string () in
-    Zl.Higher.compress ~level:0 ~w ~q ~refill ~flush i o
+    Zl.Higher.compress ~level:0 ~w:l ~q ~refill ~flush i o
     ; Fmt.epr "%S\n%!" (contents ())
     ; let refill = emitter_from_string (contents ()) in
       let flush, contents = producer_to_string () in
@@ -2068,7 +1464,7 @@ let test_multiple_flush_zlib () =
   Queue.reset q
   ; let refill = emitter_from_string "foo" in
     let flush, contents = producer_to_string () in
-    Zl.Higher.compress ~level:0 ~w ~q ~refill ~flush i o
+    Zl.Higher.compress ~level:0 ~w:l ~q ~refill ~flush i o
     ; let input = contents () in
       let decoder =
         Zl.Inf.decoder (`String input) ~o ~allocate:(fun bits ->
@@ -2098,7 +1494,7 @@ let test_empty_with_zlib () =
   Alcotest.test_case "empty zlib" `Quick @@ fun () ->
   Queue.reset q
   ; let buf = Buffer.create 16 in
-    let encoder = Zl.Def.encoder (`String "") (`Buffer buf) ~q ~w ~level:3 in
+    let encoder = Zl.Def.encoder (`String "") (`Buffer buf) ~q ~w:l ~level:3 in
     let go encoder =
       match Zl.Def.encode encoder with
       | `Flush _ | `Await _ ->
@@ -2124,7 +1520,7 @@ let test_empty_with_zlib_and_small_output () =
   Queue.reset q
   ; let o = bigstring_create 4 in
     let buf = Buffer.create 16 in
-    let encoder = Zl.Def.encoder (`String "") `Manual ~q ~w ~level:3 in
+    let encoder = Zl.Def.encoder (`String "") `Manual ~q ~w:l ~level:3 in
     let encoder = Zl.Def.dst encoder o 0 4 in
     let rec go encoder =
       match Zl.Def.encode encoder with
@@ -2159,7 +1555,7 @@ let test_empty_with_zlib_byte_per_byte () =
   Alcotest.test_case "empty zlib (byte per byte)" `Quick @@ fun () ->
   Queue.reset q
   ; let buf = Buffer.create 16 in
-    let encoder = Zl.Def.encoder (`String "") (`Buffer buf) ~q ~w ~level:3 in
+    let encoder = Zl.Def.encoder (`String "") (`Buffer buf) ~q ~w:l ~level:3 in
     let go encoder =
       match Zl.Def.encode encoder with
       | `Flush _ | `Await _ ->
@@ -2291,8 +1687,8 @@ let test_generate_empty_gzip () =
   Queue.reset q
   ; let buf = Buffer.create 16 in
     let encoder =
-      Gz.Def.encoder (`String "") (`Buffer buf) ~mtime:0l Gz.Unix ~q ~w ~level:3
-    in
+      Gz.Def.encoder (`String "") (`Buffer buf) ~mtime:0l Gz.Unix ~q ~w:l
+        ~level:3 in
     let go encoder =
       match Gz.Def.encode encoder with
       | `Await _ -> Alcotest.failf "Unexpected `Await signal"
@@ -2317,7 +1713,7 @@ let test_generate_empty_gzip_with_name () =
   ; let buf = Buffer.create 16 in
     let encoder =
       Gz.Def.encoder (`String "") (`Buffer buf) ~filename:"foo" ~mtime:0l
-        Gz.Unix ~q ~w ~level:0 in
+        Gz.Unix ~q ~w:l ~level:0 in
     let go encoder =
       match Gz.Def.encode encoder with
       | `Await _ -> Alcotest.failf "Unexpected `Await signal"
@@ -2344,7 +1740,7 @@ let test_generate_foo_gzip () =
   ; let buf = Buffer.create 16 in
     let encoder =
       Gz.Def.encoder (`String "foo") (`Buffer buf) ~filename:"foo" ~mtime:0l
-        Gz.Unix ~q ~w ~level:0 in
+        Gz.Unix ~q ~w:l ~level:0 in
     let go encoder =
       match Gz.Def.encode encoder with
       | `Await _ -> Alcotest.failf "Unexpected `Await signal"
@@ -2373,7 +1769,7 @@ let test_with_camlzip () =
   let oc = open_out "foo.gz" in
   let encoder =
     Gz.Def.encoder (`String "foo") (`Channel oc) ~filename:"foo.gz" ~mtime:0l
-      Gz.Unix ~q ~w ~level:0 in
+      Gz.Unix ~q ~w:l ~level:0 in
   let go encoder =
     match Gz.Def.encode encoder with
     | `Await _ -> Alcotest.failf "Unexpected `Await signal"
@@ -2391,7 +1787,7 @@ let test_gzip_hcrc () =
   let oc = open_out "foo.gz" in
   let encoder =
     Gz.Def.encoder (`String "foo & bar") (`Channel oc) ~filename:"foo.gz"
-      ~mtime:0l Gz.Unix ~hcrc:true ~q ~w ~level:0 in
+      ~mtime:0l Gz.Unix ~hcrc:true ~q ~w:l ~level:0 in
   let go encoder =
     match Gz.Def.encode encoder with
     | `Await _ -> Alcotest.failf "Unexpected `Await signal"
@@ -2428,12 +1824,9 @@ let test_invalid_hcrc () =
   Alcotest.test_case "invalid header crc" `Quick @@ fun () ->
   let inputs =
     [
-      "\x1f\x8b\x08\x0a\x00\x00\x00\x00\x02\x03\x66\x6f\x6f\x2e\x67\x7a"
-    ; "\x00"
-    ; "\x4b\xcb\x71\xde"
-    ; (* HCRC *)
-      "\xcf\x57\x50\x53\x48\x4a\x2c\x02\x00\x8f\x47"
-    ; "\xe4\xdd\x09\x00\x00\x00"
+      "\x1f\x8b\x08\x0a\x00\x00\x00\x00\x02\x03\x66\x6f\x6f\x2e\x67\x7a"; "\x00"
+    ; "\x4b\xcb\x71\xde"; (* HCRC *)
+      "\xcf\x57\x50\x53\x48\x4a\x2c\x02\x00\x8f\x47"; "\xe4\xdd\x09\x00\x00\x00"
     ] in
   let decoder = Gz.Inf.decoder (`String (String.concat "" inputs)) ~o in
   match Gz.Inf.decode decoder with
@@ -2451,8 +1844,8 @@ let test_gzip_os v_os =
   let input = random 256 in
   let buf = Buffer.create 16 in
   let encoder =
-    Gz.Def.encoder (`String input) (`Buffer buf) ~mtime:0l v_os ~hcrc:true ~q ~w
-      ~level:0 in
+    Gz.Def.encoder (`String input) (`Buffer buf) ~mtime:0l v_os ~hcrc:true ~q
+      ~w:l ~level:0 in
   let go encoder =
     match Gz.Def.encode encoder with
     | `Await _ -> Alcotest.failf "Unexpected `Await signal"
@@ -2481,9 +1874,7 @@ let test_gzip_extra () =
   Alcotest.test_case "GZip with extra" `Quick @@ fun () ->
   let inputs =
     [
-      "\x1f\x8b\x08\x0c\x63\xcb\x5f\x5e\x00\x03"
-    ; "\x00\x0a"
-    ; "lx\x00\x06ubuntu"
+      "\x1f\x8b\x08\x0c\x63\xcb\x5f\x5e\x00\x03"; "\x00\x0a"; "lx\x00\x06ubuntu"
     ; "\x66\x6f\x6f\x2e\x74\x78"
     ; "\x74\x00\x4b\xcb\xcf\xe7\x02\x00\xa8\x65\x32\x7e\x04\x00\x00\x00"
     ] in
@@ -2596,173 +1987,84 @@ let () =
     [
       ( "invalids"
       , [
-          invalid_complement_of_length ()
-        ; invalid_kind_of_block ()
-        ; invalid_code_lengths ()
-        ; invalid_bit_length_repeat ()
-        ; invalid_codes ()
-        ; invalid_lengths ()
-        ; invalid_distances ()
-        ; too_many_length_or_distance_symbols ()
-        ; invalid_distance_code ()
-        ; invalid_distance_too_far_back ()
-        ; invalid_access ()
+          invalid_complement_of_length (); invalid_kind_of_block ()
+        ; invalid_code_lengths (); invalid_bit_length_repeat ()
+        ; invalid_codes (); invalid_lengths (); invalid_distances ()
+        ; too_many_length_or_distance_symbols (); invalid_distance_code ()
+        ; invalid_distance_too_far_back (); invalid_access ()
         ] )
     ; ( "valids"
       , [
-          fixed ()
-        ; stored ()
-        ; length_extra ()
-        ; long_distance_and_extra ()
-        ; window_end ()
-        ; huffman_length_extra ()
-        ; dynamic_and_fixed ()
-        ; fixed_and_dynamic ()
-        ; dynamic_and_dynamic ()
-        ; flat_of_string ()
-        ; flat_block ()
-        ; flat ()
-        ; max_flat ()
-        ; fixed_and_flat ()
+          fixed (); stored (); length_extra (); long_distance_and_extra ()
+        ; window_end (); huffman_length_extra (); dynamic_and_fixed ()
+        ; fixed_and_dynamic (); dynamic_and_dynamic (); flat_of_string ()
+        ; flat_block (); flat (); max_flat (); fixed_and_flat ()
         ; flat_and_fixed ()
         ] )
     ; ( "fuzz"
       , [
-          fuzz0 ()
-        ; fuzz1 ()
-        ; fuzz2 ()
-        ; fuzz3 ()
-        ; fuzz4 ()
-        ; fuzz5 ()
-        ; fuzz6 ()
-        ; fuzz7 ()
-        ; fuzz8 ()
-        ; fuzz9 ()
-        ; fuzz10 ()
-        ; fuzz11 ()
-        ; fuzz12 ()
-        ; fuzz13 ()
-        ; fuzz14 ()
-        ; fuzz15 ()
-        ; fuzz16 ()
-        ; fuzz17 ()
-        ; fuzz18 ()
-        ] )
-    ; "huffman", [tree_0 (); tree_rfc5322_corpus ()]
+          fuzz0 (); fuzz1 (); fuzz2 (); fuzz3 (); fuzz4 (); fuzz5 (); fuzz6 ()
+        ; fuzz7 (); fuzz8 (); fuzz9 (); fuzz10 (); fuzz11 (); fuzz12 ()
+        ; fuzz13 (); fuzz14 (); fuzz15 (); fuzz16 (); fuzz17 (); fuzz18 ()
+        ] ); "huffman", [tree_0 (); tree_rfc5322_corpus ()]
     ; ( "lz77"
       , [
-          lz77_0 ()
-        ; lz77_1 ()
-        ; lz77_2 ()
-        ; lz77_3 ()
-        ; lz77_4 ()
+          lz77_0 (); lz77_1 (); lz77_2 (); lz77_3 (); lz77_4 ()
         ; lz77_corpus_rfc5322 ()
         ] )
     ; ( "calgary"
       , [
-          test_corpus "bib"
-        ; test_corpus "rfc5322.txt"
-        ; test_corpus "book1"
-        ; test_corpus "book2"
-        ; test_corpus "geo"
-        ; test_corpus "news"
-        ; test_corpus "obj1"
-        ; test_corpus "obj2"
-        ; test_corpus "paper1"
-        ; test_corpus "paper2"
-        ; test_corpus "pic"
-        ; test_corpus "progc"
-        ; test_corpus "progl"
-        ; test_corpus "progp"
-        ; test_corpus "trans"
+          test_corpus "bib"; test_corpus "rfc5322.txt"; test_corpus "book1"
+        ; test_corpus "book2"; test_corpus "geo"; test_corpus "news"
+        ; test_corpus "obj1"; test_corpus "obj2"; test_corpus "paper1"
+        ; test_corpus "paper2"; test_corpus "pic"; test_corpus "progc"
+        ; test_corpus "progl"; test_corpus "progp"; test_corpus "trans"
         ] )
     ; ( "zlib"
       , [
-          test_empty_with_zlib ()
-        ; test_empty_with_zlib_and_small_output ()
-        ; test_empty_with_zlib_byte_per_byte ()
-        ; test_corpus_with_zlib "bib"
-        ; test_corpus_with_zlib "book1"
-        ; test_corpus_with_zlib "book2"
-        ; test_corpus_with_zlib "geo"
-        ; test_corpus_with_zlib "news"
-        ; test_corpus_with_zlib "obj1"
-        ; test_corpus_with_zlib "obj2"
-        ; test_corpus_with_zlib "paper1"
-        ; test_corpus_with_zlib "paper2"
-        ; test_corpus_with_zlib "pic"
-        ; test_corpus_with_zlib "progc"
-        ; test_corpus_with_zlib "progl"
-        ; test_corpus_with_zlib "progp"
-        ; test_corpus_with_zlib "trans"
-        ; test_multiple_flush_zlib ()
+          test_empty_with_zlib (); test_empty_with_zlib_and_small_output ()
+        ; test_empty_with_zlib_byte_per_byte (); test_corpus_with_zlib "bib"
+        ; test_corpus_with_zlib "book1"; test_corpus_with_zlib "book2"
+        ; test_corpus_with_zlib "geo"; test_corpus_with_zlib "news"
+        ; test_corpus_with_zlib "obj1"; test_corpus_with_zlib "obj2"
+        ; test_corpus_with_zlib "paper1"; test_corpus_with_zlib "paper2"
+        ; test_corpus_with_zlib "pic"; test_corpus_with_zlib "progc"
+        ; test_corpus_with_zlib "progl"; test_corpus_with_zlib "progp"
+        ; test_corpus_with_zlib "trans"; test_multiple_flush_zlib ()
         ] )
     ; ( "gzip"
       , [
-          test_empty_gzip ()
-        ; test_empty_gzip_with_name ()
-        ; test_foo_gzip ()
-        ; test_multiple_flush_gzip ()
-        ; test_generate_empty_gzip ()
-        ; test_generate_empty_gzip_with_name ()
-        ; test_generate_foo_gzip ()
-        ; test_corpus_with_gzip "bib"
-        ; test_corpus_with_gzip "book1"
-        ; test_corpus_with_gzip "book2"
-        ; test_corpus_with_gzip "geo"
-        ; test_corpus_with_gzip "news"
-        ; test_corpus_with_gzip "obj1"
-        ; test_corpus_with_gzip "obj2"
-        ; test_corpus_with_gzip "paper1"
-        ; test_corpus_with_gzip "paper2"
-        ; test_corpus_with_gzip "pic"
-        ; test_corpus_with_gzip "progc"
-        ; test_corpus_with_gzip "progl"
-        ; test_corpus_with_gzip "progp"
-        ; test_corpus_with_gzip "trans"
-        ; test_with_camlzip ()
-        ; test_gzip_hcrc ()
-        ; test_invalid_hcrc ()
+          test_empty_gzip (); test_empty_gzip_with_name (); test_foo_gzip ()
+        ; test_multiple_flush_gzip (); test_generate_empty_gzip ()
+        ; test_generate_empty_gzip_with_name (); test_generate_foo_gzip ()
+        ; test_corpus_with_gzip "bib"; test_corpus_with_gzip "book1"
+        ; test_corpus_with_gzip "book2"; test_corpus_with_gzip "geo"
+        ; test_corpus_with_gzip "news"; test_corpus_with_gzip "obj1"
+        ; test_corpus_with_gzip "obj2"; test_corpus_with_gzip "paper1"
+        ; test_corpus_with_gzip "paper2"; test_corpus_with_gzip "pic"
+        ; test_corpus_with_gzip "progc"; test_corpus_with_gzip "progl"
+        ; test_corpus_with_gzip "progp"; test_corpus_with_gzip "trans"
+        ; test_with_camlzip (); test_gzip_hcrc (); test_invalid_hcrc ()
         ; test_gzip_extra ()
         ] )
     ; ( "gzip with os"
       , [
-          test_gzip_os Gz.FAT
-        ; test_gzip_os Gz.Amiga
-        ; test_gzip_os Gz.VMS
-        ; test_gzip_os Gz.Unix
-        ; test_gzip_os Gz.VM
-        ; test_gzip_os Gz.Atari
-        ; test_gzip_os Gz.HPFS
-        ; test_gzip_os Gz.Macintosh
-        ; test_gzip_os Gz.Z
-        ; test_gzip_os Gz.CPM
-        ; test_gzip_os Gz.TOPS20
-        ; test_gzip_os Gz.NTFS
-        ; test_gzip_os Gz.QDOS
-        ; test_gzip_os Gz.Acorn
-        ; test_gzip_os Gz.Unknown
+          test_gzip_os Gz.FAT; test_gzip_os Gz.Amiga; test_gzip_os Gz.VMS
+        ; test_gzip_os Gz.Unix; test_gzip_os Gz.VM; test_gzip_os Gz.Atari
+        ; test_gzip_os Gz.HPFS; test_gzip_os Gz.Macintosh; test_gzip_os Gz.Z
+        ; test_gzip_os Gz.CPM; test_gzip_os Gz.TOPS20; test_gzip_os Gz.NTFS
+        ; test_gzip_os Gz.QDOS; test_gzip_os Gz.Acorn; test_gzip_os Gz.Unknown
         ] )
     ; ( "lzo"
       , [
-          test_lzo_0 ()
-        ; test_lzo_1 ()
-        ; test_corpus_with_lzo "obj1"
-        ; test_corpus_with_lzo "obj2"
-        ; test_corpus_with_lzo "geo"
-        ; test_corpus_with_lzo "news"
-        ; test_corpus_with_lzo "pic"
-        ; test_corpus_with_lzo "progc"
-        ; test_corpus_with_lzo "progl"
-        ; test_corpus_with_lzo "progp"
-        ; test_corpus_with_lzo "trans"
-        ; test_corpus_with_lzo "paper1"
-        ; test_corpus_with_lzo "paper2"
-        ; test_corpus_with_lzo "book1"
-        ; test_corpus_with_lzo "book2"
-        ] )
-    ; "hang", [hang0 ()]
-    ; "git", [git_object ()]
+          test_lzo_0 (); test_lzo_1 (); test_corpus_with_lzo "obj1"
+        ; test_corpus_with_lzo "obj2"; test_corpus_with_lzo "geo"
+        ; test_corpus_with_lzo "news"; test_corpus_with_lzo "pic"
+        ; test_corpus_with_lzo "progc"; test_corpus_with_lzo "progl"
+        ; test_corpus_with_lzo "progp"; test_corpus_with_lzo "trans"
+        ; test_corpus_with_lzo "paper1"; test_corpus_with_lzo "paper2"
+        ; test_corpus_with_lzo "book1"; test_corpus_with_lzo "book2"
+        ] ); "hang", [hang0 ()]; "git", [git_object ()]
     ; ( "higher"
       , [higher_zlib0 (); higher_zlib1 (); higher_zlib2 (); higher_zlib3 ()] )
     ]
diff --git a/test/test_deflate.ml b/test/test_deflate.ml
new file mode 100644
index 0000000..a319f98
--- /dev/null
+++ b/test/test_deflate.ml
@@ -0,0 +1,111 @@
+open De
+
+let q = Queue.create 0x4000
+let o = bigstring_create io_buffer_size
+let t = bigstring_create io_buffer_size
+let w0 = Lz77.make_window ~bits:15
+let w1 = make_window ~bits:15
+
+let load_file filename =
+  let ic = open_in filename in
+  let ln = in_channel_length ic in
+  let rs = really_input_string ic ln in
+  close_in ic ; rs
+
+let compare_files a b =
+  let x = load_file a and y = load_file b in
+  Alcotest.(check string) (Fmt.str "%s:%s" a b) x y
+
+let deflate_with_level ~level filename =
+  Alcotest.test_case (Fmt.str "%s (level: %d)" filename level) `Quick
+  @@ fun () ->
+  let ic = open_in filename in
+  let oc = open_out (filename ^ ".o") in
+  let state = Lz77.state ~level ~q ~w:w0 (`Channel ic) in
+  let encoder = Def.encoder `Manual ~q in
+  let decoder = Inf.decoder `Manual ~o ~w:w1 in
+  let rec compress () =
+    match De.Lz77.compress state with
+    | `Await -> assert false
+    | `Flush ->
+      let literals = Lz77.literals state in
+      let distances = Lz77.distances state in
+      Fmt.epr "[compress]: `Flush.\n%!"
+      ; encode
+        @@ Def.encode encoder
+             (`Block
+               {
+                 Def.kind=
+                   Dynamic (Def.dynamic_of_frequencies ~literals ~distances)
+               ; last= false
+               })
+    | `End ->
+      close_in ic
+      ; Queue.push_exn q Queue.eob
+      ; pending @@ Def.encode encoder (`Block {Def.kind= Fixed; last= true})
+  and pending = function
+    | `Partial | `Ok ->
+      let len = bigstring_length t - Def.dst_rem encoder in
+      Fmt.epr "[pending]: `Partial (%d byte(s)).\n%!" len
+      ; Inf.src decoder t 0 len
+      ; decode @@ Inf.decode decoder
+    | `Block -> assert false
+  and encode = function
+    | `Partial ->
+      let len = bigstring_length t - Def.dst_rem encoder in
+      Fmt.epr "[encode]: `Partial (%d byte(s)).\n%!" len
+      ; Inf.src decoder t 0 len
+      ; decode @@ Inf.decode decoder
+    | `Ok ->
+      Fmt.epr "[encode] `Ok.\n%!"
+      ; compress ()
+    | `Block ->
+      Fmt.epr "[encode] `Ok.\n%!"
+      ; compress ()
+  and decode = function
+    | `Await ->
+      Def.dst encoder t 0 (bigstring_length t)
+      ; encode @@ Def.encode encoder `Await
+    | (`Flush | `End) as state ->
+      let len = bigstring_length o - Inf.dst_rem decoder in
+      let str = Bigstringaf.substring o ~off:0 ~len in
+      output_string oc str
+      ; if state = `Flush then (
+          Inf.flush decoder
+          ; decode @@ Inf.decode decoder)
+        else close_out oc
+    | `Malformed err -> Alcotest.failf "Malformed compressed input: %S" err
+  in
+  Def.dst encoder t 0 (bigstring_length t)
+  ; Queue.reset q
+  ; compress ()
+  ; compare_files filename (filename ^ ".o")
+
+let () =
+  Alcotest.run "lz"
+    [
+      ( "6"
+      , [
+          deflate_with_level ~level:6 "corpus/pic"
+        ; deflate_with_level ~level:6 "corpus/book2"
+        ; deflate_with_level ~level:6 "corpus/news"
+        ] )
+    ; ( "4"
+      , [
+          deflate_with_level ~level:4 "corpus/pic"
+        ; deflate_with_level ~level:4 "corpus/book2"
+        ; deflate_with_level ~level:4 "corpus/news"
+        ] )
+    ; ( "9"
+      , [
+          deflate_with_level ~level:9 "corpus/pic"
+        ; deflate_with_level ~level:9 "corpus/book2"
+        ; deflate_with_level ~level:9 "corpus/news"
+        ] )
+    ; ( "1"
+      , [
+          deflate_with_level ~level:1 "corpus/pic"
+        ; deflate_with_level ~level:1 "corpus/book2"
+        ; deflate_with_level ~level:1 "corpus/news"
+        ] )
+    ]