aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--archival/libarchive/bz/blocksort.c124
-rw-r--r--archival/libarchive/bz/bzlib.c2
-rw-r--r--archival/libarchive/bz/bzlib_private.h6
3 files changed, 65 insertions, 67 deletions
diff --git a/archival/libarchive/bz/blocksort.c b/archival/libarchive/bz/blocksort.c
index 578f6d41f..effaa152a 100644
--- a/archival/libarchive/bz/blocksort.c
+++ b/archival/libarchive/bz/blocksort.c
@@ -227,17 +227,19 @@ void fallbackQSort3(uint32_t* fmap,
227#define UNALIGNED_BH(zz) ((zz) & 0x01f) 227#define UNALIGNED_BH(zz) ((zz) & 0x01f)
228 228
229static 229static
230void fallbackSort(uint32_t* fmap, 230void fallbackSort(EState* state)
231 uint32_t* eclass,
232 uint32_t* bhtab,
233 int32_t nblock)
234{ 231{
235 int32_t ftab[257]; 232 int32_t ftab[257];
236 int32_t ftabCopy[256]; 233 int32_t ftabCopy[256];
237 int32_t H, i, j, k, l, r, cc, cc1; 234 int32_t H, i, j, k, l, r, cc, cc1;
238 int32_t nNotDone; 235 int32_t nNotDone;
239 int32_t nBhtab; 236 int32_t nBhtab;
240 uint8_t* eclass8 = (uint8_t*)eclass; 237 /* params */
238 uint32_t *const fmap = state->arr1;
239 uint32_t *const eclass = state->arr2;
240#define eclass8 ((uint8_t*)eclass)
241 uint32_t *const bhtab = state->ftab;
242 const int32_t nblock = state->nblock;
241 243
242 /* 244 /*
243 * Initial 1-char radix sort to generate 245 * Initial 1-char radix sort to generate
@@ -349,6 +351,7 @@ void fallbackSort(uint32_t* fmap,
349 eclass8[fmap[i]] = (uint8_t)j; 351 eclass8[fmap[i]] = (uint8_t)j;
350 } 352 }
351 AssertH(j < 256, 1005); 353 AssertH(j < 256, 1005);
354#undef eclass8
352} 355}
353 356
354#undef SET_BH 357#undef SET_BH
@@ -367,18 +370,18 @@ void fallbackSort(uint32_t* fmap,
367/*---------------------------------------------*/ 370/*---------------------------------------------*/
368static 371static
369NOINLINE 372NOINLINE
370int mainGtU( 373int mainGtU(EState* state,
371 uint32_t i1, 374 uint32_t i1,
372 uint32_t i2, 375 uint32_t i2)
373 uint8_t* block,
374 uint16_t* quadrant,
375 uint32_t nblock,
376 int32_t* budget)
377{ 376{
378 int32_t k; 377 int32_t k;
379 uint8_t c1, c2; 378 uint8_t c1, c2;
380 uint16_t s1, s2; 379 uint16_t s1, s2;
381 380
381 uint8_t *const block = state->block;
382 uint16_t *const quadrant = state->quadrant;
383 const int32_t nblock = state->nblock;
384
382/* Loop unrolling here is actually very useful 385/* Loop unrolling here is actually very useful
383 * (generated code is much simpler), 386 * (generated code is much simpler),
384 * code size increase is only 270 bytes (i386) 387 * code size increase is only 270 bytes (i386)
@@ -435,7 +438,7 @@ int mainGtU(
435 if (i1 >= nblock) i1 -= nblock; 438 if (i1 >= nblock) i1 -= nblock;
436 if (i2 >= nblock) i2 -= nblock; 439 if (i2 >= nblock) i2 -= nblock;
437 440
438 (*budget)--; 441 state->budget--;
439 k -= 8; 442 k -= 8;
440 } while (k >= 0); 443 } while (k >= 0);
441 444
@@ -459,15 +462,13 @@ const uint32_t incs[14] = {
459}; 462};
460 463
461static 464static
462void mainSimpleSort(uint32_t* ptr, 465void mainSimpleSort(EState* state,
463 uint8_t* block,
464 uint16_t* quadrant,
465 int32_t nblock,
466 int32_t lo, 466 int32_t lo,
467 int32_t hi, 467 int32_t hi,
468 int32_t d, 468 int32_t d)
469 int32_t* budget)
470{ 469{
470 uint32_t *const ptr = state->ptr;
471
471 /* At which increment to start? */ 472 /* At which increment to start? */
472 int hp = 0; 473 int hp = 0;
473 { 474 {
@@ -492,7 +493,7 @@ void mainSimpleSort(uint32_t* ptr,
492 if (i > hi) break; 493 if (i > hi) break;
493 v = ptr[i]; 494 v = ptr[i];
494 j = i; 495 j = i;
495 while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { 496 while (mainGtU(state, ptr[j-h]+d, v+d)) {
496 ptr[j] = ptr[j-h]; 497 ptr[j] = ptr[j-h];
497 j = j - h; 498 j = j - h;
498 if (j <= (lo + h - 1)) break; 499 if (j <= (lo + h - 1)) break;
@@ -506,7 +507,7 @@ void mainSimpleSort(uint32_t* ptr,
506 if (i > hi) break; 507 if (i > hi) break;
507 v = ptr[i]; 508 v = ptr[i];
508 j = i; 509 j = i;
509 while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { 510 while (mainGtU(state, ptr[j-h]+d, v+d)) {
510 ptr[j] = ptr[j-h]; 511 ptr[j] = ptr[j-h];
511 j = j - h; 512 j = j - h;
512 if (j <= (lo + h - 1)) break; 513 if (j <= (lo + h - 1)) break;
@@ -517,7 +518,7 @@ void mainSimpleSort(uint32_t* ptr,
517 if (i > hi) break; 518 if (i > hi) break;
518 v = ptr[i]; 519 v = ptr[i];
519 j = i; 520 j = i;
520 while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { 521 while (mainGtU(state, ptr[j-h]+d, v+d)) {
521 ptr[j] = ptr[j-h]; 522 ptr[j] = ptr[j-h];
522 j = j - h; 523 j = j - h;
523 if (j <= (lo + h - 1)) break; 524 if (j <= (lo + h - 1)) break;
@@ -525,7 +526,7 @@ void mainSimpleSort(uint32_t* ptr,
525 ptr[j] = v; 526 ptr[j] = v;
526 i++; 527 i++;
527#endif 528#endif
528 if (*budget < 0) return; 529 if (state->budget < 0) return;
529 } 530 }
530 } 531 }
531} 532}
@@ -590,14 +591,10 @@ uint8_t mmed3(uint8_t a, uint8_t b, uint8_t c)
590#define MAIN_QSORT_STACK_SIZE 100 591#define MAIN_QSORT_STACK_SIZE 100
591 592
592static NOINLINE 593static NOINLINE
593void mainQSort3(uint32_t* ptr, 594void mainQSort3(EState* state,
594 uint8_t* block,
595 uint16_t* quadrant,
596 int32_t nblock,
597 int32_t loSt, 595 int32_t loSt,
598 int32_t hiSt, 596 int32_t hiSt
599 /*int32_t dSt,*/ 597 /*int32_t dSt*/)
600 int32_t* budget)
601{ 598{
602 enum { dSt = BZ_N_RADIX }; 599 enum { dSt = BZ_N_RADIX };
603 int32_t unLo, unHi, ltLo, gtHi, n, m, med; 600 int32_t unLo, unHi, ltLo, gtHi, n, m, med;
@@ -611,6 +608,9 @@ void mainQSort3(uint32_t* ptr,
611 int32_t nextHi[3]; 608 int32_t nextHi[3];
612 int32_t nextD [3]; 609 int32_t nextD [3];
613 610
611 uint32_t *const ptr = state->ptr;
612 uint8_t *const block = state->block;
613
614 sp = 0; 614 sp = 0;
615 mpush(loSt, hiSt, dSt); 615 mpush(loSt, hiSt, dSt);
616 616
@@ -621,8 +621,8 @@ void mainQSort3(uint32_t* ptr,
621 if (hi - lo < MAIN_QSORT_SMALL_THRESH 621 if (hi - lo < MAIN_QSORT_SMALL_THRESH
622 || d > MAIN_QSORT_DEPTH_THRESH 622 || d > MAIN_QSORT_DEPTH_THRESH
623 ) { 623 ) {
624 mainSimpleSort(ptr, block, quadrant, nblock, lo, hi, d, budget); 624 mainSimpleSort(state, lo, hi, d);
625 if (*budget < 0) 625 if (state->budget < 0)
626 return; 626 return;
627 continue; 627 continue;
628 } 628 }
@@ -726,13 +726,7 @@ void mainQSort3(uint32_t* ptr,
726#define CLEARMASK (~(SETMASK)) 726#define CLEARMASK (~(SETMASK))
727 727
728static NOINLINE 728static NOINLINE
729void mainSort(EState* state, 729void mainSort(EState* state)
730 uint32_t* ptr,
731 uint8_t* block,
732 uint16_t* quadrant,
733 uint32_t* ftab,
734 int32_t nblock,
735 int32_t* budget)
736{ 730{
737 int32_t i, j; 731 int32_t i, j;
738 Bool bigDone[256]; 732 Bool bigDone[256];
@@ -745,6 +739,12 @@ void mainSort(EState* state,
745#define copyStart (state->mainSort__copyStart) 739#define copyStart (state->mainSort__copyStart)
746#define copyEnd (state->mainSort__copyEnd) 740#define copyEnd (state->mainSort__copyEnd)
747 741
742 uint32_t *const ptr = state->ptr;
743 uint8_t *const block = state->block;
744 uint32_t *const ftab = state->ftab;
745 const int32_t nblock = state->nblock;
746 uint16_t *const quadrant = state->quadrant;
747
748 /*-- set up the 2-byte frequency table --*/ 748 /*-- set up the 2-byte frequency table --*/
749 /* was: for (i = 65536; i >= 0; i--) ftab[i] = 0; */ 749 /* was: for (i = 65536; i >= 0; i--) ftab[i] = 0; */
750 memset(ftab, 0, 65537 * sizeof(ftab[0])); 750 memset(ftab, 0, 65537 * sizeof(ftab[0]));
@@ -883,11 +883,8 @@ void mainSort(EState* state,
883 int32_t lo = ftab[sb] /*& CLEARMASK (redundant)*/; 883 int32_t lo = ftab[sb] /*& CLEARMASK (redundant)*/;
884 int32_t hi = (ftab[sb+1] & CLEARMASK) - 1; 884 int32_t hi = (ftab[sb+1] & CLEARMASK) - 1;
885 if (hi > lo) { 885 if (hi > lo) {
886 mainQSort3( 886 mainQSort3(state, lo, hi /*,BZ_N_RADIX*/);
887 ptr, block, quadrant, nblock, 887 if (state->budget < 0) return;
888 lo, hi, /*BZ_N_RADIX,*/ budget
889 );
890 if (*budget < 0) return;
891 } 888 }
892 } 889 }
893 ftab[sb] |= SETMASK; 890 ftab[sb] |= SETMASK;
@@ -1025,31 +1022,25 @@ void mainSort(EState* state,
1025 * arr1[0 .. nblock-1] holds sorted order 1022 * arr1[0 .. nblock-1] holds sorted order
1026 */ 1023 */
1027static NOINLINE 1024static NOINLINE
1028void BZ2_blockSort(EState* s) 1025void BZ2_blockSort(EState* state)
1029{ 1026{
1030 /* In original bzip2 1.0.4, it's a parameter, but 30 1027 /* In original bzip2 1.0.4, it's a parameter, but 30
1031 * (which was the default) should work ok. */ 1028 * (which was the default) should work ok. */
1032 enum { wfact = 30 }; 1029 enum { wfact = 30 };
1030 unsigned i;
1033 1031
1034 uint32_t* ptr = s->ptr; 1032 if (state->nblock < 10000) {
1035 uint8_t* block = s->block; 1033 fallbackSort(state);
1036 uint32_t* ftab = s->ftab;
1037 int32_t nblock = s->nblock;
1038 uint16_t* quadrant;
1039 int32_t budget;
1040 int32_t i;
1041
1042 if (nblock < 10000) {
1043 fallbackSort(s->arr1, s->arr2, ftab, nblock);
1044 } else { 1034 } else {
1045 /* Calculate the location for quadrant, remembering to get 1035 /* Calculate the location for quadrant, remembering to get
1046 * the alignment right. Assumes that &(block[0]) is at least 1036 * the alignment right. Assumes that &(block[0]) is at least
1047 * 2-byte aligned -- this should be ok since block is really 1037 * 2-byte aligned -- this should be ok since block is really
1048 * the first section of arr2. 1038 * the first section of arr2.
1049 */ 1039 */
1050 i = nblock + BZ_N_OVERSHOOT; 1040 i = state->nblock + BZ_N_OVERSHOOT;
1051 if (i & 1) i++; 1041 if (i & 1)
1052 quadrant = (uint16_t*)(&(block[i])); 1042 i++;
1043 state->quadrant = (uint16_t*) &(state->block[i]);
1053 1044
1054 /* (wfact-1) / 3 puts the default-factor-30 1045 /* (wfact-1) / 3 puts the default-factor-30
1055 * transition point at very roughly the same place as 1046 * transition point at very roughly the same place as
@@ -1058,24 +1049,25 @@ void BZ2_blockSort(EState* s)
1058 * resulting compressed stream is now the same regardless 1049 * resulting compressed stream is now the same regardless
1059 * of whether or not we use the main sort or fallback sort. 1050 * of whether or not we use the main sort or fallback sort.
1060 */ 1051 */
1061 budget = nblock * ((wfact-1) / 3); 1052 state->budget = state->nblock * ((wfact-1) / 3);
1062 1053
1063 mainSort(s, ptr, block, quadrant, ftab, nblock, &budget); 1054 mainSort(state);
1064 if (budget < 0) { 1055 if (state->budget < 0) {
1065 fallbackSort(s->arr1, s->arr2, ftab, nblock); 1056 fallbackSort(state);
1066 } 1057 }
1067 } 1058 }
1068 1059
1069#if BZ_LIGHT_DEBUG 1060#if BZ_LIGHT_DEBUG
1070 s->origPtr = -1; 1061 state->origPtr = -1;
1071#endif 1062#endif
1072 for (i = 0; i < s->nblock; i++) 1063 for (i = 0; i < state->nblock; i++) {
1073 if (ptr[i] == 0) { 1064 if (state->ptr[i] == 0) {
1074 s->origPtr = i; 1065 state->origPtr = i;
1075 break; 1066 break;
1076 } 1067 }
1068 }
1077 1069
1078 AssertH(s->origPtr != -1, 1003); 1070 AssertH(state->origPtr != -1, 1003);
1079} 1071}
1080 1072
1081 1073
diff --git a/archival/libarchive/bz/bzlib.c b/archival/libarchive/bz/bzlib.c
index ef98bb213..9af2f026d 100644
--- a/archival/libarchive/bz/bzlib.c
+++ b/archival/libarchive/bz/bzlib.c
@@ -87,7 +87,7 @@ int isempty_RL(EState* s)
87static 87static
88void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k) 88void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
89{ 89{
90 int32_t n; 90 unsigned n;
91 EState* s; 91 EState* s;
92 92
93 s = xzalloc(sizeof(EState)); 93 s = xzalloc(sizeof(EState));
diff --git a/archival/libarchive/bz/bzlib_private.h b/archival/libarchive/bz/bzlib_private.h
index 4acaef8b8..fc05d0ebe 100644
--- a/archival/libarchive/bz/bzlib_private.h
+++ b/archival/libarchive/bz/bzlib_private.h
@@ -121,6 +121,7 @@ typedef struct EState {
121 /* mode this stream is in, and whether inputting */ 121 /* mode this stream is in, and whether inputting */
122 /* or outputting data */ 122 /* or outputting data */
123 int32_t mode; 123 int32_t mode;
124//both smallint?
124 int32_t state; 125 int32_t state;
125 126
126 /* remembers avail_in when flush/finish requested */ 127 /* remembers avail_in when flush/finish requested */
@@ -134,6 +135,9 @@ typedef struct EState {
134 uint32_t *arr2; 135 uint32_t *arr2;
135 uint32_t *ftab; 136 uint32_t *ftab;
136 137
138 uint16_t* quadrant;
139 int32_t budget;
140
137 /* aliases for arr1 and arr2 */ 141 /* aliases for arr1 and arr2 */
138 uint32_t *ptr; 142 uint32_t *ptr;
139 uint8_t *block; 143 uint8_t *block;
@@ -142,6 +146,7 @@ typedef struct EState {
142 146
143 /* guess what */ 147 /* guess what */
144 uint32_t *crc32table; 148 uint32_t *crc32table;
149//move down
145 150
146 /* run-length-encoding of the input */ 151 /* run-length-encoding of the input */
147 uint32_t state_in_ch; 152 uint32_t state_in_ch;
@@ -165,6 +170,7 @@ typedef struct EState {
165 /* misc administratium */ 170 /* misc administratium */
166 int32_t blockNo; 171 int32_t blockNo;
167 int32_t blockSize100k; 172 int32_t blockSize100k;
173//smallint?
168 174
169 /* stuff for coding the MTF values */ 175 /* stuff for coding the MTF values */
170 int32_t nMTF; 176 int32_t nMTF;