extraction-interface: geotemco/lib/jszip/jszip-deflate.js annotate

annotate geotemco/lib/jszip/jszip-deflate.js @ 23:a879f6b9d166

modification for select-move-taglist: tags don't appear to be duplicated in other topics.

author	Zoe Hong <zhong@mpiwg-berlin.mpg.de>
date	Wed, 25 Feb 2015 10:59:45 +0100
parents	b12c99b7c3f0
children

rev	line source
0 b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1 /*
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	2 * Port of a script by Masanao Izumo.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	3 *
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	4 * Only changes : wrap all the variables in a function and add the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	5 * main function to JSZip (DEFLATE compression method).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	6 * Everything else was written by M. Izumo.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	7 *
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	8 * Original code can be found here: http://www.onicos.com/staff/iz/amuse/javascript/expert/deflate.txt
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	9 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	10
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	11 if(!JSZip) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	12 throw "JSZip not defined";
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	13 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	14
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	15 /*
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	16 * Original:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	17 * http://www.onicos.com/staff/iz/amuse/javascript/expert/deflate.txt
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	18 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	19
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	20 (function(){
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	21
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	22 /* Copyright (C) 1999 Masanao Izumo <iz@onicos.co.jp>
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	23 * Version: 1.0.1
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	24 * LastModified: Dec 25 1999
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	25 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	26
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	27 /* Interface:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	28 * data = zip_deflate(src);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	29 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	30
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	31 /* constant parameters */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	32 var zip_WSIZE = 32768; // Sliding Window size
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	33 var zip_STORED_BLOCK = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	34 var zip_STATIC_TREES = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	35 var zip_DYN_TREES = 2;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	36
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	37 /* for deflate */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	38 var zip_DEFAULT_LEVEL = 6;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	39 var zip_FULL_SEARCH = true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	40 var zip_INBUFSIZ = 32768; // Input buffer size
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	41 var zip_INBUF_EXTRA = 64; // Extra buffer
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	42 var zip_OUTBUFSIZ = 1024 * 8;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	43 var zip_window_size = 2 * zip_WSIZE;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	44 var zip_MIN_MATCH = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	45 var zip_MAX_MATCH = 258;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	46 var zip_BITS = 16;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	47 // for SMALL_MEM
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	48 var zip_LIT_BUFSIZE = 0x2000;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	49 var zip_HASH_BITS = 13;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	50 // for MEDIUM_MEM
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	51 // var zip_LIT_BUFSIZE = 0x4000;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	52 // var zip_HASH_BITS = 14;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	53 // for BIG_MEM
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	54 // var zip_LIT_BUFSIZE = 0x8000;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	55 // var zip_HASH_BITS = 15;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	56 if(zip_LIT_BUFSIZE > zip_INBUFSIZ)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	57 alert("error: zip_INBUFSIZ is too small");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	58 if((zip_WSIZE<<1) > (1<<zip_BITS))
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	59 alert("error: zip_WSIZE is too large");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	60 if(zip_HASH_BITS > zip_BITS-1)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	61 alert("error: zip_HASH_BITS is too large");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	62 if(zip_HASH_BITS < 8 \|\| zip_MAX_MATCH != 258)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	63 alert("error: Code too clever");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	64 var zip_DIST_BUFSIZE = zip_LIT_BUFSIZE;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	65 var zip_HASH_SIZE = 1 << zip_HASH_BITS;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	66 var zip_HASH_MASK = zip_HASH_SIZE - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	67 var zip_WMASK = zip_WSIZE - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	68 var zip_NIL = 0; // Tail of hash chains
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	69 var zip_TOO_FAR = 4096;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	70 var zip_MIN_LOOKAHEAD = zip_MAX_MATCH + zip_MIN_MATCH + 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	71 var zip_MAX_DIST = zip_WSIZE - zip_MIN_LOOKAHEAD;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	72 var zip_SMALLEST = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	73 var zip_MAX_BITS = 15;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	74 var zip_MAX_BL_BITS = 7;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	75 var zip_LENGTH_CODES = 29;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	76 var zip_LITERALS =256;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	77 var zip_END_BLOCK = 256;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	78 var zip_L_CODES = zip_LITERALS + 1 + zip_LENGTH_CODES;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	79 var zip_D_CODES = 30;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	80 var zip_BL_CODES = 19;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	81 var zip_REP_3_6 = 16;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	82 var zip_REPZ_3_10 = 17;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	83 var zip_REPZ_11_138 = 18;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	84 var zip_HEAP_SIZE = 2 * zip_L_CODES + 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	85 var zip_H_SHIFT = parseInt((zip_HASH_BITS + zip_MIN_MATCH - 1) /
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	86 zip_MIN_MATCH);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	87
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	88 /* variables */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	89 var zip_free_queue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	90 var zip_qhead, zip_qtail;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	91 var zip_initflag;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	92 var zip_outbuf = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	93 var zip_outcnt, zip_outoff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	94 var zip_complete;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	95 var zip_window;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	96 var zip_d_buf;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	97 var zip_l_buf;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	98 var zip_prev;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	99 var zip_bi_buf;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	100 var zip_bi_valid;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	101 var zip_block_start;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	102 var zip_ins_h;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	103 var zip_hash_head;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	104 var zip_prev_match;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	105 var zip_match_available;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	106 var zip_match_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	107 var zip_prev_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	108 var zip_strstart;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	109 var zip_match_start;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	110 var zip_eofile;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	111 var zip_lookahead;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	112 var zip_max_chain_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	113 var zip_max_lazy_match;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	114 var zip_compr_level;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	115 var zip_good_match;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	116 var zip_nice_match;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	117 var zip_dyn_ltree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	118 var zip_dyn_dtree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	119 var zip_static_ltree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	120 var zip_static_dtree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	121 var zip_bl_tree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	122 var zip_l_desc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	123 var zip_d_desc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	124 var zip_bl_desc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	125 var zip_bl_count;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	126 var zip_heap;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	127 var zip_heap_len;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	128 var zip_heap_max;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	129 var zip_depth;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	130 var zip_length_code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	131 var zip_dist_code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	132 var zip_base_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	133 var zip_base_dist;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	134 var zip_flag_buf;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	135 var zip_last_lit;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	136 var zip_last_dist;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	137 var zip_last_flags;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	138 var zip_flags;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	139 var zip_flag_bit;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	140 var zip_opt_len;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	141 var zip_static_len;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	142 var zip_deflate_data;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	143 var zip_deflate_pos;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	144
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	145 /* objects (deflate) */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	146
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	147 var zip_DeflateCT = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	148 this.fc = 0; // frequency count or bit string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	149 this.dl = 0; // father node in Huffman tree or length of bit string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	150 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	151
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	152 var zip_DeflateTreeDesc = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	153 this.dyn_tree = null; // the dynamic tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	154 this.static_tree = null; // corresponding static tree or NULL
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	155 this.extra_bits = null; // extra bits for each code or NULL
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	156 this.extra_base = 0; // base index for extra_bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	157 this.elems = 0; // max number of elements in the tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	158 this.max_length = 0; // max bit length for the codes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	159 this.max_code = 0; // largest code with non zero frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	160 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	161
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	162 /* Values for max_lazy_match, good_match and max_chain_length, depending on
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	163 * the desired pack level (0..9). The values given below have been tuned to
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	164 * exclude worst case performance for pathological files. Better values may be
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	165 * found for specific files.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	166 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	167 var zip_DeflateConfiguration = function(a, b, c, d) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	168 this.good_length = a; // reduce lazy search above this match length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	169 this.max_lazy = b; // do not perform lazy search above this match length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	170 this.nice_length = c; // quit search above this match length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	171 this.max_chain = d;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	172 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	173
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	174 var zip_DeflateBuffer = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	175 this.next = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	176 this.len = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	177 this.ptr = new Array(zip_OUTBUFSIZ);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	178 this.off = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	179 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	180
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	181 /* constant tables */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	182 var zip_extra_lbits = new Array(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	183 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);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	184 var zip_extra_dbits = new Array(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	185 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);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	186 var zip_extra_blbits = new Array(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	187 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	188 var zip_bl_order = new Array(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	189 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	190 var zip_configuration_table = new Array(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	191 new zip_DeflateConfiguration(0, 0, 0, 0),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	192 new zip_DeflateConfiguration(4, 4, 8, 4),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	193 new zip_DeflateConfiguration(4, 5, 16, 8),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	194 new zip_DeflateConfiguration(4, 6, 32, 32),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	195 new zip_DeflateConfiguration(4, 4, 16, 16),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	196 new zip_DeflateConfiguration(8, 16, 32, 32),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	197 new zip_DeflateConfiguration(8, 16, 128, 128),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	198 new zip_DeflateConfiguration(8, 32, 128, 256),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	199 new zip_DeflateConfiguration(32, 128, 258, 1024),
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	200 new zip_DeflateConfiguration(32, 258, 258, 4096));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	201
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	202
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	203 /* routines (deflate) */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	204
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	205 var zip_deflate_start = function(level) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	206 var i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	207
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	208 if(!level)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	209 level = zip_DEFAULT_LEVEL;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	210 else if(level < 1)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	211 level = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	212 else if(level > 9)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	213 level = 9;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	214
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	215 zip_compr_level = level;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	216 zip_initflag = false;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	217 zip_eofile = false;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	218 if(zip_outbuf != null)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	219 return;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	220
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	221 zip_free_queue = zip_qhead = zip_qtail = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	222 zip_outbuf = new Array(zip_OUTBUFSIZ);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	223 zip_window = new Array(zip_window_size);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	224 zip_d_buf = new Array(zip_DIST_BUFSIZE);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	225 zip_l_buf = new Array(zip_INBUFSIZ + zip_INBUF_EXTRA);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	226 zip_prev = new Array(1 << zip_BITS);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	227 zip_dyn_ltree = new Array(zip_HEAP_SIZE);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	228 for(i = 0; i < zip_HEAP_SIZE; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	229 zip_dyn_ltree[i] = new zip_DeflateCT();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	230 zip_dyn_dtree = new Array(2*zip_D_CODES+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	231 for(i = 0; i < 2*zip_D_CODES+1; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	232 zip_dyn_dtree[i] = new zip_DeflateCT();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	233 zip_static_ltree = new Array(zip_L_CODES+2);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	234 for(i = 0; i < zip_L_CODES+2; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	235 zip_static_ltree[i] = new zip_DeflateCT();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	236 zip_static_dtree = new Array(zip_D_CODES);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	237 for(i = 0; i < zip_D_CODES; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	238 zip_static_dtree[i] = new zip_DeflateCT();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	239 zip_bl_tree = new Array(2*zip_BL_CODES+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	240 for(i = 0; i < 2*zip_BL_CODES+1; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	241 zip_bl_tree[i] = new zip_DeflateCT();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	242 zip_l_desc = new zip_DeflateTreeDesc();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	243 zip_d_desc = new zip_DeflateTreeDesc();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	244 zip_bl_desc = new zip_DeflateTreeDesc();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	245 zip_bl_count = new Array(zip_MAX_BITS+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	246 zip_heap = new Array(2*zip_L_CODES+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	247 zip_depth = new Array(2*zip_L_CODES+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	248 zip_length_code = new Array(zip_MAX_MATCH-zip_MIN_MATCH+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	249 zip_dist_code = new Array(512);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	250 zip_base_length = new Array(zip_LENGTH_CODES);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	251 zip_base_dist = new Array(zip_D_CODES);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	252 zip_flag_buf = new Array(parseInt(zip_LIT_BUFSIZE / 8));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	253 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	254
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	255 var zip_deflate_end = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	256 zip_free_queue = zip_qhead = zip_qtail = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	257 zip_outbuf = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	258 zip_window = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	259 zip_d_buf = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	260 zip_l_buf = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	261 zip_prev = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	262 zip_dyn_ltree = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	263 zip_dyn_dtree = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	264 zip_static_ltree = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	265 zip_static_dtree = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	266 zip_bl_tree = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	267 zip_l_desc = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	268 zip_d_desc = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	269 zip_bl_desc = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	270 zip_bl_count = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	271 zip_heap = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	272 zip_depth = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	273 zip_length_code = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	274 zip_dist_code = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	275 zip_base_length = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	276 zip_base_dist = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	277 zip_flag_buf = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	278 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	279
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	280 var zip_reuse_queue = function(p) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	281 p.next = zip_free_queue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	282 zip_free_queue = p;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	283 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	284
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	285 var zip_new_queue = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	286 var p;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	287
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	288 if(zip_free_queue != null)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	289 {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	290 p = zip_free_queue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	291 zip_free_queue = zip_free_queue.next;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	292 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	293 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	294 p = new zip_DeflateBuffer();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	295 p.next = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	296 p.len = p.off = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	297
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	298 return p;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	299 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	300
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	301 var zip_head1 = function(i) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	302 return zip_prev[zip_WSIZE + i];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	303 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	304
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	305 var zip_head2 = function(i, val) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	306 return zip_prev[zip_WSIZE + i] = val;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	307 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	308
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	309 /* put_byte is used for the compressed output, put_ubyte for the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	310 * uncompressed output. However unlzw() uses window for its
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	311 * suffix table instead of its output buffer, so it does not use put_ubyte
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	312 * (to be cleaned up).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	313 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	314 var zip_put_byte = function(c) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	315 zip_outbuf[zip_outoff + zip_outcnt++] = c;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	316 if(zip_outoff + zip_outcnt == zip_OUTBUFSIZ)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	317 zip_qoutbuf();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	318 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	319
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	320 /* Output a 16 bit value, lsb first */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	321 var zip_put_short = function(w) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	322 w &= 0xffff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	323 if(zip_outoff + zip_outcnt < zip_OUTBUFSIZ - 2) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	324 zip_outbuf[zip_outoff + zip_outcnt++] = (w & 0xff);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	325 zip_outbuf[zip_outoff + zip_outcnt++] = (w >>> 8);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	326 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	327 zip_put_byte(w & 0xff);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	328 zip_put_byte(w >>> 8);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	329 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	330 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	331
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	332 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	333 * Insert string s in the dictionary and set match_head to the previous head
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	334 * of the hash chain (the most recent string with same hash key). Return
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	335 * the previous length of the hash chain.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	336 * IN assertion: all calls to to INSERT_STRING are made with consecutive
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	337 * input characters and the first MIN_MATCH bytes of s are valid
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	338 * (except for the last MIN_MATCH-1 bytes of the input file).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	339 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	340 var zip_INSERT_STRING = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	341 zip_ins_h = ((zip_ins_h << zip_H_SHIFT)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	342 ^ (zip_window[zip_strstart + zip_MIN_MATCH - 1] & 0xff))
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	343 & zip_HASH_MASK;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	344 zip_hash_head = zip_head1(zip_ins_h);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	345 zip_prev[zip_strstart & zip_WMASK] = zip_hash_head;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	346 zip_head2(zip_ins_h, zip_strstart);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	347 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	348
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	349 /* Send a code of the given tree. c and tree must not have side effects */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	350 var zip_SEND_CODE = function(c, tree) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	351 zip_send_bits(tree[c].fc, tree[c].dl);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	352 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	353
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	354 /* Mapping from a distance to a distance code. dist is the distance - 1 and
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	355 * must not have side effects. dist_code[256] and dist_code[257] are never
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	356 * used.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	357 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	358 var zip_D_CODE = function(dist) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	359 return (dist < 256 ? zip_dist_code[dist]
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	360 : zip_dist_code[256 + (dist>>7)]) & 0xff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	361 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	362
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	363 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	364 * Compares to subtrees, using the tree depth as tie breaker when
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	365 * the subtrees have equal frequency. This minimizes the worst case length.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	366 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	367 var zip_SMALLER = function(tree, n, m) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	368 return tree[n].fc < tree[m].fc \|\|
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	369 (tree[n].fc == tree[m].fc && zip_depth[n] <= zip_depth[m]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	370 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	371
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	372 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	373 * read string data
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	374 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	375 var zip_read_buff = function(buff, offset, n) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	376 var i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	377 for(i = 0; i < n && zip_deflate_pos < zip_deflate_data.length; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	378 buff[offset + i] =
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	379 zip_deflate_data.charCodeAt(zip_deflate_pos++) & 0xff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	380 return i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	381 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	382
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	383 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	384 * Initialize the "longest match" routines for a new file
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	385 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	386 var zip_lm_init = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	387 var j;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	388
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	389 /* Initialize the hash table. */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	390 for(j = 0; j < zip_HASH_SIZE; j++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	391 // zip_head2(j, zip_NIL);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	392 zip_prev[zip_WSIZE + j] = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	393 /* prev will be initialized on the fly */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	394
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	395 /* Set the default configuration parameters:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	396 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	397 zip_max_lazy_match = zip_configuration_table[zip_compr_level].max_lazy;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	398 zip_good_match = zip_configuration_table[zip_compr_level].good_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	399 if(!zip_FULL_SEARCH)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	400 zip_nice_match = zip_configuration_table[zip_compr_level].nice_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	401 zip_max_chain_length = zip_configuration_table[zip_compr_level].max_chain;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	402
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	403 zip_strstart = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	404 zip_block_start = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	405
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	406 zip_lookahead = zip_read_buff(zip_window, 0, 2 * zip_WSIZE);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	407 if(zip_lookahead <= 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	408 zip_eofile = true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	409 zip_lookahead = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	410 return;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	411 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	412 zip_eofile = false;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	413 /* Make sure that we always have enough lookahead. This is important
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	414 * if input comes from a device such as a tty.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	415 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	416 while(zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	417 zip_fill_window();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	418
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	419 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	420 * not important since only literal bytes will be emitted.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	421 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	422 zip_ins_h = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	423 for(j = 0; j < zip_MIN_MATCH - 1; j++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	424 // UPDATE_HASH(ins_h, window[j]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	425 zip_ins_h = ((zip_ins_h << zip_H_SHIFT) ^ (zip_window[j] & 0xff)) & zip_HASH_MASK;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	426 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	427 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	428
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	429 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	430 * Set match_start to the longest match starting at the given string and
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	431 * return its length. Matches shorter or equal to prev_length are discarded,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	432 * in which case the result is equal to prev_length and match_start is
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	433 * garbage.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	434 * IN assertions: cur_match is the head of the hash chain for the current
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	435 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	436 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	437 var zip_longest_match = function(cur_match) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	438 var chain_length = zip_max_chain_length; // max hash chain length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	439 var scanp = zip_strstart; // current string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	440 var matchp; // matched string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	441 var len; // length of current match
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	442 var best_len = zip_prev_length; // best match length so far
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	443
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	444 /* Stop when cur_match becomes <= limit. To simplify the code,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	445 * we prevent matches with the string of window index 0.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	446 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	447 var limit = (zip_strstart > zip_MAX_DIST ? zip_strstart - zip_MAX_DIST : zip_NIL);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	448
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	449 var strendp = zip_strstart + zip_MAX_MATCH;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	450 var scan_end1 = zip_window[scanp + best_len - 1];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	451 var scan_end = zip_window[scanp + best_len];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	452
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	453 /* Do not waste too much time if we already have a good match: */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	454 if(zip_prev_length >= zip_good_match)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	455 chain_length >>= 2;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	456
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	457 // Assert(encoder->strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	458
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	459 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	460 // Assert(cur_match < encoder->strstart, "no future");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	461 matchp = cur_match;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	462
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	463 /* Skip to next match if the match length cannot increase
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	464 * or if the match length is less than 2:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	465 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	466 if(zip_window[matchp + best_len] != scan_end \|\|
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	467 zip_window[matchp + best_len - 1] != scan_end1 \|\|
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	468 zip_window[matchp] != zip_window[scanp] \|\|
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	469 zip_window[++matchp] != zip_window[scanp + 1]) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	470 continue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	471 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	472
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	473 /* The check at best_len-1 can be removed because it will be made
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	474 * again later. (This heuristic is not always a win.)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	475 * It is not necessary to compare scan[2] and match[2] since they
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	476 * are always equal when the other bytes match, given that
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	477 * the hash keys are equal and that HASH_BITS >= 8.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	478 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	479 scanp += 2;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	480 matchp++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	481
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	482 /* We check for insufficient lookahead only every 8th comparison;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	483 * the 256th check will be made at strstart+258.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	484 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	485 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	486 } while(zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	487 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	488 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	489 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	490 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	491 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	492 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	493 zip_window[++scanp] == zip_window[++matchp] &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	494 scanp < strendp);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	495
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	496 len = zip_MAX_MATCH - (strendp - scanp);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	497 scanp = strendp - zip_MAX_MATCH;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	498
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	499 if(len > best_len) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	500 zip_match_start = cur_match;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	501 best_len = len;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	502 if(zip_FULL_SEARCH) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	503 if(len >= zip_MAX_MATCH) break;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	504 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	505 if(len >= zip_nice_match) break;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	506 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	507
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	508 scan_end1 = zip_window[scanp + best_len-1];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	509 scan_end = zip_window[scanp + best_len];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	510 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	511 } while((cur_match = zip_prev[cur_match & zip_WMASK]) > limit
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	512 && --chain_length != 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	513
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	514 return best_len;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	515 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	516
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	517 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	518 * Fill the window when the lookahead becomes insufficient.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	519 * Updates strstart and lookahead, and sets eofile if end of input file.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	520 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	521 * OUT assertions: at least one byte has been read, or eofile is set;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	522 * file reads are performed for at least two bytes (required for the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	523 * translate_eol option).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	524 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	525 var zip_fill_window = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	526 var n, m;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	527
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	528 // Amount of free space at the end of the window.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	529 var more = zip_window_size - zip_lookahead - zip_strstart;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	530
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	531 /* If the window is almost full and there is insufficient lookahead,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	532 * move the upper half to the lower one to make room in the upper half.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	533 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	534 if(more == -1) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	535 /* Very unlikely, but possible on 16 bit machine if strstart == 0
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	536 * and lookahead == 1 (input done one byte at time)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	537 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	538 more--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	539 } else if(zip_strstart >= zip_WSIZE + zip_MAX_DIST) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	540 /* By the IN assertion, the window is not empty so we can't confuse
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	541 * more == 0 with more == 64K on a 16 bit machine.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	542 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	543 // Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	544
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	545 // System.arraycopy(window, WSIZE, window, 0, WSIZE);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	546 for(n = 0; n < zip_WSIZE; n++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	547 zip_window[n] = zip_window[n + zip_WSIZE];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	548
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	549 zip_match_start -= zip_WSIZE;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	550 zip_strstart -= zip_WSIZE; /* we now have strstart >= MAX_DIST: */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	551 zip_block_start -= zip_WSIZE;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	552
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	553 for(n = 0; n < zip_HASH_SIZE; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	554 m = zip_head1(n);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	555 zip_head2(n, m >= zip_WSIZE ? m - zip_WSIZE : zip_NIL);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	556 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	557 for(n = 0; n < zip_WSIZE; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	558 /* If n is not on any hash chain, prev[n] is garbage but
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	559 * its value will never be used.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	560 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	561 m = zip_prev[n];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	562 zip_prev[n] = (m >= zip_WSIZE ? m - zip_WSIZE : zip_NIL);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	563 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	564 more += zip_WSIZE;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	565 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	566 // At this point, more >= 2
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	567 if(!zip_eofile) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	568 n = zip_read_buff(zip_window, zip_strstart + zip_lookahead, more);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	569 if(n <= 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	570 zip_eofile = true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	571 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	572 zip_lookahead += n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	573 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	574 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	575
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	576 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	577 * Processes a new input file and return its compressed length. This
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	578 * function does not perform lazy evaluationof matches and inserts
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	579 * new strings in the dictionary only for unmatched strings or for short
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	580 * matches. It is used only for the fast compression options.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	581 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	582 var zip_deflate_fast = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	583 while(zip_lookahead != 0 && zip_qhead == null) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	584 var flush; // set if current block must be flushed
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	585
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	586 /* Insert the string window[strstart .. strstart+2] in the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	587 * dictionary, and set hash_head to the head of the hash chain:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	588 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	589 zip_INSERT_STRING();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	590
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	591 /* Find the longest match, discarding those <= prev_length.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	592 * At this point we have always match_length < MIN_MATCH
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	593 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	594 if(zip_hash_head != zip_NIL &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	595 zip_strstart - zip_hash_head <= zip_MAX_DIST) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	596 /* To simplify the code, we prevent matches with the string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	597 * of window index 0 (in particular we have to avoid a match
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	598 * of the string with itself at the start of the input file).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	599 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	600 zip_match_length = zip_longest_match(zip_hash_head);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	601 /* longest_match() sets match_start */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	602 if(zip_match_length > zip_lookahead)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	603 zip_match_length = zip_lookahead;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	604 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	605 if(zip_match_length >= zip_MIN_MATCH) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	606 // check_match(strstart, match_start, match_length);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	607
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	608 flush = zip_ct_tally(zip_strstart - zip_match_start,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	609 zip_match_length - zip_MIN_MATCH);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	610 zip_lookahead -= zip_match_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	611
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	612 /* Insert new strings in the hash table only if the match length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	613 * is not too large. This saves time but degrades compression.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	614 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	615 if(zip_match_length <= zip_max_lazy_match) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	616 zip_match_length--; // string at strstart already in hash table
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	617 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	618 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	619 zip_INSERT_STRING();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	620 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	621 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	622 * these bytes are garbage, but it does not matter since
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	623 * the next lookahead bytes will be emitted as literals.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	624 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	625 } while(--zip_match_length != 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	626 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	627 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	628 zip_strstart += zip_match_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	629 zip_match_length = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	630 zip_ins_h = zip_window[zip_strstart] & 0xff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	631 // UPDATE_HASH(ins_h, window[strstart + 1]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	632 zip_ins_h = ((zip_ins_h<<zip_H_SHIFT) ^ (zip_window[zip_strstart + 1] & 0xff)) & zip_HASH_MASK;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	633
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	634 //#if MIN_MATCH != 3
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	635 // Call UPDATE_HASH() MIN_MATCH-3 more times
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	636 //#endif
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	637
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	638 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	639 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	640 /* No match, output a literal byte */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	641 flush = zip_ct_tally(0, zip_window[zip_strstart] & 0xff);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	642 zip_lookahead--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	643 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	644 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	645 if(flush) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	646 zip_flush_block(0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	647 zip_block_start = zip_strstart;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	648 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	649
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	650 /* Make sure that we always have enough lookahead, except
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	651 * at the end of the input file. We need MAX_MATCH bytes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	652 * for the next match, plus MIN_MATCH bytes to insert the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	653 * string following the next match.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	654 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	655 while(zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	656 zip_fill_window();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	657 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	658 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	659
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	660 var zip_deflate_better = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	661 /* Process the input block. */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	662 while(zip_lookahead != 0 && zip_qhead == null) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	663 /* Insert the string window[strstart .. strstart+2] in the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	664 * dictionary, and set hash_head to the head of the hash chain:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	665 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	666 zip_INSERT_STRING();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	667
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	668 /* Find the longest match, discarding those <= prev_length.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	669 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	670 zip_prev_length = zip_match_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	671 zip_prev_match = zip_match_start;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	672 zip_match_length = zip_MIN_MATCH - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	673
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	674 if(zip_hash_head != zip_NIL &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	675 zip_prev_length < zip_max_lazy_match &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	676 zip_strstart - zip_hash_head <= zip_MAX_DIST) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	677 /* To simplify the code, we prevent matches with the string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	678 * of window index 0 (in particular we have to avoid a match
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	679 * of the string with itself at the start of the input file).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	680 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	681 zip_match_length = zip_longest_match(zip_hash_head);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	682 /* longest_match() sets match_start */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	683 if(zip_match_length > zip_lookahead)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	684 zip_match_length = zip_lookahead;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	685
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	686 /* Ignore a length 3 match if it is too distant: */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	687 if(zip_match_length == zip_MIN_MATCH &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	688 zip_strstart - zip_match_start > zip_TOO_FAR) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	689 /* If prev_match is also MIN_MATCH, match_start is garbage
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	690 * but we will ignore the current match anyway.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	691 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	692 zip_match_length--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	693 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	694 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	695 /* If there was a match at the previous step and the current
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	696 * match is not better, output the previous match:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	697 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	698 if(zip_prev_length >= zip_MIN_MATCH &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	699 zip_match_length <= zip_prev_length) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	700 var flush; // set if current block must be flushed
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	701
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	702 // check_match(strstart - 1, prev_match, prev_length);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	703 flush = zip_ct_tally(zip_strstart - 1 - zip_prev_match,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	704 zip_prev_length - zip_MIN_MATCH);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	705
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	706 /* Insert in hash table all strings up to the end of the match.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	707 * strstart-1 and strstart are already inserted.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	708 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	709 zip_lookahead -= zip_prev_length - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	710 zip_prev_length -= 2;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	711 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	712 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	713 zip_INSERT_STRING();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	714 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	715 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	716 * these bytes are garbage, but it does not matter since the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	717 * next lookahead bytes will always be emitted as literals.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	718 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	719 } while(--zip_prev_length != 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	720 zip_match_available = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	721 zip_match_length = zip_MIN_MATCH - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	722 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	723 if(flush) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	724 zip_flush_block(0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	725 zip_block_start = zip_strstart;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	726 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	727 } else if(zip_match_available != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	728 /* If there was no match at the previous position, output a
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	729 * single literal. If there was a match but the current match
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	730 * is longer, truncate the previous match to a single literal.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	731 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	732 if(zip_ct_tally(0, zip_window[zip_strstart - 1] & 0xff)) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	733 zip_flush_block(0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	734 zip_block_start = zip_strstart;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	735 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	736 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	737 zip_lookahead--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	738 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	739 /* There is no previous match to compare with, wait for
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	740 * the next step to decide.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	741 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	742 zip_match_available = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	743 zip_strstart++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	744 zip_lookahead--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	745 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	746
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	747 /* Make sure that we always have enough lookahead, except
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	748 * at the end of the input file. We need MAX_MATCH bytes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	749 * for the next match, plus MIN_MATCH bytes to insert the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	750 * string following the next match.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	751 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	752 while(zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	753 zip_fill_window();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	754 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	755 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	756
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	757 var zip_init_deflate = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	758 if(zip_eofile)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	759 return;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	760 zip_bi_buf = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	761 zip_bi_valid = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	762 zip_ct_init();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	763 zip_lm_init();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	764
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	765 zip_qhead = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	766 zip_outcnt = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	767 zip_outoff = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	768
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	769 if(zip_compr_level <= 3)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	770 {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	771 zip_prev_length = zip_MIN_MATCH - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	772 zip_match_length = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	773 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	774 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	775 {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	776 zip_match_length = zip_MIN_MATCH - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	777 zip_match_available = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	778 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	779
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	780 zip_complete = false;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	781 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	782
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	783 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	784 * Same as above, but achieves better compression. We use a lazy
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	785 * evaluation for matches: a match is finally adopted only if there is
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	786 * no better match at the next window position.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	787 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	788 var zip_deflate_internal = function(buff, off, buff_size) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	789 var n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	790
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	791 if(!zip_initflag)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	792 {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	793 zip_init_deflate();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	794 zip_initflag = true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	795 if(zip_lookahead == 0) { // empty
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	796 zip_complete = true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	797 return 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	798 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	799 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	800
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	801 if((n = zip_qcopy(buff, off, buff_size)) == buff_size)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	802 return buff_size;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	803
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	804 if(zip_complete)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	805 return n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	806
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	807 if(zip_compr_level <= 3) // optimized for speed
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	808 zip_deflate_fast();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	809 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	810 zip_deflate_better();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	811 if(zip_lookahead == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	812 if(zip_match_available != 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	813 zip_ct_tally(0, zip_window[zip_strstart - 1] & 0xff);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	814 zip_flush_block(1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	815 zip_complete = true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	816 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	817 return n + zip_qcopy(buff, n + off, buff_size - n);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	818 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	819
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	820 var zip_qcopy = function(buff, off, buff_size) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	821 var n, i, j;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	822
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	823 n = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	824 while(zip_qhead != null && n < buff_size)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	825 {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	826 i = buff_size - n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	827 if(i > zip_qhead.len)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	828 i = zip_qhead.len;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	829 // System.arraycopy(qhead.ptr, qhead.off, buff, off + n, i);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	830 for(j = 0; j < i; j++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	831 buff[off + n + j] = zip_qhead.ptr[zip_qhead.off + j];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	832
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	833 zip_qhead.off += i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	834 zip_qhead.len -= i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	835 n += i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	836 if(zip_qhead.len == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	837 var p;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	838 p = zip_qhead;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	839 zip_qhead = zip_qhead.next;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	840 zip_reuse_queue(p);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	841 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	842 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	843
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	844 if(n == buff_size)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	845 return n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	846
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	847 if(zip_outoff < zip_outcnt) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	848 i = buff_size - n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	849 if(i > zip_outcnt - zip_outoff)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	850 i = zip_outcnt - zip_outoff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	851 // System.arraycopy(outbuf, outoff, buff, off + n, i);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	852 for(j = 0; j < i; j++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	853 buff[off + n + j] = zip_outbuf[zip_outoff + j];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	854 zip_outoff += i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	855 n += i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	856 if(zip_outcnt == zip_outoff)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	857 zip_outcnt = zip_outoff = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	858 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	859 return n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	860 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	861
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	862 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	863 * Allocate the match buffer, initialize the various tables and save the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	864 * location of the internal file attribute (ascii/binary) and method
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	865 * (DEFLATE/STORE).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	866 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	867 var zip_ct_init = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	868 var n; // iterates over tree elements
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	869 var bits; // bit counter
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	870 var length; // length value
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	871 var code; // code value
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	872 var dist; // distance index
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	873
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	874 if(zip_static_dtree[0].dl != 0) return; // ct_init already called
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	875
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	876 zip_l_desc.dyn_tree = zip_dyn_ltree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	877 zip_l_desc.static_tree = zip_static_ltree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	878 zip_l_desc.extra_bits = zip_extra_lbits;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	879 zip_l_desc.extra_base = zip_LITERALS + 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	880 zip_l_desc.elems = zip_L_CODES;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	881 zip_l_desc.max_length = zip_MAX_BITS;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	882 zip_l_desc.max_code = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	883
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	884 zip_d_desc.dyn_tree = zip_dyn_dtree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	885 zip_d_desc.static_tree = zip_static_dtree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	886 zip_d_desc.extra_bits = zip_extra_dbits;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	887 zip_d_desc.extra_base = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	888 zip_d_desc.elems = zip_D_CODES;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	889 zip_d_desc.max_length = zip_MAX_BITS;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	890 zip_d_desc.max_code = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	891
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	892 zip_bl_desc.dyn_tree = zip_bl_tree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	893 zip_bl_desc.static_tree = null;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	894 zip_bl_desc.extra_bits = zip_extra_blbits;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	895 zip_bl_desc.extra_base = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	896 zip_bl_desc.elems = zip_BL_CODES;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	897 zip_bl_desc.max_length = zip_MAX_BL_BITS;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	898 zip_bl_desc.max_code = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	899
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	900 // Initialize the mapping length (0..255) -> length code (0..28)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	901 length = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	902 for(code = 0; code < zip_LENGTH_CODES-1; code++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	903 zip_base_length[code] = length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	904 for(n = 0; n < (1<<zip_extra_lbits[code]); n++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	905 zip_length_code[length++] = code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	906 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	907 // Assert (length == 256, "ct_init: length != 256");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	908
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	909 /* Note that the length 255 (match length 258) can be represented
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	910 * in two different ways: code 284 + 5 bits or code 285, so we
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	911 * overwrite length_code[255] to use the best encoding:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	912 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	913 zip_length_code[length-1] = code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	914
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	915 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	916 dist = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	917 for(code = 0 ; code < 16; code++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	918 zip_base_dist[code] = dist;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	919 for(n = 0; n < (1<<zip_extra_dbits[code]); n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	920 zip_dist_code[dist++] = code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	921 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	922 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	923 // Assert (dist == 256, "ct_init: dist != 256");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	924 dist >>= 7; // from now on, all distances are divided by 128
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	925 for( ; code < zip_D_CODES; code++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	926 zip_base_dist[code] = dist << 7;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	927 for(n = 0; n < (1<<(zip_extra_dbits[code]-7)); n++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	928 zip_dist_code[256 + dist++] = code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	929 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	930 // Assert (dist == 256, "ct_init: 256+dist != 512");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	931
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	932 // Construct the codes of the static literal tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	933 for(bits = 0; bits <= zip_MAX_BITS; bits++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	934 zip_bl_count[bits] = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	935 n = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	936 while(n <= 143) { zip_static_ltree[n++].dl = 8; zip_bl_count[8]++; }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	937 while(n <= 255) { zip_static_ltree[n++].dl = 9; zip_bl_count[9]++; }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	938 while(n <= 279) { zip_static_ltree[n++].dl = 7; zip_bl_count[7]++; }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	939 while(n <= 287) { zip_static_ltree[n++].dl = 8; zip_bl_count[8]++; }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	940 /* Codes 286 and 287 do not exist, but we must include them in the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	941 * tree construction to get a canonical Huffman tree (longest code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	942 * all ones)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	943 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	944 zip_gen_codes(zip_static_ltree, zip_L_CODES + 1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	945
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	946 /* The static distance tree is trivial: */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	947 for(n = 0; n < zip_D_CODES; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	948 zip_static_dtree[n].dl = 5;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	949 zip_static_dtree[n].fc = zip_bi_reverse(n, 5);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	950 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	951
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	952 // Initialize the first block of the first file:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	953 zip_init_block();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	954 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	955
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	956 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	957 * Initialize a new block.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	958 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	959 var zip_init_block = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	960 var n; // iterates over tree elements
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	961
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	962 // Initialize the trees.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	963 for(n = 0; n < zip_L_CODES; n++) zip_dyn_ltree[n].fc = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	964 for(n = 0; n < zip_D_CODES; n++) zip_dyn_dtree[n].fc = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	965 for(n = 0; n < zip_BL_CODES; n++) zip_bl_tree[n].fc = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	966
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	967 zip_dyn_ltree[zip_END_BLOCK].fc = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	968 zip_opt_len = zip_static_len = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	969 zip_last_lit = zip_last_dist = zip_last_flags = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	970 zip_flags = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	971 zip_flag_bit = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	972 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	973
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	974 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	975 * Restore the heap property by moving down the tree starting at node k,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	976 * exchanging a node with the smallest of its two sons if necessary, stopping
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	977 * when the heap property is re-established (each father smaller than its
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	978 * two sons).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	979 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	980 var zip_pqdownheap = function(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	981 tree, // the tree to restore
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	982 k) { // node to move down
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	983 var v = zip_heap[k];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	984 var j = k << 1; // left son of k
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	985
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	986 while(j <= zip_heap_len) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	987 // Set j to the smallest of the two sons:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	988 if(j < zip_heap_len &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	989 zip_SMALLER(tree, zip_heap[j + 1], zip_heap[j]))
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	990 j++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	991
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	992 // Exit if v is smaller than both sons
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	993 if(zip_SMALLER(tree, v, zip_heap[j]))
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	994 break;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	995
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	996 // Exchange v with the smallest son
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	997 zip_heap[k] = zip_heap[j];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	998 k = j;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	999
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1000 // And continue down the tree, setting j to the left son of k
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1001 j <<= 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1002 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1003 zip_heap[k] = v;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1004 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1005
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1006 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1007 * Compute the optimal bit lengths for a tree and update the total bit length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1008 * for the current block.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1009 * IN assertion: the fields freq and dad are set, heap[heap_max] and
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1010 * above are the tree nodes sorted by increasing frequency.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1011 * OUT assertions: the field len is set to the optimal bit length, the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1012 * array bl_count contains the frequencies for each bit length.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1013 * The length opt_len is updated; static_len is also updated if stree is
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1014 * not null.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1015 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1016 var zip_gen_bitlen = function(desc) { // the tree descriptor
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1017 var tree = desc.dyn_tree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1018 var extra = desc.extra_bits;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1019 var base = desc.extra_base;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1020 var max_code = desc.max_code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1021 var max_length = desc.max_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1022 var stree = desc.static_tree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1023 var h; // heap index
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1024 var n, m; // iterate over the tree elements
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1025 var bits; // bit length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1026 var xbits; // extra bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1027 var f; // frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1028 var overflow = 0; // number of elements with bit length too large
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1029
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1030 for(bits = 0; bits <= zip_MAX_BITS; bits++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1031 zip_bl_count[bits] = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1032
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1033 /* In a first pass, compute the optimal bit lengths (which may
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1034 * overflow in the case of the bit length tree).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1035 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1036 tree[zip_heap[zip_heap_max]].dl = 0; // root of the heap
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1037
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1038 for(h = zip_heap_max + 1; h < zip_HEAP_SIZE; h++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1039 n = zip_heap[h];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1040 bits = tree[tree[n].dl].dl + 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1041 if(bits > max_length) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1042 bits = max_length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1043 overflow++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1044 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1045 tree[n].dl = bits;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1046 // We overwrite tree[n].dl which is no longer needed
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1047
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1048 if(n > max_code)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1049 continue; // not a leaf node
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1050
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1051 zip_bl_count[bits]++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1052 xbits = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1053 if(n >= base)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1054 xbits = extra[n - base];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1055 f = tree[n].fc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1056 zip_opt_len += f * (bits + xbits);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1057 if(stree != null)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1058 zip_static_len += f * (stree[n].dl + xbits);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1059 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1060 if(overflow == 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1061 return;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1062
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1063 // This happens for example on obj2 and pic of the Calgary corpus
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1064
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1065 // Find the first bit length which could increase:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1066 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1067 bits = max_length - 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1068 while(zip_bl_count[bits] == 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1069 bits--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1070 zip_bl_count[bits]--; // move one leaf down the tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1071 zip_bl_count[bits + 1] += 2; // move one overflow item as its brother
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1072 zip_bl_count[max_length]--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1073 /* The brother of the overflow item also moves one step up,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1074 * but this does not affect bl_count[max_length]
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1075 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1076 overflow -= 2;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1077 } while(overflow > 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1078
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1079 /* Now recompute all bit lengths, scanning in increasing frequency.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1080 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1081 * lengths instead of fixing only the wrong ones. This idea is taken
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1082 * from 'ar' written by Haruhiko Okumura.)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1083 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1084 for(bits = max_length; bits != 0; bits--) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1085 n = zip_bl_count[bits];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1086 while(n != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1087 m = zip_heap[--h];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1088 if(m > max_code)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1089 continue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1090 if(tree[m].dl != bits) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1091 zip_opt_len += (bits - tree[m].dl) * tree[m].fc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1092 tree[m].fc = bits;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1093 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1094 n--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1095 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1096 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1097 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1098
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1099 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1100 * Generate the codes for a given tree and bit counts (which need not be
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1101 * optimal).
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1102 * IN assertion: the array bl_count contains the bit length statistics for
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1103 * the given tree and the field len is set for all tree elements.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1104 * OUT assertion: the field code is set for all tree elements of non
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1105 * zero code length.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1106 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1107 var zip_gen_codes = function(tree, // the tree to decorate
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1108 max_code) { // largest code with non zero frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1109 var next_code = new Array(zip_MAX_BITS+1); // next code value for each bit length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1110 var code = 0; // running code value
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1111 var bits; // bit index
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1112 var n; // code index
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1113
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1114 /* The distribution counts are first used to generate the code values
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1115 * without bit reversal.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1116 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1117 for(bits = 1; bits <= zip_MAX_BITS; bits++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1118 code = ((code + zip_bl_count[bits-1]) << 1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1119 next_code[bits] = code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1120 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1121
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1122 /* Check that the bit counts in bl_count are consistent. The last code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1123 * must be all ones.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1124 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1125 // Assert (code + encoder->bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1126 // "inconsistent bit counts");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1127 // Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1128
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1129 for(n = 0; n <= max_code; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1130 var len = tree[n].dl;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1131 if(len == 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1132 continue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1133 // Now reverse the bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1134 tree[n].fc = zip_bi_reverse(next_code[len]++, len);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1135
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1136 // Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1137 // n, (isgraph(n) ? n : ' '), len, tree[n].fc, next_code[len]-1));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1138 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1139 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1140
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1141 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1142 * Construct one Huffman tree and assigns the code bit strings and lengths.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1143 * Update the total bit length for the current block.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1144 * IN assertion: the field freq is set for all tree elements.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1145 * OUT assertions: the fields len and code are set to the optimal bit length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1146 * and corresponding code. The length opt_len is updated; static_len is
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1147 * also updated if stree is not null. The field max_code is set.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1148 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1149 var zip_build_tree = function(desc) { // the tree descriptor
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1150 var tree = desc.dyn_tree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1151 var stree = desc.static_tree;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1152 var elems = desc.elems;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1153 var n, m; // iterate over heap elements
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1154 var max_code = -1; // largest code with non zero frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1155 var node = elems; // next internal node of the tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1156
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1157 /* Construct the initial heap, with least frequent element in
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1158 * heap[SMALLEST]. The sons of heap[n] are heap[2n] and heap[2n+1].
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1159 * heap[0] is not used.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1160 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1161 zip_heap_len = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1162 zip_heap_max = zip_HEAP_SIZE;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1163
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1164 for(n = 0; n < elems; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1165 if(tree[n].fc != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1166 zip_heap[++zip_heap_len] = max_code = n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1167 zip_depth[n] = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1168 } else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1169 tree[n].dl = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1170 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1171
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1172 /* The pkzip format requires that at least one distance code exists,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1173 * and that at least one bit should be sent even if there is only one
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1174 * possible code. So to avoid special checks later on we force at least
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1175 * two codes of non zero frequency.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1176 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1177 while(zip_heap_len < 2) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1178 var xnew = zip_heap[++zip_heap_len] = (max_code < 2 ? ++max_code : 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1179 tree[xnew].fc = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1180 zip_depth[xnew] = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1181 zip_opt_len--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1182 if(stree != null)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1183 zip_static_len -= stree[xnew].dl;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1184 // new is 0 or 1 so it does not have extra bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1185 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1186 desc.max_code = max_code;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1187
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1188 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1189 * establish sub-heaps of increasing lengths:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1190 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1191 for(n = zip_heap_len >> 1; n >= 1; n--)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1192 zip_pqdownheap(tree, n);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1193
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1194 /* Construct the Huffman tree by repeatedly combining the least two
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1195 * frequent nodes.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1196 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1197 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1198 n = zip_heap[zip_SMALLEST];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1199 zip_heap[zip_SMALLEST] = zip_heap[zip_heap_len--];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1200 zip_pqdownheap(tree, zip_SMALLEST);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1201
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1202 m = zip_heap[zip_SMALLEST]; // m = node of next least frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1203
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1204 // keep the nodes sorted by frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1205 zip_heap[--zip_heap_max] = n;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1206 zip_heap[--zip_heap_max] = m;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1207
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1208 // Create a new node father of n and m
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1209 tree[node].fc = tree[n].fc + tree[m].fc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1210 // depth[node] = (char)(MAX(depth[n], depth[m]) + 1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1211 if(zip_depth[n] > zip_depth[m] + 1)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1212 zip_depth[node] = zip_depth[n];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1213 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1214 zip_depth[node] = zip_depth[m] + 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1215 tree[n].dl = tree[m].dl = node;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1216
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1217 // and insert the new node in the heap
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1218 zip_heap[zip_SMALLEST] = node++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1219 zip_pqdownheap(tree, zip_SMALLEST);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1220
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1221 } while(zip_heap_len >= 2);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1222
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1223 zip_heap[--zip_heap_max] = zip_heap[zip_SMALLEST];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1224
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1225 /* At this point, the fields freq and dad are set. We can now
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1226 * generate the bit lengths.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1227 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1228 zip_gen_bitlen(desc);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1229
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1230 // The field len is now set, we can generate the bit codes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1231 zip_gen_codes(tree, max_code);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1232 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1233
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1234 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1235 * Scan a literal or distance tree to determine the frequencies of the codes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1236 * in the bit length tree. Updates opt_len to take into account the repeat
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1237 * counts. (The contribution of the bit length codes will be added later
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1238 * during the construction of bl_tree.)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1239 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1240 var zip_scan_tree = function(tree,// the tree to be scanned
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1241 max_code) { // and its largest code of non zero frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1242 var n; // iterates over all tree elements
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1243 var prevlen = -1; // last emitted length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1244 var curlen; // length of current code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1245 var nextlen = tree[0].dl; // length of next code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1246 var count = 0; // repeat count of the current code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1247 var max_count = 7; // max repeat count
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1248 var min_count = 4; // min repeat count
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1249
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1250 if(nextlen == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1251 max_count = 138;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1252 min_count = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1253 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1254 tree[max_code + 1].dl = 0xffff; // guard
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1255
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1256 for(n = 0; n <= max_code; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1257 curlen = nextlen;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1258 nextlen = tree[n + 1].dl;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1259 if(++count < max_count && curlen == nextlen)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1260 continue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1261 else if(count < min_count)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1262 zip_bl_tree[curlen].fc += count;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1263 else if(curlen != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1264 if(curlen != prevlen)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1265 zip_bl_tree[curlen].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1266 zip_bl_tree[zip_REP_3_6].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1267 } else if(count <= 10)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1268 zip_bl_tree[zip_REPZ_3_10].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1269 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1270 zip_bl_tree[zip_REPZ_11_138].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1271 count = 0; prevlen = curlen;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1272 if(nextlen == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1273 max_count = 138;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1274 min_count = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1275 } else if(curlen == nextlen) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1276 max_count = 6;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1277 min_count = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1278 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1279 max_count = 7;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1280 min_count = 4;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1281 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1282 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1283 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1284
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1285 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1286 * Send a literal or distance tree in compressed form, using the codes in
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1287 * bl_tree.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1288 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1289 var zip_send_tree = function(tree, // the tree to be scanned
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1290 max_code) { // and its largest code of non zero frequency
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1291 var n; // iterates over all tree elements
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1292 var prevlen = -1; // last emitted length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1293 var curlen; // length of current code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1294 var nextlen = tree[0].dl; // length of next code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1295 var count = 0; // repeat count of the current code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1296 var max_count = 7; // max repeat count
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1297 var min_count = 4; // min repeat count
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1298
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1299 /* tree[max_code+1].dl = -1; / / guard already set */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1300 if(nextlen == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1301 max_count = 138;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1302 min_count = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1303 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1304
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1305 for(n = 0; n <= max_code; n++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1306 curlen = nextlen;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1307 nextlen = tree[n+1].dl;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1308 if(++count < max_count && curlen == nextlen) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1309 continue;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1310 } else if(count < min_count) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1311 do { zip_SEND_CODE(curlen, zip_bl_tree); } while(--count != 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1312 } else if(curlen != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1313 if(curlen != prevlen) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1314 zip_SEND_CODE(curlen, zip_bl_tree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1315 count--;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1316 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1317 // Assert(count >= 3 && count <= 6, " 3_6?");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1318 zip_SEND_CODE(zip_REP_3_6, zip_bl_tree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1319 zip_send_bits(count - 3, 2);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1320 } else if(count <= 10) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1321 zip_SEND_CODE(zip_REPZ_3_10, zip_bl_tree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1322 zip_send_bits(count-3, 3);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1323 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1324 zip_SEND_CODE(zip_REPZ_11_138, zip_bl_tree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1325 zip_send_bits(count-11, 7);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1326 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1327 count = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1328 prevlen = curlen;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1329 if(nextlen == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1330 max_count = 138;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1331 min_count = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1332 } else if(curlen == nextlen) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1333 max_count = 6;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1334 min_count = 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1335 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1336 max_count = 7;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1337 min_count = 4;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1338 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1339 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1340 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1341
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1342 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1343 * Construct the Huffman tree for the bit lengths and return the index in
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1344 * bl_order of the last bit length code to send.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1345 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1346 var zip_build_bl_tree = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1347 var max_blindex; // index of last bit length code of non zero freq
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1348
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1349 // Determine the bit length frequencies for literal and distance trees
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1350 zip_scan_tree(zip_dyn_ltree, zip_l_desc.max_code);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1351 zip_scan_tree(zip_dyn_dtree, zip_d_desc.max_code);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1352
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1353 // Build the bit length tree:
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1354 zip_build_tree(zip_bl_desc);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1355 /* opt_len now includes the length of the tree representations, except
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1356 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1357 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1358
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1359 /* Determine the number of bit length codes to send. The pkzip format
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1360 * requires that at least 4 bit length codes be sent. (appnote.txt says
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1361 * 3 but the actual value used is 4.)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1362 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1363 for(max_blindex = zip_BL_CODES-1; max_blindex >= 3; max_blindex--) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1364 if(zip_bl_tree[zip_bl_order[max_blindex]].dl != 0) break;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1365 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1366 /* Update opt_len to include the bit length tree and counts */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1367 zip_opt_len += 3*(max_blindex+1) + 5+5+4;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1368 // Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1369 // encoder->opt_len, encoder->static_len));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1370
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1371 return max_blindex;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1372 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1373
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1374 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1375 * Send the header for a block using dynamic Huffman trees: the counts, the
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1376 * lengths of the bit length codes, the literal tree and the distance tree.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1377 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1378 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1379 var zip_send_all_trees = function(lcodes, dcodes, blcodes) { // number of codes for each tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1380 var rank; // index in bl_order
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1381
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1382 // Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1383 // Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1384 // "too many codes");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1385 // Tracev((stderr, "\nbl counts: "));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1386 zip_send_bits(lcodes-257, 5); // not +255 as stated in appnote.txt
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1387 zip_send_bits(dcodes-1, 5);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1388 zip_send_bits(blcodes-4, 4); // not -3 as stated in appnote.txt
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1389 for(rank = 0; rank < blcodes; rank++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1390 // Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1391 zip_send_bits(zip_bl_tree[zip_bl_order[rank]].dl, 3);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1392 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1393
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1394 // send the literal tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1395 zip_send_tree(zip_dyn_ltree,lcodes-1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1396
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1397 // send the distance tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1398 zip_send_tree(zip_dyn_dtree,dcodes-1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1399 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1400
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1401 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1402 * Determine the best encoding for the current block: dynamic trees, static
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1403 * trees or store, and output the encoded block to the zip file.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1404 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1405 var zip_flush_block = function(eof) { // true if this is the last block for a file
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1406 var opt_lenb, static_lenb; // opt_len and static_len in bytes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1407 var max_blindex; // index of last bit length code of non zero freq
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1408 var stored_len; // length of input block
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1409
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1410 stored_len = zip_strstart - zip_block_start;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1411 zip_flag_buf[zip_last_flags] = zip_flags; // Save the flags for the last 8 items
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1412
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1413 // Construct the literal and distance trees
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1414 zip_build_tree(zip_l_desc);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1415 // Tracev((stderr, "\nlit data: dyn %ld, stat %ld",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1416 // encoder->opt_len, encoder->static_len));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1417
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1418 zip_build_tree(zip_d_desc);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1419 // Tracev((stderr, "\ndist data: dyn %ld, stat %ld",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1420 // encoder->opt_len, encoder->static_len));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1421 /* At this point, opt_len and static_len are the total bit lengths of
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1422 * the compressed block data, excluding the tree representations.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1423 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1424
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1425 /* Build the bit length tree for the above two trees, and get the index
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1426 * in bl_order of the last bit length code to send.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1427 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1428 max_blindex = zip_build_bl_tree();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1429
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1430 // Determine the best encoding. Compute first the block length in bytes
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1431 opt_lenb = (zip_opt_len +3+7)>>3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1432 static_lenb = (zip_static_len+3+7)>>3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1433
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1434 // Trace((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1435 // opt_lenb, encoder->opt_len,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1436 // static_lenb, encoder->static_len, stored_len,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1437 // encoder->last_lit, encoder->last_dist));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1438
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1439 if(static_lenb <= opt_lenb)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1440 opt_lenb = static_lenb;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1441 if(stored_len + 4 <= opt_lenb // 4: two words for the lengths
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1442 && zip_block_start >= 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1443 var i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1444
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1445 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1446 * Otherwise we can't have processed more than WSIZE input bytes since
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1447 * the last block flush, because compression would have been
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1448 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1449 * transform a block into a stored block.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1450 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1451 zip_send_bits((zip_STORED_BLOCK<<1)+eof, 3); /* send block type */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1452 zip_bi_windup(); /* align on byte boundary */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1453 zip_put_short(stored_len);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1454 zip_put_short(~stored_len);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1455
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1456 // copy block
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1457 /*
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1458 p = &window[block_start];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1459 for(i = 0; i < stored_len; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1460 put_byte(p[i]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1461 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1462 for(i = 0; i < stored_len; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1463 zip_put_byte(zip_window[zip_block_start + i]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1464
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1465 } else if(static_lenb == opt_lenb) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1466 zip_send_bits((zip_STATIC_TREES<<1)+eof, 3);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1467 zip_compress_block(zip_static_ltree, zip_static_dtree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1468 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1469 zip_send_bits((zip_DYN_TREES<<1)+eof, 3);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1470 zip_send_all_trees(zip_l_desc.max_code+1,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1471 zip_d_desc.max_code+1,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1472 max_blindex+1);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1473 zip_compress_block(zip_dyn_ltree, zip_dyn_dtree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1474 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1475
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1476 zip_init_block();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1477
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1478 if(eof != 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1479 zip_bi_windup();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1480 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1481
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1482 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1483 * Save the match info and tally the frequency counts. Return true if
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1484 * the current block must be flushed.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1485 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1486 var zip_ct_tally = function(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1487 dist, // distance of matched string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1488 lc) { // match length-MIN_MATCH or unmatched char (if dist==0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1489 zip_l_buf[zip_last_lit++] = lc;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1490 if(dist == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1491 // lc is the unmatched char
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1492 zip_dyn_ltree[lc].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1493 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1494 // Here, lc is the match length - MIN_MATCH
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1495 dist--; // dist = match distance - 1
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1496 // Assert((ush)dist < (ush)MAX_DIST &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1497 // (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1498 // (ush)D_CODE(dist) < (ush)D_CODES, "ct_tally: bad match");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1499
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1500 zip_dyn_ltree[zip_length_code[lc]+zip_LITERALS+1].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1501 zip_dyn_dtree[zip_D_CODE(dist)].fc++;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1502
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1503 zip_d_buf[zip_last_dist++] = dist;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1504 zip_flags \|= zip_flag_bit;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1505 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1506 zip_flag_bit <<= 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1507
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1508 // Output the flags if they fill a byte
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1509 if((zip_last_lit & 7) == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1510 zip_flag_buf[zip_last_flags++] = zip_flags;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1511 zip_flags = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1512 zip_flag_bit = 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1513 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1514 // Try to guess if it is profitable to stop the current block here
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1515 if(zip_compr_level > 2 && (zip_last_lit & 0xfff) == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1516 // Compute an upper bound for the compressed length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1517 var out_length = zip_last_lit * 8;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1518 var in_length = zip_strstart - zip_block_start;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1519 var dcode;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1520
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1521 for(dcode = 0; dcode < zip_D_CODES; dcode++) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1522 out_length += zip_dyn_dtree[dcode].fc * (5 + zip_extra_dbits[dcode]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1523 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1524 out_length >>= 3;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1525 // Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1526 // encoder->last_lit, encoder->last_dist, in_length, out_length,
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1527 // 100L - out_length*100L/in_length));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1528 if(zip_last_dist < parseInt(zip_last_lit/2) &&
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1529 out_length < parseInt(in_length/2))
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1530 return true;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1531 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1532 return (zip_last_lit == zip_LIT_BUFSIZE-1 \|\|
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1533 zip_last_dist == zip_DIST_BUFSIZE);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1534 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1535 * on 16 bit machines and because stored blocks are restricted to
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1536 * 64K-1 bytes.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1537 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1538 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1539
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1540 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1541 * Send the block data compressed using the given Huffman trees
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1542 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1543 var zip_compress_block = function(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1544 ltree, // literal tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1545 dtree) { // distance tree
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1546 var dist; // distance of matched string
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1547 var lc; // match length or unmatched char (if dist == 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1548 var lx = 0; // running index in l_buf
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1549 var dx = 0; // running index in d_buf
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1550 var fx = 0; // running index in flag_buf
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1551 var flag = 0; // current flags
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1552 var code; // the code to send
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1553 var extra; // number of extra bits to send
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1554
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1555 if(zip_last_lit != 0) do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1556 if((lx & 7) == 0)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1557 flag = zip_flag_buf[fx++];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1558 lc = zip_l_buf[lx++] & 0xff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1559 if((flag & 1) == 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1560 zip_SEND_CODE(lc, ltree); /* send a literal byte */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1561 // Tracecv(isgraph(lc), (stderr," '%c' ", lc));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1562 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1563 // Here, lc is the match length - MIN_MATCH
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1564 code = zip_length_code[lc];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1565 zip_SEND_CODE(code+zip_LITERALS+1, ltree); // send the length code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1566 extra = zip_extra_lbits[code];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1567 if(extra != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1568 lc -= zip_base_length[code];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1569 zip_send_bits(lc, extra); // send the extra length bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1570 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1571 dist = zip_d_buf[dx++];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1572 // Here, dist is the match distance - 1
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1573 code = zip_D_CODE(dist);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1574 // Assert (code < D_CODES, "bad d_code");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1575
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1576 zip_SEND_CODE(code, dtree); // send the distance code
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1577 extra = zip_extra_dbits[code];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1578 if(extra != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1579 dist -= zip_base_dist[code];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1580 zip_send_bits(dist, extra); // send the extra distance bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1581 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1582 } // literal or match pair ?
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1583 flag >>= 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1584 } while(lx < zip_last_lit);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1585
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1586 zip_SEND_CODE(zip_END_BLOCK, ltree);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1587 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1588
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1589 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1590 * Send a value on a given number of bits.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1591 * IN assertion: length <= 16 and value fits in length bits.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1592 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1593 var zip_Buf_size = 16; // bit size of bi_buf
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1594 var zip_send_bits = function(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1595 value, // value to send
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1596 length) { // number of bits
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1597 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1598 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1599 * unused bits in value.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1600 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1601 if(zip_bi_valid > zip_Buf_size - length) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1602 zip_bi_buf \|= (value << zip_bi_valid);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1603 zip_put_short(zip_bi_buf);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1604 zip_bi_buf = (value >> (zip_Buf_size - zip_bi_valid));
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1605 zip_bi_valid += length - zip_Buf_size;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1606 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1607 zip_bi_buf \|= value << zip_bi_valid;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1608 zip_bi_valid += length;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1609 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1610 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1611
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1612 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1613 * Reverse the first len bits of a code, using straightforward code (a faster
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1614 * method would use a table)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1615 * IN assertion: 1 <= len <= 15
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1616 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1617 var zip_bi_reverse = function(
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1618 code, // the value to invert
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1619 len) { // its bit length
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1620 var res = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1621 do {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1622 res \|= code & 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1623 code >>= 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1624 res <<= 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1625 } while(--len > 0);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1626 return res >> 1;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1627 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1628
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1629 /* ==========================================================================
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1630 * Write out any remaining bits in an incomplete byte.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1631 */
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1632 var zip_bi_windup = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1633 if(zip_bi_valid > 8) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1634 zip_put_short(zip_bi_buf);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1635 } else if(zip_bi_valid > 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1636 zip_put_byte(zip_bi_buf);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1637 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1638 zip_bi_buf = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1639 zip_bi_valid = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1640 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1641
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1642 var zip_qoutbuf = function() {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1643 if(zip_outcnt != 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1644 var q, i;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1645 q = zip_new_queue();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1646 if(zip_qhead == null)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1647 zip_qhead = zip_qtail = q;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1648 else
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1649 zip_qtail = zip_qtail.next = q;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1650 q.len = zip_outcnt - zip_outoff;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1651 // System.arraycopy(zip_outbuf, zip_outoff, q.ptr, 0, q.len);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1652 for(i = 0; i < q.len; i++)
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1653 q.ptr[i] = zip_outbuf[zip_outoff + i];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1654 zip_outcnt = zip_outoff = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1655 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1656 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1657
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1658 var zip_deflate = function(str, level) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1659 var i, j;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1660
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1661 zip_deflate_data = str;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1662 zip_deflate_pos = 0;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1663 if(typeof level == "undefined")
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1664 level = zip_DEFAULT_LEVEL;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1665 zip_deflate_start(level);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1666
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1667 var buff = new Array(1024);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1668 var aout = [];
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1669 while((i = zip_deflate_internal(buff, 0, buff.length)) > 0) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1670 var cbuf = new Array(i);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1671 for(j = 0; j < i; j++){
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1672 cbuf[j] = String.fromCharCode(buff[j]);
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1673 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1674 aout[aout.length] = cbuf.join("");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1675 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1676 zip_deflate_data = null; // G.C.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1677 return aout.join("");
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1678 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1679
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1680 //
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1681 // end of the script of Masanao Izumo.
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1682 //
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1683
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1684 // we add the compression method for JSZip
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1685 if(!JSZip.compressions["DEFLATE"]) {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1686 JSZip.compressions["DEFLATE"] = {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1687 magic : "\x08\x00",
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1688 compress : zip_deflate
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1689 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1690 } else {
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1691 JSZip.compressions["DEFLATE"].compress = zip_deflate;
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1692 }
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1693
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1694 })();
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1695
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1696 // enforcing Stuk's coding style
b12c99b7c3f0 commit for previous development Zoe Hong <zhong@mpiwg-berlin.mpg.de> parents: diff changeset	1697 // vim: set shiftwidth=3 softtabstop=3: