1/*2* Copyright 2009 Red Hat, Inc.3*4* Red Hat licenses this file to you under the Apache License, version 2.05* (the "License"); you may not use this file except in compliance with the6* 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(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)46* and contributors of zlib.47*/48 49packageorg.jboss.netty.util.internal.jzlib; 50 51finalclassTree { 52// extra bits for each length code53staticfinalint[] extra_lbits = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 54 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 }; 55 56// extra bits for each distance code57staticfinalint[] extra_dbits = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 58 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 }; 59 60// extra bits for each bit length code61staticfinalint[] extra_blbits = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62 0, 0, 0, 2, 3, 7 }; 63 64staticfinalbyte[] bl_order = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 65 12, 3, 13, 2, 14, 1, 15 }; 66 67staticfinalbyte[] _dist_code = { 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 68 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 69 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 70 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 71 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 72 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 73 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 74 13, 13, 13, 13, 13, 13, 13, 13, 13, 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, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 78 14, 14, 14, 14, 14, 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, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 82 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 83 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 84 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 85 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 86 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 87 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 88 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 89 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 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, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 93 28, 28, 28, 28, 28, 28, 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, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 97 29, 29 }; 98 99staticfinalbyte[] _length_code = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 100 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 101 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 102 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 103 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 104 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 105 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 106 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 107 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 108 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 109 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 110 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 111 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 112 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 113 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 114 27, 27, 27, 27, 27, 28 }; 115 116staticfinalint[] base_length = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 117 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 118 224, 0 }; 119 120staticfinalint[] base_dist = { 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 121 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 122 6144, 8192, 12288, 16384, 24576 }; 123 124// Mapping from a distance to a distance code. dist is the distance - 1 and125// must not have side effects. _dist_code[256] and _dist_code[257] are never126// used.127staticintd_code(intdist) { 128returndist < 256? _dist_code[dist] : _dist_code[256 + (dist >>> 7)]; 129 } 130 131short[] dyn_tree;// the dynamic tree132intmax_code;// largest code with non zero frequency133 StaticTree stat_desc;// the corresponding static tree134 135// Compute the optimal bit lengths for a tree and update the total bit length136// for the current block.137// IN assertion: the fields freq and dad are set, heap[heap_max] and138// above are the tree nodes sorted by increasing frequency.139// OUT assertions: the field len is set to the optimal bit length, the140// array bl_count contains the frequencies for each bit length.141// The length opt_len is updated; static_len is also updated if stree is142// not null.143privatevoidgen_bitlen(Deflate s) { 144short[] tree = dyn_tree; 145short[] stree = stat_desc.static_tree; 146int[] extra = stat_desc.extra_bits; 147intbase = stat_desc.extra_base; 148intmax_length = stat_desc.max_length; 149inth;// heap index150intn, m;// iterate over the tree elements151intbits;// bit length152intxbits;// extra bits153shortf;// frequency154intoverflow = 0;// number of elements with bit length too large155 156for(bits = 0; bits <= JZlib.MAX_BITS; bits ++) { 157 s.bl_count[bits] = 0; 158 } 159 160// In a first pass, compute the optimal bit lengths (which may161// overflow in the case of the bit length tree).162 tree[s.heap[s.heap_max] * 2 + 1] = 0;// root of the heap163 164for(h = s.heap_max + 1; h < JZlib.HEAP_SIZE; h ++) { 165 n = s.heap[h]; 166 bits = tree[tree[n * 2 + 1] * 2 + 1] + 1; 167if(bits > max_length) { 168 bits = max_length; 169 overflow ++; 170 } 171 tree[n * 2 + 1] = (short) bits; 172// We overwrite tree[n*2+1] which is no longer needed173 174if(n > max_code) { 175continue;// not a leaf node176 } 177 178 s.bl_count[bits] ++; 179 xbits = 0; 180if(n >= base) { 181 xbits = extra[n - base]; 182 } 183 f = tree[n * 2]; 184 s.opt_len += f * (bits + xbits); 185if(stree !=null) { 186 s.static_len += f * (stree[n * 2 + 1] + xbits); 187 } 188 } 189if(overflow == 0) { 190return; 191 } 192 193// This happens for example on obj2 and pic of the Calgary corpus194// Find the first bit length which could increase:195do{ 196 bits = max_length - 1; 197while(s.bl_count[bits] == 0) { 198 bits --; 199 } 200 s.bl_count[bits] --;// move one leaf down the tree201 s.bl_count[bits + 1] += 2;// move one overflow item as its brother202 s.bl_count[max_length] --; 203// The brother of the overflow item also moves one step up,204// but this does not affect bl_count[max_length]205 overflow -= 2; 206 }while(overflow > 0); 207 208for(bits = max_length; bits != 0; bits --) { 209 n = s.bl_count[bits]; 210while(n != 0) { 211 m = s.heap[-- h]; 212if(m > max_code) { 213continue; 214 } 215if(tree[m * 2 + 1] != bits) { 216 s.opt_len += ((long) bits - (long) tree[m * 2 + 1]) * 217 tree[m * 2]; 218 tree[m * 2 + 1] = (short) bits; 219 } 220 n --; 221 } 222 } 223 } 224 225// Construct one Huffman tree and assigns the code bit strings and lengths.226// Update the total bit length for the current block.227// IN assertion: the field freq is set for all tree elements.228// OUT assertions: the fields len and code are set to the optimal bit length229// and corresponding code. The length opt_len is updated; static_len is230// also updated if stree is not null. The field max_code is set.231voidbuild_tree(Deflate s) { 232short[] tree = dyn_tree; 233short[] stree = stat_desc.static_tree; 234intelems = stat_desc.elems; 235intn, m;// iterate over heap elements236intmax_code = -1;// largest code with non zero frequency237intnode;// new node being created238 239// Construct the initial heap, with least frequent element in240// heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].241// heap[0] is not used.242 s.heap_len = 0; 243 s.heap_max = JZlib.HEAP_SIZE; 244 245for(n = 0; n < elems; n ++) { 246if(tree[n * 2] != 0) { 247 s.heap[++ s.heap_len] = max_code = n; 248 s.depth[n] = 0; 249 }else{ 250 tree[n * 2 + 1] = 0; 251 } 252 } 253 254// The pkzip format requires that at least one distance code exists,255// and that at least one bit should be sent even if there is only one256// possible code. So to avoid special checks later on we force at least257// two codes of non zero frequency.258while(s.heap_len < 2) { 259 node = s.heap[++ s.heap_len] = max_code < 2? ++ max_code : 0; 260 tree[node * 2] = 1; 261 s.depth[node] = 0; 262 s.opt_len --; 263if(stree !=null) { 264 s.static_len -= stree[node * 2 + 1]; 265// node is 0 or 1 so it does not have extra bits266 } 267 } 268this.max_code = max_code; 269 270// The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,271// establish sub-heaps of increasing lengths:272 273for(n = s.heap_len / 2; n >= 1; n --) { 274 s.pqdownheap(tree, n); 275 } 276 277// Construct the Huffman tree by repeatedly combining the least two278// frequent nodes.279 280 node = elems;// next internal node of the tree281do{ 282// n = node of least frequency283 n = s.heap[1]; 284 s.heap[1] = s.heap[s.heap_len --]; 285 s.pqdownheap(tree, 1); 286 m = s.heap[1];// m = node of next least frequency287 288 s.heap[-- s.heap_max] = n;// keep the nodes sorted by frequency289 s.heap[-- s.heap_max] = m; 290 291// Create a new node father of n and m292 tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]); 293 s.depth[node] = (byte) (Math.max(s.depth[n], s.depth[m]) + 1); 294 tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node; 295 296// and insert the new node in the heap297 s.heap[1] = node ++; 298 s.pqdownheap(tree, 1); 299 }while(s.heap_len >= 2); 300 301 s.heap[-- s.heap_max] = s.heap[1]; 302 303// At this point, the fields freq and dad are set. We can now304// generate the bit lengths.305 306 gen_bitlen(s); 307 308// The field len is now set, we can generate the bit codes309 gen_codes(tree, max_code, s.bl_count); 310 } 311 312// Generate the codes for a given tree and bit counts (which need not be313// optimal).314// IN assertion: the array bl_count contains the bit length statistics for315// the given tree and the field len is set for all tree elements.316// OUT assertion: the field code is set for all tree elements of non317// zero code length.318privatestaticvoidgen_codes(short[] tree,// the tree to decorate319intmax_code,// largest code with non zero frequency320short[] bl_count// number of codes at each bit length321 ) { 322short[] next_code =newshort[JZlib.MAX_BITS + 1];// next code value for each bit length323shortcode = 0;// running code value324intbits;// bit index325intn;// code index326 327// The distribution counts are first used to generate the code values328// without bit reversal.329for(bits = 1; bits <= JZlib.MAX_BITS; bits ++) { 330 next_code[bits] = code = (short) (code + bl_count[bits - 1] << 1); 331 } 332 333// Check that the bit counts in bl_count are consistent. The last code334// must be all ones.335//Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,336// "inconsistent bit counts");337//Tracev((stderr,"\ngen_codes: max_code %d ", max_code));338 339for(n = 0; n <= max_code; n ++) { 340intlen = tree[n * 2 + 1]; 341if(len == 0) { 342continue; 343 } 344// Now reverse the bits345 tree[n * 2] = (short) bi_reverse(next_code[len] ++, len); 346 } 347 } 348 349// Reverse the first len bits of a code, using straightforward code (a faster350// method would use a table)351// IN assertion: 1 <= len <= 15352privatestaticintbi_reverse(intcode,// the value to invert353intlen// its bit length354 ) { 355intres = 0; 356do{ 357 res |= code & 1; 358 code >>>= 1; 359 res <<= 1; 360 }while(-- len > 0); 361returnres >>> 1; 362 } 363 }