decompress.c revision 167974
178556Sobrien 278556Sobrien/*-------------------------------------------------------------*/ 378556Sobrien/*--- Decompression machinery ---*/ 478556Sobrien/*--- decompress.c ---*/ 578556Sobrien/*-------------------------------------------------------------*/ 678556Sobrien 7167974Sdelphij/* ------------------------------------------------------------------ 8167974Sdelphij This file is part of bzip2/libbzip2, a program and library for 9167974Sdelphij lossless, block-sorting data compression. 1078556Sobrien 11167974Sdelphij bzip2/libbzip2 version 1.0.4 of 20 December 2006 12167974Sdelphij Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org> 1378556Sobrien 14167974Sdelphij Please read the WARNING, DISCLAIMER and PATENTS sections in the 15167974Sdelphij README file. 1678556Sobrien 17167974Sdelphij This program is released under the terms of the license contained 18167974Sdelphij in the file LICENSE. 19167974Sdelphij ------------------------------------------------------------------ */ 2078556Sobrien 2178556Sobrien 2278556Sobrien#include "bzlib_private.h" 2378556Sobrien 2478556Sobrien 2578556Sobrien/*---------------------------------------------------*/ 2678556Sobrienstatic 2778556Sobrienvoid makeMaps_d ( DState* s ) 2878556Sobrien{ 2978556Sobrien Int32 i; 3078556Sobrien s->nInUse = 0; 3178556Sobrien for (i = 0; i < 256; i++) 3278556Sobrien if (s->inUse[i]) { 3378556Sobrien s->seqToUnseq[s->nInUse] = i; 3478556Sobrien s->nInUse++; 3578556Sobrien } 3678556Sobrien} 3778556Sobrien 3878556Sobrien 3978556Sobrien/*---------------------------------------------------*/ 4078556Sobrien#define RETURN(rrr) \ 4178556Sobrien { retVal = rrr; goto save_state_and_return; }; 4278556Sobrien 4378556Sobrien#define GET_BITS(lll,vvv,nnn) \ 4478556Sobrien case lll: s->state = lll; \ 4578556Sobrien while (True) { \ 4678556Sobrien if (s->bsLive >= nnn) { \ 4778556Sobrien UInt32 v; \ 4878556Sobrien v = (s->bsBuff >> \ 4978556Sobrien (s->bsLive-nnn)) & ((1 << nnn)-1); \ 5078556Sobrien s->bsLive -= nnn; \ 5178556Sobrien vvv = v; \ 5278556Sobrien break; \ 5378556Sobrien } \ 5478556Sobrien if (s->strm->avail_in == 0) RETURN(BZ_OK); \ 5578556Sobrien s->bsBuff \ 5678556Sobrien = (s->bsBuff << 8) | \ 5778556Sobrien ((UInt32) \ 5878556Sobrien (*((UChar*)(s->strm->next_in)))); \ 5978556Sobrien s->bsLive += 8; \ 6078556Sobrien s->strm->next_in++; \ 6178556Sobrien s->strm->avail_in--; \ 6278556Sobrien s->strm->total_in_lo32++; \ 6378556Sobrien if (s->strm->total_in_lo32 == 0) \ 6478556Sobrien s->strm->total_in_hi32++; \ 6578556Sobrien } 6678556Sobrien 6778556Sobrien#define GET_UCHAR(lll,uuu) \ 6878556Sobrien GET_BITS(lll,uuu,8) 6978556Sobrien 7078556Sobrien#define GET_BIT(lll,uuu) \ 7178556Sobrien GET_BITS(lll,uuu,1) 7278556Sobrien 7378556Sobrien/*---------------------------------------------------*/ 7478556Sobrien#define GET_MTF_VAL(label1,label2,lval) \ 7578556Sobrien{ \ 7678556Sobrien if (groupPos == 0) { \ 7778556Sobrien groupNo++; \ 7878556Sobrien if (groupNo >= nSelectors) \ 7978556Sobrien RETURN(BZ_DATA_ERROR); \ 8078556Sobrien groupPos = BZ_G_SIZE; \ 8178556Sobrien gSel = s->selector[groupNo]; \ 8278556Sobrien gMinlen = s->minLens[gSel]; \ 8378556Sobrien gLimit = &(s->limit[gSel][0]); \ 8478556Sobrien gPerm = &(s->perm[gSel][0]); \ 8578556Sobrien gBase = &(s->base[gSel][0]); \ 8678556Sobrien } \ 8778556Sobrien groupPos--; \ 8878556Sobrien zn = gMinlen; \ 8978556Sobrien GET_BITS(label1, zvec, zn); \ 9078556Sobrien while (1) { \ 9178556Sobrien if (zn > 20 /* the longest code */) \ 9278556Sobrien RETURN(BZ_DATA_ERROR); \ 9378556Sobrien if (zvec <= gLimit[zn]) break; \ 9478556Sobrien zn++; \ 9578556Sobrien GET_BIT(label2, zj); \ 9678556Sobrien zvec = (zvec << 1) | zj; \ 9778556Sobrien }; \ 9878556Sobrien if (zvec - gBase[zn] < 0 \ 9978556Sobrien || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ 10078556Sobrien RETURN(BZ_DATA_ERROR); \ 10178556Sobrien lval = gPerm[zvec - gBase[zn]]; \ 10278556Sobrien} 10378556Sobrien 10478556Sobrien 10578556Sobrien/*---------------------------------------------------*/ 10678556SobrienInt32 BZ2_decompress ( DState* s ) 10778556Sobrien{ 10878556Sobrien UChar uc; 10978556Sobrien Int32 retVal; 11078556Sobrien Int32 minLen, maxLen; 11178556Sobrien bz_stream* strm = s->strm; 11278556Sobrien 11378556Sobrien /* stuff that needs to be saved/restored */ 11478556Sobrien Int32 i; 11578556Sobrien Int32 j; 11678556Sobrien Int32 t; 11778556Sobrien Int32 alphaSize; 11878556Sobrien Int32 nGroups; 11978556Sobrien Int32 nSelectors; 12078556Sobrien Int32 EOB; 12178556Sobrien Int32 groupNo; 12278556Sobrien Int32 groupPos; 12378556Sobrien Int32 nextSym; 12478556Sobrien Int32 nblockMAX; 12578556Sobrien Int32 nblock; 12678556Sobrien Int32 es; 12778556Sobrien Int32 N; 12878556Sobrien Int32 curr; 12978556Sobrien Int32 zt; 13078556Sobrien Int32 zn; 13178556Sobrien Int32 zvec; 13278556Sobrien Int32 zj; 13378556Sobrien Int32 gSel; 13478556Sobrien Int32 gMinlen; 13578556Sobrien Int32* gLimit; 13678556Sobrien Int32* gBase; 13778556Sobrien Int32* gPerm; 13878556Sobrien 13978556Sobrien if (s->state == BZ_X_MAGIC_1) { 14078556Sobrien /*initialise the save area*/ 14178556Sobrien s->save_i = 0; 14278556Sobrien s->save_j = 0; 14378556Sobrien s->save_t = 0; 14478556Sobrien s->save_alphaSize = 0; 14578556Sobrien s->save_nGroups = 0; 14678556Sobrien s->save_nSelectors = 0; 14778556Sobrien s->save_EOB = 0; 14878556Sobrien s->save_groupNo = 0; 14978556Sobrien s->save_groupPos = 0; 15078556Sobrien s->save_nextSym = 0; 15178556Sobrien s->save_nblockMAX = 0; 15278556Sobrien s->save_nblock = 0; 15378556Sobrien s->save_es = 0; 15478556Sobrien s->save_N = 0; 15578556Sobrien s->save_curr = 0; 15678556Sobrien s->save_zt = 0; 15778556Sobrien s->save_zn = 0; 15878556Sobrien s->save_zvec = 0; 15978556Sobrien s->save_zj = 0; 16078556Sobrien s->save_gSel = 0; 16178556Sobrien s->save_gMinlen = 0; 16278556Sobrien s->save_gLimit = NULL; 16378556Sobrien s->save_gBase = NULL; 16478556Sobrien s->save_gPerm = NULL; 16578556Sobrien } 16678556Sobrien 16778556Sobrien /*restore from the save area*/ 16878556Sobrien i = s->save_i; 16978556Sobrien j = s->save_j; 17078556Sobrien t = s->save_t; 17178556Sobrien alphaSize = s->save_alphaSize; 17278556Sobrien nGroups = s->save_nGroups; 17378556Sobrien nSelectors = s->save_nSelectors; 17478556Sobrien EOB = s->save_EOB; 17578556Sobrien groupNo = s->save_groupNo; 17678556Sobrien groupPos = s->save_groupPos; 17778556Sobrien nextSym = s->save_nextSym; 17878556Sobrien nblockMAX = s->save_nblockMAX; 17978556Sobrien nblock = s->save_nblock; 18078556Sobrien es = s->save_es; 18178556Sobrien N = s->save_N; 18278556Sobrien curr = s->save_curr; 18378556Sobrien zt = s->save_zt; 18478556Sobrien zn = s->save_zn; 18578556Sobrien zvec = s->save_zvec; 18678556Sobrien zj = s->save_zj; 18778556Sobrien gSel = s->save_gSel; 18878556Sobrien gMinlen = s->save_gMinlen; 18978556Sobrien gLimit = s->save_gLimit; 19078556Sobrien gBase = s->save_gBase; 19178556Sobrien gPerm = s->save_gPerm; 19278556Sobrien 19378556Sobrien retVal = BZ_OK; 19478556Sobrien 19578556Sobrien switch (s->state) { 19678556Sobrien 19778556Sobrien GET_UCHAR(BZ_X_MAGIC_1, uc); 19890067Ssobomax if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); 19978556Sobrien 20078556Sobrien GET_UCHAR(BZ_X_MAGIC_2, uc); 20190067Ssobomax if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); 20278556Sobrien 20378556Sobrien GET_UCHAR(BZ_X_MAGIC_3, uc) 20490067Ssobomax if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); 20578556Sobrien 20678556Sobrien GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 20790067Ssobomax if (s->blockSize100k < (BZ_HDR_0 + 1) || 20890067Ssobomax s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); 20990067Ssobomax s->blockSize100k -= BZ_HDR_0; 21078556Sobrien 21178556Sobrien if (s->smallDecompress) { 21278556Sobrien s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 21378556Sobrien s->ll4 = BZALLOC( 21478556Sobrien ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 21578556Sobrien ); 21678556Sobrien if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 21778556Sobrien } else { 21878556Sobrien s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 21978556Sobrien if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 22078556Sobrien } 22178556Sobrien 22278556Sobrien GET_UCHAR(BZ_X_BLKHDR_1, uc); 22378556Sobrien 22478556Sobrien if (uc == 0x17) goto endhdr_2; 22578556Sobrien if (uc != 0x31) RETURN(BZ_DATA_ERROR); 22678556Sobrien GET_UCHAR(BZ_X_BLKHDR_2, uc); 22778556Sobrien if (uc != 0x41) RETURN(BZ_DATA_ERROR); 22878556Sobrien GET_UCHAR(BZ_X_BLKHDR_3, uc); 22978556Sobrien if (uc != 0x59) RETURN(BZ_DATA_ERROR); 23078556Sobrien GET_UCHAR(BZ_X_BLKHDR_4, uc); 23178556Sobrien if (uc != 0x26) RETURN(BZ_DATA_ERROR); 23278556Sobrien GET_UCHAR(BZ_X_BLKHDR_5, uc); 23378556Sobrien if (uc != 0x53) RETURN(BZ_DATA_ERROR); 23478556Sobrien GET_UCHAR(BZ_X_BLKHDR_6, uc); 23578556Sobrien if (uc != 0x59) RETURN(BZ_DATA_ERROR); 23678556Sobrien 23778556Sobrien s->currBlockNo++; 23878556Sobrien if (s->verbosity >= 2) 23978556Sobrien VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 24078556Sobrien 24178556Sobrien s->storedBlockCRC = 0; 24278556Sobrien GET_UCHAR(BZ_X_BCRC_1, uc); 24378556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 24478556Sobrien GET_UCHAR(BZ_X_BCRC_2, uc); 24578556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 24678556Sobrien GET_UCHAR(BZ_X_BCRC_3, uc); 24778556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 24878556Sobrien GET_UCHAR(BZ_X_BCRC_4, uc); 24978556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 25078556Sobrien 25178556Sobrien GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 25278556Sobrien 25378556Sobrien s->origPtr = 0; 25478556Sobrien GET_UCHAR(BZ_X_ORIGPTR_1, uc); 25578556Sobrien s->origPtr = (s->origPtr << 8) | ((Int32)uc); 25678556Sobrien GET_UCHAR(BZ_X_ORIGPTR_2, uc); 25778556Sobrien s->origPtr = (s->origPtr << 8) | ((Int32)uc); 25878556Sobrien GET_UCHAR(BZ_X_ORIGPTR_3, uc); 25978556Sobrien s->origPtr = (s->origPtr << 8) | ((Int32)uc); 26078556Sobrien 26178556Sobrien if (s->origPtr < 0) 26278556Sobrien RETURN(BZ_DATA_ERROR); 26378556Sobrien if (s->origPtr > 10 + 100000*s->blockSize100k) 26478556Sobrien RETURN(BZ_DATA_ERROR); 26578556Sobrien 26678556Sobrien /*--- Receive the mapping table ---*/ 26778556Sobrien for (i = 0; i < 16; i++) { 26878556Sobrien GET_BIT(BZ_X_MAPPING_1, uc); 26978556Sobrien if (uc == 1) 27078556Sobrien s->inUse16[i] = True; else 27178556Sobrien s->inUse16[i] = False; 27278556Sobrien } 27378556Sobrien 27478556Sobrien for (i = 0; i < 256; i++) s->inUse[i] = False; 27578556Sobrien 27678556Sobrien for (i = 0; i < 16; i++) 27778556Sobrien if (s->inUse16[i]) 27878556Sobrien for (j = 0; j < 16; j++) { 27978556Sobrien GET_BIT(BZ_X_MAPPING_2, uc); 28078556Sobrien if (uc == 1) s->inUse[i * 16 + j] = True; 28178556Sobrien } 28278556Sobrien makeMaps_d ( s ); 28378556Sobrien if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); 28478556Sobrien alphaSize = s->nInUse+2; 28578556Sobrien 28678556Sobrien /*--- Now the selectors ---*/ 28778556Sobrien GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 28878556Sobrien if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); 28978556Sobrien GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 29078556Sobrien if (nSelectors < 1) RETURN(BZ_DATA_ERROR); 29178556Sobrien for (i = 0; i < nSelectors; i++) { 29278556Sobrien j = 0; 29378556Sobrien while (True) { 29478556Sobrien GET_BIT(BZ_X_SELECTOR_3, uc); 29578556Sobrien if (uc == 0) break; 29678556Sobrien j++; 29778556Sobrien if (j >= nGroups) RETURN(BZ_DATA_ERROR); 29878556Sobrien } 29978556Sobrien s->selectorMtf[i] = j; 30078556Sobrien } 30178556Sobrien 30278556Sobrien /*--- Undo the MTF values for the selectors. ---*/ 30378556Sobrien { 30478556Sobrien UChar pos[BZ_N_GROUPS], tmp, v; 30578556Sobrien for (v = 0; v < nGroups; v++) pos[v] = v; 30678556Sobrien 30778556Sobrien for (i = 0; i < nSelectors; i++) { 30878556Sobrien v = s->selectorMtf[i]; 30978556Sobrien tmp = pos[v]; 31078556Sobrien while (v > 0) { pos[v] = pos[v-1]; v--; } 31178556Sobrien pos[0] = tmp; 31278556Sobrien s->selector[i] = tmp; 31378556Sobrien } 31478556Sobrien } 31578556Sobrien 31678556Sobrien /*--- Now the coding tables ---*/ 31778556Sobrien for (t = 0; t < nGroups; t++) { 31878556Sobrien GET_BITS(BZ_X_CODING_1, curr, 5); 31978556Sobrien for (i = 0; i < alphaSize; i++) { 32078556Sobrien while (True) { 32178556Sobrien if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 32278556Sobrien GET_BIT(BZ_X_CODING_2, uc); 32378556Sobrien if (uc == 0) break; 32478556Sobrien GET_BIT(BZ_X_CODING_3, uc); 32578556Sobrien if (uc == 0) curr++; else curr--; 32678556Sobrien } 32778556Sobrien s->len[t][i] = curr; 32878556Sobrien } 32978556Sobrien } 33078556Sobrien 33178556Sobrien /*--- Create the Huffman decoding tables ---*/ 33278556Sobrien for (t = 0; t < nGroups; t++) { 33378556Sobrien minLen = 32; 33478556Sobrien maxLen = 0; 33578556Sobrien for (i = 0; i < alphaSize; i++) { 33678556Sobrien if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 33778556Sobrien if (s->len[t][i] < minLen) minLen = s->len[t][i]; 33878556Sobrien } 33978556Sobrien BZ2_hbCreateDecodeTables ( 34078556Sobrien &(s->limit[t][0]), 34178556Sobrien &(s->base[t][0]), 34278556Sobrien &(s->perm[t][0]), 34378556Sobrien &(s->len[t][0]), 34478556Sobrien minLen, maxLen, alphaSize 34578556Sobrien ); 34678556Sobrien s->minLens[t] = minLen; 34778556Sobrien } 34878556Sobrien 34978556Sobrien /*--- Now the MTF values ---*/ 35078556Sobrien 35178556Sobrien EOB = s->nInUse+1; 35278556Sobrien nblockMAX = 100000 * s->blockSize100k; 35378556Sobrien groupNo = -1; 35478556Sobrien groupPos = 0; 35578556Sobrien 35678556Sobrien for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 35778556Sobrien 35878556Sobrien /*-- MTF init --*/ 35978556Sobrien { 36078556Sobrien Int32 ii, jj, kk; 36178556Sobrien kk = MTFA_SIZE-1; 36278556Sobrien for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 36378556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 36478556Sobrien s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 36578556Sobrien kk--; 36678556Sobrien } 36778556Sobrien s->mtfbase[ii] = kk + 1; 36878556Sobrien } 36978556Sobrien } 37078556Sobrien /*-- end MTF init --*/ 37178556Sobrien 37278556Sobrien nblock = 0; 37378556Sobrien GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 37478556Sobrien 37578556Sobrien while (True) { 37678556Sobrien 37778556Sobrien if (nextSym == EOB) break; 37878556Sobrien 37978556Sobrien if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 38078556Sobrien 38178556Sobrien es = -1; 38278556Sobrien N = 1; 38378556Sobrien do { 38478556Sobrien if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 38578556Sobrien if (nextSym == BZ_RUNB) es = es + (1+1) * N; 38678556Sobrien N = N * 2; 38778556Sobrien GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 38878556Sobrien } 38978556Sobrien while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 39078556Sobrien 39178556Sobrien es++; 39278556Sobrien uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 39378556Sobrien s->unzftab[uc] += es; 39478556Sobrien 39578556Sobrien if (s->smallDecompress) 39678556Sobrien while (es > 0) { 39778556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 39878556Sobrien s->ll16[nblock] = (UInt16)uc; 39978556Sobrien nblock++; 40078556Sobrien es--; 40178556Sobrien } 40278556Sobrien else 40378556Sobrien while (es > 0) { 40478556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 40578556Sobrien s->tt[nblock] = (UInt32)uc; 40678556Sobrien nblock++; 40778556Sobrien es--; 40878556Sobrien }; 40978556Sobrien 41078556Sobrien continue; 41178556Sobrien 41278556Sobrien } else { 41378556Sobrien 41478556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 41578556Sobrien 41678556Sobrien /*-- uc = MTF ( nextSym-1 ) --*/ 41778556Sobrien { 41878556Sobrien Int32 ii, jj, kk, pp, lno, off; 41978556Sobrien UInt32 nn; 42078556Sobrien nn = (UInt32)(nextSym - 1); 42178556Sobrien 42278556Sobrien if (nn < MTFL_SIZE) { 42378556Sobrien /* avoid general-case expense */ 42478556Sobrien pp = s->mtfbase[0]; 42578556Sobrien uc = s->mtfa[pp+nn]; 42678556Sobrien while (nn > 3) { 42778556Sobrien Int32 z = pp+nn; 42878556Sobrien s->mtfa[(z) ] = s->mtfa[(z)-1]; 42978556Sobrien s->mtfa[(z)-1] = s->mtfa[(z)-2]; 43078556Sobrien s->mtfa[(z)-2] = s->mtfa[(z)-3]; 43178556Sobrien s->mtfa[(z)-3] = s->mtfa[(z)-4]; 43278556Sobrien nn -= 4; 43378556Sobrien } 43478556Sobrien while (nn > 0) { 43578556Sobrien s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 43678556Sobrien }; 43778556Sobrien s->mtfa[pp] = uc; 43878556Sobrien } else { 43978556Sobrien /* general case */ 44078556Sobrien lno = nn / MTFL_SIZE; 44178556Sobrien off = nn % MTFL_SIZE; 44278556Sobrien pp = s->mtfbase[lno] + off; 44378556Sobrien uc = s->mtfa[pp]; 44478556Sobrien while (pp > s->mtfbase[lno]) { 44578556Sobrien s->mtfa[pp] = s->mtfa[pp-1]; pp--; 44678556Sobrien }; 44778556Sobrien s->mtfbase[lno]++; 44878556Sobrien while (lno > 0) { 44978556Sobrien s->mtfbase[lno]--; 45078556Sobrien s->mtfa[s->mtfbase[lno]] 45178556Sobrien = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 45278556Sobrien lno--; 45378556Sobrien } 45478556Sobrien s->mtfbase[0]--; 45578556Sobrien s->mtfa[s->mtfbase[0]] = uc; 45678556Sobrien if (s->mtfbase[0] == 0) { 45778556Sobrien kk = MTFA_SIZE-1; 45878556Sobrien for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 45978556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 46078556Sobrien s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 46178556Sobrien kk--; 46278556Sobrien } 46378556Sobrien s->mtfbase[ii] = kk + 1; 46478556Sobrien } 46578556Sobrien } 46678556Sobrien } 46778556Sobrien } 46878556Sobrien /*-- end uc = MTF ( nextSym-1 ) --*/ 46978556Sobrien 47078556Sobrien s->unzftab[s->seqToUnseq[uc]]++; 47178556Sobrien if (s->smallDecompress) 47278556Sobrien s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 47378556Sobrien s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 47478556Sobrien nblock++; 47578556Sobrien 47678556Sobrien GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 47778556Sobrien continue; 47878556Sobrien } 47978556Sobrien } 48078556Sobrien 48178556Sobrien /* Now we know what nblock is, we can do a better sanity 48278556Sobrien check on s->origPtr. 48378556Sobrien */ 48478556Sobrien if (s->origPtr < 0 || s->origPtr >= nblock) 48578556Sobrien RETURN(BZ_DATA_ERROR); 48678556Sobrien 487146293Sobrien /*-- Set up cftab to facilitate generation of T^(-1) --*/ 488146293Sobrien s->cftab[0] = 0; 489146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 490146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 491146293Sobrien for (i = 0; i <= 256; i++) { 492146293Sobrien if (s->cftab[i] < 0 || s->cftab[i] > nblock) { 493146293Sobrien /* s->cftab[i] can legitimately be == nblock */ 494146293Sobrien RETURN(BZ_DATA_ERROR); 495146293Sobrien } 496146293Sobrien } 497146293Sobrien 49878556Sobrien s->state_out_len = 0; 49978556Sobrien s->state_out_ch = 0; 50078556Sobrien BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 50178556Sobrien s->state = BZ_X_OUTPUT; 50278556Sobrien if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 50378556Sobrien 50478556Sobrien if (s->smallDecompress) { 50578556Sobrien 50678556Sobrien /*-- Make a copy of cftab, used in generation of T --*/ 50778556Sobrien for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 50878556Sobrien 50978556Sobrien /*-- compute the T vector --*/ 51078556Sobrien for (i = 0; i < nblock; i++) { 51178556Sobrien uc = (UChar)(s->ll16[i]); 51278556Sobrien SET_LL(i, s->cftabCopy[uc]); 51378556Sobrien s->cftabCopy[uc]++; 51478556Sobrien } 51578556Sobrien 51678556Sobrien /*-- Compute T^(-1) by pointer reversal on T --*/ 51778556Sobrien i = s->origPtr; 51878556Sobrien j = GET_LL(i); 51978556Sobrien do { 52078556Sobrien Int32 tmp = GET_LL(j); 52178556Sobrien SET_LL(j, i); 52278556Sobrien i = j; 52378556Sobrien j = tmp; 52478556Sobrien } 52578556Sobrien while (i != s->origPtr); 52678556Sobrien 52778556Sobrien s->tPos = s->origPtr; 52878556Sobrien s->nblock_used = 0; 52978556Sobrien if (s->blockRandomised) { 53078556Sobrien BZ_RAND_INIT_MASK; 53178556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 53278556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 53378556Sobrien } else { 53478556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 53578556Sobrien } 53678556Sobrien 53778556Sobrien } else { 53878556Sobrien 53978556Sobrien /*-- compute the T^(-1) vector --*/ 54078556Sobrien for (i = 0; i < nblock; i++) { 54178556Sobrien uc = (UChar)(s->tt[i] & 0xff); 54278556Sobrien s->tt[s->cftab[uc]] |= (i << 8); 54378556Sobrien s->cftab[uc]++; 54478556Sobrien } 54578556Sobrien 54678556Sobrien s->tPos = s->tt[s->origPtr] >> 8; 54778556Sobrien s->nblock_used = 0; 54878556Sobrien if (s->blockRandomised) { 54978556Sobrien BZ_RAND_INIT_MASK; 55078556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 55178556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 55278556Sobrien } else { 55378556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 55478556Sobrien } 55578556Sobrien 55678556Sobrien } 55778556Sobrien 55878556Sobrien RETURN(BZ_OK); 55978556Sobrien 56078556Sobrien 56178556Sobrien 56278556Sobrien endhdr_2: 56378556Sobrien 56478556Sobrien GET_UCHAR(BZ_X_ENDHDR_2, uc); 56578556Sobrien if (uc != 0x72) RETURN(BZ_DATA_ERROR); 56678556Sobrien GET_UCHAR(BZ_X_ENDHDR_3, uc); 56778556Sobrien if (uc != 0x45) RETURN(BZ_DATA_ERROR); 56878556Sobrien GET_UCHAR(BZ_X_ENDHDR_4, uc); 56978556Sobrien if (uc != 0x38) RETURN(BZ_DATA_ERROR); 57078556Sobrien GET_UCHAR(BZ_X_ENDHDR_5, uc); 57178556Sobrien if (uc != 0x50) RETURN(BZ_DATA_ERROR); 57278556Sobrien GET_UCHAR(BZ_X_ENDHDR_6, uc); 57378556Sobrien if (uc != 0x90) RETURN(BZ_DATA_ERROR); 57478556Sobrien 57578556Sobrien s->storedCombinedCRC = 0; 57678556Sobrien GET_UCHAR(BZ_X_CCRC_1, uc); 57778556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 57878556Sobrien GET_UCHAR(BZ_X_CCRC_2, uc); 57978556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 58078556Sobrien GET_UCHAR(BZ_X_CCRC_3, uc); 58178556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 58278556Sobrien GET_UCHAR(BZ_X_CCRC_4, uc); 58378556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 58478556Sobrien 58578556Sobrien s->state = BZ_X_IDLE; 58678556Sobrien RETURN(BZ_STREAM_END); 58778556Sobrien 58878556Sobrien default: AssertH ( False, 4001 ); 58978556Sobrien } 59078556Sobrien 59178556Sobrien AssertH ( False, 4002 ); 59278556Sobrien 59378556Sobrien save_state_and_return: 59478556Sobrien 59578556Sobrien s->save_i = i; 59678556Sobrien s->save_j = j; 59778556Sobrien s->save_t = t; 59878556Sobrien s->save_alphaSize = alphaSize; 59978556Sobrien s->save_nGroups = nGroups; 60078556Sobrien s->save_nSelectors = nSelectors; 60178556Sobrien s->save_EOB = EOB; 60278556Sobrien s->save_groupNo = groupNo; 60378556Sobrien s->save_groupPos = groupPos; 60478556Sobrien s->save_nextSym = nextSym; 60578556Sobrien s->save_nblockMAX = nblockMAX; 60678556Sobrien s->save_nblock = nblock; 60778556Sobrien s->save_es = es; 60878556Sobrien s->save_N = N; 60978556Sobrien s->save_curr = curr; 61078556Sobrien s->save_zt = zt; 61178556Sobrien s->save_zn = zn; 61278556Sobrien s->save_zvec = zvec; 61378556Sobrien s->save_zj = zj; 61478556Sobrien s->save_gSel = gSel; 61578556Sobrien s->save_gMinlen = gMinlen; 61678556Sobrien s->save_gLimit = gLimit; 61778556Sobrien s->save_gBase = gBase; 61878556Sobrien s->save_gPerm = gPerm; 61978556Sobrien 62078556Sobrien return retVal; 62178556Sobrien} 62278556Sobrien 62378556Sobrien 62478556Sobrien/*-------------------------------------------------------------*/ 62578556Sobrien/*--- end decompress.c ---*/ 62678556Sobrien/*-------------------------------------------------------------*/ 627