1e0c1b49fSNick Terrell /* 2e0c1b49fSNick Terrell * Copyright (c) Yann Collet, Facebook, Inc. 3e0c1b49fSNick Terrell * All rights reserved. 4e0c1b49fSNick Terrell * 5e0c1b49fSNick Terrell * This source code is licensed under both the BSD-style license (found in the 6e0c1b49fSNick Terrell * LICENSE file in the root directory of this source tree) and the GPLv2 (found 7e0c1b49fSNick Terrell * in the COPYING file in the root directory of this source tree). 8e0c1b49fSNick Terrell * You may select, at your option, one of the above-listed licenses. 9e0c1b49fSNick Terrell */ 10e0c1b49fSNick Terrell 11e0c1b49fSNick Terrell #ifndef ZSTD_LDM_H 12e0c1b49fSNick Terrell #define ZSTD_LDM_H 13e0c1b49fSNick Terrell 14e0c1b49fSNick Terrell 15e0c1b49fSNick Terrell #include "zstd_compress_internal.h" /* ldmParams_t, U32 */ 16e0c1b49fSNick Terrell #include <linux/zstd.h> /* ZSTD_CCtx, size_t */ 17e0c1b49fSNick Terrell 18e0c1b49fSNick Terrell /*-************************************* 19e0c1b49fSNick Terrell * Long distance matching 20e0c1b49fSNick Terrell ***************************************/ 21e0c1b49fSNick Terrell 22e0c1b49fSNick Terrell #define ZSTD_LDM_DEFAULT_WINDOW_LOG ZSTD_WINDOWLOG_LIMIT_DEFAULT 23e0c1b49fSNick Terrell 24e0c1b49fSNick Terrell void ZSTD_ldm_fillHashTable( 25e0c1b49fSNick Terrell ldmState_t* state, const BYTE* ip, 26e0c1b49fSNick Terrell const BYTE* iend, ldmParams_t const* params); 27e0c1b49fSNick Terrell 28e0c1b49fSNick Terrell /* 29e0c1b49fSNick Terrell * ZSTD_ldm_generateSequences(): 30e0c1b49fSNick Terrell * 31e0c1b49fSNick Terrell * Generates the sequences using the long distance match finder. 32e0c1b49fSNick Terrell * Generates long range matching sequences in `sequences`, which parse a prefix 33e0c1b49fSNick Terrell * of the source. `sequences` must be large enough to store every sequence, 34e0c1b49fSNick Terrell * which can be checked with `ZSTD_ldm_getMaxNbSeq()`. 35e0c1b49fSNick Terrell * @returns 0 or an error code. 36e0c1b49fSNick Terrell * 37e0c1b49fSNick Terrell * NOTE: The user must have called ZSTD_window_update() for all of the input 38e0c1b49fSNick Terrell * they have, even if they pass it to ZSTD_ldm_generateSequences() in chunks. 39e0c1b49fSNick Terrell * NOTE: This function returns an error if it runs out of space to store 40e0c1b49fSNick Terrell * sequences. 41e0c1b49fSNick Terrell */ 42e0c1b49fSNick Terrell size_t ZSTD_ldm_generateSequences( 43e0c1b49fSNick Terrell ldmState_t* ldms, rawSeqStore_t* sequences, 44e0c1b49fSNick Terrell ldmParams_t const* params, void const* src, size_t srcSize); 45e0c1b49fSNick Terrell 46e0c1b49fSNick Terrell /* 47e0c1b49fSNick Terrell * ZSTD_ldm_blockCompress(): 48e0c1b49fSNick Terrell * 49e0c1b49fSNick Terrell * Compresses a block using the predefined sequences, along with a secondary 50e0c1b49fSNick Terrell * block compressor. The literals section of every sequence is passed to the 51e0c1b49fSNick Terrell * secondary block compressor, and those sequences are interspersed with the 52e0c1b49fSNick Terrell * predefined sequences. Returns the length of the last literals. 53e0c1b49fSNick Terrell * Updates `rawSeqStore.pos` to indicate how many sequences have been consumed. 54e0c1b49fSNick Terrell * `rawSeqStore.seq` may also be updated to split the last sequence between two 55e0c1b49fSNick Terrell * blocks. 56e0c1b49fSNick Terrell * @return The length of the last literals. 57e0c1b49fSNick Terrell * 58e0c1b49fSNick Terrell * NOTE: The source must be at most the maximum block size, but the predefined 59e0c1b49fSNick Terrell * sequences can be any size, and may be longer than the block. In the case that 60e0c1b49fSNick Terrell * they are longer than the block, the last sequences may need to be split into 61e0c1b49fSNick Terrell * two. We handle that case correctly, and update `rawSeqStore` appropriately. 62e0c1b49fSNick Terrell * NOTE: This function does not return any errors. 63e0c1b49fSNick Terrell */ 64e0c1b49fSNick Terrell size_t ZSTD_ldm_blockCompress(rawSeqStore_t* rawSeqStore, 65e0c1b49fSNick Terrell ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 66*2aa14b1aSNick Terrell ZSTD_paramSwitch_e useRowMatchFinder, 67e0c1b49fSNick Terrell void const* src, size_t srcSize); 68e0c1b49fSNick Terrell 69e0c1b49fSNick Terrell /* 70e0c1b49fSNick Terrell * ZSTD_ldm_skipSequences(): 71e0c1b49fSNick Terrell * 72e0c1b49fSNick Terrell * Skip past `srcSize` bytes worth of sequences in `rawSeqStore`. 73e0c1b49fSNick Terrell * Avoids emitting matches less than `minMatch` bytes. 74e0c1b49fSNick Terrell * Must be called for data that is not passed to ZSTD_ldm_blockCompress(). 75e0c1b49fSNick Terrell */ 76e0c1b49fSNick Terrell void ZSTD_ldm_skipSequences(rawSeqStore_t* rawSeqStore, size_t srcSize, 77e0c1b49fSNick Terrell U32 const minMatch); 78e0c1b49fSNick Terrell 79e0c1b49fSNick Terrell /* ZSTD_ldm_skipRawSeqStoreBytes(): 80e0c1b49fSNick Terrell * Moves forward in rawSeqStore by nbBytes, updating fields 'pos' and 'posInSequence'. 81e0c1b49fSNick Terrell * Not to be used in conjunction with ZSTD_ldm_skipSequences(). 82e0c1b49fSNick Terrell * Must be called for data with is not passed to ZSTD_ldm_blockCompress(). 83e0c1b49fSNick Terrell */ 84e0c1b49fSNick Terrell void ZSTD_ldm_skipRawSeqStoreBytes(rawSeqStore_t* rawSeqStore, size_t nbBytes); 85e0c1b49fSNick Terrell 86e0c1b49fSNick Terrell /* ZSTD_ldm_getTableSize() : 87e0c1b49fSNick Terrell * Estimate the space needed for long distance matching tables or 0 if LDM is 88e0c1b49fSNick Terrell * disabled. 89e0c1b49fSNick Terrell */ 90e0c1b49fSNick Terrell size_t ZSTD_ldm_getTableSize(ldmParams_t params); 91e0c1b49fSNick Terrell 92e0c1b49fSNick Terrell /* ZSTD_ldm_getSeqSpace() : 93e0c1b49fSNick Terrell * Return an upper bound on the number of sequences that can be produced by 94e0c1b49fSNick Terrell * the long distance matcher, or 0 if LDM is disabled. 95e0c1b49fSNick Terrell */ 96e0c1b49fSNick Terrell size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize); 97e0c1b49fSNick Terrell 98e0c1b49fSNick Terrell /* ZSTD_ldm_adjustParameters() : 99e0c1b49fSNick Terrell * If the params->hashRateLog is not set, set it to its default value based on 100e0c1b49fSNick Terrell * windowLog and params->hashLog. 101e0c1b49fSNick Terrell * 102e0c1b49fSNick Terrell * Ensures that params->bucketSizeLog is <= params->hashLog (setting it to 103e0c1b49fSNick Terrell * params->hashLog if it is not). 104e0c1b49fSNick Terrell * 105e0c1b49fSNick Terrell * Ensures that the minMatchLength >= targetLength during optimal parsing. 106e0c1b49fSNick Terrell */ 107e0c1b49fSNick Terrell void ZSTD_ldm_adjustParameters(ldmParams_t* params, 108e0c1b49fSNick Terrell ZSTD_compressionParameters const* cParams); 109e0c1b49fSNick Terrell 110e0c1b49fSNick Terrell 111e0c1b49fSNick Terrell #endif /* ZSTD_FAST_H */ 112