Rolling Hash Algorithm

Spec v4 (2021-03-09)

Make a rolling hash based file diffing algorithm. When comparing original and an updated version of an input, it should return a description ("delta") which can be used to upgrade an original version of the file into the new file. The description contains the chunks which:

• Can be reused from the original file
• have been added or modified and thus would need to be synchronized

The real-world use case for this type of construct could be a distributed file storage system. This reduces the need for bandwidth and storage. If many people have the same file stored on Dropbox, for example, there's no need to upload it again.

A library that does a similar thing is rdiff. You don't need to fulfill the patch part of the API, only signature and delta.

Requirements

• Hashing function gets the data as a parameter. Separate possible filesystem operations.
• Chunk size can be fixed or dynamic, but must be split to at least two chunks on any sufficiently sized data.
• Should be able to recognize changes between chunks. Only the exact differing locations should be added to the delta.
• Well-written unit tests function well in describing the operation, no UI necessary.

Checklist

1. Input/output operations are separated from the calculations
2. detects chunk changes and/or additions
3. detects chunk removals
4. detects additions between chunks with shifted original chunks

Research Materials

• https://www.samba.org/~tridge/phd_thesis.pdf
• https://www.andrew.cmu.edu/course/15-749/READINGS/required/cas/tridgell96.pdf
• https://developpaper.com/principle-and-application-of-rsync-algorithm/
• https://rsync.samba.org/tech_report/node3.html