commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tcu...@apache.org
Subject svn commit: r427072 [4/5] - in /jakarta/commons/sandbox/compress/trunk: ./ src/examples/ src/examples/org/ src/examples/org/apache/ src/examples/org/apache/commons/ src/examples/org/apache/commons/compress/ src/examples/org/apache/commons/compress/exam...
Date Mon, 31 Jul 2006 10:55:13 GMT
Added: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java
URL: http://svn.apache.org/viewvc/jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java?rev=427072&view=auto
==============================================================================
--- jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java (added)
+++ jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java Mon Jul 31 03:55:10 2006
@@ -0,0 +1,994 @@
+/*
+ * Copyright 2002,2004 The Apache Software Foundation.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.compress.compressors.bzip2;
+
+import java.io.IOException;
+import java.io.InputStream;
+
+
+/*
+ * This package is based on the work done by Keiron Liddle, Aftex Software
+ * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
+ * great code.
+ */
+
+/**
+ * An input stream that decompresses from the BZip2 format (without the file
+ * header chars) to be read as any other stream.
+ *
+ * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
+ */
+public class BZip2InputStream
+    extends InputStream
+    implements BZip2Constants
+{
+    private static final int START_BLOCK_STATE = 1;
+    private static final int RAND_PART_A_STATE = 2;
+    private static final int RAND_PART_B_STATE = 3;
+    private static final int RAND_PART_C_STATE = 4;
+    private static final int NO_RAND_PART_A_STATE = 5;
+    private static final int NO_RAND_PART_B_STATE = 6;
+    private static final int NO_RAND_PART_C_STATE = 7;
+
+    private CRC m_crc = new CRC();
+    private boolean[] m_inUse = new boolean[ 256 ];
+    private char[] m_seqToUnseq = new char[ 256 ];
+    private char[] m_unseqToSeq = new char[ 256 ];
+    private char[] m_selector = new char[ MAX_SELECTORS ];
+    private char[] m_selectorMtf = new char[ MAX_SELECTORS ];
+
+    /*
+     * freq table collected to save a pass over the data
+     * during decompression.
+     */
+    private int[] m_unzftab = new int[ 256 ];
+
+    private int[][] m_limit = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+    private int[][] m_base = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+    private int[][] m_perm = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+    private int[] m_minLens = new int[ N_GROUPS ];
+
+    private boolean m_streamEnd;
+    private int m_currentChar = -1;
+
+    private int m_currentState = START_BLOCK_STATE;
+    private int m_rNToGo;
+    private int m_rTPos;
+    private int m_tPos;
+
+    private int i2;
+    private int count;
+    private int chPrev;
+    private int ch2;
+    private int j2;
+    private char z;
+
+    private boolean m_blockRandomised;
+
+    /*
+     * always: in the range 0 .. 9.
+     * The current block size is 100000 * this number.
+     */
+    private int m_blockSize100k;
+    private int m_bsBuff;
+    private int m_bsLive;
+
+    private InputStream m_input;
+
+    private int m_computedBlockCRC;
+    private int m_computedCombinedCRC;
+
+    /*
+     * index of the last char in the block, so
+     * the block size == last + 1.
+     */
+    private int m_last;
+    private char[] m_ll8;
+    private int m_nInUse;
+
+    /*
+     * index in zptr[] of original string after sorting.
+     */
+    private int m_origPtr;
+
+    private int m_storedBlockCRC;
+    private int m_storedCombinedCRC;
+    private int[] m_tt;
+
+    /**
+     * Initializes ein CBZip2 InputStream with the give
+     * InputStream
+     * @param input the InputStream to initialize with
+     */
+    public BZip2InputStream( final InputStream input )
+    {
+        bsSetStream( input );
+        initialize();
+        initBlock();
+        setupBlock();
+    }
+
+    private static void badBlockHeader()
+    {
+        cadvise();
+    }
+
+    private static void blockOverrun()
+    {
+        cadvise();
+    }
+
+    private static void cadvise()
+    {
+        System.out.println( "CRC Error" );
+        //throw new CCoruptionError();
+    }
+
+    private static void compressedStreamEOF()
+    {
+        cadvise();
+    }
+
+    private static void crcError()
+    {
+        cadvise();
+    }
+
+    /* (non-Javadoc)
+     * @see java.io.InputStream#read()
+     */
+    public int read()
+    {
+        if( m_streamEnd )
+        {
+            return -1;
+        }
+        else
+        {
+            int retChar = m_currentChar;
+            switch( m_currentState )
+            {
+                case START_BLOCK_STATE:
+                    break;
+                case RAND_PART_A_STATE:
+                    break;
+                case RAND_PART_B_STATE:
+                    setupRandPartB();
+                    break;
+                case RAND_PART_C_STATE:
+                    setupRandPartC();
+                    break;
+                case NO_RAND_PART_A_STATE:
+                    break;
+                case NO_RAND_PART_B_STATE:
+                    setupNoRandPartB();
+                    break;
+                case NO_RAND_PART_C_STATE:
+                    setupNoRandPartC();
+                    break;
+                default:
+                    break;
+            }
+            return retChar;
+        }
+    }
+
+    private void setDecompressStructureSizes( int newSize100k )
+    {
+        if( !( 0 <= newSize100k && newSize100k <= 9 && 0 <= m_blockSize100k
+            && m_blockSize100k <= 9 ) )
+        {
+            // throw new IOException("Invalid block size");
+        }
+
+        m_blockSize100k = newSize100k;
+
+        if( newSize100k == 0 )
+        {
+            return;
+        }
+
+        int n = BASE_BLOCK_SIZE * newSize100k;
+        m_ll8 = new char[ n ];
+        m_tt = new int[ n ];
+    }
+
+    private void setupBlock()
+    {
+        int[] cftab = new int[ 257 ];
+        char ch;
+
+        cftab[ 0 ] = 0;
+        for( int i = 1; i <= 256; i++ )
+        {
+            cftab[ i ] = m_unzftab[ i - 1 ];
+        }
+        for( int i = 1; i <= 256; i++ )
+        {
+            cftab[ i ] += cftab[ i - 1 ];
+        }
+
+        for( int i = 0; i <= m_last; i++ )
+        {
+            ch = m_ll8[ i ];
+            m_tt[ cftab[ ch ] ] = i;
+            cftab[ ch ]++;
+        }
+        cftab = null;
+
+        m_tPos = m_tt[ m_origPtr ];
+
+        count = 0;
+        i2 = 0;
+        ch2 = 256;
+        /*
+         * not a char and not EOF
+         */
+        if( m_blockRandomised )
+        {
+            m_rNToGo = 0;
+            m_rTPos = 0;
+            setupRandPartA();
+        }
+        else
+        {
+            setupNoRandPartA();
+        }
+    }
+
+    private void setupNoRandPartA()
+    {
+        if( i2 <= m_last )
+        {
+            chPrev = ch2;
+            ch2 = m_ll8[ m_tPos ];
+            m_tPos = m_tt[ m_tPos ];
+            i2++;
+
+            m_currentChar = ch2;
+            m_currentState = NO_RAND_PART_B_STATE;
+            m_crc.updateCRC( ch2 );
+        }
+        else
+        {
+            endBlock();
+            initBlock();
+            setupBlock();
+        }
+    }
+
+    private void setupNoRandPartB()
+    {
+        if( ch2 != chPrev )
+        {
+            m_currentState = NO_RAND_PART_A_STATE;
+            count = 1;
+            setupNoRandPartA();
+        }
+        else
+        {
+            count++;
+            if( count >= 4 )
+            {
+                z = m_ll8[ m_tPos ];
+                m_tPos = m_tt[ m_tPos ];
+                m_currentState = NO_RAND_PART_C_STATE;
+                j2 = 0;
+                setupNoRandPartC();
+            }
+            else
+            {
+                m_currentState = NO_RAND_PART_A_STATE;
+                setupNoRandPartA();
+            }
+        }
+    }
+
+    private void setupNoRandPartC()
+    {
+        if( j2 < z )
+        {
+            m_currentChar = ch2;
+            m_crc.updateCRC( ch2 );
+            j2++;
+        }
+        else
+        {
+            m_currentState = NO_RAND_PART_A_STATE;
+            i2++;
+            count = 0;
+            setupNoRandPartA();
+        }
+    }
+
+    private void setupRandPartA()
+    {
+        if( i2 <= m_last )
+        {
+            chPrev = ch2;
+            ch2 = m_ll8[ m_tPos ];
+            m_tPos = m_tt[ m_tPos ];
+            if( m_rNToGo == 0 )
+            {
+                m_rNToGo = RAND_NUMS[ m_rTPos ];
+                m_rTPos++;
+                if( m_rTPos == 512 )
+                {
+                    m_rTPos = 0;
+                }
+            }
+            m_rNToGo--;
+            ch2 ^= ( ( m_rNToGo == 1 ) ? 1 : 0 );
+            i2++;
+
+            m_currentChar = ch2;
+            m_currentState = RAND_PART_B_STATE;
+            m_crc.updateCRC( ch2 );
+        }
+        else
+        {
+            endBlock();
+            initBlock();
+            setupBlock();
+        }
+    }
+
+    private void setupRandPartB()
+    {
+        if( ch2 != chPrev )
+        {
+            m_currentState = RAND_PART_A_STATE;
+            count = 1;
+            setupRandPartA();
+        }
+        else
+        {
+            count++;
+            if( count >= 4 )
+            {
+                z = m_ll8[ m_tPos ];
+                m_tPos = m_tt[ m_tPos ];
+                if( m_rNToGo == 0 )
+                {
+                    m_rNToGo = RAND_NUMS[ m_rTPos ];
+                    m_rTPos++;
+                    if( m_rTPos == 512 )
+                    {
+                        m_rTPos = 0;
+                    }
+                }
+                m_rNToGo--;
+                z ^= ( ( m_rNToGo == 1 ) ? 1 : 0 );
+                j2 = 0;
+                m_currentState = RAND_PART_C_STATE;
+                setupRandPartC();
+            }
+            else
+            {
+                m_currentState = RAND_PART_A_STATE;
+                setupRandPartA();
+            }
+        }
+    }
+
+    private void setupRandPartC()
+    {
+        if( j2 < z )
+        {
+            m_currentChar = ch2;
+            m_crc.updateCRC( ch2 );
+            j2++;
+        }
+        else
+        {
+            m_currentState = RAND_PART_A_STATE;
+            i2++;
+            count = 0;
+            setupRandPartA();
+        }
+    }
+
+    private void getAndMoveToFrontDecode()
+    {
+        int nextSym;
+
+        int limitLast = BASE_BLOCK_SIZE * m_blockSize100k;
+        m_origPtr = readVariableSizedInt( 24 );
+
+        recvDecodingTables();
+        int EOB = m_nInUse + 1;
+        int groupNo = -1;
+        int groupPos = 0;
+
+        /*
+         * Setting up the unzftab entries here is not strictly
+         * necessary, but it does save having to do it later
+         * in a separate pass, and so saves a block's worth of
+         * cache misses.
+         */
+        for( int i = 0; i <= 255; i++ )
+        {
+            m_unzftab[ i ] = 0;
+        }
+
+        final char[] yy = new char[ 256 ];
+        for( int i = 0; i <= 255; i++ )
+        {
+            yy[ i ] = (char)i;
+        }
+
+        m_last = -1;
+        int zt;
+        int zn;
+        int zvec;
+        int zj;
+        groupNo++;
+        groupPos = G_SIZE - 1;
+
+        zt = m_selector[ groupNo ];
+        zn = m_minLens[ zt ];
+        zvec = bsR( zn );
+        while( zvec > m_limit[ zt ][ zn ] )
+        {
+            zn++;
+
+            while( m_bsLive < 1 )
+            {
+                int zzi;
+                char thech = 0;
+                try
+                {
+                    thech = (char)m_input.read();
+                }
+                catch( IOException e )
+                {
+                    compressedStreamEOF();
+                }
+                if( thech == -1 )
+                {
+                    compressedStreamEOF();
+                }
+                zzi = thech;
+                m_bsBuff = ( m_bsBuff << 8 ) | ( zzi & 0xff );
+                m_bsLive += 8;
+            }
+
+            zj = ( m_bsBuff >> ( m_bsLive - 1 ) ) & 1;
+            m_bsLive--;
+
+            zvec = ( zvec << 1 ) | zj;
+        }
+        nextSym = m_perm[ zt ][ zvec - m_base[ zt ][ zn ] ];
+
+        while( true )
+        {
+            if( nextSym == EOB )
+            {
+                break;
+            }
+
+            if( nextSym == RUNA || nextSym == RUNB )
+            {
+                char ch;
+                int s = -1;
+                int N = 1;
+                do
+                {
+                    if( nextSym == RUNA )
+                    {
+                        s = s + ( 0 + 1 ) * N;
+                    }
+                    else// if( nextSym == RUNB )
+                    {
+                        s = s + ( 1 + 1 ) * N;
+                    }
+                    N = N * 2;
+
+                    if( groupPos == 0 )
+                    {
+                        groupNo++;
+                        groupPos = G_SIZE;
+                    }
+                    groupPos--;
+                    zt = m_selector[ groupNo ];
+                    zn = m_minLens[ zt ];
+                    zvec = bsR( zn );
+                    while( zvec > m_limit[ zt ][ zn ] )
+                    {
+                        zn++;
+
+                        while( m_bsLive < 1 )
+                        {
+                            int zzi;
+                            char thech = 0;
+                            try
+                            {
+                                thech = (char)m_input.read();
+                            }
+                            catch( IOException e )
+                            {
+                                compressedStreamEOF();
+                            }
+                            if( thech == -1 )
+                            {
+                                compressedStreamEOF();
+                            }
+                            zzi = thech;
+                            m_bsBuff = ( m_bsBuff << 8 ) | ( zzi & 0xff );
+                            m_bsLive += 8;
+                        }
+
+                        zj = ( m_bsBuff >> ( m_bsLive - 1 ) ) & 1;
+                        m_bsLive--;
+                        zvec = ( zvec << 1 ) | zj;
+                    }
+
+                    nextSym = m_perm[ zt ][ zvec - m_base[ zt ][ zn ] ];
+
+                } while( nextSym == RUNA || nextSym == RUNB );
+
+                s++;
+                ch = m_seqToUnseq[ yy[ 0 ] ];
+                m_unzftab[ ch ] += s;
+
+                while( s > 0 )
+                {
+                    m_last++;
+                    m_ll8[ m_last ] = ch;
+                    s--;
+                }
+
+                if( m_last >= limitLast )
+                {
+                    blockOverrun();
+                }
+                continue;
+            }
+            else
+            {
+                char tmp;
+                m_last++;
+                if( m_last >= limitLast )
+                {
+                    blockOverrun();
+                }
+
+                tmp = yy[ nextSym - 1 ];
+                m_unzftab[ m_seqToUnseq[ tmp ] ]++;
+                m_ll8[ m_last ] = m_seqToUnseq[ tmp ];
+
+                /*
+                 * This loop is hammered during decompression,
+                 * hence the unrolling.
+                 * for (j = nextSym-1; j > 0; j--) yy[j] = yy[j-1];
+                 */
+                int j = nextSym - 1;
+                for( ; j > 3; j -= 4 )
+                {
+                    yy[ j ] = yy[ j - 1 ];
+                    yy[ j - 1 ] = yy[ j - 2 ];
+                    yy[ j - 2 ] = yy[ j - 3 ];
+                    yy[ j - 3 ] = yy[ j - 4 ];
+                }
+                for( ; j > 0; j-- )
+                {
+                    yy[ j ] = yy[ j - 1 ];
+                }
+
+                yy[ 0 ] = tmp;
+
+                if( groupPos == 0 )
+                {
+                    groupNo++;
+                    groupPos = G_SIZE;
+                }
+                groupPos--;
+                zt = m_selector[ groupNo ];
+                zn = m_minLens[ zt ];
+                zvec = bsR( zn );
+                while( zvec > m_limit[ zt ][ zn ] )
+                {
+                    zn++;
+
+                    while( m_bsLive < 1 )
+                    {
+                        char ch = 0;
+                        try
+                        {
+                            ch = (char)m_input.read();
+                        }
+                        catch( IOException e )
+                        {
+                            compressedStreamEOF();
+                        }
+
+                        m_bsBuff = ( m_bsBuff << 8 ) | ( ch & 0xff );
+                        m_bsLive += 8;
+                    }
+
+                    zj = ( m_bsBuff >> ( m_bsLive - 1 ) ) & 1;
+                    m_bsLive--;
+
+                    zvec = ( zvec << 1 ) | zj;
+                }
+                nextSym = m_perm[ zt ][ zvec - m_base[ zt ][ zn ] ];
+
+                continue;
+            }
+        }
+    }
+
+    private void bsFinishedWithStream()
+    {
+        if (m_input != null)
+        {
+            try
+            {
+                m_input.close();
+            }
+            catch ( IOException e )
+            {
+            }
+        }
+        m_input = null;
+    }
+
+    private int readVariableSizedInt( final int numBits )
+    {
+        return bsR( numBits );
+    }
+
+    private char readUnsignedChar()
+    {
+        return (char)bsR( 8 );
+    }
+
+    private int readInt()
+    {
+        int u = 0;
+        u = ( u << 8 ) | bsR( 8 );
+        u = ( u << 8 ) | bsR( 8 );
+        u = ( u << 8 ) | bsR( 8 );
+        u = ( u << 8 ) | bsR( 8 );
+        return u;
+    }
+
+    private int bsR( final int n )
+    {
+        while( m_bsLive < n )
+        {
+            char ch = 0;
+            try
+            {
+                ch = (char)m_input.read();
+            }
+            catch( final IOException ioe )
+            {
+                compressedStreamEOF();
+            }
+
+            if( ch == -1 )
+            {
+                compressedStreamEOF();
+            }
+
+            m_bsBuff = ( m_bsBuff << 8 ) | ( ch & 0xff );
+            m_bsLive += 8;
+        }
+
+        final int result = ( m_bsBuff >> ( m_bsLive - n ) ) & ( ( 1 << n ) - 1 );
+        m_bsLive -= n;
+        return result;
+    }
+
+    private void bsSetStream( final InputStream input )
+    {
+        m_input = input;
+        m_bsLive = 0;
+        m_bsBuff = 0;
+    }
+
+    private void complete()
+    {
+        m_storedCombinedCRC = readInt();
+        if( m_storedCombinedCRC != m_computedCombinedCRC )
+        {
+            crcError();
+        }
+
+        bsFinishedWithStream();
+        m_streamEnd = true;
+    }
+
+    private void endBlock()
+    {
+        m_computedBlockCRC = m_crc.getFinalCRC();
+        /*
+         * A bad CRC is considered a fatal error.
+         */
+        if( m_storedBlockCRC != m_computedBlockCRC )
+        {
+            crcError();
+        }
+
+        m_computedCombinedCRC = ( m_computedCombinedCRC << 1 )
+            | ( m_computedCombinedCRC >>> 31 );
+        m_computedCombinedCRC ^= m_computedBlockCRC;
+    }
+
+    private void hbCreateDecodeTables( final int[] limit,
+                                       final int[] base,
+                                       final int[] perm,
+                                       final char[] length,
+                                       final int minLen,
+                                       final int maxLen,
+                                       final int alphaSize )
+    {
+        int pp = 0;
+        for( int i = minLen; i <= maxLen; i++ )
+        {
+            for( int j = 0; j < alphaSize; j++ )
+            {
+                if( length[ j ] == i )
+                {
+                    perm[ pp ] = j;
+                    pp++;
+                }
+            }
+        }
+
+        for( int i = 0; i < MAX_CODE_LEN; i++ )
+        {
+            base[ i ] = 0;
+        }
+
+        for( int i = 0; i < alphaSize; i++ )
+        {
+            base[ length[ i ] + 1 ]++;
+        }
+
+        for( int i = 1; i < MAX_CODE_LEN; i++ )
+        {
+            base[ i ] += base[ i - 1 ];
+        }
+
+        for( int i = 0; i < MAX_CODE_LEN; i++ )
+        {
+            limit[ i ] = 0;
+        }
+
+        int vec = 0;
+        for( int i = minLen; i <= maxLen; i++ )
+        {
+            vec += ( base[ i + 1 ] - base[ i ] );
+            limit[ i ] = vec - 1;
+            vec <<= 1;
+        }
+
+        for( int i = minLen + 1; i <= maxLen; i++ )
+        {
+            base[ i ] = ( ( limit[ i - 1 ] + 1 ) << 1 ) - base[ i ];
+        }
+    }
+
+    private void initBlock()
+    {
+        final char magic1 = readUnsignedChar();
+        final char magic2 = readUnsignedChar();
+        final char magic3 = readUnsignedChar();
+        final char magic4 = readUnsignedChar();
+        final char magic5 = readUnsignedChar();
+        final char magic6 = readUnsignedChar();
+        if( magic1 == 0x17 && magic2 == 0x72 && magic3 == 0x45 &&
+            magic4 == 0x38 && magic5 == 0x50 && magic6 == 0x90 )
+        {
+            complete();
+            return;
+        }
+
+        if( magic1 != 0x31 || magic2 != 0x41 || magic3 != 0x59 ||
+            magic4 != 0x26 || magic5 != 0x53 || magic6 != 0x59 )
+        {
+            badBlockHeader();
+            m_streamEnd = true;
+            return;
+        }
+
+        m_storedBlockCRC = readInt();
+
+        if( bsR( 1 ) == 1 )
+        {
+            m_blockRandomised = true;
+        }
+        else
+        {
+            m_blockRandomised = false;
+        }
+
+        //        currBlockNo++;
+        getAndMoveToFrontDecode();
+
+        m_crc.initialiseCRC();
+        m_currentState = START_BLOCK_STATE;
+    }
+
+    private void initialize()
+    {
+        final char magic3 = readUnsignedChar();
+        final char magic4 = readUnsignedChar();
+        if( magic3 != 'h' || magic4 < '1' || magic4 > '9' )
+        {
+            bsFinishedWithStream();
+            m_streamEnd = true;
+            return;
+        }
+
+        setDecompressStructureSizes( magic4 - '0' );
+        m_computedCombinedCRC = 0;
+    }
+
+    private void makeMaps()
+    {
+        m_nInUse = 0;
+        for( int i = 0; i < 256; i++ )
+        {
+            if( m_inUse[ i ] )
+            {
+                m_seqToUnseq[ m_nInUse ] = (char)i;
+                m_unseqToSeq[ i ] = (char)m_nInUse;
+                m_nInUse++;
+            }
+        }
+    }
+
+    private void recvDecodingTables()
+    {
+        buildInUseTable();
+        makeMaps();
+        final int alphaSize = m_nInUse + 2;
+
+        /*
+         * Now the selectors
+         */
+        final int groupCount = bsR( 3 );
+        final int selectorCount = bsR( 15 );
+        for( int i = 0; i < selectorCount; i++ )
+        {
+            int run = 0;
+            while( bsR( 1 ) == 1 )
+            {
+                run++;
+            }
+            m_selectorMtf[ i ] = (char)run;
+        }
+
+        /*
+         * Undo the MTF values for the selectors.
+         */
+        final char[] pos = new char[ N_GROUPS ];
+        for( char v = 0; v < groupCount; v++ )
+        {
+            pos[ v ] = v;
+        }
+
+        for( int i = 0; i < selectorCount; i++ )
+        {
+            int v = m_selectorMtf[ i ];
+            final char tmp = pos[ v ];
+            while( v > 0 )
+            {
+                pos[ v ] = pos[ v - 1 ];
+                v--;
+            }
+            pos[ 0 ] = tmp;
+            m_selector[ i ] = tmp;
+        }
+
+        final char[][] len = new char[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+        /*
+         * Now the coding tables
+         */
+        for( int i = 0; i < groupCount; i++ )
+        {
+            int curr = bsR( 5 );
+            for( int j = 0; j < alphaSize; j++ )
+            {
+                while( bsR( 1 ) == 1 )
+                {
+                    if( bsR( 1 ) == 0 )
+                    {
+                        curr++;
+                    }
+                    else
+                    {
+                        curr--;
+                    }
+                }
+                len[ i ][ j ] = (char)curr;
+            }
+        }
+
+        /*
+         * Create the Huffman decoding tables
+         */
+        for( int k = 0; k < groupCount; k++ )
+        {
+            int minLen = 32;
+            int maxLen = 0;
+            for( int i = 0; i < alphaSize; i++ )
+            {
+                if( len[ k ][ i ] > maxLen )
+                {
+                    maxLen = len[ k ][ i ];
+                }
+                if( len[ k ][ i ] < minLen )
+                {
+                    minLen = len[ k ][ i ];
+                }
+            }
+            hbCreateDecodeTables( m_limit[ k ], m_base[ k ], m_perm[ k ], len[ k ], minLen,
+                                  maxLen, alphaSize );
+            m_minLens[ k ] = minLen;
+        }
+    }
+
+    private void buildInUseTable()
+    {
+        final boolean[] inUse16 = new boolean[ 16 ];
+
+        /*
+         * Receive the mapping table
+         */
+        for( int i = 0; i < 16; i++ )
+        {
+            if( bsR( 1 ) == 1 )
+            {
+                inUse16[ i ] = true;
+            }
+            else
+            {
+                inUse16[ i ] = false;
+            }
+        }
+
+        for( int i = 0; i < 256; i++ )
+        {
+            m_inUse[ i ] = false;
+        }
+
+        for( int i = 0; i < 16; i++ )
+        {
+            if( inUse16[ i ] )
+            {
+                for( int j = 0; j < 16; j++ )
+                {
+                    if( bsR( 1 ) == 1 )
+                    {
+                        m_inUse[ i * 16 + j ] = true;
+                    }
+                }
+            }
+        }
+    }
+    
+    /* (non-Javadoc)
+     * @see java.io.InputStream#close()
+     */
+    public void close() throws IOException 
+    {
+    	bsFinishedWithStream();
+    }
+}

Propchange: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java
------------------------------------------------------------------------------
    svn:executable = *

Propchange: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2InputStream.java
------------------------------------------------------------------------------
    svn:keywords = "Author Date Id Revision"

Added: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java
URL: http://svn.apache.org/viewvc/jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java?rev=427072&view=auto
==============================================================================
--- jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java (added)
+++ jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java Mon Jul 31 03:55:10 2006
@@ -0,0 +1,2036 @@
+/*
+ * Copyright 2002,2004 The Apache Software Foundation.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.compress.compressors.bzip2;
+
+import java.io.IOException;
+import java.io.OutputStream;
+/*
+ * This package is based on the work done by Keiron Liddle, Aftex Software
+ * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
+ * great code.
+ */
+/**
+ * An output stream that compresses into the BZip2 format (without the file
+ * header chars) into another stream. TODO: Update to BZip2 1.0.1
+ *
+ * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
+ */
+public class BZip2OutputStream
+    extends OutputStream
+    implements BZip2Constants
+{
+    private static final int LOWER_BYTE_MASK = 0x000000ff;
+    private static final int UPPER_BYTE_MASK = 0xffffff00;
+    private static final int SETMASK = ( 1 << 21 );
+    private static final int CLEARMASK = ( ~SETMASK );
+    private static final int GREATER_ICOST = 15;
+    private static final int LESSER_ICOST = 0;
+    private static final int SMALL_THRESH = 20;
+    private static final int DEPTH_THRESH = 10;
+
+    /*
+     * If you are ever unlucky/improbable enough
+     * to get a stack overflow whilst sorting,
+     * increase the following constant and try
+     * again.  In practice I have never seen the
+     * stack go above 27 elems, so the following
+     * limit seems very generous.
+     */
+    private static final int QSORT_STACK_SIZE = 1000;
+
+    private CRC m_crc = new CRC();
+
+    private boolean[] m_inUse = new boolean[ 256 ];
+
+    private char[] m_seqToUnseq = new char[ 256 ];
+    private char[] m_unseqToSeq = new char[ 256 ];
+
+    private char[] m_selector = new char[ MAX_SELECTORS ];
+    private char[] m_selectorMtf = new char[ MAX_SELECTORS ];
+
+    private int[] m_mtfFreq = new int[ MAX_ALPHA_SIZE ];
+
+    private int m_currentChar = -1;
+    private int m_runLength;
+
+    private boolean m_closed;
+
+    /*
+     * Knuth's increments seem to work better
+     * than Incerpi-Sedgewick here.  Possibly
+     * because the number of elems to sort is
+     * usually small, typically <= 20.
+     */
+    private int[] m_incs = new int[]
+    {
+        1, 4, 13, 40, 121, 364, 1093, 3280,
+        9841, 29524, 88573, 265720,
+        797161, 2391484
+    };
+
+    private boolean m_blockRandomised;
+
+    /*
+     * always: in the range 0 .. 9.
+     * The current block size is 100000 * this number.
+     */
+    private int m_blockSize100k;
+    private int m_bsBuff;
+    private int m_bsLive;
+
+    /*
+     * index of the last char in the block, so
+     * the block size == last + 1.
+     */
+    private int m_last;
+
+    /*
+     * index in zptr[] of original string after sorting.
+     */
+    private int m_origPtr;
+
+    private int m_allowableBlockSize;
+
+    private char[] m_block;
+
+    private int m_blockCRC;
+    private int m_combinedCRC;
+
+    private OutputStream m_bsStream;
+    private boolean m_firstAttempt;
+    private int[] m_ftab;
+    private int m_nInUse;
+
+    private int m_nMTF;
+    private int[] m_quadrant;
+    private short[] m_szptr;
+    private int m_workDone;
+
+    /*
+     * Used when sorting.  If too many long comparisons
+     * happen, we stop sorting, randomise the block
+     * slightly, and try again.
+     */
+    private int m_workFactor;
+    private int m_workLimit;
+    private int[] m_zptr;
+
+    public BZip2OutputStream( final OutputStream output )
+        throws IOException
+    {
+        this( output, 9 );
+    }
+
+    public BZip2OutputStream( final OutputStream output, final int blockSize )
+        throws IOException
+    {
+        bsSetStream( output );
+        m_workFactor = 50;
+
+        int outBlockSize = blockSize;
+        if( outBlockSize > 9 )
+        {
+            outBlockSize = 9;
+        }
+        if( outBlockSize < 1 )
+        {
+            outBlockSize = 1;
+        }
+        m_blockSize100k = outBlockSize;
+        allocateCompressStructures();
+        initialize();
+        initBlock();
+    }
+
+    private static void hbMakeCodeLengths( char[] len, int[] freq,
+                                           int alphaSize, int maxLen )
+    {
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int nNodes;
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int nHeap;
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int n1;
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int n2;
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int i;
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int j;
+        /*
+         * Nodes and heap entries run from 1.  Entry 0
+         * for both the heap and nodes is a sentinel.
+         */
+        int k;
+        boolean tooLong;
+
+        int[] heap = new int[ MAX_ALPHA_SIZE + 2 ];
+        int[] weights = new int[ MAX_ALPHA_SIZE * 2 ];
+        int[] parent = new int[ MAX_ALPHA_SIZE * 2 ];
+
+        for( i = 0; i < alphaSize; i++ )
+        {
+            weights[ i + 1 ] = ( freq[ i ] == 0 ? 1 : freq[ i ] ) << 8;
+        }
+
+        while( true )
+        {
+            nNodes = alphaSize;
+            nHeap = 0;
+
+            heap[ 0 ] = 0;
+            weights[ 0 ] = 0;
+            parent[ 0 ] = -2;
+
+            for( i = 1; i <= alphaSize; i++ )
+            {
+                parent[ i ] = -1;
+                nHeap++;
+                heap[ nHeap ] = i;
+                {
+                    int zz;
+                    int tmp;
+                    zz = nHeap;
+                    tmp = heap[ zz ];
+                    while( weights[ tmp ] < weights[ heap[ zz >> 1 ] ] )
+                    {
+                        heap[ zz ] = heap[ zz >> 1 ];
+                        zz >>= 1;
+                    }
+                    heap[ zz ] = tmp;
+                }
+            }
+            if( !( nHeap < ( MAX_ALPHA_SIZE + 2 ) ) )
+            {
+                panic();
+            }
+
+            while( nHeap > 1 )
+            {
+                n1 = heap[ 1 ];
+                heap[ 1 ] = heap[ nHeap ];
+                nHeap--;
+                {
+                    int zz = 0;
+                    int yy = 0;
+                    int tmp = 0;
+                    zz = 1;
+                    tmp = heap[ zz ];
+                    while( true )
+                    {
+                        yy = zz << 1;
+                        if( yy > nHeap )
+                        {
+                            break;
+                        }
+                        if( yy < nHeap &&
+                            weights[ heap[ yy + 1 ] ] < weights[ heap[ yy ] ] )
+                        {
+                            yy++;
+                        }
+                        if( weights[ tmp ] < weights[ heap[ yy ] ] )
+                        {
+                            break;
+                        }
+                        heap[ zz ] = heap[ yy ];
+                        zz = yy;
+                    }
+                    heap[ zz ] = tmp;
+                }
+                n2 = heap[ 1 ];
+                heap[ 1 ] = heap[ nHeap ];
+                nHeap--;
+                {
+                    int zz = 0;
+                    int yy = 0;
+                    int tmp = 0;
+                    zz = 1;
+                    tmp = heap[ zz ];
+                    while( true )
+                    {
+                        yy = zz << 1;
+                        if( yy > nHeap )
+                        {
+                            break;
+                        }
+                        if( yy < nHeap &&
+                            weights[ heap[ yy + 1 ] ] < weights[ heap[ yy ] ] )
+                        {
+                            yy++;
+                        }
+                        if( weights[ tmp ] < weights[ heap[ yy ] ] )
+                        {
+                            break;
+                        }
+                        heap[ zz ] = heap[ yy ];
+                        zz = yy;
+                    }
+                    heap[ zz ] = tmp;
+                }
+                nNodes++;
+                parent[ n1 ] = nNodes;
+                parent[ n2 ] = nNodes;
+
+                final int v1 = weights[ n1 ];
+                final int v2 = weights[ n2 ];
+                final int weight = calculateWeight( v1, v2 );
+                weights[ nNodes ] = weight;
+
+                parent[ nNodes ] = -1;
+                nHeap++;
+                heap[ nHeap ] = nNodes;
+                {
+                    int zz = 0;
+                    int tmp = 0;
+                    zz = nHeap;
+                    tmp = heap[ zz ];
+                    while( weights[ tmp ] < weights[ heap[ zz >> 1 ] ] )
+                    {
+                        heap[ zz ] = heap[ zz >> 1 ];
+                        zz >>= 1;
+                    }
+                    heap[ zz ] = tmp;
+                }
+            }
+            if( !( nNodes < ( MAX_ALPHA_SIZE * 2 ) ) )
+            {
+                panic();
+            }
+
+            tooLong = false;
+            for( i = 1; i <= alphaSize; i++ )
+            {
+                j = 0;
+                k = i;
+                while( parent[ k ] >= 0 )
+                {
+                    k = parent[ k ];
+                    j++;
+                }
+                len[ i - 1 ] = (char)j;
+                if( j > maxLen )
+                {
+                    tooLong = true;
+                }
+            }
+
+            if( !tooLong )
+            {
+                break;
+            }
+
+            for( i = 1; i < alphaSize; i++ )
+            {
+                j = weights[ i ] >> 8;
+                j = 1 + ( j / 2 );
+                weights[ i ] = j << 8;
+            }
+        }
+    }
+
+    private static int calculateWeight( final int v1, final int v2 )
+    {
+        final int upper = ( v1 & UPPER_BYTE_MASK ) + ( v2 & UPPER_BYTE_MASK );
+        final int v1Lower = ( v1 & LOWER_BYTE_MASK );
+        final int v2Lower = ( v2 & LOWER_BYTE_MASK );
+        final int nnnn = ( v1Lower > v2Lower ) ? v1Lower : v2Lower;
+        return upper | ( 1 + nnnn );
+    }
+
+    private static void panic()
+    {
+        System.out.println( "panic" );
+        //throw new CError();
+    }
+
+    public void close()
+        throws IOException
+    {
+        if( m_closed )
+        {
+            return;
+        }
+
+        if( m_runLength > 0 )
+        {
+            writeRun();
+        }
+        m_currentChar = -1;
+        endBlock();
+        endCompression();
+        m_closed = true;
+        super.close();
+        m_bsStream.close();
+    }
+
+    public void finalize()
+        throws Throwable
+    {
+        close();
+    }
+
+    public void flush()
+        throws IOException
+    {
+        super.flush();
+        m_bsStream.flush();
+    }
+
+    /**
+     * modified by Oliver Merkel, 010128
+     *
+     * @param bv Description of Parameter
+     * @exception java.io.IOException Description of Exception
+     */
+    /* (non-Javadoc)
+     * @see java.io.OutputStream#write(int)
+     */
+    public void write( int bv )
+        throws IOException
+    {
+        int b = ( 256 + bv ) % 256;
+        if( m_currentChar != -1 )
+        {
+            if( m_currentChar == b )
+            {
+                m_runLength++;
+                if( m_runLength > 254 )
+                {
+                    writeRun();
+                    m_currentChar = -1;
+                    m_runLength = 0;
+                }
+            }
+            else
+            {
+                writeRun();
+                m_runLength = 1;
+                m_currentChar = b;
+            }
+        }
+        else
+        {
+            m_currentChar = b;
+            m_runLength++;
+        }
+    }
+
+    private void allocateCompressStructures()
+    {
+        int n = BASE_BLOCK_SIZE * m_blockSize100k;
+        m_block = new char[ ( n + 1 + NUM_OVERSHOOT_BYTES ) ];
+        m_quadrant = new int[ ( n + NUM_OVERSHOOT_BYTES ) ];
+        m_zptr = new int[ n ];
+        m_ftab = new int[ 65537 ];
+
+        if( m_block == null || m_quadrant == null || m_zptr == null
+            || m_ftab == null )
+        {
+            //int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
+            //compressOutOfMemory ( totalDraw, n );
+        }
+
+        /*
+         * The back end needs a place to store the MTF values
+         * whilst it calculates the coding tables.  We could
+         * put them in the zptr array.  However, these values
+         * will fit in a short, so we overlay szptr at the
+         * start of zptr, in the hope of reducing the number
+         * of cache misses induced by the multiple traversals
+         * of the MTF values when calculating coding tables.
+         * Seems to improve compression speed by about 1%.
+         */
+        //    szptr = zptr;
+
+        m_szptr = new short[ 2 * n ];
+    }
+
+    private void bsFinishedWithStream()
+        throws IOException
+    {
+        while( m_bsLive > 0 )
+        {
+            int ch = ( m_bsBuff >> 24 );
+            try
+            {
+                m_bsStream.write( ch );// write 8-bit
+            }
+            catch( IOException e )
+            {
+                throw e;
+            }
+            m_bsBuff <<= 8;
+            m_bsLive -= 8;
+        }
+    }
+
+    private void bsPutIntVS( int numBits, int c )
+        throws IOException
+    {
+        bsW( numBits, c );
+    }
+
+    private void bsPutUChar( int c )
+        throws IOException
+    {
+        bsW( 8, c );
+    }
+
+    private void bsPutint( int u )
+        throws IOException
+    {
+        bsW( 8, ( u >> 24 ) & 0xff );
+        bsW( 8, ( u >> 16 ) & 0xff );
+        bsW( 8, ( u >> 8 ) & 0xff );
+        bsW( 8, u & 0xff );
+    }
+
+    private void bsSetStream( OutputStream f )
+    {
+        m_bsStream = f;
+        m_bsLive = 0;
+        m_bsBuff = 0;
+    }
+
+    private void bsW( int n, int v )
+        throws IOException
+    {
+        while( m_bsLive >= 8 )
+        {
+            int ch = ( m_bsBuff >> 24 );
+            try
+            {
+                m_bsStream.write( ch );// write 8-bit
+            }
+            catch( IOException e )
+            {
+                throw e;
+            }
+            m_bsBuff <<= 8;
+            m_bsLive -= 8;
+        }
+        m_bsBuff |= ( v << ( 32 - m_bsLive - n ) );
+        m_bsLive += n;
+    }
+
+    private void doReversibleTransformation()
+    {
+        int i;
+
+        m_workLimit = m_workFactor * m_last;
+        m_workDone = 0;
+        m_blockRandomised = false;
+        m_firstAttempt = true;
+
+        mainSort();
+
+        if( m_workDone > m_workLimit && m_firstAttempt )
+        {
+            randomiseBlock();
+            m_workLimit = 0;
+            m_workDone = 0;
+            m_blockRandomised = true;
+            m_firstAttempt = false;
+            mainSort();
+        }
+
+        m_origPtr = -1;
+        for( i = 0; i <= m_last; i++ )
+        {
+            if( m_zptr[ i ] == 0 )
+            {
+                m_origPtr = i;
+                break;
+            }
+        }
+        ;
+
+        if( m_origPtr == -1 )
+        {
+            panic();
+        }
+    }
+
+    private void endBlock()
+        throws IOException
+    {
+        m_blockCRC = m_crc.getFinalCRC();
+        m_combinedCRC = ( m_combinedCRC << 1 ) | ( m_combinedCRC >>> 31 );
+        m_combinedCRC ^= m_blockCRC;
+
+        /*
+         * sort the block and establish posn of original string
+         */
+        doReversibleTransformation();
+
+        /*
+         * A 6-byte block header, the value chosen arbitrarily
+         * as 0x314159265359 :-).  A 32 bit value does not really
+         * give a strong enough guarantee that the value will not
+         * appear by chance in the compressed datastream.  Worst-case
+         * probability of this event, for a 900k block, is about
+         * 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
+         * For a compressed file of size 100Gb -- about 100000 blocks --
+         * only a 48-bit marker will do.  NB: normal compression/
+         * decompression do *not* rely on these statistical properties.
+         * They are only important when trying to recover blocks from
+         * damaged files.
+         */
+        bsPutUChar( 0x31 );
+        bsPutUChar( 0x41 );
+        bsPutUChar( 0x59 );
+        bsPutUChar( 0x26 );
+        bsPutUChar( 0x53 );
+        bsPutUChar( 0x59 );
+
+        /*
+         * Now the block's CRC, so it is in a known place.
+         */
+        bsPutint( m_blockCRC );
+
+        /*
+         * Now a single bit indicating randomisation.
+         */
+        if( m_blockRandomised )
+        {
+            bsW( 1, 1 );
+        }
+        else
+        {
+            bsW( 1, 0 );
+        }
+
+        /*
+         * Finally, block's contents proper.
+         */
+        moveToFrontCodeAndSend();
+    }
+
+    private void endCompression()
+        throws IOException
+    {
+        /*
+         * Now another magic 48-bit number, 0x177245385090, to
+         * indicate the end of the last block.  (sqrt(pi), if
+         * you want to know.  I did want to use e, but it contains
+         * too much repetition -- 27 18 28 18 28 46 -- for me
+         * to feel statistically comfortable.  Call me paranoid.)
+         */
+        bsPutUChar( 0x17 );
+        bsPutUChar( 0x72 );
+        bsPutUChar( 0x45 );
+        bsPutUChar( 0x38 );
+        bsPutUChar( 0x50 );
+        bsPutUChar( 0x90 );
+
+        bsPutint( m_combinedCRC );
+
+        bsFinishedWithStream();
+    }
+
+    private boolean fullGtU( int i1, int i2 )
+    {
+        int k;
+        char c1;
+        char c2;
+        int s1;
+        int s2;
+
+        c1 = m_block[ i1 + 1 ];
+        c2 = m_block[ i2 + 1 ];
+        if( c1 != c2 )
+        {
+            return ( c1 > c2 );
+        }
+        i1++;
+        i2++;
+
+        c1 = m_block[ i1 + 1 ];
+        c2 = m_block[ i2 + 1 ];
+        if( c1 != c2 )
+        {
+            return ( c1 > c2 );
+        }
+        i1++;
+        i2++;
+
+        c1 = m_block[ i1 + 1 ];
+        c2 = m_block[ i2 + 1 ];
+        if( c1 != c2 )
+        {
+            return ( c1 > c2 );
+        }
+        i1++;
+        i2++;
+
+        c1 = m_block[ i1 + 1 ];
+        c2 = m_block[ i2 + 1 ];
+        if( c1 != c2 )
+        {
+            return ( c1 > c2 );
+        }
+        i1++;
+        i2++;
+
+        c1 = m_block[ i1 + 1 ];
+        c2 = m_block[ i2 + 1 ];
+        if( c1 != c2 )
+        {
+            return ( c1 > c2 );
+        }
+        i1++;
+        i2++;
+
+        c1 = m_block[ i1 + 1 ];
+        c2 = m_block[ i2 + 1 ];
+        if( c1 != c2 )
+        {
+            return ( c1 > c2 );
+        }
+        i1++;
+        i2++;
+
+        k = m_last + 1;
+
+        do
+        {
+            c1 = m_block[ i1 + 1 ];
+            c2 = m_block[ i2 + 1 ];
+            if( c1 != c2 )
+            {
+                return ( c1 > c2 );
+            }
+            s1 = m_quadrant[ i1 ];
+            s2 = m_quadrant[ i2 ];
+            if( s1 != s2 )
+            {
+                return ( s1 > s2 );
+            }
+            i1++;
+            i2++;
+
+            c1 = m_block[ i1 + 1 ];
+            c2 = m_block[ i2 + 1 ];
+            if( c1 != c2 )
+            {
+                return ( c1 > c2 );
+            }
+            s1 = m_quadrant[ i1 ];
+            s2 = m_quadrant[ i2 ];
+            if( s1 != s2 )
+            {
+                return ( s1 > s2 );
+            }
+            i1++;
+            i2++;
+
+            c1 = m_block[ i1 + 1 ];
+            c2 = m_block[ i2 + 1 ];
+            if( c1 != c2 )
+            {
+                return ( c1 > c2 );
+            }
+            s1 = m_quadrant[ i1 ];
+            s2 = m_quadrant[ i2 ];
+            if( s1 != s2 )
+            {
+                return ( s1 > s2 );
+            }
+            i1++;
+            i2++;
+
+            c1 = m_block[ i1 + 1 ];
+            c2 = m_block[ i2 + 1 ];
+            if( c1 != c2 )
+            {
+                return ( c1 > c2 );
+            }
+            s1 = m_quadrant[ i1 ];
+            s2 = m_quadrant[ i2 ];
+            if( s1 != s2 )
+            {
+                return ( s1 > s2 );
+            }
+            i1++;
+            i2++;
+
+            if( i1 > m_last )
+            {
+                i1 -= m_last;
+                i1--;
+            }
+            ;
+            if( i2 > m_last )
+            {
+                i2 -= m_last;
+                i2--;
+            }
+            ;
+
+            k -= 4;
+            m_workDone++;
+        } while( k >= 0 );
+
+        return false;
+    }
+
+    private void generateMTFValues()
+    {
+        char[] yy = new char[ 256 ];
+        int i;
+        int j;
+        char tmp;
+        char tmp2;
+        int zPend;
+        int wr;
+        int EOB;
+
+        makeMaps();
+        EOB = m_nInUse + 1;
+
+        for( i = 0; i <= EOB; i++ )
+        {
+            m_mtfFreq[ i ] = 0;
+        }
+
+        wr = 0;
+        zPend = 0;
+        for( i = 0; i < m_nInUse; i++ )
+        {
+            yy[ i ] = (char)i;
+        }
+
+        for( i = 0; i <= m_last; i++ )
+        {
+            char ll_i;
+
+            ll_i = m_unseqToSeq[ m_block[ m_zptr[ i ] ] ];
+
+            j = 0;
+            tmp = yy[ j ];
+            while( ll_i != tmp )
+            {
+                j++;
+                tmp2 = tmp;
+                tmp = yy[ j ];
+                yy[ j ] = tmp2;
+            }
+            ;
+            yy[ 0 ] = tmp;
+
+            if( j == 0 )
+            {
+                zPend++;
+            }
+            else
+            {
+                if( zPend > 0 )
+                {
+                    zPend--;
+                    while( true )
+                    {
+                        switch( zPend % 2 )
+                        {
+                            case 0:
+                                m_szptr[ wr ] = (short)RUNA;
+                                wr++;
+                                m_mtfFreq[ RUNA ]++;
+                                break;
+                            case 1:
+                                m_szptr[ wr ] = (short)RUNB;
+                                wr++;
+                                m_mtfFreq[ RUNB ]++;
+                                break;
+                        }
+                        ;
+                        if( zPend < 2 )
+                        {
+                            break;
+                        }
+                        zPend = ( zPend - 2 ) / 2;
+                    }
+                    ;
+                    zPend = 0;
+                }
+                m_szptr[ wr ] = (short)( j + 1 );
+                wr++;
+                m_mtfFreq[ j + 1 ]++;
+            }
+        }
+
+        if( zPend > 0 )
+        {
+            zPend--;
+            while( true )
+            {
+                switch( zPend % 2 )
+                {
+                    case 0:
+                        m_szptr[ wr ] = (short)RUNA;
+                        wr++;
+                        m_mtfFreq[ RUNA ]++;
+                        break;
+                    case 1:
+                        m_szptr[ wr ] = (short)RUNB;
+                        wr++;
+                        m_mtfFreq[ RUNB ]++;
+                        break;
+                }
+                if( zPend < 2 )
+                {
+                    break;
+                }
+                zPend = ( zPend - 2 ) / 2;
+            }
+        }
+
+        m_szptr[ wr ] = (short)EOB;
+        wr++;
+        m_mtfFreq[ EOB ]++;
+
+        m_nMTF = wr;
+    }
+
+    private void hbAssignCodes( int[] code, char[] length, int minLen,
+                                int maxLen, int alphaSize )
+    {
+        int n;
+        int vec;
+        int i;
+
+        vec = 0;
+        for( n = minLen; n <= maxLen; n++ )
+        {
+            for( i = 0; i < alphaSize; i++ )
+            {
+                if( length[ i ] == n )
+                {
+                    code[ i ] = vec;
+                    vec++;
+                }
+            }
+            ;
+            vec <<= 1;
+        }
+    }
+
+    private void initBlock()
+    {
+        //        blockNo++;
+        m_crc.initialiseCRC();
+        m_last = -1;
+        //        ch = 0;
+
+        for( int i = 0; i < 256; i++ )
+        {
+            m_inUse[ i ] = false;
+        }
+
+        /*
+         * 20 is just a paranoia constant
+         */
+        m_allowableBlockSize = BASE_BLOCK_SIZE * m_blockSize100k - 20;
+    }
+
+    private void initialize()
+        throws IOException
+    {
+        /*
+         * Write `magic' bytes h indicating file-format == huffmanised,
+         * followed by a digit indicating blockSize100k.
+         */
+        bsPutUChar( 'h' );
+        bsPutUChar( '0' + m_blockSize100k );
+
+        m_combinedCRC = 0;
+    }
+
+    private void mainSort()
+    {
+        int i;
+        int j;
+        int ss;
+        int sb;
+        int[] runningOrder = new int[ 256 ];
+        int[] copy = new int[ 256 ];
+        boolean[] bigDone = new boolean[ 256 ];
+        int c1;
+        int c2;
+
+        /*
+         * In the various block-sized structures, live data runs
+         * from 0 to last+NUM_OVERSHOOT_BYTES inclusive.  First,
+         * set up the overshoot area for block.
+         */
+        //   if (verbosity >= 4) fprintf ( stderr, "        sort initialise ...\n" );
+        for( i = 0; i < NUM_OVERSHOOT_BYTES; i++ )
+        {
+            m_block[ m_last + i + 2 ] = m_block[ ( i % ( m_last + 1 ) ) + 1 ];
+        }
+        for( i = 0; i <= m_last + NUM_OVERSHOOT_BYTES; i++ )
+        {
+            m_quadrant[ i ] = 0;
+        }
+
+        m_block[ 0 ] = m_block[ m_last + 1 ];
+
+        if( m_last < 4000 )
+        {
+            /*
+             * Use simpleSort(), since the full sorting mechanism
+             * has quite a large constant overhead.
+             */
+            for( i = 0; i <= m_last; i++ )
+            {
+                m_zptr[ i ] = i;
+            }
+            m_firstAttempt = false;
+            m_workDone = 0;
+            m_workLimit = 0;
+            simpleSort( 0, m_last, 0 );
+        }
+        else
+        {
+            for( i = 0; i <= 255; i++ )
+            {
+                bigDone[ i ] = false;
+            }
+
+            for( i = 0; i <= 65536; i++ )
+            {
+                m_ftab[ i ] = 0;
+            }
+
+            c1 = m_block[ 0 ];
+            for( i = 0; i <= m_last; i++ )
+            {
+                c2 = m_block[ i + 1 ];
+                m_ftab[ ( c1 << 8 ) + c2 ]++;
+                c1 = c2;
+            }
+
+            for( i = 1; i <= 65536; i++ )
+            {
+                m_ftab[ i ] += m_ftab[ i - 1 ];
+            }
+
+            c1 = m_block[ 1 ];
+            for( i = 0; i < m_last; i++ )
+            {
+                c2 = m_block[ i + 2 ];
+                j = ( c1 << 8 ) + c2;
+                c1 = c2;
+                m_ftab[ j ]--;
+                m_zptr[ m_ftab[ j ] ] = i;
+            }
+
+            j = ( ( m_block[ m_last + 1 ] ) << 8 ) + ( m_block[ 1 ] );
+            m_ftab[ j ]--;
+            m_zptr[ m_ftab[ j ] ] = m_last;
+
+            /*
+             * Now ftab contains the first loc of every small bucket.
+             * Calculate the running order, from smallest to largest
+             * big bucket.
+             */
+            for( i = 0; i <= 255; i++ )
+            {
+                runningOrder[ i ] = i;
+            }
+            {
+                int vv;
+                int h = 1;
+                do
+                {
+                    h = 3 * h + 1;
+                } while( h <= 256 );
+                do
+                {
+                    h = h / 3;
+                    for( i = h; i <= 255; i++ )
+                    {
+                        vv = runningOrder[ i ];
+                        j = i;
+                        while( ( m_ftab[ ( ( runningOrder[ j - h ] ) + 1 ) << 8 ]
+                            - m_ftab[ ( runningOrder[ j - h ] ) << 8 ] ) >
+                            ( m_ftab[ ( ( vv ) + 1 ) << 8 ] - m_ftab[ ( vv ) << 8 ] ) )
+                        {
+                            runningOrder[ j ] = runningOrder[ j - h ];
+                            j = j - h;
+                            if( j <= ( h - 1 ) )
+                            {
+                                break;
+                            }
+                        }
+                        runningOrder[ j ] = vv;
+                    }
+                } while( h != 1 );
+            }
+
+            /*
+             * The main sorting loop.
+             */
+            for( i = 0; i <= 255; i++ )
+            {
+
+                /*
+                 * Process big buckets, starting with the least full.
+                 */
+                ss = runningOrder[ i ];
+
+                /*
+                 * Complete the big bucket [ss] by quicksorting
+                 * any unsorted small buckets [ss, j].  Hopefully
+                 * previous pointer-scanning phases have already
+                 * completed many of the small buckets [ss, j], so
+                 * we don't have to sort them at all.
+                 */
+                for( j = 0; j <= 255; j++ )
+                {
+                    sb = ( ss << 8 ) + j;
+                    if( !( ( m_ftab[ sb ] & SETMASK ) == SETMASK ) )
+                    {
+                        int lo = m_ftab[ sb ] & CLEARMASK;
+                        int hi = ( m_ftab[ sb + 1 ] & CLEARMASK ) - 1;
+                        if( hi > lo )
+                        {
+                            qSort3( lo, hi, 2 );
+                            if( m_workDone > m_workLimit && m_firstAttempt )
+                            {
+                                return;
+                            }
+                        }
+                        m_ftab[ sb ] |= SETMASK;
+                    }
+                }
+
+                /*
+                 * The ss big bucket is now done.  Record this fact,
+                 * and update the quadrant descriptors.  Remember to
+                 * update quadrants in the overshoot area too, if
+                 * necessary.  The "if (i < 255)" test merely skips
+                 * this updating for the last bucket processed, since
+                 * updating for the last bucket is pointless.
+                 */
+                bigDone[ ss ] = true;
+
+                if( i < 255 )
+                {
+                    int bbStart = m_ftab[ ss << 8 ] & CLEARMASK;
+                    int bbSize = ( m_ftab[ ( ss + 1 ) << 8 ] & CLEARMASK ) - bbStart;
+                    int shifts = 0;
+
+                    while( ( bbSize >> shifts ) > 65534 )
+                    {
+                        shifts++;
+                    }
+
+                    for( j = 0; j < bbSize; j++ )
+                    {
+                        int a2update = m_zptr[ bbStart + j ];
+                        int qVal = ( j >> shifts );
+                        m_quadrant[ a2update ] = qVal;
+                        if( a2update < NUM_OVERSHOOT_BYTES )
+                        {
+                            m_quadrant[ a2update + m_last + 1 ] = qVal;
+                        }
+                    }
+
+                    if( !( ( ( bbSize - 1 ) >> shifts ) <= 65535 ) )
+                    {
+                        panic();
+                    }
+                }
+
+                /*
+                 * Now scan this big bucket so as to synthesise the
+                 * sorted order for small buckets [t, ss] for all t != ss.
+                 */
+                for( j = 0; j <= 255; j++ )
+                {
+                    copy[ j ] = m_ftab[ ( j << 8 ) + ss ] & CLEARMASK;
+                }
+
+                for( j = m_ftab[ ss << 8 ] & CLEARMASK;
+                     j < ( m_ftab[ ( ss + 1 ) << 8 ] & CLEARMASK ); j++ )
+                {
+                    c1 = m_block[ m_zptr[ j ] ];
+                    if( !bigDone[ c1 ] )
+                    {
+                        m_zptr[ copy[ c1 ] ] = m_zptr[ j ] == 0 ? m_last : m_zptr[ j ] - 1;
+                        copy[ c1 ]++;
+                    }
+                }
+
+                for( j = 0; j <= 255; j++ )
+                {
+                    m_ftab[ ( j << 8 ) + ss ] |= SETMASK;
+                }
+            }
+        }
+    }
+
+    private void makeMaps()
+    {
+        int i;
+        m_nInUse = 0;
+        for( i = 0; i < 256; i++ )
+        {
+            if( m_inUse[ i ] )
+            {
+                m_seqToUnseq[ m_nInUse ] = (char)i;
+                m_unseqToSeq[ i ] = (char)m_nInUse;
+                m_nInUse++;
+            }
+        }
+    }
+
+    private char med3( char a, char b, char c )
+    {
+        char t;
+        if( a > b )
+        {
+            t = a;
+            a = b;
+            b = t;
+        }
+        if( b > c )
+        {
+            t = b;
+            b = c;
+            c = t;
+        }
+        if( a > b )
+        {
+            b = a;
+        }
+        return b;
+    }
+
+    private void moveToFrontCodeAndSend()
+        throws IOException
+    {
+        bsPutIntVS( 24, m_origPtr );
+        generateMTFValues();
+        sendMTFValues();
+    }
+
+    private void qSort3( int loSt, int hiSt, int dSt )
+    {
+        int unLo;
+        int unHi;
+        int ltLo;
+        int gtHi;
+        int med;
+        int n;
+        int m;
+        int sp;
+        int lo;
+        int hi;
+        int d;
+        StackElem[] stack = new StackElem[ QSORT_STACK_SIZE ];
+        for( int count = 0; count < QSORT_STACK_SIZE; count++ )
+        {
+            stack[ count ] = new StackElem();
+        }
+
+        sp = 0;
+
+        stack[ sp ].m_ll = loSt;
+        stack[ sp ].m_hh = hiSt;
+        stack[ sp ].m_dd = dSt;
+        sp++;
+
+        while( sp > 0 )
+        {
+            if( sp >= QSORT_STACK_SIZE )
+            {
+                panic();
+            }
+
+            sp--;
+            lo = stack[ sp ].m_ll;
+            hi = stack[ sp ].m_hh;
+            d = stack[ sp ].m_dd;
+
+            if( hi - lo < SMALL_THRESH || d > DEPTH_THRESH )
+            {
+                simpleSort( lo, hi, d );
+                if( m_workDone > m_workLimit && m_firstAttempt )
+                {
+                    return;
+                }
+                continue;
+            }
+
+            med = med3( m_block[ m_zptr[ lo ] + d + 1 ],
+                        m_block[ m_zptr[ hi ] + d + 1 ],
+                        m_block[ m_zptr[ ( lo + hi ) >> 1 ] + d + 1 ] );
+
+            unLo = lo;
+            ltLo = lo;
+            unHi = hi;
+            gtHi = hi;
+
+            while( true )
+            {
+                while( true )
+                {
+                    if( unLo > unHi )
+                    {
+                        break;
+                    }
+                    n = m_block[ m_zptr[ unLo ] + d + 1 ] - med;
+                    if( n == 0 )
+                    {
+                        int temp = 0;
+                        temp = m_zptr[ unLo ];
+                        m_zptr[ unLo ] = m_zptr[ ltLo ];
+                        m_zptr[ ltLo ] = temp;
+                        ltLo++;
+                        unLo++;
+                        continue;
+                    }
+                    ;
+                    if( n > 0 )
+                    {
+                        break;
+                    }
+                    unLo++;
+                }
+                while( true )
+                {
+                    if( unLo > unHi )
+                    {
+                        break;
+                    }
+                    n = m_block[ m_zptr[ unHi ] + d + 1 ] - med;
+                    if( n == 0 )
+                    {
+                        int temp = 0;
+                        temp = m_zptr[ unHi ];
+                        m_zptr[ unHi ] = m_zptr[ gtHi ];
+                        m_zptr[ gtHi ] = temp;
+                        gtHi--;
+                        unHi--;
+                        continue;
+                    }
+                    ;
+                    if( n < 0 )
+                    {
+                        break;
+                    }
+                    unHi--;
+                }
+                if( unLo > unHi )
+                {
+                    break;
+                }
+                int temp = 0;
+                temp = m_zptr[ unLo ];
+                m_zptr[ unLo ] = m_zptr[ unHi ];
+                m_zptr[ unHi ] = temp;
+                unLo++;
+                unHi--;
+            }
+
+            if( gtHi < ltLo )
+            {
+                stack[ sp ].m_ll = lo;
+                stack[ sp ].m_hh = hi;
+                stack[ sp ].m_dd = d + 1;
+                sp++;
+                continue;
+            }
+
+            n = ( ( ltLo - lo ) < ( unLo - ltLo ) ) ? ( ltLo - lo ) : ( unLo - ltLo );
+            vswap( lo, unLo - n, n );
+            m = ( ( hi - gtHi ) < ( gtHi - unHi ) ) ? ( hi - gtHi ) : ( gtHi - unHi );
+            vswap( unLo, hi - m + 1, m );
+
+            n = lo + unLo - ltLo - 1;
+            m = hi - ( gtHi - unHi ) + 1;
+
+            stack[ sp ].m_ll = lo;
+            stack[ sp ].m_hh = n;
+            stack[ sp ].m_dd = d;
+            sp++;
+
+            stack[ sp ].m_ll = n + 1;
+            stack[ sp ].m_hh = m - 1;
+            stack[ sp ].m_dd = d + 1;
+            sp++;
+
+            stack[ sp ].m_ll = m;
+            stack[ sp ].m_hh = hi;
+            stack[ sp ].m_dd = d;
+            sp++;
+        }
+    }
+
+    private void randomiseBlock()
+    {
+        int i;
+        int rNToGo = 0;
+        int rTPos = 0;
+        for( i = 0; i < 256; i++ )
+        {
+            m_inUse[ i ] = false;
+        }
+
+        for( i = 0; i <= m_last; i++ )
+        {
+            if( rNToGo == 0 )
+            {
+                rNToGo = (char)RAND_NUMS[ rTPos ];
+                rTPos++;
+                if( rTPos == 512 )
+                {
+                    rTPos = 0;
+                }
+            }
+            rNToGo--;
+            m_block[ i + 1 ] ^= ( ( rNToGo == 1 ) ? 1 : 0 );
+            // handle 16 bit signed numbers
+            m_block[ i + 1 ] &= 0xFF;
+
+            m_inUse[ m_block[ i + 1 ] ] = true;
+        }
+    }
+
+    private void sendMTFValues()
+        throws IOException
+    {
+        char[][] len = new char[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+
+        int v;
+
+        int t;
+
+        int i;
+
+        int j;
+
+        int gs;
+
+        int ge;
+
+        int bt;
+
+        int bc;
+
+        int iter;
+        int nSelectors = 0;
+        int alphaSize;
+        int minLen;
+        int maxLen;
+        int selCtr;
+        int nGroups;
+
+        alphaSize = m_nInUse + 2;
+        for( t = 0; t < N_GROUPS; t++ )
+        {
+            for( v = 0; v < alphaSize; v++ )
+            {
+                len[ t ][ v ] = (char)GREATER_ICOST;
+            }
+        }
+
+        /*
+         * Decide how many coding tables to use
+         */
+        if( m_nMTF <= 0 )
+        {
+            panic();
+        }
+
+        if( m_nMTF < 200 )
+        {
+            nGroups = 2;
+        }
+        else if( m_nMTF < 600 )
+        {
+            nGroups = 3;
+        }
+        else if( m_nMTF < 1200 )
+        {
+            nGroups = 4;
+        }
+        else if( m_nMTF < 2400 )
+        {
+            nGroups = 5;
+        }
+        else
+        {
+            nGroups = 6;
+        }
+        {
+            /*
+             * Generate an initial set of coding tables
+             */
+            int nPart;
+            int remF;
+            int tFreq;
+            int aFreq;
+
+            nPart = nGroups;
+            remF = m_nMTF;
+            gs = 0;
+            while( nPart > 0 )
+            {
+                tFreq = remF / nPart;
+                ge = gs - 1;
+                aFreq = 0;
+                while( aFreq < tFreq && ge < alphaSize - 1 )
+                {
+                    ge++;
+                    aFreq += m_mtfFreq[ ge ];
+                }
+
+                if( ge > gs && nPart != nGroups && nPart != 1
+                    && ( ( nGroups - nPart ) % 2 == 1 ) )
+                {
+                    aFreq -= m_mtfFreq[ ge ];
+                    ge--;
+                }
+
+                for( v = 0; v < alphaSize; v++ )
+                {
+                    if( v >= gs && v <= ge )
+                    {
+                        len[ nPart - 1 ][ v ] = (char)LESSER_ICOST;
+                    }
+                    else
+                    {
+                        len[ nPart - 1 ][ v ] = (char)GREATER_ICOST;
+                    }
+                }
+
+                nPart--;
+                gs = ge + 1;
+                remF -= aFreq;
+            }
+        }
+
+        int[][] rfreq = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+        int[] fave = new int[ N_GROUPS ];
+        short[] cost = new short[ N_GROUPS ];
+        /*
+         * Iterate up to N_ITERS times to improve the tables.
+         */
+        for( iter = 0; iter < N_ITERS; iter++ )
+        {
+            for( t = 0; t < nGroups; t++ )
+            {
+                fave[ t ] = 0;
+            }
+
+            for( t = 0; t < nGroups; t++ )
+            {
+                for( v = 0; v < alphaSize; v++ )
+                {
+                    rfreq[ t ][ v ] = 0;
+                }
+            }
+
+            nSelectors = 0;
+            gs = 0;
+            while( true )
+            {
+
+                /*
+                 * Set group start & end marks.
+                 */
+                if( gs >= m_nMTF )
+                {
+                    break;
+                }
+                ge = gs + G_SIZE - 1;
+                if( ge >= m_nMTF )
+                {
+                    ge = m_nMTF - 1;
+                }
+
+                /*
+                 * Calculate the cost of this group as coded
+                 * by each of the coding tables.
+                 */
+                for( t = 0; t < nGroups; t++ )
+                {
+                    cost[ t ] = 0;
+                }
+
+                if( nGroups == 6 )
+                {
+                    short cost0 = 0;
+                    short cost1 = 0;
+                    short cost2 = 0;
+                    short cost3 = 0;
+                    short cost4 = 0;
+                    short cost5 = 0;
+
+                    for( i = gs; i <= ge; i++ )
+                    {
+                        short icv = m_szptr[ i ];
+                        cost0 += len[ 0 ][ icv ];
+                        cost1 += len[ 1 ][ icv ];
+                        cost2 += len[ 2 ][ icv ];
+                        cost3 += len[ 3 ][ icv ];
+                        cost4 += len[ 4 ][ icv ];
+                        cost5 += len[ 5 ][ icv ];
+                    }
+                    cost[ 0 ] = cost0;
+                    cost[ 1 ] = cost1;
+                    cost[ 2 ] = cost2;
+                    cost[ 3 ] = cost3;
+                    cost[ 4 ] = cost4;
+                    cost[ 5 ] = cost5;
+                }
+                else
+                {
+                    for( i = gs; i <= ge; i++ )
+                    {
+                        short icv = m_szptr[ i ];
+                        for( t = 0; t < nGroups; t++ )
+                        {
+                            cost[ t ] += len[ t ][ icv ];
+                        }
+                    }
+                }
+
+                /*
+                 * Find the coding table which is best for this group,
+                 * and record its identity in the selector table.
+                 */
+                bc = 999999999;
+                bt = -1;
+                for( t = 0; t < nGroups; t++ )
+                {
+                    if( cost[ t ] < bc )
+                    {
+                        bc = cost[ t ];
+                        bt = t;
+                    }
+                }
+                ;
+                fave[ bt ]++;
+                m_selector[ nSelectors ] = (char)bt;
+                nSelectors++;
+
+                /*
+                 * Increment the symbol frequencies for the selected table.
+                 */
+                for( i = gs; i <= ge; i++ )
+                {
+                    rfreq[ bt ][ m_szptr[ i ] ]++;
+                }
+
+                gs = ge + 1;
+            }
+
+            /*
+             * Recompute the tables based on the accumulated frequencies.
+             */
+            for( t = 0; t < nGroups; t++ )
+            {
+                hbMakeCodeLengths( len[ t ], rfreq[ t ], alphaSize, 20 );
+            }
+        }
+
+        rfreq = null;
+        fave = null;
+        cost = null;
+
+        if( !( nGroups < 8 ) )
+        {
+            panic();
+        }
+        if( !( nSelectors < 32768 && nSelectors <= ( 2 + ( 900000 / G_SIZE ) ) ) )
+        {
+            panic();
+        }
+        {
+            /*
+             * Compute MTF values for the selectors.
+             */
+            char[] pos = new char[ N_GROUPS ];
+            char ll_i;
+            char tmp2;
+            char tmp;
+            for( i = 0; i < nGroups; i++ )
+            {
+                pos[ i ] = (char)i;
+            }
+            for( i = 0; i < nSelectors; i++ )
+            {
+                ll_i = m_selector[ i ];
+                j = 0;
+                tmp = pos[ j ];
+                while( ll_i != tmp )
+                {
+                    j++;
+                    tmp2 = tmp;
+                    tmp = pos[ j ];
+                    pos[ j ] = tmp2;
+                }
+                pos[ 0 ] = tmp;
+                m_selectorMtf[ i ] = (char)j;
+            }
+        }
+
+        int[][] code = new int[ N_GROUPS ][ MAX_ALPHA_SIZE ];
+
+        /*
+         * Assign actual codes for the tables.
+         */
+        for( t = 0; t < nGroups; t++ )
+        {
+            minLen = 32;
+            maxLen = 0;
+            for( i = 0; i < alphaSize; i++ )
+            {
+                if( len[ t ][ i ] > maxLen )
+                {
+                    maxLen = len[ t ][ i ];
+                }
+                if( len[ t ][ i ] < minLen )
+                {
+                    minLen = len[ t ][ i ];
+                }
+            }
+            if( maxLen > 20 )
+            {
+                panic();
+            }
+            if( minLen < 1 )
+            {
+                panic();
+            }
+            hbAssignCodes( code[ t ], len[ t ], minLen, maxLen, alphaSize );
+        }
+        {
+            /*
+             * Transmit the mapping table.
+             */
+            boolean[] inUse16 = new boolean[ 16 ];
+            for( i = 0; i < 16; i++ )
+            {
+                inUse16[ i ] = false;
+                for( j = 0; j < 16; j++ )
+                {
+                    if( m_inUse[ i * 16 + j ] )
+                    {
+                        inUse16[ i ] = true;
+                    }
+                }
+            }
+
+            for( i = 0; i < 16; i++ )
+            {
+                if( inUse16[ i ] )
+                {
+                    bsW( 1, 1 );
+                }
+                else
+                {
+                    bsW( 1, 0 );
+                }
+            }
+
+            for( i = 0; i < 16; i++ )
+            {
+                if( inUse16[ i ] )
+                {
+                    for( j = 0; j < 16; j++ )
+                    {
+                        if( m_inUse[ i * 16 + j ] )
+                        {
+                            bsW( 1, 1 );
+                        }
+                        else
+                        {
+                            bsW( 1, 0 );
+                        }
+                    }
+                }
+            }
+
+        }
+
+        /*
+         * Now the selectors.
+         */
+        bsW( 3, nGroups );
+        bsW( 15, nSelectors );
+        for( i = 0; i < nSelectors; i++ )
+        {
+            for( j = 0; j < m_selectorMtf[ i ]; j++ )
+            {
+                bsW( 1, 1 );
+            }
+            bsW( 1, 0 );
+        }
+
+        for( t = 0; t < nGroups; t++ )
+        {
+            int curr = len[ t ][ 0 ];
+            bsW( 5, curr );
+            for( i = 0; i < alphaSize; i++ )
+            {
+                while( curr < len[ t ][ i ] )
+                {
+                    bsW( 2, 2 );
+                    curr++;
+                    /*
+                     * 10
+                     */
+                }
+                while( curr > len[ t ][ i ] )
+                {
+                    bsW( 2, 3 );
+                    curr--;
+                    /*
+                     * 11
+                     */
+                }
+                bsW( 1, 0 );
+            }
+        }
+
+        /*
+         * And finally, the block data proper
+         */
+        selCtr = 0;
+        gs = 0;
+        while( true )
+        {
+            if( gs >= m_nMTF )
+            {
+                break;
+            }
+            ge = gs + G_SIZE - 1;
+            if( ge >= m_nMTF )
+            {
+                ge = m_nMTF - 1;
+            }
+            for( i = gs; i <= ge; i++ )
+            {
+                bsW( len[ m_selector[ selCtr ] ][ m_szptr[ i ] ],
+                     code[ m_selector[ selCtr ] ][ m_szptr[ i ] ] );
+            }
+
+            gs = ge + 1;
+            selCtr++;
+        }
+        if( !( selCtr == nSelectors ) )
+        {
+            panic();
+        }
+    }
+
+    private void simpleSort( int lo, int hi, int d )
+    {
+        int i;
+        int j;
+        int h;
+        int bigN;
+        int hp;
+        int v;
+
+        bigN = hi - lo + 1;
+        if( bigN < 2 )
+        {
+            return;
+        }
+
+        hp = 0;
+        while( m_incs[ hp ] < bigN )
+        {
+            hp++;
+        }
+        hp--;
+
+        for( ; hp >= 0; hp-- )
+        {
+            h = m_incs[ hp ];
+
+            i = lo + h;
+            while( true )
+            {
+                /*
+                 * copy 1
+                 */
+                if( i > hi )
+                {
+                    break;
+                }
+                v = m_zptr[ i ];
+                j = i;
+                while( fullGtU( m_zptr[ j - h ] + d, v + d ) )
+                {
+                    m_zptr[ j ] = m_zptr[ j - h ];
+                    j = j - h;
+                    if( j <= ( lo + h - 1 ) )
+                    {
+                        break;
+                    }
+                }
+                m_zptr[ j ] = v;
+                i++;
+
+                /*
+                 * copy 2
+                 */
+                if( i > hi )
+                {
+                    break;
+                }
+                v = m_zptr[ i ];
+                j = i;
+                while( fullGtU( m_zptr[ j - h ] + d, v + d ) )
+                {
+                    m_zptr[ j ] = m_zptr[ j - h ];
+                    j = j - h;
+                    if( j <= ( lo + h - 1 ) )
+                    {
+                        break;
+                    }
+                }
+                m_zptr[ j ] = v;
+                i++;
+
+                /*
+                 * copy 3
+                 */
+                if( i > hi )
+                {
+                    break;
+                }
+                v = m_zptr[ i ];
+                j = i;
+                while( fullGtU( m_zptr[ j - h ] + d, v + d ) )
+                {
+                    m_zptr[ j ] = m_zptr[ j - h ];
+                    j = j - h;
+                    if( j <= ( lo + h - 1 ) )
+                    {
+                        break;
+                    }
+                }
+                m_zptr[ j ] = v;
+                i++;
+
+                if( m_workDone > m_workLimit && m_firstAttempt )
+                {
+                    return;
+                }
+            }
+        }
+    }
+
+    private void vswap( int p1, int p2, int n )
+    {
+        int temp = 0;
+        while( n > 0 )
+        {
+            temp = m_zptr[ p1 ];
+            m_zptr[ p1 ] = m_zptr[ p2 ];
+            m_zptr[ p2 ] = temp;
+            p1++;
+            p2++;
+            n--;
+        }
+    }
+
+    private void writeRun()
+        throws IOException
+    {
+        if( m_last < m_allowableBlockSize )
+        {
+            m_inUse[ m_currentChar ] = true;
+            for( int i = 0; i < m_runLength; i++ )
+            {
+                m_crc.updateCRC( (char)m_currentChar );
+            }
+            switch( m_runLength )
+            {
+                case 1:
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    break;
+                case 2:
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    break;
+                case 3:
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    break;
+                default:
+                    m_inUse[ m_runLength - 4 ] = true;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)m_currentChar;
+                    m_last++;
+                    m_block[ m_last + 1 ] = (char)( m_runLength - 4 );
+                    break;
+            }
+        }
+        else
+        {
+            endBlock();
+            initBlock();
+            writeRun();
+        }
+    }
+
+    private static class StackElem
+    {
+        int m_dd;
+        int m_hh;
+        int m_ll;
+    }
+}
+

Propchange: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java
------------------------------------------------------------------------------
    svn:executable = *

Propchange: jakarta/commons/sandbox/compress/trunk/src/java/org/apache/commons/compress/compressors/bzip2/BZip2OutputStream.java
------------------------------------------------------------------------------
    svn:keywords = "Author Date Id Revision"



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message