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