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 the BSD-style license found in the
   6  * LICENSE file in the root directory of this source tree. An additional grant
   7  * of patent rights can be found in the PATENTS file in the same directory.
   8  */
   9
  10 #ifndef ZSTD_CCOMMON_H_MODULE
  11 #define ZSTD_CCOMMON_H_MODULE
  12
  13 /*-*******************************************************
  14 *  Compiler specifics
  15 *********************************************************/
  16 #ifdef _MSC_VER    /* Visual Studio */
  17 #  define FORCE_INLINE static __forceinline
  18 #  include <intrin.h>                    /* For Visual 2005 */
  19 #  pragma warning(disable : 4100)        /* disable: C4100: unreferenced formal parameter */
  20 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
  21 #  pragma warning(disable : 4204)        /* disable: C4204: non-constant aggregate initializer */
  22 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
  23 #else
  24 #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
  25 #    ifdef __GNUC__
  26 #      define FORCE_INLINE static inline __attribute__((always_inline))
  27 #    else
  28 #      define FORCE_INLINE static inline
  29 #    endif
  30 #  else
  31 #    define FORCE_INLINE static
  32 #  endif /* __STDC_VERSION__ */
  33 #endif
  34
  35 #ifdef _MSC_VER
  36 #  define FORCE_NOINLINE static __declspec(noinline)
  37 #else
  38 #  ifdef __GNUC__
  39 #    define FORCE_NOINLINE static __attribute__((__noinline__))
  40 #  else
  41 #    define FORCE_NOINLINE static
  42 #  endif
  43 #endif
  44
  45
  46 /*-*************************************
  47 *  Dependencies
  48 ***************************************/
  49 #include "mem.h"
  50 #include "error_private.h"
  51 #define ZSTD_STATIC_LINKING_ONLY
  52 #include "zstd.h"
  53 #ifndef XXH_STATIC_LINKING_ONLY
  54 #  define XXH_STATIC_LINKING_ONLY  /* XXH64_state_t */
  55 #endif
  56 #include "xxhash.h"                /* XXH_reset, update, digest */
  57
  58
  59 /*-*************************************
  60 *  Debug
  61 ***************************************/
  62 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
  63 #  include <assert.h>
  64 #else
  65 #  ifndef assert
  66 #    define assert(condition) ((void)0)
  67 #  endif
  68 #endif
  69
  70 #define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; }
  71
  72 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=2)
  73 #  include <stdio.h>
  74 /* recommended values for ZSTD_DEBUG display levels :
  75  * 1 : no display, enables assert() only
  76  * 2 : reserved for currently active debugging path
  77  * 3 : events once per object lifetime (CCtx, CDict)
  78  * 4 : events once per frame
  79  * 5 : events once per block
  80  * 6 : events once per sequence (*very* verbose) */
  81 #  define DEBUGLOG(l, ...) {                         \
  82                 if (l<=ZSTD_DEBUG) {                 \
  83                     fprintf(stderr, __FILE__ ": ");  \
  84                     fprintf(stderr, __VA_ARGS__);    \
  85                     fprintf(stderr, " \n");          \
  86             }   }
  87 #else
  88 #  define DEBUGLOG(l, ...)      {}    /* disabled */
  89 #endif
  90
  91
  92 /*-*************************************
  93 *  shared macros
  94 ***************************************/
  95 #undef MIN
  96 #undef MAX
  97 #define MIN(a,b) ((a)<(b) ? (a) : (b))
  98 #define MAX(a,b) ((a)>(b) ? (a) : (b))
  99 #define CHECK_F(f) { size_t const errcod = f; if (ERR_isError(errcod)) return errcod; }  /* check and Forward error code */
 100 #define CHECK_E(f, e) { size_t const errcod = f; if (ERR_isError(errcod)) return ERROR(e); }  /* check and send Error code */
 101
 102
 103 /*-*************************************
 104 *  Common constants
 105 ***************************************/
 106 #define ZSTD_OPT_NUM    (1<<12)
 107
 108 #define ZSTD_REP_NUM      3                 /* number of repcodes */
 109 #define ZSTD_REP_CHECK    (ZSTD_REP_NUM)    /* number of repcodes to check by the optimal parser */
 110 #define ZSTD_REP_MOVE     (ZSTD_REP_NUM-1)
 111 #define ZSTD_REP_MOVE_OPT (ZSTD_REP_NUM)
 112 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
 113
 114 #define KB *(1 <<10)
 115 #define MB *(1 <<20)
 116 #define GB *(1U<<30)
 117
 118 #define BIT7 128
 119 #define BIT6  64
 120 #define BIT5  32
 121 #define BIT4  16
 122 #define BIT1   2
 123 #define BIT0   1
 124
 125 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
 126 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
 127 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
 128
 129 #define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
 130 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
 131 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
 132
 133 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
 134 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
 135
 136 #define HufLog 12
 137 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
 138
 139 #define LONGNBSEQ 0x7F00
 140
 141 #define MINMATCH 3
 142
 143 #define Litbits  8
 144 #define MaxLit ((1<<Litbits) - 1)
 145 #define MaxML  52
 146 #define MaxLL  35
 147 #define MaxOff 28
 148 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
 149 #define MLFSELog    9
 150 #define LLFSELog    9
 151 #define OffFSELog   8
 152
 153 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 154                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
 155                                      13,14,15,16 };
 156 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
 157                                              2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
 158                                             -1,-1,-1,-1 };
 159 #define LL_DEFAULTNORMLOG 6  /* for static allocation */
 160 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
 161
 162 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 163                                       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 164                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
 165                                      12,13,14,15,16 };
 166 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
 167                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 168                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
 169                                             -1,-1,-1,-1,-1 };
 170 #define ML_DEFAULTNORMLOG 6  /* for static allocation */
 171 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
 172
 173 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
 174                                               1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
 175 #define OF_DEFAULTNORMLOG 5  /* for static allocation */
 176 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
 177
 178
 179 /*-*******************************************
 180 *  Shared functions to include for inlining
 181 *********************************************/
 182 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
 183 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
 184
 185 /*! ZSTD_wildcopy() :
 186 *   custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
 187 #define WILDCOPY_OVERLENGTH 8
 188 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
 189 {
 190     const BYTE* ip = (const BYTE*)src;
 191     BYTE* op = (BYTE*)dst;
 192     BYTE* const oend = op + length;
 193     do
 194         COPY8(op, ip)
 195     while (op < oend);
 196 }
 197
 198 MEM_STATIC void ZSTD_wildcopy_e(void* dst, const void* src, void* dstEnd)   /* should be faster for decoding, but strangely, not verified on all platform */
 199 {
 200     const BYTE* ip = (const BYTE*)src;
 201     BYTE* op = (BYTE*)dst;
 202     BYTE* const oend = (BYTE*)dstEnd;
 203     do
 204         COPY8(op, ip)
 205     while (op < oend);
 206 }
 207
 208
 209 /*-*******************************************
 210 *  Private interfaces
 211 *********************************************/
 212 typedef struct ZSTD_stats_s ZSTD_stats_t;
 213
 214 typedef struct {
 215     U32 off;
 216     U32 len;
 217 } ZSTD_match_t;
 218
 219 typedef struct {
 220     U32 price;
 221     U32 off;
 222     U32 mlen;
 223     U32 litlen;
 224     U32 rep[ZSTD_REP_NUM];
 225 } ZSTD_optimal_t;
 226
 227
 228 typedef struct seqDef_s {
 229     U32 offset;
 230     U16 litLength;
 231     U16 matchLength;
 232 } seqDef;
 233
 234
 235 typedef struct {
 236     seqDef* sequencesStart;
 237     seqDef* sequences;
 238     BYTE* litStart;
 239     BYTE* lit;
 240     BYTE* llCode;
 241     BYTE* mlCode;
 242     BYTE* ofCode;
 243     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
 244     U32   longLengthPos;
 245     /* opt */
 246     ZSTD_optimal_t* priceTable;
 247     ZSTD_match_t* matchTable;
 248     U32* matchLengthFreq;
 249     U32* litLengthFreq;
 250     U32* litFreq;
 251     U32* offCodeFreq;
 252     U32  matchLengthSum;
 253     U32  matchSum;
 254     U32  litLengthSum;
 255     U32  litSum;
 256     U32  offCodeSum;
 257     U32  log2matchLengthSum;
 258     U32  log2matchSum;
 259     U32  log2litLengthSum;
 260     U32  log2litSum;
 261     U32  log2offCodeSum;
 262     U32  factor;
 263     U32  staticPrices;
 264     U32  cachedPrice;
 265     U32  cachedLitLength;
 266     const BYTE* cachedLiterals;
 267 } seqStore_t;
 268
 269 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);
 270 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);
 271
 272 /* custom memory allocation functions */
 273 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
 274 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
 275 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
 276
 277
 278 /*======  common function  ======*/
 279
 280 MEM_STATIC U32 ZSTD_highbit32(U32 val)
 281 {
 282 #   if defined(_MSC_VER)   /* Visual */
 283     unsigned long r=0;
 284     _BitScanReverse(&r, val);
 285     return (unsigned)r;
 286 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* GCC Intrinsic */
 287     return 31 - __builtin_clz(val);
 288 #   else   /* Software version */
 289     static const int 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 };
 290     U32 v = val;
 291     int r;
 292     v |= v >> 1;
 293     v |= v >> 2;
 294     v |= v >> 4;
 295     v |= v >> 8;
 296     v |= v >> 16;
 297     r = DeBruijnClz[(U32)(v * 0x07C4ACDDU) >> 27];
 298     return r;
 299 #   endif
 300 }
 301
 302
 303 /* hidden functions */
 304
 305 /* ZSTD_invalidateRepCodes() :
 306  * ensures next compression will not use repcodes from previous block.
 307  * Note : only works with regular variant;
 308  *        do not use with extDict variant ! */
 309 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);
 310
 311
 312 /*! ZSTD_initCStream_internal() :
 313  *  Private use only. Init streaming operation.
 314  *  expects params to be valid.
 315  *  must receive dict, or cdict, or none, but not both.
 316  *  @return : 0, or an error code */
 317 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
 318                      const void* dict, size_t dictSize,
 319                      const ZSTD_CDict* cdict,
 320                      ZSTD_parameters params, unsigned long long pledgedSrcSize);
 321
 322 /*! ZSTD_compressStream_generic() :
 323  *  Private use only. To be called from zstdmt_compress.c in single-thread mode. */
 324 size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
 325                                    ZSTD_outBuffer* output,
 326                                    ZSTD_inBuffer* input,
 327                                    ZSTD_EndDirective const flushMode);
 328
 329 /*! ZSTD_getParamsFromCDict() :
 330  *  as the name implies */
 331 ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict* cdict);
 332
 333
 334 #endif   /* ZSTD_CCOMMON_H_MODULE */