High-throughput compression of data

1. A method, in a data processing system, for high-throughput compression of data, the method comprising:

responsive to receiving an indication of a match of a current 4-byte sequence from an incoming data stream to stored hash values in a set of hash tables:

setting an active match variable (active_match) equal to one (1);

setting an active position variable (active_pos) equal to a match position (match_pos) of an increment variable (j) (match_pos[j]);

setting an active length variable (active_len) equal to 4 minus the increment variable (j); and

setting an active distance variable (active_dist) equal to a position variable (pos) plus the increment variable (j) minus the active position variable (active_pos);

responsive to receiving a subsequent 4-byte sequence from the incoming data stream and determining that the active match variable (active_match) is set to one (1), comparing the subsequent 4-byte sequence to data in a copy of the incoming data stream in memory at the active position (active_pos) with a predefined length offset;

setting a constraint variable (k) to a number of bytes for which the match is to be extended; and

responsive to the constraint variable (k) being below a predetermined number, outputting a length (L), distance (D) pair indicating a match to a previous pattern in the incoming data stream, wherein the length (L) of the matching pattern that is set to the active length (active_len) plus the constraint variable (k) and the distance (D) is set to the active distance (active_dist).

2. The method of claim 1 , further comprising:

incrementing the position variable (pos) by 4 before proceeding to the next 4-byte sequence.

3. The method of claim 1 , further comprising:

responsive to the constraint variable (k) being equal to the predetermined number, setting the active length variable (active_len) to the active_len+4;

incrementing the position variable (pos) by 4 before proceeding to the next 4-byte sequence;

comparing the next 4-byte sequence to data in the copy of the incoming data stream in memory at the active position (active_pos) with a predefined length offset; and

setting the constraint variable (k) to a number of bytes for which the match is to be extended.

4. The method of claim 1 , further comprising:

responsive to a failure to receive the indication of the match of the current 4-byte sequence from the incoming data stream to the stored hash values in the set of hash tables, outputting the incoming data at the increment variable (j) (data_in[j]) as a literal.

5. The method of claim 1 , wherein the matching of the current 4-byte sequence from the incoming data stream to the stored hash values in the set of hash tables comprises:

computing a key value (Key[j]) for each of the current 4-byte data patterns at byte offsets j=0, 1, 2, and 3 using a hash function;

in order to determine whether the current 4-byte data patterns at byte offsets j=0, 1, 2, and 3 have been observed earlier in the incoming data stream, in parallel:

searching a first hash table in the set of hash tables for a first current 4-byte pattern at a byte offset j=0;

searching a second hash table in the set of hash tables for a second current 4-byte pattern at a byte offset j=1;

searching a third hash table in the set of hash tables for a third 4-byte pattern at a byte offset j=2; and

searching a fourth hash table in the set of hash tables for a fourth current 4-byte pattern at a byte offset j=3; and

responsive to detecting the match for byte offset j, setting a corresponding match flag match[j] to be equal to 1 and setting a corresponding entry in match position vector (match_pos[j]) equal to a hash table position (ht_pos) where the match was identified.

6. The method of claim 5 , wherein, responsive to identifying more than one match for the byte offset j, selecting the match with the largest hash table position (ht_pos).

7. The method of claim 1 , wherein the set of hash tables is updated by the method comprising:

computing a hash (Key[j]) for the current 4-byte data pattern at each byte offset j=0, 1, 2, and 3; and

in parallel:

storing the hash value at a byte offset j=0 in a first hash table;

storing the hash value at a byte offset j=1 in a second hash table;

storing the hash value at a byte offset j=2 in a third hash table; and

storing the hash value at a byte offset j=3 in a fourth hash table.

8. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

responsive to receiving an indication of a match of a current 4-byte sequence from an incoming data stream to stored hash values in a set of hash tables:

set an active match variable (active_match) equal to one (1);

set an active position variable (active_pos) equal to a match position (match_pos) of an increment variable (j) (match_pos[j]);

set an active length variable (active_len) equal to 4 minus the increment variable (j); and

set an active distance variable (active_dist) equal to a position variable (pos) plus the increment variable (j) minus the active position variable (active_pos);

responsive to receiving a subsequent 4-byte sequence from the incoming data stream and determining that the active match variable (active_match) is set to one (1), compare the subsequent 4-byte sequence to data in a copy of the incoming data stream in memory at the active position (active_pos) with a predefined length offset;

set a constraint variable (k) to a number of bytes for which the match is to be extended; and

responsive to the constraint variable (k) being below a predetermined number, output a length (L), distance (D) pair indicating a match to a previous pattern in the incoming data stream, wherein the length (L) of the matching pattern that is set to the active length (active_len) plus the constraint variable (k) and the distance (D) is set to the active distance (active_dist).

9. The computer program product of claim 8 , wherein the computer readable program further causes the computing device to:

increment the position variable (pos) by 4 before proceeding to the next 4-byte sequence.

10. The computer program product of claim 8 , wherein the computer readable program further causes the computing device to:

responsive to the constraint variable (k) being equal to the predetermined number, set the active length variable (active_len) to the active_len+4;

increment the position variable (pos) by 4 before proceeding to the next 4-byte sequence;

compare the next 4-byte sequence to data in the copy of the incoming data stream in memory at the active position (active_pos) with a predefined length offset; and

