View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
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 compliance
6    * with the 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  package io.netty.handler.codec.compression;
17  
18  /**
19   * An in-place, length restricted Canonical Huffman code length allocator.<br>
20   * Based on the algorithm proposed by R. L. Milidi'u, A. A. Pessoa and E. S. Laber in
21   * <a href="http://www-di.inf.puc-rio.br/~laber/public/spire98.ps">In-place Length-Restricted Prefix Coding</a>
22   * and incorporating additional ideas from the implementation of
23   * <a href="http://entropyware.info/shcodec/index.html">shcodec</a> by Simakov Alexander.
24   */
25  final class Bzip2HuffmanAllocator {
26      /**
27       * @param array The code length array
28       * @param i The input position
29       * @param nodesToMove The number of internal nodes to be relocated
30       * @return The smallest {@code k} such that {@code nodesToMove <= k <= i} and
31       *         {@code i <= (array[k] % array.length)}
32       */
33      private static int first(final int[] array, int i, final int nodesToMove) {
34          final int length = array.length;
35          final int limit = i;
36          int k = array.length - 2;
37  
38          while (i >= nodesToMove && array[i] % length > limit) {
39              k = i;
40              i -= limit - i + 1;
41          }
42          i = Math.max(nodesToMove - 1, i);
43  
44          while (k > i + 1) {
45              int temp = i + k >>> 1;
46              if (array[temp] % length > limit) {
47                  k = temp;
48              } else {
49                  i = temp;
50              }
51          }
52          return k;
53      }
54  
55      /**
56       * Fills the code array with extended parent pointers.
57       * @param array The code length array
58       */
59      private static void setExtendedParentPointers(final int[] array) {
60          final int length = array.length;
61          array[0] += array[1];
62  
63          for (int headNode = 0, tailNode = 1, topNode = 2; tailNode < length - 1; tailNode++) {
64              int temp;
65              if (topNode >= length || array[headNode] < array[topNode]) {
66                  temp = array[headNode];
67                  array[headNode++] = tailNode;
68              } else {
69                  temp = array[topNode++];
70              }
71  
72              if (topNode >= length || (headNode < tailNode && array[headNode] < array[topNode])) {
73                  temp += array[headNode];
74                  array[headNode++] = tailNode + length;
75              } else {
76                  temp += array[topNode++];
77              }
78              array[tailNode] = temp;
79          }
80      }
81  
82      /**
83       * Finds the number of nodes to relocate in order to achieve a given code length limit.
84       * @param array The code length array
85       * @param maximumLength The maximum bit length for the generated codes
86       * @return The number of nodes to relocate
87       */
88      private static int findNodesToRelocate(final int[] array, final int maximumLength) {
89          int currentNode = array.length - 2;
90          for (int currentDepth = 1; currentDepth < maximumLength - 1 && currentNode > 1; currentDepth++) {
91              currentNode =  first(array, currentNode - 1, 0);
92          }
93          return currentNode;
94      }
95  
96      /**
97       * A final allocation pass with no code length limit.
98       * @param array The code length array
99       */
100     private static void allocateNodeLengths(final int[] array) {
101         int firstNode = array.length - 2;
102         int nextNode = array.length - 1;
103 
104         for (int currentDepth = 1, availableNodes = 2; availableNodes > 0; currentDepth++) {
105             final int lastNode = firstNode;
106             firstNode = first(array, lastNode - 1, 0);
107 
108             for (int i = availableNodes - (lastNode - firstNode); i > 0; i--) {
109                 array[nextNode--] = currentDepth;
110             }
111 
112             availableNodes = (lastNode - firstNode) << 1;
113         }
114     }
115 
116     /**
117      * A final allocation pass that relocates nodes in order to achieve a maximum code length limit.
118      * @param array The code length array
119      * @param nodesToMove The number of internal nodes to be relocated
120      * @param insertDepth The depth at which to insert relocated nodes
121      */
122     private static void allocateNodeLengthsWithRelocation(final int[] array,
123                                                            final int nodesToMove, final int insertDepth) {
124         int firstNode = array.length - 2;
125         int nextNode = array.length - 1;
126         int currentDepth = insertDepth == 1 ? 2 : 1;
127         int nodesLeftToMove = insertDepth == 1 ? nodesToMove - 2 : nodesToMove;
128 
129         for (int availableNodes = currentDepth << 1; availableNodes > 0; currentDepth++) {
130             final int lastNode = firstNode;
131             firstNode = firstNode <= nodesToMove ? firstNode : first(array, lastNode - 1, nodesToMove);
132 
133             int offset = 0;
134             if (currentDepth >= insertDepth) {
135                 offset = Math.min(nodesLeftToMove, 1 << (currentDepth - insertDepth));
136             } else if (currentDepth == insertDepth - 1) {
137                 offset = 1;
138                 if (array[firstNode] == lastNode) {
139                     firstNode++;
140                 }
141             }
142 
143             for (int i = availableNodes - (lastNode - firstNode + offset); i > 0; i--) {
144                 array[nextNode--] = currentDepth;
145             }
146 
147             nodesLeftToMove -= offset;
148             availableNodes = (lastNode - firstNode + offset) << 1;
149         }
150     }
151 
152     /**
153      * Allocates Canonical Huffman code lengths in place based on a sorted frequency array.
154      * @param array On input, a sorted array of symbol frequencies; On output, an array of Canonical
155      *              Huffman code lengths
156      * @param maximumLength The maximum code length. Must be at least {@code ceil(log2(array.length))}
157      */
158     static void allocateHuffmanCodeLengths(final int[] array, final int maximumLength) {
159         switch (array.length) {
160             case 2:
161                 array[1] = 1;
162                 // fall through
163             case 1:
164                 array[0] = 1;
165                 return;
166         }
167 
168         /* Pass 1 : Set extended parent pointers */
169         setExtendedParentPointers(array);
170 
171         /* Pass 2 : Find number of nodes to relocate in order to achieve maximum code length */
172         int nodesToRelocate = findNodesToRelocate(array, maximumLength);
173 
174         /* Pass 3 : Generate code lengths */
175         if (array[0] % array.length >= nodesToRelocate) {
176             allocateNodeLengths(array);
177         } else {
178             int insertDepth = maximumLength - (32 - Integer.numberOfLeadingZeros(nodesToRelocate - 1));
179             allocateNodeLengthsWithRelocation(array, nodesToRelocate, insertDepth);
180         }
181     }
182 
183     private Bzip2HuffmanAllocator() { }
184 }