ReactOS  0.4.14-dev-998-g623dd26
zstd_internal.h
Go to the documentation of this file.
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 
38 #if defined (__cplusplus)
39 extern "C" {
40 #endif
41 
42 /* ---- static assert (debug) --- */
43 #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
44 
45 
46 /*-*************************************
47 * shared macros
48 ***************************************/
49 #undef MIN
50 #undef MAX
51 #define MIN(a,b) ((a)<(b) ? (a) : (b))
52 #define MAX(a,b) ((a)>(b) ? (a) : (b))
53 #define CHECK_F(f) { size_t const errcod = f; if (ERR_isError(errcod)) return errcod; } /* check and Forward error code */
54 #define CHECK_E(f, e) { size_t const errcod = f; if (ERR_isError(errcod)) return ERROR(e); } /* check and send Error code */
55 
56 
57 /*-*************************************
58 * Common constants
59 ***************************************/
60 #define ZSTD_OPT_NUM (1<<12)
61 
62 #define ZSTD_REP_NUM 3 /* number of repcodes */
63 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1)
64 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
65 
66 #define KB *(1 <<10)
67 #define MB *(1 <<20)
68 #define GB *(1U<<30)
69 
70 #define BIT7 128
71 #define BIT6 64
72 #define BIT5 32
73 #define BIT4 16
74 #define BIT1 2
75 #define BIT0 1
76 
77 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
78 #define ZSTD_WINDOWLOG_DEFAULTMAX 27 /* Default maximum allowed window log */
79 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
80 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
81 
82 #define ZSTD_FRAMEIDSIZE 4 /* magic number size */
83 
84 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
87 
88 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
89 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
90 
91 #define HufLog 12
93 
94 #define LONGNBSEQ 0x7F00
95 
96 #define MINMATCH 3
97 
98 #define Litbits 8
99 #define MaxLit ((1<<Litbits) - 1)
100 #define MaxML 52
101 #define MaxLL 35
102 #define DefaultMaxOff 28
103 #define MaxOff 31
104 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
105 #define MLFSELog 9
106 #define LLFSELog 9
107 #define OffFSELog 8
108 #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
109 
110 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
111  0, 0, 0, 0, 0, 0, 0, 0,
112  1, 1, 1, 1, 2, 2, 3, 3,
113  4, 6, 7, 8, 9,10,11,12,
114  13,14,15,16 };
115 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2,
116  2, 2, 2, 2, 2, 1, 1, 1,
117  2, 2, 2, 2, 2, 2, 2, 2,
118  2, 3, 2, 1, 1, 1, 1, 1,
119  -1,-1,-1,-1 };
120 #define LL_DEFAULTNORMLOG 6 /* for static allocation */
122 
123 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
124  0, 0, 0, 0, 0, 0, 0, 0,
125  0, 0, 0, 0, 0, 0, 0, 0,
126  0, 0, 0, 0, 0, 0, 0, 0,
127  1, 1, 1, 1, 2, 2, 3, 3,
128  4, 4, 5, 7, 8, 9,10,11,
129  12,13,14,15,16 };
130 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2,
131  2, 1, 1, 1, 1, 1, 1, 1,
132  1, 1, 1, 1, 1, 1, 1, 1,
133  1, 1, 1, 1, 1, 1, 1, 1,
134  1, 1, 1, 1, 1, 1, 1, 1,
135  1, 1, 1, 1, 1, 1,-1,-1,
136  -1,-1,-1,-1,-1 };
137 #define ML_DEFAULTNORMLOG 6 /* for static allocation */
139 
140 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2,
141  2, 1, 1, 1, 1, 1, 1, 1,
142  1, 1, 1, 1, 1, 1, 1, 1,
143  -1,-1,-1,-1,-1 };
144 #define OF_DEFAULTNORMLOG 5 /* for static allocation */
146 
147 
148 /*-*******************************************
149 * Shared functions to include for inlining
150 *********************************************/
151 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
152 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
153 
156 #define WILDCOPY_OVERLENGTH 8
157 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
158 {
159  const BYTE* ip = (const BYTE*)src;
160  BYTE* op = (BYTE*)dst;
161  BYTE* const oend = op + length;
162  do
163  COPY8(op, ip)
164  while (op < oend);
165 }
166 
167 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 */
168 {
169  const BYTE* ip = (const BYTE*)src;
170  BYTE* op = (BYTE*)dst;
171  BYTE* const oend = (BYTE*)dstEnd;
172  do
173  COPY8(op, ip)
174  while (op < oend);
175 }
176 
177 
178 /*-*******************************************
179 * Private declarations
180 *********************************************/
181 typedef struct seqDef_s {
185 } seqDef;
186 
187 typedef struct {
195  size_t maxNbSeq;
196  size_t maxNbLit;
197  U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
199 } seqStore_t;
200 
201 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */
202 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
203 
204 /* custom memory allocation functions */
205 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
206 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
207 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
208 
209 
210 MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */
211 {
212  assert(val != 0);
213  {
214 # if defined(_MSC_VER) /* Visual */
215  unsigned long r=0;
216  _BitScanReverse(&r, val);
217  return (unsigned)r;
218 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */
219  return 31 - __builtin_clz(val);
220 # else /* Software version */
221  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 };
222  U32 v = val;
223  v |= v >> 1;
224  v |= v >> 2;
225  v |= v >> 4;
226  v |= v >> 8;
227  v |= v >> 16;
228  return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
229 # endif
230  }
231 }
232 
233 
234 /* ZSTD_invalidateRepCodes() :
235  * ensures next compression will not use repcodes from previous block.
236  * Note : only works with regular variant;
237  * do not use with extDict variant ! */
238 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
239 
240 
241 typedef struct {
246 
249 /* Used by: decompress, fullbench (does not get its definition from here) */
250 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
251  blockProperties_t* bpPtr);
252 
253 #if defined (__cplusplus)
254 }
255 #endif
256 
257 #endif /* ZSTD_CCOMMON_H_MODULE */
unsigned short U16
Definition: mem.h:72
symbolEncodingType_e
Definition: zstd_internal.h:92
U16 matchLength
static void ZSTD_copy8(void *dst, const void *src)
void * ZSTD_calloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:59
#define LL_DEFAULTNORMLOG
blockType_e blockType
BYTE * ofCode
void ZSTD_invalidateRepCodes(ZSTD_CCtx *cctx)
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
static const U32 LL_bits[MaxLL+1]
blockType_e
Definition: zstd_internal.h:86
#define U(x)
Definition: wordpad.c:46
#define OF_DEFAULTNORMLOG
unsigned int U32
Definition: mem.h:77
#define assert(x)
Definition: debug.h:53
static const U32 ML_defaultNormLog
seqDef * sequencesStart
void * ZSTD_malloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:54
void ZSTD_seqToCodes(const seqStore_t *seqStorePtr)
static const S16 LL_defaultNorm[MaxLL+1]
static const size_t ZSTD_fcs_fieldSize[4]
Definition: zstd_internal.h:79
static const size_t ZSTD_blockHeaderSize
Definition: zstd_internal.h:85
seqDef * sequences
static PVOID ptr
Definition: dispmode.c:27
#define DefaultMaxOff
MEM_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
static const U32 repStartValue[ZSTD_REP_NUM]
Definition: zstd_internal.h:64
static const U32 OF_defaultNormLog
#define MaxML
GLuint GLfloat * val
Definition: glext.h:7180
#define ML_DEFAULTNORMLOG
#define ZSTD_BLOCKHEADERSIZE
Definition: zstd_internal.h:84
#define MEM_STATIC
Definition: mem.h:39
GLsizeiptr size
Definition: glext.h:5919
Definition: dhcpd.h:61
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
static const size_t ZSTD_did_fieldSize[4]
Definition: zstd_internal.h:80
static const U32 LL_defaultNormLog
size_t maxNbSeq
const seqStore_t * ZSTD_getSeqStore(const ZSTD_CCtx *ctx)
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
unsigned char BYTE
Definition: mem.h:68
GLenum src
Definition: glext.h:6340
BYTE * mlCode
static const S16 OF_defaultNorm[DefaultMaxOff+1]
size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
const GLdouble * v
Definition: gl.h:2040
static const S16 ML_defaultNorm[MaxML+1]
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
#define COPY8(d, s)
GLenum GLenum dst
Definition: glext.h:6340
static const U32 ML_bits[MaxML+1]
MEM_STATIC void ZSTD_wildcopy_e(void *dst, const void *src, void *dstEnd)
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
MEM_STATIC U32 ZSTD_highbit32(U32 val)
#define MaxLL
signed short S16
Definition: mem.h:73
void ZSTD_free(void *ptr, ZSTD_customMem customMem)
Definition: zstd_common.c:68
BYTE * llCode
UINT op
Definition: effect.c:223
struct seqDef_s seqDef
size_t maxNbLit
#define ZSTD_REP_NUM
Definition: zstd_internal.h:62
BYTE * litStart