1 /* { dg-skip-if "AArch64 does not support these bounds." { aarch64*-*-* } { "--param stack-clash-protection-*" } } */
2
3 /*-------------------------------------------------------------*/
4 /*--- Block sorting machinery ---*/
5 /*--- blocksort.c ---*/
6 /*-------------------------------------------------------------*/
7
8 /* ------------------------------------------------------------------
9 This file is part of bzip2/libbzip2, a program and library for
10 lossless, block-sorting data compression.
11
12 bzip2/libbzip2 version 1.0.6 of 6 September 2010
13 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
14
15 Please read the WARNING, DISCLAIMER and PATENTS sections in the
16 README file.
17
18 This program is released under the terms of the license contained
19 in the file LICENSE.
20 ------------------------------------------------------------------ */
21
22 typedef char Char;
23 typedef unsigned char Bool;
24 typedef unsigned char UChar;
25 #if __SIZEOF_INT__ == 2
26 typedef long Int32;
27 typedef unsigned long UInt32;
28 #else
29 typedef int Int32;
30 typedef unsigned int UInt32;
31 #endif
32 typedef short Int16;
33 typedef unsigned short UInt16;
34
35 #define True ((Bool)1)
36 #define False ((Bool)0)
37
38 #define BZ_M_IDLE 1
39 #define BZ_M_RUNNING 2
40 #define BZ_M_FLUSHING 3
41 #define BZ_M_FINISHING 4
42
43 #define BZ_S_OUTPUT 1
44 #define BZ_S_INPUT 2
45
46 #define BZ_N_RADIX 2
47 #define BZ_N_QSORT 12
48 #define BZ_N_SHELL 18
49 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
50
51 /*---------------------------------------------*/
52 /*--- Fallback O(N log(N)^2) sorting ---*/
53 /*--- algorithm, for repetitive blocks ---*/
54 /*---------------------------------------------*/
55
56 /*---------------------------------------------*/
57 void fallbackSimpleSort ( UInt32* fmap,
58 UInt32* eclass,
59 Int32 lo,
60 Int32 hi )
61 {
62 Int32 i, j, tmp;
63 UInt32 ec_tmp;
64
65 if (lo == hi) return;
66
67 if (hi - lo > 3) {
68 for ( i = hi-4; i >= lo; i-- ) {
69 tmp = fmap[i];
70 ec_tmp = eclass[tmp];
71 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
72 fmap[j-4] = fmap[j];
73 fmap[j-4] = tmp;
74 }
75 }
76
77 for ( i = hi-1; i >= lo; i-- ) {
78 tmp = fmap[i];
79 ec_tmp = eclass[tmp];
80 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
81 fmap[j-1] = fmap[j];
82 fmap[j-1] = tmp;
83 }
84 }
85
86
87 /*---------------------------------------------*/
88 #define fswap(zz1, zz2) \
89 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
90
91 #define fvswap(zzp1, zzp2, zzn) \
92 { \
93 Int32 yyp1 = (zzp1); \
94 Int32 yyp2 = (zzp2); \
95 Int32 yyn = (zzn); \
96 while (yyn > 0) { \
97 fswap(fmap[yyp1], fmap[yyp2]); \
98 yyp1++; yyp2++; yyn--; \
99 } \
100 }
101
102
103 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
104
105 #define fpush(lz,hz) { stackLo[sp] = lz; \
106 stackHi[sp] = hz; \
107 sp++; }
108
109 #define fpop(lz,hz) { sp--; \
110 lz = stackLo[sp]; \
111 hz = stackHi[sp]; }
112
113 #define FALLBACK_QSORT_SMALL_THRESH 10
114 #define FALLBACK_QSORT_STACK_SIZE 100
115
116
117 void fallbackQSort3 ( UInt32* fmap,
118 UInt32* eclass,
119 Int32 loSt,
120 Int32 hiSt )
121 {
122 Int32 unLo, unHi, ltLo, gtHi, n, m;
123 Int32 sp, lo, hi;
124 UInt32 med, r, r3;
125 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
126 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
127
128 r = 0;
129
130 sp = 0;
131 fpush ( loSt, hiSt );
132
133 while (sp > 0) {
134
135 fpop ( lo, hi );
136 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
137 fallbackSimpleSort ( fmap, eclass, lo, hi );
138 continue;
139 }
140
141 /* Random partitioning. Median of 3 sometimes fails to
142 avoid bad cases. Median of 9 seems to help but
143 looks rather expensive. This too seems to work but
144 is cheaper. Guidance for the magic constants
145 7621 and 32768 is taken from Sedgewick's algorithms
146 book, chapter 35.
147 */
148 r = ((r * 7621) + 1) % 32768;
149 r3 = r % 3;
150 if (r3 == 0) med = eclass[fmap[lo]]; else
151 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
152 med = eclass[fmap[hi]];
153
154 unLo = ltLo = lo;
155 unHi = gtHi = hi;
156
157 while (1) {
158 while (1) {
159 if (unLo > unHi) break;
160 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
161 if (n == 0) {
162 fswap(fmap[unLo], fmap[ltLo]);
163 ltLo++; unLo++;
164 continue;
165 };
166 if (n > 0) break;
167 unLo++;
168 }
169 while (1) {
170 if (unLo > unHi) break;
171 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
172 if (n == 0) {
173 fswap(fmap[unHi], fmap[gtHi]);
174 gtHi--; unHi--;
175 continue;
176 };
177 if (n < 0) break;
178 unHi--;
179 }
180 if (unLo > unHi) break;
181 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
182 }
183
184 if (gtHi < ltLo) continue;
185
186 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
187 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
188
189 n = lo + unLo - ltLo - 1;
190 m = hi - (gtHi - unHi) + 1;
191
192 if (n - lo > hi - m) {
193 fpush ( lo, n );
194 fpush ( m, hi );
195 } else {
196 fpush ( m, hi );
197 fpush ( lo, n );
198 }
199 }
200 }
201
202 #undef fmin
203 #undef fpush
204 #undef fpop
205 #undef fswap
206 #undef fvswap
207 #undef FALLBACK_QSORT_SMALL_THRESH
208 #undef FALLBACK_QSORT_STACK_SIZE
209
210
211 /*---------------------------------------------*/
212 /* Pre:
213 nblock > 0
214 eclass exists for [0 .. nblock-1]
215 ((UChar*)eclass) [0 .. nblock-1] holds block
216 ptr exists for [0 .. nblock-1]
217
218 Post:
219 ((UChar*)eclass) [0 .. nblock-1] holds block
220 All other areas of eclass destroyed
221 fmap [0 .. nblock-1] holds sorted order
222 bhtab [ 0 .. 2+(nblock/32) ] destroyed
223 */
224
225 #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
226 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
227 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
228 #define WORD_BH(zz) bhtab[(zz) >> 5]
229 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
230
231 void fallbackSort ( UInt32* fmap,
232 UInt32* eclass,
233 UInt32* bhtab,
234 Int32 nblock,
235 Int32 verb )
236 {
237 Int32 ftab[257];
238 Int32 ftabCopy[256];
239 Int32 H, i, j, k, l, r, cc, cc1;
240 Int32 nNotDone;
241 Int32 nBhtab;
242 UChar* eclass8 = (UChar*)eclass;
243
244 /*--
245 Initial 1-char radix sort to generate
246 initial fmap and initial BH bits.
247 --*/
248 for (i = 0; i < 257; i++) ftab[i] = 0;
249 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
250 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
251 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
252
253 for (i = 0; i < nblock; i++) {
254 j = eclass8[i];
255 k = ftab[j] - 1;
256 ftab[j] = k;
257 fmap[k] = i;
258 }
259
260 nBhtab = 2 + (nblock / 32);
261 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
262 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
263
264 /*--
265 Inductively refine the buckets. Kind-of an
266 "exponential radix sort" (!), inspired by the
267 Manber-Myers suffix array construction algorithm.
268 --*/
269
270 /*-- set sentinel bits for block-end detection --*/
271 for (i = 0; i < 32; i++) {
272 SET_BH(nblock + 2*i);
273 CLEAR_BH(nblock + 2*i + 1);
274 }
275
276 /*-- the log(N) loop --*/
277 H = 1;
278 while (1) {
279
280
281 j = 0;
282 for (i = 0; i < nblock; i++) {
283 if (ISSET_BH(i)) j = i;
284 k = fmap[i] - H; if (k < 0) k += nblock;
285 eclass[k] = j;
286 }
287
288 nNotDone = 0;
289 r = -1;
290 while (1) {
291
292 /*-- find the next non-singleton bucket --*/
293 k = r + 1;
294 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
295 if (ISSET_BH(k)) {
296 while (WORD_BH(k) == 0xffffffff) k += 32;
297 while (ISSET_BH(k)) k++;
298 }
299 l = k - 1;
300 if (l >= nblock) break;
301 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
302 if (!ISSET_BH(k)) {
303 while (WORD_BH(k) == 0x00000000) k += 32;
304 while (!ISSET_BH(k)) k++;
305 }
306 r = k - 1;
307 if (r >= nblock) break;
308
309 /*-- now [l, r] bracket current bucket --*/
310 if (r > l) {
311 nNotDone += (r - l + 1);
312 fallbackQSort3 ( fmap, eclass, l, r );
313
314 /*-- scan bucket and generate header bits-- */
315 cc = -1;
316 for (i = l; i <= r; i++) {
317 cc1 = eclass[fmap[i]];
318 if (cc != cc1) { SET_BH(i); cc = cc1; };
319 }
320 }
321 }
322
323 H *= 2;
324 if (H > nblock || nNotDone == 0) break;
325 }
326
327 /*--
328 Reconstruct the original block in
329 eclass8 [0 .. nblock-1], since the
330 previous phase destroyed it.
331 --*/
332 j = 0;
333 for (i = 0; i < nblock; i++) {
334 while (ftabCopy[j] == 0) j++;
335 ftabCopy[j]--;
336 eclass8[fmap[i]] = (UChar)j;
337 }
338 }
339
340 #undef SET_BH
341 #undef CLEAR_BH
342 #undef ISSET_BH
343 #undef WORD_BH
344 #undef UNALIGNED_BH
345
346
347 /*---------------------------------------------*/
348 /*--- The main, O(N^2 log(N)) sorting ---*/
349 /*--- algorithm. Faster for "normal" ---*/
350 /*--- non-repetitive blocks. ---*/
351 /*---------------------------------------------*/
352
353 /*---------------------------------------------*/
354 Bool mainGtU ( UInt32 i1,
355 UInt32 i2,
356 UChar* block,
357 UInt16* quadrant,
358 UInt32 nblock,
359 Int32* budget )
360 {
361 Int32 k;
362 UChar c1, c2;
363 UInt16 s1, s2;
364
365 /* 1 */
366 c1 = block[i1]; c2 = block[i2];
367 if (c1 != c2) return (c1 > c2);
368 i1++; i2++;
369 /* 2 */
370 c1 = block[i1]; c2 = block[i2];
371 if (c1 != c2) return (c1 > c2);
372 i1++; i2++;
373 /* 3 */
374 c1 = block[i1]; c2 = block[i2];
375 if (c1 != c2) return (c1 > c2);
376 i1++; i2++;
377 /* 4 */
378 c1 = block[i1]; c2 = block[i2];
379 if (c1 != c2) return (c1 > c2);
380 i1++; i2++;
381 /* 5 */
382 c1 = block[i1]; c2 = block[i2];
383 if (c1 != c2) return (c1 > c2);
384 i1++; i2++;
385 /* 6 */
386 c1 = block[i1]; c2 = block[i2];
387 if (c1 != c2) return (c1 > c2);
388 i1++; i2++;
389 /* 7 */
390 c1 = block[i1]; c2 = block[i2];
391 if (c1 != c2) return (c1 > c2);
392 i1++; i2++;
393 /* 8 */
394 c1 = block[i1]; c2 = block[i2];
395 if (c1 != c2) return (c1 > c2);
396 i1++; i2++;
397 /* 9 */
398 c1 = block[i1]; c2 = block[i2];
399 if (c1 != c2) return (c1 > c2);
400 i1++; i2++;
401 /* 10 */
402 c1 = block[i1]; c2 = block[i2];
403 if (c1 != c2) return (c1 > c2);
404 i1++; i2++;
405 /* 11 */
406 c1 = block[i1]; c2 = block[i2];
407 if (c1 != c2) return (c1 > c2);
408 i1++; i2++;
409 /* 12 */
410 c1 = block[i1]; c2 = block[i2];
411 if (c1 != c2) return (c1 > c2);
412 i1++; i2++;
413
414 k = nblock + 8;
415
416 do {
417 /* 1 */
418 c1 = block[i1]; c2 = block[i2];
419 if (c1 != c2) return (c1 > c2);
420 s1 = quadrant[i1]; s2 = quadrant[i2];
421 if (s1 != s2) return (s1 > s2);
422 i1++; i2++;
423 /* 2 */
424 c1 = block[i1]; c2 = block[i2];
425 if (c1 != c2) return (c1 > c2);
426 s1 = quadrant[i1]; s2 = quadrant[i2];
427 if (s1 != s2) return (s1 > s2);
428 i1++; i2++;
429 /* 3 */
430 c1 = block[i1]; c2 = block[i2];
431 if (c1 != c2) return (c1 > c2);
432 s1 = quadrant[i1]; s2 = quadrant[i2];
433 if (s1 != s2) return (s1 > s2);
434 i1++; i2++;
435 /* 4 */
436 c1 = block[i1]; c2 = block[i2];
437 if (c1 != c2) return (c1 > c2);
438 s1 = quadrant[i1]; s2 = quadrant[i2];
439 if (s1 != s2) return (s1 > s2);
440 i1++; i2++;
441 /* 5 */
442 c1 = block[i1]; c2 = block[i2];
443 if (c1 != c2) return (c1 > c2);
444 s1 = quadrant[i1]; s2 = quadrant[i2];
445 if (s1 != s2) return (s1 > s2);
446 i1++; i2++;
447 /* 6 */
448 c1 = block[i1]; c2 = block[i2];
449 if (c1 != c2) return (c1 > c2);
450 s1 = quadrant[i1]; s2 = quadrant[i2];
451 if (s1 != s2) return (s1 > s2);
452 i1++; i2++;
453 /* 7 */
454 c1 = block[i1]; c2 = block[i2];
455 if (c1 != c2) return (c1 > c2);
456 s1 = quadrant[i1]; s2 = quadrant[i2];
457 if (s1 != s2) return (s1 > s2);
458 i1++; i2++;
459 /* 8 */
460 c1 = block[i1]; c2 = block[i2];
461 if (c1 != c2) return (c1 > c2);
462 s1 = quadrant[i1]; s2 = quadrant[i2];
463 if (s1 != s2) return (s1 > s2);
464 i1++; i2++;
465
466 if (i1 >= nblock) i1 -= nblock;
467 if (i2 >= nblock) i2 -= nblock;
468
469 k -= 8;
470 (*budget)--;
471 }
472 while (k >= 0);
473
474 return False;
475 }
476
477
478 /*---------------------------------------------*/
479 /*--
480 Knuth's increments seem to work better
481 than Incerpi-Sedgewick here. Possibly
482 because the number of elems to sort is
483 usually small, typically <= 20.
484 --*/
485 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
486 9841, 29524, 88573, 265720,
487 797161, 2391484 };
488
489 void mainSimpleSort ( UInt32* ptr,
490 UChar* block,
491 UInt16* quadrant,
492 Int32 nblock,
493 Int32 lo,
494 Int32 hi,
495 Int32 d,
496 Int32* budget )
497 {
498 Int32 i, j, h, bigN, hp;
499 UInt32 v;
500
501 bigN = hi - lo + 1;
502 if (bigN < 2) return;
503
504 hp = 0;
505 while (incs[hp] < bigN) hp++;
506 hp--;
507
508 for (; hp >= 0; hp--) {
509 h = incs[hp];
510
511 i = lo + h;
512 while (True) {
513
514 /*-- copy 1 --*/
515 if (i > hi) break;
516 v = ptr[i];
517 j = i;
518 while ( mainGtU (
519 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
520 ) ) {
521 ptr[j] = ptr[j-h];
522 j = j - h;
523 if (j <= (lo + h - 1)) break;
524 }
525 ptr[j] = v;
526 i++;
527
528 /*-- copy 2 --*/
529 if (i > hi) break;
530 v = ptr[i];
531 j = i;
532 while ( mainGtU (
533 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
534 ) ) {
535 ptr[j] = ptr[j-h];
536 j = j - h;
537 if (j <= (lo + h - 1)) break;
538 }
539 ptr[j] = v;
540 i++;
541
542 /*-- copy 3 --*/
543 if (i > hi) break;
544 v = ptr[i];
545 j = i;
546 while ( mainGtU (
547 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
548 ) ) {
549 ptr[j] = ptr[j-h];
550 j = j - h;
551 if (j <= (lo + h - 1)) break;
552 }
553 ptr[j] = v;
554 i++;
555
556 if (*budget < 0) return;
557 }
558 }
559 }
560
561
562 /*---------------------------------------------*/
563 /*--
564 The following is an implementation of
565 an elegant 3-way quicksort for strings,
566 described in a paper "Fast Algorithms for
567 Sorting and Searching Strings", by Robert
568 Sedgewick and Jon L. Bentley.
569 --*/
570
571 #define mswap(zz1, zz2) \
572 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
573
574 #define mvswap(zzp1, zzp2, zzn) \
575 { \
576 Int32 yyp1 = (zzp1); \
577 Int32 yyp2 = (zzp2); \
578 Int32 yyn = (zzn); \
579 while (yyn > 0) { \
580 mswap(ptr[yyp1], ptr[yyp2]); \
581 yyp1++; yyp2++; yyn--; \
582 } \
583 }
584
585 UChar mmed3 ( UChar a, UChar b, UChar c )
586 {
587 UChar t;
588 if (a > b) { t = a; a = b; b = t; };
589 if (b > c) {
590 b = c;
591 if (a > b) b = a;
592 }
593 return b;
594 }
595
596 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
597
598 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
599 stackHi[sp] = hz; \
600 stackD [sp] = dz; \
601 sp++; }
602
603 #define mpop(lz,hz,dz) { sp--; \
604 lz = stackLo[sp]; \
605 hz = stackHi[sp]; \
606 dz = stackD [sp]; }
607
608
609 #define mnextsize(az) (nextHi[az]-nextLo[az])
610
611 #define mnextswap(az,bz) \
612 { Int32 tz; \
613 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
614 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
615 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
616
617
618 #define MAIN_QSORT_SMALL_THRESH 20
619 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
620 #define MAIN_QSORT_STACK_SIZE 100
621
622 void mainQSort3 ( UInt32* ptr,
623 UChar* block,
624 UInt16* quadrant,
625 Int32 nblock,
626 Int32 loSt,
627 Int32 hiSt,
628 Int32 dSt,
629 Int32* budget )
630 {
631 Int32 unLo, unHi, ltLo, gtHi, n, m, med;
632 Int32 sp, lo, hi, d;
633
634 Int32 stackLo[MAIN_QSORT_STACK_SIZE];
635 Int32 stackHi[MAIN_QSORT_STACK_SIZE];
636 Int32 stackD [MAIN_QSORT_STACK_SIZE];
637
638 Int32 nextLo[3];
639 Int32 nextHi[3];
640 Int32 nextD [3];
641
642 sp = 0;
643 mpush ( loSt, hiSt, dSt );
644
645 while (sp > 0) {
646
647 mpop ( lo, hi, d );
648 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
649 d > MAIN_QSORT_DEPTH_THRESH) {
650 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
651 if (*budget < 0) return;
652 continue;
653 }
654
655 med = (Int32)
656 mmed3 ( block[ptr[ lo ]+d],
657 block[ptr[ hi ]+d],
658 block[ptr[ (lo+hi)>>1 ]+d] );
659
660 unLo = ltLo = lo;
661 unHi = gtHi = hi;
662
663 while (True) {
664 while (True) {
665 if (unLo > unHi) break;
666 n = ((Int32)block[ptr[unLo]+d]) - med;
667 if (n == 0) {
668 mswap(ptr[unLo], ptr[ltLo]);
669 ltLo++; unLo++; continue;
670 };
671 if (n > 0) break;
672 unLo++;
673 }
674 while (True) {
675 if (unLo > unHi) break;
676 n = ((Int32)block[ptr[unHi]+d]) - med;
677 if (n == 0) {
678 mswap(ptr[unHi], ptr[gtHi]);
679 gtHi--; unHi--; continue;
680 };
681 if (n < 0) break;
682 unHi--;
683 }
684 if (unLo > unHi) break;
685 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
686 }
687
688 if (gtHi < ltLo) {
689 mpush(lo, hi, d+1 );
690 continue;
691 }
692
693 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
694 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
695
696 n = lo + unLo - ltLo - 1;
697 m = hi - (gtHi - unHi) + 1;
698
699 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
700 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
701 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
702
703 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
704 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
705 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
706
707
708 mpush (nextLo[0], nextHi[0], nextD[0]);
709 mpush (nextLo[1], nextHi[1], nextD[1]);
710 mpush (nextLo[2], nextHi[2], nextD[2]);
711 }
712 }