From 4fdbe71797efad633d279d9c1450d99bcdae2312 Mon Sep 17 00:00:00 2001 From: "Juan J. Martinez" Date: Tue, 6 Sep 2022 07:41:28 +0100 Subject: Updated apultra to 1.4.7 --- tools/apultra/src/apultra.c | 2 +- tools/apultra/src/matchfinder.c | 23 ++++---- tools/apultra/src/matchfinder.h | 15 ----- tools/apultra/src/shrink.c | 119 +++++++++++++++++++++------------------- 4 files changed, 76 insertions(+), 83 deletions(-) (limited to 'tools/apultra/src') diff --git a/tools/apultra/src/apultra.c b/tools/apultra/src/apultra.c index a6c3c38..40990dd 100644 --- a/tools/apultra/src/apultra.c +++ b/tools/apultra/src/apultra.c @@ -45,7 +45,7 @@ #define OPT_STATS 2 #define OPT_BACKWARD 4 -#define TOOL_VERSION "1.4.6" +#define TOOL_VERSION "1.4.7" /*---------------------------------------------------------------------------*/ diff --git a/tools/apultra/src/matchfinder.c b/tools/apultra/src/matchfinder.c index 7b17e0e..c3a30f3 100644 --- a/tools/apultra/src/matchfinder.c +++ b/tools/apultra/src/matchfinder.c @@ -186,11 +186,11 @@ int apultra_build_suffix_array(apultra_compressor *pCompressor, const unsigned c * @param pMatchDepth pointer to returned match depths * @param pMatch1 pointer to 1-byte length, 4 bit offset match * @param nMaxMatches maximum number of matches to return (0 for none) - * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise + * @param nIsSelfContainedBlock 1 if block contains all of the data to be compressesd, 0 if this block is part of more blocks * * @return number of matches */ -int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, apultra_match *pMatches, unsigned short *pMatchDepth, unsigned char *pMatch1, const int nMaxMatches, const int nBlockFlags) { +static int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, apultra_match *pMatches, unsigned short *pMatchDepth, unsigned char *pMatch1, const int nMaxMatches, const int nIsSelfContainedBlock) { unsigned long long *intervals = pCompressor->intervals; unsigned long long *pos_data = pCompressor->pos_data; unsigned long long ref; @@ -240,7 +240,7 @@ int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, int nCurDepth = 0; unsigned short *cur_depth = NULL; - if (nOffset >= match_pos && (nBlockFlags & 3) == 3) { + if (nOffset >= match_pos && nIsSelfContainedBlock) { const int nMatchOffset = (const int)(nOffset - match_pos); if ((matchptr - pMatches) < nMaxMatches) { @@ -266,7 +266,7 @@ int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, if ((super_ref = pos_data[match_pos]) > ref) { match_pos = intervals[super_ref & POS_MASK] & EXCL_VISITED_MASK; - if (nOffset >= match_pos && (nBlockFlags & 3) == 3) { + if (nOffset >= match_pos && nIsSelfContainedBlock) { const int nMatchOffset = (const int)(nOffset - match_pos); if ((matchptr - pMatches) < nMaxMatches) { @@ -298,7 +298,7 @@ int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, while ((super_ref = pos_data[match_pos]) > ref) { match_pos = intervals[super_ref & POS_MASK] & EXCL_VISITED_MASK; - if (nOffset > match_pos && (nBlockFlags & 3) == 3) { + if (nOffset > match_pos && nIsSelfContainedBlock) { const int nMatchOffset = (const int)(nOffset - match_pos); if ((matchptr - pMatches) < nMaxMatches) { @@ -363,7 +363,7 @@ int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, ref = super_ref; match_pos = intervals[ref & POS_MASK] & EXCL_VISITED_MASK; - if (nOffset > match_pos && (nBlockFlags & 3) == 3) { + if (nOffset > match_pos && nIsSelfContainedBlock) { const int nMatchOffset = (const int)(nOffset - match_pos); if ((matchptr - pMatches) < nMaxMatches) { @@ -428,16 +428,15 @@ void apultra_find_all_matches(apultra_compressor *pCompressor, const int nMatche apultra_match *pMatch = pCompressor->match; unsigned short *pMatchDepth = pCompressor->match_depth; unsigned char *pMatch1 = pCompressor->match1; + const int nIsSelfContainedBlock = ((nBlockFlags & 3) == 3) ? 1 : 0; int i; for (i = nStartOffset; i < nEndOffset; i++) { - int nMatches = apultra_find_matches_at(pCompressor, i, pMatch, pMatchDepth, pMatch1, nMatchesPerOffset, nBlockFlags); + const int nMatches = apultra_find_matches_at(pCompressor, i, pMatch, pMatchDepth, pMatch1, nMatchesPerOffset, nIsSelfContainedBlock); - while (nMatches < nMatchesPerOffset) { - pMatch[nMatches].length = 0; - pMatch[nMatches].offset = 0; - pMatchDepth[nMatches] = 0; - nMatches++; + if (nMatches < nMatchesPerOffset) { + memset(&pMatch[nMatches], 0, sizeof(apultra_match) * (nMatchesPerOffset - nMatches)); + memset(&pMatchDepth[nMatches], 0, sizeof(unsigned short) * (nMatchesPerOffset - nMatches)); } pMatch += nMatchesPerOffset; diff --git a/tools/apultra/src/matchfinder.h b/tools/apultra/src/matchfinder.h index 7d68eaf..7fba5ce 100644 --- a/tools/apultra/src/matchfinder.h +++ b/tools/apultra/src/matchfinder.h @@ -52,21 +52,6 @@ typedef struct _apultra_compressor apultra_compressor; */ int apultra_build_suffix_array(apultra_compressor *pCompressor, const unsigned char *pInWindow, const int nInWindowSize); -/** - * Find matches at the specified offset in the input window - * - * @param pCompressor compression context - * @param nOffset offset to find matches at, in the input window - * @param pMatches pointer to returned matches - * @param pMatchDepth pointer to returned match depths - * @param pMatch1 pointer to 1-byte length, 4 bit offset match - * @param nMaxMatches maximum number of matches to return (0 for none) - * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise - * - * @return number of matches - */ -int apultra_find_matches_at(apultra_compressor *pCompressor, const int nOffset, apultra_match *pMatches, unsigned short *pMatchDepth, unsigned char *pMatch1, const int nMaxMatches, const int nBlockFlags); - /** * Skip previously compressed bytes * diff --git a/tools/apultra/src/shrink.c b/tools/apultra/src/shrink.c index 8e123e0..dec3566 100644 --- a/tools/apultra/src/shrink.c +++ b/tools/apultra/src/shrink.c @@ -189,7 +189,7 @@ static inline int apultra_get_match_varlen_size(int nLength, const int nMatchOff * @param nArrivalsPerPosition maximum number of arrivals per input buffer position * @param nDepth current insertion depth */ -static void apultra_insert_forward_match(apultra_compressor *pCompressor, const unsigned char *pInWindow, const int i, const int nMatchOffset, const int nStartOffset, const int nEndOffset, const int nArrivalsPerPosition, int nDepth) { +static void apultra_insert_forward_match(apultra_compressor *pCompressor, const unsigned char *pInWindow, const int i, const int nMatchOffset, const int nStartOffset, const int nEndOffset, const int nArrivalsPerPosition, const int nDepth) { const apultra_arrival *arrival = pCompressor->arrival + ((i - nStartOffset) * nArrivalsPerPosition); const int *rle_len = (const int*)pCompressor->intervals /* reuse */; apultra_visited* visited = ((apultra_visited*)pCompressor->pos_data) - nStartOffset /* reuse */; @@ -208,56 +208,60 @@ static void apultra_insert_forward_match(apultra_compressor *pCompressor, const visited[nRepPos] = nMatchOffset; - if (nRepPos >= nMatchOffset && nRepOffset && pCompressor->match[((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT) + NMATCHES_PER_INDEX - 1].length == 0) { - const unsigned char* pInWindowStart = pInWindow + nRepPos; + apultra_match* fwd_match = pCompressor->match + ((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT); - if (!memcmp(pInWindowStart, pInWindowStart - nMatchOffset, 2)) { - const int nLen0 = rle_len[nRepPos - nMatchOffset]; - const int nLen1 = rle_len[nRepPos]; - const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; + if (fwd_match[NMATCHES_PER_INDEX - 1].length == 0) { + if (nRepPos >= nMatchOffset) { + const unsigned char* pInWindowStart = pInWindow + nRepPos; - int nMaxRepLen = nEndOffset - nRepPos; - if (nMaxRepLen > LCP_MAX) - nMaxRepLen = LCP_MAX; + if (!memcmp(pInWindowStart, pInWindowStart - nMatchOffset, 2)) { + if (nRepOffset) { + const int nLen0 = rle_len[nRepPos - nMatchOffset]; + const int nLen1 = rle_len[nRepPos]; + const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; - const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLen; - const unsigned char* pInWindowAtRepOffset = pInWindowStart + nMinLen; + int nMaxRepLen = nEndOffset - nRepPos; + if (nMaxRepLen > LCP_MAX) + nMaxRepLen = LCP_MAX; - if (pInWindowAtRepOffset > pInWindowMax) - pInWindowAtRepOffset = pInWindowMax; + const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLen; + const unsigned char* pInWindowAtRepOffset = pInWindowStart + nMinLen; - while ((pInWindowAtRepOffset + 8) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 8)) - pInWindowAtRepOffset += 8; - while ((pInWindowAtRepOffset + 4) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 4)) - pInWindowAtRepOffset += 4; - while (pInWindowAtRepOffset < pInWindowMax && pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nMatchOffset]) - pInWindowAtRepOffset++; + if (pInWindowAtRepOffset > pInWindowMax) + pInWindowAtRepOffset = pInWindowMax; - const int nCurRepLen = (const int)(pInWindowAtRepOffset - pInWindowStart); + while ((pInWindowAtRepOffset + 8) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 8)) + pInWindowAtRepOffset += 8; + while ((pInWindowAtRepOffset + 4) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 4)) + pInWindowAtRepOffset += 4; + while (pInWindowAtRepOffset < pInWindowMax && pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nMatchOffset]) + pInWindowAtRepOffset++; - apultra_match* fwd_match = pCompressor->match + ((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT); - unsigned short* fwd_depth = pCompressor->match_depth + ((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT); - int r; + const int nCurRepLen = (const int)(pInWindowAtRepOffset - pInWindowStart); - for (r = 0; fwd_match[r].length; r++) { - if (fwd_match[r].offset == nMatchOffset && (fwd_depth[r] & 0x3fff) == 0) { - if ((int)fwd_match[r].length < nCurRepLen) { + unsigned short* fwd_depth = pCompressor->match_depth + ((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT); + int r; + + for (r = 0; fwd_match[r].length; r++) { + if (fwd_match[r].offset == nMatchOffset && (fwd_depth[r] & 0x3fff) == 0) { + if ((const int)fwd_match[r].length < nCurRepLen) { + fwd_match[r].length = nCurRepLen; + fwd_depth[r] = 0; + } + break; + } + } + + if (fwd_match[r].length == 0) { fwd_match[r].length = nCurRepLen; + fwd_match[r].offset = nMatchOffset; fwd_depth[r] = 0; + + if (nDepth < 9) + apultra_insert_forward_match(pCompressor, pInWindow, nRepPos, nMatchOffset, nStartOffset, nEndOffset, nArrivalsPerPosition, nDepth + 1); } - r = NMATCHES_PER_INDEX; - break; } } - - if (r < NMATCHES_PER_INDEX) { - fwd_match[r].offset = nMatchOffset; - fwd_match[r].length = nCurRepLen; - fwd_depth[r] = 0; - - if (nDepth < 9) - apultra_insert_forward_match(pCompressor, pInWindow, nRepPos, nMatchOffset, nStartOffset, nEndOffset, nArrivalsPerPosition, nDepth + 1); - } } } } @@ -316,16 +320,16 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi if ((pInWindow[i] != 0 && nMatch1Offs == 0) || (i == nStartOffset && (nBlockFlags & 1))) { nShortOffset = 0; nShortLen = 0; + nLiteralScore = 1; nLiteralCost = 9 /* literal bit + literal byte */; } else { - nShortOffset = (pInWindow[i] == 0) ? 0 : nMatch1Offs; + nShortOffset = (pInWindow[i] != 0) ? nMatch1Offs : 0; nShortLen = 1; + nLiteralScore = nShortOffset ? 3 : 1; nLiteralCost = 4 + TOKEN_SIZE_4BIT_MATCH /* command and offset cost; no length cost */; } - nLiteralScore = nShortOffset ? 3 : 1; - if (cur_arrival[nArrivalsPerPosition].from_slot) { apultra_arrival* pDestSlots = &cur_arrival[nArrivalsPerPosition]; @@ -398,12 +402,9 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi } else { for (j = 0; j < nArrivalsPerPosition && cur_arrival[j].from_slot; j++) { - const int nCodingChoiceCost = cur_arrival[j].cost + nLiteralCost; - const int nScore = cur_arrival[j].score + nLiteralScore; - apultra_arrival* pDestArrival = &cur_arrival[nArrivalsPerPosition + j]; - pDestArrival->cost = nCodingChoiceCost; + pDestArrival->cost = cur_arrival[j].cost + nLiteralCost; pDestArrival->from_pos = i; pDestArrival->from_slot = j + 1; pDestArrival->follows_literal = 1; @@ -411,7 +412,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi pDestArrival->short_offset = nShortOffset; pDestArrival->rep_pos = cur_arrival[j].rep_pos; pDestArrival->match_len = nShortLen; - pDestArrival->score = nScore; + pDestArrival->score = cur_arrival[j].score + nLiteralScore; } } @@ -473,7 +474,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi int nOrigMatchLen = match[m].length; const int nOrigMatchOffset = match[m].offset; const unsigned int nOrigMatchDepth = match_depth[m] & 0x3fff; - const int nScorePenalty = 3 + ((match_depth[m] & 0x8000) >> 15); + const int nScorePenalty = 3 + (match_depth[m] >> 15); unsigned int d; if ((i + nOrigMatchLen) > nEndOffset) @@ -731,7 +732,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi const apultra_arrival* end_arrival = &arrival[(i * nArrivalsPerPosition) + 0]; apultra_final_match* pBestMatch = pCompressor->best_match - nStartOffset; - while (end_arrival->from_slot > 0 && end_arrival->from_pos >= 0 && (int)end_arrival->from_pos < nEndOffset) { + while (end_arrival->from_slot > 0 && end_arrival->from_pos >= 0 && (const int)end_arrival->from_pos < nEndOffset) { pBestMatch[end_arrival->from_pos].length = end_arrival->match_len; pBestMatch[end_arrival->from_pos].offset = (end_arrival->match_len >= 2) ? end_arrival->rep_offset : end_arrival->short_offset; @@ -761,7 +762,7 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign int nLastMatchLen = 0; const unsigned char *match1 = pCompressor->match1 - nStartOffset; - for (i = nStartOffset + ((nBlockFlags & 1) ? 1 : 0); i < nEndOffset; ) { + for (i = nStartOffset + (nBlockFlags & 1); i < nEndOffset; ) { apultra_final_match *pMatch = pBestMatch + i; if (pMatch->length <= 1 && @@ -934,7 +935,7 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign } } - if (!nCannotEncode && nOriginalCombinedCommandSize > nReducedCommandSize) { + if (nOriginalCombinedCommandSize > nReducedCommandSize && !nCannotEncode) { /* Reduce */ const int nMatchLen = pMatch->length; int j; @@ -1012,8 +1013,8 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign } } - if (!nCannotEncode) { - if (nCurCommandSize >= nReducedCommandSize) { + if (nCurCommandSize >= nReducedCommandSize) { + if (!nCannotEncode) { pMatch->length += pBestMatch[i + nMatchLen].length; pBestMatch[i + nMatchLen].length = 0; pBestMatch[i + nMatchLen].offset = 0; @@ -1072,7 +1073,7 @@ static int apultra_write_block(apultra_compressor *pCompressor, apultra_final_ma nCurFollowsLiteral = 1; } - for (i = nStartOffset + ((nBlockFlags & 1) ? 1 : 0); i < nEndOffset; ) { + for (i = nStartOffset + (nBlockFlags & 1); i < nEndOffset; ) { const apultra_final_match *pMatch = pBestMatch + i; if (pMatch->length >= 2) { @@ -1369,9 +1370,13 @@ static int apultra_optimize_and_write_block(apultra_compressor *pCompressor, con if (match_depth[nExistingMatchIdx] == 0x4000) { int nMatchLen = 2; - while (nMatchLen < 16 && nPosition < (nEndOffset - nMatchLen) && pInWindow[nMatchPos + nMatchLen] == pInWindow[nPosition + nMatchLen]) + while ((nMatchLen + 8) < 16 && (nPosition + nMatchLen + 8) < nEndOffset && !memcmp(pInWindow + nMatchPos + nMatchLen, pInWindow + nPosition + nMatchLen, 8)) + nMatchLen += 8; + while ((nMatchLen + 4) < 16 && (nPosition + nMatchLen + 4) < nEndOffset && !memcmp(pInWindow + nMatchPos + nMatchLen, pInWindow + nPosition + nMatchLen, 4)) + nMatchLen += 4; + while (nMatchLen < 16 && (nPosition + nMatchLen) < nEndOffset && pInWindow[nMatchPos + nMatchLen] == pInWindow[nPosition + nMatchLen]) nMatchLen++; - if (nMatchLen > (int)match[nExistingMatchIdx].length) + if (nMatchLen > (const int)match[nExistingMatchIdx].length) match[nExistingMatchIdx].length = nMatchLen; } @@ -1396,6 +1401,10 @@ static int apultra_optimize_and_write_block(apultra_compressor *pCompressor, con if (nGotMatch) { int nMatchLen = 2; + while ((nMatchLen + 8) < 16 && (nPosition + nMatchLen + 8) < nEndOffset && !memcmp(pInWindow + nMatchPos + nMatchLen, pInWindow + nPosition + nMatchLen, 8)) + nMatchLen += 8; + while ((nMatchLen + 4) < 16 && (nPosition + nMatchLen + 4) < nEndOffset && !memcmp(pInWindow + nMatchPos + nMatchLen, pInWindow + nPosition + nMatchLen, 4)) + nMatchLen += 4; while (nMatchLen < 16 && (nPosition + nMatchLen) < nEndOffset && pInWindow[nMatchPos + nMatchLen] == pInWindow[nPosition + nMatchLen]) nMatchLen++; match[m].length = nMatchLen; -- cgit v1.2.3