line |
stmt |
bran |
cond |
sub |
time |
code |
1
|
|
|
|
|
|
|
2
|
|
|
|
|
|
/*-------------------------------------------------------------*/ |
3
|
|
|
|
|
|
/*--- Block sorting machinery ---*/ |
4
|
|
|
|
|
|
/*--- blocksort.c ---*/ |
5
|
|
|
|
|
|
/*-------------------------------------------------------------*/ |
6
|
|
|
|
|
|
|
7
|
|
|
|
|
|
/* ------------------------------------------------------------------ |
8
|
|
|
|
|
|
This file is part of bzip2/libbzip2, a program and library for |
9
|
|
|
|
|
|
lossless, block-sorting data compression. |
10
|
|
|
|
|
|
|
11
|
|
|
|
|
|
bzip2/libbzip2 version 1.0.6 of 6 September 2010 |
12
|
|
|
|
|
|
Copyright (C) 1996-2010 Julian Seward |
13
|
|
|
|
|
|
|
14
|
|
|
|
|
|
Please read the WARNING, DISCLAIMER and PATENTS sections in the |
15
|
|
|
|
|
|
README file. |
16
|
|
|
|
|
|
|
17
|
|
|
|
|
|
This program is released under the terms of the license contained |
18
|
|
|
|
|
|
in the file LICENSE. |
19
|
|
|
|
|
|
------------------------------------------------------------------ */ |
20
|
|
|
|
|
|
|
21
|
|
|
|
|
|
|
22
|
|
|
|
|
|
#include "bzlib_private.h" |
23
|
|
|
|
|
|
|
24
|
|
|
|
|
|
/*---------------------------------------------*/ |
25
|
|
|
|
|
|
/*--- Fallback O(N log(N)^2) sorting ---*/ |
26
|
|
|
|
|
|
/*--- algorithm, for repetitive blocks ---*/ |
27
|
|
|
|
|
|
/*---------------------------------------------*/ |
28
|
|
|
|
|
|
|
29
|
|
|
|
|
|
/*---------------------------------------------*/ |
30
|
|
|
|
|
|
static |
31
|
|
|
|
|
|
__inline__ |
32
|
|
|
|
|
|
void fallbackSimpleSort ( UInt32* fmap, |
33
|
|
|
|
|
|
UInt32* eclass, |
34
|
|
|
|
|
|
Int32 lo, |
35
|
|
|
|
|
|
Int32 hi ) |
36
|
|
|
|
|
|
{ |
37
|
|
|
|
|
|
Int32 i, j, tmp; |
38
|
|
|
|
|
|
UInt32 ec_tmp; |
39
|
|
|
|
|
|
|
40
|
298716
|
|
|
|
|
if (lo == hi) return; |
41
|
|
|
|
|
|
|
42
|
291944
|
|
|
|
|
if (hi - lo > 3) { |
43
|
487652
|
|
|
|
|
for ( i = hi-4; i >= lo; i-- ) { |
44
|
386532
|
|
|
|
|
tmp = fmap[i]; |
45
|
386532
|
|
|
|
|
ec_tmp = eclass[tmp]; |
46
|
409704
|
|
|
|
|
for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) |
47
|
23172
|
|
|
|
|
fmap[j-4] = fmap[j]; |
48
|
386532
|
|
|
|
|
fmap[j-4] = tmp; |
49
|
|
|
|
|
|
} |
50
|
|
|
|
|
|
} |
51
|
|
|
|
|
|
|
52
|
1010644
|
|
|
|
|
for ( i = hi-1; i >= lo; i-- ) { |
53
|
718700
|
|
|
|
|
tmp = fmap[i]; |
54
|
718700
|
|
|
|
|
ec_tmp = eclass[tmp]; |
55
|
809718
|
|
|
|
|
for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) |
56
|
91018
|
|
|
|
|
fmap[j-1] = fmap[j]; |
57
|
718700
|
|
|
|
|
fmap[j-1] = tmp; |
58
|
|
|
|
|
|
} |
59
|
|
|
|
|
|
} |
60
|
|
|
|
|
|
|
61
|
|
|
|
|
|
|
62
|
|
|
|
|
|
/*---------------------------------------------*/ |
63
|
|
|
|
|
|
#define fswap(zz1, zz2) \ |
64
|
|
|
|
|
|
{ Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } |
65
|
|
|
|
|
|
|
66
|
|
|
|
|
|
#define fvswap(zzp1, zzp2, zzn) \ |
67
|
|
|
|
|
|
{ \ |
68
|
|
|
|
|
|
Int32 yyp1 = (zzp1); \ |
69
|
|
|
|
|
|
Int32 yyp2 = (zzp2); \ |
70
|
|
|
|
|
|
Int32 yyn = (zzn); \ |
71
|
|
|
|
|
|
while (yyn > 0) { \ |
72
|
|
|
|
|
|
fswap(fmap[yyp1], fmap[yyp2]); \ |
73
|
|
|
|
|
|
yyp1++; yyp2++; yyn--; \ |
74
|
|
|
|
|
|
} \ |
75
|
|
|
|
|
|
} |
76
|
|
|
|
|
|
|
77
|
|
|
|
|
|
|
78
|
|
|
|
|
|
#define fmin(a,b) ((a) < (b)) ? (a) : (b) |
79
|
|
|
|
|
|
|
80
|
|
|
|
|
|
#define fpush(lz,hz) { stackLo[sp] = lz; \ |
81
|
|
|
|
|
|
stackHi[sp] = hz; \ |
82
|
|
|
|
|
|
sp++; } |
83
|
|
|
|
|
|
|
84
|
|
|
|
|
|
#define fpop(lz,hz) { sp--; \ |
85
|
|
|
|
|
|
lz = stackLo[sp]; \ |
86
|
|
|
|
|
|
hz = stackHi[sp]; } |
87
|
|
|
|
|
|
|
88
|
|
|
|
|
|
#define FALLBACK_QSORT_SMALL_THRESH 10 |
89
|
|
|
|
|
|
#define FALLBACK_QSORT_STACK_SIZE 100 |
90
|
|
|
|
|
|
|
91
|
|
|
|
|
|
|
92
|
|
|
|
|
|
static |
93
|
65994
|
|
|
|
|
void fallbackQSort3 ( UInt32* fmap, |
94
|
|
|
|
|
|
UInt32* eclass, |
95
|
|
|
|
|
|
Int32 loSt, |
96
|
|
|
|
|
|
Int32 hiSt ) |
97
|
|
|
|
|
|
{ |
98
|
|
|
|
|
|
Int32 unLo, unHi, ltLo, gtHi, n, m; |
99
|
|
|
|
|
|
Int32 sp, lo, hi; |
100
|
|
|
|
|
|
UInt32 med, r, r3; |
101
|
|
|
|
|
|
Int32 stackLo[FALLBACK_QSORT_STACK_SIZE]; |
102
|
|
|
|
|
|
Int32 stackHi[FALLBACK_QSORT_STACK_SIZE]; |
103
|
|
|
|
|
|
|
104
|
|
|
|
|
|
r = 0; |
105
|
|
|
|
|
|
|
106
|
|
|
|
|
|
sp = 0; |
107
|
65994
|
|
|
|
|
fpush ( loSt, hiSt ); |
108
|
|
|
|
|
|
|
109
|
757426
|
|
|
|
|
while (sp > 0) { |
110
|
|
|
|
|
|
|
111
|
625438
|
|
|
|
|
AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 ); |
112
|
|
|
|
|
|
|
113
|
625438
|
|
|
|
|
fpop ( lo, hi ); |
114
|
625438
|
|
|
|
|
if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { |
115
|
|
|
|
|
|
fallbackSimpleSort ( fmap, eclass, lo, hi ); |
116
|
298716
|
|
|
|
|
continue; |
117
|
|
|
|
|
|
} |
118
|
|
|
|
|
|
|
119
|
|
|
|
|
|
/* Random partitioning. Median of 3 sometimes fails to |
120
|
|
|
|
|
|
avoid bad cases. Median of 9 seems to help but |
121
|
|
|
|
|
|
looks rather expensive. This too seems to work but |
122
|
|
|
|
|
|
is cheaper. Guidance for the magic constants |
123
|
|
|
|
|
|
7621 and 32768 is taken from Sedgewick's algorithms |
124
|
|
|
|
|
|
book, chapter 35. |
125
|
|
|
|
|
|
*/ |
126
|
326722
|
|
|
|
|
r = ((r * 7621) + 1) % 32768; |
127
|
326722
|
|
|
|
|
r3 = r % 3; |
128
|
326722
|
|
|
|
|
if (r3 == 0) med = eclass[fmap[lo]]; else |
129
|
237340
|
|
|
|
|
if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else |
130
|
93674
|
|
|
|
|
med = eclass[fmap[hi]]; |
131
|
|
|
|
|
|
|
132
|
|
|
|
|
|
unLo = ltLo = lo; |
133
|
|
|
|
|
|
unHi = gtHi = hi; |
134
|
|
|
|
|
|
|
135
|
|
|
|
|
|
while (1) { |
136
|
|
|
|
|
|
while (1) { |
137
|
30587520
|
|
|
|
|
if (unLo > unHi) break; |
138
|
30450338
|
|
|
|
|
n = (Int32)eclass[fmap[unLo]] - (Int32)med; |
139
|
30450338
|
|
|
|
|
if (n == 0) { |
140
|
19078504
|
|
|
|
|
fswap(fmap[unLo], fmap[ltLo]); |
141
|
19078504
|
|
|
|
|
ltLo++; unLo++; |
142
|
19078504
|
|
|
|
|
continue; |
143
|
|
|
|
|
|
}; |
144
|
11371834
|
|
|
|
|
if (n > 0) break; |
145
|
10138810
|
|
|
|
|
unLo++; |
146
|
|
|
|
|
|
} |
147
|
|
|
|
|
|
while (1) { |
148
|
13122316
|
|
|
|
|
if (unLo > unHi) break; |
149
|
12795594
|
|
|
|
|
n = (Int32)eclass[fmap[unHi]] - (Int32)med; |
150
|
12795594
|
|
|
|
|
if (n == 0) { |
151
|
2444020
|
|
|
|
|
fswap(fmap[unHi], fmap[gtHi]); |
152
|
2444020
|
|
|
|
|
gtHi--; unHi--; |
153
|
2444020
|
|
|
|
|
continue; |
154
|
|
|
|
|
|
}; |
155
|
10351574
|
|
|
|
|
if (n < 0) break; |
156
|
9308090
|
|
|
|
|
unHi--; |
157
|
|
|
|
|
|
} |
158
|
1370206
|
|
|
|
|
if (unLo > unHi) break; |
159
|
1043484
|
|
|
|
|
fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; |
160
|
1043484
|
|
|
|
|
} |
161
|
|
|
|
|
|
|
162
|
|
|
|
|
|
AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); |
163
|
|
|
|
|
|
|
164
|
326722
|
|
|
|
|
if (gtHi < ltLo) continue; |
165
|
|
|
|
|
|
|
166
|
279722
|
|
|
|
|
n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); |
167
|
279722
|
|
|
|
|
m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); |
168
|
|
|
|
|
|
|
169
|
279722
|
|
|
|
|
n = lo + unLo - ltLo - 1; |
170
|
279722
|
|
|
|
|
m = hi - (gtHi - unHi) + 1; |
171
|
|
|
|
|
|
|
172
|
279722
|
|
|
|
|
if (n - lo > hi - m) { |
173
|
94932
|
|
|
|
|
fpush ( lo, n ); |
174
|
94932
|
|
|
|
|
fpush ( m, hi ); |
175
|
|
|
|
|
|
} else { |
176
|
184790
|
|
|
|
|
fpush ( m, hi ); |
177
|
184790
|
|
|
|
|
fpush ( lo, n ); |
178
|
|
|
|
|
|
} |
179
|
|
|
|
|
|
} |
180
|
65994
|
|
|
|
|
} |
181
|
|
|
|
|
|
|
182
|
|
|
|
|
|
#undef fmin |
183
|
|
|
|
|
|
#undef fpush |
184
|
|
|
|
|
|
#undef fpop |
185
|
|
|
|
|
|
#undef fswap |
186
|
|
|
|
|
|
#undef fvswap |
187
|
|
|
|
|
|
#undef FALLBACK_QSORT_SMALL_THRESH |
188
|
|
|
|
|
|
#undef FALLBACK_QSORT_STACK_SIZE |
189
|
|
|
|
|
|
|
190
|
|
|
|
|
|
|
191
|
|
|
|
|
|
/*---------------------------------------------*/ |
192
|
|
|
|
|
|
/* Pre: |
193
|
|
|
|
|
|
nblock > 0 |
194
|
|
|
|
|
|
eclass exists for [0 .. nblock-1] |
195
|
|
|
|
|
|
((UChar*)eclass) [0 .. nblock-1] holds block |
196
|
|
|
|
|
|
ptr exists for [0 .. nblock-1] |
197
|
|
|
|
|
|
|
198
|
|
|
|
|
|
Post: |
199
|
|
|
|
|
|
((UChar*)eclass) [0 .. nblock-1] holds block |
200
|
|
|
|
|
|
All other areas of eclass destroyed |
201
|
|
|
|
|
|
fmap [0 .. nblock-1] holds sorted order |
202
|
|
|
|
|
|
bhtab [ 0 .. 2+(nblock/32) ] destroyed |
203
|
|
|
|
|
|
*/ |
204
|
|
|
|
|
|
|
205
|
|
|
|
|
|
#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) |
206
|
|
|
|
|
|
#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) |
207
|
|
|
|
|
|
#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) |
208
|
|
|
|
|
|
#define WORD_BH(zz) bhtab[(zz) >> 5] |
209
|
|
|
|
|
|
#define UNALIGNED_BH(zz) ((zz) & 0x01f) |
210
|
|
|
|
|
|
|
211
|
|
|
|
|
|
static |
212
|
978
|
|
|
|
|
void fallbackSort ( UInt32* fmap, |
213
|
|
|
|
|
|
UInt32* eclass, |
214
|
|
|
|
|
|
UInt32* bhtab, |
215
|
|
|
|
|
|
Int32 nblock, |
216
|
|
|
|
|
|
Int32 verb ) |
217
|
|
|
|
|
|
{ |
218
|
|
|
|
|
|
Int32 ftab[257]; |
219
|
|
|
|
|
|
Int32 ftabCopy[256]; |
220
|
|
|
|
|
|
Int32 H, i, j, k, l, r, cc, cc1; |
221
|
|
|
|
|
|
Int32 nNotDone; |
222
|
|
|
|
|
|
Int32 nBhtab; |
223
|
|
|
|
|
|
UChar* eclass8 = (UChar*)eclass; |
224
|
|
|
|
|
|
|
225
|
|
|
|
|
|
/*-- |
226
|
|
|
|
|
|
Initial 1-char radix sort to generate |
227
|
|
|
|
|
|
initial fmap and initial BH bits. |
228
|
|
|
|
|
|
--*/ |
229
|
|
|
|
|
|
if (verb >= 4) |
230
|
|
|
|
|
|
VPrintf0 ( " bucket sorting ...\n" ); |
231
|
251346
|
|
|
|
|
for (i = 0; i < 257; i++) ftab[i] = 0; |
232
|
1562042
|
|
|
|
|
for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; |
233
|
250368
|
|
|
|
|
for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; |
234
|
250368
|
|
|
|
|
for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; |
235
|
|
|
|
|
|
|
236
|
1562042
|
|
|
|
|
for (i = 0; i < nblock; i++) { |
237
|
1562042
|
|
|
|
|
j = eclass8[i]; |
238
|
1562042
|
|
|
|
|
k = ftab[j] - 1; |
239
|
1562042
|
|
|
|
|
ftab[j] = k; |
240
|
1562042
|
|
|
|
|
fmap[k] = i; |
241
|
|
|
|
|
|
} |
242
|
|
|
|
|
|
|
243
|
978
|
|
|
|
|
nBhtab = 2 + (nblock / 32); |
244
|
50134
|
|
|
|
|
for (i = 0; i < nBhtab; i++) bhtab[i] = 0; |
245
|
250368
|
|
|
|
|
for (i = 0; i < 256; i++) SET_BH(ftab[i]); |
246
|
|
|
|
|
|
|
247
|
|
|
|
|
|
/*-- |
248
|
|
|
|
|
|
Inductively refine the buckets. Kind-of an |
249
|
|
|
|
|
|
"exponential radix sort" (!), inspired by the |
250
|
|
|
|
|
|
Manber-Myers suffix array construction algorithm. |
251
|
|
|
|
|
|
--*/ |
252
|
|
|
|
|
|
|
253
|
|
|
|
|
|
/*-- set sentinel bits for block-end detection --*/ |
254
|
31296
|
|
|
|
|
for (i = 0; i < 32; i++) { |
255
|
31296
|
|
|
|
|
SET_BH(nblock + 2*i); |
256
|
31296
|
|
|
|
|
CLEAR_BH(nblock + 2*i + 1); |
257
|
|
|
|
|
|
} |
258
|
|
|
|
|
|
|
259
|
|
|
|
|
|
/*-- the log(N) loop --*/ |
260
|
|
|
|
|
|
H = 1; |
261
|
|
|
|
|
|
while (1) { |
262
|
|
|
|
|
|
|
263
|
|
|
|
|
|
if (verb >= 4) |
264
|
|
|
|
|
|
VPrintf1 ( " depth %6d has ", H ); |
265
|
|
|
|
|
|
|
266
|
|
|
|
|
|
j = 0; |
267
|
23907142
|
|
|
|
|
for (i = 0; i < nblock; i++) { |
268
|
23907142
|
|
|
|
|
if (ISSET_BH(i)) j = i; |
269
|
23907142
|
|
|
|
|
k = fmap[i] - H; if (k < 0) k += nblock; |
270
|
23907142
|
|
|
|
|
eclass[k] = j; |
271
|
|
|
|
|
|
} |
272
|
|
|
|
|
|
|
273
|
|
|
|
|
|
nNotDone = 0; |
274
|
|
|
|
|
|
r = -1; |
275
|
|
|
|
|
|
while (1) { |
276
|
|
|
|
|
|
|
277
|
|
|
|
|
|
/*-- find the next non-singleton bucket --*/ |
278
|
69620
|
|
|
|
|
k = r + 1; |
279
|
124622
|
|
|
|
|
while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; |
280
|
69620
|
|
|
|
|
if (ISSET_BH(k)) { |
281
|
44212
|
|
|
|
|
while (WORD_BH(k) == 0xffffffff) k += 32; |
282
|
69478
|
|
|
|
|
while (ISSET_BH(k)) k++; |
283
|
|
|
|
|
|
} |
284
|
69620
|
|
|
|
|
l = k - 1; |
285
|
69620
|
|
|
|
|
if (l >= nblock) break; |
286
|
893440
|
|
|
|
|
while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; |
287
|
65994
|
|
|
|
|
if (!ISSET_BH(k)) { |
288
|
648794
|
|
|
|
|
while (WORD_BH(k) == 0x00000000) k += 32; |
289
|
647036
|
|
|
|
|
while (!ISSET_BH(k)) k++; |
290
|
|
|
|
|
|
} |
291
|
65994
|
|
|
|
|
r = k - 1; |
292
|
65994
|
|
|
|
|
if (r >= nblock) break; |
293
|
|
|
|
|
|
|
294
|
|
|
|
|
|
/*-- now [l, r] bracket current bucket --*/ |
295
|
65994
|
|
|
|
|
if (r > l) { |
296
|
65994
|
|
|
|
|
nNotDone += (r - l + 1); |
297
|
65994
|
|
|
|
|
fallbackQSort3 ( fmap, eclass, l, r ); |
298
|
|
|
|
|
|
|
299
|
|
|
|
|
|
/*-- scan bucket and generate header bits-- */ |
300
|
|
|
|
|
|
cc = -1; |
301
|
22367878
|
|
|
|
|
for (i = l; i <= r; i++) { |
302
|
22367878
|
|
|
|
|
cc1 = eclass[fmap[i]]; |
303
|
22367878
|
|
|
|
|
if (cc != cc1) { SET_BH(i); cc = cc1; }; |
304
|
|
|
|
|
|
} |
305
|
|
|
|
|
|
} |
306
|
|
|
|
|
|
} |
307
|
|
|
|
|
|
|
308
|
|
|
|
|
|
if (verb >= 4) |
309
|
|
|
|
|
|
VPrintf1 ( "%6d unresolved strings\n", nNotDone ); |
310
|
|
|
|
|
|
|
311
|
3626
|
|
|
|
|
H *= 2; |
312
|
3626
|
|
|
|
|
if (H > nblock || nNotDone == 0) break; |
313
|
|
|
|
|
|
} |
314
|
|
|
|
|
|
|
315
|
|
|
|
|
|
/*-- |
316
|
|
|
|
|
|
Reconstruct the original block in |
317
|
|
|
|
|
|
eclass8 [0 .. nblock-1], since the |
318
|
|
|
|
|
|
previous phase destroyed it. |
319
|
|
|
|
|
|
--*/ |
320
|
|
|
|
|
|
if (verb >= 4) |
321
|
|
|
|
|
|
VPrintf0 ( " reconstructing block ...\n" ); |
322
|
|
|
|
|
|
j = 0; |
323
|
1562042
|
|
|
|
|
for (i = 0; i < nblock; i++) { |
324
|
115966
|
|
|
|
|
while (ftabCopy[j] == 0) j++; |
325
|
1562042
|
|
|
|
|
ftabCopy[j]--; |
326
|
1562042
|
|
|
|
|
eclass8[fmap[i]] = (UChar)j; |
327
|
|
|
|
|
|
} |
328
|
978
|
|
|
|
|
AssertH ( j < 256, 1005 ); |
329
|
978
|
|
|
|
|
} |
330
|
|
|
|
|
|
|
331
|
|
|
|
|
|
#undef SET_BH |
332
|
|
|
|
|
|
#undef CLEAR_BH |
333
|
|
|
|
|
|
#undef ISSET_BH |
334
|
|
|
|
|
|
#undef WORD_BH |
335
|
|
|
|
|
|
#undef UNALIGNED_BH |
336
|
|
|
|
|
|
|
337
|
|
|
|
|
|
|
338
|
|
|
|
|
|
/*---------------------------------------------*/ |
339
|
|
|
|
|
|
/*--- The main, O(N^2 log(N)) sorting ---*/ |
340
|
|
|
|
|
|
/*--- algorithm. Faster for "normal" ---*/ |
341
|
|
|
|
|
|
/*--- non-repetitive blocks. ---*/ |
342
|
|
|
|
|
|
/*---------------------------------------------*/ |
343
|
|
|
|
|
|
|
344
|
|
|
|
|
|
/*---------------------------------------------*/ |
345
|
|
|
|
|
|
static |
346
|
|
|
|
|
|
__inline__ |
347
|
188496
|
|
|
|
|
Bool mainGtU ( UInt32 i1, |
348
|
|
|
|
|
|
UInt32 i2, |
349
|
|
|
|
|
|
UChar* block, |
350
|
|
|
|
|
|
UInt16* quadrant, |
351
|
|
|
|
|
|
UInt32 nblock, |
352
|
|
|
|
|
|
Int32* budget ) |
353
|
|
|
|
|
|
{ |
354
|
|
|
|
|
|
Int32 k; |
355
|
|
|
|
|
|
UChar c1, c2; |
356
|
|
|
|
|
|
UInt16 s1, s2; |
357
|
|
|
|
|
|
|
358
|
|
|
|
|
|
AssertD ( i1 != i2, "mainGtU" ); |
359
|
|
|
|
|
|
/* 1 */ |
360
|
188496
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
361
|
188496
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
362
|
117146
|
|
|
|
|
i1++; i2++; |
363
|
|
|
|
|
|
/* 2 */ |
364
|
117146
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
365
|
117146
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
366
|
90532
|
|
|
|
|
i1++; i2++; |
367
|
|
|
|
|
|
/* 3 */ |
368
|
90532
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
369
|
90532
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
370
|
75850
|
|
|
|
|
i1++; i2++; |
371
|
|
|
|
|
|
/* 4 */ |
372
|
75850
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
373
|
75850
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
374
|
64456
|
|
|
|
|
i1++; i2++; |
375
|
|
|
|
|
|
/* 5 */ |
376
|
64456
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
377
|
64456
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
378
|
53224
|
|
|
|
|
i1++; i2++; |
379
|
|
|
|
|
|
/* 6 */ |
380
|
53224
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
381
|
53224
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
382
|
45138
|
|
|
|
|
i1++; i2++; |
383
|
|
|
|
|
|
/* 7 */ |
384
|
45138
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
385
|
45138
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
386
|
39534
|
|
|
|
|
i1++; i2++; |
387
|
|
|
|
|
|
/* 8 */ |
388
|
39534
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
389
|
39534
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
390
|
33924
|
|
|
|
|
i1++; i2++; |
391
|
|
|
|
|
|
/* 9 */ |
392
|
33924
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
393
|
33924
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
394
|
29916
|
|
|
|
|
i1++; i2++; |
395
|
|
|
|
|
|
/* 10 */ |
396
|
29916
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
397
|
29916
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
398
|
26364
|
|
|
|
|
i1++; i2++; |
399
|
|
|
|
|
|
/* 11 */ |
400
|
26364
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
401
|
26364
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
402
|
23216
|
|
|
|
|
i1++; i2++; |
403
|
|
|
|
|
|
/* 12 */ |
404
|
23216
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
405
|
23216
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
406
|
20942
|
|
|
|
|
i1++; i2++; |
407
|
|
|
|
|
|
|
408
|
20942
|
|
|
|
|
k = nblock + 8; |
409
|
|
|
|
|
|
|
410
|
|
|
|
|
|
do { |
411
|
|
|
|
|
|
/* 1 */ |
412
|
10291466
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
413
|
10291466
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
414
|
10288748
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
415
|
10288748
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
416
|
10283666
|
|
|
|
|
i1++; i2++; |
417
|
|
|
|
|
|
/* 2 */ |
418
|
10283666
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
419
|
10283666
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
420
|
10281606
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
421
|
10281606
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
422
|
10279848
|
|
|
|
|
i1++; i2++; |
423
|
|
|
|
|
|
/* 3 */ |
424
|
10279848
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
425
|
10279848
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
426
|
10278436
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
427
|
10278436
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
428
|
10277512
|
|
|
|
|
i1++; i2++; |
429
|
|
|
|
|
|
/* 4 */ |
430
|
10277512
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
431
|
10277512
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
432
|
10276182
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
433
|
10276182
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
434
|
10275384
|
|
|
|
|
i1++; i2++; |
435
|
|
|
|
|
|
/* 5 */ |
436
|
10275384
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
437
|
10275384
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
438
|
10274290
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
439
|
10274290
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
440
|
10273780
|
|
|
|
|
i1++; i2++; |
441
|
|
|
|
|
|
/* 6 */ |
442
|
10273780
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
443
|
10273780
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
444
|
10272920
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
445
|
10272920
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
446
|
10272596
|
|
|
|
|
i1++; i2++; |
447
|
|
|
|
|
|
/* 7 */ |
448
|
10272596
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
449
|
10272596
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
450
|
10271786
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
451
|
10271786
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
452
|
10271594
|
|
|
|
|
i1++; i2++; |
453
|
|
|
|
|
|
/* 8 */ |
454
|
10271594
|
|
|
|
|
c1 = block[i1]; c2 = block[i2]; |
455
|
10271594
|
|
|
|
|
if (c1 != c2) return (c1 > c2); |
456
|
10270872
|
|
|
|
|
s1 = quadrant[i1]; s2 = quadrant[i2]; |
457
|
10270872
|
|
|
|
|
if (s1 != s2) return (s1 > s2); |
458
|
10270668
|
|
|
|
|
i1++; i2++; |
459
|
|
|
|
|
|
|
460
|
10270668
|
|
|
|
|
if (i1 >= nblock) i1 -= nblock; |
461
|
10270668
|
|
|
|
|
if (i2 >= nblock) i2 -= nblock; |
462
|
|
|
|
|
|
|
463
|
10270668
|
|
|
|
|
k -= 8; |
464
|
10270668
|
|
|
|
|
(*budget)--; |
465
|
|
|
|
|
|
} |
466
|
10270668
|
|
|
|
|
while (k >= 0); |
467
|
|
|
|
|
|
|
468
|
|
|
|
|
|
return False; |
469
|
|
|
|
|
|
} |
470
|
|
|
|
|
|
|
471
|
|
|
|
|
|
|
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 |
477
|
|
|
|
|
|
usually small, typically <= 20. |
478
|
|
|
|
|
|
--*/ |
479
|
|
|
|
|
|
static |
480
|
|
|
|
|
|
Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280, |
481
|
|
|
|
|
|
9841, 29524, 88573, 265720, |
482
|
|
|
|
|
|
797161, 2391484 }; |
483
|
|
|
|
|
|
|
484
|
|
|
|
|
|
static |
485
|
20910
|
|
|
|
|
void mainSimpleSort ( UInt32* ptr, |
486
|
|
|
|
|
|
UChar* block, |
487
|
|
|
|
|
|
UInt16* quadrant, |
488
|
|
|
|
|
|
Int32 nblock, |
489
|
|
|
|
|
|
Int32 lo, |
490
|
|
|
|
|
|
Int32 hi, |
491
|
|
|
|
|
|
Int32 d, |
492
|
|
|
|
|
|
Int32* budget ) |
493
|
|
|
|
|
|
{ |
494
|
|
|
|
|
|
Int32 i, j, h, bigN, hp; |
495
|
|
|
|
|
|
UInt32 v; |
496
|
|
|
|
|
|
|
497
|
20910
|
|
|
|
|
bigN = hi - lo + 1; |
498
|
20910
|
|
|
|
|
if (bigN < 2) return; |
499
|
|
|
|
|
|
|
500
|
|
|
|
|
|
hp = 0; |
501
|
26032
|
|
|
|
|
while (incs[hp] < bigN) hp++; |
502
|
19196
|
|
|
|
|
hp--; |
503
|
|
|
|
|
|
|
504
|
45098
|
|
|
|
|
for (; hp >= 0; hp--) { |
505
|
25918
|
|
|
|
|
h = incs[hp]; |
506
|
|
|
|
|
|
|
507
|
25918
|
|
|
|
|
i = lo + h; |
508
|
|
|
|
|
|
while (True) { |
509
|
|
|
|
|
|
|
510
|
|
|
|
|
|
/*-- copy 1 --*/ |
511
|
54846
|
|
|
|
|
if (i > hi) break; |
512
|
50322
|
|
|
|
|
v = ptr[i]; |
513
|
|
|
|
|
|
j = i; |
514
|
192670
|
|
|
|
|
while ( mainGtU ( |
515
|
71174
|
|
|
|
|
ptr[j-h]+d, v+d, block, quadrant, nblock, budget |
516
|
|
|
|
|
|
) ) { |
517
|
36796
|
|
|
|
|
ptr[j] = ptr[j-h]; |
518
|
36796
|
|
|
|
|
j = j - h; |
519
|
36796
|
|
|
|
|
if (j <= (lo + h - 1)) break; |
520
|
|
|
|
|
|
} |
521
|
50322
|
|
|
|
|
ptr[j] = v; |
522
|
50322
|
|
|
|
|
i++; |
523
|
|
|
|
|
|
|
524
|
|
|
|
|
|
/*-- copy 2 --*/ |
525
|
50322
|
|
|
|
|
if (i > hi) break; |
526
|
35496
|
|
|
|
|
v = ptr[i]; |
527
|
|
|
|
|
|
j = i; |
528
|
158196
|
|
|
|
|
while ( mainGtU ( |
529
|
61350
|
|
|
|
|
ptr[j-h]+d, v+d, block, quadrant, nblock, budget |
530
|
|
|
|
|
|
) ) { |
531
|
33872
|
|
|
|
|
ptr[j] = ptr[j-h]; |
532
|
33872
|
|
|
|
|
j = j - h; |
533
|
33872
|
|
|
|
|
if (j <= (lo + h - 1)) break; |
534
|
|
|
|
|
|
} |
535
|
35496
|
|
|
|
|
ptr[j] = v; |
536
|
35496
|
|
|
|
|
i++; |
537
|
|
|
|
|
|
|
538
|
|
|
|
|
|
/*-- copy 3 --*/ |
539
|
35496
|
|
|
|
|
if (i > hi) break; |
540
|
28944
|
|
|
|
|
v = ptr[i]; |
541
|
|
|
|
|
|
j = i; |
542
|
140888
|
|
|
|
|
while ( mainGtU ( |
543
|
55972
|
|
|
|
|
ptr[j-h]+d, v+d, block, quadrant, nblock, budget |
544
|
|
|
|
|
|
) ) { |
545
|
32374
|
|
|
|
|
ptr[j] = ptr[j-h]; |
546
|
32374
|
|
|
|
|
j = j - h; |
547
|
32374
|
|
|
|
|
if (j <= (lo + h - 1)) break; |
548
|
|
|
|
|
|
} |
549
|
28944
|
|
|
|
|
ptr[j] = v; |
550
|
28944
|
|
|
|
|
i++; |
551
|
|
|
|
|
|
|
552
|
28944
|
|
|
|
|
if (*budget < 0) return; |
553
|
|
|
|
|
|
} |
554
|
|
|
|
|
|
} |
555
|
|
|
|
|
|
} |
556
|
|
|
|
|
|
|
557
|
|
|
|
|
|
|
558
|
|
|
|
|
|
/*---------------------------------------------*/ |
559
|
|
|
|
|
|
/*-- |
560
|
|
|
|
|
|
The following is an implementation of |
561
|
|
|
|
|
|
an elegant 3-way quicksort for strings, |
562
|
|
|
|
|
|
described in a paper "Fast Algorithms for |
563
|
|
|
|
|
|
Sorting and Searching Strings", by Robert |
564
|
|
|
|
|
|
Sedgewick and Jon L. Bentley. |
565
|
|
|
|
|
|
--*/ |
566
|
|
|
|
|
|
|
567
|
|
|
|
|
|
#define mswap(zz1, zz2) \ |
568
|
|
|
|
|
|
{ Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } |
569
|
|
|
|
|
|
|
570
|
|
|
|
|
|
#define mvswap(zzp1, zzp2, zzn) \ |
571
|
|
|
|
|
|
{ \ |
572
|
|
|
|
|
|
Int32 yyp1 = (zzp1); \ |
573
|
|
|
|
|
|
Int32 yyp2 = (zzp2); \ |
574
|
|
|
|
|
|
Int32 yyn = (zzn); \ |
575
|
|
|
|
|
|
while (yyn > 0) { \ |
576
|
|
|
|
|
|
mswap(ptr[yyp1], ptr[yyp2]); \ |
577
|
|
|
|
|
|
yyp1++; yyp2++; yyn--; \ |
578
|
|
|
|
|
|
} \ |
579
|
|
|
|
|
|
} |
580
|
|
|
|
|
|
|
581
|
|
|
|
|
|
static |
582
|
|
|
|
|
|
__inline__ |
583
|
|
|
|
|
|
UChar mmed3 ( UChar a, UChar b, UChar c ) |
584
|
|
|
|
|
|
{ |
585
|
|
|
|
|
|
UChar t; |
586
|
4108
|
|
|
|
|
if (a > b) { t = a; a = b; b = t; }; |
587
|
4108
|
|
|
|
|
if (b > c) { |
588
|
|
|
|
|
|
b = c; |
589
|
1400
|
|
|
|
|
if (a > b) b = a; |
590
|
|
|
|
|
|
} |
591
|
|
|
|
|
|
return b; |
592
|
|
|
|
|
|
} |
593
|
|
|
|
|
|
|
594
|
|
|
|
|
|
#define mmin(a,b) ((a) < (b)) ? (a) : (b) |
595
|
|
|
|
|
|
|
596
|
|
|
|
|
|
#define mpush(lz,hz,dz) { stackLo[sp] = lz; \ |
597
|
|
|
|
|
|
stackHi[sp] = hz; \ |
598
|
|
|
|
|
|
stackD [sp] = dz; \ |
599
|
|
|
|
|
|
sp++; } |
600
|
|
|
|
|
|
|
601
|
|
|
|
|
|
#define mpop(lz,hz,dz) { sp--; \ |
602
|
|
|
|
|
|
lz = stackLo[sp]; \ |
603
|
|
|
|
|
|
hz = stackHi[sp]; \ |
604
|
|
|
|
|
|
dz = stackD [sp]; } |
605
|
|
|
|
|
|
|
606
|
|
|
|
|
|
|
607
|
|
|
|
|
|
#define mnextsize(az) (nextHi[az]-nextLo[az]) |
608
|
|
|
|
|
|
|
609
|
|
|
|
|
|
#define mnextswap(az,bz) \ |
610
|
|
|
|
|
|
{ Int32 tz; \ |
611
|
|
|
|
|
|
tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ |
612
|
|
|
|
|
|
tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ |
613
|
|
|
|
|
|
tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; } |
614
|
|
|
|
|
|
|
615
|
|
|
|
|
|
|
616
|
|
|
|
|
|
#define MAIN_QSORT_SMALL_THRESH 20 |
617
|
|
|
|
|
|
#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) |
618
|
|
|
|
|
|
#define MAIN_QSORT_STACK_SIZE 100 |
619
|
|
|
|
|
|
|
620
|
|
|
|
|
|
static |
621
|
14906
|
|
|
|
|
void mainQSort3 ( UInt32* ptr, |
622
|
|
|
|
|
|
UChar* block, |
623
|
|
|
|
|
|
UInt16* quadrant, |
624
|
|
|
|
|
|
Int32 nblock, |
625
|
|
|
|
|
|
Int32 loSt, |
626
|
|
|
|
|
|
Int32 hiSt, |
627
|
|
|
|
|
|
Int32 dSt, |
628
|
|
|
|
|
|
Int32* budget ) |
629
|
|
|
|
|
|
{ |
630
|
|
|
|
|
|
Int32 unLo, unHi, ltLo, gtHi, n, m, med; |
631
|
|
|
|
|
|
Int32 sp, lo, hi, d; |
632
|
|
|
|
|
|
|
633
|
|
|
|
|
|
Int32 stackLo[MAIN_QSORT_STACK_SIZE]; |
634
|
|
|
|
|
|
Int32 stackHi[MAIN_QSORT_STACK_SIZE]; |
635
|
|
|
|
|
|
Int32 stackD [MAIN_QSORT_STACK_SIZE]; |
636
|
|
|
|
|
|
|
637
|
|
|
|
|
|
Int32 nextLo[3]; |
638
|
|
|
|
|
|
Int32 nextHi[3]; |
639
|
|
|
|
|
|
Int32 nextD [3]; |
640
|
|
|
|
|
|
|
641
|
|
|
|
|
|
sp = 0; |
642
|
14906
|
|
|
|
|
mpush ( loSt, hiSt, dSt ); |
643
|
|
|
|
|
|
|
644
|
54814
|
|
|
|
|
while (sp > 0) { |
645
|
|
|
|
|
|
|
646
|
25018
|
|
|
|
|
AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); |
647
|
|
|
|
|
|
|
648
|
25018
|
|
|
|
|
mpop ( lo, hi, d ); |
649
|
50036
|
|
|
|
|
if (hi - lo < MAIN_QSORT_SMALL_THRESH || |
650
|
25018
|
|
|
|
|
d > MAIN_QSORT_DEPTH_THRESH) { |
651
|
20910
|
|
|
|
|
mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget ); |
652
|
35816
|
|
|
|
|
if (*budget < 0) return; |
653
|
20894
|
|
|
|
|
continue; |
654
|
|
|
|
|
|
} |
655
|
|
|
|
|
|
|
656
|
4108
|
|
|
|
|
med = (Int32) |
657
|
8216
|
|
|
|
|
mmed3 ( block[ptr[ lo ]+d], |
658
|
4108
|
|
|
|
|
block[ptr[ hi ]+d], |
659
|
4108
|
|
|
|
|
block[ptr[ (lo+hi)>>1 ]+d] ); |
660
|
|
|
|
|
|
|
661
|
|
|
|
|
|
unLo = ltLo = lo; |
662
|
|
|
|
|
|
unHi = gtHi = hi; |
663
|
|
|
|
|
|
|
664
|
|
|
|
|
|
while (True) { |
665
|
|
|
|
|
|
while (True) { |
666
|
2801704
|
|
|
|
|
if (unLo > unHi) break; |
667
|
2799170
|
|
|
|
|
n = ((Int32)block[ptr[unLo]+d]) - med; |
668
|
2799170
|
|
|
|
|
if (n == 0) { |
669
|
2754618
|
|
|
|
|
mswap(ptr[unLo], ptr[ltLo]); |
670
|
2754618
|
|
|
|
|
ltLo++; unLo++; continue; |
671
|
|
|
|
|
|
}; |
672
|
44552
|
|
|
|
|
if (n > 0) break; |
673
|
29832
|
|
|
|
|
unLo++; |
674
|
|
|
|
|
|
} |
675
|
|
|
|
|
|
while (True) { |
676
|
84618
|
|
|
|
|
if (unLo > unHi) break; |
677
|
80510
|
|
|
|
|
n = ((Int32)block[ptr[unHi]+d]) - med; |
678
|
80510
|
|
|
|
|
if (n == 0) { |
679
|
29460
|
|
|
|
|
mswap(ptr[unHi], ptr[gtHi]); |
680
|
29460
|
|
|
|
|
gtHi--; unHi--; continue; |
681
|
|
|
|
|
|
}; |
682
|
51050
|
|
|
|
|
if (n < 0) break; |
683
|
37904
|
|
|
|
|
unHi--; |
684
|
|
|
|
|
|
} |
685
|
17254
|
|
|
|
|
if (unLo > unHi) break; |
686
|
13146
|
|
|
|
|
mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--; |
687
|
13146
|
|
|
|
|
} |
688
|
|
|
|
|
|
|
689
|
|
|
|
|
|
AssertD ( unHi == unLo-1, "mainQSort3(2)" ); |
690
|
|
|
|
|
|
|
691
|
4108
|
|
|
|
|
if (gtHi < ltLo) { |
692
|
1106
|
|
|
|
|
mpush(lo, hi, d+1 ); |
693
|
1106
|
|
|
|
|
continue; |
694
|
|
|
|
|
|
} |
695
|
|
|
|
|
|
|
696
|
3002
|
|
|
|
|
n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); |
697
|
3002
|
|
|
|
|
m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); |
698
|
|
|
|
|
|
|
699
|
3002
|
|
|
|
|
n = lo + unLo - ltLo - 1; |
700
|
3002
|
|
|
|
|
m = hi - (gtHi - unHi) + 1; |
701
|
|
|
|
|
|
|
702
|
|
|
|
|
|
nextLo[0] = lo; nextHi[0] = n; nextD[0] = d; |
703
|
|
|
|
|
|
nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; |
704
|
3002
|
|
|
|
|
nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; |
705
|
|
|
|
|
|
|
706
|
3002
|
|
|
|
|
if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); |
707
|
3002
|
|
|
|
|
if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); |
708
|
3002
|
|
|
|
|
if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); |
709
|
|
|
|
|
|
|
710
|
|
|
|
|
|
AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" ); |
711
|
|
|
|
|
|
AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" ); |
712
|
|
|
|
|
|
|
713
|
3002
|
|
|
|
|
mpush (nextLo[0], nextHi[0], nextD[0]); |
714
|
3002
|
|
|
|
|
mpush (nextLo[1], nextHi[1], nextD[1]); |
715
|
3002
|
|
|
|
|
mpush (nextLo[2], nextHi[2], nextD[2]); |
716
|
|
|
|
|
|
} |
717
|
|
|
|
|
|
} |
718
|
|
|
|
|
|
|
719
|
|
|
|
|
|
#undef mswap |
720
|
|
|
|
|
|
#undef mvswap |
721
|
|
|
|
|
|
#undef mpush |
722
|
|
|
|
|
|
#undef mpop |
723
|
|
|
|
|
|
#undef mmin |
724
|
|
|
|
|
|
#undef mnextsize |
725
|
|
|
|
|
|
#undef mnextswap |
726
|
|
|
|
|
|
#undef MAIN_QSORT_SMALL_THRESH |
727
|
|
|
|
|
|
#undef MAIN_QSORT_DEPTH_THRESH |
728
|
|
|
|
|
|
#undef MAIN_QSORT_STACK_SIZE |
729
|
|
|
|
|
|
|
730
|
|
|
|
|
|
|
731
|
|
|
|
|
|
/*---------------------------------------------*/ |
732
|
|
|
|
|
|
/* Pre: |
733
|
|
|
|
|
|
nblock > N_OVERSHOOT |
734
|
|
|
|
|
|
block32 exists for [0 .. nblock-1 +N_OVERSHOOT] |
735
|
|
|
|
|
|
((UChar*)block32) [0 .. nblock-1] holds block |
736
|
|
|
|
|
|
ptr exists for [0 .. nblock-1] |
737
|
|
|
|
|
|
|
738
|
|
|
|
|
|
Post: |
739
|
|
|
|
|
|
((UChar*)block32) [0 .. nblock-1] holds block |
740
|
|
|
|
|
|
All other areas of block32 destroyed |
741
|
|
|
|
|
|
ftab [0 .. 65536 ] destroyed |
742
|
|
|
|
|
|
ptr [0 .. nblock-1] holds sorted order |
743
|
|
|
|
|
|
if (*budget < 0), sorting was abandoned |
744
|
|
|
|
|
|
*/ |
745
|
|
|
|
|
|
|
746
|
|
|
|
|
|
#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) |
747
|
|
|
|
|
|
#define SETMASK (1 << 21) |
748
|
|
|
|
|
|
#define CLEARMASK (~(SETMASK)) |
749
|
|
|
|
|
|
|
750
|
|
|
|
|
|
static |
751
|
24
|
|
|
|
|
void mainSort ( UInt32* ptr, |
752
|
|
|
|
|
|
UChar* block, |
753
|
|
|
|
|
|
UInt16* quadrant, |
754
|
|
|
|
|
|
UInt32* ftab, |
755
|
|
|
|
|
|
Int32 nblock, |
756
|
|
|
|
|
|
Int32 verb, |
757
|
|
|
|
|
|
Int32* budget ) |
758
|
|
|
|
|
|
{ |
759
|
|
|
|
|
|
Int32 i, j, k, ss, sb; |
760
|
|
|
|
|
|
Int32 runningOrder[256]; |
761
|
|
|
|
|
|
Bool bigDone[256]; |
762
|
|
|
|
|
|
Int32 copyStart[256]; |
763
|
|
|
|
|
|
Int32 copyEnd [256]; |
764
|
|
|
|
|
|
UChar c1; |
765
|
|
|
|
|
|
Int32 numQSorted; |
766
|
|
|
|
|
|
UInt16 s; |
767
|
|
|
|
|
|
if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" ); |
768
|
|
|
|
|
|
|
769
|
|
|
|
|
|
/*-- set up the 2-byte frequency table --*/ |
770
|
1572888
|
|
|
|
|
for (i = 65536; i >= 0; i--) ftab[i] = 0; |
771
|
|
|
|
|
|
|
772
|
24
|
|
|
|
|
j = block[0] << 8; |
773
|
24
|
|
|
|
|
i = nblock-1; |
774
|
343814
|
|
|
|
|
for (; i >= 3; i -= 4) { |
775
|
343814
|
|
|
|
|
quadrant[i] = 0; |
776
|
343814
|
|
|
|
|
j = (j >> 8) | ( ((UInt16)block[i]) << 8); |
777
|
343814
|
|
|
|
|
ftab[j]++; |
778
|
343814
|
|
|
|
|
quadrant[i-1] = 0; |
779
|
343814
|
|
|
|
|
j = (j >> 8) | ( ((UInt16)block[i-1]) << 8); |
780
|
343814
|
|
|
|
|
ftab[j]++; |
781
|
343814
|
|
|
|
|
quadrant[i-2] = 0; |
782
|
343814
|
|
|
|
|
j = (j >> 8) | ( ((UInt16)block[i-2]) << 8); |
783
|
343814
|
|
|
|
|
ftab[j]++; |
784
|
343814
|
|
|
|
|
quadrant[i-3] = 0; |
785
|
343814
|
|
|
|
|
j = (j >> 8) | ( ((UInt16)block[i-3]) << 8); |
786
|
343814
|
|
|
|
|
ftab[j]++; |
787
|
|
|
|
|
|
} |
788
|
18
|
|
|
|
|
for (; i >= 0; i--) { |
789
|
18
|
|
|
|
|
quadrant[i] = 0; |
790
|
18
|
|
|
|
|
j = (j >> 8) | ( ((UInt16)block[i]) << 8); |
791
|
18
|
|
|
|
|
ftab[j]++; |
792
|
|
|
|
|
|
} |
793
|
|
|
|
|
|
|
794
|
|
|
|
|
|
/*-- (emphasises close relationship of block & quadrant) --*/ |
795
|
816
|
|
|
|
|
for (i = 0; i < BZ_N_OVERSHOOT; i++) { |
796
|
816
|
|
|
|
|
block [nblock+i] = block[i]; |
797
|
816
|
|
|
|
|
quadrant[nblock+i] = 0; |
798
|
|
|
|
|
|
} |
799
|
|
|
|
|
|
|
800
|
|
|
|
|
|
if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" ); |
801
|
|
|
|
|
|
|
802
|
|
|
|
|
|
/*-- Complete the initial radix sort --*/ |
803
|
1572864
|
|
|
|
|
for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; |
804
|
|
|
|
|
|
|
805
|
24
|
|
|
|
|
s = block[0] << 8; |
806
|
24
|
|
|
|
|
i = nblock-1; |
807
|
343814
|
|
|
|
|
for (; i >= 3; i -= 4) { |
808
|
343814
|
|
|
|
|
s = (s >> 8) | (block[i] << 8); |
809
|
343814
|
|
|
|
|
j = ftab[s] -1; |
810
|
343814
|
|
|
|
|
ftab[s] = j; |
811
|
343814
|
|
|
|
|
ptr[j] = i; |
812
|
343814
|
|
|
|
|
s = (s >> 8) | (block[i-1] << 8); |
813
|
343814
|
|
|
|
|
j = ftab[s] -1; |
814
|
343814
|
|
|
|
|
ftab[s] = j; |
815
|
343814
|
|
|
|
|
ptr[j] = i-1; |
816
|
343814
|
|
|
|
|
s = (s >> 8) | (block[i-2] << 8); |
817
|
343814
|
|
|
|
|
j = ftab[s] -1; |
818
|
343814
|
|
|
|
|
ftab[s] = j; |
819
|
343814
|
|
|
|
|
ptr[j] = i-2; |
820
|
343814
|
|
|
|
|
s = (s >> 8) | (block[i-3] << 8); |
821
|
343814
|
|
|
|
|
j = ftab[s] -1; |
822
|
343814
|
|
|
|
|
ftab[s] = j; |
823
|
343814
|
|
|
|
|
ptr[j] = i-3; |
824
|
|
|
|
|
|
} |
825
|
18
|
|
|
|
|
for (; i >= 0; i--) { |
826
|
18
|
|
|
|
|
s = (s >> 8) | (block[i] << 8); |
827
|
18
|
|
|
|
|
j = ftab[s] -1; |
828
|
18
|
|
|
|
|
ftab[s] = j; |
829
|
18
|
|
|
|
|
ptr[j] = i; |
830
|
|
|
|
|
|
} |
831
|
|
|
|
|
|
|
832
|
|
|
|
|
|
/*-- |
833
|
|
|
|
|
|
Now ftab contains the first loc of every small bucket. |
834
|
|
|
|
|
|
Calculate the running order, from smallest to largest |
835
|
|
|
|
|
|
big bucket. |
836
|
|
|
|
|
|
--*/ |
837
|
6144
|
|
|
|
|
for (i = 0; i <= 255; i++) { |
838
|
6144
|
|
|
|
|
bigDone [i] = False; |
839
|
6144
|
|
|
|
|
runningOrder[i] = i; |
840
|
|
|
|
|
|
} |
841
|
|
|
|
|
|
|
842
|
|
|
|
|
|
{ |
843
|
|
|
|
|
|
Int32 vv; |
844
|
|
|
|
|
|
Int32 h = 1; |
845
|
120
|
|
|
|
|
do h = 3 * h + 1; while (h <= 256); |
846
|
|
|
|
|
|
do { |
847
|
120
|
|
|
|
|
h = h / 3; |
848
|
26424
|
|
|
|
|
for (i = h; i <= 255; i++) { |
849
|
26424
|
|
|
|
|
vv = runningOrder[i]; |
850
|
|
|
|
|
|
j = i; |
851
|
32728
|
|
|
|
|
while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { |
852
|
7346
|
|
|
|
|
runningOrder[j] = runningOrder[j-h]; |
853
|
7346
|
|
|
|
|
j = j - h; |
854
|
7346
|
|
|
|
|
if (j <= (h - 1)) goto zero; |
855
|
|
|
|
|
|
} |
856
|
|
|
|
|
|
zero: |
857
|
26424
|
|
|
|
|
runningOrder[j] = vv; |
858
|
|
|
|
|
|
} |
859
|
120
|
|
|
|
|
} while (h != 1); |
860
|
|
|
|
|
|
} |
861
|
|
|
|
|
|
|
862
|
|
|
|
|
|
/*-- |
863
|
|
|
|
|
|
The main sorting loop. |
864
|
|
|
|
|
|
--*/ |
865
|
|
|
|
|
|
|
866
|
|
|
|
|
|
numQSorted = 0; |
867
|
|
|
|
|
|
|
868
|
6018
|
|
|
|
|
for (i = 0; i <= 255; i++) { |
869
|
|
|
|
|
|
|
870
|
|
|
|
|
|
/*-- |
871
|
|
|
|
|
|
Process big buckets, starting with the least full. |
872
|
|
|
|
|
|
Basically this is a 3-step process in which we call |
873
|
|
|
|
|
|
mainQSort3 to sort the small buckets [ss, j], but |
874
|
|
|
|
|
|
also make a big effort to avoid the calls if we can. |
875
|
|
|
|
|
|
--*/ |
876
|
6034
|
|
|
|
|
ss = runningOrder[i]; |
877
|
|
|
|
|
|
|
878
|
|
|
|
|
|
/*-- |
879
|
|
|
|
|
|
Step 1: |
880
|
|
|
|
|
|
Complete the big bucket [ss] by quicksorting |
881
|
|
|
|
|
|
any unsorted small buckets [ss, j], for j != ss. |
882
|
|
|
|
|
|
Hopefully previous pointer-scanning phases have already |
883
|
|
|
|
|
|
completed many of the small buckets [ss, j], so |
884
|
|
|
|
|
|
we don't have to sort them at all. |
885
|
|
|
|
|
|
--*/ |
886
|
1541634
|
|
|
|
|
for (j = 0; j <= 255; j++) { |
887
|
1541650
|
|
|
|
|
if (j != ss) { |
888
|
1535620
|
|
|
|
|
sb = (ss << 8) + j; |
889
|
1535620
|
|
|
|
|
if ( ! (ftab[sb] & SETMASK) ) { |
890
|
782772
|
|
|
|
|
Int32 lo = ftab[sb] & CLEARMASK; |
891
|
782772
|
|
|
|
|
Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; |
892
|
782772
|
|
|
|
|
if (hi > lo) { |
893
|
|
|
|
|
|
if (verb >= 4) |
894
|
|
|
|
|
|
VPrintf4 ( " qsort [0x%x, 0x%x] " |
895
|
|
|
|
|
|
"done %d this %d\n", |
896
|
|
|
|
|
|
ss, j, numQSorted, hi - lo + 1 ); |
897
|
14906
|
|
|
|
|
mainQSort3 ( |
898
|
|
|
|
|
|
ptr, block, quadrant, nblock, |
899
|
|
|
|
|
|
lo, hi, BZ_N_RADIX, budget |
900
|
|
|
|
|
|
); |
901
|
|
|
|
|
|
numQSorted += (hi - lo + 1); |
902
|
14930
|
|
|
|
|
if (*budget < 0) return; |
903
|
|
|
|
|
|
} |
904
|
|
|
|
|
|
} |
905
|
1535604
|
|
|
|
|
ftab[sb] |= SETMASK; |
906
|
|
|
|
|
|
} |
907
|
|
|
|
|
|
} |
908
|
|
|
|
|
|
|
909
|
6018
|
|
|
|
|
AssertH ( !bigDone[ss], 1006 ); |
910
|
|
|
|
|
|
|
911
|
|
|
|
|
|
/*-- |
912
|
|
|
|
|
|
Step 2: |
913
|
|
|
|
|
|
Now scan this big bucket [ss] so as to synthesise the |
914
|
|
|
|
|
|
sorted order for small buckets [t, ss] for all t, |
915
|
|
|
|
|
|
including, magically, the bucket [ss,ss] too. |
916
|
|
|
|
|
|
This will avoid doing Real Work in subsequent Step 1's. |
917
|
|
|
|
|
|
--*/ |
918
|
|
|
|
|
|
{ |
919
|
1540608
|
|
|
|
|
for (j = 0; j <= 255; j++) { |
920
|
1540608
|
|
|
|
|
copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK; |
921
|
1540608
|
|
|
|
|
copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; |
922
|
|
|
|
|
|
} |
923
|
131300
|
|
|
|
|
for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { |
924
|
125282
|
|
|
|
|
k = ptr[j]-1; if (k < 0) k += nblock; |
925
|
125282
|
|
|
|
|
c1 = block[k]; |
926
|
125282
|
|
|
|
|
if (!bigDone[c1]) |
927
|
71284
|
|
|
|
|
ptr[ copyStart[c1]++ ] = k; |
928
|
|
|
|
|
|
} |
929
|
125944
|
|
|
|
|
for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { |
930
|
119926
|
|
|
|
|
k = ptr[j]-1; if (k < 0) k += nblock; |
931
|
119926
|
|
|
|
|
c1 = block[k]; |
932
|
119926
|
|
|
|
|
if (!bigDone[c1]) |
933
|
59650
|
|
|
|
|
ptr[ copyEnd[c1]-- ] = k; |
934
|
|
|
|
|
|
} |
935
|
|
|
|
|
|
} |
936
|
|
|
|
|
|
|
937
|
6018
|
|
|
|
|
AssertH ( (copyStart[ss]-1 == copyEnd[ss]) |
938
|
|
|
|
|
|
|| |
939
|
|
|
|
|
|
/* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. |
940
|
|
|
|
|
|
Necessity for this case is demonstrated by compressing |
941
|
|
|
|
|
|
a sequence of approximately 48.5 million of character |
942
|
|
|
|
|
|
251; 1.0.0/1.0.1 will then die here. */ |
943
|
|
|
|
|
|
(copyStart[ss] == 0 && copyEnd[ss] == nblock-1), |
944
|
|
|
|
|
|
1007 ) |
945
|
|
|
|
|
|
|
946
|
1540608
|
|
|
|
|
for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; |
947
|
|
|
|
|
|
|
948
|
|
|
|
|
|
/*-- |
949
|
|
|
|
|
|
Step 3: |
950
|
|
|
|
|
|
The [ss] big bucket is now done. Record this fact, |
951
|
|
|
|
|
|
and update the quadrant descriptors. Remember to |
952
|
|
|
|
|
|
update quadrants in the overshoot area too, if |
953
|
|
|
|
|
|
necessary. The "if (i < 255)" test merely skips |
954
|
|
|
|
|
|
this updating for the last bucket processed, since |
955
|
|
|
|
|
|
updating for the last bucket is pointless. |
956
|
|
|
|
|
|
|
957
|
|
|
|
|
|
The quadrant array provides a way to incrementally |
958
|
|
|
|
|
|
cache sort orderings, as they appear, so as to |
959
|
|
|
|
|
|
make subsequent comparisons in fullGtU() complete |
960
|
|
|
|
|
|
faster. For repetitive blocks this makes a big |
961
|
|
|
|
|
|
difference (but not big enough to be able to avoid |
962
|
|
|
|
|
|
the fallback sorting mechanism, exponential radix sort). |
963
|
|
|
|
|
|
|
964
|
|
|
|
|
|
The precise meaning is: at all times: |
965
|
|
|
|
|
|
|
966
|
|
|
|
|
|
for 0 <= i < nblock and 0 <= j <= nblock |
967
|
|
|
|
|
|
|
968
|
|
|
|
|
|
if block[i] != block[j], |
969
|
|
|
|
|
|
|
970
|
|
|
|
|
|
then the relative values of quadrant[i] and |
971
|
|
|
|
|
|
quadrant[j] are meaningless. |
972
|
|
|
|
|
|
|
973
|
|
|
|
|
|
else { |
974
|
|
|
|
|
|
if quadrant[i] < quadrant[j] |
975
|
|
|
|
|
|
then the string starting at i lexicographically |
976
|
|
|
|
|
|
precedes the string starting at j |
977
|
|
|
|
|
|
|
978
|
|
|
|
|
|
else if quadrant[i] > quadrant[j] |
979
|
|
|
|
|
|
then the string starting at j lexicographically |
980
|
|
|
|
|
|
precedes the string starting at i |
981
|
|
|
|
|
|
|
982
|
|
|
|
|
|
else |
983
|
|
|
|
|
|
the relative ordering of the strings starting |
984
|
|
|
|
|
|
at i and j has not yet been determined. |
985
|
|
|
|
|
|
} |
986
|
|
|
|
|
|
--*/ |
987
|
6018
|
|
|
|
|
bigDone[ss] = True; |
988
|
|
|
|
|
|
|
989
|
6018
|
|
|
|
|
if (i < 255) { |
990
|
6010
|
|
|
|
|
Int32 bbStart = ftab[ss << 8] & CLEARMASK; |
991
|
6010
|
|
|
|
|
Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; |
992
|
|
|
|
|
|
Int32 shifts = 0; |
993
|
|
|
|
|
|
|
994
|
0
|
|
|
|
|
while ((bbSize >> shifts) > 65534) shifts++; |
995
|
|
|
|
|
|
|
996
|
217472
|
|
|
|
|
for (j = bbSize-1; j >= 0; j--) { |
997
|
211462
|
|
|
|
|
Int32 a2update = ptr[bbStart + j]; |
998
|
211462
|
|
|
|
|
UInt16 qVal = (UInt16)(j >> shifts); |
999
|
211462
|
|
|
|
|
quadrant[a2update] = qVal; |
1000
|
211462
|
|
|
|
|
if (a2update < BZ_N_OVERSHOOT) |
1001
|
266
|
|
|
|
|
quadrant[a2update + nblock] = qVal; |
1002
|
|
|
|
|
|
} |
1003
|
6010
|
|
|
|
|
AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); |
1004
|
|
|
|
|
|
} |
1005
|
|
|
|
|
|
|
1006
|
|
|
|
|
|
} |
1007
|
|
|
|
|
|
|
1008
|
|
|
|
|
|
if (verb >= 4) |
1009
|
|
|
|
|
|
VPrintf3 ( " %d pointers, %d sorted, %d scanned\n", |
1010
|
|
|
|
|
|
nblock, numQSorted, nblock - numQSorted ); |
1011
|
|
|
|
|
|
} |
1012
|
|
|
|
|
|
|
1013
|
|
|
|
|
|
#undef BIGFREQ |
1014
|
|
|
|
|
|
#undef SETMASK |
1015
|
|
|
|
|
|
#undef CLEARMASK |
1016
|
|
|
|
|
|
|
1017
|
|
|
|
|
|
|
1018
|
|
|
|
|
|
/*---------------------------------------------*/ |
1019
|
|
|
|
|
|
/* Pre: |
1020
|
|
|
|
|
|
nblock > 0 |
1021
|
|
|
|
|
|
arr2 exists for [0 .. nblock-1 +N_OVERSHOOT] |
1022
|
|
|
|
|
|
((UChar*)arr2) [0 .. nblock-1] holds block |
1023
|
|
|
|
|
|
arr1 exists for [0 .. nblock-1] |
1024
|
|
|
|
|
|
|
1025
|
|
|
|
|
|
Post: |
1026
|
|
|
|
|
|
((UChar*)arr2) [0 .. nblock-1] holds block |
1027
|
|
|
|
|
|
All other areas of block destroyed |
1028
|
|
|
|
|
|
ftab [ 0 .. 65536 ] destroyed |
1029
|
|
|
|
|
|
arr1 [0 .. nblock-1] holds sorted order |
1030
|
|
|
|
|
|
*/ |
1031
|
986
|
|
|
|
|
void BZ2_blockSort ( EState* s ) |
1032
|
|
|
|
|
|
{ |
1033
|
986
|
|
|
|
|
UInt32* ptr = s->ptr; |
1034
|
986
|
|
|
|
|
UChar* block = s->block; |
1035
|
986
|
|
|
|
|
UInt32* ftab = s->ftab; |
1036
|
986
|
|
|
|
|
Int32 nblock = s->nblock; |
1037
|
|
|
|
|
|
Int32 verb = s->verbosity; |
1038
|
986
|
|
|
|
|
Int32 wfact = s->workFactor; |
1039
|
|
|
|
|
|
UInt16* quadrant; |
1040
|
|
|
|
|
|
Int32 budget; |
1041
|
|
|
|
|
|
Int32 budgetInit; |
1042
|
|
|
|
|
|
Int32 i; |
1043
|
|
|
|
|
|
|
1044
|
986
|
|
|
|
|
if (nblock < 10000) { |
1045
|
962
|
|
|
|
|
fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); |
1046
|
|
|
|
|
|
} else { |
1047
|
|
|
|
|
|
/* Calculate the location for quadrant, remembering to get |
1048
|
|
|
|
|
|
the alignment right. Assumes that &(block[0]) is at least |
1049
|
|
|
|
|
|
2-byte aligned -- this should be ok since block is really |
1050
|
|
|
|
|
|
the first section of arr2. |
1051
|
|
|
|
|
|
*/ |
1052
|
24
|
|
|
|
|
i = nblock+BZ_N_OVERSHOOT; |
1053
|
24
|
|
|
|
|
if (i & 1) i++; |
1054
|
24
|
|
|
|
|
quadrant = (UInt16*)(&(block[i])); |
1055
|
|
|
|
|
|
|
1056
|
|
|
|
|
|
/* (wfact-1) / 3 puts the default-factor-30 |
1057
|
|
|
|
|
|
transition point at very roughly the same place as |
1058
|
|
|
|
|
|
with v0.1 and v0.9.0. |
1059
|
|
|
|
|
|
Not that it particularly matters any more, since the |
1060
|
|
|
|
|
|
resulting compressed stream is now the same regardless |
1061
|
|
|
|
|
|
of whether or not we use the main sort or fallback sort. |
1062
|
|
|
|
|
|
*/ |
1063
|
24
|
|
|
|
|
if (wfact < 1 ) wfact = 1; |
1064
|
24
|
|
|
|
|
if (wfact > 100) wfact = 100; |
1065
|
24
|
|
|
|
|
budgetInit = nblock * ((wfact-1) / 3); |
1066
|
24
|
|
|
|
|
budget = budgetInit; |
1067
|
|
|
|
|
|
|
1068
|
24
|
|
|
|
|
mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); |
1069
|
|
|
|
|
|
if (verb >= 3) |
1070
|
|
|
|
|
|
VPrintf3 ( " %d work, %d block, ratio %5.2f\n", |
1071
|
|
|
|
|
|
budgetInit - budget, |
1072
|
|
|
|
|
|
nblock, |
1073
|
|
|
|
|
|
(float)(budgetInit - budget) / |
1074
|
|
|
|
|
|
(float)(nblock==0 ? 1 : nblock) ); |
1075
|
24
|
|
|
|
|
if (budget < 0) { |
1076
|
|
|
|
|
|
if (verb >= 2) |
1077
|
|
|
|
|
|
VPrintf0 ( " too repetitive; using fallback" |
1078
|
|
|
|
|
|
" sorting algorithm\n" ); |
1079
|
16
|
|
|
|
|
fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); |
1080
|
|
|
|
|
|
} |
1081
|
|
|
|
|
|
} |
1082
|
|
|
|
|
|
|
1083
|
986
|
|
|
|
|
s->origPtr = -1; |
1084
|
841968
|
|
|
|
|
for (i = 0; i < s->nblock; i++) |
1085
|
841968
|
|
|
|
|
if (ptr[i] == 0) |
1086
|
986
|
|
|
|
|
{ s->origPtr = i; break; }; |
1087
|
|
|
|
|
|
|
1088
|
986
|
|
|
|
|
AssertH( s->origPtr != -1, 1003 ); |
1089
|
986
|
|
|
|
|
} |
1090
|
|
|
|
|
|
|
1091
|
|
|
|
|
|
|
1092
|
|
|
|
|
|
/*-------------------------------------------------------------*/ |
1093
|
|
|
|
|
|
/*--- end blocksort.c ---*/ |
1094
|
|
|
|
|
|
/*-------------------------------------------------------------*/ |