trunk/rdesktop/mppc.c

/* -*- 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 < (ctype & RDP_MPPC_BIG ? 3 : 2))
                {
                        if (i >= clen)
                                return -1;
                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                        walker_len += 8;
                }

                if (ctype & RDP_MPPC_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 = 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) & (ctype & RDP_MPPC_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;
}
1	n-ki	689	/* -- c-basic-offset: 8 --
2			rdesktop: A Remote Desktop Protocol client.
3			Protocol services - RDP decompression
4	stargo	828	Copyright (C) Matthew Chapman 1999-2005
5	n-ki	689
6			This program is free software; you can redistribute it and/or modify
7			it under the terms of the GNU General Public License as published by
8			the Free Software Foundation; either version 2 of the License, or
9			(at your option) any later version.
10
11			This program is distributed in the hope that it will be useful,
12			but WITHOUT ANY WARRANTY; without even the implied warranty of
13			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14			GNU General Public License for more details.
15
16			You should have received a copy of the GNU General Public License
17			along with this program; if not, write to the Free Software
18			Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19			*/
20
21	n-ki	684	#include <stdio.h>
22			#include <string.h>
23
24			#include "rdesktop.h"
25
26	n-ki	687	/* mppc decompression */
27	n-ki	684	/* http://www.faqs.org/rfcs/rfc2118.html */
28
29	n-ki	689	/* Contacts: */
30	n-ki	684
31	n-ki	689	/* hifn contact mentioned in the faq is */
32			/* Robert Friend rfriend at hifn dot com */
33	n-ki	684
34	n-ki	689	/* if you have questions regarding MPPC */
35			/* our contact is */
36			/* Guus Dhaeze GDhaeze at hifn dot com */
37	n-ki	684
38	n-ki	689	/* Licensing: */
39	n-ki	684
40	n-ki	689	/* decompression is alright as long as we */
41			/* don't compress data */
42
43			/* Algorithm: */
44
45	n-ki	687	/* as the rfc states the algorithm seems to */
46			/* be LZ77 with a sliding buffer */
47			/* that is empty at init. */
48	n-ki	684
49	n-ki	689	/* the algorithm is called LZS and is */
50			/* patented for another couple of years. */
51	n-ki	684
52	n-ki	689	/* more information is available in */
53			/* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
54	n-ki	684
55	n-ki	689
56	n-ki	687	RDPCOMP g_mppc_dict;
57
58	n-ki	684	int
59			mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen)
60			{
61			int k, walker_len = 0, walker;
62	jsorg71	712	uint32 i = 0;
63	n-ki	684	int next_offset, match_off;
64			int match_len;
65			int old_offset, match_bits;
66
67	jsorg71	711	uint8 *dict = g_mppc_dict.hist;
68	n-ki	684
69			if ((ctype & RDP_MPPC_COMPRESSED) == 0)
70			{
71			*roff = 0;
72			*rlen = clen;
73			return 0;
74			}
75
76			if ((ctype & RDP_MPPC_RESET) != 0)
77			{
78	n-ki	687	g_mppc_dict.roff = 0;
79	n-ki	684	}
80
81			if ((ctype & RDP_MPPC_FLUSH) != 0)
82			{
83			memset(dict, 0, RDP_MPPC_DICT_SIZE);
84	n-ki	687	g_mppc_dict.roff = 0;
85	n-ki	684	}
86
87			*roff = 0;
88			*rlen = 0;
89
90	n-ki	687	walker = g_mppc_dict.roff;
91	n-ki	684
92			next_offset = walker;
93			old_offset = next_offset;
94			*roff = old_offset;
95			if (clen == 0)
96			return 0;
97			clen += i;
98
99			do
100			{
101			if (walker_len == 0)
102			{
103			if (i >= clen)
104			break;
105			walker = data[i++] << 24;
106			walker_len = 8;
107			}
108			if (walker >= 0)
109			{
110			if (walker_len < 8)
111			{
112			if (i >= clen)
113			{
114			if (walker != 0)
115			return -1;
116			break;
117			}
118			walker \|= (data[i++] & 0xff) << (24 - walker_len);
119			walker_len += 8;
120			}
121			if (next_offset >= RDP_MPPC_DICT_SIZE)
122			return -1;
123			dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
124			walker <<= 8;
125			walker_len -= 8;
126			continue;
127			}
128			walker <<= 1;
129			/* fetch next 8-bits */
130			if (--walker_len == 0)
131			{
132			if (i >= clen)
133			return -1;
134			walker = data[i++] << 24;
135			walker_len = 8;
136			}
137			/* literal decoding */
138			if (walker >= 0)
139			{
140			if (walker_len < 8)
141			{
142			if (i >= clen)
143			return -1;
144			walker \|= (data[i++] & 0xff) << (24 - walker_len);
145			walker_len += 8;
146			}
147			if (next_offset >= RDP_MPPC_DICT_SIZE)
148			return -1;
149			dict[next_offset++] = (uint8) (walker >> 24 \| 0x80);
150			walker <<= 8;
151			walker_len -= 8;
152			continue;
153			}
154
155			/* decode offset */
156			/* length pair */
157			walker <<= 1;
158	jdmeijer	889	if (--walker_len < (ctype & RDP_MPPC_BIG ? 3 : 2))
159	n-ki	684	{
160			if (i >= clen)
161			return -1;
162			walker \|= (data[i++] & 0xff) << (24 - walker_len);
163			walker_len += 8;
164			}
165	jdmeijer	889
166			if (ctype & RDP_MPPC_BIG)
167	n-ki	684	{
168	jdmeijer	889	/* offset decoding where offset len is:
169			-63: 11111 followed by the lower 6 bits of the value
170			64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
171			320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
172			2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
173			*/
174			switch (((uint32) walker) >> ((uint32) 29))
175			{
176			case 7: /* - 63 */
177			for (; walker_len < 9; walker_len += 8)
178			{
179			if (i >= clen)
180			return -1;
181			walker \|= (data[i++] & 0xff) << (24 - walker_len);
182			}
183			walker <<= 3;
184			match_off = ((uint32) walker) >> ((uint32) 26);
185			walker <<= 6;
186			walker_len -= 9;
187			break;
188	n-ki	684
189	jdmeijer	889	case 6: /* 64 - 319 */
190			for (; walker_len < 11; walker_len += 8)
191			{
192			if (i >= clen)
193			return -1;
194			walker \|= (data[i++] & 0xff) << (24 - walker_len);
195			}
196	n-ki	684
197	jdmeijer	889	walker <<= 3;
198			match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
199			walker <<= 8;
200			walker_len -= 11;
201			break;
202	n-ki	684
203	jdmeijer	889	case 5:
204			case 4: /* 320 - 2367 */
205			for (; walker_len < 13; walker_len += 8)
206			{
207			if (i >= clen)
208			return -1;
209			walker \|= (data[i++] & 0xff) << (24 - walker_len);
210			}
211	n-ki	684
212	jdmeijer	889	walker <<= 2;
213			match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
214			walker <<= 11;
215			walker_len -= 13;
216			break;
217
218			default: /* 2368 - 65535 */
219			for (; walker_len < 17; walker_len += 8)
220			{
221			if (i >= clen)
222			return -1;
223			walker \|= (data[i++] & 0xff) << (24 - walker_len);
224			}
225
226			walker <<= 1;
227			match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
228			walker <<= 16;
229			walker_len -= 17;
230			break;
231			}
232	n-ki	684	}
233	jdmeijer	889	else
234			{
235			/* offset decoding where offset len is:
236			-63: 1111 followed by the lower 6 bits of the value
237			64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
238			320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
239			*/
240			switch (((uint32) walker) >> ((uint32) 30))
241			{
242			case 3: /* - 63 */
243			if (walker_len < 8)
244			{
245			if (i >= clen)
246			return -1;
247			walker \|= (data[i++] & 0xff) << (24 - walker_len);
248			walker_len += 8;
249			}
250			walker <<= 2;
251			match_off = ((uint32) walker) >> ((uint32) 26);
252			walker <<= 6;
253			walker_len -= 8;
254			break;
255
256			case 2: /* 64 - 319 */
257			for (; walker_len < 10; walker_len += 8)
258			{
259			if (i >= clen)
260			return -1;
261			walker \|= (data[i++] & 0xff) << (24 - walker_len);
262			}
263
264			walker <<= 2;
265			match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
266			walker <<= 8;
267			walker_len -= 10;
268			break;
269
270			default: /* 320 - 8191 */
271			for (; walker_len < 14; walker_len += 8)
272			{
273			if (i >= clen)
274			return -1;
275			walker \|= (data[i++] & 0xff) << (24 - walker_len);
276			}
277
278			match_off = (walker >> 18) + 320;
279			walker <<= 14;
280			walker_len -= 14;
281			break;
282			}
283			}
284	n-ki	684	if (walker_len == 0)
285			{
286			if (i >= clen)
287			return -1;
288			walker = data[i++] << 24;
289			walker_len = 8;
290			}
291
292			/* decode length of match */
293			match_len = 0;
294			if (walker >= 0)
295			{ /* special case - length of 3 is in bit 0 */
296			match_len = 3;
297			walker <<= 1;
298			walker_len--;
299			}
300			else
301			{
302			/* this is how it works len of:
303			4-7: 10 followed by 2 bits of the value
304			8-15: 110 followed by 3 bits of the value
305			16-31: 1110 followed by 4 bits of the value
306			32-63: .... and so forth
307			64-127:
308			128-255:
309			256-511:
310			512-1023:
311			1024-2047:
312			2048-4095:
313			4096-8191:
314
315			i.e. 4097 is encoded as: 111111111110 000000000001
316			meaning 4096 + 1...
317			*/
318			match_bits = 11; /* 11 bits of value at most */
319			do
320			{
321			walker <<= 1;
322			if (--walker_len == 0)
323			{
324			if (i >= clen)
325			return -1;
326			walker = data[i++] << 24;
327			walker_len = 8;
328			}
329			if (walker >= 0)
330			break;
331			if (--match_bits == 0)
332			{
333			return -1;
334			}
335			}
336			while (1);
337			match_len = 13 - match_bits;
338			walker <<= 1;
339			if (--walker_len < match_len)
340			{
341			for (; walker_len < match_len; walker_len += 8)
342			{
343			if (i >= clen)
344			{
345			return -1;
346			}
347			walker \|= (data[i++] & 0xff) << (24 - walker_len);
348			}
349			}
350
351			match_bits = match_len;
352			match_len =
353	astrand	717	((walker >> (32 - match_bits)) & (~(-1 << match_bits))) \| (1 <<
354			match_bits);
355	n-ki	684	walker <<= match_bits;
356			walker_len -= match_bits;
357			}
358			if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
359			{
360			return -1;
361			}
362			/* memory areas can overlap - meaning we can't use memXXX functions */
363	jdmeijer	889	k = (next_offset - match_off) & (ctype & RDP_MPPC_BIG ? 65535 : 8191);
364	n-ki	684	do
365			{
366			dict[next_offset++] = dict[k++];
367			}
368			while (--match_len != 0);
369			}
370			while (1);
371
372			/* store history offset */
373	n-ki	687	g_mppc_dict.roff = next_offset;
374	n-ki	684
375			*roff = old_offset;
376			*rlen = next_offset - old_offset;
377
378			return 0;
379			}