1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.vfs.provider.bzip2;
18
19 import java.io.IOException;
20 import java.io.InputStream;
21
22
23
24
25
26
27
28 /***
29 * An input stream that decompresses from the BZip2 format (without the file
30 * header chars) to be read as any other stream.
31 *
32 * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
33 */
34 class CBZip2InputStream
35 extends InputStream
36 implements BZip2Constants
37 {
38 private static final int START_BLOCK_STATE = 1;
39 private static final int RAND_PART_A_STATE = 2;
40 private static final int RAND_PART_B_STATE = 3;
41 private static final int RAND_PART_C_STATE = 4;
42 private static final int NO_RAND_PART_A_STATE = 5;
43 private static final int NO_RAND_PART_B_STATE = 6;
44 private static final int NO_RAND_PART_C_STATE = 7;
45
46 private CRC m_crc = new CRC();
47 private boolean[] m_inUse = new boolean[ 256 ];
48 private char[] m_seqToUnseq = new char[ 256 ];
49 private char[] m_unseqToSeq = new char[ 256 ];
50 private char[] m_selector = new char[ MAX_SELECTORS ];
51 private char[] m_selectorMtf = new char[ MAX_SELECTORS ];
52
53
54
55
56
57 private int[] m_unzftab = new int[ 256 ];
58
59 private int[][] m_limit = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
60 private int[][] m_base = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
61 private int[][] m_perm = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
62 private int[] m_minLens = new int[ N_GROUPS ];
63
64 private boolean m_streamEnd;
65 private int m_currentChar = -1;
66
67 private int m_currentState = START_BLOCK_STATE;
68 private int m_rNToGo;
69 private int m_rTPos;
70 private int m_tPos;
71
72 private int i2;
73 private int count;
74 private int chPrev;
75 private int ch2;
76 private int j2;
77 private char z;
78
79 private boolean m_blockRandomised;
80
81
82
83
84
85 private int m_blockSize100k;
86 private int m_bsBuff;
87 private int m_bsLive;
88
89 private InputStream m_input;
90
91 private int m_computedBlockCRC;
92 private int m_computedCombinedCRC;
93
94
95
96
97
98 private int m_last;
99 private char[] m_ll8;
100 private int m_nInUse;
101
102
103
104
105 private int m_origPtr;
106
107 private int m_storedBlockCRC;
108 private int m_storedCombinedCRC;
109 private int[] m_tt;
110
111 CBZip2InputStream( final InputStream input )
112 {
113 bsSetStream( input );
114 initialize();
115 initBlock();
116 setupBlock();
117 }
118
119 private static void badBlockHeader()
120 {
121 cadvise();
122 }
123
124 private static void blockOverrun()
125 {
126 cadvise();
127 }
128
129 private static void cadvise()
130 {
131 System.out.println( "CRC Error" );
132
133 }
134
135 private static void compressedStreamEOF()
136 {
137 cadvise();
138 }
139
140 private static void crcError()
141 {
142 cadvise();
143 }
144
145 /***
146 * a fake <code>available</code> which always returns 1 as long as the stream is not at end.
147 * This is required to make this stream work if wrapped in an BufferedInputStream.
148 *
149 * @author imario@apache.org
150 */
151 public int available() throws IOException
152 {
153 if (!m_streamEnd)
154 {
155 return 1;
156 }
157 return 0;
158 }
159
160 public int read()
161 {
162 if( m_streamEnd )
163 {
164 return -1;
165 }
166 else
167 {
168 int retChar = m_currentChar;
169 switch( m_currentState )
170 {
171 case START_BLOCK_STATE:
172 break;
173 case RAND_PART_A_STATE:
174 break;
175 case RAND_PART_B_STATE:
176 setupRandPartB();
177 break;
178 case RAND_PART_C_STATE:
179 setupRandPartC();
180 break;
181 case NO_RAND_PART_A_STATE:
182 break;
183 case NO_RAND_PART_B_STATE:
184 setupNoRandPartB();
185 break;
186 case NO_RAND_PART_C_STATE:
187 setupNoRandPartC();
188 break;
189 default:
190 break;
191 }
192 return retChar;
193 }
194 }
195
196 private void setDecompressStructureSizes( int newSize100k )
197 {
198 if( !( 0 <= newSize100k && newSize100k <= 9 && 0 <= m_blockSize100k
199 && m_blockSize100k <= 9 ) )
200 {
201
202 }
203
204 m_blockSize100k = newSize100k;
205
206 if( newSize100k == 0 )
207 {
208 return;
209 }
210
211 int n = BASE_BLOCK_SIZE * newSize100k;
212 m_ll8 = new char[ n ];
213 m_tt = new int[ n ];
214 }
215
216 private void setupBlock()
217 {
218 int[] cftab = new int[ 257 ];
219 char ch;
220
221 cftab[ 0 ] = 0;
222 for( int i = 1; i <= 256; i++ )
223 {
224 cftab[ i ] = m_unzftab[ i - 1 ];
225 }
226 for( int i = 1; i <= 256; i++ )
227 {
228 cftab[ i ] += cftab[ i - 1 ];
229 }
230
231 for( int i = 0; i <= m_last; i++ )
232 {
233 ch = m_ll8[ i ];
234 m_tt[ cftab[ ch ] ] = i;
235 cftab[ ch ]++;
236 }
237 cftab = null;
238
239 m_tPos = m_tt[ m_origPtr ];
240
241 count = 0;
242 i2 = 0;
243 ch2 = 256;
244
245
246
247 if( m_blockRandomised )
248 {
249 m_rNToGo = 0;
250 m_rTPos = 0;
251 setupRandPartA();
252 }
253 else
254 {
255 setupNoRandPartA();
256 }
257 }
258
259 private void setupNoRandPartA()
260 {
261 if( i2 <= m_last )
262 {
263 chPrev = ch2;
264 ch2 = m_ll8[ m_tPos ];
265 m_tPos = m_tt[ m_tPos ];
266 i2++;
267
268 m_currentChar = ch2;
269 m_currentState = NO_RAND_PART_B_STATE;
270 m_crc.updateCRC( ch2 );
271 }
272 else
273 {
274 endBlock();
275 initBlock();
276 setupBlock();
277 }
278 }
279
280 private void setupNoRandPartB()
281 {
282 if( ch2 != chPrev )
283 {
284 m_currentState = NO_RAND_PART_A_STATE;
285 count = 1;
286 setupNoRandPartA();
287 }
288 else
289 {
290 count++;
291 if( count >= 4 )
292 {
293 z = m_ll8[ m_tPos ];
294 m_tPos = m_tt[ m_tPos ];
295 m_currentState = NO_RAND_PART_C_STATE;
296 j2 = 0;
297 setupNoRandPartC();
298 }
299 else
300 {
301 m_currentState = NO_RAND_PART_A_STATE;
302 setupNoRandPartA();
303 }
304 }
305 }
306
307 private void setupNoRandPartC()
308 {
309 if( j2 < z )
310 {
311 m_currentChar = ch2;
312 m_crc.updateCRC( ch2 );
313 j2++;
314 }
315 else
316 {
317 m_currentState = NO_RAND_PART_A_STATE;
318 i2++;
319 count = 0;
320 setupNoRandPartA();
321 }
322 }
323
324 private void setupRandPartA()
325 {
326 if( i2 <= m_last )
327 {
328 chPrev = ch2;
329 ch2 = m_ll8[ m_tPos ];
330 m_tPos = m_tt[ m_tPos ];
331 if( m_rNToGo == 0 )
332 {
333 m_rNToGo = RAND_NUMS[ m_rTPos ];
334 m_rTPos++;
335 if( m_rTPos == 512 )
336 {
337 m_rTPos = 0;
338 }
339 }
340 m_rNToGo--;
341 ch2 ^= ( ( m_rNToGo == 1 ) ? 1 : 0 );
342 i2++;
343
344 m_currentChar = ch2;
345 m_currentState = RAND_PART_B_STATE;
346 m_crc.updateCRC( ch2 );
347 }
348 else
349 {
350 endBlock();
351 initBlock();
352 setupBlock();
353 }
354 }
355
356 private void setupRandPartB()
357 {
358 if( ch2 != chPrev )
359 {
360 m_currentState = RAND_PART_A_STATE;
361 count = 1;
362 setupRandPartA();
363 }
364 else
365 {
366 count++;
367 if( count >= 4 )
368 {
369 z = m_ll8[ m_tPos ];
370 m_tPos = m_tt[ m_tPos ];
371 if( m_rNToGo == 0 )
372 {
373 m_rNToGo = RAND_NUMS[ m_rTPos ];
374 m_rTPos++;
375 if( m_rTPos == 512 )
376 {
377 m_rTPos = 0;
378 }
379 }
380 m_rNToGo--;
381 z ^= ( ( m_rNToGo == 1 ) ? 1 : 0 );
382 j2 = 0;
383 m_currentState = RAND_PART_C_STATE;
384 setupRandPartC();
385 }
386 else
387 {
388 m_currentState = RAND_PART_A_STATE;
389 setupRandPartA();
390 }
391 }
392 }
393
394 private void setupRandPartC()
395 {
396 if( j2 < z )
397 {
398 m_currentChar = ch2;
399 m_crc.updateCRC( ch2 );
400 j2++;
401 }
402 else
403 {
404 m_currentState = RAND_PART_A_STATE;
405 i2++;
406 count = 0;
407 setupRandPartA();
408 }
409 }
410
411 private void getAndMoveToFrontDecode()
412 {
413 int nextSym;
414
415 int limitLast = BASE_BLOCK_SIZE * m_blockSize100k;
416 m_origPtr = readVariableSizedInt( 24 );
417
418 recvDecodingTables();
419 int EOB = m_nInUse + 1;
420 int groupNo = -1;
421 int groupPos = 0;
422
423
424
425
426
427
428
429 for( int i = 0; i <= 255; i++ )
430 {
431 m_unzftab[ i ] = 0;
432 }
433
434 final char[] yy = new char[ 256 ];
435 for( int i = 0; i <= 255; i++ )
436 {
437 yy[ i ] = (char)i;
438 }
439
440 m_last = -1;
441 int zt;
442 int zn;
443 int zvec;
444 int zj;
445 groupNo++;
446 groupPos = G_SIZE - 1;
447
448 zt = m_selector[ groupNo ];
449 zn = m_minLens[ zt ];
450 zvec = bsR( zn );
451 while( zvec > m_limit[ zt ][ zn ] )
452 {
453 zn++;
454
455 while( m_bsLive < 1 )
456 {
457 int zzi;
458 char thech = 0;
459 try
460 {
461 thech = (char)m_input.read();
462 }
463 catch( IOException e )
464 {
465 compressedStreamEOF();
466 }
467 if( thech == -1 )
468 {
469 compressedStreamEOF();
470 }
471 zzi = thech;
472 m_bsBuff = ( m_bsBuff << 8 ) | ( zzi & 0xff );
473 m_bsLive += 8;
474 }
475
476 zj = ( m_bsBuff >> ( m_bsLive - 1 ) ) & 1;
477 m_bsLive--;
478
479 zvec = ( zvec << 1 ) | zj;
480 }
481 nextSym = m_perm[ zt ][ zvec - m_base[ zt ][ zn ] ];
482
483 while( true )
484 {
485 if( nextSym == EOB )
486 {
487 break;
488 }
489
490 if( nextSym == RUNA || nextSym == RUNB )
491 {
492 char ch;
493 int s = -1;
494 int N = 1;
495 do
496 {
497 if( nextSym == RUNA )
498 {
499 s = s + ( 0 + 1 ) * N;
500 }
501 else
502 {
503 s = s + ( 1 + 1 ) * N;
504 }
505 N = N * 2;
506
507 if( groupPos == 0 )
508 {
509 groupNo++;
510 groupPos = G_SIZE;
511 }
512 groupPos--;
513 zt = m_selector[ groupNo ];
514 zn = m_minLens[ zt ];
515 zvec = bsR( zn );
516 while( zvec > m_limit[ zt ][ zn ] )
517 {
518 zn++;
519
520 while( m_bsLive < 1 )
521 {
522 int zzi;
523 char thech = 0;
524 try
525 {
526 thech = (char)m_input.read();
527 }
528 catch( IOException e )
529 {
530 compressedStreamEOF();
531 }
532 if( thech == -1 )
533 {
534 compressedStreamEOF();
535 }
536 zzi = thech;
537 m_bsBuff = ( m_bsBuff << 8 ) | ( zzi & 0xff );
538 m_bsLive += 8;
539 }
540
541 zj = ( m_bsBuff >> ( m_bsLive - 1 ) ) & 1;
542 m_bsLive--;
543 zvec = ( zvec << 1 ) | zj;
544 }
545
546 nextSym = m_perm[ zt ][ zvec - m_base[ zt ][ zn ] ];
547
548 } while( nextSym == RUNA || nextSym == RUNB );
549
550 s++;
551 ch = m_seqToUnseq[ yy[ 0 ] ];
552 m_unzftab[ ch ] += s;
553
554 while( s > 0 )
555 {
556 m_last++;
557 m_ll8[ m_last ] = ch;
558 s--;
559 }
560
561 if( m_last >= limitLast )
562 {
563 blockOverrun();
564 }
565 continue;
566 }
567 else
568 {
569 char tmp;
570 m_last++;
571 if( m_last >= limitLast )
572 {
573 blockOverrun();
574 }
575
576 tmp = yy[ nextSym - 1 ];
577 m_unzftab[ m_seqToUnseq[ tmp ] ]++;
578 m_ll8[ m_last ] = m_seqToUnseq[ tmp ];
579
580
581
582
583
584
585 int j = nextSym - 1;
586 for( ; j > 3; j -= 4 )
587 {
588 yy[ j ] = yy[ j - 1 ];
589 yy[ j - 1 ] = yy[ j - 2 ];
590 yy[ j - 2 ] = yy[ j - 3 ];
591 yy[ j - 3 ] = yy[ j - 4 ];
592 }
593 for( ; j > 0; j-- )
594 {
595 yy[ j ] = yy[ j - 1 ];
596 }
597
598 yy[ 0 ] = tmp;
599
600 if( groupPos == 0 )
601 {
602 groupNo++;
603 groupPos = G_SIZE;
604 }
605 groupPos--;
606 zt = m_selector[ groupNo ];
607 zn = m_minLens[ zt ];
608 zvec = bsR( zn );
609 while( zvec > m_limit[ zt ][ zn ] )
610 {
611 zn++;
612
613 while( m_bsLive < 1 )
614 {
615 char ch = 0;
616 try
617 {
618 ch = (char)m_input.read();
619 }
620 catch( IOException e )
621 {
622 compressedStreamEOF();
623 }
624
625 m_bsBuff = ( m_bsBuff << 8 ) | ( ch & 0xff );
626 m_bsLive += 8;
627 }
628
629 zj = ( m_bsBuff >> ( m_bsLive - 1 ) ) & 1;
630 m_bsLive--;
631
632 zvec = ( zvec << 1 ) | zj;
633 }
634 nextSym = m_perm[ zt ][ zvec - m_base[ zt ][ zn ] ];
635
636 continue;
637 }
638 }
639 }
640
641 private void bsFinishedWithStream()
642 {
643 if (m_input != null)
644 {
645 try
646 {
647 m_input.close();
648 }
649 catch ( IOException e )
650 {
651 }
652 }
653 m_input = null;
654 }
655
656 private int readVariableSizedInt( final int numBits )
657 {
658 return bsR( numBits );
659 }
660
661 private char readUnsignedChar()
662 {
663 return (char)bsR( 8 );
664 }
665
666 private int readInt()
667 {
668 int u = 0;
669 u = ( u << 8 ) | bsR( 8 );
670 u = ( u << 8 ) | bsR( 8 );
671 u = ( u << 8 ) | bsR( 8 );
672 u = ( u << 8 ) | bsR( 8 );
673 return u;
674 }
675
676 private int bsR( final int n )
677 {
678 while( m_bsLive < n )
679 {
680 char ch = 0;
681 try
682 {
683 ch = (char)m_input.read();
684 }
685 catch( final IOException ioe )
686 {
687 compressedStreamEOF();
688 }
689
690 if( ch == -1 )
691 {
692 compressedStreamEOF();
693 }
694
695 m_bsBuff = ( m_bsBuff << 8 ) | ( ch & 0xff );
696 m_bsLive += 8;
697 }
698
699 final int result = ( m_bsBuff >> ( m_bsLive - n ) ) & ( ( 1 << n ) - 1 );
700 m_bsLive -= n;
701 return result;
702 }
703
704 private void bsSetStream( final InputStream input )
705 {
706 m_input = input;
707 m_bsLive = 0;
708 m_bsBuff = 0;
709 }
710
711 private void complete()
712 {
713 m_storedCombinedCRC = readInt();
714 if( m_storedCombinedCRC != m_computedCombinedCRC )
715 {
716 crcError();
717 }
718
719 bsFinishedWithStream();
720 m_streamEnd = true;
721 }
722
723 private void endBlock()
724 {
725 m_computedBlockCRC = m_crc.getFinalCRC();
726
727
728
729 if( m_storedBlockCRC != m_computedBlockCRC )
730 {
731 crcError();
732 }
733
734 m_computedCombinedCRC = ( m_computedCombinedCRC << 1 )
735 | ( m_computedCombinedCRC >>> 31 );
736 m_computedCombinedCRC ^= m_computedBlockCRC;
737 }
738
739 private void hbCreateDecodeTables( final int[] limit,
740 final int[] base,
741 final int[] perm,
742 final char[] length,
743 final int minLen,
744 final int maxLen,
745 final int alphaSize )
746 {
747 int pp = 0;
748 for( int i = minLen; i <= maxLen; i++ )
749 {
750 for( int j = 0; j < alphaSize; j++ )
751 {
752 if( length[ j ] == i )
753 {
754 perm[ pp ] = j;
755 pp++;
756 }
757 }
758 }
759
760 for( int i = 0; i < MAX_CODE_LEN; i++ )
761 {
762 base[ i ] = 0;
763 }
764
765 for( int i = 0; i < alphaSize; i++ )
766 {
767 base[ length[ i ] + 1 ]++;
768 }
769
770 for( int i = 1; i < MAX_CODE_LEN; i++ )
771 {
772 base[ i ] += base[ i - 1 ];
773 }
774
775 for( int i = 0; i < MAX_CODE_LEN; i++ )
776 {
777 limit[ i ] = 0;
778 }
779
780 int vec = 0;
781 for( int i = minLen; i <= maxLen; i++ )
782 {
783 vec += ( base[ i + 1 ] - base[ i ] );
784 limit[ i ] = vec - 1;
785 vec <<= 1;
786 }
787
788 for( int i = minLen + 1; i <= maxLen; i++ )
789 {
790 base[ i ] = ( ( limit[ i - 1 ] + 1 ) << 1 ) - base[ i ];
791 }
792 }
793
794 private void initBlock()
795 {
796 final char magic1 = readUnsignedChar();
797 final char magic2 = readUnsignedChar();
798 final char magic3 = readUnsignedChar();
799 final char magic4 = readUnsignedChar();
800 final char magic5 = readUnsignedChar();
801 final char magic6 = readUnsignedChar();
802 if( magic1 == 0x17 && magic2 == 0x72 && magic3 == 0x45 &&
803 magic4 == 0x38 && magic5 == 0x50 && magic6 == 0x90 )
804 {
805 complete();
806 return;
807 }
808
809 if( magic1 != 0x31 || magic2 != 0x41 || magic3 != 0x59 ||
810 magic4 != 0x26 || magic5 != 0x53 || magic6 != 0x59 )
811 {
812 badBlockHeader();
813 m_streamEnd = true;
814 return;
815 }
816
817 m_storedBlockCRC = readInt();
818
819 if( bsR( 1 ) == 1 )
820 {
821 m_blockRandomised = true;
822 }
823 else
824 {
825 m_blockRandomised = false;
826 }
827
828
829 getAndMoveToFrontDecode();
830
831 m_crc.initialiseCRC();
832 m_currentState = START_BLOCK_STATE;
833 }
834
835 private void initialize()
836 {
837 final char magic3 = readUnsignedChar();
838 final char magic4 = readUnsignedChar();
839 if( magic3 != 'h' || magic4 < '1' || magic4 > '9' )
840 {
841 bsFinishedWithStream();
842 m_streamEnd = true;
843 return;
844 }
845
846 setDecompressStructureSizes( magic4 - '0' );
847 m_computedCombinedCRC = 0;
848 }
849
850 private void makeMaps()
851 {
852 m_nInUse = 0;
853 for( int i = 0; i < 256; i++ )
854 {
855 if( m_inUse[ i ] )
856 {
857 m_seqToUnseq[ m_nInUse ] = (char)i;
858 m_unseqToSeq[ i ] = (char)m_nInUse;
859 m_nInUse++;
860 }
861 }
862 }
863
864 private void recvDecodingTables()
865 {
866 buildInUseTable();
867 makeMaps();
868 final int alphaSize = m_nInUse + 2;
869
870
871
872
873 final int groupCount = bsR( 3 );
874 final int selectorCount = bsR( 15 );
875 for( int i = 0; i < selectorCount; i++ )
876 {
877 int run = 0;
878 while( bsR( 1 ) == 1 )
879 {
880 run++;
881 }
882 m_selectorMtf[ i ] = (char)run;
883 }
884
885
886
887
888 final char[] pos = new char[ N_GROUPS ];
889 for( char v = 0; v < groupCount; v++ )
890 {
891 pos[ v ] = v;
892 }
893
894 for( int i = 0; i < selectorCount; i++ )
895 {
896 int v = m_selectorMtf[ i ];
897 final char tmp = pos[ v ];
898 while( v > 0 )
899 {
900 pos[ v ] = pos[ v - 1 ];
901 v--;
902 }
903 pos[ 0 ] = tmp;
904 m_selector[ i ] = tmp;
905 }
906
907 final char[][] len = new char[ N_GROUPS ][ MAX_ALPHA_SIZE ];
908
909
910
911 for( int i = 0; i < groupCount; i++ )
912 {
913 int curr = bsR( 5 );
914 for( int j = 0; j < alphaSize; j++ )
915 {
916 while( bsR( 1 ) == 1 )
917 {
918 if( bsR( 1 ) == 0 )
919 {
920 curr++;
921 }
922 else
923 {
924 curr--;
925 }
926 }
927 len[ i ][ j ] = (char)curr;
928 }
929 }
930
931
932
933
934 for( int k = 0; k < groupCount; k++ )
935 {
936 int minLen = 32;
937 int maxLen = 0;
938 for( int i = 0; i < alphaSize; i++ )
939 {
940 if( len[ k ][ i ] > maxLen )
941 {
942 maxLen = len[ k ][ i ];
943 }
944 if( len[ k ][ i ] < minLen )
945 {
946 minLen = len[ k ][ i ];
947 }
948 }
949 hbCreateDecodeTables( m_limit[ k ], m_base[ k ], m_perm[ k ], len[ k ], minLen,
950 maxLen, alphaSize );
951 m_minLens[ k ] = minLen;
952 }
953 }
954
955 private void buildInUseTable()
956 {
957 final boolean[] inUse16 = new boolean[ 16 ];
958
959
960
961
962 for( int i = 0; i < 16; i++ )
963 {
964 if( bsR( 1 ) == 1 )
965 {
966 inUse16[ i ] = true;
967 }
968 else
969 {
970 inUse16[ i ] = false;
971 }
972 }
973
974 for( int i = 0; i < 256; i++ )
975 {
976 m_inUse[ i ] = false;
977 }
978
979 for( int i = 0; i < 16; i++ )
980 {
981 if( inUse16[ i ] )
982 {
983 for( int j = 0; j < 16; j++ )
984 {
985 if( bsR( 1 ) == 1 )
986 {
987 m_inUse[ i * 16 + j ] = true;
988 }
989 }
990 }
991 }
992 }
993
994 public void close() throws IOException
995 {
996 bsFinishedWithStream();
997 }
998 }