Voxelium

Attila T. Áfra's blog about pixels, voxels and threads

Doboz: compression library with very fast decompression

with 2 comments

Another side project of mine is Doboz (Hungarian for ‘box’), a small LZ-based data compression library written in C++ with very high decompression speed and close to zlib compression ratio. The decompression speed is typically between 700-1200 MB/s on an Intel Core i7-620M processor. However, compression is quite slow: about 2-3 MB/s. Both compression and decompression are memory safe.

There are many similar libraries (e.g., QuickLZ, FastLZ, LZO), but most of them were designed for both fast compression and decompression. Doboz is different: its compressor is really slow, but it can achieve better compression ratios and much higher decompression speeds than other libraries.

You can read more information (including detailed performance comparisons) about Doboz and grab the source code from here. I’ve made the source available under the zlib/libpng license. You can also download a package containing Windows binaries of a simple command-line compressor and a benchmark tool from here. The benchmark tool compares the performance of Doboz, QuickLZ, and zlib using the user-specified test file. I recommend using the 64-bit version because it’s slightly faster.

I took many ideas from QuickLZ and 7-zip (the dictionary), and combined them with my own tricks. Doboz is a really simple LZSS compressor that uses a relatively large, 2 MB dictionary and variable-length matches. Instead of decoding the matches with lots of branches, I use a small lookup table. This provides a nice performance boost.

static const struct {
	uint32_t mask; // the mask for the entire encoded match
	uint8_t offsetShift;
	uint8_t lengthMask;
	uint8_t lengthShift;
	int8_t size; // the size of the encoded match in bytes
} lut[] = {
	{0xff,        2,   0, 0, 1}, // (0)00
	{0xffff,      2,   0, 0, 2}, // (0)01
	{0xffff,      6,  15, 2, 2}, // (0)10
	{0xffffff,    8,  31, 3, 3}, // (0)11
	{0xff,        2,   0, 0, 1}, // (1)00 = (0)00
	{0xffff,      2,   0, 0, 2}, // (1)01 = (0)01
	{0xffff,      6,  15, 2, 2}, // (1)10 = (0)10
	{0xffffffff, 11, 255, 3, 4}, // 111
};

uint32_t word = fastRead(source, 4);
uint32_t i = word & 7;

match.offset = (word & lut[i].mask) >> lut[i].offsetShift;
match.length = ((word >> lut[i].lengthShift) & lut[i].lengthMask) + MIN_MATCH_LENGTH;

Another crucial part of the decompression algorithm is match copying. We must be careful with that because matches may overlap. Obviously, copying the bytes one by one is not the fastest method, but at least it works correctly for overlapping matches. Both QuickLZ and Doboz copy matches in chunks of 4 bytes, but they solve the overlap problem differently. Copying in chunks is valid as long as the distance between the source and destination pointers is not less than the chunk size. QuickLZ’s approach is to limit the minimum match offset to 2 and advance the pointers with only 3 bytes in every copy iteration. This means that, theoretically, 25% of the performance is wasted, even if the match is non-overlapping. In order to avoid this, I first check whether the match offset is less than the chunk size. If it is, I copy the first 3 bytes (the minimum match length) one by one and move back the source pointer a few bytes to increase the distance to the destination pointer. Then, I copy the rest of the match in chunks. This method works without limiting the minimum match offset.

int i = 0;

if (match.offset < 4) {
	do {
		fastWrite(outputIterator + i, fastRead(matchString + i, 1), 1);
		++i;
	} while (i < 3);
	matchString -= 2 + (match.offset & 1);
}

do {
	fastWrite(outputIterator + i, fastRead(matchString + i, 4), 4);
	i += 4;
} while (i < match.length);

outputIterator += match.length;

Doboz is memory safe, which means that it will never read or write beyond the specified buffers, even if the compressed data is corrupted. Of course, this slows down the decompression because of the additional buffer checks. I’ve managed to decrease the amount of necessary checks by appending a few dummy bytes to the compressed data. This doesn’t really hurt the compression ratio and it makes safe decompression so fast it’s not worth disabling (about 5-7% slower than unsafe).

Writing this little library was quite fun and I’ve learned a lot during the process. I hope you’ll find it useful in some way. 🙂

Advertisements

Written by Attila Áfra

March 19, 2011 at 5:27 pm

Posted in Compression, Doboz

2 Responses

Subscribe to comments with RSS.

  1. There is a benchmark of (de) compression libraries, including Doboz here:

    http://altdevblogaday.org/

    Erwin Coumans

    April 23, 2011 at 5:27 am

  2. I ported it to .NET (you can find sources here: https://doboz4net.codeplex.com/)

    Milosz Krajewski

    May 13, 2013 at 4:57 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: