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