/*
 * SDK Pullenti Unitext, version 4.33, fabruary 2026. Copyright (c) 2013-2026, Pullenti. All rights reserved. 
 * Non-Commercial Freeware and Commercial Software. 
 * This class is generated using the converter Unisharping (www.unisharping.ru) from Pullenti C# project. 
 * The latest version of the code is available on the site www.pullenti.ru
 */

package com.pullenti.unitext.internal.zip;

// This is the DeflaterHuffman class.
// This class is <i>not</i> thread safe.  This is inherent in the API, due
// to the split of Deflate and SetInput.
public class DeflaterHuffman {

    private static final int bUFSIZE;

    private static final int lITERAL_NUM = 286;

    private static final int dIST_NUM = 30;

    private static final int bITLEN_NUM = 19;

    private static final int rEP_3_6 = 16;

    private static final int rEP_3_10 = 17;

    private static final int rEP_11_138 = 18;

    private static final int eOF_SYMBOL = 256;

    private static int[] bL_ORDER;

    private static byte[] bit4Reverse;

    private static short[] staticLCodes;

    private static byte[] staticLLength;

    private static short[] staticDCodes;

    private static byte[] staticDLength;

    public static class Tree {
    
        public short[] freqs;
    
        public byte[] length;
    
        public int minNumCodes;
    
        public int numCodes;
    
        private short[] codes;
    
        private int[] bl_counts;
    
        private int maxLength;
    
        private com.pullenti.unitext.internal.zip.DeflaterHuffman dh;
    
        public Tree(com.pullenti.unitext.internal.zip.DeflaterHuffman _dh, int elems, int minCodes, int _maxLength) {
            this.dh = _dh;
            this.minNumCodes = minCodes;
            this.maxLength = _maxLength;
            freqs = new short[elems];
            bl_counts = new int[_maxLength];
        }
    
        public void reset() {
            for (int i = 0; i < freqs.length; i++) {
                freqs[i] = (short)0;
            }
            codes = null;
            length = null;
        }
    
        public void writeSymbol(int code) {
            dh.pending.writeBits(((int)codes[code]) & 0xffff, Byte.toUnsignedInt(length[code]));
        }
    
        public void checkEmpty() throws Exception {
            boolean empty = true;
            for (int i = 0; i < freqs.length; i++) {
                if (freqs[i] != ((short)0)) 
                    empty = false;
            }
            if (!empty) 
                throw new Exception("!Empty");
        }
    
        public void setStaticCodes(short[] staticCodes, byte[] staticLengths) {
            codes = staticCodes;
            length = staticLengths;
        }
    
        public void buildCodes() {
            int numSymbols = freqs.length;
            int[] nextCode = new int[maxLength];
            int code = 0;
            codes = new short[freqs.length];
            for (int bits = 0; bits < maxLength; bits++) {
                nextCode[bits] = code;
                code += bl_counts[bits] << ((15 - bits));
            }
            for (int i = 0; i < numCodes; i++) {
                int bits = Byte.toUnsignedInt(length[i]);
                if (bits > 0) {
                    codes[i] = com.pullenti.unitext.internal.zip.DeflaterHuffman.bitReverse(nextCode[bits - 1]);
                    nextCode[bits - 1] += 1 << ((16 - bits));
                }
            }
        }
    
        public void buildTree() throws Exception {
            int numSymbols = freqs.length;
            int[] heap = new int[numSymbols];
            int heapLen = 0;
            int maxCode = 0;
            for (int n = 0; n < numSymbols; n++) {
                int freq = (int)freqs[n];
                if (freq != 0) {
                    int pos = heapLen++;
                    int ppos;
                    while (pos > 0 && freqs[heap[(ppos = ((pos - 1)) / 2)]] > freq) {
                        heap[pos] = heap[ppos];
                        pos = ppos;
                    }
                    heap[pos] = n;
                    maxCode = n;
                }
            }
            while (heapLen < 2) {
                int node = (maxCode < 2 ? ++maxCode : 0);
                heap[heapLen++] = node;
            }
            numCodes = Math.max(maxCode + 1, minNumCodes);
            int numLeafs = heapLen;
            int[] childs = new int[(4 * heapLen) - 2];
            int[] values = new int[(2 * heapLen) - 1];
            int numNodes = numLeafs;
            for (int i = 0; i < heapLen; i++) {
                int node = heap[i];
                childs[2 * i] = node;
                childs[(2 * i) + 1] = -1;
                values[i] = ((int)freqs[node]) << 8;
                heap[i] = i;
            }
            do{
                int first = heap[0];
                int last = heap[--heapLen];
                int ppos = 0;
                int path = 1;
                while (path < heapLen) {
                    if (((path + 1) < heapLen) && values[heap[path]] > values[heap[path + 1]]) 
                        path++;
                    heap[ppos] = heap[path];
                    ppos = path;
                    path = (path * 2) + 1;
                }
                int lastVal = values[last];
                while ((((path = ppos))) > 0 && values[heap[(ppos = ((path - 1)) / 2)]] > lastVal) {
                    heap[path] = heap[ppos];
                }
                heap[path] = last;
                int second = heap[0];
                last = numNodes++;
                childs[2 * last] = first;
                childs[(2 * last) + 1] = second;
                int mindepth = Math.min(values[first] & 0xff, values[second] & 0xff);
                values[last] = (lastVal = ((values[first] + values[second]) - mindepth) + 1);
                ppos = 0;
                path = 1;
                while (path < heapLen) {
                    if (((path + 1) < heapLen) && values[heap[path]] > values[heap[path + 1]]) 
                        path++;
                    heap[ppos] = heap[path];
                    ppos = path;
                    path = (ppos * 2) + 1;
                }
                while ((((path = ppos))) > 0 && values[heap[(ppos = ((path - 1)) / 2)]] > lastVal) {
                    heap[path] = heap[ppos];
                }
                heap[path] = last;
            } while (heapLen > 1); 
            if (heap[0] != ((childs.length / 2) - 1)) 
                throw new Exception("Heap invariant violated");
            this.buildLength(childs);
        }
    
