summaryrefslogtreecommitdiff
path: root/apps/plugins/rockboy/inflate.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/rockboy/inflate.c')
-rw-r--r--apps/plugins/rockboy/inflate.c514
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
20static unsigned int
21peek_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
42static unsigned int
43read_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
53static void
54make_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
78static int
79decode_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
121static int
122get_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 */
250static unsigned int buffer_ptr = 0;
251
252/* The buffer itself */
253static unsigned char buffer[BUFFER_SIZE];
254
255static void
256pushout (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
264static unsigned char
265pushin (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
271static int
272get_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
387static int
388inflate (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
461int
462unzip (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
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-12 19:36:49 +0000