Compression of data that permits direct reconstruction of arbitrary portions of the uncompressed data. Also, the direct reconstruction of arbitrary portions of the uncompressed data. Conventional compression is done such that decompression has to begin either at the very beginning of the data, or at particular intervals (e.g., at block boundaries—every 64 kilobytes) within the data. However, the principles described herein permit decompression to begin at any point within the compressed data, without having to decompress any prior portion of the file. Thus, the principles described herein permit random access of the compressed data. In accordance with the principles described herein, this is accomplished by using an index that correlates positions within the uncompressed data with positions within the compressed data.

To decompress encoded data, a Huffman code tree stored in a data header may need to be decompressed and rebuilt. A bit length histogram table is used in a hardware design to more efficiently decompress the Huffman code tree. The bit length histogram table relates each bit length used by the Canonical Huffman Code (CHC) symbols to a corresponding number of symbols in the encoding that have that bit length. Performing decompression using bit length histogram table allows part of the Huffman tree decompression to be performed in a single pass.

An input control unit collectively sends a plurality of pieces of variable length code data. A primary analysis processing unit processes a first piece of variable length code data, recognizes zero run information, group number information, and overhead bit information relating thereto, and outputs them to a frequency conversion unit. A continuous analysis processing unit processes one or more pieces of variable length code data subsequent to the first piece of variable length code data. In the case of variable length code data targeted for a predetermined process, the continuous analysis processing unit recognizes zero run information, group number information, and overhead bit information relating thereto, and output them to the frequency conversion unit. In the case of not the variable length code data targeted for the predetermined process, the continuous analysis processing unit discards this and subsequent pieces of data.

Apparatus and method for efficient compression block decoding using content-addressable structure for header processing. For example, one embodiment of an apparatus comprises: a header parser to extract a sequence of tokens and corresponding length values from a header of a compression block, the tokens and corresponding length values associated with a type of compression used to compress a payload of the compression block; and a content-addressable data structure builder to construct a content-addressable data structure based on the tokens and length values, the content-addressable data structure builder to write an entry in the content-addressable data structure comprising a length value and a count value, the count value indicating a number of times the length value was previously written to an entry in the content-addressable data structure.

A method for providing codewords, the method may include receiving by an input buffer, one or more chunks of data; calculating a location of relevant bits within one or more chunks of data; wherein the relevant bits comprise (a) variable length retrieval information used during a retrieval process of a first type codeword, or (b) a second type codeword; performing the retrieval process of the first type codeword and retrieving the first type codeword from a memory unit that stores only a fraction of a codebook, the codebook comprises first type codewords and second type codewords; determining whether the relevant bits comprises the second type codeword or not; and outputting the second type codeword or the first type codeword, based on the determination.

According to one embodiment, a dividing circuit divides a first bit string into second bit strings and outputs the divided second bit strings. The dividing circuit includes first, second, and third blocks. The first block executes first operation for each bit of a third bit string in the first bit string. The first operation is to calculate a head bit of a succeeding symbol when one bit is assumed to be a head of one symbol. The second block executes second operation for each bit of the third bit string for a set number of times. The second operation is to overwrite boundary information associated with one bit with boundary information associated with a bit indicated by the boundary information. The third block divides the third bit string immediately before a second bit indicated by boundary information associated with a first bit of the third bit string.

Compression of data that permits direct reconstruction of arbitrary portions of the uncompressed data. Also, the direct reconstruction of arbitrary portions of the uncompressed data. Conventional compression is done such that decompression has to begin either at the very beginning of the data, or at particular intervals (e.g., at block boundaries—every 64 kilobytes) within the data. However, the principles described herein permit decompression to begin at any point within the compressed data, without having to decompress any prior portion of the file. Thus, the principles described herein permit random access of the compressed data. In accordance with the principles described herein, this is accomplished by using an index that correlates positions within the uncompressed data with positions within the compressed data.

A binary arithmetic device includes an LPS/MPS determining unit that determines, using a context variable, a range length, and an offset, whether a code is an inferior probability code or a superior probability code, a renormalization processing unit that performs renormalization processing on the range length and the offset, and a context-variable calculating unit that derives the binary data of the code using a determination result and updates the context variable according to the determination result. The renormalization processing unit 15 includes a first renormalizing unit and a second renormalizing unit and a selecting unit that selects, according to the determination result, an output of the first renormalizing unit or an output of the second renormalizing unit.

In one embodiment, an apparatus comprises a decompression engine to determine a plurality of tokens used to encode a block of data; populate a lookup table with at least two of the tokens in order of increasing token length; disable a first portion of the lookup table and enable a second portion of the lookup table based on a value of a payload of the block of data; and search for a match between a token and the payload in the second portion of the lookup table.

According to one embodiment, a dividing circuit divides a first bit string into second bit strings and outputs the divided second bit strings. The dividing circuit includes first, second, and third blocks. The first block executes first operation for each bit of a third bit string in the first bit string. The first operation is to calculate a head bit of a succeeding symbol when one bit is assumed to be a head of one symbol. The second block executes second operation for each bit of the third bit string for a set number of times. The second operation is to overwrite boundary information associated with one bit with boundary information associated with a bit indicated by the boundary information. The third block divides the third bit string immediately before a second bit indicated by boundary information associated with a first bit of the third bit string.