        public int getEncodedLength() {
            int len = 0;
            for (int i = 0; i < freqs.length; i++) {
                len += (((int)freqs[i]) * (Byte.toUnsignedInt(length[i])));
            }
            return len;
        }
    
        public void calcBLFreq(Tree blTree) {
            int max_count;
            int min_count;
            int count;
            int curlen = -1;
            int i = 0;
            while (i < numCodes) {
                count = 1;
                int nextlen = Byte.toUnsignedInt(length[i]);
                if (nextlen == 0) {
                    max_count = 138;
                    min_count = 3;
                }
                else {
                    max_count = 6;
                    min_count = 3;
                    if (curlen != nextlen) {
                        blTree.freqs[nextlen]++;
                        count = 0;
                    }
                }
                curlen = nextlen;
                i++;
                while ((i < numCodes) && curlen == (Byte.toUnsignedInt(length[i]))) {
                    i++;
                    if ((++count) >= max_count) 
                        break;
                }
                if (count < min_count) 
                    blTree.freqs[curlen] += ((short)count);
                else if (curlen != 0) 
                    blTree.freqs[com.pullenti.unitext.internal.zip.DeflaterHuffman.rEP_3_6]++;
                else if (count <= 10) 
                    blTree.freqs[com.pullenti.unitext.internal.zip.DeflaterHuffman.rEP_3_10]++;
                else 
                    blTree.freqs[com.pullenti.unitext.internal.zip.DeflaterHuffman.rEP_11_138]++;
            }
        }
    
        public void writeTree(Tree blTree) {
            int max_count;
            int min_count;
            int count;
            int curlen = -1;
            int i = 0;
            while (i < numCodes) {
                count = 1;
                int nextlen = Byte.toUnsignedInt(length[i]);
                if (nextlen == 0) {
                    max_count = 138;
                    min_count = 3;
                }
                else {
                    max_count = 6;
                    min_count = 3;
                    if (curlen != nextlen) {
                        blTree.writeSymbol(nextlen);
                        count = 0;
                    }
                }
                curlen = nextlen;
                i++;
                while ((i < numCodes) && curlen == (Byte.toUnsignedInt(length[i]))) {
                    i++;
                    if ((++count) >= max_count) 
                        break;
                }
                if (count < min_count) {
                    while ((count--) > 0) {
                        blTree.writeSymbol(curlen);
                    }
                }
                else if (curlen != 0) {
                    blTree.writeSymbol(com.pullenti.unitext.internal.zip.DeflaterHuffman.rEP_3_6);
                    dh.pending.writeBits(count - 3, 2);
                }
                else if (count <= 10) {
                    blTree.writeSymbol(com.pullenti.unitext.internal.zip.DeflaterHuffman.rEP_3_10);
                    dh.pending.writeBits(count - 3, 3);
                }
                else {
                    blTree.writeSymbol(com.pullenti.unitext.internal.zip.DeflaterHuffman.rEP_11_138);
                    dh.pending.writeBits(count - 11, 7);
                }
            }
        }
    
