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 "error_private.h"
25#define ZSTD_STATIC_LINKING_ONLY
26#include "zstd.h"
27#define FSE_STATIC_LINKING_ONLY
28#include "fse.h"
29#define HUF_STATIC_LINKING_ONLY
30#include "huf.h"
31#ifndef XXH_STATIC_LINKING_ONLY
32# define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
33#endif
34#include "xxhash.h" /* XXH_reset, update, digest */
35
36
37#if defined (__cplusplus)
38extern "C" {
39#endif
40
41
42/*-*************************************
43* Debug
44***************************************/
45#if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
46# include <assert.h>
47#else
48# ifndef assert
49# define assert(condition) ((void)0)
50# endif
51#endif
52
53#define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; }
54
55#if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=2)
56# include <stdio.h>
57extern int g_debuglog_enable;
58/* recommended values for ZSTD_DEBUG display levels :
59 * 1 : no display, enables assert() only
60 * 2 : reserved for currently active debug path
61 * 3 : events once per object lifetime (CCtx, CDict, etc.)
62 * 4 : events once per frame
63 * 5 : events once per block
64 * 6 : events once per sequence (*very* verbose) */
65# define RAWLOG(l, ...) { \
66 if ((g_debuglog_enable) & (l<=ZSTD_DEBUG)) { \
67 fprintf(stderr, __VA_ARGS__); \
68 } }
69# define DEBUGLOG(l, ...) { \
70 if ((g_debuglog_enable) & (l<=ZSTD_DEBUG)) { \
71 fprintf(stderr, __FILE__ ": " __VA_ARGS__); \
72 fprintf(stderr, " \n"); \
73 } }
74#else
75# define RAWLOG(l, ...) {} /* disabled */
76# define DEBUGLOG(l, ...) {} /* disabled */
77#endif
78
79
80/*-*************************************
81* shared macros
82***************************************/
83#undef MIN
84#undef MAX
85#define MIN(a,b) ((a)<(b) ? (a) : (b))
86#define MAX(a,b) ((a)>(b) ? (a) : (b))
87#define CHECK_F(f) { size_t const errcod = f; if (ERR_isError(errcod)) return errcod; } /* check and Forward error code */
88#define CHECK_E(f, e) { size_t const errcod = f; if (ERR_isError(errcod)) return ERROR(e); } /* check and send Error code */
89
90
91/*-*************************************
92* Common constants
93***************************************/
94#define ZSTD_OPT_NUM (1<<12)
95
96#define ZSTD_REP_NUM 3 /* number of repcodes */
97#define ZSTD_REP_MOVE (ZSTD_REP_NUM-1)
98static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
99
100#define KB *(1 <<10)
101#define MB *(1 <<20)
102#define GB *(1U<<30)
103
104#define BIT7 128
105#define BIT6 64
106#define BIT5 32
107#define BIT4 16
108#define BIT1 2
109#define BIT0 1
110
111#define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
112#define ZSTD_WINDOWLOG_DEFAULTMAX 27 /* Default maximum allowed window log */
113static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
114static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
115
116#define ZSTD_FRAMEIDSIZE 4
117static const size_t ZSTD_frameIdSize = ZSTD_FRAMEIDSIZE; /* magic number size */
118
119#define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
120static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
121typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
122
123#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
124#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
125
126#define HufLog 12
127typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
128
129#define LONGNBSEQ 0x7F00
130
131#define MINMATCH 3
132
133#define Litbits 8
134#define MaxLit ((1<<Litbits) - 1)
135#define MaxML 52
136#define MaxLL 35
137#define DefaultMaxOff 28
138#define MaxOff 31
139#define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
140#define MLFSELog 9
141#define LLFSELog 9
142#define OffFSELog 8
143#define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
144
145static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
146 0, 0, 0, 0, 0, 0, 0, 0,
147 1, 1, 1, 1, 2, 2, 3, 3,
148 4, 6, 7, 8, 9,10,11,12,
149 13,14,15,16 };
150static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2,
151 2, 2, 2, 2, 2, 1, 1, 1,
152 2, 2, 2, 2, 2, 2, 2, 2,
153 2, 3, 2, 1, 1, 1, 1, 1,
154 -1,-1,-1,-1 };
155#define LL_DEFAULTNORMLOG 6 /* for static allocation */
156static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
157
158static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
159 0, 0, 0, 0, 0, 0, 0, 0,
160 0, 0, 0, 0, 0, 0, 0, 0,
161 0, 0, 0, 0, 0, 0, 0, 0,
162 1, 1, 1, 1, 2, 2, 3, 3,
163 4, 4, 5, 7, 8, 9,10,11,
164 12,13,14,15,16 };
165static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2,
166 2, 1, 1, 1, 1, 1, 1, 1,
167 1, 1, 1, 1, 1, 1, 1, 1,
168 1, 1, 1, 1, 1, 1, 1, 1,
169 1, 1, 1, 1, 1, 1, 1, 1,
170 1, 1, 1, 1, 1, 1,-1,-1,
171 -1,-1,-1,-1,-1 };
172#define ML_DEFAULTNORMLOG 6 /* for static allocation */
173static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
174
175static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2,
176 2, 1, 1, 1, 1, 1, 1, 1,
177 1, 1, 1, 1, 1, 1, 1, 1,
178 -1,-1,-1,-1,-1 };
179#define OF_DEFAULTNORMLOG 5 /* for static allocation */
180static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
181
182
183/*-*******************************************
184* Shared functions to include for inlining
185*********************************************/
186static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
187#define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
188
189/*! ZSTD_wildcopy() :
190 * custom version of memcpy(), can overwrite up to WILDCOPY_OVERLENGTH bytes (if length==0) */
191#define WILDCOPY_OVERLENGTH 8
192MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
193{
194 const BYTE* ip = (const BYTE*)src;
195 BYTE* op = (BYTE*)dst;
196 BYTE* const oend = op + length;
197 do
198 COPY8(op, ip)
199 while (op < oend);
200}
201
202MEM_STATIC void ZSTD_wildcopy_e(void* dst, const void* src, void* dstEnd) /* should be faster for decoding, but strangely, not verified on all platform */
203{
204 const BYTE* ip = (const BYTE*)src;
205 BYTE* op = (BYTE*)dst;
206 BYTE* const oend = (BYTE*)dstEnd;
207 do
208 COPY8(op, ip)
209 while (op < oend);
210}
211
212
213/*-*******************************************
214* Private declarations
215*********************************************/
216typedef struct seqDef_s {
217 U32 offset;
218 U16 litLength;
219 U16 matchLength;
220} seqDef;
221
222typedef struct {
223 seqDef* sequencesStart;
224 seqDef* sequences;
225 BYTE* litStart;
226 BYTE* lit;
227 BYTE* llCode;
228 BYTE* mlCode;
229 BYTE* ofCode;
230 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
231 U32 longLengthPos;
232} seqStore_t;
233
234const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */
235void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
236
237/* custom memory allocation functions */
238void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
239void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
240void ZSTD_free(void* ptr, ZSTD_customMem customMem);
241
242
243MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */
244{
245 assert(val != 0);
246 {
247# if defined(_MSC_VER) /* Visual */
248 unsigned long r=0;
249 _BitScanReverse(&r, val);
250 return (unsigned)r;
251# elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */
252 return 31 - __builtin_clz(val);
253# else /* Software version */
254 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 };
255 U32 v = val;
256 v |= v >> 1;
257 v |= v >> 2;
258 v |= v >> 4;
259 v |= v >> 8;
260 v |= v >> 16;
261 return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
262# endif
263 }
264}
265
266
267/* ZSTD_invalidateRepCodes() :
268 * ensures next compression will not use repcodes from previous block.
269 * Note : only works with regular variant;
270 * do not use with extDict variant ! */
271void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
272
273
274typedef struct {
275 blockType_e blockType;
276 U32 lastBlock;
277 U32 origSize;
278} blockProperties_t;
279
280/*! ZSTD_getcBlockSize() :
281 * Provides the size of compressed block from block header `src` */
282/* Used by: decompress, fullbench (does not get its definition from here) */
283size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
284 blockProperties_t* bpPtr);
285
286#if defined (__cplusplus)
287}
288#endif
289
290#endif /* ZSTD_CCOMMON_H_MODULE */
291