--- sourceforge.net/trunk/rdesktop/mppc.c 2004/04/27 13:05:32 684 +++ sourceforge.net/trunk/rdesktop/mppc.c 2005/04/30 20:48:05 899 @@ -1,39 +1,71 @@ +/* -*- c-basic-offset: 8 -*- + rdesktop: A Remote Desktop Protocol client. + Protocol services - RDP decompression + Copyright (C) Matthew Chapman 1999-2005 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + #include #include #include "rdesktop.h" -/* mppc-like??? decompression */ +/* mppc decompression */ /* http://www.faqs.org/rfcs/rfc2118.html */ -/* TODO: research the below statements */ +/* Contacts: */ + +/* hifn contact mentioned in the faq is */ +/* Robert Friend rfriend at hifn dot com */ + +/* if you have questions regarding MPPC */ +/* our contact is */ +/* Guus Dhaeze GDhaeze at hifn dot com */ + +/* Licensing: */ -/* there exists one or more patents */ -/* related to compression algorithms */ +/* decompression is alright as long as we */ +/* don't compress data */ -/* since we are only decompressing I */ -/* think the end-user is safe. */ +/* Algorithm: */ -/* even if that isn't true, aren't you */ -/* already paying royalties */ -/* through the CAL licenses? */ +/* as the rfc states the algorithm seems to */ +/* be LZ77 with a sliding buffer */ +/* that is empty at init. */ -/* the dictionary is empty when init. like */ -/* LZ78, which is not patented */ +/* the algorithm is called LZS and is */ +/* patented for another couple of years. */ +/* more information is available in */ +/* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */ -RDPCOMP mppc_dict; + +RDPCOMP g_mppc_dict; int mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen) { int k, walker_len = 0, walker; - int i = 0; + uint32 i = 0; int next_offset, match_off; int match_len; int old_offset, match_bits; + BOOL big = ctype & RDP_MPPC_BIG ? True : False; - signed char *dict = &(mppc_dict.hist); + uint8 *dict = g_mppc_dict.hist; if ((ctype & RDP_MPPC_COMPRESSED) == 0) { @@ -44,19 +76,19 @@ if ((ctype & RDP_MPPC_RESET) != 0) { - mppc_dict.roff = 0; + g_mppc_dict.roff = 0; } if ((ctype & RDP_MPPC_FLUSH) != 0) { memset(dict, 0, RDP_MPPC_DICT_SIZE); - mppc_dict.roff = 0; + g_mppc_dict.roff = 0; } *roff = 0; *rlen = 0; - walker = mppc_dict.roff; + walker = g_mppc_dict.roff; next_offset = walker; old_offset = next_offset; @@ -124,60 +156,131 @@ /* decode offset */ /* length pair */ walker <<= 1; - if (--walker_len < 2) + if (--walker_len < (big ? 3 : 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)) + + if (big) { - 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; + /* offset decoding where offset len is: + -63: 11111 followed by the lower 6 bits of the value + 64-319: 11110 followed by the lower 8 bits of the value ( value - 64 ) + 320-2367: 1110 followed by lower 11 bits of the value ( value - 320 ) + 2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 ) + */ + switch (((uint32) walker) >> ((uint32) 29)) + { + case 7: /* - 63 */ + for (; walker_len < 9; walker_len += 8) + { + if (i >= clen) + return -1; + walker |= (data[i++] & 0xff) << (24 - walker_len); + } + walker <<= 3; + match_off = ((uint32) walker) >> ((uint32) 26); + walker <<= 6; + walker_len -= 9; + break; - case 2: /* 64 - 319 */ - for (; walker_len < 10; walker_len += 8) - { - if (i >= clen) - return -1; - walker |= (data[i++] & 0xff) << (24 - walker_len); - } + case 6: /* 64 - 319 */ + for (; walker_len < 11; 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; + walker <<= 3; + match_off = (((uint32) walker) >> ((uint32) 24)) + 64; + walker <<= 8; + walker_len -= 11; + break; - default: /* 320 - 8191 */ - for (; walker_len < 14; walker_len += 8) - { - if (i >= clen) - return -1; - walker |= (data[i++] & 0xff) << (24 - walker_len); - } + case 5: + case 4: /* 320 - 2367 */ + for (; walker_len < 13; 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; + walker <<= 2; + match_off = (((uint32) walker) >> ((uint32) 21)) + 320; + walker <<= 11; + walker_len -= 13; + break; + + default: /* 2368 - 65535 */ + for (; walker_len < 17; walker_len += 8) + { + if (i >= clen) + return -1; + walker |= (data[i++] & 0xff) << (24 - walker_len); + } + + walker <<= 1; + match_off = (((uint32) walker) >> ((uint32) 16)) + 2368; + walker <<= 16; + walker_len -= 17; + break; + } + } + else + { + /* 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) { @@ -213,7 +316,7 @@ i.e. 4097 is encoded as: 111111111110 000000000001 meaning 4096 + 1... */ - match_bits = 11; /* 11 bits of value at most */ + match_bits = big ? 14 : 11; /* 11 or 14 bits of value at most */ do { walker <<= 1; @@ -232,7 +335,7 @@ } } while (1); - match_len = 13 - match_bits; + match_len = (big ? 16 : 13) - match_bits; walker <<= 1; if (--walker_len < match_len) { @@ -248,7 +351,8 @@ match_bits = match_len; match_len = - walker >> 32 - match_bits & ~(-1 << match_bits) | 1 << match_bits; + ((walker >> (32 - match_bits)) & (~(-1 << match_bits))) | (1 << + match_bits); walker <<= match_bits; walker_len -= match_bits; } @@ -257,7 +361,7 @@ return -1; } /* memory areas can overlap - meaning we can't use memXXX functions */ - k = next_offset - match_off & (RDP_MPPC_DICT_SIZE - 1); + k = (next_offset - match_off) & (big ? 65535 : 8191); do { dict[next_offset++] = dict[k++]; @@ -267,7 +371,7 @@ while (1); /* store history offset */ - mppc_dict.roff = next_offset; + g_mppc_dict.roff = next_offset; *roff = old_offset; *rlen = next_offset - old_offset;