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