/* -*- c-basic-offset: 8 -*-   rdesktop: A Remote Desktop Protocol client.   Protocol services - RDP decompression   Copyright (C) Matthew Chapman 1999-2007   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;intmppc_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;	RD_BOOL big = ctype & RDP_MPPC_BIG ? True : False;	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 < (big ? 3 : 2))		{			if (i >= clen)				return -1;			walker |= (data[i++] & 0xff) << (24 - walker_len);			walker_len += 8;		}		if (big)		{			/* 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 lower 11 bits of the value ( value - 320 )			   2368-65535: 110 followed by 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;			}		}		else		{			/* offset decoding where offset len is:			   -63: 1111 followed by the lower 6 bits of the value			   64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )			   320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )			 */			switch (((uint32) walker) >> ((uint32) 30))			{				case 3:	/* - 63 */					if (walker_len < 8)					{						if (i >= clen)							return -1;						walker |= (data[i++] & 0xff) << (24 - walker_len);						walker_len += 8;					}					walker <<= 2;					match_off = ((uint32) walker) >> ((uint32) 26);					walker <<= 6;					walker_len -= 8;					break;				case 2:	/* 64 - 319 */					for (; walker_len < 10; walker_len += 8)					{						if (i >= clen)							return -1;						walker |= (data[i++] & 0xff) << (24 - walker_len);					}					walker <<= 2;					match_off = (((uint32) walker) >> ((uint32) 24)) + 64;					walker <<= 8;					walker_len -= 10;					break;				default:	/* 320 - 8191 */					for (; walker_len < 14; walker_len += 8)					{						if (i >= clen)							return -1;						walker |= (data[i++] & 0xff) << (24 - walker_len);					}					match_off = (walker >> 18) + 320;					walker <<= 14;					walker_len -= 14;					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 = big ? 14 : 11;	/* 11 or 14 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 = (big ? 16 : 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) & (big ? 65535 : 8191);		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;}