Requirements on window size and block size

[chmduquesne]

I can't post in https://groups.google.com/g/perkeep/c/8hNJ1_tmcmE/m/OHB0v46CCAAJ?pli=1, but there is an interesting discussion to have on the slicing parameters related to the wished chunk size.

Everybody understands that if you stop when the n most significant bits of the checksum of your rolling window are all the same, you will cut on average every 2^n bytes.

What is however rarely discussed is: is there a point where you should slice even though you have not met such a window? Imagine somebody creating input data that is specially designed to break your checksum, for example.

If anyone is interested, I discussed this in https://github.com/chmduquesne/opi/blob/master/doc/maxchunksize.md. Feel free to have a look!

[chmduquesne]

Also, thinking on the top of my head: why ask for a window of 64 bytes? Are there other window sizes that would work? I have never seen a good explanation for that number. Would 32 bytes be a good option?

What we are doing with such rolling checksum is that we are projecting the space of all windows into an integer. So if a window has n bytes, the number of possible windows is 256^n. When n=64, is this number high enough to guarantee uniform distribution of the checksums?

[zenhack]

Re: window size, making it a constant as opposed to a parameter was so that implementations could just declare the variable as a fixed-size array, rather than needing to heap allocate it. As to why 64, partially we just cargo cult-ed it from the perkeep implementation; if there's a reason beyond "small-ish power of 2," I don't know it. Note though that cp32 (and buzhash in general) benefits from the window size being a multiple of the word size, as it lets you skip a shift instruction when removing a byte from the hash.

In #3 we discussed what hash function to use, and did some light statistical analysis, but I don't think we played with the window size. The code we used is still in the eval directory in this repo, and could probably be modified to experiment with window sizes fairly easily.

And yes, we set a maximum chunk size in the spec exactly because these aren't cryptographic hashes. I want to do something similar for the tree construction algorithm.

It's funny you should come across this now; I got pulled away from it for a long time, but actually just last week pulled in @bobg's library for a project (we still need to update that library to be spec compliant...)