diff options
author | Julian Seward <jseward@acm.org> | 1998-08-23 22:13:13 +0200 |
---|---|---|
committer | Julian Seward <jseward@acm.org> | 1998-08-23 22:13:13 +0200 |
commit | 977101ad5f833f5c0a574bfeea408e5301a6b052 (patch) | |
tree | fc1e8fed202869c116cbf6b8c362456042494a0a /huffman.c | |
parent | 1eb67a9d8f7f05ae310bc9ef297d176f3a3f8a37 (diff) | |
download | bzip2-977101ad5f833f5c0a574bfeea408e5301a6b052.tar.gz bzip2-977101ad5f833f5c0a574bfeea408e5301a6b052.tar.bz2 bzip2-977101ad5f833f5c0a574bfeea408e5301a6b052.zip |
bzip2-0.9.0cbzip2-0.9.0c
Diffstat (limited to 'huffman.c')
-rw-r--r-- | huffman.c | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/huffman.c b/huffman.c new file mode 100644 index 0000000..8254990 --- /dev/null +++ b/huffman.c | |||
@@ -0,0 +1,228 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Huffman coding low-level stuff ---*/ | ||
4 | /*--- huffman.c ---*/ | ||
5 | /*-------------------------------------------------------------*/ | ||
6 | |||
7 | /*-- | ||
8 | This file is a part of bzip2 and/or libbzip2, a program and | ||
9 | library for lossless, block-sorting data compression. | ||
10 | |||
11 | Copyright (C) 1996-1998 Julian R Seward. All rights reserved. | ||
12 | |||
13 | Redistribution and use in source and binary forms, with or without | ||
14 | modification, are permitted provided that the following conditions | ||
15 | are met: | ||
16 | |||
17 | 1. Redistributions of source code must retain the above copyright | ||
18 | notice, this list of conditions and the following disclaimer. | ||
19 | |||
20 | 2. The origin of this software must not be misrepresented; you must | ||
21 | not claim that you wrote the original software. If you use this | ||
22 | software in a product, an acknowledgment in the product | ||
23 | documentation would be appreciated but is not required. | ||
24 | |||
25 | 3. Altered source versions must be plainly marked as such, and must | ||
26 | not be misrepresented as being the original software. | ||
27 | |||
28 | 4. The name of the author may not be used to endorse or promote | ||
29 | products derived from this software without specific prior written | ||
30 | permission. | ||
31 | |||
32 | THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS | ||
33 | OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | ||
34 | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
35 | ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY | ||
36 | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
37 | DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE | ||
38 | GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
39 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | ||
40 | WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | ||
41 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | ||
42 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
43 | |||
44 | Julian Seward, Guildford, Surrey, UK. | ||
45 | jseward@acm.org | ||
46 | bzip2/libbzip2 version 0.9.0c of 18 October 1998 | ||
47 | |||
48 | This program is based on (at least) the work of: | ||
49 | Mike Burrows | ||
50 | David Wheeler | ||
51 | Peter Fenwick | ||
52 | Alistair Moffat | ||
53 | Radford Neal | ||
54 | Ian H. Witten | ||
55 | Robert Sedgewick | ||
56 | Jon L. Bentley | ||
57 | |||
58 | For more information on these sources, see the manual. | ||
59 | --*/ | ||
60 | |||
61 | |||
62 | #include "bzlib_private.h" | ||
63 | |||
64 | /*---------------------------------------------------*/ | ||
65 | #define WEIGHTOF(zz0) ((zz0) & 0xffffff00) | ||
66 | #define DEPTHOF(zz1) ((zz1) & 0x000000ff) | ||
67 | #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3)) | ||
68 | |||
69 | #define ADDWEIGHTS(zw1,zw2) \ | ||
70 | (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \ | ||
71 | (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2))) | ||
72 | |||
73 | #define UPHEAP(z) \ | ||
74 | { \ | ||
75 | Int32 zz, tmp; \ | ||
76 | zz = z; tmp = heap[zz]; \ | ||
77 | while (weight[tmp] < weight[heap[zz >> 1]]) { \ | ||
78 | heap[zz] = heap[zz >> 1]; \ | ||
79 | zz >>= 1; \ | ||
80 | } \ | ||
81 | heap[zz] = tmp; \ | ||
82 | } | ||
83 | |||
84 | #define DOWNHEAP(z) \ | ||
85 | { \ | ||
86 | Int32 zz, yy, tmp; \ | ||
87 | zz = z; tmp = heap[zz]; \ | ||
88 | while (True) { \ | ||
89 | yy = zz << 1; \ | ||
90 | if (yy > nHeap) break; \ | ||
91 | if (yy < nHeap && \ | ||
92 | weight[heap[yy+1]] < weight[heap[yy]]) \ | ||
93 | yy++; \ | ||
94 | if (weight[tmp] < weight[heap[yy]]) break; \ | ||
95 | heap[zz] = heap[yy]; \ | ||
96 | zz = yy; \ | ||
97 | } \ | ||
98 | heap[zz] = tmp; \ | ||
99 | } | ||
100 | |||
101 | |||
102 | /*---------------------------------------------------*/ | ||
103 | void hbMakeCodeLengths ( UChar *len, | ||
104 | Int32 *freq, | ||
105 | Int32 alphaSize, | ||
106 | Int32 maxLen ) | ||
107 | { | ||
108 | /*-- | ||
109 | Nodes and heap entries run from 1. Entry 0 | ||
110 | for both the heap and nodes is a sentinel. | ||
111 | --*/ | ||
112 | Int32 nNodes, nHeap, n1, n2, i, j, k; | ||
113 | Bool tooLong; | ||
114 | |||
115 | Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ]; | ||
116 | Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ]; | ||
117 | Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; | ||
118 | |||
119 | for (i = 0; i < alphaSize; i++) | ||
120 | weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; | ||
121 | |||
122 | while (True) { | ||
123 | |||
124 | nNodes = alphaSize; | ||
125 | nHeap = 0; | ||
126 | |||
127 | heap[0] = 0; | ||
128 | weight[0] = 0; | ||
129 | parent[0] = -2; | ||
130 | |||
131 | for (i = 1; i <= alphaSize; i++) { | ||
132 | parent[i] = -1; | ||
133 | nHeap++; | ||
134 | heap[nHeap] = i; | ||
135 | UPHEAP(nHeap); | ||
136 | } | ||
137 | |||
138 | AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 ); | ||
139 | |||
140 | while (nHeap > 1) { | ||
141 | n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); | ||
142 | n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); | ||
143 | nNodes++; | ||
144 | parent[n1] = parent[n2] = nNodes; | ||
145 | weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]); | ||
146 | parent[nNodes] = -1; | ||
147 | nHeap++; | ||
148 | heap[nHeap] = nNodes; | ||
149 | UPHEAP(nHeap); | ||
150 | } | ||
151 | |||
152 | AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 ); | ||
153 | |||
154 | tooLong = False; | ||
155 | for (i = 1; i <= alphaSize; i++) { | ||
156 | j = 0; | ||
157 | k = i; | ||
158 | while (parent[k] >= 0) { k = parent[k]; j++; } | ||
159 | len[i-1] = j; | ||
160 | if (j > maxLen) tooLong = True; | ||
161 | } | ||
162 | |||
163 | if (! tooLong) break; | ||
164 | |||
165 | for (i = 1; i < alphaSize; i++) { | ||
166 | j = weight[i] >> 8; | ||
167 | j = 1 + (j / 2); | ||
168 | weight[i] = j << 8; | ||
169 | } | ||
170 | } | ||
171 | } | ||
172 | |||
173 | |||
174 | /*---------------------------------------------------*/ | ||
175 | void hbAssignCodes ( Int32 *code, | ||
176 | UChar *length, | ||
177 | Int32 minLen, | ||
178 | Int32 maxLen, | ||
179 | Int32 alphaSize ) | ||
180 | { | ||
181 | Int32 n, vec, i; | ||
182 | |||
183 | vec = 0; | ||
184 | for (n = minLen; n <= maxLen; n++) { | ||
185 | for (i = 0; i < alphaSize; i++) | ||
186 | if (length[i] == n) { code[i] = vec; vec++; }; | ||
187 | vec <<= 1; | ||
188 | } | ||
189 | } | ||
190 | |||
191 | |||
192 | /*---------------------------------------------------*/ | ||
193 | void hbCreateDecodeTables ( Int32 *limit, | ||
194 | Int32 *base, | ||
195 | Int32 *perm, | ||
196 | UChar *length, | ||
197 | Int32 minLen, | ||
198 | Int32 maxLen, | ||
199 | Int32 alphaSize ) | ||
200 | { | ||
201 | Int32 pp, i, j, vec; | ||
202 | |||
203 | pp = 0; | ||
204 | for (i = minLen; i <= maxLen; i++) | ||
205 | for (j = 0; j < alphaSize; j++) | ||
206 | if (length[j] == i) { perm[pp] = j; pp++; }; | ||
207 | |||
208 | for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0; | ||
209 | for (i = 0; i < alphaSize; i++) base[length[i]+1]++; | ||
210 | |||
211 | for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1]; | ||
212 | |||
213 | for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0; | ||
214 | vec = 0; | ||
215 | |||
216 | for (i = minLen; i <= maxLen; i++) { | ||
217 | vec += (base[i+1] - base[i]); | ||
218 | limit[i] = vec-1; | ||
219 | vec <<= 1; | ||
220 | } | ||
221 | for (i = minLen + 1; i <= maxLen; i++) | ||
222 | base[i] = ((limit[i-1] + 1) << 1) - base[i]; | ||
223 | } | ||
224 | |||
225 | |||
226 | /*-------------------------------------------------------------*/ | ||
227 | /*--- end huffman.c ---*/ | ||
228 | /*-------------------------------------------------------------*/ | ||