From d46a448e9d44f62cb49ae917c69d8a2415e08a9e Mon Sep 17 00:00:00 2001 From: "Juan J. Martinez" Date: Wed, 8 Sep 2021 16:17:29 +0100 Subject: Updated apultra to version 1.4.2 --- CHANGES.md | 4 + tools/apultra/README.md | 13 +- tools/apultra/src/apultra.c | 2 +- tools/apultra/src/expand.c | 4 +- tools/apultra/src/shrink.c | 325 ++++++++++++++++++++++---------------------- tools/apultra/src/shrink.h | 8 +- 6 files changed, 185 insertions(+), 171 deletions(-) diff --git a/CHANGES.md b/CHANGES.md index fc295db..f85222c 100644 --- a/CHANGES.md +++ b/CHANGES.md @@ -1,5 +1,9 @@ # What's new? +## Release 1.1.8 - 2021-??-?? + + - Updated apultra to 1.4.2 + ## Release 1.1.7 - 2021-06-24 - Documented the auxiliary tools used to build the example game diff --git a/tools/apultra/README.md b/tools/apultra/README.md index 9dc1e74..d25794e 100644 --- a/tools/apultra/README.md +++ b/tools/apultra/README.md @@ -1,18 +1,18 @@ -apultra -- a new, opensource optimal compressor for the apLib format +apultra -- a new, opensource optimal compressor for the aPLib format ==================================================================== -apultra is a command-line tool and a library that compresses bitstreams in the apLib format. +apultra is a command-line tool and a library that compresses bitstreams in the aPLib format. -The tool produces files that are 5 to 7% smaller on average than appack, the apLib compressor. Unlike the similar [cap](https://github.com/svendahl/cap) compressor, apultra can compress files larger than 64K. +The tool produces files that are 5 to 7% smaller on average than appack, the aPLib compressor. Unlike the similar [cap](https://github.com/svendahl/cap) compressor, apultra can compress files larger than 64K. -apultra is written in portable C. It is fully open-source under a liberal license. You can continue to use the regular apLib decompression libraries for your target environment. You can do whatever you like with it. +apultra is written in portable C. It is fully open-source under a liberal license. You can continue to use the regular aPLib decompression libraries for your target environment. You can do whatever you like with it. Example compression with vmlinux-5.3.0-1-amd64 original 27923676 (100,00%) appack 7370129 (26,39%) gzip 1.8 7166179 (25,66%) - apultra 1.3.5 6910729 (24,75%) + apultra 1.4.1 6910729 (24,75%) The output is fully compatible with the original [aPLib](http://ibsensoftware.com/products_aPLib.html) by Jørgen Ibsen. @@ -26,6 +26,7 @@ Inspirations: Some projects that use apultra for compression: * [Brick Rick](https://www.usebox.net/jjm/brick-rick/), a new game for the Amstrad CPC 464/6128 by usebox.net. A physical copy can be ordered from [Polyplay](https://www.polyplay.xyz/navi.php?suche=Brick+Rick&lang=eng) + * [Brick Rick: Graveyard Shift](https://www.usebox.net/jjm/graveyard-shift/), a similar new game for the ZX Spectrum 128K by usebox.net. Get it on tape from [TFW8b.com](https://www.thefuturewas8bit.com/cas019.html) * [Kitsune's Curse](https://www.usebox.net/jjm/kitsunes-curse/), another new title for the CPC line by usebox.net. * [Sgt. Helmet's Training Day](https://www.mojontwins.com/juegos_mojonos/sgt-helmet-training-day-2020-cpc/), a new game for the Amstrad CPC by the Mojon Twins (using their MK1 engine). * [Prince Dastan - Sokoban Within](https://www.pouet.net/prod.php?which=87382), a CPCRetroDev 2020 game for the Amstrad CPC by Euphoria Design @@ -35,7 +36,7 @@ Some projects that use apultra for compression: Also of interest: * [oapack](https://gitlab.com/eugene77/oapack) by Eugene Larchenko, a brute-force (exhaustive) optimal packer for the aPLib format. - * [i8080 decompressors](https://gitlab.com/ivagor/unapack) for aPLib by Ivan Gorodetsky + * [Streamed 8088 decompressor](https://hg.ulukai.org/ecm/inicomp/file/4c6ae7774f3a/apl.asm) for aPLib by C. Masloch * [Gameboy decompressor](https://github.com/untoxa/UnaPACK.GBZ80) by untoxa License: diff --git a/tools/apultra/src/apultra.c b/tools/apultra/src/apultra.c index 1b30fbe..d59a415 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.0" +#define TOOL_VERSION "1.4.2" /*---------------------------------------------------------------------------*/ diff --git a/tools/apultra/src/expand.c b/tools/apultra/src/expand.c index 76b3bf1..b65409d 100644 --- a/tools/apultra/src/expand.c +++ b/tools/apultra/src/expand.c @@ -97,7 +97,7 @@ size_t apultra_get_max_decompressed_size(const unsigned char *pInputData, size_t nDecompressedSize++; while (1) { - unsigned int nResult; + int nResult; nResult = apultra_read_bit(&pInputData, pInputDataEnd, &nCurBitMask, &bits); if (nResult < 0) return -1; @@ -222,7 +222,7 @@ size_t apultra_decompress(const unsigned char *pInputData, unsigned char *pOutDa *pCurOutData++ = *pInputData++; while (1) { - unsigned int nResult; + int nResult; nResult = apultra_read_bit(&pInputData, pInputDataEnd, &nCurBitMask, &bits); if (nResult < 0) return -1; diff --git a/tools/apultra/src/shrink.c b/tools/apultra/src/shrink.c index c6c9826..5859790 100644 --- a/tools/apultra/src/shrink.c +++ b/tools/apultra/src/shrink.c @@ -200,7 +200,7 @@ static inline int apultra_get_match_varlen_size(int nLength, const int nMatchOff 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) { const apultra_arrival *arrival = pCompressor->arrival + ((i - nStartOffset) * nArrivalsPerPosition); const int *rle_len = (int*)pCompressor->intervals /* reuse */; - int* visited = ((int*)pCompressor->pos_data) - nStartOffset /* reuse */; + apultra_visited* visited = ((apultra_visited*)pCompressor->pos_data) - nStartOffset /* reuse */; int j; for (j = 0; j < nArrivalsPerPosition && arrival[j].from_slot; j++) { @@ -211,15 +211,17 @@ static void apultra_insert_forward_match(apultra_compressor *pCompressor, const int nRepPos = arrival[j].rep_pos; if (nRepPos >= nStartOffset && - nRepPos < nEndOffset && - visited[nRepPos] != nMatchOffset) { + (nRepPos + 1) < nEndOffset && + visited[nRepPos].outer != nMatchOffset) { - visited[nRepPos] = nMatchOffset; + visited[nRepPos].outer = nMatchOffset; - if (nRepPos >= nMatchOffset && pCompressor->match[((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT) + NMATCHES_PER_INDEX - 1].length == 0) { + if (visited[nRepPos].inner != nMatchOffset && nRepPos >= nMatchOffset && pCompressor->match[((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT) + NMATCHES_PER_INDEX - 1].length == 0) { const unsigned char* pInWindowAtRepOffset = pInWindow + nRepPos; - if (pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nMatchOffset]) { + if (!memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 2)) { + visited[nRepPos].inner = nMatchOffset; + int nLen0 = rle_len[nRepPos - nMatchOffset]; int nLen1 = rle_len[nRepPos]; int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; @@ -243,30 +245,28 @@ static void apultra_insert_forward_match(apultra_compressor *pCompressor, const int nCurRepLen = (int)(pInWindowAtRepOffset - (pInWindow + nRepPos)); - if (nCurRepLen >= 2) { - 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; + 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; - for (r = 0; fwd_match[r].length >= MIN_MATCH_SIZE; r++) { - if (fwd_match[r].offset == nMatchOffset && (fwd_depth[r] & 0x3fff) == 0) { - if ((int)fwd_match[r].length < nCurRepLen) { - fwd_match[r].length = nCurRepLen; - fwd_depth[r] = 0; - } - r = NMATCHES_PER_INDEX; - break; + for (r = 0; fwd_match[r].length >= MIN_MATCH_SIZE; r++) { + if (fwd_match[r].offset == nMatchOffset && (fwd_depth[r] & 0x3fff) == 0) { + if ((int)fwd_match[r].length < nCurRepLen) { + fwd_match[r].length = nCurRepLen; + fwd_depth[r] = 0; } + 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 (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); - } + if (nDepth < 9) + apultra_insert_forward_match(pCompressor, pInWindow, nRepPos, nMatchOffset, nStartOffset, nEndOffset, nArrivalsPerPosition, nDepth + 1); } } } @@ -291,7 +291,7 @@ static void apultra_insert_forward_match(apultra_compressor *pCompressor, const static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsigned char *pInWindow, const int nStartOffset, const int nEndOffset, const int nInsertForwardReps, const int *nCurRepMatchOffset, const int nBlockFlags, const int nArrivalsPerPosition) { apultra_arrival *arrival = pCompressor->arrival - (nStartOffset * nArrivalsPerPosition); const int* rle_len = (int*)pCompressor->intervals /* reuse */; - int* visited = ((int*)pCompressor->pos_data) - nStartOffset /* reuse */; + apultra_visited* visited = ((apultra_visited*)pCompressor->pos_data) - nStartOffset /* reuse */; int i, j, n; if ((nEndOffset - nStartOffset) > pCompressor->block_size) return; @@ -306,7 +306,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi } if (nInsertForwardReps) { - memset(visited + nStartOffset, 0, (nEndOffset - nStartOffset) * sizeof(int)); + memset(visited + nStartOffset, 0, (nEndOffset - nStartOffset) * sizeof(apultra_visited)); } for (i = nStartOffset; i != nEndOffset; i++) { @@ -345,7 +345,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi int exists = 0; for (n = 0; - n < nArrivalsPerPosition && pDestSlots[n].cost < nCodingChoiceCost; + pDestSlots[n].cost < nCodingChoiceCost; n++) { if (pDestSlots[n].rep_offset == nRepOffset) { exists = 1; @@ -355,7 +355,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi if (!exists) { for (; - n < nArrivalsPerPosition && pDestSlots[n].cost == nCodingChoiceCost && nScore >= pDestSlots[n].score; + pDestSlots[n].cost == nCodingChoiceCost && nScore >= pDestSlots[n].score; n++) { if (pDestSlots[n].rep_offset == nRepOffset) { exists = 1; @@ -364,41 +364,39 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi } if (!exists) { - if (n < nArrivalsPerPosition) { - int nn; - - for (nn = n; - nn < nArrivalsPerPosition && pDestSlots[nn].cost == nCodingChoiceCost; - nn++) { - if (pDestSlots[nn].rep_offset == nRepOffset) { - exists = 1; - break; - } - } + int nn; - if (!exists) { - int z; + for (nn = n; + nn < nArrivalsPerPosition && pDestSlots[nn].cost == nCodingChoiceCost; + nn++) { + if (pDestSlots[nn].rep_offset == nRepOffset) { + exists = 1; + break; + } + } - for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) { - if (pDestSlots[z].rep_offset == nRepOffset) - break; - } + if (!exists) { + int z; - apultra_arrival* pDestArrival = &pDestSlots[n]; - memmove(&pDestSlots[n + 1], - &pDestSlots[n], - sizeof(apultra_arrival) * (z - n)); - - pDestArrival->cost = nCodingChoiceCost; - pDestArrival->from_pos = i; - pDestArrival->from_slot = j + 1; - pDestArrival->follows_literal = 1; - pDestArrival->rep_offset = nRepOffset; - pDestArrival->short_offset = nShortOffset; - pDestArrival->rep_pos = cur_arrival[j].rep_pos; - pDestArrival->match_len = nShortLen; - pDestArrival->score = nScore; + for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) { + if (pDestSlots[z].rep_offset == nRepOffset) + break; } + + memmove(&pDestSlots[n + 1], + &pDestSlots[n], + sizeof(apultra_arrival) * (z - n)); + + apultra_arrival* pDestArrival = &pDestSlots[n]; + pDestArrival->cost = nCodingChoiceCost; + pDestArrival->from_pos = i; + pDestArrival->from_slot = j + 1; + pDestArrival->follows_literal = 1; + pDestArrival->rep_offset = nRepOffset; + pDestArrival->short_offset = nShortOffset; + pDestArrival->rep_pos = cur_arrival[j].rep_pos; + pDestArrival->match_len = nShortLen; + pDestArrival->score = nScore; } } } @@ -431,47 +429,46 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi const unsigned short *match_depth = pCompressor->match_depth + ((i - nStartOffset) << MATCHES_PER_INDEX_SHIFT); int nNumArrivalsForThisPos = j, nOverallMinRepLen = 0, nOverallMaxRepLen = 0; - int nRepLenForArrival[NARRIVALS_PER_POSITION_MAX]; - memset(nRepLenForArrival, 0, nArrivalsPerPosition * sizeof(int)); - - int nRepMatchArrivalIdx[NARRIVALS_PER_POSITION_MAX + 1]; + int nRepMatchArrivalIdx[(2 * NARRIVALS_PER_POSITION_MAX) + 1]; int nNumRepMatchArrivals = 0; - int nMaxRepLenForPos = nEndOffset - i; - if (nMaxRepLenForPos > LCP_MAX) - nMaxRepLenForPos = LCP_MAX; - const unsigned char* pInWindowStart = pInWindow + i; - const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLenForPos; - const int nLen1 = rle_len[i]; - - for (j = 0; j < nNumArrivalsForThisPos && (i + 2) <= nEndOffset; j++) { - if (cur_arrival[j].follows_literal) { - int nRepOffset = cur_arrival[j].rep_offset; - - if (nRepOffset && i >= nRepOffset) { - if (pInWindowStart[0] == pInWindowStart[-nRepOffset]) { - int nLen0 = rle_len[i - nRepOffset]; - int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; - - if (nMinLen > nMaxRepLenForPos) - nMinLen = nMaxRepLenForPos; - - const unsigned char* pInWindowAtRepOffset = pInWindowStart + nMinLen; - while ((pInWindowAtRepOffset + 8) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nRepOffset, 8)) - pInWindowAtRepOffset += 8; - while ((pInWindowAtRepOffset + 4) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nRepOffset, 4)) - pInWindowAtRepOffset += 4; - while (pInWindowAtRepOffset < pInWindowMax && pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nRepOffset]) - pInWindowAtRepOffset++; - - int nCurMaxLen = (int)(pInWindowAtRepOffset - pInWindowStart); - - if (nCurMaxLen >= 2) { - nRepLenForArrival[j] = nCurMaxLen; - nRepMatchArrivalIdx[nNumRepMatchArrivals++] = j; - - if (nOverallMaxRepLen < nCurMaxLen) - nOverallMaxRepLen = nCurMaxLen; + if ((i + 2) <= nEndOffset) { + int nMaxRepLenForPos = nEndOffset - i; + if (nMaxRepLenForPos > LCP_MAX) + nMaxRepLenForPos = LCP_MAX; + const unsigned char* pInWindowStart = pInWindow + i; + const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLenForPos; + const int nLen1 = rle_len[i]; + + for (j = 0; j < nNumArrivalsForThisPos; j++) { + if (cur_arrival[j].follows_literal) { + int nRepOffset = cur_arrival[j].rep_offset; + + if (nRepOffset && i >= nRepOffset) { + if (pInWindowStart[0] == pInWindowStart[-nRepOffset]) { + int nLen0 = rle_len[i - nRepOffset]; + int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; + + if (nMinLen > nMaxRepLenForPos) + nMinLen = nMaxRepLenForPos; + + const unsigned char* pInWindowAtRepOffset = pInWindowStart + nMinLen; + while ((pInWindowAtRepOffset + 8) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nRepOffset, 8)) + pInWindowAtRepOffset += 8; + while ((pInWindowAtRepOffset + 4) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nRepOffset, 4)) + pInWindowAtRepOffset += 4; + while (pInWindowAtRepOffset < pInWindowMax && pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nRepOffset]) + pInWindowAtRepOffset++; + + int nCurMaxLen = (int)(pInWindowAtRepOffset - pInWindowStart); + + if (nCurMaxLen >= 2) { + nRepMatchArrivalIdx[nNumRepMatchArrivals++] = j; + nRepMatchArrivalIdx[nNumRepMatchArrivals++] = nCurMaxLen; + + if (nOverallMaxRepLen < nCurMaxLen) + nOverallMaxRepLen = nCurMaxLen; + } } } } @@ -553,9 +550,10 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi } for (j = 0; j < nNumArrivalsForThisPos; j++) { - if (nMatchOffset != cur_arrival[j].rep_offset || cur_arrival[j].follows_literal == 0) { + const int nFollowsLiteral = cur_arrival[j].follows_literal; + if (nMatchOffset != cur_arrival[j].rep_offset || nFollowsLiteral == 0) { int nPrevCost = cur_arrival[j].cost & 0x3fffffff; - int nMatchCmdCost = nNoRepMatchMatchLenCost + nNoRepMatchOffsetCostForLit[cur_arrival[j].follows_literal]; + int nMatchCmdCost = nNoRepMatchMatchLenCost + nNoRepMatchOffsetCostForLit[nFollowsLiteral]; int nCodingChoiceCost = nPrevCost + nMatchCmdCost; if (nCodingChoiceCost <= (pDestSlots[nArrivalsPerPosition - 1].cost + 1)) { @@ -566,7 +564,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi int exists = 0; for (n = 0; - n < nArrivalsPerPosition && pDestSlots[n].cost < nCodingChoiceCost; + pDestSlots[n].cost < nCodingChoiceCost; n++) { if (pDestSlots[n].rep_offset == nMatchOffset) { exists = 1; @@ -607,11 +605,11 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi break; } - apultra_arrival* pDestArrival = &pDestSlots[n]; memmove(&pDestSlots[n + 1], &pDestSlots[n], sizeof(apultra_arrival) * (z - n)); + apultra_arrival* pDestArrival = &pDestSlots[n]; pDestArrival->cost = nRevisedCodingChoiceCost; pDestArrival->from_pos = i; pDestArrival->from_slot = j + 1; @@ -651,8 +649,8 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi else if (nOverallMaxRepLen == k) nOverallMaxRepLen--; - for (nCurRepMatchArrival = 0; (j = nRepMatchArrivalIdx[nCurRepMatchArrival]) >= 0; nCurRepMatchArrival++) { - if (nRepLenForArrival[j] >= k) { + for (nCurRepMatchArrival = 0; (j = nRepMatchArrivalIdx[nCurRepMatchArrival]) >= 0; nCurRepMatchArrival += 2) { + if (nRepMatchArrivalIdx[nCurRepMatchArrival + 1] >= k) { int nPrevCost = cur_arrival[j].cost & 0x3fffffff; int nRepCodingChoiceCost = nPrevCost + nRepMatchCmdCost; int nScore = cur_arrival[j].score + 2; @@ -663,7 +661,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi int exists = 0; for (n = 0; - n < nArrivalsPerPosition && pDestSlots[n].cost < nRepCodingChoiceCost; + pDestSlots[n].cost < nRepCodingChoiceCost; n++) { if (pDestSlots[n].rep_offset == nRepOffset) { exists = 1; @@ -673,7 +671,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi if (!exists) { for (; - n < nArrivalsPerPosition && pDestSlots[n].cost == nRepCodingChoiceCost && nScore >= pDestSlots[n].score; + pDestSlots[n].cost == nRepCodingChoiceCost && nScore >= pDestSlots[n].score; n++) { if (pDestSlots[n].rep_offset == nRepOffset) { exists = 1; @@ -682,41 +680,39 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi } if (!exists) { - if (n < nArrivalsPerPosition) { - int nn; - - for (nn = n; - nn < nArrivalsPerPosition && pDestSlots[nn].cost == nRepCodingChoiceCost; - nn++) { - if (pDestSlots[nn].rep_offset == nRepOffset) { - exists = 1; - break; - } - } + int nn; - if (!exists) { - int z; + for (nn = n; + nn < nArrivalsPerPosition && pDestSlots[nn].cost == nRepCodingChoiceCost; + nn++) { + if (pDestSlots[nn].rep_offset == nRepOffset) { + exists = 1; + break; + } + } - for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) { - if (pDestSlots[z].rep_offset == nRepOffset) - break; - } + if (!exists) { + int z; - apultra_arrival* pDestArrival = &pDestSlots[n]; - memmove(&pDestSlots[n + 1], - &pDestSlots[n], - sizeof(apultra_arrival) * (z - n)); - - pDestArrival->cost = nRepCodingChoiceCost; - pDestArrival->from_pos = i; - pDestArrival->from_slot = j + 1; - pDestArrival->follows_literal = 0; - pDestArrival->rep_offset = nRepOffset; - pDestArrival->short_offset = 0; - pDestArrival->rep_pos = i; - pDestArrival->match_len = k; - pDestArrival->score = nScore; + for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) { + if (pDestSlots[z].rep_offset == nRepOffset) + break; } + + memmove(&pDestSlots[n + 1], + &pDestSlots[n], + sizeof(apultra_arrival) * (z - n)); + + apultra_arrival* pDestArrival = &pDestSlots[n]; + pDestArrival->cost = nRepCodingChoiceCost; + pDestArrival->from_pos = i; + pDestArrival->from_slot = j + 1; + pDestArrival->follows_literal = 0; + pDestArrival->rep_offset = nRepOffset; + pDestArrival->short_offset = 0; + pDestArrival->rep_pos = i; + pDestArrival->match_len = k; + pDestArrival->score = nScore; } } } @@ -1325,15 +1321,19 @@ static int apultra_optimize_and_write_block(apultra_compressor *pCompressor, con unsigned short* match_depth = pCompressor->match_depth + ((nPosition - nPreviousBlockSize) << MATCHES_PER_INDEX_SHIFT); int m = 0, nInserted = 0; int nMatchPos; + int nMaxForwardPos = nPosition + 2 + 1 + 5; - while (m < 42 && match[m].length) { + if (nMaxForwardPos > (nEndOffset - 2)) + nMaxForwardPos = nEndOffset - 2; + + while (m < 46 && match[m].length) { offset_cache[match[m].offset & 2047] = nPosition; offset_cache[(match[m].offset - (match_depth[m] & 0x3fff)) & 2047] = nPosition; m++; } - for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < 42 && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) { - int nMatchOffset = nPosition - nMatchPos; + for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < 46 && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) { + const int nMatchOffset = nPosition - nMatchPos; if (nMatchOffset <= pCompressor->max_offset) { int nAlreadyExists = 0; @@ -1361,30 +1361,33 @@ static int apultra_optimize_and_write_block(apultra_compressor *pCompressor, con if (!nAlreadyExists) { int nForwardPos = nPosition + 2 + 1; - int nGotMatch = 0; - while (nForwardPos >= nMatchOffset && (nForwardPos + 2) < nEndOffset && nForwardPos < (nPosition + 2 + 1 + 5)) { - if (!memcmp(pInWindow + nForwardPos, pInWindow + nForwardPos - nMatchOffset, 2)) { - nGotMatch = 1; - break; + if (nForwardPos >= nMatchOffset) { + int nGotMatch = 0; + + while (nForwardPos < nMaxForwardPos) { + if (!memcmp(pInWindow + nForwardPos, pInWindow + nForwardPos - nMatchOffset, 2)) { + nGotMatch = 1; + break; + } + nForwardPos++; } - nForwardPos++; - } - if (nGotMatch) { - int nMatchLen = 2; - while (nMatchLen < 16 && nPosition < (nEndOffset - nMatchLen) && pInWindow[nMatchPos + nMatchLen] == pInWindow[nPosition + nMatchLen]) - nMatchLen++; - match[m].length = nMatchLen; - match[m].offset = nMatchOffset; - match_depth[m] = 0; - m++; + if (nGotMatch) { + int nMatchLen = 2; + while (nMatchLen < 16 && nPosition < (nEndOffset - nMatchLen) && pInWindow[nMatchPos + nMatchLen] == pInWindow[nPosition + nMatchLen]) + nMatchLen++; + match[m].length = nMatchLen; + match[m].offset = nMatchOffset; + match_depth[m] = 0; + m++; - apultra_insert_forward_match(pCompressor, pInWindow, nPosition, nMatchOffset, nPreviousBlockSize, nEndOffset, nArrivalsPerPosition, 8); + apultra_insert_forward_match(pCompressor, pInWindow, nPosition, nMatchOffset, nPreviousBlockSize, nEndOffset, nArrivalsPerPosition, 8); - nInserted++; - if (nInserted >= 6) - break; + nInserted++; + if (nInserted >= 18 || (nInserted >= 15 && m >= 38)) + break; + } } } } @@ -1643,7 +1646,7 @@ size_t apultra_compress(const unsigned char *pInputData, unsigned char *pOutBuff nInDataSize = nBlockSize; if (nInDataSize > 0 && (nDictionarySize + nInDataSize) >= nInputSize) { - if (nInputSize <= 65536) + if (nInputSize <= 262144) nMaxArrivals = NARRIVALS_PER_POSITION_MAX; else nMaxArrivals = NARRIVALS_PER_POSITION_NORMAL; diff --git a/tools/apultra/src/shrink.h b/tools/apultra/src/shrink.h index 0057d68..d02c2dc 100644 --- a/tools/apultra/src/shrink.h +++ b/tools/apultra/src/shrink.h @@ -49,7 +49,7 @@ extern "C" { #define VISITED_FLAG 0x8000000000000000ULL #define EXCL_VISITED_MASK 0x7fffffffffffffffULL -#define NARRIVALS_PER_POSITION_MAX 55 +#define NARRIVALS_PER_POSITION_MAX 62 #define NARRIVALS_PER_POSITION_NORMAL 46 #define NARRIVALS_PER_POSITION_SMALL 9 @@ -86,6 +86,12 @@ typedef struct { int score; } apultra_arrival; +/** Visited match */ +typedef struct { + int outer; + int inner; +} apultra_visited; + /** Compression statistics */ typedef struct _apultra_stats { int num_literals; -- cgit v1.2.3