1/* lzo1x_d.ch -- implementation of the LZO1X decompression algorithm 2 3 This file is part of the LZO real-time data compression library. 4 5 Copyright (C) 1996-2014 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#if defined(DO_DECOMPRESS) 37LZO_PUBLIC(int) 38DO_DECOMPRESS ( const lzo_bytep in , lzo_uint in_len, 39 lzo_bytep out, lzo_uintp out_len, 40 lzo_voidp wrkmem ) 41#endif 42{ 43 lzo_bytep op; 44 const lzo_bytep ip; 45 lzo_uint t; 46#if defined(COPY_DICT) 47 lzo_uint m_off; 48 const lzo_bytep dict_end; 49#else 50 const lzo_bytep m_pos; 51#endif 52 53 const lzo_bytep const ip_end = in + in_len; 54#if defined(HAVE_ANY_OP) 55 lzo_bytep const op_end = out + *out_len; 56#endif 57#if defined(LZO1Z) 58 lzo_uint last_m_off = 0; 59#endif 60 61 LZO_UNUSED(wrkmem); 62 63#if defined(COPY_DICT) 64 if (dict) 65 { 66 if (dict_len > M4_MAX_OFFSET) 67 { 68 dict += dict_len - M4_MAX_OFFSET; 69 dict_len = M4_MAX_OFFSET; 70 } 71 dict_end = dict + dict_len; 72 } 73 else 74 { 75 dict_len = 0; 76 dict_end = NULL; 77 } 78#endif /* COPY_DICT */ 79 80 *out_len = 0; 81 82 op = out; 83 ip = in; 84 85 NEED_IP(1); 86 if (*ip > 17) 87 { 88 t = *ip++ - 17; 89 if (t < 4) 90 goto match_next; 91 assert(t > 0); NEED_OP(t); NEED_IP(t+3); 92 do *op++ = *ip++; while (--t > 0); 93 goto first_literal_run; 94 } 95 96 for (;;) 97 { 98 NEED_IP(3); 99 t = *ip++; 100 if (t >= 16) 101 goto match; 102 /* a literal run */ 103 if (t == 0) 104 { 105 while (*ip == 0) 106 { 107 t += 255; 108 ip++; 109 TEST_IV(t); 110 NEED_IP(1); 111 } 112 t += 15 + *ip++; 113 } 114 /* copy literals */ 115 assert(t > 0); NEED_OP(t+3); NEED_IP(t+6); 116#if (LZO_OPT_UNALIGNED64) && (LZO_OPT_UNALIGNED32) 117 t += 3; 118 if (t >= 8) do 119 { 120 UA_COPY8(op,ip); 121 op += 8; ip += 8; t -= 8; 122 } while (t >= 8); 123 if (t >= 4) 124 { 125 UA_COPY4(op,ip); 126 op += 4; ip += 4; t -= 4; 127 } 128 if (t > 0) 129 { 130 *op++ = *ip++; 131 if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } } 132 } 133#elif (LZO_OPT_UNALIGNED32) || (LZO_ALIGNED_OK_4) 134#if !(LZO_OPT_UNALIGNED32) 135 if (PTR_ALIGNED2_4(op,ip)) 136 { 137#endif 138 UA_COPY4(op,ip); 139 op += 4; ip += 4; 140 if (--t > 0) 141 { 142 if (t >= 4) 143 { 144 do { 145 UA_COPY4(op,ip); 146 op += 4; ip += 4; t -= 4; 147 } while (t >= 4); 148 if (t > 0) do *op++ = *ip++; while (--t > 0); 149 } 150 else 151 do *op++ = *ip++; while (--t > 0); 152 } 153#if !(LZO_OPT_UNALIGNED32) 154 } 155 else 156#endif 157#endif 158#if !(LZO_OPT_UNALIGNED32) 159 { 160 *op++ = *ip++; *op++ = *ip++; *op++ = *ip++; 161 do *op++ = *ip++; while (--t > 0); 162 } 163#endif 164 165 166first_literal_run: 167 168 169 t = *ip++; 170 if (t >= 16) 171 goto match; 172#if defined(COPY_DICT) 173#if defined(LZO1Z) 174 m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2); 175 last_m_off = m_off; 176#else 177 m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2); 178#endif 179 NEED_OP(3); 180 t = 3; COPY_DICT(t,m_off) 181#else /* !COPY_DICT */ 182#if defined(LZO1Z) 183 t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2); 184 m_pos = op - t; 185 last_m_off = t; 186#else 187 m_pos = op - (1 + M2_MAX_OFFSET); 188 m_pos -= t >> 2; 189 m_pos -= *ip++ << 2; 190#endif 191 TEST_LB(m_pos); NEED_OP(3); 192 *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos; 193#endif /* COPY_DICT */ 194 goto match_done; 195 196 197 /* handle matches */ 198 for (;;) { 199match: 200 if (t >= 64) /* a M2 match */ 201 { 202#if defined(COPY_DICT) 203#if defined(LZO1X) 204 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3); 205 t = (t >> 5) - 1; 206#elif defined(LZO1Y) 207 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2); 208 t = (t >> 4) - 3; 209#elif defined(LZO1Z) 210 m_off = t & 0x1f; 211 if (m_off >= 0x1c) 212 m_off = last_m_off; 213 else 214 { 215 m_off = 1 + (m_off << 6) + (*ip++ >> 2); 216 last_m_off = m_off; 217 } 218 t = (t >> 5) - 1; 219#endif 220#else /* !COPY_DICT */ 221#if defined(LZO1X) 222 m_pos = op - 1; 223 m_pos -= (t >> 2) & 7; 224 m_pos -= *ip++ << 3; 225 t = (t >> 5) - 1; 226#elif defined(LZO1Y) 227 m_pos = op - 1; 228 m_pos -= (t >> 2) & 3; 229 m_pos -= *ip++ << 2; 230 t = (t >> 4) - 3; 231#elif defined(LZO1Z) 232 { 233 lzo_uint off = t & 0x1f; 234 m_pos = op; 235 if (off >= 0x1c) 236 { 237 assert(last_m_off > 0); 238 m_pos -= last_m_off; 239 } 240 else 241 { 242 off = 1 + (off << 6) + (*ip++ >> 2); 243 m_pos -= off; 244 last_m_off = off; 245 } 246 } 247 t = (t >> 5) - 1; 248#endif 249 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1); 250 goto copy_match; 251#endif /* COPY_DICT */ 252 } 253 else if (t >= 32) /* a M3 match */ 254 { 255 t &= 31; 256 if (t == 0) 257 { 258 while (*ip == 0) 259 { 260 t += 255; 261 ip++; 262 TEST_OV(t); 263 NEED_IP(1); 264 } 265 t += 31 + *ip++; 266 NEED_IP(2); 267 } 268#if defined(COPY_DICT) 269#if defined(LZO1Z) 270 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2); 271 last_m_off = m_off; 272#else 273 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6); 274#endif 275#else /* !COPY_DICT */ 276#if defined(LZO1Z) 277 { 278 lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2); 279 m_pos = op - off; 280 last_m_off = off; 281 } 282#elif (LZO_OPT_UNALIGNED16) && (LZO_ABI_LITTLE_ENDIAN) 283 m_pos = op - 1; 284 m_pos -= UA_GET_LE16(ip) >> 2; 285#else 286 m_pos = op - 1; 287 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 288#endif 289#endif /* COPY_DICT */ 290 ip += 2; 291 } 292 else if (t >= 16) /* a M4 match */ 293 { 294#if defined(COPY_DICT) 295 m_off = (t & 8) << 11; 296#else /* !COPY_DICT */ 297 m_pos = op; 298 m_pos -= (t & 8) << 11; 299#endif /* COPY_DICT */ 300 t &= 7; 301 if (t == 0) 302 { 303 while (*ip == 0) 304 { 305 t += 255; 306 ip++; 307 TEST_OV(t); 308 NEED_IP(1); 309 } 310 t += 7 + *ip++; 311 NEED_IP(2); 312 } 313#if defined(COPY_DICT) 314#if defined(LZO1Z) 315 m_off += (ip[0] << 6) + (ip[1] >> 2); 316#else 317 m_off += (ip[0] >> 2) + (ip[1] << 6); 318#endif 319 ip += 2; 320 if (m_off == 0) 321 goto eof_found; 322 m_off += 0x4000; 323#if defined(LZO1Z) 324 last_m_off = m_off; 325#endif 326#else /* !COPY_DICT */ 327#if defined(LZO1Z) 328 m_pos -= (ip[0] << 6) + (ip[1] >> 2); 329#elif (LZO_OPT_UNALIGNED16) && (LZO_ABI_LITTLE_ENDIAN) 330 m_pos -= UA_GET_LE16(ip) >> 2; 331#else 332 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 333#endif 334 ip += 2; 335 if (m_pos == op) 336 goto eof_found; 337 m_pos -= 0x4000; 338#if defined(LZO1Z) 339 last_m_off = pd((const lzo_bytep)op, m_pos); 340#endif 341#endif /* COPY_DICT */ 342 } 343 else /* a M1 match */ 344 { 345#if defined(COPY_DICT) 346#if defined(LZO1Z) 347 m_off = 1 + (t << 6) + (*ip++ >> 2); 348 last_m_off = m_off; 349#else 350 m_off = 1 + (t >> 2) + (*ip++ << 2); 351#endif 352 NEED_OP(2); 353 t = 2; COPY_DICT(t,m_off) 354#else /* !COPY_DICT */ 355#if defined(LZO1Z) 356 t = 1 + (t << 6) + (*ip++ >> 2); 357 m_pos = op - t; 358 last_m_off = t; 359#else 360 m_pos = op - 1; 361 m_pos -= t >> 2; 362 m_pos -= *ip++ << 2; 363#endif 364 TEST_LB(m_pos); NEED_OP(2); 365 *op++ = *m_pos++; *op++ = *m_pos; 366#endif /* COPY_DICT */ 367 goto match_done; 368 } 369 370 /* copy match */ 371#if defined(COPY_DICT) 372 373 NEED_OP(t+3-1); 374 t += 3-1; COPY_DICT(t,m_off) 375 376#else /* !COPY_DICT */ 377 378 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1); 379#if (LZO_OPT_UNALIGNED64) && (LZO_OPT_UNALIGNED32) 380 if (op - m_pos >= 8) 381 { 382 t += (3 - 1); 383 if (t >= 8) do 384 { 385 UA_COPY8(op,m_pos); 386 op += 8; m_pos += 8; t -= 8; 387 } while (t >= 8); 388 if (t >= 4) 389 { 390 UA_COPY4(op,m_pos); 391 op += 4; m_pos += 4; t -= 4; 392 } 393 if (t > 0) 394 { 395 *op++ = m_pos[0]; 396 if (t > 1) { *op++ = m_pos[1]; if (t > 2) { *op++ = m_pos[2]; } } 397 } 398 } 399 else 400#elif (LZO_OPT_UNALIGNED32) || (LZO_ALIGNED_OK_4) 401#if !(LZO_OPT_UNALIGNED32) 402 if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) 403 { 404 assert((op - m_pos) >= 4); /* both pointers are aligned */ 405#else 406 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) 407 { 408#endif 409 UA_COPY4(op,m_pos); 410 op += 4; m_pos += 4; t -= 4 - (3 - 1); 411 do { 412 UA_COPY4(op,m_pos); 413 op += 4; m_pos += 4; t -= 4; 414 } while (t >= 4); 415 if (t > 0) do *op++ = *m_pos++; while (--t > 0); 416 } 417 else 418#endif 419 { 420copy_match: 421 *op++ = *m_pos++; *op++ = *m_pos++; 422 do *op++ = *m_pos++; while (--t > 0); 423 } 424 425#endif /* COPY_DICT */ 426 427match_done: 428#if defined(LZO1Z) 429 t = ip[-1] & 3; 430#else 431 t = ip[-2] & 3; 432#endif 433 if (t == 0) 434 break; 435 436 /* copy literals */ 437match_next: 438 assert(t > 0); assert(t < 4); NEED_OP(t); NEED_IP(t+3); 439#if 0 440 do *op++ = *ip++; while (--t > 0); 441#else 442 *op++ = *ip++; 443 if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } } 444#endif 445 t = *ip++; 446 } 447 } 448 449eof_found: 450 *out_len = pd(op, out); 451 return (ip == ip_end ? LZO_E_OK : 452 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 453 454 455#if defined(HAVE_NEED_IP) 456input_overrun: 457 *out_len = pd(op, out); 458 return LZO_E_INPUT_OVERRUN; 459#endif 460 461#if defined(HAVE_NEED_OP) 462output_overrun: 463 *out_len = pd(op, out); 464 return LZO_E_OUTPUT_OVERRUN; 465#endif 466 467#if defined(LZO_TEST_OVERRUN_LOOKBEHIND) 468lookbehind_overrun: 469 *out_len = pd(op, out); 470 return LZO_E_LOOKBEHIND_OVERRUN; 471#endif 472} 473 474 475/* 476vi:ts=4:et 477*/ 478 479