A Rolling Hash Algorithm and the Implementation to LZ4 Data Compression

LZ77 is a dictionary compression algorithm by replacing the repeating sequence with the addresses of the previous referenced data in the stream. To find out these repetition, the LZ77 encoder maintains a hashing table, which have to frequently calculate hash values during the encoding process. In this paper, we present a class of rolling hash functions, that can calculate multiple hash values via a carry-less multiplication instruction. Then the...