High-Throughput Compression of Data

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

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