1
2 /*-------------------------------------------------------------*/
3 /*--- Huffman coding low-level stuff ---*/
4 /*--- huffman.c ---*/
5 /*-------------------------------------------------------------*/
6
7 /* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.5 of 10 December 2007
12 Copyright (C) 1996-2007 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22 #include "bzlib_private.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 /*---------------------------------------------------*/
28 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
29 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
30 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
31
32 #define ADDWEIGHTS(zw1,zw2) \
33 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
34 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
35
36 #define UPHEAP(z) \
37 { \
38 Int32 zz, tmp; \
39 zz = z; tmp = heap[zz]; \
40 while (weight[tmp] < weight[heap[zz >> 1]]) { \
41 heap[zz] = heap[zz >> 1]; \
42 zz >>= 1; \
43 } \
44 heap[zz] = tmp; \
45 }
46
47 #define DOWNHEAP(z) \
48 { \
49 Int32 zz, yy, tmp; \
50 zz = z; tmp = heap[zz]; \
51 while (True) { \
52 yy = zz << 1; \
53 if (yy > nHeap) break; \
54 if (yy < nHeap && \
55 weight[heap[yy+1]] < weight[heap[yy]]) \
56 yy++; \
57 if (weight[tmp] < weight[heap[yy]]) break; \
58 heap[zz] = heap[yy]; \
59 zz = yy; \
60 } \
61 heap[zz] = tmp; \
62 }
63
64
65 /*---------------------------------------------------*/
BZ2_hbMakeCodeLengths(UChar * len,Int32 * freq,Int32 alphaSize,Int32 maxLen)66 void BZ2_hbMakeCodeLengths ( UChar *len,
67 Int32 *freq,
68 Int32 alphaSize,
69 Int32 maxLen )
70 {
71 /*--
72 Nodes and heap entries run from 1. Entry 0
73 for both the heap and nodes is a sentinel.
74 --*/
75 Int32 nNodes, nHeap, n1, n2, i, j, k;
76 Bool tooLong;
77
78 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
79 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
80 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
81
82 for (i = 0; i < alphaSize; i++)
83 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
84
85 while (True) {
86
87 nNodes = alphaSize;
88 nHeap = 0;
89
90 heap[0] = 0;
91 weight[0] = 0;
92 parent[0] = -2;
93
94 for (i = 1; i <= alphaSize; i++) {
95 parent[i] = -1;
96 nHeap++;
97 heap[nHeap] = i;
98 UPHEAP(nHeap);
99 }
100
101 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
102
103 while (nHeap > 1) {
104 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
105 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
106 nNodes++;
107 parent[n1] = parent[n2] = nNodes;
108 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
109 parent[nNodes] = -1;
110 nHeap++;
111 heap[nHeap] = nNodes;
112 UPHEAP(nHeap);
113 }
114
115 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
116
117 tooLong = False;
118 for (i = 1; i <= alphaSize; i++) {
119 j = 0;
120 k = i;
121 while (parent[k] >= 0) { k = parent[k]; j++; }
122 len[i-1] = j;
123 if (j > maxLen) tooLong = True;
124 }
125
126 if (! tooLong) break;
127
128 /* 17 Oct 04: keep-going condition for the following loop used
129 to be 'i < alphaSize', which missed the last element,
130 theoretically leading to the possibility of the compressor
131 looping. However, this count-scaling step is only needed if
132 one of the generated Huffman code words is longer than
133 maxLen, which up to and including version 1.0.2 was 20 bits,
134 which is extremely unlikely. In version 1.0.3 maxLen was
135 changed to 17 bits, which has minimal effect on compression
136 ratio, but does mean this scaling step is used from time to
137 time, enough to verify that it works.
138
139 This means that bzip2-1.0.3 and later will only produce
140 Huffman codes with a maximum length of 17 bits. However, in
141 order to preserve backwards compatibility with bitstreams
142 produced by versions pre-1.0.3, the decompressor must still
143 handle lengths of up to 20. */
144
145 for (i = 1; i <= alphaSize; i++) {
146 j = weight[i] >> 8;
147 j = 1 + (j / 2);
148 weight[i] = j << 8;
149 }
150 }
151 }
152
153
154 /*---------------------------------------------------*/
BZ2_hbAssignCodes(Int32 * code,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)155 void BZ2_hbAssignCodes ( Int32 *code,
156 UChar *length,
157 Int32 minLen,
158 Int32 maxLen,
159 Int32 alphaSize )
160 {
161 Int32 n, vec, i;
162
163 vec = 0;
164 for (n = minLen; n <= maxLen; n++) {
165 for (i = 0; i < alphaSize; i++)
166 if (length[i] == n) { code[i] = vec; vec++; };
167 vec <<= 1;
168 }
169 }
170
171
172 /*---------------------------------------------------*/
BZ2_hbCreateDecodeTables(Int32 * limit,Int32 * base,Int32 * perm,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)173 void BZ2_hbCreateDecodeTables ( Int32 *limit,
174 Int32 *base,
175 Int32 *perm,
176 UChar *length,
177 Int32 minLen,
178 Int32 maxLen,
179 Int32 alphaSize )
180 {
181 Int32 pp, i, j, vec;
182
183 pp = 0;
184 for (i = minLen; i <= maxLen; i++)
185 for (j = 0; j < alphaSize; j++)
186 if (length[j] == i) { perm[pp] = j; pp++; };
187
188 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
189 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
190
191 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
192
193 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
194 vec = 0;
195
196 for (i = minLen; i <= maxLen; i++) {
197 vec += (base[i+1] - base[i]);
198 limit[i] = vec-1;
199 vec <<= 1;
200 }
201 for (i = minLen + 1; i <= maxLen; i++)
202 base[i] = ((limit[i-1] + 1) << 1) - base[i];
203 }
204
205
206 /*-------------------------------------------------------------*/
207 /*--- end huffman.c ---*/
208 /*-------------------------------------------------------------*/
209
210 ABC_NAMESPACE_IMPL_END
211