Storing compressed data in non-contiguous memory

• US 5,574,953 A
• Filed: 08/19/1994
• Issued: 11/12/1996
• Est. Priority Date: 08/19/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Pennington, Roger L., Rust, Robert
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/293,229
• Time in Patent Office: 816 Days
• Field of Search: 395/600, 395/877, 395/888, 395/497.01, 395/497.02, 341/106, 382/56, 380/42, 364/715.02
• US Class Current: 710/68
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

A data compression and decompression method for storing compressed data in non-contiguous memory. As the data is compressed and stored in memory, any non-contiguous segments are properly marked. Such marking requires that the last location contains a pointer to the next memory location used. Just prior to the pointer a special "LINK" code is stored. Thus, when the compressor completes its job, the non-contiguous memory is logically linked together. To decompress the compressed data, a code of the compressed data is retrieved from the non-contiguous memory. If the code is a link code, then an address pointer to the next location in memory where the next compressed data is stored is retrieved from memory. If, in the alternative, the code in not a link code then the code is decompressed.

Claims

1. A data decompression method for decompressing a compressed data into an original data where said compressed data is stored in a non-contiguous memory, said method comprising the steps of:

retrieving a code of said compressed data from said non-contiguous memory;

determining if said code is a link code; and

if said code is said link code, then

reading a pointer where said pointer points to a next area of said non-contiguous, said pointer being stored in memory after said link code.

2. In a computer, method for decompressing a plurality of compressed data in to an plurality of original data where said compressed data is stored in a first memory and said original data is stored in a second memory, said method being performed by said computer, said method comprising the steps of:

said computer reading one of said plurality of compressed data from said first memory;

if said one of said plurality of compressed data is a link code then

retrieving an address pointer from said first memory where said address pointer being stored in memory after link code, said address pointer points to a new location in said first memory where a next one of said plurality of compressed data is stored; and

if said one of said plurality of compressed data is other than said link code then said computer decompresses said one of said plurality of compressed data into a subset of said plurality of original data and stores said subset of said plurality of original data in said second memory.

3. A data compression method for compressing an uncompressed data into a compressed data where said compressed data is stored in a memory, said method comprising the steps of:

retrieving a sub-set of said uncompressed data;

compressing said sub-set of said uncompressed data into a sub-set of said compressed data; and

requesting a next memory segment from said memory, if a present memory segment and said next memory segment are contiguous, storing said sub-set of compressed data in said next memory segment, in the alternative where said next memory segment and said present memory segment are non-contiguous then placing in said present memory segment a link code followed by a pointer pointing to where in said memory said next memory segment is located then saving said compressed data in said next memory.