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