Patent US5864859A successfully refreshed from Google Patents.
US5864859A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method of compression and decompression using store addressing
Assignee: International Business Machines Corp
•
Filing: 1996-02-20
•
Granted: 1999-01-26
•
Expires: 2016-02-20
Abstract
Abstract Variable-length data, comprising compressed pages, is stored in a memory so that access to any sub-page or line within a page can be started given a single address corresponding to the location of a fixed-length block within the memory.
Inventors
- 👤 Peter Anthony Franaszek
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 13:42
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F2212/00; G06F2212/40; G06F2212/401; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99937; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
145 words
A method for storing and accessing data in a main memory of a computer system comprising the steps of: a. dividing each page into a plurality of lines, and compressing the lines to form compressed pages comprised of the lines which are placed in random-access storage; b. providing a directory to the compressed pages, wherein a location for a directory entry for each page is in a translation table between page virtual addresses and directory entries, and the beginning of descriptors of where the nth line within each page is stored is located at a fixed offset from the location of the directory entry; c. providing a set of descriptors for each line which indicates the storage locations for the compressed line; d. storing in a set of fixed-size blocks the compressed portions of each line which are not placed in the directory descriptor space.
Claim 2
Independent Claim
145 words
A method for storing and accessing data in a main memory of a computer system comprising the steps of: a. dividing each page into a plurality of lines, and compressing the lines to form compressed pages comprised of the lines which are placed in random-access storage; b. providing a directory to the compressed pages, wherein a location for a directory entry for each page is in a translation table between page virtual addresses and directory entries, and the beginning of descriptors of where the nth line within each page is stored is located at a fixed offset from the location of the directory entry; c. providing a set of descriptors for each line which indicates the storage locations for the compressed line; d. storing in a set of fixed-size blocks the compressed portions of each line which are not placed in the directory descriptor space.
Claim 3
Dependent Claim
36 words
A method as in claim 1, wherein each directory entry points to the first block in a chain of blocks holding the compressed line, and each succeeding block has a pointer to the next succeeding block.
Claim 4
Dependent Claim
19 words
A method as in claim 1, wherein the directory entry for each page is contained in an anchor block.
Claim 5
Dependent Claim
29 words
The method as in claim 1, comprising the further steps of pipelining the decompression of the beginning portion of a line with fetching continuing portions of the same line.
Claim 6
Dependent Claim
21 words
The method as in claim 1, wherein each compressed line is stored in a set of fixed size blocks of storage.
Claim 7
Dependent Claim
24 words
The method as in claim 1, further including inserting into the directory descriptor space for a compressed line, the beginning of the compressed line.
Claim 8
Independent Claim
124 words
A method for accessing data in a system wherein compressed pages of data are stored in random access memory comprising the steps of: a. dividing each page of data into a plurality of lines of data; b. compressing each line of data individually; c. storing the beginning of each line of data in a page at a fixed storage position within an anchor block of memory which includes a beginning portion of each of the lines of data and a pointer to any continuing portion of a line of a data, wherein a single address and an offset suffices to access the beginning of any line; d. storing continuing portions of the lines of data in at least one additional continuation block of memory.
Claim 9
Independent Claim
124 words
A method for accessing data in a system wherein compressed pages of data are stored in random access memory comprising the steps of: a. dividing each page of data into a plurality of lines of data; b. compressing each line of data individually; c. storing the beginning of each line of data in a page at a fixed storage position within an anchor block of memory which includes a beginning portion of each of the lines of data and a pointer to any continuing portion of a line of a data, wherein a single address and an offset suffices to access the beginning of any line; d. storing continuing portions of the lines of data in at least one additional continuation block of memory.
Claim 10
Dependent Claim
44 words
A method as claimed in claim 7, wherein the anchor block of memory is divided into an equal number of lines of data, and the fixed storage positions of the beginning of lines of data are equally spaced in the anchor block of memory.
Claim 11
Dependent Claim
27 words
A method as claimed in claim 7, wherein the memory size of the anchor block of memory is smaller than the number of bytes in each page.
Claim 12
Dependent Claim
47 words
A method as claimed in claim 7, wherein the at least one additional continuation block of memory includes a continuing portion of at least one of the lines of data and a termination code indicating the termination of the at least one of the lines of data.
Claim 13
Dependent Claim
31 words
A method as claimed in claim 7, further comprising pipelining the decompression and placement of the beginning portions of lines of data with fetching the continuing portions of lines of data.
Claim 14
Dependent Claim
34 words
A method as claimed in claim 7, wherein access to any line in a stored page of data is accessed by providing a single physical address for that page to a translation look-aside buffer.
Claim 15
Dependent Claim
60 words
A method as claimed in claim 7, wherein each continuation block of memory includes either the completion of a compressed line of data along with a termination code indicating that no further continuation blocks need to be retrieved for the line, or a continuation portion of the line along with a pointer to a further continuation portion of the line.
References Cited (Backward Citations)
US4638429A
Cited
US4660130A
Cited
US5627995A
Cited
US5623092A
Cited
US5481701A
Cited
US5410677A
Cited
US5455577A
Cited
US5644791A
Cited
US5551020A
Cited
US5546575A
Cited
US5592342A
Cited
US5623701A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-25 | 2002-07-27 | 2003-01-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-25 | 2006-07-27 | 2007-01-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-25 | 2010-07-27 | 2011-01-26 | $7700.00 | Window Closed / Lapsed |