Data compression apparatus with shift register search means

A method for converting an input data character stream into a variable length encoded data stream in a data compression system, said data compression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said input data stream, said method comprising the steps of:

• performing a search in said shift means for a longest matching data string which matches said input data stream, said step of performing said search including the steps of broadcasting each of said input data character of said input data stream to each entry of said shift means, comparing each input data character simultaneously with each entry of said shift means, and inputting each input data character into said shift means,
• operative when said longest matching data string is found within said shift means, encoding said matching data string by assigning a tag indicating said matching data string and a string substitution code including a variable length indicator of said length of said matching data string and a pointer indicating said entry of said shift means having said matching data string,
• operative when said matching input data string is not found within said shift means, encoding a first character of said input data stream by assigning a "raw" data tag and said first character of said input data stream,
• whereby said input data stream is converted into a variable length encoded data stream.

An apparatus for converting an input data character stream into a variable length encoded data stream in a data compression system, said data compression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said input data stream, said apparatus comprising:

• means for performing a search in said shift means for a longest matching data string which matches said input data stream, said means for performing said search including means for broadcasting each said data character of said input data stream to each said entry of said shift means, and means for comparing each said input data stream simultaneously with each entry of said shift means,
• means for encoding said matching data string by assigning a tag indicating said matching data string and a string substitution code including a variable length indicator of the length of said matching data string and a pointer indicating the entry of said shift of said matching data string,
• means for encoding a first character of said input data stream by assigning a "raw" data tag and said first character of said input data stream,
• whereby said input data stream is converted into a variable length encoded data stream.

A method for comparing an input data character with a data stream, said data stream including a plurality of data characters, said method comprising the steps of:

• storing said data characters of said data stream in a shift means, said shift means having a plurality of entries and each entry of said shift means for storing one of said data characters of said data stream;
• broadcasting said input data character to each entry of said shift means;
• transferring each said stored data character of each entry of said shift means to another entry of said shift means;
• for each entry of said shift means, comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character;
• and
• separately accumulating the results of said comparison for each entry of said shift means.

A method for converting a variable length encoded data stream into an output data character stream in a data decompression system, said data decompression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said output data character stream, said method comprising the steps of:

• parsing said variable length encoded input data stream into separate portions, each said separate portion starting with a tag,
• evaluating said tag of each said separate portion for determining whether said tag is a raw data tag or a tag indicating an encoded matching data string,
• operative when said tag is said raw data tag, parsing a raw data byte from said separate portion, outputting said raw data byte, placing said raw data byte in said shift means, and
• operative when said tag is said tag indicating an encoded matching data string, parsing a variable length indicator of the length of said matching data string and an offset indicating an entry within said shift means containing the first character of said matching data string, outputting said matching data string at said entry within said shift means for said length, and placing said matching data string in said shift means.

An apparatus for converting a variable length encoded data stream into an output data character stream in a data decompression system, said data decompression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said output data character stream, said apparatus comprising:

• means for parsing said variable length encoded input data stream into separate portions, each said separate portion starting with a tag,
• means for evaluating said tag of each said separate rate portion for determining whether said tag is a raw data tag or a tag indicating an encoded matching data string,
• means for parsing a raw data byte from said separate portion, means for outputting said raw data byte, means for placing said raw data byte in said shift means, and
• means for parsing a variable length indicator of the length of said matching data string and an offset indicating an entry within said shift means containing the first character of said matching data string, means for outputting said matching data string at said entry within said shift means for said length, and means for placing said matching data string in said shift means.

An apparatus for comparing an input data character with a data stream, said data stream including a plurality of data characters, said apparatus comprising:

• means for storing said data characters of said data stream, said storage means having a plurality of entries and each entry of said storage means for storing one of said data characters of said data stream;
• means for broadcasting said input data character to each entry of said storage means;
• for each entry of said storage means, means for comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character;
• and
• means for separately accumulating the results of said comparison for each entry of said storage means.

A method for comparing an input data character with a data stream, said data stream including a plurality of data characters, said method comprising the steps of:

• storing said data characters of said data stream in a storage means, said storage means having a plurality of entries and each entry of said storage means for storing one of said data characters of said data stream;
• broadcasting said input data character to each entry of said storage means;
• for each entry of said storage means, comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character;
• and
• separately accumulating the results of said comparison for each entry of said storage means.