1 8 package installer; 9 10 import java.io.IOException ; 11 import java.io.OutputStream ; 12 13 19 public class CBZip2OutputStream 20 extends OutputStream 21 implements BZip2Constants 22 { 23 private static final int LOWER_BYTE_MASK = 0x000000ff; 24 private static final int UPPER_BYTE_MASK = 0xffffff00; 25 private static final int SETMASK = ( 1 << 21 ); 26 private static final int CLEARMASK = ( ~SETMASK ); 27 private static final int GREATER_ICOST = 15; 28 private static final int LESSER_ICOST = 0; 29 private static final int SMALL_THRESH = 20; 30 private static final int DEPTH_THRESH = 10; 31 32 40 private static final int QSORT_STACK_SIZE = 1000; 41 42 private CRC m_crc = new CRC(); 43 44 private boolean[] m_inUse = new boolean[ 256 ]; 45 46 private char[] m_seqToUnseq = new char[ 256 ]; 47 private char[] m_unseqToSeq = new char[ 256 ]; 48 49 private char[] m_selector = new char[ MAX_SELECTORS ]; 50 private char[] m_selectorMtf = new char[ MAX_SELECTORS ]; 51 52 private int[] m_mtfFreq = new int[ MAX_ALPHA_SIZE ]; 53 54 private int m_currentChar = -1; 55 private int m_runLength; 56 57 private boolean m_closed; 58 59 65 private int[] m_incs = new int[] 66 { 67 1, 4, 13, 40, 121, 364, 1093, 3280, 68 9841, 29524, 88573, 265720, 69 797161, 2391484 70 }; 71 72 private boolean m_blockRandomised; 73 74 78 private int m_blockSize100k; 79 private int m_bsBuff; 80 private int m_bsLive; 81 82 86 private int m_last; 87 88 91 private int m_origPtr; 92 93 private int m_allowableBlockSize; 94 95 private char[] m_block; 96 97 private int m_blockCRC; 98 private int m_combinedCRC; 99 100 private OutputStream m_bsStream; 101 private boolean m_firstAttempt; 102 private int[] m_ftab; 103 private int m_nInUse; 104 105 private int m_nMTF; 106 private int[] m_quadrant; 107 private short[] m_szptr; 108 private int m_workDone; 109 110 115 private int m_workFactor; 116 private int m_workLimit; 117 private int[] m_zptr; 118 119 public CBZip2OutputStream( final OutputStream output ) 120 throws IOException 121 { 122 this( output, 9 ); 123 } 124 125 public CBZip2OutputStream( final OutputStream output, final int blockSize ) 126 throws IOException 127 { 128 bsSetStream( output ); 129 m_workFactor = 50; 130 131 int outBlockSize = blockSize; 132 if( outBlockSize > 9 ) 133 { 134 outBlockSize = 9; 135 } 136 if( outBlockSize < 1 ) 137 { 138 outBlockSize = 1; 139 } 140 m_blockSize100k = outBlockSize; 141 allocateCompressStructures(); 142 initialize(); 143 initBlock(); 144 } 145 146 private static void hbMakeCodeLengths( char[] len, int[] freq, 147 int alphaSize, int maxLen ) 148 { 149 153 int nNodes; 154 158 int nHeap; 159 163 int n1; 164 168 int n2; 169 173 int i; 174 178 int j; 179 183 int k; 184 boolean tooLong; 185 186 int[] heap = new int[ MAX_ALPHA_SIZE + 2 ]; 187 int[] weights = new int[ MAX_ALPHA_SIZE * 2 ]; 188 int[] parent = new int[ MAX_ALPHA_SIZE * 2 ]; 189 190 for( i = 0; i < alphaSize; i++ ) 191 { 192 weights[ i + 1 ] = ( freq[ i ] == 0 ? 1 : freq[ i ] ) << 8; 193 } 194 195 while( true ) 196 { 197 nNodes = alphaSize; 198 nHeap = 0; 199 200 heap[ 0 ] = 0; 201 weights[ 0 ] = 0; 202 parent[ 0 ] = -2; 203 204 for( i = 1; i <= alphaSize; i++ ) 205 { 206 parent[ i ] = -1; 207 nHeap++; 208 heap[ nHeap ] = i; 209 { 210 int zz; 211 int tmp; 212 zz = nHeap; 213 tmp = heap[ zz ]; 214 while( weights[ tmp ] < weights[ heap[ zz >> 1 ] ] ) 215 { 216 heap[ zz ] = heap[ zz >> 1 ]; 217 zz >>= 1; 218 } 219 heap[ zz ] = tmp; 220 } 221 } 222 if( !( nHeap < ( MAX_ALPHA_SIZE + 2 ) ) ) 223 { 224 panic(); 225 } 226 227 while( nHeap > 1 ) 228 { 229 n1 = heap[ 1 ]; 230 heap[ 1 ] = heap[ nHeap ]; 231 nHeap--; 232 { 233 int zz = 0; 234 int yy = 0; 235 int tmp = 0; 236 zz = 1; 237 tmp = heap[ zz ]; 238 while( true ) 239 { 240 yy = zz << 1; 241 if( yy > nHeap ) 242 { 243 break; 244 } 245 if( yy < nHeap && 246 weights[ heap[ yy + 1 ] ] < weights[ heap[ yy ] ] ) 247 { 248 yy++; 249 } 250 if( weights[ tmp ] < weights[ heap[ yy ] ] ) 251 { 252 break; 253 } 254 heap[ zz ] = heap[ yy ]; 255 zz = yy; 256 } 257 heap[ zz ] = tmp; 258 } 259 n2 = heap[ 1 ]; 260 heap[ 1 ] = heap[ nHeap ]; 261 nHeap--; 262 { 263 int zz = 0; 264 int yy = 0; 265 int tmp = 0; 266 zz = 1; 267 tmp = heap[ zz ]; 268 while( true ) 269 { 270 yy = zz << 1; 271 if( yy > nHeap ) 272 { 273 break; 274 } 275 if( yy < nHeap && 276 weights[ heap[ yy + 1 ] ] < weights[ heap[ yy ] ] ) 277 { 278 yy++; 279 } 280 if( weights[ tmp ] < weights[ heap[ yy ] ] ) 281 { 282 break; 283 } 284 heap[ zz ] = heap[ yy ]; 285 zz = yy; 286 } 287 heap[ zz ] = tmp; 288 } 289 nNodes++; 290 parent[ n1 ] = nNodes; 291 parent[ n2 ] = nNodes; 292 293 final int v1 = weights[ n1 ]; 294 final int v2 = weights[ n2 ]; 295 final int weight = calculateWeight( v1, v2 ); 296 weights[ nNodes ] = weight; 297 298 parent[ nNodes ] = -1; 299 nHeap++; 300 heap[ nHeap ] = nNodes; 301 { 302 int zz = 0; 303 int tmp = 0; 304 zz = nHeap; 305 tmp = heap[ zz ]; 306 while( weights[ tmp ] < weights[ heap[ zz >> 1 ] ] ) 307 { 308 heap[ zz ] = heap[ zz >> 1 ]; 309 zz >>= 1; 310 } 311 heap[ zz ] = tmp; 312 } 313 } 314 if( !( nNodes < ( MAX_ALPHA_SIZE * 2 ) ) ) 315 { 316 panic(); 317 } 318 319 tooLong = false; 320 for( i = 1; i <= alphaSize; i++ ) 321 { 322 j = 0; 323 k = i; 324 while( parent[ k ] >= 0 ) 325 { 326 k = parent[ k ]; 327 j++; 328 } 329 len[ i - 1 ] = (char)j; 330 if( j > maxLen ) 331 { 332 tooLong = true; 333 } 334 } 335 336 if( !tooLong ) 337 { 338 break; 339 } 340 341 for( i = 1; i < alphaSize; i++ ) 342 { 343 j = weights[ i ] >> 8; 344 j = 1 + ( j / 2 ); 345 weights[ i ] = j << 8; 346 } 347 } 348 } 349 350 private static int calculateWeight( final int v1, final int v2 ) 351 { 352 final int upper = ( v1 & UPPER_BYTE_MASK ) + ( v2 & UPPER_BYTE_MASK ); 353 final int v1Lower = ( v1 & LOWER_BYTE_MASK ); 354 final int v2Lower = ( v2 & LOWER_BYTE_MASK ); 355 final int nnnn = ( v1Lower > v2Lower ) ? v1Lower : v2Lower; 356 return upper | ( 1 + nnnn ); 357 } 358 359 private static void panic() 360 { 361 System.out.println( "panic" ); 362 } 364 365 public void close() 366 throws IOException 367 { 368 if( m_closed ) 369 { 370 return; 371 } 372 373 if( m_runLength > 0 ) 374 { 375 writeRun(); 376 } 377 m_currentChar = -1; 378 endBlock(); 379 endCompression(); 380 m_closed = true; 381 super.close(); 382 m_bsStream.close(); 383 } 384 385 public void finalize() 386 throws Throwable 387 { 388 close(); 389 } 390 391 public void flush() 392 throws IOException 393 { 394 super.flush(); 395 m_bsStream.flush(); 396 } 397 398 404 public void write( int bv ) 405 throws IOException 406 { 407 int b = ( 256 + bv ) % 256; 408 if( m_currentChar != -1 ) 409 { 410 if( m_currentChar == b ) 411 { 412 m_runLength++; 413 if( m_runLength > 254 ) 414 { 415 writeRun(); 416 m_currentChar = -1; 417 m_runLength = 0; 418 } 419 } 420 else 421 { 422 writeRun(); 423 m_runLength = 1; 424 m_currentChar = b; 425 } 426 } 427 else 428 { 429 m_currentChar = b; 430 m_runLength++; 431 } 432 } 433 434 private void allocateCompressStructures() 435 { 436 int n = BASE_BLOCK_SIZE * m_blockSize100k; 437 m_block = new char[ ( n + 1 + NUM_OVERSHOOT_BYTES ) ]; 438 m_quadrant = new int[ ( n + NUM_OVERSHOOT_BYTES ) ]; 439 m_zptr = new int[ n ]; 440 m_ftab = new int[ 65537 ]; 441 442 if( m_block == null || m_quadrant == null || m_zptr == null 443 || m_ftab == null ) 444 { 445 } 448 449 459 461 m_szptr = new short[ 2 * n ]; 462 } 463 464 private void bsFinishedWithStream() 465 throws IOException 466 { 467 while( m_bsLive > 0 ) 468 { 469 int ch = ( m_bsBuff >> 24 ); 470 try 471 { 472 m_bsStream.write( ch ); } 474 catch( IOException e ) 475 { 476 throw e; 477 } 478 m_bsBuff <<= 8; 479 m_bsLive -= 8; 480 } 481 } 482 483 private void bsPutIntVS( int numBits, int c ) 484 throws IOException 485 { 486 bsW( numBits, c ); 487 } 488 489 private void bsPutUChar( int c ) 490 throws IOException 491 { 492 bsW( 8, c ); 493 } 494 495 private void bsPutint( int u ) 496 throws IOException 497 { 498 bsW( 8, ( u >> 24 ) & 0xff ); 499 bsW( 8, ( u >> 16 ) & 0xff ); 500 bsW( 8, ( u >> 8 ) & 0xff ); 501 bsW( 8, u & 0xff ); 502 } 503 504 private void bsSetStream( OutputStream f ) 505 { 506 m_bsStream = f; 507 m_bsLive = 0; 508 m_bsBuff = 0; 509 } 510 511 private void bsW( int n, int v ) 512 throws IOException 513 { 514 while( m_bsLive >= 8 ) 515 { 516 int ch = ( m_bsBuff >> 24 ); 517 try 518 { 519 m_bsStream.write( ch ); } 521 catch( IOException e ) 522 { 523 throw e; 524 } 525 m_bsBuff <<= 8; 526 m_bsLive -= 8; 527 } 528 m_bsBuff |= ( v << ( 32 - m_bsLive - n ) ); 529 m_bsLive += n; 530 } 531 532 private void doReversibleTransformation() 533 { 534 int i; 535 536 m_workLimit = m_workFactor * m_last; 537 m_workDone = 0; 538 m_blockRandomised = false; 539 m_firstAttempt = true; 540 541 mainSort(); 542 543 if( m_workDone > m_workLimit && m_firstAttempt ) 544 { 545 randomiseBlock(); 546 m_workLimit = 0; 547 m_workDone = 0; 548 m_blockRandomised = true; 549 m_firstAttempt = false; 550 mainSort(); 551 } 552 553 m_origPtr = -1; 554 for( i = 0; i <= m_last; i++ ) 555 { 556 if( m_zptr[ i ] == 0 ) 557 { 558 m_origPtr = i; 559 break; 560 } 561 } 562 ; 563 564 if( m_origPtr == -1 ) 565 { 566 panic(); 567 } 568 } 569 570 private void endBlock() 571 throws IOException 572 { 573 m_blockCRC = m_crc.getFinalCRC(); 574 m_combinedCRC = ( m_combinedCRC << 1 ) | ( m_combinedCRC >>> 31 ); 575 m_combinedCRC ^= m_blockCRC; 576 577 580 doReversibleTransformation(); 581 582 595 bsPutUChar( 0x31 ); 596 bsPutUChar( 0x41 ); 597 bsPutUChar( 0x59 ); 598 bsPutUChar( 0x26 ); 599 bsPutUChar( 0x53 ); 600 bsPutUChar( 0x59 ); 601 602 605 bsPutint( m_blockCRC ); 606 607 610 if( m_blockRandomised ) 611 { 612 bsW( 1, 1 ); 613 } 614 else 615 { 616 bsW( 1, 0 ); 617 } 618 619 622 moveToFrontCodeAndSend(); 623 } 624 625 private void endCompression() 626 throws IOException 627 { 628 635 bsPutUChar( 0x17 ); 636 bsPutUChar( 0x72 ); 637 bsPutUChar( 0x45 ); 638 bsPutUChar( 0x38 ); 639 bsPutUChar( 0x50 ); 640 bsPutUChar( 0x90 ); 641 642 bsPutint( m_combinedCRC ); 643 644 bsFinishedWithStream(); 645 } 646 647 private boolean fullGtU( int i1, int i2 ) 648 { 649 int k; 650 char c1; 651 char c2; 652 int s1; 653 int s2; 654 655 c1 = m_block[ i1 + 1 ]; 656 c2 = m_block[ i2 + 1 ]; 657 if( c1 != c2 ) 658 { 659 return ( c1 > c2 ); 660 } 661 i1++; 662 i2++; 663 664 c1 = m_block[ i1 + 1 ]; 665 c2 = m_block[ i2 + 1 ]; 666 if( c1 != c2 ) 667 { 668 return ( c1 > c2 ); 669 } 670 i1++; 671 i2++; 672 673 c1 = m_block[ i1 + 1 ]; 674 c2 = m_block[ i2 + 1 ]; 675 if( c1 != c2 ) 676 { 677 return ( c1 > c2 ); 678 } 679 i1++; 680 i2++; 681 682 c1 = m_block[ i1 + 1 ]; 683 c2 = m_block[ i2 + 1 ]; 684 if( c1 != c2 ) 685 { 686 return ( c1 > c2 ); 687 } 688 i1++; 689 i2++; 690 691 c1 = m_block[ i1 + 1 ]; 692 c2 = m_block[ i2 + 1 ]; 693 if( c1 != c2 ) 694 { 695 return ( c1 > c2 ); 696 } 697 i1++; 698 i2++; 699 700 c1 = m_block[ i1 + 1 ]; 701 c2 = m_block[ i2 + 1 ]; 702 if( c1 != c2 ) 703 { 704 return ( c1 > c2 ); 705 } 706 i1++; 707 i2++; 708 709 k = m_last + 1; 710 711 do 712 { 713 c1 = m_block[ i1 + 1 ]; 714 c2 = m_block[ i2 + 1 ]; 715 if( c1 != c2 ) 716 { 717 return ( c1 > c2 ); 718 } 719 s1 = m_quadrant[ i1 ]; 720 s2 = m_quadrant[ i2 ]; 721 if( s1 != s2 ) 722 { 723 return ( s1 > s2 ); 724 } 725 i1++; 726 i2++; 727 728 c1 = m_block[ i1 + 1 ]; 729 c2 = m_block[ i2 + 1 ]; 730 if( c1 != c2 ) 731 { 732 return ( c1 > c2 ); 733 } 734 s1 = m_quadrant[ i1 ]; 735 s2 = m_quadrant[ i2 ]; 736 if( s1 != s2 ) 737 { 738 return ( s1 > s2 ); 739 } 740 i1++; 741 i2++; 742 743 c1 = m_block[ i1 + 1 ]; 744 c2 = m_block[ i2 + 1 ]; 745 if( c1 != c2 ) 746 { 747 return ( c1 > c2 ); 748 } 749 s1 = m_quadrant[ i1 ]; 750 s2 = m_quadrant[ i2 ]; 751 if( s1 != s2 ) 752 { 753 return ( s1 > s2 ); 754 } 755 i1++; 756 i2++; 757 758 c1 = m_block[ i1 + 1 ]; 759 c2 = m_block[ i2 + 1 ]; 760 if( c1 != c2 ) 761 { 762 return ( c1 > c2 ); 763 } 764 s1 = m_quadrant[ i1 ]; 765 s2 = m_quadrant[ i2 ]; 766 if( s1 != s2 ) 767 { 768 return ( s1 > s2 ); 769 } 770 i1++; 771 i2++; 772 773 if( i1 > m_last ) 774 { 775 i1 -= m_last; 776 i1--; 777 } 778 ; 779 if( i2 > m_last ) 780 { 781 i2 -= m_last; 782 i2--; 783 } 784 ; 785 786 k -= 4; 787 m_workDone++; 788 } while( k >= 0 ); 789 790 return false; 791 } 792 793 private void generateMTFValues() 794 { 795 char[] yy = new char[ 256 ]; 796 int i; 797 int j; 798 char tmp; 799 char tmp2; 800 int zPend; 801 int wr; 802 int EOB; 803 804 makeMaps(); 805 EOB = m_nInUse + 1; 806 807 for( i = 0; i <= EOB; i++ ) 808 { 809 m_mtfFreq[ i ] = 0; 810 } 811 812 wr = 0; 813 zPend = 0; 814 for( i = 0; i < m_nInUse; i++ ) 815 { 816 yy[ i ] = (char)i; 817 } 818 819 for( i = 0; i <= m_last; i++ ) 820 { 821 char ll_i; 822 823 ll_i = m_unseqToSeq[ m_block[ m_zptr[ i ] ] ]; 824 825 j = 0; 826 tmp = yy[ j ]; 827 while( ll_i != tmp ) 828 { 829 j++; 830 tmp2 = tmp; 831 tmp = yy[ j ]; 832 yy[ j ] = tmp2; 833 } 834 ; 835 yy[ 0 ] = tmp; 836 837 if( j == 0 ) 838 { 839 zPend++; 840 } 841 else 842 { 843 if( zPend > 0 ) 844 { 845 zPend--; 846 while( true ) 847 { 848 switch( zPend % 2 ) 849 { 850 case 0: 851 m_szptr[ wr ] = (short)RUNA; 852 wr++; 853 m_mtfFreq[ RUNA ]++; 854 break; 855 case 1: 856 m_szptr[ wr ] = (short)RUNB; 857 wr++; 858 m_mtfFreq[ RUNB ]++; 859 break; 860 } 861 ; 862 if( zPend < 2 ) 863 { 864 break; 865 } 866 zPend = ( zPend - 2 ) / 2; 867 } 868 ; 869 zPend = 0; 870 } 871 m_szptr[ wr ] = (short)( j + 1 ); 872 wr++; 873 m_mtfFreq[ j + 1 ]++; 874 } 875 } 876 877 if( zPend > 0 ) 878 { 879 zPend--; 880 while( true ) 881 { 882 switch( zPend % 2 ) 883 { 884 case 0: 885 m_szptr[ wr ] = (short)RUNA; 886 wr++; 887 m_mtfFreq[ RUNA ]++; 888 break; 889 case 1: 890 m_szptr[ wr ] = (short)RUNB; 891 wr++; 892 m_mtfFreq[ RUNB ]++; 893 break; 894 } 895 if( zPend < 2 ) 896 { 897 break; 898 } 899 zPend = ( zPend - 2 ) / 2; 900 } 901 } 902 903 m_szptr[ wr ] = (short)EOB; 904 wr++; 905 m_mtfFreq[ EOB ]++; 906 907 m_nMTF = wr; 908 } 909 910 private void hbAssignCodes( int[] code, char[] length, int minLen, 911 int maxLen, int alphaSize ) 912 { 913 int n; 914 int vec; 915 int i; 916 917 vec = 0; 918 for( n = minLen; n <= maxLen; n++ ) 919 { 920 for( i = 0; i < alphaSize; i++ ) 921 { 922 if( length[ i ] == n ) 923 { 924 code[ i ] = vec; 925 vec++; 926 } 927 } 928 ; 929 vec <<= 1; 930 } 931 } 932 933 private void initBlock() 934 { 935 m_crc.initialiseCRC(); 937 m_last = -1; 938 940 for( int i = 0; i < 256; i++ ) 941 { 942 m_inUse[ i ] = false; 943 } 944 945 948 m_allowableBlockSize = BASE_BLOCK_SIZE * m_blockSize100k - 20; 949 } 950 951 private void initialize() 952 throws IOException 953 { 954 958 bsPutUChar( 'h' ); 959 bsPutUChar( '0' + m_blockSize100k ); 960 961 m_combinedCRC = 0; 962 } 963 964 private void mainSort() 965 { 966 int i; 967 int j; 968 int ss; 969 int sb; 970 int[] runningOrder = new int[ 256 ]; 971 int[] copy = new int[ 256 ]; 972 boolean[] bigDone = new boolean[ 256 ]; 973 int c1; 974 int c2; 975 976 981 for( i = 0; i < NUM_OVERSHOOT_BYTES; i++ ) 983 { 984 m_block[ m_last + i + 2 ] = m_block[ ( i % ( m_last + 1 ) ) + 1 ]; 985 } 986 for( i = 0; i <= m_last + NUM_OVERSHOOT_BYTES; i++ ) 987 { 988 m_quadrant[ i ] = 0; 989 } 990 991 m_block[ 0 ] = m_block[ m_last + 1 ]; 992 993 if( m_last < 4000 ) 994 { 995 999 for( i = 0; i <= m_last; i++ ) 1000 { 1001 m_zptr[ i ] = i; 1002 } 1003 m_firstAttempt = false; 1004 m_workDone = 0; 1005 m_workLimit = 0; 1006 simpleSort( 0, m_last, 0 ); 1007 } 1008 else 1009 { 1010 for( i = 0; i <= 255; i++ ) 1011 { 1012 bigDone[ i ] = false; 1013 } 1014 1015 for( i = 0; i <= 65536; i++ ) 1016 { 1017 m_ftab[ i ] = 0; 1018 } 1019 1020 c1 = m_block[ 0 ]; 1021 for( i = 0; i <= m_last; i++ ) 1022 { 1023 c2 = m_block[ i + 1 ]; 1024 m_ftab[ ( c1 << 8 ) + c2 ]++; 1025 c1 = c2; 1026 } 1027 1028 for( i = 1; i <= 65536; i++ ) 1029 { 1030 m_ftab[ i ] += m_ftab[ i - 1 ]; 1031 } 1032 1033 c1 = m_block[ 1 ]; 1034 for( i = 0; i < m_last; i++ ) 1035 { 1036 c2 = m_block[ i + 2 ]; 1037 j = ( c1 << 8 ) + c2; 1038 c1 = c2; 1039 m_ftab[ j ]--; 1040 m_zptr[ m_ftab[ j ] ] = i; 1041 } 1042 1043 j = ( ( m_block[ m_last + 1 ] ) << 8 ) + ( m_block[ 1 ] ); 1044 m_ftab[ j ]--; 1045 m_zptr[ m_ftab[ j ] ] = m_last; 1046 1047 1052 for( i = 0; i <= 255; i++ ) 1053 { 1054 runningOrder[ i ] = i; 1055 } 1056 { 1057 int vv; 1058 int h = 1; 1059 do 1060 { 1061 h = 3 * h + 1; 1062 } while( h <= 256 ); 1063 do 1064 { 1065 h = h / 3; 1066 for( i = h; i <= 255; i++ ) 1067 { 1068 vv = runningOrder[ i ]; 1069 j = i; 1070 while( ( m_ftab[ ( ( runningOrder[ j - h ] ) + 1 ) << 8 ] 1071 - m_ftab[ ( runningOrder[ j - h ] ) << 8 ] ) > 1072 ( m_ftab[ ( ( vv ) + 1 ) << 8 ] - m_ftab[ ( vv ) << 8 ] ) ) 1073 { 1074 runningOrder[ j ] = runningOrder[ j - h ]; 1075 j = j - h; 1076 if( j <= ( h - 1 ) ) 1077 { 1078 break; 1079 } 1080 } 1081 runningOrder[ j ] = vv; 1082 } 1083 } while( h != 1 ); 1084 } 1085 1086 1089 for( i = 0; i <= 255; i++ ) 1090 { 1091 1092 1095 ss = runningOrder[ i ]; 1096 1097 1104 for( j = 0; j <= 255; j++ ) 1105 { 1106 sb = ( ss << 8 ) + j; 1107 if( !( ( m_ftab[ sb ] & SETMASK ) == SETMASK ) ) 1108 { 1109 int lo = m_ftab[ sb ] & CLEARMASK; 1110 int hi = ( m_ftab[ sb + 1 ] & CLEARMASK ) - 1; 1111 if( hi > lo ) 1112 { 1113 qSort3( lo, hi, 2 ); 1114 if( m_workDone > m_workLimit && m_firstAttempt ) 1115 { 1116 return; 1117 } 1118 } 1119 m_ftab[ sb ] |= SETMASK; 1120 } 1121 } 1122 1123 1131 bigDone[ ss ] = true; 1132 1133 if( i < 255 ) 1134 { 1135 int bbStart = m_ftab[ ss << 8 ] & CLEARMASK; 1136 int bbSize = ( m_ftab[ ( ss + 1 ) << 8 ] & CLEARMASK ) - bbStart; 1137 int shifts = 0; 1138 1139 while( ( bbSize >> shifts ) > 65534 ) 1140 { 1141 shifts++; 1142 } 1143 1144 for( j = 0; j < bbSize; j++ ) 1145 { 1146 int a2update = m_zptr[ bbStart + j ]; 1147 int qVal = ( j >> shifts ); 1148 m_quadrant[ a2update ] = qVal; 1149 if( a2update < NUM_OVERSHOOT_BYTES ) 1150 { 1151 m_quadrant[ a2update + m_last + 1 ] = qVal; 1152 } 1153 } 1154 1155 if( !( ( ( bbSize - 1 ) >> shifts ) <= 65535 ) ) 1156 { 1157 panic(); 1158 } 1159 } 1160 1161 1165 for( j = 0; j <= 255; j++ ) 1166 { 1167 copy[ j ] = m_ftab[ ( j << 8 ) + ss ] & CLEARMASK; 1168 } 1169 1170 for( j = m_ftab[ ss << 8 ] & CLEARMASK; 1171 j < ( m_ftab[ ( ss + 1 ) << 8 ] & CLEARMASK ); j++ ) 1172 { 1173 c1 = m_block[ m_zptr[ j ] ]; 1174 if( !bigDone[ c1 ] ) 1175 { 1176 m_zptr[ copy[ c1 ] ] = m_zptr[ j ] == 0 ? m_last : m_zptr[ j ] - 1; 1177 copy[ c1 ]++; 1178 } 1179 } 1180 1181 for( j = 0; j <= 255; j++ ) 1182 { 1183 m_ftab[ ( j << 8 ) + ss ] |= SETMASK; 1184 } 1185 } 1186 } 1187 } 1188 1189 private void makeMaps() 1190 { 1191 int i; 1192 m_nInUse = 0; 1193 for( i = 0; i < 256; i++ ) 1194 { 1195 if( m_inUse[ i ] ) 1196 { 1197 m_seqToUnseq[ m_nInUse ] = (char)i; 1198 m_unseqToSeq[ i ] = (char)m_nInUse; 1199 m_nInUse++; 1200 } 1201 } 1202 } 1203 1204 private char med3( char a, char b, char c ) 1205 { 1206 char t; 1207 if( a > b ) 1208 { 1209 t = a; 1210 a = b; 1211 b = t; 1212 } 1213 if( b > c ) 1214 { 1215 t = b; 1216 b = c; 1217 c = t; 1218 } 1219 if( a > b ) 1220 { 1221 b = a; 1222 } 1223 return b; 1224 } 1225 1226 private void moveToFrontCodeAndSend() 1227 throws IOException 1228 { 1229 bsPutIntVS( 24, m_origPtr ); 1230 generateMTFValues(); 1231 sendMTFValues(); 1232 } 1233 1234 private void qSort3( int loSt, int hiSt, int dSt ) 1235 { 1236 int unLo; 1237 int unHi; 1238 int ltLo; 1239 int gtHi; 1240 int med; 1241 int n; 1242 int m; 1243 int sp; 1244 int lo; 1245 int hi; 1246 int d; 1247 StackElem[] stack = new StackElem[ QSORT_STACK_SIZE ]; 1248 for( int count = 0; count < QSORT_STACK_SIZE; count++ ) 1249 { 1250 stack[ count ] = new StackElem(); 1251 } 1252 1253 sp = 0; 1254 1255 stack[ sp ].m_ll = loSt; 1256 stack[ sp ].m_hh = hiSt; 1257 stack[ sp ].m_dd = dSt; 1258 sp++; 1259 1260 while( sp > 0 ) 1261 { 1262 if( sp >= QSORT_STACK_SIZE ) 1263 { 1264 panic(); 1265 } 1266 1267 sp--; 1268 lo = stack[ sp ].m_ll; 1269 hi = stack[ sp ].m_hh; 1270 d = stack[ sp ].m_dd; 1271 1272 if( hi - lo < SMALL_THRESH || d > DEPTH_THRESH ) 1273 { 1274 simpleSort( lo, hi, d ); 1275 if( m_workDone > m_workLimit && m_firstAttempt ) 1276 { 1277 return; 1278 } 1279 continue; 1280 } 1281 1282 med = med3( m_block[ m_zptr[ lo ] + d + 1 ], 1283 m_block[ m_zptr[ hi ] + d + 1 ], 1284 m_block[ m_zptr[ ( lo + hi ) >> 1 ] + d + 1 ] ); 1285 1286 unLo = lo; 1287 ltLo = lo; 1288 unHi = hi; 1289 gtHi = hi; 1290 1291 while( true ) 1292 { 1293 while( true ) 1294 { 1295 if( unLo > unHi ) 1296 { 1297 break; 1298 } 1299 n = m_block[ m_zptr[ unLo ] + d + 1 ] - med; 1300 if( n == 0 ) 1301 { 1302 int temp = 0; 1303 temp = m_zptr[ unLo ]; 1304 m_zptr[ unLo ] = m_zptr[ ltLo ]; 1305 m_zptr[ ltLo ] = temp; 1306 ltLo++; 1307 unLo++; 1308 continue; 1309 } 1310 ; 1311 if( n > 0 ) 1312 { 1313 break; 1314 } 1315 unLo++; 1316 } 1317 while( true ) 1318 { 1319 if( unLo > unHi ) 1320 { 1321 break; 1322 } 1323 n = m_block[ m_zptr[ unHi ] + d + 1 ] - med; 1324 if( n == 0 ) 1325 { 1326 int temp = 0; 1327 temp = m_zptr[ unHi ]; 1328 m_zptr[ unHi ] = m_zptr[ gtHi ]; 1329 m_zptr[ gtHi ] = temp; 1330 gtHi--; 1331 unHi--; 1332 continue; 1333 } 1334 ; 1335 if( n < 0 ) 1336 { 1337 break; 1338 } 1339 unHi--; 1340 } 1341 if( unLo > unHi ) 1342 { 1343 break; 1344 } 1345 int temp = 0; 1346 temp = m_zptr[ unLo ]; 1347 m_zptr[ unLo ] = m_zptr[ unHi ]; 1348 m_zptr[ unHi ] = temp; 1349 unLo++; 1350 unHi--; 1351 } 1352 1353 if( gtHi < ltLo ) 1354 { 1355 stack[ sp ].m_ll = lo; 1356 stack[ sp ].m_hh = hi; 1357 stack[ sp ].m_dd = d + 1; 1358 sp++; 1359 continue; 1360 } 1361 1362 n = ( ( ltLo - lo ) < ( unLo - ltLo ) ) ? ( ltLo - lo ) : ( unLo - ltLo ); 1363 vswap( lo, unLo - n, n ); 1364 m = ( ( hi - gtHi ) < ( gtHi - unHi ) ) ? ( hi - gtHi ) : ( gtHi - unHi ); 1365 vswap( unLo, hi - m + 1, m ); 1366 1367 n = lo + unLo - ltLo - 1; 1368 m = hi - ( gtHi - unHi ) + 1; 1369 1370 stack[ sp ].m_ll = lo; 1371 stack[ sp ].m_hh = n; 1372 stack[ sp ].m_dd = d; 1373 sp++; 1374 1375 stack[ sp ].m_ll = n + 1; 1376 stack[ sp ].m_hh = m - 1; 1377 stack[ sp ].m_dd = d + 1; 1378 sp++; 1379 1380 stack[ sp ].m_ll = m; 1381 stack[ sp ].m_hh = hi; 1382 stack[ sp ].m_dd = d; 1383 sp++; 1384 } 1385 } 1386 1387 private void randomiseBlock() 1388 { 1389 int i; 1390 int rNToGo = 0; 1391 int rTPos = 0; 1392 for( i = 0; i < 256; i++ ) 1393 { 1394 m_inUse[ i ] = false; 1395 } 1396 1397 for( i = 0; i <= m_last; i++ ) 1398 { 1399 if( rNToGo == 0 ) 1400 { 1401 rNToGo = (char)RAND_NUMS[ rTPos ]; 1402 rTPos++; 1403 if( rTPos == 512 ) 1404 { 1405 rTPos = 0; 1406 } 1407 } 1408 rNToGo--; 1409 m_block[ i + 1 ] ^= ( ( rNToGo == 1 ) ? 1 : 0 ); 1410 m_block[ i + 1 ] &= 0xFF; 1412 1413 m_inUse[ m_block[ i + 1 ] ] = true; 1414 } 1415 } 1416 1417 private void sendMTFValues() 1418 throws IOException 1419 { 1420 char[][] len = new char[ N_GROUPS ][ MAX_ALPHA_SIZE ]; 1421 1422 int v; 1423 1424 int t; 1425 1426 int i; 1427 1428 int j; 1429 1430 int gs; 1431 1432 int ge; 1433 1434 int bt; 1435 1436 int bc; 1437 1438 int iter; 1439 int nSelectors = 0; 1440 int alphaSize; 1441 int minLen; 1442 int maxLen; 1443 int selCtr; 1444 int nGroups; 1445 1446 alphaSize = m_nInUse + 2; 1447 for( t = 0; t < N_GROUPS; t++ ) 1448 { 1449 for( v = 0; v < alphaSize; v++ ) 1450 { 1451 len[ t ][ v ] = (char)GREATER_ICOST; 1452 } 1453 } 1454 1455 1458 if( m_nMTF <= 0 ) 1459 { 1460 panic(); 1461 } 1462 1463 if( m_nMTF < 200 ) 1464 { 1465 nGroups = 2; 1466 } 1467 else if( m_nMTF < 600 ) 1468 { 1469 nGroups = 3; 1470 } 1471 else if( m_nMTF < 1200 ) 1472 { 1473 nGroups = 4; 1474 } 1475 else if( m_nMTF < 2400 ) 1476 { 1477 nGroups = 5; 1478 } 1479 else 1480 { 1481 nGroups = 6; 1482 } 1483 { 1484 1487 int nPart; 1488 int remF; 1489 int tFreq; 1490 int aFreq; 1491 1492 nPart = nGroups; 1493 remF = m_nMTF; 1494 gs = 0; 1495 while( nPart > 0 ) 1496 { 1497 tFreq = remF / nPart; 1498 ge = gs - 1; 1499 aFreq = 0; 1500 while( aFreq < tFreq && ge < alphaSize - 1 ) 1501 { 1502 ge++; 1503 aFreq += m_mtfFreq[ ge ]; 1504 } 1505 1506 if( ge > gs && nPart != nGroups && nPart != 1 1507 && ( ( nGroups - nPart ) % 2 == 1 ) ) 1508 { 1509 aFreq -= m_mtfFreq[ ge ]; 1510 ge--; 1511 } 1512 1513 for( v = 0; v < alphaSize; v++ ) 1514 { 1515 if( v >= gs && v <= ge ) 1516 { 1517 len[ nPart - 1 ][ v ] = (char)LESSER_ICOST; 1518 } 1519 else 1520 { 1521 len[ nPart - 1 ][ v ] = (char)GREATER_ICOST; 1522 } 1523 } 1524 1525 nPart--; 1526 gs = ge + 1; 1527 remF -= aFreq; 1528 } 1529 } 1530 1531 int[][] rfreq = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ]; 1532 int[] fave = new int[ N_GROUPS ]; 1533 short[] cost = new short[ N_GROUPS ]; 1534 1537 for( iter = 0; iter < N_ITERS; iter++ ) 1538 { 1539 for( t = 0; t < nGroups; t++ ) 1540 { 1541 fave[ t ] = 0; 1542 } 1543 1544 for( t = 0; t < nGroups; t++ ) 1545 { 1546 for( v = 0; v < alphaSize; v++ ) 1547 { 1548 rfreq[ t ][ v ] = 0; 1549 } 1550 } 1551 1552 nSelectors = 0; 1553 gs = 0; 1554 while( true ) 1555 { 1556 1557 1560 if( gs >= m_nMTF ) 1561 { 1562 break; 1563 } 1564 ge = gs + G_SIZE - 1; 1565 if( ge >= m_nMTF ) 1566 { 1567 ge = m_nMTF - 1; 1568 } 1569 1570 1574 for( t = 0; t < nGroups; t++ ) 1575 { 1576 cost[ t ] = 0; 1577 } 1578 1579 if( nGroups == 6 ) 1580 { 1581 short cost0 = 0; 1582 short cost1 = 0; 1583 short cost2 = 0; 1584 short cost3 = 0; 1585 short cost4 = 0; 1586 short cost5 = 0; 1587 1588 for( i = gs; i <= ge; i++ ) 1589 { 1590 short icv = m_szptr[ i ]; 1591 cost0 += len[ 0 ][ icv ]; 1592 cost1 += len[ 1 ][ icv ]; 1593 cost2 += len[ 2 ][ icv ]; 1594 cost3 += len[ 3 ][ icv ]; 1595 cost4 += len[ 4 ][ icv ]; 1596 cost5 += len[ 5 ][ icv ]; 1597 } 1598 cost[ 0 ] = cost0; 1599 cost[ 1 ] = cost1; 1600 cost[ 2 ] = cost2; 1601 cost[ 3 ] = cost3; 1602 cost[ 4 ] = cost4; 1603 cost[ 5 ] = cost5; 1604 } 1605 else 1606 { 1607 for( i = gs; i <= ge; i++ ) 1608 { 1609 short icv = m_szptr[ i ]; 1610 for( t = 0; t < nGroups; t++ ) 1611 { 1612 cost[ t ] += len[ t ][ icv ]; 1613 } 1614 } 1615 } 1616 1617 1621 bc = 999999999; 1622 bt = -1; 1623 for( t = 0; t < nGroups; t++ ) 1624 { 1625 if( cost[ t ] < bc ) 1626 { 1627 bc = cost[ t ]; 1628 bt = t; 1629 } 1630 } 1631 ; 1632 fave[ bt ]++; 1633 m_selector[ nSelectors ] = (char)bt; 1634 nSelectors++; 1635 1636 1639 for( i = gs; i <= ge; i++ ) 1640 { 1641 rfreq[ bt ][ m_szptr[ i ] ]++; 1642 } 1643 1644 gs = ge + 1; 1645 } 1646 1647 1650 for( t = 0; t < nGroups; t++ ) 1651 { 1652 hbMakeCodeLengths( len[ t ], rfreq[ t ], alphaSize, 20 ); 1653 } 1654 } 1655 1656 rfreq = null; 1657 fave = null; 1658 cost = null; 1659 1660 if( !( nGroups < 8 ) ) 1661 { 1662 panic(); 1663 } 1664 if( !( nSelectors < 32768 && nSelectors <= ( 2 + ( 900000 / G_SIZE ) ) ) ) 1665 { 1666 panic(); 1667 } 1668 { 1669 1672 char[] pos = new char[ N_GROUPS ]; 1673 char ll_i; 1674 char tmp2; 1675 char tmp; 1676 for( i = 0; i < nGroups; i++ ) 1677 { 1678 pos[ i ] = (char)i; 1679 } 1680 for( i = 0; i < nSelectors; i++ ) 1681 { 1682 ll_i = m_selector[ i ]; 1683 j = 0; 1684 tmp = pos[ j ]; 1685 while( ll_i != tmp ) 1686 { 1687 j++; 1688 tmp2 = tmp; 1689 tmp = pos[ j ]; 1690 pos[ j ] = tmp2; 1691 } 1692 pos[ 0 ] = tmp; 1693 m_selectorMtf[ i ] = (char)j; 1694 } 1695 } 1696 1697 int[][] code = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ]; 1698 1699 1702 for( t = 0; t < nGroups; t++ ) 1703 { 1704 minLen = 32; 1705 maxLen = 0; 1706 for( i = 0; i < alphaSize; i++ ) 1707 { 1708 if( len[ t ][ i ] > maxLen ) 1709 { 1710 maxLen = len[ t ][ i ]; 1711 } 1712 if( len[ t ][ i ] < minLen ) 1713 { 1714 minLen = len[ t ][ i ]; 1715 } 1716 } 1717 if( maxLen > 20 ) 1718 { 1719 panic(); 1720 } 1721 if( minLen < 1 ) 1722 { 1723 panic(); 1724 } 1725 hbAssignCodes( code[ t ], len[ t ], minLen, maxLen, alphaSize ); 1726 } 1727 { 1728 1731 boolean[] inUse16 = new boolean[ 16 ]; 1732 for( i = 0; i < 16; i++ ) 1733 { 1734 inUse16[ i ] = false; 1735 for( j = 0; j < 16; j++ ) 1736 { 1737 if( m_inUse[ i * 16 + j ] ) 1738 { 1739 inUse16[ i ] = true; 1740 } 1741 } 1742 } 1743 1744 for( i = 0; i < 16; i++ ) 1745 { 1746 if( inUse16[ i ] ) 1747 { 1748 bsW( 1, 1 ); 1749 } 1750 else 1751 { 1752 bsW( 1, 0 ); 1753 } 1754 } 1755 1756 for( i = 0; i < 16; i++ ) 1757 { 1758 if( inUse16[ i ] ) 1759 { 1760 for( j = 0; j < 16; j++ ) 1761 { 1762 if( m_inUse[ i * 16 + j ] ) 1763 { 1764 bsW( 1, 1 ); 1765 } 1766 else 1767 { 1768 bsW( 1, 0 ); 1769 } 1770 } 1771 } 1772 } 1773 1774 } 1775 1776 1779 bsW( 3, nGroups ); 1780 bsW( 15, nSelectors ); 1781 for( i = 0; i < nSelectors; i++ ) 1782 { 1783 for( j = 0; j < m_selectorMtf[ i ]; j++ ) 1784 { 1785 bsW( 1, 1 ); 1786 } 1787 bsW( 1, 0 ); 1788 } 1789 1790 for( t = 0; t < nGroups; t++ ) 1791 { 1792 int curr = len[ t ][ 0 ]; 1793 bsW( 5, curr ); 1794 for( i = 0; i < alphaSize; i++ ) 1795 { 1796 while( curr < len[ t ][ i ] ) 1797 { 1798 bsW( 2, 2 ); 1799 curr++; 1800 1803 } 1804 while( curr > len[ t ][ i ] ) 1805 { 1806 bsW( 2, 3 ); 1807 curr--; 1808 1811 } 1812 bsW( 1, 0 ); 1813 } 1814 } 1815 1816 1819 selCtr = 0; 1820 gs = 0; 1821 while( true ) 1822 { 1823 if( gs >= m_nMTF ) 1824 { 1825 break; 1826 } 1827 ge = gs + G_SIZE - 1; 1828 if( ge >= m_nMTF ) 1829 { 1830 ge = m_nMTF - 1; 1831 } 1832 for( i = gs; i <= ge; i++ ) 1833 { 1834 bsW( len[ m_selector[ selCtr ] ][ m_szptr[ i ] ], 1835 code[ m_selector[ selCtr ] ][ m_szptr[ i ] ] ); 1836 } 1837 1838 gs = ge + 1; 1839 selCtr++; 1840 } 1841 if( !( selCtr == nSelectors ) ) 1842 { 1843 panic(); 1844 } 1845 } 1846 1847 private void simpleSort( int lo, int hi, int d ) 1848 { 1849 int i; 1850 int j; 1851 int h; 1852 int bigN; 1853 int hp; 1854 int v; 1855 1856 bigN = hi - lo + 1; 1857 if( bigN < 2 ) 1858 { 1859 return; 1860 } 1861 1862 hp = 0; 1863 while( m_incs[ hp ] < bigN ) 1864 { 1865 hp++; 1866 } 1867 hp--; 1868 1869 for( ; hp >= 0; hp-- ) 1870 { 1871 h = m_incs[ hp ]; 1872 1873 i = lo + h; 1874 while( true ) 1875 { 1876 1879 if( i > hi ) 1880 { 1881 break; 1882 } 1883 v = m_zptr[ i ]; 1884 j = i; 1885 while( fullGtU( m_zptr[ j - h ] + d, v + d ) ) 1886 { 1887 m_zptr[ j ] = m_zptr[ j - h ]; 1888 j = j - h; 1889 if( j <= ( lo + h - 1 ) ) 1890 { 1891 break; 1892 } 1893 } 1894 m_zptr[ j ] = v; 1895 i++; 1896 1897 1900 if( i > hi ) 1901 { 1902 break; 1903 } 1904 v = m_zptr[ i ]; 1905 j = i; 1906 while( fullGtU( m_zptr[ j - h ] + d, v + d ) ) 1907 { 1908 m_zptr[ j ] = m_zptr[ j - h ]; 1909 j = j - h; 1910 if( j <= ( lo + h - 1 ) ) 1911 { 1912 break; 1913 } 1914 } 1915 m_zptr[ j ] = v; 1916 i++; 1917 1918 1921 if( i > hi ) 1922 { 1923 break; 1924 } 1925 v = m_zptr[ i ]; 1926 j = i; 1927 while( fullGtU( m_zptr[ j - h ] + d, v + d ) ) 1928 { 1929 m_zptr[ j ] = m_zptr[ j - h ]; 1930 j = j - h; 1931 if( j <= ( lo + h - 1 ) ) 1932 { 1933 break; 1934 } 1935 } 1936 m_zptr[ j ] = v; 1937 i++; 1938 1939 if( m_workDone > m_workLimit && m_firstAttempt ) 1940 { 1941 return; 1942 } 1943 } 1944 } 1945 } 1946 1947 private void vswap( int p1, int p2, int n ) 1948 { 1949 int temp = 0; 1950 while( n > 0 ) 1951 { 1952 temp = m_zptr[ p1 ]; 1953 m_zptr[ p1 ] = m_zptr[ p2 ]; 1954 m_zptr[ p2 ] = temp; 1955 p1++; 1956 p2++; 1957 n--; 1958 } 1959 } 1960 1961 private void writeRun() 1962 throws IOException 1963 { 1964 if( m_last < m_allowableBlockSize ) 1965 { 1966 m_inUse[ m_currentChar ] = true; 1967 for( int i = 0; i < m_runLength; i++ ) 1968 { 1969 m_crc.updateCRC( (char)m_currentChar ); 1970 } 1971 switch( m_runLength ) 1972 { 1973 case 1: 1974 m_last++; 1975 m_block[ m_last + 1 ] = (char)m_currentChar; 1976 break; 1977 case 2: 1978 m_last++; 1979 m_block[ m_last + 1 ] = (char)m_currentChar; 1980 m_last++; 1981 m_block[ m_last + 1 ] = (char)m_currentChar; 1982 break; 1983 case 3: 1984 m_last++; 1985 m_block[ m_last + 1 ] = (char)m_currentChar; 1986 m_last++; 1987 m_block[ m_last + 1 ] = (char)m_currentChar; 1988 m_last++; 1989 m_block[ m_last + 1 ] = (char)m_currentChar; 1990 break; 1991 default: 1992 m_inUse[ m_runLength - 4 ] = true; 1993 m_last++; 1994 m_block[ m_last + 1 ] = (char)m_currentChar; 1995 m_last++; 1996 m_block[ m_last + 1 ] = (char)m_currentChar; 1997 m_last++; 1998 m_block[ m_last + 1 ] = (char)m_currentChar; 1999 m_last++; 2000 m_block[ m_last + 1 ] = (char)m_currentChar; 2001 m_last++; 2002 m_block[ m_last + 1 ] = (char)( m_runLength - 4 ); 2003 break; 2004 } 2005 } 2006 else 2007 { 2008 endBlock(); 2009 initBlock(); 2010 writeRun(); 2011 } 2012 } 2013 2014 private static class StackElem 2015 { 2016 int m_dd; 2017 int m_hh; 2018 int m_ll; 2019 } 2020} 2021 2022 | Popular Tags |