RDP BITMAP HASH ACCELERATION USING SIMD INSTRUCTIONS

• US 20100215280A1
• Filed: 02/26/2009
• Published: 08/26/2010
• Est. Priority Date: 02/26/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abdo, Nadim Y., Albu, Voicu Anton
• Granted Patent: US 9,071,843 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 3/1462 with means for detecting differences between the image stored in the host and the images displayed on the remote displays
• CPC Class Codes: G06Q 2220/10 Usage protection of distributed data files
• CPC Class Codes: G09G 2340/02 Handling of images in compressed format, e.g. JPEG, MPEG
• CPC Class Codes: G09G 2360/121 using a cache memory
• CPC Class Codes: G09G 2360/122 Tiling
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence

Abstract

Systems, methods and computer readable media are disclosed for a vectorized tile differencing algorithm for a remote desktop protocol (RDP). A server executes a CBC-variant vectorized hash algorithm that is used to produce a big key that identifies the tile, and keeps track of these big keys. Where a serial version of the algorithm operates on a single portion of the image at once—such as 32 bits—the vectorized algorithm operates on a plurality of these portions simultaneously. Where the server identifies that a tile has already been sent to a client via RDP because it has a second big key that matches the big key, it sends the big key to the client—which caches received tiles—and the client uses it to access the proper tile for display. Where the server identifies that a tile has not already been sent to the client, it sends the client the tile.

Claims

1. A method for classifying an image on a parallel processing system having a bit width, the method involving a first random number and a second random number, the first random number differing from the second random number, and a checksum, a datum, a first key and a second key, comprising:

grouping the image into at least one group, each group comprising a number of bits of the image equal to the bit width;

for each group, performing a hash comprising;

setting the checksum equal to the checksum plus the group;

setting the datum to equal the sum of the group and the datum multiplied by the first random number and summed with the second random number;

setting the first key to equal the first key modified by the datum; and

setting the second key to equal the second key modified by the datum; and

storing a big key comprising the first key and the second key in a big key store.

2. The method of claim 1, further comprising:

sending the image to a client computer across a communications network.

3. The method of claim 2, wherein sending the image to a client computer across a communications network occurs after:

determining that the big key does not match any other big key in the big key store;

4. The method of claim 3, further comprising:

sending the client the big key.

5. The method of claim 4, further comprising:

sending the client computer an indication to use the big key to retrieve a second image from a client hash, and to process the second image as if the client had received it instead of the indication.

6. The method of claim 2, further comprising:

encoding the image before sending the image to the client computer.

7. The method of claim 1, further comprising:

setting each of a checksum, a datum, a first key and a second key equal to zero before performing operations on each group.

8. The method of claim 1, wherein the first key is modified by the datum by performing an exclusive-or operation on the first key and the datum, and wherein the second key is modified by the datum by performing an exclusive-or operation on the second key and the datum.

9. The method of claim 1, wherein the image has a start and an end, and the operations performed for each group are first performed for the group nearest to the start for which the operations performed for each group have not already been performed.

10. The method of claim 1, further comprising:

when the image size divided by the bit width has a remainder number of bits other than zero, hashing the remainder number of bits with a serial cipher block chaining (CBC) algorithm to produce a post-first key and a post-second key, determining the first key based on the post-first key, and determining the second key based on the post-second key.

11. The method of claim 5, wherein the image has an end, the reminder number of bits and no part of the image is nearer the end than the remainder number of bits.

12. The method of claim 1, wherein the hash comprises a cipher block chaining (CBC) variant.

13. The method of claim 1, wherein the image comprises a screen scrape.

14. The method of claim 1, wherein the image comprises a tile in a Remote Desktop Protocol (RDP).

15. A system for classifying an image on a parallel processing system having a bit width, the method involving a first random number and a second random number, the first random number differing from the second random number, and a checksum, a datum, a first key and a second key, comprising:

a processor;

circuitry for grouping the image into at least one group, each group comprising a number of bits of the image equal to the bit width;

circuitry for, for each group, performing a hash comprising;

calculating a running reference to the image, the running reference comprising the checksum, the first key, the second key, and the datum, and calculated based on the running reference, the group, the datum, the first random number and the second random number;

circuitry for storing a big key comprising the first key and the second key in a big key store.

16. The system of claim 15, further comprising:

circuitry for encoding the image; and

circuitry for sending the encoded image to a client across a communications network and according to a remote desktop protocol (RDP).

17. The system of claim 15, wherein a pixel of the image comprises 32 bits, the bit width comprises 128 bits.

18. The system of claim 17, further comprising:

circuitry for determining that the image is unaligned before grouping the image, and hashing a portion of the image that occurs before the first alignment boundary with a serial algorithm to produce a pre-first key and a pre-second key; and

circuitry for combining the pre-first key with the first key and the pre-second key with the second key.

19. The system of claim 15, wherein the big key is stored in the big key store when the big key does not match any other big key in the big key store.

20. A computer-readable storage medium comprising computer-readable instructions that when executed on a parallel processor having a bit width and a DWORD size, cause the processor to perform the operations of:

selecting a first random number and a second random number, the first random number differing from the second random number;

setting each of a checksum, a datum, a first key and a second key equal to zero;

grouping the image into at least one group, each group comprising a number of bits of the image equal to the bit width;

for each group, performing a hash comprising;

setting the checksum equal to the checksum plus the group;

setting the datum to equal the sum of the group and the datum multiplied by the first random number and summed with the second random number;

setting the first key to equal the first key modified by the datum; and

setting the second key to equal the second key modified by the datum;

setting a DWORD first key based on each DWORD size of bits of the first key;

setting a DWORD second key based on each DWORD size of bits of the second key;

storing a big key comprising the DWORD first key and the DWORD second key in a big key store;

when a second image matching the image has not been sent to the client, compressing the image and sending the client the compressed image and the big key across a communications network via a remote desktop protocol (RDP); and

when a second image matching the image has been sent to the client, sending the big key across the communications network via the RDP along with an indication to use the big key to access the second image from a cache and display the second image on a display of the client.