2 ff3adf60 2004-04-14 devnull /*-------------------------------------------------------------*/
3 ff3adf60 2004-04-14 devnull /*--- Huffman coding low-level stuff ---*/
4 ff3adf60 2004-04-14 devnull /*--- huffman.c ---*/
5 ff3adf60 2004-04-14 devnull /*-------------------------------------------------------------*/
8 ff3adf60 2004-04-14 devnull This file is a part of bzip2 and/or libbzip2, a program and
9 ff3adf60 2004-04-14 devnull library for lossless, block-sorting data compression.
11 ff3adf60 2004-04-14 devnull Copyright (C) 1996-2000 Julian R Seward. All rights reserved.
13 ff3adf60 2004-04-14 devnull Redistribution and use in source and binary forms, with or without
14 ff3adf60 2004-04-14 devnull modification, are permitted provided that the following conditions
17 ff3adf60 2004-04-14 devnull 1. Redistributions of source code must retain the above copyright
18 ff3adf60 2004-04-14 devnull notice, this list of conditions and the following disclaimer.
20 ff3adf60 2004-04-14 devnull 2. The origin of this software must not be misrepresented; you must
21 ff3adf60 2004-04-14 devnull not claim that you wrote the original software. If you use this
22 ff3adf60 2004-04-14 devnull software in a product, an acknowledgment in the product
23 ff3adf60 2004-04-14 devnull documentation would be appreciated but is not required.
25 ff3adf60 2004-04-14 devnull 3. Altered source versions must be plainly marked as such, and must
26 ff3adf60 2004-04-14 devnull not be misrepresented as being the original software.
28 ff3adf60 2004-04-14 devnull 4. The name of the author may not be used to endorse or promote
29 ff3adf60 2004-04-14 devnull products derived from this software without specific prior written
30 ff3adf60 2004-04-14 devnull permission.
32 ff3adf60 2004-04-14 devnull THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33 ff3adf60 2004-04-14 devnull OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 ff3adf60 2004-04-14 devnull WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 ff3adf60 2004-04-14 devnull ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36 ff3adf60 2004-04-14 devnull DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37 ff3adf60 2004-04-14 devnull DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38 ff3adf60 2004-04-14 devnull GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39 ff3adf60 2004-04-14 devnull INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 ff3adf60 2004-04-14 devnull WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41 ff3adf60 2004-04-14 devnull NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42 ff3adf60 2004-04-14 devnull SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 ff3adf60 2004-04-14 devnull Julian Seward, Cambridge, UK.
45 ff3adf60 2004-04-14 devnull jseward@acm.org
46 ff3adf60 2004-04-14 devnull bzip2/libbzip2 version 1.0 of 21 March 2000
48 ff3adf60 2004-04-14 devnull This program is based on (at least) the work of:
49 ff3adf60 2004-04-14 devnull Mike Burrows
50 ff3adf60 2004-04-14 devnull David Wheeler
51 ff3adf60 2004-04-14 devnull Peter Fenwick
52 ff3adf60 2004-04-14 devnull Alistair Moffat
53 ff3adf60 2004-04-14 devnull Radford Neal
54 ff3adf60 2004-04-14 devnull Ian H. Witten
55 ff3adf60 2004-04-14 devnull Robert Sedgewick
56 ff3adf60 2004-04-14 devnull Jon L. Bentley
58 ff3adf60 2004-04-14 devnull For more information on these sources, see the manual.
62 ff3adf60 2004-04-14 devnull #include "os.h"
63 ff3adf60 2004-04-14 devnull #include "bzlib.h"
64 ff3adf60 2004-04-14 devnull #include "bzlib_private.h"
66 ff3adf60 2004-04-14 devnull /*---------------------------------------------------*/
67 ff3adf60 2004-04-14 devnull #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
68 ff3adf60 2004-04-14 devnull #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
69 ff3adf60 2004-04-14 devnull #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
71 ff3adf60 2004-04-14 devnull #define ADDWEIGHTS(zw1,zw2) \
72 ff3adf60 2004-04-14 devnull (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
73 ff3adf60 2004-04-14 devnull (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
75 ff3adf60 2004-04-14 devnull #define UPHEAP(z) \
77 ff3adf60 2004-04-14 devnull Int32 zz, tmp; \
78 ff3adf60 2004-04-14 devnull zz = z; tmp = heap[zz]; \
79 ff3adf60 2004-04-14 devnull while (weight[tmp] < weight[heap[zz >> 1]]) { \
80 ff3adf60 2004-04-14 devnull heap[zz] = heap[zz >> 1]; \
81 ff3adf60 2004-04-14 devnull zz >>= 1; \
83 ff3adf60 2004-04-14 devnull heap[zz] = tmp; \
86 ff3adf60 2004-04-14 devnull #define DOWNHEAP(z) \
88 ff3adf60 2004-04-14 devnull Int32 zz, yy, tmp; \
89 ff3adf60 2004-04-14 devnull zz = z; tmp = heap[zz]; \
90 ff3adf60 2004-04-14 devnull while (True) { \
91 ff3adf60 2004-04-14 devnull yy = zz << 1; \
92 ff3adf60 2004-04-14 devnull if (yy > nHeap) break; \
93 ff3adf60 2004-04-14 devnull if (yy < nHeap && \
94 ff3adf60 2004-04-14 devnull weight[heap[yy+1]] < weight[heap[yy]]) \
96 ff3adf60 2004-04-14 devnull if (weight[tmp] < weight[heap[yy]]) break; \
97 ff3adf60 2004-04-14 devnull heap[zz] = heap[yy]; \
98 ff3adf60 2004-04-14 devnull zz = yy; \
100 ff3adf60 2004-04-14 devnull heap[zz] = tmp; \
104 ff3adf60 2004-04-14 devnull /*---------------------------------------------------*/
105 ff3adf60 2004-04-14 devnull void BZ2_hbMakeCodeLengths ( UChar *len,
106 ff3adf60 2004-04-14 devnull Int32 *freq,
107 ff3adf60 2004-04-14 devnull Int32 alphaSize,
108 ff3adf60 2004-04-14 devnull Int32 maxLen )
111 ff3adf60 2004-04-14 devnull Nodes and heap entries run from 1. Entry 0
112 ff3adf60 2004-04-14 devnull for both the heap and nodes is a sentinel.
114 ff3adf60 2004-04-14 devnull Int32 nNodes, nHeap, n1, n2, i, j, k;
115 ff3adf60 2004-04-14 devnull Bool tooLong;
117 ff3adf60 2004-04-14 devnull Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
118 ff3adf60 2004-04-14 devnull Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
119 ff3adf60 2004-04-14 devnull Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
121 ff3adf60 2004-04-14 devnull for (i = 0; i < alphaSize; i++)
122 ff3adf60 2004-04-14 devnull weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
124 ff3adf60 2004-04-14 devnull while (True) {
126 ff3adf60 2004-04-14 devnull nNodes = alphaSize;
127 ff3adf60 2004-04-14 devnull nHeap = 0;
129 ff3adf60 2004-04-14 devnull heap[0] = 0;
130 ff3adf60 2004-04-14 devnull weight[0] = 0;
131 ff3adf60 2004-04-14 devnull parent[0] = -2;
133 ff3adf60 2004-04-14 devnull for (i = 1; i <= alphaSize; i++) {
134 ff3adf60 2004-04-14 devnull parent[i] = -1;
135 ff3adf60 2004-04-14 devnull nHeap++;
136 ff3adf60 2004-04-14 devnull heap[nHeap] = i;
137 ff3adf60 2004-04-14 devnull UPHEAP(nHeap);
140 ff3adf60 2004-04-14 devnull AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
142 ff3adf60 2004-04-14 devnull while (nHeap > 1) {
143 ff3adf60 2004-04-14 devnull n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
144 ff3adf60 2004-04-14 devnull n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
145 ff3adf60 2004-04-14 devnull nNodes++;
146 ff3adf60 2004-04-14 devnull parent[n1] = parent[n2] = nNodes;
147 ff3adf60 2004-04-14 devnull weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
148 ff3adf60 2004-04-14 devnull parent[nNodes] = -1;
149 ff3adf60 2004-04-14 devnull nHeap++;
150 ff3adf60 2004-04-14 devnull heap[nHeap] = nNodes;
151 ff3adf60 2004-04-14 devnull UPHEAP(nHeap);
154 ff3adf60 2004-04-14 devnull AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
156 ff3adf60 2004-04-14 devnull tooLong = False;
157 ff3adf60 2004-04-14 devnull for (i = 1; i <= alphaSize; i++) {
160 ff3adf60 2004-04-14 devnull while (parent[k] >= 0) { k = parent[k]; j++; }
161 ff3adf60 2004-04-14 devnull len[i-1] = j;
162 ff3adf60 2004-04-14 devnull if (j > maxLen) tooLong = True;
165 ff3adf60 2004-04-14 devnull if (! tooLong) break;
167 ff3adf60 2004-04-14 devnull for (i = 1; i < alphaSize; i++) {
168 ff3adf60 2004-04-14 devnull j = weight[i] >> 8;
169 ff3adf60 2004-04-14 devnull j = 1 + (j / 2);
170 ff3adf60 2004-04-14 devnull weight[i] = j << 8;
176 ff3adf60 2004-04-14 devnull /*---------------------------------------------------*/
177 ff3adf60 2004-04-14 devnull void BZ2_hbAssignCodes ( Int32 *code,
178 ff3adf60 2004-04-14 devnull UChar *length,
179 ff3adf60 2004-04-14 devnull Int32 minLen,
180 ff3adf60 2004-04-14 devnull Int32 maxLen,
181 ff3adf60 2004-04-14 devnull Int32 alphaSize )
183 ff3adf60 2004-04-14 devnull Int32 n, vec, i;
185 ff3adf60 2004-04-14 devnull vec = 0;
186 ff3adf60 2004-04-14 devnull for (n = minLen; n <= maxLen; n++) {
187 ff3adf60 2004-04-14 devnull for (i = 0; i < alphaSize; i++)
188 ff3adf60 2004-04-14 devnull if (length[i] == n) { code[i] = vec; vec++; };
189 ff3adf60 2004-04-14 devnull vec <<= 1;
194 ff3adf60 2004-04-14 devnull /*---------------------------------------------------*/
195 ff3adf60 2004-04-14 devnull void BZ2_hbCreateDecodeTables ( Int32 *limit,
196 ff3adf60 2004-04-14 devnull Int32 *base,
197 ff3adf60 2004-04-14 devnull Int32 *perm,
198 ff3adf60 2004-04-14 devnull UChar *length,
199 ff3adf60 2004-04-14 devnull Int32 minLen,
200 ff3adf60 2004-04-14 devnull Int32 maxLen,
201 ff3adf60 2004-04-14 devnull Int32 alphaSize )
203 ff3adf60 2004-04-14 devnull Int32 pp, i, j, vec;
206 ff3adf60 2004-04-14 devnull for (i = minLen; i <= maxLen; i++)
207 ff3adf60 2004-04-14 devnull for (j = 0; j < alphaSize; j++)
208 ff3adf60 2004-04-14 devnull if (length[j] == i) { perm[pp] = j; pp++; };
210 ff3adf60 2004-04-14 devnull for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
211 ff3adf60 2004-04-14 devnull for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
213 ff3adf60 2004-04-14 devnull for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
215 ff3adf60 2004-04-14 devnull for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
216 ff3adf60 2004-04-14 devnull vec = 0;
218 ff3adf60 2004-04-14 devnull for (i = minLen; i <= maxLen; i++) {
219 ff3adf60 2004-04-14 devnull vec += (base[i+1] - base[i]);
220 ff3adf60 2004-04-14 devnull limit[i] = vec-1;
221 ff3adf60 2004-04-14 devnull vec <<= 1;
223 ff3adf60 2004-04-14 devnull for (i = minLen + 1; i <= maxLen; i++)
224 ff3adf60 2004-04-14 devnull base[i] = ((limit[i-1] + 1) << 1) - base[i];
228 ff3adf60 2004-04-14 devnull /*-------------------------------------------------------------*/
229 ff3adf60 2004-04-14 devnull /*--- end huffman.c ---*/
230 ff3adf60 2004-04-14 devnull /*-------------------------------------------------------------*/