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