4 ms·

Decompressing zlib/DEFLATE streams, in the general case, is an inherently serial task. It cannot be meaningfully parallelised. The "trick" used by Apple, and a

Decompressing zlib/DEFLATE streams, in the general case, is an inherently serial task. It cannot be meaningfully parallelised. The "trick" used by Apple, and a few other encoders, is to flush the zlib state every so often (ZLIB_FULL_FLUSH), which means that subsequent data is both byte alligned, and does not make any backreferences to before the sync. If you know where these sync points are (Apple encodes this information in their non-standard "iDOT" chunk) then you can start decompressing from that point, in an isolated thread. There are ongoing discussions as to how this metadata could be standardised: https://github.com/w3c/PNG-spec/issues/54 https://github.com/w3c/PNG-spec/issues/54

vbphprubyjsgo 5y ago
I think that's what restart markers are for in JPEG from the original spec. IIRC in JPEG you can have markers that are marked as "crucial for proper decode" and programs should reject the image if they don't understand them. Maybe the latter was from PNG I forget.
lifthrasiir 5y ago
Technically speaking you can also speculatively decode Huffman coded bitstreams because the use of canonical Huffman tree means that the end-of-block symbol is almost likely the longest code and has no 0 bits, so you can start decoding at a long string of 1 bits. Of course this doesn't solve an issue of shared LZSS window across multiple blocks.
- xyzzy_plugh 5y ago
  This is hilarious to me, but makes complete sense. Do you know if this has ever been done anywhere?
  - lifthrasiir 5y ago
    There is indeed a hilarious backstory. Back in time one of my friends was looking for a task for the Distributed Computing course where you write a program for the Cell microprocessor, and I half-jokingly suggested this, not realizing that it won't work at all because of the shared window. The friend eventually came to realize that issue and couldn't finish the project in time, but still got a good grade solely because of the novelty of the task (!). (According to that friend virtually everyone else did the parallel JPEG stuffs.)
    - xyzzy_plugh 5y ago
      This doesn't surprise me. The Cell architecture wrought more insane hacks than good designs.

vbphprubyjsgo 5y ago

I think that's what restart markers are for in JPEG from the original spec. IIRC in JPEG you can have markers that are marked as "crucial for proper decode" and programs should reject the image if they don't understand them. Maybe the latter was from PNG I forget.

lifthrasiir 5y ago

Technically speaking you can also speculatively decode Huffman coded bitstreams because the use of canonical Huffman tree means that the end-of-block symbol is almost likely the longest code and has no 0 bits, so you can start decoding at a long string of 1 bits. Of course this doesn't solve an issue of shared LZSS window across multiple blocks.

xyzzy_plugh 5y ago
This is hilarious to me, but makes complete sense. Do you know if this has ever been done anywhere?
- lifthrasiir 5y ago
  There is indeed a hilarious backstory. Back in time one of my friends was looking for a task for the Distributed Computing course where you write a program for the Cell microprocessor, and I half-jokingly suggested this, not realizing that it won't work at all because of the shared window. The friend eventually came to realize that issue and couldn't finish the project in time, but still got a good grade solely because of the novelty of the task (!). (According to that friend virtually everyone else did the parallel JPEG stuffs.)
  - xyzzy_plugh 5y ago
    This doesn't surprise me. The Cell architecture wrought more insane hacks than good designs.