Multi-symbol, multi-format, parallel symbol decoder for hardware decompression engines

Patent metadata

Field	Value
Publication number	US-9819359-B1
Application number	US-201715588626-A
Country	US
Kind code	B1
Filing date	May 6, 2017
Priority date	Dec 11, 2016
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

In some data compression algorithms and/or standards, the compressed data comprises variable length symbols. A set of parallel decoders speculatively decode/decompress a window (i.e., sub-block) of data. Each of the decoders attempts to decode/decompress a symbol that starts at a different location in the compressed data block. Once the decoders have finished decoding a symbol (or determined that a valid symbol does not begin at the beginning of the window assigned to that decoder), a symbol strider selects the decoder outputs corresponding to valid symbols. The symbol strider successively selects decoder outputs based on the size of the previous symbols that were found to be valid. When the next valid symbol begins outside the current window, its location is stored to indicate the location of the next valid symbol in a subsequent window.

First claim

What is claimed is:

1. A data decompressor, comprising:
a compressed data supplier to provide a first set of distinct windows of contiguous data from a block of compressed data to each of a plurality of symbol decoders;
the plurality of symbol decoders to each attempt, concurrently, to fully decode a respective variable length symbol that begins at a respective starting location of the window of contiguous data provided to the respective symbol decoder;
the plurality of symbol decoders to include a first symbol decoder that is to receive a first window of data from the first set of distinct windows having a beginning that corresponds to a beginning of a first variable length valid symbol, the first symbol decoder to fully decode the first variable length valid symbol and to determine a first length of the first variable length valid symbol; and,
the plurality of symbol decoders to include a second symbol decoder that is to receive a second window of data having a beginning that corresponds to a beginning of a second variable length valid symbol, the output of the second symbol decoder to be selected as an output of the data decompressor based on the first length.

2. The data decompressor of claim 1 , wherein the second variable length valid symbol is in the first set of distinct windows.

3. The data decompressor of claim 1 , wherein the second variable length valid symbol is in a second set of distinct windows.

4. The data decompressor of claim 3 , wherein the second symbol decoder is to fully decode a second variable length valid symbol and is to determine a second length of the second variable length valid symbol.

5. The data decompressor of claim 4 , wherein the second set of distinct windows is to, based on the first length, be determined to include the second variable length valid symbol.

6. The data decompressor of claim 1 , wherein a first location in the block of compressed data where the first variable length valid symbol begins is to be calculated concurrently with a second location in the block of compressed data where the second variable length valid symbol begins.

7. The data decompressor of claim 1 , wherein a first indicator corresponding to the first symbol decoder is to be calculated concurrently with a second indicator corresponding to the second symbol decoder.

8. An integrated circuit to decompress data, comprising:
a first symbol decoder of a plurality of symbol decoders to be operated concurrently with each other, the first symbol decoder to receive, from a data supplier, a first window of data from a block of compressed data, the first window of data to correspond to a beginning of a first valid symbol, the first symbol decoder to fully decode the first valid symbol and to determine a length of the first valid symbol;
a second symbol decoder of the plurality of symbol decoders, the second symbol decoder to receive, from the data supplier, a second window of data from the block of compressed data, the second window of data to correspond to a beginning of a second valid symbol, the second symbol decoder to fully decode the second valid symbol and to determine a length of the second valid symbol;
a third symbol decoder of the plurality of symbol decoders, the third symbol decoder to receive, from the data supplier, a third window of data from the block of compressed data, the third window of data corresponding to a beginning of an apparently valid symbol, the third symbol decoder to fully decode the apparently valid symbol and to determine a length of the apparently valid symbol, the third window of data to comprise data that is located between the first window of data and the second window of data in the block of compressed data; and,
a symbol selector to, based on the length of the first symbol, select the second symbol as a valid symbol.

9. The integrated circuit of claim 8 , wherein, based on the length of the first symbol, the symbol selector does not select the apparently valid symbol.

10. The integrated circuit of claim 9 , wherein the first symbol decoder is to receive, from the data supplier, a fourth window of data from the block of compressed data, the fourth window of data to correspond to a beginning of a third valid symbol, the first symbol decoder to fully decode the third valid symbol and to determine a length of the third valid symbol.

11. The integrated circuit of claim 10 , wherein the third valid symbol is determined to be valid based on the length of the first valid symbol and the length of the second valid symbol.

12. The integrated circuit of claim 11 , wherein a first location in the block of compressed data where the first variable length valid symbol begins is to be calculated concurrently with a second location in the block of compressed data where the second variable length valid symbol begins and a third location in the block of compressed data where the third variable length valid symbol begins.

13. The integrated circuit of claim 11 , wherein a first indicator corresponding to the first symbol decoder is to be calculated concurrently with a second indicator corresponding to the second symbol decoder and a third indicator corresponding to the third symbol decoder.

14. A method of decompressing data, comprising:
providing a plurality of symbol decoders with a first sub-block of data from a block of compressed data, each symbol decoder being provided with a distinct window of contiguous data from the first sub-block of data, the plurality of symbol decoders including a first symbol decoder that receives a first window of contiguous data, a beginning of the first window corresponding to a beginning of a first variable length valid symbol, the plurality of symbol decoders including a second symbol decoder that receives a second window of contiguous data, a beginning of the second window corresponding to a beginning of a second variable length valid symbol in the sub-block of data;
decoding, in parallel, by each of the plurality of symbol decoders, a respective variable length symbol and determining a respective bit length of the respective variable length symbol from the respective window of data that was provided to the respective symbol decoders, the first symbol decoder decoding the first variable length valid symbol, the second symbol decoder decoding the second variable length valid symbol;
based on the bit length of the first variable length valid symbol, determining whether the second variable length symbol decoded by the second symbol decoder is a valid symbol; and,
based on the bit length of the first variable length valid symbol and the bit length of the second variable length valid symbol, selecting a third symbol decoder that is to be provided with a third window of data from a second sub-block of data from the block of compressed data, a beginning of the third window of data corresponding to a beginning of a third variable length valid symbol.

15. The integrated circuit of claim 14 , wherein a first location in the block of compressed data where the first variable length valid symbol begins, a second location in the block of compressed data where the second variable length valid symbol begins, a third location in the block of compressed data where the third variable length valid symbol begins, a first indicator corresponding to the first symbol decoder, a second indicator corresponding to the second symbol decoder, and a third indicator corresponding to the third symbol decoder are to be calculated concurrently.

16. The method of claim 14 , further comprising:
providing the plurality of symbol decoders with the second sub-block of data from t

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Havlik Robert W
• Erickson Michael J
• Vattakandy Amar
• Gladding Derek E

Classifications

• H03M7/6005

  Decoder aspects · CPC title

• H03M7/42 Primary

  using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)} · CPC title

• H03M7/6023

  Parallelization · CPC title

• H03M7/6011

  Encoder aspects · CPC title

• H03M7/4037

  Prefix coding · CPC title