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_X86_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 127 typedef unsigned char uch; 128 typedef unsigned short ush; 129 typedef 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: */ 140 static unsigned char *inbuf; 141 142 /* Sliding window buffer (and final output buffer): */ 143 static unsigned char *window; 144 145 /* Valid bytes in inbuf: */ 146 static unsigned insize; 147 148 /* Index of next byte to be processed in inbuf: */ 149 static unsigned inptr; 150 151 /* Bytes in output buffer: */ 152 static 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 182 static int fill_inbuf(void); 183 static void flush_window(void); 184 static void error(char *m); 185 186 /* 187 * This is set up by the setup-routine at boot-time 188 */ 189 static struct boot_params *real_mode; /* Pointer to real-mode data */ 190 static int quiet; 191 192 extern unsigned char input_data[]; 193 extern int input_len; 194 195 static long bytes_out; 196 197 static void *memset(void *s, int c, unsigned n); 198 static void *memcpy(void *dest, const void *src, unsigned n); 199 200 static 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 209 static memptr free_mem_ptr; 210 static memptr free_mem_end_ptr; 211 212 static char *vidmem; 213 static int vidport; 214 static int lines, cols; 215 216 #include "../../../../lib/inflate.c" 217 218 static 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 227 static 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 275 static 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 285 static 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 */ 300 static 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 */ 310 static 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 329 static 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 339 static 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 389 asmlinkage 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