API tools faq
paste
Guest User

dom0_xen_decompression.patch

a guest
Aug 8th, 2011
140
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Diff 96.88 KB | None | 0 0
raw download clone embed print report
  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);
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!