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 (at) 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) 37 LZO_PUBLIC(int) 38 DO_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 166 first_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 (;;) { 199 match: 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 { 420 copy_match: 421 *op++ = *m_pos++; *op++ = *m_pos++; 422 do *op++ = *m_pos++; while (--t > 0); 423 } 424 425 #endif /* COPY_DICT */ 426 427 match_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 */ 437 match_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 449 eof_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) 456 input_overrun: 457 *out_len = pd(op, out); 458 return LZO_E_INPUT_OVERRUN; 459 #endif 460 461 #if defined(HAVE_NEED_OP) 462 output_overrun: 463 *out_len = pd(op, out); 464 return LZO_E_OUTPUT_OVERRUN; 465 #endif 466 467 #if defined(LZO_TEST_OVERRUN_LOOKBEHIND) 468 lookbehind_overrun: 469 *out_len = pd(op, out); 470 return LZO_E_LOOKBEHIND_OVERRUN; 471 #endif 472 } 473 474 475 /* 476 vi:ts=4:et 477 */ 478 479
