package duff

You can search for identifiers within the package.

in-package search v0.2.0

Rabin's fingerprint and diff algorithm in OCaml

Install

dune-project

Dependency

sha256=f9453cf4aa3b6850efe8cc6f13f053ebe5f2111faf177ceabfbb03e5d9ad6ede

sha512=a063a549af860db2e66be5ec0c4bfb827e1fe7284c669562455cdd5ae5fa760cbeb878663ceadf93a8d7350f7eab926740fdef2e7bf7eaf2c2e605ec532eb70e

Rabin's fingerprint and diff algorithm.

Let's take a random buffer a. We can produce from it an index which is a (lightweight) simple table of occurences (string) found into a.

From this index, we can get a diff with another random buffer b such as:

  let index = make a in
  let diff = delta index ~source:a ~target:b in
  assert (apply a diff = b)

A diff is a list of hunk. apply is a simple function which needs the source a to reconstruct b.

type bigstring =
  (char, Bigarray.int8_unsigned_elt, Bigarray.c_layout) Bigarray.Array1.t

Sourcetype index

The type of the index.

Sourceval pp_index : index Fmt.t

Pretty-printer of index.

Sourceval make : bigstring -> index

make source returns a fingerprint of source.

Sourcetype hunk =

| Copy of int * int
(*
It's the copy ((off, len)) opcode to copy len byte(s) range from the source at off to the target.
*)
| Insert of int * int
(*
It's the insert (off, len) opcode to keep a specific byte range of len bytes of the target at off.
*)

The type of the compression.

Sourceval pp_hunk : hunk Fmt.t

Pretty-printer of hunk.

Sourceval delta : index -> source:bigstring -> target:bigstring -> hunk list

delta index ~source ~target returns a compression list between the Rabin's fingerprint of a source index with the target target.

Note: the given source must be the same (not necessary physically) than the source used to produce index with make.