src/lzo1b_d.ch

   1 /* lzo1b_d.ch -- implementation of the LZO1B 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 /***********************************************************************
  45 // decompress a block of data.
  46 ************************************************************************/
  47
  48 LZO_PUBLIC(int)
  49 DO_DECOMPRESS    ( const lzo_bytep in , lzo_uint  in_len,
  50                          lzo_bytep out, lzo_uintp out_len,
  51                          lzo_voidp wrkmem )
  52 {
  53     register lzo_bytep op;
  54     register const lzo_bytep ip;
  55     register lzo_uint t;
  56     register const lzo_bytep m_pos;
  57
  58     const lzo_bytep const ip_end = in + in_len;
  59 #if defined(HAVE_ANY_OP)
  60     lzo_bytep const op_end = out + *out_len;
  61 #endif
  62
  63     LZO_UNUSED(wrkmem);
  64
  65     op = out;
  66     ip = in;
  67
  68     while (TEST_IP && TEST_OP)
  69     {
  70         t = *ip++;      /* get marker */
  71
  72         if (t < R0MIN)      /* a literal run */
  73         {
  74             if (t == 0)             /* a R0 literal run */
  75             {
  76                 NEED_IP(1);
  77                 t = *ip++;
  78                 if (t >= R0FAST - R0MIN)            /* a long R0 run */
  79                 {
  80                     t -= R0FAST - R0MIN;
  81                     if (t == 0)
  82                         t = R0FAST;
  83                     else
  84                     {
  85 #if 0
  86                         t = 256u << ((unsigned) t);
  87 #else
  88                         /* help the optimizer */
  89                         lzo_uint tt = 256;
  90                         do tt <<= 1; while (--t > 0);
  91                         t = tt;
  92 #endif
  93                     }
  94
  95                     NEED_IP(t); NEED_OP(t);
  96 #if 1 && defined(LZO_UNALIGNED_OK_4)
  97                     do {
  98                         * (lzo_uint32p) (op+0) = * (const lzo_uint32p) (ip+0);
  99                         * (lzo_uint32p) (op+4) = * (const lzo_uint32p) (ip+4);
 100                         op += 8; ip += 8;
 101                         t -= 8;
 102                     } while (t > 0);
 103 #else
 104                     MEMCPY8_DS(op,ip,t);
 105 #endif
 106                     continue;
 107                 }
 108                 t += R0MIN;                         /* a short R0 run */
 109             }
 110
 111             NEED_IP(t); NEED_OP(t);
 112             /* copy literal run */
 113 #if 1 && defined(LZO_UNALIGNED_OK_4)
 114             if (t >= 4)
 115             {
 116                 do {
 117                     * (lzo_uint32p) op = * (const lzo_uint32p) ip;
 118                     op += 4; ip += 4; t -= 4;
 119                 } while (t >= 4);
 120                 if (t > 0) do *op++ = *ip++; while (--t > 0);
 121             }
 122             else
 123 #endif
 124             {
 125 #if (M3O_BITS < 7)
 126 literal1:
 127 #endif
 128                 do *op++ = *ip++; while (--t > 0);
 129             }
 130
 131 #if (M3O_BITS == 7)
 132 literal2:
 133 #endif
 134
 135             /* after a literal a match must follow */
 136             while (TEST_IP && TEST_OP)
 137             {
 138                 t = *ip++;          /* get R1 marker */
 139                 if (t >= R0MIN)
 140                     goto match;
 141
 142                 NEED_IP(2); NEED_OP(M2_MIN_LEN + 1);
 143
 144             /* R1 match - a M2_MIN_LEN match + 1 byte literal */
 145                 assert((t & M2O_MASK) == t);
 146                 m_pos = op - M2_MIN_OFFSET;
 147                 m_pos -= t | (((lzo_uint) *ip++) << M2O_BITS);
 148                 assert(m_pos >= out); assert(m_pos < op);
 149                 TEST_LB(m_pos);
 150                 COPY_M2;
 151                 *op++ = *ip++;
 152             }
 153
 154 #if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
 155             break;
 156 #endif
 157         }
 158
 159 match:
 160
 161         if (t >= M2_MARKER)             /* a M2 match */
 162         {
 163             /* get match offset */
 164             NEED_IP(1);
 165             m_pos = op - M2_MIN_OFFSET;
 166             m_pos -= (t & M2O_MASK) | (((lzo_uint) *ip++) << M2O_BITS);
 167             assert(m_pos >= out); assert(m_pos < op);
 168             TEST_LB(m_pos);
 169
 170             /* get match len */
 171             t = (t >> M2O_BITS) - 1;
 172             NEED_OP(t + M2_MIN_LEN - 1);
 173             COPY_M2X;
 174             MEMCPY_DS(op,m_pos,t);
 175         }
 176         else                            /* a M3 or M4 match */
 177         {
 178             /* get match len */
 179             t &= M3L_MASK;
 180             if (t == 0)         /* a M4 match */
 181             {
 182                 NEED_IP(1);
 183                 while (*ip == 0)
 184                 {
 185                     t += 255;
 186                     ip++;
 187                     NEED_IP(1);
 188                 }
 189                 t += (M4_MIN_LEN - M3_MIN_LEN) + *ip++;
 190             }
 191
 192             /* get match offset */
 193             NEED_IP(2);
 194             m_pos = op - (M3_MIN_OFFSET - M3_EOF_OFFSET);
 195             m_pos -= *ip++ & M3O_MASK;
 196             m_pos -= (lzo_uint)(*ip++) << M3O_BITS;
 197 #if defined(LZO_EOF_CODE)
 198             if (m_pos == op)
 199                 goto eof_found;
 200 #endif
 201
 202             /* copy match */
 203             assert(m_pos >= out); assert(m_pos < op);
 204             TEST_LB(m_pos); NEED_OP(t + M3_MIN_LEN - 1);
 205 #if defined(LZO_UNALIGNED_OK_4)
 206             if (t >= 2 * 4 - (M3_MIN_LEN - 1) && (op - m_pos) >= 4)
 207             {
 208                 * (lzo_uint32p) op = * (const lzo_uint32p) m_pos;
 209                 op += 4; m_pos += 4; t -= 4 - (M3_MIN_LEN - 1);
 210                 do {
 211                     * (lzo_uint32p) op = * (const lzo_uint32p) m_pos;
 212                     op += 4; m_pos += 4; t -= 4;
 213                 } while (t >= 4);
 214                 if (t > 0) do *op++ = *m_pos++; while (--t > 0);
 215             }
 216             else
 217 #endif
 218             {
 219             COPY_M3X;
 220             MEMCPY_DS(op,m_pos,t);
 221             }
 222
 223
 224 #if (M3O_BITS < 7)
 225             t = ip[-2] >> M3O_BITS;
 226             if (t)
 227             {
 228                 NEED_IP(t); NEED_OP(t);
 229                 goto literal1;
 230             }
 231 #elif (M3O_BITS == 7)
 232             /* optimized version */
 233             if (ip[-2] & (1 << M3O_BITS))
 234             {
 235                 NEED_IP(1); NEED_OP(1);
 236                 *op++ = *ip++;
 237                 goto literal2;
 238             }
 239 #endif
 240         }
 241     }
 242
 243
 244 #if defined(LZO_EOF_CODE)
 245 #if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
 246     /* no EOF code was found */
 247     *out_len = pd(op, out);
 248     return LZO_E_EOF_NOT_FOUND;
 249 #endif
 250
 251 eof_found:
 252     assert(t == 1);
 253 #endif
 254     *out_len = pd(op, out);
 255     return (ip == ip_end ? LZO_E_OK :
 256            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 257
 258
 259 #if defined(HAVE_NEED_IP)
 260 input_overrun:
 261     *out_len = pd(op, out);
 262     return LZO_E_INPUT_OVERRUN;
 263 #endif
 264
 265 #if defined(HAVE_NEED_OP)
 266 output_overrun:
 267     *out_len = pd(op, out);
 268     return LZO_E_OUTPUT_OVERRUN;
 269 #endif
 270
 271 #if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
 272 lookbehind_overrun:
 273     *out_len = pd(op, out);
 274     return LZO_E_LOOKBEHIND_OVERRUN;
 275 #endif
 276 }
 277
 278
 279 /*
 280 vi:ts=4:et
 281 */
 282