This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

dom0_xen_decompression.patch

By: a guest on Aug 8th, 2011  |  syntax: Diff  |  size: 96.88 KB  |  views: 74  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. diff --git a/xen/common/Makefile b/xen/common/Makefile
  2. --- a/xen/common/Makefile
  3. +++ b/xen/common/Makefile
  4. @@ -43,7 +43,7 @@
  5.  obj-y += rbtree.o
  6.  obj-y += lzo.o
  7.  
  8. -obj-$(CONFIG_X86) += decompress.o bunzip2.o unlzma.o unlzo.o
  9. +obj-$(CONFIG_X86) += decompress.o bunzip2.o unxz.o unlzma.o unlzo.o
  10.  
  11.  obj-$(perfc)       += perfc.o
  12.  obj-$(crash_debug) += gdbstub.o
  13. diff --git a/xen/common/decompress.c b/xen/common/decompress.c
  14. --- a/xen/common/decompress.c
  15. +++ b/xen/common/decompress.c
  16. @@ -20,6 +20,9 @@
  17.      if ( len >= 3 && !memcmp(inbuf, "\x42\x5a\x68", 3) )
  18.          return bunzip2(inbuf, len, NULL, NULL, outbuf, NULL, error);
  19.  
  20. +    if ( len >= 6 && !memcmp(inbuf, "\3757zXZ", 6) )
  21. +        return unxz(inbuf, len, NULL, NULL, outbuf, NULL, error);
  22. +
  23.      if ( len >= 2 && !memcmp(inbuf, "\135\000", 2) )
  24.          return unlzma(inbuf, len, NULL, NULL, outbuf, NULL, error);
  25.  
  26. diff --git a/xen/common/decompress.h b/xen/common/decompress.h
  27. --- a/xen/common/decompress.h
  28. +++ b/xen/common/decompress.h
  29. @@ -8,6 +8,7 @@
  30.  
  31.  #define STATIC
  32.  #define INIT __init
  33. +#define INITDATA __initdata
  34.  
  35.  static void(*__initdata error)(const char *);
  36.  #define set_error_fn(x) error = x;
  37. diff --git a/xen/common/unxz.c b/xen/common/unxz.c
  38. new file mode 100644
  39. --- /dev/null
  40. +++ b/xen/common/unxz.c
  41. @@ -0,0 +1,306 @@
  42. +/*
  43. + * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd
  44. + *
  45. + * Author: Lasse Collin <lasse.collin@tukaani.org>
  46. + *
  47. + * This file has been put into the public domain.
  48. + * You can do whatever you want with this file.
  49. + */
  50. +
  51. +/*
  52. + * Important notes about in-place decompression
  53. + *
  54. + * At least on x86, the kernel is decompressed in place: the compressed data
  55. + * is placed to the end of the output buffer, and the decompressor overwrites
  56. + * most of the compressed data. There must be enough safety margin to
  57. + * guarantee that the write position is always behind the read position.
  58. + *
  59. + * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below.
  60. + * Note that the margin with XZ is bigger than with Deflate (gzip)!
  61. + *
  62. + * The worst case for in-place decompression is that the beginning of
  63. + * the file is compressed extremely well, and the rest of the file is
  64. + * uncompressible. Thus, we must look for worst-case expansion when the
  65. + * compressor is encoding uncompressible data.
  66. + *
  67. + * The structure of the .xz file in case of a compresed kernel is as follows.
  68. + * Sizes (as bytes) of the fields are in parenthesis.
  69. + *
  70. + *    Stream Header (12)
  71. + *    Block Header:
  72. + *      Block Header (8-12)
  73. + *      Compressed Data (N)
  74. + *      Block Padding (0-3)
  75. + *      CRC32 (4)
  76. + *    Index (8-20)
  77. + *    Stream Footer (12)
  78. + *
  79. + * Normally there is exactly one Block, but let's assume that there are
  80. + * 2-4 Blocks just in case. Because Stream Header and also Block Header
  81. + * of the first Block don't make the decompressor produce any uncompressed
  82. + * data, we can ignore them from our calculations. Block Headers of possible
  83. + * additional Blocks have to be taken into account still. With these
  84. + * assumptions, it is safe to assume that the total header overhead is
  85. + * less than 128 bytes.
  86. + *
  87. + * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ
  88. + * doesn't change the size of the data, it is enough to calculate the
  89. + * safety margin for LZMA2.
  90. + *
  91. + * LZMA2 stores the data in chunks. Each chunk has a header whose size is
  92. + * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that
  93. + * the maximum chunk header size is 8 bytes. After the chunk header, there
  94. + * may be up to 64 KiB of actual payload in the chunk. Often the payload is
  95. + * quite a bit smaller though; to be safe, let's assume that an average
  96. + * chunk has only 32 KiB of payload.
  97. + *
  98. + * The maximum uncompressed size of the payload is 2 MiB. The minimum
  99. + * uncompressed size of the payload is in practice never less than the
  100. + * payload size itself. The LZMA2 format would allow uncompressed size
  101. + * to be less than the payload size, but no sane compressor creates such
  102. + * files. LZMA2 supports storing uncompressible data in uncompressed form,
  103. + * so there's never a need to create payloads whose uncompressed size is
  104. + * smaller than the compressed size.
  105. + *
  106. + * The assumption, that the uncompressed size of the payload is never
  107. + * smaller than the payload itself, is valid only when talking about
  108. + * the payload as a whole. It is possible that the payload has parts where
  109. + * the decompressor consumes more input than it produces output. Calculating
  110. + * the worst case for this would be tricky. Instead of trying to do that,
  111. + * let's simply make sure that the decompressor never overwrites any bytes
  112. + * of the payload which it is currently reading.
  113. + *
  114. + * Now we have enough information to calculate the safety margin. We need
  115. + *   - 128 bytes for the .xz file format headers;
  116. + *   - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header
  117. + *     per chunk, each chunk having average payload size of 32 KiB); and
  118. + *   - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that
  119. + *     the decompressor never overwrites anything from the LZMA2 chunk
  120. + *     payload it is currently reading.
  121. + *
  122. + * We get the following formula:
  123. + *
  124. + *    safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536
  125. + *                  = 128 + (uncompressed_size >> 12) + 65536
  126. + *
  127. + * For comparision, according to arch/x86/boot/compressed/misc.c, the
  128. + * equivalent formula for Deflate is this:
  129. + *
  130. + *    safety_margin = 18 + (uncompressed_size >> 12) + 32768
  131. + *
  132. + * Thus, when updating Deflate-only in-place kernel decompressor to
  133. + * support XZ, the fixed overhead has to be increased from 18+32768 bytes
  134. + * to 128+65536 bytes.
  135. + */
  136. +
  137. +#include "decompress.h"
  138. +
  139. +#define XZ_EXTERN STATIC
  140. +
  141. +/*
  142. + * For boot time use, we enable only the BCJ filter of the current
  143. + * architecture or none if no BCJ filter is available for the architecture.
  144. + */
  145. +#ifdef CONFIG_X86
  146. +#      define XZ_DEC_X86
  147. +#endif
  148. +#ifdef CONFIG_PPC
  149. +#      define XZ_DEC_POWERPC
  150. +#endif
  151. +#ifdef CONFIG_ARM
  152. +#      define XZ_DEC_ARM
  153. +#endif
  154. +#ifdef CONFIG_IA64
  155. +#      define XZ_DEC_IA64
  156. +#endif
  157. +#ifdef CONFIG_SPARC
  158. +#      define XZ_DEC_SPARC
  159. +#endif
  160. +
  161. +/*
  162. + * This will get the basic headers so that memeq() and others
  163. + * can be defined.
  164. + */
  165. +#include "xz/private.h"
  166. +
  167. +/*
  168. + * memeq and memzero are not used much and any remotely sane implementation
  169. + * is fast enough. memcpy/memmove speed matters in multi-call mode, but
  170. + * the kernel image is decompressed in single-call mode, in which only
  171. + * memcpy speed can matter and only if there is a lot of uncompressible data
  172. + * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
  173. + * functions below should just be kept small; it's probably not worth
  174. + * optimizing for speed.
  175. + */
  176. +
  177. +#ifndef memeq
  178. +#define memeq(p1, p2, sz) (memcmp(p1, p2, sz) == 0)
  179. +#endif
  180. +
  181. +#ifndef memzero
  182. +#define memzero(p, sz) memset(p, 0, sz)
  183. +#endif
  184. +
  185. +#include "xz/crc32.c"
  186. +#include "xz/dec_stream.c"
  187. +#include "xz/dec_lzma2.c"
  188. +#include "xz/dec_bcj.c"
  189. +
  190. +/* Size of the input and output buffers in multi-call mode */
  191. +#define XZ_IOBUF_SIZE 4096
  192. +
  193. +/*
  194. + * This function implements the API defined in <linux/decompress/generic.h>.
  195. + *
  196. + * This wrapper will automatically choose single-call or multi-call mode
  197. + * of the native XZ decoder API. The single-call mode can be used only when
  198. + * both input and output buffers are available as a single chunk, i.e. when
  199. + * fill() and flush() won't be used.
  200. + */
  201. +STATIC int INIT unxz(unsigned char *in, unsigned int in_size,
  202. +                    int (*fill)(void *dest, unsigned int size),
  203. +                    int (*flush)(void *src, unsigned int size),
  204. +                    unsigned char *out, unsigned int *in_used,
  205. +                    void (*error_fn)(const char *x))
  206. +{
  207. +       struct xz_buf b;
  208. +       struct xz_dec *s;
  209. +       enum xz_ret ret;
  210. +       bool_t must_free_in = false;
  211. +
  212. +       set_error_fn(error_fn);
  213. +
  214. +       xz_crc32_init();
  215. +
  216. +       if (in_used != NULL)
  217. +               *in_used = 0;
  218. +
  219. +       if (fill == NULL && flush == NULL)
  220. +               s = xz_dec_init(XZ_SINGLE, 0);
  221. +       else
  222. +               s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1);
  223. +
  224. +       if (s == NULL)
  225. +               goto error_alloc_state;
  226. +
  227. +       if (flush == NULL) {
  228. +               b.out = out;
  229. +               b.out_size = (size_t)-1;
  230. +       } else {
  231. +               b.out_size = XZ_IOBUF_SIZE;
  232. +               b.out = malloc(XZ_IOBUF_SIZE);
  233. +               if (b.out == NULL)
  234. +                       goto error_alloc_out;
  235. +       }
  236. +
  237. +       if (in == NULL) {
  238. +               must_free_in = true;
  239. +               in = malloc(XZ_IOBUF_SIZE);
  240. +               if (in == NULL)
  241. +                       goto error_alloc_in;
  242. +       }
  243. +
  244. +       b.in = in;
  245. +       b.in_pos = 0;
  246. +       b.in_size = in_size;
  247. +       b.out_pos = 0;
  248. +
  249. +       if (fill == NULL && flush == NULL) {
  250. +               ret = xz_dec_run(s, &b);
  251. +       } else {
  252. +               do {
  253. +                       if (b.in_pos == b.in_size && fill != NULL) {
  254. +                               if (in_used != NULL)
  255. +                                       *in_used += b.in_pos;
  256. +
  257. +                               b.in_pos = 0;
  258. +
  259. +                               in_size = fill(in, XZ_IOBUF_SIZE);
  260. +                               if (in_size < 0) {
  261. +                                       /*
  262. +                                        * This isn't an optimal error code
  263. +                                        * but it probably isn't worth making
  264. +                                        * a new one either.
  265. +                                        */
  266. +                                       ret = XZ_BUF_ERROR;
  267. +                                       break;
  268. +                               }
  269. +
  270. +                               b.in_size = in_size;
  271. +                       }
  272. +
  273. +                       ret = xz_dec_run(s, &b);
  274. +
  275. +                       if (flush != NULL && (b.out_pos == b.out_size
  276. +                                       || (ret != XZ_OK && b.out_pos > 0))) {
  277. +                               /*
  278. +                                * Setting ret here may hide an error
  279. +                                * returned by xz_dec_run(), but probably
  280. +                                * it's not too bad.
  281. +                                */
  282. +                               if (flush(b.out, b.out_pos) != (int)b.out_pos)
  283. +                                       ret = XZ_BUF_ERROR;
  284. +
  285. +                               b.out_pos = 0;
  286. +                       }
  287. +               } while (ret == XZ_OK);
  288. +
  289. +               if (must_free_in)
  290. +                       free(in);
  291. +
  292. +               if (flush != NULL)
  293. +                       free(b.out);
  294. +       }
  295. +
  296. +       if (in_used != NULL)
  297. +               *in_used += b.in_pos;
  298. +
  299. +       xz_dec_end(s);
  300. +
  301. +       switch (ret) {
  302. +       case XZ_STREAM_END:
  303. +               return 0;
  304. +
  305. +       case XZ_MEM_ERROR:
  306. +               /* This can occur only in multi-call mode. */
  307. +               error("XZ decompressor ran out of memory");
  308. +               break;
  309. +
  310. +       case XZ_FORMAT_ERROR:
  311. +               error("Input is not in the XZ format (wrong magic bytes)");
  312. +               break;
  313. +
  314. +       case XZ_OPTIONS_ERROR:
  315. +               error("Input was encoded with settings that are not "
  316. +                               "supported by this XZ decoder");
  317. +               break;
  318. +
  319. +       case XZ_DATA_ERROR:
  320. +       case XZ_BUF_ERROR:
  321. +               error("XZ-compressed data is corrupt");
  322. +               break;
  323. +
  324. +       default:
  325. +               error("Bug in the XZ decompressor");
  326. +               break;
  327. +       }
  328. +
  329. +       return -1;
  330. +
  331. +error_alloc_in:
  332. +       if (flush != NULL)
  333. +               free(b.out);
  334. +
  335. +error_alloc_out:
  336. +       xz_dec_end(s);
  337. +
  338. +error_alloc_state:
  339. +       error("XZ decompressor ran out of memory");
  340. +       return -1;
  341. +}
  342. +
  343. +/*
  344. + * This macro is used by architecture-specific files to decompress
  345. + * the kernel image.
  346. + */
  347. +#define decompress unxz
  348. diff --git a/xen/common/xz/crc32.c b/xen/common/xz/crc32.c
  349. new file mode 100644
  350. --- /dev/null
  351. +++ b/xen/common/xz/crc32.c
  352. @@ -0,0 +1,51 @@
  353. +/*
  354. + * CRC32 using the polynomial from IEEE-802.3
  355. + *
  356. + * Authors: Lasse Collin <lasse.collin@tukaani.org>
  357. + *          Igor Pavlov <http://7-zip.org/>
  358. + *
  359. + * This file has been put into the public domain.
  360. + * You can do whatever you want with this file.
  361. + */
  362. +
  363. +/*
  364. + * This is not the fastest implementation, but it is pretty compact.
  365. + * The fastest versions of xz_crc32() on modern CPUs without hardware
  366. + * accelerated CRC instruction are 3-5 times as fast as this version,
  367. + * but they are bigger and use more memory for the lookup table.
  368. + */
  369. +
  370. +#include "private.h"
  371. +
  372. +XZ_EXTERN uint32_t INITDATA xz_crc32_table[256];
  373. +
  374. +XZ_EXTERN void INIT xz_crc32_init(void)
  375. +{
  376. +       const uint32_t poly = 0xEDB88320;
  377. +
  378. +       uint32_t i;
  379. +       uint32_t j;
  380. +       uint32_t r;
  381. +
  382. +       for (i = 0; i < 256; ++i) {
  383. +               r = i;
  384. +               for (j = 0; j < 8; ++j)
  385. +                       r = (r >> 1) ^ (poly & ~((r & 1) - 1));
  386. +
  387. +               xz_crc32_table[i] = r;
  388. +       }
  389. +
  390. +       return;
  391. +}
  392. +
  393. +XZ_EXTERN uint32_t INIT xz_crc32(const uint8_t *buf, size_t size, uint32_t crc)
  394. +{
  395. +       crc = ~crc;
  396. +
  397. +       while (size != 0) {
  398. +               crc = xz_crc32_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8);
  399. +               --size;
  400. +       }
  401. +
  402. +       return ~crc;
  403. +}
  404. diff --git a/xen/common/xz/dec_bcj.c b/xen/common/xz/dec_bcj.c
  405. new file mode 100644
  406. --- /dev/null
  407. +++ b/xen/common/xz/dec_bcj.c
  408. @@ -0,0 +1,562 @@
  409. +/*
  410. + * Branch/Call/Jump (BCJ) filter decoders
  411. + *
  412. + * Authors: Lasse Collin <lasse.collin@tukaani.org>
  413. + *          Igor Pavlov <http://7-zip.org/>
  414. + *
  415. + * This file has been put into the public domain.
  416. + * You can do whatever you want with this file.
  417. + */
  418. +
  419. +#include "private.h"
  420. +
  421. +/*
  422. + * The rest of the file is inside this ifdef. It makes things a little more
  423. + * convenient when building without support for any BCJ filters.
  424. + */
  425. +#ifdef XZ_DEC_BCJ
  426. +
  427. +struct xz_dec_bcj {
  428. +       /* Type of the BCJ filter being used */
  429. +       enum {
  430. +               BCJ_X86 = 4,        /* x86 or x86-64 */
  431. +               BCJ_POWERPC = 5,    /* Big endian only */
  432. +               BCJ_IA64 = 6,       /* Big or little endian */
  433. +               BCJ_ARM = 7,        /* Little endian only */
  434. +               BCJ_ARMTHUMB = 8,   /* Little endian only */
  435. +               BCJ_SPARC = 9       /* Big or little endian */
  436. +       } type;
  437. +
  438. +       /*
  439. +        * Return value of the next filter in the chain. We need to preserve
  440. +        * this information across calls, because we must not call the next
  441. +        * filter anymore once it has returned XZ_STREAM_END.
  442. +        */
  443. +       enum xz_ret ret;
  444. +
  445. +       /* True if we are operating in single-call mode. */
  446. +       bool_t single_call;
  447. +
  448. +       /*
  449. +        * Absolute position relative to the beginning of the uncompressed
  450. +        * data (in a single .xz Block). We care only about the lowest 32
  451. +        * bits so this doesn't need to be uint64_t even with big files.
  452. +        */
  453. +       uint32_t pos;
  454. +
  455. +       /* x86 filter state */
  456. +       uint32_t x86_prev_mask;
  457. +
  458. +       /* Temporary space to hold the variables from struct xz_buf */
  459. +       uint8_t *out;
  460. +       size_t out_pos;
  461. +       size_t out_size;
  462. +
  463. +       struct {
  464. +               /* Amount of already filtered data in the beginning of buf */
  465. +               size_t filtered;
  466. +
  467. +               /* Total amount of data currently stored in buf  */
  468. +               size_t size;
  469. +
  470. +               /*
  471. +                * Buffer to hold a mix of filtered and unfiltered data. This
  472. +                * needs to be big enough to hold Alignment + 2 * Look-ahead:
  473. +                *
  474. +                * Type         Alignment   Look-ahead
  475. +                * x86              1           4
  476. +                * PowerPC          4           0
  477. +                * IA-64           16           0
  478. +                * ARM              4           0
  479. +                * ARM-Thumb        2           2
  480. +                * SPARC            4           0
  481. +                */
  482. +               uint8_t buf[16];
  483. +       } temp;
  484. +};
  485. +
  486. +#ifdef XZ_DEC_X86
  487. +/*
  488. + * This is used to test the most significant byte of a memory address
  489. + * in an x86 instruction.
  490. + */
  491. +static inline int INIT bcj_x86_test_msbyte(uint8_t b)
  492. +{
  493. +       return b == 0x00 || b == 0xFF;
  494. +}
  495. +
  496. +static size_t INIT bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
  497. +{
  498. +       static /*const*/ bool_t INITDATA mask_to_allowed_status[8]
  499. +               = { true, true, true, false, true, false, false, false };
  500. +
  501. +       static /*const*/ uint8_t INITDATA mask_to_bit_num[8]
  502. +               = { 0, 1, 2, 2, 3, 3, 3, 3 };
  503. +
  504. +       size_t i;
  505. +       size_t prev_pos = (size_t)-1;
  506. +       uint32_t prev_mask = s->x86_prev_mask;
  507. +       uint32_t src;
  508. +       uint32_t dest;
  509. +       uint32_t j;
  510. +       uint8_t b;
  511. +
  512. +       if (size <= 4)
  513. +               return 0;
  514. +
  515. +       size -= 4;
  516. +       for (i = 0; i < size; ++i) {
  517. +               if ((buf[i] & 0xFE) != 0xE8)
  518. +                       continue;
  519. +
  520. +               prev_pos = i - prev_pos;
  521. +               if (prev_pos > 3) {
  522. +                       prev_mask = 0;
  523. +               } else {
  524. +                       prev_mask = (prev_mask << (prev_pos - 1)) & 7;
  525. +                       if (prev_mask != 0) {
  526. +                               b = buf[i + 4 - mask_to_bit_num[prev_mask]];
  527. +                               if (!mask_to_allowed_status[prev_mask]
  528. +                                               || bcj_x86_test_msbyte(b)) {
  529. +                                       prev_pos = i;
  530. +                                       prev_mask = (prev_mask << 1) | 1;
  531. +                                       continue;
  532. +                               }
  533. +                       }
  534. +               }
  535. +
  536. +               prev_pos = i;
  537. +
  538. +               if (bcj_x86_test_msbyte(buf[i + 4])) {
  539. +                       src = get_unaligned_le32(buf + i + 1);
  540. +                       while (true) {
  541. +                               dest = src - (s->pos + (uint32_t)i + 5);
  542. +                               if (prev_mask == 0)
  543. +                                       break;
  544. +
  545. +                               j = mask_to_bit_num[prev_mask] * 8;
  546. +                               b = (uint8_t)(dest >> (24 - j));
  547. +                               if (!bcj_x86_test_msbyte(b))
  548. +                                       break;
  549. +
  550. +                               src = dest ^ (((uint32_t)1 << (32 - j)) - 1);
  551. +                       }
  552. +
  553. +                       dest &= 0x01FFFFFF;
  554. +                       dest |= (uint32_t)0 - (dest & 0x01000000);
  555. +                       put_unaligned_le32(dest, buf + i + 1);
  556. +                       i += 4;
  557. +               } else {
  558. +                       prev_mask = (prev_mask << 1) | 1;
  559. +               }
  560. +       }
  561. +
  562. +       prev_pos = i - prev_pos;
  563. +       s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1);
  564. +       return i;
  565. +}
  566. +#endif
  567. +
  568. +#ifdef XZ_DEC_POWERPC
  569. +static size_t INIT bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
  570. +{
  571. +       size_t i;
  572. +       uint32_t instr;
  573. +
  574. +       for (i = 0; i + 4 <= size; i += 4) {
  575. +               instr = get_unaligned_be32(buf + i);
  576. +               if ((instr & 0xFC000003) == 0x48000001) {
  577. +                       instr &= 0x03FFFFFC;
  578. +                       instr -= s->pos + (uint32_t)i;
  579. +                       instr &= 0x03FFFFFC;
  580. +                       instr |= 0x48000001;
  581. +                       put_unaligned_be32(instr, buf + i);
  582. +               }
  583. +       }
  584. +
  585. +       return i;
  586. +}
  587. +#endif
  588. +
  589. +#ifdef XZ_DEC_IA64
  590. +static size_t INIT bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
  591. +{
  592. +       static const uint8_t branch_table[32] = {
  593. +               0, 0, 0, 0, 0, 0, 0, 0,
  594. +               0, 0, 0, 0, 0, 0, 0, 0,
  595. +               4, 4, 6, 6, 0, 0, 7, 7,
  596. +               4, 4, 0, 0, 4, 4, 0, 0
  597. +       };
  598. +
  599. +       /*
  600. +        * The local variables take a little bit stack space, but it's less
  601. +        * than what LZMA2 decoder takes, so it doesn't make sense to reduce
  602. +        * stack usage here without doing that for the LZMA2 decoder too.
  603. +        */
  604. +
  605. +       /* Loop counters */
  606. +       size_t i;
  607. +       size_t j;
  608. +
  609. +       /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */
  610. +       uint32_t slot;
  611. +
  612. +       /* Bitwise offset of the instruction indicated by slot */
  613. +       uint32_t bit_pos;
  614. +
  615. +       /* bit_pos split into byte and bit parts */
  616. +       uint32_t byte_pos;
  617. +       uint32_t bit_res;
  618. +
  619. +       /* Address part of an instruction */
  620. +       uint32_t addr;
  621. +
  622. +       /* Mask used to detect which instructions to convert */
  623. +       uint32_t mask;
  624. +
  625. +       /* 41-bit instruction stored somewhere in the lowest 48 bits */
  626. +       uint64_t instr;
  627. +
  628. +       /* Instruction normalized with bit_res for easier manipulation */
  629. +       uint64_t norm;
  630. +
  631. +       for (i = 0; i + 16 <= size; i += 16) {
  632. +               mask = branch_table[buf[i] & 0x1F];
  633. +               for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) {
  634. +                       if (((mask >> slot) & 1) == 0)
  635. +                               continue;
  636. +
  637. +                       byte_pos = bit_pos >> 3;
  638. +                       bit_res = bit_pos & 7;
  639. +                       instr = 0;
  640. +                       for (j = 0; j < 6; ++j)
  641. +                               instr |= (uint64_t)(buf[i + j + byte_pos])
  642. +                                               << (8 * j);
  643. +
  644. +                       norm = instr >> bit_res;
  645. +
  646. +                       if (((norm >> 37) & 0x0F) == 0x05
  647. +                                       && ((norm >> 9) & 0x07) == 0) {
  648. +                               addr = (norm >> 13) & 0x0FFFFF;
  649. +                               addr |= ((uint32_t)(norm >> 36) & 1) << 20;
  650. +                               addr <<= 4;
  651. +                               addr -= s->pos + (uint32_t)i;
  652. +                               addr >>= 4;
  653. +
  654. +                               norm &= ~((uint64_t)0x8FFFFF << 13);
  655. +                               norm |= (uint64_t)(addr & 0x0FFFFF) << 13;
  656. +                               norm |= (uint64_t)(addr & 0x100000)
  657. +                                               << (36 - 20);
  658. +
  659. +                               instr &= (1 << bit_res) - 1;
  660. +                               instr |= norm << bit_res;
  661. +
  662. +                               for (j = 0; j < 6; j++)
  663. +                                       buf[i + j + byte_pos]
  664. +                                               = (uint8_t)(instr >> (8 * j));
  665. +                       }
  666. +               }
  667. +       }
  668. +
  669. +       return i;
  670. +}
  671. +#endif
  672. +
  673. +#ifdef XZ_DEC_ARM
  674. +static size_t INIT bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
  675. +{
  676. +       size_t i;
  677. +       uint32_t addr;
  678. +
  679. +       for (i = 0; i + 4 <= size; i += 4) {
  680. +               if (buf[i + 3] == 0xEB) {
  681. +                       addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8)
  682. +                                       | ((uint32_t)buf[i + 2] << 16);
  683. +                       addr <<= 2;
  684. +                       addr -= s->pos + (uint32_t)i + 8;
  685. +                       addr >>= 2;
  686. +                       buf[i] = (uint8_t)addr;
  687. +                       buf[i + 1] = (uint8_t)(addr >> 8);
  688. +                       buf[i + 2] = (uint8_t)(addr >> 16);
  689. +               }
  690. +       }
  691. +
  692. +       return i;
  693. +}
  694. +#endif
  695. +
  696. +#ifdef XZ_DEC_ARMTHUMB
  697. +static size_t INIT bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
  698. +{
  699. +       size_t i;
  700. +       uint32_t addr;
  701. +
  702. +       for (i = 0; i + 4 <= size; i += 2) {
  703. +               if ((buf[i + 1] & 0xF8) == 0xF0
  704. +                               && (buf[i + 3] & 0xF8) == 0xF8) {
  705. +                       addr = (((uint32_t)buf[i + 1] & 0x07) << 19)
  706. +                                       | ((uint32_t)buf[i] << 11)
  707. +                                       | (((uint32_t)buf[i + 3] & 0x07) << 8)
  708. +                                       | (uint32_t)buf[i + 2];
  709. +                       addr <<= 1;
  710. +                       addr -= s->pos + (uint32_t)i + 4;
  711. +                       addr >>= 1;
  712. +                       buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07));
  713. +                       buf[i] = (uint8_t)(addr >> 11);
  714. +                       buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07));
  715. +                       buf[i + 2] = (uint8_t)addr;
  716. +                       i += 2;
  717. +               }
  718. +       }
  719. +
  720. +       return i;
  721. +}
  722. +#endif
  723. +
  724. +#ifdef XZ_DEC_SPARC
  725. +static size_t INIT bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
  726. +{
  727. +       size_t i;
  728. +       uint32_t instr;
  729. +
  730. +       for (i = 0; i + 4 <= size; i += 4) {
  731. +               instr = get_unaligned_be32(buf + i);
  732. +               if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) {
  733. +                       instr <<= 2;
  734. +                       instr -= s->pos + (uint32_t)i;
  735. +                       instr >>= 2;
  736. +                       instr = ((uint32_t)0x40000000 - (instr & 0x400000))
  737. +                                       | 0x40000000 | (instr & 0x3FFFFF);
  738. +                       put_unaligned_be32(instr, buf + i);
  739. +               }
  740. +       }
  741. +
  742. +       return i;
  743. +}
  744. +#endif
  745. +
  746. +/*
  747. + * Apply the selected BCJ filter. Update *pos and s->pos to match the amount
  748. + * of data that got filtered.
  749. + *
  750. + * NOTE: This is implemented as a switch statement to avoid using function
  751. + * pointers, which could be problematic in the kernel boot code, which must
  752. + * avoid pointers to static data (at least on x86).
  753. + */
  754. +static void INIT bcj_apply(struct xz_dec_bcj *s,
  755. +                          uint8_t *buf, size_t *pos, size_t size)
  756. +{
  757. +       size_t filtered;
  758. +
  759. +       buf += *pos;
  760. +       size -= *pos;
  761. +
  762. +       switch (s->type) {
  763. +#ifdef XZ_DEC_X86
  764. +       case BCJ_X86:
  765. +               filtered = bcj_x86(s, buf, size);
  766. +               break;
  767. +#endif
  768. +#ifdef XZ_DEC_POWERPC
  769. +       case BCJ_POWERPC:
  770. +               filtered = bcj_powerpc(s, buf, size);
  771. +               break;
  772. +#endif
  773. +#ifdef XZ_DEC_IA64
  774. +       case BCJ_IA64:
  775. +               filtered = bcj_ia64(s, buf, size);
  776. +               break;
  777. +#endif
  778. +#ifdef XZ_DEC_ARM
  779. +       case BCJ_ARM:
  780. +               filtered = bcj_arm(s, buf, size);
  781. +               break;
  782. +#endif
  783. +#ifdef XZ_DEC_ARMTHUMB
  784. +       case BCJ_ARMTHUMB:
  785. +               filtered = bcj_armthumb(s, buf, size);
  786. +               break;
  787. +#endif
  788. +#ifdef XZ_DEC_SPARC
  789. +       case BCJ_SPARC:
  790. +               filtered = bcj_sparc(s, buf, size);
  791. +               break;
  792. +#endif
  793. +       default:
  794. +               /* Never reached but silence compiler warnings. */
  795. +               filtered = 0;
  796. +               break;
  797. +       }
  798. +
  799. +       *pos += filtered;
  800. +       s->pos += filtered;
  801. +}
  802. +
  803. +/*
  804. + * Flush pending filtered data from temp to the output buffer.
  805. + * Move the remaining mixture of possibly filtered and unfiltered
  806. + * data to the beginning of temp.
  807. + */
  808. +static void INIT bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b)
  809. +{
  810. +       size_t copy_size;
  811. +
  812. +       copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos);
  813. +       memcpy(b->out + b->out_pos, s->temp.buf, copy_size);
  814. +       b->out_pos += copy_size;
  815. +
  816. +       s->temp.filtered -= copy_size;
  817. +       s->temp.size -= copy_size;
  818. +       memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size);
  819. +}
  820. +
  821. +/*
  822. + * The BCJ filter functions are primitive in sense that they process the
  823. + * data in chunks of 1-16 bytes. To hide this issue, this function does
  824. + * some buffering.
  825. + */
  826. +XZ_EXTERN enum xz_ret INIT xz_dec_bcj_run(struct xz_dec_bcj *s,
  827. +                                         struct xz_dec_lzma2 *lzma2,
  828. +                                         struct xz_buf *b)
  829. +{
  830. +       size_t out_start;
  831. +
  832. +       /*
  833. +        * Flush pending already filtered data to the output buffer. Return
  834. +        * immediatelly if we couldn't flush everything, or if the next
  835. +        * filter in the chain had already returned XZ_STREAM_END.
  836. +        */
  837. +       if (s->temp.filtered > 0) {
  838. +               bcj_flush(s, b);
  839. +               if (s->temp.filtered > 0)
  840. +                       return XZ_OK;
  841. +
  842. +               if (s->ret == XZ_STREAM_END)
  843. +                       return XZ_STREAM_END;
  844. +       }
  845. +
  846. +       /*
  847. +        * If we have more output space than what is currently pending in
  848. +        * temp, copy the unfiltered data from temp to the output buffer
  849. +        * and try to fill the output buffer by decoding more data from the
  850. +        * next filter in the chain. Apply the BCJ filter on the new data
  851. +        * in the output buffer. If everything cannot be filtered, copy it
  852. +        * to temp and rewind the output buffer position accordingly.
  853. +        */
  854. +       if (s->temp.size < b->out_size - b->out_pos) {
  855. +               out_start = b->out_pos;
  856. +               memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size);
  857. +               b->out_pos += s->temp.size;
  858. +
  859. +               s->ret = xz_dec_lzma2_run(lzma2, b);
  860. +               if (s->ret != XZ_STREAM_END
  861. +                               && (s->ret != XZ_OK || s->single_call))
  862. +                       return s->ret;
  863. +
  864. +               bcj_apply(s, b->out, &out_start, b->out_pos);
  865. +
  866. +               /*
  867. +                * As an exception, if the next filter returned XZ_STREAM_END,
  868. +                * we can do that too, since the last few bytes that remain
  869. +                * unfiltered are meant to remain unfiltered.
  870. +                */
  871. +               if (s->ret == XZ_STREAM_END)
  872. +                       return XZ_STREAM_END;
  873. +
  874. +               s->temp.size = b->out_pos - out_start;
  875. +               b->out_pos -= s->temp.size;
  876. +               memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size);
  877. +       }
  878. +
  879. +       /*
  880. +        * If we have unfiltered data in temp, try to fill by decoding more
  881. +        * data from the next filter. Apply the BCJ filter on temp. Then we
  882. +        * hopefully can fill the actual output buffer by copying filtered
  883. +        * data from temp. A mix of filtered and unfiltered data may be left
  884. +        * in temp; it will be taken care on the next call to this function.
  885. +        */
  886. +       if (s->temp.size > 0) {
  887. +               /* Make b->out{,_pos,_size} temporarily point to s->temp. */
  888. +               s->out = b->out;
  889. +               s->out_pos = b->out_pos;
  890. +               s->out_size = b->out_size;
  891. +               b->out = s->temp.buf;
  892. +               b->out_pos = s->temp.size;
  893. +               b->out_size = sizeof(s->temp.buf);
  894. +
  895. +               s->ret = xz_dec_lzma2_run(lzma2, b);
  896. +
  897. +               s->temp.size = b->out_pos;
  898. +               b->out = s->out;
  899. +               b->out_pos = s->out_pos;
  900. +               b->out_size = s->out_size;
  901. +
  902. +               if (s->ret != XZ_OK && s->ret != XZ_STREAM_END)
  903. +                       return s->ret;
  904. +
  905. +               bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size);
  906. +
  907. +               /*
  908. +                * If the next filter returned XZ_STREAM_END, we mark that
  909. +                * everything is filtered, since the last unfiltered bytes
  910. +                * of the stream are meant to be left as is.
  911. +                */
  912. +               if (s->ret == XZ_STREAM_END)
  913. +                       s->temp.filtered = s->temp.size;
  914. +
  915. +               bcj_flush(s, b);
  916. +               if (s->temp.filtered > 0)
  917. +                       return XZ_OK;
  918. +       }
  919. +
  920. +       return s->ret;
  921. +}
  922. +
  923. +XZ_EXTERN struct xz_dec_bcj *INIT xz_dec_bcj_create(bool_t single_call)
  924. +{
  925. +       struct xz_dec_bcj *s = malloc(sizeof(*s));
  926. +       if (s != NULL)
  927. +               s->single_call = single_call;
  928. +
  929. +       return s;
  930. +}
  931. +
  932. +XZ_EXTERN enum xz_ret INIT xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id)
  933. +{
  934. +       switch (id) {
  935. +#ifdef XZ_DEC_X86
  936. +       case BCJ_X86:
  937. +#endif
  938. +#ifdef XZ_DEC_POWERPC
  939. +       case BCJ_POWERPC:
  940. +#endif
  941. +#ifdef XZ_DEC_IA64
  942. +       case BCJ_IA64:
  943. +#endif
  944. +#ifdef XZ_DEC_ARM
  945. +       case BCJ_ARM:
  946. +#endif
  947. +#ifdef XZ_DEC_ARMTHUMB
  948. +       case BCJ_ARMTHUMB:
  949. +#endif
  950. +#ifdef XZ_DEC_SPARC
  951. +       case BCJ_SPARC:
  952. +#endif
  953. +               break;
  954. +
  955. +       default:
  956. +               /* Unsupported Filter ID */
  957. +               return XZ_OPTIONS_ERROR;
  958. +       }
  959. +
  960. +       s->type = id;
  961. +       s->ret = XZ_OK;
  962. +       s->pos = 0;
  963. +       s->x86_prev_mask = 0;
  964. +       s->temp.filtered = 0;
  965. +       s->temp.size = 0;
  966. +
  967. +       return XZ_OK;
  968. +}
  969. +
  970. +#endif
  971. diff --git a/xen/common/xz/dec_lzma2.c b/xen/common/xz/dec_lzma2.c
  972. new file mode 100644
  973. --- /dev/null
  974. +++ b/xen/common/xz/dec_lzma2.c
  975. @@ -0,0 +1,1171 @@
  976. +/*
  977. + * LZMA2 decoder
  978. + *
  979. + * Authors: Lasse Collin <lasse.collin@tukaani.org>
  980. + *          Igor Pavlov <http://7-zip.org/>
  981. + *
  982. + * This file has been put into the public domain.
  983. + * You can do whatever you want with this file.
  984. + */
  985. +
  986. +#include "private.h"
  987. +#include "lzma2.h"
  988. +
  989. +/*
  990. + * Range decoder initialization eats the first five bytes of each LZMA chunk.
  991. + */
  992. +#define RC_INIT_BYTES 5
  993. +
  994. +/*
  995. + * Minimum number of usable input buffer to safely decode one LZMA symbol.
  996. + * The worst case is that we decode 22 bits using probabilities and 26
  997. + * direct bits. This may decode at maximum of 20 bytes of input. However,
  998. + * lzma_main() does an extra normalization before returning, thus we
  999. + * need to put 21 here.
  1000. + */
  1001. +#define LZMA_IN_REQUIRED 21
  1002. +
  1003. +/*
  1004. + * Dictionary (history buffer)
  1005. + *
  1006. + * These are always true:
  1007. + *    start <= pos <= full <= end
  1008. + *    pos <= limit <= end
  1009. + *
  1010. + * In multi-call mode, also these are true:
  1011. + *    end == size
  1012. + *    size <= size_max
  1013. + *    allocated <= size
  1014. + *
  1015. + * Most of these variables are size_t to support single-call mode,
  1016. + * in which the dictionary variables address the actual output
  1017. + * buffer directly.
  1018. + */
  1019. +struct dictionary {
  1020. +       /* Beginning of the history buffer */
  1021. +       uint8_t *buf;
  1022. +
  1023. +       /* Old position in buf (before decoding more data) */
  1024. +       size_t start;
  1025. +
  1026. +       /* Position in buf */
  1027. +       size_t pos;
  1028. +
  1029. +       /*
  1030. +        * How full dictionary is. This is used to detect corrupt input that
  1031. +        * would read beyond the beginning of the uncompressed stream.
  1032. +        */
  1033. +       size_t full;
  1034. +
  1035. +       /* Write limit; we don't write to buf[limit] or later bytes. */
  1036. +       size_t limit;
  1037. +
  1038. +       /*
  1039. +        * End of the dictionary buffer. In multi-call mode, this is
  1040. +        * the same as the dictionary size. In single-call mode, this
  1041. +        * indicates the size of the output buffer.
  1042. +        */
  1043. +       size_t end;
  1044. +
  1045. +       /*
  1046. +        * Size of the dictionary as specified in Block Header. This is used
  1047. +        * together with "full" to detect corrupt input that would make us
  1048. +        * read beyond the beginning of the uncompressed stream.
  1049. +        */
  1050. +       uint32_t size;
  1051. +
  1052. +       /*
  1053. +        * Maximum allowed dictionary size in multi-call mode.
  1054. +        * This is ignored in single-call mode.
  1055. +        */
  1056. +       uint32_t size_max;
  1057. +
  1058. +       /*
  1059. +        * Amount of memory currently allocated for the dictionary.
  1060. +        * This is used only with XZ_DYNALLOC. (With XZ_PREALLOC,
  1061. +        * size_max is always the same as the allocated size.)
  1062. +        */
  1063. +       uint32_t allocated;
  1064. +
  1065. +       /* Operation mode */
  1066. +       enum xz_mode mode;
  1067. +};
  1068. +
  1069. +/* Range decoder */
  1070. +struct rc_dec {
  1071. +       uint32_t range;
  1072. +       uint32_t code;
  1073. +
  1074. +       /*
  1075. +        * Number of initializing bytes remaining to be read
  1076. +        * by rc_read_init().
  1077. +        */
  1078. +       uint32_t init_bytes_left;
  1079. +
  1080. +       /*
  1081. +        * Buffer from which we read our input. It can be either
  1082. +        * temp.buf or the caller-provided input buffer.
  1083. +        */
  1084. +       const uint8_t *in;
  1085. +       size_t in_pos;
  1086. +       size_t in_limit;
  1087. +};
  1088. +
  1089. +/* Probabilities for a length decoder. */
  1090. +struct lzma_len_dec {
  1091. +       /* Probability of match length being at least 10 */
  1092. +       uint16_t choice;
  1093. +
  1094. +       /* Probability of match length being at least 18 */
  1095. +       uint16_t choice2;
  1096. +
  1097. +       /* Probabilities for match lengths 2-9 */
  1098. +       uint16_t low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
  1099. +
  1100. +       /* Probabilities for match lengths 10-17 */
  1101. +       uint16_t mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
  1102. +
  1103. +       /* Probabilities for match lengths 18-273 */
  1104. +       uint16_t high[LEN_HIGH_SYMBOLS];
  1105. +};
  1106. +
  1107. +struct lzma_dec {
  1108. +       /* Distances of latest four matches */
  1109. +       uint32_t rep0;
  1110. +       uint32_t rep1;
  1111. +       uint32_t rep2;
  1112. +       uint32_t rep3;
  1113. +
  1114. +       /* Types of the most recently seen LZMA symbols */
  1115. +       enum lzma_state state;
  1116. +
  1117. +       /*
  1118. +        * Length of a match. This is updated so that dict_repeat can
  1119. +        * be called again to finish repeating the whole match.
  1120. +        */
  1121. +       uint32_t len;
  1122. +
  1123. +       /*
  1124. +        * LZMA properties or related bit masks (number of literal
  1125. +        * context bits, a mask dervied from the number of literal
  1126. +        * position bits, and a mask dervied from the number
  1127. +        * position bits)
  1128. +        */
  1129. +       uint32_t lc;
  1130. +       uint32_t literal_pos_mask; /* (1 << lp) - 1 */
  1131. +       uint32_t pos_mask;         /* (1 << pb) - 1 */
  1132. +
  1133. +       /* If 1, it's a match. Otherwise it's a single 8-bit literal. */
  1134. +       uint16_t is_match[STATES][POS_STATES_MAX];
  1135. +
  1136. +       /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
  1137. +       uint16_t is_rep[STATES];
  1138. +
  1139. +       /*
  1140. +        * If 0, distance of a repeated match is rep0.
  1141. +        * Otherwise check is_rep1.
  1142. +        */
  1143. +       uint16_t is_rep0[STATES];
  1144. +
  1145. +       /*
  1146. +        * If 0, distance of a repeated match is rep1.
  1147. +        * Otherwise check is_rep2.
  1148. +        */
  1149. +       uint16_t is_rep1[STATES];
  1150. +
  1151. +       /* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */
  1152. +       uint16_t is_rep2[STATES];
  1153. +
  1154. +       /*
  1155. +        * If 1, the repeated match has length of one byte. Otherwise
  1156. +        * the length is decoded from rep_len_decoder.
  1157. +        */
  1158. +       uint16_t is_rep0_long[STATES][POS_STATES_MAX];
  1159. +
  1160. +       /*
  1161. +        * Probability tree for the highest two bits of the match
  1162. +        * distance. There is a separate probability tree for match
  1163. +        * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
  1164. +        */
  1165. +       uint16_t dist_slot[DIST_STATES][DIST_SLOTS];
  1166. +
  1167. +       /*
  1168. +        * Probility trees for additional bits for match distance
  1169. +        * when the distance is in the range [4, 127].
  1170. +        */
  1171. +       uint16_t dist_special[FULL_DISTANCES - DIST_MODEL_END];
  1172. +
  1173. +       /*
  1174. +        * Probability tree for the lowest four bits of a match
  1175. +        * distance that is equal to or greater than 128.
  1176. +        */
  1177. +       uint16_t dist_align[ALIGN_SIZE];
  1178. +
  1179. +       /* Length of a normal match */
  1180. +       struct lzma_len_dec match_len_dec;
  1181. +
  1182. +       /* Length of a repeated match */
  1183. +       struct lzma_len_dec rep_len_dec;
  1184. +
  1185. +       /* Probabilities of literals */
  1186. +       uint16_t literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
  1187. +};
  1188. +
  1189. +struct lzma2_dec {
  1190. +       /* Position in xz_dec_lzma2_run(). */
  1191. +       enum lzma2_seq {
  1192. +               SEQ_CONTROL,
  1193. +               SEQ_UNCOMPRESSED_1,
  1194. +               SEQ_UNCOMPRESSED_2,
  1195. +               SEQ_COMPRESSED_0,
  1196. +               SEQ_COMPRESSED_1,
  1197. +               SEQ_PROPERTIES,
  1198. +               SEQ_LZMA_PREPARE,
  1199. +               SEQ_LZMA_RUN,
  1200. +               SEQ_COPY
  1201. +       } sequence;
  1202. +
  1203. +       /* Next position after decoding the compressed size of the chunk. */
  1204. +       enum lzma2_seq next_sequence;
  1205. +
  1206. +       /* Uncompressed size of LZMA chunk (2 MiB at maximum) */
  1207. +       uint32_t uncompressed;
  1208. +
  1209. +       /*
  1210. +        * Compressed size of LZMA chunk or compressed/uncompressed
  1211. +        * size of uncompressed chunk (64 KiB at maximum)
  1212. +        */
  1213. +       uint32_t compressed;
  1214. +
  1215. +       /*
  1216. +        * True if dictionary reset is needed. This is false before
  1217. +        * the first chunk (LZMA or uncompressed).
  1218. +        */
  1219. +       bool_t need_dict_reset;
  1220. +
  1221. +       /*
  1222. +        * True if new LZMA properties are needed. This is false
  1223. +        * before the first LZMA chunk.
  1224. +        */
  1225. +       bool_t need_props;
  1226. +};
  1227. +
  1228. +struct xz_dec_lzma2 {
  1229. +       /*
  1230. +        * The order below is important on x86 to reduce code size and
  1231. +        * it shouldn't hurt on other platforms. Everything up to and
  1232. +        * including lzma.pos_mask are in the first 128 bytes on x86-32,
  1233. +        * which allows using smaller instructions to access those
  1234. +        * variables. On x86-64, fewer variables fit into the first 128
  1235. +        * bytes, but this is still the best order without sacrificing
  1236. +        * the readability by splitting the structures.
  1237. +        */
  1238. +       struct rc_dec rc;
  1239. +       struct dictionary dict;
  1240. +       struct lzma2_dec lzma2;
  1241. +       struct lzma_dec lzma;
  1242. +
  1243. +       /*
  1244. +        * Temporary buffer which holds small number of input bytes between
  1245. +        * decoder calls. See lzma2_lzma() for details.
  1246. +        */
  1247. +       struct {
  1248. +               uint32_t size;
  1249. +               uint8_t buf[3 * LZMA_IN_REQUIRED];
  1250. +       } temp;
  1251. +};
  1252. +
  1253. +/**************
  1254. + * Dictionary *
  1255. + **************/
  1256. +
  1257. +/*
  1258. + * Reset the dictionary state. When in single-call mode, set up the beginning
  1259. + * of the dictionary to point to the actual output buffer.
  1260. + */
  1261. +static void INIT dict_reset(struct dictionary *dict, struct xz_buf *b)
  1262. +{
  1263. +       if (DEC_IS_SINGLE(dict->mode)) {
  1264. +               dict->buf = b->out + b->out_pos;
  1265. +               dict->end = b->out_size - b->out_pos;
  1266. +       }
  1267. +
  1268. +       dict->start = 0;
  1269. +       dict->pos = 0;
  1270. +       dict->limit = 0;
  1271. +       dict->full = 0;
  1272. +}
  1273. +
  1274. +/* Set dictionary write limit */
  1275. +static void INIT dict_limit(struct dictionary *dict, size_t out_max)
  1276. +{
  1277. +       if (dict->end - dict->pos <= out_max)
  1278. +               dict->limit = dict->end;
  1279. +       else
  1280. +               dict->limit = dict->pos + out_max;
  1281. +}
  1282. +
  1283. +/* Return true if at least one byte can be written into the dictionary. */
  1284. +static inline bool_t INIT dict_has_space(const struct dictionary *dict)
  1285. +{
  1286. +       return dict->pos < dict->limit;
  1287. +}
  1288. +
  1289. +/*
  1290. + * Get a byte from the dictionary at the given distance. The distance is
  1291. + * assumed to valid, or as a special case, zero when the dictionary is
  1292. + * still empty. This special case is needed for single-call decoding to
  1293. + * avoid writing a '\0' to the end of the destination buffer.
  1294. + */
  1295. +static inline uint32_t INIT dict_get(const struct dictionary *dict, uint32_t dist)
  1296. +{
  1297. +       size_t offset = dict->pos - dist - 1;
  1298. +
  1299. +       if (dist >= dict->pos)
  1300. +               offset += dict->end;
  1301. +
  1302. +       return dict->full > 0 ? dict->buf[offset] : 0;
  1303. +}
  1304. +
  1305. +/*
  1306. + * Put one byte into the dictionary. It is assumed that there is space for it.
  1307. + */
  1308. +static inline void INIT dict_put(struct dictionary *dict, uint8_t byte)
  1309. +{
  1310. +       dict->buf[dict->pos++] = byte;
  1311. +
  1312. +       if (dict->full < dict->pos)
  1313. +               dict->full = dict->pos;
  1314. +}
  1315. +
  1316. +/*
  1317. + * Repeat given number of bytes from the given distance. If the distance is
  1318. + * invalid, false is returned. On success, true is returned and *len is
  1319. + * updated to indicate how many bytes were left to be repeated.
  1320. + */
  1321. +static bool_t INIT dict_repeat(struct dictionary *dict, uint32_t *len, uint32_t dist)
  1322. +{
  1323. +       size_t back;
  1324. +       uint32_t left;
  1325. +
  1326. +       if (dist >= dict->full || dist >= dict->size)
  1327. +               return false;
  1328. +
  1329. +       left = min_t(size_t, dict->limit - dict->pos, *len);
  1330. +       *len -= left;
  1331. +
  1332. +       back = dict->pos - dist - 1;
  1333. +       if (dist >= dict->pos)
  1334. +               back += dict->end;
  1335. +
  1336. +       do {
  1337. +               dict->buf[dict->pos++] = dict->buf[back++];
  1338. +               if (back == dict->end)
  1339. +                       back = 0;
  1340. +       } while (--left > 0);
  1341. +
  1342. +       if (dict->full < dict->pos)
  1343. +               dict->full = dict->pos;
  1344. +
  1345. +       return true;
  1346. +}
  1347. +
  1348. +/* Copy uncompressed data as is from input to dictionary and output buffers. */
  1349. +static void INIT dict_uncompressed(struct dictionary *dict, struct xz_buf *b,
  1350. +                                  uint32_t *left)
  1351. +{
  1352. +       size_t copy_size;
  1353. +
  1354. +       while (*left > 0 && b->in_pos < b->in_size
  1355. +                       && b->out_pos < b->out_size) {
  1356. +               copy_size = min(b->in_size - b->in_pos,
  1357. +                               b->out_size - b->out_pos);
  1358. +               if (copy_size > dict->end - dict->pos)
  1359. +                       copy_size = dict->end - dict->pos;
  1360. +               if (copy_size > *left)
  1361. +                       copy_size = *left;
  1362. +
  1363. +               *left -= copy_size;
  1364. +
  1365. +               memcpy(dict->buf + dict->pos, b->in + b->in_pos, copy_size);
  1366. +               dict->pos += copy_size;
  1367. +
  1368. +               if (dict->full < dict->pos)
  1369. +                       dict->full = dict->pos;
  1370. +
  1371. +               if (DEC_IS_MULTI(dict->mode)) {
  1372. +                       if (dict->pos == dict->end)
  1373. +                               dict->pos = 0;
  1374. +
  1375. +                       memcpy(b->out + b->out_pos, b->in + b->in_pos,
  1376. +                                       copy_size);
  1377. +               }
  1378. +
  1379. +               dict->start = dict->pos;
  1380. +
  1381. +               b->out_pos += copy_size;
  1382. +               b->in_pos += copy_size;
  1383. +       }
  1384. +}
  1385. +
  1386. +/*
  1387. + * Flush pending data from dictionary to b->out. It is assumed that there is
  1388. + * enough space in b->out. This is guaranteed because caller uses dict_limit()
  1389. + * before decoding data into the dictionary.
  1390. + */
  1391. +static uint32_t INIT dict_flush(struct dictionary *dict, struct xz_buf *b)
  1392. +{
  1393. +       size_t copy_size = dict->pos - dict->start;
  1394. +
  1395. +       if (DEC_IS_MULTI(dict->mode)) {
  1396. +               if (dict->pos == dict->end)
  1397. +                       dict->pos = 0;
  1398. +
  1399. +               memcpy(b->out + b->out_pos, dict->buf + dict->start,
  1400. +                               copy_size);
  1401. +       }
  1402. +
  1403. +       dict->start = dict->pos;
  1404. +       b->out_pos += copy_size;
  1405. +       return copy_size;
  1406. +}
  1407. +
  1408. +/*****************
  1409. + * Range decoder *
  1410. + *****************/
  1411. +
  1412. +/* Reset the range decoder. */
  1413. +static void INIT rc_reset(struct rc_dec *rc)
  1414. +{
  1415. +       rc->range = (uint32_t)-1;
  1416. +       rc->code = 0;
  1417. +       rc->init_bytes_left = RC_INIT_BYTES;
  1418. +}
  1419. +
  1420. +/*
  1421. + * Read the first five initial bytes into rc->code if they haven't been
  1422. + * read already. (Yes, the first byte gets completely ignored.)
  1423. + */
  1424. +static bool_t INIT rc_read_init(struct rc_dec *rc, struct xz_buf *b)
  1425. +{
  1426. +       while (rc->init_bytes_left > 0) {
  1427. +               if (b->in_pos == b->in_size)
  1428. +                       return false;
  1429. +
  1430. +               rc->code = (rc->code << 8) + b->in[b->in_pos++];
  1431. +               --rc->init_bytes_left;
  1432. +       }
  1433. +
  1434. +       return true;
  1435. +}
  1436. +
  1437. +/* Return true if there may not be enough input for the next decoding loop. */
  1438. +static inline bool_t INIT rc_limit_exceeded(const struct rc_dec *rc)
  1439. +{
  1440. +       return rc->in_pos > rc->in_limit;
  1441. +}
  1442. +
  1443. +/*
  1444. + * Return true if it is possible (from point of view of range decoder) that
  1445. + * we have reached the end of the LZMA chunk.
  1446. + */
  1447. +static inline bool_t INIT rc_is_finished(const struct rc_dec *rc)
  1448. +{
  1449. +       return rc->code == 0;
  1450. +}
  1451. +
  1452. +/* Read the next input byte if needed. */
  1453. +static always_inline void rc_normalize(struct rc_dec *rc)
  1454. +{
  1455. +       if (rc->range < RC_TOP_VALUE) {
  1456. +               rc->range <<= RC_SHIFT_BITS;
  1457. +               rc->code = (rc->code << RC_SHIFT_BITS) + rc->in[rc->in_pos++];
  1458. +       }
  1459. +}
  1460. +
  1461. +/*
  1462. + * Decode one bit. In some versions, this function has been splitted in three
  1463. + * functions so that the compiler is supposed to be able to more easily avoid
  1464. + * an extra branch. In this particular version of the LZMA decoder, this
  1465. + * doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
  1466. + * on x86). Using a non-splitted version results in nicer looking code too.
  1467. + *
  1468. + * NOTE: This must return an int. Do not make it return a bool or the speed
  1469. + * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care,
  1470. + * and it generates 10-20 % faster code than GCC 3.x from this file anyway.)
  1471. + */
  1472. +static always_inline int rc_bit(struct rc_dec *rc, uint16_t *prob)
  1473. +{
  1474. +       uint32_t bound;
  1475. +       int bit;
  1476. +
  1477. +       rc_normalize(rc);
  1478. +       bound = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * *prob;
  1479. +       if (rc->code < bound) {
  1480. +               rc->range = bound;
  1481. +               *prob += (RC_BIT_MODEL_TOTAL - *prob) >> RC_MOVE_BITS;
  1482. +               bit = 0;
  1483. +       } else {
  1484. +               rc->range -= bound;
  1485. +               rc->code -= bound;
  1486. +               *prob -= *prob >> RC_MOVE_BITS;
  1487. +               bit = 1;
  1488. +       }
  1489. +
  1490. +       return bit;
  1491. +}
  1492. +
  1493. +/* Decode a bittree starting from the most significant bit. */
  1494. +static always_inline uint32_t rc_bittree(struct rc_dec *rc,
  1495. +                                        uint16_t *probs, uint32_t limit)
  1496. +{
  1497. +       uint32_t symbol = 1;
  1498. +
  1499. +       do {
  1500. +               if (rc_bit(rc, &probs[symbol]))
  1501. +                       symbol = (symbol << 1) + 1;
  1502. +               else
  1503. +                       symbol <<= 1;
  1504. +       } while (symbol < limit);
  1505. +
  1506. +       return symbol;
  1507. +}
  1508. +
  1509. +/* Decode a bittree starting from the least significant bit. */
  1510. +static always_inline void rc_bittree_reverse(struct rc_dec *rc,
  1511. +                                            uint16_t *probs,
  1512. +                                            uint32_t *dest, uint32_t limit)
  1513. +{
  1514. +       uint32_t symbol = 1;
  1515. +       uint32_t i = 0;
  1516. +
  1517. +       do {
  1518. +               if (rc_bit(rc, &probs[symbol])) {
  1519. +                       symbol = (symbol << 1) + 1;
  1520. +                       *dest += 1 << i;
  1521. +               } else {
  1522. +                       symbol <<= 1;
  1523. +               }
  1524. +       } while (++i < limit);
  1525. +}
  1526. +
  1527. +/* Decode direct bits (fixed fifty-fifty probability) */
  1528. +static inline void INIT rc_direct(struct rc_dec *rc, uint32_t *dest, uint32_t limit)
  1529. +{
  1530. +       uint32_t mask;
  1531. +
  1532. +       do {
  1533. +               rc_normalize(rc);
  1534. +               rc->range >>= 1;
  1535. +               rc->code -= rc->range;
  1536. +               mask = (uint32_t)0 - (rc->code >> 31);
  1537. +               rc->code += rc->range & mask;
  1538. +               *dest = (*dest << 1) + (mask + 1);
  1539. +       } while (--limit > 0);
  1540. +}
  1541. +
  1542. +/********
  1543. + * LZMA *
  1544. + ********/
  1545. +
  1546. +/* Get pointer to literal coder probability array. */
  1547. +static uint16_t *INIT lzma_literal_probs(struct xz_dec_lzma2 *s)
  1548. +{
  1549. +       uint32_t prev_byte = dict_get(&s->dict, 0);
  1550. +       uint32_t low = prev_byte >> (8 - s->lzma.lc);
  1551. +       uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc;
  1552. +       return s->lzma.literal[low + high];
  1553. +}
  1554. +
  1555. +/* Decode a literal (one 8-bit byte) */
  1556. +static void INIT lzma_literal(struct xz_dec_lzma2 *s)
  1557. +{
  1558. +       uint16_t *probs;
  1559. +       uint32_t symbol;
  1560. +       uint32_t match_byte;
  1561. +       uint32_t match_bit;
  1562. +       uint32_t offset;
  1563. +       uint32_t i;
  1564. +
  1565. +       probs = lzma_literal_probs(s);
  1566. +
  1567. +       if (lzma_state_is_literal(s->lzma.state)) {
  1568. +               symbol = rc_bittree(&s->rc, probs, 0x100);
  1569. +       } else {
  1570. +               symbol = 1;
  1571. +               match_byte = dict_get(&s->dict, s->lzma.rep0) << 1;
  1572. +               offset = 0x100;
  1573. +
  1574. +               do {
  1575. +                       match_bit = match_byte & offset;
  1576. +                       match_byte <<= 1;
  1577. +                       i = offset + match_bit + symbol;
  1578. +
  1579. +                       if (rc_bit(&s->rc, &probs[i])) {
  1580. +                               symbol = (symbol << 1) + 1;
  1581. +                               offset &= match_bit;
  1582. +                       } else {
  1583. +                               symbol <<= 1;
  1584. +                               offset &= ~match_bit;
  1585. +                       }
  1586. +               } while (symbol < 0x100);
  1587. +       }
  1588. +
  1589. +       dict_put(&s->dict, (uint8_t)symbol);
  1590. +       lzma_state_literal(&s->lzma.state);
  1591. +}
  1592. +
  1593. +/* Decode the length of the match into s->lzma.len. */
  1594. +static void INIT lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l,
  1595. +                         uint32_t pos_state)
  1596. +{
  1597. +       uint16_t *probs;
  1598. +       uint32_t limit;
  1599. +
  1600. +       if (!rc_bit(&s->rc, &l->choice)) {
  1601. +               probs = l->low[pos_state];
  1602. +               limit = LEN_LOW_SYMBOLS;
  1603. +               s->lzma.len = MATCH_LEN_MIN;
  1604. +       } else {
  1605. +               if (!rc_bit(&s->rc, &l->choice2)) {
  1606. +                       probs = l->mid[pos_state];
  1607. +                       limit = LEN_MID_SYMBOLS;
  1608. +                       s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS;
  1609. +               } else {
  1610. +                       probs = l->high;
  1611. +                       limit = LEN_HIGH_SYMBOLS;
  1612. +                       s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS
  1613. +                                       + LEN_MID_SYMBOLS;
  1614. +               }
  1615. +       }
  1616. +
  1617. +       s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit;
  1618. +}
  1619. +
  1620. +/* Decode a match. The distance will be stored in s->lzma.rep0. */
  1621. +static void INIT lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
  1622. +{
  1623. +       uint16_t *probs;
  1624. +       uint32_t dist_slot;
  1625. +       uint32_t limit;
  1626. +
  1627. +       lzma_state_match(&s->lzma.state);
  1628. +
  1629. +       s->lzma.rep3 = s->lzma.rep2;
  1630. +       s->lzma.rep2 = s->lzma.rep1;
  1631. +       s->lzma.rep1 = s->lzma.rep0;
  1632. +
  1633. +       lzma_len(s, &s->lzma.match_len_dec, pos_state);
  1634. +
  1635. +       probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)];
  1636. +       dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS;
  1637. +
  1638. +       if (dist_slot < DIST_MODEL_START) {
  1639. +               s->lzma.rep0 = dist_slot;
  1640. +       } else {
  1641. +               limit = (dist_slot >> 1) - 1;
  1642. +               s->lzma.rep0 = 2 + (dist_slot & 1);
  1643. +
  1644. +               if (dist_slot < DIST_MODEL_END) {
  1645. +                       s->lzma.rep0 <<= limit;
  1646. +                       probs = s->lzma.dist_special + s->lzma.rep0
  1647. +                                       - dist_slot - 1;
  1648. +                       rc_bittree_reverse(&s->rc, probs,
  1649. +                                       &s->lzma.rep0, limit);
  1650. +               } else {
  1651. +                       rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS);
  1652. +                       s->lzma.rep0 <<= ALIGN_BITS;
  1653. +                       rc_bittree_reverse(&s->rc, s->lzma.dist_align,
  1654. +                                       &s->lzma.rep0, ALIGN_BITS);
  1655. +               }
  1656. +       }
  1657. +}
  1658. +
  1659. +/*
  1660. + * Decode a repeated match. The distance is one of the four most recently
  1661. + * seen matches. The distance will be stored in s->lzma.rep0.
  1662. + */
  1663. +static void INIT lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
  1664. +{
  1665. +       uint32_t tmp;
  1666. +
  1667. +       if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) {
  1668. +               if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[
  1669. +                               s->lzma.state][pos_state])) {
  1670. +                       lzma_state_short_rep(&s->lzma.state);
  1671. +                       s->lzma.len = 1;
  1672. +                       return;
  1673. +               }
  1674. +       } else {
  1675. +               if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) {
  1676. +                       tmp = s->lzma.rep1;
  1677. +               } else {
  1678. +                       if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) {
  1679. +                               tmp = s->lzma.rep2;
  1680. +                       } else {
  1681. +                               tmp = s->lzma.rep3;
  1682. +                               s->lzma.rep3 = s->lzma.rep2;
  1683. +                       }
  1684. +
  1685. +                       s->lzma.rep2 = s->lzma.rep1;
  1686. +               }
  1687. +
  1688. +               s->lzma.rep1 = s->lzma.rep0;
  1689. +               s->lzma.rep0 = tmp;
  1690. +       }
  1691. +
  1692. +       lzma_state_long_rep(&s->lzma.state);
  1693. +       lzma_len(s, &s->lzma.rep_len_dec, pos_state);
  1694. +}
  1695. +
  1696. +/* LZMA decoder core */
  1697. +static bool_t INIT lzma_main(struct xz_dec_lzma2 *s)
  1698. +{
  1699. +       uint32_t pos_state;
  1700. +
  1701. +       /*
  1702. +        * If the dictionary was reached during the previous call, try to
  1703. +        * finish the possibly pending repeat in the dictionary.
  1704. +        */
  1705. +       if (dict_has_space(&s->dict) && s->lzma.len > 0)
  1706. +               dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0);
  1707. +
  1708. +       /*
  1709. +        * Decode more LZMA symbols. One iteration may consume up to
  1710. +        * LZMA_IN_REQUIRED - 1 bytes.
  1711. +        */
  1712. +       while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) {
  1713. +               pos_state = s->dict.pos & s->lzma.pos_mask;
  1714. +
  1715. +               if (!rc_bit(&s->rc, &s->lzma.is_match[
  1716. +                               s->lzma.state][pos_state])) {
  1717. +                       lzma_literal(s);
  1718. +               } else {
  1719. +                       if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state]))
  1720. +                               lzma_rep_match(s, pos_state);
  1721. +                       else
  1722. +                               lzma_match(s, pos_state);
  1723. +
  1724. +                       if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0))
  1725. +                               return false;
  1726. +               }
  1727. +       }
  1728. +
  1729. +       /*
  1730. +        * Having the range decoder always normalized when we are outside
  1731. +        * this function makes it easier to correctly handle end of the chunk.
  1732. +        */
  1733. +       rc_normalize(&s->rc);
  1734. +
  1735. +       return true;
  1736. +}
  1737. +
  1738. +/*
  1739. + * Reset the LZMA decoder and range decoder state. Dictionary is nore reset
  1740. + * here, because LZMA state may be reset without resetting the dictionary.
  1741. + */
  1742. +static void INIT lzma_reset(struct xz_dec_lzma2 *s)
  1743. +{
  1744. +       uint16_t *probs;
  1745. +       size_t i;
  1746. +
  1747. +       s->lzma.state = STATE_LIT_LIT;
  1748. +       s->lzma.rep0 = 0;
  1749. +       s->lzma.rep1 = 0;
  1750. +       s->lzma.rep2 = 0;
  1751. +       s->lzma.rep3 = 0;
  1752. +
  1753. +       /*
  1754. +        * All probabilities are initialized to the same value. This hack
  1755. +        * makes the code smaller by avoiding a separate loop for each
  1756. +        * probability array.
  1757. +        *
  1758. +        * This could be optimized so that only that part of literal
  1759. +        * probabilities that are actually required. In the common case
  1760. +        * we would write 12 KiB less.
  1761. +        */
  1762. +       probs = s->lzma.is_match[0];
  1763. +       for (i = 0; i < PROBS_TOTAL; ++i)
  1764. +               probs[i] = RC_BIT_MODEL_TOTAL / 2;
  1765. +
  1766. +       rc_reset(&s->rc);
  1767. +}
  1768. +
  1769. +/*
  1770. + * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks
  1771. + * from the decoded lp and pb values. On success, the LZMA decoder state is
  1772. + * reset and true is returned.
  1773. + */
  1774. +static bool_t INIT lzma_props(struct xz_dec_lzma2 *s, uint8_t props)
  1775. +{
  1776. +       if (props > (4 * 5 + 4) * 9 + 8)
  1777. +               return false;
  1778. +
  1779. +       s->lzma.pos_mask = 0;
  1780. +       while (props >= 9 * 5) {
  1781. +               props -= 9 * 5;
  1782. +               ++s->lzma.pos_mask;
  1783. +       }
  1784. +
  1785. +       s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1;
  1786. +
  1787. +       s->lzma.literal_pos_mask = 0;
  1788. +       while (props >= 9) {
  1789. +               props -= 9;
  1790. +               ++s->lzma.literal_pos_mask;
  1791. +       }
  1792. +
  1793. +       s->lzma.lc = props;
  1794. +
  1795. +       if (s->lzma.lc + s->lzma.literal_pos_mask > 4)
  1796. +               return false;
  1797. +
  1798. +       s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1;
  1799. +
  1800. +       lzma_reset(s);
  1801. +
  1802. +       return true;
  1803. +}
  1804. +
  1805. +/*********
  1806. + * LZMA2 *
  1807. + *********/
  1808. +
  1809. +/*
  1810. + * The LZMA decoder assumes that if the input limit (s->rc.in_limit) hasn't
  1811. + * been exceeded, it is safe to read up to LZMA_IN_REQUIRED bytes. This
  1812. + * wrapper function takes care of making the LZMA decoder's assumption safe.
  1813. + *
  1814. + * As long as there is plenty of input left to be decoded in the current LZMA
  1815. + * chunk, we decode directly from the caller-supplied input buffer until
  1816. + * there's LZMA_IN_REQUIRED bytes left. Those remaining bytes are copied into
  1817. + * s->temp.buf, which (hopefully) gets filled on the next call to this
  1818. + * function. We decode a few bytes from the temporary buffer so that we can
  1819. + * continue decoding from the caller-supplied input buffer again.
  1820. + */
  1821. +static bool_t INIT lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b)
  1822. +{
  1823. +       size_t in_avail;
  1824. +       uint32_t tmp;
  1825. +
  1826. +       in_avail = b->in_size - b->in_pos;
  1827. +       if (s->temp.size > 0 || s->lzma2.compressed == 0) {
  1828. +               tmp = 2 * LZMA_IN_REQUIRED - s->temp.size;
  1829. +               if (tmp > s->lzma2.compressed - s->temp.size)
  1830. +                       tmp = s->lzma2.compressed - s->temp.size;
  1831. +               if (tmp > in_avail)
  1832. +                       tmp = in_avail;
  1833. +
  1834. +               memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp);
  1835. +
  1836. +               if (s->temp.size + tmp == s->lzma2.compressed) {
  1837. +                       memzero(s->temp.buf + s->temp.size + tmp,
  1838. +                                       sizeof(s->temp.buf)
  1839. +                                               - s->temp.size - tmp);
  1840. +                       s->rc.in_limit = s->temp.size + tmp;
  1841. +               } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) {
  1842. +                       s->temp.size += tmp;
  1843. +                       b->in_pos += tmp;
  1844. +                       return true;
  1845. +               } else {
  1846. +                       s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED;
  1847. +               }
  1848. +
  1849. +               s->rc.in = s->temp.buf;
  1850. +               s->rc.in_pos = 0;
  1851. +
  1852. +               if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp)
  1853. +                       return false;
  1854. +
  1855. +               s->lzma2.compressed -= s->rc.in_pos;
  1856. +
  1857. +               if (s->rc.in_pos < s->temp.size) {
  1858. +                       s->temp.size -= s->rc.in_pos;
  1859. +                       memmove(s->temp.buf, s->temp.buf + s->rc.in_pos,
  1860. +                                       s->temp.size);
  1861. +                       return true;
  1862. +               }
  1863. +
  1864. +               b->in_pos += s->rc.in_pos - s->temp.size;
  1865. +               s->temp.size = 0;
  1866. +       }
  1867. +
  1868. +       in_avail = b->in_size - b->in_pos;
  1869. +       if (in_avail >= LZMA_IN_REQUIRED) {
  1870. +               s->rc.in = b->in;
  1871. +               s->rc.in_pos = b->in_pos;
  1872. +
  1873. +               if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED)
  1874. +                       s->rc.in_limit = b->in_pos + s->lzma2.compressed;
  1875. +               else
  1876. +                       s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED;
  1877. +
  1878. +               if (!lzma_main(s))
  1879. +                       return false;
  1880. +
  1881. +               in_avail = s->rc.in_pos - b->in_pos;
  1882. +               if (in_avail > s->lzma2.compressed)
  1883. +                       return false;
  1884. +
  1885. +               s->lzma2.compressed -= in_avail;
  1886. +               b->in_pos = s->rc.in_pos;
  1887. +       }
  1888. +
  1889. +       in_avail = b->in_size - b->in_pos;
  1890. +       if (in_avail < LZMA_IN_REQUIRED) {
  1891. +               if (in_avail > s->lzma2.compressed)
  1892. +                       in_avail = s->lzma2.compressed;
  1893. +
  1894. +               memcpy(s->temp.buf, b->in + b->in_pos, in_avail);
  1895. +               s->temp.size = in_avail;
  1896. +               b->in_pos += in_avail;
  1897. +       }
  1898. +
  1899. +       return true;
  1900. +}
  1901. +
  1902. +/*
  1903. + * Take care of the LZMA2 control layer, and forward the job of actual LZMA
  1904. + * decoding or copying of uncompressed chunks to other functions.
  1905. + */
  1906. +XZ_EXTERN enum xz_ret INIT xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
  1907. +                                           struct xz_buf *b)
  1908. +{
  1909. +       uint32_t tmp;
  1910. +
  1911. +       while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) {
  1912. +               switch (s->lzma2.sequence) {
  1913. +               case SEQ_CONTROL:
  1914. +                       /*
  1915. +                        * LZMA2 control byte
  1916. +                        *
  1917. +                        * Exact values:
  1918. +                        *   0x00   End marker
  1919. +                        *   0x01   Dictionary reset followed by
  1920. +                        *          an uncompressed chunk
  1921. +                        *   0x02   Uncompressed chunk (no dictionary reset)
  1922. +                        *
  1923. +                        * Highest three bits (s->control & 0xE0):
  1924. +                        *   0xE0   Dictionary reset, new properties and state
  1925. +                        *          reset, followed by LZMA compressed chunk
  1926. +                        *   0xC0   New properties and state reset, followed
  1927. +                        *          by LZMA compressed chunk (no dictionary
  1928. +                        *          reset)
  1929. +                        *   0xA0   State reset using old properties,
  1930. +                        *          followed by LZMA compressed chunk (no
  1931. +                        *          dictionary reset)
  1932. +                        *   0x80   LZMA chunk (no dictionary or state reset)
  1933. +                        *
  1934. +                        * For LZMA compressed chunks, the lowest five bits
  1935. +                        * (s->control & 1F) are the highest bits of the
  1936. +                        * uncompressed size (bits 16-20).
  1937. +                        *
  1938. +                        * A new LZMA2 stream must begin with a dictionary
  1939. +                        * reset. The first LZMA chunk must set new
  1940. +                        * properties and reset the LZMA state.
  1941. +                        *
  1942. +                        * Values that don't match anything described above
  1943. +                        * are invalid and we return XZ_DATA_ERROR.
  1944. +                        */
  1945. +                       tmp = b->in[b->in_pos++];
  1946. +
  1947. +                       if (tmp >= 0xE0 || tmp == 0x01) {
  1948. +                               s->lzma2.need_props = true;
  1949. +                               s->lzma2.need_dict_reset = false;
  1950. +                               dict_reset(&s->dict, b);
  1951. +                       } else if (s->lzma2.need_dict_reset) {
  1952. +                               return XZ_DATA_ERROR;
  1953. +                       }
  1954. +
  1955. +                       if (tmp >= 0x80) {
  1956. +                               s->lzma2.uncompressed = (tmp & 0x1F) << 16;
  1957. +                               s->lzma2.sequence = SEQ_UNCOMPRESSED_1;
  1958. +
  1959. +                               if (tmp >= 0xC0) {
  1960. +                                       /*
  1961. +                                        * When there are new properties,
  1962. +                                        * state reset is done at
  1963. +                                        * SEQ_PROPERTIES.
  1964. +                                        */
  1965. +                                       s->lzma2.need_props = false;
  1966. +                                       s->lzma2.next_sequence
  1967. +                                                       = SEQ_PROPERTIES;
  1968. +
  1969. +                               } else if (s->lzma2.need_props) {
  1970. +                                       return XZ_DATA_ERROR;
  1971. +
  1972. +                               } else {
  1973. +                                       s->lzma2.next_sequence
  1974. +                                                       = SEQ_LZMA_PREPARE;
  1975. +                                       if (tmp >= 0xA0)
  1976. +                                               lzma_reset(s);
  1977. +                               }
  1978. +                       } else {
  1979. +                               if (tmp == 0x00)
  1980. +                                       return XZ_STREAM_END;
  1981. +
  1982. +                               if (tmp > 0x02)
  1983. +                                       return XZ_DATA_ERROR;
  1984. +
  1985. +                               s->lzma2.sequence = SEQ_COMPRESSED_0;
  1986. +                               s->lzma2.next_sequence = SEQ_COPY;
  1987. +                       }
  1988. +
  1989. +                       break;
  1990. +
  1991. +               case SEQ_UNCOMPRESSED_1:
  1992. +                       s->lzma2.uncompressed
  1993. +                                       += (uint32_t)b->in[b->in_pos++] << 8;
  1994. +                       s->lzma2.sequence = SEQ_UNCOMPRESSED_2;
  1995. +                       break;
  1996. +
  1997. +               case SEQ_UNCOMPRESSED_2:
  1998. +                       s->lzma2.uncompressed
  1999. +                                       += (uint32_t)b->in[b->in_pos++] + 1;
  2000. +                       s->lzma2.sequence = SEQ_COMPRESSED_0;
  2001. +                       break;
  2002. +
  2003. +               case SEQ_COMPRESSED_0:
  2004. +                       s->lzma2.compressed
  2005. +                                       = (uint32_t)b->in[b->in_pos++] << 8;
  2006. +                       s->lzma2.sequence = SEQ_COMPRESSED_1;
  2007. +                       break;
  2008. +
  2009. +               case SEQ_COMPRESSED_1:
  2010. +                       s->lzma2.compressed
  2011. +                                       += (uint32_t)b->in[b->in_pos++] + 1;
  2012. +                       s->lzma2.sequence = s->lzma2.next_sequence;
  2013. +                       break;
  2014. +
  2015. +               case SEQ_PROPERTIES:
  2016. +                       if (!lzma_props(s, b->in[b->in_pos++]))
  2017. +                               return XZ_DATA_ERROR;
  2018. +
  2019. +                       s->lzma2.sequence = SEQ_LZMA_PREPARE;
  2020. +
  2021. +               case SEQ_LZMA_PREPARE:
  2022. +                       if (s->lzma2.compressed < RC_INIT_BYTES)
  2023. +                               return XZ_DATA_ERROR;
  2024. +
  2025. +                       if (!rc_read_init(&s->rc, b))
  2026. +                               return XZ_OK;
  2027. +
  2028. +                       s->lzma2.compressed -= RC_INIT_BYTES;
  2029. +                       s->lzma2.sequence = SEQ_LZMA_RUN;
  2030. +
  2031. +               case SEQ_LZMA_RUN:
  2032. +                       /*
  2033. +                        * Set dictionary limit to indicate how much we want
  2034. +                        * to be encoded at maximum. Decode new data into the
  2035. +                        * dictionary. Flush the new data from dictionary to
  2036. +                        * b->out. Check if we finished decoding this chunk.
  2037. +                        * In case the dictionary got full but we didn't fill
  2038. +                        * the output buffer yet, we may run this loop
  2039. +                        * multiple times without changing s->lzma2.sequence.
  2040. +                        */
  2041. +                       dict_limit(&s->dict, min_t(size_t,
  2042. +                                       b->out_size - b->out_pos,
  2043. +                                       s->lzma2.uncompressed));
  2044. +                       if (!lzma2_lzma(s, b))
  2045. +                               return XZ_DATA_ERROR;
  2046. +
  2047. +                       s->lzma2.uncompressed -= dict_flush(&s->dict, b);
  2048. +
  2049. +                       if (s->lzma2.uncompressed == 0) {
  2050. +                               if (s->lzma2.compressed > 0 || s->lzma.len > 0
  2051. +                                               || !rc_is_finished(&s->rc))
  2052. +                                       return XZ_DATA_ERROR;
  2053. +
  2054. +                               rc_reset(&s->rc);
  2055. +                               s->lzma2.sequence = SEQ_CONTROL;
  2056. +
  2057. +                       } else if (b->out_pos == b->out_size
  2058. +                                       || (b->in_pos == b->in_size
  2059. +                                               && s->temp.size
  2060. +                                               < s->lzma2.compressed)) {
  2061. +                               return XZ_OK;
  2062. +                       }
  2063. +
  2064. +                       break;
  2065. +
  2066. +               case SEQ_COPY:
  2067. +                       dict_uncompressed(&s->dict, b, &s->lzma2.compressed);
  2068. +                       if (s->lzma2.compressed > 0)
  2069. +                               return XZ_OK;
  2070. +
  2071. +                       s->lzma2.sequence = SEQ_CONTROL;
  2072. +                       break;
  2073. +               }
  2074. +       }
  2075. +
  2076. +       return XZ_OK;
  2077. +}
  2078. +
  2079. +XZ_EXTERN struct xz_dec_lzma2 *INIT xz_dec_lzma2_create(enum xz_mode mode,
  2080. +                                                  uint32_t dict_max)
  2081. +{
  2082. +       struct xz_dec_lzma2 *s = malloc(sizeof(*s));
  2083. +       if (s == NULL)
  2084. +               return NULL;
  2085. +
  2086. +       s->dict.mode = mode;
  2087. +       s->dict.size_max = dict_max;
  2088. +
  2089. +       if (DEC_IS_PREALLOC(mode)) {
  2090. +               s->dict.buf = large_malloc(dict_max);
  2091. +               if (s->dict.buf == NULL) {
  2092. +                       free(s);
  2093. +                       return NULL;
  2094. +               }
  2095. +       } else if (DEC_IS_DYNALLOC(mode)) {
  2096. +               s->dict.buf = NULL;
  2097. +               s->dict.allocated = 0;
  2098. +       }
  2099. +
  2100. +       return s;
  2101. +}
  2102. +
  2103. +XZ_EXTERN enum xz_ret INIT xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props)
  2104. +{
  2105. +       /* This limits dictionary size to 3 GiB to keep parsing simpler. */
  2106. +       if (props > 39)
  2107. +               return XZ_OPTIONS_ERROR;
  2108. +
  2109. +       s->dict.size = 2 + (props & 1);
  2110. +       s->dict.size <<= (props >> 1) + 11;
  2111. +
  2112. +       if (DEC_IS_MULTI(s->dict.mode)) {
  2113. +               if (s->dict.size > s->dict.size_max)
  2114. +                       return XZ_MEMLIMIT_ERROR;
  2115. +
  2116. +               s->dict.end = s->dict.size;
  2117. +
  2118. +               if (DEC_IS_DYNALLOC(s->dict.mode)) {
  2119. +                       if (s->dict.allocated < s->dict.size) {
  2120. +                               large_free(s->dict.buf);
  2121. +                               s->dict.buf = large_malloc(s->dict.size);
  2122. +                               if (s->dict.buf == NULL) {
  2123. +                                       s->dict.allocated = 0;
  2124. +                                       return XZ_MEM_ERROR;
  2125. +                               }
  2126. +                       }
  2127. +               }
  2128. +       }
  2129. +
  2130. +       s->lzma.len = 0;
  2131. +
  2132. +       s->lzma2.sequence = SEQ_CONTROL;
  2133. +       s->lzma2.need_dict_reset = true;
  2134. +
  2135. +       s->temp.size = 0;
  2136. +
  2137. +       return XZ_OK;
  2138. +}
  2139. +
  2140. +XZ_EXTERN void INIT xz_dec_lzma2_end(struct xz_dec_lzma2 *s)
  2141. +{
  2142. +       if (DEC_IS_MULTI(s->dict.mode))
  2143. +               large_free(s->dict.buf);
  2144. +
  2145. +       free(s);
  2146. +}
  2147. diff --git a/xen/common/xz/dec_stream.c b/xen/common/xz/dec_stream.c
  2148. new file mode 100644
  2149. --- /dev/null
  2150. +++ b/xen/common/xz/dec_stream.c
  2151. @@ -0,0 +1,821 @@
  2152. +/*
  2153. + * .xz Stream decoder
  2154. + *
  2155. + * Author: Lasse Collin <lasse.collin@tukaani.org>
  2156. + *
  2157. + * This file has been put into the public domain.
  2158. + * You can do whatever you want with this file.
  2159. + */
  2160. +
  2161. +#include "private.h"
  2162. +#include "stream.h"
  2163. +
  2164. +/* Hash used to validate the Index field */
  2165. +struct xz_dec_hash {
  2166. +       vli_type unpadded;
  2167. +       vli_type uncompressed;
  2168. +       uint32_t crc32;
  2169. +};
  2170. +
  2171. +struct xz_dec {
  2172. +       /* Position in dec_main() */
  2173. +       enum {
  2174. +               SEQ_STREAM_HEADER,
  2175. +               SEQ_BLOCK_START,
  2176. +               SEQ_BLOCK_HEADER,
  2177. +               SEQ_BLOCK_UNCOMPRESS,
  2178. +               SEQ_BLOCK_PADDING,
  2179. +               SEQ_BLOCK_CHECK,
  2180. +               SEQ_INDEX,
  2181. +               SEQ_INDEX_PADDING,
  2182. +               SEQ_INDEX_CRC32,
  2183. +               SEQ_STREAM_FOOTER
  2184. +       } sequence;
  2185. +
  2186. +       /* Position in variable-length integers and Check fields */
  2187. +       uint32_t pos;
  2188. +
  2189. +       /* Variable-length integer decoded by dec_vli() */
  2190. +       vli_type vli;
  2191. +
  2192. +       /* Saved in_pos and out_pos */
  2193. +       size_t in_start;
  2194. +       size_t out_start;
  2195. +
  2196. +       /* CRC32 value in Block or Index */
  2197. +       uint32_t crc32;
  2198. +
  2199. +       /* Type of the integrity check calculated from uncompressed data */
  2200. +       enum xz_check check_type;
  2201. +
  2202. +       /* Operation mode */
  2203. +       enum xz_mode mode;
  2204. +
  2205. +       /*
  2206. +        * True if the next call to xz_dec_run() is allowed to return
  2207. +        * XZ_BUF_ERROR.
  2208. +        */
  2209. +       bool_t allow_buf_error;
  2210. +
  2211. +       /* Information stored in Block Header */
  2212. +       struct {
  2213. +               /*
  2214. +                * Value stored in the Compressed Size field, or
  2215. +                * VLI_UNKNOWN if Compressed Size is not present.
  2216. +                */
  2217. +               vli_type compressed;
  2218. +
  2219. +               /*
  2220. +                * Value stored in the Uncompressed Size field, or
  2221. +                * VLI_UNKNOWN if Uncompressed Size is not present.
  2222. +                */
  2223. +               vli_type uncompressed;
  2224. +
  2225. +               /* Size of the Block Header field */
  2226. +               uint32_t size;
  2227. +       } block_header;
  2228. +
  2229. +       /* Information collected when decoding Blocks */
  2230. +       struct {
  2231. +               /* Observed compressed size of the current Block */
  2232. +               vli_type compressed;
  2233. +
  2234. +               /* Observed uncompressed size of the current Block */
  2235. +               vli_type uncompressed;
  2236. +
  2237. +               /* Number of Blocks decoded so far */
  2238. +               vli_type count;
  2239. +
  2240. +               /*
  2241. +                * Hash calculated from the Block sizes. This is used to
  2242. +                * validate the Index field.
  2243. +                */
  2244. +               struct xz_dec_hash hash;
  2245. +       } block;
  2246. +
  2247. +       /* Variables needed when verifying the Index field */
  2248. +       struct {
  2249. +               /* Position in dec_index() */
  2250. +               enum {
  2251. +                       SEQ_INDEX_COUNT,
  2252. +                       SEQ_INDEX_UNPADDED,
  2253. +                       SEQ_INDEX_UNCOMPRESSED
  2254. +               } sequence;
  2255. +
  2256. +               /* Size of the Index in bytes */
  2257. +               vli_type size;
  2258. +
  2259. +               /* Number of Records (matches block.count in valid files) */
  2260. +               vli_type count;
  2261. +
  2262. +               /*
  2263. +                * Hash calculated from the Records (matches block.hash in
  2264. +                * valid files).
  2265. +                */
  2266. +               struct xz_dec_hash hash;
  2267. +       } index;
  2268. +
  2269. +       /*
  2270. +        * Temporary buffer needed to hold Stream Header, Block Header,
  2271. +        * and Stream Footer. The Block Header is the biggest (1 KiB)
  2272. +        * so we reserve space according to that. buf[] has to be aligned
  2273. +        * to a multiple of four bytes; the size_t variables before it
  2274. +        * should guarantee this.
  2275. +        */
  2276. +       struct {
  2277. +               size_t pos;
  2278. +               size_t size;
  2279. +               uint8_t buf[1024];
  2280. +       } temp;
  2281. +
  2282. +       struct xz_dec_lzma2 *lzma2;
  2283. +
  2284. +#ifdef XZ_DEC_BCJ
  2285. +       struct xz_dec_bcj *bcj;
  2286. +       bool_t bcj_active;
  2287. +#endif
  2288. +};
  2289. +
  2290. +#ifdef XZ_DEC_ANY_CHECK
  2291. +/* Sizes of the Check field with different Check IDs */
  2292. +static const uint8_t check_sizes[16] = {
  2293. +       0,
  2294. +       4, 4, 4,
  2295. +       8, 8, 8,
  2296. +       16, 16, 16,
  2297. +       32, 32, 32,
  2298. +       64, 64, 64
  2299. +};
  2300. +#endif
  2301. +
  2302. +/*
  2303. + * Fill s->temp by copying data starting from b->in[b->in_pos]. Caller
  2304. + * must have set s->temp.pos to indicate how much data we are supposed
  2305. + * to copy into s->temp.buf. Return true once s->temp.pos has reached
  2306. + * s->temp.size.
  2307. + */
  2308. +static bool_t INIT fill_temp(struct xz_dec *s, struct xz_buf *b)
  2309. +{
  2310. +       size_t copy_size = min_t(size_t,
  2311. +                       b->in_size - b->in_pos, s->temp.size - s->temp.pos);
  2312. +
  2313. +       memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size);
  2314. +       b->in_pos += copy_size;
  2315. +       s->temp.pos += copy_size;
  2316. +
  2317. +       if (s->temp.pos == s->temp.size) {
  2318. +               s->temp.pos = 0;
  2319. +               return true;
  2320. +       }
  2321. +
  2322. +       return false;
  2323. +}
  2324. +
  2325. +/* Decode a variable-length integer (little-endian base-128 encoding) */
  2326. +static enum xz_ret INIT dec_vli(struct xz_dec *s, const uint8_t *in,
  2327. +                               size_t *in_pos, size_t in_size)
  2328. +{
  2329. +       uint8_t byte;
  2330. +
  2331. +       if (s->pos == 0)
  2332. +               s->vli = 0;
  2333. +
  2334. +       while (*in_pos < in_size) {
  2335. +               byte = in[*in_pos];
  2336. +               ++*in_pos;
  2337. +
  2338. +               s->vli |= (vli_type)(byte & 0x7F) << s->pos;
  2339. +
  2340. +               if ((byte & 0x80) == 0) {
  2341. +                       /* Don't allow non-minimal encodings. */
  2342. +                       if (byte == 0 && s->pos != 0)
  2343. +                               return XZ_DATA_ERROR;
  2344. +
  2345. +                       s->pos = 0;
  2346. +                       return XZ_STREAM_END;
  2347. +               }
  2348. +
  2349. +               s->pos += 7;
  2350. +               if (s->pos == 7 * VLI_BYTES_MAX)
  2351. +                       return XZ_DATA_ERROR;
  2352. +       }
  2353. +
  2354. +       return XZ_OK;
  2355. +}
  2356. +
  2357. +/*
  2358. + * Decode the Compressed Data field from a Block. Update and validate
  2359. + * the observed compressed and uncompressed sizes of the Block so that
  2360. + * they don't exceed the values possibly stored in the Block Header
  2361. + * (validation assumes that no integer overflow occurs, since vli_type
  2362. + * is normally uint64_t). Update the CRC32 if presence of the CRC32
  2363. + * field was indicated in Stream Header.
  2364. + *
  2365. + * Once the decoding is finished, validate that the observed sizes match
  2366. + * the sizes possibly stored in the Block Header. Update the hash and
  2367. + * Block count, which are later used to validate the Index field.
  2368. + */
  2369. +static enum xz_ret INIT dec_block(struct xz_dec *s, struct xz_buf *b)
  2370. +{
  2371. +       enum xz_ret ret;
  2372. +
  2373. +       s->in_start = b->in_pos;
  2374. +       s->out_start = b->out_pos;
  2375. +
  2376. +#ifdef XZ_DEC_BCJ
  2377. +       if (s->bcj_active)
  2378. +               ret = xz_dec_bcj_run(s->bcj, s->lzma2, b);
  2379. +       else
  2380. +#endif
  2381. +               ret = xz_dec_lzma2_run(s->lzma2, b);
  2382. +
  2383. +       s->block.compressed += b->in_pos - s->in_start;
  2384. +       s->block.uncompressed += b->out_pos - s->out_start;
  2385. +
  2386. +       /*
  2387. +        * There is no need to separately check for VLI_UNKNOWN, since
  2388. +        * the observed sizes are always smaller than VLI_UNKNOWN.
  2389. +        */
  2390. +       if (s->block.compressed > s->block_header.compressed
  2391. +                       || s->block.uncompressed
  2392. +                               > s->block_header.uncompressed)
  2393. +               return XZ_DATA_ERROR;
  2394. +
  2395. +       if (s->check_type == XZ_CHECK_CRC32)
  2396. +               s->crc32 = xz_crc32(b->out + s->out_start,
  2397. +                               b->out_pos - s->out_start, s->crc32);
  2398. +
  2399. +       if (ret == XZ_STREAM_END) {
  2400. +               if (s->block_header.compressed != VLI_UNKNOWN
  2401. +                               && s->block_header.compressed
  2402. +                                       != s->block.compressed)
  2403. +                       return XZ_DATA_ERROR;
  2404. +
  2405. +               if (s->block_header.uncompressed != VLI_UNKNOWN
  2406. +                               && s->block_header.uncompressed
  2407. +                                       != s->block.uncompressed)
  2408. +                       return XZ_DATA_ERROR;
  2409. +
  2410. +               s->block.hash.unpadded += s->block_header.size
  2411. +                               + s->block.compressed;
  2412. +
  2413. +#ifdef XZ_DEC_ANY_CHECK
  2414. +               s->block.hash.unpadded += check_sizes[s->check_type];
  2415. +#else
  2416. +               if (s->check_type == XZ_CHECK_CRC32)
  2417. +                       s->block.hash.unpadded += 4;
  2418. +#endif
  2419. +
  2420. +               s->block.hash.uncompressed += s->block.uncompressed;
  2421. +               s->block.hash.crc32 = xz_crc32(
  2422. +                               (const uint8_t *)&s->block.hash,
  2423. +                               sizeof(s->block.hash), s->block.hash.crc32);
  2424. +
  2425. +               ++s->block.count;
  2426. +       }
  2427. +
  2428. +       return ret;
  2429. +}
  2430. +
  2431. +/* Update the Index size and the CRC32 value. */
  2432. +static void INIT index_update(struct xz_dec *s, const struct xz_buf *b)
  2433. +{
  2434. +       size_t in_used = b->in_pos - s->in_start;
  2435. +       s->index.size += in_used;
  2436. +       s->crc32 = xz_crc32(b->in + s->in_start, in_used, s->crc32);
  2437. +}
  2438. +
  2439. +/*
  2440. + * Decode the Number of Records, Unpadded Size, and Uncompressed Size
  2441. + * fields from the Index field. That is, Index Padding and CRC32 are not
  2442. + * decoded by this function.
  2443. + *
  2444. + * This can return XZ_OK (more input needed), XZ_STREAM_END (everything
  2445. + * successfully decoded), or XZ_DATA_ERROR (input is corrupt).
  2446. + */
  2447. +static enum xz_ret INIT dec_index(struct xz_dec *s, struct xz_buf *b)
  2448. +{
  2449. +       enum xz_ret ret;
  2450. +
  2451. +       do {
  2452. +               ret = dec_vli(s, b->in, &b->in_pos, b->in_size);
  2453. +               if (ret != XZ_STREAM_END) {
  2454. +                       index_update(s, b);
  2455. +                       return ret;
  2456. +               }
  2457. +
  2458. +               switch (s->index.sequence) {
  2459. +               case SEQ_INDEX_COUNT:
  2460. +                       s->index.count = s->vli;
  2461. +
  2462. +                       /*
  2463. +                        * Validate that the Number of Records field
  2464. +                        * indicates the same number of Records as
  2465. +                        * there were Blocks in the Stream.
  2466. +                        */
  2467. +                       if (s->index.count != s->block.count)
  2468. +                               return XZ_DATA_ERROR;
  2469. +
  2470. +                       s->index.sequence = SEQ_INDEX_UNPADDED;
  2471. +                       break;
  2472. +
  2473. +               case SEQ_INDEX_UNPADDED:
  2474. +                       s->index.hash.unpadded += s->vli;
  2475. +                       s->index.sequence = SEQ_INDEX_UNCOMPRESSED;
  2476. +                       break;
  2477. +
  2478. +               case SEQ_INDEX_UNCOMPRESSED:
  2479. +                       s->index.hash.uncompressed += s->vli;
  2480. +                       s->index.hash.crc32 = xz_crc32(
  2481. +                                       (const uint8_t *)&s->index.hash,
  2482. +                                       sizeof(s->index.hash),
  2483. +                                       s->index.hash.crc32);
  2484. +                       --s->index.count;
  2485. +                       s->index.sequence = SEQ_INDEX_UNPADDED;
  2486. +                       break;
  2487. +               }
  2488. +       } while (s->index.count > 0);
  2489. +
  2490. +       return XZ_STREAM_END;
  2491. +}
  2492. +
  2493. +/*
  2494. + * Validate that the next four input bytes match the value of s->crc32.
  2495. + * s->pos must be zero when starting to validate the first byte.
  2496. + */
  2497. +static enum xz_ret INIT crc32_validate(struct xz_dec *s, struct xz_buf *b)
  2498. +{
  2499. +       do {
  2500. +               if (b->in_pos == b->in_size)
  2501. +                       return XZ_OK;
  2502. +
  2503. +               if (((s->crc32 >> s->pos) & 0xFF) != b->in[b->in_pos++])
  2504. +                       return XZ_DATA_ERROR;
  2505. +
  2506. +               s->pos += 8;
  2507. +
  2508. +       } while (s->pos < 32);
  2509. +
  2510. +       s->crc32 = 0;
  2511. +       s->pos = 0;
  2512. +
  2513. +       return XZ_STREAM_END;
  2514. +}
  2515. +
  2516. +#ifdef XZ_DEC_ANY_CHECK
  2517. +/*
  2518. + * Skip over the Check field when the Check ID is not supported.
  2519. + * Returns true once the whole Check field has been skipped over.
  2520. + */
  2521. +static bool_t INIT check_skip(struct xz_dec *s, struct xz_buf *b)
  2522. +{
  2523. +       while (s->pos < check_sizes[s->check_type]) {
  2524. +               if (b->in_pos == b->in_size)
  2525. +                       return false;
  2526. +
  2527. +               ++b->in_pos;
  2528. +               ++s->pos;
  2529. +       }
  2530. +
  2531. +       s->pos = 0;
  2532. +
  2533. +       return true;
  2534. +}
  2535. +#endif
  2536. +
  2537. +/* Decode the Stream Header field (the first 12 bytes of the .xz Stream). */
  2538. +static enum xz_ret INIT dec_stream_header(struct xz_dec *s)
  2539. +{
  2540. +       if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE))
  2541. +               return XZ_FORMAT_ERROR;
  2542. +
  2543. +       if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0)
  2544. +                       != get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2))
  2545. +               return XZ_DATA_ERROR;
  2546. +
  2547. +       if (s->temp.buf[HEADER_MAGIC_SIZE] != 0)
  2548. +               return XZ_OPTIONS_ERROR;
  2549. +
  2550. +       /*
  2551. +        * Of integrity checks, we support only none (Check ID = 0) and
  2552. +        * CRC32 (Check ID = 1). However, if XZ_DEC_ANY_CHECK is defined,
  2553. +        * we will accept other check types too, but then the check won't
  2554. +        * be verified and a warning (XZ_UNSUPPORTED_CHECK) will be given.
  2555. +        */
  2556. +       s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1];
  2557. +
  2558. +#ifdef XZ_DEC_ANY_CHECK
  2559. +       if (s->check_type > XZ_CHECK_MAX)
  2560. +               return XZ_OPTIONS_ERROR;
  2561. +
  2562. +       if (s->check_type > XZ_CHECK_CRC32)
  2563. +               return XZ_UNSUPPORTED_CHECK;
  2564. +#else
  2565. +       if (s->check_type > XZ_CHECK_CRC32)
  2566. +               return XZ_OPTIONS_ERROR;
  2567. +#endif
  2568. +
  2569. +       return XZ_OK;
  2570. +}
  2571. +
  2572. +/* Decode the Stream Footer field (the last 12 bytes of the .xz Stream) */
  2573. +static enum xz_ret INIT dec_stream_footer(struct xz_dec *s)
  2574. +{
  2575. +       if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE))
  2576. +               return XZ_DATA_ERROR;
  2577. +
  2578. +       if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf))
  2579. +               return XZ_DATA_ERROR;
  2580. +
  2581. +       /*
  2582. +        * Validate Backward Size. Note that we never added the size of the
  2583. +        * Index CRC32 field to s->index.size, thus we use s->index.size / 4
  2584. +        * instead of s->index.size / 4 - 1.
  2585. +        */
  2586. +       if ((s->index.size >> 2) != get_le32(s->temp.buf + 4))
  2587. +               return XZ_DATA_ERROR;
  2588. +
  2589. +       if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type)
  2590. +               return XZ_DATA_ERROR;
  2591. +
  2592. +       /*
  2593. +        * Use XZ_STREAM_END instead of XZ_OK to be more convenient
  2594. +        * for the caller.
  2595. +        */
  2596. +       return XZ_STREAM_END;
  2597. +}
  2598. +
  2599. +/* Decode the Block Header and initialize the filter chain. */
  2600. +static enum xz_ret INIT dec_block_header(struct xz_dec *s)
  2601. +{
  2602. +       enum xz_ret ret;
  2603. +
  2604. +       /*
  2605. +        * Validate the CRC32. We know that the temp buffer is at least
  2606. +        * eight bytes so this is safe.
  2607. +        */
  2608. +       s->temp.size -= 4;
  2609. +       if (xz_crc32(s->temp.buf, s->temp.size, 0)
  2610. +                       != get_le32(s->temp.buf + s->temp.size))
  2611. +               return XZ_DATA_ERROR;
  2612. +
  2613. +       s->temp.pos = 2;
  2614. +
  2615. +       /*
  2616. +        * Catch unsupported Block Flags. We support only one or two filters
  2617. +        * in the chain, so we catch that with the same test.
  2618. +        */
  2619. +#ifdef XZ_DEC_BCJ
  2620. +       if (s->temp.buf[1] & 0x3E)
  2621. +#else
  2622. +       if (s->temp.buf[1] & 0x3F)
  2623. +#endif
  2624. +               return XZ_OPTIONS_ERROR;
  2625. +
  2626. +       /* Compressed Size */
  2627. +       if (s->temp.buf[1] & 0x40) {
  2628. +               if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
  2629. +                                       != XZ_STREAM_END)
  2630. +                       return XZ_DATA_ERROR;
  2631. +
  2632. +               s->block_header.compressed = s->vli;
  2633. +       } else {
  2634. +               s->block_header.compressed = VLI_UNKNOWN;
  2635. +       }
  2636. +
  2637. +       /* Uncompressed Size */
  2638. +       if (s->temp.buf[1] & 0x80) {
  2639. +               if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
  2640. +                               != XZ_STREAM_END)
  2641. +                       return XZ_DATA_ERROR;
  2642. +
  2643. +               s->block_header.uncompressed = s->vli;
  2644. +       } else {
  2645. +               s->block_header.uncompressed = VLI_UNKNOWN;
  2646. +       }
  2647. +
  2648. +#ifdef XZ_DEC_BCJ
  2649. +       /* If there are two filters, the first one must be a BCJ filter. */
  2650. +       s->bcj_active = s->temp.buf[1] & 0x01;
  2651. +       if (s->bcj_active) {
  2652. +               if (s->temp.size - s->temp.pos < 2)
  2653. +                       return XZ_OPTIONS_ERROR;
  2654. +
  2655. +               ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]);
  2656. +               if (ret != XZ_OK)
  2657. +                       return ret;
  2658. +
  2659. +               /*
  2660. +                * We don't support custom start offset,
  2661. +                * so Size of Properties must be zero.
  2662. +                */
  2663. +               if (s->temp.buf[s->temp.pos++] != 0x00)
  2664. +                       return XZ_OPTIONS_ERROR;
  2665. +       }
  2666. +#endif
  2667. +
  2668. +       /* Valid Filter Flags always take at least two bytes. */
  2669. +       if (s->temp.size - s->temp.pos < 2)
  2670. +               return XZ_DATA_ERROR;
  2671. +
  2672. +       /* Filter ID = LZMA2 */
  2673. +       if (s->temp.buf[s->temp.pos++] != 0x21)
  2674. +               return XZ_OPTIONS_ERROR;
  2675. +
  2676. +       /* Size of Properties = 1-byte Filter Properties */
  2677. +       if (s->temp.buf[s->temp.pos++] != 0x01)
  2678. +               return XZ_OPTIONS_ERROR;
  2679. +
  2680. +       /* Filter Properties contains LZMA2 dictionary size. */
  2681. +       if (s->temp.size - s->temp.pos < 1)
  2682. +               return XZ_DATA_ERROR;
  2683. +
  2684. +       ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]);
  2685. +       if (ret != XZ_OK)
  2686. +               return ret;
  2687. +
  2688. +       /* The rest must be Header Padding. */
  2689. +       while (s->temp.pos < s->temp.size)
  2690. +               if (s->temp.buf[s->temp.pos++] != 0x00)
  2691. +                       return XZ_OPTIONS_ERROR;
  2692. +
  2693. +       s->temp.pos = 0;
  2694. +       s->block.compressed = 0;
  2695. +       s->block.uncompressed = 0;
  2696. +
  2697. +       return XZ_OK;
  2698. +}
  2699. +
  2700. +static enum xz_ret INIT dec_main(struct xz_dec *s, struct xz_buf *b)
  2701. +{
  2702. +       enum xz_ret ret;
  2703. +
  2704. +       /*
  2705. +        * Store the start position for the case when we are in the middle
  2706. +        * of the Index field.
  2707. +        */
  2708. +       s->in_start = b->in_pos;
  2709. +
  2710. +       while (true) {
  2711. +               switch (s->sequence) {
  2712. +               case SEQ_STREAM_HEADER:
  2713. +                       /*
  2714. +                        * Stream Header is copied to s->temp, and then
  2715. +                        * decoded from there. This way if the caller
  2716. +                        * gives us only little input at a time, we can
  2717. +                        * still keep the Stream Header decoding code
  2718. +                        * simple. Similar approach is used in many places
  2719. +                        * in this file.
  2720. +                        */
  2721. +                       if (!fill_temp(s, b))
  2722. +                               return XZ_OK;
  2723. +
  2724. +                       /*
  2725. +                        * If dec_stream_header() returns
  2726. +                        * XZ_UNSUPPORTED_CHECK, it is still possible
  2727. +                        * to continue decoding if working in multi-call
  2728. +                        * mode. Thus, update s->sequence before calling
  2729. +                        * dec_stream_header().
  2730. +                        */
  2731. +                       s->sequence = SEQ_BLOCK_START;
  2732. +
  2733. +                       ret = dec_stream_header(s);
  2734. +                       if (ret != XZ_OK)
  2735. +                               return ret;
  2736. +
  2737. +               case SEQ_BLOCK_START:
  2738. +                       /* We need one byte of input to continue. */
  2739. +                       if (b->in_pos == b->in_size)
  2740. +                               return XZ_OK;
  2741. +
  2742. +                       /* See if this is the beginning of the Index field. */
  2743. +                       if (b->in[b->in_pos] == 0) {
  2744. +                               s->in_start = b->in_pos++;
  2745. +                               s->sequence = SEQ_INDEX;
  2746. +                               break;
  2747. +                       }
  2748. +
  2749. +                       /*
  2750. +                        * Calculate the size of the Block Header and
  2751. +                        * prepare to decode it.
  2752. +                        */
  2753. +                       s->block_header.size
  2754. +                               = ((uint32_t)b->in[b->in_pos] + 1) * 4;
  2755. +
  2756. +                       s->temp.size = s->block_header.size;
  2757. +                       s->temp.pos = 0;
  2758. +                       s->sequence = SEQ_BLOCK_HEADER;
  2759. +
  2760. +               case SEQ_BLOCK_HEADER:
  2761. +                       if (!fill_temp(s, b))
  2762. +                               return XZ_OK;
  2763. +
  2764. +                       ret = dec_block_header(s);
  2765. +                       if (ret != XZ_OK)
  2766. +                               return ret;
  2767. +
  2768. +                       s->sequence = SEQ_BLOCK_UNCOMPRESS;
  2769. +
  2770. +               case SEQ_BLOCK_UNCOMPRESS:
  2771. +                       ret = dec_block(s, b);
  2772. +                       if (ret != XZ_STREAM_END)
  2773. +                               return ret;
  2774. +
  2775. +                       s->sequence = SEQ_BLOCK_PADDING;
  2776. +
  2777. +               case SEQ_BLOCK_PADDING:
  2778. +                       /*
  2779. +                        * Size of Compressed Data + Block Padding
  2780. +                        * must be a multiple of four. We don't need
  2781. +                        * s->block.compressed for anything else
  2782. +                        * anymore, so we use it here to test the size
  2783. +                        * of the Block Padding field.
  2784. +                        */
  2785. +                       while (s->block.compressed & 3) {
  2786. +                               if (b->in_pos == b->in_size)
  2787. +                                       return XZ_OK;
  2788. +
  2789. +                               if (b->in[b->in_pos++] != 0)
  2790. +                                       return XZ_DATA_ERROR;
  2791. +
  2792. +                               ++s->block.compressed;
  2793. +                       }
  2794. +
  2795. +                       s->sequence = SEQ_BLOCK_CHECK;
  2796. +
  2797. +               case SEQ_BLOCK_CHECK:
  2798. +                       if (s->check_type == XZ_CHECK_CRC32) {
  2799. +                               ret = crc32_validate(s, b);
  2800. +                               if (ret != XZ_STREAM_END)
  2801. +                                       return ret;
  2802. +                       }
  2803. +#ifdef XZ_DEC_ANY_CHECK
  2804. +                       else if (!check_skip(s, b)) {
  2805. +                               return XZ_OK;
  2806. +                       }
  2807. +#endif
  2808. +
  2809. +                       s->sequence = SEQ_BLOCK_START;
  2810. +                       break;
  2811. +
  2812. +               case SEQ_INDEX:
  2813. +                       ret = dec_index(s, b);
  2814. +                       if (ret != XZ_STREAM_END)
  2815. +                               return ret;
  2816. +
  2817. +                       s->sequence = SEQ_INDEX_PADDING;
  2818. +
  2819. +               case SEQ_INDEX_PADDING:
  2820. +                       while ((s->index.size + (b->in_pos - s->in_start))
  2821. +                                       & 3) {
  2822. +                               if (b->in_pos == b->in_size) {
  2823. +                                       index_update(s, b);
  2824. +                                       return XZ_OK;
  2825. +                               }
  2826. +
  2827. +                               if (b->in[b->in_pos++] != 0)
  2828. +                                       return XZ_DATA_ERROR;
  2829. +                       }
  2830. +
  2831. +                       /* Finish the CRC32 value and Index size. */
  2832. +                       index_update(s, b);
  2833. +
  2834. +                       /* Compare the hashes to validate the Index field. */
  2835. +                       if (!memeq(&s->block.hash, &s->index.hash,
  2836. +                                       sizeof(s->block.hash)))
  2837. +                               return XZ_DATA_ERROR;
  2838. +
  2839. +                       s->sequence = SEQ_INDEX_CRC32;
  2840. +
  2841. +               case SEQ_INDEX_CRC32:
  2842. +                       ret = crc32_validate(s, b);
  2843. +                       if (ret != XZ_STREAM_END)
  2844. +                               return ret;
  2845. +
  2846. +                       s->temp.size = STREAM_HEADER_SIZE;
  2847. +                       s->sequence = SEQ_STREAM_FOOTER;
  2848. +
  2849. +               case SEQ_STREAM_FOOTER:
  2850. +                       if (!fill_temp(s, b))
  2851. +                               return XZ_OK;
  2852. +
  2853. +                       return dec_stream_footer(s);
  2854. +               }
  2855. +       }
  2856. +
  2857. +       /* Never reached */
  2858. +}
  2859. +
  2860. +XZ_EXTERN void INIT xz_dec_reset(struct xz_dec *s)
  2861. +{
  2862. +       s->sequence = SEQ_STREAM_HEADER;
  2863. +       s->allow_buf_error = false;
  2864. +       s->pos = 0;
  2865. +       s->crc32 = 0;
  2866. +       memzero(&s->block, sizeof(s->block));
  2867. +       memzero(&s->index, sizeof(s->index));
  2868. +       s->temp.pos = 0;
  2869. +       s->temp.size = STREAM_HEADER_SIZE;
  2870. +}
  2871. +
  2872. +/*
  2873. + * xz_dec_run() is a wrapper for dec_main() to handle some special cases in
  2874. + * multi-call and single-call decoding.
  2875. + *
  2876. + * In multi-call mode, we must return XZ_BUF_ERROR when it seems clear that we
  2877. + * are not going to make any progress anymore. This is to prevent the caller
  2878. + * from calling us infinitely when the input file is truncated or otherwise
  2879. + * corrupt. Since zlib-style API allows that the caller fills the input buffer
  2880. + * only when the decoder doesn't produce any new output, we have to be careful
  2881. + * to avoid returning XZ_BUF_ERROR too easily: XZ_BUF_ERROR is returned only
  2882. + * after the second consecutive call to xz_dec_run() that makes no progress.
  2883. + *
  2884. + * In single-call mode, if we couldn't decode everything and no error
  2885. + * occurred, either the input is truncated or the output buffer is too small.
  2886. + * Since we know that the last input byte never produces any output, we know
  2887. + * that if all the input was consumed and decoding wasn't finished, the file
  2888. + * must be corrupt. Otherwise the output buffer has to be too small or the
  2889. + * file is corrupt in a way that decoding it produces too big output.
  2890. + *
  2891. + * If single-call decoding fails, we reset b->in_pos and b->out_pos back to
  2892. + * their original values. This is because with some filter chains there won't
  2893. + * be any valid uncompressed data in the output buffer unless the decoding
  2894. + * actually succeeds (that's the price to pay of using the output buffer as
  2895. + * the workspace).
  2896. + */
  2897. +XZ_EXTERN enum xz_ret INIT xz_dec_run(struct xz_dec *s, struct xz_buf *b)
  2898. +{
  2899. +       size_t in_start;
  2900. +       size_t out_start;
  2901. +       enum xz_ret ret;
  2902. +
  2903. +       if (DEC_IS_SINGLE(s->mode))
  2904. +               xz_dec_reset(s);
  2905. +
  2906. +       in_start = b->in_pos;
  2907. +       out_start = b->out_pos;
  2908. +       ret = dec_main(s, b);
  2909. +
  2910. +       if (DEC_IS_SINGLE(s->mode)) {
  2911. +               if (ret == XZ_OK)
  2912. +                       ret = b->in_pos == b->in_size
  2913. +                                       ? XZ_DATA_ERROR : XZ_BUF_ERROR;
  2914. +
  2915. +               if (ret != XZ_STREAM_END) {
  2916. +                       b->in_pos = in_start;
  2917. +                       b->out_pos = out_start;
  2918. +               }
  2919. +
  2920. +       } else if (ret == XZ_OK && in_start == b->in_pos
  2921. +                       && out_start == b->out_pos) {
  2922. +               if (s->allow_buf_error)
  2923. +                       ret = XZ_BUF_ERROR;
  2924. +
  2925. +               s->allow_buf_error = true;
  2926. +       } else {
  2927. +               s->allow_buf_error = false;
  2928. +       }
  2929. +
  2930. +       return ret;
  2931. +}
  2932. +
  2933. +XZ_EXTERN struct xz_dec *INIT xz_dec_init(enum xz_mode mode, uint32_t dict_max)
  2934. +{
  2935. +       struct xz_dec *s = malloc(sizeof(*s));
  2936. +       if (s == NULL)
  2937. +               return NULL;
  2938. +
  2939. +       s->mode = mode;
  2940. +
  2941. +#ifdef XZ_DEC_BCJ
  2942. +       s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode));
  2943. +       if (s->bcj == NULL)
  2944. +               goto error_bcj;
  2945. +#endif
  2946. +
  2947. +       s->lzma2 = xz_dec_lzma2_create(mode, dict_max);
  2948. +       if (s->lzma2 == NULL)
  2949. +               goto error_lzma2;
  2950. +
  2951. +       xz_dec_reset(s);
  2952. +       return s;
  2953. +
  2954. +error_lzma2:
  2955. +#ifdef XZ_DEC_BCJ
  2956. +       xz_dec_bcj_end(s->bcj);
  2957. +error_bcj:
  2958. +#endif
  2959. +       free(s);
  2960. +       return NULL;
  2961. +}
  2962. +
  2963. +XZ_EXTERN void INIT xz_dec_end(struct xz_dec *s)
  2964. +{
  2965. +       if (s != NULL) {
  2966. +               xz_dec_lzma2_end(s->lzma2);
  2967. +#ifdef XZ_DEC_BCJ
  2968. +               xz_dec_bcj_end(s->bcj);
  2969. +#endif
  2970. +               free(s);
  2971. +       }
  2972. +}
  2973. diff --git a/xen/common/xz/lzma2.h b/xen/common/xz/lzma2.h
  2974. new file mode 100644
  2975. --- /dev/null
  2976. +++ b/xen/common/xz/lzma2.h
  2977. @@ -0,0 +1,204 @@
  2978. +/*
  2979. + * LZMA2 definitions
  2980. + *
  2981. + * Authors: Lasse Collin <lasse.collin@tukaani.org>
  2982. + *          Igor Pavlov <http://7-zip.org/>
  2983. + *
  2984. + * This file has been put into the public domain.
  2985. + * You can do whatever you want with this file.
  2986. + */
  2987. +
  2988. +#ifndef XZ_LZMA2_H
  2989. +#define XZ_LZMA2_H
  2990. +
  2991. +/* Range coder constants */
  2992. +#define RC_SHIFT_BITS 8
  2993. +#define RC_TOP_BITS 24
  2994. +#define RC_TOP_VALUE (1 << RC_TOP_BITS)
  2995. +#define RC_BIT_MODEL_TOTAL_BITS 11
  2996. +#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
  2997. +#define RC_MOVE_BITS 5
  2998. +
  2999. +/*
  3000. + * Maximum number of position states. A position state is the lowest pb
  3001. + * number of bits of the current uncompressed offset. In some places there
  3002. + * are different sets of probabilities for different position states.
  3003. + */
  3004. +#define POS_STATES_MAX (1 << 4)
  3005. +
  3006. +/*
  3007. + * This enum is used to track which LZMA symbols have occurred most recently
  3008. + * and in which order. This information is used to predict the next symbol.
  3009. + *
  3010. + * Symbols:
  3011. + *  - Literal: One 8-bit byte
  3012. + *  - Match: Repeat a chunk of data at some distance
  3013. + *  - Long repeat: Multi-byte match at a recently seen distance
  3014. + *  - Short repeat: One-byte repeat at a recently seen distance
  3015. + *
  3016. + * The symbol names are in from STATE_oldest_older_previous. REP means
  3017. + * either short or long repeated match, and NONLIT means any non-literal.
  3018. + */
  3019. +enum lzma_state {
  3020. +       STATE_LIT_LIT,
  3021. +       STATE_MATCH_LIT_LIT,
  3022. +       STATE_REP_LIT_LIT,
  3023. +       STATE_SHORTREP_LIT_LIT,
  3024. +       STATE_MATCH_LIT,
  3025. +       STATE_REP_LIT,
  3026. +       STATE_SHORTREP_LIT,
  3027. +       STATE_LIT_MATCH,
  3028. +       STATE_LIT_LONGREP,
  3029. +       STATE_LIT_SHORTREP,
  3030. +       STATE_NONLIT_MATCH,
  3031. +       STATE_NONLIT_REP
  3032. +};
  3033. +
  3034. +/* Total number of states */
  3035. +#define STATES 12
  3036. +
  3037. +/* The lowest 7 states indicate that the previous state was a literal. */
  3038. +#define LIT_STATES 7
  3039. +
  3040. +/* Indicate that the latest symbol was a literal. */
  3041. +static inline void INIT lzma_state_literal(enum lzma_state *state)
  3042. +{
  3043. +       if (*state <= STATE_SHORTREP_LIT_LIT)
  3044. +               *state = STATE_LIT_LIT;
  3045. +       else if (*state <= STATE_LIT_SHORTREP)
  3046. +               *state -= 3;
  3047. +       else
  3048. +               *state -= 6;
  3049. +}
  3050. +
  3051. +/* Indicate that the latest symbol was a match. */
  3052. +static inline void INIT lzma_state_match(enum lzma_state *state)
  3053. +{
  3054. +       *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
  3055. +}
  3056. +
  3057. +/* Indicate that the latest state was a long repeated match. */
  3058. +static inline void INIT lzma_state_long_rep(enum lzma_state *state)
  3059. +{
  3060. +       *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
  3061. +}
  3062. +
  3063. +/* Indicate that the latest symbol was a short match. */
  3064. +static inline void INIT lzma_state_short_rep(enum lzma_state *state)
  3065. +{
  3066. +       *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
  3067. +}
  3068. +
  3069. +/* Test if the previous symbol was a literal. */
  3070. +static inline bool_t INIT lzma_state_is_literal(enum lzma_state state)
  3071. +{
  3072. +       return state < LIT_STATES;
  3073. +}
  3074. +
  3075. +/* Each literal coder is divided in three sections:
  3076. + *   - 0x001-0x0FF: Without match byte
  3077. + *   - 0x101-0x1FF: With match byte; match bit is 0
  3078. + *   - 0x201-0x2FF: With match byte; match bit is 1
  3079. + *
  3080. + * Match byte is used when the previous LZMA symbol was something else than
  3081. + * a literal (that is, it was some kind of match).
  3082. + */
  3083. +#define LITERAL_CODER_SIZE 0x300
  3084. +
  3085. +/* Maximum number of literal coders */
  3086. +#define LITERAL_CODERS_MAX (1 << 4)
  3087. +
  3088. +/* Minimum length of a match is two bytes. */
  3089. +#define MATCH_LEN_MIN 2
  3090. +
  3091. +/* Match length is encoded with 4, 5, or 10 bits.
  3092. + *
  3093. + * Length   Bits
  3094. + *  2-9      4 = Choice=0 + 3 bits
  3095. + * 10-17     5 = Choice=1 + Choice2=0 + 3 bits
  3096. + * 18-273   10 = Choice=1 + Choice2=1 + 8 bits
  3097. + */
  3098. +#define LEN_LOW_BITS 3
  3099. +#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
  3100. +#define LEN_MID_BITS 3
  3101. +#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
  3102. +#define LEN_HIGH_BITS 8
  3103. +#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
  3104. +#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
  3105. +
  3106. +/*
  3107. + * Maximum length of a match is 273 which is a result of the encoding
  3108. + * described above.
  3109. + */
  3110. +#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
  3111. +
  3112. +/*
  3113. + * Different sets of probabilities are used for match distances that have
  3114. + * very short match length: Lengths of 2, 3, and 4 bytes have a separate
  3115. + * set of probabilities for each length. The matches with longer length
  3116. + * use a shared set of probabilities.
  3117. + */
  3118. +#define DIST_STATES 4
  3119. +
  3120. +/*
  3121. + * Get the index of the appropriate probability array for decoding
  3122. + * the distance slot.
  3123. + */
  3124. +static inline uint32_t INIT lzma_get_dist_state(uint32_t len)
  3125. +{
  3126. +       return len < DIST_STATES + MATCH_LEN_MIN
  3127. +                       ? len - MATCH_LEN_MIN : DIST_STATES - 1;
  3128. +}
  3129. +
  3130. +/*
  3131. + * The highest two bits of a 32-bit match distance are encoded using six bits.
  3132. + * This six-bit value is called a distance slot. This way encoding a 32-bit
  3133. + * value takes 6-36 bits, larger values taking more bits.
  3134. + */
  3135. +#define DIST_SLOT_BITS 6
  3136. +#define DIST_SLOTS (1 << DIST_SLOT_BITS)
  3137. +
  3138. +/* Match distances up to 127 are fully encoded using probabilities. Since
  3139. + * the highest two bits (distance slot) are always encoded using six bits,
  3140. + * the distances 0-3 don't need any additional bits to encode, since the
  3141. + * distance slot itself is the same as the actual distance. DIST_MODEL_START
  3142. + * indicates the first distance slot where at least one additional bit is
  3143. + * needed.
  3144. + */
  3145. +#define DIST_MODEL_START 4
  3146. +
  3147. +/*
  3148. + * Match distances greater than 127 are encoded in three pieces:
  3149. + *   - distance slot: the highest two bits
  3150. + *   - direct bits: 2-26 bits below the highest two bits
  3151. + *   - alignment bits: four lowest bits
  3152. + *
  3153. + * Direct bits don't use any probabilities.
  3154. + *
  3155. + * The distance slot value of 14 is for distances 128-191.
  3156. + */
  3157. +#define DIST_MODEL_END 14
  3158. +
  3159. +/* Distance slots that indicate a distance <= 127. */
  3160. +#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
  3161. +#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
  3162. +
  3163. +/*
  3164. + * For match distances greater than 127, only the highest two bits and the
  3165. + * lowest four bits (alignment) is encoded using probabilities.
  3166. + */
  3167. +#define ALIGN_BITS 4
  3168. +#define ALIGN_SIZE (1 << ALIGN_BITS)
  3169. +#define ALIGN_MASK (ALIGN_SIZE - 1)
  3170. +
  3171. +/* Total number of all probability variables */
  3172. +#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
  3173. +
  3174. +/*
  3175. + * LZMA remembers the four most recent match distances. Reusing these
  3176. + * distances tends to take less space than re-encoding the actual
  3177. + * distance value.
  3178. + */
  3179. +#define REPS 4
  3180. +
  3181. +#endif
  3182. diff --git a/xen/common/xz/private.h b/xen/common/xz/private.h
  3183. new file mode 100644
  3184. --- /dev/null
  3185. +++ b/xen/common/xz/private.h
  3186. @@ -0,0 +1,271 @@
  3187. +/*
  3188. + * Private includes and definitions
  3189. + *
  3190. + * Author: Lasse Collin <lasse.collin@tukaani.org>
  3191. + *
  3192. + * This file has been put into the public domain.
  3193. + * You can do whatever you want with this file.
  3194. + */
  3195. +
  3196. +#ifndef XZ_PRIVATE_H
  3197. +#define XZ_PRIVATE_H
  3198. +
  3199. +#include <xen/kernel.h>
  3200. +#include <asm/byteorder.h>
  3201. +#define get_le32(p) le32_to_cpup((const uint32_t *)(p))
  3202. +
  3203. +#if 1 /* ndef CONFIG_??? */
  3204. +static inline u32 INIT get_unaligned_le32(void *p)
  3205. +{
  3206. +       return le32_to_cpup(p);
  3207. +}
  3208. +
  3209. +static inline void INIT put_unaligned_le32(u32 val, void *p)
  3210. +{
  3211. +       *(__force __le32*)p = cpu_to_le32(val);
  3212. +}
  3213. +#else
  3214. +#include <asm/unaligned.h>
  3215. +
  3216. +static inline u32 INIT get_unaligned_le32(void *p)
  3217. +{
  3218. +       return le32_to_cpu(__get_unaligned(p, 4));
  3219. +}
  3220. +
  3221. +static inline void INIT put_unaligned_le32(u32 val, void *p)
  3222. +{
  3223. +       __put_unaligned(cpu_to_le32(val), p, 4);
  3224. +}
  3225. +#endif
  3226. +
  3227. +#define false 0
  3228. +#define true 1
  3229. +
  3230. +/**
  3231. + * enum xz_mode - Operation mode
  3232. + *
  3233. + * @XZ_SINGLE:              Single-call mode. This uses less RAM than
  3234. + *                          than multi-call modes, because the LZMA2
  3235. + *                          dictionary doesn't need to be allocated as
  3236. + *                          part of the decoder state. All required data
  3237. + *                          structures are allocated at initialization,
  3238. + *                          so xz_dec_run() cannot return XZ_MEM_ERROR.
  3239. + * @XZ_PREALLOC:            Multi-call mode with preallocated LZMA2
  3240. + *                          dictionary buffer. All data structures are
  3241. + *                          allocated at initialization, so xz_dec_run()
  3242. + *                          cannot return XZ_MEM_ERROR.
  3243. + * @XZ_DYNALLOC:            Multi-call mode. The LZMA2 dictionary is
  3244. + *                          allocated once the required size has been
  3245. + *                          parsed from the stream headers. If the
  3246. + *                          allocation fails, xz_dec_run() will return
  3247. + *                          XZ_MEM_ERROR.
  3248. + *
  3249. + * It is possible to enable support only for a subset of the above
  3250. + * modes at compile time by defining XZ_DEC_SINGLE, XZ_DEC_PREALLOC,
  3251. + * or XZ_DEC_DYNALLOC. The xz_dec kernel module is always compiled
  3252. + * with support for all operation modes, but the preboot code may
  3253. + * be built with fewer features to minimize code size.
  3254. + */
  3255. +enum xz_mode {
  3256. +       XZ_SINGLE,
  3257. +       XZ_PREALLOC,
  3258. +       XZ_DYNALLOC
  3259. +};
  3260. +
  3261. +/**
  3262. + * enum xz_ret - Return codes
  3263. + * @XZ_OK:                  Everything is OK so far. More input or more
  3264. + *                          output space is required to continue. This
  3265. + *                          return code is possible only in multi-call mode
  3266. + *                          (XZ_PREALLOC or XZ_DYNALLOC).
  3267. + * @XZ_STREAM_END:          Operation finished successfully.
  3268. + * @XZ_UNSUPPORTED_CHECK:   Integrity check type is not supported. Decoding
  3269. + *                          is still possible in multi-call mode by simply
  3270. + *                          calling xz_dec_run() again.
  3271. + *                          Note that this return value is used only if
  3272. + *                          XZ_DEC_ANY_CHECK was defined at build time,
  3273. + *                          which is not used in the kernel. Unsupported
  3274. + *                          check types return XZ_OPTIONS_ERROR if
  3275. + *                          XZ_DEC_ANY_CHECK was not defined at build time.
  3276. + * @XZ_MEM_ERROR:           Allocating memory failed. This return code is
  3277. + *                          possible only if the decoder was initialized
  3278. + *                          with XZ_DYNALLOC. The amount of memory that was
  3279. + *                          tried to be allocated was no more than the
  3280. + *                          dict_max argument given to xz_dec_init().
  3281. + * @XZ_MEMLIMIT_ERROR:      A bigger LZMA2 dictionary would be needed than
  3282. + *                          allowed by the dict_max argument given to
  3283. + *                          xz_dec_init(). This return value is possible
  3284. + *                          only in multi-call mode (XZ_PREALLOC or
  3285. + *                          XZ_DYNALLOC); the single-call mode (XZ_SINGLE)
  3286. + *                          ignores the dict_max argument.
  3287. + * @XZ_FORMAT_ERROR:        File format was not recognized (wrong magic
  3288. + *                          bytes).
  3289. + * @XZ_OPTIONS_ERROR:       This implementation doesn't support the requested
  3290. + *                          compression options. In the decoder this means
  3291. + *                          that the header CRC32 matches, but the header
  3292. + *                          itself specifies something that we don't support.
  3293. + * @XZ_DATA_ERROR:          Compressed data is corrupt.
  3294. + * @XZ_BUF_ERROR:           Cannot make any progress. Details are slightly
  3295. + *                          different between multi-call and single-call
  3296. + *                          mode; more information below.
  3297. + *
  3298. + * In multi-call mode, XZ_BUF_ERROR is returned when two consecutive calls
  3299. + * to XZ code cannot consume any input and cannot produce any new output.
  3300. + * This happens when there is no new input available, or the output buffer
  3301. + * is full while at least one output byte is still pending. Assuming your
  3302. + * code is not buggy, you can get this error only when decoding a compressed
  3303. + * stream that is truncated or otherwise corrupt.
  3304. + *
  3305. + * In single-call mode, XZ_BUF_ERROR is returned only when the output buffer
  3306. + * is too small or the compressed input is corrupt in a way that makes the
  3307. + * decoder produce more output than the caller expected. When it is
  3308. + * (relatively) clear that the compressed input is truncated, XZ_DATA_ERROR
  3309. + * is used instead of XZ_BUF_ERROR.
  3310. + */
  3311. +enum xz_ret {
  3312. +       XZ_OK,
  3313. +       XZ_STREAM_END,
  3314. +       XZ_UNSUPPORTED_CHECK,
  3315. +       XZ_MEM_ERROR,
  3316. +       XZ_MEMLIMIT_ERROR,
  3317. +       XZ_FORMAT_ERROR,
  3318. +       XZ_OPTIONS_ERROR,
  3319. +       XZ_DATA_ERROR,
  3320. +       XZ_BUF_ERROR
  3321. +};
  3322. +
  3323. +/**
  3324. + * struct xz_buf - Passing input and output buffers to XZ code
  3325. + * @in:         Beginning of the input buffer. This may be NULL if and only
  3326. + *              if in_pos is equal to in_size.
  3327. + * @in_pos:     Current position in the input buffer. This must not exceed
  3328. + *              in_size.
  3329. + * @in_size:    Size of the input buffer
  3330. + * @out:        Beginning of the output buffer. This may be NULL if and only
  3331. + *              if out_pos is equal to out_size.
  3332. + * @out_pos:    Current position in the output buffer. This must not exceed
  3333. + *              out_size.
  3334. + * @out_size:   Size of the output buffer
  3335. + *
  3336. + * Only the contents of the output buffer from out[out_pos] onward, and
  3337. + * the variables in_pos and out_pos are modified by the XZ code.
  3338. + */
  3339. +struct xz_buf {
  3340. +       const uint8_t *in;
  3341. +       size_t in_pos;
  3342. +       size_t in_size;
  3343. +
  3344. +       uint8_t *out;
  3345. +       size_t out_pos;
  3346. +       size_t out_size;
  3347. +};
  3348. +
  3349. +/**
  3350. + * struct xz_dec - Opaque type to hold the XZ decoder state
  3351. + */
  3352. +struct xz_dec;
  3353. +
  3354. +/* If no specific decoding mode is requested, enable support for all modes. */
  3355. +#if !defined(XZ_DEC_SINGLE) && !defined(XZ_DEC_PREALLOC) \
  3356. +               && !defined(XZ_DEC_DYNALLOC)
  3357. +#      define XZ_DEC_SINGLE
  3358. +#      define XZ_DEC_PREALLOC
  3359. +#      define XZ_DEC_DYNALLOC
  3360. +#endif
  3361. +
  3362. +/*
  3363. + * The DEC_IS_foo(mode) macros are used in "if" statements. If only some
  3364. + * of the supported modes are enabled, these macros will evaluate to true or
  3365. + * false at compile time and thus allow the compiler to omit unneeded code.
  3366. + */
  3367. +#ifdef XZ_DEC_SINGLE
  3368. +#      define DEC_IS_SINGLE(mode) ((mode) == XZ_SINGLE)
  3369. +#else
  3370. +#      define DEC_IS_SINGLE(mode) (false)
  3371. +#endif
  3372. +
  3373. +#ifdef XZ_DEC_PREALLOC
  3374. +#      define DEC_IS_PREALLOC(mode) ((mode) == XZ_PREALLOC)
  3375. +#else
  3376. +#      define DEC_IS_PREALLOC(mode) (false)
  3377. +#endif
  3378. +
  3379. +#ifdef XZ_DEC_DYNALLOC
  3380. +#      define DEC_IS_DYNALLOC(mode) ((mode) == XZ_DYNALLOC)
  3381. +#else
  3382. +#      define DEC_IS_DYNALLOC(mode) (false)
  3383. +#endif
  3384. +
  3385. +#if !defined(XZ_DEC_SINGLE)
  3386. +#      define DEC_IS_MULTI(mode) (true)
  3387. +#elif defined(XZ_DEC_PREALLOC) || defined(XZ_DEC_DYNALLOC)
  3388. +#      define DEC_IS_MULTI(mode) ((mode) != XZ_SINGLE)
  3389. +#else
  3390. +#      define DEC_IS_MULTI(mode) (false)
  3391. +#endif
  3392. +
  3393. +/*
  3394. + * If any of the BCJ filter decoders are wanted, define XZ_DEC_BCJ.
  3395. + * XZ_DEC_BCJ is used to enable generic support for BCJ decoders.
  3396. + */
  3397. +#ifndef XZ_DEC_BCJ
  3398. +#      if defined(XZ_DEC_X86) || defined(XZ_DEC_POWERPC) \
  3399. +                       || defined(XZ_DEC_IA64) || defined(XZ_DEC_ARM) \
  3400. +                       || defined(XZ_DEC_ARM) || defined(XZ_DEC_ARMTHUMB) \
  3401. +                       || defined(XZ_DEC_SPARC)
  3402. +#              define XZ_DEC_BCJ
  3403. +#      endif
  3404. +#endif
  3405. +
  3406. +/*
  3407. + * Allocate memory for LZMA2 decoder. xz_dec_lzma2_reset() must be used
  3408. + * before calling xz_dec_lzma2_run().
  3409. + */
  3410. +XZ_EXTERN struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode,
  3411. +                                                  uint32_t dict_max);
  3412. +
  3413. +/*
  3414. + * Decode the LZMA2 properties (one byte) and reset the decoder. Return
  3415. + * XZ_OK on success, XZ_MEMLIMIT_ERROR if the preallocated dictionary is not
  3416. + * big enough, and XZ_OPTIONS_ERROR if props indicates something that this
  3417. + * decoder doesn't support.
  3418. + */
  3419. +XZ_EXTERN enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s,
  3420. +                                        uint8_t props);
  3421. +
  3422. +/* Decode raw LZMA2 stream from b->in to b->out. */
  3423. +XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
  3424. +                                      struct xz_buf *b);
  3425. +
  3426. +/* Free the memory allocated for the LZMA2 decoder. */
  3427. +XZ_EXTERN void xz_dec_lzma2_end(struct xz_dec_lzma2 *s);
  3428. +
  3429. +#ifdef XZ_DEC_BCJ
  3430. +/*
  3431. + * Allocate memory for BCJ decoders. xz_dec_bcj_reset() must be used before
  3432. + * calling xz_dec_bcj_run().
  3433. + */
  3434. +XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool_t single_call);
  3435. +
  3436. +/*
  3437. + * Decode the Filter ID of a BCJ filter. This implementation doesn't
  3438. + * support custom start offsets, so no decoding of Filter Properties
  3439. + * is needed. Returns XZ_OK if the given Filter ID is supported.
  3440. + * Otherwise XZ_OPTIONS_ERROR is returned.
  3441. + */
  3442. +XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id);
  3443. +
  3444. +/*
  3445. + * Decode raw BCJ + LZMA2 stream. This must be used only if there actually is
  3446. + * a BCJ filter in the chain. If the chain has only LZMA2, xz_dec_lzma2_run()
  3447. + * must be called directly.
  3448. + */
  3449. +XZ_EXTERN enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
  3450. +                                    struct xz_dec_lzma2 *lzma2,
  3451. +                                    struct xz_buf *b);
  3452. +
  3453. +/* Free the memory allocated for the BCJ filters. */
  3454. +#define xz_dec_bcj_end(s) free(s)
  3455. +#endif
  3456. +
  3457. +#endif
  3458. diff --git a/xen/common/xz/stream.h b/xen/common/xz/stream.h
  3459. new file mode 100644
  3460. --- /dev/null
  3461. +++ b/xen/common/xz/stream.h
  3462. @@ -0,0 +1,55 @@
  3463. +/*
  3464. + * Definitions for handling the .xz file format
  3465. + *
  3466. + * Author: Lasse Collin <lasse.collin@tukaani.org>
  3467. + *
  3468. + * This file has been put into the public domain.
  3469. + * You can do whatever you want with this file.
  3470. + */
  3471. +
  3472. +#ifndef XZ_STREAM_H
  3473. +#define XZ_STREAM_H
  3474. +
  3475. +/*
  3476. + * See the .xz file format specification at
  3477. + * http://tukaani.org/xz/xz-file-format.txt
  3478. + * to understand the container format.
  3479. + */
  3480. +
  3481. +#define STREAM_HEADER_SIZE 12
  3482. +
  3483. +#define HEADER_MAGIC "\3757zXZ"
  3484. +#define HEADER_MAGIC_SIZE 6
  3485. +
  3486. +#define FOOTER_MAGIC "YZ"
  3487. +#define FOOTER_MAGIC_SIZE 2
  3488. +
  3489. +/*
  3490. + * Variable-length integer can hold a 63-bit unsigned integer or a special
  3491. + * value indicating that the value is unknown.
  3492. + *
  3493. + * Experimental: vli_type can be defined to uint32_t to save a few bytes
  3494. + * in code size (no effect on speed). Doing so limits the uncompressed and
  3495. + * compressed size of the file to less than 256 MiB and may also weaken
  3496. + * error detection slightly.
  3497. + */
  3498. +typedef uint64_t vli_type;
  3499. +
  3500. +#define VLI_MAX ((vli_type)-1 / 2)
  3501. +#define VLI_UNKNOWN ((vli_type)-1)
  3502. +
  3503. +/* Maximum encoded size of a VLI */
  3504. +#define VLI_BYTES_MAX (sizeof(vli_type) * 8 / 7)
  3505. +
  3506. +/* Integrity Check types */
  3507. +enum xz_check {
  3508. +       XZ_CHECK_NONE = 0,
  3509. +       XZ_CHECK_CRC32 = 1,
  3510. +       XZ_CHECK_CRC64 = 4,
  3511. +       XZ_CHECK_SHA256 = 10
  3512. +};
  3513. +
  3514. +/* Maximum possible Check ID */
  3515. +#define XZ_CHECK_MAX 15
  3516. +
  3517. +#endif
  3518. diff --git a/xen/include/xen/decompress.h b/xen/include/xen/decompress.h
  3519. --- a/xen/include/xen/decompress.h
  3520. +++ b/xen/include/xen/decompress.h
  3521. @@ -31,7 +31,7 @@
  3522.   * dependent).
  3523.   */
  3524.  
  3525. -decompress_fn bunzip2, unlzma, unlzo;
  3526. +decompress_fn bunzip2, unxz, unlzma, unlzo;
  3527.  
  3528.  int decompress(void *inbuf, unsigned int len, void *outbuf);
clone this paste RAW Paste Data