Data.Hash.Rolling

Documentation

roll' :: ByteString -> ByteString

Take a ByteString and generate a new ByteString with chunks based on a rolling hash. This generates chunks with an expected size of 8k, where the sizes vary between 128 bytes and 64k each. and the breakpoints are based on moments where a rolling hash function applied to the last 128 bytes of the input matches a mask.

This can be used with various chunk hashing schemes to allow hashing that is fairly robust in the presence of inline insertions and deletions.

This scheme is based on the standard Rabin-Karp rolling checksum. It is much slower than rolling, but is provided here for comparison purposes.

roll :: ByteString -> ByteString

Take a strict ByteString and generate a new lazy ByteString with chunks based on a rolling hash. This generates chunks with an expected size of 8k, where the sizes vary between 128 bytes and 64k each. and the breakpoints are based on moments where a rolling hash function applied to the last 128 bytes of the input matches a mask.

This can be used with various chunk hashing schemes to allow hashing that is fairly robust in the presence of inline insertions and deletions.

The rolling hash is based on the ideas from buzhash, but since we have a known window size that is an integral multiple of the word size we save work.