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 #include <linux/linkage.h> 23 #include <linux/screen_info.h> 24 #include <linux/elf.h> 25 #include <linux/io.h> 26 #include <asm/page.h> 27 #include <asm/boot.h> 28 #include <asm/bootparam.h> 29 30 /* WARNING!! 31 * This code is compiled with -fPIC and it is relocated dynamically 32 * at run time, but no relocation processing is performed. 33 * This means that it is not safe to place pointers in static structures. 34 */ 35 36 /* 37 * Getting to provable safe in place decompression is hard. 38 * Worst case behaviours need to be analyzed. 39 * Background information: 40 * 41 * The file layout is: 42 * magic[2] 43 * method[1] 44 * flags[1] 45 * timestamp[4] 46 * extraflags[1] 47 * os[1] 48 * compressed data blocks[N] 49 * crc[4] orig_len[4] 50 * 51 * resulting in 18 bytes of non compressed data overhead. 52 * 53 * Files divided into blocks 54 * 1 bit (last block flag) 55 * 2 bits (block type) 56 * 57 * 1 block occurs every 32K -1 bytes or when there 50% compression 58 * has been achieved. The smallest block type encoding is always used. 59 * 60 * stored: 61 * 32 bits length in bytes. 62 * 63 * fixed: 64 * magic fixed tree. 65 * symbols. 66 * 67 * dynamic: 68 * dynamic tree encoding. 69 * symbols. 70 * 71 * 72 * The buffer for decompression in place is the length of the 73 * uncompressed data, plus a small amount extra to keep the algorithm safe. 74 * The compressed data is placed at the end of the buffer. The output 75 * pointer is placed at the start of the buffer and the input pointer 76 * is placed where the compressed data starts. Problems will occur 77 * when the output pointer overruns the input pointer. 78 * 79 * The output pointer can only overrun the input pointer if the input 80 * pointer is moving faster than the output pointer. A condition only 81 * triggered by data whose compressed form is larger than the uncompressed 82 * form. 83 * 84 * The worst case at the block level is a growth of the compressed data 85 * of 5 bytes per 32767 bytes. 86 * 87 * The worst case internal to a compressed block is very hard to figure. 88 * The worst case can at least be boundined by having one bit that represents 89 * 32764 bytes and then all of the rest of the bytes representing the very 90 * very last byte. 91 * 92 * All of which is enough to compute an amount of extra data that is required 93 * to be safe. To avoid problems at the block level allocating 5 extra bytes 94 * per 32767 bytes of data is sufficient. To avoind problems internal to a 95 * block adding an extra 32767 bytes (the worst case uncompressed block size) 96 * is sufficient, to ensure that in the worst case the decompressed data for 97 * block will stop the byte before the compressed data for a block begins. 98 * To avoid problems with the compressed data's meta information an extra 18 99 * bytes are needed. Leading to the formula: 100 * 101 * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size. 102 * 103 * Adding 8 bytes per 32K is a bit excessive but much easier to calculate. 104 * Adding 32768 instead of 32767 just makes for round numbers. 105 * Adding the decompressor_size is necessary as it musht live after all 106 * of the data as well. Last I measured the decompressor is about 14K. 107 * 10K of actual data and 4K of bss. 108 * 109 */ 110 111 /* 112 * gzip declarations 113 */ 114 #define STATIC static 115 116 #undef memset 117 #undef memcpy 118 #define memzero(s, n) memset((s), 0, (n)) 119 120 121 static void error(char *m); 122 123 /* 124 * This is set up by the setup-routine at boot-time 125 */ 126 static struct boot_params *real_mode; /* Pointer to real-mode data */ 127 static int quiet; 128 129 void *memset(void *s, int c, size_t n); 130 void *memcpy(void *dest, const void *src, size_t n); 131 132 static void __putstr(int, const char *); 133 #define putstr(__x) __putstr(0, __x) 134 135 #ifdef CONFIG_X86_64 136 #define memptr long 137 #else 138 #define memptr unsigned 139 #endif 140 141 static memptr free_mem_ptr; 142 static memptr free_mem_end_ptr; 143 144 static char *vidmem; 145 static int vidport; 146 static int lines, cols; 147 148 #ifdef CONFIG_KERNEL_GZIP 149 #include "../../../../lib/decompress_inflate.c" 150 #endif 151 152 #ifdef CONFIG_KERNEL_BZIP2 153 #include "../../../../lib/decompress_bunzip2.c" 154 #endif 155 156 #ifdef CONFIG_KERNEL_LZMA 157 #include "../../../../lib/decompress_unlzma.c" 158 #endif 159 160 #ifdef CONFIG_KERNEL_LZO 161 #include "../../../../lib/decompress_unlzo.c" 162 #endif 163 164 static void scroll(void) 165 { 166 int i; 167 168 memcpy(vidmem, vidmem + cols * 2, (lines - 1) * cols * 2); 169 for (i = (lines - 1) * cols * 2; i < lines * cols * 2; i += 2) 170 vidmem[i] = ' '; 171 } 172 173 static void __putstr(int error, const char *s) 174 { 175 int x, y, pos; 176 char c; 177 178 #ifndef CONFIG_X86_VERBOSE_BOOTUP 179 if (!error) 180 return; 181 #endif 182 183 if (real_mode->screen_info.orig_video_mode == 0 && 184 lines == 0 && cols == 0) 185 return; 186 187 x = real_mode->screen_info.orig_x; 188 y = real_mode->screen_info.orig_y; 189 190 while ((c = *s++) != '\0') { 191 if (c == '\n') { 192 x = 0; 193 if (++y >= lines) { 194 scroll(); 195 y--; 196 } 197 } else { 198 vidmem[(x + cols * y) * 2] = c; 199 if (++x >= cols) { 200 x = 0; 201 if (++y >= lines) { 202 scroll(); 203 y--; 204 } 205 } 206 } 207 } 208 209 real_mode->screen_info.orig_x = x; 210 real_mode->screen_info.orig_y = y; 211 212 pos = (x + cols * y) * 2; /* Update cursor position */ 213 outb(14, vidport); 214 outb(0xff & (pos >> 9), vidport+1); 215 outb(15, vidport); 216 outb(0xff & (pos >> 1), vidport+1); 217 } 218 219 void *memset(void *s, int c, size_t n) 220 { 221 int i; 222 char *ss = s; 223 224 for (i = 0; i < n; i++) 225 ss[i] = c; 226 return s; 227 } 228 229 void *memcpy(void *dest, const void *src, size_t n) 230 { 231 int i; 232 const char *s = src; 233 char *d = dest; 234 235 for (i = 0; i < n; i++) 236 d[i] = s[i]; 237 return dest; 238 } 239 240 241 static void error(char *x) 242 { 243 __putstr(1, "\n\n"); 244 __putstr(1, x); 245 __putstr(1, "\n\n -- System halted"); 246 247 while (1) 248 asm("hlt"); 249 } 250 251 static void parse_elf(void *output) 252 { 253 #ifdef CONFIG_X86_64 254 Elf64_Ehdr ehdr; 255 Elf64_Phdr *phdrs, *phdr; 256 #else 257 Elf32_Ehdr ehdr; 258 Elf32_Phdr *phdrs, *phdr; 259 #endif 260 void *dest; 261 int i; 262 263 memcpy(&ehdr, output, sizeof(ehdr)); 264 if (ehdr.e_ident[EI_MAG0] != ELFMAG0 || 265 ehdr.e_ident[EI_MAG1] != ELFMAG1 || 266 ehdr.e_ident[EI_MAG2] != ELFMAG2 || 267 ehdr.e_ident[EI_MAG3] != ELFMAG3) { 268 error("Kernel is not a valid ELF file"); 269 return; 270 } 271 272 if (!quiet) 273 putstr("Parsing ELF... "); 274 275 phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum); 276 if (!phdrs) 277 error("Failed to allocate space for phdrs"); 278 279 memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum); 280 281 for (i = 0; i < ehdr.e_phnum; i++) { 282 phdr = &phdrs[i]; 283 284 switch (phdr->p_type) { 285 case PT_LOAD: 286 #ifdef CONFIG_RELOCATABLE 287 dest = output; 288 dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR); 289 #else 290 dest = (void *)(phdr->p_paddr); 291 #endif 292 memcpy(dest, 293 output + phdr->p_offset, 294 phdr->p_filesz); 295 break; 296 default: /* Ignore other PT_* */ break; 297 } 298 } 299 } 300 301 asmlinkage void decompress_kernel(void *rmode, memptr heap, 302 unsigned char *input_data, 303 unsigned long input_len, 304 unsigned char *output) 305 { 306 real_mode = rmode; 307 308 if (real_mode->hdr.loadflags & QUIET_FLAG) 309 quiet = 1; 310 311 if (real_mode->screen_info.orig_video_mode == 7) { 312 vidmem = (char *) 0xb0000; 313 vidport = 0x3b4; 314 } else { 315 vidmem = (char *) 0xb8000; 316 vidport = 0x3d4; 317 } 318 319 lines = real_mode->screen_info.orig_video_lines; 320 cols = real_mode->screen_info.orig_video_cols; 321 322 free_mem_ptr = heap; /* Heap */ 323 free_mem_end_ptr = heap + BOOT_HEAP_SIZE; 324 325 if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1)) 326 error("Destination address inappropriately aligned"); 327 #ifdef CONFIG_X86_64 328 if (heap > 0x3fffffffffffUL) 329 error("Destination address too large"); 330 #else 331 if (heap > ((-__PAGE_OFFSET-(512<<20)-1) & 0x7fffffff)) 332 error("Destination address too large"); 333 #endif 334 #ifndef CONFIG_RELOCATABLE 335 if ((unsigned long)output != LOAD_PHYSICAL_ADDR) 336 error("Wrong destination address"); 337 #endif 338 339 if (!quiet) 340 putstr("\nDecompressing Linux... "); 341 decompress(input_data, input_len, NULL, NULL, output, NULL, error); 342 parse_elf(output); 343 if (!quiet) 344 putstr("done.\nBooting the kernel.\n"); 345 return; 346 } 347