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#define FOR_bunzip2
42#include "toys.h"
43
44#define THREADS 1
45
46
47#define MAX_GROUPS 6
48#define GROUP_SIZE 50
49#define MAX_HUFCODE_BITS 20
50#define MAX_SYMBOLS 258
51#define SYMBOL_RUNA 0
52#define SYMBOL_RUNB 1
53
54
55#define IOBUF_SIZE 4096
56
57
58#define RETVAL_LAST_BLOCK (-100)
59#define RETVAL_NOT_BZIP_DATA (-1)
60#define RETVAL_DATA_ERROR (-2)
61#define RETVAL_OBSOLETE_INPUT (-3)
62
63
64struct group_data {
65 int limit[MAX_HUFCODE_BITS+1], base[MAX_HUFCODE_BITS], permute[MAX_SYMBOLS];
66 char minLen, maxLen;
67};
68
69
70
71struct bwdata {
72 unsigned int origPtr;
73 int byteCount[256];
74
75 int writePos, writeRun, writeCount, writeCurrent;
76 unsigned int dataCRC, headerCRC;
77 unsigned int *dbuf;
78};
79
80
81
82struct bunzip_data {
83
84 int in_fd, inbufCount, inbufPos;
85 char *inbuf;
86 unsigned int inbufBitCount, inbufBits;
87
88
89 char outbuf[IOBUF_SIZE];
90 int outbufPos;
91
92 unsigned int totalCRC;
93
94
95 char selectors[32768];
96 struct group_data groups[MAX_GROUPS];
97 int symTotal, groupCount, nSelectors;
98 unsigned char symToByte[256], mtfSymbol[256];
99
100
101 unsigned int crc32Table[256];
102
103
104 unsigned int dbufSize;
105 struct bwdata bwdata[THREADS];
106};
107
108
109
110static unsigned int get_bits(struct bunzip_data *bd, char bits_wanted)
111{
112 unsigned int bits = 0;
113
114
115
116 while (bd->inbufBitCount < bits_wanted) {
117
118
119 if (bd->inbufPos == bd->inbufCount) {
120 if (0 >= (bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE)))
121 error_exit("input EOF");
122 bd->inbufPos = 0;
123 }
124
125
126 if (bd->inbufBitCount>=24) {
127 bits = bd->inbufBits&((1<<bd->inbufBitCount)-1);
128 bits_wanted -= bd->inbufBitCount;
129 bits <<= bits_wanted;
130 bd->inbufBitCount = 0;
131 }
132
133
134 bd->inbufBits = (bd->inbufBits<<8) | bd->inbuf[bd->inbufPos++];
135 bd->inbufBitCount += 8;
136 }
137
138
139 bd->inbufBitCount -= bits_wanted;
140 bits |= (bd->inbufBits>>bd->inbufBitCount) & ((1<<bits_wanted)-1);
141
142 return bits;
143}
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161static int read_block_header(struct bunzip_data *bd, struct bwdata *bw)
162{
163 struct group_data *hufGroup;
164 int hh, ii, jj, kk, symCount, *base, *limit;
165 unsigned char uc;
166
167
168 ii = get_bits(bd, 24);
169 jj = get_bits(bd, 24);
170 bw->headerCRC = get_bits(bd,32);
171
172
173 if (ii==0x177245 && jj==0x385090) return RETVAL_LAST_BLOCK;
174
175
176 if (ii!=0x314159 || jj!=0x265359) return RETVAL_NOT_BZIP_DATA;
177
178
179 if (get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT;
180 if ((bw->origPtr = get_bits(bd,24)) > bd->dbufSize) return RETVAL_DATA_ERROR;
181
182
183
184
185
186
187 hh = get_bits(bd, 16);
188 bd->symTotal = 0;
189 for (ii=0; ii<16; ii++) {
190 if (hh & (1 << (15 - ii))) {
191 kk = get_bits(bd, 16);
192 for (jj=0; jj<16; jj++)
193 if (kk & (1 << (15 - jj)))
194 bd->symToByte[bd->symTotal++] = (16 * ii) + jj;
195 }
196 }
197
198
199 bd->groupCount = get_bits(bd,3);
200 if (bd->groupCount<2 || bd->groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR;
201
202
203
204
205
206
207
208
209 if (!(bd->nSelectors = get_bits(bd, 15))) return RETVAL_DATA_ERROR;
210 for (ii=0; ii<bd->groupCount; ii++) bd->mtfSymbol[ii] = ii;
211 for (ii=0; ii<bd->nSelectors; ii++) {
212
213
214 for(jj=0;get_bits(bd,1);jj++)
215 if (jj>=bd->groupCount) return RETVAL_DATA_ERROR;
216
217
218 uc = bd->mtfSymbol[jj];
219 memmove(bd->mtfSymbol+1, bd->mtfSymbol, jj);
220 bd->mtfSymbol[0] = bd->selectors[ii] = uc;
221 }
222
223
224
225 symCount = bd->symTotal+2;
226 for (jj=0; jj<bd->groupCount; jj++) {
227 unsigned char length[MAX_SYMBOLS];
228 unsigned temp[MAX_HUFCODE_BITS+1];
229 int minLen, maxLen, pp;
230
231
232 hh = get_bits(bd, 5);
233 for (ii = 0; ii < symCount; ii++) {
234 for(;;) {
235
236 if (MAX_HUFCODE_BITS-1 < (unsigned)hh-1) return RETVAL_DATA_ERROR;
237
238
239
240 kk = get_bits(bd, 2);
241 if (kk & 2) hh += 1 - ((kk&1)<<1);
242 else {
243 bd->inbufBitCount++;
244 break;
245 }
246 }
247 length[ii] = hh;
248 }
249
250
251 minLen = maxLen = length[0];
252 for (ii = 1; ii < symCount; ii++) {
253 if(length[ii] > maxLen) maxLen = length[ii];
254 else if(length[ii] < minLen) minLen = length[ii];
255 }
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272 hufGroup = bd->groups+jj;
273 hufGroup->minLen = minLen;
274 hufGroup->maxLen = maxLen;
275
276
277
278
279 base = hufGroup->base-1;
280 limit = hufGroup->limit-1;
281
282
283 pp = 0;
284 for (ii = minLen; ii <= maxLen; ii++) {
285 temp[ii] = limit[ii] = 0;
286 for (hh = 0; hh < symCount; hh++)
287 if (length[hh] == ii) hufGroup->permute[pp++] = hh;
288 }
289
290
291 for (ii = 0; ii < symCount; ii++) temp[length[ii]]++;
292
293
294
295
296
297 pp = hh = 0;
298 for (ii = minLen; ii < maxLen; ii++) {
299 pp += temp[ii];
300 limit[ii] = pp-1;
301 pp <<= 1;
302 base[ii+1] = pp-(hh+=temp[ii]);
303 }
304 limit[maxLen] = pp+temp[maxLen]-1;
305 limit[maxLen+1] = INT_MAX;
306 base[minLen] = 0;
307 }
308
309 return 0;
310}
311
312
313
314
315
316
317
318
319static int read_huffman_data(struct bunzip_data *bd, struct bwdata *bw)
320{
321 struct group_data *hufGroup;
322 int ii, jj, kk, runPos, dbufCount, symCount, selector, nextSym,
323 *byteCount, *base, *limit;
324 unsigned hh, *dbuf = bw->dbuf;
325 unsigned char uc;
326
327
328
329
330
331
332 byteCount = bw->byteCount;
333 for(ii=0; ii<256; ii++) {
334 byteCount[ii] = 0;
335 bd->mtfSymbol[ii] = ii;
336 }
337
338
339
340
341 runPos = dbufCount = symCount = selector = 0;
342
343 base = limit = 0;
344 hufGroup = 0;
345 hh = 0;
346
347 for (;;) {
348
349 if (!(symCount--)) {
350
351 symCount = GROUP_SIZE-1;
352 if (selector >= bd->nSelectors) return RETVAL_DATA_ERROR;
353 hufGroup = bd->groups + bd->selectors[selector++];
354 base = hufGroup->base-1;
355 limit = hufGroup->limit-1;
356 }
357
358
359 ii = hufGroup->minLen;
360 jj = get_bits(bd, ii);
361 while (jj > limit[ii]) {
362
363 ii++;
364
365
366
367 kk = bd->inbufBitCount
368 ? (bd->inbufBits >> --(bd->inbufBitCount)) & 1 : get_bits(bd, 1);
369 jj = (jj << 1) | kk;
370 }
371
372 jj-=base[ii];
373
374 if (ii > hufGroup->maxLen || (unsigned)jj >= MAX_SYMBOLS)
375 return RETVAL_DATA_ERROR;
376 nextSym = hufGroup->permute[jj];
377
378
379 if ((unsigned)nextSym <= SYMBOL_RUNB) {
380
381 if(!runPos) {
382 runPos = 1;
383 hh = 0;
384 }
385
386
387
388
389
390
391
392
393 hh += (runPos << nextSym);
394 runPos <<= 1;
395 continue;
396 }
397
398
399
400
401
402 if (runPos) {
403 runPos = 0;
404
405 if (hh>bd->dbufSize || dbufCount+hh>bd->dbufSize)
406 return RETVAL_DATA_ERROR;
407
408 uc = bd->symToByte[bd->mtfSymbol[0]];
409 byteCount[uc] += hh;
410 while (hh--) dbuf[dbufCount++] = uc;
411 }
412
413
414 if (nextSym>bd->symTotal) break;
415
416
417
418
419
420
421
422 if (dbufCount>=bd->dbufSize) return RETVAL_DATA_ERROR;
423 ii = nextSym - 1;
424 uc = bd->mtfSymbol[ii];
425
426
427 while(ii--) bd->mtfSymbol[ii+1] = bd->mtfSymbol[ii];
428 bd->mtfSymbol[0] = uc;
429 uc = bd->symToByte[uc];
430
431
432 byteCount[uc]++;
433 dbuf[dbufCount++] = (unsigned int)uc;
434 }
435
436
437 if (bw->origPtr >= (bw->writeCount = dbufCount)) return RETVAL_DATA_ERROR;
438
439 return 0;
440}
441
442
443static void flush_bunzip_outbuf(struct bunzip_data *bd, int out_fd)
444{
445 if (bd->outbufPos) {
446 if (write(out_fd, bd->outbuf, bd->outbufPos) != bd->outbufPos)
447 error_exit("output EOF");
448 bd->outbufPos = 0;
449 }
450}
451
452static void burrows_wheeler_prep(struct bunzip_data *bd, struct bwdata *bw)
453{
454 int ii, jj;
455 unsigned int *dbuf = bw->dbuf;
456 int *byteCount = bw->byteCount;
457
458
459 jj = 0;
460 for (ii=0; ii<256; ii++) {
461 int kk = jj + byteCount[ii];
462 byteCount[ii] = jj;
463 jj = kk;
464 }
465
466
467
468 for (ii=0; ii < bw->writeCount; ii++) {
469 unsigned char uc = dbuf[ii];
470 dbuf[byteCount[uc]] |= (ii << 8);
471 byteCount[uc]++;
472 }
473
474
475
476
477
478 bw->dataCRC = 0xffffffffL;
479
480
481
482
483
484 if (bw->writeCount) {
485 bw->writePos = dbuf[bw->origPtr];
486 bw->writeCurrent = (unsigned char)bw->writePos;
487 bw->writePos >>= 8;
488 bw->writeRun = -1;
489 }
490}
491
492
493static int read_bunzip_data(struct bunzip_data *bd)
494{
495 int rc = read_block_header(bd, bd->bwdata);
496 if (!rc) rc=read_huffman_data(bd, bd->bwdata);
497
498
499 burrows_wheeler_prep(bd, bd->bwdata);
500
501 return rc;
502}
503
504
505
506
507
508
509
510
511
512static int write_bunzip_data(struct bunzip_data *bd, struct bwdata *bw,
513 int out_fd, char *outbuf, int len)
514{
515 unsigned int *dbuf = bw->dbuf;
516 int count, pos, current, run, copies, outbyte, previous, gotcount = 0;
517
518 for (;;) {
519
520 if (bw->writeCount < 0) return bw->writeCount;
521
522
523 if (!bw->writeCount) {
524 int i = read_bunzip_data(bd);
525 if (i) {
526 if (i == RETVAL_LAST_BLOCK) {
527 bw->writeCount = i;
528 return gotcount;
529 } else return i;
530 }
531 }
532
533
534 count = bw->writeCount;
535 pos = bw->writePos;
536 current = bw->writeCurrent;
537 run = bw->writeRun;
538 while (count) {
539
540
541
542 if (len && bd->outbufPos >= len) goto dataus_interruptus;
543 count--;
544
545
546 previous = current;
547 pos = dbuf[pos];
548 current = pos&0xff;
549 pos >>= 8;
550
551
552
553 if (run++ == 3) {
554 copies = current;
555 outbyte = previous;
556 current = -1;
557 } else {
558 copies = 1;
559 outbyte = current;
560 }
561
562
563 while (copies--) {
564 if (bd->outbufPos == IOBUF_SIZE) flush_bunzip_outbuf(bd, out_fd);
565 bd->outbuf[bd->outbufPos++] = outbyte;
566 bw->dataCRC = (bw->dataCRC << 8)
567 ^ bd->crc32Table[(bw->dataCRC >> 24) ^ outbyte];
568 }
569 if (current != previous) run=0;
570 }
571
572
573 bw->dataCRC = ~(bw->dataCRC);
574 bd->totalCRC = ((bd->totalCRC << 1) | (bd->totalCRC >> 31)) ^ bw->dataCRC;
575
576
577 if (bw->dataCRC != bw->headerCRC) {
578 bd->totalCRC = bw->headerCRC+1;
579
580 return RETVAL_LAST_BLOCK;
581 }
582dataus_interruptus:
583 bw->writeCount = count;
584 if (len) {
585 gotcount += bd->outbufPos;
586 memcpy(outbuf, bd->outbuf, len);
587
588
589 if ((len -= bd->outbufPos)<1) {
590 bd->outbufPos -= len;
591 if (bd->outbufPos) memmove(bd->outbuf, bd->outbuf+len, bd->outbufPos);
592 bw->writePos = pos;
593 bw->writeCurrent = current;
594 bw->writeRun = run;
595
596 return gotcount;
597 }
598 }
599 }
600}
601
602
603
604static int start_bunzip(struct bunzip_data **bdp, int src_fd, char *inbuf,
605 int len)
606{
607 struct bunzip_data *bd;
608 unsigned int i;
609
610
611 i = sizeof(struct bunzip_data);
612 if (!len) i += IOBUF_SIZE;
613
614
615 bd = *bdp = xzalloc(i);
616 if (len) {
617 bd->inbuf = inbuf;
618 bd->inbufCount = len;
619 bd->in_fd = -1;
620 } else {
621 bd->inbuf = (char *)(bd+1);
622 bd->in_fd = src_fd;
623 }
624
625 crc_init(bd->crc32Table, 0);
626
627
628 for (i=0;i<3;i++) if (get_bits(bd,8)!="BZh"[i]) return RETVAL_NOT_BZIP_DATA;
629
630
631
632 i = get_bits(bd, 8);
633 if (i<'1' || i>'9') return RETVAL_NOT_BZIP_DATA;
634 bd->dbufSize = 100000*(i-'0')*THREADS;
635 for (i=0; i<THREADS; i++)
636 bd->bwdata[i].dbuf = xmalloc(bd->dbufSize * sizeof(int));
637
638 return 0;
639}
640
641
642
643static char *bunzipStream(int src_fd, int dst_fd)
644{
645 struct bunzip_data *bd;
646 char *bunzip_errors[] = {0, "not bzip", "bad data", "old format"};
647 int i, j;
648
649 if (!(i = start_bunzip(&bd,src_fd, 0, 0))) {
650 i = write_bunzip_data(bd,bd->bwdata, dst_fd, 0, 0);
651 if (i==RETVAL_LAST_BLOCK) {
652 if (bd->bwdata[0].headerCRC==bd->totalCRC) i = 0;
653 else i = RETVAL_DATA_ERROR;
654 }
655 }
656 flush_bunzip_outbuf(bd, dst_fd);
657
658 for (j=0; j<THREADS; j++) free(bd->bwdata[j].dbuf);
659 free(bd);
660
661 return bunzip_errors[-i];
662}
663
664static void do_bzcat(int fd, char *name)
665{
666 char *err = bunzipStream(fd, 1);
667
668 if (err) error_exit_raw(err);
669}
670
671void bzcat_main(void)
672{
673 loopfiles(toys.optargs, do_bzcat);
674}
675
676static void do_bunzip2(int fd, char *name)
677{
678 int outfd = 1, rename = 0, len = strlen(name);
679 char *tmp, *err, *dotbz = 0;
680
681
682 dotbz = name+len-3;
683 if ((len>3 && !strcmp(dotbz, ".bz")) || (len>4 && !strcmp(--dotbz, ".bz2")))
684 dotbz = 0;
685
686
687 if (toys.optflags&FLAG_t) outfd = xopen("/dev/null", O_WRONLY);
688 else if ((fd || strcmp(name, "-")) && !(toys.optflags&FLAG_c)) {
689 if (toys.optflags&FLAG_k) {
690 if (!dotbz || !access(name, X_OK)) {
691 error_msg("%s exists", name);
692
693 return;
694 }
695 }
696 outfd = copy_tempfile(fd, name, &tmp);
697 rename++;
698 }
699
700 if (toys.optflags&FLAG_v) printf("%s:", name);
701 err = bunzipStream(fd, outfd);
702 if (toys.optflags&FLAG_v) {
703 printf("%s\n", err ? err : "ok");
704 toys.exitval |= !!err;
705 } else if (err) error_msg_raw(err);
706
707
708 if (rename) {
709 if (toys.optflags&FLAG_k) {
710 free(tmp);
711 tmp = 0;
712 } else {
713 if (dotbz) *dotbz = '.';
714 if (!unlink(name)) perror_msg_raw(name);
715 }
716 (err ? delete_tempfile : replace_tempfile)(-1, outfd, &tmp);
717 }
718}
719
720void bunzip2_main(void)
721{
722 loopfiles(toys.optargs, do_bunzip2);
723}
724