This is my first release for RCM (realtime compression madness), a fast byte-aligned dictionary compressor with 64KB windows. I plan to post source after cleaning up a few parts.
Tests with enwik8 and enwik9 (semi-optimal parse, executable attached):
The format is very simple. A 4-byte int (block size, worst-case is <1.01*64KB) indicating the length of the compressed block follows zero or more packets. Each packet starts with 2 bits:
0 - number of literals follows, up to 6 bits: 0 to 63. If >= 63, next bytes encode further length. Example:
1 - Short match. Length is the next 3 bits, min length (4) to min length + 7. Distance is the next 3 bits, 1 to 8.
int sym_lit = token >> 2;
int num_literals = sym_lit;
if (sym_lit == 63)
while (sym_lit >= 0)
sym_lit = input[rp++];
num_literals += sym_lit;
sym_lit -= 255;
2 - Medium match. Length is the next 6 bits, 1 to 64. Distance is the next two bytes.
3 - Long match. Same as medium match, but length also includes the next byte (up to 6+8 bits, 16k max match length).
Example for these:
The executable I have attached uses a sliding window, so input size block size is 2*64 KB (read every 64 KB) and output size is 1.01*64KB. Reading small I/O blocks is bad for performance, so timings are not great. There are two compression modes, fast and semi-optimal (greedy on long matches to stop wasting time in long regions). Larger window sizes would improve compression. I chose 64 KB for 16-bit addresses and because the fast compressor (hash chain) has an overhead of ~80 KB (needed low overhead and on stack memory for my purposes).
int len, dist;
if (op == 1)
len = (token >> 2) & 7;
dist = (token >> 5) & 7;
int sym_dist = input[rp++];
dist += sym_dist << 3;
else if (op & 0x2)
len = (token >> 2) & 63;
dist = input[rp++];
dist += input[rp++] << 8;
if (op == 3)
len += input[rp++] << 6;
len += MATCH_MIN;
Disclaimer: I use the same algorithm as a pure in-memory compressor for a commercial project (my IP). However, I believe others can benefit from sharing the results, including the reference source (once I clean it up) as free for non-commercial purposes.
c [input] [output] - Compress input file to output file (fast)
co [input] [output] - Compress input file to output file (best)
d [input] [output] - Decompress input file to output file
h [input] - CRC32 for input file