X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fdivsufsort.c;h=6753695657b6ed09b36925279f3eb03a6f1b6ee5;hp=6353a9583518b62a7bc32238bacfcf40b5d49b0f;hb=658ee1d652613948b29c412d75b3732801c2a235;hpb=260370b878a0b1d2351164ae882407ba7de52616 diff --git a/src/divsufsort.c b/src/divsufsort.c index 6353a958..67536956 100644 --- a/src/divsufsort.c +++ b/src/divsufsort.c @@ -24,39 +24,24 @@ * OTHER DEALINGS IN THE SOFTWARE. */ -#define assert(x) +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif #include "wimlib/divsufsort.h" -#include +#include "wimlib/util.h" + +#define DIVSUFSORT_ASSERT(expr) /*- Constants -*/ -#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1) -# undef ALPHABET_SIZE -#endif -#if !defined(ALPHABET_SIZE) -# define ALPHABET_SIZE (256) -#endif +#define ALPHABET_SIZE 256 #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 + +#define SS_INSERTIONSORT_THRESHOLD 8 + +#define SS_BLOCKSIZE 1024 + /* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ #if SS_BLOCKSIZE == 0 # define SS_MISORT_STACKSIZE (96) @@ -71,37 +56,32 @@ /*- 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 SWAP swap +#define MIN min +#define MAX max + #define STACK_PUSH(_a, _b, _c, _d)\ do {\ - assert(ssize < STACK_SIZE);\ + DIVSUFSORT_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);\ + DIVSUFSORT_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);\ + DIVSUFSORT_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);\ + DIVSUFSORT_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;\ @@ -304,7 +284,6 @@ 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; } @@ -318,7 +297,6 @@ 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); } @@ -966,7 +944,6 @@ tr_heapsort(const int *ISAd, int *SA, int size) { 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; } @@ -980,7 +957,6 @@ 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); } @@ -1159,7 +1135,6 @@ tr_introsort(int *ISA, const int *ISAd, #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; @@ -1554,9 +1529,9 @@ construct_SA(const unsigned char *T, int *SA, 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]); + DIVSUFSORT_ASSERT(T[s] == c1); + DIVSUFSORT_ASSERT(((s + 1) < n) && (T[s] <= T[s + 1])); + DIVSUFSORT_ASSERT(T[s - 1] <= T[s]); *j = ~s; c0 = T[--s]; if((0 < s) && (T[s - 1] > c0)) { s = ~s; } @@ -1564,10 +1539,10 @@ construct_SA(const unsigned char *T, int *SA, if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; } k = SA + BUCKET_B(c2 = c0, c1); } - assert(k < j); + DIVSUFSORT_ASSERT(k < j); *k-- = s; } else { - assert(((s == 0) && (T[s] == c1)) || (s < 0)); + DIVSUFSORT_ASSERT(((s == 0) && (T[s] == c1)) || (s < 0)); *j = ~s; } } @@ -1581,17 +1556,17 @@ construct_SA(const unsigned char *T, int *SA, /* 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]); + DIVSUFSORT_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); + DIVSUFSORT_ASSERT(i < k); *k++ = s; } else { - assert(s < 0); + DIVSUFSORT_ASSERT(s < 0); *i = ~s; } } @@ -1604,10 +1579,11 @@ construct_SA(const unsigned char *T, int *SA, /* XXX Modified from original: use provided temporary space instead of * allocating it. */ void -divsufsort(const unsigned char *T, int *SA, int n, - int *bucket_A, int *bucket_B) +divsufsort(const u8 *T, u32 *SA, u32 n, u32 *tmp) { - int m; + u32 *bucket_A = tmp; + u32 *bucket_B = tmp + BUCKET_A_SIZE; + u32 m; switch (n) { case 0: