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.

 [MS-RDPEGDI]   http://msdn.microsoft.com/en-us/library/cc241537(PROT.10).aspx

 [MS-RDPBCGR]   http://msdn.microsoft.com/en-us/library/cc240445(v=PROT.10).aspx

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 3.1.8.1). 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] 3.1.8.1.4.1   Literal, EOS, and Copy-Offset Tables and [MS-RDPEGDI] 3.1.8.1.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

Flowchart:

 

Table 1: Bit-lengths for the 294 Huffman-encoded LiteralOrEosOrCopyOffset codes

Code index

0

1

2

3

4

5

6

7

0

0x6

0x6

0x6

0x7

0x7

0x7

0x7

0x7

8

0x7

0x7

0x7

0x8

0x8

0x8

0x8

0x8

16

0x8

0x8

0x9

0x8

0x9

0x9

0x9

0x9

24

0x8

0x8

0x9

0x9

0x9

0x9

0x9

0x9

32

0x8

0x9

0x9

0xa

0x9

0x9

0x9

0x9

40

0x9

0x9

0x9

0xa

0x9

0xa

0xa

0xa

48

0x9

0x9

0xa

0x9

0xa

0x9

0xa

0x9

56

0x9

0x9

0xa

0xa

0x9

0xa

0x9

0x9

64

0x8

0x9

0x9

0x9

0x9

0xa

0xa

0xa

72

0x9

0x9

0xa

0xa

0xa

0xa

0xa

0xa

80

0x9

0x9

0xa

0xa

0xa

0xa

0xa

0xa

88

0xa

0x9

0xa

0xa

0xa

0xa

0xa

0xa

96

0x8

0xa

0xa

0xa

0xa

0xa

0xa

0xa

104

0xa

0xa

0xa

0xa

0xa

0xa

0xa

0xa

112

0x9

0xa

0xa

0xa

0xa

0xa

0xa

0xa

120

0x9

0xa

0xa

0xa

0xa

0xa

0xa

0x9

128

0x7

0x9

0x9

0xa

0x9

0xa

0xa

0xa

136

0x9

0xa

0xa

0xa

0xa

0xa

0xa

0xa

144

0x9

0xa

0xa

0xa

0xa

0xa

0xa

0xa

152

0xa

0xa

0xa

0xa

0xa

0xa

0xa

0xa

160

0xa

0xa

0xa

0xa

0xa

0xa

0xa

0xa

168

0xa

0xa

0xa

0xd

0xa

0xa

0xa

0xa

176

0xa

0xa

0xb

0xa

0xa

0xa

0xa

0xa

184

0xa

0xa

0xa

0xa

0xa

0xa

0xa

0xa

192

0x9

0xa

0xa

0xa

0xa

0xa

0x9

0xa

200

0xa

0xa

0xa

0xa

0x9

0xa

0xa

0xa

208

0x9

0xa

0xa

0xa

0xa

0xa

0xa

0xa

216

0xa

0xa

0xa

0xa

0xa

0xa

0xa

0xa

224

0x9

0xa

0xa

0xa

0xa

0xa

0xa

0xa

232

0xa

0xa

0xa

0xa

0xa

0xa

0x9

0xa

240

0x8

0x9

0x9

0xa

0x9

0xa

0xa

0xa

248

0x9

0xa

0xa

0xa

0x9

0x9

0x8

0x7

256

0xd

0xd

0x7

0x7

0xa

0x7

0x7

0x6

264

0x6

0x6

0x6

0x5

0x6

0x6

0x6

0x5

272

0x6

0x5

0x6

0x6

0x6

0x6

0x6

0x6

280

0x6

0x6

0x6

0x6

0x6

0x6

0x6

0x6

288

0x8

0x5

0x6

0x7

0x7

0xD

 

 

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.

Table 2: Huffman codebook for the 294 Huffman-encoded LiteralOrEosOrCopyOffset codes

Code index

0

1

2

3

4

5

6

7

0

0x0004

0x0024

0x0014

0x0011

0x0051

0x0031

0x0071

0x0009

8

0x0049

0x0029

0x0069

0x0015

0x0095

0x0055

0x00d5

0x0035

16

0x00b5

0x0075

0x001d

0x00f5

0x011d

0x009d

0x019d

0x005d

24

0x000d

0x008d

0x015d

0x00dd

0x01dd

0x003d

0x013d

0x00bd

32

0x004d

0x01bd

0x007d

0x006b

0x017d

0x00fd

0x01fd

0x0003

40

0x0103

0x0083

0x0183

0x026b

