Method and apparatus for storing compressed data

• US 6,452,602 B1
• Filed: 12/13/1999
• Issued: 09/17/2002
• Est. Priority Date: 12/13/1999
• Status: Expired due to Term

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI International SRL (Advanced Micro Devices, Inc.)
• Inventors: Morein, Stephen L.
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US09/459,809
• Time in Patent Office: 1,009 Days
• Field of Search: 345/555, 345/552, 345/582, 345/536, 345/501, 345/564, 345/586, 345/587, 382/232, 382/233, 382/244, 382/245
• US Class Current: 345/555
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence

Abstract

A method and apparatus for storing data for a plurality of data blocks in a compressed format in memory is presented where the compression scheme used for compressing the data blocks may vary. For each data block included in the plurality of data blocks, the data block is compressed using a compression scheme that is included in a set of predetermined compression schemes. The resulting compressed data set is of a size included in a set of predetermined sizes that correspond to the particular compression scheme utilized. The compressed data set for each block is then stored in a compressed data set memory, where the compressed data sets are stored in groups. A descriptor data set corresponding to each group is then stored in a descriptor memory, where the descriptor data set includes an encoded compression descriptor for each data block included in the group. The data descriptor set also stores a base address that corresponds to a starting location for that group in the compressed data set memory. The encoded compression descriptor for each data block encodes the compression scheme used for that data block and the resulting compressed data set size. When the data for a particular data block is required in an uncompressed format, the storage location of the compressed data set corresponding to that block can be determined from the descriptor data set for the group that includes the particular block required. By combining the base address within the descriptor data set with the sizes of all of the compressed data blocks in the group that precede the particular block in the compressed data set memory, the address for the compressed data set required for decompression can be determined. The compressed data set can then be fetched from memory and decompressed based on the compression scheme as determined from the encoded compression descriptor corresponding to that data block.

Claims

1. A method for compressing data corresponding to a plurality of data blocks, wherein each of the plurality of data blocks includes a plurality of data values, comprising:

for each data block of the plurality of data blocks;

compressing the data block using a compression scheme included in a set of predetermined compression schemes to produce a compressed data set of a size included in a set of predetermined sizes corresponding to the compression scheme;

storing the compressed data set in a compressed data set memory, wherein the compressed data set is included in a selected group of compressed data sets in the compressed data set memory, wherein a plurality of groups of compressed data sets are stored in the compressed data set memory; and

storing an encoded compression descriptor for the data block in a descriptor data set corresponding to the selected group, wherein the descriptor data set includes a base address value and a plurality of ordered encoded compression descriptors corresponding to compressed data sets included in the selected group, wherein ordering of the plurality of ordered encoded compression descriptors is based on storage order of the compressed data sets of the selected group in the compressed data set memory, wherein the descriptor data set is stored in a descriptor memory, wherein the encoded compression descriptor encodes the compression scheme and the size corresponding to the compressed data set;

receiving an address corresponding to a first data block of the plurality of data blocks;

determining a first group that includes a compressed data set corresponding to the first data block;

fetching a descriptor data set corresponding to the first group from the descriptor memory;

adding the base address value of the descriptor data set corresponding to the first group to size values for data blocks that precede the first data block in the first group as stored in the compressed data set memory to determine an address for the compressed data set corresponding to the first data block in the compressed data set memory, wherein the size values for data blocks that precede the first data block are determined by decoding the encoded compression descriptors corresponding to the data blocks that precede the first data block in the first group;

fetching the compressed data set corresponding to the first data block from the compressed data set memory using the address for the compressed data set corresponding to the first data block in the compressed data set memory;

determining the compression scheme corresponding to the compressed data set for the first data block from the encoded compression descriptor for the first data block; and

decompressing the compressed data set for the first data block to produce data values for the first data block, wherein the decompressing is performed based on the compression scheme corresponding to the compressed data set for the first data block.

2. The method of claim 1, wherein data values for each of the plurality of data blocks are texture map data values.

