X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Fdivsufsort.c;h=c80412f5cad1f9f18478b3e4327b8fd431642d2c;hb=c68da43690263dd818fc974cfe96364f8c8d945e;hp=fe2a8ebca067b8594b21f6057807a98ae8e77438;hpb=4dd45340f9fe3a533e0f1a9d6b79f8118e45ca2a;p=wimlib diff --git a/src/divsufsort.c b/src/divsufsort.c index fe2a8ebc..c80412f5 100644 --- a/src/divsufsort.c +++ b/src/divsufsort.c @@ -29,9 +29,10 @@ #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) @@ -61,26 +62,26 @@ #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;\ @@ -110,7 +111,7 @@ static const int lg_table[256]= { #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) -static inline +static forceinline int ss_ilg(int n) { #if SS_BLOCKSIZE == 0 @@ -153,7 +154,7 @@ static const int sqq_table[256] = { 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; @@ -186,7 +187,7 @@ ss_isqrt(int x) { /*---------------------------------------------------------------------------*/ /* Compares two suffixes. */ -static inline +static forceinline int ss_compare(const unsigned char *T, const int *p1, const int *p2, @@ -237,7 +238,7 @@ ss_insertionsort(const unsigned char *T, const int *PA, #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) { @@ -279,7 +280,7 @@ ss_heapsort(const unsigned char *Td, const int *PA, int *SA, 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) { @@ -292,7 +293,7 @@ ss_median3(const unsigned char *Td, const int *PA, } /* 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) { @@ -306,7 +307,7 @@ ss_median5(const unsigned char *Td, const int *PA, } /* Returns the pivot element. */ -static inline +static forceinline int * ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) { int *middle; @@ -334,7 +335,7 @@ ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) { /*---------------------------------------------------------------------------*/ /* Binary partition for substrings. */ -static inline +static forceinline int * ss_partition(const int *PA, int *first, int *last, int depth) { @@ -495,7 +496,7 @@ ss_mintrosort(const unsigned char *T, const int *PA, #if SS_BLOCKSIZE != 0 -static inline +static forceinline void ss_blockswap(int *a, int *b, int n) { int t; @@ -504,7 +505,7 @@ ss_blockswap(int *a, int *b, int n) { } } -static inline +static forceinline void ss_rotate(int *first, int *middle, int *last) { int *a, *b, t; @@ -864,7 +865,7 @@ sssort(const unsigned char *T, const int *PA, /*---------------------------------------------------------------------------*/ -static inline +static forceinline int tr_ilg(int n) { return (n & 0xffff0000) ? @@ -899,7 +900,7 @@ tr_insertionsort(const int *ISAd, int *first, int *last) { /*---------------------------------------------------------------------------*/ -static inline +static forceinline void tr_fixdown(const int *ISAd, int *SA, int i, int size) { int j, k; @@ -940,7 +941,7 @@ tr_heapsort(const int *ISAd, int *SA, int size) { /*---------------------------------------------------------------------------*/ /* 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); } @@ -952,7 +953,7 @@ tr_median3(const int *ISAd, int *v1, int *v2, int *v3) { } /* 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) { @@ -966,7 +967,7 @@ tr_median5(const int *ISAd, } /* Returns the pivot element. */ -static inline +static forceinline int * tr_pivot(const int *ISAd, int *first, int *last) { int *middle; @@ -1001,14 +1002,14 @@ struct _trbudget_t { 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; } @@ -1021,7 +1022,7 @@ trbudget_check(trbudget_t *budget, int size) { /*---------------------------------------------------------------------------*/ -static inline +static forceinline void tr_partition(const int *ISAd, int *first, int *middle, int *last, @@ -1528,9 +1529,9 @@ construct_SA(const unsigned char *T, int *SA, 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; } @@ -1538,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); } - 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; } } @@ -1555,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)) { - 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; } } @@ -1578,8 +1579,10 @@ construct_SA(const unsigned char *T, int *SA, /* 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) {