Granted Patent B2

US 7,215,259 · App. 11/179,080 · Granted May 8, 2007

Abstract

Claims (144)

1. A method of encoding digital data, the method comprising:

searching for a match between a current one or more segments of data and a corresponding one or more past segments of data;

coding the current segment of data as a literal if no match exists;

coding the match as a reference if the match exists and the match length greater than 1; and

if the match exists and a match length is 1:

determining if a match offset is less than a threshold;

coding the match as a single-character reference, if the match offset is less than the threshold; and

coding the match as a literal, if the match offset is greater than the threshold.

2. The method of claim 1 , wherein the searching includes:

reading a new segment of data;

determining if the new segment of data previously occurred;

if the new segment of data previously occurred:

determine a match exists;

continuing to read a new segment of data until the end of a match is reached;

determining a match offset and a match length; and if the new segment of data did not previously occur, determining no match exists.

3. The method of claim 1 , wherein the coding the current segment of data as the literal includes:

writing a flag indicating literal data encoding; and

writing the current segment of data.

4. The method of claim 1 , wherein the coding the match as the reference includes:

writing a flag indicating non-literal data;

setting an encoding type flag indicated non-literal data encoding;

writing the encoding type flag;

writing an indication of the match offset; and

writing an indication of the match length.

5. The method of claim 4 , wherein the indication of the match offset includes the match offset.

6. The method of claim 4 , wherein the indication of the match offset includes a variable length encoding of the match offset.

7. The method of claim 6 , wherein the variable length value includes a group indicator.

8. The method of claim 4 , wherein the indication of the match length includes the match length.

9. The method of claim 4 , wherein the indication of the match length includes a variable length encoding of the match length.

10. The method of claim 9 , wherein the variable length encoding includes a group indicator.

11. The method of claim 1 , wherein the coding the match as the single-character reference includes:

writing a flag indicating non-literal data;

setting an encoding type flag indicating single-character reference encoding;

writing the encoding type flag; and

writing the match offset.

12. The method of claim 1 , wherein the coding the match as the literal includes:

writing a flag indicating literal data encoding; and

writing the current segment of data.

13. A method of encoding a stream of data segments, the method comprising:

loading a new segment of data from the stream of data segments;

determining if the new segment of data matches a past segment of data;

if the new segment of data does not match the past segment of data:

encoding the new segment of data as literal data; and

if at least a portion of the new segment of data matches at least a portion of the past data:

determining a length of matching data, wherein the matching data corresponds to the at least a portion of the new segment of data that matches,

if the length is a single character:

determining if an offset of the matching data from the past segment of data is within a threshold,

if the offset of the matching data is within the threshold:

encoding the new segment of data as a single character match, and if the offset of the matching data is not within the threshold:

encoding the new segment as literal data;

if the length of the matching data is greater than a single character:

encoding the new segment of data as a multi character match.

14. The method of claim 13 , wherein the determining if the new segment of data matches the past segment of data includes:

loading a value from a locate memory corresponding to the new segment of data;

determining the new segment of data matches past data if the value is not zero; and

determining the new segment of data does not match past data if the value is zero.

15. The method of claim 13 , further comprising updating a locate memory.

16. The method of claim 13 , further comprising updating a match register.

17. The method of claim 16 , wherein the updating a match register includes:

loading a value from an a locate memory corresponding to the new segment of data, wherein the locate memory identifies locations of repeated occurrences of past data segments;

determining a result of a logical AND operation between bits from the loaded value and bits shifted by one from the match registers;

updating the match register with the logical AND results if any of the bits of the logical AND result is not zero;

updating the match register with the loaded value from the locate memory if all of the bits of the result are zero.

18. The method of claim 13 , further comprising determining the match offset from a match register.

19. The method of claim 18 , wherein the determining the match offset from the match register includes counting a number of bit positions from a current position to a first bit set to 1.

20. An encoder comprising:

encoding logic, wherein the encoding logic includes a table of match offsets to single-characters and a table of match offsets of long length; and

string matching logic coupled to the encoding logic, wherein the string matching logic includes a locate memory operable to identify locations of repeated occurrences of the past data segments and a match register coupled to the locate memory.

21. The encoder of claim 20 , wherein the encoding logic further includes a table of match lengths.

22. The encoder of claim 20 , wherein string matching logic further includes a history buffer operable to hold past data segments.

23. A parallel encoder for encoding a source of data, the parallel encoder comprising:

a plurality of serial encoders, wherein each serial encoder includes:

