release/src/router/lzo/src/lzo1x_d.ch

   1 /* lzo1x_d.ch -- implementation of the LZO1X decompression algorithm
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 2011 Markus Franz Xaver Johannes Oberhumer
   6    Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer
   7    Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer
   8    Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   9    Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
  10    Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
  11    Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
  12    Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  13    Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  14    Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  15    Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  16    Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  17    Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  18    Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  19    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  20    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  21    All Rights Reserved.
  22
  23    The LZO library is free software; you can redistribute it and/or
  24    modify it under the terms of the GNU General Public License as
  25    published by the Free Software Foundation; either version 2 of
  26    the License, or (at your option) any later version.
  27
  28    The LZO library is distributed in the hope that it will be useful,
  29    but WITHOUT ANY WARRANTY; without even the implied warranty of
  30    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31    GNU General Public License for more details.
  32
  33    You should have received a copy of the GNU General Public License
  34    along with the LZO library; see the file COPYING.
  35    If not, write to the Free Software Foundation, Inc.,
  36    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  37
  38    Markus F.X.J. Oberhumer
  39    <markus@oberhumer.com>
  40    http://www.oberhumer.com/opensource/lzo/
  41  */
  42
  43
  44 #include "lzo1_d.ch"
  45
  46
  47 /***********************************************************************
  48 // decompress a block of data.
  49 ************************************************************************/
  50
  51 #if defined(DO_DECOMPRESS)
  52 LZO_PUBLIC(int)
  53 DO_DECOMPRESS  ( const lzo_bytep in , lzo_uint  in_len,
  54                        lzo_bytep out, lzo_uintp out_len,
  55                        lzo_voidp wrkmem )
  56 #endif
  57 {
  58     register lzo_bytep op;
  59     register const lzo_bytep ip;
  60     register lzo_uint t;
  61 #if defined(COPY_DICT)
  62     lzo_uint m_off;
  63     const lzo_bytep dict_end;
  64 #else
  65     register const lzo_bytep m_pos;
  66 #endif
  67
  68     const lzo_bytep const ip_end = in + in_len;
  69 #if defined(HAVE_ANY_OP)
  70     lzo_bytep const op_end = out + *out_len;
  71 #endif
  72 #if defined(LZO1Z)
  73     lzo_uint last_m_off = 0;
  74 #endif
  75
  76     LZO_UNUSED(wrkmem);
  77
  78 #if defined(COPY_DICT)
  79     if (dict)
  80     {
  81         if (dict_len > M4_MAX_OFFSET)
  82         {
  83             dict += dict_len - M4_MAX_OFFSET;
  84             dict_len = M4_MAX_OFFSET;
  85         }
  86         dict_end = dict + dict_len;
  87     }
  88     else
  89     {
  90         dict_len = 0;
  91         dict_end = NULL;
  92     }
  93 #endif /* COPY_DICT */
  94
  95     *out_len = 0;
  96
  97     op = out;
  98     ip = in;
  99
 100     if (*ip > 17)
 101     {
 102         t = *ip++ - 17;
 103         if (t < 4)
 104             goto match_next;
 105         assert(t > 0); NEED_OP(t); NEED_IP(t+1);
 106         do *op++ = *ip++; while (--t > 0);
 107         goto first_literal_run;
 108     }
 109
 110     while (TEST_IP && TEST_OP)
 111     {
 112         t = *ip++;
 113         if (t >= 16)
 114             goto match;
 115         /* a literal run */
 116         if (t == 0)
 117         {
 118             NEED_IP(1);
 119             while (*ip == 0)
 120             {
 121                 t += 255;
 122                 ip++;
 123                 NEED_IP(1);
 124             }
 125             t += 15 + *ip++;
 126         }
 127         /* copy literals */
 128         assert(t > 0); NEED_OP(t+3); NEED_IP(t+4);
 129 #if defined(LZO_UNALIGNED_OK_8) && defined(LZO_UNALIGNED_OK_4)
 130         t += 3;
 131         if (t >= 8) do
 132         {
 133             UA_COPY64(op,ip);
 134             op += 8; ip += 8; t -= 8;
 135         } while (t >= 8);
 136         if (t >= 4)
 137         {
 138             UA_COPY32(op,ip);
 139             op += 4; ip += 4; t -= 4;
 140         }
 141         if (t > 0)
 142         {
 143             *op++ = *ip++;
 144             if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
 145         }
 146 #elif defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
 147 #if !defined(LZO_UNALIGNED_OK_4)
 148         if (PTR_ALIGNED2_4(op,ip))
 149         {
 150 #endif
 151         UA_COPY32(op,ip);
 152         op += 4; ip += 4;
 153         if (--t > 0)
 154         {
 155             if (t >= 4)
 156             {
 157                 do {
 158                     UA_COPY32(op,ip);
 159                     op += 4; ip += 4; t -= 4;
 160                 } while (t >= 4);
 161                 if (t > 0) do *op++ = *ip++; while (--t > 0);
 162             }
 163             else
 164                 do *op++ = *ip++; while (--t > 0);
 165         }
 166 #if !defined(LZO_UNALIGNED_OK_4)
 167         }
 168         else
 169 #endif
 170 #endif
 171 #if !defined(LZO_UNALIGNED_OK_4) && !defined(LZO_UNALIGNED_OK_8)
 172         {
 173             *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
 174             do *op++ = *ip++; while (--t > 0);
 175         }
 176 #endif
 177
 178
 179 first_literal_run:
 180
 181
 182         t = *ip++;
 183         if (t >= 16)
 184             goto match;
 185 #if defined(COPY_DICT)
 186 #if defined(LZO1Z)
 187         m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
 188         last_m_off = m_off;
 189 #else
 190         m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
 191 #endif
 192         NEED_OP(3);
 193         t = 3; COPY_DICT(t,m_off)
 194 #else /* !COPY_DICT */
 195 #if defined(LZO1Z)
 196         t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
 197         m_pos = op - t;
 198         last_m_off = t;
 199 #else
 200         m_pos = op - (1 + M2_MAX_OFFSET);
 201         m_pos -= t >> 2;
 202         m_pos -= *ip++ << 2;
 203 #endif
 204         TEST_LB(m_pos); NEED_OP(3);
 205         *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
 206 #endif /* COPY_DICT */
 207         goto match_done;
 208
 209
 210         /* handle matches */
 211         do {
 212 match:
 213             if (t >= 64)                /* a M2 match */
 214             {
 215 #if defined(COPY_DICT)
 216 #if defined(LZO1X)
 217                 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
 218                 t = (t >> 5) - 1;
 219 #elif defined(LZO1Y)
 220                 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
 221                 t = (t >> 4) - 3;
 222 #elif defined(LZO1Z)
 223                 m_off = t & 0x1f;
 224                 if (m_off >= 0x1c)
 225                     m_off = last_m_off;
 226                 else
 227                 {
 228                     m_off = 1 + (m_off << 6) + (*ip++ >> 2);
 229                     last_m_off = m_off;
 230                 }
 231                 t = (t >> 5) - 1;
 232 #endif
 233 #else /* !COPY_DICT */
 234 #if defined(LZO1X)
 235                 m_pos = op - 1;
 236                 m_pos -= (t >> 2) & 7;
 237                 m_pos -= *ip++ << 3;
 238                 t = (t >> 5) - 1;
 239 #elif defined(LZO1Y)
 240                 m_pos = op - 1;
 241                 m_pos -= (t >> 2) & 3;
 242                 m_pos -= *ip++ << 2;
 243                 t = (t >> 4) - 3;
 244 #elif defined(LZO1Z)
 245                 {
 246                     lzo_uint off = t & 0x1f;
 247                     m_pos = op;
 248                     if (off >= 0x1c)
 249                     {
 250                         assert(last_m_off > 0);
 251                         m_pos -= last_m_off;
 252                     }
 253                     else
 254                     {
 255                         off = 1 + (off << 6) + (*ip++ >> 2);
 256                         m_pos -= off;
 257                         last_m_off = off;
 258                     }
 259                 }
 260                 t = (t >> 5) - 1;
 261 #endif
 262                 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 263                 goto copy_match;
 264 #endif /* COPY_DICT */
 265             }
 266             else if (t >= 32)           /* a M3 match */
 267             {
 268                 t &= 31;
 269                 if (t == 0)
 270                 {
 271                     NEED_IP(1);
 272                     while (*ip == 0)
 273                     {
 274                         t += 255;
 275                         ip++;
 276                         NEED_IP(1);
 277                     }
 278                     t += 31 + *ip++;
 279                 }
 280 #if defined(COPY_DICT)
 281 #if defined(LZO1Z)
 282                 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
 283                 last_m_off = m_off;
 284 #else
 285                 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
 286 #endif
 287 #else /* !COPY_DICT */
 288 #if defined(LZO1Z)
 289                 {
 290                     lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
 291                     m_pos = op - off;
 292                     last_m_off = off;
 293                 }
 294 #elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 295                 m_pos = op - 1;
 296                 m_pos -= UA_GET16(ip) >> 2;
 297 #else
 298                 m_pos = op - 1;
 299                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
 300 #endif
 301 #endif /* COPY_DICT */
 302                 ip += 2;
 303             }
 304             else if (t >= 16)           /* a M4 match */
 305             {
 306 #if defined(COPY_DICT)
 307                 m_off = (t & 8) << 11;
 308 #else /* !COPY_DICT */
 309                 m_pos = op;
 310                 m_pos -= (t & 8) << 11;
 311 #endif /* COPY_DICT */
 312                 t &= 7;
 313                 if (t == 0)
 314                 {
 315                     NEED_IP(1);
 316                     while (*ip == 0)
 317                     {
 318                         t += 255;
 319                         ip++;
 320                         NEED_IP(1);
 321                     }
 322                     t += 7 + *ip++;
 323                 }
 324 #if defined(COPY_DICT)
 325 #if defined(LZO1Z)
 326                 m_off += (ip[0] << 6) + (ip[1] >> 2);
 327 #else
 328                 m_off += (ip[0] >> 2) + (ip[1] << 6);
 329 #endif
 330                 ip += 2;
 331                 if (m_off == 0)
 332                     goto eof_found;
 333                 m_off += 0x4000;
 334 #if defined(LZO1Z)
 335                 last_m_off = m_off;
 336 #endif
 337 #else /* !COPY_DICT */
 338 #if defined(LZO1Z)
 339                 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
 340 #elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 341                 m_pos -= UA_GET16(ip) >> 2;
 342 #else
 343                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
 344 #endif
 345                 ip += 2;
 346                 if (m_pos == op)
 347                     goto eof_found;
 348                 m_pos -= 0x4000;
 349 #if defined(LZO1Z)
 350                 last_m_off = pd((const lzo_bytep)op, m_pos);
 351 #endif
 352 #endif /* COPY_DICT */
 353             }
 354             else                            /* a M1 match */
 355             {
 356 #if defined(COPY_DICT)
 357 #if defined(LZO1Z)
 358                 m_off = 1 + (t << 6) + (*ip++ >> 2);
 359                 last_m_off = m_off;
 360 #else
 361                 m_off = 1 + (t >> 2) + (*ip++ << 2);
 362 #endif
 363                 NEED_OP(2);
 364                 t = 2; COPY_DICT(t,m_off)
 365 #else /* !COPY_DICT */
 366 #if defined(LZO1Z)
 367                 t = 1 + (t << 6) + (*ip++ >> 2);
 368                 m_pos = op - t;
 369                 last_m_off = t;
 370 #else
 371                 m_pos = op - 1;
 372                 m_pos -= t >> 2;
 373                 m_pos -= *ip++ << 2;
 374 #endif
 375                 TEST_LB(m_pos); NEED_OP(2);
 376                 *op++ = *m_pos++; *op++ = *m_pos;
 377 #endif /* COPY_DICT */
 378                 goto match_done;
 379             }
 380
 381             /* copy match */
 382 #if defined(COPY_DICT)
 383
 384             NEED_OP(t+3-1);
 385             t += 3-1; COPY_DICT(t,m_off)
 386
 387 #else /* !COPY_DICT */
 388
 389             TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 390 #if defined(LZO_UNALIGNED_OK_8) && defined(LZO_UNALIGNED_OK_4)
 391             if (op - m_pos >= 8)
 392             {
 393                 t += (3 - 1);
 394                 if (t >= 8) do
 395                 {
 396                     UA_COPY64(op,m_pos);
 397                     op += 8; m_pos += 8; t -= 8;
 398                 } while (t >= 8);
 399                 if (t >= 4)
 400                 {
 401                     UA_COPY32(op,m_pos);
 402                     op += 4; m_pos += 4; t -= 4;
 403                 }
 404                 if (t > 0)
 405                 {
 406                     *op++ = m_pos[0];
 407                     if (t > 1) { *op++ = m_pos[1]; if (t > 2) { *op++ = m_pos[2]; } }
 408                 }
 409             }
 410             else
 411 #elif defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
 412 #if !defined(LZO_UNALIGNED_OK_4)
 413             if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
 414             {
 415                 assert((op - m_pos) >= 4);  /* both pointers are aligned */
 416 #else
 417             if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
 418             {
 419 #endif
 420                 UA_COPY32(op,m_pos);
 421                 op += 4; m_pos += 4; t -= 4 - (3 - 1);
 422                 do {
 423                     UA_COPY32(op,m_pos);
 424                     op += 4; m_pos += 4; t -= 4;
 425                 } while (t >= 4);
 426                 if (t > 0) do *op++ = *m_pos++; while (--t > 0);
 427             }
 428             else
 429 #endif
 430             {
 431 copy_match:
 432                 *op++ = *m_pos++; *op++ = *m_pos++;
 433                 do *op++ = *m_pos++; while (--t > 0);
 434             }
 435
 436 #endif /* COPY_DICT */
 437
 438 match_done:
 439 #if defined(LZO1Z)
 440             t = ip[-1] & 3;
 441 #else
 442             t = ip[-2] & 3;
 443 #endif
 444             if (t == 0)
 445                 break;
 446
 447             /* copy literals */
 448 match_next:
 449             assert(t > 0); assert(t < 4); NEED_OP(t); NEED_IP(t+1);
 450 #if 0
 451             do *op++ = *ip++; while (--t > 0);
 452 #else
 453             *op++ = *ip++;
 454             if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
 455 #endif
 456             t = *ip++;
 457         } while (TEST_IP && TEST_OP);
 458     }
 459
 460 #if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
 461     /* no EOF code was found */
 462     *out_len = pd(op, out);
 463     return LZO_E_EOF_NOT_FOUND;
 464 #endif
 465
 466 eof_found:
 467     assert(t == 1);
 468     *out_len = pd(op, out);
 469     return (ip == ip_end ? LZO_E_OK :
 470            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 471
 472
 473 #if defined(HAVE_NEED_IP)
 474 input_overrun:
 475     *out_len = pd(op, out);
 476     return LZO_E_INPUT_OVERRUN;
 477 #endif
 478
 479 #if defined(HAVE_NEED_OP)
 480 output_overrun:
 481     *out_len = pd(op, out);
 482     return LZO_E_OUTPUT_OVERRUN;
 483 #endif
 484
 485 #if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
 486 lookbehind_overrun:
 487     *out_len = pd(op, out);
 488     return LZO_E_LOOKBEHIND_OVERRUN;
 489 #endif
 490 }
 491
 492
 493 /*
 494 vi:ts=4:et
 495 */
 496