function zip_gen_bitlen()

in themes/docsy/static/js/deflate.js [989:1070]

• 60 lines of code
• 14 McCabe index (conditional complexity)

    function zip_gen_bitlen(desc) { // the tree descriptor
        var tree = desc.dyn_tree;
        var extra = desc.extra_bits;
        var base = desc.extra_base;
        var max_code = desc.max_code;
        var max_length = desc.max_length;
        var stree = desc.static_tree;
        var h;		// heap index
        var n, m;		// iterate over the tree elements
        var bits;		// bit length
        var xbits;		// extra bits
        var f;		// frequency
        var overflow = 0;	// number of elements with bit length too large

        for (bits = 0; bits <= zip_MAX_BITS; bits++)
            zip_bl_count[bits] = 0;

        /* In a first pass, compute the optimal bit lengths (which may
            * overflow in the case of the bit length tree).
            */
        tree[zip_heap[zip_heap_max]].dl = 0; // root of the heap

        for (h = zip_heap_max + 1; h < zip_HEAP_SIZE; h++) {
            n = zip_heap[h];
            bits = tree[tree[n].dl].dl + 1;
            if (bits > max_length) {
                bits = max_length;
                overflow++;
            }
            tree[n].dl = bits;
            // We overwrite tree[n].dl which is no longer needed

            if (n > max_code)
                continue; // not a leaf node

            zip_bl_count[bits]++;
            xbits = 0;
            if (n >= base)
                xbits = extra[n - base];
            f = tree[n].fc;
            zip_opt_len += f * (bits + xbits);
            if (stree != null)
                zip_static_len += f * (stree[n].dl + xbits);
        }
        if (overflow == 0)
            return;

        // This happens for example on obj2 and pic of the Calgary corpus

        // Find the first bit length which could increase:
        do {
            bits = max_length - 1;
            while (zip_bl_count[bits] == 0)
                bits--;
            zip_bl_count[bits]--;		// move one leaf down the tree
            zip_bl_count[bits + 1] += 2;	// move one overflow item as its brother
            zip_bl_count[max_length]--;
            /* The brother of the overflow item also moves one step up,
                * but this does not affect bl_count[max_length]
                */
            overflow -= 2;
        } while (overflow > 0);

        /* Now recompute all bit lengths, scanning in increasing frequency.
            * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
            * lengths instead of fixing only the wrong ones. This idea is taken
            * from 'ar' written by Haruhiko Okumura.)
            */
        for (bits = max_length; bits != 0; bits--) {
            n = zip_bl_count[bits];
            while (n != 0) {
                m = zip_heap[--h];
                if (m > max_code)
                    continue;
                if (tree[m].dl != bits) {
                    zip_opt_len += (bits - tree[m].dl) * tree[m].fc;
                    tree[m].fc = bits;
                }
                n--;
            }
        }
    }