KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > installer > CBZip2OutputStream


1 /*
2  * Copyright (C) The Apache Software Foundation. All rights reserved.
3  *
4  * This software is published under the terms of the Apache Software License
5  * version 1.1, a copy of which has been included with this distribution in
6  * the LICENSE.txt file.
7  */

8 package installer;
9
10 import java.io.IOException JavaDoc;
11 import java.io.OutputStream JavaDoc;
12
13 /**
14  * An output stream that compresses into the BZip2 format (without the file
15  * header chars) into another stream. TODO: Update to BZip2 1.0.1
16  *
17  * @author <a HREF="mailto:keiron@aftexsw.com">Keiron Liddle</a>
18  */

19 public class CBZip2OutputStream
20     extends OutputStream JavaDoc
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     /*
33      * If you are ever unlucky/improbable enough
34      * to get a stack overflow whilst sorting,
35      * increase the following constant and try
36      * again. In practice I have never seen the
37      * stack go above 27 elems, so the following
38      * limit seems very generous.
39      */

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     /*
60      * Knuth's increments seem to work better
61      * than Incerpi-Sedgewick here. Possibly
62      * because the number of elems to sort is
63      * usually small, typically <= 20.
64      */

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     /*
75      * always: in the range 0 .. 9.
76      * The current block size is 100000 * this number.
77      */

78     private int m_blockSize100k;
79     private int m_bsBuff;
80     private int m_bsLive;
81
82     /*
83      * index of the last char in the block, so
84      * the block size == last + 1.
85      */

86     private int m_last;
87
88     /*
89      * index in zptr[] of original string after sorting.
90      */

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 JavaDoc 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     /*
111      * Used when sorting. If too many long comparisons
112      * happen, we stop sorting, randomise the block
113      * slightly, and try again.
114      */

115     private int m_workFactor;
116     private int m_workLimit;
117     private int[] m_zptr;
118
119     public CBZip2OutputStream( final OutputStream JavaDoc output )
120         throws IOException JavaDoc
121     {
122         this( output, 9 );
123     }
124
125     public CBZip2OutputStream( final OutputStream JavaDoc output, final int blockSize )
126         throws IOException JavaDoc
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         /*
150          * Nodes and heap entries run from 1. Entry 0
151          * for both the heap and nodes is a sentinel.
152          */

153         int nNodes;
154         /*
155          * Nodes and heap entries run from 1. Entry 0
156          * for both the heap and nodes is a sentinel.
157          */

158         int nHeap;
159         /*
160          * Nodes and heap entries run from 1. Entry 0
161          * for both the heap and nodes is a sentinel.
162          */

163         int n1;
164         /*
165          * Nodes and heap entries run from 1. Entry 0
166          * for both the heap and nodes is a sentinel.
167          */

168         int n2;
169         /*
170          * Nodes and heap entries run from 1. Entry 0
171          * for both the heap and nodes is a sentinel.
172          */

173         int i;
174         /*
175          * Nodes and heap entries run from 1. Entry 0
176          * for both the heap and nodes is a sentinel.
177          */

178         int j;
179         /*
180          * Nodes and heap entries run from 1. Entry 0
181          * for both the heap and nodes is a sentinel.
182          */

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         //throw new CError();
363
}
364
365     public void close()
366         throws IOException JavaDoc
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 JavaDoc
387     {
388         close();
389     }
390
391     public void flush()
392         throws IOException JavaDoc
393     {
394         super.flush();
395         m_bsStream.flush();
396     }
397
398     /**
399      * modified by Oliver Merkel, 010128
400      *
401      * @param bv Description of Parameter
402      * @exception java.io.IOException Description of Exception
403      */

404     public void write( int bv )
405         throws IOException JavaDoc
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             //int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
446
//compressOutOfMemory ( totalDraw, n );
447
}
448
449         /*
450          * The back end needs a place to store the MTF values
451          * whilst it calculates the coding tables. We could
452          * put them in the zptr array. However, these values
453          * will fit in a short, so we overlay szptr at the
454          * start of zptr, in the hope of reducing the number
455          * of cache misses induced by the multiple traversals
456          * of the MTF values when calculating coding tables.
457          * Seems to improve compression speed by about 1%.
458          */

459         // szptr = zptr;
460

