zstd/common/zstd_internal.h

0001 /*
0002  * Copyright (c) Yann Collet, Facebook, Inc.
0003  * All rights reserved.
0004  *
0005  * This source code is licensed under both the BSD-style license (found in the
0006  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0007  * in the COPYING file in the root directory of this source tree).
0008  * You may select, at your option, one of the above-listed licenses.
0009  */
0010
0011 #ifndef ZSTD_CCOMMON_H_MODULE
0012 #define ZSTD_CCOMMON_H_MODULE
0013
0014 /* this module contains definitions which must be identical
0015  * across compression, decompression and dictBuilder.
0016  * It also contains a few functions useful to at least 2 of them
0017  * and which benefit from being inlined */
0018
0019 /*-*************************************
0020 *  Dependencies
0021 ***************************************/
0022 #include "compiler.h"
0023 #include "mem.h"
0024 #include "debug.h"                 /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
0025 #include "error_private.h"
0026 #define ZSTD_STATIC_LINKING_ONLY
0027 #include <linux/zstd.h>
0028 #define FSE_STATIC_LINKING_ONLY
0029 #include "fse.h"
0030 #define HUF_STATIC_LINKING_ONLY
0031 #include "huf.h"
0032 #include <linux/xxhash.h>                /* XXH_reset, update, digest */
0033 #define ZSTD_TRACE 0
0034
0035
0036 /* ---- static assert (debug) --- */
0037 #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
0038 #define ZSTD_isError ERR_isError   /* for inlining */
0039 #define FSE_isError  ERR_isError
0040 #define HUF_isError  ERR_isError
0041
0042
0043 /*-*************************************
0044 *  shared macros
0045 ***************************************/
0046 #undef MIN
0047 #undef MAX
0048 #define MIN(a,b) ((a)<(b) ? (a) : (b))
0049 #define MAX(a,b) ((a)>(b) ? (a) : (b))
0050
0051 /*
0052  * Ignore: this is an internal helper.
0053  *
0054  * This is a helper function to help force C99-correctness during compilation.
0055  * Under strict compilation modes, variadic macro arguments can't be empty.
0056  * However, variadic function arguments can be. Using a function therefore lets
0057  * us statically check that at least one (string) argument was passed,
0058  * independent of the compilation flags.
0059  */
0060 static INLINE_KEYWORD UNUSED_ATTR
0061 void _force_has_format_string(const char *format, ...) {
0062   (void)format;
0063 }
0064
0065 /*
0066  * Ignore: this is an internal helper.
0067  *
0068  * We want to force this function invocation to be syntactically correct, but
0069  * we don't want to force runtime evaluation of its arguments.
0070  */
0071 #define _FORCE_HAS_FORMAT_STRING(...) \
0072   if (0) { \
0073     _force_has_format_string(__VA_ARGS__); \
0074   }
0075
0076 /*
0077  * Return the specified error if the condition evaluates to true.
0078  *
0079  * In debug modes, prints additional information.
0080  * In order to do that (particularly, printing the conditional that failed),
0081  * this can't just wrap RETURN_ERROR().
0082  */
0083 #define RETURN_ERROR_IF(cond, err, ...) \
0084   if (cond) { \
0085     RAWLOG(3, "%s:%d: ERROR!: check %s failed, returning %s", \
0086            __FILE__, __LINE__, ZSTD_QUOTE(cond), ZSTD_QUOTE(ERROR(err))); \
0087     _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \
0088     RAWLOG(3, ": " __VA_ARGS__); \
0089     RAWLOG(3, "\n"); \
0090     return ERROR(err); \
0091   }
0092
0093 /*
0094  * Unconditionally return the specified error.
0095  *
0096  * In debug modes, prints additional information.
0097  */
0098 #define RETURN_ERROR(err, ...) \
0099   do { \
0100     RAWLOG(3, "%s:%d: ERROR!: unconditional check failed, returning %s", \
0101            __FILE__, __LINE__, ZSTD_QUOTE(ERROR(err))); \
0102     _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \
0103     RAWLOG(3, ": " __VA_ARGS__); \
0104     RAWLOG(3, "\n"); \
0105     return ERROR(err); \
0106   } while(0);
0107
0108 /*
0109  * If the provided expression evaluates to an error code, returns that error code.
0110  *
0111  * In debug modes, prints additional information.
0112  */
0113 #define FORWARD_IF_ERROR(err, ...) \
0114   do { \
0115     size_t const err_code = (err); \
0116     if (ERR_isError(err_code)) { \
0117       RAWLOG(3, "%s:%d: ERROR!: forwarding error in %s: %s", \
0118              __FILE__, __LINE__, ZSTD_QUOTE(err), ERR_getErrorName(err_code)); \
0119       _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \
0120       RAWLOG(3, ": " __VA_ARGS__); \
0121       RAWLOG(3, "\n"); \
0122       return err_code; \
0123     } \
0124   } while(0);
0125
0126
0127 /*-*************************************
0128 *  Common constants
0129 ***************************************/
0130 #define ZSTD_OPT_NUM    (1<<12)
0131
0132 #define ZSTD_REP_NUM      3                 /* number of repcodes */
0133 #define ZSTD_REP_MOVE     (ZSTD_REP_NUM-1)
0134 static UNUSED_ATTR const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
0135
0136 #define KB *(1 <<10)
0137 #define MB *(1 <<20)
0138 #define GB *(1U<<30)
0139
0140 #define BIT7 128
0141 #define BIT6  64
0142 #define BIT5  32
0143 #define BIT4  16
0144 #define BIT1   2
0145 #define BIT0   1
0146
0147 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
0148 static UNUSED_ATTR const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
0149 static UNUSED_ATTR const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
0150
0151 #define ZSTD_FRAMEIDSIZE 4   /* magic number size */
0152
0153 #define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
0154 static UNUSED_ATTR const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
0155 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
0156
0157 #define ZSTD_FRAMECHECKSUMSIZE 4
0158
0159 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
0160 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
0161
0162 #define HufLog 12
0163 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
0164
0165 #define LONGNBSEQ 0x7F00
0166
0167 #define MINMATCH 3
0168
0169 #define Litbits  8
0170 #define MaxLit ((1<<Litbits) - 1)
0171 #define MaxML   52
0172 #define MaxLL   35
0173 #define DefaultMaxOff 28
0174 #define MaxOff  31
0175 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
0176 #define MLFSELog    9
0177 #define LLFSELog    9
0178 #define OffFSELog   8
0179 #define MaxFSELog  MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
0180
0181 #define ZSTD_MAX_HUF_HEADER_SIZE 128 /* header + <= 127 byte tree description */
0182 /* Each table cannot take more than #symbols * FSELog bits */
0183 #define ZSTD_MAX_FSE_HEADERS_SIZE (((MaxML + 1) * MLFSELog + (MaxLL + 1) * LLFSELog + (MaxOff + 1) * OffFSELog + 7) / 8)
0184
0185 static UNUSED_ATTR const U32 LL_bits[MaxLL+1] = {
0186      0, 0, 0, 0, 0, 0, 0, 0,
0187      0, 0, 0, 0, 0, 0, 0, 0,
0188      1, 1, 1, 1, 2, 2, 3, 3,
0189      4, 6, 7, 8, 9,10,11,12,
0190     13,14,15,16
0191 };
0192 static UNUSED_ATTR const S16 LL_defaultNorm[MaxLL+1] = {
0193      4, 3, 2, 2, 2, 2, 2, 2,
0194      2, 2, 2, 2, 2, 1, 1, 1,
0195      2, 2, 2, 2, 2, 2, 2, 2,
0196      2, 3, 2, 1, 1, 1, 1, 1,
0197     -1,-1,-1,-1
0198 };
0199 #define LL_DEFAULTNORMLOG 6  /* for static allocation */
0200 static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
0201
0202 static UNUSED_ATTR const U32 ML_bits[MaxML+1] = {
0203      0, 0, 0, 0, 0, 0, 0, 0,
0204      0, 0, 0, 0, 0, 0, 0, 0,
0205      0, 0, 0, 0, 0, 0, 0, 0,
0206      0, 0, 0, 0, 0, 0, 0, 0,
0207      1, 1, 1, 1, 2, 2, 3, 3,
0208      4, 4, 5, 7, 8, 9,10,11,
0209     12,13,14,15,16
0210 };
0211 static UNUSED_ATTR const S16 ML_defaultNorm[MaxML+1] = {
0212      1, 4, 3, 2, 2, 2, 2, 2,
0213      2, 1, 1, 1, 1, 1, 1, 1,
0214      1, 1, 1, 1, 1, 1, 1, 1,
0215      1, 1, 1, 1, 1, 1, 1, 1,
0216      1, 1, 1, 1, 1, 1, 1, 1,
0217      1, 1, 1, 1, 1, 1,-1,-1,
0218     -1,-1,-1,-1,-1
0219 };
0220 #define ML_DEFAULTNORMLOG 6  /* for static allocation */
0221 static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
0222
0223 static UNUSED_ATTR const S16 OF_defaultNorm[DefaultMaxOff+1] = {
0224      1, 1, 1, 1, 1, 1, 2, 2,
0225      2, 1, 1, 1, 1, 1, 1, 1,
0226      1, 1, 1, 1, 1, 1, 1, 1,
0227     -1,-1,-1,-1,-1
0228 };
0229 #define OF_DEFAULTNORMLOG 5  /* for static allocation */
0230 static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
0231
0232
0233 /*-*******************************************
0234 *  Shared functions to include for inlining
0235 *********************************************/
0236 static void ZSTD_copy8(void* dst, const void* src) {
0237     ZSTD_memcpy(dst, src, 8);
0238 }
0239
0240 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
0241 static void ZSTD_copy16(void* dst, const void* src) {
0242     ZSTD_memcpy(dst, src, 16);
0243 }
0244 #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; }
0245
0246 #define WILDCOPY_OVERLENGTH 32
0247 #define WILDCOPY_VECLEN 16
0248
0249 typedef enum {
0250     ZSTD_no_overlap,
0251     ZSTD_overlap_src_before_dst
0252     /*  ZSTD_overlap_dst_before_src, */
0253 } ZSTD_overlap_e;
0254
0255 /*! ZSTD_wildcopy() :
0256  *  Custom version of ZSTD_memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0)
0257  *  @param ovtype controls the overlap detection
0258  *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
0259  *         - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart.
0260  *           The src buffer must be before the dst buffer.
0261  */
0262 MEM_STATIC FORCE_INLINE_ATTR
0263 void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
0264 {
0265     ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src;
0266     const BYTE* ip = (const BYTE*)src;
0267     BYTE* op = (BYTE*)dst;
0268     BYTE* const oend = op + length;
0269
0270     assert(diff >= 8 || (ovtype == ZSTD_no_overlap && diff <= -WILDCOPY_VECLEN));
0271
0272     if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
0273         /* Handle short offset copies. */
0274         do {
0275             COPY8(op, ip)
0276         } while (op < oend);
0277     } else {
0278         assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN);
0279         /* Separate out the first COPY16() call because the copy length is
0280          * almost certain to be short, so the branches have different
0281          * probabilities. Since it is almost certain to be short, only do
0282          * one COPY16() in the first call. Then, do two calls per loop since
0283          * at that point it is more likely to have a high trip count.
0284          */
0285 #ifdef __aarch64__
0286         do {
0287             COPY16(op, ip);
0288         }
0289         while (op < oend);
0290 #else
0291         ZSTD_copy16(op, ip);
0292         if (16 >= length) return;
0293         op += 16;
0294         ip += 16;
0295         do {
0296             COPY16(op, ip);
0297             COPY16(op, ip);
0298         }
0299         while (op < oend);
0300 #endif
0301     }
0302 }
0303
0304 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
0305 {
0306     size_t const length = MIN(dstCapacity, srcSize);
0307     if (length > 0) {
0308         ZSTD_memcpy(dst, src, length);
0309     }
0310     return length;
0311 }
0312
0313 /* define "workspace is too large" as this number of times larger than needed */
0314 #define ZSTD_WORKSPACETOOLARGE_FACTOR 3
0315
0316 /* when workspace is continuously too large
0317  * during at least this number of times,
0318  * context's memory usage is considered wasteful,
0319  * because it's sized to handle a worst case scenario which rarely happens.
0320  * In which case, resize it down to free some memory */
0321 #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128
0322
0323 /* Controls whether the input/output buffer is buffered or stable. */
0324 typedef enum {
0325     ZSTD_bm_buffered = 0,  /* Buffer the input/output */
0326     ZSTD_bm_stable = 1     /* ZSTD_inBuffer/ZSTD_outBuffer is stable */
0327 } ZSTD_bufferMode_e;
0328
0329
0330 /*-*******************************************
0331 *  Private declarations
0332 *********************************************/
0333 typedef struct seqDef_s {
0334     U32 offset;         /* Offset code of the sequence */
0335     U16 litLength;
0336     U16 matchLength;
0337 } seqDef;
0338
0339 typedef struct {
0340     seqDef* sequencesStart;
0341     seqDef* sequences;      /* ptr to end of sequences */
0342     BYTE* litStart;
0343     BYTE* lit;              /* ptr to end of literals */
0344     BYTE* llCode;
0345     BYTE* mlCode;
0346     BYTE* ofCode;
0347     size_t maxNbSeq;
0348     size_t maxNbLit;
0349
0350     /* longLengthPos and longLengthID to allow us to represent either a single litLength or matchLength
0351      * in the seqStore that has a value larger than U16 (if it exists). To do so, we increment
0352      * the existing value of the litLength or matchLength by 0x10000.
0353      */
0354     U32   longLengthID;   /* 0 == no longLength; 1 == Represent the long literal; 2 == Represent the long match; */
0355     U32   longLengthPos;  /* Index of the sequence to apply long length modification to */
0356 } seqStore_t;
0357
0358 typedef struct {
0359     U32 litLength;
0360     U32 matchLength;
0361 } ZSTD_sequenceLength;
0362
0363 /*
0364  * Returns the ZSTD_sequenceLength for the given sequences. It handles the decoding of long sequences
0365  * indicated by longLengthPos and longLengthID, and adds MINMATCH back to matchLength.
0366  */
0367 MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const* seqStore, seqDef const* seq)
0368 {
0369     ZSTD_sequenceLength seqLen;
0370     seqLen.litLength = seq->litLength;
0371     seqLen.matchLength = seq->matchLength + MINMATCH;
0372     if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) {
0373         if (seqStore->longLengthID == 1) {
0374             seqLen.litLength += 0xFFFF;
0375         }
0376         if (seqStore->longLengthID == 2) {
0377             seqLen.matchLength += 0xFFFF;
0378         }
0379     }
0380     return seqLen;
0381 }
0382
0383 /*
0384  * Contains the compressed frame size and an upper-bound for the decompressed frame size.
0385  * Note: before using `compressedSize`, check for errors using ZSTD_isError().
0386  *       similarly, before using `decompressedBound`, check for errors using:
0387  *          `decompressedBound != ZSTD_CONTENTSIZE_ERROR`
0388  */
0389 typedef struct {
0390     size_t compressedSize;
0391     unsigned long long decompressedBound;
0392 } ZSTD_frameSizeInfo;   /* decompress & legacy */
0393
0394 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);   /* compress & dictBuilder */
0395 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);   /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
0396
0397 /* custom memory allocation functions */
0398 void* ZSTD_customMalloc(size_t size, ZSTD_customMem customMem);
0399 void* ZSTD_customCalloc(size_t size, ZSTD_customMem customMem);
0400 void ZSTD_customFree(void* ptr, ZSTD_customMem customMem);
0401
0402
0403 MEM_STATIC U32 ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
0404 {
0405     assert(val != 0);
0406     {
0407 #   if (__GNUC__ >= 3)   /* GCC Intrinsic */
0408         return __builtin_clz (val) ^ 31;
0409 #   else   /* Software version */
0410         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 };
0411         U32 v = val;
0412         v |= v >> 1;
0413         v |= v >> 2;
0414         v |= v >> 4;
0415         v |= v >> 8;
0416         v |= v >> 16;
0417         return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
0418 #   endif
0419     }
0420 }
0421
0422
0423 /* ZSTD_invalidateRepCodes() :
0424  * ensures next compression will not use repcodes from previous block.
0425  * Note : only works with regular variant;
0426  *        do not use with extDict variant ! */
0427 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);   /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
0428
0429
0430 typedef struct {
0431     blockType_e blockType;
0432     U32 lastBlock;
0433     U32 origSize;
0434 } blockProperties_t;   /* declared here for decompress and fullbench */
0435
0436 /*! ZSTD_getcBlockSize() :
0437  *  Provides the size of compressed block from block header `src` */
0438 /* Used by: decompress, fullbench (does not get its definition from here) */
0439 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
0440                           blockProperties_t* bpPtr);
0441
0442 /*! ZSTD_decodeSeqHeaders() :
0443  *  decode sequence header from src */
0444 /* Used by: decompress, fullbench (does not get its definition from here) */
0445 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
0446                        const void* src, size_t srcSize);
0447
0448
0449
0450 #endif   /* ZSTD_CCOMMON_H_MODULE */