1 #include <u.h> 2 #include <libc.h> 3 #include <bio.h> 4 #include "bzfs.h" 5 6 /* 7 * THIS FILE IS NOT IDENTICAL TO THE ORIGINAL 8 * FROM THE BZIP2 DISTRIBUTION. 9 * 10 * It has been modified, mainly to break the library 11 * into smaller pieces. 12 * 13 * Russ Cox 14 * rsc@plan9.bell-labs.com 15 * July 2000 16 */ 17 18 /*---------------------------------------------*/ 19 /*-- 20 Place a 1 beside your platform, and 0 elsewhere. 21 Attempts to autosniff this even if you don't. 22 --*/ 23 24 25 /*-- 26 Plan 9 from Bell Labs 27 --*/ 28 #define BZ_PLAN9 1 29 #define BZ_UNIX 0 30 31 #define exit(x) exits((x) ? "whoops" : nil) 32 #define size_t ulong 33 34 #ifdef __GNUC__ 35 # define NORETURN __attribute__ ((noreturn)) 36 #else 37 # define NORETURN /**/ 38 #endif 39 40 /*-- 41 Some more stuff for all platforms :-) 42 This might have to get moved into the platform-specific 43 header files if we encounter a machine with different sizes. 44 --*/ 45 46 typedef char Char; 47 typedef unsigned char Bool; 48 typedef unsigned char UChar; 49 typedef int Int32; 50 typedef unsigned int UInt32; 51 typedef short Int16; 52 typedef unsigned short UInt16; 53 54 #define True ((Bool)1) 55 #define False ((Bool)0) 56 57 /*-- 58 IntNative is your platform's `native' int size. 59 Only here to avoid probs with 64-bit platforms. 60 --*/ 61 typedef int IntNative; 62 63 #include "bzfs.h" 64 #include "bzlib.h" 65 #include "bzlib_private.h" 66 67 static int 68 bunzip(int ofd, char *ofile, Biobuf *bin) 69 { 70 int e, n, done, onemore; 71 char buf[8192]; 72 char obuf[8192]; 73 Biobuf bout; 74 bz_stream strm; 75 76 USED(ofile); 77 78 memset(&strm, 0, sizeof strm); 79 BZ2_bzDecompressInit(&strm, 0, 0); 80 81 strm.next_in = buf; 82 strm.avail_in = 0; 83 strm.next_out = obuf; 84 strm.avail_out = sizeof obuf; 85 86 done = 0; 87 Binit(&bout, ofd, OWRITE); 88 89 /* 90 * onemore is a crummy hack to go 'round the loop 91 * once after we finish, to flush the output buffer. 92 */ 93 onemore = 1; 94 SET(e); 95 do { 96 if(!done && strm.avail_in < sizeof buf) { 97 if(strm.avail_in) 98 memmove(buf, strm.next_in, strm.avail_in); 99 100 n = Bread(bin, buf+strm.avail_in, sizeof(buf)-strm.avail_in); 101 if(n <= 0) 102 done = 1; 103 else 104 strm.avail_in += n; 105 strm.next_in = buf; 106 } 107 if(strm.avail_out < sizeof obuf) { 108 Bwrite(&bout, obuf, sizeof(obuf)-strm.avail_out); 109 strm.next_out = obuf; 110 strm.avail_out = sizeof obuf; 111 } 112 113 if(onemore == 0) 114 break; 115 } while((e=BZ2_bzDecompress(&strm)) == BZ_OK || onemore--); 116 117 if(e != BZ_STREAM_END) { 118 fprint(2, "bunzip2: decompress failed\n"); 119 return 0; 120 } 121 122 if(BZ2_bzDecompressEnd(&strm) != BZ_OK) { 123 fprint(2, "bunzip2: decompress end failed (can't happen)\n"); 124 return 0; 125 } 126 127 Bterm(&bout); 128 129 return 1; 130 } 131 132 void 133 _unbzip(int in, int out) 134 { 135 Biobuf bin; 136 137 Binit(&bin, in, OREAD); 138 if(bunzip(out, nil, &bin) != 1) { 139 fprint(2, "bunzip2 failed\n"); 140 _exits("bunzip2"); 141 } 142 } 143 144 int 145 unbzip(int in) 146 { 147 int rv, out, p[2]; 148 149 if(pipe(p) < 0) 150 sysfatal("pipe: %r"); 151 152 rv = p[0]; 153 out = p[1]; 154 switch(rfork(RFPROC|RFFDG|RFNOTEG|RFMEM)){ 155 case -1: 156 sysfatal("fork: %r"); 157 case 0: 158 close(rv); 159 break; 160 default: 161 close(in); 162 close(out); 163 return rv; 164 } 165 166 _unbzip(in, out); 167 _exits(0); 168 return -1; /* not reached */ 169 } 170 171 int bz_config_ok ( void ) 172 { 173 if (sizeof(int) != 4) return 0; 174 if (sizeof(short) != 2) return 0; 175 if (sizeof(char) != 1) return 0; 176 return 1; 177 } 178 179 void* default_bzalloc(void *o, int items, int size) 180 { 181 USED(o); 182 return sbrk(items*size); 183 } 184 185 void default_bzfree(void*, void*) 186 { 187 } 188 189 void 190 bz_internal_error(int) 191 { 192 abort(); 193 } 194 195 /*-------------------------------------------------------------*/ 196 /*--- Decompression machinery ---*/ 197 /*--- decompress.c ---*/ 198 /*-------------------------------------------------------------*/ 199 200 /*-- 201 This file is a part of bzip2 and/or libbzip2, a program and 202 library for lossless, block-sorting data compression. 203 204 Copyright (C) 1996-2000 Julian R Seward. All rights reserved. 205 206 Redistribution and use in source and binary forms, with or without 207 modification, are permitted provided that the following conditions 208 are met: 209 210 1. Redistributions of source code must retain the above copyright 211 notice, this list of conditions and the following disclaimer. 212 213 2. The origin of this software must not be misrepresented; you must 214 not claim that you wrote the original software. If you use this 215 software in a product, an acknowledgment in the product 216 documentation would be appreciated but is not required. 217 218 3. Altered source versions must be plainly marked as such, and must 219 not be misrepresented as being the original software. 220 221 4. The name of the author may not be used to endorse or promote 222 products derived from this software without specific prior written 223 permission. 224 225 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 226 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 227 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 228 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 229 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 230 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 231 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 232 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 233 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 234 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 235 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 236 237 Julian Seward, Cambridge, UK. 238 jseward@acm.org 239 bzip2/libbzip2 version 1.0 of 21 March 2000 240 241 This program is based on (at least) the work of: 242 Mike Burrows 243 David Wheeler 244 Peter Fenwick 245 Alistair Moffat 246 Radford Neal 247 Ian H. Witten 248 Robert Sedgewick 249 Jon L. Bentley 250 251 For more information on these sources, see the manual. 252 --*/ 253 254 255 256 /*---------------------------------------------------*/ 257 static 258 void makeMaps_d ( DState* s ) 259 { 260 Int32 i; 261 s->nInUse = 0; 262 for (i = 0; i < 256; i++) 263 if (s->inUse[i]) { 264 s->seqToUnseq[s->nInUse] = i; 265 s->nInUse++; 266 } 267 } 268 269 270 /*---------------------------------------------------*/ 271 #define RETURN(rrr) \ 272 { retVal = rrr; goto save_state_and_return; }; 273 274 #define GET_BITS(lll,vvv,nnn) \ 275 case lll: \ 276 { int x; if((retVal = getbits(s, lll, &x, nnn)) != 99) \ 277 goto save_state_and_return; vvv=x; }\ 278 279 int 280 getbits(DState *s, int lll, int *vvv, int nnn) 281 { 282 s->state = lll; 283 284 for(;;) { 285 if (s->bsLive >= nnn) { 286 UInt32 v; 287 v = (s->bsBuff >> 288 (s->bsLive-nnn)) & ((1 << nnn)-1); 289 s->bsLive -= nnn; 290 *vvv = v; 291 return 99; 292 } 293 if (s->strm->avail_in == 0) return BZ_OK; 294 s->bsBuff 295 = (s->bsBuff << 8) | 296 ((UInt32) 297 (*((UChar*)(s->strm->next_in)))); 298 s->bsLive += 8; 299 s->strm->next_in++; 300 s->strm->avail_in--; 301 s->strm->total_in_lo32++; 302 if (s->strm->total_in_lo32 == 0) 303 s->strm->total_in_hi32++; 304 } 305 } 306 307 #define GET_UCHAR(lll,uuu) \ 308 GET_BITS(lll,uuu,8) 309 310 #define GET_BIT(lll,uuu) \ 311 GET_BITS(lll,uuu,1) 312 313 /*---------------------------------------------------*/ 314 #define GET_MTF_VAL(label1,label2,lval) \ 315 { \ 316 if (groupPos == 0) { \ 317 groupNo++; \ 318 if (groupNo >= nSelectors) \ 319 RETURN(BZ_DATA_ERROR); \ 320 groupPos = BZ_G_SIZE; \ 321 gSel = s->selector[groupNo]; \ 322 gMinlen = s->minLens[gSel]; \ 323 gLimit = &(s->limit[gSel][0]); \ 324 gPerm = &(s->perm[gSel][0]); \ 325 gBase = &(s->base[gSel][0]); \ 326 } \ 327 groupPos--; \ 328 zn = gMinlen; \ 329 GET_BITS(label1, zvec, zn); \ 330 while (1) { \ 331 if (zn > 20 /* the longest code */) \ 332 RETURN(BZ_DATA_ERROR); \ 333 if (zvec <= gLimit[zn]) break; \ 334 zn++; \ 335 GET_BIT(label2, zj); \ 336 zvec = (zvec << 1) | zj; \ 337 }; \ 338 if (zvec - gBase[zn] < 0 \ 339 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ 340 RETURN(BZ_DATA_ERROR); \ 341 lval = gPerm[zvec - gBase[zn]]; \ 342 } 343 344 345 /*---------------------------------------------------*/ 346 Int32 BZ2_decompress ( DState* s ) 347 { 348 UChar uc; 349 Int32 retVal; 350 Int32 minLen, maxLen; 351 bz_stream* strm = s->strm; 352 353 /* stuff that needs to be saved/restored */ 354 Int32 i; 355 Int32 j; 356 Int32 t; 357 Int32 alphaSize; 358 Int32 nGroups; 359 Int32 nSelectors; 360 Int32 EOB; 361 Int32 groupNo; 362 Int32 groupPos; 363 Int32 nextSym; 364 Int32 nblockMAX; 365 Int32 nblock; 366 Int32 es; 367 Int32 N; 368 Int32 curr; 369 Int32 zt; 370 Int32 zn; 371 Int32 zvec; 372 Int32 zj; 373 Int32 gSel; 374 Int32 gMinlen; 375 Int32* gLimit; 376 Int32* gBase; 377 Int32* gPerm; 378 379 if (s->state == BZ_X_MAGIC_1) { 380 /*initialise the save area*/ 381 s->save_i = 0; 382 s->save_j = 0; 383 s->save_t = 0; 384 s->save_alphaSize = 0; 385 s->save_nGroups = 0; 386 s->save_nSelectors = 0; 387 s->save_EOB = 0; 388 s->save_groupNo = 0; 389 s->save_groupPos = 0; 390 s->save_nextSym = 0; 391 s->save_nblockMAX = 0; 392 s->save_nblock = 0; 393 s->save_es = 0; 394 s->save_N = 0; 395 s->save_curr = 0; 396 s->save_zt = 0; 397 s->save_zn = 0; 398 s->save_zvec = 0; 399 s->save_zj = 0; 400 s->save_gSel = 0; 401 s->save_gMinlen = 0; 402 s->save_gLimit = NULL; 403 s->save_gBase = NULL; 404 s->save_gPerm = NULL; 405 } 406 407 /*restore from the save area*/ 408 i = s->save_i; 409 j = s->save_j; 410 t = s->save_t; 411 alphaSize = s->save_alphaSize; 412 nGroups = s->save_nGroups; 413 nSelectors = s->save_nSelectors; 414 EOB = s->save_EOB; 415 groupNo = s->save_groupNo; 416 groupPos = s->save_groupPos; 417 nextSym = s->save_nextSym; 418 nblockMAX = s->save_nblockMAX; 419 nblock = s->save_nblock; 420 es = s->save_es; 421 N = s->save_N; 422 curr = s->save_curr; 423 zt = s->save_zt; 424 zn = s->save_zn; 425 zvec = s->save_zvec; 426 zj = s->save_zj; 427 gSel = s->save_gSel; 428 gMinlen = s->save_gMinlen; 429 gLimit = s->save_gLimit; 430 gBase = s->save_gBase; 431 gPerm = s->save_gPerm; 432 433 retVal = BZ_OK; 434 435 switch (s->state) { 436 437 GET_UCHAR(BZ_X_MAGIC_1, uc); 438 if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC); 439 440 GET_UCHAR(BZ_X_MAGIC_2, uc); 441 if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC); 442 443 GET_UCHAR(BZ_X_MAGIC_3, uc) 444 if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC); 445 446 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 447 if (s->blockSize100k < '1' || 448 s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC); 449 s->blockSize100k -= '0'; 450 451 if (0 && s->smallDecompress) { 452 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 453 s->ll4 = BZALLOC( 454 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 455 ); 456 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 457 } else { 458 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 459 if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 460 } 461 462 GET_UCHAR(BZ_X_BLKHDR_1, uc); 463 464 if (uc == 0x17) goto endhdr_2; 465 if (uc != 0x31) RETURN(BZ_DATA_ERROR); 466 GET_UCHAR(BZ_X_BLKHDR_2, uc); 467 if (uc != 0x41) RETURN(BZ_DATA_ERROR); 468 GET_UCHAR(BZ_X_BLKHDR_3, uc); 469 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 470 GET_UCHAR(BZ_X_BLKHDR_4, uc); 471 if (uc != 0x26) RETURN(BZ_DATA_ERROR); 472 GET_UCHAR(BZ_X_BLKHDR_5, uc); 473 if (uc != 0x53) RETURN(BZ_DATA_ERROR); 474 GET_UCHAR(BZ_X_BLKHDR_6, uc); 475 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 476 477 s->currBlockNo++; 478 // if (s->verbosity >= 2) 479 // VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 480 481 s->storedBlockCRC = 0; 482 GET_UCHAR(BZ_X_BCRC_1, uc); 483 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 484 GET_UCHAR(BZ_X_BCRC_2, uc); 485 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 486 GET_UCHAR(BZ_X_BCRC_3, uc); 487 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 488 GET_UCHAR(BZ_X_BCRC_4, uc); 489 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 490 491 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 492 493 s->origPtr = 0; 494 GET_UCHAR(BZ_X_ORIGPTR_1, uc); 495 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 496 GET_UCHAR(BZ_X_ORIGPTR_2, uc); 497 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 498 GET_UCHAR(BZ_X_ORIGPTR_3, uc); 499 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 500 501 if (s->origPtr < 0) 502 RETURN(BZ_DATA_ERROR); 503 if (s->origPtr > 10 + 100000*s->blockSize100k) 504 RETURN(BZ_DATA_ERROR); 505 506 /*--- Receive the mapping table ---*/ 507 for (i = 0; i < 16; i++) { 508 GET_BIT(BZ_X_MAPPING_1, uc); 509 if (uc == 1) 510 s->inUse16[i] = True; else 511 s->inUse16[i] = False; 512 } 513 514 for (i = 0; i < 256; i++) s->inUse[i] = False; 515 516 for (i = 0; i < 16; i++) 517 if (s->inUse16[i]) 518 for (j = 0; j < 16; j++) { 519 GET_BIT(BZ_X_MAPPING_2, uc); 520 if (uc == 1) s->inUse[i * 16 + j] = True; 521 } 522 makeMaps_d ( s ); 523 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); 524 alphaSize = s->nInUse+2; 525 526 /*--- Now the selectors ---*/ 527 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 528 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); 529 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 530 if (nSelectors < 1) RETURN(BZ_DATA_ERROR); 531 for (i = 0; i < nSelectors; i++) { 532 j = 0; 533 while (True) { 534 GET_BIT(BZ_X_SELECTOR_3, uc); 535 if (uc == 0) break; 536 j++; 537 if (j >= nGroups) RETURN(BZ_DATA_ERROR); 538 } 539 s->selectorMtf[i] = j; 540 } 541 542 /*--- Undo the MTF values for the selectors. ---*/ 543 { 544 UChar pos[BZ_N_GROUPS], tmp, v; 545 for (v = 0; v < nGroups; v++) pos[v] = v; 546 547 for (i = 0; i < nSelectors; i++) { 548 v = s->selectorMtf[i]; 549 tmp = pos[v]; 550 while (v > 0) { pos[v] = pos[v-1]; v--; } 551 pos[0] = tmp; 552 s->selector[i] = tmp; 553 } 554 } 555 556 /*--- Now the coding tables ---*/ 557 for (t = 0; t < nGroups; t++) { 558 GET_BITS(BZ_X_CODING_1, curr, 5); 559 for (i = 0; i < alphaSize; i++) { 560 while (True) { 561 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 562 GET_BIT(BZ_X_CODING_2, uc); 563 if (uc == 0) break; 564 GET_BIT(BZ_X_CODING_3, uc); 565 if (uc == 0) curr++; else curr--; 566 } 567 s->len[t][i] = curr; 568 } 569 } 570 571 /*--- Create the Huffman decoding tables ---*/ 572 for (t = 0; t < nGroups; t++) { 573 minLen = 32; 574 maxLen = 0; 575 for (i = 0; i < alphaSize; i++) { 576 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 577 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 578 } 579 BZ2_hbCreateDecodeTables ( 580 &(s->limit[t][0]), 581 &(s->base[t][0]), 582 &(s->perm[t][0]), 583 &(s->len[t][0]), 584 minLen, maxLen, alphaSize 585 ); 586 s->minLens[t] = minLen; 587 } 588 589 /*--- Now the MTF values ---*/ 590 591 EOB = s->nInUse+1; 592 nblockMAX = 100000 * s->blockSize100k; 593 groupNo = -1; 594 groupPos = 0; 595 596 for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 597 598 /*-- MTF init --*/ 599 { 600 Int32 ii, jj, kk; 601 kk = MTFA_SIZE-1; 602 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 603 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 604 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 605 kk--; 606 } 607 s->mtfbase[ii] = kk + 1; 608 } 609 } 610 /*-- end MTF init --*/ 611 612 nblock = 0; 613 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 614 615 while (True) { 616 617 if (nextSym == EOB) break; 618 619 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 620 621 es = -1; 622 N = 1; 623 do { 624 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 625 if (nextSym == BZ_RUNB) es = es + (1+1) * N; 626 N = N * 2; 627 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 628 } 629 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 630 631 es++; 632 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 633 s->unzftab[uc] += es; 634 635 if (0 && s->smallDecompress) 636 while (es > 0) { 637 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 638 s->ll16[nblock] = (UInt16)uc; 639 nblock++; 640 es--; 641 } 642 else 643 while (es > 0) { 644 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 645 s->tt[nblock] = (UInt32)uc; 646 nblock++; 647 es--; 648 }; 649 650 continue; 651 652 } else { 653 654 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 655 656 /*-- uc = MTF ( nextSym-1 ) --*/ 657 { 658 Int32 ii, jj, kk, pp, lno, off; 659 UInt32 nn; 660 nn = (UInt32)(nextSym - 1); 661 662 if (nn < MTFL_SIZE) { 663 /* avoid general-case expense */ 664 pp = s->mtfbase[0]; 665 uc = s->mtfa[pp+nn]; 666 while (nn > 3) { 667 Int32 z = pp+nn; 668 s->mtfa[(z) ] = s->mtfa[(z)-1]; 669 s->mtfa[(z)-1] = s->mtfa[(z)-2]; 670 s->mtfa[(z)-2] = s->mtfa[(z)-3]; 671 s->mtfa[(z)-3] = s->mtfa[(z)-4]; 672 nn -= 4; 673 } 674 while (nn > 0) { 675 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 676 }; 677 s->mtfa[pp] = uc; 678 } else { 679 /* general case */ 680 lno = nn / MTFL_SIZE; 681 off = nn % MTFL_SIZE; 682 pp = s->mtfbase[lno] + off; 683 uc = s->mtfa[pp]; 684 while (pp > s->mtfbase[lno]) { 685 s->mtfa[pp] = s->mtfa[pp-1]; pp--; 686 }; 687 s->mtfbase[lno]++; 688 while (lno > 0) { 689 s->mtfbase[lno]--; 690 s->mtfa[s->mtfbase[lno]] 691 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 692 lno--; 693 } 694 s->mtfbase[0]--; 695 s->mtfa[s->mtfbase[0]] = uc; 696 if (s->mtfbase[0] == 0) { 697 kk = MTFA_SIZE-1; 698 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 699 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 700 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 701 kk--; 702 } 703 s->mtfbase[ii] = kk + 1; 704 } 705 } 706 } 707 } 708 /*-- end uc = MTF ( nextSym-1 ) --*/ 709 710 s->unzftab[s->seqToUnseq[uc]]++; 711 if (0 && s->smallDecompress) 712 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 713 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 714 nblock++; 715 716 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 717 continue; 718 } 719 } 720 721 /* Now we know what nblock is, we can do a better sanity 722 check on s->origPtr. 723 */ 724 if (s->origPtr < 0 || s->origPtr >= nblock) 725 RETURN(BZ_DATA_ERROR); 726 727 s->state_out_len = 0; 728 s->state_out_ch = 0; 729 BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 730 s->state = BZ_X_OUTPUT; 731 // if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 732 733 /*-- Set up cftab to facilitate generation of T^(-1) --*/ 734 s->cftab[0] = 0; 735 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 736 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 737 738 if (0 && s->smallDecompress) { 739 740 /*-- Make a copy of cftab, used in generation of T --*/ 741 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 742 743 /*-- compute the T vector --*/ 744 for (i = 0; i < nblock; i++) { 745 uc = (UChar)(s->ll16[i]); 746 SET_LL(i, s->cftabCopy[uc]); 747 s->cftabCopy[uc]++; 748 } 749 750 /*-- Compute T^(-1) by pointer reversal on T --*/ 751 i = s->origPtr; 752 j = GET_LL(i); 753 do { 754 Int32 tmp = GET_LL(j); 755 SET_LL(j, i); 756 i = j; 757 j = tmp; 758 } 759 while (i != s->origPtr); 760 761 s->tPos = s->origPtr; 762 s->nblock_used = 0; 763 if (s->blockRandomised) { 764 BZ_RAND_INIT_MASK; 765 BZ_GET_SMALL(s->k0); s->nblock_used++; 766 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 767 } else { 768 BZ_GET_SMALL(s->k0); s->nblock_used++; 769 } 770 771 } else { 772 773 /*-- compute the T^(-1) vector --*/ 774 for (i = 0; i < nblock; i++) { 775 uc = (UChar)(s->tt[i] & 0xff); 776 s->tt[s->cftab[uc]] |= (i << 8); 777 s->cftab[uc]++; 778 } 779 780 s->tPos = s->tt[s->origPtr] >> 8; 781 s->nblock_used = 0; 782 if (s->blockRandomised) { 783 BZ_RAND_INIT_MASK; 784 BZ_GET_FAST(s->k0); s->nblock_used++; 785 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 786 } else { 787 BZ_GET_FAST(s->k0); s->nblock_used++; 788 } 789 790 } 791 792 RETURN(BZ_OK); 793 794 795 796 endhdr_2: 797 798 GET_UCHAR(BZ_X_ENDHDR_2, uc); 799 if (uc != 0x72) RETURN(BZ_DATA_ERROR); 800 GET_UCHAR(BZ_X_ENDHDR_3, uc); 801 if (uc != 0x45) RETURN(BZ_DATA_ERROR); 802 GET_UCHAR(BZ_X_ENDHDR_4, uc); 803 if (uc != 0x38) RETURN(BZ_DATA_ERROR); 804 GET_UCHAR(BZ_X_ENDHDR_5, uc); 805 if (uc != 0x50) RETURN(BZ_DATA_ERROR); 806 GET_UCHAR(BZ_X_ENDHDR_6, uc); 807 if (uc != 0x90) RETURN(BZ_DATA_ERROR); 808 809 s->storedCombinedCRC = 0; 810 GET_UCHAR(BZ_X_CCRC_1, uc); 811 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 812 GET_UCHAR(BZ_X_CCRC_2, uc); 813 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 814 GET_UCHAR(BZ_X_CCRC_3, uc); 815 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 816 GET_UCHAR(BZ_X_CCRC_4, uc); 817 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 818 819 s->state = BZ_X_IDLE; 820 RETURN(BZ_STREAM_END); 821 822 default: AssertH ( False, 4001 ); 823 } 824 825 AssertH ( False, 4002 ); 826 827 save_state_and_return: 828 829 s->save_i = i; 830 s->save_j = j; 831 s->save_t = t; 832 s->save_alphaSize = alphaSize; 833 s->save_nGroups = nGroups; 834 s->save_nSelectors = nSelectors; 835 s->save_EOB = EOB; 836 s->save_groupNo = groupNo; 837 s->save_groupPos = groupPos; 838 s->save_nextSym = nextSym; 839 s->save_nblockMAX = nblockMAX; 840 s->save_nblock = nblock; 841 s->save_es = es; 842 s->save_N = N; 843 s->save_curr = curr; 844 s->save_zt = zt; 845 s->save_zn = zn; 846 s->save_zvec = zvec; 847 s->save_zj = zj; 848 s->save_gSel = gSel; 849 s->save_gMinlen = gMinlen; 850 s->save_gLimit = gLimit; 851 s->save_gBase = gBase; 852 s->save_gPerm = gPerm; 853 854 return retVal; 855 } 856 857 858 /*-------------------------------------------------------------*/ 859 /*--- end decompress.c ---*/ 860 /*-------------------------------------------------------------*/ 861