README
¶
go-rsync
Go implementation of the rsync delta-transfer algorithm — 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
- ⚡ 3-tier checksum engine — AVX2 assembly (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.
- 📡 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. - 🔗 rsync-compatible checksum — same CHAR_OFFSET=31, same uint32 natural-overflow arithmetic.
- 🧪 Well tested — roundtrip, identical-file, partial-modification, and tier comparison tests.
📦 Install
go get github.com/henryborner/go-rsync
🚀 Quick start
package main
import (
"os"
"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
checksum1 throughput on AMD Ryzen 9 8940HX (higher is better):
| Data size | AVX2 | SSE2 | Pure Go |
|---|---|---|---|
| 1 KB | 45 GB/s | 21 GB/s | 1.9 GB/s |
| 64 KB | 52 GB/s | 26 GB/s | 1.9 GB/s |
| 1 MB | 52 GB/s | 26 GB/s | 1.9 GB/s |
AVX2 is ~27× faster than pure Go. All tiers produce bit-identical results (parity tested).
Run on your own machine:
go test -bench BenchmarkAllTiers -benchmem ./...
📁 Package layout
| File | Purpose |
|---|---|
rolling.go |
Rolling checksum (RollingSum, Checksum1) |
rolling_amd64.s |
AVX2 assembly (64B/iter, VPMADDUBSW core) |
rolling_sse2_amd64.s |
SSE2/SSSE3 assembly (32B/iter) |
rolling_fast_amd64.go |
Tiered dispatch: AVX2 → SSE2 → Go |
rolling_generic.go |
Portable pure-Go checksum |
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 |
🔗 Related
📄 License
MIT © 2026 henryborner
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 algorithm is compatible with rsync's (CHAR_OFFSET=31, uint32 natural-overflow arithmetic). The hash-table matching and block-size heuristics follow the same design. 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 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
- type MatchEngine
- type MatchResult
- type Reconstructor
- type RollingSum
- type Signature
Examples ¶
Constants ¶
const (
CHAR_OFFSET = 31
)
const CHUNK_SIZE = 32 * 1024
CHUNK_SIZE is the maximum literal chunk size (same as rsync's 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 块，确保接收端单次缓冲区分配不超过此值。
Variables ¶
This section is empty.
Functions ¶
func CalculateBlockSize ¶
func Checksum1 ¶
Checksum1 computes a one-shot rolling checksum (non-rolling mode). Checksum1 直接计算一次性的滚动校验和（非滚动模式）。
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 Register ¶
func Register(algo ChecksumAlgo)
Register registers a checksum algorithm (thread-safe). Register 注册一个校验和算法（线程安全）。
func SetDefault ¶
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 将指令序列编码为二进制流。
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 / 输出字节数
}
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 (same as rsync), 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 ¶
GenerateSignature generates block signatures for file B (called by the receiver). GenerateSignature 为文件 B 生成块签名（接收端调用）。
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. GenerateSignatureReader 从 io.Reader 流式生成块签名，避免全量读入内存。
Source Files