/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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.vfs2.provider.bzip2;

import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.BASE_BLOCK_SIZE;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.G_SIZE;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.MAX_ALPHA_SIZE;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.MAX_SELECTORS;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.NUM_OVERSHOOT_BYTES;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.N_GROUPS;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.N_ITERS;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.RAND_NUMS;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.RUNA;
import static org.apache.commons.vfs2.provider.bzip2.BZip2Constants.RUNB;

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="http://commons.apache.org/vfs/team-list.html">Commons VFS team</a>
 */
class CBZip2OutputStream extends OutputStream
{
    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 crc = new CRC();

    private boolean[] inUse = new boolean[256];

    private char[] seqToUnseq = new char[256];
    private char[] unseqToSeq = new char[256];

    private char[] selector = new char[MAX_SELECTORS];
    private char[] selectorMtf = new char[MAX_SELECTORS];

    private int[] mtfFreq = new int[MAX_ALPHA_SIZE];

    private int currentChar = -1;
    private int runLength;

    private boolean 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[] incs = new int[]
            {
                    1, 4, 13, 40, 121, 364, 1093, 3280,
                    9841, 29524, 88573, 265720,
                    797161, 2391484
            };

    private boolean blockRandomised;

    /*
     * always: in the range 0 .. 9.
     * The current block size is 100000 * this number.
     */
    private int blockSize100k;
    private int bsBuff;
    private int bsLive;

    /*
     * index of the last char in the block, so
     * the block size == last + 1.
     */
    private int last;

    /*
     * index in zptr[] of original string after sorting.
     */
    private int origPtr;

    private int allowableBlockSize;

    private char[] block;

    private int blockCRC;
    private int combinedCRC;

    private OutputStream bsStream;
    private boolean firstAttempt;
    private int[] ftab;
    private int nInUse;

    private int nMTF;
    private int[] quadrant;
    private short[] szptr;
    private int workDone;

    /*
     * Used when sorting.  If too many long comparisons
     * happen, we stop sorting, randomise the block
     * slightly, and try again.
     */
    private int workFactor;
    private int workLimit;
    private int[] zptr;

    CBZip2OutputStream(final OutputStream output)
            throws IOException
    {
        this(output, 9);
    }

    CBZip2OutputStream(final OutputStream output, final int blockSize)
            throws IOException
    {
        bsSetStream(output);
        workFactor = 50;

        int outBlockSize = blockSize;
        if (outBlockSize > 9)
        {
            outBlockSize = 9;
        }
        if (outBlockSize < 1)
        {
            outBlockSize = 1;
        }
        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();
    }

    @Override
    public void close()
            throws IOException
    {
        if (closed)
        {
            return;
        }

        if (runLength > 0)
        {
            writeRun();
        }
        currentChar = -1;
        endBlock();
        endCompression();
        closed = true;
        super.close();
        bsStream.close();
    }

    @Override
    public void finalize()
            throws Throwable
    {
        close();
    }

    @Override
    public void flush()
            throws IOException
    {
        super.flush();
        bsStream.flush();
    }

    /**
     * modified by Oliver Merkel, 010128
     *
     * @param bv Description of Parameter
     * @throws java.io.IOException Description of Exception
     */
    @Override
    public void write(int bv)
            throws IOException
    {
        int b = (256 + bv) % 256;
        if (currentChar != -1)
        {
            if (currentChar == b)
            {
                runLength++;
                if (runLength > 254)
                {
                    writeRun();
                    currentChar = -1;
                    runLength = 0;
                }
            }
            else
            {
                writeRun();
                runLength = 1;
                currentChar = b;
            }
        }
        else
        {
            currentChar = b;
            runLength++;
        }
    }

