From 833d4e7f84f59099ee66eabfa3457ebb7d37eaa8 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Wed, 3 Nov 2010 02:38:31 +0100 Subject: rename archival/libunarchive -> archival/libarchive; move bz/ into it Signed-off-by: Denys Vlasenko --- archival/bz/blocksort.c | 1072 ----------------------------------------------- 1 file changed, 1072 deletions(-) delete mode 100644 archival/bz/blocksort.c (limited to 'archival/bz/blocksort.c') diff --git a/archival/bz/blocksort.c b/archival/bz/blocksort.c deleted file mode 100644 index f70c3701d..000000000 --- a/archival/bz/blocksort.c +++ /dev/null @@ -1,1072 +0,0 @@ -/* - * bzip2 is written by Julian Seward . - * Adapted for busybox by Denys Vlasenko . - * See README and LICENSE files in this directory for more information. - */ - -/*-------------------------------------------------------------*/ -/*--- Block sorting machinery ---*/ -/*--- blocksort.c ---*/ -/*-------------------------------------------------------------*/ - -/* ------------------------------------------------------------------ -This file is part of bzip2/libbzip2, a program and library for -lossless, block-sorting data compression. - -bzip2/libbzip2 version 1.0.4 of 20 December 2006 -Copyright (C) 1996-2006 Julian Seward - -Please read the WARNING, DISCLAIMER and PATENTS sections in the -README file. - -This program is released under the terms of the license contained -in the file LICENSE. ------------------------------------------------------------------- */ - -/* #include "bzlib_private.h" */ - -#define mswap(zz1, zz2) \ -{ \ - int32_t zztmp = zz1; \ - zz1 = zz2; \ - zz2 = zztmp; \ -} - -static -/* No measurable speed gain with inlining */ -/* ALWAYS_INLINE */ -void mvswap(uint32_t* ptr, int32_t zzp1, int32_t zzp2, int32_t zzn) -{ - while (zzn > 0) { - mswap(ptr[zzp1], ptr[zzp2]); - zzp1++; - zzp2++; - zzn--; - } -} - -static -ALWAYS_INLINE -int32_t mmin(int32_t a, int32_t b) -{ - return (a < b) ? a : b; -} - - -/*---------------------------------------------*/ -/*--- Fallback O(N log(N)^2) sorting ---*/ -/*--- algorithm, for repetitive blocks ---*/ -/*---------------------------------------------*/ - -/*---------------------------------------------*/ -static -inline -void fallbackSimpleSort(uint32_t* fmap, - uint32_t* eclass, - int32_t lo, - int32_t hi) -{ - int32_t i, j, tmp; - uint32_t ec_tmp; - - if (lo == hi) return; - - if (hi - lo > 3) { - for (i = hi-4; i >= lo; i--) { - tmp = fmap[i]; - ec_tmp = eclass[tmp]; - for (j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4) - fmap[j-4] = fmap[j]; - fmap[j-4] = tmp; - } - } - - for (i = hi-1; i >= lo; i--) { - tmp = fmap[i]; - ec_tmp = eclass[tmp]; - for (j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++) - fmap[j-1] = fmap[j]; - fmap[j-1] = tmp; - } -} - - -/*---------------------------------------------*/ -#define fpush(lz,hz) { \ - stackLo[sp] = lz; \ - stackHi[sp] = hz; \ - sp++; \ -} - -#define fpop(lz,hz) { \ - sp--; \ - lz = stackLo[sp]; \ - hz = stackHi[sp]; \ -} - -#define FALLBACK_QSORT_SMALL_THRESH 10 -#define FALLBACK_QSORT_STACK_SIZE 100 - -static -void fallbackQSort3(uint32_t* fmap, - uint32_t* eclass, - int32_t loSt, - int32_t hiSt) -{ - int32_t unLo, unHi, ltLo, gtHi, n, m; - int32_t sp, lo, hi; - uint32_t med, r, r3; - int32_t stackLo[FALLBACK_QSORT_STACK_SIZE]; - int32_t stackHi[FALLBACK_QSORT_STACK_SIZE]; - - r = 0; - - sp = 0; - fpush(loSt, hiSt); - - while (sp > 0) { - AssertH(sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004); - - fpop(lo, hi); - if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { - fallbackSimpleSort(fmap, eclass, lo, hi); - continue; - } - - /* Random partitioning. Median of 3 sometimes fails to - * avoid bad cases. Median of 9 seems to help but - * looks rather expensive. This too seems to work but - * is cheaper. Guidance for the magic constants - * 7621 and 32768 is taken from Sedgewick's algorithms - * book, chapter 35. - */ - r = ((r * 7621) + 1) % 32768; - r3 = r % 3; - if (r3 == 0) - med = eclass[fmap[lo]]; - else if (r3 == 1) - med = eclass[fmap[(lo+hi)>>1]]; - else - med = eclass[fmap[hi]]; - - unLo = ltLo = lo; - unHi = gtHi = hi; - - while (1) { - while (1) { - if (unLo > unHi) break; - n = (int32_t)eclass[fmap[unLo]] - (int32_t)med; - if (n == 0) { - mswap(fmap[unLo], fmap[ltLo]); - ltLo++; - unLo++; - continue; - }; - if (n > 0) break; - unLo++; - } - while (1) { - if (unLo > unHi) break; - n = (int32_t)eclass[fmap[unHi]] - (int32_t)med; - if (n == 0) { - mswap(fmap[unHi], fmap[gtHi]); - gtHi--; unHi--; - continue; - }; - if (n < 0) break; - unHi--; - } - if (unLo > unHi) break; - mswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; - } - - AssertD(unHi == unLo-1, "fallbackQSort3(2)"); - - if (gtHi < ltLo) continue; - - n = mmin(ltLo-lo, unLo-ltLo); mvswap(fmap, lo, unLo-n, n); - m = mmin(hi-gtHi, gtHi-unHi); mvswap(fmap, unLo, hi-m+1, m); - - n = lo + unLo - ltLo - 1; - m = hi - (gtHi - unHi) + 1; - - if (n - lo > hi - m) { - fpush(lo, n); - fpush(m, hi); - } else { - fpush(m, hi); - fpush(lo, n); - } - } -} - -#undef fpush -#undef fpop -#undef FALLBACK_QSORT_SMALL_THRESH -#undef FALLBACK_QSORT_STACK_SIZE - - -/*---------------------------------------------*/ -/* Pre: - * nblock > 0 - * eclass exists for [0 .. nblock-1] - * ((uint8_t*)eclass) [0 .. nblock-1] holds block - * ptr exists for [0 .. nblock-1] - * - * Post: - * ((uint8_t*)eclass) [0 .. nblock-1] holds block - * All other areas of eclass destroyed - * fmap [0 .. nblock-1] holds sorted order - * bhtab[0 .. 2+(nblock/32)] destroyed -*/ - -#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) -#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) -#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) -#define WORD_BH(zz) bhtab[(zz) >> 5] -#define UNALIGNED_BH(zz) ((zz) & 0x01f) - -static -void fallbackSort(uint32_t* fmap, - uint32_t* eclass, - uint32_t* bhtab, - int32_t nblock) -{ - int32_t ftab[257]; - int32_t ftabCopy[256]; - int32_t H, i, j, k, l, r, cc, cc1; - int32_t nNotDone; - int32_t nBhtab; - uint8_t* eclass8 = (uint8_t*)eclass; - - /* - * Initial 1-char radix sort to generate - * initial fmap and initial BH bits. - */ - for (i = 0; i < 257; i++) ftab[i] = 0; - for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; - for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; - - j = ftab[0]; /* bbox: optimized */ - for (i = 1; i < 257; i++) { - j += ftab[i]; - ftab[i] = j; - } - - for (i = 0; i < nblock; i++) { - j = eclass8[i]; - k = ftab[j] - 1; - ftab[j] = k; - fmap[k] = i; - } - - nBhtab = 2 + ((uint32_t)nblock / 32); /* bbox: unsigned div is easier */ - for (i = 0; i < nBhtab; i++) bhtab[i] = 0; - for (i = 0; i < 256; i++) SET_BH(ftab[i]); - - /* - * Inductively refine the buckets. Kind-of an - * "exponential radix sort" (!), inspired by the - * Manber-Myers suffix array construction algorithm. - */ - - /*-- set sentinel bits for block-end detection --*/ - for (i = 0; i < 32; i++) { - SET_BH(nblock + 2*i); - CLEAR_BH(nblock + 2*i + 1); - } - - /*-- the log(N) loop --*/ - H = 1; - while (1) { - j = 0; - for (i = 0; i < nblock; i++) { - if (ISSET_BH(i)) - j = i; - k = fmap[i] - H; - if (k < 0) - k += nblock; - eclass[k] = j; - } - - nNotDone = 0; - r = -1; - while (1) { - - /*-- find the next non-singleton bucket --*/ - k = r + 1; - while (ISSET_BH(k) && UNALIGNED_BH(k)) - k++; - if (ISSET_BH(k)) { - while (WORD_BH(k) == 0xffffffff) k += 32; - while (ISSET_BH(k)) k++; - } - l = k - 1; - if (l >= nblock) - break; - while (!ISSET_BH(k) && UNALIGNED_BH(k)) - k++; - if (!ISSET_BH(k)) { - while (WORD_BH(k) == 0x00000000) k += 32; - while (!ISSET_BH(k)) k++; - } - r = k - 1; - if (r >= nblock) - break; - - /*-- now [l, r] bracket current bucket --*/ - if (r > l) { - nNotDone += (r - l + 1); - fallbackQSort3(fmap, eclass, l, r); - - /*-- scan bucket and generate header bits-- */ - cc = -1; - for (i = l; i <= r; i++) { - cc1 = eclass[fmap[i]]; - if (cc != cc1) { - SET_BH(i); - cc = cc1; - }; - } - } - } - - H *= 2; - if (H > nblock || nNotDone == 0) - break; - } - - /* - * Reconstruct the original block in - * eclass8 [0 .. nblock-1], since the - * previous phase destroyed it. - */ - j = 0; - for (i = 0; i < nblock; i++) { - while (ftabCopy[j] == 0) - j++; - ftabCopy[j]--; - eclass8[fmap[i]] = (uint8_t)j; - } - AssertH(j < 256, 1005); -} - -#undef SET_BH -#undef CLEAR_BH -#undef ISSET_BH -#undef WORD_BH -#undef UNALIGNED_BH - - -/*---------------------------------------------*/ -/*--- The main, O(N^2 log(N)) sorting ---*/ -/*--- algorithm. Faster for "normal" ---*/ -/*--- non-repetitive blocks. ---*/ -/*---------------------------------------------*/ - -/*---------------------------------------------*/ -static -NOINLINE -int mainGtU( - uint32_t i1, - uint32_t i2, - uint8_t* block, - uint16_t* quadrant, - uint32_t nblock, - int32_t* budget) -{ - int32_t k; - uint8_t c1, c2; - uint16_t s1, s2; - -/* Loop unrolling here is actually very useful - * (generated code is much simpler), - * code size increase is only 270 bytes (i386) - * but speeds up compression 10% overall - */ - -#if CONFIG_BZIP2_FEATURE_SPEED >= 1 - -#define TIMES_8(code) \ - code; code; code; code; \ - code; code; code; code; -#define TIMES_12(code) \ - code; code; code; code; \ - code; code; code; code; \ - code; code; code; code; - -#else - -#define TIMES_8(code) \ -{ \ - int nn = 8; \ - do { \ - code; \ - } while (--nn); \ -} -#define TIMES_12(code) \ -{ \ - int nn = 12; \ - do { \ - code; \ - } while (--nn); \ -} - -#endif - - AssertD(i1 != i2, "mainGtU"); - TIMES_12( - c1 = block[i1]; c2 = block[i2]; - if (c1 != c2) return (c1 > c2); - i1++; i2++; - ) - - k = nblock + 8; - - do { - TIMES_8( - c1 = block[i1]; c2 = block[i2]; - if (c1 != c2) return (c1 > c2); - s1 = quadrant[i1]; s2 = quadrant[i2]; - if (s1 != s2) return (s1 > s2); - i1++; i2++; - ) - - if (i1 >= nblock) i1 -= nblock; - if (i2 >= nblock) i2 -= nblock; - - (*budget)--; - k -= 8; - } while (k >= 0); - - return False; -} -#undef TIMES_8 -#undef TIMES_12 - -/*---------------------------------------------*/ -/* - * Knuth's increments seem to work better - * than Incerpi-Sedgewick here. Possibly - * because the number of elems to sort is - * usually small, typically <= 20. - */ -static -const int32_t incs[14] = { - 1, 4, 13, 40, 121, 364, 1093, 3280, - 9841, 29524, 88573, 265720, - 797161, 2391484 -}; - -static -void mainSimpleSort(uint32_t* ptr, - uint8_t* block, - uint16_t* quadrant, - int32_t nblock, - int32_t lo, - int32_t hi, - int32_t d, - int32_t* budget) -{ - int32_t i, j, h, bigN, hp; - uint32_t v; - - bigN = hi - lo + 1; - if (bigN < 2) return; - - hp = 0; - while (incs[hp] < bigN) hp++; - hp--; - - for (; hp >= 0; hp--) { - h = incs[hp]; - - i = lo + h; - while (1) { - /*-- copy 1 --*/ - if (i > hi) break; - v = ptr[i]; - j = i; - while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { - ptr[j] = ptr[j-h]; - j = j - h; - if (j <= (lo + h - 1)) break; - } - ptr[j] = v; - i++; - -/* 1.5% overall speedup, +290 bytes */ -#if CONFIG_BZIP2_FEATURE_SPEED >= 3 - /*-- copy 2 --*/ - if (i > hi) break; - v = ptr[i]; - j = i; - while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { - ptr[j] = ptr[j-h]; - j = j - h; - if (j <= (lo + h - 1)) break; - } - ptr[j] = v; - i++; - - /*-- copy 3 --*/ - if (i > hi) break; - v = ptr[i]; - j = i; - while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) { - ptr[j] = ptr[j-h]; - j = j - h; - if (j <= (lo + h - 1)) break; - } - ptr[j] = v; - i++; -#endif - if (*budget < 0) return; - } - } -} - - -/*---------------------------------------------*/ -/* - * The following is an implementation of - * an elegant 3-way quicksort for strings, - * described in a paper "Fast Algorithms for - * Sorting and Searching Strings", by Robert - * Sedgewick and Jon L. Bentley. - */ - -static -ALWAYS_INLINE -uint8_t mmed3(uint8_t a, uint8_t b, uint8_t c) -{ - uint8_t t; - if (a > b) { - t = a; - a = b; - b = t; - }; - /* here b >= a */ - if (b > c) { - b = c; - if (a > b) - b = a; - } - return b; -} - -#define mpush(lz,hz,dz) \ -{ \ - stackLo[sp] = lz; \ - stackHi[sp] = hz; \ - stackD [sp] = dz; \ - sp++; \ -} - -#define mpop(lz,hz,dz) \ -{ \ - sp--; \ - lz = stackLo[sp]; \ - hz = stackHi[sp]; \ - dz = stackD [sp]; \ -} - -#define mnextsize(az) (nextHi[az] - nextLo[az]) - -#define mnextswap(az,bz) \ -{ \ - int32_t tz; \ - tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ - tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ - tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; \ -} - -#define MAIN_QSORT_SMALL_THRESH 20 -#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) -#define MAIN_QSORT_STACK_SIZE 100 - -static NOINLINE -void mainQSort3(uint32_t* ptr, - uint8_t* block, - uint16_t* quadrant, - int32_t nblock, - int32_t loSt, - int32_t hiSt, - int32_t dSt, - int32_t* budget) -{ - int32_t unLo, unHi, ltLo, gtHi, n, m, med; - int32_t sp, lo, hi, d; - - int32_t stackLo[MAIN_QSORT_STACK_SIZE]; - int32_t stackHi[MAIN_QSORT_STACK_SIZE]; - int32_t stackD [MAIN_QSORT_STACK_SIZE]; - - int32_t nextLo[3]; - int32_t nextHi[3]; - int32_t nextD [3]; - - sp = 0; - mpush(loSt, hiSt, dSt); - - while (sp > 0) { - AssertH(sp < MAIN_QSORT_STACK_SIZE - 2, 1001); - - mpop(lo, hi, d); - if (hi - lo < MAIN_QSORT_SMALL_THRESH - || d > MAIN_QSORT_DEPTH_THRESH - ) { - mainSimpleSort(ptr, block, quadrant, nblock, lo, hi, d, budget); - if (*budget < 0) - return; - continue; - } - med = (int32_t) mmed3(block[ptr[lo ] + d], - block[ptr[hi ] + d], - block[ptr[(lo+hi) >> 1] + d]); - - unLo = ltLo = lo; - unHi = gtHi = hi; - - while (1) { - while (1) { - if (unLo > unHi) - break; - n = ((int32_t)block[ptr[unLo]+d]) - med; - if (n == 0) { - mswap(ptr[unLo], ptr[ltLo]); - ltLo++; - unLo++; - continue; - }; - if (n > 0) break; - unLo++; - } - while (1) { - if (unLo > unHi) - break; - n = ((int32_t)block[ptr[unHi]+d]) - med; - if (n == 0) { - mswap(ptr[unHi], ptr[gtHi]); - gtHi--; - unHi--; - continue; - }; - if (n < 0) break; - unHi--; - } - if (unLo > unHi) - break; - mswap(ptr[unLo], ptr[unHi]); - unLo++; - unHi--; - } - - AssertD(unHi == unLo-1, "mainQSort3(2)"); - - if (gtHi < ltLo) { - mpush(lo, hi, d + 1); - continue; - } - - n = mmin(ltLo-lo, unLo-ltLo); mvswap(ptr, lo, unLo-n, n); - m = mmin(hi-gtHi, gtHi-unHi); mvswap(ptr, unLo, hi-m+1, m); - - n = lo + unLo - ltLo - 1; - m = hi - (gtHi - unHi) + 1; - - nextLo[0] = lo; nextHi[0] = n; nextD[0] = d; - nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; - nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; - - if (mnextsize(0) < mnextsize(1)) mnextswap(0, 1); - if (mnextsize(1) < mnextsize(2)) mnextswap(1, 2); - if (mnextsize(0) < mnextsize(1)) mnextswap(0, 1); - - AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)"); - AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)"); - - mpush(nextLo[0], nextHi[0], nextD[0]); - mpush(nextLo[1], nextHi[1], nextD[1]); - mpush(nextLo[2], nextHi[2], nextD[2]); - } -} - -#undef mpush -#undef mpop -#undef mnextsize -#undef mnextswap -#undef MAIN_QSORT_SMALL_THRESH -#undef MAIN_QSORT_DEPTH_THRESH -#undef MAIN_QSORT_STACK_SIZE - - -/*---------------------------------------------*/ -/* Pre: - * nblock > N_OVERSHOOT - * block32 exists for [0 .. nblock-1 +N_OVERSHOOT] - * ((uint8_t*)block32) [0 .. nblock-1] holds block - * ptr exists for [0 .. nblock-1] - * - * Post: - * ((uint8_t*)block32) [0 .. nblock-1] holds block - * All other areas of block32 destroyed - * ftab[0 .. 65536] destroyed - * ptr [0 .. nblock-1] holds sorted order - * if (*budget < 0), sorting was abandoned - */ - -#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) -#define SETMASK (1 << 21) -#define CLEARMASK (~(SETMASK)) - -static NOINLINE -void mainSort(EState* state, - uint32_t* ptr, - uint8_t* block, - uint16_t* quadrant, - uint32_t* ftab, - int32_t nblock, - int32_t* budget) -{ - int32_t i, j, k, ss, sb; - uint8_t c1; - int32_t numQSorted; - uint16_t s; - Bool bigDone[256]; - /* bbox: moved to EState to save stack - int32_t runningOrder[256]; - int32_t copyStart[256]; - int32_t copyEnd [256]; - */ -#define runningOrder (state->mainSort__runningOrder) -#define copyStart (state->mainSort__copyStart) -#define copyEnd (state->mainSort__copyEnd) - - /*-- set up the 2-byte frequency table --*/ - /* was: for (i = 65536; i >= 0; i--) ftab[i] = 0; */ - memset(ftab, 0, 65537 * sizeof(ftab[0])); - - j = block[0] << 8; - i = nblock - 1; -/* 3%, +300 bytes */ -#if CONFIG_BZIP2_FEATURE_SPEED >= 2 - for (; i >= 3; i -= 4) { - quadrant[i] = 0; - j = (j >> 8) | (((uint16_t)block[i]) << 8); - ftab[j]++; - quadrant[i-1] = 0; - j = (j >> 8) | (((uint16_t)block[i-1]) << 8); - ftab[j]++; - quadrant[i-2] = 0; - j = (j >> 8) | (((uint16_t)block[i-2]) << 8); - ftab[j]++; - quadrant[i-3] = 0; - j = (j >> 8) | (((uint16_t)block[i-3]) << 8); - ftab[j]++; - } -#endif - for (; i >= 0; i--) { - quadrant[i] = 0; - j = (j >> 8) | (((uint16_t)block[i]) << 8); - ftab[j]++; - } - - /*-- (emphasises close relationship of block & quadrant) --*/ - for (i = 0; i < BZ_N_OVERSHOOT; i++) { - block [nblock+i] = block[i]; - quadrant[nblock+i] = 0; - } - - /*-- Complete the initial radix sort --*/ - j = ftab[0]; /* bbox: optimized */ - for (i = 1; i <= 65536; i++) { - j += ftab[i]; - ftab[i] = j; - } - - s = block[0] << 8; - i = nblock - 1; -#if CONFIG_BZIP2_FEATURE_SPEED >= 2 - for (; i >= 3; i -= 4) { - s = (s >> 8) | (block[i] << 8); - j = ftab[s] - 1; - ftab[s] = j; - ptr[j] = i; - s = (s >> 8) | (block[i-1] << 8); - j = ftab[s] - 1; - ftab[s] = j; - ptr[j] = i-1; - s = (s >> 8) | (block[i-2] << 8); - j = ftab[s] - 1; - ftab[s] = j; - ptr[j] = i-2; - s = (s >> 8) | (block[i-3] << 8); - j = ftab[s] - 1; - ftab[s] = j; - ptr[j] = i-3; - } -#endif - for (; i >= 0; i--) { - s = (s >> 8) | (block[i] << 8); - j = ftab[s] - 1; - ftab[s] = j; - ptr[j] = i; - } - - /* - * Now ftab contains the first loc of every small bucket. - * Calculate the running order, from smallest to largest - * big bucket. - */ - for (i = 0; i <= 255; i++) { - bigDone [i] = False; - runningOrder[i] = i; - } - - { - int32_t vv; - /* bbox: was: int32_t h = 1; */ - /* do h = 3 * h + 1; while (h <= 256); */ - uint32_t h = 364; - - do { - /*h = h / 3;*/ - h = (h * 171) >> 9; /* bbox: fast h/3 */ - for (i = h; i <= 255; i++) { - vv = runningOrder[i]; - j = i; - while (BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv)) { - runningOrder[j] = runningOrder[j-h]; - j = j - h; - if (j <= (h - 1)) - goto zero; - } - zero: - runningOrder[j] = vv; - } - } while (h != 1); - } - - /* - * The main sorting loop. - */ - - numQSorted = 0; - - for (i = 0; i <= 255; i++) { - - /* - * Process big buckets, starting with the least full. - * Basically this is a 3-step process in which we call - * mainQSort3 to sort the small buckets [ss, j], but - * also make a big effort to avoid the calls if we can. - */ - ss = runningOrder[i]; - - /* - * Step 1: - * Complete the big bucket [ss] by quicksorting - * any unsorted small buckets [ss, j], for j != ss. - * Hopefully previous pointer-scanning phases have already - * completed many of the small buckets [ss, j], so - * we don't have to sort them at all. - */ - for (j = 0; j <= 255; j++) { - if (j != ss) { - sb = (ss << 8) + j; - if (!(ftab[sb] & SETMASK)) { - int32_t lo = ftab[sb] & CLEARMASK; - int32_t hi = (ftab[sb+1] & CLEARMASK) - 1; - if (hi > lo) { - mainQSort3( - ptr, block, quadrant, nblock, - lo, hi, BZ_N_RADIX, budget - ); - if (*budget < 0) return; - numQSorted += (hi - lo + 1); - } - } - ftab[sb] |= SETMASK; - } - } - - AssertH(!bigDone[ss], 1006); - - /* - * Step 2: - * Now scan this big bucket [ss] so as to synthesise the - * sorted order for small buckets [t, ss] for all t, - * including, magically, the bucket [ss,ss] too. - * This will avoid doing Real Work in subsequent Step 1's. - */ - { - for (j = 0; j <= 255; j++) { - copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK; - copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; - } - for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { - k = ptr[j] - 1; - if (k < 0) - k += nblock; - c1 = block[k]; - if (!bigDone[c1]) - ptr[copyStart[c1]++] = k; - } - for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { - k = ptr[j]-1; - if (k < 0) - k += nblock; - c1 = block[k]; - if (!bigDone[c1]) - ptr[copyEnd[c1]--] = k; - } - } - - /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. - * Necessity for this case is demonstrated by compressing - * a sequence of approximately 48.5 million of character - * 251; 1.0.0/1.0.1 will then die here. */ - AssertH((copyStart[ss]-1 == copyEnd[ss]) \ - || (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), 1007); - - for (j = 0; j <= 255; j++) - ftab[(j << 8) + ss] |= SETMASK; - - /* - * Step 3: - * The [ss] big bucket is now done. Record this fact, - * and update the quadrant descriptors. Remember to - * update quadrants in the overshoot area too, if - * necessary. The "if (i < 255)" test merely skips - * this updating for the last bucket processed, since - * updating for the last bucket is pointless. - * - * The quadrant array provides a way to incrementally - * cache sort orderings, as they appear, so as to - * make subsequent comparisons in fullGtU() complete - * faster. For repetitive blocks this makes a big - * difference (but not big enough to be able to avoid - * the fallback sorting mechanism, exponential radix sort). - * - * The precise meaning is: at all times: - * - * for 0 <= i < nblock and 0 <= j <= nblock - * - * if block[i] != block[j], - * - * then the relative values of quadrant[i] and - * quadrant[j] are meaningless. - * - * else { - * if quadrant[i] < quadrant[j] - * then the string starting at i lexicographically - * precedes the string starting at j - * - * else if quadrant[i] > quadrant[j] - * then the string starting at j lexicographically - * precedes the string starting at i - * - * else - * the relative ordering of the strings starting - * at i and j has not yet been determined. - * } - */ - bigDone[ss] = True; - - if (i < 255) { - int32_t bbStart = ftab[ss << 8] & CLEARMASK; - int32_t bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; - int32_t shifts = 0; - - while ((bbSize >> shifts) > 65534) shifts++; - - for (j = bbSize-1; j >= 0; j--) { - int32_t a2update = ptr[bbStart + j]; - uint16_t qVal = (uint16_t)(j >> shifts); - quadrant[a2update] = qVal; - if (a2update < BZ_N_OVERSHOOT) - quadrant[a2update + nblock] = qVal; - } - AssertH(((bbSize-1) >> shifts) <= 65535, 1002); - } - } -#undef runningOrder -#undef copyStart -#undef copyEnd -} - -#undef BIGFREQ -#undef SETMASK -#undef CLEARMASK - - -/*---------------------------------------------*/ -/* Pre: - * nblock > 0 - * arr2 exists for [0 .. nblock-1 +N_OVERSHOOT] - * ((uint8_t*)arr2)[0 .. nblock-1] holds block - * arr1 exists for [0 .. nblock-1] - * - * Post: - * ((uint8_t*)arr2) [0 .. nblock-1] holds block - * All other areas of block destroyed - * ftab[0 .. 65536] destroyed - * arr1[0 .. nblock-1] holds sorted order - */ -static NOINLINE -void BZ2_blockSort(EState* s) -{ - /* In original bzip2 1.0.4, it's a parameter, but 30 - * (which was the default) should work ok. */ - enum { wfact = 30 }; - - uint32_t* ptr = s->ptr; - uint8_t* block = s->block; - uint32_t* ftab = s->ftab; - int32_t nblock = s->nblock; - uint16_t* quadrant; - int32_t budget; - int32_t i; - - if (nblock < 10000) { - fallbackSort(s->arr1, s->arr2, ftab, nblock); - } else { - /* Calculate the location for quadrant, remembering to get - * the alignment right. Assumes that &(block[0]) is at least - * 2-byte aligned -- this should be ok since block is really - * the first section of arr2. - */ - i = nblock + BZ_N_OVERSHOOT; - if (i & 1) i++; - quadrant = (uint16_t*)(&(block[i])); - - /* (wfact-1) / 3 puts the default-factor-30 - * transition point at very roughly the same place as - * with v0.1 and v0.9.0. - * Not that it particularly matters any more, since the - * resulting compressed stream is now the same regardless - * of whether or not we use the main sort or fallback sort. - */ - budget = nblock * ((wfact-1) / 3); - - mainSort(s, ptr, block, quadrant, ftab, nblock, &budget); - if (budget < 0) { - fallbackSort(s->arr1, s->arr2, ftab, nblock); - } - } - - s->origPtr = -1; - for (i = 0; i < s->nblock; i++) - if (ptr[i] == 0) { - s->origPtr = i; - break; - }; - - AssertH(s->origPtr != -1, 1003); -} - - -/*-------------------------------------------------------------*/ -/*--- end blocksort.c ---*/ -/*-------------------------------------------------------------*/ -- cgit v1.2.3