1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include "bzlib_private.h"
63#include <log.h>
64
65
66
67
68
69
70
71static
72__inline__
73void fallbackSimpleSort ( UInt32* fmap,
74 UInt32* eclass,
75 Int32 lo,
76 Int32 hi )
77{
78 Int32 i, j, tmp;
79 UInt32 ec_tmp;
80
81 if (lo == hi) return;
82
83 if (hi - lo > 3) {
84 for ( i = hi-4; i >= lo; i-- ) {
85 tmp = fmap[i];
86 ec_tmp = eclass[tmp];
87 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
88 fmap[j-4] = fmap[j];
89 fmap[j-4] = tmp;
90 }
91 }
92
93 for ( i = hi-1; i >= lo; i-- ) {
94 tmp = fmap[i];
95 ec_tmp = eclass[tmp];
96 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
97 fmap[j-1] = fmap[j];
98 fmap[j-1] = tmp;
99 }
100}
101
102
103
104#define fswap(zz1, zz2) \
105 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
106
107#define fvswap(zzp1, zzp2, zzn) \
108{ \
109 Int32 yyp1 = (zzp1); \
110 Int32 yyp2 = (zzp2); \
111 Int32 yyn = (zzn); \
112 while (yyn > 0) { \
113 fswap(fmap[yyp1], fmap[yyp2]); \
114 yyp1++; yyp2++; yyn--; \
115 } \
116}
117
118
119#define fmin(a,b) ((a) < (b)) ? (a) : (b)
120
121#define fpush(lz,hz) { stackLo[sp] = lz; \
122 stackHi[sp] = hz; \
123 sp++; }
124
125#define fpop(lz,hz) { sp--; \
126 lz = stackLo[sp]; \
127 hz = stackHi[sp]; }
128
129#define FALLBACK_QSORT_SMALL_THRESH 10
130#define FALLBACK_QSORT_STACK_SIZE 100
131
132
133static
134void fallbackQSort3 ( UInt32* fmap,
135 UInt32* eclass,
136 Int32 loSt,
137 Int32 hiSt )
138{
139 Int32 unLo, unHi, ltLo, gtHi, n, m;
140 Int32 sp, lo, hi;
141 UInt32 med, r, r3;
142 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
143 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
144
145 r = 0;
146
147 sp = 0;
148 fpush ( loSt, hiSt );
149
150 while (sp > 0) {
151
152 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
153
154 fpop ( lo, hi );
155 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
156 fallbackSimpleSort ( fmap, eclass, lo, hi );
157 continue;
158 }
159
160
161
162
163
164
165
166
167 r = ((r * 7621) + 1) % 32768;
168 r3 = r % 3;
169 if (r3 == 0) med = eclass[fmap[lo]]; else
170 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
171 med = eclass[fmap[hi]];
172
173 unLo = ltLo = lo;
174 unHi = gtHi = hi;
175
176 while (1) {
177 while (1) {
178 if (unLo > unHi) break;
179 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
180 if (n == 0) {
181 fswap(fmap[unLo], fmap[ltLo]);
182 ltLo++; unLo++;
183 continue;
184 };
185 if (n > 0) break;
186 unLo++;
187 }
188 while (1) {
189 if (unLo > unHi) break;
190 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
191 if (n == 0) {
192 fswap(fmap[unHi], fmap[gtHi]);
193 gtHi--; unHi--;
194 continue;
195 };
196 if (n < 0) break;
197 unHi--;
198 }
199 if (unLo > unHi) break;
200 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
201 }
202
203 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
204
205 if (gtHi < ltLo) continue;
206
207 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
208 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
209
210 n = lo + unLo - ltLo - 1;
211 m = hi - (gtHi - unHi) + 1;
212
213 if (n - lo > hi - m) {
214 fpush ( lo, n );
215 fpush ( m, hi );
216 } else {
217 fpush ( m, hi );
218 fpush ( lo, n );
219 }
220 }
221}
222
223#undef fmin
224#undef fpush
225#undef fpop
226#undef fswap
227#undef fvswap
228#undef FALLBACK_QSORT_SMALL_THRESH
229#undef FALLBACK_QSORT_STACK_SIZE
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
247#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
248#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
249#define WORD_BH(zz) bhtab[(zz) >> 5]
250#define UNALIGNED_BH(zz) ((zz) & 0x01f)
251
252static
253void fallbackSort ( UInt32* fmap,
254 UInt32* eclass,
255 UInt32* bhtab,
256 Int32 nblock,
257 Int32 verb )
258{
259 Int32 ftab[257];
260 Int32 ftabCopy[256];
261 Int32 H, i, j, k, l, r, cc, cc1;
262 Int32 nNotDone;
263 Int32 nBhtab;
264 UChar* eclass8 = (UChar*)eclass;
265
266
267
268
269
270 if (verb >= 4)
271 VPrintf0 ( " bucket sorting ...\n" );
272 for (i = 0; i < 257; i++) ftab[i] = 0;
273 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
274 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
275 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
276
277 for (i = 0; i < nblock; i++) {
278 j = eclass8[i];
279 k = ftab[j] - 1;
280 ftab[j] = k;
281 fmap[k] = i;
282 }
283
284 nBhtab = 2 + (nblock / 32);
285 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
286 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
287
288
289
290
291
292
293
294
295 for (i = 0; i < 32; i++) {
296 SET_BH(nblock + 2*i);
297 CLEAR_BH(nblock + 2*i + 1);
298 }
299
300
301 H = 1;
302 while (1) {
303
304 if (verb >= 4)
305 VPrintf1 ( " depth %6d has ", H );
306
307 j = 0;
308 for (i = 0; i < nblock; i++) {
309 if (ISSET_BH(i)) j = i;
310 k = fmap[i] - H; if (k < 0) k += nblock;
311 eclass[k] = j;
312 }
313
314 nNotDone = 0;
315 r = -1;
316 while (1) {
317
318
319 k = r + 1;
320 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
321 if (ISSET_BH(k)) {
322 while (WORD_BH(k) == 0xffffffff) k += 32;
323 while (ISSET_BH(k)) k++;
324 }
325 l = k - 1;
326 if (l >= nblock) break;
327 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
328 if (!ISSET_BH(k)) {
329 while (WORD_BH(k) == 0x00000000) k += 32;
330 while (!ISSET_BH(k)) k++;
331 }
332 r = k - 1;
333 if (r >= nblock) break;
334
335
336 if (r > l) {
337 nNotDone += (r - l + 1);
338 fallbackQSort3 ( fmap, eclass, l, r );
339
340
341 cc = -1;
342 for (i = l; i <= r; i++) {
343 cc1 = eclass[fmap[i]];
344 if (cc != cc1) { SET_BH(i); cc = cc1; };
345 }
346 }
347 }
348
349 if (verb >= 4)
350 VPrintf1 ( "%6d unresolved strings\n", nNotDone );
351
352 H *= 2;
353 if (H > nblock || nNotDone == 0) break;
354 }
355
356
357
358
359
360
361 if (verb >= 4)
362 VPrintf0 ( " reconstructing block ...\n" );
363 j = 0;
364 for (i = 0; i < nblock; i++) {
365 while (ftabCopy[j] == 0) j++;
366 ftabCopy[j]--;
367 eclass8[fmap[i]] = (UChar)j;
368 }
369 AssertH ( j < 256, 1005 );
370}
371
372#undef SET_BH
373#undef CLEAR_BH
374#undef ISSET_BH
375#undef WORD_BH
376#undef UNALIGNED_BH
377
378
379
380
381
382
383
384
385
386static
387__inline__
388Bool mainGtU ( UInt32 i1,
389 UInt32 i2,
390 UChar* block,
391 UInt16* quadrant,
392 UInt32 nblock,
393 Int32* budget )
394{
395 Int32 k;
396 UChar c1, c2;
397 UInt16 s1, s2;
398
399 AssertD ( i1 != i2, "mainGtU" );
400
401 c1 = block[i1]; c2 = block[i2];
402 if (c1 != c2) return (c1 > c2);
403 i1++; i2++;
404
405 c1 = block[i1]; c2 = block[i2];
406 if (c1 != c2) return (c1 > c2);
407 i1++; i2++;
408
409 c1 = block[i1]; c2 = block[i2];
410 if (c1 != c2) return (c1 > c2);
411 i1++; i2++;
412
413 c1 = block[i1]; c2 = block[i2];
414 if (c1 != c2) return (c1 > c2);
415 i1++; i2++;
416
417 c1 = block[i1]; c2 = block[i2];
418 if (c1 != c2) return (c1 > c2);
419 i1++; i2++;
420
421 c1 = block[i1]; c2 = block[i2];
422 if (c1 != c2) return (c1 > c2);
423 i1++; i2++;
424
425 c1 = block[i1]; c2 = block[i2];
426 if (c1 != c2) return (c1 > c2);
427 i1++; i2++;
428
429 c1 = block[i1]; c2 = block[i2];
430 if (c1 != c2) return (c1 > c2);
431 i1++; i2++;
432
433 c1 = block[i1]; c2 = block[i2];
434 if (c1 != c2) return (c1 > c2);
435 i1++; i2++;
436
437 c1 = block[i1]; c2 = block[i2];
438 if (c1 != c2) return (c1 > c2);
439 i1++; i2++;
440
441 c1 = block[i1]; c2 = block[i2];
442 if (c1 != c2) return (c1 > c2);
443 i1++; i2++;
444
445 c1 = block[i1]; c2 = block[i2];
446 if (c1 != c2) return (c1 > c2);
447 i1++; i2++;
448
449 k = nblock + 8;
450
451 do {
452
453 c1 = block[i1]; c2 = block[i2];
454 if (c1 != c2) return (c1 > c2);
455 s1 = quadrant[i1]; s2 = quadrant[i2];
456 if (s1 != s2) return (s1 > s2);
457 i1++; i2++;
458
459 c1 = block[i1]; c2 = block[i2];
460 if (c1 != c2) return (c1 > c2);
461 s1 = quadrant[i1]; s2 = quadrant[i2];
462 if (s1 != s2) return (s1 > s2);
463 i1++; i2++;
464
465 c1 = block[i1]; c2 = block[i2];
466 if (c1 != c2) return (c1 > c2);
467 s1 = quadrant[i1]; s2 = quadrant[i2];
468 if (s1 != s2) return (s1 > s2);
469 i1++; i2++;
470
471 c1 = block[i1]; c2 = block[i2];
472 if (c1 != c2) return (c1 > c2);
473 s1 = quadrant[i1]; s2 = quadrant[i2];
474 if (s1 != s2) return (s1 > s2);
475 i1++; i2++;
476
477 c1 = block[i1]; c2 = block[i2];
478 if (c1 != c2) return (c1 > c2);
479 s1 = quadrant[i1]; s2 = quadrant[i2];
480 if (s1 != s2) return (s1 > s2);
481 i1++; i2++;
482
483 c1 = block[i1]; c2 = block[i2];
484 if (c1 != c2) return (c1 > c2);
485 s1 = quadrant[i1]; s2 = quadrant[i2];
486 if (s1 != s2) return (s1 > s2);
487 i1++; i2++;
488
489 c1 = block[i1]; c2 = block[i2];
490 if (c1 != c2) return (c1 > c2);
491 s1 = quadrant[i1]; s2 = quadrant[i2];
492 if (s1 != s2) return (s1 > s2);
493 i1++; i2++;
494
495 c1 = block[i1]; c2 = block[i2];
496 if (c1 != c2) return (c1 > c2);
497 s1 = quadrant[i1]; s2 = quadrant[i2];
498 if (s1 != s2) return (s1 > s2);
499 i1++; i2++;
500
501 if (i1 >= nblock) i1 -= nblock;
502 if (i2 >= nblock) i2 -= nblock;
503
504 k -= 8;
505 (*budget)--;
506 }
507 while (k >= 0);
508
509 return False;
510}
511
512
513
514
515
516
517
518
519
520static
521Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
522 9841, 29524, 88573, 265720,
523 797161, 2391484 };
524
525static
526void mainSimpleSort ( UInt32* ptr,
527 UChar* block,
528 UInt16* quadrant,
529 Int32 nblock,
530 Int32 lo,
531 Int32 hi,
532 Int32 d,
533 Int32* budget )
534{
535 Int32 i, j, h, bigN, hp;
536 UInt32 v;
537
538 bigN = hi - lo + 1;
539 if (bigN < 2) return;
540
541 hp = 0;
542 while (incs[hp] < bigN) hp++;
543 hp--;
544
545 for (; hp >= 0; hp--) {
546 h = incs[hp];
547
548 i = lo + h;
549 while (True) {
550
551
552 if (i > hi) break;
553 v = ptr[i];
554 j = i;
555 while ( mainGtU (
556 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
557 ) ) {
558 ptr[j] = ptr[j-h];
559 j = j - h;
560 if (j <= (lo + h - 1)) break;
561 }
562 ptr[j] = v;
563 i++;
564
565
566 if (i > hi) break;
567 v = ptr[i];
568 j = i;
569 while ( mainGtU (
570 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
571 ) ) {
572 ptr[j] = ptr[j-h];
573 j = j - h;
574 if (j <= (lo + h - 1)) break;
575 }
576 ptr[j] = v;
577 i++;
578
579
580 if (i > hi) break;
581 v = ptr[i];
582 j = i;
583 while ( mainGtU (
584 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
585 ) ) {
586 ptr[j] = ptr[j-h];
587 j = j - h;
588 if (j <= (lo + h - 1)) break;
589 }
590 ptr[j] = v;
591 i++;
592
593 if (*budget < 0) return;
594 }
595 }
596}
597
598
599
600
601
602
603
604
605
606
607
608#define mswap(zz1, zz2) \
609 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
610
611#define mvswap(zzp1, zzp2, zzn) \
612{ \
613 Int32 yyp1 = (zzp1); \
614 Int32 yyp2 = (zzp2); \
615 Int32 yyn = (zzn); \
616 while (yyn > 0) { \
617 mswap(ptr[yyp1], ptr[yyp2]); \
618 yyp1++; yyp2++; yyn--; \
619 } \
620}
621
622static
623__inline__
624UChar mmed3 ( UChar a, UChar b, UChar c )
625{
626 UChar t;
627 if (a > b) { t = a; a = b; b = t; };
628 if (b > c) {
629 b = c;
630 if (a > b) b = a;
631 }
632 return b;
633}
634
635#define mmin(a,b) ((a) < (b)) ? (a) : (b)
636
637#define mpush(lz,hz,dz) { stackLo[sp] = lz; \
638 stackHi[sp] = hz; \
639 stackD [sp] = dz; \
640 sp++; }
641
642#define mpop(lz,hz,dz) { sp--; \
643 lz = stackLo[sp]; \
644 hz = stackHi[sp]; \
645 dz = stackD [sp]; }
646
647
648#define mnextsize(az) (nextHi[az]-nextLo[az])
649
650#define mnextswap(az,bz) \
651 { Int32 tz; \
652 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
653 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
654 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
655
656
657#define MAIN_QSORT_SMALL_THRESH 20
658#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
659#define MAIN_QSORT_STACK_SIZE 100
660
661static
662void mainQSort3 ( UInt32* ptr,
663 UChar* block,
664 UInt16* quadrant,
665 Int32 nblock,
666 Int32 loSt,
667 Int32 hiSt,
668 Int32 dSt,
669 Int32* budget )
670{
671 Int32 unLo, unHi, ltLo, gtHi, n, m, med;
672 Int32 sp, lo, hi, d;
673
674 Int32 stackLo[MAIN_QSORT_STACK_SIZE];
675 Int32 stackHi[MAIN_QSORT_STACK_SIZE];
676 Int32 stackD [MAIN_QSORT_STACK_SIZE];
677
678 Int32 nextLo[3];
679 Int32 nextHi[3];
680 Int32 nextD [3];
681
682 sp = 0;
683 mpush ( loSt, hiSt, dSt );
684
685 while (sp > 0) {
686
687 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
688
689 mpop ( lo, hi, d );
690 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
691 d > MAIN_QSORT_DEPTH_THRESH) {
692 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
693 if (*budget < 0) return;
694 continue;
695 }
696
697 med = (Int32)
698 mmed3 ( block[ptr[ lo ]+d],
699 block[ptr[ hi ]+d],
700 block[ptr[ (lo+hi)>>1 ]+d] );
701
702 unLo = ltLo = lo;
703 unHi = gtHi = hi;
704
705 while (True) {
706 while (True) {
707 if (unLo > unHi) break;
708 n = ((Int32)block[ptr[unLo]+d]) - med;
709 if (n == 0) {
710 mswap(ptr[unLo], ptr[ltLo]);
711 ltLo++; unLo++; continue;
712 };
713 if (n > 0) break;
714 unLo++;
715 }
716 while (True) {
717 if (unLo > unHi) break;
718 n = ((Int32)block[ptr[unHi]+d]) - med;
719 if (n == 0) {
720 mswap(ptr[unHi], ptr[gtHi]);
721 gtHi--; unHi--; continue;
722 };
723 if (n < 0) break;
724 unHi--;
725 }
726 if (unLo > unHi) break;
727 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
728 }
729
730 AssertD ( unHi == unLo-1, "mainQSort3(2)" );
731
732 if (gtHi < ltLo) {
733 mpush(lo, hi, d+1 );
734 continue;
735 }
736
737 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
738 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
739
740 n = lo + unLo - ltLo - 1;
741 m = hi - (gtHi - unHi) + 1;
742
743 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
744 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
745 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
746
747 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
748 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
749 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
750
751 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
752 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
753
754 mpush (nextLo[0], nextHi[0], nextD[0]);
755 mpush (nextLo[1], nextHi[1], nextD[1]);
756 mpush (nextLo[2], nextHi[2], nextD[2]);
757 }
758}
759
760#undef mswap
761#undef mvswap
762#undef mpush
763#undef mpop
764#undef mmin
765#undef mnextsize
766#undef mnextswap
767#undef MAIN_QSORT_SMALL_THRESH
768#undef MAIN_QSORT_DEPTH_THRESH
769#undef MAIN_QSORT_STACK_SIZE
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
788#define SETMASK (1 << 21)
789#define CLEARMASK (~(SETMASK))
790
791static
792void mainSort ( UInt32* ptr,
793 UChar* block,
794 UInt16* quadrant,
795 UInt32* ftab,
796 Int32 nblock,
797 Int32 verb,
798 Int32* budget )
799{
800 Int32 i, j, k, ss, sb;
801 Int32 runningOrder[256];
802 Bool bigDone[256];
803 Int32 copyStart[256];
804 Int32 copyEnd [256];
805 UChar c1;
806 Int32 numQSorted;
807 UInt16 s;
808 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
809
810
811 for (i = 65536; i >= 0; i--) ftab[i] = 0;
812
813 j = block[0] << 8;
814 i = nblock-1;
815 for (; i >= 3; i -= 4) {
816 quadrant[i] = 0;
817 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
818 ftab[j]++;
819 quadrant[i-1] = 0;
820 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
821 ftab[j]++;
822 quadrant[i-2] = 0;
823 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
824 ftab[j]++;
825 quadrant[i-3] = 0;
826 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
827 ftab[j]++;
828 }
829 for (; i >= 0; i--) {
830 quadrant[i] = 0;
831 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
832 ftab[j]++;
833 }
834
835
836 for (i = 0; i < BZ_N_OVERSHOOT; i++) {
837 block [nblock+i] = block[i];
838 quadrant[nblock+i] = 0;
839 }
840
841 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
842
843
844 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
845
846 s = block[0] << 8;
847 i = nblock-1;
848 for (; i >= 3; i -= 4) {
849 s = (s >> 8) | (block[i] << 8);
850 j = ftab[s] -1;
851 ftab[s] = j;
852 ptr[j] = i;
853 s = (s >> 8) | (block[i-1] << 8);
854 j = ftab[s] -1;
855 ftab[s] = j;
856 ptr[j] = i-1;
857 s = (s >> 8) | (block[i-2] << 8);
858 j = ftab[s] -1;
859 ftab[s] = j;
860 ptr[j] = i-2;
861 s = (s >> 8) | (block[i-3] << 8);
862 j = ftab[s] -1;
863 ftab[s] = j;
864 ptr[j] = i-3;
865 }
866 for (; i >= 0; i--) {
867 s = (s >> 8) | (block[i] << 8);
868 j = ftab[s] -1;
869 ftab[s] = j;
870 ptr[j] = i;
871 }
872
873
874
875
876
877
878 for (i = 0; i <= 255; i++) {
879 bigDone [i] = False;
880 runningOrder[i] = i;
881 }
882
883 {
884 Int32 vv;
885 Int32 h = 1;
886 do h = 3 * h + 1; while (h <= 256);
887 do {
888 h = h / 3;
889 for (i = h; i <= 255; i++) {
890 vv = runningOrder[i];
891 j = i;
892 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
893 runningOrder[j] = runningOrder[j-h];
894 j = j - h;
895 if (j <= (h - 1)) goto zero;
896 }
897 zero:
898 runningOrder[j] = vv;
899 }
900 } while (h != 1);
901 }
902
903
904
905
906
907 numQSorted = 0;
908
909 for (i = 0; i <= 255; i++) {
910
911
912
913
914
915
916
917 ss = runningOrder[i];
918
919
920
921
922
923
924
925
926
927 for (j = 0; j <= 255; j++) {
928 if (j != ss) {
929 sb = (ss << 8) + j;
930 if ( ! (ftab[sb] & SETMASK) ) {
931 Int32 lo = ftab[sb] & CLEARMASK;
932 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
933 if (hi > lo) {
934 if (verb >= 4)
935 VPrintf4 ( " qsort [0x%x, 0x%x] "
936 "done %d this %d\n",
937 ss, j, numQSorted, hi - lo + 1 );
938 mainQSort3 (
939 ptr, block, quadrant, nblock,
940 lo, hi, BZ_N_RADIX, budget
941 );
942 numQSorted += (hi - lo + 1);
943 if (*budget < 0) return;
944 }
945 }
946 ftab[sb] |= SETMASK;
947 }
948 }
949
950 AssertH ( !bigDone[ss], 1006 );
951
952
953
954
955
956
957
958
959 {
960 for (j = 0; j <= 255; j++) {
961 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
962 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
963 }
964 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
965 k = ptr[j]-1; if (k < 0) k += nblock;
966 c1 = block[k];
967 if (!bigDone[c1])
968 ptr[ copyStart[c1]++ ] = k;
969 }
970 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
971 k = ptr[j]-1; if (k < 0) k += nblock;
972 c1 = block[k];
973 if (!bigDone[c1])
974 ptr[ copyEnd[c1]-- ] = k;
975 }
976 }
977
978 AssertH ( (copyStart[ss]-1 == copyEnd[ss])
979 ||
980
981
982
983
984 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
985 1007 )
986
987 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028 bigDone[ss] = True;
1029
1030 if (i < 255) {
1031 Int32 bbStart = ftab[ss << 8] & CLEARMASK;
1032 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
1033 Int32 shifts = 0;
1034
1035 while ((bbSize >> shifts) > 65534) shifts++;
1036
1037 for (j = bbSize-1; j >= 0; j--) {
1038 Int32 a2update = ptr[bbStart + j];
1039 UInt16 qVal = (UInt16)(j >> shifts);
1040 quadrant[a2update] = qVal;
1041 if (a2update < BZ_N_OVERSHOOT)
1042 quadrant[a2update + nblock] = qVal;
1043 }
1044 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
1045 }
1046
1047 }
1048
1049 if (verb >= 4)
1050 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
1051 nblock, numQSorted, nblock - numQSorted );
1052}
1053
1054#undef BIGFREQ
1055#undef SETMASK
1056#undef CLEARMASK
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072void BZ2_blockSort ( EState* s )
1073{
1074 UInt32* ptr = s->ptr;
1075 UChar* block = s->block;
1076 UInt32* ftab = s->ftab;
1077 Int32 nblock = s->nblock;
1078 Int32 verb = s->verbosity;
1079 Int32 wfact = s->workFactor;
1080 UInt16* quadrant;
1081 Int32 budget;
1082 Int32 budgetInit;
1083 Int32 i;
1084
1085 if (nblock < 10000) {
1086 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1087 } else {
1088
1089
1090
1091
1092
1093 i = nblock+BZ_N_OVERSHOOT;
1094 if (i & 1) i++;
1095 quadrant = (UInt16*)(&(block[i]));
1096
1097
1098
1099
1100
1101
1102
1103
1104 if (wfact < 1 ) wfact = 1;
1105 if (wfact > 100) wfact = 100;
1106 budgetInit = nblock * ((wfact-1) / 3);
1107 budget = budgetInit;
1108
1109 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1110 if (verb >= 3)
1111 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1112 budgetInit - budget,
1113 nblock,
1114 (float)(budgetInit - budget) /
1115 (float)(nblock==0 ? 1 : nblock) );
1116 if (budget < 0) {
1117 if (verb >= 2)
1118 VPrintf0 ( " too repetitive; using fallback"
1119 " sorting algorithm\n" );
1120 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1121 }
1122 }
1123
1124 s->origPtr = -1;
1125 for (i = 0; i < s->nblock; i++)
1126 if (ptr[i] == 0)
1127 { s->origPtr = i; break; };
1128
1129 AssertH( s->origPtr != -1, 1003 );
1130}
1131
1132
1133
1134
1135
1136