| /* |
| * divsufsort.c for libdivsufsort-lite |
| * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. |
| * |
| * Permission is hereby granted, free of charge, to any person |
| * obtaining a copy of this software and associated documentation |
| * files (the "Software"), to deal in the Software without |
| * restriction, including without limitation the rights to use, |
| * copy, modify, merge, publish, distribute, sublicense, and/or sell |
| * copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following |
| * conditions: |
| * |
| * The above copyright notice and this permission notice shall be |
| * included in all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
| * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
| * OTHER DEALINGS IN THE SOFTWARE. |
| */ |
| |
| /*- Compiler specifics -*/ |
| #ifdef __clang__ |
| #pragma clang diagnostic ignored "-Wshorten-64-to-32" |
| #endif |
| |
| #if defined(_MSC_VER) |
| # pragma warning(disable : 4244) |
| # pragma warning(disable : 4127) /* C4127 : Condition expression is constant */ |
| #endif |
| |
| |
| /*- Dependencies -*/ |
| #include <assert.h> |
| #include <stdio.h> |
| #include <stdlib.h> |
| |
| #include "divsufsort.h" |
| |
| /*- Constants -*/ |
| #if defined(INLINE) |
| # undef INLINE |
| #endif |
| #if !defined(INLINE) |
| # define INLINE __inline |
| #endif |
| #if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1) |
| # undef ALPHABET_SIZE |
| #endif |
| #if !defined(ALPHABET_SIZE) |
| # define ALPHABET_SIZE (256) |
| #endif |
| #define BUCKET_A_SIZE (ALPHABET_SIZE) |
| #define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE) |
| #if defined(SS_INSERTIONSORT_THRESHOLD) |
| # if SS_INSERTIONSORT_THRESHOLD < 1 |
| # undef SS_INSERTIONSORT_THRESHOLD |
| # define SS_INSERTIONSORT_THRESHOLD (1) |
| # endif |
| #else |
| # define SS_INSERTIONSORT_THRESHOLD (8) |
| #endif |
| #if defined(SS_BLOCKSIZE) |
| # if SS_BLOCKSIZE < 0 |
| # undef SS_BLOCKSIZE |
| # define SS_BLOCKSIZE (0) |
| # elif 32768 <= SS_BLOCKSIZE |
| # undef SS_BLOCKSIZE |
| # define SS_BLOCKSIZE (32767) |
| # endif |
| #else |
| # define SS_BLOCKSIZE (1024) |
| #endif |
| /* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ |
| #if SS_BLOCKSIZE == 0 |
| # define SS_MISORT_STACKSIZE (96) |
| #elif SS_BLOCKSIZE <= 4096 |
| # define SS_MISORT_STACKSIZE (16) |
| #else |
| # define SS_MISORT_STACKSIZE (24) |
| #endif |
| #define SS_SMERGE_STACKSIZE (32) |
| #define TR_INSERTIONSORT_THRESHOLD (8) |
| #define TR_STACKSIZE (64) |
| |
| |
| /*- Macros -*/ |
| #ifndef SWAP |
| # define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0) |
| #endif /* SWAP */ |
| #ifndef MIN |
| # define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b)) |
| #endif /* MIN */ |
| #ifndef MAX |
| # define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b)) |
| #endif /* MAX */ |
| #define STACK_PUSH(_a, _b, _c, _d)\ |
| do {\ |
| assert(ssize < STACK_SIZE);\ |
| stack[ssize].a = (_a), stack[ssize].b = (_b),\ |
| stack[ssize].c = (_c), stack[ssize++].d = (_d);\ |
| } while(0) |
| #define STACK_PUSH5(_a, _b, _c, _d, _e)\ |
| do {\ |
| assert(ssize < STACK_SIZE);\ |
| stack[ssize].a = (_a), stack[ssize].b = (_b),\ |
| stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\ |
| } while(0) |
| #define STACK_POP(_a, _b, _c, _d)\ |
| do {\ |
| assert(0 <= ssize);\ |
| if(ssize == 0) { return; }\ |
| (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ |
| (_c) = stack[ssize].c, (_d) = stack[ssize].d;\ |
| } while(0) |
| #define STACK_POP5(_a, _b, _c, _d, _e)\ |
| do {\ |
| assert(0 <= ssize);\ |
| if(ssize == 0) { return; }\ |
| (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ |
| (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\ |
| } while(0) |
| #define BUCKET_A(_c0) bucket_A[(_c0)] |
| #if ALPHABET_SIZE == 256 |
| #define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)]) |
| #define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)]) |
| #else |
| #define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)]) |
| #define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)]) |
| #endif |
| |
| |
| /*- Private Functions -*/ |
| |
| static const int lg_table[256]= { |
| -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, |
| 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, |
| 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, |
| 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, |
| 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, |
| 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, |
| 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, |
| 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 |
| }; |
| |
| #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) |
| |
| static INLINE |
| int |
| ss_ilg(int n) { |
| #if SS_BLOCKSIZE == 0 |
| return (n & 0xffff0000) ? |
| ((n & 0xff000000) ? |
| 24 + lg_table[(n >> 24) & 0xff] : |
| 16 + lg_table[(n >> 16) & 0xff]) : |
| ((n & 0x0000ff00) ? |
| 8 + lg_table[(n >> 8) & 0xff] : |
| 0 + lg_table[(n >> 0) & 0xff]); |
| #elif SS_BLOCKSIZE < 256 |
| return lg_table[n]; |
| #else |
| return (n & 0xff00) ? |
| 8 + lg_table[(n >> 8) & 0xff] : |
| 0 + lg_table[(n >> 0) & 0xff]; |
| #endif |
| } |
| |
| #endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */ |
| |
| #if SS_BLOCKSIZE != 0 |
| |
| static const int sqq_table[256] = { |
| 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61, |
| 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89, |
| 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109, |
| 110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, |
| 128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, |
| 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, |
| 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168, |
| 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180, |
| 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191, |
| 192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201, |
| 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211, |
| 212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, |
| 221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, |
| 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238, |
| 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, |
| 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255 |
| }; |
| |
| static INLINE |
| int |
| ss_isqrt(int x) { |
| int y, e; |
| |
| if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; } |
| e = (x & 0xffff0000) ? |
| ((x & 0xff000000) ? |
| 24 + lg_table[(x >> 24) & 0xff] : |
| 16 + lg_table[(x >> 16) & 0xff]) : |
| ((x & 0x0000ff00) ? |
| 8 + lg_table[(x >> 8) & 0xff] : |
| 0 + lg_table[(x >> 0) & 0xff]); |
| |
| if(e >= 16) { |
| y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7); |
| if(e >= 24) { y = (y + 1 + x / y) >> 1; } |
| y = (y + 1 + x / y) >> 1; |
| } else if(e >= 8) { |
| y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1; |
| } else { |
| return sqq_table[x] >> 4; |
| } |
| |
| return (x < (y * y)) ? y - 1 : y; |
| } |
| |
| #endif /* SS_BLOCKSIZE != 0 */ |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Compares two suffixes. */ |
| static INLINE |
| int |
| ss_compare(const unsigned char *T, |
| const int *p1, const int *p2, |
| int depth) { |
| const unsigned char *U1, *U2, *U1n, *U2n; |
| |
| for(U1 = T + depth + *p1, |
| U2 = T + depth + *p2, |
| U1n = T + *(p1 + 1) + 2, |
| U2n = T + *(p2 + 1) + 2; |
| (U1 < U1n) && (U2 < U2n) && (*U1 == *U2); |
| ++U1, ++U2) { |
| } |
| |
| return U1 < U1n ? |
| (U2 < U2n ? *U1 - *U2 : 1) : |
| (U2 < U2n ? -1 : 0); |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| #if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) |
| |
| /* Insertionsort for small size groups */ |
| static |
| void |
| ss_insertionsort(const unsigned char *T, const int *PA, |
| int *first, int *last, int depth) { |
| int *i, *j; |
| int t; |
| int r; |
| |
| for(i = last - 2; first <= i; --i) { |
| for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) { |
| do { *(j - 1) = *j; } while((++j < last) && (*j < 0)); |
| if(last <= j) { break; } |
| } |
| if(r == 0) { *j = ~*j; } |
| *(j - 1) = t; |
| } |
| } |
| |
| #endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */ |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) |
| |
| static INLINE |
| void |
| ss_fixdown(const unsigned char *Td, const int *PA, |
| int *SA, int i, int size) { |
| int j, k; |
| int v; |
| int c, d, e; |
| |
| for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { |
| d = Td[PA[SA[k = j++]]]; |
| if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; } |
| if(d <= c) { break; } |
| } |
| SA[i] = v; |
| } |
| |
| /* Simple top-down heapsort. */ |
| static |
| void |
| ss_heapsort(const unsigned char *Td, const int *PA, int *SA, int size) { |
| int i, m; |
| int t; |
| |
| m = size; |
| if((size % 2) == 0) { |
| m--; |
| if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); } |
| } |
| |
| for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); } |
| if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); } |
| for(i = m - 1; 0 < i; --i) { |
| t = SA[0], SA[0] = SA[i]; |
| ss_fixdown(Td, PA, SA, 0, i); |
| SA[i] = t; |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Returns the median of three elements. */ |
| static INLINE |
| int * |
| ss_median3(const unsigned char *Td, const int *PA, |
| int *v1, int *v2, int *v3) { |
| int *t; |
| if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); } |
| if(Td[PA[*v2]] > Td[PA[*v3]]) { |
| if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; } |
| else { return v3; } |
| } |
| return v2; |
| } |
| |
| /* Returns the median of five elements. */ |
| static INLINE |
| int * |
| ss_median5(const unsigned char *Td, const int *PA, |
| int *v1, int *v2, int *v3, int *v4, int *v5) { |
| int *t; |
| if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); } |
| if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); } |
| if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); } |
| if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); } |
| if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); } |
| if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; } |
| return v3; |
| } |
| |
| /* Returns the pivot element. */ |
| static INLINE |
| int * |
| ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) { |
| int *middle; |
| int t; |
| |
| t = last - first; |
| middle = first + t / 2; |
| |
| if(t <= 512) { |
| if(t <= 32) { |
| return ss_median3(Td, PA, first, middle, last - 1); |
| } else { |
| t >>= 2; |
| return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1); |
| } |
| } |
| t >>= 3; |
| first = ss_median3(Td, PA, first, first + t, first + (t << 1)); |
| middle = ss_median3(Td, PA, middle - t, middle, middle + t); |
| last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1); |
| return ss_median3(Td, PA, first, middle, last); |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Binary partition for substrings. */ |
| static INLINE |
| int * |
| ss_partition(const int *PA, |
| int *first, int *last, int depth) { |
| int *a, *b; |
| int t; |
| for(a = first - 1, b = last;;) { |
| for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; } |
| for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { } |
| if(b <= a) { break; } |
| t = ~*b; |
| *b = *a; |
| *a = t; |
| } |
| if(first < a) { *first = ~*first; } |
| return a; |
| } |
| |
| /* Multikey introsort for medium size groups. */ |
| static |
| void |
| ss_mintrosort(const unsigned char *T, const int *PA, |
| int *first, int *last, |
| int depth) { |
| #define STACK_SIZE SS_MISORT_STACKSIZE |
| struct { int *a, *b, c; int d; } stack[STACK_SIZE]; |
| const unsigned char *Td; |
| int *a, *b, *c, *d, *e, *f; |
| int s, t; |
| int ssize; |
| int limit; |
| int v, x = 0; |
| |
| for(ssize = 0, limit = ss_ilg(last - first);;) { |
| |
| if((last - first) <= SS_INSERTIONSORT_THRESHOLD) { |
| #if 1 < SS_INSERTIONSORT_THRESHOLD |
| if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); } |
| #endif |
| STACK_POP(first, last, depth, limit); |
| continue; |
| } |
| |
| Td = T + depth; |
| if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); } |
| if(limit < 0) { |
| for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) { |
| if((x = Td[PA[*a]]) != v) { |
| if(1 < (a - first)) { break; } |
| v = x; |
| first = a; |
| } |
| } |
| if(Td[PA[*first] - 1] < v) { |
| first = ss_partition(PA, first, a, depth); |
| } |
| if((a - first) <= (last - a)) { |
| if(1 < (a - first)) { |
| STACK_PUSH(a, last, depth, -1); |
| last = a, depth += 1, limit = ss_ilg(a - first); |
| } else { |
| first = a, limit = -1; |
| } |
| } else { |
| if(1 < (last - a)) { |
| STACK_PUSH(first, a, depth + 1, ss_ilg(a - first)); |
| first = a, limit = -1; |
| } else { |
| last = a, depth += 1, limit = ss_ilg(a - first); |
| } |
| } |
| continue; |
| } |
| |
| /* choose pivot */ |
| a = ss_pivot(Td, PA, first, last); |
| v = Td[PA[*a]]; |
| SWAP(*first, *a); |
| |
| /* partition */ |
| for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } |
| if(((a = b) < last) && (x < v)) { |
| for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) { |
| if(x == v) { SWAP(*b, *a); ++a; } |
| } |
| } |
| for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { } |
| if((b < (d = c)) && (x > v)) { |
| for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { |
| if(x == v) { SWAP(*c, *d); --d; } |
| } |
| } |
| for(; b < c;) { |
| SWAP(*b, *c); |
| for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) { |
| if(x == v) { SWAP(*b, *a); ++a; } |
| } |
| for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { |
| if(x == v) { SWAP(*c, *d); --d; } |
| } |
| } |
| |
| if(a <= d) { |
| c = b - 1; |
| |
| if((s = a - first) > (t = b - a)) { s = t; } |
| for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
| if((s = d - c) > (t = last - d - 1)) { s = t; } |
| for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
| |
| a = first + (b - a), c = last - (d - c); |
| b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth); |
| |
| if((a - first) <= (last - c)) { |
| if((last - c) <= (c - b)) { |
| STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); |
| STACK_PUSH(c, last, depth, limit); |
| last = a; |
| } else if((a - first) <= (c - b)) { |
| STACK_PUSH(c, last, depth, limit); |
| STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); |
| last = a; |
| } else { |
| STACK_PUSH(c, last, depth, limit); |
| STACK_PUSH(first, a, depth, limit); |
| first = b, last = c, depth += 1, limit = ss_ilg(c - b); |
| } |
| } else { |
| if((a - first) <= (c - b)) { |
| STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); |
| STACK_PUSH(first, a, depth, limit); |
| first = c; |
| } else if((last - c) <= (c - b)) { |
| STACK_PUSH(first, a, depth, limit); |
| STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); |
| first = c; |
| } else { |
| STACK_PUSH(first, a, depth, limit); |
| STACK_PUSH(c, last, depth, limit); |
| first = b, last = c, depth += 1, limit = ss_ilg(c - b); |
| } |
| } |
| } else { |
| limit += 1; |
| if(Td[PA[*first] - 1] < v) { |
| first = ss_partition(PA, first, last, depth); |
| limit = ss_ilg(last - first); |
| } |
| depth += 1; |
| } |
| } |
| #undef STACK_SIZE |
| } |
| |
| #endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */ |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| #if SS_BLOCKSIZE != 0 |
| |
| static INLINE |
| void |
| ss_blockswap(int *a, int *b, int n) { |
| int t; |
| for(; 0 < n; --n, ++a, ++b) { |
| t = *a, *a = *b, *b = t; |
| } |
| } |
| |
| static INLINE |
| void |
| ss_rotate(int *first, int *middle, int *last) { |
| int *a, *b, t; |
| int l, r; |
| l = middle - first, r = last - middle; |
| for(; (0 < l) && (0 < r);) { |
| if(l == r) { ss_blockswap(first, middle, l); break; } |
| if(l < r) { |
| a = last - 1, b = middle - 1; |
| t = *a; |
| do { |
| *a-- = *b, *b-- = *a; |
| if(b < first) { |
| *a = t; |
| last = a; |
| if((r -= l + 1) <= l) { break; } |
| a -= 1, b = middle - 1; |
| t = *a; |
| } |
| } while(1); |
| } else { |
| a = first, b = middle; |
| t = *a; |
| do { |
| *a++ = *b, *b++ = *a; |
| if(last <= b) { |
| *a = t; |
| first = a + 1; |
| if((l -= r + 1) <= r) { break; } |
| a += 1, b = middle; |
| t = *a; |
| } |
| } while(1); |
| } |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| static |
| void |
| ss_inplacemerge(const unsigned char *T, const int *PA, |
| int *first, int *middle, int *last, |
| int depth) { |
| const int *p; |
| int *a, *b; |
| int len, half; |
| int q, r; |
| int x; |
| |
| for(;;) { |
| if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); } |
| else { x = 0; p = PA + *(last - 1); } |
| for(a = first, len = middle - first, half = len >> 1, r = -1; |
| 0 < len; |
| len = half, half >>= 1) { |
| b = a + half; |
| q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth); |
| if(q < 0) { |
| a = b + 1; |
| half -= (len & 1) ^ 1; |
| } else { |
| r = q; |
| } |
| } |
| if(a < middle) { |
| if(r == 0) { *a = ~*a; } |
| ss_rotate(a, middle, last); |
| last -= middle - a; |
| middle = a; |
| if(first == middle) { break; } |
| } |
| --last; |
| if(x != 0) { while(*--last < 0) { } } |
| if(middle == last) { break; } |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Merge-forward with internal buffer. */ |
| static |
| void |
| ss_mergeforward(const unsigned char *T, const int *PA, |
| int *first, int *middle, int *last, |
| int *buf, int depth) { |
| int *a, *b, *c, *bufend; |
| int t; |
| int r; |
| |
| bufend = buf + (middle - first) - 1; |
| ss_blockswap(buf, first, middle - first); |
| |
| for(t = *(a = first), b = buf, c = middle;;) { |
| r = ss_compare(T, PA + *b, PA + *c, depth); |
| if(r < 0) { |
| do { |
| *a++ = *b; |
| if(bufend <= b) { *bufend = t; return; } |
| *b++ = *a; |
| } while(*b < 0); |
| } else if(r > 0) { |
| do { |
| *a++ = *c, *c++ = *a; |
| if(last <= c) { |
| while(b < bufend) { *a++ = *b, *b++ = *a; } |
| *a = *b, *b = t; |
| return; |
| } |
| } while(*c < 0); |
| } else { |
| *c = ~*c; |
| do { |
| *a++ = *b; |
| if(bufend <= b) { *bufend = t; return; } |
| *b++ = *a; |
| } while(*b < 0); |
| |
| do { |
| *a++ = *c, *c++ = *a; |
| if(last <= c) { |
| while(b < bufend) { *a++ = *b, *b++ = *a; } |
| *a = *b, *b = t; |
| return; |
| } |
| } while(*c < 0); |
| } |
| } |
| } |
| |
| /* Merge-backward with internal buffer. */ |
| static |
| void |
| ss_mergebackward(const unsigned char *T, const int *PA, |
| int *first, int *middle, int *last, |
| int *buf, int depth) { |
| const int *p1, *p2; |
| int *a, *b, *c, *bufend; |
| int t; |
| int r; |
| int x; |
| |
| bufend = buf + (last - middle) - 1; |
| ss_blockswap(buf, middle, last - middle); |
| |
| x = 0; |
| if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; } |
| else { p1 = PA + *bufend; } |
| if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; } |
| else { p2 = PA + *(middle - 1); } |
| for(t = *(a = last - 1), b = bufend, c = middle - 1;;) { |
| r = ss_compare(T, p1, p2, depth); |
| if(0 < r) { |
| if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } |
| *a-- = *b; |
| if(b <= buf) { *buf = t; break; } |
| *b-- = *a; |
| if(*b < 0) { p1 = PA + ~*b; x |= 1; } |
| else { p1 = PA + *b; } |
| } else if(r < 0) { |
| if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } |
| *a-- = *c, *c-- = *a; |
| if(c < first) { |
| while(buf < b) { *a-- = *b, *b-- = *a; } |
| *a = *b, *b = t; |
| break; |
| } |
| if(*c < 0) { p2 = PA + ~*c; x |= 2; } |
| else { p2 = PA + *c; } |
| } else { |
| if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } |
| *a-- = ~*b; |
| if(b <= buf) { *buf = t; break; } |
| *b-- = *a; |
| if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } |
| *a-- = *c, *c-- = *a; |
| if(c < first) { |
| while(buf < b) { *a-- = *b, *b-- = *a; } |
| *a = *b, *b = t; |
| break; |
| } |
| if(*b < 0) { p1 = PA + ~*b; x |= 1; } |
| else { p1 = PA + *b; } |
| if(*c < 0) { p2 = PA + ~*c; x |= 2; } |
| else { p2 = PA + *c; } |
| } |
| } |
| } |
| |
| /* D&C based merge. */ |
| static |
| void |
| ss_swapmerge(const unsigned char *T, const int *PA, |
| int *first, int *middle, int *last, |
| int *buf, int bufsize, int depth) { |
| #define STACK_SIZE SS_SMERGE_STACKSIZE |
| #define GETIDX(a) ((0 <= (a)) ? (a) : (~(a))) |
| #define MERGE_CHECK(a, b, c)\ |
| do {\ |
| if(((c) & 1) ||\ |
| (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\ |
| *(a) = ~*(a);\ |
| }\ |
| if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\ |
| *(b) = ~*(b);\ |
| }\ |
| } while(0) |
| struct { int *a, *b, *c; int d; } stack[STACK_SIZE]; |
| int *l, *r, *lm, *rm; |
| int m, len, half; |
| int ssize; |
| int check, next; |
| |
| for(check = 0, ssize = 0;;) { |
| if((last - middle) <= bufsize) { |
| if((first < middle) && (middle < last)) { |
| ss_mergebackward(T, PA, first, middle, last, buf, depth); |
| } |
| MERGE_CHECK(first, last, check); |
| STACK_POP(first, middle, last, check); |
| continue; |
| } |
| |
| if((middle - first) <= bufsize) { |
| if(first < middle) { |
| ss_mergeforward(T, PA, first, middle, last, buf, depth); |
| } |
| MERGE_CHECK(first, last, check); |
| STACK_POP(first, middle, last, check); |
| continue; |
| } |
| |
| for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1; |
| 0 < len; |
| len = half, half >>= 1) { |
| if(ss_compare(T, PA + GETIDX(*(middle + m + half)), |
| PA + GETIDX(*(middle - m - half - 1)), depth) < 0) { |
| m += half + 1; |
| half -= (len & 1) ^ 1; |
| } |
| } |
| |
| if(0 < m) { |
| lm = middle - m, rm = middle + m; |
| ss_blockswap(lm, middle, m); |
| l = r = middle, next = 0; |
| if(rm < last) { |
| if(*rm < 0) { |
| *rm = ~*rm; |
| if(first < lm) { for(; *--l < 0;) { } next |= 4; } |
| next |= 1; |
| } else if(first < lm) { |
| for(; *r < 0; ++r) { } |
| next |= 2; |
| } |
| } |
| |
| if((l - first) <= (last - r)) { |
| STACK_PUSH(r, rm, last, (next & 3) | (check & 4)); |
| middle = lm, last = l, check = (check & 3) | (next & 4); |
| } else { |
| if((next & 2) && (r == middle)) { next ^= 6; } |
| STACK_PUSH(first, lm, l, (check & 3) | (next & 4)); |
| first = r, middle = rm, check = (next & 3) | (check & 4); |
| } |
| } else { |
| if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) { |
| *middle = ~*middle; |
| } |
| MERGE_CHECK(first, last, check); |
| STACK_POP(first, middle, last, check); |
| } |
| } |
| #undef STACK_SIZE |
| } |
| |
| #endif /* SS_BLOCKSIZE != 0 */ |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Substring sort */ |
| static |
| void |
| sssort(const unsigned char *T, const int *PA, |
| int *first, int *last, |
| int *buf, int bufsize, |
| int depth, int n, int lastsuffix) { |
| int *a; |
| #if SS_BLOCKSIZE != 0 |
| int *b, *middle, *curbuf; |
| int j, k, curbufsize, limit; |
| #endif |
| int i; |
| |
| if(lastsuffix != 0) { ++first; } |
| |
| #if SS_BLOCKSIZE == 0 |
| ss_mintrosort(T, PA, first, last, depth); |
| #else |
| if((bufsize < SS_BLOCKSIZE) && |
| (bufsize < (last - first)) && |
| (bufsize < (limit = ss_isqrt(last - first)))) { |
| if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; } |
| buf = middle = last - limit, bufsize = limit; |
| } else { |
| middle = last, limit = 0; |
| } |
| for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) { |
| #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE |
| ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth); |
| #elif 1 < SS_BLOCKSIZE |
| ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth); |
| #endif |
| curbufsize = last - (a + SS_BLOCKSIZE); |
| curbuf = a + SS_BLOCKSIZE; |
| if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; } |
| for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) { |
| ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth); |
| } |
| } |
| #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE |
| ss_mintrosort(T, PA, a, middle, depth); |
| #elif 1 < SS_BLOCKSIZE |
| ss_insertionsort(T, PA, a, middle, depth); |
| #endif |
| for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) { |
| if(i & 1) { |
| ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth); |
| a -= k; |
| } |
| } |
| if(limit != 0) { |
| #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE |
| ss_mintrosort(T, PA, middle, last, depth); |
| #elif 1 < SS_BLOCKSIZE |
| ss_insertionsort(T, PA, middle, last, depth); |
| #endif |
| ss_inplacemerge(T, PA, first, middle, last, depth); |
| } |
| #endif |
| |
| if(lastsuffix != 0) { |
| /* Insert last type B* suffix. */ |
| int PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2; |
| for(a = first, i = *(first - 1); |
| (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); |
| ++a) { |
| *(a - 1) = *a; |
| } |
| *(a - 1) = i; |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| static INLINE |
| int |
| tr_ilg(int n) { |
| return (n & 0xffff0000) ? |
| ((n & 0xff000000) ? |
| 24 + lg_table[(n >> 24) & 0xff] : |
| 16 + lg_table[(n >> 16) & 0xff]) : |
| ((n & 0x0000ff00) ? |
| 8 + lg_table[(n >> 8) & 0xff] : |
| 0 + lg_table[(n >> 0) & 0xff]); |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Simple insertionsort for small size groups. */ |
| static |
| void |
| tr_insertionsort(const int *ISAd, int *first, int *last) { |
| int *a, *b; |
| int t, r; |
| |
| for(a = first + 1; a < last; ++a) { |
| for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) { |
| do { *(b + 1) = *b; } while((first <= --b) && (*b < 0)); |
| if(b < first) { break; } |
| } |
| if(r == 0) { *b = ~*b; } |
| *(b + 1) = t; |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| static INLINE |
| void |
| tr_fixdown(const int *ISAd, int *SA, int i, int size) { |
| int j, k; |
| int v; |
| int c, d, e; |
| |
| for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { |
| d = ISAd[SA[k = j++]]; |
| if(d < (e = ISAd[SA[j]])) { k = j; d = e; } |
| if(d <= c) { break; } |
| } |
| SA[i] = v; |
| } |
| |
| /* Simple top-down heapsort. */ |
| static |
| void |
| tr_heapsort(const int *ISAd, int *SA, int size) { |
| int i, m; |
| int t; |
| |
| m = size; |
| if((size % 2) == 0) { |
| m--; |
| if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); } |
| } |
| |
| for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); } |
| if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); } |
| for(i = m - 1; 0 < i; --i) { |
| t = SA[0], SA[0] = SA[i]; |
| tr_fixdown(ISAd, SA, 0, i); |
| SA[i] = t; |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Returns the median of three elements. */ |
| static INLINE |
| int * |
| tr_median3(const int *ISAd, int *v1, int *v2, int *v3) { |
| int *t; |
| if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); } |
| if(ISAd[*v2] > ISAd[*v3]) { |
| if(ISAd[*v1] > ISAd[*v3]) { return v1; } |
| else { return v3; } |
| } |
| return v2; |
| } |
| |
| /* Returns the median of five elements. */ |
| static INLINE |
| int * |
| tr_median5(const int *ISAd, |
| int *v1, int *v2, int *v3, int *v4, int *v5) { |
| int *t; |
| if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); } |
| if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); } |
| if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); } |
| if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); } |
| if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); } |
| if(ISAd[*v3] > ISAd[*v4]) { return v4; } |
| return v3; |
| } |
| |
| /* Returns the pivot element. */ |
| static INLINE |
| int * |
| tr_pivot(const int *ISAd, int *first, int *last) { |
| int *middle; |
| int t; |
| |
| t = last - first; |
| middle = first + t / 2; |
| |
| if(t <= 512) { |
| if(t <= 32) { |
| return tr_median3(ISAd, first, middle, last - 1); |
| } else { |
| t >>= 2; |
| return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1); |
| } |
| } |
| t >>= 3; |
| first = tr_median3(ISAd, first, first + t, first + (t << 1)); |
| middle = tr_median3(ISAd, middle - t, middle, middle + t); |
| last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1); |
| return tr_median3(ISAd, first, middle, last); |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| typedef struct _trbudget_t trbudget_t; |
| struct _trbudget_t { |
| int chance; |
| int remain; |
| int incval; |
| int count; |
| }; |
| |
| static INLINE |
| void |
| trbudget_init(trbudget_t *budget, int chance, int incval) { |
| budget->chance = chance; |
| budget->remain = budget->incval = incval; |
| } |
| |
| static INLINE |
| int |
| trbudget_check(trbudget_t *budget, int size) { |
| if(size <= budget->remain) { budget->remain -= size; return 1; } |
| if(budget->chance == 0) { budget->count += size; return 0; } |
| budget->remain += budget->incval - size; |
| budget->chance -= 1; |
| return 1; |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| static INLINE |
| void |
| tr_partition(const int *ISAd, |
| int *first, int *middle, int *last, |
| int **pa, int **pb, int v) { |
| int *a, *b, *c, *d, *e, *f; |
| int t, s; |
| int x = 0; |
| |
| for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { } |
| if(((a = b) < last) && (x < v)) { |
| for(; (++b < last) && ((x = ISAd[*b]) <= v);) { |
| if(x == v) { SWAP(*b, *a); ++a; } |
| } |
| } |
| for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { } |
| if((b < (d = c)) && (x > v)) { |
| for(; (b < --c) && ((x = ISAd[*c]) >= v);) { |
| if(x == v) { SWAP(*c, *d); --d; } |
| } |
| } |
| for(; b < c;) { |
| SWAP(*b, *c); |
| for(; (++b < c) && ((x = ISAd[*b]) <= v);) { |
| if(x == v) { SWAP(*b, *a); ++a; } |
| } |
| for(; (b < --c) && ((x = ISAd[*c]) >= v);) { |
| if(x == v) { SWAP(*c, *d); --d; } |
| } |
| } |
| |
| if(a <= d) { |
| c = b - 1; |
| if((s = a - first) > (t = b - a)) { s = t; } |
| for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
| if((s = d - c) > (t = last - d - 1)) { s = t; } |
| for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
| first += (b - a), last -= (d - c); |
| } |
| *pa = first, *pb = last; |
| } |
| |
| static |
| void |
| tr_copy(int *ISA, const int *SA, |
| int *first, int *a, int *b, int *last, |
| int depth) { |
| /* sort suffixes of middle partition |
| by using sorted order of suffixes of left and right partition. */ |
| int *c, *d, *e; |
| int s, v; |
| |
| v = b - SA - 1; |
| for(c = first, d = a - 1; c <= d; ++c) { |
| if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
| *++d = s; |
| ISA[s] = d - SA; |
| } |
| } |
| for(c = last - 1, e = d + 1, d = b; e < d; --c) { |
| if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
| *--d = s; |
| ISA[s] = d - SA; |
| } |
| } |
| } |
| |
| static |
| void |
| tr_partialcopy(int *ISA, const int *SA, |
| int *first, int *a, int *b, int *last, |
| int depth) { |
| int *c, *d, *e; |
| int s, v; |
| int rank, lastrank, newrank = -1; |
| |
| v = b - SA - 1; |
| lastrank = -1; |
| for(c = first, d = a - 1; c <= d; ++c) { |
| if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
| *++d = s; |
| rank = ISA[s + depth]; |
| if(lastrank != rank) { lastrank = rank; newrank = d - SA; } |
| ISA[s] = newrank; |
| } |
| } |
| |
| lastrank = -1; |
| for(e = d; first <= e; --e) { |
| rank = ISA[*e]; |
| if(lastrank != rank) { lastrank = rank; newrank = e - SA; } |
| if(newrank != rank) { ISA[*e] = newrank; } |
| } |
| |
| lastrank = -1; |
| for(c = last - 1, e = d + 1, d = b; e < d; --c) { |
| if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
| *--d = s; |
| rank = ISA[s + depth]; |
| if(lastrank != rank) { lastrank = rank; newrank = d - SA; } |
| ISA[s] = newrank; |
| } |
| } |
| } |
| |
| static |
| void |
| tr_introsort(int *ISA, const int *ISAd, |
| int *SA, int *first, int *last, |
| trbudget_t *budget) { |
| #define STACK_SIZE TR_STACKSIZE |
| struct { const int *a; int *b, *c; int d, e; }stack[STACK_SIZE]; |
| int *a, *b, *c; |
| int t; |
| int v, x = 0; |
| int incr = ISAd - ISA; |
| int limit, next; |
| int ssize, trlink = -1; |
| |
| for(ssize = 0, limit = tr_ilg(last - first);;) { |
| |
| if(limit < 0) { |
| if(limit == -1) { |
| /* tandem repeat partition */ |
| tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1); |
| |
| /* update ranks */ |
| if(a < last) { |
| for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } |
| } |
| if(b < last) { |
| for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } |
| } |
| |
| /* push */ |
| if(1 < (b - a)) { |
| STACK_PUSH5(NULL, a, b, 0, 0); |
| STACK_PUSH5(ISAd - incr, first, last, -2, trlink); |
| trlink = ssize - 2; |
| } |
| if((a - first) <= (last - b)) { |
| if(1 < (a - first)) { |
| STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink); |
| last = a, limit = tr_ilg(a - first); |
| } else if(1 < (last - b)) { |
| first = b, limit = tr_ilg(last - b); |
| } else { |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } else { |
| if(1 < (last - b)) { |
| STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink); |
| first = b, limit = tr_ilg(last - b); |
| } else if(1 < (a - first)) { |
| last = a, limit = tr_ilg(a - first); |
| } else { |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } |
| } else if(limit == -2) { |
| /* tandem repeat copy */ |
| a = stack[--ssize].b, b = stack[ssize].c; |
| if(stack[ssize].d == 0) { |
| tr_copy(ISA, SA, first, a, b, last, ISAd - ISA); |
| } else { |
| if(0 <= trlink) { stack[trlink].d = -1; } |
| tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA); |
| } |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } else { |
| /* sorted partition */ |
| if(0 <= *first) { |
| a = first; |
| do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a)); |
| first = a; |
| } |
| if(first < last) { |
| a = first; do { *a = ~*a; } while(*++a < 0); |
| next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1; |
| if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } |
| |
| /* push */ |
| if(trbudget_check(budget, a - first)) { |
| if((a - first) <= (last - a)) { |
| STACK_PUSH5(ISAd, a, last, -3, trlink); |
| ISAd += incr, last = a, limit = next; |
| } else { |
| if(1 < (last - a)) { |
| STACK_PUSH5(ISAd + incr, first, a, next, trlink); |
| first = a, limit = -3; |
| } else { |
| ISAd += incr, last = a, limit = next; |
| } |
| } |
| } else { |
| if(0 <= trlink) { stack[trlink].d = -1; } |
| if(1 < (last - a)) { |
| first = a, limit = -3; |
| } else { |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } |
| } else { |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } |
| continue; |
| } |
| |
| if((last - first) <= TR_INSERTIONSORT_THRESHOLD) { |
| tr_insertionsort(ISAd, first, last); |
| limit = -3; |
| continue; |
| } |
| |
| if(limit-- == 0) { |
| tr_heapsort(ISAd, first, last - first); |
| for(a = last - 1; first < a; a = b) { |
| for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } |
| } |
| limit = -3; |
| continue; |
| } |
| |
| /* choose pivot */ |
| a = tr_pivot(ISAd, first, last); |
| SWAP(*first, *a); |
| v = ISAd[*first]; |
| |
| /* partition */ |
| tr_partition(ISAd, first, first + 1, last, &a, &b, v); |
| if((last - first) != (b - a)) { |
| next = (ISA[*a] != v) ? tr_ilg(b - a) : -1; |
| |
| /* update ranks */ |
| for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } |
| if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } } |
| |
| /* push */ |
| if((1 < (b - a)) && (trbudget_check(budget, b - a))) { |
| if((a - first) <= (last - b)) { |
| if((last - b) <= (b - a)) { |
| if(1 < (a - first)) { |
| STACK_PUSH5(ISAd + incr, a, b, next, trlink); |
| STACK_PUSH5(ISAd, b, last, limit, trlink); |
| last = a; |
| } else if(1 < (last - b)) { |
| STACK_PUSH5(ISAd + incr, a, b, next, trlink); |
| first = b; |
| } else { |
| ISAd += incr, first = a, last = b, limit = next; |
| } |
| } else if((a - first) <= (b - a)) { |
| if(1 < (a - first)) { |
| STACK_PUSH5(ISAd, b, last, limit, trlink); |
| STACK_PUSH5(ISAd + incr, a, b, next, trlink); |
| last = a; |
| } else { |
| STACK_PUSH5(ISAd, b, last, limit, trlink); |
| ISAd += incr, first = a, last = b, limit = next; |
| } |
| } else { |
| STACK_PUSH5(ISAd, b, last, limit, trlink); |
| STACK_PUSH5(ISAd, first, a, limit, trlink); |
| ISAd += incr, first = a, last = b, limit = next; |
| } |
| } else { |
| if((a - first) <= (b - a)) { |
| if(1 < (last - b)) { |
| STACK_PUSH5(ISAd + incr, a, b, next, trlink); |
| STACK_PUSH5(ISAd, first, a, limit, trlink); |
| first = b; |
| } else if(1 < (a - first)) { |
| STACK_PUSH5(ISAd + incr, a, b, next, trlink); |
| last = a; |
| } else { |
| ISAd += incr, first = a, last = b, limit = next; |
| } |
| } else if((last - b) <= (b - a)) { |
| if(1 < (last - b)) { |
| STACK_PUSH5(ISAd, first, a, limit, trlink); |
| STACK_PUSH5(ISAd + incr, a, b, next, trlink); |
| first = b; |
| } else { |
| STACK_PUSH5(ISAd, first, a, limit, trlink); |
| ISAd += incr, first = a, last = b, limit = next; |
| } |
| } else { |
| STACK_PUSH5(ISAd, first, a, limit, trlink); |
| STACK_PUSH5(ISAd, b, last, limit, trlink); |
| ISAd += incr, first = a, last = b, limit = next; |
| } |
| } |
| } else { |
| if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; } |
| if((a - first) <= (last - b)) { |
| if(1 < (a - first)) { |
| STACK_PUSH5(ISAd, b, last, limit, trlink); |
| last = a; |
| } else if(1 < (last - b)) { |
| first = b; |
| } else { |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } else { |
| if(1 < (last - b)) { |
| STACK_PUSH5(ISAd, first, a, limit, trlink); |
| first = b; |
| } else if(1 < (a - first)) { |
| last = a; |
| } else { |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } |
| } |
| } else { |
| if(trbudget_check(budget, last - first)) { |
| limit = tr_ilg(last - first), ISAd += incr; |
| } else { |
| if(0 <= trlink) { stack[trlink].d = -1; } |
| STACK_POP5(ISAd, first, last, limit, trlink); |
| } |
| } |
| } |
| #undef STACK_SIZE |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Tandem repeat sort */ |
| static |
| void |
| trsort(int *ISA, int *SA, int n, int depth) { |
| int *ISAd; |
| int *first, *last; |
| trbudget_t budget; |
| int t, skip, unsorted; |
| |
| trbudget_init(&budget, tr_ilg(n) * 2 / 3, n); |
| /* trbudget_init(&budget, tr_ilg(n) * 3 / 4, n); */ |
| for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) { |
| first = SA; |
| skip = 0; |
| unsorted = 0; |
| do { |
| if((t = *first) < 0) { first -= t; skip += t; } |
| else { |
| if(skip != 0) { *(first + skip) = skip; skip = 0; } |
| last = SA + ISA[t] + 1; |
| if(1 < (last - first)) { |
| budget.count = 0; |
| tr_introsort(ISA, ISAd, SA, first, last, &budget); |
| if(budget.count != 0) { unsorted += budget.count; } |
| else { skip = first - last; } |
| } else if((last - first) == 1) { |
| skip = -1; |
| } |
| first = last; |
| } |
| } while(first < (SA + n)); |
| if(skip != 0) { *(first + skip) = skip; } |
| if(unsorted == 0) { break; } |
| } |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /* Sorts suffixes of type B*. */ |
| static |
| int |
| sort_typeBstar(const unsigned char *T, int *SA, |
| int *bucket_A, int *bucket_B, |
| int n, int openMP) { |
| int *PAb, *ISAb, *buf; |
| #ifdef LIBBSC_OPENMP |
| int *curbuf; |
| int l; |
| #endif |
| int i, j, k, t, m, bufsize; |
| int c0, c1; |
| #ifdef LIBBSC_OPENMP |
| int d0, d1; |
| #endif |
| (void)openMP; |
| |
| /* Initialize bucket arrays. */ |
| for(i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; } |
| for(i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; } |
| |
| /* Count the number of occurrences of the first one or two characters of each |
| type A, B and B* suffix. Moreover, store the beginning position of all |
| type B* suffixes into the array SA. */ |
| for(i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) { |
| /* type A suffix. */ |
| do { ++BUCKET_A(c1 = c0); } while((0 <= --i) && ((c0 = T[i]) >= c1)); |
| if(0 <= i) { |
| /* type B* suffix. */ |
| ++BUCKET_BSTAR(c0, c1); |
| SA[--m] = i; |
| /* type B suffix. */ |
| for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { |
| ++BUCKET_B(c0, c1); |
| } |
| } |
| } |
| m = n - m; |
| /* |
| note: |
| A type B* suffix is lexicographically smaller than a type B suffix that |
| begins with the same first two characters. |
| */ |
| |
| /* Calculate the index of start/end point of each bucket. */ |
| for(c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) { |
| t = i + BUCKET_A(c0); |
| BUCKET_A(c0) = i + j; /* start point */ |
| i = t + BUCKET_B(c0, c0); |
| for(c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) { |
| j += BUCKET_BSTAR(c0, c1); |
| BUCKET_BSTAR(c0, c1) = j; /* end point */ |
| i += BUCKET_B(c0, c1); |
| } |
| } |
| |
| if(0 < m) { |
| /* Sort the type B* suffixes by their first two characters. */ |
| PAb = SA + n - m; ISAb = SA + m; |
| for(i = m - 2; 0 <= i; --i) { |
| t = PAb[i], c0 = T[t], c1 = T[t + 1]; |
| SA[--BUCKET_BSTAR(c0, c1)] = i; |
| } |
| t = PAb[m - 1], c0 = T[t], c1 = T[t + 1]; |
| SA[--BUCKET_BSTAR(c0, c1)] = m - 1; |
| |
| /* Sort the type B* substrings using sssort. */ |
| #ifdef LIBBSC_OPENMP |
| if (openMP) |
| { |
| buf = SA + m; |
| c0 = ALPHABET_SIZE - 2, c1 = ALPHABET_SIZE - 1, j = m; |
| #pragma omp parallel default(shared) private(bufsize, curbuf, k, l, d0, d1) |
| { |
| bufsize = (n - (2 * m)) / omp_get_num_threads(); |
| curbuf = buf + omp_get_thread_num() * bufsize; |
| k = 0; |
| for(;;) { |
| #pragma omp critical(sssort_lock) |
| { |
| if(0 < (l = j)) { |
| d0 = c0, d1 = c1; |
| do { |
| k = BUCKET_BSTAR(d0, d1); |
| if(--d1 <= d0) { |
| d1 = ALPHABET_SIZE - 1; |
| if(--d0 < 0) { break; } |
| } |
| } while(((l - k) <= 1) && (0 < (l = k))); |
| c0 = d0, c1 = d1, j = k; |
| } |
| } |
| if(l == 0) { break; } |
| sssort(T, PAb, SA + k, SA + l, |
| curbuf, bufsize, 2, n, *(SA + k) == (m - 1)); |
| } |
| } |
| } |
| else |
| { |
| buf = SA + m, bufsize = n - (2 * m); |
| for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) { |
| for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) { |
| i = BUCKET_BSTAR(c0, c1); |
| if(1 < (j - i)) { |
| sssort(T, PAb, SA + i, SA + j, |
| buf, bufsize, 2, n, *(SA + i) == (m - 1)); |
| } |
| } |
| } |
| } |
| #else |
| buf = SA + m, bufsize = n - (2 * m); |
| for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) { |
| for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) { |
| i = BUCKET_BSTAR(c0, c1); |
| if(1 < (j - i)) { |
| sssort(T, PAb, SA + i, SA + j, |
| buf, bufsize, 2, n, *(SA + i) == (m - 1)); |
| } |
| } |
| } |
| #endif |
| |
| /* Compute ranks of type B* substrings. */ |
| for(i = m - 1; 0 <= i; --i) { |
| if(0 <= SA[i]) { |
| j = i; |
| do { ISAb[SA[i]] = i; } while((0 <= --i) && (0 <= SA[i])); |
| SA[i + 1] = i - j; |
| if(i <= 0) { break; } |
| } |
| j = i; |
| do { ISAb[SA[i] = ~SA[i]] = j; } while(SA[--i] < 0); |
| ISAb[SA[i]] = j; |
| } |
| |
| /* Construct the inverse suffix array of type B* suffixes using trsort. */ |
| trsort(ISAb, SA, m, 1); |
| |
| /* Set the sorted order of tyoe B* suffixes. */ |
| for(i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) { |
| for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) { } |
| if(0 <= i) { |
| t = i; |
| for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { } |
| SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t; |
| } |
| } |
| |
| /* Calculate the index of start/end point of each bucket. */ |
| BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */ |
| for(c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) { |
| i = BUCKET_A(c0 + 1) - 1; |
| for(c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) { |
| t = i - BUCKET_B(c0, c1); |
| BUCKET_B(c0, c1) = i; /* end point */ |
| |
| /* Move all type B* suffixes to the correct position. */ |
| for(i = t, j = BUCKET_BSTAR(c0, c1); |
| j <= k; |
| --i, --k) { SA[i] = SA[k]; } |
| } |
| BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */ |
| BUCKET_B(c0, c0) = i; /* end point */ |
| } |
| } |
| |
| return m; |
| } |
| |
| /* Constructs the suffix array by using the sorted order of type B* suffixes. */ |
| static |
| void |
| construct_SA(const unsigned char *T, int *SA, |
| int *bucket_A, int *bucket_B, |
| int n, int m) { |
| int *i, *j, *k; |
| int s; |
| int c0, c1, c2; |
| |
| if(0 < m) { |
| /* Construct the sorted order of type B suffixes by using |
| the sorted order of type B* suffixes. */ |
| for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) { |
| /* Scan the suffix array from right to left. */ |
| for(i = SA + BUCKET_BSTAR(c1, c1 + 1), |
| j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; |
| i <= j; |
| --j) { |
| if(0 < (s = *j)) { |
| assert(T[s] == c1); |
| assert(((s + 1) < n) && (T[s] <= T[s + 1])); |
| assert(T[s - 1] <= T[s]); |
| *j = ~s; |
| c0 = T[--s]; |
| if((0 < s) && (T[s - 1] > c0)) { s = ~s; } |
| if(c0 != c2) { |
| if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; } |
| k = SA + BUCKET_B(c2 = c0, c1); |
| } |
| assert(k < j); assert(k != NULL); |
| *k-- = s; |
| } else { |
| assert(((s == 0) && (T[s] == c1)) || (s < 0)); |
| *j = ~s; |
| } |
| } |
| } |
| } |
| |
| /* Construct the suffix array by using |
| the sorted order of type B suffixes. */ |
| k = SA + BUCKET_A(c2 = T[n - 1]); |
| *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1); |
| /* Scan the suffix array from left to right. */ |
| for(i = SA, j = SA + n; i < j; ++i) { |
| if(0 < (s = *i)) { |
| assert(T[s - 1] >= T[s]); |
| c0 = T[--s]; |
| if((s == 0) || (T[s - 1] < c0)) { s = ~s; } |
| if(c0 != c2) { |
| BUCKET_A(c2) = k - SA; |
| k = SA + BUCKET_A(c2 = c0); |
| } |
| assert(i < k); |
| *k++ = s; |
| } else { |
| assert(s < 0); |
| *i = ~s; |
| } |
| } |
| } |
| |
| /* Constructs the burrows-wheeler transformed string directly |
| by using the sorted order of type B* suffixes. */ |
| static |
| int |
| construct_BWT(const unsigned char *T, int *SA, |
| int *bucket_A, int *bucket_B, |
| int n, int m) { |
| int *i, *j, *k, *orig; |
| int s; |
| int c0, c1, c2; |
| |
| if(0 < m) { |
| /* Construct the sorted order of type B suffixes by using |
| the sorted order of type B* suffixes. */ |
| for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) { |
| /* Scan the suffix array from right to left. */ |
| for(i = SA + BUCKET_BSTAR(c1, c1 + 1), |
| j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; |
| i <= j; |
| --j) { |
| if(0 < (s = *j)) { |
| assert(T[s] == c1); |
| assert(((s + 1) < n) && (T[s] <= T[s + 1])); |
| assert(T[s - 1] <= T[s]); |
| c0 = T[--s]; |
| *j = ~((int)c0); |
| if((0 < s) && (T[s - 1] > c0)) { s = ~s; } |
| if(c0 != c2) { |
| if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; } |
| k = SA + BUCKET_B(c2 = c0, c1); |
| } |
| assert(k < j); assert(k != NULL); |
| *k-- = s; |
| } else if(s != 0) { |
| *j = ~s; |
| #ifndef NDEBUG |
| } else { |
| assert(T[s] == c1); |
| #endif |
| } |
| } |
| } |
| } |
| |
| /* Construct the BWTed string by using |
| the sorted order of type B suffixes. */ |
| k = SA + BUCKET_A(c2 = T[n - 1]); |
| *k++ = (T[n - 2] < c2) ? ~((int)T[n - 2]) : (n - 1); |
| /* Scan the suffix array from left to right. */ |
| for(i = SA, j = SA + n, orig = SA; i < j; ++i) { |
| if(0 < (s = *i)) { |
| assert(T[s - 1] >= T[s]); |
| c0 = T[--s]; |
| *i = c0; |
| if((0 < s) && (T[s - 1] < c0)) { s = ~((int)T[s - 1]); } |
| if(c0 != c2) { |
| BUCKET_A(c2) = k - SA; |
| k = SA + BUCKET_A(c2 = c0); |
| } |
| assert(i < k); |
| *k++ = s; |
| } else if(s != 0) { |
| *i = ~s; |
| } else { |
| orig = i; |
| } |
| } |
| |
| return orig - SA; |
| } |
| |
| /* Constructs the burrows-wheeler transformed string directly |
| by using the sorted order of type B* suffixes. */ |
| static |
| int |
| construct_BWT_indexes(const unsigned char *T, int *SA, |
| int *bucket_A, int *bucket_B, |
| int n, int m, |
| unsigned char * num_indexes, int * indexes) { |
| int *i, *j, *k, *orig; |
| int s; |
| int c0, c1, c2; |
| |
| int mod = n / 8; |
| { |
| mod |= mod >> 1; mod |= mod >> 2; |
| mod |= mod >> 4; mod |= mod >> 8; |
| mod |= mod >> 16; mod >>= 1; |
| |
| *num_indexes = (unsigned char)((n - 1) / (mod + 1)); |
| } |
| |
| if(0 < m) { |
| /* Construct the sorted order of type B suffixes by using |
| the sorted order of type B* suffixes. */ |
| for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) { |
| /* Scan the suffix array from right to left. */ |
| for(i = SA + BUCKET_BSTAR(c1, c1 + 1), |
| j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; |
| i <= j; |
| --j) { |
| if(0 < (s = *j)) { |
| assert(T[s] == c1); |
| assert(((s + 1) < n) && (T[s] <= T[s + 1])); |
| assert(T[s - 1] <= T[s]); |
| |
| if ((s & mod) == 0) indexes[s / (mod + 1) - 1] = j - SA; |
| |
| c0 = T[--s]; |
| *j = ~((int)c0); |
| if((0 < s) && (T[s - 1] > c0)) { s = ~s; } |
| if(c0 != c2) { |
| if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; } |
| k = SA + BUCKET_B(c2 = c0, c1); |
| } |
| assert(k < j); assert(k != NULL); |
| *k-- = s; |
| } else if(s != 0) { |
| *j = ~s; |
| #ifndef NDEBUG |
| } else { |
| assert(T[s] == c1); |
| #endif |
| } |
| } |
| } |
| } |
| |
| /* Construct the BWTed string by using |
| the sorted order of type B suffixes. */ |
| k = SA + BUCKET_A(c2 = T[n - 1]); |
| if (T[n - 2] < c2) { |
| if (((n - 1) & mod) == 0) indexes[(n - 1) / (mod + 1) - 1] = k - SA; |
| *k++ = ~((int)T[n - 2]); |
| } |
| else { |
| *k++ = n - 1; |
| } |
| |
| /* Scan the suffix array from left to right. */ |
| for(i = SA, j = SA + n, orig = SA; i < j; ++i) { |
| if(0 < (s = *i)) { |
| assert(T[s - 1] >= T[s]); |
| |
| if ((s & mod) == 0) indexes[s / (mod + 1) - 1] = i - SA; |
| |
| c0 = T[--s]; |
| *i = c0; |
| if(c0 != c2) { |
| BUCKET_A(c2) = k - SA; |
| k = SA + BUCKET_A(c2 = c0); |
| } |
| assert(i < k); |
| if((0 < s) && (T[s - 1] < c0)) { |
| if ((s & mod) == 0) indexes[s / (mod + 1) - 1] = k - SA; |
| *k++ = ~((int)T[s - 1]); |
| } else |
| *k++ = s; |
| } else if(s != 0) { |
| *i = ~s; |
| } else { |
| orig = i; |
| } |
| } |
| |
| return orig - SA; |
| } |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| |
| /*- Function -*/ |
| |
| int |
| divsufsort(const unsigned char *T, int *SA, int n, int openMP) { |
| int *bucket_A, *bucket_B; |
| int m; |
| int err = 0; |
| |
| /* Check arguments. */ |
| if((T == NULL) || (SA == NULL) || (n < 0)) { return -1; } |
| else if(n == 0) { return 0; } |
| else if(n == 1) { SA[0] = 0; return 0; } |
| else if(n == 2) { m = (T[0] < T[1]); SA[m ^ 1] = 0, SA[m] = 1; return 0; } |
| |
| bucket_A = (int *)malloc(BUCKET_A_SIZE * sizeof(int)); |
| bucket_B = (int *)malloc(BUCKET_B_SIZE * sizeof(int)); |
| |
| /* Suffixsort. */ |
| if((bucket_A != NULL) && (bucket_B != NULL)) { |
| m = sort_typeBstar(T, SA, bucket_A, bucket_B, n, openMP); |
| construct_SA(T, SA, bucket_A, bucket_B, n, m); |
| } else { |
| err = -2; |
| } |
| |
| free(bucket_B); |
| free(bucket_A); |
| |
| return err; |
| } |
| |
| int |
| divbwt(const unsigned char *T, unsigned char *U, int *A, int n, unsigned char * num_indexes, int * indexes, int openMP) { |
| int *B; |
| int *bucket_A, *bucket_B; |
| int m, pidx, i; |
| |
| /* Check arguments. */ |
| if((T == NULL) || (U == NULL) || (n < 0)) { return -1; } |
| else if(n <= 1) { if(n == 1) { U[0] = T[0]; } return n; } |
| |
| if((B = A) == NULL) { B = (int *)malloc((size_t)(n + 1) * sizeof(int)); } |
| bucket_A = (int *)malloc(BUCKET_A_SIZE * sizeof(int)); |
| bucket_B = (int *)malloc(BUCKET_B_SIZE * sizeof(int)); |
| |
| /* Burrows-Wheeler Transform. */ |
| if((B != NULL) && (bucket_A != NULL) && (bucket_B != NULL)) { |
| m = sort_typeBstar(T, B, bucket_A, bucket_B, n, openMP); |
| |
| if (num_indexes == NULL || indexes == NULL) { |
| pidx = construct_BWT(T, B, bucket_A, bucket_B, n, m); |
| } else { |
| pidx = construct_BWT_indexes(T, B, bucket_A, bucket_B, n, m, num_indexes, indexes); |
| } |
| |
| /* Copy to output string. */ |
| U[0] = T[n - 1]; |
| for(i = 0; i < pidx; ++i) { U[i + 1] = (unsigned char)B[i]; } |
| for(i += 1; i < n; ++i) { U[i] = (unsigned char)B[i]; } |
| pidx += 1; |
| } else { |
| pidx = -2; |
| } |
| |
| free(bucket_B); |
| free(bucket_A); |
| if(A == NULL) { free(B); } |
| |
| return pidx; |
| } |