cannam@89: cannam@89: /*-------------------------------------------------------------*/ cannam@89: /*--- Block sorting machinery ---*/ cannam@89: /*--- blocksort.c ---*/ cannam@89: /*-------------------------------------------------------------*/ cannam@89: cannam@89: /* ------------------------------------------------------------------ cannam@89: This file is part of bzip2/libbzip2, a program and library for cannam@89: lossless, block-sorting data compression. cannam@89: cannam@89: bzip2/libbzip2 version 1.0.6 of 6 September 2010 cannam@89: Copyright (C) 1996-2010 Julian Seward cannam@89: cannam@89: Please read the WARNING, DISCLAIMER and PATENTS sections in the cannam@89: README file. cannam@89: cannam@89: This program is released under the terms of the license contained cannam@89: in the file LICENSE. cannam@89: ------------------------------------------------------------------ */ cannam@89: cannam@89: cannam@89: #include "bzlib_private.h" cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /*--- Fallback O(N log(N)^2) sorting ---*/ cannam@89: /*--- algorithm, for repetitive blocks ---*/ cannam@89: /*---------------------------------------------*/ cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: static cannam@89: __inline__ cannam@89: void fallbackSimpleSort ( UInt32* fmap, cannam@89: UInt32* eclass, cannam@89: Int32 lo, cannam@89: Int32 hi ) cannam@89: { cannam@89: Int32 i, j, tmp; cannam@89: UInt32 ec_tmp; cannam@89: cannam@89: if (lo == hi) return; cannam@89: cannam@89: if (hi - lo > 3) { cannam@89: for ( i = hi-4; i >= lo; i-- ) { cannam@89: tmp = fmap[i]; cannam@89: ec_tmp = eclass[tmp]; cannam@89: for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) cannam@89: fmap[j-4] = fmap[j]; cannam@89: fmap[j-4] = tmp; cannam@89: } cannam@89: } cannam@89: cannam@89: for ( i = hi-1; i >= lo; i-- ) { cannam@89: tmp = fmap[i]; cannam@89: ec_tmp = eclass[tmp]; cannam@89: for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) cannam@89: fmap[j-1] = fmap[j]; cannam@89: fmap[j-1] = tmp; cannam@89: } cannam@89: } cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: #define fswap(zz1, zz2) \ cannam@89: { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } cannam@89: cannam@89: #define fvswap(zzp1, zzp2, zzn) \ cannam@89: { \ cannam@89: Int32 yyp1 = (zzp1); \ cannam@89: Int32 yyp2 = (zzp2); \ cannam@89: Int32 yyn = (zzn); \ cannam@89: while (yyn > 0) { \ cannam@89: fswap(fmap[yyp1], fmap[yyp2]); \ cannam@89: yyp1++; yyp2++; yyn--; \ cannam@89: } \ cannam@89: } cannam@89: cannam@89: cannam@89: #define fmin(a,b) ((a) < (b)) ? (a) : (b) cannam@89: cannam@89: #define fpush(lz,hz) { stackLo[sp] = lz; \ cannam@89: stackHi[sp] = hz; \ cannam@89: sp++; } cannam@89: cannam@89: #define fpop(lz,hz) { sp--; \ cannam@89: lz = stackLo[sp]; \ cannam@89: hz = stackHi[sp]; } cannam@89: cannam@89: #define FALLBACK_QSORT_SMALL_THRESH 10 cannam@89: #define FALLBACK_QSORT_STACK_SIZE 100 cannam@89: cannam@89: cannam@89: static cannam@89: void fallbackQSort3 ( UInt32* fmap, cannam@89: UInt32* eclass, cannam@89: Int32 loSt, cannam@89: Int32 hiSt ) cannam@89: { cannam@89: Int32 unLo, unHi, ltLo, gtHi, n, m; cannam@89: Int32 sp, lo, hi; cannam@89: UInt32 med, r, r3; cannam@89: Int32 stackLo[FALLBACK_QSORT_STACK_SIZE]; cannam@89: Int32 stackHi[FALLBACK_QSORT_STACK_SIZE]; cannam@89: cannam@89: r = 0; cannam@89: cannam@89: sp = 0; cannam@89: fpush ( loSt, hiSt ); cannam@89: cannam@89: while (sp > 0) { cannam@89: cannam@89: AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 ); cannam@89: cannam@89: fpop ( lo, hi ); cannam@89: if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { cannam@89: fallbackSimpleSort ( fmap, eclass, lo, hi ); cannam@89: continue; cannam@89: } cannam@89: cannam@89: /* Random partitioning. Median of 3 sometimes fails to cannam@89: avoid bad cases. Median of 9 seems to help but cannam@89: looks rather expensive. This too seems to work but cannam@89: is cheaper. Guidance for the magic constants cannam@89: 7621 and 32768 is taken from Sedgewick's algorithms cannam@89: book, chapter 35. cannam@89: */ cannam@89: r = ((r * 7621) + 1) % 32768; cannam@89: r3 = r % 3; cannam@89: if (r3 == 0) med = eclass[fmap[lo]]; else cannam@89: if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else cannam@89: med = eclass[fmap[hi]]; cannam@89: cannam@89: unLo = ltLo = lo; cannam@89: unHi = gtHi = hi; cannam@89: cannam@89: while (1) { cannam@89: while (1) { cannam@89: if (unLo > unHi) break; cannam@89: n = (Int32)eclass[fmap[unLo]] - (Int32)med; cannam@89: if (n == 0) { cannam@89: fswap(fmap[unLo], fmap[ltLo]); cannam@89: ltLo++; unLo++; cannam@89: continue; cannam@89: }; cannam@89: if (n > 0) break; cannam@89: unLo++; cannam@89: } cannam@89: while (1) { cannam@89: if (unLo > unHi) break; cannam@89: n = (Int32)eclass[fmap[unHi]] - (Int32)med; cannam@89: if (n == 0) { cannam@89: fswap(fmap[unHi], fmap[gtHi]); cannam@89: gtHi--; unHi--; cannam@89: continue; cannam@89: }; cannam@89: if (n < 0) break; cannam@89: unHi--; cannam@89: } cannam@89: if (unLo > unHi) break; cannam@89: fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; cannam@89: } cannam@89: cannam@89: AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); cannam@89: cannam@89: if (gtHi < ltLo) continue; cannam@89: cannam@89: n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); cannam@89: m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); cannam@89: cannam@89: n = lo + unLo - ltLo - 1; cannam@89: m = hi - (gtHi - unHi) + 1; cannam@89: cannam@89: if (n - lo > hi - m) { cannam@89: fpush ( lo, n ); cannam@89: fpush ( m, hi ); cannam@89: } else { cannam@89: fpush ( m, hi ); cannam@89: fpush ( lo, n ); cannam@89: } cannam@89: } cannam@89: } cannam@89: cannam@89: #undef fmin cannam@89: #undef fpush cannam@89: #undef fpop cannam@89: #undef fswap cannam@89: #undef fvswap cannam@89: #undef FALLBACK_QSORT_SMALL_THRESH cannam@89: #undef FALLBACK_QSORT_STACK_SIZE cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /* Pre: cannam@89: nblock > 0 cannam@89: eclass exists for [0 .. nblock-1] cannam@89: ((UChar*)eclass) [0 .. nblock-1] holds block cannam@89: ptr exists for [0 .. nblock-1] cannam@89: cannam@89: Post: cannam@89: ((UChar*)eclass) [0 .. nblock-1] holds block cannam@89: All other areas of eclass destroyed cannam@89: fmap [0 .. nblock-1] holds sorted order cannam@89: bhtab [ 0 .. 2+(nblock/32) ] destroyed cannam@89: */ cannam@89: cannam@89: #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) cannam@89: #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) cannam@89: #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) cannam@89: #define WORD_BH(zz) bhtab[(zz) >> 5] cannam@89: #define UNALIGNED_BH(zz) ((zz) & 0x01f) cannam@89: cannam@89: static cannam@89: void fallbackSort ( UInt32* fmap, cannam@89: UInt32* eclass, cannam@89: UInt32* bhtab, cannam@89: Int32 nblock, cannam@89: Int32 verb ) cannam@89: { cannam@89: Int32 ftab[257]; cannam@89: Int32 ftabCopy[256]; cannam@89: Int32 H, i, j, k, l, r, cc, cc1; cannam@89: Int32 nNotDone; cannam@89: Int32 nBhtab; cannam@89: UChar* eclass8 = (UChar*)eclass; cannam@89: cannam@89: /*-- cannam@89: Initial 1-char radix sort to generate cannam@89: initial fmap and initial BH bits. cannam@89: --*/ cannam@89: if (verb >= 4) cannam@89: VPrintf0 ( " bucket sorting ...\n" ); cannam@89: for (i = 0; i < 257; i++) ftab[i] = 0; cannam@89: for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; cannam@89: for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; cannam@89: for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; cannam@89: cannam@89: for (i = 0; i < nblock; i++) { cannam@89: j = eclass8[i]; cannam@89: k = ftab[j] - 1; cannam@89: ftab[j] = k; cannam@89: fmap[k] = i; cannam@89: } cannam@89: cannam@89: nBhtab = 2 + (nblock / 32); cannam@89: for (i = 0; i < nBhtab; i++) bhtab[i] = 0; cannam@89: for (i = 0; i < 256; i++) SET_BH(ftab[i]); cannam@89: cannam@89: /*-- cannam@89: Inductively refine the buckets. Kind-of an cannam@89: "exponential radix sort" (!), inspired by the cannam@89: Manber-Myers suffix array construction algorithm. cannam@89: --*/ cannam@89: cannam@89: /*-- set sentinel bits for block-end detection --*/ cannam@89: for (i = 0; i < 32; i++) { cannam@89: SET_BH(nblock + 2*i); cannam@89: CLEAR_BH(nblock + 2*i + 1); cannam@89: } cannam@89: cannam@89: /*-- the log(N) loop --*/ cannam@89: H = 1; cannam@89: while (1) { cannam@89: cannam@89: if (verb >= 4) cannam@89: VPrintf1 ( " depth %6d has ", H ); cannam@89: cannam@89: j = 0; cannam@89: for (i = 0; i < nblock; i++) { cannam@89: if (ISSET_BH(i)) j = i; cannam@89: k = fmap[i] - H; if (k < 0) k += nblock; cannam@89: eclass[k] = j; cannam@89: } cannam@89: cannam@89: nNotDone = 0; cannam@89: r = -1; cannam@89: while (1) { cannam@89: cannam@89: /*-- find the next non-singleton bucket --*/ cannam@89: k = r + 1; cannam@89: while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; cannam@89: if (ISSET_BH(k)) { cannam@89: while (WORD_BH(k) == 0xffffffff) k += 32; cannam@89: while (ISSET_BH(k)) k++; cannam@89: } cannam@89: l = k - 1; cannam@89: if (l >= nblock) break; cannam@89: while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; cannam@89: if (!ISSET_BH(k)) { cannam@89: while (WORD_BH(k) == 0x00000000) k += 32; cannam@89: while (!ISSET_BH(k)) k++; cannam@89: } cannam@89: r = k - 1; cannam@89: if (r >= nblock) break; cannam@89: cannam@89: /*-- now [l, r] bracket current bucket --*/ cannam@89: if (r > l) { cannam@89: nNotDone += (r - l + 1); cannam@89: fallbackQSort3 ( fmap, eclass, l, r ); cannam@89: cannam@89: /*-- scan bucket and generate header bits-- */ cannam@89: cc = -1; cannam@89: for (i = l; i <= r; i++) { cannam@89: cc1 = eclass[fmap[i]]; cannam@89: if (cc != cc1) { SET_BH(i); cc = cc1; }; cannam@89: } cannam@89: } cannam@89: } cannam@89: cannam@89: if (verb >= 4) cannam@89: VPrintf1 ( "%6d unresolved strings\n", nNotDone ); cannam@89: cannam@89: H *= 2; cannam@89: if (H > nblock || nNotDone == 0) break; cannam@89: } cannam@89: cannam@89: /*-- cannam@89: Reconstruct the original block in cannam@89: eclass8 [0 .. nblock-1], since the cannam@89: previous phase destroyed it. cannam@89: --*/ cannam@89: if (verb >= 4) cannam@89: VPrintf0 ( " reconstructing block ...\n" ); cannam@89: j = 0; cannam@89: for (i = 0; i < nblock; i++) { cannam@89: while (ftabCopy[j] == 0) j++; cannam@89: ftabCopy[j]--; cannam@89: eclass8[fmap[i]] = (UChar)j; cannam@89: } cannam@89: AssertH ( j < 256, 1005 ); cannam@89: } cannam@89: cannam@89: #undef SET_BH cannam@89: #undef CLEAR_BH cannam@89: #undef ISSET_BH cannam@89: #undef WORD_BH cannam@89: #undef UNALIGNED_BH cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /*--- The main, O(N^2 log(N)) sorting ---*/ cannam@89: /*--- algorithm. Faster for "normal" ---*/ cannam@89: /*--- non-repetitive blocks. ---*/ cannam@89: /*---------------------------------------------*/ cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: static cannam@89: __inline__ cannam@89: Bool mainGtU ( UInt32 i1, cannam@89: UInt32 i2, cannam@89: UChar* block, cannam@89: UInt16* quadrant, cannam@89: UInt32 nblock, cannam@89: Int32* budget ) cannam@89: { cannam@89: Int32 k; cannam@89: UChar c1, c2; cannam@89: UInt16 s1, s2; cannam@89: cannam@89: AssertD ( i1 != i2, "mainGtU" ); cannam@89: /* 1 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 2 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 3 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 4 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 5 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 6 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 7 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 8 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 9 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 10 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 11 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: /* 12 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: i1++; i2++; cannam@89: cannam@89: k = nblock + 8; cannam@89: cannam@89: do { cannam@89: /* 1 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 2 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 3 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 4 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 5 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 6 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 7 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: /* 8 */ cannam@89: c1 = block[i1]; c2 = block[i2]; cannam@89: if (c1 != c2) return (c1 > c2); cannam@89: s1 = quadrant[i1]; s2 = quadrant[i2]; cannam@89: if (s1 != s2) return (s1 > s2); cannam@89: i1++; i2++; cannam@89: cannam@89: if (i1 >= nblock) i1 -= nblock; cannam@89: if (i2 >= nblock) i2 -= nblock; cannam@89: cannam@89: k -= 8; cannam@89: (*budget)--; cannam@89: } cannam@89: while (k >= 0); cannam@89: cannam@89: return False; cannam@89: } cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /*-- cannam@89: Knuth's increments seem to work better cannam@89: than Incerpi-Sedgewick here. Possibly cannam@89: because the number of elems to sort is cannam@89: usually small, typically <= 20. cannam@89: --*/ cannam@89: static cannam@89: Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280, cannam@89: 9841, 29524, 88573, 265720, cannam@89: 797161, 2391484 }; cannam@89: cannam@89: static cannam@89: void mainSimpleSort ( UInt32* ptr, cannam@89: UChar* block, cannam@89: UInt16* quadrant, cannam@89: Int32 nblock, cannam@89: Int32 lo, cannam@89: Int32 hi, cannam@89: Int32 d, cannam@89: Int32* budget ) cannam@89: { cannam@89: Int32 i, j, h, bigN, hp; cannam@89: UInt32 v; cannam@89: cannam@89: bigN = hi - lo + 1; cannam@89: if (bigN < 2) return; cannam@89: cannam@89: hp = 0; cannam@89: while (incs[hp] < bigN) hp++; cannam@89: hp--; cannam@89: cannam@89: for (; hp >= 0; hp--) { cannam@89: h = incs[hp]; cannam@89: cannam@89: i = lo + h; cannam@89: while (True) { cannam@89: cannam@89: /*-- copy 1 --*/ cannam@89: if (i > hi) break; cannam@89: v = ptr[i]; cannam@89: j = i; cannam@89: while ( mainGtU ( cannam@89: ptr[j-h]+d, v+d, block, quadrant, nblock, budget cannam@89: ) ) { cannam@89: ptr[j] = ptr[j-h]; cannam@89: j = j - h; cannam@89: if (j <= (lo + h - 1)) break; cannam@89: } cannam@89: ptr[j] = v; cannam@89: i++; cannam@89: cannam@89: /*-- copy 2 --*/ cannam@89: if (i > hi) break; cannam@89: v = ptr[i]; cannam@89: j = i; cannam@89: while ( mainGtU ( cannam@89: ptr[j-h]+d, v+d, block, quadrant, nblock, budget cannam@89: ) ) { cannam@89: ptr[j] = ptr[j-h]; cannam@89: j = j - h; cannam@89: if (j <= (lo + h - 1)) break; cannam@89: } cannam@89: ptr[j] = v; cannam@89: i++; cannam@89: cannam@89: /*-- copy 3 --*/ cannam@89: if (i > hi) break; cannam@89: v = ptr[i]; cannam@89: j = i; cannam@89: while ( mainGtU ( cannam@89: ptr[j-h]+d, v+d, block, quadrant, nblock, budget cannam@89: ) ) { cannam@89: ptr[j] = ptr[j-h]; cannam@89: j = j - h; cannam@89: if (j <= (lo + h - 1)) break; cannam@89: } cannam@89: ptr[j] = v; cannam@89: i++; cannam@89: cannam@89: if (*budget < 0) return; cannam@89: } cannam@89: } cannam@89: } cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /*-- cannam@89: The following is an implementation of cannam@89: an elegant 3-way quicksort for strings, cannam@89: described in a paper "Fast Algorithms for cannam@89: Sorting and Searching Strings", by Robert cannam@89: Sedgewick and Jon L. Bentley. cannam@89: --*/ cannam@89: cannam@89: #define mswap(zz1, zz2) \ cannam@89: { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } cannam@89: cannam@89: #define mvswap(zzp1, zzp2, zzn) \ cannam@89: { \ cannam@89: Int32 yyp1 = (zzp1); \ cannam@89: Int32 yyp2 = (zzp2); \ cannam@89: Int32 yyn = (zzn); \ cannam@89: while (yyn > 0) { \ cannam@89: mswap(ptr[yyp1], ptr[yyp2]); \ cannam@89: yyp1++; yyp2++; yyn--; \ cannam@89: } \ cannam@89: } cannam@89: cannam@89: static cannam@89: __inline__ cannam@89: UChar mmed3 ( UChar a, UChar b, UChar c ) cannam@89: { cannam@89: UChar t; cannam@89: if (a > b) { t = a; a = b; b = t; }; cannam@89: if (b > c) { cannam@89: b = c; cannam@89: if (a > b) b = a; cannam@89: } cannam@89: return b; cannam@89: } cannam@89: cannam@89: #define mmin(a,b) ((a) < (b)) ? (a) : (b) cannam@89: cannam@89: #define mpush(lz,hz,dz) { stackLo[sp] = lz; \ cannam@89: stackHi[sp] = hz; \ cannam@89: stackD [sp] = dz; \ cannam@89: sp++; } cannam@89: cannam@89: #define mpop(lz,hz,dz) { sp--; \ cannam@89: lz = stackLo[sp]; \ cannam@89: hz = stackHi[sp]; \ cannam@89: dz = stackD [sp]; } cannam@89: cannam@89: cannam@89: #define mnextsize(az) (nextHi[az]-nextLo[az]) cannam@89: cannam@89: #define mnextswap(az,bz) \ cannam@89: { Int32 tz; \ cannam@89: tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ cannam@89: tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ cannam@89: tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; } cannam@89: cannam@89: cannam@89: #define MAIN_QSORT_SMALL_THRESH 20 cannam@89: #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) cannam@89: #define MAIN_QSORT_STACK_SIZE 100 cannam@89: cannam@89: static cannam@89: void mainQSort3 ( UInt32* ptr, cannam@89: UChar* block, cannam@89: UInt16* quadrant, cannam@89: Int32 nblock, cannam@89: Int32 loSt, cannam@89: Int32 hiSt, cannam@89: Int32 dSt, cannam@89: Int32* budget ) cannam@89: { cannam@89: Int32 unLo, unHi, ltLo, gtHi, n, m, med; cannam@89: Int32 sp, lo, hi, d; cannam@89: cannam@89: Int32 stackLo[MAIN_QSORT_STACK_SIZE]; cannam@89: Int32 stackHi[MAIN_QSORT_STACK_SIZE]; cannam@89: Int32 stackD [MAIN_QSORT_STACK_SIZE]; cannam@89: cannam@89: Int32 nextLo[3]; cannam@89: Int32 nextHi[3]; cannam@89: Int32 nextD [3]; cannam@89: cannam@89: sp = 0; cannam@89: mpush ( loSt, hiSt, dSt ); cannam@89: cannam@89: while (sp > 0) { cannam@89: cannam@89: AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); cannam@89: cannam@89: mpop ( lo, hi, d ); cannam@89: if (hi - lo < MAIN_QSORT_SMALL_THRESH || cannam@89: d > MAIN_QSORT_DEPTH_THRESH) { cannam@89: mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget ); cannam@89: if (*budget < 0) return; cannam@89: continue; cannam@89: } cannam@89: cannam@89: med = (Int32) cannam@89: mmed3 ( block[ptr[ lo ]+d], cannam@89: block[ptr[ hi ]+d], cannam@89: block[ptr[ (lo+hi)>>1 ]+d] ); cannam@89: cannam@89: unLo = ltLo = lo; cannam@89: unHi = gtHi = hi; cannam@89: cannam@89: while (True) { cannam@89: while (True) { cannam@89: if (unLo > unHi) break; cannam@89: n = ((Int32)block[ptr[unLo]+d]) - med; cannam@89: if (n == 0) { cannam@89: mswap(ptr[unLo], ptr[ltLo]); cannam@89: ltLo++; unLo++; continue; cannam@89: }; cannam@89: if (n > 0) break; cannam@89: unLo++; cannam@89: } cannam@89: while (True) { cannam@89: if (unLo > unHi) break; cannam@89: n = ((Int32)block[ptr[unHi]+d]) - med; cannam@89: if (n == 0) { cannam@89: mswap(ptr[unHi], ptr[gtHi]); cannam@89: gtHi--; unHi--; continue; cannam@89: }; cannam@89: if (n < 0) break; cannam@89: unHi--; cannam@89: } cannam@89: if (unLo > unHi) break; cannam@89: mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--; cannam@89: } cannam@89: cannam@89: AssertD ( unHi == unLo-1, "mainQSort3(2)" ); cannam@89: cannam@89: if (gtHi < ltLo) { cannam@89: mpush(lo, hi, d+1 ); cannam@89: continue; cannam@89: } cannam@89: cannam@89: n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); cannam@89: m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); cannam@89: cannam@89: n = lo + unLo - ltLo - 1; cannam@89: m = hi - (gtHi - unHi) + 1; cannam@89: cannam@89: nextLo[0] = lo; nextHi[0] = n; nextD[0] = d; cannam@89: nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; cannam@89: nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; cannam@89: cannam@89: if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); cannam@89: if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); cannam@89: if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); cannam@89: cannam@89: AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" ); cannam@89: AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" ); cannam@89: cannam@89: mpush (nextLo[0], nextHi[0], nextD[0]); cannam@89: mpush (nextLo[1], nextHi[1], nextD[1]); cannam@89: mpush (nextLo[2], nextHi[2], nextD[2]); cannam@89: } cannam@89: } cannam@89: cannam@89: #undef mswap cannam@89: #undef mvswap cannam@89: #undef mpush cannam@89: #undef mpop cannam@89: #undef mmin cannam@89: #undef mnextsize cannam@89: #undef mnextswap cannam@89: #undef MAIN_QSORT_SMALL_THRESH cannam@89: #undef MAIN_QSORT_DEPTH_THRESH cannam@89: #undef MAIN_QSORT_STACK_SIZE cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /* Pre: cannam@89: nblock > N_OVERSHOOT cannam@89: block32 exists for [0 .. nblock-1 +N_OVERSHOOT] cannam@89: ((UChar*)block32) [0 .. nblock-1] holds block cannam@89: ptr exists for [0 .. nblock-1] cannam@89: cannam@89: Post: cannam@89: ((UChar*)block32) [0 .. nblock-1] holds block cannam@89: All other areas of block32 destroyed cannam@89: ftab [0 .. 65536 ] destroyed cannam@89: ptr [0 .. nblock-1] holds sorted order cannam@89: if (*budget < 0), sorting was abandoned cannam@89: */ cannam@89: cannam@89: #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) cannam@89: #define SETMASK (1 << 21) cannam@89: #define CLEARMASK (~(SETMASK)) cannam@89: cannam@89: static cannam@89: void mainSort ( UInt32* ptr, cannam@89: UChar* block, cannam@89: UInt16* quadrant, cannam@89: UInt32* ftab, cannam@89: Int32 nblock, cannam@89: Int32 verb, cannam@89: Int32* budget ) cannam@89: { cannam@89: Int32 i, j, k, ss, sb; cannam@89: Int32 runningOrder[256]; cannam@89: Bool bigDone[256]; cannam@89: Int32 copyStart[256]; cannam@89: Int32 copyEnd [256]; cannam@89: UChar c1; cannam@89: Int32 numQSorted; cannam@89: UInt16 s; cannam@89: if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" ); cannam@89: cannam@89: /*-- set up the 2-byte frequency table --*/ cannam@89: for (i = 65536; i >= 0; i--) ftab[i] = 0; cannam@89: cannam@89: j = block[0] << 8; cannam@89: i = nblock-1; cannam@89: for (; i >= 3; i -= 4) { cannam@89: quadrant[i] = 0; cannam@89: j = (j >> 8) | ( ((UInt16)block[i]) << 8); cannam@89: ftab[j]++; cannam@89: quadrant[i-1] = 0; cannam@89: j = (j >> 8) | ( ((UInt16)block[i-1]) << 8); cannam@89: ftab[j]++; cannam@89: quadrant[i-2] = 0; cannam@89: j = (j >> 8) | ( ((UInt16)block[i-2]) << 8); cannam@89: ftab[j]++; cannam@89: quadrant[i-3] = 0; cannam@89: j = (j >> 8) | ( ((UInt16)block[i-3]) << 8); cannam@89: ftab[j]++; cannam@89: } cannam@89: for (; i >= 0; i--) { cannam@89: quadrant[i] = 0; cannam@89: j = (j >> 8) | ( ((UInt16)block[i]) << 8); cannam@89: ftab[j]++; cannam@89: } cannam@89: cannam@89: /*-- (emphasises close relationship of block & quadrant) --*/ cannam@89: for (i = 0; i < BZ_N_OVERSHOOT; i++) { cannam@89: block [nblock+i] = block[i]; cannam@89: quadrant[nblock+i] = 0; cannam@89: } cannam@89: cannam@89: if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" ); cannam@89: cannam@89: /*-- Complete the initial radix sort --*/ cannam@89: for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; cannam@89: cannam@89: s = block[0] << 8; cannam@89: i = nblock-1; cannam@89: for (; i >= 3; i -= 4) { cannam@89: s = (s >> 8) | (block[i] << 8); cannam@89: j = ftab[s] -1; cannam@89: ftab[s] = j; cannam@89: ptr[j] = i; cannam@89: s = (s >> 8) | (block[i-1] << 8); cannam@89: j = ftab[s] -1; cannam@89: ftab[s] = j; cannam@89: ptr[j] = i-1; cannam@89: s = (s >> 8) | (block[i-2] << 8); cannam@89: j = ftab[s] -1; cannam@89: ftab[s] = j; cannam@89: ptr[j] = i-2; cannam@89: s = (s >> 8) | (block[i-3] << 8); cannam@89: j = ftab[s] -1; cannam@89: ftab[s] = j; cannam@89: ptr[j] = i-3; cannam@89: } cannam@89: for (; i >= 0; i--) { cannam@89: s = (s >> 8) | (block[i] << 8); cannam@89: j = ftab[s] -1; cannam@89: ftab[s] = j; cannam@89: ptr[j] = i; cannam@89: } cannam@89: cannam@89: /*-- cannam@89: Now ftab contains the first loc of every small bucket. cannam@89: Calculate the running order, from smallest to largest cannam@89: big bucket. cannam@89: --*/ cannam@89: for (i = 0; i <= 255; i++) { cannam@89: bigDone [i] = False; cannam@89: runningOrder[i] = i; cannam@89: } cannam@89: cannam@89: { cannam@89: Int32 vv; cannam@89: Int32 h = 1; cannam@89: do h = 3 * h + 1; while (h <= 256); cannam@89: do { cannam@89: h = h / 3; cannam@89: for (i = h; i <= 255; i++) { cannam@89: vv = runningOrder[i]; cannam@89: j = i; cannam@89: while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { cannam@89: runningOrder[j] = runningOrder[j-h]; cannam@89: j = j - h; cannam@89: if (j <= (h - 1)) goto zero; cannam@89: } cannam@89: zero: cannam@89: runningOrder[j] = vv; cannam@89: } cannam@89: } while (h != 1); cannam@89: } cannam@89: cannam@89: /*-- cannam@89: The main sorting loop. cannam@89: --*/ cannam@89: cannam@89: numQSorted = 0; cannam@89: cannam@89: for (i = 0; i <= 255; i++) { cannam@89: cannam@89: /*-- cannam@89: Process big buckets, starting with the least full. cannam@89: Basically this is a 3-step process in which we call cannam@89: mainQSort3 to sort the small buckets [ss, j], but cannam@89: also make a big effort to avoid the calls if we can. cannam@89: --*/ cannam@89: ss = runningOrder[i]; cannam@89: cannam@89: /*-- cannam@89: Step 1: cannam@89: Complete the big bucket [ss] by quicksorting cannam@89: any unsorted small buckets [ss, j], for j != ss. cannam@89: Hopefully previous pointer-scanning phases have already cannam@89: completed many of the small buckets [ss, j], so cannam@89: we don't have to sort them at all. cannam@89: --*/ cannam@89: for (j = 0; j <= 255; j++) { cannam@89: if (j != ss) { cannam@89: sb = (ss << 8) + j; cannam@89: if ( ! (ftab[sb] & SETMASK) ) { cannam@89: Int32 lo = ftab[sb] & CLEARMASK; cannam@89: Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; cannam@89: if (hi > lo) { cannam@89: if (verb >= 4) cannam@89: VPrintf4 ( " qsort [0x%x, 0x%x] " cannam@89: "done %d this %d\n", cannam@89: ss, j, numQSorted, hi - lo + 1 ); cannam@89: mainQSort3 ( cannam@89: ptr, block, quadrant, nblock, cannam@89: lo, hi, BZ_N_RADIX, budget cannam@89: ); cannam@89: numQSorted += (hi - lo + 1); cannam@89: if (*budget < 0) return; cannam@89: } cannam@89: } cannam@89: ftab[sb] |= SETMASK; cannam@89: } cannam@89: } cannam@89: cannam@89: AssertH ( !bigDone[ss], 1006 ); cannam@89: cannam@89: /*-- cannam@89: Step 2: cannam@89: Now scan this big bucket [ss] so as to synthesise the cannam@89: sorted order for small buckets [t, ss] for all t, cannam@89: including, magically, the bucket [ss,ss] too. cannam@89: This will avoid doing Real Work in subsequent Step 1's. cannam@89: --*/ cannam@89: { cannam@89: for (j = 0; j <= 255; j++) { cannam@89: copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK; cannam@89: copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; cannam@89: } cannam@89: for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { cannam@89: k = ptr[j]-1; if (k < 0) k += nblock; cannam@89: c1 = block[k]; cannam@89: if (!bigDone[c1]) cannam@89: ptr[ copyStart[c1]++ ] = k; cannam@89: } cannam@89: for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { cannam@89: k = ptr[j]-1; if (k < 0) k += nblock; cannam@89: c1 = block[k]; cannam@89: if (!bigDone[c1]) cannam@89: ptr[ copyEnd[c1]-- ] = k; cannam@89: } cannam@89: } cannam@89: cannam@89: AssertH ( (copyStart[ss]-1 == copyEnd[ss]) cannam@89: || cannam@89: /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. cannam@89: Necessity for this case is demonstrated by compressing cannam@89: a sequence of approximately 48.5 million of character cannam@89: 251; 1.0.0/1.0.1 will then die here. */ cannam@89: (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), cannam@89: 1007 ) cannam@89: cannam@89: for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; cannam@89: cannam@89: /*-- cannam@89: Step 3: cannam@89: The [ss] big bucket is now done. Record this fact, cannam@89: and update the quadrant descriptors. Remember to cannam@89: update quadrants in the overshoot area too, if cannam@89: necessary. The "if (i < 255)" test merely skips cannam@89: this updating for the last bucket processed, since cannam@89: updating for the last bucket is pointless. cannam@89: cannam@89: The quadrant array provides a way to incrementally cannam@89: cache sort orderings, as they appear, so as to cannam@89: make subsequent comparisons in fullGtU() complete cannam@89: faster. For repetitive blocks this makes a big cannam@89: difference (but not big enough to be able to avoid cannam@89: the fallback sorting mechanism, exponential radix sort). cannam@89: cannam@89: The precise meaning is: at all times: cannam@89: cannam@89: for 0 <= i < nblock and 0 <= j <= nblock cannam@89: cannam@89: if block[i] != block[j], cannam@89: cannam@89: then the relative values of quadrant[i] and cannam@89: quadrant[j] are meaningless. cannam@89: cannam@89: else { cannam@89: if quadrant[i] < quadrant[j] cannam@89: then the string starting at i lexicographically cannam@89: precedes the string starting at j cannam@89: cannam@89: else if quadrant[i] > quadrant[j] cannam@89: then the string starting at j lexicographically cannam@89: precedes the string starting at i cannam@89: cannam@89: else cannam@89: the relative ordering of the strings starting cannam@89: at i and j has not yet been determined. cannam@89: } cannam@89: --*/ cannam@89: bigDone[ss] = True; cannam@89: cannam@89: if (i < 255) { cannam@89: Int32 bbStart = ftab[ss << 8] & CLEARMASK; cannam@89: Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; cannam@89: Int32 shifts = 0; cannam@89: cannam@89: while ((bbSize >> shifts) > 65534) shifts++; cannam@89: cannam@89: for (j = bbSize-1; j >= 0; j--) { cannam@89: Int32 a2update = ptr[bbStart + j]; cannam@89: UInt16 qVal = (UInt16)(j >> shifts); cannam@89: quadrant[a2update] = qVal; cannam@89: if (a2update < BZ_N_OVERSHOOT) cannam@89: quadrant[a2update + nblock] = qVal; cannam@89: } cannam@89: AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); cannam@89: } cannam@89: cannam@89: } cannam@89: cannam@89: if (verb >= 4) cannam@89: VPrintf3 ( " %d pointers, %d sorted, %d scanned\n", cannam@89: nblock, numQSorted, nblock - numQSorted ); cannam@89: } cannam@89: cannam@89: #undef BIGFREQ cannam@89: #undef SETMASK cannam@89: #undef CLEARMASK cannam@89: cannam@89: cannam@89: /*---------------------------------------------*/ cannam@89: /* Pre: cannam@89: nblock > 0 cannam@89: arr2 exists for [0 .. nblock-1 +N_OVERSHOOT] cannam@89: ((UChar*)arr2) [0 .. nblock-1] holds block cannam@89: arr1 exists for [0 .. nblock-1] cannam@89: cannam@89: Post: cannam@89: ((UChar*)arr2) [0 .. nblock-1] holds block cannam@89: All other areas of block destroyed cannam@89: ftab [ 0 .. 65536 ] destroyed cannam@89: arr1 [0 .. nblock-1] holds sorted order cannam@89: */ cannam@89: void BZ2_blockSort ( EState* s ) cannam@89: { cannam@89: UInt32* ptr = s->ptr; cannam@89: UChar* block = s->block; cannam@89: UInt32* ftab = s->ftab; cannam@89: Int32 nblock = s->nblock; cannam@89: Int32 verb = s->verbosity; cannam@89: Int32 wfact = s->workFactor; cannam@89: UInt16* quadrant; cannam@89: Int32 budget; cannam@89: Int32 budgetInit; cannam@89: Int32 i; cannam@89: cannam@89: if (nblock < 10000) { cannam@89: fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); cannam@89: } else { cannam@89: /* Calculate the location for quadrant, remembering to get cannam@89: the alignment right. Assumes that &(block[0]) is at least cannam@89: 2-byte aligned -- this should be ok since block is really cannam@89: the first section of arr2. cannam@89: */ cannam@89: i = nblock+BZ_N_OVERSHOOT; cannam@89: if (i & 1) i++; cannam@89: quadrant = (UInt16*)(&(block[i])); cannam@89: cannam@89: /* (wfact-1) / 3 puts the default-factor-30 cannam@89: transition point at very roughly the same place as cannam@89: with v0.1 and v0.9.0. cannam@89: Not that it particularly matters any more, since the cannam@89: resulting compressed stream is now the same regardless cannam@89: of whether or not we use the main sort or fallback sort. cannam@89: */ cannam@89: if (wfact < 1 ) wfact = 1; cannam@89: if (wfact > 100) wfact = 100; cannam@89: budgetInit = nblock * ((wfact-1) / 3); cannam@89: budget = budgetInit; cannam@89: cannam@89: mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); cannam@89: if (verb >= 3) cannam@89: VPrintf3 ( " %d work, %d block, ratio %5.2f\n", cannam@89: budgetInit - budget, cannam@89: nblock, cannam@89: (float)(budgetInit - budget) / cannam@89: (float)(nblock==0 ? 1 : nblock) ); cannam@89: if (budget < 0) { cannam@89: if (verb >= 2) cannam@89: VPrintf0 ( " too repetitive; using fallback" cannam@89: " sorting algorithm\n" ); cannam@89: fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); cannam@89: } cannam@89: } cannam@89: cannam@89: s->origPtr = -1; cannam@89: for (i = 0; i < s->nblock; i++) cannam@89: if (ptr[i] == 0) cannam@89: { s->origPtr = i; break; }; cannam@89: cannam@89: AssertH( s->origPtr != -1, 1003 ); cannam@89: } cannam@89: cannam@89: cannam@89: /*-------------------------------------------------------------*/ cannam@89: /*--- end blocksort.c ---*/ cannam@89: /*-------------------------------------------------------------*/