ReactOS  0.4.15-dev-4869-g35a816a
zstd_internal.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016-2020, 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 #ifdef __aarch64__
23 #include <arm_neon.h>
24 #endif
25 #include "compiler.h"
26 #include "mem.h"
27 #include "debug.h" /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
28 #include "error_private.h"
29 #define ZSTD_STATIC_LINKING_ONLY
30 #include "zstd.h"
31 #define FSE_STATIC_LINKING_ONLY
32 #include "fse.h"
33 #define HUF_STATIC_LINKING_ONLY
34 #include "huf.h"
35 #ifndef XXH_STATIC_LINKING_ONLY
36 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
37 #endif
38 #include "../xxhash.h" /* XXH_reset, update, digest */
39 
40 #if defined (__cplusplus)
41 extern "C" {
42 #endif
43 
44 /* ---- static assert (debug) --- */
45 #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
46 #define ZSTD_isError ERR_isError /* for inlining */
47 #define FSE_isError ERR_isError
48 #define HUF_isError ERR_isError
49 
50 
51 /*-*************************************
52 * shared macros
53 ***************************************/
54 #undef MIN
55 #undef MAX
56 #define MIN(a,b) ((a)<(b) ? (a) : (b))
57 #define MAX(a,b) ((a)>(b) ? (a) : (b))
58 
69 void _force_has_format_string(const char *format, ...) {
70  (void)format;
71 }
72 
79 #define _FORCE_HAS_FORMAT_STRING(...) \
80  if (0) { \
81  _force_has_format_string(__VA_ARGS__); \
82  }
83 
91 #define RETURN_ERROR_IF(cond, err, ...) \
92  if (cond) { \
93  RAWLOG(3, "%s:%d: ERROR!: check %s failed, returning %s", \
94  __FILE__, __LINE__, ZSTD_QUOTE(cond), ZSTD_QUOTE(ERROR(err))); \
95  _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \
96  RAWLOG(3, ": " __VA_ARGS__); \
97  RAWLOG(3, "\n"); \
98  return ERROR(err); \
99  }
100 
106 #define RETURN_ERROR(err, ...) \
107  do { \
108  RAWLOG(3, "%s:%d: ERROR!: unconditional check failed, returning %s", \
109  __FILE__, __LINE__, ZSTD_QUOTE(ERROR(err))); \
110  _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \
111  RAWLOG(3, ": " __VA_ARGS__); \
112  RAWLOG(3, "\n"); \
113  return ERROR(err); \
114  } while(0);
115 
121 #define FORWARD_IF_ERROR(err, ...) \
122  do { \
123  size_t const err_code = (err); \
124  if (ERR_isError(err_code)) { \
125  RAWLOG(3, "%s:%d: ERROR!: forwarding error in %s: %s", \
126  __FILE__, __LINE__, ZSTD_QUOTE(err), ERR_getErrorName(err_code)); \
127  _FORCE_HAS_FORMAT_STRING(__VA_ARGS__); \
128  RAWLOG(3, ": " __VA_ARGS__); \
129  RAWLOG(3, "\n"); \
130  return err_code; \
131  } \
132  } while(0);
133 
134 
135 /*-*************************************
136 * Common constants
137 ***************************************/
138 #define ZSTD_OPT_NUM (1<<12)
139 
140 #define ZSTD_REP_NUM 3 /* number of repcodes */
141 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1)
142 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
143 
144 #define KB *(1 <<10)
145 #define MB *(1 <<20)
146 #define GB *(1U<<30)
147 
148 #define BIT7 128
149 #define BIT6 64
150 #define BIT5 32
151 #define BIT4 16
152 #define BIT1 2
153 #define BIT0 1
154 
155 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
156 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
157 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
158 
159 #define ZSTD_FRAMEIDSIZE 4 /* magic number size */
160 
161 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
164 
165 #define ZSTD_FRAMECHECKSUMSIZE 4
166 
167 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
168 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
169 
170 #define HufLog 12
172 
173 #define LONGNBSEQ 0x7F00
174 
175 #define MINMATCH 3
176 
177 #define Litbits 8
178 #define MaxLit ((1<<Litbits) - 1)
179 #define MaxML 52
180 #define MaxLL 35
181 #define DefaultMaxOff 28
182 #define MaxOff 31
183 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
184 #define MLFSELog 9
185 #define LLFSELog 9
186 #define OffFSELog 8
187 #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
188 
189 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
190  0, 0, 0, 0, 0, 0, 0, 0,
191  1, 1, 1, 1, 2, 2, 3, 3,
192  4, 6, 7, 8, 9,10,11,12,
193  13,14,15,16 };
194 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2,
195  2, 2, 2, 2, 2, 1, 1, 1,
196  2, 2, 2, 2, 2, 2, 2, 2,
197  2, 3, 2, 1, 1, 1, 1, 1,
198  -1,-1,-1,-1 };
199 #define LL_DEFAULTNORMLOG 6 /* for static allocation */
201 
202 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
203  0, 0, 0, 0, 0, 0, 0, 0,
204  0, 0, 0, 0, 0, 0, 0, 0,
205  0, 0, 0, 0, 0, 0, 0, 0,
206  1, 1, 1, 1, 2, 2, 3, 3,
207  4, 4, 5, 7, 8, 9,10,11,
208  12,13,14,15,16 };
209 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2,
210  2, 1, 1, 1, 1, 1, 1, 1,
211  1, 1, 1, 1, 1, 1, 1, 1,
212  1, 1, 1, 1, 1, 1, 1, 1,
213  1, 1, 1, 1, 1, 1, 1, 1,
214  1, 1, 1, 1, 1, 1,-1,-1,
215  -1,-1,-1,-1,-1 };
216 #define ML_DEFAULTNORMLOG 6 /* for static allocation */
218 
219 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2,
220  2, 1, 1, 1, 1, 1, 1, 1,
221  1, 1, 1, 1, 1, 1, 1, 1,
222  -1,-1,-1,-1,-1 };
223 #define OF_DEFAULTNORMLOG 5 /* for static allocation */
225 
226 
227 /*-*******************************************
228 * Shared functions to include for inlining
229 *********************************************/
230 static void ZSTD_copy8(void* dst, const void* src) {
231 #ifdef __aarch64__
232  vst1_u8((uint8_t*)dst, vld1_u8((const uint8_t*)src));
233 #else
234  memcpy(dst, src, 8);
235 #endif
236 }
237 
238 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
239 static void ZSTD_copy16(void* dst, const void* src) {
240 #ifdef __aarch64__
241  vst1q_u8((uint8_t*)dst, vld1q_u8((const uint8_t*)src));
242 #else
243  memcpy(dst, src, 16);
244 #endif
245 }
246 #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; }
247 
248 #define WILDCOPY_OVERLENGTH 32
249 #define WILDCOPY_VECLEN 16
250 
251 typedef enum {
254  /* ZSTD_overlap_dst_before_src, */
256 
265 void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
266 {
267  ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src;
268  const BYTE* ip = (const BYTE*)src;
269  BYTE* op = (BYTE*)dst;
270  BYTE* const oend = op + length;
271 
272  assert(diff >= 8 || (ovtype == ZSTD_no_overlap && diff <= -WILDCOPY_VECLEN));
273 
274  if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
275  /* Handle short offset copies. */
276  do {
277  COPY8(op, ip)
278  } while (op < oend);
279  } else {
280  assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN);
281  /* Separate out the first COPY16() call because the copy length is
282  * almost certain to be short, so the branches have different
283  * probabilities. Since it is almost certain to be short, only do
284  * one COPY16() in the first call. Then, do two calls per loop since
285  * at that point it is more likely to have a high trip count.
286  */
287 #ifndef __aarch64__
288  do {
289  COPY16(op, ip);
290  }
291  while (op < oend);
292 #else
293  COPY16(op, ip);
294  if (op >= oend) return;
295  do {
296  COPY16(op, ip);
297  COPY16(op, ip);
298  }
299  while (op < oend);
300 #endif
301  }
302 }
303 
304 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
305 {
306  size_t const length = MIN(dstCapacity, srcSize);
307  if (length > 0) {
308  memcpy(dst, src, length);
309  }
310  return length;
311 }
312 
313 /* define "workspace is too large" as this number of times larger than needed */
314 #define ZSTD_WORKSPACETOOLARGE_FACTOR 3
315 
316 /* when workspace is continuously too large
317  * during at least this number of times,
318  * context's memory usage is considered wasteful,
319  * because it's sized to handle a worst case scenario which rarely happens.
320  * In which case, resize it down to free some memory */
321 #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128
322 
323 
324 /*-*******************************************
325 * Private declarations
326 *********************************************/
327 typedef struct seqDef_s {
331 } seqDef;
332 
333 typedef struct {
341  size_t maxNbSeq;
342  size_t maxNbLit;
343  U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
345 } seqStore_t;
346 
347 typedef struct {
351 
357 {
358  ZSTD_sequenceLength seqLen;
359  seqLen.litLength = seq->litLength;
360  seqLen.matchLength = seq->matchLength + MINMATCH;
361  if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) {
362  if (seqStore->longLengthID == 1) {
363  seqLen.litLength += 0xFFFF;
364  }
365  if (seqStore->longLengthID == 2) {
366  seqLen.matchLength += 0xFFFF;
367  }
368  }
369  return seqLen;
370 }
371 
378 typedef struct {
380  unsigned long long decompressedBound;
381 } ZSTD_frameSizeInfo; /* decompress & legacy */
382 
383 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */
384 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
385 
386 /* custom memory allocation functions */
387 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
388 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
389 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
390 
391 
392 MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */
393 {
394  assert(val != 0);
395  {
396 # if defined(_MSC_VER) /* Visual */
397  unsigned long r=0;
398  return _BitScanReverse(&r, val) ? (unsigned)r : 0;
399 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */
400  return __builtin_clz (val) ^ 31;
401 # elif defined(__ICCARM__) /* IAR Intrinsic */
402  return 31 - __CLZ(val);
403 # else /* Software version */
404  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 };
405  U32 v = val;
406  v |= v >> 1;
407  v |= v >> 2;
408  v |= v >> 4;
409  v |= v >> 8;
410  v |= v >> 16;
411  return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
412 # endif
413  }
414 }
415 
416 
417 /* ZSTD_invalidateRepCodes() :
418  * ensures next compression will not use repcodes from previous block.
419  * Note : only works with regular variant;
420  * do not use with extDict variant ! */
421 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
422 
423 
424 typedef struct {
428 } blockProperties_t; /* declared here for decompress and fullbench */
429 
432 /* Used by: decompress, fullbench (does not get its definition from here) */
433 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
434  blockProperties_t* bpPtr);
435 
438 /* Used by: decompress, fullbench (does not get its definition from here) */
439 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
440  const void* src, size_t srcSize);
441 
442 
443 #if defined (__cplusplus)
444 }
445 #endif
446 
447 #endif /* ZSTD_CCOMMON_H_MODULE */
MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const *seqStore, seqDef const *seq)
symbolEncodingType_e
static INLINE_KEYWORD UNUSED_ATTR void _force_has_format_string(const char *format,...)
Definition: zstd_internal.h:69
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
U16 matchLength
static void ZSTD_copy8(void *dst, const void *src)
void * ZSTD_calloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:61
#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
MEM_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
#define U(x)
Definition: wordpad.c:45
size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void *src, size_t srcSize)
#define OF_DEFAULTNORMLOG
#define FORCE_INLINE_ATTR
Definition: xxhash.c:169
#define assert(x)
Definition: debug.h:53
static const U32 ML_defaultNormLog
seqDef * sequencesStart
unsigned long long decompressedBound
GLint GLint GLsizei GLsizei GLsizei GLint GLenum format
Definition: gl.h:1546
void * ZSTD_malloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:56
void ZSTD_seqToCodes(const seqStore_t *seqStorePtr)
static const S16 LL_defaultNorm[MaxLL+1]
static const size_t ZSTD_fcs_fieldSize[4]
static const size_t ZSTD_blockHeaderSize
seqDef * sequences
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
#define WILDCOPY_VECLEN
static PVOID ptr
Definition: dispmode.c:27
#define DefaultMaxOff
static const U32 repStartValue[ZSTD_REP_NUM]
static const U32 OF_defaultNormLog
#define MaxML
#define MIN(a, b)
Definition: zstd_internal.h:56
GLuint GLfloat * val
Definition: glext.h:7180
#define ML_DEFAULTNORMLOG
#define ZSTD_BLOCKHEADERSIZE
#define MEM_STATIC
Definition: mem.h:39
GLsizeiptr size
Definition: glext.h:5919
Definition: dhcpd.h:61
MEM_STATIC FORCE_INLINE_ATTR void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
static void ZSTD_copy16(void *dst, const void *src)
static const size_t ZSTD_did_fieldSize[4]
UINT op
Definition: effect.c:236
static const U32 LL_defaultNormLog
#define INLINE_KEYWORD
Definition: xxhash.c:161
size_t maxNbSeq
const seqStore_t * ZSTD_getSeqStore(const ZSTD_CCtx *ctx)
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum src
Definition: glext.h:6340
BYTE * mlCode
BYTE uint8_t
Definition: msvideo1.c:66
unsigned char BYTE
Definition: xxhash.c:193
static const S16 OF_defaultNorm[DefaultMaxOff+1]
size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
unsigned short U16
Definition: xxhash.c:194
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]
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
MEM_STATIC U32 ZSTD_highbit32(U32 val)
#define MaxLL
ZSTD_overlap_e
#define MINMATCH
signed short S16
Definition: mem.h:146
void ZSTD_free(void *ptr, ZSTD_customMem customMem)
Definition: zstd_common.c:70
BYTE * llCode
struct seqDef_s seqDef
size_t maxNbLit
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_REP_NUM
#define COPY16(d, s)
static unsigned(__cdecl *hash_bstr)(bstr_t s)
BYTE * litStart
#define UNUSED_ATTR
Definition: compiler.h:68