1
/* vi: set sw = 4 ts = 4: */
2
/* Small bzip2 deflate implementation, by Rob Landley (rob@landley.net).
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.
9
This code is licensed under the LGPLv2:
10
LGPL (http://www.gnu.org/copyleft/lgpl.html
14
Size and speed optimizations by Manuel Novoa III (mjn3@codepoet.org).
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.
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.
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.
29
In memory of Toni W. Hagan
31
Hospice of Acadiana, Inc.
32
2600 Johnston St., Suite 200
33
Lafayette, LA 70503-3240
35
Phone (337) 232-1234 or 1-800-738-2226
38
http://www.hospiceacadiana.com/
44
Made it fit for running in Linux Kernel by Alain Knaff (alain@knaff.lu)
51
#include <linux/decompress/bunzip2.h>
54
#include <linux/decompress/mm.h>
57
#define INT_MAX 0x7fffffff
60
/* Constants for Huffman coding */
62
#define GROUP_SIZE 50 /* 64 would have been more efficient */
63
#define MAX_HUFCODE_BITS 20 /* Longest Huffman code allowed */
64
#define MAX_SYMBOLS 258 /* 256 literals + RUNA + RUNB */
68
/* Status return values */
70
#define RETVAL_LAST_BLOCK (-1)
71
#define RETVAL_NOT_BZIP_DATA (-2)
72
#define RETVAL_UNEXPECTED_INPUT_EOF (-3)
73
#define RETVAL_UNEXPECTED_OUTPUT_EOF (-4)
74
#define RETVAL_DATA_ERROR (-5)
75
#define RETVAL_OUT_OF_MEMORY (-6)
76
#define RETVAL_OBSOLETE_INPUT (-7)
78
/* Other housekeeping constants */
79
#define BZIP2_IOBUF_SIZE 4096
81
/* This is what we know about each Huffman coding group */
83
/* We have an extra slot at the end of limit[] for a sentinal value. */
84
int limit[MAX_HUFCODE_BITS+1];
85
int base[MAX_HUFCODE_BITS];
86
int permute[MAX_SYMBOLS];
90
/* Structure holding all the housekeeping data, including IO buffers and
91
memory that persists between calls to bunzip */
93
/* State for interrupting output loop */
94
int writeCopies, writePos, writeRunCountdown, writeCount, writeCurrent;
95
/* I/O tracking data (file handles, buffers, positions, etc.) */
96
int (*fill)(void*, unsigned int);
97
int inbufCount, inbufPos /*, outbufPos*/;
98
unsigned char *inbuf /*,*outbuf*/;
99
unsigned int inbufBitCount, inbufBits;
100
/* The CRC values stored in the block header and calculated from the
102
unsigned int crc32Table[256], headerCRC, totalCRC, writeCRC;
103
/* Intermediate buffer and its size (in bytes) */
104
unsigned int *dbuf, dbufSize;
105
/* These things are a bit too big to go on the stack */
106
unsigned char selectors[32768]; /* nSelectors = 15 bits */
107
struct group_data groups[MAX_GROUPS]; /* Huffman coding tables */
108
int io_error; /* non-zero if we have IO error */
110
unsigned char symToByte[256], mtfSymbol[256];
114
/* Return the next nnn bits of input. All reads from the compressed input
115
are done through this function. All reads are big endian */
116
static unsigned int INIT get_bits(struct bunzip_data *bd, char bits_wanted)
118
unsigned int bits = 0;
120
/* If we need to get more data from the byte buffer, do so.
121
(Loop getting one byte at a time to enforce endianness and avoid
122
unaligned access.) */
123
while (bd->inbufBitCount < bits_wanted) {
124
/* If we need to read more data from file into byte buffer, do
126
if (bd->inbufPos == bd->inbufCount) {
129
bd->inbufCount = bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE);
130
if (bd->inbufCount <= 0) {
131
bd->io_error = RETVAL_UNEXPECTED_INPUT_EOF;
136
/* Avoid 32-bit overflow (dump bit buffer to top of output) */
137
if (bd->inbufBitCount >= 24) {
138
bits = bd->inbufBits&((1 << bd->inbufBitCount)-1);
139
bits_wanted -= bd->inbufBitCount;
140
bits <<= bits_wanted;
141
bd->inbufBitCount = 0;
143
/* Grab next 8 bits of input from buffer. */
144
bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
145
bd->inbufBitCount += 8;
147
/* Calculate result */
148
bd->inbufBitCount -= bits_wanted;
149
bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1);
154
/* Unpacks the next block and sets up for the inverse burrows-wheeler step. */
156
static int INIT get_next_block(struct bunzip_data *bd)
158
struct group_data *hufGroup = NULL;
161
int dbufCount, nextSym, dbufSize, groupCount, selector,
162
i, j, k, t, runPos, symCount, symTotal, nSelectors, *byteCount;
163
unsigned char uc, *symToByte, *mtfSymbol, *selectors;
164
unsigned int *dbuf, origPtr;
167
dbufSize = bd->dbufSize;
168
selectors = bd->selectors;
169
byteCount = bd->byteCount;
170
symToByte = bd->symToByte;
171
mtfSymbol = bd->mtfSymbol;
173
/* Read in header signature and CRC, then validate signature.
174
(last block signature means CRC is for whole file, return now) */
175
i = get_bits(bd, 24);
176
j = get_bits(bd, 24);
177
bd->headerCRC = get_bits(bd, 32);
178
if ((i == 0x177245) && (j == 0x385090))
179
return RETVAL_LAST_BLOCK;
180
if ((i != 0x314159) || (j != 0x265359))
181
return RETVAL_NOT_BZIP_DATA;
182
/* We can add support for blockRandomised if anybody complains.
183
There was some code for this in busybox 1.0.0-pre3, but nobody ever
184
noticed that it didn't actually work. */
186
return RETVAL_OBSOLETE_INPUT;
187
origPtr = get_bits(bd, 24);
188
if (origPtr > dbufSize)
189
return RETVAL_DATA_ERROR;
190
/* mapping table: if some byte values are never used (encoding things
191
like ascii text), the compression code removes the gaps to have fewer
192
symbols to deal with, and writes a sparse bitfield indicating which
193
values were present. We make a translation table to convert the
194
symbols back to the corresponding bytes. */
195
t = get_bits(bd, 16);
197
for (i = 0; i < 16; i++) {
198
if (t&(1 << (15-i))) {
199
k = get_bits(bd, 16);
200
for (j = 0; j < 16; j++)
202
symToByte[symTotal++] = (16*i)+j;
205
/* How many different Huffman coding groups does this block use? */
206
groupCount = get_bits(bd, 3);
207
if (groupCount < 2 || groupCount > MAX_GROUPS)
208
return RETVAL_DATA_ERROR;
209
/* nSelectors: Every GROUP_SIZE many symbols we select a new
210
Huffman coding group. Read in the group selector list,
211
which is stored as MTF encoded bit runs. (MTF = Move To
212
Front, as each value is used it's moved to the start of the
214
nSelectors = get_bits(bd, 15);
216
return RETVAL_DATA_ERROR;
217
for (i = 0; i < groupCount; i++)
219
for (i = 0; i < nSelectors; i++) {
221
for (j = 0; get_bits(bd, 1); j++)
223
return RETVAL_DATA_ERROR;
224
/* Decode MTF to get the next selector */
227
mtfSymbol[j] = mtfSymbol[j-1];
228
mtfSymbol[0] = selectors[i] = uc;
230
/* Read the Huffman coding tables for each group, which code
231
for symTotal literal symbols, plus two run symbols (RUNA,
233
symCount = symTotal+2;
234
for (j = 0; j < groupCount; j++) {
235
unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1];
236
int minLen, maxLen, pp;
237
/* Read Huffman code lengths for each symbol. They're
238
stored in a way similar to mtf; record a starting
239
value for the first symbol, and an offset from the
240
previous value for everys symbol after that.
241
(Subtracting 1 before the loop and then adding it
242
back at the end is an optimization that makes the
243
test inside the loop simpler: symbol length 0
244
becomes negative, so an unsigned inequality catches
246
t = get_bits(bd, 5)-1;
247
for (i = 0; i < symCount; i++) {
249
if (((unsigned)t) > (MAX_HUFCODE_BITS-1))
250
return RETVAL_DATA_ERROR;
252
/* If first bit is 0, stop. Else
253
second bit indicates whether to
254
increment or decrement the value.
255
Optimization: grab 2 bits and unget
256
the second if the first was 0. */
263
/* Add one if second bit 1, else
264
* subtract 1. Avoids if/else */
267
/* Correct for the initial -1, to get the
268
* final symbol length */
271
/* Find largest and smallest lengths in this group */
272
minLen = maxLen = length[0];
274
for (i = 1; i < symCount; i++) {
275
if (length[i] > maxLen)
277
else if (length[i] < minLen)
281
/* Calculate permute[], base[], and limit[] tables from
284
* permute[] is the lookup table for converting
285
* Huffman coded symbols into decoded symbols. base[]
286
* is the amount to subtract from the value of a
287
* Huffman symbol of a given length when using
290
* limit[] indicates the largest numerical value a
291
* symbol with a given number of bits can have. This
292
* is how the Huffman codes can vary in length: each
293
* code with a value > limit[length] needs another
296
hufGroup = bd->groups+j;
297
hufGroup->minLen = minLen;
298
hufGroup->maxLen = maxLen;
299
/* Note that minLen can't be smaller than 1, so we
300
adjust the base and limit array pointers so we're
301
not always wasting the first entry. We do this
302
again when using them (during symbol decoding).*/
303
base = hufGroup->base-1;
304
limit = hufGroup->limit-1;
305
/* Calculate permute[]. Concurrently, initialize
306
* temp[] and limit[]. */
308
for (i = minLen; i <= maxLen; i++) {
309
temp[i] = limit[i] = 0;
310
for (t = 0; t < symCount; t++)
312
hufGroup->permute[pp++] = t;
314
/* Count symbols coded for at each bit length */
315
for (i = 0; i < symCount; i++)
317
/* Calculate limit[] (the largest symbol-coding value
318
*at each bit length, which is (previous limit <<
319
*1)+symbols at this level), and base[] (number of
320
*symbols to ignore at each bit length, which is limit
321
*minus the cumulative count of symbols coded for
324
for (i = minLen; i < maxLen; i++) {
326
/* We read the largest possible symbol size
327
and then unget bits after determining how
328
many we need, and those extra bits could be
329
set to anything. (They're noise from
330
future symbols.) At each level we're
331
really only interested in the first few
332
bits, so here we set all the trailing
333
to-be-ignored bits to 1 so they don't
334
affect the value > limit[length]
336
limit[i] = (pp << (maxLen - i)) - 1;
338
base[i+1] = pp-(t += temp[i]);
340
limit[maxLen+1] = INT_MAX; /* Sentinal value for
341
* reading next sym. */
342
limit[maxLen] = pp+temp[maxLen]-1;
345
/* We've finished reading and digesting the block header. Now
346
read this block's Huffman coded symbols from the file and
347
undo the Huffman coding and run length encoding, saving the
348
result into dbuf[dbufCount++] = uc */
350
/* Initialize symbol occurrence counters and symbol Move To
352
for (i = 0; i < 256; i++) {
354
mtfSymbol[i] = (unsigned char)i;
356
/* Loop through compressed symbols. */
357
runPos = dbufCount = symCount = selector = 0;
359
/* Determine which Huffman coding group to use. */
361
symCount = GROUP_SIZE-1;
362
if (selector >= nSelectors)
363
return RETVAL_DATA_ERROR;
364
hufGroup = bd->groups+selectors[selector++];
365
base = hufGroup->base-1;
366
limit = hufGroup->limit-1;
368
/* Read next Huffman-coded symbol. */
369
/* Note: It is far cheaper to read maxLen bits and
370
back up than it is to read minLen bits and then an
371
additional bit at a time, testing as we go.
372
Because there is a trailing last block (with file
373
CRC), there is no danger of the overread causing an
374
unexpected EOF for a valid compressed file. As a
375
further optimization, we do the read inline
376
(falling back to a call to get_bits if the buffer
377
runs dry). The following (up to got_huff_bits:) is
378
equivalent to j = get_bits(bd, hufGroup->maxLen);
380
while (bd->inbufBitCount < hufGroup->maxLen) {
381
if (bd->inbufPos == bd->inbufCount) {
382
j = get_bits(bd, hufGroup->maxLen);
386
(bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
387
bd->inbufBitCount += 8;
389
bd->inbufBitCount -= hufGroup->maxLen;
390
j = (bd->inbufBits >> bd->inbufBitCount)&
391
((1 << hufGroup->maxLen)-1);
393
/* Figure how how many bits are in next symbol and
395
i = hufGroup->minLen;
398
bd->inbufBitCount += (hufGroup->maxLen - i);
399
/* Huffman decode value to get nextSym (with bounds checking) */
400
if ((i > hufGroup->maxLen)
401
|| (((unsigned)(j = (j>>(hufGroup->maxLen-i))-base[i]))
403
return RETVAL_DATA_ERROR;
404
nextSym = hufGroup->permute[j];
405
/* We have now decoded the symbol, which indicates
406
either a new literal byte, or a repeated run of the
407
most recent literal byte. First, check if nextSym
408
indicates a repeated run, and if so loop collecting
409
how many times to repeat the last literal. */
410
if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */
411
/* If this is the start of a new run, zero out
417
/* Neat trick that saves 1 symbol: instead of
418
or-ing 0 or 1 at each bit position, add 1
419
or 2 instead. For example, 1011 is 1 << 0
420
+ 1 << 1 + 2 << 2. 1010 is 2 << 0 + 2 << 1
421
+ 1 << 2. You can make any bit pattern
422
that way using 1 less symbol than the basic
423
or 0/1 method (except all bits 0, which
424
would use no symbols, but a run of length 0
425
doesn't mean anything in this context).
426
Thus space is saved. */
427
t += (runPos << nextSym);
428
/* +runPos if RUNA; +2*runPos if RUNB */
433
/* When we hit the first non-run symbol after a run,
434
we now know how many times to repeat the last
435
literal, so append that many copies to our buffer
436
of decoded symbols (dbuf) now. (The last literal
437
used is the one at the head of the mtfSymbol
441
if (dbufCount+t >= dbufSize)
442
return RETVAL_DATA_ERROR;
444
uc = symToByte[mtfSymbol[0]];
447
dbuf[dbufCount++] = uc;
449
/* Is this the terminating symbol? */
450
if (nextSym > symTotal)
452
/* At this point, nextSym indicates a new literal
453
character. Subtract one to get the position in the
454
MTF array at which this literal is currently to be
455
found. (Note that the result can't be -1 or 0,
456
because 0 and 1 are RUNA and RUNB. But another
457
instance of the first symbol in the mtf array,
458
position 0, would have been handled as part of a
459
run above. Therefore 1 unused mtf position minus 2
460
non-literal nextSym values equals -1.) */
461
if (dbufCount >= dbufSize)
462
return RETVAL_DATA_ERROR;
465
/* Adjust the MTF array. Since we typically expect to
466
*move only a small number of symbols, and are bound
467
*by 256 in any case, using memmove here would
468
*typically be bigger and slower due to function call
469
*overhead and other assorted setup costs. */
471
mtfSymbol[i] = mtfSymbol[i-1];
475
/* We have our literal byte. Save it into dbuf. */
477
dbuf[dbufCount++] = (unsigned int)uc;
479
/* At this point, we've read all the Huffman-coded symbols
480
(and repeated runs) for this block from the input stream,
481
and decoded them into the intermediate buffer. There are
482
dbufCount many decoded bytes in dbuf[]. Now undo the
483
Burrows-Wheeler transform on dbuf. See
484
http://dogma.net/markn/articles/bwt/bwt.htm
486
/* Turn byteCount into cumulative occurrence counts of 0 to n-1. */
488
for (i = 0; i < 256; i++) {
493
/* Figure out what order dbuf would be in if we sorted it. */
494
for (i = 0; i < dbufCount; i++) {
495
uc = (unsigned char)(dbuf[i] & 0xff);
496
dbuf[byteCount[uc]] |= (i << 8);
499
/* Decode first byte by hand to initialize "previous" byte.
500
Note that it doesn't get output, and if the first three
501
characters are identical it doesn't qualify as a run (hence
502
writeRunCountdown = 5). */
504
if (origPtr >= dbufCount)
505
return RETVAL_DATA_ERROR;
506
bd->writePos = dbuf[origPtr];
507
bd->writeCurrent = (unsigned char)(bd->writePos&0xff);
509
bd->writeRunCountdown = 5;
511
bd->writeCount = dbufCount;
516
/* Undo burrows-wheeler transform on intermediate buffer to produce output.
517
If start_bunzip was initialized with out_fd =-1, then up to len bytes of
518
data are written to outbuf. Return value is number of bytes written or
519
error (all errors are negative numbers). If out_fd!=-1, outbuf and len
520
are ignored, data is written to out_fd and return is RETVAL_OK or error.
523
static int INIT read_bunzip(struct bunzip_data *bd, char *outbuf, int len)
525
const unsigned int *dbuf;
526
int pos, xcurrent, previous, gotcount;
528
/* If last read was short due to end of file, return last block now */
529
if (bd->writeCount < 0)
530
return bd->writeCount;
535
xcurrent = bd->writeCurrent;
537
/* We will always have pending decoded data to write into the output
538
buffer unless this is the very first call (in which case we haven't
539
Huffman-decoded a block into the intermediate buffer yet). */
541
if (bd->writeCopies) {
542
/* Inside the loop, writeCopies means extra copies (beyond 1) */
544
/* Loop outputting bytes */
546
/* If the output buffer is full, snapshot
547
* state and return */
548
if (gotcount >= len) {
550
bd->writeCurrent = xcurrent;
554
/* Write next byte into output buffer, updating CRC */
555
outbuf[gotcount++] = xcurrent;
556
bd->writeCRC = (((bd->writeCRC) << 8)
557
^bd->crc32Table[((bd->writeCRC) >> 24)
559
/* Loop now if we're outputting multiple
560
* copies of this byte */
561
if (bd->writeCopies) {
566
if (!bd->writeCount--)
568
/* Follow sequence vector to undo
569
* Burrows-Wheeler transform */
574
/* After 3 consecutive copies of the same
575
byte, the 4th is a repeat count. We count
576
down from 4 instead *of counting up because
577
testing for non-zero is faster */
578
if (--bd->writeRunCountdown) {
579
if (xcurrent != previous)
580
bd->writeRunCountdown = 4;
582
/* We have a repeated run, this byte
583
* indicates the count */
584
bd->writeCopies = xcurrent;
586
bd->writeRunCountdown = 5;
587
/* Sometimes there are just 3 bytes
589
if (!bd->writeCopies)
590
goto decode_next_byte;
591
/* Subtract the 1 copy we'd output
592
* anyway to get extras */
596
/* Decompression of this block completed successfully */
597
bd->writeCRC = ~bd->writeCRC;
598
bd->totalCRC = ((bd->totalCRC << 1) |
599
(bd->totalCRC >> 31)) ^ bd->writeCRC;
600
/* If this block had a CRC error, force file level CRC error. */
601
if (bd->writeCRC != bd->headerCRC) {
602
bd->totalCRC = bd->headerCRC+1;
603
return RETVAL_LAST_BLOCK;
607
/* Refill the intermediate buffer by Huffman-decoding next
609
/* (previous is just a convenient unused temp variable here) */
610
previous = get_next_block(bd);
612
bd->writeCount = previous;
613
return (previous != RETVAL_LAST_BLOCK) ? previous : gotcount;
615
bd->writeCRC = 0xffffffffUL;
617
xcurrent = bd->writeCurrent;
618
goto decode_next_byte;
621
static int INIT nofill(void *buf, unsigned int len)
626
/* Allocate the structure, read file header. If in_fd ==-1, inbuf must contain
627
a complete bunzip file (len bytes long). If in_fd!=-1, inbuf and len are
628
ignored, and data is read from file handle into temporary buffer. */
629
static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len,
630
int (*fill)(void*, unsigned int))
632
struct bunzip_data *bd;
633
unsigned int i, j, c;
634
const unsigned int BZh0 =
635
(((unsigned int)'B') << 24)+(((unsigned int)'Z') << 16)
636
+(((unsigned int)'h') << 8)+(unsigned int)'0';
638
/* Figure out how much data to allocate */
639
i = sizeof(struct bunzip_data);
641
/* Allocate bunzip_data. Most fields initialize to zero. */
642
bd = *bdp = malloc(i);
644
return RETVAL_OUT_OF_MEMORY;
645
memset(bd, 0, sizeof(struct bunzip_data));
646
/* Setup input buffer */
648
bd->inbufCount = len;
654
/* Init the CRC32 table (big endian) */
655
for (i = 0; i < 256; i++) {
658
c = c&0x80000000 ? (c << 1)^0x04c11db7 : (c << 1);
659
bd->crc32Table[i] = c;
662
/* Ensure that file starts with "BZh['1'-'9']." */
663
i = get_bits(bd, 32);
664
if (((unsigned int)(i-BZh0-1)) >= 9)
665
return RETVAL_NOT_BZIP_DATA;
667
/* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of
668
uncompressed data. Allocate intermediate buffer for block. */
669
bd->dbufSize = 100000*(i-BZh0);
671
bd->dbuf = large_malloc(bd->dbufSize * sizeof(int));
673
return RETVAL_OUT_OF_MEMORY;
677
/* Example usage: decompress src_fd to dst_fd. (Stops at end of bzip2 data,
679
STATIC int INIT bunzip2(unsigned char *buf, int len,
680
int(*fill)(void*, unsigned int),
681
int(*flush)(void*, unsigned int),
682
unsigned char *outbuf,
684
void(*error)(char *x))
686
struct bunzip_data *bd;
688
unsigned char *inbuf;
691
outbuf = malloc(BZIP2_IOBUF_SIZE);
694
error("Could not allocate output bufer");
695
return RETVAL_OUT_OF_MEMORY;
700
inbuf = malloc(BZIP2_IOBUF_SIZE);
702
error("Could not allocate input bufer");
703
i = RETVAL_OUT_OF_MEMORY;
706
i = start_bunzip(&bd, inbuf, len, fill);
709
i = read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE);
715
if (i != flush(outbuf, i)) {
716
i = RETVAL_UNEXPECTED_OUTPUT_EOF;
721
/* Check CRC and release memory */
722
if (i == RETVAL_LAST_BLOCK) {
723
if (bd->headerCRC != bd->totalCRC)
724
error("Data integrity error when decompressing.");
727
} else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) {
728
error("Compressed file ends unexpectedly");
733
large_free(bd->dbuf);
747
STATIC int INIT decompress(unsigned char *buf, int len,
748
int(*fill)(void*, unsigned int),
749
int(*flush)(void*, unsigned int),
750
unsigned char *outbuf,
752
void(*error)(char *x))
754
return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error);