/* -*- 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 decompression */ /* http://www.faqs.org/rfcs/rfc2118.html */ /* 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: */ /* decompression is alright as long as we */ /* don't compress data */ /* Algorithm: */ /* as the rfc states the algorithm seems to */ /* be LZ77 with a sliding buffer */ /* that is empty at init. */ /* 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 g_mppc_dict; int mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen) { int k, walker_len = 0, walker; uint32 i = 0; int next_offset, match_off; int match_len; int old_offset, match_bits; BOOL big = ctype & RDP_MPPC_BIG ? True : False; uint8 *dict = g_mppc_dict.hist; if ((ctype & RDP_MPPC_COMPRESSED) == 0) { *roff = 0; *rlen = clen; return 0; } if ((ctype & RDP_MPPC_RESET) != 0) { g_mppc_dict.roff = 0; } if ((ctype & RDP_MPPC_FLUSH) != 0) { memset(dict, 0, RDP_MPPC_DICT_SIZE); g_mppc_dict.roff = 0; } *roff = 0; *rlen = 0; walker = g_mppc_dict.roff; next_offset = walker; old_offset = next_offset; *roff = old_offset; if (clen == 0) return 0; clen += i; do { if (walker_len == 0) { if (i >= clen) break; walker = data[i++] << 24; walker_len = 8; } if (walker >= 0) { if (walker_len < 8) { if (i >= clen) { if (walker != 0) return -1; break; } walker |= (data[i++] & 0xff) << (24 - walker_len); walker_len += 8; } if (next_offset >= RDP_MPPC_DICT_SIZE) return -1; dict[next_offset++] = (((uint32) walker) >> ((uint32) 24)); walker <<= 8; walker_len -= 8; continue; } walker <<= 1; /* fetch next 8-bits */ if (--walker_len == 0) { if (i >= clen) return -1; walker = data[i++] << 24; walker_len = 8; } /* literal decoding */ if (walker >= 0) { if (walker_len < 8) { if (i >= clen) return -1; walker |= (data[i++] & 0xff) << (24 - walker_len); walker_len += 8; } if (next_offset >= RDP_MPPC_DICT_SIZE) return -1; dict[next_offset++] = (uint8) (walker >> 24 | 0x80); walker <<= 8; walker_len -= 8; continue; } /* decode offset */ /* length pair */ walker <<= 1; if (--walker_len < (big ? 3 : 2)) { if (i >= clen) return -1; walker |= (data[i++] & 0xff) << (24 - walker_len); walker_len += 8; } if (big) { /* 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 6: /* 64 - 319 */ for (; walker_len < 11; walker_len += 8) { if (i >= clen) return -1; walker |= (data[i++] & 0xff) << (24 - walker_len); } walker <<= 3; match_off = (((uint32) walker) >> ((uint32) 24)) + 64; walker <<= 8; walker_len -= 11; break; 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); } 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) { if (i >= clen) return -1; walker = data[i++] << 24; walker_len = 8; } /* decode length of match */ match_len = 0; if (walker >= 0) { /* special case - length of 3 is in bit 0 */ match_len = 3; walker <<= 1; walker_len--; } else { /* this is how it works len of: 4-7: 10 followed by 2 bits of the value 8-15: 110 followed by 3 bits of the value 16-31: 1110 followed by 4 bits of the value 32-63: .... and so forth 64-127: 128-255: 256-511: 512-1023: 1024-2047: 2048-4095: 4096-8191: i.e. 4097 is encoded as: 111111111110 000000000001 meaning 4096 + 1... */ match_bits = big ? 14 : 11; /* 11 or 14 bits of value at most */ do { walker <<= 1; if (--walker_len == 0) { if (i >= clen) return -1; walker = data[i++] << 24; walker_len = 8; } if (walker >= 0) break; if (--match_bits == 0) { return -1; } } while (1); match_len = (big ? 16 : 13) - match_bits; walker <<= 1; if (--walker_len < match_len) { for (; walker_len < match_len; walker_len += 8) { if (i >= clen) { return -1; } walker |= (data[i++] & 0xff) << (24 - walker_len); } } match_bits = match_len; match_len = ((walker >> (32 - match_bits)) & (~(-1 << match_bits))) | (1 << match_bits); walker <<= match_bits; walker_len -= match_bits; } if (next_offset + match_len >= RDP_MPPC_DICT_SIZE) { return -1; } /* memory areas can overlap - meaning we can't use memXXX functions */ k = (next_offset - match_off) & (big ? 65535 : 8191); do { dict[next_offset++] = dict[k++]; } while (--match_len != 0); } while (1); /* store history offset */ g_mppc_dict.roff = next_offset; *roff = old_offset; *rlen = next_offset - old_offset; return 0; }