Mercurial > hg > toybox
comparison toys/pending/xzcat.c @ 855:88060f1ff4a4
Convert tabs to spaces.
author | Rob Landley <rob@landley.net> |
---|---|
date | Fri, 12 Apr 2013 20:12:02 -0500 |
parents | 68cdd244f8b1 |
children | b4faf2ae39e8 |
comparison
equal
deleted
inserted
replaced
854:68cdd244f8b1 | 855:88060f1ff4a4 |
---|---|
45 * modes at compile time by defining XZ_DEC_SINGLE, XZ_DEC_PREALLOC, | 45 * modes at compile time by defining XZ_DEC_SINGLE, XZ_DEC_PREALLOC, |
46 * or XZ_DEC_DYNALLOC. xzcat uses only XZ_DEC_DYNALLOC, | 46 * or XZ_DEC_DYNALLOC. xzcat uses only XZ_DEC_DYNALLOC, |
47 * so that is the default. | 47 * so that is the default. |
48 */ | 48 */ |
49 enum xz_mode { | 49 enum xz_mode { |
50 XZ_SINGLE, | 50 XZ_SINGLE, |
51 XZ_PREALLOC, | 51 XZ_PREALLOC, |
52 XZ_DYNALLOC | 52 XZ_DYNALLOC |
53 }; | 53 }; |
54 | 54 |
55 /** | 55 /** |
56 * enum xz_ret - Return codes | 56 * enum xz_ret - Return codes |
57 * @XZ_OK: Everything is OK so far. More input or more | 57 * @XZ_OK: Everything is OK so far. More input or more |
101 * decoder produce more output than the caller expected. When it is | 101 * decoder produce more output than the caller expected. When it is |
102 * (relatively) clear that the compressed input is truncated, XZ_DATA_ERROR | 102 * (relatively) clear that the compressed input is truncated, XZ_DATA_ERROR |
103 * is used instead of XZ_BUF_ERROR. | 103 * is used instead of XZ_BUF_ERROR. |
104 */ | 104 */ |
105 enum xz_ret { | 105 enum xz_ret { |
106 XZ_OK, | 106 XZ_OK, |
107 XZ_STREAM_END, | 107 XZ_STREAM_END, |
108 XZ_UNSUPPORTED_CHECK, | 108 XZ_UNSUPPORTED_CHECK, |
109 XZ_MEM_ERROR, | 109 XZ_MEM_ERROR, |
110 XZ_MEMLIMIT_ERROR, | 110 XZ_MEMLIMIT_ERROR, |
111 XZ_FORMAT_ERROR, | 111 XZ_FORMAT_ERROR, |
112 XZ_OPTIONS_ERROR, | 112 XZ_OPTIONS_ERROR, |
113 XZ_DATA_ERROR, | 113 XZ_DATA_ERROR, |
114 XZ_BUF_ERROR | 114 XZ_BUF_ERROR |
115 }; | 115 }; |
116 | 116 |
117 /** | 117 /** |
118 * struct xz_buf - Passing input and output buffers to XZ code | 118 * struct xz_buf - Passing input and output buffers to XZ code |
119 * @in: Beginning of the input buffer. This may be NULL if and only | 119 * @in: Beginning of the input buffer. This may be NULL if and only |
129 * | 129 * |
130 * Only the contents of the output buffer from out[out_pos] onward, and | 130 * Only the contents of the output buffer from out[out_pos] onward, and |
131 * the variables in_pos and out_pos are modified by the XZ code. | 131 * the variables in_pos and out_pos are modified by the XZ code. |
132 */ | 132 */ |
133 struct xz_buf { | 133 struct xz_buf { |
134 const uint8_t *in; | 134 const uint8_t *in; |
135 size_t in_pos; | 135 size_t in_pos; |
136 size_t in_size; | 136 size_t in_size; |
137 | 137 |
138 uint8_t *out; | 138 uint8_t *out; |
139 size_t out_pos; | 139 size_t out_pos; |
140 size_t out_size; | 140 size_t out_size; |
141 }; | 141 }; |
142 | 142 |
143 /** | 143 /** |
144 * struct xz_dec - Opaque type to hold the XZ decoder state | 144 * struct xz_dec - Opaque type to hold the XZ decoder state |
145 */ | 145 */ |
237 */ | 237 */ |
238 static uint32_t xz_crc32_table[256]; | 238 static uint32_t xz_crc32_table[256]; |
239 | 239 |
240 uint32_t xz_crc32(const uint8_t *buf, size_t size, uint32_t crc) | 240 uint32_t xz_crc32(const uint8_t *buf, size_t size, uint32_t crc) |
241 { | 241 { |
242 crc = ~crc; | 242 crc = ~crc; |
243 | 243 |
244 while (size != 0) { | 244 while (size != 0) { |
245 crc = xz_crc32_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8); | 245 crc = xz_crc32_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8); |
246 --size; | 246 --size; |
247 } | 247 } |
248 | 248 |
249 return ~crc; | 249 return ~crc; |
250 } | 250 } |
251 | 251 |
252 /* | 252 /* |
253 * This must be called before any other xz_* function (but after crc_init()) | 253 * This must be called before any other xz_* function (but after crc_init()) |
254 * to initialize the CRC64 lookup table. | 254 * to initialize the CRC64 lookup table. |
255 */ | 255 */ |
256 static uint64_t xz_crc64_table[256]; | 256 static uint64_t xz_crc64_table[256]; |
257 | 257 |
258 void xz_crc64_init(void) | 258 void xz_crc64_init(void) |
259 { | 259 { |
260 const uint64_t poly = 0xC96C5795D7870F42ULL; | 260 const uint64_t poly = 0xC96C5795D7870F42ULL; |
261 | 261 |
262 uint32_t i; | 262 uint32_t i; |
263 uint32_t j; | 263 uint32_t j; |
264 uint64_t r; | 264 uint64_t r; |
265 | 265 |
266 for (i = 0; i < 256; ++i) { | 266 for (i = 0; i < 256; ++i) { |
267 r = i; | 267 r = i; |
268 for (j = 0; j < 8; ++j) | 268 for (j = 0; j < 8; ++j) |
269 r = (r >> 1) ^ (poly & ~((r & 1) - 1)); | 269 r = (r >> 1) ^ (poly & ~((r & 1) - 1)); |
270 | 270 |
271 xz_crc64_table[i] = r; | 271 xz_crc64_table[i] = r; |
272 } | 272 } |
273 | 273 |
274 return; | 274 return; |
275 } | 275 } |
276 | 276 |
277 /* | 277 /* |
278 * Update CRC64 value using the polynomial from ECMA-182. To start a new | 278 * Update CRC64 value using the polynomial from ECMA-182. To start a new |
279 * calculation, the third argument must be zero. To continue the calculation, | 279 * calculation, the third argument must be zero. To continue the calculation, |
280 * the previously returned value is passed as the third argument. | 280 * the previously returned value is passed as the third argument. |
281 */ | 281 */ |
282 uint64_t xz_crc64(const uint8_t *buf, size_t size, uint64_t crc) | 282 uint64_t xz_crc64(const uint8_t *buf, size_t size, uint64_t crc) |
283 { | 283 { |
284 crc = ~crc; | 284 crc = ~crc; |
285 | 285 |
286 while (size != 0) { | 286 while (size != 0) { |
287 crc = xz_crc64_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8); | 287 crc = xz_crc64_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8); |
288 --size; | 288 --size; |
289 } | 289 } |
290 | 290 |
291 return ~crc; | 291 return ~crc; |
292 } | 292 } |
293 | 293 |
294 // END xz.h | 294 // END xz.h |
295 | 295 |
296 static uint8_t in[BUFSIZ]; | 296 static uint8_t in[BUFSIZ]; |
297 static uint8_t out[BUFSIZ]; | 297 static uint8_t out[BUFSIZ]; |
298 | 298 |
299 void xzcat_main(void) | 299 void xzcat_main(void) |
300 { | 300 { |
301 struct xz_buf b; | 301 struct xz_buf b; |
302 struct xz_dec *s; | 302 struct xz_dec *s; |
303 enum xz_ret ret; | 303 enum xz_ret ret; |
304 const char *msg; | 304 const char *msg; |
305 | 305 |
306 crc_init(xz_crc32_table, 1); | 306 crc_init(xz_crc32_table, 1); |
307 xz_crc64_init(); | 307 xz_crc64_init(); |
308 | 308 |
309 /* | 309 /* |
310 * Support up to 64 MiB dictionary. The actually needed memory | 310 * Support up to 64 MiB dictionary. The actually needed memory |
311 * is allocated once the headers have been parsed. | 311 * is allocated once the headers have been parsed. |
312 */ | 312 */ |
313 s = xz_dec_init(XZ_DYNALLOC, 1 << 26); | 313 s = xz_dec_init(XZ_DYNALLOC, 1 << 26); |
314 if (s == NULL) { | 314 if (s == NULL) { |
315 msg = "Memory allocation failed\n"; | 315 msg = "Memory allocation failed\n"; |
316 goto error; | 316 goto error; |
317 } | 317 } |
318 | 318 |
319 b.in = in; | 319 b.in = in; |
320 b.in_pos = 0; | 320 b.in_pos = 0; |
321 b.in_size = 0; | 321 b.in_size = 0; |
322 b.out = out; | 322 b.out = out; |
323 b.out_pos = 0; | 323 b.out_pos = 0; |
324 b.out_size = BUFSIZ; | 324 b.out_size = BUFSIZ; |
325 | 325 |
326 for (;;) { | 326 for (;;) { |
327 if (b.in_pos == b.in_size) { | 327 if (b.in_pos == b.in_size) { |
328 b.in_size = fread(in, 1, sizeof(in), stdin); | 328 b.in_size = fread(in, 1, sizeof(in), stdin); |
329 b.in_pos = 0; | 329 b.in_pos = 0; |
330 } | 330 } |
331 | 331 |
332 ret = xz_dec_run(s, &b); | 332 ret = xz_dec_run(s, &b); |
333 | 333 |
334 if (b.out_pos == sizeof(out)) { | 334 if (b.out_pos == sizeof(out)) { |
335 if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos) { | 335 if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos) { |
336 msg = "Write error\n"; | 336 msg = "Write error\n"; |
337 goto error; | 337 goto error; |
338 } | 338 } |
339 | 339 |
340 b.out_pos = 0; | 340 b.out_pos = 0; |
341 } | 341 } |
342 | 342 |
343 if (ret == XZ_OK) | 343 if (ret == XZ_OK) |
344 continue; | 344 continue; |
345 | 345 |
346 if (ret == XZ_UNSUPPORTED_CHECK) | 346 if (ret == XZ_UNSUPPORTED_CHECK) |
347 continue; | 347 continue; |
348 | 348 |
349 if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos | 349 if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos |
350 || fclose(stdout)) { | 350 || fclose(stdout)) { |
351 msg = "Write error\n"; | 351 msg = "Write error\n"; |
352 goto error; | 352 goto error; |
353 } | 353 } |
354 | 354 |
355 switch (ret) { | 355 switch (ret) { |
356 case XZ_STREAM_END: | 356 case XZ_STREAM_END: |
357 xz_dec_end(s); | 357 xz_dec_end(s); |
358 return; | 358 return; |
359 | 359 |
360 case XZ_MEM_ERROR: | 360 case XZ_MEM_ERROR: |
361 msg = "Memory allocation failed\n"; | 361 msg = "Memory allocation failed\n"; |
362 goto error; | 362 goto error; |
363 | 363 |
364 case XZ_MEMLIMIT_ERROR: | 364 case XZ_MEMLIMIT_ERROR: |
365 msg = "Memory usage limit reached\n"; | 365 msg = "Memory usage limit reached\n"; |
366 goto error; | 366 goto error; |
367 | 367 |
368 case XZ_FORMAT_ERROR: | 368 case XZ_FORMAT_ERROR: |
369 msg = "Not a .xz file\n"; | 369 msg = "Not a .xz file\n"; |
370 goto error; | 370 goto error; |
371 | 371 |
372 case XZ_OPTIONS_ERROR: | 372 case XZ_OPTIONS_ERROR: |
373 msg = "Unsupported options in the .xz headers\n"; | 373 msg = "Unsupported options in the .xz headers\n"; |
374 goto error; | 374 goto error; |
375 | 375 |
376 case XZ_DATA_ERROR: | 376 case XZ_DATA_ERROR: |
377 case XZ_BUF_ERROR: | 377 case XZ_BUF_ERROR: |
378 msg = "File is corrupt\n"; | 378 msg = "File is corrupt\n"; |
379 goto error; | 379 goto error; |
380 | 380 |
381 default: | 381 default: |
382 msg = "Bug!\n"; | 382 msg = "Bug!\n"; |
383 goto error; | 383 goto error; |
384 } | 384 } |
385 } | 385 } |
386 | 386 |
387 error: | 387 error: |
388 xz_dec_end(s); | 388 xz_dec_end(s); |
389 error_exit("%s", msg); | 389 error_exit("%s", msg); |
390 } | 390 } |
391 | 391 |
392 // BEGIN xz_private.h | 392 // BEGIN xz_private.h |
393 | 393 |
394 | 394 |
414 | 414 |
415 /* Inline functions to access unaligned unsigned 32-bit integers */ | 415 /* Inline functions to access unaligned unsigned 32-bit integers */ |
416 #ifndef get_unaligned_le32 | 416 #ifndef get_unaligned_le32 |
417 static inline uint32_t get_unaligned_le32(const uint8_t *buf) | 417 static inline uint32_t get_unaligned_le32(const uint8_t *buf) |
418 { | 418 { |
419 return (uint32_t)buf[0] | 419 return (uint32_t)buf[0] |
420 | ((uint32_t)buf[1] << 8) | 420 | ((uint32_t)buf[1] << 8) |
421 | ((uint32_t)buf[2] << 16) | 421 | ((uint32_t)buf[2] << 16) |
422 | ((uint32_t)buf[3] << 24); | 422 | ((uint32_t)buf[3] << 24); |
423 } | 423 } |
424 #endif | 424 #endif |
425 | 425 |
426 #ifndef get_unaligned_be32 | 426 #ifndef get_unaligned_be32 |
427 static inline uint32_t get_unaligned_be32(const uint8_t *buf) | 427 static inline uint32_t get_unaligned_be32(const uint8_t *buf) |
428 { | 428 { |
429 return (uint32_t)(buf[0] << 24) | 429 return (uint32_t)(buf[0] << 24) |
430 | ((uint32_t)buf[1] << 16) | 430 | ((uint32_t)buf[1] << 16) |
431 | ((uint32_t)buf[2] << 8) | 431 | ((uint32_t)buf[2] << 8) |
432 | (uint32_t)buf[3]; | 432 | (uint32_t)buf[3]; |
433 } | 433 } |
434 #endif | 434 #endif |
435 | 435 |
436 #ifndef put_unaligned_le32 | 436 #ifndef put_unaligned_le32 |
437 static inline void put_unaligned_le32(uint32_t val, uint8_t *buf) | 437 static inline void put_unaligned_le32(uint32_t val, uint8_t *buf) |
438 { | 438 { |
439 buf[0] = (uint8_t)val; | 439 buf[0] = (uint8_t)val; |
440 buf[1] = (uint8_t)(val >> 8); | 440 buf[1] = (uint8_t)(val >> 8); |
441 buf[2] = (uint8_t)(val >> 16); | 441 buf[2] = (uint8_t)(val >> 16); |
442 buf[3] = (uint8_t)(val >> 24); | 442 buf[3] = (uint8_t)(val >> 24); |
443 } | 443 } |
444 #endif | 444 #endif |
445 | 445 |
446 #ifndef put_unaligned_be32 | 446 #ifndef put_unaligned_be32 |
447 static inline void put_unaligned_be32(uint32_t val, uint8_t *buf) | 447 static inline void put_unaligned_be32(uint32_t val, uint8_t *buf) |
448 { | 448 { |
449 buf[0] = (uint8_t)(val >> 24); | 449 buf[0] = (uint8_t)(val >> 24); |
450 buf[1] = (uint8_t)(val >> 16); | 450 buf[1] = (uint8_t)(val >> 16); |
451 buf[2] = (uint8_t)(val >> 8); | 451 buf[2] = (uint8_t)(val >> 8); |
452 buf[3] = (uint8_t)val; | 452 buf[3] = (uint8_t)val; |
453 } | 453 } |
454 #endif | 454 #endif |
455 | 455 |
456 /* | 456 /* |
457 * Use get_unaligned_le32() also for aligned access for simplicity. On | 457 * Use get_unaligned_le32() also for aligned access for simplicity. On |
504 * If any of the BCJ filter decoders are wanted, define XZ_DEC_BCJ. | 504 * If any of the BCJ filter decoders are wanted, define XZ_DEC_BCJ. |
505 * XZ_DEC_BCJ is used to enable generic support for BCJ decoders. | 505 * XZ_DEC_BCJ is used to enable generic support for BCJ decoders. |
506 */ | 506 */ |
507 #ifndef XZ_DEC_BCJ | 507 #ifndef XZ_DEC_BCJ |
508 # if defined(XZ_DEC_X86) || defined(XZ_DEC_POWERPC) \ | 508 # if defined(XZ_DEC_X86) || defined(XZ_DEC_POWERPC) \ |
509 || defined(XZ_DEC_IA64) || defined(XZ_DEC_ARM) \ | 509 || defined(XZ_DEC_IA64) || defined(XZ_DEC_ARM) \ |
510 || defined(XZ_DEC_ARM) || defined(XZ_DEC_ARMTHUMB) \ | 510 || defined(XZ_DEC_ARM) || defined(XZ_DEC_ARMTHUMB) \ |
511 || defined(XZ_DEC_SPARC) | 511 || defined(XZ_DEC_SPARC) |
512 # define XZ_DEC_BCJ | 512 # define XZ_DEC_BCJ |
513 # endif | 513 # endif |
514 #endif | 514 #endif |
515 | 515 |
516 /* | 516 /* |
517 * Allocate memory for LZMA2 decoder. xz_dec_lzma2_reset() must be used | 517 * Allocate memory for LZMA2 decoder. xz_dec_lzma2_reset() must be used |
518 * before calling xz_dec_lzma2_run(). | 518 * before calling xz_dec_lzma2_run(). |
519 */ | 519 */ |
520 struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode, | 520 struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode, |
521 uint32_t dict_max); | 521 uint32_t dict_max); |
522 | 522 |
523 /* | 523 /* |
524 * Decode the LZMA2 properties (one byte) and reset the decoder. Return | 524 * Decode the LZMA2 properties (one byte) and reset the decoder. Return |
525 * XZ_OK on success, XZ_MEMLIMIT_ERROR if the preallocated dictionary is not | 525 * XZ_OK on success, XZ_MEMLIMIT_ERROR if the preallocated dictionary is not |
526 * big enough, and XZ_OPTIONS_ERROR if props indicates something that this | 526 * big enough, and XZ_OPTIONS_ERROR if props indicates something that this |
527 * decoder doesn't support. | 527 * decoder doesn't support. |
528 */ | 528 */ |
529 enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, | 529 enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, |
530 uint8_t props); | 530 uint8_t props); |
531 | 531 |
532 /* Decode raw LZMA2 stream from b->in to b->out. */ | 532 /* Decode raw LZMA2 stream from b->in to b->out. */ |
533 enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, | 533 enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, |
534 struct xz_buf *b); | 534 struct xz_buf *b); |
535 | 535 |
536 #ifdef XZ_DEC_BCJ | 536 #ifdef XZ_DEC_BCJ |
537 /* | 537 /* |
538 * Allocate memory for BCJ decoders. xz_dec_bcj_reset() must be used before | 538 * Allocate memory for BCJ decoders. xz_dec_bcj_reset() must be used before |
539 * calling xz_dec_bcj_run(). | 539 * calling xz_dec_bcj_run(). |
552 * Decode raw BCJ + LZMA2 stream. This must be used only if there actually is | 552 * Decode raw BCJ + LZMA2 stream. This must be used only if there actually is |
553 * a BCJ filter in the chain. If the chain has only LZMA2, xz_dec_lzma2_run() | 553 * a BCJ filter in the chain. If the chain has only LZMA2, xz_dec_lzma2_run() |
554 * must be called directly. | 554 * must be called directly. |
555 */ | 555 */ |
556 enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s, | 556 enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s, |
557 struct xz_dec_lzma2 *lzma2, | 557 struct xz_dec_lzma2 *lzma2, |
558 struct xz_buf *b); | 558 struct xz_buf *b); |
559 #endif | 559 #endif |
560 | 560 |
561 // END "xz_private.h" | 561 // END "xz_private.h" |
562 | 562 |
563 | 563 |
569 * convenient when building without support for any BCJ filters. | 569 * convenient when building without support for any BCJ filters. |
570 */ | 570 */ |
571 #ifdef XZ_DEC_BCJ | 571 #ifdef XZ_DEC_BCJ |
572 | 572 |
573 struct xz_dec_bcj { | 573 struct xz_dec_bcj { |
574 /* Type of the BCJ filter being used */ | 574 /* Type of the BCJ filter being used */ |
575 enum { | 575 enum { |
576 BCJ_X86 = 4, /* x86 or x86-64 */ | 576 BCJ_X86 = 4, /* x86 or x86-64 */ |
577 BCJ_POWERPC = 5, /* Big endian only */ | 577 BCJ_POWERPC = 5, /* Big endian only */ |
578 BCJ_IA64 = 6, /* Big or little endian */ | 578 BCJ_IA64 = 6, /* Big or little endian */ |
579 BCJ_ARM = 7, /* Little endian only */ | 579 BCJ_ARM = 7, /* Little endian only */ |
580 BCJ_ARMTHUMB = 8, /* Little endian only */ | 580 BCJ_ARMTHUMB = 8, /* Little endian only */ |
581 BCJ_SPARC = 9 /* Big or little endian */ | 581 BCJ_SPARC = 9 /* Big or little endian */ |
582 } type; | 582 } type; |
583 | 583 |
584 /* | 584 /* |
585 * Return value of the next filter in the chain. We need to preserve | 585 * Return value of the next filter in the chain. We need to preserve |
586 * this information across calls, because we must not call the next | 586 * this information across calls, because we must not call the next |
587 * filter anymore once it has returned XZ_STREAM_END. | 587 * filter anymore once it has returned XZ_STREAM_END. |
588 */ | 588 */ |
589 enum xz_ret ret; | 589 enum xz_ret ret; |
590 | 590 |
591 /* True if we are operating in single-call mode. */ | 591 /* True if we are operating in single-call mode. */ |
592 int single_call; | 592 int single_call; |
593 | 593 |
594 /* | 594 /* |
595 * Absolute position relative to the beginning of the uncompressed | 595 * Absolute position relative to the beginning of the uncompressed |
596 * data (in a single .xz Block). We care only about the lowest 32 | 596 * data (in a single .xz Block). We care only about the lowest 32 |
597 * bits so this doesn't need to be uint64_t even with big files. | 597 * bits so this doesn't need to be uint64_t even with big files. |
598 */ | 598 */ |
599 uint32_t pos; | 599 uint32_t pos; |
600 | 600 |
601 /* x86 filter state */ | 601 /* x86 filter state */ |
602 uint32_t x86_prev_mask; | 602 uint32_t x86_prev_mask; |
603 | 603 |
604 /* Temporary space to hold the variables from struct xz_buf */ | 604 /* Temporary space to hold the variables from struct xz_buf */ |
605 uint8_t *out; | 605 uint8_t *out; |
606 size_t out_pos; | 606 size_t out_pos; |
607 size_t out_size; | 607 size_t out_size; |
608 | 608 |
609 struct { | 609 struct { |
610 /* Amount of already filtered data in the beginning of buf */ | 610 /* Amount of already filtered data in the beginning of buf */ |
611 size_t filtered; | 611 size_t filtered; |
612 | 612 |
613 /* Total amount of data currently stored in buf */ | 613 /* Total amount of data currently stored in buf */ |
614 size_t size; | 614 size_t size; |
615 | 615 |
616 /* | 616 /* |
617 * Buffer to hold a mix of filtered and unfiltered data. This | 617 * Buffer to hold a mix of filtered and unfiltered data. This |
618 * needs to be big enough to hold Alignment + 2 * Look-ahead: | 618 * needs to be big enough to hold Alignment + 2 * Look-ahead: |
619 * | 619 * |
620 * Type Alignment Look-ahead | 620 * Type Alignment Look-ahead |
621 * x86 1 4 | 621 * x86 1 4 |
622 * PowerPC 4 0 | 622 * PowerPC 4 0 |
623 * IA-64 16 0 | 623 * IA-64 16 0 |
624 * ARM 4 0 | 624 * ARM 4 0 |
625 * ARM-Thumb 2 2 | 625 * ARM-Thumb 2 2 |
626 * SPARC 4 0 | 626 * SPARC 4 0 |
627 */ | 627 */ |
628 uint8_t buf[16]; | 628 uint8_t buf[16]; |
629 } temp; | 629 } temp; |
630 }; | 630 }; |
631 | 631 |
632 #ifdef XZ_DEC_X86 | 632 #ifdef XZ_DEC_X86 |
633 /* | 633 /* |
634 * This is used to test the most significant byte of a memory address | 634 * This is used to test the most significant byte of a memory address |
635 * in an x86 instruction. | 635 * in an x86 instruction. |
636 */ | 636 */ |
637 static inline int bcj_x86_test_msbyte(uint8_t b) | 637 static inline int bcj_x86_test_msbyte(uint8_t b) |
638 { | 638 { |
639 return b == 0x00 || b == 0xFF; | 639 return b == 0x00 || b == 0xFF; |
640 } | 640 } |
641 | 641 |
642 static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | 642 static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size) |
643 { | 643 { |
644 static const int mask_to_allowed_status[8] | 644 static const int mask_to_allowed_status[8] |
645 = { 1,1,1,0,1,0,0,0 }; | 645 = { 1,1,1,0,1,0,0,0 }; |
646 | 646 |
647 static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 }; | 647 static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 }; |
648 | 648 |
649 size_t i; | 649 size_t i; |
650 size_t prev_pos = (size_t)-1; | 650 size_t prev_pos = (size_t)-1; |
651 uint32_t prev_mask = s->x86_prev_mask; | 651 uint32_t prev_mask = s->x86_prev_mask; |
652 uint32_t src; | 652 uint32_t src; |
653 uint32_t dest; | 653 uint32_t dest; |
654 uint32_t j; | 654 uint32_t j; |
655 uint8_t b; | 655 uint8_t b; |
656 | 656 |
657 if (size <= 4) | 657 if (size <= 4) |
658 return 0; | 658 return 0; |
659 | 659 |
660 size -= 4; | 660 size -= 4; |
661 for (i = 0; i < size; ++i) { | 661 for (i = 0; i < size; ++i) { |
662 if ((buf[i] & 0xFE) != 0xE8) | 662 if ((buf[i] & 0xFE) != 0xE8) |
663 continue; | 663 continue; |
664 | 664 |
665 prev_pos = i - prev_pos; | 665 prev_pos = i - prev_pos; |
666 if (prev_pos > 3) { | 666 if (prev_pos > 3) { |
667 prev_mask = 0; | 667 prev_mask = 0; |
668 } else { | 668 } else { |
669 prev_mask = (prev_mask << (prev_pos - 1)) & 7; | 669 prev_mask = (prev_mask << (prev_pos - 1)) & 7; |
670 if (prev_mask != 0) { | 670 if (prev_mask != 0) { |
671 b = buf[i + 4 - mask_to_bit_num[prev_mask]]; | 671 b = buf[i + 4 - mask_to_bit_num[prev_mask]]; |
672 if (!mask_to_allowed_status[prev_mask] | 672 if (!mask_to_allowed_status[prev_mask] |
673 || bcj_x86_test_msbyte(b)) { | 673 || bcj_x86_test_msbyte(b)) { |
674 prev_pos = i; | 674 prev_pos = i; |
675 prev_mask = (prev_mask << 1) | 1; | 675 prev_mask = (prev_mask << 1) | 1; |
676 continue; | 676 continue; |
677 } | 677 } |
678 } | 678 } |
679 } | 679 } |
680 | 680 |
681 prev_pos = i; | 681 prev_pos = i; |
682 | 682 |
683 if (bcj_x86_test_msbyte(buf[i + 4])) { | 683 if (bcj_x86_test_msbyte(buf[i + 4])) { |
684 src = get_unaligned_le32(buf + i + 1); | 684 src = get_unaligned_le32(buf + i + 1); |
685 for (;;) { | 685 for (;;) { |
686 dest = src - (s->pos + (uint32_t)i + 5); | 686 dest = src - (s->pos + (uint32_t)i + 5); |
687 if (prev_mask == 0) | 687 if (prev_mask == 0) |
688 break; | 688 break; |
689 | 689 |
690 j = mask_to_bit_num[prev_mask] * 8; | 690 j = mask_to_bit_num[prev_mask] * 8; |
691 b = (uint8_t)(dest >> (24 - j)); | 691 b = (uint8_t)(dest >> (24 - j)); |
692 if (!bcj_x86_test_msbyte(b)) | 692 if (!bcj_x86_test_msbyte(b)) |
693 break; | 693 break; |
694 | 694 |
695 src = dest ^ (((uint32_t)1 << (32 - j)) - 1); | 695 src = dest ^ (((uint32_t)1 << (32 - j)) - 1); |
696 } | 696 } |
697 | 697 |
698 dest &= 0x01FFFFFF; | 698 dest &= 0x01FFFFFF; |
699 dest |= (uint32_t)0 - (dest & 0x01000000); | 699 dest |= (uint32_t)0 - (dest & 0x01000000); |
700 put_unaligned_le32(dest, buf + i + 1); | 700 put_unaligned_le32(dest, buf + i + 1); |
701 i += 4; | 701 i += 4; |
702 } else { | 702 } else { |
703 prev_mask = (prev_mask << 1) | 1; | 703 prev_mask = (prev_mask << 1) | 1; |
704 } | 704 } |
705 } | 705 } |
706 | 706 |
707 prev_pos = i - prev_pos; | 707 prev_pos = i - prev_pos; |
708 s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1); | 708 s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1); |
709 return i; | 709 return i; |
710 } | 710 } |
711 #endif | 711 #endif |
712 | 712 |
713 #ifdef XZ_DEC_POWERPC | 713 #ifdef XZ_DEC_POWERPC |
714 static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | 714 static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size) |
715 { | 715 { |
716 size_t i; | 716 size_t i; |
717 uint32_t instr; | 717 uint32_t instr; |
718 | 718 |
719 for (i = 0; i + 4 <= size; i += 4) { | 719 for (i = 0; i + 4 <= size; i += 4) { |
720 instr = get_unaligned_be32(buf + i); | 720 instr = get_unaligned_be32(buf + i); |
721 if ((instr & 0xFC000003) == 0x48000001) { | 721 if ((instr & 0xFC000003) == 0x48000001) { |
722 instr &= 0x03FFFFFC; | 722 instr &= 0x03FFFFFC; |
723 instr -= s->pos + (uint32_t)i; | 723 instr -= s->pos + (uint32_t)i; |
724 instr &= 0x03FFFFFC; | 724 instr &= 0x03FFFFFC; |
725 instr |= 0x48000001; | 725 instr |= 0x48000001; |
726 put_unaligned_be32(instr, buf + i); | 726 put_unaligned_be32(instr, buf + i); |
727 } | 727 } |
728 } | 728 } |
729 | 729 |
730 return i; | 730 return i; |
731 } | 731 } |
732 #endif | 732 #endif |
733 | 733 |
734 #ifdef XZ_DEC_IA64 | 734 #ifdef XZ_DEC_IA64 |
735 static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | 735 static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size) |
736 { | 736 { |
737 static const uint8_t branch_table[32] = { | 737 static const uint8_t branch_table[32] = { |
738 0, 0, 0, 0, 0, 0, 0, 0, | 738 0, 0, 0, 0, 0, 0, 0, 0, |
739 0, 0, 0, 0, 0, 0, 0, 0, | 739 0, 0, 0, 0, 0, 0, 0, 0, |
740 4, 4, 6, 6, 0, 0, 7, 7, | 740 4, 4, 6, 6, 0, 0, 7, 7, |
741 4, 4, 0, 0, 4, 4, 0, 0 | 741 4, 4, 0, 0, 4, 4, 0, 0 |
742 }; | 742 }; |
743 | 743 |
744 /* | 744 /* |
745 * The local variables take a little bit stack space, but it's less | 745 * The local variables take a little bit stack space, but it's less |
746 * than what LZMA2 decoder takes, so it doesn't make sense to reduce | 746 * than what LZMA2 decoder takes, so it doesn't make sense to reduce |
747 * stack usage here without doing that for the LZMA2 decoder too. | 747 * stack usage here without doing that for the LZMA2 decoder too. |
748 */ | 748 */ |
749 | 749 |
750 /* Loop counters */ | 750 /* Loop counters */ |
751 size_t i; | 751 size_t i; |
752 size_t j; | 752 size_t j; |
753 | 753 |
754 /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */ | 754 /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */ |
755 uint32_t slot; | 755 uint32_t slot; |
756 | 756 |
757 /* Bitwise offset of the instruction indicated by slot */ | 757 /* Bitwise offset of the instruction indicated by slot */ |
758 uint32_t bit_pos; | 758 uint32_t bit_pos; |
759 | 759 |
760 /* bit_pos split into byte and bit parts */ | 760 /* bit_pos split into byte and bit parts */ |
761 uint32_t byte_pos; | 761 uint32_t byte_pos; |
762 uint32_t bit_res; | 762 uint32_t bit_res; |
763 | 763 |
764 /* Address part of an instruction */ | 764 /* Address part of an instruction */ |
765 uint32_t addr; | 765 uint32_t addr; |
766 | 766 |
767 /* Mask used to detect which instructions to convert */ | 767 /* Mask used to detect which instructions to convert */ |
768 uint32_t mask; | 768 uint32_t mask; |
769 | 769 |
770 /* 41-bit instruction stored somewhere in the lowest 48 bits */ | 770 /* 41-bit instruction stored somewhere in the lowest 48 bits */ |
771 uint64_t instr; | 771 uint64_t instr; |
772 | 772 |
773 /* Instruction normalized with bit_res for easier manipulation */ | 773 /* Instruction normalized with bit_res for easier manipulation */ |
774 uint64_t norm; | 774 uint64_t norm; |
775 | 775 |
776 for (i = 0; i + 16 <= size; i += 16) { | 776 for (i = 0; i + 16 <= size; i += 16) { |
777 mask = branch_table[buf[i] & 0x1F]; | 777 mask = branch_table[buf[i] & 0x1F]; |
778 for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) { | 778 for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) { |
779 if (((mask >> slot) & 1) == 0) | 779 if (((mask >> slot) & 1) == 0) |
780 continue; | 780 continue; |
781 | 781 |
782 byte_pos = bit_pos >> 3; | 782 byte_pos = bit_pos >> 3; |
783 bit_res = bit_pos & 7; | 783 bit_res = bit_pos & 7; |
784 instr = 0; | 784 instr = 0; |
785 for (j = 0; j < 6; ++j) | 785 for (j = 0; j < 6; ++j) |
786 instr |= (uint64_t)(buf[i + j + byte_pos]) | 786 instr |= (uint64_t)(buf[i + j + byte_pos]) |
787 << (8 * j); | 787 << (8 * j); |
788 | 788 |
789 norm = instr >> bit_res; | 789 norm = instr >> bit_res; |
790 | 790 |
791 if (((norm >> 37) & 0x0F) == 0x05 | 791 if (((norm >> 37) & 0x0F) == 0x05 |
792 && ((norm >> 9) & 0x07) == 0) { | 792 && ((norm >> 9) & 0x07) == 0) { |
793 addr = (norm >> 13) & 0x0FFFFF; | 793 addr = (norm >> 13) & 0x0FFFFF; |
794 addr |= ((uint32_t)(norm >> 36) & 1) << 20; | 794 addr |= ((uint32_t)(norm >> 36) & 1) << 20; |
795 addr <<= 4; | 795 addr <<= 4; |
796 addr -= s->pos + (uint32_t)i; | 796 addr -= s->pos + (uint32_t)i; |
797 addr >>= 4; | 797 addr >>= 4; |
798 | 798 |
799 norm &= ~((uint64_t)0x8FFFFF << 13); | 799 norm &= ~((uint64_t)0x8FFFFF << 13); |
800 norm |= (uint64_t)(addr & 0x0FFFFF) << 13; | 800 norm |= (uint64_t)(addr & 0x0FFFFF) << 13; |
801 norm |= (uint64_t)(addr & 0x100000) | 801 norm |= (uint64_t)(addr & 0x100000) |
802 << (36 - 20); | 802 << (36 - 20); |
803 | 803 |
804 instr &= (1 << bit_res) - 1; | 804 instr &= (1 << bit_res) - 1; |
805 instr |= norm << bit_res; | 805 instr |= norm << bit_res; |
806 | 806 |
807 for (j = 0; j < 6; j++) | 807 for (j = 0; j < 6; j++) |
808 buf[i + j + byte_pos] | 808 buf[i + j + byte_pos] |
809 = (uint8_t)(instr >> (8 * j)); | 809 = (uint8_t)(instr >> (8 * j)); |
810 } | 810 } |
811 } | 811 } |
812 } | 812 } |
813 | 813 |
814 return i; | 814 return i; |
815 } | 815 } |
816 #endif | 816 #endif |
817 | 817 |
818 #ifdef XZ_DEC_ARM | 818 #ifdef XZ_DEC_ARM |
819 static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | 819 static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size) |
820 { | 820 { |
821 size_t i; | 821 size_t i; |
822 uint32_t addr; | 822 uint32_t addr; |
823 | 823 |
824 for (i = 0; i + 4 <= size; i += 4) { | 824 for (i = 0; i + 4 <= size; i += 4) { |
825 if (buf[i + 3] == 0xEB) { | 825 if (buf[i + 3] == 0xEB) { |
826 addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8) | 826 addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8) |
827 | ((uint32_t)buf[i + 2] << 16); | 827 | ((uint32_t)buf[i + 2] << 16); |
828 addr <<= 2; | 828 addr <<= 2; |
829 addr -= s->pos + (uint32_t)i + 8; | 829 addr -= s->pos + (uint32_t)i + 8; |
830 addr >>= 2; | 830 addr >>= 2; |
831 buf[i] = (uint8_t)addr; | 831 buf[i] = (uint8_t)addr; |
832 buf[i + 1] = (uint8_t)(addr >> 8); | 832 buf[i + 1] = (uint8_t)(addr >> 8); |
833 buf[i + 2] = (uint8_t)(addr >> 16); | 833 buf[i + 2] = (uint8_t)(addr >> 16); |
834 } | 834 } |
835 } | 835 } |
836 | 836 |
837 return i; | 837 return i; |
838 } | 838 } |
839 #endif | 839 #endif |
840 | 840 |
841 #ifdef XZ_DEC_ARMTHUMB | 841 #ifdef XZ_DEC_ARMTHUMB |
842 static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | 842 static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size) |
843 { | 843 { |
844 size_t i; | 844 size_t i; |
845 uint32_t addr; | 845 uint32_t addr; |
846 | 846 |
847 for (i = 0; i + 4 <= size; i += 2) { | 847 for (i = 0; i + 4 <= size; i += 2) { |
848 if ((buf[i + 1] & 0xF8) == 0xF0 | 848 if ((buf[i + 1] & 0xF8) == 0xF0 |
849 && (buf[i + 3] & 0xF8) == 0xF8) { | 849 && (buf[i + 3] & 0xF8) == 0xF8) { |
850 addr = (((uint32_t)buf[i + 1] & 0x07) << 19) | 850 addr = (((uint32_t)buf[i + 1] & 0x07) << 19) |
851 | ((uint32_t)buf[i] << 11) | 851 | ((uint32_t)buf[i] << 11) |
852 | (((uint32_t)buf[i + 3] & 0x07) << 8) | 852 | (((uint32_t)buf[i + 3] & 0x07) << 8) |
853 | (uint32_t)buf[i + 2]; | 853 | (uint32_t)buf[i + 2]; |
854 addr <<= 1; | 854 addr <<= 1; |
855 addr -= s->pos + (uint32_t)i + 4; | 855 addr -= s->pos + (uint32_t)i + 4; |
856 addr >>= 1; | 856 addr >>= 1; |
857 buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07)); | 857 buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07)); |
858 buf[i] = (uint8_t)(addr >> 11); | 858 buf[i] = (uint8_t)(addr >> 11); |
859 buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07)); | 859 buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07)); |
860 buf[i + 2] = (uint8_t)addr; | 860 buf[i + 2] = (uint8_t)addr; |
861 i += 2; | 861 i += 2; |
862 } | 862 } |
863 } | 863 } |
864 | 864 |
865 return i; | 865 return i; |
866 } | 866 } |
867 #endif | 867 #endif |
868 | 868 |
869 #ifdef XZ_DEC_SPARC | 869 #ifdef XZ_DEC_SPARC |
870 static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | 870 static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size) |
871 { | 871 { |
872 size_t i; | 872 size_t i; |
873 uint32_t instr; | 873 uint32_t instr; |
874 | 874 |
875 for (i = 0; i + 4 <= size; i += 4) { | 875 for (i = 0; i + 4 <= size; i += 4) { |
876 instr = get_unaligned_be32(buf + i); | 876 instr = get_unaligned_be32(buf + i); |
877 if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) { | 877 if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) { |
878 instr <<= 2; | 878 instr <<= 2; |
879 instr -= s->pos + (uint32_t)i; | 879 instr -= s->pos + (uint32_t)i; |
880 instr >>= 2; | 880 instr >>= 2; |
881 instr = ((uint32_t)0x40000000 - (instr & 0x400000)) | 881 instr = ((uint32_t)0x40000000 - (instr & 0x400000)) |
882 | 0x40000000 | (instr & 0x3FFFFF); | 882 | 0x40000000 | (instr & 0x3FFFFF); |
883 put_unaligned_be32(instr, buf + i); | 883 put_unaligned_be32(instr, buf + i); |
884 } | 884 } |
885 } | 885 } |
886 | 886 |
887 return i; | 887 return i; |
888 } | 888 } |
889 #endif | 889 #endif |
890 | 890 |
891 /* | 891 /* |
892 * Apply the selected BCJ filter. Update *pos and s->pos to match the amount | 892 * Apply the selected BCJ filter. Update *pos and s->pos to match the amount |
895 * NOTE: This is implemented as a switch statement to avoid using function | 895 * NOTE: This is implemented as a switch statement to avoid using function |
896 * pointers, which could be problematic in the kernel boot code, which must | 896 * pointers, which could be problematic in the kernel boot code, which must |
897 * avoid pointers to static data (at least on x86). | 897 * avoid pointers to static data (at least on x86). |
898 */ | 898 */ |
899 static void bcj_apply(struct xz_dec_bcj *s, | 899 static void bcj_apply(struct xz_dec_bcj *s, |
900 uint8_t *buf, size_t *pos, size_t size) | 900 uint8_t *buf, size_t *pos, size_t size) |
901 { | 901 { |
902 size_t filtered; | 902 size_t filtered; |
903 | 903 |
904 buf += *pos; | 904 buf += *pos; |
905 size -= *pos; | 905 size -= *pos; |
906 | 906 |
907 switch (s->type) { | 907 switch (s->type) { |
908 #ifdef XZ_DEC_X86 | 908 #ifdef XZ_DEC_X86 |
909 case BCJ_X86: | 909 case BCJ_X86: |
910 filtered = bcj_x86(s, buf, size); | 910 filtered = bcj_x86(s, buf, size); |
911 break; | 911 break; |
912 #endif | 912 #endif |
913 #ifdef XZ_DEC_POWERPC | 913 #ifdef XZ_DEC_POWERPC |
914 case BCJ_POWERPC: | 914 case BCJ_POWERPC: |
915 filtered = bcj_powerpc(s, buf, size); | 915 filtered = bcj_powerpc(s, buf, size); |
916 break; | 916 break; |
917 #endif | 917 #endif |
918 #ifdef XZ_DEC_IA64 | 918 #ifdef XZ_DEC_IA64 |
919 case BCJ_IA64: | 919 case BCJ_IA64: |
920 filtered = bcj_ia64(s, buf, size); | 920 filtered = bcj_ia64(s, buf, size); |
921 break; | 921 break; |
922 #endif | 922 #endif |
923 #ifdef XZ_DEC_ARM | 923 #ifdef XZ_DEC_ARM |
924 case BCJ_ARM: | 924 case BCJ_ARM: |
925 filtered = bcj_arm(s, buf, size); | 925 filtered = bcj_arm(s, buf, size); |
926 break; | 926 break; |
927 #endif | 927 #endif |
928 #ifdef XZ_DEC_ARMTHUMB | 928 #ifdef XZ_DEC_ARMTHUMB |
929 case BCJ_ARMTHUMB: | 929 case BCJ_ARMTHUMB: |
930 filtered = bcj_armthumb(s, buf, size); | 930 filtered = bcj_armthumb(s, buf, size); |
931 break; | 931 break; |
932 #endif | 932 #endif |
933 #ifdef XZ_DEC_SPARC | 933 #ifdef XZ_DEC_SPARC |
934 case BCJ_SPARC: | 934 case BCJ_SPARC: |
935 filtered = bcj_sparc(s, buf, size); | 935 filtered = bcj_sparc(s, buf, size); |
936 break; | 936 break; |
937 #endif | 937 #endif |
938 default: | 938 default: |
939 /* Never reached but silence compiler warnings. */ | 939 /* Never reached but silence compiler warnings. */ |
940 filtered = 0; | 940 filtered = 0; |
941 break; | 941 break; |
942 } | 942 } |
943 | 943 |
944 *pos += filtered; | 944 *pos += filtered; |
945 s->pos += filtered; | 945 s->pos += filtered; |
946 } | 946 } |
947 | 947 |
948 /* | 948 /* |
949 * Flush pending filtered data from temp to the output buffer. | 949 * Flush pending filtered data from temp to the output buffer. |
950 * Move the remaining mixture of possibly filtered and unfiltered | 950 * Move the remaining mixture of possibly filtered and unfiltered |
951 * data to the beginning of temp. | 951 * data to the beginning of temp. |
952 */ | 952 */ |
953 static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b) | 953 static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b) |
954 { | 954 { |
955 size_t copy_size; | 955 size_t copy_size; |
956 | 956 |
957 copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos); | 957 copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos); |
958 memcpy(b->out + b->out_pos, s->temp.buf, copy_size); | 958 memcpy(b->out + b->out_pos, s->temp.buf, copy_size); |
959 b->out_pos += copy_size; | 959 b->out_pos += copy_size; |
960 | 960 |
961 s->temp.filtered -= copy_size; | 961 s->temp.filtered -= copy_size; |
962 s->temp.size -= copy_size; | 962 s->temp.size -= copy_size; |
963 memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size); | 963 memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size); |
964 } | 964 } |
965 | 965 |
966 /* | 966 /* |
967 * The BCJ filter functions are primitive in sense that they process the | 967 * The BCJ filter functions are primitive in sense that they process the |
968 * data in chunks of 1-16 bytes. To hide this issue, this function does | 968 * data in chunks of 1-16 bytes. To hide this issue, this function does |
969 * some buffering. | 969 * some buffering. |
970 */ | 970 */ |
971 enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s, | 971 enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s, |
972 struct xz_dec_lzma2 *lzma2, | 972 struct xz_dec_lzma2 *lzma2, |
973 struct xz_buf *b) | 973 struct xz_buf *b) |
974 { | 974 { |
975 size_t out_start; | 975 size_t out_start; |
976 | 976 |
977 /* | 977 /* |
978 * Flush pending already filtered data to the output buffer. Return | 978 * Flush pending already filtered data to the output buffer. Return |
979 * immediatelly if we couldn't flush everything, or if the next | 979 * immediatelly if we couldn't flush everything, or if the next |
980 * filter in the chain had already returned XZ_STREAM_END. | 980 * filter in the chain had already returned XZ_STREAM_END. |
981 */ | 981 */ |
982 if (s->temp.filtered > 0) { | 982 if (s->temp.filtered > 0) { |
983 bcj_flush(s, b); | 983 bcj_flush(s, b); |
984 if (s->temp.filtered > 0) | 984 if (s->temp.filtered > 0) |
985 return XZ_OK; | 985 return XZ_OK; |
986 | 986 |
987 if (s->ret == XZ_STREAM_END) | 987 if (s->ret == XZ_STREAM_END) |
988 return XZ_STREAM_END; | 988 return XZ_STREAM_END; |
989 } | 989 } |
990 | 990 |
991 /* | 991 /* |
992 * If we have more output space than what is currently pending in | 992 * If we have more output space than what is currently pending in |
993 * temp, copy the unfiltered data from temp to the output buffer | 993 * temp, copy the unfiltered data from temp to the output buffer |
994 * and try to fill the output buffer by decoding more data from the | 994 * and try to fill the output buffer by decoding more data from the |
995 * next filter in the chain. Apply the BCJ filter on the new data | 995 * next filter in the chain. Apply the BCJ filter on the new data |
996 * in the output buffer. If everything cannot be filtered, copy it | 996 * in the output buffer. If everything cannot be filtered, copy it |
997 * to temp and rewind the output buffer position accordingly. | 997 * to temp and rewind the output buffer position accordingly. |
998 * | 998 * |
999 * This needs to be always run when temp.size == 0 to handle a special | 999 * This needs to be always run when temp.size == 0 to handle a special |
1000 * case where the output buffer is full and the next filter has no | 1000 * case where the output buffer is full and the next filter has no |
1001 * more output coming but hasn't returned XZ_STREAM_END yet. | 1001 * more output coming but hasn't returned XZ_STREAM_END yet. |
1002 */ | 1002 */ |
1003 if (s->temp.size < b->out_size - b->out_pos || s->temp.size == 0) { | 1003 if (s->temp.size < b->out_size - b->out_pos || s->temp.size == 0) { |
1004 out_start = b->out_pos; | 1004 out_start = b->out_pos; |
1005 memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size); | 1005 memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size); |
1006 b->out_pos += s->temp.size; | 1006 b->out_pos += s->temp.size; |
1007 | 1007 |
1008 s->ret = xz_dec_lzma2_run(lzma2, b); | 1008 s->ret = xz_dec_lzma2_run(lzma2, b); |
1009 if (s->ret != XZ_STREAM_END | 1009 if (s->ret != XZ_STREAM_END |
1010 && (s->ret != XZ_OK || s->single_call)) | 1010 && (s->ret != XZ_OK || s->single_call)) |
1011 return s->ret; | 1011 return s->ret; |
1012 | 1012 |
1013 bcj_apply(s, b->out, &out_start, b->out_pos); | 1013 bcj_apply(s, b->out, &out_start, b->out_pos); |
1014 | 1014 |
1015 /* | 1015 /* |
1016 * As an exception, if the next filter returned XZ_STREAM_END, | 1016 * As an exception, if the next filter returned XZ_STREAM_END, |
1017 * we can do that too, since the last few bytes that remain | 1017 * we can do that too, since the last few bytes that remain |
1018 * unfiltered are meant to remain unfiltered. | 1018 * unfiltered are meant to remain unfiltered. |
1019 */ | 1019 */ |
1020 if (s->ret == XZ_STREAM_END) | 1020 if (s->ret == XZ_STREAM_END) |
1021 return XZ_STREAM_END; | 1021 return XZ_STREAM_END; |
1022 | 1022 |
1023 s->temp.size = b->out_pos - out_start; | 1023 s->temp.size = b->out_pos - out_start; |
1024 b->out_pos -= s->temp.size; | 1024 b->out_pos -= s->temp.size; |
1025 memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size); | 1025 memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size); |
1026 | 1026 |
1027 /* | 1027 /* |
1028 * If there wasn't enough input to the next filter to fill | 1028 * If there wasn't enough input to the next filter to fill |
1029 * the output buffer with unfiltered data, there's no point | 1029 * the output buffer with unfiltered data, there's no point |
1030 * to try decoding more data to temp. | 1030 * to try decoding more data to temp. |
1031 */ | 1031 */ |
1032 if (b->out_pos + s->temp.size < b->out_size) | 1032 if (b->out_pos + s->temp.size < b->out_size) |
1033 return XZ_OK; | 1033 return XZ_OK; |
1034 } | 1034 } |
1035 | 1035 |
1036 /* | 1036 /* |
1037 * We have unfiltered data in temp. If the output buffer isn't full | 1037 * We have unfiltered data in temp. If the output buffer isn't full |
1038 * yet, try to fill the temp buffer by decoding more data from the | 1038 * yet, try to fill the temp buffer by decoding more data from the |
1039 * next filter. Apply the BCJ filter on temp. Then we hopefully can | 1039 * next filter. Apply the BCJ filter on temp. Then we hopefully can |
1040 * fill the actual output buffer by copying filtered data from temp. | 1040 * fill the actual output buffer by copying filtered data from temp. |
1041 * A mix of filtered and unfiltered data may be left in temp; it will | 1041 * A mix of filtered and unfiltered data may be left in temp; it will |
1042 * be taken care on the next call to this function. | 1042 * be taken care on the next call to this function. |
1043 */ | 1043 */ |
1044 if (b->out_pos < b->out_size) { | 1044 if (b->out_pos < b->out_size) { |
1045 /* Make b->out{,_pos,_size} temporarily point to s->temp. */ | 1045 /* Make b->out{,_pos,_size} temporarily point to s->temp. */ |
1046 s->out = b->out; | 1046 s->out = b->out; |
1047 s->out_pos = b->out_pos; | 1047 s->out_pos = b->out_pos; |
1048 s->out_size = b->out_size; | 1048 s->out_size = b->out_size; |
1049 b->out = s->temp.buf; | 1049 b->out = s->temp.buf; |
1050 b->out_pos = s->temp.size; | 1050 b->out_pos = s->temp.size; |
1051 b->out_size = sizeof(s->temp.buf); | 1051 b->out_size = sizeof(s->temp.buf); |
1052 | 1052 |
1053 s->ret = xz_dec_lzma2_run(lzma2, b); | 1053 s->ret = xz_dec_lzma2_run(lzma2, b); |
1054 | 1054 |
1055 s->temp.size = b->out_pos; | 1055 s->temp.size = b->out_pos; |
1056 b->out = s->out; | 1056 b->out = s->out; |
1057 b->out_pos = s->out_pos; | 1057 b->out_pos = s->out_pos; |
1058 b->out_size = s->out_size; | 1058 b->out_size = s->out_size; |
1059 | 1059 |
1060 if (s->ret != XZ_OK && s->ret != XZ_STREAM_END) | 1060 if (s->ret != XZ_OK && s->ret != XZ_STREAM_END) |
1061 return s->ret; | 1061 return s->ret; |
1062 | 1062 |
1063 bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size); | 1063 bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size); |
1064 | 1064 |
1065 /* | 1065 /* |
1066 * If the next filter returned XZ_STREAM_END, we mark that | 1066 * If the next filter returned XZ_STREAM_END, we mark that |
1067 * everything is filtered, since the last unfiltered bytes | 1067 * everything is filtered, since the last unfiltered bytes |
1068 * of the stream are meant to be left as is. | 1068 * of the stream are meant to be left as is. |
1069 */ | 1069 */ |
1070 if (s->ret == XZ_STREAM_END) | 1070 if (s->ret == XZ_STREAM_END) |
1071 s->temp.filtered = s->temp.size; | 1071 s->temp.filtered = s->temp.size; |
1072 | 1072 |
1073 bcj_flush(s, b); | 1073 bcj_flush(s, b); |
1074 if (s->temp.filtered > 0) | 1074 if (s->temp.filtered > 0) |
1075 return XZ_OK; | 1075 return XZ_OK; |
1076 } | 1076 } |
1077 | 1077 |
1078 return s->ret; | 1078 return s->ret; |
1079 } | 1079 } |
1080 | 1080 |
1081 struct xz_dec_bcj *xz_dec_bcj_create(int single_call) | 1081 struct xz_dec_bcj *xz_dec_bcj_create(int single_call) |
1082 { | 1082 { |
1083 struct xz_dec_bcj *s = malloc(sizeof(*s)); | 1083 struct xz_dec_bcj *s = malloc(sizeof(*s)); |
1084 if (s != NULL) | 1084 if (s != NULL) |
1085 s->single_call = single_call; | 1085 s->single_call = single_call; |
1086 | 1086 |
1087 return s; | 1087 return s; |
1088 } | 1088 } |
1089 | 1089 |
1090 enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id) | 1090 enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id) |
1091 { | 1091 { |
1092 switch (id) { | 1092 switch (id) { |
1093 #ifdef XZ_DEC_X86 | 1093 #ifdef XZ_DEC_X86 |
1094 case BCJ_X86: | 1094 case BCJ_X86: |
1095 #endif | 1095 #endif |
1096 #ifdef XZ_DEC_POWERPC | 1096 #ifdef XZ_DEC_POWERPC |
1097 case BCJ_POWERPC: | 1097 case BCJ_POWERPC: |
1098 #endif | 1098 #endif |
1099 #ifdef XZ_DEC_IA64 | 1099 #ifdef XZ_DEC_IA64 |
1100 case BCJ_IA64: | 1100 case BCJ_IA64: |
1101 #endif | 1101 #endif |
1102 #ifdef XZ_DEC_ARM | 1102 #ifdef XZ_DEC_ARM |
1103 case BCJ_ARM: | 1103 case BCJ_ARM: |
1104 #endif | 1104 #endif |
1105 #ifdef XZ_DEC_ARMTHUMB | 1105 #ifdef XZ_DEC_ARMTHUMB |
1106 case BCJ_ARMTHUMB: | 1106 case BCJ_ARMTHUMB: |
1107 #endif | 1107 #endif |
1108 #ifdef XZ_DEC_SPARC | 1108 #ifdef XZ_DEC_SPARC |
1109 case BCJ_SPARC: | 1109 case BCJ_SPARC: |
1110 #endif | 1110 #endif |
1111 break; | 1111 break; |
1112 | 1112 |
1113 default: | 1113 default: |
1114 /* Unsupported Filter ID */ | 1114 /* Unsupported Filter ID */ |
1115 return XZ_OPTIONS_ERROR; | 1115 return XZ_OPTIONS_ERROR; |
1116 } | 1116 } |
1117 | 1117 |
1118 s->type = id; | 1118 s->type = id; |
1119 s->ret = XZ_OK; | 1119 s->ret = XZ_OK; |
1120 s->pos = 0; | 1120 s->pos = 0; |
1121 s->x86_prev_mask = 0; | 1121 s->x86_prev_mask = 0; |
1122 s->temp.filtered = 0; | 1122 s->temp.filtered = 0; |
1123 s->temp.size = 0; | 1123 s->temp.size = 0; |
1124 | 1124 |
1125 return XZ_OK; | 1125 return XZ_OK; |
1126 } | 1126 } |
1127 | 1127 |
1128 #endif | 1128 #endif |
1129 /* | 1129 /* |
1130 * LZMA2 decoder | 1130 * LZMA2 decoder |
1165 * | 1165 * |
1166 * The symbol names are in from STATE_oldest_older_previous. REP means | 1166 * The symbol names are in from STATE_oldest_older_previous. REP means |
1167 * either short or long repeated match, and NONLIT means any non-literal. | 1167 * either short or long repeated match, and NONLIT means any non-literal. |
1168 */ | 1168 */ |
1169 enum lzma_state { | 1169 enum lzma_state { |
1170 STATE_LIT_LIT, | 1170 STATE_LIT_LIT, |
1171 STATE_MATCH_LIT_LIT, | 1171 STATE_MATCH_LIT_LIT, |
1172 STATE_REP_LIT_LIT, | 1172 STATE_REP_LIT_LIT, |
1173 STATE_SHORTREP_LIT_LIT, | 1173 STATE_SHORTREP_LIT_LIT, |
1174 STATE_MATCH_LIT, | 1174 STATE_MATCH_LIT, |
1175 STATE_REP_LIT, | 1175 STATE_REP_LIT, |
1176 STATE_SHORTREP_LIT, | 1176 STATE_SHORTREP_LIT, |
1177 STATE_LIT_MATCH, | 1177 STATE_LIT_MATCH, |
1178 STATE_LIT_LONGREP, | 1178 STATE_LIT_LONGREP, |
1179 STATE_LIT_SHORTREP, | 1179 STATE_LIT_SHORTREP, |
1180 STATE_NONLIT_MATCH, | 1180 STATE_NONLIT_MATCH, |
1181 STATE_NONLIT_REP | 1181 STATE_NONLIT_REP |
1182 }; | 1182 }; |
1183 | 1183 |
1184 /* Total number of states */ | 1184 /* Total number of states */ |
1185 #define STATES 12 | 1185 #define STATES 12 |
1186 | 1186 |
1188 #define LIT_STATES 7 | 1188 #define LIT_STATES 7 |
1189 | 1189 |
1190 /* Indicate that the latest symbol was a literal. */ | 1190 /* Indicate that the latest symbol was a literal. */ |
1191 static inline void lzma_state_literal(enum lzma_state *state) | 1191 static inline void lzma_state_literal(enum lzma_state *state) |
1192 { | 1192 { |
1193 if (*state <= STATE_SHORTREP_LIT_LIT) | 1193 if (*state <= STATE_SHORTREP_LIT_LIT) |
1194 *state = STATE_LIT_LIT; | 1194 *state = STATE_LIT_LIT; |
1195 else if (*state <= STATE_LIT_SHORTREP) | 1195 else if (*state <= STATE_LIT_SHORTREP) |
1196 *state -= 3; | 1196 *state -= 3; |
1197 else | 1197 else |
1198 *state -= 6; | 1198 *state -= 6; |
1199 } | 1199 } |
1200 | 1200 |
1201 /* Indicate that the latest symbol was a match. */ | 1201 /* Indicate that the latest symbol was a match. */ |
1202 static inline void lzma_state_match(enum lzma_state *state) | 1202 static inline void lzma_state_match(enum lzma_state *state) |
1203 { | 1203 { |
1204 *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH; | 1204 *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH; |
1205 } | 1205 } |
1206 | 1206 |
1207 /* Indicate that the latest state was a long repeated match. */ | 1207 /* Indicate that the latest state was a long repeated match. */ |
1208 static inline void lzma_state_long_rep(enum lzma_state *state) | 1208 static inline void lzma_state_long_rep(enum lzma_state *state) |
1209 { | 1209 { |
1210 *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP; | 1210 *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP; |
1211 } | 1211 } |
1212 | 1212 |
1213 /* Indicate that the latest symbol was a short match. */ | 1213 /* Indicate that the latest symbol was a short match. */ |
1214 static inline void lzma_state_short_rep(enum lzma_state *state) | 1214 static inline void lzma_state_short_rep(enum lzma_state *state) |
1215 { | 1215 { |
1216 *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP; | 1216 *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP; |
1217 } | 1217 } |
1218 | 1218 |
1219 /* Test if the previous symbol was a literal. */ | 1219 /* Test if the previous symbol was a literal. */ |
1220 static inline int lzma_state_is_literal(enum lzma_state state) | 1220 static inline int lzma_state_is_literal(enum lzma_state state) |
1221 { | 1221 { |
1222 return state < LIT_STATES; | 1222 return state < LIT_STATES; |
1223 } | 1223 } |
1224 | 1224 |
1225 /* Each literal coder is divided in three sections: | 1225 /* Each literal coder is divided in three sections: |
1226 * - 0x001-0x0FF: Without match byte | 1226 * - 0x001-0x0FF: Without match byte |
1227 * - 0x101-0x1FF: With match byte; match bit is 0 | 1227 * - 0x101-0x1FF: With match byte; match bit is 0 |
1271 * Get the index of the appropriate probability array for decoding | 1271 * Get the index of the appropriate probability array for decoding |
1272 * the distance slot. | 1272 * the distance slot. |
1273 */ | 1273 */ |
1274 static inline uint32_t lzma_get_dist_state(uint32_t len) | 1274 static inline uint32_t lzma_get_dist_state(uint32_t len) |
1275 { | 1275 { |
1276 return len < DIST_STATES + MATCH_LEN_MIN | 1276 return len < DIST_STATES + MATCH_LEN_MIN |
1277 ? len - MATCH_LEN_MIN : DIST_STATES - 1; | 1277 ? len - MATCH_LEN_MIN : DIST_STATES - 1; |
1278 } | 1278 } |
1279 | 1279 |
1280 /* | 1280 /* |
1281 * The highest two bits of a 32-bit match distance are encoded using six bits. | 1281 * The highest two bits of a 32-bit match distance are encoded using six bits. |
1282 * This six-bit value is called a distance slot. This way encoding a 32-bit | 1282 * This six-bit value is called a distance slot. This way encoding a 32-bit |
1360 * Most of these variables are size_t to support single-call mode, | 1360 * Most of these variables are size_t to support single-call mode, |
1361 * in which the dictionary variables address the actual output | 1361 * in which the dictionary variables address the actual output |
1362 * buffer directly. | 1362 * buffer directly. |
1363 */ | 1363 */ |
1364 struct dictionary { | 1364 struct dictionary { |
1365 /* Beginning of the history buffer */ | 1365 /* Beginning of the history buffer */ |
1366 uint8_t *buf; | 1366 uint8_t *buf; |
1367 | 1367 |
1368 /* Old position in buf (before decoding more data) */ | 1368 /* Old position in buf (before decoding more data) */ |
1369 size_t start; | 1369 size_t start; |
1370 | 1370 |
1371 /* Position in buf */ | 1371 /* Position in buf */ |
1372 size_t pos; | 1372 size_t pos; |
1373 | 1373 |
1374 /* | 1374 /* |
1375 * How full dictionary is. This is used to detect corrupt input that | 1375 * How full dictionary is. This is used to detect corrupt input that |
1376 * would read beyond the beginning of the uncompressed stream. | 1376 * would read beyond the beginning of the uncompressed stream. |
1377 */ | 1377 */ |
1378 size_t full; | 1378 size_t full; |
1379 | 1379 |
1380 /* Write limit; we don't write to buf[limit] or later bytes. */ | 1380 /* Write limit; we don't write to buf[limit] or later bytes. */ |
1381 size_t limit; | 1381 size_t limit; |
1382 | 1382 |
1383 /* | 1383 /* |
1384 * End of the dictionary buffer. In multi-call mode, this is | 1384 * End of the dictionary buffer. In multi-call mode, this is |
1385 * the same as the dictionary size. In single-call mode, this | 1385 * the same as the dictionary size. In single-call mode, this |
1386 * indicates the size of the output buffer. | 1386 * indicates the size of the output buffer. |
1387 */ | 1387 */ |
1388 size_t end; | 1388 size_t end; |
1389 | 1389 |
1390 /* | 1390 /* |
1391 * Size of the dictionary as specified in Block Header. This is used | 1391 * Size of the dictionary as specified in Block Header. This is used |
1392 * together with "full" to detect corrupt input that would make us | 1392 * together with "full" to detect corrupt input that would make us |
1393 * read beyond the beginning of the uncompressed stream. | 1393 * read beyond the beginning of the uncompressed stream. |
1394 */ | 1394 */ |
1395 uint32_t size; | 1395 uint32_t size; |
1396 | 1396 |
1397 /* | 1397 /* |
1398 * Maximum allowed dictionary size in multi-call mode. | 1398 * Maximum allowed dictionary size in multi-call mode. |
1399 * This is ignored in single-call mode. | 1399 * This is ignored in single-call mode. |
1400 */ | 1400 */ |
1401 uint32_t size_max; | 1401 uint32_t size_max; |
1402 | 1402 |
1403 /* | 1403 /* |
1404 * Amount of memory currently allocated for the dictionary. | 1404 * Amount of memory currently allocated for the dictionary. |
1405 * This is used only with XZ_DYNALLOC. (With XZ_PREALLOC, | 1405 * This is used only with XZ_DYNALLOC. (With XZ_PREALLOC, |
1406 * size_max is always the same as the allocated size.) | 1406 * size_max is always the same as the allocated size.) |
1407 */ | 1407 */ |
1408 uint32_t allocated; | 1408 uint32_t allocated; |
1409 | 1409 |
1410 /* Operation mode */ | 1410 /* Operation mode */ |
1411 enum xz_mode mode; | 1411 enum xz_mode mode; |
1412 }; | 1412 }; |
1413 | 1413 |
1414 /* Range decoder */ | 1414 /* Range decoder */ |
1415 struct rc_dec { | 1415 struct rc_dec { |
1416 uint32_t range; | 1416 uint32_t range; |
1417 uint32_t code; | 1417 uint32_t code; |
1418 | 1418 |
1419 /* | 1419 /* |
1420 * Number of initializing bytes remaining to be read | 1420 * Number of initializing bytes remaining to be read |
1421 * by rc_read_init(). | 1421 * by rc_read_init(). |
1422 */ | 1422 */ |
1423 uint32_t init_bytes_left; | 1423 uint32_t init_bytes_left; |
1424 | 1424 |
1425 /* | 1425 /* |
1426 * Buffer from which we read our input. It can be either | 1426 * Buffer from which we read our input. It can be either |
1427 * temp.buf or the caller-provided input buffer. | 1427 * temp.buf or the caller-provided input buffer. |
1428 */ | 1428 */ |
1429 const uint8_t *in; | 1429 const uint8_t *in; |
1430 size_t in_pos; | 1430 size_t in_pos; |
1431 size_t in_limit; | 1431 size_t in_limit; |
1432 }; | 1432 }; |
1433 | 1433 |
1434 /* Probabilities for a length decoder. */ | 1434 /* Probabilities for a length decoder. */ |
1435 struct lzma_len_dec { | 1435 struct lzma_len_dec { |
1436 /* Probability of match length being at least 10 */ | 1436 /* Probability of match length being at least 10 */ |
1437 uint16_t choice; | 1437 uint16_t choice; |
1438 | 1438 |
1439 /* Probability of match length being at least 18 */ | 1439 /* Probability of match length being at least 18 */ |
1440 uint16_t choice2; | 1440 uint16_t choice2; |
1441 | 1441 |
1442 /* Probabilities for match lengths 2-9 */ | 1442 /* Probabilities for match lengths 2-9 */ |
1443 uint16_t low[POS_STATES_MAX][LEN_LOW_SYMBOLS]; | 1443 uint16_t low[POS_STATES_MAX][LEN_LOW_SYMBOLS]; |
1444 | 1444 |
1445 /* Probabilities for match lengths 10-17 */ | 1445 /* Probabilities for match lengths 10-17 */ |
1446 uint16_t mid[POS_STATES_MAX][LEN_MID_SYMBOLS]; | 1446 uint16_t mid[POS_STATES_MAX][LEN_MID_SYMBOLS]; |
1447 | 1447 |
1448 /* Probabilities for match lengths 18-273 */ | 1448 /* Probabilities for match lengths 18-273 */ |
1449 uint16_t high[LEN_HIGH_SYMBOLS]; | 1449 uint16_t high[LEN_HIGH_SYMBOLS]; |
1450 }; | 1450 }; |
1451 | 1451 |
1452 struct lzma_dec { | 1452 struct lzma_dec { |
1453 /* Distances of latest four matches */ | 1453 /* Distances of latest four matches */ |
1454 uint32_t rep0; | 1454 uint32_t rep0; |
1455 uint32_t rep1; | 1455 uint32_t rep1; |
1456 uint32_t rep2; | 1456 uint32_t rep2; |
1457 uint32_t rep3; | 1457 uint32_t rep3; |
1458 | 1458 |
1459 /* Types of the most recently seen LZMA symbols */ | 1459 /* Types of the most recently seen LZMA symbols */ |
1460 enum lzma_state state; | 1460 enum lzma_state state; |
1461 | 1461 |
1462 /* | 1462 /* |
1463 * Length of a match. This is updated so that dict_repeat can | 1463 * Length of a match. This is updated so that dict_repeat can |
1464 * be called again to finish repeating the whole match. | 1464 * be called again to finish repeating the whole match. |
1465 */ | 1465 */ |
1466 uint32_t len; | 1466 uint32_t len; |
1467 | 1467 |
1468 /* | 1468 /* |
1469 * LZMA properties or related bit masks (number of literal | 1469 * LZMA properties or related bit masks (number of literal |
1470 * context bits, a mask dervied from the number of literal | 1470 * context bits, a mask dervied from the number of literal |
1471 * position bits, and a mask dervied from the number | 1471 * position bits, and a mask dervied from the number |
1472 * position bits) | 1472 * position bits) |
1473 */ | 1473 */ |
1474 uint32_t lc; | 1474 uint32_t lc; |
1475 uint32_t literal_pos_mask; /* (1 << lp) - 1 */ | 1475 uint32_t literal_pos_mask; /* (1 << lp) - 1 */ |
1476 uint32_t pos_mask; /* (1 << pb) - 1 */ | 1476 uint32_t pos_mask; /* (1 << pb) - 1 */ |
1477 | 1477 |
1478 /* If 1, it's a match. Otherwise it's a single 8-bit literal. */ | 1478 /* If 1, it's a match. Otherwise it's a single 8-bit literal. */ |
1479 uint16_t is_match[STATES][POS_STATES_MAX]; | 1479 uint16_t is_match[STATES][POS_STATES_MAX]; |
1480 | 1480 |
1481 /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */ | 1481 /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */ |
1482 uint16_t is_rep[STATES]; | 1482 uint16_t is_rep[STATES]; |
1483 | 1483 |
1484 /* | 1484 /* |
1485 * If 0, distance of a repeated match is rep0. | 1485 * If 0, distance of a repeated match is rep0. |
1486 * Otherwise check is_rep1. | 1486 * Otherwise check is_rep1. |
1487 */ | 1487 */ |
1488 uint16_t is_rep0[STATES]; | 1488 uint16_t is_rep0[STATES]; |
1489 | 1489 |
1490 /* | 1490 /* |
1491 * If 0, distance of a repeated match is rep1. | 1491 * If 0, distance of a repeated match is rep1. |
1492 * Otherwise check is_rep2. | 1492 * Otherwise check is_rep2. |
1493 */ | 1493 */ |
1494 uint16_t is_rep1[STATES]; | 1494 uint16_t is_rep1[STATES]; |
1495 | 1495 |
1496 /* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */ | 1496 /* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */ |
1497 uint16_t is_rep2[STATES]; | 1497 uint16_t is_rep2[STATES]; |
1498 | 1498 |
1499 /* | 1499 /* |
1500 * If 1, the repeated match has length of one byte. Otherwise | 1500 * If 1, the repeated match has length of one byte. Otherwise |
1501 * the length is decoded from rep_len_decoder. | 1501 * the length is decoded from rep_len_decoder. |
1502 */ | 1502 */ |
1503 uint16_t is_rep0_long[STATES][POS_STATES_MAX]; | 1503 uint16_t is_rep0_long[STATES][POS_STATES_MAX]; |
1504 | 1504 |
1505 /* | 1505 /* |
1506 * Probability tree for the highest two bits of the match | 1506 * Probability tree for the highest two bits of the match |
1507 * distance. There is a separate probability tree for match | 1507 * distance. There is a separate probability tree for match |
1508 * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273]. | 1508 * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273]. |
1509 */ | 1509 */ |
1510 uint16_t dist_slot[DIST_STATES][DIST_SLOTS]; | 1510 uint16_t dist_slot[DIST_STATES][DIST_SLOTS]; |
1511 | 1511 |
1512 /* | 1512 /* |
1513 * Probility trees for additional bits for match distance | 1513 * Probility trees for additional bits for match distance |
1514 * when the distance is in the range [4, 127]. | 1514 * when the distance is in the range [4, 127]. |
1515 */ | 1515 */ |
1516 uint16_t dist_special[FULL_DISTANCES - DIST_MODEL_END]; | 1516 uint16_t dist_special[FULL_DISTANCES - DIST_MODEL_END]; |
1517 | 1517 |
1518 /* | 1518 /* |
1519 * Probability tree for the lowest four bits of a match | 1519 * Probability tree for the lowest four bits of a match |
1520 * distance that is equal to or greater than 128. | 1520 * distance that is equal to or greater than 128. |
1521 */ | 1521 */ |
1522 uint16_t dist_align[ALIGN_SIZE]; | 1522 uint16_t dist_align[ALIGN_SIZE]; |
1523 | 1523 |
1524 /* Length of a normal match */ | 1524 /* Length of a normal match */ |
1525 struct lzma_len_dec match_len_dec; | 1525 struct lzma_len_dec match_len_dec; |
1526 | 1526 |
1527 /* Length of a repeated match */ | 1527 /* Length of a repeated match */ |
1528 struct lzma_len_dec rep_len_dec; | 1528 struct lzma_len_dec rep_len_dec; |
1529 | 1529 |
1530 /* Probabilities of literals */ | 1530 /* Probabilities of literals */ |
1531 uint16_t literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE]; | 1531 uint16_t literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE]; |
1532 }; | 1532 }; |
1533 | 1533 |
1534 struct lzma2_dec { | 1534 struct lzma2_dec { |
1535 /* Position in xz_dec_lzma2_run(). */ | 1535 /* Position in xz_dec_lzma2_run(). */ |
1536 enum lzma2_seq { | 1536 enum lzma2_seq { |
1537 SEQ_CONTROL, | 1537 SEQ_CONTROL, |
1538 SEQ_UNCOMPRESSED_1, | 1538 SEQ_UNCOMPRESSED_1, |
1539 SEQ_UNCOMPRESSED_2, | 1539 SEQ_UNCOMPRESSED_2, |
1540 SEQ_COMPRESSED_0, | 1540 SEQ_COMPRESSED_0, |
1541 SEQ_COMPRESSED_1, | 1541 SEQ_COMPRESSED_1, |
1542 SEQ_PROPERTIES, | 1542 SEQ_PROPERTIES, |
1543 SEQ_LZMA_PREPARE, | 1543 SEQ_LZMA_PREPARE, |
1544 SEQ_LZMA_RUN, | 1544 SEQ_LZMA_RUN, |
1545 SEQ_COPY | 1545 SEQ_COPY |
1546 } sequence; | 1546 } sequence; |
1547 | 1547 |
1548 /* Next position after decoding the compressed size of the chunk. */ | 1548 /* Next position after decoding the compressed size of the chunk. */ |
1549 enum lzma2_seq next_sequence; | 1549 enum lzma2_seq next_sequence; |
1550 | 1550 |
1551 /* Uncompressed size of LZMA chunk (2 MiB at maximum) */ | 1551 /* Uncompressed size of LZMA chunk (2 MiB at maximum) */ |
1552 uint32_t uncompressed; | 1552 uint32_t uncompressed; |
1553 | 1553 |
1554 /* | 1554 /* |
1555 * Compressed size of LZMA chunk or compressed/uncompressed | 1555 * Compressed size of LZMA chunk or compressed/uncompressed |
1556 * size of uncompressed chunk (64 KiB at maximum) | 1556 * size of uncompressed chunk (64 KiB at maximum) |
1557 */ | 1557 */ |
1558 uint32_t compressed; | 1558 uint32_t compressed; |
1559 | 1559 |
1560 /* | 1560 /* |
1561 * True if dictionary reset is needed. This is false before | 1561 * True if dictionary reset is needed. This is false before |
1562 * the first chunk (LZMA or uncompressed). | 1562 * the first chunk (LZMA or uncompressed). |
1563 */ | 1563 */ |
1564 int need_dict_reset; | 1564 int need_dict_reset; |
1565 | 1565 |
1566 /* | 1566 /* |
1567 * True if new LZMA properties are needed. This is false | 1567 * True if new LZMA properties are needed. This is false |
1568 * before the first LZMA chunk. | 1568 * before the first LZMA chunk. |
1569 */ | 1569 */ |
1570 int need_props; | 1570 int need_props; |
1571 }; | 1571 }; |
1572 | 1572 |
1573 struct xz_dec_lzma2 { | 1573 struct xz_dec_lzma2 { |
1574 /* | 1574 /* |
1575 * The order below is important on x86 to reduce code size and | 1575 * The order below is important on x86 to reduce code size and |
1576 * it shouldn't hurt on other platforms. Everything up to and | 1576 * it shouldn't hurt on other platforms. Everything up to and |
1577 * including lzma.pos_mask are in the first 128 bytes on x86-32, | 1577 * including lzma.pos_mask are in the first 128 bytes on x86-32, |
1578 * which allows using smaller instructions to access those | 1578 * which allows using smaller instructions to access those |
1579 * variables. On x86-64, fewer variables fit into the first 128 | 1579 * variables. On x86-64, fewer variables fit into the first 128 |
1580 * bytes, but this is still the best order without sacrificing | 1580 * bytes, but this is still the best order without sacrificing |
1581 * the readability by splitting the structures. | 1581 * the readability by splitting the structures. |
1582 */ | 1582 */ |
1583 struct rc_dec rc; | 1583 struct rc_dec rc; |
1584 struct dictionary dict; | 1584 struct dictionary dict; |
1585 struct lzma2_dec lzma2; | 1585 struct lzma2_dec lzma2; |
1586 struct lzma_dec lzma; | 1586 struct lzma_dec lzma; |
1587 | 1587 |
1588 /* | 1588 /* |
1589 * Temporary buffer which holds small number of input bytes between | 1589 * Temporary buffer which holds small number of input bytes between |
1590 * decoder calls. See lzma2_lzma() for details. | 1590 * decoder calls. See lzma2_lzma() for details. |
1591 */ | 1591 */ |
1592 struct { | 1592 struct { |
1593 uint32_t size; | 1593 uint32_t size; |
1594 uint8_t buf[3 * LZMA_IN_REQUIRED]; | 1594 uint8_t buf[3 * LZMA_IN_REQUIRED]; |
1595 } temp; | 1595 } temp; |
1596 }; | 1596 }; |
1597 | 1597 |
1598 /************** | 1598 /************** |
1599 * Dictionary * | 1599 * Dictionary * |
1600 **************/ | 1600 **************/ |
1603 * Reset the dictionary state. When in single-call mode, set up the beginning | 1603 * Reset the dictionary state. When in single-call mode, set up the beginning |
1604 * of the dictionary to point to the actual output buffer. | 1604 * of the dictionary to point to the actual output buffer. |
1605 */ | 1605 */ |
1606 static void dict_reset(struct dictionary *dict, struct xz_buf *b) | 1606 static void dict_reset(struct dictionary *dict, struct xz_buf *b) |
1607 { | 1607 { |
1608 if (DEC_IS_SINGLE(dict->mode)) { | 1608 if (DEC_IS_SINGLE(dict->mode)) { |
1609 dict->buf = b->out + b->out_pos; | 1609 dict->buf = b->out + b->out_pos; |
1610 dict->end = b->out_size - b->out_pos; | 1610 dict->end = b->out_size - b->out_pos; |
1611 } | 1611 } |
1612 | 1612 |
1613 dict->start = 0; | 1613 dict->start = 0; |
1614 dict->pos = 0; | 1614 dict->pos = 0; |
1615 dict->limit = 0; | 1615 dict->limit = 0; |
1616 dict->full = 0; | 1616 dict->full = 0; |
1617 } | 1617 } |
1618 | 1618 |
1619 /* Set dictionary write limit */ | 1619 /* Set dictionary write limit */ |
1620 static void dict_limit(struct dictionary *dict, size_t out_max) | 1620 static void dict_limit(struct dictionary *dict, size_t out_max) |
1621 { | 1621 { |
1622 if (dict->end - dict->pos <= out_max) | 1622 if (dict->end - dict->pos <= out_max) |
1623 dict->limit = dict->end; | 1623 dict->limit = dict->end; |
1624 else | 1624 else |
1625 dict->limit = dict->pos + out_max; | 1625 dict->limit = dict->pos + out_max; |
1626 } | 1626 } |
1627 | 1627 |
1628 /* Return true if at least one byte can be written into the dictionary. */ | 1628 /* Return true if at least one byte can be written into the dictionary. */ |
1629 static inline int dict_has_space(const struct dictionary *dict) | 1629 static inline int dict_has_space(const struct dictionary *dict) |
1630 { | 1630 { |
1631 return dict->pos < dict->limit; | 1631 return dict->pos < dict->limit; |
1632 } | 1632 } |
1633 | 1633 |
1634 /* | 1634 /* |
1635 * Get a byte from the dictionary at the given distance. The distance is | 1635 * Get a byte from the dictionary at the given distance. The distance is |
1636 * assumed to valid, or as a special case, zero when the dictionary is | 1636 * assumed to valid, or as a special case, zero when the dictionary is |
1637 * still empty. This special case is needed for single-call decoding to | 1637 * still empty. This special case is needed for single-call decoding to |
1638 * avoid writing a '\0' to the end of the destination buffer. | 1638 * avoid writing a '\0' to the end of the destination buffer. |
1639 */ | 1639 */ |
1640 static inline uint32_t dict_get(const struct dictionary *dict, uint32_t dist) | 1640 static inline uint32_t dict_get(const struct dictionary *dict, uint32_t dist) |
1641 { | 1641 { |
1642 size_t offset = dict->pos - dist - 1; | 1642 size_t offset = dict->pos - dist - 1; |
1643 | 1643 |
1644 if (dist >= dict->pos) | 1644 if (dist >= dict->pos) |
1645 offset += dict->end; | 1645 offset += dict->end; |
1646 | 1646 |
1647 return dict->full > 0 ? dict->buf[offset] : 0; | 1647 return dict->full > 0 ? dict->buf[offset] : 0; |
1648 } | 1648 } |
1649 | 1649 |
1650 /* | 1650 /* |
1651 * Put one byte into the dictionary. It is assumed that there is space for it. | 1651 * Put one byte into the dictionary. It is assumed that there is space for it. |
1652 */ | 1652 */ |
1653 static inline void dict_put(struct dictionary *dict, uint8_t byte) | 1653 static inline void dict_put(struct dictionary *dict, uint8_t byte) |
1654 { | 1654 { |
1655 dict->buf[dict->pos++] = byte; | 1655 dict->buf[dict->pos++] = byte; |
1656 | 1656 |
1657 if (dict->full < dict->pos) | 1657 if (dict->full < dict->pos) |
1658 dict->full = dict->pos; | 1658 dict->full = dict->pos; |
1659 } | 1659 } |
1660 | 1660 |
1661 /* | 1661 /* |
1662 * Repeat given number of bytes from the given distance. If the distance is | 1662 * Repeat given number of bytes from the given distance. If the distance is |
1663 * invalid, false is returned. On success, true is returned and *len is | 1663 * invalid, false is returned. On success, true is returned and *len is |
1664 * updated to indicate how many bytes were left to be repeated. | 1664 * updated to indicate how many bytes were left to be repeated. |
1665 */ | 1665 */ |
1666 static int dict_repeat(struct dictionary *dict, uint32_t *len, uint32_t dist) | 1666 static int dict_repeat(struct dictionary *dict, uint32_t *len, uint32_t dist) |
1667 { | 1667 { |
1668 size_t back; | 1668 size_t back; |
1669 uint32_t left; | 1669 uint32_t left; |
1670 | 1670 |
1671 if (dist >= dict->full || dist >= dict->size) return 0; | 1671 if (dist >= dict->full || dist >= dict->size) return 0; |
1672 | 1672 |
1673 left = min_t(size_t, dict->limit - dict->pos, *len); | 1673 left = min_t(size_t, dict->limit - dict->pos, *len); |
1674 *len -= left; | 1674 *len -= left; |
1675 | 1675 |
1676 back = dict->pos - dist - 1; | 1676 back = dict->pos - dist - 1; |
1677 if (dist >= dict->pos) | 1677 if (dist >= dict->pos) |
1678 back += dict->end; | 1678 back += dict->end; |
1679 | 1679 |
1680 do { | 1680 do { |
1681 dict->buf[dict->pos++] = dict->buf[back++]; | 1681 dict->buf[dict->pos++] = dict->buf[back++]; |
1682 if (back == dict->end) | 1682 if (back == dict->end) |
1683 back = 0; | 1683 back = 0; |
1684 } while (--left > 0); | 1684 } while (--left > 0); |
1685 | 1685 |
1686 if (dict->full < dict->pos) | 1686 if (dict->full < dict->pos) |
1687 dict->full = dict->pos; | 1687 dict->full = dict->pos; |
1688 | 1688 |
1689 return 1; | 1689 return 1; |
1690 } | 1690 } |
1691 | 1691 |
1692 /* Copy uncompressed data as is from input to dictionary and output buffers. */ | 1692 /* Copy uncompressed data as is from input to dictionary and output buffers. */ |
1693 static void dict_uncompressed(struct dictionary *dict, struct xz_buf *b, | 1693 static void dict_uncompressed(struct dictionary *dict, struct xz_buf *b, |
1694 uint32_t *left) | 1694 uint32_t *left) |
1695 { | 1695 { |
1696 size_t copy_size; | 1696 size_t copy_size; |
1697 | 1697 |
1698 while (*left > 0 && b->in_pos < b->in_size | 1698 while (*left > 0 && b->in_pos < b->in_size |
1699 && b->out_pos < b->out_size) { | 1699 && b->out_pos < b->out_size) { |
1700 copy_size = min(b->in_size - b->in_pos, | 1700 copy_size = min(b->in_size - b->in_pos, |
1701 b->out_size - b->out_pos); | 1701 b->out_size - b->out_pos); |
1702 if (copy_size > dict->end - dict->pos) | 1702 if (copy_size > dict->end - dict->pos) |
1703 copy_size = dict->end - dict->pos; | 1703 copy_size = dict->end - dict->pos; |
1704 if (copy_size > *left) | 1704 if (copy_size > *left) |
1705 copy_size = *left; | 1705 copy_size = *left; |
1706 | 1706 |
1707 *left -= copy_size; | 1707 *left -= copy_size; |
1708 | 1708 |
1709 memcpy(dict->buf + dict->pos, b->in + b->in_pos, copy_size); | 1709 memcpy(dict->buf + dict->pos, b->in + b->in_pos, copy_size); |
1710 dict->pos += copy_size; | 1710 dict->pos += copy_size; |
1711 | 1711 |
1712 if (dict->full < dict->pos) | 1712 if (dict->full < dict->pos) |
1713 dict->full = dict->pos; | 1713 dict->full = dict->pos; |
1714 | 1714 |
1715 if (DEC_IS_MULTI(dict->mode)) { | 1715 if (DEC_IS_MULTI(dict->mode)) { |
1716 if (dict->pos == dict->end) | 1716 if (dict->pos == dict->end) |
1717 dict->pos = 0; | 1717 dict->pos = 0; |
1718 | 1718 |
1719 memcpy(b->out + b->out_pos, b->in + b->in_pos, | 1719 memcpy(b->out + b->out_pos, b->in + b->in_pos, |
1720 copy_size); | 1720 copy_size); |
1721 } | 1721 } |
1722 | 1722 |
1723 dict->start = dict->pos; | 1723 dict->start = dict->pos; |
1724 | 1724 |
1725 b->out_pos += copy_size; | 1725 b->out_pos += copy_size; |
1726 b->in_pos += copy_size; | 1726 b->in_pos += copy_size; |
1727 } | 1727 } |
1728 } | 1728 } |
1729 | 1729 |
1730 /* | 1730 /* |
1731 * Flush pending data from dictionary to b->out. It is assumed that there is | 1731 * Flush pending data from dictionary to b->out. It is assumed that there is |
1732 * enough space in b->out. This is guaranteed because caller uses dict_limit() | 1732 * enough space in b->out. This is guaranteed because caller uses dict_limit() |
1733 * before decoding data into the dictionary. | 1733 * before decoding data into the dictionary. |
1734 */ | 1734 */ |
1735 static uint32_t dict_flush(struct dictionary *dict, struct xz_buf *b) | 1735 static uint32_t dict_flush(struct dictionary *dict, struct xz_buf *b) |
1736 { | 1736 { |
1737 size_t copy_size = dict->pos - dict->start; | 1737 size_t copy_size = dict->pos - dict->start; |
1738 | 1738 |
1739 if (DEC_IS_MULTI(dict->mode)) { | 1739 if (DEC_IS_MULTI(dict->mode)) { |
1740 if (dict->pos == dict->end) | 1740 if (dict->pos == dict->end) |
1741 dict->pos = 0; | 1741 dict->pos = 0; |
1742 | 1742 |
1743 memcpy(b->out + b->out_pos, dict->buf + dict->start, | 1743 memcpy(b->out + b->out_pos, dict->buf + dict->start, |
1744 copy_size); | 1744 copy_size); |
1745 } | 1745 } |
1746 | 1746 |
1747 dict->start = dict->pos; | 1747 dict->start = dict->pos; |
1748 b->out_pos += copy_size; | 1748 b->out_pos += copy_size; |
1749 return copy_size; | 1749 return copy_size; |
1750 } | 1750 } |
1751 | 1751 |
1752 /***************** | 1752 /***************** |
1753 * Range decoder * | 1753 * Range decoder * |
1754 *****************/ | 1754 *****************/ |
1755 | 1755 |
1756 /* Reset the range decoder. */ | 1756 /* Reset the range decoder. */ |
1757 static void rc_reset(struct rc_dec *rc) | 1757 static void rc_reset(struct rc_dec *rc) |
1758 { | 1758 { |
1759 rc->range = (uint32_t)-1; | 1759 rc->range = (uint32_t)-1; |
1760 rc->code = 0; | 1760 rc->code = 0; |
1761 rc->init_bytes_left = RC_INIT_BYTES; | 1761 rc->init_bytes_left = RC_INIT_BYTES; |
1762 } | 1762 } |
1763 | 1763 |
1764 /* | 1764 /* |
1765 * Read the first five initial bytes into rc->code if they haven't been | 1765 * Read the first five initial bytes into rc->code if they haven't been |
1766 * read already. (Yes, the first byte gets completely ignored.) | 1766 * read already. (Yes, the first byte gets completely ignored.) |
1767 */ | 1767 */ |
1768 static int rc_read_init(struct rc_dec *rc, struct xz_buf *b) | 1768 static int rc_read_init(struct rc_dec *rc, struct xz_buf *b) |
1769 { | 1769 { |
1770 while (rc->init_bytes_left > 0) { | 1770 while (rc->init_bytes_left > 0) { |
1771 if (b->in_pos == b->in_size) return 0; | 1771 if (b->in_pos == b->in_size) return 0; |
1772 | 1772 |
1773 rc->code = (rc->code << 8) + b->in[b->in_pos++]; | 1773 rc->code = (rc->code << 8) + b->in[b->in_pos++]; |
1774 --rc->init_bytes_left; | 1774 --rc->init_bytes_left; |
1775 } | 1775 } |
1776 | 1776 |
1777 return 1; | 1777 return 1; |
1778 } | 1778 } |
1779 | 1779 |
1780 /* Return true if there may not be enough input for the next decoding loop. */ | 1780 /* Return true if there may not be enough input for the next decoding loop. */ |
1781 static inline int rc_limit_exceeded(const struct rc_dec *rc) | 1781 static inline int rc_limit_exceeded(const struct rc_dec *rc) |
1782 { | 1782 { |
1783 return rc->in_pos > rc->in_limit; | 1783 return rc->in_pos > rc->in_limit; |
1784 } | 1784 } |
1785 | 1785 |
1786 /* | 1786 /* |
1787 * Return true if it is possible (from point of view of range decoder) that | 1787 * Return true if it is possible (from point of view of range decoder) that |
1788 * we have reached the end of the LZMA chunk. | 1788 * we have reached the end of the LZMA chunk. |
1789 */ | 1789 */ |
1790 static inline int rc_is_finished(const struct rc_dec *rc) | 1790 static inline int rc_is_finished(const struct rc_dec *rc) |
1791 { | 1791 { |
1792 return rc->code == 0; | 1792 return rc->code == 0; |
1793 } | 1793 } |
1794 | 1794 |
1795 /* Read the next input byte if needed. */ | 1795 /* Read the next input byte if needed. */ |
1796 static inline void rc_normalize(struct rc_dec *rc) | 1796 static inline void rc_normalize(struct rc_dec *rc) |
1797 { | 1797 { |
1798 if (rc->range < RC_TOP_VALUE) { | 1798 if (rc->range < RC_TOP_VALUE) { |
1799 rc->range <<= RC_SHIFT_BITS; | 1799 rc->range <<= RC_SHIFT_BITS; |
1800 rc->code = (rc->code << RC_SHIFT_BITS) + rc->in[rc->in_pos++]; | 1800 rc->code = (rc->code << RC_SHIFT_BITS) + rc->in[rc->in_pos++]; |
1801 } | 1801 } |
1802 } | 1802 } |
1803 | 1803 |
1804 /* | 1804 /* |
1805 * Decode one bit. In some versions, this function has been splitted in three | 1805 * Decode one bit. In some versions, this function has been splitted in three |
1806 * functions so that the compiler is supposed to be able to more easily avoid | 1806 * functions so that the compiler is supposed to be able to more easily avoid |
1812 * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care, | 1812 * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care, |
1813 * and it generates 10-20 % faster code than GCC 3.x from this file anyway.) | 1813 * and it generates 10-20 % faster code than GCC 3.x from this file anyway.) |
1814 */ | 1814 */ |
1815 static inline int rc_bit(struct rc_dec *rc, uint16_t *prob) | 1815 static inline int rc_bit(struct rc_dec *rc, uint16_t *prob) |
1816 { | 1816 { |
1817 uint32_t bound; | 1817 uint32_t bound; |
1818 int bit; | 1818 int bit; |
1819 | 1819 |
1820 rc_normalize(rc); | 1820 rc_normalize(rc); |
1821 bound = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * *prob; | 1821 bound = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * *prob; |
1822 if (rc->code < bound) { | 1822 if (rc->code < bound) { |
1823 rc->range = bound; | 1823 rc->range = bound; |
1824 *prob += (RC_BIT_MODEL_TOTAL - *prob) >> RC_MOVE_BITS; | 1824 *prob += (RC_BIT_MODEL_TOTAL - *prob) >> RC_MOVE_BITS; |
1825 bit = 0; | 1825 bit = 0; |
1826 } else { | 1826 } else { |
1827 rc->range -= bound; | 1827 rc->range -= bound; |
1828 rc->code -= bound; | 1828 rc->code -= bound; |
1829 *prob -= *prob >> RC_MOVE_BITS; | 1829 *prob -= *prob >> RC_MOVE_BITS; |
1830 bit = 1; | 1830 bit = 1; |
1831 } | 1831 } |
1832 | 1832 |
1833 return bit; | 1833 return bit; |
1834 } | 1834 } |
1835 | 1835 |
1836 /* Decode a bittree starting from the most significant bit. */ | 1836 /* Decode a bittree starting from the most significant bit. */ |
1837 static inline uint32_t rc_bittree(struct rc_dec *rc, | 1837 static inline uint32_t rc_bittree(struct rc_dec *rc, |
1838 uint16_t *probs, uint32_t limit) | 1838 uint16_t *probs, uint32_t limit) |
1839 { | 1839 { |
1840 uint32_t symbol = 1; | 1840 uint32_t symbol = 1; |
1841 | 1841 |
1842 do { | 1842 do { |
1843 if (rc_bit(rc, &probs[symbol])) | 1843 if (rc_bit(rc, &probs[symbol])) |
1844 symbol = (symbol << 1) + 1; | 1844 symbol = (symbol << 1) + 1; |
1845 else | 1845 else |
1846 symbol <<= 1; | 1846 symbol <<= 1; |
1847 } while (symbol < limit); | 1847 } while (symbol < limit); |
1848 | 1848 |
1849 return symbol; | 1849 return symbol; |
1850 } | 1850 } |
1851 | 1851 |
1852 /* Decode a bittree starting from the least significant bit. */ | 1852 /* Decode a bittree starting from the least significant bit. */ |
1853 static inline void rc_bittree_reverse(struct rc_dec *rc, | 1853 static inline void rc_bittree_reverse(struct rc_dec *rc, |
1854 uint16_t *probs, | 1854 uint16_t *probs, |
1855 uint32_t *dest, uint32_t limit) | 1855 uint32_t *dest, uint32_t limit) |
1856 { | 1856 { |
1857 uint32_t symbol = 1; | 1857 uint32_t symbol = 1; |
1858 uint32_t i = 0; | 1858 uint32_t i = 0; |
1859 | 1859 |
1860 do { | 1860 do { |
1861 if (rc_bit(rc, &probs[symbol])) { | 1861 if (rc_bit(rc, &probs[symbol])) { |
1862 symbol = (symbol << 1) + 1; | 1862 symbol = (symbol << 1) + 1; |
1863 *dest += 1 << i; | 1863 *dest += 1 << i; |
1864 } else { | 1864 } else { |
1865 symbol <<= 1; | 1865 symbol <<= 1; |
1866 } | 1866 } |
1867 } while (++i < limit); | 1867 } while (++i < limit); |
1868 } | 1868 } |
1869 | 1869 |
1870 /* Decode direct bits (fixed fifty-fifty probability) */ | 1870 /* Decode direct bits (fixed fifty-fifty probability) */ |
1871 static inline void rc_direct(struct rc_dec *rc, uint32_t *dest, uint32_t limit) | 1871 static inline void rc_direct(struct rc_dec *rc, uint32_t *dest, uint32_t limit) |
1872 { | 1872 { |
1873 uint32_t mask; | 1873 uint32_t mask; |
1874 | 1874 |
1875 do { | 1875 do { |
1876 rc_normalize(rc); | 1876 rc_normalize(rc); |
1877 rc->range >>= 1; | 1877 rc->range >>= 1; |
1878 rc->code -= rc->range; | 1878 rc->code -= rc->range; |
1879 mask = (uint32_t)0 - (rc->code >> 31); | 1879 mask = (uint32_t)0 - (rc->code >> 31); |
1880 rc->code += rc->range & mask; | 1880 rc->code += rc->range & mask; |
1881 *dest = (*dest << 1) + (mask + 1); | 1881 *dest = (*dest << 1) + (mask + 1); |
1882 } while (--limit > 0); | 1882 } while (--limit > 0); |
1883 } | 1883 } |
1884 | 1884 |
1885 /******** | 1885 /******** |
1886 * LZMA * | 1886 * LZMA * |
1887 ********/ | 1887 ********/ |
1888 | 1888 |
1889 /* Get pointer to literal coder probability array. */ | 1889 /* Get pointer to literal coder probability array. */ |
1890 static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s) | 1890 static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s) |
1891 { | 1891 { |
1892 uint32_t prev_byte = dict_get(&s->dict, 0); | 1892 uint32_t prev_byte = dict_get(&s->dict, 0); |
1893 uint32_t low = prev_byte >> (8 - s->lzma.lc); | 1893 uint32_t low = prev_byte >> (8 - s->lzma.lc); |
1894 uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc; | 1894 uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc; |
1895 return s->lzma.literal[low + high]; | 1895 return s->lzma.literal[low + high]; |
1896 } | 1896 } |
1897 | 1897 |
1898 /* Decode a literal (one 8-bit byte) */ | 1898 /* Decode a literal (one 8-bit byte) */ |
1899 static void lzma_literal(struct xz_dec_lzma2 *s) | 1899 static void lzma_literal(struct xz_dec_lzma2 *s) |
1900 { | 1900 { |
1901 uint16_t *probs; | 1901 uint16_t *probs; |
1902 uint32_t symbol; | 1902 uint32_t symbol; |
1903 uint32_t match_byte; | 1903 uint32_t match_byte; |
1904 uint32_t match_bit; | 1904 uint32_t match_bit; |
1905 uint32_t offset; | 1905 uint32_t offset; |
1906 uint32_t i; | 1906 uint32_t i; |
1907 | 1907 |
1908 probs = lzma_literal_probs(s); | 1908 probs = lzma_literal_probs(s); |
1909 | 1909 |
1910 if (lzma_state_is_literal(s->lzma.state)) { | 1910 if (lzma_state_is_literal(s->lzma.state)) { |
1911 symbol = rc_bittree(&s->rc, probs, 0x100); | 1911 symbol = rc_bittree(&s->rc, probs, 0x100); |
1912 } else { | 1912 } else { |
1913 symbol = 1; | 1913 symbol = 1; |
1914 match_byte = dict_get(&s->dict, s->lzma.rep0) << 1; | 1914 match_byte = dict_get(&s->dict, s->lzma.rep0) << 1; |
1915 offset = 0x100; | 1915 offset = 0x100; |
1916 | 1916 |
1917 do { | 1917 do { |
1918 match_bit = match_byte & offset; | 1918 match_bit = match_byte & offset; |
1919 match_byte <<= 1; | 1919 match_byte <<= 1; |
1920 i = offset + match_bit + symbol; | 1920 i = offset + match_bit + symbol; |
1921 | 1921 |
1922 if (rc_bit(&s->rc, &probs[i])) { | 1922 if (rc_bit(&s->rc, &probs[i])) { |
1923 symbol = (symbol << 1) + 1; | 1923 symbol = (symbol << 1) + 1; |
1924 offset &= match_bit; | 1924 offset &= match_bit; |
1925 } else { | 1925 } else { |
1926 symbol <<= 1; | 1926 symbol <<= 1; |
1927 offset &= ~match_bit; | 1927 offset &= ~match_bit; |
1928 } | 1928 } |
1929 } while (symbol < 0x100); | 1929 } while (symbol < 0x100); |
1930 } | 1930 } |
1931 | 1931 |
1932 dict_put(&s->dict, (uint8_t)symbol); | 1932 dict_put(&s->dict, (uint8_t)symbol); |
1933 lzma_state_literal(&s->lzma.state); | 1933 lzma_state_literal(&s->lzma.state); |
1934 } | 1934 } |
1935 | 1935 |
1936 /* Decode the length of the match into s->lzma.len. */ | 1936 /* Decode the length of the match into s->lzma.len. */ |
1937 static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l, | 1937 static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l, |
1938 uint32_t pos_state) | 1938 uint32_t pos_state) |
1939 { | 1939 { |
1940 uint16_t *probs; | 1940 uint16_t *probs; |
1941 uint32_t limit; | 1941 uint32_t limit; |
1942 | 1942 |
1943 if (!rc_bit(&s->rc, &l->choice)) { | 1943 if (!rc_bit(&s->rc, &l->choice)) { |
1944 probs = l->low[pos_state]; | 1944 probs = l->low[pos_state]; |
1945 limit = LEN_LOW_SYMBOLS; | 1945 limit = LEN_LOW_SYMBOLS; |
1946 s->lzma.len = MATCH_LEN_MIN; | 1946 s->lzma.len = MATCH_LEN_MIN; |
1947 } else { | 1947 } else { |
1948 if (!rc_bit(&s->rc, &l->choice2)) { | 1948 if (!rc_bit(&s->rc, &l->choice2)) { |
1949 probs = l->mid[pos_state]; | 1949 probs = l->mid[pos_state]; |
1950 limit = LEN_MID_SYMBOLS; | 1950 limit = LEN_MID_SYMBOLS; |
1951 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; | 1951 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; |
1952 } else { | 1952 } else { |
1953 probs = l->high; | 1953 probs = l->high; |
1954 limit = LEN_HIGH_SYMBOLS; | 1954 limit = LEN_HIGH_SYMBOLS; |
1955 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS | 1955 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS |
1956 + LEN_MID_SYMBOLS; | 1956 + LEN_MID_SYMBOLS; |
1957 } | 1957 } |
1958 } | 1958 } |
1959 | 1959 |
1960 s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit; | 1960 s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit; |
1961 } | 1961 } |
1962 | 1962 |
1963 /* Decode a match. The distance will be stored in s->lzma.rep0. */ | 1963 /* Decode a match. The distance will be stored in s->lzma.rep0. */ |
1964 static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state) | 1964 static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state) |
1965 { | 1965 { |
1966 uint16_t *probs; | 1966 uint16_t *probs; |
1967 uint32_t dist_slot; | 1967 uint32_t dist_slot; |
1968 uint32_t limit; | 1968 uint32_t limit; |
1969 | 1969 |
1970 lzma_state_match(&s->lzma.state); | 1970 lzma_state_match(&s->lzma.state); |
1971 | 1971 |
1972 s->lzma.rep3 = s->lzma.rep2; | 1972 s->lzma.rep3 = s->lzma.rep2; |
1973 s->lzma.rep2 = s->lzma.rep1; | 1973 s->lzma.rep2 = s->lzma.rep1; |
1974 s->lzma.rep1 = s->lzma.rep0; | 1974 s->lzma.rep1 = s->lzma.rep0; |
1975 | 1975 |
1976 lzma_len(s, &s->lzma.match_len_dec, pos_state); | 1976 lzma_len(s, &s->lzma.match_len_dec, pos_state); |
1977 | 1977 |
1978 probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)]; | 1978 probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)]; |
1979 dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS; | 1979 dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS; |
1980 | 1980 |
1981 if (dist_slot < DIST_MODEL_START) { | 1981 if (dist_slot < DIST_MODEL_START) { |
1982 s->lzma.rep0 = dist_slot; | 1982 s->lzma.rep0 = dist_slot; |
1983 } else { | 1983 } else { |
1984 limit = (dist_slot >> 1) - 1; | 1984 limit = (dist_slot >> 1) - 1; |
1985 s->lzma.rep0 = 2 + (dist_slot & 1); | 1985 s->lzma.rep0 = 2 + (dist_slot & 1); |
1986 | 1986 |
1987 if (dist_slot < DIST_MODEL_END) { | 1987 if (dist_slot < DIST_MODEL_END) { |
1988 s->lzma.rep0 <<= limit; | 1988 s->lzma.rep0 <<= limit; |
1989 probs = s->lzma.dist_special + s->lzma.rep0 | 1989 probs = s->lzma.dist_special + s->lzma.rep0 |
1990 - dist_slot - 1; | 1990 - dist_slot - 1; |
1991 rc_bittree_reverse(&s->rc, probs, | 1991 rc_bittree_reverse(&s->rc, probs, |
1992 &s->lzma.rep0, limit); | 1992 &s->lzma.rep0, limit); |
1993 } else { | 1993 } else { |
1994 rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS); | 1994 rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS); |
1995 s->lzma.rep0 <<= ALIGN_BITS; | 1995 s->lzma.rep0 <<= ALIGN_BITS; |
1996 rc_bittree_reverse(&s->rc, s->lzma.dist_align, | 1996 rc_bittree_reverse(&s->rc, s->lzma.dist_align, |
1997 &s->lzma.rep0, ALIGN_BITS); | 1997 &s->lzma.rep0, ALIGN_BITS); |
1998 } | 1998 } |
1999 } | 1999 } |
2000 } | 2000 } |
2001 | 2001 |
2002 /* | 2002 /* |
2003 * Decode a repeated match. The distance is one of the four most recently | 2003 * Decode a repeated match. The distance is one of the four most recently |
2004 * seen matches. The distance will be stored in s->lzma.rep0. | 2004 * seen matches. The distance will be stored in s->lzma.rep0. |
2005 */ | 2005 */ |
2006 static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state) | 2006 static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state) |
2007 { | 2007 { |
2008 uint32_t tmp; | 2008 uint32_t tmp; |
2009 | 2009 |
2010 if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) { | 2010 if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) { |
2011 if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[ | 2011 if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[ |
2012 s->lzma.state][pos_state])) { | 2012 s->lzma.state][pos_state])) { |
2013 lzma_state_short_rep(&s->lzma.state); | 2013 lzma_state_short_rep(&s->lzma.state); |
2014 s->lzma.len = 1; | 2014 s->lzma.len = 1; |
2015 return; | 2015 return; |
2016 } | 2016 } |
2017 } else { | 2017 } else { |
2018 if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) { | 2018 if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) { |
2019 tmp = s->lzma.rep1; | 2019 tmp = s->lzma.rep1; |
2020 } else { | 2020 } else { |
2021 if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) { | 2021 if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) { |
2022 tmp = s->lzma.rep2; | 2022 tmp = s->lzma.rep2; |
2023 } else { | 2023 } else { |
2024 tmp = s->lzma.rep3; | 2024 tmp = s->lzma.rep3; |
2025 s->lzma.rep3 = s->lzma.rep2; | 2025 s->lzma.rep3 = s->lzma.rep2; |
2026 } | 2026 } |
2027 | 2027 |
2028 s->lzma.rep2 = s->lzma.rep1; | 2028 s->lzma.rep2 = s->lzma.rep1; |
2029 } | 2029 } |
2030 | 2030 |
2031 s->lzma.rep1 = s->lzma.rep0; | 2031 s->lzma.rep1 = s->lzma.rep0; |
2032 s->lzma.rep0 = tmp; | 2032 s->lzma.rep0 = tmp; |
2033 } | 2033 } |
2034 | 2034 |
2035 lzma_state_long_rep(&s->lzma.state); | 2035 lzma_state_long_rep(&s->lzma.state); |
2036 lzma_len(s, &s->lzma.rep_len_dec, pos_state); | 2036 lzma_len(s, &s->lzma.rep_len_dec, pos_state); |
2037 } | 2037 } |
2038 | 2038 |
2039 /* LZMA decoder core */ | 2039 /* LZMA decoder core */ |
2040 static int lzma_main(struct xz_dec_lzma2 *s) | 2040 static int lzma_main(struct xz_dec_lzma2 *s) |
2041 { | 2041 { |
2042 uint32_t pos_state; | 2042 uint32_t pos_state; |
2043 | 2043 |
2044 /* | 2044 /* |
2045 * If the dictionary was reached during the previous call, try to | 2045 * If the dictionary was reached during the previous call, try to |
2046 * finish the possibly pending repeat in the dictionary. | 2046 * finish the possibly pending repeat in the dictionary. |
2047 */ | 2047 */ |
2048 if (dict_has_space(&s->dict) && s->lzma.len > 0) | 2048 if (dict_has_space(&s->dict) && s->lzma.len > 0) |
2049 dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0); | 2049 dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0); |
2050 | 2050 |
2051 /* | 2051 /* |
2052 * Decode more LZMA symbols. One iteration may consume up to | 2052 * Decode more LZMA symbols. One iteration may consume up to |
2053 * LZMA_IN_REQUIRED - 1 bytes. | 2053 * LZMA_IN_REQUIRED - 1 bytes. |
2054 */ | 2054 */ |
2055 while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) { | 2055 while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) { |
2056 pos_state = s->dict.pos & s->lzma.pos_mask; | 2056 pos_state = s->dict.pos & s->lzma.pos_mask; |
2057 | 2057 |
2058 if (!rc_bit(&s->rc, &s->lzma.is_match[ | 2058 if (!rc_bit(&s->rc, &s->lzma.is_match[ |
2059 s->lzma.state][pos_state])) { | 2059 s->lzma.state][pos_state])) { |
2060 lzma_literal(s); | 2060 lzma_literal(s); |
2061 } else { | 2061 } else { |
2062 if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state])) | 2062 if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state])) |
2063 lzma_rep_match(s, pos_state); | 2063 lzma_rep_match(s, pos_state); |
2064 else | 2064 else |
2065 lzma_match(s, pos_state); | 2065 lzma_match(s, pos_state); |
2066 | 2066 |
2067 if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0)) | 2067 if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0)) |
2068 return 0; | 2068 return 0; |
2069 } | 2069 } |
2070 } | 2070 } |
2071 | 2071 |
2072 /* | 2072 /* |
2073 * Having the range decoder always normalized when we are outside | 2073 * Having the range decoder always normalized when we are outside |
2074 * this function makes it easier to correctly handle end of the chunk. | 2074 * this function makes it easier to correctly handle end of the chunk. |
2075 */ | 2075 */ |
2076 rc_normalize(&s->rc); | 2076 rc_normalize(&s->rc); |
2077 | 2077 |
2078 return 1; | 2078 return 1; |
2079 } | 2079 } |
2080 | 2080 |
2081 /* | 2081 /* |
2082 * Reset the LZMA decoder and range decoder state. Dictionary is nore reset | 2082 * Reset the LZMA decoder and range decoder state. Dictionary is nore reset |
2083 * here, because LZMA state may be reset without resetting the dictionary. | 2083 * here, because LZMA state may be reset without resetting the dictionary. |
2084 */ | 2084 */ |
2085 static void lzma_reset(struct xz_dec_lzma2 *s) | 2085 static void lzma_reset(struct xz_dec_lzma2 *s) |
2086 { | 2086 { |
2087 uint16_t *probs; | 2087 uint16_t *probs; |
2088 size_t i; | 2088 size_t i; |
2089 | 2089 |
2090 s->lzma.state = STATE_LIT_LIT; | 2090 s->lzma.state = STATE_LIT_LIT; |
2091 s->lzma.rep0 = 0; | 2091 s->lzma.rep0 = 0; |
2092 s->lzma.rep1 = 0; | 2092 s->lzma.rep1 = 0; |
2093 s->lzma.rep2 = 0; | 2093 s->lzma.rep2 = 0; |
2094 s->lzma.rep3 = 0; | 2094 s->lzma.rep3 = 0; |
2095 | 2095 |
2096 /* | 2096 /* |
2097 * All probabilities are initialized to the same value. This hack | 2097 * All probabilities are initialized to the same value. This hack |
2098 * makes the code smaller by avoiding a separate loop for each | 2098 * makes the code smaller by avoiding a separate loop for each |
2099 * probability array. | 2099 * probability array. |
2100 * | 2100 * |
2101 * This could be optimized so that only that part of literal | 2101 * This could be optimized so that only that part of literal |
2102 * probabilities that are actually required. In the common case | 2102 * probabilities that are actually required. In the common case |
2103 * we would write 12 KiB less. | 2103 * we would write 12 KiB less. |
2104 */ | 2104 */ |
2105 probs = s->lzma.is_match[0]; | 2105 probs = s->lzma.is_match[0]; |
2106 for (i = 0; i < PROBS_TOTAL; ++i) | 2106 for (i = 0; i < PROBS_TOTAL; ++i) |
2107 probs[i] = RC_BIT_MODEL_TOTAL / 2; | 2107 probs[i] = RC_BIT_MODEL_TOTAL / 2; |
2108 | 2108 |
2109 rc_reset(&s->rc); | 2109 rc_reset(&s->rc); |
2110 } | 2110 } |
2111 | 2111 |
2112 /* | 2112 /* |
2113 * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks | 2113 * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks |
2114 * from the decoded lp and pb values. On success, the LZMA decoder state is | 2114 * from the decoded lp and pb values. On success, the LZMA decoder state is |
2115 * reset and true is returned. | 2115 * reset and true is returned. |
2116 */ | 2116 */ |
2117 static int lzma_props(struct xz_dec_lzma2 *s, uint8_t props) | 2117 static int lzma_props(struct xz_dec_lzma2 *s, uint8_t props) |
2118 { | 2118 { |
2119 if (props > (4 * 5 + 4) * 9 + 8) | 2119 if (props > (4 * 5 + 4) * 9 + 8) |
2120 return 0; | 2120 return 0; |
2121 | 2121 |
2122 s->lzma.pos_mask = 0; | 2122 s->lzma.pos_mask = 0; |
2123 while (props >= 9 * 5) { | 2123 while (props >= 9 * 5) { |
2124 props -= 9 * 5; | 2124 props -= 9 * 5; |
2125 ++s->lzma.pos_mask; | 2125 ++s->lzma.pos_mask; |
2126 } | 2126 } |
2127 | 2127 |
2128 s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1; | 2128 s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1; |
2129 | 2129 |
2130 s->lzma.literal_pos_mask = 0; | 2130 s->lzma.literal_pos_mask = 0; |
2131 while (props >= 9) { | 2131 while (props >= 9) { |
2132 props -= 9; | 2132 props -= 9; |
2133 ++s->lzma.literal_pos_mask; | 2133 ++s->lzma.literal_pos_mask; |
2134 } | 2134 } |
2135 | 2135 |
2136 s->lzma.lc = props; | 2136 s->lzma.lc = props; |
2137 | 2137 |
2138 if (s->lzma.lc + s->lzma.literal_pos_mask > 4) | 2138 if (s->lzma.lc + s->lzma.literal_pos_mask > 4) |
2139 return 0; | 2139 return 0; |
2140 | 2140 |
2141 s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1; | 2141 s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1; |
2142 | 2142 |
2143 lzma_reset(s); | 2143 lzma_reset(s); |
2144 | 2144 |
2145 return 1; | 2145 return 1; |
2146 } | 2146 } |
2147 | 2147 |
2148 /********* | 2148 /********* |
2149 * LZMA2 * | 2149 * LZMA2 * |
2150 *********/ | 2150 *********/ |
2161 * function. We decode a few bytes from the temporary buffer so that we can | 2161 * function. We decode a few bytes from the temporary buffer so that we can |
2162 * continue decoding from the caller-supplied input buffer again. | 2162 * continue decoding from the caller-supplied input buffer again. |
2163 */ | 2163 */ |
2164 static int lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b) | 2164 static int lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b) |
2165 { | 2165 { |
2166 size_t in_avail; | 2166 size_t in_avail; |
2167 uint32_t tmp; | 2167 uint32_t tmp; |
2168 | 2168 |
2169 in_avail = b->in_size - b->in_pos; | 2169 in_avail = b->in_size - b->in_pos; |
2170 if (s->temp.size > 0 || s->lzma2.compressed == 0) { | 2170 if (s->temp.size > 0 || s->lzma2.compressed == 0) { |
2171 tmp = 2 * LZMA_IN_REQUIRED - s->temp.size; | 2171 tmp = 2 * LZMA_IN_REQUIRED - s->temp.size; |
2172 if (tmp > s->lzma2.compressed - s->temp.size) | 2172 if (tmp > s->lzma2.compressed - s->temp.size) |
2173 tmp = s->lzma2.compressed - s->temp.size; | 2173 tmp = s->lzma2.compressed - s->temp.size; |
2174 if (tmp > in_avail) | 2174 if (tmp > in_avail) |
2175 tmp = in_avail; | 2175 tmp = in_avail; |
2176 | 2176 |
2177 memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp); | 2177 memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp); |
2178 | 2178 |
2179 if (s->temp.size + tmp == s->lzma2.compressed) { | 2179 if (s->temp.size + tmp == s->lzma2.compressed) { |
2180 memset(s->temp.buf + s->temp.size + tmp, 0, | 2180 memset(s->temp.buf + s->temp.size + tmp, 0, |
2181 sizeof(s->temp.buf) | 2181 sizeof(s->temp.buf) |
2182 - s->temp.size - tmp); | 2182 - s->temp.size - tmp); |
2183 s->rc.in_limit = s->temp.size + tmp; | 2183 s->rc.in_limit = s->temp.size + tmp; |
2184 } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) { | 2184 } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) { |
2185 s->temp.size += tmp; | 2185 s->temp.size += tmp; |
2186 b->in_pos += tmp; | 2186 b->in_pos += tmp; |
2187 return 1; | 2187 return 1; |
2188 } else { | 2188 } else { |
2189 s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED; | 2189 s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED; |
2190 } | 2190 } |
2191 | 2191 |
2192 s->rc.in = s->temp.buf; | 2192 s->rc.in = s->temp.buf; |
2193 s->rc.in_pos = 0; | 2193 s->rc.in_pos = 0; |
2194 | 2194 |
2195 if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp) | 2195 if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp) |
2196 return 0; | 2196 return 0; |
2197 | 2197 |
2198 s->lzma2.compressed -= s->rc.in_pos; | 2198 s->lzma2.compressed -= s->rc.in_pos; |
2199 | 2199 |
2200 if (s->rc.in_pos < s->temp.size) { | 2200 if (s->rc.in_pos < s->temp.size) { |
2201 s->temp.size -= s->rc.in_pos; | 2201 s->temp.size -= s->rc.in_pos; |
2202 memmove(s->temp.buf, s->temp.buf + s->rc.in_pos, | 2202 memmove(s->temp.buf, s->temp.buf + s->rc.in_pos, |
2203 s->temp.size); | 2203 s->temp.size); |
2204 return 1; | 2204 return 1; |
2205 } | 2205 } |
2206 | 2206 |
2207 b->in_pos += s->rc.in_pos - s->temp.size; | 2207 b->in_pos += s->rc.in_pos - s->temp.size; |
2208 s->temp.size = 0; | 2208 s->temp.size = 0; |
2209 } | 2209 } |
2210 | 2210 |
2211 in_avail = b->in_size - b->in_pos; | 2211 in_avail = b->in_size - b->in_pos; |
2212 if (in_avail >= LZMA_IN_REQUIRED) { | 2212 if (in_avail >= LZMA_IN_REQUIRED) { |
2213 s->rc.in = b->in; | 2213 s->rc.in = b->in; |
2214 s->rc.in_pos = b->in_pos; | 2214 s->rc.in_pos = b->in_pos; |
2215 | 2215 |
2216 if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED) | 2216 if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED) |
2217 s->rc.in_limit = b->in_pos + s->lzma2.compressed; | 2217 s->rc.in_limit = b->in_pos + s->lzma2.compressed; |
2218 else | 2218 else |
2219 s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED; | 2219 s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED; |
2220 | 2220 |
2221 if (!lzma_main(s)) | 2221 if (!lzma_main(s)) |
2222 return 0; | 2222 return 0; |
2223 | 2223 |
2224 in_avail = s->rc.in_pos - b->in_pos; | 2224 in_avail = s->rc.in_pos - b->in_pos; |
2225 if (in_avail > s->lzma2.compressed) return 0; | 2225 if (in_avail > s->lzma2.compressed) return 0; |
2226 | 2226 |
2227 s->lzma2.compressed -= in_avail; | 2227 s->lzma2.compressed -= in_avail; |
2228 b->in_pos = s->rc.in_pos; | 2228 b->in_pos = s->rc.in_pos; |
2229 } | 2229 } |
2230 | 2230 |
2231 in_avail = b->in_size - b->in_pos; | 2231 in_avail = b->in_size - b->in_pos; |
2232 if (in_avail < LZMA_IN_REQUIRED) { | 2232 if (in_avail < LZMA_IN_REQUIRED) { |
2233 if (in_avail > s->lzma2.compressed) | 2233 if (in_avail > s->lzma2.compressed) |
2234 in_avail = s->lzma2.compressed; | 2234 in_avail = s->lzma2.compressed; |
2235 | 2235 |
2236 memcpy(s->temp.buf, b->in + b->in_pos, in_avail); | 2236 memcpy(s->temp.buf, b->in + b->in_pos, in_avail); |
2237 s->temp.size = in_avail; | 2237 s->temp.size = in_avail; |
2238 b->in_pos += in_avail; | 2238 b->in_pos += in_avail; |
2239 } | 2239 } |
2240 | 2240 |
2241 return 1; | 2241 return 1; |
2242 } | 2242 } |
2243 | 2243 |
2244 /* | 2244 /* |
2245 * Take care of the LZMA2 control layer, and forward the job of actual LZMA | 2245 * Take care of the LZMA2 control layer, and forward the job of actual LZMA |
2246 * decoding or copying of uncompressed chunks to other functions. | 2246 * decoding or copying of uncompressed chunks to other functions. |
2247 */ | 2247 */ |
2248 enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, | 2248 enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, |
2249 struct xz_buf *b) | 2249 struct xz_buf *b) |
2250 { | 2250 { |
2251 uint32_t tmp; | 2251 uint32_t tmp; |
2252 | 2252 |
2253 while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) { | 2253 while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) { |
2254 switch (s->lzma2.sequence) { | 2254 switch (s->lzma2.sequence) { |
2255 case SEQ_CONTROL: | 2255 case SEQ_CONTROL: |
2256 /* | 2256 /* |
2257 * LZMA2 control byte | 2257 * LZMA2 control byte |
2258 * | 2258 * |
2259 * Exact values: | 2259 * Exact values: |
2260 * 0x00 End marker | 2260 * 0x00 End marker |
2261 * 0x01 Dictionary reset followed by | 2261 * 0x01 Dictionary reset followed by |
2262 * an uncompressed chunk | 2262 * an uncompressed chunk |
2263 * 0x02 Uncompressed chunk (no dictionary reset) | 2263 * 0x02 Uncompressed chunk (no dictionary reset) |
2264 * | 2264 * |
2265 * Highest three bits (s->control & 0xE0): | 2265 * Highest three bits (s->control & 0xE0): |
2266 * 0xE0 Dictionary reset, new properties and state | 2266 * 0xE0 Dictionary reset, new properties and state |
2267 * reset, followed by LZMA compressed chunk | 2267 * reset, followed by LZMA compressed chunk |
2268 * 0xC0 New properties and state reset, followed | 2268 * 0xC0 New properties and state reset, followed |
2269 * by LZMA compressed chunk (no dictionary | 2269 * by LZMA compressed chunk (no dictionary |
2270 * reset) | 2270 * reset) |
2271 * 0xA0 State reset using old properties, | 2271 * 0xA0 State reset using old properties, |
2272 * followed by LZMA compressed chunk (no | 2272 * followed by LZMA compressed chunk (no |
2273 * dictionary reset) | 2273 * dictionary reset) |
2274 * 0x80 LZMA chunk (no dictionary or state reset) | 2274 * 0x80 LZMA chunk (no dictionary or state reset) |
2275 * | 2275 * |
2276 * For LZMA compressed chunks, the lowest five bits | 2276 * For LZMA compressed chunks, the lowest five bits |
2277 * (s->control & 1F) are the highest bits of the | 2277 * (s->control & 1F) are the highest bits of the |
2278 * uncompressed size (bits 16-20). | 2278 * uncompressed size (bits 16-20). |
2279 * | 2279 * |
2280 * A new LZMA2 stream must begin with a dictionary | 2280 * A new LZMA2 stream must begin with a dictionary |
2281 * reset. The first LZMA chunk must set new | 2281 * reset. The first LZMA chunk must set new |
2282 * properties and reset the LZMA state. | 2282 * properties and reset the LZMA state. |
2283 * | 2283 * |
2284 * Values that don't match anything described above | 2284 * Values that don't match anything described above |
2285 * are invalid and we return XZ_DATA_ERROR. | 2285 * are invalid and we return XZ_DATA_ERROR. |
2286 */ | 2286 */ |
2287 tmp = b->in[b->in_pos++]; | 2287 tmp = b->in[b->in_pos++]; |
2288 | 2288 |
2289 if (tmp == 0x00) | 2289 if (tmp == 0x00) |
2290 return XZ_STREAM_END; | 2290 return XZ_STREAM_END; |
2291 | 2291 |
2292 if (tmp >= 0xE0 || tmp == 0x01) { | 2292 if (tmp >= 0xE0 || tmp == 0x01) { |
2293 s->lzma2.need_props = 1; | 2293 s->lzma2.need_props = 1; |
2294 s->lzma2.need_dict_reset = 0; | 2294 s->lzma2.need_dict_reset = 0; |
2295 dict_reset(&s->dict, b); | 2295 dict_reset(&s->dict, b); |
2296 } else if (s->lzma2.need_dict_reset) { | 2296 } else if (s->lzma2.need_dict_reset) { |
2297 return XZ_DATA_ERROR; | 2297 return XZ_DATA_ERROR; |
2298 } | 2298 } |
2299 | 2299 |
2300 if (tmp >= 0x80) { | 2300 if (tmp >= 0x80) { |
2301 s->lzma2.uncompressed = (tmp & 0x1F) << 16; | 2301 s->lzma2.uncompressed = (tmp & 0x1F) << 16; |
2302 s->lzma2.sequence = SEQ_UNCOMPRESSED_1; | 2302 s->lzma2.sequence = SEQ_UNCOMPRESSED_1; |
2303 | 2303 |
2304 if (tmp >= 0xC0) { | 2304 if (tmp >= 0xC0) { |
2305 /* | 2305 /* |
2306 * When there are new properties, | 2306 * When there are new properties, |
2307 * state reset is done at | 2307 * state reset is done at |
2308 * SEQ_PROPERTIES. | 2308 * SEQ_PROPERTIES. |
2309 */ | 2309 */ |
2310 s->lzma2.need_props = 0; | 2310 s->lzma2.need_props = 0; |
2311 s->lzma2.next_sequence | 2311 s->lzma2.next_sequence |
2312 = SEQ_PROPERTIES; | 2312 = SEQ_PROPERTIES; |
2313 | 2313 |
2314 } else if (s->lzma2.need_props) { | 2314 } else if (s->lzma2.need_props) { |
2315 return XZ_DATA_ERROR; | 2315 return XZ_DATA_ERROR; |
2316 | 2316 |
2317 } else { | 2317 } else { |
2318 s->lzma2.next_sequence | 2318 s->lzma2.next_sequence |
2319 = SEQ_LZMA_PREPARE; | 2319 = SEQ_LZMA_PREPARE; |
2320 if (tmp >= 0xA0) | 2320 if (tmp >= 0xA0) |
2321 lzma_reset(s); | 2321 lzma_reset(s); |
2322 } | 2322 } |
2323 } else { | 2323 } else { |
2324 if (tmp > 0x02) | 2324 if (tmp > 0x02) |
2325 return XZ_DATA_ERROR; | 2325 return XZ_DATA_ERROR; |
2326 | 2326 |
2327 s->lzma2.sequence = SEQ_COMPRESSED_0; | 2327 s->lzma2.sequence = SEQ_COMPRESSED_0; |
2328 s->lzma2.next_sequence = SEQ_COPY; | 2328 s->lzma2.next_sequence = SEQ_COPY; |
2329 } | 2329 } |
2330 | 2330 |
2331 break; | 2331 break; |
2332 | 2332 |
2333 case SEQ_UNCOMPRESSED_1: | 2333 case SEQ_UNCOMPRESSED_1: |
2334 s->lzma2.uncompressed | 2334 s->lzma2.uncompressed |
2335 += (uint32_t)b->in[b->in_pos++] << 8; | 2335 += (uint32_t)b->in[b->in_pos++] << 8; |
2336 s->lzma2.sequence = SEQ_UNCOMPRESSED_2; | 2336 s->lzma2.sequence = SEQ_UNCOMPRESSED_2; |
2337 break; | 2337 break; |
2338 | 2338 |
2339 case SEQ_UNCOMPRESSED_2: | 2339 case SEQ_UNCOMPRESSED_2: |
2340 s->lzma2.uncompressed | 2340 s->lzma2.uncompressed |
2341 += (uint32_t)b->in[b->in_pos++] + 1; | 2341 += (uint32_t)b->in[b->in_pos++] + 1; |
2342 s->lzma2.sequence = SEQ_COMPRESSED_0; | 2342 s->lzma2.sequence = SEQ_COMPRESSED_0; |
2343 break; | 2343 break; |
2344 | 2344 |
2345 case SEQ_COMPRESSED_0: | 2345 case SEQ_COMPRESSED_0: |
2346 s->lzma2.compressed | 2346 s->lzma2.compressed |
2347 = (uint32_t)b->in[b->in_pos++] << 8; | 2347 = (uint32_t)b->in[b->in_pos++] << 8; |
2348 s->lzma2.sequence = SEQ_COMPRESSED_1; | 2348 s->lzma2.sequence = SEQ_COMPRESSED_1; |
2349 break; | 2349 break; |
2350 | 2350 |
2351 case SEQ_COMPRESSED_1: | 2351 case SEQ_COMPRESSED_1: |
2352 s->lzma2.compressed | 2352 s->lzma2.compressed |
2353 += (uint32_t)b->in[b->in_pos++] + 1; | 2353 += (uint32_t)b->in[b->in_pos++] + 1; |
2354 s->lzma2.sequence = s->lzma2.next_sequence; | 2354 s->lzma2.sequence = s->lzma2.next_sequence; |
2355 break; | 2355 break; |
2356 | 2356 |
2357 case SEQ_PROPERTIES: | 2357 case SEQ_PROPERTIES: |
2358 if (!lzma_props(s, b->in[b->in_pos++])) | 2358 if (!lzma_props(s, b->in[b->in_pos++])) |
2359 return XZ_DATA_ERROR; | 2359 return XZ_DATA_ERROR; |
2360 | 2360 |
2361 s->lzma2.sequence = SEQ_LZMA_PREPARE; | 2361 s->lzma2.sequence = SEQ_LZMA_PREPARE; |
2362 | 2362 |
2363 case SEQ_LZMA_PREPARE: | 2363 case SEQ_LZMA_PREPARE: |
2364 if (s->lzma2.compressed < RC_INIT_BYTES) | 2364 if (s->lzma2.compressed < RC_INIT_BYTES) |
2365 return XZ_DATA_ERROR; | 2365 return XZ_DATA_ERROR; |
2366 | 2366 |
2367 if (!rc_read_init(&s->rc, b)) | 2367 if (!rc_read_init(&s->rc, b)) |
2368 return XZ_OK; | 2368 return XZ_OK; |
2369 | 2369 |
2370 s->lzma2.compressed -= RC_INIT_BYTES; | 2370 s->lzma2.compressed -= RC_INIT_BYTES; |
2371 s->lzma2.sequence = SEQ_LZMA_RUN; | 2371 s->lzma2.sequence = SEQ_LZMA_RUN; |
2372 | 2372 |
2373 case SEQ_LZMA_RUN: | 2373 case SEQ_LZMA_RUN: |
2374 /* | 2374 /* |
2375 * Set dictionary limit to indicate how much we want | 2375 * Set dictionary limit to indicate how much we want |
2376 * to be encoded at maximum. Decode new data into the | 2376 * to be encoded at maximum. Decode new data into the |
2377 * dictionary. Flush the new data from dictionary to | 2377 * dictionary. Flush the new data from dictionary to |
2378 * b->out. Check if we finished decoding this chunk. | 2378 * b->out. Check if we finished decoding this chunk. |
2379 * In case the dictionary got full but we didn't fill | 2379 * In case the dictionary got full but we didn't fill |
2380 * the output buffer yet, we may run this loop | 2380 * the output buffer yet, we may run this loop |
2381 * multiple times without changing s->lzma2.sequence. | 2381 * multiple times without changing s->lzma2.sequence. |
2382 */ | 2382 */ |
2383 dict_limit(&s->dict, min_t(size_t, | 2383 dict_limit(&s->dict, min_t(size_t, |
2384 b->out_size - b->out_pos, | 2384 b->out_size - b->out_pos, |
2385 s->lzma2.uncompressed)); | 2385 s->lzma2.uncompressed)); |
2386 if (!lzma2_lzma(s, b)) | 2386 if (!lzma2_lzma(s, b)) |
2387 return XZ_DATA_ERROR; | 2387 return XZ_DATA_ERROR; |
2388 | 2388 |
2389 s->lzma2.uncompressed -= dict_flush(&s->dict, b); | 2389 s->lzma2.uncompressed -= dict_flush(&s->dict, b); |
2390 | 2390 |
2391 if (s->lzma2.uncompressed == 0) { | 2391 if (s->lzma2.uncompressed == 0) { |
2392 if (s->lzma2.compressed > 0 || s->lzma.len > 0 | 2392 if (s->lzma2.compressed > 0 || s->lzma.len > 0 |
2393 || !rc_is_finished(&s->rc)) | 2393 || !rc_is_finished(&s->rc)) |
2394 return XZ_DATA_ERROR; | 2394 return XZ_DATA_ERROR; |
2395 | 2395 |
2396 rc_reset(&s->rc); | 2396 rc_reset(&s->rc); |
2397 s->lzma2.sequence = SEQ_CONTROL; | 2397 s->lzma2.sequence = SEQ_CONTROL; |
2398 | 2398 |
2399 } else if (b->out_pos == b->out_size | 2399 } else if (b->out_pos == b->out_size |
2400 || (b->in_pos == b->in_size | 2400 || (b->in_pos == b->in_size |
2401 && s->temp.size | 2401 && s->temp.size |
2402 < s->lzma2.compressed)) { | 2402 < s->lzma2.compressed)) { |
2403 return XZ_OK; | 2403 return XZ_OK; |
2404 } | 2404 } |
2405 | 2405 |
2406 break; | 2406 break; |
2407 | 2407 |
2408 case SEQ_COPY: | 2408 case SEQ_COPY: |
2409 dict_uncompressed(&s->dict, b, &s->lzma2.compressed); | 2409 dict_uncompressed(&s->dict, b, &s->lzma2.compressed); |
2410 if (s->lzma2.compressed > 0) | 2410 if (s->lzma2.compressed > 0) |
2411 return XZ_OK; | 2411 return XZ_OK; |
2412 | 2412 |
2413 s->lzma2.sequence = SEQ_CONTROL; | 2413 s->lzma2.sequence = SEQ_CONTROL; |
2414 break; | 2414 break; |
2415 } | 2415 } |
2416 } | 2416 } |
2417 | 2417 |
2418 return XZ_OK; | 2418 return XZ_OK; |
2419 } | 2419 } |
2420 | 2420 |
2421 struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode, | 2421 struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode, |
2422 uint32_t dict_max) | 2422 uint32_t dict_max) |
2423 { | 2423 { |
2424 struct xz_dec_lzma2 *s = malloc(sizeof(*s)); | 2424 struct xz_dec_lzma2 *s = malloc(sizeof(*s)); |
2425 if (s == NULL) | 2425 if (s == NULL) |
2426 return NULL; | 2426 return NULL; |
2427 | 2427 |
2428 s->dict.mode = mode; | 2428 s->dict.mode = mode; |
2429 s->dict.size_max = dict_max; | 2429 s->dict.size_max = dict_max; |
2430 | 2430 |
2431 if (DEC_IS_PREALLOC(mode)) { | 2431 if (DEC_IS_PREALLOC(mode)) { |
2432 s->dict.buf = malloc(dict_max); | 2432 s->dict.buf = malloc(dict_max); |
2433 if (s->dict.buf == NULL) { | 2433 if (s->dict.buf == NULL) { |
2434 free(s); | 2434 free(s); |
2435 return NULL; | 2435 return NULL; |
2436 } | 2436 } |
2437 } else if (DEC_IS_DYNALLOC(mode)) { | 2437 } else if (DEC_IS_DYNALLOC(mode)) { |
2438 s->dict.buf = NULL; | 2438 s->dict.buf = NULL; |
2439 s->dict.allocated = 0; | 2439 s->dict.allocated = 0; |
2440 } | 2440 } |
2441 | 2441 |
2442 return s; | 2442 return s; |
2443 } | 2443 } |
2444 | 2444 |
2445 enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props) | 2445 enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props) |
2446 { | 2446 { |
2447 /* This limits dictionary size to 3 GiB to keep parsing simpler. */ | 2447 /* This limits dictionary size to 3 GiB to keep parsing simpler. */ |
2448 if (props > 39) | 2448 if (props > 39) |
2449 return XZ_OPTIONS_ERROR; | 2449 return XZ_OPTIONS_ERROR; |
2450 | 2450 |
2451 s->dict.size = 2 + (props & 1); | 2451 s->dict.size = 2 + (props & 1); |
2452 s->dict.size <<= (props >> 1) + 11; | 2452 s->dict.size <<= (props >> 1) + 11; |
2453 | 2453 |
2454 if (DEC_IS_MULTI(s->dict.mode)) { | 2454 if (DEC_IS_MULTI(s->dict.mode)) { |
2455 if (s->dict.size > s->dict.size_max) | 2455 if (s->dict.size > s->dict.size_max) |
2456 return XZ_MEMLIMIT_ERROR; | 2456 return XZ_MEMLIMIT_ERROR; |
2457 | 2457 |
2458 s->dict.end = s->dict.size; | 2458 s->dict.end = s->dict.size; |
2459 | 2459 |
2460 if (DEC_IS_DYNALLOC(s->dict.mode)) { | 2460 if (DEC_IS_DYNALLOC(s->dict.mode)) { |
2461 if (s->dict.allocated < s->dict.size) { | 2461 if (s->dict.allocated < s->dict.size) { |
2462 free(s->dict.buf); | 2462 free(s->dict.buf); |
2463 s->dict.buf = malloc(s->dict.size); | 2463 s->dict.buf = malloc(s->dict.size); |
2464 if (s->dict.buf == NULL) { | 2464 if (s->dict.buf == NULL) { |
2465 s->dict.allocated = 0; | 2465 s->dict.allocated = 0; |
2466 return XZ_MEM_ERROR; | 2466 return XZ_MEM_ERROR; |
2467 } | 2467 } |
2468 } | 2468 } |
2469 } | 2469 } |
2470 } | 2470 } |
2471 | 2471 |
2472 s->lzma.len = 0; | 2472 s->lzma.len = 0; |
2473 | 2473 |
2474 s->lzma2.sequence = SEQ_CONTROL; | 2474 s->lzma2.sequence = SEQ_CONTROL; |
2475 s->lzma2.need_dict_reset = 1; | 2475 s->lzma2.need_dict_reset = 1; |
2476 | 2476 |
2477 s->temp.size = 0; | 2477 s->temp.size = 0; |
2478 | 2478 |
2479 return XZ_OK; | 2479 return XZ_OK; |
2480 } | 2480 } |
2481 | 2481 |
2482 /* | 2482 /* |
2483 * .xz Stream decoder | 2483 * .xz Stream decoder |
2484 */ | 2484 */ |
2520 /* Maximum encoded size of a VLI */ | 2520 /* Maximum encoded size of a VLI */ |
2521 #define VLI_BYTES_MAX (sizeof(vli_type) * 8 / 7) | 2521 #define VLI_BYTES_MAX (sizeof(vli_type) * 8 / 7) |
2522 | 2522 |
2523 /* Integrity Check types */ | 2523 /* Integrity Check types */ |
2524 enum xz_check { | 2524 enum xz_check { |
2525 XZ_CHECK_NONE = 0, | 2525 XZ_CHECK_NONE = 0, |
2526 XZ_CHECK_CRC32 = 1, | 2526 XZ_CHECK_CRC32 = 1, |
2527 XZ_CHECK_CRC64 = 4, | 2527 XZ_CHECK_CRC64 = 4, |
2528 XZ_CHECK_SHA256 = 10 | 2528 XZ_CHECK_SHA256 = 10 |
2529 }; | 2529 }; |
2530 | 2530 |
2531 /* Maximum possible Check ID */ | 2531 /* Maximum possible Check ID */ |
2532 #define XZ_CHECK_MAX 15 | 2532 #define XZ_CHECK_MAX 15 |
2533 // END xz_stream.h | 2533 // END xz_stream.h |
2534 | 2534 |
2535 #define IS_CRC64(check_type) ((check_type) == XZ_CHECK_CRC64) | 2535 #define IS_CRC64(check_type) ((check_type) == XZ_CHECK_CRC64) |
2536 | 2536 |
2537 /* Hash used to validate the Index field */ | 2537 /* Hash used to validate the Index field */ |
2538 struct xz_dec_hash { | 2538 struct xz_dec_hash { |
2539 vli_type unpadded; | 2539 vli_type unpadded; |
2540 vli_type uncompressed; | 2540 vli_type uncompressed; |
2541 uint32_t crc32; | 2541 uint32_t crc32; |
2542 }; | 2542 }; |
2543 | 2543 |
2544 struct xz_dec { | 2544 struct xz_dec { |
2545 /* Position in dec_main() */ | 2545 /* Position in dec_main() */ |
2546 enum { | 2546 enum { |
2547 SEQ_STREAM_HEADER, | 2547 SEQ_STREAM_HEADER, |
2548 SEQ_BLOCK_START, | 2548 SEQ_BLOCK_START, |
2549 SEQ_BLOCK_HEADER, | 2549 SEQ_BLOCK_HEADER, |
2550 SEQ_BLOCK_UNCOMPRESS, | 2550 SEQ_BLOCK_UNCOMPRESS, |
2551 SEQ_BLOCK_PADDING, | 2551 SEQ_BLOCK_PADDING, |
2552 SEQ_BLOCK_CHECK, | 2552 SEQ_BLOCK_CHECK, |
2553 SEQ_INDEX, | 2553 SEQ_INDEX, |
2554 SEQ_INDEX_PADDING, | 2554 SEQ_INDEX_PADDING, |
2555 SEQ_INDEX_CRC32, | 2555 SEQ_INDEX_CRC32, |
2556 SEQ_STREAM_FOOTER | 2556 SEQ_STREAM_FOOTER |
2557 } sequence; | 2557 } sequence; |
2558 | 2558 |
2559 /* Position in variable-length integers and Check fields */ | 2559 /* Position in variable-length integers and Check fields */ |
2560 uint32_t pos; | 2560 uint32_t pos; |
2561 | 2561 |
2562 /* Variable-length integer decoded by dec_vli() */ | 2562 /* Variable-length integer decoded by dec_vli() */ |
2563 vli_type vli; | 2563 vli_type vli; |
2564 | 2564 |
2565 /* Saved in_pos and out_pos */ | 2565 /* Saved in_pos and out_pos */ |
2566 size_t in_start; | 2566 size_t in_start; |
2567 size_t out_start; | 2567 size_t out_start; |
2568 | 2568 |
2569 /* CRC32 or CRC64 value in Block or CRC32 value in Index */ | 2569 /* CRC32 or CRC64 value in Block or CRC32 value in Index */ |
2570 uint64_t crc; | 2570 uint64_t crc; |
2571 | 2571 |
2572 /* Type of the integrity check calculated from uncompressed data */ | 2572 /* Type of the integrity check calculated from uncompressed data */ |
2573 enum xz_check check_type; | 2573 enum xz_check check_type; |
2574 | 2574 |
2575 /* Operation mode */ | 2575 /* Operation mode */ |
2576 enum xz_mode mode; | 2576 enum xz_mode mode; |
2577 | 2577 |
2578 /* | 2578 /* |
2579 * True if the next call to xz_dec_run() is allowed to return | 2579 * True if the next call to xz_dec_run() is allowed to return |
2580 * XZ_BUF_ERROR. | 2580 * XZ_BUF_ERROR. |
2581 */ | 2581 */ |
2582 int allow_buf_error; | 2582 int allow_buf_error; |
2583 | 2583 |
2584 /* Information stored in Block Header */ | 2584 /* Information stored in Block Header */ |
2585 struct { | 2585 struct { |
2586 /* | 2586 /* |
2587 * Value stored in the Compressed Size field, or | 2587 * Value stored in the Compressed Size field, or |
2588 * VLI_UNKNOWN if Compressed Size is not present. | 2588 * VLI_UNKNOWN if Compressed Size is not present. |
2589 */ | 2589 */ |
2590 vli_type compressed; | 2590 vli_type compressed; |
2591 | 2591 |
2592 /* | 2592 /* |
2593 * Value stored in the Uncompressed Size field, or | 2593 * Value stored in the Uncompressed Size field, or |
2594 * VLI_UNKNOWN if Uncompressed Size is not present. | 2594 * VLI_UNKNOWN if Uncompressed Size is not present. |
2595 */ | 2595 */ |
2596 vli_type uncompressed; | 2596 vli_type uncompressed; |
2597 | 2597 |
2598 /* Size of the Block Header field */ | 2598 /* Size of the Block Header field */ |
2599 uint32_t size; | 2599 uint32_t size; |
2600 } block_header; | 2600 } block_header; |
2601 | 2601 |
2602 /* Information collected when decoding Blocks */ | 2602 /* Information collected when decoding Blocks */ |
2603 struct { | 2603 struct { |
2604 /* Observed compressed size of the current Block */ | 2604 /* Observed compressed size of the current Block */ |
2605 vli_type compressed; | 2605 vli_type compressed; |
2606 | 2606 |
2607 /* Observed uncompressed size of the current Block */ | 2607 /* Observed uncompressed size of the current Block */ |
2608 vli_type uncompressed; | 2608 vli_type uncompressed; |
2609 | 2609 |
2610 /* Number of Blocks decoded so far */ | 2610 /* Number of Blocks decoded so far */ |
2611 vli_type count; | 2611 vli_type count; |
2612 | 2612 |
2613 /* | 2613 /* |
2614 * Hash calculated from the Block sizes. This is used to | 2614 * Hash calculated from the Block sizes. This is used to |
2615 * validate the Index field. | 2615 * validate the Index field. |
2616 */ | 2616 */ |
2617 struct xz_dec_hash hash; | 2617 struct xz_dec_hash hash; |
2618 } block; | 2618 } block; |
2619 | 2619 |
2620 /* Variables needed when verifying the Index field */ | 2620 /* Variables needed when verifying the Index field */ |
2621 struct { | 2621 struct { |
2622 /* Position in dec_index() */ | 2622 /* Position in dec_index() */ |
2623 enum { | 2623 enum { |
2624 SEQ_INDEX_COUNT, | 2624 SEQ_INDEX_COUNT, |
2625 SEQ_INDEX_UNPADDED, | 2625 SEQ_INDEX_UNPADDED, |
2626 SEQ_INDEX_UNCOMPRESSED | 2626 SEQ_INDEX_UNCOMPRESSED |
2627 } sequence; | 2627 } sequence; |
2628 | 2628 |
2629 /* Size of the Index in bytes */ | 2629 /* Size of the Index in bytes */ |
2630 vli_type size; | 2630 vli_type size; |
2631 | 2631 |
2632 /* Number of Records (matches block.count in valid files) */ | 2632 /* Number of Records (matches block.count in valid files) */ |
2633 vli_type count; | 2633 vli_type count; |
2634 | 2634 |
2635 /* | 2635 /* |
2636 * Hash calculated from the Records (matches block.hash in | 2636 * Hash calculated from the Records (matches block.hash in |
2637 * valid files). | 2637 * valid files). |
2638 */ | 2638 */ |
2639 struct xz_dec_hash hash; | 2639 struct xz_dec_hash hash; |
2640 } index; | 2640 } index; |
2641 | 2641 |
2642 /* | 2642 /* |
2643 * Temporary buffer needed to hold Stream Header, Block Header, | 2643 * Temporary buffer needed to hold Stream Header, Block Header, |
2644 * and Stream Footer. The Block Header is the biggest (1 KiB) | 2644 * and Stream Footer. The Block Header is the biggest (1 KiB) |
2645 * so we reserve space according to that. buf[] has to be aligned | 2645 * so we reserve space according to that. buf[] has to be aligned |
2646 * to a multiple of four bytes; the size_t variables before it | 2646 * to a multiple of four bytes; the size_t variables before it |
2647 * should guarantee this. | 2647 * should guarantee this. |
2648 */ | 2648 */ |
2649 struct { | 2649 struct { |
2650 size_t pos; | 2650 size_t pos; |
2651 size_t size; | 2651 size_t size; |
2652 uint8_t buf[1024]; | 2652 uint8_t buf[1024]; |
2653 } temp; | 2653 } temp; |
2654 | 2654 |
2655 struct xz_dec_lzma2 *lzma2; | 2655 struct xz_dec_lzma2 *lzma2; |
2656 | 2656 |
2657 #ifdef XZ_DEC_BCJ | 2657 #ifdef XZ_DEC_BCJ |
2658 struct xz_dec_bcj *bcj; | 2658 struct xz_dec_bcj *bcj; |
2659 int bcj_active; | 2659 int bcj_active; |
2660 #endif | 2660 #endif |
2661 }; | 2661 }; |
2662 | 2662 |
2663 /* Sizes of the Check field with different Check IDs */ | 2663 /* Sizes of the Check field with different Check IDs */ |
2664 static const uint8_t check_sizes[16] = { | 2664 static const uint8_t check_sizes[16] = { |
2665 0, | 2665 0, |
2666 4, 4, 4, | 2666 4, 4, 4, |
2667 8, 8, 8, | 2667 8, 8, 8, |
2668 16, 16, 16, | 2668 16, 16, 16, |
2669 32, 32, 32, | 2669 32, 32, 32, |
2670 64, 64, 64 | 2670 64, 64, 64 |
2671 }; | 2671 }; |
2672 | 2672 |
2673 /* | 2673 /* |
2674 * Fill s->temp by copying data starting from b->in[b->in_pos]. Caller | 2674 * Fill s->temp by copying data starting from b->in[b->in_pos]. Caller |
2675 * must have set s->temp.pos to indicate how much data we are supposed | 2675 * must have set s->temp.pos to indicate how much data we are supposed |
2676 * to copy into s->temp.buf. Return true once s->temp.pos has reached | 2676 * to copy into s->temp.buf. Return true once s->temp.pos has reached |
2677 * s->temp.size. | 2677 * s->temp.size. |
2678 */ | 2678 */ |
2679 static int fill_temp(struct xz_dec *s, struct xz_buf *b) | 2679 static int fill_temp(struct xz_dec *s, struct xz_buf *b) |
2680 { | 2680 { |
2681 size_t copy_size = min_t(size_t, | 2681 size_t copy_size = min_t(size_t, |
2682 b->in_size - b->in_pos, s->temp.size - s->temp.pos); | 2682 b->in_size - b->in_pos, s->temp.size - s->temp.pos); |
2683 | 2683 |
2684 memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size); | 2684 memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size); |
2685 b->in_pos += copy_size; | 2685 b->in_pos += copy_size; |
2686 s->temp.pos += copy_size; | 2686 s->temp.pos += copy_size; |
2687 | 2687 |
2688 if (s->temp.pos == s->temp.size) { | 2688 if (s->temp.pos == s->temp.size) { |
2689 s->temp.pos = 0; | 2689 s->temp.pos = 0; |
2690 return 1; | 2690 return 1; |
2691 } | 2691 } |
2692 | 2692 |
2693 return 0; | 2693 return 0; |
2694 } | 2694 } |
2695 | 2695 |
2696 /* Decode a variable-length integer (little-endian base-128 encoding) */ | 2696 /* Decode a variable-length integer (little-endian base-128 encoding) */ |
2697 static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in, | 2697 static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in, |
2698 size_t *in_pos, size_t in_size) | 2698 size_t *in_pos, size_t in_size) |
2699 { | 2699 { |
2700 uint8_t byte; | 2700 uint8_t byte; |
2701 | 2701 |
2702 if (s->pos == 0) | 2702 if (s->pos == 0) |
2703 s->vli = 0; | 2703 s->vli = 0; |
2704 | 2704 |
2705 while (*in_pos < in_size) { | 2705 while (*in_pos < in_size) { |
2706 byte = in[*in_pos]; | 2706 byte = in[*in_pos]; |
2707 ++*in_pos; | 2707 ++*in_pos; |
2708 | 2708 |
2709 s->vli |= (vli_type)(byte & 0x7F) << s->pos; | 2709 s->vli |= (vli_type)(byte & 0x7F) << s->pos; |
2710 | 2710 |
2711 if ((byte & 0x80) == 0) { | 2711 if ((byte & 0x80) == 0) { |
2712 /* Don't allow non-minimal encodings. */ | 2712 /* Don't allow non-minimal encodings. */ |
2713 if (byte == 0 && s->pos != 0) | 2713 if (byte == 0 && s->pos != 0) |
2714 return XZ_DATA_ERROR; | 2714 return XZ_DATA_ERROR; |
2715 | 2715 |
2716 s->pos = 0; | 2716 s->pos = 0; |
2717 return XZ_STREAM_END; | 2717 return XZ_STREAM_END; |
2718 } | 2718 } |
2719 | 2719 |
2720 s->pos += 7; | 2720 s->pos += 7; |
2721 if (s->pos == 7 * VLI_BYTES_MAX) | 2721 if (s->pos == 7 * VLI_BYTES_MAX) |
2722 return XZ_DATA_ERROR; | 2722 return XZ_DATA_ERROR; |
2723 } | 2723 } |
2724 | 2724 |
2725 return XZ_OK; | 2725 return XZ_OK; |
2726 } | 2726 } |
2727 | 2727 |
2728 /* | 2728 /* |
2729 * Decode the Compressed Data field from a Block. Update and validate | 2729 * Decode the Compressed Data field from a Block. Update and validate |
2730 * the observed compressed and uncompressed sizes of the Block so that | 2730 * the observed compressed and uncompressed sizes of the Block so that |
2737 * the sizes possibly stored in the Block Header. Update the hash and | 2737 * the sizes possibly stored in the Block Header. Update the hash and |
2738 * Block count, which are later used to validate the Index field. | 2738 * Block count, which are later used to validate the Index field. |
2739 */ | 2739 */ |
2740 static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b) | 2740 static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b) |
2741 { | 2741 { |
2742 enum xz_ret ret; | 2742 enum xz_ret ret; |
2743 | 2743 |
2744 s->in_start = b->in_pos; | 2744 s->in_start = b->in_pos; |
2745 s->out_start = b->out_pos; | 2745 s->out_start = b->out_pos; |
2746 | 2746 |
2747 #ifdef XZ_DEC_BCJ | 2747 #ifdef XZ_DEC_BCJ |
2748 if (s->bcj_active) | 2748 if (s->bcj_active) |
2749 ret = xz_dec_bcj_run(s->bcj, s->lzma2, b); | 2749 ret = xz_dec_bcj_run(s->bcj, s->lzma2, b); |
2750 else | 2750 else |
2751 #endif | 2751 #endif |
2752 ret = xz_dec_lzma2_run(s->lzma2, b); | 2752 ret = xz_dec_lzma2_run(s->lzma2, b); |
2753 | 2753 |
2754 s->block.compressed += b->in_pos - s->in_start; | 2754 s->block.compressed += b->in_pos - s->in_start; |
2755 s->block.uncompressed += b->out_pos - s->out_start; | 2755 s->block.uncompressed += b->out_pos - s->out_start; |
2756 | 2756 |
2757 /* | 2757 /* |
2758 * There is no need to separately check for VLI_UNKNOWN, since | 2758 * There is no need to separately check for VLI_UNKNOWN, since |
2759 * the observed sizes are always smaller than VLI_UNKNOWN. | 2759 * the observed sizes are always smaller than VLI_UNKNOWN. |
2760 */ | 2760 */ |
2761 if (s->block.compressed > s->block_header.compressed | 2761 if (s->block.compressed > s->block_header.compressed |
2762 || s->block.uncompressed | 2762 || s->block.uncompressed |
2763 > s->block_header.uncompressed) | 2763 > s->block_header.uncompressed) |
2764 return XZ_DATA_ERROR; | 2764 return XZ_DATA_ERROR; |
2765 | 2765 |
2766 if (s->check_type == XZ_CHECK_CRC32) | 2766 if (s->check_type == XZ_CHECK_CRC32) |
2767 s->crc = xz_crc32(b->out + s->out_start, | 2767 s->crc = xz_crc32(b->out + s->out_start, |
2768 b->out_pos - s->out_start, s->crc); | 2768 b->out_pos - s->out_start, s->crc); |
2769 else if (s->check_type == XZ_CHECK_CRC64) | 2769 else if (s->check_type == XZ_CHECK_CRC64) |
2770 s->crc = xz_crc64(b->out + s->out_start, | 2770 s->crc = xz_crc64(b->out + s->out_start, |
2771 b->out_pos - s->out_start, s->crc); | 2771 b->out_pos - s->out_start, s->crc); |
2772 | 2772 |
2773 if (ret == XZ_STREAM_END) { | 2773 if (ret == XZ_STREAM_END) { |
2774 if (s->block_header.compressed != VLI_UNKNOWN | 2774 if (s->block_header.compressed != VLI_UNKNOWN |
2775 && s->block_header.compressed | 2775 && s->block_header.compressed |
2776 != s->block.compressed) | 2776 != s->block.compressed) |
2777 return XZ_DATA_ERROR; | 2777 return XZ_DATA_ERROR; |
2778 | 2778 |
2779 if (s->block_header.uncompressed != VLI_UNKNOWN | 2779 if (s->block_header.uncompressed != VLI_UNKNOWN |
2780 && s->block_header.uncompressed | 2780 && s->block_header.uncompressed |
2781 != s->block.uncompressed) | 2781 != s->block.uncompressed) |
2782 return XZ_DATA_ERROR; | 2782 return XZ_DATA_ERROR; |
2783 | 2783 |
2784 s->block.hash.unpadded += s->block_header.size | 2784 s->block.hash.unpadded += s->block_header.size |
2785 + s->block.compressed; | 2785 + s->block.compressed; |
2786 | 2786 |
2787 s->block.hash.unpadded += check_sizes[s->check_type]; | 2787 s->block.hash.unpadded += check_sizes[s->check_type]; |
2788 | 2788 |
2789 s->block.hash.uncompressed += s->block.uncompressed; | 2789 s->block.hash.uncompressed += s->block.uncompressed; |
2790 s->block.hash.crc32 = xz_crc32( | 2790 s->block.hash.crc32 = xz_crc32( |
2791 (const uint8_t *)&s->block.hash, | 2791 (const uint8_t *)&s->block.hash, |
2792 sizeof(s->block.hash), s->block.hash.crc32); | 2792 sizeof(s->block.hash), s->block.hash.crc32); |
2793 | 2793 |
2794 ++s->block.count; | 2794 ++s->block.count; |
2795 } | 2795 } |
2796 | 2796 |
2797 return ret; | 2797 return ret; |
2798 } | 2798 } |
2799 | 2799 |
2800 /* Update the Index size and the CRC32 value. */ | 2800 /* Update the Index size and the CRC32 value. */ |
2801 static void index_update(struct xz_dec *s, const struct xz_buf *b) | 2801 static void index_update(struct xz_dec *s, const struct xz_buf *b) |
2802 { | 2802 { |
2803 size_t in_used = b->in_pos - s->in_start; | 2803 size_t in_used = b->in_pos - s->in_start; |
2804 s->index.size += in_used; | 2804 s->index.size += in_used; |
2805 s->crc = xz_crc32(b->in + s->in_start, in_used, s->crc); | 2805 s->crc = xz_crc32(b->in + s->in_start, in_used, s->crc); |
2806 } | 2806 } |
2807 | 2807 |
2808 /* | 2808 /* |
2809 * Decode the Number of Records, Unpadded Size, and Uncompressed Size | 2809 * Decode the Number of Records, Unpadded Size, and Uncompressed Size |
2810 * fields from the Index field. That is, Index Padding and CRC32 are not | 2810 * fields from the Index field. That is, Index Padding and CRC32 are not |
2813 * This can return XZ_OK (more input needed), XZ_STREAM_END (everything | 2813 * This can return XZ_OK (more input needed), XZ_STREAM_END (everything |
2814 * successfully decoded), or XZ_DATA_ERROR (input is corrupt). | 2814 * successfully decoded), or XZ_DATA_ERROR (input is corrupt). |
2815 */ | 2815 */ |
2816 static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b) | 2816 static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b) |
2817 { | 2817 { |
2818 enum xz_ret ret; | 2818 enum xz_ret ret; |
2819 | 2819 |
2820 do { | 2820 do { |
2821 ret = dec_vli(s, b->in, &b->in_pos, b->in_size); | 2821 ret = dec_vli(s, b->in, &b->in_pos, b->in_size); |
2822 if (ret != XZ_STREAM_END) { | 2822 if (ret != XZ_STREAM_END) { |
2823 index_update(s, b); | 2823 index_update(s, b); |
2824 return ret; | 2824 return ret; |
2825 } | 2825 } |
2826 | 2826 |
2827 switch (s->index.sequence) { | 2827 switch (s->index.sequence) { |
2828 case SEQ_INDEX_COUNT: | 2828 case SEQ_INDEX_COUNT: |
2829 s->index.count = s->vli; | 2829 s->index.count = s->vli; |
2830 | 2830 |
2831 /* | 2831 /* |
2832 * Validate that the Number of Records field | 2832 * Validate that the Number of Records field |
2833 * indicates the same number of Records as | 2833 * indicates the same number of Records as |
2834 * there were Blocks in the Stream. | 2834 * there were Blocks in the Stream. |
2835 */ | 2835 */ |
2836 if (s->index.count != s->block.count) | 2836 if (s->index.count != s->block.count) |
2837 return XZ_DATA_ERROR; | 2837 return XZ_DATA_ERROR; |
2838 | 2838 |
2839 s->index.sequence = SEQ_INDEX_UNPADDED; | 2839 s->index.sequence = SEQ_INDEX_UNPADDED; |
2840 break; | 2840 break; |
2841 | 2841 |
2842 case SEQ_INDEX_UNPADDED: | 2842 case SEQ_INDEX_UNPADDED: |
2843 s->index.hash.unpadded += s->vli; | 2843 s->index.hash.unpadded += s->vli; |
2844 s->index.sequence = SEQ_INDEX_UNCOMPRESSED; | 2844 s->index.sequence = SEQ_INDEX_UNCOMPRESSED; |
2845 break; | 2845 break; |
2846 | 2846 |
2847 case SEQ_INDEX_UNCOMPRESSED: | 2847 case SEQ_INDEX_UNCOMPRESSED: |
2848 s->index.hash.uncompressed += s->vli; | 2848 s->index.hash.uncompressed += s->vli; |
2849 s->index.hash.crc32 = xz_crc32( | 2849 s->index.hash.crc32 = xz_crc32( |
2850 (const uint8_t *)&s->index.hash, | 2850 (const uint8_t *)&s->index.hash, |
2851 sizeof(s->index.hash), | 2851 sizeof(s->index.hash), |
2852 s->index.hash.crc32); | 2852 s->index.hash.crc32); |
2853 --s->index.count; | 2853 --s->index.count; |
2854 s->index.sequence = SEQ_INDEX_UNPADDED; | 2854 s->index.sequence = SEQ_INDEX_UNPADDED; |
2855 break; | 2855 break; |
2856 } | 2856 } |
2857 } while (s->index.count > 0); | 2857 } while (s->index.count > 0); |
2858 | 2858 |
2859 return XZ_STREAM_END; | 2859 return XZ_STREAM_END; |
2860 } | 2860 } |
2861 | 2861 |
2862 /* | 2862 /* |
2863 * Validate that the next four or eight input bytes match the value | 2863 * Validate that the next four or eight input bytes match the value |
2864 * of s->crc. s->pos must be zero when starting to validate the first byte. | 2864 * of s->crc. s->pos must be zero when starting to validate the first byte. |
2865 * The "bits" argument allows using the same code for both CRC32 and CRC64. | 2865 * The "bits" argument allows using the same code for both CRC32 and CRC64. |
2866 */ | 2866 */ |
2867 static enum xz_ret crc_validate(struct xz_dec *s, struct xz_buf *b, | 2867 static enum xz_ret crc_validate(struct xz_dec *s, struct xz_buf *b, |
2868 uint32_t bits) | 2868 uint32_t bits) |
2869 { | 2869 { |
2870 do { | 2870 do { |
2871 if (b->in_pos == b->in_size) | 2871 if (b->in_pos == b->in_size) |
2872 return XZ_OK; | 2872 return XZ_OK; |
2873 | 2873 |
2874 if (((s->crc >> s->pos) & 0xFF) != b->in[b->in_pos++]) | 2874 if (((s->crc >> s->pos) & 0xFF) != b->in[b->in_pos++]) |
2875 return XZ_DATA_ERROR; | 2875 return XZ_DATA_ERROR; |
2876 | 2876 |
2877 s->pos += 8; | 2877 s->pos += 8; |
2878 | 2878 |
2879 } while (s->pos < bits); | 2879 } while (s->pos < bits); |
2880 | 2880 |
2881 s->crc = 0; | 2881 s->crc = 0; |
2882 s->pos = 0; | 2882 s->pos = 0; |
2883 | 2883 |
2884 return XZ_STREAM_END; | 2884 return XZ_STREAM_END; |
2885 } | 2885 } |
2886 | 2886 |
2887 /* | 2887 /* |
2888 * Skip over the Check field when the Check ID is not supported. | 2888 * Skip over the Check field when the Check ID is not supported. |
2889 * Returns true once the whole Check field has been skipped over. | 2889 * Returns true once the whole Check field has been skipped over. |
2890 */ | 2890 */ |
2891 static int check_skip(struct xz_dec *s, struct xz_buf *b) | 2891 static int check_skip(struct xz_dec *s, struct xz_buf *b) |
2892 { | 2892 { |
2893 while (s->pos < check_sizes[s->check_type]) { | 2893 while (s->pos < check_sizes[s->check_type]) { |
2894 if (b->in_pos == b->in_size) return 0; | 2894 if (b->in_pos == b->in_size) return 0; |
2895 | 2895 |
2896 ++b->in_pos; | 2896 ++b->in_pos; |
2897 ++s->pos; | 2897 ++s->pos; |
2898 } | 2898 } |
2899 | 2899 |
2900 s->pos = 0; | 2900 s->pos = 0; |
2901 | 2901 |
2902 return 1; | 2902 return 1; |
2903 } | 2903 } |
2904 | 2904 |
2905 /* Decode the Stream Header field (the first 12 bytes of the .xz Stream). */ | 2905 /* Decode the Stream Header field (the first 12 bytes of the .xz Stream). */ |
2906 static enum xz_ret dec_stream_header(struct xz_dec *s) | 2906 static enum xz_ret dec_stream_header(struct xz_dec *s) |
2907 { | 2907 { |
2908 if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE)) | 2908 if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE)) |
2909 return XZ_FORMAT_ERROR; | 2909 return XZ_FORMAT_ERROR; |
2910 | 2910 |
2911 if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0) | 2911 if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0) |
2912 != get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2)) | 2912 != get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2)) |
2913 return XZ_DATA_ERROR; | 2913 return XZ_DATA_ERROR; |
2914 | 2914 |
2915 if (s->temp.buf[HEADER_MAGIC_SIZE] != 0) | 2915 if (s->temp.buf[HEADER_MAGIC_SIZE] != 0) |
2916 return XZ_OPTIONS_ERROR; | 2916 return XZ_OPTIONS_ERROR; |
2917 | 2917 |
2918 /* | 2918 /* |
2919 * Of integrity checks, we support none (Check ID = 0), | 2919 * Of integrity checks, we support none (Check ID = 0), |
2920 * CRC32 (Check ID = 1), and optionally CRC64 (Check ID = 4). | 2920 * CRC32 (Check ID = 1), and optionally CRC64 (Check ID = 4). |
2921 * However, if XZ_DEC_ANY_CHECK is defined, we will accept other | 2921 * However, if XZ_DEC_ANY_CHECK is defined, we will accept other |
2922 * check types too, but then the check won't be verified and | 2922 * check types too, but then the check won't be verified and |
2923 * a warning (XZ_UNSUPPORTED_CHECK) will be given. | 2923 * a warning (XZ_UNSUPPORTED_CHECK) will be given. |
2924 */ | 2924 */ |
2925 s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1]; | 2925 s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1]; |
2926 | 2926 |
2927 if (s->check_type > XZ_CHECK_MAX) | 2927 if (s->check_type > XZ_CHECK_MAX) |
2928 return XZ_OPTIONS_ERROR; | 2928 return XZ_OPTIONS_ERROR; |
2929 | 2929 |
2930 if (s->check_type > XZ_CHECK_CRC32 && !IS_CRC64(s->check_type)) | 2930 if (s->check_type > XZ_CHECK_CRC32 && !IS_CRC64(s->check_type)) |
2931 return XZ_UNSUPPORTED_CHECK; | 2931 return XZ_UNSUPPORTED_CHECK; |
2932 | 2932 |
2933 return XZ_OK; | 2933 return XZ_OK; |
2934 } | 2934 } |
2935 | 2935 |
2936 /* Decode the Stream Footer field (the last 12 bytes of the .xz Stream) */ | 2936 /* Decode the Stream Footer field (the last 12 bytes of the .xz Stream) */ |
2937 static enum xz_ret dec_stream_footer(struct xz_dec *s) | 2937 static enum xz_ret dec_stream_footer(struct xz_dec *s) |
2938 { | 2938 { |
2939 if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE)) | 2939 if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE)) |
2940 return XZ_DATA_ERROR; | 2940 return XZ_DATA_ERROR; |
2941 | 2941 |
2942 if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf)) | 2942 if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf)) |
2943 return XZ_DATA_ERROR; | 2943 return XZ_DATA_ERROR; |
2944 | 2944 |
2945 /* | 2945 /* |
2946 * Validate Backward Size. Note that we never added the size of the | 2946 * Validate Backward Size. Note that we never added the size of the |
2947 * Index CRC32 field to s->index.size, thus we use s->index.size / 4 | 2947 * Index CRC32 field to s->index.size, thus we use s->index.size / 4 |
2948 * instead of s->index.size / 4 - 1. | 2948 * instead of s->index.size / 4 - 1. |
2949 */ | 2949 */ |
2950 if ((s->index.size >> 2) != get_le32(s->temp.buf + 4)) | 2950 if ((s->index.size >> 2) != get_le32(s->temp.buf + 4)) |
2951 return XZ_DATA_ERROR; | 2951 return XZ_DATA_ERROR; |
2952 | 2952 |
2953 if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type) | 2953 if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type) |
2954 return XZ_DATA_ERROR; | 2954 return XZ_DATA_ERROR; |
2955 | 2955 |
2956 /* | 2956 /* |
2957 * Use XZ_STREAM_END instead of XZ_OK to be more convenient | 2957 * Use XZ_STREAM_END instead of XZ_OK to be more convenient |
2958 * for the caller. | 2958 * for the caller. |
2959 */ | 2959 */ |
2960 return XZ_STREAM_END; | 2960 return XZ_STREAM_END; |
2961 } | 2961 } |
2962 | 2962 |
2963 /* Decode the Block Header and initialize the filter chain. */ | 2963 /* Decode the Block Header and initialize the filter chain. */ |
2964 static enum xz_ret dec_block_header(struct xz_dec *s) | 2964 static enum xz_ret dec_block_header(struct xz_dec *s) |
2965 { | 2965 { |
2966 enum xz_ret ret; | 2966 enum xz_ret ret; |
2967 | 2967 |
2968 /* | 2968 /* |
2969 * Validate the CRC32. We know that the temp buffer is at least | 2969 * Validate the CRC32. We know that the temp buffer is at least |
2970 * eight bytes so this is safe. | 2970 * eight bytes so this is safe. |
2971 */ | 2971 */ |
2972 s->temp.size -= 4; | 2972 s->temp.size -= 4; |
2973 if (xz_crc32(s->temp.buf, s->temp.size, 0) | 2973 if (xz_crc32(s->temp.buf, s->temp.size, 0) |
2974 != get_le32(s->temp.buf + s->temp.size)) | 2974 != get_le32(s->temp.buf + s->temp.size)) |
2975 return XZ_DATA_ERROR; | 2975 return XZ_DATA_ERROR; |
2976 | 2976 |
2977 s->temp.pos = 2; | 2977 s->temp.pos = 2; |
2978 | 2978 |
2979 /* | 2979 /* |
2980 * Catch unsupported Block Flags. We support only one or two filters | 2980 * Catch unsupported Block Flags. We support only one or two filters |
2981 * in the chain, so we catch that with the same test. | 2981 * in the chain, so we catch that with the same test. |
2982 */ | 2982 */ |
2983 #ifdef XZ_DEC_BCJ | 2983 #ifdef XZ_DEC_BCJ |
2984 if (s->temp.buf[1] & 0x3E) | 2984 if (s->temp.buf[1] & 0x3E) |
2985 #else | 2985 #else |
2986 if (s->temp.buf[1] & 0x3F) | 2986 if (s->temp.buf[1] & 0x3F) |
2987 #endif | 2987 #endif |
2988 return XZ_OPTIONS_ERROR; | 2988 return XZ_OPTIONS_ERROR; |
2989 | 2989 |
2990 /* Compressed Size */ | 2990 /* Compressed Size */ |
2991 if (s->temp.buf[1] & 0x40) { | 2991 if (s->temp.buf[1] & 0x40) { |
2992 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size) | 2992 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size) |
2993 != XZ_STREAM_END) | 2993 != XZ_STREAM_END) |
2994 return XZ_DATA_ERROR; | 2994 return XZ_DATA_ERROR; |
2995 | 2995 |
2996 s->block_header.compressed = s->vli; | 2996 s->block_header.compressed = s->vli; |
2997 } else { | 2997 } else { |
2998 s->block_header.compressed = VLI_UNKNOWN; | 2998 s->block_header.compressed = VLI_UNKNOWN; |
2999 } | 2999 } |
3000 | 3000 |
3001 /* Uncompressed Size */ | 3001 /* Uncompressed Size */ |
3002 if (s->temp.buf[1] & 0x80) { | 3002 if (s->temp.buf[1] & 0x80) { |
3003 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size) | 3003 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size) |
3004 != XZ_STREAM_END) | 3004 != XZ_STREAM_END) |
3005 return XZ_DATA_ERROR; | 3005 return XZ_DATA_ERROR; |
3006 | 3006 |
3007 s->block_header.uncompressed = s->vli; | 3007 s->block_header.uncompressed = s->vli; |
3008 } else { | 3008 } else { |
3009 s->block_header.uncompressed = VLI_UNKNOWN; | 3009 s->block_header.uncompressed = VLI_UNKNOWN; |
3010 } | 3010 } |
3011 | 3011 |
3012 #ifdef XZ_DEC_BCJ | 3012 #ifdef XZ_DEC_BCJ |
3013 /* If there are two filters, the first one must be a BCJ filter. */ | 3013 /* If there are two filters, the first one must be a BCJ filter. */ |
3014 s->bcj_active = s->temp.buf[1] & 0x01; | 3014 s->bcj_active = s->temp.buf[1] & 0x01; |
3015 if (s->bcj_active) { | 3015 if (s->bcj_active) { |
3016 if (s->temp.size - s->temp.pos < 2) | 3016 if (s->temp.size - s->temp.pos < 2) |
3017 return XZ_OPTIONS_ERROR; | 3017 return XZ_OPTIONS_ERROR; |
3018 | 3018 |
3019 ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]); | 3019 ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]); |
3020 if (ret != XZ_OK) | 3020 if (ret != XZ_OK) |
3021 return ret; | 3021 return ret; |
3022 | 3022 |
3023 /* | 3023 /* |
3024 * We don't support custom start offset, | 3024 * We don't support custom start offset, |
3025 * so Size of Properties must be zero. | 3025 * so Size of Properties must be zero. |
3026 */ | 3026 */ |
3027 if (s->temp.buf[s->temp.pos++] != 0x00) | 3027 if (s->temp.buf[s->temp.pos++] != 0x00) |
3028 return XZ_OPTIONS_ERROR; | 3028 return XZ_OPTIONS_ERROR; |
3029 } | 3029 } |
3030 #endif | 3030 #endif |
3031 | 3031 |
3032 /* Valid Filter Flags always take at least two bytes. */ | 3032 /* Valid Filter Flags always take at least two bytes. */ |
3033 if (s->temp.size - s->temp.pos < 2) | 3033 if (s->temp.size - s->temp.pos < 2) |
3034 return XZ_DATA_ERROR; | 3034 return XZ_DATA_ERROR; |
3035 | 3035 |
3036 /* Filter ID = LZMA2 */ | 3036 /* Filter ID = LZMA2 */ |
3037 if (s->temp.buf[s->temp.pos++] != 0x21) | 3037 if (s->temp.buf[s->temp.pos++] != 0x21) |
3038 return XZ_OPTIONS_ERROR; | 3038 return XZ_OPTIONS_ERROR; |
3039 | 3039 |
3040 /* Size of Properties = 1-byte Filter Properties */ | 3040 /* Size of Properties = 1-byte Filter Properties */ |
3041 if (s->temp.buf[s->temp.pos++] != 0x01) | 3041 if (s->temp.buf[s->temp.pos++] != 0x01) |
3042 return XZ_OPTIONS_ERROR; | 3042 return XZ_OPTIONS_ERROR; |
3043 | 3043 |
3044 /* Filter Properties contains LZMA2 dictionary size. */ | 3044 /* Filter Properties contains LZMA2 dictionary size. */ |
3045 if (s->temp.size - s->temp.pos < 1) | 3045 if (s->temp.size - s->temp.pos < 1) |
3046 return XZ_DATA_ERROR; | 3046 return XZ_DATA_ERROR; |
3047 | 3047 |
3048 ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]); | 3048 ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]); |
3049 if (ret != XZ_OK) | 3049 if (ret != XZ_OK) |
3050 return ret; | 3050 return ret; |
3051 | 3051 |
3052 /* The rest must be Header Padding. */ | 3052 /* The rest must be Header Padding. */ |
3053 while (s->temp.pos < s->temp.size) | 3053 while (s->temp.pos < s->temp.size) |
3054 if (s->temp.buf[s->temp.pos++] != 0x00) | 3054 if (s->temp.buf[s->temp.pos++] != 0x00) |
3055 return XZ_OPTIONS_ERROR; | 3055 return XZ_OPTIONS_ERROR; |
3056 | 3056 |
3057 s->temp.pos = 0; | 3057 s->temp.pos = 0; |
3058 s->block.compressed = 0; | 3058 s->block.compressed = 0; |
3059 s->block.uncompressed = 0; | 3059 s->block.uncompressed = 0; |
3060 | 3060 |
3061 return XZ_OK; | 3061 return XZ_OK; |
3062 } | 3062 } |
3063 | 3063 |
3064 static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b) | 3064 static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b) |
3065 { | 3065 { |
3066 enum xz_ret ret; | 3066 enum xz_ret ret; |
3067 | 3067 |
3068 /* | 3068 /* |
3069 * Store the start position for the case when we are in the middle | 3069 * Store the start position for the case when we are in the middle |
3070 * of the Index field. | 3070 * of the Index field. |
3071 */ | 3071 */ |
3072 s->in_start = b->in_pos; | 3072 s->in_start = b->in_pos; |
3073 | 3073 |
3074 for (;;) { | 3074 for (;;) { |
3075 switch (s->sequence) { | 3075 switch (s->sequence) { |
3076 case SEQ_STREAM_HEADER: | 3076 case SEQ_STREAM_HEADER: |
3077 /* | 3077 /* |
3078 * Stream Header is copied to s->temp, and then | 3078 * Stream Header is copied to s->temp, and then |
3079 * decoded from there. This way if the caller | 3079 * decoded from there. This way if the caller |
3080 * gives us only little input at a time, we can | 3080 * gives us only little input at a time, we can |
3081 * still keep the Stream Header decoding code | 3081 * still keep the Stream Header decoding code |
3082 * simple. Similar approach is used in many places | 3082 * simple. Similar approach is used in many places |
3083 * in this file. | 3083 * in this file. |
3084 */ | 3084 */ |
3085 if (!fill_temp(s, b)) | 3085 if (!fill_temp(s, b)) |
3086 return XZ_OK; | 3086 return XZ_OK; |
3087 | 3087 |
3088 /* | 3088 /* |
3089 * If dec_stream_header() returns | 3089 * If dec_stream_header() returns |
3090 * XZ_UNSUPPORTED_CHECK, it is still possible | 3090 * XZ_UNSUPPORTED_CHECK, it is still possible |
3091 * to continue decoding if working in multi-call | 3091 * to continue decoding if working in multi-call |
3092 * mode. Thus, update s->sequence before calling | 3092 * mode. Thus, update s->sequence before calling |
3093 * dec_stream_header(). | 3093 * dec_stream_header(). |
3094 */ | 3094 */ |
3095 s->sequence = SEQ_BLOCK_START; | 3095 s->sequence = SEQ_BLOCK_START; |
3096 | 3096 |
3097 ret = dec_stream_header(s); | 3097 ret = dec_stream_header(s); |
3098 if (ret != XZ_OK) | 3098 if (ret != XZ_OK) |
3099 return ret; | 3099 return ret; |
3100 | 3100 |
3101 case SEQ_BLOCK_START: | 3101 case SEQ_BLOCK_START: |
3102 /* We need one byte of input to continue. */ | 3102 /* We need one byte of input to continue. */ |
3103 if (b->in_pos == b->in_size) | 3103 if (b->in_pos == b->in_size) |
3104 return XZ_OK; | 3104 return XZ_OK; |
3105 | 3105 |
3106 /* See if this is the beginning of the Index field. */ | 3106 /* See if this is the beginning of the Index field. */ |
3107 if (b->in[b->in_pos] == 0) { | 3107 if (b->in[b->in_pos] == 0) { |
3108 s->in_start = b->in_pos++; | 3108 s->in_start = b->in_pos++; |
3109 s->sequence = SEQ_INDEX; | 3109 s->sequence = SEQ_INDEX; |
3110 break; | 3110 break; |
3111 } | 3111 } |
3112 | 3112 |
3113 /* | 3113 /* |
3114 * Calculate the size of the Block Header and | 3114 * Calculate the size of the Block Header and |
3115 * prepare to decode it. | 3115 * prepare to decode it. |
3116 */ | 3116 */ |
3117 s->block_header.size | 3117 s->block_header.size |
3118 = ((uint32_t)b->in[b->in_pos] + 1) * 4; | 3118 = ((uint32_t)b->in[b->in_pos] + 1) * 4; |
3119 | 3119 |
3120 s->temp.size = s->block_header.size; | 3120 s->temp.size = s->block_header.size; |
3121 s->temp.pos = 0; | 3121 s->temp.pos = 0; |
3122 s->sequence = SEQ_BLOCK_HEADER; | 3122 s->sequence = SEQ_BLOCK_HEADER; |
3123 | 3123 |
3124 case SEQ_BLOCK_HEADER: | 3124 case SEQ_BLOCK_HEADER: |
3125 if (!fill_temp(s, b)) | 3125 if (!fill_temp(s, b)) |
3126 return XZ_OK; | 3126 return XZ_OK; |
3127 | 3127 |
3128 ret = dec_block_header(s); | 3128 ret = dec_block_header(s); |
3129 if (ret != XZ_OK) | 3129 if (ret != XZ_OK) |
3130 return ret; | 3130 return ret; |
3131 | 3131 |
3132 s->sequence = SEQ_BLOCK_UNCOMPRESS; | 3132 s->sequence = SEQ_BLOCK_UNCOMPRESS; |
3133 | 3133 |
3134 case SEQ_BLOCK_UNCOMPRESS: | 3134 case SEQ_BLOCK_UNCOMPRESS: |
3135 ret = dec_block(s, b); | 3135 ret = dec_block(s, b); |
3136 if (ret != XZ_STREAM_END) | 3136 if (ret != XZ_STREAM_END) |
3137 return ret; | 3137 return ret; |
3138 | 3138 |
3139 s->sequence = SEQ_BLOCK_PADDING; | 3139 s->sequence = SEQ_BLOCK_PADDING; |
3140 | 3140 |
3141 case SEQ_BLOCK_PADDING: | 3141 case SEQ_BLOCK_PADDING: |
3142 /* | 3142 /* |
3143 * Size of Compressed Data + Block Padding | 3143 * Size of Compressed Data + Block Padding |
3144 * must be a multiple of four. We don't need | 3144 * must be a multiple of four. We don't need |
3145 * s->block.compressed for anything else | 3145 * s->block.compressed for anything else |
3146 * anymore, so we use it here to test the size | 3146 * anymore, so we use it here to test the size |
3147 * of the Block Padding field. | 3147 * of the Block Padding field. |
3148 */ | 3148 */ |
3149 while (s->block.compressed & 3) { | 3149 while (s->block.compressed & 3) { |
3150 if (b->in_pos == b->in_size) | 3150 if (b->in_pos == b->in_size) |
3151 return XZ_OK; | 3151 return XZ_OK; |
3152 | 3152 |
3153 if (b->in[b->in_pos++] != 0) | 3153 if (b->in[b->in_pos++] != 0) |
3154 return XZ_DATA_ERROR; | 3154 return XZ_DATA_ERROR; |
3155 | 3155 |
3156 ++s->block.compressed; | 3156 ++s->block.compressed; |
3157 } | 3157 } |
3158 | 3158 |
3159 s->sequence = SEQ_BLOCK_CHECK; | 3159 s->sequence = SEQ_BLOCK_CHECK; |
3160 | 3160 |
3161 case SEQ_BLOCK_CHECK: | 3161 case SEQ_BLOCK_CHECK: |
3162 if (s->check_type == XZ_CHECK_CRC32) { | 3162 if (s->check_type == XZ_CHECK_CRC32) { |
3163 ret = crc_validate(s, b, 32); | 3163 ret = crc_validate(s, b, 32); |
3164 if (ret != XZ_STREAM_END) | 3164 if (ret != XZ_STREAM_END) |
3165 return ret; | 3165 return ret; |
3166 } | 3166 } |
3167 else if (IS_CRC64(s->check_type)) { | 3167 else if (IS_CRC64(s->check_type)) { |
3168 ret = crc_validate(s, b, 64); | 3168 ret = crc_validate(s, b, 64); |
3169 if (ret != XZ_STREAM_END) | 3169 if (ret != XZ_STREAM_END) |
3170 return ret; | 3170 return ret; |
3171 } | 3171 } |
3172 else if (!check_skip(s, b)) { | 3172 else if (!check_skip(s, b)) { |
3173 return XZ_OK; | 3173 return XZ_OK; |
3174 } | 3174 } |
3175 | 3175 |
3176 s->sequence = SEQ_BLOCK_START; | 3176 s->sequence = SEQ_BLOCK_START; |
3177 break; | 3177 break; |
3178 | 3178 |
3179 case SEQ_INDEX: | 3179 case SEQ_INDEX: |
3180 ret = dec_index(s, b); | 3180 ret = dec_index(s, b); |
3181 if (ret != XZ_STREAM_END) | 3181 if (ret != XZ_STREAM_END) |
3182 return ret; | 3182 return ret; |
3183 | 3183 |
3184 s->sequence = SEQ_INDEX_PADDING; | 3184 s->sequence = SEQ_INDEX_PADDING; |
3185 | 3185 |
3186 case SEQ_INDEX_PADDING: | 3186 case SEQ_INDEX_PADDING: |
3187 while ((s->index.size + (b->in_pos - s->in_start)) | 3187 while ((s->index.size + (b->in_pos - s->in_start)) |
3188 & 3) { | 3188 & 3) { |
3189 if (b->in_pos == b->in_size) { | 3189 if (b->in_pos == b->in_size) { |
3190 index_update(s, b); | 3190 index_update(s, b); |
3191 return XZ_OK; | 3191 return XZ_OK; |
3192 } | 3192 } |
3193 | 3193 |
3194 if (b->in[b->in_pos++] != 0) | 3194 if (b->in[b->in_pos++] != 0) |
3195 return XZ_DATA_ERROR; | 3195 return XZ_DATA_ERROR; |
3196 } | 3196 } |
3197 | 3197 |
3198 /* Finish the CRC32 value and Index size. */ | 3198 /* Finish the CRC32 value and Index size. */ |
3199 index_update(s, b); | 3199 index_update(s, b); |
3200 | 3200 |
3201 /* Compare the hashes to validate the Index field. */ | 3201 /* Compare the hashes to validate the Index field. */ |
3202 if (!memeq(&s->block.hash, &s->index.hash, | 3202 if (!memeq(&s->block.hash, &s->index.hash, |
3203 sizeof(s->block.hash))) | 3203 sizeof(s->block.hash))) |
3204 return XZ_DATA_ERROR; | 3204 return XZ_DATA_ERROR; |
3205 | 3205 |
3206 s->sequence = SEQ_INDEX_CRC32; | 3206 s->sequence = SEQ_INDEX_CRC32; |
3207 | 3207 |
3208 case SEQ_INDEX_CRC32: | 3208 case SEQ_INDEX_CRC32: |
3209 ret = crc_validate(s, b, 32); | 3209 ret = crc_validate(s, b, 32); |
3210 if (ret != XZ_STREAM_END) | 3210 if (ret != XZ_STREAM_END) |
3211 return ret; | 3211 return ret; |
3212 | 3212 |
3213 s->temp.size = STREAM_HEADER_SIZE; | 3213 s->temp.size = STREAM_HEADER_SIZE; |
3214 s->sequence = SEQ_STREAM_FOOTER; | 3214 s->sequence = SEQ_STREAM_FOOTER; |
3215 | 3215 |
3216 case SEQ_STREAM_FOOTER: | 3216 case SEQ_STREAM_FOOTER: |
3217 if (!fill_temp(s, b)) | 3217 if (!fill_temp(s, b)) |
3218 return XZ_OK; | 3218 return XZ_OK; |
3219 | 3219 |
3220 return dec_stream_footer(s); | 3220 return dec_stream_footer(s); |
3221 } | 3221 } |
3222 } | 3222 } |
3223 | 3223 |
3224 /* Never reached */ | 3224 /* Never reached */ |
3225 } | 3225 } |
3226 | 3226 |
3227 /* | 3227 /* |
3228 * xz_dec_run() is a wrapper for dec_main() to handle some special cases in | 3228 * xz_dec_run() is a wrapper for dec_main() to handle some special cases in |
3229 * multi-call and single-call decoding. | 3229 * multi-call and single-call decoding. |
3249 * actually succeeds (that's the price to pay of using the output buffer as | 3249 * actually succeeds (that's the price to pay of using the output buffer as |
3250 * the workspace). | 3250 * the workspace). |
3251 */ | 3251 */ |
3252 enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b) | 3252 enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b) |
3253 { | 3253 { |
3254 size_t in_start; | 3254 size_t in_start; |
3255 size_t out_start; | 3255 size_t out_start; |
3256 enum xz_ret ret; | 3256 enum xz_ret ret; |
3257 | 3257 |
3258 if (DEC_IS_SINGLE(s->mode)) | 3258 if (DEC_IS_SINGLE(s->mode)) |
3259 xz_dec_reset(s); | 3259 xz_dec_reset(s); |
3260 | 3260 |
3261 in_start = b->in_pos; | 3261 in_start = b->in_pos; |
3262 out_start = b->out_pos; | 3262 out_start = b->out_pos; |
3263 ret = dec_main(s, b); | 3263 ret = dec_main(s, b); |
3264 | 3264 |
3265 if (DEC_IS_SINGLE(s->mode)) { | 3265 if (DEC_IS_SINGLE(s->mode)) { |
3266 if (ret == XZ_OK) | 3266 if (ret == XZ_OK) |
3267 ret = b->in_pos == b->in_size | 3267 ret = b->in_pos == b->in_size |
3268 ? XZ_DATA_ERROR : XZ_BUF_ERROR; | 3268 ? XZ_DATA_ERROR : XZ_BUF_ERROR; |
3269 | 3269 |
3270 if (ret != XZ_STREAM_END) { | 3270 if (ret != XZ_STREAM_END) { |
3271 b->in_pos = in_start; | 3271 b->in_pos = in_start; |
3272 b->out_pos = out_start; | 3272 b->out_pos = out_start; |
3273 } | 3273 } |
3274 | 3274 |
3275 } else if (ret == XZ_OK && in_start == b->in_pos | 3275 } else if (ret == XZ_OK && in_start == b->in_pos |
3276 && out_start == b->out_pos) { | 3276 && out_start == b->out_pos) { |
3277 if (s->allow_buf_error) | 3277 if (s->allow_buf_error) |
3278 ret = XZ_BUF_ERROR; | 3278 ret = XZ_BUF_ERROR; |
3279 | 3279 |
3280 s->allow_buf_error = 1; | 3280 s->allow_buf_error = 1; |
3281 } else { | 3281 } else { |
3282 s->allow_buf_error = 0; | 3282 s->allow_buf_error = 0; |
3283 } | 3283 } |
3284 | 3284 |
3285 return ret; | 3285 return ret; |
3286 } | 3286 } |
3287 | 3287 |
3288 struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max) | 3288 struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max) |
3289 { | 3289 { |
3290 struct xz_dec *s = malloc(sizeof(*s)); | 3290 struct xz_dec *s = malloc(sizeof(*s)); |
3291 if (s == NULL) | 3291 if (s == NULL) |
3292 return NULL; | 3292 return NULL; |
3293 | 3293 |
3294 s->mode = mode; | 3294 s->mode = mode; |
3295 | 3295 |
3296 #ifdef XZ_DEC_BCJ | 3296 #ifdef XZ_DEC_BCJ |
3297 s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode)); | 3297 s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode)); |
3298 if (s->bcj == NULL) | 3298 if (s->bcj == NULL) |
3299 goto error_bcj; | 3299 goto error_bcj; |
3300 #endif | 3300 #endif |
3301 | 3301 |
3302 s->lzma2 = xz_dec_lzma2_create(mode, dict_max); | 3302 s->lzma2 = xz_dec_lzma2_create(mode, dict_max); |
3303 if (s->lzma2 == NULL) | 3303 if (s->lzma2 == NULL) |
3304 goto error_lzma2; | 3304 goto error_lzma2; |
3305 | 3305 |
3306 xz_dec_reset(s); | 3306 xz_dec_reset(s); |
3307 return s; | 3307 return s; |
3308 | 3308 |
3309 error_lzma2: | 3309 error_lzma2: |
3310 #ifdef XZ_DEC_BCJ | 3310 #ifdef XZ_DEC_BCJ |
3311 free(s->bcj); | 3311 free(s->bcj); |
3312 error_bcj: | 3312 error_bcj: |
3313 #endif | 3313 #endif |
3314 free(s); | 3314 free(s); |
3315 return NULL; | 3315 return NULL; |
3316 } | 3316 } |
3317 | 3317 |
3318 void xz_dec_reset(struct xz_dec *s) | 3318 void xz_dec_reset(struct xz_dec *s) |
3319 { | 3319 { |
3320 s->sequence = SEQ_STREAM_HEADER; | 3320 s->sequence = SEQ_STREAM_HEADER; |
3321 s->allow_buf_error = 0; | 3321 s->allow_buf_error = 0; |
3322 s->pos = 0; | 3322 s->pos = 0; |
3323 s->crc = 0; | 3323 s->crc = 0; |
3324 memset(&s->block, 0, sizeof(s->block)); | 3324 memset(&s->block, 0, sizeof(s->block)); |
3325 memset(&s->index, 0, sizeof(s->index)); | 3325 memset(&s->index, 0, sizeof(s->index)); |
3326 s->temp.pos = 0; | 3326 s->temp.pos = 0; |
3327 s->temp.size = STREAM_HEADER_SIZE; | 3327 s->temp.size = STREAM_HEADER_SIZE; |
3328 } | 3328 } |
3329 | 3329 |
3330 void xz_dec_end(struct xz_dec *s) | 3330 void xz_dec_end(struct xz_dec *s) |
3331 { | 3331 { |
3332 if (s != NULL) { | 3332 if (s != NULL) { |
3333 if (DEC_IS_MULTI((s->lzma2)->dict.mode)) | 3333 if (DEC_IS_MULTI((s->lzma2)->dict.mode)) |
3334 free((s->lzma2)->dict.buf); | 3334 free((s->lzma2)->dict.buf); |
3335 free(s->lzma2); | 3335 free(s->lzma2); |
3336 | 3336 |
3337 #ifdef XZ_DEC_BCJ | 3337 #ifdef XZ_DEC_BCJ |
3338 free(s->bcj); | 3338 free(s->bcj); |
3339 #endif | 3339 #endif |
3340 free(s); | 3340 free(s); |
3341 } | 3341 } |
3342 } | 3342 } |