1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package io.netty.handler.codec.compression;
17
18
19
20
21
22
23
24
25 final class Bzip2HuffmanAllocator {
26
27
28
29
30
31
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
57
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
84
85
86
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
98
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
118
119
120
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
154
155
156
157
158 static void allocateHuffmanCodeLengths(final int[] array, final int maximumLength) {
159 switch (array.length) {
160 case 2:
161 array[1] = 1;
162
163 case 1:
164 array[0] = 1;
165 return;
166 }
167
168
169 setExtendedParentPointers(array);
170
171
172 int nodesToRelocate = findNodesToRelocate(array, maximumLength);
173
174
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 }