1 /*

     2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.

     3  * All rights reserved.

     4  *

     5  * This source code is licensed under both the BSD-style license (found in the

     6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found

     7  * in the COPYING file in the root directory of this source tree).

     8  * You may select, at your option, one of the above-listed licenses.

     9  */

    10 

    11 #include "zstd_compress_internal.h"

    12 #include "zstd_lazy.h"

    13 

    14 

    15 /*-*************************************

    16 *  Binary Tree search

    17 ***************************************/

    18 

    19 void ZSTD_updateDUBT(

    20                 ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

    21                 const BYTE* ip, const BYTE* iend,

    22                 U32 mls)

    23 {

    24     U32* const hashTable = ms->hashTable;

    25     U32  const hashLog = cParams->hashLog;

    26 

    27     U32* const bt = ms->chainTable;

    28     U32  const btLog  = cParams->chainLog - 1;

    29     U32  const btMask = (1 << btLog) - 1;

    30 

    31     const BYTE* const base = ms->window.base;

    32     U32 const target = (U32)(ip - base);

    33     U32 idx = ms->nextToUpdate;

    34 

    35     if (idx != target)

    36         DEBUGLOG(7, "ZSTD_updateDUBT, from %u to %u (dictLimit:%u)",

    37                     idx, target, ms->window.dictLimit);

    38     assert(ip + 8 <= iend);   /* condition for ZSTD_hashPtr */

    39     (void)iend;

    40 

    41     assert(idx >= ms->window.dictLimit);   /* condition for valid base+idx */

    42     for ( ; idx < target ; idx++) {

    43         size_t const h  = ZSTD_hashPtr(base + idx, hashLog, mls);   /* assumption : ip + 8 <= iend */

    44         U32    const matchIndex = hashTable[h];

    45 

    46         U32*   const nextCandidatePtr = bt + 2*(idx&btMask);

    47         U32*   const sortMarkPtr  = nextCandidatePtr + 1;

    48 

    49         DEBUGLOG(8, "ZSTD_updateDUBT: insert %u", idx);

    50         hashTable[h] = idx;   /* Update Hash Table */

    51         *nextCandidatePtr = matchIndex;   /* update BT like a chain */

    52         *sortMarkPtr = ZSTD_DUBT_UNSORTED_MARK;

    53     }

    54     ms->nextToUpdate = target;

    55 }

    56 

    57 

    58 /** ZSTD_insertDUBT1() :

    59  *  sort one already inserted but unsorted position

    60  *  assumption : current >= btlow == (current - btmask)

    61  *  doesn't fail */

    62 static void ZSTD_insertDUBT1(

    63                  ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

    64                  U32 current, const BYTE* inputEnd,

    65                  U32 nbCompares, U32 btLow, int extDict)

    66 {

    67     U32*   const bt = ms->chainTable;

    68     U32    const btLog  = cParams->chainLog - 1;

    69     U32    const btMask = (1 << btLog) - 1;

    70     size_t commonLengthSmaller=0, commonLengthLarger=0;

    71     const BYTE* const base = ms->window.base;

    72     const BYTE* const dictBase = ms->window.dictBase;

    73     const U32 dictLimit = ms->window.dictLimit;

    74     const BYTE* const ip = (current>=dictLimit) ? base + current : dictBase + current;

    75     const BYTE* const iend = (current>=dictLimit) ? inputEnd : dictBase + dictLimit;

    76     const BYTE* const dictEnd = dictBase + dictLimit;

    77     const BYTE* const prefixStart = base + dictLimit;

    78     const BYTE* match;

    79     U32* smallerPtr = bt + 2*(current&btMask);

    80     U32* largerPtr  = smallerPtr + 1;

    81     U32 matchIndex = *smallerPtr;

    82     U32 dummy32;   /* to be nullified at the end */

    83     U32 const windowLow = ms->window.lowLimit;

    84 

    85     DEBUGLOG(8, "ZSTD_insertDUBT1(%u) (dictLimit=%u, lowLimit=%u)",

    86                 current, dictLimit, windowLow);

    87     assert(current >= btLow);

    88     assert(ip < iend);   /* condition for ZSTD_count */

    89 

    90     while (nbCompares-- && (matchIndex > windowLow)) {

    91         U32* const nextPtr = bt + 2*(matchIndex & btMask);

    92         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */

    93         assert(matchIndex < current);

    94 

    95         if ( (!extDict)

    96           || (matchIndex+matchLength >= dictLimit)  /* both in current segment*/

    97           || (current < dictLimit) /* both in extDict */) {

    98             const BYTE* const mBase = !extDict || ((matchIndex+matchLength) >= dictLimit) ? base : dictBase;

    99             assert( (matchIndex+matchLength >= dictLimit)   /* might be wrong if extDict is incorrectly set to 0 */

   100                  || (current < dictLimit) );

   101             match = mBase + matchIndex;

   102             matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);

   103         } else {

   104             match = dictBase + matchIndex;

   105             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);

   106             if (matchIndex+matchLength >= dictLimit)

   107                 match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */

   108         }

   109 

   110         DEBUGLOG(8, "ZSTD_insertDUBT1: comparing %u with %u : found %u common bytes ",

   111                     current, matchIndex, (U32)matchLength);

   112 

   113         if (ip+matchLength == iend) {   /* equal : no way to know if inf or sup */

   114             break;   /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */

   115         }

   116 

   117         if (match[matchLength] < ip[matchLength]) {  /* necessarily within buffer */

   118             /* match is smaller than current */

   119             *smallerPtr = matchIndex;             /* update smaller idx */

   120             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */

   121             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop searching */

   122             DEBUGLOG(8, "ZSTD_insertDUBT1: %u (>btLow=%u) is smaller : next => %u",

   123                         matchIndex, btLow, nextPtr[1]);

   124             smallerPtr = nextPtr+1;               /* new "candidate" => larger than match, which was smaller than target */

   125             matchIndex = nextPtr[1];              /* new matchIndex, larger than previous and closer to current */

   126         } else {

   127             /* match is larger than current */

   128             *largerPtr = matchIndex;

   129             commonLengthLarger = matchLength;

   130             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop searching */

   131             DEBUGLOG(8, "ZSTD_insertDUBT1: %u (>btLow=%u) is larger => %u",

   132                         matchIndex, btLow, nextPtr[0]);

   133             largerPtr = nextPtr;

   134             matchIndex = nextPtr[0];

   135     }   }

   136 

   137     *smallerPtr = *largerPtr = 0;

   138 }

   139 

   140 

   141 static size_t ZSTD_DUBT_findBestMatch (

   142                             ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   143                             const BYTE* const ip, const BYTE* const iend,

   144                             size_t* offsetPtr,

   145                             U32 const mls,

   146                             U32 const extDict)

   147 {

   148     U32*   const hashTable = ms->hashTable;

   149     U32    const hashLog = cParams->hashLog;

   150     size_t const h  = ZSTD_hashPtr(ip, hashLog, mls);

   151     U32          matchIndex  = hashTable[h];

   152 

   153     const BYTE* const base = ms->window.base;

   154     U32    const current = (U32)(ip-base);

   155     U32    const windowLow = ms->window.lowLimit;

   156 

   157     U32*   const bt = ms->chainTable;

   158     U32    const btLog  = cParams->chainLog - 1;

   159     U32    const btMask = (1 << btLog) - 1;

   160     U32    const btLow = (btMask >= current) ? 0 : current - btMask;

   161     U32    const unsortLimit = MAX(btLow, windowLow);

   162 

   163     U32*         nextCandidate = bt + 2*(matchIndex&btMask);

   164     U32*         unsortedMark = bt + 2*(matchIndex&btMask) + 1;

   165     U32          nbCompares = 1U << cParams->searchLog;

   166     U32          nbCandidates = nbCompares;

   167     U32          previousCandidate = 0;

   168 

   169     DEBUGLOG(7, "ZSTD_DUBT_findBestMatch (%u) ", current);

   170     assert(ip <= iend-8);   /* required for h calculation */

   171 

   172     /* reach end of unsorted candidates list */

   173     while ( (matchIndex > unsortLimit)

   174          && (*unsortedMark == ZSTD_DUBT_UNSORTED_MARK)

   175          && (nbCandidates > 1) ) {

   176         DEBUGLOG(8, "ZSTD_DUBT_findBestMatch: candidate %u is unsorted",

   177                     matchIndex);

   178         *unsortedMark = previousCandidate;

   179         previousCandidate = matchIndex;

   180         matchIndex = *nextCandidate;

   181         nextCandidate = bt + 2*(matchIndex&btMask);

   182         unsortedMark = bt + 2*(matchIndex&btMask) + 1;

   183         nbCandidates --;

   184     }

   185 

   186     if ( (matchIndex > unsortLimit)

   187       && (*unsortedMark==ZSTD_DUBT_UNSORTED_MARK) ) {

   188         DEBUGLOG(7, "ZSTD_DUBT_findBestMatch: nullify last unsorted candidate %u",

   189                     matchIndex);

   190         *nextCandidate = *unsortedMark = 0;   /* nullify next candidate if it's still unsorted (note : simplification, detrimental to compression ratio, beneficial for speed) */

   191     }

   192 

   193     /* batch sort stacked candidates */

   194     matchIndex = previousCandidate;

   195     while (matchIndex) {  /* will end on matchIndex == 0 */

   196         U32* const nextCandidateIdxPtr = bt + 2*(matchIndex&btMask) + 1;

   197         U32 const nextCandidateIdx = *nextCandidateIdxPtr;

   198         ZSTD_insertDUBT1(ms, cParams, matchIndex, iend,

   199                          nbCandidates, unsortLimit, extDict);

   200         matchIndex = nextCandidateIdx;

   201         nbCandidates++;

   202     }

   203 

   204     /* find longest match */

   205     {   size_t commonLengthSmaller=0, commonLengthLarger=0;

   206         const BYTE* const dictBase = ms->window.dictBase;

   207         const U32 dictLimit = ms->window.dictLimit;

   208         const BYTE* const dictEnd = dictBase + dictLimit;

   209         const BYTE* const prefixStart = base + dictLimit;

   210         U32* smallerPtr = bt + 2*(current&btMask);

   211         U32* largerPtr  = bt + 2*(current&btMask) + 1;

   212         U32 matchEndIdx = current+8+1;

   213         U32 dummy32;   /* to be nullified at the end */

   214         size_t bestLength = 0;

   215 

   216         matchIndex  = hashTable[h];

   217         hashTable[h] = current;   /* Update Hash Table */

   218 

   219         while (nbCompares-- && (matchIndex > windowLow)) {

   220             U32* const nextPtr = bt + 2*(matchIndex & btMask);

   221             size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */

   222             const BYTE* match;

   223 

   224             if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {

   225                 match = base + matchIndex;

   226                 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);

   227             } else {

   228                 match = dictBase + matchIndex;

   229                 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);

   230                 if (matchIndex+matchLength >= dictLimit)

   231                     match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */

   232             }

   233 

   234             if (matchLength > bestLength) {

   235                 if (matchLength > matchEndIdx - matchIndex)

   236                     matchEndIdx = matchIndex + (U32)matchLength;

   237                 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) )

   238                     bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;

   239                 if (ip+matchLength == iend) {   /* equal : no way to know if inf or sup */

   240                     break;   /* drop, to guarantee consistency (miss a little bit of compression) */

   241                 }

   242             }

   243 

   244             if (match[matchLength] < ip[matchLength]) {

   245                 /* match is smaller than current */

   246                 *smallerPtr = matchIndex;             /* update smaller idx */

   247                 commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */

   248                 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */

   249                 smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */

   250                 matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */

   251             } else {

   252                 /* match is larger than current */

   253                 *largerPtr = matchIndex;

   254                 commonLengthLarger = matchLength;

   255                 if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */

   256                 largerPtr = nextPtr;

   257                 matchIndex = nextPtr[0];

   258         }   }

   259 

   260         *smallerPtr = *largerPtr = 0;

   261 

   262         assert(matchEndIdx > current+8); /* ensure nextToUpdate is increased */

   263         ms->nextToUpdate = matchEndIdx - 8;   /* skip repetitive patterns */

   264         if (bestLength >= MINMATCH) {

   265             U32 const mIndex = current - ((U32)*offsetPtr - ZSTD_REP_MOVE); (void)mIndex;

   266             DEBUGLOG(8, "ZSTD_DUBT_findBestMatch(%u) : found match of length %u and offsetCode %u (pos %u)",

   267                         current, (U32)bestLength, (U32)*offsetPtr, mIndex);

   268         }

   269         return bestLength;

   270     }

   271 }

   272 

   273 

   274 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */

   275 static size_t ZSTD_BtFindBestMatch (

   276                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   277                         const BYTE* const ip, const BYTE* const iLimit,

   278                         size_t* offsetPtr,

   279                         const U32 mls /* template */)

   280 {

   281     DEBUGLOG(7, "ZSTD_BtFindBestMatch");

   282     if (ip < ms->window.base + ms->nextToUpdate) return 0;   /* skipped area */

   283     ZSTD_updateDUBT(ms, cParams, ip, iLimit, mls);

   284     return ZSTD_DUBT_findBestMatch(ms, cParams, ip, iLimit, offsetPtr, mls, 0);

   285 }

   286 

   287 

   288 static size_t ZSTD_BtFindBestMatch_selectMLS (

   289                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   290                         const BYTE* ip, const BYTE* const iLimit,

   291                         size_t* offsetPtr)

   292 {

   293     switch(cParams->searchLength)

   294     {

   295     default : /* includes case 3 */

   296     case 4 : return ZSTD_BtFindBestMatch(ms, cParams, ip, iLimit, offsetPtr, 4);

   297     case 5 : return ZSTD_BtFindBestMatch(ms, cParams, ip, iLimit, offsetPtr, 5);

   298     case 7 :

   299     case 6 : return ZSTD_BtFindBestMatch(ms, cParams, ip, iLimit, offsetPtr, 6);

   300     }

   301 }

   302 

   303 

   304 /** Tree updater, providing best match */

   305 static size_t ZSTD_BtFindBestMatch_extDict (

   306                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   307                         const BYTE* const ip, const BYTE* const iLimit,

   308                         size_t* offsetPtr,

   309                         const U32 mls)

   310 {

   311     DEBUGLOG(7, "ZSTD_BtFindBestMatch_extDict");

   312     if (ip < ms->window.base + ms->nextToUpdate) return 0;   /* skipped area */

   313     ZSTD_updateDUBT(ms, cParams, ip, iLimit, mls);

   314     return ZSTD_DUBT_findBestMatch(ms, cParams, ip, iLimit, offsetPtr, mls, 1);

   315 }

   316 

   317 

   318 static size_t ZSTD_BtFindBestMatch_selectMLS_extDict (

   319                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   320                         const BYTE* ip, const BYTE* const iLimit,

   321                         size_t* offsetPtr)

   322 {

   323     switch(cParams->searchLength)

   324     {

   325     default : /* includes case 3 */

   326     case 4 : return ZSTD_BtFindBestMatch_extDict(ms, cParams, ip, iLimit, offsetPtr, 4);

   327     case 5 : return ZSTD_BtFindBestMatch_extDict(ms, cParams, ip, iLimit, offsetPtr, 5);

   328     case 7 :

   329     case 6 : return ZSTD_BtFindBestMatch_extDict(ms, cParams, ip, iLimit, offsetPtr, 6);

   330     }

   331 }

   332 

   333 

   334 

   335 /* *********************************

   336 *  Hash Chain

   337 ***********************************/

   338 #define NEXT_IN_CHAIN(d, mask)   chainTable[(d) & mask]

   339 

   340 /* Update chains up to ip (excluded)

   341    Assumption : always within prefix (i.e. not within extDict) */

   342 static U32 ZSTD_insertAndFindFirstIndex_internal(

   343                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   344                         const BYTE* ip, U32 const mls)

   345 {

   346     U32* const hashTable  = ms->hashTable;

   347     const U32 hashLog = cParams->hashLog;

   348     U32* const chainTable = ms->chainTable;

   349     const U32 chainMask = (1 << cParams->chainLog) - 1;

   350     const BYTE* const base = ms->window.base;

   351     const U32 target = (U32)(ip - base);

   352     U32 idx = ms->nextToUpdate;

   353 

   354     while(idx < target) { /* catch up */

   355         size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls);

   356         NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];

   357         hashTable[h] = idx;

   358         idx++;

   359     }

   360 

   361     ms->nextToUpdate = target;

   362     return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];

   363 }

   364 

   365 U32 ZSTD_insertAndFindFirstIndex(

   366                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   367                         const BYTE* ip)

   368 {

   369     return ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, cParams->searchLength);

   370 }

   371 

   372 

   373 /* inlining is important to hardwire a hot branch (template emulation) */

   374 FORCE_INLINE_TEMPLATE

   375 size_t ZSTD_HcFindBestMatch_generic (

   376                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   377                         const BYTE* const ip, const BYTE* const iLimit,

   378                         size_t* offsetPtr,

   379                         const U32 mls, const U32 extDict)

   380 {

   381     U32* const chainTable = ms->chainTable;

   382     const U32 chainSize = (1 << cParams->chainLog);

   383     const U32 chainMask = chainSize-1;

   384     const BYTE* const base = ms->window.base;

   385     const BYTE* const dictBase = ms->window.dictBase;

   386     const U32 dictLimit = ms->window.dictLimit;

   387     const BYTE* const prefixStart = base + dictLimit;

   388     const BYTE* const dictEnd = dictBase + dictLimit;

   389     const U32 lowLimit = ms->window.lowLimit;

   390     const U32 current = (U32)(ip-base);

   391     const U32 minChain = current > chainSize ? current - chainSize : 0;

   392     U32 nbAttempts = 1U << cParams->searchLog;

   393     size_t ml=4-1;

   394 

   395     /* HC4 match finder */

   396     U32 matchIndex = ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, mls);

   397 

   398     for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {

   399         size_t currentMl=0;

   400         if ((!extDict) || matchIndex >= dictLimit) {

   401             const BYTE* const match = base + matchIndex;

   402             if (match[ml] == ip[ml])   /* potentially better */

   403                 currentMl = ZSTD_count(ip, match, iLimit);

   404         } else {

   405             const BYTE* const match = dictBase + matchIndex;

   406             assert(match+4 <= dictEnd);

   407             if (MEM_read32(match) == MEM_read32(ip))   /* assumption : matchIndex <= dictLimit-4 (by table construction) */

   408                 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dictEnd, prefixStart) + 4;

   409         }

   410 

   411         /* save best solution */

   412         if (currentMl > ml) {

   413             ml = currentMl;

   414             *offsetPtr = current - matchIndex + ZSTD_REP_MOVE;

   415             if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */

   416         }

   417 

   418         if (matchIndex <= minChain) break;

   419         matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);

   420     }

   421 

   422     return ml;

   423 }

   424 

   425 

   426 FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch_selectMLS (

   427                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   428                         const BYTE* ip, const BYTE* const iLimit,

   429                         size_t* offsetPtr)

   430 {

   431     switch(cParams->searchLength)

   432     {

   433     default : /* includes case 3 */

   434     case 4 : return ZSTD_HcFindBestMatch_generic(ms, cParams, ip, iLimit, offsetPtr, 4, 0);

   435     case 5 : return ZSTD_HcFindBestMatch_generic(ms, cParams, ip, iLimit, offsetPtr, 5, 0);

   436     case 7 :

   437     case 6 : return ZSTD_HcFindBestMatch_generic(ms, cParams, ip, iLimit, offsetPtr, 6, 0);

   438     }

   439 }

   440 

   441 

   442 FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch_extDict_selectMLS (

   443                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   444                         const BYTE* ip, const BYTE* const iLimit,

   445                         size_t* const offsetPtr)

   446 {

   447     switch(cParams->searchLength)

   448     {

   449     default : /* includes case 3 */

   450     case 4 : return ZSTD_HcFindBestMatch_generic(ms, cParams, ip, iLimit, offsetPtr, 4, 1);

   451     case 5 : return ZSTD_HcFindBestMatch_generic(ms, cParams, ip, iLimit, offsetPtr, 5, 1);

   452     case 7 :

   453     case 6 : return ZSTD_HcFindBestMatch_generic(ms, cParams, ip, iLimit, offsetPtr, 6, 1);

   454     }

   455 }

   456 

   457 

   458 /* *******************************

   459 *  Common parser - lazy strategy

   460 *********************************/

   461 FORCE_INLINE_TEMPLATE

   462 size_t ZSTD_compressBlock_lazy_generic(

   463                         ZSTD_matchState_t* ms, seqStore_t* seqStore,

   464                         U32 rep[ZSTD_REP_NUM],

   465                         ZSTD_compressionParameters const* cParams,

   466                         const void* src, size_t srcSize,

   467                         const U32 searchMethod, const U32 depth)

   468 {

   469     const BYTE* const istart = (const BYTE*)src;

   470     const BYTE* ip = istart;

   471     const BYTE* anchor = istart;

   472     const BYTE* const iend = istart + srcSize;

   473     const BYTE* const ilimit = iend - 8;

   474     const BYTE* const base = ms->window.base + ms->window.dictLimit;

   475 

   476     typedef size_t (*searchMax_f)(

   477                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   478                         const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr);

   479     searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS;

   480     U32 offset_1 = rep[0], offset_2 = rep[1], savedOffset=0;

   481 

   482     /* init */

   483     ip += (ip==base);

   484     ms->nextToUpdate3 = ms->nextToUpdate;

   485     {   U32 const maxRep = (U32)(ip-base);

   486         if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0;

   487         if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0;

   488     }

   489 

   490     /* Match Loop */

   491     while (ip < ilimit) {

   492         size_t matchLength=0;

   493         size_t offset=0;

   494         const BYTE* start=ip+1;

   495 

   496         /* check repCode */

   497         if ((offset_1>0) & (MEM_read32(ip+1) == MEM_read32(ip+1 - offset_1))) {

   498             /* repcode : we take it */

   499             matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;

   500             if (depth==0) goto _storeSequence;

   501         }

   502 

   503         /* first search (depth 0) */

   504         {   size_t offsetFound = 99999999;

   505             size_t const ml2 = searchMax(ms, cParams, ip, iend, &offsetFound);

   506             if (ml2 > matchLength)

   507                 matchLength = ml2, start = ip, offset=offsetFound;

   508         }

   509 

   510         if (matchLength < 4) {

   511             ip += ((ip-anchor) >> kSearchStrength) + 1;   /* jump faster over incompressible sections */

   512             continue;

   513         }

   514 

   515         /* let's try to find a better solution */

   516         if (depth>=1)

   517         while (ip<ilimit) {

   518             ip ++;

   519             if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {

   520                 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;

   521                 int const gain2 = (int)(mlRep * 3);

   522                 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);

   523                 if ((mlRep >= 4) && (gain2 > gain1))

   524                     matchLength = mlRep, offset = 0, start = ip;

   525             }

   526             {   size_t offset2=99999999;

   527                 size_t const ml2 = searchMax(ms, cParams, ip, iend, &offset2);

   528                 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */

   529                 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);

   530                 if ((ml2 >= 4) && (gain2 > gain1)) {

   531                     matchLength = ml2, offset = offset2, start = ip;

   532                     continue;   /* search a better one */

   533             }   }

   534 

   535             /* let's find an even better one */

   536             if ((depth==2) && (ip<ilimit)) {

   537                 ip ++;

   538                 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {

   539                     size_t const ml2 = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;

   540                     int const gain2 = (int)(ml2 * 4);

   541                     int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);

   542                     if ((ml2 >= 4) && (gain2 > gain1))

   543                         matchLength = ml2, offset = 0, start = ip;

   544                 }

   545                 {   size_t offset2=99999999;

   546                     size_t const ml2 = searchMax(ms, cParams, ip, iend, &offset2);

   547                     int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */

   548                     int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);

   549                     if ((ml2 >= 4) && (gain2 > gain1)) {

   550                         matchLength = ml2, offset = offset2, start = ip;

   551                         continue;

   552             }   }   }

   553             break;  /* nothing found : store previous solution */

   554         }

   555 

   556         /* NOTE:

   557          * start[-offset+ZSTD_REP_MOVE-1] is undefined behavior.

   558          * (-offset+ZSTD_REP_MOVE-1) is unsigned, and is added to start, which

   559          * overflows the pointer, which is undefined behavior.

   560          */

   561         /* catch up */

   562         if (offset) {

   563             while ( ((start > anchor) & (start - (offset-ZSTD_REP_MOVE) > base))

   564                  && (start[-1] == (start-(offset-ZSTD_REP_MOVE))[-1]) )  /* only search for offset within prefix */

   565                 { start--; matchLength++; }

   566             offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);

   567         }

   568         /* store sequence */

   569 _storeSequence:

   570         {   size_t const litLength = start - anchor;

   571             ZSTD_storeSeq(seqStore, litLength, anchor, (U32)offset, matchLength-MINMATCH);

   572             anchor = ip = start + matchLength;

   573         }

   574 

   575         /* check immediate repcode */

   576         while ( ((ip <= ilimit) & (offset_2>0))

   577              && (MEM_read32(ip) == MEM_read32(ip - offset_2)) ) {

   578             /* store sequence */

   579             matchLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;

   580             offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */

   581             ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH);

   582             ip += matchLength;

   583             anchor = ip;

   584             continue;   /* faster when present ... (?) */

   585     }   }

   586 

   587     /* Save reps for next block */

   588     rep[0] = offset_1 ? offset_1 : savedOffset;

   589     rep[1] = offset_2 ? offset_2 : savedOffset;

   590 

   591     /* Return the last literals size */

   592     return iend - anchor;

   593 }

   594 

   595 

   596 size_t ZSTD_compressBlock_btlazy2(

   597         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   598         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   599 {

   600     return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, cParams, src, srcSize, 1, 2);

   601 }

   602 

   603 size_t ZSTD_compressBlock_lazy2(

   604         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   605         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   606 {

   607     return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, cParams, src, srcSize, 0, 2);

   608 }

   609 

   610 size_t ZSTD_compressBlock_lazy(

   611         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   612         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   613 {

   614     return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, cParams, src, srcSize, 0, 1);

   615 }

   616 

   617 size_t ZSTD_compressBlock_greedy(

   618         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   619         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   620 {

   621     return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, cParams, src, srcSize, 0, 0);

   622 }

   623 

   624 

   625 FORCE_INLINE_TEMPLATE

   626 size_t ZSTD_compressBlock_lazy_extDict_generic(

   627                         ZSTD_matchState_t* ms, seqStore_t* seqStore,

   628                         U32 rep[ZSTD_REP_NUM],

   629                         ZSTD_compressionParameters const* cParams,

   630                         const void* src, size_t srcSize,

   631                         const U32 searchMethod, const U32 depth)

   632 {

   633     const BYTE* const istart = (const BYTE*)src;

   634     const BYTE* ip = istart;

   635     const BYTE* anchor = istart;

   636     const BYTE* const iend = istart + srcSize;

   637     const BYTE* const ilimit = iend - 8;

   638     const BYTE* const base = ms->window.base;

   639     const U32 dictLimit = ms->window.dictLimit;

   640     const U32 lowestIndex = ms->window.lowLimit;

   641     const BYTE* const prefixStart = base + dictLimit;

   642     const BYTE* const dictBase = ms->window.dictBase;

   643     const BYTE* const dictEnd  = dictBase + dictLimit;

   644     const BYTE* const dictStart  = dictBase + lowestIndex;

   645 

   646     typedef size_t (*searchMax_f)(

   647                         ZSTD_matchState_t* ms, ZSTD_compressionParameters const* cParams,

   648                         const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr);

   649     searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS;

   650 

   651     U32 offset_1 = rep[0], offset_2 = rep[1];

   652 

   653     /* init */

   654     ms->nextToUpdate3 = ms->nextToUpdate;

   655     ip += (ip == prefixStart);

   656 

   657     /* Match Loop */

   658     while (ip < ilimit) {

   659         size_t matchLength=0;

   660         size_t offset=0;

   661         const BYTE* start=ip+1;

   662         U32 current = (U32)(ip-base);

   663 

   664         /* check repCode */

   665         {   const U32 repIndex = (U32)(current+1 - offset_1);

   666             const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;

   667             const BYTE* const repMatch = repBase + repIndex;

   668             if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))   /* intentional overflow */

   669             if (MEM_read32(ip+1) == MEM_read32(repMatch)) {

   670                 /* repcode detected we should take it */

   671                 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;

   672                 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4;

   673                 if (depth==0) goto _storeSequence;

   674         }   }

   675 

   676         /* first search (depth 0) */

   677         {   size_t offsetFound = 99999999;

   678             size_t const ml2 = searchMax(ms, cParams, ip, iend, &offsetFound);

   679             if (ml2 > matchLength)

   680                 matchLength = ml2, start = ip, offset=offsetFound;

   681         }

   682 

   683          if (matchLength < 4) {

   684             ip += ((ip-anchor) >> kSearchStrength) + 1;   /* jump faster over incompressible sections */

   685             continue;

   686         }

   687 

   688         /* let's try to find a better solution */

   689         if (depth>=1)

   690         while (ip<ilimit) {

   691             ip ++;

   692             current++;

   693             /* check repCode */

   694             if (offset) {

   695                 const U32 repIndex = (U32)(current - offset_1);

   696                 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;

   697                 const BYTE* const repMatch = repBase + repIndex;

   698                 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))  /* intentional overflow */

   699                 if (MEM_read32(ip) == MEM_read32(repMatch)) {

   700                     /* repcode detected */

   701                     const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;

   702                     size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;

   703                     int const gain2 = (int)(repLength * 3);

   704                     int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);

   705                     if ((repLength >= 4) && (gain2 > gain1))

   706                         matchLength = repLength, offset = 0, start = ip;

   707             }   }

   708 

   709             /* search match, depth 1 */

   710             {   size_t offset2=99999999;

   711                 size_t const ml2 = searchMax(ms, cParams, ip, iend, &offset2);

   712                 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */

   713                 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);

   714                 if ((ml2 >= 4) && (gain2 > gain1)) {

   715                     matchLength = ml2, offset = offset2, start = ip;

   716                     continue;   /* search a better one */

   717             }   }

   718 

   719             /* let's find an even better one */

   720             if ((depth==2) && (ip<ilimit)) {

   721                 ip ++;

   722                 current++;

   723                 /* check repCode */

   724                 if (offset) {

   725                     const U32 repIndex = (U32)(current - offset_1);

   726                     const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;

   727                     const BYTE* const repMatch = repBase + repIndex;

   728                     if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))  /* intentional overflow */

   729                     if (MEM_read32(ip) == MEM_read32(repMatch)) {

   730                         /* repcode detected */

   731                         const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;

   732                         size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;

   733                         int const gain2 = (int)(repLength * 4);

   734                         int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);

   735                         if ((repLength >= 4) && (gain2 > gain1))

   736                             matchLength = repLength, offset = 0, start = ip;

   737                 }   }

   738 

   739                 /* search match, depth 2 */

   740                 {   size_t offset2=99999999;

   741                     size_t const ml2 = searchMax(ms, cParams, ip, iend, &offset2);

   742                     int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */

   743                     int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);

   744                     if ((ml2 >= 4) && (gain2 > gain1)) {

   745                         matchLength = ml2, offset = offset2, start = ip;

   746                         continue;

   747             }   }   }

   748             break;  /* nothing found : store previous solution */

   749         }

   750 

   751         /* catch up */

   752         if (offset) {

   753             U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));

   754             const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;

   755             const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;

   756             while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; }  /* catch up */

   757             offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);

   758         }

   759 

   760         /* store sequence */

   761 _storeSequence:

   762         {   size_t const litLength = start - anchor;

   763             ZSTD_storeSeq(seqStore, litLength, anchor, (U32)offset, matchLength-MINMATCH);

   764             anchor = ip = start + matchLength;

   765         }

   766 

   767         /* check immediate repcode */

   768         while (ip <= ilimit) {

   769             const U32 repIndex = (U32)((ip-base) - offset_2);

   770             const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;

   771             const BYTE* const repMatch = repBase + repIndex;

   772             if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))  /* intentional overflow */

   773             if (MEM_read32(ip) == MEM_read32(repMatch)) {

   774                 /* repcode detected we should take it */

   775                 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;

   776                 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;

   777                 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset;   /* swap offset history */

   778                 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH);

   779                 ip += matchLength;

   780                 anchor = ip;

   781                 continue;   /* faster when present ... (?) */

   782             }

   783             break;

   784     }   }

   785 

   786     /* Save reps for next block */

   787     rep[0] = offset_1;

   788     rep[1] = offset_2;

   789 

   790     /* Return the last literals size */

   791     return iend - anchor;

   792 }

   793 

   794 

   795 size_t ZSTD_compressBlock_greedy_extDict(

   796         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   797         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   798 {

   799     return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 0, 0);

   800 }

   801 

   802 size_t ZSTD_compressBlock_lazy_extDict(

   803         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   804         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   805 

   806 {

   807     return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 0, 1);

   808 }

   809 

   810 size_t ZSTD_compressBlock_lazy2_extDict(

   811         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   812         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   813 

   814 {

   815     return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 0, 2);

   816 }

   817 

   818 size_t ZSTD_compressBlock_btlazy2_extDict(

   819         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],

   820         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize)

   821 

   822 {

   823     return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 1, 2);

   824 }