DigitalState / Formio

 * $Id: rawdeflate.js,v 0.5 2013/04/09 14:25:38 dankogai Exp dankogai $

 *

 * GNU General Public License, version 2 (GPL-2.0)

 *   http://opensource.org/licenses/GPL-2.0

 * Original:

 *  http://www.onicos.com/staff/iz/amuse/javascript/expert/deflate.txt

 */

function JSDeflater(/*inbuff*/inbuf) {

    /* Copyright (C) 1999 Masanao Izumo <[email protected]>

     * Version: 1.0.1

     * LastModified: Dec 25 1999

     */

    var WSIZE = 32768,		// Sliding Window size

        zip_STORED_BLOCK = 0,

        zip_STATIC_TREES = 1,

        zip_DYN_TREES = 2,

        zip_DEFAULT_LEVEL = 6,

        zip_FULL_SEARCH = true,

        zip_INBUFSIZ = 32768,	// Input buffer size

        zip_INBUF_EXTRA = 64,	// Extra buffer

        zip_OUTBUFSIZ = 1024 * 8,

        zip_window_size = 2 * WSIZE,

        MIN_MATCH = 3,

        MAX_MATCH = 258,

        zip_BITS = 16,

        LIT_BUFSIZE = 0x2000,

        zip_HASH_BITS = 13,

        zip_DIST_BUFSIZE = LIT_BUFSIZE,

        zip_HASH_SIZE = 1 << zip_HASH_BITS,

        zip_HASH_MASK = zip_HASH_SIZE - 1,

        zip_WMASK = WSIZE - 1,

        zip_NIL = 0, // Tail of hash chains

        zip_TOO_FAR = 4096,

        zip_MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1,

        zip_MAX_DIST = WSIZE - zip_MIN_LOOKAHEAD,

        zip_SMALLEST = 1,

        zip_MAX_BITS = 15,

        zip_MAX_BL_BITS = 7,

        zip_LENGTH_CODES = 29,

        zip_LITERALS = 256,

        zip_END_BLOCK = 256,

        zip_L_CODES = zip_LITERALS + 1 + zip_LENGTH_CODES,

        zip_D_CODES = 30,

        zip_BL_CODES = 19,

        zip_REP_3_6 = 16,

        zip_REPZ_3_10 = 17,

        zip_REPZ_11_138 = 18,

        zip_HEAP_SIZE = 2 * zip_L_CODES + 1,

        zip_H_SHIFT = parseInt((zip_HASH_BITS + MIN_MATCH - 1) / MIN_MATCH);

    var zip_free_queue, zip_qhead, zip_qtail, zip_initflag, zip_outbuf = null, zip_outcnt, zip_outoff, zip_complete,

        zip_window, zip_d_buf, zip_l_buf, zip_prev, zip_bi_buf, zip_bi_valid, zip_block_start, zip_ins_h, zip_hash_head,

        zip_prev_match, zip_match_available, zip_match_length, zip_prev_length, zip_strstart, zip_match_start, zip_eofile,

        zip_lookahead, zip_max_chain_length, zip_max_lazy_match, zip_compr_level, zip_good_match, zip_nice_match,

        zip_dyn_ltree, zip_dyn_dtree, zip_static_ltree, zip_static_dtree, zip_bl_tree, zip_l_desc, zip_d_desc, zip_bl_desc,

        zip_bl_count, zip_heap, zip_heap_len, zip_heap_max, zip_depth, zip_length_code, zip_dist_code, zip_base_length,

        zip_base_dist, zip_flag_buf, zip_last_lit, zip_last_dist, zip_last_flags, zip_flags, zip_flag_bit, zip_opt_len,

        zip_static_len, zip_deflate_data, zip_deflate_pos;

    var zip_DeflateCT = function () {

        this.fc = 0; // frequency count or bit string

        this.dl = 0; // father node in Huffman tree or length of bit string

    };

    var zip_DeflateTreeDesc = function () {

        this.dyn_tree = null;	// the dynamic tree

        this.static_tree = null;	// corresponding static tree or NULL

        this.extra_bits = null;	// extra bits for each code or NULL

        this.extra_base = 0;	// base index for extra_bits

        this.elems = 0;		// max number of elements in the tree

        this.max_length = 0;	// max bit length for the codes

        this.max_code = 0;		// largest code with non zero frequency

    };

    /* Values for max_lazy_match, good_match and max_chain_length, depending on

     * the desired pack level (0..9). The values given below have been tuned to

     * exclude worst case performance for pathological files. Better values may be

     * found for specific files.

     */

    var zip_DeflateConfiguration = function (a, b, c, d) {

        this.good_length = a; // reduce lazy search above this match length

        this.max_lazy = b;    // do not perform lazy search above this match length

        this.nice_length = c; // quit search above this match length

        this.max_chain = d;

    };

    var zip_DeflateBuffer = function () {

        this.next = null;

        this.len = 0;

        this.ptr = new Array(zip_OUTBUFSIZ);

        this.off = 0;

    };

    /* constant tables */

        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0);

        0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13);

        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7);

        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15);

    /* routines (deflate) */

    var zip_deflate_start = function (level) {

        var i;

        if (!level)

            level = zip_DEFAULT_LEVEL;

        else if (level < 1)

            level = 1;

        else if (level > 9)

            level = 9;

        zip_compr_level = level;

        zip_initflag = false;

        zip_eofile = false;

        if (zip_outbuf != null)

            return;

        zip_free_queue = zip_qhead = zip_qtail = null;

        zip_outbuf = new Array(zip_OUTBUFSIZ);

        zip_window = new Array(zip_window_size);

        zip_l_buf = new Array(zip_INBUFSIZ + zip_INBUF_EXTRA);

        zip_prev = new Array(1 << zip_BITS);

        zip_dyn_ltree = new Array(zip_HEAP_SIZE);

        zip_dyn_dtree = new Array(2 * zip_D_CODES + 1);

        zip_static_ltree = new Array(zip_L_CODES + 2);

        zip_static_dtree = new Array(zip_D_CODES);

        zip_bl_tree = new Array(2 * zip_BL_CODES + 1);

        zip_bl_count = new Array(zip_MAX_BITS + 1);

        zip_heap = new Array(2 * zip_L_CODES + 1);

        zip_depth = new Array(2 * zip_L_CODES + 1);

        zip_length_code = new Array(MAX_MATCH - MIN_MATCH + 1);

        zip_dist_code = new Array(512);

        zip_base_length = new Array(zip_LENGTH_CODES);

        zip_base_dist = new Array(zip_D_CODES);

    };

    var zip_deflate_end = function () {

        zip_free_queue = zip_qhead = zip_qtail = null;

        zip_outbuf = null;

        zip_window = null;

        zip_d_buf = null;

        zip_l_buf = null;

        zip_prev = null;

        zip_dyn_ltree = null;

        zip_dyn_dtree = null;

        zip_static_ltree = null;

        zip_static_dtree = null;

        zip_bl_tree = null;

        zip_l_desc = null;

        zip_d_desc = null;

        zip_bl_desc = null;

        zip_bl_count = null;

        zip_heap = null;

        zip_depth = null;

        zip_length_code = null;

        zip_dist_code = null;

        zip_base_length = null;

        zip_base_dist = null;

        zip_flag_buf = null;

    };

    var zip_reuse_queue = function (p) {

        p.next = zip_free_queue;

        zip_free_queue = p;

    };

    var zip_new_queue = function () {

        var p;

        if (zip_free_queue != null) {

            p = zip_free_queue;

            zip_free_queue = zip_free_queue.next;

        }

        else

        p.next = null;

        p.len = p.off = 0;

        return p;

    };

    var zip_head1 = function (i) {

        return zip_prev[WSIZE + i];

    };

    var zip_head2 = function (i, val) {

        return zip_prev[WSIZE + i] = val;

    };

    /* put_byte is used for the compressed output, put_ubyte for the

     * uncompressed output. However unlzw() uses window for its

     * suffix table instead of its output buffer, so it does not use put_ubyte

     * (to be cleaned up).

     */

    var zip_put_byte = function (c) {

        zip_outbuf[zip_outoff + zip_outcnt++] = c;

        if (zip_outoff + zip_outcnt == zip_OUTBUFSIZ)

            zip_qoutbuf();

    };

    /* Output a 16 bit value, lsb first */

    var zip_put_short = function (w) {

        w &= 0xffff;

        if (zip_outoff + zip_outcnt < zip_OUTBUFSIZ - 2) {

            zip_outbuf[zip_outoff + zip_outcnt++] = (w & 0xff);

            zip_outbuf[zip_outoff + zip_outcnt++] = (w >>> 8);

        } else {

            zip_put_byte(w & 0xff);

            zip_put_byte(w >>> 8);

        }

    };

    /* ==========================================================================

     * Insert string s in the dictionary and set match_head to the previous head

     * of the hash chain (the most recent string with same hash key). Return

     * the previous length of the hash chain.

     * IN  assertion: all calls to to INSERT_STRING are made with consecutive

     *    input characters and the first MIN_MATCH bytes of s are valid

     *    (except for the last MIN_MATCH-1 bytes of the input file).

     */

    var zip_INSERT_STRING = function () {

        zip_ins_h = ((zip_ins_h << zip_H_SHIFT)

            ^ (zip_window[zip_strstart + MIN_MATCH - 1] & 0xff))

            & zip_HASH_MASK;

        zip_hash_head = zip_head1(zip_ins_h);

        zip_prev[zip_strstart & zip_WMASK] = zip_hash_head;

        zip_head2(zip_ins_h, zip_strstart);

    };

    /* Send a code of the given tree. c and tree must not have side effects */

    var zip_SEND_CODE = function (c, tree) {

        zip_send_bits(tree[c].fc, tree[c].dl);

    };

    /* Mapping from a distance to a distance code. dist is the distance - 1 and

     * must not have side effects. dist_code[256] and dist_code[257] are never

     * used.

     */

    var zip_D_CODE = function (dist) {

        return (dist < 256 ? zip_dist_code[dist]

            : zip_dist_code[256 + (dist >> 7)]) & 0xff;

    };

    /* ==========================================================================

     * Compares to subtrees, using the tree depth as tie breaker when

     * the subtrees have equal frequency. This minimizes the worst case length.

     */

    var zip_SMALLER = function (tree, n, m) {

        return tree[n].fc < tree[m].fc ||

            (tree[n].fc == tree[m].fc && zip_depth[n] <= zip_depth[m]);

    };

    /* ==========================================================================

     * read string data

     */

    var zip_read_buff = function (buff, offset, n) {

        var i;

            buff[offset + i] =

                zip_deflate_data[zip_deflate_pos++] & 0xff;

        return i;

    };

    /* ==========================================================================

     * Initialize the "longest match" routines for a new file

     */

    var zip_lm_init = function () {

        var j;

        /* Initialize the hash table. */

        for (j = 0; j < zip_HASH_SIZE; j++)

            zip_prev[WSIZE + j] = 0;

        zip_max_lazy_match = zip_configuration_table[zip_compr_level].max_lazy;

        zip_good_match = zip_configuration_table[zip_compr_level].good_length;

        if (!zip_FULL_SEARCH)

            zip_nice_match = zip_configuration_table[zip_compr_level].nice_length;

        zip_max_chain_length = zip_configuration_table[zip_compr_level].max_chain;

        zip_strstart = 0;

        zip_block_start = 0;

        zip_lookahead = zip_read_buff(zip_window, 0, 2 * WSIZE);

        if (zip_lookahead <= 0) {

            zip_eofile = true;

            zip_lookahead = 0;

            return;

        }

        zip_eofile = false;

        /* Make sure that we always have enough lookahead. This is important

         * if input comes from a device such as a tty.

         */

        while (zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile)

            zip_fill_window();

        /* If lookahead < MIN_MATCH, ins_h is garbage, but this is

         * not important since only literal bytes will be emitted.

         */

        zip_ins_h = 0;

        for (j = 0; j < MIN_MATCH - 1; j++) {

        }

    };

    /* ==========================================================================

     * Set match_start to the longest match starting at the given string and

     * return its length. Matches shorter or equal to prev_length are discarded,

     * in which case the result is equal to prev_length and match_start is

     * garbage.

     * IN assertions: cur_match is the head of the hash chain for the current

     *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1

     */

    var zip_longest_match = function (cur_match) {

        var chain_length = zip_max_chain_length; // max hash chain length

        var scanp = zip_strstart; // current string

        var matchp;		// matched string

        var len;		// length of current match

        var best_len = zip_prev_length;	// best match length so far

        /* Stop when cur_match becomes <= limit. To simplify the code,

         * we prevent matches with the string of window index 0.

         */

        var limit = (zip_strstart > zip_MAX_DIST ? zip_strstart - zip_MAX_DIST : zip_NIL);

        var strendp = zip_strstart + MAX_MATCH;

        var scan_end1 = zip_window[scanp + best_len - 1];

        var scan_end = zip_window[scanp + best_len];

        /* Do not waste too much time if we already have a good match: */

        if (zip_prev_length >= zip_good_match)

            chain_length >>= 2;

        do {

            matchp = cur_match;

            /* Skip to next match if the match length cannot increase

             * or if the match length is less than 2:

             */

            if (zip_window[matchp + best_len] != scan_end ||

                zip_window[matchp + best_len - 1] != scan_end1 ||

                zip_window[matchp] != zip_window[scanp] ||

                zip_window[++matchp] != zip_window[scanp + 1]) {

                continue;

            }

            /* The check at best_len-1 can be removed because it will be made

             * again later. (This heuristic is not always a win.)

             * It is not necessary to compare scan[2] and match[2] since they

             * are always equal when the other bytes match, given that

             * the hash keys are equal and that HASH_BITS >= 8.

             */

            scanp += 2;

            matchp++;

            /* We check for insufficient lookahead only every 8th comparison;

             * the 256th check will be made at strstart+258.

             */

            } while (zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                zip_window[++scanp] == zip_window[++matchp] &&

                scanp < strendp);

            len = MAX_MATCH - (strendp - scanp);

            scanp = strendp - MAX_MATCH;

            if (len > best_len) {

                zip_match_start = cur_match;

                best_len = len;

                if (zip_FULL_SEARCH) {

                    if (len >= MAX_MATCH) break;

                } else {

                    if (len >= zip_nice_match) break;

                }

                scan_end1 = zip_window[scanp + best_len - 1];

                scan_end = zip_window[scanp + best_len];

            }

        } while ((cur_match = zip_prev[cur_match & zip_WMASK]) > limit

            && --chain_length != 0);

        return best_len;

    };

    /* ==========================================================================

     * Fill the window when the lookahead becomes insufficient.

     * Updates strstart and lookahead, and sets eofile if end of input file.

     * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0

     * OUT assertions: at least one byte has been read, or eofile is set;

     *    file reads are performed for at least two bytes (required for the

     *    translate_eol option).

     */

    var zip_fill_window = function () {

        var n, m;

        // Amount of free space at the end of the window.

        var more = zip_window_size - zip_lookahead - zip_strstart;

        /* If the window is almost full and there is insufficient lookahead,

         * move the upper half to the lower one to make room in the upper half.

         */

        if (more == -1) {

            /* Very unlikely, but possible on 16 bit machine if strstart == 0

             * and lookahead == 1 (input done one byte at time)

             */

            more--;

        } else if (zip_strstart >= WSIZE + zip_MAX_DIST) {

            /* By the IN assertion, the window is not empty so we can't confuse

             * more == 0 with more == 64K on a 16 bit machine.

             */

            for (n = 0; n < WSIZE; n++)

                zip_window[n] = zip_window[n + WSIZE];

            zip_match_start -= WSIZE;

            zip_strstart -= WSIZE;

            /* we now have strstart >= MAX_DIST: */

            zip_block_start -= WSIZE;

            for (n = 0; n < zip_HASH_SIZE; n++) {

                m = zip_head1(n);

                zip_head2(n, m >= WSIZE ? m - WSIZE : zip_NIL);

            }

            for (n = 0; n < WSIZE; n++) {

                /* If n is not on any hash chain, prev[n] is garbage but

                 * its value will never be used.

                 */

                m = zip_prev[n];

                zip_prev[n] = (m >= WSIZE ? m - WSIZE : zip_NIL);

            }

            more += WSIZE;

        }

        // At this point, more >= 2

        if (!zip_eofile) {

            if (n <= 0)

                zip_eofile = true;

            else

                zip_lookahead += n;

        }

    };

    /* ==========================================================================

     * Processes a new input file and return its compressed length. This

     * function does not perform lazy evaluationof matches and inserts

     * new strings in the dictionary only for unmatched strings or for short

     * matches. It is used only for the fast compression options.

     */

    var zip_deflate_fast = function () {

            var flush; // set if current block must be flushed

            /* Insert the string window[strstart .. strstart+2] in the

             * dictionary, and set hash_head to the head of the hash chain:

             */

            zip_INSERT_STRING();

            /* Find the longest match, discarding those <= prev_length.

             * At this point we have always match_length < MIN_MATCH

             */

            if (zip_hash_head != zip_NIL &&

                /* To simplify the code, we prevent matches with the string

                 * of window index 0 (in particular we have to avoid a match

                 * of the string with itself at the start of the input file).

                 */

                zip_match_length = zip_longest_match(zip_hash_head);

                /* longest_match() sets match_start */

                    zip_match_length = zip_lookahead;

            }

                flush = zip_ct_tally(zip_strstart - zip_match_start,

                    zip_match_length - MIN_MATCH);

                zip_lookahead -= zip_match_length;

                /* Insert new strings in the hash table only if the match length

                 * is not too large. This saves time but degrades compression.

                 */

                if (zip_match_length <= zip_max_lazy_match) {

                    zip_match_length--; // string at strstart already in hash table

                    do {

                        zip_strstart++;

                        zip_INSERT_STRING();

                        /* strstart never exceeds WSIZE-MAX_MATCH, so there are

                         * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH

                         * these bytes are garbage, but it does not matter since

                         * the next lookahead bytes will be emitted as literals.

                         */

                    } while (--zip_match_length != 0);

                } else {

                    zip_strstart += zip_match_length;

                    zip_match_length = 0;

                    zip_ins_h = zip_window[zip_strstart] & 0xff;

                }

            } else {

                /* No match, output a literal byte */

                flush = zip_ct_tally(0, zip_window[zip_strstart] & 0xff);

                zip_lookahead--;

                zip_strstart++;

            }

            if (flush) {

                zip_flush_block(0);

                zip_block_start = zip_strstart;

            }

            /* Make sure that we always have enough lookahead, except

             * at the end of the input file. We need MAX_MATCH bytes

             * for the next match, plus MIN_MATCH bytes to insert the

             * string following the next match.

             */

            while (zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile)

                zip_fill_window();

        }

    };

    var zip_deflate_better = function () {

        /* Process the input block. */

            /* Insert the string window[strstart .. strstart+2] in the

             * dictionary, and set hash_head to the head of the hash chain:

             */

            zip_INSERT_STRING();

            /* Find the longest match, discarding those <= prev_length.

             */

            zip_prev_match = zip_match_start;

            zip_match_length = MIN_MATCH - 1;

            if (zip_hash_head != zip_NIL &&

                /* To simplify the code, we prevent matches with the string

                 * of window index 0 (in particular we have to avoid a match

                 * of the string with itself at the start of the input file).

                 */

                zip_match_length = zip_longest_match(zip_hash_head);

                /* longest_match() sets match_start */

                    zip_match_length = zip_lookahead;

                /* Ignore a length 3 match if it is too distant: */

                if (zip_match_length == MIN_MATCH &&

                    zip_strstart - zip_match_start > zip_TOO_FAR) {

                    /* If prev_match is also MIN_MATCH, match_start is garbage

                     * but we will ignore the current match anyway.

                     */

                    zip_match_length--;

                }

            }

            /* If there was a match at the previous step and the current

             * match is not better, output the previous match:

             */

            if (zip_prev_length >= MIN_MATCH &&

                zip_match_length <= zip_prev_length) {

                var flush; // set if current block must be flushed

                    zip_prev_length - MIN_MATCH);

                /* Insert in hash table all strings up to the end of the match.

                 * strstart-1 and strstart are already inserted.

                 */

                zip_lookahead -= zip_prev_length - 1;

                zip_prev_length -= 2;

                do {

                    zip_strstart++;

                    zip_INSERT_STRING();

                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are

                     * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH

                     * these bytes are garbage, but it does not matter since the

                     * next lookahead bytes will always be emitted as literals.

                     */

                } while (--zip_prev_length != 0);

                zip_match_available = 0;

                zip_match_length = MIN_MATCH - 1;

                if (flush) {

                    zip_flush_block(0);

                    zip_block_start = zip_strstart;

                }

                /* If there was no match at the previous position, output a

                 * single literal. If there was a match but the current match

                 * is longer, truncate the previous match to a single literal.

                 */

                if (zip_ct_tally(0, zip_window[zip_strstart - 1] & 0xff)) {

                    zip_flush_block(0);

                    zip_block_start = zip_strstart;

                }

                zip_strstart++;

                zip_lookahead--;

            } else {

                /* There is no previous match to compare with, wait for

                 * the next step to decide.

                 */

                zip_match_available = 1;

                zip_strstart++;

                zip_lookahead--;

            }

            /* Make sure that we always have enough lookahead, except

             * at the end of the input file. We need MAX_MATCH bytes

             * for the next match, plus MIN_MATCH bytes to insert the

             * string following the next match.

             */

            while (zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile)

                zip_fill_window();

        }

    };

    var zip_init_deflate = function () {

        if (zip_eofile)

            return;

        zip_bi_buf = 0;

        zip_bi_valid = 0;

        zip_ct_init();

        zip_lm_init();

        zip_qhead = null;

        zip_outcnt = 0;

        zip_outoff = 0;

        zip_match_available = 0;

        if (zip_compr_level <= 3) {

            zip_prev_length = MIN_MATCH - 1;

            zip_match_length = 0;

        }

        else {

            zip_match_length = MIN_MATCH - 1;

            zip_match_available = 0;

            zip_match_available = 0;

        }

        zip_complete = false;

    };

    /* ==========================================================================

     * Same as above, but achieves better compression. We use a lazy

     * evaluation for matches: a match is finally adopted only if there is

     * no better match at the next window position.

     */

    var zip_deflate_internal = function (buff, off, buff_size) {

        var n;

        if (!zip_initflag) {

            zip_init_deflate();

            zip_initflag = true;

            if (zip_lookahead == 0) { // empty

                zip_complete = true;

                return 0;

            }

        }

        if ((n = zip_qcopy(buff, off, buff_size)) == buff_size)

            return buff_size;

        if (zip_complete)

            return n;

        if (zip_compr_level <= 3) // optimized for speed

            zip_deflate_fast();

        else

            zip_deflate_better();

        if (zip_lookahead == 0) {

            if (zip_match_available != 0)

                zip_ct_tally(0, zip_window[zip_strstart - 1] & 0xff);

            zip_flush_block(1);

            zip_complete = true;

        }

        return n + zip_qcopy(buff, n + off, buff_size - n);

    };

    var zip_qcopy = function (buff, off, buff_size) {

        var n, i, j;

        n = 0;

            i = buff_size - n;

            if (i > zip_qhead.len)

                i = zip_qhead.len;

            for (j = 0; j < i; j++)

                buff[off + n + j] = zip_qhead.ptr[zip_qhead.off + j];

            zip_qhead.off += i;

            zip_qhead.len -= i;

            n += i;

            if (zip_qhead.len == 0) {

                var p;

                p = zip_qhead;

                zip_qhead = zip_qhead.next;

                zip_reuse_queue(p);

            }

        }

        if (n == buff_size)

            return n;

        if (zip_outoff < zip_outcnt) {

            i = buff_size - n;

            if (i > zip_outcnt - zip_outoff)

                i = zip_outcnt - zip_outoff;

            // System.arraycopy(outbuf, outoff, buff, off + n, i);

            for (j = 0; j < i; j++)

                buff[off + n + j] = zip_outbuf[zip_outoff + j];

            zip_outoff += i;

            n += i;

            if (zip_outcnt == zip_outoff)

                zip_outcnt = zip_outoff = 0;

        }

        return n;

    };

    /* ==========================================================================

     * Allocate the match buffer, initialize the various tables and save the

     * location of the internal file attribute (ascii/binary) and method

     * (DEFLATE/STORE).

     */

    var zip_ct_init = function () {

        var n;	// iterates over tree elements

        var bits;	// bit counter

        var length;	// length value

        var code;	// code value

        var dist;	// distance index

        if (zip_static_dtree[0].dl != 0) return; // ct_init already called

        zip_l_desc.dyn_tree = zip_dyn_ltree;

        zip_l_desc.static_tree = zip_static_ltree;

        zip_l_desc.extra_bits = zip_extra_lbits;

        zip_l_desc.extra_base = zip_LITERALS + 1;

        zip_l_desc.elems = zip_L_CODES;

        zip_l_desc.max_length = zip_MAX_BITS;

        zip_l_desc.max_code = 0;

        zip_d_desc.dyn_tree = zip_dyn_dtree;

        zip_d_desc.static_tree = zip_static_dtree;

        zip_d_desc.extra_bits = zip_extra_dbits;

        zip_d_desc.extra_base = 0;

        zip_d_desc.elems = zip_D_CODES;

        zip_d_desc.max_length = zip_MAX_BITS;

        zip_d_desc.max_code = 0;

        zip_bl_desc.dyn_tree = zip_bl_tree;

        zip_bl_desc.static_tree = null;

        zip_bl_desc.extra_bits = zip_extra_blbits;

        zip_bl_desc.extra_base = 0;

        zip_bl_desc.elems = zip_BL_CODES;

        zip_bl_desc.max_length = zip_MAX_BL_BITS;

        zip_bl_desc.max_code = 0;

        // Initialize the mapping length (0..255) -> length code (0..28)

        length = 0;

        for (code = 0; code < zip_LENGTH_CODES - 1; code++) {

            zip_base_length[code] = length;

            for (n = 0; n < (1 << zip_extra_lbits[code]); n++)

                zip_length_code[length++] = code;

        }

        /* Note that the length 255 (match length 258) can be represented

         * in two different ways: code 284 + 5 bits or code 285, so we

         * overwrite length_code[255] to use the best encoding:

         */

        zip_length_code[length - 1] = code;

        /* Initialize the mapping dist (0..32K) -> dist code (0..29) */

        dist = 0;

        for (code = 0; code < 16; code++) {

            zip_base_dist[code] = dist;

            for (n = 0; n < (1 << zip_extra_dbits[code]); n++) {

                zip_dist_code[dist++] = code;

            }

        }

        dist >>= 7; // from now on, all distances are divided by 128

        for (; code < zip_D_CODES; code++) {

            zip_base_dist[code] = dist << 7;

            for (n = 0; n < (1 << (zip_extra_dbits[code] - 7)); n++)

                zip_dist_code[256 + dist++] = code;

        }

        // Construct the codes of the static literal tree

        for (bits = 0; bits <= zip_MAX_BITS; bits++)

            zip_bl_count[bits] = 0;

        n = 0;

        while (n <= 143) {

            zip_static_ltree[n++].dl = 8;

            zip_bl_count[8]++;

        }

        while (n <= 255) {

            zip_static_ltree[n++].dl = 9;

            zip_bl_count[9]++;

        }

        while (n <= 279) {

            zip_static_ltree[n++].dl = 7;

            zip_bl_count[7]++;

        }

        while (n <= 287) {

            zip_static_ltree[n++].dl = 8;

            zip_bl_count[8]++;

        }

        /* Codes 286 and 287 do not exist, but we must include them in the

         * tree construction to get a canonical Huffman tree (longest code

         * all ones)

         */

        zip_gen_codes(zip_static_ltree, zip_L_CODES + 1);

        /* The static distance tree is trivial: */

        for (n = 0; n < zip_D_CODES; n++) {

            zip_static_dtree[n].dl = 5;