461         m_szptr = new short[ 2 * n ];
462     }
463
464     private void bsFinishedWithStream()
465         throws IOException JavaDoc
466     {
467         while( m_bsLive > 0 )
468         {
469             int ch = ( m_bsBuff >> 24 );
470             try
471             {
472                 m_bsStream.write( ch );// write 8-bit
473
}
474             catch( IOException JavaDoc 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 JavaDoc
485     {
486         bsW( numBits, c );
487     }
488
489     private void bsPutUChar( int c )
490         throws IOException JavaDoc
491     {
492         bsW( 8, c );
493     }
494
495     private void bsPutint( int u )
496         throws IOException JavaDoc
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 JavaDoc 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 JavaDoc
513     {
514         while( m_bsLive >= 8 )
515         {
516             int ch = ( m_bsBuff >> 24 );
517             try
518             {
519                 m_bsStream.write( ch );// write 8-bit
520
}
521             catch( IOException JavaDoc 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 JavaDoc
572     {
573         m_blockCRC = m_crc.getFinalCRC();
574         m_combinedCRC = ( m_combinedCRC << 1 ) | ( m_combinedCRC >>> 31 );
575         m_combinedCRC ^= m_blockCRC;
576
577         /*
578          * sort the block and establish posn of original string
579          */

580         doReversibleTransformation();
581
582         /*
583          * A 6-byte block header, the value chosen arbitrarily
584          * as 0x314159265359 :-). A 32 bit value does not really
585          * give a strong enough guarantee that the value will not
586          * appear by chance in the compressed datastream. Worst-case
587          * probability of this event, for a 900k block, is about
588          * 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
589          * For a compressed file of size 100Gb -- about 100000 blocks --
590          * only a 48-bit marker will do. NB: normal compression/
591          * decompression do *not* rely on these statistical properties.
592          * They are only important when trying to recover blocks from
593          * damaged files.
594          */

595         bsPutUChar( 0x31 );
596         bsPutUChar( 0x41 );
597         bsPutUChar( 0x59 );
598         bsPutUChar( 0x26 );
599         bsPutUChar( 0x53 );
600         bsPutUChar( 0x59 );
601
602         /*
603          * Now the block's CRC, so it is in a known place.
604          */

605         bsPutint( m_blockCRC );
606
607         /*
608          * Now a single bit indicating randomisation.
609          */

610         if( m_blockRandomised )
611         {
612             bsW( 1, 1 );
613         }
614         else
615         {
616             bsW( 1, 0 );
617         }
618
619         /*
620          * Finally, block's contents proper.
621          */

622         moveToFrontCodeAndSend();
623     }
624
625     private void endCompression()
626         throws IOException JavaDoc
627     {
628         /*
629          * Now another magic 48-bit number, 0x177245385090, to
630          * indicate the end of the last block. (sqrt(pi), if
631          * you want to know. I did want to use e, but it contains
632          * too much repetition -- 27 18 28 18 28 46 -- for me
633          * to feel statistically comfortable. Call me paranoid.)
634          */

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         // blockNo++;
936
m_crc.initialiseCRC();
937         m_last = -1;
938         // ch = 0;
939

940         for( int i = 0; i < 256; i++ )
941         {
942             m_inUse[ i ] = false;
943         }
944
945         /*
946          * 20 is just a paranoia constant
947          */

948         m_allowableBlockSize = BASE_BLOCK_SIZE * m_blockSize100k - 20;
949     }
950
951     private void initialize()
952         throws IOException JavaDoc
953     {
954         /*
955          * Write `magic' bytes h indicating file-format == huffmanised,
956          * followed by a digit indicating blockSize100k.
957          */

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         /*
977          * In the various block-sized structures, live data runs
978          * from 0 to last+NUM_OVERSHOOT_BYTES inclusive. First,
979          * set up the overshoot area for block.
980          */

981         // if (verbosity >= 4) fprintf ( stderr, " sort initialise ...\n" );
982
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             /*
996              * Use simpleSort(), since the full sorting mechanism
997              * has quite a large constant overhead.
998              */

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            /*
1048             * Now ftab contains the first loc of every small bucket.
1049             * Calculate the running order, from smallest to largest
1050             * big bucket.
1051             */

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            /*
1087             * The main sorting loop.
1088             */

1089            for( i = 0; i <= 255; i++ )
1090            {
1091
1092                /*
1093                 * Process big buckets, starting with the least full.
1094                 */

1095                ss = runningOrder[ i ];
1096
1097                /*
1098                 * Complete the big bucket [ss] by quicksorting
1099                 * any unsorted small buckets [ss, j]. Hopefully
1100                 * previous pointer-scanning phases have already
1101                 * completed many of the small buckets [ss, j], so
1102                 * we don't have to sort them at all.
1103                 */

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                /*
1124                 * The ss big bucket is now done. Record this fact,
1125                 * and update the quadrant descriptors. Remember to
1126                 * update quadrants in the overshoot area too, if
1127                 * necessary. The "if (i < 255)" test merely skips
1128                 * this updating for the last bucket processed, since
1129                 * updating for the last bucket is pointless.
1130                 */

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                /*
1162                 * Now scan this big bucket so as to synthesise the
1163                 * sorted order for small buckets [t, ss] for all t != ss.
1164                 */

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 JavaDoc
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            // handle 16 bit signed numbers
1411
m_block[ i + 1 ] &= 0xFF;
1412
1413            m_inUse[ m_block[ i + 1 ] ] = true;
1414        }
1415    }
1416
1417    private void sendMTFValues()
1418        throws IOException JavaDoc
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        /*
1456         * Decide how many coding tables to use
1457         */

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            /*
1485             * Generate an initial set of coding tables
1486             */

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        /*
1535         * Iterate up to N_ITERS times to improve the tables.
1536         */

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                /*
1558                 * Set group start & end marks.
1559                 */

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                /*
1571                 * Calculate the cost of this group as coded
1572                 * by each of the coding tables.
1573                 */

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                /*
1618                 * Find the coding table which is best for this group,
1619                 * and record its identity in the selector table.
1620                 */

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                /*
1637                 * Increment the symbol frequencies for the selected table.
1638                 */

1639                for( i = gs; i <= ge; i++ )
1640                {
1641                    rfreq[ bt ][ m_szptr[ i ] ]++;
1642                }
1643
1644                gs = ge + 1;
1645            }
1646
1647            /*
1648             * Recompute the tables based on the accumulated frequencies.
1649             */

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            /*
1670             * Compute MTF values for the selectors.
1671             */

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        /*
1700         * Assign actual codes for the tables.
1701         */

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            /*
1729             * Transmit the mapping table.
1730             */

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        /*
1777         * Now the selectors.
1778         */

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                    /*
1801                     * 10
1802                     */

1803                }
1804                while( curr > len[ t ][ i ] )
1805                {
1806                    bsW( 2, 3 );
1807                    curr--;
1808                    /*
1809                     * 11
1810                     */

1811                }
1812                bsW( 1, 0 );
1813            }
1814        }
1815
1816        /*
1817         * And finally, the block data proper
1818         */

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                /*
1877                 * copy 1
1878                 */

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                /*
1898                 * copy 2
1899                 */

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                /*
1919                 * copy 3
1920                 */

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 JavaDoc
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