]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
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 | ||
d3561b7f | 12 | #undef CONFIG_PARAVIRT |
1da177e4 LT |
13 | #include <linux/linkage.h> |
14 | #include <linux/vmalloc.h> | |
7e7f358c | 15 | #include <linux/screen_info.h> |
1da177e4 | 16 | #include <asm/io.h> |
968de4f0 | 17 | #include <asm/page.h> |
e69f202d | 18 | #include <asm/boot.h> |
968de4f0 EB |
19 | |
20 | /* WARNING!! | |
21 | * This code is compiled with -fPIC and it is relocated dynamically | |
22 | * at run time, but no relocation processing is performed. | |
23 | * This means that it is not safe to place pointers in static structures. | |
24 | */ | |
25 | ||
26 | /* | |
27 | * Getting to provable safe in place decompression is hard. | |
28 | * Worst case behaviours need to be analized. | |
29 | * Background information: | |
30 | * | |
31 | * The file layout is: | |
32 | * magic[2] | |
33 | * method[1] | |
34 | * flags[1] | |
35 | * timestamp[4] | |
36 | * extraflags[1] | |
37 | * os[1] | |
38 | * compressed data blocks[N] | |
39 | * crc[4] orig_len[4] | |
40 | * | |
41 | * resulting in 18 bytes of non compressed data overhead. | |
42 | * | |
43 | * Files divided into blocks | |
44 | * 1 bit (last block flag) | |
45 | * 2 bits (block type) | |
46 | * | |
47 | * 1 block occurs every 32K -1 bytes or when there 50% compression has been achieved. | |
48 | * The smallest block type encoding is always used. | |
49 | * | |
50 | * stored: | |
51 | * 32 bits length in bytes. | |
52 | * | |
53 | * fixed: | |
54 | * magic fixed tree. | |
55 | * symbols. | |
56 | * | |
57 | * dynamic: | |
58 | * dynamic tree encoding. | |
59 | * symbols. | |
60 | * | |
61 | * | |
62 | * The buffer for decompression in place is the length of the | |
63 | * uncompressed data, plus a small amount extra to keep the algorithm safe. | |
64 | * The compressed data is placed at the end of the buffer. The output | |
65 | * pointer is placed at the start of the buffer and the input pointer | |
66 | * is placed where the compressed data starts. Problems will occur | |
67 | * when the output pointer overruns the input pointer. | |
68 | * | |
69 | * The output pointer can only overrun the input pointer if the input | |
70 | * pointer is moving faster than the output pointer. A condition only | |
71 | * triggered by data whose compressed form is larger than the uncompressed | |
72 | * form. | |
73 | * | |
74 | * The worst case at the block level is a growth of the compressed data | |
75 | * of 5 bytes per 32767 bytes. | |
76 | * | |
77 | * The worst case internal to a compressed block is very hard to figure. | |
78 | * The worst case can at least be boundined by having one bit that represents | |
79 | * 32764 bytes and then all of the rest of the bytes representing the very | |
80 | * very last byte. | |
81 | * | |
82 | * All of which is enough to compute an amount of extra data that is required | |
83 | * to be safe. To avoid problems at the block level allocating 5 extra bytes | |
84 | * per 32767 bytes of data is sufficient. To avoind problems internal to a block | |
85 | * adding an extra 32767 bytes (the worst case uncompressed block size) is | |
86 | * sufficient, to ensure that in the worst case the decompressed data for | |
87 | * block will stop the byte before the compressed data for a block begins. | |
88 | * To avoid problems with the compressed data's meta information an extra 18 | |
89 | * bytes are needed. Leading to the formula: | |
90 | * | |
91 | * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size. | |
92 | * | |
93 | * Adding 8 bytes per 32K is a bit excessive but much easier to calculate. | |
94 | * Adding 32768 instead of 32767 just makes for round numbers. | |
95 | * Adding the decompressor_size is necessary as it musht live after all | |
96 | * of the data as well. Last I measured the decompressor is about 14K. | |
97 | * 10K of actuall data and 4K of bss. | |
98 | * | |
99 | */ | |
1da177e4 LT |
100 | |
101 | /* | |
102 | * gzip declarations | |
103 | */ | |
104 | ||
105 | #define OF(args) args | |
106 | #define STATIC static | |
107 | ||
108 | #undef memset | |
109 | #undef memcpy | |
1da177e4 LT |
110 | #define memzero(s, n) memset ((s), 0, (n)) |
111 | ||
112 | typedef unsigned char uch; | |
113 | typedef unsigned short ush; | |
114 | typedef unsigned long ulg; | |
115 | ||
968de4f0 EB |
116 | #define WSIZE 0x80000000 /* Window size must be at least 32k, |
117 | * and a power of two | |
118 | * We don't actually have a window just | |
119 | * a huge output buffer so I report | |
120 | * a 2G windows size, as that should | |
121 | * always be larger than our output buffer. | |
122 | */ | |
1da177e4 | 123 | |
968de4f0 EB |
124 | static uch *inbuf; /* input buffer */ |
125 | static uch *window; /* Sliding window buffer, (and final output buffer) */ | |
1da177e4 | 126 | |
968de4f0 EB |
127 | static unsigned insize; /* valid bytes in inbuf */ |
128 | static unsigned inptr; /* index of next byte to be processed in inbuf */ | |
129 | static unsigned outcnt; /* bytes in output buffer */ | |
1da177e4 LT |
130 | |
131 | /* gzip flag byte */ | |
132 | #define ASCII_FLAG 0x01 /* bit 0 set: file probably ASCII text */ | |
133 | #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */ | |
134 | #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */ | |
135 | #define ORIG_NAME 0x08 /* bit 3 set: original file name present */ | |
136 | #define COMMENT 0x10 /* bit 4 set: file comment present */ | |
137 | #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */ | |
138 | #define RESERVED 0xC0 /* bit 6,7: reserved */ | |
139 | ||
140 | #define get_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf()) | |
141 | ||
142 | /* Diagnostic functions */ | |
143 | #ifdef DEBUG | |
144 | # define Assert(cond,msg) {if(!(cond)) error(msg);} | |
145 | # define Trace(x) fprintf x | |
146 | # define Tracev(x) {if (verbose) fprintf x ;} | |
147 | # define Tracevv(x) {if (verbose>1) fprintf x ;} | |
148 | # define Tracec(c,x) {if (verbose && (c)) fprintf x ;} | |
149 | # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} | |
150 | #else | |
151 | # define Assert(cond,msg) | |
152 | # define Trace(x) | |
153 | # define Tracev(x) | |
154 | # define Tracevv(x) | |
155 | # define Tracec(c,x) | |
156 | # define Tracecv(c,x) | |
157 | #endif | |
158 | ||
159 | static int fill_inbuf(void); | |
160 | static void flush_window(void); | |
161 | static void error(char *m); | |
162 | static void gzip_mark(void **); | |
163 | static void gzip_release(void **); | |
164 | ||
165 | /* | |
166 | * This is set up by the setup-routine at boot-time | |
167 | */ | |
168 | static unsigned char *real_mode; /* Pointer to real-mode data */ | |
169 | ||
170 | #define RM_EXT_MEM_K (*(unsigned short *)(real_mode + 0x2)) | |
171 | #ifndef STANDARD_MEMORY_BIOS_CALL | |
172 | #define RM_ALT_MEM_K (*(unsigned long *)(real_mode + 0x1e0)) | |
173 | #endif | |
174 | #define RM_SCREEN_INFO (*(struct screen_info *)(real_mode+0)) | |
175 | ||
b79c4df7 | 176 | extern unsigned char input_data[]; |
1da177e4 LT |
177 | extern int input_len; |
178 | ||
179 | static long bytes_out = 0; | |
1da177e4 LT |
180 | |
181 | static void *malloc(int size); | |
182 | static void free(void *where); | |
183 | ||
b79c4df7 CDH |
184 | static void *memset(void *s, int c, unsigned n); |
185 | static void *memcpy(void *dest, const void *src, unsigned n); | |
186 | ||
1da177e4 LT |
187 | static void putstr(const char *); |
188 | ||
968de4f0 EB |
189 | static unsigned long free_mem_ptr; |
190 | static unsigned long free_mem_end_ptr; | |
1da177e4 | 191 | |
35c74226 | 192 | #define HEAP_SIZE 0x4000 |
1da177e4 LT |
193 | |
194 | static char *vidmem = (char *)0xb8000; | |
195 | static int vidport; | |
196 | static int lines, cols; | |
197 | ||
198 | #ifdef CONFIG_X86_NUMAQ | |
d5d2448d | 199 | void *xquad_portio; |
1da177e4 LT |
200 | #endif |
201 | ||
202 | #include "../../../../lib/inflate.c" | |
203 | ||
204 | static void *malloc(int size) | |
205 | { | |
206 | void *p; | |
207 | ||
208 | if (size <0) error("Malloc error"); | |
209 | if (free_mem_ptr <= 0) error("Memory error"); | |
210 | ||
211 | free_mem_ptr = (free_mem_ptr + 3) & ~3; /* Align */ | |
212 | ||
213 | p = (void *)free_mem_ptr; | |
214 | free_mem_ptr += size; | |
215 | ||
216 | if (free_mem_ptr >= free_mem_end_ptr) | |
217 | error("Out of memory"); | |
218 | ||
219 | return p; | |
220 | } | |
221 | ||
222 | static void free(void *where) | |
223 | { /* Don't care */ | |
224 | } | |
225 | ||
226 | static void gzip_mark(void **ptr) | |
227 | { | |
228 | *ptr = (void *) free_mem_ptr; | |
229 | } | |
230 | ||
231 | static void gzip_release(void **ptr) | |
232 | { | |
968de4f0 | 233 | free_mem_ptr = (unsigned long) *ptr; |
1da177e4 LT |
234 | } |
235 | ||
236 | static void scroll(void) | |
237 | { | |
238 | int i; | |
239 | ||
240 | memcpy ( vidmem, vidmem + cols * 2, ( lines - 1 ) * cols * 2 ); | |
241 | for ( i = ( lines - 1 ) * cols * 2; i < lines * cols * 2; i += 2 ) | |
242 | vidmem[i] = ' '; | |
243 | } | |
244 | ||
245 | static void putstr(const char *s) | |
246 | { | |
247 | int x,y,pos; | |
248 | char c; | |
249 | ||
250 | x = RM_SCREEN_INFO.orig_x; | |
251 | y = RM_SCREEN_INFO.orig_y; | |
252 | ||
253 | while ( ( c = *s++ ) != '\0' ) { | |
254 | if ( c == '\n' ) { | |
255 | x = 0; | |
256 | if ( ++y >= lines ) { | |
257 | scroll(); | |
258 | y--; | |
259 | } | |
260 | } else { | |
968de4f0 | 261 | vidmem [ ( x + cols * y ) * 2 ] = c; |
1da177e4 LT |
262 | if ( ++x >= cols ) { |
263 | x = 0; | |
264 | if ( ++y >= lines ) { | |
265 | scroll(); | |
266 | y--; | |
267 | } | |
268 | } | |
269 | } | |
270 | } | |
271 | ||
272 | RM_SCREEN_INFO.orig_x = x; | |
273 | RM_SCREEN_INFO.orig_y = y; | |
274 | ||
275 | pos = (x + cols * y) * 2; /* Update cursor position */ | |
276 | outb_p(14, vidport); | |
277 | outb_p(0xff & (pos >> 9), vidport+1); | |
278 | outb_p(15, vidport); | |
279 | outb_p(0xff & (pos >> 1), vidport+1); | |
280 | } | |
281 | ||
b79c4df7 | 282 | static void* memset(void* s, int c, unsigned n) |
1da177e4 LT |
283 | { |
284 | int i; | |
285 | char *ss = (char*)s; | |
286 | ||
287 | for (i=0;i<n;i++) ss[i] = c; | |
288 | return s; | |
289 | } | |
290 | ||
b79c4df7 | 291 | static void* memcpy(void* dest, const void* src, unsigned n) |
1da177e4 LT |
292 | { |
293 | int i; | |
b79c4df7 | 294 | char *d = (char *)dest, *s = (char *)src; |
1da177e4 | 295 | |
b79c4df7 CDH |
296 | for (i=0;i<n;i++) d[i] = s[i]; |
297 | return dest; | |
1da177e4 LT |
298 | } |
299 | ||
300 | /* =========================================================================== | |
301 | * Fill the input buffer. This is called only when the buffer is empty | |
302 | * and at least one byte is really needed. | |
303 | */ | |
304 | static int fill_inbuf(void) | |
305 | { | |
968de4f0 EB |
306 | error("ran out of input data"); |
307 | return 0; | |
1da177e4 LT |
308 | } |
309 | ||
310 | /* =========================================================================== | |
311 | * Write the output window window[0..outcnt-1] and update crc and bytes_out. | |
312 | * (Used for the decompressed data only.) | |
313 | */ | |
1da177e4 LT |
314 | static void flush_window(void) |
315 | { | |
968de4f0 EB |
316 | /* With my window equal to my output buffer |
317 | * I only need to compute the crc here. | |
318 | */ | |
319 | ulg c = crc; /* temporary variable */ | |
320 | unsigned n; | |
321 | uch *in, ch; | |
322 | ||
323 | in = window; | |
324 | for (n = 0; n < outcnt; n++) { | |
325 | ch = *in++; | |
326 | c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8); | |
327 | } | |
328 | crc = c; | |
329 | bytes_out += (ulg)outcnt; | |
330 | outcnt = 0; | |
1da177e4 LT |
331 | } |
332 | ||
333 | static void error(char *x) | |
334 | { | |
335 | putstr("\n\n"); | |
336 | putstr(x); | |
337 | putstr("\n\n -- System halted"); | |
338 | ||
339 | while(1); /* Halt */ | |
340 | } | |
341 | ||
968de4f0 EB |
342 | asmlinkage void decompress_kernel(void *rmode, unsigned long end, |
343 | uch *input_data, unsigned long input_len, uch *output) | |
1da177e4 LT |
344 | { |
345 | real_mode = rmode; | |
346 | ||
347 | if (RM_SCREEN_INFO.orig_video_mode == 7) { | |
348 | vidmem = (char *) 0xb0000; | |
349 | vidport = 0x3b4; | |
350 | } else { | |
351 | vidmem = (char *) 0xb8000; | |
352 | vidport = 0x3d4; | |
353 | } | |
354 | ||
355 | lines = RM_SCREEN_INFO.orig_video_lines; | |
356 | cols = RM_SCREEN_INFO.orig_video_cols; | |
357 | ||
968de4f0 EB |
358 | window = output; /* Output buffer (Normally at 1M) */ |
359 | free_mem_ptr = end; /* Heap */ | |
360 | free_mem_end_ptr = end + HEAP_SIZE; | |
361 | inbuf = input_data; /* Input buffer */ | |
362 | insize = input_len; | |
363 | inptr = 0; | |
364 | ||
e69f202d VG |
365 | if ((u32)output & (CONFIG_PHYSICAL_ALIGN -1)) |
366 | error("Destination address not CONFIG_PHYSICAL_ALIGN aligned"); | |
968de4f0 EB |
367 | if (end > ((-__PAGE_OFFSET-(512 <<20)-1) & 0x7fffffff)) |
368 | error("Destination address too large"); | |
369 | #ifndef CONFIG_RELOCATABLE | |
e69f202d | 370 | if ((u32)output != LOAD_PHYSICAL_ADDR) |
968de4f0 EB |
371 | error("Wrong destination address"); |
372 | #endif | |
1da177e4 LT |
373 | |
374 | makecrc(); | |
375 | putstr("Uncompressing Linux... "); | |
376 | gunzip(); | |
377 | putstr("Ok, booting the kernel.\n"); | |
968de4f0 | 378 | return; |
1da177e4 | 379 | } |