package duff
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=583ec0c2a768331dad4b7057e6edd8966296698052cb6403c32c91417840202e
md5=b0a60ff1efb160b1ded56c640b874be3
Description
This library provides a pure implementation of Rabin's fingerprint and diff algorithm in OCaml.
It follows libXdiff C library. It is used by ocaml-git project.
Published: 16 Oct 2018
README
Duff – libXdiff implementation in OCaml
Duff is a little library to implement libXdiff in OCaml. This library is a part of the ocaml-git project. This code is a translation of diff-delta.c
available on the git project in OCaml. So, it respects some git's constraints unlike libXdiff.
Examples
This library let the user to calculate an Index.t
from a source (a hash-table) which can be computed with a blob. Then, from Index.t
(which represents your source) and a blob, we generate a list of Copy
and Insert
elements.
Copy (off, len)
means to take a slice oflen
bytes from your source atoff
(absolute offset) and copy it.Insert (off, len)
means to store a slice oflen
bytes from your blob atoff
(absolute offset) and copy it.
From this information, we can have a tiny representation of your blob which can be reconstruct with your source. The goal is to store Copy
opcode with off
and len
, and Insert
opcode which contains entirely slice of your blob.
Finally, to produce a PACK file in git or ocaml-git, we use this algorithm and this representation to optimize storage of your blobs (cf. git gc
).
Binary
You can see an example of duff
in bin
directory. It's an executable to represent a thin representation of your file. Then, you can reconstruct it with patch
sub-command.
This is an example to use duff
:
$ ./duff.exe diff source target > target.xduff
$ ./duff.exe patch source < target.xduff > target.new
$ diff target target.new
$ echo $?
0
The internal format used is close to what git
does internally (without zlib
layer). However, it does not correspond to an official format.
Limitations
Because this project is used by ocaml-git, we have some limitations:
We compute at most
0xFFFFFFFE
bytes from sourceAn
insert
block can not be bigger than0x10000
bytes
For example, libXdiff computes a bigger source than this implementation. Then, limitation about insert
block depends on the PACK (git) file format. So, don't ask me to compute bigger source or merge and produce bigger insert
block - these constraints is outside this library.
From this limitation, Copy
opcode have an offset between 0x0 and 0xFFFFFFE and off + len
is lower than 0xFFFFFFFE.
Fuzzer
We provide a fuzzer to randomly test this library. Currently (4/9/2018), afl-fuzz
did not find any bugs and it computed 67.7k cycles (117 paths).