xref: /freebsd/sys/contrib/zstd/lib/common/zstd_internal.h (revision 4f52dfbb8d6c4d446500c5b097e3806ec219fbd4)
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)
38 extern "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>
57 extern 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)
98 static 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 */
113 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
114 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
115 
116 #define ZSTD_FRAMEIDSIZE 4
117 static 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 */
120 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
121 typedef 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
127 typedef 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 
145 static 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 };
150 static 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 */
156 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
157 
158 static 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 };
165 static 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 */
173 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
174 
175 static 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 */
180 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
181 
182 
183 /*-*******************************************
184 *  Shared functions to include for inlining
185 *********************************************/
186 static 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
192 MEM_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 
202 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 */
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 *********************************************/
216 typedef struct seqDef_s {
217     U32 offset;
218     U16 litLength;
219     U16 matchLength;
220 } seqDef;
221 
222 typedef 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 
234 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx);   /* compress & dictBuilder */
235 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr);   /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
236 
237 /* custom memory allocation functions */
238 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem);
239 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem);
240 void ZSTD_free(void* ptr, ZSTD_customMem customMem);
241 
242 
243 MEM_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) && __has_builtin(__builtin_clz)   /* 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 ! */
271 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx);   /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
272 
273 
274 typedef 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) */
283 size_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