delta

README

go-rsync

Go implementation of the rsync delta-transfer algorithm — the first Go rsync library with AVX2/AVX-512 accelerated MD5 (8-way + 16-way SIMD). Rolling checksum matching, block signature generation, file reconstruction, and a binary wire protocol. Batteries included.

Used in production by Shuttle, a Windows-native file sync tool.

✨ Features

• 🧬 8-way AVX2 MD5 — 8 blocks hashed in parallel via hand-written AVX2 assembly (YMM registers), VPGATHERDD gather load (raw machine code, bypasses Go assembler VSIB bug). First Go rsync library to do this.
• ⚡ 3-tier checksum engine — AVX2 (64B/iter) → SSE2/SSSE3 (32B/iter) → pure Go 128B batch. Auto-detects CPU at runtime.
• 🔌 Pluggable strong hash — md5, sha256, xxh64 built-in. Register your own with FastSum support.
• 📡 Binary wire protocol — compact big-endian encoding, ready for SSH pipes.
• 💧 Streaming I/O — generate signatures from io.Reader, decode instructions one-at-a-time, minimal memory.
• 🔗 Rolling checksum — CHAR_OFFSET=31, uint32 natural-overflow arithmetic.
• 🧪 Well tested — roundtrip, identical-file, parity tests (AVX2 vs SSE2 vs pure Go), MD5 8-way + 16-way validation (AVX2 + AVX-512 vs stdlib).

📦 Install

go get github.com/henryborner/go-rsync

🚀 Quick start

package main

import (
    "os"
    delta "github.com/henryborner/go-rsync"
)

func main() {
    oldFile, _ := os.ReadFile("v1.bin")
    newFile, _ := os.ReadFile("v2.bin")

    blockSize := delta.CalculateBlockSize(int64(len(oldFile)))

    // 1. Generate signature from old file
    sig := delta.GenerateSignature(oldFile, blockSize, "md5")

    // 2. Search new file for matching blocks
    eng := delta.NewMatchEngine(blockSize, "md5")
    eng.LoadSignature(sig)
    instructions := eng.Search(newFile)

    // 3. Reconstruct on the other side
    recon := delta.NewReconstructor(oldFile, blockSize, "md5")
    result, _ := recon.Reconstruct(instructions)

    os.WriteFile("v2_reconstructed.bin", result, 0644)
}

📊 Benchmarks

AMD Ryzen 9 8940HX (Zen 4), single-threaded, 1MB data, blockSize≈700:

Benchmark	Time	Throughput
GenerateSignature (md5)	~447 µs	2.35 GB/s
GenerateSignature (xxh64)	~318 µs	3.30 GB/s
GenerateSignature (sha256)	~819 µs	1.28 GB/s

Intel Xeon Platinum @ 2.5GHz, AVX-512 enabled:

Benchmark	Time	Throughput
MD5x8_Bulk (AVX2 8-way, 32KB)	11.5 µs	2.84 GB/s
MD5x8Core_Bulk (AVX2 raw, 1000×64B×8)	145 µs	3.54 GB/s
MD5x16Core_Bulk (AVX-512 raw, 1000×64B×16)	94 µs	10.86 GB/s 🔥
SignatureReader/10MB_32KB	2.88 ms	3.64 GB/s

Checksum1 (rolling weak checksum) throughput:

Data size	AVX2 (Ryzen)	AVX2 (Xeon)	rsync-AVX2 (Xeon)
1 KB	55 GB/s	37 GB/s	43 GB/s
64 KB	69 GB/s	44 GB/s	44 GB/s
1 MB	51 GB/s	44 GB/s	—

64KB within 1.4% of rsync on Xeon. AVX-512 raw MD5 core hits 10.9 GB/s.

Run on your own machine:

go test -bench='BenchmarkSignature$|BenchmarkMD5x8_Bulk|BenchmarkChecksum1' -benchmem .

📁 Package layout

