1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#ifdef STATIC
48#define PREBOOT
49#else
50#include <linux/decompress/bunzip2.h>
51#endif
52
53#include <linux/decompress/mm.h>
54
55#ifndef INT_MAX
56#define INT_MAX 0x7fffffff
57#endif
58
59
60#define MAX_GROUPS 6
61#define GROUP_SIZE 50
62#define MAX_HUFCODE_BITS 20
63#define MAX_SYMBOLS 258
64#define SYMBOL_RUNA 0
65#define SYMBOL_RUNB 1
66
67
68#define RETVAL_OK 0
69#define RETVAL_LAST_BLOCK (-1)
70#define RETVAL_NOT_BZIP_DATA (-2)
71#define RETVAL_UNEXPECTED_INPUT_EOF (-3)
72#define RETVAL_UNEXPECTED_OUTPUT_EOF (-4)
73#define RETVAL_DATA_ERROR (-5)
74#define RETVAL_OUT_OF_MEMORY (-6)
75#define RETVAL_OBSOLETE_INPUT (-7)
76
77
78#define BZIP2_IOBUF_SIZE 4096
79
80
81struct group_data {
82
83 int limit[MAX_HUFCODE_BITS+1];
84 int base[MAX_HUFCODE_BITS];
85 int permute[MAX_SYMBOLS];
86 int minLen, maxLen;
87};
88
89
90
91struct bunzip_data {
92
93 int writeCopies, writePos, writeRunCountdown, writeCount, writeCurrent;
94
95 int (*fill)(void*, unsigned int);
96 int inbufCount, inbufPos ;
97 unsigned char *inbuf ;
98 unsigned int inbufBitCount, inbufBits;
99
100
101 unsigned int crc32Table[256], headerCRC, totalCRC, writeCRC;
102
103 unsigned int *dbuf, dbufSize;
104
105 unsigned char selectors[32768];
106 struct group_data groups[MAX_GROUPS];
107 int io_error;
108 int byteCount[256];
109 unsigned char symToByte[256], mtfSymbol[256];
110};
111
112
113
114
115static unsigned int INIT get_bits(struct bunzip_data *bd, char bits_wanted)
116{
117 unsigned int bits = 0;
118
119
120
121
122 while (bd->inbufBitCount < bits_wanted) {
123
124
125 if (bd->inbufPos == bd->inbufCount) {
126 if (bd->io_error)
127 return 0;
128 bd->inbufCount = bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE);
129 if (bd->inbufCount <= 0) {
130 bd->io_error = RETVAL_UNEXPECTED_INPUT_EOF;
131 return 0;
132 }
133 bd->inbufPos = 0;
134 }
135
136 if (bd->inbufBitCount >= 24) {
137 bits = bd->inbufBits&((1 << bd->inbufBitCount)-1);
138 bits_wanted -= bd->inbufBitCount;
139 bits <<= bits_wanted;
140 bd->inbufBitCount = 0;
141 }
142
143 bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
144 bd->inbufBitCount += 8;
145 }
146
147 bd->inbufBitCount -= bits_wanted;
148 bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1);
149
150 return bits;
151}
152
153
154
155static int INIT get_next_block(struct bunzip_data *bd)
156{
157 struct group_data *hufGroup = NULL;
158 int *base = NULL;
159 int *limit = NULL;
160 int dbufCount, nextSym, dbufSize, groupCount, selector,
161 i, j, k, t, runPos, symCount, symTotal, nSelectors, *byteCount;
162 unsigned char uc, *symToByte, *mtfSymbol, *selectors;
163 unsigned int *dbuf, origPtr;
164
165 dbuf = bd->dbuf;
166 dbufSize = bd->dbufSize;
167 selectors = bd->selectors;
168 byteCount = bd->byteCount;
169 symToByte = bd->symToByte;
170 mtfSymbol = bd->mtfSymbol;
171
172
173
174 i = get_bits(bd, 24);
175 j = get_bits(bd, 24);
176 bd->headerCRC = get_bits(bd, 32);
177 if ((i == 0x177245) && (j == 0x385090))
178 return RETVAL_LAST_BLOCK;
179 if ((i != 0x314159) || (j != 0x265359))
180 return RETVAL_NOT_BZIP_DATA;
181
182
183
184 if (get_bits(bd, 1))
185 return RETVAL_OBSOLETE_INPUT;
186 origPtr = get_bits(bd, 24);
187 if (origPtr > dbufSize)
188 return RETVAL_DATA_ERROR;
189
190
191
192
193
194 t = get_bits(bd, 16);
195 symTotal = 0;
196 for (i = 0; i < 16; i++) {
197 if (t&(1 << (15-i))) {
198 k = get_bits(bd, 16);
199 for (j = 0; j < 16; j++)
200 if (k&(1 << (15-j)))
201 symToByte[symTotal++] = (16*i)+j;
202 }
203 }
204
205 groupCount = get_bits(bd, 3);
206 if (groupCount < 2 || groupCount > MAX_GROUPS)
207 return RETVAL_DATA_ERROR;
208
209
210
211
212
213 nSelectors = get_bits(bd, 15);
214 if (!nSelectors)
215 return RETVAL_DATA_ERROR;
216 for (i = 0; i < groupCount; i++)
217 mtfSymbol[i] = i;
218 for (i = 0; i < nSelectors; i++) {
219
220 for (j = 0; get_bits(bd, 1); j++)
221 if (j >= groupCount)
222 return RETVAL_DATA_ERROR;
223
224 uc = mtfSymbol[j];
225 for (; j; j--)
226 mtfSymbol[j] = mtfSymbol[j-1];
227 mtfSymbol[0] = selectors[i] = uc;
228 }
229
230
231
232 symCount = symTotal+2;
233 for (j = 0; j < groupCount; j++) {
234 unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1];
235 int minLen, maxLen, pp;
236
237
238
239
240
241
242
243
244
245 t = get_bits(bd, 5)-1;
246 for (i = 0; i < symCount; i++) {
247 for (;;) {
248 if (((unsigned)t) > (MAX_HUFCODE_BITS-1))
249 return RETVAL_DATA_ERROR;
250
251
252
253
254
255
256
257 k = get_bits(bd, 2);
258 if (k < 2) {
259 bd->inbufBitCount++;
260 break;
261 }
262
263
264 t += (((k+1)&2)-1);
265 }
266
267
268 length[i] = t+1;
269 }
270
271 minLen = maxLen = length[0];
272
273 for (i = 1; i < symCount; i++) {
274 if (length[i] > maxLen)
275 maxLen = length[i];
276 else if (length[i] < minLen)
277 minLen = length[i];
278 }
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295 hufGroup = bd->groups+j;
296 hufGroup->minLen = minLen;
297 hufGroup->maxLen = maxLen;
298
299
300
301
302 base = hufGroup->base-1;
303 limit = hufGroup->limit-1;
304
305
306 pp = 0;
307 for (i = minLen; i <= maxLen; i++) {
308 temp[i] = limit[i] = 0;
309 for (t = 0; t < symCount; t++)
310 if (length[t] == i)
311 hufGroup->permute[pp++] = t;
312 }
313
314 for (i = 0; i < symCount; i++)
315 temp[length[i]]++;
316
317
318
319
320
321
322 pp = t = 0;
323 for (i = minLen; i < maxLen; i++) {
324 pp += temp[i];
325
326
327
328
329
330
331
332
333
334
335 limit[i] = (pp << (maxLen - i)) - 1;
336 pp <<= 1;
337 base[i+1] = pp-(t += temp[i]);
338 }
339 limit[maxLen+1] = INT_MAX;
340
341 limit[maxLen] = pp+temp[maxLen]-1;
342 base[minLen] = 0;
343 }
344
345
346
347
348
349
350
351 for (i = 0; i < 256; i++) {
352 byteCount[i] = 0;
353 mtfSymbol[i] = (unsigned char)i;
354 }
355
356 runPos = dbufCount = symCount = selector = 0;
357 for (;;) {
358
359 if (!(symCount--)) {
360 symCount = GROUP_SIZE-1;
361 if (selector >= nSelectors)
362 return RETVAL_DATA_ERROR;
363 hufGroup = bd->groups+selectors[selector++];
364 base = hufGroup->base-1;
365 limit = hufGroup->limit-1;
366 }
367
368
369
370
371
372
373
374
375
376
377
378
379 while (bd->inbufBitCount < hufGroup->maxLen) {
380 if (bd->inbufPos == bd->inbufCount) {
381 j = get_bits(bd, hufGroup->maxLen);
382 goto got_huff_bits;
383 }
384 bd->inbufBits =
385 (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
386 bd->inbufBitCount += 8;
387 };
388 bd->inbufBitCount -= hufGroup->maxLen;
389 j = (bd->inbufBits >> bd->inbufBitCount)&
390 ((1 << hufGroup->maxLen)-1);
391got_huff_bits:
392
393
394 i = hufGroup->minLen;
395 while (j > limit[i])
396 ++i;
397 bd->inbufBitCount += (hufGroup->maxLen - i);
398
399 if ((i > hufGroup->maxLen)
400 || (((unsigned)(j = (j>>(hufGroup->maxLen-i))-base[i]))
401 >= MAX_SYMBOLS))
402 return RETVAL_DATA_ERROR;
403 nextSym = hufGroup->permute[j];
404
405
406
407
408
409 if (((unsigned)nextSym) <= SYMBOL_RUNB) {
410
411
412 if (!runPos) {
413 runPos = 1;
414 t = 0;
415 }
416
417
418
419
420
421
422
423
424
425
426 t += (runPos << nextSym);
427
428
429 runPos <<= 1;
430 continue;
431 }
432
433
434
435
436
437
438 if (runPos) {
439 runPos = 0;
440 if (dbufCount+t >= dbufSize)
441 return RETVAL_DATA_ERROR;
442
443 uc = symToByte[mtfSymbol[0]];
444 byteCount[uc] += t;
445 while (t--)
446 dbuf[dbufCount++] = uc;
447 }
448
449 if (nextSym > symTotal)
450 break;
451
452
453
454
455
456
457
458
459
460 if (dbufCount >= dbufSize)
461 return RETVAL_DATA_ERROR;
462 i = nextSym - 1;
463 uc = mtfSymbol[i];
464
465
466
467
468
469 do {
470 mtfSymbol[i] = mtfSymbol[i-1];
471 } while (--i);
472 mtfSymbol[0] = uc;
473 uc = symToByte[uc];
474
475 byteCount[uc]++;
476 dbuf[dbufCount++] = (unsigned int)uc;
477 }
478
479
480
481
482
483
484
485
486 j = 0;
487 for (i = 0; i < 256; i++) {
488 k = j+byteCount[i];
489 byteCount[i] = j;
490 j = k;
491 }
492
493 for (i = 0; i < dbufCount; i++) {
494 uc = (unsigned char)(dbuf[i] & 0xff);
495 dbuf[byteCount[uc]] |= (i << 8);
496 byteCount[uc]++;
497 }
498
499
500
501
502 if (dbufCount) {
503 if (origPtr >= dbufCount)
504 return RETVAL_DATA_ERROR;
505 bd->writePos = dbuf[origPtr];
506 bd->writeCurrent = (unsigned char)(bd->writePos&0xff);
507 bd->writePos >>= 8;
508 bd->writeRunCountdown = 5;
509 }
510 bd->writeCount = dbufCount;
511
512 return RETVAL_OK;
513}
514
515
516
517
518
519
520
521
522static int INIT read_bunzip(struct bunzip_data *bd, char *outbuf, int len)
523{
524 const unsigned int *dbuf;
525 int pos, xcurrent, previous, gotcount;
526
527
528 if (bd->writeCount < 0)
529 return bd->writeCount;
530
531 gotcount = 0;
532 dbuf = bd->dbuf;
533 pos = bd->writePos;
534 xcurrent = bd->writeCurrent;
535
536
537
538
539
540 if (bd->writeCopies) {
541
542 --bd->writeCopies;
543
544 for (;;) {
545
546
547 if (gotcount >= len) {
548 bd->writePos = pos;
549 bd->writeCurrent = xcurrent;
550 bd->writeCopies++;
551 return len;
552 }
553
554 outbuf[gotcount++] = xcurrent;
555 bd->writeCRC = (((bd->writeCRC) << 8)
556 ^bd->crc32Table[((bd->writeCRC) >> 24)
557 ^xcurrent]);
558
559
560 if (bd->writeCopies) {
561 --bd->writeCopies;
562 continue;
563 }
564decode_next_byte:
565 if (!bd->writeCount--)
566 break;
567
568
569 previous = xcurrent;
570 pos = dbuf[pos];
571 xcurrent = pos&0xff;
572 pos >>= 8;
573
574
575
576
577 if (--bd->writeRunCountdown) {
578 if (xcurrent != previous)
579 bd->writeRunCountdown = 4;
580 } else {
581
582
583 bd->writeCopies = xcurrent;
584 xcurrent = previous;
585 bd->writeRunCountdown = 5;
586
587
588 if (!bd->writeCopies)
589 goto decode_next_byte;
590
591
592 --bd->writeCopies;
593 }
594 }
595
596 bd->writeCRC = ~bd->writeCRC;
597 bd->totalCRC = ((bd->totalCRC << 1) |
598 (bd->totalCRC >> 31)) ^ bd->writeCRC;
599
600 if (bd->writeCRC != bd->headerCRC) {
601 bd->totalCRC = bd->headerCRC+1;
602 return RETVAL_LAST_BLOCK;
603 }
604 }
605
606
607
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 = 0xffffffffUL;
615 pos = bd->writePos;
616 xcurrent = bd->writeCurrent;
617 goto decode_next_byte;
618}
619
620static int INIT nofill(void *buf, unsigned int len)
621{
622 return -1;
623}
624
625
626
627
628static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len,
629 int (*fill)(void*, unsigned int))
630{
631 struct bunzip_data *bd;
632 unsigned int i, j, c;
633 const unsigned int BZh0 =
634 (((unsigned int)'B') << 24)+(((unsigned int)'Z') << 16)
635 +(((unsigned int)'h') << 8)+(unsigned int)'0';
636
637
638 i = sizeof(struct bunzip_data);
639
640
641 bd = *bdp = malloc(i);
642 if (!bd)
643 return RETVAL_OUT_OF_MEMORY;
644 memset(bd, 0, sizeof(struct bunzip_data));
645
646 bd->inbuf = inbuf;
647 bd->inbufCount = len;
648 if (fill != NULL)
649 bd->fill = fill;
650 else
651 bd->fill = nofill;
652
653
654 for (i = 0; i < 256; i++) {
655 c = i << 24;
656 for (j = 8; j; j--)
657 c = c&0x80000000 ? (c << 1)^0x04c11db7 : (c << 1);
658 bd->crc32Table[i] = c;
659 }
660
661
662 i = get_bits(bd, 32);
663 if (((unsigned int)(i-BZh0-1)) >= 9)
664 return RETVAL_NOT_BZIP_DATA;
665
666
667
668 bd->dbufSize = 100000*(i-BZh0);
669
670 bd->dbuf = large_malloc(bd->dbufSize * sizeof(int));
671 if (!bd->dbuf)
672 return RETVAL_OUT_OF_MEMORY;
673 return RETVAL_OK;
674}
675
676
677
678STATIC int INIT bunzip2(unsigned char *buf, int len,
679 int(*fill)(void*, unsigned int),
680 int(*flush)(void*, unsigned int),
681 unsigned char *outbuf,
682 int *pos,
683 void(*error)(char *x))
684{
685 struct bunzip_data *bd;
686 int i = -1;
687 unsigned char *inbuf;
688
689 if (flush)
690 outbuf = malloc(BZIP2_IOBUF_SIZE);
691
692 if (!outbuf) {
693 error("Could not allocate output buffer");
694 return RETVAL_OUT_OF_MEMORY;
695 }
696 if (buf)
697 inbuf = buf;
698 else
699 inbuf = malloc(BZIP2_IOBUF_SIZE);
700 if (!inbuf) {
701 error("Could not allocate input buffer");
702 i = RETVAL_OUT_OF_MEMORY;
703 goto exit_0;
704 }
705 i = start_bunzip(&bd, inbuf, len, fill);
706 if (!i) {
707 for (;;) {
708 i = read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE);
709 if (i <= 0)
710 break;
711 if (!flush)
712 outbuf += i;
713 else
714 if (i != flush(outbuf, i)) {
715 i = RETVAL_UNEXPECTED_OUTPUT_EOF;
716 break;
717 }
718 }
719 }
720
721 if (i == RETVAL_LAST_BLOCK) {
722 if (bd->headerCRC != bd->totalCRC)
723 error("Data integrity error when decompressing.");
724 else
725 i = RETVAL_OK;
726 } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) {
727 error("Compressed file ends unexpectedly");
728 }
729 if (!bd)
730 goto exit_1;
731 if (bd->dbuf)
732 large_free(bd->dbuf);
733 if (pos)
734 *pos = bd->inbufPos;
735 free(bd);
736exit_1:
737 if (!buf)
738 free(inbuf);
739exit_0:
740 if (flush)
741 free(outbuf);
742 return i;
743}
744
745#ifdef PREBOOT
746STATIC int INIT decompress(unsigned char *buf, int len,
747 int(*fill)(void*, unsigned int),
748 int(*flush)(void*, unsigned int),
749 unsigned char *outbuf,
750 int *pos,
751 void(*error)(char *x))
752{
753 return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error);
754}
755#endif
756