fdelta

package module
v0.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 23, 2026 License: BSD-2-Clause Imports: 5 Imported by: 1

README

fdelta

Go Reference

Fossil delta compression for Go.

Instead of storing or transmitting the whole of something, store or transmit only what changed relative to a version the other side already has. Create builds the diff, Apply reconstructs the new bytes from the old ones plus the diff.

Other implementations:

Deltas are portable in both directions between all of them.

Install

go get github.com/centrifugal/fdelta

No dependencies and no cgo: go.mod has no require block, and importing the package pulls in nothing beyond encoding/binary, math/bits, slices, errors and sync.

Example

package main

import (
	"fmt"

	"github.com/centrifugal/fdelta"
)

func main() {
	origin := []byte(`{"user":"alice","status":"online","score":1200,"rank":"gold"}`)
	target := []byte(`{"user":"alice","status":"online","score":1350,"rank":"gold"}`)

	delta := fdelta.Create(origin, target)

	patched, err := fdelta.Apply(origin, delta)
	if err != nil {
		panic(err)
	}

	fmt.Printf("target: %d bytes\n", len(target)) // target: 61 bytes
	fmt.Printf("delta:  %d bytes\n", len(delta))  // delta:  32 bytes
	fmt.Printf("match:  %v\n", string(patched) == string(target))
}

Create always succeeds, but a delta is not always worth sending: for payloads with little in common it comes out larger than the payload itself. Compare len(delta) against len(target) and send whichever is smaller.

API

func Create(origin, target []byte) []byte
func Apply(origin, delta []byte) ([]byte, error)

// Appending forms, for callers reusing a buffer.
func AppendCreate(dst, origin, target []byte) []byte
func AppendApply(dst, origin, delta []byte) ([]byte, error)

// The output size a delta declares, read from its header alone.
func OutputSize(delta []byte) (int, error)

Errors

Apply distinguishes the two failures a caller handles differently:

out, err := fdelta.Apply(base, delta)
switch {
case errors.Is(err, fdelta.ErrChecksumMismatch):
    // Well formed, but the output does not match its checksum: almost
    // always, base is not the source it was built from.
    // Ask for the payload in full.
case errors.Is(err, fdelta.ErrInvalidDelta):
    // The delta itself is corrupt.
}

It never panics, never returns partial output, and never allocates for a malformed delta — deltas usually arrive from somewhere else, so it is written to hold up against bytes chosen to break it.

A well formed delta is a different matter, and this is the one thing to know before applying deltas from an untrusted peer. A copy command costs about seven bytes and can copy the whole of origin, so a tiny delta can legitimately demand an enormous output. Against a 1 MiB origin, a 3.5 KB delta can ask for 500 MB; the ceiling is 4 GiB per call. That is inherent to the format, not to this implementation.

Call OutputSize first. It reads the header alone, allocates nothing, and Apply will not produce more than it reported:

if n, err := fdelta.OutputSize(delta); err != nil || n > maxPayload {
    // refuse, having done no work
}

The checksum is an integrity check, not authentication: whoever supplies the delta chooses the output and can supply a matching checksum. Nor is it a guarantee against a drifted base: it is a plain sum, fixed by the format, and some drifts leave it unchanged. See SECURITY.md.

Performance

Apple M4, Go 1.26, median of three runs. go test -bench . reproduces these.

Create, by payload size and shape of change:

payload one field changed block rewritten unchanged nothing in common
1 KiB 470 ns 1.40 µs 412 ns 3.30 µs
4 KiB 1.51 µs 3.80 µs 1.46 µs 12.3 µs
16 KiB 5.69 µs 15.2 µs 5.64 µs 57.0 µs
64 KiB 22.2 µs 171 µs 22.1 µs 287 µs

Apply:

payload time throughput
1 KiB 139 ns 7.4 GB/s
4 KiB 451 ns 9.1 GB/s
16 KiB 1.52 µs 10.8 GB/s
64 KiB 6.21 µs 10.6 GB/s

Create allocates once, for the delta itself — 128 bytes for a payload with one field changed, whatever its size, since the hash tables come from a pool. Apply allocates once, for the output, sized exactly by its validation pass; rejecting a malformed delta allocates nothing at all. AppendCreate and AppendApply remove even those: a 16 KiB payload applies in about 700 ns into a buffer that is already large enough, against 1.52 µs when the output has to be allocated and zeroed.