File	Purpose
match.go	Block matching engine, signature generation
reconstruct.go	File reconstruction from instruction stream
wire.go	Binary wire protocol encode/decode
registry.go	Pluggable strong-hash registry
rolling.go	Rolling checksum (RollingSum, Checksum1)
rolling_amd64.s	AVX2 checksum assembly (64B/iter) + checksum1PackedAVX2
rolling_sse2_amd64.s	SSE2/SSSE3 checksum assembly (32B/iter)
rolling_fast_amd64.go	Tiered dispatch: AVX2 → SSE2 → Go, inlined Checksum1
rolling_generic.go	Portable byte-by-byte checksum (non-amd64 fallback)
md5x8_amd64.s	Generated — 64-step unrolled AVX2 MD5 core (8-way)
md5x8_transpose_fast_amd64.s	Register-shuffle transpose (~80 vs ~320 VPINSRD instructions)
md5x8_transpose.s	Contiguous 8×64→16 transposed YMMs (tail finalization)
md5x8_load_transpose_amd64.s	VPINSRD scalar load+transpose (~288 insn/chunk, correct fallback)
md5x8_amd64.go	Go-side glue: md5Hash8wayAVX2, md5Finalize8way
md5x8_common.go	Shared MD5 constants + md5FinalLane
md5x8_generic.go	Stubs for non-amd64 (darwin/arm64)
md5x8_purego.go	Correct pure-Go 8-way MD5 reference (fallback / validation)
md5x8_gather_amd64.s	Raw machine code — VPGATHERDD load+transpose (bypasses Go asm VSIB bug)
md5x16_amd64.s	Generated — AVX-512 MD5 core (16-way, ≥2KB blocks)
md5x16_amd64.go	Go-side glue for AVX-512 path
md5x16_gather_amd64.s	ZMM VPGATHERDD load+transpose (k-mask reloaded per gather)
md5x8_test.go	Tests: 8-way + 16-way MD5 parity, gather verification
gen_md5x8/main.go	Code generator for md5x8_amd64.s
gen_md5x16/main.go	Code generator for md5x16_amd64.s
docs/checksum-engine.md	Checksum engine: algorithm, loop structure, quirks, bug history, SSE2 appendix
docs/md5-simd.md	MD5 SIMD reference: architecture, techniques, safety checklist, debugging journal

📚 Documentation

• Checksum Engine — Rolling checksum algorithm, AVX2/SSE2 loop structure, Go Plan 9 quirks, optimization history (v0→v6), all bugs fixed, register map, test coverage, performance data.
• MD5 SIMD — AVX2/AVX-512 parallel MD5 architecture, gather/transpose techniques, safety checklist, full debugging journal (2026-06-26), lessons learned.

🔗 Related

• rsync — the original C implementation
• md5-simd — MinIO's AVX2/AVX-512 MD5 (multi-stream server use case)
• md5vec — first Go AVX2 8-way MD5 (2018, unmaintained)
• Shuttle — Windows sync tool using this library

Documentation

Overview

Package delta implements the rsync delta-transfer algorithm in Go.

It provides a complete toolkit for binary delta compression: rolling checksum matching (rsync-style), block signature generation, instruction-based file reconstruction, and a binary wire protocol for sending deltas over the network.

Key features

• Tiered checksum engine: AVX2 (64B/iter, ~52 GB/s) → SSE2 (32B/iter, ~26 GB/s) → pure Go 128B batch on amd64; portable byte-by-byte on other architectures. Automatic CPU dispatch at runtime.
• Pluggable strong hash: md5, sha256, xxh64 built-in. Register your own via Register.
• Streaming I/O: generate signatures from io.Reader, decode instructions one-at-a-time with DecodeInstructionsStream, and reconstruct files with minimal memory.
• Binary wire format: compact big-endian encoding for signatures and instructions — ready to pipe over SSH or any io.Writer.

Quick start

