Lines Matching +full:j +full:- +full:to +full:- +full:k
2 /*-------------------------------------------------------------*/
3 /*--- Block sorting machinery ---*/
4 /*--- blocksort.c ---*/
5 /*-------------------------------------------------------------*/
7 /* ------------------------------------------------------------------
9 lossless, block-sorting data compression.
12 Copyright (C) 1996-2019 Julian Seward <jseward@acm.org>
19 ------------------------------------------------------------------ */
24 /*---------------------------------------------*/
25 /*--- Fallback O(N log(N)^2) sorting ---*/
26 /*--- algorithm, for repetitive blocks ---*/
27 /*---------------------------------------------*/
29 /*---------------------------------------------*/
37 Int32 i, j, tmp; in fallbackSimpleSort() local
42 if (hi - lo > 3) { in fallbackSimpleSort()
43 for ( i = hi-4; i >= lo; i-- ) { in fallbackSimpleSort()
46 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) in fallbackSimpleSort()
47 fmap[j-4] = fmap[j]; in fallbackSimpleSort()
48 fmap[j-4] = tmp; in fallbackSimpleSort()
52 for ( i = hi-1; i >= lo; i-- ) { in fallbackSimpleSort()
55 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) in fallbackSimpleSort()
56 fmap[j-1] = fmap[j]; in fallbackSimpleSort()
57 fmap[j-1] = tmp; in fallbackSimpleSort()
62 /*---------------------------------------------*/
73 yyp1++; yyp2++; yyn--; \
84 #define fpop(lz,hz) { sp--; \
111 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 ); in fallbackQSort3()
114 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { in fallbackQSort3()
119 /* Random partitioning. Median of 3 sometimes fails to in fallbackQSort3()
120 avoid bad cases. Median of 9 seems to help but in fallbackQSort3()
121 looks rather expensive. This too seems to work but in fallbackQSort3()
138 n = (Int32)eclass[fmap[unLo]] - (Int32)med; in fallbackQSort3()
149 n = (Int32)eclass[fmap[unHi]] - (Int32)med; in fallbackQSort3()
152 gtHi--; unHi--; in fallbackQSort3()
156 unHi--; in fallbackQSort3()
159 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; in fallbackQSort3()
162 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); in fallbackQSort3()
166 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); in fallbackQSort3()
167 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); in fallbackQSort3()
169 n = lo + unLo - ltLo - 1; in fallbackQSort3()
170 m = hi - (gtHi - unHi) + 1; in fallbackQSort3()
172 if (n - lo > hi - m) { in fallbackQSort3()
191 /*---------------------------------------------*/
194 eclass exists for [0 .. nblock-1]
195 ((UChar*)eclass) [0 .. nblock-1] holds block
196 ptr exists for [0 .. nblock-1]
199 ((UChar*)eclass) [0 .. nblock-1] holds block
201 fmap [0 .. nblock-1] holds sorted order
220 Int32 H, i, j, k, l, r, cc, cc1; in fallbackSort() local
225 /*-- in fallbackSort()
226 Initial 1-char radix sort to generate in fallbackSort()
228 --*/ in fallbackSort()
234 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; in fallbackSort()
237 j = eclass8[i]; in fallbackSort()
238 k = ftab[j] - 1; in fallbackSort()
239 ftab[j] = k; in fallbackSort()
240 fmap[k] = i; in fallbackSort()
247 /*-- in fallbackSort()
248 Inductively refine the buckets. Kind-of an in fallbackSort()
250 Manber-Myers suffix array construction algorithm. in fallbackSort()
251 --*/ in fallbackSort()
253 /*-- set sentinel bits for block-end detection --*/ in fallbackSort()
259 /*-- the log(N) loop --*/ in fallbackSort()
266 j = 0; in fallbackSort()
268 if (ISSET_BH(i)) j = i; in fallbackSort()
269 k = fmap[i] - H; if (k < 0) k += nblock; in fallbackSort()
270 eclass[k] = j; in fallbackSort()
274 r = -1; in fallbackSort()
277 /*-- find the next non-singleton bucket --*/ in fallbackSort()
278 k = r + 1; in fallbackSort()
279 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; in fallbackSort()
280 if (ISSET_BH(k)) { in fallbackSort()
281 while (WORD_BH(k) == 0xffffffff) k += 32; in fallbackSort()
282 while (ISSET_BH(k)) k++; in fallbackSort()
284 l = k - 1; in fallbackSort()
286 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; in fallbackSort()
287 if (!ISSET_BH(k)) { in fallbackSort()
288 while (WORD_BH(k) == 0x00000000) k += 32; in fallbackSort()
289 while (!ISSET_BH(k)) k++; in fallbackSort()
291 r = k - 1; in fallbackSort()
294 /*-- now [l, r] bracket current bucket --*/ in fallbackSort()
296 nNotDone += (r - l + 1); in fallbackSort()
299 /*-- scan bucket and generate header bits-- */ in fallbackSort()
300 cc = -1; in fallbackSort()
315 /*-- in fallbackSort()
317 eclass8 [0 .. nblock-1], since the in fallbackSort()
319 --*/ in fallbackSort()
322 j = 0; in fallbackSort()
324 while (ftabCopy[j] == 0) j++; in fallbackSort()
325 ftabCopy[j]--; in fallbackSort()
326 eclass8[fmap[i]] = (UChar)j; in fallbackSort()
328 AssertH ( j < 256, 1005 ); in fallbackSort()
338 /*---------------------------------------------*/
339 /*--- The main, O(N^2 log(N)) sorting ---*/
340 /*--- algorithm. Faster for "normal" ---*/
341 /*--- non-repetitive blocks. ---*/
342 /*---------------------------------------------*/
344 /*---------------------------------------------*/
354 Int32 k; in mainGtU() local
408 k = nblock + 8; in mainGtU()
460 if (i1 >= nblock) i1 -= nblock; in mainGtU()
461 if (i2 >= nblock) i2 -= nblock; in mainGtU()
463 k -= 8; in mainGtU()
464 (*budget)--; in mainGtU()
466 while (k >= 0); in mainGtU()
472 /*---------------------------------------------*/
473 /*--
474 Knuth's increments seem to work better
475 than Incerpi-Sedgewick here. Possibly
476 because the number of elems to sort is
478 --*/
494 Int32 i, j, h, bigN, hp; in mainSimpleSort() local
497 bigN = hi - lo + 1; in mainSimpleSort()
502 hp--; in mainSimpleSort()
504 for (; hp >= 0; hp--) { in mainSimpleSort()
510 /*-- copy 1 --*/ in mainSimpleSort()
513 j = i; in mainSimpleSort()
515 ptr[j-h]+d, v+d, block, quadrant, nblock, budget in mainSimpleSort()
517 ptr[j] = ptr[j-h]; in mainSimpleSort()
518 j = j - h; in mainSimpleSort()
519 if (j <= (lo + h - 1)) break; in mainSimpleSort()
521 ptr[j] = v; in mainSimpleSort()
524 /*-- copy 2 --*/ in mainSimpleSort()
527 j = i; in mainSimpleSort()
529 ptr[j-h]+d, v+d, block, quadrant, nblock, budget in mainSimpleSort()
531 ptr[j] = ptr[j-h]; in mainSimpleSort()
532 j = j - h; in mainSimpleSort()
533 if (j <= (lo + h - 1)) break; in mainSimpleSort()
535 ptr[j] = v; in mainSimpleSort()
538 /*-- copy 3 --*/ in mainSimpleSort()
541 j = i; in mainSimpleSort()
543 ptr[j-h]+d, v+d, block, quadrant, nblock, budget in mainSimpleSort()
545 ptr[j] = ptr[j-h]; in mainSimpleSort()
546 j = j - h; in mainSimpleSort()
547 if (j <= (lo + h - 1)) break; in mainSimpleSort()
549 ptr[j] = v; in mainSimpleSort()
558 /*---------------------------------------------*/
559 /*--
561 an elegant 3-way quicksort for strings,
565 --*/
577 yyp1++; yyp2++; yyn--; \
601 #define mpop(lz,hz,dz) { sp--; \
607 #define mnextsize(az) (nextHi[az]-nextLo[az])
646 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); in mainQSort3()
649 if (hi - lo < MAIN_QSORT_SMALL_THRESH || in mainQSort3()
667 n = ((Int32)block[ptr[unLo]+d]) - med; in mainQSort3()
677 n = ((Int32)block[ptr[unHi]+d]) - med; in mainQSort3()
680 gtHi--; unHi--; continue; in mainQSort3()
683 unHi--; in mainQSort3()
686 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--; in mainQSort3()
689 AssertD ( unHi == unLo-1, "mainQSort3(2)" ); in mainQSort3()
696 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); in mainQSort3()
697 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); in mainQSort3()
699 n = lo + unLo - ltLo - 1; in mainQSort3()
700 m = hi - (gtHi - unHi) + 1; in mainQSort3()
704 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; in mainQSort3()
731 /*---------------------------------------------*/
734 block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
735 ((UChar*)block32) [0 .. nblock-1] holds block
736 ptr exists for [0 .. nblock-1]
739 ((UChar*)block32) [0 .. nblock-1] holds block
742 ptr [0 .. nblock-1] holds sorted order
746 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
759 Int32 i, j, k, ss, sb; in mainSort() local
769 /*-- set up the 2-byte frequency table --*/ in mainSort()
770 for (i = 65536; i >= 0; i--) ftab[i] = 0; in mainSort()
772 j = block[0] << 8; in mainSort()
773 i = nblock-1; in mainSort()
774 for (; i >= 3; i -= 4) { in mainSort()
776 j = (j >> 8) | ( ((UInt16)block[i]) << 8); in mainSort()
777 ftab[j]++; in mainSort()
778 quadrant[i-1] = 0; in mainSort()
779 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8); in mainSort()
780 ftab[j]++; in mainSort()
781 quadrant[i-2] = 0; in mainSort()
782 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8); in mainSort()
783 ftab[j]++; in mainSort()
784 quadrant[i-3] = 0; in mainSort()
785 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8); in mainSort()
786 ftab[j]++; in mainSort()
788 for (; i >= 0; i--) { in mainSort()
790 j = (j >> 8) | ( ((UInt16)block[i]) << 8); in mainSort()
791 ftab[j]++; in mainSort()
794 /*-- (emphasises close relationship of block & quadrant) --*/ in mainSort()
802 /*-- Complete the initial radix sort --*/ in mainSort()
803 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; in mainSort()
806 i = nblock-1; in mainSort()
807 for (; i >= 3; i -= 4) { in mainSort()
809 j = ftab[s] -1; in mainSort()
810 ftab[s] = j; in mainSort()
811 ptr[j] = i; in mainSort()
812 s = (s >> 8) | (block[i-1] << 8); in mainSort()
813 j = ftab[s] -1; in mainSort()
814 ftab[s] = j; in mainSort()
815 ptr[j] = i-1; in mainSort()
816 s = (s >> 8) | (block[i-2] << 8); in mainSort()
817 j = ftab[s] -1; in mainSort()
818 ftab[s] = j; in mainSort()
819 ptr[j] = i-2; in mainSort()
820 s = (s >> 8) | (block[i-3] << 8); in mainSort()
821 j = ftab[s] -1; in mainSort()
822 ftab[s] = j; in mainSort()
823 ptr[j] = i-3; in mainSort()
825 for (; i >= 0; i--) { in mainSort()
827 j = ftab[s] -1; in mainSort()
828 ftab[s] = j; in mainSort()
829 ptr[j] = i; in mainSort()
832 /*-- in mainSort()
834 Calculate the running order, from smallest to largest in mainSort()
836 --*/ in mainSort()
850 j = i; in mainSort()
851 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { in mainSort()
852 runningOrder[j] = runningOrder[j-h]; in mainSort()
853 j = j - h; in mainSort()
854 if (j <= (h - 1)) goto zero; in mainSort()
857 runningOrder[j] = vv; in mainSort()
862 /*-- in mainSort()
864 --*/ in mainSort()
870 /*-- in mainSort()
872 Basically this is a 3-step process in which we call in mainSort()
873 mainQSort3 to sort the small buckets [ss, j], but in mainSort()
874 also make a big effort to avoid the calls if we can. in mainSort()
875 --*/ in mainSort()
878 /*-- in mainSort()
881 any unsorted small buckets [ss, j], for j != ss. in mainSort()
882 Hopefully previous pointer-scanning phases have already in mainSort()
883 completed many of the small buckets [ss, j], so in mainSort()
884 we don't have to sort them at all. in mainSort()
885 --*/ in mainSort()
886 for (j = 0; j <= 255; j++) { in mainSort()
887 if (j != ss) { in mainSort()
888 sb = (ss << 8) + j; in mainSort()
891 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; in mainSort()
896 ss, j, numQSorted, hi - lo + 1 ); in mainSort()
901 numQSorted += (hi - lo + 1); in mainSort()
911 /*-- in mainSort()
913 Now scan this big bucket [ss] so as to synthesise the in mainSort()
917 --*/ in mainSort()
919 for (j = 0; j <= 255; j++) { in mainSort()
920 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK; in mainSort()
921 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; in mainSort()
923 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { in mainSort()
924 k = ptr[j]-1; if (k < 0) k += nblock; in mainSort()
925 c1 = block[k]; in mainSort()
927 ptr[ copyStart[c1]++ ] = k; in mainSort()
929 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { in mainSort()
930 k = ptr[j]-1; if (k < 0) k += nblock; in mainSort()
931 c1 = block[k]; in mainSort()
933 ptr[ copyEnd[c1]-- ] = k; in mainSort()
937 AssertH ( (copyStart[ss]-1 == copyEnd[ss]) in mainSort()
939 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. in mainSort()
943 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), in mainSort()
946 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; in mainSort()
948 /*-- in mainSort()
951 and update the quadrant descriptors. Remember to in mainSort()
957 The quadrant array provides a way to incrementally in mainSort()
958 cache sort orderings, as they appear, so as to in mainSort()
961 difference (but not big enough to be able to avoid in mainSort()
966 for 0 <= i < nblock and 0 <= j <= nblock in mainSort()
968 if block[i] != block[j], in mainSort()
971 quadrant[j] are meaningless. in mainSort()
974 if quadrant[i] < quadrant[j] in mainSort()
976 precedes the string starting at j in mainSort()
978 else if quadrant[i] > quadrant[j] in mainSort()
979 then the string starting at j lexicographically in mainSort()
984 at i and j has not yet been determined. in mainSort()
986 --*/ in mainSort()
991 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; in mainSort()
996 for (j = bbSize-1; j >= 0; j--) { in mainSort()
997 Int32 a2update = ptr[bbStart + j]; in mainSort()
998 UInt16 qVal = (UInt16)(j >> shifts); in mainSort()
1003 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); in mainSort()
1010 nblock, numQSorted, nblock - numQSorted ); in mainSort()
1018 /*---------------------------------------------*/
1021 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1022 ((UChar*)arr2) [0 .. nblock-1] holds block
1023 arr1 exists for [0 .. nblock-1]
1026 ((UChar*)arr2) [0 .. nblock-1] holds block
1029 arr1 [0 .. nblock-1] holds sorted order
1033 UInt32* ptr = s->ptr; in BZ2_blockSort()
1034 UChar* block = s->block; in BZ2_blockSort()
1035 UInt32* ftab = s->ftab; in BZ2_blockSort()
1036 Int32 nblock = s->nblock; in BZ2_blockSort()
1037 Int32 verb = s->verbosity; in BZ2_blockSort()
1038 Int32 wfact = s->workFactor; in BZ2_blockSort()
1045 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); in BZ2_blockSort()
1047 /* Calculate the location for quadrant, remembering to get in BZ2_blockSort()
1049 2-byte aligned -- this should be ok since block is really in BZ2_blockSort()
1056 /* (wfact-1) / 3 puts the default-factor-30 in BZ2_blockSort()
1065 budgetInit = nblock * ((wfact-1) / 3); in BZ2_blockSort()
1071 budgetInit - budget, in BZ2_blockSort()
1073 (float)(budgetInit - budget) / in BZ2_blockSort()
1079 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); in BZ2_blockSort()
1083 s->origPtr = -1; in BZ2_blockSort()
1084 for (i = 0; i < s->nblock; i++) in BZ2_blockSort()
1086 { s->origPtr = i; break; }; in BZ2_blockSort()
1088 AssertH( s->origPtr != -1, 1003 ); in BZ2_blockSort()
1092 /*-------------------------------------------------------------*/
1093 /*--- end blocksort.c ---*/
1094 /*-------------------------------------------------------------*/