1/* 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..2008 Markus Franz Xaver Johannes Oberhumer 6 All Rights Reserved. 7 8 Markus F.X.J. Oberhumer <markus@oberhumer.com> 9 http://www.oberhumer.com/opensource/lzo/ 10 11 The LZO library is free software; you can redistribute it and/or 12 modify it under the terms of the GNU General Public License as 13 published by the Free Software Foundation; either version 2 of 14 the License, or (at your option) any later version. 15 16 The LZO library is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License for more details. 20 21 You should have received a copy of the GNU General Public License 22 along with the LZO library; see the file COPYING. 23 If not, write to the Free Software Foundation, Inc., 24 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 25 */ 26#include "libbb.h" 27#include "liblzo.h" 28 29/*********************************************************************** 30// decompress a block of data. 31************************************************************************/ 32/* safe decompression with overrun testing */ 33int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len, 34 uint8_t* out, unsigned* out_len, 35 void* wrkmem UNUSED_PARAM) 36{ 37 register uint8_t* op; 38 register const uint8_t* ip; 39 register unsigned t; 40#if defined(COPY_DICT) 41 unsigned m_off; 42 const uint8_t* dict_end; 43#else 44 register const uint8_t* m_pos = NULL; /* possibly not needed */ 45#endif 46 const uint8_t* const ip_end = in + in_len; 47#if defined(HAVE_ANY_OP) 48 uint8_t* const op_end = out + *out_len; 49#endif 50#if defined(LZO1Z) 51 unsigned last_m_off = 0; 52#endif 53 54// LZO_UNUSED(wrkmem); 55 56#if defined(COPY_DICT) 57 if (dict) { 58 if (dict_len > M4_MAX_OFFSET) { 59 dict += dict_len - M4_MAX_OFFSET; 60 dict_len = M4_MAX_OFFSET; 61 } 62 dict_end = dict + dict_len; 63 } else { 64 dict_len = 0; 65 dict_end = NULL; 66 } 67#endif /* COPY_DICT */ 68 69 *out_len = 0; 70 71 op = out; 72 ip = in; 73 74 if (*ip > 17) { 75 t = *ip++ - 17; 76 if (t < 4) 77 goto match_next; 78 assert(t > 0); NEED_OP(t); NEED_IP(t+1); 79 do *op++ = *ip++; while (--t > 0); 80 goto first_literal_run; 81 } 82 83 while (TEST_IP && TEST_OP) { 84 t = *ip++; 85 if (t >= 16) 86 goto match; 87 /* a literal run */ 88 if (t == 0) { 89 NEED_IP(1); 90 while (*ip == 0) { 91 t += 255; 92 ip++; 93 NEED_IP(1); 94 } 95 t += 15 + *ip++; 96 } 97 /* copy literals */ 98 assert(t > 0); 99 NEED_OP(t+3); 100 NEED_IP(t+4); 101#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4) 102# if !defined(LZO_UNALIGNED_OK_4) 103 if (PTR_ALIGNED2_4(op, ip)) 104# endif 105 { 106 COPY4(op, ip); 107 op += 4; 108 ip += 4; 109 if (--t > 0) { 110 if (t >= 4) { 111 do { 112 COPY4(op, ip); 113 op += 4; 114 ip += 4; 115 t -= 4; 116 } while (t >= 4); 117 if (t > 0) 118 do *op++ = *ip++; while (--t > 0); 119 } else { 120 do *op++ = *ip++; while (--t > 0); 121 } 122 } 123 } 124# if !defined(LZO_UNALIGNED_OK_4) 125 else 126# endif 127#endif 128#if !defined(LZO_UNALIGNED_OK_4) 129 { 130 *op++ = *ip++; 131 *op++ = *ip++; 132 *op++ = *ip++; 133 do *op++ = *ip++; while (--t > 0); 134 } 135#endif 136 137 first_literal_run: 138 t = *ip++; 139 if (t >= 16) 140 goto match; 141#if defined(COPY_DICT) 142#if defined(LZO1Z) 143 m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2); 144 last_m_off = m_off; 145#else 146 m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2); 147#endif 148 NEED_OP(3); 149 t = 3; COPY_DICT(t,m_off) 150#else /* !COPY_DICT */ 151#if defined(LZO1Z) 152 t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2); 153 m_pos = op - t; 154 last_m_off = t; 155#else 156 m_pos = op - (1 + M2_MAX_OFFSET); 157 m_pos -= t >> 2; 158 m_pos -= *ip++ << 2; 159#endif 160 TEST_LB(m_pos); NEED_OP(3); 161 *op++ = *m_pos++; 162 *op++ = *m_pos++; 163 *op++ = *m_pos; 164#endif /* COPY_DICT */ 165 goto match_done; 166 167 /* handle matches */ 168 do { 169 match: 170 if (t >= 64) { /* a M2 match */ 171#if defined(COPY_DICT) 172#if defined(LZO1X) 173 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3); 174 t = (t >> 5) - 1; 175#elif defined(LZO1Y) 176 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2); 177 t = (t >> 4) - 3; 178#elif defined(LZO1Z) 179 m_off = t & 0x1f; 180 if (m_off >= 0x1c) 181 m_off = last_m_off; 182 else { 183 m_off = 1 + (m_off << 6) + (*ip++ >> 2); 184 last_m_off = m_off; 185 } 186 t = (t >> 5) - 1; 187#endif 188#else /* !COPY_DICT */ 189#if defined(LZO1X) 190 m_pos = op - 1; 191 m_pos -= (t >> 2) & 7; 192 m_pos -= *ip++ << 3; 193 t = (t >> 5) - 1; 194#elif defined(LZO1Y) 195 m_pos = op - 1; 196 m_pos -= (t >> 2) & 3; 197 m_pos -= *ip++ << 2; 198 t = (t >> 4) - 3; 199#elif defined(LZO1Z) 200 { 201 unsigned off = t & 0x1f; 202 m_pos = op; 203 if (off >= 0x1c) { 204 assert(last_m_off > 0); 205 m_pos -= last_m_off; 206 } else { 207 off = 1 + (off << 6) + (*ip++ >> 2); 208 m_pos -= off; 209 last_m_off = off; 210 } 211 } 212 t = (t >> 5) - 1; 213#endif 214 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1); 215 goto copy_match; 216#endif /* COPY_DICT */ 217 } 218 else if (t >= 32) { /* a M3 match */ 219 t &= 31; 220 if (t == 0) { 221 NEED_IP(1); 222 while (*ip == 0) { 223 t += 255; 224 ip++; 225 NEED_IP(1); 226 } 227 t += 31 + *ip++; 228 } 229#if defined(COPY_DICT) 230#if defined(LZO1Z) 231 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2); 232 last_m_off = m_off; 233#else 234 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6); 235#endif 236#else /* !COPY_DICT */ 237#if defined(LZO1Z) 238 { 239 unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2); 240 m_pos = op - off; 241 last_m_off = off; 242 } 243#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN) 244 m_pos = op - 1; 245 m_pos -= (* (const lzo_ushortp) ip) >> 2; 246#else 247 m_pos = op - 1; 248 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 249#endif 250#endif /* COPY_DICT */ 251 ip += 2; 252 } 253 else if (t >= 16) { /* a M4 match */ 254#if defined(COPY_DICT) 255 m_off = (t & 8) << 11; 256#else /* !COPY_DICT */ 257 m_pos = op; 258 m_pos -= (t & 8) << 11; 259#endif /* COPY_DICT */ 260 t &= 7; 261 if (t == 0) { 262 NEED_IP(1); 263 while (*ip == 0) { 264 t += 255; 265 ip++; 266 NEED_IP(1); 267 } 268 t += 7 + *ip++; 269 } 270#if defined(COPY_DICT) 271#if defined(LZO1Z) 272 m_off += (ip[0] << 6) + (ip[1] >> 2); 273#else 274 m_off += (ip[0] >> 2) + (ip[1] << 6); 275#endif 276 ip += 2; 277 if (m_off == 0) 278 goto eof_found; 279 m_off += 0x4000; 280#if defined(LZO1Z) 281 last_m_off = m_off; 282#endif 283#else /* !COPY_DICT */ 284#if defined(LZO1Z) 285 m_pos -= (ip[0] << 6) + (ip[1] >> 2); 286#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN) 287 m_pos -= (* (const lzo_ushortp) ip) >> 2; 288#else 289 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 290#endif 291 ip += 2; 292 if (m_pos == op) 293 goto eof_found; 294 m_pos -= 0x4000; 295#if defined(LZO1Z) 296 last_m_off = pd((const uint8_t*)op, m_pos); 297#endif 298#endif /* COPY_DICT */ 299 } 300 else { /* a M1 match */ 301#if defined(COPY_DICT) 302#if defined(LZO1Z) 303 m_off = 1 + (t << 6) + (*ip++ >> 2); 304 last_m_off = m_off; 305#else 306 m_off = 1 + (t >> 2) + (*ip++ << 2); 307#endif 308 NEED_OP(2); 309 t = 2; COPY_DICT(t,m_off) 310#else /* !COPY_DICT */ 311#if defined(LZO1Z) 312 t = 1 + (t << 6) + (*ip++ >> 2); 313 m_pos = op - t; 314 last_m_off = t; 315#else 316 m_pos = op - 1; 317 m_pos -= t >> 2; 318 m_pos -= *ip++ << 2; 319#endif 320 TEST_LB(m_pos); NEED_OP(2); 321 *op++ = *m_pos++; 322 *op++ = *m_pos; 323#endif /* COPY_DICT */ 324 goto match_done; 325 } 326 327 /* copy match */ 328#if defined(COPY_DICT) 329 330 NEED_OP(t+3-1); 331 t += 3-1; COPY_DICT(t,m_off) 332 333#else /* !COPY_DICT */ 334 335 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1); 336#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4) 337# if !defined(LZO_UNALIGNED_OK_4) 338 if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) { 339 assert((op - m_pos) >= 4); /* both pointers are aligned */ 340# else 341 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) { 342# endif 343 COPY4(op,m_pos); 344 op += 4; m_pos += 4; t -= 4 - (3 - 1); 345 do { 346 COPY4(op,m_pos); 347 op += 4; m_pos += 4; t -= 4; 348 } while (t >= 4); 349 if (t > 0) 350 do *op++ = *m_pos++; while (--t > 0); 351 } 352 else 353#endif 354 { 355 copy_match: 356 *op++ = *m_pos++; *op++ = *m_pos++; 357 do *op++ = *m_pos++; while (--t > 0); 358 } 359 360#endif /* COPY_DICT */ 361 362 match_done: 363#if defined(LZO1Z) 364 t = ip[-1] & 3; 365#else 366 t = ip[-2] & 3; 367#endif 368 if (t == 0) 369 break; 370 371 /* copy literals */ 372 match_next: 373 assert(t > 0); 374 assert(t < 4); 375 NEED_OP(t); 376 NEED_IP(t+1); 377#if 0 378 do *op++ = *ip++; while (--t > 0); 379#else 380 *op++ = *ip++; 381 if (t > 1) { 382 *op++ = *ip++; 383 if (t > 2) 384 *op++ = *ip++; 385 } 386#endif 387 t = *ip++; 388 } while (TEST_IP && TEST_OP); 389 } 390 391//#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP) 392 /* no EOF code was found */ 393 *out_len = pd(op, out); 394 return LZO_E_EOF_NOT_FOUND; 395//#endif 396 397 eof_found: 398 assert(t == 1); 399 *out_len = pd(op, out); 400 return (ip == ip_end ? LZO_E_OK : 401 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 402 403//#if defined(HAVE_NEED_IP) 404 input_overrun: 405 *out_len = pd(op, out); 406 return LZO_E_INPUT_OVERRUN; 407//#endif 408 409//#if defined(HAVE_NEED_OP) 410 output_overrun: 411 *out_len = pd(op, out); 412 return LZO_E_OUTPUT_OVERRUN; 413//#endif 414 415//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND) 416 lookbehind_overrun: 417 *out_len = pd(op, out); 418 return LZO_E_LOOKBEHIND_OVERRUN; 419//#endif 420} 421