Notes on the encoder

Create does not emit the byte-for-byte delta the reference implementation would choose, though it emits one of the same size, and every implementation reads it.

The difference is in how a block hash is reduced to a bucket in the index the encoder builds over origin. The format's hash is concentrated — its low half is a plain byte sum, at most 4080 over a 16-byte window — so reducing it with a remainder leaves most buckets empty and the collision chains long. The modulus is the block count, which is a power of two whenever the payload is, and the hash's high half then cancels out of the remainder entirely: at 1 MiB that leaves 2.8% of buckets used and chains 120 long.

The effect on high-entropy payloads is severe, and worst at sizes a remote peer is quite likely to hit. A mebibyte of random bytes takes 292 ms to encode that way, against 13 ms for 1,000,000 random bytes — a 22x penalty for a 4.8% difference in size.

This package multiplies the hash by an odd constant and takes the high bits instead, folding every input bit into the bucket. Occupancy at 1 MiB goes to 55%, the longest chain to 10, and that mebibyte encodes in 17.8 ms, with the cost roughly linear in payload size and no dependence on whether that size is a power of two. The hash is the encoder's private index and never appears in a delta, so nothing about the format changes.

Testing

make test          # unit, differential, property and golden tests
make test-race
make test-cref     # additionally against Fossil's own delta.c
make check         # everything CI runs, bar the slow jobs

make on its own lists every target.

The cref tag compiles a vendored, unmodified copy of src/delta.c through cgo and runs this package against it: identical checksums and digit counts, deltas that apply in both directions, and no delta the reference accepts that this package does not accept to the same bytes. It needs a C toolchain, which is why it is behind a tag; an ordinary go test needs nothing.

Interoperability is checked in two directions that matter. delta.c is the reference, and make interop-js runs this encoder's deltas through the JavaScript decoder from fossil-delta-js — the code browsers actually run, since Centrifugo's JavaScript SDK vendors it.

testdata/fossil-vectors/ holds frozen origin/target/delta triples whose deltas were produced by Fossil itself, and testdata/golden.txt pins what this encoder emits. Seven fuzz targets run in CI on every push and for ten minutes each weekly, three of them differentially against delta.c.

Some tests cover their input space completely rather than sampling it: every pair of strings over a two-symbol alphabet up to length ten, every single-byte edit at every position for lengths either side of the hash window, and every one and two byte input to the integer decoder. Apply is additionally checked against deltas assembled directly from arbitrary valid commands — zero-length copies, copies that overlap or run backwards, deltas made only of inserts — which the encoder here would never emit but another implementation may. The suite also runs on 32-bit ARM, 32-bit x86 and big-endian s390x, since several bounds checks only carry weight where int is 32 bits and the word-at-a-time comparisons have to agree whatever the machine's byte order.

Contributing

AGENTS.md documents the invariants, how to run the suite in each of its modes, the golden file workflow, and the parts of the source that look wrong but are deliberate. Read it before changing anything here.

License

BSD 2-Clause. See LICENSE, which carries the notices of every implementation this descends from, beginning with the original C in Fossil by D. Richard Hipp.

internal/cref/fossil/ holds unmodified copies of Fossil's src/delta.c and src/delta.h, compiled only under the cref build tag to check this package against the reference implementation. They are never part of what the package ships, and carry Fossil's own notice in internal/cref/fossil/LICENSE.

Documentation

Overview

Package fdelta implements the Fossil delta encoding: a compact binary diff between two byte slices.

Instead of storing or transmitting the whole of something, store or transmit only what changed relative to a version the other side already has. Create builds the diff and Apply reconstructs the new bytes from the old ones plus the diff. A delta is self-describing and carries a checksum of the result, so Apply reports an error rather than returning wrong data when the delta is corrupt or was built against different base bytes.

The format is specified at https://fossil-scm.org/home/doc/tip/www/delta_format.wiki and deltas are portable between every implementation of it. 

patch := fdelta.Create(oldData, newData)
// ... send patch ...
newData, err := fdelta.Apply(oldData, patch)

