Pipelined decompression of sliding window compressed data

Abstract

Decompressing sliding window compressed data requires reference to previously decompressed character sequences. Previously decompressed data is stored in a history buffer to satisfy these 'back references.' As each decompressed/decoded character is emitted, it is stored in this history buffer. Thus, for each decompressed character that is emitted, the history buffer may need to be accessed at least twice—once to retrieve the backreference, and once to store the emitted character. A pipeline architecture is disclosed that stores decompressed characters in a write queue that coalesces eight or more emitted characters before they are stored in the history buffer memory. This reduces collisions between accessing the history buffer memory to retrieve the backreferences and the storing of the emitted character. This also allows the use of a single-ported memory which is less expensive than a multi-ported memory.