sys/contrib/zstd/lib/common/zstd_internal.h

   1 /*
   2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11 #ifndef ZSTD_CCOMMON_H_MODULE
  12 #define ZSTD_CCOMMON_H_MODULE
  13
  14 /* this module contains definitions which must be identical
  15  * across compression, decompression and dictBuilder.
  16  * It also contains a few functions useful to at least 2 of them
  17  * and which benefit from being inlined */
  18
  19 /*-*************************************
  20 *  Dependencies
  21 ***************************************/
  22 #include "compiler.h"
  23 #include "mem.h"
  24 #include "debug.h"                 /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
  25 #include "error_private.h"
  26 #define ZSTD_STATIC_LINKING_ONLY
  27 #include "zstd.h"
  28 #define FSE_STATIC_LINKING_ONLY
  29 #include "fse.h"
  30 #define HUF_STATIC_LINKING_ONLY
  31 #include "huf.h"
  32 #ifndef XXH_STATIC_LINKING_ONLY
  33 #  define XXH_STATIC_LINKING_ONLY  /* XXH64_state_t */
  34 #endif
  35 #include "xxhash.h"                /* XXH_reset, update, digest */
  36
  37 #if defined (__cplusplus)
  38 extern "C" {
  39 #endif
  40
  41 /* ---- static assert (debug) --- */
  42 #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
  43 #define ZSTD_isError ERR_isError   /* for inlining */
  44 #define FSE_isError  ERR_isError
  45 #define HUF_isError  ERR_isError
  46
  47
  48 /*-*************************************
  49 *  shared macros
  50 ***************************************/
  51 #undef MIN
  52 #undef MAX
  53 #define MIN(a,b) ((a)<(b) ? (a) : (b))
  54 #define MAX(a,b) ((a)>(b) ? (a) : (b))
  55
  56 /**
  57  * Return the specified error if the condition evaluates to true.
  58  *
  59  * In debug modes, prints additional information.
  60  * In order to do that (particularly, printing the conditional that failed),
  61  * this can't just wrap RETURN_ERROR().
  62  */
  63 #define RETURN_ERROR_IF(cond, err, ...) \
  64   if (cond) { \
  65     RAWLOG(3, "%s:%d: ERROR!: check %s failed, returning %s", __FILE__, __LINE__, ZSTD_QUOTE(cond), ZSTD_QUOTE(ERROR(err))); \
  66     RAWLOG(3, ": " __VA_ARGS__); \
  67     RAWLOG(3, "\n"); \
  68     return ERROR(err); \
  69   }
  70
  71 /**
  72  * Unconditionally return the specified error.
  73  *
  74  * In debug modes, prints additional information.
  75  */
  76 #define RETURN_ERROR(err, ...) \
  77   do { \
  78     RAWLOG(3, "%s:%d: ERROR!: unconditional check failed, returning %s", __FILE__, __LINE__, ZSTD_QUOTE(ERROR(err))); \
  79     RAWLOG(3, ": " __VA_ARGS__); \
  80     RAWLOG(3, "\n"); \
  81     return ERROR(err); \
  82   } while(0);
  83
  84 /**
  85  * If the provided expression evaluates to an error code, returns that error code.
  86  *
  87  * In debug modes, prints additional information.
  88  */
  89 #define FORWARD_IF_ERROR(err, ...) \
  90   do { \
  91     size_t const err_code = (err); \
  92     if (ERR_isError(err_code)) { \
  93       RAWLOG(3, "%s:%d: ERROR!: forwarding error in %s: %s", __FILE__, __LINE__, ZSTD_QUOTE(err), ERR_getErrorName(err_code)); \
  94       RAWLOG(3, ": " __VA_ARGS__); \
  95       RAWLOG(3, "\n"); \
  96       return err_code; \
  97     } \
  98   } while(0);
  99
 100
 101 /*-*************************************
 102 *  Common constants
 103 ***************************************/
 104 #define ZSTD_OPT_NUM    (1<<12)
 105
 106 #define ZSTD_REP_NUM      3                 /* number of repcodes */
 107 #define ZSTD_REP_MOVE     (ZSTD_REP_NUM-1)
 108 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
 109
 110 #define KB *(1 <<10)
 111 #define MB *(1 <<20)
 112 #define GB *(1U<<30)
 113
 114 #define BIT7 128
 115 #define BIT6  64
 116 #define BIT5  32
 117 #define BIT4  16
 118 #define BIT1   2
 119 #define BIT0   1
 120
 121 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
 122 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
 123 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
 124
 125 #define ZSTD_FRAMEIDSIZE 4   /* magic number size */
 126
 127 #define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
 128 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
 129 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
 130
 131 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
 132 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
 133
 134 #define HufLog 12
 135 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
 136
 137 #define LONGNBSEQ 0x7F00
 138
 139 #define MINMATCH 3
 140
 141 #define Litbits  8
 142 #define MaxLit ((1<<Litbits) - 1)
 143 #define MaxML   52
 144 #define MaxLL   35
 145 #define DefaultMaxOff 28
 146 #define MaxOff  31
 147 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
 148 #define MLFSELog    9
 149 #define LLFSELog    9
 150 #define OffFSELog   8
 151 #define MaxFSELog  MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
 152
 153 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
 154                                       0, 0, 0, 0, 0, 0, 0, 0,
 155                                       1, 1, 1, 1, 2, 2, 3, 3,
 156                                       4, 6, 7, 8, 9,10,11,12,
 157                                      13,14,15,16 };
 158 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2,
 159                                              2, 2, 2, 2, 2, 1, 1, 1,
 160                                              2, 2, 2, 2, 2, 2, 2, 2,
 161                                              2, 3, 2, 1, 1, 1, 1, 1,
 162                                             -1,-1,-1,-1 };
 163 #define LL_DEFAULTNORMLOG 6  /* for static allocation */
 164 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
 165
 166 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
 167                                       0, 0, 0, 0, 0, 0, 0, 0,
 168                                       0, 0, 0, 0, 0, 0, 0, 0,
 169                                       0, 0, 0, 0, 0, 0, 0, 0,
 170                                       1, 1, 1, 1, 2, 2, 3, 3,
 171                                       4, 4, 5, 7, 8, 9,10,11,
 172                                      12,13,14,15,16 };
 173 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2,
 174                                              2, 1, 1, 1, 1, 1, 1, 1,
 175                                              1, 1, 1, 1, 1, 1, 1, 1,
 176                                              1, 1, 1, 1, 1, 1, 1, 1,
 177                                              1, 1, 1, 1, 1, 1, 1, 1,
 178                                              1, 1, 1, 1, 1, 1,-1,-1,
 179                                             -1,-1,-1,-1,-1 };
 180 #define ML_DEFAULTNORMLOG 6  /* for static allocation */
 181 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
 182
 183 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2,
 184                                                      2, 1, 1, 1, 1, 1, 1, 1,
 185                                                      1, 1, 1, 1, 1, 1, 1, 1,
 186                                                     -1,-1,-1,-1,-1 };
 187 #define OF_DEFAULTNORMLOG 5  /* for static allocation */
 188 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
 189
 190
 191 /*-*******************************************
 192 *  Shared functions to include for inlining
 193 *********************************************/
 194 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
 195
 196 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
 197 static void ZSTD_copy16(void* dst, const void* src) { memcpy(dst, src, 16); }
 198 #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; }
 199
 200 #define WILDCOPY_OVERLENGTH 32
 201 #define WILDCOPY_VECLEN 16
 202
 203 typedef enum {
 204     ZSTD_no_overlap,
 205     ZSTD_overlap_src_before_dst
 206     /*  ZSTD_overlap_dst_before_src, */
 207 } ZSTD_overlap_e;
 208
 209 /*! ZSTD_wildcopy() :
 210  *  Custom version of memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0)
 211  *  @param ovtype controls the overlap detection
 212  *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
 213  *         - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart.
 214  *           The src buffer must be before the dst buffer.
 215  */
 216 MEM_STATIC FORCE_INLINE_ATTR DONT_VECTORIZE
 217 void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
 218 {
 219     ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src;
 220     const BYTE* ip = (const BYTE*)src;
 221     BYTE* op = (BYTE*)dst;
 222     BYTE* const oend = op + length;
 223
 224     assert(diff >= 8 || (ovtype == ZSTD_no_overlap && diff <= -WILDCOPY_VECLEN));
 225
 226     if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
 227         /* Handle short offset copies. */
 228         do {
 229             COPY8(op, ip)
 230         } while (op < oend);
 231     } else {
 232         assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN);
 233         /* Separate out the first two COPY16() calls because the copy length is
 234          * almost certain to be short, so the branches have different
 235          * probabilities.
 236          * On gcc-9 unrolling once is +1.6%, twice is +2%, thrice is +1.8%.
 237          * On clang-8 unrolling once is +1.4%, twice is +3.3%, thrice is +3%.
 238          */
 239         COPY16(op, ip);
 240         COPY16(op, ip);
 241         if (op >= oend) return;
 242         do {
 243             COPY16(op, ip);
 244             COPY16(op, ip);
 245         }
 246         while (op < oend);
 247     }
 248 }
 249
 250
 251 /*-*******************************************
 252 *  Private declarations
 253 *********************************************/
 254 typedef struct seqDef_s {
 255     U32 offset;
 256     U16 litLength;
 257     U16 matchLength;
 258 } seqDef;
 259
 260 typedef struct {
 261     seqDef* sequencesStart;
 262     seqDef* sequences;
 263     BYTE* litStart;
 264     BYTE* lit;
 265     BYTE* llCode;
 266     BYTE* mlCode;
 267     BYTE* ofCode;
 268     size_t maxNbSeq;
 269     size_t maxNbLit;
 270     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
 271     U32   longLengthPos;
 272 } seqStore_t;
 273
 274 /**
 275  * Contains the compressed frame size and an upper-bound for the decompressed frame size.
 276  * Note: before using `compressedSize`, check for errors using ZSTD_isError().
 277  *       similarly, before using `decompressedBound`, check for errors using:
 278  *          `decompressedBound != ZSTD_CONTENTSIZE_ERROR`
 279  */
 280 typedef struct {
 281     size_t compressedSize;
 282     unsigned long long decompressedBound;
 283 } ZSTD_frameSizeInfo;   /* decompress & legacy */
 284
 285 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);   /* compress & dictBuilder */
 286 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);   /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
 287
 288 /* custom memory allocation functions */
 289 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
 290 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
 291 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
 292
 293
 294 MEM_STATIC U32 ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
 295 {
 296     assert(val != 0);
 297     {
 298 #   if defined(_MSC_VER)   /* Visual */
 299         unsigned long r=0;
 300         _BitScanReverse(&r, val);
 301         return (unsigned)r;
 302 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* GCC Intrinsic */
 303         return __builtin_clz (val) ^ 31;
 304 #   elif defined(__ICCARM__)    /* IAR Intrinsic */
 305         return 31 - __CLZ(val);
 306 #   else   /* Software version */
 307         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 };
 308         U32 v = val;
 309         v |= v >> 1;
 310         v |= v >> 2;
 311         v |= v >> 4;
 312         v |= v >> 8;
 313         v |= v >> 16;
 314         return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
 315 #   endif
 316     }
 317 }
 318
 319
 320 /* ZSTD_invalidateRepCodes() :
 321  * ensures next compression will not use repcodes from previous block.
 322  * Note : only works with regular variant;
 323  *        do not use with extDict variant ! */
 324 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);   /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
 325
 326
 327 typedef struct {
 328     blockType_e blockType;
 329     U32 lastBlock;
 330     U32 origSize;
 331 } blockProperties_t;   /* declared here for decompress and fullbench */
 332
 333 /*! ZSTD_getcBlockSize() :
 334  *  Provides the size of compressed block from block header `src` */
 335 /* Used by: decompress, fullbench (does not get its definition from here) */
 336 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
 337                           blockProperties_t* bpPtr);
 338
 339 /*! ZSTD_decodeSeqHeaders() :
 340  *  decode sequence header from src */
 341 /* Used by: decompress, fullbench (does not get its definition from here) */
 342 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
 343                        const void* src, size_t srcSize);
 344
 345
 346 #if defined (__cplusplus)
 347 }
 348 #endif
 349
 350 #endif   /* ZSTD_CCOMMON_H_MODULE */