encoding logic having an input and an output, wherein the encoding logic includes a table of match offsets to single-characters, and a table of match offsets of long length; and

string matching logic coupled to the encoding logic, wherein the string matching logic includes a history buffer operable to hold past data segments, a locate memory operable to identify locations of repeated occurrences of the past data segments, and a match register coupled to the locate memory;

a head control including:

an input coupled to the source of data; and

a plurality of outputs, each output coupled to the input of a corresponding one of the plurality of serial encoders; and

a tail control including:

a plurality of inputs, each input coupled to the output of a corresponding one of the plurality of serial encoders; and

an output providing a coded data stream.

24. A parallel decoder for decoding a source of encoded data, the parallel decoder comprising:

a plurality of serial decoders, wherein each serial decoder includes:

decoding logic, wherein the decoding logic includes a table of match offsets to single-characters and a table of match offsets of long length; and

a history buffer operable to hold decoded data segments;

a head control including:

an input coupled to the source of encoded data; and

a plurality of outputs, each output coupled to the input of a corresponding one of the plurality of serial decoders; and

a tail control including:

a plurality of inputs, each input coupled to the output of a corresponding one of the plurality of serial decoders; and

an output providing a decoded data stream.

25. A method of decoding coded data, the method comprising:

determining a beginning of coded data;

reading a flag indicating whether the coded data contains literal data or an encoded representation;

if the flag indicates literal data, extracting a literal length of data thereby forming a segment of decoded data;

if the flag indicates the encoded representation:

reading an encoding-type flag indicating whether the encoded representation includes a single-character match offset or a long-length match offset;

if the encoding-type flag indicates the single-character match offset:

determining the single-character match offset; and

determining a value from a history buffer corresponding to the single-character match offset, thereby forming the segment of decoded data; and

if the encoding-type flag indicates the long-length match offset:

determining the long-length match offset;

determining a match length; and

reading one or more values from the history buffer corresponding to the long-length match offset and the match length, thereby forming a corresponding one or more segments of decoded data.

26. The method of claim 25 , wherein determining the long-length match offset includes:

determining a length of the long-length match offset;

reading a number of bits corresponding to the determined length; and

setting the long-length match offset based on the read bits.

27. The method of claim 25 , wherein determining the long-length match offset includes:

reading a group indicator;

reading a number of bits corresponding to the group indicator; and

setting the long-length match offset based on the read bits.

28. The method of claim 25 , wherein determining the match length includes:

determining a length of the match length;

reading a number of bits corresponding to the determined length; and

setting the match length based on the read bits.

29. The method of claim 25 , wherein determining the match length includes:

reading a group indicator;

reading a number of bits corresponding to the group indicator; and

setting the match length based on the read bits.

30. A magnetic tape drive comprising:

an encoder including:

encoding logic, wherein the encoding logic includes a table of match offsets to single-characters and a table of match offsets of long length; and

string matching logic coupled to the encoding logic, wherein the string matching logic includes a locate memory operable to identify locations of repeated occurrences of the past data segments and a match register coupled to the locate memory; and

a decoder including:

decoding logic, wherein the decoding logic includes a table of match offsets to single-characters and a table of match offsets of long length; and

a history buffer operable to hold decoded data segments.

31. A method of encoding a stream of data, the method comprising:

selecting from three formats a format to encode a segment of the stream of data, wherein:

a first format represents the segment as a literal including the segment;

a second format represents the segment as a reference including an offset to a single-character match to a previous segment, wherein the previous segment is determined to be within a threshold offset; and

a third format represents the segment as a reference including an indication of a match offset and an indication of a match length.

32. The method of claim 31 , wherein:

the first format further including a cleared bit immediately preceding the segment;

the second format further including a set bit and a cleared bit pair immediately preceding the offset to the single-character match; and

the third format further including a pair of set bits immediately preceding the indication of the match offset and the indication of the match length.

33. The method of claim 31 , further comprising:

forming bit pattern in the selected format; and

writing the bit pattern.

34. A method of encoding a stream of data, the method comprising:

selecting from four formats a format to encode a segment of the stream of data, wherein:

a first format represents the segment as a literal including the segment;

a second format represents the segment as a reference including an offset to a single-character match to a previous segment, wherein the previous segment is determined to be within a threshold offset;

a third format represents the segment as a reference including an offset to a double-character match to a previous segment; and

a fourth format represents the segment as a reference including an indication of a match offset and an indication of a match length.

Assignments (12)