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 #define ZSTD_isError ERR_isError   /* for inlining */
45 #define FSE_isError  ERR_isError
46 #define HUF_isError  ERR_isError
47 
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))
56 #define CHECK_F(f) { size_t const errcod = f; if (ERR_isError(errcod)) return errcod; }  /* check and Forward error code */
57 #define CHECK_E(f, e) { size_t const errcod = f; if (ERR_isError(errcod)) return ERROR(e); }  /* check and send Error code */
58 
59 
60 /*-*************************************
61 *  Common constants
62 ***************************************/
63 #define ZSTD_OPT_NUM    (1<<12)
64 
65 #define ZSTD_REP_NUM      3                 /* number of repcodes */
66 #define ZSTD_REP_MOVE     (ZSTD_REP_NUM-1)
67 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
68 
69 #define KB *(1 <<10)
70 #define MB *(1 <<20)
71 #define GB *(1U<<30)
72 
73 #define BIT7 128
74 #define BIT6  64
75 #define BIT5  32
76 #define BIT4  16
77 #define BIT1   2
78 #define BIT0   1
79 
80 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
81 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
82 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
83 
84 #define ZSTD_FRAMEIDSIZE 4   /* magic number size */
85 
86 #define ZSTD_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
87 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
88 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
89 
90 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
91 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
92 
93 #define HufLog 12
94 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
95 
96 #define LONGNBSEQ 0x7F00
97 
98 #define MINMATCH 3
99 
100 #define Litbits  8
101 #define MaxLit ((1<<Litbits) - 1)
102 #define MaxML   52
103 #define MaxLL   35
104 #define DefaultMaxOff 28
105 #define MaxOff  31
106 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
107 #define MLFSELog    9
108 #define LLFSELog    9
109 #define OffFSELog   8
110 #define MaxFSELog  MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
111 
112 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
113                                       0, 0, 0, 0, 0, 0, 0, 0,
114                                       1, 1, 1, 1, 2, 2, 3, 3,
115                                       4, 6, 7, 8, 9,10,11,12,
116                                      13,14,15,16 };
117 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2,
118                                              2, 2, 2, 2, 2, 1, 1, 1,
119                                              2, 2, 2, 2, 2, 2, 2, 2,
120                                              2, 3, 2, 1, 1, 1, 1, 1,
121                                             -1,-1,-1,-1 };
122 #define LL_DEFAULTNORMLOG 6  /* for static allocation */
123 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
124 
125 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0,
126                                       0, 0, 0, 0, 0, 0, 0, 0,
127                                       0, 0, 0, 0, 0, 0, 0, 0,
128                                       0, 0, 0, 0, 0, 0, 0, 0,
129                                       1, 1, 1, 1, 2, 2, 3, 3,
130                                       4, 4, 5, 7, 8, 9,10,11,
131                                      12,13,14,15,16 };
132 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2,
133                                              2, 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, 1, 1, 1,
137                                              1, 1, 1, 1, 1, 1,-1,-1,
138                                             -1,-1,-1,-1,-1 };
139 #define ML_DEFAULTNORMLOG 6  /* for static allocation */
140 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
141 
142 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2,
143                                                      2, 1, 1, 1, 1, 1, 1, 1,
144                                                      1, 1, 1, 1, 1, 1, 1, 1,
145                                                     -1,-1,-1,-1,-1 };
146 #define OF_DEFAULTNORMLOG 5  /* for static allocation */
147 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
148 
149 
150 /*-*******************************************
151 *  Shared functions to include for inlining
152 *********************************************/
153 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
154 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
155 
156 /*! ZSTD_wildcopy() :
157  *  custom version of memcpy(), can overwrite up to WILDCOPY_OVERLENGTH bytes (if length==0) */
158 #define WILDCOPY_OVERLENGTH 8
159 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
160 {
161     const BYTE* ip = (const BYTE*)src;
162     BYTE* op = (BYTE*)dst;
163     BYTE* const oend = op + length;
164     do
165         COPY8(op, ip)
166     while (op < oend);
167 }
168 
169 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 */
170 {
171     const BYTE* ip = (const BYTE*)src;
172     BYTE* op = (BYTE*)dst;
173     BYTE* const oend = (BYTE*)dstEnd;
174     do
175         COPY8(op, ip)
176     while (op < oend);
177 }
178 
179 
180 /*-*******************************************
181 *  Private declarations
182 *********************************************/
183 typedef struct seqDef_s {
184     U32 offset;
185     U16 litLength;
186     U16 matchLength;
187 } seqDef;
188 
189 typedef struct {
190     seqDef* sequencesStart;
191     seqDef* sequences;
192     BYTE* litStart;
193     BYTE* lit;
194     BYTE* llCode;
195     BYTE* mlCode;
196     BYTE* ofCode;
197     size_t maxNbSeq;
198     size_t maxNbLit;
199     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
200     U32   longLengthPos;
201 } seqStore_t;
202 
203 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);   /* compress & dictBuilder */
204 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);   /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
205 
206 /* custom memory allocation functions */
207 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
208 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
209 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
210 
211 
212 MEM_STATIC U32 ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
213 {
214     assert(val != 0);
215     {
216 #   if defined(_MSC_VER)   /* Visual */
217         unsigned long r=0;
218         _BitScanReverse(&r, val);
219         return (unsigned)r;
220 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* GCC Intrinsic */
221         return 31 - __builtin_clz(val);
222 #   else   /* Software version */
223         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 };
224         U32 v = val;
225         v |= v >> 1;
226         v |= v >> 2;
227         v |= v >> 4;
228         v |= v >> 8;
229         v |= v >> 16;
230         return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
231 #   endif
232     }
233 }
234 
235 
236 /* ZSTD_invalidateRepCodes() :
237  * ensures next compression will not use repcodes from previous block.
238  * Note : only works with regular variant;
239  *        do not use with extDict variant ! */
240 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);   /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
241 
242 
243 typedef struct {
244     blockType_e blockType;
245     U32 lastBlock;
246     U32 origSize;
247 } blockProperties_t;   /* declared here for decompress and fullbench */
248 
249 /*! ZSTD_getcBlockSize() :
250  *  Provides the size of compressed block from block header `src` */
251 /* Used by: decompress, fullbench (does not get its definition from here) */
252 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
253                           blockProperties_t* bpPtr);
254 
255 /*! ZSTD_decodeSeqHeaders() :
256  *  decode sequence header from src */
257 /* Used by: decompress, fullbench (does not get its definition from here) */
258 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
259                        const void* src, size_t srcSize);
260 
261 
262 #if defined (__cplusplus)
263 }
264 #endif
265 
266 #endif   /* ZSTD_CCOMMON_H_MODULE */
267