X-Git-Url: http://4ch.mooo.com/gitweb/?a=blobdiff_plain;f=src%2Flib%2Fdl%2Fext%2Fbzip2%2Fdecomprs.c;fp=src%2Flib%2Fdl%2Fext%2Fbzip2%2Fdecomprs.c;h=0000000000000000000000000000000000000000;hb=4b23f27092a9470a741e3a18261ad389fd1929db;hp=91092feda301d3672cb25018d0eadf724d435bad;hpb=5d8d1deb6c3520abadbad86d202ea453df77bfc2;p=16.git diff --git a/src/lib/dl/ext/bzip2/decomprs.c b/src/lib/dl/ext/bzip2/decomprs.c deleted file mode 100755 index 91092fed..00000000 --- a/src/lib/dl/ext/bzip2/decomprs.c +++ /dev/null @@ -1,646 +0,0 @@ - -/*-------------------------------------------------------------*/ -/*--- Decompression machinery ---*/ -/*--- decompress.c ---*/ -/*-------------------------------------------------------------*/ - -/* ------------------------------------------------------------------ - This file is part of bzip2/libbzip2, a program and library for - lossless, block-sorting data compression. - - bzip2/libbzip2 version 1.0.6 of 6 September 2010 - Copyright (C) 1996-2010 Julian Seward - - Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file. - - This program is released under the terms of the license contained - in the file LICENSE. - ------------------------------------------------------------------ */ - - -#include "bzlibprv.h" - - -/*---------------------------------------------------*/ -static -void makeMaps_d ( DState* s ) -{ - Int32 i; - s->nInUse = 0; - for (i = 0; i < 256; i++) - if (s->inUse[i]) { - s->seqToUnseq[s->nInUse] = i; - s->nInUse++; - } -} - - -/*---------------------------------------------------*/ -#define RETURN(rrr) \ - { retVal = rrr; goto save_state_and_return; }; - -#define GET_BITS(lll,vvv,nnn) \ - case lll: s->state = lll; \ - while (True) { \ - if (s->bsLive >= nnn) { \ - UInt32 v; \ - v = (s->bsBuff >> \ - (s->bsLive-nnn)) & ((1 << nnn)-1); \ - s->bsLive -= nnn; \ - vvv = v; \ - break; \ - } \ - if (s->strm->avail_in == 0) RETURN(BZ_OK); \ - s->bsBuff \ - = (s->bsBuff << 8) | \ - ((UInt32) \ - (*((UChar*)(s->strm->next_in)))); \ - s->bsLive += 8; \ - s->strm->next_in++; \ - s->strm->avail_in--; \ - s->strm->total_in_lo32++; \ - if (s->strm->total_in_lo32 == 0) \ - s->strm->total_in_hi32++; \ - } - -#define GET_UCHAR(lll,uuu) \ - GET_BITS(lll,uuu,8) - -#define GET_BIT(lll,uuu) \ - GET_BITS(lll,uuu,1) - -/*---------------------------------------------------*/ -#define GET_MTF_VAL(label1,label2,lval) \ -{ \ - if (groupPos == 0) { \ - groupNo++; \ - if (groupNo >= nSelectors) \ - RETURN(BZ_DATA_ERROR); \ - groupPos = BZ_G_SIZE; \ - gSel = s->selector[groupNo]; \ - gMinlen = s->minLens[gSel]; \ - gLimit = &(s->limit[gSel][0]); \ - gPerm = &(s->perm[gSel][0]); \ - gBase = &(s->base[gSel][0]); \ - } \ - groupPos--; \ - zn = gMinlen; \ - GET_BITS(label1, zvec, zn); \ - while (1) { \ - if (zn > 20 /* the longest code */) \ - RETURN(BZ_DATA_ERROR); \ - if (zvec <= gLimit[zn]) break; \ - zn++; \ - GET_BIT(label2, zj); \ - zvec = (zvec << 1) | zj; \ - }; \ - if (zvec - gBase[zn] < 0 \ - || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ - RETURN(BZ_DATA_ERROR); \ - lval = gPerm[zvec - gBase[zn]]; \ -} - - -/*---------------------------------------------------*/ -Int32 BZ2_decompress ( DState* s ) -{ - UChar uc; - Int32 retVal; - Int32 minLen, maxLen; - bz_stream* strm = s->strm; - - /* stuff that needs to be saved/restored */ - Int32 i; - Int32 j; - Int32 t; - Int32 alphaSize; - Int32 nGroups; - Int32 nSelectors; - Int32 EOB; - Int32 groupNo; - Int32 groupPos; - Int32 nextSym; - Int32 nblockMAX; - Int32 nblock; - Int32 es; - Int32 N; - Int32 curr; - Int32 zt; - Int32 zn; - Int32 zvec; - Int32 zj; - Int32 gSel; - Int32 gMinlen; - Int32* gLimit; - Int32* gBase; - Int32* gPerm; - - if (s->state == BZ_X_MAGIC_1) { - /*initialise the save area*/ - s->save_i = 0; - s->save_j = 0; - s->save_t = 0; - s->save_alphaSize = 0; - s->save_nGroups = 0; - s->save_nSelectors = 0; - s->save_EOB = 0; - s->save_groupNo = 0; - s->save_groupPos = 0; - s->save_nextSym = 0; - s->save_nblockMAX = 0; - s->save_nblock = 0; - s->save_es = 0; - s->save_N = 0; - s->save_curr = 0; - s->save_zt = 0; - s->save_zn = 0; - s->save_zvec = 0; - s->save_zj = 0; - s->save_gSel = 0; - s->save_gMinlen = 0; - s->save_gLimit = NULL; - s->save_gBase = NULL; - s->save_gPerm = NULL; - } - - /*restore from the save area*/ - i = s->save_i; - j = s->save_j; - t = s->save_t; - alphaSize = s->save_alphaSize; - nGroups = s->save_nGroups; - nSelectors = s->save_nSelectors; - EOB = s->save_EOB; - groupNo = s->save_groupNo; - groupPos = s->save_groupPos; - nextSym = s->save_nextSym; - nblockMAX = s->save_nblockMAX; - nblock = s->save_nblock; - es = s->save_es; - N = s->save_N; - curr = s->save_curr; - zt = s->save_zt; - zn = s->save_zn; - zvec = s->save_zvec; - zj = s->save_zj; - gSel = s->save_gSel; - gMinlen = s->save_gMinlen; - gLimit = s->save_gLimit; - gBase = s->save_gBase; - gPerm = s->save_gPerm; - - retVal = BZ_OK; - - switch (s->state) { - - GET_UCHAR(BZ_X_MAGIC_1, uc); - if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); - - GET_UCHAR(BZ_X_MAGIC_2, uc); - if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); - - GET_UCHAR(BZ_X_MAGIC_3, uc) - if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); - - GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) - if (s->blockSize100k < (BZ_HDR_0 + 1) || - s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); - s->blockSize100k -= BZ_HDR_0; - - if (s->smallDecompress) { - s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); - s->ll4 = BZALLOC( - ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) - ); - if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); - } else { - s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); - if (s->tt == NULL) RETURN(BZ_MEM_ERROR); - } - - GET_UCHAR(BZ_X_BLKHDR_1, uc); - - if (uc == 0x17) goto endhdr_2; - if (uc != 0x31) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_BLKHDR_2, uc); - if (uc != 0x41) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_BLKHDR_3, uc); - if (uc != 0x59) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_BLKHDR_4, uc); - if (uc != 0x26) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_BLKHDR_5, uc); - if (uc != 0x53) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_BLKHDR_6, uc); - if (uc != 0x59) RETURN(BZ_DATA_ERROR); - - s->currBlockNo++; - if (s->verbosity >= 2) - VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); - - s->storedBlockCRC = 0; - GET_UCHAR(BZ_X_BCRC_1, uc); - s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); - GET_UCHAR(BZ_X_BCRC_2, uc); - s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); - GET_UCHAR(BZ_X_BCRC_3, uc); - s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); - GET_UCHAR(BZ_X_BCRC_4, uc); - s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); - - GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); - - s->origPtr = 0; - GET_UCHAR(BZ_X_ORIGPTR_1, uc); - s->origPtr = (s->origPtr << 8) | ((Int32)uc); - GET_UCHAR(BZ_X_ORIGPTR_2, uc); - s->origPtr = (s->origPtr << 8) | ((Int32)uc); - GET_UCHAR(BZ_X_ORIGPTR_3, uc); - s->origPtr = (s->origPtr << 8) | ((Int32)uc); - - if (s->origPtr < 0) - RETURN(BZ_DATA_ERROR); - if (s->origPtr > 10 + 100000*s->blockSize100k) - RETURN(BZ_DATA_ERROR); - - /*--- Receive the mapping table ---*/ - for (i = 0; i < 16; i++) { - GET_BIT(BZ_X_MAPPING_1, uc); - if (uc == 1) - s->inUse16[i] = True; else - s->inUse16[i] = False; - } - - for (i = 0; i < 256; i++) s->inUse[i] = False; - - for (i = 0; i < 16; i++) - if (s->inUse16[i]) - for (j = 0; j < 16; j++) { - GET_BIT(BZ_X_MAPPING_2, uc); - if (uc == 1) s->inUse[i * 16 + j] = True; - } - makeMaps_d ( s ); - if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); - alphaSize = s->nInUse+2; - - /*--- Now the selectors ---*/ - GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); - if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); - GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); - if (nSelectors < 1) RETURN(BZ_DATA_ERROR); - for (i = 0; i < nSelectors; i++) { - j = 0; - while (True) { - GET_BIT(BZ_X_SELECTOR_3, uc); - if (uc == 0) break; - j++; - if (j >= nGroups) RETURN(BZ_DATA_ERROR); - } - s->selectorMtf[i] = j; - } - - /*--- Undo the MTF values for the selectors. ---*/ - { - UChar pos[BZ_N_GROUPS], tmp, v; - for (v = 0; v < nGroups; v++) pos[v] = v; - - for (i = 0; i < nSelectors; i++) { - v = s->selectorMtf[i]; - tmp = pos[v]; - while (v > 0) { pos[v] = pos[v-1]; v--; } - pos[0] = tmp; - s->selector[i] = tmp; - } - } - - /*--- Now the coding tables ---*/ - for (t = 0; t < nGroups; t++) { - GET_BITS(BZ_X_CODING_1, curr, 5); - for (i = 0; i < alphaSize; i++) { - while (True) { - if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); - GET_BIT(BZ_X_CODING_2, uc); - if (uc == 0) break; - GET_BIT(BZ_X_CODING_3, uc); - if (uc == 0) curr++; else curr--; - } - s->len[t][i] = curr; - } - } - - /*--- Create the Huffman decoding tables ---*/ - for (t = 0; t < nGroups; t++) { - minLen = 32; - maxLen = 0; - for (i = 0; i < alphaSize; i++) { - if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; - if (s->len[t][i] < minLen) minLen = s->len[t][i]; - } - BZ2_hbCreateDecodeTables ( - &(s->limit[t][0]), - &(s->base[t][0]), - &(s->perm[t][0]), - &(s->len[t][0]), - minLen, maxLen, alphaSize - ); - s->minLens[t] = minLen; - } - - /*--- Now the MTF values ---*/ - - EOB = s->nInUse+1; - nblockMAX = 100000 * s->blockSize100k; - groupNo = -1; - groupPos = 0; - - for (i = 0; i <= 255; i++) s->unzftab[i] = 0; - - /*-- MTF init --*/ - { - Int32 ii, jj, kk; - kk = MTFA_SIZE-1; - for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { - for (jj = MTFL_SIZE-1; jj >= 0; jj--) { - s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); - kk--; - } - s->mtfbase[ii] = kk + 1; - } - } - /*-- end MTF init --*/ - - nblock = 0; - GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); - - while (True) { - - if (nextSym == EOB) break; - - if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { - - es = -1; - N = 1; - do { - /* Check that N doesn't get too big, so that es doesn't - go negative. The maximum value that can be - RUNA/RUNB encoded is equal to the block size (post - the initial RLE), viz, 900k, so bounding N at 2 - million should guard against overflow without - rejecting any legitimate inputs. */ - if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR); - if (nextSym == BZ_RUNA) es = es + (0+1) * N; else - if (nextSym == BZ_RUNB) es = es + (1+1) * N; - N = N * 2; - GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); - } - while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); - - es++; - uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; - s->unzftab[uc] += es; - - if (s->smallDecompress) - while (es > 0) { - if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); - s->ll16[nblock] = (UInt16)uc; - nblock++; - es--; - } - else - while (es > 0) { - if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); - s->tt[nblock] = (UInt32)uc; - nblock++; - es--; - }; - - continue; - - } else { - - if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); - - /*-- uc = MTF ( nextSym-1 ) --*/ - { - Int32 ii, jj, kk, pp, lno, off; - UInt32 nn; - nn = (UInt32)(nextSym - 1); - - if (nn < MTFL_SIZE) { - /* avoid general-case expense */ - pp = s->mtfbase[0]; - uc = s->mtfa[pp+nn]; - while (nn > 3) { - Int32 z = pp+nn; - s->mtfa[(z) ] = s->mtfa[(z)-1]; - s->mtfa[(z)-1] = s->mtfa[(z)-2]; - s->mtfa[(z)-2] = s->mtfa[(z)-3]; - s->mtfa[(z)-3] = s->mtfa[(z)-4]; - nn -= 4; - } - while (nn > 0) { - s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; - }; - s->mtfa[pp] = uc; - } else { - /* general case */ - lno = nn / MTFL_SIZE; - off = nn % MTFL_SIZE; - pp = s->mtfbase[lno] + off; - uc = s->mtfa[pp]; - while (pp > s->mtfbase[lno]) { - s->mtfa[pp] = s->mtfa[pp-1]; pp--; - }; - s->mtfbase[lno]++; - while (lno > 0) { - s->mtfbase[lno]--; - s->mtfa[s->mtfbase[lno]] - = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; - lno--; - } - s->mtfbase[0]--; - s->mtfa[s->mtfbase[0]] = uc; - if (s->mtfbase[0] == 0) { - kk = MTFA_SIZE-1; - for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { - for (jj = MTFL_SIZE-1; jj >= 0; jj--) { - s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; - kk--; - } - s->mtfbase[ii] = kk + 1; - } - } - } - } - /*-- end uc = MTF ( nextSym-1 ) --*/ - - s->unzftab[s->seqToUnseq[uc]]++; - if (s->smallDecompress) - s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else - s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); - nblock++; - - GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); - continue; - } - } - - /* Now we know what nblock is, we can do a better sanity - check on s->origPtr. - */ - if (s->origPtr < 0 || s->origPtr >= nblock) - RETURN(BZ_DATA_ERROR); - - /*-- Set up cftab to facilitate generation of T^(-1) --*/ - /* Check: unzftab entries in range. */ - for (i = 0; i <= 255; i++) { - if (s->unzftab[i] < 0 || s->unzftab[i] > nblock) - RETURN(BZ_DATA_ERROR); - } - /* Actually generate cftab. */ - s->cftab[0] = 0; - for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; - for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; - /* Check: cftab entries in range. */ - for (i = 0; i <= 256; i++) { - if (s->cftab[i] < 0 || s->cftab[i] > nblock) { - /* s->cftab[i] can legitimately be == nblock */ - RETURN(BZ_DATA_ERROR); - } - } - /* Check: cftab entries non-descending. */ - for (i = 1; i <= 256; i++) { - if (s->cftab[i-1] > s->cftab[i]) { - RETURN(BZ_DATA_ERROR); - } - } - - s->state_out_len = 0; - s->state_out_ch = 0; - BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); - s->state = BZ_X_OUTPUT; - if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); - - if (s->smallDecompress) { - - /*-- Make a copy of cftab, used in generation of T --*/ - for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; - - /*-- compute the T vector --*/ - for (i = 0; i < nblock; i++) { - uc = (UChar)(s->ll16[i]); - SET_LL(i, s->cftabCopy[uc]); - s->cftabCopy[uc]++; - } - - /*-- Compute T^(-1) by pointer reversal on T --*/ - i = s->origPtr; - j = GET_LL(i); - do { - Int32 tmp = GET_LL(j); - SET_LL(j, i); - i = j; - j = tmp; - } - while (i != s->origPtr); - - s->tPos = s->origPtr; - s->nblock_used = 0; - if (s->blockRandomised) { - BZ_RAND_INIT_MASK; - BZ_GET_SMALL(s->k0); s->nblock_used++; - BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; - } else { - BZ_GET_SMALL(s->k0); s->nblock_used++; - } - - } else { - - /*-- compute the T^(-1) vector --*/ - for (i = 0; i < nblock; i++) { - uc = (UChar)(s->tt[i] & 0xff); - s->tt[s->cftab[uc]] |= (i << 8); - s->cftab[uc]++; - } - - s->tPos = s->tt[s->origPtr] >> 8; - s->nblock_used = 0; - if (s->blockRandomised) { - BZ_RAND_INIT_MASK; - BZ_GET_FAST(s->k0); s->nblock_used++; - BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; - } else { - BZ_GET_FAST(s->k0); s->nblock_used++; - } - - } - - RETURN(BZ_OK); - - - - endhdr_2: - - GET_UCHAR(BZ_X_ENDHDR_2, uc); - if (uc != 0x72) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_ENDHDR_3, uc); - if (uc != 0x45) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_ENDHDR_4, uc); - if (uc != 0x38) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_ENDHDR_5, uc); - if (uc != 0x50) RETURN(BZ_DATA_ERROR); - GET_UCHAR(BZ_X_ENDHDR_6, uc); - if (uc != 0x90) RETURN(BZ_DATA_ERROR); - - s->storedCombinedCRC = 0; - GET_UCHAR(BZ_X_CCRC_1, uc); - s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); - GET_UCHAR(BZ_X_CCRC_2, uc); - s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); - GET_UCHAR(BZ_X_CCRC_3, uc); - s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); - GET_UCHAR(BZ_X_CCRC_4, uc); - s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); - - s->state = BZ_X_IDLE; - RETURN(BZ_STREAM_END); - - default: AssertH ( False, 4001 ); - } - - AssertH ( False, 4002 ); - - save_state_and_return: - - s->save_i = i; - s->save_j = j; - s->save_t = t; - s->save_alphaSize = alphaSize; - s->save_nGroups = nGroups; - s->save_nSelectors = nSelectors; - s->save_EOB = EOB; - s->save_groupNo = groupNo; - s->save_groupPos = groupPos; - s->save_nextSym = nextSym; - s->save_nblockMAX = nblockMAX; - s->save_nblock = nblock; - s->save_es = es; - s->save_N = N; - s->save_curr = curr; - s->save_zt = zt; - s->save_zn = zn; - s->save_zvec = zvec; - s->save_zj = zj; - s->save_gSel = gSel; - s->save_gMinlen = gMinlen; - s->save_gLimit = gLimit; - s->save_gBase = gBase; - s->save_gPerm = gPerm; - - return retVal; -} - - -/*-------------------------------------------------------------*/ -/*--- end decompress.c ---*/ -/*-------------------------------------------------------------*/