aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDenis Vlasenko <vda.linux@googlemail.com>2007-10-14 00:43:01 +0000
committerDenis Vlasenko <vda.linux@googlemail.com>2007-10-14 00:43:01 +0000
commitef3aabe906a351f0bdf97199b4f38a2c6b54eaa5 (patch)
tree7ce8c73be864396eb656c2ef59ef797824a07942
parent77f1ec1b9bf100e6c10aa0856c7156e321511785 (diff)
downloadbusybox-w32-ef3aabe906a351f0bdf97199b4f38a2c6b54eaa5.tar.gz
busybox-w32-ef3aabe906a351f0bdf97199b4f38a2c6b54eaa5.tar.bz2
busybox-w32-ef3aabe906a351f0bdf97199b4f38a2c6b54eaa5.zip
bzip2: size reduction, to just below 9k.
Diffstat
-rw-r--r--archival/bz/blocksort.c339
-rw-r--r--archival/bz/bzlib.c218
-rw-r--r--archival/bz/bzlib.h2
-rw-r--r--archival/bz/bzlib_private.h84
-rw-r--r--archival/bz/compress.c154
-rw-r--r--archival/bz/huffman.c4
-rw-r--r--archival/bzip2.c30
7 files changed, 375 insertions, 456 deletions
diff --git a/archival/bz/blocksort.c b/archival/bz/blocksort.c
index 7d2856ba7..ec8a2a56b 100644
--- a/archival/bz/blocksort.c
+++ b/archival/bz/blocksort.c
@@ -25,6 +25,34 @@ in the file LICENSE.
25 25
26/* #include "bzlib_private.h" */ 26/* #include "bzlib_private.h" */
27 27
28#define mswap(zz1, zz2) \
29{ \
30 int32_t zztmp = zz1; \
31 zz1 = zz2; \
32 zz2 = zztmp; \
33}
34
35static
36/* No measurable speed gain with inlining */
37/* ALWAYS_INLINE */
38void mvswap(uint32_t* ptr, int32_t zzp1, int32_t zzp2, int32_t zzn)
39{
40 while (zzn > 0) {
41 mswap(ptr[zzp1], ptr[zzp2]);
42 zzp1++;
43 zzp2++;
44 zzn--;
45 }
46}
47
48static
49ALWAYS_INLINE
50int32_t mmin(int32_t a, int32_t b)
51{
52 return (a < b) ? a : b;
53}
54
55
28/*---------------------------------------------*/ 56/*---------------------------------------------*/
29/*--- Fallback O(N log(N)^2) sorting ---*/ 57/*--- Fallback O(N log(N)^2) sorting ---*/
30/*--- algorithm, for repetitive blocks ---*/ 58/*--- algorithm, for repetitive blocks ---*/
@@ -64,29 +92,6 @@ void fallbackSimpleSort(uint32_t* fmap,
64 92
65 93
66/*---------------------------------------------*/ 94/*---------------------------------------------*/
67#define fswap(zz1, zz2) \
68{ \
69 int32_t zztmp = zz1; \
70 zz1 = zz2; \
71 zz2 = zztmp; \
72}
73
74#define fvswap(zzp1, zzp2, zzn) \
75{ \
76 int32_t yyp1 = (zzp1); \
77 int32_t yyp2 = (zzp2); \
78 int32_t yyn = (zzn); \
79 while (yyn > 0) { \
80 fswap(fmap[yyp1], fmap[yyp2]); \
81 yyp1++; \
82 yyp2++; \
83 yyn--; \
84 } \
85}
86
87
88#define fmin(a,b) ((a) < (b)) ? (a) : (b)
89
90#define fpush(lz,hz) { \ 95#define fpush(lz,hz) { \
91 stackLo[sp] = lz; \ 96 stackLo[sp] = lz; \
92 stackHi[sp] = hz; \ 97 stackHi[sp] = hz; \
@@ -102,7 +107,6 @@ void fallbackSimpleSort(uint32_t* fmap,
102#define FALLBACK_QSORT_SMALL_THRESH 10 107#define FALLBACK_QSORT_SMALL_THRESH 10
103#define FALLBACK_QSORT_STACK_SIZE 100 108#define FALLBACK_QSORT_STACK_SIZE 100
104 109
105
106static 110static
107void fallbackQSort3(uint32_t* fmap, 111void fallbackQSort3(uint32_t* fmap,
108 uint32_t* eclass, 112 uint32_t* eclass,
@@ -153,7 +157,7 @@ void fallbackQSort3(uint32_t* fmap,
153 if (unLo > unHi) break; 157 if (unLo > unHi) break;
154 n = (int32_t)eclass[fmap[unLo]] - (int32_t)med; 158 n = (int32_t)eclass[fmap[unLo]] - (int32_t)med;
155 if (n == 0) { 159 if (n == 0) {
156 fswap(fmap[unLo], fmap[ltLo]); 160 mswap(fmap[unLo], fmap[ltLo]);
157 ltLo++; 161 ltLo++;
158 unLo++; 162 unLo++;
159 continue; 163 continue;
@@ -165,7 +169,7 @@ void fallbackQSort3(uint32_t* fmap,
165 if (unLo > unHi) break; 169 if (unLo > unHi) break;
166 n = (int32_t)eclass[fmap[unHi]] - (int32_t)med; 170 n = (int32_t)eclass[fmap[unHi]] - (int32_t)med;
167 if (n == 0) { 171 if (n == 0) {
168 fswap(fmap[unHi], fmap[gtHi]); 172 mswap(fmap[unHi], fmap[gtHi]);
169 gtHi--; unHi--; 173 gtHi--; unHi--;
170 continue; 174 continue;
171 }; 175 };
@@ -173,15 +177,15 @@ void fallbackQSort3(uint32_t* fmap,
173 unHi--; 177 unHi--;
174 } 178 }
175 if (unLo > unHi) break; 179 if (unLo > unHi) break;
176 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; 180 mswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
177 } 181 }
178 182
179 AssertD(unHi == unLo-1, "fallbackQSort3(2)"); 183 AssertD(unHi == unLo-1, "fallbackQSort3(2)");
180 184
181 if (gtHi < ltLo) continue; 185 if (gtHi < ltLo) continue;
182 186
183 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); 187 n = mmin(ltLo-lo, unLo-ltLo); mvswap(fmap, lo, unLo-n, n);
184 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); 188 m = mmin(hi-gtHi, gtHi-unHi); mvswap(fmap, unLo, hi-m+1, m);
185 189
186 n = lo + unLo - ltLo - 1; 190 n = lo + unLo - ltLo - 1;
187 m = hi - (gtHi - unHi) + 1; 191 m = hi - (gtHi - unHi) + 1;
@@ -196,11 +200,8 @@ void fallbackQSort3(uint32_t* fmap,
196 } 200 }
197} 201}
198 202
199#undef fmin
200#undef fpush 203#undef fpush
201#undef fpop 204#undef fpop
202#undef fswap
203#undef fvswap
204#undef FALLBACK_QSORT_SMALL_THRESH 205#undef FALLBACK_QSORT_SMALL_THRESH
205#undef FALLBACK_QSORT_STACK_SIZE 206#undef FALLBACK_QSORT_STACK_SIZE
206 207
@@ -209,11 +210,11 @@ void fallbackQSort3(uint32_t* fmap,
209/* Pre: 210/* Pre:
210 * nblock > 0 211 * nblock > 0
211 * eclass exists for [0 .. nblock-1] 212 * eclass exists for [0 .. nblock-1]
212 * ((UChar*)eclass) [0 .. nblock-1] holds block 213 * ((uint8_t*)eclass) [0 .. nblock-1] holds block
213 * ptr exists for [0 .. nblock-1] 214 * ptr exists for [0 .. nblock-1]
214 * 215 *
215 * Post: 216 * Post:
216 * ((UChar*)eclass) [0 .. nblock-1] holds block 217 * ((uint8_t*)eclass) [0 .. nblock-1] holds block
217 * All other areas of eclass destroyed 218 * All other areas of eclass destroyed
218 * fmap [0 .. nblock-1] holds sorted order 219 * fmap [0 .. nblock-1] holds sorted order
219 * bhtab[0 .. 2+(nblock/32)] destroyed 220 * bhtab[0 .. 2+(nblock/32)] destroyed
@@ -236,7 +237,7 @@ void fallbackSort(uint32_t* fmap,
236 int32_t H, i, j, k, l, r, cc, cc1; 237 int32_t H, i, j, k, l, r, cc, cc1;
237 int32_t nNotDone; 238 int32_t nNotDone;
238 int32_t nBhtab; 239 int32_t nBhtab;
239 UChar* eclass8 = (UChar*)eclass; 240 uint8_t* eclass8 = (uint8_t*)eclass;
240 241
241 /* 242 /*
242 * Initial 1-char radix sort to generate 243 * Initial 1-char radix sort to generate
@@ -287,7 +288,7 @@ void fallbackSort(uint32_t* fmap,
287 r = -1; 288 r = -1;
288 while (1) { 289 while (1) {
289 290
290 /*-- find the next non-singleton bucket --*/ 291 /*-- find the next non-singleton bucket --*/
291 k = r + 1; 292 k = r + 1;
292 while (ISSET_BH(k) && UNALIGNED_BH(k)) 293 while (ISSET_BH(k) && UNALIGNED_BH(k))
293 k++; 294 k++;
@@ -340,7 +341,7 @@ void fallbackSort(uint32_t* fmap,
340 while (ftabCopy[j] == 0) 341 while (ftabCopy[j] == 0)
341 j++; 342 j++;
342 ftabCopy[j]--; 343 ftabCopy[j]--;
343 eclass8[fmap[i]] = (UChar)j; 344 eclass8[fmap[i]] = (uint8_t)j;
344 } 345 }
345 AssertH(j < 256, 1005); 346 AssertH(j < 256, 1005);
346} 347}
@@ -360,133 +361,83 @@ void fallbackSort(uint32_t* fmap,
360 361
361/*---------------------------------------------*/ 362/*---------------------------------------------*/
362static 363static
363inline 364NOINLINE
364Bool mainGtU( 365int mainGtU(
365 uint32_t i1, 366 uint32_t i1,
366 uint32_t i2, 367 uint32_t i2,
367 UChar* block, 368 uint8_t* block,
368 uint16_t* quadrant, 369 uint16_t* quadrant,
369 uint32_t nblock, 370 uint32_t nblock,
370 int32_t* budget) 371 int32_t* budget)
371{ 372{
372 int32_t k; 373 int32_t k;
373 UChar c1, c2; 374 uint8_t c1, c2;
374 uint16_t s1, s2; 375 uint16_t s1, s2;
375 376
376///unrolling 377/* Loop unrolling here is actually very useful
377 AssertD(i1 != i2, "mainGtU"); 378 * (generated code is much simpler),
378 /* 1 */ 379 * code size increase is only 270 bytes (i386)
379 c1 = block[i1]; c2 = block[i2]; 380 * but speeds up compression 10% overall
380 if (c1 != c2) return (c1 > c2); 381 */
381 i1++; i2++;
382 /* 2 */
383 c1 = block[i1]; c2 = block[i2];
384 if (c1 != c2) return (c1 > c2);
385 i1++; i2++;
386 /* 3 */
387 c1 = block[i1]; c2 = block[i2];
388 if (c1 != c2) return (c1 > c2);
389 i1++; i2++;
390 /* 4 */
391 c1 = block[i1]; c2 = block[i2];
392 if (c1 != c2) return (c1 > c2);
393 i1++; i2++;
394 /* 5 */
395 c1 = block[i1]; c2 = block[i2];
396 if (c1 != c2) return (c1 > c2);
397 i1++; i2++;
398 /* 6 */
399 c1 = block[i1]; c2 = block[i2];
400 if (c1 != c2) return (c1 > c2);
401 i1++; i2++;
402 /* 7 */
403 c1 = block[i1]; c2 = block[i2];
404 if (c1 != c2) return (c1 > c2);
405 i1++; i2++;
406 /* 8 */
407 c1 = block[i1]; c2 = block[i2];
408 if (c1 != c2) return (c1 > c2);
409 i1++; i2++;
410 /* 9 */
411 c1 = block[i1]; c2 = block[i2];
412 if (c1 != c2) return (c1 > c2);
413 i1++; i2++;
414 /* 10 */
415 c1 = block[i1]; c2 = block[i2];
416 if (c1 != c2) return (c1 > c2);
417 i1++; i2++;
418 /* 11 */
419 c1 = block[i1]; c2 = block[i2];
420 if (c1 != c2) return (c1 > c2);
421 i1++; i2++;
422 /* 12 */
423 c1 = block[i1]; c2 = block[i2];
424 if (c1 != c2) return (c1 > c2);
425 i1++; i2++;
426 382
427 k = nblock + 8; 383#if CONFIG_BZIP2_FEATURE_SPEED >= 1
428 384
429///unrolling 385#define TIMES_8(code) \
430 do { 386 code; code; code; code; \
431 /* 1 */ 387 code; code; code; code;
432 c1 = block[i1]; c2 = block[i2]; 388#define TIMES_12(code) \
433 if (c1 != c2) return (c1 > c2); 389 code; code; code; code; \
434 s1 = quadrant[i1]; s2 = quadrant[i2]; 390 code; code; code; code; \
435 if (s1 != s2) return (s1 > s2); 391 code; code; code; code;
436 i1++; i2++; 392
437 /* 2 */ 393#else
438 c1 = block[i1]; c2 = block[i2]; 394
439 if (c1 != c2) return (c1 > c2); 395#define TIMES_8(code) \
440 s1 = quadrant[i1]; s2 = quadrant[i2]; 396{ \
441 if (s1 != s2) return (s1 > s2); 397 int nn = 8; \
442 i1++; i2++; 398 do { \
443 /* 3 */ 399 code; \
444 c1 = block[i1]; c2 = block[i2]; 400 } while (--nn); \
445 if (c1 != c2) return (c1 > c2); 401}
446 s1 = quadrant[i1]; s2 = quadrant[i2]; 402#define TIMES_12(code) \
447 if (s1 != s2) return (s1 > s2); 403{ \
448 i1++; i2++; 404 int nn = 12; \
449 /* 4 */ 405 do { \
450 c1 = block[i1]; c2 = block[i2]; 406 code; \
451 if (c1 != c2) return (c1 > c2); 407 } while (--nn); \
452 s1 = quadrant[i1]; s2 = quadrant[i2]; 408}
453 if (s1 != s2) return (s1 > s2); 409
454 i1++; i2++; 410#endif
455 /* 5 */ 411
456 c1 = block[i1]; c2 = block[i2]; 412 AssertD(i1 != i2, "mainGtU");
457 if (c1 != c2) return (c1 > c2); 413 TIMES_12(
458 s1 = quadrant[i1]; s2 = quadrant[i2];
459 if (s1 != s2) return (s1 > s2);
460 i1++; i2++;
461 /* 6 */
462 c1 = block[i1]; c2 = block[i2];
463 if (c1 != c2) return (c1 > c2);
464 s1 = quadrant[i1]; s2 = quadrant[i2];
465 if (s1 != s2) return (s1 > s2);
466 i1++; i2++;
467 /* 7 */
468 c1 = block[i1]; c2 = block[i2];
469 if (c1 != c2) return (c1 > c2);
470 s1 = quadrant[i1]; s2 = quadrant[i2];
471 if (s1 != s2) return (s1 > s2);
472 i1++; i2++;
473 /* 8 */
474 c1 = block[i1]; c2 = block[i2]; 414 c1 = block[i1]; c2 = block[i2];
475 if (c1 != c2) return (c1 > c2); 415 if (c1 != c2) return (c1 > c2);
476 s1 = quadrant[i1]; s2 = quadrant[i2];
477 if (s1 != s2) return (s1 > s2);
478 i1++; i2++; 416 i1++; i2++;
417 )
418
419 k = nblock + 8;
420
421 do {
422 TIMES_8(
423 c1 = block[i1]; c2 = block[i2];
424 if (c1 != c2) return (c1 > c2);
425 s1 = quadrant[i1]; s2 = quadrant[i2];
426 if (s1 != s2) return (s1 > s2);
427 i1++; i2++;
428 )
479 429
480 if (i1 >= nblock) i1 -= nblock; 430 if (i1 >= nblock) i1 -= nblock;
481 if (i2 >= nblock) i2 -= nblock; 431 if (i2 >= nblock) i2 -= nblock;
482 432
483 k -= 8;
484 (*budget)--; 433 (*budget)--;
434 k -= 8;
485 } while (k >= 0); 435 } while (k >= 0);
486 436
487 return False; 437 return False;
488} 438}
489 439#undef TIMES_8
440#undef TIMES_12
490 441
491/*---------------------------------------------*/ 442/*---------------------------------------------*/
492/* 443/*
@@ -504,7 +455,7 @@ const int32_t incs[14] = {
504 455
505static 456static
506void mainSimpleSort(uint32_t* ptr, 457void mainSimpleSort(uint32_t* ptr,
507 UChar* block, 458 uint8_t* block,
508 uint16_t* quadrant, 459 uint16_t* quadrant,
509 int32_t nblock, 460 int32_t nblock,
510 int32_t lo, 461 int32_t lo,
@@ -527,8 +478,6 @@ void mainSimpleSort(uint32_t* ptr,
527 478
528 i = lo + h; 479 i = lo + h;
529 while (1) { 480 while (1) {
530
531///unrolling
532 /*-- copy 1 --*/ 481 /*-- copy 1 --*/
533 if (i > hi) break; 482 if (i > hi) break;
534 v = ptr[i]; 483 v = ptr[i];
@@ -541,6 +490,8 @@ void mainSimpleSort(uint32_t* ptr,
541 ptr[j] = v; 490 ptr[j] = v;
542 i++; 491 i++;
543 492
493/* 1.5% overall speedup, +290 bytes */
494#if CONFIG_BZIP2_FEATURE_SPEED >= 3
544 /*-- copy 2 --*/ 495 /*-- copy 2 --*/
545 if (i > hi) break; 496 if (i > hi) break;
546 v = ptr[i]; 497 v = ptr[i];
@@ -557,14 +508,14 @@ void mainSimpleSort(uint32_t* ptr,
557 if (i > hi) break; 508 if (i > hi) break;
558 v = ptr[i]; 509 v = ptr[i];
559 j = i; 510 j = i;
560 while (mainGtU (ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { 511 while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
561 ptr[j] = ptr[j-h]; 512 ptr[j] = ptr[j-h];
562 j = j - h; 513 j = j - h;
563 if (j <= (lo + h - 1)) break; 514 if (j <= (lo + h - 1)) break;
564 } 515 }
565 ptr[j] = v; 516 ptr[j] = v;
566 i++; 517 i++;
567 518#endif
568 if (*budget < 0) return; 519 if (*budget < 0) return;
569 } 520 }
570 } 521 }
@@ -580,36 +531,17 @@ void mainSimpleSort(uint32_t* ptr,
580 * Sedgewick and Jon L. Bentley. 531 * Sedgewick and Jon L. Bentley.
581 */ 532 */
582 533
583#define mswap(zz1, zz2) \
584{ \
585 int32_t zztmp = zz1; \
586 zz1 = zz2; \
587 zz2 = zztmp; \
588}
589
590#define mvswap(zzp1, zzp2, zzn) \
591{ \
592 int32_t yyp1 = (zzp1); \
593 int32_t yyp2 = (zzp2); \
594 int32_t yyn = (zzn); \
595 while (yyn > 0) { \
596 mswap(ptr[yyp1], ptr[yyp2]); \
597 yyp1++; \
598 yyp2++; \
599 yyn--; \
600 } \
601}
602
603static 534static
604inline 535ALWAYS_INLINE
605UChar mmed3(UChar a, UChar b, UChar c) 536uint8_t mmed3(uint8_t a, uint8_t b, uint8_t c)
606{ 537{
607 UChar t; 538 uint8_t t;
608 if (a > b) { 539 if (a > b) {
609 t = a; 540 t = a;
610 a = b; 541 a = b;
611 b = t; 542 b = t;
612 }; 543 };
544 /* here b >= a */
613 if (b > c) { 545 if (b > c) {
614 b = c; 546 b = c;
615 if (a > b) 547 if (a > b)
@@ -618,8 +550,6 @@ UChar mmed3(UChar a, UChar b, UChar c)
618 return b; 550 return b;
619} 551}
620 552
621#define mmin(a,b) ((a) < (b)) ? (a) : (b)
622
623#define mpush(lz,hz,dz) \ 553#define mpush(lz,hz,dz) \
624{ \ 554{ \
625 stackLo[sp] = lz; \ 555 stackLo[sp] = lz; \
@@ -636,8 +566,7 @@ UChar mmed3(UChar a, UChar b, UChar c)
636 dz = stackD [sp]; \ 566 dz = stackD [sp]; \
637} 567}
638 568
639 569#define mnextsize(az) (nextHi[az] - nextLo[az])
640#define mnextsize(az) (nextHi[az]-nextLo[az])
641 570
642#define mnextswap(az,bz) \ 571#define mnextswap(az,bz) \
643{ \ 572{ \
@@ -653,7 +582,7 @@ UChar mmed3(UChar a, UChar b, UChar c)
653 582
654static 583static
655void mainQSort3(uint32_t* ptr, 584void mainQSort3(uint32_t* ptr,
656 UChar* block, 585 uint8_t* block,
657 uint16_t* quadrant, 586 uint16_t* quadrant,
658 int32_t nblock, 587 int32_t nblock,
659 int32_t loSt, 588 int32_t loSt,
@@ -687,7 +616,6 @@ void mainQSort3(uint32_t* ptr,
687 return; 616 return;
688 continue; 617 continue;
689 } 618 }
690
691 med = (int32_t) mmed3(block[ptr[lo ] + d], 619 med = (int32_t) mmed3(block[ptr[lo ] + d],
692 block[ptr[hi ] + d], 620 block[ptr[hi ] + d],
693 block[ptr[(lo+hi) >> 1] + d]); 621 block[ptr[(lo+hi) >> 1] + d]);
@@ -736,8 +664,8 @@ void mainQSort3(uint32_t* ptr,
736 continue; 664 continue;
737 } 665 }
738 666
739 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); 667 n = mmin(ltLo-lo, unLo-ltLo); mvswap(ptr, lo, unLo-n, n);
740 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); 668 m = mmin(hi-gtHi, gtHi-unHi); mvswap(ptr, unLo, hi-m+1, m);
741 669
742 n = lo + unLo - ltLo - 1; 670 n = lo + unLo - ltLo - 1;
743 m = hi - (gtHi - unHi) + 1; 671 m = hi - (gtHi - unHi) + 1;
@@ -746,24 +674,21 @@ void mainQSort3(uint32_t* ptr,
746 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; 674 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
747 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; 675 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
748 676
749 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 677 if (mnextsize(0) < mnextsize(1)) mnextswap(0, 1);
750 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); 678 if (mnextsize(1) < mnextsize(2)) mnextswap(1, 2);
751 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 679 if (mnextsize(0) < mnextsize(1)) mnextswap(0, 1);
752 680
753 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)"); 681 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)");
754 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)"); 682 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)");
755 683
756 mpush (nextLo[0], nextHi[0], nextD[0]); 684 mpush(nextLo[0], nextHi[0], nextD[0]);
757 mpush (nextLo[1], nextHi[1], nextD[1]); 685 mpush(nextLo[1], nextHi[1], nextD[1]);
758 mpush (nextLo[2], nextHi[2], nextD[2]); 686 mpush(nextLo[2], nextHi[2], nextD[2]);
759 } 687 }
760} 688}
761 689
762#undef mswap
763#undef mvswap
764#undef mpush 690#undef mpush
765#undef mpop 691#undef mpop
766#undef mmin
767#undef mnextsize 692#undef mnextsize
768#undef mnextswap 693#undef mnextswap
769#undef MAIN_QSORT_SMALL_THRESH 694#undef MAIN_QSORT_SMALL_THRESH
@@ -775,11 +700,11 @@ void mainQSort3(uint32_t* ptr,
775/* Pre: 700/* Pre:
776 * nblock > N_OVERSHOOT 701 * nblock > N_OVERSHOOT
777 * block32 exists for [0 .. nblock-1 +N_OVERSHOOT] 702 * block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
778 * ((UChar*)block32) [0 .. nblock-1] holds block 703 * ((uint8_t*)block32) [0 .. nblock-1] holds block
779 * ptr exists for [0 .. nblock-1] 704 * ptr exists for [0 .. nblock-1]
780 * 705 *
781 * Post: 706 * Post:
782 * ((UChar*)block32) [0 .. nblock-1] holds block 707 * ((uint8_t*)block32) [0 .. nblock-1] holds block
783 * All other areas of block32 destroyed 708 * All other areas of block32 destroyed
784 * ftab[0 .. 65536] destroyed 709 * ftab[0 .. 65536] destroyed
785 * ptr [0 .. nblock-1] holds sorted order 710 * ptr [0 .. nblock-1] holds sorted order
@@ -792,7 +717,7 @@ void mainQSort3(uint32_t* ptr,
792 717
793static NOINLINE 718static NOINLINE
794void mainSort(uint32_t* ptr, 719void mainSort(uint32_t* ptr,
795 UChar* block, 720 uint8_t* block,
796 uint16_t* quadrant, 721 uint16_t* quadrant,
797 uint32_t* ftab, 722 uint32_t* ftab,
798 int32_t nblock, 723 int32_t nblock,
@@ -800,10 +725,10 @@ void mainSort(uint32_t* ptr,
800{ 725{
801 int32_t i, j, k, ss, sb; 726 int32_t i, j, k, ss, sb;
802 int32_t runningOrder[256]; 727 int32_t runningOrder[256];
803 Bool bigDone[256]; 728 Bool bigDone[256];
804 int32_t copyStart[256]; 729 int32_t copyStart[256];
805 int32_t copyEnd [256]; 730 int32_t copyEnd [256];
806 UChar c1; 731 uint8_t c1;
807 int32_t numQSorted; 732 int32_t numQSorted;
808 uint16_t s; 733 uint16_t s;
809 734
@@ -813,7 +738,8 @@ void mainSort(uint32_t* ptr,
813 738
814 j = block[0] << 8; 739 j = block[0] << 8;
815 i = nblock-1; 740 i = nblock-1;
816#if 0 741/* 3%, +300 bytes */
742#if CONFIG_BZIP2_FEATURE_SPEED >= 2
817 for (; i >= 3; i -= 4) { 743 for (; i >= 3; i -= 4) {
818 quadrant[i] = 0; 744 quadrant[i] = 0;
819 j = (j >> 8) |(((uint16_t)block[i]) << 8); 745 j = (j >> 8) |(((uint16_t)block[i]) << 8);
@@ -842,11 +768,12 @@ void mainSort(uint32_t* ptr,
842 } 768 }
843 769
844 /*-- Complete the initial radix sort --*/ 770 /*-- Complete the initial radix sort --*/
845 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; 771 for (i = 1; i <= 65536; i++)
772 ftab[i] += ftab[i-1];
846 773
847 s = block[0] << 8; 774 s = block[0] << 8;
848 i = nblock-1; 775 i = nblock-1;
849#if 0 776#if CONFIG_BZIP2_FEATURE_SPEED >= 2
850 for (; i >= 3; i -= 4) { 777 for (; i >= 3; i -= 4) {
851 s = (s >> 8) | (block[i] << 8); 778 s = (s >> 8) | (block[i] << 8);
852 j = ftab[s] -1; 779 j = ftab[s] -1;
@@ -940,8 +867,8 @@ void mainSort(uint32_t* ptr,
940 ptr, block, quadrant, nblock, 867 ptr, block, quadrant, nblock,
941 lo, hi, BZ_N_RADIX, budget 868 lo, hi, BZ_N_RADIX, budget
942 ); 869 );
943 numQSorted += (hi - lo + 1);
944 if (*budget < 0) return; 870 if (*budget < 0) return;
871 numQSorted += (hi - lo + 1);
945 } 872 }
946 } 873 }
947 ftab[sb] |= SETMASK; 874 ftab[sb] |= SETMASK;
@@ -980,14 +907,12 @@ void mainSort(uint32_t* ptr,
980 } 907 }
981 } 908 }
982 909
983 AssertH((copyStart[ss]-1 == copyEnd[ss]) 910 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
984 || 911 * Necessity for this case is demonstrated by compressing
985 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. 912 * a sequence of approximately 48.5 million of character
986 * Necessity for this case is demonstrated by compressing 913 * 251; 1.0.0/1.0.1 will then die here. */
987 * a sequence of approximately 48.5 million of character 914 AssertH((copyStart[ss]-1 == copyEnd[ss]) \
988 * 251; 1.0.0/1.0.1 will then die here. */ 915 || (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), 1007);
989 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
990 1007)
991 916
992 for (j = 0; j <= 255; j++) 917 for (j = 0; j <= 255; j++)
993 ftab[(j << 8) + ss] |= SETMASK; 918 ftab[(j << 8) + ss] |= SETMASK;
@@ -1062,11 +987,11 @@ void mainSort(uint32_t* ptr,
1062/* Pre: 987/* Pre:
1063 * nblock > 0 988 * nblock > 0
1064 * arr2 exists for [0 .. nblock-1 +N_OVERSHOOT] 989 * arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1065 * ((UChar*)arr2)[0 .. nblock-1] holds block 990 * ((uint8_t*)arr2)[0 .. nblock-1] holds block
1066 * arr1 exists for [0 .. nblock-1] 991 * arr1 exists for [0 .. nblock-1]
1067 * 992 *
1068 * Post: 993 * Post:
1069 * ((UChar*)arr2) [0 .. nblock-1] holds block 994 * ((uint8_t*)arr2) [0 .. nblock-1] holds block
1070 * All other areas of block destroyed 995 * All other areas of block destroyed
1071 * ftab[0 .. 65536] destroyed 996 * ftab[0 .. 65536] destroyed
1072 * arr1[0 .. nblock-1] holds sorted order 997 * arr1[0 .. nblock-1] holds sorted order
@@ -1075,11 +1000,11 @@ static NOINLINE
1075void BZ2_blockSort(EState* s) 1000void BZ2_blockSort(EState* s)
1076{ 1001{
1077 /* In original bzip2 1.0.4, it's a parameter, but 30 1002 /* In original bzip2 1.0.4, it's a parameter, but 30
1078 * should work ok. */ 1003 * (which was the default) should work ok. */
1079 enum { wfact = 30 }; 1004 enum { wfact = 30 };
1080 1005
1081 uint32_t* ptr = s->ptr; 1006 uint32_t* ptr = s->ptr;
1082 UChar* block = s->block; 1007 uint8_t* block = s->block;
1083 uint32_t* ftab = s->ftab; 1008 uint32_t* ftab = s->ftab;
1084 int32_t nblock = s->nblock; 1009 int32_t nblock = s->nblock;
1085 uint16_t* quadrant; 1010 uint16_t* quadrant;
diff --git a/archival/bz/bzlib.c b/archival/bz/bzlib.c
index 3125bb0bf..57a69747e 100644
--- a/archival/bz/bzlib.c
+++ b/archival/bz/bzlib.c
@@ -40,25 +40,27 @@ in the file LICENSE.
40/*---------------------------------------------------*/ 40/*---------------------------------------------------*/
41 41
42/*---------------------------------------------------*/ 42/*---------------------------------------------------*/
43#ifndef BZ_NO_STDIO 43#if BZ_LIGHT_DEBUG
44static void bz_assert_fail(int errcode) 44static
45void bz_assert_fail(int errcode)
45{ 46{
46 /* if (errcode == 1007) bb_error_msg_and_die("probably bad RAM"); */ 47 /* if (errcode == 1007) bb_error_msg_and_die("probably bad RAM"); */
47 bb_error_msg_and_die("bzip2 internal error %d", errcode); 48 bb_error_msg_and_die("internal error %d", errcode);
48} 49}
49#endif 50#endif
50 51
51
52/*---------------------------------------------------*/ 52/*---------------------------------------------------*/
53static 53static
54void prepare_new_block(EState* s) 54void prepare_new_block(EState* s)
55{ 55{
56 int32_t i; 56 int i;
57 s->nblock = 0; 57 s->nblock = 0;
58 s->numZ = 0; 58 s->numZ = 0;
59 s->state_out_pos = 0; 59 s->state_out_pos = 0;
60 BZ_INITIALISE_CRC(s->blockCRC); 60 BZ_INITIALISE_CRC(s->blockCRC);
61 for (i = 0; i < 256; i++) s->inUse[i] = False; 61 /* inlined memset would be nice to have here */
62 for (i = 0; i < 256; i++)
63 s->inUse[i] = 0;
62 s->blockNo++; 64 s->blockNo++;
63} 65}
64 66
@@ -97,9 +99,11 @@ void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
97 s->mtfv = (uint16_t*)s->arr1; 99 s->mtfv = (uint16_t*)s->arr1;
98 s->ptr = (uint32_t*)s->arr1; 100 s->ptr = (uint32_t*)s->arr1;
99 s->arr2 = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t)); 101 s->arr2 = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
100 s->block = (UChar*)s->arr2; 102 s->block = (uint8_t*)s->arr2;
101 s->ftab = xmalloc(65537 * sizeof(uint32_t)); 103 s->ftab = xmalloc(65537 * sizeof(uint32_t));
102 104
105 s->crc32table = crc32_filltable(NULL, 1);
106
103 s->state = BZ_S_INPUT; 107 s->state = BZ_S_INPUT;
104 s->mode = BZ_M_RUNNING; 108 s->mode = BZ_M_RUNNING;
105 s->blockSize100k = blockSize100k; 109 s->blockSize100k = blockSize100k;
@@ -107,7 +111,7 @@ void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
107 111
108 strm->state = s; 112 strm->state = s;
109 /*strm->total_in = 0;*/ 113 /*strm->total_in = 0;*/
110 strm->total_out = 0; 114 strm->total_out = 0;
111 init_RL(s); 115 init_RL(s);
112 prepare_new_block(s); 116 prepare_new_block(s);
113} 117}
@@ -118,31 +122,28 @@ static
118void add_pair_to_block(EState* s) 122void add_pair_to_block(EState* s)
119{ 123{
120 int32_t i; 124 int32_t i;
121 UChar ch = (UChar)(s->state_in_ch); 125 uint8_t ch = (uint8_t)(s->state_in_ch);
122 for (i = 0; i < s->state_in_len; i++) { 126 for (i = 0; i < s->state_in_len; i++) {
123 BZ_UPDATE_CRC(s->blockCRC, ch); 127 BZ_UPDATE_CRC(s, s->blockCRC, ch);
124 } 128 }
125 s->inUse[s->state_in_ch] = True; 129 s->inUse[s->state_in_ch] = 1;
126 switch (s->state_in_len) { 130 switch (s->state_in_len) {
127 case 1:
128 s->block[s->nblock] = (UChar)ch; s->nblock++;
129 break;
130 case 2:
131 s->block[s->nblock] = (UChar)ch; s->nblock++;
132 s->block[s->nblock] = (UChar)ch; s->nblock++;
133 break;
134 case 3: 131 case 3:
135 s->block[s->nblock] = (UChar)ch; s->nblock++; 132 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
136 s->block[s->nblock] = (UChar)ch; s->nblock++; 133 /* fall through */
137 s->block[s->nblock] = (UChar)ch; s->nblock++; 134 case 2:
135 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
136 /* fall through */
137 case 1:
138 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
138 break; 139 break;
139 default: 140 default:
140 s->inUse[s->state_in_len-4] = True; 141 s->inUse[s->state_in_len - 4] = 1;
141 s->block[s->nblock] = (UChar)ch; s->nblock++; 142 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
142 s->block[s->nblock] = (UChar)ch; s->nblock++; 143 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
143 s->block[s->nblock] = (UChar)ch; s->nblock++; 144 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
144 s->block[s->nblock] = (UChar)ch; s->nblock++; 145 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
145 s->block[s->nblock] = ((UChar)(s->state_in_len-4)); 146 s->block[s->nblock] = (uint8_t)(s->state_in_len - 4);
146 s->nblock++; 147 s->nblock++;
147 break; 148 break;
148 } 149 }
@@ -164,17 +165,16 @@ void flush_RL(EState* s)
164 uint32_t zchh = (uint32_t)(zchh0); \ 165 uint32_t zchh = (uint32_t)(zchh0); \
165 /*-- fast track the common case --*/ \ 166 /*-- fast track the common case --*/ \
166 if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \ 167 if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
167 UChar ch = (UChar)(zs->state_in_ch); \ 168 uint8_t ch = (uint8_t)(zs->state_in_ch); \
168 BZ_UPDATE_CRC(zs->blockCRC, ch); \ 169 BZ_UPDATE_CRC(zs, zs->blockCRC, ch); \
169 zs->inUse[zs->state_in_ch] = True; \ 170 zs->inUse[zs->state_in_ch] = 1; \
170 zs->block[zs->nblock] = (UChar)ch; \ 171 zs->block[zs->nblock] = (uint8_t)ch; \
171 zs->nblock++; \ 172 zs->nblock++; \
172 zs->state_in_ch = zchh; \ 173 zs->state_in_ch = zchh; \
173 } \ 174 } \
174 else \ 175 else \
175 /*-- general, uncommon cases --*/ \ 176 /*-- general, uncommon cases --*/ \
176 if (zchh != zs->state_in_ch || \ 177 if (zchh != zs->state_in_ch || zs->state_in_len == 255) { \
177 zs->state_in_len == 255) { \
178 if (zs->state_in_ch < 256) \ 178 if (zs->state_in_ch < 256) \
179 add_pair_to_block(zs); \ 179 add_pair_to_block(zs); \
180 zs->state_in_ch = zchh; \ 180 zs->state_in_ch = zchh; \
@@ -187,114 +187,117 @@ void flush_RL(EState* s)
187 187
188/*---------------------------------------------------*/ 188/*---------------------------------------------------*/
189static 189static
190Bool copy_input_until_stop(EState* s) 190void /*Bool*/ copy_input_until_stop(EState* s)
191{ 191{
192 Bool progress_in = False; 192 /*Bool progress_in = False;*/
193 193
194//vda: cannot simplify this until avail_in_expect is removed 194#ifdef SAME_CODE_AS_BELOW
195 if (s->mode == BZ_M_RUNNING) { 195 if (s->mode == BZ_M_RUNNING) {
196 /*-- fast track the common case --*/ 196 /*-- fast track the common case --*/
197 while (1) { 197 while (1) {
198 /*-- block full? --*/
199 if (s->nblock >= s->nblockMAX) break;
200 /*-- no input? --*/ 198 /*-- no input? --*/
201 if (s->strm->avail_in == 0) break; 199 if (s->strm->avail_in == 0) break;
202 progress_in = True; 200 /*-- block full? --*/
203 ADD_CHAR_TO_BLOCK(s, (uint32_t)(*((UChar*)(s->strm->next_in)))); 201 if (s->nblock >= s->nblockMAX) break;
202 /*progress_in = True;*/
203 ADD_CHAR_TO_BLOCK(s, (uint32_t)(*(uint8_t*)(s->strm->next_in)));
204 s->strm->next_in++; 204 s->strm->next_in++;
205 s->strm->avail_in--; 205 s->strm->avail_in--;
206 /*s->strm->total_in++;*/ 206 /*s->strm->total_in++;*/
207 } 207 }
208 } else { 208 } else
209#endif
210 {
209 /*-- general, uncommon case --*/ 211 /*-- general, uncommon case --*/
210 while (1) { 212 while (1) {
211 /*-- block full? --*/
212 if (s->nblock >= s->nblockMAX) break;
213 /*-- no input? --*/ 213 /*-- no input? --*/
214 if (s->strm->avail_in == 0) break; 214 if (s->strm->avail_in == 0) break;
215 /*-- flush/finish end? --*/ 215 /*-- block full? --*/
216 if (s->avail_in_expect == 0) break; 216 if (s->nblock >= s->nblockMAX) break;
217 progress_in = True; 217 //# /*-- flush/finish end? --*/
218 ADD_CHAR_TO_BLOCK(s, (uint32_t)(*((UChar*)(s->strm->next_in)))); 218 //# if (s->avail_in_expect == 0) break;
219 /*progress_in = True;*/
220 ADD_CHAR_TO_BLOCK(s, *(uint8_t*)(s->strm->next_in));
219 s->strm->next_in++; 221 s->strm->next_in++;
220 s->strm->avail_in--; 222 s->strm->avail_in--;
221 /*s->strm->total_in++;*/ 223 /*s->strm->total_in++;*/
222 s->avail_in_expect--; 224 //# s->avail_in_expect--;
223 } 225 }
224 } 226 }
225 return progress_in; 227 /*return progress_in;*/
226} 228}
227 229
228 230
229/*---------------------------------------------------*/ 231/*---------------------------------------------------*/
230static 232static
231Bool copy_output_until_stop(EState* s) 233void /*Bool*/ copy_output_until_stop(EState* s)
232{ 234{
233 Bool progress_out = False; 235 /*Bool progress_out = False;*/
234 236
235 while (1) { 237 while (1) {
236
237 /*-- no output space? --*/ 238 /*-- no output space? --*/
238 if (s->strm->avail_out == 0) break; 239 if (s->strm->avail_out == 0) break;
239 240
240 /*-- block done? --*/ 241 /*-- block done? --*/
241 if (s->state_out_pos >= s->numZ) break; 242 if (s->state_out_pos >= s->numZ) break;
242 243
243 progress_out = True; 244 /*progress_out = True;*/
244 *(s->strm->next_out) = s->zbits[s->state_out_pos]; 245 *(s->strm->next_out) = s->zbits[s->state_out_pos];
245 s->state_out_pos++; 246 s->state_out_pos++;
246 s->strm->avail_out--; 247 s->strm->avail_out--;
247 s->strm->next_out++; 248 s->strm->next_out++;
248 s->strm->total_out++; 249 s->strm->total_out++;
249 } 250 }
250 251 /*return progress_out;*/
251 return progress_out;
252} 252}
253 253
254 254
255/*---------------------------------------------------*/ 255/*---------------------------------------------------*/
256static 256static
257Bool handle_compress(bz_stream *strm) 257void /*Bool*/ handle_compress(bz_stream *strm)
258{ 258{
259 Bool progress_in = False; 259 /*Bool progress_in = False;*/
260 Bool progress_out = False; 260 /*Bool progress_out = False;*/
261 EState* s = strm->state; 261 EState* s = strm->state;
262 262
263 while (1) { 263 while (1) {
264 if (s->state == BZ_S_OUTPUT) { 264 if (s->state == BZ_S_OUTPUT) {
265 progress_out |= copy_output_until_stop(s); 265 /*progress_out |=*/ copy_output_until_stop(s);
266 if (s->state_out_pos < s->numZ) break; 266 if (s->state_out_pos < s->numZ) break;
267 if (s->mode == BZ_M_FINISHING 267 if (s->mode == BZ_M_FINISHING
268 && s->avail_in_expect == 0 268 //# && s->avail_in_expect == 0
269 && s->strm->avail_in == 0
269 && isempty_RL(s)) 270 && isempty_RL(s))
270 break; 271 break;
271 prepare_new_block(s); 272 prepare_new_block(s);
272 s->state = BZ_S_INPUT; 273 s->state = BZ_S_INPUT;
274#ifdef FLUSH_IS_UNUSED
273 if (s->mode == BZ_M_FLUSHING 275 if (s->mode == BZ_M_FLUSHING
274 && s->avail_in_expect == 0 276 && s->avail_in_expect == 0
275 && isempty_RL(s)) 277 && isempty_RL(s))
276 break; 278 break;
279#endif
277 } 280 }
278 281
279 if (s->state == BZ_S_INPUT) { 282 if (s->state == BZ_S_INPUT) {
280 progress_in |= copy_input_until_stop(s); 283 /*progress_in |=*/ copy_input_until_stop(s);
281 if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) { 284 //#if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
285 if (s->mode != BZ_M_RUNNING && s->strm->avail_in == 0) {
282 flush_RL(s); 286 flush_RL(s);
283 BZ2_compressBlock(s, (Bool)(s->mode == BZ_M_FINISHING)); 287 BZ2_compressBlock(s, (s->mode == BZ_M_FINISHING));
284 s->state = BZ_S_OUTPUT; 288 s->state = BZ_S_OUTPUT;
285 } else 289 } else
286 if (s->nblock >= s->nblockMAX) { 290 if (s->nblock >= s->nblockMAX) {
287 BZ2_compressBlock(s, False); 291 BZ2_compressBlock(s, 0);
288 s->state = BZ_S_OUTPUT; 292 s->state = BZ_S_OUTPUT;
289 } else 293 } else
290 if (s->strm->avail_in == 0) { 294 if (s->strm->avail_in == 0) {
291 break; 295 break;
292 } 296 }
293 } 297 }
294
295 } 298 }
296 299
297 return progress_in || progress_out; 300 /*return progress_in || progress_out;*/
298} 301}
299 302
300 303
@@ -302,82 +305,75 @@ Bool handle_compress(bz_stream *strm)
302static 305static
303int BZ2_bzCompress(bz_stream *strm, int action) 306int BZ2_bzCompress(bz_stream *strm, int action)
304{ 307{
305 Bool progress; 308 /*Bool progress;*/
306 EState* s; 309 EState* s;
307 if (strm == NULL) return BZ_PARAM_ERROR; 310
308 s = strm->state; 311 s = strm->state;
309 if (s == NULL) return BZ_PARAM_ERROR;
310 if (s->strm != strm) return BZ_PARAM_ERROR;
311 312
312 preswitch:
313 switch (s->mode) { 313 switch (s->mode) {
314
315 case BZ_M_IDLE:
316 return BZ_SEQUENCE_ERROR;
317
318 case BZ_M_RUNNING: 314 case BZ_M_RUNNING:
319 if (action == BZ_RUN) { 315 if (action == BZ_RUN) {
320 progress = handle_compress(strm); 316 /*progress =*/ handle_compress(strm);
321 return progress ? BZ_RUN_OK : BZ_PARAM_ERROR; 317 /*return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;*/
318 return BZ_RUN_OK;
322 } 319 }
320#ifdef FLUSH_IS_UNUSED
323 else 321 else
324 if (action == BZ_FLUSH) { 322 if (action == BZ_FLUSH) {
325 s->avail_in_expect = strm->avail_in; 323 //#s->avail_in_expect = strm->avail_in;
326 s->mode = BZ_M_FLUSHING; 324 s->mode = BZ_M_FLUSHING;
327 goto preswitch; 325 goto case_BZ_M_FLUSHING;
328 } 326 }
327#endif
329 else 328 else
330 if (action == BZ_FINISH) { 329 /*if (action == BZ_FINISH)*/ {
331 s->avail_in_expect = strm->avail_in; 330 //#s->avail_in_expect = strm->avail_in;
332 s->mode = BZ_M_FINISHING; 331 s->mode = BZ_M_FINISHING;
333 goto preswitch; 332 goto case_BZ_M_FINISHING;
334 } 333 }
335 else
336 return BZ_PARAM_ERROR;
337 334
335#ifdef FLUSH_IS_UNUSED
336case_BZ_M_FLUSHING:
338 case BZ_M_FLUSHING: 337 case BZ_M_FLUSHING:
339 if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR; 338 /*if (s->avail_in_expect != s->strm->avail_in)
340 if (s->avail_in_expect != s->strm->avail_in) 339 return BZ_SEQUENCE_ERROR;*/
341 return BZ_SEQUENCE_ERROR; 340 /*progress =*/ handle_compress(strm);
342 progress = handle_compress(strm);
343 if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ) 341 if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
344 return BZ_FLUSH_OK; 342 return BZ_FLUSH_OK;
345 s->mode = BZ_M_RUNNING; 343 s->mode = BZ_M_RUNNING;
346 return BZ_RUN_OK; 344 return BZ_RUN_OK;
345#endif
347 346
348 case BZ_M_FINISHING: 347 case_BZ_M_FINISHING:
349 if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR; 348 /*case BZ_M_FINISHING:*/
350 if (s->avail_in_expect != s->strm->avail_in) 349 default:
351 return BZ_SEQUENCE_ERROR; 350 /*if (s->avail_in_expect != s->strm->avail_in)
352 progress = handle_compress(strm); 351 return BZ_SEQUENCE_ERROR;*/
353 if (!progress) return BZ_SEQUENCE_ERROR; 352 /*progress =*/ handle_compress(strm);
354 if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ) 353 /*if (!progress) return BZ_SEQUENCE_ERROR;*/
354 //#if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
355 //# return BZ_FINISH_OK;
356 if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
355 return BZ_FINISH_OK; 357 return BZ_FINISH_OK;
356 s->mode = BZ_M_IDLE; 358 /*s->mode = BZ_M_IDLE;*/
357 return BZ_STREAM_END; 359 return BZ_STREAM_END;
358 } 360 }
359 return BZ_OK; /*--not reached--*/ 361 /* return BZ_OK; --not reached--*/
360} 362}
361 363
362 364
363/*---------------------------------------------------*/ 365/*---------------------------------------------------*/
364static 366static
365int BZ2_bzCompressEnd(bz_stream *strm) 367void BZ2_bzCompressEnd(bz_stream *strm)
366{ 368{
367 EState* s; 369 EState* s;
368 if (strm == NULL) return BZ_PARAM_ERROR;
369 s = strm->state;
370 if (s == NULL) return BZ_PARAM_ERROR;
371 if (s->strm != strm) return BZ_PARAM_ERROR;
372 370
373 if (s->arr1 != NULL) free(s->arr1); 371 s = strm->state;
374 if (s->arr2 != NULL) free(s->arr2); 372 free(s->arr1);
375 if (s->ftab != NULL) free(s->ftab); 373 free(s->arr2);
374 free(s->ftab);
375 free(s->crc32table);
376 free(strm->state); 376 free(strm->state);
377
378 strm->state = NULL;
379
380 return BZ_OK;
381} 377}
382 378
383 379
@@ -418,11 +414,11 @@ int BZ2_bzBuffToBuffCompress(char* dest,
418 BZ2_bzCompressEnd(&strm); 414 BZ2_bzCompressEnd(&strm);
419 return BZ_OK; 415 return BZ_OK;
420 416
421 output_overflow: 417 output_overflow:
422 BZ2_bzCompressEnd(&strm); 418 BZ2_bzCompressEnd(&strm);
423 return BZ_OUTBUFF_FULL; 419 return BZ_OUTBUFF_FULL;
424 420
425 errhandler: 421 errhandler:
426 BZ2_bzCompressEnd(&strm); 422 BZ2_bzCompressEnd(&strm);
427 return ret; 423 return ret;
428} 424}
diff --git a/archival/bz/bzlib.h b/archival/bz/bzlib.h
index 805e9b328..602aab926 100644
--- a/archival/bz/bzlib.h
+++ b/archival/bz/bzlib.h
@@ -56,7 +56,7 @@ typedef struct bz_stream {
56 56
57static void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k); 57static void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k);
58static int BZ2_bzCompress(bz_stream *strm, int action); 58static int BZ2_bzCompress(bz_stream *strm, int action);
59static int BZ2_bzCompressEnd(bz_stream *strm); 59static void BZ2_bzCompressEnd(bz_stream *strm);
60 60
61/*-------------------------------------------------------------*/ 61/*-------------------------------------------------------------*/
62/*--- end bzlib.h ---*/ 62/*--- end bzlib.h ---*/
diff --git a/archival/bz/bzlib_private.h b/archival/bz/bzlib_private.h
index 24ffbee9c..02f177eb2 100644
--- a/archival/bz/bzlib_private.h
+++ b/archival/bz/bzlib_private.h
@@ -25,31 +25,30 @@ in the file LICENSE.
25 25
26/* #include "bzlib.h" */ 26/* #include "bzlib.h" */
27 27
28#define BZ_DEBUG 0
29//#define BZ_NO_STDIO 1 - does not work
30
31
32/*-- General stuff. --*/ 28/*-- General stuff. --*/
33 29
34typedef unsigned char Bool; 30typedef unsigned char Bool;
35typedef unsigned char UChar;
36 31
37#define True ((Bool)1) 32#define True ((Bool)1)
38#define False ((Bool)0) 33#define False ((Bool)0)
39 34
35#if BZ_LIGHT_DEBUG
40static void bz_assert_fail(int errcode) ATTRIBUTE_NORETURN; 36static void bz_assert_fail(int errcode) ATTRIBUTE_NORETURN;
41#define AssertH(cond, errcode) \ 37#define AssertH(cond, errcode) \
42{ \ 38do { \
43 if (!(cond)) \ 39 if (!(cond)) \
44 bz_assert_fail(errcode); \ 40 bz_assert_fail(errcode); \
45} 41} while (0)
42#else
43#define AssertH(cond, msg) do { } while (0)
44#endif
46 45
47#if BZ_DEBUG 46#if BZ_DEBUG
48#define AssertD(cond, msg) \ 47#define AssertD(cond, msg) \
49{ \ 48do { \
50 if (!(cond)) \ 49 if (!(cond)) \
51 bb_error_msg_and_die("(debug build): internal error %s", msg); \ 50 bb_error_msg_and_die("(debug build): internal error %s", msg); \
52} 51} while (0)
53#else 52#else
54#define AssertD(cond, msg) do { } while (0) 53#define AssertD(cond, msg) do { } while (0)
55#endif 54#endif
@@ -79,35 +78,8 @@ static void bz_assert_fail(int errcode) ATTRIBUTE_NORETURN;
79#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) 78#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
80 79
81 80
82/*-- Stuff for randomising repetitive blocks. --*/
83
84static const int32_t BZ2_rNums[512];
85
86#define BZ_RAND_DECLS \
87 int32_t rNToGo; \
88 int32_t rTPos \
89
90#define BZ_RAND_INIT_MASK \
91 s->rNToGo = 0; \
92 s->rTPos = 0 \
93
94#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
95
96#define BZ_RAND_UPD_MASK \
97{ \
98 if (s->rNToGo == 0) { \
99 s->rNToGo = BZ2_rNums[s->rTPos]; \
100 s->rTPos++; \
101 if (s->rTPos == 512) s->rTPos = 0; \
102 } \
103 s->rNToGo--; \
104}
105
106
107/*-- Stuff for doing CRCs. --*/ 81/*-- Stuff for doing CRCs. --*/
108 82
109static const uint32_t BZ2_crc32Table[256];
110
111#define BZ_INITIALISE_CRC(crcVar) \ 83#define BZ_INITIALISE_CRC(crcVar) \
112{ \ 84{ \
113 crcVar = 0xffffffffL; \ 85 crcVar = 0xffffffffL; \
@@ -118,9 +90,9 @@ static const uint32_t BZ2_crc32Table[256];
118 crcVar = ~(crcVar); \ 90 crcVar = ~(crcVar); \
119} 91}
120 92
121#define BZ_UPDATE_CRC(crcVar,cha) \ 93#define BZ_UPDATE_CRC(s, crcVar, cha) \
122{ \ 94{ \
123 crcVar = (crcVar << 8) ^ BZ2_crc32Table[(crcVar >> 24) ^ ((UChar)cha)]; \ 95 crcVar = (crcVar << 8) ^ s->crc32table[(crcVar >> 24) ^ ((uint8_t)cha)]; \
124} 96}
125 97
126 98
@@ -152,24 +124,28 @@ typedef struct EState {
152 int32_t state; 124 int32_t state;
153 125
154 /* remembers avail_in when flush/finish requested */ 126 /* remembers avail_in when flush/finish requested */
155 uint32_t avail_in_expect; //vda: do we need this? 127/* bbox: not needed, strm->avail_in always has the same value */
128/* commented out with '//#' throughout the code */
129 /* uint32_t avail_in_expect; */
156 130
157 /* for doing the block sorting */ 131 /* for doing the block sorting */
132 int32_t origPtr;
158 uint32_t *arr1; 133 uint32_t *arr1;
159 uint32_t *arr2; 134 uint32_t *arr2;
160 uint32_t *ftab; 135 uint32_t *ftab;
161 int32_t origPtr;
162 136
163 /* aliases for arr1 and arr2 */ 137 /* aliases for arr1 and arr2 */
164 uint32_t *ptr; 138 uint32_t *ptr;
165 UChar *block; 139 uint8_t *block;
166 uint16_t *mtfv; 140 uint16_t *mtfv;
167 UChar *zbits; 141 uint8_t *zbits;
142
143 /* guess what */
144 uint32_t *crc32table;
168 145
169 /* run-length-encoding of the input */ 146 /* run-length-encoding of the input */
170 uint32_t state_in_ch; 147 uint32_t state_in_ch;
171 int32_t state_in_len; 148 int32_t state_in_len;
172 BZ_RAND_DECLS;
173 149
174 /* input and output limits and current posns */ 150 /* input and output limits and current posns */
175 int32_t nblock; 151 int32_t nblock;
@@ -194,18 +170,18 @@ typedef struct EState {
194 170
195 /* map of bytes used in block */ 171 /* map of bytes used in block */
196 int32_t nInUse; 172 int32_t nInUse;
197 Bool inUse[256]; 173 Bool inUse[256] __attribute__(( aligned(sizeof(long)) ));
198 UChar unseqToSeq[256]; 174 uint8_t unseqToSeq[256];
199 175
200 /* stuff for coding the MTF values */ 176 /* stuff for coding the MTF values */
201 int32_t mtfFreq [BZ_MAX_ALPHA_SIZE]; 177 int32_t mtfFreq [BZ_MAX_ALPHA_SIZE];
202 UChar selector [BZ_MAX_SELECTORS]; 178 uint8_t selector [BZ_MAX_SELECTORS];
203 UChar selectorMtf[BZ_MAX_SELECTORS]; 179 uint8_t selectorMtf[BZ_MAX_SELECTORS];
204 180
205 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 181 uint8_t len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
206 int32_t code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 182 int32_t code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
207 int32_t rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 183 int32_t rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
208#ifdef FAST_GROUP6 184#if CONFIG_BZIP2_FEATURE_SPEED >= 5
209 /* second dimension: only 3 needed; 4 makes index calculations faster */ 185 /* second dimension: only 3 needed; 4 makes index calculations faster */
210 uint32_t len_pack[BZ_MAX_ALPHA_SIZE][4]; 186 uint32_t len_pack[BZ_MAX_ALPHA_SIZE][4];
211#endif 187#endif
@@ -218,16 +194,16 @@ static void
218BZ2_blockSort(EState*); 194BZ2_blockSort(EState*);
219 195
220static void 196static void
221BZ2_compressBlock(EState*, Bool); 197BZ2_compressBlock(EState*, int);
222 198
223static void 199static void
224BZ2_bsInitWrite(EState*); 200BZ2_bsInitWrite(EState*);
225 201
226static void 202static void
227BZ2_hbAssignCodes(int32_t*, UChar*, int32_t, int32_t, int32_t); 203BZ2_hbAssignCodes(int32_t*, uint8_t*, int32_t, int32_t, int32_t);
228 204
229static void 205static void
230BZ2_hbMakeCodeLengths(UChar*, int32_t*, int32_t, int32_t); 206BZ2_hbMakeCodeLengths(uint8_t*, int32_t*, int32_t, int32_t);
231 207
232/*-------------------------------------------------------------*/ 208/*-------------------------------------------------------------*/
233/*--- end bzlib_private.h ---*/ 209/*--- end bzlib_private.h ---*/
diff --git a/archival/bz/compress.c b/archival/bz/compress.c
index 54426dcc7..4bd364ee3 100644
--- a/archival/bz/compress.c
+++ b/archival/bz/compress.c
@@ -50,7 +50,7 @@ static NOINLINE
50void bsFinishWrite(EState* s) 50void bsFinishWrite(EState* s)
51{ 51{
52 while (s->bsLive > 0) { 52 while (s->bsLive > 0) {
53 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24); 53 s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24);
54 s->numZ++; 54 s->numZ++;
55 s->bsBuff <<= 8; 55 s->bsBuff <<= 8;
56 s->bsLive -= 8; 56 s->bsLive -= 8;
@@ -60,13 +60,14 @@ void bsFinishWrite(EState* s)
60 60
61/*---------------------------------------------------*/ 61/*---------------------------------------------------*/
62static 62static
63/* Forced inlining results in +600 bytes code, 63/* Helps only on level 5, on other levels hurts. ? */
64 * 2% faster compression. Not worth it. */ 64#if CONFIG_BZIP2_FEATURE_SPEED >= 5
65/*ALWAYS_INLINE*/ 65ALWAYS_INLINE
66#endif
66void bsW(EState* s, int32_t n, uint32_t v) 67void bsW(EState* s, int32_t n, uint32_t v)
67{ 68{
68 while (s->bsLive >= 8) { 69 while (s->bsLive >= 8) {
69 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24); 70 s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24);
70 s->numZ++; 71 s->numZ++;
71 s->bsBuff <<= 8; 72 s->bsBuff <<= 8;
72 s->bsLive -= 8; 73 s->bsLive -= 8;
@@ -78,7 +79,7 @@ void bsW(EState* s, int32_t n, uint32_t v)
78 79
79/*---------------------------------------------------*/ 80/*---------------------------------------------------*/
80static 81static
81void bsPutU32(EState* s, uint32_t u) 82void bsPutU32(EState* s, unsigned u)
82{ 83{
83 bsW(s, 8, (u >> 24) & 0xff); 84 bsW(s, 8, (u >> 24) & 0xff);
84 bsW(s, 8, (u >> 16) & 0xff); 85 bsW(s, 8, (u >> 16) & 0xff);
@@ -89,9 +90,10 @@ void bsPutU32(EState* s, uint32_t u)
89 90
90/*---------------------------------------------------*/ 91/*---------------------------------------------------*/
91static 92static
92void bsPutUChar(EState* s, UChar c) 93void bsPutU16(EState* s, unsigned u)
93{ 94{
94 bsW(s, 8, (uint32_t)c); 95 bsW(s, 8, (u >> 8) & 0xff);
96 bsW(s, 8, u & 0xff);
95} 97}
96 98
97 99
@@ -103,7 +105,7 @@ void bsPutUChar(EState* s, UChar c)
103static 105static
104void makeMaps_e(EState* s) 106void makeMaps_e(EState* s)
105{ 107{
106 int32_t i; 108 int i;
107 s->nInUse = 0; 109 s->nInUse = 0;
108 for (i = 0; i < 256; i++) { 110 for (i = 0; i < 256; i++) {
109 if (s->inUse[i]) { 111 if (s->inUse[i]) {
@@ -118,7 +120,7 @@ void makeMaps_e(EState* s)
118static NOINLINE 120static NOINLINE
119void generateMTFValues(EState* s) 121void generateMTFValues(EState* s)
120{ 122{
121 UChar yy[256]; 123 uint8_t yy[256];
122 int32_t i, j; 124 int32_t i, j;
123 int32_t zPend; 125 int32_t zPend;
124 int32_t wr; 126 int32_t wr;
@@ -128,7 +130,7 @@ void generateMTFValues(EState* s)
128 * After sorting (eg, here), 130 * After sorting (eg, here),
129 * s->arr1[0 .. s->nblock-1] holds sorted order, 131 * s->arr1[0 .. s->nblock-1] holds sorted order,
130 * and 132 * and
131 * ((UChar*)s->arr2)[0 .. s->nblock-1] 133 * ((uint8_t*)s->arr2)[0 .. s->nblock-1]
132 * holds the original block data. 134 * holds the original block data.
133 * 135 *
134 * The first thing to do is generate the MTF values, 136 * The first thing to do is generate the MTF values,
@@ -140,14 +142,14 @@ void generateMTFValues(EState* s)
140 * 142 *
141 * The final compressed bitstream is generated into the 143 * The final compressed bitstream is generated into the
142 * area starting at 144 * area starting at
143 * (UChar*) (&((UChar*)s->arr2)[s->nblock]) 145 * &((uint8_t*)s->arr2)[s->nblock]
144 * 146 *
145 * These storage aliases are set up in bzCompressInit(), 147 * These storage aliases are set up in bzCompressInit(),
146 * except for the last one, which is arranged in 148 * except for the last one, which is arranged in
147 * compressBlock(). 149 * compressBlock().
148 */ 150 */
149 uint32_t* ptr = s->ptr; 151 uint32_t* ptr = s->ptr;
150 UChar* block = s->block; 152 uint8_t* block = s->block;
151 uint16_t* mtfv = s->mtfv; 153 uint16_t* mtfv = s->mtfv;
152 154
153 makeMaps_e(s); 155 makeMaps_e(s);
@@ -159,12 +161,12 @@ void generateMTFValues(EState* s)
159 wr = 0; 161 wr = 0;
160 zPend = 0; 162 zPend = 0;
161 for (i = 0; i < s->nInUse; i++) 163 for (i = 0; i < s->nInUse; i++)
162 yy[i] = (UChar) i; 164 yy[i] = (uint8_t) i;
163 165
164 for (i = 0; i < s->nblock; i++) { 166 for (i = 0; i < s->nblock; i++) {
165 UChar ll_i; 167 uint8_t ll_i;
166 AssertD(wr <= i, "generateMTFValues(1)"); 168 AssertD(wr <= i, "generateMTFValues(1)");
167 j = ptr[i]-1; 169 j = ptr[i] - 1;
168 if (j < 0) 170 if (j < 0)
169 j += s->nblock; 171 j += s->nblock;
170 ll_i = s->unseqToSeq[block[j]]; 172 ll_i = s->unseqToSeq[block[j]];
@@ -189,15 +191,15 @@ void generateMTFValues(EState* s)
189 zPend = 0; 191 zPend = 0;
190 } 192 }
191 { 193 {
192 register UChar rtmp; 194 register uint8_t rtmp;
193 register UChar* ryy_j; 195 register uint8_t* ryy_j;
194 register UChar rll_i; 196 register uint8_t rll_i;
195 rtmp = yy[1]; 197 rtmp = yy[1];
196 yy[1] = yy[0]; 198 yy[1] = yy[0];
197 ryy_j = &(yy[1]); 199 ryy_j = &(yy[1]);
198 rll_i = ll_i; 200 rll_i = ll_i;
199 while (rll_i != rtmp) { 201 while (rll_i != rtmp) {
200 register UChar rtmp2; 202 register uint8_t rtmp2;
201 ryy_j++; 203 ryy_j++;
202 rtmp2 = rtmp; 204 rtmp2 = rtmp;
203 rtmp = *ryy_j; 205 rtmp = *ryy_j;
@@ -250,7 +252,7 @@ void sendMTFValues(EState* s)
250 int32_t nGroups, nBytes; 252 int32_t nGroups, nBytes;
251 253
252 /* 254 /*
253 * UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 255 * uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
254 * is a global since the decoder also needs it. 256 * is a global since the decoder also needs it.
255 * 257 *
256 * int32_t code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 258 * int32_t code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
@@ -295,7 +297,7 @@ void sendMTFValues(EState* s)
295 297
296 if (ge > gs 298 if (ge > gs
297 && nPart != nGroups && nPart != 1 299 && nPart != nGroups && nPart != 1
298 && ((nGroups-nPart) % 2 == 1) 300 && ((nGroups - nPart) % 2 == 1)
299 ) { 301 ) {
300 aFreq -= s->mtfFreq[ge]; 302 aFreq -= s->mtfFreq[ge];
301 ge--; 303 ge--;
@@ -324,7 +326,7 @@ void sendMTFValues(EState* s)
324 for (v = 0; v < alphaSize; v++) 326 for (v = 0; v < alphaSize; v++)
325 s->rfreq[t][v] = 0; 327 s->rfreq[t][v] = 0;
326 328
327#ifdef FAST_GROUP6 329#if CONFIG_BZIP2_FEATURE_SPEED >= 5
328 /* 330 /*
329 * Set up an auxiliary length table which is used to fast-track 331 * Set up an auxiliary length table which is used to fast-track
330 * the common case (nGroups == 6). 332 * the common case (nGroups == 6).
@@ -337,7 +339,6 @@ void sendMTFValues(EState* s)
337 } 339 }
338 } 340 }
339#endif 341#endif
340
341 nSelectors = 0; 342 nSelectors = 0;
342 totc = 0; 343 totc = 0;
343 gs = 0; 344 gs = 0;
@@ -355,7 +356,7 @@ void sendMTFValues(EState* s)
355 */ 356 */
356 for (t = 0; t < nGroups; t++) 357 for (t = 0; t < nGroups; t++)
357 cost[t] = 0; 358 cost[t] = 0;
358#ifdef FAST_GROUP6 359#if CONFIG_BZIP2_FEATURE_SPEED >= 5
359 if (nGroups == 6 && 50 == ge-gs+1) { 360 if (nGroups == 6 && 50 == ge-gs+1) {
360 /*--- fast track the common case ---*/ 361 /*--- fast track the common case ---*/
361 register uint32_t cost01, cost23, cost45; 362 register uint32_t cost01, cost23, cost45;
@@ -395,11 +396,11 @@ void sendMTFValues(EState* s)
395 * Find the coding table which is best for this group, 396 * Find the coding table which is best for this group,
396 * and record its identity in the selector table. 397 * and record its identity in the selector table.
397 */ 398 */
398 bc = 999999999; 399 /*bc = 999999999;*/
399 bt = -1; 400 /*bt = -1;*/
400 //bc = cost[0]; 401 bc = cost[0];
401 //bt = 0; 402 bt = 0;
402 for (t = 0; t < nGroups; t++) { 403 for (t = 1 /*0*/; t < nGroups; t++) {
403 if (cost[t] < bc) { 404 if (cost[t] < bc) {
404 bc = cost[t]; 405 bc = cost[t];
405 bt = t; 406 bt = t;
@@ -413,8 +414,8 @@ void sendMTFValues(EState* s)
413 /* 414 /*
414 * Increment the symbol frequencies for the selected table. 415 * Increment the symbol frequencies for the selected table.
415 */ 416 */
416/* ~0.5% faster compress. +800 bytes */ 417/* 1% faster compress. +800 bytes */
417#if 0 418#if CONFIG_BZIP2_FEATURE_SPEED >= 4
418 if (nGroups == 6 && 50 == ge-gs+1) { 419 if (nGroups == 6 && 50 == ge-gs+1) {
419 /*--- fast track the common case ---*/ 420 /*--- fast track the common case ---*/
420#define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++ 421#define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
@@ -429,7 +430,7 @@ void sendMTFValues(EState* s)
429 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); 430 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
430 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); 431 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
431#undef BZ_ITUR 432#undef BZ_ITUR
432 gs = ge+1; 433 gs = ge + 1;
433 } else 434 } else
434#endif 435#endif
435 { 436 {
@@ -438,7 +439,7 @@ void sendMTFValues(EState* s)
438 s->rfreq[bt][mtfv[gs]]++; 439 s->rfreq[bt][mtfv[gs]]++;
439 gs++; 440 gs++;
440 } 441 }
441 /* already is: gs = ge+1; */ 442 /* already is: gs = ge + 1; */
442 } 443 }
443 } 444 }
444 445
@@ -456,7 +457,7 @@ void sendMTFValues(EState* s)
456 457
457 /*--- Compute MTF values for the selectors. ---*/ 458 /*--- Compute MTF values for the selectors. ---*/
458 { 459 {
459 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; 460 uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
460 461
461 for (i = 0; i < nGroups; i++) 462 for (i = 0; i < nGroups; i++)
462 pos[i] = i; 463 pos[i] = i;
@@ -490,31 +491,34 @@ void sendMTFValues(EState* s)
490 491
491 /*--- Transmit the mapping table. ---*/ 492 /*--- Transmit the mapping table. ---*/
492 { 493 {
493 Bool inUse16[16]; 494 /* bbox: optimized a bit more than in bzip2 */
495 int inUse16 = 0;
494 for (i = 0; i < 16; i++) { 496 for (i = 0; i < 16; i++) {
495 inUse16[i] = False; 497 if (sizeof(long) <= 4) {
496 for (j = 0; j < 16; j++) 498 inUse16 = inUse16*2 +
497 if (s->inUse[i * 16 + j]) 499 ((*(uint32_t*)&(s->inUse[i * 16 + 0])
498 inUse16[i] = True; 500 | *(uint32_t*)&(s->inUse[i * 16 + 4])
501 | *(uint32_t*)&(s->inUse[i * 16 + 8])
502 | *(uint32_t*)&(s->inUse[i * 16 + 12])) != 0);
503 } else { /* Our CPU can do better */
504 inUse16 = inUse16*2 +
505 ((*(uint64_t*)&(s->inUse[i * 16 + 0])
506 | *(uint64_t*)&(s->inUse[i * 16 + 8])) != 0);
507 }
499 } 508 }
500 509
501 nBytes = s->numZ; 510 nBytes = s->numZ;
502 for (i = 0; i < 16; i++) { 511 bsW(s, 16, inUse16);
503 if (inUse16[i])
504 bsW(s, 1, 1);
505 else
506 bsW(s, 1, 0);
507 }
508 512
513 inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */
509 for (i = 0; i < 16; i++) { 514 for (i = 0; i < 16; i++) {
510 if (inUse16[i]) { 515 if (inUse16 < 0) {
511 for (j = 0; j < 16; j++) { 516 unsigned v16 = 0;
512 if (s->inUse[i * 16 + j]) 517 for (j = 0; j < 16; j++)
513 bsW(s, 1, 1); 518 v16 = v16*2 + s->inUse[i * 16 + j];
514 else 519 bsW(s, 16, v16);
515 bsW(s, 1, 0);
516 }
517 } 520 }
521 inUse16 <<= 1;
518 } 522 }
519 } 523 }
520 524
@@ -558,7 +562,7 @@ void sendMTFValues(EState* s)
558 if (nGroups == 6 && 50 == ge-gs+1) { 562 if (nGroups == 6 && 50 == ge-gs+1) {
559 /*--- fast track the common case ---*/ 563 /*--- fast track the common case ---*/
560 uint16_t mtfv_i; 564 uint16_t mtfv_i;
561 UChar* s_len_sel_selCtr = &(s->len[s->selector[selCtr]][0]); 565 uint8_t* s_len_sel_selCtr = &(s->len[s->selector[selCtr]][0]);
562 int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]); 566 int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
563#define BZ_ITAH(nn) \ 567#define BZ_ITAH(nn) \
564 mtfv_i = mtfv[gs+(nn)]; \ 568 mtfv_i = mtfv[gs+(nn)]; \
@@ -580,7 +584,7 @@ void sendMTFValues(EState* s)
580 { 584 {
581 /*--- slow version which correctly handles all situations ---*/ 585 /*--- slow version which correctly handles all situations ---*/
582 /* code is bit bigger, but moves multiply out of the loop */ 586 /* code is bit bigger, but moves multiply out of the loop */
583 UChar* s_len_sel_selCtr = &(s->len [s->selector[selCtr]][0]); 587 uint8_t* s_len_sel_selCtr = &(s->len [s->selector[selCtr]][0]);
584 int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]); 588 int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
585 while (gs <= ge) { 589 while (gs <= ge) {
586 bsW(s, 590 bsW(s,
@@ -599,7 +603,7 @@ void sendMTFValues(EState* s)
599 603
600/*---------------------------------------------------*/ 604/*---------------------------------------------------*/
601static 605static
602void BZ2_compressBlock(EState* s, Bool is_last_block) 606void BZ2_compressBlock(EState* s, int is_last_block)
603{ 607{
604 if (s->nblock > 0) { 608 if (s->nblock > 0) {
605 BZ_FINALISE_CRC(s->blockCRC); 609 BZ_FINALISE_CRC(s->blockCRC);
@@ -611,26 +615,27 @@ void BZ2_compressBlock(EState* s, Bool is_last_block)
611 BZ2_blockSort(s); 615 BZ2_blockSort(s);
612 } 616 }
613 617
614 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]); 618 s->zbits = &((uint8_t*)s->arr2)[s->nblock];
615 619
616 /*-- If this is the first block, create the stream header. --*/ 620 /*-- If this is the first block, create the stream header. --*/
617 if (s->blockNo == 1) { 621 if (s->blockNo == 1) {
618 BZ2_bsInitWrite(s); 622 BZ2_bsInitWrite(s);
619 /*bsPutUChar(s, BZ_HDR_B);*/ 623 /*bsPutU8(s, BZ_HDR_B);*/
620 /*bsPutUChar(s, BZ_HDR_Z);*/ 624 /*bsPutU8(s, BZ_HDR_Z);*/
621 /*bsPutUChar(s, BZ_HDR_h);*/ 625 /*bsPutU8(s, BZ_HDR_h);*/
622 /*bsPutUChar(s, (UChar)(BZ_HDR_0 + s->blockSize100k));*/ 626 /*bsPutU8(s, BZ_HDR_0 + s->blockSize100k);*/
623 bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k); 627 bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k);
624 } 628 }
625 629
626 if (s->nblock > 0) { 630 if (s->nblock > 0) {
627 /*bsPutUChar(s, 0x31);*/ 631 /*bsPutU8(s, 0x31);*/
628 /*bsPutUChar(s, 0x41);*/ 632 /*bsPutU8(s, 0x41);*/
629 /*bsPutUChar(s, 0x59);*/ 633 /*bsPutU8(s, 0x59);*/
630 /*bsPutUChar(s, 0x26);*/ 634 /*bsPutU8(s, 0x26);*/
631 bsPutU32(s, 0x31415926); 635 bsPutU32(s, 0x31415926);
632 bsPutUChar(s, 0x53); 636 /*bsPutU8(s, 0x53);*/
633 bsPutUChar(s, 0x59); 637 /*bsPutU8(s, 0x59);*/
638 bsPutU16(s, 0x5359);
634 639
635 /*-- Now the block's CRC, so it is in a known place. --*/ 640 /*-- Now the block's CRC, so it is in a known place. --*/
636 bsPutU32(s, s->blockCRC); 641 bsPutU32(s, s->blockCRC);
@@ -653,13 +658,14 @@ void BZ2_compressBlock(EState* s, Bool is_last_block)
653 658
654 /*-- If this is the last block, add the stream trailer. --*/ 659 /*-- If this is the last block, add the stream trailer. --*/
655 if (is_last_block) { 660 if (is_last_block) {
656 /*bsPutUChar(s, 0x17);*/ 661 /*bsPutU8(s, 0x17);*/
657 /*bsPutUChar(s, 0x72);*/ 662 /*bsPutU8(s, 0x72);*/
658 /*bsPutUChar(s, 0x45);*/ 663 /*bsPutU8(s, 0x45);*/
659 /*bsPutUChar(s, 0x38);*/ 664 /*bsPutU8(s, 0x38);*/
660 bsPutU32(s, 0x17724538); 665 bsPutU32(s, 0x17724538);
661 bsPutUChar(s, 0x50); 666 /*bsPutU8(s, 0x50);*/
662 bsPutUChar(s, 0x90); 667 /*bsPutU8(s, 0x90);*/
668 bsPutU16(s, 0x5090);
663 bsPutU32(s, s->combinedCRC); 669 bsPutU32(s, s->combinedCRC);
664 bsFinishWrite(s); 670 bsFinishWrite(s);
665 } 671 }
diff --git a/archival/bz/huffman.c b/archival/bz/huffman.c
index d01af11c2..89e54604b 100644
--- a/archival/bz/huffman.c
+++ b/archival/bz/huffman.c
@@ -68,7 +68,7 @@ in the file LICENSE.
68 68
69/*---------------------------------------------------*/ 69/*---------------------------------------------------*/
70static 70static
71void BZ2_hbMakeCodeLengths(UChar *len, 71void BZ2_hbMakeCodeLengths(uint8_t *len,
72 int32_t *freq, 72 int32_t *freq,
73 int32_t alphaSize, 73 int32_t alphaSize,
74 int32_t maxLen) 74 int32_t maxLen)
@@ -163,7 +163,7 @@ void BZ2_hbMakeCodeLengths(UChar *len,
163/*---------------------------------------------------*/ 163/*---------------------------------------------------*/
164static 164static
165void BZ2_hbAssignCodes(int32_t *code, 165void BZ2_hbAssignCodes(int32_t *code,
166 UChar *length, 166 uint8_t *length,
167 int32_t minLen, 167 int32_t minLen,
168 int32_t maxLen, 168 int32_t maxLen,
169 int32_t alphaSize) 169 int32_t alphaSize)
diff --git a/archival/bzip2.c b/archival/bzip2.c
index 04478eecc..bb1610eb4 100644
--- a/archival/bzip2.c
+++ b/archival/bzip2.c
@@ -9,8 +9,28 @@
9 9
10#include "libbb.h" 10#include "libbb.h"
11 11
12/* This buys 6% speed for nearly 4k code */ 12#define CONFIG_BZIP2_FEATURE_SPEED 1
13/*#define FAST_GROUP6 1*/ 13
14/* Speed test:
15 * Compiled with gcc 4.2.1, run on Athlon 64 1800 MHz (512K L2 cache).
16 * Stock bzip2 is 26.4% slower than bbox bzip2 at SPEED 1
17 * (time to compress gcc-4.2.1.tar is 126.4% compared to bbox).
18 * At SPEED 5 difference is 32.7%.
19 *
20 * Test run of all CONFIG_BZIP2_FEATURE_SPEED values on a 11Mb text file:
21 * Size Time (3 runs)
22 * 0: 10828 4.145 4.146 4.148
23 * 1: 11097 3.845 3.860 3.861
24 * 2: 11392 3.763 3.767 3.768
25 * 3: 11892 3.722 3.724 3.727
26 * 4: 12740 3.637 3.640 3.644
27 * 5: 17273 3.497 3.509 3.509
28 */
29
30
31#define BZ_DEBUG 0
32/* Takes ~300 bytes, detects corruption caused by bad RAM etc */
33#define BZ_LIGHT_DEBUG 0
14 34
15#include "bz/bzlib.h" 35#include "bz/bzlib.h"
16 36
@@ -19,9 +39,7 @@
19#include "bz/blocksort.c" 39#include "bz/blocksort.c"
20#include "bz/bzlib.c" 40#include "bz/bzlib.c"
21#include "bz/compress.c" 41#include "bz/compress.c"
22#include "bz/crctable.c"
23#include "bz/huffman.c" 42#include "bz/huffman.c"
24#include "bz/randtable.c"
25 43
26/* No point in being shy and having very small buffer here. 44/* No point in being shy and having very small buffer here.
27 * bzip2 internal buffers are much bigger anyway, hundreds of kbytes. 45 * bzip2 internal buffers are much bigger anyway, hundreds of kbytes.
@@ -36,7 +54,7 @@ enum {
36/* Returns: 54/* Returns:
37 * <0 on write errors (examine errno), 55 * <0 on write errors (examine errno),
38 * >0 on short writes (errno == 0) 56 * >0 on short writes (errno == 0)
39 * 0 no error (entire input consume, gimme more) 57 * 0 no error (entire input consumed, gimme more)
40 * on "impossible" errors (internal bzip2 compressor bug) dies 58 * on "impossible" errors (internal bzip2 compressor bug) dies
41 */ 59 */
42static 60static
@@ -44,8 +62,6 @@ ssize_t bz_write(bz_stream *strm, void* rbuf, ssize_t rlen, void *wbuf)
44{ 62{
45 int n, n2, ret; 63 int n, n2, ret;
46 64
47 /* if (len == 0) return 0; */
48
49 strm->avail_in = rlen; 65 strm->avail_in = rlen;
50 strm->next_in = rbuf; 66 strm->next_in = rbuf;
51 while (1) { 67 while (1) {
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 15:24:53 +0000