* OTHER DEALINGS IN THE SOFTWARE.
*/
-#define assert(x)
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
#include "wimlib/divsufsort.h"
-#include <stddef.h>
+#include "wimlib/lz_mf.h"
+#include "wimlib/util.h"
/*- 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)
/*- 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);\
+ LZ_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);\
+ LZ_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);\
+ LZ_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);\
+ LZ_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;\
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; }
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); }
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; }
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); }
#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;
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]);
+ LZ_ASSERT(T[s] == c1);
+ LZ_ASSERT(((s + 1) < n) && (T[s] <= T[s + 1]));
+ LZ_ASSERT(T[s - 1] <= T[s]);
*j = ~s;
c0 = T[--s];
if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
k = SA + BUCKET_B(c2 = c0, c1);
}
- assert(k < j);
+ LZ_ASSERT(k < j);
*k-- = s;
} else {
- assert(((s == 0) && (T[s] == c1)) || (s < 0));
+ LZ_ASSERT(((s == 0) && (T[s] == c1)) || (s < 0));
*j = ~s;
}
}
/* 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]);
+ LZ_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);
+ LZ_ASSERT(i < k);
*k++ = s;
} else {
- assert(s < 0);
+ LZ_ASSERT(s < 0);
*i = ~s;
}
}
/* 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 *bucket_A, u32 *bucket_B)
{
- int m;
+ u32 m;
switch (n) {
case 0: