misc_32.c 9.7 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8 9 10 11
/*
 * misc.c
 * 
 * This is a collection of several routines from gzip-1.0.3 
 * adapted for Linux.
 *
 * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
 * puts by Nick Holloway 1993, better puts by Martin Mares 1995
 * High loaded stuff by Hans Lermen & Werner Almesberger, Feb. 1996
 */

12
#undef CONFIG_PARAVIRT
L
Linus Torvalds 已提交
13 14
#include <linux/linkage.h>
#include <linux/vmalloc.h>
15
#include <linux/screen_info.h>
L
Linus Torvalds 已提交
16
#include <asm/io.h>
17
#include <asm/page.h>
18
#include <asm/boot.h>
19 20 21 22 23 24 25 26 27

/* WARNING!!
 * This code is compiled with -fPIC and it is relocated dynamically
 * at run time, but no relocation processing is performed.
 * This means that it is not safe to place pointers in static structures.
 */

/*
 * Getting to provable safe in place decompression is hard.
S
Simon Arlott 已提交
28
 * Worst case behaviours need to be analyzed.
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
 * Background information:
 *
 * The file layout is:
 *    magic[2]
 *    method[1]
 *    flags[1]
 *    timestamp[4]
 *    extraflags[1]
 *    os[1]
 *    compressed data blocks[N]
 *    crc[4] orig_len[4]
 *
 * resulting in 18 bytes of non compressed data overhead.
 *
 * Files divided into blocks
 * 1 bit (last block flag)
 * 2 bits (block type)
 *
 * 1 block occurs every 32K -1 bytes or when there 50% compression has been achieved.
 * The smallest block type encoding is always used.
 *
 * stored:
 *    32 bits length in bytes.
 *
 * fixed:
 *    magic fixed tree.
 *    symbols.
 *
 * dynamic:
 *    dynamic tree encoding.
 *    symbols.
 *
 *
 * The buffer for decompression in place is the length of the
 * uncompressed data, plus a small amount extra to keep the algorithm safe.
 * The compressed data is placed at the end of the buffer.  The output
 * pointer is placed at the start of the buffer and the input pointer
 * is placed where the compressed data starts.  Problems will occur
 * when the output pointer overruns the input pointer.
 *
 * The output pointer can only overrun the input pointer if the input
 * pointer is moving faster than the output pointer.  A condition only
 * triggered by data whose compressed form is larger than the uncompressed
 * form.
 *
 * The worst case at the block level is a growth of the compressed data
 * of 5 bytes per 32767 bytes.
 *
 * The worst case internal to a compressed block is very hard to figure.
 * The worst case can at least be boundined by having one bit that represents
 * 32764 bytes and then all of the rest of the bytes representing the very
 * very last byte.
 *
 * All of which is enough to compute an amount of extra data that is required
 * to be safe.  To avoid problems at the block level allocating 5 extra bytes
 * per 32767 bytes of data is sufficient.  To avoind problems internal to a block
 * adding an extra 32767 bytes (the worst case uncompressed block size) is
 * sufficient, to ensure that in the worst case the decompressed data for
 * block will stop the byte before the compressed data for a block begins.
 * To avoid problems with the compressed data's meta information an extra 18
 * bytes are needed.  Leading to the formula:
 *
 * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
 *
 * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
 * Adding 32768 instead of 32767 just makes for round numbers.
 * Adding the decompressor_size is necessary as it musht live after all
 * of the data as well.  Last I measured the decompressor is about 14K.
S
Simon Arlott 已提交
97
 * 10K of actual data and 4K of bss.
98 99
 *
 */
L
Linus Torvalds 已提交
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

/*
 * gzip declarations
 */

#define OF(args)  args
#define STATIC static

#undef memset
#undef memcpy
#define memzero(s, n)     memset ((s), 0, (n))

typedef unsigned char  uch;
typedef unsigned short ush;
typedef unsigned long  ulg;

116 117 118 119 120 121 122
#define WSIZE 0x80000000	/* Window size must be at least 32k,
				 * and a power of two
				 * We don't actually have a window just
				 * a huge output buffer so I report
				 * a 2G windows size, as that should
				 * always be larger than our output buffer.
				 */
L
Linus Torvalds 已提交
123

