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 11351007Sdelphij bzip2/libbzip2 version 1.0.8 of 13 July 2019 12351007Sdelphij Copyright (C) 1996-2019 Julian Seward <jseward@acm.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); 288349718Sdelphij if (nGroups < 2 || nGroups > BZ_N_GROUPS) RETURN(BZ_DATA_ERROR); 28978556Sobrien GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 290351007Sdelphij 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 } 299351007Sdelphij /* Having more than BZ_MAX_SELECTORS doesn't make much sense 300351007Sdelphij since they will never be used, but some implementations might 301351007Sdelphij "round up" the number of selectors, so just ignore those. */ 302351007Sdelphij if (i < BZ_MAX_SELECTORS) 303351007Sdelphij s->selectorMtf[i] = j; 30478556Sobrien } 305351007Sdelphij if (nSelectors > BZ_MAX_SELECTORS) 306351007Sdelphij nSelectors = BZ_MAX_SELECTORS; 30778556Sobrien 30878556Sobrien /*--- Undo the MTF values for the selectors. ---*/ 30978556Sobrien { 31078556Sobrien UChar pos[BZ_N_GROUPS], tmp, v; 31178556Sobrien for (v = 0; v < nGroups; v++) pos[v] = v; 31278556Sobrien 31378556Sobrien for (i = 0; i < nSelectors; i++) { 31478556Sobrien v = s->selectorMtf[i]; 31578556Sobrien tmp = pos[v]; 31678556Sobrien while (v > 0) { pos[v] = pos[v-1]; v--; } 31778556Sobrien pos[0] = tmp; 31878556Sobrien s->selector[i] = tmp; 31978556Sobrien } 32078556Sobrien } 32178556Sobrien 32278556Sobrien /*--- Now the coding tables ---*/ 32378556Sobrien for (t = 0; t < nGroups; t++) { 32478556Sobrien GET_BITS(BZ_X_CODING_1, curr, 5); 32578556Sobrien for (i = 0; i < alphaSize; i++) { 32678556Sobrien while (True) { 32778556Sobrien if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 32878556Sobrien GET_BIT(BZ_X_CODING_2, uc); 32978556Sobrien if (uc == 0) break; 33078556Sobrien GET_BIT(BZ_X_CODING_3, uc); 33178556Sobrien if (uc == 0) curr++; else curr--; 33278556Sobrien } 33378556Sobrien s->len[t][i] = curr; 33478556Sobrien } 33578556Sobrien } 33678556Sobrien 33778556Sobrien /*--- Create the Huffman decoding tables ---*/ 33878556Sobrien for (t = 0; t < nGroups; t++) { 33978556Sobrien minLen = 32; 34078556Sobrien maxLen = 0; 34178556Sobrien for (i = 0; i < alphaSize; i++) { 34278556Sobrien if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 34378556Sobrien if (s->len[t][i] < minLen) minLen = s->len[t][i]; 34478556Sobrien } 34578556Sobrien BZ2_hbCreateDecodeTables ( 34678556Sobrien &(s->limit[t][0]), 34778556Sobrien &(s->base[t][0]), 34878556Sobrien &(s->perm[t][0]), 34978556Sobrien &(s->len[t][0]), 35078556Sobrien minLen, maxLen, alphaSize 35178556Sobrien ); 35278556Sobrien s->minLens[t] = minLen; 35378556Sobrien } 35478556Sobrien 35578556Sobrien /*--- Now the MTF values ---*/ 35678556Sobrien 35778556Sobrien EOB = s->nInUse+1; 35878556Sobrien nblockMAX = 100000 * s->blockSize100k; 35978556Sobrien groupNo = -1; 36078556Sobrien groupPos = 0; 36178556Sobrien 36278556Sobrien for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 36378556Sobrien 36478556Sobrien /*-- MTF init --*/ 36578556Sobrien { 36678556Sobrien Int32 ii, jj, kk; 36778556Sobrien kk = MTFA_SIZE-1; 36878556Sobrien for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 36978556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 37078556Sobrien s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 37178556Sobrien kk--; 37278556Sobrien } 37378556Sobrien s->mtfbase[ii] = kk + 1; 37478556Sobrien } 37578556Sobrien } 37678556Sobrien /*-- end MTF init --*/ 37778556Sobrien 37878556Sobrien nblock = 0; 37978556Sobrien GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 38078556Sobrien 38178556Sobrien while (True) { 38278556Sobrien 38378556Sobrien if (nextSym == EOB) break; 38478556Sobrien 38578556Sobrien if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 38678556Sobrien 38778556Sobrien es = -1; 38878556Sobrien N = 1; 38978556Sobrien do { 390212901Scperciva /* Check that N doesn't get too big, so that es doesn't 391212901Scperciva go negative. The maximum value that can be 392212901Scperciva RUNA/RUNB encoded is equal to the block size (post 393212901Scperciva the initial RLE), viz, 900k, so bounding N at 2 394212901Scperciva million should guard against overflow without 395212901Scperciva rejecting any legitimate inputs. */ 396212901Scperciva if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR); 39778556Sobrien if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 39878556Sobrien if (nextSym == BZ_RUNB) es = es + (1+1) * N; 39978556Sobrien N = N * 2; 40078556Sobrien GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 40178556Sobrien } 40278556Sobrien while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 40378556Sobrien 40478556Sobrien es++; 40578556Sobrien uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 40678556Sobrien s->unzftab[uc] += es; 40778556Sobrien 40878556Sobrien if (s->smallDecompress) 40978556Sobrien while (es > 0) { 41078556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 41178556Sobrien s->ll16[nblock] = (UInt16)uc; 41278556Sobrien nblock++; 41378556Sobrien es--; 41478556Sobrien } 41578556Sobrien else 41678556Sobrien while (es > 0) { 41778556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 41878556Sobrien s->tt[nblock] = (UInt32)uc; 41978556Sobrien nblock++; 42078556Sobrien es--; 42178556Sobrien }; 42278556Sobrien 42378556Sobrien continue; 42478556Sobrien 42578556Sobrien } else { 42678556Sobrien 42778556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 42878556Sobrien 42978556Sobrien /*-- uc = MTF ( nextSym-1 ) --*/ 43078556Sobrien { 43178556Sobrien Int32 ii, jj, kk, pp, lno, off; 43278556Sobrien UInt32 nn; 43378556Sobrien nn = (UInt32)(nextSym - 1); 43478556Sobrien 43578556Sobrien if (nn < MTFL_SIZE) { 43678556Sobrien /* avoid general-case expense */ 43778556Sobrien pp = s->mtfbase[0]; 43878556Sobrien uc = s->mtfa[pp+nn]; 43978556Sobrien while (nn > 3) { 44078556Sobrien Int32 z = pp+nn; 44178556Sobrien s->mtfa[(z) ] = s->mtfa[(z)-1]; 44278556Sobrien s->mtfa[(z)-1] = s->mtfa[(z)-2]; 44378556Sobrien s->mtfa[(z)-2] = s->mtfa[(z)-3]; 44478556Sobrien s->mtfa[(z)-3] = s->mtfa[(z)-4]; 44578556Sobrien nn -= 4; 44678556Sobrien } 44778556Sobrien while (nn > 0) { 44878556Sobrien s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 44978556Sobrien }; 45078556Sobrien s->mtfa[pp] = uc; 45178556Sobrien } else { 45278556Sobrien /* general case */ 45378556Sobrien lno = nn / MTFL_SIZE; 45478556Sobrien off = nn % MTFL_SIZE; 45578556Sobrien pp = s->mtfbase[lno] + off; 45678556Sobrien uc = s->mtfa[pp]; 45778556Sobrien while (pp > s->mtfbase[lno]) { 45878556Sobrien s->mtfa[pp] = s->mtfa[pp-1]; pp--; 45978556Sobrien }; 46078556Sobrien s->mtfbase[lno]++; 46178556Sobrien while (lno > 0) { 46278556Sobrien s->mtfbase[lno]--; 46378556Sobrien s->mtfa[s->mtfbase[lno]] 46478556Sobrien = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 46578556Sobrien lno--; 46678556Sobrien } 46778556Sobrien s->mtfbase[0]--; 46878556Sobrien s->mtfa[s->mtfbase[0]] = uc; 46978556Sobrien if (s->mtfbase[0] == 0) { 47078556Sobrien kk = MTFA_SIZE-1; 47178556Sobrien for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 47278556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 47378556Sobrien s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 47478556Sobrien kk--; 47578556Sobrien } 47678556Sobrien s->mtfbase[ii] = kk + 1; 47778556Sobrien } 47878556Sobrien } 47978556Sobrien } 48078556Sobrien } 48178556Sobrien /*-- end uc = MTF ( nextSym-1 ) --*/ 48278556Sobrien 48378556Sobrien s->unzftab[s->seqToUnseq[uc]]++; 48478556Sobrien if (s->smallDecompress) 48578556Sobrien s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 48678556Sobrien s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 48778556Sobrien nblock++; 48878556Sobrien 48978556Sobrien GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 49078556Sobrien continue; 49178556Sobrien } 49278556Sobrien } 49378556Sobrien 49478556Sobrien /* Now we know what nblock is, we can do a better sanity 49578556Sobrien check on s->origPtr. 49678556Sobrien */ 49778556Sobrien if (s->origPtr < 0 || s->origPtr >= nblock) 49878556Sobrien RETURN(BZ_DATA_ERROR); 49978556Sobrien 500146293Sobrien /*-- Set up cftab to facilitate generation of T^(-1) --*/ 501215041Sobrien /* Check: unzftab entries in range. */ 502215041Sobrien for (i = 0; i <= 255; i++) { 503215041Sobrien if (s->unzftab[i] < 0 || s->unzftab[i] > nblock) 504215041Sobrien RETURN(BZ_DATA_ERROR); 505215041Sobrien } 506215041Sobrien /* Actually generate cftab. */ 507146293Sobrien s->cftab[0] = 0; 508146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 509146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 510215041Sobrien /* Check: cftab entries in range. */ 511146293Sobrien for (i = 0; i <= 256; i++) { 512146293Sobrien if (s->cftab[i] < 0 || s->cftab[i] > nblock) { 513146293Sobrien /* s->cftab[i] can legitimately be == nblock */ 514146293Sobrien RETURN(BZ_DATA_ERROR); 515146293Sobrien } 516146293Sobrien } 517215041Sobrien /* Check: cftab entries non-descending. */ 518215041Sobrien for (i = 1; i <= 256; i++) { 519215041Sobrien if (s->cftab[i-1] > s->cftab[i]) { 520215041Sobrien RETURN(BZ_DATA_ERROR); 521215041Sobrien } 522215041Sobrien } 523146293Sobrien 52478556Sobrien s->state_out_len = 0; 52578556Sobrien s->state_out_ch = 0; 52678556Sobrien BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 52778556Sobrien s->state = BZ_X_OUTPUT; 52878556Sobrien if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 52978556Sobrien 53078556Sobrien if (s->smallDecompress) { 53178556Sobrien 53278556Sobrien /*-- Make a copy of cftab, used in generation of T --*/ 53378556Sobrien for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 53478556Sobrien 53578556Sobrien /*-- compute the T vector --*/ 53678556Sobrien for (i = 0; i < nblock; i++) { 53778556Sobrien uc = (UChar)(s->ll16[i]); 53878556Sobrien SET_LL(i, s->cftabCopy[uc]); 53978556Sobrien s->cftabCopy[uc]++; 54078556Sobrien } 54178556Sobrien 54278556Sobrien /*-- Compute T^(-1) by pointer reversal on T --*/ 54378556Sobrien i = s->origPtr; 54478556Sobrien j = GET_LL(i); 54578556Sobrien do { 54678556Sobrien Int32 tmp = GET_LL(j); 54778556Sobrien SET_LL(j, i); 54878556Sobrien i = j; 54978556Sobrien j = tmp; 55078556Sobrien } 55178556Sobrien while (i != s->origPtr); 55278556Sobrien 55378556Sobrien s->tPos = s->origPtr; 55478556Sobrien s->nblock_used = 0; 55578556Sobrien if (s->blockRandomised) { 55678556Sobrien BZ_RAND_INIT_MASK; 55778556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 55878556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 55978556Sobrien } else { 56078556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 56178556Sobrien } 56278556Sobrien 56378556Sobrien } else { 56478556Sobrien 56578556Sobrien /*-- compute the T^(-1) vector --*/ 56678556Sobrien for (i = 0; i < nblock; i++) { 56778556Sobrien uc = (UChar)(s->tt[i] & 0xff); 56878556Sobrien s->tt[s->cftab[uc]] |= (i << 8); 56978556Sobrien s->cftab[uc]++; 57078556Sobrien } 57178556Sobrien 57278556Sobrien s->tPos = s->tt[s->origPtr] >> 8; 57378556Sobrien s->nblock_used = 0; 57478556Sobrien if (s->blockRandomised) { 57578556Sobrien BZ_RAND_INIT_MASK; 57678556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 57778556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 57878556Sobrien } else { 57978556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 58078556Sobrien } 58178556Sobrien 58278556Sobrien } 58378556Sobrien 58478556Sobrien RETURN(BZ_OK); 58578556Sobrien 58678556Sobrien 58778556Sobrien 58878556Sobrien endhdr_2: 58978556Sobrien 59078556Sobrien GET_UCHAR(BZ_X_ENDHDR_2, uc); 59178556Sobrien if (uc != 0x72) RETURN(BZ_DATA_ERROR); 59278556Sobrien GET_UCHAR(BZ_X_ENDHDR_3, uc); 59378556Sobrien if (uc != 0x45) RETURN(BZ_DATA_ERROR); 59478556Sobrien GET_UCHAR(BZ_X_ENDHDR_4, uc); 59578556Sobrien if (uc != 0x38) RETURN(BZ_DATA_ERROR); 59678556Sobrien GET_UCHAR(BZ_X_ENDHDR_5, uc); 59778556Sobrien if (uc != 0x50) RETURN(BZ_DATA_ERROR); 59878556Sobrien GET_UCHAR(BZ_X_ENDHDR_6, uc); 59978556Sobrien if (uc != 0x90) RETURN(BZ_DATA_ERROR); 60078556Sobrien 60178556Sobrien s->storedCombinedCRC = 0; 60278556Sobrien GET_UCHAR(BZ_X_CCRC_1, uc); 60378556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 60478556Sobrien GET_UCHAR(BZ_X_CCRC_2, uc); 60578556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 60678556Sobrien GET_UCHAR(BZ_X_CCRC_3, uc); 60778556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 60878556Sobrien GET_UCHAR(BZ_X_CCRC_4, uc); 60978556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 61078556Sobrien 61178556Sobrien s->state = BZ_X_IDLE; 61278556Sobrien RETURN(BZ_STREAM_END); 61378556Sobrien 61478556Sobrien default: AssertH ( False, 4001 ); 61578556Sobrien } 61678556Sobrien 61778556Sobrien AssertH ( False, 4002 ); 61878556Sobrien 61978556Sobrien save_state_and_return: 62078556Sobrien 62178556Sobrien s->save_i = i; 62278556Sobrien s->save_j = j; 62378556Sobrien s->save_t = t; 62478556Sobrien s->save_alphaSize = alphaSize; 62578556Sobrien s->save_nGroups = nGroups; 62678556Sobrien s->save_nSelectors = nSelectors; 62778556Sobrien s->save_EOB = EOB; 62878556Sobrien s->save_groupNo = groupNo; 62978556Sobrien s->save_groupPos = groupPos; 63078556Sobrien s->save_nextSym = nextSym; 63178556Sobrien s->save_nblockMAX = nblockMAX; 63278556Sobrien s->save_nblock = nblock; 63378556Sobrien s->save_es = es; 63478556Sobrien s->save_N = N; 63578556Sobrien s->save_curr = curr; 63678556Sobrien s->save_zt = zt; 63778556Sobrien s->save_zn = zn; 63878556Sobrien s->save_zvec = zvec; 63978556Sobrien s->save_zj = zj; 64078556Sobrien s->save_gSel = gSel; 64178556Sobrien s->save_gMinlen = gMinlen; 64278556Sobrien s->save_gLimit = gLimit; 64378556Sobrien s->save_gBase = gBase; 64478556Sobrien s->save_gPerm = gPerm; 64578556Sobrien 64678556Sobrien return retVal; 64778556Sobrien} 64878556Sobrien 64978556Sobrien 65078556Sobrien/*-------------------------------------------------------------*/ 65178556Sobrien/*--- end decompress.c ---*/ 65278556Sobrien/*-------------------------------------------------------------*/ 653