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