]> wimlib.net Git - wimlib/commitdiff
Switch from suffix array match-finder to binary tree match-finder
authorEric Biggers <ebiggers3@gmail.com>
Mon, 2 Jun 2014 03:01:14 +0000 (22:01 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Sat, 7 Jun 2014 21:32:04 +0000 (16:32 -0500)
This uses less memory (8 bytes overhead per position vs. 14), is faster,
requires less code (no libdivsufsort), and in some tests actually results
in a better compression ratio.

A binary tree match-finder was used in wimlib v1.5.2 but it didn't seem
as good then, probably because it was combined with a slow block division
algorithm for LZX.

Repeat offsets are now handled differently.  The binary tree match-finder
itself doesn't have any logic for repeat offsets at all; instead, the
match-choosing code (now implemented separately for LZX and LZMS) now
does special checks for matches at repeat offsets.

Since less memory is used for match-finding now, increase the default
LZMS pack chunk size from 2^25 (33554432) to 2^26 (67108864).


No differences found