124 125
static uch *inbuf;	/* input buffer */
static uch *window;	/* Sliding window buffer, (and final output buffer) */
L
Linus Torvalds 已提交
126

127 128 129
static unsigned insize;  /* valid bytes in inbuf */
static unsigned inptr;   /* index of next byte to be processed in inbuf */
static unsigned outcnt;  /* bytes in output buffer */
L
Linus Torvalds 已提交
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

/* gzip flag byte */
#define ASCII_FLAG   0x01 /* bit 0 set: file probably ASCII text */
#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
#define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */
#define ORIG_NAME    0x08 /* bit 3 set: original file name present */
#define COMMENT      0x10 /* bit 4 set: file comment present */
#define ENCRYPTED    0x20 /* bit 5 set: file is encrypted */
#define RESERVED     0xC0 /* bit 6,7:   reserved */

#define get_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf())
		
/* Diagnostic functions */
#ifdef DEBUG
#  define Assert(cond,msg) {if(!(cond)) error(msg);}
#  define Trace(x) fprintf x
#  define Tracev(x) {if (verbose) fprintf x ;}
#  define Tracevv(x) {if (verbose>1) fprintf x ;}
#  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
#  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
#else
#  define Assert(cond,msg)
#  define Trace(x)
#  define Tracev(x)
#  define Tracevv(x)
#  define Tracec(c,x)
#  define Tracecv(c,x)
#endif

static int  fill_inbuf(void);
static void flush_window(void);
static void error(char *m);
static void gzip_mark(void **);
static void gzip_release(void **);
  
/*
 * This is set up by the setup-routine at boot-time
 */
static unsigned char *real_mode; /* Pointer to real-mode data */

#define RM_EXT_MEM_K   (*(unsigned short *)(real_mode + 0x2))
#ifndef STANDARD_MEMORY_BIOS_CALL
#define RM_ALT_MEM_K   (*(unsigned long *)(real_mode + 0x1e0))
#endif
#define RM_SCREEN_INFO (*(struct screen_info *)(real_mode+0))

176
extern unsigned char input_data[];
L
Linus Torvalds 已提交
177 178 179 180 181 182 183
extern int input_len;

static long bytes_out = 0;

static void *malloc(int size);
static void free(void *where);

184 185 186
static void *memset(void *s, int c, unsigned n);
static void *memcpy(void *dest, const void *src, unsigned n);

L
Linus Torvalds 已提交
187 188
static void putstr(const char *);

189 190
static unsigned long free_mem_ptr;
static unsigned long free_mem_end_ptr;
L
Linus Torvalds 已提交
191

192
#define HEAP_SIZE             0x4000
L
Linus Torvalds 已提交
193 194 195 196 197 198

static char *vidmem = (char *)0xb8000;
static int vidport;
static int lines, cols;

#ifdef CONFIG_X86_NUMAQ
199
void *xquad_portio;
L
Linus Torvalds 已提交
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
#endif

#include "../../../../lib/inflate.c"

static void *malloc(int size)
{
	void *p;

	if (size <0) error("Malloc error");
	if (free_mem_ptr <= 0) error("Memory error");

	free_mem_ptr = (free_mem_ptr + 3) & ~3;	/* Align */

	p = (void *)free_mem_ptr;
	free_mem_ptr += size;

	if (free_mem_ptr >= free_mem_end_ptr)
		error("Out of memory");

	return p;
}

static void free(void *where)
{	/* Don't care */
}

static void gzip_mark(void **ptr)
{
	*ptr = (void *) free_mem_ptr;
}

static void gzip_release(void **ptr)
{
233
	free_mem_ptr = (unsigned long) *ptr;
L
Linus Torvalds 已提交
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
}
 
static void scroll(void)
{
	int i;

	memcpy ( vidmem, vidmem + cols * 2, ( lines - 1 ) * cols * 2 );
	for ( i = ( lines - 1 ) * cols * 2; i < lines * cols * 2; i += 2 )
		vidmem[i] = ' ';
}

