US5363098A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Byte aligned data compression
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-10-25
•
Granted: 1994-11-08
•
Expires: 2013-10-25
Abstract
Abstract In a system for compressing, decompressing, and logically manipulating arbitrary bit-maps, the bit-map is aligned along byte boundaries. Each aligned byte is classified as a gap byte if all of the bits of the byte store the same logical value, otherwise the byte is classified as a non-gap byte. Adjacent bytes of the same class are grouped. Groups of gap bytes are encoded into an atomic sequence of bytes as a count of the number of bits included in the grouped gap bytes. Map bytes are duplicated in the atomic sequence and also associated with a count thereof.
Inventors
- 👤 Gennady Antoshenkov
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 07:31
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
161 words
In a computer system, a method for compressing data comprising the steps of: storing the data into a first set of bytes of a memory of the computer system, each byte of said set of bytes including an identical number of bits for storing logical values; classifying a byte of said first set of bytes as a gap byte if each bit of said byte stores the identical logical value, otherwise, classifying said byte as a map byte; grouping adjacent identically classified bytes; storing, in a second set of ordered bytes of said memory, for each group of gap bytes, a first bit sequence representative of the number of bits in said group of gap bytes; storing, in said second ordered set of bytes, for each group of map bytes, a second bit sequence representative of the number of bits in said group of map bytes, said second set of bytes having an order corresponding to said first set of bytes.
Claim 2
Dependent Claim
161 words
In a computer system, a method for compressing data comprising the steps of: storing the data into a first set of bytes of a memory of the computer system, each byte of said set of bytes including an identical number of bits for storing logical values; classifying a byte of said first set of bytes as a gap byte if each bit of said byte stores the identical logical value, otherwise, classifying said byte as a map byte; grouping adjacent identically classified bytes; storing, in a second set of ordered bytes of said memory, for each group of gap bytes, a first bit sequence representative of the number of bits in said group of gap bytes; storing, in said second ordered set of bytes, for each group of map bytes, a second bit sequence representative of the number of bits in said group of map bytes, said second set of bytes having an order corresponding to said first set of bytes.
Claim 3
Dependent Claim
62 words
The method as in claim 1 further including the steps of sensing if said bits of a particular group of gap bytes stores all zeros or all ones, storing a flag associated with a particular first bit sequence corresponding to said particular group of gap bytes, said flag indicative of the sense of said bits of said particular group of gap bytes.
Claim 4
Dependent Claim
89 words
The method as in claim 2 further including the steps of sensing if a first byte of a group of map bytes has exactly one bit different than an immediately preceding group of gap bytes, and in response to said sensing, storing said first byte as a bit off-set in said second set of bytes, said bit off-set associated with a corresponding first bit sequence representative of said preceding group of gap bytes, said bit off-set indicative of the position of said one different bit in said first byte.
Claim 5
Dependent Claim
44 words
The method as in claim 3 further including the steps of organizing said set second set of bytes as a plurality of atoms, each of said atoms including a control byte for storing said first bit sequence, said second bit sequence, and said flag.
Claim 6
Dependent Claim
40 words
The method as in claim 4 further including the step of storing said first bit sequence in a byte following said control byte if the number of bits in said group of gap bytes is larger than a predetermined number.
Claim 7
Independent Claim
181 words
An apparatus for compressing data including: a memory having a first set of bytes for storing the data, each byte including a plurality of bits for storing logical values representative of the data, said logical values being either a one or a zero; means for classifying a byte of said first set of bytes as a gap byte if all of said plurality of bits of said byte store the identical logical value, otherwise classifying said byte as a map byte; means for counting the number of bits in adjacent bytes having the identical classification; means for storing a first bit sequence representative of the counted number of bits in a second set of bytes of said memory for each group of adjacent gap bytes; means for storing a second bit sequence representative of the counted number of bits in said second set of bytes for each group of adjacent map bytes; means for storing said group of adjacent map bytes in said second set of bytes, the order of said first and second set of bytes corresponding to each other.
Claim 8
Independent Claim
181 words
An apparatus for compressing data including: a memory having a first set of bytes for storing the data, each byte including a plurality of bits for storing logical values representative of the data, said logical values being either a one or a zero; means for classifying a byte of said first set of bytes as a gap byte if all of said plurality of bits of said byte store the identical logical value, otherwise classifying said byte as a map byte; means for counting the number of bits in adjacent bytes having the identical classification; means for storing a first bit sequence representative of the counted number of bits in a second set of bytes of said memory for each group of adjacent gap bytes; means for storing a second bit sequence representative of the counted number of bits in said second set of bytes for each group of adjacent map bytes; means for storing said group of adjacent map bytes in said second set of bytes, the order of said first and second set of bytes corresponding to each other.
Claim 9
Dependent Claim
53 words
The apparatus as in claim 6 further including means for sensing if a particular group of gap bytes stores all zeros or all ones, and means for storing a flag associated with a particular first bit sequence, said flag indicative of the sense of the bits of said particular group of gap bytes.
Claim 10
Dependent Claim
90 words
The apparatus as in claim 7 further including means for sensing if a first byte of a group of map bytes has exactly one bit different than an immediately preceding group of gap bytes, and means, response to said sensing means, for storing said first byte as a bit off-set in said second set of bytes, said bit off-set associated with a corresponding first bit sequence representative of said preceding group of gap bytes, said bit off-set indicative of the position of said one different byte in said first byte.
Claim 11
Independent Claim
217 words
A method for compressing data comprising the steps of: storing the data into a source set of bytes of a storage device, each source byte having a plurality of bits, each of said bits to store a logical zero or a logical one; determining if all of said plurality of bits of a particular byte of said source set of bytes store the identical logical value; in response to a true determination, classifying said particular byte as a gap byte, otherwise classifying said particular byte as a map byte; grouping adjacent identically classified bytes of said source set of bytes; counting the number of said bits in each group of adjacent identically classified bytes; storing in a destination set of bytes of said storage device, for each group of classified gap bytes, a gap bit sequence representative of the number of said counted bits of said groups of gap bytes; storing in said destination set of bytes of said storage device, for each group of classified map bytes, a map bit sequence representative of the number of said counted bits of said groups of map bytes; storing in said destination set of bytes of said storage device, each group of classified map bytes, the order of said source and destination sets of bytes corresponding to each other.
Claim 12
Independent Claim
217 words
A method for compressing data comprising the steps of: storing the data into a source set of bytes of a storage device, each source byte having a plurality of bits, each of said bits to store a logical zero or a logical one; determining if all of said plurality of bits of a particular byte of said source set of bytes store the identical logical value; in response to a true determination, classifying said particular byte as a gap byte, otherwise classifying said particular byte as a map byte; grouping adjacent identically classified bytes of said source set of bytes; counting the number of said bits in each group of adjacent identically classified bytes; storing in a destination set of bytes of said storage device, for each group of classified gap bytes, a gap bit sequence representative of the number of said counted bits of said groups of gap bytes; storing in said destination set of bytes of said storage device, for each group of classified map bytes, a map bit sequence representative of the number of said counted bits of said groups of map bytes; storing in said destination set of bytes of said storage device, each group of classified map bytes, the order of said source and destination sets of bytes corresponding to each other.
References Cited (Backward Citations)
US3656178A
Cited
US4495639A
Cited
US4606002A
Cited
US4610027A
Cited
US4782325A
Cited
US4630030A
Cited
US4684923A
Cited
US4626829A
Cited
US4841299A
Cited
US4868570A
Cited
US5006849A
Cited
US4988998A
Cited
US5049881A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-11-07 | 1998-05-09 | 1998-11-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-11-07 | 2002-05-09 | 2002-11-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-11-07 | 2006-05-09 | 2006-11-08 | $7700.00 | Window Closed / Lapsed |