Crate hash_roll

hash-roll provides various content defined chunking algorithms

Content defined chunking (CDC) algorithms are algorithms that examine a stream of input bytes (often represented as a slice like [u8], and provide locations within that input stream to split or chunk the stream into parts.

CDC algorithms generally try to optimize for the following:

1. Processing speed (ie: bytes/second)
2. Stability in split locations even when insertions/deletions of bytes occur
3. Reasonable distributions of chunk lengths

API Concepts

• Configured Algorithm Instance (impliments Chunk). Normally named plainly (like [Bup]). These can be thought of as “parameters” for an algorithm.
• Incrimental (impliments ChunkIncr). Normally named with Incr suffix.

Because of the various ways one might use a CDC, and the different CDC algorithm characteristics, hash-roll provides a few ways to use them.

Configured Algorithm Instances are created from the set of configuration needed for a given algorithm. For example, this might mean configuring a window size or how to decide where to split. These don’t include any mutable data, in other words: they don’t keep track of what data is given to them. Configured Algorithm Instances provide the all-at-once APIs, as well as methods to obtain other kinds of APIs, like incrimental style apis.

CDC Algorithms and Window Buffering

Different CDC algorithms have different constraints about how they process data. Notably, some require a large amount of previous processed data to process additional data. This “large amount of previously processed data” is typically referred to as the “window”. That said, note that some CDC algorithms that use a window concept don’t need previously accessed data.

For the window-buffering algorithms, their is an extra cost to certain types of API implimentations. The documentation will note when these occur and suggest alternatives.

Generally, CDC interfaces that are incrimental will be slower for window-buffering algorithms. Using an explicitly allocating interface (which emits Vec<u8> or Vec<Vec<u8>>) will have no worse performance that the incrimental API, but might be more convenient. Using an all-at-once API will provide the best performance due to not requiring any buffering (the input data can be used directly).

Use Cases that drive API choices

• accumulate vecs, emits vecs

  • incrimental: yes
  • input: Vec<u8>
  • internal state: Vec<Vec<u8>>
  • output: Vec<Vec<u8>>

• stream data through

  • incrimenal: yes
  • input: &[u8]

• mmap (or read entire) file, emit

  • incrimenal: no
  • input: &[u8]
  • output: &[u8]

Modules

bup

buzhash

BuzHash (aka Cyclic Polynomial Hashing) is a window based rolling hash

buzhash_table

fastcdc

FastCDC is a chunking algorithm using some features from Gear

gear

gear_table

gzip

gzip (forks) rsyncable mode that uses a simple window accumulator

mii

pigz

ram

Rapid Asymmetric Maximum (RAM) is a fast chunking algorithm

range

zpaq

zpaq impliments the chunking algorithm used in the zpaq archiving tool

zstd

zstd’s --rsyncable option performs content defined chunking

Structs

IterSlices

Returned by ChunkIncr::iter_slices()

IterSlicesStrict

Returned by ChunkIncr::iter_slices_strict()

Traits

Chunk

Impl on algorthms that define methods of chunking data

ChunkIncr

Accept incrimental input and provide indexes of split points

ToChunkIncr

Implimented on types which can be converted to/can provide a ChunkIncr interface.