Something went wrong. Try again.
My own corner of monopam
Something went wrong. Try again.
13 kB · 329 lines
OCaml
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330open Bytesrw
let str = Alcotest.stringlet get c f = Wire.Staged.unstage (Wire.Codec.get c f)let set c f = Wire.Staged.unstage (Wire.Codec.set c f)
(* Encode a BSDIFF40 integer: 64-bit little-endian sign-and-magnitude (bsdiff.c's offtout). Used to hand-craft patches independently of the library's own encoder. *)let offt v = let mag = Int64.of_int (abs v) in let w = if v < 0 then Int64.logor mag Int64.min_int else mag in String.init 8 (fun i -> Char.chr (Int64.to_int (Int64.shift_right_logical w (8 * i)) land 0xff))
let u64_of_string8 s = if String.length s <> 8 then invalid_arg "u64_of_string8"; Bytes.get_int64_le (Bytes.unsafe_of_string s) 0
let bz2 s = Bytes.Reader.filter_string [ Bytesrw_bz2.compress_reads () ] s
let contains haystack needle = let len = String.length needle in let max = String.length haystack - len in let rec loop i = i <= max && (String.sub haystack i len = needle || loop (i + 1)) in loop 0
let schema_source codec = let schema = Wire.Everparse.project ~mode:`Standalone codec in Wire.Everparse.Raw.to_3d ~enum_as_type:true schema.module_
(* Assemble a patch from raw sections, bzip2ing them like bsdiff does. *)let patch_of_sections ?new_size ~ctrl ~diff ~extra () = let bz_ctrl = bz2 ctrl and bz_diff = bz2 diff and bz_extra = bz2 extra in let new_size = match new_size with Some n -> n | None -> String.length diff in String.concat "" [ "BSDIFF40"; offt (String.length bz_ctrl); offt (String.length bz_diff); offt new_size; bz_ctrl; bz_diff; bz_extra; ]
let test_roundtrips () = List.iter (fun (name, source, target) -> let patch = Bsdiff.diff ~source ~target in Alcotest.check str name target (Bsdiff.apply_exn ~source patch)) [ ("identical", "same bytes", "same bytes"); ("empty both", "", ""); ("empty source", "", "built from nothing, long enough to matter"); ("empty target", "something", ""); ("disjoint", String.make 64 'a', String.make 64 'z'); ( "edit in the middle", "the quick brown fox jumps over the lazy dog", "the quick brown cat jumps over the lazy dog!" ); ( "binary with small deltas", String.init 4096 (fun i -> Char.chr (i * 31 land 0xff)), String.init 4096 (fun i -> Char.chr ((i * 31 land 0xff) + if i mod 100 = 0 then 1 else 0)) ); ( "moved block", String.concat "" [ String.make 300 'A'; String.make 300 'B' ], String.concat "" [ String.make 300 'B'; String.make 300 'A' ] ); ]
let test_container_layout () = let patch = Bsdiff.diff ~source:"abcdef" ~target:"abcdef!" in Alcotest.check str "magic" "BSDIFF40" (String.sub patch 0 8); (* The three streams are bzip2: each starts with the BZh marker. *) let int_at off = let b i = Int64.of_int (Char.code patch.[off + i]) in let v = ref 0L in for i = 7 downto 0 do v := Int64.logor (Int64.shift_left !v 8) (b i) done; Int64.to_int (Int64.logand !v Int64.max_int) in let ctrl_len = int_at 8 and diff_len = int_at 16 in Alcotest.check str "ctrl stream magic" "BZh" (String.sub patch 32 3); Alcotest.check str "diff stream magic" "BZh" (String.sub patch (32 + ctrl_len) 3); Alcotest.check str "extra stream magic" "BZh" (String.sub patch (32 + ctrl_len + diff_len) 3)
let test_schema_constrains_magic () = let schema = schema_source Bsdiff.header_codec in Alcotest.(check bool) "magic constrained to BSDIFF40" true (contains schema "UINT64 magic { (magic == 3473478480300364610) }")
(* The magic renders as a bare decimal and seek is a UINT64 carrying a sign-and-magnitude value (not two's complement), so both must be explained in the .3d docs or a reader will misread them. *)let test_schema_documents_magic_and_seek () = let h = schema_source Bsdiff.header_codec in Alcotest.(check bool) "header doc bridges the magic to BSDIFF40 hex" true (contains h "0x3034464649445342"); let c = schema_source Bsdiff.triple_codec in Alcotest.(check bool) "control doc flags the seek as sign-and-magnitude" true (contains c "sign-and-magnitude")
(* A hand-crafted control program: mix 3 bytes with the source, insert 2 extra bytes, seek backwards, mix 2 more. *)let test_handcrafted_program () = let source = "ABCDE" in let ctrl = offt 3 ^ offt 2 ^ offt (-3) ^ offt 2 ^ offt 0 ^ offt 0 in let diff = "\x01\x01\x01\x00\x00" in let extra = "xy" in let patch = patch_of_sections ~new_size:7 ~ctrl ~diff ~extra () in (* ABC+1 = BCD, insert xy, seek back to source position 0, AB+0 = AB. *) Alcotest.check str "applied" "BCDxyAB" (Bsdiff.apply_exn ~source patch)
let test_control_field_handles () = let ctrl = Bytes.make 24 '\000' in let raw_seek = u64_of_string8 (offt (-3)) in set Bsdiff.triple_codec Bsdiff.mix ctrl 0 3; set Bsdiff.triple_codec Bsdiff.copy ctrl 0 2; set Bsdiff.triple_codec Bsdiff.seek ctrl 0 raw_seek; Alcotest.(check int) "mix field reads back as a size" 3 (get Bsdiff.triple_codec Bsdiff.mix ctrl 0); Alcotest.(check int) "copy field reads back as a size" 2 (get Bsdiff.triple_codec Bsdiff.copy ctrl 0); Alcotest.(check int64) "seek field reads back as raw sign-magnitude" raw_seek (get Bsdiff.triple_codec Bsdiff.seek ctrl 0); Alcotest.(check int) "seek is encoded as sign-magnitude" 0x80 (Char.code (Bytes.get ctrl 23)); let patch = patch_of_sections ~new_size:5 ~ctrl:(Bytes.unsafe_to_string ctrl) ~diff:"\x01\x01\x01" ~extra:"xy" () in Alcotest.check str "field-written control applies" "BCDxy" (Bsdiff.apply_exn ~source:"ABCDE" patch)
(* Mixing past the end of the source keeps the bare diff bytes, mirroring bspatch's bounds check rather than failing. *)let test_mix_past_source_end () = let source = "AB" in let ctrl = offt 4 ^ offt 0 ^ offt 0 in let diff = "\x01\x01\x41\x42" in let patch = patch_of_sections ~ctrl ~diff ~extra:"" () in Alcotest.check str "applied" "BCAB" (Bsdiff.apply_exn ~source patch)
let check_error name patch pred = match Bsdiff.apply ~source:"some source bytes" patch with | Ok _ -> Alcotest.failf "%s: expected an error" name | Error e -> if not (pred (Loc.Error.kind e)) then Alcotest.failf "%s: wrong error: %s" name (Bsdiff.Error.to_string e)
let hostile_cases = let open Bsdiff.Error in let valid = patch_of_sections ~ctrl:(offt 1 ^ offt 0 ^ offt 0) ~diff:"x" ~extra:"" () in [ ("empty", "", function Truncated _ -> true | _ -> false); ("magic prefix", "BSDIF", function Truncated _ -> true | _ -> false); ( "bad magic", "NOTDIFF0" ^ String.make 24 '\x00', function Magic_mismatch "NOTDIFF0" -> true | _ -> false ); ( "sign-bit ctrl length", "BSDIFF40" ^ offt (-1) ^ offt 0 ^ offt 0, function Corrupt _ -> true | _ -> false ); ( "sections beyond patch", "BSDIFF40" ^ offt 1000 ^ offt 0 ^ offt 0, function Truncated _ -> true | _ -> false ); ( "garbage sections", "BSDIFF40" ^ offt 4 ^ offt 4 ^ offt 4 ^ "abcdefgh", function Corrupt _ -> true | _ -> false ); ( "ragged control section", patch_of_sections ~new_size:0 ~ctrl:"12345" ~diff:"" ~extra:"" (), function Corrupt _ -> true | _ -> false ); ( "sign-bit mix", patch_of_sections ~new_size:1 ~ctrl:(offt (-2) ^ offt 0 ^ offt 0) ~diff:"x" ~extra:"" (), function Corrupt _ -> true | _ -> false ); ( "seek magnitude over native int", patch_of_sections ~new_size:0 ~ctrl:(offt 0 ^ offt 0 ^ String.make 8 '\xff') ~diff:"" ~extra:"" (), function Corrupt _ -> true | _ -> false ); ( "target size overrun", patch_of_sections ~new_size:1 ~ctrl:(offt 2 ^ offt 0 ^ offt 0) ~diff:"xy" ~extra:"" (), function Invalid _ -> true | _ -> false ); ( "diff section overrun", patch_of_sections ~new_size:4 ~ctrl:(offt 4 ^ offt 0 ^ offt 0) ~diff:"x" ~extra:"" (), function Invalid _ -> true | _ -> false ); ( "extra section overrun", patch_of_sections ~new_size:4 ~ctrl:(offt 0 ^ offt 4 ^ offt 0) ~diff:"" ~extra:"x" (), function Invalid _ -> true | _ -> false ); ( "declared size not reached", patch_of_sections ~new_size:9 ~ctrl:(offt 1 ^ offt 0 ^ offt 0) ~diff:"x" ~extra:"" (), function Invalid _ -> true | _ -> false ); ( "truncated bz2 stream", (let n = String.length valid in String.sub valid 0 (n - 4)), function Corrupt _ | Invalid _ -> true | _ -> false ); ]
let test_hostile () = List.iter (fun (name, patch, pred) -> check_error name patch pred) hostile_cases
(* Patches stay small when source and target share content. *)let test_patch_size () = let source = String.init 8192 (fun i -> Char.chr (i * 31 land 0xff)) in let target = String.sub source 7 8000 ^ "tail" in let patch = Bsdiff.diff ~source ~target in Alcotest.check str "applies" target (Bsdiff.apply_exn ~source patch); if String.length patch >= 256 then Alcotest.failf "patch too large: %d bytes for an 8004-byte target" (String.length patch)
(* [apply_writer] streams the target to a sink; collect it into a string so it can be compared byte-for-byte with the in-RAM [apply_exn]. *)let apply_streaming ~source patch = let buf = Buffer.create 256 in let w = Bytes.Writer.of_buffer buf in Bsdiff.apply_writer_exn ~source patch w; Buffer.contents buf
(* The streaming apply must reconstruct exactly the same bytes as the in-RAM apply, including across many decompressed slices (the large vector forces mix/copy runs that span more than one [io_buffer_size] slice). *)let test_streaming_matches_apply () = let big_source = String.init 200_000 (fun i -> Char.chr (i * 31 land 0xff)) in let big_target = String.init 200_000 (fun i -> Char.chr ((i * 31 land 0xff) + if i mod 64 = 0 then 1 else 0)) in List.iter (fun (name, source, target) -> let patch = Bsdiff.diff ~source ~target in Alcotest.check str (name ^ ": in-RAM") target (Bsdiff.apply_exn ~source patch); Alcotest.check str (name ^ ": streaming") target (apply_streaming ~source patch)) [ ("identical", "same bytes", "same bytes"); ("empty both", "", ""); ("empty source", "", "built from nothing, long enough to matter"); ("empty target", "something", ""); ("disjoint", String.make 64 'a', String.make 64 'z'); ( "edit in the middle", "the quick brown fox jumps over the lazy dog", "the quick brown cat jumps over the lazy dog!" ); ( "moved block", String.concat "" [ String.make 300 'A'; String.make 300 'B' ], String.concat "" [ String.make 300 'B'; String.make 300 'A' ] ); ("large with small deltas", big_source, big_target); ]
(* Hand-crafted control programs apply identically through the streaming path, including a backward seek and mixing past the end of the source. *)let test_streaming_handcrafted () = let source = "ABCDE" in let ctrl = offt 3 ^ offt 2 ^ offt (-3) ^ offt 2 ^ offt 0 ^ offt 0 in let patch = patch_of_sections ~new_size:7 ~ctrl ~diff:"\x01\x01\x01\x00\x00" ~extra:"xy" () in Alcotest.check str "program" "BCDxyAB" (apply_streaming ~source patch); let patch = patch_of_sections ~ctrl:(offt 4 ^ offt 0 ^ offt 0) ~diff:"\x01\x01\x41\x42" ~extra:"" () in Alcotest.check str "mix past source end" "BCAB" (apply_streaming ~source:"AB" patch)
(* The streaming path must reject every malformed patch the in-RAM path does; it must never silently produce a partial or wrong target. *)let test_streaming_rejects_hostile () = List.iter (fun (name, patch, _pred) -> let buf = Buffer.create 16 in let w = Bytes.Writer.of_buffer buf in match Bsdiff.apply_writer ~source:"some source bytes" patch w with | Ok () -> Alcotest.failf "%s: expected an error" name | Error _ -> ()) hostile_cases
let suite = ( "bsdiff", [ Alcotest.test_case "roundtrips" `Quick test_roundtrips; Alcotest.test_case "container layout" `Quick test_container_layout; Alcotest.test_case "schema constrains magic" `Quick test_schema_constrains_magic; Alcotest.test_case "schema documents magic/seek" `Quick test_schema_documents_magic_and_seek; Alcotest.test_case "hand-crafted program" `Quick test_handcrafted_program; Alcotest.test_case "control field handles" `Quick test_control_field_handles; Alcotest.test_case "mix past source end" `Quick test_mix_past_source_end; Alcotest.test_case "hostile patches" `Quick test_hostile; Alcotest.test_case "patch size" `Quick test_patch_size; Alcotest.test_case "streaming matches apply" `Quick test_streaming_matches_apply; Alcotest.test_case "streaming hand-crafted" `Quick test_streaming_handcrafted; Alcotest.test_case "streaming rejects hostile" `Quick test_streaming_rejects_hostile; ] )