0x0043

0x016b

0x036b

0x00eb

48

0x0143

0x00c3

0x02eb

0x01c3

0x01eb

0x0023

0x03eb

0x0123

56

0x00a3

0x01a3

0x001b

0x021b

0x0063

0x011b

0x0163

0x00e3

64

0x00cd

0x01e3

0x0013

0x0113

0x0093

0x031b

0x009b

0x029b

72

0x0193

0x0053

0x019b

0x039b

0x005b

0x025b

0x015b

0x035b

80

0x0153

0x00d3

0x00db

0x02db

0x01db

0x03db

0x003b

0x023b

88

0x013b

0x01d3

0x033b

0x00bb

0x02bb

0x01bb

0x03bb

0x007b

96

0x002d

0x027b

0x017b

0x037b

0x00fb

0x02fb

0x01fb

0x03fb

104

0x0007

0x0207

0x0107

0x0307

0x0087

0x0287

0x0187

0x0387

112

0x0033

0x0047

0x0247

0x0147

0x0347

0x00c7

0x02c7

0x01c7

120

0x0133

0x03c7

0x0027

0x0227

0x0127

0x0327

0x00a7

0x00b3

128

0x0019

0x01b3

0x0073

0x02a7

0x0173

0x01a7

0x03a7

0x0067

136

0x00f3

0x0267

0x0167

0x0367

0x00e7

0x02e7

0x01e7

0x03e7

144

0x01f3

0x0017

0x0217

0x0117

0x0317

0x0097

0x0297

0x0197

152

0x0397

0x0057

0x0257

0x0157

0x0357

0x00d7

0x02d7

0x01d7

160

0x03d7

0x0037

0x0237

0x0137

0x0337

0x00b7

0x02b7

0x01b7

168

0x03b7

0x0077

0x0277

0x07ff

0x0177

0x0377

0x00f7

0x02f7

176

0x01f7

0x03f7

0x03ff

0x000f

0x020f

0x010f

0x030f

0x008f

184

0x028f

0x018f

0x038f

0x004f

0x024f

0x014f

0x034f

0x00cf

192

0x000b

0x02cf

0x01cf

0x03cf

0x002f

0x022f

0x010b

0x012f

200

0x032f

0x00af

0x02af

0x01af

0x008b

0x03af

0x006f

0x026f

208

0x018b

0x016f

0x036f

0x00ef

0x02ef

0x01ef

0x03ef

0x001f

216

0x021f

0x011f

0x031f

0x009f

0x029f

0x019f

0x039f

0x005f

224

0x004b

0x025f

0x015f

0x035f

0x00df

0x02df

0x01df

0x03df

232

0x003f

0x023f

0x013f

0x033f

0x00bf

0x02bf

0x014b

0x01bf

240

0x00ad

0x00cb

0x01cb

0x03bf

0x002b

0x007f

0x027f

0x017f

248

0x012b

0x037f

0x00ff

0x02ff

0x00ab

0x01ab

0x006d

0x0059

256

0x17ff

0x0fff

0x0039

0x0079

0x01ff

0x0005

0x0045

0x0034

264

0x000c

0x002c

0x001c

0x0000

0x003c

0x0002

0x0022

0x0010

272

0x0012

0x0008

0x0032

0x000a

0x002a

0x001a

0x003a

0x0006

280

0x0026

0x0016

0x0036

0x000e

0x002e

0x001e

0x003e

0x0001

288

0x00ed

0x0018

0x0021

0x0025

0x0065

0x1fff

 

 

 

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.

Index

CopyOffsetBitsLUT

CopyOffsetBaseLUT

0

0

1

1

0

2

2

0

3

3

0

4

4

1

5

5

1

7

6

2

9

7

2

13

8

3

17

9

3

25

10

4

33

11

4

49

12

5

65

13

5

97

14

6

129

15

6

193

16

7

257

17

7

385

18

8

513

19

8

769

20

9

1025

21

9

1537

22

10

2049

23

10

3073

24

11

4097

25

11

6145

26

12

8193

27

12

12289

28

13

16385

29

13

24577

30

14

32769

31

14

49153

32

15

65537

 

Table 4: Bit lengths for the 32 Huffman-encoded LengthOfMatch codes

 

0

1

2

3

4

5

6

7

0

0x4

0x2

0x3

0x4

0x3

0x4

0x4

0x5

8

0x4

0x5

0x5

0x6

0x6

0x7

0x7

0x8

16

0x7

0x8

0x8

0x9

0x9

0x8

0x9

0x9

24

0x9

0x9

0x9

