arch/x86/boot/compressed/misc.c

   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 #ifdef CONFIG_X86_32
 184         if (real_mode->screen_info.orig_video_mode == 0 &&
 185             lines == 0 && cols == 0)
 186                 return;
 187 #endif
 188
 189         x = real_mode->screen_info.orig_x;
 190         y = real_mode->screen_info.orig_y;
 191
 192         while ((c = *s++) != '\0') {
 193                 if (c == '\n') {
 194                         x = 0;
 195                         if (++y >= lines) {
 196                                 scroll();
 197                                 y--;
 198                         }
 199                 } else {
 200                         vidmem[(x + cols * y) * 2] = c;
 201                         if (++x >= cols) {
 202                                 x = 0;
 203                                 if (++y >= lines) {
 204                                         scroll();
 205                                         y--;
 206                                 }
 207                         }
 208                 }
 209         }
 210
 211         real_mode->screen_info.orig_x = x;
 212         real_mode->screen_info.orig_y = y;
 213
 214         pos = (x + cols * y) * 2;       /* Update cursor position */
 215         outb(14, vidport);
 216         outb(0xff & (pos >> 9), vidport+1);
 217         outb(15, vidport);
 218         outb(0xff & (pos >> 1), vidport+1);
 219 }
 220
 221 void *memset(void *s, int c, size_t n)
 222 {
 223         int i;
 224         char *ss = s;
 225
 226         for (i = 0; i < n; i++)
 227                 ss[i] = c;
 228         return s;
 229 }
 230
 231 void *memcpy(void *dest, const void *src, size_t n)
 232 {
 233         int i;
 234         const char *s = src;
 235         char *d = dest;
 236
 237         for (i = 0; i < n; i++)
 238                 d[i] = s[i];
 239         return dest;
 240 }
 241
 242
 243 static void error(char *x)
 244 {
 245         __putstr(1, "\n\n");
 246         __putstr(1, x);
 247         __putstr(1, "\n\n -- System halted");
 248
 249         while (1)
 250                 asm("hlt");
 251 }
 252
 253 static void parse_elf(void *output)
 254 {
 255 #ifdef CONFIG_X86_64
 256         Elf64_Ehdr ehdr;
 257         Elf64_Phdr *phdrs, *phdr;
 258 #else
 259         Elf32_Ehdr ehdr;
 260         Elf32_Phdr *phdrs, *phdr;
 261 #endif
 262         void *dest;
 263         int i;
 264
 265         memcpy(&ehdr, output, sizeof(ehdr));
 266         if (ehdr.e_ident[EI_MAG0] != ELFMAG0 ||
 267            ehdr.e_ident[EI_MAG1] != ELFMAG1 ||
 268            ehdr.e_ident[EI_MAG2] != ELFMAG2 ||
 269            ehdr.e_ident[EI_MAG3] != ELFMAG3) {
 270                 error("Kernel is not a valid ELF file");
 271                 return;
 272         }
 273
 274         if (!quiet)
 275                 putstr("Parsing ELF... ");
 276
 277         phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum);
 278         if (!phdrs)
 279                 error("Failed to allocate space for phdrs");
 280
 281         memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum);
 282
 283         for (i = 0; i < ehdr.e_phnum; i++) {
 284                 phdr = &phdrs[i];
 285
 286                 switch (phdr->p_type) {
 287                 case PT_LOAD:
 288 #ifdef CONFIG_RELOCATABLE
 289                         dest = output;
 290                         dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR);
 291 #else
 292                         dest = (void *)(phdr->p_paddr);
 293 #endif
 294                         memcpy(dest,
 295                                output + phdr->p_offset,
 296                                phdr->p_filesz);
 297                         break;
 298                 default: /* Ignore other PT_* */ break;
 299                 }
 300         }
 301 }
 302
 303 asmlinkage void decompress_kernel(void *rmode, memptr heap,
 304                                   unsigned char *input_data,
 305                                   unsigned long input_len,
 306                                   unsigned char *output)
 307 {
 308         real_mode = rmode;
 309
 310         if (real_mode->hdr.loadflags & QUIET_FLAG)
 311                 quiet = 1;
 312
 313         if (real_mode->screen_info.orig_video_mode == 7) {
 314                 vidmem = (char *) 0xb0000;
 315                 vidport = 0x3b4;
 316         } else {
 317                 vidmem = (char *) 0xb8000;
 318                 vidport = 0x3d4;
 319         }
 320
 321         lines = real_mode->screen_info.orig_video_lines;
 322         cols = real_mode->screen_info.orig_video_cols;
 323
 324         free_mem_ptr     = heap;        /* Heap */
 325         free_mem_end_ptr = heap + BOOT_HEAP_SIZE;
 326
 327         if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1))
 328                 error("Destination address inappropriately aligned");
 329 #ifdef CONFIG_X86_64
 330         if (heap > 0x3fffffffffffUL)
 331                 error("Destination address too large");
 332 #else
 333         if (heap > ((-__PAGE_OFFSET-(512<<20)-1) & 0x7fffffff))
 334                 error("Destination address too large");
 335 #endif
 336 #ifndef CONFIG_RELOCATABLE
 337         if ((unsigned long)output != LOAD_PHYSICAL_ADDR)
 338                 error("Wrong destination address");
 339 #endif
 340
 341         if (!quiet)
 342                 putstr("\nDecompressing Linux... ");
 343         decompress(input_data, input_len, NULL, NULL, output, NULL, error);
 344         parse_elf(output);
 345         if (!quiet)
 346                 putstr("done.\nBooting the kernel.\n");
 347         return;
 348 }