annotate src/com/jcraft/jzlib/Deflate.java @ 118:9c0aaf27ce28

host editor database values override summary text
author Carl Byington <carl@five-ten-sg.com>
date Wed, 18 Jun 2014 16:53:58 -0700
parents 0ce5cc452d02
children 46c2115ae1c8
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1 /* -*-mode:java; c-basic-offset:2; -*- */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
2 /*
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
3 Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
4
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
5 Redistribution and use in source and binary forms, with or without
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
6 modification, are permitted provided that the following conditions are met:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
7
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
8 1. Redistributions of source code must retain the above copyright notice,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
9 this list of conditions and the following disclaimer.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
10
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
11 2. Redistributions in binary form must reproduce the above copyright
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
12 notice, this list of conditions and the following disclaimer in
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
13 the documentation and/or other materials provided with the distribution.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
14
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
15 3. The names of the authors may not be used to endorse or promote products
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
16 derived from this software without specific prior written permission.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
17
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
18 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
19 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
20 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
21 INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
24 OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
25 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
26 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
27 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
28 */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
29 /*
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
30 * This program is based on zlib-1.1.3, so all credit should go authors
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
31 * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
32 * and contributors of zlib.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
33 */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
34
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
35 package com.jcraft.jzlib;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
36
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
37 public
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
38 final class Deflate {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
39
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
40 static final private int MAX_MEM_LEVEL = 9;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
41
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
42 static final private int Z_DEFAULT_COMPRESSION = -1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
43
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
44 static final private int MAX_WBITS = 15; // 32K LZ77 window
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
45 static final private int DEF_MEM_LEVEL = 8;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
46
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
47 static class Config {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
48 int good_length; // reduce lazy search above this match length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
49 int max_lazy; // do not perform lazy search above this match length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
50 int nice_length; // quit search above this match length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
51 int max_chain;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
52 int func;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
53 Config(int good_length, int max_lazy,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
54 int nice_length, int max_chain, int func) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
55 this.good_length = good_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
56 this.max_lazy = max_lazy;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
57 this.nice_length = nice_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
58 this.max_chain = max_chain;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
59 this.func = func;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
60 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
61 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
62
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
63 static final private int STORED = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
64 static final private int FAST = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
65 static final private int SLOW = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
66 static final private Config[] config_table;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
67 static {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
68 config_table = new Config[10];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
69 // good lazy nice chain
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
70 config_table[0] = new Config(0, 0, 0, 0, STORED);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
71 config_table[1] = new Config(4, 4, 8, 4, FAST);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
72 config_table[2] = new Config(4, 5, 16, 8, FAST);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
73 config_table[3] = new Config(4, 6, 32, 32, FAST);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
74 config_table[4] = new Config(4, 4, 16, 16, SLOW);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
75 config_table[5] = new Config(8, 16, 32, 32, SLOW);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
76 config_table[6] = new Config(8, 16, 128, 128, SLOW);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
77 config_table[7] = new Config(8, 32, 128, 256, SLOW);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
78 config_table[8] = new Config(32, 128, 258, 1024, SLOW);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
79 config_table[9] = new Config(32, 258, 258, 4096, SLOW);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
80 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
81
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
82 static final private String[] z_errmsg = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
83 "need dictionary", // Z_NEED_DICT 2
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
84 "stream end", // Z_STREAM_END 1
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
85 "", // Z_OK 0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
86 "file error", // Z_ERRNO (-1)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
87 "stream error", // Z_STREAM_ERROR (-2)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
88 "data error", // Z_DATA_ERROR (-3)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
89 "insufficient memory", // Z_MEM_ERROR (-4)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
90 "buffer error", // Z_BUF_ERROR (-5)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
91 "incompatible version",// Z_VERSION_ERROR (-6)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
92 ""
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
93 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
94
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
95 // block not completed, need more input or more output
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
96 static final private int NeedMore = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
97
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
98 // block flush performed
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
99 static final private int BlockDone = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
100
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
101 // finish started, need only more output at next deflate
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
102 static final private int FinishStarted = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
103
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
104 // finish done, accept no more input or output
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
105 static final private int FinishDone = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
106
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
107 // preset dictionary flag in zlib header
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
108 static final private int PRESET_DICT = 0x20;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
109
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
110 static final private int Z_FILTERED = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
111 static final private int Z_HUFFMAN_ONLY = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
112 static final private int Z_DEFAULT_STRATEGY = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
113
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
114 static final private int Z_NO_FLUSH = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
115 static final private int Z_PARTIAL_FLUSH = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
116 static final private int Z_SYNC_FLUSH = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
117 static final private int Z_FULL_FLUSH = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
118 static final private int Z_FINISH = 4;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
119
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
120 static final private int Z_OK = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
121 static final private int Z_STREAM_END = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
122 static final private int Z_NEED_DICT = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
123 static final private int Z_ERRNO = -1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
124 static final private int Z_STREAM_ERROR = -2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
125 static final private int Z_DATA_ERROR = -3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
126 static final private int Z_MEM_ERROR = -4;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
127 static final private int Z_BUF_ERROR = -5;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
128 static final private int Z_VERSION_ERROR = -6;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
129
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
130 static final private int INIT_STATE = 42;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
131 static final private int BUSY_STATE = 113;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
132 static final private int FINISH_STATE = 666;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
133
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
134 // The deflate compression method
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
135 static final private int Z_DEFLATED = 8;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
136
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
137 static final private int STORED_BLOCK = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
138 static final private int STATIC_TREES = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
139 static final private int DYN_TREES = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
140
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
141 // The three kinds of block type
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
142 static final private int Z_BINARY = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
143 static final private int Z_ASCII = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
144 static final private int Z_UNKNOWN = 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
145
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
146 static final private int Buf_size = 8 * 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
147
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
148 // repeat previous bit length 3-6 times (2 bits of repeat count)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
149 static final private int REP_3_6 = 16;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
150
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
151 // repeat a zero length 3-10 times (3 bits of repeat count)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
152 static final private int REPZ_3_10 = 17;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
153
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
154 // repeat a zero length 11-138 times (7 bits of repeat count)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
155 static final private int REPZ_11_138 = 18;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
156
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
157 static final private int MIN_MATCH = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
158 static final private int MAX_MATCH = 258;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
159 static final private int MIN_LOOKAHEAD = (MAX_MATCH + MIN_MATCH + 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
160
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
161 static final private int MAX_BITS = 15;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
162 static final private int D_CODES = 30;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
163 static final private int BL_CODES = 19;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
164 static final private int LENGTH_CODES = 29;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
165 static final private int LITERALS = 256;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
166 static final private int L_CODES = (LITERALS + 1 + LENGTH_CODES);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
167 static final private int HEAP_SIZE = (2 * L_CODES + 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
168
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
169 static final private int END_BLOCK = 256;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
170
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
171 ZStream strm; // pointer back to this zlib stream
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
172 int status; // as the name implies
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
173 byte[] pending_buf; // output still pending
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
174 int pending_buf_size; // size of pending_buf
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
175 int pending_out; // next pending byte to output to the stream
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
176 int pending; // nb of bytes in the pending buffer
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
177 int noheader; // suppress zlib header and adler32
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
178 byte data_type; // UNKNOWN, BINARY or ASCII
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
179 byte method; // STORED (for zip only) or DEFLATED
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
180 int last_flush; // value of flush param for previous deflate call
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
181
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
182 int w_size; // LZ77 window size (32K by default)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
183 int w_bits; // log2(w_size) (8..16)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
184 int w_mask; // w_size - 1
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
185
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
186 byte[] window;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
187 // Sliding window. Input bytes are read into the second half of the window,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
188 // and move to the first half later to keep a dictionary of at least wSize
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
189 // bytes. With this organization, matches are limited to a distance of
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
190 // wSize-MAX_MATCH bytes, but this ensures that IO is always
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
191 // performed with a length multiple of the block size. Also, it limits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
192 // the window size to 64K, which is quite useful on MSDOS.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
193 // To do: use the user input buffer as sliding window.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
194
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
195 int window_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
196 // Actual size of window: 2*wSize, except when the user input buffer
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
197 // is directly used as sliding window.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
198
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
199 short[] prev;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
200 // Link to older string with same hash index. To limit the size of this
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
201 // array to 64K, this link is maintained only for the last 32K strings.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
202 // An index in this array is thus a window index modulo 32K.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
203
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
204 short[] head; // Heads of the hash chains or NIL.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
205
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
206 int ins_h; // hash index of string to be inserted
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
207 int hash_size; // number of elements in hash table
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
208 int hash_bits; // log2(hash_size)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
209 int hash_mask; // hash_size-1
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
210
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
211 // Number of bits by which ins_h must be shifted at each input
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
212 // step. It must be such that after MIN_MATCH steps, the oldest
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
213 // byte no longer takes part in the hash key, that is:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
214 // hash_shift * MIN_MATCH >= hash_bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
215 int hash_shift;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
216
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
217 // Window position at the beginning of the current output block. Gets
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
218 // negative when the window is moved backwards.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
219
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
220 int block_start;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
221
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
222 int match_length; // length of best match
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
223 int prev_match; // previous match
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
224 int match_available; // set if previous match exists
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
225 int strstart; // start of string to insert
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
226 int match_start; // start of matching string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
227 int lookahead; // number of valid bytes ahead in window
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
228
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
229 // Length of the best match at previous step. Matches not greater than this
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
230 // are discarded. This is used in the lazy match evaluation.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
231 int prev_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
232
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
233 // To speed up deflation, hash chains are never searched beyond this
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
234 // length. A higher limit improves compression ratio but degrades the speed.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
235 int max_chain_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
236
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
237 // Attempt to find a better match only when the current match is strictly
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
238 // smaller than this value. This mechanism is used only for compression
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
239 // levels >= 4.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
240 int max_lazy_match;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
241
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
242 // Insert new strings in the hash table only if the match length is not
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
243 // greater than this length. This saves time but degrades compression.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
244 // max_insert_length is used only for compression levels <= 3.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
245
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
246 int level; // compression level (1..9)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
247 int strategy; // favor or force Huffman coding
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
248
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
249 // Use a faster search when the previous match is longer than this
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
250 int good_match;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
251
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
252 // Stop searching when current match exceeds this
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
253 int nice_match;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
254
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
255 short[] dyn_ltree; // literal and length tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
256 short[] dyn_dtree; // distance tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
257 short[] bl_tree; // Huffman tree for bit lengths
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
258
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
259 Tree l_desc = new Tree(); // desc for literal tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
260 Tree d_desc = new Tree(); // desc for distance tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
261 Tree bl_desc = new Tree(); // desc for bit length tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
262
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
263 // number of codes at each bit length for an optimal tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
264 short[] bl_count = new short[MAX_BITS + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
265
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
266 // heap used to build the Huffman trees
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
267 int[] heap = new int[2 * L_CODES + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
268
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
269 int heap_len; // number of elements in the heap
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
270 int heap_max; // element of largest frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
271 // The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
272 // The same heap array is used to build all trees.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
273
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
274 // Depth of each subtree used as tie breaker for trees of equal frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
275 byte[] depth = new byte[2 * L_CODES + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
276
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
277 int l_buf; // index for literals or lengths */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
278
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
279 // Size of match buffer for literals/lengths. There are 4 reasons for
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
280 // limiting lit_bufsize to 64K:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
281 // - frequencies can be kept in 16 bit counters
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
282 // - if compression is not successful for the first block, all input
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
283 // data is still in the window so we can still emit a stored block even
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
284 // when input comes from standard input. (This can also be done for
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
285 // all blocks if lit_bufsize is not greater than 32K.)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
286 // - if compression is not successful for a file smaller than 64K, we can
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
287 // even emit a stored file instead of a stored block (saving 5 bytes).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
288 // This is applicable only for zip (not gzip or zlib).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
289 // - creating new Huffman trees less frequently may not provide fast
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
290 // adaptation to changes in the input data statistics. (Take for
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
291 // example a binary file with poorly compressible code followed by
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
292 // a highly compressible string table.) Smaller buffer sizes give
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
293 // fast adaptation but have of course the overhead of transmitting
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
294 // trees more frequently.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
295 // - I can't count above 4
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
296 int lit_bufsize;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
297
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
298 int last_lit; // running index in l_buf
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
299
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
300 // Buffer for distances. To simplify the code, d_buf and l_buf have
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
301 // the same number of elements. To use different lengths, an extra flag
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
302 // array would be necessary.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
303
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
304 int d_buf; // index of pendig_buf
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
305
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
306 int opt_len; // bit length of current block with optimal trees
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
307 int static_len; // bit length of current block with static trees
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
308 int matches; // number of string matches in current block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
309 int last_eob_len; // bit length of EOB code for last block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
310
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
311 // Output buffer. bits are inserted starting at the bottom (least
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
312 // significant bits).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
313 short bi_buf;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
314
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
315 // Number of valid bits in bi_buf. All bits above the last valid bit
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
316 // are always zero.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
317 int bi_valid;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
318
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
319 Deflate() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
320 dyn_ltree = new short[HEAP_SIZE * 2];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
321 dyn_dtree = new short[(2 * D_CODES + 1) * 2]; // distance tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
322 bl_tree = new short[(2 * BL_CODES + 1) * 2]; // Huffman tree for bit lengths
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
323 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
324
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
325 void lm_init() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
326 window_size = 2 * w_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
327 head[hash_size - 1] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
328
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
329 for (int i = 0; i < hash_size - 1; i++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
330 head[i] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
331 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
332
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
333 // Set the default configuration parameters:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
334 max_lazy_match = Deflate.config_table[level].max_lazy;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
335 good_match = Deflate.config_table[level].good_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
336 nice_match = Deflate.config_table[level].nice_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
337 max_chain_length = Deflate.config_table[level].max_chain;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
338 strstart = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
339 block_start = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
340 lookahead = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
341 match_length = prev_length = MIN_MATCH - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
342 match_available = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
343 ins_h = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
344 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
345
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
346 // Initialize the tree data structures for a new zlib stream.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
347 void tr_init() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
348 l_desc.dyn_tree = dyn_ltree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
349 l_desc.stat_desc = StaticTree.static_l_desc;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
350 d_desc.dyn_tree = dyn_dtree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
351 d_desc.stat_desc = StaticTree.static_d_desc;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
352 bl_desc.dyn_tree = bl_tree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
353 bl_desc.stat_desc = StaticTree.static_bl_desc;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
354 bi_buf = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
355 bi_valid = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
356 last_eob_len = 8; // enough lookahead for inflate
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
357 // Initialize the first block of the first file:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
358 init_block();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
359 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
360
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
361 void init_block() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
362 // Initialize the trees.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
363 for (int i = 0; i < L_CODES; i++) dyn_ltree[i * 2] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
364
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
365 for (int i = 0; i < D_CODES; i++) dyn_dtree[i * 2] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
366
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
367 for (int i = 0; i < BL_CODES; i++) bl_tree[i * 2] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
368
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
369 dyn_ltree[END_BLOCK * 2] = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
370 opt_len = static_len = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
371 last_lit = matches = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
372 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
373
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
374 // Restore the heap property by moving down the tree starting at node k,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
375 // exchanging a node with the smallest of its two sons if necessary, stopping
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
376 // when the heap property is re-established (each father smaller than its
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
377 // two sons).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
378 void pqdownheap(short[] tree, // the tree to restore
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
379 int k // node to move down
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
380 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
381 int v = heap[k];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
382 int j = k << 1; // left son of k
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
383
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
384 while (j <= heap_len) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
385 // Set j to the smallest of the two sons:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
386 if (j < heap_len &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
387 smaller(tree, heap[j + 1], heap[j], depth)) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
388 j++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
389 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
390
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
391 // Exit if v is smaller than both sons
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
392 if (smaller(tree, v, heap[j], depth)) break;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
393
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
394 // Exchange v with the smallest son
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
395 heap[k] = heap[j]; k = j;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
396 // And continue down the tree, setting j to the left son of k
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
397 j <<= 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
398 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
399
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
400 heap[k] = v;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
401 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
402
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
403 static boolean smaller(short[] tree, int n, int m, byte[] depth) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
404 short tn2 = tree[n * 2];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
405 short tm2 = tree[m * 2];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
406 return (tn2 < tm2 ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
407 (tn2 == tm2 && depth[n] <= depth[m]));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
408 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
409
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
410 // Scan a literal or distance tree to determine the frequencies of the codes
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
411 // in the bit length tree.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
412 void scan_tree(short[] tree, // the tree to be scanned
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
413 int max_code // and its largest code of non zero frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
414 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
415 int n; // iterates over all tree elements
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
416 int prevlen = -1; // last emitted length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
417 int curlen; // length of current code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
418 int nextlen = tree[0 * 2 + 1]; // length of next code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
419 int count = 0; // repeat count of the current code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
420 int max_count = 7; // max repeat count
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
421 int min_count = 4; // min repeat count
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
422
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
423 if (nextlen == 0) { max_count = 138; min_count = 3; }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
424
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
425 tree[(max_code + 1) * 2 + 1] = (short)0xffff; // guard
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
426
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
427 for (n = 0; n <= max_code; n++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
428 curlen = nextlen; nextlen = tree[(n + 1) * 2 + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
429
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
430 if (++count < max_count && curlen == nextlen) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
431 continue;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
432 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
433 else if (count < min_count) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
434 bl_tree[curlen * 2] += count;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
435 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
436 else if (curlen != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
437 if (curlen != prevlen) bl_tree[curlen * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
438
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
439 bl_tree[REP_3_6 * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
440 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
441 else if (count <= 10) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
442 bl_tree[REPZ_3_10 * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
443 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
444 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
445 bl_tree[REPZ_11_138 * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
446 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
447
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
448 count = 0; prevlen = curlen;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
449
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
450 if (nextlen == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
451 max_count = 138; min_count = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
452 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
453 else if (curlen == nextlen) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
454 max_count = 6; min_count = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
455 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
456 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
457 max_count = 7; min_count = 4;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
458 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
459 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
460 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
461
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
462 // Construct the Huffman tree for the bit lengths and return the index in
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
463 // bl_order of the last bit length code to send.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
464 int build_bl_tree() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
465 int max_blindex; // index of last bit length code of non zero freq
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
466 // Determine the bit length frequencies for literal and distance trees
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
467 scan_tree(dyn_ltree, l_desc.max_code);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
468 scan_tree(dyn_dtree, d_desc.max_code);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
469 // Build the bit length tree:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
470 bl_desc.build_tree(this);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
471
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
472 // opt_len now includes the length of the tree representations, except
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
473 // the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
474 // Determine the number of bit length codes to send. The pkzip format
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
475 // requires that at least 4 bit length codes be sent. (appnote.txt says
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
476 // 3 but the actual value used is 4.)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
477 for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
478 if (bl_tree[Tree.bl_order[max_blindex] * 2 + 1] != 0) break;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
479 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
480
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
481 // Update opt_len to include the bit length tree and counts
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
482 opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
483 return max_blindex;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
484 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
485
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
486
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
487 // Send the header for a block using dynamic Huffman trees: the counts, the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
488 // lengths of the bit length codes, the literal tree and the distance tree.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
489 // IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
490 void send_all_trees(int lcodes, int dcodes, int blcodes) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
491 int rank; // index in bl_order
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
492 send_bits(lcodes - 257, 5); // not +255 as stated in appnote.txt
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
493 send_bits(dcodes - 1, 5);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
494 send_bits(blcodes - 4, 4); // not -3 as stated in appnote.txt
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
495
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
496 for (rank = 0; rank < blcodes; rank++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
497 send_bits(bl_tree[Tree.bl_order[rank] * 2 + 1], 3);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
498 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
499
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
500 send_tree(dyn_ltree, lcodes - 1); // literal tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
501 send_tree(dyn_dtree, dcodes - 1); // distance tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
502 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
503
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
504 // Send a literal or distance tree in compressed form, using the codes in
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
505 // bl_tree.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
506 void send_tree(short[] tree, // the tree to be sent
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
507 int max_code // and its largest code of non zero frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
508 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
509 int n; // iterates over all tree elements
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
510 int prevlen = -1; // last emitted length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
511 int curlen; // length of current code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
512 int nextlen = tree[0 * 2 + 1]; // length of next code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
513 int count = 0; // repeat count of the current code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
514 int max_count = 7; // max repeat count
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
515 int min_count = 4; // min repeat count
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
516
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
517 if (nextlen == 0) { max_count = 138; min_count = 3; }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
518
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
519 for (n = 0; n <= max_code; n++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
520 curlen = nextlen; nextlen = tree[(n + 1) * 2 + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
521
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
522 if (++count < max_count && curlen == nextlen) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
523 continue;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
524 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
525 else if (count < min_count) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
526 do { send_code(curlen, bl_tree); }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
527 while (--count != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
528 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
529 else if (curlen != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
530 if (curlen != prevlen) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
531 send_code(curlen, bl_tree); count--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
532 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
533
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
534 send_code(REP_3_6, bl_tree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
535 send_bits(count - 3, 2);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
536 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
537 else if (count <= 10) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
538 send_code(REPZ_3_10, bl_tree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
539 send_bits(count - 3, 3);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
540 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
541 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
542 send_code(REPZ_11_138, bl_tree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
543 send_bits(count - 11, 7);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
544 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
545
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
546 count = 0; prevlen = curlen;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
547
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
548 if (nextlen == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
549 max_count = 138; min_count = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
550 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
551 else if (curlen == nextlen) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
552 max_count = 6; min_count = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
553 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
554 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
555 max_count = 7; min_count = 4;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
556 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
557 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
558 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
559
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
560 // Output a byte on the stream.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
561 // IN assertion: there is enough room in pending_buf.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
562 final void put_byte(byte[] p, int start, int len) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
563 System.arraycopy(p, start, pending_buf, pending, len);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
564 pending += len;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
565 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
566
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
567 final void put_byte(byte c) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
568 pending_buf[pending++] = c;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
569 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
570 final void put_short(int w) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
571 put_byte((byte)(w/*&0xff*/));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
572 put_byte((byte)(w >>> 8));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
573 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
574 final void putShortMSB(int b) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
575 put_byte((byte)(b >> 8));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
576 put_byte((byte)(b/*&0xff*/));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
577 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
578
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
579 final void send_code(int c, short[] tree) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
580 int c2 = c * 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
581 send_bits((tree[c2] & 0xffff), (tree[c2 + 1] & 0xffff));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
582 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
583
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
584 void send_bits(int value, int length) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
585 int len = length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
586
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
587 if (bi_valid > (int)Buf_size - len) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
588 int val = value;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
589 // bi_buf |= (val << bi_valid);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
590 bi_buf |= ((val << bi_valid) & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
591 put_short(bi_buf);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
592 bi_buf = (short)(val >>> (Buf_size - bi_valid));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
593 bi_valid += len - Buf_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
594 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
595 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
596 // bi_buf |= (value) << bi_valid;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
597 bi_buf |= (((value) << bi_valid) & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
598 bi_valid += len;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
599 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
600 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
601
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
602 // Send one empty static block to give enough lookahead for inflate.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
603 // This takes 10 bits, of which 7 may remain in the bit buffer.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
604 // The current inflate code requires 9 bits of lookahead. If the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
605 // last two codes for the previous block (real code plus EOB) were coded
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
606 // on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
607 // the last real code. In this case we send two empty static blocks instead
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
608 // of one. (There are no problems if the previous block is stored or fixed.)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
609 // To simplify the code, we assume the worst case of last real code encoded
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
610 // on one bit only.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
611 void _tr_align() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
612 send_bits(STATIC_TREES << 1, 3);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
613 send_code(END_BLOCK, StaticTree.static_ltree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
614 bi_flush();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
615
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
616 // Of the 10 bits for the empty block, we have already sent
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
617 // (10 - bi_valid) bits. The lookahead for the last real code (before
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
618 // the EOB of the previous block) was thus at least one plus the length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
619 // of the EOB plus what we have just sent of the empty static block.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
620 if (1 + last_eob_len + 10 - bi_valid < 9) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
621 send_bits(STATIC_TREES << 1, 3);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
622 send_code(END_BLOCK, StaticTree.static_ltree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
623 bi_flush();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
624 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
625
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
626 last_eob_len = 7;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
627 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
628
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
629
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
630 // Save the match info and tally the frequency counts. Return true if
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
631 // the current block must be flushed.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
632 boolean _tr_tally(int dist, // distance of matched string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
633 int lc // match length-MIN_MATCH or unmatched char (if dist==0)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
634 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
635 pending_buf[d_buf + last_lit * 2] = (byte)(dist >>> 8);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
636 pending_buf[d_buf + last_lit * 2 + 1] = (byte)dist;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
637 pending_buf[l_buf + last_lit] = (byte)lc; last_lit++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
638
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
639 if (dist == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
640 // lc is the unmatched char
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
641 dyn_ltree[lc * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
642 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
643 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
644 matches++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
645 // Here, lc is the match length - MIN_MATCH
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
646 dist--; // dist = match distance - 1
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
647 dyn_ltree[(Tree._length_code[lc] + LITERALS + 1) * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
648 dyn_dtree[Tree.d_code(dist) * 2]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
649 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
650
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
651 if ((last_lit & 0x1fff) == 0 && level > 2) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
652 // Compute an upper bound for the compressed length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
653 int out_length = last_lit * 8;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
654 int in_length = strstart - block_start;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
655 int dcode;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
656
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
657 for (dcode = 0; dcode < D_CODES; dcode++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
658 out_length += (int)dyn_dtree[dcode * 2] *
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
659 (5L + Tree.extra_dbits[dcode]);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
660 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
661
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
662 out_length >>>= 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
663
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
664 if ((matches < (last_lit / 2)) && out_length < in_length / 2) return true;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
665 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
666
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
667 return (last_lit == lit_bufsize - 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
668 // We avoid equality with lit_bufsize because of wraparound at 64K
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
669 // on 16 bit machines and because stored blocks are restricted to
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
670 // 64K-1 bytes.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
671 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
672
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
673 // Send the block data compressed using the given Huffman trees
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
674 void compress_block(short[] ltree, short[] dtree) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
675 int dist; // distance of matched string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
676 int lc; // match length or unmatched char (if dist == 0)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
677 int lx = 0; // running index in l_buf
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
678 int code; // the code to send
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
679 int extra; // number of extra bits to send
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
680
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
681 if (last_lit != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
682 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
683 dist = ((pending_buf[d_buf + lx * 2] << 8) & 0xff00) |
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
684 (pending_buf[d_buf + lx * 2 + 1] & 0xff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
685 lc = (pending_buf[l_buf + lx]) & 0xff; lx++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
686
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
687 if (dist == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
688 send_code(lc, ltree); // send a literal byte
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
689 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
690 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
691 // Here, lc is the match length - MIN_MATCH
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
692 code = Tree._length_code[lc];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
693 send_code(code + LITERALS + 1, ltree); // send the length code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
694 extra = Tree.extra_lbits[code];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
695
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
696 if (extra != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
697 lc -= Tree.base_length[code];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
698 send_bits(lc, extra); // send the extra length bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
699 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
700
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
701 dist--; // dist is now the match distance - 1
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
702 code = Tree.d_code(dist);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
703 send_code(code, dtree); // send the distance code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
704 extra = Tree.extra_dbits[code];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
705
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
706 if (extra != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
707 dist -= Tree.base_dist[code];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
708 send_bits(dist, extra); // send the extra distance bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
709 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
710 } // literal or match pair ?
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
711
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
712 // Check that the overlay between pending_buf and d_buf+l_buf is ok:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
713 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
714 while (lx < last_lit);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
715 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
716
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
717 send_code(END_BLOCK, ltree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
718 last_eob_len = ltree[END_BLOCK * 2 + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
719 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
720
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
721 // Set the data type to ASCII or BINARY, using a crude approximation:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
722 // binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
723 // IN assertion: the fields freq of dyn_ltree are set and the total of all
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
724 // frequencies does not exceed 64K (to fit in an int on 16 bit machines).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
725 void set_data_type() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
726 int n = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
727 int ascii_freq = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
728 int bin_freq = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
729
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
730 while (n < 7) { bin_freq += dyn_ltree[n * 2]; n++;}
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
731
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
732 while (n < 128) { ascii_freq += dyn_ltree[n * 2]; n++;}
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
733
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
734 while (n < LITERALS) { bin_freq += dyn_ltree[n * 2]; n++;}
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
735
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
736 data_type = (byte)(bin_freq > (ascii_freq >>> 2) ? Z_BINARY : Z_ASCII);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
737 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
738
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
739 // Flush the bit buffer, keeping at most 7 bits in it.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
740 void bi_flush() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
741 if (bi_valid == 16) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
742 put_short(bi_buf);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
743 bi_buf = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
744 bi_valid = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
745 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
746 else if (bi_valid >= 8) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
747 put_byte((byte)bi_buf);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
748 bi_buf >>>= 8;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
749 bi_valid -= 8;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
750 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
751 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
752
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
753 // Flush the bit buffer and align the output on a byte boundary
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
754 void bi_windup() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
755 if (bi_valid > 8) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
756 put_short(bi_buf);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
757 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
758 else if (bi_valid > 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
759 put_byte((byte)bi_buf);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
760 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
761
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
762 bi_buf = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
763 bi_valid = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
764 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
765
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
766 // Copy a stored block, storing first the length and its
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
767 // one's complement if requested.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
768 void copy_block(int buf, // the input data
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
769 int len, // its length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
770 boolean header // true if block header must be written
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
771 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
772 int index = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
773 bi_windup(); // align on byte boundary
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
774 last_eob_len = 8; // enough lookahead for inflate
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
775
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
776 if (header) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
777 put_short((short)len);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
778 put_short((short)~len);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
779 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
780
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
781 // while(len--!=0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
782 // put_byte(window[buf+index]);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
783 // index++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
784 // }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
785 put_byte(window, buf, len);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
786 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
787
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
788 void flush_block_only(boolean eof) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
789 _tr_flush_block(block_start >= 0 ? block_start : -1,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
790 strstart - block_start,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
791 eof);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
792 block_start = strstart;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
793 strm.flush_pending();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
794 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
795
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
796 // Copy without compression as much as possible from the input stream, return
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
797 // the current block state.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
798 // This function does not insert new strings in the dictionary since
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
799 // uncompressible data is probably not useful. This function is used
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
800 // only for the level=0 compression option.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
801 // NOTE: this function should be optimized to avoid extra copying from
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
802 // window to pending_buf.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
803 int deflate_stored(int flush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
804 // Stored blocks are limited to 0xffff bytes, pending_buf is limited
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
805 // to pending_buf_size, and each stored block has a 5 byte header:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
806 int max_block_size = 0xffff;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
807 int max_start;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
808
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
809 if (max_block_size > pending_buf_size - 5) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
810 max_block_size = pending_buf_size - 5;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
811 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
812
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
813 // Copy as much as possible from input to output:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
814 while (true) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
815 // Fill the window as much as possible:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
816 if (lookahead <= 1) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
817 fill_window();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
818
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
819 if (lookahead == 0 && flush == Z_NO_FLUSH) return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
820
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
821 if (lookahead == 0) break; // flush the current block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
822 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
823
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
824 strstart += lookahead;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
825 lookahead = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
826 // Emit a stored block if pending_buf will be full:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
827 max_start = block_start + max_block_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
828
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
829 if (strstart == 0 || strstart >= max_start) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
830 // strstart == 0 is possible when wraparound on 16-bit machine
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
831 lookahead = (int)(strstart - max_start);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
832 strstart = (int)max_start;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
833 flush_block_only(false);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
834
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
835 if (strm.avail_out == 0) return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
836 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
837
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
838 // Flush if we may have to slide, otherwise block_start may become
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
839 // negative and the data will be gone:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
840 if (strstart - block_start >= w_size - MIN_LOOKAHEAD) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
841 flush_block_only(false);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
842
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
843 if (strm.avail_out == 0) return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
844 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
845 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
846
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
847 flush_block_only(flush == Z_FINISH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
848
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
849 if (strm.avail_out == 0)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
850 return (flush == Z_FINISH) ? FinishStarted : NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
851
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
852 return flush == Z_FINISH ? FinishDone : BlockDone;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
853 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
854
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
855 // Send a stored block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
856 void _tr_stored_block(int buf, // input block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
857 int stored_len, // length of input block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
858 boolean eof // true if this is the last block for a file
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
859 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
860 send_bits((STORED_BLOCK << 1) + (eof ? 1 : 0), 3); // send block type
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
861 copy_block(buf, stored_len, true); // with header
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
862 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
863
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
864 // Determine the best encoding for the current block: dynamic trees, static
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
865 // trees or store, and output the encoded block to the zip file.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
866 void _tr_flush_block(int buf, // input block, or NULL if too old
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
867 int stored_len, // length of input block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
868 boolean eof // true if this is the last block for a file
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
869 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
870 int opt_lenb, static_lenb;// opt_len and static_len in bytes
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
871 int max_blindex = 0; // index of last bit length code of non zero freq
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
872
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
873 // Build the Huffman trees unless a stored block is forced
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
874 if (level > 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
875 // Check if the file is ascii or binary
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
876 if (data_type == Z_UNKNOWN) set_data_type();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
877
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
878 // Construct the literal and distance trees
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
879 l_desc.build_tree(this);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
880 d_desc.build_tree(this);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
881 // At this point, opt_len and static_len are the total bit lengths of
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
882 // the compressed block data, excluding the tree representations.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
883 // Build the bit length tree for the above two trees, and get the index
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
884 // in bl_order of the last bit length code to send.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
885 max_blindex = build_bl_tree();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
886 // Determine the best encoding. Compute first the block length in bytes
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
887 opt_lenb = (opt_len + 3 + 7) >>> 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
888 static_lenb = (static_len + 3 + 7) >>> 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
889
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
890 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
891 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
892 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
893 opt_lenb = static_lenb = stored_len + 5; // force a stored block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
894 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
895
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
896 if (stored_len + 4 <= opt_lenb && buf != -1) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
897 // 4: two words for the lengths
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
898 // The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
899 // Otherwise we can't have processed more than WSIZE input bytes since
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
900 // the last block flush, because compression would have been
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
901 // successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
902 // transform a block into a stored block.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
903 _tr_stored_block(buf, stored_len, eof);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
904 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
905 else if (static_lenb == opt_lenb) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
906 send_bits((STATIC_TREES << 1) + (eof ? 1 : 0), 3);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
907 compress_block(StaticTree.static_ltree, StaticTree.static_dtree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
908 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
909 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
910 send_bits((DYN_TREES << 1) + (eof ? 1 : 0), 3);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
911 send_all_trees(l_desc.max_code + 1, d_desc.max_code + 1, max_blindex + 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
912 compress_block(dyn_ltree, dyn_dtree);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
913 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
914
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
915 // The above check is made mod 2^32, for files larger than 512 MB
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
916 // and uLong implemented on 32 bits.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
917 init_block();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
918
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
919 if (eof) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
920 bi_windup();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
921 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
922 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
923
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
924 // Fill the window when the lookahead becomes insufficient.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
925 // Updates strstart and lookahead.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
926 //
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
927 // IN assertion: lookahead < MIN_LOOKAHEAD
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
928 // OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
929 // At least one byte has been read, or avail_in == 0; reads are
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
930 // performed for at least two bytes (required for the zip translate_eol
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
931 // option -- not supported here).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
932 void fill_window() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
933 int n, m;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
934 int p;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
935 int more; // Amount of free space at the end of the window.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
936
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
937 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
938 more = (window_size - lookahead - strstart);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
939
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
940 // Deal with !@#$% 64K limit:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
941 if (more == 0 && strstart == 0 && lookahead == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
942 more = w_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
943 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
944 else if (more == -1) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
945 // Very unlikely, but possible on 16 bit machine if strstart == 0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
946 // and lookahead == 1 (input done one byte at time)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
947 more--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
948 // If the window is almost full and there is insufficient lookahead,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
949 // move the upper half to the lower one to make room in the upper half.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
950 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
951 else if (strstart >= w_size + w_size - MIN_LOOKAHEAD) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
952 System.arraycopy(window, w_size, window, 0, w_size);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
953 match_start -= w_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
954 strstart -= w_size; // we now have strstart >= MAX_DIST
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
955 block_start -= w_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
956 // Slide the hash table (could be avoided with 32 bit values
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
957 // at the expense of memory usage). We slide even when level == 0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
958 // to keep the hash table consistent if we switch back to level > 0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
959 // later. (Using level 0 permanently is not an optimal usage of
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
960 // zlib, so we don't care about this pathological case.)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
961 n = hash_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
962 p = n;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
963
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
964 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
965 m = (head[--p] & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
966 head[p] = (m >= w_size ? (short)(m - w_size) : 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
967 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
968 while (--n != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
969
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
970 n = w_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
971 p = n;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
972
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
973 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
974 m = (prev[--p] & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
975 prev[p] = (m >= w_size ? (short)(m - w_size) : 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
976 // If n is not on any hash chain, prev[n] is garbage but
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
977 // its value will never be used.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
978 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
979 while (--n != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
980
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
981 more += w_size;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
982 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
983
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
984 if (strm.avail_in == 0) return;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
985
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
986 // If there was no sliding:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
987 // strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
988 // more == window_size - lookahead - strstart
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
989 // => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
990 // => more >= window_size - 2*WSIZE + 2
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
991 // In the BIG_MEM or MMAP case (not yet supported),
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
992 // window_size == input_size + MIN_LOOKAHEAD &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
993 // strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
994 // Otherwise, window_size == 2*WSIZE so more >= 2.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
995 // If there was sliding, more >= WSIZE. So in all cases, more >= 2.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
996 n = strm.read_buf(window, strstart + lookahead, more);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
997 lookahead += n;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
998
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
999 // Initialize the hash value now that we have some input:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1000 if (lookahead >= MIN_MATCH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1001 ins_h = window[strstart] & 0xff;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1002 ins_h = (((ins_h) << hash_shift) ^ (window[strstart + 1] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1003 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1004
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1005 // If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1006 // but this is not important since only literal bytes will be emitted.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1007 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1008 while (lookahead < MIN_LOOKAHEAD && strm.avail_in != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1009 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1010
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1011 // Compress as much as possible from the input stream, return the current
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1012 // block state.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1013 // This function does not perform lazy evaluation of matches and inserts
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1014 // new strings in the dictionary only for unmatched strings or for short
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1015 // matches. It is used only for the fast compression options.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1016 int deflate_fast(int flush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1017 // short hash_head = 0; // head of the hash chain
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1018 int hash_head = 0; // head of the hash chain
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1019 boolean bflush; // set if current block must be flushed
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1020
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1021 while (true) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1022 // Make sure that we always have enough lookahead, except
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1023 // at the end of the input file. We need MAX_MATCH bytes
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1024 // for the next match, plus MIN_MATCH bytes to insert the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1025 // string following the next match.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1026 if (lookahead < MIN_LOOKAHEAD) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1027 fill_window();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1028
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1029 if (lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1030 return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1031 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1032
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1033 if (lookahead == 0) break; // flush the current block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1034 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1035
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1036 // Insert the string window[strstart .. strstart+2] in the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1037 // dictionary, and set hash_head to the head of the hash chain:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1038 if (lookahead >= MIN_MATCH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1039 ins_h = (((ins_h) << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1040 // prev[strstart&w_mask]=hash_head=head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1041 hash_head = (head[ins_h] & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1042 prev[strstart & w_mask] = head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1043 head[ins_h] = (short)strstart;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1044 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1045
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1046 // Find the longest match, discarding those <= prev_length.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1047 // At this point we have always match_length < MIN_MATCH
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1048 if (hash_head != 0L &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1049 ((strstart - hash_head) & 0xffff) <= w_size - MIN_LOOKAHEAD
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1050 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1051 // To simplify the code, we prevent matches with the string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1052 // of window index 0 (in particular we have to avoid a match
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1053 // of the string with itself at the start of the input file).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1054 if (strategy != Z_HUFFMAN_ONLY) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1055 match_length = longest_match(hash_head);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1056 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1057
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1058 // longest_match() sets match_start
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1059 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1060
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1061 if (match_length >= MIN_MATCH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1062 // check_match(strstart, match_start, match_length);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1063 bflush = _tr_tally(strstart - match_start, match_length - MIN_MATCH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1064 lookahead -= match_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1065
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1066 // Insert new strings in the hash table only if the match length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1067 // is not too large. This saves time but degrades compression.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1068 if (match_length <= max_lazy_match &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1069 lookahead >= MIN_MATCH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1070 match_length--; // string at strstart already in hash table
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1071
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1072 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1073 strstart++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1074 ins_h = ((ins_h << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1075 // prev[strstart&w_mask]=hash_head=head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1076 hash_head = (head[ins_h] & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1077 prev[strstart & w_mask] = head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1078 head[ins_h] = (short)strstart;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1079 // strstart never exceeds WSIZE-MAX_MATCH, so there are
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1080 // always MIN_MATCH bytes ahead.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1081 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1082 while (--match_length != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1083
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1084 strstart++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1085 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1086 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1087 strstart += match_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1088 match_length = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1089 ins_h = window[strstart] & 0xff;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1090 ins_h = (((ins_h) << hash_shift) ^ (window[strstart + 1] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1091 // If lookahead < MIN_MATCH, ins_h is garbage, but it does not
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1092 // matter since it will be recomputed at next deflate call.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1093 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1094 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1095 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1096 // No match, output a literal byte
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1097 bflush = _tr_tally(0, window[strstart] & 0xff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1098 lookahead--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1099 strstart++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1100 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1101
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1102 if (bflush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1103 flush_block_only(false);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1104
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1105 if (strm.avail_out == 0) return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1106 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1107 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1108
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1109 flush_block_only(flush == Z_FINISH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1110
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1111 if (strm.avail_out == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1112 if (flush == Z_FINISH) return FinishStarted;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1113 else return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1114 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1115
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1116 return flush == Z_FINISH ? FinishDone : BlockDone;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1117 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1118
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1119 // Same as above, but achieves better compression. We use a lazy
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1120 // evaluation for matches: a match is finally adopted only if there is
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1121 // no better match at the next window position.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1122 int deflate_slow(int flush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1123 // short hash_head = 0; // head of hash chain
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1124 int hash_head = 0; // head of hash chain
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1125 boolean bflush; // set if current block must be flushed
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1126
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1127 // Process the input block.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1128 while (true) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1129 // Make sure that we always have enough lookahead, except
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1130 // at the end of the input file. We need MAX_MATCH bytes
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1131 // for the next match, plus MIN_MATCH bytes to insert the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1132 // string following the next match.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1133 if (lookahead < MIN_LOOKAHEAD) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1134 fill_window();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1135
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1136 if (lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1137 return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1138 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1139
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1140 if (lookahead == 0) break; // flush the current block
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1141 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1142
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1143 // Insert the string window[strstart .. strstart+2] in the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1144 // dictionary, and set hash_head to the head of the hash chain:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1145 if (lookahead >= MIN_MATCH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1146 ins_h = (((ins_h) << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1147 // prev[strstart&w_mask]=hash_head=head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1148 hash_head = (head[ins_h] & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1149 prev[strstart & w_mask] = head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1150 head[ins_h] = (short)strstart;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1151 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1152
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1153 // Find the longest match, discarding those <= prev_length.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1154 prev_length = match_length; prev_match = match_start;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1155 match_length = MIN_MATCH - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1156
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1157 if (hash_head != 0 && prev_length < max_lazy_match &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1158 ((strstart - hash_head) & 0xffff) <= w_size - MIN_LOOKAHEAD
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1159 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1160 // To simplify the code, we prevent matches with the string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1161 // of window index 0 (in particular we have to avoid a match
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1162 // of the string with itself at the start of the input file).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1163 if (strategy != Z_HUFFMAN_ONLY) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1164 match_length = longest_match(hash_head);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1165 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1166
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1167 // longest_match() sets match_start
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1168 if (match_length <= 5 && (strategy == Z_FILTERED ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1169 (match_length == MIN_MATCH &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1170 strstart - match_start > 4096))) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1171 // If prev_match is also MIN_MATCH, match_start is garbage
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1172 // but we will ignore the current match anyway.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1173 match_length = MIN_MATCH - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1174 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1175 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1176
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1177 // If there was a match at the previous step and the current
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1178 // match is not better, output the previous match:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1179 if (prev_length >= MIN_MATCH && match_length <= prev_length) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1180 int max_insert = strstart + lookahead - MIN_MATCH;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1181 // Do not insert strings in hash table beyond this.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1182 // check_match(strstart-1, prev_match, prev_length);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1183 bflush = _tr_tally(strstart - 1 - prev_match, prev_length - MIN_MATCH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1184 // Insert in hash table all strings up to the end of the match.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1185 // strstart-1 and strstart are already inserted. If there is not
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1186 // enough lookahead, the last two strings are not inserted in
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1187 // the hash table.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1188 lookahead -= prev_length - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1189 prev_length -= 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1190
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1191 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1192 if (++strstart <= max_insert) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1193 ins_h = (((ins_h) << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1194 //prev[strstart&w_mask]=hash_head=head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1195 hash_head = (head[ins_h] & 0xffff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1196 prev[strstart & w_mask] = head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1197 head[ins_h] = (short)strstart;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1198 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1199 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1200 while (--prev_length != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1201
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1202 match_available = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1203 match_length = MIN_MATCH - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1204 strstart++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1205
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1206 if (bflush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1207 flush_block_only(false);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1208
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1209 if (strm.avail_out == 0) return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1210 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1211 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1212 else if (match_available != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1213 // If there was no match at the previous position, output a
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1214 // single literal. If there was a match but the current match
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1215 // is longer, truncate the previous match to a single literal.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1216 bflush = _tr_tally(0, window[strstart - 1] & 0xff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1217
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1218 if (bflush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1219 flush_block_only(false);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1220 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1221
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1222 strstart++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1223 lookahead--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1224
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1225 if (strm.avail_out == 0) return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1226 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1227 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1228 // There is no previous match to compare with, wait for
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1229 // the next step to decide.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1230 match_available = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1231 strstart++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1232 lookahead--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1233 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1234 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1235
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1236 if (match_available != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1237 bflush = _tr_tally(0, window[strstart - 1] & 0xff);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1238 match_available = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1239 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1240
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1241 flush_block_only(flush == Z_FINISH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1242
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1243 if (strm.avail_out == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1244 if (flush == Z_FINISH) return FinishStarted;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1245 else return NeedMore;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1246 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1247
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1248 return flush == Z_FINISH ? FinishDone : BlockDone;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1249 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1250
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1251 int longest_match(int cur_match) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1252 int chain_length = max_chain_length; // max hash chain length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1253 int scan = strstart; // current string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1254 int match; // matched string
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1255 int len; // length of current match
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1256 int best_len = prev_length; // best match length so far
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1257 int limit = strstart > (w_size - MIN_LOOKAHEAD) ?
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1258 strstart - (w_size - MIN_LOOKAHEAD) : 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1259 int nice_match = this.nice_match;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1260 // Stop when cur_match becomes <= limit. To simplify the code,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1261 // we prevent matches with the string of window index 0.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1262 int wmask = w_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1263 int strend = strstart + MAX_MATCH;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1264 byte scan_end1 = window[scan + best_len - 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1265 byte scan_end = window[scan + best_len];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1266
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1267 // The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1268 // It is easy to get rid of this optimization if necessary.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1269 // Do not waste too much time if we already have a good match:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1270 if (prev_length >= good_match) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1271 chain_length >>= 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1272 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1273
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1274 // Do not look for matches beyond the end of the input. This is necessary
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1275 // to make deflate deterministic.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1276 if (nice_match > lookahead) nice_match = lookahead;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1277
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1278 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1279 match = cur_match;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1280
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1281 // Skip to next match if the match length cannot increase
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1282 // or if the match length is less than 2:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1283 if (window[match + best_len] != scan_end ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1284 window[match + best_len - 1] != scan_end1 ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1285 window[match] != window[scan] ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1286 window[++match] != window[scan + 1]) continue;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1287
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1288 // The check at best_len-1 can be removed because it will be made
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1289 // again later. (This heuristic is not always a win.)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1290 // It is not necessary to compare scan[2] and match[2] since they
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1291 // are always equal when the other bytes match, given that
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1292 // the hash keys are equal and that HASH_BITS >= 8.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1293 scan += 2; match++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1294
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1295 // We check for insufficient lookahead only every 8th comparison;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1296 // the 256th check will be made at strstart+258.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1297 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1298 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1299 while (window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1300 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1301 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1302 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1303 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1304 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1305 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1306 window[++scan] == window[++match] &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1307 scan < strend);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1308
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1309 len = MAX_MATCH - (int)(strend - scan);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1310 scan = strend - MAX_MATCH;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1311
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1312 if (len > best_len) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1313 match_start = cur_match;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1314 best_len = len;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1315
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1316 if (len >= nice_match) break;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1317
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1318 scan_end1 = window[scan + best_len - 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1319 scan_end = window[scan + best_len];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1320 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1321 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1322 while ((cur_match = (prev[cur_match & wmask] & 0xffff)) > limit
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1323 && --chain_length != 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1324
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1325 if (best_len <= lookahead) return best_len;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1326
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1327 return lookahead;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1328 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1329
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1330 int deflateInit(ZStream strm, int level, int bits) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1331 return deflateInit2(strm, level, Z_DEFLATED, bits, DEF_MEM_LEVEL,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1332 Z_DEFAULT_STRATEGY);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1333 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1334 int deflateInit(ZStream strm, int level) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1335 return deflateInit(strm, level, MAX_WBITS);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1336 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1337 int deflateInit2(ZStream strm, int level, int method, int windowBits,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1338 int memLevel, int strategy) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1339 int noheader = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1340 // byte[] my_version=ZLIB_VERSION;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1341 //
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1342 // if (version == null || version[0] != my_version[0]
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1343 // || stream_size != sizeof(z_stream)) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1344 // return Z_VERSION_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1345 // }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1346 strm.msg = null;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1347
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1348 if (level == Z_DEFAULT_COMPRESSION) level = 6;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1349
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1350 if (windowBits < 0) { // undocumented feature: suppress zlib header
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1351 noheader = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1352 windowBits = -windowBits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1353 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1354
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1355 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1356 method != Z_DEFLATED ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1357 windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1358 strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1359 return Z_STREAM_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1360 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1361
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1362 strm.dstate = (Deflate)this;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1363 this.noheader = noheader;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1364 w_bits = windowBits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1365 w_size = 1 << w_bits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1366 w_mask = w_size - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1367 hash_bits = memLevel + 7;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1368 hash_size = 1 << hash_bits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1369 hash_mask = hash_size - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1370 hash_shift = ((hash_bits + MIN_MATCH - 1) / MIN_MATCH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1371 window = new byte[w_size * 2];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1372 prev = new short[w_size];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1373 head = new short[hash_size];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1374 lit_bufsize = 1 << (memLevel + 6); // 16K elements by default
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1375 // We overlay pending_buf and d_buf+l_buf. This works since the average
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1376 // output size for (length,distance) codes is <= 24 bits.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1377 pending_buf = new byte[lit_bufsize * 4];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1378 pending_buf_size = lit_bufsize * 4;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1379 d_buf = lit_bufsize / 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1380 l_buf = (1 + 2) * lit_bufsize;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1381 this.level = level;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1382 //System.out.println("level="+level);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1383 this.strategy = strategy;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1384 this.method = (byte)method;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1385 return deflateReset(strm);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1386 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1387
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1388 int deflateReset(ZStream strm) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1389 strm.total_in = strm.total_out = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1390 strm.msg = null; //
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1391 strm.data_type = Z_UNKNOWN;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1392 pending = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1393 pending_out = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1394
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1395 if (noheader < 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1396 noheader = 0; // was set to -1 by deflate(..., Z_FINISH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1397 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1398
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1399 status = (noheader != 0) ? BUSY_STATE : INIT_STATE;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1400 strm.adler = strm._adler.adler32(0, null, 0, 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1401 last_flush = Z_NO_FLUSH;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1402 tr_init();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1403 lm_init();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1404 return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1405 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1406
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1407 int deflateEnd() {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1408 if (status != INIT_STATE && status != BUSY_STATE && status != FINISH_STATE) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1409 return Z_STREAM_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1410 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1411
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1412 // Deallocate in reverse order of allocations:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1413 pending_buf = null;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1414 head = null;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1415 prev = null;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1416 window = null;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1417 // free
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1418 // dstate=null;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1419 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1420 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1421
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1422 int deflateParams(ZStream strm, int _level, int _strategy) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1423 int err = Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1424
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1425 if (_level == Z_DEFAULT_COMPRESSION) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1426 _level = 6;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1427 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1428
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1429 if (_level < 0 || _level > 9 ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1430 _strategy < 0 || _strategy > Z_HUFFMAN_ONLY) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1431 return Z_STREAM_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1432 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1433
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1434 if (config_table[level].func != config_table[_level].func &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1435 strm.total_in != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1436 // Flush the last buffer:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1437 err = strm.deflate(Z_PARTIAL_FLUSH);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1438 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1439
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1440 if (level != _level) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1441 level = _level;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1442 max_lazy_match = config_table[level].max_lazy;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1443 good_match = config_table[level].good_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1444 nice_match = config_table[level].nice_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1445 max_chain_length = config_table[level].max_chain;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1446 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1447
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1448 strategy = _strategy;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1449 return err;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1450 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1451
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1452 int deflateSetDictionary(ZStream strm, byte[] dictionary, int dictLength) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1453 int length = dictLength;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1454 int index = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1455
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1456 if (dictionary == null || status != INIT_STATE)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1457 return Z_STREAM_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1458
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1459 strm.adler = strm._adler.adler32(strm.adler, dictionary, 0, dictLength);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1460
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1461 if (length < MIN_MATCH) return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1462
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1463 if (length > w_size - MIN_LOOKAHEAD) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1464 length = w_size - MIN_LOOKAHEAD;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1465 index = dictLength - length; // use the tail of the dictionary
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1466 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1467
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1468 System.arraycopy(dictionary, index, window, 0, length);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1469 strstart = length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1470 block_start = length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1471 // Insert all strings in the hash table (except for the last two bytes).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1472 // s->lookahead stays null, so s->ins_h will be recomputed at the next
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1473 // call of fill_window.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1474 ins_h = window[0] & 0xff;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1475 ins_h = (((ins_h) << hash_shift) ^ (window[1] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1476
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1477 for (int n = 0; n <= length - MIN_MATCH; n++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1478 ins_h = (((ins_h) << hash_shift) ^ (window[(n) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1479 prev[n & w_mask] = head[ins_h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1480 head[ins_h] = (short)n;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1481 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1482
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1483 return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1484 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1485
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1486 int deflate(ZStream strm, int flush) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1487 int old_flush;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1488
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1489 if (flush > Z_FINISH || flush < 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1490 return Z_STREAM_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1491 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1492
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1493 if (strm.next_out == null ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1494 (strm.next_in == null && strm.avail_in != 0) ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1495 (status == FINISH_STATE && flush != Z_FINISH)) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1496 strm.msg = z_errmsg[Z_NEED_DICT - (Z_STREAM_ERROR)];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1497 return Z_STREAM_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1498 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1499
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1500 if (strm.avail_out == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1501 strm.msg = z_errmsg[Z_NEED_DICT - (Z_BUF_ERROR)];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1502 return Z_BUF_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1503 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1504
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1505 this.strm = strm; // just in case
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1506 old_flush = last_flush;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1507 last_flush = flush;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1508
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1509 // Write the zlib header
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1510 if (status == INIT_STATE) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1511 int header = (Z_DEFLATED + ((w_bits - 8) << 4)) << 8;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1512 int level_flags = ((level - 1) & 0xff) >> 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1513
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1514 if (level_flags > 3) level_flags = 3;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1515
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1516 header |= (level_flags << 6);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1517
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1518 if (strstart != 0) header |= PRESET_DICT;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1519
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1520 header += 31 - (header % 31);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1521 status = BUSY_STATE;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1522 putShortMSB(header);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1523
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1524 // Save the adler32 of the preset dictionary:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1525 if (strstart != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1526 putShortMSB((int)(strm.adler >>> 16));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1527 putShortMSB((int)(strm.adler & 0xffff));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1528 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1529
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1530 strm.adler = strm._adler.adler32(0, null, 0, 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1531 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1532
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1533 // Flush as much pending output as possible
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1534 if (pending != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1535 strm.flush_pending();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1536
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1537 if (strm.avail_out == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1538 //System.out.println(" avail_out==0");
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1539 // Since avail_out is 0, deflate will be called again with
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1540 // more output space, but possibly with both pending and
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1541 // avail_in equal to zero. There won't be anything to do,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1542 // but this is not an error situation so make sure we
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1543 // return OK instead of BUF_ERROR at next call of deflate:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1544 last_flush = -1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1545 return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1546 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1547
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1548 // Make sure there is something to do and avoid duplicate consecutive
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1549 // flushes. For repeated and useless calls with Z_FINISH, we keep
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1550 // returning Z_STREAM_END instead of Z_BUFF_ERROR.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1551 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1552 else if (strm.avail_in == 0 && flush <= old_flush &&
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1553 flush != Z_FINISH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1554 strm.msg = z_errmsg[Z_NEED_DICT - (Z_BUF_ERROR)];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1555 return Z_BUF_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1556 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1557
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1558 // User must not provide more input after the first FINISH:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1559 if (status == FINISH_STATE && strm.avail_in != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1560 strm.msg = z_errmsg[Z_NEED_DICT - (Z_BUF_ERROR)];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1561 return Z_BUF_ERROR;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1562 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1563
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1564 // Start a new block or continue the current one.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1565 if (strm.avail_in != 0 || lookahead != 0 ||
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1566 (flush != Z_NO_FLUSH && status != FINISH_STATE)) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1567 int bstate = -1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1568
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1569 switch (config_table[level].func) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1570 case STORED:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1571 bstate = deflate_stored(flush);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1572 break;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1573
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1574 case FAST:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1575 bstate = deflate_fast(flush);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1576 break;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1577
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1578 case SLOW:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1579 bstate = deflate_slow(flush);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1580 break;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1581
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1582 default:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1583 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1584
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1585 if (bstate == FinishStarted || bstate == FinishDone) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1586 status = FINISH_STATE;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1587 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1588
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1589 if (bstate == NeedMore || bstate == FinishStarted) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1590 if (strm.avail_out == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1591 last_flush = -1; // avoid BUF_ERROR next call, see above
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1592 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1593
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1594 return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1595 // If flush != Z_NO_FLUSH && avail_out == 0, the next call
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1596 // of deflate should use the same flush parameter to make sure
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1597 // that the flush is complete. So we don't have to output an
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1598 // empty block here, this will be done at next call. This also
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1599 // ensures that for a very small output buffer, we emit at most
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1600 // one empty block.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1601 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1602
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1603 if (bstate == BlockDone) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1604 if (flush == Z_PARTIAL_FLUSH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1605 _tr_align();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1606 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1607 else { // FULL_FLUSH or SYNC_FLUSH
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1608 _tr_stored_block(0, 0, false);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1609
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1610 // For a full flush, this empty block will be recognized
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1611 // as a special marker by inflate_sync().
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1612 if (flush == Z_FULL_FLUSH) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1613 //state.head[s.hash_size-1]=0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1614 for (int i = 0; i < hash_size/*-1*/; i++) // forget history
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1615 head[i] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1616 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1617 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1618
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1619 strm.flush_pending();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1620
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1621 if (strm.avail_out == 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1622 last_flush = -1; // avoid BUF_ERROR at next call, see above
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1623 return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1624 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1625 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1626 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1627
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1628 if (flush != Z_FINISH) return Z_OK;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1629
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1630 if (noheader != 0) return Z_STREAM_END;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1631
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1632 // Write the zlib trailer (adler32)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1633 putShortMSB((int)(strm.adler >>> 16));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1634 putShortMSB((int)(strm.adler & 0xffff));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1635 strm.flush_pending();
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1636 // If avail_out is zero, the application will call deflate again
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1637 // to flush the rest.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1638 noheader = -1; // write the trailer only once!
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1639 return pending != 0 ? Z_OK : Z_STREAM_END;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1640 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1641 }