Method and apparatus for high performance compression and decompression

Abstract

An apparatus and method for performing efficient lossless compression. For example, one embodiment of an apparatus comprises: first compression circuitry to identify and replace one or more repeated bit strings from an input data stream with distances to the one or more repeated bit strings, the first compression circuitry to generate a first compressed data stream comprising literal-length data identifying a first instance of each repeated bit string and distance data comprising distances from the first instance to each repeated instance of the repeated bit string; second compression circuitry to perform sorting, tree generation, and length calculations for literal-length values and distance values of the first compressed data stream, the second compression circuitry comprising: variable length code mapping circuitry to map each literal-length value and distance value to a variable length code; header generation circuitry to generate a header for a final compressed bit stream using the length calculations; and a transcoder to substitute the variable length codes in place of the literal-length and distance values to generate a compressed bit stream body, wherein the transcoder operates in parallel with the header generation circuitry; and bit stream merge circuitry to combine the header with the compressed bit stream body to generate a final lossless compressed bitstream.