        private void buildLength(int[] childs) {
            this.length = new byte[freqs.length];
            int numNodes = childs.length / 2;
            int numLeafs = ((numNodes + 1)) / 2;
            int overflow = 0;
            for (int i = 0; i < maxLength; i++) {
                bl_counts[i] = 0;
            }
            int[] lengths = new int[numNodes];
            lengths[numNodes - 1] = 0;
            for (int i = numNodes - 1; i >= 0; i--) {
                if (childs[(2 * i) + 1] != -1) {
                    int bitLength = lengths[i] + 1;
                    if (bitLength > maxLength) {
                        bitLength = maxLength;
                        overflow++;
                    }
                    lengths[childs[2 * i]] = (lengths[childs[(2 * i) + 1]] = bitLength);
                }
                else {
                    int bitLength = lengths[i];
                    bl_counts[bitLength - 1]++;
                    this.length[childs[2 * i]] = (byte)lengths[i];
                }
            }
            if (overflow == 0) 
                return;
            int incrBitLen = maxLength - 1;
            do{
                while (bl_counts[--incrBitLen] == 0) {
                }
                do{
                    bl_counts[incrBitLen]--;
                    bl_counts[++incrBitLen]++;
                    overflow -= 1 << ((maxLength - 1 - incrBitLen));
                } while (overflow > 0 && (incrBitLen < (maxLength - 1))); 
            } while (overflow > 0); 
            bl_counts[maxLength - 1] += overflow;
            bl_counts[maxLength - 2] -= overflow;
            int nodePtr = 2 * numLeafs;
            for (int bits = maxLength; bits != 0; bits--) {
                int n = bl_counts[bits - 1];
                while (n > 0) {
                    int childPtr = 2 * childs[nodePtr++];
                    if (childs[childPtr + 1] == -1) {
                        length[childs[childPtr]] = (byte)bits;
                        n--;
                    }
                }
            }
        }
        public Tree() {
        }
    }


    public DeflaterPending pending;

    private Tree literalTree;

    private Tree distTree;

    private Tree blTree;

    private short[] d_buf;

    private byte[] l_buf;

    private int last_lit;

    private int extra_bits;


    public DeflaterHuffman(DeflaterPending _pending) {
        if(_globalInstance == null) return;
        this.pending = _pending;
        literalTree = new Tree(this, lITERAL_NUM, 257, 15);
        distTree = new Tree(this, dIST_NUM, 1, 15);
        blTree = new Tree(this, bITLEN_NUM, 4, 7);
        d_buf = new short[bUFSIZE];
        l_buf = new byte[bUFSIZE];
    }

    public void reset() {
        last_lit = 0;
        extra_bits = 0;
        literalTree.reset();
        distTree.reset();
        blTree.reset();
    }

    public void sendAllTrees(int blTreeCodes) {
        blTree.buildCodes();
        literalTree.buildCodes();
        distTree.buildCodes();
        pending.writeBits(literalTree.numCodes - 257, 5);
        pending.writeBits(distTree.numCodes - 1, 5);
        pending.writeBits(blTreeCodes - 4, 4);
        for (int rank = 0; rank < blTreeCodes; rank++) {
            pending.writeBits(Byte.toUnsignedInt(blTree.length[bL_ORDER[rank]]), 3);
        }
        literalTree.writeTree(blTree);
        distTree.writeTree(blTree);
    }

    public void compressBlock() {
        for (int i = 0; i < last_lit; i++) {
            int litlen = (Byte.toUnsignedInt(l_buf[i])) & 0xff;
            int dist = ((int)d_buf[i]) - 1;
            if (dist != -1) {
                int lc = lcode(litlen);
                literalTree.writeSymbol(lc);
                int bits = ((lc - 261)) / 4;
                if (bits > 0 && bits <= 5) 
                    pending.writeBits(litlen & (((1 << bits) - 1)), bits);
                int dc = dcode(dist);
                distTree.writeSymbol(dc);
                bits = (dc / 2) - 1;
                if (bits > 0) 
                    pending.writeBits(dist & (((1 << bits) - 1)), bits);
            }
            else 
                literalTree.writeSymbol(litlen);
        }
        literalTree.writeSymbol(eOF_SYMBOL);
    }

    public void flushStoredBlock(byte[] stored, int storedOffset, int storedLength, boolean lastBlock) {
        pending.writeBits((DeflaterConstants.STORED_BLOCK << 1) + ((lastBlock ? 1 : 0)), 3);
        pending.alignToByte();
        pending.writeShort(storedLength);
        pending.writeShort(~storedLength);
        pending.writeBlock(stored, storedOffset, storedLength);
        this.reset();
    }

