Browse Prior Art Database

Data Compression With Fixed Count Pass Mode Expansion Limiting

IP.com Disclosure Number: IPCOM000115288D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 88K

Publishing Venue

IBM

Related People

Buerkle, D: AUTHOR [+3]

Abstract

Disclosed is a method and apparatus for performing data compression. Suppression of repeated characters by Run Length Coding is employed, yet a rare, constant-valued "Escape" code signals the beginning of each compression run. Additionally, a Pass mode run is defined to limit expansion, and while pass runs have a variable run-length count, simple and fast implementations can exploit small, FIXED counts with no compression performance degradation. There is also a feature to allow compression on a per-packet basis, and for related reasons the data is treated strictly on even 2-byte, or word, boundaries.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Data Compression With Fixed Count Pass Mode Expansion Limiting

      Disclosed is a method and apparatus for performing data
compression.  Suppression of repeated characters by Run Length Coding
is employed, yet a rare, constant-valued "Escape" code signals the
beginning of each compression run.  Additionally, a Pass mode run is
defined to limit expansion, and while pass runs have a variable
run-length count, simple and fast implementations can exploit small,
FIXED counts with no compression performance degradation.  There is
also a feature to allow compression on a per-packet basis, and for
related reasons the data is treated strictly on even 2-byte, or word,
boundaries.

      For packet data, compression is done by scanning the part of
the packet following the command word and compressing repeated
'0000'x or 'FFFF'x word runs, where these runs can start only on word
boundaries.  When an 'EA'x byte is encountered in the most
significant byte of a word (i.e., the word equals 'EAxx'x) a Pass run
is produced.  Each packet's compressed data consists of a series of
sections.  There are two types of sections: incompressible data words
and Run Length Code sections.  An incompressible section is simply a
group of contiguous words that doesn't contain '0000'x or 'FFFF'x
runs, or 'EAxx'x words.  There are three types of Run Length Code
sections representing (1) an 'EAxx'x Pass Run, (2) a '0000'x run, and
(3) a 'FFFF'x run.

      The Run Length Code is a word (2 bytes = 16 bits) consisting of
the Escape byte concatenated with a control byte.  The Escape byte is
the constant EA'x always, and is a rare value, being an invalid and
unused EBCDIC code and S/370/390 opcode, and an uncommon ASCII code.
The control byte is comprised of a 1- or 2-bit opcode, followed by a
7- or 6-bit count, respectively.  The three possible control byte
types, and their meanings, are:
  1.  Pass run code:  opcode = '0'b, count = NN (7 bit count).
       Meaning: 'EAxx'x was encountered during compression.  This
code
       was inserted, with the NN words of data passed as-is following
       it, and recognition of 'EAxx', '0000', and 'FFFF'x being
       suppressed for these NN words.
  2.  '0000'x repeat run code:  opcode = '10'b, count = NN (6 bit
       count).  Meaning:  2 or more repeated '0000'x words were
       encountered during compression.  The NN+2 repeate...