Storage of compressed data on random access storage devices

• US 5,237,460 A
• Filed: 09/04/1992
• Issued: 08/17/1993
• Est. Priority Date: 12/14/1990
• Status: Expired due to Term

• Current Assignee: Digital Data Funding LLC (Intellectual Ventures LLC)
• Original Assignee: CeRam, Incorporated
• Inventors: Miller, William D., Harrington, Gary L., Fullerton, Lawrence M.
• Primary Examiner(s): Psitos, Aristotelis
• Assistant Examiner(s): Kim, Won Tae C.
• Application Number:
  US07/940,769
• Time in Patent Office: 347 Days
• Field of Search: 360/8, 360/40, 360/48, 360/9.1, 341/51, 341/106, 358/906, 358/133, 358/135, 358/261.2, 358/261.4, 358/426
• US Class Current: 360/8
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11B 20/00007 Time or data compression or expansion audio compression based on psychoacoustics G10L19/00; data processing for reproducing audio data at different playback speeds G10L21/04; video compression H04N19/00; data compression per se H03M7/30
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A random-access type storage device such as a hard disk or semiconductor memory is formatted to provide multiple partitions of varying block size. The data to be stored is in blocks of fixed size, and these blocks are compressed if the compressed size fits in the block size of a small-block partition in the storage device. If a data block is not compressible to the small block size, it is stored uncompressed in another of the partitions. The memory device also contains a table storing the locations of the blocks in the partitions, so upon recall the block is retrieved from location, decompressed (if it had been compressed), and sent to the CPU. For example, there may be two partitions, one using the block size of the original (uncompressed) data, and the other having a block size corresponding to the typical compressed size of the blocks of data (perhaps one-half the size of the original data blocks). The relative number of blocks in each partition (e.g., the physical storage capacity of each partition) is set at the average ratio of compressible blocks to uncompressible blocks for the compression algorithm used. For example, an algorithm may compress 90% of the blocks to 50% of their original size, so a ratio of the number of blocks in the compressed partition to the number of blocks in the uncompressed partition is selected as 90:10.

Claims

1. A method of processing blocks of data received from an input and storing said blocks of data in a memory device so that data in any of said blocks can be retrieved in original form, the blocks of data being of fixed size, comprising the steps of:

a) partitioning the memory device to provide a first memory space containing a large number of memory locations of a first size, said first size being smaller than said fixed size, each of said memory locations of a first size being capable of storing a compressed version of one of said blocks of data, and to provide a second memory space containing a large number of memory locations of said fixed size, each of said memory locations of a fixed size being capable of storing an uncompressed version of one of said blocks of data;

b) receiving from said input and compressing each of said blocks of data to produce a compressed block, and detecting whether or not each said compressed block is as small as said first size to produce a size indicator;

c) storing each of said blocks of data, so that data in any of said compressed blocks of data can be expanded to original form, either in said first memory space as a compressed block or in said second memory space as an uncompressed block in response to said size indicator produced by said step of detecting.

2. A method according to claim 1 wherein said step of storing includes writing said blocks of data to a magnetic disk.

3. A method according to claim 2 wherein said step of partitioning includes writing to said disk to define said first memory space as a first partition of said disk and said second memory space as a second partition of said disk.

4. A method according to claim 3 wherein said first partition is much larger than said second partition.

5. A method according to claim 4 wherein said fixed size is about twice as large as said first size.

6. A method according to claim 1 including the steps of receiving a separate address with each of said blocks and storing said address in said memory device associated with a location of said block in said first or second memory spaces.

7. A method according to claim 6 including the step of recalling said data blocks by

d) receiving a request for one of said blocks using said address for said block;

e) finding said address for said block in said stored addresses and determining the location of said block;

f) detecting whether or not said block was stored in said first memory space; and

g) decompressing said block if stored in said first memory space.

8. Apparatus for processing blocks of data received from an input and storing said blocks of data in a memory device, so that any data in said blocks of data can be retrieved in original form, the blocks of data being of fixed size, comprising:

a) a first memory space in said memory device containing a large number of memory locations of a first size, said first size being smaller than said fixed size, each of said memory locations of a first size storing a compressed version of one of said blocks of data;

b) a second memory space in said memory device containing a large number of memory locations of said fixed size, each of said memory locations of said fixed size storing an uncompressed version of one of said blocks of data;

