Remove building with NOCRYPTO option
[minix.git] / external / bsd / bzip2 / dist / decompress.c
blob821f809c7497d0f9cf5cc17f272cefc7776a338c
1 /* $NetBSD: decompress.c,v 1.3 2012/05/07 00:45:48 wiz Exp $ */
4 /*-------------------------------------------------------------*/
5 /*--- Decompression machinery ---*/
6 /*--- decompress.c ---*/
7 /*-------------------------------------------------------------*/
9 /* ------------------------------------------------------------------
10 This file is part of bzip2/libbzip2, a program and library for
11 lossless, block-sorting data compression.
13 bzip2/libbzip2 version 1.0.6 of 6 September 2010
14 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
16 Please read the WARNING, DISCLAIMER and PATENTS sections in the
17 README file.
19 This program is released under the terms of the license contained
20 in the file LICENSE.
21 ------------------------------------------------------------------ */
24 #include "bzlib_private.h"
27 /*---------------------------------------------------*/
28 static
29 void makeMaps_d ( DState* s )
31 Int32 i;
32 s->nInUse = 0;
33 for (i = 0; i < 256; i++)
34 if (s->inUse[i]) {
35 s->seqToUnseq[s->nInUse] = i;
36 s->nInUse++;
41 /*---------------------------------------------------*/
42 #define RETURN(rrr) \
43 { retVal = rrr; goto save_state_and_return; };
45 #define GET_BITS(lll,vvv,nnn) \
46 case lll: s->state = lll; \
47 while (True) { \
48 if (s->bsLive >= nnn) { \
49 UInt32 v; \
50 v = (s->bsBuff >> \
51 (s->bsLive-nnn)) & ((1 << nnn)-1); \
52 s->bsLive -= nnn; \
53 vvv = v; \
54 break; \
55 } \
56 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
57 s->bsBuff \
58 = (s->bsBuff << 8) | \
59 ((UInt32) \
60 (*((UChar*)(s->strm->next_in)))); \
61 s->bsLive += 8; \
62 s->strm->next_in++; \
63 s->strm->avail_in--; \
64 s->strm->total_in_lo32++; \
65 if (s->strm->total_in_lo32 == 0) \
66 s->strm->total_in_hi32++; \
69 #define GET_UCHAR(lll,uuu) \
70 GET_BITS(lll,uuu,8)
72 #define GET_BIT(lll,uuu) \
73 GET_BITS(lll,uuu,1)
75 /*---------------------------------------------------*/
76 #define GET_MTF_VAL(label1,label2,lval) \
77 { \
78 if (groupPos == 0) { \
79 groupNo++; \
80 if (groupNo >= nSelectors) \
81 RETURN(BZ_DATA_ERROR); \
82 groupPos = BZ_G_SIZE; \
83 gSel = s->selector[groupNo]; \
84 gMinlen = s->minLens[gSel]; \
85 gLimit = &(s->limit[gSel][0]); \
86 gPerm = &(s->perm[gSel][0]); \
87 gBase = &(s->base[gSel][0]); \
88 } \
89 groupPos--; \
90 zn = gMinlen; \
91 GET_BITS(label1, zvec, zn); \
92 while (1) { \
93 if (zn > 20 /* the longest code */) \
94 RETURN(BZ_DATA_ERROR); \
95 if (zvec <= gLimit[zn]) break; \
96 zn++; \
97 GET_BIT(label2, zj); \
98 zvec = (zvec << 1) | zj; \
99 }; \
100 if (zvec - gBase[zn] < 0 \
101 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
102 RETURN(BZ_DATA_ERROR); \
103 lval = gPerm[zvec - gBase[zn]]; \
107 /*---------------------------------------------------*/
108 Int32 BZ2_decompress ( DState* s )
110 UChar uc;
111 Int32 retVal;
112 Int32 minLen, maxLen;
113 bz_stream* strm = s->strm;
115 /* stuff that needs to be saved/restored */
116 Int32 i;
117 Int32 j;
118 Int32 t;
119 Int32 alphaSize;
120 Int32 nGroups;
121 Int32 nSelectors;
122 Int32 EOB;
123 Int32 groupNo;
124 Int32 groupPos;
125 Int32 nextSym;
126 Int32 nblockMAX;
127 Int32 nblock;
128 Int32 es;
129 Int32 N;
130 Int32 curr;
131 Int32 zt;
132 Int32 zn;
133 Int32 zvec;
134 Int32 zj;
135 Int32 gSel;
136 Int32 gMinlen;
137 Int32* gLimit;
138 Int32* gBase;
139 Int32* gPerm;
141 if (s->state == BZ_X_MAGIC_1) {
142 /*initialise the save area*/
143 s->save_i = 0;
144 s->save_j = 0;
145 s->save_t = 0;
146 s->save_alphaSize = 0;
147 s->save_nGroups = 0;
148 s->save_nSelectors = 0;
149 s->save_EOB = 0;
150 s->save_groupNo = 0;
151 s->save_groupPos = 0;
152 s->save_nextSym = 0;
153 s->save_nblockMAX = 0;
154 s->save_nblock = 0;
155 s->save_es = 0;
156 s->save_N = 0;
157 s->save_curr = 0;
158 s->save_zt = 0;
159 s->save_zn = 0;
160 s->save_zvec = 0;
161 s->save_zj = 0;
162 s->save_gSel = 0;
163 s->save_gMinlen = 0;
164 s->save_gLimit = NULL;
165 s->save_gBase = NULL;
166 s->save_gPerm = NULL;
169 /*restore from the save area*/
170 i = s->save_i;
171 j = s->save_j;
172 t = s->save_t;
173 alphaSize = s->save_alphaSize;
174 nGroups = s->save_nGroups;
175 nSelectors = s->save_nSelectors;
176 EOB = s->save_EOB;
177 groupNo = s->save_groupNo;
178 groupPos = s->save_groupPos;
179 nextSym = s->save_nextSym;
180 nblockMAX = s->save_nblockMAX;
181 nblock = s->save_nblock;
182 es = s->save_es;
183 N = s->save_N;
184 curr = s->save_curr;
185 zt = s->save_zt;
186 zn = s->save_zn;
187 zvec = s->save_zvec;
188 zj = s->save_zj;
189 gSel = s->save_gSel;
190 gMinlen = s->save_gMinlen;
191 gLimit = s->save_gLimit;
192 gBase = s->save_gBase;
193 gPerm = s->save_gPerm;
195 retVal = BZ_OK;
197 switch (s->state) {
199 GET_UCHAR(BZ_X_MAGIC_1, uc);
200 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
202 GET_UCHAR(BZ_X_MAGIC_2, uc);
203 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
205 GET_UCHAR(BZ_X_MAGIC_3, uc)
206 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
208 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
209 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
210 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
211 s->blockSize100k -= BZ_HDR_0;
213 if (s->smallDecompress) {
214 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
215 s->ll4 = BZALLOC(
216 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
218 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
219 } else {
220 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
221 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
224 GET_UCHAR(BZ_X_BLKHDR_1, uc);
226 if (uc == 0x17) goto endhdr_2;
227 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
228 GET_UCHAR(BZ_X_BLKHDR_2, uc);
229 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
230 GET_UCHAR(BZ_X_BLKHDR_3, uc);
231 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
232 GET_UCHAR(BZ_X_BLKHDR_4, uc);
233 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
234 GET_UCHAR(BZ_X_BLKHDR_5, uc);
235 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
236 GET_UCHAR(BZ_X_BLKHDR_6, uc);
237 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
239 s->currBlockNo++;
240 if (s->verbosity >= 2)
241 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
243 s->storedBlockCRC = 0;
244 GET_UCHAR(BZ_X_BCRC_1, uc);
245 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
246 GET_UCHAR(BZ_X_BCRC_2, uc);
247 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
248 GET_UCHAR(BZ_X_BCRC_3, uc);
249 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
250 GET_UCHAR(BZ_X_BCRC_4, uc);
251 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
253 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
255 s->origPtr = 0;
256 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
257 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
258 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
259 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
260 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
261 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
263 if (s->origPtr < 0)
264 RETURN(BZ_DATA_ERROR);
265 if (s->origPtr > 10 + 100000*s->blockSize100k)
266 RETURN(BZ_DATA_ERROR);
268 /*--- Receive the mapping table ---*/
269 for (i = 0; i < 16; i++) {
270 GET_BIT(BZ_X_MAPPING_1, uc);
271 if (uc == 1)
272 s->inUse16[i] = True; else
273 s->inUse16[i] = False;
276 for (i = 0; i < 256; i++) s->inUse[i] = False;
278 for (i = 0; i < 16; i++)
279 if (s->inUse16[i])
280 for (j = 0; j < 16; j++) {
281 GET_BIT(BZ_X_MAPPING_2, uc);
282 if (uc == 1) s->inUse[i * 16 + j] = True;
284 makeMaps_d ( s );
285 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
286 alphaSize = s->nInUse+2;
288 /*--- Now the selectors ---*/
289 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
290 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
291 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
292 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
293 for (i = 0; i < nSelectors; i++) {
294 j = 0;
295 while (True) {
296 GET_BIT(BZ_X_SELECTOR_3, uc);
297 if (uc == 0) break;
298 j++;
299 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
301 s->selectorMtf[i] = j;
304 /*--- Undo the MTF values for the selectors. ---*/
306 UChar pos[BZ_N_GROUPS], tmp, v;
307 for (v = 0; v < nGroups; v++) pos[v] = v;
309 for (i = 0; i < nSelectors; i++) {
310 v = s->selectorMtf[i];
311 tmp = pos[v];
312 while (v > 0) { pos[v] = pos[v-1]; v--; }
313 pos[0] = tmp;
314 s->selector[i] = tmp;
318 /*--- Now the coding tables ---*/
319 for (t = 0; t < nGroups; t++) {
320 GET_BITS(BZ_X_CODING_1, curr, 5);
321 for (i = 0; i < alphaSize; i++) {
322 while (True) {
323 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
324 GET_BIT(BZ_X_CODING_2, uc);
325 if (uc == 0) break;
326 GET_BIT(BZ_X_CODING_3, uc);
327 if (uc == 0) curr++; else curr--;
329 s->len[t][i] = curr;
333 /*--- Create the Huffman decoding tables ---*/
334 for (t = 0; t < nGroups; t++) {
335 minLen = 32;
336 maxLen = 0;
337 for (i = 0; i < alphaSize; i++) {
338 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
339 if (s->len[t][i] < minLen) minLen = s->len[t][i];
341 BZ2_hbCreateDecodeTables (
342 &(s->limit[t][0]),
343 &(s->base[t][0]),
344 &(s->perm[t][0]),
345 &(s->len[t][0]),
346 minLen, maxLen, alphaSize
348 s->minLens[t] = minLen;
351 /*--- Now the MTF values ---*/
353 EOB = s->nInUse+1;
354 nblockMAX = 100000 * s->blockSize100k;
355 groupNo = -1;
356 groupPos = 0;
358 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
360 /*-- MTF init --*/
362 Int32 ii, jj, kk;
363 kk = MTFA_SIZE-1;
364 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
365 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
366 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
367 kk--;
369 s->mtfbase[ii] = kk + 1;
372 /*-- end MTF init --*/
374 nblock = 0;
375 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
377 while (True) {
379 if (nextSym == EOB) break;
381 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
383 es = -1;
384 N = 1;
385 do {
386 /* Check that N doesn't get too big, so that es doesn't
387 go negative. The maximum value that can be
388 RUNA/RUNB encoded is equal to the block size (post
389 the initial RLE), viz, 900k, so bounding N at 2
390 million should guard against overflow without
391 rejecting any legitimate inputs. */
392 if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
393 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
394 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
395 N = N * 2;
396 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
398 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
400 es++;
401 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
402 s->unzftab[uc] += es;
404 if (s->smallDecompress)
405 while (es > 0) {
406 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
407 s->ll16[nblock] = (UInt16)uc;
408 nblock++;
409 es--;
411 else
412 while (es > 0) {
413 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
414 s->tt[nblock] = (UInt32)uc;
415 nblock++;
416 es--;
419 continue;
421 } else {
423 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
425 /*-- uc = MTF ( nextSym-1 ) --*/
427 Int32 ii, jj, kk, pp, lno, off;
428 UInt32 nn;
429 nn = (UInt32)(nextSym - 1);
431 if (nn < MTFL_SIZE) {
432 /* avoid general-case expense */
433 pp = s->mtfbase[0];
434 uc = s->mtfa[pp+nn];
435 while (nn > 3) {
436 Int32 z = pp+nn;
437 s->mtfa[(z) ] = s->mtfa[(z)-1];
438 s->mtfa[(z)-1] = s->mtfa[(z)-2];
439 s->mtfa[(z)-2] = s->mtfa[(z)-3];
440 s->mtfa[(z)-3] = s->mtfa[(z)-4];
441 nn -= 4;
443 while (nn > 0) {
444 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
446 s->mtfa[pp] = uc;
447 } else {
448 /* general case */
449 lno = nn / MTFL_SIZE;
450 off = nn % MTFL_SIZE;
451 pp = s->mtfbase[lno] + off;
452 uc = s->mtfa[pp];
453 while (pp > s->mtfbase[lno]) {
454 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
456 s->mtfbase[lno]++;
457 while (lno > 0) {
458 s->mtfbase[lno]--;
459 s->mtfa[s->mtfbase[lno]]
460 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
461 lno--;
463 s->mtfbase[0]--;
464 s->mtfa[s->mtfbase[0]] = uc;
465 if (s->mtfbase[0] == 0) {
466 kk = MTFA_SIZE-1;
467 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
468 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
469 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
470 kk--;
472 s->mtfbase[ii] = kk + 1;
477 /*-- end uc = MTF ( nextSym-1 ) --*/
479 s->unzftab[s->seqToUnseq[uc]]++;
480 if (s->smallDecompress)
481 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
482 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
483 nblock++;
485 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
486 continue;
490 /* Now we know what nblock is, we can do a better sanity
491 check on s->origPtr.
493 if (s->origPtr < 0 || s->origPtr >= nblock)
494 RETURN(BZ_DATA_ERROR);
496 /*-- Set up cftab to facilitate generation of T^(-1) --*/
497 /* Check: unzftab entries in range. */
498 for (i = 0; i <= 255; i++) {
499 if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
500 RETURN(BZ_DATA_ERROR);
502 /* Actually generate cftab. */
503 s->cftab[0] = 0;
504 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
505 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
506 /* Check: cftab entries in range. */
507 for (i = 0; i <= 256; i++) {
508 if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
509 /* s->cftab[i] can legitimately be == nblock */
510 RETURN(BZ_DATA_ERROR);
513 /* Check: cftab entries non-descending. */
514 for (i = 1; i <= 256; i++) {
515 if (s->cftab[i-1] > s->cftab[i]) {
516 RETURN(BZ_DATA_ERROR);
520 s->state_out_len = 0;
521 s->state_out_ch = 0;
522 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
523 s->state = BZ_X_OUTPUT;
524 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
526 if (s->smallDecompress) {
528 /*-- Make a copy of cftab, used in generation of T --*/
529 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
531 /*-- compute the T vector --*/
532 for (i = 0; i < nblock; i++) {
533 uc = (UChar)(s->ll16[i]);
534 SET_LL(i, s->cftabCopy[uc]);
535 s->cftabCopy[uc]++;
538 /*-- Compute T^(-1) by pointer reversal on T --*/
539 i = s->origPtr;
540 j = GET_LL(i);
541 do {
542 Int32 tmp = GET_LL(j);
543 SET_LL(j, i);
544 i = j;
545 j = tmp;
547 while (i != s->origPtr);
549 s->tPos = s->origPtr;
550 s->nblock_used = 0;
551 if (s->blockRandomised) {
552 BZ_RAND_INIT_MASK;
553 BZ_GET_SMALL(s->k0); s->nblock_used++;
554 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
555 } else {
556 BZ_GET_SMALL(s->k0); s->nblock_used++;
559 } else {
561 /*-- compute the T^(-1) vector --*/
562 for (i = 0; i < nblock; i++) {
563 uc = (UChar)(s->tt[i] & 0xff);
564 s->tt[s->cftab[uc]] |= (i << 8);
565 s->cftab[uc]++;
568 s->tPos = s->tt[s->origPtr] >> 8;
569 s->nblock_used = 0;
570 if (s->blockRandomised) {
571 BZ_RAND_INIT_MASK;
572 BZ_GET_FAST(s->k0); s->nblock_used++;
573 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
574 } else {
575 BZ_GET_FAST(s->k0); s->nblock_used++;
580 RETURN(BZ_OK);
584 endhdr_2:
586 GET_UCHAR(BZ_X_ENDHDR_2, uc);
587 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
588 GET_UCHAR(BZ_X_ENDHDR_3, uc);
589 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
590 GET_UCHAR(BZ_X_ENDHDR_4, uc);
591 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
592 GET_UCHAR(BZ_X_ENDHDR_5, uc);
593 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
594 GET_UCHAR(BZ_X_ENDHDR_6, uc);
595 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
597 s->storedCombinedCRC = 0;
598 GET_UCHAR(BZ_X_CCRC_1, uc);
599 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
600 GET_UCHAR(BZ_X_CCRC_2, uc);
601 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
602 GET_UCHAR(BZ_X_CCRC_3, uc);
603 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
604 GET_UCHAR(BZ_X_CCRC_4, uc);
605 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
607 s->state = BZ_X_IDLE;
608 RETURN(BZ_STREAM_END);
610 default: AssertH ( False, 4001 );
613 AssertH ( False, 4002 );
615 save_state_and_return:
617 s->save_i = i;
618 s->save_j = j;
619 s->save_t = t;
620 s->save_alphaSize = alphaSize;
621 s->save_nGroups = nGroups;
622 s->save_nSelectors = nSelectors;
623 s->save_EOB = EOB;
624 s->save_groupNo = groupNo;
625 s->save_groupPos = groupPos;
626 s->save_nextSym = nextSym;
627 s->save_nblockMAX = nblockMAX;
628 s->save_nblock = nblock;
629 s->save_es = es;
630 s->save_N = N;
631 s->save_curr = curr;
632 s->save_zt = zt;
633 s->save_zn = zn;
634 s->save_zvec = zvec;
635 s->save_zj = zj;
636 s->save_gSel = gSel;
637 s->save_gMinlen = gMinlen;
638 s->save_gLimit = gLimit;
639 s->save_gBase = gBase;
640 s->save_gPerm = gPerm;
642 return retVal;
646 /*-------------------------------------------------------------*/
647 /*--- end decompress.c ---*/
648 /*-------------------------------------------------------------*/