rdesktop/trunk/mppc.c

/* -*- c-basic-offset: 8 -*-
   rdesktop: A Remote Desktop Protocol client.
   Protocol services - RDP decompression
   Copyright (C) Matthew Chapman 1999-2004

   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;
        int 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 < 2)
                {
                        if (i >= clen)
                                return -1;
                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                        walker_len += 8;
                }
                /* 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) & (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;
}
1	n-ki	689	/* -- c-basic-offset: 8 --
2			rdesktop: A Remote Desktop Protocol client.
3			Protocol services - RDP decompression
4			Copyright (C) Matthew Chapman 1999-2004
5
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			int i = 0;
63			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			if (--walker_len < 2)
159			{
160			if (i >= clen)
161			return -1;
162			walker \|= (data[i++] & 0xff) << (24 - walker_len);
163			walker_len += 8;
164			}
165			/* offset decoding where offset len is:
166			-63: 1111 followed by the lower 6 bits of the value
167			64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
168			320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
169			*/
170			switch (((uint32) walker) >> ((uint32) 30))
171			{
172			case 3: /* - 63 */
173			if (walker_len < 8)
174			{
175			if (i >= clen)
176			return -1;
177			walker \|= (data[i++] & 0xff) << (24 - walker_len);
178			walker_len += 8;
179			}
180			walker <<= 2;
181			match_off = ((uint32) walker) >> ((uint32) 26);
182			walker <<= 6;
183			walker_len -= 8;
184			break;
185
186			case 2: /* 64 - 319 */
187			for (; walker_len < 10; walker_len += 8)
188			{
189			if (i >= clen)
190			return -1;
191			walker \|= (data[i++] & 0xff) << (24 - walker_len);
192			}
193
194			walker <<= 2;
195			match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
196			walker <<= 8;
197			walker_len -= 10;
198			break;
199
200			default: /* 320 - 8191 */
201			for (; walker_len < 14; walker_len += 8)
202			{
203			if (i >= clen)
204			return -1;
205			walker \|= (data[i++] & 0xff) << (24 - walker_len);
206			}
207
208			match_off = (walker >> 18) + 320;
209			walker <<= 14;
210			walker_len -= 14;
211			break;
212			}
213			if (walker_len == 0)
214			{
215			if (i >= clen)
216			return -1;
217			walker = data[i++] << 24;
218			walker_len = 8;
219			}
220
221			/* decode length of match */
222			match_len = 0;
223			if (walker >= 0)
224			{ /* special case - length of 3 is in bit 0 */
225			match_len = 3;
226			walker <<= 1;
227			walker_len--;
228			}
229			else
230			{
231			/* this is how it works len of:
232			4-7: 10 followed by 2 bits of the value
233			8-15: 110 followed by 3 bits of the value
234			16-31: 1110 followed by 4 bits of the value
235			32-63: .... and so forth
236			64-127:
237			128-255:
238			256-511:
239			512-1023:
240			1024-2047:
241			2048-4095:
242			4096-8191:
243
244			i.e. 4097 is encoded as: 111111111110 000000000001
245			meaning 4096 + 1...
246			*/
247			match_bits = 11; /* 11 bits of value at most */
248			do
249			{
250			walker <<= 1;
251			if (--walker_len == 0)
252			{
253			if (i >= clen)
254			return -1;
255			walker = data[i++] << 24;
256			walker_len = 8;
257			}
258			if (walker >= 0)
259			break;
260			if (--match_bits == 0)
261			{
262			return -1;
263			}
264			}
265			while (1);
266			match_len = 13 - match_bits;
267			walker <<= 1;
268			if (--walker_len < match_len)
269			{
270			for (; walker_len < match_len; walker_len += 8)
271			{
272			if (i >= clen)
273			{
274			return -1;
275			}
276			walker \|= (data[i++] & 0xff) << (24 - walker_len);
277			}
278			}
279
280			match_bits = match_len;
281			match_len =
282	jsorg71	711	((walker >> (32 - match_bits)) & (~(-1 << match_bits))) \| (1 << match_bits);
283	n-ki	684	walker <<= match_bits;
284			walker_len -= match_bits;
285			}
286			if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
287			{
288			return -1;
289			}
290			/* memory areas can overlap - meaning we can't use memXXX functions */
291	jsorg71	711	k = (next_offset - match_off) & (RDP_MPPC_DICT_SIZE - 1);
292	n-ki	684	do
293			{
294			dict[next_offset++] = dict[k++];
295			}
296			while (--match_len != 0);
297			}
298			while (1);
299
300			/* store history offset */
301	n-ki	687	g_mppc_dict.roff = next_offset;
302	n-ki	684
303			*roff = old_offset;
304			*rlen = next_offset - old_offset;
305
306			return 0;
307			}