4 * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
5 * puts by Nick Holloway 1993, better puts by Martin Mares 1995
6 * High loaded stuff by Hans Lermen & Werner Almesberger, Feb. 1996
8 * Decompress LZMA compressed vmlinuz
9 * Version 0.9 Copyright (c) Ming-Ching Tiew mctiew@yahoo.com
10 * Program adapted from misc.c for 2.6 kernel
11 * Forward ported to latest 2.6 version of misc.c by
12 * Felix Fietkau <nbd@openwrt.org>
15 #undef CONFIG_PARAVIRT
16 #include <linux/linkage.h>
17 #include <linux/vmalloc.h>
18 #include <linux/screen_info.h>
19 #include <linux/console.h>
20 #include <linux/string.h>
26 * This code is compiled with -fPIC and it is relocated dynamically
27 * at run time, but no relocation processing is performed.
28 * This means that it is not safe to place pointers in static structures.
32 * Getting to provable safe in place decompression is hard.
33 * Worst case behaviours need to be analized.
34 * Background information:
43 * compressed data blocks[N]
46 * resulting in 18 bytes of non compressed data overhead.
48 * Files divided into blocks
49 * 1 bit (last block flag)
52 * 1 block occurs every 32K -1 bytes or when there 50% compression has been achieved.
53 * The smallest block type encoding is always used.
56 * 32 bits length in bytes.
63 * dynamic tree encoding.
67 * The buffer for decompression in place is the length of the
68 * uncompressed data, plus a small amount extra to keep the algorithm safe.
69 * The compressed data is placed at the end of the buffer. The output
70 * pointer is placed at the start of the buffer and the input pointer
71 * is placed where the compressed data starts. Problems will occur
72 * when the output pointer overruns the input pointer.
74 * The output pointer can only overrun the input pointer if the input
75 * pointer is moving faster than the output pointer. A condition only
76 * triggered by data whose compressed form is larger than the uncompressed
79 * The worst case at the block level is a growth of the compressed data
80 * of 5 bytes per 32767 bytes.
82 * The worst case internal to a compressed block is very hard to figure.
83 * The worst case can at least be boundined by having one bit that represents
84 * 32764 bytes and then all of the rest of the bytes representing the very
87 * All of which is enough to compute an amount of extra data that is required
88 * to be safe. To avoid problems at the block level allocating 5 extra bytes
89 * per 32767 bytes of data is sufficient. To avoind problems internal to a block
90 * adding an extra 32767 bytes (the worst case uncompressed block size) is
91 * sufficient, to ensure that in the worst case the decompressed data for
92 * block will stop the byte before the compressed data for a block begins.
93 * To avoid problems with the compressed data's meta information an extra 18
94 * bytes are needed. Leading to the formula:
96 * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
98 * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
99 * Adding 32768 instead of 32767 just makes for round numbers.
100 * Adding the decompressor_size is necessary as it musht live after all
101 * of the data as well. Last I measured the decompressor is about 14K.
102 * 10K of actuall data and 4K of bss.
110 #define OF(args) args
111 #define STATIC static
115 typedef unsigned char uch;
116 typedef unsigned short ush;
117 typedef unsigned long ulg;
119 #define WSIZE 0x80000000 /* Window size must be at least 32k,
121 * We don't actually have a window just
122 * a huge output buffer so I report
123 * a 2G windows size, as that should
124 * always be larger than our output buffer.
127 static uch *inbuf; /* input buffer */
128 static uch *window; /* Sliding window buffer, (and final output buffer) */
130 static unsigned insize; /* valid bytes in inbuf */
131 static unsigned inptr; /* index of next byte to be processed in inbuf */
132 static unsigned long workspace;
134 #define get_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf())
136 /* Diagnostic functions */
138 # define Assert(cond,msg) {if(!(cond)) error(msg);}
139 # define Trace(x) fprintf x
140 # define Tracev(x) {if (verbose) fprintf x ;}
141 # define Tracevv(x) {if (verbose>1) fprintf x ;}
142 # define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
143 # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
145 # define Assert(cond,msg)
150 # define Tracecv(c,x)
153 static int fill_inbuf(void);
156 * This is set up by the setup-routine at boot-time
158 static unsigned char *real_mode; /* Pointer to real-mode data */
159 extern unsigned char input_data[];
160 extern int input_len;
162 static void error(char *x);
163 static void *memcpy(void *dest, const void *src, unsigned n);
165 #ifdef CONFIG_X86_NUMAQ
169 static void* memcpy(void* dest, const void* src, unsigned n)
172 char *d = (char *)dest, *s = (char *)src;
174 for (i=0;i<n;i++) d[i] = s[i];
178 /* ===========================================================================
179 * Fill the input buffer. This is called only when the buffer is empty
180 * and at least one byte is really needed.
182 static int fill_inbuf(void)
184 error("ran out of input data");
189 // When using LZMA in callback, the compressed length is not needed.
190 // Otherwise you need a special version of lzma compression program
191 // which will pad the compressed length in the header.
193 #include "LzmaDecode.h"
194 #include "LzmaDecode.c"
196 static int read_byte(void *object, unsigned char **buffer, UInt32 *bufferSize);
198 static int early_serial_base = 0x3f8; /* ttyS0 */
204 #define TXR 0 /* Transmit register (WRITE) */
205 #define RXR 0 /* Receive register (READ) */
206 #define IER 1 /* Interrupt Enable */
207 #define IIR 2 /* Interrupt ID */
208 #define FCR 2 /* FIFO control */
209 #define LCR 3 /* Line control */
210 #define MCR 4 /* Modem control */
211 #define LSR 5 /* Line Status */
212 #define MSR 6 /* Modem Status */
213 #define DLL 0 /* Divisor Latch Low */
214 #define DLH 1 /* Divisor latch High */
216 static int early_serial_putc(unsigned char ch)
218 unsigned timeout = 0xffff;
219 while ((inb(early_serial_base + LSR) & XMTRDY) == 0 && --timeout)
221 outb(ch, early_serial_base + TXR);
222 return timeout ? 0 : -1;
225 static void early_serial_write(const char *s, unsigned n)
227 while (*s && n-- > 0) {
229 early_serial_putc('\r');
230 early_serial_putc(*s);
235 #define DEFAULT_BAUD 38400
237 static __init void early_serial_init(void)
241 unsigned baud = DEFAULT_BAUD;
244 outb(0x3, early_serial_base + LCR); /* 8n1 */
245 outb(0, early_serial_base + IER); /* no interrupt */
246 outb(0, early_serial_base + FCR); /* no fifo */
247 outb(0x3, early_serial_base + MCR); /* DTR + RTS */
251 divisor = 115200 / baud;
252 c = inb(early_serial_base + LCR);
253 outb(c | DLAB, early_serial_base + LCR);
254 outb(divisor & 0xff, early_serial_base + DLL);
255 outb((divisor >> 8) & 0xff, early_serial_base + DLH);
256 outb(c & ~DLAB, early_serial_base + LCR);
260 * Do the lzma decompression
261 * When using LZMA in callback, the end of input stream is automatically determined
263 static int lzma_unzip(void)
266 unsigned int i; /* temp value */
267 unsigned int lc; /* literal context bits */
268 unsigned int lp; /* literal pos state bits */
269 unsigned int pb; /* pos state bits */
270 unsigned int uncompressedSize = 0;
273 ILzmaInCallback callback;
274 callback.Read = read_byte;
278 lc = i % 9, i = i / 9;
279 lp = i % 5, pb = i / 5;
281 /* skip dictionary size */
282 for (i = 0; i < 4; i++)
284 // get uncompressedSize
285 p= (char*)&uncompressedSize;
286 for (i = 0; i < 4; i++)
290 for (i = 0; i < 4; i++)
293 // point it beyond uncompresedSize
294 //workspace = window + uncompressedSize;
296 /* decompress kernel */
297 if (LzmaDecode((unsigned char*)workspace, ~0, lc, lp, pb, &callback,
298 (unsigned char*)window, uncompressedSize, &i) == LZMA_RESULT_OK)
306 static int read_byte(void *object, unsigned char **buffer, UInt32 *bufferSize)
308 static unsigned int i = 0;
309 static unsigned char val;
313 return LZMA_RESULT_OK;
317 static void error(char *x)
322 asmlinkage void decompress_kernel(void *rmode, unsigned long end,
323 uch *input_data, unsigned long input_len, uch *output)
328 inbuf = input_data; /* Input buffer */
332 if ((u32)output & (CONFIG_PHYSICAL_ALIGN -1))
333 error("Destination address not CONFIG_PHYSICAL_ALIGN aligned");
334 if ((workspace = end) > ((-__PAGE_OFFSET-(512 <<20)-1) & 0x7fffffff))
335 error("Destination address too large");
336 #ifndef CONFIG_RELOCATABLE
337 if ((u32)output != LOAD_PHYSICAL_ADDR)
338 error("Wrong destination address");
341 early_serial_write("Uncompressing Linux\n", 512);
343 early_serial_write("Done, booting\n", 512);