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