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