    private void allocateCompressStructures()
    {
        int n = BASE_BLOCK_SIZE * blockSize100k;
        block = new char[(n + 1 + NUM_OVERSHOOT_BYTES)];
        quadrant = new int[(n + NUM_OVERSHOOT_BYTES)];
        zptr = new int[n];
        ftab = new int[65537];

        if (block == null || quadrant == null || zptr == null
                || 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;

        szptr = new short[2 * n];
    }

    private void bsFinishedWithStream()
            throws IOException
    {
        while (bsLive > 0)
        {
            int ch = (bsBuff >> 24);
            try
            {
                bsStream.write(ch); // write 8-bit
            }
            catch (IOException e)
            {
                throw e;
            }
            bsBuff <<= 8;
            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)
    {
        bsStream = f;
        bsLive = 0;
        bsBuff = 0;
    }

    private void bsW(int n, int v)
            throws IOException
    {
        while (bsLive >= 8)
        {
            int ch = (bsBuff >> 24);
            try
            {
                bsStream.write(ch); // write 8-bit
            }
            catch (IOException e)
            {
                throw e;
            }
            bsBuff <<= 8;
            bsLive -= 8;
        }
        bsBuff |= (v << (32 - bsLive - n));
        bsLive += n;
    }

    private void doReversibleTransformation()
    {
        int i;

        workLimit = workFactor * last;
        workDone = 0;
        blockRandomised = false;
        firstAttempt = true;

        mainSort();

        if (workDone > workLimit && firstAttempt)
        {
            randomiseBlock();
            workLimit = 0;
            workDone = 0;
            blockRandomised = true;
            firstAttempt = false;
            mainSort();
        }

        origPtr = -1;
        for (i = 0; i <= last; i++)
        {
            if (zptr[i] == 0)
            {
                origPtr = i;
                break;
            }
        }

        if (origPtr == -1)
        {
            panic();
        }
    }

    private void endBlock()
            throws IOException
    {
        blockCRC = crc.getFinalCRC();
        combinedCRC = (combinedCRC << 1) | (combinedCRC >>> 31);
        combinedCRC ^= 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(blockCRC);

        /*
         * Now a single bit indicating randomisation.
         */
        if (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(combinedCRC);

        bsFinishedWithStream();
    }

    private boolean fullGtU(int i1, int i2)
    {
        int k;
        char c1;
        char c2;
        int s1;
        int s2;

        c1 = block[i1 + 1];
        c2 = block[i2 + 1];
        if (c1 != c2)
        {
            return (c1 > c2);
        }
        i1++;
        i2++;

        c1 = block[i1 + 1];
        c2 = block[i2 + 1];
        if (c1 != c2)
        {
            return (c1 > c2);
        }
        i1++;
        i2++;

        c1 = block[i1 + 1];
        c2 = block[i2 + 1];
        if (c1 != c2)
        {
            return (c1 > c2);
        }
        i1++;
        i2++;

        c1 = block[i1 + 1];
        c2 = block[i2 + 1];
        if (c1 != c2)
        {
            return (c1 > c2);
        }
        i1++;
        i2++;

        c1 = block[i1 + 1];
        c2 = block[i2 + 1];
        if (c1 != c2)
        {
            return (c1 > c2);
        }
        i1++;
        i2++;

        c1 = block[i1 + 1];
        c2 = block[i2 + 1];
        if (c1 != c2)
        {
            return (c1 > c2);
        }
        i1++;
        i2++;

        k = last + 1;

        do
        {
            c1 = block[i1 + 1];
            c2 = block[i2 + 1];
            if (c1 != c2)
            {
                return (c1 > c2);
            }
            s1 = quadrant[i1];
            s2 = quadrant[i2];
            if (s1 != s2)
            {
                return (s1 > s2);
            }
            i1++;
            i2++;

            c1 = block[i1 + 1];
            c2 = block[i2 + 1];
            if (c1 != c2)
            {
                return (c1 > c2);
            }
            s1 = quadrant[i1];
            s2 = quadrant[i2];
            if (s1 != s2)
            {
                return (s1 > s2);
            }
            i1++;
            i2++;

            c1 = block[i1 + 1];
            c2 = block[i2 + 1];
            if (c1 != c2)
            {
                return (c1 > c2);
            }
            s1 = quadrant[i1];
            s2 = quadrant[i2];
            if (s1 != s2)
            {
                return (s1 > s2);
            }
            i1++;
            i2++;

            c1 = block[i1 + 1];
            c2 = block[i2 + 1];
            if (c1 != c2)
            {
                return (c1 > c2);
            }
            s1 = quadrant[i1];
            s2 = quadrant[i2];
            if (s1 != s2)
            {
                return (s1 > s2);
            }
            i1++;
            i2++;

            if (i1 > last)
            {
                i1 -= last;
                i1--;
            }

            if (i2 > last)
            {
                i2 -= last;
                i2--;
            }

            k -= 4;
            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 = nInUse + 1;

        for (i = 0; i <= eob; i++)
        {
            mtfFreq[i] = 0;
        }

        wr = 0;
        zPend = 0;
        for (i = 0; i < nInUse; i++)
        {
            yy[i] = (char) i;
        }

        for (i = 0; i <= last; i++)
        {
            char ll_i;

            ll_i = unseqToSeq[block[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:
                                szptr[wr] = (short) RUNA;
                                wr++;
                                mtfFreq[RUNA]++;
                                break;
                            case 1:
                                szptr[wr] = (short) RUNB;
                                wr++;
                                mtfFreq[RUNB]++;
                                break;
                        }

                        if (zPend < 2)
                        {
                            break;
                        }
                        zPend = (zPend - 2) / 2;
                    }

                    zPend = 0;
                }
                szptr[wr] = (short) (j + 1);
                wr++;
                mtfFreq[j + 1]++;
            }
        }

        if (zPend > 0)
        {
            zPend--;
            while (true)
            {
                switch (zPend % 2)
                {
                    case 0:
                        szptr[wr] = (short) RUNA;
                        wr++;
                        mtfFreq[RUNA]++;
                        break;
                    case 1:
                        szptr[wr] = (short) RUNB;
                        wr++;
                        mtfFreq[RUNB]++;
                        break;
                }
                if (zPend < 2)
                {
                    break;
                }
                zPend = (zPend - 2) / 2;
            }
        }

        szptr[wr] = (short) eob;
        wr++;
        mtfFreq[eob]++;

        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++;
        crc.initialiseCRC();
        last = -1;
        //        ch = 0;

        for (int i = 0; i < 256; i++)
        {
            inUse[i] = false;
        }

        /*
         * 20 is just a paranoia constant
         */
        allowableBlockSize = BASE_BLOCK_SIZE * 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' + blockSize100k);

        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++)
        {
            block[last + i + 2] = block[(i % (last + 1)) + 1];
        }
        for (i = 0; i <= last + NUM_OVERSHOOT_BYTES; i++)
        {
            quadrant[i] = 0;
        }

        block[0] = block[last + 1];

        if (last < 4000)
        {
            /*
             * Use simpleSort(), since the full sorting mechanism
             * has quite a large constant overhead.
             */
            for (i = 0; i <= last; i++)
            {
                zptr[i] = i;
            }
            firstAttempt = false;
            workDone = 0;
            workLimit = 0;
            simpleSort(0, last, 0);
        }
        else
        {
            for (i = 0; i <= 255; i++)
            {
                bigDone[i] = false;
            }

            for (i = 0; i <= 65536; i++)
            {
                ftab[i] = 0;
            }

            c1 = block[0];
            for (i = 0; i <= last; i++)
            {
                c2 = block[i + 1];
                ftab[(c1 << 8) + c2]++;
                c1 = c2;
            }

            for (i = 1; i <= 65536; i++)
            {
                ftab[i] += ftab[i - 1];
            }

            c1 = block[1];
            for (i = 0; i < last; i++)
            {
                c2 = block[i + 2];
                j = (c1 << 8) + c2;
                c1 = c2;
                ftab[j]--;
                zptr[ftab[j]] = i;
            }

            j = ((block[last + 1]) << 8) + (block[1]);
            ftab[j]--;
            zptr[ftab[j]] = 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 ((ftab[((runningOrder[j - h]) + 1) << 8]
                                - ftab[(runningOrder[j - h]) << 8]) >
                                (ftab[((vv) + 1) << 8] - 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 (!((ftab[sb] & SETMASK) == SETMASK))
                    {
                        int lo = ftab[sb] & CLEARMASK;
                        int hi = (ftab[sb + 1] & CLEARMASK) - 1;
                        if (hi > lo)
                        {
                            qSort3(lo, hi, 2);
                            if (workDone > workLimit && firstAttempt)
                            {
                                return;
                            }
                        }
                        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 = ftab[ss << 8] & CLEARMASK;
                    int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart;
                    int shifts = 0;

                    while ((bbSize >> shifts) > 65534)
                    {
                        shifts++;
                    }

                    for (j = 0; j < bbSize; j++)
                    {
                        int a2update = zptr[bbStart + j];
                        int qVal = (j >> shifts);
                        quadrant[a2update] = qVal;
                        if (a2update < NUM_OVERSHOOT_BYTES)
                        {
                            quadrant[a2update + 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] = ftab[(j << 8) + ss] & CLEARMASK;
                }

                for (j = ftab[ss << 8] & CLEARMASK;
                     j < (ftab[(ss + 1) << 8] & CLEARMASK); j++)
                {
                    c1 = block[zptr[j]];
                    if (!bigDone[c1])
                    {
                        zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
                        copy[c1]++;
                    }
                }

                for (j = 0; j <= 255; j++)
                {
                    ftab[(j << 8) + ss] |= SETMASK;
                }
            }
        }
    }

    private void makeMaps()
    {
        int i;
        nInUse = 0;
        for (i = 0; i < 256; i++)
        {
            if (inUse[i])
            {
                seqToUnseq[nInUse] = (char) i;
                unseqToSeq[i] = (char) nInUse;
                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, 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].ll = loSt;
        stack[sp].hh = hiSt;
        stack[sp].dd = dSt;
        sp++;

        while (sp > 0)
        {
            if (sp >= QSORT_STACK_SIZE)
            {
                panic();
            }

            sp--;
            lo = stack[sp].ll;
            hi = stack[sp].hh;
            d = stack[sp].dd;

            if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH)
            {
                simpleSort(lo, hi, d);
                if (workDone > workLimit && firstAttempt)
                {
                    return;
                }
                continue;
            }

            med = med3(block[zptr[lo] + d + 1],
                    block[zptr[hi] + d + 1],
                    block[zptr[(lo + hi) >> 1] + d + 1]);

            unLo = lo;
            ltLo = lo;
            unHi = hi;
            gtHi = hi;

            while (true)
            {
                while (true)
                {
                    if (unLo > unHi)
                    {
                        break;
                    }
                    n = block[zptr[unLo] + d + 1] - med;
                    if (n == 0)
                    {
                        int temp = 0;
                        temp = zptr[unLo];
                        zptr[unLo] = zptr[ltLo];
                        zptr[ltLo] = temp;
                        ltLo++;
                        unLo++;
                        continue;
                    }

                    if (n > 0)
                    {
                        break;
                    }
                    unLo++;
                }
                while (true)
                {
                    if (unLo > unHi)
                    {
                        break;
                    }
                    n = block[zptr[unHi] + d + 1] - med;
                    if (n == 0)
                    {
                        int temp = 0;
                        temp = zptr[unHi];
                        zptr[unHi] = zptr[gtHi];
                        zptr[gtHi] = temp;
                        gtHi--;
                        unHi--;
                        continue;
                    }

                    if (n < 0)
                    {
                        break;
                    }
                    unHi--;
                }
                if (unLo > unHi)
                {
                    break;
                }
                int temp = 0;
                temp = zptr[unLo];
                zptr[unLo] = zptr[unHi];
                zptr[unHi] = temp;
                unLo++;
                unHi--;
            }

            if (gtHi < ltLo)
            {
                stack[sp].ll = lo;
                stack[sp].hh = hi;
                stack[sp].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].ll = lo;
            stack[sp].hh = n;
            stack[sp].dd = d;
            sp++;

            stack[sp].ll = n + 1;
            stack[sp].hh = m - 1;
            stack[sp].dd = d + 1;
            sp++;

            stack[sp].ll = m;
            stack[sp].hh = hi;
            stack[sp].dd = d;
            sp++;
        }
    }

    private void randomiseBlock()
    {
        int i;
        int rNToGo = 0;
        int rTPos = 0;
        for (i = 0; i < 256; i++)
        {
            inUse[i] = false;
        }

        for (i = 0; i <= last; i++)
        {
            if (rNToGo == 0)
            {
                rNToGo = (char) RAND_NUMS[rTPos];
                rTPos++;
                if (rTPos == 512)
                {
                    rTPos = 0;
                }
            }
            rNToGo--;
            block[i + 1] ^= ((rNToGo == 1) ? 1 : 0);
            // handle 16 bit signed numbers
            block[i + 1] &= 0xFF;

            inUse[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 = 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 (nMTF <= 0)
        {
            panic();
        }

        if (nMTF < 200)
        {
            nGroups = 2;
        }
        else if (nMTF < 600)
        {
            nGroups = 3;
        }
        else if (nMTF < 1200)
        {
            nGroups = 4;
        }
        else if (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 = nMTF;
            gs = 0;
            while (nPart > 0)
            {
                tFreq = remF / nPart;
                ge = gs - 1;
                aFreq = 0;
                while (aFreq < tFreq && ge < alphaSize - 1)
                {
                    ge++;
                    aFreq += mtfFreq[ge];
                }

                if (ge > gs && nPart != nGroups && nPart != 1
                        && ((nGroups - nPart) % 2 == 1))
                {
                    aFreq -= 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 >= nMTF)
                {
                    break;
                }
                ge = gs + G_SIZE - 1;
                if (ge >= nMTF)
                {
                    ge = 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 = 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 = 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]++;
                selector[nSelectors] = (char) bt;
                nSelectors++;

                /*
                 * Increment the symbol frequencies for the selected table.
                 */
                for (i = gs; i <= ge; i++)
                {
                    rfreq[bt][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 = selector[i];
                j = 0;
                tmp = pos[j];
                while (ll_i != tmp)
                {
                    j++;
                    tmp2 = tmp;
                    tmp = pos[j];
                    pos[j] = tmp2;
                }
                pos[0] = tmp;
                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 (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 (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 < 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 >= nMTF)
            {
                break;
            }
            ge = gs + G_SIZE - 1;
            if (ge >= nMTF)
            {
                ge = nMTF - 1;
            }
            for (i = gs; i <= ge; i++)
            {
                bsW(len[selector[selCtr]][szptr[i]],
                        code[selector[selCtr]][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 (incs[hp] < bigN)
        {
            hp++;
        }
        hp--;

        for (; hp >= 0; hp--)
        {
            h = incs[hp];

            i = lo + h;
            while (true)
            {
                /*
                 * copy 1
                 */
                if (i > hi)
                {
                    break;
                }
                v = zptr[i];
                j = i;
                while (fullGtU(zptr[j - h] + d, v + d))
                {
                    zptr[j] = zptr[j - h];
                    j = j - h;
                    if (j <= (lo + h - 1))
                    {
                        break;
                    }
                }
                zptr[j] = v;
                i++;

                /*
                 * copy 2
                 */
                if (i > hi)
                {
                    break;
                }
                v = zptr[i];
                j = i;
                while (fullGtU(zptr[j - h] + d, v + d))
                {
                    zptr[j] = zptr[j - h];
                    j = j - h;
                    if (j <= (lo + h - 1))
                    {
                        break;
                    }
                }
                zptr[j] = v;
                i++;

                /*
                 * copy 3
                 */
                if (i > hi)
                {
                    break;
                }
                v = zptr[i];
                j = i;
                while (fullGtU(zptr[j - h] + d, v + d))
                {
                    zptr[j] = zptr[j - h];
                    j = j - h;
                    if (j <= (lo + h - 1))
                    {
                        break;
                    }
                }
                zptr[j] = v;
                i++;

                if (workDone > workLimit && firstAttempt)
                {
                    return;
                }
            }
        }
    }

    private void vswap(int p1, int p2, int n)
    {
        int temp = 0;
        while (n > 0)
        {
            temp = zptr[p1];
            zptr[p1] = zptr[p2];
            zptr[p2] = temp;
            p1++;
            p2++;
            n--;
        }
    }

    private void writeRun()
            throws IOException
    {
        if (last < allowableBlockSize)
        {
            inUse[currentChar] = true;
            for (int i = 0; i < runLength; i++)
            {
                crc.updateCRC((char) currentChar);
            }
            switch (runLength)
            {
                case 1:
                    last++;
                    block[last + 1] = (char) currentChar;
                    break;
                case 2:
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) currentChar;
                    break;
                case 3:
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) currentChar;
                    break;
                default:
                    inUse[runLength - 4] = true;
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) currentChar;
                    last++;
                    block[last + 1] = (char) (runLength - 4);
                    break;
            }
        }
        else
        {
            endBlock();
            initBlock();
            writeRun();
        }
    }

    /**
     * A Stack element
     */
    private static class StackElem
    {
        int dd;
        int hh;
        int ll;
    }
}