// --- Sender side ---
sig := delta.GenerateSignature(oldFile, blockSize, "md5")
eng := delta.NewMatchEngine(blockSize, "md5")
eng.LoadSignature(sig)
insts := eng.Search(newFile)
delta.WireEncodeInstructions(os.Stdout, insts)

// --- Receiver side ---
sig, _ := delta.WireDecodeSignature(os.Stdin)
recon := delta.NewReconstructor(oldFile, blockSize, "md5")
delta.DecodeInstructionsStream(os.Stdin, func(inst delta.MatchResult) error {
    return recon.WriteInstruction(os.Stdout, inst)
})

Relationship to rsync

The rolling checksum uses CHAR_OFFSET=31. (Note: standard rsync builds use CHAR_OFFSET=0; not wire-compatible.) The hash-table matching and block-size goal (~√N blocks) follow the same approach. This package is NOT a wire-compatible rsync client — it provides the building blocks so you can embed delta compression in your own tools.

Performance (amd64, Ryzen 9 8940HX)

checksum1 throughput:
  AVX2      ~52 GB/s
  SSE2      ~26 GB/s
  pure Go    ~1.9 GB/s

See the project README for full benchmark tables.

Package delta allows registering custom hash algorithms, replacing hard-coded switches. 允许用户注册自定义哈希算法，替换硬编码的 switch。

Example

Example demonstrates a complete roundtrip: signature → match → reconstruct.

package main

import (
	"bytes"
	"fmt"

	delta "github.com/henryborner/go-rsync"
)

func main() {
	oldFile := []byte("The quick brown fox jumps over the lazy dog. " +
		"This is an example of rsync-style delta transfer.")
	newFile := []byte("The quick brown fox jumps over the lazy dog. " +
		"INSERTED CONTENT HERE. " +
		"This is an example of rsync-style delta transfer.")

	blockSize := int32(32)

	// 1. Generate signature for old file
	sig := delta.GenerateSignature(oldFile, blockSize, "md5")

	// 2. Search new file for matching blocks
	eng := delta.NewMatchEngine(blockSize, "md5")
	eng.LoadSignature(sig)
	instructions := eng.Search(newFile)

	// 3. Reconstruct
	recon := delta.NewReconstructor(oldFile, blockSize, "md5")
	result, _ := recon.Reconstruct(instructions)

	fmt.Println(bytes.Equal(result, newFile))
	fmt.Printf("Transfer: %.0f%%\n",
		float64(eng.LiteralBytes)/float64(len(newFile))*100)

}

Output:
true
Transfer: 73%

Index

• Constants
• func CalculateBlockSize(fileSize int64) int32
• func Checksum1(data []byte) uint32
• func DecodeInstructionsStream(r io.Reader, fn func(inst MatchResult) error) error
• func GetDefault() string
• func ListAlgos() []string
• func MD5x8CoreForBench(x *[16][8]uint32, state *[4][8]uint32)
• func MD5x16CoreForBench(x *[16][16]uint32, state *[4][16]uint32)
• func MD5x16available() bool
• func NewHash(algoName string) (hash.Hash, error)
• func Register(algo ChecksumAlgo)
• func SetDefault(name string) error
• func WireEncodeInstructions(w io.Writer, insts []MatchResult) error
• func WireEncodeSignature(w io.Writer, sig *Signature) error
• type BlockSum
• type ChecksumAlgo
  • func GetAlgo(name string) (ChecksumAlgo, error)
  • func MustGet(name string) ChecksumAlgo
• type MatchEngine
  • func NewMatchEngine(blockSize int32, strongAlgo string) *MatchEngine
  • func (me *MatchEngine) LoadSignature(sig *Signature)
  • func (me *MatchEngine) Search(data []byte) []MatchResult
• type MatchResult
  • func WireDecodeInstructions(r io.Reader) ([]MatchResult, error)
