Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * Hypervisor Software File: decomp.c | |
5 | * | |
6 | * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
7 | * | |
8 | * - Do no alter or remove copyright notices | |
9 | * | |
10 | * - Redistribution and use of this software in source and binary forms, with | |
11 | * or without modification, are permitted provided that the following | |
12 | * conditions are met: | |
13 | * | |
14 | * - Redistribution of source code must retain the above copyright notice, | |
15 | * this list of conditions and the following disclaimer. | |
16 | * | |
17 | * - Redistribution in binary form must reproduce the above copyright notice, | |
18 | * this list of conditions and the following disclaimer in the | |
19 | * documentation and/or other materials provided with the distribution. | |
20 | * | |
21 | * Neither the name of Sun Microsystems, Inc. or the names of contributors | |
22 | * may be used to endorse or promote products derived from this software | |
23 | * without specific prior written permission. | |
24 | * | |
25 | * This software is provided "AS IS," without a warranty of any kind. | |
26 | * ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, | |
27 | * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A | |
28 | * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN | |
29 | * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR | |
30 | * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR | |
31 | * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN | |
32 | * OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR | |
33 | * FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE | |
34 | * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, | |
35 | * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF | |
36 | * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. | |
37 | * | |
38 | * You acknowledge that this software is not designed, licensed or | |
39 | * intended for use in the design, construction, operation or maintenance of | |
40 | * any nuclear facility. | |
41 | * | |
42 | * ========== Copyright Header End ============================================ | |
43 | */ | |
44 | #ifndef STANDALONE | |
45 | #include <stdio.h> | |
46 | #endif /* STANDALONE */ | |
47 | ||
48 | /* | |
49 | * @(#)decomp.c 1.6 03/04/01 | |
50 | * Copyright 2000, 2003 Sun Microsystems, Inc. All Rights Reserved | |
51 | * Use is subject to license terms. | |
52 | * New simplified getcode() routine, adaptive block compress. | |
53 | */ | |
54 | ||
55 | /* marker for needed scope management of symbols in this file */ | |
56 | #define PRIVATE | |
57 | ||
58 | typedef unsigned char uchar_t; | |
59 | ||
60 | #define HSIZE 18013 /* 91% occupancy */ | |
61 | #define BITS 14 | |
62 | #define INIT_BITS 9 /* initial number of bits/code */ | |
63 | ||
64 | /* | |
65 | * Character output. | |
66 | */ | |
67 | PRIVATE unsigned char *output; | |
68 | PRIVATE unsigned char *input; | |
69 | PRIVATE int data_count; | |
70 | ||
71 | #ifdef STANDALONE | |
72 | #define putbyte(c) *output++ = (c) | |
73 | #else | |
74 | #define putbyte(c) putchar((c)) | |
75 | #endif /* STANDALONE */ | |
76 | PRIVATE int getbyte(); | |
77 | ||
78 | #define init_output(op) output = (op) | |
79 | ||
80 | #define init_input(ip, size) input = (ip), data_count = (size) | |
81 | /* | |
82 | * Start of Uninitialized globals | |
83 | */ | |
84 | typedef short code_int; | |
85 | typedef unsigned char char_type; | |
86 | typedef int count_int; | |
87 | ||
88 | PRIVATE char_type tab_suffix[HSIZE]; | |
89 | PRIVATE unsigned short tab_prefix[HSIZE]; | |
90 | PRIVATE char_type de_stack[8000]; | |
91 | ||
92 | /* | |
93 | * End of uninitialized globals | |
94 | */ | |
95 | ||
96 | PRIVATE code_int getcode(); | |
97 | ||
98 | #define maxmaxcode ((code_int)1 << BITS) /* should NEVER generate this code */ | |
99 | #define MAXCODE(n_bits) ((1 << (n_bits)) - 1) | |
100 | ||
101 | /* | |
102 | * block compression parameters -- after all codes are used up, | |
103 | * and compression rate changes, start over. | |
104 | * These codes should not be changed lightly, as they must not | |
105 | * lie within the contiguous general code space. | |
106 | * The END marker is used because some file transfer programs are | |
107 | * prone to adding garbage bytes to the end of the file. | |
108 | */ | |
109 | #define FIRST 258 /* first free entry */ | |
110 | #define END 257 /* End of file marker */ | |
111 | #define CLEAR 256 /* table clear output code */ | |
112 | ||
113 | static char_type magic_header[] = { "\037\236" }; /* 1F 9E */ | |
114 | ||
115 | /* | |
116 | * Don't initialize these explicitly because we want them in the | |
117 | * BSS segment for ROM/RAM systems. It would probably be a good | |
118 | * idea to initialize them to 0 at run time (when decompress() | |
119 | * begins). | |
120 | */ | |
121 | static int getcode_offset; | |
122 | static int getcode_oldcode; | |
123 | ||
124 | /* | |
125 | * Decompress stdin to stdout. This routine adapts to the codes in the | |
126 | * file building the "string" table on-the-fly; requiring no table to | |
127 | * be stored in the compressed file. The tables used herein are shared | |
128 | * with those of the compress() routine. See the definitions above. | |
129 | */ | |
130 | ||
131 | PRIVATE void | |
132 | decompress(ip, insize, op) | |
133 | unsigned char *ip; | |
134 | int insize; | |
135 | unsigned char *op; | |
136 | { | |
137 | register char_type *stackp; | |
138 | register int finchar; | |
139 | register code_int code, | |
140 | oldcode, | |
141 | incode; | |
142 | register int n_bits; /* number of bits/code */ | |
143 | code_int maxcode; /* max code, given n_bits */ | |
144 | code_int free_ent; /* first unused entry */ | |
145 | ||
146 | getcode_offset = 0; | |
147 | getcode_oldcode = 0; | |
148 | ||
149 | init_input(ip, insize); | |
150 | init_output(op); | |
151 | /* Check the magic number */ | |
152 | if ((getbyte() != (magic_header[0] & 0xFF)) || | |
153 | (getbyte() != (magic_header[1] & 0xFF))) { | |
154 | ||
155 | #if defined(DEBUG) && ! defined(STANDALONE) | |
156 | fprintf(stderr, "Bad MAGIC number\n"); | |
157 | exit(1); | |
158 | #endif /* DEBUG */ | |
159 | *(short *)1 = 1; | |
160 | } | |
161 | if (getbyte() != BITS) { | |
162 | #if defined(DEBUG) && ! defined(STANDALONE) | |
163 | fprintf(stderr, "Bad #bits\n"); | |
164 | #endif /* DEBUG */ | |
165 | *(short *)1 = 2; | |
166 | } | |
167 | /* | |
168 | * As above, initialize the first 256 entries in the table. | |
169 | */ | |
170 | maxcode = MAXCODE(n_bits = INIT_BITS); | |
171 | ||
172 | for (code = 255; code >= 0; code--) { | |
173 | tab_prefix[code] = 0; | |
174 | tab_suffix[code] = (char_type)code; | |
175 | } | |
176 | ||
177 | free_ent = FIRST; | |
178 | ||
179 | finchar = oldcode = getcode(n_bits); | |
180 | if (oldcode == -1 || oldcode == END) /* EOF already? */ | |
181 | *(short *)1 = 3; | |
182 | putbyte((char)finchar); /* first code must be 8 bits = char */ | |
183 | stackp = de_stack; | |
184 | ||
185 | while ((code = getcode(n_bits)) > (code_int)-1 && code != END) { | |
186 | ||
187 | if (code == CLEAR) { | |
188 | for (code = 255; code >= 0; code--) | |
189 | tab_prefix[code] = 0; | |
190 | maxcode = MAXCODE(n_bits = INIT_BITS); | |
191 | free_ent = FIRST - 1; | |
192 | if ((code = getcode(n_bits)) == -1) /* EOF */ | |
193 | break; | |
194 | } | |
195 | incode = code; | |
196 | ||
197 | /* | |
198 | * Special case for KwKwK string. | |
199 | */ | |
200 | if (code >= free_ent) { | |
201 | *stackp++ = finchar; | |
202 | code = oldcode; | |
203 | } | |
204 | ||
205 | /* | |
206 | * Generate output characters in reverse order | |
207 | */ | |
208 | while (code >= 256) { | |
209 | *stackp++ = tab_suffix[code]; | |
210 | code = tab_prefix[code]; | |
211 | } | |
212 | *stackp++ = finchar = tab_suffix[code]; | |
213 | ||
214 | /* | |
215 | * And put them out in forward order | |
216 | */ | |
217 | do | |
218 | putbyte(*--stackp); | |
219 | while (stackp > de_stack); | |
220 | ||
221 | /* | |
222 | * Generate the new entry. | |
223 | */ | |
224 | if ((code = free_ent) < (code_int)maxmaxcode) { | |
225 | tab_prefix[code] = (unsigned short)oldcode; | |
226 | tab_suffix[code] = finchar; | |
227 | free_ent = code+1; | |
228 | } | |
229 | ||
230 | /* | |
231 | * Remember previous code. | |
232 | */ | |
233 | oldcode = incode; | |
234 | ||
235 | /* | |
236 | * If the next entry will be too big for the current code | |
237 | * size, then we must increase the size. | |
238 | */ | |
239 | if (free_ent > maxcode) { | |
240 | n_bits++; | |
241 | if (n_bits == BITS) | |
242 | /* won't get any bigger now */ | |
243 | maxcode = maxmaxcode; | |
244 | else | |
245 | maxcode = MAXCODE(n_bits); | |
246 | } | |
247 | } | |
248 | } | |
249 | ||
250 | /* | |
251 | * getcode | |
252 | * Read one code from the standard input. If EOF, return -1. | |
253 | */ | |
254 | ||
255 | PRIVATE code_int rmask[] = { | |
256 | 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, | |
257 | 0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, | |
258 | 0x3fff, 0x7fff, (code_int)0xffff | |
259 | }; | |
260 | ||
261 | PRIVATE code_int | |
262 | getcode(bits) | |
263 | register int bits; | |
264 | { | |
265 | register int r_off = getcode_offset; | |
266 | register int code = getcode_oldcode; | |
267 | register int c; | |
268 | ||
269 | do { | |
270 | if ((c = getbyte()) == -1) | |
271 | return (-1); | |
272 | code += c << r_off; | |
273 | r_off += 8; | |
274 | } while (r_off < bits); | |
275 | ||
276 | getcode_oldcode = code >> bits; | |
277 | getcode_offset = r_off - bits; | |
278 | #if defined(DEBUG) && ! defined(STANDALONE) | |
279 | fprintf(stderr, "[%x]\n", code & rmask[bits]); | |
280 | #endif /* DEBUG */ | |
281 | return (code & rmask[bits]); | |
282 | } | |
283 | ||
284 | PRIVATE int | |
285 | getbyte() | |
286 | { | |
287 | #ifndef STANDALONE | |
288 | int c; | |
289 | c = getchar(); | |
290 | #ifdef DEBUG | |
291 | fprintf(stderr, "%2x ", c); | |
292 | #endif /* DEBUG */ | |
293 | if (c == EOF) c = -1; | |
294 | return (c); | |
295 | #else | |
296 | if (--data_count < 0) | |
297 | return (-1); | |
298 | return ((int)*input++); | |
299 | #endif /* STANDALONE */ | |
300 | } | |
301 | ||
302 | #ifndef STANDALONE | |
303 | main(void) | |
304 | { | |
305 | decompress(0, 0, 0); | |
306 | return (0); | |
307 | } | |
308 | #endif /* STANDALONE */ | |
309 | ||
310 | #ifdef DROPIN_LIB | |
311 | int | |
312 | decomp(uchar_t *src, int size, uchar_t *dest) | |
313 | { | |
314 | decompress(src, size, dest); | |
315 | return (output - dest); | |
316 | } | |
317 | #endif /* DROPIN_LIB */ |