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