trunk/rdesktop/mppc.c

#include <stdio.h>
#include <string.h>

#include "rdesktop.h"

/* mppc decompression                       */
/* http://www.faqs.org/rfcs/rfc2118.html    */

/* TODO: research the below statements      */

/* there exists one or more patents         */
/* related to compression algorithms        */

/* since we are only decompressing I        */
/* think the end-user is safe.              */

/* even if that isn't true, aren't you      */
/* already paying royalties                 */
/* through the CAL licenses?                */

/* as the rfc states the algorithm seems to */
/* be LZ77 with a sliding buffer            */
/* that is empty at init.                   */

/* as of my limited knowledge these patents */
/* has expired.                             */


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;

        signed char *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	684	#include <stdio.h>
2			#include <string.h>
3
4			#include "rdesktop.h"
5
6	n-ki	687	/* mppc decompression */
7	n-ki	684	/* http://www.faqs.org/rfcs/rfc2118.html */
8
9			/* TODO: research the below statements */
10
11			/* there exists one or more patents */
12			/* related to compression algorithms */
13
14			/* since we are only decompressing I */
15			/* think the end-user is safe. */
16
17			/* even if that isn't true, aren't you */
18			/* already paying royalties */
19			/* through the CAL licenses? */
20
21	n-ki	687	/* as the rfc states the algorithm seems to */
22			/* be LZ77 with a sliding buffer */
23			/* that is empty at init. */
24	n-ki	684
25	n-ki	687	/* as of my limited knowledge these patents */
26			/* has expired. */
27	n-ki	684
28
29	n-ki	687	RDPCOMP g_mppc_dict;
30
31	n-ki	684	int
32			mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen)
33			{
34			int k, walker_len = 0, walker;
35			int i = 0;
36			int next_offset, match_off;
37			int match_len;
38			int old_offset, match_bits;
39
40	n-ki	687	signed char *dict = &(g_mppc_dict.hist);
41	n-ki	684
42			if ((ctype & RDP_MPPC_COMPRESSED) == 0)
43			{
44			*roff = 0;
45			*rlen = clen;
46			return 0;
47			}
48
49			if ((ctype & RDP_MPPC_RESET) != 0)
50			{
51	n-ki	687	g_mppc_dict.roff = 0;
52	n-ki	684	}
53
54			if ((ctype & RDP_MPPC_FLUSH) != 0)
55			{
56			memset(dict, 0, RDP_MPPC_DICT_SIZE);
57	n-ki	687	g_mppc_dict.roff = 0;
58	n-ki	684	}
59
60			*roff = 0;
61			*rlen = 0;
62
63	n-ki	687	walker = g_mppc_dict.roff;
64	n-ki	684
65			next_offset = walker;
66			old_offset = next_offset;
67			*roff = old_offset;
68			if (clen == 0)
69			return 0;
70			clen += i;
71
72			do
73			{
74			if (walker_len == 0)
75			{
76			if (i >= clen)
77			break;
78			walker = data[i++] << 24;
79			walker_len = 8;
80			}
81			if (walker >= 0)
82			{
83			if (walker_len < 8)
84			{
85			if (i >= clen)
86			{
87			if (walker != 0)
88			return -1;
89			break;
90			}
91			walker \|= (data[i++] & 0xff) << (24 - walker_len);
92			walker_len += 8;
93			}
94			if (next_offset >= RDP_MPPC_DICT_SIZE)
95			return -1;
96			dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
97			walker <<= 8;
98			walker_len -= 8;
99			continue;
100			}
101			walker <<= 1;
102			/* fetch next 8-bits */
103			if (--walker_len == 0)
104			{
105			if (i >= clen)
106			return -1;
107			walker = data[i++] << 24;
108			walker_len = 8;
109			}
110			/* literal decoding */
111			if (walker >= 0)
112			{
113			if (walker_len < 8)
114			{
115			if (i >= clen)
116			return -1;
117			walker \|= (data[i++] & 0xff) << (24 - walker_len);
118			walker_len += 8;
119			}
120			if (next_offset >= RDP_MPPC_DICT_SIZE)
121			return -1;
122			dict[next_offset++] = (uint8) (walker >> 24 \| 0x80);
123			walker <<= 8;
124			walker_len -= 8;
125			continue;
126			}
127
128			/* decode offset */
129			/* length pair */
130			walker <<= 1;
131			if (--walker_len < 2)
132			{
133			if (i >= clen)
134			return -1;
135			walker \|= (data[i++] & 0xff) << (24 - walker_len);
136			walker_len += 8;
137			}
138			/* offset decoding where offset len is:
139			-63: 1111 followed by the lower 6 bits of the value
140			64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
141			320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
142			*/
143			switch (((uint32) walker) >> ((uint32) 30))
144			{
145			case 3: /* - 63 */
146			if (walker_len < 8)
147			{
148			if (i >= clen)
149			return -1;
150			walker \|= (data[i++] & 0xff) << (24 - walker_len);
151			walker_len += 8;
152			}
153			walker <<= 2;
154			match_off = ((uint32) walker) >> ((uint32) 26);
155			walker <<= 6;
156			walker_len -= 8;
157			break;
158
159			case 2: /* 64 - 319 */
160			for (; walker_len < 10; walker_len += 8)
161			{
162			if (i >= clen)
163			return -1;
164			walker \|= (data[i++] & 0xff) << (24 - walker_len);
165			}
166
167			walker <<= 2;
168			match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
169			walker <<= 8;
170			walker_len -= 10;
171			break;
172
173			default: /* 320 - 8191 */
174			for (; walker_len < 14; walker_len += 8)
175			{
176			if (i >= clen)
177			return -1;
178			walker \|= (data[i++] & 0xff) << (24 - walker_len);
179			}
180
181			match_off = (walker >> 18) + 320;
182			walker <<= 14;
183			walker_len -= 14;
184			break;
185			}
186			if (walker_len == 0)
187			{
188			if (i >= clen)
189			return -1;
190			walker = data[i++] << 24;
191			walker_len = 8;
192			}
193
194			/* decode length of match */
195			match_len = 0;
196			if (walker >= 0)
197			{ /* special case - length of 3 is in bit 0 */
198			match_len = 3;
199			walker <<= 1;
200			walker_len--;
201			}
202			else
203			{
204			/* this is how it works len of:
205			4-7: 10 followed by 2 bits of the value
206			8-15: 110 followed by 3 bits of the value
207			16-31: 1110 followed by 4 bits of the value
208			32-63: .... and so forth
209			64-127:
210			128-255:
211			256-511:
212			512-1023:
213			1024-2047:
214			2048-4095:
215			4096-8191:
216
217			i.e. 4097 is encoded as: 111111111110 000000000001
218			meaning 4096 + 1...
219			*/
220			match_bits = 11; /* 11 bits of value at most */
221			do
222			{
223			walker <<= 1;
224			if (--walker_len == 0)
225			{
226			if (i >= clen)
227			return -1;
228			walker = data[i++] << 24;
229			walker_len = 8;
230			}
231			if (walker >= 0)
232			break;
233			if (--match_bits == 0)
234			{
235			return -1;
236			}
237			}
238			while (1);
239			match_len = 13 - match_bits;
240			walker <<= 1;
241			if (--walker_len < match_len)
242			{
243			for (; walker_len < match_len; walker_len += 8)
244			{
245			if (i >= clen)
246			{
247			return -1;
248			}
249			walker \|= (data[i++] & 0xff) << (24 - walker_len);
250			}
251			}
252
253			match_bits = match_len;
254			match_len =
255			walker >> 32 - match_bits & ~(-1 << match_bits) \| 1 << match_bits;
256			walker <<= match_bits;
257			walker_len -= match_bits;
258			}
259			if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
260			{
261			return -1;
262			}
263			/* memory areas can overlap - meaning we can't use memXXX functions */
264			k = next_offset - match_off & (RDP_MPPC_DICT_SIZE - 1);
265			do
266			{
267			dict[next_offset++] = dict[k++];
268			}
269			while (--match_len != 0);
270			}
271			while (1);
272
273			/* store history offset */
274	n-ki	687	g_mppc_dict.roff = next_offset;
275	n-ki	684
276			*roff = old_offset;
277			*rlen = next_offset - old_offset;
278
279			return 0;
280			}