Byte aligned data compression

• US 5,363,098 A
• Filed: 10/25/1993
• Issued: 11/08/1994
• Est. Priority Date: 10/25/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Antoshenkov, Gennady
• Primary Examiner(s): Logan, Sharon D.
• Application Number:
  US08/142,640
• Time in Patent Office: 379 Days
• Field of Search: 341/63, 341/59, 341/95, 341/50, 358/261.1
• US Class Current: 341/95
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.