1/*2* Copyright 2012 The Netty Project3*4* The Netty Project licenses this file to you under the Apache License,5* version 2.0 (the "License"); you may not use this file except in compliance6* with the License. You may obtain a copy of the License at:7*8* http://www.apache.org/licenses/LICENSE-2.09*10* Unless required by applicable law or agreed to in writing, software11* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT12* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the13* License for the specific language governing permissions and limitations14* under the License.15*/16/*17Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.18 19Redistribution and use in source and binary forms, with or without20modification, are permitted provided that the following conditions are met:21 221. Redistributions of source code must retain the above copyright notice,23this list of conditions and the following disclaimer.24 252. Redistributions in binary form must reproduce the above copyright26notice, this list of conditions and the following disclaimer in27the documentation and/or other materials provided with the distribution.28 293. The names of the authors may not be used to endorse or promote products30derived from this software without specific prior written permission.31 32THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,33INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND34FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,35INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,36INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT37LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,38OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF39LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING40NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,41EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.42*/43/*44* This program is based on zlib-1.1.3, so all credit should go authors45* Jean-loup Gailly([email protected]) and Mark Adler([email protected])46* and contributors of zlib.47*/48packageorg.jboss.netty.util.internal.jzlib; 49 50finalclassTree { 51// extra bits for each length code52staticfinalint[] extra_lbits = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 53 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 }; 54 55// extra bits for each distance code56staticfinalint[] extra_dbits = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 57 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 }; 58 59// extra bits for each bit length code60staticfinalint[] extra_blbits = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 61 0, 0, 0, 2, 3, 7 }; 62 63staticfinalbyte[] bl_order = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 64 12, 3, 13, 2, 14, 1, 15 }; 65 66staticfinalbyte[] _dist_code = { 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 67 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 68 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 69 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 70 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 71 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 72 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 73 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 74 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 75 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 76 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 77 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 78 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 79 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 80 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 81 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 82 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 83 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 84 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 85 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 86 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 87 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 88 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 89 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 90 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 91 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 92 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 93 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 94 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 95 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 96 29, 29 }; 97 98staticfinalbyte[] _length_code = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 99 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 100 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 101 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 102 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 103 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 104 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 105 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 106 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 107 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 108 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 109 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 110 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 111 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 112 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 113 27, 27, 27, 27, 27, 28 }; 114 115staticfinalint[] base_length = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 116 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 117 224, 0 }; 118 119staticfinalint[] base_dist = { 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 120 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 121 6144, 8192, 12288, 16384, 24576 }; 122 123// Mapping from a distance to a distance code. dist is the distance - 1 and124// must not have side effects. _dist_code[256] and _dist_code[257] are never125// used.126staticintd_code(intdist) { 127returndist < 256? _dist_code[dist] : _dist_code[256 + (dist >>> 7)]; 128 } 129 130short[] dyn_tree;// the dynamic tree131intmax_code;// largest code with non zero frequency132 StaticTree stat_desc;// the corresponding static tree133 134// Compute the optimal bit lengths for a tree and update the total bit length135// for the current block.136// IN assertion: the fields freq and dad are set, heap[heap_max] and137// above are the tree nodes sorted by increasing frequency.138// OUT assertions: the field len is set to the optimal bit length, the139// array bl_count contains the frequencies for each bit length.140// The length opt_len is updated; static_len is also updated if stree is141// not null.142privatevoidgen_bitlen(Deflate s) { 143short[] tree = dyn_tree; 144short[] stree = stat_desc.static_tree; 145int[] extra = stat_desc.extra_bits; 146intbase = stat_desc.extra_base; 147intmax_length = stat_desc.max_length; 148inth;// heap index149intn, m;// iterate over the tree elements150intbits;// bit length151intxbits;// extra bits152shortf;// frequency153intoverflow = 0;// number of elements with bit length too large154 155for(bits = 0; bits <= JZlib.MAX_BITS; bits ++) { 156 s.bl_count[bits] = 0; 157 } 158 159// In a first pass, compute the optimal bit lengths (which may160// overflow in the case of the bit length tree).161 tree[s.heap[s.heap_max] * 2 + 1] = 0;// root of the heap162 163for(h = s.heap_max + 1; h < JZlib.HEAP_SIZE; h ++) { 164 n = s.heap[h]; 165 bits = tree[tree[n * 2 + 1] * 2 + 1] + 1; 166if(bits > max_length) { 167 bits = max_length; 168 overflow ++; 169 } 170 tree[n * 2 + 1] = (short) bits; 171// We overwrite tree[n*2+1] which is no longer needed172 173if(n > max_code) { 174continue;// not a leaf node175 } 176 177 s.bl_count[bits] ++; 178 xbits = 0; 179if(n >= base) { 180 xbits = extra[n - base]; 181 } 182 f = tree[n * 2]; 183 s.opt_len += f * (bits + xbits); 184if(stree !=null) { 185 s.static_len += f * (stree[n * 2 + 1] + xbits); 186 } 187 } 188if(overflow == 0) { 189return; 190 } 191 192// This happens for example on obj2 and pic of the Calgary corpus193// Find the first bit length which could increase:194do{ 195 bits = max_length - 1; 196while(s.bl_count[bits] == 0) { 197 bits --; 198 } 199 s.bl_count[bits] --;// move one leaf down the tree200 s.bl_count[bits + 1] += 2;// move one overflow item as its brother201 s.bl_count[max_length] --; 202// The brother of the overflow item also moves one step up,203// but this does not affect bl_count[max_length]204 overflow -= 2; 205 }while(overflow > 0); 206 207for(bits = max_length; bits != 0; bits --) { 208 n = s.bl_count[bits]; 209while(n != 0) { 210 m = s.heap[-- h]; 211if(m > max_code) { 212continue; 213 } 214if(tree[m * 2 + 1] != bits) { 215 s.opt_len += ((long) bits - tree[m * 2 + 1]) * 216 tree[m * 2]; 217 tree[m * 2 + 1] = (short) bits; 218 } 219 n --; 220 } 221 } 222 } 223 224// Construct one Huffman tree and assigns the code bit strings and lengths.225// Update the total bit length for the current block.226// IN assertion: the field freq is set for all tree elements.227// OUT assertions: the fields len and code are set to the optimal bit length228// and corresponding code. The length opt_len is updated; static_len is229// also updated if stree is not null. The field max_code is set.230voidbuild_tree(Deflate s) { 231short[] tree = dyn_tree; 232short[] stree = stat_desc.static_tree; 233intelems = stat_desc.elems; 234intn, m;// iterate over heap elements235intmax_code = -1;// largest code with non zero frequency236intnode;// new node being created237 238// Construct the initial heap, with least frequent element in239// heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].240// heap[0] is not used.241 s.heap_len = 0; 242 s.heap_max = JZlib.HEAP_SIZE; 243 244for(n = 0; n < elems; n ++) { 245if(tree[n * 2] != 0) { 246 s.heap[++ s.heap_len] = max_code = n; 247 s.depth[n] = 0; 248 }else{ 249 tree[n * 2 + 1] = 0; 250 } 251 } 252 253// The pkzip format requires that at least one distance code exists,254// and that at least one bit should be sent even if there is only one255// possible code. So to avoid special checks later on we force at least256// two codes of non zero frequency.257while(s.heap_len < 2) { 258 node = s.heap[++ s.heap_len] = max_code < 2? ++ max_code : 0; 259 tree[node * 2] = 1; 260 s.depth[node] = 0; 261 s.opt_len --; 262if(stree !=null) { 263 s.static_len -= stree[node * 2 + 1]; 264// node is 0 or 1 so it does not have extra bits265 } 266 } 267this.max_code = max_code; 268 269// The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,270// establish sub-heaps of increasing lengths:271 272for(n = s.heap_len / 2; n >= 1; n --) { 273 s.pqdownheap(tree, n); 274 } 275 276// Construct the Huffman tree by repeatedly combining the least two277// frequent nodes.278 279 node = elems;// next internal node of the tree280do{ 281// n = node of least frequency282 n = s.heap[1]; 283 s.heap[1] = s.heap[s.heap_len --]; 284 s.pqdownheap(tree, 1); 285 m = s.heap[1];// m = node of next least frequency286 287 s.heap[-- s.heap_max] = n;// keep the nodes sorted by frequency288 s.heap[-- s.heap_max] = m; 289 290// Create a new node father of n and m291 tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]); 292 s.depth[node] = (byte) (Math.max(s.depth[n], s.depth[m]) + 1); 293 tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node; 294 295// and insert the new node in the heap296 s.heap[1] = node ++; 297 s.pqdownheap(tree, 1); 298 }while(s.heap_len >= 2); 299 300 s.heap[-- s.heap_max] = s.heap[1]; 301 302// At this point, the fields freq and dad are set. We can now303// generate the bit lengths.304 305 gen_bitlen(s); 306 307// The field len is now set, we can generate the bit codes308 gen_codes(tree, max_code, s.bl_count); 309 } 310 311// Generate the codes for a given tree and bit counts (which need not be312// optimal).313// IN assertion: the array bl_count contains the bit length statistics for314// the given tree and the field len is set for all tree elements.315// OUT assertion: the field code is set for all tree elements of non316// zero code length.317privatestaticvoidgen_codes(short[] tree,// the tree to decorate318intmax_code,// largest code with non zero frequency319short[] bl_count// number of codes at each bit length320 ) { 321short[] next_code =newshort[JZlib.MAX_BITS + 1];// next code value for each bit length322shortcode = 0;// running code value323intbits;// bit index324intn;// code index325 326// The distribution counts are first used to generate the code values327// without bit reversal.328for(bits = 1; bits <= JZlib.MAX_BITS; bits ++) { 329 next_code[bits] = code = (short) (code + bl_count[bits - 1] << 1); 330 } 331 332// Check that the bit counts in bl_count are consistent. The last code333// must be all ones.334//Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,335// "inconsistent bit counts");336//Tracev((stderr,"\ngen_codes: max_code %d ", max_code));337 338for(n = 0; n <= max_code; n ++) { 339intlen = tree[n * 2 + 1]; 340if(len == 0) { 341continue; 342 } 343// Now reverse the bits344 tree[n * 2] = (short) bi_reverse(next_code[len] ++, len); 345 } 346 } 347 348// Reverse the first len bits of a code, using straightforward code (a faster349// method would use a table)350// IN assertion: 1 <= len <= 15351privatestaticintbi_reverse(intcode,// the value to invert352intlen// its bit length353 ) { 354intres = 0; 355do{ 356 res |= code & 1; 357 code >>>= 1; 358 res <<= 1; 359 }while(-- len > 0); 360returnres >>> 1; 361 } 362 }