3 ms·

Interesting, I never thought about looking for the EOB symbol like that but it makes sense. I would guess that some blocks you wouldn't be finding with this are

Interesting, I never thought about looking for the EOB symbol like that but it makes sense. I would guess that some blocks you wouldn't be finding with this are, e.g., compressed zeros, because there would basically be only two Huffman codes, 0 for repeating the last symbol as much times as possible, and 1 for EOB it might even be the other way around. The overhead of looking for deflate blocks can actually be made arbitrarily small by simply increasing the chunk size because you only have to check the first ~64 kiB of the chunk for a valid start position. 99% of compressors limit the produced deflate block size to something below 128 KiB, that's why. Of course, lager chunk sizes have their own problems, like decreased performance for "small" files and higher memory usage because at least one chunk per core has to be kept in memory. The performance improvements on the block finder I made over the one in pugz made it possible to reduce the optimal chunk size from 16 MiB down to 4 MiB and thereby slash the memory usage by 4. 1 MiB chunks might also be fine if you can stomach the ~10% slowdown. The LZ77 windows are something that I skipped over in my other answer. They are a problem. In order to decompress at a position without knowing the LZ77 window, the idea proposed by pugz was to use a dummy 16-bit LZ77 window initialized with unique IDs. That way, you can decompress into a 16-bit data stream and in a second step, when the window becomes known, you do a one-to-one replacement of the 16-bit unique IDs into 8-bit actual data from the real LZ77 window that has become known at this point. Decoding to 16-bit instead of 8-bit requires to modify the decompressor or write one from scratch and it also adds overhead because more memory needs to be traversed and of course because of the second replacement step that now has to be done.

lifthrasiir 3y ago
> [...] there would basically be only two Huffman codes, 0 for repeating the last symbol as much times as possible, and 1 for EOB it might even be the other way around. You are correct. More generally EOB won't be the lexicographically last symbol if there are length codes used only once in given block. But it's already possible that the Huffman tree was not optimal anyway, so such cases are safe to ignore as we can rely on the fallback. > The overhead of looking for deflate blocks can actually be made arbitrarily small by simply increasing the chunk size because you only have to check the first ~64 kiB of the chunk for a valid start position. But it still means that you need to probe all 2^19 positions. The fact that such probing can be made efficient surprised me the most. After reading your paper (especially the Table 1), it seems that rejecting valid trees with unused symbols were the defining factor, given that allowing them will increase false positives by at least 8 orders of magnitude. > [...] the idea proposed by pugz was to use a dummy 16-bit LZ77 window initialized with unique IDs. Unique IDs per block, right? I also assume there is some encoding for definitive literals (okay if only the standard DEFLATE is supported), and that second pass has to be serialized so it should make heavy use of gather instructions for performance (another reason that it didn't come to my mind at that time). Still in awe, to be honest.
- mxmlnkn 3y ago
  > it seems that rejecting valid trees with unused symbols were the defining factor You are correct. This assumption helps a lot to make the block finder faster. I tested with lots of compressors and I have never found one that creates "bloating Huffman codes", as I called the error code in rapidgzip. Note that, ironically, the Fixed Huffman blocks actually contain such a (predefined) Huffman code with two unused symbols. I'm not sure why it was defined in such a way, but it would allow searching Fixed Huffman blocks by looking for long bit sequences without these forbidden codes. However, Fixed Huffman blocks are rather rare, mostly for very small files (<256 B) or for the last blocks at the end of a compressed file. I currently do not look for those. > Unique IDs per block, right? I try to differentiate between deflate blocks (~8-128 KiB) and decompression chunks (~4 MiB). The unique IDs are per chunk, i.e., per unknown window preceding each chunk, which is at maximum 32 KiB. The encoding is something like: 0-255: fully resolved literals, 32 * 1024 to 64 * 1024 - 1: unique IDs corresponding to the index pointing in the unknown window. The second pass can also be mostly parallelized. The only serialized part is the propagation of the windows right before each chunk. The unique IDs in the last 32 KiB of each chunk can be resolved knowing only the last 32 KiB of the preceding chunk. This needs to be serial. However, the rest of the 4 MiB chunks can then be resolved in parallel and this is also done in parallel. A prior version of rapidgzip did not parallelize this and it didn't scale to a lot of cores.

lifthrasiir 3y ago

> [...] there would basically be only two Huffman codes, 0 for repeating the last symbol as much times as possible, and 1 for EOB it might even be the other way around. You are correct. More generally EOB won't be the lexicographically last symbol if there are length codes used only once in given block. But it's already possible that the Huffman tree was not optimal anyway, so such cases are safe to ignore as we can rely on the fallback. > The overhead of looking for deflate blocks can actually be made arbitrarily small by simply increasing the chunk size because you only have to check the first ~64 kiB of the chunk for a valid start position. But it still means that you need to probe all 2^19 positions. The fact that such probing can be made efficient surprised me the most. After reading your paper (especially the Table 1), it seems that rejecting valid trees with unused symbols were the defining factor, given that allowing them will increase false positives by at least 8 orders of magnitude. > [...] the idea proposed by pugz was to use a dummy 16-bit LZ77 window initialized with unique IDs. Unique IDs per block, right? I also assume there is some encoding for definitive literals (okay if only the standard DEFLATE is supported), and that second pass has to be serialized so it should make heavy use of gather instructions for performance (another reason that it didn't come to my mind at that time). Still in awe, to be honest.

mxmlnkn 3y ago
> it seems that rejecting valid trees with unused symbols were the defining factor You are correct. This assumption helps a lot to make the block finder faster. I tested with lots of compressors and I have never found one that creates "bloating Huffman codes", as I called the error code in rapidgzip. Note that, ironically, the Fixed Huffman blocks actually contain such a (predefined) Huffman code with two unused symbols. I'm not sure why it was defined in such a way, but it would allow searching Fixed Huffman blocks by looking for long bit sequences without these forbidden codes. However, Fixed Huffman blocks are rather rare, mostly for very small files (<256 B) or for the last blocks at the end of a compressed file. I currently do not look for those. > Unique IDs per block, right? I try to differentiate between deflate blocks (~8-128 KiB) and decompression chunks (~4 MiB). The unique IDs are per chunk, i.e., per unknown window preceding each chunk, which is at maximum 32 KiB. The encoding is something like: 0-255: fully resolved literals, 32 * 1024 to 64 * 1024 - 1: unique IDs corresponding to the index pointing in the unknown window. The second pass can also be mostly parallelized. The only serialized part is the propagation of the windows right before each chunk. The unique IDs in the last 32 KiB of each chunk can be resolved knowing only the last 32 KiB of the preceding chunk. This needs to be serial. However, the rest of the 4 MiB chunks can then be resolved in parallel and this is also done in parallel. A prior version of rapidgzip did not parallelize this and it didn't scale to a lot of cores.