4 * This is a collection of several routines from gzip-1.0.3
7 * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
8 * puts by Nick Holloway 1993, better puts by Martin Mares 1995
9 * High loaded stuff by Hans Lermen & Werner Almesberger, Feb. 1996
13 * we have to be careful, because no indirections are allowed here, and
14 * paravirt_ops is a kind of one. As it will only run in baremetal anyway,
15 * we just keep it from happening
17 #undef CONFIG_PARAVIRT
19 #define _ASM_DESC_H_ 1
23 #define _LINUX_STRING_H_ 1
24 #define __LINUX_BITMAP_H 1
27 #include <linux/linkage.h>
28 #include <linux/screen_info.h>
29 #include <linux/elf.h>
35 * This code is compiled with -fPIC and it is relocated dynamically
36 * at run time, but no relocation processing is performed.
37 * This means that it is not safe to place pointers in static structures.
41 * Getting to provable safe in place decompression is hard.
42 * Worst case behaviours need to be analyzed.
43 * Background information:
52 * compressed data blocks[N]
55 * resulting in 18 bytes of non compressed data overhead.
57 * Files divided into blocks
58 * 1 bit (last block flag)
61 * 1 block occurs every 32K -1 bytes or when there 50% compression
62 * has been achieved. The smallest block type encoding is always used.
65 * 32 bits length in bytes.
72 * dynamic tree encoding.
76 * The buffer for decompression in place is the length of the
77 * uncompressed data, plus a small amount extra to keep the algorithm safe.
78 * The compressed data is placed at the end of the buffer. The output
79 * pointer is placed at the start of the buffer and the input pointer
80 * is placed where the compressed data starts. Problems will occur
81 * when the output pointer overruns the input pointer.
83 * The output pointer can only overrun the input pointer if the input
84 * pointer is moving faster than the output pointer. A condition only
85 * triggered by data whose compressed form is larger than the uncompressed
88 * The worst case at the block level is a growth of the compressed data
89 * of 5 bytes per 32767 bytes.
91 * The worst case internal to a compressed block is very hard to figure.
92 * The worst case can at least be boundined by having one bit that represents
93 * 32764 bytes and then all of the rest of the bytes representing the very
96 * All of which is enough to compute an amount of extra data that is required
97 * to be safe. To avoid problems at the block level allocating 5 extra bytes
98 * per 32767 bytes of data is sufficient. To avoind problems internal to a
99 * block adding an extra 32767 bytes (the worst case uncompressed block size)
100 * is sufficient, to ensure that in the worst case the decompressed data for
101 * block will stop the byte before the compressed data for a block begins.
102 * To avoid problems with the compressed data's meta information an extra 18
103 * bytes are needed. Leading to the formula:
105 * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
107 * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
108 * Adding 32768 instead of 32767 just makes for round numbers.
109 * Adding the decompressor_size is necessary as it musht live after all
110 * of the data as well. Last I measured the decompressor is about 14K.
111 * 10K of actual data and 4K of bss.
119 #define OF(args) args
120 #define STATIC static
124 #define memzero(s, n) memset((s), 0, (n))
126 typedef unsigned char uch;
127 typedef unsigned short ush;
128 typedef unsigned long ulg;
131 * Window size must be at least 32k, and a power of two.
132 * We don't actually have a window just a huge output buffer,
133 * so we report a 2G window size, as that should always be
134 * larger than our output buffer:
136 #define WSIZE 0x80000000
139 static unsigned char *inbuf;
141 /* Sliding window buffer (and final output buffer): */
142 static unsigned char *window;
144 /* Valid bytes in inbuf: */
145 static unsigned insize;
147 /* Index of next byte to be processed in inbuf: */
148 static unsigned inptr;
150 /* Bytes in output buffer: */
151 static unsigned outcnt;
154 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ASCII text */
155 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gz file */
156 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
157 #define ORIG_NAM 0x08 /* bit 3 set: original file name present */
158 #define COMMENT 0x10 /* bit 4 set: file comment present */
159 #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
160 #define RESERVED 0xC0 /* bit 6, 7: reserved */
162 #define get_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf())
164 /* Diagnostic functions */
166 # define Assert(cond, msg) do { if (!(cond)) error(msg); } while (0)
167 # define Trace(x) do { fprintf x; } while (0)
168 # define Tracev(x) do { if (verbose) fprintf x ; } while (0)
169 # define Tracevv(x) do { if (verbose > 1) fprintf x ; } while (0)
170 # define Tracec(c, x) do { if (verbose && (c)) fprintf x ; } while (0)
171 # define Tracecv(c, x) do { if (verbose > 1 && (c)) fprintf x ; } while (0)
173 # define Assert(cond, msg)
177 # define Tracec(c, x)
178 # define Tracecv(c, x)
181 static int fill_inbuf(void);
182 static void flush_window(void);
183 static void error(char *m);
184 static void gzip_mark(void **);
185 static void gzip_release(void **);
188 * This is set up by the setup-routine at boot-time
190 static unsigned char *real_mode; /* Pointer to real-mode data */
192 #define RM_EXT_MEM_K (*(unsigned short *)(real_mode + 0x2))
193 #ifndef STANDARD_MEMORY_BIOS_CALL
194 #define RM_ALT_MEM_K (*(unsigned long *)(real_mode + 0x1e0))
196 #define RM_SCREEN_INFO (*(struct screen_info *)(real_mode+0))
198 extern unsigned char input_data[];
199 extern int input_len;
201 static long bytes_out;
203 static void *malloc(int size);
204 static void free(void *where);
206 static void *memset(void *s, int c, unsigned n);
207 static void *memcpy(void *dest, const void *src, unsigned n);
209 static void putstr(const char *);
214 #define memptr unsigned
217 static memptr free_mem_ptr;
218 static memptr free_mem_end_ptr;
221 #define HEAP_SIZE 0x7000
223 #define HEAP_SIZE 0x4000
228 static int lines, cols;
230 #ifdef CONFIG_X86_NUMAQ
234 #include "../../../../lib/inflate.c"
236 static void *malloc(int size)
241 error("Malloc error");
242 if (free_mem_ptr <= 0)
243 error("Memory error");
245 free_mem_ptr = (free_mem_ptr + 3) & ~3; /* Align */
247 p = (void *)free_mem_ptr;
248 free_mem_ptr += size;
250 if (free_mem_ptr >= free_mem_end_ptr)
251 error("Out of memory");
256 static void free(void *where)
260 static void gzip_mark(void **ptr)
262 *ptr = (void *) free_mem_ptr;
265 static void gzip_release(void **ptr)
267 free_mem_ptr = (memptr) *ptr;
270 static void scroll(void)
274 memcpy(vidmem, vidmem + cols * 2, (lines - 1) * cols * 2);
275 for (i = (lines - 1) * cols * 2; i < lines * cols * 2; i += 2)
279 static void putstr(const char *s)
285 if (RM_SCREEN_INFO.orig_video_mode == 0 && lines == 0 && cols == 0)
289 x = RM_SCREEN_INFO.orig_x;
290 y = RM_SCREEN_INFO.orig_y;
292 while ((c = *s++) != '\0') {
300 vidmem [(x + cols * y) * 2] = c;
311 RM_SCREEN_INFO.orig_x = x;
312 RM_SCREEN_INFO.orig_y = y;
314 pos = (x + cols * y) * 2; /* Update cursor position */
316 outb(0xff & (pos >> 9), vidport+1);
318 outb(0xff & (pos >> 1), vidport+1);
321 static void *memset(void *s, int c, unsigned n)
326 for (i = 0; i < n; i++) ss[i] = c;
330 static void *memcpy(void *dest, const void *src, unsigned n)
336 for (i = 0; i < n; i++) d[i] = s[i];
340 /* ===========================================================================
341 * Fill the input buffer. This is called only when the buffer is empty
342 * and at least one byte is really needed.
344 static int fill_inbuf(void)
346 error("ran out of input data");
350 /* ===========================================================================
351 * Write the output window window[0..outcnt-1] and update crc and bytes_out.
352 * (Used for the decompressed data only.)
354 static void flush_window(void)
356 /* With my window equal to my output buffer
357 * I only need to compute the crc here.
359 unsigned long c = crc; /* temporary variable */
361 unsigned char *in, ch;
364 for (n = 0; n < outcnt; n++) {
366 c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
369 bytes_out += (unsigned long)outcnt;
373 static void error(char *x)
377 putstr("\n\n -- System halted");
383 static void parse_elf(void *output)
387 Elf64_Phdr *phdrs, *phdr;
390 Elf32_Phdr *phdrs, *phdr;
395 memcpy(&ehdr, output, sizeof(ehdr));
396 if (ehdr.e_ident[EI_MAG0] != ELFMAG0 ||
397 ehdr.e_ident[EI_MAG1] != ELFMAG1 ||
398 ehdr.e_ident[EI_MAG2] != ELFMAG2 ||
399 ehdr.e_ident[EI_MAG3] != ELFMAG3) {
400 error("Kernel is not a valid ELF file");
404 putstr("Parsing ELF... ");
406 phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum);
408 error("Failed to allocate space for phdrs");
410 memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum);
412 for (i = 0; i < ehdr.e_phnum; i++) {
415 switch (phdr->p_type) {
417 #ifdef CONFIG_RELOCATABLE
419 dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR);
421 dest = (void *)(phdr->p_paddr);
424 output + phdr->p_offset,
427 default: /* Ignore other PT_* */ break;
432 asmlinkage void decompress_kernel(void *rmode, memptr heap,
433 unsigned char *input_data,
434 unsigned long input_len,
435 unsigned char *output)
439 if (RM_SCREEN_INFO.orig_video_mode == 7) {
440 vidmem = (char *) 0xb0000;
443 vidmem = (char *) 0xb8000;
447 lines = RM_SCREEN_INFO.orig_video_lines;
448 cols = RM_SCREEN_INFO.orig_video_cols;
450 window = output; /* Output buffer (Normally at 1M) */
451 free_mem_ptr = heap; /* Heap */
452 free_mem_end_ptr = heap + HEAP_SIZE;
453 inbuf = input_data; /* Input buffer */
458 if ((unsigned long)output & (__KERNEL_ALIGN - 1))
459 error("Destination address not 2M aligned");
460 if ((unsigned long)output >= 0xffffffffffUL)
461 error("Destination address too large");
463 if ((u32)output & (CONFIG_PHYSICAL_ALIGN - 1))
464 error("Destination address not CONFIG_PHYSICAL_ALIGN aligned");
465 if (heap > ((-__PAGE_OFFSET-(512<<20)-1) & 0x7fffffff))
466 error("Destination address too large");
467 #ifndef CONFIG_RELOCATABLE
468 if ((u32)output != LOAD_PHYSICAL_ADDR)
469 error("Wrong destination address");
474 putstr("\nDecompressing Linux... ");
477 putstr("done.\nBooting the kernel.\n");