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 
55 int
56 mppc_expand(RDPCLIENT * This, 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 = 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 }
378