3. The method of claim 2, wherein each of the data blocks corresponds to a M-by-N texel block.

4. The method of claim 3 further comprises texturing pixels using the texture map data values for the first data block.

5. The method of claim 1, wherein the compressed data set memory and the descriptor memory are included in a common memory structure.

6. The method of claim 1 further comprises storing the data values for the first data block in a data cache for use in data processing operations.

7. The method of claim 1, wherein fetching the descriptor data set further comprises storing the descriptor data set in a descriptor cache.

8. The method of claim 1, wherein each encoded compression descriptor includes K bits, wherein the K bits encode 2^K potential compression scheme/size combinations.

9. The method of claim 1, wherein compressing each data block of the plurality of data blocks further comprises compressing at least a portion of the data blocks in the plurality of data blocks using a variable length compression scheme.

10. A method for storing compressed data for a plurality of data blocks, comprising:

selecting a compression scheme for each data block of the plurality of data blocks, wherein each compression scheme selected is selected from a set of predetermined compression schemes;

compressing each data block using the compression scheme selected for the data block to produce a compressed data set corresponding to each data block, wherein compressing compresses data within each data block to a size corresponding to the compression scheme selected for the data block, wherein each compression scheme supports at least one size;

storing the compressed data sets corresponding to the plurality of data blocks in a first memory, wherein the compressed data sets are grouped into a plurality of groups, wherein compressed data sets in each of the plurality of groups are stored in a predetermined order within the first memory; and

storing a descriptor data set for each group of the plurality of groups in a second memory, wherein each descriptor data set includes a base address for the group in the first memory and an encoded compression descriptor for each compressed data set included in the group, wherein each encoded compression descriptor encodes the compression scheme and the size for each compressed data set, wherein ordering of encoded compression descriptors in the descriptor data set corresponds to ordering of the compressed data sets for the group as stored in the first memory.

11. The method of claim 10 further comprises decompressing a compressed data set for a selected data block of the plurality of data blocks, wherein decompressing includes:

fetching a descriptor data set from the second memory that includes an encoded compression descriptor for the compressed data set that corresponds to the selected data block;

determining an address of the compressed data set corresponding to the selected data set in the first memory based on the base address of the descriptor data set fetched from the second memory and sizes of other compressed data blocks as indicated by additional encoded compression descriptors included in the descriptor data set fetched;

fetching the compressed data block corresponding to the selected data set from the first memory using the address;

determining the compression scheme used for compressing the compressed data set corresponding to the selected data block based on the encoded compression descriptor corresponding to the compressed data set in the descriptor data set fetched from the second memory; and

decompressing the compressed data set fetched from the first memory based on the compression scheme used for compressing the compressed data set to produce data of the selected data block.

12. The method of claim 11, wherein fetching the compressed data block corresponding to the selected data set further comprises:

determining the size of the compressed data block based on the encoded compression descriptor corresponding to the compressed data set in the descriptor data set fetched from the second memory; and

fetching the compressed data set from the first memory using the address and the size of the compressed data block.

13. A data compression circuit that stores compressed data for a plurality of data blocks, comprising:

a compressed data set memory that stores a plurality of compressed data sets, wherein each of the plurality of compressed data sets corresponds to one of the plurality of data blocks, wherein at least a portion of the plurality of compressed data sets are compressed using a variable length compression scheme, wherein the compressed data sets are stored in the compressed data set memory in a predetermined order;

a descriptor memory that stores a plurality of data descriptor sets, wherein each data descriptor set of the plurality of data descriptor sets includes a base address pointer and a plurality of encoded compression descriptors for a group of data blocks, wherein the encoded compression descriptors in each data descriptor set are ordered based on the predetermined order of the compressed data sets for a corresponding group as stored in the compressed data set memory, wherein each base address pointer indicates a starting address for compressed data blocks included in a corresponding group as stored in the compressed data set memory, wherein each encoded compression descriptor in a data descriptor set indicates a compression scheme and size value for a data block included in the group of data blocks to which the data descriptor set corresponds;