0x9

0x9

0x9

0x9

0x9

 

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.

Table 5: Huffman codebook for the 32 Huffman-encoded LengthOfMatch codes

Code index

0

1

2

3

4

5

6

7

0

0x0001

0x0000

0x0002

0x0009

0x0006

0x0005

0x000d

0x000b

8

0x0003

0x001b

0x0007

0x0017

0x0037

0x000f

0x004f

0x006f

16

0x002f

0x00ef

0x001f

0x005f

0x015f

0x009f

0x00df

0x01df

24

0x003f

0x013f

0x00bf

0x01bf

0x007f

0x017f

0x00ff

0x01ff

 

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.

Table 6: Bit count and base value lookup tables to encode and decode length-of-match values

Index

LoMBitsLUT

LoMBaseLUT

0

0

2

1

0

3

2

0

4

3

0

5

4

0

6

5

0

7

6

0

8

7

0

9

8

1

10

9

1

12

10

1

14

11

1

16

12

2

18

13

2

22

14

2

26

15

2

30

16

3

34

17

3

42

18

3

50

19

3

58

20

4

66

21

4

82

22

4

98

23

4

114

24

6

130

25

6

194

26

8

258

27

8

514

28

14

2

29

14

2

 

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)

OutputBits(HuffCodeL[LUTIndex], HuffLengthL[LUTIndex])

 

ExtraBitsLength = LoMBitsLUT[LUTIndex]

ExtraBits = (LoM - 2) & ((2 ^ ExtraBitsLength) - 1)

OutputBits (ExtraBits, ExtraBitsLength)

Sample Walkthrough:

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)

Output 0x24:6

 

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

00 00

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

OutputBits(HuffCodeLEC[HuffmanIndex], HuffLengthLEC[HuffmanIndex])

 

ExtraBitsLength = CopyOffsetBitsLUT[LUTIndex]

ExtraBits = CopyOffset & ((2 ^ ExtraBitsLen) - 1)

OutputBits(ExtraBits, ExtraBitsLength)

 

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

                                                                                                                OutputBits(0x00,

 

 

ExtraMatchBits = 0 (from table 3 for LUTIndex 1)

 

Output 0x39:7

 

Step 4 Encoding the Length of the match – Action B in the flowchart

Encoding LoM

Length = 2

   Using the following algorithm we calculate LoM:

 

Encoding the Length of Match:

LUTIndex = IndexOfEqualOrSmallerEntry(LoM, LoMBaseLUT)

OutputBits(HuffCodeL[LUTIndex], HuffLengthL[LUTIndex])

 

ExtraBitsLength = LoMBitsLUT[LUTIndex]

ExtraBits = (LoM - 2) & ((2 ^ ExtraBitsLength) - 1)

OutputBits (ExtraBits, ExtraBitsLength)

 

 

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

0a

 

 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

Output 0x69:7

 

Step 6 Found a Match Encode the Copy-Offset and LoM

00 0a 00

Match

At 3, length 3 (non cached)

(Back 2 positions)

 

Encoding Copy-Offset

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)

 

Output 0x79:7

 

Encoding LoM

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)

 

Output 0x0:2

 

Step 6 Encode Literal

20

literal 8 bit code 77 (0x4d)

Output 0x4d:8

 

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

(Back 2 positions)

Encode OffsetCacheIndex

Index + 289 = 0 + 289 = 289 (0x121)

HuffmanCode for 289 -> 0x0018 (table 2)

Bits for Index 289 -> 0x5 (from Table 1)

Output 0x18:5

Encode the LoM as previously performed.

Encoding LoM

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)

Output 0x0:2

 

Step 8 Encode Literal

80

literal 7 bit code 25 (0x0019)

Output 0x19:7

 

Step 7 Found a Match [Cached] Encode the Copy-Offset and LoM

00 80 00

Match (cached)

At 11 (0xb), length 3

(Back 2 positions)

Last Offset used was also back 2 postions so we have a match with LRU cache index 0

 

Encode OffsetCacheIndex

Index + 289 = 0 + 289 = 289 (0x121)

HuffmanCode for 289 -> 0x0018 (table 2)

Bits for Index 289 -> 0x5 (from Table 1)

Output 0x18:5

 

Encoding LoM

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)

 

Output 0x0:2

 

Encoding Finished!

 

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: 0x24:6

          0x04:6

          0x39:7

          0x01:4

          0x69:7

          0x79:7

          0x00:2

          0x4d:8

          0x18:5

          0x00:2

          0x19:7

          0x18:5

          0x00:2

 

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.