package duff

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

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 index

The type of the index.

val pp_index : index Fmt.t

Pretty-printer of index.

val make : bigstring -> index

make source returns a fingerprint of source.

type hunk =
  1. | 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.

    *)
  2. | 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.

val pp_hunk : hunk Fmt.t

Pretty-printer of hunk.

val 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.

OCaml

Innovation. Community. Security.