The most important design principle behind LZ4 has been simplicity. It allows for an easy code, and fast execution.
Let's start with the compressed data format.
The compressed block is composed of sequences.
Each sequence starts with a token.
The token is a one byte value, separated into two 4-bits fields (which therefore range from 0 to 15).
The first field uses the 4 high-bits of the token, and indicates the length of literals. If it is 0, then there is no literal. If it is 15, then we need to add some more bytes to indicate the full length. Each additional byte then represent a value of 0 to 255, which is added to the previous value to produce a total length. When the byte value is 255, another byte is output.
There can be any number of bytes following the token. There is no "size limit". As a sidenote, here is the reason why a not-compressible input data block can be expanded by up to 0.4%.
Following the token and optional literal length bytes, are the literals themselves. Literals are uncompressed bytes, to be copied as-is.
They are exactly as numerous as previously decoded into length of literals. It's possible that there are zero literal.
Following the literals is the offset. This is a 2 bytes value, between 0 and 65535. It represents the position of the match to be copied from. Note that 0 is an invalid value, never used. 1 means "current position - 1 byte". 65536 cannot be coded, so the maximum offset value is really 65535. The value is stored using "little endian" format.
Then we need to extract the matchlength. For this, we use the second token field, a 4-bits value, from 0 to 15. There is an baselength to apply, which is the minimum length of a match, called minmatch. This minimum is 4. As a consequence, a value of 0 means a match length of 4 bytes, and a value of 15 means a match length of 19+ bytes.
Similar to literal length, on reaching the highest possible value (15), we output additional bytes, one at a time, with values ranging from 0 to 255. They are added to total to provide the final matchlength. A 255 value means there is another byte to read and add. There is no limit to the number of optional bytes that can be output this way (This points towards a maximum achievable compression ratio of ~250).
With the offset and the matchlength, the decoder can now proceed to copy the repetitive data from the already decoded buffer. Note that it is necessary to pay attention to overlapped copy, when matchlength > offset (typically when there are numerous consecutive zeroes).
By decoding the matchlength, we reach the end of the sequence, and start another one.
Graphically, the sequence looks like this :
Click for larger display
Note that the last sequence stops right after literals field.
There are specific parsing rules to respect to be compatible with the reference decoder :
1) The last 5 bytes are always literals
2) The last match cannot start within the last 12 bytes
Consequently, a file with less then 13 bytes can only be represented as literals
These rules are in place to benefit speed and ensure buffer limits are never crossed.
Regarding the way LZ4 searches and finds matches, note that there is no restriction on the method used. It could be a full search, using advanced structures such as MMC, BST or standard hash chains, a fast scan, a 2D hash table, well whatever. Advanced parsing can also be achieved while respecting full format compatibility (typically achieved by LZ4-HC).
The "fast" version of LZ4 hosted on Google Code uses a fast scan strategy, which is a single-cell wide hash table. Each position in the input data block gets "hashed", using the first 4 bytes (minmatch). Then the position is stored at the hashed position.
The size of the hash table can be modified while respecting full format compatibility. For restricted memory systems, this is an important feature, since the hash size can be reduced to 12 bits, or even 10 bits (1024 positions, needing only 4K). Obviously, the smaller the table, the more collisions (false positive) we get, reducing compression effectiveness. But it nonetheless still works, and remain fully compatible with more complex and memory-hungry versions. The decoder do not care of the method used to find matches, and requires no additional memory.
Note : the format above describes the content of an LZ4 compressed block. It is the raw compression format, with no additional feature, and is intended to be integrated into a program, which will wrap around its own custom enveloppe information.
If you are looking for a portable and interoperable format, which can be understood by other LZ4-compatible programs, you'll have to look at the LZ4 Framing format. In a nutshell, the framing format allows the compression of large files or data stream of arbitrary size, and will organize data into a flow of smaller compressed blocks with (optionnally) verified checksum.
I read your spec to reimplement from the description. I think it is complete, the only thing that surprised me is that the matches are allowed to overlap forwards. It might be worth mentioning. My impl was intended to experiment with vectorization but in the end it did not work.
ReplyDeleteYes, this is a classic LZ77 design.
DeleteWith matches autorised to overlap forward, it makes the equivalent of RLE (Run Length Encoding) for free, and even repeated 2-bytes / 4-bytes sequences, which are very common.
This is in contrast with LZ78 for example, which never takes advantage of overlap. Neither PPM, nor BWT, etc.
That being said, i'm not sure to understand in which way it prevented your experiment on vectorization to work.
Rgds
With the specification of "The last match cannot start within the last 12 bytes" to be handled by the reference decoder, it is not an equivalent of RLE for free. However, anything that compresses well with RLE is very likely going to compress well with LZ4 unless you pick a worse case of unique byte tokens repeated 12 at a time.
DeleteNot to be confused : minimum match length is still only 4.
DeleteSo, if a token is repeated 12 times, it will be caught by the algorithm.
The only exception is for the last 12 bytes within input data. Even though this restriction is supposed to have a negative impact on compression ratio, its impact on real-life data is negligible.
Thank you for creating a clear and easily understood specification.
ReplyDeleteI believe you should add a specification of the size limit of literal length and match length. As specified currently, a correct decoder must be able to process an infinite number of bytes in either field. The best would be to specify the maximum value (not length) of either field as a power of two. The maximum length can then be inferred.
There is a typographical error in your specification: "additional" is the correct spelling.
It was in the initial spirit of the specification that sizes (of literal length or match length) can be unlimited.
DeleteIn practice though, it is necessarily limited, by the maximum size that the current implementation supports, which is ~1.9 GB.
A future implementation may support larger block sizes though.
There is also a theoretical issue with limited literal length : in case of compressing an encrypted file, it is possible that the compressed output consists only of literals. In this case, the size of literal length is the same as the size of the file. Thus, it cannot be limited.
Would you mind telling why you think enforcing a limit on length would be beneficial ?
Typo corrected. Thanks for the hint.
Hello Yann, Perhaps it is pedantic, but with no limit specified, a "correct" implementation is impossible to create.
DeleteAnother concern is efficiency. To determine a length field value > 14, "we need to add some more bytes to indicate the full length. Each additional byte then represent a value of 0 to 255, which is added to the previous value to produce a total length. When the byte value is 255, another byte is output."
I understand you chose to add byte values, rather than use a compressed integer, such as the bottom 7 bits as the next most significant bits (with top bit as signal as another byte needed). I believe this was to reduce the output size when the lengths are small. However, with an unlimited length field, we can have a huge number of bytes representing the length. So it seems there must be a limit on the length or the compression becomes inefficient.
Regarding maximum size :
Deletesince block input size is currently limited to 1.9GB, what about limiting length sizes to this value too ?
Regarding length encoding :
The LZ4 format was defined years ago. Initially, it was just created to "learn" compression, so its primary design was simplicity. High speed was then a "side-effect". Since then, priorities have been a bit reversed, but the format remained "stable", a key property to build trust around it.
I can understand that different trade-off can be invented, and may seem better. And indeed, if I had to re-invent LZ4 today, I would probably change a few things, including the way "big lengthes" are encoded.
But don't expect these corner cases scenario to really make a difference in "normal" circumstances. A few people have already attempted such variant, and benched that in most circumstances, the difference is small (<1%) if only length encoding is modified.
Larger difference can be achieved by modifying the fixed 64KB frame, allowing repetitions at larger distances, but with bigger impact on performance and complexity. (You can have a look at Shrinker and LZnib for example)
"the difference is small (<1%) if only length encoding is modified": I expect this to be true if only small length values are encoded. This was why I expected a fairly small length limit: I assumed the LZ4 format was only useful in cases where lengths are small, as the length encoding is poor for large lengths. A length of (2^16, 16K) requires 65 bytes, 64K requires 257 bytes, 256K requires 2028 bytes, and so forth. I am not speaking of the algorithm to compute the literals, but simply the length representation. Whether such lengths would be computed, I don't know.
DeleteI cannot say what the best limit would be, you would have to decide, as you are the expert. Hopefully I explained why it was surprising the limit is currently infinite, and why I expected a small limit.
DeleteSure. It's possible to introduce the notion of "implementation-dependent limit".
DeleteFor example, current LZ4 reference C implementation has an implementation-limit of 1.9 GB. But other implementations could have different limits.
This seems more important for decoders. So, whenever a decoder detects a length beyond its limit, it could refuse to continue decoding, and send an error message instead.
There's a way to handle the encoding limit without hurting the compression ratio nor limiting the total file size (eg: streaming-compatible) : you just have to specify that a given litteral length is never followed by an offset (just like the last block). That way you can easily have a litteral limit of 1 GB (30 bits) and if you want to encode litterals larger than this, you just have to stop at 1 GB and put a new litteral, which will just take a few bytes every gigabyte. BTW, thanks for the description and kudos for this smart and fast design!
DeleteYes, I realized that point later on.
DeleteUnfortunately, at that point, LZ4 is already widely deployed, with a stable format. It's no longer possible to change that now.
A correct "limit" for streaming would probably be something like ~4KB. There is a direct relation between this limit and the amount of "memory buffer" a streaming implementation must allocate.
Currently, my "work around" to this issue is to use "small blocks", typically 64KB. So the issue is solved by the upper "streaming layer" format.
I like to see a bigger version of the tiny picture.
ReplyDeleteWould you be so kind and upload one?
Which tiny picture are you talking about ? The first one on the top left ? It's just an illustration, taken from http://fastcompression.blogspot.fr/p/compression-benchmark.html
DeleteDid you also evaluate Base-128 Varints (how Protocol Buffers encode ints) for lengths? I assume they might be slightly smaller, but slower, since they require more arithmetic operations.
ReplyDeleteNot for the compression format. The loss of speed would be sensible.
Deletecan u tell me how much memory consume by lz4 during uncompression
ReplyDeleteThe algorithm itself doesn't consume any memory.
DeleteThe used memory is limited to the input and output buffer. So it's implementation dependent.
sir, i have only 64kb memory so what i have to do. what should be defined as chunksze
DeleteWell, it can be any value you want.
DeleteLZ4 compression algorithm (lz4.c & lz4.h) doesn't define a chunk size. You can select 64kb, 32kb, 16kb, or even a weird 10936 bytes, there is no limitation. This parameter is fully implementation specific.
Since I don't know what's the source of the data, what's the surrounding buffer environment, etc. it's not possible to be more precise.
LZ4 is known to work on system specs as low as 1979's Atari XL or 1984's Amstrad. So there is no blocking point in making in work into 64kb.
Regards
how to compress full Directory or Folder?
ReplyDeleteCompressing directory, or even file attributes is outside of the scope of LZ4. LZ4 has the same responsibility as zlib, and therefore compresses "stream of bytes", irrespective of metadata.
ReplyDeleteTo compress directory, there are 2 possible methods :
1) On Windows : use the LZ4 installer program, at http://fastcompression.blogspot.fr/p/lz4.html. It will enable a new context menu option by right-clicking a folder : "compress with LZ4". The resulting file will be the directory compressed. You can, of course, regenerate the directory by decompressing the file (just double-click on it).
2) On Linux : use 'tar' to aggregate directory content, pipe the result to lz4 (exactly the same as gzip).
Thanks for the excellent and concise description. There's only one detail that seems to be missing (or maybe I missed it): You say that the token gets divided into two four bit fields. However, I don't think you said how those pack into the byte.
ReplyDeleteAre they packed little endian with the first field in bits 0-3 and the second field in bits 4-7, or big endian?
I suppose I could go look at the code. It just seems a shame that it isn't included with this otherwise-complete looking description.
The format is explained in more detail in the file LZ4_format_description.txt, which is provided with the source code, and be consulted online here :
Deletehttps://code.google.com/p/lz4/source/browse/trunk/lz4_format_description.txt
Within it, you'll find a more precise answer to your question :
"Each sequence starts with a token.
The token is a one byte value, separated into two 4-bits fields.
Therefore each field ranges from 0 to 15.
The first field uses the 4 high-bits of the token.
It provides the length of literals to follow."
I'll update this blog post to add this information.
First of all thanks for this amazing LZ4 and also for this short explanation.
ReplyDeleteIf I got this right, according to offset being hard-coded to 2-bytes we can leverage match back only up yo 64k. And this could explain why in my use case the compression ratio is not increasing when I try to feed it with bigger buffers even if the data repeated is very frequent.
So here it comes the question: theoretically, if memory is not an issue, by increasing the 'offset' to e.g. up to 32bits (no more fixed size at that point) and making the hash-table bigger, we could achieve a more than trivial improvement in compression ratio on bigger buffers.
Does this sound good or am I missing something?
Thanks in advance.
Hi Carlo.
DeleteIndeed, a 32-bits offset would open larger perspectives to find duplicated sequences. However, it would also make the cost of offsets larger.
Currently, a "match" (duplicate sequence) costs approximately 3 bytes : 2-bytes offset + 1 byte token. Your proposal would increase that cost to 5 bytes. That means you'll need matches of length at least 6 to compress. It also means that you'll need matches which are all, on average 2 bytes larger, to pay off.
Will that work ? Well, maybe. The problem is, there is no single definitive answer to this question. You'll have to test your hypothesis on your use cases to find out if this modification is worthy.
Some trivial corner cases :
1) Input source size <= 64 KB ? The modification will obviously be detrimental.
2) Large Repeated pattern at distance > 64 KB ? The modification will obviously benefit a lot.
Unfortunately, real use cases are more complex.
My guess is that, on average, the 32-bits offset strategy will cost more than it gains. But then again, if your use case contains large repeated patterns at large distances, it will more likely be a win.
Thanks for advice Yann.
DeleteI was also underestimating the power of L1 cache, so that when increasing hash table beyond your good default, it always start to decrease performances anyway.
But at the same time I had the chance to play a bit with it and seem to have found some good tradeoff, working decently in all use cases. I'll drop you an email with more details through the dedicated form.
Thanks again.
I am using lz4mt multi-threaded version of lz4 and in my workflow I am sending thousands of large size files (620 MB) from client to server and when file reaches on server my rule will trigger and compress file using lz4 and then remove uncompressed file. The problem is sometimes when I remove uncompressed file, I am not able to get compressed file of right size its because lz4 returns immediately before sending output to disk.
ReplyDeleteSo is there any way lz4 will remove uncompressed file itself after compressing as done by bzip2.
Input: bzip2 uncompress_file
Output: Compressed file only
whereas
Input: lz4 uncompress_file
Output: (Uncompressed + Compressed) file
If possible please tell me as soon as possible.
I'm not sure to fully understand your question, but since it is unrelated to LZ4 block format, could you please redirect it to the LZ4 forum board :
Deletehttps://groups.google.com/forum/#!forum/lz4c
lz4mt is Takayuki's work, so he will probably be in better position to answer your question on the forum board.
Submit an Internet Draft (https://datatracker.ietf.org/submit/)?
ReplyDeleteWell, if anyone has any experience with this process, he's welcomed
DeleteIs it correct to assume that this format can't compress more than 255x?
ReplyDeleteAssuming that you have a giant block memory that's simply cleared to 0, when you encode match length it'll keep doing adding length a byte at a time, so you'll only get 2^8 length per byte...
I have some data that I'd like to use lz4 on, but it occasionally has some very, very long runs, so that worries me a bit.
Yes that's correct.
DeleteAlthough if your data is really very redundant, you may have some luck at combining LZ4 with a second pass using LZ4 HC for example.
The reason is, LZ4 keep the property of generating "byte aligned" data, which traditional compressor (zip etc.) do not. So it can be used as a king of "preprocessor".
For more information, see notes from Vitor Oliveira :
https://groups.google.com/forum/#!msg/lz4c/DcN5SgFywwk/AVMOPri0O3gJ
Thanks for the quick reply, that makes perfect sense. I think that strategy might work here, thanks!
DeleteYann, it looks like an SSE version of LZ4 decode can be up to twice as fast as pure C code, this is at least what my testing seems to show!
ReplyDeleteWow, a 100% speed increase is quite a serious feat, indeed.
DeleteIn my (previous) experiments, SSE version wasn't bringing anything close to that. But SSE was just limited to replacing LZ4_wildCopy(). Maybe you have some more drastic change in mind.
I can only encourage you to complete your testings and then share relevant details when you feel it's ready enough.
The key idea is to implement RLE encoding of any match that occurs within 16 bytes of the current output point, this way the output can be generated by stores only, with no need to do any actual copies.
DeleteI use the SSE3 PSHUFB opcode (which was first available as permute in Altivec/PowerPC) to take in the 16 bytes beginning at the match location, then shuffle those bytes into two target SSE registers so that they contain the next 32 bytes to be written.
In the store loop I write those two registers in each iteration, then increment the write pointer by the highest value which is a multiple of the offset and fits in 32.
I.e. if the offset was 3 bytes, then I will write 30 bytes in each iteration, which means that most matches will only take a single iteration.
Here's the entire sse decoding function, please note that it has absolutely zero error handling!
static byte stepSize16[17] = {16,16,16,15,16,15,12,14,16,9,10,11,12,13,14,15,16};
static __m128i replicateTable[17] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1},
{0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0},
{0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3},
{0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0},
{0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3},
{0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1},
{0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7},
{0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6},
{0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5},
{0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4},
{0,1,2,3,4,5,6,7,8,9,10,11,0,1,2,3},
{0,1,2,3,4,5,6,7,8,9,10,11,12,0,1,2},
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,0,1},
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0},
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}};
static byte stepSize32[17] = {32,32,32,30,32,30,30,28,32,27,30,22,24,26,28,30,16};
static __m128i replicateTable2[17] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1},
{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1},
{0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3},
{1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1},
{4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1},
{2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3},
{0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7},
{7,8,0,1,2,3,4,5,6,7,8,0,1,2,3,4},
{6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1},
{5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9},
{4,5,6,7,8,9,10,11,0,1,2,3,4,5,6,7},
{3,4,5,6,7,8,9,10,11,12,0,1,2,3,4,5},
{2,3,4,5,6,7,8,9,10,11,12,13,0,1,2,3},
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,1},
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}};
unsigned lz4_decode_sse(byte *dest, byte *src, unsigned len)
{
byte *d = dest, *e = src+len;
unsigned token, lit_len, mat_len;
if (!len) return 0;
goto start;
__m128i a;
byte *dstore, *msrc;
do {
unsigned mat_offset = src[0] + (src[1] << 8);
src += 2;
msrc = d - mat_offset;
if (mat_len == 15) {
do {
token = *src++;
mat_len += token;
} while (token == 255);
}
mat_len += 4;
uint32_t step;
dstore = d;
d += mat_len;
if (mat_offset <= 16) { // Bulk store only!
a = _mm_loadu_si128((const __m128i *)msrc);
__m128i a2 = _mm_shuffle_epi8(a, replicateTable2[mat_offset]);
a = _mm_shuffle_epi8(a, replicateTable[mat_offset]);
step = stepSize32[mat_offset];
do {
_mm_storeu_si128((__m128i *)dstore, a);
_mm_storeu_si128((__m128i *)(dstore+16), a2);
dstore += step;
} while (dstore < d);
}
else {
do {
a = _mm_loadu_si128((const __m128i *)msrc);
_mm_storeu_si128((__m128i *)dstore, a);
msrc += sizeof(a);
dstore += sizeof(a);
} while (dstore < d);
}
start:
token = *src++;
lit_len = token >> 4;
mat_len = token & 15;
if (token >= 0xf0) { // lit_len == 15
do {
token = *src++;
lit_len += token;
} while (token == 255);
}
dstore = d;
msrc = src;
d += lit_len;
src += lit_len;
do {
a = _mm_loadu_si128((const __m128i *)msrc);
_mm_storeu_si128((__m128i *)dstore, a);
msrc += sizeof(a);
dstore += sizeof(a);
} while (dstore < d);
} while (src < e);
return (d-dest);
}
That's definitely very clever.
DeleteI was initially skeptical that only overlapping matches would produce such a boost, since they are supposed to only count as a minority of situations,
but I see you are using SSE load/store instruction everywhere, for normal matches & literals too, so yes, I guess it must add up.
There will be a need to add some "clean conditions" to ensure memory guarantee at borders, but overall, this looks very good.
I can't wait testing your code....
I had a chance to test your code using Visual 2012 compiler.
DeleteIt required only a few minor tweaks to get it running.
(tmmintrin.h mostly)
Here are some preliminary benchmark numbers,
using fullbench test program, on the Silesia test corpus.
LZ4_decompress_safe : 1770 MB/s
LZ4_decompress_fast : 1850 MB/s
lz4_decode_sse : 2050 MB/s
So there is definitely an improvement, but I can't reproduce the +100% claim using this setup.
I had less luck with GCC and Clang.
Both complain a lot about initialization tables.
Interestingly, both also warn : unused variable 'stepSize16'
Perhaps more importantly, both fail the corrution test, which wasn't the case for Visual.
I had to disable the corruption test to run the benchmark, and finally got these results :
LZ4_decompress_safe : 1630 MB/s
LZ4_decompress_fast : 1715 MB/s
lz4_decode_sse : 1900 MB/s
Here also, a measurable gain >~ 10%, but no double speed.
Result difference might be explained by the test data corpus.
Silesia is relatively good corpus, avoiding pathological datasets from which wrong conclusions could be projected. I can only recommend using it for benchmark tests.
Best Regards
PS. Sorry about the formatting, the blog sw stripped my nice indenting. :-(
ReplyDeleteI have downloaded the Silesia Corpus, and like you I don't see the same huge wins as I got from a set of very small files (less than 64 KB output for each of them).
ReplyDeleteOTOH, any win is a win, right? :-)
I'm thinking that it would be useful to implement dictionaries (& chaining) by simply allocating an initial 64 KB buffer before the input file read location, and to get rid of most of the buffer overflow tests by making the output buffer large enough that it would be sufficient to check or those conditions when having an extended length chunk, then switch to slower/safer code when/if you get too close to the end.
I.e. an extended version of what you are currently doing in some places.
I am still using VS2008 which might be the cause of some minor performance differences, but probably not anything significant: LZ4 decoding with SSE should be dominated by two things:
Branch misses and any extra memory costs due to unaligned operations and/or partial memory overwrites when I have RLE coding of non-power-of-two chunks.
I will try and see if it is better to always copy 16-byte chunks instead of getting 22-32 bytes of sometimes overlapping chunks, but I don't expect that to be a win: I suspect pretty much all odd-offset RLE runs to be so short as to fit in a single iteration.
I still think that using PSHUFB to fixup short RLE offsets to be very nice, avoiding a lot of single-byte copies, but when such RLE compression turns out to be rare, it doesn't really matter.
Re. stepSize16: This was from a version that used a single SSE register for RLE chunks, limiting the step size to the 9-16 byte range instead of the current 22-32. The difference between those two seems miniscule.
It's a great code you put together.
DeleteIf you decide to make it public, through a github repository for example, I can certainly link your SSE implementation from LZ4 homepage, even if it consists "solely" of an optimized decoder. Other platform-specifics decoders are linked there too.
I've done some more testing, it seems like the only really significant optimization is in the handling of RLE patterns of up to 16 bytes which I handle with stores only instead of copy operations: This does reduce the memory/cache traffic significantly.
ReplyDeleteUsing just the PSHUFB trick to fixup the first 16 bytes so that the rest can fall into the full-size (16 or 32 bytes) copy loop is 10-20% slower on webster, x-ray and xml. (All compressed with -9)
Generally speaking most modern compression algorithms give roughly the same compression, and with regard to the number of cores that you can use at once, it is up to you to decide how many you want to use. Generally speaking (unless you are creating large archives) there is no reason to need more than one though. In addition, with multiple cores doing the compression, the bottleneck may become the hard drive. Legacy zip compression is akin to the Deflate method in 7-zip, and will offer the most compatibility between different compression software.
ReplyDeleteLing
How can I recognize that a particular sequence is the last one?
ReplyDeleteThe mere fact that its literal length is 5 surely isn't enough, since there might be other literals 5 bytes long, of course.
Similarly, match length being 0 is not enough, since after adding minmatch=4 it is no longer 0 but 4, and there surely can be matches of that length as well.
So what is the actual condition that indicates that a particular sequence is the final one?
Or maybe it is being recognized by the fact that there is no backref field after the literal? I can't think of anything else that could indicate that we're done, but this seems to be a bit of a stretch, because if the file is corrupted and it so happens that the corruption just erased the backref word, this should be an error, but instead it would be recognized as the final sequence, with no error :q
Can you help me with solving this mystery? I can't find the answer anywhere in the specification.
In general, the last sequence is identified as such because the code just reached the end of the input buffer. Therefore, the most common method is to provide the size of the compressed block to the decoding function.
DeleteA less common method, but still a possible one, is to provide the size of data to regenerate. On reaching that amount, the decoder knows that it's done, and can determine how many bytes it consumed from input.
Therefore, additional metadata (size of compressed block, or size of data to regenerate) is required to properly decode an LZ4 block.
Note that LZ4 is not designed to guarantee that a corruption will necessarily be detected. Without an additional checksum, such as XXH32 employed in LZ4frame, there are countless corruption events that can happen and remain undetected by the block decoder.
That being said, not respecting the end-of-block parsing conditions isn't one of them. If a compressed block doesn't finish with 5+ literals, it's likely to be flagged as an error by most versions of the reference decoders.