Granted Patent B1

US 10,651,871 · App. 16/507,739 · Granted May 12, 2020

Inventor: Muhammad Dawood (High Wycombe, GB)

Assignee: Citrix Systems, Inc.

H03M7/42H03M7/3084

Abstract

Claims (80)

1. A method for stream-based compression comprising:

receiving, by an encoder of a first device, an input stream of bytes including a first byte preceded by one or more second bytes;

determining, by the encoder, to identify a prefix code for the first byte;

selecting, by the encoder from a plurality of prefix code tables maintained by the encoder, a prefix code table using the one or more second bytes, each prefix code table of the plurality of prefix code tables including respective prefix codes for respective bytes, each prefix code comprising a number of bits based on a frequency of occurrence of the one or more second bytes preceding the respective byte;

identifying, by the encoder, from the selected prefix code table, the prefix code of the first byte;

generating, by the encoder, an output stream of bytes by replacing the first byte in the input stream with the prefix code of the first byte; and

transmitting the output stream from the encoder of the first device to a decoder of a second device, the output stream having a fewer number of bits than the input stream.

2. The method of claim 1 , wherein transmitting the output stream comprises transmitting the output stream to the decoder of the second device, the decoder configured to decode the output stream using a plurality of prefix code tables corresponding to the plurality of prefix code tables maintained by the encoder.

3. The method of claim 1 , wherein determining to identify the prefix code for the first byte comprises:

generating, by the encoder, from the input stream, a hash value based on the first byte and a number of preceding bytes;

performing, by the encoder using the hash value, a lookup in a buffer comprising a plurality of hashes; and

determining that the buffer does not include a matching string.

4. The method of claim 1 , further comprising:

identifying, by the encoder, a third byte in the input stream;

generating, by the encoder, from the input stream, a hash value based on the third byte and a number of preceding bytes;

performing, by the encoder using the hash value, a lookup in a buffer comprising a plurality of hash values to identify a matching hash value; and

generating, by the encoder responsive to identifying the matching hash value in the buffer, an identifier indicating a presence of the matching hash value within the buffer.

5. The method of claim 4 , wherein generating the output stream further comprises generating, by the encoder, the output stream of bytes by replacing the third byte and the number of preceding bytes in the input stream with the identifier and a length.

6. The method of claim 5 , wherein a length is limited to a length of a maximum number of bits of the respective prefix codes for the plurality of prefix code tables.

7. The method of claim 5 , further comprising:

determining, by the encoder, the length of bytes corresponding to the matching hash value; and

identifying, by the encoder, in a length prefix code table corresponding to the identifier, a prefix code corresponding to the length of bytes; wherein

generating the output stream further comprises generating, by the encoder, the output stream of bytes by replacing the third byte and the number of preceding bytes in the input stream with the identifier and the prefix code corresponding to the length of bytes.

8. The method of claim 1 , wherein the input stream comprises a stream of input bytes, and wherein the plurality of prefix code tables comprises a respective prefix code table for each possible input byte.

9. The method of claim 1 , further comprising:

maintaining, by the encoder, each of the plurality of prefix code tables indexed by one or more respective bytes;

wherein selecting the prefix code table comprises:

performing, by the encoder, a look-up of the plurality of prefix code tables using the one or more second bytes to identify the prefix code table.

10. The method of claim 1 , wherein the plurality of prefix code tables is a first plurality of prefix code tables and the input stream is a first input stream, the plurality of prefix code tables being generated based on the first input stream, further comprising:

receiving, by the encoder, a second input stream comprising a plurality of second bytes;

for at least some of the second bytes of the second input stream,

identifying, by the encoder, a respective prefix code table using at least one preceding byte of the second input stream which precedes the second byte;

identifying, by the encoder, from the respective prefix code table, a prefix code corresponding to the second byte; and

updating, by the encoder, a count of the prefix code corresponding to the second byte; and

generating, by the encoder, a second plurality of prefix code tables based on the count of each respective prefix code in each respective prefix code table in the first plurality of prefix code tables.

11. The method of claim 10 , further comprising:

maintaining, by the decoder, the first plurality of prefix code tables;

