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