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