trunk/rdesktop/mppc.c

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

#include "rdesktop.h"

/* mppc-like??? 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?                */

/* the dictionary is empty when init. like  */
/* LZ78,  which is not patented             */


RDPCOMP 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 = &(mppc_dict.hist);

        if ((ctype & RDP_MPPC_COMPRESSED) == 0)
        {
                *roff = 0;
                *rlen = clen;
                return 0;
        }

        if ((ctype & RDP_MPPC_RESET) != 0)
        {
                mppc_dict.roff = 0;
        }

        if ((ctype & RDP_MPPC_FLUSH) != 0)
        {
                memset(dict, 0, RDP_MPPC_DICT_SIZE);
                mppc_dict.roff = 0;
        }

        *roff = 0;
        *rlen = 0;

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