decompress.c revision 212901
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 11177420Sdelphij bzip2/libbzip2 version 1.0.5 of 10 December 2007 12177420Sdelphij Copyright (C) 1996-2007 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) --*/ 495146293Sobrien s->cftab[0] = 0; 496146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 497146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 498146293Sobrien for (i = 0; i <= 256; i++) { 499146293Sobrien if (s->cftab[i] < 0 || s->cftab[i] > nblock) { 500146293Sobrien /* s->cftab[i] can legitimately be == nblock */ 501146293Sobrien RETURN(BZ_DATA_ERROR); 502146293Sobrien } 503146293Sobrien } 504146293Sobrien 50578556Sobrien s->state_out_len = 0; 50678556Sobrien s->state_out_ch = 0; 50778556Sobrien BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 50878556Sobrien s->state = BZ_X_OUTPUT; 50978556Sobrien if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 51078556Sobrien 51178556Sobrien if (s->smallDecompress) { 51278556Sobrien 51378556Sobrien /*-- Make a copy of cftab, used in generation of T --*/ 51478556Sobrien for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 51578556Sobrien 51678556Sobrien /*-- compute the T vector --*/ 51778556Sobrien for (i = 0; i < nblock; i++) { 51878556Sobrien uc = (UChar)(s->ll16[i]); 51978556Sobrien SET_LL(i, s->cftabCopy[uc]); 52078556Sobrien s->cftabCopy[uc]++; 52178556Sobrien } 52278556Sobrien 52378556Sobrien /*-- Compute T^(-1) by pointer reversal on T --*/ 52478556Sobrien i = s->origPtr; 52578556Sobrien j = GET_LL(i); 52678556Sobrien do { 52778556Sobrien Int32 tmp = GET_LL(j); 52878556Sobrien SET_LL(j, i); 52978556Sobrien i = j; 53078556Sobrien j = tmp; 53178556Sobrien } 53278556Sobrien while (i != s->origPtr); 53378556Sobrien 53478556Sobrien s->tPos = s->origPtr; 53578556Sobrien s->nblock_used = 0; 53678556Sobrien if (s->blockRandomised) { 53778556Sobrien BZ_RAND_INIT_MASK; 53878556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 53978556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 54078556Sobrien } else { 54178556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 54278556Sobrien } 54378556Sobrien 54478556Sobrien } else { 54578556Sobrien 54678556Sobrien /*-- compute the T^(-1) vector --*/ 54778556Sobrien for (i = 0; i < nblock; i++) { 54878556Sobrien uc = (UChar)(s->tt[i] & 0xff); 54978556Sobrien s->tt[s->cftab[uc]] |= (i << 8); 55078556Sobrien s->cftab[uc]++; 55178556Sobrien } 55278556Sobrien 55378556Sobrien s->tPos = s->tt[s->origPtr] >> 8; 55478556Sobrien s->nblock_used = 0; 55578556Sobrien if (s->blockRandomised) { 55678556Sobrien BZ_RAND_INIT_MASK; 55778556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 55878556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 55978556Sobrien } else { 56078556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 56178556Sobrien } 56278556Sobrien 56378556Sobrien } 56478556Sobrien 56578556Sobrien RETURN(BZ_OK); 56678556Sobrien 56778556Sobrien 56878556Sobrien 56978556Sobrien endhdr_2: 57078556Sobrien 57178556Sobrien GET_UCHAR(BZ_X_ENDHDR_2, uc); 57278556Sobrien if (uc != 0x72) RETURN(BZ_DATA_ERROR); 57378556Sobrien GET_UCHAR(BZ_X_ENDHDR_3, uc); 57478556Sobrien if (uc != 0x45) RETURN(BZ_DATA_ERROR); 57578556Sobrien GET_UCHAR(BZ_X_ENDHDR_4, uc); 57678556Sobrien if (uc != 0x38) RETURN(BZ_DATA_ERROR); 57778556Sobrien GET_UCHAR(BZ_X_ENDHDR_5, uc); 57878556Sobrien if (uc != 0x50) RETURN(BZ_DATA_ERROR); 57978556Sobrien GET_UCHAR(BZ_X_ENDHDR_6, uc); 58078556Sobrien if (uc != 0x90) RETURN(BZ_DATA_ERROR); 58178556Sobrien 58278556Sobrien s->storedCombinedCRC = 0; 58378556Sobrien GET_UCHAR(BZ_X_CCRC_1, uc); 58478556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 58578556Sobrien GET_UCHAR(BZ_X_CCRC_2, uc); 58678556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 58778556Sobrien GET_UCHAR(BZ_X_CCRC_3, uc); 58878556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 58978556Sobrien GET_UCHAR(BZ_X_CCRC_4, uc); 59078556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 59178556Sobrien 59278556Sobrien s->state = BZ_X_IDLE; 59378556Sobrien RETURN(BZ_STREAM_END); 59478556Sobrien 59578556Sobrien default: AssertH ( False, 4001 ); 59678556Sobrien } 59778556Sobrien 59878556Sobrien AssertH ( False, 4002 ); 59978556Sobrien 60078556Sobrien save_state_and_return: 60178556Sobrien 60278556Sobrien s->save_i = i; 60378556Sobrien s->save_j = j; 60478556Sobrien s->save_t = t; 60578556Sobrien s->save_alphaSize = alphaSize; 60678556Sobrien s->save_nGroups = nGroups; 60778556Sobrien s->save_nSelectors = nSelectors; 60878556Sobrien s->save_EOB = EOB; 60978556Sobrien s->save_groupNo = groupNo; 61078556Sobrien s->save_groupPos = groupPos; 61178556Sobrien s->save_nextSym = nextSym; 61278556Sobrien s->save_nblockMAX = nblockMAX; 61378556Sobrien s->save_nblock = nblock; 61478556Sobrien s->save_es = es; 61578556Sobrien s->save_N = N; 61678556Sobrien s->save_curr = curr; 61778556Sobrien s->save_zt = zt; 61878556Sobrien s->save_zn = zn; 61978556Sobrien s->save_zvec = zvec; 62078556Sobrien s->save_zj = zj; 62178556Sobrien s->save_gSel = gSel; 62278556Sobrien s->save_gMinlen = gMinlen; 62378556Sobrien s->save_gLimit = gLimit; 62478556Sobrien s->save_gBase = gBase; 62578556Sobrien s->save_gPerm = gPerm; 62678556Sobrien 62778556Sobrien return retVal; 62878556Sobrien} 62978556Sobrien 63078556Sobrien 63178556Sobrien/*-------------------------------------------------------------*/ 63278556Sobrien/*--- end decompress.c ---*/ 63378556Sobrien/*-------------------------------------------------------------*/ 634