decompress.c revision 78556
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 1178556Sobrien Copyright (C) 1996-2000 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. 4578556Sobrien jseward@acm.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); 23878556Sobrien if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC); 23978556Sobrien 24078556Sobrien GET_UCHAR(BZ_X_MAGIC_2, uc); 24178556Sobrien if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC); 24278556Sobrien 24378556Sobrien GET_UCHAR(BZ_X_MAGIC_3, uc) 24478556Sobrien if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC); 24578556Sobrien 24678556Sobrien GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 24778556Sobrien if (s->blockSize100k < '1' || 24878556Sobrien s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC); 24978556Sobrien s->blockSize100k -= '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 52778556Sobrien s->state_out_len = 0; 52878556Sobrien s->state_out_ch = 0; 52978556Sobrien BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 53078556Sobrien s->state = BZ_X_OUTPUT; 53178556Sobrien if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 53278556Sobrien 53378556Sobrien /*-- Set up cftab to facilitate generation of T^(-1) --*/ 53478556Sobrien s->cftab[0] = 0; 53578556Sobrien for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 53678556Sobrien for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 53778556Sobrien 53878556Sobrien if (s->smallDecompress) { 53978556Sobrien 54078556Sobrien /*-- Make a copy of cftab, used in generation of T --*/ 54178556Sobrien for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 54278556Sobrien 54378556Sobrien /*-- compute the T vector --*/ 54478556Sobrien for (i = 0; i < nblock; i++) { 54578556Sobrien uc = (UChar)(s->ll16[i]); 54678556Sobrien SET_LL(i, s->cftabCopy[uc]); 54778556Sobrien s->cftabCopy[uc]++; 54878556Sobrien } 54978556Sobrien 55078556Sobrien /*-- Compute T^(-1) by pointer reversal on T --*/ 55178556Sobrien i = s->origPtr; 55278556Sobrien j = GET_LL(i); 55378556Sobrien do { 55478556Sobrien Int32 tmp = GET_LL(j); 55578556Sobrien SET_LL(j, i); 55678556Sobrien i = j; 55778556Sobrien j = tmp; 55878556Sobrien } 55978556Sobrien while (i != s->origPtr); 56078556Sobrien 56178556Sobrien s->tPos = s->origPtr; 56278556Sobrien s->nblock_used = 0; 56378556Sobrien if (s->blockRandomised) { 56478556Sobrien BZ_RAND_INIT_MASK; 56578556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 56678556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 56778556Sobrien } else { 56878556Sobrien BZ_GET_SMALL(s->k0); s->nblock_used++; 56978556Sobrien } 57078556Sobrien 57178556Sobrien } else { 57278556Sobrien 57378556Sobrien /*-- compute the T^(-1) vector --*/ 57478556Sobrien for (i = 0; i < nblock; i++) { 57578556Sobrien uc = (UChar)(s->tt[i] & 0xff); 57678556Sobrien s->tt[s->cftab[uc]] |= (i << 8); 57778556Sobrien s->cftab[uc]++; 57878556Sobrien } 57978556Sobrien 58078556Sobrien s->tPos = s->tt[s->origPtr] >> 8; 58178556Sobrien s->nblock_used = 0; 58278556Sobrien if (s->blockRandomised) { 58378556Sobrien BZ_RAND_INIT_MASK; 58478556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 58578556Sobrien BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 58678556Sobrien } else { 58778556Sobrien BZ_GET_FAST(s->k0); s->nblock_used++; 58878556Sobrien } 58978556Sobrien 59078556Sobrien } 59178556Sobrien 59278556Sobrien RETURN(BZ_OK); 59378556Sobrien 59478556Sobrien 59578556Sobrien 59678556Sobrien endhdr_2: 59778556Sobrien 59878556Sobrien GET_UCHAR(BZ_X_ENDHDR_2, uc); 59978556Sobrien if (uc != 0x72) RETURN(BZ_DATA_ERROR); 60078556Sobrien GET_UCHAR(BZ_X_ENDHDR_3, uc); 60178556Sobrien if (uc != 0x45) RETURN(BZ_DATA_ERROR); 60278556Sobrien GET_UCHAR(BZ_X_ENDHDR_4, uc); 60378556Sobrien if (uc != 0x38) RETURN(BZ_DATA_ERROR); 60478556Sobrien GET_UCHAR(BZ_X_ENDHDR_5, uc); 60578556Sobrien if (uc != 0x50) RETURN(BZ_DATA_ERROR); 60678556Sobrien GET_UCHAR(BZ_X_ENDHDR_6, uc); 60778556Sobrien if (uc != 0x90) RETURN(BZ_DATA_ERROR); 60878556Sobrien 60978556Sobrien s->storedCombinedCRC = 0; 61078556Sobrien GET_UCHAR(BZ_X_CCRC_1, uc); 61178556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 61278556Sobrien GET_UCHAR(BZ_X_CCRC_2, uc); 61378556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 61478556Sobrien GET_UCHAR(BZ_X_CCRC_3, uc); 61578556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 61678556Sobrien GET_UCHAR(BZ_X_CCRC_4, uc); 61778556Sobrien s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 61878556Sobrien 61978556Sobrien s->state = BZ_X_IDLE; 62078556Sobrien RETURN(BZ_STREAM_END); 62178556Sobrien 62278556Sobrien default: AssertH ( False, 4001 ); 62378556Sobrien } 62478556Sobrien 62578556Sobrien AssertH ( False, 4002 ); 62678556Sobrien 62778556Sobrien save_state_and_return: 62878556Sobrien 62978556Sobrien s->save_i = i; 63078556Sobrien s->save_j = j; 63178556Sobrien s->save_t = t; 63278556Sobrien s->save_alphaSize = alphaSize; 63378556Sobrien s->save_nGroups = nGroups; 63478556Sobrien s->save_nSelectors = nSelectors; 63578556Sobrien s->save_EOB = EOB; 63678556Sobrien s->save_groupNo = groupNo; 63778556Sobrien s->save_groupPos = groupPos; 63878556Sobrien s->save_nextSym = nextSym; 63978556Sobrien s->save_nblockMAX = nblockMAX; 64078556Sobrien s->save_nblock = nblock; 64178556Sobrien s->save_es = es; 64278556Sobrien s->save_N = N; 64378556Sobrien s->save_curr = curr; 64478556Sobrien s->save_zt = zt; 64578556Sobrien s->save_zn = zn; 64678556Sobrien s->save_zvec = zvec; 64778556Sobrien s->save_zj = zj; 64878556Sobrien s->save_gSel = gSel; 64978556Sobrien s->save_gMinlen = gMinlen; 65078556Sobrien s->save_gLimit = gLimit; 65178556Sobrien s->save_gBase = gBase; 65278556Sobrien s->save_gPerm = gPerm; 65378556Sobrien 65478556Sobrien return retVal; 65578556Sobrien} 65678556Sobrien 65778556Sobrien 65878556Sobrien/*-------------------------------------------------------------*/ 65978556Sobrien/*--- end decompress.c ---*/ 66078556Sobrien/*-------------------------------------------------------------*/ 661