summaryrefslogtreecommitdiff
path: root/utils/bzip2
diff options
context:
space:
mode:
authorDominik Riebeling <Dominik.Riebeling@gmail.com>2021-12-15 21:04:28 +0100
committerDominik Riebeling <Dominik.Riebeling@gmail.com>2021-12-24 18:05:53 +0100
commitc876d3bbefe0dc00c27ca0c12d29da5874946962 (patch)
tree69f468a185a369b01998314bc3ecc19b70f4fcaa /utils/bzip2
parent6c6f0757d7a902feb293be165d1490c42bc8e7ad (diff)
downloadrockbox-c876d3bbefe0dc00c27ca0c12d29da5874946962.tar.gz
rockbox-c876d3bbefe0dc00c27ca0c12d29da5874946962.zip
rbutil: Merge rbutil with utils folder.
rbutil uses several components from the utils folder, and can be considered part of utils too. Having it in a separate folder is an arbitrary split that doesn't help anymore these days, so merge them. This also allows other utils to easily use libtools.make without the need to navigate to a different folder. Change-Id: I3fc2f4de19e3e776553efb5dea5f779dfec0dc21
Diffstat (limited to 'utils/bzip2')
-rw-r--r--utils/bzip2/LICENSE42
-rw-r--r--utils/bzip2/Makefile15
-rw-r--r--utils/bzip2/blocksort.c1094
-rw-r--r--utils/bzip2/bzlib.c1572
-rw-r--r--utils/bzip2/bzlib.h282
-rw-r--r--utils/bzip2/bzlib_private.h512
-rw-r--r--utils/bzip2/compress.c672
-rw-r--r--utils/bzip2/crctable.c104
-rw-r--r--utils/bzip2/decompress.c646
-rw-r--r--utils/bzip2/huffman.c205
-rw-r--r--utils/bzip2/randtable.c84
11 files changed, 5228 insertions, 0 deletions
diff --git a/utils/bzip2/LICENSE b/utils/bzip2/LICENSE
new file mode 100644
index 0000000000..cc614178cf
--- /dev/null
+++ b/utils/bzip2/LICENSE
@@ -0,0 +1,42 @@
1
2--------------------------------------------------------------------------
3
4This program, "bzip2", the associated library "libbzip2", and all
5documentation, are copyright (C) 1996-2010 Julian R Seward. All
6rights reserved.
7
8Redistribution and use in source and binary forms, with or without
9modification, are permitted provided that the following conditions
10are met:
11
121. Redistributions of source code must retain the above copyright
13 notice, this list of conditions and the following disclaimer.
14
152. The origin of this software must not be misrepresented; you must
16 not claim that you wrote the original software. If you use this
17 software in a product, an acknowledgment in the product
18 documentation would be appreciated but is not required.
19
203. Altered source versions must be plainly marked as such, and must
21 not be misrepresented as being the original software.
22
234. The name of the author may not be used to endorse or promote
24 products derived from this software without specific prior written
25 permission.
26
27THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
28OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
29WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
31DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
33GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
34INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
35WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
36NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38
39Julian Seward, jseward@bzip.org
40bzip2/libbzip2 version 1.0.6 of 6 September 2010
41
42--------------------------------------------------------------------------
diff --git a/utils/bzip2/Makefile b/utils/bzip2/Makefile
new file mode 100644
index 0000000000..6dc59ed025
--- /dev/null
+++ b/utils/bzip2/Makefile
@@ -0,0 +1,15 @@
1# __________ __ ___.
2# Open \______ \ ____ ____ | | _\_ |__ _______ ___
3# Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
4# Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
5# Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
6# \/ \/ \/ \/ \/
7# $Id$
8#
9
10LIBSOURCES := blocksort.c compress.c decompress.c randtable.c \
11 bzlib.c crctable.c huffman.c
12
13OUTPUT := bz2
14
15include ../libtools.make
diff --git a/utils/bzip2/blocksort.c b/utils/bzip2/blocksort.c
new file mode 100644
index 0000000000..d0d662cd4e
--- /dev/null
+++ b/utils/bzip2/blocksort.c
@@ -0,0 +1,1094 @@
1
2/*-------------------------------------------------------------*/
3/*--- Block sorting machinery ---*/
4/*--- blocksort.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#include "bzlib_private.h"
23
24/*---------------------------------------------*/
25/*--- Fallback O(N log(N)^2) sorting ---*/
26/*--- algorithm, for repetitive blocks ---*/
27/*---------------------------------------------*/
28
29/*---------------------------------------------*/
30static
31__inline__
32void fallbackSimpleSort ( UInt32* fmap,
33 UInt32* eclass,
34 Int32 lo,
35 Int32 hi )
36{
37 Int32 i, j, tmp;
38 UInt32 ec_tmp;
39
40 if (lo == hi) return;
41
42 if (hi - lo > 3) {
43 for ( i = hi-4; i >= lo; i-- ) {
44 tmp = fmap[i];
45 ec_tmp = eclass[tmp];
46 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
47 fmap[j-4] = fmap[j];
48 fmap[j-4] = tmp;
49 }
50 }
51
52 for ( i = hi-1; i >= lo; i-- ) {
53 tmp = fmap[i];
54 ec_tmp = eclass[tmp];
55 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
56 fmap[j-1] = fmap[j];
57 fmap[j-1] = tmp;
58 }
59}
60
61
62/*---------------------------------------------*/
63#define fswap(zz1, zz2) \
64 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
65
66#define fvswap(zzp1, zzp2, zzn) \
67{ \
68 Int32 yyp1 = (zzp1); \
69 Int32 yyp2 = (zzp2); \
70 Int32 yyn = (zzn); \
71 while (yyn > 0) { \
72 fswap(fmap[yyp1], fmap[yyp2]); \
73 yyp1++; yyp2++; yyn--; \
74 } \
75}
76
77
78#define fmin(a,b) ((a) < (b)) ? (a) : (b)
79
80#define fpush(lz,hz) { stackLo[sp] = lz; \
81 stackHi[sp] = hz; \
82 sp++; }
83
84#define fpop(lz,hz) { sp--; \
85 lz = stackLo[sp]; \
86 hz = stackHi[sp]; }
87
88#define FALLBACK_QSORT_SMALL_THRESH 10
89#define FALLBACK_QSORT_STACK_SIZE 100
90
91
92static
93void fallbackQSort3 ( UInt32* fmap,
94 UInt32* eclass,
95 Int32 loSt,
96 Int32 hiSt )
97{
98 Int32 unLo, unHi, ltLo, gtHi, n, m;
99 Int32 sp, lo, hi;
100 UInt32 med, r, r3;
101 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
102 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
103
104 r = 0;
105
106 sp = 0;
107 fpush ( loSt, hiSt );
108
109 while (sp > 0) {
110
111 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
112
113 fpop ( lo, hi );
114 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
115 fallbackSimpleSort ( fmap, eclass, lo, hi );
116 continue;
117 }
118
119 /* Random partitioning. Median of 3 sometimes fails to
120 avoid bad cases. Median of 9 seems to help but
121 looks rather expensive. This too seems to work but
122 is cheaper. Guidance for the magic constants
123 7621 and 32768 is taken from Sedgewick's algorithms
124 book, chapter 35.
125 */
126 r = ((r * 7621) + 1) % 32768;
127 r3 = r % 3;
128 if (r3 == 0) med = eclass[fmap[lo]]; else
129 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
130 med = eclass[fmap[hi]];
131
132 unLo = ltLo = lo;
133 unHi = gtHi = hi;
134
135 while (1) {
136 while (1) {
137 if (unLo > unHi) break;
138 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
139 if (n == 0) {
140 fswap(fmap[unLo], fmap[ltLo]);
141 ltLo++; unLo++;
142 continue;
143 };
144 if (n > 0) break;
145 unLo++;
146 }
147 while (1) {
148 if (unLo > unHi) break;
149 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
150 if (n == 0) {
151 fswap(fmap[unHi], fmap[gtHi]);
152 gtHi--; unHi--;
153 continue;
154 };
155 if (n < 0) break;
156 unHi--;
157 }
158 if (unLo > unHi) break;
159 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
160 }
161
162 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
163
164 if (gtHi < ltLo) continue;
165
166 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
167 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
168
169 n = lo + unLo - ltLo - 1;
170 m = hi - (gtHi - unHi) + 1;
171
172 if (n - lo > hi - m) {
173 fpush ( lo, n );
174 fpush ( m, hi );
175 } else {
176 fpush ( m, hi );
177 fpush ( lo, n );
178 }
179 }
180}
181
182#undef fmin
183#undef fpush
184#undef fpop
185#undef fswap
186#undef fvswap
187#undef FALLBACK_QSORT_SMALL_THRESH
188#undef FALLBACK_QSORT_STACK_SIZE
189
190
191/*---------------------------------------------*/
192/* Pre:
193 nblock > 0
194 eclass exists for [0 .. nblock-1]
195 ((UChar*)eclass) [0 .. nblock-1] holds block
196 ptr exists for [0 .. nblock-1]
197
198 Post:
199 ((UChar*)eclass) [0 .. nblock-1] holds block
200 All other areas of eclass destroyed
201 fmap [0 .. nblock-1] holds sorted order
202 bhtab [ 0 .. 2+(nblock/32) ] destroyed
203*/
204
205#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
206#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
207#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
208#define WORD_BH(zz) bhtab[(zz) >> 5]
209#define UNALIGNED_BH(zz) ((zz) & 0x01f)
210
211static
212void fallbackSort ( UInt32* fmap,
213 UInt32* eclass,
214 UInt32* bhtab,
215 Int32 nblock,
216 Int32 verb )
217{
218 Int32 ftab[257];
219 Int32 ftabCopy[256];
220 Int32 H, i, j, k, l, r, cc, cc1;
221 Int32 nNotDone;
222 Int32 nBhtab;
223 UChar* eclass8 = (UChar*)eclass;
224
225 /*--
226 Initial 1-char radix sort to generate
227 initial fmap and initial BH bits.
228 --*/
229 if (verb >= 4)
230 VPrintf0 ( " bucket sorting ...\n" );
231 for (i = 0; i < 257; i++) ftab[i] = 0;
232 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
233 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
234 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
235
236 for (i = 0; i < nblock; i++) {
237 j = eclass8[i];
238 k = ftab[j] - 1;
239 ftab[j] = k;
240 fmap[k] = i;
241 }
242
243 nBhtab = 2 + (nblock / 32);
244 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
245 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
246
247 /*--
248 Inductively refine the buckets. Kind-of an
249 "exponential radix sort" (!), inspired by the
250 Manber-Myers suffix array construction algorithm.
251 --*/
252
253 /*-- set sentinel bits for block-end detection --*/
254 for (i = 0; i < 32; i++) {
255 SET_BH(nblock + 2*i);
256 CLEAR_BH(nblock + 2*i + 1);
257 }
258
259 /*-- the log(N) loop --*/
260 H = 1;
261 while (1) {
262
263 if (verb >= 4)
264 VPrintf1 ( " depth %6d has ", H );
265
266 j = 0;
267 for (i = 0; i < nblock; i++) {
268 if (ISSET_BH(i)) j = i;
269 k = fmap[i] - H; if (k < 0) k += nblock;
270 eclass[k] = j;
271 }
272
273 nNotDone = 0;
274 r = -1;
275 while (1) {
276
277 /*-- find the next non-singleton bucket --*/
278 k = r + 1;
279 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
280 if (ISSET_BH(k)) {
281 while (WORD_BH(k) == 0xffffffff) k += 32;
282 while (ISSET_BH(k)) k++;
283 }
284 l = k - 1;
285 if (l >= nblock) break;
286 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
287 if (!ISSET_BH(k)) {
288 while (WORD_BH(k) == 0x00000000) k += 32;
289 while (!ISSET_BH(k)) k++;
290 }
291 r = k - 1;
292 if (r >= nblock) break;
293
294 /*-- now [l, r] bracket current bucket --*/
295 if (r > l) {
296 nNotDone += (r - l + 1);
297 fallbackQSort3 ( fmap, eclass, l, r );
298
299 /*-- scan bucket and generate header bits-- */
300 cc = -1;
301 for (i = l; i <= r; i++) {
302 cc1 = eclass[fmap[i]];
303 if (cc != cc1) { SET_BH(i); cc = cc1; };
304 }
305 }
306 }
307
308 if (verb >= 4)
309 VPrintf1 ( "%6d unresolved strings\n", nNotDone );
310
311 H *= 2;
312 if (H > nblock || nNotDone == 0) break;
313 }
314
315 /*--
316 Reconstruct the original block in
317 eclass8 [0 .. nblock-1], since the
318 previous phase destroyed it.
319 --*/
320 if (verb >= 4)
321 VPrintf0 ( " reconstructing block ...\n" );
322 j = 0;
323 for (i = 0; i < nblock; i++) {
324 while (ftabCopy[j] == 0) j++;
325 ftabCopy[j]--;
326 eclass8[fmap[i]] = (UChar)j;
327 }
328 AssertH ( j < 256, 1005 );
329}
330
331#undef SET_BH
332#undef CLEAR_BH
333#undef ISSET_BH
334#undef WORD_BH
335#undef UNALIGNED_BH
336
337
338/*---------------------------------------------*/
339/*--- The main, O(N^2 log(N)) sorting ---*/
340/*--- algorithm. Faster for "normal" ---*/
341/*--- non-repetitive blocks. ---*/
342/*---------------------------------------------*/
343
344/*---------------------------------------------*/
345static
346__inline__
347Bool mainGtU ( UInt32 i1,
348 UInt32 i2,
349 UChar* block,
350 UInt16* quadrant,
351 UInt32 nblock,
352 Int32* budget )
353{
354 Int32 k;
355 UChar c1, c2;
356 UInt16 s1, s2;
357
358 AssertD ( i1 != i2, "mainGtU" );
359 /* 1 */
360 c1 = block[i1]; c2 = block[i2];
361 if (c1 != c2) return (c1 > c2);
362 i1++; i2++;
363 /* 2 */
364 c1 = block[i1]; c2 = block[i2];
365 if (c1 != c2) return (c1 > c2);
366 i1++; i2++;
367 /* 3 */
368 c1 = block[i1]; c2 = block[i2];
369 if (c1 != c2) return (c1 > c2);
370 i1++; i2++;
371 /* 4 */
372 c1 = block[i1]; c2 = block[i2];
373 if (c1 != c2) return (c1 > c2);
374 i1++; i2++;
375 /* 5 */
376 c1 = block[i1]; c2 = block[i2];
377 if (c1 != c2) return (c1 > c2);
378 i1++; i2++;
379 /* 6 */
380 c1 = block[i1]; c2 = block[i2];
381 if (c1 != c2) return (c1 > c2);
382 i1++; i2++;
383 /* 7 */
384 c1 = block[i1]; c2 = block[i2];
385 if (c1 != c2) return (c1 > c2);
386 i1++; i2++;
387 /* 8 */
388 c1 = block[i1]; c2 = block[i2];
389 if (c1 != c2) return (c1 > c2);
390 i1++; i2++;
391 /* 9 */
392 c1 = block[i1]; c2 = block[i2];
393 if (c1 != c2) return (c1 > c2);
394 i1++; i2++;
395 /* 10 */
396 c1 = block[i1]; c2 = block[i2];
397 if (c1 != c2) return (c1 > c2);
398 i1++; i2++;
399 /* 11 */
400 c1 = block[i1]; c2 = block[i2];
401 if (c1 != c2) return (c1 > c2);
402 i1++; i2++;
403 /* 12 */
404 c1 = block[i1]; c2 = block[i2];
405 if (c1 != c2) return (c1 > c2);
406 i1++; i2++;
407
408 k = nblock + 8;
409
410 do {
411 /* 1 */
412 c1 = block[i1]; c2 = block[i2];
413 if (c1 != c2) return (c1 > c2);
414 s1 = quadrant[i1]; s2 = quadrant[i2];
415 if (s1 != s2) return (s1 > s2);
416 i1++; i2++;
417 /* 2 */
418 c1 = block[i1]; c2 = block[i2];
419 if (c1 != c2) return (c1 > c2);
420 s1 = quadrant[i1]; s2 = quadrant[i2];
421 if (s1 != s2) return (s1 > s2);
422 i1++; i2++;
423 /* 3 */
424 c1 = block[i1]; c2 = block[i2];
425 if (c1 != c2) return (c1 > c2);
426 s1 = quadrant[i1]; s2 = quadrant[i2];
427 if (s1 != s2) return (s1 > s2);
428 i1++; i2++;
429 /* 4 */
430 c1 = block[i1]; c2 = block[i2];
431 if (c1 != c2) return (c1 > c2);
432 s1 = quadrant[i1]; s2 = quadrant[i2];
433 if (s1 != s2) return (s1 > s2);
434 i1++; i2++;
435 /* 5 */
436 c1 = block[i1]; c2 = block[i2];
437 if (c1 != c2) return (c1 > c2);
438 s1 = quadrant[i1]; s2 = quadrant[i2];
439 if (s1 != s2) return (s1 > s2);
440 i1++; i2++;
441 /* 6 */
442 c1 = block[i1]; c2 = block[i2];
443 if (c1 != c2) return (c1 > c2);
444 s1 = quadrant[i1]; s2 = quadrant[i2];
445 if (s1 != s2) return (s1 > s2);
446 i1++; i2++;
447 /* 7 */
448 c1 = block[i1]; c2 = block[i2];
449 if (c1 != c2) return (c1 > c2);
450 s1 = quadrant[i1]; s2 = quadrant[i2];
451 if (s1 != s2) return (s1 > s2);
452 i1++; i2++;
453 /* 8 */
454 c1 = block[i1]; c2 = block[i2];
455 if (c1 != c2) return (c1 > c2);
456 s1 = quadrant[i1]; s2 = quadrant[i2];
457 if (s1 != s2) return (s1 > s2);
458 i1++; i2++;
459
460 if (i1 >= nblock) i1 -= nblock;
461 if (i2 >= nblock) i2 -= nblock;
462
463 k -= 8;
464 (*budget)--;
465 }
466 while (k >= 0);
467
468 return False;
469}
470
471
472/*---------------------------------------------*/
473/*--
474 Knuth's increments seem to work better
475 than Incerpi-Sedgewick here. Possibly
476 because the number of elems to sort is
477 usually small, typically <= 20.
478--*/
479static
480Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
481 9841, 29524, 88573, 265720,
482 797161, 2391484 };
483
484static
485void mainSimpleSort ( UInt32* ptr,
486 UChar* block,
487 UInt16* quadrant,
488 Int32 nblock,
489 Int32 lo,
490 Int32 hi,
491 Int32 d,
492 Int32* budget )
493{
494 Int32 i, j, h, bigN, hp;
495 UInt32 v;
496
497 bigN = hi - lo + 1;
498 if (bigN < 2) return;
499
500 hp = 0;
501 while (incs[hp] < bigN) hp++;
502 hp--;
503
504 for (; hp >= 0; hp--) {
505 h = incs[hp];
506
507 i = lo + h;
508 while (True) {
509
510 /*-- copy 1 --*/
511 if (i > hi) break;
512 v = ptr[i];
513 j = i;
514 while ( mainGtU (
515 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
516 ) ) {
517 ptr[j] = ptr[j-h];
518 j = j - h;
519 if (j <= (lo + h - 1)) break;
520 }
521 ptr[j] = v;
522 i++;
523
524 /*-- copy 2 --*/
525 if (i > hi) break;
526 v = ptr[i];
527 j = i;
528 while ( mainGtU (
529 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
530 ) ) {
531 ptr[j] = ptr[j-h];
532 j = j - h;
533 if (j <= (lo + h - 1)) break;
534 }
535 ptr[j] = v;
536 i++;
537
538 /*-- copy 3 --*/
539 if (i > hi) break;
540 v = ptr[i];
541 j = i;
542 while ( mainGtU (
543 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
544 ) ) {
545 ptr[j] = ptr[j-h];
546 j = j - h;
547 if (j <= (lo + h - 1)) break;
548 }
549 ptr[j] = v;
550 i++;
551
552 if (*budget < 0) return;
553 }
554 }
555}
556
557
558/*---------------------------------------------*/
559/*--
560 The following is an implementation of
561 an elegant 3-way quicksort for strings,
562 described in a paper "Fast Algorithms for
563 Sorting and Searching Strings", by Robert
564 Sedgewick and Jon L. Bentley.
565--*/
566
567#define mswap(zz1, zz2) \
568 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
569
570#define mvswap(zzp1, zzp2, zzn) \
571{ \
572 Int32 yyp1 = (zzp1); \
573 Int32 yyp2 = (zzp2); \
574 Int32 yyn = (zzn); \
575 while (yyn > 0) { \
576 mswap(ptr[yyp1], ptr[yyp2]); \
577 yyp1++; yyp2++; yyn--; \
578 } \
579}
580
581static
582__inline__
583UChar mmed3 ( UChar a, UChar b, UChar c )
584{
585 UChar t;
586 if (a > b) { t = a; a = b; b = t; };
587 if (b > c) {
588 b = c;
589 if (a > b) b = a;
590 }
591 return b;
592}
593
594#define mmin(a,b) ((a) < (b)) ? (a) : (b)
595
596#define mpush(lz,hz,dz) { stackLo[sp] = lz; \
597 stackHi[sp] = hz; \
598 stackD [sp] = dz; \
599 sp++; }
600
601#define mpop(lz,hz,dz) { sp--; \
602 lz = stackLo[sp]; \
603 hz = stackHi[sp]; \
604 dz = stackD [sp]; }
605
606
607#define mnextsize(az) (nextHi[az]-nextLo[az])
608
609#define mnextswap(az,bz) \
610 { Int32 tz; \
611 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
612 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
613 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
614
615
616#define MAIN_QSORT_SMALL_THRESH 20
617#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
618#define MAIN_QSORT_STACK_SIZE 100
619
620static
621void mainQSort3 ( UInt32* ptr,
622 UChar* block,
623 UInt16* quadrant,
624 Int32 nblock,
625 Int32 loSt,
626 Int32 hiSt,
627 Int32 dSt,
628 Int32* budget )
629{
630 Int32 unLo, unHi, ltLo, gtHi, n, m, med;
631 Int32 sp, lo, hi, d;
632
633 Int32 stackLo[MAIN_QSORT_STACK_SIZE];
634 Int32 stackHi[MAIN_QSORT_STACK_SIZE];
635 Int32 stackD [MAIN_QSORT_STACK_SIZE];
636
637 Int32 nextLo[3];
638 Int32 nextHi[3];
639 Int32 nextD [3];
640
641 sp = 0;
642 mpush ( loSt, hiSt, dSt );
643
644 while (sp > 0) {
645
646 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
647
648 mpop ( lo, hi, d );
649 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
650 d > MAIN_QSORT_DEPTH_THRESH) {
651 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
652 if (*budget < 0) return;
653 continue;
654 }
655
656 med = (Int32)
657 mmed3 ( block[ptr[ lo ]+d],
658 block[ptr[ hi ]+d],
659 block[ptr[ (lo+hi)>>1 ]+d] );
660
661 unLo = ltLo = lo;
662 unHi = gtHi = hi;
663
664 while (True) {
665 while (True) {
666 if (unLo > unHi) break;
667 n = ((Int32)block[ptr[unLo]+d]) - med;
668 if (n == 0) {
669 mswap(ptr[unLo], ptr[ltLo]);
670 ltLo++; unLo++; continue;
671 };
672 if (n > 0) break;
673 unLo++;
674 }
675 while (True) {
676 if (unLo > unHi) break;
677 n = ((Int32)block[ptr[unHi]+d]) - med;
678 if (n == 0) {
679 mswap(ptr[unHi], ptr[gtHi]);
680 gtHi--; unHi--; continue;
681 };
682 if (n < 0) break;
683 unHi--;
684 }
685 if (unLo > unHi) break;
686 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
687 }
688
689 AssertD ( unHi == unLo-1, "mainQSort3(2)" );
690
691 if (gtHi < ltLo) {
692 mpush(lo, hi, d+1 );
693 continue;
694 }
695
696 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
697 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
698
699 n = lo + unLo - ltLo - 1;
700 m = hi - (gtHi - unHi) + 1;
701
702 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
703 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
704 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
705
706 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
707 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
708 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
709
710 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
711 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
712
713 mpush (nextLo[0], nextHi[0], nextD[0]);
714 mpush (nextLo[1], nextHi[1], nextD[1]);
715 mpush (nextLo[2], nextHi[2], nextD[2]);
716 }
717}
718
719#undef mswap
720#undef mvswap
721#undef mpush
722#undef mpop
723#undef mmin
724#undef mnextsize
725#undef mnextswap
726#undef MAIN_QSORT_SMALL_THRESH
727#undef MAIN_QSORT_DEPTH_THRESH
728#undef MAIN_QSORT_STACK_SIZE
729
730
731/*---------------------------------------------*/
732/* Pre:
733 nblock > N_OVERSHOOT
734 block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
735 ((UChar*)block32) [0 .. nblock-1] holds block
736 ptr exists for [0 .. nblock-1]
737
738 Post:
739 ((UChar*)block32) [0 .. nblock-1] holds block
740 All other areas of block32 destroyed
741 ftab [0 .. 65536 ] destroyed
742 ptr [0 .. nblock-1] holds sorted order
743 if (*budget < 0), sorting was abandoned
744*/
745
746#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
747#define SETMASK (1 << 21)
748#define CLEARMASK (~(SETMASK))
749
750static
751void mainSort ( UInt32* ptr,
752 UChar* block,
753 UInt16* quadrant,
754 UInt32* ftab,
755 Int32 nblock,
756 Int32 verb,
757 Int32* budget )
758{
759 Int32 i, j, k, ss, sb;
760 Int32 runningOrder[256];
761 Bool bigDone[256];
762 Int32 copyStart[256];
763 Int32 copyEnd [256];
764 UChar c1;
765 Int32 numQSorted;
766 UInt16 s;
767 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
768
769 /*-- set up the 2-byte frequency table --*/
770 for (i = 65536; i >= 0; i--) ftab[i] = 0;
771
772 j = block[0] << 8;
773 i = nblock-1;
774 for (; i >= 3; i -= 4) {
775 quadrant[i] = 0;
776 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
777 ftab[j]++;
778 quadrant[i-1] = 0;
779 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
780 ftab[j]++;
781 quadrant[i-2] = 0;
782 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
783 ftab[j]++;
784 quadrant[i-3] = 0;
785 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
786 ftab[j]++;
787 }
788 for (; i >= 0; i--) {
789 quadrant[i] = 0;
790 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
791 ftab[j]++;
792 }
793
794 /*-- (emphasises close relationship of block & quadrant) --*/
795 for (i = 0; i < BZ_N_OVERSHOOT; i++) {
796 block [nblock+i] = block[i];
797 quadrant[nblock+i] = 0;
798 }
799
800 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
801
802 /*-- Complete the initial radix sort --*/
803 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
804
805 s = block[0] << 8;
806 i = nblock-1;
807 for (; i >= 3; i -= 4) {
808 s = (s >> 8) | (block[i] << 8);
809 j = ftab[s] -1;
810 ftab[s] = j;
811 ptr[j] = i;
812 s = (s >> 8) | (block[i-1] << 8);
813 j = ftab[s] -1;
814 ftab[s] = j;
815 ptr[j] = i-1;
816 s = (s >> 8) | (block[i-2] << 8);
817 j = ftab[s] -1;
818 ftab[s] = j;
819 ptr[j] = i-2;
820 s = (s >> 8) | (block[i-3] << 8);
821 j = ftab[s] -1;
822 ftab[s] = j;
823 ptr[j] = i-3;
824 }
825 for (; i >= 0; i--) {
826 s = (s >> 8) | (block[i] << 8);
827 j = ftab[s] -1;
828 ftab[s] = j;
829 ptr[j] = i;
830 }
831
832 /*--
833 Now ftab contains the first loc of every small bucket.
834 Calculate the running order, from smallest to largest
835 big bucket.
836 --*/
837 for (i = 0; i <= 255; i++) {
838 bigDone [i] = False;
839 runningOrder[i] = i;
840 }
841
842 {
843 Int32 vv;
844 Int32 h = 1;
845 do h = 3 * h + 1; while (h <= 256);
846 do {
847 h = h / 3;
848 for (i = h; i <= 255; i++) {
849 vv = runningOrder[i];
850 j = i;
851 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
852 runningOrder[j] = runningOrder[j-h];
853 j = j - h;
854 if (j <= (h - 1)) goto zero;
855 }
856 zero:
857 runningOrder[j] = vv;
858 }
859 } while (h != 1);
860 }
861
862 /*--
863 The main sorting loop.
864 --*/
865
866 numQSorted = 0;
867
868 for (i = 0; i <= 255; i++) {
869
870 /*--
871 Process big buckets, starting with the least full.
872 Basically this is a 3-step process in which we call
873 mainQSort3 to sort the small buckets [ss, j], but
874 also make a big effort to avoid the calls if we can.
875 --*/
876 ss = runningOrder[i];
877
878 /*--
879 Step 1:
880 Complete the big bucket [ss] by quicksorting
881 any unsorted small buckets [ss, j], for j != ss.
882 Hopefully previous pointer-scanning phases have already
883 completed many of the small buckets [ss, j], so
884 we don't have to sort them at all.
885 --*/
886 for (j = 0; j <= 255; j++) {
887 if (j != ss) {
888 sb = (ss << 8) + j;
889 if ( ! (ftab[sb] & SETMASK) ) {
890 Int32 lo = ftab[sb] & CLEARMASK;
891 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
892 if (hi > lo) {
893 if (verb >= 4)
894 VPrintf4 ( " qsort [0x%x, 0x%x] "
895 "done %d this %d\n",
896 ss, j, numQSorted, hi - lo + 1 );
897 mainQSort3 (
898 ptr, block, quadrant, nblock,
899 lo, hi, BZ_N_RADIX, budget
900 );
901 numQSorted += (hi - lo + 1);
902 if (*budget < 0) return;
903 }
904 }
905 ftab[sb] |= SETMASK;
906 }
907 }
908
909 AssertH ( !bigDone[ss], 1006 );
910
911 /*--
912 Step 2:
913 Now scan this big bucket [ss] so as to synthesise the
914 sorted order for small buckets [t, ss] for all t,
915 including, magically, the bucket [ss,ss] too.
916 This will avoid doing Real Work in subsequent Step 1's.
917 --*/
918 {
919 for (j = 0; j <= 255; j++) {
920 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
921 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
922 }
923 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
924 k = ptr[j]-1; if (k < 0) k += nblock;
925 c1 = block[k];
926 if (!bigDone[c1])
927 ptr[ copyStart[c1]++ ] = k;
928 }
929 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
930 k = ptr[j]-1; if (k < 0) k += nblock;
931 c1 = block[k];
932 if (!bigDone[c1])
933 ptr[ copyEnd[c1]-- ] = k;
934 }
935 }
936
937 AssertH ( (copyStart[ss]-1 == copyEnd[ss])
938 ||
939 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
940 Necessity for this case is demonstrated by compressing
941 a sequence of approximately 48.5 million of character
942 251; 1.0.0/1.0.1 will then die here. */
943 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
944 1007 )
945
946 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
947
948 /*--
949 Step 3:
950 The [ss] big bucket is now done. Record this fact,
951 and update the quadrant descriptors. Remember to
952 update quadrants in the overshoot area too, if
953 necessary. The "if (i < 255)" test merely skips
954 this updating for the last bucket processed, since
955 updating for the last bucket is pointless.
956
957 The quadrant array provides a way to incrementally
958 cache sort orderings, as they appear, so as to
959 make subsequent comparisons in fullGtU() complete
960 faster. For repetitive blocks this makes a big
961 difference (but not big enough to be able to avoid
962 the fallback sorting mechanism, exponential radix sort).
963
964 The precise meaning is: at all times:
965
966 for 0 <= i < nblock and 0 <= j <= nblock
967
968 if block[i] != block[j],
969
970 then the relative values of quadrant[i] and
971 quadrant[j] are meaningless.
972
973 else {
974 if quadrant[i] < quadrant[j]
975 then the string starting at i lexicographically
976 precedes the string starting at j
977
978 else if quadrant[i] > quadrant[j]
979 then the string starting at j lexicographically
980 precedes the string starting at i
981
982 else
983 the relative ordering of the strings starting
984 at i and j has not yet been determined.
985 }
986 --*/
987 bigDone[ss] = True;
988
989 if (i < 255) {
990 Int32 bbStart = ftab[ss << 8] & CLEARMASK;
991 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
992 Int32 shifts = 0;
993
994 while ((bbSize >> shifts) > 65534) shifts++;
995
996 for (j = bbSize-1; j >= 0; j--) {
997 Int32 a2update = ptr[bbStart + j];
998 UInt16 qVal = (UInt16)(j >> shifts);
999 quadrant[a2update] = qVal;
1000 if (a2update < BZ_N_OVERSHOOT)
1001 quadrant[a2update + nblock] = qVal;
1002 }
1003 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
1004 }
1005
1006 }
1007
1008 if (verb >= 4)
1009 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
1010 nblock, numQSorted, nblock - numQSorted );
1011}
1012
1013#undef BIGFREQ
1014#undef SETMASK
1015#undef CLEARMASK
1016
1017
1018/*---------------------------------------------*/
1019/* Pre:
1020 nblock > 0
1021 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1022 ((UChar*)arr2) [0 .. nblock-1] holds block
1023 arr1 exists for [0 .. nblock-1]
1024
1025 Post:
1026 ((UChar*)arr2) [0 .. nblock-1] holds block
1027 All other areas of block destroyed
1028 ftab [ 0 .. 65536 ] destroyed
1029 arr1 [0 .. nblock-1] holds sorted order
1030*/
1031void BZ2_blockSort ( EState* s )
1032{
1033 UInt32* ptr = s->ptr;
1034 UChar* block = s->block;
1035 UInt32* ftab = s->ftab;
1036 Int32 nblock = s->nblock;
1037 Int32 verb = s->verbosity;
1038 Int32 wfact = s->workFactor;
1039 UInt16* quadrant;
1040 Int32 budget;
1041 Int32 budgetInit;
1042 Int32 i;
1043
1044 if (nblock < 10000) {
1045 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1046 } else {
1047 /* Calculate the location for quadrant, remembering to get
1048 the alignment right. Assumes that &(block[0]) is at least
1049 2-byte aligned -- this should be ok since block is really
1050 the first section of arr2.
1051 */
1052 i = nblock+BZ_N_OVERSHOOT;
1053 if (i & 1) i++;
1054 quadrant = (UInt16*)(&(block[i]));
1055
1056 /* (wfact-1) / 3 puts the default-factor-30
1057 transition point at very roughly the same place as
1058 with v0.1 and v0.9.0.
1059 Not that it particularly matters any more, since the
1060 resulting compressed stream is now the same regardless
1061 of whether or not we use the main sort or fallback sort.
1062 */
1063 if (wfact < 1 ) wfact = 1;
1064 if (wfact > 100) wfact = 100;
1065 budgetInit = nblock * ((wfact-1) / 3);
1066 budget = budgetInit;
1067
1068 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1069 if (verb >= 3)
1070 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1071 budgetInit - budget,
1072 nblock,
1073 (float)(budgetInit - budget) /
1074 (float)(nblock==0 ? 1 : nblock) );
1075 if (budget < 0) {
1076 if (verb >= 2)
1077 VPrintf0 ( " too repetitive; using fallback"
1078 " sorting algorithm\n" );
1079 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1080 }
1081 }
1082
1083 s->origPtr = -1;
1084 for (i = 0; i < s->nblock; i++)
1085 if (ptr[i] == 0)
1086 { s->origPtr = i; break; };
1087
1088 AssertH( s->origPtr != -1, 1003 );
1089}
1090
1091
1092/*-------------------------------------------------------------*/
1093/*--- end blocksort.c ---*/
1094/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/bzlib.c b/utils/bzip2/bzlib.c
new file mode 100644
index 0000000000..6e78e19407
--- /dev/null
+++ b/utils/bzip2/bzlib.c
@@ -0,0 +1,1572 @@
1
2/*-------------------------------------------------------------*/
3/*--- Library top-level functions. ---*/
4/*--- bzlib.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21/* CHANGES
22 0.9.0 -- original version.
23 0.9.0a/b -- no changes in this file.
24 0.9.0c -- made zero-length BZ_FLUSH work correctly in bzCompress().
25 fixed bzWrite/bzRead to ignore zero-length requests.
26 fixed bzread to correctly handle read requests after EOF.
27 wrong parameter order in call to bzDecompressInit in
28 bzBuffToBuffDecompress. Fixed.
29*/
30
31#include "bzlib_private.h"
32
33
34/*---------------------------------------------------*/
35/*--- Compression stuff ---*/
36/*---------------------------------------------------*/
37
38
39/*---------------------------------------------------*/
40#ifndef BZ_NO_STDIO
41void BZ2_bz__AssertH__fail ( int errcode )
42{
43 fprintf(stderr,
44 "\n\nbzip2/libbzip2: internal error number %d.\n"
45 "This is a bug in bzip2/libbzip2, %s.\n"
46 "Please report it to me at: jseward@bzip.org. If this happened\n"
47 "when you were using some program which uses libbzip2 as a\n"
48 "component, you should also report this bug to the author(s)\n"
49 "of that program. Please make an effort to report this bug;\n"
50 "timely and accurate bug reports eventually lead to higher\n"
51 "quality software. Thanks. Julian Seward, 10 December 2007.\n\n",
52 errcode,
53 BZ2_bzlibVersion()
54 );
55
56 if (errcode == 1007) {
57 fprintf(stderr,
58 "\n*** A special note about internal error number 1007 ***\n"
59 "\n"
60 "Experience suggests that a common cause of i.e. 1007\n"
61 "is unreliable memory or other hardware. The 1007 assertion\n"
62 "just happens to cross-check the results of huge numbers of\n"
63 "memory reads/writes, and so acts (unintendedly) as a stress\n"
64 "test of your memory system.\n"
65 "\n"
66 "I suggest the following: try compressing the file again,\n"
67 "possibly monitoring progress in detail with the -vv flag.\n"
68 "\n"
69 "* If the error cannot be reproduced, and/or happens at different\n"
70 " points in compression, you may have a flaky memory system.\n"
71 " Try a memory-test program. I have used Memtest86\n"
72 " (www.memtest86.com). At the time of writing it is free (GPLd).\n"
73 " Memtest86 tests memory much more thorougly than your BIOSs\n"
74 " power-on test, and may find failures that the BIOS doesn't.\n"
75 "\n"
76 "* If the error can be repeatably reproduced, this is a bug in\n"
77 " bzip2, and I would very much like to hear about it. Please\n"
78 " let me know, and, ideally, save a copy of the file causing the\n"
79 " problem -- without which I will be unable to investigate it.\n"
80 "\n"
81 );
82 }
83
84 exit(3);
85}
86#endif
87
88
89/*---------------------------------------------------*/
90static
91int bz_config_ok ( void )
92{
93 if (sizeof(int) != 4) return 0;
94 if (sizeof(short) != 2) return 0;
95 if (sizeof(char) != 1) return 0;
96 return 1;
97}
98
99
100/*---------------------------------------------------*/
101static
102void* default_bzalloc ( void* opaque, Int32 items, Int32 size )
103{
104 void* v = malloc ( items * size );
105 return v;
106}
107
108static
109void default_bzfree ( void* opaque, void* addr )
110{
111 if (addr != NULL) free ( addr );
112}
113
114
115/*---------------------------------------------------*/
116static
117void prepare_new_block ( EState* s )
118{
119 Int32 i;
120 s->nblock = 0;
121 s->numZ = 0;
122 s->state_out_pos = 0;
123 BZ_INITIALISE_CRC ( s->blockCRC );
124 for (i = 0; i < 256; i++) s->inUse[i] = False;
125 s->blockNo++;
126}
127
128
129/*---------------------------------------------------*/
130static
131void init_RL ( EState* s )
132{
133 s->state_in_ch = 256;
134 s->state_in_len = 0;
135}
136
137
138static
139Bool isempty_RL ( EState* s )
140{
141 if (s->state_in_ch < 256 && s->state_in_len > 0)
142 return False; else
143 return True;
144}
145
146
147/*---------------------------------------------------*/
148int BZ_API(BZ2_bzCompressInit)
149 ( bz_stream* strm,
150 int blockSize100k,
151 int verbosity,
152 int workFactor )
153{
154 Int32 n;
155 EState* s;
156
157 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
158
159 if (strm == NULL ||
160 blockSize100k < 1 || blockSize100k > 9 ||
161 workFactor < 0 || workFactor > 250)
162 return BZ_PARAM_ERROR;
163
164 if (workFactor == 0) workFactor = 30;
165 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
166 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
167
168 s = BZALLOC( sizeof(EState) );
169 if (s == NULL) return BZ_MEM_ERROR;
170 s->strm = strm;
171
172 s->arr1 = NULL;
173 s->arr2 = NULL;
174 s->ftab = NULL;
175
176 n = 100000 * blockSize100k;
177 s->arr1 = BZALLOC( n * sizeof(UInt32) );
178 s->arr2 = BZALLOC( (n+BZ_N_OVERSHOOT) * sizeof(UInt32) );
179 s->ftab = BZALLOC( 65537 * sizeof(UInt32) );
180
181 if (s->arr1 == NULL || s->arr2 == NULL || s->ftab == NULL) {
182 if (s->arr1 != NULL) BZFREE(s->arr1);
183 if (s->arr2 != NULL) BZFREE(s->arr2);
184 if (s->ftab != NULL) BZFREE(s->ftab);
185 if (s != NULL) BZFREE(s);
186 return BZ_MEM_ERROR;
187 }
188
189 s->blockNo = 0;
190 s->state = BZ_S_INPUT;
191 s->mode = BZ_M_RUNNING;
192 s->combinedCRC = 0;
193 s->blockSize100k = blockSize100k;
194 s->nblockMAX = 100000 * blockSize100k - 19;
195 s->verbosity = verbosity;
196 s->workFactor = workFactor;
197
198 s->block = (UChar*)s->arr2;
199 s->mtfv = (UInt16*)s->arr1;
200 s->zbits = NULL;
201 s->ptr = (UInt32*)s->arr1;
202
203 strm->state = s;
204 strm->total_in_lo32 = 0;
205 strm->total_in_hi32 = 0;
206 strm->total_out_lo32 = 0;
207 strm->total_out_hi32 = 0;
208 init_RL ( s );
209 prepare_new_block ( s );
210 return BZ_OK;
211}
212
213
214/*---------------------------------------------------*/
215static
216void add_pair_to_block ( EState* s )
217{
218 Int32 i;
219 UChar ch = (UChar)(s->state_in_ch);
220 for (i = 0; i < s->state_in_len; i++) {
221 BZ_UPDATE_CRC( s->blockCRC, ch );
222 }
223 s->inUse[s->state_in_ch] = True;
224 switch (s->state_in_len) {
225 case 1:
226 s->block[s->nblock] = (UChar)ch; s->nblock++;
227 break;
228 case 2:
229 s->block[s->nblock] = (UChar)ch; s->nblock++;
230 s->block[s->nblock] = (UChar)ch; s->nblock++;
231 break;
232 case 3:
233 s->block[s->nblock] = (UChar)ch; s->nblock++;
234 s->block[s->nblock] = (UChar)ch; s->nblock++;
235 s->block[s->nblock] = (UChar)ch; s->nblock++;
236 break;
237 default:
238 s->inUse[s->state_in_len-4] = True;
239 s->block[s->nblock] = (UChar)ch; s->nblock++;
240 s->block[s->nblock] = (UChar)ch; s->nblock++;
241 s->block[s->nblock] = (UChar)ch; s->nblock++;
242 s->block[s->nblock] = (UChar)ch; s->nblock++;
243 s->block[s->nblock] = ((UChar)(s->state_in_len-4));
244 s->nblock++;
245 break;
246 }
247}
248
249
250/*---------------------------------------------------*/
251static
252void flush_RL ( EState* s )
253{
254 if (s->state_in_ch < 256) add_pair_to_block ( s );
255 init_RL ( s );
256}
257
258
259/*---------------------------------------------------*/
260#define ADD_CHAR_TO_BLOCK(zs,zchh0) \
261{ \
262 UInt32 zchh = (UInt32)(zchh0); \
263 /*-- fast track the common case --*/ \
264 if (zchh != zs->state_in_ch && \
265 zs->state_in_len == 1) { \
266 UChar ch = (UChar)(zs->state_in_ch); \
267 BZ_UPDATE_CRC( zs->blockCRC, ch ); \
268 zs->inUse[zs->state_in_ch] = True; \
269 zs->block[zs->nblock] = (UChar)ch; \
270 zs->nblock++; \
271 zs->state_in_ch = zchh; \
272 } \
273 else \
274 /*-- general, uncommon cases --*/ \
275 if (zchh != zs->state_in_ch || \
276 zs->state_in_len == 255) { \
277 if (zs->state_in_ch < 256) \
278 add_pair_to_block ( zs ); \
279 zs->state_in_ch = zchh; \
280 zs->state_in_len = 1; \
281 } else { \
282 zs->state_in_len++; \
283 } \
284}
285
286
287/*---------------------------------------------------*/
288static
289Bool copy_input_until_stop ( EState* s )
290{
291 Bool progress_in = False;
292
293 if (s->mode == BZ_M_RUNNING) {
294
295 /*-- fast track the common case --*/
296 while (True) {
297 /*-- block full? --*/
298 if (s->nblock >= s->nblockMAX) break;
299 /*-- no input? --*/
300 if (s->strm->avail_in == 0) break;
301 progress_in = True;
302 ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) );
303 s->strm->next_in++;
304 s->strm->avail_in--;
305 s->strm->total_in_lo32++;
306 if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;
307 }
308
309 } else {
310
311 /*-- general, uncommon case --*/
312 while (True) {
313 /*-- block full? --*/
314 if (s->nblock >= s->nblockMAX) break;
315 /*-- no input? --*/
316 if (s->strm->avail_in == 0) break;
317 /*-- flush/finish end? --*/
318 if (s->avail_in_expect == 0) break;
319 progress_in = True;
320 ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) );
321 s->strm->next_in++;
322 s->strm->avail_in--;
323 s->strm->total_in_lo32++;
324 if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;
325 s->avail_in_expect--;
326 }
327 }
328 return progress_in;
329}
330
331
332/*---------------------------------------------------*/
333static
334Bool copy_output_until_stop ( EState* s )
335{
336 Bool progress_out = False;
337
338 while (True) {
339
340 /*-- no output space? --*/
341 if (s->strm->avail_out == 0) break;
342
343 /*-- block done? --*/
344 if (s->state_out_pos >= s->numZ) break;
345
346 progress_out = True;
347 *(s->strm->next_out) = s->zbits[s->state_out_pos];
348 s->state_out_pos++;
349 s->strm->avail_out--;
350 s->strm->next_out++;
351 s->strm->total_out_lo32++;
352 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
353 }
354
355 return progress_out;
356}
357
358
359/*---------------------------------------------------*/
360static
361Bool handle_compress ( bz_stream* strm )
362{
363 Bool progress_in = False;
364 Bool progress_out = False;
365 EState* s = strm->state;
366
367 while (True) {
368
369 if (s->state == BZ_S_OUTPUT) {
370 progress_out |= copy_output_until_stop ( s );
371 if (s->state_out_pos < s->numZ) break;
372 if (s->mode == BZ_M_FINISHING &&
373 s->avail_in_expect == 0 &&
374 isempty_RL(s)) break;
375 prepare_new_block ( s );
376 s->state = BZ_S_INPUT;
377 if (s->mode == BZ_M_FLUSHING &&
378 s->avail_in_expect == 0 &&
379 isempty_RL(s)) break;
380 }
381
382 if (s->state == BZ_S_INPUT) {
383 progress_in |= copy_input_until_stop ( s );
384 if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
385 flush_RL ( s );
386 BZ2_compressBlock ( s, (Bool)(s->mode == BZ_M_FINISHING) );
387 s->state = BZ_S_OUTPUT;
388 }
389 else
390 if (s->nblock >= s->nblockMAX) {
391 BZ2_compressBlock ( s, False );
392 s->state = BZ_S_OUTPUT;
393 }
394 else
395 if (s->strm->avail_in == 0) {
396 break;
397 }
398 }
399
400 }
401
402 return progress_in || progress_out;
403}
404
405
406/*---------------------------------------------------*/
407int BZ_API(BZ2_bzCompress) ( bz_stream *strm, int action )
408{
409 Bool progress;
410 EState* s;
411 if (strm == NULL) return BZ_PARAM_ERROR;
412 s = strm->state;
413 if (s == NULL) return BZ_PARAM_ERROR;
414 if (s->strm != strm) return BZ_PARAM_ERROR;
415
416 preswitch:
417 switch (s->mode) {
418
419 case BZ_M_IDLE:
420 return BZ_SEQUENCE_ERROR;
421
422 case BZ_M_RUNNING:
423 if (action == BZ_RUN) {
424 progress = handle_compress ( strm );
425 return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;
426 }
427 else
428 if (action == BZ_FLUSH) {
429 s->avail_in_expect = strm->avail_in;
430 s->mode = BZ_M_FLUSHING;
431 goto preswitch;
432 }
433 else
434 if (action == BZ_FINISH) {
435 s->avail_in_expect = strm->avail_in;
436 s->mode = BZ_M_FINISHING;
437 goto preswitch;
438 }
439 else
440 return BZ_PARAM_ERROR;
441
442 case BZ_M_FLUSHING:
443 if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR;
444 if (s->avail_in_expect != s->strm->avail_in)
445 return BZ_SEQUENCE_ERROR;
446 progress = handle_compress ( strm );
447 if (s->avail_in_expect > 0 || !isempty_RL(s) ||
448 s->state_out_pos < s->numZ) return BZ_FLUSH_OK;
449 s->mode = BZ_M_RUNNING;
450 return BZ_RUN_OK;
451
452 case BZ_M_FINISHING:
453 if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR;
454 if (s->avail_in_expect != s->strm->avail_in)
455 return BZ_SEQUENCE_ERROR;
456 progress = handle_compress ( strm );
457 if (!progress) return BZ_SEQUENCE_ERROR;
458 if (s->avail_in_expect > 0 || !isempty_RL(s) ||
459 s->state_out_pos < s->numZ) return BZ_FINISH_OK;
460 s->mode = BZ_M_IDLE;
461 return BZ_STREAM_END;
462 }
463 return BZ_OK; /*--not reached--*/
464}
465
466
467/*---------------------------------------------------*/
468int BZ_API(BZ2_bzCompressEnd) ( bz_stream *strm )
469{
470 EState* s;
471 if (strm == NULL) return BZ_PARAM_ERROR;
472 s = strm->state;
473 if (s == NULL) return BZ_PARAM_ERROR;
474 if (s->strm != strm) return BZ_PARAM_ERROR;
475
476 if (s->arr1 != NULL) BZFREE(s->arr1);
477 if (s->arr2 != NULL) BZFREE(s->arr2);
478 if (s->ftab != NULL) BZFREE(s->ftab);
479 BZFREE(strm->state);
480
481 strm->state = NULL;
482
483 return BZ_OK;
484}
485
486
487/*---------------------------------------------------*/
488/*--- Decompression stuff ---*/
489/*---------------------------------------------------*/
490
491/*---------------------------------------------------*/
492int BZ_API(BZ2_bzDecompressInit)
493 ( bz_stream* strm,
494 int verbosity,
495 int small )
496{
497 DState* s;
498
499 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
500
501 if (strm == NULL) return BZ_PARAM_ERROR;
502 if (small != 0 && small != 1) return BZ_PARAM_ERROR;
503 if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
504
505 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
506 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
507
508 s = BZALLOC( sizeof(DState) );
509 if (s == NULL) return BZ_MEM_ERROR;
510 s->strm = strm;
511 strm->state = s;
512 s->state = BZ_X_MAGIC_1;
513 s->bsLive = 0;
514 s->bsBuff = 0;
515 s->calculatedCombinedCRC = 0;
516 strm->total_in_lo32 = 0;
517 strm->total_in_hi32 = 0;
518 strm->total_out_lo32 = 0;
519 strm->total_out_hi32 = 0;
520 s->smallDecompress = (Bool)small;
521 s->ll4 = NULL;
522 s->ll16 = NULL;
523 s->tt = NULL;
524 s->currBlockNo = 0;
525 s->verbosity = verbosity;
526
527 return BZ_OK;
528}
529
530
531/*---------------------------------------------------*/
532/* Return True iff data corruption is discovered.
533 Returns False if there is no problem.
534*/
535static
536Bool unRLE_obuf_to_output_FAST ( DState* s )
537{
538 UChar k1;
539
540 if (s->blockRandomised) {
541
542 while (True) {
543 /* try to finish existing run */
544 while (True) {
545 if (s->strm->avail_out == 0) return False;
546 if (s->state_out_len == 0) break;
547 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
548 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
549 s->state_out_len--;
550 s->strm->next_out++;
551 s->strm->avail_out--;
552 s->strm->total_out_lo32++;
553 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
554 }
555
556 /* can a new run be started? */
557 if (s->nblock_used == s->save_nblock+1) return False;
558
559 /* Only caused by corrupt data stream? */
560 if (s->nblock_used > s->save_nblock+1)
561 return True;
562
563 s->state_out_len = 1;
564 s->state_out_ch = s->k0;
565 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
566 k1 ^= BZ_RAND_MASK; s->nblock_used++;
567 if (s->nblock_used == s->save_nblock+1) continue;
568 if (k1 != s->k0) { s->k0 = k1; continue; };
569
570 s->state_out_len = 2;
571 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
572 k1 ^= BZ_RAND_MASK; s->nblock_used++;
573 if (s->nblock_used == s->save_nblock+1) continue;
574 if (k1 != s->k0) { s->k0 = k1; continue; };
575
576 s->state_out_len = 3;
577 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
578 k1 ^= BZ_RAND_MASK; s->nblock_used++;
579 if (s->nblock_used == s->save_nblock+1) continue;
580 if (k1 != s->k0) { s->k0 = k1; continue; };
581
582 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
583 k1 ^= BZ_RAND_MASK; s->nblock_used++;
584 s->state_out_len = ((Int32)k1) + 4;
585 BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK;
586 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
587 }
588
589 } else {
590
591 /* restore */
592 UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC;
593 UChar c_state_out_ch = s->state_out_ch;
594 Int32 c_state_out_len = s->state_out_len;
595 Int32 c_nblock_used = s->nblock_used;
596 Int32 c_k0 = s->k0;
597 UInt32* c_tt = s->tt;
598 UInt32 c_tPos = s->tPos;
599 char* cs_next_out = s->strm->next_out;
600 unsigned int cs_avail_out = s->strm->avail_out;
601 Int32 ro_blockSize100k = s->blockSize100k;
602 /* end restore */
603
604 UInt32 avail_out_INIT = cs_avail_out;
605 Int32 s_save_nblockPP = s->save_nblock+1;
606 unsigned int total_out_lo32_old;
607
608 while (True) {
609
610 /* try to finish existing run */
611 if (c_state_out_len > 0) {
612 while (True) {
613 if (cs_avail_out == 0) goto return_notr;
614 if (c_state_out_len == 1) break;
615 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
616 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
617 c_state_out_len--;
618 cs_next_out++;
619 cs_avail_out--;
620 }
621 s_state_out_len_eq_one:
622 {
623 if (cs_avail_out == 0) {
624 c_state_out_len = 1; goto return_notr;
625 };
626 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
627 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
628 cs_next_out++;
629 cs_avail_out--;
630 }
631 }
632 /* Only caused by corrupt data stream? */
633 if (c_nblock_used > s_save_nblockPP)
634 return True;
635
636 /* can a new run be started? */
637 if (c_nblock_used == s_save_nblockPP) {
638 c_state_out_len = 0; goto return_notr;
639 };
640 c_state_out_ch = c_k0;
641 BZ_GET_FAST_C(k1); c_nblock_used++;
642 if (k1 != c_k0) {
643 c_k0 = k1; goto s_state_out_len_eq_one;
644 };
645 if (c_nblock_used == s_save_nblockPP)
646 goto s_state_out_len_eq_one;
647
648 c_state_out_len = 2;
649 BZ_GET_FAST_C(k1); c_nblock_used++;
650 if (c_nblock_used == s_save_nblockPP) continue;
651 if (k1 != c_k0) { c_k0 = k1; continue; };
652
653 c_state_out_len = 3;
654 BZ_GET_FAST_C(k1); c_nblock_used++;
655 if (c_nblock_used == s_save_nblockPP) continue;
656 if (k1 != c_k0) { c_k0 = k1; continue; };
657
658 BZ_GET_FAST_C(k1); c_nblock_used++;
659 c_state_out_len = ((Int32)k1) + 4;
660 BZ_GET_FAST_C(c_k0); c_nblock_used++;
661 }
662
663 return_notr:
664 total_out_lo32_old = s->strm->total_out_lo32;
665 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
666 if (s->strm->total_out_lo32 < total_out_lo32_old)
667 s->strm->total_out_hi32++;
668
669 /* save */
670 s->calculatedBlockCRC = c_calculatedBlockCRC;
671 s->state_out_ch = c_state_out_ch;
672 s->state_out_len = c_state_out_len;
673 s->nblock_used = c_nblock_used;
674 s->k0 = c_k0;
675 s->tt = c_tt;
676 s->tPos = c_tPos;
677 s->strm->next_out = cs_next_out;
678 s->strm->avail_out = cs_avail_out;
679 /* end save */
680 }
681 return False;
682}
683
684
685
686/*---------------------------------------------------*/
687__inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
688{
689 Int32 nb, na, mid;
690 nb = 0;
691 na = 256;
692 do {
693 mid = (nb + na) >> 1;
694 if (indx >= cftab[mid]) nb = mid; else na = mid;
695 }
696 while (na - nb != 1);
697 return nb;
698}
699
700
701/*---------------------------------------------------*/
702/* Return True iff data corruption is discovered.
703 Returns False if there is no problem.
704*/
705static
706Bool unRLE_obuf_to_output_SMALL ( DState* s )
707{
708 UChar k1;
709
710 if (s->blockRandomised) {
711
712 while (True) {
713 /* try to finish existing run */
714 while (True) {
715 if (s->strm->avail_out == 0) return False;
716 if (s->state_out_len == 0) break;
717 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
718 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
719 s->state_out_len--;
720 s->strm->next_out++;
721 s->strm->avail_out--;
722 s->strm->total_out_lo32++;
723 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
724 }
725
726 /* can a new run be started? */
727 if (s->nblock_used == s->save_nblock+1) return False;
728
729 /* Only caused by corrupt data stream? */
730 if (s->nblock_used > s->save_nblock+1)
731 return True;
732
733 s->state_out_len = 1;
734 s->state_out_ch = s->k0;
735 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
736 k1 ^= BZ_RAND_MASK; s->nblock_used++;
737 if (s->nblock_used == s->save_nblock+1) continue;
738 if (k1 != s->k0) { s->k0 = k1; continue; };
739
740 s->state_out_len = 2;
741 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
742 k1 ^= BZ_RAND_MASK; s->nblock_used++;
743 if (s->nblock_used == s->save_nblock+1) continue;
744 if (k1 != s->k0) { s->k0 = k1; continue; };
745
746 s->state_out_len = 3;
747 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
748 k1 ^= BZ_RAND_MASK; s->nblock_used++;
749 if (s->nblock_used == s->save_nblock+1) continue;
750 if (k1 != s->k0) { s->k0 = k1; continue; };
751
752 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
753 k1 ^= BZ_RAND_MASK; s->nblock_used++;
754 s->state_out_len = ((Int32)k1) + 4;
755 BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK;
756 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
757 }
758
759 } else {
760
761 while (True) {
762 /* try to finish existing run */
763 while (True) {
764 if (s->strm->avail_out == 0) return False;
765 if (s->state_out_len == 0) break;
766 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
767 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
768 s->state_out_len--;
769 s->strm->next_out++;
770 s->strm->avail_out--;
771 s->strm->total_out_lo32++;
772 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
773 }
774
775 /* can a new run be started? */
776 if (s->nblock_used == s->save_nblock+1) return False;
777
778 /* Only caused by corrupt data stream? */
779 if (s->nblock_used > s->save_nblock+1)
780 return True;
781
782 s->state_out_len = 1;
783 s->state_out_ch = s->k0;
784 BZ_GET_SMALL(k1); s->nblock_used++;
785 if (s->nblock_used == s->save_nblock+1) continue;
786 if (k1 != s->k0) { s->k0 = k1; continue; };
787
788 s->state_out_len = 2;
789 BZ_GET_SMALL(k1); s->nblock_used++;
790 if (s->nblock_used == s->save_nblock+1) continue;
791 if (k1 != s->k0) { s->k0 = k1; continue; };
792
793 s->state_out_len = 3;
794 BZ_GET_SMALL(k1); s->nblock_used++;
795 if (s->nblock_used == s->save_nblock+1) continue;
796 if (k1 != s->k0) { s->k0 = k1; continue; };
797
798 BZ_GET_SMALL(k1); s->nblock_used++;
799 s->state_out_len = ((Int32)k1) + 4;
800 BZ_GET_SMALL(s->k0); s->nblock_used++;
801 }
802
803 }
804}
805
806
807/*---------------------------------------------------*/
808int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )
809{
810 Bool corrupt;
811 DState* s;
812 if (strm == NULL) return BZ_PARAM_ERROR;
813 s = strm->state;
814 if (s == NULL) return BZ_PARAM_ERROR;
815 if (s->strm != strm) return BZ_PARAM_ERROR;
816
817 while (True) {
818 if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
819 if (s->state == BZ_X_OUTPUT) {
820 if (s->smallDecompress)
821 corrupt = unRLE_obuf_to_output_SMALL ( s ); else
822 corrupt = unRLE_obuf_to_output_FAST ( s );
823 if (corrupt) return BZ_DATA_ERROR;
824 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
825 BZ_FINALISE_CRC ( s->calculatedBlockCRC );
826 if (s->verbosity >= 3)
827 VPrintf2 ( " {0x%08x, 0x%08x}", s->storedBlockCRC,
828 s->calculatedBlockCRC );
829 if (s->verbosity >= 2) VPrintf0 ( "]" );
830 if (s->calculatedBlockCRC != s->storedBlockCRC)
831 return BZ_DATA_ERROR;
832 s->calculatedCombinedCRC
833 = (s->calculatedCombinedCRC << 1) |
834 (s->calculatedCombinedCRC >> 31);
835 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
836 s->state = BZ_X_BLKHDR_1;
837 } else {
838 return BZ_OK;
839 }
840 }
841 if (s->state >= BZ_X_MAGIC_1) {
842 Int32 r = BZ2_decompress ( s );
843 if (r == BZ_STREAM_END) {
844 if (s->verbosity >= 3)
845 VPrintf2 ( "\n combined CRCs: stored = 0x%08x, computed = 0x%08x",
846 s->storedCombinedCRC, s->calculatedCombinedCRC );
847 if (s->calculatedCombinedCRC != s->storedCombinedCRC)
848 return BZ_DATA_ERROR;
849 return r;
850 }
851 if (s->state != BZ_X_OUTPUT) return r;
852 }
853 }
854
855 AssertH ( 0, 6001 );
856
857 return 0; /*NOTREACHED*/
858}
859
860
861/*---------------------------------------------------*/
862int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm )
863{
864 DState* s;
865 if (strm == NULL) return BZ_PARAM_ERROR;
866 s = strm->state;
867 if (s == NULL) return BZ_PARAM_ERROR;
868 if (s->strm != strm) return BZ_PARAM_ERROR;
869
870 if (s->tt != NULL) BZFREE(s->tt);
871 if (s->ll16 != NULL) BZFREE(s->ll16);
872 if (s->ll4 != NULL) BZFREE(s->ll4);
873
874 BZFREE(strm->state);
875 strm->state = NULL;
876
877 return BZ_OK;
878}
879
880
881#ifndef BZ_NO_STDIO
882/*---------------------------------------------------*/
883/*--- File I/O stuff ---*/
884/*---------------------------------------------------*/
885
886#define BZ_SETERR(eee) \
887{ \
888 if (bzerror != NULL) *bzerror = eee; \
889 if (bzf != NULL) bzf->lastErr = eee; \
890}
891
892typedef
893 struct {
894 FILE* handle;
895 Char buf[BZ_MAX_UNUSED];
896 Int32 bufN;
897 Bool writing;
898 bz_stream strm;
899 Int32 lastErr;
900 Bool initialisedOk;
901 }
902 bzFile;
903
904
905/*---------------------------------------------*/
906static Bool myfeof ( FILE* f )
907{
908 Int32 c = fgetc ( f );
909 if (c == EOF) return True;
910 ungetc ( c, f );
911 return False;
912}
913
914
915/*---------------------------------------------------*/
916BZFILE* BZ_API(BZ2_bzWriteOpen)
917 ( int* bzerror,
918 FILE* f,
919 int blockSize100k,
920 int verbosity,
921 int workFactor )
922{
923 Int32 ret;
924 bzFile* bzf = NULL;
925
926 BZ_SETERR(BZ_OK);
927
928 if (f == NULL ||
929 (blockSize100k < 1 || blockSize100k > 9) ||
930 (workFactor < 0 || workFactor > 250) ||
931 (verbosity < 0 || verbosity > 4))
932 { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
933
934 if (ferror(f))
935 { BZ_SETERR(BZ_IO_ERROR); return NULL; };
936
937 bzf = malloc ( sizeof(bzFile) );
938 if (bzf == NULL)
939 { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
940
941 BZ_SETERR(BZ_OK);
942 bzf->initialisedOk = False;
943 bzf->bufN = 0;
944 bzf->handle = f;
945 bzf->writing = True;
946 bzf->strm.bzalloc = NULL;
947 bzf->strm.bzfree = NULL;
948 bzf->strm.opaque = NULL;
949
950 if (workFactor == 0) workFactor = 30;
951 ret = BZ2_bzCompressInit ( &(bzf->strm), blockSize100k,
952 verbosity, workFactor );
953 if (ret != BZ_OK)
954 { BZ_SETERR(ret); free(bzf); return NULL; };
955
956 bzf->strm.avail_in = 0;
957 bzf->initialisedOk = True;
958 return bzf;
959}
960
961
962
963/*---------------------------------------------------*/
964void BZ_API(BZ2_bzWrite)
965 ( int* bzerror,
966 BZFILE* b,
967 void* buf,
968 int len )
969{
970 Int32 n, n2, ret;
971 bzFile* bzf = (bzFile*)b;
972
973 BZ_SETERR(BZ_OK);
974 if (bzf == NULL || buf == NULL || len < 0)
975 { BZ_SETERR(BZ_PARAM_ERROR); return; };
976 if (!(bzf->writing))
977 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
978 if (ferror(bzf->handle))
979 { BZ_SETERR(BZ_IO_ERROR); return; };
980
981 if (len == 0)
982 { BZ_SETERR(BZ_OK); return; };
983
984 bzf->strm.avail_in = len;
985 bzf->strm.next_in = buf;
986
987 while (True) {
988 bzf->strm.avail_out = BZ_MAX_UNUSED;
989 bzf->strm.next_out = bzf->buf;
990 ret = BZ2_bzCompress ( &(bzf->strm), BZ_RUN );
991 if (ret != BZ_RUN_OK)
992 { BZ_SETERR(ret); return; };
993
994 if (bzf->strm.avail_out < BZ_MAX_UNUSED) {
995 n = BZ_MAX_UNUSED - bzf->strm.avail_out;
996 n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar),
997 n, bzf->handle );
998 if (n != n2 || ferror(bzf->handle))
999 { BZ_SETERR(BZ_IO_ERROR); return; };
1000 }
1001
1002 if (bzf->strm.avail_in == 0)
1003 { BZ_SETERR(BZ_OK); return; };
1004 }
1005}
1006
1007
1008/*---------------------------------------------------*/
1009void BZ_API(BZ2_bzWriteClose)
1010 ( int* bzerror,
1011 BZFILE* b,
1012 int abandon,
1013 unsigned int* nbytes_in,
1014 unsigned int* nbytes_out )
1015{
1016 BZ2_bzWriteClose64 ( bzerror, b, abandon,
1017 nbytes_in, NULL, nbytes_out, NULL );
1018}
1019
1020
1021void BZ_API(BZ2_bzWriteClose64)
1022 ( int* bzerror,
1023 BZFILE* b,
1024 int abandon,
1025 unsigned int* nbytes_in_lo32,
1026 unsigned int* nbytes_in_hi32,
1027 unsigned int* nbytes_out_lo32,
1028 unsigned int* nbytes_out_hi32 )
1029{
1030 Int32 n, n2, ret;
1031 bzFile* bzf = (bzFile*)b;
1032
1033 if (bzf == NULL)
1034 { BZ_SETERR(BZ_OK); return; };
1035 if (!(bzf->writing))
1036 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
1037 if (ferror(bzf->handle))
1038 { BZ_SETERR(BZ_IO_ERROR); return; };
1039
1040 if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = 0;
1041 if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = 0;
1042 if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = 0;
1043 if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = 0;
1044
1045 if ((!abandon) && bzf->lastErr == BZ_OK) {
1046 while (True) {
1047 bzf->strm.avail_out = BZ_MAX_UNUSED;
1048 bzf->strm.next_out = bzf->buf;
1049 ret = BZ2_bzCompress ( &(bzf->strm), BZ_FINISH );
1050 if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END)
1051 { BZ_SETERR(ret); return; };
1052
1053 if (bzf->strm.avail_out < BZ_MAX_UNUSED) {
1054 n = BZ_MAX_UNUSED - bzf->strm.avail_out;
1055 n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar),
1056 n, bzf->handle );
1057 if (n != n2 || ferror(bzf->handle))
1058 { BZ_SETERR(BZ_IO_ERROR); return; };
1059 }
1060
1061 if (ret == BZ_STREAM_END) break;
1062 }
1063 }
1064
1065 if ( !abandon && !ferror ( bzf->handle ) ) {
1066 fflush ( bzf->handle );
1067 if (ferror(bzf->handle))
1068 { BZ_SETERR(BZ_IO_ERROR); return; };
1069 }
1070
1071 if (nbytes_in_lo32 != NULL)
1072 *nbytes_in_lo32 = bzf->strm.total_in_lo32;
1073 if (nbytes_in_hi32 != NULL)
1074 *nbytes_in_hi32 = bzf->strm.total_in_hi32;
1075 if (nbytes_out_lo32 != NULL)
1076 *nbytes_out_lo32 = bzf->strm.total_out_lo32;
1077 if (nbytes_out_hi32 != NULL)
1078 *nbytes_out_hi32 = bzf->strm.total_out_hi32;
1079
1080 BZ_SETERR(BZ_OK);
1081 BZ2_bzCompressEnd ( &(bzf->strm) );
1082 free ( bzf );
1083}
1084
1085
1086/*---------------------------------------------------*/
1087BZFILE* BZ_API(BZ2_bzReadOpen)
1088 ( int* bzerror,
1089 FILE* f,
1090 int verbosity,
1091 int small,
1092 void* unused,
1093 int nUnused )
1094{
1095 bzFile* bzf = NULL;
1096 int ret;
1097
1098 BZ_SETERR(BZ_OK);
1099
1100 if (f == NULL ||
1101 (small != 0 && small != 1) ||
1102 (verbosity < 0 || verbosity > 4) ||
1103 (unused == NULL && nUnused != 0) ||
1104 (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED)))
1105 { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
1106
1107 if (ferror(f))
1108 { BZ_SETERR(BZ_IO_ERROR); return NULL; };
1109
1110 bzf = malloc ( sizeof(bzFile) );
1111 if (bzf == NULL)
1112 { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
1113
1114 BZ_SETERR(BZ_OK);
1115
1116 bzf->initialisedOk = False;
1117 bzf->handle = f;
1118 bzf->bufN = 0;
1119 bzf->writing = False;
1120 bzf->strm.bzalloc = NULL;
1121 bzf->strm.bzfree = NULL;
1122 bzf->strm.opaque = NULL;
1123
1124 while (nUnused > 0) {
1125 bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++;
1126 unused = ((void*)( 1 + ((UChar*)(unused)) ));
1127 nUnused--;
1128 }
1129
1130 ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small );
1131 if (ret != BZ_OK)
1132 { BZ_SETERR(ret); free(bzf); return NULL; };
1133
1134 bzf->strm.avail_in = bzf->bufN;
1135 bzf->strm.next_in = bzf->buf;
1136
1137 bzf->initialisedOk = True;
1138 return bzf;
1139}
1140
1141
1142/*---------------------------------------------------*/
1143void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b )
1144{
1145 bzFile* bzf = (bzFile*)b;
1146
1147 BZ_SETERR(BZ_OK);
1148 if (bzf == NULL)
1149 { BZ_SETERR(BZ_OK); return; };
1150
1151 if (bzf->writing)
1152 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
1153
1154 if (bzf->initialisedOk)
1155 (void)BZ2_bzDecompressEnd ( &(bzf->strm) );
1156 free ( bzf );
1157}
1158
1159
1160/*---------------------------------------------------*/
1161int BZ_API(BZ2_bzRead)
1162 ( int* bzerror,
1163 BZFILE* b,
1164 void* buf,
1165 int len )
1166{
1167 Int32 n, ret;
1168 bzFile* bzf = (bzFile*)b;
1169
1170 BZ_SETERR(BZ_OK);
1171
1172 if (bzf == NULL || buf == NULL || len < 0)
1173 { BZ_SETERR(BZ_PARAM_ERROR); return 0; };
1174
1175 if (bzf->writing)
1176 { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; };
1177
1178 if (len == 0)
1179 { BZ_SETERR(BZ_OK); return 0; };
1180
1181 bzf->strm.avail_out = len;
1182 bzf->strm.next_out = buf;
1183
1184 while (True) {
1185
1186 if (ferror(bzf->handle))
1187 { BZ_SETERR(BZ_IO_ERROR); return 0; };
1188
1189 if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) {
1190 n = fread ( bzf->buf, sizeof(UChar),
1191 BZ_MAX_UNUSED, bzf->handle );
1192 if (ferror(bzf->handle))
1193 { BZ_SETERR(BZ_IO_ERROR); return 0; };
1194 bzf->bufN = n;
1195 bzf->strm.avail_in = bzf->bufN;
1196 bzf->strm.next_in = bzf->buf;
1197 }
1198
1199 ret = BZ2_bzDecompress ( &(bzf->strm) );
1200
1201 if (ret != BZ_OK && ret != BZ_STREAM_END)
1202 { BZ_SETERR(ret); return 0; };
1203
1204 if (ret == BZ_OK && myfeof(bzf->handle) &&
1205 bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0)
1206 { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; };
1207
1208 if (ret == BZ_STREAM_END)
1209 { BZ_SETERR(BZ_STREAM_END);
1210 return len - bzf->strm.avail_out; };
1211 if (bzf->strm.avail_out == 0)
1212 { BZ_SETERR(BZ_OK); return len; };
1213
1214 }
1215
1216 return 0; /*not reached*/
1217}
1218
1219
1220/*---------------------------------------------------*/
1221void BZ_API(BZ2_bzReadGetUnused)
1222 ( int* bzerror,
1223 BZFILE* b,
1224 void** unused,
1225 int* nUnused )
1226{
1227 bzFile* bzf = (bzFile*)b;
1228 if (bzf == NULL)
1229 { BZ_SETERR(BZ_PARAM_ERROR); return; };
1230 if (bzf->lastErr != BZ_STREAM_END)
1231 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
1232 if (unused == NULL || nUnused == NULL)
1233 { BZ_SETERR(BZ_PARAM_ERROR); return; };
1234
1235 BZ_SETERR(BZ_OK);
1236 *nUnused = bzf->strm.avail_in;
1237 *unused = bzf->strm.next_in;
1238}
1239#endif
1240
1241
1242/*---------------------------------------------------*/
1243/*--- Misc convenience stuff ---*/
1244/*---------------------------------------------------*/
1245
1246/*---------------------------------------------------*/
1247int BZ_API(BZ2_bzBuffToBuffCompress)
1248 ( char* dest,
1249 unsigned int* destLen,
1250 char* source,
1251 unsigned int sourceLen,
1252 int blockSize100k,
1253 int verbosity,
1254 int workFactor )
1255{
1256 bz_stream strm;
1257 int ret;
1258
1259 if (dest == NULL || destLen == NULL ||
1260 source == NULL ||
1261 blockSize100k < 1 || blockSize100k > 9 ||
1262 verbosity < 0 || verbosity > 4 ||
1263 workFactor < 0 || workFactor > 250)
1264 return BZ_PARAM_ERROR;
1265
1266 if (workFactor == 0) workFactor = 30;
1267 strm.bzalloc = NULL;
1268 strm.bzfree = NULL;
1269 strm.opaque = NULL;
1270 ret = BZ2_bzCompressInit ( &strm, blockSize100k,
1271 verbosity, workFactor );
1272 if (ret != BZ_OK) return ret;
1273
1274 strm.next_in = source;
1275 strm.next_out = dest;
1276 strm.avail_in = sourceLen;
1277 strm.avail_out = *destLen;
1278
1279 ret = BZ2_bzCompress ( &strm, BZ_FINISH );
1280 if (ret == BZ_FINISH_OK) goto output_overflow;
1281 if (ret != BZ_STREAM_END) goto errhandler;
1282
1283 /* normal termination */
1284 *destLen -= strm.avail_out;
1285 BZ2_bzCompressEnd ( &strm );
1286 return BZ_OK;
1287
1288 output_overflow:
1289 BZ2_bzCompressEnd ( &strm );
1290 return BZ_OUTBUFF_FULL;
1291
1292 errhandler:
1293 BZ2_bzCompressEnd ( &strm );
1294 return ret;
1295}
1296
1297
1298/*---------------------------------------------------*/
1299int BZ_API(BZ2_bzBuffToBuffDecompress)
1300 ( char* dest,
1301 unsigned int* destLen,
1302 char* source,
1303 unsigned int sourceLen,
1304 int small,
1305 int verbosity )
1306{
1307 bz_stream strm;
1308 int ret;
1309
1310 if (dest == NULL || destLen == NULL ||
1311 source == NULL ||
1312 (small != 0 && small != 1) ||
1313 verbosity < 0 || verbosity > 4)
1314 return BZ_PARAM_ERROR;
1315
1316 strm.bzalloc = NULL;
1317 strm.bzfree = NULL;
1318 strm.opaque = NULL;
1319 ret = BZ2_bzDecompressInit ( &strm, verbosity, small );
1320 if (ret != BZ_OK) return ret;
1321
1322 strm.next_in = source;
1323 strm.next_out = dest;
1324 strm.avail_in = sourceLen;
1325 strm.avail_out = *destLen;
1326
1327 ret = BZ2_bzDecompress ( &strm );
1328 if (ret == BZ_OK) goto output_overflow_or_eof;
1329 if (ret != BZ_STREAM_END) goto errhandler;
1330
1331 /* normal termination */
1332 *destLen -= strm.avail_out;
1333 BZ2_bzDecompressEnd ( &strm );
1334 return BZ_OK;
1335
1336 output_overflow_or_eof:
1337 if (strm.avail_out > 0) {
1338 BZ2_bzDecompressEnd ( &strm );
1339 return BZ_UNEXPECTED_EOF;
1340 } else {
1341 BZ2_bzDecompressEnd ( &strm );
1342 return BZ_OUTBUFF_FULL;
1343 };
1344
1345 errhandler:
1346 BZ2_bzDecompressEnd ( &strm );
1347 return ret;
1348}
1349
1350
1351/*---------------------------------------------------*/
1352/*--
1353 Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp)
1354 to support better zlib compatibility.
1355 This code is not _officially_ part of libbzip2 (yet);
1356 I haven't tested it, documented it, or considered the
1357 threading-safeness of it.
1358 If this code breaks, please contact both Yoshioka and me.
1359--*/
1360/*---------------------------------------------------*/
1361
1362/*---------------------------------------------------*/
1363/*--
1364 return version like "0.9.5d, 4-Sept-1999".
1365--*/
1366const char * BZ_API(BZ2_bzlibVersion)(void)
1367{
1368 return BZ_VERSION;
1369}
1370
1371
1372#ifndef BZ_NO_STDIO
1373/*---------------------------------------------------*/
1374
1375#if defined(_WIN32) || defined(OS2) || defined(MSDOS)
1376# include <fcntl.h>
1377# include <io.h>
1378# define SET_BINARY_MODE(file) _setmode(_fileno(file),O_BINARY)
1379#else
1380# define SET_BINARY_MODE(file)
1381#endif
1382static
1383BZFILE * bzopen_or_bzdopen
1384 ( const char *path, /* no use when bzdopen */
1385 int fd, /* no use when bzdopen */
1386 const char *mode,
1387 int open_mode) /* bzopen: 0, bzdopen:1 */
1388{
1389 int bzerr;
1390 char unused[BZ_MAX_UNUSED];
1391 int blockSize100k = 9;
1392 int writing = 0;
1393 char mode2[10] = "";
1394 FILE *fp = NULL;
1395 BZFILE *bzfp = NULL;
1396 int verbosity = 0;
1397 int workFactor = 30;
1398 int smallMode = 0;
1399 int nUnused = 0;
1400
1401 if (mode == NULL) return NULL;
1402 while (*mode) {
1403 switch (*mode) {
1404 case 'r':
1405 writing = 0; break;
1406 case 'w':
1407 writing = 1; break;
1408 case 's':
1409 smallMode = 1; break;
1410 default:
1411 if (isdigit((int)(*mode))) {
1412 blockSize100k = *mode-BZ_HDR_0;
1413 }
1414 }
1415 mode++;
1416 }
1417 strcat(mode2, writing ? "w" : "r" );
1418 strcat(mode2,"b"); /* binary mode */
1419
1420 if (open_mode==0) {
1421 if (path==NULL || strcmp(path,"")==0) {
1422 fp = (writing ? stdout : stdin);
1423 SET_BINARY_MODE(fp);
1424 } else {
1425 fp = fopen(path,mode2);
1426 }
1427 } else {
1428#ifdef BZ_STRICT_ANSI
1429 fp = NULL;
1430#else
1431 fp = _fdopen(fd,mode2);
1432#endif
1433 }
1434 if (fp == NULL) return NULL;
1435
1436 if (writing) {
1437 /* Guard against total chaos and anarchy -- JRS */
1438 if (blockSize100k < 1) blockSize100k = 1;
1439 if (blockSize100k > 9) blockSize100k = 9;
1440 bzfp = BZ2_bzWriteOpen(&bzerr,fp,blockSize100k,
1441 verbosity,workFactor);
1442 } else {
1443 bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode,
1444 unused,nUnused);
1445 }
1446 if (bzfp == NULL) {
1447 if (fp != stdin && fp != stdout) fclose(fp);
1448 return NULL;
1449 }
1450 return bzfp;
1451}
1452
1453
1454/*---------------------------------------------------*/
1455/*--
1456 open file for read or write.
1457 ex) bzopen("file","w9")
1458 case path="" or NULL => use stdin or stdout.
1459--*/
1460BZFILE * BZ_API(BZ2_bzopen)
1461 ( const char *path,
1462 const char *mode )
1463{
1464 return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0);
1465}
1466
1467
1468/*---------------------------------------------------*/
1469BZFILE * BZ_API(BZ2_bzdopen)
1470 ( int fd,
1471 const char *mode )
1472{
1473 return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1);
1474}
1475
1476
1477/*---------------------------------------------------*/
1478int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len )
1479{
1480 int bzerr, nread;
1481 if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0;
1482 nread = BZ2_bzRead(&bzerr,b,buf,len);
1483 if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) {
1484 return nread;
1485 } else {
1486 return -1;
1487 }
1488}
1489
1490
1491/*---------------------------------------------------*/
1492int BZ_API(BZ2_bzwrite) (BZFILE* b, void* buf, int len )
1493{
1494 int bzerr;
1495
1496 BZ2_bzWrite(&bzerr,b,buf,len);
1497 if(bzerr == BZ_OK){
1498 return len;
1499 }else{
1500 return -1;
1501 }
1502}
1503
1504
1505/*---------------------------------------------------*/
1506int BZ_API(BZ2_bzflush) (BZFILE *b)
1507{
1508 /* do nothing now... */
1509 return 0;
1510}
1511
1512
1513/*---------------------------------------------------*/
1514void BZ_API(BZ2_bzclose) (BZFILE* b)
1515{
1516 int bzerr;
1517 FILE *fp;
1518
1519 if (b==NULL) {return;}
1520 fp = ((bzFile *)b)->handle;
1521 if(((bzFile*)b)->writing){
1522 BZ2_bzWriteClose(&bzerr,b,0,NULL,NULL);
1523 if(bzerr != BZ_OK){
1524 BZ2_bzWriteClose(NULL,b,1,NULL,NULL);
1525 }
1526 }else{
1527 BZ2_bzReadClose(&bzerr,b);
1528 }
1529 if(fp!=stdin && fp!=stdout){
1530 fclose(fp);
1531 }
1532}
1533
1534
1535/*---------------------------------------------------*/
1536/*--
1537 return last error code
1538--*/
1539static const char *bzerrorstrings[] = {
1540 "OK"
1541 ,"SEQUENCE_ERROR"
1542 ,"PARAM_ERROR"
1543 ,"MEM_ERROR"
1544 ,"DATA_ERROR"
1545 ,"DATA_ERROR_MAGIC"
1546 ,"IO_ERROR"
1547 ,"UNEXPECTED_EOF"
1548 ,"OUTBUFF_FULL"
1549 ,"CONFIG_ERROR"
1550 ,"???" /* for future */
1551 ,"???" /* for future */
1552 ,"???" /* for future */
1553 ,"???" /* for future */
1554 ,"???" /* for future */
1555 ,"???" /* for future */
1556};
1557
1558
1559const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum)
1560{
1561 int err = ((bzFile *)b)->lastErr;
1562
1563 if(err>0) err = 0;
1564 *errnum = err;
1565 return bzerrorstrings[err*-1];
1566}
1567#endif
1568
1569
1570/*-------------------------------------------------------------*/
1571/*--- end bzlib.c ---*/
1572/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/bzlib.h b/utils/bzip2/bzlib.h
new file mode 100644
index 0000000000..8277123da8
--- /dev/null
+++ b/utils/bzip2/bzlib.h
@@ -0,0 +1,282 @@
1
2/*-------------------------------------------------------------*/
3/*--- Public header file for the library. ---*/
4/*--- bzlib.h ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#ifndef _BZLIB_H
23#define _BZLIB_H
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29#define BZ_RUN 0
30#define BZ_FLUSH 1
31#define BZ_FINISH 2
32
33#define BZ_OK 0
34#define BZ_RUN_OK 1
35#define BZ_FLUSH_OK 2
36#define BZ_FINISH_OK 3
37#define BZ_STREAM_END 4
38#define BZ_SEQUENCE_ERROR (-1)
39#define BZ_PARAM_ERROR (-2)
40#define BZ_MEM_ERROR (-3)
41#define BZ_DATA_ERROR (-4)
42#define BZ_DATA_ERROR_MAGIC (-5)
43#define BZ_IO_ERROR (-6)
44#define BZ_UNEXPECTED_EOF (-7)
45#define BZ_OUTBUFF_FULL (-8)
46#define BZ_CONFIG_ERROR (-9)
47
48typedef
49 struct {
50 char *next_in;
51 unsigned int avail_in;
52 unsigned int total_in_lo32;
53 unsigned int total_in_hi32;
54
55 char *next_out;
56 unsigned int avail_out;
57 unsigned int total_out_lo32;
58 unsigned int total_out_hi32;
59
60 void *state;
61
62 void *(*bzalloc)(void *,int,int);
63 void (*bzfree)(void *,void *);
64 void *opaque;
65 }
66 bz_stream;
67
68
69#ifndef BZ_IMPORT
70#define BZ_EXPORT
71#endif
72
73#ifndef BZ_NO_STDIO
74/* Need a definitition for FILE */
75#include <stdio.h>
76#endif
77
78#ifdef _WIN32
79# include <windows.h>
80# ifdef small
81 /* windows.h define small to char */
82# undef small
83# endif
84# ifdef BZ_EXPORT
85# define BZ_API(func) WINAPI func
86# define BZ_EXTERN extern
87# else
88 /* import windows dll dynamically */
89# define BZ_API(func) (WINAPI * func)
90# define BZ_EXTERN
91# endif
92#else
93# define BZ_API(func) func
94# define BZ_EXTERN extern
95#endif
96
97
98/*-- Core (low-level) library functions --*/
99
100BZ_EXTERN int BZ_API(BZ2_bzCompressInit) (
101 bz_stream* strm,
102 int blockSize100k,
103 int verbosity,
104 int workFactor
105 );
106
107BZ_EXTERN int BZ_API(BZ2_bzCompress) (
108 bz_stream* strm,
109 int action
110 );
111
112BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) (
113 bz_stream* strm
114 );
115
116BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) (
117 bz_stream *strm,
118 int verbosity,
119 int small
120 );
121
122BZ_EXTERN int BZ_API(BZ2_bzDecompress) (
123 bz_stream* strm
124 );
125
126BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) (
127 bz_stream *strm
128 );
129
130
131
132/*-- High(er) level library functions --*/
133
134#ifndef BZ_NO_STDIO
135#define BZ_MAX_UNUSED 5000
136
137typedef void BZFILE;
138
139BZ_EXTERN BZFILE* BZ_API(BZ2_bzReadOpen) (
140 int* bzerror,
141 FILE* f,
142 int verbosity,
143 int small,
144 void* unused,
145 int nUnused
146 );
147
148BZ_EXTERN void BZ_API(BZ2_bzReadClose) (
149 int* bzerror,
150 BZFILE* b
151 );
152
153BZ_EXTERN void BZ_API(BZ2_bzReadGetUnused) (
154 int* bzerror,
155 BZFILE* b,
156 void** unused,
157 int* nUnused
158 );
159
160BZ_EXTERN int BZ_API(BZ2_bzRead) (
161 int* bzerror,
162 BZFILE* b,
163 void* buf,
164 int len
165 );
166
167BZ_EXTERN BZFILE* BZ_API(BZ2_bzWriteOpen) (
168 int* bzerror,
169 FILE* f,
170 int blockSize100k,
171 int verbosity,
172 int workFactor
173 );
174
175BZ_EXTERN void BZ_API(BZ2_bzWrite) (
176 int* bzerror,
177 BZFILE* b,
178 void* buf,
179 int len
180 );
181
182BZ_EXTERN void BZ_API(BZ2_bzWriteClose) (
183 int* bzerror,
184 BZFILE* b,
185 int abandon,
186 unsigned int* nbytes_in,
187 unsigned int* nbytes_out
188 );
189
190BZ_EXTERN void BZ_API(BZ2_bzWriteClose64) (
191 int* bzerror,
192 BZFILE* b,
193 int abandon,
194 unsigned int* nbytes_in_lo32,
195 unsigned int* nbytes_in_hi32,
196 unsigned int* nbytes_out_lo32,
197 unsigned int* nbytes_out_hi32
198 );
199#endif
200
201
202/*-- Utility functions --*/
203
204BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) (
205 char* dest,
206 unsigned int* destLen,
207 char* source,
208 unsigned int sourceLen,
209 int blockSize100k,
210 int verbosity,
211 int workFactor
212 );
213
214BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) (
215 char* dest,
216 unsigned int* destLen,
217 char* source,
218 unsigned int sourceLen,
219 int small,
220 int verbosity
221 );
222
223
224/*--
225 Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp)
226 to support better zlib compatibility.
227 This code is not _officially_ part of libbzip2 (yet);
228 I haven't tested it, documented it, or considered the
229 threading-safeness of it.
230 If this code breaks, please contact both Yoshioka and me.
231--*/
232
233BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) (
234 void
235 );
236
237#ifndef BZ_NO_STDIO
238BZ_EXTERN BZFILE * BZ_API(BZ2_bzopen) (
239 const char *path,
240 const char *mode
241 );
242
243BZ_EXTERN BZFILE * BZ_API(BZ2_bzdopen) (
244 int fd,
245 const char *mode
246 );
247
248BZ_EXTERN int BZ_API(BZ2_bzread) (
249 BZFILE* b,
250 void* buf,
251 int len
252 );
253
254BZ_EXTERN int BZ_API(BZ2_bzwrite) (
255 BZFILE* b,
256 void* buf,
257 int len
258 );
259
260BZ_EXTERN int BZ_API(BZ2_bzflush) (
261 BZFILE* b
262 );
263
264BZ_EXTERN void BZ_API(BZ2_bzclose) (
265 BZFILE* b
266 );
267
268BZ_EXTERN const char * BZ_API(BZ2_bzerror) (
269 BZFILE *b,
270 int *errnum
271 );
272#endif
273
274#ifdef __cplusplus
275}
276#endif
277
278#endif
279
280/*-------------------------------------------------------------*/
281/*--- end bzlib.h ---*/
282/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/bzlib_private.h b/utils/bzip2/bzlib_private.h
new file mode 100644
index 0000000000..d2b1a97ccb
--- /dev/null
+++ b/utils/bzip2/bzlib_private.h
@@ -0,0 +1,512 @@
1
2/*-------------------------------------------------------------*/
3/*--- Private header file for the library. ---*/
4/*--- bzlib_private.h ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#ifndef _BZLIB_PRIVATE_H
23#define _BZLIB_PRIVATE_H
24
25#include <stdlib.h>
26
27#ifndef BZ_NO_STDIO
28#include <stdio.h>
29#include <ctype.h>
30#include <string.h>
31#endif
32
33#include "bzlib.h"
34
35
36
37/*-- General stuff. --*/
38
39#define BZ_VERSION "1.0.6, 6-Sept-2010"
40
41typedef char Char;
42typedef unsigned char Bool;
43typedef unsigned char UChar;
44typedef int Int32;
45typedef unsigned int UInt32;
46typedef short Int16;
47typedef unsigned short UInt16;
48
49#define True ((Bool)1)
50#define False ((Bool)0)
51
52#ifndef __GNUC__
53#define __inline__ /* */
54#endif
55
56#ifndef BZ_NO_STDIO
57
58extern void BZ2_bz__AssertH__fail ( int errcode );
59#define AssertH(cond,errcode) \
60 { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
61
62#if BZ_DEBUG
63#define AssertD(cond,msg) \
64 { if (!(cond)) { \
65 fprintf ( stderr, \
66 "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
67 exit(1); \
68 }}
69#else
70#define AssertD(cond,msg) /* */
71#endif
72
73#define VPrintf0(zf) \
74 fprintf(stderr,zf)
75#define VPrintf1(zf,za1) \
76 fprintf(stderr,zf,za1)
77#define VPrintf2(zf,za1,za2) \
78 fprintf(stderr,zf,za1,za2)
79#define VPrintf3(zf,za1,za2,za3) \
80 fprintf(stderr,zf,za1,za2,za3)
81#define VPrintf4(zf,za1,za2,za3,za4) \
82 fprintf(stderr,zf,za1,za2,za3,za4)
83#define VPrintf5(zf,za1,za2,za3,za4,za5) \
84 fprintf(stderr,zf,za1,za2,za3,za4,za5)
85
86#else
87
88extern void bz_internal_error ( int errcode );
89#define AssertH(cond,errcode) \
90 { if (!(cond)) bz_internal_error ( errcode ); }
91#define AssertD(cond,msg) do { } while (0)
92#define VPrintf0(zf) do { } while (0)
93#define VPrintf1(zf,za1) do { } while (0)
94#define VPrintf2(zf,za1,za2) do { } while (0)
95#define VPrintf3(zf,za1,za2,za3) do { } while (0)
96#define VPrintf4(zf,za1,za2,za3,za4) do { } while (0)
97#define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0)
98
99#endif
100
101
102#define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
103#define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp))
104
105
106/*-- Header bytes. --*/
107
108#define BZ_HDR_B 0x42 /* 'B' */
109#define BZ_HDR_Z 0x5a /* 'Z' */
110#define BZ_HDR_h 0x68 /* 'h' */
111#define BZ_HDR_0 0x30 /* '0' */
112
113/*-- Constants for the back end. --*/
114
115#define BZ_MAX_ALPHA_SIZE 258
116#define BZ_MAX_CODE_LEN 23
117
118#define BZ_RUNA 0
119#define BZ_RUNB 1
120
121#define BZ_N_GROUPS 6
122#define BZ_G_SIZE 50
123#define BZ_N_ITERS 4
124
125#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
126
127
128
129/*-- Stuff for randomising repetitive blocks. --*/
130
131extern Int32 BZ2_rNums[512];
132
133#define BZ_RAND_DECLS \
134 Int32 rNToGo; \
135 Int32 rTPos \
136
137#define BZ_RAND_INIT_MASK \
138 s->rNToGo = 0; \
139 s->rTPos = 0 \
140
141#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
142
143#define BZ_RAND_UPD_MASK \
144 if (s->rNToGo == 0) { \
145 s->rNToGo = BZ2_rNums[s->rTPos]; \
146 s->rTPos++; \
147 if (s->rTPos == 512) s->rTPos = 0; \
148 } \
149 s->rNToGo--;
150
151
152
153/*-- Stuff for doing CRCs. --*/
154
155extern UInt32 BZ2_crc32Table[256];
156
157#define BZ_INITIALISE_CRC(crcVar) \
158{ \
159 crcVar = 0xffffffffL; \
160}
161
162#define BZ_FINALISE_CRC(crcVar) \
163{ \
164 crcVar = ~(crcVar); \
165}
166
167#define BZ_UPDATE_CRC(crcVar,cha) \
168{ \
169 crcVar = (crcVar << 8) ^ \
170 BZ2_crc32Table[(crcVar >> 24) ^ \
171 ((UChar)cha)]; \
172}
173
174
175
176/*-- States and modes for compression. --*/
177
178#define BZ_M_IDLE 1
179#define BZ_M_RUNNING 2
180#define BZ_M_FLUSHING 3
181#define BZ_M_FINISHING 4
182
183#define BZ_S_OUTPUT 1
184#define BZ_S_INPUT 2
185
186#define BZ_N_RADIX 2
187#define BZ_N_QSORT 12
188#define BZ_N_SHELL 18
189#define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
190
191
192
193
194/*-- Structure holding all the compression-side stuff. --*/
195
196typedef
197 struct {
198 /* pointer back to the struct bz_stream */
199 bz_stream* strm;
200
201 /* mode this stream is in, and whether inputting */
202 /* or outputting data */
203 Int32 mode;
204 Int32 state;
205
206 /* remembers avail_in when flush/finish requested */
207 UInt32 avail_in_expect;
208
209 /* for doing the block sorting */
210 UInt32* arr1;
211 UInt32* arr2;
212 UInt32* ftab;
213 Int32 origPtr;
214
215 /* aliases for arr1 and arr2 */
216 UInt32* ptr;
217 UChar* block;
218 UInt16* mtfv;
219 UChar* zbits;
220
221 /* for deciding when to use the fallback sorting algorithm */
222 Int32 workFactor;
223
224 /* run-length-encoding of the input */
225 UInt32 state_in_ch;
226 Int32 state_in_len;
227 BZ_RAND_DECLS;
228
229 /* input and output limits and current posns */
230 Int32 nblock;
231 Int32 nblockMAX;
232 Int32 numZ;
233 Int32 state_out_pos;
234
235 /* map of bytes used in block */
236 Int32 nInUse;
237 Bool inUse[256];
238 UChar unseqToSeq[256];
239
240 /* the buffer for bit stream creation */
241 UInt32 bsBuff;
242 Int32 bsLive;
243
244 /* block and combined CRCs */
245 UInt32 blockCRC;
246 UInt32 combinedCRC;
247
248 /* misc administratium */
249 Int32 verbosity;
250 Int32 blockNo;
251 Int32 blockSize100k;
252
253 /* stuff for coding the MTF values */
254 Int32 nMTF;
255 Int32 mtfFreq [BZ_MAX_ALPHA_SIZE];
256 UChar selector [BZ_MAX_SELECTORS];
257 UChar selectorMtf[BZ_MAX_SELECTORS];
258
259 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
260 Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
261 Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
262 /* second dimension: only 3 needed; 4 makes index calculations faster */
263 UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4];
264
265 }
266 EState;
267
268
269
270/*-- externs for compression. --*/
271
272extern void
273BZ2_blockSort ( EState* );
274
275extern void
276BZ2_compressBlock ( EState*, Bool );
277
278extern void
279BZ2_bsInitWrite ( EState* );
280
281extern void
282BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
283
284extern void
285BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
286
287
288
289/*-- states for decompression. --*/
290
291#define BZ_X_IDLE 1
292#define BZ_X_OUTPUT 2
293
294#define BZ_X_MAGIC_1 10
295#define BZ_X_MAGIC_2 11
296#define BZ_X_MAGIC_3 12
297#define BZ_X_MAGIC_4 13
298#define BZ_X_BLKHDR_1 14
299#define BZ_X_BLKHDR_2 15
300#define BZ_X_BLKHDR_3 16
301#define BZ_X_BLKHDR_4 17
302#define BZ_X_BLKHDR_5 18
303#define BZ_X_BLKHDR_6 19
304#define BZ_X_BCRC_1 20
305#define BZ_X_BCRC_2 21
306#define BZ_X_BCRC_3 22
307#define BZ_X_BCRC_4 23
308#define BZ_X_RANDBIT 24
309#define BZ_X_ORIGPTR_1 25
310#define BZ_X_ORIGPTR_2 26
311#define BZ_X_ORIGPTR_3 27
312#define BZ_X_MAPPING_1 28
313#define BZ_X_MAPPING_2 29
314#define BZ_X_SELECTOR_1 30
315#define BZ_X_SELECTOR_2 31
316#define BZ_X_SELECTOR_3 32
317#define BZ_X_CODING_1 33
318#define BZ_X_CODING_2 34
319#define BZ_X_CODING_3 35
320#define BZ_X_MTF_1 36
321#define BZ_X_MTF_2 37
322#define BZ_X_MTF_3 38
323#define BZ_X_MTF_4 39
324#define BZ_X_MTF_5 40
325#define BZ_X_MTF_6 41
326#define BZ_X_ENDHDR_2 42
327#define BZ_X_ENDHDR_3 43
328#define BZ_X_ENDHDR_4 44
329#define BZ_X_ENDHDR_5 45
330#define BZ_X_ENDHDR_6 46
331#define BZ_X_CCRC_1 47
332#define BZ_X_CCRC_2 48
333#define BZ_X_CCRC_3 49
334#define BZ_X_CCRC_4 50
335
336
337
338/*-- Constants for the fast MTF decoder. --*/
339
340#define MTFA_SIZE 4096
341#define MTFL_SIZE 16
342
343
344
345/*-- Structure holding all the decompression-side stuff. --*/
346
347typedef
348 struct {
349 /* pointer back to the struct bz_stream */
350 bz_stream* strm;
351
352 /* state indicator for this stream */
353 Int32 state;
354
355 /* for doing the final run-length decoding */
356 UChar state_out_ch;
357 Int32 state_out_len;
358 Bool blockRandomised;
359 BZ_RAND_DECLS;
360
361 /* the buffer for bit stream reading */
362 UInt32 bsBuff;
363 Int32 bsLive;
364
365 /* misc administratium */
366 Int32 blockSize100k;
367 Bool smallDecompress;
368 Int32 currBlockNo;
369 Int32 verbosity;
370
371 /* for undoing the Burrows-Wheeler transform */
372 Int32 origPtr;
373 UInt32 tPos;
374 Int32 k0;
375 Int32 unzftab[256];
376 Int32 nblock_used;
377 Int32 cftab[257];
378 Int32 cftabCopy[257];
379
380 /* for undoing the Burrows-Wheeler transform (FAST) */
381 UInt32 *tt;
382
383 /* for undoing the Burrows-Wheeler transform (SMALL) */
384 UInt16 *ll16;
385 UChar *ll4;
386
387 /* stored and calculated CRCs */
388 UInt32 storedBlockCRC;
389 UInt32 storedCombinedCRC;
390 UInt32 calculatedBlockCRC;
391 UInt32 calculatedCombinedCRC;
392
393 /* map of bytes used in block */
394 Int32 nInUse;
395 Bool inUse[256];
396 Bool inUse16[16];
397 UChar seqToUnseq[256];
398
399 /* for decoding the MTF values */
400 UChar mtfa [MTFA_SIZE];
401 Int32 mtfbase[256 / MTFL_SIZE];
402 UChar selector [BZ_MAX_SELECTORS];
403 UChar selectorMtf[BZ_MAX_SELECTORS];
404 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
405
406 Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
407 Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
408 Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
409 Int32 minLens[BZ_N_GROUPS];
410
411 /* save area for scalars in the main decompress code */
412 Int32 save_i;
413 Int32 save_j;
414 Int32 save_t;
415 Int32 save_alphaSize;
416 Int32 save_nGroups;
417 Int32 save_nSelectors;
418 Int32 save_EOB;
419 Int32 save_groupNo;
420 Int32 save_groupPos;
421 Int32 save_nextSym;
422 Int32 save_nblockMAX;
423 Int32 save_nblock;
424 Int32 save_es;
425 Int32 save_N;
426 Int32 save_curr;
427 Int32 save_zt;
428 Int32 save_zn;
429 Int32 save_zvec;
430 Int32 save_zj;
431 Int32 save_gSel;
432 Int32 save_gMinlen;
433 Int32* save_gLimit;
434 Int32* save_gBase;
435 Int32* save_gPerm;
436
437 }
438 DState;
439
440
441
442/*-- Macros for decompression. --*/
443
444#define BZ_GET_FAST(cccc) \
445 /* c_tPos is unsigned, hence test < 0 is pointless. */ \
446 if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \
447 s->tPos = s->tt[s->tPos]; \
448 cccc = (UChar)(s->tPos & 0xff); \
449 s->tPos >>= 8;
450
451#define BZ_GET_FAST_C(cccc) \
452 /* c_tPos is unsigned, hence test < 0 is pointless. */ \
453 if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \
454 c_tPos = c_tt[c_tPos]; \
455 cccc = (UChar)(c_tPos & 0xff); \
456 c_tPos >>= 8;
457
458#define SET_LL4(i,n) \
459 { if (((i) & 0x1) == 0) \
460 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \
461 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \
462 }
463
464#define GET_LL4(i) \
465 ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
466
467#define SET_LL(i,n) \
468 { s->ll16[i] = (UInt16)(n & 0x0000ffff); \
469 SET_LL4(i, n >> 16); \
470 }
471
472#define GET_LL(i) \
473 (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
474
475#define BZ_GET_SMALL(cccc) \
476 /* c_tPos is unsigned, hence test < 0 is pointless. */ \
477 if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \
478 cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \
479 s->tPos = GET_LL(s->tPos);
480
481
482/*-- externs for decompression. --*/
483
484extern Int32
485BZ2_indexIntoF ( Int32, Int32* );
486
487extern Int32
488BZ2_decompress ( DState* );
489
490extern void
491BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
492 Int32, Int32, Int32 );
493
494
495#endif
496
497
498/*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
499
500#ifdef BZ_NO_STDIO
501#ifndef NULL
502#define NULL 0
503#endif
504#endif
505
506#ifndef WIN32
507#define _fdopen fdopen
508#endif
509
510/*-------------------------------------------------------------*/
511/*--- end bzlib_private.h ---*/
512/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/compress.c b/utils/bzip2/compress.c
new file mode 100644
index 0000000000..caf7696011
--- /dev/null
+++ b/utils/bzip2/compress.c
@@ -0,0 +1,672 @@
1
2/*-------------------------------------------------------------*/
3/*--- Compression machinery (not incl block sorting) ---*/
4/*--- compress.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22/* CHANGES
23 0.9.0 -- original version.
24 0.9.0a/b -- no changes in this file.
25 0.9.0c -- changed setting of nGroups in sendMTFValues()
26 so as to do a bit better on small files
27*/
28
29#include "bzlib_private.h"
30
31
32/*---------------------------------------------------*/
33/*--- Bit stream I/O ---*/
34/*---------------------------------------------------*/
35
36/*---------------------------------------------------*/
37void BZ2_bsInitWrite ( EState* s )
38{
39 s->bsLive = 0;
40 s->bsBuff = 0;
41}
42
43
44/*---------------------------------------------------*/
45static
46void bsFinishWrite ( EState* s )
47{
48 while (s->bsLive > 0) {
49 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
50 s->numZ++;
51 s->bsBuff <<= 8;
52 s->bsLive -= 8;
53 }
54}
55
56
57/*---------------------------------------------------*/
58#define bsNEEDW(nz) \
59{ \
60 while (s->bsLive >= 8) { \
61 s->zbits[s->numZ] \
62 = (UChar)(s->bsBuff >> 24); \
63 s->numZ++; \
64 s->bsBuff <<= 8; \
65 s->bsLive -= 8; \
66 } \
67}
68
69
70/*---------------------------------------------------*/
71static
72__inline__
73void bsW ( EState* s, Int32 n, UInt32 v )
74{
75 bsNEEDW ( n );
76 s->bsBuff |= (v << (32 - s->bsLive - n));
77 s->bsLive += n;
78}
79
80
81/*---------------------------------------------------*/
82static
83void bsPutUInt32 ( EState* s, UInt32 u )
84{
85 bsW ( s, 8, (u >> 24) & 0xffL );
86 bsW ( s, 8, (u >> 16) & 0xffL );
87 bsW ( s, 8, (u >> 8) & 0xffL );
88 bsW ( s, 8, u & 0xffL );
89}
90
91
92/*---------------------------------------------------*/
93static
94void bsPutUChar ( EState* s, UChar c )
95{
96 bsW( s, 8, (UInt32)c );
97}
98
99
100/*---------------------------------------------------*/
101/*--- The back end proper ---*/
102/*---------------------------------------------------*/
103
104/*---------------------------------------------------*/
105static
106void makeMaps_e ( EState* s )
107{
108 Int32 i;
109 s->nInUse = 0;
110 for (i = 0; i < 256; i++)
111 if (s->inUse[i]) {
112 s->unseqToSeq[i] = s->nInUse;
113 s->nInUse++;
114 }
115}
116
117
118/*---------------------------------------------------*/
119static
120void generateMTFValues ( EState* s )
121{
122 UChar yy[256];
123 Int32 i, j;
124 Int32 zPend;
125 Int32 wr;
126 Int32 EOB;
127
128 /*
129 After sorting (eg, here),
130 s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
131 and
132 ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
133 holds the original block data.
134
135 The first thing to do is generate the MTF values,
136 and put them in
137 ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
138 Because there are strictly fewer or equal MTF values
139 than block values, ptr values in this area are overwritten
140 with MTF values only when they are no longer needed.
141
142 The final compressed bitstream is generated into the
143 area starting at
144 (UChar*) (&((UChar*)s->arr2)[s->nblock])
145
146 These storage aliases are set up in bzCompressInit(),
147 except for the last one, which is arranged in
148 compressBlock().
149 */
150 UInt32* ptr = s->ptr;
151 UChar* block = s->block;
152 UInt16* mtfv = s->mtfv;
153
154 makeMaps_e ( s );
155 EOB = s->nInUse+1;
156
157 for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
158
159 wr = 0;
160 zPend = 0;
161 for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
162
163 for (i = 0; i < s->nblock; i++) {
164 UChar ll_i;
165 AssertD ( wr <= i, "generateMTFValues(1)" );
166 j = ptr[i]-1; if (j < 0) j += s->nblock;
167 ll_i = s->unseqToSeq[block[j]];
168 AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
169
170 if (yy[0] == ll_i) {
171 zPend++;
172 } else {
173
174 if (zPend > 0) {
175 zPend--;
176 while (True) {
177 if (zPend & 1) {
178 mtfv[wr] = BZ_RUNB; wr++;
179 s->mtfFreq[BZ_RUNB]++;
180 } else {
181 mtfv[wr] = BZ_RUNA; wr++;
182 s->mtfFreq[BZ_RUNA]++;
183 }
184 if (zPend < 2) break;
185 zPend = (zPend - 2) / 2;
186 };
187 zPend = 0;
188 }
189 {
190 register UChar rtmp;
191 register UChar* ryy_j;
192 register UChar rll_i;
193 rtmp = yy[1];
194 yy[1] = yy[0];
195 ryy_j = &(yy[1]);
196 rll_i = ll_i;
197 while ( rll_i != rtmp ) {
198 register UChar rtmp2;
199 ryy_j++;
200 rtmp2 = rtmp;
201 rtmp = *ryy_j;
202 *ryy_j = rtmp2;
203 };
204 yy[0] = rtmp;
205 j = ryy_j - &(yy[0]);
206 mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
207 }
208
209 }
210 }
211
212 if (zPend > 0) {
213 zPend--;
214 while (True) {
215 if (zPend & 1) {
216 mtfv[wr] = BZ_RUNB; wr++;
217 s->mtfFreq[BZ_RUNB]++;
218 } else {
219 mtfv[wr] = BZ_RUNA; wr++;
220 s->mtfFreq[BZ_RUNA]++;
221 }
222 if (zPend < 2) break;
223 zPend = (zPend - 2) / 2;
224 };
225 zPend = 0;
226 }
227
228 mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
229
230 s->nMTF = wr;
231}
232
233
234/*---------------------------------------------------*/
235#define BZ_LESSER_ICOST 0
236#define BZ_GREATER_ICOST 15
237
238static
239void sendMTFValues ( EState* s )
240{
241 Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
242 Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
243 Int32 nGroups, nBytes;
244
245 /*--
246 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
247 is a global since the decoder also needs it.
248
249 Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
250 Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
251 are also globals only used in this proc.
252 Made global to keep stack frame size small.
253 --*/
254
255
256 UInt16 cost[BZ_N_GROUPS];
257 Int32 fave[BZ_N_GROUPS];
258
259 UInt16* mtfv = s->mtfv;
260
261 if (s->verbosity >= 3)
262 VPrintf3( " %d in block, %d after MTF & 1-2 coding, "
263 "%d+2 syms in use\n",
264 s->nblock, s->nMTF, s->nInUse );
265
266 alphaSize = s->nInUse+2;
267 for (t = 0; t < BZ_N_GROUPS; t++)
268 for (v = 0; v < alphaSize; v++)
269 s->len[t][v] = BZ_GREATER_ICOST;
270
271 /*--- Decide how many coding tables to use ---*/
272 AssertH ( s->nMTF > 0, 3001 );
273 if (s->nMTF < 200) nGroups = 2; else
274 if (s->nMTF < 600) nGroups = 3; else
275 if (s->nMTF < 1200) nGroups = 4; else
276 if (s->nMTF < 2400) nGroups = 5; else
277 nGroups = 6;
278
279 /*--- Generate an initial set of coding tables ---*/
280 {
281 Int32 nPart, remF, tFreq, aFreq;
282
283 nPart = nGroups;
284 remF = s->nMTF;
285 gs = 0;
286 while (nPart > 0) {
287 tFreq = remF / nPart;
288 ge = gs-1;
289 aFreq = 0;
290 while (aFreq < tFreq && ge < alphaSize-1) {
291 ge++;
292 aFreq += s->mtfFreq[ge];
293 }
294
295 if (ge > gs
296 && nPart != nGroups && nPart != 1
297 && ((nGroups-nPart) % 2 == 1)) {
298 aFreq -= s->mtfFreq[ge];
299 ge--;
300 }
301
302 if (s->verbosity >= 3)
303 VPrintf5( " initial group %d, [%d .. %d], "
304 "has %d syms (%4.1f%%)\n",
305 nPart, gs, ge, aFreq,
306 (100.0 * (float)aFreq) / (float)(s->nMTF) );
307
308 for (v = 0; v < alphaSize; v++)
309 if (v >= gs && v <= ge)
310 s->len[nPart-1][v] = BZ_LESSER_ICOST; else
311 s->len[nPart-1][v] = BZ_GREATER_ICOST;
312
313 nPart--;
314 gs = ge+1;
315 remF -= aFreq;
316 }
317 }
318
319 /*---
320 Iterate up to BZ_N_ITERS times to improve the tables.
321 ---*/
322 for (iter = 0; iter < BZ_N_ITERS; iter++) {
323
324 for (t = 0; t < nGroups; t++) fave[t] = 0;
325
326 for (t = 0; t < nGroups; t++)
327 for (v = 0; v < alphaSize; v++)
328 s->rfreq[t][v] = 0;
329
330 /*---
331 Set up an auxiliary length table which is used to fast-track
332 the common case (nGroups == 6).
333 ---*/
334 if (nGroups == 6) {
335 for (v = 0; v < alphaSize; v++) {
336 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
337 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
338 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
339 }
340 }
341
342 nSelectors = 0;
343 totc = 0;
344 gs = 0;
345 while (True) {
346
347 /*--- Set group start & end marks. --*/
348 if (gs >= s->nMTF) break;
349 ge = gs + BZ_G_SIZE - 1;
350 if (ge >= s->nMTF) 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++) cost[t] = 0;
357
358 if (nGroups == 6 && 50 == ge-gs+1) {
359 /*--- fast track the common case ---*/
360 register UInt32 cost01, cost23, cost45;
361 register UInt16 icv;
362 cost01 = cost23 = cost45 = 0;
363
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
370 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
371 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
372 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
373 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
374 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
375 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
376 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
377 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
378 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
379 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
380
381# undef BZ_ITER
382
383 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
384 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
385 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
386
387 } else {
388 /*--- slow version which correctly handles all situations ---*/
389 for (i = gs; i <= ge; i++) {
390 UInt16 icv = mtfv[i];
391 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
392 }
393 }
394
395 /*--
396 Find the coding table which is best for this group,
397 and record its identity in the selector table.
398 --*/
399 bc = 999999999; bt = -1;
400 for (t = 0; t < nGroups; t++)
401 if (cost[t] < bc) { bc = cost[t]; bt = t; };
402 totc += bc;
403 fave[bt]++;
404 s->selector[nSelectors] = bt;
405 nSelectors++;
406
407 /*--
408 Increment the symbol frequencies for the selected table.
409 --*/
410 if (nGroups == 6 && 50 == ge-gs+1) {
411 /*--- fast track the common case ---*/
412
413# define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
414
415 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
416 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
417 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
418 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
419 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
420 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
421 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
422 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
423 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
424 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
425
426# undef BZ_ITUR
427
428 } else {
429 /*--- slow version which correctly handles all situations ---*/
430 for (i = gs; i <= ge; i++)
431 s->rfreq[bt][ mtfv[i] ]++;
432 }
433
434 gs = ge+1;
435 }
436 if (s->verbosity >= 3) {
437 VPrintf2 ( " pass %d: size is %d, grp uses are ",
438 iter+1, totc/8 );
439 for (t = 0; t < nGroups; t++)
440 VPrintf1 ( "%d ", fave[t] );
441 VPrintf0 ( "\n" );
442 }
443
444 /*--
445 Recompute the tables based on the accumulated frequencies.
446 --*/
447 /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
448 comment in huffman.c for details. */
449 for (t = 0; t < nGroups; t++)
450 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
451 alphaSize, 17 /*20*/ );
452 }
453
454
455 AssertH( nGroups < 8, 3002 );
456 AssertH( nSelectors < 32768 &&
457 nSelectors <= (2 + (900000 / BZ_G_SIZE)),
458 3003 );
459
460
461 /*--- Compute MTF values for the selectors. ---*/
462 {
463 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
464 for (i = 0; i < nGroups; i++) pos[i] = i;
465 for (i = 0; i < nSelectors; i++) {
466 ll_i = s->selector[i];
467 j = 0;
468 tmp = pos[j];
469 while ( ll_i != tmp ) {
470 j++;
471 tmp2 = tmp;
472 tmp = pos[j];
473 pos[j] = tmp2;
474 };
475 pos[0] = tmp;
476 s->selectorMtf[i] = j;
477 }
478 };
479
480 /*--- Assign actual codes for the tables. --*/
481 for (t = 0; t < nGroups; t++) {
482 minLen = 32;
483 maxLen = 0;
484 for (i = 0; i < alphaSize; i++) {
485 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
486 if (s->len[t][i] < minLen) minLen = s->len[t][i];
487 }
488 AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
489 AssertH ( !(minLen < 1), 3005 );
490 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
491 minLen, maxLen, alphaSize );
492 }
493
494 /*--- Transmit the mapping table. ---*/
495 {
496 Bool inUse16[16];
497 for (i = 0; i < 16; i++) {
498 inUse16[i] = False;
499 for (j = 0; j < 16; j++)
500 if (s->inUse[i * 16 + j]) inUse16[i] = True;
501 }
502
503 nBytes = s->numZ;
504 for (i = 0; i < 16; i++)
505 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
506
507 for (i = 0; i < 16; i++)
508 if (inUse16[i])
509 for (j = 0; j < 16; j++) {
510 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
511 }
512
513 if (s->verbosity >= 3)
514 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes );
515 }
516
517 /*--- Now the selectors. ---*/
518 nBytes = s->numZ;
519 bsW ( s, 3, nGroups );
520 bsW ( s, 15, nSelectors );
521 for (i = 0; i < nSelectors; i++) {
522 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
523 bsW(s,1,0);
524 }
525 if (s->verbosity >= 3)
526 VPrintf1( "selectors %d, ", s->numZ-nBytes );
527
528 /*--- Now the coding tables. ---*/
529 nBytes = s->numZ;
530
531 for (t = 0; t < nGroups; t++) {
532 Int32 curr = s->len[t][0];
533 bsW ( s, 5, curr );
534 for (i = 0; i < alphaSize; i++) {
535 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
536 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
537 bsW ( s, 1, 0 );
538 }
539 }
540
541 if (s->verbosity >= 3)
542 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
543
544 /*--- And finally, the block data proper ---*/
545 nBytes = s->numZ;
546 selCtr = 0;
547 gs = 0;
548 while (True) {
549 if (gs >= s->nMTF) break;
550 ge = gs + BZ_G_SIZE - 1;
551 if (ge >= s->nMTF) ge = s->nMTF-1;
552 AssertH ( s->selector[selCtr] < nGroups, 3006 );
553
554 if (nGroups == 6 && 50 == ge-gs+1) {
555 /*--- fast track the common case ---*/
556 UInt16 mtfv_i;
557 UChar* s_len_sel_selCtr
558 = &(s->len[s->selector[selCtr]][0]);
559 Int32* s_code_sel_selCtr
560 = &(s->code[s->selector[selCtr]][0]);
561
562# define BZ_ITAH(nn) \
563 mtfv_i = mtfv[gs+(nn)]; \
564 bsW ( s, \
565 s_len_sel_selCtr[mtfv_i], \
566 s_code_sel_selCtr[mtfv_i] )
567
568 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
569 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
570 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
571 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
572 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
573 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
574 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
575 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
576 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
577 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
578
579# undef BZ_ITAH
580
581 } else {
582 /*--- slow version which correctly handles all situations ---*/
583 for (i = gs; i <= ge; i++) {
584 bsW ( s,
585 s->len [s->selector[selCtr]] [mtfv[i]],
586 s->code [s->selector[selCtr]] [mtfv[i]] );
587 }
588 }
589
590
591 gs = ge+1;
592 selCtr++;
593 }
594 AssertH( selCtr == nSelectors, 3007 );
595
596 if (s->verbosity >= 3)
597 VPrintf1( "codes %d\n", s->numZ-nBytes );
598}
599
600
601/*---------------------------------------------------*/
602void BZ2_compressBlock ( EState* s, Bool is_last_block )
603{
604 if (s->nblock > 0) {
605
606 BZ_FINALISE_CRC ( s->blockCRC );
607 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
608 s->combinedCRC ^= s->blockCRC;
609 if (s->blockNo > 1) s->numZ = 0;
610
611 if (s->verbosity >= 2)
612 VPrintf4( " block %d: crc = 0x%08x, "
613 "combined CRC = 0x%08x, size = %d\n",
614 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
615
616 BZ2_blockSort ( s );
617 }
618
619 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
620
621 /*-- If this is the first block, create the stream header. --*/
622 if (s->blockNo == 1) {
623 BZ2_bsInitWrite ( s );
624 bsPutUChar ( s, BZ_HDR_B );
625 bsPutUChar ( s, BZ_HDR_Z );
626 bsPutUChar ( s, BZ_HDR_h );
627 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
628 }
629
630 if (s->nblock > 0) {
631
632 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
633 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
634 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
635
636 /*-- Now the block's CRC, so it is in a known place. --*/
637 bsPutUInt32 ( s, s->blockCRC );
638
639 /*--
640 Now a single bit indicating (non-)randomisation.
641 As of version 0.9.5, we use a better sorting algorithm
642 which makes randomisation unnecessary. So always set
643 the randomised bit to 'no'. Of course, the decoder
644 still needs to be able to handle randomised blocks
645 so as to maintain backwards compatibility with
646 older versions of bzip2.
647 --*/
648 bsW(s,1,0);
649
650 bsW ( s, 24, s->origPtr );
651 generateMTFValues ( s );
652 sendMTFValues ( s );
653 }
654
655
656 /*-- If this is the last block, add the stream trailer. --*/
657 if (is_last_block) {
658
659 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
660 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
661 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
662 bsPutUInt32 ( s, s->combinedCRC );
663 if (s->verbosity >= 2)
664 VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );
665 bsFinishWrite ( s );
666 }
667}
668
669
670/*-------------------------------------------------------------*/
671/*--- end compress.c ---*/
672/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/crctable.c b/utils/bzip2/crctable.c
new file mode 100644
index 0000000000..1fea7e946c
--- /dev/null
+++ b/utils/bzip2/crctable.c
@@ -0,0 +1,104 @@
1
2/*-------------------------------------------------------------*/
3/*--- Table for doing CRCs ---*/
4/*--- crctable.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#include "bzlib_private.h"
23
24/*--
25 I think this is an implementation of the AUTODIN-II,
26 Ethernet & FDDI 32-bit CRC standard. Vaguely derived
27 from code by Rob Warnock, in Section 51 of the
28 comp.compression FAQ.
29--*/
30
31UInt32 BZ2_crc32Table[256] = {
32
33 /*-- Ugly, innit? --*/
34
35 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
36 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
37 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
38 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
39 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
40 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
41 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
42 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
43 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
44 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
45 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
46 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
47 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
48 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
49 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
50 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
51 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
52 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
53 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
54 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
55 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
56 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
57 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
58 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
59 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
60 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
61 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
62 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
63 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
64 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
65 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
66 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
67 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
68 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
69 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
70 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
71 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
72 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
73 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
74 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
75 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
76 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
77 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
78 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
79 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
80 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
81 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
82 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
83 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
84 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
85 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
86 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
87 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
88 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
89 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
90 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
91 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
92 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
93 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
94 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
95 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
96 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
97 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
98 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
99};
100
101
102/*-------------------------------------------------------------*/
103/*--- end crctable.c ---*/
104/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/decompress.c b/utils/bzip2/decompress.c
new file mode 100644
index 0000000000..311f5668f9
--- /dev/null
+++ b/utils/bzip2/decompress.c
@@ -0,0 +1,646 @@
1
2/*-------------------------------------------------------------*/
3/*--- Decompression machinery ---*/
4/*--- decompress.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#include "bzlib_private.h"
23
24
25/*---------------------------------------------------*/
26static
27void makeMaps_d ( DState* s )
28{
29 Int32 i;
30 s->nInUse = 0;
31 for (i = 0; i < 256; i++)
32 if (s->inUse[i]) {
33 s->seqToUnseq[s->nInUse] = i;
34 s->nInUse++;
35 }
36}
37
38
39/*---------------------------------------------------*/
40#define RETURN(rrr) \
41 { retVal = rrr; goto save_state_and_return; };
42
43#define GET_BITS(lll,vvv,nnn) \
44 case lll: s->state = lll; \
45 while (True) { \
46 if (s->bsLive >= nnn) { \
47 UInt32 v; \
48 v = (s->bsBuff >> \
49 (s->bsLive-nnn)) & ((1 << nnn)-1); \
50 s->bsLive -= nnn; \
51 vvv = v; \
52 break; \
53 } \
54 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
55 s->bsBuff \
56 = (s->bsBuff << 8) | \
57 ((UInt32) \
58 (*((UChar*)(s->strm->next_in)))); \
59 s->bsLive += 8; \
60 s->strm->next_in++; \
61 s->strm->avail_in--; \
62 s->strm->total_in_lo32++; \
63 if (s->strm->total_in_lo32 == 0) \
64 s->strm->total_in_hi32++; \
65 }
66
67#define GET_UCHAR(lll,uuu) \
68 GET_BITS(lll,uuu,8)
69
70#define GET_BIT(lll,uuu) \
71 GET_BITS(lll,uuu,1)
72
73/*---------------------------------------------------*/
74#define GET_MTF_VAL(label1,label2,lval) \
75{ \
76 if (groupPos == 0) { \
77 groupNo++; \
78 if (groupNo >= nSelectors) \
79 RETURN(BZ_DATA_ERROR); \
80 groupPos = BZ_G_SIZE; \
81 gSel = s->selector[groupNo]; \
82 gMinlen = s->minLens[gSel]; \
83 gLimit = &(s->limit[gSel][0]); \
84 gPerm = &(s->perm[gSel][0]); \
85 gBase = &(s->base[gSel][0]); \
86 } \
87 groupPos--; \
88 zn = gMinlen; \
89 GET_BITS(label1, zvec, zn); \
90 while (1) { \
91 if (zn > 20 /* the longest code */) \
92 RETURN(BZ_DATA_ERROR); \
93 if (zvec <= gLimit[zn]) break; \
94 zn++; \
95 GET_BIT(label2, zj); \
96 zvec = (zvec << 1) | zj; \
97 }; \
98 if (zvec - gBase[zn] < 0 \
99 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
100 RETURN(BZ_DATA_ERROR); \
101 lval = gPerm[zvec - gBase[zn]]; \
102}
103
104
105/*---------------------------------------------------*/
106Int32 BZ2_decompress ( DState* s )
107{
108 UChar uc;
109 Int32 retVal;
110 Int32 minLen, maxLen;
111 bz_stream* strm = s->strm;
112
113 /* stuff that needs to be saved/restored */
114 Int32 i;
115 Int32 j;
116 Int32 t;
117 Int32 alphaSize;
118 Int32 nGroups;
119 Int32 nSelectors;
120 Int32 EOB;
121 Int32 groupNo;
122 Int32 groupPos;
123 Int32 nextSym;
124 Int32 nblockMAX;
125 Int32 nblock;
126 Int32 es;
127 Int32 N;
128 Int32 curr;
129 Int32 zt;
130 Int32 zn;
131 Int32 zvec;
132 Int32 zj;
133 Int32 gSel;
134 Int32 gMinlen;
135 Int32* gLimit;
136 Int32* gBase;
137 Int32* gPerm;
138
139 if (s->state == BZ_X_MAGIC_1) {
140 /*initialise the save area*/
141 s->save_i = 0;
142 s->save_j = 0;
143 s->save_t = 0;
144 s->save_alphaSize = 0;
145 s->save_nGroups = 0;
146 s->save_nSelectors = 0;
147 s->save_EOB = 0;
148 s->save_groupNo = 0;
149 s->save_groupPos = 0;
150 s->save_nextSym = 0;
151 s->save_nblockMAX = 0;
152 s->save_nblock = 0;
153 s->save_es = 0;
154 s->save_N = 0;
155 s->save_curr = 0;
156 s->save_zt = 0;
157 s->save_zn = 0;
158 s->save_zvec = 0;
159 s->save_zj = 0;
160 s->save_gSel = 0;
161 s->save_gMinlen = 0;
162 s->save_gLimit = NULL;
163 s->save_gBase = NULL;
164 s->save_gPerm = NULL;
165 }
166
167 /*restore from the save area*/
168 i = s->save_i;
169 j = s->save_j;
170 t = s->save_t;
171 alphaSize = s->save_alphaSize;
172 nGroups = s->save_nGroups;
173 nSelectors = s->save_nSelectors;
174 EOB = s->save_EOB;
175 groupNo = s->save_groupNo;
176 groupPos = s->save_groupPos;
177 nextSym = s->save_nextSym;
178 nblockMAX = s->save_nblockMAX;
179 nblock = s->save_nblock;
180 es = s->save_es;
181 N = s->save_N;
182 curr = s->save_curr;
183 zt = s->save_zt;
184 zn = s->save_zn;
185 zvec = s->save_zvec;
186 zj = s->save_zj;
187 gSel = s->save_gSel;
188 gMinlen = s->save_gMinlen;
189 gLimit = s->save_gLimit;
190 gBase = s->save_gBase;
191 gPerm = s->save_gPerm;
192
193 retVal = BZ_OK;
194
195 switch (s->state) {
196
197 GET_UCHAR(BZ_X_MAGIC_1, uc);
198 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
199
200 GET_UCHAR(BZ_X_MAGIC_2, uc);
201 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
202
203 GET_UCHAR(BZ_X_MAGIC_3, uc)
204 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
205
206 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
207 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
208 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
209 s->blockSize100k -= BZ_HDR_0;
210
211 if (s->smallDecompress) {
212 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
213 s->ll4 = BZALLOC(
214 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
215 );
216 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
217 } else {
218 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
219 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
220 }
221
222 GET_UCHAR(BZ_X_BLKHDR_1, uc);
223
224 if (uc == 0x17) goto endhdr_2;
225 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
226 GET_UCHAR(BZ_X_BLKHDR_2, uc);
227 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
228 GET_UCHAR(BZ_X_BLKHDR_3, uc);
229 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
230 GET_UCHAR(BZ_X_BLKHDR_4, uc);
231 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
232 GET_UCHAR(BZ_X_BLKHDR_5, uc);
233 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
234 GET_UCHAR(BZ_X_BLKHDR_6, uc);
235 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
236
237 s->currBlockNo++;
238 if (s->verbosity >= 2)
239 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
240
241 s->storedBlockCRC = 0;
242 GET_UCHAR(BZ_X_BCRC_1, uc);
243 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
244 GET_UCHAR(BZ_X_BCRC_2, uc);
245 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
246 GET_UCHAR(BZ_X_BCRC_3, uc);
247 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
248 GET_UCHAR(BZ_X_BCRC_4, uc);
249 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
250
251 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
252
253 s->origPtr = 0;
254 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
255 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
256 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
257 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
258 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
259 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
260
261 if (s->origPtr < 0)
262 RETURN(BZ_DATA_ERROR);
263 if (s->origPtr > 10 + 100000*s->blockSize100k)
264 RETURN(BZ_DATA_ERROR);
265
266 /*--- Receive the mapping table ---*/
267 for (i = 0; i < 16; i++) {
268 GET_BIT(BZ_X_MAPPING_1, uc);
269 if (uc == 1)
270 s->inUse16[i] = True; else
271 s->inUse16[i] = False;
272 }
273
274 for (i = 0; i < 256; i++) s->inUse[i] = False;
275
276 for (i = 0; i < 16; i++)
277 if (s->inUse16[i])
278 for (j = 0; j < 16; j++) {
279 GET_BIT(BZ_X_MAPPING_2, uc);
280 if (uc == 1) s->inUse[i * 16 + j] = True;
281 }
282 makeMaps_d ( s );
283 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
284 alphaSize = s->nInUse+2;
285
286 /*--- Now the selectors ---*/
287 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
288 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
289 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
290 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
291 for (i = 0; i < nSelectors; i++) {
292 j = 0;
293 while (True) {
294 GET_BIT(BZ_X_SELECTOR_3, uc);
295 if (uc == 0) break;
296 j++;
297 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
298 }
299 s->selectorMtf[i] = j;
300 }
301
302 /*--- Undo the MTF values for the selectors. ---*/
303 {
304 UChar pos[BZ_N_GROUPS], tmp, v;
305 for (v = 0; v < nGroups; v++) pos[v] = v;
306
307 for (i = 0; i < nSelectors; i++) {
308 v = s->selectorMtf[i];
309 tmp = pos[v];
310 while (v > 0) { pos[v] = pos[v-1]; v--; }
311 pos[0] = tmp;
312 s->selector[i] = tmp;
313 }
314 }
315
316 /*--- Now the coding tables ---*/
317 for (t = 0; t < nGroups; t++) {
318 GET_BITS(BZ_X_CODING_1, curr, 5);
319 for (i = 0; i < alphaSize; i++) {
320 while (True) {
321 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
322 GET_BIT(BZ_X_CODING_2, uc);
323 if (uc == 0) break;
324 GET_BIT(BZ_X_CODING_3, uc);
325 if (uc == 0) curr++; else curr--;
326 }
327 s->len[t][i] = curr;
328 }
329 }
330
331 /*--- Create the Huffman decoding tables ---*/
332 for (t = 0; t < nGroups; t++) {
333 minLen = 32;
334 maxLen = 0;
335 for (i = 0; i < alphaSize; i++) {
336 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
337 if (s->len[t][i] < minLen) minLen = s->len[t][i];
338 }
339 BZ2_hbCreateDecodeTables (
340 &(s->limit[t][0]),
341 &(s->base[t][0]),
342 &(s->perm[t][0]),
343 &(s->len[t][0]),
344 minLen, maxLen, alphaSize
345 );
346 s->minLens[t] = minLen;
347 }
348
349 /*--- Now the MTF values ---*/
350
351 EOB = s->nInUse+1;
352 nblockMAX = 100000 * s->blockSize100k;
353 groupNo = -1;
354 groupPos = 0;
355
356 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
357
358 /*-- MTF init --*/
359 {
360 Int32 ii, jj, kk;
361 kk = MTFA_SIZE-1;
362 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
363 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
364 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
365 kk--;
366 }
367 s->mtfbase[ii] = kk + 1;
368 }
369 }
370 /*-- end MTF init --*/
371
372 nblock = 0;
373 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
374
375 while (True) {
376
377 if (nextSym == EOB) break;
378
379 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
380
381 es = -1;
382 N = 1;
383 do {
384 /* Check that N doesn't get too big, so that es doesn't
385 go negative. The maximum value that can be
386 RUNA/RUNB encoded is equal to the block size (post
387 the initial RLE), viz, 900k, so bounding N at 2
388 million should guard against overflow without
389 rejecting any legitimate inputs. */
390 if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
391 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
392 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
393 N = N * 2;
394 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
395 }
396 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
397
398 es++;
399 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
400 s->unzftab[uc] += es;
401
402 if (s->smallDecompress)
403 while (es > 0) {
404 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
405 s->ll16[nblock] = (UInt16)uc;
406 nblock++;
407 es--;
408 }
409 else
410 while (es > 0) {
411 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
412 s->tt[nblock] = (UInt32)uc;
413 nblock++;
414 es--;
415 };
416
417 continue;
418
419 } else {
420
421 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
422
423 /*-- uc = MTF ( nextSym-1 ) --*/
424 {
425 Int32 ii, jj, kk, pp, lno, off;
426 UInt32 nn;
427 nn = (UInt32)(nextSym - 1);
428
429 if (nn < MTFL_SIZE) {
430 /* avoid general-case expense */
431 pp = s->mtfbase[0];
432 uc = s->mtfa[pp+nn];
433 while (nn > 3) {
434 Int32 z = pp+nn;
435 s->mtfa[(z) ] = s->mtfa[(z)-1];
436 s->mtfa[(z)-1] = s->mtfa[(z)-2];
437 s->mtfa[(z)-2] = s->mtfa[(z)-3];
438 s->mtfa[(z)-3] = s->mtfa[(z)-4];
439 nn -= 4;
440 }
441 while (nn > 0) {
442 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
443 };
444 s->mtfa[pp] = uc;
445 } else {
446 /* general case */
447 lno = nn / MTFL_SIZE;
448 off = nn % MTFL_SIZE;
449 pp = s->mtfbase[lno] + off;
450 uc = s->mtfa[pp];
451 while (pp > s->mtfbase[lno]) {
452 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
453 };
454 s->mtfbase[lno]++;
455 while (lno > 0) {
456 s->mtfbase[lno]--;
457 s->mtfa[s->mtfbase[lno]]
458 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
459 lno--;
460 }
461 s->mtfbase[0]--;
462 s->mtfa[s->mtfbase[0]] = uc;
463 if (s->mtfbase[0] == 0) {
464 kk = MTFA_SIZE-1;
465 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
466 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
467 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
468 kk--;
469 }
470 s->mtfbase[ii] = kk + 1;
471 }
472 }
473 }
474 }
475 /*-- end uc = MTF ( nextSym-1 ) --*/
476
477 s->unzftab[s->seqToUnseq[uc]]++;
478 if (s->smallDecompress)
479 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
480 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
481 nblock++;
482
483 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
484 continue;
485 }
486 }
487
488 /* Now we know what nblock is, we can do a better sanity
489 check on s->origPtr.
490 */
491 if (s->origPtr < 0 || s->origPtr >= nblock)
492 RETURN(BZ_DATA_ERROR);
493
494 /*-- Set up cftab to facilitate generation of T^(-1) --*/
495 /* Check: unzftab entries in range. */
496 for (i = 0; i <= 255; i++) {
497 if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
498 RETURN(BZ_DATA_ERROR);
499 }
500 /* Actually generate cftab. */
501 s->cftab[0] = 0;
502 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
503 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
504 /* Check: cftab entries in range. */
505 for (i = 0; i <= 256; i++) {
506 if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
507 /* s->cftab[i] can legitimately be == nblock */
508 RETURN(BZ_DATA_ERROR);
509 }
510 }
511 /* Check: cftab entries non-descending. */
512 for (i = 1; i <= 256; i++) {
513 if (s->cftab[i-1] > s->cftab[i]) {
514 RETURN(BZ_DATA_ERROR);
515 }
516 }
517
518 s->state_out_len = 0;
519 s->state_out_ch = 0;
520 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
521 s->state = BZ_X_OUTPUT;
522 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
523
524 if (s->smallDecompress) {
525
526 /*-- Make a copy of cftab, used in generation of T --*/
527 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
528
529 /*-- compute the T vector --*/
530 for (i = 0; i < nblock; i++) {
531 uc = (UChar)(s->ll16[i]);
532 SET_LL(i, s->cftabCopy[uc]);
533 s->cftabCopy[uc]++;
534 }
535
536 /*-- Compute T^(-1) by pointer reversal on T --*/
537 i = s->origPtr;
538 j = GET_LL(i);
539 do {
540 Int32 tmp = GET_LL(j);
541 SET_LL(j, i);
542 i = j;
543 j = tmp;
544 }
545 while (i != s->origPtr);
546
547 s->tPos = s->origPtr;
548 s->nblock_used = 0;
549 if (s->blockRandomised) {
550 BZ_RAND_INIT_MASK;
551 BZ_GET_SMALL(s->k0); s->nblock_used++;
552 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
553 } else {
554 BZ_GET_SMALL(s->k0); s->nblock_used++;
555 }
556
557 } else {
558
559 /*-- compute the T^(-1) vector --*/
560 for (i = 0; i < nblock; i++) {
561 uc = (UChar)(s->tt[i] & 0xff);
562 s->tt[s->cftab[uc]] |= (i << 8);
563 s->cftab[uc]++;
564 }
565
566 s->tPos = s->tt[s->origPtr] >> 8;
567 s->nblock_used = 0;
568 if (s->blockRandomised) {
569 BZ_RAND_INIT_MASK;
570 BZ_GET_FAST(s->k0); s->nblock_used++;
571 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
572 } else {
573 BZ_GET_FAST(s->k0); s->nblock_used++;
574 }
575
576 }
577
578 RETURN(BZ_OK);
579
580
581
582 endhdr_2:
583
584 GET_UCHAR(BZ_X_ENDHDR_2, uc);
585 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
586 GET_UCHAR(BZ_X_ENDHDR_3, uc);
587 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
588 GET_UCHAR(BZ_X_ENDHDR_4, uc);
589 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
590 GET_UCHAR(BZ_X_ENDHDR_5, uc);
591 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
592 GET_UCHAR(BZ_X_ENDHDR_6, uc);
593 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
594
595 s->storedCombinedCRC = 0;
596 GET_UCHAR(BZ_X_CCRC_1, uc);
597 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
598 GET_UCHAR(BZ_X_CCRC_2, uc);
599 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
600 GET_UCHAR(BZ_X_CCRC_3, uc);
601 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
602 GET_UCHAR(BZ_X_CCRC_4, uc);
603 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
604
605 s->state = BZ_X_IDLE;
606 RETURN(BZ_STREAM_END);
607
608 default: AssertH ( False, 4001 );
609 }
610
611 AssertH ( False, 4002 );
612
613 save_state_and_return:
614
615 s->save_i = i;
616 s->save_j = j;
617 s->save_t = t;
618 s->save_alphaSize = alphaSize;
619 s->save_nGroups = nGroups;
620 s->save_nSelectors = nSelectors;
621 s->save_EOB = EOB;
622 s->save_groupNo = groupNo;
623 s->save_groupPos = groupPos;
624 s->save_nextSym = nextSym;
625 s->save_nblockMAX = nblockMAX;
626 s->save_nblock = nblock;
627 s->save_es = es;
628 s->save_N = N;
629 s->save_curr = curr;
630 s->save_zt = zt;
631 s->save_zn = zn;
632 s->save_zvec = zvec;
633 s->save_zj = zj;
634 s->save_gSel = gSel;
635 s->save_gMinlen = gMinlen;
636 s->save_gLimit = gLimit;
637 s->save_gBase = gBase;
638 s->save_gPerm = gPerm;
639
640 return retVal;
641}
642
643
644/*-------------------------------------------------------------*/
645/*--- end decompress.c ---*/
646/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/huffman.c b/utils/bzip2/huffman.c
new file mode 100644
index 0000000000..2283fdbc5a
--- /dev/null
+++ b/utils/bzip2/huffman.c
@@ -0,0 +1,205 @@
1
2/*-------------------------------------------------------------*/
3/*--- Huffman coding low-level stuff ---*/
4/*--- huffman.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#include "bzlib_private.h"
23
24/*---------------------------------------------------*/
25#define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
26#define DEPTHOF(zz1) ((zz1) & 0x000000ff)
27#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
28
29#define ADDWEIGHTS(zw1,zw2) \
30 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
31 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
32
33#define UPHEAP(z) \
34{ \
35 Int32 zz, tmp; \
36 zz = z; tmp = heap[zz]; \
37 while (weight[tmp] < weight[heap[zz >> 1]]) { \
38 heap[zz] = heap[zz >> 1]; \
39 zz >>= 1; \
40 } \
41 heap[zz] = tmp; \
42}
43
44#define DOWNHEAP(z) \
45{ \
46 Int32 zz, yy, tmp; \
47 zz = z; tmp = heap[zz]; \
48 while (True) { \
49 yy = zz << 1; \
50 if (yy > nHeap) break; \
51 if (yy < nHeap && \
52 weight[heap[yy+1]] < weight[heap[yy]]) \
53 yy++; \
54 if (weight[tmp] < weight[heap[yy]]) break; \
55 heap[zz] = heap[yy]; \
56 zz = yy; \
57 } \
58 heap[zz] = tmp; \
59}
60
61
62/*---------------------------------------------------*/
63void BZ2_hbMakeCodeLengths ( UChar *len,
64 Int32 *freq,
65 Int32 alphaSize,
66 Int32 maxLen )
67{
68 /*--
69 Nodes and heap entries run from 1. Entry 0
70 for both the heap and nodes is a sentinel.
71 --*/
72 Int32 nNodes, nHeap, n1, n2, i, j, k;
73 Bool tooLong;
74
75 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
76 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
77 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
78
79 for (i = 0; i < alphaSize; i++)
80 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
81
82 while (True) {
83
84 nNodes = alphaSize;
85 nHeap = 0;
86
87 heap[0] = 0;
88 weight[0] = 0;
89 parent[0] = -2;
90
91 for (i = 1; i <= alphaSize; i++) {
92 parent[i] = -1;
93 nHeap++;
94 heap[nHeap] = i;
95 UPHEAP(nHeap);
96 }
97
98 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
99
100 while (nHeap > 1) {
101 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
102 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
103 nNodes++;
104 parent[n1] = parent[n2] = nNodes;
105 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
106 parent[nNodes] = -1;
107 nHeap++;
108 heap[nHeap] = nNodes;
109 UPHEAP(nHeap);
110 }
111
112 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
113
114 tooLong = False;
115 for (i = 1; i <= alphaSize; i++) {
116 j = 0;
117 k = i;
118 while (parent[k] >= 0) { k = parent[k]; j++; }
119 len[i-1] = j;
120 if (j > maxLen) tooLong = True;
121 }
122
123 if (! tooLong) break;
124
125 /* 17 Oct 04: keep-going condition for the following loop used
126 to be 'i < alphaSize', which missed the last element,
127 theoretically leading to the possibility of the compressor
128 looping. However, this count-scaling step is only needed if
129 one of the generated Huffman code words is longer than
130 maxLen, which up to and including version 1.0.2 was 20 bits,
131 which is extremely unlikely. In version 1.0.3 maxLen was
132 changed to 17 bits, which has minimal effect on compression
133 ratio, but does mean this scaling step is used from time to
134 time, enough to verify that it works.
135
136 This means that bzip2-1.0.3 and later will only produce
137 Huffman codes with a maximum length of 17 bits. However, in
138 order to preserve backwards compatibility with bitstreams
139 produced by versions pre-1.0.3, the decompressor must still
140 handle lengths of up to 20. */
141
142 for (i = 1; i <= alphaSize; i++) {
143 j = weight[i] >> 8;
144 j = 1 + (j / 2);
145 weight[i] = j << 8;
146 }
147 }
148}
149
150
151/*---------------------------------------------------*/
152void BZ2_hbAssignCodes ( Int32 *code,
153 UChar *length,
154 Int32 minLen,
155 Int32 maxLen,
156 Int32 alphaSize )
157{
158 Int32 n, vec, i;
159
160 vec = 0;
161 for (n = minLen; n <= maxLen; n++) {
162 for (i = 0; i < alphaSize; i++)
163 if (length[i] == n) { code[i] = vec; vec++; };
164 vec <<= 1;
165 }
166}
167
168
169/*---------------------------------------------------*/
170void BZ2_hbCreateDecodeTables ( Int32 *limit,
171 Int32 *base,
172 Int32 *perm,
173 UChar *length,
174 Int32 minLen,
175 Int32 maxLen,
176 Int32 alphaSize )
177{
178 Int32 pp, i, j, vec;
179
180 pp = 0;
181 for (i = minLen; i <= maxLen; i++)
182 for (j = 0; j < alphaSize; j++)
183 if (length[j] == i) { perm[pp] = j; pp++; };
184
185 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
186 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
187
188 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
189
190 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
191 vec = 0;
192
193 for (i = minLen; i <= maxLen; i++) {
194 vec += (base[i+1] - base[i]);
195 limit[i] = vec-1;
196 vec <<= 1;
197 }
198 for (i = minLen + 1; i <= maxLen; i++)
199 base[i] = ((limit[i-1] + 1) << 1) - base[i];
200}
201
202
203/*-------------------------------------------------------------*/
204/*--- end huffman.c ---*/
205/*-------------------------------------------------------------*/
diff --git a/utils/bzip2/randtable.c b/utils/bzip2/randtable.c
new file mode 100644
index 0000000000..6d62459906
--- /dev/null
+++ b/utils/bzip2/randtable.c
@@ -0,0 +1,84 @@
1
2/*-------------------------------------------------------------*/
3/*--- Table for randomising repetitive blocks ---*/
4/*--- randtable.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8 This file is part of bzip2/libbzip2, a program and library for
9 lossless, block-sorting data compression.
10
11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22#include "bzlib_private.h"
23
24
25/*---------------------------------------------*/
26Int32 BZ2_rNums[512] = {
27 619, 720, 127, 481, 931, 816, 813, 233, 566, 247,
28 985, 724, 205, 454, 863, 491, 741, 242, 949, 214,
29 733, 859, 335, 708, 621, 574, 73, 654, 730, 472,
30 419, 436, 278, 496, 867, 210, 399, 680, 480, 51,
31 878, 465, 811, 169, 869, 675, 611, 697, 867, 561,
32 862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
33 150, 238, 59, 379, 684, 877, 625, 169, 643, 105,
34 170, 607, 520, 932, 727, 476, 693, 425, 174, 647,
35 73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
36 909, 545, 703, 919, 874, 474, 882, 500, 594, 612,
37 641, 801, 220, 162, 819, 984, 589, 513, 495, 799,
38 161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
39 382, 596, 414, 171, 516, 375, 682, 485, 911, 276,
40 98, 553, 163, 354, 666, 933, 424, 341, 533, 870,
41 227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
42 469, 68, 770, 919, 190, 373, 294, 822, 808, 206,
43 184, 943, 795, 384, 383, 461, 404, 758, 839, 887,
44 715, 67, 618, 276, 204, 918, 873, 777, 604, 560,
45 951, 160, 578, 722, 79, 804, 96, 409, 713, 940,
46 652, 934, 970, 447, 318, 353, 859, 672, 112, 785,
47 645, 863, 803, 350, 139, 93, 354, 99, 820, 908,
48 609, 772, 154, 274, 580, 184, 79, 626, 630, 742,
49 653, 282, 762, 623, 680, 81, 927, 626, 789, 125,
50 411, 521, 938, 300, 821, 78, 343, 175, 128, 250,
51 170, 774, 972, 275, 999, 639, 495, 78, 352, 126,
52 857, 956, 358, 619, 580, 124, 737, 594, 701, 612,
53 669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
54 944, 375, 748, 52, 600, 747, 642, 182, 862, 81,
55 344, 805, 988, 739, 511, 655, 814, 334, 249, 515,
56 897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
57 433, 837, 553, 268, 926, 240, 102, 654, 459, 51,
58 686, 754, 806, 760, 493, 403, 415, 394, 687, 700,
59 946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
60 978, 321, 576, 617, 626, 502, 894, 679, 243, 440,
61 680, 879, 194, 572, 640, 724, 926, 56, 204, 700,
62 707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
63 297, 59, 87, 824, 713, 663, 412, 693, 342, 606,
64 134, 108, 571, 364, 631, 212, 174, 643, 304, 329,
65 343, 97, 430, 751, 497, 314, 983, 374, 822, 928,
66 140, 206, 73, 263, 980, 736, 876, 478, 430, 305,
67 170, 514, 364, 692, 829, 82, 855, 953, 676, 246,
68 369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
69 804, 378, 215, 828, 592, 281, 565, 555, 710, 82,
70 896, 831, 547, 261, 524, 462, 293, 465, 502, 56,
71 661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
72 768, 550, 608, 933, 378, 286, 215, 979, 792, 961,
73 61, 688, 793, 644, 986, 403, 106, 366, 905, 644,
74 372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
75 780, 773, 635, 389, 707, 100, 626, 958, 165, 504,
76 920, 176, 193, 713, 857, 265, 203, 50, 668, 108,
77 645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
78 936, 638
79};
80
81
82/*-------------------------------------------------------------*/
83/*--- end randtable.c ---*/
84/*-------------------------------------------------------------*/
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-15 23:48:24 +0000