Mercurial > hg > sv-dependency-builds

annotate src/bzip2-1.0.6/decompress.c @ 169:223a55898ab9 tip default

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add null config files
author Chris Cannam <cannam@all-day-breakfast.com>
date Mon, 02 Mar 2020 14:03:47 +0000
parents 8a15ff55d9af
children
rev   line source
cannam@89 1
cannam@89 2 /*-------------------------------------------------------------*/
cannam@89 3 /*--- Decompression machinery ---*/
cannam@89 4 /*--- decompress.c ---*/
cannam@89 5 /*-------------------------------------------------------------*/
cannam@89 6
cannam@89 7 /* ------------------------------------------------------------------
cannam@89 8 This file is part of bzip2/libbzip2, a program and library for
cannam@89 9 lossless, block-sorting data compression.
cannam@89 10
cannam@89 11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
cannam@89 12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
cannam@89 13
cannam@89 14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
cannam@89 15 README file.
cannam@89 16
cannam@89 17 This program is released under the terms of the license contained
cannam@89 18 in the file LICENSE.
cannam@89 19 ------------------------------------------------------------------ */
cannam@89 20
cannam@89 21
cannam@89 22 #include "bzlib_private.h"
cannam@89 23
cannam@89 24
cannam@89 25 /*---------------------------------------------------*/
cannam@89 26 static
cannam@89 27 void makeMaps_d ( DState* s )
cannam@89 28 {
cannam@89 29 Int32 i;
cannam@89 30 s->nInUse = 0;
cannam@89 31 for (i = 0; i < 256; i++)
cannam@89 32 if (s->inUse[i]) {
cannam@89 33 s->seqToUnseq[s->nInUse] = i;
cannam@89 34 s->nInUse++;
cannam@89 35 }
cannam@89 36 }
cannam@89 37
cannam@89 38
cannam@89 39 /*---------------------------------------------------*/
cannam@89 40 #define RETURN(rrr) \
cannam@89 41 { retVal = rrr; goto save_state_and_return; };
cannam@89 42
cannam@89 43 #define GET_BITS(lll,vvv,nnn) \
cannam@89 44 case lll: s->state = lll; \
cannam@89 45 while (True) { \
cannam@89 46 if (s->bsLive >= nnn) { \
cannam@89 47 UInt32 v; \
cannam@89 48 v = (s->bsBuff >> \
cannam@89 49 (s->bsLive-nnn)) & ((1 << nnn)-1); \
cannam@89 50 s->bsLive -= nnn; \
cannam@89 51 vvv = v; \
cannam@89 52 break; \
cannam@89 53 } \
cannam@89 54 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
cannam@89 55 s->bsBuff \
cannam@89 56 = (s->bsBuff << 8) | \
cannam@89 57 ((UInt32) \
cannam@89 58 (*((UChar*)(s->strm->next_in)))); \
cannam@89 59 s->bsLive += 8; \
cannam@89 60 s->strm->next_in++; \
cannam@89 61 s->strm->avail_in--; \
cannam@89 62 s->strm->total_in_lo32++; \
cannam@89 63 if (s->strm->total_in_lo32 == 0) \
cannam@89 64 s->strm->total_in_hi32++; \
cannam@89 65 }
cannam@89 66
cannam@89 67 #define GET_UCHAR(lll,uuu) \
cannam@89 68 GET_BITS(lll,uuu,8)
cannam@89 69
cannam@89 70 #define GET_BIT(lll,uuu) \
cannam@89 71 GET_BITS(lll,uuu,1)
cannam@89 72
cannam@89 73 /*---------------------------------------------------*/
cannam@89 74 #define GET_MTF_VAL(label1,label2,lval) \
cannam@89 75 { \
cannam@89 76 if (groupPos == 0) { \
cannam@89 77 groupNo++; \
cannam@89 78 if (groupNo >= nSelectors) \
cannam@89 79 RETURN(BZ_DATA_ERROR); \
cannam@89 80 groupPos = BZ_G_SIZE; \
cannam@89 81 gSel = s->selector[groupNo]; \
cannam@89 82 gMinlen = s->minLens[gSel]; \
cannam@89 83 gLimit = &(s->limit[gSel][0]); \
cannam@89 84 gPerm = &(s->perm[gSel][0]); \
cannam@89 85 gBase = &(s->base[gSel][0]); \
cannam@89 86 } \
cannam@89 87 groupPos--; \
cannam@89 88 zn = gMinlen; \
cannam@89 89 GET_BITS(label1, zvec, zn); \
cannam@89 90 while (1) { \
cannam@89 91 if (zn > 20 /* the longest code */) \
cannam@89 92 RETURN(BZ_DATA_ERROR); \
cannam@89 93 if (zvec <= gLimit[zn]) break; \
cannam@89 94 zn++; \
cannam@89 95 GET_BIT(label2, zj); \
cannam@89 96 zvec = (zvec << 1) | zj; \
cannam@89 97 }; \
cannam@89 98 if (zvec - gBase[zn] < 0 \
cannam@89 99 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
cannam@89 100 RETURN(BZ_DATA_ERROR); \
cannam@89 101 lval = gPerm[zvec - gBase[zn]]; \
cannam@89 102 }
cannam@89 103
cannam@89 104
cannam@89 105 /*---------------------------------------------------*/
cannam@89 106 Int32 BZ2_decompress ( DState* s )
cannam@89 107 {
cannam@89 108 UChar uc;
cannam@89 109 Int32 retVal;
cannam@89 110 Int32 minLen, maxLen;
cannam@89 111 bz_stream* strm = s->strm;
cannam@89 112
cannam@89 113 /* stuff that needs to be saved/restored */
cannam@89 114 Int32 i;
cannam@89 115 Int32 j;
cannam@89 116 Int32 t;
cannam@89 117 Int32 alphaSize;
cannam@89 118 Int32 nGroups;
cannam@89 119 Int32 nSelectors;
cannam@89 120 Int32 EOB;
cannam@89 121 Int32 groupNo;
cannam@89 122 Int32 groupPos;
cannam@89 123 Int32 nextSym;
cannam@89 124 Int32 nblockMAX;
cannam@89 125 Int32 nblock;
cannam@89 126 Int32 es;
cannam@89 127 Int32 N;
cannam@89 128 Int32 curr;
cannam@89 129 Int32 zt;
cannam@89 130 Int32 zn;
cannam@89 131 Int32 zvec;
cannam@89 132 Int32 zj;
cannam@89 133 Int32 gSel;
cannam@89 134 Int32 gMinlen;
cannam@89 135 Int32* gLimit;
cannam@89 136 Int32* gBase;
cannam@89 137 Int32* gPerm;
cannam@89 138
cannam@89 139 if (s->state == BZ_X_MAGIC_1) {
cannam@89 140 /*initialise the save area*/
cannam@89 141 s->save_i = 0;
cannam@89 142 s->save_j = 0;
cannam@89 143 s->save_t = 0;
cannam@89 144 s->save_alphaSize = 0;
cannam@89 145 s->save_nGroups = 0;
cannam@89 146 s->save_nSelectors = 0;
cannam@89 147 s->save_EOB = 0;
cannam@89 148 s->save_groupNo = 0;
cannam@89 149 s->save_groupPos = 0;
cannam@89 150 s->save_nextSym = 0;
cannam@89 151 s->save_nblockMAX = 0;
cannam@89 152 s->save_nblock = 0;
cannam@89 153 s->save_es = 0;
cannam@89 154 s->save_N = 0;
cannam@89 155 s->save_curr = 0;
cannam@89 156 s->save_zt = 0;
cannam@89 157 s->save_zn = 0;
cannam@89 158 s->save_zvec = 0;
cannam@89 159 s->save_zj = 0;
cannam@89 160 s->save_gSel = 0;
cannam@89 161 s->save_gMinlen = 0;
cannam@89 162 s->save_gLimit = NULL;
cannam@89 163 s->save_gBase = NULL;
cannam@89 164 s->save_gPerm = NULL;
cannam@89 165 }
cannam@89 166
cannam@89 167 /*restore from the save area*/
cannam@89 168 i = s->save_i;
cannam@89 169 j = s->save_j;
cannam@89 170 t = s->save_t;
cannam@89 171 alphaSize = s->save_alphaSize;
cannam@89 172 nGroups = s->save_nGroups;
cannam@89 173 nSelectors = s->save_nSelectors;
cannam@89 174 EOB = s->save_EOB;
cannam@89 175 groupNo = s->save_groupNo;
cannam@89 176 groupPos = s->save_groupPos;
cannam@89 177 nextSym = s->save_nextSym;
cannam@89 178 nblockMAX = s->save_nblockMAX;
cannam@89 179 nblock = s->save_nblock;
cannam@89 180 es = s->save_es;
cannam@89 181 N = s->save_N;
cannam@89 182 curr = s->save_curr;
cannam@89 183 zt = s->save_zt;
cannam@89 184 zn = s->save_zn;
cannam@89 185 zvec = s->save_zvec;
cannam@89 186 zj = s->save_zj;
cannam@89 187 gSel = s->save_gSel;
cannam@89 188 gMinlen = s->save_gMinlen;
cannam@89 189 gLimit = s->save_gLimit;
cannam@89 190 gBase = s->save_gBase;
cannam@89 191 gPerm = s->save_gPerm;
cannam@89 192
cannam@89 193 retVal = BZ_OK;
cannam@89 194
cannam@89 195 switch (s->state) {
cannam@89 196
cannam@89 197 GET_UCHAR(BZ_X_MAGIC_1, uc);
cannam@89 198 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
cannam@89 199
cannam@89 200 GET_UCHAR(BZ_X_MAGIC_2, uc);
cannam@89 201 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
cannam@89 202
cannam@89 203 GET_UCHAR(BZ_X_MAGIC_3, uc)
cannam@89 204 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
cannam@89 205
cannam@89 206 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
cannam@89 207 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
cannam@89 208 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
cannam@89 209 s->blockSize100k -= BZ_HDR_0;
cannam@89 210
cannam@89 211 if (s->smallDecompress) {
cannam@89 212 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
cannam@89 213 s->ll4 = BZALLOC(
cannam@89 214 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
cannam@89 215 );
cannam@89 216 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
cannam@89 217 } else {
cannam@89 218 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
cannam@89 219 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
cannam@89 220 }
cannam@89 221
cannam@89 222 GET_UCHAR(BZ_X_BLKHDR_1, uc);
cannam@89 223
cannam@89 224 if (uc == 0x17) goto endhdr_2;
cannam@89 225 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
cannam@89 226 GET_UCHAR(BZ_X_BLKHDR_2, uc);
cannam@89 227 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
cannam@89 228 GET_UCHAR(BZ_X_BLKHDR_3, uc);
cannam@89 229 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
cannam@89 230 GET_UCHAR(BZ_X_BLKHDR_4, uc);
cannam@89 231 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
cannam@89 232 GET_UCHAR(BZ_X_BLKHDR_5, uc);
cannam@89 233 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
cannam@89 234 GET_UCHAR(BZ_X_BLKHDR_6, uc);
cannam@89 235 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
cannam@89 236
cannam@89 237 s->currBlockNo++;
cannam@89 238 if (s->verbosity >= 2)
cannam@89 239 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
cannam@89 240
cannam@89 241 s->storedBlockCRC = 0;
cannam@89 242 GET_UCHAR(BZ_X_BCRC_1, uc);
cannam@89 243 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
cannam@89 244 GET_UCHAR(BZ_X_BCRC_2, uc);
cannam@89 245 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
cannam@89 246 GET_UCHAR(BZ_X_BCRC_3, uc);
cannam@89 247 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
cannam@89 248 GET_UCHAR(BZ_X_BCRC_4, uc);
cannam@89 249 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
cannam@89 250
cannam@89 251 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
cannam@89 252
cannam@89 253 s->origPtr = 0;
cannam@89 254 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
cannam@89 255 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
cannam@89 256 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
cannam@89 257 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
cannam@89 258 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
cannam@89 259 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
cannam@89 260
cannam@89 261 if (s->origPtr < 0)
cannam@89 262 RETURN(BZ_DATA_ERROR);
cannam@89 263 if (s->origPtr > 10 + 100000*s->blockSize100k)
cannam@89 264 RETURN(BZ_DATA_ERROR);
cannam@89 265
cannam@89 266 /*--- Receive the mapping table ---*/
cannam@89 267 for (i = 0; i < 16; i++) {
cannam@89 268 GET_BIT(BZ_X_MAPPING_1, uc);
cannam@89 269 if (uc == 1)
cannam@89 270 s->inUse16[i] = True; else
cannam@89 271 s->inUse16[i] = False;
cannam@89 272 }
cannam@89 273
cannam@89 274 for (i = 0; i < 256; i++) s->inUse[i] = False;
cannam@89 275
cannam@89 276 for (i = 0; i < 16; i++)
cannam@89 277 if (s->inUse16[i])
cannam@89 278 for (j = 0; j < 16; j++) {
cannam@89 279 GET_BIT(BZ_X_MAPPING_2, uc);
cannam@89 280 if (uc == 1) s->inUse[i * 16 + j] = True;
cannam@89 281 }
cannam@89 282 makeMaps_d ( s );
cannam@89 283 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
cannam@89 284 alphaSize = s->nInUse+2;
cannam@89 285
cannam@89 286 /*--- Now the selectors ---*/
cannam@89 287 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
cannam@89 288 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
cannam@89 289 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
cannam@89 290 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
cannam@89 291 for (i = 0; i < nSelectors; i++) {
cannam@89 292 j = 0;
cannam@89 293 while (True) {
cannam@89 294 GET_BIT(BZ_X_SELECTOR_3, uc);
cannam@89 295 if (uc == 0) break;
cannam@89 296 j++;
cannam@89 297 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
cannam@89 298 }
cannam@89 299 s->selectorMtf[i] = j;
cannam@89 300 }
cannam@89 301
cannam@89 302 /*--- Undo the MTF values for the selectors. ---*/
cannam@89 303 {
cannam@89 304 UChar pos[BZ_N_GROUPS], tmp, v;
cannam@89 305 for (v = 0; v < nGroups; v++) pos[v] = v;
cannam@89 306
cannam@89 307 for (i = 0; i < nSelectors; i++) {
cannam@89 308 v = s->selectorMtf[i];
cannam@89 309 tmp = pos[v];
cannam@89 310 while (v > 0) { pos[v] = pos[v-1]; v--; }
cannam@89 311 pos[0] = tmp;
cannam@89 312 s->selector[i] = tmp;
cannam@89 313 }
cannam@89 314 }
cannam@89 315
cannam@89 316 /*--- Now the coding tables ---*/
cannam@89 317 for (t = 0; t < nGroups; t++) {
cannam@89 318 GET_BITS(BZ_X_CODING_1, curr, 5);
cannam@89 319 for (i = 0; i < alphaSize; i++) {
cannam@89 320 while (True) {
cannam@89 321 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
cannam@89 322 GET_BIT(BZ_X_CODING_2, uc);
cannam@89 323 if (uc == 0) break;
cannam@89 324 GET_BIT(BZ_X_CODING_3, uc);
cannam@89 325 if (uc == 0) curr++; else curr--;
cannam@89 326 }
cannam@89 327 s->len[t][i] = curr;
cannam@89 328 }
cannam@89 329 }
cannam@89 330
cannam@89 331 /*--- Create the Huffman decoding tables ---*/
cannam@89 332 for (t = 0; t < nGroups; t++) {
cannam@89 333 minLen = 32;
cannam@89 334 maxLen = 0;
cannam@89 335 for (i = 0; i < alphaSize; i++) {
cannam@89 336 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
cannam@89 337 if (s->len[t][i] < minLen) minLen = s->len[t][i];
cannam@89 338 }
cannam@89 339 BZ2_hbCreateDecodeTables (
cannam@89 340 &(s->limit[t][0]),
cannam@89 341 &(s->base[t][0]),
cannam@89 342 &(s->perm[t][0]),
cannam@89 343 &(s->len[t][0]),
cannam@89 344 minLen, maxLen, alphaSize
cannam@89 345 );
cannam@89 346 s->minLens[t] = minLen;
cannam@89 347 }
cannam@89 348
cannam@89 349 /*--- Now the MTF values ---*/
cannam@89 350
cannam@89 351 EOB = s->nInUse+1;
cannam@89 352 nblockMAX = 100000 * s->blockSize100k;
cannam@89 353 groupNo = -1;
cannam@89 354 groupPos = 0;
cannam@89 355
cannam@89 356 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
cannam@89 357
cannam@89 358 /*-- MTF init --*/
cannam@89 359 {
cannam@89 360 Int32 ii, jj, kk;
cannam@89 361 kk = MTFA_SIZE-1;
cannam@89 362 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
cannam@89 363 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
cannam@89 364 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
cannam@89 365 kk--;
cannam@89 366 }
cannam@89 367 s->mtfbase[ii] = kk + 1;
cannam@89 368 }
cannam@89 369 }
cannam@89 370 /*-- end MTF init --*/
cannam@89 371
cannam@89 372 nblock = 0;
cannam@89 373 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
cannam@89 374
cannam@89 375 while (True) {
cannam@89 376
cannam@89 377 if (nextSym == EOB) break;
cannam@89 378
cannam@89 379 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
cannam@89 380
cannam@89 381 es = -1;
cannam@89 382 N = 1;
cannam@89 383 do {
cannam@89 384 /* Check that N doesn't get too big, so that es doesn't
cannam@89 385 go negative. The maximum value that can be
cannam@89 386 RUNA/RUNB encoded is equal to the block size (post
cannam@89 387 the initial RLE), viz, 900k, so bounding N at 2
cannam@89 388 million should guard against overflow without
cannam@89 389 rejecting any legitimate inputs. */
cannam@89 390 if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
cannam@89 391 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
cannam@89 392 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
cannam@89 393 N = N * 2;
cannam@89 394 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
cannam@89 395 }
cannam@89 396 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
cannam@89 397
cannam@89 398 es++;
cannam@89 399 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
cannam@89 400 s->unzftab[uc] += es;
cannam@89 401
cannam@89 402 if (s->smallDecompress)
cannam@89 403 while (es > 0) {
cannam@89 404 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
cannam@89 405 s->ll16[nblock] = (UInt16)uc;
cannam@89 406 nblock++;
cannam@89 407 es--;
cannam@89 408 }
cannam@89 409 else
cannam@89 410 while (es > 0) {
cannam@89 411 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
cannam@89 412 s->tt[nblock] = (UInt32)uc;
cannam@89 413 nblock++;
cannam@89 414 es--;
cannam@89 415 };
cannam@89 416
cannam@89 417 continue;
cannam@89 418
cannam@89 419 } else {
cannam@89 420
cannam@89 421 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
cannam@89 422
cannam@89 423 /*-- uc = MTF ( nextSym-1 ) --*/
cannam@89 424 {
cannam@89 425 Int32 ii, jj, kk, pp, lno, off;
cannam@89 426 UInt32 nn;
cannam@89 427 nn = (UInt32)(nextSym - 1);
cannam@89 428
cannam@89 429 if (nn < MTFL_SIZE) {
cannam@89 430 /* avoid general-case expense */
cannam@89 431 pp = s->mtfbase[0];
cannam@89 432 uc = s->mtfa[pp+nn];
cannam@89 433 while (nn > 3) {
cannam@89 434 Int32 z = pp+nn;
cannam@89 435 s->mtfa[(z) ] = s->mtfa[(z)-1];
cannam@89 436 s->mtfa[(z)-1] = s->mtfa[(z)-2];
cannam@89 437 s->mtfa[(z)-2] = s->mtfa[(z)-3];
cannam@89 438 s->mtfa[(z)-3] = s->mtfa[(z)-4];
cannam@89 439 nn -= 4;
cannam@89 440 }
cannam@89 441 while (nn > 0) {
cannam@89 442 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
cannam@89 443 };
cannam@89 444 s->mtfa[pp] = uc;
cannam@89 445 } else {
cannam@89 446 /* general case */
cannam@89 447 lno = nn / MTFL_SIZE;
cannam@89 448 off = nn % MTFL_SIZE;
cannam@89 449 pp = s->mtfbase[lno] + off;
cannam@89 450 uc = s->mtfa[pp];
cannam@89 451 while (pp > s->mtfbase[lno]) {
cannam@89 452 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
cannam@89 453 };
cannam@89 454 s->mtfbase[lno]++;
cannam@89 455 while (lno > 0) {
cannam@89 456 s->mtfbase[lno]--;
cannam@89 457 s->mtfa[s->mtfbase[lno]]
cannam@89 458 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
cannam@89 459 lno--;
cannam@89 460 }
cannam@89 461 s->mtfbase[0]--;
cannam@89 462 s->mtfa[s->mtfbase[0]] = uc;
cannam@89 463 if (s->mtfbase[0] == 0) {
cannam@89 464 kk = MTFA_SIZE-1;
cannam@89 465 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
cannam@89 466 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
cannam@89 467 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
cannam@89 468 kk--;
cannam@89 469 }
cannam@89 470 s->mtfbase[ii] = kk + 1;
cannam@89 471 }
cannam@89 472 }
cannam@89 473 }
cannam@89 474 }
cannam@89 475 /*-- end uc = MTF ( nextSym-1 ) --*/
cannam@89 476
cannam@89 477 s->unzftab[s->seqToUnseq[uc]]++;
cannam@89 478 if (s->smallDecompress)
cannam@89 479 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
cannam@89 480 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
cannam@89 481 nblock++;
cannam@89 482
cannam@89 483 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
cannam@89 484 continue;
cannam@89 485 }
cannam@89 486 }
cannam@89 487
cannam@89 488 /* Now we know what nblock is, we can do a better sanity
cannam@89 489 check on s->origPtr.
cannam@89 490 */
cannam@89 491 if (s->origPtr < 0 || s->origPtr >= nblock)
cannam@89 492 RETURN(BZ_DATA_ERROR);
cannam@89 493
cannam@89 494 /*-- Set up cftab to facilitate generation of T^(-1) --*/
cannam@89 495 /* Check: unzftab entries in range. */
cannam@89 496 for (i = 0; i <= 255; i++) {
cannam@89 497 if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
cannam@89 498 RETURN(BZ_DATA_ERROR);
cannam@89 499 }
cannam@89 500 /* Actually generate cftab. */
cannam@89 501 s->cftab[0] = 0;
cannam@89 502 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
cannam@89 503 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
cannam@89 504 /* Check: cftab entries in range. */
cannam@89 505 for (i = 0; i <= 256; i++) {
cannam@89 506 if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
cannam@89 507 /* s->cftab[i] can legitimately be == nblock */
cannam@89 508 RETURN(BZ_DATA_ERROR);
cannam@89 509 }
cannam@89 510 }
cannam@89 511 /* Check: cftab entries non-descending. */
cannam@89 512 for (i = 1; i <= 256; i++) {
cannam@89 513 if (s->cftab[i-1] > s->cftab[i]) {
cannam@89 514 RETURN(BZ_DATA_ERROR);
cannam@89 515 }
cannam@89 516 }
cannam@89 517
cannam@89 518 s->state_out_len = 0;
cannam@89 519 s->state_out_ch = 0;
cannam@89 520 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
cannam@89 521 s->state = BZ_X_OUTPUT;
cannam@89 522 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
cannam@89 523
cannam@89 524 if (s->smallDecompress) {
cannam@89 525
cannam@89 526 /*-- Make a copy of cftab, used in generation of T --*/
cannam@89 527 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
cannam@89 528
cannam@89 529 /*-- compute the T vector --*/
cannam@89 530 for (i = 0; i < nblock; i++) {
cannam@89 531 uc = (UChar)(s->ll16[i]);
cannam@89 532 SET_LL(i, s->cftabCopy[uc]);
cannam@89 533 s->cftabCopy[uc]++;
cannam@89 534 }
cannam@89 535
cannam@89 536 /*-- Compute T^(-1) by pointer reversal on T --*/
cannam@89 537 i = s->origPtr;
cannam@89 538 j = GET_LL(i);
cannam@89 539 do {
cannam@89 540 Int32 tmp = GET_LL(j);
cannam@89 541 SET_LL(j, i);
cannam@89 542 i = j;
cannam@89 543 j = tmp;
cannam@89 544 }
cannam@89 545 while (i != s->origPtr);
cannam@89 546
cannam@89 547 s->tPos = s->origPtr;
cannam@89 548 s->nblock_used = 0;
cannam@89 549 if (s->blockRandomised) {
cannam@89 550 BZ_RAND_INIT_MASK;
cannam@89 551 BZ_GET_SMALL(s->k0); s->nblock_used++;
cannam@89 552 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
cannam@89 553 } else {
cannam@89 554 BZ_GET_SMALL(s->k0); s->nblock_used++;
cannam@89 555 }
cannam@89 556
cannam@89 557 } else {
cannam@89 558
cannam@89 559 /*-- compute the T^(-1) vector --*/
cannam@89 560 for (i = 0; i < nblock; i++) {
cannam@89 561 uc = (UChar)(s->tt[i] & 0xff);
cannam@89 562 s->tt[s->cftab[uc]] |= (i << 8);
cannam@89 563 s->cftab[uc]++;
cannam@89 564 }
cannam@89 565
cannam@89 566 s->tPos = s->tt[s->origPtr] >> 8;
cannam@89 567 s->nblock_used = 0;
cannam@89 568 if (s->blockRandomised) {
cannam@89 569 BZ_RAND_INIT_MASK;
cannam@89 570 BZ_GET_FAST(s->k0); s->nblock_used++;
cannam@89 571 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
cannam@89 572 } else {
cannam@89 573 BZ_GET_FAST(s->k0); s->nblock_used++;
cannam@89 574 }
cannam@89 575
cannam@89 576 }
cannam@89 577
cannam@89 578 RETURN(BZ_OK);
cannam@89 579
cannam@89 580
cannam@89 581
cannam@89 582 endhdr_2:
cannam@89 583
cannam@89 584 GET_UCHAR(BZ_X_ENDHDR_2, uc);
cannam@89 585 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
cannam@89 586 GET_UCHAR(BZ_X_ENDHDR_3, uc);
cannam@89 587 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
cannam@89 588 GET_UCHAR(BZ_X_ENDHDR_4, uc);
cannam@89 589 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
cannam@89 590 GET_UCHAR(BZ_X_ENDHDR_5, uc);
cannam@89 591 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
cannam@89 592 GET_UCHAR(BZ_X_ENDHDR_6, uc);
cannam@89 593 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
cannam@89 594
cannam@89 595 s->storedCombinedCRC = 0;
cannam@89 596 GET_UCHAR(BZ_X_CCRC_1, uc);
cannam@89 597 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
cannam@89 598 GET_UCHAR(BZ_X_CCRC_2, uc);
cannam@89 599 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
cannam@89 600 GET_UCHAR(BZ_X_CCRC_3, uc);
cannam@89 601 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
cannam@89 602 GET_UCHAR(BZ_X_CCRC_4, uc);
cannam@89 603 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
cannam@89 604
cannam@89 605 s->state = BZ_X_IDLE;
cannam@89 606 RETURN(BZ_STREAM_END);
cannam@89 607
cannam@89 608 default: AssertH ( False, 4001 );
cannam@89 609 }
cannam@89 610
cannam@89 611 AssertH ( False, 4002 );
cannam@89 612
cannam@89 613 save_state_and_return:
cannam@89 614
cannam@89 615 s->save_i = i;
cannam@89 616 s->save_j = j;
cannam@89 617 s->save_t = t;
cannam@89 618 s->save_alphaSize = alphaSize;
cannam@89 619 s->save_nGroups = nGroups;
cannam@89 620 s->save_nSelectors = nSelectors;
cannam@89 621 s->save_EOB = EOB;
cannam@89 622 s->save_groupNo = groupNo;
cannam@89 623 s->save_groupPos = groupPos;
cannam@89 624 s->save_nextSym = nextSym;
cannam@89 625 s->save_nblockMAX = nblockMAX;
cannam@89 626 s->save_nblock = nblock;
cannam@89 627 s->save_es = es;
cannam@89 628 s->save_N = N;
cannam@89 629 s->save_curr = curr;
cannam@89 630 s->save_zt = zt;
cannam@89 631 s->save_zn = zn;
cannam@89 632 s->save_zvec = zvec;
cannam@89 633 s->save_zj = zj;
cannam@89 634 s->save_gSel = gSel;
cannam@89 635 s->save_gMinlen = gMinlen;
cannam@89 636 s->save_gLimit = gLimit;
cannam@89 637 s->save_gBase = gBase;
cannam@89 638 s->save_gPerm = gPerm;
cannam@89 639
cannam@89 640 return retVal;
cannam@89 641 }
cannam@89 642
cannam@89 643
cannam@89 644 /*-------------------------------------------------------------*/
cannam@89 645 /*--- end decompress.c ---*/
cannam@89 646 /*-------------------------------------------------------------*/