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 */
85 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
86 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
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
92 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
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 */
121 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
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 */
138 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
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 */
145 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
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 
154 /*! ZSTD_wildcopy() :
155  *  custom version of memcpy(), can overwrite up to WILDCOPY_OVERLENGTH bytes (if length==0) */
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 {
182     U32 offset;
183     U16 litLength;
184     U16 matchLength;
185 } seqDef;
186 
187 typedef struct {
188     seqDef* sequencesStart;
189     seqDef* sequences;
190     BYTE* litStart;
191     BYTE* lit;
192     BYTE* llCode;
193     BYTE* mlCode;
194     BYTE* ofCode;
195     size_t maxNbSeq;
196     size_t maxNbLit;
197     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
198     U32   longLengthPos;
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 {
242     blockType_e blockType;
243     U32 lastBlock;
244     U32 origSize;
245 } blockProperties_t;
246 
247 /*! ZSTD_getcBlockSize() :
248  *  Provides the size of compressed block from block header `src` */
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 */
258