1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0-only 2 /* 3 * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc. 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 /* 16 * Disable the aarch64 NEON SIMD intrinsics for kernel builds. Safely 17 * using them in the kernel context requires saving/restoring the FPU 18 * registers which is not currently done. 19 */ 20 #ifdef _KERNEL 21 #define ZSTD_NO_INTRINSICS 22 #endif 23 24 /* this module contains definitions which must be identical 25 * across compression, decompression and dictBuilder. 26 * It also contains a few functions useful to at least 2 of them 27 * and which benefit from being inlined */ 28 29 /*-************************************* 30 * Dependencies 31 ***************************************/ 32 #if !defined(ZSTD_NO_INTRINSICS) && defined(__ARM_NEON) 33 #include <arm_neon.h> 34 #endif 35 #include "compiler.h" 36 #include "mem.h" 37 #include "debug.h" /* assert, DEBUGLOG, RAWLOG, g_debuglevel */ 38 #include "error_private.h" 39 #define ZSTD_STATIC_LINKING_ONLY 40 #include "../zstd.h" 41 #define FSE_STATIC_LINKING_ONLY 42 #include "fse.h" 43 #define HUF_STATIC_LINKING_ONLY 44 #include "huf.h" 45 #ifndef XXH_STATIC_LINKING_ONLY 46 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */ 47 #endif 48 #include "xxhash.h" /* XXH_reset, update, digest */ 49 50 #if defined (__cplusplus) 51 extern "C" { 52 #endif 53 54 /* ---- static assert (debug) --- */ 55 #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) 56 #define FSE_isError ERR_isError 57 #define HUF_isError ERR_isError 58 59 60 /*-************************************* 61 * shared macros 62 ***************************************/ 63 #undef MIN 64 #undef MAX 65 #define MIN(a,b) ((a)<(b) ? (a) : (b)) 66 #define MAX(a,b) ((a)>(b) ? (a) : (b)) 67 68 /** 69 * Ignore: this is an internal helper. 70 * 71 * This is a helper function to help force C99-correctness during compilation. 72 * Under strict compilation modes, variadic macro arguments can't be empty. 73 * However, variadic function arguments can be. Using a function therefore lets 74 * us statically check that at least one (string) argument was passed, 75 * independent of the compilation flags. 76 */ 77 static INLINE_KEYWORD UNUSED_ATTR 78 void _force_has_format_string(const char *format, ...) { 79 (void)format; 80 } 81 82 /** 83 * Ignore: this is an internal helper. 84 * 85 * We want to force this function invocation to be syntactically correct, but 86 * we don't want to force runtime evaluation of its arguments. 87 */ 88 #define _FORCE_HAS_FORMAT_STRING(...) \ 89 if (0) { \ 90 _force_has_format_string(__VA_ARGS__); \ 91 } 92 93 /** 94 * Return the specified error if the condition evaluates to true. 95 * 96 * In debug modes, prints additional information. 97 * In order to do that (particularly, printing the conditional that failed), 98 * this can't just wrap RETURN_ERROR(). 99 */ 100 #define RETURN_ERROR_IF(cond, err, ...) \ 101 if (cond) { \ 102 RAWLOG(3, "%s:%d: ERROR!: check %s failed, returning %s", \ 103 __FILE__, __LINE__, ZSTD_QUOTE(cond), ZSTD_QUOTE(ERROR(err))); \ 104 _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \ 105 RAWLOG(3, ": " __VA_ARGS__); \ 106 RAWLOG(3, "\n"); \ 107 return ERROR(err); \ 108 } 109 110 /** 111 * Unconditionally return the specified error. 112 * 113 * In debug modes, prints additional information. 114 */ 115 #define RETURN_ERROR(err, ...) \ 116 do { \ 117 RAWLOG(3, "%s:%d: ERROR!: unconditional check failed, returning %s", \ 118 __FILE__, __LINE__, ZSTD_QUOTE(ERROR(err))); \ 119 _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \ 120 RAWLOG(3, ": " __VA_ARGS__); \ 121 RAWLOG(3, "\n"); \ 122 return ERROR(err); \ 123 } while(0); 124 125 /** 126 * If the provided expression evaluates to an error code, returns that error code. 127 * 128 * In debug modes, prints additional information. 129 */ 130 #define FORWARD_IF_ERROR(err, ...) \ 131 do { \ 132 size_t const err_code = (err); \ 133 if (ERR_isError(err_code)) { \ 134 RAWLOG(3, "%s:%d: ERROR!: forwarding error in %s: %s", \ 135 __FILE__, __LINE__, ZSTD_QUOTE(err), ERR_getErrorName(err_code)); \ 136 _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \ 137 RAWLOG(3, ": " __VA_ARGS__); \ 138 RAWLOG(3, "\n"); \ 139 return err_code; \ 140 } \ 141 } while(0); 142 143 144 /*-************************************* 145 * Common constants 146 ***************************************/ 147 #define ZSTD_OPT_NUM (1<<12) 148 149 #define ZSTD_REP_NUM 3 /* number of repcodes */ 150 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1) 151 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 }; 152 153 #define KB *(1 <<10) 154 #define MB *(1 <<20) 155 #define GB *(1U<<30) 156 157 #define BIT7 128 158 #define BIT6 64 159 #define BIT5 32 160 #define BIT4 16 161 #define BIT1 2 162 #define BIT0 1 163 164 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10 165 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 }; 166 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 }; 167 168 #define ZSTD_FRAMEIDSIZE 4 /* magic number size */ 169 170 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */ 171 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE; 172 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e; 173 174 #define ZSTD_FRAMECHECKSUMSIZE 4 175 176 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ 177 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ 178 179 #define HufLog 12 180 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e; 181 182 #define LONGNBSEQ 0x7F00 183 184 #define MINMATCH 3 185 186 #define Litbits 8 187 #define MaxLit ((1<<Litbits) - 1) 188 #define MaxML 52 189 #define MaxLL 35 190 #define DefaultMaxOff 28 191 #define MaxOff 31 192 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ 193 #define MLFSELog 9 194 #define LLFSELog 9 195 #define OffFSELog 8 196 #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog) 197 198 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 199 0, 0, 0, 0, 0, 0, 0, 0, 200 1, 1, 1, 1, 2, 2, 3, 3, 201 4, 6, 7, 8, 9,10,11,12, 202 13,14,15,16 }; 203 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 204 2, 2, 2, 2, 2, 1, 1, 1, 205 2, 2, 2, 2, 2, 2, 2, 2, 206 2, 3, 2, 1, 1, 1, 1, 1, 207 -1,-1,-1,-1 }; 208 #define LL_DEFAULTNORMLOG 6 /* for static allocation */ 209 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; 210 211 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 212 0, 0, 0, 0, 0, 0, 0, 0, 213 0, 0, 0, 0, 0, 0, 0, 0, 214 0, 0, 0, 0, 0, 0, 0, 0, 215 1, 1, 1, 1, 2, 2, 3, 3, 216 4, 4, 5, 7, 8, 9,10,11, 217 12,13,14,15,16 }; 218 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 219 2, 1, 1, 1, 1, 1, 1, 1, 220 1, 1, 1, 1, 1, 1, 1, 1, 221 1, 1, 1, 1, 1, 1, 1, 1, 222 1, 1, 1, 1, 1, 1, 1, 1, 223 1, 1, 1, 1, 1, 1,-1,-1, 224 -1,-1,-1,-1,-1 }; 225 #define ML_DEFAULTNORMLOG 6 /* for static allocation */ 226 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; 227 228 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 229 2, 1, 1, 1, 1, 1, 1, 1, 230 1, 1, 1, 1, 1, 1, 1, 1, 231 -1,-1,-1,-1,-1 }; 232 #define OF_DEFAULTNORMLOG 5 /* for static allocation */ 233 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; 234 235 236 /*-******************************************* 237 * Shared functions to include for inlining 238 *********************************************/ 239 static void ZSTD_copy8(void* dst, const void* src) { 240 #if !defined(ZSTD_NO_INTRINSICS) && defined(__ARM_NEON) 241 vst1_u8((uint8_t*)dst, vld1_u8((const uint8_t*)src)); 242 #else 243 memcpy(dst, src, 8); 244 #endif 245 } 246 247 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 248 static void ZSTD_copy16(void* dst, const void* src) { 249 #if !defined(ZSTD_NO_INTRINSICS) && defined(__ARM_NEON) 250 vst1q_u8((uint8_t*)dst, vld1q_u8((const uint8_t*)src)); 251 #else 252 memcpy(dst, src, 16); 253 #endif 254 } 255 #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; } 256 257 #define WILDCOPY_OVERLENGTH 32 258 #define WILDCOPY_VECLEN 16 259 260 typedef enum { 261 ZSTD_no_overlap, 262 ZSTD_overlap_src_before_dst 263 /* ZSTD_overlap_dst_before_src, */ 264 } ZSTD_overlap_e; 265 266 /*! ZSTD_wildcopy() : 267 * Custom version of memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0) 268 * @param ovtype controls the overlap detection 269 * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart. 270 * - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart. 271 * The src buffer must be before the dst buffer. 272 */ 273 MEM_STATIC FORCE_INLINE_ATTR 274 void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype) 275 { 276 ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src; 277 const BYTE* ip = (const BYTE*)src; 278 BYTE* op = (BYTE*)dst; 279 BYTE* const oend = op + length; 280 281 assert(diff >= 8 || (ovtype == ZSTD_no_overlap && diff <= -WILDCOPY_VECLEN)); 282 283 if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) { 284 /* Handle short offset copies. */ 285 do { 286 COPY8(op, ip) 287 } while (op < oend); 288 } else { 289 assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN); 290 /* Separate out the first COPY16() call because the copy length is 291 * almost certain to be short, so the branches have different 292 * probabilities. Since it is almost certain to be short, only do 293 * one COPY16() in the first call. Then, do two calls per loop since 294 * at that point it is more likely to have a high trip count. 295 */ 296 #ifndef __aarch64__ 297 do { 298 COPY16(op, ip); 299 } 300 while (op < oend); 301 #else 302 COPY16(op, ip); 303 if (op >= oend) return; 304 do { 305 COPY16(op, ip); 306 COPY16(op, ip); 307 } 308 while (op < oend); 309 #endif 310 } 311 } 312 313 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 314 { 315 size_t const length = MIN(dstCapacity, srcSize); 316 if (length > 0) { 317 memcpy(dst, src, length); 318 } 319 return length; 320 } 321 322 /* define "workspace is too large" as this number of times larger than needed */ 323 #define ZSTD_WORKSPACETOOLARGE_FACTOR 3 324 325 /* when workspace is continuously too large 326 * during at least this number of times, 327 * context's memory usage is considered wasteful, 328 * because it's sized to handle a worst case scenario which rarely happens. 329 * In which case, resize it down to free some memory */ 330 #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128 331 332 333 /*-******************************************* 334 * Private declarations 335 *********************************************/ 336 typedef struct seqDef_s { 337 U32 offset; 338 U16 litLength; 339 U16 matchLength; 340 } seqDef; 341 342 typedef struct { 343 seqDef* sequencesStart; 344 seqDef* sequences; 345 BYTE* litStart; 346 BYTE* lit; 347 BYTE* llCode; 348 BYTE* mlCode; 349 BYTE* ofCode; 350 size_t maxNbSeq; 351 size_t maxNbLit; 352 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ 353 U32 longLengthPos; 354 } seqStore_t; 355 356 typedef struct { 357 U32 litLength; 358 U32 matchLength; 359 } ZSTD_sequenceLength; 360 361 /** 362 * Returns the ZSTD_sequenceLength for the given sequences. It handles the decoding of long sequences 363 * indicated by longLengthPos and longLengthID, and adds MINMATCH back to matchLength. 364 */ 365 MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const* seqStore, seqDef const* seq) 366 { 367 ZSTD_sequenceLength seqLen; 368 seqLen.litLength = seq->litLength; 369 seqLen.matchLength = seq->matchLength + MINMATCH; 370 if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) { 371 if (seqStore->longLengthID == 1) { 372 seqLen.litLength += 0xFFFF; 373 } 374 if (seqStore->longLengthID == 2) { 375 seqLen.matchLength += 0xFFFF; 376 } 377 } 378 return seqLen; 379 } 380 381 /** 382 * Contains the compressed frame size and an upper-bound for the decompressed frame size. 383 * Note: before using `compressedSize`, check for errors using ZSTD_isError(). 384 * similarly, before using `decompressedBound`, check for errors using: 385 * `decompressedBound != ZSTD_CONTENTSIZE_ERROR` 386 */ 387 typedef struct { 388 size_t compressedSize; 389 unsigned long long decompressedBound; 390 } ZSTD_frameSizeInfo; /* decompress & legacy */ 391 392 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */ 393 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */ 394 395 /* custom memory allocation functions */ 396 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem); 397 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem); 398 void ZSTD_free(void* ptr, ZSTD_customMem customMem); 399 400 401 MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */ 402 { 403 assert(val != 0); 404 { 405 # if defined(_MSC_VER) /* Visual */ 406 unsigned long r=0; 407 return _BitScanReverse(&r, val) ? (unsigned)r : 0; 408 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */ 409 return __builtin_clz (val) ^ 31; 410 # elif defined(__ICCARM__) /* IAR Intrinsic */ 411 return 31 - __CLZ(val); 412 # else /* Software version */ 413 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 }; 414 U32 v = val; 415 v |= v >> 1; 416 v |= v >> 2; 417 v |= v >> 4; 418 v |= v >> 8; 419 v |= v >> 16; 420 return DeBruijnClz[(v * 0x07C4ACDDU) >> 27]; 421 # endif 422 } 423 } 424 425 426 /* ZSTD_invalidateRepCodes() : 427 * ensures next compression will not use repcodes from previous block. 428 * Note : only works with regular variant; 429 * do not use with extDict variant ! */ 430 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */ 431 432 433 typedef struct { 434 blockType_e blockType; 435 U32 lastBlock; 436 U32 origSize; 437 } blockProperties_t; /* declared here for decompress and fullbench */ 438 439 /*! ZSTD_getcBlockSize() : 440 * Provides the size of compressed block from block header `src` */ 441 /* Used by: decompress, fullbench (does not get its definition from here) */ 442 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, 443 blockProperties_t* bpPtr); 444 445 /*! ZSTD_decodeSeqHeaders() : 446 * decode sequence header from src */ 447 /* Used by: decompress, fullbench (does not get its definition from here) */ 448 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr, 449 const void* src, size_t srcSize); 450 451 452 #if defined (__cplusplus) 453 } 454 #endif 455 456 #endif /* ZSTD_CCOMMON_H_MODULE */ 457