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