static void putstr(const char *s)
{
	int x,y,pos;
	char c;

	x = RM_SCREEN_INFO.orig_x;
	y = RM_SCREEN_INFO.orig_y;

	while ( ( c = *s++ ) != '\0' ) {
		if ( c == '\n' ) {
			x = 0;
			if ( ++y >= lines ) {
				scroll();
				y--;
			}
		} else {
261
			vidmem [ ( x + cols * y ) * 2 ] = c;
L
Linus Torvalds 已提交
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
			if ( ++x >= cols ) {
				x = 0;
				if ( ++y >= lines ) {
					scroll();
					y--;
				}
			}
		}
	}

	RM_SCREEN_INFO.orig_x = x;
	RM_SCREEN_INFO.orig_y = y;

	pos = (x + cols * y) * 2;	/* Update cursor position */
	outb_p(14, vidport);
	outb_p(0xff & (pos >> 9), vidport+1);
	outb_p(15, vidport);
	outb_p(0xff & (pos >> 1), vidport+1);
}

282
static void* memset(void* s, int c, unsigned n)
L
Linus Torvalds 已提交
283 284 285 286 287 288 289 290
{
	int i;
	char *ss = (char*)s;

	for (i=0;i<n;i++) ss[i] = c;
	return s;
}

291
static void* memcpy(void* dest, const void* src, unsigned n)
L
Linus Torvalds 已提交
292 293
{
	int i;
294
	char *d = (char *)dest, *s = (char *)src;
L
Linus Torvalds 已提交
295

296 297
	for (i=0;i<n;i++) d[i] = s[i];
	return dest;
L
Linus Torvalds 已提交
298 299 300 301 302 303 304 305
}

/* ===========================================================================
 * Fill the input buffer. This is called only when the buffer is empty
 * and at least one byte is really needed.
 */
static int fill_inbuf(void)
{
306 307
	error("ran out of input data");
	return 0;
L
Linus Torvalds 已提交
308 309 310 311 312 313 314 315
}

/* ===========================================================================
 * Write the output window window[0..outcnt-1] and update crc and bytes_out.
 * (Used for the decompressed data only.)
 */
static void flush_window(void)
{
316 317 318 319 320 321 322 323 324 325 326 327 328 329 330
	/* With my window equal to my output buffer
	 * I only need to compute the crc here.
	 */
	ulg c = crc;         /* temporary variable */
	unsigned n;
	uch *in, ch;

	in = window;
	for (n = 0; n < outcnt; n++) {
		ch = *in++;
		c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
	}
	crc = c;
	bytes_out += (ulg)outcnt;
	outcnt = 0;
L
Linus Torvalds 已提交
331 332 333 334 335 336 337 338 339 340 341
}

static void error(char *x)
{
	putstr("\n\n");
	putstr(x);
	putstr("\n\n -- System halted");

	while(1);	/* Halt */
}

342 343
asmlinkage void decompress_kernel(void *rmode, unsigned long end,
			uch *input_data, unsigned long input_len, uch *output)
L
Linus Torvalds 已提交
344 345 346 347 348 349 350 351 352 353 354 355 356 357
{
	real_mode = rmode;

	if (RM_SCREEN_INFO.orig_video_mode == 7) {
		vidmem = (char *) 0xb0000;
		vidport = 0x3b4;
	} else {
		vidmem = (char *) 0xb8000;
		vidport = 0x3d4;
	}

	lines = RM_SCREEN_INFO.orig_video_lines;
	cols = RM_SCREEN_INFO.orig_video_cols;

358 359 360 361 362 363 364
	window = output;  	/* Output buffer (Normally at 1M) */
	free_mem_ptr     = end;	/* Heap  */
	free_mem_end_ptr = end + HEAP_SIZE;
	inbuf  = input_data;	/* Input buffer */
	insize = input_len;
	inptr  = 0;

365 366
	if ((u32)output & (CONFIG_PHYSICAL_ALIGN -1))
		error("Destination address not CONFIG_PHYSICAL_ALIGN aligned");
367 368 369
	if (end > ((-__PAGE_OFFSET-(512 <<20)-1) & 0x7fffffff))
		error("Destination address too large");
#ifndef CONFIG_RELOCATABLE
370
	if ((u32)output != LOAD_PHYSICAL_ADDR)
371 372
		error("Wrong destination address");
#endif
L
Linus Torvalds 已提交
373 374 375 376 377

	makecrc();
	putstr("Uncompressing Linux... ");
	gunzip();
	putstr("Ok, booting the kernel.\n");
378
	return;
L
Linus Torvalds 已提交
379
}