Create always succeeds and always returns a valid delta, but a delta is not always worth sending: for unrelated payloads it is larger than the new payload itself. Callers are expected to compare and fall back to sending the payload in full.

Relationship to Fossil

The format comes from Fossil, whose src/delta.c is the reference implementation. See https://fossil-scm.org/home/doc/tip/www/delta_format.wiki for the format and https://fossil-scm.org/home/doc/tip/www/delta_encoder_algorithm.wiki for the encoder.

This package follows it in everything a delta expresses: the command stream, the integer encoding, the checksum, and what Apply accepts. Deltas are portable in both directions between every implementation of the format.

Create does not emit the byte-for-byte delta the reference would choose. It reduces a block hash to a bucket by multiplying and taking the high bits rather than by a remainder, so that its index does not collapse on high-entropy payloads; see bucketIndex. That hash is the encoder's private index and never appears in a delta, so the result is an ordinary Fossil delta of the same size: measured across structured, textual and binary payloads the totals agree with the reference to within a fraction of a percent.

Payload size and untrusted input

Apply is hardened against hostile deltas: it validates one completely before allocating, never panics, and reports ErrChecksumMismatch when the output does not match the checksum the delta carries. That catches corruption and most cases of applying a delta to the wrong source, but the checksum is a plain sum fixed by the format, so it cannot catch every one; see Apply. Two things are worth knowing beyond that.

First, a delta is small but its output need not be. A copy command costs a handful of bytes and can copy the whole of origin, so a short delta can legitimately declare an output far larger than either input. That is inherent to the format. Use OutputSize to impose your own ceiling before calling Apply; Apply is guaranteed not to exceed what OutputSize reported.

Second, Create's cost rises with the size of origin, and more steeply on payloads with no structure to find. It is close to linear -- a mebibyte of random bytes costs roughly 18ms on a current machine, against roughly 0.3ms for 64 kibibytes -- and, unlike the algorithm as delta.c implements it, does not depend on the payload happening to be a power of two in size. See bucketIndex for what that took and why the reference does not do it.

Delta encoding high-entropy data is pointless regardless, since the delta comes out larger than the payload and the caller discards it. If a remote peer can influence what you diff, decide a maximum payload size and send anything larger in full without calling Create at all: that bounds the cost exactly, where relying on the encoder's own speed only bounds it roughly.

Concurrency

All functions are safe for concurrent use and hold no state between calls beyond an internal pool of scratch buffers.

Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/centrifugal/fdelta"
)

func main() {
	previous := []byte(`{"user":"alice","status":"online","score":1200,"rank":"gold"}`)
	current := []byte(`{"user":"alice","status":"online","score":1350,"rank":"gold"}`)

	patch := fdelta.Create(previous, current)

	// Send the patch instead of the payload only when it is actually smaller.
	if len(patch) >= len(current) {
		fmt.Println("send the payload in full")
		return
	}

	got, err := fdelta.Apply(previous, patch)
	if err != nil {
		fmt.Println("error:", err)
		return
	}
	fmt.Printf("patch is %d bytes for a %d byte payload, applies correctly: %v\n",
		len(patch), len(current), bytes.Equal(got, current))
}

Output:
patch is 32 bytes for a 61 byte payload, applies correctly: true

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	// ErrInvalidDelta reports that a delta is not well formed: a truncated or
	// corrupt command stream, a count that runs past the end of the delta or
	// of the source, or a size that disagrees with the commands. Every error
	// returned by [Apply] and [OutputSize] other than [ErrChecksumMismatch]
	// wraps it, so errors.Is(err, ErrInvalidDelta) matches them all.
	ErrInvalidDelta = errors.New("fdelta: invalid delta")

	// ErrChecksumMismatch reports that a delta is well formed but the bytes it
	// produced do not match the checksum it carries. In practice this means it
	// was applied to the wrong source: a client whose base payload has drifted
	// from the one the delta was built against sees this, and should ask for
	// the payload in full.
	//
	// Its absence is not proof that the source was right. The checksum is a
	// plain sum of 32-bit words, fixed by the format, so a drifted source that
	// happens to leave the sum unchanged applies without error. Detecting drift
	// reliably is for the protocol carrying the deltas, for example by
	// tracking the position of each payload in its stream.
	ErrChecksumMismatch = errors.New("fdelta: checksum mismatch")
)

