Method _buildLength

packages/alphatab/src/zip/DeflaterHuffman.ts:217–292

(childs: Int32Array)

    }

    private _buildLength(childs: Int32Array) {
        this.length = new Uint8Array(this.freqs.length);
        const numNodes = Math.floor(childs.length / 2);
        const numLeafs = Math.floor((numNodes + 1) / 2);
        let overflow = 0;

        for (let i = 0; i < this._maxLength; i++) {
            this._bitLengthCounts[i] = 0;
        }

        // First calculate optimal bit lengths
        const lengths = new Int32Array(numNodes);
        lengths[numNodes - 1] = 0;

        for (let i = numNodes - 1; i >= 0; i--) {
            if (childs[2 * i + 1] !== -1) {
                let bitLength = lengths[i] + 1;
                if (bitLength > this._maxLength) {
                    bitLength = this._maxLength;
                    overflow++;
                }
                lengths[childs[2 * i]] = bitLength;
                lengths[childs[2 * i + 1]] = bitLength;
            } else {
                // A leaf node
                const bitLength = lengths[i];
                this._bitLengthCounts[bitLength - 1]++;
                this.length[childs[2 * i]] = lengths[i];
            }
        }

        if (overflow === 0) {
            return;
        }

        let incrBitLen = this._maxLength - 1;
        do {
            // Find the first bit length which could increase:
            while (this._bitLengthCounts[--incrBitLen] === 0) {}

            // Move this node one down and remove a corresponding
            // number of overflow nodes.
            do {
                this._bitLengthCounts[incrBitLen]--;
                this._bitLengthCounts[++incrBitLen]++;
                overflow -= 1 << (this._maxLength - 1 - incrBitLen);
            } while (overflow > 0 && incrBitLen < this._maxLength - 1);
        } while (overflow > 0);

        /* We may have overshot above.  Move some nodes from maxLength to
         * maxLength-1 in that case.
         */
        this._bitLengthCounts[this._maxLength - 1] += overflow;
        this._bitLengthCounts[this._maxLength - 2] -= overflow;

        /* Now recompute all bit lengths, scanning in increasing
         * frequency.  It is simpler to reconstruct all lengths instead of
         * fixing only the wrong ones. This idea is taken from 'ar'