RDP bitmap hash acceleration using SIMD instructions

• US 9,071,843 B2
• Filed: 02/26/2009
• Issued: 06/30/2015
• Est. Priority Date: 02/26/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Abdo, Nadim Y., Albu, Voicu Anton
• Primary Examiner(s): Nigh, James D
• Application Number:
  US12/393,950
• Publication Number:
  US 20100215280A1
• Time in Patent Office: 2,315 Days
• Field of Search: 361/679.03, 361/679.55, 361/679.56, 190/110, 206/576, 206/320, 206/769, 206/771, 705/50, 726/26, 382/232
• US Class Current: 1/1
• 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 computer-implemented method for classifying an image on a parallel processing system having a bit width corresponding to a number of bits that a processor of the parallel processing system may operate on at a time, the method involving a first random number and a second random number, the first random number differing from the second random number, a datum, a first key, and a second key, comprising:

dividing, by the parallel processing system, the image into two groups each group comprising a number of bits of the image equal to the bit width;

for each group, performing, by the parallel processing system, a hash comprising;

setting a new value of the datum to equal the sum of the value expressed in binary of the group and the current value of the datum multiplied by the first random number and summed with the second random number;

setting a new value of the first key to equal the current value of the first key modified by the datum; and

setting a new value of the second key to equal the current value of the second key modified by the datum; and

after performing the hash, storing, by the parallel processing system, a big key comprising the first key and the second key in a computer memory.

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 comprises:

sending the image to the client in response to 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 the datum, the first key and the 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:

in response to determining that 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 10, wherein the image has an end, and a remainder number of bits that are not part of a group of the at least one group, and wherein the remainder number of bits are located within the image at the end of the image.

12. The method of claim 1, wherein performing the hash comprises:

performing 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 system involving a first random number and a second random number, the first random number differing from the second random number, a datum, a first key and a second key, comprising:

a processor; and

a memory comprising processor-executable instructions that, when executed on the processor, cause the system to at least;

divide the image into two groups, each group comprising a number of bits of the image equal to the bit width;

for each group, perform a hash comprising;

calculating a running reference to the image, the running reference comprising 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; and

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

16. The system of claim 15, wherein the memory further bears processor-executable instructions that, when executed on the processor, cause the system to at least:

encode the image; and

send the encoded image to a client across a communications network 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, wherein the memory further bears processor-executable instructions that, when executed on the processor, cause the system to at least:

determine that the image is unaligned before dividing 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

combine 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 device bearing computer-executable instructions that, when executed by a parallel processing system having a bit width corresponding to a number of bits that a processor of the parallel processing system may operate on at a time, a first random number and a second random number, the first random number differing from the second random number, a datum, a first key, and a second key, comprising, cause the parallel processing system to perform operations comprising:

dividing the image into two groups, each group comprising a number of bits of the image equal to the bit width;

for each group, performing a hash comprising;

setting a new value of the datum to equal the sum of the value expressed in binary of the group and the current value of the datum multiplied by the first random number and summed with the second random number;

setting a new value of the first key to equal the current value of the first key modified by the datum; and

setting a new value of the second key to equal the current value of the second key modified by the datum; and

after performing the hash, storing a big key comprising the first key and the second key in a computer memory.