I thought you had to write "sync points" inside a gzip file to support reading from locations other than the start. If you somehow bypass that requirement, can you explain how?
I thought you had to write "sync points" inside a gzip file to support reading from locations other than the start. If you somehow bypass that requirement, can you explain how?
Rapidgzip does not require sync points because it simply looks for them. The approach is similar to gzrecover [1], i.e., you "simply" try to start decompression at every possible >bit< position. Of course that would be too slow (~200 kB/s), so instead I use several skip and lookup tables to speed up this search to achieve roughly (~70 MB/s).
However, that search for deflate block boundaries can yield positions that look valid but which actually aren't, e.g., think of gzip-compressed gzip files. These cases also need to be detected and filtered. Rapidgzip does this filtering and the parallelization by using a cache which stores prefetched decompressed results with the start bit position as key. When the previous block has finished decoding, we know the start position of the next block, and if it exists in the cache, then that result is used. This implicitly filters out valid-looking duds, i.e., false positives.
The proof of concept of looking for block boundaries and to resolve and parallelize interdependencies between consecutive blocks, was introduced by pugz [1]. However, it had no detection for false positives and therefore did only work for compressed text files. I built upon this to make it work without assumptions on the compressed data, and I also added capabilities for random access, for which the prefetch-cache architecture also is very suited, so that I can use it in ratarmount.
[0] http://www.htslib.org/doc/bgzip.html
For people like me who have battled this demon before, it would help to explicitly say that you support any gzip file by way of this special magic. At least on my cursory reading of your page I did not understand this. And I never heard of gzrecover, so thanks for that too.
I like how the pugz paper starts with "Decompressing a file made by the gzip program at an arbitrary location is in principle impossible." Until today I believed the same!