kernel-bzip2-lzma.patch

   1 Linus,
   2
   3 Please pull the latest bzip2-lzma-for-linus git tree from:
   4
   5    git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip.git bzip2-lzma-for-linus
   6
   7 We are sending this as a separate tree as it affects generic
   8 files as well.
   9
  10 Highlights:
  11
  12  - Add kernel image compression mode config options:
  13
  14     Kernel compression mode
  15     > 1. Gzip (KERNEL_GZIP) (NEW)
  16       2. Bzip2 (KERNEL_BZIP2) (NEW)
  17       3. LZMA (KERNEL_LZMA) (NEW)
  18
  19     Initial ramdisk compressed using gzip (RD_GZIP) [Y/n/?] (NEW)
  20     Initial ramdisk compressed using bzip2 (RD_BZIP2) [N/y/?] (NEW)
  21     Initial ramdisk compressed using lzma (RD_LZMA) [N/y/?] (NEW)
  22
  23     Built-in initramfs compression mode
  24     > 1. None (INITRAMFS_COMPRESSION_NONE) (NEW)
  25       2. Gzip (INITRAMFS_COMPRESSION_GZIP) (NEW)
  26     choice[1-2?]:
  27
  28    ... and matching compression and decompression implementations.
  29
  30 Risks:
  31
  32  - This has been a historically problematic topic thus we skipped
  33    the v2.6.28 and v2.6.29 merge windows with it. Boot failures,
  34    panics, initrd decompression problems have been observed and
  35    fixed.
  36
  37  - On x86 we switch over from lib/inflate.c to zlib - same
  38    functionality but different library. Other architectures are not
  39    affected by that, use of this new facility is opt-in. (This was
  40    the last in-kernel user of lib/inflate.c on x86.)
  41
  42  - To build a kernel with a different compressor the 'bzip2' or 'lzma'
  43    tools are needed. If the kernel is built with CONFIG_KERNEL_LZMA=y
  44    and the tool is not available the kernel build will fail with a clear
  45    message. This tool is available in all major kernel distros, but
  46    it is not generally a default-installed package. bzip2 is generally
  47    installed by default.
  48
  49  - There are no known regressions.
  50
  51  Thanks,
  52
  53         Ingo
  54
  55 ------------------>
  56 Alain Knaff (8):
  57       bzip2/lzma: library support for gzip, bzip2 and lzma decompression
  58       bzip2/lzma: config and initramfs support for bzip2/lzma decompression
  59       bzip2/lzma: x86 kernel compression support
  60       bzip2/lzma: fix built-in initramfs vs CONFIG_RD_GZIP
  61       bzip2/lzma: fix decompress_inflate.c vs multi-block-with-embedded-filename
  62       bzip2/lzma: don't stop search at first unconfigured compression
  63       bzip2/lzma: don't leave empty files around on failure
  64       bzip2/lzma: make internal initramfs compression configurable
  65
  66 Cyrill Gorcunov (1):
  67       x86: headers cleanup - boot.h
  68
  69 H. Peter Anvin (11):
  70       bzip2/lzma: use a table to search for initramfs compression formats
  71       bzip2/lzma: handle failures from bzip2 and lzma correctly
  72       bzip2/lzma: make config machinery an arch configurable
  73       bzip2/lzma: proper Kconfig dependencies for the ramdisk options
  74       bzip2/lzma: DECOMPRESS_GZIP should select ZLIB_INFLATE
  75       bzip2/lzma: move initrd/ramfs options out of BLK_DEV
  76       bzip2/lzma: fix constant in decompress_inflate
  77       bzip2/lzma: centralize format detection
  78       bzip2/lzma: comprehensible error messages for missing decompressor
  79       init: make initrd/initramfs decompression failure a KERN_EMERG event
  80       bzip2/lzma: update boot protocol specification
  81
  82 Ingo Molnar (1):
  83       bzip2/lzma: make flush_buffer() unconditional
  84
  85
  86  Documentation/x86/boot.txt         |    5 +-
  87  arch/x86/Kconfig                   |    3 +
  88  arch/x86/boot/compressed/Makefile  |   21 +-
  89  arch/x86/boot/compressed/misc.c    |  118 +-----
  90  arch/x86/include/asm/boot.h        |   16 +-
  91  include/linux/decompress/bunzip2.h |   10 +
  92  include/linux/decompress/generic.h |   33 ++
  93  include/linux/decompress/inflate.h |   13 +
  94  include/linux/decompress/mm.h      |   87 +++++
  95  include/linux/decompress/unlzma.h  |   12 +
  96  init/Kconfig                       |   60 +++
  97  init/do_mounts_rd.c                |  178 +++-------
  98  init/initramfs.c                   |  122 ++-----
  99  lib/Kconfig                        |   14 +
 100  lib/Makefile                       |    7 +-
 101  lib/decompress.c                   |   54 +++
 102  lib/decompress_bunzip2.c           |  735 ++++++++++++++++++++++++++++++++++++
 103  lib/decompress_inflate.c           |  167 ++++++++
 104  lib/decompress_unlzma.c            |  647 +++++++++++++++++++++++++++++++
 105  lib/zlib_inflate/inflate.h         |    4 +
 106  lib/zlib_inflate/inftrees.h        |    4 +
 107  scripts/Makefile.lib               |   14 +
 108  scripts/bin_size                   |   10 +
 109  scripts/gen_initramfs_list.sh      |   18 +-
 110  usr/Kconfig                        |   89 +++++
 111  usr/Makefile                       |   36 ++-
 112  usr/initramfs_data.S               |    2 +-
 113  usr/initramfs_data.bz2.S           |   29 ++
 114  usr/initramfs_data.gz.S            |   29 ++
 115  usr/initramfs_data.lzma.S          |   29 ++
 116  30 files changed, 2222 insertions(+), 344 deletions(-)
 117  create mode 100644 include/linux/decompress/bunzip2.h
 118  create mode 100644 include/linux/decompress/generic.h
 119  create mode 100644 include/linux/decompress/inflate.h
 120  create mode 100644 include/linux/decompress/mm.h
 121  create mode 100644 include/linux/decompress/unlzma.h
 122  create mode 100644 lib/decompress.c
 123  create mode 100644 lib/decompress_bunzip2.c
 124  create mode 100644 lib/decompress_inflate.c
 125  create mode 100644 lib/decompress_unlzma.c
 126  create mode 100644 scripts/bin_size
 127  create mode 100644 usr/initramfs_data.bz2.S
 128  create mode 100644 usr/initramfs_data.gz.S
 129  create mode 100644 usr/initramfs_data.lzma.S
 130
 131 diff --git a/Documentation/x86/boot.txt b/Documentation/x86/boot.txt
 132 index 7b4596a..d05730e 100644
 133 --- a/Documentation/x86/boot.txt
 134 +++ b/Documentation/x86/boot.txt
 135 @@ -542,7 +542,10 @@ Protocol:  2.08+
 136
 137    The payload may be compressed. The format of both the compressed and
 138    uncompressed data should be determined using the standard magic
 139 -  numbers. Currently only gzip compressed ELF is used.
 140 +  numbers.  The currently supported compression formats are gzip
 141 +  (magic numbers 1F 8B or 1F 9E), bzip2 (magic number 42 5A) and LZMA
 142 +  (magic number 5D 00).  The uncompressed payload is currently always ELF
 143 +  (magic number 7F 45 4C 46).
 144
 145  Field name:    payload_length
 146  Type:          read
 147 diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
 148 index bc2fbad..a233768 100644
 149 --- a/arch/x86/Kconfig
 150 +++ b/arch/x86/Kconfig
 151 @@ -40,6 +40,9 @@ config X86
 152         select HAVE_GENERIC_DMA_COHERENT if X86_32
 153         select HAVE_EFFICIENT_UNALIGNED_ACCESS
 154         select USER_STACKTRACE_SUPPORT
 155 +       select HAVE_KERNEL_GZIP
 156 +       select HAVE_KERNEL_BZIP2
 157 +       select HAVE_KERNEL_LZMA
 158
 159  config ARCH_DEFCONFIG
 160         string
 161 diff --git a/arch/x86/boot/compressed/Makefile b/arch/x86/boot/compressed/Makefile
 162 index 1771c80..3ca4c19 100644
 163 --- a/arch/x86/boot/compressed/Makefile
 164 +++ b/arch/x86/boot/compressed/Makefile
 165 @@ -4,7 +4,7 @@
 166  # create a compressed vmlinux image from the original vmlinux
 167  #
 168
 169 -targets := vmlinux vmlinux.bin vmlinux.bin.gz head_$(BITS).o misc.o piggy.o
 170 +targets := vmlinux vmlinux.bin vmlinux.bin.gz vmlinux.bin.bz2 vmlinux.bin.lzma head_$(BITS).o misc.o piggy.o
 171
 172  KBUILD_CFLAGS := -m$(BITS) -D__KERNEL__ $(LINUX_INCLUDE) -O2
 173  KBUILD_CFLAGS += -fno-strict-aliasing -fPIC
 174 @@ -47,18 +47,35 @@ ifeq ($(CONFIG_X86_32),y)
 175  ifdef CONFIG_RELOCATABLE
 176  $(obj)/vmlinux.bin.gz: $(obj)/vmlinux.bin.all FORCE
 177         $(call if_changed,gzip)
 178 +$(obj)/vmlinux.bin.bz2: $(obj)/vmlinux.bin.all FORCE
 179 +       $(call if_changed,bzip2)
 180 +$(obj)/vmlinux.bin.lzma: $(obj)/vmlinux.bin.all FORCE
 181 +       $(call if_changed,lzma)
 182  else
 183  $(obj)/vmlinux.bin.gz: $(obj)/vmlinux.bin FORCE
 184         $(call if_changed,gzip)
 185 +$(obj)/vmlinux.bin.bz2: $(obj)/vmlinux.bin FORCE
 186 +       $(call if_changed,bzip2)
 187 +$(obj)/vmlinux.bin.lzma: $(obj)/vmlinux.bin FORCE
 188 +       $(call if_changed,lzma)
 189  endif
 190  LDFLAGS_piggy.o := -r --format binary --oformat elf32-i386 -T
 191
 192  else
 193 +
 194  $(obj)/vmlinux.bin.gz: $(obj)/vmlinux.bin FORCE
 195         $(call if_changed,gzip)
 196 +$(obj)/vmlinux.bin.bz2: $(obj)/vmlinux.bin FORCE
 197 +       $(call if_changed,bzip2)
 198 +$(obj)/vmlinux.bin.lzma: $(obj)/vmlinux.bin FORCE
 199 +       $(call if_changed,lzma)
 200
 201  LDFLAGS_piggy.o := -r --format binary --oformat elf64-x86-64 -T
 202  endif
 203
 204 -$(obj)/piggy.o: $(obj)/vmlinux.scr $(obj)/vmlinux.bin.gz FORCE
 205 +suffix_$(CONFIG_KERNEL_GZIP)  = gz
 206 +suffix_$(CONFIG_KERNEL_BZIP2) = bz2
 207 +suffix_$(CONFIG_KERNEL_LZMA)  = lzma
 208 +
 209 +$(obj)/piggy.o: $(obj)/vmlinux.scr $(obj)/vmlinux.bin.$(suffix_y) FORCE
 210         $(call if_changed,ld)
 211 diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
 212 index da06221..e45be73 100644
 213 --- a/arch/x86/boot/compressed/misc.c
 214 +++ b/arch/x86/boot/compressed/misc.c
 215 @@ -116,71 +116,13 @@
 216  /*
 217   * gzip declarations
 218   */
 219 -
 220 -#define OF(args)       args
 221  #define STATIC         static
 222
 223  #undef memset
 224  #undef memcpy
 225  #define memzero(s, n)  memset((s), 0, (n))
 226
 227 -typedef unsigned char  uch;
 228 -typedef unsigned short ush;
 229 -typedef unsigned long  ulg;
 230 -
 231 -/*
 232 - * Window size must be at least 32k, and a power of two.
 233 - * We don't actually have a window just a huge output buffer,
 234 - * so we report a 2G window size, as that should always be
 235 - * larger than our output buffer:
 236 - */
 237 -#define WSIZE          0x80000000
 238 -
 239 -/* Input buffer: */
 240 -static unsigned char   *inbuf;
 241 -
 242 -/* Sliding window buffer (and final output buffer): */
 243 -static unsigned char   *window;
 244 -
 245 -/* Valid bytes in inbuf: */
 246 -static unsigned                insize;
 247 -
 248 -/* Index of next byte to be processed in inbuf: */
 249 -static unsigned                inptr;
 250 -
 251 -/* Bytes in output buffer: */
 252 -static unsigned                outcnt;
 253 -
 254 -/* gzip flag byte */
 255 -#define ASCII_FLAG     0x01 /* bit 0 set: file probably ASCII text */
 256 -#define CONTINUATION   0x02 /* bit 1 set: continuation of multi-part gz file */
 257 -#define EXTRA_FIELD    0x04 /* bit 2 set: extra field present */
 258 -#define ORIG_NAM       0x08 /* bit 3 set: original file name present */
 259 -#define COMMENT                0x10 /* bit 4 set: file comment present */
 260 -#define ENCRYPTED      0x20 /* bit 5 set: file is encrypted */
 261 -#define RESERVED       0xC0 /* bit 6, 7:  reserved */
 262 -
 263 -#define get_byte()     (inptr < insize ? inbuf[inptr++] : fill_inbuf())
 264 -
 265 -/* Diagnostic functions */
 266 -#ifdef DEBUG
 267 -#  define Assert(cond, msg) do { if (!(cond)) error(msg); } while (0)
 268 -#  define Trace(x)     do { fprintf x; } while (0)
 269 -#  define Tracev(x)    do { if (verbose) fprintf x ; } while (0)
 270 -#  define Tracevv(x)   do { if (verbose > 1) fprintf x ; } while (0)
 271 -#  define Tracec(c, x) do { if (verbose && (c)) fprintf x ; } while (0)
 272 -#  define Tracecv(c, x)        do { if (verbose > 1 && (c)) fprintf x ; } while (0)
 273 -#else
 274 -#  define Assert(cond, msg)
 275 -#  define Trace(x)
 276 -#  define Tracev(x)
 277 -#  define Tracevv(x)
 278 -#  define Tracec(c, x)
 279 -#  define Tracecv(c, x)
 280 -#endif
 281
 282 -static int  fill_inbuf(void);
 283 -static void flush_window(void);
 284  static void error(char *m);
 285
 286  /*
 287 @@ -189,13 +131,8 @@ static void error(char *m);
 288  static struct boot_params *real_mode;          /* Pointer to real-mode data */
 289  static int quiet;
 290
 291 -extern unsigned char input_data[];
 292 -extern int input_len;
 293 -
 294 -static long bytes_out;
 295 -
 296  static void *memset(void *s, int c, unsigned n);
 297 -static void *memcpy(void *dest, const void *src, unsigned n);
 298 +void *memcpy(void *dest, const void *src, unsigned n);
 299
 300  static void __putstr(int, const char *);
 301  #define putstr(__x)  __putstr(0, __x)
 302 @@ -213,7 +150,17 @@ static char *vidmem;
 303  static int vidport;
 304  static int lines, cols;
 305
 306 -#include "../../../../lib/inflate.c"
 307 +#ifdef CONFIG_KERNEL_GZIP
 308 +#include "../../../../lib/decompress_inflate.c"
 309 +#endif
 310 +
 311 +#ifdef CONFIG_KERNEL_BZIP2
 312 +#include "../../../../lib/decompress_bunzip2.c"
 313 +#endif
 314 +
 315 +#ifdef CONFIG_KERNEL_LZMA
 316 +#include "../../../../lib/decompress_unlzma.c"
 317 +#endif
 318
 319  static void scroll(void)
 320  {
 321 @@ -282,7 +229,7 @@ static void *memset(void *s, int c, unsigned n)
 322         return s;
 323  }
 324
 325 -static void *memcpy(void *dest, const void *src, unsigned n)
 326 +void *memcpy(void *dest, const void *src, unsigned n)
 327  {
 328         int i;
 329         const char *s = src;
 330 @@ -293,38 +240,6 @@ static void *memcpy(void *dest, const void *src, unsigned n)
 331         return dest;
 332  }
 333
 334 -/* ===========================================================================
 335 - * Fill the input buffer. This is called only when the buffer is empty
 336 - * and at least one byte is really needed.
 337 - */
 338 -static int fill_inbuf(void)
 339 -{
 340 -       error("ran out of input data");
 341 -       return 0;
 342 -}
 343 -
 344 -/* ===========================================================================
 345 - * Write the output window window[0..outcnt-1] and update crc and bytes_out.
 346 - * (Used for the decompressed data only.)
 347 - */
 348 -static void flush_window(void)
 349 -{
 350 -       /* With my window equal to my output buffer
 351 -        * I only need to compute the crc here.
 352 -        */
 353 -       unsigned long c = crc;         /* temporary variable */
 354 -       unsigned n;
 355 -       unsigned char *in, ch;
 356 -
 357 -       in = window;
 358 -       for (n = 0; n < outcnt; n++) {
 359 -               ch = *in++;
 360 -               c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
 361 -       }
 362 -       crc = c;
 363 -       bytes_out += (unsigned long)outcnt;
 364 -       outcnt = 0;
 365 -}
 366
 367  static void error(char *x)
 368  {
 369 @@ -407,12 +322,8 @@ asmlinkage void decompress_kernel(void *rmode, memptr heap,
 370         lines = real_mode->screen_info.orig_video_lines;
 371         cols = real_mode->screen_info.orig_video_cols;
 372
 373 -       window = output;                /* Output buffer (Normally at 1M) */
 374         free_mem_ptr     = heap;        /* Heap */
 375         free_mem_end_ptr = heap + BOOT_HEAP_SIZE;
 376 -       inbuf  = input_data;            /* Input buffer */
 377 -       insize = input_len;
 378 -       inptr  = 0;
 379
 380  #ifdef CONFIG_X86_64
 381         if ((unsigned long)output & (__KERNEL_ALIGN - 1))
 382 @@ -430,10 +341,9 @@ asmlinkage void decompress_kernel(void *rmode, memptr heap,
 383  #endif
 384  #endif
 385
 386 -       makecrc();
 387         if (!quiet)
 388                 putstr("\nDecompressing Linux... ");
 389 -       gunzip();
 390 +       decompress(input_data, input_len, NULL, NULL, output, NULL, error);
 391         parse_elf(output);
 392         if (!quiet)
 393                 putstr("done.\nBooting the kernel.\n");
 394 diff --git a/arch/x86/include/asm/boot.h b/arch/x86/include/asm/boot.h
 395 index dd61616..6526cf0 100644
 396 --- a/arch/x86/include/asm/boot.h
 397 +++ b/arch/x86/include/asm/boot.h
 398 @@ -10,17 +10,31 @@
 399  #define EXTENDED_VGA   0xfffe          /* 80x50 mode */
 400  #define ASK_VGA                0xfffd          /* ask for it at bootup */
 401
 402 +#ifdef __KERNEL__
 403 +
 404  /* Physical address where kernel should be loaded. */
 405  #define LOAD_PHYSICAL_ADDR ((CONFIG_PHYSICAL_START \
 406                                 + (CONFIG_PHYSICAL_ALIGN - 1)) \
 407                                 & ~(CONFIG_PHYSICAL_ALIGN - 1))
 408
 409 +#ifdef CONFIG_KERNEL_BZIP2
 410 +#define BOOT_HEAP_SIZE             0x400000
 411 +#else /* !CONFIG_KERNEL_BZIP2 */
 412 +
 413  #ifdef CONFIG_X86_64
 414  #define BOOT_HEAP_SIZE 0x7000
 415 -#define BOOT_STACK_SIZE        0x4000
 416  #else
 417  #define BOOT_HEAP_SIZE 0x4000
 418 +#endif
 419 +
 420 +#endif /* !CONFIG_KERNEL_BZIP2 */
 421 +
 422 +#ifdef CONFIG_X86_64
 423 +#define BOOT_STACK_SIZE        0x4000
 424 +#else
 425  #define BOOT_STACK_SIZE        0x1000
 426  #endif
 427
 428 +#endif /* __KERNEL__ */
 429 +
 430  #endif /* _ASM_X86_BOOT_H */
 431 diff --git a/include/linux/decompress/bunzip2.h b/include/linux/decompress/bunzip2.h
 432 new file mode 100644
 433 index 0000000..1152721
 434 --- /dev/null
 435 +++ b/include/linux/decompress/bunzip2.h
 436 @@ -0,0 +1,10 @@
 437 +#ifndef DECOMPRESS_BUNZIP2_H
 438 +#define DECOMPRESS_BUNZIP2_H
 439 +
 440 +int bunzip2(unsigned char *inbuf, int len,
 441 +           int(*fill)(void*, unsigned int),
 442 +           int(*flush)(void*, unsigned int),
 443 +           unsigned char *output,
 444 +           int *pos,
 445 +           void(*error)(char *x));
 446 +#endif
 447 diff --git a/include/linux/decompress/generic.h b/include/linux/decompress/generic.h
 448 new file mode 100644
 449 index 0000000..6dfb856
 450 --- /dev/null
 451 +++ b/include/linux/decompress/generic.h
 452 @@ -0,0 +1,33 @@
 453 +#ifndef DECOMPRESS_GENERIC_H
 454 +#define DECOMPRESS_GENERIC_H
 455 +
 456 +/* Minimal chunksize to be read.
 457 + *Bzip2 prefers at least 4096
 458 + *Lzma prefers 0x10000 */
 459 +#define COMPR_IOBUF_SIZE       4096
 460 +
 461 +typedef int (*decompress_fn) (unsigned char *inbuf, int len,
 462 +                             int(*fill)(void*, unsigned int),
 463 +                             int(*writebb)(void*, unsigned int),
 464 +                             unsigned char *output,
 465 +                             int *posp,
 466 +                             void(*error)(char *x));
 467 +
 468 +/* inbuf   - input buffer
 469 + *len     - len of pre-read data in inbuf
 470 + *fill    - function to fill inbuf if empty
 471 + *writebb - function to write out outbug
 472 + *posp    - if non-null, input position (number of bytes read) will be
 473 + *       returned here
 474 + *
 475 + *If len != 0, the inbuf is initialized (with as much data), and fill
 476 + *should not be called
 477 + *If len = 0, the inbuf is allocated, but empty. Its size is IOBUF_SIZE
 478 + *fill should be called (repeatedly...) to read data, at most IOBUF_SIZE
 479 + */
 480 +
 481 +/* Utility routine to detect the decompression method */
 482 +decompress_fn decompress_method(const unsigned char *inbuf, int len,
 483 +                               const char **name);
 484 +
 485 +#endif
 486 diff --git a/include/linux/decompress/inflate.h b/include/linux/decompress/inflate.h
 487 new file mode 100644
 488 index 0000000..f9b06cc
 489 --- /dev/null
 490 +++ b/include/linux/decompress/inflate.h
 491 @@ -0,0 +1,13 @@
 492 +#ifndef INFLATE_H
 493 +#define INFLATE_H
 494 +
 495 +/* Other housekeeping constants */
 496 +#define INBUFSIZ 4096
 497 +
 498 +int gunzip(unsigned char *inbuf, int len,
 499 +          int(*fill)(void*, unsigned int),
 500 +          int(*flush)(void*, unsigned int),
 501 +          unsigned char *output,
 502 +          int *pos,
 503 +          void(*error_fn)(char *x));
 504 +#endif
 505 diff --git a/include/linux/decompress/mm.h b/include/linux/decompress/mm.h
 506 new file mode 100644
 507 index 0000000..12ff8c3
 508 --- /dev/null
 509 +++ b/include/linux/decompress/mm.h
 510 @@ -0,0 +1,87 @@
 511 +/*
 512 + * linux/compr_mm.h
 513 + *
 514 + * Memory management for pre-boot and ramdisk uncompressors
 515 + *
 516 + * Authors: Alain Knaff <alain@knaff.lu>
 517 + *
 518 + */
 519 +
 520 +#ifndef DECOMPR_MM_H
 521 +#define DECOMPR_MM_H
 522 +
 523 +#ifdef STATIC
 524 +
 525 +/* Code active when included from pre-boot environment: */
 526 +
 527 +/* A trivial malloc implementation, adapted from
 528 + *  malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
 529 + */
 530 +static unsigned long malloc_ptr;
 531 +static int malloc_count;
 532 +
 533 +static void *malloc(int size)
 534 +{
 535 +       void *p;
 536 +
 537 +       if (size < 0)
 538 +               error("Malloc error");
 539 +       if (!malloc_ptr)
 540 +               malloc_ptr = free_mem_ptr;
 541 +
 542 +       malloc_ptr = (malloc_ptr + 3) & ~3;     /* Align */
 543 +
 544 +       p = (void *)malloc_ptr;
 545 +       malloc_ptr += size;
 546 +
 547 +       if (free_mem_end_ptr && malloc_ptr >= free_mem_end_ptr)
 548 +               error("Out of memory");
 549 +
 550 +       malloc_count++;
 551 +       return p;
 552 +}
 553 +
 554 +static void free(void *where)
 555 +{
 556 +       malloc_count--;
 557 +       if (!malloc_count)
 558 +               malloc_ptr = free_mem_ptr;
 559 +}
 560 +
 561 +#define large_malloc(a) malloc(a)
 562 +#define large_free(a) free(a)
 563 +
 564 +#define set_error_fn(x)
 565 +
 566 +#define INIT
 567 +
 568 +#else /* STATIC */
 569 +
 570 +/* Code active when compiled standalone for use when loading ramdisk: */
 571 +
 572 +#include <linux/kernel.h>
 573 +#include <linux/fs.h>
 574 +#include <linux/string.h>
 575 +#include <linux/vmalloc.h>
 576 +
 577 +/* Use defines rather than static inline in order to avoid spurious
 578 + * warnings when not needed (indeed large_malloc / large_free are not
 579 + * needed by inflate */
 580 +
 581 +#define malloc(a) kmalloc(a, GFP_KERNEL)
 582 +#define free(a) kfree(a)
 583 +
 584 +#define large_malloc(a) vmalloc(a)
 585 +#define large_free(a) vfree(a)
 586 +
 587 +static void(*error)(char *m);
 588 +#define set_error_fn(x) error = x;
 589 +
 590 +#define INIT __init
 591 +#define STATIC
 592 +
 593 +#include <linux/init.h>
 594 +
 595 +#endif /* STATIC */
 596 +
 597 +#endif /* DECOMPR_MM_H */
 598 diff --git a/include/linux/decompress/unlzma.h b/include/linux/decompress/unlzma.h
 599 new file mode 100644
 600 index 0000000..7796538
 601 --- /dev/null
 602 +++ b/include/linux/decompress/unlzma.h
 603 @@ -0,0 +1,12 @@
 604 +#ifndef DECOMPRESS_UNLZMA_H
 605 +#define DECOMPRESS_UNLZMA_H
 606 +
 607 +int unlzma(unsigned char *, int,
 608 +          int(*fill)(void*, unsigned int),
 609 +          int(*flush)(void*, unsigned int),
 610 +          unsigned char *output,
 611 +          int *posp,
 612 +          void(*error)(char *x)
 613 +       );
 614 +
 615 +#endif
 616 diff --git a/init/Kconfig b/init/Kconfig
 617 index 6a5c5fe..38396ec 100644
 618 --- a/init/Kconfig
 619 +++ b/init/Kconfig
 620 @@ -101,6 +101,66 @@ config LOCALVERSION_AUTO
 621
 622           which is done within the script "scripts/setlocalversion".)
 623
 624 +config HAVE_KERNEL_GZIP
 625 +       bool
 626 +
 627 +config HAVE_KERNEL_BZIP2
 628 +       bool
 629 +
 630 +config HAVE_KERNEL_LZMA
 631 +       bool
 632 +
 633 +choice
 634 +       prompt "Kernel compression mode"
 635 +       default KERNEL_GZIP
 636 +       depends on HAVE_KERNEL_GZIP || HAVE_KERNEL_BZIP2 || HAVE_KERNEL_LZMA
 637 +       help
 638 +         The linux kernel is a kind of self-extracting executable.
 639 +         Several compression algorithms are available, which differ
 640 +         in efficiency, compression and decompression speed.
 641 +         Compression speed is only relevant when building a kernel.
 642 +         Decompression speed is relevant at each boot.
 643 +
 644 +         If you have any problems with bzip2 or lzma compressed
 645 +         kernels, mail me (Alain Knaff) <alain@knaff.lu>. (An older
 646 +         version of this functionality (bzip2 only), for 2.4, was
 647 +         supplied by Christian Ludwig)
 648 +
 649 +         High compression options are mostly useful for users, who
 650 +         are low on disk space (embedded systems), but for whom ram
 651 +         size matters less.
 652 +
 653 +         If in doubt, select 'gzip'
 654 +
 655 +config KERNEL_GZIP
 656 +       bool "Gzip"
 657 +       depends on HAVE_KERNEL_GZIP
 658 +       help
 659 +         The old and tried gzip compression. Its compression ratio is
 660 +         the poorest among the 3 choices; however its speed (both
 661 +         compression and decompression) is the fastest.
 662 +
 663 +config KERNEL_BZIP2
 664 +       bool "Bzip2"
 665 +       depends on HAVE_KERNEL_BZIP2
 666 +       help
 667 +         Its compression ratio and speed is intermediate.
 668 +         Decompression speed is slowest among the three.  The kernel
 669 +         size is about 10% smaller with bzip2, in comparison to gzip.
 670 +         Bzip2 uses a large amount of memory. For modern kernels you
 671 +         will need at least 8MB RAM or more for booting.
 672 +
 673 +config KERNEL_LZMA
 674 +       bool "LZMA"
 675 +       depends on HAVE_KERNEL_LZMA
 676 +       help
 677 +         The most recent compression algorithm.
 678 +         Its ratio is best, decompression speed is between the other
 679 +         two. Compression is slowest.  The kernel size is about 33%
 680 +         smaller with LZMA in comparison to gzip.
 681 +
 682 +endchoice
 683 +
 684  config SWAP
 685         bool "Support for paging of anonymous memory (swap)"
 686         depends on MMU && BLOCK
 687 diff --git a/init/do_mounts_rd.c b/init/do_mounts_rd.c
 688 index 0f0f0cf..027a402 100644
 689 --- a/init/do_mounts_rd.c
 690 +++ b/init/do_mounts_rd.c
 691 @@ -11,6 +11,9 @@
 692  #include "do_mounts.h"
 693  #include "../fs/squashfs/squashfs_fs.h"
 694
 695 +#include <linux/decompress/generic.h>
 696 +
 697 +
 698  int __initdata rd_prompt = 1;/* 1 = prompt for RAM disk, 0 = don't prompt */
 699
 700  static int __init prompt_ramdisk(char *str)
 701 @@ -29,7 +32,7 @@ static int __init ramdisk_start_setup(char *str)
 702  }
 703  __setup("ramdisk_start=", ramdisk_start_setup);
 704
 705 -static int __init crd_load(int in_fd, int out_fd);
 706 +static int __init crd_load(int in_fd, int out_fd, decompress_fn deco);
 707
 708  /*
 709   * This routine tries to find a RAM disk image to load, and returns the
 710 @@ -38,15 +41,15 @@ static int __init crd_load(int in_fd, int out_fd);
 711   * numbers could not be found.
 712   *
 713   * We currently check for the following magic numbers:
 714 - *     minix
 715 - *     ext2
 716 + *     minix
 717 + *     ext2
 718   *     romfs
 719   *     cramfs
 720   *     squashfs
 721 - *     gzip
 722 + *     gzip
 723   */
 724 -static int __init
 725 -identify_ramdisk_image(int fd, int start_block)
 726 +static int __init
 727 +identify_ramdisk_image(int fd, int start_block, decompress_fn *decompressor)
 728  {
 729         const int size = 512;
 730         struct minix_super_block *minixsb;
 731 @@ -56,6 +59,7 @@ identify_ramdisk_image(int fd, int start_block)
 732         struct squashfs_super_block *squashfsb;
 733         int nblocks = -1;
 734         unsigned char *buf;
 735 +       const char *compress_name;
 736
 737         buf = kmalloc(size, GFP_KERNEL);
 738         if (!buf)
 739 @@ -69,18 +73,19 @@ identify_ramdisk_image(int fd, int start_block)
 740         memset(buf, 0xe5, size);
 741
 742         /*
 743 -        * Read block 0 to test for gzipped kernel
 744 +        * Read block 0 to test for compressed kernel
 745          */
 746         sys_lseek(fd, start_block * BLOCK_SIZE, 0);
 747         sys_read(fd, buf, size);
 748
 749 -       /*
 750 -        * If it matches the gzip magic numbers, return 0
 751 -        */
 752 -       if (buf[0] == 037 && ((buf[1] == 0213) || (buf[1] == 0236))) {
 753 -               printk(KERN_NOTICE
 754 -                      "RAMDISK: Compressed image found at block %d\n",
 755 -                      start_block);
 756 +       *decompressor = decompress_method(buf, size, &compress_name);
 757 +       if (compress_name) {
 758 +               printk(KERN_NOTICE "RAMDISK: %s image found at block %d\n",
 759 +                      compress_name, start_block);
 760 +               if (!*decompressor)
 761 +                       printk(KERN_EMERG
 762 +                              "RAMDISK: %s decompressor not configured!\n",
 763 +                              compress_name);
 764                 nblocks = 0;
 765                 goto done;
 766         }
 767 @@ -142,7 +147,7 @@ identify_ramdisk_image(int fd, int start_block)
 768         printk(KERN_NOTICE
 769                "RAMDISK: Couldn't find valid RAM disk image starting at %d.\n",
 770                start_block);
 771 -
 772 +
 773  done:
 774         sys_lseek(fd, start_block * BLOCK_SIZE, 0);
 775         kfree(buf);
 776 @@ -157,6 +162,7 @@ int __init rd_load_image(char *from)
 777         int nblocks, i, disk;
 778         char *buf = NULL;
 779         unsigned short rotate = 0;
 780 +       decompress_fn decompressor = NULL;
 781  #if !defined(CONFIG_S390) && !defined(CONFIG_PPC_ISERIES)
 782         char rotator[4] = { '|' , '/' , '-' , '\\' };
 783  #endif
 784 @@ -169,12 +175,12 @@ int __init rd_load_image(char *from)
 785         if (in_fd < 0)
 786                 goto noclose_input;
 787
 788 -       nblocks = identify_ramdisk_image(in_fd, rd_image_start);
 789 +       nblocks = identify_ramdisk_image(in_fd, rd_image_start, &decompressor);
 790         if (nblocks < 0)
 791                 goto done;
 792
 793         if (nblocks == 0) {
 794 -               if (crd_load(in_fd, out_fd) == 0)
 795 +               if (crd_load(in_fd, out_fd, decompressor) == 0)
 796                         goto successful_load;
 797                 goto done;
 798         }
 799 @@ -200,7 +206,7 @@ int __init rd_load_image(char *from)
 800                        nblocks, rd_blocks);
 801                 goto done;
 802         }
 803 -
 804 +
 805         /*
 806          * OK, time to copy in the data
 807          */
 808 @@ -273,138 +279,48 @@ int __init rd_load_disk(int n)
 809         return rd_load_image("/dev/root");
 810  }
 811
 812 -/*
 813 - * gzip declarations
 814 - */
 815 -
 816 -#define OF(args)  args
 817 -
 818 -#ifndef memzero
 819 -#define memzero(s, n)     memset ((s), 0, (n))
 820 -#endif
 821 -
 822 -typedef unsigned char  uch;
 823 -typedef unsigned short ush;
 824 -typedef unsigned long  ulg;
 825 -
 826 -#define INBUFSIZ 4096
 827 -#define WSIZE 0x8000    /* window size--must be a power of two, and */
 828 -                       /*  at least 32K for zip's deflate method */
 829 -
 830 -static uch *inbuf;
 831 -static uch *window;
 832 -
 833 -static unsigned insize;  /* valid bytes in inbuf */
 834 -static unsigned inptr;   /* index of next byte to be processed in inbuf */
 835 -static unsigned outcnt;  /* bytes in output buffer */
 836  static int exit_code;
 837 -static int unzip_error;
 838 -static long bytes_out;
 839 +static int decompress_error;
 840  static int crd_infd, crd_outfd;
 841
 842 -#define get_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf())
 843 -
 844 -/* Diagnostic functions (stubbed out) */
 845 -#define Assert(cond,msg)
 846 -#define Trace(x)
 847 -#define Tracev(x)
 848 -#define Tracevv(x)
 849 -#define Tracec(c,x)
 850 -#define Tracecv(c,x)
 851 -
 852 -#define STATIC static
 853 -#define INIT __init
 854 -
 855 -static int  __init fill_inbuf(void);
 856 -static void __init flush_window(void);
 857 -static void __init error(char *m);
 858 -
 859 -#define NO_INFLATE_MALLOC
 860 -
 861 -#include "../lib/inflate.c"
 862 -
 863 -/* ===========================================================================
 864 - * Fill the input buffer. This is called only when the buffer is empty
 865 - * and at least one byte is really needed.
 866 - * Returning -1 does not guarantee that gunzip() will ever return.
 867 - */
 868 -static int __init fill_inbuf(void)
 869 +static int __init compr_fill(void *buf, unsigned int len)
 870  {
 871 -       if (exit_code) return -1;
 872 -
 873 -       insize = sys_read(crd_infd, inbuf, INBUFSIZ);
 874 -       if (insize == 0) {
 875 -               error("RAMDISK: ran out of compressed data");
 876 -               return -1;
 877 -       }
 878 -
 879 -       inptr = 1;
 880 -
 881 -       return inbuf[0];
 882 +       int r = sys_read(crd_infd, buf, len);
 883 +       if (r < 0)
 884 +               printk(KERN_ERR "RAMDISK: error while reading compressed data");
 885 +       else if (r == 0)
 886 +               printk(KERN_ERR "RAMDISK: EOF while reading compressed data");
 887 +       return r;
 888  }
 889
 890 -/* ===========================================================================
 891 - * Write the output window window[0..outcnt-1] and update crc and bytes_out.
 892 - * (Used for the decompressed data only.)
 893 - */
 894 -static void __init flush_window(void)
 895 +static int __init compr_flush(void *window, unsigned int outcnt)
 896  {
 897 -    ulg c = crc;         /* temporary variable */
 898 -    unsigned n, written;
 899 -    uch *in, ch;
 900 -
 901 -    written = sys_write(crd_outfd, window, outcnt);
 902 -    if (written != outcnt && unzip_error == 0) {
 903 -       printk(KERN_ERR "RAMDISK: incomplete write (%d != %d) %ld\n",
 904 -              written, outcnt, bytes_out);
 905 -       unzip_error = 1;
 906 -    }
 907 -    in = window;
 908 -    for (n = 0; n < outcnt; n++) {
 909 -           ch = *in++;
 910 -           c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
 911 -    }
 912 -    crc = c;
 913 -    bytes_out += (ulg)outcnt;
 914 -    outcnt = 0;
 915 +       int written = sys_write(crd_outfd, window, outcnt);
 916 +       if (written != outcnt) {
 917 +               if (decompress_error == 0)
 918 +                       printk(KERN_ERR
 919 +                              "RAMDISK: incomplete write (%d != %d)\n",
 920 +                              written, outcnt);
 921 +               decompress_error = 1;
 922 +               return -1;
 923 +       }
 924 +       return outcnt;
 925  }
 926
 927  static void __init error(char *x)
 928  {
 929         printk(KERN_ERR "%s\n", x);
 930         exit_code = 1;
 931 -       unzip_error = 1;
 932 +       decompress_error = 1;
 933  }
 934
 935 -static int __init crd_load(int in_fd, int out_fd)
 936 +static int __init crd_load(int in_fd, int out_fd, decompress_fn deco)
 937  {
 938         int result;
 939 -
 940 -       insize = 0;             /* valid bytes in inbuf */
 941 -       inptr = 0;              /* index of next byte to be processed in inbuf */
 942 -       outcnt = 0;             /* bytes in output buffer */
 943 -       exit_code = 0;
 944 -       bytes_out = 0;
 945 -       crc = (ulg)0xffffffffL; /* shift register contents */
 946 -
 947         crd_infd = in_fd;
 948         crd_outfd = out_fd;
 949 -       inbuf = kmalloc(INBUFSIZ, GFP_KERNEL);
 950 -       if (!inbuf) {
 951 -               printk(KERN_ERR "RAMDISK: Couldn't allocate gzip buffer\n");
 952 -               return -1;
 953 -       }
 954 -       window = kmalloc(WSIZE, GFP_KERNEL);
 955 -       if (!window) {
 956 -               printk(KERN_ERR "RAMDISK: Couldn't allocate gzip window\n");
 957 -               kfree(inbuf);
 958 -               return -1;
 959 -       }
 960 -       makecrc();
 961 -       result = gunzip();
 962 -       if (unzip_error)
 963 +       result = deco(NULL, 0, compr_fill, compr_flush, NULL, NULL, error);
 964 +       if (decompress_error)
 965                 result = 1;
 966 -       kfree(inbuf);
 967 -       kfree(window);
 968         return result;
 969  }
 970 diff --git a/init/initramfs.c b/init/initramfs.c
 971 index d9c941c..7dcde7e 100644
 972 --- a/init/initramfs.c
 973 +++ b/init/initramfs.c
 974 @@ -390,11 +390,13 @@ static int __init write_buffer(char *buf, unsigned len)
 975         return len - count;
 976  }
 977
 978 -static void __init flush_buffer(char *buf, unsigned len)
 979 +static int __init flush_buffer(void *bufv, unsigned len)
 980  {
 981 +       char *buf = (char *) bufv;
 982         int written;
 983 +       int origLen = len;
 984         if (message)
 985 -               return;
 986 +               return -1;
 987         while ((written = write_buffer(buf, len)) < len && !message) {
 988                 char c = buf[written];
 989                 if (c == '0') {
 990 @@ -408,84 +410,28 @@ static void __init flush_buffer(char *buf, unsigned len)
 991                 } else
 992                         error("junk in compressed archive");
 993         }
 994 +       return origLen;
 995  }
 996
 997 -/*
 998 - * gzip declarations
 999 - */
