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