receiving, by the decoder from the encoder, a second output stream corresponding to the second input stream, the second output string comprising a plurality of prefix codes;

for each prefix code of the plurality of prefix codes,

identifying, by the decoder, a corresponding input byte within a prefix code table of the first plurality of prefix code tables corresponding to a preceding byte of the respective prefix code; and

updating, by the decoder, a count of the corresponding input byte within the prefix code table; and

generating, by the encoder, a second plurality of prefix code tables based on the count of each respective input byte in each respective prefix code table in the first plurality of prefix code tables.

12. The method of claim 1 , further comprising:

identifying a third byte in the input stream;

generating, by the encoder, from the input stream, a string comprising the third byte and a plurality of preceding bytes;

computing, by the encoder, a hash value for the string; and

performing, by the encoder, a lookup of the hash value in a hash table comprising a plurality of hash values corresponding to respective strings.

13. The method of claim 1 , wherein the string is a first string comprising the third byte and a first plurality of preceding byes, the hash is a first hash, and the hash table is a first hash table comprising a plurality of first hash values, and wherein the method further comprises:

generating, by the encoder responsive to not identifying a matching first hash value of the first hash table, a second string comprising the third byte and a second plurality of preceding bytes less than the first plurality of preceding bytes;

computing, by the encoder, a second hash value for the second string;

performing, by the encoder, a lookup of the second hash value in a second hash table comprising a plurality of second hash values corresponding to respective strings; and

identifying, by the encoder, a matching second hash value of the second hash table.

14. The method of claim 12 , wherein generating the output stream further comprises generating, by the encoder, the output stream of bytes by replacing the third byte and the second plurality of preceding bytes with the identifier and a length.

15. The method of claim 1 , further comprising:

receiving, by the decoder from the encoder, the output stream, the output stream comprising at least one prefix code;

identifying, by the decoder, the prefix code in the output stream;

identifying, by the decoder, at least one preceding byte which precedes the prefix code;

selecting, by the decoder, from a plurality of prefix code tables maintained by the decoder, a prefix code table corresponding to the at least one preceding byte;

identifying, by the decoder, an input byte corresponding to the prefix code by performing a lookup of the prefix code in the selected prefix code table; and

reproducing, by the decoder, the input stream by replacing the prefix code in the output stream with the input byte.

16. A system for stream-based compression comprising:

a first device comprising:

an encoder configured to:

receive an input stream of bytes including a first byte preceded by one or more second bytes;

determine to identify a prefix code for the first byte;

select, from a plurality of prefix code tables maintained by the encoder, a prefix code table using the one or more second bytes, each prefix code table of the plurality of prefix code tables including respective prefix codes for respective bytes, each prefix code comprising a number of bits based on a frequency of occurrence of the one or more second bytes preceding the respective byte;

identify, from the selected prefix code table, the prefix code of the first byte; and

generate an output stream of bytes by replacing the first byte in the input stream with the prefix code of the first byte;

wherein the first device is configured to transmit the output stream from the encoder of the first device to a decoder of a second device, the output stream having a fewer number of bits than the input stream.

17. The system of claim 16 , wherein the first device is configured to transmit the output stream to the decoder of the second device, the decoder configured to decode the output stream using a plurality of prefix code tables corresponding to the plurality of prefix code tables maintained by the encoder.

18. The system of claim 16 , wherein the encoder is further configured to:

generate, from the input stream, a hash based on the first byte and a number of preceding bytes;

perform a lookup in a buffer using the hash, the buffer comprising a plurality of hashes; and

determine that the buffer does not include a matching string.

19. The system of claim 16 , wherein the encoder is further configured to:

identify a third byte in the input stream;

generate, from the input stream, a hash based on the third byte and a number of preceding bytes;

perform, by the encoder, a lookup in a buffer using the string to identify a matching hash, the buffer comprising a plurality of hashes; and

generate, responsive to identifying the matching hash in the buffer, an identifier indicating a presence of the matching hash within the buffer.

20. The system of claim 19 , wherein generating the output stream further comprises generating, by the encoder, the output stream of bytes by replacing the third byte and the number of preceding bytes in the input stream with the identifier and a length.

Assignments (9)

Cited By (1)

US 12,695,942