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