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 11215041Sobrien bzip2/libbzip2 version 1.0.6 of 6 September 2010 12215041Sobrien Copyright (C) 1996-2010 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 { 384212901Scperciva /* Check that N doesn't get too big, so that es doesn't 385212901Scperciva go negative. The maximum value that can be 386212901Scperciva RUNA/RUNB encoded is equal to the block size (post 387212901Scperciva the initial RLE), viz, 900k, so bounding N at 2 388212901Scperciva million should guard against overflow without 389212901Scperciva rejecting any legitimate inputs. */ 390212901Scperciva if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR); 39178556Sobrien if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 39278556Sobrien if (nextSym == BZ_RUNB) es = es + (1+1) * N; 39378556Sobrien N = N * 2; 39478556Sobrien GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 39578556Sobrien } 39678556Sobrien while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 39778556Sobrien 39878556Sobrien es++; 39978556Sobrien uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 40078556Sobrien s->unzftab[uc] += es; 40178556Sobrien 40278556Sobrien if (s->smallDecompress) 40378556Sobrien while (es > 0) { 40478556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 40578556Sobrien s->ll16[nblock] = (UInt16)uc; 40678556Sobrien nblock++; 40778556Sobrien es--; 40878556Sobrien } 40978556Sobrien else 41078556Sobrien while (es > 0) { 41178556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 41278556Sobrien s->tt[nblock] = (UInt32)uc; 41378556Sobrien nblock++; 41478556Sobrien es--; 41578556Sobrien }; 41678556Sobrien 41778556Sobrien continue; 41878556Sobrien 41978556Sobrien } else { 42078556Sobrien 42178556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 42278556Sobrien 42378556Sobrien /*-- uc = MTF ( nextSym-1 ) --*/ 42478556Sobrien { 42578556Sobrien Int32 ii, jj, kk, pp, lno, off; 42678556Sobrien UInt32 nn; 42778556Sobrien nn = (UInt32)(nextSym - 1); 42878556Sobrien 42978556Sobrien if (nn < MTFL_SIZE) { 43078556Sobrien /* avoid general-case expense */ 43178556Sobrien pp = s->mtfbase[0]; 43278556Sobrien uc = s->mtfa[pp+nn]; 43378556Sobrien while (nn > 3) { 43478556Sobrien Int32 z = pp+nn; 43578556Sobrien s->mtfa[(z) ] = s->mtfa[(z)-1]; 43678556Sobrien s->mtfa[(z)-1] = s->mtfa[(z)-2]; 43778556Sobrien s->mtfa[(z)-2] = s->mtfa[(z)-3]; 43878556Sobrien s->mtfa[(z)-3] = s->mtfa[(z)-4]; 43978556Sobrien nn -= 4; 44078556Sobrien } 44178556Sobrien while (nn > 0) { 44278556Sobrien s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 44378556Sobrien }; 44478556Sobrien s->mtfa[pp] = uc; 44578556Sobrien } else { 44678556Sobrien /* general case */ 44778556Sobrien lno = nn / MTFL_SIZE; 44878556Sobrien off = nn % MTFL_SIZE; 44978556Sobrien pp = s->mtfbase[lno] + off; 45078556Sobrien uc = s->mtfa[pp]; 45178556Sobrien while (pp > s->mtfbase[lno]) { 45278556Sobrien s->mtfa[pp] = s->mtfa[pp-1]; pp--; 45378556Sobrien }; 45478556Sobrien s->mtfbase[lno]++; 45578556Sobrien while (lno > 0) { 45678556Sobrien s->mtfbase[lno]--; 45778556Sobrien s->mtfa[s->mtfbase[lno]] 45878556Sobrien = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 45978556Sobrien lno--; 46078556Sobrien } 46178556Sobrien s->mtfbase[0]--; 46278556Sobrien s->mtfa[s->mtfbase[0]] = uc; 46378556Sobrien if (s->mtfbase[0] == 0) { 46478556Sobrien kk = MTFA_SIZE-1; 46578556Sobrien for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 46678556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 46778556Sobrien s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 46878556Sobrien kk--; 46978556Sobrien } 47078556Sobrien s->mtfbase[ii] = kk + 1; 47178556Sobrien } 47278556Sobrien } 47378556Sobrien } 47478556Sobrien } 47578556Sobrien /*-- end uc = MTF ( nextSym-1 ) --*/ 47678556Sobrien 47778556Sobrien s->unzftab[s->seqToUnseq[uc]]++; 47878556Sobrien if (s->smallDecompress) 47978556Sobrien s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 48078556Sobrien s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 48178556Sobrien nblock++; 48278556Sobrien 48378556Sobrien GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 48478556Sobrien continue; 48578556Sobrien } 48678556Sobrien } 48778556Sobrien 48878556Sobrien /* Now we know what nblock is, we can do a better sanity 48978556Sobrien check on s->origPtr. 49078556Sobrien */ 49178556Sobrien if (s->origPtr < 0 || s->origPtr >= nblock) 49278556Sobrien RETURN(BZ_DATA_ERROR); 49378556Sobrien 494146293Sobrien /*-- Set up cftab to facilitate generation of T^(-1) --*/ 495215041Sobrien /* Check: unzftab entries in range. */ 496215041Sobrien for (i = 0; i <= 255; i++) { 497215041Sobrien if (s->unzftab[i] < 0 || s->unzftab[i] > nblock) 498215041Sobrien RETURN(BZ_DATA_ERROR); 499215041Sobrien } 500215041Sobrien /* Actually generate cftab. */ 501146293Sobrien s->cftab[0] = 0; 502146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 503146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 504215041Sobrien /* Check: cftab entries in range. */ 505146293Sobrien for (i = 0; i <= 256; i++) { 506146293Sobrien if (s->cftab[i] < 0 || s->cftab[i] > nblock) { 507146293Sobrien /* s->cftab[i] can legitimately be == nblock */ 508146293Sobrien RETURN(BZ_DATA_ERROR); 509146293Sobrien } 510146293Sobrien } 511215041Sobrien /* Check: cftab entries non-descending. */ 512215041Sobrien for (i = 1; i <= 256; i++) { 513215041Sobrien if (s->cftab[i-1] > s->cftab[i]) { 514215041Sobrien RETURN(BZ_DATA_ERROR); 515215041Sobrien } 516215041Sobrien } 517146293Sobrien 51878556Sobrien s->state_out_len = 0; 51978556Sobrien s->state_out_ch = 0; 52078556Sobrien BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 52178556Sobrien s->state = BZ_X_OUTPUT; 52278556Sobrien if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 52378556Sobrien 52478556Sobrien if (s->smallDecompress) { 52578556Sobrien 52678556Sobrien /*-- Make a copy of cftab, used in generation of T --*/ 52778556Sobrien for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 52878556Sobrien 52978556Sobrien /*-- compute the T vector --*/ 53078556Sobrien for (i = 0; i < nblock; i++) { 53178556Sobrien uc = (UChar)(s->ll16[i]); 53278556Sobrien SET_LL(i, s->cftabCopy[uc]); 53378556Sobrien s->cftabCopy[uc]++; 53478556Sobrien } 53578556Sobrien 53678556Sobrien /*-- Compute T^(-1) by pointer reversal on T --*/ 53778556Sobrien i = s->origPtr; 53878556Sobrien j = GET_LL(i); 53978556Sobrien do { 54078556Sobrien Int32 tmp = GET_LL(j); 54178556Sobrien SET_LL(j, i); 54278556Sobrien i = j; 54378556Sobrien j = tmp; 54478556Sobrien } 54578556Sobrien while (i != s->origPtr); 54678556Sobrien 54778556Sobrien s->tPos = s->origPtr; 54878556Sobrien s->nblock_used = 0; 54978556Sobrien if (s->blockRandomised) { 55078556Sobrien BZ_RAND_INIT_MASK; 55178556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 55278556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 55378556Sobrien } else { 55478556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 55578556Sobrien } 55678556Sobrien 55778556Sobrien } else { 55878556Sobrien 55978556Sobrien /*-- compute the T^(-1) vector --*/ 56078556Sobrien for (i = 0; i < nblock; i++) { 56178556Sobrien uc = (UChar)(s->tt[i] & 0xff); 56278556Sobrien s->tt[s->cftab[uc]] |= (i << 8); 56378556Sobrien s->cftab[uc]++; 56478556Sobrien } 56578556Sobrien 56678556Sobrien s->tPos = s->tt[s->origPtr] >> 8; 56778556Sobrien s->nblock_used = 0; 56878556Sobrien if (s->blockRandomised) { 56978556Sobrien BZ_RAND_INIT_MASK; 57078556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 57178556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 57278556Sobrien } else { 57378556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 57478556Sobrien } 57578556Sobrien 57678556Sobrien } 57778556Sobrien 57878556Sobrien RETURN(BZ_OK); 57978556Sobrien 58078556Sobrien 58178556Sobrien 58278556Sobrien endhdr_2: 58378556Sobrien 58478556Sobrien GET_UCHAR(BZ_X_ENDHDR_2, uc); 58578556Sobrien if (uc != 0x72) RETURN(BZ_DATA_ERROR); 58678556Sobrien GET_UCHAR(BZ_X_ENDHDR_3, uc); 58778556Sobrien if (uc != 0x45) RETURN(BZ_DATA_ERROR); 58878556Sobrien GET_UCHAR(BZ_X_ENDHDR_4, uc); 58978556Sobrien if (uc != 0x38) RETURN(BZ_DATA_ERROR); 59078556Sobrien GET_UCHAR(BZ_X_ENDHDR_5, uc); 59178556Sobrien if (uc != 0x50) RETURN(BZ_DATA_ERROR); 59278556Sobrien GET_UCHAR(BZ_X_ENDHDR_6, uc); 59378556Sobrien if (uc != 0x90) RETURN(BZ_DATA_ERROR); 59478556Sobrien 59578556Sobrien s->storedCombinedCRC = 0; 59678556Sobrien GET_UCHAR(BZ_X_CCRC_1, uc); 59778556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 59878556Sobrien GET_UCHAR(BZ_X_CCRC_2, uc); 59978556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 60078556Sobrien GET_UCHAR(BZ_X_CCRC_3, uc); 60178556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 60278556Sobrien GET_UCHAR(BZ_X_CCRC_4, uc); 60378556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 60478556Sobrien 60578556Sobrien s->state = BZ_X_IDLE; 60678556Sobrien RETURN(BZ_STREAM_END); 60778556Sobrien 60878556Sobrien default: AssertH ( False, 4001 ); 60978556Sobrien } 61078556Sobrien 61178556Sobrien AssertH ( False, 4002 ); 61278556Sobrien 61378556Sobrien save_state_and_return: 61478556Sobrien 61578556Sobrien s->save_i = i; 61678556Sobrien s->save_j = j; 61778556Sobrien s->save_t = t; 61878556Sobrien s->save_alphaSize = alphaSize; 61978556Sobrien s->save_nGroups = nGroups; 62078556Sobrien s->save_nSelectors = nSelectors; 62178556Sobrien s->save_EOB = EOB; 62278556Sobrien s->save_groupNo = groupNo; 62378556Sobrien s->save_groupPos = groupPos; 62478556Sobrien s->save_nextSym = nextSym; 62578556Sobrien s->save_nblockMAX = nblockMAX; 62678556Sobrien s->save_nblock = nblock; 62778556Sobrien s->save_es = es; 62878556Sobrien s->save_N = N; 62978556Sobrien s->save_curr = curr; 63078556Sobrien s->save_zt = zt; 63178556Sobrien s->save_zn = zn; 63278556Sobrien s->save_zvec = zvec; 63378556Sobrien s->save_zj = zj; 63478556Sobrien s->save_gSel = gSel; 63578556Sobrien s->save_gMinlen = gMinlen; 63678556Sobrien s->save_gLimit = gLimit; 63778556Sobrien s->save_gBase = gBase; 63878556Sobrien s->save_gPerm = gPerm; 63978556Sobrien 64078556Sobrien return retVal; 64178556Sobrien} 64278556Sobrien 64378556Sobrien 64478556Sobrien/*-------------------------------------------------------------*/ 64578556Sobrien/*--- end decompress.c ---*/ 64678556Sobrien/*-------------------------------------------------------------*/ 647