blob: 31f756ab581235c2ffadc07c2847f94ebfd6d13d [file] [log] [blame]
William Kurkianea869482019-04-09 15:16:11 -04001/*
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"
Abhilash S.L3b494632019-07-16 15:51:09 +053024#include "debug.h" /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
William Kurkianea869482019-04-09 15:16:11 -040025#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)
39extern "C" {
40#endif
41
Abhilash S.L3b494632019-07-16 15:51:09 +053042/* ---- static assert (debug) --- */
43#define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
44#define ZSTD_isError ERR_isError /* for inlining */
45#define FSE_isError ERR_isError
46#define HUF_isError ERR_isError
William Kurkianea869482019-04-09 15:16:11 -040047
48
49/*-*************************************
50* shared macros
51***************************************/
52#undef MIN
53#undef MAX
54#define MIN(a,b) ((a)<(b) ? (a) : (b))
55#define MAX(a,b) ((a)>(b) ? (a) : (b))
Abhilash S.L3b494632019-07-16 15:51:09 +053056
57/**
58 * Return the specified error if the condition evaluates to true.
59 *
60 * In debug modes, prints additional information. In order to do that
61 * (particularly, printing the conditional that failed), this can't just wrap
62 * RETURN_ERROR().
63 */
64#define RETURN_ERROR_IF(cond, err, ...) \
65 if (cond) { \
66 RAWLOG(3, "%s:%d: ERROR!: check %s failed, returning %s", __FILE__, __LINE__, ZSTD_QUOTE(cond), ZSTD_QUOTE(ERROR(err))); \
67 RAWLOG(3, ": " __VA_ARGS__); \
68 RAWLOG(3, "\n"); \
69 return ERROR(err); \
70 }
71
72/**
73 * Unconditionally return the specified error.
74 *
75 * In debug modes, prints additional information.
76 */
77#define RETURN_ERROR(err, ...) \
78 do { \
79 RAWLOG(3, "%s:%d: ERROR!: unconditional check failed, returning %s", __FILE__, __LINE__, ZSTD_QUOTE(ERROR(err))); \
80 RAWLOG(3, ": " __VA_ARGS__); \
81 RAWLOG(3, "\n"); \
82 return ERROR(err); \
83 } while(0);
84
85/**
86 * If the provided expression evaluates to an error code, returns that error code.
87 *
88 * In debug modes, prints additional information.
89 */
90#define FORWARD_IF_ERROR(err, ...) \
91 do { \
92 size_t const err_code = (err); \
93 if (ERR_isError(err_code)) { \
94 RAWLOG(3, "%s:%d: ERROR!: forwarding error in %s: %s", __FILE__, __LINE__, ZSTD_QUOTE(err), ERR_getErrorName(err_code)); \
95 RAWLOG(3, ": " __VA_ARGS__); \
96 RAWLOG(3, "\n"); \
97 return err_code; \
98 } \
99 } while(0);
William Kurkianea869482019-04-09 15:16:11 -0400100
101
102/*-*************************************
103* Common constants
104***************************************/
105#define ZSTD_OPT_NUM (1<<12)
106
107#define ZSTD_REP_NUM 3 /* number of repcodes */
108#define ZSTD_REP_MOVE (ZSTD_REP_NUM-1)
109static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
110
111#define KB *(1 <<10)
112#define MB *(1 <<20)
113#define GB *(1U<<30)
114
115#define BIT7 128
116#define BIT6 64
117#define BIT5 32
118#define BIT4 16
119#define BIT1 2
120#define BIT0 1
121
122#define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
William Kurkianea869482019-04-09 15:16:11 -0400123static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
124static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
125
Abhilash S.L3b494632019-07-16 15:51:09 +0530126#define ZSTD_FRAMEIDSIZE 4 /* magic number size */
William Kurkianea869482019-04-09 15:16:11 -0400127
128#define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
129static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
130typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
131
132#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
133#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
134
135#define HufLog 12
136typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
137
138#define LONGNBSEQ 0x7F00
139
140#define MINMATCH 3
141
142#define Litbits 8
143#define MaxLit ((1<<Litbits) - 1)
144#define MaxML 52
145#define MaxLL 35
146#define DefaultMaxOff 28
147#define MaxOff 31
148#define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
149#define MLFSELog 9
150#define LLFSELog 9
151#define OffFSELog 8
152#define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
153
154static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
155 0, 0, 0, 0, 0, 0, 0, 0,
156 1, 1, 1, 1, 2, 2, 3, 3,
157 4, 6, 7, 8, 9,10,11,12,
158 13,14,15,16 };
159static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2,
160 2, 2, 2, 2, 2, 1, 1, 1,
161 2, 2, 2, 2, 2, 2, 2, 2,
162 2, 3, 2, 1, 1, 1, 1, 1,
163 -1,-1,-1,-1 };
164#define LL_DEFAULTNORMLOG 6 /* for static allocation */
165static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
166
167static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
168 0, 0, 0, 0, 0, 0, 0, 0,
169 0, 0, 0, 0, 0, 0, 0, 0,
170 0, 0, 0, 0, 0, 0, 0, 0,
171 1, 1, 1, 1, 2, 2, 3, 3,
172 4, 4, 5, 7, 8, 9,10,11,
173 12,13,14,15,16 };
174static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2,
175 2, 1, 1, 1, 1, 1, 1, 1,
176 1, 1, 1, 1, 1, 1, 1, 1,
177 1, 1, 1, 1, 1, 1, 1, 1,
178 1, 1, 1, 1, 1, 1, 1, 1,
179 1, 1, 1, 1, 1, 1,-1,-1,
180 -1,-1,-1,-1,-1 };
181#define ML_DEFAULTNORMLOG 6 /* for static allocation */
182static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
183
184static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2,
185 2, 1, 1, 1, 1, 1, 1, 1,
186 1, 1, 1, 1, 1, 1, 1, 1,
187 -1,-1,-1,-1,-1 };
188#define OF_DEFAULTNORMLOG 5 /* for static allocation */
189static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
190
191
192/*-*******************************************
193* Shared functions to include for inlining
194*********************************************/
195static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
196#define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
197
198/*! ZSTD_wildcopy() :
199 * custom version of memcpy(), can overwrite up to WILDCOPY_OVERLENGTH bytes (if length==0) */
200#define WILDCOPY_OVERLENGTH 8
201MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
202{
203 const BYTE* ip = (const BYTE*)src;
204 BYTE* op = (BYTE*)dst;
205 BYTE* const oend = op + length;
206 do
207 COPY8(op, ip)
208 while (op < oend);
209}
210
211MEM_STATIC void ZSTD_wildcopy_e(void* dst, const void* src, void* dstEnd) /* should be faster for decoding, but strangely, not verified on all platform */
212{
213 const BYTE* ip = (const BYTE*)src;
214 BYTE* op = (BYTE*)dst;
215 BYTE* const oend = (BYTE*)dstEnd;
216 do
217 COPY8(op, ip)
218 while (op < oend);
219}
220
221
222/*-*******************************************
223* Private declarations
224*********************************************/
225typedef struct seqDef_s {
226 U32 offset;
227 U16 litLength;
228 U16 matchLength;
229} seqDef;
230
231typedef struct {
232 seqDef* sequencesStart;
233 seqDef* sequences;
234 BYTE* litStart;
235 BYTE* lit;
236 BYTE* llCode;
237 BYTE* mlCode;
238 BYTE* ofCode;
Abhilash S.L3b494632019-07-16 15:51:09 +0530239 size_t maxNbSeq;
240 size_t maxNbLit;
William Kurkianea869482019-04-09 15:16:11 -0400241 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
242 U32 longLengthPos;
243} seqStore_t;
244
Abhilash S.L3b494632019-07-16 15:51:09 +0530245/**
246 * Contains the compressed frame size and an upper-bound for the decompressed frame size.
247 * Note: before using `compressedSize`, check for errors using ZSTD_isError().
248 * similarly, before using `decompressedBound`, check for errors using:
249 * `decompressedBound != ZSTD_CONTENTSIZE_ERROR`
250 */
251typedef struct {
252 size_t compressedSize;
253 unsigned long long decompressedBound;
254} ZSTD_frameSizeInfo; /* decompress & legacy */
255
William Kurkianea869482019-04-09 15:16:11 -0400256const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */
257void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
258
259/* custom memory allocation functions */
260void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
261void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
262void ZSTD_free(void* ptr, ZSTD_customMem customMem);
263
264
265MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */
266{
267 assert(val != 0);
268 {
269# if defined(_MSC_VER) /* Visual */
270 unsigned long r=0;
271 _BitScanReverse(&r, val);
272 return (unsigned)r;
273# elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */
274 return 31 - __builtin_clz(val);
275# else /* Software version */
276 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 };
277 U32 v = val;
278 v |= v >> 1;
279 v |= v >> 2;
280 v |= v >> 4;
281 v |= v >> 8;
282 v |= v >> 16;
283 return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
284# endif
285 }
286}
287
288
289/* ZSTD_invalidateRepCodes() :
290 * ensures next compression will not use repcodes from previous block.
291 * Note : only works with regular variant;
292 * do not use with extDict variant ! */
293void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
294
295
296typedef struct {
297 blockType_e blockType;
298 U32 lastBlock;
299 U32 origSize;
Abhilash S.L3b494632019-07-16 15:51:09 +0530300} blockProperties_t; /* declared here for decompress and fullbench */
William Kurkianea869482019-04-09 15:16:11 -0400301
302/*! ZSTD_getcBlockSize() :
303 * Provides the size of compressed block from block header `src` */
304/* Used by: decompress, fullbench (does not get its definition from here) */
305size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
306 blockProperties_t* bpPtr);
307
Abhilash S.L3b494632019-07-16 15:51:09 +0530308/*! ZSTD_decodeSeqHeaders() :
309 * decode sequence header from src */
310/* Used by: decompress, fullbench (does not get its definition from here) */
311size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
312 const void* src, size_t srcSize);
313
314
William Kurkianea869482019-04-09 15:16:11 -0400315#if defined (__cplusplus)
316}
317#endif
318
319#endif /* ZSTD_CCOMMON_H_MODULE */