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;
        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;
}
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	jdmeijer	899	BOOL big = ctype & RDP_MPPC_BIG ? True : False;
67	n-ki	684
68	jsorg71	711	uint8 *dict = g_mppc_dict.hist;
69	n-ki	684
70			if ((ctype & RDP_MPPC_COMPRESSED) == 0)
71			{
72			*roff = 0;
73			*rlen = clen;
74			return 0;
75			}
76
77			if ((ctype & RDP_MPPC_RESET) != 0)
78			{
79	n-ki	687	g_mppc_dict.roff = 0;
80	n-ki	684	}
81
82			if ((ctype & RDP_MPPC_FLUSH) != 0)
83			{
84			memset(dict, 0, RDP_MPPC_DICT_SIZE);
85	n-ki	687	g_mppc_dict.roff = 0;
86	n-ki	684	}
87
88			*roff = 0;
89			*rlen = 0;
90
91	n-ki	687	walker = g_mppc_dict.roff;
92	n-ki	684
93			next_offset = walker;
94			old_offset = next_offset;
95			*roff = old_offset;
96			if (clen == 0)
97			return 0;
98			clen += i;
99
100			do
101			{
102			if (walker_len == 0)
103			{
104			if (i >= clen)
105			break;
106			walker = data[i++] << 24;
107			walker_len = 8;
108			}
109			if (walker >= 0)
110			{
111			if (walker_len < 8)
112			{
113			if (i >= clen)
114			{
115			if (walker != 0)
116			return -1;
117			break;
118			}
119			walker \|= (data[i++] & 0xff) << (24 - walker_len);
120			walker_len += 8;
121			}
122			if (next_offset >= RDP_MPPC_DICT_SIZE)
123			return -1;
124			dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
125			walker <<= 8;
126			walker_len -= 8;
127			continue;
128			}
129			walker <<= 1;
130			/* fetch next 8-bits */
131			if (--walker_len == 0)
132			{
133			if (i >= clen)
134			return -1;
135			walker = data[i++] << 24;
136			walker_len = 8;
137			}
138			/* literal decoding */
139			if (walker >= 0)
140			{
141			if (walker_len < 8)
142			{
143			if (i >= clen)
144			return -1;
145			walker \|= (data[i++] & 0xff) << (24 - walker_len);
146			walker_len += 8;
147			}
148			if (next_offset >= RDP_MPPC_DICT_SIZE)
149			return -1;
150			dict[next_offset++] = (uint8) (walker >> 24 \| 0x80);
151			walker <<= 8;
152			walker_len -= 8;
153			continue;
154			}
155
156			/* decode offset */
157			/* length pair */
158			walker <<= 1;
159	jdmeijer	899	if (--walker_len < (big ? 3 : 2))
160	n-ki	684	{
161			if (i >= clen)
162			return -1;
163			walker \|= (data[i++] & 0xff) << (24 - walker_len);
164			walker_len += 8;
165			}
166	jdmeijer	889
167	jdmeijer	899	if (big)
168	n-ki	684	{
169	jdmeijer	889	/* offset decoding where offset len is:
170			-63: 11111 followed by the lower 6 bits of the value
171			64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
172			320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
173			2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
174			*/
175			switch (((uint32) walker) >> ((uint32) 29))
176			{
177			case 7: /* - 63 */
178			for (; walker_len < 9; walker_len += 8)
179			{
180			if (i >= clen)
181			return -1;
182			walker \|= (data[i++] & 0xff) << (24 - walker_len);
183			}
184			walker <<= 3;
185			match_off = ((uint32) walker) >> ((uint32) 26);
186			walker <<= 6;
187			walker_len -= 9;
188			break;
189	n-ki	684
190	jdmeijer	889	case 6: /* 64 - 319 */
191			for (; walker_len < 11; walker_len += 8)
192			{
193			if (i >= clen)
194			return -1;
195			walker \|= (data[i++] & 0xff) << (24 - walker_len);
196			}
197	n-ki	684
198	jdmeijer	889	walker <<= 3;
199			match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
200			walker <<= 8;
201			walker_len -= 11;
202			break;
203	n-ki	684
204	jdmeijer	889	case 5:
205			case 4: /* 320 - 2367 */
206			for (; walker_len < 13; walker_len += 8)
207			{
208			if (i >= clen)
209			return -1;
210			walker \|= (data[i++] & 0xff) << (24 - walker_len);
211			}
212	n-ki	684
213	jdmeijer	889	walker <<= 2;
214			match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
215			walker <<= 11;
216			walker_len -= 13;
217			break;
218
219			default: /* 2368 - 65535 */
220			for (; walker_len < 17; walker_len += 8)
221			{
222			if (i >= clen)
223			return -1;
224			walker \|= (data[i++] & 0xff) << (24 - walker_len);
225			}
226
227			walker <<= 1;
228			match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
229			walker <<= 16;
230			walker_len -= 17;
231			break;
232			}
233	n-ki	684	}
234	jdmeijer	889	else
235			{
236			/* offset decoding where offset len is:
237			-63: 1111 followed by the lower 6 bits of the value
238			64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
239			320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
240			*/
241			switch (((uint32) walker) >> ((uint32) 30))
242			{
243			case 3: /* - 63 */
244			if (walker_len < 8)
245			{
246			if (i >= clen)
247			return -1;
248			walker \|= (data[i++] & 0xff) << (24 - walker_len);
249			walker_len += 8;
250			}
251			walker <<= 2;
252			match_off = ((uint32) walker) >> ((uint32) 26);
253			walker <<= 6;
254			walker_len -= 8;
255			break;
256
257			case 2: /* 64 - 319 */
258			for (; walker_len < 10; walker_len += 8)
259			{
260			if (i >= clen)
261			return -1;
262			walker \|= (data[i++] & 0xff) << (24 - walker_len);
263			}
264
265			walker <<= 2;
266			match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
267			walker <<= 8;
268			walker_len -= 10;
269			break;
270
271			default: /* 320 - 8191 */
272			for (; walker_len < 14; walker_len += 8)
273			{
274			if (i >= clen)
275			return -1;
276			walker \|= (data[i++] & 0xff) << (24 - walker_len);
277			}
278
279			match_off = (walker >> 18) + 320;
280			walker <<= 14;
281			walker_len -= 14;
282			break;
283			}
284			}
285	n-ki	684	if (walker_len == 0)
286			{
287			if (i >= clen)
288			return -1;
289			walker = data[i++] << 24;
290			walker_len = 8;
291			}
292
293			/* decode length of match */
294			match_len = 0;
295			if (walker >= 0)
296			{ /* special case - length of 3 is in bit 0 */
297			match_len = 3;
298			walker <<= 1;
299			walker_len--;
300			}
301			else
302			{
303			/* this is how it works len of:
304			4-7: 10 followed by 2 bits of the value
305			8-15: 110 followed by 3 bits of the value
306			16-31: 1110 followed by 4 bits of the value
307			32-63: .... and so forth
308			64-127:
309			128-255:
310			256-511:
311			512-1023:
312			1024-2047:
313			2048-4095:
314			4096-8191:
315
316			i.e. 4097 is encoded as: 111111111110 000000000001
317			meaning 4096 + 1...
318			*/
319	jdmeijer	899	match_bits = big ? 14 : 11; /* 11 or 14 bits of value at most */
320	n-ki	684	do
321			{
322			walker <<= 1;
323			if (--walker_len == 0)
324			{
325			if (i >= clen)
326			return -1;
327			walker = data[i++] << 24;
328			walker_len = 8;
329			}
330			if (walker >= 0)
331			break;
332			if (--match_bits == 0)
333			{
334			return -1;
335			}
336			}
337			while (1);
338	jdmeijer	899	match_len = (big ? 16 : 13) - match_bits;
339	n-ki	684	walker <<= 1;
340			if (--walker_len < match_len)
341			{
342			for (; walker_len < match_len; walker_len += 8)
343			{
344			if (i >= clen)
345			{
346			return -1;
347			}
348			walker \|= (data[i++] & 0xff) << (24 - walker_len);
349			}
350			}
351
352			match_bits = match_len;
353			match_len =
354	astrand	717	((walker >> (32 - match_bits)) & (~(-1 << match_bits))) \| (1 <<
355			match_bits);
356	n-ki	684	walker <<= match_bits;
357			walker_len -= match_bits;
358			}
359			if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
360			{
361			return -1;
362			}
363			/* memory areas can overlap - meaning we can't use memXXX functions */
364	jdmeijer	899	k = (next_offset - match_off) & (big ? 65535 : 8191);
365	n-ki	684	do
366			{
367			dict[next_offset++] = dict[k++];
368			}
369			while (--match_len != 0);
370			}
371			while (1);
372
373			/* store history offset */
374	n-ki	687	g_mppc_dict.roff = next_offset;
375	n-ki	684
376			*roff = old_offset;
377			*rlen = next_offset - old_offset;
378
379			return 0;
380			}