hesela.devGear hash
Gear hash is a rolling fingerprint based on a byte-indexed table and a shift-and-add recurrence, used in content-defined boundary selection.
The FastCDC paper describes a left-shift recurrence with finite-width arithmetic and explains how mask placement changes the input history visible to a boundary test. The number of selected bits and their positions serve different roles; a boundary fingerprint is not a cryptographic identifier of the whole chunk. [1]
Variants matter: fastcdc-py 1.7.0 uses p_next = floor(p/2) + g. From zero on one repeated byte with g > 0, p_t = 2g - ceil(2g / 2^t), eventually reaching the odd state 2g - 1. Its low-bit zero masks cannot pass after settling, though transient matches remain possible. [2] [3]
At 2048/8192/65536 B parameters, the 256 separate 131073-byte constant-byte fixtures produce maximum-sized chunks for 255 byte values; 0x5D instead yields 63 chunks of 2070 B and a 663 B tail. Exact reconstruction and independent recurrence checks support this bounded result, not a general FastCDC performance or storage-savings claim. [3]
Relations
Limitations
- A fingerprint's recurrence, integer width, table and boundary masks must be specified to reproduce behavior.
Citations
- Xia et al. FastCDC: a Fast and Efficient Content-Defined Chunking Approach for Data Deduplication. USENIX ATC 2016, sections 3-4.
- ISCC. fastcdc-py v1.7.0: cdc_offset, masks and Gear table.
- Hesela. Exhaustive constant-byte FastCDC experiment: pinned 1.7.0 Python API, source hashes, exact reconstruction and independent recurrence checks.