diff --git a/README b/README index a0495d7197f8..566d604c15b9 100644 --- a/README +++ b/README @@ -1,127 +1,163 @@ XZ Embedded =========== XZ Embedded is a relatively small, limited implementation of the .xz file format. Currently only decoding is implemented. XZ Embedded was written for use in the Linux kernel, but the code can be easily used in other environments too, including regular userspace - applications. + applications. See userspace/xzminidec.c for an example program. This README contains information that is useful only when the copy of XZ Embedded isn't part of the Linux kernel tree. You should also read linux/Documentation/xz.txt even if you aren't using XZ Embedded as part of Linux; information in that file is not repeated in this README. Compiling the Linux kernel module The xz_dec module depends on crc32 module, so make sure that you have it enabled (CONFIG_CRC32). Building the xz_dec and xz_dec_test modules without support for BCJ filters: cd linux/lib/xz make -C /path/to/kernel/source \ KCPPFLAGS=-I"$(pwd)/../../include" M="$(pwd)" \ CONFIG_XZ_DEC=m CONFIG_XZ_DEC_TEST=m Building the xz_dec and xz_dec_test modules with support for BCJ filters: cd linux/lib/xz make -C /path/to/kernel/source \ KCPPFLAGS=-I"$(pwd)/../../include" M="$(pwd)" \ CONFIG_XZ_DEC=m CONFIG_XZ_DEC_TEST=m CONFIG_XZ_DEC_BCJ=y \ CONFIG_XZ_DEC_X86=y CONFIG_XZ_DEC_POWERPC=y \ CONFIG_XZ_DEC_IA64=y CONFIG_XZ_DEC_ARM=y \ CONFIG_XZ_DEC_ARMTHUMB=y CONFIG_XZ_DEC_SPARC=y If you want only one or a few of the BCJ filters, omit the appropriate variables. CONFIG_XZ_DEC_BCJ=y is always required to build the support code shared between all BCJ filters. Most people don't need the xz_dec_test module. You can skip building it by omitting CONFIG_XZ_DEC_TEST=m from the make command line. Compiler requirements XZ Embedded should compile as either GNU-C89 (used in the Linux kernel) or with any C99 compiler. Getting the code to compile with non-GNU C89 compiler or a C++ compiler should be quite easy as long as there is a data type for unsigned 64-bit integer (or the code is modified not to support large files, which needs some more care than just using 32-bit integer instead of 64-bit). If you use GCC, try to use a recent version. For example, on x86-32, xz_dec_lzma2.c compiled with GCC 3.3.6 is 15-25 % slower than when compiled with GCC 4.3.3. Embedding into userspace applications To embed the XZ decoder, copy the following files into a single directory in your source code tree: linux/include/linux/xz.h linux/lib/xz/xz_crc32.c linux/lib/xz/xz_dec_lzma2.c linux/lib/xz/xz_dec_stream.c linux/lib/xz/xz_lzma2.h linux/lib/xz/xz_private.h linux/lib/xz/xz_stream.h userspace/xz_config.h Alternatively, xz.h may be placed into a different directory but then that directory must be in the compiler include path when compiling the .c files. Your code should use only the functions declared in xz.h. The rest of the .h files are meant only for internal use in XZ Embedded. You may want to modify xz_config.h to be more suitable for your build environment. Probably you should at least skim through it even if the default file works as is. +Integrity check support + + XZ Embedded always supports the integrity check types None and + CRC32. Support for CRC64 is optional. SHA-256 is currently not + supported in XZ Embedded although the .xz format does support it. + The xz tool from XZ Utils uses CRC64 by default, but CRC32 is usually + enough in embedded systems to keep the code size smaller. + + If you want support for CRC64, you need to copy linux/lib/xz/xz_crc64.c + into your application, and #define XZ_USE_CRC64 in xz_config.h or in + compiler flags. + + When using the internal CRC32 or CRC64, their lookup tables need to be + initialized with xz_crc32_init() and xz_crc64_init(), respectively. + See xz.h for details. + + To use external CRC32 or CRC64 code instead of the code from + xz_crc32.c or xz_crc64.c, the following #defines may be used + in xz_config.h or in compiler flags: + + #define XZ_INTERNAL_CRC32 0 + #define XZ_INTERNAL_CRC64 0 + + Then it is up to you to provide compatible xz_crc32() or xz_crc64() + functions. + + If the .xz file being decompressed uses an integrity check type that + isn't supported by XZ Embedded, it is treated as an error and the + file cannot be decompressed. For multi-call mode, this can be modified + by #defining XZ_DEC_ANY_CHECK. Then xz_dec_run() will return + XZ_UNSUPPORTED_CHECK when unsupported check type is detected. After + that decompression can be continued normally except that the + integrity check won't be verified. In single-call mode there's + no way to continue decoding, so XZ_DEC_ANY_CHECK is almost useless + in single-call mode. + BCJ filter support If you want support for one or more BCJ filters, you need to copy also linux/lib/xz/xz_dec_bcj.c into your application, and use appropriate #defines in xz_config.h or in compiler flags. You don't need these #defines in the code that just uses XZ Embedded via xz.h, but having them always #defined doesn't hurt either. #define Instruction set BCJ filter endianness XZ_DEC_X86 x86-32 or x86-64 Little endian only XZ_DEC_POWERPC PowerPC Big endian only XZ_DEC_IA64 Itanium (IA-64) Big or little endian XZ_DEC_ARM ARM Little endian only XZ_DEC_ARMTHUMB ARM-Thumb Little endian only XZ_DEC_SPARC SPARC Big or little endian While some architectures are (partially) bi-endian, the endianness setting doesn't change the endianness of the instructions on all architectures. That's why Itanium and SPARC filters work for both big and little endian executables (Itanium has little endian instructions and SPARC has big endian instructions). There currently is no filter for little endian PowerPC or big endian ARM or ARM-Thumb. Implementing filters for them can be considered if there is a need for such filters in real-world applications. Notes about shared libraries If you are including XZ Embedded into a shared library, you very probably should rename the xz_* functions to prevent symbol conflicts in case your library is linked against some other library or application that also has XZ Embedded in it (which may even be a different version of XZ Embedded). TODO: Provide an easy way to do this. Please don't create a shared library of XZ Embedded itself unless it is fine to rebuild everything depending on that shared library everytime you upgrade to a newer version of XZ Embedded. There are no API or ABI stability guarantees between different versions of XZ Embedded. diff --git a/linux/include/linux/xz.h b/linux/include/linux/xz.h index 810cb10a6357..0a4b38d33c2c 100644 --- a/linux/include/linux/xz.h +++ b/linux/include/linux/xz.h @@ -1,273 +1,304 @@ /* * XZ decompressor * * Authors: Lasse Collin * Igor Pavlov * * This file has been put into the public domain. * You can do whatever you want with this file. */ #ifndef XZ_H #define XZ_H #ifdef __KERNEL__ # include # include #else # include # include #endif #ifdef __cplusplus extern "C" { #endif /* In Linux, this is used to make extern functions static when needed. */ #ifndef XZ_EXTERN # define XZ_EXTERN extern #endif /** * enum xz_mode - Operation mode * * @XZ_SINGLE: Single-call mode. This uses less RAM than * than multi-call modes, because the LZMA2 * dictionary doesn't need to be allocated as * part of the decoder state. All required data * structures are allocated at initialization, * so xz_dec_run() cannot return XZ_MEM_ERROR. * @XZ_PREALLOC: Multi-call mode with preallocated LZMA2 * dictionary buffer. All data structures are * allocated at initialization, so xz_dec_run() * cannot return XZ_MEM_ERROR. * @XZ_DYNALLOC: Multi-call mode. The LZMA2 dictionary is * allocated once the required size has been * parsed from the stream headers. If the * allocation fails, xz_dec_run() will return * XZ_MEM_ERROR. * * It is possible to enable support only for a subset of the above * modes at compile time by defining XZ_DEC_SINGLE, XZ_DEC_PREALLOC, * or XZ_DEC_DYNALLOC. The xz_dec kernel module is always compiled * with support for all operation modes, but the preboot code may * be built with fewer features to minimize code size. */ enum xz_mode { XZ_SINGLE, XZ_PREALLOC, XZ_DYNALLOC }; /** * enum xz_ret - Return codes * @XZ_OK: Everything is OK so far. More input or more * output space is required to continue. This * return code is possible only in multi-call mode * (XZ_PREALLOC or XZ_DYNALLOC). * @XZ_STREAM_END: Operation finished successfully. * @XZ_UNSUPPORTED_CHECK: Integrity check type is not supported. Decoding * is still possible in multi-call mode by simply * calling xz_dec_run() again. * Note that this return value is used only if * XZ_DEC_ANY_CHECK was defined at build time, * which is not used in the kernel. Unsupported * check types return XZ_OPTIONS_ERROR if * XZ_DEC_ANY_CHECK was not defined at build time. * @XZ_MEM_ERROR: Allocating memory failed. This return code is * possible only if the decoder was initialized * with XZ_DYNALLOC. The amount of memory that was * tried to be allocated was no more than the * dict_max argument given to xz_dec_init(). * @XZ_MEMLIMIT_ERROR: A bigger LZMA2 dictionary would be needed than * allowed by the dict_max argument given to * xz_dec_init(). This return value is possible * only in multi-call mode (XZ_PREALLOC or * XZ_DYNALLOC); the single-call mode (XZ_SINGLE) * ignores the dict_max argument. * @XZ_FORMAT_ERROR: File format was not recognized (wrong magic * bytes). * @XZ_OPTIONS_ERROR: This implementation doesn't support the requested * compression options. In the decoder this means * that the header CRC32 matches, but the header * itself specifies something that we don't support. * @XZ_DATA_ERROR: Compressed data is corrupt. * @XZ_BUF_ERROR: Cannot make any progress. Details are slightly * different between multi-call and single-call * mode; more information below. * * In multi-call mode, XZ_BUF_ERROR is returned when two consecutive calls * to XZ code cannot consume any input and cannot produce any new output. * This happens when there is no new input available, or the output buffer * is full while at least one output byte is still pending. Assuming your * code is not buggy, you can get this error only when decoding a compressed * stream that is truncated or otherwise corrupt. * * In single-call mode, XZ_BUF_ERROR is returned only when the output buffer * is too small or the compressed input is corrupt in a way that makes the * decoder produce more output than the caller expected. When it is * (relatively) clear that the compressed input is truncated, XZ_DATA_ERROR * is used instead of XZ_BUF_ERROR. */ enum xz_ret { XZ_OK, XZ_STREAM_END, XZ_UNSUPPORTED_CHECK, XZ_MEM_ERROR, XZ_MEMLIMIT_ERROR, XZ_FORMAT_ERROR, XZ_OPTIONS_ERROR, XZ_DATA_ERROR, XZ_BUF_ERROR }; /** * struct xz_buf - Passing input and output buffers to XZ code * @in: Beginning of the input buffer. This may be NULL if and only * if in_pos is equal to in_size. * @in_pos: Current position in the input buffer. This must not exceed * in_size. * @in_size: Size of the input buffer * @out: Beginning of the output buffer. This may be NULL if and only * if out_pos is equal to out_size. * @out_pos: Current position in the output buffer. This must not exceed * out_size. * @out_size: Size of the output buffer * * Only the contents of the output buffer from out[out_pos] onward, and * the variables in_pos and out_pos are modified by the XZ code. */ struct xz_buf { const uint8_t *in; size_t in_pos; size_t in_size; uint8_t *out; size_t out_pos; size_t out_size; }; /** * struct xz_dec - Opaque type to hold the XZ decoder state */ struct xz_dec; /** * xz_dec_init() - Allocate and initialize a XZ decoder state * @mode: Operation mode * @dict_max: Maximum size of the LZMA2 dictionary (history buffer) for * multi-call decoding. This is ignored in single-call mode * (mode == XZ_SINGLE). LZMA2 dictionary is always 2^n bytes * or 2^n + 2^(n-1) bytes (the latter sizes are less common * in practice), so other values for dict_max don't make sense. * In the kernel, dictionary sizes of 64 KiB, 128 KiB, 256 KiB, * 512 KiB, and 1 MiB are probably the only reasonable values, * except for kernel and initramfs images where a bigger * dictionary can be fine and useful. * * Single-call mode (XZ_SINGLE): xz_dec_run() decodes the whole stream at * once. The caller must provide enough output space or the decoding will * fail. The output space is used as the dictionary buffer, which is why * there is no need to allocate the dictionary as part of the decoder's * internal state. * * Because the output buffer is used as the workspace, streams encoded using * a big dictionary are not a problem in single-call mode. It is enough that * the output buffer is big enough to hold the actual uncompressed data; it * can be smaller than the dictionary size stored in the stream headers. * * Multi-call mode with preallocated dictionary (XZ_PREALLOC): dict_max bytes * of memory is preallocated for the LZMA2 dictionary. This way there is no * risk that xz_dec_run() could run out of memory, since xz_dec_run() will * never allocate any memory. Instead, if the preallocated dictionary is too * small for decoding the given input stream, xz_dec_run() will return * XZ_MEMLIMIT_ERROR. Thus, it is important to know what kind of data will be * decoded to avoid allocating excessive amount of memory for the dictionary. * * Multi-call mode with dynamically allocated dictionary (XZ_DYNALLOC): * dict_max specifies the maximum allowed dictionary size that xz_dec_run() * may allocate once it has parsed the dictionary size from the stream * headers. This way excessive allocations can be avoided while still * limiting the maximum memory usage to a sane value to prevent running the * system out of memory when decompressing streams from untrusted sources. * * On success, xz_dec_init() returns a pointer to struct xz_dec, which is * ready to be used with xz_dec_run(). If memory allocation fails, * xz_dec_init() returns NULL. */ XZ_EXTERN struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max); /** * xz_dec_run() - Run the XZ decoder * @s: Decoder state allocated using xz_dec_init() * @b: Input and output buffers * * The possible return values depend on build options and operation mode. * See enum xz_ret for details. * * Note that if an error occurs in single-call mode (return value is not * XZ_STREAM_END), b->in_pos and b->out_pos are not modified and the * contents of the output buffer from b->out[b->out_pos] onward are * undefined. This is true even after XZ_BUF_ERROR, because with some filter * chains, there may be a second pass over the output buffer, and this pass * cannot be properly done if the output buffer is truncated. Thus, you * cannot give the single-call decoder a too small buffer and then expect to * get that amount valid data from the beginning of the stream. You must use * the multi-call decoder if you don't want to uncompress the whole stream. */ XZ_EXTERN enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b); /** * xz_dec_reset() - Reset an already allocated decoder state * @s: Decoder state allocated using xz_dec_init() * * This function can be used to reset the multi-call decoder state without * freeing and reallocating memory with xz_dec_end() and xz_dec_init(). * * In single-call mode, xz_dec_reset() is always called in the beginning of * xz_dec_run(). Thus, explicit call to xz_dec_reset() is useful only in * multi-call mode. */ XZ_EXTERN void xz_dec_reset(struct xz_dec *s); /** * xz_dec_end() - Free the memory allocated for the decoder state * @s: Decoder state allocated using xz_dec_init(). If s is NULL, * this function does nothing. */ XZ_EXTERN void xz_dec_end(struct xz_dec *s); /* * Standalone build (userspace build or in-kernel build for boot time use) * needs a CRC32 implementation. For normal in-kernel use, kernel's own * CRC32 module is used instead, and users of this module don't need to * care about the functions below. */ #ifndef XZ_INTERNAL_CRC32 # ifdef __KERNEL__ # define XZ_INTERNAL_CRC32 0 # else # define XZ_INTERNAL_CRC32 1 # endif #endif +/* + * If CRC64 support has been enabled with XZ_USE_CRC64, a CRC64 + * implementation is needed too. + */ +#ifndef XZ_USE_CRC64 +# undef XZ_INTERNAL_CRC64 +# define XZ_INTERNAL_CRC64 0 +#endif +#ifndef XZ_INTERNAL_CRC64 +# ifdef __KERNEL__ +# error Using CRC64 in the kernel has not been implemented. +# else +# define XZ_INTERNAL_CRC64 1 +# endif +#endif + #if XZ_INTERNAL_CRC32 /* * This must be called before any other xz_* function to initialize * the CRC32 lookup table. */ XZ_EXTERN void xz_crc32_init(void); /* * Update CRC32 value using the polynomial from IEEE-802.3. To start a new * calculation, the third argument must be zero. To continue the calculation, * the previously returned value is passed as the third argument. */ XZ_EXTERN uint32_t xz_crc32(const uint8_t *buf, size_t size, uint32_t crc); #endif +#if XZ_INTERNAL_CRC64 +/* + * This must be called before any other xz_* function (except xz_crc32_init()) + * to initialize the CRC64 lookup table. + */ +XZ_EXTERN void xz_crc64_init(void); + +/* + * Update CRC64 value using the polynomial from ECMA-182. To start a new + * calculation, the third argument must be zero. To continue the calculation, + * the previously returned value is passed as the third argument. + */ +XZ_EXTERN uint64_t xz_crc64(const uint8_t *buf, size_t size, uint64_t crc); +#endif + #ifdef __cplusplus } #endif #endif diff --git a/linux/lib/decompress_unxz.c b/linux/lib/decompress_unxz.c index cecd23df2b9a..9f34eb56854d 100644 --- a/linux/lib/decompress_unxz.c +++ b/linux/lib/decompress_unxz.c @@ -1,397 +1,397 @@ /* * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd * * Author: Lasse Collin * * This file has been put into the public domain. * You can do whatever you want with this file. */ /* * Important notes about in-place decompression * * At least on x86, the kernel is decompressed in place: the compressed data * is placed to the end of the output buffer, and the decompressor overwrites * most of the compressed data. There must be enough safety margin to * guarantee that the write position is always behind the read position. * * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below. * Note that the margin with XZ is bigger than with Deflate (gzip)! * * The worst case for in-place decompression is that the beginning of * the file is compressed extremely well, and the rest of the file is * uncompressible. Thus, we must look for worst-case expansion when the * compressor is encoding uncompressible data. * * The structure of the .xz file in case of a compresed kernel is as follows. * Sizes (as bytes) of the fields are in parenthesis. * * Stream Header (12) * Block Header: * Block Header (8-12) * Compressed Data (N) * Block Padding (0-3) * CRC32 (4) * Index (8-20) * Stream Footer (12) * * Normally there is exactly one Block, but let's assume that there are * 2-4 Blocks just in case. Because Stream Header and also Block Header * of the first Block don't make the decompressor produce any uncompressed * data, we can ignore them from our calculations. Block Headers of possible * additional Blocks have to be taken into account still. With these * assumptions, it is safe to assume that the total header overhead is * less than 128 bytes. * * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ * doesn't change the size of the data, it is enough to calculate the * safety margin for LZMA2. * * LZMA2 stores the data in chunks. Each chunk has a header whose size is * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that * the maximum chunk header size is 8 bytes. After the chunk header, there * may be up to 64 KiB of actual payload in the chunk. Often the payload is * quite a bit smaller though; to be safe, let's assume that an average * chunk has only 32 KiB of payload. * * The maximum uncompressed size of the payload is 2 MiB. The minimum * uncompressed size of the payload is in practice never less than the * payload size itself. The LZMA2 format would allow uncompressed size * to be less than the payload size, but no sane compressor creates such * files. LZMA2 supports storing uncompressible data in uncompressed form, * so there's never a need to create payloads whose uncompressed size is * smaller than the compressed size. * * The assumption, that the uncompressed size of the payload is never * smaller than the payload itself, is valid only when talking about * the payload as a whole. It is possible that the payload has parts where * the decompressor consumes more input than it produces output. Calculating * the worst case for this would be tricky. Instead of trying to do that, * let's simply make sure that the decompressor never overwrites any bytes * of the payload which it is currently reading. * * Now we have enough information to calculate the safety margin. We need * - 128 bytes for the .xz file format headers; * - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header * per chunk, each chunk having average payload size of 32 KiB); and * - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that * the decompressor never overwrites anything from the LZMA2 chunk * payload it is currently reading. * * We get the following formula: * * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536 * = 128 + (uncompressed_size >> 12) + 65536 * - * For comparision, according to arch/x86/boot/compressed/misc.c, the + * For comparison, according to arch/x86/boot/compressed/misc.c, the * equivalent formula for Deflate is this: * * safety_margin = 18 + (uncompressed_size >> 12) + 32768 * * Thus, when updating Deflate-only in-place kernel decompressor to * support XZ, the fixed overhead has to be increased from 18+32768 bytes * to 128+65536 bytes. */ /* * STATIC is defined to "static" if we are being built for kernel * decompression (pre-boot code). will define * STATIC to empty if it wasn't already defined. Since we will need to * know later if we are being used for kernel decompression, we define * XZ_PREBOOT here. */ #ifdef STATIC # define XZ_PREBOOT #endif #ifdef __KERNEL__ # include #endif #define XZ_EXTERN STATIC #ifndef XZ_PREBOOT # include # include #else /* * Use the internal CRC32 code instead of kernel's CRC32 module, which * is not available in early phase of booting. */ #define XZ_INTERNAL_CRC32 1 /* * For boot time use, we enable only the BCJ filter of the current * architecture or none if no BCJ filter is available for the architecture. */ #ifdef CONFIG_X86 # define XZ_DEC_X86 #endif #ifdef CONFIG_PPC # define XZ_DEC_POWERPC #endif #ifdef CONFIG_ARM # define XZ_DEC_ARM #endif #ifdef CONFIG_IA64 # define XZ_DEC_IA64 #endif #ifdef CONFIG_SPARC # define XZ_DEC_SPARC #endif /* * This will get the basic headers so that memeq() and others * can be defined. */ #include "xz/xz_private.h" /* * Replace the normal allocation functions with the versions from * . vfree() needs to support vfree(NULL) * when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it. * Workaround it here because the other decompressors don't need it. */ #undef kmalloc #undef kfree #undef vmalloc #undef vfree #define kmalloc(size, flags) malloc(size) #define kfree(ptr) free(ptr) #define vmalloc(size) malloc(size) #define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0) /* * FIXME: Not all basic memory functions are provided in architecture-specific * files (yet). We define our own versions here for now, but this should be * only a temporary solution. * * memeq and memzero are not used much and any remotely sane implementation * is fast enough. memcpy/memmove speed matters in multi-call mode, but * the kernel image is decompressed in single-call mode, in which only * memcpy speed can matter and only if there is a lot of uncompressible data * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the * functions below should just be kept small; it's probably not worth * optimizing for speed. */ #ifndef memeq static bool memeq(const void *a, const void *b, size_t size) { const uint8_t *x = a; const uint8_t *y = b; size_t i; for (i = 0; i < size; ++i) if (x[i] != y[i]) return false; return true; } #endif #ifndef memzero static void memzero(void *buf, size_t size) { uint8_t *b = buf; uint8_t *e = b + size; while (b != e) *b++ = '\0'; } #endif #ifndef memmove /* Not static to avoid a conflict with the prototype in the Linux headers. */ void *memmove(void *dest, const void *src, size_t size) { uint8_t *d = dest; const uint8_t *s = src; size_t i; if (d < s) { for (i = 0; i < size; ++i) d[i] = s[i]; } else if (d > s) { i = size; while (i-- > 0) d[i] = s[i]; } return dest; } #endif /* * Since we need memmove anyway, would use it as memcpy too. * Commented out for now to avoid breaking things. */ /* #ifndef memcpy # define memcpy memmove #endif */ #include "xz/xz_crc32.c" #include "xz/xz_dec_stream.c" #include "xz/xz_dec_lzma2.c" #include "xz/xz_dec_bcj.c" #endif /* XZ_PREBOOT */ /* Size of the input and output buffers in multi-call mode */ #define XZ_IOBUF_SIZE 4096 /* * This function implements the API defined in . * * This wrapper will automatically choose single-call or multi-call mode * of the native XZ decoder API. The single-call mode can be used only when * both input and output buffers are available as a single chunk, i.e. when * fill() and flush() won't be used. */ STATIC int INIT unxz(unsigned char *in, int in_size, int (*fill)(void *dest, unsigned int size), int (*flush)(void *src, unsigned int size), unsigned char *out, int *in_used, void (*error)(char *x)) { struct xz_buf b; struct xz_dec *s; enum xz_ret ret; bool must_free_in = false; #if XZ_INTERNAL_CRC32 xz_crc32_init(); #endif if (in_used != NULL) *in_used = 0; if (fill == NULL && flush == NULL) s = xz_dec_init(XZ_SINGLE, 0); else s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1); if (s == NULL) goto error_alloc_state; if (flush == NULL) { b.out = out; b.out_size = (size_t)-1; } else { b.out_size = XZ_IOBUF_SIZE; b.out = malloc(XZ_IOBUF_SIZE); if (b.out == NULL) goto error_alloc_out; } if (in == NULL) { must_free_in = true; in = malloc(XZ_IOBUF_SIZE); if (in == NULL) goto error_alloc_in; } b.in = in; b.in_pos = 0; b.in_size = in_size; b.out_pos = 0; if (fill == NULL && flush == NULL) { ret = xz_dec_run(s, &b); } else { do { if (b.in_pos == b.in_size && fill != NULL) { if (in_used != NULL) *in_used += b.in_pos; b.in_pos = 0; in_size = fill(in, XZ_IOBUF_SIZE); if (in_size < 0) { /* * This isn't an optimal error code * but it probably isn't worth making * a new one either. */ ret = XZ_BUF_ERROR; break; } b.in_size = in_size; } ret = xz_dec_run(s, &b); if (flush != NULL && (b.out_pos == b.out_size || (ret != XZ_OK && b.out_pos > 0))) { /* * Setting ret here may hide an error * returned by xz_dec_run(), but probably * it's not too bad. */ if (flush(b.out, b.out_pos) != (int)b.out_pos) ret = XZ_BUF_ERROR; b.out_pos = 0; } } while (ret == XZ_OK); if (must_free_in) free(in); if (flush != NULL) free(b.out); } if (in_used != NULL) *in_used += b.in_pos; xz_dec_end(s); switch (ret) { case XZ_STREAM_END: return 0; case XZ_MEM_ERROR: /* This can occur only in multi-call mode. */ error("XZ decompressor ran out of memory"); break; case XZ_FORMAT_ERROR: error("Input is not in the XZ format (wrong magic bytes)"); break; case XZ_OPTIONS_ERROR: error("Input was encoded with settings that are not " "supported by this XZ decoder"); break; case XZ_DATA_ERROR: case XZ_BUF_ERROR: error("XZ-compressed data is corrupt"); break; default: error("Bug in the XZ decompressor"); break; } return -1; error_alloc_in: if (flush != NULL) free(b.out); error_alloc_out: xz_dec_end(s); error_alloc_state: error("XZ decompressor ran out of memory"); return -1; } /* * This macro is used by architecture-specific files to decompress * the kernel image. */ #define decompress unxz diff --git a/linux/lib/xz/Kconfig b/linux/lib/xz/Kconfig index 60a6088d0e5e..08837db52d94 100644 --- a/linux/lib/xz/Kconfig +++ b/linux/lib/xz/Kconfig @@ -1,59 +1,57 @@ config XZ_DEC tristate "XZ decompression support" select CRC32 help LZMA2 compression algorithm and BCJ filters are supported using the .xz file format as the container. For integrity checking, CRC32 is supported. See Documentation/xz.txt for more information. +if XZ_DEC + config XZ_DEC_X86 - bool "x86 BCJ filter decoder" if EXPERT - default y - depends on XZ_DEC + bool "x86 BCJ filter decoder" + default y if X86 select XZ_DEC_BCJ config XZ_DEC_POWERPC - bool "PowerPC BCJ filter decoder" if EXPERT - default y - depends on XZ_DEC + bool "PowerPC BCJ filter decoder" + default y if PPC select XZ_DEC_BCJ config XZ_DEC_IA64 - bool "IA-64 BCJ filter decoder" if EXPERT - default y - depends on XZ_DEC + bool "IA-64 BCJ filter decoder" + default y if IA64 select XZ_DEC_BCJ config XZ_DEC_ARM - bool "ARM BCJ filter decoder" if EXPERT - default y - depends on XZ_DEC + bool "ARM BCJ filter decoder" + default y if ARM select XZ_DEC_BCJ config XZ_DEC_ARMTHUMB - bool "ARM-Thumb BCJ filter decoder" if EXPERT - default y - depends on XZ_DEC + bool "ARM-Thumb BCJ filter decoder" + default y if (ARM && ARM_THUMB) select XZ_DEC_BCJ config XZ_DEC_SPARC - bool "SPARC BCJ filter decoder" if EXPERT - default y - depends on XZ_DEC + bool "SPARC BCJ filter decoder" + default y if SPARC select XZ_DEC_BCJ +endif + config XZ_DEC_BCJ bool default n config XZ_DEC_TEST tristate "XZ decompressor tester" default n depends on XZ_DEC help This allows passing .xz files to the in-kernel XZ decoder via a character special file. It calculates CRC32 of the decompressed data and writes diagnostics to the system log. Unless you are developing the XZ decoder, you don't need this and should say N. diff --git a/linux/lib/xz/xz_crc64.c b/linux/lib/xz/xz_crc64.c new file mode 100644 index 000000000000..ca1caee899ae --- /dev/null +++ b/linux/lib/xz/xz_crc64.c @@ -0,0 +1,50 @@ +/* + * CRC64 using the polynomial from ECMA-182 + * + * This file is similar to xz_crc32.c. See the comments there. + * + * Authors: Lasse Collin + * Igor Pavlov + * + * This file has been put into the public domain. + * You can do whatever you want with this file. + */ + +#include "xz_private.h" + +#ifndef STATIC_RW_DATA +# define STATIC_RW_DATA static +#endif + +STATIC_RW_DATA uint64_t xz_crc64_table[256]; + +XZ_EXTERN void xz_crc64_init(void) +{ + const uint64_t poly = 0xC96C5795D7870F42; + + uint32_t i; + uint32_t j; + uint64_t r; + + for (i = 0; i < 256; ++i) { + r = i; + for (j = 0; j < 8; ++j) + r = (r >> 1) ^ (poly & ~((r & 1) - 1)); + + xz_crc64_table[i] = r; + } + + return; +} + +XZ_EXTERN uint64_t xz_crc64(const uint8_t *buf, size_t size, uint64_t crc) +{ + crc = ~crc; + + while (size != 0) { + crc = xz_crc64_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8); + --size; + } + + return ~crc; +} diff --git a/linux/lib/xz/xz_dec_stream.c b/linux/lib/xz/xz_dec_stream.c index ac809b1e64f7..d6525506a1ed 100644 --- a/linux/lib/xz/xz_dec_stream.c +++ b/linux/lib/xz/xz_dec_stream.c @@ -1,821 +1,847 @@ /* * .xz Stream decoder * * Author: Lasse Collin * * This file has been put into the public domain. * You can do whatever you want with this file. */ #include "xz_private.h" #include "xz_stream.h" +#ifdef XZ_USE_CRC64 +# define IS_CRC64(check_type) ((check_type) == XZ_CHECK_CRC64) +#else +# define IS_CRC64(check_type) false +#endif + /* Hash used to validate the Index field */ struct xz_dec_hash { vli_type unpadded; vli_type uncompressed; uint32_t crc32; }; struct xz_dec { /* Position in dec_main() */ enum { SEQ_STREAM_HEADER, SEQ_BLOCK_START, SEQ_BLOCK_HEADER, SEQ_BLOCK_UNCOMPRESS, SEQ_BLOCK_PADDING, SEQ_BLOCK_CHECK, SEQ_INDEX, SEQ_INDEX_PADDING, SEQ_INDEX_CRC32, SEQ_STREAM_FOOTER } sequence; /* Position in variable-length integers and Check fields */ uint32_t pos; /* Variable-length integer decoded by dec_vli() */ vli_type vli; /* Saved in_pos and out_pos */ size_t in_start; size_t out_start; +#ifdef XZ_USE_CRC64 + /* CRC32 or CRC64 value in Block or CRC32 value in Index */ + uint64_t crc; +#else /* CRC32 value in Block or Index */ - uint32_t crc32; + uint32_t crc; +#endif /* Type of the integrity check calculated from uncompressed data */ enum xz_check check_type; /* Operation mode */ enum xz_mode mode; /* * True if the next call to xz_dec_run() is allowed to return * XZ_BUF_ERROR. */ bool allow_buf_error; /* Information stored in Block Header */ struct { /* * Value stored in the Compressed Size field, or * VLI_UNKNOWN if Compressed Size is not present. */ vli_type compressed; /* * Value stored in the Uncompressed Size field, or * VLI_UNKNOWN if Uncompressed Size is not present. */ vli_type uncompressed; /* Size of the Block Header field */ uint32_t size; } block_header; /* Information collected when decoding Blocks */ struct { /* Observed compressed size of the current Block */ vli_type compressed; /* Observed uncompressed size of the current Block */ vli_type uncompressed; /* Number of Blocks decoded so far */ vli_type count; /* * Hash calculated from the Block sizes. This is used to * validate the Index field. */ struct xz_dec_hash hash; } block; /* Variables needed when verifying the Index field */ struct { /* Position in dec_index() */ enum { SEQ_INDEX_COUNT, SEQ_INDEX_UNPADDED, SEQ_INDEX_UNCOMPRESSED } sequence; /* Size of the Index in bytes */ vli_type size; /* Number of Records (matches block.count in valid files) */ vli_type count; /* * Hash calculated from the Records (matches block.hash in * valid files). */ struct xz_dec_hash hash; } index; /* * Temporary buffer needed to hold Stream Header, Block Header, * and Stream Footer. The Block Header is the biggest (1 KiB) * so we reserve space according to that. buf[] has to be aligned * to a multiple of four bytes; the size_t variables before it * should guarantee this. */ struct { size_t pos; size_t size; uint8_t buf[1024]; } temp; struct xz_dec_lzma2 *lzma2; #ifdef XZ_DEC_BCJ struct xz_dec_bcj *bcj; bool bcj_active; #endif }; #ifdef XZ_DEC_ANY_CHECK /* Sizes of the Check field with different Check IDs */ static const uint8_t check_sizes[16] = { 0, 4, 4, 4, 8, 8, 8, 16, 16, 16, 32, 32, 32, 64, 64, 64 }; #endif /* * Fill s->temp by copying data starting from b->in[b->in_pos]. Caller * must have set s->temp.pos to indicate how much data we are supposed * to copy into s->temp.buf. Return true once s->temp.pos has reached * s->temp.size. */ static bool fill_temp(struct xz_dec *s, struct xz_buf *b) { size_t copy_size = min_t(size_t, b->in_size - b->in_pos, s->temp.size - s->temp.pos); memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size); b->in_pos += copy_size; s->temp.pos += copy_size; if (s->temp.pos == s->temp.size) { s->temp.pos = 0; return true; } return false; } /* Decode a variable-length integer (little-endian base-128 encoding) */ static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in, size_t *in_pos, size_t in_size) { uint8_t byte; if (s->pos == 0) s->vli = 0; while (*in_pos < in_size) { byte = in[*in_pos]; ++*in_pos; s->vli |= (vli_type)(byte & 0x7F) << s->pos; if ((byte & 0x80) == 0) { /* Don't allow non-minimal encodings. */ if (byte == 0 && s->pos != 0) return XZ_DATA_ERROR; s->pos = 0; return XZ_STREAM_END; } s->pos += 7; if (s->pos == 7 * VLI_BYTES_MAX) return XZ_DATA_ERROR; } return XZ_OK; } /* * Decode the Compressed Data field from a Block. Update and validate * the observed compressed and uncompressed sizes of the Block so that * they don't exceed the values possibly stored in the Block Header * (validation assumes that no integer overflow occurs, since vli_type - * is normally uint64_t). Update the CRC32 if presence of the CRC32 - * field was indicated in Stream Header. + * is normally uint64_t). Update the CRC32 or CRC64 value if presence of + * the CRC32 or CRC64 field was indicated in Stream Header. * * Once the decoding is finished, validate that the observed sizes match * the sizes possibly stored in the Block Header. Update the hash and * Block count, which are later used to validate the Index field. */ static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b) { enum xz_ret ret; s->in_start = b->in_pos; s->out_start = b->out_pos; #ifdef XZ_DEC_BCJ if (s->bcj_active) ret = xz_dec_bcj_run(s->bcj, s->lzma2, b); else #endif ret = xz_dec_lzma2_run(s->lzma2, b); s->block.compressed += b->in_pos - s->in_start; s->block.uncompressed += b->out_pos - s->out_start; /* * There is no need to separately check for VLI_UNKNOWN, since * the observed sizes are always smaller than VLI_UNKNOWN. */ if (s->block.compressed > s->block_header.compressed || s->block.uncompressed > s->block_header.uncompressed) return XZ_DATA_ERROR; if (s->check_type == XZ_CHECK_CRC32) - s->crc32 = xz_crc32(b->out + s->out_start, - b->out_pos - s->out_start, s->crc32); + s->crc = xz_crc32(b->out + s->out_start, + b->out_pos - s->out_start, s->crc); +#ifdef XZ_USE_CRC64 + else if (s->check_type == XZ_CHECK_CRC64) + s->crc = xz_crc64(b->out + s->out_start, + b->out_pos - s->out_start, s->crc); +#endif if (ret == XZ_STREAM_END) { if (s->block_header.compressed != VLI_UNKNOWN && s->block_header.compressed != s->block.compressed) return XZ_DATA_ERROR; if (s->block_header.uncompressed != VLI_UNKNOWN && s->block_header.uncompressed != s->block.uncompressed) return XZ_DATA_ERROR; s->block.hash.unpadded += s->block_header.size + s->block.compressed; #ifdef XZ_DEC_ANY_CHECK s->block.hash.unpadded += check_sizes[s->check_type]; #else if (s->check_type == XZ_CHECK_CRC32) s->block.hash.unpadded += 4; + else if (IS_CRC64(s->check_type)) + s->block.hash.unpadded += 8; #endif s->block.hash.uncompressed += s->block.uncompressed; s->block.hash.crc32 = xz_crc32( (const uint8_t *)&s->block.hash, sizeof(s->block.hash), s->block.hash.crc32); ++s->block.count; } return ret; } /* Update the Index size and the CRC32 value. */ static void index_update(struct xz_dec *s, const struct xz_buf *b) { size_t in_used = b->in_pos - s->in_start; s->index.size += in_used; - s->crc32 = xz_crc32(b->in + s->in_start, in_used, s->crc32); + s->crc = xz_crc32(b->in + s->in_start, in_used, s->crc); } /* * Decode the Number of Records, Unpadded Size, and Uncompressed Size * fields from the Index field. That is, Index Padding and CRC32 are not * decoded by this function. * * This can return XZ_OK (more input needed), XZ_STREAM_END (everything * successfully decoded), or XZ_DATA_ERROR (input is corrupt). */ static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b) { enum xz_ret ret; do { ret = dec_vli(s, b->in, &b->in_pos, b->in_size); if (ret != XZ_STREAM_END) { index_update(s, b); return ret; } switch (s->index.sequence) { case SEQ_INDEX_COUNT: s->index.count = s->vli; /* * Validate that the Number of Records field * indicates the same number of Records as * there were Blocks in the Stream. */ if (s->index.count != s->block.count) return XZ_DATA_ERROR; s->index.sequence = SEQ_INDEX_UNPADDED; break; case SEQ_INDEX_UNPADDED: s->index.hash.unpadded += s->vli; s->index.sequence = SEQ_INDEX_UNCOMPRESSED; break; case SEQ_INDEX_UNCOMPRESSED: s->index.hash.uncompressed += s->vli; s->index.hash.crc32 = xz_crc32( (const uint8_t *)&s->index.hash, sizeof(s->index.hash), s->index.hash.crc32); --s->index.count; s->index.sequence = SEQ_INDEX_UNPADDED; break; } } while (s->index.count > 0); return XZ_STREAM_END; } /* - * Validate that the next four input bytes match the value of s->crc32. - * s->pos must be zero when starting to validate the first byte. + * Validate that the next four or eight input bytes match the value + * of s->crc. s->pos must be zero when starting to validate the first byte. + * The "bits" argument allows using the same code for both CRC32 and CRC64. */ -static enum xz_ret crc32_validate(struct xz_dec *s, struct xz_buf *b) +static enum xz_ret crc_validate(struct xz_dec *s, struct xz_buf *b, + uint32_t bits) { do { if (b->in_pos == b->in_size) return XZ_OK; - if (((s->crc32 >> s->pos) & 0xFF) != b->in[b->in_pos++]) + if (((s->crc >> s->pos) & 0xFF) != b->in[b->in_pos++]) return XZ_DATA_ERROR; s->pos += 8; - } while (s->pos < 32); + } while (s->pos < bits); - s->crc32 = 0; + s->crc = 0; s->pos = 0; return XZ_STREAM_END; } #ifdef XZ_DEC_ANY_CHECK /* * Skip over the Check field when the Check ID is not supported. * Returns true once the whole Check field has been skipped over. */ static bool check_skip(struct xz_dec *s, struct xz_buf *b) { while (s->pos < check_sizes[s->check_type]) { if (b->in_pos == b->in_size) return false; ++b->in_pos; ++s->pos; } s->pos = 0; return true; } #endif /* Decode the Stream Header field (the first 12 bytes of the .xz Stream). */ static enum xz_ret dec_stream_header(struct xz_dec *s) { if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE)) return XZ_FORMAT_ERROR; if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0) != get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2)) return XZ_DATA_ERROR; if (s->temp.buf[HEADER_MAGIC_SIZE] != 0) return XZ_OPTIONS_ERROR; /* - * Of integrity checks, we support only none (Check ID = 0) and - * CRC32 (Check ID = 1). However, if XZ_DEC_ANY_CHECK is defined, - * we will accept other check types too, but then the check won't - * be verified and a warning (XZ_UNSUPPORTED_CHECK) will be given. + * Of integrity checks, we support none (Check ID = 0), + * CRC32 (Check ID = 1), and optionally CRC64 (Check ID = 4). + * However, if XZ_DEC_ANY_CHECK is defined, we will accept other + * check types too, but then the check won't be verified and + * a warning (XZ_UNSUPPORTED_CHECK) will be given. */ s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1]; #ifdef XZ_DEC_ANY_CHECK if (s->check_type > XZ_CHECK_MAX) return XZ_OPTIONS_ERROR; - if (s->check_type > XZ_CHECK_CRC32) + if (s->check_type > XZ_CHECK_CRC32 && !IS_CRC64(s->check_type)) return XZ_UNSUPPORTED_CHECK; #else - if (s->check_type > XZ_CHECK_CRC32) + if (s->check_type > XZ_CHECK_CRC32 && !IS_CRC64(s->check_type)) return XZ_OPTIONS_ERROR; #endif return XZ_OK; } /* Decode the Stream Footer field (the last 12 bytes of the .xz Stream) */ static enum xz_ret dec_stream_footer(struct xz_dec *s) { if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE)) return XZ_DATA_ERROR; if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf)) return XZ_DATA_ERROR; /* * Validate Backward Size. Note that we never added the size of the * Index CRC32 field to s->index.size, thus we use s->index.size / 4 * instead of s->index.size / 4 - 1. */ if ((s->index.size >> 2) != get_le32(s->temp.buf + 4)) return XZ_DATA_ERROR; if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type) return XZ_DATA_ERROR; /* * Use XZ_STREAM_END instead of XZ_OK to be more convenient * for the caller. */ return XZ_STREAM_END; } /* Decode the Block Header and initialize the filter chain. */ static enum xz_ret dec_block_header(struct xz_dec *s) { enum xz_ret ret; /* * Validate the CRC32. We know that the temp buffer is at least * eight bytes so this is safe. */ s->temp.size -= 4; if (xz_crc32(s->temp.buf, s->temp.size, 0) != get_le32(s->temp.buf + s->temp.size)) return XZ_DATA_ERROR; s->temp.pos = 2; /* * Catch unsupported Block Flags. We support only one or two filters * in the chain, so we catch that with the same test. */ #ifdef XZ_DEC_BCJ if (s->temp.buf[1] & 0x3E) #else if (s->temp.buf[1] & 0x3F) #endif return XZ_OPTIONS_ERROR; /* Compressed Size */ if (s->temp.buf[1] & 0x40) { if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size) != XZ_STREAM_END) return XZ_DATA_ERROR; s->block_header.compressed = s->vli; } else { s->block_header.compressed = VLI_UNKNOWN; } /* Uncompressed Size */ if (s->temp.buf[1] & 0x80) { if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size) != XZ_STREAM_END) return XZ_DATA_ERROR; s->block_header.uncompressed = s->vli; } else { s->block_header.uncompressed = VLI_UNKNOWN; } #ifdef XZ_DEC_BCJ /* If there are two filters, the first one must be a BCJ filter. */ s->bcj_active = s->temp.buf[1] & 0x01; if (s->bcj_active) { if (s->temp.size - s->temp.pos < 2) return XZ_OPTIONS_ERROR; ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]); if (ret != XZ_OK) return ret; /* * We don't support custom start offset, * so Size of Properties must be zero. */ if (s->temp.buf[s->temp.pos++] != 0x00) return XZ_OPTIONS_ERROR; } #endif /* Valid Filter Flags always take at least two bytes. */ if (s->temp.size - s->temp.pos < 2) return XZ_DATA_ERROR; /* Filter ID = LZMA2 */ if (s->temp.buf[s->temp.pos++] != 0x21) return XZ_OPTIONS_ERROR; /* Size of Properties = 1-byte Filter Properties */ if (s->temp.buf[s->temp.pos++] != 0x01) return XZ_OPTIONS_ERROR; /* Filter Properties contains LZMA2 dictionary size. */ if (s->temp.size - s->temp.pos < 1) return XZ_DATA_ERROR; ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]); if (ret != XZ_OK) return ret; /* The rest must be Header Padding. */ while (s->temp.pos < s->temp.size) if (s->temp.buf[s->temp.pos++] != 0x00) return XZ_OPTIONS_ERROR; s->temp.pos = 0; s->block.compressed = 0; s->block.uncompressed = 0; return XZ_OK; } static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b) { enum xz_ret ret; /* * Store the start position for the case when we are in the middle * of the Index field. */ s->in_start = b->in_pos; while (true) { switch (s->sequence) { case SEQ_STREAM_HEADER: /* * Stream Header is copied to s->temp, and then * decoded from there. This way if the caller * gives us only little input at a time, we can * still keep the Stream Header decoding code * simple. Similar approach is used in many places * in this file. */ if (!fill_temp(s, b)) return XZ_OK; /* * If dec_stream_header() returns * XZ_UNSUPPORTED_CHECK, it is still possible * to continue decoding if working in multi-call * mode. Thus, update s->sequence before calling * dec_stream_header(). */ s->sequence = SEQ_BLOCK_START; ret = dec_stream_header(s); if (ret != XZ_OK) return ret; case SEQ_BLOCK_START: /* We need one byte of input to continue. */ if (b->in_pos == b->in_size) return XZ_OK; /* See if this is the beginning of the Index field. */ if (b->in[b->in_pos] == 0) { s->in_start = b->in_pos++; s->sequence = SEQ_INDEX; break; } /* * Calculate the size of the Block Header and * prepare to decode it. */ s->block_header.size = ((uint32_t)b->in[b->in_pos] + 1) * 4; s->temp.size = s->block_header.size; s->temp.pos = 0; s->sequence = SEQ_BLOCK_HEADER; case SEQ_BLOCK_HEADER: if (!fill_temp(s, b)) return XZ_OK; ret = dec_block_header(s); if (ret != XZ_OK) return ret; s->sequence = SEQ_BLOCK_UNCOMPRESS; case SEQ_BLOCK_UNCOMPRESS: ret = dec_block(s, b); if (ret != XZ_STREAM_END) return ret; s->sequence = SEQ_BLOCK_PADDING; case SEQ_BLOCK_PADDING: /* * Size of Compressed Data + Block Padding * must be a multiple of four. We don't need * s->block.compressed for anything else * anymore, so we use it here to test the size * of the Block Padding field. */ while (s->block.compressed & 3) { if (b->in_pos == b->in_size) return XZ_OK; if (b->in[b->in_pos++] != 0) return XZ_DATA_ERROR; ++s->block.compressed; } s->sequence = SEQ_BLOCK_CHECK; case SEQ_BLOCK_CHECK: if (s->check_type == XZ_CHECK_CRC32) { - ret = crc32_validate(s, b); + ret = crc_validate(s, b, 32); + if (ret != XZ_STREAM_END) + return ret; + } + else if (IS_CRC64(s->check_type)) { + ret = crc_validate(s, b, 64); if (ret != XZ_STREAM_END) return ret; } #ifdef XZ_DEC_ANY_CHECK else if (!check_skip(s, b)) { return XZ_OK; } #endif s->sequence = SEQ_BLOCK_START; break; case SEQ_INDEX: ret = dec_index(s, b); if (ret != XZ_STREAM_END) return ret; s->sequence = SEQ_INDEX_PADDING; case SEQ_INDEX_PADDING: while ((s->index.size + (b->in_pos - s->in_start)) & 3) { if (b->in_pos == b->in_size) { index_update(s, b); return XZ_OK; } if (b->in[b->in_pos++] != 0) return XZ_DATA_ERROR; } /* Finish the CRC32 value and Index size. */ index_update(s, b); /* Compare the hashes to validate the Index field. */ if (!memeq(&s->block.hash, &s->index.hash, sizeof(s->block.hash))) return XZ_DATA_ERROR; s->sequence = SEQ_INDEX_CRC32; case SEQ_INDEX_CRC32: - ret = crc32_validate(s, b); + ret = crc_validate(s, b, 32); if (ret != XZ_STREAM_END) return ret; s->temp.size = STREAM_HEADER_SIZE; s->sequence = SEQ_STREAM_FOOTER; case SEQ_STREAM_FOOTER: if (!fill_temp(s, b)) return XZ_OK; return dec_stream_footer(s); } } /* Never reached */ } /* * xz_dec_run() is a wrapper for dec_main() to handle some special cases in * multi-call and single-call decoding. * * In multi-call mode, we must return XZ_BUF_ERROR when it seems clear that we * are not going to make any progress anymore. This is to prevent the caller * from calling us infinitely when the input file is truncated or otherwise * corrupt. Since zlib-style API allows that the caller fills the input buffer * only when the decoder doesn't produce any new output, we have to be careful * to avoid returning XZ_BUF_ERROR too easily: XZ_BUF_ERROR is returned only * after the second consecutive call to xz_dec_run() that makes no progress. * * In single-call mode, if we couldn't decode everything and no error * occurred, either the input is truncated or the output buffer is too small. * Since we know that the last input byte never produces any output, we know * that if all the input was consumed and decoding wasn't finished, the file * must be corrupt. Otherwise the output buffer has to be too small or the * file is corrupt in a way that decoding it produces too big output. * * If single-call decoding fails, we reset b->in_pos and b->out_pos back to * their original values. This is because with some filter chains there won't * be any valid uncompressed data in the output buffer unless the decoding * actually succeeds (that's the price to pay of using the output buffer as * the workspace). */ XZ_EXTERN enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b) { size_t in_start; size_t out_start; enum xz_ret ret; if (DEC_IS_SINGLE(s->mode)) xz_dec_reset(s); in_start = b->in_pos; out_start = b->out_pos; ret = dec_main(s, b); if (DEC_IS_SINGLE(s->mode)) { if (ret == XZ_OK) ret = b->in_pos == b->in_size ? XZ_DATA_ERROR : XZ_BUF_ERROR; if (ret != XZ_STREAM_END) { b->in_pos = in_start; b->out_pos = out_start; } } else if (ret == XZ_OK && in_start == b->in_pos && out_start == b->out_pos) { if (s->allow_buf_error) ret = XZ_BUF_ERROR; s->allow_buf_error = true; } else { s->allow_buf_error = false; } return ret; } XZ_EXTERN struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max) { struct xz_dec *s = kmalloc(sizeof(*s), GFP_KERNEL); if (s == NULL) return NULL; s->mode = mode; #ifdef XZ_DEC_BCJ s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode)); if (s->bcj == NULL) goto error_bcj; #endif s->lzma2 = xz_dec_lzma2_create(mode, dict_max); if (s->lzma2 == NULL) goto error_lzma2; xz_dec_reset(s); return s; error_lzma2: #ifdef XZ_DEC_BCJ xz_dec_bcj_end(s->bcj); error_bcj: #endif kfree(s); return NULL; } XZ_EXTERN void xz_dec_reset(struct xz_dec *s) { s->sequence = SEQ_STREAM_HEADER; s->allow_buf_error = false; s->pos = 0; - s->crc32 = 0; + s->crc = 0; memzero(&s->block, sizeof(s->block)); memzero(&s->index, sizeof(s->index)); s->temp.pos = 0; s->temp.size = STREAM_HEADER_SIZE; } XZ_EXTERN void xz_dec_end(struct xz_dec *s) { if (s != NULL) { xz_dec_lzma2_end(s->lzma2); #ifdef XZ_DEC_BCJ xz_dec_bcj_end(s->bcj); #endif kfree(s); } } diff --git a/linux/scripts/xz_wrap.sh b/linux/scripts/xz_wrap.sh index 17a5798c29da..7a2d372f4885 100755 --- a/linux/scripts/xz_wrap.sh +++ b/linux/scripts/xz_wrap.sh @@ -1,23 +1,23 @@ #!/bin/sh # # This is a wrapper for xz to compress the kernel image using appropriate # compression options depending on the architecture. # # Author: Lasse Collin # # This file has been put into the public domain. # You can do whatever you want with this file. # BCJ= LZMA2OPTS= -case $ARCH in - x86|x86_64) BCJ=--x86 ;; +case $SRCARCH in + x86) BCJ=--x86 ;; powerpc) BCJ=--powerpc ;; ia64) BCJ=--ia64; LZMA2OPTS=pb=4 ;; arm) BCJ=--arm ;; sparc) BCJ=--sparc ;; esac exec xz --check=crc32 $BCJ --lzma2=$LZMA2OPTS,dict=32MiB diff --git a/userspace/Makefile b/userspace/Makefile index 9d1779905bd2..5bd6b282e252 100644 --- a/userspace/Makefile +++ b/userspace/Makefile @@ -1,48 +1,48 @@ # # Makefile # # Author: Lasse Collin # # This file has been put into the public domain. # You can do whatever you want with this file. # CC = gcc -std=gnu89 BCJ_CPPFLAGS = -DXZ_DEC_X86 -DXZ_DEC_POWERPC -DXZ_DEC_IA64 \ -DXZ_DEC_ARM -DXZ_DEC_ARMTHUMB -DXZ_DEC_SPARC -CPPFLAGS = -DXZ_DEC_ANY_CHECK +CPPFLAGS = -DXZ_USE_CRC64 -DXZ_DEC_ANY_CHECK CFLAGS = -ggdb3 -O2 -pedantic -Wall -Wextra RM = rm -f VPATH = ../linux/include/linux ../linux/lib/xz -COMMON_SRCS = xz_crc32.c xz_dec_stream.c xz_dec_lzma2.c xz_dec_bcj.c +COMMON_SRCS = xz_crc32.c xz_crc64.c xz_dec_stream.c xz_dec_lzma2.c xz_dec_bcj.c COMMON_OBJS = $(COMMON_SRCS:.c=.o) XZMINIDEC_OBJS = xzminidec.o BYTETEST_OBJS = bytetest.o BUFTEST_OBJS = buftest.o BOOTTEST_OBJS = boottest.o XZ_HEADERS = xz.h xz_private.h xz_stream.h xz_lzma2.h xz_config.h PROGRAMS = xzminidec bytetest buftest boottest ALL_CPPFLAGS = -I../linux/include/linux -I. $(BCJ_CPPFLAGS) $(CPPFLAGS) all: $(PROGRAMS) %.o: %.c $(XZ_HEADERS) $(CC) $(ALL_CPPFLAGS) $(CFLAGS) -c -o $@ $< xzminidec: $(COMMON_OBJS) $(XZMINIDEC_OBJS) $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $(COMMON_OBJS) $(XZMINIDEC_OBJS) bytetest: $(COMMON_OBJS) $(BYTETEST_OBJS) $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $(COMMON_OBJS) $(BYTETEST_OBJS) buftest: $(COMMON_OBJS) $(BUFTEST_OBJS) $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $(COMMON_OBJS) $(BUFTEST_OBJS) boottest: $(BOOTTEST_OBJS) $(COMMON_SRCS) $(CC) $(ALL_CPPFLAGS) $(CFLAGS) $(LDFLAGS) -o $@ $(BOOTTEST_OBJS) .PHONY: clean clean: -$(RM) $(COMMON_OBJS) $(XZMINIDEC_OBJS) $(BUFTEST_OBJS) \ $(BOOTTEST_OBJS) $(PROGRAMS) diff --git a/userspace/boottest.c b/userspace/boottest.c index f5bc28261ea6..1aef5ed69d11 100644 --- a/userspace/boottest.c +++ b/userspace/boottest.c @@ -1,93 +1,96 @@ /* * Test application for xz_boot.c * * Author: Lasse Collin * * This file has been put into the public domain. * You can do whatever you want with this file. */ #include #include #include #define STATIC static #define INIT static void error(/*const*/ char *msg) { fprintf(stderr, "%s\n", msg); } +/* Disable the CRC64 support even if it was enabled in the Makefile. */ +#undef XZ_USE_CRC64 + #include "../linux/lib/decompress_unxz.c" static uint8_t in[1024 * 1024]; static uint8_t out[1024 * 1024]; static int fill(void *buf, unsigned int size) { return fread(buf, 1, size, stdin); } static int flush(/*const*/ void *buf, unsigned int size) { return fwrite(buf, 1, size, stdout); } static void test_buf_to_buf(void) { size_t in_size; int ret; in_size = fread(in, 1, sizeof(in), stdin); ret = decompress(in, in_size, NULL, NULL, out, NULL, &error); /* fwrite(out, 1, FIXME, stdout); */ fprintf(stderr, "ret = %d\n", ret); } static void test_buf_to_cb(void) { size_t in_size; int in_used; int ret; in_size = fread(in, 1, sizeof(in), stdin); ret = decompress(in, in_size, NULL, &flush, NULL, &in_used, &error); fprintf(stderr, "ret = %d; in_used = %d\n", ret, in_used); } static void test_cb_to_cb(void) { int ret; ret = decompress(NULL, 0, &fill, &flush, NULL, NULL, &error); fprintf(stderr, "ret = %d\n", ret); } /* * Not used by Linux <= 2.6.37-rc4 and newer probably won't use it either, * but this kind of use case is still required to be supported by the API. */ static void test_cb_to_buf(void) { int in_used; int ret; ret = decompress(in, 0, &fill, NULL, out, &in_used, &error); /* fwrite(out, 1, FIXME, stdout); */ fprintf(stderr, "ret = %d; in_used = %d\n", ret, in_used); } int main(int argc, char **argv) { if (argc != 2) fprintf(stderr, "Usage: %s [bb|bc|cc|cb]\n", argv[0]); else if (strcmp(argv[1], "bb") == 0) test_buf_to_buf(); else if (strcmp(argv[1], "bc") == 0) test_buf_to_cb(); else if (strcmp(argv[1], "cc") == 0) test_cb_to_cb(); else if (strcmp(argv[1], "cb") == 0) test_cb_to_buf(); else fprintf(stderr, "Usage: %s [bb|bc|cc|cb]\n", argv[0]); return 0; } diff --git a/userspace/xzminidec.c b/userspace/bytetest.c similarity index 78% copy from userspace/xzminidec.c copy to userspace/bytetest.c index 2a039c6dea10..aa48b9b3edce 100644 --- a/userspace/xzminidec.c +++ b/userspace/bytetest.c @@ -1,132 +1,135 @@ /* - * Simple XZ decoder command line tool + * Lazy test for the case when the output size is known * * Author: Lasse Collin * * This file has been put into the public domain. * You can do whatever you want with this file. */ -/* - * This is really limited: Not all filters from .xz format are supported, - * only CRC32 is supported as the integrity check, and decoding of - * concatenated .xz streams is not supported. Thus, you may want to look - * at xzdec from XZ Utils if a few KiB bigger tool is not a problem. - */ - #include #include #include +#include #include "xz.h" -static uint8_t in[BUFSIZ]; +static uint8_t in[1]; static uint8_t out[BUFSIZ]; int main(int argc, char **argv) { struct xz_buf b; struct xz_dec *s; enum xz_ret ret; const char *msg; + size_t uncomp_size; - if (argc >= 2 && strcmp(argv[1], "--help") == 0) { - fputs("Uncompress a .xz file from stdin to stdout.\n" - "Arguments other than `--help' are ignored.\n", - stdout); - return 0; + if (argc != 2) { + fputs("Give uncompressed size as the argument", stderr); + return 1; } + uncomp_size = atoi(argv[1]); + xz_crc32_init(); /* * Support up to 64 MiB dictionary. The actually needed memory * is allocated once the headers have been parsed. */ s = xz_dec_init(XZ_DYNALLOC, 1 << 26); if (s == NULL) { msg = "Memory allocation failed\n"; goto error; } b.in = in; b.in_pos = 0; b.in_size = 0; b.out = out; b.out_pos = 0; - b.out_size = BUFSIZ; + b.out_size = uncomp_size < BUFSIZ ? uncomp_size : BUFSIZ; while (true) { if (b.in_pos == b.in_size) { b.in_size = fread(in, 1, sizeof(in), stdin); b.in_pos = 0; } ret = xz_dec_run(s, &b); if (b.out_pos == sizeof(out)) { if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos) { msg = "Write error\n"; goto error; } + uncomp_size -= b.out_pos; b.out_pos = 0; + b.out_size = uncomp_size < BUFSIZ + ? uncomp_size : BUFSIZ; } if (ret == XZ_OK) continue; #ifdef XZ_DEC_ANY_CHECK if (ret == XZ_UNSUPPORTED_CHECK) { fputs(argv[0], stderr); fputs(": ", stderr); fputs("Unsupported check; not verifying " "file integrity\n", stderr); continue; } #endif + if (uncomp_size != b.out_pos) { + msg = "Uncompressed size doesn't match\n"; + goto error; + } + if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos || fclose(stdout)) { msg = "Write error\n"; goto error; } switch (ret) { case XZ_STREAM_END: xz_dec_end(s); return 0; case XZ_MEM_ERROR: msg = "Memory allocation failed\n"; goto error; case XZ_MEMLIMIT_ERROR: msg = "Memory usage limit reached\n"; goto error; case XZ_FORMAT_ERROR: msg = "Not a .xz file\n"; goto error; case XZ_OPTIONS_ERROR: msg = "Unsupported options in the .xz headers\n"; goto error; case XZ_DATA_ERROR: case XZ_BUF_ERROR: msg = "File is corrupt\n"; goto error; default: msg = "Bug!\n"; goto error; } } error: xz_dec_end(s); fputs(argv[0], stderr); fputs(": ", stderr); fputs(msg, stderr); return 1; } diff --git a/userspace/xz_config.h b/userspace/xz_config.h index 71bb0293fe3d..eb9dac1a4bda 100644 --- a/userspace/xz_config.h +++ b/userspace/xz_config.h @@ -1,109 +1,124 @@ /* * Private includes and definitions for userspace use of XZ Embedded * * Author: Lasse Collin * * This file has been put into the public domain. * You can do whatever you want with this file. */ #ifndef XZ_CONFIG_H #define XZ_CONFIG_H +/* Uncomment to enable CRC64 support. */ +/* #define XZ_USE_CRC64 */ + /* Uncomment as needed to enable BCJ filter decoders. */ /* #define XZ_DEC_X86 */ /* #define XZ_DEC_POWERPC */ /* #define XZ_DEC_IA64 */ /* #define XZ_DEC_ARM */ /* #define XZ_DEC_ARMTHUMB */ /* #define XZ_DEC_SPARC */ -#include +/* + * MSVC doesn't support modern C but XZ Embedded is mostly C89 + * so these are enough. + */ +#ifdef _MSC_VER +typedef unsigned char bool; +# define true 1 +# define false 0 +# define inline __inline +#else +# include +#endif + #include #include #include "xz.h" #define kmalloc(size, flags) malloc(size) #define kfree(ptr) free(ptr) #define vmalloc(size) malloc(size) #define vfree(ptr) free(ptr) #define memeq(a, b, size) (memcmp(a, b, size) == 0) #define memzero(buf, size) memset(buf, 0, size) #ifndef min # define min(x, y) ((x) < (y) ? (x) : (y)) #endif #define min_t(type, x, y) min(x, y) /* * Some functions have been marked with __always_inline to keep the * performance reasonable even when the compiler is optimizing for * small code size. You may be able to save a few bytes by #defining * __always_inline to plain inline, but don't complain if the code * becomes slow. * * NOTE: System headers on GNU/Linux may #define this macro already, * so if you want to change it, you need to #undef it first. */ #ifndef __always_inline # ifdef __GNUC__ # define __always_inline \ inline __attribute__((__always_inline__)) # else # define __always_inline inline # endif #endif /* Inline functions to access unaligned unsigned 32-bit integers */ #ifndef get_unaligned_le32 static inline uint32_t get_unaligned_le32(const uint8_t *buf) { return (uint32_t)buf[0] | ((uint32_t)buf[1] << 8) | ((uint32_t)buf[2] << 16) | ((uint32_t)buf[3] << 24); } #endif #ifndef get_unaligned_be32 static inline uint32_t get_unaligned_be32(const uint8_t *buf) { return (uint32_t)(buf[0] << 24) | ((uint32_t)buf[1] << 16) | ((uint32_t)buf[2] << 8) | (uint32_t)buf[3]; } #endif #ifndef put_unaligned_le32 static inline void put_unaligned_le32(uint32_t val, uint8_t *buf) { buf[0] = (uint8_t)val; buf[1] = (uint8_t)(val >> 8); buf[2] = (uint8_t)(val >> 16); buf[3] = (uint8_t)(val >> 24); } #endif #ifndef put_unaligned_be32 static inline void put_unaligned_be32(uint32_t val, uint8_t *buf) { buf[0] = (uint8_t)(val >> 24); buf[1] = (uint8_t)(val >> 16); buf[2] = (uint8_t)(val >> 8); buf[3] = (uint8_t)val; } #endif /* * Use get_unaligned_le32() also for aligned access for simplicity. On * little endian systems, #define get_le32(ptr) (*(const uint32_t *)(ptr)) * could save a few bytes in code size. */ #ifndef get_le32 # define get_le32 get_unaligned_le32 #endif #endif diff --git a/userspace/xzminidec.c b/userspace/xzminidec.c index 2a039c6dea10..ba07413125a1 100644 --- a/userspace/xzminidec.c +++ b/userspace/xzminidec.c @@ -1,132 +1,135 @@ /* * Simple XZ decoder command line tool * * Author: Lasse Collin * * This file has been put into the public domain. * You can do whatever you want with this file. */ /* * This is really limited: Not all filters from .xz format are supported, * only CRC32 is supported as the integrity check, and decoding of * concatenated .xz streams is not supported. Thus, you may want to look * at xzdec from XZ Utils if a few KiB bigger tool is not a problem. */ #include #include #include #include "xz.h" static uint8_t in[BUFSIZ]; static uint8_t out[BUFSIZ]; int main(int argc, char **argv) { struct xz_buf b; struct xz_dec *s; enum xz_ret ret; const char *msg; if (argc >= 2 && strcmp(argv[1], "--help") == 0) { fputs("Uncompress a .xz file from stdin to stdout.\n" "Arguments other than `--help' are ignored.\n", stdout); return 0; } xz_crc32_init(); +#ifdef XZ_USE_CRC64 + xz_crc64_init(); +#endif /* * Support up to 64 MiB dictionary. The actually needed memory * is allocated once the headers have been parsed. */ s = xz_dec_init(XZ_DYNALLOC, 1 << 26); if (s == NULL) { msg = "Memory allocation failed\n"; goto error; } b.in = in; b.in_pos = 0; b.in_size = 0; b.out = out; b.out_pos = 0; b.out_size = BUFSIZ; while (true) { if (b.in_pos == b.in_size) { b.in_size = fread(in, 1, sizeof(in), stdin); b.in_pos = 0; } ret = xz_dec_run(s, &b); if (b.out_pos == sizeof(out)) { if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos) { msg = "Write error\n"; goto error; } b.out_pos = 0; } if (ret == XZ_OK) continue; #ifdef XZ_DEC_ANY_CHECK if (ret == XZ_UNSUPPORTED_CHECK) { fputs(argv[0], stderr); fputs(": ", stderr); fputs("Unsupported check; not verifying " "file integrity\n", stderr); continue; } #endif if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos || fclose(stdout)) { msg = "Write error\n"; goto error; } switch (ret) { case XZ_STREAM_END: xz_dec_end(s); return 0; case XZ_MEM_ERROR: msg = "Memory allocation failed\n"; goto error; case XZ_MEMLIMIT_ERROR: msg = "Memory usage limit reached\n"; goto error; case XZ_FORMAT_ERROR: msg = "Not a .xz file\n"; goto error; case XZ_OPTIONS_ERROR: msg = "Unsupported options in the .xz headers\n"; goto error; case XZ_DATA_ERROR: case XZ_BUF_ERROR: msg = "File is corrupt\n"; goto error; default: msg = "Bug!\n"; goto error; } } error: xz_dec_end(s); fputs(argv[0], stderr); fputs(": ", stderr); fputs(msg, stderr); return 1; }