aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDenis Vlasenko <vda.linux@googlemail.com>2007-10-13 03:36:03 +0000
committerDenis Vlasenko <vda.linux@googlemail.com>2007-10-13 03:36:03 +0000
commit77f1ec1b9bf100e6c10aa0856c7156e321511785 (patch)
treef20e5a9062ecad82a43bde81e3041a19c4292733
parent11c23d7b990eae27357e5a41a97d62b9a214f7db (diff)
downloadbusybox-w32-77f1ec1b9bf100e6c10aa0856c7156e321511785.tar.gz
busybox-w32-77f1ec1b9bf100e6c10aa0856c7156e321511785.tar.bz2
busybox-w32-77f1ec1b9bf100e6c10aa0856c7156e321511785.zip
bzip2: port bzip2 1.0.4 to busybox. note: bzip2 code resides
in separate directory (archival/bz/*) and is covered by BSD-style license. code size: 13k
Diffstat
-rw-r--r--archival/Config.in16
-rw-r--r--archival/Kbuild1
-rw-r--r--archival/bz/LICENSE44
-rw-r--r--archival/bz/README90
-rw-r--r--archival/bz/blocksort.c1128
-rw-r--r--archival/bz/bzlib.c433
-rw-r--r--archival/bz/bzlib.h63
-rw-r--r--archival/bz/bzlib_private.h234
-rw-r--r--archival/bz/compress.c671
-rw-r--r--archival/bz/crctable.c105
-rw-r--r--archival/bz/huffman.c188
-rw-r--r--archival/bz/randtable.c85
-rw-r--r--archival/bzip2.c166
-rw-r--r--archival/gzip.c11
-rw-r--r--archival/libunarchive/Kbuild14
-rw-r--r--archival/libunarchive/decompress_unzip.c2
-rw-r--r--include/applets.h1
-rw-r--r--include/libbb.h3
-rw-r--r--include/platform.h6
-rw-r--r--include/usage.h14
20 files changed, 3253 insertions, 22 deletions
diff --git a/archival/Config.in b/archival/Config.in
index 49070da06..8d31ec771 100644
--- a/archival/Config.in
+++ b/archival/Config.in
@@ -48,12 +48,22 @@ config BUNZIP2
48 conventional LZ77/LZ78-based compressors, and approaches the 48 conventional LZ77/LZ78-based compressors, and approaches the
49 performance of the PPM family of statistical compressors. 49 performance of the PPM family of statistical compressors.
50 50
51 The BusyBox bunzip2 applet is limited to de-compression only.
52 On an x86 system, this applet adds about 11K.
53
54 Unless you have a specific application which requires bunzip2, you 51 Unless you have a specific application which requires bunzip2, you
55 should probably say N here. 52 should probably say N here.
56 53
54config BZIP2
55 bool "bzip2"
56 default n
57 help
58 bzip2 is a compression utility using the Burrows-Wheeler block
59 sorting text compression algorithm, and Huffman coding. Compression
60 is generally considerably better than that achieved by more
61 conventional LZ77/LZ78-based compressors, and approaches the
62 performance of the PPM family of statistical compressors.
63
64 Unless you have a specific application which requires bzip2, you
65 should probably say N here.
66
57config CPIO 67config CPIO
58 bool "cpio" 68 bool "cpio"
59 default n 69 default n
diff --git a/archival/Kbuild b/archival/Kbuild
index 07b442f15..72dbdda0e 100644
--- a/archival/Kbuild
+++ b/archival/Kbuild
@@ -9,6 +9,7 @@ libs-y += libunarchive/
9lib-y:= 9lib-y:=
10lib-$(CONFIG_AR) += ar.o 10lib-$(CONFIG_AR) += ar.o
11lib-$(CONFIG_BUNZIP2) += bbunzip.o 11lib-$(CONFIG_BUNZIP2) += bbunzip.o
12lib-$(CONFIG_BZIP2) += bzip2.o bbunzip.o
12lib-$(CONFIG_UNLZMA) += bbunzip.o 13lib-$(CONFIG_UNLZMA) += bbunzip.o
13lib-$(CONFIG_CPIO) += cpio.o 14lib-$(CONFIG_CPIO) += cpio.o
14lib-$(CONFIG_DPKG) += dpkg.o 15lib-$(CONFIG_DPKG) += dpkg.o
diff --git a/archival/bz/LICENSE b/archival/bz/LICENSE
new file mode 100644
index 000000000..f01f08022
--- /dev/null
+++ b/archival/bz/LICENSE
@@ -0,0 +1,44 @@
1bzip2 applet in busybox is based on lightly-modified source
2of bzip2 version 1.0.4. bzip2 source is distributed
3under the following conditions (copied verbatim from LICENSE file)
4===========================================================
5
6
7This program, "bzip2", the associated library "libbzip2", and all
8documentation, are copyright (C) 1996-2006 Julian R Seward. All
9rights reserved.
10
11Redistribution and use in source and binary forms, with or without
12modification, are permitted provided that the following conditions
13are met:
14
151. Redistributions of source code must retain the above copyright
16 notice, this list of conditions and the following disclaimer.
17
182. The origin of this software must not be misrepresented; you must
19 not claim that you wrote the original software. If you use this
20 software in a product, an acknowledgment in the product
21 documentation would be appreciated but is not required.
22
233. Altered source versions must be plainly marked as such, and must
24 not be misrepresented as being the original software.
25
264. The name of the author may not be used to endorse or promote
27 products derived from this software without specific prior written
28 permission.
29
30THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
31OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
32WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
34DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
36GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
37INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
38WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
39NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
40SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41
42Julian Seward, Cambridge, UK.
43jseward@bzip.org
44bzip2/libbzip2 version 1.0.4 of 20 December 2006
diff --git a/archival/bz/README b/archival/bz/README
new file mode 100644
index 000000000..ef06d67da
--- /dev/null
+++ b/archival/bz/README
@@ -0,0 +1,90 @@
1This file is an abridged version of README from bizp2 1.0.4
2Build instructions (which are not relevant to busyboxed bzip2)
3are removed.
4===========================================================
5
6
7This is the README for bzip2/libzip2.
8This version is fully compatible with the previous public releases.
9
10------------------------------------------------------------------
11This file is part of bzip2/libbzip2, a program and library for
12lossless, block-sorting data compression.
13
14bzip2/libbzip2 version 1.0.4 of 20 December 2006
15Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
16
17Please read the WARNING, DISCLAIMER and PATENTS sections in this file.
18
19This program is released under the terms of the license contained
20in the file LICENSE.
21------------------------------------------------------------------
22
23Please read and be aware of the following:
24
25
26WARNING:
27
28 This program and library (attempts to) compress data by
29 performing several non-trivial transformations on it.
30 Unless you are 100% familiar with *all* the algorithms
31 contained herein, and with the consequences of modifying them,
32 you should NOT meddle with the compression or decompression
33 machinery. Incorrect changes can and very likely *will*
34 lead to disastrous loss of data.
35
36
37DISCLAIMER:
38
39 I TAKE NO RESPONSIBILITY FOR ANY LOSS OF DATA ARISING FROM THE
40 USE OF THIS PROGRAM/LIBRARY, HOWSOEVER CAUSED.
41
42 Every compression of a file implies an assumption that the
43 compressed file can be decompressed to reproduce the original.
44 Great efforts in design, coding and testing have been made to
45 ensure that this program works correctly. However, the complexity
46 of the algorithms, and, in particular, the presence of various
47 special cases in the code which occur with very low but non-zero
48 probability make it impossible to rule out the possibility of bugs
49 remaining in the program. DO NOT COMPRESS ANY DATA WITH THIS
50 PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE POSSIBILITY, HOWEVER
51 SMALL, THAT THE DATA WILL NOT BE RECOVERABLE.
52
53 That is not to say this program is inherently unreliable.
54 Indeed, I very much hope the opposite is true. bzip2/libbzip2
55 has been carefully constructed and extensively tested.
56
57
58PATENTS:
59
60 To the best of my knowledge, bzip2/libbzip2 does not use any
61 patented algorithms. However, I do not have the resources
62 to carry out a patent search. Therefore I cannot give any
63 guarantee of the above statement.
64
65
66I hope you find bzip2 useful. Feel free to contact me at
67 jseward@bzip.org
68if you have any suggestions or queries. Many people mailed me with
69comments, suggestions and patches after the releases of bzip-0.15,
70bzip-0.21, and bzip2 versions 0.1pl2, 0.9.0, 0.9.5, 1.0.0, 1.0.1,
711.0.2 and 1.0.3, and the changes in bzip2 are largely a result of this
72feedback. I thank you for your comments.
73
74bzip2's "home" is http://www.bzip.org/
75
76Julian Seward
77jseward@bzip.org
78Cambridge, UK.
79
8018 July 1996 (version 0.15)
8125 August 1996 (version 0.21)
82 7 August 1997 (bzip2, version 0.1)
8329 August 1997 (bzip2, version 0.1pl2)
8423 August 1998 (bzip2, version 0.9.0)
85 8 June 1999 (bzip2, version 0.9.5)
86 4 Sept 1999 (bzip2, version 0.9.5d)
87 5 May 2000 (bzip2, version 1.0pre8)
8830 December 2001 (bzip2, version 1.0.2pre1)
8915 February 2005 (bzip2, version 1.0.3)
9020 December 2006 (bzip2, version 1.0.4)
diff --git a/archival/bz/blocksort.c b/archival/bz/blocksort.c
new file mode 100644
index 000000000..7d2856ba7
--- /dev/null
+++ b/archival/bz/blocksort.c
@@ -0,0 +1,1128 @@
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/*--- Block sorting machinery ---*/
9/*--- blocksort.c ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26/* #include "bzlib_private.h" */
27
28/*---------------------------------------------*/
29/*--- Fallback O(N log(N)^2) sorting ---*/
30/*--- algorithm, for repetitive blocks ---*/
31/*---------------------------------------------*/
32
33/*---------------------------------------------*/
34static
35inline
36void fallbackSimpleSort(uint32_t* fmap,
37 uint32_t* eclass,
38 int32_t lo,
39 int32_t hi)
40{
41 int32_t i, j, tmp;
42 uint32_t ec_tmp;
43
44 if (lo == hi) return;
45
46 if (hi - lo > 3) {
47 for (i = hi-4; i >= lo; i--) {
48 tmp = fmap[i];
49 ec_tmp = eclass[tmp];
50 for (j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4)
51 fmap[j-4] = fmap[j];
52 fmap[j-4] = tmp;
53 }
54 }
55
56 for (i = hi-1; i >= lo; i--) {
57 tmp = fmap[i];
58 ec_tmp = eclass[tmp];
59 for (j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++)
60 fmap[j-1] = fmap[j];
61 fmap[j-1] = tmp;
62 }
63}
64
65
66/*---------------------------------------------*/
67#define fswap(zz1, zz2) \
68{ \
69 int32_t zztmp = zz1; \
70 zz1 = zz2; \
71 zz2 = zztmp; \
72}
73
74#define fvswap(zzp1, zzp2, zzn) \
75{ \
76 int32_t yyp1 = (zzp1); \
77 int32_t yyp2 = (zzp2); \
78 int32_t yyn = (zzn); \
79 while (yyn > 0) { \
80 fswap(fmap[yyp1], fmap[yyp2]); \
81 yyp1++; \
82 yyp2++; \
83 yyn--; \
84 } \
85}
86
87
88#define fmin(a,b) ((a) < (b)) ? (a) : (b)
89
90#define fpush(lz,hz) { \
91 stackLo[sp] = lz; \
92 stackHi[sp] = hz; \
93 sp++; \
94}
95
96#define fpop(lz,hz) { \
97 sp--; \
98 lz = stackLo[sp]; \
99 hz = stackHi[sp]; \
100}
101
102#define FALLBACK_QSORT_SMALL_THRESH 10
103#define FALLBACK_QSORT_STACK_SIZE 100
104
105
106static
107void fallbackQSort3(uint32_t* fmap,
108 uint32_t* eclass,
109 int32_t loSt,
110 int32_t hiSt)
111{
112 int32_t unLo, unHi, ltLo, gtHi, n, m;
113 int32_t sp, lo, hi;
114 uint32_t med, r, r3;
115 int32_t stackLo[FALLBACK_QSORT_STACK_SIZE];
116 int32_t stackHi[FALLBACK_QSORT_STACK_SIZE];
117
118 r = 0;
119
120 sp = 0;
121 fpush(loSt, hiSt);
122
123 while (sp > 0) {
124 AssertH(sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004);
125
126 fpop(lo, hi);
127 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
128 fallbackSimpleSort(fmap, eclass, lo, hi);
129 continue;
130 }
131
132 /* Random partitioning. Median of 3 sometimes fails to
133 * avoid bad cases. Median of 9 seems to help but
134 * looks rather expensive. This too seems to work but
135 * is cheaper. Guidance for the magic constants
136 * 7621 and 32768 is taken from Sedgewick's algorithms
137 * book, chapter 35.
138 */
139 r = ((r * 7621) + 1) % 32768;
140 r3 = r % 3;
141 if (r3 == 0)
142 med = eclass[fmap[lo]];
143 else if (r3 == 1)
144 med = eclass[fmap[(lo+hi)>>1]];
145 else
146 med = eclass[fmap[hi]];
147
148 unLo = ltLo = lo;
149 unHi = gtHi = hi;
150
151 while (1) {
152 while (1) {
153 if (unLo > unHi) break;
154 n = (int32_t)eclass[fmap[unLo]] - (int32_t)med;
155 if (n == 0) {
156 fswap(fmap[unLo], fmap[ltLo]);
157 ltLo++;
158 unLo++;
159 continue;
160 };
161 if (n > 0) break;
162 unLo++;
163 }
164 while (1) {
165 if (unLo > unHi) break;
166 n = (int32_t)eclass[fmap[unHi]] - (int32_t)med;
167 if (n == 0) {
168 fswap(fmap[unHi], fmap[gtHi]);
169 gtHi--; unHi--;
170 continue;
171 };
172 if (n < 0) break;
173 unHi--;
174 }
175 if (unLo > unHi) break;
176 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
177 }
178
179 AssertD(unHi == unLo-1, "fallbackQSort3(2)");
180
181 if (gtHi < ltLo) continue;
182
183 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
184 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
185
186 n = lo + unLo - ltLo - 1;
187 m = hi - (gtHi - unHi) + 1;
188
189 if (n - lo > hi - m) {
190 fpush(lo, n);
191 fpush(m, hi);
192 } else {
193 fpush(m, hi);
194 fpush(lo, n);
195 }
196 }
197}
198
199#undef fmin
200#undef fpush
201#undef fpop
202#undef fswap
203#undef fvswap
204#undef FALLBACK_QSORT_SMALL_THRESH
205#undef FALLBACK_QSORT_STACK_SIZE
206
207
208/*---------------------------------------------*/
209/* Pre:
210 * nblock > 0
211 * eclass exists for [0 .. nblock-1]
212 * ((UChar*)eclass) [0 .. nblock-1] holds block
213 * ptr exists for [0 .. nblock-1]
214 *
215 * Post:
216 * ((UChar*)eclass) [0 .. nblock-1] holds block
217 * All other areas of eclass destroyed
218 * fmap [0 .. nblock-1] holds sorted order
219 * bhtab[0 .. 2+(nblock/32)] destroyed
220*/
221
222#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
223#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
224#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
225#define WORD_BH(zz) bhtab[(zz) >> 5]
226#define UNALIGNED_BH(zz) ((zz) & 0x01f)
227
228static
229void fallbackSort(uint32_t* fmap,
230 uint32_t* eclass,
231 uint32_t* bhtab,
232 int32_t nblock)
233{
234 int32_t ftab[257];
235 int32_t ftabCopy[256];
236 int32_t H, i, j, k, l, r, cc, cc1;
237 int32_t nNotDone;
238 int32_t nBhtab;
239 UChar* eclass8 = (UChar*)eclass;
240
241 /*
242 * Initial 1-char radix sort to generate
243 * initial fmap and initial BH bits.
244 */
245 for (i = 0; i < 257; i++) ftab[i] = 0;
246 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
247 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
248 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
249
250 for (i = 0; i < nblock; i++) {
251 j = eclass8[i];
252 k = ftab[j] - 1;
253 ftab[j] = k;
254 fmap[k] = i;
255 }
256
257 nBhtab = 2 + (nblock / 32);
258 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
259 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
260
261 /*
262 * Inductively refine the buckets. Kind-of an
263 * "exponential radix sort" (!), inspired by the
264 * Manber-Myers suffix array construction algorithm.
265 */
266
267 /*-- set sentinel bits for block-end detection --*/
268 for (i = 0; i < 32; i++) {
269 SET_BH(nblock + 2*i);
270 CLEAR_BH(nblock + 2*i + 1);
271 }
272
273 /*-- the log(N) loop --*/
274 H = 1;
275 while (1) {
276 j = 0;
277 for (i = 0; i < nblock; i++) {
278 if (ISSET_BH(i))
279 j = i;
280 k = fmap[i] - H;
281 if (k < 0)
282 k += nblock;
283 eclass[k] = j;
284 }
285
286 nNotDone = 0;
287 r = -1;
288 while (1) {
289
290 /*-- find the next non-singleton bucket --*/
291 k = r + 1;
292 while (ISSET_BH(k) && UNALIGNED_BH(k))
293 k++;
294 if (ISSET_BH(k)) {
295 while (WORD_BH(k) == 0xffffffff) k += 32;
296 while (ISSET_BH(k)) k++;
297 }
298 l = k - 1;
299 if (l >= nblock)
300 break;
301 while (!ISSET_BH(k) && UNALIGNED_BH(k))
302 k++;
303 if (!ISSET_BH(k)) {
304 while (WORD_BH(k) == 0x00000000) k += 32;
305 while (!ISSET_BH(k)) k++;
306 }
307 r = k - 1;
308 if (r >= nblock)
309 break;
310
311 /*-- now [l, r] bracket current bucket --*/
312 if (r > l) {
313 nNotDone += (r - l + 1);
314 fallbackQSort3(fmap, eclass, l, r);
315
316 /*-- scan bucket and generate header bits-- */
317 cc = -1;
318 for (i = l; i <= r; i++) {
319 cc1 = eclass[fmap[i]];
320 if (cc != cc1) {
321 SET_BH(i);
322 cc = cc1;
323 };
324 }
325 }
326 }
327
328 H *= 2;
329 if (H > nblock || nNotDone == 0)
330 break;
331 }
332
333 /*
334 * Reconstruct the original block in
335 * eclass8 [0 .. nblock-1], since the
336 * previous phase destroyed it.
337 */
338 j = 0;
339 for (i = 0; i < nblock; i++) {
340 while (ftabCopy[j] == 0)
341 j++;
342 ftabCopy[j]--;
343 eclass8[fmap[i]] = (UChar)j;
344 }
345 AssertH(j < 256, 1005);
346}
347
348#undef SET_BH
349#undef CLEAR_BH
350#undef ISSET_BH
351#undef WORD_BH
352#undef UNALIGNED_BH
353
354
355/*---------------------------------------------*/
356/*--- The main, O(N^2 log(N)) sorting ---*/
357/*--- algorithm. Faster for "normal" ---*/
358/*--- non-repetitive blocks. ---*/
359/*---------------------------------------------*/
360
361/*---------------------------------------------*/
362static
363inline
364Bool mainGtU(
365 uint32_t i1,
366 uint32_t i2,
367 UChar* block,
368 uint16_t* quadrant,
369 uint32_t nblock,
370 int32_t* budget)
371{
372 int32_t k;
373 UChar c1, c2;
374 uint16_t s1, s2;
375
376///unrolling
377 AssertD(i1 != i2, "mainGtU");
378 /* 1 */
379 c1 = block[i1]; c2 = block[i2];
380 if (c1 != c2) return (c1 > c2);
381 i1++; i2++;
382 /* 2 */
383 c1 = block[i1]; c2 = block[i2];
384 if (c1 != c2) return (c1 > c2);
385 i1++; i2++;
386 /* 3 */
387 c1 = block[i1]; c2 = block[i2];
388 if (c1 != c2) return (c1 > c2);
389 i1++; i2++;
390 /* 4 */
391 c1 = block[i1]; c2 = block[i2];
392 if (c1 != c2) return (c1 > c2);
393 i1++; i2++;
394 /* 5 */
395 c1 = block[i1]; c2 = block[i2];
396 if (c1 != c2) return (c1 > c2);
397 i1++; i2++;
398 /* 6 */
399 c1 = block[i1]; c2 = block[i2];
400 if (c1 != c2) return (c1 > c2);
401 i1++; i2++;
402 /* 7 */
403 c1 = block[i1]; c2 = block[i2];
404 if (c1 != c2) return (c1 > c2);
405 i1++; i2++;
406 /* 8 */
407 c1 = block[i1]; c2 = block[i2];
408 if (c1 != c2) return (c1 > c2);
409 i1++; i2++;
410 /* 9 */
411 c1 = block[i1]; c2 = block[i2];
412 if (c1 != c2) return (c1 > c2);
413 i1++; i2++;
414 /* 10 */
415 c1 = block[i1]; c2 = block[i2];
416 if (c1 != c2) return (c1 > c2);
417 i1++; i2++;
418 /* 11 */
419 c1 = block[i1]; c2 = block[i2];
420 if (c1 != c2) return (c1 > c2);
421 i1++; i2++;
422 /* 12 */
423 c1 = block[i1]; c2 = block[i2];
424 if (c1 != c2) return (c1 > c2);
425 i1++; i2++;
426
427 k = nblock + 8;
428
429///unrolling
430 do {
431 /* 1 */
432 c1 = block[i1]; c2 = block[i2];
433 if (c1 != c2) return (c1 > c2);
434 s1 = quadrant[i1]; s2 = quadrant[i2];
435 if (s1 != s2) return (s1 > s2);
436 i1++; i2++;
437 /* 2 */
438 c1 = block[i1]; c2 = block[i2];
439 if (c1 != c2) return (c1 > c2);
440 s1 = quadrant[i1]; s2 = quadrant[i2];
441 if (s1 != s2) return (s1 > s2);
442 i1++; i2++;
443 /* 3 */
444 c1 = block[i1]; c2 = block[i2];
445 if (c1 != c2) return (c1 > c2);
446 s1 = quadrant[i1]; s2 = quadrant[i2];
447 if (s1 != s2) return (s1 > s2);
448 i1++; i2++;
449 /* 4 */
450 c1 = block[i1]; c2 = block[i2];
451 if (c1 != c2) return (c1 > c2);
452 s1 = quadrant[i1]; s2 = quadrant[i2];
453 if (s1 != s2) return (s1 > s2);
454 i1++; i2++;
455 /* 5 */
456 c1 = block[i1]; c2 = block[i2];
457 if (c1 != c2) return (c1 > c2);
458 s1 = quadrant[i1]; s2 = quadrant[i2];
459 if (s1 != s2) return (s1 > s2);
460 i1++; i2++;
461 /* 6 */
462 c1 = block[i1]; c2 = block[i2];
463 if (c1 != c2) return (c1 > c2);
464 s1 = quadrant[i1]; s2 = quadrant[i2];
465 if (s1 != s2) return (s1 > s2);
466 i1++; i2++;
467 /* 7 */
468 c1 = block[i1]; c2 = block[i2];
469 if (c1 != c2) return (c1 > c2);
470 s1 = quadrant[i1]; s2 = quadrant[i2];
471 if (s1 != s2) return (s1 > s2);
472 i1++; i2++;
473 /* 8 */
474 c1 = block[i1]; c2 = block[i2];
475 if (c1 != c2) return (c1 > c2);
476 s1 = quadrant[i1]; s2 = quadrant[i2];
477 if (s1 != s2) return (s1 > s2);
478 i1++; i2++;
479
480 if (i1 >= nblock) i1 -= nblock;
481 if (i2 >= nblock) i2 -= nblock;
482
483 k -= 8;
484 (*budget)--;
485 } while (k >= 0);
486
487 return False;
488}
489
490
491/*---------------------------------------------*/
492/*
493 * Knuth's increments seem to work better
494 * than Incerpi-Sedgewick here. Possibly
495 * because the number of elems to sort is
496 * usually small, typically <= 20.
497 */
498static
499const int32_t incs[14] = {
500 1, 4, 13, 40, 121, 364, 1093, 3280,
501 9841, 29524, 88573, 265720,
502 797161, 2391484
503};
504
505static
506void mainSimpleSort(uint32_t* ptr,
507 UChar* block,
508 uint16_t* quadrant,
509 int32_t nblock,
510 int32_t lo,
511 int32_t hi,
512 int32_t d,
513 int32_t* budget)
514{
515 int32_t i, j, h, bigN, hp;
516 uint32_t v;
517
518 bigN = hi - lo + 1;
519 if (bigN < 2) return;
520
521 hp = 0;
522 while (incs[hp] < bigN) hp++;
523 hp--;
524
525 for (; hp >= 0; hp--) {
526 h = incs[hp];
527
528 i = lo + h;
529 while (1) {
530
531///unrolling
532 /*-- copy 1 --*/
533 if (i > hi) break;
534 v = ptr[i];
535 j = i;
536 while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
537 ptr[j] = ptr[j-h];
538 j = j - h;
539 if (j <= (lo + h - 1)) break;
540 }
541 ptr[j] = v;
542 i++;
543
544 /*-- copy 2 --*/
545 if (i > hi) break;
546 v = ptr[i];
547 j = i;
548 while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
549 ptr[j] = ptr[j-h];
550 j = j - h;
551 if (j <= (lo + h - 1)) break;
552 }
553 ptr[j] = v;
554 i++;
555
556 /*-- copy 3 --*/
557 if (i > hi) break;
558 v = ptr[i];
559 j = i;
560 while (mainGtU (ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
561 ptr[j] = ptr[j-h];
562 j = j - h;
563 if (j <= (lo + h - 1)) break;
564 }
565 ptr[j] = v;
566 i++;
567
568 if (*budget < 0) return;
569 }
570 }
571}
572
573
574/*---------------------------------------------*/
575/*
576 * The following is an implementation of
577 * an elegant 3-way quicksort for strings,
578 * described in a paper "Fast Algorithms for
579 * Sorting and Searching Strings", by Robert
580 * Sedgewick and Jon L. Bentley.
581 */
582
583#define mswap(zz1, zz2) \
584{ \
585 int32_t zztmp = zz1; \
586 zz1 = zz2; \
587 zz2 = zztmp; \
588}
589
590#define mvswap(zzp1, zzp2, zzn) \
591{ \
592 int32_t yyp1 = (zzp1); \
593 int32_t yyp2 = (zzp2); \
594 int32_t yyn = (zzn); \
595 while (yyn > 0) { \
596 mswap(ptr[yyp1], ptr[yyp2]); \
597 yyp1++; \
598 yyp2++; \
599 yyn--; \
600 } \
601}
602
603static
604inline
605UChar mmed3(UChar a, UChar b, UChar c)
606{
607 UChar t;
608 if (a > b) {
609 t = a;
610 a = b;
611 b = t;
612 };
613 if (b > c) {
614 b = c;
615 if (a > b)
616 b = a;
617 }
618 return b;
619}
620
621#define mmin(a,b) ((a) < (b)) ? (a) : (b)
622
623#define mpush(lz,hz,dz) \
624{ \
625 stackLo[sp] = lz; \
626 stackHi[sp] = hz; \
627 stackD [sp] = dz; \
628 sp++; \
629}
630
631#define mpop(lz,hz,dz) \
632{ \
633 sp--; \
634 lz = stackLo[sp]; \
635 hz = stackHi[sp]; \
636 dz = stackD [sp]; \
637}
638
639
640#define mnextsize(az) (nextHi[az]-nextLo[az])
641
642#define mnextswap(az,bz) \
643{ \
644 int32_t tz; \
645 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
646 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
647 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; \
648}
649
650#define MAIN_QSORT_SMALL_THRESH 20
651#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
652#define MAIN_QSORT_STACK_SIZE 100
653
654static
655void mainQSort3(uint32_t* ptr,
656 UChar* block,
657 uint16_t* quadrant,
658 int32_t nblock,
659 int32_t loSt,
660 int32_t hiSt,
661 int32_t dSt,
662 int32_t* budget)
663{
664 int32_t unLo, unHi, ltLo, gtHi, n, m, med;
665 int32_t sp, lo, hi, d;
666
667 int32_t stackLo[MAIN_QSORT_STACK_SIZE];
668 int32_t stackHi[MAIN_QSORT_STACK_SIZE];
669 int32_t stackD [MAIN_QSORT_STACK_SIZE];
670
671 int32_t nextLo[3];
672 int32_t nextHi[3];
673 int32_t nextD [3];
674
675 sp = 0;
676 mpush(loSt, hiSt, dSt);
677
678 while (sp > 0) {
679 AssertH(sp < MAIN_QSORT_STACK_SIZE - 2, 1001);
680
681 mpop(lo, hi, d);
682 if (hi - lo < MAIN_QSORT_SMALL_THRESH
683 || d > MAIN_QSORT_DEPTH_THRESH
684 ) {
685 mainSimpleSort(ptr, block, quadrant, nblock, lo, hi, d, budget);
686 if (*budget < 0)
687 return;
688 continue;
689 }
690
691 med = (int32_t) mmed3(block[ptr[lo ] + d],
692 block[ptr[hi ] + d],
693 block[ptr[(lo+hi) >> 1] + d]);
694
695 unLo = ltLo = lo;
696 unHi = gtHi = hi;
697
698 while (1) {
699 while (1) {
700 if (unLo > unHi)
701 break;
702 n = ((int32_t)block[ptr[unLo]+d]) - med;
703 if (n == 0) {
704 mswap(ptr[unLo], ptr[ltLo]);
705 ltLo++;
706 unLo++;
707 continue;
708 };
709 if (n > 0) break;
710 unLo++;
711 }
712 while (1) {
713 if (unLo > unHi)
714 break;
715 n = ((int32_t)block[ptr[unHi]+d]) - med;
716 if (n == 0) {
717 mswap(ptr[unHi], ptr[gtHi]);
718 gtHi--;
719 unHi--;
720 continue;
721 };
722 if (n < 0) break;
723 unHi--;
724 }
725 if (unLo > unHi)
726 break;
727 mswap(ptr[unLo], ptr[unHi]);
728 unLo++;
729 unHi--;
730 }
731
732 AssertD(unHi == unLo-1, "mainQSort3(2)");
733
734 if (gtHi < ltLo) {
735 mpush(lo, hi, d + 1);
736 continue;
737 }
738
739 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
740 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
741
742 n = lo + unLo - ltLo - 1;
743 m = hi - (gtHi - unHi) + 1;
744
745 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
746 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
747 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
748
749 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
750 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
751 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
752
753 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)");
754 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)");
755
756 mpush (nextLo[0], nextHi[0], nextD[0]);
757 mpush (nextLo[1], nextHi[1], nextD[1]);
758 mpush (nextLo[2], nextHi[2], nextD[2]);
759 }
760}
761
762#undef mswap
763#undef mvswap
764#undef mpush
765#undef mpop
766#undef mmin
767#undef mnextsize
768#undef mnextswap
769#undef MAIN_QSORT_SMALL_THRESH
770#undef MAIN_QSORT_DEPTH_THRESH
771#undef MAIN_QSORT_STACK_SIZE
772
773
774/*---------------------------------------------*/
775/* Pre:
776 * nblock > N_OVERSHOOT
777 * block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
778 * ((UChar*)block32) [0 .. nblock-1] holds block
779 * ptr exists for [0 .. nblock-1]
780 *
781 * Post:
782 * ((UChar*)block32) [0 .. nblock-1] holds block
783 * All other areas of block32 destroyed
784 * ftab[0 .. 65536] destroyed
785 * ptr [0 .. nblock-1] holds sorted order
786 * if (*budget < 0), sorting was abandoned
787 */
788
789#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
790#define SETMASK (1 << 21)
791#define CLEARMASK (~(SETMASK))
792
793static NOINLINE
794void mainSort(uint32_t* ptr,
795 UChar* block,
796 uint16_t* quadrant,
797 uint32_t* ftab,
798 int32_t nblock,
799 int32_t* budget)
800{
801 int32_t i, j, k, ss, sb;
802 int32_t runningOrder[256];
803 Bool bigDone[256];
804 int32_t copyStart[256];
805 int32_t copyEnd [256];
806 UChar c1;
807 int32_t numQSorted;
808 uint16_t s;
809
810 /*-- set up the 2-byte frequency table --*/
811 /* was: for (i = 65536; i >= 0; i--) ftab[i] = 0; */
812 memset(ftab, 0, 65537 * sizeof(ftab[0]));
813
814 j = block[0] << 8;
815 i = nblock-1;
816#if 0
817 for (; i >= 3; i -= 4) {
818 quadrant[i] = 0;
819 j = (j >> 8) |(((uint16_t)block[i]) << 8);
820 ftab[j]++;
821 quadrant[i-1] = 0;
822 j = (j >> 8) |(((uint16_t)block[i-1]) << 8);
823 ftab[j]++;
824 quadrant[i-2] = 0;
825 j = (j >> 8) |(((uint16_t)block[i-2]) << 8);
826 ftab[j]++;
827 quadrant[i-3] = 0;
828 j = (j >> 8) |(((uint16_t)block[i-3]) << 8);
829 ftab[j]++;
830 }
831#endif
832 for (; i >= 0; i--) {
833 quadrant[i] = 0;
834 j = (j >> 8) |(((uint16_t)block[i]) << 8);
835 ftab[j]++;
836 }
837
838 /*-- (emphasises close relationship of block & quadrant) --*/
839 for (i = 0; i < BZ_N_OVERSHOOT; i++) {
840 block [nblock+i] = block[i];
841 quadrant[nblock+i] = 0;
842 }
843
844 /*-- Complete the initial radix sort --*/
845 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
846
847 s = block[0] << 8;
848 i = nblock-1;
849#if 0
850 for (; i >= 3; i -= 4) {
851 s = (s >> 8) | (block[i] << 8);
852 j = ftab[s] -1;
853 ftab[s] = j;
854 ptr[j] = i;
855 s = (s >> 8) | (block[i-1] << 8);
856 j = ftab[s] -1;
857 ftab[s] = j;
858 ptr[j] = i-1;
859 s = (s >> 8) | (block[i-2] << 8);
860 j = ftab[s] -1;
861 ftab[s] = j;
862 ptr[j] = i-2;
863 s = (s >> 8) | (block[i-3] << 8);
864 j = ftab[s] -1;
865 ftab[s] = j;
866 ptr[j] = i-3;
867 }
868#endif
869 for (; i >= 0; i--) {
870 s = (s >> 8) | (block[i] << 8);
871 j = ftab[s] -1;
872 ftab[s] = j;
873 ptr[j] = i;
874 }
875
876 /*
877 * Now ftab contains the first loc of every small bucket.
878 * Calculate the running order, from smallest to largest
879 * big bucket.
880 */
881 for (i = 0; i <= 255; i++) {
882 bigDone [i] = False;
883 runningOrder[i] = i;
884 }
885
886 {
887 int32_t vv;
888 /* was: int32_t h = 1; */
889 /* do h = 3 * h + 1; while (h <= 256); */
890 int32_t h = 364;
891
892 do {
893 h = h / 3;
894 for (i = h; i <= 255; i++) {
895 vv = runningOrder[i];
896 j = i;
897 while (BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv)) {
898 runningOrder[j] = runningOrder[j-h];
899 j = j - h;
900 if (j <= (h - 1)) goto zero;
901 }
902 zero:
903 runningOrder[j] = vv;
904 }
905 } while (h != 1);
906 }
907
908 /*
909 * The main sorting loop.
910 */
911
912 numQSorted = 0;
913
914 for (i = 0; i <= 255; i++) {
915
916 /*
917 * Process big buckets, starting with the least full.
918 * Basically this is a 3-step process in which we call
919 * mainQSort3 to sort the small buckets [ss, j], but
920 * also make a big effort to avoid the calls if we can.
921 */
922 ss = runningOrder[i];
923
924 /*
925 * Step 1:
926 * Complete the big bucket [ss] by quicksorting
927 * any unsorted small buckets [ss, j], for j != ss.
928 * Hopefully previous pointer-scanning phases have already
929 * completed many of the small buckets [ss, j], so
930 * we don't have to sort them at all.
931 */
932 for (j = 0; j <= 255; j++) {
933 if (j != ss) {
934 sb = (ss << 8) + j;
935 if (!(ftab[sb] & SETMASK)) {
936 int32_t lo = ftab[sb] & CLEARMASK;
937 int32_t hi = (ftab[sb+1] & CLEARMASK) - 1;
938 if (hi > lo) {
939 mainQSort3 (
940 ptr, block, quadrant, nblock,
941 lo, hi, BZ_N_RADIX, budget
942 );
943 numQSorted += (hi - lo + 1);
944 if (*budget < 0) return;
945 }
946 }
947 ftab[sb] |= SETMASK;
948 }
949 }
950
951 AssertH(!bigDone[ss], 1006);
952
953 /*
954 * Step 2:
955 * Now scan this big bucket [ss] so as to synthesise the
956 * sorted order for small buckets [t, ss] for all t,
957 * including, magically, the bucket [ss,ss] too.
958 * This will avoid doing Real Work in subsequent Step 1's.
959 */
960 {
961 for (j = 0; j <= 255; j++) {
962 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
963 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
964 }
965 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
966 k = ptr[j] - 1;
967 if (k < 0)
968 k += nblock;
969 c1 = block[k];
970 if (!bigDone[c1])
971 ptr[copyStart[c1]++] = k;
972 }
973 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
974 k = ptr[j]-1;
975 if (k < 0)
976 k += nblock;
977 c1 = block[k];
978 if (!bigDone[c1])
979 ptr[copyEnd[c1]--] = k;
980 }
981 }
982
983 AssertH((copyStart[ss]-1 == copyEnd[ss])
984 ||
985 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
986 * Necessity for this case is demonstrated by compressing
987 * a sequence of approximately 48.5 million of character
988 * 251; 1.0.0/1.0.1 will then die here. */
989 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
990 1007)
991
992 for (j = 0; j <= 255; j++)
993 ftab[(j << 8) + ss] |= SETMASK;
994
995 /*
996 * Step 3:
997 * The [ss] big bucket is now done. Record this fact,
998 * and update the quadrant descriptors. Remember to
999 * update quadrants in the overshoot area too, if
1000 * necessary. The "if (i < 255)" test merely skips
1001 * this updating for the last bucket processed, since
1002 * updating for the last bucket is pointless.
1003 *
1004 * The quadrant array provides a way to incrementally
1005 * cache sort orderings, as they appear, so as to
1006 * make subsequent comparisons in fullGtU() complete
1007 * faster. For repetitive blocks this makes a big
1008 * difference (but not big enough to be able to avoid
1009 * the fallback sorting mechanism, exponential radix sort).
1010 *
1011 * The precise meaning is: at all times:
1012 *
1013 * for 0 <= i < nblock and 0 <= j <= nblock
1014 *
1015 * if block[i] != block[j],
1016 *
1017 * then the relative values of quadrant[i] and
1018 * quadrant[j] are meaningless.
1019 *
1020 * else {
1021 * if quadrant[i] < quadrant[j]
1022 * then the string starting at i lexicographically
1023 * precedes the string starting at j
1024 *
1025 * else if quadrant[i] > quadrant[j]
1026 * then the string starting at j lexicographically
1027 * precedes the string starting at i
1028 *
1029 * else
1030 * the relative ordering of the strings starting
1031 * at i and j has not yet been determined.
1032 * }
1033 */
1034 bigDone[ss] = True;
1035
1036 if (i < 255) {
1037 int32_t bbStart = ftab[ss << 8] & CLEARMASK;
1038 int32_t bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
1039 int32_t shifts = 0;
1040
1041 while ((bbSize >> shifts) > 65534) shifts++;
1042
1043 for (j = bbSize-1; j >= 0; j--) {
1044 int32_t a2update = ptr[bbStart + j];
1045 uint16_t qVal = (uint16_t)(j >> shifts);
1046 quadrant[a2update] = qVal;
1047 if (a2update < BZ_N_OVERSHOOT)
1048 quadrant[a2update + nblock] = qVal;
1049 }
1050 AssertH(((bbSize-1) >> shifts) <= 65535, 1002);
1051 }
1052
1053 }
1054}
1055
1056#undef BIGFREQ
1057#undef SETMASK
1058#undef CLEARMASK
1059
1060
1061/*---------------------------------------------*/
1062/* Pre:
1063 * nblock > 0
1064 * arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1065 * ((UChar*)arr2)[0 .. nblock-1] holds block
1066 * arr1 exists for [0 .. nblock-1]
1067 *
1068 * Post:
1069 * ((UChar*)arr2) [0 .. nblock-1] holds block
1070 * All other areas of block destroyed
1071 * ftab[0 .. 65536] destroyed
1072 * arr1[0 .. nblock-1] holds sorted order
1073 */
1074static NOINLINE
1075void BZ2_blockSort(EState* s)
1076{
1077 /* In original bzip2 1.0.4, it's a parameter, but 30
1078 * should work ok. */
1079 enum { wfact = 30 };
1080
1081 uint32_t* ptr = s->ptr;
1082 UChar* block = s->block;
1083 uint32_t* ftab = s->ftab;
1084 int32_t nblock = s->nblock;
1085 uint16_t* quadrant;
1086 int32_t budget;
1087 int32_t i;
1088
1089 if (nblock < 10000) {
1090 fallbackSort(s->arr1, s->arr2, ftab, nblock);
1091 } else {
1092 /* Calculate the location for quadrant, remembering to get
1093 * the alignment right. Assumes that &(block[0]) is at least
1094 * 2-byte aligned -- this should be ok since block is really
1095 * the first section of arr2.
1096 */
1097 i = nblock + BZ_N_OVERSHOOT;
1098 if (i & 1) i++;
1099 quadrant = (uint16_t*)(&(block[i]));
1100
1101 /* (wfact-1) / 3 puts the default-factor-30
1102 * transition point at very roughly the same place as
1103 * with v0.1 and v0.9.0.
1104 * Not that it particularly matters any more, since the
1105 * resulting compressed stream is now the same regardless
1106 * of whether or not we use the main sort or fallback sort.
1107 */
1108 budget = nblock * ((wfact-1) / 3);
1109
1110 mainSort(ptr, block, quadrant, ftab, nblock, &budget);
1111 if (budget < 0) {
1112 fallbackSort(s->arr1, s->arr2, ftab, nblock);
1113 }
1114 }
1115
1116 s->origPtr = -1;
1117 for (i = 0; i < s->nblock; i++)
1118 if (ptr[i] == 0) {
1119 s->origPtr = i; break;
1120 };
1121
1122 AssertH(s->origPtr != -1, 1003);
1123}
1124
1125
1126/*-------------------------------------------------------------*/
1127/*--- end blocksort.c ---*/
1128/*-------------------------------------------------------------*/
diff --git a/archival/bz/bzlib.c b/archival/bz/bzlib.c
new file mode 100644
index 000000000..3125bb0bf
--- /dev/null
+++ b/archival/bz/bzlib.c
@@ -0,0 +1,433 @@
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/*--- Library top-level functions. ---*/
9/*--- bzlib.c ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26/* CHANGES
27 * 0.9.0 -- original version.
28 * 0.9.0a/b -- no changes in this file.
29 * 0.9.0c -- made zero-length BZ_FLUSH work correctly in bzCompress().
30 * fixed bzWrite/bzRead to ignore zero-length requests.
31 * fixed bzread to correctly handle read requests after EOF.
32 * wrong parameter order in call to bzDecompressInit in
33 * bzBuffToBuffDecompress. Fixed.
34 */
35
36/* #include "bzlib_private.h" */
37
38/*---------------------------------------------------*/
39/*--- Compression stuff ---*/
40/*---------------------------------------------------*/
41
42/*---------------------------------------------------*/
43#ifndef BZ_NO_STDIO
44static void bz_assert_fail(int errcode)
45{
46 /* if (errcode == 1007) bb_error_msg_and_die("probably bad RAM"); */
47 bb_error_msg_and_die("bzip2 internal error %d", errcode);
48}
49#endif
50
51
52/*---------------------------------------------------*/
53static
54void prepare_new_block(EState* s)
55{
56 int32_t i;
57 s->nblock = 0;
58 s->numZ = 0;
59 s->state_out_pos = 0;
60 BZ_INITIALISE_CRC(s->blockCRC);
61 for (i = 0; i < 256; i++) s->inUse[i] = False;
62 s->blockNo++;
63}
64
65
66/*---------------------------------------------------*/
67static
68ALWAYS_INLINE
69void init_RL(EState* s)
70{
71 s->state_in_ch = 256;
72 s->state_in_len = 0;
73}
74
75
76static
77Bool isempty_RL(EState* s)
78{
79 if (s->state_in_ch < 256 && s->state_in_len > 0)
80 return False;
81 return True;
82}
83
84
85/*---------------------------------------------------*/
86static
87void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
88{
89 int32_t n;
90 EState* s;
91
92 s = xzalloc(sizeof(EState));
93 s->strm = strm;
94
95 n = 100000 * blockSize100k;
96 s->arr1 = xmalloc(n * sizeof(uint32_t));
97 s->mtfv = (uint16_t*)s->arr1;
98 s->ptr = (uint32_t*)s->arr1;
99 s->arr2 = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
100 s->block = (UChar*)s->arr2;
101 s->ftab = xmalloc(65537 * sizeof(uint32_t));
102
103 s->state = BZ_S_INPUT;
104 s->mode = BZ_M_RUNNING;
105 s->blockSize100k = blockSize100k;
106 s->nblockMAX = n - 19;
107
108 strm->state = s;
109 /*strm->total_in = 0;*/
110 strm->total_out = 0;
111 init_RL(s);
112 prepare_new_block(s);
113}
114
115
116/*---------------------------------------------------*/
117static
118void add_pair_to_block(EState* s)
119{
120 int32_t i;
121 UChar ch = (UChar)(s->state_in_ch);
122 for (i = 0; i < s->state_in_len; i++) {
123 BZ_UPDATE_CRC(s->blockCRC, ch);
124 }
125 s->inUse[s->state_in_ch] = True;
126 switch (s->state_in_len) {
127 case 1:
128 s->block[s->nblock] = (UChar)ch; s->nblock++;
129 break;
130 case 2:
131 s->block[s->nblock] = (UChar)ch; s->nblock++;
132 s->block[s->nblock] = (UChar)ch; s->nblock++;
133 break;
134 case 3:
135 s->block[s->nblock] = (UChar)ch; s->nblock++;
136 s->block[s->nblock] = (UChar)ch; s->nblock++;
137 s->block[s->nblock] = (UChar)ch; s->nblock++;
138 break;
139 default:
140 s->inUse[s->state_in_len-4] = True;
141 s->block[s->nblock] = (UChar)ch; s->nblock++;
142 s->block[s->nblock] = (UChar)ch; s->nblock++;
143 s->block[s->nblock] = (UChar)ch; s->nblock++;
144 s->block[s->nblock] = (UChar)ch; s->nblock++;
145 s->block[s->nblock] = ((UChar)(s->state_in_len-4));
146 s->nblock++;
147 break;
148 }
149}
150
151
152/*---------------------------------------------------*/
153static
154void flush_RL(EState* s)
155{
156 if (s->state_in_ch < 256) add_pair_to_block(s);
157 init_RL(s);
158}
159
160
161/*---------------------------------------------------*/
162#define ADD_CHAR_TO_BLOCK(zs, zchh0) \
163{ \
164 uint32_t zchh = (uint32_t)(zchh0); \
165 /*-- fast track the common case --*/ \
166 if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
167 UChar ch = (UChar)(zs->state_in_ch); \
168 BZ_UPDATE_CRC(zs->blockCRC, ch); \
169 zs->inUse[zs->state_in_ch] = True; \
170 zs->block[zs->nblock] = (UChar)ch; \
171 zs->nblock++; \
172 zs->state_in_ch = zchh; \
173 } \
174 else \
175 /*-- general, uncommon cases --*/ \
176 if (zchh != zs->state_in_ch || \
177 zs->state_in_len == 255) { \
178 if (zs->state_in_ch < 256) \
179 add_pair_to_block(zs); \
180 zs->state_in_ch = zchh; \
181 zs->state_in_len = 1; \
182 } else { \
183 zs->state_in_len++; \
184 } \
185}
186
187
188/*---------------------------------------------------*/
189static
190Bool copy_input_until_stop(EState* s)
191{
192 Bool progress_in = False;
193
194//vda: cannot simplify this until avail_in_expect is removed
195 if (s->mode == BZ_M_RUNNING) {
196 /*-- fast track the common case --*/
197 while (1) {
198 /*-- block full? --*/
199 if (s->nblock >= s->nblockMAX) break;
200 /*-- no input? --*/
201 if (s->strm->avail_in == 0) break;
202 progress_in = True;
203 ADD_CHAR_TO_BLOCK(s, (uint32_t)(*((UChar*)(s->strm->next_in))));
204 s->strm->next_in++;
205 s->strm->avail_in--;
206 /*s->strm->total_in++;*/
207 }
208 } else {
209 /*-- general, uncommon case --*/
210 while (1) {
211 /*-- block full? --*/
212 if (s->nblock >= s->nblockMAX) break;
213 /*-- no input? --*/
214 if (s->strm->avail_in == 0) break;
215 /*-- flush/finish end? --*/
216 if (s->avail_in_expect == 0) break;
217 progress_in = True;
218 ADD_CHAR_TO_BLOCK(s, (uint32_t)(*((UChar*)(s->strm->next_in))));
219 s->strm->next_in++;
220 s->strm->avail_in--;
221 /*s->strm->total_in++;*/
222 s->avail_in_expect--;
223 }
224 }
225 return progress_in;
226}
227
228
229/*---------------------------------------------------*/
230static
231Bool copy_output_until_stop(EState* s)
232{
233 Bool progress_out = False;
234
235 while (1) {
236
237 /*-- no output space? --*/
238 if (s->strm->avail_out == 0) break;
239
240 /*-- block done? --*/
241 if (s->state_out_pos >= s->numZ) break;
242
243 progress_out = True;
244 *(s->strm->next_out) = s->zbits[s->state_out_pos];
245 s->state_out_pos++;
246 s->strm->avail_out--;
247 s->strm->next_out++;
248 s->strm->total_out++;
249 }
250
251 return progress_out;
252}
253
254
255/*---------------------------------------------------*/
256static
257Bool handle_compress(bz_stream *strm)
258{
259 Bool progress_in = False;
260 Bool progress_out = False;
261 EState* s = strm->state;
262
263 while (1) {
264 if (s->state == BZ_S_OUTPUT) {
265 progress_out |= copy_output_until_stop(s);
266 if (s->state_out_pos < s->numZ) break;
267 if (s->mode == BZ_M_FINISHING
268 && s->avail_in_expect == 0
269 && isempty_RL(s))
270 break;
271 prepare_new_block(s);
272 s->state = BZ_S_INPUT;
273 if (s->mode == BZ_M_FLUSHING
274 && s->avail_in_expect == 0
275 && isempty_RL(s))
276 break;
277 }
278
279 if (s->state == BZ_S_INPUT) {
280 progress_in |= copy_input_until_stop(s);
281 if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
282 flush_RL(s);
283 BZ2_compressBlock(s, (Bool)(s->mode == BZ_M_FINISHING));
284 s->state = BZ_S_OUTPUT;
285 } else
286 if (s->nblock >= s->nblockMAX) {
287 BZ2_compressBlock(s, False);
288 s->state = BZ_S_OUTPUT;
289 } else
290 if (s->strm->avail_in == 0) {
291 break;
292 }
293 }
294
295 }
296
297 return progress_in || progress_out;
298}
299
300
301/*---------------------------------------------------*/
302static
303int BZ2_bzCompress(bz_stream *strm, int action)
304{
305 Bool progress;
306 EState* s;
307 if (strm == NULL) return BZ_PARAM_ERROR;
308 s = strm->state;
309 if (s == NULL) return BZ_PARAM_ERROR;
310 if (s->strm != strm) return BZ_PARAM_ERROR;
311
312 preswitch:
313 switch (s->mode) {
314
315 case BZ_M_IDLE:
316 return BZ_SEQUENCE_ERROR;
317
318 case BZ_M_RUNNING:
319 if (action == BZ_RUN) {
320 progress = handle_compress(strm);
321 return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;
322 }
323 else
324 if (action == BZ_FLUSH) {
325 s->avail_in_expect = strm->avail_in;
326 s->mode = BZ_M_FLUSHING;
327 goto preswitch;
328 }
329 else
330 if (action == BZ_FINISH) {
331 s->avail_in_expect = strm->avail_in;
332 s->mode = BZ_M_FINISHING;
333 goto preswitch;
334 }
335 else
336 return BZ_PARAM_ERROR;
337
338 case BZ_M_FLUSHING:
339 if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR;
340 if (s->avail_in_expect != s->strm->avail_in)
341 return BZ_SEQUENCE_ERROR;
342 progress = handle_compress(strm);
343 if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
344 return BZ_FLUSH_OK;
345 s->mode = BZ_M_RUNNING;
346 return BZ_RUN_OK;
347
348 case BZ_M_FINISHING:
349 if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR;
350 if (s->avail_in_expect != s->strm->avail_in)
351 return BZ_SEQUENCE_ERROR;
352 progress = handle_compress(strm);
353 if (!progress) return BZ_SEQUENCE_ERROR;
354 if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
355 return BZ_FINISH_OK;
356 s->mode = BZ_M_IDLE;
357 return BZ_STREAM_END;
358 }
359 return BZ_OK; /*--not reached--*/
360}
361
362
363/*---------------------------------------------------*/
364static
365int BZ2_bzCompressEnd(bz_stream *strm)
366{
367 EState* s;
368 if (strm == NULL) return BZ_PARAM_ERROR;
369 s = strm->state;
370 if (s == NULL) return BZ_PARAM_ERROR;
371 if (s->strm != strm) return BZ_PARAM_ERROR;
372
373 if (s->arr1 != NULL) free(s->arr1);
374 if (s->arr2 != NULL) free(s->arr2);
375 if (s->ftab != NULL) free(s->ftab);
376 free(strm->state);
377
378 strm->state = NULL;
379
380 return BZ_OK;
381}
382
383
384/*---------------------------------------------------*/
385/*--- Misc convenience stuff ---*/
386/*---------------------------------------------------*/
387
388/*---------------------------------------------------*/
389#ifdef EXAMPLE_CODE_FOR_MEM_TO_MEM_COMPRESSION
390static
391int BZ2_bzBuffToBuffCompress(char* dest,
392 unsigned int* destLen,
393 char* source,
394 unsigned int sourceLen,
395 int blockSize100k)
396{
397 bz_stream strm;
398 int ret;
399
400 if (dest == NULL || destLen == NULL ||
401 source == NULL ||
402 blockSize100k < 1 || blockSize100k > 9)
403 return BZ_PARAM_ERROR;
404
405 BZ2_bzCompressInit(&strm, blockSize100k);
406
407 strm.next_in = source;
408 strm.next_out = dest;
409 strm.avail_in = sourceLen;
410 strm.avail_out = *destLen;
411
412 ret = BZ2_bzCompress(&strm, BZ_FINISH);
413 if (ret == BZ_FINISH_OK) goto output_overflow;
414 if (ret != BZ_STREAM_END) goto errhandler;
415
416 /* normal termination */
417 *destLen -= strm.avail_out;
418 BZ2_bzCompressEnd(&strm);
419 return BZ_OK;
420
421 output_overflow:
422 BZ2_bzCompressEnd(&strm);
423 return BZ_OUTBUFF_FULL;
424
425 errhandler:
426 BZ2_bzCompressEnd(&strm);
427 return ret;
428}
429#endif
430
431/*-------------------------------------------------------------*/
432/*--- end bzlib.c ---*/
433/*-------------------------------------------------------------*/
diff --git a/archival/bz/bzlib.h b/archival/bz/bzlib.h
new file mode 100644
index 000000000..805e9b328
--- /dev/null
+++ b/archival/bz/bzlib.h
@@ -0,0 +1,63 @@
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/*--- Public header file for the library. ---*/
9/*--- bzlib.h ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26#define BZ_RUN 0
27#define BZ_FLUSH 1
28#define BZ_FINISH 2
29
30#define BZ_OK 0
31#define BZ_RUN_OK 1
32#define BZ_FLUSH_OK 2
33#define BZ_FINISH_OK 3
34#define BZ_STREAM_END 4
35#define BZ_SEQUENCE_ERROR (-1)
36#define BZ_PARAM_ERROR (-2)
37#define BZ_MEM_ERROR (-3)
38#define BZ_DATA_ERROR (-4)
39#define BZ_DATA_ERROR_MAGIC (-5)
40#define BZ_IO_ERROR (-6)
41#define BZ_UNEXPECTED_EOF (-7)
42#define BZ_OUTBUFF_FULL (-8)
43#define BZ_CONFIG_ERROR (-9)
44
45typedef struct bz_stream {
46 char *next_in;
47 char *next_out;
48 unsigned avail_in;
49 unsigned avail_out;
50 /*unsigned long long total_in;*/
51 unsigned long long total_out;
52 void *state;
53} bz_stream;
54
55/*-- Core (low-level) library functions --*/
56
57static void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k);
58static int BZ2_bzCompress(bz_stream *strm, int action);
59static int BZ2_bzCompressEnd(bz_stream *strm);
60
61/*-------------------------------------------------------------*/
62/*--- end bzlib.h ---*/
63/*-------------------------------------------------------------*/
diff --git a/archival/bz/bzlib_private.h b/archival/bz/bzlib_private.h
new file mode 100644
index 000000000..24ffbee9c
--- /dev/null
+++ b/archival/bz/bzlib_private.h
@@ -0,0 +1,234 @@
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/*--- Private header file for the library. ---*/
9/*--- bzlib_private.h ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26/* #include "bzlib.h" */
27
28#define BZ_DEBUG 0
29//#define BZ_NO_STDIO 1 - does not work
30
31
32/*-- General stuff. --*/
33
34typedef unsigned char Bool;
35typedef unsigned char UChar;
36
37#define True ((Bool)1)
38#define False ((Bool)0)
39
40static void bz_assert_fail(int errcode) ATTRIBUTE_NORETURN;
41#define AssertH(cond, errcode) \
42{ \
43 if (!(cond)) \
44 bz_assert_fail(errcode); \
45}
46
47#if BZ_DEBUG
48#define AssertD(cond, msg) \
49{ \
50 if (!(cond)) \
51 bb_error_msg_and_die("(debug build): internal error %s", msg); \
52}
53#else
54#define AssertD(cond, msg) do { } while (0)
55#endif
56
57
58/*-- Header bytes. --*/
59
60#define BZ_HDR_B 0x42 /* 'B' */
61#define BZ_HDR_Z 0x5a /* 'Z' */
62#define BZ_HDR_h 0x68 /* 'h' */
63#define BZ_HDR_0 0x30 /* '0' */
64
65#define BZ_HDR_BZh0 0x425a6830
66
67/*-- Constants for the back end. --*/
68
69#define BZ_MAX_ALPHA_SIZE 258
70#define BZ_MAX_CODE_LEN 23
71
72#define BZ_RUNA 0
73#define BZ_RUNB 1
74
75#define BZ_N_GROUPS 6
76#define BZ_G_SIZE 50
77#define BZ_N_ITERS 4
78
79#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
80
81
82/*-- Stuff for randomising repetitive blocks. --*/
83
84static const int32_t BZ2_rNums[512];
85
86#define BZ_RAND_DECLS \
87 int32_t rNToGo; \
88 int32_t rTPos \
89
90#define BZ_RAND_INIT_MASK \
91 s->rNToGo = 0; \
92 s->rTPos = 0 \
93
94#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
95
96#define BZ_RAND_UPD_MASK \
97{ \
98 if (s->rNToGo == 0) { \
99 s->rNToGo = BZ2_rNums[s->rTPos]; \
100 s->rTPos++; \
101 if (s->rTPos == 512) s->rTPos = 0; \
102 } \
103 s->rNToGo--; \
104}
105
106
107/*-- Stuff for doing CRCs. --*/
108
109static const uint32_t BZ2_crc32Table[256];
110
111#define BZ_INITIALISE_CRC(crcVar) \
112{ \
113 crcVar = 0xffffffffL; \
114}
115
116#define BZ_FINALISE_CRC(crcVar) \
117{ \
118 crcVar = ~(crcVar); \
119}
120
121#define BZ_UPDATE_CRC(crcVar,cha) \
122{ \
123 crcVar = (crcVar << 8) ^ BZ2_crc32Table[(crcVar >> 24) ^ ((UChar)cha)]; \
124}
125
126
127/*-- States and modes for compression. --*/
128
129#define BZ_M_IDLE 1
130#define BZ_M_RUNNING 2
131#define BZ_M_FLUSHING 3
132#define BZ_M_FINISHING 4
133
134#define BZ_S_OUTPUT 1
135#define BZ_S_INPUT 2
136
137#define BZ_N_RADIX 2
138#define BZ_N_QSORT 12
139#define BZ_N_SHELL 18
140#define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
141
142
143/*-- Structure holding all the compression-side stuff. --*/
144
145typedef struct EState {
146 /* pointer back to the struct bz_stream */
147 bz_stream *strm;
148
149 /* mode this stream is in, and whether inputting */
150 /* or outputting data */
151 int32_t mode;
152 int32_t state;
153
154 /* remembers avail_in when flush/finish requested */
155 uint32_t avail_in_expect; //vda: do we need this?
156
157 /* for doing the block sorting */
158 uint32_t *arr1;
159 uint32_t *arr2;
160 uint32_t *ftab;
161 int32_t origPtr;
162
163 /* aliases for arr1 and arr2 */
164 uint32_t *ptr;
165 UChar *block;
166 uint16_t *mtfv;
167 UChar *zbits;
168
169 /* run-length-encoding of the input */
170 uint32_t state_in_ch;
171 int32_t state_in_len;
172 BZ_RAND_DECLS;
173
174 /* input and output limits and current posns */
175 int32_t nblock;
176 int32_t nblockMAX;
177 int32_t numZ;
178 int32_t state_out_pos;
179
180 /* the buffer for bit stream creation */
181 uint32_t bsBuff;
182 int32_t bsLive;
183
184 /* block and combined CRCs */
185 uint32_t blockCRC;
186 uint32_t combinedCRC;
187
188 /* misc administratium */
189 int32_t blockNo;
190 int32_t blockSize100k;
191
192 /* stuff for coding the MTF values */
193 int32_t nMTF;
194
195 /* map of bytes used in block */
196 int32_t nInUse;
197 Bool inUse[256];
198 UChar unseqToSeq[256];
199
200 /* stuff for coding the MTF values */
201 int32_t mtfFreq [BZ_MAX_ALPHA_SIZE];
202 UChar selector [BZ_MAX_SELECTORS];
203 UChar selectorMtf[BZ_MAX_SELECTORS];
204
205 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
206 int32_t code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
207 int32_t rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
208#ifdef FAST_GROUP6
209 /* second dimension: only 3 needed; 4 makes index calculations faster */
210 uint32_t len_pack[BZ_MAX_ALPHA_SIZE][4];
211#endif
212} EState;
213
214
215/*-- compression. --*/
216
217static void
218BZ2_blockSort(EState*);
219
220static void
221BZ2_compressBlock(EState*, Bool);
222
223static void
224BZ2_bsInitWrite(EState*);
225
226static void
227BZ2_hbAssignCodes(int32_t*, UChar*, int32_t, int32_t, int32_t);
228
229static void
230BZ2_hbMakeCodeLengths(UChar*, int32_t*, int32_t, int32_t);
231
232/*-------------------------------------------------------------*/
233/*--- end bzlib_private.h ---*/
234/*-------------------------------------------------------------*/
diff --git a/archival/bz/compress.c b/archival/bz/compress.c
new file mode 100644
index 000000000..54426dcc7
--- /dev/null
+++ b/archival/bz/compress.c
@@ -0,0 +1,671 @@
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/*--- Compression machinery (not incl block sorting) ---*/
9/*--- compress.c ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26/* CHANGES
27 * 0.9.0 -- original version.
28 * 0.9.0a/b -- no changes in this file.
29 * 0.9.0c -- changed setting of nGroups in sendMTFValues()
30 * so as to do a bit better on small files
31*/
32
33/* #include "bzlib_private.h" */
34
35/*---------------------------------------------------*/
36/*--- Bit stream I/O ---*/
37/*---------------------------------------------------*/
38
39/*---------------------------------------------------*/
40static
41void BZ2_bsInitWrite(EState* s)
42{
43 s->bsLive = 0;
44 s->bsBuff = 0;
45}
46
47
48/*---------------------------------------------------*/
49static NOINLINE
50void bsFinishWrite(EState* s)
51{
52 while (s->bsLive > 0) {
53 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
54 s->numZ++;
55 s->bsBuff <<= 8;
56 s->bsLive -= 8;
57 }
58}
59
60
61/*---------------------------------------------------*/
62static
63/* Forced inlining results in +600 bytes code,
64 * 2% faster compression. Not worth it. */
65/*ALWAYS_INLINE*/
66void bsW(EState* s, int32_t n, uint32_t v)
67{
68 while (s->bsLive >= 8) {
69 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
70 s->numZ++;
71 s->bsBuff <<= 8;
72 s->bsLive -= 8;
73 }
74 s->bsBuff |= (v << (32 - s->bsLive - n));
75 s->bsLive += n;
76}
77
78
79/*---------------------------------------------------*/
80static
81void bsPutU32(EState* s, uint32_t u)
82{
83 bsW(s, 8, (u >> 24) & 0xff);
84 bsW(s, 8, (u >> 16) & 0xff);
85 bsW(s, 8, (u >> 8) & 0xff);
86 bsW(s, 8, u & 0xff);
87}
88
89
90/*---------------------------------------------------*/
91static
92void bsPutUChar(EState* s, UChar c)
93{
94 bsW(s, 8, (uint32_t)c);
95}
96
97
98/*---------------------------------------------------*/
99/*--- The back end proper ---*/
100/*---------------------------------------------------*/
101
102/*---------------------------------------------------*/
103static
104void makeMaps_e(EState* s)
105{
106 int32_t i;
107 s->nInUse = 0;
108 for (i = 0; i < 256; i++) {
109 if (s->inUse[i]) {
110 s->unseqToSeq[i] = s->nInUse;
111 s->nInUse++;
112 }
113 }
114}
115
116
117/*---------------------------------------------------*/
118static NOINLINE
119void generateMTFValues(EState* s)
120{
121 UChar yy[256];
122 int32_t i, j;
123 int32_t zPend;
124 int32_t wr;
125 int32_t EOB;
126
127 /*
128 * After sorting (eg, here),
129 * s->arr1[0 .. s->nblock-1] holds sorted order,
130 * and
131 * ((UChar*)s->arr2)[0 .. s->nblock-1]
132 * holds the original block data.
133 *
134 * The first thing to do is generate the MTF values,
135 * and put them in
136 * ((uint16_t*)s->arr1)[0 .. s->nblock-1].
137 * Because there are strictly fewer or equal MTF values
138 * than block values, ptr values in this area are overwritten
139 * with MTF values only when they are no longer needed.
140 *
141 * The final compressed bitstream is generated into the
142 * area starting at
143 * (UChar*) (&((UChar*)s->arr2)[s->nblock])
144 *
145 * These storage aliases are set up in bzCompressInit(),
146 * except for the last one, which is arranged in
147 * compressBlock().
148 */
149 uint32_t* ptr = s->ptr;
150 UChar* block = s->block;
151 uint16_t* mtfv = s->mtfv;
152
153 makeMaps_e(s);
154 EOB = s->nInUse+1;
155
156 for (i = 0; i <= EOB; i++)
157 s->mtfFreq[i] = 0;
158
159 wr = 0;
160 zPend = 0;
161 for (i = 0; i < s->nInUse; i++)
162 yy[i] = (UChar) i;
163
164 for (i = 0; i < s->nblock; i++) {
165 UChar ll_i;
166 AssertD(wr <= i, "generateMTFValues(1)");
167 j = ptr[i]-1;
168 if (j < 0)
169 j += s->nblock;
170 ll_i = s->unseqToSeq[block[j]];
171 AssertD(ll_i < s->nInUse, "generateMTFValues(2a)");
172
173 if (yy[0] == ll_i) {
174 zPend++;
175 } else {
176 if (zPend > 0) {
177 zPend--;
178 while (1) {
179 if (zPend & 1) {
180 mtfv[wr] = BZ_RUNB; wr++;
181 s->mtfFreq[BZ_RUNB]++;
182 } else {
183 mtfv[wr] = BZ_RUNA; wr++;
184 s->mtfFreq[BZ_RUNA]++;
185 }
186 if (zPend < 2) break;
187 zPend = (zPend - 2) / 2;
188 };
189 zPend = 0;
190 }
191 {
192 register UChar rtmp;
193 register UChar* ryy_j;
194 register UChar rll_i;
195 rtmp = yy[1];
196 yy[1] = yy[0];
197 ryy_j = &(yy[1]);
198 rll_i = ll_i;
199 while (rll_i != rtmp) {
200 register UChar rtmp2;
201 ryy_j++;
202 rtmp2 = rtmp;
203 rtmp = *ryy_j;
204 *ryy_j = rtmp2;
205 };
206 yy[0] = rtmp;
207 j = ryy_j - &(yy[0]);
208 mtfv[wr] = j+1;
209 wr++;
210 s->mtfFreq[j+1]++;
211 }
212
213 }
214 }
215
216 if (zPend > 0) {
217 zPend--;
218 while (1) {
219 if (zPend & 1) {
220 mtfv[wr] = BZ_RUNB; wr++;
221 s->mtfFreq[BZ_RUNB]++;
222 } else {
223 mtfv[wr] = BZ_RUNA; wr++;
224 s->mtfFreq[BZ_RUNA]++;
225 }
226 if (zPend < 2)
227 break;
228 zPend = (zPend - 2) / 2;
229 };
230 zPend = 0;
231 }
232
233 mtfv[wr] = EOB;
234 wr++;
235 s->mtfFreq[EOB]++;
236
237 s->nMTF = wr;
238}
239
240
241/*---------------------------------------------------*/
242#define BZ_LESSER_ICOST 0
243#define BZ_GREATER_ICOST 15
244
245static NOINLINE
246void sendMTFValues(EState* s)
247{
248 int32_t v, t, i, j, gs, ge, totc, bt, bc, iter;
249 int32_t nSelectors, alphaSize, minLen, maxLen, selCtr;
250 int32_t nGroups, nBytes;
251
252 /*
253 * UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
254 * is a global since the decoder also needs it.
255 *
256 * int32_t code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
257 * int32_t rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
258 * are also globals only used in this proc.
259 * Made global to keep stack frame size small.
260 */
261
262 uint16_t cost[BZ_N_GROUPS];
263 int32_t fave[BZ_N_GROUPS];
264
265 uint16_t* mtfv = s->mtfv;
266
267 alphaSize = s->nInUse+2;
268 for (t = 0; t < BZ_N_GROUPS; t++)
269 for (v = 0; v < alphaSize; v++)
270 s->len[t][v] = BZ_GREATER_ICOST;
271
272 /*--- Decide how many coding tables to use ---*/
273 AssertH(s->nMTF > 0, 3001);
274 if (s->nMTF < 200) nGroups = 2; else
275 if (s->nMTF < 600) nGroups = 3; else
276 if (s->nMTF < 1200) nGroups = 4; else
277 if (s->nMTF < 2400) nGroups = 5; else
278 nGroups = 6;
279
280 /*--- Generate an initial set of coding tables ---*/
281 {
282 int32_t nPart, remF, tFreq, aFreq;
283
284 nPart = nGroups;
285 remF = s->nMTF;
286 gs = 0;
287 while (nPart > 0) {
288 tFreq = remF / nPart;
289 ge = gs-1;
290 aFreq = 0;
291 while (aFreq < tFreq && ge < alphaSize-1) {
292 ge++;
293 aFreq += s->mtfFreq[ge];
294 }
295
296 if (ge > gs
297 && nPart != nGroups && nPart != 1
298 && ((nGroups-nPart) % 2 == 1)
299 ) {
300 aFreq -= s->mtfFreq[ge];
301 ge--;
302 }
303
304 for (v = 0; v < alphaSize; v++)
305 if (v >= gs && v <= ge)
306 s->len[nPart-1][v] = BZ_LESSER_ICOST;
307 else
308 s->len[nPart-1][v] = BZ_GREATER_ICOST;
309
310 nPart--;
311 gs = ge+1;
312 remF -= aFreq;
313 }
314 }
315
316 /*
317 * Iterate up to BZ_N_ITERS times to improve the tables.
318 */
319 for (iter = 0; iter < BZ_N_ITERS; iter++) {
320 for (t = 0; t < nGroups; t++)
321 fave[t] = 0;
322
323 for (t = 0; t < nGroups; t++)
324 for (v = 0; v < alphaSize; v++)
325 s->rfreq[t][v] = 0;
326
327#ifdef FAST_GROUP6
328 /*
329 * Set up an auxiliary length table which is used to fast-track
330 * the common case (nGroups == 6).
331 */
332 if (nGroups == 6) {
333 for (v = 0; v < alphaSize; v++) {
334 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
335 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
336 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
337 }
338 }
339#endif
340
341 nSelectors = 0;
342 totc = 0;
343 gs = 0;
344 while (1) {
345 /*--- Set group start & end marks. --*/
346 if (gs >= s->nMTF)
347 break;
348 ge = gs + BZ_G_SIZE - 1;
349 if (ge >= s->nMTF)
350 ge = s->nMTF-1;
351
352 /*
353 * Calculate the cost of this group as coded
354 * by each of the coding tables.
355 */
356 for (t = 0; t < nGroups; t++)
357 cost[t] = 0;
358#ifdef FAST_GROUP6
359 if (nGroups == 6 && 50 == ge-gs+1) {
360 /*--- fast track the common case ---*/
361 register uint32_t cost01, cost23, cost45;
362 register uint16_t icv;
363 cost01 = cost23 = cost45 = 0;
364#define BZ_ITER(nn) \
365 icv = mtfv[gs+(nn)]; \
366 cost01 += s->len_pack[icv][0]; \
367 cost23 += s->len_pack[icv][1]; \
368 cost45 += s->len_pack[icv][2];
369 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
370 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
371 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
372 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
373 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
374 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
375 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
376 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
377 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
378 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
379#undef BZ_ITER
380 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
381 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
382 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
383
384 } else
385#endif
386 {
387 /*--- slow version which correctly handles all situations ---*/
388 for (i = gs; i <= ge; i++) {
389 uint16_t icv = mtfv[i];
390 for (t = 0; t < nGroups; t++)
391 cost[t] += s->len[t][icv];
392 }
393 }
394 /*
395 * Find the coding table which is best for this group,
396 * and record its identity in the selector table.
397 */
398 bc = 999999999;
399 bt = -1;
400 //bc = cost[0];
401 //bt = 0;
402 for (t = 0; t < nGroups; t++) {
403 if (cost[t] < bc) {
404 bc = cost[t];
405 bt = t;
406 }
407 }
408 totc += bc;
409 fave[bt]++;
410 s->selector[nSelectors] = bt;
411 nSelectors++;
412
413 /*
414 * Increment the symbol frequencies for the selected table.
415 */
416/* ~0.5% faster compress. +800 bytes */
417#if 0
418 if (nGroups == 6 && 50 == ge-gs+1) {
419 /*--- fast track the common case ---*/
420#define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
421 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
422 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
423 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
424 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
425 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
426 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
427 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
428 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
429 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
430 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
431#undef BZ_ITUR
432 gs = ge+1;
433 } else
434#endif
435 {
436 /*--- slow version which correctly handles all situations ---*/
437 while (gs <= ge) {
438 s->rfreq[bt][mtfv[gs]]++;
439 gs++;
440 }
441 /* already is: gs = ge+1; */
442 }
443 }
444
445 /*
446 * Recompute the tables based on the accumulated frequencies.
447 */
448 /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
449 * comment in huffman.c for details. */
450 for (t = 0; t < nGroups; t++)
451 BZ2_hbMakeCodeLengths(&(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /*20*/);
452 }
453
454 AssertH(nGroups < 8, 3002);
455 AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003);
456
457 /*--- Compute MTF values for the selectors. ---*/
458 {
459 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
460
461 for (i = 0; i < nGroups; i++)
462 pos[i] = i;
463 for (i = 0; i < nSelectors; i++) {
464 ll_i = s->selector[i];
465 j = 0;
466 tmp = pos[j];
467 while (ll_i != tmp) {
468 j++;
469 tmp2 = tmp;
470 tmp = pos[j];
471 pos[j] = tmp2;
472 };
473 pos[0] = tmp;
474 s->selectorMtf[i] = j;
475 }
476 };
477
478 /*--- Assign actual codes for the tables. --*/
479 for (t = 0; t < nGroups; t++) {
480 minLen = 32;
481 maxLen = 0;
482 for (i = 0; i < alphaSize; i++) {
483 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
484 if (s->len[t][i] < minLen) minLen = s->len[t][i];
485 }
486 AssertH(!(maxLen > 17 /*20*/), 3004);
487 AssertH(!(minLen < 1), 3005);
488 BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize);
489 }
490
491 /*--- Transmit the mapping table. ---*/
492 {
493 Bool inUse16[16];
494 for (i = 0; i < 16; i++) {
495 inUse16[i] = False;
496 for (j = 0; j < 16; j++)
497 if (s->inUse[i * 16 + j])
498 inUse16[i] = True;
499 }
500
501 nBytes = s->numZ;
502 for (i = 0; i < 16; i++) {
503 if (inUse16[i])
504 bsW(s, 1, 1);
505 else
506 bsW(s, 1, 0);
507 }
508
509 for (i = 0; i < 16; i++) {
510 if (inUse16[i]) {
511 for (j = 0; j < 16; j++) {
512 if (s->inUse[i * 16 + j])
513 bsW(s, 1, 1);
514 else
515 bsW(s, 1, 0);
516 }
517 }
518 }
519 }
520
521 /*--- Now the selectors. ---*/
522 nBytes = s->numZ;
523 bsW(s, 3, nGroups);
524 bsW(s, 15, nSelectors);
525 for (i = 0; i < nSelectors; i++) {
526 for (j = 0; j < s->selectorMtf[i]; j++)
527 bsW(s, 1, 1);
528 bsW(s, 1, 0);
529 }
530
531 /*--- Now the coding tables. ---*/
532 nBytes = s->numZ;
533
534 for (t = 0; t < nGroups; t++) {
535 int32_t curr = s->len[t][0];
536 bsW(s, 5, curr);
537 for (i = 0; i < alphaSize; i++) {
538 while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ };
539 while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ };
540 bsW(s, 1, 0);
541 }
542 }
543
544 /*--- And finally, the block data proper ---*/
545 nBytes = s->numZ;
546 selCtr = 0;
547 gs = 0;
548 while (1) {
549 if (gs >= s->nMTF)
550 break;
551 ge = gs + BZ_G_SIZE - 1;
552 if (ge >= s->nMTF)
553 ge = s->nMTF-1;
554 AssertH(s->selector[selCtr] < nGroups, 3006);
555
556/* Costs 1300 bytes and is _slower_ (on Intel Core 2) */
557#if 0
558 if (nGroups == 6 && 50 == ge-gs+1) {
559 /*--- fast track the common case ---*/
560 uint16_t mtfv_i;
561 UChar* s_len_sel_selCtr = &(s->len[s->selector[selCtr]][0]);
562 int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
563#define BZ_ITAH(nn) \
564 mtfv_i = mtfv[gs+(nn)]; \
565 bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i])
566 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
567 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
568 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
569 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
570 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
571 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
572 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
573 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
574 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
575 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
576#undef BZ_ITAH
577 gs = ge+1;
578 } else
579#endif
580 {
581 /*--- slow version which correctly handles all situations ---*/
582 /* code is bit bigger, but moves multiply out of the loop */
583 UChar* s_len_sel_selCtr = &(s->len [s->selector[selCtr]][0]);
584 int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
585 while (gs <= ge) {
586 bsW(s,
587 s_len_sel_selCtr[mtfv[gs]],
588 s_code_sel_selCtr[mtfv[gs]]
589 );
590 gs++;
591 }
592 /* already is: gs = ge+1; */
593 }
594 selCtr++;
595 }
596 AssertH(selCtr == nSelectors, 3007);
597}
598
599
600/*---------------------------------------------------*/
601static
602void BZ2_compressBlock(EState* s, Bool is_last_block)
603{
604 if (s->nblock > 0) {
605 BZ_FINALISE_CRC(s->blockCRC);
606 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
607 s->combinedCRC ^= s->blockCRC;
608 if (s->blockNo > 1)
609 s->numZ = 0;
610
611 BZ2_blockSort(s);
612 }
613
614 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
615
616 /*-- If this is the first block, create the stream header. --*/
617 if (s->blockNo == 1) {
618 BZ2_bsInitWrite(s);
619 /*bsPutUChar(s, BZ_HDR_B);*/
620 /*bsPutUChar(s, BZ_HDR_Z);*/
621 /*bsPutUChar(s, BZ_HDR_h);*/
622 /*bsPutUChar(s, (UChar)(BZ_HDR_0 + s->blockSize100k));*/
623 bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k);
624 }
625
626 if (s->nblock > 0) {
627 /*bsPutUChar(s, 0x31);*/
628 /*bsPutUChar(s, 0x41);*/
629 /*bsPutUChar(s, 0x59);*/
630 /*bsPutUChar(s, 0x26);*/
631 bsPutU32(s, 0x31415926);
632 bsPutUChar(s, 0x53);
633 bsPutUChar(s, 0x59);
634
635 /*-- Now the block's CRC, so it is in a known place. --*/
636 bsPutU32(s, s->blockCRC);
637
638 /*
639 * Now a single bit indicating (non-)randomisation.
640 * As of version 0.9.5, we use a better sorting algorithm
641 * which makes randomisation unnecessary. So always set
642 * the randomised bit to 'no'. Of course, the decoder
643 * still needs to be able to handle randomised blocks
644 * so as to maintain backwards compatibility with
645 * older versions of bzip2.
646 */
647 bsW(s, 1, 0);
648
649 bsW(s, 24, s->origPtr);
650 generateMTFValues(s);
651 sendMTFValues(s);
652 }
653
654 /*-- If this is the last block, add the stream trailer. --*/
655 if (is_last_block) {
656 /*bsPutUChar(s, 0x17);*/
657 /*bsPutUChar(s, 0x72);*/
658 /*bsPutUChar(s, 0x45);*/
659 /*bsPutUChar(s, 0x38);*/
660 bsPutU32(s, 0x17724538);
661 bsPutUChar(s, 0x50);
662 bsPutUChar(s, 0x90);
663 bsPutU32(s, s->combinedCRC);
664 bsFinishWrite(s);
665 }
666}
667
668
669/*-------------------------------------------------------------*/
670/*--- end compress.c ---*/
671/*-------------------------------------------------------------*/
diff --git a/archival/bz/crctable.c b/archival/bz/crctable.c
new file mode 100644
index 000000000..dadd372d3
--- /dev/null
+++ b/archival/bz/crctable.c
@@ -0,0 +1,105 @@
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/*--- Table for doing CRCs ---*/
9/*--- crctable.c ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26/* #include "bzlib_private.h" */
27
28/*
29 * I think this is an implementation of the AUTODIN-II,
30 * Ethernet & FDDI 32-bit CRC standard. Vaguely derived
31 * from code by Rob Warnock, in Section 51 of the
32 * comp.compression FAQ.
33 */
34
35static const uint32_t BZ2_crc32Table[256] = {
36 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
37 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
38 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
39 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
40 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
41 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
42 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
43 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
44 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
45 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
46 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
47 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
48 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
49 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
50 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
51 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
52 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
53 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
54 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
55 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
56 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
57 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
58 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
59 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
60 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
61 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
62 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
63 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
64 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
65 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
66 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
67 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
68 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
69 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
70 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
71 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
72 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
73 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
74 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
75 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
76 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
77 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
78 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
79 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
80 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
81 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
82 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
83 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
84 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
85 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
86 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
87 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
88 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
89 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
90 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
91 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
92 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
93 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
94 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
95 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
96 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
97 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
98 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
99 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
100};
101
102
103/*-------------------------------------------------------------*/
104/*--- end crctable.c ---*/
105/*-------------------------------------------------------------*/
diff --git a/archival/bz/huffman.c b/archival/bz/huffman.c
new file mode 100644
index 000000000..d01af11c2
--- /dev/null
+++ b/archival/bz/huffman.c
@@ -0,0 +1,188 @@
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/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in 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#define DOWNHEAP(z) \
50{ \
51 int32_t zz, yy, tmp; \
52 zz = z; tmp = heap[zz]; \
53 while (1) { \
54 yy = zz << 1; \
55 if (yy > nHeap) \
56 break; \
57 if (yy < nHeap \
58 && weight[heap[yy+1]] < weight[heap[yy]]) \
59 yy++; \
60 if (weight[tmp] < weight[heap[yy]]) \
61 break; \
62 heap[zz] = heap[yy]; \
63 zz = yy; \
64 } \
65 heap[zz] = tmp; \
66}
67
68
69/*---------------------------------------------------*/
70static
71void BZ2_hbMakeCodeLengths(UChar *len,
72 int32_t *freq,
73 int32_t alphaSize,
74 int32_t maxLen)
75{
76 /*
77 * Nodes and heap entries run from 1. Entry 0
78 * for both the heap and nodes is a sentinel.
79 */
80 int32_t nNodes, nHeap, n1, n2, i, j, k;
81 Bool tooLong;
82
83 int32_t heap [BZ_MAX_ALPHA_SIZE + 2];
84 int32_t weight[BZ_MAX_ALPHA_SIZE * 2];
85 int32_t parent[BZ_MAX_ALPHA_SIZE * 2];
86
87 for (i = 0; i < alphaSize; i++)
88 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
89
90 while (1) {
91 nNodes = alphaSize;
92 nHeap = 0;
93
94 heap[0] = 0;
95 weight[0] = 0;
96 parent[0] = -2;
97
98 for (i = 1; i <= alphaSize; i++) {
99 parent[i] = -1;
100 nHeap++;
101 heap[nHeap] = i;
102 UPHEAP(nHeap);
103 }
104
105 AssertH(nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001);
106
107 while (nHeap > 1) {
108 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
109 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
110 nNodes++;
111 parent[n1] = parent[n2] = nNodes;
112 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
113 parent[nNodes] = -1;
114 nHeap++;
115 heap[nHeap] = nNodes;
116 UPHEAP(nHeap);
117 }
118
119 AssertH(nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002);
120
121 tooLong = False;
122 for (i = 1; i <= alphaSize; i++) {
123 j = 0;
124 k = i;
125 while (parent[k] >= 0) {
126 k = parent[k];
127 j++;
128 }
129 len[i-1] = j;
130 if (j > maxLen)
131 tooLong = True;
132 }
133
134 if (!tooLong)
135 break;
136
137 /* 17 Oct 04: keep-going condition for the following loop used
138 to be 'i < alphaSize', which missed the last element,
139 theoretically leading to the possibility of the compressor
140 looping. However, this count-scaling step is only needed if
141 one of the generated Huffman code words is longer than
142 maxLen, which up to and including version 1.0.2 was 20 bits,
143 which is extremely unlikely. In version 1.0.3 maxLen was
144 changed to 17 bits, which has minimal effect on compression
145 ratio, but does mean this scaling step is used from time to
146 time, enough to verify that it works.
147
148 This means that bzip2-1.0.3 and later will only produce
149 Huffman codes with a maximum length of 17 bits. However, in
150 order to preserve backwards compatibility with bitstreams
151 produced by versions pre-1.0.3, the decompressor must still
152 handle lengths of up to 20. */
153
154 for (i = 1; i <= alphaSize; i++) {
155 j = weight[i] >> 8;
156 j = 1 + (j / 2);
157 weight[i] = j << 8;
158 }
159 }
160}
161
162
163/*---------------------------------------------------*/
164static
165void BZ2_hbAssignCodes(int32_t *code,
166 UChar *length,
167 int32_t minLen,
168 int32_t maxLen,
169 int32_t alphaSize)
170{
171 int32_t n, vec, i;
172
173 vec = 0;
174 for (n = minLen; n <= maxLen; n++) {
175 for (i = 0; i < alphaSize; i++) {
176 if (length[i] == n) {
177 code[i] = vec;
178 vec++;
179 };
180 }
181 vec <<= 1;
182 }
183}
184
185
186/*-------------------------------------------------------------*/
187/*--- end huffman.c ---*/
188/*-------------------------------------------------------------*/
diff --git a/archival/bz/randtable.c b/archival/bz/randtable.c
new file mode 100644
index 000000000..8a3c562da
--- /dev/null
+++ b/archival/bz/randtable.c
@@ -0,0 +1,85 @@
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/*--- Table for randomising repetitive blocks ---*/
9/*--- randtable.c ---*/
10/*-------------------------------------------------------------*/
11
12/* ------------------------------------------------------------------
13This file is part of bzip2/libbzip2, a program and library for
14lossless, block-sorting data compression.
15
16bzip2/libbzip2 version 1.0.4 of 20 December 2006
17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19Please read the WARNING, DISCLAIMER and PATENTS sections in the
20README file.
21
22This program is released under the terms of the license contained
23in the file LICENSE.
24------------------------------------------------------------------ */
25
26/* #include "bzlib_private.h" */
27
28static const int32_t BZ2_rNums[512] = {
29 619, 720, 127, 481, 931, 816, 813, 233, 566, 247,
30 985, 724, 205, 454, 863, 491, 741, 242, 949, 214,
31 733, 859, 335, 708, 621, 574, 73, 654, 730, 472,
32 419, 436, 278, 496, 867, 210, 399, 680, 480, 51,
33 878, 465, 811, 169, 869, 675, 611, 697, 867, 561,
34 862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
35 150, 238, 59, 379, 684, 877, 625, 169, 643, 105,
36 170, 607, 520, 932, 727, 476, 693, 425, 174, 647,
37 73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
38 909, 545, 703, 919, 874, 474, 882, 500, 594, 612,
39 641, 801, 220, 162, 819, 984, 589, 513, 495, 799,
40 161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
41 382, 596, 414, 171, 516, 375, 682, 485, 911, 276,
42 98, 553, 163, 354, 666, 933, 424, 341, 533, 870,
43 227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
44 469, 68, 770, 919, 190, 373, 294, 822, 808, 206,
45 184, 943, 795, 384, 383, 461, 404, 758, 839, 887,
46 715, 67, 618, 276, 204, 918, 873, 777, 604, 560,
47 951, 160, 578, 722, 79, 804, 96, 409, 713, 940,
48 652, 934, 970, 447, 318, 353, 859, 672, 112, 785,
49 645, 863, 803, 350, 139, 93, 354, 99, 820, 908,
50 609, 772, 154, 274, 580, 184, 79, 626, 630, 742,
51 653, 282, 762, 623, 680, 81, 927, 626, 789, 125,
52 411, 521, 938, 300, 821, 78, 343, 175, 128, 250,
53 170, 774, 972, 275, 999, 639, 495, 78, 352, 126,
54 857, 956, 358, 619, 580, 124, 737, 594, 701, 612,
55 669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
56 944, 375, 748, 52, 600, 747, 642, 182, 862, 81,
57 344, 805, 988, 739, 511, 655, 814, 334, 249, 515,
58 897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
59 433, 837, 553, 268, 926, 240, 102, 654, 459, 51,
60 686, 754, 806, 760, 493, 403, 415, 394, 687, 700,
61 946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
62 978, 321, 576, 617, 626, 502, 894, 679, 243, 440,
63 680, 879, 194, 572, 640, 724, 926, 56, 204, 700,
64 707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
65 297, 59, 87, 824, 713, 663, 412, 693, 342, 606,
66 134, 108, 571, 364, 631, 212, 174, 643, 304, 329,
67 343, 97, 430, 751, 497, 314, 983, 374, 822, 928,
68 140, 206, 73, 263, 980, 736, 876, 478, 430, 305,
69 170, 514, 364, 692, 829, 82, 855, 953, 676, 246,
70 369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
71 804, 378, 215, 828, 592, 281, 565, 555, 710, 82,
72 896, 831, 547, 261, 524, 462, 293, 465, 502, 56,
73 661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
74 768, 550, 608, 933, 378, 286, 215, 979, 792, 961,
75 61, 688, 793, 644, 986, 403, 106, 366, 905, 644,
76 372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
77 780, 773, 635, 389, 707, 100, 626, 958, 165, 504,
78 920, 176, 193, 713, 857, 265, 203, 50, 668, 108,
79 645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
80 936, 638
81};
82
83/*-------------------------------------------------------------*/
84/*--- end randtable.c ---*/
85/*-------------------------------------------------------------*/
diff --git a/archival/bzip2.c b/archival/bzip2.c
new file mode 100644
index 000000000..04478eecc
--- /dev/null
+++ b/archival/bzip2.c
@@ -0,0 +1,166 @@
1/*
2 * Copyright (C) 2007 Denys Vlasenko <vda.linux@googlemail.com>
3 *
4 * This file uses bzip2 library code which is written
5 * by Julian Seward <jseward@bzip.org>.
6 * See README and LICENSE files in bz/ directory for more information
7 * about bzip2 library code.
8 */
9
10#include "libbb.h"
11
12/* This buys 6% speed for nearly 4k code */
13/*#define FAST_GROUP6 1*/
14
15#include "bz/bzlib.h"
16
17#include "bz/bzlib_private.h"
18
19#include "bz/blocksort.c"
20#include "bz/bzlib.c"
21#include "bz/compress.c"
22#include "bz/crctable.c"
23#include "bz/huffman.c"
24#include "bz/randtable.c"
25
26/* No point in being shy and having very small buffer here.
27 * bzip2 internal buffers are much bigger anyway, hundreds of kbytes.
28 * If iobuf is several pages long, malloc() may use mmap,
29 * making iobuf is page aligned and thus (maybe) have one memcpy less
30 * if kernel is clever enough.
31 */
32enum {
33 IOBUF_SIZE = 8 * 1024
34};
35
36/* Returns:
37 * <0 on write errors (examine errno),
38 * >0 on short writes (errno == 0)
39 * 0 no error (entire input consume, gimme more)
40 * on "impossible" errors (internal bzip2 compressor bug) dies
41 */
42static
43ssize_t bz_write(bz_stream *strm, void* rbuf, ssize_t rlen, void *wbuf)
44{
45 int n, n2, ret;
46
47 /* if (len == 0) return 0; */
48
49 strm->avail_in = rlen;
50 strm->next_in = rbuf;
51 while (1) {
52 strm->avail_out = IOBUF_SIZE;
53 strm->next_out = wbuf;
54
55 ret = BZ2_bzCompress(strm, BZ_RUN);
56 if (ret != BZ_RUN_OK)
57 bb_error_msg_and_die("internal error %d", ret);
58
59 n = IOBUF_SIZE - strm->avail_out;
60 if (n) {
61 /* short reads must have errno == 0 */
62 errno = 0;
63 n2 = full_write(STDOUT_FILENO, wbuf, n);
64 if (n2 != n)
65 return n2 ? n2 : 1;
66 }
67
68 if (strm->avail_in == 0)
69 return 0;
70 }
71}
72
73
74/*---------------------------------------------------*/
75static
76USE_DESKTOP(long long) int bz_write_tail(bz_stream *strm, void *wbuf)
77{
78 int n, n2, ret;
79 USE_DESKTOP(long long) int total;
80
81 total = -1;
82 while (1) {
83 strm->avail_out = IOBUF_SIZE;
84 strm->next_out = wbuf;
85
86 ret = BZ2_bzCompress(strm, BZ_FINISH);
87 if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END)
88 bb_error_msg_and_die("internal error %d", ret);
89
90 n = IOBUF_SIZE - strm->avail_out;
91 if (n) {
92 n2 = full_write(STDOUT_FILENO, wbuf, n);
93 if (n2 != n)
94 goto err;
95 }
96
97 if (ret == BZ_STREAM_END)
98 break;
99 }
100
101 total = 0 USE_DESKTOP( + strm->total_out );
102 err:
103 BZ2_bzCompressEnd(strm);
104 return total;
105}
106
107
108static
109USE_DESKTOP(long long) int compressStream(void)
110{
111 USE_DESKTOP(long long) int total;
112 ssize_t count;
113 bz_stream bzs; /* it's small */
114#define strm (&bzs)
115 char *iobuf;
116#define rbuf iobuf
117#define wbuf (iobuf + IOBUF_SIZE)
118
119 iobuf = xmalloc(2 * IOBUF_SIZE);
120
121 BZ2_bzCompressInit(strm, 9 /*blockSize100k*/);
122
123 while (1) {
124 count = full_read(STDIN_FILENO, rbuf, IOBUF_SIZE);
125 if (count < 0)
126 bb_perror_msg("read error");
127 if (count <= 0)
128 break;
129 count = bz_write(strm, rbuf, count, wbuf);
130 if (count) {
131 bb_perror_msg(count < 0 ? "write error" : "short write");
132 break;
133 }
134 }
135
136 total = bz_write_tail(strm, wbuf);
137 free(iobuf);
138 /* we had no error _only_ if count == 0 */
139 return count == 0 ? total : -1;
140}
141
142static
143char* make_new_name_bzip2(char *filename)
144{
145 return xasprintf("%s.bz2", filename);
146}
147
148int bzip2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
149int bzip2_main(int argc, char **argv)
150{
151 unsigned opt;
152
153 /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */
154 opt = getopt32(argv, "cfv" USE_BUNZIP2("d") "q123456789" );
155#if ENABLE_BUNZIP2 /* bunzip2_main may not be visible... */
156 if (opt & 0x8) // -d
157 return bunzip2_main(argc, argv);
158#endif
159 option_mask32 &= 0x7; /* ignore -q, -0..9 */
160 //if (opt & 0x1) // -c
161 //if (opt & 0x2) // -f
162 //if (opt & 0x4) // -v
163 argv += optind;
164
165 return bbunpack(argv, make_new_name_bzip2, compressStream);
166}
diff --git a/archival/gzip.c b/archival/gzip.c
index bc7502e70..00299b17c 100644
--- a/archival/gzip.c
+++ b/archival/gzip.c
@@ -2032,15 +2032,14 @@ int gzip_main(int argc, char **argv)
2032 2032
2033 /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */ 2033 /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */
2034 opt = getopt32(argv, "cfv" USE_GUNZIP("d") "q123456789" ); 2034 opt = getopt32(argv, "cfv" USE_GUNZIP("d") "q123456789" );
2035 option_mask32 &= 0x7; /* Clear -d, ignore -q, -0..9 */
2036 //if (opt & 0x1) // -c
2037 //if (opt & 0x2) // -f
2038 //if (opt & 0x4) // -v
2039#if ENABLE_GUNZIP /* gunzip_main may not be visible... */ 2035#if ENABLE_GUNZIP /* gunzip_main may not be visible... */
2040 if (opt & 0x8) { // -d 2036 if (opt & 0x8) // -d
2041 return gunzip_main(argc, argv); 2037 return gunzip_main(argc, argv);
2042 }
2043#endif 2038#endif
2039 option_mask32 &= 0x7; /* ignore -q, -0..9 */
2040 //if (opt & 0x1) // -c
2041 //if (opt & 0x2) // -f
2042 //if (opt & 0x4) // -v
2044 argv += optind; 2043 argv += optind;
2045 2044
2046 PTR_TO_GLOBALS = xzalloc(sizeof(struct globals) + sizeof(struct globals2)) 2045 PTR_TO_GLOBALS = xzalloc(sizeof(struct globals) + sizeof(struct globals2))
diff --git a/archival/libunarchive/Kbuild b/archival/libunarchive/Kbuild
index a58a84f4b..1bc054a96 100644
--- a/archival/libunarchive/Kbuild
+++ b/archival/libunarchive/Kbuild
@@ -28,8 +28,6 @@ lib-y:= \
28 find_list_entry.o \ 28 find_list_entry.o \
29 init_handle.o 29 init_handle.o
30 30
31GUNZIP_FILES:= decompress_unzip.o
32
33DPKG_FILES:= \ 31DPKG_FILES:= \
34 get_header_ar.o \ 32 get_header_ar.o \
35 unpack_ar_archive.o \ 33 unpack_ar_archive.o \
@@ -51,19 +49,19 @@ lib-$(CONFIG_UNLZMA) += decompress_unlzma.o
51lib-$(CONFIG_CPIO) += get_header_cpio.o 49lib-$(CONFIG_CPIO) += get_header_cpio.o
52lib-$(CONFIG_DPKG) += $(DPKG_FILES) 50lib-$(CONFIG_DPKG) += $(DPKG_FILES)
53lib-$(CONFIG_DPKG_DEB) += $(DPKG_FILES) 51lib-$(CONFIG_DPKG_DEB) += $(DPKG_FILES)
54lib-$(CONFIG_FEATURE_DEB_TAR_GZ) += $(GUNZIP_FILES) get_header_tar_gz.o 52lib-$(CONFIG_FEATURE_DEB_TAR_GZ) += decompress_unzip.o get_header_tar_gz.o
55lib-$(CONFIG_FEATURE_DEB_TAR_BZ2) += decompress_bunzip2.o get_header_tar_bz2.o 53lib-$(CONFIG_FEATURE_DEB_TAR_BZ2) += decompress_bunzip2.o get_header_tar_bz2.o
56lib-$(CONFIG_FEATURE_DEB_TAR_LZMA) += decompress_unlzma.o get_header_tar_lzma.o 54lib-$(CONFIG_FEATURE_DEB_TAR_LZMA) += decompress_unlzma.o get_header_tar_lzma.o
57lib-$(CONFIG_GUNZIP) += $(GUNZIP_FILES) 55lib-$(CONFIG_GUNZIP) += decompress_unzip.o
58lib-$(CONFIG_FEATURE_GUNZIP_UNCOMPRESS) += decompress_uncompress.o 56lib-$(CONFIG_FEATURE_GUNZIP_UNCOMPRESS) += decompress_uncompress.o
59lib-$(CONFIG_RPM2CPIO) += $(GUNZIP_FILES) get_header_cpio.o 57lib-$(CONFIG_RPM2CPIO) += decompress_unzip.o get_header_cpio.o
60lib-$(CONFIG_RPM) += $(GUNZIP_FILES) get_header_cpio.o 58lib-$(CONFIG_RPM) += decompress_unzip.o get_header_cpio.o
61lib-$(CONFIG_FEATURE_RPM_BZ2) += decompress_bunzip2.o 59lib-$(CONFIG_FEATURE_RPM_BZ2) += decompress_bunzip2.o
62lib-$(CONFIG_TAR) += get_header_tar.o 60lib-$(CONFIG_TAR) += get_header_tar.o
63lib-$(CONFIG_FEATURE_TAR_BZIP2) += decompress_bunzip2.o get_header_tar_bz2.o 61lib-$(CONFIG_FEATURE_TAR_BZIP2) += decompress_bunzip2.o get_header_tar_bz2.o
64lib-$(CONFIG_FEATURE_TAR_LZMA) += decompress_unlzma.o get_header_tar_lzma.o 62lib-$(CONFIG_FEATURE_TAR_LZMA) += decompress_unlzma.o get_header_tar_lzma.o
65lib-$(CONFIG_FEATURE_TAR_GZIP) += $(GUNZIP_FILES) get_header_tar_gz.o 63lib-$(CONFIG_FEATURE_TAR_GZIP) += decompress_unzip.o get_header_tar_gz.o
66lib-$(CONFIG_FEATURE_TAR_COMPRESS) += decompress_uncompress.o 64lib-$(CONFIG_FEATURE_TAR_COMPRESS) += decompress_uncompress.o
67lib-$(CONFIG_UNCOMPRESS) += decompress_uncompress.o 65lib-$(CONFIG_UNCOMPRESS) += decompress_uncompress.o
68lib-$(CONFIG_UNZIP) += $(GUNZIP_FILES) 66lib-$(CONFIG_UNZIP) += decompress_unzip.o
69lib-$(CONFIG_FEATURE_COMPRESS_USAGE) += decompress_bunzip2.o 67lib-$(CONFIG_FEATURE_COMPRESS_USAGE) += decompress_bunzip2.o
diff --git a/archival/libunarchive/decompress_unzip.c b/archival/libunarchive/decompress_unzip.c
index 52be6b25d..0572bee68 100644
--- a/archival/libunarchive/decompress_unzip.c
+++ b/archival/libunarchive/decompress_unzip.c
@@ -323,7 +323,7 @@ static int huft_build(const unsigned *b, const unsigned n,
323 } while (--i); 323 } while (--i);
324 if (c[0] == n) { /* null input - all zero length codes */ 324 if (c[0] == n) { /* null input - all zero length codes */
325 *m = 0; 325 *m = 0;
326 return 2; 326 return 2;
327 } 327 }
328 328
329 /* Find minimum and maximum length, bound *m by those */ 329 /* Find minimum and maximum length, bound *m by those */
diff --git a/include/applets.h b/include/applets.h
index ceab00334..29a5d09e3 100644
--- a/include/applets.h
+++ b/include/applets.h
@@ -88,6 +88,7 @@ USE_BBCONFIG(APPLET(bbconfig, _BB_DIR_BIN, _BB_SUID_NEVER))
88//USE_BBSH(APPLET(bbsh, _BB_DIR_BIN, _BB_SUID_NEVER)) 88//USE_BBSH(APPLET(bbsh, _BB_DIR_BIN, _BB_SUID_NEVER))
89USE_BUNZIP2(APPLET(bunzip2, _BB_DIR_USR_BIN, _BB_SUID_NEVER)) 89USE_BUNZIP2(APPLET(bunzip2, _BB_DIR_USR_BIN, _BB_SUID_NEVER))
90USE_BUNZIP2(APPLET_ODDNAME(bzcat, bunzip2, _BB_DIR_USR_BIN, _BB_SUID_NEVER, bzcat)) 90USE_BUNZIP2(APPLET_ODDNAME(bzcat, bunzip2, _BB_DIR_USR_BIN, _BB_SUID_NEVER, bzcat))
91USE_BZIP2(APPLET(bzip2, _BB_DIR_USR_BIN, _BB_SUID_NEVER))
91USE_CAL(APPLET(cal, _BB_DIR_USR_BIN, _BB_SUID_NEVER)) 92USE_CAL(APPLET(cal, _BB_DIR_USR_BIN, _BB_SUID_NEVER))
92USE_CAT(APPLET_NOFORK(cat, cat, _BB_DIR_BIN, _BB_SUID_NEVER, cat)) 93USE_CAT(APPLET_NOFORK(cat, cat, _BB_DIR_BIN, _BB_SUID_NEVER, cat))
93USE_CATV(APPLET(catv, _BB_DIR_BIN, _BB_SUID_NEVER)) 94USE_CATV(APPLET(catv, _BB_DIR_BIN, _BB_SUID_NEVER))
diff --git a/include/libbb.h b/include/libbb.h
index be548a306..af385e232 100644
--- a/include/libbb.h
+++ b/include/libbb.h
@@ -709,6 +709,9 @@ int chown_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
709#if ENABLE_GUNZIP 709#if ENABLE_GUNZIP
710int gunzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; 710int gunzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
711#endif 711#endif
712#if ENABLE_BUNZIP2
713int bunzip2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
714#endif
712int bbunpack(char **argv, 715int bbunpack(char **argv,
713 char* (*make_new_name)(char *filename), 716 char* (*make_new_name)(char *filename),
714 USE_DESKTOP(long long) int (*unpacker)(void) 717 USE_DESKTOP(long long) int (*unpacker)(void)
diff --git a/include/platform.h b/include/platform.h
index 53d72829f..edb0f8ab0 100644
--- a/include/platform.h
+++ b/include/platform.h
@@ -54,7 +54,8 @@
54# define ATTRIBUTE_ALIGNED(m) __attribute__ ((__aligned__(m))) 54# define ATTRIBUTE_ALIGNED(m) __attribute__ ((__aligned__(m)))
55# if __GNUC_PREREQ (3,0) 55# if __GNUC_PREREQ (3,0)
56# define ALWAYS_INLINE __attribute__ ((always_inline)) inline 56# define ALWAYS_INLINE __attribute__ ((always_inline)) inline
57# define NOINLINE __attribute__((noinline)) 57/* I've seen a toolchain where I needed __noinline__ instead of noinline */
58# define NOINLINE __attribute__((__noinline__))
58# if !ENABLE_WERROR 59# if !ENABLE_WERROR
59# define ATTRIBUTE_DEPRECATED __attribute__ ((__deprecated__)) 60# define ATTRIBUTE_DEPRECATED __attribute__ ((__deprecated__))
60# define ATTRIBUTE_UNUSED_RESULT __attribute__ ((warn_unused_result)) 61# define ATTRIBUTE_UNUSED_RESULT __attribute__ ((warn_unused_result))
@@ -63,7 +64,8 @@
63# define ATTRIBUTE_UNUSED_RESULT /* n/a */ 64# define ATTRIBUTE_UNUSED_RESULT /* n/a */
64# endif 65# endif
65# else 66# else
66# define ALWAYS_INLINE inline 67# define ALWAYS_INLINE inline /* n/a */
68# define NOINLINE /* n/a */
67# define ATTRIBUTE_DEPRECATED /* n/a */ 69# define ATTRIBUTE_DEPRECATED /* n/a */
68# define ATTRIBUTE_UNUSED_RESULT /* n/a */ 70# define ATTRIBUTE_UNUSED_RESULT /* n/a */
69# endif 71# endif
diff --git a/include/usage.h b/include/usage.h
index b53820d7b..4c697d380 100644
--- a/include/usage.h
+++ b/include/usage.h
@@ -127,6 +127,16 @@
127 " -c Write output to standard output\n" \ 127 " -c Write output to standard output\n" \
128 " -f Force" 128 " -f Force"
129 129
130#define bzip2_trivial_usage \
131 "[OPTION]... [FILE]..."
132#define bzip2_full_usage \
133 "Compress FILE(s) with bzip2 algorithm.\n" \
134 "When FILE is '-' or unspecified, reads standard input. Implies -c." \
135 "\n\nOptions:\n" \
136 " -c Write output to standard output instead of FILE.bz\n" \
137 " -d Decompress\n" \
138 " -f Force"
139
130#define busybox_notes_usage \ 140#define busybox_notes_usage \
131 "Hello world!\n" 141 "Hello world!\n"
132 142
@@ -1201,7 +1211,7 @@
1201 "Uncompress FILE (or standard input if FILE is '-')" \ 1211 "Uncompress FILE (or standard input if FILE is '-')" \
1202 "\n\nOptions:\n" \ 1212 "\n\nOptions:\n" \
1203 " -c Write output to standard output\n" \ 1213 " -c Write output to standard output\n" \
1204 " -f Force read when source is a terminal\n" \ 1214 " -f Force\n" \
1205 " -t Test compressed file integrity" 1215 " -t Test compressed file integrity"
1206#define gunzip_example_usage \ 1216#define gunzip_example_usage \
1207 "$ ls -la /tmp/BusyBox*\n" \ 1217 "$ ls -la /tmp/BusyBox*\n" \
@@ -1218,7 +1228,7 @@
1218 "\n\nOptions:\n" \ 1228 "\n\nOptions:\n" \
1219 " -c Write output to standard output instead of FILE.gz\n" \ 1229 " -c Write output to standard output instead of FILE.gz\n" \
1220 " -d Decompress\n" \ 1230 " -d Decompress\n" \
1221 " -f Force write when destination is a terminal" 1231 " -f Force"
1222#define gzip_example_usage \ 1232#define gzip_example_usage \
1223 "$ ls -la /tmp/busybox*\n" \ 1233 "$ ls -la /tmp/busybox*\n" \
1224 "-rw-rw-r-- 1 andersen andersen 1761280 Apr 14 17:47 /tmp/busybox.tar\n" \ 1234 "-rw-rw-r-- 1 andersen andersen 1761280 Apr 14 17:47 /tmp/busybox.tar\n" \
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 15:24:56 +0000