changed:
-The FastCDC paper highlighted that typical chunking algorithms use N bits of the hash to get an average chunk size of 2^N, but the distribution is not a normal distribution around the target chunk size, but an exponential distribution with the most common block size being the smallest. Also, skipping over a min-block-size effectively shifts this distribution by the min size, which changes the average chunk size to min+2^N. We will call 2^N the "target-size", so the average-size = min-size + target-size.
The FastCDC paper highlighted that typical chunking algorithms use N bits of the hash to get an average chunk size of 2^N, but the distribution is not a normal distribution around the target chunk size, but an exponential distribution with the most common block size being the smallest. Also, skipping over a min-block-size effectively shifts this distribution by the min size, which changes the average chunk size to min+2^N. We will call 2^N the "target-size", so the average-size = min-size + target-size. There is a >22% chance of a chunk-boundary within 1/4 of, the median chunk size is about 70% of, and <13% are greater than 2x, the target-size.

added:

Algorithms
==========

PolyHash
--------

This is the Polynomial Hash AKA RabinKarp (not Rabin Fingerprint) mentioned at https://en.wikipedia.org/wiki/Rolling_hash, and used by librsync. It gives a very good hash (low collisions, good distribution) without needing a byte-mapping table, which saves cache memory. However, it does use 2 multiplies per rotation, which makes it slower than rollsums that only use addition or xor like CyclicPoly/Buzhash, Rollsum/Alder32/Bap, or Gear. Also unlike Gear, it does need to keep the sliding window of data.

