linux/lib/decompress_unxz.c
<<
>>
Prefs
   1/*
   2 * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd
   3 *
   4 * Author: Lasse Collin <lasse.collin@tukaani.org>
   5 *
   6 * This file has been put into the public domain.
   7 * You can do whatever you want with this file.
   8 */
   9
  10/*
  11 * Important notes about in-place decompression
  12 *
  13 * At least on x86, the kernel is decompressed in place: the compressed data
  14 * is placed to the end of the output buffer, and the decompressor overwrites
  15 * most of the compressed data. There must be enough safety margin to
  16 * guarantee that the write position is always behind the read position.
  17 *
  18 * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below.
  19 * Note that the margin with XZ is bigger than with Deflate (gzip)!
  20 *
  21 * The worst case for in-place decompression is that the beginning of
  22 * the file is compressed extremely well, and the rest of the file is
  23 * uncompressible. Thus, we must look for worst-case expansion when the
  24 * compressor is encoding uncompressible data.
  25 *
  26 * The structure of the .xz file in case of a compresed kernel is as follows.
  27 * Sizes (as bytes) of the fields are in parenthesis.
  28 *
  29 *    Stream Header (12)
  30 *    Block Header:
  31 *      Block Header (8-12)
  32 *      Compressed Data (N)
  33 *      Block Padding (0-3)
  34 *      CRC32 (4)
  35 *    Index (8-20)
  36 *    Stream Footer (12)
  37 *
  38 * Normally there is exactly one Block, but let's assume that there are
  39 * 2-4 Blocks just in case. Because Stream Header and also Block Header
  40 * of the first Block don't make the decompressor produce any uncompressed
  41 * data, we can ignore them from our calculations. Block Headers of possible
  42 * additional Blocks have to be taken into account still. With these
  43 * assumptions, it is safe to assume that the total header overhead is
  44 * less than 128 bytes.
  45 *
  46 * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ
  47 * doesn't change the size of the data, it is enough to calculate the
  48 * safety margin for LZMA2.
  49 *
  50 * LZMA2 stores the data in chunks. Each chunk has a header whose size is
  51 * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that
  52 * the maximum chunk header size is 8 bytes. After the chunk header, there
  53 * may be up to 64 KiB of actual payload in the chunk. Often the payload is
  54 * quite a bit smaller though; to be safe, let's assume that an average
  55 * chunk has only 32 KiB of payload.
  56 *
  57 * The maximum uncompressed size of the payload is 2 MiB. The minimum
  58 * uncompressed size of the payload is in practice never less than the
  59 * payload size itself. The LZMA2 format would allow uncompressed size
  60 * to be less than the payload size, but no sane compressor creates such
  61 * files. LZMA2 supports storing uncompressible data in uncompressed form,
  62 * so there's never a need to create payloads whose uncompressed size is
  63 * smaller than the compressed size.
  64 *
  65 * The assumption, that the uncompressed size of the payload is never
  66 * smaller than the payload itself, is valid only when talking about
  67 * the payload as a whole. It is possible that the payload has parts where
  68 * the decompressor consumes more input than it produces output. Calculating
  69 * the worst case for this would be tricky. Instead of trying to do that,
  70 * let's simply make sure that the decompressor never overwrites any bytes
  71 * of the payload which it is currently reading.
  72 *
  73 * Now we have enough information to calculate the safety margin. We need
  74 *   - 128 bytes for the .xz file format headers;
  75 *   - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header
  76 *     per chunk, each chunk having average payload size of 32 KiB); and
  77 *   - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that
  78 *     the decompressor never overwrites anything from the LZMA2 chunk
  79 *     payload it is currently reading.
  80 *
  81 * We get the following formula:
  82 *
  83 *    safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536
  84 *                  = 128 + (uncompressed_size >> 12) + 65536
  85 *
  86 * For comparison, according to arch/x86/boot/compressed/misc.c, the
  87 * equivalent formula for Deflate is this:
  88 *
  89 *    safety_margin = 18 + (uncompressed_size >> 12) + 32768
  90 *
  91 * Thus, when updating Deflate-only in-place kernel decompressor to
  92 * support XZ, the fixed overhead has to be increased from 18+32768 bytes
  93 * to 128+65536 bytes.
  94 */
  95
  96/*
  97 * STATIC is defined to "static" if we are being built for kernel
  98 * decompression (pre-boot code). <linux/decompress/mm.h> will define
  99 * STATIC to empty if it wasn't already defined. Since we will need to
 100 * know later if we are being used for kernel decompression, we define
 101 * XZ_PREBOOT here.
 102 */
 103#ifdef STATIC
 104#       define XZ_PREBOOT
 105#endif
 106#ifdef __KERNEL__
 107#       include <linux/decompress/mm.h>
 108#endif
 109#define XZ_EXTERN STATIC
 110
 111#ifndef XZ_PREBOOT
 112#       include <linux/slab.h>
 113#       include <linux/xz.h>
 114#else
 115/*
 116 * Use the internal CRC32 code instead of kernel's CRC32 module, which
 117 * is not available in early phase of booting.
 118 */
 119#define XZ_INTERNAL_CRC32 1
 120
 121/*
 122 * For boot time use, we enable only the BCJ filter of the current
 123 * architecture or none if no BCJ filter is available for the architecture.
 124 */
 125#ifdef CONFIG_X86
 126#       define XZ_DEC_X86
 127#endif
 128#ifdef CONFIG_PPC
 129#       define XZ_DEC_POWERPC
 130#endif
 131#ifdef CONFIG_ARM
 132#       define XZ_DEC_ARM
 133#endif
 134#ifdef CONFIG_IA64
 135#       define XZ_DEC_IA64
 136#endif
 137#ifdef CONFIG_SPARC
 138#       define XZ_DEC_SPARC
 139#endif
 140
 141/*
 142 * This will get the basic headers so that memeq() and others
 143 * can be defined.
 144 */
 145#include "xz/xz_private.h"
 146
 147/*
 148 * Replace the normal allocation functions with the versions from
 149 * <linux/decompress/mm.h>. vfree() needs to support vfree(NULL)
 150 * when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it.
 151 * Workaround it here because the other decompressors don't need it.
 152 */
 153#undef kmalloc
 154#undef kfree
 155#undef vmalloc
 156#undef vfree
 157#define kmalloc(size, flags) malloc(size)
 158#define kfree(ptr) free(ptr)
 159#define vmalloc(size) malloc(size)
 160#define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0)
 161
 162/*
 163 * FIXME: Not all basic memory functions are provided in architecture-specific
 164 * files (yet). We define our own versions here for now, but this should be
 165 * only a temporary solution.
 166 *
 167 * memeq and memzero are not used much and any remotely sane implementation
 168 * is fast enough. memcpy/memmove speed matters in multi-call mode, but
 169 * the kernel image is decompressed in single-call mode, in which only
 170 * memcpy speed can matter and only if there is a lot of uncompressible data
 171 * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
 172 * functions below should just be kept small; it's probably not worth
 173 * optimizing for speed.
 174 */
 175
 176#ifndef memeq
 177static bool memeq(const void *a, const void *b, size_t size)
 178{
 179        const uint8_t *x = a;
 180        const uint8_t *y = b;
 181        size_t i;
 182
 183        for (i = 0; i < size; ++i)
 184                if (x[i] != y[i])
 185                        return false;
 186
 187        return true;
 188}
 189#endif
 190
 191#ifndef memzero
 192static void memzero(void *buf, size_t size)
 193{
 194        uint8_t *b = buf;
 195        uint8_t *e = b + size;
 196
 197        while (b != e)
 198                *b++ = '\0';
 199}
 200#endif
 201
 202#ifndef memmove
 203/* Not static to avoid a conflict with the prototype in the Linux headers. */
 204void *memmove(void *dest, const void *src, size_t size)
 205{
 206        uint8_t *d = dest;
 207        const uint8_t *s = src;
 208        size_t i;
 209
 210        if (d < s) {
 211                for (i = 0; i < size; ++i)
 212                        d[i] = s[i];
 213        } else if (d > s) {
 214                i = size;
 215                while (i-- > 0)
 216                        d[i] = s[i];
 217        }
 218
 219        return dest;
 220}
 221#endif
 222
 223/*
 224 * Since we need memmove anyway, would use it as memcpy too.
 225 * Commented out for now to avoid breaking things.
 226 */
 227/*
 228#ifndef memcpy
 229#       define memcpy memmove
 230#endif
 231*/
 232
 233#include "xz/xz_crc32.c"
 234#include "xz/xz_dec_stream.c"
 235#include "xz/xz_dec_lzma2.c"
 236#include "xz/xz_dec_bcj.c"
 237
 238#endif /* XZ_PREBOOT */
 239
 240/* Size of the input and output buffers in multi-call mode */
 241#define XZ_IOBUF_SIZE 4096
 242
 243/*
 244 * This function implements the API defined in <linux/decompress/generic.h>.
 245 *
 246 * This wrapper will automatically choose single-call or multi-call mode
 247 * of the native XZ decoder API. The single-call mode can be used only when
 248 * both input and output buffers are available as a single chunk, i.e. when
 249 * fill() and flush() won't be used.
 250 */
 251STATIC int INIT unxz(unsigned char *in, int in_size,
 252                     int (*fill)(void *dest, unsigned int size),
 253                     int (*flush)(void *src, unsigned int size),
 254                     unsigned char *out, int *in_used,
 255                     void (*error)(char *x))
 256{
 257        struct xz_buf b;
 258        struct xz_dec *s;
 259        enum xz_ret ret;
 260        bool must_free_in = false;
 261
 262#if XZ_INTERNAL_CRC32
 263        xz_crc32_init();
 264#endif
 265
          e fixed overhead has to be increased a(3"> 253                     int (omp0out, int * 27e32y rem26 name="L217"> 217        }
 265


 207        cons" id="Lf="lib/decompress_unxzd="Lf="ld="L2 name="L261"> 261 263linux/xz.h>
in_d="L207" class="line" name="L207"> 207        cons" id="Lf="lib/decompress_unxzd="Lf="ld="L2 name="L261"> 261<="lib/deib/decompress_unxz="lib/de class2 name="L261"> 2nxz.L26lib/decompress_unxz.L26l.c#L2-163" class="line" name="L263"> 263 263 173 265
<"line" name="L207"> 207 id="L2>
 12427sed" class="sref">in_goto.c#L197" id="L197d="L_class_href7" class="line" nd="L_class_href7 size;
 176#ifndef  265

size_t .ib/decompress_unxz.c#L254" id="L254" cla07        consnxz.c#L254" id="L254" cla .ib/decompress_unxze=unxz" class="sref"nxze=unx cla07vmalloc(x =2y =2.ib/decompress_unxze=unxz" class="sref"nxze=unx cla07
size_t2in_d="L207" class=s="line" name="L257">.ib/decompress_unxz.c#L254" id="L254" cla07        cons href="+code=vmalloc" class="sref">vmalloc(n>
 263se="L265"> 265
.ib/decompress_unxz.c#L254" id="L254" cla07 id="L2>
size; +2in_goto.c#L197" id="L197d="L_class_nxz.c#L254" id="L27d="L_class_nxzd="L y[2a hre2="+code=i" clat" class="sref">dest;
false;
 265
        } else if ( 182        return  260                cons href="+code=vmalloc" class="sref">vmalloc(n>
 263 265
 263in_goto.c#L197" id="L197d="L_class_code=INIT" class=7d="L_class_coz.c#L187" id="L187" class="line" name=2="L191"> 291#ifndef dest;
size_t  263 193.ib/decompress_ucode=INIT" class="sref" =        conscode=INIT" class="sref"L187" id="L187" class="line" name=2=compress_class="sref">b = buf.ib/decompress_uco_po"line" name="L20co_po"p0outcode=b" c2ass="sref">b +  205.ib/decompress_uco_=unxz" class="sref">unxz(u =        consco_=unxz" class="sref">unxz(un64" id="L6> 226<" class="sref">outclib/deco2press_unxz.c#L196" id="L296" c2ass="line" nam id="L257" class="line" name="L257">.ib/decompress_unxzepo"line" name="L20nxzepo"p0outc187"> 182b" class="sref">b !=2 217        }
b++ =  265


 207        cons" id="Lruode=INIT" class=" id="Lruo="sref">vmalloc("line" name="L207"> 2, & id="L257" class="line" name="L257">63" class="line" name="L263"> 263        } else if (in_0"> 13        } else if (size_t size 265
.ib/decompress_uco_po"line" name="L20co_po"p0 195        unxz(u &&57#define vfree( 13        } else if (in_ize 265
size_t i]]]]]]]]]]]]]]]]]sed a(3"> 253                     int (omp0 195         263b + false;
d = buf.ib/decompress_uco_po"line" name="L20co_po"p0ou3"+code=s"3class="sref">s =  217        }
size_t3bufunxz(u =        cons mpress_unxz.c#L252" id="L2L265"> 265
(void *
 263in_ize 265
unxz(u &ld="L2> 13        } else if (d < <3 href3"+code=s" class="sref"ass="sreaaaaaaaaaaaaaaaasne" name="L242"> 242
size; +3
s[3a hre3139;s probably not worth"linitss="line" i="line" n="L17 m25" i>
d > <3 href31span class="comment">/*a new omprei" id" id="L249" class="line" name="L249"> 2493code=i" c3ass="sref">i =  114#eaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaan>
      3         while (i-- > 00000000000000000d="L207" class=ass="line" name="L259"> 207        consnxz#L24ERRORib/decompress_unxz#L24ERRORp0 263s[3a hre31head has to be increaaaaaaaaaaaaaaaaaaaaaaaaa#L2253" class="line" name="L263"> 263dest;
/* XZ_PREBOOT */
 213        return in_ize 205.ib/decompress_uco_=unxz" class="sref">unxz(u =        consco_=unxz" class="sref">unxz(un64" id="L6> 226<" class="sref">ou3lib/decom3ress_unxz.c#L220" id="L230" cl32+code=s" class="sref"ass="sret" class="sref">dest;
 221#endif
size 207        cons" id="Lruode=INIT" class=" id="Lruo="sref">vmalloc("line" name="L207"> 2, & id="L257" class="line" name="L257">63" class="line" name="L263"> 263 323 13ent"> * S"L296" c2e/a> =2in_ize 265 323 26563" class="line" name="L23ers. */ 13        } else if (iOKpo"line" name="L20co_po"p0in_ize 265 323 * Commented out fo3 now 32=ss="sref">b + d < <3 hre="L226" c3ass="line" name="L226"> 326 */ 13        } else if (d < <3 hre=code=s"3zname="L227"> 227/*
 13        } else if (d < <3 hre/a>#ifndef m3mcpy<3span>
 229#3     3define memcpy memmovel> 13        } else if (i =  2303/a>i = 0;  13ent"> L241" id="L63" class="line" name="L263"> 263in_ize 265 323in_ize 265 323i =       3         while (i-- > 00000000000000000d="L207" class=ass="linine" name3"L232"> 232
63" c32.c3quot;
unxz(un64" id="L6> 226<" class="sref">outclib/deco2press_unxz.c#L196" id="L296" c2ass="line" nam id="L257"3tream.c"
b +  214      3      as a single chunk, iOKclass="sref">iOKpo"lLruode=INIT" class=" id="Lruo="sref" name="L236"> 236#include &quo3;s = a32 id="L135" class213        } else if ( 1)" c3ass="sref">i =  160#define buf 233
bool <3rs in mul3i-call mode */
i = 0;  13ent"> * S"L296" c2e/a> =2i =  241#de3ine <34unxz.c#L221" id="L221" c3ass="3ine" name="L2=0"> 160#define  263(xz3 implemen3s the API defined in <3linux34unxz.c#L264" id="L264" class="line" name="L264"> 264#endif
 265
<3an>
 i]]]]]]]]]]]]]]]]]sed a(3"> 253                     int (omp0 195
lib/deco3press_unxz.c#en=2line" name="L1unxz.c#en=ass="sref">size * fill()3and f35onsco_=unxz" switchame="L214"> 214      3    09" id="L309" c310ead has to be incre+code=INI3" class="sref">INIT 3a hre3="+code=unxz" casd="L240" class="lineSTREAM_ENDclass="sref">iSTREAM_END+cod: id="L309" c310ead has to be incre+lass="sre                  int (*3a hre3="+code=fill" class="s"L217" d="L296" c2ass="line" nam id="L257"3253  3                  int (*3a hre35id="L257" class="line" name="L257">63" z.c#L254"3id="L254" class="line" n3me="L354"> 254  casd="L240" class="lineMEMde3i" class="sref">iMEMde3i" +cod: id="L309" c310ead has to be incre+implemen3_unxz.c#L255" id="L255" 3lass=35"li5an31mp="l> 138#endif mmentef="lib/decompresef="+code=memmove" class="sref">memmove
3      voi3 (*memor rll ou imagress_ud="L235code=mLruode=INIT" class=" id="Lruo="sref"a 263;
;
iFORMATde3i" +cod: id="L309" c310ead has to be incre="line" n3me="L260"> 260      3 x =2pantterat (wrong magic bytes)d="L235code=mLruode=INIT" class=" id="Lruo="sref" href="+c3de=must_free_in" class="3ref">36"sref">i = 0;  263 261
<3 href36ndef XZ_INTERNAL_CRC32
3a hre364="L259" clascasd="L240" class="lineOPTIONSde3i" class="sref">iOPTIONSde3i" +cod: id="L309" c310ead has to be incre=.c#L254"3e="L263"> 263       3 * sibld="L235code=m id="L309" c310ead has to be incre=implemen3();
 2633253                     int (omp0out, in3 *iDATAde3i" +cod: id="L309" c310ead has to be incre i-- > 00000: id="L309" c310ead has to be incre "line" n3="Lf="ld="L2 name="L261"3 261<37>x =2 263 263 2n3z.L26lib/decompress_unxz.L26l.c#L2-163"3class="li3e" name="L263"> 263 2073id="L3>
pan claf">memord="L235code=mLruode=INIT" class=" id="Lruo="sref" implemen3c#L197" id="L197d="L_cla3s_hre37"li5an31mp="l> 13"line" name="L263"> 263d[37                     int (omp0.ib/decompress_unxze=unxz3 class="s3ef"nxze=unx cla07vm3lloc<38nxz.c#L188" id="L188" class="line" nam3t_free_in3 classref="+cod2=x" clas3="sre38sh() won't be use" name="L263"> 263 13ent"> * S"L296" c2e/a> =2i = vmalloc(n>3 160#define  26363" eref">in_3oto.c#L197" id="L197d="L3class3nxz.c#won't be use" name="L2665" class=ode=size"2class="sref">size: id="L309" c310ead has to be increeimplemen3ree_in" classrcompress_e3y" cl38uco_po"line" name="L20co_po"unxz.c#en=2line" name="L1unxz.c#en=ass="sref">sizedest;
 260    3   lib/deco3press_a href="+code=out" class="sre(e (memor rll ou imagress_ud="L235code=mLruode=INIT" class=" id="Lruo="sref"alloc" cl3ss="sref">vmalloc(n>3.ib/decompress_unxze=unxz3265
<3ode=INIT" class="sref" =3id="L3>
d[i3_goto.c#L197" id="L197d=3L_cla390" cl32+code=s" class="sref"ass="sret" 87" class3"line" name=2="L191"> 293#39href="+code=XZ_IOBUF_SIZE" class="sref">XZ_IOBUF_SIZE 4096
dest;
 242
 2es/a> 40ass="sref">XZ_IOBUF_SIZE 4096
in_3ss_ucode=INIT" class="sr3f" =<39xz.c#L224" id="L224" class="likernel imageth input and output buffers are available3buf.ib/dec3mpres39ompress_unxz.c#L225" id="L225" class="line" name="L225"> 225unxz(u = 3     3consco240" id="L240" class="l225"> 225 40asaL250"> 250 */ 225
.ib/decom3ress_3nxzepo


nt">original LXR softw> * by tod="L240" clhttp://sourceforgetnet/ 2ojec2s/lxr">LXR 5" iunity" iduntode=experiid="al vers"libby "L240" clmailto:lxr@lclas.no">lxr@lclas.no"L263
lxr.lclas.no kindly hosted by "L240" clhttp://www.redpill-lcl 2o.no">Redpill>#if 2o AS" idun 2oviss="magLifnde hre"libngspan cpera="lis services/s