1000 +static unsigned my_inptr;   /* index of next byte to be processed in inbuf */
1001
1002 -#define OF(args)  args
1003 -
1004 -#ifndef memzero
1005 -#define memzero(s, n)     memset ((s), 0, (n))
1006 -#endif
1007 -
1008 -typedef unsigned char  uch;
1009 -typedef unsigned short ush;
1010 -typedef unsigned long  ulg;
1011 -
1012 -#define WSIZE 0x8000    /* window size--must be a power of two, and */
1013 -                       /*  at least 32K for zip's deflate method */
1014 -
1015 -static uch *inbuf;
1016 -static uch *window;
1017 -
1018 -static unsigned insize;  /* valid bytes in inbuf */
1019 -static unsigned inptr;   /* index of next byte to be processed in inbuf */
1020 -static unsigned outcnt;  /* bytes in output buffer */
1021 -static long bytes_out;
1022 -
1023 -#define get_byte()  (inptr < insize ? inbuf[inptr++] : -1)
1024 -
1025 -/* Diagnostic functions (stubbed out) */
1026 -#define Assert(cond,msg)
1027 -#define Trace(x)
1028 -#define Tracev(x)
1029 -#define Tracevv(x)
1030 -#define Tracec(c,x)
1031 -#define Tracecv(c,x)
1032 -
1033 -#define STATIC static
1034 -#define INIT __init
1035 -
1036 -static void __init flush_window(void);
1037 -static void __init error(char *m);
1038 -
1039 -#define NO_INFLATE_MALLOC
1040 -
1041 -#include "../lib/inflate.c"
1042 -
1043 -/* ===========================================================================
1044 - * Write the output window window[0..outcnt-1] and update crc and bytes_out.
1045 - * (Used for the decompressed data only.)
1046 - */
1047 -static void __init flush_window(void)
1048 -{
1049 -       ulg c = crc;         /* temporary variable */
1050 -       unsigned n;
1051 -       uch *in, ch;
1052 -
1053 -       flush_buffer(window, outcnt);
1054 -       in = window;
1055 -       for (n = 0; n < outcnt; n++) {
1056 -               ch = *in++;
1057 -               c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
1058 -       }
1059 -       crc = c;
1060 -       bytes_out += (ulg)outcnt;
1061 -       outcnt = 0;
1062 -}
1063 +#include <linux/decompress/generic.h>
1064
1065  static char * __init unpack_to_rootfs(char *buf, unsigned len, int check_only)
1066  {
1067         int written;
1068 +       decompress_fn decompress;
1069 +       const char *compress_name;
1070 +       static __initdata char msg_buf[64];
1071 +
1072         dry_run = check_only;
1073         header_buf = kmalloc(110, GFP_KERNEL);
1074         symlink_buf = kmalloc(PATH_MAX + N_ALIGN(PATH_MAX) + 1, GFP_KERNEL);
1075         name_buf = kmalloc(N_ALIGN(PATH_MAX), GFP_KERNEL);
1076 -       window = kmalloc(WSIZE, GFP_KERNEL);
1077 -       if (!window || !header_buf || !symlink_buf || !name_buf)
1078 +
1079 +       if (!header_buf || !symlink_buf || !name_buf)
1080                 panic("can't allocate buffers");
1081 +
1082         state = Start;
1083         this_header = 0;
1084         message = NULL;
1085 @@ -505,22 +451,25 @@ static char * __init unpack_to_rootfs(char *buf, unsigned len, int check_only)
1086                         continue;
1087                 }
1088                 this_header = 0;
1089 -               insize = len;
1090 -               inbuf = buf;
1091 -               inptr = 0;
1092 -               outcnt = 0;             /* bytes in output buffer */
1093 -               bytes_out = 0;
1094 -               crc = (ulg)0xffffffffL; /* shift register contents */
1095 -               makecrc();
1096 -               gunzip();
1097 +               decompress = decompress_method(buf, len, &compress_name);
1098 +               if (decompress)
1099 +                       decompress(buf, len, NULL, flush_buffer, NULL,
1100 +                                  &my_inptr, error);
1101 +               else if (compress_name) {
1102 +                       if (!message) {
1103 +                               snprintf(msg_buf, sizeof msg_buf,
1104 +                                        "compression method %s not configured",
1105 +                                        compress_name);
1106 +                               message = msg_buf;
1107 +                       }
1108 +               }
1109                 if (state != Reset)
1110 -                       error("junk in gzipped archive");
1111 -               this_header = saved_offset + inptr;
1112 -               buf += inptr;
1113 -               len -= inptr;
1114 +                       error("junk in compressed archive");
1115 +               this_header = saved_offset + my_inptr;
1116 +               buf += my_inptr;
1117 +               len -= my_inptr;
1118         }
1119         dir_utime();
1120 -       kfree(window);
1121         kfree(name_buf);
1122         kfree(symlink_buf);
1123         kfree(header_buf);
1124 @@ -579,7 +528,7 @@ static int __init populate_rootfs(void)
1125         char *err = unpack_to_rootfs(__initramfs_start,
1126                          __initramfs_end - __initramfs_start, 0);
1127         if (err)
1128 -               panic(err);
1129 +               panic(err);     /* Failed to decompress INTERNAL initramfs */
1130         if (initrd_start) {
1131  #ifdef CONFIG_BLK_DEV_RAM
1132                 int fd;
1133 @@ -605,9 +554,12 @@ static int __init populate_rootfs(void)
1134                 printk(KERN_INFO "Unpacking initramfs...");
1135                 err = unpack_to_rootfs((char *)initrd_start,
1136                         initrd_end - initrd_start, 0);
1137 -               if (err)
1138 -                       panic(err);
1139 -               printk(" done\n");
1140 +               if (err) {
1141 +                       printk(" failed!\n");
1142 +                       printk(KERN_EMERG "%s\n", err);
1143 +               } else {
1144 +                       printk(" done\n");
1145 +               }
1146                 free_initrd();
1147  #endif
1148         }
1149 diff --git a/lib/Kconfig b/lib/Kconfig
1150 index 03c2c24..daa4818 100644
1151 --- a/lib/Kconfig
1152 +++ b/lib/Kconfig
1153 @@ -98,6 +98,20 @@ config LZO_DECOMPRESS
1154         tristate
1155
1156  #
1157 +# These all provide a common interface (hence the apparent duplication with
1158 +# ZLIB_INFLATE; DECOMPRESS_GZIP is just a wrapper.)
1159 +#
1160 +config DECOMPRESS_GZIP
1161 +       select ZLIB_INFLATE
1162 +       tristate
1163 +
1164 +config DECOMPRESS_BZIP2
1165 +       tristate
1166 +
1167 +config DECOMPRESS_LZMA
1168 +       tristate
1169 +
1170 +#
1171  # Generic allocator support is selected if needed
1172  #
1173  config GENERIC_ALLOCATOR
1174 diff --git a/lib/Makefile b/lib/Makefile
1175 index 32b0e64..790de7c 100644
1176 --- a/lib/Makefile
1177 +++ b/lib/Makefile
1178 @@ -11,7 +11,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
1179          rbtree.o radix-tree.o dump_stack.o \
1180          idr.o int_sqrt.o extable.o prio_tree.o \
1181          sha1.o irq_regs.o reciprocal_div.o argv_split.o \
1182 -        proportions.o prio_heap.o ratelimit.o show_mem.o is_single_threaded.o
1183 +        proportions.o prio_heap.o ratelimit.o show_mem.o \
1184 +        is_single_threaded.o decompress.o
1185
1186  lib-$(CONFIG_MMU) += ioremap.o
1187  lib-$(CONFIG_SMP) += cpumask.o
1188 @@ -65,6 +66,10 @@ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
1189  obj-$(CONFIG_LZO_COMPRESS) += lzo/
1190  obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
1191
1192 +lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o
1193 +lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
1194 +lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o
1195 +
1196  obj-$(CONFIG_TEXTSEARCH) += textsearch.o
1197  obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
1198  obj-$(CONFIG_TEXTSEARCH_BM) += ts_bm.o
1199 diff --git a/lib/decompress.c b/lib/decompress.c
1200 new file mode 100644
1201 index 0000000..d2842f5
1202 --- /dev/null
1203 +++ b/lib/decompress.c
1204 @@ -0,0 +1,54 @@
1205 +/*
1206 + * decompress.c
1207 + *
1208 + * Detect the decompression method based on magic number
1209 + */
1210 +
1211 +#include <linux/decompress/generic.h>
1212 +
1213 +#include <linux/decompress/bunzip2.h>
1214 +#include <linux/decompress/unlzma.h>
1215 +#include <linux/decompress/inflate.h>
1216 +
1217 +#include <linux/types.h>
1218 +#include <linux/string.h>
1219 +
1220 +#ifndef CONFIG_DECOMPRESS_GZIP
1221 +# define gunzip NULL
1222 +#endif
1223 +#ifndef CONFIG_DECOMPRESS_BZIP2
1224 +# define bunzip2 NULL
1225 +#endif
1226 +#ifndef CONFIG_DECOMPRESS_LZMA
1227 +# define unlzma NULL
1228 +#endif
1229 +
1230 +static const struct compress_format {
1231 +       unsigned char magic[2];
1232 +       const char *name;
1233 +       decompress_fn decompressor;
1234 +} compressed_formats[] = {
1235 +       { {037, 0213}, "gzip", gunzip },
1236 +       { {037, 0236}, "gzip", gunzip },
1237 +       { {0x42, 0x5a}, "bzip2", bunzip2 },
1238 +       { {0x5d, 0x00}, "lzma", unlzma },
1239 +       { {0, 0}, NULL, NULL }
1240 +};
1241 +
1242 +decompress_fn decompress_method(const unsigned char *inbuf, int len,
1243 +                               const char **name)
1244 +{
1245 +       const struct compress_format *cf;
1246 +
1247 +       if (len < 2)
1248 +               return NULL;    /* Need at least this much... */
1249 +
1250 +       for (cf = compressed_formats; cf->name; cf++) {
1251 +               if (!memcmp(inbuf, cf->magic, 2))
1252 +                       break;
1253 +
1254 +       }
1255 +       if (name)
1256 +               *name = cf->name;
1257 +       return cf->decompressor;
1258 +}
1259 diff --git a/lib/decompress_bunzip2.c b/lib/decompress_bunzip2.c
1260 new file mode 100644
1261 index 0000000..5d3ddb5
1262 --- /dev/null
1263 +++ b/lib/decompress_bunzip2.c
1264 @@ -0,0 +1,735 @@
1265 +/* vi: set sw = 4 ts = 4: */
1266 +/*     Small bzip2 deflate implementation, by Rob Landley (rob@landley.net).
1267 +
1268 +       Based on bzip2 decompression code by Julian R Seward (jseward@acm.org),
1269 +       which also acknowledges contributions by Mike Burrows, David Wheeler,
1270 +       Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten,
1271 +       Robert Sedgewick, and Jon L. Bentley.
1272 +
1273 +       This code is licensed under the LGPLv2:
1274 +               LGPL (http://www.gnu.org/copyleft/lgpl.html
1275 +*/
1276 +
1277 +/*
1278 +       Size and speed optimizations by Manuel Novoa III  (mjn3@codepoet.org).
1279 +
1280 +       More efficient reading of Huffman codes, a streamlined read_bunzip()
1281 +       function, and various other tweaks.  In (limited) tests, approximately
1282 +       20% faster than bzcat on x86 and about 10% faster on arm.
1283 +
1284 +       Note that about 2/3 of the time is spent in read_unzip() reversing
1285 +       the Burrows-Wheeler transformation.  Much of that time is delay
1286 +       resulting from cache misses.
1287 +
1288 +       I would ask that anyone benefiting from this work, especially those
1289 +       using it in commercial products, consider making a donation to my local
1290 +       non-profit hospice organization in the name of the woman I loved, who
1291 +       passed away Feb. 12, 2003.
1292 +
1293 +               In memory of Toni W. Hagan
1294 +
1295 +               Hospice of Acadiana, Inc.
1296 +               2600 Johnston St., Suite 200
1297 +               Lafayette, LA 70503-3240
1298 +
1299 +               Phone (337) 232-1234 or 1-800-738-2226
1300 +               Fax   (337) 232-1297
1301 +
1302 +               http://www.hospiceacadiana.com/
1303 +
1304 +       Manuel
1305 + */
1306 +
1307 +/*
1308 +       Made it fit for running in Linux Kernel by Alain Knaff (alain@knaff.lu)
1309 +*/
1310 +
1311 +
1312 +#ifndef STATIC
1313 +#include <linux/decompress/bunzip2.h>
1314 +#endif /* !STATIC */
1315 +
1316 +#include <linux/decompress/mm.h>
1317 +
1318 +#ifndef INT_MAX
1319 +#define INT_MAX 0x7fffffff
1320 +#endif
1321 +
1322 +/* Constants for Huffman coding */
1323 +#define MAX_GROUPS             6
1324 +#define GROUP_SIZE             50      /* 64 would have been more efficient */
1325 +#define MAX_HUFCODE_BITS       20      /* Longest Huffman code allowed */
1326 +#define MAX_SYMBOLS            258     /* 256 literals + RUNA + RUNB */
1327 +#define SYMBOL_RUNA            0
1328 +#define SYMBOL_RUNB            1
1329 +
1330 +/* Status return values */
1331 +#define RETVAL_OK                      0
1332 +#define RETVAL_LAST_BLOCK              (-1)
1333 +#define RETVAL_NOT_BZIP_DATA           (-2)
1334 +#define RETVAL_UNEXPECTED_INPUT_EOF    (-3)
1335 +#define RETVAL_UNEXPECTED_OUTPUT_EOF   (-4)
1336 +#define RETVAL_DATA_ERROR              (-5)
1337 +#define RETVAL_OUT_OF_MEMORY           (-6)
1338 +#define RETVAL_OBSOLETE_INPUT          (-7)
1339 +
1340 +/* Other housekeeping constants */
1341 +#define BZIP2_IOBUF_SIZE               4096
1342 +
1343 +/* This is what we know about each Huffman coding group */
1344 +struct group_data {
1345 +       /* We have an extra slot at the end of limit[] for a sentinal value. */
1346 +       int limit[MAX_HUFCODE_BITS+1];
1347 +       int base[MAX_HUFCODE_BITS];
1348 +       int permute[MAX_SYMBOLS];
1349 +       int minLen, maxLen;
1350 +};
1351 +
1352 +/* Structure holding all the housekeeping data, including IO buffers and
1353 +   memory that persists between calls to bunzip */
1354 +struct bunzip_data {
1355 +       /* State for interrupting output loop */
1356 +       int writeCopies, writePos, writeRunCountdown, writeCount, writeCurrent;
1357 +       /* I/O tracking data (file handles, buffers, positions, etc.) */
1358 +       int (*fill)(void*, unsigned int);
1359 +       int inbufCount, inbufPos /*, outbufPos*/;
1360 +       unsigned char *inbuf /*,*outbuf*/;
1361 +       unsigned int inbufBitCount, inbufBits;
1362 +       /* The CRC values stored in the block header and calculated from the
1363 +       data */
1364 +       unsigned int crc32Table[256], headerCRC, totalCRC, writeCRC;
1365 +       /* Intermediate buffer and its size (in bytes) */
1366 +       unsigned int *dbuf, dbufSize;
1367 +       /* These things are a bit too big to go on the stack */
1368 +       unsigned char selectors[32768];         /* nSelectors = 15 bits */
1369 +       struct group_data groups[MAX_GROUPS];   /* Huffman coding tables */
1370 +       int io_error;                   /* non-zero if we have IO error */
1371 +};
1372 +
1373 +
1374 +/* Return the next nnn bits of input.  All reads from the compressed input
1375 +   are done through this function.  All reads are big endian */
1376 +static unsigned int INIT get_bits(struct bunzip_data *bd, char bits_wanted)
1377 +{
1378 +       unsigned int bits = 0;
1379 +
1380 +       /* If we need to get more data from the byte buffer, do so.
1381 +          (Loop getting one byte at a time to enforce endianness and avoid
1382 +          unaligned access.) */
1383 +       while (bd->inbufBitCount < bits_wanted) {
1384 +               /* If we need to read more data from file into byte buffer, do
1385 +                  so */
1386 +               if (bd->inbufPos == bd->inbufCount) {
1387 +                       if (bd->io_error)
1388 +                               return 0;
1389 +                       bd->inbufCount = bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE);
1390 +                       if (bd->inbufCount <= 0) {
1391 +                               bd->io_error = RETVAL_UNEXPECTED_INPUT_EOF;
1392 +                               return 0;
1393 +                       }
1394 +                       bd->inbufPos = 0;
1395 +               }
1396 +               /* Avoid 32-bit overflow (dump bit buffer to top of output) */
1397 +               if (bd->inbufBitCount >= 24) {
1398 +                       bits = bd->inbufBits&((1 << bd->inbufBitCount)-1);
1399 +                       bits_wanted -= bd->inbufBitCount;
1400 +                       bits <<= bits_wanted;
1401 +                       bd->inbufBitCount = 0;
1402 +               }
1403 +               /* Grab next 8 bits of input from buffer. */
1404 +               bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
1405 +               bd->inbufBitCount += 8;
1406 +       }
1407 +       /* Calculate result */
1408 +       bd->inbufBitCount -= bits_wanted;
1409 +       bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1);
1410 +
1411 +       return bits;
1412 +}
1413 +
1414 +/* Unpacks the next block and sets up for the inverse burrows-wheeler step. */
1415 +
1416 +static int INIT get_next_block(struct bunzip_data *bd)
1417 +{
1418 +       struct group_data *hufGroup = NULL;
1419 +       int *base = NULL;
1420 +       int *limit = NULL;
1421 +       int dbufCount, nextSym, dbufSize, groupCount, selector,
1422 +               i, j, k, t, runPos, symCount, symTotal, nSelectors,
1423 +               byteCount[256];
1424 +       unsigned char uc, symToByte[256], mtfSymbol[256], *selectors;
1425 +       unsigned int *dbuf, origPtr;
1426 +
1427 +       dbuf = bd->dbuf;
1428 +       dbufSize = bd->dbufSize;
1429 +       selectors = bd->selectors;
1430 +
1431 +       /* Read in header signature and CRC, then validate signature.
1432 +          (last block signature means CRC is for whole file, return now) */
1433 +       i = get_bits(bd, 24);
1434 +       j = get_bits(bd, 24);
1435 +       bd->headerCRC = get_bits(bd, 32);
1436 +       if ((i == 0x177245) && (j == 0x385090))
1437 +               return RETVAL_LAST_BLOCK;
1438 +       if ((i != 0x314159) || (j != 0x265359))
1439 +               return RETVAL_NOT_BZIP_DATA;
1440 +       /* We can add support for blockRandomised if anybody complains.
1441 +          There was some code for this in busybox 1.0.0-pre3, but nobody ever
1442 +          noticed that it didn't actually work. */
1443 +       if (get_bits(bd, 1))
1444 +               return RETVAL_OBSOLETE_INPUT;
1445 +       origPtr = get_bits(bd, 24);
1446 +       if (origPtr > dbufSize)
1447 +               return RETVAL_DATA_ERROR;
1448 +       /* mapping table: if some byte values are never used (encoding things
1449 +          like ascii text), the compression code removes the gaps to have fewer
1450 +          symbols to deal with, and writes a sparse bitfield indicating which
1451 +          values were present.  We make a translation table to convert the
1452 +          symbols back to the corresponding bytes. */
1453 +       t = get_bits(bd, 16);
1454 +       symTotal = 0;
1455 +       for (i = 0; i < 16; i++) {
1456 +               if (t&(1 << (15-i))) {
1457 +                       k = get_bits(bd, 16);
1458 +                       for (j = 0; j < 16; j++)
1459 +                               if (k&(1 << (15-j)))
1460 +                                       symToByte[symTotal++] = (16*i)+j;
1461 +               }
1462 +       }
1463 +       /* How many different Huffman coding groups does this block use? */
1464 +       groupCount = get_bits(bd, 3);
1465 +       if (groupCount < 2 || groupCount > MAX_GROUPS)
1466 +               return RETVAL_DATA_ERROR;
1467 +       /* nSelectors: Every GROUP_SIZE many symbols we select a new
1468 +          Huffman coding group.  Read in the group selector list,
1469 +          which is stored as MTF encoded bit runs.  (MTF = Move To
1470 +          Front, as each value is used it's moved to the start of the
1471 +          list.) */
1472 +       nSelectors = get_bits(bd, 15);
1473 +       if (!nSelectors)
1474 +               return RETVAL_DATA_ERROR;
1475 +       for (i = 0; i < groupCount; i++)
1476 +               mtfSymbol[i] = i;
1477 +       for (i = 0; i < nSelectors; i++) {
1478 +               /* Get next value */
1479 +               for (j = 0; get_bits(bd, 1); j++)
1480 +                       if (j >= groupCount)
1481 +                               return RETVAL_DATA_ERROR;
1482 +               /* Decode MTF to get the next selector */
1483 +               uc = mtfSymbol[j];
1484 +               for (; j; j--)
1485 +                       mtfSymbol[j] = mtfSymbol[j-1];
1486 +               mtfSymbol[0] = selectors[i] = uc;
1487 +       }
1488 +       /* Read the Huffman coding tables for each group, which code
1489 +          for symTotal literal symbols, plus two run symbols (RUNA,
1490 +          RUNB) */
1491 +       symCount = symTotal+2;
1492 +       for (j = 0; j < groupCount; j++) {
1493 +               unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1];
1494 +               int     minLen, maxLen, pp;
1495 +               /* Read Huffman code lengths for each symbol.  They're
1496 +                  stored in a way similar to mtf; record a starting
1497 +                  value for the first symbol, and an offset from the
1498 +                  previous value for everys symbol after that.
1499 +                  (Subtracting 1 before the loop and then adding it
1500 +                  back at the end is an optimization that makes the
1501 +                  test inside the loop simpler: symbol length 0
1502 +                  becomes negative, so an unsigned inequality catches
1503 +                  it.) */
1504 +               t = get_bits(bd, 5)-1;
1505 +               for (i = 0; i < symCount; i++) {
1506 +                       for (;;) {
1507 +                               if (((unsigned)t) > (MAX_HUFCODE_BITS-1))
1508 +                                       return RETVAL_DATA_ERROR;
1509 +
1510 +                               /* If first bit is 0, stop.  Else
1511 +                                  second bit indicates whether to
1512 +                                  increment or decrement the value.
1513 +                                  Optimization: grab 2 bits and unget
1514 +                                  the second if the first was 0. */
1515 +
1516 +                               k = get_bits(bd, 2);
1517 +                               if (k < 2) {
1518 +                                       bd->inbufBitCount++;
1519 +                                       break;
1520 +                               }
1521 +                               /* Add one if second bit 1, else
1522 +                                * subtract 1.  Avoids if/else */
1523 +                               t += (((k+1)&2)-1);
1524 +                       }
1525 +                       /* Correct for the initial -1, to get the
1526 +                        * final symbol length */
1527 +                       length[i] = t+1;
1528 +               }
1529 +               /* Find largest and smallest lengths in this group */
1530 +               minLen = maxLen = length[0];
1531 +
1532 +               for (i = 1; i < symCount; i++) {
1533 +                       if (length[i] > maxLen)
1534 +                               maxLen = length[i];
1535 +                       else if (length[i] < minLen)
1536 +                               minLen = length[i];
1537 +               }
1538 +
1539 +               /* Calculate permute[], base[], and limit[] tables from
1540 +                * length[].
1541 +                *
1542 +                * permute[] is the lookup table for converting
1543 +                * Huffman coded symbols into decoded symbols.  base[]
1544 +                * is the amount to subtract from the value of a
1545 +                * Huffman symbol of a given length when using
1546 +                * permute[].
1547 +                *
1548 +                * limit[] indicates the largest numerical value a
1549 +                * symbol with a given number of bits can have.  This
1550 +                * is how the Huffman codes can vary in length: each
1551 +                * code with a value > limit[length] needs another
1552 +                * bit.
1553 +                */
1554 +               hufGroup = bd->groups+j;
1555 +               hufGroup->minLen = minLen;
1556 +               hufGroup->maxLen = maxLen;
1557 +               /* Note that minLen can't be smaller than 1, so we
1558 +                  adjust the base and limit array pointers so we're
1559 +                  not always wasting the first entry.  We do this
1560 +                  again when using them (during symbol decoding).*/
1561 +               base = hufGroup->base-1;
1562 +               limit = hufGroup->limit-1;
1563 +               /* Calculate permute[].  Concurently, initialize
1564 +                * temp[] and limit[]. */
1565 +               pp = 0;
1566 +               for (i = minLen; i <= maxLen; i++) {
1567 +                       temp[i] = limit[i] = 0;
1568 +                       for (t = 0; t < symCount; t++)
1569 +                               if (length[t] == i)
1570 +                                       hufGroup->permute[pp++] = t;
1571 +               }
1572 +               /* Count symbols coded for at each bit length */
1573 +               for (i = 0; i < symCount; i++)
1574 +                       temp[length[i]]++;
1575 +               /* Calculate limit[] (the largest symbol-coding value
1576 +                *at each bit length, which is (previous limit <<
1577 +                *1)+symbols at this level), and base[] (number of
1578 +                *symbols to ignore at each bit length, which is limit
1579 +                *minus the cumulative count of symbols coded for
1580 +                *already). */
1581 +               pp = t = 0;
1582 +               for (i = minLen; i < maxLen; i++) {
1583 +                       pp += temp[i];
1584 +                       /* We read the largest possible symbol size
1585 +                          and then unget bits after determining how
1586 +                          many we need, and those extra bits could be
1587 +                          set to anything.  (They're noise from
1588 +                          future symbols.)  At each level we're
1589 +                          really only interested in the first few
1590 +                          bits, so here we set all the trailing
1591 +                          to-be-ignored bits to 1 so they don't
1592 +                          affect the value > limit[length]
1593 +                          comparison. */
1594 +                       limit[i] = (pp << (maxLen - i)) - 1;
1595 +                       pp <<= 1;
1596 +                       base[i+1] = pp-(t += temp[i]);
1597 +               }
1598 +               limit[maxLen+1] = INT_MAX; /* Sentinal value for
1599 +                                           * reading next sym. */
1600 +               limit[maxLen] = pp+temp[maxLen]-1;
1601 +               base[minLen] = 0;
1602 +       }
1603 +       /* We've finished reading and digesting the block header.  Now
1604 +          read this block's Huffman coded symbols from the file and
1605 +          undo the Huffman coding and run length encoding, saving the
1606 +          result into dbuf[dbufCount++] = uc */
1607 +
1608 +       /* Initialize symbol occurrence counters and symbol Move To
1609 +        * Front table */
1610 +       for (i = 0; i < 256; i++) {
1611 +               byteCount[i] = 0;
1612 +               mtfSymbol[i] = (unsigned char)i;
1613 +       }
1614 +       /* Loop through compressed symbols. */
1615 +       runPos = dbufCount = symCount = selector = 0;
1616 +       for (;;) {
1617 +               /* Determine which Huffman coding group to use. */
1618 +               if (!(symCount--)) {
1619 +                       symCount = GROUP_SIZE-1;
1620 +                       if (selector >= nSelectors)
1621 +                               return RETVAL_DATA_ERROR;
1622 +                       hufGroup = bd->groups+selectors[selector++];
1623 +                       base = hufGroup->base-1;
1624 +                       limit = hufGroup->limit-1;
1625 +               }
1626 +               /* Read next Huffman-coded symbol. */
1627 +               /* Note: It is far cheaper to read maxLen bits and
1628 +                  back up than it is to read minLen bits and then an
1629 +                  additional bit at a time, testing as we go.
1630 +                  Because there is a trailing last block (with file
1631 +                  CRC), there is no danger of the overread causing an
1632 +                  unexpected EOF for a valid compressed file.  As a
1633 +                  further optimization, we do the read inline
1634 +                  (falling back to a call to get_bits if the buffer
1635 +                  runs dry).  The following (up to got_huff_bits:) is
1636 +                  equivalent to j = get_bits(bd, hufGroup->maxLen);
1637 +                */
1638 +               while (bd->inbufBitCount < hufGroup->maxLen) {
1639 +                       if (bd->inbufPos == bd->inbufCount) {
1640 +                               j = get_bits(bd, hufGroup->maxLen);
1641 +                               goto got_huff_bits;
1642 +                       }
1643 +                       bd->inbufBits =
1644 +                               (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
1645 +                       bd->inbufBitCount += 8;
1646 +               };
1647 +               bd->inbufBitCount -= hufGroup->maxLen;
1648 +               j = (bd->inbufBits >> bd->inbufBitCount)&
1649 +                       ((1 << hufGroup->maxLen)-1);
1650 +got_huff_bits:
1651 +               /* Figure how how many bits are in next symbol and
1652 +                * unget extras */
1653 +               i = hufGroup->minLen;
1654 +               while (j > limit[i])
1655 +                       ++i;
1656 +               bd->inbufBitCount += (hufGroup->maxLen - i);
1657 +               /* Huffman decode value to get nextSym (with bounds checking) */
1658 +               if ((i > hufGroup->maxLen)
1659 +                       || (((unsigned)(j = (j>>(hufGroup->maxLen-i))-base[i]))
1660 +                               >= MAX_SYMBOLS))
1661 +                       return RETVAL_DATA_ERROR;
1662 +               nextSym = hufGroup->permute[j];
1663 +               /* We have now decoded the symbol, which indicates
1664 +                  either a new literal byte, or a repeated run of the
1665 +                  most recent literal byte.  First, check if nextSym
1666 +                  indicates a repeated run, and if so loop collecting
1667 +                  how many times to repeat the last literal. */
1668 +               if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */
1669 +                       /* If this is the start of a new run, zero out
1670 +                        * counter */
1671 +                       if (!runPos) {
1672 +                               runPos = 1;
1673 +                               t = 0;
1674 +                       }
1675 +                       /* Neat trick that saves 1 symbol: instead of
1676 +                          or-ing 0 or 1 at each bit position, add 1
1677 +                          or 2 instead.  For example, 1011 is 1 << 0
1678 +                          + 1 << 1 + 2 << 2.  1010 is 2 << 0 + 2 << 1
1679 +                          + 1 << 2.  You can make any bit pattern
1680 +                          that way using 1 less symbol than the basic
1681 +                          or 0/1 method (except all bits 0, which
1682 +                          would use no symbols, but a run of length 0
1683 +                          doesn't mean anything in this context).
1684 +                          Thus space is saved. */
1685 +                       t += (runPos << nextSym);
1686 +                       /* +runPos if RUNA; +2*runPos if RUNB */
1687 +
1688 +                       runPos <<= 1;
1689 +                       continue;
1690 +               }
1691 +               /* When we hit the first non-run symbol after a run,
1692 +                  we now know how many times to repeat the last
1693 +                  literal, so append that many copies to our buffer
1694 +                  of decoded symbols (dbuf) now.  (The last literal
1695 +                  used is the one at the head of the mtfSymbol
1696 +                  array.) */
1697 +               if (runPos) {
1698 +                       runPos = 0;
1699 +                       if (dbufCount+t >= dbufSize)
1700 +                               return RETVAL_DATA_ERROR;
1701 +
1702 +                       uc = symToByte[mtfSymbol[0]];
1703 +                       byteCount[uc] += t;
1704 +                       while (t--)
1705 +                               dbuf[dbufCount++] = uc;
1706 +               }
1707 +               /* Is this the terminating symbol? */
1708 +               if (nextSym > symTotal)
1709 +                       break;
1710 +               /* At this point, nextSym indicates a new literal
1711 +                  character.  Subtract one to get the position in the
1712 +                  MTF array at which this literal is currently to be
1713 +                  found.  (Note that the result can't be -1 or 0,
1714 +                  because 0 and 1 are RUNA and RUNB.  But another
1715 +                  instance of the first symbol in the mtf array,
1716 +                  position 0, would have been handled as part of a
1717 +                  run above.  Therefore 1 unused mtf position minus 2
1718 +                  non-literal nextSym values equals -1.) */
1719 +               if (dbufCount >= dbufSize)
1720 +                       return RETVAL_DATA_ERROR;
1721 +               i = nextSym - 1;
1722 +               uc = mtfSymbol[i];
1723 +               /* Adjust the MTF array.  Since we typically expect to
1724 +                *move only a small number of symbols, and are bound
1725 +                *by 256 in any case, using memmove here would
1726 +                *typically be bigger and slower due to function call
1727 +                *overhead and other assorted setup costs. */
1728 +               do {
1729 +                       mtfSymbol[i] = mtfSymbol[i-1];
1730 +               } while (--i);
1731 +               mtfSymbol[0] = uc;
1732 +               uc = symToByte[uc];
1733 +               /* We have our literal byte.  Save it into dbuf. */
1734 +               byteCount[uc]++;
1735 +               dbuf[dbufCount++] = (unsigned int)uc;
1736 +       }
1737 +       /* At this point, we've read all the Huffman-coded symbols
1738 +          (and repeated runs) for this block from the input stream,
1739 +          and decoded them into the intermediate buffer.  There are
1740 +          dbufCount many decoded bytes in dbuf[].  Now undo the
1741 +          Burrows-Wheeler transform on dbuf.  See
1742 +          http://dogma.net/markn/articles/bwt/bwt.htm
1743 +        */
1744 +       /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */
1745 +       j = 0;
1746 +       for (i = 0; i < 256; i++) {
1747 +               k = j+byteCount[i];
1748 +               byteCount[i] = j;
1749 +               j = k;
1750 +       }
1751 +       /* Figure out what order dbuf would be in if we sorted it. */
1752 +       for (i = 0; i < dbufCount; i++) {
1753 +               uc = (unsigned char)(dbuf[i] & 0xff);
1754 +               dbuf[byteCount[uc]] |= (i << 8);
1755 +               byteCount[uc]++;
1756 +       }
1757 +       /* Decode first byte by hand to initialize "previous" byte.
1758 +          Note that it doesn't get output, and if the first three
1759 +          characters are identical it doesn't qualify as a run (hence
1760 +          writeRunCountdown = 5). */
1761 +       if (dbufCount) {
1762 +               if (origPtr >= dbufCount)
1763 +                       return RETVAL_DATA_ERROR;
1764 +               bd->writePos = dbuf[origPtr];
1765 +               bd->writeCurrent = (unsigned char)(bd->writePos&0xff);
1766 +               bd->writePos >>= 8;
1767 +               bd->writeRunCountdown = 5;
1768 +       }
1769 +       bd->writeCount = dbufCount;
1770 +
1771 +       return RETVAL_OK;
1772 +}
1773 +
1774 +/* Undo burrows-wheeler transform on intermediate buffer to produce output.
1775 +   If start_bunzip was initialized with out_fd =-1, then up to len bytes of
1776 +   data are written to outbuf.  Return value is number of bytes written or
1777 +   error (all errors are negative numbers).  If out_fd!=-1, outbuf and len
1778 +   are ignored, data is written to out_fd and return is RETVAL_OK or error.
1779 +*/
1780 +
1781 +static int INIT read_bunzip(struct bunzip_data *bd, char *outbuf, int len)
1782 +{
1783 +       const unsigned int *dbuf;
1784 +       int pos, xcurrent, previous, gotcount;
1785 +
1786 +       /* If last read was short due to end of file, return last block now */
1787 +       if (bd->writeCount < 0)
1788 +               return bd->writeCount;
1789 +
1790 +       gotcount = 0;
1791 +       dbuf = bd->dbuf;
1792 +       pos = bd->writePos;
1793 +       xcurrent = bd->writeCurrent;
1794 +
1795 +       /* We will always have pending decoded data to write into the output
1796 +          buffer unless this is the very first call (in which case we haven't
1797 +          Huffman-decoded a block into the intermediate buffer yet). */
1798 +
1799 +       if (bd->writeCopies) {
1800 +               /* Inside the loop, writeCopies means extra copies (beyond 1) */
1801 +               --bd->writeCopies;
1802 +               /* Loop outputting bytes */
1803 +               for (;;) {
1804 +                       /* If the output buffer is full, snapshot
1805 +                        * state and return */
1806 +                       if (gotcount >= len) {
1807 +                               bd->writePos = pos;
1808 +                               bd->writeCurrent = xcurrent;
1809 +                               bd->writeCopies++;
1810 +                               return len;
1811 +                       }
1812 +                       /* Write next byte into output buffer, updating CRC */
1813 +                       outbuf[gotcount++] = xcurrent;
1814 +                       bd->writeCRC = (((bd->writeCRC) << 8)
1815 +                               ^bd->crc32Table[((bd->writeCRC) >> 24)
1816 +                               ^xcurrent]);
1817 +                       /* Loop now if we're outputting multiple
1818 +                        * copies of this byte */
1819 +                       if (bd->writeCopies) {
1820 +                               --bd->writeCopies;
1821 +                               continue;
1822 +                       }
1823 +decode_next_byte:
1824 +                       if (!bd->writeCount--)
1825 +                               break;
1826 +                       /* Follow sequence vector to undo
1827 +                        * Burrows-Wheeler transform */
1828 +                       previous = xcurrent;
1829 +                       pos = dbuf[pos];
1830 +                       xcurrent = pos&0xff;
1831 +                       pos >>= 8;
1832 +                       /* After 3 consecutive copies of the same
1833 +                          byte, the 4th is a repeat count.  We count
1834 +                          down from 4 instead *of counting up because
1835 +                          testing for non-zero is faster */
1836 +                       if (--bd->writeRunCountdown) {
1837 +                               if (xcurrent != previous)
1838 +                                       bd->writeRunCountdown = 4;
1839 +                       } else {
1840 +                               /* We have a repeated run, this byte
1841 +                                * indicates the count */
1842 +                               bd->writeCopies = xcurrent;
1843 +                               xcurrent = previous;
1844 +                               bd->writeRunCountdown = 5;
1845 +                               /* Sometimes there are just 3 bytes
1846 +                                * (run length 0) */
1847 +                               if (!bd->writeCopies)
1848 +                                       goto decode_next_byte;
1849 +                               /* Subtract the 1 copy we'd output
1850 +                                * anyway to get extras */
1851 +                               --bd->writeCopies;
1852 +                       }
1853 +               }
1854 +               /* Decompression of this block completed successfully */
1855 +               bd->writeCRC = ~bd->writeCRC;
1856 +               bd->totalCRC = ((bd->totalCRC << 1) |
1857 +                               (bd->totalCRC >> 31)) ^ bd->writeCRC;
1858 +               /* If this block had a CRC error, force file level CRC error. */
1859 +               if (bd->writeCRC != bd->headerCRC) {
1860 +                       bd->totalCRC = bd->headerCRC+1;
1861 +                       return RETVAL_LAST_BLOCK;
1862 +               }
1863 +       }
1864 +
1865 +       /* Refill the intermediate buffer by Huffman-decoding next
1866 +        * block of input */
1867 +       /* (previous is just a convenient unused temp variable here) */
1868 +       previous = get_next_block(bd);
1869 +       if (previous) {
1870 +               bd->writeCount = previous;
1871 +               return (previous != RETVAL_LAST_BLOCK) ? previous : gotcount;
1872 +       }
1873 +       bd->writeCRC = 0xffffffffUL;
1874 +       pos = bd->writePos;
1875 +       xcurrent = bd->writeCurrent;
1876 +       goto decode_next_byte;
1877 +}
1878 +
1879 +static int INIT nofill(void *buf, unsigned int len)
1880 +{
1881 +       return -1;
1882 +}
1883 +
1884 +/* Allocate the structure, read file header.  If in_fd ==-1, inbuf must contain
1885 +   a complete bunzip file (len bytes long).  If in_fd!=-1, inbuf and len are
1886 +   ignored, and data is read from file handle into temporary buffer. */
1887 +static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len,
1888 +                            int (*fill)(void*, unsigned int))
1889 +{
1890 +       struct bunzip_data *bd;
1891 +       unsigned int i, j, c;
1892 +       const unsigned int BZh0 =
1893 +               (((unsigned int)'B') << 24)+(((unsigned int)'Z') << 16)
1894 +               +(((unsigned int)'h') << 8)+(unsigned int)'0';
1895 +
1896 +       /* Figure out how much data to allocate */
1897 +       i = sizeof(struct bunzip_data);
1898 +
1899 +       /* Allocate bunzip_data.  Most fields initialize to zero. */
1900 +       bd = *bdp = malloc(i);
1901 +       memset(bd, 0, sizeof(struct bunzip_data));
1902 +       /* Setup input buffer */
1903 +       bd->inbuf = inbuf;
1904 +       bd->inbufCount = len;
1905 +       if (fill != NULL)
1906 +               bd->fill = fill;
1907 +       else
1908 +               bd->fill = nofill;
1909 +
1910 +       /* Init the CRC32 table (big endian) */
1911 +       for (i = 0; i < 256; i++) {
1912 +               c = i << 24;
1913 +               for (j = 8; j; j--)
1914 +                       c = c&0x80000000 ? (c << 1)^0x04c11db7 : (c << 1);
1915 +               bd->crc32Table[i] = c;
1916 +       }
1917 +
1918 +       /* Ensure that file starts with "BZh['1'-'9']." */
1919 +       i = get_bits(bd, 32);
1920 +       if (((unsigned int)(i-BZh0-1)) >= 9)
1921 +               return RETVAL_NOT_BZIP_DATA;
1922 +
1923 +       /* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of
1924 +          uncompressed data.  Allocate intermediate buffer for block. */
1925 +       bd->dbufSize = 100000*(i-BZh0);
1926 +
1927 +       bd->dbuf = large_malloc(bd->dbufSize * sizeof(int));
1928 +       return RETVAL_OK;
1929 +}
1930 +
1931 +/* Example usage: decompress src_fd to dst_fd.  (Stops at end of bzip2 data,
1932 +   not end of file.) */
1933 +STATIC int INIT bunzip2(unsigned char *buf, int len,
1934 +                       int(*fill)(void*, unsigned int),
1935 +                       int(*flush)(void*, unsigned int),
1936 +                       unsigned char *outbuf,
1937 +                       int *pos,
1938 +                       void(*error_fn)(char *x))
1939 +{
1940 +       struct bunzip_data *bd;
1941 +       int i = -1;
1942 +       unsigned char *inbuf;
1943 +
1944 +       set_error_fn(error_fn);
1945 +       if (flush)
1946 +               outbuf = malloc(BZIP2_IOBUF_SIZE);
1947 +       else
1948 +               len -= 4; /* Uncompressed size hack active in pre-boot
1949 +                            environment */
1950 +       if (!outbuf) {
1951 +               error("Could not allocate output bufer");
1952 +               return -1;
1953 +       }
1954 +       if (buf)
1955 +               inbuf = buf;
1956 +       else
1957 +               inbuf = malloc(BZIP2_IOBUF_SIZE);
1958 +       if (!inbuf) {
1959 +               error("Could not allocate input bufer");
1960 +               goto exit_0;
1961 +       }
1962 +       i = start_bunzip(&bd, inbuf, len, fill);
1963 +       if (!i) {
1964 +               for (;;) {
1965 +                       i = read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE);
1966 +                       if (i <= 0)
1967 +                               break;
1968 +                       if (!flush)
1969 +                               outbuf += i;
1970 +                       else
1971 +                               if (i != flush(outbuf, i)) {
1972 +                                       i = RETVAL_UNEXPECTED_OUTPUT_EOF;
1973 +                                       break;
1974 +                               }
1975 +               }
1976 +       }
1977 +       /* Check CRC and release memory */
1978 +       if (i == RETVAL_LAST_BLOCK) {
1979 +               if (bd->headerCRC != bd->totalCRC)
1980 +                       error("Data integrity error when decompressing.");
1981 +               else
1982 +                       i = RETVAL_OK;
1983 +       } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) {
1984 +               error("Compressed file ends unexpectedly");
1985 +       }
1986 +       if (bd->dbuf)
1987 +               large_free(bd->dbuf);
1988 +       if (pos)
1989 +               *pos = bd->inbufPos;
1990 +       free(bd);
1991 +       if (!buf)
1992 +               free(inbuf);
1993 +exit_0:
1994 +       if (flush)
1995 +               free(outbuf);
1996 +       return i;
1997 +}
1998 +
1999 +#define decompress bunzip2
2000 diff --git a/lib/decompress_inflate.c b/lib/decompress_inflate.c
2001 new file mode 100644
2002 index 0000000..839a329
2003 --- /dev/null
2004 +++ b/lib/decompress_inflate.c
2005 @@ -0,0 +1,167 @@
2006 +#ifdef STATIC
2007 +/* Pre-boot environment: included */
2008 +
2009 +/* prevent inclusion of _LINUX_KERNEL_H in pre-boot environment: lots
2010 + * errors about console_printk etc... on ARM */
2011 +#define _LINUX_KERNEL_H
2012 +
2013 +#include "zlib_inflate/inftrees.c"
2014 +#include "zlib_inflate/inffast.c"
2015 +#include "zlib_inflate/inflate.c"
2016 +
2017 +#else /* STATIC */
2018 +/* initramfs et al: linked */
2019 +
2020 +#include <linux/zutil.h>
2021 +
2022 +#include "zlib_inflate/inftrees.h"
2023 +#include "zlib_inflate/inffast.h"
2024 +#include "zlib_inflate/inflate.h"
2025 +
2026 +#include "zlib_inflate/infutil.h"
2027 +
2028 +#endif /* STATIC */
2029 +
2030 +#include <linux/decompress/mm.h>
2031 +
2032 +#define INBUF_LEN (16*1024)
2033 +
2034 +/* Included from initramfs et al code */
2035 +STATIC int INIT gunzip(unsigned char *buf, int len,
2036 +                      int(*fill)(void*, unsigned int),
2037 +                      int(*flush)(void*, unsigned int),
2038 +                      unsigned char *out_buf,
2039 +                      int *pos,
2040 +                      void(*error_fn)(char *x)) {
2041 +       u8 *zbuf;
2042 +       struct z_stream_s *strm;
2043 +       int rc;
2044 +       size_t out_len;
2045 +
2046 +       set_error_fn(error_fn);
2047 +       rc = -1;
2048 +       if (flush) {
2049 +               out_len = 0x8000; /* 32 K */
2050 +               out_buf = malloc(out_len);
2051 +       } else {
2052 +               out_len = 0x7fffffff; /* no limit */
2053 +       }
2054 +       if (!out_buf) {
2055 +               error("Out of memory while allocating output buffer");
2056 +               goto gunzip_nomem1;
2057 +       }
2058 +
2059 +       if (buf)
2060 +               zbuf = buf;
2061 +       else {
2062 +               zbuf = malloc(INBUF_LEN);
2063 +               len = 0;
2064 +       }
2065 +       if (!zbuf) {
2066 +               error("Out of memory while allocating input buffer");
2067 +               goto gunzip_nomem2;
2068 +       }
2069 +
2070 +       strm = malloc(sizeof(*strm));
2071 +       if (strm == NULL) {
2072 +               error("Out of memory while allocating z_stream");
2073 +               goto gunzip_nomem3;
2074 +       }
2075 +
2076 +       strm->workspace = malloc(flush ? zlib_inflate_workspacesize() :
2077 +                                sizeof(struct inflate_state));
2078 +       if (strm->workspace == NULL) {
2079 +               error("Out of memory while allocating workspace");
2080 +               goto gunzip_nomem4;
2081 +       }
2082 +
2083 +       if (len == 0)
2084 +               len = fill(zbuf, INBUF_LEN);
2085 +
2086 +       /* verify the gzip header */
2087 +       if (len < 10 ||
2088 +          zbuf[0] != 0x1f || zbuf[1] != 0x8b || zbuf[2] != 0x08) {
2089 +               if (pos)
2090 +                       *pos = 0;
2091 +               error("Not a gzip file");
2092 +               goto gunzip_5;
2093 +       }
2094 +
2095 +       /* skip over gzip header (1f,8b,08... 10 bytes total +
2096 +        * possible asciz filename)
2097 +        */
2098 +       strm->next_in = zbuf + 10;
2099 +       /* skip over asciz filename */
2100 +       if (zbuf[3] & 0x8) {
2101 +               while (strm->next_in[0])
2102 +                       strm->next_in++;
2103 +               strm->next_in++;
2104 +       }
2105 +       strm->avail_in = len - (strm->next_in - zbuf);
2106 +
2107 +       strm->next_out = out_buf;
2108 +       strm->avail_out = out_len;
2109 +
2110 +       rc = zlib_inflateInit2(strm, -MAX_WBITS);
2111 +
2112 +       if (!flush) {
2113 +               WS(strm)->inflate_state.wsize = 0;
2114 +               WS(strm)->inflate_state.window = NULL;
2115 +       }
2116 +
2117 +       while (rc == Z_OK) {
2118 +               if (strm->avail_in == 0) {
2119 +                       /* TODO: handle case where both pos and fill are set */
2120 +                       len = fill(zbuf, INBUF_LEN);
2121 +                       if (len < 0) {
2122 +                               rc = -1;
2123 +                               error("read error");
2124 +                               break;
2125 +                       }
2126 +                       strm->next_in = zbuf;
2127 +                       strm->avail_in = len;
2128 +               }
2129 +               rc = zlib_inflate(strm, 0);
2130 +
2131 +               /* Write any data generated */
2132 +               if (flush && strm->next_out > out_buf) {
2133 +                       int l = strm->next_out - out_buf;
2134 +                       if (l != flush(out_buf, l)) {
2135 +                               rc = -1;
2136 +                               error("write error");
2137 +                               break;
2138 +                       }
2139 +                       strm->next_out = out_buf;
2140 +                       strm->avail_out = out_len;
2141 +               }
2142 +
2143 +               /* after Z_FINISH, only Z_STREAM_END is "we unpacked it all" */
2144 +               if (rc == Z_STREAM_END) {
2145 +                       rc = 0;
2146 +                       break;
2147 +               } else if (rc != Z_OK) {
2148 +                       error("uncompression error");
2149 +                       rc = -1;
2150 +               }
2151 +       }
2152 +
2153 +       zlib_inflateEnd(strm);
2154 +       if (pos)
2155 +               /* add + 8 to skip over trailer */
2156 +               *pos = strm->next_in - zbuf+8;
2157 +
2158 +gunzip_5:
2159 +       free(strm->workspace);
2160 +gunzip_nomem4:
2161 +       free(strm);
2162 +gunzip_nomem3:
2163 +       if (!buf)
2164 +               free(zbuf);
2165 +gunzip_nomem2:
2166 +       if (flush)
2167 +               free(out_buf);
2168 +gunzip_nomem1:
2169 +       return rc; /* returns Z_OK (0) if successful */
2170 +}
2171 +
2172 +#define decompress gunzip
2173 diff --git a/lib/decompress_unlzma.c b/lib/decompress_unlzma.c
2174 new file mode 100644
2175 index 0000000..546f2f4
2176 --- /dev/null
2177 +++ b/lib/decompress_unlzma.c
2178 @@ -0,0 +1,647 @@
2179 +/* Lzma decompressor for Linux kernel. Shamelessly snarfed
2180 + *from busybox 1.1.1
2181 + *
2182 + *Linux kernel adaptation
2183 + *Copyright (C) 2006  Alain < alain@knaff.lu >
2184 + *
2185 + *Based on small lzma deflate implementation/Small range coder
2186 + *implementation for lzma.
2187 + *Copyright (C) 2006  Aurelien Jacobs < aurel@gnuage.org >
2188 + *
2189 + *Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
2190 + *Copyright (C) 1999-2005  Igor Pavlov
2191 + *
2192 + *Copyrights of the parts, see headers below.
2193 + *
2194 + *
2195 + *This program is free software; you can redistribute it and/or
2196 + *modify it under the terms of the GNU Lesser General Public
2197 + *License as published by the Free Software Foundation; either
2198 + *version 2.1 of the License, or (at your option) any later version.
2199 + *
2200 + *This program is distributed in the hope that it will be useful,
2201 + *but WITHOUT ANY WARRANTY; without even the implied warranty of
2202 + *MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
2203 + *Lesser General Public License for more details.
2204 + *
2205 + *You should have received a copy of the GNU Lesser General Public
2206 + *License along with this library; if not, write to the Free Software
2207 + *Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
2208 + */
2209 +
2210 +#ifndef STATIC
2211 +#include <linux/decompress/unlzma.h>
2212 +#endif /* STATIC */
2213 +
2214 +#include <linux/decompress/mm.h>
2215 +
2216 +#define        MIN(a, b) (((a) < (b)) ? (a) : (b))
2217 +
2218 +static long long INIT read_int(unsigned char *ptr, int size)
2219 +{
2220 +       int i;
2221 +       long long ret = 0;
2222 +
2223 +       for (i = 0; i < size; i++)
2224 +               ret = (ret << 8) | ptr[size-i-1];
2225 +       return ret;
2226 +}
2227 +
2228 +#define ENDIAN_CONVERT(x) \
2229 +  x = (typeof(x))read_int((unsigned char *)&x, sizeof(x))
2230 +
2231 +
2232 +/* Small range coder implementation for lzma.
2233 + *Copyright (C) 2006  Aurelien Jacobs < aurel@gnuage.org >
2234 + *
2235 + *Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
2236 + *Copyright (c) 1999-2005  Igor Pavlov
2237 + */
2238 +
2239 +#include <linux/compiler.h>
2240 +
2241 +#define LZMA_IOBUF_SIZE        0x10000
2242 +
2243 +struct rc {
2244 +       int (*fill)(void*, unsigned int);
2245 +       uint8_t *ptr;
2246 +       uint8_t *buffer;
2247 +       uint8_t *buffer_end;
2248 +       int buffer_size;
2249 +       uint32_t code;
2250 +       uint32_t range;
2251 +       uint32_t bound;
2252 +};
2253 +
2254 +
2255 +#define RC_TOP_BITS 24
2256 +#define RC_MOVE_BITS 5
2257 +#define RC_MODEL_TOTAL_BITS 11
2258 +
2259 +
2260 +/* Called twice: once at startup and once in rc_normalize() */
2261 +static void INIT rc_read(struct rc *rc)
2262 +{
2263 +       rc->buffer_size = rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE);
2264 +       if (rc->buffer_size <= 0)
2265 +               error("unexpected EOF");
2266 +       rc->ptr = rc->buffer;
2267 +       rc->buffer_end = rc->buffer + rc->buffer_size;
2268 +}
2269 +
2270 +/* Called once */
2271 +static inline void INIT rc_init(struct rc *rc,
2272 +                                      int (*fill)(void*, unsigned int),
2273 +                                      char *buffer, int buffer_size)
2274 +{
2275 +       rc->fill = fill;
2276 +       rc->buffer = (uint8_t *)buffer;
2277 +       rc->buffer_size = buffer_size;
2278 +       rc->buffer_end = rc->buffer + rc->buffer_size;
2279 +       rc->ptr = rc->buffer;
2280 +
2281 +       rc->code = 0;
2282 +       rc->range = 0xFFFFFFFF;
2283 +}
2284 +
2285 +static inline void INIT rc_init_code(struct rc *rc)
2286 +{
2287 +       int i;
2288 +
2289 +       for (i = 0; i < 5; i++) {
2290 +               if (rc->ptr >= rc->buffer_end)
2291 +                       rc_read(rc);
2292 +               rc->code = (rc->code << 8) | *rc->ptr++;
2293 +       }
2294 +}
2295 +
2296 +
2297 +/* Called once. TODO: bb_maybe_free() */
2298 +static inline void INIT rc_free(struct rc *rc)
2299 +{
2300 +       free(rc->buffer);
2301 +}
2302 +
2303 +/* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */
2304 +static void INIT rc_do_normalize(struct rc *rc)
2305 +{
2306 +       if (rc->ptr >= rc->buffer_end)
2307 +               rc_read(rc);
2308 +       rc->range <<= 8;
2309 +       rc->code = (rc->code << 8) | *rc->ptr++;
2310 +}
2311 +static inline void INIT rc_normalize(struct rc *rc)
2312 +{
2313 +       if (rc->range < (1 << RC_TOP_BITS))
2314 +               rc_do_normalize(rc);
2315 +}
2316 +
2317 +/* Called 9 times */
2318 +/* Why rc_is_bit_0_helper exists?
2319 + *Because we want to always expose (rc->code < rc->bound) to optimizer
2320 + */
2321 +static inline uint32_t INIT rc_is_bit_0_helper(struct rc *rc, uint16_t *p)
2322 +{
2323 +       rc_normalize(rc);
2324 +       rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS);
2325 +       return rc->bound;
2326 +}
2327 +static inline int INIT rc_is_bit_0(struct rc *rc, uint16_t *p)
2328 +{
2329 +       uint32_t t = rc_is_bit_0_helper(rc, p);
2330 +       return rc->code < t;
2331 +}
2332 +
2333 +/* Called ~10 times, but very small, thus inlined */
2334 +static inline void INIT rc_update_bit_0(struct rc *rc, uint16_t *p)
2335 +{
2336 +       rc->range = rc->bound;
2337 +       *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
2338 +}
2339 +static inline void rc_update_bit_1(struct rc *rc, uint16_t *p)
2340 +{
2341 +       rc->range -= rc->bound;
2342 +       rc->code -= rc->bound;
2343 +       *p -= *p >> RC_MOVE_BITS;
2344 +}
2345 +
2346 +/* Called 4 times in unlzma loop */
2347 +static int INIT rc_get_bit(struct rc *rc, uint16_t *p, int *symbol)
2348 +{
2349 +       if (rc_is_bit_0(rc, p)) {
2350 +               rc_update_bit_0(rc, p);
2351 +               *symbol *= 2;
2352 +               return 0;
2353 +       } else {
2354 +               rc_update_bit_1(rc, p);
2355 +               *symbol = *symbol * 2 + 1;
2356 +               return 1;
2357 +       }
2358 +}
2359 +
2360 +/* Called once */
2361 +static inline int INIT rc_direct_bit(struct rc *rc)
2362 +{
2363 +       rc_normalize(rc);
2364 +       rc->range >>= 1;
2365 +       if (rc->code >= rc->range) {
2366 +               rc->code -= rc->range;
2367 +               return 1;
2368 +       }
2369 +       return 0;
2370 +}
2371 +
2372 +/* Called twice */
2373 +static inline void INIT
2374 +rc_bit_tree_decode(struct rc *rc, uint16_t *p, int num_levels, int *symbol)
2375 +{
2376 +       int i = num_levels;
2377 +
2378 +       *symbol = 1;
2379 +       while (i--)
2380 +               rc_get_bit(rc, p + *symbol, symbol);
2381 +       *symbol -= 1 << num_levels;
2382 +}
2383 +
2384 +
2385 +/*
2386 + * Small lzma deflate implementation.
2387 + * Copyright (C) 2006  Aurelien Jacobs < aurel@gnuage.org >
2388 + *
2389 + * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
2390 + * Copyright (C) 1999-2005  Igor Pavlov
2391 + */
2392 +
2393 +
2394 +struct lzma_header {
2395 +       uint8_t pos;
2396 +       uint32_t dict_size;
2397 +       uint64_t dst_size;
2398 +} __attribute__ ((packed)) ;
2399 +
2400 +
2401 +#define LZMA_BASE_SIZE 1846
2402 +#define LZMA_LIT_SIZE 768
2403 +
2404 +#define LZMA_NUM_POS_BITS_MAX 4
2405 +
2406 +#define LZMA_LEN_NUM_LOW_BITS 3
2407 +#define LZMA_LEN_NUM_MID_BITS 3
2408 +#define LZMA_LEN_NUM_HIGH_BITS 8
2409 +
2410 +#define LZMA_LEN_CHOICE 0
2411 +#define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1)
2412 +#define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1)
2413 +#define LZMA_LEN_MID (LZMA_LEN_LOW \
2414 +                     + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS)))
2415 +#define LZMA_LEN_HIGH (LZMA_LEN_MID \
2416 +                      +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS)))
2417 +#define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))
2418 +
2419 +#define LZMA_NUM_STATES 12
2420 +#define LZMA_NUM_LIT_STATES 7
2421 +
2422 +#define LZMA_START_POS_MODEL_INDEX 4
2423 +#define LZMA_END_POS_MODEL_INDEX 14
2424 +#define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1))
2425 +
2426 +#define LZMA_NUM_POS_SLOT_BITS 6
2427 +#define LZMA_NUM_LEN_TO_POS_STATES 4
2428 +
2429 +#define LZMA_NUM_ALIGN_BITS 4
2430 +
2431 +#define LZMA_MATCH_MIN_LEN 2
2432 +
2433 +#define LZMA_IS_MATCH 0
2434 +#define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
2435 +#define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES)
2436 +#define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES)
2437 +#define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES)
2438 +#define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES)
2439 +#define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \
2440 +                      + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
2441 +#define LZMA_SPEC_POS (LZMA_POS_SLOT \
2442 +                      +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS))
2443 +#define LZMA_ALIGN (LZMA_SPEC_POS \
2444 +                   + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX)
2445 +#define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS))
2446 +#define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS)
2447 +#define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS)
2448 +
2449 +
2450 +struct writer {
2451 +       uint8_t *buffer;
2452 +       uint8_t previous_byte;
2453 +       size_t buffer_pos;
2454 +       int bufsize;
2455 +       size_t global_pos;
2456 +       int(*flush)(void*, unsigned int);
2457 +       struct lzma_header *header;
2458 +};
2459 +
2460 +struct cstate {
2461 +       int state;
2462 +       uint32_t rep0, rep1, rep2, rep3;
2463 +};
2464 +
2465 +static inline size_t INIT get_pos(struct writer *wr)
2466 +{
2467 +       return
2468 +               wr->global_pos + wr->buffer_pos;
2469 +}
2470 +
2471 +static inline uint8_t INIT peek_old_byte(struct writer *wr,
2472 +                                               uint32_t offs)
2473 +{
2474 +       if (!wr->flush) {
2475 +               int32_t pos;
2476 +               while (offs > wr->header->dict_size)
2477 +                       offs -= wr->header->dict_size;
2478 +               pos = wr->buffer_pos - offs;
2479 +               return wr->buffer[pos];
2480 +       } else {
2481 +               uint32_t pos = wr->buffer_pos - offs;
2482 +               while (pos >= wr->header->dict_size)
2483 +                       pos += wr->header->dict_size;
2484 +               return wr->buffer[pos];
2485 +       }
2486 +
2487 +}
2488 +
2489 +static inline void INIT write_byte(struct writer *wr, uint8_t byte)
2490 +{
2491 +       wr->buffer[wr->buffer_pos++] = wr->previous_byte = byte;
2492 +       if (wr->flush && wr->buffer_pos == wr->header->dict_size) {
2493 +               wr->buffer_pos = 0;
2494 +               wr->global_pos += wr->header->dict_size;
2495 +               wr->flush((char *)wr->buffer, wr->header->dict_size);
2496 +       }
2497 +}
2498 +
2499 +
2500 +static inline void INIT copy_byte(struct writer *wr, uint32_t offs)
2501 +{
2502 +       write_byte(wr, peek_old_byte(wr, offs));
2503 +}
2504 +
2505 +static inline void INIT copy_bytes(struct writer *wr,
2506 +                                        uint32_t rep0, int len)
2507 +{
2508 +       do {
2509 +               copy_byte(wr, rep0);
2510 +               len--;
2511 +       } while (len != 0 && wr->buffer_pos < wr->header->dst_size);
2512 +}
2513 +
2514 +static inline void INIT process_bit0(struct writer *wr, struct rc *rc,
2515 +                                    struct cstate *cst, uint16_t *p,
2516 +                                    int pos_state, uint16_t *prob,
2517 +                                    int lc, uint32_t literal_pos_mask) {
2518 +       int mi = 1;
2519 +       rc_update_bit_0(rc, prob);
2520 +       prob = (p + LZMA_LITERAL +
2521 +               (LZMA_LIT_SIZE
2522 +                * (((get_pos(wr) & literal_pos_mask) << lc)
2523 +                   + (wr->previous_byte >> (8 - lc))))
2524 +               );
2525 +
2526 +       if (cst->state >= LZMA_NUM_LIT_STATES) {
2527 +               int match_byte = peek_old_byte(wr, cst->rep0);
2528 +               do {
2529 +                       int bit;
2530 +                       uint16_t *prob_lit;
2531 +
2532 +                       match_byte <<= 1;
2533 +                       bit = match_byte & 0x100;
2534 +                       prob_lit = prob + 0x100 + bit + mi;
2535 +                       if (rc_get_bit(rc, prob_lit, &mi)) {
2536 +                               if (!bit)
2537 +                                       break;
2538 +                       } else {
2539 +                               if (bit)
2540 +                                       break;
2541 +                       }
2542 +               } while (mi < 0x100);
2543 +       }
2544 +       while (mi < 0x100) {
2545 +               uint16_t *prob_lit = prob + mi;
2546 +               rc_get_bit(rc, prob_lit, &mi);
2547 +       }
2548 +       write_byte(wr, mi);
2549 +       if (cst->state < 4)
2550 +               cst->state = 0;
2551 +       else if (cst->state < 10)
2552 +               cst->state -= 3;
2553 +       else
2554 +               cst->state -= 6;
2555 +}
2556 +
2557 +static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
2558 +                                           struct cstate *cst, uint16_t *p,
2559 +                                           int pos_state, uint16_t *prob) {
2560 +  int offset;
2561 +       uint16_t *prob_len;
2562 +       int num_bits;
2563 +       int len;
2564 +
2565 +       rc_update_bit_1(rc, prob);
2566 +       prob = p + LZMA_IS_REP + cst->state;
2567 +       if (rc_is_bit_0(rc, prob)) {
2568 +               rc_update_bit_0(rc, prob);
2569 +               cst->rep3 = cst->rep2;
2570 +               cst->rep2 = cst->rep1;
2571 +               cst->rep1 = cst->rep0;
2572 +               cst->state = cst->state < LZMA_NUM_LIT_STATES ? 0 : 3;
2573 +               prob = p + LZMA_LEN_CODER;
2574 +       } else {
2575 +               rc_update_bit_1(rc, prob);
2576 +               prob = p + LZMA_IS_REP_G0 + cst->state;
2577 +               if (rc_is_bit_0(rc, prob)) {
2578 +                       rc_update_bit_0(rc, prob);
2579 +                       prob = (p + LZMA_IS_REP_0_LONG
2580 +                               + (cst->state <<
2581 +                                  LZMA_NUM_POS_BITS_MAX) +
2582 +                               pos_state);
2583 +                       if (rc_is_bit_0(rc, prob)) {
2584 +                               rc_update_bit_0(rc, prob);
2585 +
2586 +                               cst->state = cst->state < LZMA_NUM_LIT_STATES ?
2587 +                                       9 : 11;
2588 +                               copy_byte(wr, cst->rep0);
2589 +                               return;
2590 +                       } else {
2591 +                               rc_update_bit_1(rc, prob);
2592 +                       }
2593 +               } else {
2594 +                       uint32_t distance;
2595 +
2596 +                       rc_update_bit_1(rc, prob);
2597 +                       prob = p + LZMA_IS_REP_G1 + cst->state;
2598 +                       if (rc_is_bit_0(rc, prob)) {
2599 +                               rc_update_bit_0(rc, prob);
2600 +                               distance = cst->rep1;
2601 +                       } else {
2602 +                               rc_update_bit_1(rc, prob);
2603 +                               prob = p + LZMA_IS_REP_G2 + cst->state;
2604 +                               if (rc_is_bit_0(rc, prob)) {
2605 +                                       rc_update_bit_0(rc, prob);
2606 +                                       distance = cst->rep2;
2607 +                               } else {
2608 +                                       rc_update_bit_1(rc, prob);
2609 +                                       distance = cst->rep3;
2610 +                                       cst->rep3 = cst->rep2;
2611 +                               }
2612 +                               cst->rep2 = cst->rep1;
2613 +                       }
2614 +                       cst->rep1 = cst->rep0;
2615 +                       cst->rep0 = distance;
2616 +               }
2617 +               cst->state = cst->state < LZMA_NUM_LIT_STATES ? 8 : 11;
2618 +               prob = p + LZMA_REP_LEN_CODER;
2619 +       }
2620 +
2621 +       prob_len = prob + LZMA_LEN_CHOICE;
2622 +       if (rc_is_bit_0(rc, prob_len)) {
2623 +               rc_update_bit_0(rc, prob_len);
2624 +               prob_len = (prob + LZMA_LEN_LOW
2625 +                           + (pos_state <<
2626 +                              LZMA_LEN_NUM_LOW_BITS));
2627 +               offset = 0;
2628 +               num_bits = LZMA_LEN_NUM_LOW_BITS;
2629 +       } else {
2630 +               rc_update_bit_1(rc, prob_len);
2631 +               prob_len = prob + LZMA_LEN_CHOICE_2;
2632 +               if (rc_is_bit_0(rc, prob_len)) {
2633 +                       rc_update_bit_0(rc, prob_len);
2634 +                       prob_len = (prob + LZMA_LEN_MID
2635 +                                   + (pos_state <<
2636 +                                      LZMA_LEN_NUM_MID_BITS));
2637 +                       offset = 1 << LZMA_LEN_NUM_LOW_BITS;
2638 +                       num_bits = LZMA_LEN_NUM_MID_BITS;
2639 +               } else {
2640 +                       rc_update_bit_1(rc, prob_len);
2641 +                       prob_len = prob + LZMA_LEN_HIGH;
2642 +                       offset = ((1 << LZMA_LEN_NUM_LOW_BITS)
2643 +                                 + (1 << LZMA_LEN_NUM_MID_BITS));
2644 +                       num_bits = LZMA_LEN_NUM_HIGH_BITS;
2645 +               }
2646 +       }
2647 +
2648 +       rc_bit_tree_decode(rc, prob_len, num_bits, &len);
2649 +       len += offset;
2650 +
2651 +       if (cst->state < 4) {
2652 +               int pos_slot;
2653 +
2654 +               cst->state += LZMA_NUM_LIT_STATES;
2655 +               prob =
2656 +                       p + LZMA_POS_SLOT +
2657 +                       ((len <
2658 +                         LZMA_NUM_LEN_TO_POS_STATES ? len :
2659 +                         LZMA_NUM_LEN_TO_POS_STATES - 1)
2660 +                        << LZMA_NUM_POS_SLOT_BITS);
2661 +               rc_bit_tree_decode(rc, prob,
2662 +                                  LZMA_NUM_POS_SLOT_BITS,
2663 +                                  &pos_slot);
2664 +               if (pos_slot >= LZMA_START_POS_MODEL_INDEX) {
2665 +                       int i, mi;
2666 +                       num_bits = (pos_slot >> 1) - 1;
2667 +                       cst->rep0 = 2 | (pos_slot & 1);
2668 +                       if (pos_slot < LZMA_END_POS_MODEL_INDEX) {
2669 +                               cst->rep0 <<= num_bits;
2670 +                               prob = p + LZMA_SPEC_POS +
2671 +                                       cst->rep0 - pos_slot - 1;
2672 +                       } else {
2673 +                               num_bits -= LZMA_NUM_ALIGN_BITS;
2674 +                               while (num_bits--)
2675 +                                       cst->rep0 = (cst->rep0 << 1) |
2676 +                                               rc_direct_bit(rc);
2677 +                               prob = p + LZMA_ALIGN;
2678 +                               cst->rep0 <<= LZMA_NUM_ALIGN_BITS;
2679 +                               num_bits = LZMA_NUM_ALIGN_BITS;
2680 +                       }
2681 +                       i = 1;
2682 +                       mi = 1;
2683 +                       while (num_bits--) {
2684 +                               if (rc_get_bit(rc, prob + mi, &mi))
2685 +                                       cst->rep0 |= i;
2686 +                               i <<= 1;
2687 +                       }
2688 +               } else
2689 +                       cst->rep0 = pos_slot;
2690 +               if (++(cst->rep0) == 0)
2691 +                       return;
2692 +       }
2693 +
2694 +       len += LZMA_MATCH_MIN_LEN;
2695 +
2696 +       copy_bytes(wr, cst->rep0, len);
2697 +}
2698 +
2699 +
2700 +
2701 +STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
2702 +                             int(*fill)(void*, unsigned int),
2703 +                             int(*flush)(void*, unsigned int),
2704 +                             unsigned char *output,
2705 +                             int *posp,
2706 +                             void(*error_fn)(char *x)
2707 +       )
2708 +{
2709 +       struct lzma_header header;
2710 +       int lc, pb, lp;
2711 +       uint32_t pos_state_mask;
2712 +       uint32_t literal_pos_mask;
2713 +       uint16_t *p;
2714 +       int num_probs;
2715 +       struct rc rc;
2716 +       int i, mi;
2717 +       struct writer wr;
2718 +       struct cstate cst;
2719 +       unsigned char *inbuf;
2720 +       int ret = -1;
2721 +
2722 +       set_error_fn(error_fn);
2723 +       if (!flush)
2724 +               in_len -= 4; /* Uncompressed size hack active in pre-boot
2725 +                               environment */
2726 +       if (buf)
2727 +               inbuf = buf;
2728 +       else
2729 +               inbuf = malloc(LZMA_IOBUF_SIZE);
2730 +       if (!inbuf) {
2731 +               error("Could not allocate input bufer");
2732 +               goto exit_0;
2733 +       }
2734 +
2735 +       cst.state = 0;
2736 +       cst.rep0 = cst.rep1 = cst.rep2 = cst.rep3 = 1;
2737 +
2738 +       wr.header = &header;
2739 +       wr.flush = flush;
2740 +       wr.global_pos = 0;
2741 +       wr.previous_byte = 0;
2742 +       wr.buffer_pos = 0;
2743 +
2744 +       rc_init(&rc, fill, inbuf, in_len);
2745 +
2746 +       for (i = 0; i < sizeof(header); i++) {
2747 +               if (rc.ptr >= rc.buffer_end)
2748 +                       rc_read(&rc);
2749 +               ((unsigned char *)&header)[i] = *rc.ptr++;
2750 +       }
2751 +
2752 +       if (header.pos >= (9 * 5 * 5))
2753 +               error("bad header");
2754 +
2755 +       mi = 0;
2756 +       lc = header.pos;
2757 +       while (lc >= 9) {
2758 +               mi++;
2759 +               lc -= 9;
2760 +       }
2761 +       pb = 0;
2762 +       lp = mi;
2763 +       while (lp >= 5) {
2764 +               pb++;
2765 +               lp -= 5;
2766 +       }
2767 +       pos_state_mask = (1 << pb) - 1;
2768 +       literal_pos_mask = (1 << lp) - 1;
2769 +
2770 +       ENDIAN_CONVERT(header.dict_size);
2771 +       ENDIAN_CONVERT(header.dst_size);
2772 +
2773 +       if (header.dict_size == 0)
2774 +               header.dict_size = 1;
2775 +
2776 +       if (output)
2777 +               wr.buffer = output;
2778 +       else {
2779 +               wr.bufsize = MIN(header.dst_size, header.dict_size);
2780 +               wr.buffer = large_malloc(wr.bufsize);
2781 +       }
2782 +       if (wr.buffer == NULL)
2783 +               goto exit_1;
2784 +
2785 +       num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp));
2786 +       p = (uint16_t *) large_malloc(num_probs * sizeof(*p));
2787 +       if (p == 0)
2788 +               goto exit_2;
2789 +       num_probs = LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp));
2790 +       for (i = 0; i < num_probs; i++)
2791 +               p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1;
2792 +
2793 +       rc_init_code(&rc);
2794 +
2795 +       while (get_pos(&wr) < header.dst_size) {
2796 +               int pos_state = get_pos(&wr) & pos_state_mask;
2797 +               uint16_t *prob = p + LZMA_IS_MATCH +
2798 +                       (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state;
2799 +               if (rc_is_bit_0(&rc, prob))
2800 +                       process_bit0(&wr, &rc, &cst, p, pos_state, prob,
2801 +                                    lc, literal_pos_mask);
2802 +               else {
2803 +                       process_bit1(&wr, &rc, &cst, p, pos_state, prob);
2804 +                       if (cst.rep0 == 0)
2805 +                               break;
2806 +               }
2807 +       }
2808 +
2809 +       if (posp)
2810 +               *posp = rc.ptr-rc.buffer;
2811 +       if (wr.flush)
2812 +               wr.flush(wr.buffer, wr.buffer_pos);
2813 +       ret = 0;
2814 +       large_free(p);
2815 +exit_2:
2816 +       if (!output)
2817 +               large_free(wr.buffer);
2818 +exit_1:
2819 +       if (!buf)
2820 +               free(inbuf);
2821 +exit_0:
2822 +       return ret;
2823 +}
2824 +
2825 +#define decompress unlzma
2826 diff --git a/lib/zlib_inflate/inflate.h b/lib/zlib_inflate/inflate.h
2827 index df8a6c9..3d17b3d 100644
2828 --- a/lib/zlib_inflate/inflate.h
2829 +++ b/lib/zlib_inflate/inflate.h
2830 @@ -1,3 +1,6 @@
2831 +#ifndef INFLATE_H
2832 +#define INFLATE_H
2833 +
2834  /* inflate.h -- internal inflate state definition
2835   * Copyright (C) 1995-2004 Mark Adler
2836   * For conditions of distribution and use, see copyright notice in zlib.h
2837 @@ -105,3 +108,4 @@ struct inflate_state {
2838      unsigned short work[288];   /* work area for code table building */
2839      code codes[ENOUGH];         /* space for code tables */
2840  };
2841 +#endif
2842 diff --git a/lib/zlib_inflate/inftrees.h b/lib/zlib_inflate/inftrees.h
2843 index 5f5219b..b70b473 100644
2844 --- a/lib/zlib_inflate/inftrees.h
2845 +++ b/lib/zlib_inflate/inftrees.h
2846 @@ -1,3 +1,6 @@
2847 +#ifndef INFTREES_H
2848 +#define INFTREES_H
2849 +
2850  /* inftrees.h -- header to use inftrees.c
2851   * Copyright (C) 1995-2005 Mark Adler
2852   * For conditions of distribution and use, see copyright notice in zlib.h
2853 @@ -53,3 +56,4 @@ typedef enum {
2854  extern int zlib_inflate_table (codetype type, unsigned short *lens,
2855                               unsigned codes, code **table,
2856                               unsigned *bits, unsigned short *work);
2857 +#endif
2858 diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
2859 index e063657..3b949a3 100644
2860 --- a/scripts/Makefile.lib
2861 +++ b/scripts/Makefile.lib
2862 @@ -186,3 +186,17 @@ quiet_cmd_gzip = GZIP    $@
2863  cmd_gzip = gzip -f -9 < $< > $@
2864
2865
2866 +# Bzip2
2867 +# ---------------------------------------------------------------------------
2868 +
2869 +# Bzip2 does not include size in file... so we have to fake that
2870 +size_append=$(CONFIG_SHELL) $(srctree)/scripts/bin_size
2871 +
2872 +quiet_cmd_bzip2 = BZIP2    $@
2873 +cmd_bzip2 = (bzip2 -9 < $< && $(size_append) $<) > $@ || (rm -f $@ ; false)
2874 +
2875 +# Lzma
2876 +# ---------------------------------------------------------------------------
2877 +
2878 +quiet_cmd_lzma = LZMA    $@
2879 +cmd_lzma = (lzma -9 -c $< && $(size_append) $<) >$@ || (rm -f $@ ; false)
2880 diff --git a/scripts/bin_size b/scripts/bin_size
2881 new file mode 100644
2882 index 0000000..43e1b36
2883 --- /dev/null
2884 +++ b/scripts/bin_size
2885 @@ -0,0 +1,10 @@
2886 +#!/bin/sh
2887 +
2888 +if [ $# = 0 ] ; then
2889 +   echo Usage: $0 file
2890 +fi
2891 +
2892 +size_dec=`stat -c "%s" $1`
2893 +size_hex_echo_string=`printf "%08x" $size_dec |
2894 +     sed 's/\(..\)\(..\)\(..\)\(..\)/\\\\x\4\\\\x\3\\\\x\2\\\\x\1/g'`
2895 +/bin/echo -ne $size_hex_echo_string
2896 diff --git a/scripts/gen_initramfs_list.sh b/scripts/gen_initramfs_list.sh
2897 index 5f3415f..3eea8f1 100644
2898 --- a/scripts/gen_initramfs_list.sh
2899 +++ b/scripts/gen_initramfs_list.sh
2900 @@ -5,7 +5,7 @@
2901  # Released under the terms of the GNU GPL
2902  #
2903  # Generate a cpio packed initramfs. It uses gen_init_cpio to generate
2904 -# the cpio archive, and gzip to pack it.
2905 +# the cpio archive, and then compresses it.
2906  # The script may also be used to generate the inputfile used for gen_init_cpio
2907  # This script assumes that gen_init_cpio is located in usr/ directory
2908
2909 @@ -16,8 +16,8 @@ usage() {
2910  cat << EOF
2911  Usage:
2912  $0 [-o <file>] [-u <uid>] [-g <gid>] {-d | <cpio_source>} ...
2913 -       -o <file>      Create gzipped initramfs file named <file> using
2914 -                      gen_init_cpio and gzip
2915 +       -o <file>      Create compressed initramfs file named <file> using
2916 +                      gen_init_cpio and compressor depending on the extension
2917         -u <uid>       User ID to map to user ID 0 (root).
2918                        <uid> is only meaningful if <cpio_source> is a
2919                        directory.  "squash" forces all files to uid 0.
2920 @@ -225,6 +225,7 @@ cpio_list=
2921  output="/dev/stdout"
2922  output_file=""
2923  is_cpio_compressed=
2924 +compr="gzip -9 -f"
2925
2926  arg="$1"
2927  case "$arg" in
2928 @@ -233,11 +234,15 @@ case "$arg" in
2929                 echo "deps_initramfs := \\"
2930                 shift
2931                 ;;
2932 -       "-o")   # generate gzipped cpio image named $1
2933 +       "-o")   # generate compressed cpio image named $1
2934                 shift
2935                 output_file="$1"
2936                 cpio_list="$(mktemp ${TMPDIR:-/tmp}/cpiolist.XXXXXX)"
2937                 output=${cpio_list}
2938 +               echo "$output_file" | grep -q "\.gz$" && compr="gzip -9 -f"
2939 +               echo "$output_file" | grep -q "\.bz2$" && compr="bzip2 -9 -f"
2940 +               echo "$output_file" | grep -q "\.lzma$" && compr="lzma -9 -f"
2941 +               echo "$output_file" | grep -q "\.cpio$" && compr="cat"
2942                 shift
2943                 ;;
2944  esac
2945 @@ -274,7 +279,7 @@ while [ $# -gt 0 ]; do
2946         esac
2947  done
2948
2949 -# If output_file is set we will generate cpio archive and gzip it
2950 +# If output_file is set we will generate cpio archive and compress it
2951  # we are carefull to delete tmp files
2952  if [ ! -z ${output_file} ]; then
2953         if [ -z ${cpio_file} ]; then
2954 @@ -287,7 +292,8 @@ if [ ! -z ${output_file} ]; then
2955         if [ "${is_cpio_compressed}" = "compressed" ]; then
2956                 cat ${cpio_tfile} > ${output_file}
2957         else
2958 -               cat ${cpio_tfile} | gzip -f -9 - > ${output_file}
2959 +               (cat ${cpio_tfile} | ${compr}  - > ${output_file}) \
2960 +               || (rm -f ${output_file} ; false)
2961         fi
2962         [ -z ${cpio_file} ] && rm ${cpio_tfile}
2963  fi
2964 diff --git a/usr/Kconfig b/usr/Kconfig
2965 index 86cecb5..43a3a0f 100644
2966 --- a/usr/Kconfig
2967 +++ b/usr/Kconfig
2968 @@ -44,3 +44,92 @@ config INITRAMFS_ROOT_GID
2969           owned by group root in the initial ramdisk image.
2970
2971           If you are not sure, leave it set to "0".
2972 +
2973 +config RD_GZIP
2974 +       bool "Initial ramdisk compressed using gzip"
2975 +       default y
2976 +       depends on BLK_DEV_INITRD=y
2977 +       select DECOMPRESS_GZIP
2978 +       help
2979 +         Support loading of a gzip encoded initial ramdisk or cpio buffer.
2980 +         If unsure, say Y.
2981 +
2982 +config RD_BZIP2
2983 +       bool "Initial ramdisk compressed using bzip2"
2984 +       default n
2985 +       depends on BLK_DEV_INITRD=y
2986 +       select DECOMPRESS_BZIP2
2987 +       help
2988 +         Support loading of a bzip2 encoded initial ramdisk or cpio buffer
2989 +         If unsure, say N.
2990 +
2991 +config RD_LZMA
2992 +       bool "Initial ramdisk compressed using lzma"
2993 +       default n
2994 +       depends on BLK_DEV_INITRD=y
2995 +       select DECOMPRESS_LZMA
2996 +       help
2997 +         Support loading of a lzma encoded initial ramdisk or cpio buffer
2998 +         If unsure, say N.
2999 +
3000 +choice
3001 +       prompt "Built-in initramfs compression mode"
3002 +       help
3003 +         This setting is only meaningful if the INITRAMFS_SOURCE is
3004 +         set. It decides by which algorithm the INITRAMFS_SOURCE will
3005 +         be compressed.
3006 +         Several compression algorithms are available, which differ
3007 +         in efficiency, compression and decompression speed.
3008 +         Compression speed is only relevant when building a kernel.
3009 +         Decompression speed is relevant at each boot.
3010 +
3011 +         If you have any problems with bzip2 or lzma compressed
3012 +         initramfs, mail me (Alain Knaff) <alain@knaff.lu>.
3013 +
3014 +         High compression options are mostly useful for users who
3015 +         are low on disk space (embedded systems), but for whom ram
3016 +         size matters less.
3017 +
3018 +         If in doubt, select 'gzip'
3019 +
3020 +config INITRAMFS_COMPRESSION_NONE
3021 +       bool "None"
3022 +       help
3023 +         Do not compress the built-in initramfs at all. This may
3024 +         sound wasteful in space, but, you should be aware that the
3025 +         built-in initramfs will be compressed at a later stage
3026 +         anyways along with the rest of the kernel, on those
3027 +         architectures that support this.
3028 +         However, not compressing the initramfs may lead to slightly
3029 +         higher memory consumption during a short time at boot, while
3030 +         both the cpio image and the unpacked filesystem image will
3031 +         be present in memory simultaneously
3032 +
3033 +config INITRAMFS_COMPRESSION_GZIP
3034 +       bool "Gzip"
3035 +       depends on RD_GZIP
3036 +       help
3037 +         The old and tried gzip compression. Its compression ratio is
3038 +         the poorest among the 3 choices; however its speed (both
3039 +         compression and decompression) is the fastest.
3040 +
3041 +config INITRAMFS_COMPRESSION_BZIP2
3042 +       bool "Bzip2"
3043 +       depends on RD_BZIP2
3044 +       help
3045 +         Its compression ratio and speed is intermediate.
3046 +         Decompression speed is slowest among the three.  The initramfs
3047 +         size is about 10% smaller with bzip2, in comparison to gzip.
3048 +         Bzip2 uses a large amount of memory. For modern kernels you
3049 +         will need at least 8MB RAM or more for booting.
3050 +
3051 +config INITRAMFS_COMPRESSION_LZMA
3052 +       bool "LZMA"
3053 +       depends on RD_LZMA
3054 +       help
3055 +         The most recent compression algorithm.
3056 +         Its ratio is best, decompression speed is between the other
3057 +         two. Compression is slowest.  The initramfs size is about 33%
3058 +         smaller with LZMA in comparison to gzip.
3059 +
3060 +endchoice
3061 diff --git a/usr/Makefile b/usr/Makefile
3062 index 201f27f..b84894b 100644
3063 --- a/usr/Makefile
3064 +++ b/usr/Makefile
3065 @@ -6,13 +6,25 @@ klibcdirs:;
3066  PHONY += klibcdirs
3067
3068
3069 +# No compression
3070 +suffix_$(CONFIG_INITRAMFS_COMPRESSION_NONE)   =
3071 +
3072 +# Gzip, but no bzip2
3073 +suffix_$(CONFIG_INITRAMFS_COMPRESSION_GZIP)   = .gz
3074 +
3075 +# Bzip2
3076 +suffix_$(CONFIG_INITRAMFS_COMPRESSION_BZIP2)  = .bz2
3077 +
3078 +# Lzma
3079 +suffix_$(CONFIG_INITRAMFS_COMPRESSION_LZMA)   = .lzma
3080 +
3081  # Generate builtin.o based on initramfs_data.o
3082 -obj-$(CONFIG_BLK_DEV_INITRD) := initramfs_data.o
3083 +obj-$(CONFIG_BLK_DEV_INITRD) := initramfs_data$(suffix_y).o
3084
3085 -# initramfs_data.o contains the initramfs_data.cpio.gz image.
3086 +# initramfs_data.o contains the compressed initramfs_data.cpio image.
3087  # The image is included using .incbin, a dependency which is not
3088  # tracked automatically.
3089 -$(obj)/initramfs_data.o: $(obj)/initramfs_data.cpio.gz FORCE
3090 +$(obj)/initramfs_data$(suffix_y).o: $(obj)/initramfs_data.cpio$(suffix_y) FORCE
3091
3092  #####
3093  # Generate the initramfs cpio archive
3094 @@ -25,28 +37,28 @@ ramfs-args  := \
3095          $(if $(CONFIG_INITRAMFS_ROOT_UID), -u $(CONFIG_INITRAMFS_ROOT_UID)) \
3096          $(if $(CONFIG_INITRAMFS_ROOT_GID), -g $(CONFIG_INITRAMFS_ROOT_GID))
3097
3098 -# .initramfs_data.cpio.gz.d is used to identify all files included
3099 +# .initramfs_data.cpio.d is used to identify all files included
3100  # in initramfs and to detect if any files are added/removed.
3101  # Removed files are identified by directory timestamp being updated
3102  # The dependency list is generated by gen_initramfs.sh -l
3103 -ifneq ($(wildcard $(obj)/.initramfs_data.cpio.gz.d),)
3104 -       include $(obj)/.initramfs_data.cpio.gz.d
3105 +ifneq ($(wildcard $(obj)/.initramfs_data.cpio.d),)
3106 +       include $(obj)/.initramfs_data.cpio.d
3107  endif
3108
3109  quiet_cmd_initfs = GEN     $@
3110        cmd_initfs = $(initramfs) -o $@ $(ramfs-args) $(ramfs-input)
3111
3112 -targets := initramfs_data.cpio.gz
3113 +targets := initramfs_data.cpio.gz initramfs_data.cpio.bz2 initramfs_data.cpio.lzma initramfs_data.cpio
3114  # do not try to update files included in initramfs
3115  $(deps_initramfs): ;
3116
3117  $(deps_initramfs): klibcdirs
3118 -# We rebuild initramfs_data.cpio.gz if:
3119 -# 1) Any included file is newer then initramfs_data.cpio.gz
3120 +# We rebuild initramfs_data.cpio if:
3121 +# 1) Any included file is newer then initramfs_data.cpio
3122  # 2) There are changes in which files are included (added or deleted)
3123 -# 3) If gen_init_cpio are newer than initramfs_data.cpio.gz
3124 +# 3) If gen_init_cpio are newer than initramfs_data.cpio
3125  # 4) arguments to gen_initramfs.sh changes
3126 -$(obj)/initramfs_data.cpio.gz: $(obj)/gen_init_cpio $(deps_initramfs) klibcdirs
3127 -       $(Q)$(initramfs) -l $(ramfs-input) > $(obj)/.initramfs_data.cpio.gz.d
3128 +$(obj)/initramfs_data.cpio$(suffix_y): $(obj)/gen_init_cpio $(deps_initramfs) klibcdirs
3129 +       $(Q)$(initramfs) -l $(ramfs-input) > $(obj)/.initramfs_data.cpio.d
3130         $(call if_changed,initfs)
3131
3132 diff --git a/usr/initramfs_data.S b/usr/initramfs_data.S
3133 index c2e1ad4..7c6973d 100644
3134 --- a/usr/initramfs_data.S
3135 +++ b/usr/initramfs_data.S
3136 @@ -26,5 +26,5 @@ SECTIONS
3137  */
3138
3139  .section .init.ramfs,"a"
3140 -.incbin "usr/initramfs_data.cpio.gz"
3141 +.incbin "usr/initramfs_data.cpio"
3142
3143 diff --git a/usr/initramfs_data.bz2.S b/usr/initramfs_data.bz2.S
3144 new file mode 100644
3145 index 0000000..bc54d09
3146 --- /dev/null
3147 +++ b/usr/initramfs_data.bz2.S
3148 @@ -0,0 +1,29 @@
3149 +/*
3150 +  initramfs_data includes the compressed binary that is the
3151 +  filesystem used for early user space.
3152 +  Note: Older versions of "as" (prior to binutils 2.11.90.0.23
3153 +  released on 2001-07-14) dit not support .incbin.
3154 +  If you are forced to use older binutils than that then the
3155 +  following trick can be applied to create the resulting binary:
3156 +
3157 +
3158 +  ld -m elf_i386  --format binary --oformat elf32-i386 -r \
3159 +  -T initramfs_data.scr initramfs_data.cpio.gz -o initramfs_data.o
3160 +   ld -m elf_i386  -r -o built-in.o initramfs_data.o
3161 +
3162 +  initramfs_data.scr looks like this:
3163 +SECTIONS
3164 +{
3165 +       .init.ramfs : { *(.data) }
3166 +}
3167 +
3168 +  The above example is for i386 - the parameters vary from architectures.
3169 +  Eventually look up LDFLAGS_BLOB in an older version of the
3170 +  arch/$(ARCH)/Makefile to see the flags used before .incbin was introduced.
3171 +
3172 +  Using .incbin has the advantage over ld that the correct flags are set
3173 +  in the ELF header, as required by certain architectures.
3174 +*/
3175 +
3176 +.section .init.ramfs,"a"
3177 +.incbin "usr/initramfs_data.cpio.bz2"
3178 diff --git a/usr/initramfs_data.gz.S b/usr/initramfs_data.gz.S
3179 new file mode 100644
3180 index 0000000..890c8dd
3181 --- /dev/null
3182 +++ b/usr/initramfs_data.gz.S
3183 @@ -0,0 +1,29 @@
3184 +/*
3185 +  initramfs_data includes the compressed binary that is the
3186 +  filesystem used for early user space.
3187 +  Note: Older versions of "as" (prior to binutils 2.11.90.0.23
3188 +  released on 2001-07-14) dit not support .incbin.
3189 +  If you are forced to use older binutils than that then the
3190 +  following trick can be applied to create the resulting binary:
3191 +
3192 +
3193 +  ld -m elf_i386  --format binary --oformat elf32-i386 -r \
3194 +  -T initramfs_data.scr initramfs_data.cpio.gz -o initramfs_data.o
3195 +   ld -m elf_i386  -r -o built-in.o initramfs_data.o
3196 +
3197 +  initramfs_data.scr looks like this:
3198 +SECTIONS
3199 +{
3200 +       .init.ramfs : { *(.data) }
3201 +}
3202 +
3203 +  The above example is for i386 - the parameters vary from architectures.
3204 +  Eventually look up LDFLAGS_BLOB in an older version of the
3205 +  arch/$(ARCH)/Makefile to see the flags used before .incbin was introduced.
3206 +
3207 +  Using .incbin has the advantage over ld that the correct flags are set
3208 +  in the ELF header, as required by certain architectures.
3209 +*/
3210 +
3211 +.section .init.ramfs,"a"
3212 +.incbin "usr/initramfs_data.cpio.gz"
3213 diff --git a/usr/initramfs_data.lzma.S b/usr/initramfs_data.lzma.S
3214 new file mode 100644
3215 index 0000000..e11469e
3216 --- /dev/null
3217 +++ b/usr/initramfs_data.lzma.S
3218 @@ -0,0 +1,29 @@
3219 +/*
3220 +  initramfs_data includes the compressed binary that is the
3221 +  filesystem used for early user space.
3222 +  Note: Older versions of "as" (prior to binutils 2.11.90.0.23
3223 +  released on 2001-07-14) dit not support .incbin.
3224 +  If you are forced to use older binutils than that then the
3225 +  following trick can be applied to create the resulting binary:
3226 +
3227 +
3228 +  ld -m elf_i386  --format binary --oformat elf32-i386 -r \
3229 +  -T initramfs_data.scr initramfs_data.cpio.gz -o initramfs_data.o
3230 +   ld -m elf_i386  -r -o built-in.o initramfs_data.o
3231 +
3232 +  initramfs_data.scr looks like this:
3233 +SECTIONS
3234 +{
3235 +       .init.ramfs : { *(.data) }
3236 +}
3237 +
3238 +  The above example is for i386 - the parameters vary from architectures.
3239 +  Eventually look up LDFLAGS_BLOB in an older version of the
3240 +  arch/$(ARCH)/Makefile to see the flags used before .incbin was introduced.
3241 +
3242 +  Using .incbin has the advantage over ld that the correct flags are set
3243 +  in the ELF header, as required by certain architectures.
3244 +*/
3245 +
3246 +.section .init.ramfs,"a"
3247 +.incbin "usr/initramfs_data.cpio.lzma"
3248 --
3249 To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
3250 the body of a message to majordomo@vger.kernel.org
3251 More majordomo info at  http://vger.kernel.org/majordomo-info.html
3252 Please read the FAQ at  http://www.tux.org/lkml/