• type Reconstructor
  • func NewReconstructor(basisFile []byte, blockSize int32, strongAlgo string, blockLens ...[]int32) *Reconstructor
  • func (rc *Reconstructor) Reconstruct(instructions []MatchResult) ([]byte, error)
  • func (rc *Reconstructor) Verify(result []byte, expectedSum []byte) bool
  • func (rc *Reconstructor) WriteInstruction(w io.Writer, inst MatchResult) error
• type RollingSum
  • func NewRollingSum(data []byte) *RollingSum
  • func (rs *RollingSum) Reset(data []byte)
  • func (rs *RollingSum) Roll(oldByte, newByte byte, blockLen int32)
  • func (rs *RollingSum) S1() uint32
  • func (rs *RollingSum) S2() uint32
  • func (rs *RollingSum) Value() uint32
• type Signature
  • func GenerateSignature(data []byte, blockSize int32, strongAlgo string) *Signature
  • func GenerateSignatureParallel(data []byte, blockSize int32, strongAlgo string) *Signature
  • func GenerateSignatureReader(r io.Reader, fileSize int64, blockSize int32, strongAlgo string) *Signature
  • func WireDecodeSignature(r io.Reader) (*Signature, error)

Examples

• Package

Constants

const (
	CHAR_OFFSET = 31
)

const CHUNK_SIZE = 32 * 1024

CHUNK_SIZE is the maximum literal chunk size (32KB). Large literals are split into CHUNK_SIZE pieces to ensure the receiver never allocates more than 32KB at once (safe for low-memory servers). CHUNK_SIZE 字面量分块上限，同 rsync 的 32KB。 大字面量拆分为多个 CHUNK_SIZE 块，确保接收端单次缓冲区分配不超过此值。

Functions

func CalculateBlockSize

func CalculateBlockSize(fileSize int64) int32

func Checksum1

func Checksum1(data []byte) uint32

Checksum1 zero-alloc fast path for amd64 with AVX2. Inlines the AVX2 checksum directly to avoid the checksum1 wrapper call overhead.

func DecodeInstructionsStream

func DecodeInstructionsStream(r io.Reader, fn func(inst MatchResult) error) error

DecodeInstructionsStream decodes instructions one at a time, calling fn for each. The MatchResult.Data passed to fn is only valid during the callback (reuses a single buffer). Do not retain the reference. Designed for low-memory receivers: avoids loading all instructions + literal data into memory at once.

DecodeInstructionsStream 流式解码指令，每读取一条指令就回调 fn。 fn 收到的 MatchResult.Data 仅回调期间有效（使用可复用缓冲区），不得持有引用。 用于低内存接收端：避免将全部指令+字面量数据加载到内存。

func GetDefault

func GetDefault() string

GetDefault returns the current default algorithm name. GetDefault 获取默认算法名称。

func ListAlgos

func ListAlgos() []string

func MD5x8CoreForBench

func MD5x8CoreForBench(x *[16][8]uint32, state *[4][8]uint32)

MD5x8CoreForBench is an exported wrapper for benchmarking the pure AVX2 core.

func MD5x16CoreForBench

func MD5x16CoreForBench(x *[16][16]uint32, state *[4][16]uint32)

MD5x16CoreForBench is an exported wrapper for benchmarking the pure AVX512 core.

func MD5x16available

func MD5x16available() bool

MD5x16available is the exported version for external use.

func NewHash

func NewHash(algoName string) (hash.Hash, error)

func Register

func Register(algo ChecksumAlgo)

Register registers a checksum algorithm (thread-safe). Register 注册一个校验和算法（线程安全）。

func SetDefault

func SetDefault(name string) error

SetDefault sets the default algorithm. SetDefault 设置默认算法。

func WireEncodeInstructions

func WireEncodeInstructions(w io.Writer, insts []MatchResult) error

WireEncodeInstructions encodes an instruction sequence as a binary stream. WireEncodeInstructions 将指令序列编码为二进制流。

func WireEncodeSignature

func WireEncodeSignature(w io.Writer, sig *Signature) error

WireEncodeSignature encodes a signature as a binary stream. WireEncodeSignature 将签名编码为二进制流。

