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 return -1; /* KEN */ 306 } 307 308 #define GET_UCHAR(lll,uuu) \ 309 GET_BITS(lll,uuu,8) 310 311 #define GET_BIT(lll,uuu) \ 312 GET_BITS(lll,uuu,1) 313 314 /*---------------------------------------------------*/ 315 #define GET_MTF_VAL(label1,label2,lval) \ 316 { \ 317 if (groupPos == 0) { \ 318 groupNo++; \ 319 if (groupNo >= nSelectors) \ 320 RETURN(BZ_DATA_ERROR); \ 321 groupPos = BZ_G_SIZE; \ 322 gSel = s->selector[groupNo]; \ 323 gMinlen = s->minLens[gSel]; \ 324 gLimit = &(s->limit[gSel][0]); \ 325 gPerm = &(s->perm[gSel][0]); \ 326 gBase = &(s->base[gSel][0]); \ 327 } \ 328 groupPos--; \ 329 zn = gMinlen; \ 330 GET_BITS(label1, zvec, zn); \ 331 while (1) { \ 332 if (zn > 20 /* the longest code */) \ 333 RETURN(BZ_DATA_ERROR); \ 334 if (zvec <= gLimit[zn]) break; \ 335 zn++; \ 336 GET_BIT(label2, zj); \ 337 zvec = (zvec << 1) | zj; \ 338 }; \ 339 if (zvec - gBase[zn] < 0 \ 340 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ 341 RETURN(BZ_DATA_ERROR); \ 342 lval = gPerm[zvec - gBase[zn]]; \ 343 } 344 345 346 /*---------------------------------------------------*/ 347 Int32 BZ2_decompress ( DState* s ) 348 { 349 UChar uc; 350 Int32 retVal; 351 Int32 minLen, maxLen; 352 bz_stream* strm = s->strm; 353 354 /* stuff that needs to be saved/restored */ 355 Int32 i; 356 Int32 j; 357 Int32 t; 358 Int32 alphaSize; 359 Int32 nGroups; 360 Int32 nSelectors; 361 Int32 EOB; 362 Int32 groupNo; 363 Int32 groupPos; 364 Int32 nextSym; 365 Int32 nblockMAX; 366 Int32 nblock; 367 Int32 es; 368 Int32 N; 369 Int32 curr; 370 Int32 zt; 371 Int32 zn; 372 Int32 zvec; 373 Int32 zj; 374 Int32 gSel; 375 Int32 gMinlen; 376 Int32* gLimit; 377 Int32* gBase; 378 Int32* gPerm; 379 380 if (s->state == BZ_X_MAGIC_1) { 381 /*initialise the save area*/ 382 s->save_i = 0; 383 s->save_j = 0; 384 s->save_t = 0; 385 s->save_alphaSize = 0; 386 s->save_nGroups = 0; 387 s->save_nSelectors = 0; 388 s->save_EOB = 0; 389 s->save_groupNo = 0; 390 s->save_groupPos = 0; 391 s->save_nextSym = 0; 392 s->save_nblockMAX = 0; 393 s->save_nblock = 0; 394 s->save_es = 0; 395 s->save_N = 0; 396 s->save_curr = 0; 397 s->save_zt = 0; 398 s->save_zn = 0; 399 s->save_zvec = 0; 400 s->save_zj = 0; 401 s->save_gSel = 0; 402 s->save_gMinlen = 0; 403 s->save_gLimit = NULL; 404 s->save_gBase = NULL; 405 s->save_gPerm = NULL; 406 } 407 408 /*restore from the save area*/ 409 i = s->save_i; 410 j = s->save_j; 411 t = s->save_t; 412 alphaSize = s->save_alphaSize; 413 nGroups = s->save_nGroups; 414 nSelectors = s->save_nSelectors; 415 EOB = s->save_EOB; 416 groupNo = s->save_groupNo; 417 groupPos = s->save_groupPos; 418 nextSym = s->save_nextSym; 419 nblockMAX = s->save_nblockMAX; 420 nblock = s->save_nblock; 421 es = s->save_es; 422 N = s->save_N; 423 curr = s->save_curr; 424 zt = s->save_zt; 425 zn = s->save_zn; 426 zvec = s->save_zvec; 427 zj = s->save_zj; 428 gSel = s->save_gSel; 429 gMinlen = s->save_gMinlen; 430 gLimit = s->save_gLimit; 431 gBase = s->save_gBase; 432 gPerm = s->save_gPerm; 433 434 retVal = BZ_OK; 435 436 switch (s->state) { 437 438 GET_UCHAR(BZ_X_MAGIC_1, uc); 439 if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC); 440 441 GET_UCHAR(BZ_X_MAGIC_2, uc); 442 if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC); 443 444 GET_UCHAR(BZ_X_MAGIC_3, uc) 445 if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC); 446 447 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 448 if (s->blockSize100k < '1' || 449 s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC); 450 s->blockSize100k -= '0'; 451 452 if (0 && s->smallDecompress) { 453 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 454 s->ll4 = BZALLOC( 455 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 456 ); 457 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 458 } else { 459 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 460 if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 461 } 462 463 GET_UCHAR(BZ_X_BLKHDR_1, uc); 464 465 if (uc == 0x17) goto endhdr_2; 466 if (uc != 0x31) RETURN(BZ_DATA_ERROR); 467 GET_UCHAR(BZ_X_BLKHDR_2, uc); 468 if (uc != 0x41) RETURN(BZ_DATA_ERROR); 469 GET_UCHAR(BZ_X_BLKHDR_3, uc); 470 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 471 GET_UCHAR(BZ_X_BLKHDR_4, uc); 472 if (uc != 0x26) RETURN(BZ_DATA_ERROR); 473 GET_UCHAR(BZ_X_BLKHDR_5, uc); 474 if (uc != 0x53) RETURN(BZ_DATA_ERROR); 475 GET_UCHAR(BZ_X_BLKHDR_6, uc); 476 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 477 478 s->currBlockNo++; 479 // if (s->verbosity >= 2) 480 // VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 481 482 s->storedBlockCRC = 0; 483 GET_UCHAR(BZ_X_BCRC_1, uc); 484 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 485 GET_UCHAR(BZ_X_BCRC_2, uc); 486 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 487 GET_UCHAR(BZ_X_BCRC_3, uc); 488 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 489 GET_UCHAR(BZ_X_BCRC_4, uc); 490 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 491 492 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 493 494 s->origPtr = 0; 495 GET_UCHAR(BZ_X_ORIGPTR_1, uc); 496 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 497 GET_UCHAR(BZ_X_ORIGPTR_2, uc); 498 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 499 GET_UCHAR(BZ_X_ORIGPTR_3, uc); 500 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 501 502 if (s->origPtr < 0) 503 RETURN(BZ_DATA_ERROR); 504 if (s->origPtr > 10 + 100000*s->blockSize100k) 505 RETURN(BZ_DATA_ERROR); 506 507 /*--- Receive the mapping table ---*/ 508 for (i = 0; i < 16; i++) { 509 GET_BIT(BZ_X_MAPPING_1, uc); 510 if (uc == 1) 511 s->inUse16[i] = True; else 512 s->inUse16[i] = False; 513 } 514 515 for (i = 0; i < 256; i++) s->inUse[i] = False; 516 517 for (i = 0; i < 16; i++) 518 if (s->inUse16[i]) 519 for (j = 0; j < 16; j++) { 520 GET_BIT(BZ_X_MAPPING_2, uc); 521 if (uc == 1) s->inUse[i * 16 + j] = True; 522 } 523 makeMaps_d ( s ); 524 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); 525 alphaSize = s->nInUse+2; 526 527 /*--- Now the selectors ---*/ 528 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 529 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); 530 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 531 if (nSelectors < 1) RETURN(BZ_DATA_ERROR); 532 for (i = 0; i < nSelectors; i++) { 533 j = 0; 534 while (True) { 535 GET_BIT(BZ_X_SELECTOR_3, uc); 536 if (uc == 0) break; 537 j++; 538 if (j >= nGroups) RETURN(BZ_DATA_ERROR); 539 } 540 s->selectorMtf[i] = j; 541 } 542 543 /*--- Undo the MTF values for the selectors. ---*/ 544 { 545 UChar pos[BZ_N_GROUPS], tmp, v; 546 for (v = 0; v < nGroups; v++) pos[v] = v; 547 548 for (i = 0; i < nSelectors; i++) { 549 v = s->selectorMtf[i]; 550 tmp = pos[v]; 551 while (v > 0) { pos[v] = pos[v-1]; v--; } 552 pos[0] = tmp; 553 s->selector[i] = tmp; 554 } 555 } 556 557 /*--- Now the coding tables ---*/ 558 for (t = 0; t < nGroups; t++) { 559 GET_BITS(BZ_X_CODING_1, curr, 5); 560 for (i = 0; i < alphaSize; i++) { 561 while (True) { 562 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 563 GET_BIT(BZ_X_CODING_2, uc); 564 if (uc == 0) break; 565 GET_BIT(BZ_X_CODING_3, uc); 566 if (uc == 0) curr++; else curr--; 567 } 568 s->len[t][i] = curr; 569 } 570 } 571 572 /*--- Create the Huffman decoding tables ---*/ 573 for (t = 0; t < nGroups; t++) { 574 minLen = 32; 575 maxLen = 0; 576 for (i = 0; i < alphaSize; i++) { 577 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 578 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 579 } 580 BZ2_hbCreateDecodeTables ( 581 &(s->limit[t][0]), 582 &(s->base[t][0]), 583 &(s->perm[t][0]), 584 &(s->len[t][0]), 585 minLen, maxLen, alphaSize 586 ); 587 s->minLens[t] = minLen; 588 } 589 590 /*--- Now the MTF values ---*/ 591 592 EOB = s->nInUse+1; 593 nblockMAX = 100000 * s->blockSize100k; 594 groupNo = -1; 595 groupPos = 0; 596 597 for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 598 599 /*-- MTF init --*/ 600 { 601 Int32 ii, jj, kk; 602 kk = MTFA_SIZE-1; 603 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 604 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 605 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 606 kk--; 607 } 608 s->mtfbase[ii] = kk + 1; 609 } 610 } 611 /*-- end MTF init --*/ 612 613 nblock = 0; 614 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 615 616 while (True) { 617 618 if (nextSym == EOB) break; 619 620 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 621 622 es = -1; 623 N = 1; 624 do { 625 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 626 if (nextSym == BZ_RUNB) es = es + (1+1) * N; 627 N = N * 2; 628 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 629 } 630 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 631 632 es++; 633 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 634 s->unzftab[uc] += es; 635 636 if (0 && s->smallDecompress) 637 while (es > 0) { 638 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 639 s->ll16[nblock] = (UInt16)uc; 640 nblock++; 641 es--; 642 } 643 else 644 while (es > 0) { 645 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 646 s->tt[nblock] = (UInt32)uc; 647 nblock++; 648 es--; 649 }; 650 651 continue; 652 653 } else { 654 655 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 656 657 /*-- uc = MTF ( nextSym-1 ) --*/ 658 { 659 Int32 ii, jj, kk, pp, lno, off; 660 UInt32 nn; 661 nn = (UInt32)(nextSym - 1); 662 663 if (nn < MTFL_SIZE) { 664 /* avoid general-case expense */ 665 pp = s->mtfbase[0]; 666 uc = s->mtfa[pp+nn]; 667 while (nn > 3) { 668 Int32 z = pp+nn; 669 s->mtfa[(z) ] = s->mtfa[(z)-1]; 670 s->mtfa[(z)-1] = s->mtfa[(z)-2]; 671 s->mtfa[(z)-2] = s->mtfa[(z)-3]; 672 s->mtfa[(z)-3] = s->mtfa[(z)-4]; 673 nn -= 4; 674 } 675 while (nn > 0) { 676 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 677 }; 678 s->mtfa[pp] = uc; 679 } else { 680 /* general case */ 681 lno = nn / MTFL_SIZE; 682 off = nn % MTFL_SIZE; 683 pp = s->mtfbase[lno] + off; 684 uc = s->mtfa[pp]; 685 while (pp > s->mtfbase[lno]) { 686 s->mtfa[pp] = s->mtfa[pp-1]; pp--; 687 }; 688 s->mtfbase[lno]++; 689 while (lno > 0) { 690 s->mtfbase[lno]--; 691 s->mtfa[s->mtfbase[lno]] 692 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 693 lno--; 694 } 695 s->mtfbase[0]--; 696 s->mtfa[s->mtfbase[0]] = uc; 697 if (s->mtfbase[0] == 0) { 698 kk = MTFA_SIZE-1; 699 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 700 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 701 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 702 kk--; 703 } 704 s->mtfbase[ii] = kk + 1; 705 } 706 } 707 } 708 } 709 /*-- end uc = MTF ( nextSym-1 ) --*/ 710 711 s->unzftab[s->seqToUnseq[uc]]++; 712 if (0 && s->smallDecompress) 713 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 714 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 715 nblock++; 716 717 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 718 continue; 719 } 720 } 721 722 /* Now we know what nblock is, we can do a better sanity 723 check on s->origPtr. 724 */ 725 if (s->origPtr < 0 || s->origPtr >= nblock) 726 RETURN(BZ_DATA_ERROR); 727 728 s->state_out_len = 0; 729 s->state_out_ch = 0; 730 BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 731 s->state = BZ_X_OUTPUT; 732 // if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 733 734 /*-- Set up cftab to facilitate generation of T^(-1) --*/ 735 s->cftab[0] = 0; 736 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 737 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 738 739 if (0 && s->smallDecompress) { 740 741 /*-- Make a copy of cftab, used in generation of T --*/ 742 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 743 744 /*-- compute the T vector --*/ 745 for (i = 0; i < nblock; i++) { 746 uc = (UChar)(s->ll16[i]); 747 SET_LL(i, s->cftabCopy[uc]); 748 s->cftabCopy[uc]++; 749 } 750 751 /*-- Compute T^(-1) by pointer reversal on T --*/ 752 i = s->origPtr; 753 j = GET_LL(i); 754 do { 755 Int32 tmp = GET_LL(j); 756 SET_LL(j, i); 757 i = j; 758 j = tmp; 759 } 760 while (i != s->origPtr); 761 762 s->tPos = s->origPtr; 763 s->nblock_used = 0; 764 if (s->blockRandomised) { 765 BZ_RAND_INIT_MASK; 766 BZ_GET_SMALL(s->k0); s->nblock_used++; 767 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 768 } else { 769 BZ_GET_SMALL(s->k0); s->nblock_used++; 770 } 771 772 } else { 773 774 /*-- compute the T^(-1) vector --*/ 775 for (i = 0; i < nblock; i++) { 776 uc = (UChar)(s->tt[i] & 0xff); 777 s->tt[s->cftab[uc]] |= (i << 8); 778 s->cftab[uc]++; 779 } 780 781 s->tPos = s->tt[s->origPtr] >> 8; 782 s->nblock_used = 0; 783 if (s->blockRandomised) { 784 BZ_RAND_INIT_MASK; 785 BZ_GET_FAST(s->k0); s->nblock_used++; 786 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 787 } else { 788 BZ_GET_FAST(s->k0); s->nblock_used++; 789 } 790 791 } 792 793 RETURN(BZ_OK); 794 795 796 797 endhdr_2: 798 799 GET_UCHAR(BZ_X_ENDHDR_2, uc); 800 if (uc != 0x72) RETURN(BZ_DATA_ERROR); 801 GET_UCHAR(BZ_X_ENDHDR_3, uc); 802 if (uc != 0x45) RETURN(BZ_DATA_ERROR); 803 GET_UCHAR(BZ_X_ENDHDR_4, uc); 804 if (uc != 0x38) RETURN(BZ_DATA_ERROR); 805 GET_UCHAR(BZ_X_ENDHDR_5, uc); 806 if (uc != 0x50) RETURN(BZ_DATA_ERROR); 807 GET_UCHAR(BZ_X_ENDHDR_6, uc); 808 if (uc != 0x90) RETURN(BZ_DATA_ERROR); 809 810 s->storedCombinedCRC = 0; 811 GET_UCHAR(BZ_X_CCRC_1, uc); 812 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 813 GET_UCHAR(BZ_X_CCRC_2, uc); 814 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 815 GET_UCHAR(BZ_X_CCRC_3, uc); 816 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 817 GET_UCHAR(BZ_X_CCRC_4, uc); 818 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 819 820 s->state = BZ_X_IDLE; 821 RETURN(BZ_STREAM_END); 822 823 default: AssertH ( False, 4001 ); 824 } 825 826 AssertH ( False, 4002 ); 827 828 save_state_and_return: 829 830 s->save_i = i; 831 s->save_j = j; 832 s->save_t = t; 833 s->save_alphaSize = alphaSize; 834 s->save_nGroups = nGroups; 835 s->save_nSelectors = nSelectors; 836 s->save_EOB = EOB; 837 s->save_groupNo = groupNo; 838 s->save_groupPos = groupPos; 839 s->save_nextSym = nextSym; 840 s->save_nblockMAX = nblockMAX; 841 s->save_nblock = nblock; 842 s->save_es = es; 843 s->save_N = N; 844 s->save_curr = curr; 845 s->save_zt = zt; 846 s->save_zn = zn; 847 s->save_zvec = zvec; 848 s->save_zj = zj; 849 s->save_gSel = gSel; 850 s->save_gMinlen = gMinlen; 851 s->save_gLimit = gLimit; 852 s->save_gBase = gBase; 853 s->save_gPerm = gPerm; 854 855 return retVal; 856 } 857 858 859 /*-------------------------------------------------------------*/ 860 /*--- end decompress.c ---*/ 861 /*-------------------------------------------------------------*/ 862