#endif
#include "wimlib/divsufsort.h"
-#include "wimlib/lz_mf.h"
#include "wimlib/util.h"
+#define DIVSUFSORT_ASSERT(expr)
+
/*- Constants -*/
#define ALPHABET_SIZE 256
#define BUCKET_A_SIZE (ALPHABET_SIZE)
#define STACK_PUSH(_a, _b, _c, _d)\
do {\
- LZ_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 {\
- LZ_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 {\
- LZ_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 {\
- LZ_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;\
#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
-static inline
+static forceinline
int
ss_ilg(int n) {
#if SS_BLOCKSIZE == 0
247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255
};
-static inline
+static forceinline
int
ss_isqrt(int x) {
int y, e;
/*---------------------------------------------------------------------------*/
/* Compares two suffixes. */
-static inline
+static forceinline
int
ss_compare(const unsigned char *T,
const int *p1, const int *p2,
#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
-static inline
+static forceinline
void
ss_fixdown(const unsigned char *Td, const int *PA,
int *SA, int i, int size) {
/*---------------------------------------------------------------------------*/
/* Returns the median of three elements. */
-static inline
+static forceinline
int *
ss_median3(const unsigned char *Td, const int *PA,
int *v1, int *v2, int *v3) {
}
/* Returns the median of five elements. */
-static inline
+static forceinline
int *
ss_median5(const unsigned char *Td, const int *PA,
int *v1, int *v2, int *v3, int *v4, int *v5) {
}
/* Returns the pivot element. */
-static inline
+static forceinline
int *
ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) {
int *middle;
/*---------------------------------------------------------------------------*/
/* Binary partition for substrings. */
-static inline
+static forceinline
int *
ss_partition(const int *PA,
int *first, int *last, int depth) {
#if SS_BLOCKSIZE != 0
-static inline
+static forceinline
void
ss_blockswap(int *a, int *b, int n) {
int t;
}
}
-static inline
+static forceinline
void
ss_rotate(int *first, int *middle, int *last) {
int *a, *b, t;
/*---------------------------------------------------------------------------*/
-static inline
+static forceinline
int
tr_ilg(int n) {
return (n & 0xffff0000) ?
/*---------------------------------------------------------------------------*/
-static inline
+static forceinline
void
tr_fixdown(const int *ISAd, int *SA, int i, int size) {
int j, k;
/*---------------------------------------------------------------------------*/
/* Returns the median of three elements. */
-static inline
+static forceinline
int *
tr_median3(const int *ISAd, int *v1, int *v2, int *v3) {
if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); }
}
/* Returns the median of five elements. */
-static inline
+static forceinline
int *
tr_median5(const int *ISAd,
int *v1, int *v2, int *v3, int *v4, int *v5) {
}
/* Returns the pivot element. */
-static inline
+static forceinline
int *
tr_pivot(const int *ISAd, int *first, int *last) {
int *middle;
int count;
};
-static inline
+static forceinline
void
trbudget_init(trbudget_t *budget, int chance, int incval) {
budget->chance = chance;
budget->remain = budget->incval = incval;
}
-static inline
+static forceinline
int
trbudget_check(trbudget_t *budget, int size) {
if(size <= budget->remain) { budget->remain -= size; return 1; }
/*---------------------------------------------------------------------------*/
-static inline
+static forceinline
void
tr_partition(const int *ISAd,
int *first, int *middle, int *last,
i <= j;
--j) {
if(0 < (s = *j)) {
- LZ_ASSERT(T[s] == c1);
- LZ_ASSERT(((s + 1) < n) && (T[s] <= T[s + 1]));
- LZ_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; }
if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
k = SA + BUCKET_B(c2 = c0, c1);
}
- LZ_ASSERT(k < j);
+ DIVSUFSORT_ASSERT(k < j);
*k-- = s;
} else {
- LZ_ASSERT(((s == 0) && (T[s] == c1)) || (s < 0));
+ DIVSUFSORT_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)) {
- LZ_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);
}
- LZ_ASSERT(i < k);
+ DIVSUFSORT_ASSERT(i < k);
*k++ = s;
} else {
- LZ_ASSERT(s < 0);
+ DIVSUFSORT_ASSERT(s < 0);
*i = ~s;
}
}
/* XXX Modified from original: use provided temporary space instead of
* allocating it. */
void
-divsufsort(const u8 *T, u32 *SA, u32 n, u32 *bucket_A, u32 *bucket_B)
+divsufsort(const u8 *T, u32 *SA, u32 n, u32 *tmp)
{
+ u32 *bucket_A = tmp;
+ u32 *bucket_B = tmp + BUCKET_A_SIZE;
u32 m;
switch (n) {