1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * https://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19 /* 20 * This package is based on the work done by Keiron Liddle, Aftex Software 21 * <keiron@aftexsw.com> to whom the Ant project is very grateful for his 22 * great code. 23 */ 24 package org.bouncycastle.apache.bzip2; 25 26 import java.io.IOException; 27 import java.io.InputStream; 28 29 /** 30 * An input stream that decompresses from the BZip2 format (with the file 31 * header chars) to be read as any other stream. 32 * 33 * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a> 34 * 35 * <b>NB:</b> note this class has been modified to read the leading BZ from the 36 * start of the BZIP2 stream to make it compatible with other PGP programs. 37 */ 38 public class CBZip2InputStream extends InputStream implements BZip2Constants { cadvise()39 private static void cadvise() { 40 System.out.println("CRC Error"); 41 //throw new CCoruptionError(); 42 } 43 44 // private static void badBGLengths() { 45 // cadvise(); 46 // } 47 // 48 // private static void bitStreamEOF() { 49 // cadvise(); 50 // } 51 compressedStreamEOF()52 private static void compressedStreamEOF() { 53 cadvise(); 54 } 55 makeMaps()56 private void makeMaps() { 57 int i; 58 nInUse = 0; 59 for (i = 0; i < 256; i++) { 60 if (inUse[i]) { 61 seqToUnseq[nInUse] = (char) i; 62 unseqToSeq[i] = (char) nInUse; 63 nInUse++; 64 } 65 } 66 } 67 68 /* 69 index of the last char in the block, so 70 the block size == last + 1. 71 */ 72 private int last; 73 74 /* 75 index in zptr[] of original string after sorting. 76 */ 77 private int origPtr; 78 79 /* 80 always: in the range 0 .. 9. 81 The current block size is 100000 * this number. 82 */ 83 private int blockSize100k; 84 85 private boolean blockRandomised; 86 87 private int bsBuff; 88 private int bsLive; 89 private CRC mCrc = new CRC(); 90 91 private boolean[] inUse = new boolean[256]; 92 private int nInUse; 93 94 private char[] seqToUnseq = new char[256]; 95 private char[] unseqToSeq = new char[256]; 96 97 private char[] selector = new char[MAX_SELECTORS]; 98 private char[] selectorMtf = new char[MAX_SELECTORS]; 99 100 private int[] tt; 101 private char[] ll8; 102 103 /* 104 freq table collected to save a pass over the data 105 during decompression. 106 */ 107 private int[] unzftab = new int[256]; 108 109 private int[][] limit = new int[N_GROUPS][MAX_ALPHA_SIZE]; 110 private int[][] base = new int[N_GROUPS][MAX_ALPHA_SIZE]; 111 private int[][] perm = new int[N_GROUPS][MAX_ALPHA_SIZE]; 112 private int[] minLens = new int[N_GROUPS]; 113 114 private InputStream bsStream; 115 116 private boolean streamEnd = false; 117 118 private int currentChar = -1; 119 120 private static final int START_BLOCK_STATE = 1; 121 private static final int RAND_PART_A_STATE = 2; 122 private static final int RAND_PART_B_STATE = 3; 123 private static final int RAND_PART_C_STATE = 4; 124 private static final int NO_RAND_PART_A_STATE = 5; 125 private static final int NO_RAND_PART_B_STATE = 6; 126 private static final int NO_RAND_PART_C_STATE = 7; 127 128 private int currentState = START_BLOCK_STATE; 129 130 private int storedBlockCRC, storedCombinedCRC; 131 private int computedBlockCRC, computedCombinedCRC; 132 133 int i2, count, chPrev, ch2; 134 int i, tPos; 135 int rNToGo = 0; 136 int rTPos = 0; 137 int j2; 138 char z; 139 CBZip2InputStream(InputStream zStream)140 public CBZip2InputStream(InputStream zStream) 141 throws IOException 142 { 143 ll8 = null; 144 tt = null; 145 bsSetStream(zStream); 146 initialize(); 147 initBlock(); 148 setupBlock(); 149 } 150 read()151 public int read() { 152 if (streamEnd) { 153 return -1; 154 } else { 155 int retChar = currentChar; 156 switch(currentState) { 157 case START_BLOCK_STATE: 158 break; 159 case RAND_PART_A_STATE: 160 break; 161 case RAND_PART_B_STATE: 162 setupRandPartB(); 163 break; 164 case RAND_PART_C_STATE: 165 setupRandPartC(); 166 break; 167 case NO_RAND_PART_A_STATE: 168 break; 169 case NO_RAND_PART_B_STATE: 170 setupNoRandPartB(); 171 break; 172 case NO_RAND_PART_C_STATE: 173 setupNoRandPartC(); 174 break; 175 default: 176 break; 177 } 178 return retChar; 179 } 180 } 181 initialize()182 private void initialize() throws IOException { 183 char magic3, magic4; 184 magic3 = bsGetUChar(); 185 magic4 = bsGetUChar(); 186 if (magic3 != 'B' && magic4 != 'Z') 187 { 188 throw new IOException("Not a BZIP2 marked stream"); 189 } 190 magic3 = bsGetUChar(); 191 magic4 = bsGetUChar(); 192 if (magic3 != 'h' || magic4 < '1' || magic4 > '9') { 193 bsFinishedWithStream(); 194 streamEnd = true; 195 return; 196 } 197 198 setDecompressStructureSizes(magic4 - '0'); 199 computedCombinedCRC = 0; 200 } 201 initBlock()202 private void initBlock() { 203 char magic1, magic2, magic3, magic4; 204 char magic5, magic6; 205 magic1 = bsGetUChar(); 206 magic2 = bsGetUChar(); 207 magic3 = bsGetUChar(); 208 magic4 = bsGetUChar(); 209 magic5 = bsGetUChar(); 210 magic6 = bsGetUChar(); 211 if (magic1 == 0x17 && magic2 == 0x72 && magic3 == 0x45 212 && magic4 == 0x38 && magic5 == 0x50 && magic6 == 0x90) { 213 complete(); 214 return; 215 } 216 217 if (magic1 != 0x31 || magic2 != 0x41 || magic3 != 0x59 218 || magic4 != 0x26 || magic5 != 0x53 || magic6 != 0x59) { 219 badBlockHeader(); 220 streamEnd = true; 221 return; 222 } 223 224 storedBlockCRC = bsGetInt32(); 225 226 if (bsR(1) == 1) { 227 blockRandomised = true; 228 } else { 229 blockRandomised = false; 230 } 231 232 // currBlockNo++; 233 getAndMoveToFrontDecode(); 234 235 mCrc.initialiseCRC(); 236 currentState = START_BLOCK_STATE; 237 } 238 endBlock()239 private void endBlock() { 240 computedBlockCRC = mCrc.getFinalCRC(); 241 /* A bad CRC is considered a fatal error. */ 242 if (storedBlockCRC != computedBlockCRC) { 243 crcError(); 244 } 245 246 computedCombinedCRC = (computedCombinedCRC << 1) 247 | (computedCombinedCRC >>> 31); 248 computedCombinedCRC ^= computedBlockCRC; 249 } 250 complete()251 private void complete() { 252 storedCombinedCRC = bsGetInt32(); 253 if (storedCombinedCRC != computedCombinedCRC) { 254 crcError(); 255 } 256 257 bsFinishedWithStream(); 258 streamEnd = true; 259 } 260 blockOverrun()261 private static void blockOverrun() { 262 cadvise(); 263 } 264 badBlockHeader()265 private static void badBlockHeader() { 266 cadvise(); 267 } 268 crcError()269 private static void crcError() { 270 cadvise(); 271 } 272 bsFinishedWithStream()273 private void bsFinishedWithStream() { 274 try { 275 if (this.bsStream != null) { 276 if (this.bsStream != System.in) { 277 this.bsStream.close(); 278 this.bsStream = null; 279 } 280 } 281 } catch (IOException ioe) { 282 //ignore 283 } 284 } 285 bsSetStream(InputStream f)286 private void bsSetStream(InputStream f) { 287 bsStream = f; 288 bsLive = 0; 289 bsBuff = 0; 290 } 291 bsR(int n)292 private int bsR(int n) { 293 int v; 294 while (bsLive < n) { 295 int zzi; 296 char thech = 0; 297 try { 298 thech = (char) bsStream.read(); 299 } catch (IOException e) { 300 compressedStreamEOF(); 301 } 302 if (thech == -1) { 303 compressedStreamEOF(); 304 } 305 zzi = thech; 306 bsBuff = (bsBuff << 8) | (zzi & 0xff); 307 bsLive += 8; 308 } 309 310 v = (bsBuff >> (bsLive - n)) & ((1 << n) - 1); 311 bsLive -= n; 312 return v; 313 } 314 bsGetUChar()315 private char bsGetUChar() { 316 return (char) bsR(8); 317 } 318 bsGetint()319 private int bsGetint() { 320 int u = 0; 321 u = (u << 8) | bsR(8); 322 u = (u << 8) | bsR(8); 323 u = (u << 8) | bsR(8); 324 u = (u << 8) | bsR(8); 325 return u; 326 } 327 bsGetIntVS(int numBits)328 private int bsGetIntVS(int numBits) { 329 return (int) bsR(numBits); 330 } 331 bsGetInt32()332 private int bsGetInt32() { 333 return (int) bsGetint(); 334 } 335 hbCreateDecodeTables(int[] limit, int[] base, int[] perm, char[] length, int minLen, int maxLen, int alphaSize)336 private void hbCreateDecodeTables(int[] limit, int[] base, 337 int[] perm, char[] length, 338 int minLen, int maxLen, int alphaSize) { 339 int pp, i, j, vec; 340 341 pp = 0; 342 for (i = minLen; i <= maxLen; i++) { 343 for (j = 0; j < alphaSize; j++) { 344 if (length[j] == i) { 345 perm[pp] = j; 346 pp++; 347 } 348 } 349 } 350 351 for (i = 0; i < MAX_CODE_LEN; i++) { 352 base[i] = 0; 353 } 354 for (i = 0; i < alphaSize; i++) { 355 base[length[i] + 1]++; 356 } 357 358 for (i = 1; i < MAX_CODE_LEN; i++) { 359 base[i] += base[i - 1]; 360 } 361 362 for (i = 0; i < MAX_CODE_LEN; i++) { 363 limit[i] = 0; 364 } 365 vec = 0; 366 367 for (i = minLen; i <= maxLen; i++) { 368 vec += (base[i + 1] - base[i]); 369 limit[i] = vec - 1; 370 vec <<= 1; 371 } 372 for (i = minLen + 1; i <= maxLen; i++) { 373 base[i] = ((limit[i - 1] + 1) << 1) - base[i]; 374 } 375 } 376 recvDecodingTables()377 private void recvDecodingTables() { 378 char len[][] = new char[N_GROUPS][MAX_ALPHA_SIZE]; 379 int i, j, t, nGroups, nSelectors, alphaSize; 380 int minLen, maxLen; 381 boolean[] inUse16 = new boolean[16]; 382 383 /* Receive the mapping table */ 384 for (i = 0; i < 16; i++) { 385 if (bsR(1) == 1) { 386 inUse16[i] = true; 387 } else { 388 inUse16[i] = false; 389 } 390 } 391 392 for (i = 0; i < 256; i++) { 393 inUse[i] = false; 394 } 395 396 for (i = 0; i < 16; i++) { 397 if (inUse16[i]) { 398 for (j = 0; j < 16; j++) { 399 if (bsR(1) == 1) { 400 inUse[i * 16 + j] = true; 401 } 402 } 403 } 404 } 405 406 makeMaps(); 407 alphaSize = nInUse + 2; 408 409 /* Now the selectors */ 410 nGroups = bsR(3); 411 nSelectors = bsR(15); 412 for (i = 0; i < nSelectors; i++) { 413 j = 0; 414 while (bsR(1) == 1) { 415 j++; 416 } 417 selectorMtf[i] = (char) j; 418 } 419 420 /* Undo the MTF values for the selectors. */ 421 { 422 char[] pos = new char[N_GROUPS]; 423 char tmp, v; 424 for (v = 0; v < nGroups; v++) { 425 pos[v] = v; 426 } 427 428 for (i = 0; i < nSelectors; i++) { 429 v = selectorMtf[i]; 430 tmp = pos[v]; 431 while (v > 0) { 432 pos[v] = pos[v - 1]; 433 v--; 434 } 435 pos[0] = tmp; 436 selector[i] = tmp; 437 } 438 } 439 440 /* Now the coding tables */ 441 for (t = 0; t < nGroups; t++) { 442 int curr = bsR(5); 443 for (i = 0; i < alphaSize; i++) { 444 while (bsR(1) == 1) { 445 if (bsR(1) == 0) { 446 curr++; 447 } else { 448 curr--; 449 } 450 } 451 len[t][i] = (char) curr; 452 } 453 } 454 455 /* Create the Huffman decoding tables */ 456 for (t = 0; t < nGroups; t++) { 457 minLen = 32; 458 maxLen = 0; 459 for (i = 0; i < alphaSize; i++) { 460 if (len[t][i] > maxLen) { 461 maxLen = len[t][i]; 462 } 463 if (len[t][i] < minLen) { 464 minLen = len[t][i]; 465 } 466 } 467 hbCreateDecodeTables(limit[t], base[t], perm[t], len[t], minLen, 468 maxLen, alphaSize); 469 minLens[t] = minLen; 470 } 471 } 472 getAndMoveToFrontDecode()473 private void getAndMoveToFrontDecode() { 474 char[] yy = new char[256]; 475 int i, j, nextSym, limitLast; 476 int EOB, groupNo, groupPos; 477 478 limitLast = baseBlockSize * blockSize100k; 479 origPtr = bsGetIntVS(24); 480 481 recvDecodingTables(); 482 EOB = nInUse + 1; 483 groupNo = -1; 484 groupPos = 0; 485 486 /* 487 Setting up the unzftab entries here is not strictly 488 necessary, but it does save having to do it later 489 in a separate pass, and so saves a block's worth of 490 cache misses. 491 */ 492 for (i = 0; i <= 255; i++) { 493 unzftab[i] = 0; 494 } 495 496 for (i = 0; i <= 255; i++) { 497 yy[i] = (char) i; 498 } 499 500 last = -1; 501 502 { 503 int zt, zn, zvec, zj; 504 if (groupPos == 0) { 505 groupNo++; 506 groupPos = G_SIZE; 507 } 508 groupPos--; 509 zt = selector[groupNo]; 510 zn = minLens[zt]; 511 zvec = bsR(zn); 512 while (zvec > limit[zt][zn]) { 513 zn++; 514 { 515 { 516 while (bsLive < 1) { 517 int zzi; 518 char thech = 0; 519 try { 520 thech = (char) bsStream.read(); 521 } catch (IOException e) { 522 compressedStreamEOF(); 523 } 524 if (thech == -1) { 525 compressedStreamEOF(); 526 } 527 zzi = thech; 528 bsBuff = (bsBuff << 8) | (zzi & 0xff); 529 bsLive += 8; 530 } 531 } 532 zj = (bsBuff >> (bsLive - 1)) & 1; 533 bsLive--; 534 } 535 zvec = (zvec << 1) | zj; 536 } 537 nextSym = perm[zt][zvec - base[zt][zn]]; 538 } 539 540 while (true) { 541 542 if (nextSym == EOB) { 543 break; 544 } 545 546 if (nextSym == RUNA || nextSym == RUNB) { 547 char ch; 548 int s = -1; 549 int N = 1; 550 do { 551 if (nextSym == RUNA) { 552 s = s + (0 + 1) * N; 553 } else if (nextSym == RUNB) { 554 s = s + (1 + 1) * N; 555 } 556 N = N * 2; 557 { 558 int zt, zn, zvec, zj; 559 if (groupPos == 0) { 560 groupNo++; 561 groupPos = G_SIZE; 562 } 563 groupPos--; 564 zt = selector[groupNo]; 565 zn = minLens[zt]; 566 zvec = bsR(zn); 567 while (zvec > limit[zt][zn]) { 568 zn++; 569 { 570 { 571 while (bsLive < 1) { 572 int zzi; 573 char thech = 0; 574 try { 575 thech = (char) bsStream.read(); 576 } catch (IOException e) { 577 compressedStreamEOF(); 578 } 579 if (thech == -1) { 580 compressedStreamEOF(); 581 } 582 zzi = thech; 583 bsBuff = (bsBuff << 8) | (zzi & 0xff); 584 bsLive += 8; 585 } 586 } 587 zj = (bsBuff >> (bsLive - 1)) & 1; 588 bsLive--; 589 } 590 zvec = (zvec << 1) | zj; 591 } 592 nextSym = perm[zt][zvec - base[zt][zn]]; 593 } 594 } while (nextSym == RUNA || nextSym == RUNB); 595 596 s++; 597 ch = seqToUnseq[yy[0]]; 598 unzftab[ch] += s; 599 600 while (s > 0) { 601 last++; 602 ll8[last] = ch; 603 s--; 604 } 605 606 if (last >= limitLast) { 607 blockOverrun(); 608 } 609 continue; 610 } else { 611 char tmp; 612 last++; 613 if (last >= limitLast) { 614 blockOverrun(); 615 } 616 617 tmp = yy[nextSym - 1]; 618 unzftab[seqToUnseq[tmp]]++; 619 ll8[last] = seqToUnseq[tmp]; 620 621 /* 622 This loop is hammered during decompression, 623 hence the unrolling. 624 625 for (j = nextSym-1; j > 0; j--) yy[j] = yy[j-1]; 626 */ 627 628 j = nextSym - 1; 629 for (; j > 3; j -= 4) { 630 yy[j] = yy[j - 1]; 631 yy[j - 1] = yy[j - 2]; 632 yy[j - 2] = yy[j - 3]; 633 yy[j - 3] = yy[j - 4]; 634 } 635 for (; j > 0; j--) { 636 yy[j] = yy[j - 1]; 637 } 638 639 yy[0] = tmp; 640 { 641 int zt, zn, zvec, zj; 642 if (groupPos == 0) { 643 groupNo++; 644 groupPos = G_SIZE; 645 } 646 groupPos--; 647 zt = selector[groupNo]; 648 zn = minLens[zt]; 649 zvec = bsR(zn); 650 while (zvec > limit[zt][zn]) { 651 zn++; 652 { 653 { 654 while (bsLive < 1) { 655 int zzi; 656 char thech = 0; 657 try { 658 thech = (char) bsStream.read(); 659 } catch (IOException e) { 660 compressedStreamEOF(); 661 } 662 zzi = thech; 663 bsBuff = (bsBuff << 8) | (zzi & 0xff); 664 bsLive += 8; 665 } 666 } 667 zj = (bsBuff >> (bsLive - 1)) & 1; 668 bsLive--; 669 } 670 zvec = (zvec << 1) | zj; 671 } 672 nextSym = perm[zt][zvec - base[zt][zn]]; 673 } 674 continue; 675 } 676 } 677 } 678 setupBlock()679 private void setupBlock() { 680 int[] cftab = new int[257]; 681 char ch; 682 683 cftab[0] = 0; 684 for (i = 1; i <= 256; i++) { 685 cftab[i] = unzftab[i - 1]; 686 } 687 for (i = 1; i <= 256; i++) { 688 cftab[i] += cftab[i - 1]; 689 } 690 691 for (i = 0; i <= last; i++) { 692 ch = (char) ll8[i]; 693 tt[cftab[ch]] = i; 694 cftab[ch]++; 695 } 696 cftab = null; 697 698 tPos = tt[origPtr]; 699 700 count = 0; 701 i2 = 0; 702 ch2 = 256; /* not a char and not EOF */ 703 704 if (blockRandomised) { 705 rNToGo = 0; 706 rTPos = 0; 707 setupRandPartA(); 708 } else { 709 setupNoRandPartA(); 710 } 711 } 712 setupRandPartA()713 private void setupRandPartA() { 714 if (i2 <= last) { 715 chPrev = ch2; 716 ch2 = ll8[tPos]; 717 tPos = tt[tPos]; 718 if (rNToGo == 0) { 719 rNToGo = rNums[rTPos]; 720 rTPos++; 721 if (rTPos == 512) { 722 rTPos = 0; 723 } 724 } 725 rNToGo--; 726 ch2 ^= (int) ((rNToGo == 1) ? 1 : 0); 727 i2++; 728 729 currentChar = ch2; 730 currentState = RAND_PART_B_STATE; 731 mCrc.updateCRC(ch2); 732 } else { 733 endBlock(); 734 initBlock(); 735 setupBlock(); 736 } 737 } 738 setupNoRandPartA()739 private void setupNoRandPartA() { 740 if (i2 <= last) { 741 chPrev = ch2; 742 ch2 = ll8[tPos]; 743 tPos = tt[tPos]; 744 i2++; 745 746 currentChar = ch2; 747 currentState = NO_RAND_PART_B_STATE; 748 mCrc.updateCRC(ch2); 749 } else { 750 endBlock(); 751 initBlock(); 752 setupBlock(); 753 } 754 } 755 setupRandPartB()756 private void setupRandPartB() { 757 if (ch2 != chPrev) { 758 currentState = RAND_PART_A_STATE; 759 count = 1; 760 setupRandPartA(); 761 } else { 762 count++; 763 if (count >= 4) { 764 z = ll8[tPos]; 765 tPos = tt[tPos]; 766 if (rNToGo == 0) { 767 rNToGo = rNums[rTPos]; 768 rTPos++; 769 if (rTPos == 512) { 770 rTPos = 0; 771 } 772 } 773 rNToGo--; 774 z ^= ((rNToGo == 1) ? 1 : 0); 775 j2 = 0; 776 currentState = RAND_PART_C_STATE; 777 setupRandPartC(); 778 } else { 779 currentState = RAND_PART_A_STATE; 780 setupRandPartA(); 781 } 782 } 783 } 784 setupRandPartC()785 private void setupRandPartC() { 786 if (j2 < (int) z) { 787 currentChar = ch2; 788 mCrc.updateCRC(ch2); 789 j2++; 790 } else { 791 currentState = RAND_PART_A_STATE; 792 i2++; 793 count = 0; 794 setupRandPartA(); 795 } 796 } 797 setupNoRandPartB()798 private void setupNoRandPartB() { 799 if (ch2 != chPrev) { 800 currentState = NO_RAND_PART_A_STATE; 801 count = 1; 802 setupNoRandPartA(); 803 } else { 804 count++; 805 if (count >= 4) { 806 z = ll8[tPos]; 807 tPos = tt[tPos]; 808 currentState = NO_RAND_PART_C_STATE; 809 j2 = 0; 810 setupNoRandPartC(); 811 } else { 812 currentState = NO_RAND_PART_A_STATE; 813 setupNoRandPartA(); 814 } 815 } 816 } 817 setupNoRandPartC()818 private void setupNoRandPartC() { 819 if (j2 < (int) z) { 820 currentChar = ch2; 821 mCrc.updateCRC(ch2); 822 j2++; 823 } else { 824 currentState = NO_RAND_PART_A_STATE; 825 i2++; 826 count = 0; 827 setupNoRandPartA(); 828 } 829 } 830 setDecompressStructureSizes(int newSize100k)831 private void setDecompressStructureSizes(int newSize100k) { 832 if (!(0 <= newSize100k && newSize100k <= 9 && 0 <= blockSize100k 833 && blockSize100k <= 9)) { 834 // throw new IOException("Invalid block size"); 835 } 836 837 blockSize100k = newSize100k; 838 839 if (newSize100k == 0) { 840 return; 841 } 842 843 int n = baseBlockSize * newSize100k; 844 ll8 = new char[n]; 845 tt = new int[n]; 846 } 847 } 848 849