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