ReactOS 0.4.15-dev-5666-gc548b97
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 <matthewc.unsw.edu.au> 1999-2008
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 3 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, see <http://www.gnu.org/licenses/>.
18*/
19
20#include <stdio.h>
21#include <string.h>
22
23#include "precomp.h"
24
25/* mppc decompression */
26/* http://www.faqs.org/rfcs/rfc2118.html */
27
28/* Contacts: */
29
30/* hifn contact mentioned in the faq is */
31/* Robert Friend rfriend at hifn dot com */
32
33/* if you have questions regarding MPPC */
34/* our contact is */
35/* Guus Dhaeze GDhaeze at hifn dot com */
36
37/* Licensing: */
38
39/* decompression is alright as long as we */
40/* don't compress data */
41
42/* Algorithm: */
43
44/* as the rfc states the algorithm seems to */
45/* be LZ77 with a sliding buffer */
46/* that is empty at init. */
47
48/* the algorithm is called LZS and is */
49/* patented for another couple of years. */
50
51/* more information is available in */
52/* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
53
54
56
57int
59{
60 int k, walker_len = 0, walker;
61 uint32 i = 0;
62 int next_offset, match_off;
63 int match_len;
64 int old_offset, match_bits;
66
67 uint8 *dict = g_mppc_dict.hist;
68
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 g_mppc_dict.roff = 0;
79 }
80
81 if ((ctype & RDP_MPPC_FLUSH) != 0)
82 {
83 memset(dict, 0, RDP_MPPC_DICT_SIZE);
84 g_mppc_dict.roff = 0;
85 }
86
87 *roff = 0;
88 *rlen = 0;
89
90 walker = g_mppc_dict.roff;
91
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 < (big ? 3 : 2))
159 {
160 if (i >= clen)
161 return -1;
162 walker |= (data[i++] & 0xff) << (24 - walker_len);
163 walker_len += 8;
164 }
165
166 if (big)
167 {
168 /* offset decoding where offset len is:
169 -63: 11111 followed by the lower 6 bits of the value
170 64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
171 320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
172 2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
173 */
174 switch (((uint32) walker) >> ((uint32) 29))
175 {
176 case 7: /* - 63 */
177 for (; walker_len < 9; walker_len += 8)
178 {
179 if (i >= clen)
180 return -1;
181 walker |= (data[i++] & 0xff) << (24 - walker_len);
182 }
183 walker <<= 3;
184 match_off = ((uint32) walker) >> ((uint32) 26);
185 walker <<= 6;
186 walker_len -= 9;
187 break;
188
189 case 6: /* 64 - 319 */
190 for (; walker_len < 11; walker_len += 8)
191 {
192 if (i >= clen)
193 return -1;
194 walker |= (data[i++] & 0xff) << (24 - walker_len);
195 }
196
197 walker <<= 3;
198 match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
199 walker <<= 8;
200 walker_len -= 11;
201 break;
202
203 case 5:
204 case 4: /* 320 - 2367 */
205 for (; walker_len < 13; walker_len += 8)
206 {
207 if (i >= clen)
208 return -1;
209 walker |= (data[i++] & 0xff) << (24 - walker_len);
210 }
211
212 walker <<= 2;
213 match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
214 walker <<= 11;
215 walker_len -= 13;
216 break;
217
218 default: /* 2368 - 65535 */
219 for (; walker_len < 17; walker_len += 8)
220 {
221 if (i >= clen)
222 return -1;
223 walker |= (data[i++] & 0xff) << (24 - walker_len);
224 }
225
226 walker <<= 1;
227 match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
228 walker <<= 16;
229 walker_len -= 17;
230 break;
231 }
232 }
233 else
234 {
235 /* offset decoding where offset len is:
236 -63: 1111 followed by the lower 6 bits of the value
237 64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
238 320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
239 */
240 switch (((uint32) walker) >> ((uint32) 30))
241 {
242 case 3: /* - 63 */
243 if (walker_len < 8)
244 {
245 if (i >= clen)
246 return -1;
247 walker |= (data[i++] & 0xff) << (24 - walker_len);
248 walker_len += 8;
249 }
250 walker <<= 2;
251 match_off = ((uint32) walker) >> ((uint32) 26);
252 walker <<= 6;
253 walker_len -= 8;
254 break;
255
256 case 2: /* 64 - 319 */
257 for (; walker_len < 10; walker_len += 8)
258 {
259 if (i >= clen)
260 return -1;
261 walker |= (data[i++] & 0xff) << (24 - walker_len);
262 }
263
264 walker <<= 2;
265 match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
266 walker <<= 8;
267 walker_len -= 10;
268 break;
269
270 default: /* 320 - 8191 */
271 for (; walker_len < 14; walker_len += 8)
272 {
273 if (i >= clen)
274 return -1;
275 walker |= (data[i++] & 0xff) << (24 - walker_len);
276 }
277
278 match_off = (walker >> 18) + 320;
279 walker <<= 14;
280 walker_len -= 14;
281 break;
282 }
283 }
284 if (walker_len == 0)
285 {
286 if (i >= clen)
287 return -1;
288 walker = data[i++] << 24;
289 walker_len = 8;
290 }
291
292 /* decode length of match */
293 match_len = 0;
294 if (walker >= 0)
295 { /* special case - length of 3 is in bit 0 */
296 match_len = 3;
297 walker <<= 1;
298 walker_len--;
299 }
300 else
301 {
302 /* this is how it works len of:
303 4-7: 10 followed by 2 bits of the value
304 8-15: 110 followed by 3 bits of the value
305 16-31: 1110 followed by 4 bits of the value
306 32-63: .... and so forth
307 64-127:
308 128-255:
309 256-511:
310 512-1023:
311 1024-2047:
312 2048-4095:
313 4096-8191:
314
315 i.e. 4097 is encoded as: 111111111110 000000000001
316 meaning 4096 + 1...
317 */
318 match_bits = big ? 14 : 11; /* 11 or 14 bits of value at most */
319 do
320 {
321 walker <<= 1;
322 if (--walker_len == 0)
323 {
324 if (i >= clen)
325 return -1;
326 walker = data[i++] << 24;
327 walker_len = 8;
328 }
329 if (walker >= 0)
330 break;
331 if (--match_bits == 0)
332 {
333 return -1;
334 }
335 }
336 while (1);
337 match_len = (big ? 16 : 13) - match_bits;
338 walker <<= 1;
339 if (--walker_len < match_len)
340 {
341 for (; walker_len < match_len; walker_len += 8)
342 {
343 if (i >= clen)
344 {
345 return -1;
346 }
347 walker |= (data[i++] & 0xff) << (24 - walker_len);
348 }
349 }
350
351 match_bits = match_len;
352 match_len =
353 ((walker >> (32 - match_bits)) & (~(-1 << match_bits))) | (1 <<
354 match_bits);
355 walker <<= match_bits;
356 walker_len -= match_bits;
357 }
358 if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
359 {
360 return -1;
361 }
362 /* memory areas can overlap - meaning we can't use memXXX functions */
363 k = (next_offset - match_off) & (big ? 65535 : 8191);
364 do
365 {
366 dict[next_offset++] = dict[k++];
367 }
368 while (--match_len != 0);
369 }
370 while (1);
371
372 /* store history offset */
373 g_mppc_dict.roff = next_offset;
374
375 *roff = old_offset;
376 *rlen = next_offset - old_offset;
377
378 return 0;
379}
#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
RDPCOMP g_mppc_dict
Definition: mppc.c:55
unsigned int uint32
Definition: types.h:32
#define False
Definition: types.h:25
int RD_BOOL
Definition: types.h:21
#define True
Definition: types.h:24
unsigned char uint8
Definition: types.h:28
Definition: _ctype.h:58
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
uint32 roff
Definition: types.h:190
uint8 hist[RDP_MPPC_DICT_SIZE]
Definition: types.h:191