diff options
Diffstat (limited to 'apps/plugins/rockboy/inflate.c')
-rw-r--r-- | apps/plugins/rockboy/inflate.c | 514 |
1 files changed, 514 insertions, 0 deletions
diff --git a/apps/plugins/rockboy/inflate.c b/apps/plugins/rockboy/inflate.c new file mode 100644 index 0000000000..6818749187 --- /dev/null +++ b/apps/plugins/rockboy/inflate.c | |||
@@ -0,0 +1,514 @@ | |||
1 | |||
2 | /* Slightly modified from its original form so as not to exit the | ||
3 | * program on errors. The resulting file remains in the public | ||
4 | * domain for all to use. */ | ||
5 | |||
6 | /* --- GZIP file format uncompression routines --- */ | ||
7 | |||
8 | /* The following routines (notably the unzip()) function below | ||
9 | * uncompress gzipped data. They are terribly slow at the task, but | ||
10 | * it is presumed that they work reasonably well. They don't do any | ||
11 | * error checking, but they're probably not too vulnerable to buggy | ||
12 | * data either. Another important limitation (but it would be pretty | ||
13 | * easy to get around) is that the data must reside in memory, it is | ||
14 | * not read as a stream. They have been very little tested. Anyway, | ||
15 | * whatever these functions are good for, I put them in the public | ||
16 | * domain. -- David Madore <david.madore@ens.fr> 1999/11/21 */ | ||
17 | |||
18 | #include "rockmacros.h" | ||
19 | |||
20 | static unsigned int | ||
21 | peek_bits (const unsigned char *data, long p, int q) | ||
22 | /* Read q bits starting from bit p from the data pointed to by | ||
23 | * data. Data is in little-endian format. */ | ||
24 | { | ||
25 | unsigned int answer; | ||
26 | int cnt; /* Number of bits already placed in answer */ | ||
27 | char ob, lb; /* Offset and length of bit field within current byte */ | ||
28 | |||
29 | answer = 0; | ||
30 | for ( cnt=0 ; cnt<q ; /* cnt updated in body */ ) | ||
31 | { | ||
32 | ob = (p+cnt)%8; | ||
33 | lb = 8-ob; | ||
34 | if ( cnt+lb > q ) | ||
35 | lb = q-cnt; | ||
36 | answer |= ((unsigned int)((data[(p+cnt)/8]>>ob)&((1U<<lb)-1)))<<cnt; | ||
37 | cnt += lb; | ||
38 | } | ||
39 | return answer; | ||
40 | } | ||
41 | |||
42 | static unsigned int | ||
43 | read_bits (const unsigned char *data, long *p, int q) | ||
44 | /* Read q bits as per peek_bits(), but also increase p by q. */ | ||
45 | { | ||
46 | unsigned int answer; | ||
47 | |||
48 | answer = peek_bits (data, *p, q); | ||
49 | *p += q; | ||
50 | return answer; | ||
51 | } | ||
52 | |||
53 | static void | ||
54 | make_code_table (const char size_table[], int table_length, | ||
55 | unsigned int code_table[], int maxbits) | ||
56 | /* Make a code table from a length table. See rfc1951, section | ||
57 | * 3.2.2, for details on what this means. The size_table | ||
58 | * contains the length of the Huffman codes for each letter, and | ||
59 | * the code_table receives the computed codes themselves. | ||
60 | * table_length is the size of the tables (alphabet length) and | ||
61 | * maxbits is the maximal allowed code length. */ | ||
62 | { | ||
63 | int i, j; | ||
64 | unsigned int code; | ||
65 | |||
66 | code = 0; | ||
67 | for ( i=1 ; i<=maxbits ; i++ ) | ||
68 | { | ||
69 | for ( j=0 ; j<table_length ; j++ ) | ||
70 | { | ||
71 | if ( size_table[j]==i ) | ||
72 | code_table[j] = code++; | ||
73 | } | ||
74 | code <<= 1; | ||
75 | } | ||
76 | } | ||
77 | |||
78 | static int | ||
79 | decode_one (const unsigned char *data, long *p, | ||
80 | const char size_table[], int table_length, | ||
81 | const unsigned int code_table[], int maxbits) | ||
82 | /* Decode one alphabet letter from the data, starting at bit p | ||
83 | * (which will be increased by the appropriate amount) using | ||
84 | * size_table and code_table to decipher the Huffman encoding. */ | ||
85 | { | ||
86 | unsigned int code; | ||
87 | int i, j; | ||
88 | |||
89 | code = 0; | ||
90 | /* Read as many bits as are likely to be necessary - backward, of | ||
91 | * course. */ | ||
92 | for ( i=0 ; i<maxbits ; i++ ) | ||
93 | code = (code<<1) + peek_bits (data, (*p)+i, 1); | ||
94 | /* Now examine each symbol of the table to find one that matches the | ||
95 | * first bits of the code read. */ | ||
96 | for ( j=0 ; j<table_length ; j++ ) | ||
97 | { | ||
98 | if ( size_table[j] | ||
99 | && ( (code>>(maxbits-size_table[j])) == code_table[j] ) ) | ||
100 | { | ||
101 | *p += size_table[j]; | ||
102 | return j; | ||
103 | } | ||
104 | } | ||
105 | return -1; | ||
106 | } | ||
107 | |||
108 | /* I don't know what these should be. The rfc1951 doesn't seem to say | ||
109 | * (it only mentions them in the last paragraph of section 3.2.1). 15 | ||
110 | * is almost certainly safe, and it is the largest I can put given the | ||
111 | * constraints on the size of integers in the C standard. */ | ||
112 | #define CLEN_MAXBITS 15 | ||
113 | #define HLIT_MAXBITS 15 | ||
114 | #define HDIST_MAXBITS 15 | ||
115 | |||
116 | /* The magical table sizes... */ | ||
117 | #define CLEN_TSIZE 19 | ||
118 | #define HLIT_TSIZE 288 | ||
119 | #define HDIST_TSIZE 30 | ||
120 | |||
121 | static int | ||
122 | get_tables (const unsigned char *data, long *p, | ||
123 | char hlit_size_table[HLIT_TSIZE], | ||
124 | unsigned int hlit_code_table[HLIT_TSIZE], | ||
125 | char hdist_size_table[HDIST_TSIZE], | ||
126 | unsigned int hdist_code_table[HDIST_TSIZE]) | ||
127 | /* Fill the Huffman tables (first the code lengths table, and | ||
128 | * then, using it, the literal/length table and the distance | ||
129 | * table). See section 3.2.7 of rfc1951 for details. */ | ||
130 | { | ||
131 | char hlit, hdist, hclen; | ||
132 | const int clen_weird_tangle[CLEN_TSIZE] | ||
133 | = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; | ||
134 | char clen_size_table[CLEN_TSIZE]; | ||
135 | unsigned int clen_code_table[CLEN_TSIZE]; | ||
136 | int j; | ||
137 | unsigned int b; | ||
138 | int remainder; /* See note at end of section 3.2.7 of rfc1951. */ | ||
139 | char rem_val; | ||
140 | |||
141 | hlit = read_bits (data, p, 5); | ||
142 | hdist = read_bits (data, p, 5); | ||
143 | hclen = read_bits (data, p, 4); | ||
144 | for ( j=0 ; j<4+hclen ; j++ ) | ||
145 | clen_size_table[clen_weird_tangle[j]] | ||
146 | = read_bits (data, p, 3); | ||
147 | for ( ; j<CLEN_TSIZE ; j++ ) | ||
148 | clen_size_table[clen_weird_tangle[j]] = 0; | ||
149 | make_code_table (clen_size_table, CLEN_TSIZE, | ||
150 | clen_code_table, CLEN_MAXBITS); | ||
151 | remainder = 0; | ||
152 | rem_val = 0; | ||
153 | for ( j=0 ; j<257+hlit ; j++ ) | ||
154 | { | ||
155 | b = decode_one (data, p, clen_size_table, CLEN_TSIZE, | ||
156 | clen_code_table, CLEN_MAXBITS); | ||
157 | if ( b<0 ) return -1; | ||
158 | if ( b<16 ) | ||
159 | hlit_size_table[j] = b; | ||
160 | else if ( b == 16 ) | ||
161 | { | ||
162 | int k, l; | ||
163 | |||
164 | k = read_bits (data, p, 2); | ||
165 | for ( l=0 ; l<k+3 && j+l<257+hlit ; l++ ) | ||
166 | hlit_size_table[j+l] = hlit_size_table[j-1]; | ||
167 | j += l-1; | ||
168 | remainder = k+3-l; /* THIS IS SO UGLY! */ | ||
169 | rem_val = hlit_size_table[j-1]; | ||
170 | } | ||
171 | else if ( b == 17 ) | ||
172 | { | ||
173 | int k, l; | ||
174 | |||
175 | k = read_bits (data, p, 3); | ||
176 | for ( l=0 ; l<k+3 && j+l<257+hlit ; l++ ) | ||
177 | hlit_size_table[j+l] = 0; | ||
178 | j += l-1; | ||
179 | remainder = k+3-l; | ||
180 | rem_val = 0; | ||
181 | } | ||
182 | else if ( b == 18 ) | ||
183 | { | ||
184 | int k, l; | ||
185 | |||
186 | k = read_bits (data, p, 7); | ||
187 | for ( l=0 ; l<k+11 && j+l<257+hlit ; l++ ) | ||
188 | hlit_size_table[j+l] = 0; | ||
189 | j += l-1; | ||
190 | remainder = k+11-l; | ||
191 | rem_val = 0; | ||
192 | } | ||
193 | } | ||
194 | for ( ; j<HLIT_TSIZE ; j++ ) | ||
195 | hlit_size_table[j] = 0; | ||
196 | make_code_table (hlit_size_table, HLIT_TSIZE, | ||
197 | hlit_code_table, HLIT_MAXBITS); | ||
198 | for ( j=0 ; j<remainder ; j++ ) | ||
199 | hdist_size_table[j] = rem_val; | ||
200 | for ( ; j<1+hdist ; j++ ) | ||
201 | /* Can you spell: ``copy-paste''? */ | ||
202 | { | ||
203 | b = decode_one (data, p, clen_size_table, CLEN_TSIZE, | ||
204 | clen_code_table, CLEN_MAXBITS); | ||
205 | if ( b<0 ) return -1; | ||
206 | if ( b<16 ) | ||
207 | hdist_size_table[j] = b; | ||
208 | else if ( b == 16 ) | ||
209 | { | ||
210 | int k, l; | ||
211 | |||
212 | k = read_bits (data, p, 2); | ||
213 | for ( l=0 ; l<k+3 && j+l<1+hdist ; l++ ) | ||
214 | hdist_size_table[j+l] = hdist_size_table[j-1]; | ||
215 | j += l-1; | ||
216 | } | ||
217 | else if ( b == 17 ) | ||
218 | { | ||
219 | int k, l; | ||
220 | |||
221 | k = read_bits (data, p, 3); | ||
222 | for ( l=0 ; l<k+3 && j+l<1+hdist ; l++ ) | ||
223 | hdist_size_table[j+l] = 0; | ||
224 | j += l-1; | ||
225 | } | ||
226 | else if ( b == 18 ) | ||
227 | { | ||
228 | int k, l; | ||
229 | |||
230 | k = read_bits (data, p, 7); | ||
231 | for ( l=0 ; l<k+11 && j+l<1+hdist ; l++ ) | ||
232 | hdist_size_table[j+l] = 0; | ||
233 | j += l-1; | ||
234 | } | ||
235 | } | ||
236 | for ( ; j<HDIST_TSIZE ; j++ ) | ||
237 | hdist_size_table[j] = 0; | ||
238 | make_code_table (hdist_size_table, HDIST_TSIZE, | ||
239 | hdist_code_table, HDIST_MAXBITS); | ||
240 | return 0; | ||
241 | } | ||
242 | |||
243 | /* The (circular) output buffer. This lets us track | ||
244 | * backreferences. */ | ||
245 | |||
246 | /* Minimal buffer size. Also the only useful value. */ | ||
247 | #define BUFFER_SIZE 32768 | ||
248 | |||
249 | /* Pointer to the character to be added to the buffer */ | ||
250 | static unsigned int buffer_ptr = 0; | ||
251 | |||
252 | /* The buffer itself */ | ||
253 | static unsigned char buffer[BUFFER_SIZE]; | ||
254 | |||
255 | static void | ||
256 | pushout (unsigned char ch) | ||
257 | /* Store one byte in the output buffer so it may be retrieved if | ||
258 | * it is referenced again. */ | ||
259 | { | ||
260 | buffer[buffer_ptr++] = ch; | ||
261 | buffer_ptr %= BUFFER_SIZE; | ||
262 | } | ||
263 | |||
264 | static unsigned char | ||
265 | pushin (unsigned int dist) | ||
266 | /* Retrieve one byte, dist bytes away, from the output buffer. */ | ||
267 | { | ||
268 | return buffer[(buffer_ptr+(BUFFER_SIZE-dist))%BUFFER_SIZE]; | ||
269 | } | ||
270 | |||
271 | static int | ||
272 | get_data (const unsigned char *data, long *p, | ||
273 | const char hlit_size_table[HLIT_TSIZE], | ||
274 | const unsigned int hlit_code_table[HLIT_TSIZE], | ||
275 | const char hdist_size_table[HDIST_TSIZE], | ||
276 | const unsigned int hdist_code_table[HDIST_TSIZE], | ||
277 | void (* callback) (unsigned char d)) | ||
278 | /* Do the actual uncompressing. Call callback on each character | ||
279 | * uncompressed. */ | ||
280 | { | ||
281 | unsigned int b; | ||
282 | |||
283 | while ( 1 ) { | ||
284 | b = decode_one (data, p, hlit_size_table, HLIT_TSIZE, | ||
285 | hlit_code_table, HLIT_MAXBITS); | ||
286 | if ( b<0 ) return -1; | ||
287 | if ( b < 256 ) | ||
288 | /* Literal */ | ||
289 | { | ||
290 | pushout ((unsigned char) b); | ||
291 | callback ((unsigned char) b); | ||
292 | } | ||
293 | else if ( b == 256 ) | ||
294 | /* End of block */ | ||
295 | return 0; | ||
296 | else if ( b >= 257 ) | ||
297 | /* Back reference */ | ||
298 | { | ||
299 | unsigned int bb; | ||
300 | unsigned int length, dist; | ||
301 | unsigned int l; | ||
302 | |||
303 | switch ( b ) | ||
304 | { | ||
305 | case 257: length = 3; break; | ||
306 | case 258: length = 4; break; | ||
307 | case 259: length = 5; break; | ||
308 | case 260: length = 6; break; | ||
309 | case 261: length = 7; break; | ||
310 | case 262: length = 8; break; | ||
311 | case 263: length = 9; break; | ||
312 | case 264: length = 10; break; | ||
313 | case 265: length = 11 + read_bits (data, p, 1); break; | ||
314 | case 266: length = 13 + read_bits (data, p, 1); break; | ||
315 | case 267: length = 15 + read_bits (data, p, 1); break; | ||
316 | case 268: length = 17 + read_bits (data, p, 1); break; | ||
317 | case 269: length = 19 + read_bits (data, p, 2); break; | ||
318 | case 270: length = 23 + read_bits (data, p, 2); break; | ||
319 | case 271: length = 27 + read_bits (data, p, 2); break; | ||
320 | case 272: length = 31 + read_bits (data, p, 2); break; | ||
321 | case 273: length = 35 + read_bits (data, p, 3); break; | ||
322 | case 274: length = 43 + read_bits (data, p, 3); break; | ||
323 | case 275: length = 51 + read_bits (data, p, 3); break; | ||
324 | case 276: length = 59 + read_bits (data, p, 3); break; | ||
325 | case 277: length = 67 + read_bits (data, p, 4); break; | ||
326 | case 278: length = 83 + read_bits (data, p, 4); break; | ||
327 | case 279: length = 99 + read_bits (data, p, 4); break; | ||
328 | case 280: length = 115 + read_bits (data, p, 4); break; | ||
329 | case 281: length = 131 + read_bits (data, p, 5); break; | ||
330 | case 282: length = 163 + read_bits (data, p, 5); break; | ||
331 | case 283: length = 195 + read_bits (data, p, 5); break; | ||
332 | case 284: length = 227 + read_bits (data, p, 5); break; | ||
333 | case 285: length = 258; break; | ||
334 | default: | ||
335 | return -1; | ||
336 | } | ||
337 | bb = decode_one (data, p, hdist_size_table, HDIST_TSIZE, | ||
338 | hdist_code_table, HDIST_MAXBITS); | ||
339 | switch ( bb ) | ||
340 | { | ||
341 | case 0: dist = 1; break; | ||
342 | case 1: dist = 2; break; | ||
343 | case 2: dist = 3; break; | ||
344 | case 3: dist = 4; break; | ||
345 | case 4: dist = 5 + read_bits (data, p, 1); break; | ||
346 | case 5: dist = 7 + read_bits (data, p, 1); break; | ||
347 | case 6: dist = 9 + read_bits (data, p, 2); break; | ||
348 | case 7: dist = 13 + read_bits (data, p, 2); break; | ||
349 | case 8: dist = 17 + read_bits (data, p, 3); break; | ||
350 | case 9: dist = 25 + read_bits (data, p, 3); break; | ||
351 | case 10: dist = 33 + read_bits (data, p, 4); break; | ||
352 | case 11: dist = 49 + read_bits (data, p, 4); break; | ||
353 | case 12: dist = 65 + read_bits (data, p, 5); break; | ||
354 | case 13: dist = 97 + read_bits (data, p, 5); break; | ||
355 | case 14: dist = 129 + read_bits (data, p, 6); break; | ||
356 | case 15: dist = 193 + read_bits (data, p, 6); break; | ||
357 | case 16: dist = 257 + read_bits (data, p, 7); break; | ||
358 | case 17: dist = 385 + read_bits (data, p, 7); break; | ||
359 | case 18: dist = 513 + read_bits (data, p, 8); break; | ||
360 | case 19: dist = 769 + read_bits (data, p, 8); break; | ||
361 | case 20: dist = 1025 + read_bits (data, p, 9); break; | ||
362 | case 21: dist = 1537 + read_bits (data, p, 9); break; | ||
363 | case 22: dist = 2049 + read_bits (data, p, 10); break; | ||
364 | case 23: dist = 3073 + read_bits (data, p, 10); break; | ||
365 | case 24: dist = 4097 + read_bits (data, p, 11); break; | ||
366 | case 25: dist = 6145 + read_bits (data, p, 11); break; | ||
367 | case 26: dist = 8193 + read_bits (data, p, 12); break; | ||
368 | case 27: dist = 12289 + read_bits (data, p, 12); break; | ||
369 | case 28: dist = 16385 + read_bits (data, p, 13); break; | ||
370 | case 29: dist = 24577 + read_bits (data, p, 13); break; | ||
371 | default: | ||
372 | return -1; | ||
373 | } | ||
374 | for ( l=0 ; l<length ; l++ ) | ||
375 | { | ||
376 | unsigned char ch; | ||
377 | |||
378 | ch = pushin (dist); | ||
379 | pushout (ch); | ||
380 | callback (ch); | ||
381 | } | ||
382 | } | ||
383 | } | ||
384 | return 0; | ||
385 | } | ||
386 | |||
387 | static int | ||
388 | inflate (const unsigned char *data, long *p, | ||
389 | void (* callback) (unsigned char d)) | ||
390 | /* Main uncompression function for the deflate method */ | ||
391 | { | ||
392 | char blast, btype; | ||
393 | char hlit_size_table[HLIT_TSIZE]; | ||
394 | unsigned int hlit_code_table[HLIT_TSIZE]; | ||
395 | char hdist_size_table[HDIST_TSIZE]; | ||
396 | unsigned int hdist_code_table[HDIST_TSIZE]; | ||
397 | |||
398 | again: | ||
399 | blast = read_bits (data, p, 1); | ||
400 | btype = read_bits (data, p, 2); | ||
401 | if ( btype == 1 || btype == 2 ) | ||
402 | { | ||
403 | if ( btype == 2 ) | ||
404 | { | ||
405 | /* Dynamic Huffman tables */ | ||
406 | if (get_tables (data, p, | ||
407 | hlit_size_table, hlit_code_table, | ||
408 | hdist_size_table, hdist_code_table) < 0) return -1; | ||
409 | } | ||
410 | else | ||
411 | /* Fixed Huffman codes */ | ||
412 | { | ||
413 | int j; | ||
414 | |||
415 | for ( j=0 ; j<144 ; j++ ) | ||
416 | hlit_size_table[j] = 8; | ||
417 | for ( ; j<256 ; j++ ) | ||
418 | hlit_size_table[j] = 9; | ||
419 | for ( ; j<280 ; j++ ) | ||
420 | hlit_size_table[j] = 7; | ||
421 | for ( ; j<HLIT_TSIZE ; j++ ) | ||
422 | hlit_size_table[j] = 8; | ||
423 | make_code_table (hlit_size_table, HLIT_TSIZE, | ||
424 | hlit_code_table, HLIT_MAXBITS); | ||
425 | for ( j=0 ; j<HDIST_TSIZE ; j++ ) | ||
426 | hdist_size_table[j] = 5; | ||
427 | make_code_table (hdist_size_table, HDIST_TSIZE, | ||
428 | hdist_code_table, HDIST_MAXBITS); | ||
429 | } | ||
430 | if (get_data (data, p, | ||
431 | hlit_size_table, hlit_code_table, | ||
432 | hdist_size_table, hdist_code_table, | ||
433 | callback) < 0) return -1;; | ||
434 | } | ||
435 | else if ( btype == 0 ) | ||
436 | /* Non compressed block */ | ||
437 | { | ||
438 | unsigned int len, nlen; | ||
439 | unsigned int l; | ||
440 | unsigned char b; | ||
441 | |||
442 | *p = (*p+7)/8; /* Jump to next byte boundary */ | ||
443 | len = read_bits (data, p, 16); | ||
444 | nlen = read_bits (data, p, 16); | ||
445 | for ( l=0 ; l<len ; l++ ) | ||
446 | { | ||
447 | b = read_bits (data, p, 8); | ||
448 | pushout (b); | ||
449 | callback (b); | ||
450 | } | ||
451 | } | ||
452 | else | ||
453 | { | ||
454 | return -1; | ||
455 | } | ||
456 | if ( ! blast ) | ||
457 | goto again; | ||
458 | return 0; | ||
459 | } | ||
460 | |||
461 | int | ||
462 | unzip (const unsigned char *data, long *p, | ||
463 | void (* callback) (unsigned char d)) | ||
464 | /* Uncompress gzipped data. data is a pointer to the data, p is | ||
465 | * a pointer to a long that is initialized to 0 (unless for some | ||
466 | * reason you want to start uncompressing further down the data), | ||
467 | * and callback is a function taking an unsigned char and | ||
468 | * returning void that will be called successively for every | ||
469 | * uncompressed byte. */ | ||
470 | { | ||
471 | unsigned char cm, flg; | ||
472 | |||
473 | if ( read_bits (data, p, 8) != 0x1f | ||
474 | || read_bits (data, p, 8) != 0x8b ) | ||
475 | { | ||
476 | return -1; | ||
477 | } | ||
478 | cm = read_bits (data, p, 8); | ||
479 | if ( cm != 0x8 ) | ||
480 | { | ||
481 | return -1; | ||
482 | } | ||
483 | flg = read_bits (data, p, 8); | ||
484 | if ( flg & 0xe0 ) | ||
485 | /* fprintf (stderr, "Warning: unknown bits are set in flags.\n") */ ; | ||
486 | read_bits (data, p, 32); /* Ignore modification time */ | ||
487 | read_bits (data, p, 8); /* Ignore extra flags */ | ||
488 | read_bits (data, p, 8); /* Ignore OS type */ | ||
489 | if ( flg & 0x4 ) | ||
490 | { | ||
491 | /* Skip over extra data */ | ||
492 | unsigned int xlen; | ||
493 | |||
494 | xlen = read_bits (data, p, 16); | ||
495 | *p += ((long)xlen)*8; | ||
496 | } | ||
497 | if ( flg & 0x8 ) | ||
498 | { | ||
499 | /* Skip over file name */ | ||
500 | while ( read_bits (data, p, 8) ); | ||
501 | } | ||
502 | if ( flg & 0x10 ) | ||
503 | { | ||
504 | /* Skip over comment */ | ||
505 | while ( read_bits (data, p, 8) ); | ||
506 | } | ||
507 | if ( flg & 0x2 ) | ||
508 | /* Ignore CRC16 */ | ||
509 | read_bits (data, p, 16); | ||
510 | return inflate (data, p, callback); | ||
511 | /* CRC32 and ISIZE are at the end. We don't even bother to look at | ||
512 | * them. */ | ||
513 | } | ||
514 | |||