View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.vfs.provider.bzip2;
18  
19  import java.io.IOException;
20  import java.io.OutputStream;
21  
22  /*
23   * This package is based on the work done by Keiron Liddle, Aftex Software
24   * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
25   * great code.
26   */
27  
28  /***
29   * An output stream that compresses into the BZip2 format (without the file
30   * header chars) into another stream. TODO: Update to BZip2 1.0.1
31   *
32   * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
33   */
34  class CBZip2OutputStream
35      extends OutputStream
36      implements BZip2Constants
37  {
38      private static final int LOWER_BYTE_MASK = 0x000000ff;
39      private static final int UPPER_BYTE_MASK = 0xffffff00;
40      private static final int SETMASK = ( 1 << 21 );
41      private static final int CLEARMASK = ( ~SETMASK );
42      private static final int GREATER_ICOST = 15;
43      private static final int LESSER_ICOST = 0;
44      private static final int SMALL_THRESH = 20;
45      private static final int DEPTH_THRESH = 10;
46  
47      /*
48       * If you are ever unlucky/improbable enough
49       * to get a stack overflow whilst sorting,
50       * increase the following constant and try
51       * again.  In practice I have never seen the
52       * stack go above 27 elems, so the following
53       * limit seems very generous.
54       */
55      private static final int QSORT_STACK_SIZE = 1000;
56  
57      private CRC m_crc = new CRC();
58  
59      private boolean[] m_inUse = new boolean[ 256 ];
60  
61      private char[] m_seqToUnseq = new char[ 256 ];
62      private char[] m_unseqToSeq = new char[ 256 ];
63  
64      private char[] m_selector = new char[ MAX_SELECTORS ];
65      private char[] m_selectorMtf = new char[ MAX_SELECTORS ];
66  
67      private int[] m_mtfFreq = new int[ MAX_ALPHA_SIZE ];
68  
69      private int m_currentChar = -1;
70      private int m_runLength;
71  
72      private boolean m_closed;
73  
74      /*
75       * Knuth's increments seem to work better
76       * than Incerpi-Sedgewick here.  Possibly
77       * because the number of elems to sort is
78       * usually small, typically <= 20.
79       */
80      private int[] m_incs = new int[]
81      {
82          1, 4, 13, 40, 121, 364, 1093, 3280,
83          9841, 29524, 88573, 265720,
84          797161, 2391484
85      };
86  
87      private boolean m_blockRandomised;
88  
89      /*
90       * always: in the range 0 .. 9.
91       * The current block size is 100000 * this number.
92       */
93      private int m_blockSize100k;
94      private int m_bsBuff;
95      private int m_bsLive;
96  
97      /*
98       * index of the last char in the block, so
99       * the block size == last + 1.
100      */
101     private int m_last;
102 
103     /*
104      * index in zptr[] of original string after sorting.
105      */
106     private int m_origPtr;
107 
108     private int m_allowableBlockSize;
109 
110     private char[] m_block;
111 
112     private int m_blockCRC;
113     private int m_combinedCRC;
114 
115     private OutputStream m_bsStream;
116     private boolean m_firstAttempt;
117     private int[] m_ftab;
118     private int m_nInUse;
119 
120     private int m_nMTF;
121     private int[] m_quadrant;
122     private short[] m_szptr;
123     private int m_workDone;
124 
125     /*
126      * Used when sorting.  If too many long comparisons
127      * happen, we stop sorting, randomise the block
128      * slightly, and try again.
129      */
130     private int m_workFactor;
131     private int m_workLimit;
132     private int[] m_zptr;
133 
134     CBZip2OutputStream( final OutputStream output )
135         throws IOException
136     {
137         this( output, 9 );
138     }
139 
140     CBZip2OutputStream( final OutputStream output, final int blockSize )
141         throws IOException
142     {
143         bsSetStream( output );
144         m_workFactor = 50;
145 
146         int outBlockSize = blockSize;
147         if( outBlockSize > 9 )
148         {
149             outBlockSize = 9;
150         }
151         if( outBlockSize < 1 )
152         {
153             outBlockSize = 1;
154         }
155         m_blockSize100k = outBlockSize;
156         allocateCompressStructures();
157         initialize();
158         initBlock();
159     }
160 
161     private static void hbMakeCodeLengths( char[] len, int[] freq,
162                                            int alphaSize, int maxLen )
163     {
164         /*
165          * Nodes and heap entries run from 1.  Entry 0
166          * for both the heap and nodes is a sentinel.
167          */
168         int nNodes;
169         /*
170          * Nodes and heap entries run from 1.  Entry 0
171          * for both the heap and nodes is a sentinel.
172          */
173         int nHeap;
174         /*
175          * Nodes and heap entries run from 1.  Entry 0
176          * for both the heap and nodes is a sentinel.
177          */
178         int n1;
179         /*
180          * Nodes and heap entries run from 1.  Entry 0
181          * for both the heap and nodes is a sentinel.
182          */
183         int n2;
184         /*
185          * Nodes and heap entries run from 1.  Entry 0
186          * for both the heap and nodes is a sentinel.
187          */
188         int i;
189         /*
190          * Nodes and heap entries run from 1.  Entry 0
191          * for both the heap and nodes is a sentinel.
192          */
193         int j;
194         /*
195          * Nodes and heap entries run from 1.  Entry 0
196          * for both the heap and nodes is a sentinel.
197          */
198         int k;
199         boolean tooLong;
200 
201         int[] heap = new int[ MAX_ALPHA_SIZE + 2 ];
202         int[] weights = new int[ MAX_ALPHA_SIZE * 2 ];
203         int[] parent = new int[ MAX_ALPHA_SIZE * 2 ];
204 
205         for( i = 0; i < alphaSize; i++ )
206         {
207             weights[ i + 1 ] = ( freq[ i ] == 0 ? 1 : freq[ i ] ) << 8;
208         }
209 
210         while( true )
211         {
212             nNodes = alphaSize;
213             nHeap = 0;
214 
215             heap[ 0 ] = 0;
216             weights[ 0 ] = 0;
217             parent[ 0 ] = -2;
218 
219             for( i = 1; i <= alphaSize; i++ )
220             {
221                 parent[ i ] = -1;
222                 nHeap++;
223                 heap[ nHeap ] = i;
224                 {
225                     int zz;
226                     int tmp;
227                     zz = nHeap;
228                     tmp = heap[ zz ];
229                     while( weights[ tmp ] < weights[ heap[ zz >> 1 ] ] )
230                     {
231                         heap[ zz ] = heap[ zz >> 1 ];
232                         zz >>= 1;
233                     }
234                     heap[ zz ] = tmp;
235                 }
236             }
237             if( !( nHeap < ( MAX_ALPHA_SIZE + 2 ) ) )
238             {
239                 panic();
240             }
241 
242             while( nHeap > 1 )
243             {
244                 n1 = heap[ 1 ];
245                 heap[ 1 ] = heap[ nHeap ];
246                 nHeap--;
247                 {
248                     int zz = 0;
249                     int yy = 0;
250                     int tmp = 0;
251                     zz = 1;
252                     tmp = heap[ zz ];
253                     while( true )
254                     {
255                         yy = zz << 1;
256                         if( yy > nHeap )
257                         {
258                             break;
259                         }
260                         if( yy < nHeap &&
261                             weights[ heap[ yy + 1 ] ] < weights[ heap[ yy ] ] )
262                         {
263                             yy++;
264                         }
265                         if( weights[ tmp ] < weights[ heap[ yy ] ] )
266                         {
267                             break;
268                         }
269                         heap[ zz ] = heap[ yy ];
270                         zz = yy;
271                     }
272                     heap[ zz ] = tmp;
273                 }
274                 n2 = heap[ 1 ];
275                 heap[ 1 ] = heap[ nHeap ];
276                 nHeap--;
277                 {
278                     int zz = 0;
279                     int yy = 0;
280                     int tmp = 0;
281                     zz = 1;
282                     tmp = heap[ zz ];
283                     while( true )
284                     {
285                         yy = zz << 1;
286                         if( yy > nHeap )
287                         {
288                             break;
289                         }
290                         if( yy < nHeap &&
291                             weights[ heap[ yy + 1 ] ] < weights[ heap[ yy ] ] )
292                         {
293                             yy++;
294                         }
295                         if( weights[ tmp ] < weights[ heap[ yy ] ] )
296                         {
297                             break;
298                         }
299                         heap[ zz ] = heap[ yy ];
300                         zz = yy;
301                     }
302                     heap[ zz ] = tmp;
303                 }
304                 nNodes++;
305                 parent[ n1 ] = nNodes;
306                 parent[ n2 ] = nNodes;
307 
308                 final int v1 = weights[ n1 ];
309                 final int v2 = weights[ n2 ];
310                 final int weight = calculateWeight( v1, v2 );
311                 weights[ nNodes ] = weight;
312 
313                 parent[ nNodes ] = -1;
314                 nHeap++;
315                 heap[ nHeap ] = nNodes;
316                 {
317                     int zz = 0;
318                     int tmp = 0;
319                     zz = nHeap;
320                     tmp = heap[ zz ];
321                     while( weights[ tmp ] < weights[ heap[ zz >> 1 ] ] )
322                     {
323                         heap[ zz ] = heap[ zz >> 1 ];
324                         zz >>= 1;
325                     }
326                     heap[ zz ] = tmp;
327                 }
328             }
329             if( !( nNodes < ( MAX_ALPHA_SIZE * 2 ) ) )
330             {
331                 panic();
332             }
333 
334             tooLong = false;
335             for( i = 1; i <= alphaSize; i++ )
336             {
337                 j = 0;
338                 k = i;
339                 while( parent[ k ] >= 0 )
340                 {
341                     k = parent[ k ];
342                     j++;
343                 }
344                 len[ i - 1 ] = (char)j;
345                 if( j > maxLen )
346                 {
347                     tooLong = true;
348                 }
349             }
350 
351             if( !tooLong )
352             {
353                 break;
354             }
355 
356             for( i = 1; i < alphaSize; i++ )
357             {
358                 j = weights[ i ] >> 8;
359                 j = 1 + ( j / 2 );
360                 weights[ i ] = j << 8;
361             }
362         }
363     }
364 
365     private static int calculateWeight( final int v1, final int v2 )
366     {
367         final int upper = ( v1 & UPPER_BYTE_MASK ) + ( v2 & UPPER_BYTE_MASK );
368         final int v1Lower = ( v1 & LOWER_BYTE_MASK );
369         final int v2Lower = ( v2 & LOWER_BYTE_MASK );
370         final int nnnn = ( v1Lower > v2Lower ) ? v1Lower : v2Lower;
371         return upper | ( 1 + nnnn );
372     }
373 
374     private static void panic()
375     {
376         System.out.println( "panic" );
377         //throw new CError();
378     }
379 
380     public void close()
381         throws IOException
382     {
383         if( m_closed )
384         {
385             return;
386         }
387 
388         if( m_runLength > 0 )
389         {
390             writeRun();
391         }
392         m_currentChar = -1;
393         endBlock();
394         endCompression();
395         m_closed = true;
396         super.close();
397         m_bsStream.close();
398     }
399 
400     public void finalize()
401         throws Throwable
402     {
403         close();
404     }
405 
406     public void flush()
407         throws IOException
408     {
409         super.flush();
410         m_bsStream.flush();
411     }
412 
413     /***
414      * modified by Oliver Merkel, 010128
415      *
416      * @param bv Description of Parameter
417      * @exception java.io.IOException Description of Exception
418      */
419     public void write( int bv )
420         throws IOException
421     {
422         int b = ( 256 + bv ) % 256;
423         if( m_currentChar != -1 )
424         {
425             if( m_currentChar == b )
426             {
427                 m_runLength++;
428                 if( m_runLength > 254 )
429                 {
430                     writeRun();
431                     m_currentChar = -1;
432                     m_runLength = 0;
433                 }
434             }
435             else
436             {
437                 writeRun();
438                 m_runLength = 1;
439                 m_currentChar = b;
440             }
441         }
442         else
443         {
444             m_currentChar = b;
445             m_runLength++;
446         }
447     }
448 
449     private void allocateCompressStructures()
450     {
451         int n = BASE_BLOCK_SIZE * m_blockSize100k;
452         m_block = new char[ ( n + 1 + NUM_OVERSHOOT_BYTES ) ];
453         m_quadrant = new int[ ( n + NUM_OVERSHOOT_BYTES ) ];
454         m_zptr = new int[ n ];
455         m_ftab = new int[ 65537 ];
456 
457         if( m_block == null || m_quadrant == null || m_zptr == null
458             || m_ftab == null )
459         {
460             //int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
461             //compressOutOfMemory ( totalDraw, n );
462         }
463 
464         /*
465          * The back end needs a place to store the MTF values
466          * whilst it calculates the coding tables.  We could
467          * put them in the zptr array.  However, these values
468          * will fit in a short, so we overlay szptr at the
469          * start of zptr, in the hope of reducing the number
470          * of cache misses induced by the multiple traversals
471          * of the MTF values when calculating coding tables.
472          * Seems to improve compression speed by about 1%.
473          */
474         //    szptr = zptr;
475 
476         m_szptr = new short[ 2 * n ];
477     }
478 
479     private void bsFinishedWithStream()
480         throws IOException
481     {
482         while( m_bsLive > 0 )
483         {
484             int ch = ( m_bsBuff >> 24 );
485             try
486             {
487                 m_bsStream.write( ch );// write 8-bit
488             }
489             catch( IOException e )
490             {
491                 throw e;
492             }
493             m_bsBuff <<= 8;
494             m_bsLive -= 8;
495         }
496     }
497 
498     private void bsPutIntVS( int numBits, int c )
499         throws IOException
500     {
501         bsW( numBits, c );
502     }
503 
504     private void bsPutUChar( int c )
505         throws IOException
506     {
507         bsW( 8, c );
508     }
509 
510     private void bsPutint( int u )
511         throws IOException
512     {
513         bsW( 8, ( u >> 24 ) & 0xff );
514         bsW( 8, ( u >> 16 ) & 0xff );
515         bsW( 8, ( u >> 8 ) & 0xff );
516         bsW( 8, u & 0xff );
517     }
518 
519     private void bsSetStream( OutputStream f )
520     {
521         m_bsStream = f;
522         m_bsLive = 0;
523         m_bsBuff = 0;
524     }
525 
526     private void bsW( int n, int v )
527         throws IOException
528     {
529         while( m_bsLive >= 8 )
530         {
531             int ch = ( m_bsBuff >> 24 );
532             try
533             {
534                 m_bsStream.write( ch );// write 8-bit
535             }
536             catch( IOException e )
537             {
538                 throw e;
539             }
540             m_bsBuff <<= 8;
541             m_bsLive -= 8;
542         }
543         m_bsBuff |= ( v << ( 32 - m_bsLive - n ) );
544         m_bsLive += n;
545     }
546 
547     private void doReversibleTransformation()
548     {
549         int i;
550 
551         m_workLimit = m_workFactor * m_last;
552         m_workDone = 0;
553         m_blockRandomised = false;
554         m_firstAttempt = true;
555 
556         mainSort();
557 
558         if( m_workDone > m_workLimit && m_firstAttempt )
559         {
560             randomiseBlock();
561             m_workLimit = 0;
562             m_workDone = 0;
563             m_blockRandomised = true;
564             m_firstAttempt = false;
565             mainSort();
566         }
567 
568         m_origPtr = -1;
569         for( i = 0; i <= m_last; i++ )
570         {
571             if( m_zptr[ i ] == 0 )
572             {
573                 m_origPtr = i;
574                 break;
575             }
576         }
577         ;
578 
579         if( m_origPtr == -1 )
580         {
581             panic();
582         }
583     }
584 
585     private void endBlock()
586         throws IOException
587     {
588         m_blockCRC = m_crc.getFinalCRC();
589         m_combinedCRC = ( m_combinedCRC << 1 ) | ( m_combinedCRC >>> 31 );
590         m_combinedCRC ^= m_blockCRC;
591 
592         /*
593          * sort the block and establish posn of original string
594          */
595         doReversibleTransformation();
596 
597         /*
598          * A 6-byte block header, the value chosen arbitrarily
599          * as 0x314159265359 :-).  A 32 bit value does not really
600          * give a strong enough guarantee that the value will not
601          * appear by chance in the compressed datastream.  Worst-case
602          * probability of this event, for a 900k block, is about
603          * 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
604          * For a compressed file of size 100Gb -- about 100000 blocks --
605          * only a 48-bit marker will do.  NB: normal compression/
606          * decompression do *not* rely on these statistical properties.
607          * They are only important when trying to recover blocks from
608          * damaged files.
609          */
610         bsPutUChar( 0x31 );
611         bsPutUChar( 0x41 );
612         bsPutUChar( 0x59 );
613         bsPutUChar( 0x26 );
614         bsPutUChar( 0x53 );
615         bsPutUChar( 0x59 );
616 
617         /*
618          * Now the block's CRC, so it is in a known place.
619          */
620         bsPutint( m_blockCRC );
621 
622         /*
623          * Now a single bit indicating randomisation.
624          */
625         if( m_blockRandomised )
626         {
627             bsW( 1, 1 );
628         }
629         else
630         {
631             bsW( 1, 0 );
632         }
633 
634         /*
635          * Finally, block's contents proper.
636          */
637         moveToFrontCodeAndSend();
638     }
639 
640     private void endCompression()
641         throws IOException
642     {
643         /*
644          * Now another magic 48-bit number, 0x177245385090, to
645          * indicate the end of the last block.  (sqrt(pi), if
646          * you want to know.  I did want to use e, but it contains
647          * too much repetition -- 27 18 28 18 28 46 -- for me
648          * to feel statistically comfortable.  Call me paranoid.)
649          */
650         bsPutUChar( 0x17 );
651         bsPutUChar( 0x72 );
652         bsPutUChar( 0x45 );
653         bsPutUChar( 0x38 );
654         bsPutUChar( 0x50 );
655         bsPutUChar( 0x90 );
656 
657         bsPutint( m_combinedCRC );
658 
659         bsFinishedWithStream();
660     }
661 
662     private boolean fullGtU( int i1, int i2 )
663     {
664         int k;
665         char c1;
666         char c2;
667         int s1;
668         int s2;
669 
670         c1 = m_block[ i1 + 1 ];
671         c2 = m_block[ i2 + 1 ];
672         if( c1 != c2 )
673         {
674             return ( c1 > c2 );
675         }
676         i1++;
677         i2++;
678 
679         c1 = m_block[ i1 + 1 ];
680         c2 = m_block[ i2 + 1 ];
681         if( c1 != c2 )
682         {
683             return ( c1 > c2 );
684         }
685         i1++;
686         i2++;
687 
688         c1 = m_block[ i1 + 1 ];
689         c2 = m_block[ i2 + 1 ];
690         if( c1 != c2 )
691         {
692             return ( c1 > c2 );
693         }
694         i1++;
695         i2++;
696 
697         c1 = m_block[ i1 + 1 ];
698         c2 = m_block[ i2 + 1 ];
699         if( c1 != c2 )
700         {
701             return ( c1 > c2 );
702         }
703         i1++;
704         i2++;
705 
706         c1 = m_block[ i1 + 1 ];
707         c2 = m_block[ i2 + 1 ];
708         if( c1 != c2 )
709         {
710             return ( c1 > c2 );
711         }
712         i1++;
713         i2++;
714 
715         c1 = m_block[ i1 + 1 ];
716         c2 = m_block[ i2 + 1 ];
717         if( c1 != c2 )
718         {
719             return ( c1 > c2 );
720         }
721         i1++;
722         i2++;
723 
724         k = m_last + 1;
725 
726         do
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             c1 = m_block[ i1 + 1 ];
774             c2 = m_block[ i2 + 1 ];
775             if( c1 != c2 )
776             {
777                 return ( c1 > c2 );
778             }
779             s1 = m_quadrant[ i1 ];
780             s2 = m_quadrant[ i2 ];
781             if( s1 != s2 )
782             {
783                 return ( s1 > s2 );
784             }
785             i1++;
786             i2++;
787 
788             if( i1 > m_last )
789             {
790                 i1 -= m_last;
791                 i1--;
792             }
793             ;
794             if( i2 > m_last )
795             {
796                 i2 -= m_last;
797                 i2--;
798             }
799             ;
800 
801             k -= 4;
802             m_workDone++;
803         } while( k >= 0 );
804 
805         return false;
806     }
807 
808     private void generateMTFValues()
809     {
810         char[] yy = new char[ 256 ];
811         int i;
812         int j;
813         char tmp;
814         char tmp2;
815         int zPend;
816         int wr;
817         int EOB;
818 
819         makeMaps();
820         EOB = m_nInUse + 1;
821 
822         for( i = 0; i <= EOB; i++ )
823         {
824             m_mtfFreq[ i ] = 0;
825         }
826 
827         wr = 0;
828         zPend = 0;
829         for( i = 0; i < m_nInUse; i++ )
830         {
831             yy[ i ] = (char)i;
832         }
833 
834         for( i = 0; i <= m_last; i++ )
835         {
836             char ll_i;
837 
838             ll_i = m_unseqToSeq[ m_block[ m_zptr[ i ] ] ];
839 
840             j = 0;
841             tmp = yy[ j ];
842             while( ll_i != tmp )
843             {
844                 j++;
845                 tmp2 = tmp;
846                 tmp = yy[ j ];
847                 yy[ j ] = tmp2;
848             }
849             ;
850             yy[ 0 ] = tmp;
851 
852             if( j == 0 )
853             {
854                 zPend++;
855             }
856             else
857             {
858                 if( zPend > 0 )
859                 {
860                     zPend--;
861                     while( true )
862                     {
863                         switch( zPend % 2 )
864                         {
865                             case 0:
866                                 m_szptr[ wr ] = (short)RUNA;
867                                 wr++;
868                                 m_mtfFreq[ RUNA ]++;
869                                 break;
870                             case 1:
871                                 m_szptr[ wr ] = (short)RUNB;
872                                 wr++;
873                                 m_mtfFreq[ RUNB ]++;
874                                 break;
875                         }
876                         ;
877                         if( zPend < 2 )
878                         {
879                             break;
880                         }
881                         zPend = ( zPend - 2 ) / 2;
882                     }
883                     ;
884                     zPend = 0;
885                 }
886                 m_szptr[ wr ] = (short)( j + 1 );
887                 wr++;
888                 m_mtfFreq[ j + 1 ]++;
889             }
890         }
891 
892         if( zPend > 0 )
893         {
894             zPend--;
895             while( true )
896             {
897                 switch( zPend % 2 )
898                 {
899                     case 0:
900                         m_szptr[ wr ] = (short)RUNA;
901                         wr++;
902                         m_mtfFreq[ RUNA ]++;
903                         break;
904                     case 1:
905                         m_szptr[ wr ] = (short)RUNB;
906                         wr++;
907                         m_mtfFreq[ RUNB ]++;
908                         break;
909                 }
910                 if( zPend < 2 )
911                 {
912                     break;
913                 }
914                 zPend = ( zPend - 2 ) / 2;
915             }
916         }
917 
918         m_szptr[ wr ] = (short)EOB;
919         wr++;
920         m_mtfFreq[ EOB ]++;
921 
922         m_nMTF = wr;
923     }
924 
925     private void hbAssignCodes( int[] code, char[] length, int minLen,
926                                 int maxLen, int alphaSize )
927     {
928         int n;
929         int vec;
930         int i;
931 
932         vec = 0;
933         for( n = minLen; n <= maxLen; n++ )
934         {
935             for( i = 0; i < alphaSize; i++ )
936             {
937                 if( length[ i ] == n )
938                 {
939                     code[ i ] = vec;
940                     vec++;
941                 }
942             }
943             ;
944             vec <<= 1;
945         }
946     }
947 
948     private void initBlock()
949     {
950         //        blockNo++;
951         m_crc.initialiseCRC();
952         m_last = -1;
953         //        ch = 0;
954 
955         for( int i = 0; i < 256; i++ )
956         {
957             m_inUse[ i ] = false;
958         }
959 
960         /*
961          * 20 is just a paranoia constant
962          */
963         m_allowableBlockSize = BASE_BLOCK_SIZE * m_blockSize100k - 20;
964     }
965 
966     private void initialize()
967         throws IOException
968     {
969         /*
970          * Write `magic' bytes h indicating file-format == huffmanised,
971          * followed by a digit indicating blockSize100k.
972          */
973         bsPutUChar( 'h' );
974         bsPutUChar( '0' + m_blockSize100k );
975 
976         m_combinedCRC = 0;
977     }
978 
979     private void mainSort()
980     {
981         int i;
982         int j;
983         int ss;
984         int sb;
985         int[] runningOrder = new int[ 256 ];
986         int[] copy = new int[ 256 ];
987         boolean[] bigDone = new boolean[ 256 ];
988         int c1;
989         int c2;
990 
991         /*
992          * In the various block-sized structures, live data runs
993          * from 0 to last+NUM_OVERSHOOT_BYTES inclusive.  First,
994          * set up the overshoot area for block.
995          */
996         //   if (verbosity >= 4) fprintf ( stderr, "        sort initialise ...\n" );
997         for( i = 0; i < NUM_OVERSHOOT_BYTES; i++ )
998         {
999             m_block[ m_last + i + 2 ] = m_block[ ( i % ( m_last + 1 ) ) + 1 ];
1000         }
1001         for( i = 0; i <= m_last + NUM_OVERSHOOT_BYTES; i++ )
1002         {
1003             m_quadrant[ i ] = 0;
1004         }
1005 
1006         m_block[ 0 ] = m_block[ m_last + 1 ];
1007 
1008         if( m_last < 4000 )
1009         {
1010             /*
1011              * Use simpleSort(), since the full sorting mechanism
1012              * has quite a large constant overhead.
1013              */
1014             for( i = 0; i <= m_last; i++ )
1015             {
1016                 m_zptr[ i ] = i;
1017             }
1018             m_firstAttempt = false;
1019             m_workDone = 0;
1020             m_workLimit = 0;
1021             simpleSort( 0, m_last, 0 );
1022         }
1023         else
1024         {
1025             for( i = 0; i <= 255; i++ )
1026             {
1027                 bigDone[ i ] = false;
1028             }
1029 
1030             for( i = 0; i <= 65536; i++ )
1031             {
1032                 m_ftab[ i ] = 0;
1033             }
1034 
1035             c1 = m_block[ 0 ];
1036             for( i = 0; i <= m_last; i++ )
1037             {
1038                 c2 = m_block[ i + 1 ];
1039                 m_ftab[ ( c1 << 8 ) + c2 ]++;
1040                 c1 = c2;
1041             }
1042 
1043             for( i = 1; i <= 65536; i++ )
1044             {
1045                 m_ftab[ i ] += m_ftab[ i - 1 ];
1046             }
1047 
1048             c1 = m_block[ 1 ];
1049             for( i = 0; i < m_last; i++ )
1050             {
1051                 c2 = m_block[ i + 2 ];
1052                 j = ( c1 << 8 ) + c2;
1053                 c1 = c2;
1054                 m_ftab[ j ]--;
1055                 m_zptr[ m_ftab[ j ] ] = i;
1056             }
1057 
1058             j = ( ( m_block[ m_last + 1 ] ) << 8 ) + ( m_block[ 1 ] );
1059             m_ftab[ j ]--;
1060             m_zptr[ m_ftab[ j ] ] = m_last;
1061 
1062             /*
1063              * Now ftab contains the first loc of every small bucket.
1064              * Calculate the running order, from smallest to largest
1065              * big bucket.
1066              */
1067             for( i = 0; i <= 255; i++ )
1068             {
1069                 runningOrder[ i ] = i;
1070             }
1071             {
1072                 int vv;
1073                 int h = 1;
1074                 do
1075                 {
1076                     h = 3 * h + 1;
1077                 } while( h <= 256 );
1078                 do
1079                 {
1080                     h = h / 3;
1081                     for( i = h; i <= 255; i++ )
1082                     {
1083                         vv = runningOrder[ i ];
1084                         j = i;
1085                         while( ( m_ftab[ ( ( runningOrder[ j - h ] ) + 1 ) << 8 ]
1086                             - m_ftab[ ( runningOrder[ j - h ] ) << 8 ] ) >
1087                             ( m_ftab[ ( ( vv ) + 1 ) << 8 ] - m_ftab[ ( vv ) << 8 ] ) )
1088                         {
1089                             runningOrder[ j ] = runningOrder[ j - h ];
1090                             j = j - h;
1091                             if( j <= ( h - 1 ) )
1092                             {
1093                                 break;
1094                             }
1095                         }
1096                         runningOrder[ j ] = vv;
1097                     }
1098                 } while( h != 1 );
1099             }
1100 
1101             /*
1102              * The main sorting loop.
1103              */
1104             for( i = 0; i <= 255; i++ )
1105             {
1106 
1107                 /*
1108                  * Process big buckets, starting with the least full.
1109                  */
1110                 ss = runningOrder[ i ];
1111 
1112                 /*
1113                  * Complete the big bucket [ss] by quicksorting
1114                  * any unsorted small buckets [ss, j].  Hopefully
1115                  * previous pointer-scanning phases have already
1116                  * completed many of the small buckets [ss, j], so
1117                  * we don't have to sort them at all.
1118                  */
1119                 for( j = 0; j <= 255; j++ )
1120                 {
1121                     sb = ( ss << 8 ) + j;
1122                     if( !( ( m_ftab[ sb ] & SETMASK ) == SETMASK ) )
1123                     {
1124                         int lo = m_ftab[ sb ] & CLEARMASK;
1125                         int hi = ( m_ftab[ sb + 1 ] & CLEARMASK ) - 1;
1126                         if( hi > lo )
1127                         {
1128                             qSort3( lo, hi, 2 );
1129                             if( m_workDone > m_workLimit && m_firstAttempt )
1130                             {
1131                                 return;
1132                             }
1133                         }
1134                         m_ftab[ sb ] |= SETMASK;
1135                     }
1136                 }
1137 
1138                 /*
1139                  * The ss big bucket is now done.  Record this fact,
1140                  * and update the quadrant descriptors.  Remember to
1141                  * update quadrants in the overshoot area too, if
1142                  * necessary.  The "if (i < 255)" test merely skips
1143                  * this updating for the last bucket processed, since
1144                  * updating for the last bucket is pointless.
1145                  */
1146                 bigDone[ ss ] = true;
1147 
1148                 if( i < 255 )
1149                 {
1150                     int bbStart = m_ftab[ ss << 8 ] & CLEARMASK;
1151                     int bbSize = ( m_ftab[ ( ss + 1 ) << 8 ] & CLEARMASK ) - bbStart;
1152                     int shifts = 0;
1153 
1154                     while( ( bbSize >> shifts ) > 65534 )
1155                     {
1156                         shifts++;
1157                     }
1158 
1159                     for( j = 0; j < bbSize; j++ )
1160                     {
1161                         int a2update = m_zptr[ bbStart + j ];
1162                         int qVal = ( j >> shifts );
1163                         m_quadrant[ a2update ] = qVal;
1164                         if( a2update < NUM_OVERSHOOT_BYTES )
1165                         {
1166                             m_quadrant[ a2update + m_last + 1 ] = qVal;
1167                         }
1168                     }
1169 
1170                     if( !( ( ( bbSize - 1 ) >> shifts ) <= 65535 ) )
1171                     {
1172                         panic();
1173                     }
1174                 }
1175 
1176                 /*
1177                  * Now scan this big bucket so as to synthesise the
1178                  * sorted order for small buckets [t, ss] for all t != ss.
1179                  */
1180                 for( j = 0; j <= 255; j++ )
1181                 {
1182                     copy[ j ] = m_ftab[ ( j << 8 ) + ss ] & CLEARMASK;
1183                 }
1184 
1185                 for( j = m_ftab[ ss << 8 ] & CLEARMASK;
1186                      j < ( m_ftab[ ( ss + 1 ) << 8 ] & CLEARMASK ); j++ )
1187                 {
1188                     c1 = m_block[ m_zptr[ j ] ];
1189                     if( !bigDone[ c1 ] )
1190                     {
1191                         m_zptr[ copy[ c1 ] ] = m_zptr[ j ] == 0 ? m_last : m_zptr[ j ] - 1;
1192                         copy[ c1 ]++;
1193                     }
1194                 }
1195 
1196                 for( j = 0; j <= 255; j++ )
1197                 {
1198                     m_ftab[ ( j << 8 ) + ss ] |= SETMASK;
1199                 }
1200             }
1201         }
1202     }
1203 
1204     private void makeMaps()
1205     {
1206         int i;
1207         m_nInUse = 0;
1208         for( i = 0; i < 256; i++ )
1209         {
1210             if( m_inUse[ i ] )
1211             {
1212                 m_seqToUnseq[ m_nInUse ] = (char)i;
1213                 m_unseqToSeq[ i ] = (char)m_nInUse;
1214                 m_nInUse++;
1215             }
1216         }
1217     }
1218 
1219     private char med3( char a, char b, char c )
1220     {
1221         char t;
1222         if( a > b )
1223         {
1224             t = a;
1225             a = b;
1226             b = t;
1227         }
1228         if( b > c )
1229         {
1230             t = b;
1231             b = c;
1232             c = t;
1233         }
1234         if( a > b )
1235         {
1236             b = a;
1237         }
1238         return b;
1239     }
1240 
1241     private void moveToFrontCodeAndSend()
1242         throws IOException
1243     {
1244         bsPutIntVS( 24, m_origPtr );
1245         generateMTFValues();
1246         sendMTFValues();
1247     }
1248 
1249     private void qSort3( int loSt, int hiSt, int dSt )
1250     {
1251         int unLo;
1252         int unHi;
1253         int ltLo;
1254         int gtHi;
1255         int med;
1256         int n;
1257         int m;
1258         int sp;
1259         int lo;
1260         int hi;
1261         int d;
1262         StackElem[] stack = new StackElem[ QSORT_STACK_SIZE ];
1263         for( int count = 0; count < QSORT_STACK_SIZE; count++ )
1264         {
1265             stack[ count ] = new StackElem();
1266         }
1267 
1268         sp = 0;
1269 
1270         stack[ sp ].m_ll = loSt;
1271         stack[ sp ].m_hh = hiSt;
1272         stack[ sp ].m_dd = dSt;
1273         sp++;
1274 
1275         while( sp > 0 )
1276         {
1277             if( sp >= QSORT_STACK_SIZE )
1278             {
1279                 panic();
1280             }
1281 
1282             sp--;
1283             lo = stack[ sp ].m_ll;
1284             hi = stack[ sp ].m_hh;
1285             d = stack[ sp ].m_dd;
1286 
1287             if( hi - lo < SMALL_THRESH || d > DEPTH_THRESH )
1288             {
1289                 simpleSort( lo, hi, d );
1290                 if( m_workDone > m_workLimit && m_firstAttempt )
1291                 {
1292                     return;
1293                 }
1294                 continue;
1295             }
1296 
1297             med = med3( m_block[ m_zptr[ lo ] + d + 1 ],
1298                         m_block[ m_zptr[ hi ] + d + 1 ],
1299                         m_block[ m_zptr[ ( lo + hi ) >> 1 ] + d + 1 ] );
1300 
1301             unLo = lo;
1302             ltLo = lo;
1303             unHi = hi;
1304             gtHi = hi;
1305 
1306             while( true )
1307             {
1308                 while( true )
1309                 {
1310                     if( unLo > unHi )
1311                     {
1312                         break;
1313                     }
1314                     n = m_block[ m_zptr[ unLo ] + d + 1 ] - med;
1315                     if( n == 0 )
1316                     {
1317                         int temp = 0;
1318                         temp = m_zptr[ unLo ];
1319                         m_zptr[ unLo ] = m_zptr[ ltLo ];
1320                         m_zptr[ ltLo ] = temp;
1321                         ltLo++;
1322                         unLo++;
1323                         continue;
1324                     }
1325                     ;
1326                     if( n > 0 )
1327                     {
1328                         break;
1329                     }
1330                     unLo++;
1331                 }
1332                 while( true )
1333                 {
1334                     if( unLo > unHi )
1335                     {
1336                         break;
1337                     }
1338                     n = m_block[ m_zptr[ unHi ] + d + 1 ] - med;
1339                     if( n == 0 )
1340                     {
1341                         int temp = 0;
1342                         temp = m_zptr[ unHi ];
1343                         m_zptr[ unHi ] = m_zptr[ gtHi ];
1344                         m_zptr[ gtHi ] = temp;
1345                         gtHi--;
1346                         unHi--;
1347                         continue;
1348                     }
1349                     ;
1350                     if( n < 0 )
1351                     {
1352                         break;
1353                     }
1354                     unHi--;
1355                 }
1356                 if( unLo > unHi )
1357                 {
1358                     break;
1359                 }
1360                 int temp = 0;
1361                 temp = m_zptr[ unLo ];
1362                 m_zptr[ unLo ] = m_zptr[ unHi ];
1363                 m_zptr[ unHi ] = temp;
1364                 unLo++;
1365                 unHi--;
1366             }
1367 
1368             if( gtHi < ltLo )
1369             {
1370                 stack[ sp ].m_ll = lo;
1371                 stack[ sp ].m_hh = hi;
1372                 stack[ sp ].m_dd = d + 1;
1373                 sp++;
1374                 continue;
1375             }
1376 
1377             n = ( ( ltLo - lo ) < ( unLo - ltLo ) ) ? ( ltLo - lo ) : ( unLo - ltLo );
1378             vswap( lo, unLo - n, n );
1379             m = ( ( hi - gtHi ) < ( gtHi - unHi ) ) ? ( hi - gtHi ) : ( gtHi - unHi );
1380             vswap( unLo, hi - m + 1, m );
1381 
1382             n = lo + unLo - ltLo - 1;
1383             m = hi - ( gtHi - unHi ) + 1;
1384 
1385             stack[ sp ].m_ll = lo;
1386             stack[ sp ].m_hh = n;
1387             stack[ sp ].m_dd = d;
1388             sp++;
1389 
1390             stack[ sp ].m_ll = n + 1;
1391             stack[ sp ].m_hh = m - 1;
1392             stack[ sp ].m_dd = d + 1;
1393             sp++;
1394 
1395             stack[ sp ].m_ll = m;
1396             stack[ sp ].m_hh = hi;
1397             stack[ sp ].m_dd = d;
1398             sp++;
1399         }
1400     }
1401 
1402     private void randomiseBlock()
1403     {
1404         int i;
1405         int rNToGo = 0;
1406         int rTPos = 0;
1407         for( i = 0; i < 256; i++ )
1408         {
1409             m_inUse[ i ] = false;
1410         }
1411 
1412         for( i = 0; i <= m_last; i++ )
1413         {
1414             if( rNToGo == 0 )
1415             {
1416                 rNToGo = (char)RAND_NUMS[ rTPos ];
1417                 rTPos++;
1418                 if( rTPos == 512 )
1419                 {
1420                     rTPos = 0;
1421                 }
1422             }
1423             rNToGo--;
1424             m_block[ i + 1 ] ^= ( ( rNToGo == 1 ) ? 1 : 0 );
1425             // handle 16 bit signed numbers
1426             m_block[ i + 1 ] &= 0xFF;
1427 
1428             m_inUse[ m_block[ i + 1 ] ] = true;
1429         }
1430     }
1431 
1432     private void sendMTFValues()
1433         throws IOException
1434     {
1435         char[][] len = new char[ N_GROUPS ][ MAX_ALPHA_SIZE ];
1436 
1437         int v;
1438 
1439         int t;
1440 
1441         int i;
1442 
1443         int j;
1444 
1445         int gs;
1446 
1447         int ge;
1448 
1449         int bt;
1450 
1451         int bc;
1452 
1453         int iter;
1454         int nSelectors = 0;
1455         int alphaSize;
1456         int minLen;
1457         int maxLen;
1458         int selCtr;
1459         int nGroups;
1460 
1461         alphaSize = m_nInUse + 2;
1462         for( t = 0; t < N_GROUPS; t++ )
1463         {
1464             for( v = 0; v < alphaSize; v++ )
1465             {
1466                 len[ t ][ v ] = (char)GREATER_ICOST;
1467             }
1468         }
1469 
1470         /*
1471          * Decide how many coding tables to use
1472          */
1473         if( m_nMTF <= 0 )
1474         {
1475             panic();
1476         }
1477 
1478         if( m_nMTF < 200 )
1479         {
1480             nGroups = 2;
1481         }
1482         else if( m_nMTF < 600 )
1483         {
1484             nGroups = 3;
1485         }
1486         else if( m_nMTF < 1200 )
1487         {
1488             nGroups = 4;
1489         }
1490         else if( m_nMTF < 2400 )
1491         {
1492             nGroups = 5;
1493         }
1494         else
1495         {
1496             nGroups = 6;
1497         }
1498         {
1499             /*
1500              * Generate an initial set of coding tables
1501              */
1502             int nPart;
1503             int remF;
1504             int tFreq;
1505             int aFreq;
1506 
1507             nPart = nGroups;
1508             remF = m_nMTF;
1509             gs = 0;
1510             while( nPart > 0 )
1511             {
1512                 tFreq = remF / nPart;
1513                 ge = gs - 1;
1514                 aFreq = 0;
1515                 while( aFreq < tFreq && ge < alphaSize - 1 )
1516                 {
1517                     ge++;
1518                     aFreq += m_mtfFreq[ ge ];
1519                 }
1520 
1521                 if( ge > gs && nPart != nGroups && nPart != 1
1522                     && ( ( nGroups - nPart ) % 2 == 1 ) )
1523                 {
1524                     aFreq -= m_mtfFreq[ ge ];
1525                     ge--;
1526                 }
1527 
1528                 for( v = 0; v < alphaSize; v++ )
1529                 {
1530                     if( v >= gs && v <= ge )
1531                     {
1532                         len[ nPart - 1 ][ v ] = (char)LESSER_ICOST;
1533                     }
1534                     else
1535                     {
1536                         len[ nPart - 1 ][ v ] = (char)GREATER_ICOST;
1537                     }
1538                 }
1539 
1540                 nPart--;
1541                 gs = ge + 1;
1542                 remF -= aFreq;
1543             }
1544         }
1545 
1546         int[][] rfreq = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
1547         int[] fave = new int[ N_GROUPS ];
1548         short[] cost = new short[ N_GROUPS ];
1549         /*
1550          * Iterate up to N_ITERS times to improve the tables.
1551          */
1552         for( iter = 0; iter < N_ITERS; iter++ )
1553         {
1554             for( t = 0; t < nGroups; t++ )
1555             {
1556                 fave[ t ] = 0;
1557             }
1558 
1559             for( t = 0; t < nGroups; t++ )
1560             {
1561                 for( v = 0; v < alphaSize; v++ )
1562                 {
1563                     rfreq[ t ][ v ] = 0;
1564                 }
1565             }
1566 
1567             nSelectors = 0;
1568             gs = 0;
1569             while( true )
1570             {
1571 
1572                 /*
1573                  * Set group start & end marks.
1574                  */
1575                 if( gs >= m_nMTF )
1576                 {
1577                     break;
1578                 }
1579                 ge = gs + G_SIZE - 1;
1580                 if( ge >= m_nMTF )
1581                 {
1582                     ge = m_nMTF - 1;
1583                 }
1584 
1585                 /*
1586                  * Calculate the cost of this group as coded
1587                  * by each of the coding tables.
1588                  */
1589                 for( t = 0; t < nGroups; t++ )
1590                 {
1591                     cost[ t ] = 0;
1592                 }
1593 
1594                 if( nGroups == 6 )
1595                 {
1596                     short cost0 = 0;
1597                     short cost1 = 0;
1598                     short cost2 = 0;
1599                     short cost3 = 0;
1600                     short cost4 = 0;
1601                     short cost5 = 0;
1602 
1603                     for( i = gs; i <= ge; i++ )
1604                     {
1605                         short icv = m_szptr[ i ];
1606                         cost0 += len[ 0 ][ icv ];
1607                         cost1 += len[ 1 ][ icv ];
1608                         cost2 += len[ 2 ][ icv ];
1609                         cost3 += len[ 3 ][ icv ];
1610                         cost4 += len[ 4 ][ icv ];
1611                         cost5 += len[ 5 ][ icv ];
1612                     }
1613                     cost[ 0 ] = cost0;
1614                     cost[ 1 ] = cost1;
1615                     cost[ 2 ] = cost2;
1616                     cost[ 3 ] = cost3;
1617                     cost[ 4 ] = cost4;
1618                     cost[ 5 ] = cost5;
1619                 }
1620                 else
1621                 {
1622                     for( i = gs; i <= ge; i++ )
1623                     {
1624                         short icv = m_szptr[ i ];
1625                         for( t = 0; t < nGroups; t++ )
1626                         {
1627                             cost[ t ] += len[ t ][ icv ];
1628                         }
1629                     }
1630                 }
1631 
1632                 /*
1633                  * Find the coding table which is best for this group,
1634                  * and record its identity in the selector table.
1635                  */
1636                 bc = 999999999;
1637                 bt = -1;
1638                 for( t = 0; t < nGroups; t++ )
1639                 {
1640                     if( cost[ t ] < bc )
1641                     {
1642                         bc = cost[ t ];
1643                         bt = t;
1644                     }
1645                 }
1646                 ;
1647                 fave[ bt ]++;
1648                 m_selector[ nSelectors ] = (char)bt;
1649                 nSelectors++;
1650 
1651                 /*
1652                  * Increment the symbol frequencies for the selected table.
1653                  */
1654                 for( i = gs; i <= ge; i++ )
1655                 {
1656                     rfreq[ bt ][ m_szptr[ i ] ]++;
1657                 }
1658 
1659                 gs = ge + 1;
1660             }
1661 
1662             /*
1663              * Recompute the tables based on the accumulated frequencies.
1664              */
1665             for( t = 0; t < nGroups; t++ )
1666             {
1667                 hbMakeCodeLengths( len[ t ], rfreq[ t ], alphaSize, 20 );
1668             }
1669         }
1670 
1671         rfreq = null;
1672         fave = null;
1673         cost = null;
1674 
1675         if( !( nGroups < 8 ) )
1676         {
1677             panic();
1678         }
1679         if( !( nSelectors < 32768 && nSelectors <= ( 2 + ( 900000 / G_SIZE ) ) ) )
1680         {
1681             panic();
1682         }
1683         {
1684             /*
1685              * Compute MTF values for the selectors.
1686              */
1687             char[] pos = new char[ N_GROUPS ];
1688             char ll_i;
1689             char tmp2;
1690             char tmp;
1691             for( i = 0; i < nGroups; i++ )
1692             {
1693                 pos[ i ] = (char)i;
1694             }
1695             for( i = 0; i < nSelectors; i++ )
1696             {
1697                 ll_i = m_selector[ i ];
1698                 j = 0;
1699                 tmp = pos[ j ];
1700                 while( ll_i != tmp )
1701                 {
1702                     j++;
1703                     tmp2 = tmp;
1704                     tmp = pos[ j ];
1705                     pos[ j ] = tmp2;
1706                 }
1707                 pos[ 0 ] = tmp;
1708                 m_selectorMtf[ i ] = (char)j;
1709             }
1710         }
1711 
1712         int[][] code = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
1713 
1714         /*
1715          * Assign actual codes for the tables.
1716          */
1717         for( t = 0; t < nGroups; t++ )
1718         {
1719             minLen = 32;
1720             maxLen = 0;
1721             for( i = 0; i < alphaSize; i++ )
1722             {
1723                 if( len[ t ][ i ] > maxLen )
1724                 {
1725                     maxLen = len[ t ][ i ];
1726                 }
1727                 if( len[ t ][ i ] < minLen )
1728                 {
1729                     minLen = len[ t ][ i ];
1730                 }
1731             }
1732             if( maxLen > 20 )
1733             {
1734                 panic();
1735             }
1736             if( minLen < 1 )
1737             {
1738                 panic();
1739             }
1740             hbAssignCodes( code[ t ], len[ t ], minLen, maxLen, alphaSize );
1741         }
1742         {
1743             /*
1744              * Transmit the mapping table.
1745              */
1746             boolean[] inUse16 = new boolean[ 16 ];
1747             for( i = 0; i < 16; i++ )
1748             {
1749                 inUse16[ i ] = false;
1750                 for( j = 0; j < 16; j++ )
1751                 {
1752                     if( m_inUse[ i * 16 + j ] )
1753                     {
1754                         inUse16[ i ] = true;
1755                     }
1756                 }
1757             }
1758 
1759             for( i = 0; i < 16; i++ )
1760             {
1761                 if( inUse16[ i ] )
1762                 {
1763                     bsW( 1, 1 );
1764                 }
1765                 else
1766                 {
1767                     bsW( 1, 0 );
1768                 }
1769             }
1770 
1771             for( i = 0; i < 16; i++ )
1772             {
1773                 if( inUse16[ i ] )
1774                 {
1775                     for( j = 0; j < 16; j++ )
1776                     {
1777                         if( m_inUse[ i * 16 + j ] )
1778                         {
1779                             bsW( 1, 1 );
1780                         }
1781                         else
1782                         {
1783                             bsW( 1, 0 );
1784                         }
1785                     }
1786                 }
1787             }
1788 
1789         }
1790 
1791         /*
1792          * Now the selectors.
1793          */
1794         bsW( 3, nGroups );
1795         bsW( 15, nSelectors );
1796         for( i = 0; i < nSelectors; i++ )
1797         {
1798             for( j = 0; j < m_selectorMtf[ i ]; j++ )
1799             {
1800                 bsW( 1, 1 );
1801             }
1802             bsW( 1, 0 );
1803         }
1804 
1805         for( t = 0; t < nGroups; t++ )
1806         {
1807             int curr = len[ t ][ 0 ];
1808             bsW( 5, curr );
1809             for( i = 0; i < alphaSize; i++ )
1810             {
1811                 while( curr < len[ t ][ i ] )
1812                 {
1813                     bsW( 2, 2 );
1814                     curr++;
1815                     /*
1816                      * 10
1817                      */
1818                 }
1819                 while( curr > len[ t ][ i ] )
1820                 {
1821                     bsW( 2, 3 );
1822                     curr--;
1823                     /*
1824                      * 11
1825                      */
1826                 }
1827                 bsW( 1, 0 );
1828             }
1829         }
1830 
1831         /*
1832          * And finally, the block data proper
1833          */
1834         selCtr = 0;
1835         gs = 0;
1836         while( true )
1837         {
1838             if( gs >= m_nMTF )
1839             {
1840                 break;
1841             }
1842             ge = gs + G_SIZE - 1;
1843             if( ge >= m_nMTF )
1844             {
1845                 ge = m_nMTF - 1;
1846             }
1847             for( i = gs; i <= ge; i++ )
1848             {
1849                 bsW( len[ m_selector[ selCtr ] ][ m_szptr[ i ] ],
1850                      code[ m_selector[ selCtr ] ][ m_szptr[ i ] ] );
1851             }
1852 
1853             gs = ge + 1;
1854             selCtr++;
1855         }
1856         if( !( selCtr == nSelectors ) )
1857         {
1858             panic();
1859         }
1860     }
1861 
1862     private void simpleSort( int lo, int hi, int d )
1863     {
1864         int i;
1865         int j;
1866         int h;
1867         int bigN;
1868         int hp;
1869         int v;
1870 
1871         bigN = hi - lo + 1;
1872         if( bigN < 2 )
1873         {
1874             return;
1875         }
1876 
1877         hp = 0;
1878         while( m_incs[ hp ] < bigN )
1879         {
1880             hp++;
1881         }
1882         hp--;
1883 
1884         for( ; hp >= 0; hp-- )
1885         {
1886             h = m_incs[ hp ];
1887 
1888             i = lo + h;
1889             while( true )
1890             {
1891                 /*
1892                  * copy 1
1893                  */
1894                 if( i > hi )
1895                 {
1896                     break;
1897                 }
1898                 v = m_zptr[ i ];
1899                 j = i;
1900                 while( fullGtU( m_zptr[ j - h ] + d, v + d ) )
1901                 {
1902                     m_zptr[ j ] = m_zptr[ j - h ];
1903                     j = j - h;
1904                     if( j <= ( lo + h - 1 ) )
1905                     {
1906                         break;
1907                     }
1908                 }
1909                 m_zptr[ j ] = v;
1910                 i++;
1911 
1912                 /*
1913                  * copy 2
1914                  */
1915                 if( i > hi )
1916                 {
1917                     break;
1918                 }
1919                 v = m_zptr[ i ];
1920                 j = i;
1921                 while( fullGtU( m_zptr[ j - h ] + d, v + d ) )
1922                 {
1923                     m_zptr[ j ] = m_zptr[ j - h ];
1924                     j = j - h;
1925                     if( j <= ( lo + h - 1 ) )
1926                     {
1927                         break;
1928                     }
1929                 }
1930                 m_zptr[ j ] = v;
1931                 i++;
1932 
1933                 /*
1934                  * copy 3
1935                  */
1936                 if( i > hi )
1937                 {
1938                     break;
1939                 }
1940                 v = m_zptr[ i ];
1941                 j = i;
1942                 while( fullGtU( m_zptr[ j - h ] + d, v + d ) )
1943                 {
1944                     m_zptr[ j ] = m_zptr[ j - h ];
1945                     j = j - h;
1946                     if( j <= ( lo + h - 1 ) )
1947                     {
1948                         break;
1949                     }
1950                 }
1951                 m_zptr[ j ] = v;
1952                 i++;
1953 
1954                 if( m_workDone > m_workLimit && m_firstAttempt )
1955                 {
1956                     return;
1957                 }
1958             }
1959         }
1960     }
1961 
1962     private void vswap( int p1, int p2, int n )
1963     {
1964         int temp = 0;
1965         while( n > 0 )
1966         {
1967             temp = m_zptr[ p1 ];
1968             m_zptr[ p1 ] = m_zptr[ p2 ];
1969             m_zptr[ p2 ] = temp;
1970             p1++;
1971             p2++;
1972             n--;
1973         }
1974     }
1975 
1976     private void writeRun()
1977         throws IOException
1978     {
1979         if( m_last < m_allowableBlockSize )
1980         {
1981             m_inUse[ m_currentChar ] = true;
1982             for( int i = 0; i < m_runLength; i++ )
1983             {
1984                 m_crc.updateCRC( (char)m_currentChar );
1985             }
1986             switch( m_runLength )
1987             {
1988                 case 1:
1989                     m_last++;
1990                     m_block[ m_last + 1 ] = (char)m_currentChar;
1991                     break;
1992                 case 2:
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                     break;
1998                 case 3:
1999                     m_last++;
2000                     m_block[ m_last + 1 ] = (char)m_currentChar;
2001                     m_last++;
2002                     m_block[ m_last + 1 ] = (char)m_currentChar;
2003                     m_last++;
2004                     m_block[ m_last + 1 ] = (char)m_currentChar;
2005                     break;
2006                 default:
2007                     m_inUse[ m_runLength - 4 ] = true;
2008                     m_last++;
2009                     m_block[ m_last + 1 ] = (char)m_currentChar;
2010                     m_last++;
2011                     m_block[ m_last + 1 ] = (char)m_currentChar;
2012                     m_last++;
2013                     m_block[ m_last + 1 ] = (char)m_currentChar;
2014                     m_last++;
2015                     m_block[ m_last + 1 ] = (char)m_currentChar;
2016                     m_last++;
2017                     m_block[ m_last + 1 ] = (char)( m_runLength - 4 );
2018                     break;
2019             }
2020         }
2021         else
2022         {
2023             endBlock();
2024             initBlock();
2025             writeRun();
2026         }
2027     }
2028 
2029     private static class StackElem
2030     {
2031         int m_dd;
2032         int m_hh;
2033         int m_ll;
2034     }
2035 }
2036