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_double_fast.h"

    13 

    14 

    15 void ZSTD_fillDoubleHashTable(ZSTD_matchState_t* ms,

    16                               ZSTD_compressionParameters const* cParams,

    17                               void const* end)

    18 {

    19     U32* const hashLarge = ms->hashTable;

    20     U32  const hBitsL = cParams->hashLog;

    21     U32  const mls = cParams->searchLength;

    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 current = (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] = current + i;

    41             if (i == 0 || hashLarge[lgHash] == 0)

    42                 hashLarge[lgHash] = current + i;

    43         }

    44     }

    45 }

    46 

    47 

    48 FORCE_INLINE_TEMPLATE

    49 size_t ZSTD_compressBlock_doubleFast_generic(

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

    51         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize,

    52         U32 const mls /* template */)

    53 {

    54     U32* const hashLong = ms->hashTable;

    55     const U32 hBitsL = cParams->hashLog;

    56     U32* const hashSmall = ms->chainTable;

    57     const U32 hBitsS = cParams->chainLog;

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

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

    60     const BYTE* ip = istart;

    61     const BYTE* anchor = istart;

    62     const U32 lowestIndex = ms->window.dictLimit;

    63     const BYTE* const lowest = base + lowestIndex;

    64     const BYTE* const iend = istart + srcSize;

    65     const BYTE* const ilimit = iend - HASH_READ_SIZE;

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

    67     U32 offsetSaved = 0;

    68 

    69     /* init */

    70     ip += (ip==lowest);

    71     {   U32 const maxRep = (U32)(ip-lowest);

    72         if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;

    73         if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;

    74     }

    75 

    76     /* Main Search Loop */

    77     while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */

    78         size_t mLength;

    79         size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);

    80         size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);

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

    82         U32 const matchIndexL = hashLong[h2];

    83         U32 const matchIndexS = hashSmall[h];

    84         const BYTE* matchLong = base + matchIndexL;

    85         const BYTE* match = base + matchIndexS;

    86         hashLong[h2] = hashSmall[h] = current;   /* update hash tables */

    87 

    88         assert(offset_1 <= current);   /* supposed guaranteed by construction */

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

    90             /* favor repcode */

    91             mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;

    92             ip++;

    93             ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH);

    94         } else {

    95             U32 offset;

    96             if ( (matchIndexL > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip)) ) {

    97                 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;

    98                 offset = (U32)(ip-matchLong);

    99                 while (((ip>anchor) & (matchLong>lowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */

   100             } else if ( (matchIndexS > lowestIndex) && (MEM_read32(match) == MEM_read32(ip)) ) {

   101                 size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);

   102                 U32 const matchIndexL3 = hashLong[hl3];

   103                 const BYTE* matchL3 = base + matchIndexL3;

   104                 hashLong[hl3] = current + 1;

   105                 if ( (matchIndexL3 > lowestIndex) && (MEM_read64(matchL3) == MEM_read64(ip+1)) ) {

   106                     mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;

   107                     ip++;

   108                     offset = (U32)(ip-matchL3);

   109                     while (((ip>anchor) & (matchL3>lowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */

   110                 } else {

   111                     mLength = ZSTD_count(ip+4, match+4, iend) + 4;

   112                     offset = (U32)(ip-match);

   113                     while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */

   114                 }

   115             } else {

   116                 ip += ((ip-anchor) >> kSearchStrength) + 1;

   117                 continue;

   118             }

   119 

   120             offset_2 = offset_1;

   121             offset_1 = offset;

   122 

   123             ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);

   124         }

   125 

   126         /* match found */

   127         ip += mLength;

   128         anchor = ip;

   129 

   130         if (ip <= ilimit) {

   131             /* Fill Table */

   132             hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] =

   133                 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;  /* here because current+2 could be > iend-8 */

   134             hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] =

   135                 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);

   136 

   137             /* check immediate repcode */

   138             while ( (ip <= ilimit)

   139                  && ( (offset_2>0)

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

   141                 /* store sequence */

   142                 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;

   143                 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */

   144                 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);

   145                 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);

   146                 ZSTD_storeSeq(seqStore, 0, anchor, 0, rLength-MINMATCH);

   147                 ip += rLength;

   148                 anchor = ip;

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

   150     }   }   }

   151 

   152     /* save reps for next block */

   153     rep[0] = offset_1 ? offset_1 : offsetSaved;

   154     rep[1] = offset_2 ? offset_2 : offsetSaved;

   155 

   156     /* Return the last literals size */

   157     return iend - anchor;

   158 }

   159 

   160 

   161 size_t ZSTD_compressBlock_doubleFast(

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

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

   164 {

   165     const U32 mls = cParams->searchLength;

   166     switch(mls)

   167     {

   168     default: /* includes case 3 */

   169     case 4 :

   170         return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, cParams, src, srcSize, 4);

   171     case 5 :

   172         return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, cParams, src, srcSize, 5);

   173     case 6 :

   174         return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, cParams, src, srcSize, 6);

   175     case 7 :

   176         return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, cParams, src, srcSize, 7);

   177     }

   178 }

   179 

   180 

   181 static size_t ZSTD_compressBlock_doubleFast_extDict_generic(

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

   183         ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize,

   184         U32 const mls /* template */)

   185 {

   186     U32* const hashLong = ms->hashTable;

   187     U32  const hBitsL = cParams->hashLog;

   188     U32* const hashSmall = ms->chainTable;

   189     U32  const hBitsS = cParams->chainLog;

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

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

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

   193     const BYTE* ip = istart;

   194     const BYTE* anchor = istart;

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

   196     const BYTE* const dictStart = dictBase + lowestIndex;

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

   198     const BYTE* const lowPrefixPtr = base + dictLimit;

   199     const BYTE* const dictEnd = dictBase + dictLimit;

   200     const BYTE* const iend = istart + srcSize;

   201     const BYTE* const ilimit = iend - 8;

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

   203 

   204     /* Search Loop */

   205     while (ip < ilimit) {  /* < instead of <=, because (ip+1) */

   206         const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);

   207         const U32 matchIndex = hashSmall[hSmall];

   208         const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;

   209         const BYTE* match = matchBase + matchIndex;

   210 

   211         const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);

   212         const U32 matchLongIndex = hashLong[hLong];

   213         const BYTE* matchLongBase = matchLongIndex < dictLimit ? dictBase : base;

   214         const BYTE* matchLong = matchLongBase + matchLongIndex;

   215 

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

   217         const U32 repIndex = current + 1 - offset_1;   /* offset_1 expected <= current +1 */

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

   219         const BYTE* repMatch = repBase + repIndex;

   220         size_t mLength;

   221         hashSmall[hSmall] = hashLong[hLong] = current;   /* update hash table */

   222 

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

   224            && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {

   225             const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;

   226             mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;

   227             ip++;

   228             ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH);

   229         } else {

   230             if ((matchLongIndex > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {

   231                 const BYTE* matchEnd = matchLongIndex < dictLimit ? dictEnd : iend;

   232                 const BYTE* lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr;

   233                 U32 offset;

   234                 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, lowPrefixPtr) + 8;

   235                 offset = current - matchLongIndex;

   236                 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; }   /* catch up */

   237                 offset_2 = offset_1;

   238                 offset_1 = offset;

   239                 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);

   240 

   241             } else if ((matchIndex > lowestIndex) && (MEM_read32(match) == MEM_read32(ip))) {

   242                 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);

   243                 U32 const matchIndex3 = hashLong[h3];

   244                 const BYTE* const match3Base = matchIndex3 < dictLimit ? dictBase : base;

   245                 const BYTE* match3 = match3Base + matchIndex3;

   246                 U32 offset;

   247                 hashLong[h3] = current + 1;

   248                 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {

   249                     const BYTE* matchEnd = matchIndex3 < dictLimit ? dictEnd : iend;

   250                     const BYTE* lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr;

   251                     mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, lowPrefixPtr) + 8;

   252                     ip++;

   253                     offset = current+1 - matchIndex3;

   254                     while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */

   255                 } else {

   256                     const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;

   257                     const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;

   258                     mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;

   259                     offset = current - matchIndex;

   260                     while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */

   261                 }

   262                 offset_2 = offset_1;

   263                 offset_1 = offset;

   264                 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);

   265 

   266             } else {

   267                 ip += ((ip-anchor) >> kSearchStrength) + 1;

   268                 continue;

   269         }   }

   270 

   271         /* found a match : store it */

   272         ip += mLength;

   273         anchor = ip;

   274 

   275         if (ip <= ilimit) {

   276             /* Fill Table */

   277             hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;

   278             hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = current+2;

   279             hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);

   280             hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);

   281             /* check immediate repcode */

   282             while (ip <= ilimit) {

   283                 U32 const current2 = (U32)(ip-base);

   284                 U32 const repIndex2 = current2 - offset_2;

   285                 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;

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

   287                    && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {

   288                     const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;

   289                     size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;

   290                     U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */

   291                     ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH);

   292                     hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;

   293                     hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;

   294                     ip += repLength2;

   295                     anchor = ip;

   296                     continue;

   297                 }

   298                 break;

   299     }   }   }

   300 

   301     /* save reps for next block */

   302     rep[0] = offset_1;

   303     rep[1] = offset_2;

   304 

   305     /* Return the last literals size */

   306     return iend - anchor;

   307 }

   308 

   309 

   310 size_t ZSTD_compressBlock_doubleFast_extDict(

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

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

   313 {

   314     U32 const mls = cParams->searchLength;

   315     switch(mls)

   316     {

   317     default: /* includes case 3 */

   318     case 4 :

   319         return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 4);

   320     case 5 :

   321         return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 5);

   322     case 6 :

   323         return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 6);

   324     case 7 :

   325         return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, cParams, src, srcSize, 7);

   326     }

   327 }