changed:
-The gear rollsum has a really neat feature for chunking; there is no need to keep a sliding window because old bytes "expire" out of the hash as they get shifted out. It uses a lookup table to map bytes to the full hash width before adding them to the hash, and they slowly get shifted out with each byte added. This means that the window is limited to the size of the hash, with older bytes only represented in the more significant bits of the hash. 
-
-This means the normal technique of selecting the N least-significant bits with a mask also prunes the window size to N bytes. Importantly, it not only prunes the window size to N bytes, but it also only selects part of the entropy of the last 8 bytes of that window (assuming the original byte's entropy is perfectly spread across the hash by the mapping function). If we assume the entropy linearly decays for the last 8 bytes, it means we loose 4 bytes worth of entropy. So for N bits of entropy, assuming 1 bit of entropy per byte, we need at least N+4 bytes in the window.
The gear rollsum has a really neat feature for chunking; there is no need to keep a sliding window because old bytes "expire" out of the hash as they get shifted out. It uses a lookup table to map bytes to the full hash width before adding them to the hash, and they slowly get shifted out with each byte added. This means that the window is limited to the size of the hash, with older bytes only represented in the more significant bits of the hash. This makes it completely useless as a fast rolling hash for rsync, but ideal for chunking. 

This means the normal technique of selecting the N least-significant bits with a mask also prunes the window size to N bytes. Importantly, it not only prunes the window size to N bytes, but it also only selects only part of the entropy of the last 8 bytes of that window (assuming the original byte's entropy is perfectly spread across the hash by the mapping function). If we assume the entropy linearly decays for the last 8 bytes, it means we loose 4 bytes worth of entropy. So for N bits of entropy, assuming 1 bit of entropy per byte, we need at least N+4 bytes in the window.

changed:
-For 2. it seems strange that they didn't seem to realize that just using the most significant bits would give you the largest window size. Shifting the mask by 5 seems very arbitrary, and less effective than always using the most significant N bits. Also I'm not sure but `!(h>>S)` where S=32-N might be just as fast as `!(h&M)` where M=((~0) << (32-N)). However, it's also interesting to note that in the Gear entropy analysis above we need at least N+4 bytes in the window, so adding 5 bytes by shifting the mask 5 places should be sufficient to get your N bits of entropy. However, using the most significant bits would mean you are using a full window size of 32-4 = 28bytes, which is probably still better.
For 2. it seems strange that they didn't seem to realize that just using the most significant bits would give you the largest window size. Shifting the mask by 5 seems very arbitrary, and less effective than always using the most significant N bits. Also I'm not sure but `!(h>>S)` where S=32-N might be just as fast as `!(h&M)` where `M=((~0) << (32-N))`. However, it's also interesting to note that in the Gear entropy analysis above we need at least N+4 bytes in the window, so adding 5 bytes by shifting the mask 5 places should be sufficient to get your N bits of entropy. However, using the most significant bits would mean you are using a full window size of 32-4 = 28bytes, which is probably still better.

changed:
-It means that the hash effectively includes history data before the window, since chunk boundary selection also depends on how far back the last chunk boundary was.
-
-The chunk boundaries have a degree of "hardness" based on their hash. A hash with more zero bits is "harder" and more likely to be chosen as a chunk boundary even if there was another boundary before it. These "hard boundaries" force the synchronisation of chunk boundaries after changes harder.
-
-The "hard cliff" at the target-size feels a little ugly, but it does avoid complicating things. An incremental adjustment to the probabilities to give a more normal distribution would be interesting to try/analize. This together with `h <= r` hash judgment can give a continuously variable match probability.
-
-
* It means that the hash judgement effectively includes history data before the window, since chunk boundary selection also depends on how far back the last chunk boundary was.

* The chunk boundaries have a degree of "hardness" based on their hash. A hash with more zero bits is "harder" and more likely to be chosen as a chunk boundary even if there was another boundary before it. These "hard boundaries" force the synchronisation of chunk boundaries after changes harder.

The "hard cliff" at the target-size feels a little ugly, but it does avoid complicating things. An incremental adjustment to the probabilities to give a more normal distribution would be interesting to try/analyze. This together with `h <= r` hash judgment can give a continuously variable match probability.


Better Normalized Chunking
==========================

We can use a hash judgement of `h <= p` where p is a fixed point probability of being a chunk boundary between 0.0 -> 1.0 scaled into a 32bit number. This lets use use arbitrary chunking probabilities based on the size to give whatever chunk-size distribution we want.

Using the following gives a pretty good approximation of a standard distribution centered on the target_size::

    min_size=target_size/4
    max_size=target_size*2
    p = ((size - min_size)/(max_size - min_size))^2

You can see this graphed here;

https://docs.google.com/spreadsheets/d/1ofg3-ZX04mbGA-9HZAcu5shfkbPYEO_PGW_4UuKFQpc/edit?usp=sharing

Note that p as a fixed point unsigned 32bit number can be calculated efficiently incrementally like this::

    p = 0
    step = 2^32 / (max_size - min_size)^2
    incr = step * 2

    for each iteration:
      h = <update rollsum>
      if h < p:
         <chunk breakpoint>
      p += step
      step += incr
    
Note that provided (max_size - min_size) is not a power of 2 then this will be rounded down and will not quite reach 1.0 (which would overflow P anyway) by the time you reach the max size. If (max_size - min_size) is close or larger than 2**16 then incr will be too small to be accurate enough. If you want to calculate it more accurately you'd need integer fractions like this::


    p = 0
    denom = (max_size - min_size)^2
    step = 2^32 / denom
    step_frac = 2^32 % denom
    incr = step * 2
    incr_fract = step_frac * 2
    if incr_frac >= denom:
        incr += 1
        incr_frac -= denom

    for each iteration:
      h = <update rollsum>
      if h < p:
         <chunk breakpoint>
      p += step
      step += incr
      step_frac += incr_frac
      if step_frac >= denom:
        step += 1
        step_frac -= denom

or (probably better) update p and step at a courser granularity like this every 1024 bytes::

    p = 0
    step = 2^32 / ((max_size - min_size)/1024)^2
    incr = step * 2

    for each iteration:
      h = <update rollsum>
      if h < p:
         <chunk breakpoint>
      if size % 1024 == 0:
        p += step
        step += incr


It's not entirely clear that doing this actually does improve re-syncing breakpoints, which is necessary to maximize duplicate detection, but it will give a much better chunk size distribution.

Comparing the hash to a probability like this probably requires that the hash used is fairly good, which is a stronger requirement than for `(h&mask == r)` style hash judgement. Things like Gear are probably sufficient provided the byte-mapping table is good. Buzhash and Rollsum/Adler/Bup without a decent byte-mapping table are not.

min_size=target_size/4
max_size=target_size*2
p = ((size - min_size)/(max_size - min_size))^2

p = 0
step = 2^32 / (max_size - min_size)^2
incr = step * 2

for each iteration:
  h = <update rollsum>
  if h < p:
     <chunk breakpoint>
  p += step
  step += incr

p = 0
denom = (max_size - min_size)^2
step = 2^32 / denom
step_frac = 2^32 % denom
incr = step * 2
incr_fract = step_frac * 2
if incr_frac >= denom:
    incr += 1
    incr_frac -= denom

for each iteration:
  h = <update rollsum>
  if h < p:
     <chunk breakpoint>
  p += step
  step += incr
  step_frac += incr_frac
  if step_frac >= denom:
    step += 1
    step_frac -= denom

p = 0
step = 2^32 / ((max_size - min_size)/1024)^2
incr = step * 2

for each iteration:
  h = <update rollsum>
  if h < p:
     <chunk breakpoint>
  if size % 1024 == 0:
    p += step
    step += incr