Data compression and decompression using memory spaces of more than one size

• US 5,627,995 A
• Filed: 06/01/1994
• Issued: 05/06/1997
• Est. Priority Date: 12/14/1990
• Status: Expired due to Term

• Current Assignee: Digital Data Funding LLC (Intellectual Ventures LLC)
• Original Assignee: Alfred P. Gnadinger
• Inventors: Miller, William D., Bellman, Chris M., Harrington, Gary L., Weldon, E. J. Jr., Fullerton, Larry M.
• Primary Examiner(s): Kim, Matthew M.
• Application Number:
  US08/251,465
• Time in Patent Office: 1,070 Days
• Field of Search: 395/497.01, 395/497.02, 395/477.03, 395/888, 395/182.04, 395/185.07, 395/414, 395/415, 395/464, 395/421.03, 364/200 MS File, 364/900 MS File, 371/40.1
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• 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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• 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 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A method for storing data in a memory, including compressing fixed-sized pages of data, and storing the compressed pages into available smaller memory spaces on a medium if the compressed page will fit into such space, or storing the compressed pages onto available larger memory spaces on the medium, if the compressed page will not fit into the smaller space.

Claims

1. A memory device for storing pages of data, the pages of data being of fixed size, said memory device comprising:

a) a first set of a plurality of memory spaces of said fixed size, said memory spaces of said first set storing an uncompressed version of one of said pages of data;

b) a second set of a plurality of memory spaces smaller than said fixed size of said memory spaces, said memory spaces of said second set storing a compressed form of one of said pages of data;

c) means for compressing each of said pages of data to produce a plurality of compressed pages, and means for detecting if a compressed page is smaller than a memory space of said second set; and

d) means for selectively storing a compressed page of data in a memory space of said second set as said compressed version if the compressed page is smaller than a memory space of said second set, in response to said means for detecting; and

including means for generating at least one error-correcting code for each one of each of said compressed pages, and wherein said means for selectively storing a compressed page of data in a memory space of said second set stores said error-correcting codes with said compressed pages; and

including means for transferring said compressed pages as parallel 9-bit symbols to said means for generating an error-correcting code.

2. A memory device for storing pages of data, the pages of data being of a fixed size of bytes, said memory device comprising:

a) a first set of a plurality of memory spaces of said fixed size, said memory spaces of said first set storing an uncompressed version of one of said pages of data;

b) a second set of a plurality of memory spaces smaller than said fixed size of said memory spaces, said memory spaces of said second set storing a compressed form of one of said pages of data;

c) means for compressing each of said pages of data to produce a plurality of compressed pages, and means for detecting if a compressed page is smaller than a memory space of said second set; and

d) means for selectively storing a compressed page of data in a memory space of said second set as said compressed version if the compressed page is smaller than a memory space of said second set, in response to said means for detecting; and

wherein said means for compression includes a lookahead buffer storing a first number of bytes of one of the pages of data, and includes a window buffer containing a second number of bytes of the one of the pages of data, said second number being larger than said first number, and means for comparing the first number of bytes in said lookahead buffer to all of the second number of the bytes in said window buffer and generating match symbols if multiple-byte matches are found in said comparing.

3. The memory device according to claim 2 wherein said lookahead buffer and said window buffer are of bit-parallel format, and said means for compressing has an output which includes an added bit that indicates whether or not said output of the means for compressing represents a compressed or non-compressed symbol.