Contents of /trunk/mkinitrd-magellan/busybox/archival/bz/huffman.c
Parent Directory | Revision Log
Revision 816 -
(show annotations)
(download)
Fri Apr 24 18:33:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 5695 byte(s)
Fri Apr 24 18:33:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 5695 byte(s)
-updated to busybox-1.13.4
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 | /*-------------------------------------------------------------*/ |