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