set the constraint variable (k) to a number of bytes for which the match is to be extended.

11. The computer program product of claim 8 , wherein the computer readable program further causes the computing device to:

responsive to a failure to receive the indication of the match of the current 4-byte sequence from the incoming data stream to the stored hash values in the set of hash tables, output the incoming data at the increment variable (j) (data_in[j]) as a literal.

12. The computer program product of claim 8 , wherein the matching of the current 4-byte sequence from the incoming data stream to the stored hash values in the set of hash tables comprises the computer readable program further causing the computing device to:

compute a key value (Key[j]) for each of the current 4-byte data patterns at byte offsets j=0, 1, 2, and 3 using a hash function;

in order to determine whether the current 4-byte data patterns at byte offsets j=0, 1, 2, and 3 have been observed earlier in the incoming data stream, in parallel:

search a first hash table in the set of hash tables for a first current 4-byte pattern at a byte offset j=0;

search a second hash table in the set of hash tables for a second current 4-byte pattern at a byte offset j=1;

search a third hash table in the set of hash tables for a third current 4-byte pattern at a byte offset j=2; and

search a fourth hash table in the set of hash tables hr a fourth current 4-byte pattern at a byte offset j=3; and

responsive to detecting the match for byte offset j, set a corresponding match flag match[j] to be equal to 1 and setting a corresponding entry in match position vector (match_pos[j]) equal to a hash table position (ht_pos) where the match was identified.

13. The computer program product of claim 12 , wherein, responsive to identifying more than one match for the byte offset j, the computer readable program further causes the computing device to:

select the match with the largest hash table position (ht_pos).

14. The computer program product of claim 8 , wherein the set of hash tables is updated by the computer program product further causing the computing device to:

compute a hash (Key[j]) for the current 4-byte data pattern at each byte offset j=0, 1, 2, and 3; and

in parallel:

store the hash value at a byte offset j=0 in a first hash table;

store the hash value at a byte offset j=1 in a second hash table;

store the hash value at a byte offset j=2 in a third hash table; and

store the hash value at a byte offset j=3 in a fourth hash table.

15. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to:

responsive to receiving an indication of a match of a current 4-byte sequence from an incoming data stream to stored hash values in a set of hash tables:

set an active match variable (active_match) equal to one (1);

set an active position variable (active_pos) equal to a match position (match_pos) of an increment variable (j) (match_pos[j]);

set an active length variable (active_len) equal to 4 minus the increment variable (j); and

set an active distance variable (active_dist) equal to a position variable (pos) plus the increment variable (j) minus the active position variable (active_pos);

responsive to receiving a subsequent 4-byte sequence from the incoming data stream and determining that the active match variable (active_match) is set to one (1), compare the subsequent 4-byte sequence to data in a copy of the incoming data stream in memory at the active position (active_pos) with a predefined length offset;

set a constraint variable (k) to a number of bytes for which the match is to be extended; and

responsive to the constraint variable (k) being below a predetermined number, output a length (L), distance (D) pair indicating a match to a previous pattern in the incoming data stream, wherein the length (L) of the matching pattern that is set to the active length (active_len) plus the constraint variable (k) and the distance (D) is set to the active distance (active_dist).

16. The apparatus of claim 15 , wherein the instructions further cause the processor to:

increment the position variable (pos) by 4 before proceeding to the next 4-byte sequence.

17. The apparatus of claim 15 , wherein the instructions further cause the processor to:

responsive to the constraint variable (k) being equal to the predetermined number, set the active length variable (active_len) to the active_len+4;

increment the position variable (pos) by 4 before proceeding to the next 4-byte sequence;

compare the next 4-byte sequence to data_in the copy of the incoming data stream in memory at the active position (active_pos) with a predefined length offset; and

set the constraint variable (k) to a number of bytes for which the match is to be extended.

18. The apparatus of claim 15 , wherein the instructions further cause the processor to:

responsive to a failure to receive the indication of the match of the current 4-byte sequence from the incoming data stream to the stored hash values in the set of hash tables, output the incoming data at the increment variable (j) (data_in[j]) as a literal.

19. The apparatus of claim 15 , wherein the matching of the current 4-byte sequence from the incoming data stream to the stored hash values in the set of hash tables comprises the instructions further causing the processor to:

compute a key value (Key[j]) for each of the current 4-byte data patterns at byte offsets j=0, 1, 2, and 3 using a hash function;

in order to determine whether the current 4-byte data patterns at byte offsets j=0, 1, 2, and 3 have been observed earlier in the incoming data stream, in parallel:

search a first hash table in the set of hash tables for a first current 4-byte pattern at a byte offset j=0;

search a second hash table in the set of hash tables for a second current 4-byte pattern at a byte offset j=1;

search a third hash table in the set of hash tables for a third current 4-byte pattern at a byte offset j=2; and

search a fourth hash table in the set of hash tables for a fourth current 4-byte pattern at a byte offset j=3; and

responsive to detecting the match for byte offset j, set a corresponding match flag match[j] to be equal to 1 and setting a corresponding entry in match position vector (match_pos[j]) equal to a hash table position (ht_pos) where the match was identified.

20. The apparatus of claim 19 , wherein, responsive to identifying more than one match for the byte offset j, the instructions further cause the processor to:

select the match with the largest hash table position (ht_pos).