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