zstd_internal.h

  1/* SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause */
  2/*
  3 * Copyright (c) Meta Platforms, Inc. and affiliates.
  4 * All rights reserved.
  5 *
  6 * This source code is licensed under both the BSD-style license (found in the
  7 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  8 * in the COPYING file in the root directory of this source tree).
  9 * You may select, at your option, one of the above-listed licenses.
 10 */
 11
 12#ifndef ZSTD_CCOMMON_H_MODULE
 13#define ZSTD_CCOMMON_H_MODULE
 14
 15/* this module contains definitions which must be identical
 16 * across compression, decompression and dictBuilder.
 17 * It also contains a few functions useful to at least 2 of them
 18 * and which benefit from being inlined */
 19
 20/*-*************************************
 21*  Dependencies
 22***************************************/
 23#include "compiler.h"
 24#include "cpu.h"
 25#include "mem.h"
 26#include "debug.h"                 /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
 27#include "error_private.h"
 28#define ZSTD_STATIC_LINKING_ONLY
 29#include <linux/zstd.h>
 30#define FSE_STATIC_LINKING_ONLY
 31#include "fse.h"
 32#include "huf.h"
 33#include <linux/xxhash.h>                /* XXH_reset, update, digest */
 34#define ZSTD_TRACE 0
 35
 36/* ---- static assert (debug) --- */
 37#define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
 38#define ZSTD_isError ERR_isError   /* for inlining */
 39#define FSE_isError  ERR_isError
 40#define HUF_isError  ERR_isError
 41
 42
 43/*-*************************************
 44*  shared macros
 45***************************************/
 46#undef MIN
 47#undef MAX
 48#define MIN(a,b) ((a)<(b) ? (a) : (b))
 49#define MAX(a,b) ((a)>(b) ? (a) : (b))
 50#define BOUNDED(min,val,max) (MAX(min,MIN(val,max)))
 51
 52
 53/*-*************************************
 54*  Common constants
 55***************************************/
 56#define ZSTD_OPT_NUM    (1<<12)
 57
 58#define ZSTD_REP_NUM      3                 /* number of repcodes */
 59static UNUSED_ATTR const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
 60
 61#define KB *(1 <<10)
 62#define MB *(1 <<20)
 63#define GB *(1U<<30)
 64
 65#define BIT7 128
 66#define BIT6  64
 67#define BIT5  32
 68#define BIT4  16
 69#define BIT1   2
 70#define BIT0   1
 71
 72#define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
 73static UNUSED_ATTR const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
 74static UNUSED_ATTR const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
 75
 76#define ZSTD_FRAMEIDSIZE 4   /* magic number size */
 77
 78#define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
 79static UNUSED_ATTR const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
 80typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
 81
 82#define ZSTD_FRAMECHECKSUMSIZE 4
 83
 84#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
 85#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */)   /* for a non-null block */
 86#define MIN_LITERALS_FOR_4_STREAMS 6
 87
 88typedef enum { set_basic, set_rle, set_compressed, set_repeat } SymbolEncodingType_e;
 89
 90#define LONGNBSEQ 0x7F00
 91
 92#define MINMATCH 3
 93
 94#define Litbits  8
 95#define LitHufLog 11
 96#define MaxLit ((1<<Litbits) - 1)
 97#define MaxML   52
 98#define MaxLL   35
 99#define DefaultMaxOff 28
