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 */ 59 static 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 73 static UNUSED_ATTR const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 }; 74 static 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 */ 79 static UNUSED_ATTR const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE; 80 typedef 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 88 typedef 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 113 static 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 }; 120 static 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 */ 128 static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; 129 130 static 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 }; 139 static 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 */ 149 static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; 150 151 static 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 */ 158 static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; 159 160 161 /*-******************************************* 162 * Shared functions to include for inlining 163 *********************************************/ 164 static 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. */ 177 static 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 196 typedef 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 */ 209 MEM_STATIC FORCE_INLINE_ATTR 210 void 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 242 MEM_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. */ 262 typedef 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 */ 278 typedef 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 ! */ 288 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */ 289 290 291 typedef 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 */ 300 size_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 */ 306 size_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 */ 312 MEM_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 */ 319