buzhash chunker / chunking algorithm

[rupertpaulson]

After reading the documentation and watching this video (BTW, thanks for the nice introduction to attic/borg @ThomasWaldmann), I'm not sure if I understand the chunking algorithm correctly. That's how I understand the rolling hash chunker:

                                         chunk n                    chunk n+1
                               id_hash: MAC(SHA-256/Blake2)
              ----------------|----------------------------|-------------------------|---------
data bytes:   x x x x x x x X1 x x x x x x x x x x x x x X2 x x x X3 x x x x x x x X4 x x x x x 
                  |-----------|                |-----------|             |-----------|
                     buzash                       buzhash                   buzhash
                                                        |-----------|
                                                           buzhash

• CHUNK_MIN < varying chunk size < CHUNK_MAX
• buzhash window of fixed size (HASH_WINDOW_SIZE = 4095 B)
• buzhash is calculated for each byte, hence the rolling hash
• X1, X2, X3, X4 = bytes where a cut could be placed (condition of buzhash with trailing/leading zeroes fulfilled)
• chunk X2-X3 < CHUNK_MIN, so chunk X2-X4 is used as chunk n+1
• the real chunk sizes are much bigger than the buzhash window size (unlike the illustration might suggest)

Do I get it right?

[ThomasWaldmann]

yes, correct. iirc, we also skip the ranges where we do not want to accept cuts (due to < CHUNK_MIN), that saves the computation of quite some of the rolling hash values.

https://youtu.be/Vc0URl-GWrg?t=611 < a good explanation by restic author @fd0.

rabin fingerprinting is a different algorithm than buzhash, but it is also a rolling hash and the use case is exactly the same.

[rupertpaulson]

Thanks for the helpful video.

... skip the ranges where we do not want to accept cuts (due to < CHUNK_MIN) ...

Makes sense.