100#define MaxOff  31
101#define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
102#define MLFSELog    9
103#define LLFSELog    9
104#define OffFSELog   8
105#define MaxFSELog  MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
106#define MaxMLBits 16
107#define MaxLLBits 16
108
109#define ZSTD_MAX_HUF_HEADER_SIZE 128 /* header + <= 127 byte tree description */
110/* Each table cannot take more than #symbols * FSELog bits */
111#define ZSTD_MAX_FSE_HEADERS_SIZE (((MaxML + 1) * MLFSELog + (MaxLL + 1) * LLFSELog + (MaxOff + 1) * OffFSELog + 7) / 8)
112
113static UNUSED_ATTR const U8 LL_bits[MaxLL+1] = {
114     0, 0, 0, 0, 0, 0, 0, 0,
115     0, 0, 0, 0, 0, 0, 0, 0,
116     1, 1, 1, 1, 2, 2, 3, 3,
117     4, 6, 7, 8, 9,10,11,12,
118    13,14,15,16
119};
120static UNUSED_ATTR const S16 LL_defaultNorm[MaxLL+1] = {
121     4, 3, 2, 2, 2, 2, 2, 2,
122     2, 2, 2, 2, 2, 1, 1, 1,
123     2, 2, 2, 2, 2, 2, 2, 2,
124     2, 3, 2, 1, 1, 1, 1, 1,
125    -1,-1,-1,-1
126};
127#define LL_DEFAULTNORMLOG 6  /* for static allocation */
128static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
129
130static UNUSED_ATTR const U8 ML_bits[MaxML+1] = {
131     0, 0, 0, 0, 0, 0, 0, 0,
132     0, 0, 0, 0, 0, 0, 0, 0,
133     0, 0, 0, 0, 0, 0, 0, 0,
134     0, 0, 0, 0, 0, 0, 0, 0,
135     1, 1, 1, 1, 2, 2, 3, 3,
136     4, 4, 5, 7, 8, 9,10,11,
137    12,13,14,15,16
138};
139static UNUSED_ATTR const S16 ML_defaultNorm[MaxML+1] = {
140     1, 4, 3, 2, 2, 2, 2, 2,
141     2, 1, 1, 1, 1, 1, 1, 1,
142     1, 1, 1, 1, 1, 1, 1, 1,
143     1, 1, 1, 1, 1, 1, 1, 1,
144     1, 1, 1, 1, 1, 1, 1, 1,
145     1, 1, 1, 1, 1, 1,-1,-1,
146    -1,-1,-1,-1,-1
147};
148#define ML_DEFAULTNORMLOG 6  /* for static allocation */
149static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
150
151static UNUSED_ATTR const S16 OF_defaultNorm[DefaultMaxOff+1] = {
152     1, 1, 1, 1, 1, 1, 2, 2,
153     2, 1, 1, 1, 1, 1, 1, 1,
154     1, 1, 1, 1, 1, 1, 1, 1,
155    -1,-1,-1,-1,-1
156};
157#define OF_DEFAULTNORMLOG 5  /* for static allocation */
158static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
159
160
161/*-*******************************************
162*  Shared functions to include for inlining
163*********************************************/
164static void ZSTD_copy8(void* dst, const void* src) {
165#if defined(ZSTD_ARCH_ARM_NEON)
166    vst1_u8((uint8_t*)dst, vld1_u8((const uint8_t*)src));
167#else
168    ZSTD_memcpy(dst, src, 8);
169#endif
170}
171#define COPY8(d,s) do { ZSTD_copy8(d,s); d+=8; s+=8; } while (0)
172
173/* Need to use memmove here since the literal buffer can now be located within
174   the dst buffer. In circumstances where the op "catches up" to where the
175   literal buffer is, there can be partial overlaps in this call on the final
176   copy if the literal is being shifted by less than 16 bytes. */
177static void ZSTD_copy16(void* dst, const void* src) {
178#if defined(ZSTD_ARCH_ARM_NEON)
179    vst1q_u8((uint8_t*)dst, vld1q_u8((const uint8_t*)src));
180#elif defined(ZSTD_ARCH_X86_SSE2)
181    _mm_storeu_si128((__m128i*)dst, _mm_loadu_si128((const __m128i*)src));
182#elif defined(__clang__)
183    ZSTD_memmove(dst, src, 16);
184#else
185    /* ZSTD_memmove is not inlined properly by gcc */
186    BYTE copy16_buf[16];
187    ZSTD_memcpy(copy16_buf, src, 16);
188    ZSTD_memcpy(dst, copy16_buf, 16);
189#endif
190}
191#define COPY16(d,s) do { ZSTD_copy16(d,s); d+=16; s+=16; } while (0)
192
193#define WILDCOPY_OVERLENGTH 32
194#define WILDCOPY_VECLEN 16
195
196typedef enum {
197    ZSTD_no_overlap,
198    ZSTD_overlap_src_before_dst
199    /*  ZSTD_overlap_dst_before_src, */
200} ZSTD_overlap_e;
201
202/*! ZSTD_wildcopy() :
203 *  Custom version of ZSTD_memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0)
204 *  @param ovtype controls the overlap detection
205 *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
206 *         - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart.
207 *           The src buffer must be before the dst buffer.
208 */
209MEM_STATIC FORCE_INLINE_ATTR
210void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
211{
212    ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src;
213    const BYTE* ip = (const BYTE*)src;
214    BYTE* op = (BYTE*)dst;
215    BYTE* const oend = op + length;
216
217    if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
218        /* Handle short offset copies. */
219        do {
220            COPY8(op, ip);
221        } while (op < oend);
222    } else {
223        assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN);
224        /* Separate out the first COPY16() call because the copy length is
225         * almost certain to be short, so the branches have different
226         * probabilities. Since it is almost certain to be short, only do
227         * one COPY16() in the first call. Then, do two calls per loop since
228         * at that point it is more likely to have a high trip count.
229         */
230        ZSTD_copy16(op, ip);
231        if (16 >= length) return;
232        op += 16;
233        ip += 16;
234        do {
235            COPY16(op, ip);
236            COPY16(op, ip);
237        }
238        while (op < oend);
239    }
240}
241
242MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
243{
244    size_t const length = MIN(dstCapacity, srcSize);
245    if (length > 0) {
246        ZSTD_memcpy(dst, src, length);
247    }
248    return length;
249}
250
251/* define "workspace is too large" as this number of times larger than needed */
252#define ZSTD_WORKSPACETOOLARGE_FACTOR 3
253
254/* when workspace is continuously too large
255 * during at least this number of times,
256 * context's memory usage is considered wasteful,
257 * because it's sized to handle a worst case scenario which rarely happens.
258 * In which case, resize it down to free some memory */
259#define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128
260
261/* Controls whether the input/output buffer is buffered or stable. */
262typedef enum {
263    ZSTD_bm_buffered = 0,  /* Buffer the input/output */
264    ZSTD_bm_stable = 1     /* ZSTD_inBuffer/ZSTD_outBuffer is stable */
265} ZSTD_bufferMode_e;
266
267
268/*-*******************************************
269*  Private declarations
270*********************************************/
271
272/*
273 * Contains the compressed frame size and an upper-bound for the decompressed frame size.
274 * Note: before using `compressedSize`, check for errors using ZSTD_isError().
275 *       similarly, before using `decompressedBound`, check for errors using:
276 *          `decompressedBound != ZSTD_CONTENTSIZE_ERROR`
277 */
278typedef struct {
279    size_t nbBlocks;
280    size_t compressedSize;
281    unsigned long long decompressedBound;
282} ZSTD_frameSizeInfo;   /* decompress & legacy */
283
284/* ZSTD_invalidateRepCodes() :
285 * ensures next compression will not use repcodes from previous block.
286 * Note : only works with regular variant;
287 *        do not use with extDict variant ! */
288void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);   /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
289
290
291typedef struct {
292    blockType_e blockType;
293    U32 lastBlock;
294    U32 origSize;
295} blockProperties_t;   /* declared here for decompress and fullbench */
296
297/*! ZSTD_getcBlockSize() :
298 *  Provides the size of compressed block from block header `src` */
299/*  Used by: decompress, fullbench */
300size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
301                          blockProperties_t* bpPtr);
302
303/*! ZSTD_decodeSeqHeaders() :
304 *  decode sequence header from src */
305/*  Used by: zstd_decompress_block, fullbench */
306size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
307                       const void* src, size_t srcSize);
308
309/*
310 * @returns true iff the CPU supports dynamic BMI2 dispatch.
311 */
312MEM_STATIC int ZSTD_cpuSupportsBmi2(void)
313{
314    ZSTD_cpuid_t cpuid = ZSTD_cpuid();
315    return ZSTD_cpuid_bmi1(cpuid) && ZSTD_cpuid_bmi2(cpuid);
316}
317
318#endif   /* ZSTD_CCOMMON_H_MODULE */