Updated apultra to 1.4.7

4 files changed, 76 insertions, 83 deletions

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
@@ -53,21 +53,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

  *

  * @param pCompressor compression context

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;