Something went wrong. Try again.
Zstd compression in pure OCaml
Something went wrong. Try again.
26 kB · 721 lines
OCaml
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722(** Zstandard decompression implementation (RFC 8878). *)
(** Frame header information *)type frame_header = { window_size : int; frame_content_size : int64 option; dictionary_id : int32 option; content_checksum : bool; single_segment : bool;}
(** Sequence command *)type sequence = { literal_length : int; match_length : int; offset : int;}
(** Dictionary *)type dictionary = { dict_id : int32; huf_table : Huffman.dtable option; ll_table : Fse.dtable; ml_table : Fse.dtable; of_table : Fse.dtable; content : bytes; repeat_offsets : int array;}
(** Frame context during decompression *)type frame_context = { mutable huf_table : Huffman.dtable option; mutable ll_table : Fse.dtable option; mutable ml_table : Fse.dtable option; mutable of_table : Fse.dtable option; mutable repeat_offsets : int array; mutable total_output : int; dict : dictionary option; dict_content : bytes option; window_size : int;}
(** Parse frame header *)let parse_frame_header stream = let descriptor = Bit_reader.Forward.read_byte stream in
let fcs_flag = descriptor lsr 6 in let single_segment = (descriptor lsr 5) land 1 = 1 in let (_ : int) = (descriptor lsr 4) land 1 in (* unused bit *) let reserved = (descriptor lsr 3) land 1 in let checksum_flag = (descriptor lsr 2) land 1 = 1 in let dict_id_flag = descriptor land 3 in
if reserved <> 0 then raise (Constants.Zstd_error Constants.Invalid_frame_header);
(* Window descriptor (if not single segment) *) let window_size = if not single_segment then begin let window_desc = Bit_reader.Forward.read_byte stream in let exponent = window_desc lsr 3 in let mantissa = window_desc land 7 in let window_base = 1 lsl (10 + exponent) in let window_add = (window_base / 8) * mantissa in window_base + window_add end else 0 in
(* Dictionary ID *) let dictionary_id = if dict_id_flag <> 0 then begin let sizes = [| 0; 1; 2; 4 |] in let bytes = sizes.(dict_id_flag) in let id = ref 0l in for i = 0 to bytes - 1 do let b = Bit_reader.Forward.read_byte stream in id := Int32.logor !id (Int32.shift_left (Int32.of_int b) (i * 8)) done; Some !id end else None in
(* Frame content size *) let frame_content_size = if single_segment || fcs_flag <> 0 then begin let sizes = [| 1; 2; 4; 8 |] in let bytes = sizes.(fcs_flag) in let size = ref 0L in for i = 0 to bytes - 1 do let b = Bit_reader.Forward.read_byte stream in size := Int64.logor !size (Int64.shift_left (Int64.of_int b) (i * 8)) done; (* 2-byte sizes have 256 added *) if bytes = 2 then size := Int64.add !size 256L; Some !size end else None in
(* For single segment, window_size = frame_content_size *) let window_size = if single_segment then Option.fold ~none:0 ~some:Int64.to_int frame_content_size else window_size in
{ window_size; frame_content_size; dictionary_id; content_checksum = checksum_flag; single_segment }
(** Decode literals section *)let decode_literals ctx stream output ~out_pos = (* Read first byte to get block type and size format *) let header_byte = Bit_reader.Forward.read_byte stream in let block_type = header_byte land 3 in let size_format = (header_byte lsr 2) land 3 in
match Constants.literals_block_type_of_int block_type with | Raw_literals | RLE_literals -> (* For Raw/RLE: Size_Format determines header size 00/10: 1 byte total (5 bit size in first byte) 01: 2 bytes total (12 bit size) 11: 3 bytes total (20 bit size) *) let regen_size = match size_format with | 0 | 2 -> (* 5-bit size is in upper 5 bits of first byte *) header_byte lsr 3 | 1 -> (* 12-bit size: 4 bits from first byte + 8 bits from second *) let high = header_byte lsr 4 in let low = Bit_reader.Forward.read_byte stream in (low lsl 4) lor high | 3 | _ -> (* 20-bit size: 4 bits + 16 bits *) let high = header_byte lsr 4 in let b1 = Bit_reader.Forward.read_byte stream in let b2 = Bit_reader.Forward.read_byte stream in (b2 lsl 12) lor (b1 lsl 4) lor high in
if regen_size > Constants.max_literals_size then raise (Constants.Zstd_error Constants.Invalid_literals_header);
begin match Constants.literals_block_type_of_int block_type with | Raw_literals -> if regen_size > 0 then begin let data = Bit_reader.Forward.get_bytes stream regen_size in Bytes.blit data 0 output out_pos regen_size end | RLE_literals -> if regen_size > 0 then begin let byte = Bit_reader.Forward.read_byte stream in Bytes.fill output out_pos regen_size (Char.chr byte) end | _ -> () end; regen_size
| Compressed_literals | Treeless_literals -> let num_streams = if size_format = 0 then 1 else 4 in
(* For compressed: Size_Format determines header size 0: 1 stream, 3 bytes (10-bit sizes) 1: 4 streams, 3 bytes (10-bit sizes) 2: 4 streams, 4 bytes (14-bit sizes) 3: 4 streams, 5 bytes (18-bit sizes) *) let (regen_size, compressed_size) = match size_format with | 0 | 1 -> (* 3 bytes: 4 bits type+format, 10 bits regen, 10 bits compressed *) let b1 = Bit_reader.Forward.read_byte stream in let b2 = Bit_reader.Forward.read_byte stream in let high = header_byte lsr 4 in let regen = ((b1 land 0x3f) lsl 4) lor high in let comp = (b2 lsl 2) lor (b1 lsr 6) in (regen, comp) | 2 -> (* 4 bytes: 4 bits, 14 bits, 14 bits *) let b1 = Bit_reader.Forward.read_byte stream in let b2 = Bit_reader.Forward.read_byte stream in let b3 = Bit_reader.Forward.read_byte stream in let high = header_byte lsr 4 in let regen = (((b2 land 3) lsl 12) lor (b1 lsl 4) lor high) in let comp = (b3 lsl 6) lor (b2 lsr 2) in (regen, comp) | 3 | _ -> (* 5 bytes: 4 bits, 18 bits, 18 bits *) let b1 = Bit_reader.Forward.read_byte stream in let b2 = Bit_reader.Forward.read_byte stream in let b3 = Bit_reader.Forward.read_byte stream in let b4 = Bit_reader.Forward.read_byte stream in let high = header_byte lsr 4 in let regen = ((b2 land 0x3f) lsl 12) lor (b1 lsl 4) lor high in let comp = (b4 lsl 10) lor (b3 lsl 2) lor (b2 lsr 6) in (regen, comp) in
if regen_size > Constants.max_literals_size then raise (Constants.Zstd_error Constants.Invalid_literals_header);
(* Get compressed data *) let huf_data = Bit_reader.Forward.get_bytes stream compressed_size in let huf_stream = Bit_reader.Forward.of_bytes huf_data in
(* Decode Huffman table if not treeless *) let dtable = if block_type = 2 then begin let table = Huffman.decode_table huf_stream in ctx.huf_table <- Some table; table end else begin match ctx.huf_table with | Some t -> t | None -> raise (Constants.Zstd_error Constants.Invalid_huffman_table) end in
(* Decode literals *) let huf_pos = Bit_reader.Forward.byte_position huf_stream in let huf_len = compressed_size - huf_pos in
let written = if num_streams = 1 then Huffman.decompress_1stream dtable huf_data ~pos:huf_pos ~len:huf_len output ~out_pos ~out_len:regen_size else Huffman.decompress_4stream dtable huf_data ~pos:huf_pos ~len:huf_len output ~out_pos ~regen_size in
if written <> regen_size then raise (Constants.Zstd_error Constants.Corruption);
regen_size
(** Decode sequence table based on mode *)let decode_seq_table stream mode default_dist default_acc max_acc get_table set_table = match mode with | Constants.Predefined_mode -> set_table (Some (Fse.build_predefined_table default_dist default_acc)) | Constants.RLE_mode -> let symbol = Bit_reader.Forward.read_byte stream in set_table (Some (Fse.build_dtable_rle symbol)) | Constants.FSE_mode -> set_table (Some (Fse.decode_header stream max_acc)) | Constants.Repeat_mode -> match get_table () with | Some _ -> () | None -> raise (Constants.Zstd_error Constants.Invalid_fse_table)
(** Decode sequences section *)let decode_sequences ctx stream = (* Number of sequences *) let header = Bit_reader.Forward.read_byte stream in let num_sequences = if header < 128 then header else if header < 255 then let second = Bit_reader.Forward.read_byte stream in ((header - 128) lsl 8) + second else begin let low = Bit_reader.Forward.read_byte stream in let high = Bit_reader.Forward.read_byte stream in low + (high lsl 8) + 0x7F00 end in
if num_sequences = 0 then [||] else begin (* Compression modes byte (RFC 8878 section 3.1.1.3.2.1): bits 0-1: Literals_Lengths_Mode bits 2-3: Offsets_Mode bits 4-5: Match_Lengths_Mode bits 6-7: reserved (must be 0) *) let modes = Bit_reader.Forward.read_byte stream in if (modes lsr 6) land 3 <> 0 then raise (Constants.Zstd_error Constants.Invalid_sequence_header);
let ll_mode = Constants.seq_mode_of_int (modes land 3) in let of_mode = Constants.seq_mode_of_int ((modes lsr 2) land 3) in let ml_mode = Constants.seq_mode_of_int ((modes lsr 4) land 3) in
(* Decode tables *) decode_seq_table stream ll_mode Constants.ll_default_distribution Constants.ll_default_accuracy_log Constants.ll_max_accuracy_log (fun () -> ctx.ll_table) (fun t -> ctx.ll_table <- t);
decode_seq_table stream of_mode Constants.of_default_distribution Constants.of_default_accuracy_log Constants.of_max_accuracy_log (fun () -> ctx.of_table) (fun t -> ctx.of_table <- t);
decode_seq_table stream ml_mode Constants.ml_default_distribution Constants.ml_default_accuracy_log Constants.ml_max_accuracy_log (fun () -> ctx.ml_table) (fun t -> ctx.ml_table <- t);
let ll_table = Option.get ctx.ll_table in let of_table = Option.get ctx.of_table in let ml_table = Option.get ctx.ml_table in
(* Get remaining bytes for FSE decoding *) let remaining = Bit_reader.Forward.remaining_bytes stream in let seq_data = Bit_reader.Forward.get_bytes stream remaining in
(* Create backward stream *) let bstream = Bit_reader.Backward.of_bytes seq_data ~pos:0 ~len:remaining in
(* Initialize states *) let ll_state = ref (Fse.init_state ll_table bstream) in let of_state = ref (Fse.init_state of_table bstream) in let ml_state = ref (Fse.init_state ml_table bstream) in
(* Decode sequences *) let sequences = Array.init num_sequences (fun i -> let of_code = Fse.peek_symbol of_table !of_state in let ll_code = Fse.peek_symbol ll_table !ll_state in let ml_code = Fse.peek_symbol ml_table !ml_state in
if ll_code > Constants.ll_max_code || ml_code > Constants.ml_max_code then raise (Constants.Zstd_error Constants.Corruption);
(* Read extra bits: offset, match_length, literal_length *) let offset = (1 lsl of_code) + Bit_reader.Backward.read_bits bstream of_code in let match_length = Constants.ml_baselines.(ml_code) + Bit_reader.Backward.read_bits bstream Constants.ml_extra_bits.(ml_code) in let literal_length = Constants.ll_baselines.(ll_code) + Bit_reader.Backward.read_bits bstream Constants.ll_extra_bits.(ll_code) in
(* Update states (except for last sequence) *) if i < num_sequences - 1 then begin ll_state := Fse.update_state ll_table !ll_state bstream; ml_state := Fse.update_state ml_table !ml_state bstream; of_state := Fse.update_state of_table !of_state bstream end;
{ literal_length; match_length; offset } ) in
(* Verify stream is consumed *) if Bit_reader.Backward.remaining bstream <> 0 then raise (Constants.Zstd_error Constants.Corruption);
sequences end
(** Compute actual offset from sequence offset value *)let compute_offset seq repeat_offsets = let offset_value = seq.offset in if offset_value > 3 then begin (* Real offset: shift history and use value - 3 *) let actual_offset = offset_value - 3 in repeat_offsets.(2) <- repeat_offsets.(1); repeat_offsets.(1) <- repeat_offsets.(0); repeat_offsets.(0) <- actual_offset; actual_offset end else begin (* Repeat offset *) let idx = offset_value - 1 in let idx = if seq.literal_length = 0 then idx + 1 else idx in
let actual_offset = if idx = 3 then repeat_offsets.(0) - 1 else repeat_offsets.(idx) in
(* Update history *) if idx > 0 then begin if idx > 1 then repeat_offsets.(2) <- repeat_offsets.(1); repeat_offsets.(1) <- repeat_offsets.(0); repeat_offsets.(0) <- actual_offset end;
actual_offset end
(** Execute sequences to produce output *)let execute_sequences ctx sequences literals ~lit_len output ~out_pos = let lit_pos = ref 0 in let out = ref out_pos in
for i = 0 to Array.length sequences - 1 do let seq = sequences.(i) in
(* Copy literals *) if seq.literal_length > 0 then begin if !lit_pos + seq.literal_length > lit_len then raise (Constants.Zstd_error Constants.Corruption); Bytes.blit literals !lit_pos output !out seq.literal_length; lit_pos := !lit_pos + seq.literal_length; out := !out + seq.literal_length end;
(* Compute actual offset *) let offset = compute_offset seq ctx.repeat_offsets in
(* Validate offset *) let total_available = ctx.total_output + (!out - out_pos) in let dict_len = Option.fold ~none:0 ~some:Bytes.length ctx.dict_content in
if offset > total_available + dict_len then raise (Constants.Zstd_error Constants.Invalid_offset);
(* Copy match *) let match_length = seq.match_length in if offset > total_available then begin (* Part of match is from dictionary *) let dict = Option.get ctx.dict_content in let dict_copy = min (offset - total_available) match_length in let dict_offset = dict_len - (offset - total_available) in Bytes.blit dict dict_offset output !out dict_copy; out := !out + dict_copy;
(* Rest from output buffer *) for _ = dict_copy to match_length - 1 do Bytes.set output !out (Bytes.get output (!out - offset)); incr out done end else begin (* Match is entirely in output buffer *) (* Note: may overlap, so copy byte-by-byte for small offsets *) for _ = 0 to match_length - 1 do Bytes.set output !out (Bytes.get output (!out - offset)); incr out done end done;
(* Copy remaining literals *) let remaining = lit_len - !lit_pos in if remaining > 0 then begin Bytes.blit literals !lit_pos output !out remaining; out := !out + remaining end;
!out - out_pos
(** Decompress a single block *)let decompress_block ctx stream output ~out_pos = (* Decode literals *) let literals = Bytes.create Constants.max_literals_size in let lit_len = decode_literals ctx stream literals ~out_pos:0 in
(* Decode and execute sequences *) let sequences = decode_sequences ctx stream in
let written = execute_sequences ctx sequences literals ~lit_len output ~out_pos in ctx.total_output <- ctx.total_output + written; written
(** Decompress frame data (all blocks) *)let decompress_data ctx stream output ~out_pos = let written = ref 0 in let last_block = ref false in
while not !last_block do let header = Bit_reader.Forward.read_bits stream 24 in last_block := (header land 1) = 1; let block_type = Constants.block_type_of_int ((header lsr 1) land 3) in let block_size = header lsr 3 in
if block_size > Constants.block_size_max then raise (Constants.Zstd_error Constants.Invalid_block_size);
match block_type with | Raw_block -> let data = Bit_reader.Forward.get_bytes stream block_size in Bytes.blit data 0 output (out_pos + !written) block_size; written := !written + block_size; ctx.total_output <- ctx.total_output + block_size
| RLE_block -> let byte = Bit_reader.Forward.read_byte stream in Bytes.fill output (out_pos + !written) block_size (Char.chr byte); written := !written + block_size; ctx.total_output <- ctx.total_output + block_size
| Compressed_block -> let block_data = Bit_reader.Forward.get_bytes stream block_size in let block_stream = Bit_reader.Forward.of_bytes block_data in let block_written = decompress_block ctx block_stream output ~out_pos:(out_pos + !written) in written := !written + block_written
| Reserved_block -> raise (Constants.Zstd_error Constants.Invalid_block_type) done;
!written
(** Create initial frame context *)let create_frame_context (header : frame_header) (dict_opt : dictionary option) : frame_context = let huf_table = Option.bind dict_opt (fun (d : dictionary) -> d.huf_table) in let ll_table = Option.map (fun (d : dictionary) -> d.ll_table) dict_opt in let ml_table = Option.map (fun (d : dictionary) -> d.ml_table) dict_opt in let of_table = Option.map (fun (d : dictionary) -> d.of_table) dict_opt in let repeat_offsets = Option.fold ~none:(Array.copy Constants.initial_repeat_offsets) ~some:(fun (d : dictionary) -> Array.copy d.repeat_offsets) dict_opt in let dict_content = Option.map (fun (d : dictionary) -> d.content) dict_opt in { huf_table; ll_table; ml_table; of_table; repeat_offsets; total_output = 0; dict = dict_opt; dict_content; window_size = header.window_size }
(** Decompress a single frame *)let decompress_frame ?dict src ~pos ~len = let stream = Bit_reader.Forward.create src ~pos ~len in
(* Check magic number *) let magic = Bit_reader.Forward.read_bits stream 32 in if Int32.of_int magic <> Constants.zstd_magic_number then raise (Constants.Zstd_error Constants.Invalid_magic_number);
(* Parse header *) let header = parse_frame_header stream in
(* Validate dictionary if required *) begin match header.dictionary_id, dict with | Some id, Some d when id <> d.dict_id -> raise (Constants.Zstd_error Constants.Dictionary_mismatch) | Some _, None -> raise (Constants.Zstd_error Constants.Dictionary_mismatch) | _ -> () end;
(* Determine output size *) let output_size = match header.frame_content_size with | Some size -> Int64.to_int size | None -> header.window_size * 2 (* Estimate *) in
let output = Bytes.create output_size in let ctx = create_frame_context header dict in
(* Decompress all blocks *) let written = decompress_data ctx stream output ~out_pos:0 in
(* Verify checksum if present *) if header.content_checksum then begin let expected = Bit_reader.Forward.read_bits stream 32 in let actual = Xxhash.hash32 output ~pos:0 ~len:written in if Int32.of_int expected <> actual then raise (Constants.Zstd_error Constants.Checksum_mismatch) end;
Bytes.sub output 0 written
(** Get decompressed size from frame header (if available) *)let get_decompressed_size src ~pos ~len = let stream = Bit_reader.Forward.create src ~pos ~len in
let magic = Bit_reader.Forward.read_bits stream 32 in if Int32.of_int magic <> Constants.zstd_magic_number then None else begin let header = parse_frame_header stream in header.frame_content_size end
(** Check if a magic number is a skippable frame magic *)let[@inline] is_skippable_magic magic = Int32.equal (Int32.logand magic Constants.skippable_magic_mask) Constants.skippable_magic_start
(** Check if data starts with skippable frame magic *)let is_skippable_frame src ~pos ~len = len >= 4 && is_skippable_magic (Bytes.get_int32_le src pos)
(** Get skippable frame variant (0-15) *)let get_skippable_variant src ~pos ~len = if len < 4 then None else let magic = Bytes.get_int32_le src pos in if is_skippable_magic magic then Some (Int32.to_int (Int32.logand magic 0xFl)) else None
(** Get skippable frame size (returns total frame size including header) *)let get_skippable_frame_size src ~pos ~len = if len < 8 then None else if not (is_skippable_frame src ~pos ~len) then None else let content_size = Int32.to_int (Bytes.get_int32_le src (pos + 4)) in Some (Constants.skippable_header_size + content_size)
(** Skip skippable frame and return content + next position *)let read_skippable_frame src ~pos ~len = if len < 8 then raise (Constants.Zstd_error Constants.Truncated_input); if not (is_skippable_frame src ~pos ~len) then raise (Constants.Zstd_error Constants.Invalid_magic_number); let content_size = Int32.to_int (Bytes.get_int32_le src (pos + 4)) in let total_size = Constants.skippable_header_size + content_size in if len < total_size then raise (Constants.Zstd_error Constants.Truncated_input); let content = Bytes.sub src (pos + 8) content_size in (content, pos + total_size)
(** Find compressed size of first frame (zstd or skippable) *)let find_frame_compressed_size src ~pos ~len = if len < 4 then raise (Constants.Zstd_error Constants.Truncated_input); let magic = Bytes.get_int32_le src pos in if is_skippable_magic magic then begin (* Skippable frame *) if len < 8 then raise (Constants.Zstd_error Constants.Truncated_input); let content_size = Int32.to_int (Bytes.get_int32_le src (pos + 4)) in Constants.skippable_header_size + content_size end else if Int32.equal magic Constants.zstd_magic_number then begin (* Regular zstd frame - need to scan through blocks *) let stream = Bit_reader.Forward.create src ~pos ~len in (* Skip magic *) let _ = Bit_reader.Forward.read_bits stream 32 in (* Parse header to get size *) let header = parse_frame_header stream in (* Now scan through blocks *) let last_block = ref false in while not !last_block do let block_header = Bit_reader.Forward.read_bits stream 24 in last_block := (block_header land 1) = 1; let block_type = (block_header lsr 1) land 3 in let block_size = block_header lsr 3 in (* Skip block content *) let bytes_to_skip = match block_type with | 0 -> block_size (* Raw *) | 1 -> 1 (* RLE: single byte *) | 2 -> block_size (* Compressed *) | _ -> raise (Constants.Zstd_error Constants.Invalid_block_type) in ignore (Bit_reader.Forward.get_bytes stream bytes_to_skip) done; (* Add checksum if present *) if header.content_checksum then ignore (Bit_reader.Forward.read_bits stream 32); Bit_reader.Forward.byte_position stream end else raise (Constants.Zstd_error Constants.Invalid_magic_number)
(** Decompress all frames (zstd and skippable) concatenated together *)let decompress_frames ?dict src ~pos ~len = let results = ref [] in let current_pos = ref pos in let remaining = ref len in
while !remaining > 0 do if !remaining < 4 then raise (Constants.Zstd_error Constants.Truncated_input); let magic = Bytes.get_int32_le src !current_pos in
if is_skippable_magic magic then begin (* Skippable frame - skip it *) match get_skippable_frame_size src ~pos:!current_pos ~len:!remaining with | Some frame_size -> current_pos := !current_pos + frame_size; remaining := !remaining - frame_size | None -> raise (Constants.Zstd_error Constants.Truncated_input) end else if Int32.equal magic Constants.zstd_magic_number then begin (* Regular zstd frame *) let frame_size = find_frame_compressed_size src ~pos:!current_pos ~len:!remaining in let result = decompress_frame ?dict src ~pos:!current_pos ~len:frame_size in results := result :: !results; current_pos := !current_pos + frame_size; remaining := !remaining - frame_size end else raise (Constants.Zstd_error Constants.Invalid_magic_number) done;
(* Concatenate results in order *) let results_rev = List.rev !results in let total_len = List.fold_left (fun acc b -> acc + Bytes.length b) 0 results_rev in let output = Bytes.create total_len in ignore (List.fold_left (fun pos b -> let len = Bytes.length b in Bytes.blit b 0 output pos len; pos + len ) 0 results_rev); output
(** Parse dictionary *)let parse_dictionary src ~pos ~len = let stream = Bit_reader.Forward.create src ~pos ~len in
let magic = Bit_reader.Forward.read_bits stream 32 in if Int32.of_int magic <> Constants.dict_magic_number then begin (* Raw content dictionary (no magic) *) { dict_id = 0l; huf_table = None; ll_table = Fse.build_predefined_table Constants.ll_default_distribution Constants.ll_default_accuracy_log; ml_table = Fse.build_predefined_table Constants.ml_default_distribution Constants.ml_default_accuracy_log; of_table = Fse.build_predefined_table Constants.of_default_distribution Constants.of_default_accuracy_log; content = Bytes.sub src pos len; repeat_offsets = Array.copy Constants.initial_repeat_offsets; } end else begin (* Formatted dictionary *) let dict_id = Int32.of_int (Bit_reader.Forward.read_bits stream 32) in
(* Decode entropy tables *) let huf_table = Some (Huffman.decode_table stream) in
(* Decode FSE tables (always FSE mode for dictionaries) *) let of_table = Fse.decode_header stream Constants.of_max_accuracy_log in let ml_table = Fse.decode_header stream Constants.ml_max_accuracy_log in let ll_table = Fse.decode_header stream Constants.ll_max_accuracy_log in
(* Read repeat offsets *) let repeat_offsets = Array.init 3 (fun _ -> Bit_reader.Forward.read_bits stream 32 ) in
(* Remaining is content *) let content_pos = Bit_reader.Forward.byte_position stream in let content_len = len - content_pos in let content = Bytes.sub src (pos + content_pos) content_len in
{ dict_id; huf_table; ll_table; ml_table; of_table; content; repeat_offsets } end