Method and apparatus for storing compressed data
First Claim
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 Assignments
0 Petitions
Accused Products
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.
136 Citations
30 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12)
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28)
-
-
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. - View Dependent Claims (30)
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.
-
Specification