The aim of this blog is to walk through an example of compressing a data sample using RDP 6.0 Compression. In a future blog I will provide a walkthrough of decoding the compressed stream back to the original data stream. In order to better understand the example I want to first establish some key points. Most of this blog will center around [MS-RDPEGDI] Remote Desktop Protocol: Graphics Device Interface (GDI) Acceleration Extensions Section 3.1.8 Bulk Data Compression. This blog will mainly include only details that are important to the example walkthrough itself. For more inquisitive minds, other important details not covered here can be found in section 3.1.8. RDP version 6.0 supports an extension to the compression techniques described in [MS-RDPBCGR] Remote Desktop Protocol: Basic Connectivity and Graphics Remoting Specification section 3.1.8. This extension is called "RDP 6.0 Bulk Compression" (RDP6.0-BC) and is only supported for server-to-client traffic.
Let’s take a look at some important concepts before we look at the example. The shared state necessary to support the transmission and reception of RDP6.0-BC compressed data between a client and server requires a history buffer and a current offset into the history buffer (HistoryOffset). The size of the history buffer is 64 KB. The HistoryOffset MUST start initialized to zero, while the history buffer MUST be filled with zeros. After it has been initialized, the entire history buffer is immediately regarded as valid.
In addition to the history buffer and HistoryOffset, a small cache MUST also be managed by the client and server endpoints. This cache is referred to as the OffsetCache and is used to store the last four unique copy-offsets encountered during data compression (copy-offsets are described in [MS-RDPBCGR] section 220.127.116.11). This saves on bandwidth in cases where there are many repeated copy-offsets. Whenever the history buffer is initialized or reinitialized, the OffsetCache MUST be emptied. The uncompressed data is first inserted into the local history buffer at the position indicated by HistoryOffset by the sender. The compressor then runs through the length of newly added uncompressed data to be sent and produces as output a sequence of literals (bytes to be sent uncompressed) or copy-tuples which consists of a <copy-offset, length-of-match> pair. The copy-offset component of the copy-tuple is an index into the history buffer (counting backwards from the current byte being compressed in the history buffer towards the start of the buffer) where there is a match to the data to be sent.
There are 6 tables and a flowchart that are needed to walk through the sample data. These can be found under [MS-RDPEGDI] 18.104.22.168.4.1 Literal, EOS, and Copy-Offset Tables and [MS-RDPEGDI] 22.214.171.124.4.3 Encoding the Logically Compressed Stream respectively.
Here are the tables and flowcharts that we will be using. You may find it easier to print these off in order to follow the walkthrough.
Table 1: Bit-lengths for the 294 Huffman-encoded LiteralOrEosOrCopyOffset codes
Table 2: Huffman codebook for the 294 Huffman-encoded LiteralOrEosOrCopyOffset codes
Table 3: Bit count and base value lookup tables to encode and decode copy-offset values
Table 4: Table 4: Bit lengths for the 32 Huffman-encoded LengthOfMatch codes
Table 5: Huffman codebook for the 32 Huffman-encoded LengthOfMatch codes
Table 6: Bit count and base value lookup tables to encode and decode length-of-match values
Table 1: Bit-lengths for the 294 Huffman-encoded LiteralOrEosOrCopyOffset codes
For example, it can be determined from the previous table that the 0th Huffman-encoded LiteralOrEosOrCopyOffset code has a length of 6 bits, and the 131st Huffman-encoded LiteralOrEosOrCopyOffset code has a length of 10 (0x0A) bits.
For example, it can be determined from the previous table that the 0th Huffman-encoded LiteralOrEosOrCopyOffset code has a value of 0x0004. Applying the bit length information from the first table in this section (6 bits), it can be determined that the Huffman code in binary MUST be 000100.
As another example, it can be determined from the previous table that the 131st Huffman-encoded LiteralOrEosOrCopyOffset code has a value of 0x02a7. Applying the bit length information from the first table in this section (10 bits), it can be determined that the Huffman code in binary MUST be 1010100111.
Table 3: Bit count and base value lookup tables to encode and decode copy-offset values.
Table 4: Bit lengths for the 32 Huffman-encoded LengthOfMatch codes
For example, it can be determined from the previous table that the 0th Huffman-encoded LengthOfMatch code has a length of 4 bits while the 21st Huffman-encoded LengthOfMatch code has a length of 8 bits.
Using the canonical Huffman algorithm (for more information, see [CANONHUFF]), the Huffman codebook table shown in the following table (HuffCodeL) can be obtained. The bit lengths in the previous table MUST be used to mask out the appropriate bits.
For example, it can be determined from the previous table that the 0th Huffman-encoded LengthOfMatch code has a value of 0x0001. Applying the bit length information from the first table in this section (4 bits), it can be determined that the Huffman code in binary MUST be 0001.
As another example, it can be determined from the previous table that the 21st Huffman-encoded LengthOfMatch code has a value of 0x009f. Applying the bit length information from the first table in this section (8 bits), it can be determined that the Huffman code in binary MUST be 10011111.
The following flow chart describes how literals and copy-tuples in a logically compressed stream are encoded.
Figure 8: Encoding a logically compressed stream
Literals are merely encoded using the Huffman Tables HuffCodeLEC (table 2) and HuffLengthL (table 1). Copy-tuples are encoded using the four lookup tables in table 3 and table 6 (CopyOffsetBaseLUT, CopyOffsetBitsLUT, LoMBaseLUT, and LoMBitsLUT) and the Huffman Tables.
The flowchart shows that the initial decision is whether we are dealing with a literal or not. If we are working with a literal then the process is fairly simple. Encode the literal using Huffman tables using table 1 and 2 and output the Encoded bits. If the data does not represent a literal then we are dealing with outputting a copy-tuple which consists of a <copy-offset, length-of-match> pair, as previously mentioned.
For the copy-tuple there are two encodings that need to be performed, one for the copy-offset and one for the length-of-match (LoM).
Encoding the Length of Match:
Encoding of the length-of-match is shown in the previous figure by the Action B item. The following describes the algorithm for encoding the length-of-match.
LUTIndex = IndexOfEqualOrSmallerEntry(LoM, LoMBaseLUT)
ExtraBitsLength = LoMBitsLUT[LUTIndex]
ExtraBits = (LoM - 2) & ((2 ^ ExtraBitsLength) - 1)
OutputBits (ExtraBits, ExtraBitsLength)
Now that we are armed with all of this information and perhaps a little dangerous lets walk through the sample data to see what data the encoder should spit out. The sample data we will use is:
Offset 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Bytes 01 00 00 00 0a 00 0a 00 20 00 20 00 80 00 80 00
Step 1 Encoding a literal
01 For this data we use tables one and 2. We use the value of 1 to index into both tables. Table 1 gives us a value of 6 for the length and 0x24 for the value. Doing so we get the output of 0x24:6
literal 6 bit code 36 (0x24)
Step 2 Encoding a literal
00 Again it’s a literal so use tables 1 and 2 in the same manner. Output is 0x04:6
Step 3 Encoding the Copy-Offset for the match – Action A in the Flowchart
Match (non cached)
At 1, length 2
(Back 1 position) Looking back at the history buffer we see that we have a match at index 1 (back 1 position) and the match has a length of 2. We need to use the algorithm for encoding a copy-tuple to obtain the copy-offset and Extra match bits if any. Here is that algorithm:
Encoding the Copy-Offset:
LUTIndex = IndexOfEqualOrSmallerEntry(CopyOffset + 1, CopyOffsetBaseLUT)
HuffmanIndex = LUTIndex + 257
ExtraBitsLength = CopyOffsetBitsLUT[LUTIndex]
ExtraBits = CopyOffset & ((2 ^ ExtraBitsLen) - 1)
The IndexOfEqualOrSmallerEntry function searches through the specified LUT table and returns the index of the entry that contains a value of equal or lesser value than the first parameter. The OutputBits function outputs the bits specified by the first parameter in the appropriate order (the number of bits to output is given by the second parameter). "^" is the exponentiation operator, and "&" is the bitwise AND operator.
Insert our values, note that the IndexOfEqualOrSmallerEntry function uses the amount of the offset (backup position) +1 as its first parameter.
LUTIndex = 1 (Table 3)
HuffmanIndex = 1 + 257 = 258
OutputBits(0x0039, 7) obtain the value and length from Huffman tables 1 and 2
ExtraBitsLength = 2
ExtraBits = 8 & ((2 ^ 2) - 1) = 8 & 3 = bin:1000 & bin:0011 = 0
ExtraMatchBits = 0 (from table 3 for LUTIndex 1)
Step 4 Encoding the Length of the match – Action B in the flowchart
Length = 2
Using the following algorithm we calculate LoM:
Calculation using our data:
LUTIndex = 0 This comes from Table 6 using out LOM of 2
HuffmanCode = 0x0001 (Index 0 of Table 5)
LoMBits = 4 (Index of 0 Table 4)
OutputBits(0x0001, 4) Output of Huffman code and length from Tables 5 and 4 respectively.
ExtraBitsLength = 0 (from table 3 for LUTIndex 0)
No extra bits to output
Step 5 Encode Literal
Using the value a (dec 10) as the index into Tables 1 and 2 we obtain a length of 7 and a code of 0x69
Step 6 Found a Match Encode the Copy-Offset and LoM
00 0a 00
At 3, length 3 (non cached)
(Back 2 positions)
LUTIndex = 2 (Table 3)
HuffmanIndex = 2 + 257 = 259 (0x103)
Index 0x103 -> Huffman Code 0x0079 (from table 2)
Bits for Index 259 -> 0x7 (from table 1)
ExtraMatchBits = 0 (from Table 3 for LUTIndex 2)
Length = 3
LUTIndex = 1 (Table 6)
HuffmanCode for LoM 0x0000 (Index 1 Table 5)
LoMBits = 0x2 (index 1 Table 4)
ExtraMatchBits = 0 (from Table 3 for LUTIndex 1)
Step 6 Encode Literal
literal 8 bit code 77 (0x4d)
Step 7 Found a Match [Cached] Encode the Copy-Offset and LoM
00 20 00
Match (cached)-- Last Offset used was also back 2 postions so we have a match with LRU cache index 0
Looking back at the flowchart you can see what happens when we get a cache hit.
At 7, length 3
Index + 289 = 0 + 289 = 289 (0x121)
HuffmanCode for 289 -> 0x0018 (table 2)
Bits for Index 289 -> 0x5 (from Table 1)
Encode the LoM as previously performed.
Step 8 Encode Literal
literal 7 bit code 25 (0x0019)
00 80 00
At 11 (0xb), length 3
Last Offset used was also back 2 postions so we have a match with LRU cache index 0
Note Wire Format:
The compressed stream consists of a bit-encoded sequence of literals, <copy-offset, length-of-match> tuples (also known as copy-tuples), and a terminating End-of-Stream (EOS) marker. The convention used on the stream is that the sender MUST output bytes in little-endian order with the most significant bit first.
Input : 01 00 00 00 0a 00 0a 00 20 00 20 00 80 00 80 00
Output of the Encoder: 24 91 8b 74 9e 26 4c 06 13 be bf b6 80 06 4c 77 4c 4f 4c 2f 2c 01 d1 6b 41…
There you have it! This stream will be byte transposed into little-endian format and then sent over the wire to the decoder. Look for Part 2 RDP 6.0 Decompressing Data Walkthrough coming soon to a blog near you.