a decompression block operably coupled to the compressed data set memory, wherein the decompression block receives a selected compressed data set and an indication as to a compression scheme used for compressing the selected compressed data set, wherein the decompression block decompresses the selected compressed data set received based on the compression scheme as indicated to produce uncompressed data block data; and

a controller operably coupled to the decompression block, the descriptor memory, and the compressed data set memory, wherein the controller receives coordinates corresponding to a selected data block, wherein the controller retrieves a selected descriptor data set corresponding to the selected data block from the descriptor memory, wherein the controller determines an address for a selected compressed data set in the compressed data set memory based on the selected descriptor data set, wherein the controller issues control signals to the compressed data set memory based on the address such that the compressed data set memory provides the selected compressed data set to the decompression block, wherein the selected compressed data set corresponds to the selected data block, wherein the controller determines a compression scheme used for compressing the selected compressed data set based on a encoded compression descriptor included in the descriptor data set retrieved, wherein the controller provides the indication as to the compression scheme to the decompression block.

14. The data compression circuit of claim 13, wherein the plurality of data blocks correspond to a texture map such that each of the plurality of data block includes a portion of the texture map.

15. The data compression circuit of claim 14, wherein the compressed data set memory stores compressed texel colors for each portion of the texture map.

16. The data compression circuit of claim 15 further comprises a texture mapping block operably coupled to the controller and the decompression block, wherein the texture mapping block provides coordinates corresponding to a portion of the texture map to the control block and utilizes resulting uncompressed data block data from the decompression block to perform texturing operations related to video graphics data.

17. The data compression circuit of claim 13 further comprises a descriptor cache operably coupled to the descriptor memory and the controller, wherein the descriptor cache stores at least a portion of the plurality of data descriptor sets stored in the descriptor memory.

18. The data compression circuit of claim 13 further comprises a data cache operably coupled to the decompression block and the controller, wherein data cache caches uncompressed data block data.

19. The data compression circuit of claim 13 further comprises a compression block operably coupled to the compressed data set memory and the descriptor memory, wherein the compression block receives uncompressed data corresponding to the plurality of data blocks and compresses each of the plurality of data blocks to produce the plurality of compressed data sets stored in the compressed data set memory, wherein the compression block generates the plurality of data descriptor sets that are stored in the descriptor memory based on compression performed on the plurality of data blocks.

20. The data compression circuit of claim 13, wherein each of the encoded compression descriptors include K bits, wherein each encoded compression descriptor encodes one of 2^K potential compression scheme/size combinations.

21. The data compression circuit of claim 13, wherein the controller determines the address for a compressed data set by adding the base address pointer for the selected descriptor data set to size values corresponding to data blocks that precede the selected data block in the selected descriptor data set.

22. The data compression circuit of claim 21, wherein the controller adds the base address pointer to the size values using a configurable adder tree that includes a plurality of decoding blocks that decode the size values from encoded compression descriptors included in the selected descriptor data set.

23. A data processing system, comprising:

a processing module; and

memory operably coupled to the processing module, wherein the memory stores operating instructions that, when executed by the processing module, cause the processing module to perform functions that include;

for each data block of a plurality of data blocks, wherein each of the plurality of data blocks includes a plurality of data values;

compressing the data block using a compression scheme included in a set of predetermined compression schemes to produce a compressed data set of a size included in a set of predetermined sizes corresponding to the compression scheme;

storing the compressed data set in a compressed data set memory, wherein the compressed data set is included in a selected group of compressed data sets in the compressed data set memory, wherein a plurality of groups of compressed data sets are stored in the compressed data set memory; and

storing an encoded compression descriptor for the data block in a descriptor data set corresponding to the selected group, wherein the descriptor data set includes a base address value and a plurality of ordered encoded compression descriptors corresponding to compressed data sets included in the selected group, wherein ordering of the plurality of ordered encoded compression descriptors is based on storage order of the compressed data sets of the selected group in the compressed data set memory,wherein the descriptor data set is stored in a descriptor memory, wherein the encoded compression descriptor encodes the compression scheme and the size corresponding to the compressed data set;