Functions

func AppendApply 

func AppendApply(dst, origin, delta []byte) ([]byte, error)

AppendApply appends the bytes that delta produces from origin to dst and returns the extended slice, in the manner of [append]. It lets a caller that applies many deltas reuse one buffer.

Reuse is worth real time here, unlike in AppendCreate: the output is as large as the payload, and once the copying is this fast, allocating and zeroing that buffer is most of the work. Applying a 16 KiB payload takes roughly a third as long with a buffer that is already big enough.

On any error dst is returned unchanged and dst[:len(dst)] is untouched. A malformed delta is rejected before a single byte is written; a checksum mismatch is only discovered after the output has been produced, so by then the spare capacity beyond len(dst) may have been written to.

dst, including its spare capacity, may not overlap origin or delta.

Example (BufferReuse)

A client applying a stream of deltas can reuse two buffers instead of allocating a payload per message: the delta is applied into the buffer holding the base from before last, which nothing refers to any more. 

package main

import (
	"fmt"

	"github.com/centrifugal/fdelta"
)

func main() {
	payloads := [][]byte{
		[]byte(`{"seq":1,"body":"a reasonably long payload that changes slightly"}`),
		[]byte(`{"seq":2,"body":"a reasonably long payload that changes slightly"}`),
		[]byte(`{"seq":3,"body":"a reasonably long payload that changes slightly"}`),
	}

	var buffers [2][]byte
	base := payloads[0]

	for i := 1; i < len(payloads); i++ {
		patch := fdelta.Create(base, payloads[i])

		next := buffers[i%2][:0]
		next, err := fdelta.AppendApply(next, base, patch)
		if err != nil {
			fmt.Println("error:", err)
			return
		}
		buffers[i%2] = next
		base = next
		fmt.Printf("seq %d applied, %d bytes\n", i+1, len(base))
	}
}

Output:
seq 2 applied, 66 bytes
seq 3 applied, 66 bytes

func AppendCreate 

func AppendCreate(dst, origin, target []byte) []byte

AppendCreate appends the delta that turns origin into target to dst and returns the extended slice, in the manner of [append]. It lets a caller that creates many deltas reuse one buffer.

What this saves is the allocation, not time: a delta worth sending is small, so Create's own allocation barely registers next to the search. Reach for it to keep a hot publication path allocation-free, not to make it faster. AppendApply is the one where reuse changes the timing.

dst may not overlap origin or target.

func Apply 

func Apply(origin, delta []byte) ([]byte, error)

Apply returns the bytes that delta produces from origin.

It returns ErrChecksumMismatch when the delta is well formed but the output does not match the checksum it carries, which almost always means origin is not the source it was built from, and an error wrapping ErrInvalidDelta when the delta itself is malformed. It never returns partial output and never panics, whatever the delta contains.

The result does not alias origin or delta.

Applying deltas from an untrusted peer

A malformed delta is rejected without allocating anything. A well formed one is a different matter: a copy command costs a handful of bytes and can copy the whole of origin, so a delta that is itself tiny can legitimately demand an enormous output, and Apply will produce it. Measured on a 1 MiB origin, a 3.5 KB delta can ask for 500 MB, and the format's own ceiling is 4 GiB per call, because the declared size is a 32-bit number.

Call OutputSize and impose your own ceiling before calling Apply. It reads the header alone, costs no allocation, and Apply is guaranteed not to produce more than it reported: 

if n, err := fdelta.OutputSize(delta); err != nil || n > maxPayload {
	// refuse without doing any further work
}

Note also what the checksum is and is not. It binds the output to the claim the delta makes about it, so it catches corruption and most cases of a wrong origin. It is a plain sum of 32-bit words, fixed by the format, so it cannot catch them all: an origin that differs from the right one in a way that leaves the sum unchanged, such as two values swapped four bytes apart, applies without error to the wrong output. It is also not authentication: whoever supplies the delta chooses the output, and can supply a correct checksum for whatever they chose. If the deltas you apply need to be trusted, that has to come from somewhere else.

Example (Errors)

Apply separates the two failures a caller has to handle differently. 

package main

