Re: [rdesktop-devel] 16 bpp compression

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Hi Vahur,

Thanks very much! I've commited your decompression code to CVS. Bit 0 in the ctype byte tells whether to use the old or alternative values for mppc decompression. Hopefully the compression problems are over now!

I think we should enable compression by default if there's no more problems. I've read a document from Microsoft stating that it hardly makes a difference in the amount of concurrent connections a server is able to handle. So to the list: Are there any objections to enabling compression by default?

Regards,
Jeroen

On Sun, Apr 17, 2005 at 06:25:30AM +0300, Vahur Sinij?rv wrote:
> Hi !
> 
> Thanks for the tip !
> 
> > Sending flags |= 0x0280 in the RDP logon packet (rdp.c) seems to trigger
> > the other (or modified?) compression algorithm.
> 
> You do not actually have to set the 0x80 bit, just the 0x200 and it enables 
> bigger history buffer for MPPC. I did some investigation on the matter and 
> discovered that the compression is indeed MPPC, just the history is now 64K. 
> They did change also the huffman encoding of offsets into history and by 
> trial and error I've managed to find out the correct values, so here is the 
> mppc.c, which works with RDP5 compression:
> 
> /* -*- c-basic-offset: 8 -*-
>    rdesktop: A Remote Desktop Protocol client.
>    Protocol services - RDP decompression
>    Copyright (C) Matthew Chapman 1999-2005
> 
>    This program is free software; you can redistribute it and/or modify
>    it under the terms of the GNU General Public License as published by
>    the Free Software Foundation; either version 2 of the License, or
>    (at your option) any later version.
> 
>    This program is distributed in the hope that it will be useful,
>    but WITHOUT ANY WARRANTY; without even the implied warranty of
>    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>    GNU General Public License for more details.
> 
>    You should have received a copy of the GNU General Public License
>    along with this program; if not, write to the Free Software
>    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
> */
> 
> #include <stdio.h>
> #include <string.h>
> 
> #include "rdesktop.h"
> 
> /* mppc decompression                       */
> /* http://www.faqs.org/rfcs/rfc2118.html    */
> 
> /* Contacts:                                */
> 
> /* hifn contact mentioned in the faq is     */
> /* Robert Friend rfriend at hifn dot com    */
> 
> /* if you have questions regarding MPPC     */
> /* our contact is                           */
> /* Guus Dhaeze  GDhaeze at hifn dot com     */
> 
> /* Licensing:                               */
> 
> /* decompression is alright as long as we   */
> /* don't compress data                      */
> 
> /* Algorithm: */
> 
> /* as the rfc states the algorithm seems to */
> /* be LZ77 with a sliding buffer            */
> /* that is empty at init.                   */
> 
> /* the algorithm is called LZS and is       */
> /* patented for another couple of years.    */
> 
> /* more information is available in         */
> /* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt 
> */
> 
> 
> RDPCOMP g_mppc_dict;
> 
> int
> mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * 
> rlen)
> {
> 	int k, walker_len = 0, walker;
> 	uint32 i = 0;
> 	int next_offset, match_off;
> 	int match_len;
> 	int old_offset, match_bits;
> 
> 	uint8 *dict = g_mppc_dict.hist;
> 
> 	if ((ctype & RDP_MPPC_COMPRESSED) == 0)
> 	{
> 		*roff = 0;
> 		*rlen = clen;
> 		return 0;
> 	}
> 
> 	if ((ctype & RDP_MPPC_RESET) != 0)
> 	{
> 		g_mppc_dict.roff = 0;
> 	}
> 
> 	if ((ctype & RDP_MPPC_FLUSH) != 0)
> 	{
> 		memset(dict, 0, RDP_MPPC_DICT_SIZE);
> 		g_mppc_dict.roff = 0;
> 	}
> 
> 	*roff = 0;
> 	*rlen = 0;
> 
> 	walker = g_mppc_dict.roff;
> 
> 	next_offset = walker;
> 	old_offset = next_offset;
> 	*roff = old_offset;
> 	if (clen == 0)
> 		return 0;
> 	clen += i;
> 
> 	do
> 	{
> 		if (walker_len == 0)
> 		{
> 			if (i >= clen)
> 				break;
> 			walker = data[i++] << 24;
> 			walker_len = 8;
> 		}
> 		if (walker >= 0)
> 		{
> 			if (walker_len < 8)
> 			{
> 				if (i >= clen)
> 				{
> 					if (walker != 0)
> 						return -1;
> 					break;
> 				}
> 				walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				walker_len += 8;
> 			}
> 			if (next_offset >= RDP_MPPC_DICT_SIZE) {
> 				return -1;
> 			}
> 			dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
> 			walker <<= 8;
> 			walker_len -= 8;
> 			continue;
> 		}
> 		walker <<= 1;
> 		/* fetch next 8-bits */
> 		if (--walker_len == 0)
> 		{
> 			if (i >= clen)
> 				return -1;
> 			walker = data[i++] << 24;
> 			walker_len = 8;
> 		}
> 		/* literal decoding */
> 		if (walker >= 0)
> 		{
> 			if (walker_len < 8)
> 			{
> 				if (i >= clen)
> 					return -1;
> 				walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				walker_len += 8;
> 			}
> 			if (next_offset >= RDP_MPPC_DICT_SIZE) {
> 				return -1;
> 			}
> 			dict[next_offset++] = (uint8) (walker >> 24 | 0x80);
> 			walker <<= 8;
> 			walker_len -= 8;
> 			continue;
> 		}
> 
> 		/* decode offset  */
> 		/* length pair    */
> 		walker <<= 1;
> 		if (--walker_len < 3)
> 		{
> 			if (i >= clen)
> 				return -1;
> 			walker |= (data[i++] & 0xff) << (24 - walker_len);
> 			walker_len += 8;
> 		}
> 		/* offset decoding where offset len is:
> 		   -63: 11111 followed by the lower 6 bits of the value
> 		   64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
> 		   320-2367: 1110 followed by the lower 11 bits of the value ( value - 320 )
> 		   2368-65535: 110 followed by the lower 16 bits of the value ( value - 
> 2368 )
> 		 */
> 		switch (((uint32) walker) >> ((uint32) 29))
> 		{
> 			case 7:	/* - 63 */
> 				for (; walker_len < 9; walker_len += 8) {
> 					if (i >= clen)
> 						return -1;
> 					walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				}
> 				walker <<= 3;
> 				match_off = ((uint32) walker) >> ((uint32) 26);
> 				walker <<= 6;
> 				walker_len -= 9;
> 				break;
> 
> 			case 6:	/* 64 - 319 */
> 				for (; walker_len < 11; walker_len += 8)
> 				{
> 					if (i >= clen)
> 						return -1;
> 					walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				}
> 
> 				walker <<= 3;
> 				match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
> 				walker <<= 8;
> 				walker_len -= 11;
> 				break;
> 
> 			case 5:
> 			case 4:	/* 320 - 2367 */
> 				for (; walker_len < 13; walker_len += 8)
> 				{
> 					if (i >= clen)
> 						return -1;
> 					walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				}
> 
> 				walker <<= 2;
> 				match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
> 				walker <<= 11;
> 				walker_len -= 13;
> 				break;
> 				
> 			default: /* 2368 - 65535 */
> 				for (; walker_len < 17; walker_len += 8)
> 				{
> 					if (i >= clen)
> 						return -1;
> 					walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				}
> 
> 				walker <<= 1;
> 				match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
> 				walker <<= 16;
> 				walker_len -= 17;
> 				break;
> 			
> 		}
> 		if (walker_len == 0)
> 		{
> 			if (i >= clen)
> 				return -1;
> 			walker = data[i++] << 24;
> 			walker_len = 8;
> 		}
> 
> 		/* decode length of match */
> 		match_len = 0;
> 		if (walker >= 0)
> 		{		/* special case - length of 3 is in bit 0 */
> 			match_len = 3;
> 			walker <<= 1;
> 			walker_len--;
> 		}
> 		else
> 		{
> 			/* this is how it works len of:
> 			   4-7: 10 followed by 2 bits of the value
> 			   8-15: 110 followed by 3 bits of the value
> 			   16-31: 1110 followed by 4 bits of the value
> 			   32-63: .... and so forth
> 			   64-127:
> 			   128-255:
> 			   256-511:
> 			   512-1023:
> 			   1024-2047:
> 			   2048-4095:
> 			   4096-8191:
> 
> 			   i.e. 4097 is encoded as: 111111111110 000000000001
> 			   meaning 4096 + 1...
> 			 */
> 			match_bits = 11;	/* 11 bits of value at most */
> 			do
> 			{
> 				walker <<= 1;
> 				if (--walker_len == 0)
> 				{
> 					if (i >= clen)
> 						return -1;
> 					walker = data[i++] << 24;
> 					walker_len = 8;
> 				}
> 				if (walker >= 0)
> 					break;
> 				if (--match_bits == 0)
> 				{
> 					return -1;
> 				}
> 			}
> 			while (1);
> 			match_len = 13 - match_bits;
> 			walker <<= 1;
> 			if (--walker_len < match_len)
> 			{
> 				for (; walker_len < match_len; walker_len += 8)
> 				{
> 					if (i >= clen)
> 					{
> 						return -1;
> 					}
> 					walker |= (data[i++] & 0xff) << (24 - walker_len);
> 				}
> 			}
> 
> 			match_bits = match_len;
> 			match_len =
> 				((walker >> (32 - match_bits)) & (~(-1 << match_bits))) | (1 <<
> 											   match_bits);
> 			walker <<= match_bits;
> 			walker_len -= match_bits;
> 		}
> 		if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
> 		{
> 			return -1;
> 		}
> 		
> 		/* memory areas can overlap - meaning we can't use memXXX functions */
> 		k = (next_offset - match_off) & (RDP_MPPC_DICT_SIZE - 1);
> 		do
> 		{
> 			dict[next_offset++] = dict[k++];
> 		}
> 		while (--match_len != 0);
> 	}
> 	while (1);
> 
> 	/* store history offset */
> 	g_mppc_dict.roff = next_offset;
> 
> 	*roff = old_offset;
> 	*rlen = next_offset - old_offset;
> 
> 	return 0;
> }
> 
> This makes small 32x32 cells unneccessary and you can again use 64x64 and 
> compression and persistent cache together. It really makes huge difference 
> over DSL links. I think this function could be renamed to mppc_expand_rdp5() 
> or something and used only when RDP5 and compression is active (through 
> pointer to function or something). Or you could extract the part which deals 
> with offsets and lengths and call this though pointer.
> 
> History size must be set to 64K in constants.h
> #define RDP_MPPC_DICT_SIZE	65536
> 
> And of course the flags in rdp.c in function rdp_send_logon_info() must be set 
> to flags |= 0x0200
> 
> There might be a problem with lengths decoding if they have larger lengths 
> than 8K, but I have not encountered any yet. Bandwidth usage with larger 
> history is less, because better compression ratios can be achieved.
> 
> Regards,
> Vahur
> 
> 
> -------------------------------------------------------
> SF email is sponsored by - The IT Product Guide
> Read honest & candid reviews on hundreds of IT Products from real users.
> Discover which products truly live up to the hype. Start reading now.
> http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click
> _______________________________________________
> rdesktop-devel mailing list
> rde...@li...
> https://lists.sourceforge.net/lists/listinfo/rdesktop-devel

Re: [rdesktop-devel] 16 bpp compression

rdesktop has moved to GitHub

Re: [rdesktop-devel] 16 bpp compression