c) means for receiving from said input and compressing each of said blocks of data to produce a compressed block, and means for detecting whether or not each said compressed block is as small as said first size and producing a size indicator in response to said detecting;

d) and means for storing each of said blocks of data either in said first memory space as a compressed block whereby data of a compressed block can be expanded to original form, or in said second memory space as an uncompressed version, in response to said size indicator produced by said means for detecting.

9. Apparatus according to claim 8 wherein said first and second memory spaces are defined in a magnetic disk.

10. Apparatus according to claim 9 wherein said first memory space is larger than said second memory space.

11. Apparatus according to claim 10 wherein said fixed size is about twice as large as said first size.

12. Apparatus according to claim 8 including means for receiving a separate address with each of said blocks and storing said address in said memory device associated with a location of said block in said first or second memory spaces.

13. Apparatus according to claim 12 including means for recalling said data blocks, including:

e) means for receiving a request for one of said blocks including said address for said block;

f) means for finding said address for said block in said stored addresses and determining the location of said block;

g) means for detecting whether or not said block was stored in said first memory space; and

h) means for decompressing said block if stored in said first memory space.

14. A digital system comprising:

a) a source of data blocks of fixed length;

b) storage means having first storage locations of at least one selected size less than said fixed length and second storage locations of said fixed length;

c) a data compression unit receiving said data blocks from said source and compressing all of the data in each of said data blocks to produce a compressed block, so that data in any of said data blocks can be expanded to its original form;

d) means for detecting whether each of said data blocks is compressed to said selected size by said data compression unit and producing a size indicator in response to said detecting;

e) and means responsive to said size indicator for storing a compressed block in one of said first storage locations if said compressed block is as small as one of said at least one selected size, or for storing one of said data blocks in one of said second locations if said compressed block for said one of said data blocks is larger than any one of said at least one selected size.

15. A system according to claim 14 wherein said first and second storage locations are defined in a magnetic disk.

16. A system according to claim 15 wherein said first storage locations occupy a first memory space which is large than a second memory space occupied by said second storage locations.

17. A system according to claim 16 wherein said fixed size is about twice as large as said at least one selected size.

18. A system according to claim 14 including means for receiving a separate address with each of said blocks and storing said address in said storage means associated with one of said first or second storage locations.

19. A system according to claim 18 including means for recalling said data blocks, including:

e) means for receiving a request for one of said blocks including said address for said block;

f) means for finding said address for said block in said stored addresses and determining the location of said block;

g) means for detecting whether or not said block was stored in one of said first storage locations; and

h) means for decompressing said block if stored in one of said first storage locations.

20. A system according to claim 14 wherein said storage means includes third storage locations of a third size less than said selected size;

and said means for storing stores a compressed block in said third storage location if said compressed block is as small as said third size.

21. A system according to claim 14 wherein said first storage locations are defined in semiconductor memory and said second storage locations are defined in a magnetic disk.

22. Apparatus receiving blocks of data of fixed size and storing said blocks of data in a memory so that said blocks of data can be retrieved in original form, comprising:

a) a first memory space in said memory containing memory locations of a first size, each of said memory locations of a first size storing a compressed version of one of said blocks of data;

b) a second memory space in said memory containing memory locations of said fixed size, each of said memory locations of said fixed size storing an uncompressed version of one of said blocks of data;

c) means for compressing each of said blocks of data and storing in said memory each of said blocks of data either in one of said first memory spaces as a compressed version which may be expanded to original form or in one said second memory spaces as a uncompressed version;

d) a third memory space containing a table of the locations of blocks of data in said first and second memory spaces;

e) means for receiving a request for one of said blocks including an identification of said block;

f) addressing means for accessing said third memory space in response to said request for finding said identification in said table of locations in said third memory space and determining the location of said one of said blocks in said first or second memory space from said table of locations and retrieving said one of said blocks;

g) output means including decompressing means and including means for detecting from said addressing means if said one of said blocks was stored in said first memory space, and, if so, decompressing said one of said blocks by said decompressing means to expand said block to its original form.

23. Apparatus according to claim 22 wherein said first and second memory spaces are defined in a magnetic disk.

24. Apparatus according to claim 22 wherein said first memory space is constructed of semiconductor memory devices and said second memory space is defined in a magnetic disk device.

25. Apparatus according to claim 22 wherein said first and second memory spaces are defined in semiconductor memory devices of a non-volatile type.