    public void flushBlock(byte[] stored, int storedOffset, int storedLength, boolean lastBlock) throws Exception {
        literalTree.freqs[eOF_SYMBOL]++;
        literalTree.buildTree();
        distTree.buildTree();
        literalTree.calcBLFreq(blTree);
        distTree.calcBLFreq(blTree);
        blTree.buildTree();
        int blTreeCodes = 4;
        for (int i = 18; i > blTreeCodes; i--) {
            if (blTree.length[bL_ORDER[i]] > ((byte)0)) 
                blTreeCodes = i + 1;
        }
        int opt_len = ((14 + (blTreeCodes * 3) + blTree.getEncodedLength()) + literalTree.getEncodedLength() + distTree.getEncodedLength()) + extra_bits;
        int static_len = extra_bits;
        for (int i = 0; i < lITERAL_NUM; i++) {
            static_len += (((int)literalTree.freqs[i]) * (Byte.toUnsignedInt(staticLLength[i])));
        }
        for (int i = 0; i < dIST_NUM; i++) {
            static_len += (((int)distTree.freqs[i]) * (Byte.toUnsignedInt(staticDLength[i])));
        }
        if (opt_len >= static_len) 
            opt_len = static_len;
        if (storedOffset >= 0 && ((storedLength + 4) < (opt_len >> 3))) 
            this.flushStoredBlock(stored, storedOffset, storedLength, lastBlock);
        else if (opt_len == static_len) {
            pending.writeBits((DeflaterConstants.STATIC_TREES << 1) + ((lastBlock ? 1 : 0)), 3);
            literalTree.setStaticCodes(staticLCodes, staticLLength);
            distTree.setStaticCodes(staticDCodes, staticDLength);
            this.compressBlock();
            this.reset();
        }
        else {
            pending.writeBits((DeflaterConstants.DYN_TREES << 1) + ((lastBlock ? 1 : 0)), 3);
            this.sendAllTrees(blTreeCodes);
            this.compressBlock();
            this.reset();
        }
    }

    public boolean isFull() {
        return last_lit >= bUFSIZE;
    }

    public boolean tallyLit(int literal) {
        d_buf[last_lit] = (short)0;
        l_buf[last_lit++] = (byte)literal;
        literalTree.freqs[literal]++;
        return this.isFull();
    }

    public boolean tallyDist(int distance, int length) {
        d_buf[last_lit] = (short)distance;
        l_buf[last_lit++] = (byte)((length - 3));
        int lc = lcode(length - 3);
        literalTree.freqs[lc]++;
        if (lc >= 265 && (lc < 285)) 
            extra_bits += (((lc - 261)) / 4);
        int dc = dcode(distance - 1);
        distTree.freqs[dc]++;
        if (dc >= 4) 
            extra_bits += ((dc / 2) - 1);
        return this.isFull();
    }

    public static short bitReverse(int toReverse) {
        return (short)(((((Byte.toUnsignedInt(bit4Reverse[toReverse & 0xF])) << 12) | ((Byte.toUnsignedInt(bit4Reverse[((toReverse >> 4)) & 0xF])) << 8) | ((Byte.toUnsignedInt(bit4Reverse[((toReverse >> 8)) & 0xF])) << 4)) | (Byte.toUnsignedInt(bit4Reverse[((toReverse >> 12)) & 0xF]))));
    }

    private static int lcode(int length) {
        if (length == 255) 
            return 285;
        int code = 257;
        while (length >= 8) {
            code += 4;
            length >>= 1;
        }
        return code + length;
    }

    private static int dcode(int distance) {
        int code = 0;
        while (distance >= 4) {
            code += 2;
            distance >>= 1;
        }
        return code + distance;
    }
    public DeflaterHuffman() {
    }
    public static DeflaterHuffman _globalInstance;
    
    static {
        try { _globalInstance = new DeflaterHuffman(); } 
        catch(Exception e) { }
        bUFSIZE = 1 << ((DeflaterConstants.DEFAULT_MEM_LEVEL + 6));
        bL_ORDER = new int[] {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
        bit4Reverse = new byte[] {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        staticLCodes = new short[lITERAL_NUM];
        staticLLength = new byte[lITERAL_NUM];
        int i = 0;
        while (i < 144) {
            staticLCodes[i] = bitReverse(((0x030 + i)) << 8);
            staticLLength[i++] = (byte)8;
        }
        while (i < 256) {
            staticLCodes[i] = bitReverse((((0x190 - 144) + i)) << 7);
            staticLLength[i++] = (byte)9;
        }
        while (i < 280) {
            staticLCodes[i] = bitReverse((((0x000 - 256) + i)) << 9);
            staticLLength[i++] = (byte)7;
        }
        while (i < lITERAL_NUM) {
            staticLCodes[i] = bitReverse((((0x0c0 - 280) + i)) << 8);
            staticLLength[i++] = (byte)8;
        }
        staticDCodes = new short[dIST_NUM];
        staticDLength = new byte[dIST_NUM];
        for (i = 0; i < dIST_NUM; i++) {
            staticDCodes[i] = bitReverse(i << 11);
            staticDLength[i] = (byte)5;
        }
    }
}
