Ecosyste.ms: Packages

proxy.golang.org : github.com/whyrusleeping/chunker

Package chunker implements Content Defined Chunking (CDC) based on a rolling Rabin Checksum. The function RandomPolynomial() returns a new random polynomial of degree 53 for use with the chunker. The degree 53 is chosen because it is the largest prime below 64-8 = 56, so that the top 8 bits of an uint64 can be used for optimising calculations in the chunker. A random polynomial is chosen selecting 64 random bits, masking away bits 64..54 and setting bit 53 to one (otherwise the polynomial is not of the desired degree) and bit 0 to one (otherwise the polynomial is trivially reducible), so that 51 bits are chosen at random. This process is repeated until Irreducible() returns true, then this polynomials is returned. If this doesn't happen after 1 million tries, the function returns an error. The probability for selecting an irreducible polynomial at random is about 7.5% ( (2^53-2)/53 / 2^51), so the probability that no irreducible polynomial has been found after 100 tries is lower than 0.04%. During development the results have been verified using the computational discrete algebra system GAP, which can be obtained from the website at http://www.gap-system.org/. For filtering a given list of polynomials in hexadecimal coefficient notation, the following script can be used: All irreducible polynomials from the list are written to the output. An introduction to Rabin Fingerprints/Checksums can be found in the following articles: Michael O. Rabin (1981): "Fingerprinting by Random Polynomials" http://www.xmailserver.org/rabin.pdf Ross N. Williams (1993): "A Painless Guide to CRC Error Detection Algorithms" http://www.zlib.net/crc_v3.txt Andrei Z. Broder (1993): "Some Applications of Rabin's Fingerprinting Method" http://www.xmailserver.org/rabin_apps.pdf Shuhong Gao and Daniel Panario (1997): "Tests and Constructions of Irreducible Polynomials over Finite Fields" http://www.math.clemson.edu/~sgao/papers/GP97a.pdf Andrew Kadatch, Bob Jenkins (2007): "Everything we know about CRC but afraid to forget" http://crcutil.googlecode.com/files/crc-doc.1.0.pdf

Registry - Source - Documentation - JSON
purl: pkg:golang/github.com/whyrusleeping/chunker
License: BSD-2-Clause
Latest release: over 5 years ago
First release: over 5 years ago
Namespace: github.com/whyrusleeping
Dependent packages: 446
Dependent repositories: 1,099
Stars: 3 on GitHub
Forks: 4 on GitHub
Docker dependents: 66
Docker downloads: 64,626,590
See more repository details: repos.ecosyste.ms
Last synced: 16 days ago

• Readme
• Versions 1
• Dependent Packages 446
• Maintainers 0