receiving an address corresponding to a first data block of the plurality of data blocks;

determining a first group that includes a compressed data set corresponding to the first data block;

fetching a descriptor data set corresponding to the first group from the descriptor memory;

adding the base address value of the descriptor data set corresponding to the first group to size values for data blocks that precede the first data block in the first group as stored in the compressed data set memory to determine an address for the compressed data set corresponding to the first data block in the compressed data set memory, wherein the size values for data blocks that precede the first data block are determined by decoding the encoded compression descriptors corresponding to the data blocks that precede the first data block in the descriptor data set corresponding to the first group;

fetching the compressed data set corresponding to the first data block from the compressed data set memory using the address for the compressed data set corresponding to the first data block in the compressed data set memory;

determining the compression scheme corresponding to the compressed data set for the first data block from the encoded compression descriptor for the first data block; and

decompressing the compressed data set for the first data block to produce data values for the first data block, wherein the decompressing is performed based on the compression scheme corresponding to the compressed data set for the first data block.

24. The data processing system of claim 23, wherein data values for each of the plurality of data blocks are texture map data values.

25. The data processing system of claim 24, wherein each of the data blocks corresponds to a M-by-N texel block.

26. The data processing system of claim 25, wherein the memory includes operating instructions such that the processor performs an additional function of texturing pixels using the texture map data values for the first data block.

27. The data processing system of claim 23, wherein each encoded compression descriptor includes K bits, wherein the K bits encode 2^K potential compression scheme/size combinations.

28. The data processing system of claim 23, wherein the memory includes operating instructions such that the processing module performs the function of compressing each data block of the plurality of data blocks such that at least a portion of the data blocks in the plurality of data blocks are compressed using a variable length compression scheme.

29. A data processing system, comprising:

a first memory;

a second memory;

a processing module operably coupled to the first memory and the second memory; and

an instruction memory operably coupled to the processing module, wherein the instruction memory stores operating instructions that, when executed by the processing module, cause the processing module to perform functions that include;

selecting a compression scheme for each data block of a plurality of data blocks, wherein each compression scheme selected is selected from a set of predetermined compression schemes;

compressing each data block using the compression scheme selected for the data block to produce a compressed data set corresponding to each data block, wherein compressing compresses data within each data block to a size corresponding to the compression scheme selected for the data block, wherein each compression scheme supports at least one size;

storing the compressed data sets corresponding to each of the plurality of data blocks in the first memory, wherein the compressed data sets are grouped into a plurality of groups, wherein compressed data sets in each of the plurality of groups are stored in a predetermined order within the first memory; and

storing a descriptor data set for each group of the plurality of groups in the second memory, wherein each descriptor data set includes a base address for the group in the first memory and an encoded compression descriptor for each compressed data set included in the group, wherein each encoded compression descriptor encodes the compression scheme and size for each compressed data set, wherein ordering of the encoded compression descriptors in the descriptor data set corresponds to ordering of the compressed data sets for the group as stored in the first memory.

30. The data processing system of claim 29, wherein the instruction memory includes instructions such that the functions performed by the processing module include decompressing the compressed data for a selected data block of the plurality of data blocks, wherein decompressing includes:

fetching a descriptor data set from the second memory that includes an encoded compression descriptor for a compressed data block that corresponds to the selected block;

determining an address of the compressed data set corresponding to the selected data block in the first memory based on the base address of the descriptor data set fetched from the second memory and sizes of other compressed data blocks as indicated by additional encoded compression descriptors included in the descriptor data set fetched;

fetching the compressed data set corresponding to the selected data block from the first memory using the address;

determining the compression scheme used for compressing the compressed data set corresponding to the selected data block based on the encoded compression descriptor corresponding to the compressed data set in the descriptor data set fetched from the second memory; and

decompressing the compressed data set fetched from the first memory based on the compression scheme used for compressing the compressed data set to produce data of the selected data block.