Buckets:

hf-doc-build
/

doc-dev

Files

xet

hf-doc-build/doc-dev / xet /pr_2299 /en /chunking.html

rtrm

about 2 months ago

download

raw

41.3 kB

	<meta charset="utf-8" /><meta name="hf:doc:metadata" content="{"title":"Content-Defined Chunking Algorithm","local":"content-defined-chunking-algorithm","sections":[{"title":"Step-by-step Algorithm (Gearhash-based CDC)","local":"step-by-step-algorithm-gearhash-based-cdc","sections":[{"title":"Constant Parameters","local":"constant-parameters","sections":[],"depth":3},{"title":"State","local":"state","sections":[],"depth":3},{"title":"Per-byte Update Rule (Gearhash)","local":"per-byte-update-rule-gearhash","sections":[],"depth":3},{"title":"Boundary Test and Size Constraints","local":"boundary-test-and-size-constraints","sections":[],"depth":3},{"title":"Decision Flowchart","local":"decision-flowchart","sections":[],"depth":3},{"title":"Pseudocode","local":"pseudocode","sections":[],"depth":3},{"title":"Boundary probability and mask selection","local":"boundary-probability-and-mask-selection","sections":[],"depth":3},{"title":"Properties","local":"properties","sections":[],"depth":3},{"title":"Intuition and Rationale","local":"intuition-and-rationale","sections":[],"depth":3},{"title":"Implementation Notes","local":"implementation-notes","sections":[],"depth":3},{"title":"Edge Cases","local":"edge-cases","sections":[],"depth":3},{"title":"Portability and Determinism","local":"portability-and-determinism","sections":[],"depth":3}],"depth":2},{"title":"Minimum-size Skip-ahead (Cut-point Skipping Optimization)","local":"minimum-size-skip-ahead-cut-point-skipping-optimization","sections":[],"depth":2},{"title":"References","local":"references","sections":[],"depth":2},{"title":"Sample Reference","local":"sample-reference","sections":[],"depth":2}],"depth":1}">
	<link href="/docs/xet/pr_2299/en/_app/immutable/assets/0.e3b0c442.css" rel="modulepreload">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/entry/start.f5880d7c.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/scheduler.de5597d1.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/singletons.f4429561.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/paths.e4822296.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/entry/app.ed536e32.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/preload-helper.c2fccda0.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/index.f8bac2c1.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/nodes/0.91def38f.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/each.e59479a4.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/nodes/4.ff5a55d8.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/MermaidChart.svelte_svelte_type_style_lang.c78ae8b2.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/CodeBlock.ca7a0bdb.js">
	<link rel="modulepreload" href="/docs/xet/pr_2299/en/_app/immutable/chunks/MermaidChart.18ec4e45.js"><!-- HEAD_svelte-u9bgzb_START --><meta name="hf:doc:metadata" content="{"title":"Content-Defined Chunking Algorithm","local":"content-defined-chunking-algorithm","sections":[{"title":"Step-by-step Algorithm (Gearhash-based CDC)","local":"step-by-step-algorithm-gearhash-based-cdc","sections":[{"title":"Constant Parameters","local":"constant-parameters","sections":[],"depth":3},{"title":"State","local":"state","sections":[],"depth":3},{"title":"Per-byte Update Rule (Gearhash)","local":"per-byte-update-rule-gearhash","sections":[],"depth":3},{"title":"Boundary Test and Size Constraints","local":"boundary-test-and-size-constraints","sections":[],"depth":3},{"title":"Decision Flowchart","local":"decision-flowchart","sections":[],"depth":3},{"title":"Pseudocode","local":"pseudocode","sections":[],"depth":3},{"title":"Boundary probability and mask selection","local":"boundary-probability-and-mask-selection","sections":[],"depth":3},{"title":"Properties","local":"properties","sections":[],"depth":3},{"title":"Intuition and Rationale","local":"intuition-and-rationale","sections":[],"depth":3},{"title":"Implementation Notes","local":"implementation-notes","sections":[],"depth":3},{"title":"Edge Cases","local":"edge-cases","sections":[],"depth":3},{"title":"Portability and Determinism","local":"portability-and-determinism","sections":[],"depth":3}],"depth":2},{"title":"Minimum-size Skip-ahead (Cut-point Skipping Optimization)","local":"minimum-size-skip-ahead-cut-point-skipping-optimization","sections":[],"depth":2},{"title":"References","local":"references","sections":[],"depth":2},{"title":"Sample Reference","local":"sample-reference","sections":[],"depth":2}],"depth":1}"><!-- HEAD_svelte-u9bgzb_END --> <p></p> <div class="items-center shrink-0 min-w-[100px] max-sm:min-w-[50px] justify-end ml-auto flex" style="float: right; margin-left: 10px; display: inline-flex; position: relative; z-index: 10;"><div class="inline-flex rounded-md max-sm:rounded-sm"><button class="inline-flex items-center gap-1 h-7 max-sm:h-7 px-2 max-sm:px-1.5 text-sm font-medium text-gray-800 border border-r-0 rounded-l-md max-sm:rounded-l-sm border-gray-200 bg-white hover:shadow-inner dark:border-gray-850 dark:bg-gray-950 dark:text-gray-200 dark:hover:bg-gray-800" aria-live="polite"><span class="inline-flex items-center justify-center rounded-md p-0.5 max-sm:p-0 hover:text-gray-800 dark:hover:text-gray-200"><svg class="sm:size-3.5 size-3" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" fill="currentColor" focusable="false" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 32 32"><path d="M28,10V28H10V10H28m0-2H10a2,2,0,0,0-2,2V28a2,2,0,0,0,2,2H28a2,2,0,0,0,2-2V10a2,2,0,0,0-2-2Z" transform="translate(0)"></path><path d="M4,18H2V4A2,2,0,0,1,4,2H18V4H4Z" transform="translate(0)"></path><rect fill="none" width="32" height="32"></rect></svg></span> <span>Copy page</span></button> <button class="inline-flex items-center justify-center w-6 max-sm:w-5 h-7 max-sm:h-7 disabled:pointer-events-none text-sm text-gray-500 hover:text-gray-700 dark:hover:text-white rounded-r-md max-sm:rounded-r-sm border border-l transition border-gray-200 bg-white hover:shadow-inner dark:border-gray-850 dark:bg-gray-950 dark:text-gray-200 dark:hover:bg-gray-800" aria-haspopup="menu" aria-expanded="false" aria-label="Open copy menu"><svg class="transition-transform text-gray-400 overflow-visible sm:size-3.5 size-3 rotate-0" width="1em" height="1em" viewBox="0 0 12 7" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M1 1L6 6L11 1" stroke="currentColor"></path></svg></button></div> </div> <h1 class="relative group"><a id="content-defined-chunking-algorithm" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#content-defined-chunking-algorithm"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Content-Defined Chunking Algorithm</span></h1> <p data-svelte-h="svelte-poqjqk">The goal in chunking is to convert file data into smaller variable length chunks, approximately 64 KiB in length.
	Chunks boundaries MUST be computed in a deterministic way such that chunking the same data in 2 different places yields chunks that can be deduplicated.</p> <div class="code-block relative "><div class="absolute top-2.5 right-4"><button class="inline-flex items-center relative text-sm focus:text-green-500 cursor-pointer focus:outline-none transition duration-200 ease-in-out opacity-0 mx-0.5 text-gray-600 " title="code excerpt" type="button"><svg class="" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" fill="currentColor" focusable="false" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 32 32"><path d="M28,10V28H10V10H28m0-2H10a2,2,0,0,0-2,2V28a2,2,0,0,0,2,2H28a2,2,0,0,0,2-2V10a2,2,0,0,0-2-2Z" transform="translate(0)"></path><path d="M4,18H2V4A2,2,0,0,1,4,2H18V4H4Z" transform="translate(0)"></path><rect fill="none" width="32" height="32"></rect></svg> <div class="absolute pointer-events-none transition-opacity bg-black text-white py-1 px-2 leading-tight rounded font-normal shadow left-1/2 top-full transform -translate-x-1/2 translate-y-2 opacity-0"><div class="absolute bottom-full left-1/2 transform -translate-x-1/2 w-0 h-0 border-black border-4 border-t-0" style="border-left-color: transparent; border-right-color: transparent; "></div> Copied</div></button></div> <pre class=""><!-- HTML_TAG_START --> +---------+---------+---------+---------+---------+---------+---------+--------------
	File -> \| chunk 0 \| chunk 1 \| chunk 2 \| chunk 3 \| chunk 4 \| chunk 5 \| chunk 6 \| chunk 7 \| ...
	+---------+---------+---------+---------+---------+---------+---------+--------------<!-- HTML_TAG_END --></pre></div> <h2 class="relative group"><a id="step-by-step-algorithm-gearhash-based-cdc" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#step-by-step-algorithm-gearhash-based-cdc"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Step-by-step Algorithm (Gearhash-based CDC)</span></h2> <h3 class="relative group"><a id="constant-parameters" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#constant-parameters"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Constant Parameters</span></h3> <ul data-svelte-h="svelte-1wdq0zq"><li>target_chunk_size: <code>64 KiB</code></li> <li>MIN_CHUNK_SIZE: <code>8 KiB</code> (minimum chunk size)</li> <li>MAX_CHUNK_SIZE: <code>128 KiB</code> (maximum chunk size)</li> <li>MASK: <code>0xFFFF000000000000</code> (16 one-bits → boundary probability 1/2^16 per byte)</li> <li>TABLE[256]: table of 256 64-bit constants (<a href="https://github.com/srijs/rust-gearhash/blob/adad44e7141cfd29d898cf6e0858f50b995db286/src/table.rs#L5" rel="nofollow">rust-gearhash-table</a>)</li></ul> <h3 class="relative group"><a id="state" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#state"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>State</span></h3> <ul data-svelte-h="svelte-akuthx"><li>h: 64-bit hash, initialized to 0</li> <li>start_offset: start offset of the current chunk, initialized to 0</li></ul> <h3 class="relative group"><a id="per-byte-update-rule-gearhash" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#per-byte-update-rule-gearhash"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Per-byte Update Rule (Gearhash)</span></h3> <p data-svelte-h="svelte-kzwscd">For each input byte <code>b</code>, update the hash with 64-bit wrapping arithmetic:</p> <div class="code-block relative "><div class="absolute top-2.5 right-4"><button class="inline-flex items-center relative text-sm focus:text-green-500 cursor-pointer focus:outline-none transition duration-200 ease-in-out opacity-0 mx-0.5 text-gray-600 " title="code excerpt" type="button"><svg class="" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" fill="currentColor" focusable="false" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 32 32"><path d="M28,10V28H10V10H28m0-2H10a2,2,0,0,0-2,2V28a2,2,0,0,0,2,2H28a2,2,0,0,0,2-2V10a2,2,0,0,0-2-2Z" transform="translate(0)"></path><path d="M4,18H2V4A2,2,0,0,1,4,2H18V4H4Z" transform="translate(0)"></path><rect fill="none" width="32" height="32"></rect></svg> <div class="absolute pointer-events-none transition-opacity bg-black text-white py-1 px-2 leading-tight rounded font-normal shadow left-1/2 top-full transform -translate-x-1/2 translate-y-2 opacity-0"><div class="absolute bottom-full left-1/2 transform -translate-x-1/2 w-0 h-0 border-black border-4 border-t-0" style="border-left-color: transparent; border-right-color: transparent; "></div> Copied</div></button></div> <pre class=""><!-- HTML_TAG_START -->h = (h << 1) + TABLE[b]<!-- HTML_TAG_END --></pre></div> <h3 class="relative group"><a id="boundary-test-and-size-constraints" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#boundary-test-and-size-constraints"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Boundary Test and Size Constraints</span></h3> <p data-svelte-h="svelte-1bzrojw">At each position after updating <code>h</code>, let <code>size = current_offset - start_offset + 1</code>.</p> <ul data-svelte-h="svelte-19v4xfc"><li>If <code>size < MIN_CHUNK_SIZE</code>: skip testing <code>MASK</code>; continue</li> <li>Else if <code>size >= MAX_CHUNK_SIZE</code>: force a boundary</li> <li>Else if <code>(h & MASK) == 0</code>: boundary at this position</li></ul> <p data-svelte-h="svelte-4he0dj">When a boundary found or taken:</p> <ul data-svelte-h="svelte-ck8gkw"><li>Emit the chunk <code>[start_offset, current_offset + 1)</code></li> <li>Set <code>start_offset = current_offset + 1</code></li> <li>Reset <code>h = 0</code></li></ul> <p data-svelte-h="svelte-e2mz6u">At end-of-file, if <code>start_offset < len(data)</code>, emit the final chunk <code>[start_offset, len(data))</code>.</p> <h3 class="relative group"><a id="decision-flowchart" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#decision-flowchart"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Decision Flowchart</span></h3> <div class="mermaid-chart " style="text-align: center;"></div> <h3 class="relative group"><a id="pseudocode" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#pseudocode"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Pseudocode</span></h3> <div class="code-block relative "><div class="absolute top-2.5 right-4"><button class="inline-flex items-center relative text-sm focus:text-green-500 cursor-pointer focus:outline-none transition duration-200 ease-in-out opacity-0 mx-0.5 text-gray-600 " title="code excerpt" type="button"><svg class="" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" fill="currentColor" focusable="false" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 32 32"><path d="M28,10V28H10V10H28m0-2H10a2,2,0,0,0-2,2V28a2,2,0,0,0,2,2H28a2,2,0,0,0,2-2V10a2,2,0,0,0-2-2Z" transform="translate(0)"></path><path d="M4,18H2V4A2,2,0,0,1,4,2H18V4H4Z" transform="translate(0)"></path><rect fill="none" width="32" height="32"></rect></svg> <div class="absolute pointer-events-none transition-opacity bg-black text-white py-1 px-2 leading-tight rounded font-normal shadow left-1/2 top-full transform -translate-x-1/2 translate-y-2 opacity-0"><div class="absolute bottom-full left-1/2 transform -translate-x-1/2 w-0 h-0 border-black border-4 border-t-0" style="border-left-color: transparent; border-right-color: transparent; "></div> Copied</div></button></div> <pre class=""><!-- HTML_TAG_START -->Inputs: (See above for constant parameters)
	data: byte array

	State:
	h = 0
	start_offset = 0 // start of the "current chunk"

	if len(data) < MIN_CHUNK_SIZE:
	emit chunk [0, len(data))
	done

	for i in range(0, len(data)):
	b = data[i]
	h = (h << 1) + TABLE[b] // 64-bit wrapping
	size = i + 1 - start_offset

	if size < MIN_CHUNK_SIZE:
	continue

	if size >= MAX_CHUNK_SIZE or (h & MASK) == 0:
	emit chunk [start_offset, i + 1)
	start_offset = i + 1
	h = 0

	if start_offset < len(data):
	emit chunk [start_offset, len(data))<!-- HTML_TAG_END --></pre></div> <h3 class="relative group"><a id="boundary-probability-and-mask-selection" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#boundary-probability-and-mask-selection"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Boundary probability and mask selection</span></h3> <p data-svelte-h="svelte-6rjey3">Given that MASK has 16 one-bits, for a random 64-bit hash <code>h</code>, the chance that all those 16 bits are zero is 1 / 2^16. On average, that means you’ll see a match about once every 64 KiB.</p> <h3 class="relative group"><a id="properties" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#properties"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Properties</span></h3> <ul data-svelte-h="svelte-3e1x3u"><li>Deterministic boundaries: same content → same chunks</li> <li>Locality: small edits only affect nearby boundaries</li> <li>Linear time and constant memory: single 64-bit state and counters</li></ul> <h3 class="relative group"><a id="intuition-and-rationale" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#intuition-and-rationale"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Intuition and Rationale</span></h3> <ul data-svelte-h="svelte-1taix48"><li>The table <code>TABLE[256]</code> injects pseudo-randomness per byte value so that the evolving hash <code>h</code> behaves like a random 64-bit value with respect to the mask test. This makes boundaries content-defined yet statistically evenly spaced.</li> <li>The left shift <code>(h << 1)</code> amplifies recent bytes, helping small changes affect nearby positions without globally shifting all boundaries.</li> <li>Resetting <code>h</code> to 0 at each boundary prevents long-range carryover and keeps boundary decisions for each chunk statistically independent.</li></ul> <h3 class="relative group"><a id="implementation-notes" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#implementation-notes"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Implementation Notes</span></h3> <ul data-svelte-h="svelte-1e8v9r3"><li>Only reset <code>h</code> when you emit a boundary. This ensures chunking is stable even when streaming input in pieces.</li> <li>Apply the mask test only once <code>size >= MIN_CHUNK_SIZE</code>. This reduces the frequency of tiny chunks and stabilizes average chunk sizes.</li> <li>MUST force a boundary at <code>MAX_CHUNK_SIZE</code> even if <code>(h & MASK) != 0</code>. This guarantees bounded chunk sizes and prevents pathological long chunks when matches are rare.</li> <li>Use 64-bit wrapping arithmetic for <code>(h << 1) + TABLE[b]</code>. This is the behavior in the reference implementation <a href="https://github.com/srijs/rust-gearhash" rel="nofollow">rust-gearhash</a>.</li></ul> <h3 class="relative group"><a id="edge-cases" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#edge-cases"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Edge Cases</span></h3> <ul data-svelte-h="svelte-1hh9184"><li>Tiny files: if <code>len(data) < MIN_CHUNK_SIZE</code>, the entire <code>data</code> is emitted as a single chunk.</li> <li>Long runs without a match: if no position matches <code>(h & MASK) == 0</code> before <code>MAX_CHUNK_SIZE</code>, a boundary is forced at <code>MAX_CHUNK_SIZE</code> to cap chunk size.</li></ul> <h3 class="relative group"><a id="portability-and-determinism" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#portability-and-determinism"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Portability and Determinism</span></h3> <ul data-svelte-h="svelte-1txztnm"><li>With a fixed <code>T[256]</code> table and mask, the algorithm is deterministic across platforms: same input → same chunk boundaries.</li> <li>Endianness does not affect behavior because updates are byte-wise and use scalar 64-bit operations.</li> <li>SIMD-accelerated implementations (when available) are optimizations only; they produce the same boundaries as the scalar path <a href="https://github.com/srijs/rust-gearhash" rel="nofollow">rust-gearhash</a>.</li></ul> <h2 class="relative group"><a id="minimum-size-skip-ahead-cut-point-skipping-optimization" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#minimum-size-skip-ahead-cut-point-skipping-optimization"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Minimum-size Skip-ahead (Cut-point Skipping Optimization)</span></h2> <p data-svelte-h="svelte-17dduyg">Computing and testing the rolling hash at every byte is expensive for large data, and early tests inside the first few bytes of a chunk are disallowed by the <code>MIN_CHUNK_SIZE</code> constraint anyway.
	We are able to intentionally skip testing some data with cut-point skipping to accelerate scanning without affecting correctness.</p> <p data-svelte-h="svelte-j2h0cg">The hash function by virtue of the use of 64 byte integer length and the bit shift (<code>(h << 1) + TABLE[b]</code>) causes the hash at any byte offset to only depend on the last 64 bytes.
	With a Gear rolling hash window of 64 bytes, the first boundary test is deferred until at least <code>MIN_CHUNK_SIZE - 64 - 1</code> bytes into the chunk.
	This ensures that, by the time the first boundary can be considered (at offset <code>MIN_CHUNK_SIZE</code>), at least one full hash window of bytes from the current chunk has influenced the hash state.</p> <ul data-svelte-h="svelte-8yellp"><li>Effect:
	<ul><li>Distribution quality is preserved because the first admissible test uses a well-mixed hash (full window), avoiding bias from the earliest bytes.</li> <li>Performance improves by avoiding per-byte hashing/judgment in the prefix where boundaries cannot be taken.</li> <li>Correctness is preserved because boundaries MUST NOT be set before <code>MIN_CHUNK_SIZE</code> and the hash produced at a testable offset is the same as the hash computed had we not skipped any bytes.</li></ul></li> <li>Notes:
	<ul><li>This is an optimization of the search procedure only; it does not change the boundary condition, mask, or emitted chunk set compared to a byte-by-byte implementation that simply refrains from taking boundaries before <code>MIN_CHUNK_SIZE</code>.</li> <li>In the reference code, this appears as advancing the scan pointer by up to <code>MIN_CHUNK_SIZE - 64 - 1</code> before invoking the mask test loop.</li></ul></li></ul> <h2 class="relative group"><a id="references" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#references"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>References</span></h2> <ul data-svelte-h="svelte-1y7dtch"><li>rust-gearhash: Fast, SIMD-accelerated GEAR hashing for CDC <a href="https://github.com/srijs/rust-gearhash" rel="nofollow">rust-gearhash</a></li> <li>FastCDC paper (background and design rationale of CDC) <a href="https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia" rel="nofollow">fastcdc-paper</a></li></ul> <h2 class="relative group"><a id="sample-reference" class="header-link block pr-1.5 text-lg no-hover:hidden with-hover:absolute with-hover:p-1.5 with-hover:opacity-0 with-hover:group-hover:opacity-100 with-hover:right-full" href="#sample-reference"><span><svg class="" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 256 256"><path d="M167.594 88.393a8.001 8.001 0 0 1 0 11.314l-67.882 67.882a8 8 0 1 1-11.314-11.315l67.882-67.881a8.003 8.003 0 0 1 11.314 0zm-28.287 84.86l-28.284 28.284a40 40 0 0 1-56.567-56.567l28.284-28.284a8 8 0 0 0-11.315-11.315l-28.284 28.284a56 56 0 0 0 79.196 79.197l28.285-28.285a8 8 0 1 0-11.315-11.314zM212.852 43.14a56.002 56.002 0 0 0-79.196 0l-28.284 28.284a8 8 0 1 0 11.314 11.314l28.284-28.284a40 40 0 0 1 56.568 56.567l-28.285 28.285a8 8 0 0 0 11.315 11.314l28.284-28.284a56.065 56.065 0 0 0 0-79.196z" fill="currentColor"></path></svg></span></a> <span>Sample Reference</span></h2> <p data-svelte-h="svelte-rbppk8">The <a href="https://huggingface.co/datasets/xet-team/xet-spec-reference-files" rel="nofollow">xet-team/xet-spec-reference-files</a> repository contains the original file <a href="https://huggingface.co/datasets/xet-team/xet-spec-reference-files/blob/main/Electric_Vehicle_Population_Data_20250917.csv" rel="nofollow">Electric_Vehicle_Population_Data_20250917.csv</a>.</p> <p data-svelte-h="svelte-129lynf">In the same repository in file <a href="https://huggingface.co/datasets/xet-team/xet-spec-reference-files/blob/main/Electric_Vehicle_Population_Data_20250917.csv.chunks" rel="nofollow">Electric_Vehicle_Population_Data_20250917.csv.chunks</a>
	the chunks produced out of <a href="https://huggingface.co/datasets/xet-team/xet-spec-reference-files/blob/main/Electric_Vehicle_Population_Data_20250917.csv" rel="nofollow">Electric_Vehicle_Population_Data_20250917.csv</a> are listed.
	Each line in the file is a 64 hexadecimal character string version of the hash of the chunk, followed by a space and then the number of bytes in that chunk.</p> <p data-svelte-h="svelte-5t06qc">Implementors should use the chunk lengths to determine that they are producing the right chunk boundaries for this file with their chunking implementation.</p> <a class="!text-gray-400 !no-underline text-sm flex items-center not-prose mt-4" href="https://github.com/huggingface/hub-docs/blob/main/docs/xet/chunking.md" target="_blank"><svg class="mr-1" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" fill="currentColor" focusable="false" role="img" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 32 32"><path d="M31,16l-7,7l-1.41-1.41L28.17,16l-5.58-5.59L24,9l7,7z"></path><path d="M1,16l7-7l1.41,1.41L3.83,16l5.58,5.59L8,23l-7-7z"></path><path d="M12.419,25.484L17.639,6.552l1.932,0.518L14.351,26.002z"></path></svg> <span data-svelte-h="svelte-zjs2n5"><span class="underline">Update</span> on GitHub</span></a> <p></p>

	<script>
	{
	__sveltekit_9k147l = {
	assets: "/docs/xet/pr_2299/en",
	base: "/docs/xet/pr_2299/en",
	env: {}
	};

	const element = document.currentScript.parentElement;

	const data = [null,null];

	Promise.all([
	import("/docs/xet/pr_2299/en/_app/immutable/entry/start.f5880d7c.js"),
	import("/docs/xet/pr_2299/en/_app/immutable/entry/app.ed536e32.js")
	]).then(([kit, app]) => {
	kit.start(app, element, {
	node_ids: [0, 4],
	data,
	form: null,
	error: null
	});
	});
	}
	</script>

Xet Storage Details

Size:: 41.3 kB
Xet hash:: 91063a2f895ed9d5d3f042f855f9ebf86839abc73cf0344d84175cb862c19e06

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.