src/lzo1f_d.ch

   1 /* lzo1f_d.ch -- implementation of the LZO1F 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     *out_len = 0;
  66
  67     op = out;
  68     ip = in;
  69
  70     while (TEST_IP && TEST_OP)
  71     {
  72         t = *ip++;
  73         if (t > 31)
  74             goto match;
  75
  76         /* a literal run */
  77         if (t == 0)
  78         {
  79             NEED_IP(1);
  80             while (*ip == 0)
  81             {
  82                 t += 255;
  83                 ip++;
  84                 NEED_IP(1);
  85             }
  86             t += 31 + *ip++;
  87         }
  88         /* copy literals */
  89         assert(t > 0); NEED_OP(t); NEED_IP(t+1);
  90 #if defined(LZO_UNALIGNED_OK_4)
  91         if (t >= 4)
  92         {
  93             do {
  94                 * (lzo_uint32p) op = * (const lzo_uint32p) ip;
  95                 op += 4; ip += 4; t -= 4;
  96             } while (t >= 4);
  97             if (t > 0) do *op++ = *ip++; while (--t > 0);
  98         }
  99         else
 100 #endif
 101         do *op++ = *ip++; while (--t > 0);
 102
 103         t = *ip++;
 104
 105         while (TEST_IP && TEST_OP)
 106         {
 107             /* handle matches */
 108             if (t < 32)
 109             {
 110                 m_pos = op - 1 - 0x800;
 111                 m_pos -= (t >> 2) & 7;
 112                 m_pos -= *ip++ << 3;
 113                 TEST_LB(m_pos); NEED_OP(3);
 114                 *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
 115             }
 116             else
 117             {
 118 match:
 119                 if (t < M3_MARKER)
 120                 {
 121                     m_pos = op - 1;
 122                     m_pos -= (t >> 2) & 7;
 123                     m_pos -= *ip++ << 3;
 124                     t >>= 5;
 125                     TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 126                     goto copy_match;
 127                 }
 128                 else
 129                 {
 130                     t &= 31;
 131                     if (t == 0)
 132                     {
 133                         NEED_IP(1);
 134                         while (*ip == 0)
 135                         {
 136                             t += 255;
 137                             ip++;
 138                             NEED_IP(1);
 139                         }
 140                         t += 31 + *ip++;
 141                     }
 142                     NEED_IP(2);
 143                     m_pos = op;
 144 #if defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 145                     m_pos -= (* (const lzo_ushortp) ip) >> 2;
 146                     ip += 2;
 147 #else
 148                     m_pos -= *ip++ >> 2;
 149                     m_pos -= *ip++ << 6;
 150 #endif
 151                     if (m_pos == op)
 152                         goto eof_found;
 153                 }
 154
 155                 /* copy match */
 156                 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 157 #if defined(LZO_UNALIGNED_OK_4)
 158                 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
 159                 {
 160                     * (lzo_uint32p) op = * (const lzo_uint32p) m_pos;
 161                     op += 4; m_pos += 4; t -= 4 - (3 - 1);
 162                     do {
 163                         * (lzo_uint32p) op = * (const lzo_uint32p) m_pos;
 164                         op += 4; m_pos += 4; t -= 4;
 165                     } while (t >= 4);
 166                     if (t > 0) do *op++ = *m_pos++; while (--t > 0);
 167                 }
 168                 else
 169 #endif
 170                 {
 171 copy_match:
 172                 *op++ = *m_pos++; *op++ = *m_pos++;
 173                 do *op++ = *m_pos++; while (--t > 0);
 174                 }
 175             }
 176             t = ip[-2] & 3;
 177             if (t == 0)
 178                 break;
 179
 180             /* copy literals */
 181             assert(t > 0); NEED_OP(t); NEED_IP(t+1);
 182             do *op++ = *ip++; while (--t > 0);
 183             t = *ip++;
 184         }
 185     }
 186
 187 #if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
 188     /* no EOF code was found */
 189     *out_len = pd(op, out);
 190     return LZO_E_EOF_NOT_FOUND;
 191 #endif
 192
 193 eof_found:
 194     assert(t == 1);
 195     *out_len = pd(op, out);
 196     return (ip == ip_end ? LZO_E_OK :
 197            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 198
 199
 200 #if defined(HAVE_NEED_IP)
 201 input_overrun:
 202     *out_len = pd(op, out);
 203     return LZO_E_INPUT_OVERRUN;
 204 #endif
 205
 206 #if defined(HAVE_NEED_OP)
 207 output_overrun:
 208     *out_len = pd(op, out);
 209     return LZO_E_OUTPUT_OVERRUN;
 210 #endif
 211
 212 #if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
 213 lookbehind_overrun:
 214     *out_len = pd(op, out);
 215     return LZO_E_LOOKBEHIND_OVERRUN;
 216 #endif
 217 }
 218
 219
 220 /*
 221 vi:ts=4:et
 222 */
 223