import (
	"bytes"
	"errors"
	"fmt"

	"github.com/centrifugal/fdelta"
)

func main() {
	base := []byte("the quick brown fox jumps over the lazy dog, at some length")
	patch := fdelta.Create(base, []byte("the quick brown cat jumps over the lazy dog, at some length"))

	// The base this client holds has drifted from the one the delta was built
	// against, so the delta reconstructs something else and the checksum says so.
	drifted := bytes.Clone(base)
	drifted[0] = 'T'

	_, err := fdelta.Apply(drifted, patch)
	switch {
	case errors.Is(err, fdelta.ErrChecksumMismatch):
		fmt.Println("wrong base: ask for the payload in full")
	case errors.Is(err, fdelta.ErrInvalidDelta):
		fmt.Println("malformed delta: drop the connection")
	case err != nil:
		fmt.Println("other error:", err)
	default:
		fmt.Println("applied")
	}

	_, err = fdelta.Apply(base, []byte("not a delta at all"))
	fmt.Println("malformed:", errors.Is(err, fdelta.ErrInvalidDelta))
}

Output:
wrong base: ask for the payload in full
malformed: true

func Create 

func Create(origin, target []byte) []byte

Create returns a delta that turns origin into target.

It never fails and the result is always a valid delta, but it is not always a useful one: when the two payloads have little in common the delta is larger than target itself. Callers that are deciding whether to send a delta or the payload in full should compare len(delta) against len(target) and use whichever is smaller.

The result does not alias origin or target.

Limits

The format encodes every length and offset as an unsigned 32-bit number, so neither input may exceed 4 GiB-1. Given a larger input, Create returns a delta that declares an empty output and is never terminated, which Apply and every other implementation of the format reject. Encoding it anyway would wrap the lengths, and a delta with wrapped lengths is not reliably rejected: the bytes after a wrapped literal are read as further commands, and a crafted target can make them apply cleanly to the wrong output.

Cost grows with the size of origin and with how little structure it has; see the package documentation on payload size before feeding it large, high-entropy input from an untrusted source.

Create does not produce the same bytes delta.c would, because it indexes the source differently; see bucketIndex. It produces a delta of the same size, and every implementation of the format reads it.

Example (NotAlwaysSmaller)

Create always succeeds, but a delta is not always worth sending: when the payloads have little in common it is larger than the payload itself. 

package main

import (
	"fmt"

	"github.com/centrifugal/fdelta"
)

func main() {
	previous := []byte("the quick brown fox jumps over the lazy dog")
	unrelated := []byte("entirely different content with nothing in common!!")

	patch := fdelta.Create(previous, unrelated)
	fmt.Println("worth sending:", len(patch) < len(unrelated))
}

Output:
worth sending: false

func OutputSize 

func OutputSize(delta []byte) (int, error)

OutputSize returns the size of the output that delta declares in its header, without examining the rest of it.

This is a cheap pre-filter, not a validation: it reports what the delta claims. Apply independently verifies that the commands really do produce that many bytes, and fails otherwise, so a caller that rejects an oversized delta here can rely on Apply not exceeding what this returned.

It is worth checking. A delta is small but its output need not be: a copy command costs a handful of bytes and can copy the whole of origin, so a short delta can legitimately ask for an output far larger than either input. That is inherent to the format and true of every implementation of it; a caller taking deltas from an untrusted peer should decide its own ceiling here.

Example

A delta is small but its output need not be, so a peer taking deltas from an untrusted source should set its own ceiling before applying one. 

package main

import (
	"bytes"
	"fmt"

	"github.com/centrifugal/fdelta"
)

func main() {
	base := bytes.Repeat([]byte("payload-"), 1024)
	patch := fdelta.Create(base, append(bytes.Clone(base), "tail"...))

	const maxPayload = 4 << 10

	size, err := fdelta.OutputSize(patch)
	if err != nil {
		fmt.Println("malformed delta:", err)
		return
	}
	if size > maxPayload {
		fmt.Printf("refusing a %d byte delta that declares %d bytes of output\n",
			len(patch), size)
		return
	}
	fmt.Println("would apply")
}

Output:
refusing a 38 byte delta that declares 8196 bytes of output

Types

This section is empty.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.