LXR linux/lib/zstd/compress/zstd_double

   1/*
   2 * Copyright (c) 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_double_fast.h"
  13
  14
  15void ZSTD_fillDoubleHashTable(ZSTD_matchState_t* ms,
  16                              void const* end, ZSTD_dictTableLoadMethod_e dtlm)
  17{
  18    const ZSTD_compressionParameters* const cParams = &ms->cParams;
  19    U32* const hashLarge = ms->hashTable;
  20    U32  const hBitsL = cParams->hashLog;
  21    U32  const mls = cParams->minMatch;
  22    U32* const hashSmall = ms->chainTable;
  23    U32  const hBitsS = cParams->chainLog;
  24    const BYTE* const base = ms->window.base;
  25    const BYTE* ip = base + ms->nextToUpdate;
  26    const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
  27    const U32 fastHashFillStep = 3;
  28
  29    /* Always insert every fastHashFillStep position into the hash tables.
  30     * Insert the other positions into the large hash table if their entry
  31     * is empty.
  32     */
  33    for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) {
  34        U32 const curr = (U32)(ip - base);
  35        U32 i;
  36        for (i = 0; i < fastHashFillStep; ++i) {
  37            size_t const smHash = ZSTD_hashPtr(ip + i, hBitsS, mls);
  38            size_t const lgHash = ZSTD_hashPtr(ip + i, hBitsL, 8);
  39            if (i == 0)
  40                hashSmall[smHash] = curr + i;
  41            if (i == 0 || hashLarge[lgHash] == 0)
  42                hashLarge[lgHash] = curr + i;
  43            /* Only load extra positions for ZSTD_dtlm_full */
  44            if (dtlm == ZSTD_dtlm_fast)
  45                break;
  46    }   }
  47}
  48
  49
  50FORCE_INLINE_TEMPLATE
  51size_t ZSTD_compressBlock_doubleFast_generic(
  52        ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
  53        void const* src, size_t srcSize,
  54        U32 const mls /* template */, ZSTD_dictMode_e const dictMode)
  55{
  56    ZSTD_compressionParameters const* cParams = &ms->cParams;
  57    U32* const hashLong = ms->hashTable;
  58    const U32 hBitsL = cParams->hashLog;
  59    U32* const hashSmall = ms->chainTable;
  60    const U32 hBitsS = cParams->chainLog;
  61    const BYTE* const base = ms->window.base;
  62    const BYTE* const istart = (const BYTE*)src;
  63    const BYTE* ip = istart;
  64    const BYTE* anchor = istart;
  65    const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);
  66    /* presumes that, if there is a dictionary, it must be using Attach mode */
  67    const U32 prefixLowestIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog);
  68    const BYTE* const prefixLowest = base + prefixLowestIndex;
  69    const BYTE* const iend = istart + srcSize;
  70    const BYTE* const ilimit = iend - HASH_READ_SIZE;
  71    U32 offset_1=rep[0], offset_2=rep[1];
  72    U32 offsetSaved = 0;
  73
  74    const ZSTD_matchState_t* const dms = ms->dictMatchState;
  75    const ZSTD_compressionParameters* const dictCParams =
  76                                     dictMode == ZSTD_dictMatchState ?
  77                                     &dms->cParams : NULL;
  78    const U32* const dictHashLong  = dictMode == ZSTD_dictMatchState ?
  79                                     dms->hashTable : NULL;
  80    const U32* const dictHashSmall = dictMode == ZSTD_dictMatchState ?
  81                                     dms->chainTable : NULL;
  82    const U32 dictStartIndex       = dictMode == ZSTD_dictMatchState ?
  83                                     dms->window.dictLimit : 0;
  84    const BYTE* const dictBase     = dictMode == ZSTD_dictMatchState ?
  85                                     dms->window.base : NULL;
  86    const BYTE* const dictStart    = dictMode == ZSTD_dictMatchState ?
  87                                     dictBase + dictStartIndex : NULL;
  88    const BYTE* const dictEnd      = dictMode == ZSTD_dictMatchState ?
  89                                     dms->window.nextSrc : NULL;
  90    const U32 dictIndexDelta       = dictMode == ZSTD_dictMatchState ?
  91                                     prefixLowestIndex - (U32)(dictEnd - dictBase) :
  92                                     0;
  93    const U32 dictHBitsL           = dictMode == ZSTD_dictMatchState ?
  94                                     dictCParams->hashLog : hBitsL;
  95    const U32 dictHBitsS           = dictMode == ZSTD_dictMatchState ?
  96                                     dictCParams->chainLog : hBitsS;
  97    const U32 dictAndPrefixLength  = (U32)((ip - prefixLowest) + (dictEnd - dictStart));
  98
  99    DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_generic");
 100
 101    assert(dictMode == ZSTD_noDict || dictMode == ZSTD_dictMatchState);
 102
 103    /* if a dictionary is attached, it must be within window range */
 104    if (dictMode == ZSTD_dictMatchState) {
 105        assert(ms->window.dictLimit + (1U << cParams->windowLog) >= endIndex);
 106    }
 107
 108    /* init */
 109    ip += (dictAndPrefixLength == 0);
 110    if (dictMode == ZSTD_noDict) {
 111        U32 const curr = (U32)(ip - base);
 112        U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, curr, cParams->windowLog);
 113        U32 const maxRep = curr - windowLow;
 114        if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
 115        if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
 116    }
 117    if (dictMode == ZSTD_dictMatchState) {
 118        /* dictMatchState repCode checks don't currently handle repCode == 0
 119         * disabling. */
 120        assert(offset_1 <= dictAndPrefixLength);
 121        assert(offset_2 <= dictAndPrefixLength);
 122    }
 123
 124    /* Main Search Loop */
 125    while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */
 126        size_t mLength;
 127        U32 offset;
 128        size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
 129        size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
 130        size_t const dictHL = ZSTD_hashPtr(ip, dictHBitsL, 8);
 131        size_t const dictHS = ZSTD_hashPtr(ip, dictHBitsS, mls);
 132        U32 const curr = (U32)(ip-base);
 133        U32 const matchIndexL = hashLong[h2];
 134        U32 matchIndexS = hashSmall[h];
 135        const BYTE* matchLong = base + matchIndexL;
 136        const BYTE* match = base + matchIndexS;
 137        const U32 repIndex = curr + 1 - offset_1;
 138        const BYTE* repMatch = (dictMode == ZSTD_dictMatchState
 139                            && repIndex < prefixLowestIndex) ?
 140                               dictBase + (repIndex - dictIndexDelta) :
 141                               base + repIndex;
 142        hashLong[h2] = hashSmall[h] = curr;   /* update hash tables */
 143
 144        /* check dictMatchState repcode */
 145        if (dictMode == ZSTD_dictMatchState
 146            && ((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */)
 147            && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
 148            const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend;
 149            mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4;
 150            ip++;
 151            ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH);
 152            goto _match_stored;
 153        }
 154
 155        /* check noDict repcode */
 156        if ( dictMode == ZSTD_noDict
 157          && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) {
 158            mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
 159            ip++;
 160            ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH);
 161            goto _match_stored;
 162        }
 163
 164        if (matchIndexL > prefixLowestIndex) {
 165            /* check prefix long match */
 166            if (MEM_read64(matchLong) == MEM_read64(ip)) {
 167                mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
 168                offset = (U32)(ip-matchLong);
 169                while (((ip>anchor) & (matchLong>prefixLowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
 170                goto _match_found;
 171            }
 172        } else if (dictMode == ZSTD_dictMatchState) {
 173            /* check dictMatchState long match */
 174            U32 const dictMatchIndexL = dictHashLong[dictHL];
 175            const BYTE* dictMatchL = dictBase + dictMatchIndexL;
 176            assert(dictMatchL < dictEnd);
 177
 178            if (dictMatchL > dictStart && MEM_read64(dictMatchL) == MEM_read64(ip)) {
 179                mLength = ZSTD_count_2segments(ip+8, dictMatchL+8, iend, dictEnd, prefixLowest) + 8;
 180                offset = (U32)(curr - dictMatchIndexL - dictIndexDelta);
 181                while (((ip>anchor) & (dictMatchL>dictStart)) && (ip[-1] == dictMatchL[-1])) { ip--; dictMatchL--; mLength++; } /* catch up */
 182                goto _match_found;
 183        }   }
 184
 185        if (matchIndexS > prefixLowestIndex) {
 186            /* check prefix short match */
 187            if (MEM_read32(match) == MEM_read32(ip)) {
 188                goto _search_next_long;
 189            }
 190        } else if (dictMode == ZSTD_dictMatchState) {
 191            /* check dictMatchState short match */
 192            U32 const dictMatchIndexS = dictHashSmall[dictHS];
 193            match = dictBase + dictMatchIndexS;
 194            matchIndexS = dictMatchIndexS + dictIndexDelta;
 195
 196            if (match > dictStart && MEM_read32(match) == MEM_read32(ip)) {
 197                goto _search_next_long;
 198        }   }
 199
 200        ip += ((ip-anchor) >> kSearchStrength) + 1;
 201#if defined(__aarch64__)
 202        PREFETCH_L1(ip+256);
 203#endif
 204        continue;
 205
 206_search_next_long:
 207
 208        {   size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
 209            size_t const dictHLNext = ZSTD_hashPtr(ip+1, dictHBitsL, 8);
 210            U32 const matchIndexL3 = hashLong[hl3];
 211            const BYTE* matchL3 = base + matchIndexL3;
 212            hashLong[hl3] = curr + 1;
 213
 214            /* check prefix long +1 match */
 215            if (matchIndexL3 > prefixLowestIndex) {
 216                if (MEM_read64(matchL3) == MEM_read64(ip+1)) {
 217                    mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;
 218                    ip++;
 219                    offset = (U32)(ip-matchL3);
 220                    while (((ip>anchor) & (matchL3>prefixLowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */
 221                    goto _match_found;
 222                }
 223            } else if (dictMode == ZSTD_dictMatchState) {
 224                /* check dict long +1 match */
 225                U32 const dictMatchIndexL3 = dictHashLong[dictHLNext];
 226                const BYTE* dictMatchL3 = dictBase + dictMatchIndexL3;
 227                assert(dictMatchL3 < dictEnd);
 228                if (dictMatchL3 > dictStart && MEM_read64(dictMatchL3) == MEM_read64(ip+1)) {
 229                    mLength = ZSTD_count_2segments(ip+1+8, dictMatchL3+8, iend, dictEnd, prefixLowest) + 8;
 230                    ip++;
 231                    offset = (U32)(curr + 1 - dictMatchIndexL3 - dictIndexDelta);
 232                    while (((ip>anchor) & (dictMatchL3>dictStart)) && (ip[-1] == dictMatchL3[-1])) { ip--; dictMatchL3--; mLength++; } /* catch up */
 233                    goto _match_found;
 234        }   }   }
 235
 236        /* if no long +1 match, explore the short match we found */
 237        if (dictMode == ZSTD_dictMatchState && matchIndexS < prefixLowestIndex) {
 238            mLength = ZSTD_count_2segments(ip+4, match+4, iend, dictEnd, prefixLowest) + 4;
 239            offset = (U32)(curr - matchIndexS);
 240            while (((ip>anchor) & (match>dictStart)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
 241        } else {
 242            mLength = ZSTD_count(ip+4, match+4, iend) + 4;
 243            offset = (U32)(ip - match);
 244            while (((ip>anchor) & (match>prefixLowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
 245        }
 246
 247_match_found:
 248        offset_2 = offset_1;
 249        offset_1 = offset;
 250
 251        ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
 252
 253_match_stored:
 254        /* match found */
 255        ip += mLength;
 256        anchor = ip;
 257
 258        if (ip <= ilimit) {
 259            /* Complementary insertion */
 260            /* done after iLimit test, as candidates could be > iend-8 */
 261            {   U32 const indexToInsert = curr+2;
 262                hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
 263                hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
 264                hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
 265                hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
 266            }
 267
 268            /* check immediate repcode */
 269            if (dictMode == ZSTD_dictMatchState) {
 270                while (ip <= ilimit) {
 271                    U32 const current2 = (U32)(ip-base);
 272                    U32 const repIndex2 = current2 - offset_2;
 273                    const BYTE* repMatch2 = dictMode == ZSTD_dictMatchState
 274                        && repIndex2 < prefixLowestIndex ?
 275                            dictBase + repIndex2 - dictIndexDelta :
 276                            base + repIndex2;
 277                    if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */)
 278                       && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
 279                        const BYTE* const repEnd2 = repIndex2 < prefixLowestIndex ? dictEnd : iend;
 280                        size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixLowest) + 4;
 281                        U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
 282                        ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, repLength2-MINMATCH);
 283                        hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
 284                        hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
 285                        ip += repLength2;
 286                        anchor = ip;
 287                        continue;
 288                    }
 289                    break;
 290            }   }
 291
 292            if (dictMode == ZSTD_noDict) {
 293                while ( (ip <= ilimit)
 294                     && ( (offset_2>0)
 295                        & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
 296                    /* store sequence */
 297                    size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
 298                    U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff;  /* swap offset_2 <=> offset_1 */
 299                    hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
 300                    hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
 301                    ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, rLength-MINMATCH);
 302                    ip += rLength;
 303                    anchor = ip;
 304                    continue;   /* faster when present ... (?) */
 305        }   }   }
 306    }   /* while (ip < ilimit) */
 307
 308    /* save reps for next block */
 309    rep[0] = offset_1 ? offset_1 : offsetSaved;
 310    rep[1] = offset_2 ? offset_2 : offsetSaved;
 311
 312    /* Return the last literals size */
 313    return (size_t)(iend - anchor);
 314}
 315
 316
 317size_t ZSTD_compressBlock_doubleFast(
 318        ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 319        void const* src, size_t srcSize)
 320{
 321    const U32 mls = ms->cParams.minMatch;
 322    switch(mls)
 323    {
 324    default: /* includes case 3 */
 325    case 4 :
 326        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_noDict);
 327    case 5 :
 328        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_noDict);
 329    case 6 :
 330        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_noDict);
 331    case 7 :
 332        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_noDict);
 333    }
 334}
 335
 336
 337size_t ZSTD_compressBlock_doubleFast_dictMatchState(
 338        ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 339        void const* src, size_t srcSize)
 340{
 341    const U32 mls = ms->cParams.minMatch;
 342    switch(mls)
 343    {
 344    default: /* includes case 3 */
 345    case 4 :
 346        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_dictMatchState);
 347    case 5 :
 348        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_dictMatchState);
 349    case 6 :
 350        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_dictMatchState);
 351    case 7 :
 352        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_dictMatchState);
 353    }
 354}
 355
 356
 357static size_t ZSTD_compressBlock_doubleFast_extDict_generic(
 358        ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 359        void const* src, size_t srcSize,
 360        U32 const mls /* template */)
 361{
 362    ZSTD_compressionParameters const* cParams = &ms->cParams;
 363    U32* const hashLong = ms->hashTable;
 364    U32  const hBitsL = cParams->hashLog;
 365    U32* const hashSmall = ms->chainTable;
 366    U32  const hBitsS = cParams->chainLog;
 367    const BYTE* const istart = (const BYTE*)src;
 368    const BYTE* ip = istart;
 369    const BYTE* anchor = istart;
 370    const BYTE* const iend = istart + srcSize;
 371    const BYTE* const ilimit = iend - 8;
 372    const BYTE* const base = ms->window.base;
 373    const U32   endIndex = (U32)((size_t)(istart - base) + srcSize);
 374    const U32   lowLimit = ZSTD_getLowestMatchIndex(ms, endIndex, cParams->windowLog);
 375    const U32   dictStartIndex = lowLimit;
 376    const U32   dictLimit = ms->window.dictLimit;
 377    const U32   prefixStartIndex = (dictLimit > lowLimit) ? dictLimit : lowLimit;
 378    const BYTE* const prefixStart = base + prefixStartIndex;
 379    const BYTE* const dictBase = ms->window.dictBase;
 380    const BYTE* const dictStart = dictBase + dictStartIndex;
 381    const BYTE* const dictEnd = dictBase + prefixStartIndex;
 382    U32 offset_1=rep[0], offset_2=rep[1];
 383
 384    DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_extDict_generic (srcSize=%zu)", srcSize);
 385
 386    /* if extDict is invalidated due to maxDistance, switch to "regular" variant */
 387    if (prefixStartIndex == dictStartIndex)
 388        return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, mls, ZSTD_noDict);
 389
 390    /* Search Loop */
 391    while (ip < ilimit) {  /* < instead of <=, because (ip+1) */
 392        const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
 393        const U32 matchIndex = hashSmall[hSmall];
 394        const BYTE* const matchBase = matchIndex < prefixStartIndex ? dictBase : base;
 395        const BYTE* match = matchBase + matchIndex;
 396
 397        const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
 398        const U32 matchLongIndex = hashLong[hLong];
 399        const BYTE* const matchLongBase = matchLongIndex < prefixStartIndex ? dictBase : base;
 400        const BYTE* matchLong = matchLongBase + matchLongIndex;
 401
 402        const U32 curr = (U32)(ip-base);
 403        const U32 repIndex = curr + 1 - offset_1;   /* offset_1 expected <= curr +1 */
 404        const BYTE* const repBase = repIndex < prefixStartIndex ? dictBase : base;
 405        const BYTE* const repMatch = repBase + repIndex;
 406        size_t mLength;
 407        hashSmall[hSmall] = hashLong[hLong] = curr;   /* update hash table */
 408
 409        if ((((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex doesn't overlap dict + prefix */
 410            & (repIndex > dictStartIndex))
 411          && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
 412            const BYTE* repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;
 413            mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4;
 414            ip++;
 415            ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH);
 416        } else {
 417            if ((matchLongIndex > dictStartIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
 418                const BYTE* const matchEnd = matchLongIndex < prefixStartIndex ? dictEnd : iend;
 419                const BYTE* const lowMatchPtr = matchLongIndex < prefixStartIndex ? dictStart : prefixStart;
 420                U32 offset;
 421                mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, prefixStart) + 8;
 422                offset = curr - matchLongIndex;
 423                while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; }   /* catch up */
 424                offset_2 = offset_1;
 425                offset_1 = offset;
 426                ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
 427
 428            } else if ((matchIndex > dictStartIndex) && (MEM_read32(match) == MEM_read32(ip))) {
 429                size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
 430                U32 const matchIndex3 = hashLong[h3];
 431                const BYTE* const match3Base = matchIndex3 < prefixStartIndex ? dictBase : base;
 432                const BYTE* match3 = match3Base + matchIndex3;
 433                U32 offset;
 434                hashLong[h3] = curr + 1;
 435                if ( (matchIndex3 > dictStartIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
 436                    const BYTE* const matchEnd = matchIndex3 < prefixStartIndex ? dictEnd : iend;
 437                    const BYTE* const lowMatchPtr = matchIndex3 < prefixStartIndex ? dictStart : prefixStart;
 438                    mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, prefixStart) + 8;
 439                    ip++;
 440                    offset = curr+1 - matchIndex3;
 441                    while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
 442                } else {
 443                    const BYTE* const matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend;
 444                    const BYTE* const lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart;
 445                    mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4;
 446                    offset = curr - matchIndex;
 447                    while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */
 448                }
 449                offset_2 = offset_1;
 450                offset_1 = offset;
 451                ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
 452
 453            } else {
 454                ip += ((ip-anchor) >> kSearchStrength) + 1;
 455                continue;
 456        }   }
 457
 458        /* move to next sequence start */
 459        ip += mLength;
 460        anchor = ip;
 461
 462        if (ip <= ilimit) {
 463            /* Complementary insertion */
 464            /* done after iLimit test, as candidates could be > iend-8 */
 465            {   U32 const indexToInsert = curr+2;
 466                hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
 467                hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
 468                hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
 469                hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
 470            }
 471
 472            /* check immediate repcode */
 473            while (ip <= ilimit) {
 474                U32 const current2 = (U32)(ip-base);
 475                U32 const repIndex2 = current2 - offset_2;
 476                const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2;
 477                if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3)   /* intentional overflow : ensure repIndex2 doesn't overlap dict + prefix */
 478                    & (repIndex2 > dictStartIndex))
 479                  && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
 480                    const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;
 481                    size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;
 482                    U32 const tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
 483                    ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, repLength2-MINMATCH);
 484                    hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
 485                    hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
 486                    ip += repLength2;
 487                    anchor = ip;
 488                    continue;
 489                }
 490                break;
 491    }   }   }
 492
 493    /* save reps for next block */
 494    rep[0] = offset_1;
 495    rep[1] = offset_2;
 496
 497    /* Return the last literals size */
 498    return (size_t)(iend - anchor);
 499}
 500
 501
 502size_t ZSTD_compressBlock_doubleFast_extDict(
 503        ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 504        void const* src, size_t srcSize)
 505{
 506    U32 const mls = ms->cParams.minMatch;
 507    switch(mls)
 508    {
 509    default: /* includes case 3 */
 510    case 4 :
 511        return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 4);
 512    case 5 :
 513        return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 5);
 514    case 6 :
 515        return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 6);
 516    case 7 :
 517        return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 7);
 518    }
 519}
 520