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 : 4127)        /* disable: C4127: conditional expression is constant */
  20 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
  21 #  pragma warning(disable : 4100)        /* disable: C4100: unreferenced formal parameter */
  22 #else
  23 #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
  24 #    ifdef __GNUC__
  25 #      define FORCE_INLINE static inline __attribute__((always_inline))
  26 #    else
  27 #      define FORCE_INLINE static inline
  28 #    endif
  29 #  else
  30 #    define FORCE_INLINE static
  31 #  endif /* __STDC_VERSION__ */
  32 #endif
  33
  34 #ifdef _MSC_VER
  35 #  define FORCE_NOINLINE static __declspec(noinline)
  36 #else
  37 #  ifdef __GNUC__
  38 #    define FORCE_NOINLINE static __attribute__((__noinline__))
  39 #  else
  40 #    define FORCE_NOINLINE static
  41 #  endif
  42 #endif
  43
  44
  45 /*-*************************************
  46 *  Dependencies
  47 ***************************************/
  48 #include "mem.h"
  49 #include "error_private.h"
  50 #define ZSTD_STATIC_LINKING_ONLY
  51 #include "zstd.h"
  52 #ifndef XXH_STATIC_LINKING_ONLY
  53 #  define XXH_STATIC_LINKING_ONLY   /* XXH64_state_t */
  54 #endif
  55 #include "xxhash.h"               /* XXH_reset, update, digest */
  56
  57
  58 /*-*************************************
  59 *  shared macros
  60 ***************************************/
  61 #define MIN(a,b) ((a)<(b) ? (a) : (b))
  62 #define MAX(a,b) ((a)>(b) ? (a) : (b))
  63 #define CHECK_F(f) { size_t const errcod = f; if (ERR_isError(errcod)) return errcod; }  /* check and Forward error code */
  64 #define CHECK_E(f, e) { size_t const errcod = f; if (ERR_isError(errcod)) return ERROR(e); }  /* check and send Error code */
  65
  66
  67 /*-*************************************
  68 *  Common constants
  69 ***************************************/
  70 #define ZSTD_OPT_NUM    (1<<12)
  71 #define ZSTD_DICT_MAGIC  0xEC30A437   /* v0.7+ */
  72
  73 #define ZSTD_REP_NUM      3                 /* number of repcodes */
  74 #define ZSTD_REP_CHECK    (ZSTD_REP_NUM)    /* number of repcodes to check by the optimal parser */
  75 #define ZSTD_REP_MOVE     (ZSTD_REP_NUM-1)
  76 #define ZSTD_REP_MOVE_OPT (ZSTD_REP_NUM)
  77 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
  78
  79 #define KB *(1 <<10)
  80 #define MB *(1 <<20)
  81 #define GB *(1U<<30)
  82
  83 #define BIT7 128
  84 #define BIT6  64
  85 #define BIT5  32
  86 #define BIT4  16
  87 #define BIT1   2
  88 #define BIT0   1
  89
  90 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
  91 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
  92 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
  93
  94 #define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
  95 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
  96 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
  97
  98 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
  99 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
 100
 101 #define HufLog 12
 102 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
 103
 104 #define LONGNBSEQ 0x7F00
 105
 106 #define MINMATCH 3
 107 #define EQUAL_READ32 4
 108
 109 #define Litbits  8
 110 #define MaxLit ((1<<Litbits) - 1)
 111 #define MaxML  52
 112 #define MaxLL  35
 113 #define MaxOff 28
 114 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
 115 #define MLFSELog    9
 116 #define LLFSELog    9
 117 #define OffFSELog   8
 118
 119 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 120                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
 121                                      13,14,15,16 };
 122 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
 123                                              2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
 124                                             -1,-1,-1,-1 };
 125 #define LL_DEFAULTNORMLOG 6  /* for static allocation */
 126 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
 127
 128 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 129                                       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 130                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
 131                                      12,13,14,15,16 };
 132 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
 133                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 134                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
 135                                             -1,-1,-1,-1,-1 };
 136 #define ML_DEFAULTNORMLOG 6  /* for static allocation */
 137 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
 138
 139 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
 140                                               1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
 141 #define OF_DEFAULTNORMLOG 5  /* for static allocation */
 142 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
 143
 144
 145 /*-*******************************************
 146 *  Shared functions to include for inlining
 147 *********************************************/
 148 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
 149 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
 150
 151 /*! ZSTD_wildcopy() :
 152 *   custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
 153 #define WILDCOPY_OVERLENGTH 8
 154 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
 155 {
 156     const BYTE* ip = (const BYTE*)src;
 157     BYTE* op = (BYTE*)dst;
 158     BYTE* const oend = op + length;
 159     do
 160         COPY8(op, ip)
 161     while (op < oend);
 162 }
 163
 164 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 */
 165 {
 166     const BYTE* ip = (const BYTE*)src;
 167     BYTE* op = (BYTE*)dst;
 168     BYTE* const oend = (BYTE*)dstEnd;
 169     do
 170         COPY8(op, ip)
 171     while (op < oend);
 172 }
 173
 174
 175 /*-*******************************************
 176 *  Private interfaces
 177 *********************************************/
 178 typedef struct ZSTD_stats_s ZSTD_stats_t;
 179
 180 typedef struct {
 181     U32 off;
 182     U32 len;
 183 } ZSTD_match_t;
 184
 185 typedef struct {
 186     U32 price;
 187     U32 off;
 188     U32 mlen;
 189     U32 litlen;
 190     U32 rep[ZSTD_REP_NUM];
 191 } ZSTD_optimal_t;
 192
 193
 194 typedef struct seqDef_s {
 195     U32 offset;
 196     U16 litLength;
 197     U16 matchLength;
 198 } seqDef;
 199
 200
 201 typedef struct {
 202     seqDef* sequencesStart;
 203     seqDef* sequences;
 204     BYTE* litStart;
 205     BYTE* lit;
 206     BYTE* llCode;
 207     BYTE* mlCode;
 208     BYTE* ofCode;
 209     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
 210     U32   longLengthPos;
 211     /* opt */
 212     ZSTD_optimal_t* priceTable;
 213     ZSTD_match_t* matchTable;
 214     U32* matchLengthFreq;
 215     U32* litLengthFreq;
 216     U32* litFreq;
 217     U32* offCodeFreq;
 218     U32  matchLengthSum;
 219     U32  matchSum;
 220     U32  litLengthSum;
 221     U32  litSum;
 222     U32  offCodeSum;
 223     U32  log2matchLengthSum;
 224     U32  log2matchSum;
 225     U32  log2litLengthSum;
 226     U32  log2litSum;
 227     U32  log2offCodeSum;
 228     U32  factor;
 229     U32  staticPrices;
 230     U32  cachedPrice;
 231     U32  cachedLitLength;
 232     const BYTE* cachedLiterals;
 233 } seqStore_t;
 234
 235 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);
 236 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);
 237 int ZSTD_isSkipFrame(ZSTD_DCtx* dctx);
 238
 239 /* custom memory allocation functions */
 240 void* ZSTD_defaultAllocFunction(void* opaque, size_t size);
 241 void ZSTD_defaultFreeFunction(void* opaque, void* address);
 242 #ifndef ZSTD_DLL_IMPORT
 243 static const ZSTD_customMem defaultCustomMem = { ZSTD_defaultAllocFunction, ZSTD_defaultFreeFunction, NULL };
 244 #endif
 245 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
 246 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
 247
 248
 249 /*======  common function  ======*/
 250
 251 MEM_STATIC U32 ZSTD_highbit32(U32 val)
 252 {
 253 #   if defined(_MSC_VER)   /* Visual */
 254     unsigned long r=0;
 255     _BitScanReverse(&r, val);
 256     return (unsigned)r;
 257 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* GCC Intrinsic */
 258     return 31 - __builtin_clz(val);
 259 #   else   /* Software version */
 260     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 };
 261     U32 v = val;
 262     int r;
 263     v |= v >> 1;
 264     v |= v >> 2;
 265     v |= v >> 4;
 266     v |= v >> 8;
 267     v |= v >> 16;
 268     r = DeBruijnClz[(U32)(v * 0x07C4ACDDU) >> 27];
 269     return r;
 270 #   endif
 271 }
 272
 273
 274 /* hidden functions */
 275
 276 /* ZSTD_invalidateRepCodes() :
 277  * ensures next compression will not use repcodes from previous block.
 278  * Note : only works with regular variant;
 279  *        do not use with extDict variant ! */
 280 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);
 281
 282
 283 #endif   /* ZSTD_CCOMMON_H_MODULE */