ReactOS 0.4.15-dev-7842-g558ab78
mppc.c
Go to the documentation of this file.
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 <stdio.h>
22#include <string.h>
23
24#include "rdesktop.h"
25
26/* mppc decompression */
27/* http://www.faqs.org/rfcs/rfc2118.html */
28
29/* Contacts: */
30
31/* hifn contact mentioned in the faq is */
32/* Robert Friend rfriend at hifn dot com */
33
34/* if you have questions regarding MPPC */
35/* our contact is */
36/* Guus Dhaeze GDhaeze at hifn dot com */
37
38/* Licensing: */
39
40/* decompression is alright as long as we */
41/* don't compress data */
42
43/* Algorithm: */
44
45/* as the rfc states the algorithm seems to */
46/* be LZ77 with a sliding buffer */
47/* that is empty at init. */
48
49/* the algorithm is called LZS and is */
50/* patented for another couple of years. */
51
52/* more information is available in */
53/* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
54
55int
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 = This->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 This->mppc_dict.roff = 0;
77 }
78
79 if ((ctype & RDP_MPPC_FLUSH) != 0)
80 {
81 memset(dict, 0, RDP_MPPC_DICT_SIZE);
82 This->mppc_dict.roff = 0;
83 }
84
85 *roff = 0;
86 *rlen = 0;
87
88 walker = This->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 This->mppc_dict.roff = next_offset;
372
373 *roff = old_offset;
374 *rlen = next_offset - old_offset;
375
376 return 0;
377}
#define RDP_MPPC_RESET
Definition: constants.h:356
#define RDP_MPPC_DICT_SIZE
Definition: constants.h:358
#define RDP_MPPC_COMPRESSED
Definition: constants.h:355
#define RDP_MPPC_BIG
Definition: constants.h:354
#define RDP_MPPC_FLUSH
Definition: constants.h:357
int mppc_expand(uint8 *data, uint32 clen, uint8 ctype, uint32 *roff, uint32 *rlen)
Definition: mppc.c:58
unsigned int uint32
Definition: types.h:32
#define False
Definition: types.h:25
#define True
Definition: types.h:24
unsigned char uint8
Definition: types.h:28
Definition: _ctype.h:58
unsigned int BOOL
Definition: ntddk_ex.h:94
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
int k
Definition: mpi.c:3369
#define memset(x, y, z)
Definition: compat.h:39