decompress.c revision 146293
178556Sobrien 278556Sobrien/*-------------------------------------------------------------*/ 378556Sobrien/*--- Decompression machinery ---*/ 478556Sobrien/*--- decompress.c ---*/ 578556Sobrien/*-------------------------------------------------------------*/ 678556Sobrien 778556Sobrien/*-- 878556Sobrien This file is a part of bzip2 and/or libbzip2, a program and 978556Sobrien library for lossless, block-sorting data compression. 1078556Sobrien 11146293Sobrien Copyright (C) 1996-2005 Julian R Seward. All rights reserved. 1278556Sobrien 1378556Sobrien Redistribution and use in source and binary forms, with or without 1478556Sobrien modification, are permitted provided that the following conditions 1578556Sobrien are met: 1678556Sobrien 1778556Sobrien 1. Redistributions of source code must retain the above copyright 1878556Sobrien notice, this list of conditions and the following disclaimer. 1978556Sobrien 2078556Sobrien 2. The origin of this software must not be misrepresented; you must 2178556Sobrien not claim that you wrote the original software. If you use this 2278556Sobrien software in a product, an acknowledgment in the product 2378556Sobrien documentation would be appreciated but is not required. 2478556Sobrien 2578556Sobrien 3. Altered source versions must be plainly marked as such, and must 2678556Sobrien not be misrepresented as being the original software. 2778556Sobrien 2878556Sobrien 4. The name of the author may not be used to endorse or promote 2978556Sobrien products derived from this software without specific prior written 3078556Sobrien permission. 3178556Sobrien 3278556Sobrien THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 3378556Sobrien OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 3478556Sobrien WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 3578556Sobrien ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 3678556Sobrien DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 3778556Sobrien DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 3878556Sobrien GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 3978556Sobrien INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 4078556Sobrien WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 4178556Sobrien NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 4278556Sobrien SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 4378556Sobrien 4478556Sobrien Julian Seward, Cambridge, UK. 45146293Sobrien jseward@bzip.org 4678556Sobrien bzip2/libbzip2 version 1.0 of 21 March 2000 4778556Sobrien 4878556Sobrien This program is based on (at least) the work of: 4978556Sobrien Mike Burrows 5078556Sobrien David Wheeler 5178556Sobrien Peter Fenwick 5278556Sobrien Alistair Moffat 5378556Sobrien Radford Neal 5478556Sobrien Ian H. Witten 5578556Sobrien Robert Sedgewick 5678556Sobrien Jon L. Bentley 5778556Sobrien 5878556Sobrien For more information on these sources, see the manual. 5978556Sobrien--*/ 6078556Sobrien 6178556Sobrien 6278556Sobrien#include "bzlib_private.h" 6378556Sobrien 6478556Sobrien 6578556Sobrien/*---------------------------------------------------*/ 6678556Sobrienstatic 6778556Sobrienvoid makeMaps_d ( DState* s ) 6878556Sobrien{ 6978556Sobrien Int32 i; 7078556Sobrien s->nInUse = 0; 7178556Sobrien for (i = 0; i < 256; i++) 7278556Sobrien if (s->inUse[i]) { 7378556Sobrien s->seqToUnseq[s->nInUse] = i; 7478556Sobrien s->nInUse++; 7578556Sobrien } 7678556Sobrien} 7778556Sobrien 7878556Sobrien 7978556Sobrien/*---------------------------------------------------*/ 8078556Sobrien#define RETURN(rrr) \ 8178556Sobrien { retVal = rrr; goto save_state_and_return; }; 8278556Sobrien 8378556Sobrien#define GET_BITS(lll,vvv,nnn) \ 8478556Sobrien case lll: s->state = lll; \ 8578556Sobrien while (True) { \ 8678556Sobrien if (s->bsLive >= nnn) { \ 8778556Sobrien UInt32 v; \ 8878556Sobrien v = (s->bsBuff >> \ 8978556Sobrien (s->bsLive-nnn)) & ((1 << nnn)-1); \ 9078556Sobrien s->bsLive -= nnn; \ 9178556Sobrien vvv = v; \ 9278556Sobrien break; \ 9378556Sobrien } \ 9478556Sobrien if (s->strm->avail_in == 0) RETURN(BZ_OK); \ 9578556Sobrien s->bsBuff \ 9678556Sobrien = (s->bsBuff << 8) | \ 9778556Sobrien ((UInt32) \ 9878556Sobrien (*((UChar*)(s->strm->next_in)))); \ 9978556Sobrien s->bsLive += 8; \ 10078556Sobrien s->strm->next_in++; \ 10178556Sobrien s->strm->avail_in--; \ 10278556Sobrien s->strm->total_in_lo32++; \ 10378556Sobrien if (s->strm->total_in_lo32 == 0) \ 10478556Sobrien s->strm->total_in_hi32++; \ 10578556Sobrien } 10678556Sobrien 10778556Sobrien#define GET_UCHAR(lll,uuu) \ 10878556Sobrien GET_BITS(lll,uuu,8) 10978556Sobrien 11078556Sobrien#define GET_BIT(lll,uuu) \ 11178556Sobrien GET_BITS(lll,uuu,1) 11278556Sobrien 11378556Sobrien/*---------------------------------------------------*/ 11478556Sobrien#define GET_MTF_VAL(label1,label2,lval) \ 11578556Sobrien{ \ 11678556Sobrien if (groupPos == 0) { \ 11778556Sobrien groupNo++; \ 11878556Sobrien if (groupNo >= nSelectors) \ 11978556Sobrien RETURN(BZ_DATA_ERROR); \ 12078556Sobrien groupPos = BZ_G_SIZE; \ 12178556Sobrien gSel = s->selector[groupNo]; \ 12278556Sobrien gMinlen = s->minLens[gSel]; \ 12378556Sobrien gLimit = &(s->limit[gSel][0]); \ 12478556Sobrien gPerm = &(s->perm[gSel][0]); \ 12578556Sobrien gBase = &(s->base[gSel][0]); \ 12678556Sobrien } \ 12778556Sobrien groupPos--; \ 12878556Sobrien zn = gMinlen; \ 12978556Sobrien GET_BITS(label1, zvec, zn); \ 13078556Sobrien while (1) { \ 13178556Sobrien if (zn > 20 /* the longest code */) \ 13278556Sobrien RETURN(BZ_DATA_ERROR); \ 13378556Sobrien if (zvec <= gLimit[zn]) break; \ 13478556Sobrien zn++; \ 13578556Sobrien GET_BIT(label2, zj); \ 13678556Sobrien zvec = (zvec << 1) | zj; \ 13778556Sobrien }; \ 13878556Sobrien if (zvec - gBase[zn] < 0 \ 13978556Sobrien || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ 14078556Sobrien RETURN(BZ_DATA_ERROR); \ 14178556Sobrien lval = gPerm[zvec - gBase[zn]]; \ 14278556Sobrien} 14378556Sobrien 14478556Sobrien 14578556Sobrien/*---------------------------------------------------*/ 14678556SobrienInt32 BZ2_decompress ( DState* s ) 14778556Sobrien{ 14878556Sobrien UChar uc; 14978556Sobrien Int32 retVal; 15078556Sobrien Int32 minLen, maxLen; 15178556Sobrien bz_stream* strm = s->strm; 15278556Sobrien 15378556Sobrien /* stuff that needs to be saved/restored */ 15478556Sobrien Int32 i; 15578556Sobrien Int32 j; 15678556Sobrien Int32 t; 15778556Sobrien Int32 alphaSize; 15878556Sobrien Int32 nGroups; 15978556Sobrien Int32 nSelectors; 16078556Sobrien Int32 EOB; 16178556Sobrien Int32 groupNo; 16278556Sobrien Int32 groupPos; 16378556Sobrien Int32 nextSym; 16478556Sobrien Int32 nblockMAX; 16578556Sobrien Int32 nblock; 16678556Sobrien Int32 es; 16778556Sobrien Int32 N; 16878556Sobrien Int32 curr; 16978556Sobrien Int32 zt; 17078556Sobrien Int32 zn; 17178556Sobrien Int32 zvec; 17278556Sobrien Int32 zj; 17378556Sobrien Int32 gSel; 17478556Sobrien Int32 gMinlen; 17578556Sobrien Int32* gLimit; 17678556Sobrien Int32* gBase; 17778556Sobrien Int32* gPerm; 17878556Sobrien 17978556Sobrien if (s->state == BZ_X_MAGIC_1) { 18078556Sobrien /*initialise the save area*/ 18178556Sobrien s->save_i = 0; 18278556Sobrien s->save_j = 0; 18378556Sobrien s->save_t = 0; 18478556Sobrien s->save_alphaSize = 0; 18578556Sobrien s->save_nGroups = 0; 18678556Sobrien s->save_nSelectors = 0; 18778556Sobrien s->save_EOB = 0; 18878556Sobrien s->save_groupNo = 0; 18978556Sobrien s->save_groupPos = 0; 19078556Sobrien s->save_nextSym = 0; 19178556Sobrien s->save_nblockMAX = 0; 19278556Sobrien s->save_nblock = 0; 19378556Sobrien s->save_es = 0; 19478556Sobrien s->save_N = 0; 19578556Sobrien s->save_curr = 0; 19678556Sobrien s->save_zt = 0; 19778556Sobrien s->save_zn = 0; 19878556Sobrien s->save_zvec = 0; 19978556Sobrien s->save_zj = 0; 20078556Sobrien s->save_gSel = 0; 20178556Sobrien s->save_gMinlen = 0; 20278556Sobrien s->save_gLimit = NULL; 20378556Sobrien s->save_gBase = NULL; 20478556Sobrien s->save_gPerm = NULL; 20578556Sobrien } 20678556Sobrien 20778556Sobrien /*restore from the save area*/ 20878556Sobrien i = s->save_i; 20978556Sobrien j = s->save_j; 21078556Sobrien t = s->save_t; 21178556Sobrien alphaSize = s->save_alphaSize; 21278556Sobrien nGroups = s->save_nGroups; 21378556Sobrien nSelectors = s->save_nSelectors; 21478556Sobrien EOB = s->save_EOB; 21578556Sobrien groupNo = s->save_groupNo; 21678556Sobrien groupPos = s->save_groupPos; 21778556Sobrien nextSym = s->save_nextSym; 21878556Sobrien nblockMAX = s->save_nblockMAX; 21978556Sobrien nblock = s->save_nblock; 22078556Sobrien es = s->save_es; 22178556Sobrien N = s->save_N; 22278556Sobrien curr = s->save_curr; 22378556Sobrien zt = s->save_zt; 22478556Sobrien zn = s->save_zn; 22578556Sobrien zvec = s->save_zvec; 22678556Sobrien zj = s->save_zj; 22778556Sobrien gSel = s->save_gSel; 22878556Sobrien gMinlen = s->save_gMinlen; 22978556Sobrien gLimit = s->save_gLimit; 23078556Sobrien gBase = s->save_gBase; 23178556Sobrien gPerm = s->save_gPerm; 23278556Sobrien 23378556Sobrien retVal = BZ_OK; 23478556Sobrien 23578556Sobrien switch (s->state) { 23678556Sobrien 23778556Sobrien GET_UCHAR(BZ_X_MAGIC_1, uc); 23890067Ssobomax if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); 23978556Sobrien 24078556Sobrien GET_UCHAR(BZ_X_MAGIC_2, uc); 24190067Ssobomax if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); 24278556Sobrien 24378556Sobrien GET_UCHAR(BZ_X_MAGIC_3, uc) 24490067Ssobomax if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); 24578556Sobrien 24678556Sobrien GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 24790067Ssobomax if (s->blockSize100k < (BZ_HDR_0 + 1) || 24890067Ssobomax s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); 24990067Ssobomax s->blockSize100k -= BZ_HDR_0; 25078556Sobrien 25178556Sobrien if (s->smallDecompress) { 25278556Sobrien s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 25378556Sobrien s->ll4 = BZALLOC( 25478556Sobrien ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 25578556Sobrien ); 25678556Sobrien if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 25778556Sobrien } else { 25878556Sobrien s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 25978556Sobrien if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 26078556Sobrien } 26178556Sobrien 26278556Sobrien GET_UCHAR(BZ_X_BLKHDR_1, uc); 26378556Sobrien 26478556Sobrien if (uc == 0x17) goto endhdr_2; 26578556Sobrien if (uc != 0x31) RETURN(BZ_DATA_ERROR); 26678556Sobrien GET_UCHAR(BZ_X_BLKHDR_2, uc); 26778556Sobrien if (uc != 0x41) RETURN(BZ_DATA_ERROR); 26878556Sobrien GET_UCHAR(BZ_X_BLKHDR_3, uc); 26978556Sobrien if (uc != 0x59) RETURN(BZ_DATA_ERROR); 27078556Sobrien GET_UCHAR(BZ_X_BLKHDR_4, uc); 27178556Sobrien if (uc != 0x26) RETURN(BZ_DATA_ERROR); 27278556Sobrien GET_UCHAR(BZ_X_BLKHDR_5, uc); 27378556Sobrien if (uc != 0x53) RETURN(BZ_DATA_ERROR); 27478556Sobrien GET_UCHAR(BZ_X_BLKHDR_6, uc); 27578556Sobrien if (uc != 0x59) RETURN(BZ_DATA_ERROR); 27678556Sobrien 27778556Sobrien s->currBlockNo++; 27878556Sobrien if (s->verbosity >= 2) 27978556Sobrien VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 28078556Sobrien 28178556Sobrien s->storedBlockCRC = 0; 28278556Sobrien GET_UCHAR(BZ_X_BCRC_1, uc); 28378556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 28478556Sobrien GET_UCHAR(BZ_X_BCRC_2, uc); 28578556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 28678556Sobrien GET_UCHAR(BZ_X_BCRC_3, uc); 28778556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 28878556Sobrien GET_UCHAR(BZ_X_BCRC_4, uc); 28978556Sobrien s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 29078556Sobrien 29178556Sobrien GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 29278556Sobrien 29378556Sobrien s->origPtr = 0; 29478556Sobrien GET_UCHAR(BZ_X_ORIGPTR_1, uc); 29578556Sobrien s->origPtr = (s->origPtr << 8) | ((Int32)uc); 29678556Sobrien GET_UCHAR(BZ_X_ORIGPTR_2, uc); 29778556Sobrien s->origPtr = (s->origPtr << 8) | ((Int32)uc); 29878556Sobrien GET_UCHAR(BZ_X_ORIGPTR_3, uc); 29978556Sobrien s->origPtr = (s->origPtr << 8) | ((Int32)uc); 30078556Sobrien 30178556Sobrien if (s->origPtr < 0) 30278556Sobrien RETURN(BZ_DATA_ERROR); 30378556Sobrien if (s->origPtr > 10 + 100000*s->blockSize100k) 30478556Sobrien RETURN(BZ_DATA_ERROR); 30578556Sobrien 30678556Sobrien /*--- Receive the mapping table ---*/ 30778556Sobrien for (i = 0; i < 16; i++) { 30878556Sobrien GET_BIT(BZ_X_MAPPING_1, uc); 30978556Sobrien if (uc == 1) 31078556Sobrien s->inUse16[i] = True; else 31178556Sobrien s->inUse16[i] = False; 31278556Sobrien } 31378556Sobrien 31478556Sobrien for (i = 0; i < 256; i++) s->inUse[i] = False; 31578556Sobrien 31678556Sobrien for (i = 0; i < 16; i++) 31778556Sobrien if (s->inUse16[i]) 31878556Sobrien for (j = 0; j < 16; j++) { 31978556Sobrien GET_BIT(BZ_X_MAPPING_2, uc); 32078556Sobrien if (uc == 1) s->inUse[i * 16 + j] = True; 32178556Sobrien } 32278556Sobrien makeMaps_d ( s ); 32378556Sobrien if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); 32478556Sobrien alphaSize = s->nInUse+2; 32578556Sobrien 32678556Sobrien /*--- Now the selectors ---*/ 32778556Sobrien GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 32878556Sobrien if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); 32978556Sobrien GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 33078556Sobrien if (nSelectors < 1) RETURN(BZ_DATA_ERROR); 33178556Sobrien for (i = 0; i < nSelectors; i++) { 33278556Sobrien j = 0; 33378556Sobrien while (True) { 33478556Sobrien GET_BIT(BZ_X_SELECTOR_3, uc); 33578556Sobrien if (uc == 0) break; 33678556Sobrien j++; 33778556Sobrien if (j >= nGroups) RETURN(BZ_DATA_ERROR); 33878556Sobrien } 33978556Sobrien s->selectorMtf[i] = j; 34078556Sobrien } 34178556Sobrien 34278556Sobrien /*--- Undo the MTF values for the selectors. ---*/ 34378556Sobrien { 34478556Sobrien UChar pos[BZ_N_GROUPS], tmp, v; 34578556Sobrien for (v = 0; v < nGroups; v++) pos[v] = v; 34678556Sobrien 34778556Sobrien for (i = 0; i < nSelectors; i++) { 34878556Sobrien v = s->selectorMtf[i]; 34978556Sobrien tmp = pos[v]; 35078556Sobrien while (v > 0) { pos[v] = pos[v-1]; v--; } 35178556Sobrien pos[0] = tmp; 35278556Sobrien s->selector[i] = tmp; 35378556Sobrien } 35478556Sobrien } 35578556Sobrien 35678556Sobrien /*--- Now the coding tables ---*/ 35778556Sobrien for (t = 0; t < nGroups; t++) { 35878556Sobrien GET_BITS(BZ_X_CODING_1, curr, 5); 35978556Sobrien for (i = 0; i < alphaSize; i++) { 36078556Sobrien while (True) { 36178556Sobrien if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 36278556Sobrien GET_BIT(BZ_X_CODING_2, uc); 36378556Sobrien if (uc == 0) break; 36478556Sobrien GET_BIT(BZ_X_CODING_3, uc); 36578556Sobrien if (uc == 0) curr++; else curr--; 36678556Sobrien } 36778556Sobrien s->len[t][i] = curr; 36878556Sobrien } 36978556Sobrien } 37078556Sobrien 37178556Sobrien /*--- Create the Huffman decoding tables ---*/ 37278556Sobrien for (t = 0; t < nGroups; t++) { 37378556Sobrien minLen = 32; 37478556Sobrien maxLen = 0; 37578556Sobrien for (i = 0; i < alphaSize; i++) { 37678556Sobrien if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 37778556Sobrien if (s->len[t][i] < minLen) minLen = s->len[t][i]; 37878556Sobrien } 37978556Sobrien BZ2_hbCreateDecodeTables ( 38078556Sobrien &(s->limit[t][0]), 38178556Sobrien &(s->base[t][0]), 38278556Sobrien &(s->perm[t][0]), 38378556Sobrien &(s->len[t][0]), 38478556Sobrien minLen, maxLen, alphaSize 38578556Sobrien ); 38678556Sobrien s->minLens[t] = minLen; 38778556Sobrien } 38878556Sobrien 38978556Sobrien /*--- Now the MTF values ---*/ 39078556Sobrien 39178556Sobrien EOB = s->nInUse+1; 39278556Sobrien nblockMAX = 100000 * s->blockSize100k; 39378556Sobrien groupNo = -1; 39478556Sobrien groupPos = 0; 39578556Sobrien 39678556Sobrien for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 39778556Sobrien 39878556Sobrien /*-- MTF init --*/ 39978556Sobrien { 40078556Sobrien Int32 ii, jj, kk; 40178556Sobrien kk = MTFA_SIZE-1; 40278556Sobrien for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 40378556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 40478556Sobrien s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 40578556Sobrien kk--; 40678556Sobrien } 40778556Sobrien s->mtfbase[ii] = kk + 1; 40878556Sobrien } 40978556Sobrien } 41078556Sobrien /*-- end MTF init --*/ 41178556Sobrien 41278556Sobrien nblock = 0; 41378556Sobrien GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 41478556Sobrien 41578556Sobrien while (True) { 41678556Sobrien 41778556Sobrien if (nextSym == EOB) break; 41878556Sobrien 41978556Sobrien if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 42078556Sobrien 42178556Sobrien es = -1; 42278556Sobrien N = 1; 42378556Sobrien do { 42478556Sobrien if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 42578556Sobrien if (nextSym == BZ_RUNB) es = es + (1+1) * N; 42678556Sobrien N = N * 2; 42778556Sobrien GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 42878556Sobrien } 42978556Sobrien while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 43078556Sobrien 43178556Sobrien es++; 43278556Sobrien uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 43378556Sobrien s->unzftab[uc] += es; 43478556Sobrien 43578556Sobrien if (s->smallDecompress) 43678556Sobrien while (es > 0) { 43778556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 43878556Sobrien s->ll16[nblock] = (UInt16)uc; 43978556Sobrien nblock++; 44078556Sobrien es--; 44178556Sobrien } 44278556Sobrien else 44378556Sobrien while (es > 0) { 44478556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 44578556Sobrien s->tt[nblock] = (UInt32)uc; 44678556Sobrien nblock++; 44778556Sobrien es--; 44878556Sobrien }; 44978556Sobrien 45078556Sobrien continue; 45178556Sobrien 45278556Sobrien } else { 45378556Sobrien 45478556Sobrien if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 45578556Sobrien 45678556Sobrien /*-- uc = MTF ( nextSym-1 ) --*/ 45778556Sobrien { 45878556Sobrien Int32 ii, jj, kk, pp, lno, off; 45978556Sobrien UInt32 nn; 46078556Sobrien nn = (UInt32)(nextSym - 1); 46178556Sobrien 46278556Sobrien if (nn < MTFL_SIZE) { 46378556Sobrien /* avoid general-case expense */ 46478556Sobrien pp = s->mtfbase[0]; 46578556Sobrien uc = s->mtfa[pp+nn]; 46678556Sobrien while (nn > 3) { 46778556Sobrien Int32 z = pp+nn; 46878556Sobrien s->mtfa[(z) ] = s->mtfa[(z)-1]; 46978556Sobrien s->mtfa[(z)-1] = s->mtfa[(z)-2]; 47078556Sobrien s->mtfa[(z)-2] = s->mtfa[(z)-3]; 47178556Sobrien s->mtfa[(z)-3] = s->mtfa[(z)-4]; 47278556Sobrien nn -= 4; 47378556Sobrien } 47478556Sobrien while (nn > 0) { 47578556Sobrien s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 47678556Sobrien }; 47778556Sobrien s->mtfa[pp] = uc; 47878556Sobrien } else { 47978556Sobrien /* general case */ 48078556Sobrien lno = nn / MTFL_SIZE; 48178556Sobrien off = nn % MTFL_SIZE; 48278556Sobrien pp = s->mtfbase[lno] + off; 48378556Sobrien uc = s->mtfa[pp]; 48478556Sobrien while (pp > s->mtfbase[lno]) { 48578556Sobrien s->mtfa[pp] = s->mtfa[pp-1]; pp--; 48678556Sobrien }; 48778556Sobrien s->mtfbase[lno]++; 48878556Sobrien while (lno > 0) { 48978556Sobrien s->mtfbase[lno]--; 49078556Sobrien s->mtfa[s->mtfbase[lno]] 49178556Sobrien = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 49278556Sobrien lno--; 49378556Sobrien } 49478556Sobrien s->mtfbase[0]--; 49578556Sobrien s->mtfa[s->mtfbase[0]] = uc; 49678556Sobrien if (s->mtfbase[0] == 0) { 49778556Sobrien kk = MTFA_SIZE-1; 49878556Sobrien for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 49978556Sobrien for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 50078556Sobrien s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 50178556Sobrien kk--; 50278556Sobrien } 50378556Sobrien s->mtfbase[ii] = kk + 1; 50478556Sobrien } 50578556Sobrien } 50678556Sobrien } 50778556Sobrien } 50878556Sobrien /*-- end uc = MTF ( nextSym-1 ) --*/ 50978556Sobrien 51078556Sobrien s->unzftab[s->seqToUnseq[uc]]++; 51178556Sobrien if (s->smallDecompress) 51278556Sobrien s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 51378556Sobrien s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 51478556Sobrien nblock++; 51578556Sobrien 51678556Sobrien GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 51778556Sobrien continue; 51878556Sobrien } 51978556Sobrien } 52078556Sobrien 52178556Sobrien /* Now we know what nblock is, we can do a better sanity 52278556Sobrien check on s->origPtr. 52378556Sobrien */ 52478556Sobrien if (s->origPtr < 0 || s->origPtr >= nblock) 52578556Sobrien RETURN(BZ_DATA_ERROR); 52678556Sobrien 527146293Sobrien /*-- Set up cftab to facilitate generation of T^(-1) --*/ 528146293Sobrien s->cftab[0] = 0; 529146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 530146293Sobrien for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 531146293Sobrien for (i = 0; i <= 256; i++) { 532146293Sobrien if (s->cftab[i] < 0 || s->cftab[i] > nblock) { 533146293Sobrien /* s->cftab[i] can legitimately be == nblock */ 534146293Sobrien RETURN(BZ_DATA_ERROR); 535146293Sobrien } 536146293Sobrien } 537146293Sobrien 53878556Sobrien s->state_out_len = 0; 53978556Sobrien s->state_out_ch = 0; 54078556Sobrien BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 54178556Sobrien s->state = BZ_X_OUTPUT; 54278556Sobrien if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 54378556Sobrien 54478556Sobrien if (s->smallDecompress) { 54578556Sobrien 54678556Sobrien /*-- Make a copy of cftab, used in generation of T --*/ 54778556Sobrien for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 54878556Sobrien 54978556Sobrien /*-- compute the T vector --*/ 55078556Sobrien for (i = 0; i < nblock; i++) { 55178556Sobrien uc = (UChar)(s->ll16[i]); 55278556Sobrien SET_LL(i, s->cftabCopy[uc]); 55378556Sobrien s->cftabCopy[uc]++; 55478556Sobrien } 55578556Sobrien 55678556Sobrien /*-- Compute T^(-1) by pointer reversal on T --*/ 55778556Sobrien i = s->origPtr; 55878556Sobrien j = GET_LL(i); 55978556Sobrien do { 56078556Sobrien Int32 tmp = GET_LL(j); 56178556Sobrien SET_LL(j, i); 56278556Sobrien i = j; 56378556Sobrien j = tmp; 56478556Sobrien } 56578556Sobrien while (i != s->origPtr); 56678556Sobrien 56778556Sobrien s->tPos = s->origPtr; 56878556Sobrien s->nblock_used = 0; 56978556Sobrien if (s->blockRandomised) { 57078556Sobrien BZ_RAND_INIT_MASK; 57178556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 57278556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 57378556Sobrien } else { 57478556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 57578556Sobrien } 57678556Sobrien 57778556Sobrien } else { 57878556Sobrien 57978556Sobrien /*-- compute the T^(-1) vector --*/ 58078556Sobrien for (i = 0; i < nblock; i++) { 58178556Sobrien uc = (UChar)(s->tt[i] & 0xff); 58278556Sobrien s->tt[s->cftab[uc]] |= (i << 8); 58378556Sobrien s->cftab[uc]++; 58478556Sobrien } 58578556Sobrien 58678556Sobrien s->tPos = s->tt[s->origPtr] >> 8; 58778556Sobrien s->nblock_used = 0; 58878556Sobrien if (s->blockRandomised) { 58978556Sobrien BZ_RAND_INIT_MASK; 59078556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 59178556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 59278556Sobrien } else { 59378556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 59478556Sobrien } 59578556Sobrien 59678556Sobrien } 59778556Sobrien 59878556Sobrien RETURN(BZ_OK); 59978556Sobrien 60078556Sobrien 60178556Sobrien 60278556Sobrien endhdr_2: 60378556Sobrien 60478556Sobrien GET_UCHAR(BZ_X_ENDHDR_2, uc); 60578556Sobrien if (uc != 0x72) RETURN(BZ_DATA_ERROR); 60678556Sobrien GET_UCHAR(BZ_X_ENDHDR_3, uc); 60778556Sobrien if (uc != 0x45) RETURN(BZ_DATA_ERROR); 60878556Sobrien GET_UCHAR(BZ_X_ENDHDR_4, uc); 60978556Sobrien if (uc != 0x38) RETURN(BZ_DATA_ERROR); 61078556Sobrien GET_UCHAR(BZ_X_ENDHDR_5, uc); 61178556Sobrien if (uc != 0x50) RETURN(BZ_DATA_ERROR); 61278556Sobrien GET_UCHAR(BZ_X_ENDHDR_6, uc); 61378556Sobrien if (uc != 0x90) RETURN(BZ_DATA_ERROR); 61478556Sobrien 61578556Sobrien s->storedCombinedCRC = 0; 61678556Sobrien GET_UCHAR(BZ_X_CCRC_1, uc); 61778556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 61878556Sobrien GET_UCHAR(BZ_X_CCRC_2, uc); 61978556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 62078556Sobrien GET_UCHAR(BZ_X_CCRC_3, uc); 62178556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 62278556Sobrien GET_UCHAR(BZ_X_CCRC_4, uc); 62378556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 62478556Sobrien 62578556Sobrien s->state = BZ_X_IDLE; 62678556Sobrien RETURN(BZ_STREAM_END); 62778556Sobrien 62878556Sobrien default: AssertH ( False, 4001 ); 62978556Sobrien } 63078556Sobrien 63178556Sobrien AssertH ( False, 4002 ); 63278556Sobrien 63378556Sobrien save_state_and_return: 63478556Sobrien 63578556Sobrien s->save_i = i; 63678556Sobrien s->save_j = j; 63778556Sobrien s->save_t = t; 63878556Sobrien s->save_alphaSize = alphaSize; 63978556Sobrien s->save_nGroups = nGroups; 64078556Sobrien s->save_nSelectors = nSelectors; 64178556Sobrien s->save_EOB = EOB; 64278556Sobrien s->save_groupNo = groupNo; 64378556Sobrien s->save_groupPos = groupPos; 64478556Sobrien s->save_nextSym = nextSym; 64578556Sobrien s->save_nblockMAX = nblockMAX; 64678556Sobrien s->save_nblock = nblock; 64778556Sobrien s->save_es = es; 64878556Sobrien s->save_N = N; 64978556Sobrien s->save_curr = curr; 65078556Sobrien s->save_zt = zt; 65178556Sobrien s->save_zn = zn; 65278556Sobrien s->save_zvec = zvec; 65378556Sobrien s->save_zj = zj; 65478556Sobrien s->save_gSel = gSel; 65578556Sobrien s->save_gMinlen = gMinlen; 65678556Sobrien s->save_gLimit = gLimit; 65778556Sobrien s->save_gBase = gBase; 65878556Sobrien s->save_gPerm = gPerm; 65978556Sobrien 66078556Sobrien return retVal; 66178556Sobrien} 66278556Sobrien 66378556Sobrien 66478556Sobrien/*-------------------------------------------------------------*/ 66578556Sobrien/*--- end decompress.c ---*/ 66678556Sobrien/*-------------------------------------------------------------*/ 667