1/*
2 * Copyright (c) 2016-2020, 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/* This header contains definitions
12 * that shall **only** be used by modules within lib/compress.
13 */
14
15#ifndef ZSTD_COMPRESS_H
16#define ZSTD_COMPRESS_H
17
18/*-*************************************
19*  Dependencies
20***************************************/
21#include "../common/zstd_internal.h"
22#include "zstd_cwksp.h"
23#ifdef ZSTD_MULTITHREAD
24#  include "zstdmt_compress.h"
25#endif
26
27#if defined (__cplusplus)
28extern "C" {
29#endif
30
31
32/*-*************************************
33*  Constants
34***************************************/
35#define kSearchStrength      8
36#define HASH_READ_SIZE       8
37#define ZSTD_DUBT_UNSORTED_MARK 1   /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted".
38                                       It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
39                                       It's not a big deal though : candidate will just be sorted again.
40                                       Additionally, candidate position 1 will be lost.
41                                       But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
42                                       The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy.
43                                       This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */
44
45
46/*-*************************************
47*  Context memory management
48***************************************/
49typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
50typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
51
52typedef struct ZSTD_prefixDict_s {
53    const void* dict;
54    size_t dictSize;
55    ZSTD_dictContentType_e dictContentType;
56} ZSTD_prefixDict;
57
58typedef struct {
59    void* dictBuffer;
60    void const* dict;
61    size_t dictSize;
62    ZSTD_dictContentType_e dictContentType;
63    ZSTD_CDict* cdict;
64} ZSTD_localDict;
65
66typedef struct {
67    U32 CTable[HUF_CTABLE_SIZE_U32(255)];
68    HUF_repeat repeatMode;
69} ZSTD_hufCTables_t;
70
71typedef struct {
72    FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
73    FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
74    FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
75    FSE_repeat offcode_repeatMode;
76    FSE_repeat matchlength_repeatMode;
77    FSE_repeat litlength_repeatMode;
78} ZSTD_fseCTables_t;
79
80typedef struct {
81    ZSTD_hufCTables_t huf;
82    ZSTD_fseCTables_t fse;
83} ZSTD_entropyCTables_t;
84
85typedef struct {
86    U32 off;
87    U32 len;
88} ZSTD_match_t;
89
90typedef struct {
91    int price;
92    U32 off;
93    U32 mlen;
94    U32 litlen;
95    U32 rep[ZSTD_REP_NUM];
96} ZSTD_optimal_t;
97
98typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;
99
100typedef struct {
101    /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
102    unsigned* litFreq;           /* table of literals statistics, of size 256 */
103    unsigned* litLengthFreq;     /* table of litLength statistics, of size (MaxLL+1) */
104    unsigned* matchLengthFreq;   /* table of matchLength statistics, of size (MaxML+1) */
105    unsigned* offCodeFreq;       /* table of offCode statistics, of size (MaxOff+1) */
106    ZSTD_match_t* matchTable;    /* list of found matches, of size ZSTD_OPT_NUM+1 */
107    ZSTD_optimal_t* priceTable;  /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
108
109    U32  litSum;                 /* nb of literals */
110    U32  litLengthSum;           /* nb of litLength codes */
111    U32  matchLengthSum;         /* nb of matchLength codes */
112    U32  offCodeSum;             /* nb of offset codes */
113    U32  litSumBasePrice;        /* to compare to log2(litfreq) */
114    U32  litLengthSumBasePrice;  /* to compare to log2(llfreq)  */
115    U32  matchLengthSumBasePrice;/* to compare to log2(mlfreq)  */
116    U32  offCodeSumBasePrice;    /* to compare to log2(offreq)  */
117    ZSTD_OptPrice_e priceType;   /* prices can be determined dynamically, or follow a pre-defined cost structure */
118    const ZSTD_entropyCTables_t* symbolCosts;  /* pre-calculated dictionary statistics */
119    ZSTD_literalCompressionMode_e literalCompressionMode;
120} optState_t;
121
122typedef struct {
123  ZSTD_entropyCTables_t entropy;
124  U32 rep[ZSTD_REP_NUM];
125} ZSTD_compressedBlockState_t;
126
127typedef struct {
128    BYTE const* nextSrc;    /* next block here to continue on current prefix */
129    BYTE const* base;       /* All regular indexes relative to this position */
130    BYTE const* dictBase;   /* extDict indexes relative to this position */
131    U32 dictLimit;          /* below that point, need extDict */
132    U32 lowLimit;           /* below that point, no more valid data */
133} ZSTD_window_t;
134
135typedef struct ZSTD_matchState_t ZSTD_matchState_t;
136struct ZSTD_matchState_t {
137    ZSTD_window_t window;   /* State for window round buffer management */
138    U32 loadedDictEnd;      /* index of end of dictionary, within context's referential.
139                             * When loadedDictEnd != 0, a dictionary is in use, and still valid.
140                             * This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance.
141                             * Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity().
142                             * When dict referential is copied into active context (i.e. not attached),
143                             * loadedDictEnd == dictSize, since referential starts from zero.
144                             */
145    U32 nextToUpdate;       /* index from which to continue table update */
146    U32 hashLog3;           /* dispatch table for matches of len==3 : larger == faster, more memory */
147    U32* hashTable;
148    U32* hashTable3;
149    U32* chainTable;
150    optState_t opt;         /* optimal parser state */
151    const ZSTD_matchState_t* dictMatchState;
152    ZSTD_compressionParameters cParams;
153};
154
155typedef struct {
156    ZSTD_compressedBlockState_t* prevCBlock;
157    ZSTD_compressedBlockState_t* nextCBlock;
158    ZSTD_matchState_t matchState;
159} ZSTD_blockState_t;
160
161typedef struct {
162    U32 offset;
163    U32 checksum;
164} ldmEntry_t;
165
166typedef struct {
167    ZSTD_window_t window;   /* State for the window round buffer management */
168    ldmEntry_t* hashTable;
169    U32 loadedDictEnd;
170    BYTE* bucketOffsets;    /* Next position in bucket to insert entry */
171    U64 hashPower;          /* Used to compute the rolling hash.
172                             * Depends on ldmParams.minMatchLength */
173} ldmState_t;
174
175typedef struct {
176    U32 enableLdm;          /* 1 if enable long distance matching */
177    U32 hashLog;            /* Log size of hashTable */
178    U32 bucketSizeLog;      /* Log bucket size for collision resolution, at most 8 */
179    U32 minMatchLength;     /* Minimum match length */
180    U32 hashRateLog;       /* Log number of entries to skip */
181    U32 windowLog;          /* Window log for the LDM */
182} ldmParams_t;
183
184typedef struct {
185    U32 offset;
186    U32 litLength;
187    U32 matchLength;
188} rawSeq;
189
190typedef struct {
191  rawSeq* seq;     /* The start of the sequences */
192  size_t pos;      /* The position where reading stopped. <= size. */
193  size_t size;     /* The number of sequences. <= capacity. */
194  size_t capacity; /* The capacity starting from `seq` pointer */
195} rawSeqStore_t;
196
197typedef struct {
198    int collectSequences;
199    ZSTD_Sequence* seqStart;
200    size_t seqIndex;
201    size_t maxSequences;
202} SeqCollector;
203
204struct ZSTD_CCtx_params_s {
205    ZSTD_format_e format;
206    ZSTD_compressionParameters cParams;
207    ZSTD_frameParameters fParams;
208
209    int compressionLevel;
210    int forceWindow;           /* force back-references to respect limit of
211                                * 1<<wLog, even for dictionary */
212    size_t targetCBlockSize;   /* Tries to fit compressed block size to be around targetCBlockSize.
213                                * No target when targetCBlockSize == 0.
214                                * There is no guarantee on compressed block size */
215    int srcSizeHint;           /* User's best guess of source size.
216                                * Hint is not valid when srcSizeHint == 0.
217                                * There is no guarantee that hint is close to actual source size */
218
219    ZSTD_dictAttachPref_e attachDictPref;
220    ZSTD_literalCompressionMode_e literalCompressionMode;
221
222    /* Multithreading: used to pass parameters to mtctx */
223    int nbWorkers;
224    size_t jobSize;
225    int overlapLog;
226    int rsyncable;
227
228    /* Long distance matching parameters */
229    ldmParams_t ldmParams;
230
231    /* Internal use, for createCCtxParams() and freeCCtxParams() only */
232    ZSTD_customMem customMem;
233};  /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
234
235struct ZSTD_CCtx_s {
236    ZSTD_compressionStage_e stage;
237    int cParamsChanged;                  /* == 1 if cParams(except wlog) or compression level are changed in requestedParams. Triggers transmission of new params to ZSTDMT (if available) then reset to 0. */
238    int bmi2;                            /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
239    ZSTD_CCtx_params requestedParams;
240    ZSTD_CCtx_params appliedParams;
241    U32   dictID;
242
243    ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */
244    size_t blockSize;
245    unsigned long long pledgedSrcSizePlusOne;  /* this way, 0 (default) == unknown */
246    unsigned long long consumedSrcSize;
247    unsigned long long producedCSize;
248    XXH64_state_t xxhState;
249    ZSTD_customMem customMem;
250    size_t staticSize;
251    SeqCollector seqCollector;
252    int isFirstBlock;
253    int initialized;
254
255    seqStore_t seqStore;      /* sequences storage ptrs */
256    ldmState_t ldmState;      /* long distance matching state */
257    rawSeq* ldmSequences;     /* Storage for the ldm output sequences */
258    size_t maxNbLdmSequences;
259    rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
260    ZSTD_blockState_t blockState;
261    U32* entropyWorkspace;  /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
262
263    /* streaming */
264    char*  inBuff;
265    size_t inBuffSize;
266    size_t inToCompress;
267    size_t inBuffPos;
268    size_t inBuffTarget;
269    char*  outBuff;
270    size_t outBuffSize;
271    size_t outBuffContentSize;
272    size_t outBuffFlushedSize;
273    ZSTD_cStreamStage streamStage;
274    U32    frameEnded;
275
276    /* Dictionary */
277    ZSTD_localDict localDict;
278    const ZSTD_CDict* cdict;
279    ZSTD_prefixDict prefixDict;   /* single-usage dictionary */
280
281    /* Multi-threading */
282#ifdef ZSTD_MULTITHREAD
283    ZSTDMT_CCtx* mtctx;
284#endif
285};
286
287typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e;
288
289typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
290
291
292typedef size_t (*ZSTD_blockCompressor) (
293        ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
294        void const* src, size_t srcSize);
295ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode);
296
297
298MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
299{
300    static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,
301                                       8,  9, 10, 11, 12, 13, 14, 15,
302                                      16, 16, 17, 17, 18, 18, 19, 19,
303                                      20, 20, 20, 20, 21, 21, 21, 21,
304                                      22, 22, 22, 22, 22, 22, 22, 22,
305                                      23, 23, 23, 23, 23, 23, 23, 23,
306                                      24, 24, 24, 24, 24, 24, 24, 24,
307                                      24, 24, 24, 24, 24, 24, 24, 24 };
308    static const U32 LL_deltaCode = 19;
309    return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
310}
311
312/* ZSTD_MLcode() :
313 * note : mlBase = matchLength - MINMATCH;
314 *        because it's the format it's stored in seqStore->sequences */
315MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
316{
317    static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
318                                      16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
319                                      32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
320                                      38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
321                                      40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
322                                      41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
323                                      42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
324                                      42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
325    static const U32 ML_deltaCode = 36;
326    return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
327}
328
329typedef struct repcodes_s {
330    U32 rep[3];
331} repcodes_t;
332
333MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
334{
335    repcodes_t newReps;
336    if (offset >= ZSTD_REP_NUM) {  /* full offset */
337        newReps.rep[2] = rep[1];
338        newReps.rep[1] = rep[0];
339        newReps.rep[0] = offset - ZSTD_REP_MOVE;
340    } else {   /* repcode */
341        U32 const repCode = offset + ll0;
342        if (repCode > 0) {  /* note : if repCode==0, no change */
343            U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
344            newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2];
345            newReps.rep[1] = rep[0];
346            newReps.rep[0] = currentOffset;
347        } else {   /* repCode == 0 */
348            memcpy(&newReps, rep, sizeof(newReps));
349        }
350    }
351    return newReps;
352}
353
354/* ZSTD_cParam_withinBounds:
355 * @return 1 if value is within cParam bounds,
356 * 0 otherwise */
357MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value)
358{
359    ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam);
360    if (ZSTD_isError(bounds.error)) return 0;
361    if (value < bounds.lowerBound) return 0;
362    if (value > bounds.upperBound) return 0;
363    return 1;
364}
365
366/* ZSTD_noCompressBlock() :
367 * Writes uncompressed block to dst buffer from given src.
368 * Returns the size of the block */
369MEM_STATIC size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock)
370{
371    U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);
372    RETURN_ERROR_IF(srcSize + ZSTD_blockHeaderSize > dstCapacity,
373                    dstSize_tooSmall, "dst buf too small for uncompressed block");
374    MEM_writeLE24(dst, cBlockHeader24);
375    memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
376    return ZSTD_blockHeaderSize + srcSize;
377}
378
379MEM_STATIC size_t ZSTD_rleCompressBlock (void* dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
380{
381    BYTE* const op = (BYTE*)dst;
382    U32 const cBlockHeader = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3);
383    RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, "");
384    MEM_writeLE24(op, cBlockHeader);
385    op[3] = src;
386    return 4;
387}
388
389
390/* ZSTD_minGain() :
391 * minimum compression required
392 * to generate a compress block or a compressed literals section.
393 * note : use same formula for both situations */
394MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
395{
396    U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6;
397    ZSTD_STATIC_ASSERT(ZSTD_btultra == 8);
398    assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat));
399    return (srcSize >> minlog) + 2;
400}
401
402MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams)
403{
404    switch (cctxParams->literalCompressionMode) {
405    case ZSTD_lcm_huffman:
406        return 0;
407    case ZSTD_lcm_uncompressed:
408        return 1;
409    default:
410        assert(0 /* impossible: pre-validated */);
411        /* fall-through */
412    case ZSTD_lcm_auto:
413        return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0);
414    }
415}
416
417/*! ZSTD_safecopyLiterals() :
418 *  memcpy() function that won't read beyond more than WILDCOPY_OVERLENGTH bytes past ilimit_w.
419 *  Only called when the sequence ends past ilimit_w, so it only needs to be optimized for single
420 *  large copies.
421 */
422static void ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) {
423    assert(iend > ilimit_w);
424    if (ip <= ilimit_w) {
425        ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap);
426        op += ilimit_w - ip;
427        ip = ilimit_w;
428    }
429    while (ip < iend) *op++ = *ip++;
430}
431
432/*! ZSTD_storeSeq() :
433 *  Store a sequence (litlen, litPtr, offCode and mlBase) into seqStore_t.
434 *  `offCode` : distance to match + ZSTD_REP_MOVE (values <= ZSTD_REP_MOVE are repCodes).
435 *  `mlBase` : matchLength - MINMATCH
436 *  Allowed to overread literals up to litLimit.
437*/
438HINT_INLINE UNUSED_ATTR
439void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase)
440{
441    BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH;
442    BYTE const* const litEnd = literals + litLength;
443#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
444    static const BYTE* g_start = NULL;
445    if (g_start==NULL) g_start = (const BYTE*)literals;  /* note : index only works for compression within a single segment */
446    {   U32 const pos = (U32)((const BYTE*)literals - g_start);
447        DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
448               pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode);
449    }
450#endif
451    assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
452    /* copy Literals */
453    assert(seqStorePtr->maxNbLit <= 128 KB);
454    assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
455    assert(literals + litLength <= litLimit);
456    if (litEnd <= litLimit_w) {
457        /* Common case we can use wildcopy.
458	 * First copy 16 bytes, because literals are likely short.
459	 */
460        assert(WILDCOPY_OVERLENGTH >= 16);
461        ZSTD_copy16(seqStorePtr->lit, literals);
462        if (litLength > 16) {
463            ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap);
464        }
465    } else {
466        ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w);
467    }
468    seqStorePtr->lit += litLength;
469
470    /* literal Length */
471    if (litLength>0xFFFF) {
472        assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
473        seqStorePtr->longLengthID = 1;
474        seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
475    }
476    seqStorePtr->sequences[0].litLength = (U16)litLength;
477
478    /* match offset */
479    seqStorePtr->sequences[0].offset = offCode + 1;
480
481    /* match Length */
482    if (mlBase>0xFFFF) {
483        assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
484        seqStorePtr->longLengthID = 2;
485        seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
486    }
487    seqStorePtr->sequences[0].matchLength = (U16)mlBase;
488
489    seqStorePtr->sequences++;
490}
491
492
493/*-*************************************
494*  Match length counter
495***************************************/
496static unsigned ZSTD_NbCommonBytes (size_t val)
497{
498    if (MEM_isLittleEndian()) {
499        if (MEM_64bits()) {
500#       if defined(_MSC_VER) && defined(_WIN64)
501            unsigned long r = 0;
502            return _BitScanForward64( &r, (U64)val ) ? (unsigned)(r >> 3) : 0;
503#       elif defined(__GNUC__) && (__GNUC__ >= 4)
504            return (__builtin_ctzll((U64)val) >> 3);
505#       else
506            static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
507                                                     0, 3, 1, 3, 1, 4, 2, 7,
508                                                     0, 2, 3, 6, 1, 5, 3, 5,
509                                                     1, 3, 4, 4, 2, 5, 6, 7,
510                                                     7, 0, 1, 2, 3, 3, 4, 6,
511                                                     2, 6, 5, 5, 3, 4, 5, 6,
512                                                     7, 1, 2, 4, 6, 4, 4, 5,
513                                                     7, 2, 6, 5, 7, 6, 7, 7 };
514            return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
515#       endif
516        } else { /* 32 bits */
517#       if defined(_MSC_VER)
518            unsigned long r=0;
519            return _BitScanForward( &r, (U32)val ) ? (unsigned)(r >> 3) : 0;
520#       elif defined(__GNUC__) && (__GNUC__ >= 3)
521            return (__builtin_ctz((U32)val) >> 3);
522#       else
523            static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
524                                                     3, 2, 2, 1, 3, 2, 0, 1,
525                                                     3, 3, 1, 2, 2, 2, 2, 0,
526                                                     3, 1, 2, 0, 1, 0, 1, 1 };
527            return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
528#       endif
529        }
530    } else {  /* Big Endian CPU */
531        if (MEM_64bits()) {
532#       if defined(_MSC_VER) && defined(_WIN64)
533            unsigned long r = 0;
534            return _BitScanReverse64( &r, val ) ? (unsigned)(r >> 3) : 0;
535#       elif defined(__GNUC__) && (__GNUC__ >= 4)
536            return (__builtin_clzll(val) >> 3);
537#       else
538            unsigned r;
539            const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
540            if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
541            if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
542            r += (!val);
543            return r;
544#       endif
545        } else { /* 32 bits */
546#       if defined(_MSC_VER)
547            unsigned long r = 0;
548            return _BitScanReverse( &r, (unsigned long)val ) ? (unsigned)(r >> 3) : 0;
549#       elif defined(__GNUC__) && (__GNUC__ >= 3)
550            return (__builtin_clz((U32)val) >> 3);
551#       else
552            unsigned r;
553            if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
554            r += (!val);
555            return r;
556#       endif
557    }   }
558}
559
560
561MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
562{
563    const BYTE* const pStart = pIn;
564    const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
565
566    if (pIn < pInLoopLimit) {
567        { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
568          if (diff) return ZSTD_NbCommonBytes(diff); }
569        pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
570        while (pIn < pInLoopLimit) {
571            size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
572            if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
573            pIn += ZSTD_NbCommonBytes(diff);
574            return (size_t)(pIn - pStart);
575    }   }
576    if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
577    if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
578    if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
579    return (size_t)(pIn - pStart);
580}
581
582/** ZSTD_count_2segments() :
583 *  can count match length with `ip` & `match` in 2 different segments.
584 *  convention : on reaching mEnd, match count continue starting from iStart
585 */
586MEM_STATIC size_t
587ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
588                     const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
589{
590    const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
591    size_t const matchLength = ZSTD_count(ip, match, vEnd);
592    if (match + matchLength != mEnd) return matchLength;
593    DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
594    DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
595    DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
596    DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
597    DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
598    return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
599}
600
601
602/*-*************************************
603 *  Hashes
604 ***************************************/
605static const U32 prime3bytes = 506832829U;
606static U32    ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }
607MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
608
609static const U32 prime4bytes = 2654435761U;
610static U32    ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
611static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
612
613static const U64 prime5bytes = 889523592379ULL;
614static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }
615static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
616
617static const U64 prime6bytes = 227718039650203ULL;
618static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }
619static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
620
621static const U64 prime7bytes = 58295818150454627ULL;
622static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }
623static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
624
625static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
626static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
627static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
628
629MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
630{
631    switch(mls)
632    {
633    default:
634    case 4: return ZSTD_hash4Ptr(p, hBits);
635    case 5: return ZSTD_hash5Ptr(p, hBits);
636    case 6: return ZSTD_hash6Ptr(p, hBits);
637    case 7: return ZSTD_hash7Ptr(p, hBits);
638    case 8: return ZSTD_hash8Ptr(p, hBits);
639    }
640}
641
642/** ZSTD_ipow() :
643 * Return base^exponent.
644 */
645static U64 ZSTD_ipow(U64 base, U64 exponent)
646{
647    U64 power = 1;
648    while (exponent) {
649      if (exponent & 1) power *= base;
650      exponent >>= 1;
651      base *= base;
652    }
653    return power;
654}
655
656#define ZSTD_ROLL_HASH_CHAR_OFFSET 10
657
658/** ZSTD_rollingHash_append() :
659 * Add the buffer to the hash value.
660 */
661static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size)
662{
663    BYTE const* istart = (BYTE const*)buf;
664    size_t pos;
665    for (pos = 0; pos < size; ++pos) {
666        hash *= prime8bytes;
667        hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET;
668    }
669    return hash;
670}
671
672/** ZSTD_rollingHash_compute() :
673 * Compute the rolling hash value of the buffer.
674 */
675MEM_STATIC U64 ZSTD_rollingHash_compute(void const* buf, size_t size)
676{
677    return ZSTD_rollingHash_append(0, buf, size);
678}
679
680/** ZSTD_rollingHash_primePower() :
681 * Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash
682 * over a window of length bytes.
683 */
684MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
685{
686    return ZSTD_ipow(prime8bytes, length - 1);
687}
688
689/** ZSTD_rollingHash_rotate() :
690 * Rotate the rolling hash by one byte.
691 */
692MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
693{
694    hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
695    hash *= prime8bytes;
696    hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET;
697    return hash;
698}
699
700/*-*************************************
701*  Round buffer management
702***************************************/
703#if (ZSTD_WINDOWLOG_MAX_64 > 31)
704# error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX"
705#endif
706/* Max current allowed */
707#define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
708/* Maximum chunk size before overflow correction needs to be called again */
709#define ZSTD_CHUNKSIZE_MAX                                                     \
710    ( ((U32)-1)                  /* Maximum ending current index */            \
711    - ZSTD_CURRENT_MAX)          /* Maximum beginning lowLimit */
712
713/**
714 * ZSTD_window_clear():
715 * Clears the window containing the history by simply setting it to empty.
716 */
717MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window)
718{
719    size_t const endT = (size_t)(window->nextSrc - window->base);
720    U32 const end = (U32)endT;
721
722    window->lowLimit = end;
723    window->dictLimit = end;
724}
725
726/**
727 * ZSTD_window_hasExtDict():
728 * Returns non-zero if the window has a non-empty extDict.
729 */
730MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
731{
732    return window.lowLimit < window.dictLimit;
733}
734
735/**
736 * ZSTD_matchState_dictMode():
737 * Inspects the provided matchState and figures out what dictMode should be
738 * passed to the compressor.
739 */
740MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
741{
742    return ZSTD_window_hasExtDict(ms->window) ?
743        ZSTD_extDict :
744        ms->dictMatchState != NULL ?
745            ZSTD_dictMatchState :
746            ZSTD_noDict;
747}
748
749/**
750 * ZSTD_window_needOverflowCorrection():
751 * Returns non-zero if the indices are getting too large and need overflow
752 * protection.
753 */
754MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window,
755                                                  void const* srcEnd)
756{
757    U32 const current = (U32)((BYTE const*)srcEnd - window.base);
758    return current > ZSTD_CURRENT_MAX;
759}
760
761/**
762 * ZSTD_window_correctOverflow():
763 * Reduces the indices to protect from index overflow.
764 * Returns the correction made to the indices, which must be applied to every
765 * stored index.
766 *
767 * The least significant cycleLog bits of the indices must remain the same,
768 * which may be 0. Every index up to maxDist in the past must be valid.
769 * NOTE: (maxDist & cycleMask) must be zero.
770 */
771MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
772                                           U32 maxDist, void const* src)
773{
774    /* preemptive overflow correction:
775     * 1. correction is large enough:
776     *    lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
777     *    1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
778     *
779     *    current - newCurrent
780     *    > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
781     *    > (3<<29) - (1<<chainLog)
782     *    > (3<<29) - (1<<30)             (NOTE: chainLog <= 30)
783     *    > 1<<29
784     *
785     * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
786     *    After correction, current is less than (1<<chainLog + 1<<windowLog).
787     *    In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
788     *    In 32-bit mode we are safe, because (chainLog <= 29), so
789     *    ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
790     * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
791     *    windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
792     */
793    U32 const cycleMask = (1U << cycleLog) - 1;
794    U32 const current = (U32)((BYTE const*)src - window->base);
795    U32 const currentCycle0 = current & cycleMask;
796    /* Exclude zero so that newCurrent - maxDist >= 1. */
797    U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0;
798    U32 const newCurrent = currentCycle1 + maxDist;
799    U32 const correction = current - newCurrent;
800    assert((maxDist & cycleMask) == 0);
801    assert(current > newCurrent);
802    /* Loose bound, should be around 1<<29 (see above) */
803    assert(correction > 1<<28);
804
805    window->base += correction;
806    window->dictBase += correction;
807    if (window->lowLimit <= correction) window->lowLimit = 1;
808    else window->lowLimit -= correction;
809    if (window->dictLimit <= correction) window->dictLimit = 1;
810    else window->dictLimit -= correction;
811
812    /* Ensure we can still reference the full window. */
813    assert(newCurrent >= maxDist);
814    assert(newCurrent - maxDist >= 1);
815    /* Ensure that lowLimit and dictLimit didn't underflow. */
816    assert(window->lowLimit <= newCurrent);
817    assert(window->dictLimit <= newCurrent);
818
819    DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
820             window->lowLimit);
821    return correction;
822}
823
824/**
825 * ZSTD_window_enforceMaxDist():
826 * Updates lowLimit so that:
827 *    (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
828 *
829 * It ensures index is valid as long as index >= lowLimit.
830 * This must be called before a block compression call.
831 *
832 * loadedDictEnd is only defined if a dictionary is in use for current compression.
833 * As the name implies, loadedDictEnd represents the index at end of dictionary.
834 * The value lies within context's referential, it can be directly compared to blockEndIdx.
835 *
836 * If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0.
837 * If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit.
838 * This is because dictionaries are allowed to be referenced fully
839 * as long as the last byte of the dictionary is in the window.
840 * Once input has progressed beyond window size, dictionary cannot be referenced anymore.
841 *
842 * In normal dict mode, the dictionary lies between lowLimit and dictLimit.
843 * In dictMatchState mode, lowLimit and dictLimit are the same,
844 * and the dictionary is below them.
845 * forceWindow and dictMatchState are therefore incompatible.
846 */
847MEM_STATIC void
848ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
849                     const void* blockEnd,
850                           U32   maxDist,
851                           U32*  loadedDictEndPtr,
852                     const ZSTD_matchState_t** dictMatchStatePtr)
853{
854    U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
855    U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
856    DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
857                (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
858
859    /* - When there is no dictionary : loadedDictEnd == 0.
860         In which case, the test (blockEndIdx > maxDist) is merely to avoid
861         overflowing next operation `newLowLimit = blockEndIdx - maxDist`.
862       - When there is a standard dictionary :
863         Index referential is copied from the dictionary,
864         which means it starts from 0.
865         In which case, loadedDictEnd == dictSize,
866         and it makes sense to compare `blockEndIdx > maxDist + dictSize`
867         since `blockEndIdx` also starts from zero.
868       - When there is an attached dictionary :
869         loadedDictEnd is expressed within the referential of the context,
870         so it can be directly compared against blockEndIdx.
871    */
872    if (blockEndIdx > maxDist + loadedDictEnd) {
873        U32 const newLowLimit = blockEndIdx - maxDist;
874        if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
875        if (window->dictLimit < window->lowLimit) {
876            DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
877                        (unsigned)window->dictLimit, (unsigned)window->lowLimit);
878            window->dictLimit = window->lowLimit;
879        }
880        /* On reaching window size, dictionaries are invalidated */
881        if (loadedDictEndPtr) *loadedDictEndPtr = 0;
882        if (dictMatchStatePtr) *dictMatchStatePtr = NULL;
883    }
884}
885
886/* Similar to ZSTD_window_enforceMaxDist(),
887 * but only invalidates dictionary
888 * when input progresses beyond window size.
889 * assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL)
890 *              loadedDictEnd uses same referential as window->base
891 *              maxDist is the window size */
892MEM_STATIC void
893ZSTD_checkDictValidity(const ZSTD_window_t* window,
894                       const void* blockEnd,
895                             U32   maxDist,
896                             U32*  loadedDictEndPtr,
897                       const ZSTD_matchState_t** dictMatchStatePtr)
898{
899    assert(loadedDictEndPtr != NULL);
900    assert(dictMatchStatePtr != NULL);
901    {   U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
902        U32 const loadedDictEnd = *loadedDictEndPtr;
903        DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
904                    (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
905        assert(blockEndIdx >= loadedDictEnd);
906
907        if (blockEndIdx > loadedDictEnd + maxDist) {
908            /* On reaching window size, dictionaries are invalidated.
909             * For simplification, if window size is reached anywhere within next block,
910             * the dictionary is invalidated for the full block.
911             */
912            DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)");
913            *loadedDictEndPtr = 0;
914            *dictMatchStatePtr = NULL;
915        } else {
916            if (*loadedDictEndPtr != 0) {
917                DEBUGLOG(6, "dictionary considered valid for current block");
918    }   }   }
919}
920
921MEM_STATIC void ZSTD_window_init(ZSTD_window_t* window) {
922    memset(window, 0, sizeof(*window));
923    window->base = (BYTE const*)"";
924    window->dictBase = (BYTE const*)"";
925    window->dictLimit = 1;    /* start from 1, so that 1st position is valid */
926    window->lowLimit = 1;     /* it ensures first and later CCtx usages compress the same */
927    window->nextSrc = window->base + 1;   /* see issue #1241 */
928}
929
930/**
931 * ZSTD_window_update():
932 * Updates the window by appending [src, src + srcSize) to the window.
933 * If it is not contiguous, the current prefix becomes the extDict, and we
934 * forget about the extDict. Handles overlap of the prefix and extDict.
935 * Returns non-zero if the segment is contiguous.
936 */
937MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
938                                  void const* src, size_t srcSize)
939{
940    BYTE const* const ip = (BYTE const*)src;
941    U32 contiguous = 1;
942    DEBUGLOG(5, "ZSTD_window_update");
943    if (srcSize == 0)
944        return contiguous;
945    assert(window->base != NULL);
946    assert(window->dictBase != NULL);
947    /* Check if blocks follow each other */
948    if (src != window->nextSrc) {
949        /* not contiguous */
950        size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
951        DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
952        window->lowLimit = window->dictLimit;
953        assert(distanceFromBase == (size_t)(U32)distanceFromBase);  /* should never overflow */
954        window->dictLimit = (U32)distanceFromBase;
955        window->dictBase = window->base;
956        window->base = ip - distanceFromBase;
957        /* ms->nextToUpdate = window->dictLimit; */
958        if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit;   /* too small extDict */
959        contiguous = 0;
960    }
961    window->nextSrc = ip + srcSize;
962    /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
963    if ( (ip+srcSize > window->dictBase + window->lowLimit)
964       & (ip < window->dictBase + window->dictLimit)) {
965        ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
966        U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
967        window->lowLimit = lowLimitMax;
968        DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
969    }
970    return contiguous;
971}
972
973/**
974 * Returns the lowest allowed match index. It may either be in the ext-dict or the prefix.
975 */
976MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t* ms, U32 current, unsigned windowLog)
977{
978    U32    const maxDistance = 1U << windowLog;
979    U32    const lowestValid = ms->window.lowLimit;
980    U32    const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
981    U32    const isDictionary = (ms->loadedDictEnd != 0);
982    U32    const matchLowest = isDictionary ? lowestValid : withinWindow;
983    return matchLowest;
984}
985
986/**
987 * Returns the lowest allowed match index in the prefix.
988 */
989MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t* ms, U32 current, unsigned windowLog)
990{
991    U32    const maxDistance = 1U << windowLog;
992    U32    const lowestValid = ms->window.dictLimit;
993    U32    const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
994    U32    const isDictionary = (ms->loadedDictEnd != 0);
995    U32    const matchLowest = isDictionary ? lowestValid : withinWindow;
996    return matchLowest;
997}
998
999
1000
1001/* debug functions */
1002#if (DEBUGLEVEL>=2)
1003
1004MEM_STATIC double ZSTD_fWeight(U32 rawStat)
1005{
1006    U32 const fp_accuracy = 8;
1007    U32 const fp_multiplier = (1 << fp_accuracy);
1008    U32 const newStat = rawStat + 1;
1009    U32 const hb = ZSTD_highbit32(newStat);
1010    U32 const BWeight = hb * fp_multiplier;
1011    U32 const FWeight = (newStat << fp_accuracy) >> hb;
1012    U32 const weight = BWeight + FWeight;
1013    assert(hb + fp_accuracy < 31);
1014    return (double)weight / fp_multiplier;
1015}
1016
1017/* display a table content,
1018 * listing each element, its frequency, and its predicted bit cost */
1019MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
1020{
1021    unsigned u, sum;
1022    for (u=0, sum=0; u<=max; u++) sum += table[u];
1023    DEBUGLOG(2, "total nb elts: %u", sum);
1024    for (u=0; u<=max; u++) {
1025        DEBUGLOG(2, "%2u: %5u  (%.2f)",
1026                u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
1027    }
1028}
1029
1030#endif
1031
1032
1033#if defined (__cplusplus)
1034}
1035#endif
1036
1037/* ===============================================================
1038 * Shared internal declarations
1039 * These prototypes may be called from sources not in lib/compress
1040 * =============================================================== */
1041
1042/* ZSTD_loadCEntropy() :
1043 * dict : must point at beginning of a valid zstd dictionary.
1044 * return : size of dictionary header (size of magic number + dict ID + entropy tables)
1045 * assumptions : magic number supposed already checked
1046 *               and dictSize >= 8 */
1047size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t* bs, void* workspace,
1048                         short* offcodeNCount, unsigned* offcodeMaxValue,
1049                         const void* const dict, size_t dictSize);
1050
1051void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t* bs);
1052
1053/* ==============================================================
1054 * Private declarations
1055 * These prototypes shall only be called from within lib/compress
1056 * ============================================================== */
1057
1058/* ZSTD_getCParamsFromCCtxParams() :
1059 * cParams are built depending on compressionLevel, src size hints,
1060 * LDM and manually set compression parameters.
1061 * Note: srcSizeHint == 0 means 0!
1062 */
1063ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
1064        const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
1065
1066/*! ZSTD_initCStream_internal() :
1067 *  Private use only. Init streaming operation.
1068 *  expects params to be valid.
1069 *  must receive dict, or cdict, or none, but not both.
1070 *  @return : 0, or an error code */
1071size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
1072                     const void* dict, size_t dictSize,
1073                     const ZSTD_CDict* cdict,
1074                     const ZSTD_CCtx_params* params, unsigned long long pledgedSrcSize);
1075
1076void ZSTD_resetSeqStore(seqStore_t* ssPtr);
1077
1078/*! ZSTD_getCParamsFromCDict() :
1079 *  as the name implies */
1080ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
1081
1082/* ZSTD_compressBegin_advanced_internal() :
1083 * Private use only. To be called from zstdmt_compress.c. */
1084size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
1085                                    const void* dict, size_t dictSize,
1086                                    ZSTD_dictContentType_e dictContentType,
1087                                    ZSTD_dictTableLoadMethod_e dtlm,
1088                                    const ZSTD_CDict* cdict,
1089                                    const ZSTD_CCtx_params* params,
1090                                    unsigned long long pledgedSrcSize);
1091
1092/* ZSTD_compress_advanced_internal() :
1093 * Private use only. To be called from zstdmt_compress.c. */
1094size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
1095                                       void* dst, size_t dstCapacity,
1096                                 const void* src, size_t srcSize,
1097                                 const void* dict,size_t dictSize,
1098                                 const ZSTD_CCtx_params* params);
1099
1100
1101/* ZSTD_writeLastEmptyBlock() :
1102 * output an empty Block with end-of-frame mark to complete a frame
1103 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
1104 *           or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize)
1105 */
1106size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
1107
1108
1109/* ZSTD_referenceExternalSequences() :
1110 * Must be called before starting a compression operation.
1111 * seqs must parse a prefix of the source.
1112 * This cannot be used when long range matching is enabled.
1113 * Zstd will use these sequences, and pass the literals to a secondary block
1114 * compressor.
1115 * @return : An error code on failure.
1116 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
1117 * access and data corruption.
1118 */
1119size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
1120
1121/** ZSTD_cycleLog() :
1122 *  condition for correct operation : hashLog > 1 */
1123U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat);
1124
1125#endif /* ZSTD_COMPRESS_H */
1126