2 * divsufsort.c for libdivsufsort-lite
3 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
31 #include "wimlib/divsufsort.h"
32 #include "wimlib/lz_mf.h"
33 #include "wimlib/util.h"
36 #define ALPHABET_SIZE 256
37 #define BUCKET_A_SIZE (ALPHABET_SIZE)
38 #define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)
40 #define SS_INSERTIONSORT_THRESHOLD 8
42 #define SS_BLOCKSIZE 1024
44 /* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */
46 # define SS_MISORT_STACKSIZE (96)
47 #elif SS_BLOCKSIZE <= 4096
48 # define SS_MISORT_STACKSIZE (16)
50 # define SS_MISORT_STACKSIZE (24)
52 #define SS_SMERGE_STACKSIZE (32)
53 #define TR_INSERTIONSORT_THRESHOLD (8)
54 #define TR_STACKSIZE (64)
62 #define STACK_PUSH(_a, _b, _c, _d)\
64 LZ_ASSERT(ssize < STACK_SIZE);\
65 stack[ssize].a = (_a), stack[ssize].b = (_b),\
66 stack[ssize].c = (_c), stack[ssize++].d = (_d);\
68 #define STACK_PUSH5(_a, _b, _c, _d, _e)\
70 LZ_ASSERT(ssize < STACK_SIZE);\
71 stack[ssize].a = (_a), stack[ssize].b = (_b),\
72 stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\
74 #define STACK_POP(_a, _b, _c, _d)\
76 LZ_ASSERT(0 <= ssize);\
77 if(ssize == 0) { return; }\
78 (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
79 (_c) = stack[ssize].c, (_d) = stack[ssize].d;\
81 #define STACK_POP5(_a, _b, _c, _d, _e)\
83 LZ_ASSERT(0 <= ssize);\
84 if(ssize == 0) { return; }\
85 (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
86 (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\
88 #define BUCKET_A(_c0) bucket_A[(_c0)]
89 #if ALPHABET_SIZE == 256
90 #define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)])
91 #define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)])
93 #define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)])
94 #define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)])
98 /*- Private Functions -*/
100 static const int lg_table[256]= {
101 -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
102 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
103 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
104 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
105 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
106 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
107 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
108 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
111 #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
116 #if SS_BLOCKSIZE == 0
117 return (n & 0xffff0000) ?
119 24 + lg_table[(n >> 24) & 0xff] :
120 16 + lg_table[(n >> 16) & 0xff]) :
122 8 + lg_table[(n >> 8) & 0xff] :
123 0 + lg_table[(n >> 0) & 0xff]);
124 #elif SS_BLOCKSIZE < 256
127 return (n & 0xff00) ?
128 8 + lg_table[(n >> 8) & 0xff] :
129 0 + lg_table[(n >> 0) & 0xff];
133 #endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
135 #if SS_BLOCKSIZE != 0
137 static const int sqq_table[256] = {
138 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61,
139 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89,
140 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109,
141 110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126,
142 128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142,
143 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155,
144 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
145 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180,
146 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191,
147 192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201,
148 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211,
149 212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221,
150 221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230,
151 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
152 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247,
153 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255
161 if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; }
162 e = (x & 0xffff0000) ?
164 24 + lg_table[(x >> 24) & 0xff] :
165 16 + lg_table[(x >> 16) & 0xff]) :
167 8 + lg_table[(x >> 8) & 0xff] :
168 0 + lg_table[(x >> 0) & 0xff]);
171 y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7);
172 if(e >= 24) { y = (y + 1 + x / y) >> 1; }
173 y = (y + 1 + x / y) >> 1;
175 y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1;
177 return sqq_table[x] >> 4;
180 return (x < (y * y)) ? y - 1 : y;
183 #endif /* SS_BLOCKSIZE != 0 */
186 /*---------------------------------------------------------------------------*/
188 /* Compares two suffixes. */
191 ss_compare(const unsigned char *T,
192 const int *p1, const int *p2,
194 const unsigned char *U1, *U2, *U1n, *U2n;
196 for(U1 = T + depth + *p1,
197 U2 = T + depth + *p2,
198 U1n = T + *(p1 + 1) + 2,
199 U2n = T + *(p2 + 1) + 2;
200 (U1 < U1n) && (U2 < U2n) && (*U1 == *U2);
205 (U2 < U2n ? *U1 - *U2 : 1) :
210 /*---------------------------------------------------------------------------*/
212 #if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1)
214 /* Insertionsort for small size groups */
217 ss_insertionsort(const unsigned char *T, const int *PA,
218 int *first, int *last, int depth) {
223 for(i = last - 2; first <= i; --i) {
224 for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
225 do { *(j - 1) = *j; } while((++j < last) && (*j < 0));
226 if(last <= j) { break; }
228 if(r == 0) { *j = ~*j; }
233 #endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */
236 /*---------------------------------------------------------------------------*/
238 #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
242 ss_fixdown(const unsigned char *Td, const int *PA,
243 int *SA, int i, int size) {
248 for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
249 d = Td[PA[SA[k = j++]]];
250 if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; }
251 if(d <= c) { break; }
256 /* Simple top-down heapsort. */
259 ss_heapsort(const unsigned char *Td, const int *PA, int *SA, int size) {
264 if((size % 2) == 0) {
266 if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); }
269 for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); }
270 if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); }
271 for(i = m - 1; 0 < i; --i) {
272 t = SA[0], SA[0] = SA[i];
273 ss_fixdown(Td, PA, SA, 0, i);
279 /*---------------------------------------------------------------------------*/
281 /* Returns the median of three elements. */
284 ss_median3(const unsigned char *Td, const int *PA,
285 int *v1, int *v2, int *v3) {
286 if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
287 if(Td[PA[*v2]] > Td[PA[*v3]]) {
288 if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; }
294 /* Returns the median of five elements. */
297 ss_median5(const unsigned char *Td, const int *PA,
298 int *v1, int *v2, int *v3, int *v4, int *v5) {
299 if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
300 if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
301 if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); }
302 if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); }
303 if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); }
304 if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; }
308 /* Returns the pivot element. */
311 ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) {
316 middle = first + t / 2;
320 return ss_median3(Td, PA, first, middle, last - 1);
323 return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
327 first = ss_median3(Td, PA, first, first + t, first + (t << 1));
328 middle = ss_median3(Td, PA, middle - t, middle, middle + t);
329 last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
330 return ss_median3(Td, PA, first, middle, last);
334 /*---------------------------------------------------------------------------*/
336 /* Binary partition for substrings. */
339 ss_partition(const int *PA,
340 int *first, int *last, int depth) {
343 for(a = first - 1, b = last;;) {
344 for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; }
345 for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { }
346 if(b <= a) { break; }
351 if(first < a) { *first = ~*first; }
355 /* Multikey introsort for medium size groups. */
358 ss_mintrosort(const unsigned char *T, const int *PA,
359 int *first, int *last,
361 #define STACK_SIZE SS_MISORT_STACKSIZE
362 struct { int *a, *b, c; int d; } stack[STACK_SIZE];
363 const unsigned char *Td;
364 int *a, *b, *c, *d, *e, *f;
370 for(ssize = 0, limit = ss_ilg(last - first);;) {
372 if((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
373 #if 1 < SS_INSERTIONSORT_THRESHOLD
374 if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); }
376 STACK_POP(first, last, depth, limit);
381 if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); }
383 for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
384 if((x = Td[PA[*a]]) != v) {
385 if(1 < (a - first)) { break; }
390 if(Td[PA[*first] - 1] < v) {
391 first = ss_partition(PA, first, a, depth);
393 if((a - first) <= (last - a)) {
394 if(1 < (a - first)) {
395 STACK_PUSH(a, last, depth, -1);
396 last = a, depth += 1, limit = ss_ilg(a - first);
398 first = a, limit = -1;
402 STACK_PUSH(first, a, depth + 1, ss_ilg(a - first));
403 first = a, limit = -1;
405 last = a, depth += 1, limit = ss_ilg(a - first);
412 a = ss_pivot(Td, PA, first, last);
417 for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { }
418 if(((a = b) < last) && (x < v)) {
419 for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
420 if(x == v) { SWAP(*b, *a); ++a; }
423 for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { }
424 if((b < (d = c)) && (x > v)) {
425 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
426 if(x == v) { SWAP(*c, *d); --d; }
431 for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
432 if(x == v) { SWAP(*b, *a); ++a; }
434 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
435 if(x == v) { SWAP(*c, *d); --d; }
442 if((s = a - first) > (t = b - a)) { s = t; }
443 for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
444 if((s = d - c) > (t = last - d - 1)) { s = t; }
445 for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
447 a = first + (b - a), c = last - (d - c);
448 b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);
450 if((a - first) <= (last - c)) {
451 if((last - c) <= (c - b)) {
452 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
453 STACK_PUSH(c, last, depth, limit);
455 } else if((a - first) <= (c - b)) {
456 STACK_PUSH(c, last, depth, limit);
457 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
460 STACK_PUSH(c, last, depth, limit);
461 STACK_PUSH(first, a, depth, limit);
462 first = b, last = c, depth += 1, limit = ss_ilg(c - b);
465 if((a - first) <= (c - b)) {
466 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
467 STACK_PUSH(first, a, depth, limit);
469 } else if((last - c) <= (c - b)) {
470 STACK_PUSH(first, a, depth, limit);
471 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
474 STACK_PUSH(first, a, depth, limit);
475 STACK_PUSH(c, last, depth, limit);
476 first = b, last = c, depth += 1, limit = ss_ilg(c - b);
481 if(Td[PA[*first] - 1] < v) {
482 first = ss_partition(PA, first, last, depth);
483 limit = ss_ilg(last - first);
491 #endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
494 /*---------------------------------------------------------------------------*/
496 #if SS_BLOCKSIZE != 0
500 ss_blockswap(int *a, int *b, int n) {
502 for(; 0 < n; --n, ++a, ++b) {
503 t = *a, *a = *b, *b = t;
509 ss_rotate(int *first, int *middle, int *last) {
512 l = middle - first, r = last - middle;
513 for(; (0 < l) && (0 < r);) {
514 if(l == r) { ss_blockswap(first, middle, l); break; }
516 a = last - 1, b = middle - 1;
519 *a-- = *b, *b-- = *a;
523 if((r -= l + 1) <= l) { break; }
524 a -= 1, b = middle - 1;
529 a = first, b = middle;
532 *a++ = *b, *b++ = *a;
536 if((l -= r + 1) <= r) { break; }
546 /*---------------------------------------------------------------------------*/
550 ss_inplacemerge(const unsigned char *T, const int *PA,
551 int *first, int *middle, int *last,
560 if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); }
561 else { x = 0; p = PA + *(last - 1); }
562 for(a = first, len = middle - first, half = len >> 1, r = -1;
564 len = half, half >>= 1) {
566 q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
569 half -= (len & 1) ^ 1;
575 if(r == 0) { *a = ~*a; }
576 ss_rotate(a, middle, last);
579 if(first == middle) { break; }
582 if(x != 0) { while(*--last < 0) { } }
583 if(middle == last) { break; }
588 /*---------------------------------------------------------------------------*/
590 /* Merge-forward with internal buffer. */
593 ss_mergeforward(const unsigned char *T, const int *PA,
594 int *first, int *middle, int *last,
595 int *buf, int depth) {
596 int *a, *b, *c, *bufend;
600 bufend = buf + (middle - first) - 1;
601 ss_blockswap(buf, first, middle - first);
603 for(t = *(a = first), b = buf, c = middle;;) {
604 r = ss_compare(T, PA + *b, PA + *c, depth);
608 if(bufend <= b) { *bufend = t; return; }
613 *a++ = *c, *c++ = *a;
615 while(b < bufend) { *a++ = *b, *b++ = *a; }
624 if(bufend <= b) { *bufend = t; return; }
629 *a++ = *c, *c++ = *a;
631 while(b < bufend) { *a++ = *b, *b++ = *a; }
640 /* Merge-backward with internal buffer. */
643 ss_mergebackward(const unsigned char *T, const int *PA,
644 int *first, int *middle, int *last,
645 int *buf, int depth) {
647 int *a, *b, *c, *bufend;
652 bufend = buf + (last - middle) - 1;
653 ss_blockswap(buf, middle, last - middle);
656 if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; }
657 else { p1 = PA + *bufend; }
658 if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; }
659 else { p2 = PA + *(middle - 1); }
660 for(t = *(a = last - 1), b = bufend, c = middle - 1;;) {
661 r = ss_compare(T, p1, p2, depth);
663 if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
665 if(b <= buf) { *buf = t; break; }
667 if(*b < 0) { p1 = PA + ~*b; x |= 1; }
668 else { p1 = PA + *b; }
670 if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
671 *a-- = *c, *c-- = *a;
673 while(buf < b) { *a-- = *b, *b-- = *a; }
677 if(*c < 0) { p2 = PA + ~*c; x |= 2; }
678 else { p2 = PA + *c; }
680 if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
682 if(b <= buf) { *buf = t; break; }
684 if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
685 *a-- = *c, *c-- = *a;
687 while(buf < b) { *a-- = *b, *b-- = *a; }
691 if(*b < 0) { p1 = PA + ~*b; x |= 1; }
692 else { p1 = PA + *b; }
693 if(*c < 0) { p2 = PA + ~*c; x |= 2; }
694 else { p2 = PA + *c; }
699 /* D&C based merge. */
702 ss_swapmerge(const unsigned char *T, const int *PA,
703 int *first, int *middle, int *last,
704 int *buf, int bufsize, int depth) {
705 #define STACK_SIZE SS_SMERGE_STACKSIZE
706 #define GETIDX(a) ((0 <= (a)) ? (a) : (~(a)))
707 #define MERGE_CHECK(a, b, c)\
710 (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\
713 if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\
717 struct { int *a, *b, *c; int d; } stack[STACK_SIZE];
718 int *l, *r, *lm, *rm;
723 for(check = 0, ssize = 0;;) {
724 if((last - middle) <= bufsize) {
725 if((first < middle) && (middle < last)) {
726 ss_mergebackward(T, PA, first, middle, last, buf, depth);
728 MERGE_CHECK(first, last, check);
729 STACK_POP(first, middle, last, check);
733 if((middle - first) <= bufsize) {
735 ss_mergeforward(T, PA, first, middle, last, buf, depth);
737 MERGE_CHECK(first, last, check);
738 STACK_POP(first, middle, last, check);
742 for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1;
744 len = half, half >>= 1) {
745 if(ss_compare(T, PA + GETIDX(*(middle + m + half)),
746 PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
748 half -= (len & 1) ^ 1;
753 lm = middle - m, rm = middle + m;
754 ss_blockswap(lm, middle, m);
755 l = r = middle, next = 0;
759 if(first < lm) { for(; *--l < 0;) { } next |= 4; }
761 } else if(first < lm) {
762 for(; *r < 0; ++r) { }
767 if((l - first) <= (last - r)) {
768 STACK_PUSH(r, rm, last, (next & 3) | (check & 4));
769 middle = lm, last = l, check = (check & 3) | (next & 4);
771 if((next & 2) && (r == middle)) { next ^= 6; }
772 STACK_PUSH(first, lm, l, (check & 3) | (next & 4));
773 first = r, middle = rm, check = (next & 3) | (check & 4);
776 if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
779 MERGE_CHECK(first, last, check);
780 STACK_POP(first, middle, last, check);
786 #endif /* SS_BLOCKSIZE != 0 */
789 /*---------------------------------------------------------------------------*/
794 sssort(const unsigned char *T, const int *PA,
795 int *first, int *last,
796 int *buf, int bufsize,
797 int depth, int n, int lastsuffix) {
799 #if SS_BLOCKSIZE != 0
800 int *b, *middle, *curbuf;
801 int j, k, curbufsize, limit;
805 if(lastsuffix != 0) { ++first; }
807 #if SS_BLOCKSIZE == 0
808 ss_mintrosort(T, PA, first, last, depth);
810 if((bufsize < SS_BLOCKSIZE) &&
811 (bufsize < (last - first)) &&
812 (bufsize < (limit = ss_isqrt(last - first)))) {
813 if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; }
814 buf = middle = last - limit, bufsize = limit;
816 middle = last, limit = 0;
818 for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) {
819 #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
820 ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
821 #elif 1 < SS_BLOCKSIZE
822 ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
824 curbufsize = last - (a + SS_BLOCKSIZE);
825 curbuf = a + SS_BLOCKSIZE;
826 if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; }
827 for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) {
828 ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
831 #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
832 ss_mintrosort(T, PA, a, middle, depth);
833 #elif 1 < SS_BLOCKSIZE
834 ss_insertionsort(T, PA, a, middle, depth);
836 for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
838 ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
843 #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
844 ss_mintrosort(T, PA, middle, last, depth);
845 #elif 1 < SS_BLOCKSIZE
846 ss_insertionsort(T, PA, middle, last, depth);
848 ss_inplacemerge(T, PA, first, middle, last, depth);
852 if(lastsuffix != 0) {
853 /* Insert last type B* suffix. */
854 int PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
855 for(a = first, i = *(first - 1);
856 (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));
865 /*---------------------------------------------------------------------------*/
870 return (n & 0xffff0000) ?
872 24 + lg_table[(n >> 24) & 0xff] :
873 16 + lg_table[(n >> 16) & 0xff]) :
875 8 + lg_table[(n >> 8) & 0xff] :
876 0 + lg_table[(n >> 0) & 0xff]);
880 /*---------------------------------------------------------------------------*/
882 /* Simple insertionsort for small size groups. */
885 tr_insertionsort(const int *ISAd, int *first, int *last) {
889 for(a = first + 1; a < last; ++a) {
890 for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) {
891 do { *(b + 1) = *b; } while((first <= --b) && (*b < 0));
892 if(b < first) { break; }
894 if(r == 0) { *b = ~*b; }
900 /*---------------------------------------------------------------------------*/
904 tr_fixdown(const int *ISAd, int *SA, int i, int size) {
909 for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
910 d = ISAd[SA[k = j++]];
911 if(d < (e = ISAd[SA[j]])) { k = j; d = e; }
912 if(d <= c) { break; }
917 /* Simple top-down heapsort. */
920 tr_heapsort(const int *ISAd, int *SA, int size) {
925 if((size % 2) == 0) {
927 if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); }
930 for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); }
931 if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); }
932 for(i = m - 1; 0 < i; --i) {
933 t = SA[0], SA[0] = SA[i];
934 tr_fixdown(ISAd, SA, 0, i);
940 /*---------------------------------------------------------------------------*/
942 /* Returns the median of three elements. */
945 tr_median3(const int *ISAd, int *v1, int *v2, int *v3) {
946 if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); }
947 if(ISAd[*v2] > ISAd[*v3]) {
948 if(ISAd[*v1] > ISAd[*v3]) { return v1; }
954 /* Returns the median of five elements. */
957 tr_median5(const int *ISAd,
958 int *v1, int *v2, int *v3, int *v4, int *v5) {
959 if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); }
960 if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); }
961 if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); }
962 if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); }
963 if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); }
964 if(ISAd[*v3] > ISAd[*v4]) { return v4; }
968 /* Returns the pivot element. */
971 tr_pivot(const int *ISAd, int *first, int *last) {
976 middle = first + t / 2;
980 return tr_median3(ISAd, first, middle, last - 1);
983 return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1);
987 first = tr_median3(ISAd, first, first + t, first + (t << 1));
988 middle = tr_median3(ISAd, middle - t, middle, middle + t);
989 last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1);
990 return tr_median3(ISAd, first, middle, last);
994 /*---------------------------------------------------------------------------*/
996 typedef struct _trbudget_t trbudget_t;
1006 trbudget_init(trbudget_t *budget, int chance, int incval) {
1007 budget->chance = chance;
1008 budget->remain = budget->incval = incval;
1013 trbudget_check(trbudget_t *budget, int size) {
1014 if(size <= budget->remain) { budget->remain -= size; return 1; }
1015 if(budget->chance == 0) { budget->count += size; return 0; }
1016 budget->remain += budget->incval - size;
1017 budget->chance -= 1;
1022 /*---------------------------------------------------------------------------*/
1026 tr_partition(const int *ISAd,
1027 int *first, int *middle, int *last,
1028 int **pa, int **pb, int v) {
1029 int *a, *b, *c, *d, *e, *f;
1033 for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { }
1034 if(((a = b) < last) && (x < v)) {
1035 for(; (++b < last) && ((x = ISAd[*b]) <= v);) {
1036 if(x == v) { SWAP(*b, *a); ++a; }
1039 for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { }
1040 if((b < (d = c)) && (x > v)) {
1041 for(; (b < --c) && ((x = ISAd[*c]) >= v);) {
1042 if(x == v) { SWAP(*c, *d); --d; }
1047 for(; (++b < c) && ((x = ISAd[*b]) <= v);) {
1048 if(x == v) { SWAP(*b, *a); ++a; }
1050 for(; (b < --c) && ((x = ISAd[*c]) >= v);) {
1051 if(x == v) { SWAP(*c, *d); --d; }
1057 if((s = a - first) > (t = b - a)) { s = t; }
1058 for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
1059 if((s = d - c) > (t = last - d - 1)) { s = t; }
1060 for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
1061 first += (b - a), last -= (d - c);
1063 *pa = first, *pb = last;
1068 tr_copy(int *ISA, const int *SA,
1069 int *first, int *a, int *b, int *last,
1071 /* sort suffixes of middle partition
1072 by using sorted order of suffixes of left and right partition. */
1077 for(c = first, d = a - 1; c <= d; ++c) {
1078 if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
1083 for(c = last - 1, e = d + 1, d = b; e < d; --c) {
1084 if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
1093 tr_partialcopy(int *ISA, const int *SA,
1094 int *first, int *a, int *b, int *last,
1098 int rank, lastrank, newrank = -1;
1102 for(c = first, d = a - 1; c <= d; ++c) {
1103 if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
1105 rank = ISA[s + depth];
1106 if(lastrank != rank) { lastrank = rank; newrank = d - SA; }
1112 for(e = d; first <= e; --e) {
1114 if(lastrank != rank) { lastrank = rank; newrank = e - SA; }
1115 if(newrank != rank) { ISA[*e] = newrank; }
1119 for(c = last - 1, e = d + 1, d = b; e < d; --c) {
1120 if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
1122 rank = ISA[s + depth];
1123 if(lastrank != rank) { lastrank = rank; newrank = d - SA; }
1131 tr_introsort(int *ISA, const int *ISAd,
1132 int *SA, int *first, int *last,
1133 trbudget_t *budget) {
1134 #define STACK_SIZE TR_STACKSIZE
1135 struct { const int *a; int *b, *c; int d, e; }stack[STACK_SIZE];
1138 int incr = ISAd - ISA;
1140 int ssize, trlink = -1;
1142 for(ssize = 0, limit = tr_ilg(last - first);;) {
1146 /* tandem repeat partition */
1147 tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1);
1151 for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
1154 for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; }
1159 STACK_PUSH5(NULL, a, b, 0, 0);
1160 STACK_PUSH5(ISAd - incr, first, last, -2, trlink);
1163 if((a - first) <= (last - b)) {
1164 if(1 < (a - first)) {
1165 STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink);
1166 last = a, limit = tr_ilg(a - first);
1167 } else if(1 < (last - b)) {
1168 first = b, limit = tr_ilg(last - b);
1170 STACK_POP5(ISAd, first, last, limit, trlink);
1173 if(1 < (last - b)) {
1174 STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink);
1175 first = b, limit = tr_ilg(last - b);
1176 } else if(1 < (a - first)) {
1177 last = a, limit = tr_ilg(a - first);
1179 STACK_POP5(ISAd, first, last, limit, trlink);
1182 } else if(limit == -2) {
1183 /* tandem repeat copy */
1184 a = stack[--ssize].b, b = stack[ssize].c;
1185 if(stack[ssize].d == 0) {
1186 tr_copy(ISA, SA, first, a, b, last, ISAd - ISA);
1188 if(0 <= trlink) { stack[trlink].d = -1; }
1189 tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA);
1191 STACK_POP5(ISAd, first, last, limit, trlink);
1193 /* sorted partition */
1196 do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a));
1200 a = first; do { *a = ~*a; } while(*++a < 0);
1201 next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1;
1202 if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } }
1205 if(trbudget_check(budget, a - first)) {
1206 if((a - first) <= (last - a)) {
1207 STACK_PUSH5(ISAd, a, last, -3, trlink);
1208 ISAd += incr, last = a, limit = next;
1210 if(1 < (last - a)) {
1211 STACK_PUSH5(ISAd + incr, first, a, next, trlink);
1212 first = a, limit = -3;
1214 ISAd += incr, last = a, limit = next;
1218 if(0 <= trlink) { stack[trlink].d = -1; }
1219 if(1 < (last - a)) {
1220 first = a, limit = -3;
1222 STACK_POP5(ISAd, first, last, limit, trlink);
1226 STACK_POP5(ISAd, first, last, limit, trlink);
1232 if((last - first) <= TR_INSERTIONSORT_THRESHOLD) {
1233 tr_insertionsort(ISAd, first, last);
1239 tr_heapsort(ISAd, first, last - first);
1240 for(a = last - 1; first < a; a = b) {
1241 for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; }
1248 a = tr_pivot(ISAd, first, last);
1253 tr_partition(ISAd, first, first + 1, last, &a, &b, v);
1254 if((last - first) != (b - a)) {
1255 next = (ISA[*a] != v) ? tr_ilg(b - a) : -1;
1258 for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
1259 if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } }
1262 if((1 < (b - a)) && (trbudget_check(budget, b - a))) {
1263 if((a - first) <= (last - b)) {
1264 if((last - b) <= (b - a)) {
1265 if(1 < (a - first)) {
1266 STACK_PUSH5(ISAd + incr, a, b, next, trlink);
1267 STACK_PUSH5(ISAd, b, last, limit, trlink);
1269 } else if(1 < (last - b)) {
1270 STACK_PUSH5(ISAd + incr, a, b, next, trlink);
1273 ISAd += incr, first = a, last = b, limit = next;
1275 } else if((a - first) <= (b - a)) {
1276 if(1 < (a - first)) {
1277 STACK_PUSH5(ISAd, b, last, limit, trlink);
1278 STACK_PUSH5(ISAd + incr, a, b, next, trlink);
1281 STACK_PUSH5(ISAd, b, last, limit, trlink);
1282 ISAd += incr, first = a, last = b, limit = next;
1285 STACK_PUSH5(ISAd, b, last, limit, trlink);
1286 STACK_PUSH5(ISAd, first, a, limit, trlink);
1287 ISAd += incr, first = a, last = b, limit = next;
1290 if((a - first) <= (b - a)) {
1291 if(1 < (last - b)) {
1292 STACK_PUSH5(ISAd + incr, a, b, next, trlink);
1293 STACK_PUSH5(ISAd, first, a, limit, trlink);
1295 } else if(1 < (a - first)) {
1296 STACK_PUSH5(ISAd + incr, a, b, next, trlink);
1299 ISAd += incr, first = a, last = b, limit = next;
1301 } else if((last - b) <= (b - a)) {
1302 if(1 < (last - b)) {
1303 STACK_PUSH5(ISAd, first, a, limit, trlink);
1304 STACK_PUSH5(ISAd + incr, a, b, next, trlink);
1307 STACK_PUSH5(ISAd, first, a, limit, trlink);
1308 ISAd += incr, first = a, last = b, limit = next;
1311 STACK_PUSH5(ISAd, first, a, limit, trlink);
1312 STACK_PUSH5(ISAd, b, last, limit, trlink);
1313 ISAd += incr, first = a, last = b, limit = next;
1317 if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; }
1318 if((a - first) <= (last - b)) {
1319 if(1 < (a - first)) {
1320 STACK_PUSH5(ISAd, b, last, limit, trlink);
1322 } else if(1 < (last - b)) {
1325 STACK_POP5(ISAd, first, last, limit, trlink);
1328 if(1 < (last - b)) {
1329 STACK_PUSH5(ISAd, first, a, limit, trlink);
1331 } else if(1 < (a - first)) {
1334 STACK_POP5(ISAd, first, last, limit, trlink);
1339 if(trbudget_check(budget, last - first)) {
1340 limit = tr_ilg(last - first), ISAd += incr;
1342 if(0 <= trlink) { stack[trlink].d = -1; }
1343 STACK_POP5(ISAd, first, last, limit, trlink);
1352 /*---------------------------------------------------------------------------*/
1354 /* Tandem repeat sort */
1357 trsort(int *ISA, int *SA, int n, int depth) {
1361 int t, skip, unsorted;
1363 trbudget_init(&budget, tr_ilg(n) * 2 / 3, n);
1364 /* trbudget_init(&budget, tr_ilg(n) * 3 / 4, n); */
1365 for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) {
1370 if((t = *first) < 0) { first -= t; skip += t; }
1372 if(skip != 0) { *(first + skip) = skip; skip = 0; }
1373 last = SA + ISA[t] + 1;
1374 if(1 < (last - first)) {
1376 tr_introsort(ISA, ISAd, SA, first, last, &budget);
1377 if(budget.count != 0) { unsorted += budget.count; }
1378 else { skip = first - last; }
1379 } else if((last - first) == 1) {
1384 } while(first < (SA + n));
1385 if(skip != 0) { *(first + skip) = skip; }
1386 if(unsorted == 0) { break; }
1391 /*---------------------------------------------------------------------------*/
1393 /* Sorts suffixes of type B*. */
1396 sort_typeBstar(const unsigned char *T, int *SA,
1397 int *bucket_A, int *bucket_B,
1399 int *PAb, *ISAb, *buf;
1400 int i, j, k, t, m, bufsize;
1403 /* Initialize bucket arrays. */
1404 for(i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; }
1405 for(i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; }
1407 /* Count the number of occurrences of the first one or two characters of each
1408 type A, B and B* suffix. Moreover, store the beginning position of all
1409 type B* suffixes into the array SA. */
1410 for(i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) {
1411 /* type A suffix. */
1412 do { ++BUCKET_A(c1 = c0); } while((0 <= --i) && ((c0 = T[i]) >= c1));
1414 /* type B* suffix. */
1415 ++BUCKET_BSTAR(c0, c1);
1417 /* type B suffix. */
1418 for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
1426 A type B* suffix is lexicographically smaller than a type B suffix that
1427 begins with the same first two characters.
1430 /* Calculate the index of start/end point of each bucket. */
1431 for(c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) {
1432 t = i + BUCKET_A(c0);
1433 BUCKET_A(c0) = i + j; /* start point */
1434 i = t + BUCKET_B(c0, c0);
1435 for(c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) {
1436 j += BUCKET_BSTAR(c0, c1);
1437 BUCKET_BSTAR(c0, c1) = j; /* end point */
1438 i += BUCKET_B(c0, c1);
1443 /* Sort the type B* suffixes by their first two characters. */
1444 PAb = SA + n - m; ISAb = SA + m;
1445 for(i = m - 2; 0 <= i; --i) {
1446 t = PAb[i], c0 = T[t], c1 = T[t + 1];
1447 SA[--BUCKET_BSTAR(c0, c1)] = i;
1449 t = PAb[m - 1], c0 = T[t], c1 = T[t + 1];
1450 SA[--BUCKET_BSTAR(c0, c1)] = m - 1;
1452 /* Sort the type B* substrings using sssort. */
1453 buf = SA + m, bufsize = n - (2 * m);
1454 for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
1455 for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
1456 i = BUCKET_BSTAR(c0, c1);
1458 sssort(T, PAb, SA + i, SA + j,
1459 buf, bufsize, 2, n, *(SA + i) == (m - 1));
1464 /* Compute ranks of type B* substrings. */
1465 for(i = m - 1; 0 <= i; --i) {
1468 do { ISAb[SA[i]] = i; } while((0 <= --i) && (0 <= SA[i]));
1470 if(i <= 0) { break; }
1473 do { ISAb[SA[i] = ~SA[i]] = j; } while(SA[--i] < 0);
1477 /* Construct the inverse suffix array of type B* suffixes using trsort. */
1478 trsort(ISAb, SA, m, 1);
1480 /* Set the sorted order of tyoe B* suffixes. */
1481 for(i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) {
1482 for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) { }
1485 for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { }
1486 SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t;
1490 /* Calculate the index of start/end point of each bucket. */
1491 BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */
1492 for(c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) {
1493 i = BUCKET_A(c0 + 1) - 1;
1494 for(c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) {
1495 t = i - BUCKET_B(c0, c1);
1496 BUCKET_B(c0, c1) = i; /* end point */
1498 /* Move all type B* suffixes to the correct position. */
1499 for(i = t, j = BUCKET_BSTAR(c0, c1);
1501 --i, --k) { SA[i] = SA[k]; }
1503 BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */
1504 BUCKET_B(c0, c0) = i; /* end point */
1511 /* Constructs the suffix array by using the sorted order of type B* suffixes. */
1514 construct_SA(const unsigned char *T, int *SA,
1515 int *bucket_A, int *bucket_B,
1522 /* Construct the sorted order of type B suffixes by using
1523 the sorted order of type B* suffixes. */
1524 for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
1525 /* Scan the suffix array from right to left. */
1526 for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
1527 j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
1531 LZ_ASSERT(T[s] == c1);
1532 LZ_ASSERT(((s + 1) < n) && (T[s] <= T[s + 1]));
1533 LZ_ASSERT(T[s - 1] <= T[s]);
1536 if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
1538 if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
1539 k = SA + BUCKET_B(c2 = c0, c1);
1544 LZ_ASSERT(((s == 0) && (T[s] == c1)) || (s < 0));
1551 /* Construct the suffix array by using
1552 the sorted order of type B suffixes. */
1553 k = SA + BUCKET_A(c2 = T[n - 1]);
1554 *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1);
1555 /* Scan the suffix array from left to right. */
1556 for(i = SA, j = SA + n; i < j; ++i) {
1558 LZ_ASSERT(T[s - 1] >= T[s]);
1560 if((s == 0) || (T[s - 1] < c0)) { s = ~s; }
1562 BUCKET_A(c2) = k - SA;
1563 k = SA + BUCKET_A(c2 = c0);
1574 /*---------------------------------------------------------------------------*/
1578 /* XXX Modified from original: use provided temporary space instead of
1581 divsufsort(const u8 *T, u32 *SA, u32 n, u32 *bucket_A, u32 *bucket_B)
1600 m = sort_typeBstar(T, SA, bucket_A, bucket_B, n);
1601 construct_SA(T, SA, bucket_A, bucket_B, n, m);