misc.c revision 020878ac427aa053414602cef975c2b5a2e33bf8 
1/*
2 * misc.c
3 *
4 * This is a collection of several routines from gzip-1.0.3
5 * adapted for Linux.
6 *
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
10 */
11
12/*
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
16 */
17#undef CONFIG_PARAVIRT
18#ifdef CONFIG_X86_32
19#define _ASM_DESC_H_ 1
20#endif
21
22#ifdef CONFIG_X86_64
23#define _LINUX_STRING_H_ 1
24#define __LINUX_BITMAP_H 1
25#endif
26
27#include <linux/linkage.h>
28#include <linux/screen_info.h>
29#include <linux/elf.h>
30#include <linux/io.h>
31#include <asm/page.h>
32#include <asm/boot.h>
33#include <asm/bootparam.h>
34
35/* WARNING!!
36 * This code is compiled with -fPIC and it is relocated dynamically
37 * at run time, but no relocation processing is performed.
38 * This means that it is not safe to place pointers in static structures.
39 */
40
41/*
42 * Getting to provable safe in place decompression is hard.
43 * Worst case behaviours need to be analyzed.
44 * Background information:
45 *
46 * The file layout is:
47 *    magic[2]
48 *    method[1]
49 *    flags[1]
50 *    timestamp[4]
51 *    extraflags[1]
52 *    os[1]
53 *    compressed data blocks[N]
54 *    crc[4] orig_len[4]
55 *
56 * resulting in 18 bytes of non compressed data overhead.
57 *
58 * Files divided into blocks
59 * 1 bit (last block flag)
60 * 2 bits (block type)
61 *
62 * 1 block occurs every 32K -1 bytes or when there 50% compression
63 * has been achieved. The smallest block type encoding is always used.
64 *
65 * stored:
66 *    32 bits length in bytes.
67 *
68 * fixed:
69 *    magic fixed tree.
70 *    symbols.
71 *
72 * dynamic:
73 *    dynamic tree encoding.
74 *    symbols.
75 *
76 *
77 * The buffer for decompression in place is the length of the
78 * uncompressed data, plus a small amount extra to keep the algorithm safe.
79 * The compressed data is placed at the end of the buffer.  The output
80 * pointer is placed at the start of the buffer and the input pointer
81 * is placed where the compressed data starts.  Problems will occur
82 * when the output pointer overruns the input pointer.
83 *
84 * The output pointer can only overrun the input pointer if the input
85 * pointer is moving faster than the output pointer.  A condition only
86 * triggered by data whose compressed form is larger than the uncompressed
87 * form.
88 *
89 * The worst case at the block level is a growth of the compressed data
90 * of 5 bytes per 32767 bytes.
91 *
92 * The worst case internal to a compressed block is very hard to figure.
93 * The worst case can at least be boundined by having one bit that represents
94 * 32764 bytes and then all of the rest of the bytes representing the very
95 * very last byte.
96 *
97 * All of which is enough to compute an amount of extra data that is required
98 * to be safe.  To avoid problems at the block level allocating 5 extra bytes
99 * per 32767 bytes of data is sufficient.  To avoind problems internal to a
100 * block adding an extra 32767 bytes (the worst case uncompressed block size)
101 * is sufficient, to ensure that in the worst case the decompressed data for
102 * block will stop the byte before the compressed data for a block begins.
103 * To avoid problems with the compressed data's meta information an extra 18
104 * bytes are needed.  Leading to the formula:
105 *
106 * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
107 *
108 * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
109 * Adding 32768 instead of 32767 just makes for round numbers.
110 * Adding the decompressor_size is necessary as it musht live after all
111 * of the data as well.  Last I measured the decompressor is about 14K.
112 * 10K of actual data and 4K of bss.
113 *
114 */
115
116/*
117 * gzip declarations
118 */
119
120#define OF(args)	args
121#define STATIC		static
122
123#undef memset
124#undef memcpy
125#define memzero(s, n)	memset((s), 0, (n))
126
127typedef unsigned char	uch;
128typedef unsigned short	ush;
129typedef unsigned long	ulg;
130
131/*
132 * Window size must be at least 32k, and a power of two.
133 * We don't actually have a window just a huge output buffer,
134 * so we report a 2G window size, as that should always be
135 * larger than our output buffer:
136 */
137#define WSIZE		0x80000000
138
139/* Input buffer: */
140static unsigned char	*inbuf;
141
142/* Sliding window buffer (and final output buffer): */
143static unsigned char	*window;
144
145/* Valid bytes in inbuf: */
146static unsigned		insize;
147
148/* Index of next byte to be processed in inbuf: */
149static unsigned		inptr;
150
151/* Bytes in output buffer: */
152static unsigned		outcnt;
153
154/* gzip flag byte */
155#define ASCII_FLAG	0x01 /* bit 0 set: file probably ASCII text */
156#define CONTINUATION	0x02 /* bit 1 set: continuation of multi-part gz file */
157#define EXTRA_FIELD	0x04 /* bit 2 set: extra field present */
158#define ORIG_NAM	0x08 /* bit 3 set: original file name present */
159#define COMMENT		0x10 /* bit 4 set: file comment present */
160#define ENCRYPTED	0x20 /* bit 5 set: file is encrypted */
161#define RESERVED	0xC0 /* bit 6, 7:  reserved */
162
163#define get_byte()	(inptr < insize ? inbuf[inptr++] : fill_inbuf())
164
165/* Diagnostic functions */
166#ifdef DEBUG
167#  define Assert(cond, msg) do { if (!(cond)) error(msg); } while (0)
168#  define Trace(x)	do { fprintf x; } while (0)
169#  define Tracev(x)	do { if (verbose) fprintf x ; } while (0)
170#  define Tracevv(x)	do { if (verbose > 1) fprintf x ; } while (0)
171#  define Tracec(c, x)	do { if (verbose && (c)) fprintf x ; } while (0)
172#  define Tracecv(c, x)	do { if (verbose > 1 && (c)) fprintf x ; } while (0)
173#else
174#  define Assert(cond, msg)
175#  define Trace(x)
176#  define Tracev(x)
177#  define Tracevv(x)
178#  define Tracec(c, x)
179#  define Tracecv(c, x)
180#endif
181
182static int  fill_inbuf(void);
183static void flush_window(void);
184static void error(char *m);
185
186/*
187 * This is set up by the setup-routine at boot-time
188 */
189static struct boot_params *real_mode;		/* Pointer to real-mode data */
190static int quiet;
191
192extern unsigned char input_data[];
193extern int input_len;
194
195static long bytes_out;
196
197static void *memset(void *s, int c, unsigned n);
198static void *memcpy(void *dest, const void *src, unsigned n);
199
200static void __putstr(int, const char *);
201#define putstr(__x)  __putstr(0, __x)
202
203#ifdef CONFIG_X86_64
204#define memptr long
205#else
206#define memptr unsigned
207#endif
208
209static memptr free_mem_ptr;
210static memptr free_mem_end_ptr;
211
212static char *vidmem;
213static int vidport;
214static int lines, cols;
215
216#include "../../../../lib/inflate.c"
217
218static void scroll(void)
219{
220	int i;
221
222	memcpy(vidmem, vidmem + cols * 2, (lines - 1) * cols * 2);
223	for (i = (lines - 1) * cols * 2; i < lines * cols * 2; i += 2)
224		vidmem[i] = ' ';
225}
226
227static void __putstr(int error, const char *s)
228{
229	int x, y, pos;
230	char c;
231
232#ifndef CONFIG_X86_VERBOSE_BOOTUP
233	if (!error)
234		return;
235#endif
236
237#ifdef CONFIG_X86_32
238	if (real_mode->screen_info.orig_video_mode == 0 &&
239	    lines == 0 && cols == 0)
240		return;
241#endif
242
243	x = real_mode->screen_info.orig_x;
244	y = real_mode->screen_info.orig_y;
245
246	while ((c = *s++) != '\0') {
247		if (c == '\n') {
248			x = 0;
249			if (++y >= lines) {
250				scroll();
251				y--;
252			}
253		} else {
254			vidmem[(x + cols * y) * 2] = c;
255			if (++x >= cols) {
256				x = 0;
257				if (++y >= lines) {
258					scroll();
259					y--;
260				}
261			}
262		}
263	}
264
265	real_mode->screen_info.orig_x = x;
266	real_mode->screen_info.orig_y = y;
267
268	pos = (x + cols * y) * 2;	/* Update cursor position */
269	outb(14, vidport);
270	outb(0xff & (pos >> 9), vidport+1);
271	outb(15, vidport);
272	outb(0xff & (pos >> 1), vidport+1);
273}
274
275static void *memset(void *s, int c, unsigned n)
276{
277	int i;
278	char *ss = s;
279
280	for (i = 0; i < n; i++)
281		ss[i] = c;
282	return s;
283}
284
285static void *memcpy(void *dest, const void *src, unsigned n)
286{
287	int i;
288	const char *s = src;
289	char *d = dest;
290
291	for (i = 0; i < n; i++)
292		d[i] = s[i];
293	return dest;
294}
295
296/* ===========================================================================
297 * Fill the input buffer. This is called only when the buffer is empty
298 * and at least one byte is really needed.
299 */
300static int fill_inbuf(void)
301{
302	error("ran out of input data");
303	return 0;
304}
305
306/* ===========================================================================
307 * Write the output window window[0..outcnt-1] and update crc and bytes_out.
308 * (Used for the decompressed data only.)
309 */
310static void flush_window(void)
311{
312	/* With my window equal to my output buffer
313	 * I only need to compute the crc here.
314	 */
315	unsigned long c = crc;         /* temporary variable */
316	unsigned n;
317	unsigned char *in, ch;
318
319	in = window;
320	for (n = 0; n < outcnt; n++) {
321		ch = *in++;
322		c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
323	}
324	crc = c;
325	bytes_out += (unsigned long)outcnt;
326	outcnt = 0;
327}
328
329static void error(char *x)
330{
331	__putstr(1, "\n\n");
332	__putstr(1, x);
333	__putstr(1, "\n\n -- System halted");
334
335	while (1)
336		asm("hlt");
337}
338
339static void parse_elf(void *output)
340{
341#ifdef CONFIG_X86_64
342	Elf64_Ehdr ehdr;
343	Elf64_Phdr *phdrs, *phdr;
344#else
345	Elf32_Ehdr ehdr;
346	Elf32_Phdr *phdrs, *phdr;
347#endif
348	void *dest;
349	int i;
350
351	memcpy(&ehdr, output, sizeof(ehdr));
352	if (ehdr.e_ident[EI_MAG0] != ELFMAG0 ||
353	   ehdr.e_ident[EI_MAG1] != ELFMAG1 ||
354	   ehdr.e_ident[EI_MAG2] != ELFMAG2 ||
355	   ehdr.e_ident[EI_MAG3] != ELFMAG3) {
356		error("Kernel is not a valid ELF file");
357		return;
358	}
359
360	if (!quiet)
361		putstr("Parsing ELF... ");
362
363	phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum);
364	if (!phdrs)
365		error("Failed to allocate space for phdrs");
366
367	memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum);
368
369	for (i = 0; i < ehdr.e_phnum; i++) {
370		phdr = &phdrs[i];
371
372		switch (phdr->p_type) {
373		case PT_LOAD:
374#ifdef CONFIG_RELOCATABLE
375			dest = output;
376			dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR);
377#else
378			dest = (void *)(phdr->p_paddr);
379#endif
380			memcpy(dest,
381			       output + phdr->p_offset,
382			       phdr->p_filesz);
383			break;
384		default: /* Ignore other PT_* */ break;
385		}
386	}
387}
388
389asmlinkage void decompress_kernel(void *rmode, memptr heap,
390				  unsigned char *input_data,
391				  unsigned long input_len,
392				  unsigned char *output)
393{
394	real_mode = rmode;
395
396	if (real_mode->hdr.loadflags & QUIET_FLAG)
397		quiet = 1;
398
399	if (real_mode->screen_info.orig_video_mode == 7) {
400		vidmem = (char *) 0xb0000;
401		vidport = 0x3b4;
402	} else {
403		vidmem = (char *) 0xb8000;
404		vidport = 0x3d4;
405	}
406
407	lines = real_mode->screen_info.orig_video_lines;
408	cols = real_mode->screen_info.orig_video_cols;
409
410	window = output;		/* Output buffer (Normally at 1M) */
411	free_mem_ptr     = heap;	/* Heap */
412	free_mem_end_ptr = heap + BOOT_HEAP_SIZE;
413	inbuf  = input_data;		/* Input buffer */
414	insize = input_len;
415	inptr  = 0;
416
417#ifdef CONFIG_X86_64
418	if ((unsigned long)output & (__KERNEL_ALIGN - 1))
419		error("Destination address not 2M aligned");
420	if ((unsigned long)output >= 0xffffffffffUL)
421		error("Destination address too large");
422#else
423	if ((u32)output & (CONFIG_PHYSICAL_ALIGN - 1))
424		error("Destination address not CONFIG_PHYSICAL_ALIGN aligned");
425	if (heap > ((-__PAGE_OFFSET-(512<<20)-1) & 0x7fffffff))
426		error("Destination address too large");
427#ifndef CONFIG_RELOCATABLE
428	if ((u32)output != LOAD_PHYSICAL_ADDR)
429		error("Wrong destination address");
430#endif
431#endif
432
433	makecrc();
434	if (!quiet)
435		putstr("\nDecompressing Linux... ");
436	gunzip();
437	parse_elf(output);
438	if (!quiet)
439		putstr("done.\nBooting the kernel.\n");
440	return;
441}
442