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 48LZO_PUBLIC(int) 49DO_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) 126literal1: 127#endif 128 do *op++ = *ip++; while (--t > 0); 129 } 130 131#if (M3O_BITS == 7) 132literal2: 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 159match: 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 251eof_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) 260input_overrun: 261 *out_len = pd(op, out); 262 return LZO_E_INPUT_OVERRUN; 263#endif 264 265#if defined(HAVE_NEED_OP) 266output_overrun: 267 *out_len = pd(op, out); 268 return LZO_E_OUTPUT_OVERRUN; 269#endif 270 271#if defined(LZO_TEST_OVERRUN_LOOKBEHIND) 272lookbehind_overrun: 273 *out_len = pd(op, out); 274 return LZO_E_LOOKBEHIND_OVERRUN; 275#endif 276} 277 278 279/* 280vi:ts=4:et 281*/ 282 283