mkfs: symlink support
[minix.git] / dist / bzip2 / decompress.c
blobaf1d4d09afb9c31f7d2919a08dbc2fb372c7b266
2 /*-------------------------------------------------------------*/
3 /*--- Decompression machinery ---*/
4 /*--- decompress.c ---*/
5 /*-------------------------------------------------------------*/
7 /* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
11 bzip2/libbzip2 version 1.0.5 of 10 December 2007
12 Copyright (C) 1996-2007 Julian Seward <jseward@bzip.org>
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
22 #include "bzlib_private.h"
25 /*---------------------------------------------------*/
26 static
27 void makeMaps_d ( DState* s )
29 Int32 i;
30 s->nInUse = 0;
31 for (i = 0; i < 256; i++)
32 if (s->inUse[i]) {
33 s->seqToUnseq[s->nInUse] = i;
34 s->nInUse++;
39 /*---------------------------------------------------*/
40 #define RETURN(rrr) \
41 { retVal = rrr; goto save_state_and_return; };
43 #define GET_BITS(lll,vvv,nnn) \
44 case lll: s->state = lll; \
45 while (True) { \
46 if (s->bsLive >= nnn) { \
47 UInt32 v; \
48 v = (s->bsBuff >> \
49 (s->bsLive-nnn)) & ((1 << nnn)-1); \
50 s->bsLive -= nnn; \
51 vvv = v; \
52 break; \
53 } \
54 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
55 s->bsBuff \
56 = (s->bsBuff << 8) | \
57 ((UInt32) \
58 (*((UChar*)(s->strm->next_in)))); \
59 s->bsLive += 8; \
60 s->strm->next_in++; \
61 s->strm->avail_in--; \
62 s->strm->total_in_lo32++; \
63 if (s->strm->total_in_lo32 == 0) \
64 s->strm->total_in_hi32++; \
67 #define GET_UCHAR(lll,uuu) \
68 GET_BITS(lll,uuu,8)
70 #define GET_BIT(lll,uuu) \
71 GET_BITS(lll,uuu,1)
73 /*---------------------------------------------------*/
74 #define GET_MTF_VAL(label1,label2,lval) \
75 { \
76 if (groupPos == 0) { \
77 groupNo++; \
78 if (groupNo >= nSelectors) \
79 RETURN(BZ_DATA_ERROR); \
80 groupPos = BZ_G_SIZE; \
81 gSel = s->selector[groupNo]; \
82 gMinlen = s->minLens[gSel]; \
83 gLimit = &(s->limit[gSel][0]); \
84 gPerm = &(s->perm[gSel][0]); \
85 gBase = &(s->base[gSel][0]); \
86 } \
87 groupPos--; \
88 zn = gMinlen; \
89 GET_BITS(label1, zvec, zn); \
90 while (1) { \
91 if (zn > 20 /* the longest code */) \
92 RETURN(BZ_DATA_ERROR); \
93 if (zvec <= gLimit[zn]) break; \
94 zn++; \
95 GET_BIT(label2, zj); \
96 zvec = (zvec << 1) | zj; \
97 }; \
98 if (zvec - gBase[zn] < 0 \
99 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
100 RETURN(BZ_DATA_ERROR); \
101 lval = gPerm[zvec - gBase[zn]]; \
105 /*---------------------------------------------------*/
106 Int32 BZ2_decompress ( DState* s )
108 UChar uc;
109 Int32 retVal;
110 Int32 minLen, maxLen;
111 bz_stream* strm = s->strm;
113 /* stuff that needs to be saved/restored */
114 Int32 i;
115 Int32 j;
116 Int32 t;
117 Int32 alphaSize;
118 Int32 nGroups;
119 Int32 nSelectors;
120 Int32 EOB;
121 Int32 groupNo;
122 Int32 groupPos;
123 Int32 nextSym;
124 Int32 nblockMAX;
125 Int32 nblock;
126 Int32 es;
127 Int32 N;
128 Int32 curr;
129 Int32 zt;
130 Int32 zn;
131 Int32 zvec;
132 Int32 zj;
133 Int32 gSel;
134 Int32 gMinlen;
135 Int32* gLimit;
136 Int32* gBase;
137 Int32* gPerm;
139 if (s->state == BZ_X_MAGIC_1) {
140 /*initialise the save area*/
141 s->save_i = 0;
142 s->save_j = 0;
143 s->save_t = 0;
144 s->save_alphaSize = 0;
145 s->save_nGroups = 0;
146 s->save_nSelectors = 0;
147 s->save_EOB = 0;
148 s->save_groupNo = 0;
149 s->save_groupPos = 0;
150 s->save_nextSym = 0;
151 s->save_nblockMAX = 0;
152 s->save_nblock = 0;
153 s->save_es = 0;
154 s->save_N = 0;
155 s->save_curr = 0;
156 s->save_zt = 0;
157 s->save_zn = 0;
158 s->save_zvec = 0;
159 s->save_zj = 0;
160 s->save_gSel = 0;
161 s->save_gMinlen = 0;
162 s->save_gLimit = NULL;
163 s->save_gBase = NULL;
164 s->save_gPerm = NULL;
167 /*restore from the save area*/
168 i = s->save_i;
169 j = s->save_j;
170 t = s->save_t;
171 alphaSize = s->save_alphaSize;
172 nGroups = s->save_nGroups;
173 nSelectors = s->save_nSelectors;
174 EOB = s->save_EOB;
175 groupNo = s->save_groupNo;
176 groupPos = s->save_groupPos;
177 nextSym = s->save_nextSym;
178 nblockMAX = s->save_nblockMAX;
179 nblock = s->save_nblock;
180 es = s->save_es;
181 N = s->save_N;
182 curr = s->save_curr;
183 zt = s->save_zt;
184 zn = s->save_zn;
185 zvec = s->save_zvec;
186 zj = s->save_zj;
187 gSel = s->save_gSel;
188 gMinlen = s->save_gMinlen;
189 gLimit = s->save_gLimit;
190 gBase = s->save_gBase;
191 gPerm = s->save_gPerm;
193 retVal = BZ_OK;
195 switch (s->state) {
197 GET_UCHAR(BZ_X_MAGIC_1, uc);
198 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
200 GET_UCHAR(BZ_X_MAGIC_2, uc);
201 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
203 GET_UCHAR(BZ_X_MAGIC_3, uc)
204 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
206 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
207 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
208 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
209 s->blockSize100k -= BZ_HDR_0;
211 if (s->smallDecompress) {
212 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
213 s->ll4 = BZALLOC(
214 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
216 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
217 } else {
218 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
219 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
222 GET_UCHAR(BZ_X_BLKHDR_1, uc);
224 if (uc == 0x17) goto endhdr_2;
225 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
226 GET_UCHAR(BZ_X_BLKHDR_2, uc);
227 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
228 GET_UCHAR(BZ_X_BLKHDR_3, uc);
229 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
230 GET_UCHAR(BZ_X_BLKHDR_4, uc);
231 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
232 GET_UCHAR(BZ_X_BLKHDR_5, uc);
233 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
234 GET_UCHAR(BZ_X_BLKHDR_6, uc);
235 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
237 s->currBlockNo++;
238 if (s->verbosity >= 2)
239 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
241 s->storedBlockCRC = 0;
242 GET_UCHAR(BZ_X_BCRC_1, uc);
243 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
244 GET_UCHAR(BZ_X_BCRC_2, uc);
245 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
246 GET_UCHAR(BZ_X_BCRC_3, uc);
247 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
248 GET_UCHAR(BZ_X_BCRC_4, uc);
249 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
251 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
253 s->origPtr = 0;
254 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
255 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
256 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
257 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
258 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
259 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
261 if (s->origPtr < 0)
262 RETURN(BZ_DATA_ERROR);
263 if (s->origPtr > 10 + 100000*s->blockSize100k)
264 RETURN(BZ_DATA_ERROR);
266 /*--- Receive the mapping table ---*/
267 for (i = 0; i < 16; i++) {
268 GET_BIT(BZ_X_MAPPING_1, uc);
269 if (uc == 1)
270 s->inUse16[i] = True; else
271 s->inUse16[i] = False;
274 for (i = 0; i < 256; i++) s->inUse[i] = False;
276 for (i = 0; i < 16; i++)
277 if (s->inUse16[i])
278 for (j = 0; j < 16; j++) {
279 GET_BIT(BZ_X_MAPPING_2, uc);
280 if (uc == 1) s->inUse[i * 16 + j] = True;
282 makeMaps_d ( s );
283 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
284 alphaSize = s->nInUse+2;
286 /*--- Now the selectors ---*/
287 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
288 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
289 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
290 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
291 for (i = 0; i < nSelectors; i++) {
292 j = 0;
293 while (True) {
294 GET_BIT(BZ_X_SELECTOR_3, uc);
295 if (uc == 0) break;
296 j++;
297 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
299 s->selectorMtf[i] = j;
302 /*--- Undo the MTF values for the selectors. ---*/
304 UChar pos[BZ_N_GROUPS], tmp, v;
305 for (v = 0; v < nGroups; v++) pos[v] = v;
307 for (i = 0; i < nSelectors; i++) {
308 v = s->selectorMtf[i];
309 tmp = pos[v];
310 while (v > 0) { pos[v] = pos[v-1]; v--; }
311 pos[0] = tmp;
312 s->selector[i] = tmp;
316 /*--- Now the coding tables ---*/
317 for (t = 0; t < nGroups; t++) {
318 GET_BITS(BZ_X_CODING_1, curr, 5);
319 for (i = 0; i < alphaSize; i++) {
320 while (True) {
321 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
322 GET_BIT(BZ_X_CODING_2, uc);
323 if (uc == 0) break;
324 GET_BIT(BZ_X_CODING_3, uc);
325 if (uc == 0) curr++; else curr--;
327 s->len[t][i] = curr;
331 /*--- Create the Huffman decoding tables ---*/
332 for (t = 0; t < nGroups; t++) {
333 minLen = 32;
334 maxLen = 0;
335 for (i = 0; i < alphaSize; i++) {
336 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
337 if (s->len[t][i] < minLen) minLen = s->len[t][i];
339 BZ2_hbCreateDecodeTables (
340 &(s->limit[t][0]),
341 &(s->base[t][0]),
342 &(s->perm[t][0]),
343 &(s->len[t][0]),
344 minLen, maxLen, alphaSize
346 s->minLens[t] = minLen;
349 /*--- Now the MTF values ---*/
351 EOB = s->nInUse+1;
352 nblockMAX = 100000 * s->blockSize100k;
353 groupNo = -1;
354 groupPos = 0;
356 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
358 /*-- MTF init --*/
360 Int32 ii, jj, kk;
361 kk = MTFA_SIZE-1;
362 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
363 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
364 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
365 kk--;
367 s->mtfbase[ii] = kk + 1;
370 /*-- end MTF init --*/
372 nblock = 0;
373 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
375 while (True) {
377 if (nextSym == EOB) break;
379 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
381 es = -1;
382 N = 1;
383 do {
384 /* Check that N doesn't get too big, so that es doesn't
385 go negative. The maximum value that can be
386 RUNA/RUNB encoded is equal to the block size (post
387 the initial RLE), viz, 900k, so bounding N at 2
388 million should guard against overflow without
389 rejecting any legitimate inputs. */
390 if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
391 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
392 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
393 N = N * 2;
394 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
396 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
398 es++;
399 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
400 s->unzftab[uc] += es;
402 if (s->smallDecompress)
403 while (es > 0) {
404 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
405 s->ll16[nblock] = (UInt16)uc;
406 nblock++;
407 es--;
409 else
410 while (es > 0) {
411 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
412 s->tt[nblock] = (UInt32)uc;
413 nblock++;
414 es--;
417 continue;
419 } else {
421 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
423 /*-- uc = MTF ( nextSym-1 ) --*/
425 Int32 ii, jj, kk, pp, lno, off;
426 UInt32 nn;
427 nn = (UInt32)(nextSym - 1);
429 if (nn < MTFL_SIZE) {
430 /* avoid general-case expense */
431 pp = s->mtfbase[0];
432 uc = s->mtfa[pp+nn];
433 while (nn > 3) {
434 Int32 z = pp+nn;
435 s->mtfa[(z) ] = s->mtfa[(z)-1];
436 s->mtfa[(z)-1] = s->mtfa[(z)-2];
437 s->mtfa[(z)-2] = s->mtfa[(z)-3];
438 s->mtfa[(z)-3] = s->mtfa[(z)-4];
439 nn -= 4;
441 while (nn > 0) {
442 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
444 s->mtfa[pp] = uc;
445 } else {
446 /* general case */
447 lno = nn / MTFL_SIZE;
448 off = nn % MTFL_SIZE;
449 pp = s->mtfbase[lno] + off;
450 uc = s->mtfa[pp];
451 while (pp > s->mtfbase[lno]) {
452 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
454 s->mtfbase[lno]++;
455 while (lno > 0) {
456 s->mtfbase[lno]--;
457 s->mtfa[s->mtfbase[lno]]
458 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
459 lno--;
461 s->mtfbase[0]--;
462 s->mtfa[s->mtfbase[0]] = uc;
463 if (s->mtfbase[0] == 0) {
464 kk = MTFA_SIZE-1;
465 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
466 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
467 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
468 kk--;
470 s->mtfbase[ii] = kk + 1;
475 /*-- end uc = MTF ( nextSym-1 ) --*/
477 s->unzftab[s->seqToUnseq[uc]]++;
478 if (s->smallDecompress)
479 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
480 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
481 nblock++;
483 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
484 continue;
488 /* Now we know what nblock is, we can do a better sanity
489 check on s->origPtr.
491 if (s->origPtr < 0 || s->origPtr >= nblock)
492 RETURN(BZ_DATA_ERROR);
494 /*-- Set up cftab to facilitate generation of T^(-1) --*/
495 s->cftab[0] = 0;
496 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
497 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
498 for (i = 0; i <= 256; i++) {
499 if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
500 /* s->cftab[i] can legitimately be == nblock */
501 RETURN(BZ_DATA_ERROR);
505 s->state_out_len = 0;
506 s->state_out_ch = 0;
507 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
508 s->state = BZ_X_OUTPUT;
509 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
511 if (s->smallDecompress) {
513 /*-- Make a copy of cftab, used in generation of T --*/
514 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
516 /*-- compute the T vector --*/
517 for (i = 0; i < nblock; i++) {
518 uc = (UChar)(s->ll16[i]);
519 SET_LL(i, s->cftabCopy[uc]);
520 s->cftabCopy[uc]++;
523 /*-- Compute T^(-1) by pointer reversal on T --*/
524 i = s->origPtr;
525 j = GET_LL(i);
526 do {
527 Int32 tmp = GET_LL(j);
528 SET_LL(j, i);
529 i = j;
530 j = tmp;
532 while (i != s->origPtr);
534 s->tPos = s->origPtr;
535 s->nblock_used = 0;
536 if (s->blockRandomised) {
537 BZ_RAND_INIT_MASK;
538 BZ_GET_SMALL(s->k0); s->nblock_used++;
539 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
540 } else {
541 BZ_GET_SMALL(s->k0); s->nblock_used++;
544 } else {
546 /*-- compute the T^(-1) vector --*/
547 for (i = 0; i < nblock; i++) {
548 uc = (UChar)(s->tt[i] & 0xff);
549 s->tt[s->cftab[uc]] |= (i << 8);
550 s->cftab[uc]++;
553 s->tPos = s->tt[s->origPtr] >> 8;
554 s->nblock_used = 0;
555 if (s->blockRandomised) {
556 BZ_RAND_INIT_MASK;
557 BZ_GET_FAST(s->k0); s->nblock_used++;
558 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
559 } else {
560 BZ_GET_FAST(s->k0); s->nblock_used++;
565 RETURN(BZ_OK);
569 endhdr_2:
571 GET_UCHAR(BZ_X_ENDHDR_2, uc);
572 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
573 GET_UCHAR(BZ_X_ENDHDR_3, uc);
574 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
575 GET_UCHAR(BZ_X_ENDHDR_4, uc);
576 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
577 GET_UCHAR(BZ_X_ENDHDR_5, uc);
578 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
579 GET_UCHAR(BZ_X_ENDHDR_6, uc);
580 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
582 s->storedCombinedCRC = 0;
583 GET_UCHAR(BZ_X_CCRC_1, uc);
584 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
585 GET_UCHAR(BZ_X_CCRC_2, uc);
586 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
587 GET_UCHAR(BZ_X_CCRC_3, uc);
588 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
589 GET_UCHAR(BZ_X_CCRC_4, uc);
590 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
592 s->state = BZ_X_IDLE;
593 RETURN(BZ_STREAM_END);
595 default: AssertH ( False, 4001 );
598 AssertH ( False, 4002 );
600 save_state_and_return:
602 s->save_i = i;
603 s->save_j = j;
604 s->save_t = t;
605 s->save_alphaSize = alphaSize;
606 s->save_nGroups = nGroups;
607 s->save_nSelectors = nSelectors;
608 s->save_EOB = EOB;
609 s->save_groupNo = groupNo;
610 s->save_groupPos = groupPos;
611 s->save_nextSym = nextSym;
612 s->save_nblockMAX = nblockMAX;
613 s->save_nblock = nblock;
614 s->save_es = es;
615 s->save_N = N;
616 s->save_curr = curr;
617 s->save_zt = zt;
618 s->save_zn = zn;
619 s->save_zvec = zvec;
620 s->save_zj = zj;
621 s->save_gSel = gSel;
622 s->save_gMinlen = gMinlen;
623 s->save_gLimit = gLimit;
624 s->save_gBase = gBase;
625 s->save_gPerm = gPerm;
627 return retVal;
631 /*-------------------------------------------------------------*/
632 /*--- end decompress.c ---*/
633 /*-------------------------------------------------------------*/