Contents of /trunk/mkinitrd-magellan/busybox/archival/libunarchive/decompress_bunzip2.c
Parent Directory | Revision Log
Revision 532 -
(show annotations)
(download)
Sat Sep 1 22:45:15 2007 UTC (16 years, 8 months ago) by niro
File MIME type: text/plain
File size: 22540 byte(s)
Sat Sep 1 22:45:15 2007 UTC (16 years, 8 months ago) by niro
File MIME type: text/plain
File size: 22540 byte(s)
-import if magellan mkinitrd; it is a fork of redhats mkinitrd-5.0.8 with all magellan patches and features; deprecates magellan-src/mkinitrd
1 | /* vi: set sw=4 ts=4: */ |
2 | /* Small bzip2 deflate implementation, by Rob Landley (rob@landley.net). |
3 | |
4 | Based on bzip2 decompression code by Julian R Seward (jseward@acm.org), |
5 | which also acknowledges contributions by Mike Burrows, David Wheeler, |
6 | Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten, |
7 | Robert Sedgewick, and Jon L. Bentley. |
8 | |
9 | Licensed under GPLv2 or later, see file LICENSE in this tarball for details. |
10 | */ |
11 | |
12 | /* |
13 | Size and speed optimizations by Manuel Novoa III (mjn3@codepoet.org). |
14 | |
15 | More efficient reading of Huffman codes, a streamlined read_bunzip() |
16 | function, and various other tweaks. In (limited) tests, approximately |
17 | 20% faster than bzcat on x86 and about 10% faster on arm. |
18 | |
19 | Note that about 2/3 of the time is spent in read_unzip() reversing |
20 | the Burrows-Wheeler transformation. Much of that time is delay |
21 | resulting from cache misses. |
22 | |
23 | I would ask that anyone benefiting from this work, especially those |
24 | using it in commercial products, consider making a donation to my local |
25 | non-profit hospice organization (www.hospiceacadiana.com) in the name of |
26 | the woman I loved, Toni W. Hagan, who passed away Feb. 12, 2003. |
27 | |
28 | Manuel |
29 | */ |
30 | |
31 | #include "libbb.h" |
32 | #include "unarchive.h" |
33 | |
34 | /* Constants for Huffman coding */ |
35 | #define MAX_GROUPS 6 |
36 | #define GROUP_SIZE 50 /* 64 would have been more efficient */ |
37 | #define MAX_HUFCODE_BITS 20 /* Longest Huffman code allowed */ |
38 | #define MAX_SYMBOLS 258 /* 256 literals + RUNA + RUNB */ |
39 | #define SYMBOL_RUNA 0 |
40 | #define SYMBOL_RUNB 1 |
41 | |
42 | /* Status return values */ |
43 | #define RETVAL_OK 0 |
44 | #define RETVAL_LAST_BLOCK (-1) |
45 | #define RETVAL_NOT_BZIP_DATA (-2) |
46 | #define RETVAL_UNEXPECTED_INPUT_EOF (-3) |
47 | #define RETVAL_UNEXPECTED_OUTPUT_EOF (-4) |
48 | #define RETVAL_DATA_ERROR (-5) |
49 | #define RETVAL_OUT_OF_MEMORY (-6) |
50 | #define RETVAL_OBSOLETE_INPUT (-7) |
51 | |
52 | /* Other housekeeping constants */ |
53 | #define IOBUF_SIZE 4096 |
54 | |
55 | /* This is what we know about each Huffman coding group */ |
56 | struct group_data { |
57 | /* We have an extra slot at the end of limit[] for a sentinal value. */ |
58 | int limit[MAX_HUFCODE_BITS+1],base[MAX_HUFCODE_BITS],permute[MAX_SYMBOLS]; |
59 | int minLen, maxLen; |
60 | }; |
61 | |
62 | /* Structure holding all the housekeeping data, including IO buffers and |
63 | memory that persists between calls to bunzip */ |
64 | |
65 | typedef struct { |
66 | /* State for interrupting output loop */ |
67 | |
68 | int writeCopies,writePos,writeRunCountdown,writeCount,writeCurrent; |
69 | |
70 | /* I/O tracking data (file handles, buffers, positions, etc.) */ |
71 | |
72 | int in_fd,out_fd,inbufCount,inbufPos /*,outbufPos*/; |
73 | unsigned char *inbuf /*,*outbuf*/; |
74 | unsigned int inbufBitCount, inbufBits; |
75 | |
76 | /* The CRC values stored in the block header and calculated from the data */ |
77 | |
78 | uint32_t headerCRC, totalCRC, writeCRC; |
79 | uint32_t *crc32Table; |
80 | /* Intermediate buffer and its size (in bytes) */ |
81 | |
82 | unsigned int *dbuf, dbufSize; |
83 | |
84 | /* These things are a bit too big to go on the stack */ |
85 | |
86 | unsigned char selectors[32768]; /* nSelectors=15 bits */ |
87 | struct group_data groups[MAX_GROUPS]; /* Huffman coding tables */ |
88 | |
89 | /* For I/O error handling */ |
90 | |
91 | jmp_buf jmpbuf; |
92 | } bunzip_data; |
93 | |
94 | /* Return the next nnn bits of input. All reads from the compressed input |
95 | are done through this function. All reads are big endian */ |
96 | |
97 | static unsigned int get_bits(bunzip_data *bd, char bits_wanted) |
98 | { |
99 | unsigned int bits=0; |
100 | |
101 | /* If we need to get more data from the byte buffer, do so. (Loop getting |
102 | one byte at a time to enforce endianness and avoid unaligned access.) */ |
103 | |
104 | while (bd->inbufBitCount<bits_wanted) { |
105 | |
106 | /* If we need to read more data from file into byte buffer, do so */ |
107 | |
108 | if(bd->inbufPos==bd->inbufCount) { |
109 | if((bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE)) <= 0) |
110 | longjmp(bd->jmpbuf,RETVAL_UNEXPECTED_INPUT_EOF); |
111 | bd->inbufPos=0; |
112 | } |
113 | |
114 | /* Avoid 32-bit overflow (dump bit buffer to top of output) */ |
115 | |
116 | if(bd->inbufBitCount>=24) { |
117 | bits=bd->inbufBits&((1<<bd->inbufBitCount)-1); |
118 | bits_wanted-=bd->inbufBitCount; |
119 | bits<<=bits_wanted; |
120 | bd->inbufBitCount=0; |
121 | } |
122 | |
123 | /* Grab next 8 bits of input from buffer. */ |
124 | |
125 | bd->inbufBits=(bd->inbufBits<<8)|bd->inbuf[bd->inbufPos++]; |
126 | bd->inbufBitCount+=8; |
127 | } |
128 | |
129 | /* Calculate result */ |
130 | |
131 | bd->inbufBitCount-=bits_wanted; |
132 | bits|=(bd->inbufBits>>bd->inbufBitCount)&((1<<bits_wanted)-1); |
133 | |
134 | return bits; |
135 | } |
136 | |
137 | /* Unpacks the next block and sets up for the inverse burrows-wheeler step. */ |
138 | |
139 | static int get_next_block(bunzip_data *bd) |
140 | { |
141 | struct group_data *hufGroup; |
142 | int dbufCount,nextSym,dbufSize,groupCount,*base,*limit,selector, |
143 | i,j,k,t,runPos,symCount,symTotal,nSelectors,byteCount[256]; |
144 | unsigned char uc, symToByte[256], mtfSymbol[256], *selectors; |
145 | unsigned int *dbuf,origPtr; |
146 | |
147 | dbuf=bd->dbuf; |
148 | dbufSize=bd->dbufSize; |
149 | selectors=bd->selectors; |
150 | |
151 | /* Reset longjmp I/O error handling */ |
152 | |
153 | i=setjmp(bd->jmpbuf); |
154 | if (i) return i; |
155 | |
156 | /* Read in header signature and CRC, then validate signature. |
157 | (last block signature means CRC is for whole file, return now) */ |
158 | |
159 | i = get_bits(bd,24); |
160 | j = get_bits(bd,24); |
161 | bd->headerCRC=get_bits(bd,32); |
162 | if ((i == 0x177245) && (j == 0x385090)) return RETVAL_LAST_BLOCK; |
163 | if ((i != 0x314159) || (j != 0x265359)) return RETVAL_NOT_BZIP_DATA; |
164 | |
165 | /* We can add support for blockRandomised if anybody complains. There was |
166 | some code for this in busybox 1.0.0-pre3, but nobody ever noticed that |
167 | it didn't actually work. */ |
168 | |
169 | if (get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT; |
170 | if ((origPtr=get_bits(bd,24)) > dbufSize) return RETVAL_DATA_ERROR; |
171 | |
172 | /* mapping table: if some byte values are never used (encoding things |
173 | like ascii text), the compression code removes the gaps to have fewer |
174 | symbols to deal with, and writes a sparse bitfield indicating which |
175 | values were present. We make a translation table to convert the symbols |
176 | back to the corresponding bytes. */ |
177 | |
178 | t=get_bits(bd, 16); |
179 | symTotal=0; |
180 | for (i=0;i<16;i++) { |
181 | if(t&(1<<(15-i))) { |
182 | k=get_bits(bd,16); |
183 | for (j=0;j<16;j++) |
184 | if(k&(1<<(15-j))) symToByte[symTotal++]=(16*i)+j; |
185 | } |
186 | } |
187 | |
188 | /* How many different Huffman coding groups does this block use? */ |
189 | |
190 | groupCount=get_bits(bd,3); |
191 | if (groupCount<2 || groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR; |
192 | |
193 | /* nSelectors: Every GROUP_SIZE many symbols we select a new Huffman coding |
194 | group. Read in the group selector list, which is stored as MTF encoded |
195 | bit runs. (MTF=Move To Front, as each value is used it's moved to the |
196 | start of the list.) */ |
197 | |
198 | if(!(nSelectors=get_bits(bd, 15))) return RETVAL_DATA_ERROR; |
199 | for (i=0; i<groupCount; i++) mtfSymbol[i] = i; |
200 | for (i=0; i<nSelectors; i++) { |
201 | |
202 | /* Get next value */ |
203 | |
204 | for (j=0;get_bits(bd,1);j++) if (j>=groupCount) return RETVAL_DATA_ERROR; |
205 | |
206 | /* Decode MTF to get the next selector */ |
207 | |
208 | uc = mtfSymbol[j]; |
209 | for (;j;j--) mtfSymbol[j] = mtfSymbol[j-1]; |
210 | mtfSymbol[0]=selectors[i]=uc; |
211 | } |
212 | |
213 | /* Read the Huffman coding tables for each group, which code for symTotal |
214 | literal symbols, plus two run symbols (RUNA, RUNB) */ |
215 | |
216 | symCount=symTotal+2; |
217 | for (j=0; j<groupCount; j++) { |
218 | unsigned char length[MAX_SYMBOLS],temp[MAX_HUFCODE_BITS+1]; |
219 | int minLen, maxLen, pp; |
220 | |
221 | /* Read Huffman code lengths for each symbol. They're stored in |
222 | a way similar to mtf; record a starting value for the first symbol, |
223 | and an offset from the previous value for everys symbol after that. |
224 | (Subtracting 1 before the loop and then adding it back at the end is |
225 | an optimization that makes the test inside the loop simpler: symbol |
226 | length 0 becomes negative, so an unsigned inequality catches it.) */ |
227 | |
228 | t=get_bits(bd, 5)-1; |
229 | for (i = 0; i < symCount; i++) { |
230 | for (;;) { |
231 | if (((unsigned)t) > (MAX_HUFCODE_BITS-1)) |
232 | return RETVAL_DATA_ERROR; |
233 | |
234 | /* If first bit is 0, stop. Else second bit indicates whether |
235 | to increment or decrement the value. Optimization: grab 2 |
236 | bits and unget the second if the first was 0. */ |
237 | |
238 | k = get_bits(bd,2); |
239 | if (k < 2) { |
240 | bd->inbufBitCount++; |
241 | break; |
242 | } |
243 | |
244 | /* Add one if second bit 1, else subtract 1. Avoids if/else */ |
245 | |
246 | t+=(((k+1)&2)-1); |
247 | } |
248 | |
249 | /* Correct for the initial -1, to get the final symbol length */ |
250 | |
251 | length[i]=t+1; |
252 | } |
253 | |
254 | /* Find largest and smallest lengths in this group */ |
255 | |
256 | minLen=maxLen=length[0]; |
257 | for (i = 1; i < symCount; i++) { |
258 | if(length[i] > maxLen) maxLen = length[i]; |
259 | else if(length[i] < minLen) minLen = length[i]; |
260 | } |
261 | |
262 | /* Calculate permute[], base[], and limit[] tables from length[]. |
263 | * |
264 | * permute[] is the lookup table for converting Huffman coded symbols |
265 | * into decoded symbols. base[] is the amount to subtract from the |
266 | * value of a Huffman symbol of a given length when using permute[]. |
267 | * |
268 | * limit[] indicates the largest numerical value a symbol with a given |
269 | * number of bits can have. This is how the Huffman codes can vary in |
270 | * length: each code with a value>limit[length] needs another bit. |
271 | */ |
272 | |
273 | hufGroup=bd->groups+j; |
274 | hufGroup->minLen = minLen; |
275 | hufGroup->maxLen = maxLen; |
276 | |
277 | /* Note that minLen can't be smaller than 1, so we adjust the base |
278 | and limit array pointers so we're not always wasting the first |
279 | entry. We do this again when using them (during symbol decoding).*/ |
280 | |
281 | base=hufGroup->base-1; |
282 | limit=hufGroup->limit-1; |
283 | |
284 | /* Calculate permute[]. Concurently, initialize temp[] and limit[]. */ |
285 | |
286 | pp=0; |
287 | for (i=minLen;i<=maxLen;i++) { |
288 | temp[i]=limit[i]=0; |
289 | for (t=0;t<symCount;t++) |
290 | if(length[t]==i) hufGroup->permute[pp++] = t; |
291 | } |
292 | |
293 | /* Count symbols coded for at each bit length */ |
294 | |
295 | for (i=0;i<symCount;i++) temp[length[i]]++; |
296 | |
297 | /* Calculate limit[] (the largest symbol-coding value at each bit |
298 | * length, which is (previous limit<<1)+symbols at this level), and |
299 | * base[] (number of symbols to ignore at each bit length, which is |
300 | * limit minus the cumulative count of symbols coded for already). */ |
301 | |
302 | pp=t=0; |
303 | for (i=minLen; i<maxLen; i++) { |
304 | pp+=temp[i]; |
305 | |
306 | /* We read the largest possible symbol size and then unget bits |
307 | after determining how many we need, and those extra bits could |
308 | be set to anything. (They're noise from future symbols.) At |
309 | each level we're really only interested in the first few bits, |
310 | so here we set all the trailing to-be-ignored bits to 1 so they |
311 | don't affect the value>limit[length] comparison. */ |
312 | |
313 | limit[i]= (pp << (maxLen - i)) - 1; |
314 | pp<<=1; |
315 | base[i+1]=pp-(t+=temp[i]); |
316 | } |
317 | limit[maxLen+1] = INT_MAX; /* Sentinal value for reading next sym. */ |
318 | limit[maxLen]=pp+temp[maxLen]-1; |
319 | base[minLen]=0; |
320 | } |
321 | |
322 | /* We've finished reading and digesting the block header. Now read this |
323 | block's Huffman coded symbols from the file and undo the Huffman coding |
324 | and run length encoding, saving the result into dbuf[dbufCount++]=uc */ |
325 | |
326 | /* Initialize symbol occurrence counters and symbol Move To Front table */ |
327 | |
328 | for (i=0;i<256;i++) { |
329 | byteCount[i] = 0; |
330 | mtfSymbol[i]=(unsigned char)i; |
331 | } |
332 | |
333 | /* Loop through compressed symbols. */ |
334 | |
335 | runPos=dbufCount=selector=0; |
336 | for (;;) { |
337 | |
338 | /* fetch next Huffman coding group from list. */ |
339 | |
340 | symCount=GROUP_SIZE-1; |
341 | if(selector>=nSelectors) return RETVAL_DATA_ERROR; |
342 | hufGroup=bd->groups+selectors[selector++]; |
343 | base=hufGroup->base-1; |
344 | limit=hufGroup->limit-1; |
345 | continue_this_group: |
346 | |
347 | /* Read next Huffman-coded symbol. */ |
348 | |
349 | /* Note: It is far cheaper to read maxLen bits and back up than it is |
350 | to read minLen bits and then an additional bit at a time, testing |
351 | as we go. Because there is a trailing last block (with file CRC), |
352 | there is no danger of the overread causing an unexpected EOF for a |
353 | valid compressed file. As a further optimization, we do the read |
354 | inline (falling back to a call to get_bits if the buffer runs |
355 | dry). The following (up to got_huff_bits:) is equivalent to |
356 | j=get_bits(bd,hufGroup->maxLen); |
357 | */ |
358 | |
359 | while (bd->inbufBitCount<hufGroup->maxLen) { |
360 | if(bd->inbufPos==bd->inbufCount) { |
361 | j = get_bits(bd,hufGroup->maxLen); |
362 | goto got_huff_bits; |
363 | } |
364 | bd->inbufBits=(bd->inbufBits<<8)|bd->inbuf[bd->inbufPos++]; |
365 | bd->inbufBitCount+=8; |
366 | }; |
367 | bd->inbufBitCount-=hufGroup->maxLen; |
368 | j = (bd->inbufBits>>bd->inbufBitCount)&((1<<hufGroup->maxLen)-1); |
369 | |
370 | got_huff_bits: |
371 | |
372 | /* Figure how how many bits are in next symbol and unget extras */ |
373 | |
374 | i=hufGroup->minLen; |
375 | while (j>limit[i]) ++i; |
376 | bd->inbufBitCount += (hufGroup->maxLen - i); |
377 | |
378 | /* Huffman decode value to get nextSym (with bounds checking) */ |
379 | |
380 | if ((i > hufGroup->maxLen) |
381 | || (((unsigned)(j=(j>>(hufGroup->maxLen-i))-base[i])) |
382 | >= MAX_SYMBOLS)) |
383 | return RETVAL_DATA_ERROR; |
384 | nextSym = hufGroup->permute[j]; |
385 | |
386 | /* We have now decoded the symbol, which indicates either a new literal |
387 | byte, or a repeated run of the most recent literal byte. First, |
388 | check if nextSym indicates a repeated run, and if so loop collecting |
389 | how many times to repeat the last literal. */ |
390 | |
391 | if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */ |
392 | |
393 | /* If this is the start of a new run, zero out counter */ |
394 | |
395 | if(!runPos) { |
396 | runPos = 1; |
397 | t = 0; |
398 | } |
399 | |
400 | /* Neat trick that saves 1 symbol: instead of or-ing 0 or 1 at |
401 | each bit position, add 1 or 2 instead. For example, |
402 | 1011 is 1<<0 + 1<<1 + 2<<2. 1010 is 2<<0 + 2<<1 + 1<<2. |
403 | You can make any bit pattern that way using 1 less symbol than |
404 | the basic or 0/1 method (except all bits 0, which would use no |
405 | symbols, but a run of length 0 doesn't mean anything in this |
406 | context). Thus space is saved. */ |
407 | |
408 | t += (runPos << nextSym); /* +runPos if RUNA; +2*runPos if RUNB */ |
409 | if(runPos < dbufSize) runPos <<= 1; |
410 | goto end_of_huffman_loop; |
411 | } |
412 | |
413 | /* When we hit the first non-run symbol after a run, we now know |
414 | how many times to repeat the last literal, so append that many |
415 | copies to our buffer of decoded symbols (dbuf) now. (The last |
416 | literal used is the one at the head of the mtfSymbol array.) */ |
417 | |
418 | if(runPos) { |
419 | runPos=0; |
420 | if(dbufCount+t>=dbufSize) return RETVAL_DATA_ERROR; |
421 | |
422 | uc = symToByte[mtfSymbol[0]]; |
423 | byteCount[uc] += t; |
424 | while (t--) dbuf[dbufCount++]=uc; |
425 | } |
426 | |
427 | /* Is this the terminating symbol? */ |
428 | |
429 | if(nextSym>symTotal) break; |
430 | |
431 | /* At this point, nextSym indicates a new literal character. Subtract |
432 | one to get the position in the MTF array at which this literal is |
433 | currently to be found. (Note that the result can't be -1 or 0, |
434 | because 0 and 1 are RUNA and RUNB. But another instance of the |
435 | first symbol in the mtf array, position 0, would have been handled |
436 | as part of a run above. Therefore 1 unused mtf position minus |
437 | 2 non-literal nextSym values equals -1.) */ |
438 | |
439 | if(dbufCount>=dbufSize) return RETVAL_DATA_ERROR; |
440 | i = nextSym - 1; |
441 | uc = mtfSymbol[i]; |
442 | |
443 | /* Adjust the MTF array. Since we typically expect to move only a |
444 | * small number of symbols, and are bound by 256 in any case, using |
445 | * memmove here would typically be bigger and slower due to function |
446 | * call overhead and other assorted setup costs. */ |
447 | |
448 | do { |
449 | mtfSymbol[i] = mtfSymbol[i-1]; |
450 | } while (--i); |
451 | mtfSymbol[0] = uc; |
452 | uc=symToByte[uc]; |
453 | |
454 | /* We have our literal byte. Save it into dbuf. */ |
455 | |
456 | byteCount[uc]++; |
457 | dbuf[dbufCount++] = (unsigned int)uc; |
458 | |
459 | /* Skip group initialization if we're not done with this group. Done |
460 | * this way to avoid compiler warning. */ |
461 | |
462 | end_of_huffman_loop: |
463 | if(symCount--) goto continue_this_group; |
464 | } |
465 | |
466 | /* At this point, we've read all the Huffman-coded symbols (and repeated |
467 | runs) for this block from the input stream, and decoded them into the |
468 | intermediate buffer. There are dbufCount many decoded bytes in dbuf[]. |
469 | Now undo the Burrows-Wheeler transform on dbuf. |
470 | See http://dogma.net/markn/articles/bwt/bwt.htm |
471 | */ |
472 | |
473 | /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */ |
474 | |
475 | j=0; |
476 | for (i=0;i<256;i++) { |
477 | k=j+byteCount[i]; |
478 | byteCount[i] = j; |
479 | j=k; |
480 | } |
481 | |
482 | /* Figure out what order dbuf would be in if we sorted it. */ |
483 | |
484 | for (i=0;i<dbufCount;i++) { |
485 | uc=(unsigned char)(dbuf[i] & 0xff); |
486 | dbuf[byteCount[uc]] |= (i << 8); |
487 | byteCount[uc]++; |
488 | } |
489 | |
490 | /* Decode first byte by hand to initialize "previous" byte. Note that it |
491 | doesn't get output, and if the first three characters are identical |
492 | it doesn't qualify as a run (hence writeRunCountdown=5). */ |
493 | |
494 | if(dbufCount) { |
495 | if(origPtr>=dbufCount) return RETVAL_DATA_ERROR; |
496 | bd->writePos=dbuf[origPtr]; |
497 | bd->writeCurrent=(unsigned char)(bd->writePos&0xff); |
498 | bd->writePos>>=8; |
499 | bd->writeRunCountdown=5; |
500 | } |
501 | bd->writeCount=dbufCount; |
502 | |
503 | return RETVAL_OK; |
504 | } |
505 | |
506 | /* Undo burrows-wheeler transform on intermediate buffer to produce output. |
507 | If start_bunzip was initialized with out_fd=-1, then up to len bytes of |
508 | data are written to outbuf. Return value is number of bytes written or |
509 | error (all errors are negative numbers). If out_fd!=-1, outbuf and len |
510 | are ignored, data is written to out_fd and return is RETVAL_OK or error. |
511 | */ |
512 | |
513 | static int read_bunzip(bunzip_data *bd, char *outbuf, int len) |
514 | { |
515 | const unsigned int *dbuf; |
516 | int pos,current,previous,gotcount; |
517 | |
518 | /* If last read was short due to end of file, return last block now */ |
519 | if(bd->writeCount<0) return bd->writeCount; |
520 | |
521 | gotcount = 0; |
522 | dbuf=bd->dbuf; |
523 | pos=bd->writePos; |
524 | current=bd->writeCurrent; |
525 | |
526 | /* We will always have pending decoded data to write into the output |
527 | buffer unless this is the very first call (in which case we haven't |
528 | Huffman-decoded a block into the intermediate buffer yet). */ |
529 | |
530 | if (bd->writeCopies) { |
531 | |
532 | /* Inside the loop, writeCopies means extra copies (beyond 1) */ |
533 | |
534 | --bd->writeCopies; |
535 | |
536 | /* Loop outputting bytes */ |
537 | |
538 | for (;;) { |
539 | |
540 | /* If the output buffer is full, snapshot state and return */ |
541 | |
542 | if(gotcount >= len) { |
543 | bd->writePos=pos; |
544 | bd->writeCurrent=current; |
545 | bd->writeCopies++; |
546 | return len; |
547 | } |
548 | |
549 | /* Write next byte into output buffer, updating CRC */ |
550 | |
551 | outbuf[gotcount++] = current; |
552 | bd->writeCRC=(((bd->writeCRC)<<8) |
553 | ^bd->crc32Table[((bd->writeCRC)>>24)^current]); |
554 | |
555 | /* Loop now if we're outputting multiple copies of this byte */ |
556 | |
557 | if (bd->writeCopies) { |
558 | --bd->writeCopies; |
559 | continue; |
560 | } |
561 | decode_next_byte: |
562 | if (!bd->writeCount--) break; |
563 | /* Follow sequence vector to undo Burrows-Wheeler transform */ |
564 | previous=current; |
565 | pos=dbuf[pos]; |
566 | current=pos&0xff; |
567 | pos>>=8; |
568 | |
569 | /* After 3 consecutive copies of the same byte, the 4th is a repeat |
570 | count. We count down from 4 instead |
571 | * of counting up because testing for non-zero is faster */ |
572 | |
573 | if(--bd->writeRunCountdown) { |
574 | if(current!=previous) bd->writeRunCountdown=4; |
575 | } else { |
576 | |
577 | /* We have a repeated run, this byte indicates the count */ |
578 | |
579 | bd->writeCopies=current; |
580 | current=previous; |
581 | bd->writeRunCountdown=5; |
582 | |
583 | /* Sometimes there are just 3 bytes (run length 0) */ |
584 | |
585 | if(!bd->writeCopies) goto decode_next_byte; |
586 | |
587 | /* Subtract the 1 copy we'd output anyway to get extras */ |
588 | |
589 | --bd->writeCopies; |
590 | } |
591 | } |
592 | |
593 | /* Decompression of this block completed successfully */ |
594 | |
595 | bd->writeCRC=~bd->writeCRC; |
596 | bd->totalCRC=((bd->totalCRC<<1) | (bd->totalCRC>>31)) ^ bd->writeCRC; |
597 | |
598 | /* If this block had a CRC error, force file level CRC error. */ |
599 | |
600 | if(bd->writeCRC!=bd->headerCRC) { |
601 | bd->totalCRC=bd->headerCRC+1; |
602 | return RETVAL_LAST_BLOCK; |
603 | } |
604 | } |
605 | |
606 | /* Refill the intermediate buffer by Huffman-decoding next block of input */ |
607 | /* (previous is just a convenient unused temp variable here) */ |
608 | |
609 | previous=get_next_block(bd); |
610 | if(previous) { |
611 | bd->writeCount=previous; |
612 | return (previous!=RETVAL_LAST_BLOCK) ? previous : gotcount; |
613 | } |
614 | bd->writeCRC=~0; |
615 | pos=bd->writePos; |
616 | current=bd->writeCurrent; |
617 | goto decode_next_byte; |
618 | } |
619 | |
620 | /* Allocate the structure, read file header. If in_fd==-1, inbuf must contain |
621 | a complete bunzip file (len bytes long). If in_fd!=-1, inbuf and len are |
622 | ignored, and data is read from file handle into temporary buffer. */ |
623 | |
624 | static int start_bunzip(bunzip_data **bdp, int in_fd, unsigned char *inbuf, |
625 | int len) |
626 | { |
627 | bunzip_data *bd; |
628 | unsigned int i; |
629 | const unsigned int BZh0=(((unsigned int)'B')<<24)+(((unsigned int)'Z')<<16) |
630 | +(((unsigned int)'h')<<8)+(unsigned int)'0'; |
631 | |
632 | /* Figure out how much data to allocate */ |
633 | |
634 | i=sizeof(bunzip_data); |
635 | if(in_fd!=-1) i+=IOBUF_SIZE; |
636 | |
637 | /* Allocate bunzip_data. Most fields initialize to zero. */ |
638 | |
639 | bd=*bdp=xzalloc(i); |
640 | |
641 | /* Setup input buffer */ |
642 | |
643 | if(-1==(bd->in_fd=in_fd)) { |
644 | bd->inbuf=inbuf; |
645 | bd->inbufCount=len; |
646 | } else bd->inbuf=(unsigned char *)(bd+1); |
647 | |
648 | /* Init the CRC32 table (big endian) */ |
649 | |
650 | bd->crc32Table = crc32_filltable(1); |
651 | |
652 | /* Setup for I/O error handling via longjmp */ |
653 | |
654 | i=setjmp(bd->jmpbuf); |
655 | if(i) return i; |
656 | |
657 | /* Ensure that file starts with "BZh['1'-'9']." */ |
658 | |
659 | i = get_bits(bd,32); |
660 | if (((unsigned int)(i-BZh0-1)) >= 9) return RETVAL_NOT_BZIP_DATA; |
661 | |
662 | /* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of |
663 | uncompressed data. Allocate intermediate buffer for block. */ |
664 | |
665 | bd->dbufSize=100000*(i-BZh0); |
666 | |
667 | bd->dbuf=xmalloc(bd->dbufSize * sizeof(int)); |
668 | return RETVAL_OK; |
669 | } |
670 | |
671 | /* Example usage: decompress src_fd to dst_fd. (Stops at end of bzip data, |
672 | not end of file.) */ |
673 | |
674 | USE_DESKTOP(long long) int |
675 | uncompressStream(int src_fd, int dst_fd) |
676 | { |
677 | USE_DESKTOP(long long total_written = 0;) |
678 | char *outbuf; |
679 | bunzip_data *bd; |
680 | int i; |
681 | |
682 | outbuf=xmalloc(IOBUF_SIZE); |
683 | i=start_bunzip(&bd,src_fd,0,0); |
684 | if(!i) { |
685 | for (;;) { |
686 | if((i=read_bunzip(bd,outbuf,IOBUF_SIZE)) <= 0) break; |
687 | if(i!=write(dst_fd,outbuf,i)) { |
688 | i=RETVAL_UNEXPECTED_OUTPUT_EOF; |
689 | break; |
690 | } |
691 | USE_DESKTOP(total_written += i;) |
692 | } |
693 | } |
694 | |
695 | /* Check CRC and release memory */ |
696 | |
697 | if(i==RETVAL_LAST_BLOCK) { |
698 | if (bd->headerCRC!=bd->totalCRC) { |
699 | bb_error_msg("data integrity error when decompressing"); |
700 | } else { |
701 | i=RETVAL_OK; |
702 | } |
703 | } else if (i==RETVAL_UNEXPECTED_OUTPUT_EOF) { |
704 | bb_error_msg("compressed file ends unexpectedly"); |
705 | } else { |
706 | bb_error_msg("decompression failed"); |
707 | } |
708 | free(bd->dbuf); |
709 | free(bd); |
710 | free(outbuf); |
711 | |
712 | return i ? i : USE_DESKTOP(total_written) + 0; |
713 | } |
714 | |
715 | #ifdef TESTING |
716 | |
717 | static char * const bunzip_errors[]={NULL,"Bad file checksum","Not bzip data", |
718 | "Unexpected input EOF","Unexpected output EOF","Data error", |
719 | "Out of memory","Obsolete (pre 0.9.5) bzip format not supported."}; |
720 | |
721 | /* Dumb little test thing, decompress stdin to stdout */ |
722 | int main(int argc, char *argv[]) |
723 | { |
724 | int i=uncompressStream(0,1); |
725 | char c; |
726 | |
727 | if(i<0) fprintf(stderr,"%s\n", bunzip_errors[-i]); |
728 | else if(read(0,&c,1)) fprintf(stderr,"Trailing garbage ignored\n"); |
729 | return -i; |
730 | } |
731 | #endif |