base/applications/mstsc/mppc.c

   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 <precomp.h>
  22
  23 /* mppc decompression                       */
  24 /* http://www.faqs.org/rfcs/rfc2118.html    */
  25
  26 /* Contacts:                                */
  27
  28 /* hifn contact mentioned in the faq is     */
  29 /* Robert Friend rfriend at hifn dot com    */
  30
  31 /* if you have questions regarding MPPC     */
  32 /* our contact is                           */
  33 /* Guus Dhaeze  GDhaeze at hifn dot com     */
  34
  35 /* Licensing:                               */
  36
  37 /* decompression is alright as long as we   */
  38 /* don't compress data                      */
  39
  40 /* Algorithm: */
  41
  42 /* as the rfc states the algorithm seems to */
  43 /* be LZ77 with a sliding buffer            */
  44 /* that is empty at init.                   */
  45
  46 /* the algorithm is called LZS and is       */
  47 /* patented for another couple of years.    */
  48
  49 /* more information is available in         */
  50 /* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
  51
  52
  53 RDPCOMP g_mppc_dict;
  54
  55 int
  56 mppc_expand(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 = g_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                 g_mppc_dict.roff = 0;
  77         }
  78
  79         if ((ctype & RDP_MPPC_FLUSH) != 0)
  80         {
  81                 memset(dict, 0, RDP_MPPC_DICT_SIZE);
  82                 g_mppc_dict.roff = 0;
  83         }
  84
  85         *roff = 0;
  86         *rlen = 0;
  87
  88         walker = g_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         g_mppc_dict.roff = next_offset;
 372
 373         *roff = old_offset;
 374         *rlen = next_offset - old_offset;
 375
 376         return 0;
 377 }