diff options
Diffstat (limited to 'arch/x86/boot/compressed/misc.c')
-rw-r--r-- | arch/x86/boot/compressed/misc.c | 413 |
1 files changed, 413 insertions, 0 deletions
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c new file mode 100644 index 000000000000..8182e32c1b42 --- /dev/null +++ b/arch/x86/boot/compressed/misc.c | |||
@@ -0,0 +1,413 @@ | |||
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 | } | ||