> 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

> 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.