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