US5502439A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for compression of binary data
Assignee: United States Department of Energy
•
Filing: 1994-05-16
•
Granted: 1996-03-26
•
Expires: 2014-05-16
Abstract
Abstract The disclosed method for compression of a series of data bytes, based on LZSS-based compression methods, provides faster decompression of the stored data. The method involves the creation of a flag bit buffer in a random access memory device for temporary storage of flag bits generated during normal LZSS-based compression. The flag bit buffer stores the flag bits separately from their corresponding pointers and uncompressed data bytes until all input data has been read. Then, the flag bits are appended to the compressed output stream of data. Decompression can be performed much faster because bit manipulation is only required when reading the flag bits and not when reading uncompressed data bytes and pointers. Uncompressed data is read using byte length instructions and pointers are read using word instructions, thus reducing the time required for decompression.
Inventors
- 👤 Gary J. Berlin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 13:23
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
164 words
A method for compressing an input stream of data being transferred from an input buffer to an output buffer, said input data stream composed of a series of data bytes including at least one repeated data byte that repeats a previous data byte in said series of data bytes, said method comprising the steps of: reading each data byte in said series of data bytes; determining whether said each data byte is a repeated data byte; replacing said repeated data byte by a pointer that indicates the location of said previous data byte, said series of data bytes then containing pointers and remaining data bytes; establishing a flag bit for said repeated byte; storing temporarily said flag bit in a flag bit buffer; writing said remaining data bytes and said pointers to said output buffer as an output series of data bytes; and writing said flag bit from said temporary flag bit buffer to said output buffer at the end of said output series.
Claim 2
Independent Claim
164 words
A method for compressing an input stream of data being transferred from an input buffer to an output buffer, said input data stream composed of a series of data bytes including at least one repeated data byte that repeats a previous data byte in said series of data bytes, said method comprising the steps of: reading each data byte in said series of data bytes; determining whether said each data byte is a repeated data byte; replacing said repeated data byte by a pointer that indicates the location of said previous data byte, said series of data bytes then containing pointers and remaining data bytes; establishing a flag bit for said repeated byte; storing temporarily said flag bit in a flag bit buffer; writing said remaining data bytes and said pointers to said output buffer as an output series of data bytes; and writing said flag bit from said temporary flag bit buffer to said output buffer at the end of said output series.
Claim 3
Dependent Claim
41 words
The method as recited in claim 1, wherein said series of data bytes has a plurality of repeated data bytes and wherein said method further comprises the step of allocating a portion of said output buffer for all established flag bits.
Claim 4
Dependent Claim
18 words
The method as recited in claim 2, wherein said pointers are read and written using integer move instructions.
Claim 5
Dependent Claim
20 words
The method as recited in claim 1, wherein said remaining data bytes are read and written using byte move instructions.
Claim 6
Dependent Claim
18 words
The method as recited in claim 1, wherein said pointers are read and written using integer move instructions.
Claim 7
Dependent Claim
20 words
The method as recited in claim 1, wherein said temporary flag bit buffer is in a random access memory device.
Claim 8
Independent Claim
215 words
A method for managing an input data stream received from an input buffer, said method for use with a storage buffer and an output buffer, said input data stream composed of a series of data bytes including at least one string of repeated data bytes, said at least one string of repeated data bytes repeating a previous data byte string in said series of data bytes, and said method comprising the steps of: reading each data byte in said series of data bytes; determining whether said each data byte is part of a repeated data byte string; replacing said repeated data byte string by a pointer that indicates the location and run length of said previous data byte string, said series of data bytes then containing pointers and remaining data bytes; establishing a first flag bit for said repeated data byte string and a second flag bit for each remaining data byte; storing temporarily in a flag bit buffer said first and said second flag bits in the order in which they were established; writing said remaining data bytes and said pointers to said storage buffer as an output series of data bytes; and writing said flag bit from said temporary flag bit buffer to said storage buffer at the end of said output series.
Claim 9
Independent Claim
215 words
A method for managing an input data stream received from an input buffer, said method for use with a storage buffer and an output buffer, said input data stream composed of a series of data bytes including at least one string of repeated data bytes, said at least one string of repeated data bytes repeating a previous data byte string in said series of data bytes, and said method comprising the steps of: reading each data byte in said series of data bytes; determining whether said each data byte is part of a repeated data byte string; replacing said repeated data byte string by a pointer that indicates the location and run length of said previous data byte string, said series of data bytes then containing pointers and remaining data bytes; establishing a first flag bit for said repeated data byte string and a second flag bit for each remaining data byte; storing temporarily in a flag bit buffer said first and said second flag bits in the order in which they were established; writing said remaining data bytes and said pointers to said storage buffer as an output series of data bytes; and writing said flag bit from said temporary flag bit buffer to said storage buffer at the end of said output series.
Claim 10
Dependent Claim
19 words
The method as recited in claim 7, further comprising the step of reserving a portion of said output buffer.
Claim 11
Dependent Claim
36 words
The method as recited in claim 7, wherein said pointer indicates said location of said previous data byte string by the number of data bytes between said previous data string and said repeating data byte string.
Claim 12
Dependent Claim
82 words
The method as recited in claim 7, further comprising the steps of: reading said output series with said flag bits; identifying each pointer in said output series using said flag bits; locating each previous data byte string from each pointer; replacing each pointer with said previous data byte string to form, in sequence with said data bytes, a restored series of data bytes equivalent to said series of data bytes; and writing said restored series of data bytes to said output buffer.
Claim 13
Dependent Claim
19 words
The method as recited in claim 10, wherein said data bytes are read and written using byte move instructions.
Claim 14
Dependent Claim
18 words
The method as recited in claim 10, wherein said pointers are read and written using word move instructions.
Claim 15
Dependent Claim
40 words
The method as recited in claim 10, wherein said flag bits are read and written using bit instructions, said pointers are read and written using word move instructions and said data bytes are read and written using byte move instructions.
Claim 16
Dependent Claim
27 words
The method as recited in claim 7, wherein said first flag bit is a set flag bit and said second flag bit is a clear flag bit.
Claim 17
Dependent Claim
23 words
The method as recited in claim 7, further comprising the step of reserving a portion of said storage buffer for said flag bits.
Claim 18
Dependent Claim
20 words
The method as recited in claim 7, wherein said temporary flag bit buffer is in a random access memory device.
Claim 19
Dependent Claim
25 words
The method as recited in claim 7, wherein said flag bit buffer is no more than approximately one eighth the size of said input buffer.
Claim 20
Independent Claim
284 words
A method for managing an input data stream received from an input buffer, said method for use with a storage buffer and an output buffer, said input data stream composed of a series of data bytes including at least one string of repeated data bytes, said at least one string of repeated data bytes repeating a previous data byte string in said series of data bytes, and said method comprising the steps of: reading each data byte in said series of data bytes; determining whether said each data byte is part of a repeated data byte string; replacing said repeated data byte string by a pointer that indicates the location and run length of said previous data byte string, said series of data bytes then containing pointers and remaining data bytes; establishing a first flag bit for said repeated data byte string and a second flag bit for each remaining data byte; storing temporarily in a flag bit buffer said first and said second flag bits in the order in which they were established; writing said remaining data bytes and said pointers to said storage buffer as an output series of data bytes; writing said flag bit from said temporary flag bit buffer to said storage buffer at the end of said output series; reading said output series with said flag bits; identifying each pointer in said output series using said flag bits; locating each previous data byte string from each pointer; replacing each pointer with said previous data byte string to form, in sequence with said data bytes, a restored series of data bytes equivalent to said series of data bytes; and writing said restored series of data bytes to said output buffer.
Claim 21
Independent Claim
284 words
A method for managing an input data stream received from an input buffer, said method for use with a storage buffer and an output buffer, said input data stream composed of a series of data bytes including at least one string of repeated data bytes, said at least one string of repeated data bytes repeating a previous data byte string in said series of data bytes, and said method comprising the steps of: reading each data byte in said series of data bytes; determining whether said each data byte is part of a repeated data byte string; replacing said repeated data byte string by a pointer that indicates the location and run length of said previous data byte string, said series of data bytes then containing pointers and remaining data bytes; establishing a first flag bit for said repeated data byte string and a second flag bit for each remaining data byte; storing temporarily in a flag bit buffer said first and said second flag bits in the order in which they were established; writing said remaining data bytes and said pointers to said storage buffer as an output series of data bytes; writing said flag bit from said temporary flag bit buffer to said storage buffer at the end of said output series; reading said output series with said flag bits; identifying each pointer in said output series using said flag bits; locating each previous data byte string from each pointer; replacing each pointer with said previous data byte string to form, in sequence with said data bytes, a restored series of data bytes equivalent to said series of data bytes; and writing said restored series of data bytes to said output buffer.
Claim 22
Dependent Claim
19 words
The method as recited in claim 18, wherein said data bytes are read and written using byte move instructions.
Claim 23
Dependent Claim
18 words
The method as recited in claim 18, wherein said pointers are read and written using word move instructions.
References Cited (Backward Citations)
US4286256A
Cited
US4464650A
Cited
US4491934A
Cited
US4622545A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4586027A
Cited
US4633490A
Cited
US4682150A
Cited
US4905297A
Cited
US4872009A
Cited
US4943869A
Cited
US4941193A
Cited
US4876541A
Cited
US4906991A
Cited
US5153591A
Cited
US5001477A
Cited
US5003307A
Cited
US5146221A
Cited
US5126739A
Cited
US5065447A
Cited
US5177622A
Cited
US5250949A
Cited
US4988998A
Cited
US5109433A
Cited
US4955066A
Cited
US5179711A
Cited
US5010345A
Cited
US5298895A
Cited
US5254990A
Cited
US5206742A
Cited
US5237675A
Cited
US5049881A
Cited
US5051745A
Cited
US5210536A
Cited
US5185820A
Cited
US5151697A
Cited
US5212565A
Cited
US5166684A
Cited
US5245427A
Cited
US5150430A
Cited
US5212742A
Cited
US5271071A
Cited
US5179378A
Cited
US5140321A
Cited
US5155484A
Cited
US5245441A
Cited
US5229768A
Cited
US5239298A
Cited
US5363098A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-26 | 1999-09-25 | 2000-03-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-26 | 2003-09-25 | 2004-03-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-26 | 2007-09-25 | 2008-03-26 | $7700.00 | Window Closed / Lapsed |