View Javadoc

    1   /*
    2    * Copyright 2009 Red Hat, Inc.
    3    *
    4    * Red Hat licenses this file to you under the Apache License, version 2.0
    5    * (the "License"); you may not use this file except in compliance with the
    6    * License.  You may obtain a copy of the License at:
    7    *
    8    *    http://www.apache.org/licenses/LICENSE-2.0
    9    *
    10   * Unless required by applicable law or agreed to in writing, software
    11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
    12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  See the
    13   * License for the specific language governing permissions and limitations
    14   * under the License.
    15   */
    16  /*
    17  Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
    18
    19  Redistribution and use in source and binary forms, with or without
    20  modification, are permitted provided that the following conditions are met:
    21
    22    1. Redistributions of source code must retain the above copyright notice,
    23       this list of conditions and the following disclaimer.
    24
    25    2. Redistributions in binary form must reproduce the above copyright
    26       notice, this list of conditions and the following disclaimer in
    27       the documentation and/or other materials provided with the distribution.
    28
    29    3. The names of the authors may not be used to endorse or promote products
    30       derived from this software without specific prior written permission.
    31
    32  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
    33  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
    34  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
    35  INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
    36  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    37  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
    38  OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    39  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    40  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
    41  EVEN 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 authors
    45   * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
    46   * and contributors of zlib.
    47   */
    48
    49  package org.jboss.netty.util.internal.jzlib;
    50
    51  final class Tree {
    52      // extra bits for each length code
    53      static final int[] 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 code
    57      static final int[] 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 code
    61      static final int[] extra_blbits = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    62              0, 0, 0, 2, 3, 7 };
    63
    64      static final byte[] bl_order = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4,
    65              12, 3, 13, 2, 14, 1, 15 };
    66
    67      static final byte[] _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
    99      static final byte[] _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
    116     static final int[] 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
    120     static final int[] 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 and
    125     // must not have side effects. _dist_code[256] and _dist_code[257] are never
    126     // used.
    127     static int d_code(int dist) {
    128         return dist < 256? _dist_code[dist] : _dist_code[256 + (dist >>> 7)];
    129     }
    130
    131     short[] dyn_tree; // the dynamic tree
    132     int max_code; // largest code with non zero frequency
    133     StaticTree stat_desc; // the corresponding static tree
    134
    135     // Compute the optimal bit lengths for a tree and update the total bit length
    136     // for the current block.
    137     // IN assertion: the fields freq and dad are set, heap[heap_max] and
    138     //    above are the tree nodes sorted by increasing frequency.
    139     // OUT assertions: the field len is set to the optimal bit length, the
    140     //     array bl_count contains the frequencies for each bit length.
    141     //     The length opt_len is updated; static_len is also updated if stree is
    142     //     not null.
    143     private void gen_bitlen(Deflate s) {
    144         short[] tree = dyn_tree;
    145         short[] stree = stat_desc.static_tree;
    146         int[] extra = stat_desc.extra_bits;
    147         int base = stat_desc.extra_base;
    148         int max_length = stat_desc.max_length;
    149         int h; // heap index
    150         int n, m; // iterate over the tree elements
    151         int bits; // bit length
    152         int xbits; // extra bits
    153         short f; // frequency
    154         int overflow = 0; // number of elements with bit length too large
    155
    156         for (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 may
    161         // overflow in the case of the bit length tree).
    162         tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap
    163
    164         for (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;
    167             if (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 needed
    173
    174             if (n > max_code) {
    175                 continue; // not a leaf node
    176             }
    177
    178             s.bl_count[bits] ++;
    179             xbits = 0;
    180             if (n >= base) {
    181                 xbits = extra[n - base];
    182             }
    183             f = tree[n * 2];
    184             s.opt_len += f * (bits + xbits);
    185             if (stree != null) {
    186                 s.static_len += f * (stree[n * 2 + 1] + xbits);
    187             }
    188         }
    189         if (overflow == 0) {
    190             return;
    191         }
    192
    193         // This happens for example on obj2 and pic of the Calgary corpus
    194         // Find the first bit length which could increase:
    195         do {
    196             bits = max_length - 1;
    197             while (s.bl_count[bits] == 0) {
    198                 bits --;
    199             }
    200             s.bl_count[bits] --; // move one leaf down the tree
    201             s.bl_count[bits + 1] += 2; // move one overflow item as its brother
    202             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
    208         for (bits = max_length; bits != 0; bits --) {
    209             n = s.bl_count[bits];
    210             while (n != 0) {
    211                 m = s.heap[-- h];
    212                 if (m > max_code) {
    213                     continue;
    214                 }
    215                 if (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 length
    229     //     and corresponding code. The length opt_len is updated; static_len is
    230     //     also updated if stree is not null. The field max_code is set.
    231     void build_tree(Deflate s) {
    232         short[] tree = dyn_tree;
    233         short[] stree = stat_desc.static_tree;
    234         int elems = stat_desc.elems;
    235         int n, m; // iterate over heap elements
    236         int max_code = -1; // largest code with non zero frequency
    237         int node; // new node being created
    238
    239         // Construct the initial heap, with least frequent element in
    240         // 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
    245         for (n = 0; n < elems; n ++) {
    246             if (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 one
    256         // possible code. So to avoid special checks later on we force at least
    257         // two codes of non zero frequency.
    258         while (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 --;
    263             if (stree != null) {
    264                 s.static_len -= stree[node * 2 + 1];
    265                 // node is 0 or 1 so it does not have extra bits
    266             }
    267         }
    268         this.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
    273         for (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 two
    278         // frequent nodes.
    279
    280         node = elems; // next internal node of the tree
    281         do {
    282             // n = node of least frequency
    283             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 frequency
    287
    288             s.heap[-- s.heap_max] = n; // keep the nodes sorted by frequency
    289             s.heap[-- s.heap_max] = m;
    290
    291             // Create a new node father of n and m
    292             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 heap
    297             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 now
    304         // generate the bit lengths.
    305
    306         gen_bitlen(s);
    307
    308         // The field len is now set, we can generate the bit codes
    309         gen_codes(tree, max_code, s.bl_count);
    310     }
    311
    312     // Generate the codes for a given tree and bit counts (which need not be
    313     // optimal).
    314     // IN assertion: the array bl_count contains the bit length statistics for
    315     // 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 non
    317     //     zero code length.
    318     private static void gen_codes(short[] tree, // the tree to decorate
    319             int max_code, // largest code with non zero frequency
    320             short[] bl_count // number of codes at each bit length
    321     ) {
    322         short[] next_code = new short[JZlib.MAX_BITS + 1]; // next code value for each bit length
    323         short code = 0; // running code value
    324         int bits; // bit index
    325         int n; // code index
    326
    327         // The distribution counts are first used to generate the code values
    328         // without bit reversal.
    329         for (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 code
    334         // 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
    339         for (n = 0; n <= max_code; n ++) {
    340             int len = tree[n * 2 + 1];
    341             if (len == 0) {
    342                 continue;
    343             }
    344             // Now reverse the bits
    345             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 faster
    350     // method would use a table)
    351     // IN assertion: 1 <= len <= 15
    352     private static int bi_reverse(int code, // the value to invert
    353             int len // its bit length
    354     ) {
    355         int res = 0;
    356         do {
    357             res |= code & 1;
    358             code >>>= 1;
    359             res <<= 1;
    360         } while (-- len > 0);
    361         return res >>> 1;
    362     }
    363 }