xref: /freebsd/sys/contrib/zstd/lib/common/zstd_internal.h (revision 5ff13fbc199bdf5f0572845351c68ee5ca828e71)
10c16b537SWarner Losh /*
2*5ff13fbcSAllan Jude  * Copyright (c) Yann Collet, Facebook, Inc.
30c16b537SWarner Losh  * All rights reserved.
40c16b537SWarner Losh  *
50c16b537SWarner Losh  * This source code is licensed under both the BSD-style license (found in the
60c16b537SWarner Losh  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
70c16b537SWarner Losh  * in the COPYING file in the root directory of this source tree).
80c16b537SWarner Losh  * You may select, at your option, one of the above-listed licenses.
90c16b537SWarner Losh  */
100c16b537SWarner Losh 
110c16b537SWarner Losh #ifndef ZSTD_CCOMMON_H_MODULE
120c16b537SWarner Losh #define ZSTD_CCOMMON_H_MODULE
130c16b537SWarner Losh 
14052d3c12SConrad Meyer /* this module contains definitions which must be identical
15052d3c12SConrad Meyer  * across compression, decompression and dictBuilder.
16052d3c12SConrad Meyer  * It also contains a few functions useful to at least 2 of them
17052d3c12SConrad Meyer  * and which benefit from being inlined */
180c16b537SWarner Losh 
190c16b537SWarner Losh /*-*************************************
200c16b537SWarner Losh *  Dependencies
210c16b537SWarner Losh ***************************************/
220c16b537SWarner Losh #include "compiler.h"
23*5ff13fbcSAllan Jude #include "cpu.h"
240c16b537SWarner Losh #include "mem.h"
250f743729SConrad Meyer #include "debug.h"                 /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
260c16b537SWarner Losh #include "error_private.h"
270c16b537SWarner Losh #define ZSTD_STATIC_LINKING_ONLY
2837f1f268SConrad Meyer #include "../zstd.h"
290c16b537SWarner Losh #define FSE_STATIC_LINKING_ONLY
300c16b537SWarner Losh #include "fse.h"
310c16b537SWarner Losh #define HUF_STATIC_LINKING_ONLY
320c16b537SWarner Losh #include "huf.h"
330c16b537SWarner Losh #ifndef XXH_STATIC_LINKING_ONLY
340c16b537SWarner Losh #  define XXH_STATIC_LINKING_ONLY  /* XXH64_state_t */
350c16b537SWarner Losh #endif
360c16b537SWarner Losh #include "xxhash.h"                /* XXH_reset, update, digest */
37*5ff13fbcSAllan Jude #ifndef ZSTD_NO_TRACE
38*5ff13fbcSAllan Jude #  include "zstd_trace.h"
39*5ff13fbcSAllan Jude #else
40*5ff13fbcSAllan Jude #  define ZSTD_TRACE 0
41*5ff13fbcSAllan Jude #endif
420c16b537SWarner Losh 
430c16b537SWarner Losh #if defined (__cplusplus)
440c16b537SWarner Losh extern "C" {
450c16b537SWarner Losh #endif
460c16b537SWarner Losh 
470f743729SConrad Meyer /* ---- static assert (debug) --- */
480f743729SConrad Meyer #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
49a0483764SConrad Meyer #define ZSTD_isError ERR_isError   /* for inlining */
50a0483764SConrad Meyer #define FSE_isError  ERR_isError
51a0483764SConrad Meyer #define HUF_isError  ERR_isError
520c16b537SWarner Losh 
530c16b537SWarner Losh 
540c16b537SWarner Losh /*-*************************************
550c16b537SWarner Losh *  shared macros
560c16b537SWarner Losh ***************************************/
570c16b537SWarner Losh #undef MIN
580c16b537SWarner Losh #undef MAX
590c16b537SWarner Losh #define MIN(a,b) ((a)<(b) ? (a) : (b))
600c16b537SWarner Losh #define MAX(a,b) ((a)>(b) ? (a) : (b))
61*5ff13fbcSAllan Jude #define BOUNDED(min,val,max) (MAX(min,MIN(val,max)))
620c16b537SWarner Losh 
630c16b537SWarner Losh 
640c16b537SWarner Losh /*-*************************************
650c16b537SWarner Losh *  Common constants
660c16b537SWarner Losh ***************************************/
670c16b537SWarner Losh #define ZSTD_OPT_NUM    (1<<12)
680c16b537SWarner Losh 
690c16b537SWarner Losh #define ZSTD_REP_NUM      3                 /* number of repcodes */
70f7cd7fe5SConrad Meyer static UNUSED_ATTR const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
710c16b537SWarner Losh 
720c16b537SWarner Losh #define KB *(1 <<10)
730c16b537SWarner Losh #define MB *(1 <<20)
740c16b537SWarner Losh #define GB *(1U<<30)
750c16b537SWarner Losh 
760c16b537SWarner Losh #define BIT7 128
770c16b537SWarner Losh #define BIT6  64
780c16b537SWarner Losh #define BIT5  32
790c16b537SWarner Losh #define BIT4  16
800c16b537SWarner Losh #define BIT1   2
810c16b537SWarner Losh #define BIT0   1
820c16b537SWarner Losh 
830c16b537SWarner Losh #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
84f7cd7fe5SConrad Meyer static UNUSED_ATTR const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
85f7cd7fe5SConrad Meyer static UNUSED_ATTR const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
860c16b537SWarner Losh 
870f743729SConrad Meyer #define ZSTD_FRAMEIDSIZE 4   /* magic number size */
880c16b537SWarner Losh 
890c16b537SWarner Losh #define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
90f7cd7fe5SConrad Meyer static UNUSED_ATTR const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
910c16b537SWarner Losh typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
920c16b537SWarner Losh 
9337f1f268SConrad Meyer #define ZSTD_FRAMECHECKSUMSIZE 4
9437f1f268SConrad Meyer 
950c16b537SWarner Losh #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
960c16b537SWarner Losh #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
970c16b537SWarner Losh 
980c16b537SWarner Losh #define HufLog 12
990c16b537SWarner Losh typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
1000c16b537SWarner Losh 
1010c16b537SWarner Losh #define LONGNBSEQ 0x7F00
1020c16b537SWarner Losh 
1030c16b537SWarner Losh #define MINMATCH 3
1040c16b537SWarner Losh 
1050c16b537SWarner Losh #define Litbits  8
1060c16b537SWarner Losh #define MaxLit ((1<<Litbits) - 1)
1070c16b537SWarner Losh #define MaxML   52
1080c16b537SWarner Losh #define MaxLL   35
1090c16b537SWarner Losh #define DefaultMaxOff 28
1100c16b537SWarner Losh #define MaxOff  31
1110c16b537SWarner Losh #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
1120c16b537SWarner Losh #define MLFSELog    9
1130c16b537SWarner Losh #define LLFSELog    9
1140c16b537SWarner Losh #define OffFSELog   8
11519fcbaf1SConrad Meyer #define MaxFSELog  MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
1160c16b537SWarner Losh 
117f7cd7fe5SConrad Meyer #define ZSTD_MAX_HUF_HEADER_SIZE 128 /* header + <= 127 byte tree description */
118f7cd7fe5SConrad Meyer /* Each table cannot take more than #symbols * FSELog bits */
119f7cd7fe5SConrad Meyer #define ZSTD_MAX_FSE_HEADERS_SIZE (((MaxML + 1) * MLFSELog + (MaxLL + 1) * LLFSELog + (MaxOff + 1) * OffFSELog + 7) / 8)
120f7cd7fe5SConrad Meyer 
121*5ff13fbcSAllan Jude static UNUSED_ATTR const U8 LL_bits[MaxLL+1] = {
122f7cd7fe5SConrad Meyer      0, 0, 0, 0, 0, 0, 0, 0,
123052d3c12SConrad Meyer      0, 0, 0, 0, 0, 0, 0, 0,
124052d3c12SConrad Meyer      1, 1, 1, 1, 2, 2, 3, 3,
125052d3c12SConrad Meyer      4, 6, 7, 8, 9,10,11,12,
126f7cd7fe5SConrad Meyer     13,14,15,16
127f7cd7fe5SConrad Meyer };
128f7cd7fe5SConrad Meyer static UNUSED_ATTR const S16 LL_defaultNorm[MaxLL+1] = {
129f7cd7fe5SConrad Meyer      4, 3, 2, 2, 2, 2, 2, 2,
130052d3c12SConrad Meyer      2, 2, 2, 2, 2, 1, 1, 1,
131052d3c12SConrad Meyer      2, 2, 2, 2, 2, 2, 2, 2,
132052d3c12SConrad Meyer      2, 3, 2, 1, 1, 1, 1, 1,
133f7cd7fe5SConrad Meyer     -1,-1,-1,-1
134f7cd7fe5SConrad Meyer };
1350c16b537SWarner Losh #define LL_DEFAULTNORMLOG 6  /* for static allocation */
136f7cd7fe5SConrad Meyer static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
1370c16b537SWarner Losh 
138*5ff13fbcSAllan Jude static UNUSED_ATTR const U8 ML_bits[MaxML+1] = {
139f7cd7fe5SConrad Meyer      0, 0, 0, 0, 0, 0, 0, 0,
140052d3c12SConrad Meyer      0, 0, 0, 0, 0, 0, 0, 0,
141052d3c12SConrad Meyer      0, 0, 0, 0, 0, 0, 0, 0,
142052d3c12SConrad Meyer      0, 0, 0, 0, 0, 0, 0, 0,
143052d3c12SConrad Meyer      1, 1, 1, 1, 2, 2, 3, 3,
144052d3c12SConrad Meyer      4, 4, 5, 7, 8, 9,10,11,
145f7cd7fe5SConrad Meyer     12,13,14,15,16
146f7cd7fe5SConrad Meyer };
147f7cd7fe5SConrad Meyer static UNUSED_ATTR const S16 ML_defaultNorm[MaxML+1] = {
148f7cd7fe5SConrad Meyer      1, 4, 3, 2, 2, 2, 2, 2,
149052d3c12SConrad Meyer      2, 1, 1, 1, 1, 1, 1, 1,
150052d3c12SConrad Meyer      1, 1, 1, 1, 1, 1, 1, 1,
151052d3c12SConrad Meyer      1, 1, 1, 1, 1, 1, 1, 1,
152052d3c12SConrad Meyer      1, 1, 1, 1, 1, 1, 1, 1,
153052d3c12SConrad Meyer      1, 1, 1, 1, 1, 1,-1,-1,
154f7cd7fe5SConrad Meyer     -1,-1,-1,-1,-1
155f7cd7fe5SConrad Meyer };
1560c16b537SWarner Losh #define ML_DEFAULTNORMLOG 6  /* for static allocation */
157f7cd7fe5SConrad Meyer static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
1580c16b537SWarner Losh 
159f7cd7fe5SConrad Meyer static UNUSED_ATTR const S16 OF_defaultNorm[DefaultMaxOff+1] = {
160f7cd7fe5SConrad Meyer      1, 1, 1, 1, 1, 1, 2, 2,
161052d3c12SConrad Meyer      2, 1, 1, 1, 1, 1, 1, 1,
162052d3c12SConrad Meyer      1, 1, 1, 1, 1, 1, 1, 1,
163f7cd7fe5SConrad Meyer     -1,-1,-1,-1,-1
164f7cd7fe5SConrad Meyer };
1650c16b537SWarner Losh #define OF_DEFAULTNORMLOG 5  /* for static allocation */
166f7cd7fe5SConrad Meyer static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
1670c16b537SWarner Losh 
1680c16b537SWarner Losh 
1690c16b537SWarner Losh /*-*******************************************
1700c16b537SWarner Losh *  Shared functions to include for inlining
1710c16b537SWarner Losh *********************************************/
ZSTD_copy8(void * dst,const void * src)17237f1f268SConrad Meyer static void ZSTD_copy8(void* dst, const void* src) {
173*5ff13fbcSAllan Jude #if defined(ZSTD_ARCH_ARM_NEON)
17437f1f268SConrad Meyer     vst1_u8((uint8_t*)dst, vld1_u8((const uint8_t*)src));
17537f1f268SConrad Meyer #else
176f7cd7fe5SConrad Meyer     ZSTD_memcpy(dst, src, 8);
17737f1f268SConrad Meyer #endif
17837f1f268SConrad Meyer }
1790c16b537SWarner Losh #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
180*5ff13fbcSAllan Jude 
181*5ff13fbcSAllan Jude /* Need to use memmove here since the literal buffer can now be located within
182*5ff13fbcSAllan Jude    the dst buffer. In circumstances where the op "catches up" to where the
183*5ff13fbcSAllan Jude    literal buffer is, there can be partial overlaps in this call on the final
184*5ff13fbcSAllan Jude    copy if the literal is being shifted by less than 16 bytes. */
ZSTD_copy16(void * dst,const void * src)18537f1f268SConrad Meyer static void ZSTD_copy16(void* dst, const void* src) {
186*5ff13fbcSAllan Jude #if defined(ZSTD_ARCH_ARM_NEON)
18737f1f268SConrad Meyer     vst1q_u8((uint8_t*)dst, vld1q_u8((const uint8_t*)src));
188*5ff13fbcSAllan Jude #elif defined(ZSTD_ARCH_X86_SSE2)
189*5ff13fbcSAllan Jude     _mm_storeu_si128((__m128i*)dst, _mm_loadu_si128((const __m128i*)src));
190*5ff13fbcSAllan Jude #elif defined(__clang__)
191*5ff13fbcSAllan Jude     ZSTD_memmove(dst, src, 16);
19237f1f268SConrad Meyer #else
193*5ff13fbcSAllan Jude     /* ZSTD_memmove is not inlined properly by gcc */
194*5ff13fbcSAllan Jude     BYTE copy16_buf[16];
195*5ff13fbcSAllan Jude     ZSTD_memcpy(copy16_buf, src, 16);
196*5ff13fbcSAllan Jude     ZSTD_memcpy(dst, copy16_buf, 16);
19737f1f268SConrad Meyer #endif
19837f1f268SConrad Meyer }
1994d3f1eafSConrad Meyer #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; }
2004d3f1eafSConrad Meyer 
2019cbefe25SConrad Meyer #define WILDCOPY_OVERLENGTH 32
2029cbefe25SConrad Meyer #define WILDCOPY_VECLEN 16
2034d3f1eafSConrad Meyer 
2044d3f1eafSConrad Meyer typedef enum {
2054d3f1eafSConrad Meyer     ZSTD_no_overlap,
2069cbefe25SConrad Meyer     ZSTD_overlap_src_before_dst
2074d3f1eafSConrad Meyer     /*  ZSTD_overlap_dst_before_src, */
2084d3f1eafSConrad Meyer } ZSTD_overlap_e;
2090c16b537SWarner Losh 
2100c16b537SWarner Losh /*! ZSTD_wildcopy() :
211f7cd7fe5SConrad Meyer  *  Custom version of ZSTD_memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0)
2129cbefe25SConrad Meyer  *  @param ovtype controls the overlap detection
2139cbefe25SConrad Meyer  *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
2149cbefe25SConrad Meyer  *         - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart.
2159cbefe25SConrad Meyer  *           The src buffer must be before the dst buffer.
2169cbefe25SConrad Meyer  */
21737f1f268SConrad Meyer MEM_STATIC FORCE_INLINE_ATTR
ZSTD_wildcopy(void * dst,const void * src,ptrdiff_t length,ZSTD_overlap_e const ovtype)2189cbefe25SConrad Meyer void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
2190c16b537SWarner Losh {
2204d3f1eafSConrad Meyer     ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src;
2210c16b537SWarner Losh     const BYTE* ip = (const BYTE*)src;
2220c16b537SWarner Losh     BYTE* op = (BYTE*)dst;
2230c16b537SWarner Losh     BYTE* const oend = op + length;
2244d3f1eafSConrad Meyer 
2259cbefe25SConrad Meyer     if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
2269cbefe25SConrad Meyer         /* Handle short offset copies. */
2274d3f1eafSConrad Meyer         do {
2289cbefe25SConrad Meyer             COPY8(op, ip)
2299cbefe25SConrad Meyer         } while (op < oend);
2309cbefe25SConrad Meyer     } else {
2319cbefe25SConrad Meyer         assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN);
23237f1f268SConrad Meyer         /* Separate out the first COPY16() call because the copy length is
2339cbefe25SConrad Meyer          * almost certain to be short, so the branches have different
23437f1f268SConrad Meyer          * probabilities. Since it is almost certain to be short, only do
23537f1f268SConrad Meyer          * one COPY16() in the first call. Then, do two calls per loop since
23637f1f268SConrad Meyer          * at that point it is more likely to have a high trip count.
2379cbefe25SConrad Meyer          */
238f7cd7fe5SConrad Meyer #ifdef __aarch64__
23937f1f268SConrad Meyer         do {
2409cbefe25SConrad Meyer             COPY16(op, ip);
24137f1f268SConrad Meyer         }
24237f1f268SConrad Meyer         while (op < oend);
24337f1f268SConrad Meyer #else
244f7cd7fe5SConrad Meyer         ZSTD_copy16(op, ip);
245f7cd7fe5SConrad Meyer         if (16 >= length) return;
246f7cd7fe5SConrad Meyer         op += 16;
247f7cd7fe5SConrad Meyer         ip += 16;
2489cbefe25SConrad Meyer         do {
2499cbefe25SConrad Meyer             COPY16(op, ip);
2504d3f1eafSConrad Meyer             COPY16(op, ip);
2514d3f1eafSConrad Meyer         }
2524d3f1eafSConrad Meyer         while (op < oend);
25337f1f268SConrad Meyer #endif
2544d3f1eafSConrad Meyer     }
2554d3f1eafSConrad Meyer }
2564d3f1eafSConrad Meyer 
ZSTD_limitCopy(void * dst,size_t dstCapacity,const void * src,size_t srcSize)25737f1f268SConrad Meyer MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
25837f1f268SConrad Meyer {
25937f1f268SConrad Meyer     size_t const length = MIN(dstCapacity, srcSize);
26037f1f268SConrad Meyer     if (length > 0) {
261f7cd7fe5SConrad Meyer         ZSTD_memcpy(dst, src, length);
26237f1f268SConrad Meyer     }
26337f1f268SConrad Meyer     return length;
26437f1f268SConrad Meyer }
26537f1f268SConrad Meyer 
26637f1f268SConrad Meyer /* define "workspace is too large" as this number of times larger than needed */
26737f1f268SConrad Meyer #define ZSTD_WORKSPACETOOLARGE_FACTOR 3
26837f1f268SConrad Meyer 
26937f1f268SConrad Meyer /* when workspace is continuously too large
27037f1f268SConrad Meyer  * during at least this number of times,
27137f1f268SConrad Meyer  * context's memory usage is considered wasteful,
27237f1f268SConrad Meyer  * because it's sized to handle a worst case scenario which rarely happens.
27337f1f268SConrad Meyer  * In which case, resize it down to free some memory */
27437f1f268SConrad Meyer #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128
27537f1f268SConrad Meyer 
276f7cd7fe5SConrad Meyer /* Controls whether the input/output buffer is buffered or stable. */
277f7cd7fe5SConrad Meyer typedef enum {
278f7cd7fe5SConrad Meyer     ZSTD_bm_buffered = 0,  /* Buffer the input/output */
279f7cd7fe5SConrad Meyer     ZSTD_bm_stable = 1     /* ZSTD_inBuffer/ZSTD_outBuffer is stable */
280f7cd7fe5SConrad Meyer } ZSTD_bufferMode_e;
281f7cd7fe5SConrad Meyer 
2820c16b537SWarner Losh 
2830c16b537SWarner Losh /*-*******************************************
284052d3c12SConrad Meyer *  Private declarations
2850c16b537SWarner Losh *********************************************/
2860c16b537SWarner Losh typedef struct seqDef_s {
287*5ff13fbcSAllan Jude     U32 offBase;   /* offBase == Offset + ZSTD_REP_NUM, or repcode 1,2,3 */
2880c16b537SWarner Losh     U16 litLength;
289*5ff13fbcSAllan Jude     U16 mlBase;    /* mlBase == matchLength - MINMATCH */
2900c16b537SWarner Losh } seqDef;
2910c16b537SWarner Losh 
292*5ff13fbcSAllan Jude /* Controls whether seqStore has a single "long" litLength or matchLength. See seqStore_t. */
293*5ff13fbcSAllan Jude typedef enum {
294*5ff13fbcSAllan Jude     ZSTD_llt_none = 0,             /* no longLengthType */
295*5ff13fbcSAllan Jude     ZSTD_llt_literalLength = 1,    /* represents a long literal */
296*5ff13fbcSAllan Jude     ZSTD_llt_matchLength = 2       /* represents a long match */
297*5ff13fbcSAllan Jude } ZSTD_longLengthType_e;
298*5ff13fbcSAllan Jude 
2990c16b537SWarner Losh typedef struct {
3000c16b537SWarner Losh     seqDef* sequencesStart;
301f7cd7fe5SConrad Meyer     seqDef* sequences;      /* ptr to end of sequences */
3020c16b537SWarner Losh     BYTE* litStart;
303f7cd7fe5SConrad Meyer     BYTE* lit;              /* ptr to end of literals */
3040c16b537SWarner Losh     BYTE* llCode;
3050c16b537SWarner Losh     BYTE* mlCode;
3060c16b537SWarner Losh     BYTE* ofCode;
3070f743729SConrad Meyer     size_t maxNbSeq;
3080f743729SConrad Meyer     size_t maxNbLit;
309f7cd7fe5SConrad Meyer 
310*5ff13fbcSAllan Jude     /* longLengthPos and longLengthType to allow us to represent either a single litLength or matchLength
311f7cd7fe5SConrad Meyer      * in the seqStore that has a value larger than U16 (if it exists). To do so, we increment
312f7cd7fe5SConrad Meyer      * the existing value of the litLength or matchLength by 0x10000.
313f7cd7fe5SConrad Meyer      */
314*5ff13fbcSAllan Jude     ZSTD_longLengthType_e   longLengthType;
315f7cd7fe5SConrad Meyer     U32                     longLengthPos;  /* Index of the sequence to apply long length modification to */
3160c16b537SWarner Losh } seqStore_t;
3170c16b537SWarner Losh 
31837f1f268SConrad Meyer typedef struct {
31937f1f268SConrad Meyer     U32 litLength;
32037f1f268SConrad Meyer     U32 matchLength;
32137f1f268SConrad Meyer } ZSTD_sequenceLength;
32237f1f268SConrad Meyer 
32337f1f268SConrad Meyer /**
32437f1f268SConrad Meyer  * Returns the ZSTD_sequenceLength for the given sequences. It handles the decoding of long sequences
325*5ff13fbcSAllan Jude  * indicated by longLengthPos and longLengthType, and adds MINMATCH back to matchLength.
32637f1f268SConrad Meyer  */
ZSTD_getSequenceLength(seqStore_t const * seqStore,seqDef const * seq)32737f1f268SConrad Meyer MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const* seqStore, seqDef const* seq)
32837f1f268SConrad Meyer {
32937f1f268SConrad Meyer     ZSTD_sequenceLength seqLen;
33037f1f268SConrad Meyer     seqLen.litLength = seq->litLength;
331*5ff13fbcSAllan Jude     seqLen.matchLength = seq->mlBase + MINMATCH;
33237f1f268SConrad Meyer     if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) {
333*5ff13fbcSAllan Jude         if (seqStore->longLengthType == ZSTD_llt_literalLength) {
33437f1f268SConrad Meyer             seqLen.litLength += 0xFFFF;
33537f1f268SConrad Meyer         }
336*5ff13fbcSAllan Jude         if (seqStore->longLengthType == ZSTD_llt_matchLength) {
33737f1f268SConrad Meyer             seqLen.matchLength += 0xFFFF;
33837f1f268SConrad Meyer         }
33937f1f268SConrad Meyer     }
34037f1f268SConrad Meyer     return seqLen;
34137f1f268SConrad Meyer }
34237f1f268SConrad Meyer 
3432b9c00cbSConrad Meyer /**
3442b9c00cbSConrad Meyer  * Contains the compressed frame size and an upper-bound for the decompressed frame size.
3452b9c00cbSConrad Meyer  * Note: before using `compressedSize`, check for errors using ZSTD_isError().
3462b9c00cbSConrad Meyer  *       similarly, before using `decompressedBound`, check for errors using:
3472b9c00cbSConrad Meyer  *          `decompressedBound != ZSTD_CONTENTSIZE_ERROR`
3482b9c00cbSConrad Meyer  */
3492b9c00cbSConrad Meyer typedef struct {
3502b9c00cbSConrad Meyer     size_t compressedSize;
3512b9c00cbSConrad Meyer     unsigned long long decompressedBound;
3522b9c00cbSConrad Meyer } ZSTD_frameSizeInfo;   /* decompress & legacy */
3532b9c00cbSConrad Meyer 
354052d3c12SConrad Meyer const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);   /* compress & dictBuilder */
355052d3c12SConrad Meyer void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);   /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
3560c16b537SWarner Losh 
3570c16b537SWarner Losh /* custom memory allocation functions */
358f7cd7fe5SConrad Meyer void* ZSTD_customMalloc(size_t size, ZSTD_customMem customMem);
359f7cd7fe5SConrad Meyer void* ZSTD_customCalloc(size_t size, ZSTD_customMem customMem);
360f7cd7fe5SConrad Meyer void ZSTD_customFree(void* ptr, ZSTD_customMem customMem);
3610c16b537SWarner Losh 
3620c16b537SWarner Losh 
ZSTD_highbit32(U32 val)363052d3c12SConrad Meyer MEM_STATIC U32 ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
3640c16b537SWarner Losh {
3650c16b537SWarner Losh     assert(val != 0);
3660c16b537SWarner Losh     {
3670c16b537SWarner Losh #   if defined(_MSC_VER)   /* Visual */
368f7cd7fe5SConrad Meyer #       if STATIC_BMI2 == 1
369f7cd7fe5SConrad Meyer             return _lzcnt_u32(val)^31;
370f7cd7fe5SConrad Meyer #       else
371*5ff13fbcSAllan Jude             if (val != 0) {
372*5ff13fbcSAllan Jude                 unsigned long r;
373*5ff13fbcSAllan Jude                 _BitScanReverse(&r, val);
374*5ff13fbcSAllan Jude                 return (unsigned)r;
375*5ff13fbcSAllan Jude             } else {
376*5ff13fbcSAllan Jude                 /* Should not reach this code path */
377*5ff13fbcSAllan Jude                 __assume(0);
378*5ff13fbcSAllan Jude             }
379f7cd7fe5SConrad Meyer #       endif
3800f743729SConrad Meyer #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* GCC Intrinsic */
3819cbefe25SConrad Meyer         return __builtin_clz (val) ^ 31;
3829cbefe25SConrad Meyer #   elif defined(__ICCARM__)    /* IAR Intrinsic */
3839cbefe25SConrad Meyer         return 31 - __CLZ(val);
3840c16b537SWarner Losh #   else   /* Software version */
385052d3c12SConrad Meyer         static const U32 DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
3860c16b537SWarner Losh         U32 v = val;
3870c16b537SWarner Losh         v |= v >> 1;
3880c16b537SWarner Losh         v |= v >> 2;
3890c16b537SWarner Losh         v |= v >> 4;
3900c16b537SWarner Losh         v |= v >> 8;
3910c16b537SWarner Losh         v |= v >> 16;
392052d3c12SConrad Meyer         return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
3930c16b537SWarner Losh #   endif
3940c16b537SWarner Losh     }
3950c16b537SWarner Losh }
3960c16b537SWarner Losh 
397*5ff13fbcSAllan Jude /**
398*5ff13fbcSAllan Jude  * Counts the number of trailing zeros of a `size_t`.
399*5ff13fbcSAllan Jude  * Most compilers should support CTZ as a builtin. A backup
400*5ff13fbcSAllan Jude  * implementation is provided if the builtin isn't supported, but
401*5ff13fbcSAllan Jude  * it may not be terribly efficient.
402*5ff13fbcSAllan Jude  */
ZSTD_countTrailingZeros(size_t val)403*5ff13fbcSAllan Jude MEM_STATIC unsigned ZSTD_countTrailingZeros(size_t val)
404*5ff13fbcSAllan Jude {
405*5ff13fbcSAllan Jude     if (MEM_64bits()) {
406*5ff13fbcSAllan Jude #       if defined(_MSC_VER) && defined(_WIN64)
407*5ff13fbcSAllan Jude #           if STATIC_BMI2
408*5ff13fbcSAllan Jude                 return _tzcnt_u64(val);
409*5ff13fbcSAllan Jude #           else
410*5ff13fbcSAllan Jude                 if (val != 0) {
411*5ff13fbcSAllan Jude                     unsigned long r;
412*5ff13fbcSAllan Jude                     _BitScanForward64(&r, (U64)val);
413*5ff13fbcSAllan Jude                     return (unsigned)r;
414*5ff13fbcSAllan Jude                 } else {
415*5ff13fbcSAllan Jude                     /* Should not reach this code path */
416*5ff13fbcSAllan Jude                     __assume(0);
417*5ff13fbcSAllan Jude                 }
418*5ff13fbcSAllan Jude #           endif
419*5ff13fbcSAllan Jude #       elif defined(__GNUC__) && (__GNUC__ >= 4)
420*5ff13fbcSAllan Jude             return __builtin_ctzll((U64)val);
421*5ff13fbcSAllan Jude #       else
422*5ff13fbcSAllan Jude             static const int DeBruijnBytePos[64] = {  0,  1,  2,  7,  3, 13,  8, 19,
423*5ff13fbcSAllan Jude                                                       4, 25, 14, 28,  9, 34, 20, 56,
424*5ff13fbcSAllan Jude                                                       5, 17, 26, 54, 15, 41, 29, 43,
425*5ff13fbcSAllan Jude                                                       10, 31, 38, 35, 21, 45, 49, 57,
426*5ff13fbcSAllan Jude                                                       63,  6, 12, 18, 24, 27, 33, 55,
427*5ff13fbcSAllan Jude                                                       16, 53, 40, 42, 30, 37, 44, 48,
428*5ff13fbcSAllan Jude                                                       62, 11, 23, 32, 52, 39, 36, 47,
429*5ff13fbcSAllan Jude                                                       61, 22, 51, 46, 60, 50, 59, 58 };
430*5ff13fbcSAllan Jude             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
431*5ff13fbcSAllan Jude #       endif
432*5ff13fbcSAllan Jude     } else { /* 32 bits */
433*5ff13fbcSAllan Jude #       if defined(_MSC_VER)
434*5ff13fbcSAllan Jude             if (val != 0) {
435*5ff13fbcSAllan Jude                 unsigned long r;
436*5ff13fbcSAllan Jude                 _BitScanForward(&r, (U32)val);
437*5ff13fbcSAllan Jude                 return (unsigned)r;
438*5ff13fbcSAllan Jude             } else {
439*5ff13fbcSAllan Jude                 /* Should not reach this code path */
440*5ff13fbcSAllan Jude                 __assume(0);
441*5ff13fbcSAllan Jude             }
442*5ff13fbcSAllan Jude #       elif defined(__GNUC__) && (__GNUC__ >= 3)
443*5ff13fbcSAllan Jude             return __builtin_ctz((U32)val);
444*5ff13fbcSAllan Jude #       else
445*5ff13fbcSAllan Jude             static const int DeBruijnBytePos[32] = {  0,  1, 28,  2, 29, 14, 24,  3,
446*5ff13fbcSAllan Jude                                                      30, 22, 20, 15, 25, 17,  4,  8,
447*5ff13fbcSAllan Jude                                                      31, 27, 13, 23, 21, 19, 16,  7,
448*5ff13fbcSAllan Jude                                                      26, 12, 18,  6, 11,  5, 10,  9 };
449*5ff13fbcSAllan Jude             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
450*5ff13fbcSAllan Jude #       endif
451*5ff13fbcSAllan Jude     }
452*5ff13fbcSAllan Jude }
453*5ff13fbcSAllan Jude 
4540c16b537SWarner Losh 
4550c16b537SWarner Losh /* ZSTD_invalidateRepCodes() :
4560c16b537SWarner Losh  * ensures next compression will not use repcodes from previous block.
4570c16b537SWarner Losh  * Note : only works with regular variant;
4580c16b537SWarner Losh  *        do not use with extDict variant ! */
459052d3c12SConrad Meyer void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);   /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
4600c16b537SWarner Losh 
4610c16b537SWarner Losh 
4620c16b537SWarner Losh typedef struct {
4630c16b537SWarner Losh     blockType_e blockType;
4640c16b537SWarner Losh     U32 lastBlock;
4650c16b537SWarner Losh     U32 origSize;
466a0483764SConrad Meyer } blockProperties_t;   /* declared here for decompress and fullbench */
4670c16b537SWarner Losh 
4680c16b537SWarner Losh /*! ZSTD_getcBlockSize() :
4690c16b537SWarner Losh  *  Provides the size of compressed block from block header `src` */
470052d3c12SConrad Meyer /* Used by: decompress, fullbench (does not get its definition from here) */
4710c16b537SWarner Losh size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
4720c16b537SWarner Losh                           blockProperties_t* bpPtr);
4730c16b537SWarner Losh 
474a0483764SConrad Meyer /*! ZSTD_decodeSeqHeaders() :
475a0483764SConrad Meyer  *  decode sequence header from src */
476a0483764SConrad Meyer /* Used by: decompress, fullbench (does not get its definition from here) */
477a0483764SConrad Meyer size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
478a0483764SConrad Meyer                        const void* src, size_t srcSize);
479a0483764SConrad Meyer 
480*5ff13fbcSAllan Jude /**
481*5ff13fbcSAllan Jude  * @returns true iff the CPU supports dynamic BMI2 dispatch.
482*5ff13fbcSAllan Jude  */
ZSTD_cpuSupportsBmi2(void)483*5ff13fbcSAllan Jude MEM_STATIC int ZSTD_cpuSupportsBmi2(void)
484*5ff13fbcSAllan Jude {
485*5ff13fbcSAllan Jude     ZSTD_cpuid_t cpuid = ZSTD_cpuid();
486*5ff13fbcSAllan Jude     return ZSTD_cpuid_bmi1(cpuid) && ZSTD_cpuid_bmi2(cpuid);
487*5ff13fbcSAllan Jude }
488a0483764SConrad Meyer 
4890c16b537SWarner Losh #if defined (__cplusplus)
4900c16b537SWarner Losh }
4910c16b537SWarner Losh #endif
4920c16b537SWarner Losh 
4930c16b537SWarner Losh #endif   /* ZSTD_CCOMMON_H_MODULE */
494