Lines Matching +full:k +full:- +full:block
2 /*-------------------------------------------------------------*/
3 /*--- Block sorting machinery ---*/
4 /*--- blocksort.c ---*/
5 /*-------------------------------------------------------------*/
7 /* ------------------------------------------------------------------
9 lossless, block-sorting data compression.
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
19 ------------------------------------------------------------------ */
24 /*---------------------------------------------*/
25 /*--- Fallback O(N log(N)^2) sorting ---*/
26 /*--- algorithm, for repetitive blocks ---*/
27 /*---------------------------------------------*/
29 /*---------------------------------------------*/
42 if (hi - lo > 3) { in fallbackSimpleSort()
43 for ( i = hi-4; i >= lo; i-- ) { 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()
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()
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()
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()
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()
316 Reconstruct the original block in in fallbackSort()
317 eclass8 [0 .. nblock-1], since the in fallbackSort()
319 --*/ in fallbackSort()
321 VPrintf0 ( " reconstructing block ...\n" ); in fallbackSort()
325 ftabCopy[j]--; in fallbackSort()
338 /*---------------------------------------------*/
339 /*--- The main, O(N^2 log(N)) sorting ---*/
340 /*--- algorithm. Faster for "normal" ---*/
341 /*--- non-repetitive blocks. ---*/
342 /*---------------------------------------------*/
344 /*---------------------------------------------*/
349 UChar* block, in mainGtU() argument
354 Int32 k; in mainGtU() local
360 c1 = block[i1]; c2 = block[i2]; in mainGtU()
364 c1 = block[i1]; c2 = block[i2]; in mainGtU()
368 c1 = block[i1]; c2 = block[i2]; in mainGtU()
372 c1 = block[i1]; c2 = block[i2]; in mainGtU()
376 c1 = block[i1]; c2 = block[i2]; in mainGtU()
380 c1 = block[i1]; c2 = block[i2]; in mainGtU()
384 c1 = block[i1]; c2 = block[i2]; in mainGtU()
388 c1 = block[i1]; c2 = block[i2]; in mainGtU()
392 c1 = block[i1]; c2 = block[i2]; in mainGtU()
396 c1 = block[i1]; c2 = block[i2]; in mainGtU()
400 c1 = block[i1]; c2 = block[i2]; in mainGtU()
404 c1 = block[i1]; c2 = block[i2]; in mainGtU()
408 k = nblock + 8; in mainGtU()
412 c1 = block[i1]; c2 = block[i2]; in mainGtU()
418 c1 = block[i1]; c2 = block[i2]; in mainGtU()
424 c1 = block[i1]; c2 = block[i2]; in mainGtU()
430 c1 = block[i1]; c2 = block[i2]; in mainGtU()
436 c1 = block[i1]; c2 = block[i2]; in mainGtU()
442 c1 = block[i1]; c2 = block[i2]; in mainGtU()
448 c1 = block[i1]; c2 = block[i2]; in mainGtU()
454 c1 = block[i1]; c2 = block[i2]; 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 /*--
475 than Incerpi-Sedgewick here. Possibly
478 --*/
486 UChar* block, in mainSimpleSort() argument
497 bigN = hi - lo + 1; in mainSimpleSort()
502 hp--; in mainSimpleSort()
504 for (; hp >= 0; hp--) { in mainSimpleSort()
510 /*-- copy 1 --*/ 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()
524 /*-- copy 2 --*/ 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()
538 /*-- copy 3 --*/ 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()
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])
622 UChar* block, in mainQSort3() argument
646 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); in mainQSort3()
649 if (hi - lo < MAIN_QSORT_SMALL_THRESH || in mainQSort3()
651 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget ); in mainQSort3()
657 mmed3 ( block[ptr[ lo ]+d], in mainQSort3()
658 block[ptr[ hi ]+d], in mainQSort3()
659 block[ptr[ (lo+hi)>>1 ]+d] ); 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])
752 UChar* block, in mainSort() argument
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()
778 quadrant[i-1] = 0; in mainSort()
779 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8); in mainSort()
781 quadrant[i-2] = 0; in mainSort()
782 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8); in mainSort()
784 quadrant[i-3] = 0; in mainSort()
785 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8); in mainSort()
788 for (; i >= 0; i--) { in mainSort()
790 j = (j >> 8) | ( ((UInt16)block[i]) << 8); in mainSort()
794 /*-- (emphasises close relationship of block & quadrant) --*/ in mainSort()
796 block [nblock+i] = block[i]; in mainSort()
802 /*-- Complete the initial radix sort --*/ in mainSort()
803 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; in mainSort()
805 s = block[0] << 8; in mainSort()
806 i = nblock-1; in mainSort()
807 for (; i >= 3; i -= 4) { in mainSort()
808 s = (s >> 8) | (block[i] << 8); in mainSort()
809 j = ftab[s] -1; in mainSort()
812 s = (s >> 8) | (block[i-1] << 8); in mainSort()
813 j = ftab[s] -1; 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()
819 ptr[j] = i-2; in mainSort()
820 s = (s >> 8) | (block[i-3] << 8); in mainSort()
821 j = ftab[s] -1; in mainSort()
823 ptr[j] = i-3; in mainSort()
825 for (; i >= 0; i--) { in mainSort()
826 s = (s >> 8) | (block[i] << 8); in mainSort()
827 j = ftab[s] -1; in mainSort()
832 /*-- in mainSort()
836 --*/ 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()
862 /*-- in mainSort()
864 --*/ in mainSort()
870 /*-- in mainSort()
872 Basically this is a 3-step process in which we call in mainSort()
875 --*/ in mainSort()
878 /*-- in mainSort()
882 Hopefully previous pointer-scanning phases have already in mainSort()
885 --*/ in mainSort()
891 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; in mainSort()
896 ss, j, numQSorted, hi - lo + 1 ); in mainSort()
898 ptr, block, quadrant, nblock, in mainSort()
901 numQSorted += (hi - lo + 1); in mainSort()
911 /*-- in mainSort()
917 --*/ in mainSort()
921 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; 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()
948 /*-- in mainSort()
968 if block[i] != block[j], 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()
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
1027 All other areas of block destroyed
1029 arr1 [0 .. nblock-1] holds sorted order
1033 UInt32* ptr = s->ptr; in BZ2_blockSort()
1034 UChar* block = s->block; in BZ2_blockSort() local
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()
1048 the alignment right. Assumes that &(block[0]) is at least in BZ2_blockSort()
1049 2-byte aligned -- this should be ok since block is really in BZ2_blockSort()
1054 quadrant = (UInt16*)(&(block[i])); in BZ2_blockSort()
1056 /* (wfact-1) / 3 puts the default-factor-30 in BZ2_blockSort()
1065 budgetInit = nblock * ((wfact-1) / 3); in BZ2_blockSort()
1068 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); in BZ2_blockSort()
1070 VPrintf3 ( " %d work, %d block, ratio %5.2f\n", 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 /*-------------------------------------------------------------*/