Types

type BlockSum

type BlockSum struct {
	Index  int    // block index / 块索引
	Sum1   uint32 // weak rolling checksum / 弱滚动校验和
	Sum2   []byte // strong checksum (MD5/SHA256) / 强校验和
	Offset int64  // byte offset within the file / 块在文件中的偏移
	Length int32  // actual block length (last block may be shorter) / 块长（末块可能更短）
}

BlockSum represents a single block checksum from file B. BlockSum 表示文件 B 中一个块的校验和。

type ChecksumAlgo

type ChecksumAlgo struct {
	Name   string           // algorithm name e.g. "md5", "sha256", "xxh3" / 算法名称
	New    func() hash.Hash // hash constructor / 哈希构造函数
	Length int              // output bytes / 输出字节数

	// FastSum is an optional zero-allocation fast path for in-memory hashing.
	// It computes the hash of data and writes the result to out[:Length].
	// out is a pre-allocated buffer with at least Length bytes of capacity.
	// Returns out[:Length] (may be a subslice of out).
	// If nil, the hash.Hash path (New+Write+Sum) is used instead.
	// FastSum 是可选的零分配快速哈希路径。直接计算 data 的哈希写入 out[:Length]，
	// out 是预分配的缓冲区（容量 ≥ Length）。返回 out[:Length]。若为 nil，走 hash.Hash 路径。
	FastSum func(out, data []byte) []byte
}

ChecksumAlgo describes a checksum algorithm. ChecksumAlgo 描述一个校验和算法。

func GetAlgo

func GetAlgo(name string) (ChecksumAlgo, error)

GetAlgo retrieves a registered algorithm. GetAlgo 获取已注册的算法。

func MustGet

func MustGet(name string) ChecksumAlgo

type MatchEngine

type MatchEngine struct {

	// stats / 统计
	HashHits     int
	FalseAlarms  int
	Matches      int
	LiteralBytes int64
	// contains filtered or unexported fields
}

MatchEngine is the delta match engine. MatchEngine 增量匹配引擎。

func NewMatchEngine

func NewMatchEngine(blockSize int32, strongAlgo string) *MatchEngine

NewMatchEngine creates a new match engine. NewMatchEngine 创建匹配引擎。

func (*MatchEngine) LoadSignature

func (me *MatchEngine) LoadSignature(sig *Signature)

func (*MatchEngine) Search

func (me *MatchEngine) Search(data []byte) []MatchResult

Search searches source data for matches, returning an instruction sequence. Search 在源数据中搜索匹配，返回指令序列。

type MatchResult

type MatchResult struct {
	IsLiteral bool   // true = literal data, false = block reference / true=字面量, false=块引用
	Data      []byte // literal payload / 字面量数据
	BlockIdx  int    // matched block index / 匹配的块索引
	Offset    int64  // source offset (for ordering) / 来源中的偏移（用于排序）
}

func WireDecodeInstructions

func WireDecodeInstructions(r io.Reader) ([]MatchResult, error)

type Reconstructor

type Reconstructor struct {
	// contains filtered or unexported fields
}

Reconstructor rebuilds files on the receiver side. Reconstructor rebuilds files on the receiver side. Reconstructor 文件重建器（接收端）。

func NewReconstructor

func NewReconstructor(basisFile []byte, blockSize int32, strongAlgo string, blockLens ...[]int32) *Reconstructor

NewReconstructor creates a reconstructor. blockLens is optional: pass per-block actual lengths (from Signature.BlockSums[].Length) to avoid copying extra bytes from the last block. Pass nil to use blockSize uniformly, truncating by file length. NewReconstructor creates a reconstructor. blockLens is optional: pass per-block actual lengths (from Signature.BlockSums[].Length) to avoid copying extra bytes from the last block. Pass nil to use blockSize uniformly, truncating by file length. NewReconstructor 创建重建器。 blockLens 可选：传入每个块的实际长度（通常来自 Signature.BlockSums[].Length）， 避免最后一个块复制多余字节。传 nil 则全部使用 blockSize 并靠文件长度截断。

