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 #define STATIC static 120 121 #undef memset 122 #undef memcpy 123 #define memzero(s, n) memset((s), 0, (n)) 124 125 126 static void error(char *m); 127 128 /* 129 * This is set up by the setup-routine at boot-time 130 */ 131 static struct boot_params *real_mode; /* Pointer to real-mode data */ 132 static int quiet; 133 134 static void *memset(void *s, int c, unsigned n); 135 void *memcpy(void *dest, const void *src, unsigned n); 136 137 static void __putstr(int, const char *); 138 #define putstr(__x) __putstr(0, __x) 139 140 #ifdef CONFIG_X86_64 141 #define memptr long 142 #else 143 #define memptr unsigned 144 #endif 145 146 static memptr free_mem_ptr; 147 static memptr free_mem_end_ptr; 148 149 static char *vidmem; 150 static int vidport; 151 static int lines, cols; 152 153 #ifdef CONFIG_KERNEL_GZIP 154 #include "../../../../lib/decompress_inflate.c" 155 #endif 156 157 #ifdef CONFIG_KERNEL_BZIP2 158 #include "../../../../lib/decompress_bunzip2.c" 159 #endif 160 161 #ifdef CONFIG_KERNEL_LZMA 162 #include "../../../../lib/decompress_unlzma.c" 163 #endif 164 165 #ifdef CONFIG_KERNEL_LZO 166 #include "../../../../lib/decompress_unlzo.c" 167 #endif 168 169 static void scroll(void) 170 { 171 int i; 172 173 memcpy(vidmem, vidmem + cols * 2, (lines - 1) * cols * 2); 174 for (i = (lines - 1) * cols * 2; i < lines * cols * 2; i += 2) 175 vidmem[i] = ' '; 176 } 177 178 static void __putstr(int error, const char *s) 179 { 180 int x, y, pos; 181 char c; 182 183 #ifndef CONFIG_X86_VERBOSE_BOOTUP 184 if (!error) 185 return; 186 #endif 187 188 #ifdef CONFIG_X86_32 189 if (real_mode->screen_info.orig_video_mode == 0 && 190 lines == 0 && cols == 0) 191 return; 192 #endif 193 194 x = real_mode->screen_info.orig_x; 195 y = real_mode->screen_info.orig_y; 196 197 while ((c = *s++) != '\0') { 198 if (c == '\n') { 199 x = 0; 200 if (++y >= lines) { 201 scroll(); 202 y--; 203 } 204 } else { 205 vidmem[(x + cols * y) * 2] = c; 206 if (++x >= cols) { 207 x = 0; 208 if (++y >= lines) { 209 scroll(); 210 y--; 211 } 212 } 213 } 214 } 215 216 real_mode->screen_info.orig_x = x; 217 real_mode->screen_info.orig_y = y; 218 219 pos = (x + cols * y) * 2; /* Update cursor position */ 220 outb(14, vidport); 221 outb(0xff & (pos >> 9), vidport+1); 222 outb(15, vidport); 223 outb(0xff & (pos >> 1), vidport+1); 224 } 225 226 static void *memset(void *s, int c, unsigned n) 227 { 228 int i; 229 char *ss = s; 230 231 for (i = 0; i < n; i++) 232 ss[i] = c; 233 return s; 234 } 235 236 void *memcpy(void *dest, const void *src, unsigned n) 237 { 238 int i; 239 const char *s = src; 240 char *d = dest; 241 242 for (i = 0; i < n; i++) 243 d[i] = s[i]; 244 return dest; 245 } 246 247 248 static void error(char *x) 249 { 250 __putstr(1, "\n\n"); 251 __putstr(1, x); 252 __putstr(1, "\n\n -- System halted"); 253 254 while (1) 255 asm("hlt"); 256 } 257 258 static void parse_elf(void *output) 259 { 260 #ifdef CONFIG_X86_64 261 Elf64_Ehdr ehdr; 262 Elf64_Phdr *phdrs, *phdr; 263 #else 264 Elf32_Ehdr ehdr; 265 Elf32_Phdr *phdrs, *phdr; 266 #endif 267 void *dest; 268 int i; 269 270 memcpy(&ehdr, output, sizeof(ehdr)); 271 if (ehdr.e_ident[EI_MAG0] != ELFMAG0 || 272 ehdr.e_ident[EI_MAG1] != ELFMAG1 || 273 ehdr.e_ident[EI_MAG2] != ELFMAG2 || 274 ehdr.e_ident[EI_MAG3] != ELFMAG3) { 275 error("Kernel is not a valid ELF file"); 276 return; 277 } 278 279 if (!quiet) 280 putstr("Parsing ELF... "); 281 282 phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum); 283 if (!phdrs) 284 error("Failed to allocate space for phdrs"); 285 286 memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum); 287 288 for (i = 0; i < ehdr.e_phnum; i++) { 289 phdr = &phdrs[i]; 290 291 switch (phdr->p_type) { 292 case PT_LOAD: 293 #ifdef CONFIG_RELOCATABLE 294 dest = output; 295 dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR); 296 #else 297 dest = (void *)(phdr->p_paddr); 298 #endif 299 memcpy(dest, 300 output + phdr->p_offset, 301 phdr->p_filesz); 302 break; 303 default: /* Ignore other PT_* */ break; 304 } 305 } 306 } 307 308 asmlinkage void decompress_kernel(void *rmode, memptr heap, 309 unsigned char *input_data, 310 unsigned long input_len, 311 unsigned char *output) 312 { 313 real_mode = rmode; 314 315 if (real_mode->hdr.loadflags & QUIET_FLAG) 316 quiet = 1; 317 318 if (real_mode->screen_info.orig_video_mode == 7) { 319 vidmem = (char *) 0xb0000; 320 vidport = 0x3b4; 321 } else { 322 vidmem = (char *) 0xb8000; 323 vidport = 0x3d4; 324 } 325 326 lines = real_mode->screen_info.orig_video_lines; 327 cols = real_mode->screen_info.orig_video_cols; 328 329 free_mem_ptr = heap; /* Heap */ 330 free_mem_end_ptr = heap + BOOT_HEAP_SIZE; 331 332 if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1)) 333 error("Destination address inappropriately aligned"); 334 #ifdef CONFIG_X86_64 335 if (heap > 0x3fffffffffffUL) 336 error("Destination address too large"); 337 #else 338 if (heap > ((-__PAGE_OFFSET-(512<<20)-1) & 0x7fffffff)) 339 error("Destination address too large"); 340 #endif 341 #ifndef CONFIG_RELOCATABLE 342 if ((unsigned long)output != LOAD_PHYSICAL_ADDR) 343 error("Wrong destination address"); 344 #endif 345 346 if (!quiet) 347 putstr("\nDecompressing Linux... "); 348 decompress(input_data, input_len, NULL, NULL, output, NULL, error); 349 parse_elf(output); 350 if (!quiet) 351 putstr("done.\nBooting the kernel.\n"); 352 return; 353 } 354