rabin-aes, goldilocks-aes and toeplitz-aes differed only in their rolling
universal hash, but each carried its own copy of the AES layer, the
two-lane scan structure, the chunker class and the test suite - about 79%
of the goldilocks/toeplitz code was line-identical to rabin-aes.
Three shared pieces replace the copies:
- phte_core.h: AES-128 key expansion, endian-explicit LE helpers, hardware
detection, single-block AES helpers and the context base (round keys, EVP
context, path selection).
- phte_scan.h: the scan itself as a compile-time template. Each kernel
defines its rolling functions and PH_PREFIX/PH_CTX/PH_ROLL/PH_ROLL2/
PH_DIGEST64, then includes it, so the rolling code is still expanded
inline into fully specialized scan loops - no function pointers, no
cross-kernel calls, identical code generation.
- phte_chunker.pyx/.pxd: ChunkerPHTE, the shared chunker driver (buffering,
min/max clamping, normalized chunking, scan loop, sparse handling). The
subclasses implement _scan()/_digest64() as Cython cdef methods, i.e. one
vtable call per scan span (up to a whole chunk) and per chunk start, never
per byte.
Likewise for the tests: the behavior every one of these chunkers must have
(kernel equivalence, size distribution, shift resilience, param parsing,
fuzzing) now runs parametrized over all three in phte_chunkers_test.py; the
per-chunker modules keep only their frozen golden chunk points and the
tests of their own hash arithmetic and key derivation.
Net -2335 lines. Each kernel .c is now 84-125 lines (was 523-564) and each
chunker .pyx no longer contains the ~250-line class body.
Verified unchanged behavior and performance:
- all three frozen golden chunk-point tests unchanged, 508 tests pass,
mypy/black/ruff clean, e2e create+extract with all three chunkers OK;
- C-level A/B of the production scan (same harness, HEAD kernels vs these,
64 MiB, best of 8): rabin 683.6 -> 682.5, goldilocks 331.8 -> 331.8,
toeplitz 687.4 -> 694.7 MB/s hw; EVP paths 376.6 -> 376.6, 251 -> 250,
394.2 -> 394.0 - all within +-1%;
- disassembly of ra_scan keeps the identical AES and table-lookup structure
(853 vs 850 instructions; the delta is prologue register shuffling caused
by the changed struct field offsets).
Also excludes *.pxd from the wheel (build-time only, borg's first .pxd).
Co-Authored-By: Claude Fable 5 <[email protected]>
Third UHF-then-PRF chunker, and on the evidence the best construction of
the three: the universal hash is a tabulated LFSR-based Toeplitz hash
(Krawczyk, CRYPTO '94) - digest = sum_j x^(63-j) * T[b_j] over
GF(2)[x] mod P - with a secret random table T of 256 uint64 (2 KiB of
key material) and a FIXED PUBLIC irreducible P of degree 64
(x^64 + x^4 + x^3 + x + 1, the CLHASH polynomial, top bit implicit).
Collision bound: two distinct 64-byte windows collide with probability
EXACTLY 2^-64 over T - optimal for a 64-bit digest and unconditional
(rabin-aes: ~2^-55 probabilistic over the sampled P; goldilocks-aes:
~2^-58). Sketch: the difference is sum_v c_v * T[v] where some c_v is a
nonzero polynomial of degree < 64, hence an invertible element mod the
irreducible degree-64 P, making the sum uniform. This needs the fixed
64-byte window (distinct powers x^0..x^63); a plain-rotation variant
(keyed buzhash) fails - rotations satisfy R^64 = I, so e.g. two
all-same-byte windows collide with probability 1/2.
The rolling step d' = d*x ^ x^64*T[out] ^ T[in] reduces via a branchless
shift+masked-XOR and indexes tables only by plaintext bytes: no loads and
no secret-dependent memory access on the serial chain. Setup needs no
irreducibility sampling (P is public; the secrecy is the table).
Same C kernel architecture as rabin-aes/goldilocks-aes (two even/odd
lanes, grouped AES on arm64/AES-NI, batched OpenSSL EVP, bit-identical
paths), fully wired (constants, ChunkerParams, get_chunker, completion,
borg benchmark cpu, docs, tests with frozen golden chunk points),
verified end-to-end with repo-create/create/extract.
Measured (1 GiB random, 19,23,21, 5 runs x 2 reps): hw 666/713 (nc2)
MB/s - on par with rabin-aes 661/698; EVP 424/450 vs 405/434 (~+5%).
The tie on the hw path is itself a finding: at ~700 MB/s the grouped-AES
path is AES/transfer-bound, not roll-chain-bound, so the cheaper roller
only shows on the EVP path. Equal speed, strictly better bound.
Co-Authored-By: Claude Fable 5 <[email protected]>
Add a second UHF-then-PRF chunker implementing the reference
construction of "Breaking and Fixing Content-Defined Chunking"
(Truong et al., eprint 2025/558) with its original universal hash: a
rolling polynomial hash over the Goldilocks prime field GF(p),
p = 2^64 - 2^32 + 1, at a secret random evaluation point K, over the
same 64-byte window - followed by the same AES-128 PRF layer as
rabin-aes. The C kernel mirrors rabin_aes_impl.c exactly (two even/odd
rolling lanes, groups of 8 pipelined AES blocks on arm64/AES-NI,
batched OpenSSL EVP fallback, bit-identical paths); only the rolling
arithmetic differs. Negated removal tables keep the field multiply as
the only critical-path operation; all values stay canonical since the
state feeds AES verbatim.
Verified equivalent to the paper's Rust artifact on shared keys and
random data: rolling states, AES input blocks and ciphertexts are
bit-identical per position; only the cut rule differs (they mask the
last ciphertext bytes via a big-endian u128, we mask the first 8
little-endian), so cut positions do not coincide - by choice, both
rules see uniform PRF bits.
Purpose is an evidence baseline, not a new default: on an Apple
M-series (256 MiB random, 19,23,21), 354 MB/s hw / 267 MB/s EVP versus
rabin-aes 670 / 401 - the GF(p) multiply chain is ~2x the GF(2)
shift+xor chain, table loads hide off-path in both. Non-speed
trade-offs versus rabin-aes: slightly better collision bound (63/p ~=
2^-58 vs ~2^-55), trivial key sampling (no irreducibility search), no
secret-dependent table indices in the hot loop, and a cheaper wide-
digest upgrade path (two independent K vs GF(2^127) clmul); rabin-aes
keeps the 2x throughput. Wired into get_chunker ("goldilocks-aes",
own key domain) and chunker_bench.py only.
Co-Authored-By: Claude Fable 5 <[email protected]>
Add a "UHF-then-PRF" content-defined chunker following the Chk-PHTE
construction of "Breaking and Fixing Content-Defined Chunking"
(Truong et al., eprint 2025/558): a rolling Rabin fingerprint over
GF(2)[x]/P(x) - with P a secret, random, irreducible polynomial of
degree 63 - hashes the last 64 bytes (a universal hash family), and
AES-128 with a secret key is applied to the digest; the cut decision
only looks at the AES output. Observed chunk boundaries are thus
pseudo-random and yield no usable equations about the chunking
secrets, unlike chunkers cutting directly on (keyed) rolling-hash
bits. Both secrets are derived from the id key (domain "rabin-aes").
The C scan kernel has three bit-identical paths: batched OpenSSL EVP
AES-128-ECB (portable), arm64 crypto-extension intrinsics and x86-64
AES-NI (runtime detected), interleaving the AES work with the serial
rolling-hash chain. Batching ahead of the cut decision is possible
because the digest stream does not depend on where cuts happen.
Throughput on an Apple M-series (1 GiB random, 19,23,21,2): 489 MB/s
(arm64 hw path), 334 MB/s (EVP path); chunk-size distribution, shift
resilience and dedup behavior are identical to fastcdc/buzhash64.
Normalized chunking, param shape rabin-aes,min,max,mask,nc_level.
Co-Authored-By: Claude Fable 5 <[email protected]>
Port of the .claude config from the 1.4-maint line, adapted for master (borg 2.x):
CLAUDE.md now describes the borgstore-based repository, the archiver/ command package,
Python >=3.11 and the borg2 testsuite layout. Shared .claude/CLAUDE.md and settings.json
are tracked; machine-specific bits (local virtualenv path, GPG signing) live in a
gitignored .claude/CLAUDE.local.md. Switch .gitignore from ignoring all of .claude/ to
ignoring only the personal settings.local.json and CLAUDE.local.md.
Co-Authored-By: Claude Opus 4.8 <[email protected]>
Claude-Session: https://claude.ai/code/session_01Dg49arm61F42gHR4aFD4ac
- compact_pack: walk gap object headers, drop copies whose chunk id is
indexed elsewhere (superseded duplicates), keep unindexed ones for repair
- compact_pack: repoint kept objects in a single linear pass over drop ranges
- compact_packs: report total unindexed bytes when nonzero
- mark_soft_deleted_used: count and warn about objects missing from the index
- epilog: compact reclaims redundant indexed copies, repair handles the rest
- tests: superseded gap dropped, duplicate reclaimed on rewrite
Add a new "fastcdc" content-defined chunker selectable via --chunker-params.
It uses the FastCDC Gear rolling hash (fp = (fp << 1) + Gear[byte]), which is
window-less and cheaper per byte than buzhash's cyclic-polynomial update, so it
chunks noticeably faster (see "borg benchmark cpu" output), while producing
the same chunk-size distribution and deduplication.
The Gear table is keyed: it is derived from the repo id key via CSPRNG (own
"fastcdc" domain), exactly like the buzhash64 table, so chunk cut points stay
unpredictable without the key (anti-fingerprinting). It implements the same
FastCDC techniques as buzhash64 (sub-minimum skipping, normalized chunking with
a required nc_level, min/max clamping); the mask uses the high bits of the hash
(Gear accumulates entropy there).
chunker-params: "fastcdc,chunk_min,chunk_max,chunk_mask,nc_level" - there is no
window field, because Gear is window-less. e.g. fastcdc,19,23,21,2
Also: borg benchmark cpu now measures the fastcdc chunker; tests in
borg.testsuite.chunkers (golden vector, size distribution, keyed gear table,
param parsing, slow fuzz); docs and changelog.
Benchmarks (scripts/chunker_bench.py, buzhash64 vs fastcdc, both nc_level=2,
incompressible data unless noted):
5 GiB, 2 MiB target (default params):
buzhash64: CV 0.294, 1011 MB/s
fastcdc: CV 0.295, 1313 MB/s (+30%)
64 MiB, 64 KiB target:
buzhash64: CV 0.374, shift-resilience 0.9928, 963 MB/s
fastcdc: CV 0.359, shift-resilience 0.9929, 1331 MB/s (+38%)
Re-backup of a 2.5 GiB file after scattered single-byte edits (dedup ratio,
0.5 = v2 fully deduplicated, lower is better):
64 edits: buzhash64 0.5237, fastcdc 0.5236
320 edits: buzhash64 0.6133, fastcdc 0.6161
borg benchmark cpu, 1 GB: fastcdc 3.80s, buzhash 4.36s, buzhash64 8.13s,
fixed 0.56s.
Chunk-size distribution, deduplication and shift-resilience match buzhash64
within noise; fastcdc is consistently faster.
Also: fix bug when computing the mask, one needs to use 1ULL instead of
1, so the shifting computation is done in a uint64, not in a 32bit int.
Co-Authored-By: Claude Opus 4.8 <[email protected]>
moved --junitxml parameter to the tox configuration.
haiku: add coverage params to pytest invocation (tox not used there).
vm_tests: add test_results and coverage uploads.
hard-code coverage.xml as coverage filename
Moved the `ChunkerFixed` implementation from `chunker` to a new `fixed` module for better modularity. Updated imports and type hints.
Removed now empty chunkers.chunker module.
Moved `buzhash` implementation from `chunker` to a new `buzhash` module for better separation of concerns. Updated imports, adjusted `setup.py` and build configuration accordingly. Removed deprecated `Chunker` definitions from `chunker.pyi`.
Extracted the `reader` logic from `chunker` into a dedicated `reader` module to improve modularity and maintainability. Updated imports, references, and build configurations accordingly.
- Created a batch file to build borg on windows
- Adjusted setup.py to be runnable on windows and build the windows
extension
- Extracted the free space check to a function in the platform module
- Created the minimal needed (dummy) functions for the windows platform
module
CRC slice by 8 for generic CPUs outperforms zlib CRC32 on ppc
and x86 (ARM untested but expected to as well).
PCLMULQDQ derived from Intel's zlib patches outperforms every other
CRC implementation by a huge margin.
the generation of those files was causing us way too much pain to
justify automatically generating them all the time.
those will have to be re-generated with `build_api` or `build_usage`
as appropriate, for example when function signatures or commandline
flags change.
see #384
the current instructions create a dirty tree that `git add .` would
commit into git. this is error prone and somewhat unclean.
i found it preferable to change the `.gitignore` than to change the instructions, since there are probably `borg-env` environments lying around everywhere already.
Thomas Waldmann