func (*Reconstructor) Reconstruct

func (rc *Reconstructor) Reconstruct(instructions []MatchResult) ([]byte, error)

Reconstruct rebuilds a file from an instruction sequence. Reconstruct rebuilds a file from an instruction sequence. Reconstruct 根据指令序列重建文件。

func (*Reconstructor) Verify

func (rc *Reconstructor) Verify(result []byte, expectedSum []byte) bool

Verify checks the reconstructed result against an expected strong checksum. Verify checks the reconstructed result against an expected strong checksum. Verify 验证重建结果。

func (*Reconstructor) WriteInstruction

func (rc *Reconstructor) WriteInstruction(w io.Writer, inst MatchResult) error

WriteInstruction writes the output of a single instruction to w (streaming reconstruction, low memory). Literal instructions write Data directly; match instructions copy the corresponding block from the basis file. WriteInstruction writes the output of a single instruction to w (streaming reconstruction, low memory). Literal instructions write Data directly; match instructions copy the corresponding block from the basis file. WriteInstruction 将单条指令的输出写入 w（流式重建，低内存占用）。 Literal 指令直接写 Data，Match 指令从 basisFile 复制对应块。

type RollingSum

type RollingSum struct {
	// contains filtered or unexported fields
}

func NewRollingSum

func NewRollingSum(data []byte) *RollingSum

func (*RollingSum) Reset

func (rs *RollingSum) Reset(data []byte)

func (*RollingSum) Roll

func (rs *RollingSum) Roll(oldByte, newByte byte, blockLen int32)

Roll advances the rolling window: removes one old byte, adds one new byte, and updates s1/s2. Uses uint32 natural overflow, no modulo, no type conversions. Roll 滚动窗口：移除一个旧字节，加入一个新字节，更新 s1/s2。 使用 uint32 自然溢出（同 rsync），无取模、无类型转换。

func (*RollingSum) S1

func (rs *RollingSum) S1() uint32

S1 returns the lower 16 bits of s1. S1 返回 s1 低 16 位。

func (*RollingSum) S2

func (rs *RollingSum) S2() uint32

S2 returns the lower 16 bits of s2. S2 返回 s2 低 16 位。

func (*RollingSum) Value

func (rs *RollingSum) Value() uint32

type Signature

type Signature struct {
	BlockSize int32      // block size / 块大小
	BlockSums []BlockSum // all block checksums / 所有块的校验和
	FileSize  int64      // original file size / 文件原始大小
}

func GenerateSignature

func GenerateSignature(data []byte, blockSize int32, strongAlgo string) *Signature

GenerateSignature generates block signatures from in-memory data. GenerateSignature 从内存数据生成块签名。

This is a convenience wrapper around GenerateSignatureReader. For large files, prefer GenerateSignatureReader to stream from disk and avoid holding the entire file in memory.

func GenerateSignatureParallel

func GenerateSignatureParallel(data []byte, blockSize int32, strongAlgo string) *Signature

GenerateSignatureParallel generates block signatures from in-memory data. GenerateSignatureParallel 从内存数据并行生成块签名。

Delegates to GenerateSignatureReader (AVX512 → AVX2 → scalar). For large files, prefer GenerateSignatureReader directly.

func GenerateSignatureReader

func GenerateSignatureReader(r io.Reader, fileSize int64, blockSize int32, strongAlgo string) *Signature

GenerateSignatureReader generates block signatures from an io.Reader, avoiding loading the entire file into memory. Uses 8-way AVX2 acceleration for md5 when available. GenerateSignatureReader 从 io.Reader 流式生成块签名，避免全量读入内存。 md5 + AVX512 可用时使用 16 路 SIMD；否则 AVX2 8 路；否则标量回退。

func WireDecodeSignature

func WireDecodeSignature(r io.Reader) (*Signature, error)