aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJuan J. Martinez <jjm@usebox.net>2022-01-07 07:20:37 +0000
committerJuan J. Martinez <jjm@usebox.net>2022-01-07 07:20:37 +0000
commit928346dced45ed91b765eb47ed3ed18a7f1ad744 (patch)
tree390d5b17515d355062f815d29c85746729ef8e2d
parent6ddb99828102bd70e7a55261cf04c67be165ee21 (diff)
downloadubox-msx-lib-928346dced45ed91b765eb47ed3ed18a7f1ad744.tar.gz
ubox-msx-lib-928346dced45ed91b765eb47ed3ed18a7f1ad744.zip
Updated apultra to 1.4.5
-rw-r--r--CHANGES.md4
-rw-r--r--tools/apultra/src/apultra.c2
-rw-r--r--tools/apultra/src/shrink.c175
-rw-r--r--tools/apultra/src/shrink.h7
4 files changed, 92 insertions, 96 deletions
diff --git a/CHANGES.md b/CHANGES.md
index 854aa43..abba299 100644
--- a/CHANGES.md
+++ b/CHANGES.md
@@ -1,3 +1,7 @@
+## Release 1.x.x - 2021-??-??
+
+ - Updated apultra to 1.4.5
+
## Release 1.1.9 - 2021-12-29
- Generate a "what's new?" HTML page in the docs
diff --git a/tools/apultra/src/apultra.c b/tools/apultra/src/apultra.c
index e4a867e..4800ff6 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.4"
+#define TOOL_VERSION "1.4.5"
/*---------------------------------------------------------------------------*/
diff --git a/tools/apultra/src/shrink.c b/tools/apultra/src/shrink.c
index 6dfb0cf..fae7692 100644
--- a/tools/apultra/src/shrink.c
+++ b/tools/apultra/src/shrink.c
@@ -123,14 +123,14 @@ static int apultra_get_gamma2_size(int nValue) {
*
* @return updated write index into output buffer, or -1 in case of an error
*/
-static int apultra_write_gamma2_value(unsigned char *pOutData, int nOutOffset, const int nMaxOutDataSize, int nValue, int *nCurBitsOffset, int *nCurBitShift) {
+static int apultra_write_gamma2_value(unsigned char *pOutData, int nOutOffset, const int nMaxOutDataSize, const int nValue, int *nCurBitsOffset, int *nCurBitShift) {
int msb = 30;
while ((nValue >> msb--) == 0);
while (msb > 0) {
- const int bit = (nValue >> msb--) & 1;
+ const int bit = (nValue >> --msb) & 2;
- nOutOffset = apultra_write_bits(pOutData, nOutOffset, nMaxOutDataSize, (bit << 1) | 1, 2, nCurBitsOffset, nCurBitShift);
+ nOutOffset = apultra_write_bits(pOutData, nOutOffset, nMaxOutDataSize, bit | 1, 2, nCurBitsOffset, nCurBitShift);
}
return apultra_write_bits(pOutData, nOutOffset, nMaxOutDataSize, (nValue & 1) << 1, 2, nCurBitsOffset, nCurBitShift);
@@ -204,63 +204,59 @@ static void apultra_insert_forward_match(apultra_compressor *pCompressor, const
if (nRepPos >= nStartOffset &&
(nRepPos + 1) < nEndOffset &&
- visited[nRepPos].outer != nMatchOffset) {
+ visited[nRepPos] != nMatchOffset) {
- visited[nRepPos].outer = nMatchOffset;
+ visited[nRepPos] = nMatchOffset;
- if (visited[nRepPos].inner != nMatchOffset && nRepPos >= nMatchOffset && pCompressor->match[((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT) + NMATCHES_PER_INDEX - 1].length == 0) {
+ if (nRepPos >= nMatchOffset && nRepOffset && pCompressor->match[((nRepPos - nStartOffset) << MATCHES_PER_INDEX_SHIFT) + NMATCHES_PER_INDEX - 1].length == 0) {
const unsigned char* pInWindowAtRepOffset = pInWindow + nRepPos;
if (!memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 2)) {
- visited[nRepPos].inner = nMatchOffset;
-
- if (nRepOffset) {
- const int nLen0 = rle_len[nRepPos - nMatchOffset];
- const int nLen1 = rle_len[nRepPos];
- int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1;
-
- int nMaxRepLen = nEndOffset - nRepPos;
- if (nMaxRepLen > LCP_MAX)
- nMaxRepLen = LCP_MAX;
-
- if (nMinLen > nMaxRepLen)
- nMinLen = nMaxRepLen;
-
- const unsigned char* pInWindowMax = pInWindowAtRepOffset + nMaxRepLen;
- pInWindowAtRepOffset += 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++;
-
- const int nCurRepLen = (int)(pInWindowAtRepOffset - (pInWindow + nRepPos));
-
- 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; 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;
+ const int nLen0 = rle_len[nRepPos - nMatchOffset];
+ const int nLen1 = rle_len[nRepPos];
+ int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1;
+
+ int nMaxRepLen = nEndOffset - nRepPos;
+ if (nMaxRepLen > LCP_MAX)
+ nMaxRepLen = LCP_MAX;
+
+ if (nMinLen > nMaxRepLen)
+ nMinLen = nMaxRepLen;
+
+ const unsigned char* pInWindowMax = pInWindowAtRepOffset + nMaxRepLen;
+ pInWindowAtRepOffset += 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++;
+
+ const int nCurRepLen = (int)(pInWindowAtRepOffset - (pInWindow + nRepPos));
+
+ 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; 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);
}
}
}
@@ -333,10 +329,11 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
const int nPrevCost = cur_arrival[j].cost & 0x3fffffff;
const int nCodingChoiceCost = nPrevCost + nLiteralCost;
const int nScore = cur_arrival[j].score + nLiteralScore;
+ const int nRepOffset = cur_arrival[j].rep_offset;
if (nCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 1].cost ||
- (nCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 1].cost && nScore < pDestSlots[nArrivalsPerPosition - 1].score)) {
- const int nRepOffset = cur_arrival[j].rep_offset;
+ (nCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 1].cost && nScore < pDestSlots[nArrivalsPerPosition - 1].score &&
+ nRepOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset)) {
int exists = 0;
for (n = 0;
@@ -359,21 +356,19 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
}
if (!exists) {
- int nn;
+ int z;
- for (nn = n;
- nn < nArrivalsPerPosition && pDestSlots[nn].cost == nCodingChoiceCost;
- nn++) {
- if (pDestSlots[nn].rep_offset == nRepOffset) {
+ for (z = n;
+ z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nCodingChoiceCost;
+ z++) {
+ if (pDestSlots[z].rep_offset == nRepOffset) {
exists = 1;
break;
}
}
if (!exists) {
- int z;
-
- for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
+ for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
if (pDestSlots[z].rep_offset == nRepOffset)
break;
}
@@ -494,7 +489,7 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
int nStartingMatchLen, nJumpMatchLen, k;
int nNoRepMatchOffsetCostForLit[2], nNoRepMatchOffsetCostDelta;
int nMinMatchLenForOffset;
- int nNoRepCostAdjusment = (nMatchLen >= LCP_MAX) ? 1 : 0;
+ const int nNoRepCostAdjusment = (nMatchLen >= LCP_MAX) ? 1 : 0;
if (nMatchOffset < MINMATCH3_OFFSET)
nMinMatchLenForOffset = 2;
@@ -555,7 +550,8 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
const int nScore = cur_arrival[j].score + nScorePenalty;
if (nCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 2].cost ||
- (nCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 2].cost && nScore < pDestSlots[nArrivalsPerPosition - 2].score)) {
+ (nCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 2].cost && nScore < pDestSlots[nArrivalsPerPosition - 2].score &&
+ (nCodingChoiceCost != pDestSlots[nArrivalsPerPosition - 1].cost || nMatchOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset))) {
int exists = 0;
for (n = 0;
@@ -581,21 +577,19 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
if (!exists) {
if (n < nArrivalsPerPosition - 1) {
- int nn;
+ int z;
- for (nn = n;
- nn < nArrivalsPerPosition && pDestSlots[nn].cost == nCodingChoiceCost;
- nn++) {
- if (pDestSlots[nn].rep_offset == nMatchOffset) {
+ for (z = n;
+ z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nCodingChoiceCost;
+ z++) {
+ if (pDestSlots[z].rep_offset == nMatchOffset) {
exists = 1;
break;
}
}
if (!exists) {
- int z;
-
- for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
+ for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
if (pDestSlots[z].rep_offset == nMatchOffset)
break;
}
@@ -649,10 +643,11 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
const int nPrevCost = cur_arrival[j].cost & 0x3fffffff;
const int nRepCodingChoiceCost = nPrevCost + nRepMatchCmdCost;
const int nScore = cur_arrival[j].score + 2;
+ const int nRepOffset = cur_arrival[j].rep_offset;
if (nRepCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 1].cost ||
- (nRepCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 1].cost && nScore < pDestSlots[nArrivalsPerPosition - 1].score)) {
- const int nRepOffset = cur_arrival[j].rep_offset;
+ (nRepCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 1].cost && nScore < pDestSlots[nArrivalsPerPosition - 1].score &&
+ nRepOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset)) {
int exists = 0;
for (n = 0;
@@ -675,21 +670,19 @@ static void apultra_optimize_forward(apultra_compressor *pCompressor, const unsi
}
if (!exists) {
- int nn;
+ int z;
- for (nn = n;
- nn < nArrivalsPerPosition && pDestSlots[nn].cost == nRepCodingChoiceCost;
- nn++) {
- if (pDestSlots[nn].rep_offset == nRepOffset) {
+ for (z = n;
+ z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nRepCodingChoiceCost;
+ z++) {
+ if (pDestSlots[z].rep_offset == nRepOffset) {
exists = 1;
break;
}
}
if (!exists) {
- int z;
-
- for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
+ for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
if (pDestSlots[z].rep_offset == nRepOffset)
break;
}
@@ -834,6 +827,8 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign
(pBestMatch[nNextIndex].offset < MINMATCH4_OFFSET || pMatch->length >= 4)) {
int nMaxLen = 0;
const unsigned char* pInWindowAtPos = pInWindow + i;
+ while ((nMaxLen + 4) < pMatch->length && !memcmp(pInWindowAtPos + nMaxLen - pBestMatch[nNextIndex].offset, pInWindowAtPos + nMaxLen, 4))
+ nMaxLen += 4;
while (nMaxLen < pMatch->length && pInWindowAtPos[nMaxLen - pBestMatch[nNextIndex].offset] == pInWindowAtPos[nMaxLen])
nMaxLen++;
@@ -875,7 +870,7 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign
/* We gain a repmatch that is shorter than the original match as this is the best we can do, so it is followed by extra literals, but
* we have calculated that this is shorter */
- int nOrigLen = pMatch->length;
+ const int nOrigLen = pMatch->length;
int j;
pMatch->offset = pBestMatch[nNextIndex].offset;
@@ -914,7 +909,7 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign
nNextCommandSize = apultra_get_offset_varlen_size(pBestMatch[nNextIndex].length, pBestMatch[nNextIndex].offset, nNextFollowsLiteral) + apultra_get_match_varlen_size(pBestMatch[nNextIndex].length, pBestMatch[nNextIndex].offset);
}
- int nOriginalCombinedCommandSize = nCurCommandSize + nNextCommandSize;
+ const int nOriginalCombinedCommandSize = nCurCommandSize + nNextCommandSize;
/* Calculate the cost of replacing this match command by literals + the effect on the cost of the next command */
int nReducedCommandSize = 0;
@@ -943,7 +938,7 @@ static int apultra_reduce_commands(apultra_compressor *pCompressor, const unsign
if (!nCannotEncode && nOriginalCombinedCommandSize > nReducedCommandSize) {
/* Reduce */
- int nMatchLen = pMatch->length;
+ const int nMatchLen = pMatch->length;
int j;
for (j = 0; j < nMatchLen; j++) {
@@ -1081,8 +1076,8 @@ static int apultra_write_block(apultra_compressor *pCompressor, apultra_final_ma
const apultra_final_match *pMatch = pBestMatch + i;
if (pMatch->length >= 2) {
- int nMatchOffset = pMatch->offset;
- int nMatchLen = pMatch->length;
+ const int nMatchOffset = pMatch->offset;
+ const int nMatchLen = pMatch->length;
if (nMatchOffset < MIN_OFFSET || nMatchOffset > nMaxOffset)
return -1;
@@ -1178,7 +1173,7 @@ static int apultra_write_block(apultra_compressor *pCompressor, apultra_final_ma
pCompressor->stats.commands_divisor++;
}
else if (pMatch->length == 1) {
- int nMatchOffset = pMatch->offset;
+ const int nMatchOffset = pMatch->offset;
/* 4 bits offset */
@@ -1210,7 +1205,7 @@ static int apultra_write_block(apultra_compressor *pCompressor, apultra_final_ma
*nFollowsLiteral = 1;
}
- int nCurSafeDist = (i - nStartOffset) - nOutOffset;
+ const int nCurSafeDist = (i - nStartOffset) - nOutOffset;
if (nCurSafeDist >= 0 && pCompressor->stats.safe_dist < nCurSafeDist)
pCompressor->stats.safe_dist = nCurSafeDist;
}
@@ -1226,7 +1221,7 @@ static int apultra_write_block(apultra_compressor *pCompressor, apultra_final_ma
pCompressor->stats.num_eod++;
pCompressor->stats.commands_divisor++;
- int nCurSafeDist = (i - nStartOffset) - nOutOffset;
+ const int nCurSafeDist = (i - nStartOffset) - nOutOffset;
if (nCurSafeDist >= 0 && pCompressor->stats.safe_dist < nCurSafeDist)
pCompressor->stats.safe_dist = nCurSafeDist;
}
@@ -1285,7 +1280,7 @@ static int apultra_optimize_and_write_block(apultra_compressor *pCompressor, con
m++;
for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < 15 && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) {
- int nMatchOffset = nPosition - nMatchPos;
+ const int nMatchOffset = nPosition - nMatchPos;
if (nMatchOffset <= pCompressor->max_offset) {
int nExistingMatchIdx;
diff --git a/tools/apultra/src/shrink.h b/tools/apultra/src/shrink.h
index d02c2dc..3be37e9 100644
--- a/tools/apultra/src/shrink.h
+++ b/tools/apultra/src/shrink.h
@@ -71,7 +71,7 @@ typedef struct _apultra_final_match {
} apultra_final_match;
/** Forward arrival slot */
-typedef struct {
+typedef struct _apultra_arrival {
int cost;
unsigned int from_pos:21;
@@ -87,10 +87,7 @@ typedef struct {
} apultra_arrival;
/** Visited match */
-typedef struct {
- int outer;
- int inner;
-} apultra_visited;
+typedef int apultra_visited;
/** Compression statistics */
typedef struct _apultra_stats {