/* * Copyright (c) Yann Collet, Facebook, Inc. * All rights reserved. * * This source code is licensed under both the BSD-style license (found in the * LICENSE file in the root directory of this source tree) and the GPLv2 (found * in the COPYING file in the root directory of this source tree). * You may select, at your option, one of the above-listed licenses. */ #include "zstd_compress_internal.h" #include "zstd_lazy.h" /*-************************************* * Binary Tree search ***************************************/ static void ZSTD_updateDUBT(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend, U32 mls) { … } /* ZSTD_insertDUBT1() : * sort one already inserted but unsorted position * assumption : curr >= btlow == (curr - btmask) * doesn't fail */ static void ZSTD_insertDUBT1(const ZSTD_matchState_t* ms, U32 curr, const BYTE* inputEnd, U32 nbCompares, U32 btLow, const ZSTD_dictMode_e dictMode) { … } static size_t ZSTD_DUBT_findBetterDictMatch ( const ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iend, size_t* offsetPtr, size_t bestLength, U32 nbCompares, U32 const mls, const ZSTD_dictMode_e dictMode) { … } static size_t ZSTD_DUBT_findBestMatch(ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iend, size_t* offsetPtr, U32 const mls, const ZSTD_dictMode_e dictMode) { … } /* ZSTD_BtFindBestMatch() : Tree updater, providing best match */ FORCE_INLINE_TEMPLATE size_t ZSTD_BtFindBestMatch( ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iLimit, size_t* offsetPtr, const U32 mls /* template */, const ZSTD_dictMode_e dictMode) { … } /* ********************************* * Dedicated dict search ***********************************/ void ZSTD_dedicatedDictSearch_lazy_loadDictionary(ZSTD_matchState_t* ms, const BYTE* const ip) { … } /* Returns the longest match length found in the dedicated dict search structure. * If none are longer than the argument ml, then ml will be returned. */ FORCE_INLINE_TEMPLATE size_t ZSTD_dedicatedDictSearch_lazy_search(size_t* offsetPtr, size_t ml, U32 nbAttempts, const ZSTD_matchState_t* const dms, const BYTE* const ip, const BYTE* const iLimit, const BYTE* const prefixStart, const U32 curr, const U32 dictLimit, const size_t ddsIdx) { … } /* ********************************* * Hash Chain ***********************************/ #define NEXT_IN_CHAIN(d, mask) … /* Update chains up to ip (excluded) Assumption : always within prefix (i.e. not within extDict) */ FORCE_INLINE_TEMPLATE U32 ZSTD_insertAndFindFirstIndex_internal( ZSTD_matchState_t* ms, const ZSTD_compressionParameters* const cParams, const BYTE* ip, U32 const mls) { … } U32 ZSTD_insertAndFindFirstIndex(ZSTD_matchState_t* ms, const BYTE* ip) { … } /* inlining is important to hardwire a hot branch (template emulation) */ FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch( ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iLimit, size_t* offsetPtr, const U32 mls, const ZSTD_dictMode_e dictMode) { … } /* ********************************* * (SIMD) Row-based matchfinder ***********************************/ /* Constants for row-based hash */ #define ZSTD_ROW_HASH_TAG_OFFSET … #define ZSTD_ROW_HASH_TAG_BITS … #define ZSTD_ROW_HASH_TAG_MASK … #define ZSTD_ROW_HASH_MAX_ENTRIES … #define ZSTD_ROW_HASH_CACHE_MASK … ZSTD_VecMask; /* Clarifies when we are interacting with a U64 representing a mask of matches */ /* ZSTD_VecMask_next(): * Starting from the LSB, returns the idx of the next non-zero bit. * Basically counting the nb of trailing zeroes. */ static U32 ZSTD_VecMask_next(ZSTD_VecMask val) { … } /* ZSTD_rotateRight_*(): * Rotates a bitfield to the right by "count" bits. * https://en.wikipedia.org/w/index.php?title=Circular_shift&oldid=991635599#Implementing_circular_shifts */ FORCE_INLINE_TEMPLATE U64 ZSTD_rotateRight_U64(U64 const value, U32 count) { … } FORCE_INLINE_TEMPLATE U32 ZSTD_rotateRight_U32(U32 const value, U32 count) { … } FORCE_INLINE_TEMPLATE U16 ZSTD_rotateRight_U16(U16 const value, U32 count) { … } /* ZSTD_row_nextIndex(): * Returns the next index to insert at within a tagTable row, and updates the "head" * value to reflect the update. Essentially cycles backwards from [0, {entries per row}) */ FORCE_INLINE_TEMPLATE U32 ZSTD_row_nextIndex(BYTE* const tagRow, U32 const rowMask) { … } /* ZSTD_isAligned(): * Checks that a pointer is aligned to "align" bytes which must be a power of 2. */ MEM_STATIC int ZSTD_isAligned(void const* ptr, size_t align) { … } /* ZSTD_row_prefetch(): * Performs prefetching for the hashTable and tagTable at a given row. */ FORCE_INLINE_TEMPLATE void ZSTD_row_prefetch(U32 const* hashTable, U16 const* tagTable, U32 const relRow, U32 const rowLog) { … } /* ZSTD_row_fillHashCache(): * Fill up the hash cache starting at idx, prefetching up to ZSTD_ROW_HASH_CACHE_SIZE entries, * but not beyond iLimit. */ FORCE_INLINE_TEMPLATE void ZSTD_row_fillHashCache(ZSTD_matchState_t* ms, const BYTE* base, U32 const rowLog, U32 const mls, U32 idx, const BYTE* const iLimit) { … } /* ZSTD_row_nextCachedHash(): * Returns the hash of base + idx, and replaces the hash in the hash cache with the byte at * base + idx + ZSTD_ROW_HASH_CACHE_SIZE. Also prefetches the appropriate rows from hashTable and tagTable. */ FORCE_INLINE_TEMPLATE U32 ZSTD_row_nextCachedHash(U32* cache, U32 const* hashTable, U16 const* tagTable, BYTE const* base, U32 idx, U32 const hashLog, U32 const rowLog, U32 const mls) { … } /* ZSTD_row_update_internalImpl(): * Updates the hash table with positions starting from updateStartIdx until updateEndIdx. */ FORCE_INLINE_TEMPLATE void ZSTD_row_update_internalImpl(ZSTD_matchState_t* ms, U32 updateStartIdx, U32 const updateEndIdx, U32 const mls, U32 const rowLog, U32 const rowMask, U32 const useCache) { … } /* ZSTD_row_update_internal(): * Inserts the byte at ip into the appropriate position in the hash table, and updates ms->nextToUpdate. * Skips sections of long matches as is necessary. */ FORCE_INLINE_TEMPLATE void ZSTD_row_update_internal(ZSTD_matchState_t* ms, const BYTE* ip, U32 const mls, U32 const rowLog, U32 const rowMask, U32 const useCache) { … } /* ZSTD_row_update(): * External wrapper for ZSTD_row_update_internal(). Used for filling the hashtable during dictionary * processing. */ void ZSTD_row_update(ZSTD_matchState_t* const ms, const BYTE* ip) { … } #if defined(ZSTD_ARCH_X86_SSE2) FORCE_INLINE_TEMPLATE ZSTD_VecMask ZSTD_row_getSSEMask(int nbChunks, const BYTE* const src, const BYTE tag, const U32 head) { const __m128i comparisonMask = _mm_set1_epi8((char)tag); int matches[4] = {0}; int i; assert(nbChunks == 1 || nbChunks == 2 || nbChunks == 4); for (i=0; i<nbChunks; i++) { const __m128i chunk = _mm_loadu_si128((const __m128i*)(const void*)(src + 16*i)); const __m128i equalMask = _mm_cmpeq_epi8(chunk, comparisonMask); matches[i] = _mm_movemask_epi8(equalMask); } if (nbChunks == 1) return ZSTD_rotateRight_U16((U16)matches[0], head); if (nbChunks == 2) return ZSTD_rotateRight_U32((U32)matches[1] << 16 | (U32)matches[0], head); assert(nbChunks == 4); return ZSTD_rotateRight_U64((U64)matches[3] << 48 | (U64)matches[2] << 32 | (U64)matches[1] << 16 | (U64)matches[0], head); } #endif /* Returns a ZSTD_VecMask (U32) that has the nth bit set to 1 if the newly-computed "tag" matches * the hash at the nth position in a row of the tagTable. * Each row is a circular buffer beginning at the value of "head". So we must rotate the "matches" bitfield * to match up with the actual layout of the entries within the hashTable */ FORCE_INLINE_TEMPLATE ZSTD_VecMask ZSTD_row_getMatchMask(const BYTE* const tagRow, const BYTE tag, const U32 head, const U32 rowEntries) { … } /* The high-level approach of the SIMD row based match finder is as follows: * - Figure out where to insert the new entry: * - Generate a hash from a byte along with an additional 1-byte "short hash". The additional byte is our "tag" * - The hashTable is effectively split into groups or "rows" of 16 or 32 entries of U32, and the hash determines * which row to insert into. * - Determine the correct position within the row to insert the entry into. Each row of 16 or 32 can * be considered as a circular buffer with a "head" index that resides in the tagTable. * - Also insert the "tag" into the equivalent row and position in the tagTable. * - Note: The tagTable has 17 or 33 1-byte entries per row, due to 16 or 32 tags, and 1 "head" entry. * The 17 or 33 entry rows are spaced out to occur every 32 or 64 bytes, respectively, * for alignment/performance reasons, leaving some bytes unused. * - Use SIMD to efficiently compare the tags in the tagTable to the 1-byte "short hash" and * generate a bitfield that we can cycle through to check the collisions in the hash table. * - Pick the longest match. */ FORCE_INLINE_TEMPLATE size_t ZSTD_RowFindBestMatch( ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iLimit, size_t* offsetPtr, const U32 mls, const ZSTD_dictMode_e dictMode, const U32 rowLog) { … } /* * Generate search functions templated on (dictMode, mls, rowLog). * These functions are outlined for code size & compilation time. * ZSTD_searchMax() dispatches to the correct implementation function. * * TODO: The start of the search function involves loading and calculating a * bunch of constants from the ZSTD_matchState_t. These computations could be * done in an initialization function, and saved somewhere in the match state. * Then we could pass a pointer to the saved state instead of the match state, * and avoid duplicate computations. * * TODO: Move the match re-winding into searchMax. This improves compression * ratio, and unlocks further simplifications with the next TODO. * * TODO: Try moving the repcode search into searchMax. After the re-winding * and repcode search are in searchMax, there is no more logic in the match * finder loop that requires knowledge about the dictMode. So we should be * able to avoid force inlining it, and we can join the extDict loop with * the single segment loop. It should go in searchMax instead of its own * function to avoid having multiple virtual function calls per search. */ #define ZSTD_BT_SEARCH_FN(dictMode, mls) … #define ZSTD_HC_SEARCH_FN(dictMode, mls) … #define ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog) … #define ZSTD_SEARCH_FN_ATTRS … #define GEN_ZSTD_BT_SEARCH_FN(dictMode, mls) … \ #define GEN_ZSTD_HC_SEARCH_FN(dictMode, mls) … \ #define GEN_ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog) … \ #define ZSTD_FOR_EACH_ROWLOG(X, dictMode, mls) … #define ZSTD_FOR_EACH_MLS_ROWLOG(X, dictMode) … #define ZSTD_FOR_EACH_MLS(X, dictMode) … #define ZSTD_FOR_EACH_DICT_MODE(X, ...) … /* Generate row search fns for each combination of (dictMode, mls, rowLog) */ ZSTD_FOR_EACH_DICT_MODE(…) /* Generate binary Tree search fns for each combination of (dictMode, mls) */ ZSTD_FOR_EACH_DICT_MODE(…) /* Generate hash chain search fns for each combination of (dictMode, mls) */ ZSTD_FOR_EACH_DICT_MODE(…) searchMethod_e; #define GEN_ZSTD_CALL_BT_SEARCH_FN(dictMode, mls) … #define GEN_ZSTD_CALL_HC_SEARCH_FN(dictMode, mls) … #define GEN_ZSTD_CALL_ROW_SEARCH_FN(dictMode, mls, rowLog) … #define ZSTD_SWITCH_MLS(X, dictMode) … #define ZSTD_SWITCH_ROWLOG(dictMode, mls) … #define ZSTD_SWITCH_SEARCH_METHOD(dictMode) … /* * Searches for the longest match at @p ip. * Dispatches to the correct implementation function based on the * (searchMethod, dictMode, mls, rowLog). We use switch statements * here instead of using an indirect function call through a function * pointer because after Spectre and Meltdown mitigations, indirect * function calls can be very costly, especially in the kernel. * * NOTE: dictMode and searchMethod should be templated, so those switch * statements should be optimized out. Only the mls & rowLog switches * should be left. * * @param ms The match state. * @param ip The position to search at. * @param iend The end of the input data. * @param[out] offsetPtr Stores the match offset into this pointer. * @param mls The minimum search length, in the range [4, 6]. * @param rowLog The row log (if applicable), in the range [4, 6]. * @param searchMethod The search method to use (templated). * @param dictMode The dictMode (templated). * * @returns The length of the longest match found, or < mls if no match is found. * If a match is found its offset is stored in @p offsetPtr. */ FORCE_INLINE_TEMPLATE size_t ZSTD_searchMax( ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend, size_t* offsetPtr, U32 const mls, U32 const rowLog, searchMethod_e const searchMethod, ZSTD_dictMode_e const dictMode) { … } /* ******************************* * Common parser - lazy strategy *********************************/ FORCE_INLINE_TEMPLATE size_t ZSTD_compressBlock_lazy_generic( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize, const searchMethod_e searchMethod, const U32 depth, ZSTD_dictMode_e const dictMode) { … } size_t ZSTD_compressBlock_btlazy2( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_btlazy2_dictMatchState( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2_dictMatchState( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_dictMatchState( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy_dictMatchState( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2_dedicatedDictSearch( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_dedicatedDictSearch( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy_dedicatedDictSearch( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } /* Row-based matchfinder */ size_t ZSTD_compressBlock_lazy2_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2_dictMatchState_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_dictMatchState_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy_dictMatchState_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2_dedicatedDictSearch_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_dedicatedDictSearch_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy_dedicatedDictSearch_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } FORCE_INLINE_TEMPLATE size_t ZSTD_compressBlock_lazy_extDict_generic( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize, const searchMethod_e searchMethod, const U32 depth) { … } size_t ZSTD_compressBlock_greedy_extDict( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_extDict( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2_extDict( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_btlazy2_extDict( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_greedy_extDict_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy_extDict_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … } size_t ZSTD_compressBlock_lazy2_extDict_row( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], void const* src, size_t srcSize) { … }
Codebase Browser
linux