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 144 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 145 0, 0, 0, 0, 0, 0, 0, 0, 146 1, 1, 1, 1, 2, 2, 3, 3, 147 4, 6, 7, 8, 9,10,11,12, 148 13,14,15,16 }; 149 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 150 2, 2, 2, 2, 2, 1, 1, 1, 151 2, 2, 2, 2, 2, 2, 2, 2, 152 2, 3, 2, 1, 1, 1, 1, 1, 153 -1,-1,-1,-1 }; 154 #define LL_DEFAULTNORMLOG 6 /* for static allocation */ 155 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; 156 157 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 158 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 1, 1, 1, 1, 2, 2, 3, 3, 162 4, 4, 5, 7, 8, 9,10,11, 163 12,13,14,15,16 }; 164 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 165 2, 1, 1, 1, 1, 1, 1, 1, 166 1, 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 }; 171 #define ML_DEFAULTNORMLOG 6 /* for static allocation */ 172 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; 173 174 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 175 2, 1, 1, 1, 1, 1, 1, 1, 176 1, 1, 1, 1, 1, 1, 1, 1, 177 -1,-1,-1,-1,-1 }; 178 #define OF_DEFAULTNORMLOG 5 /* for static allocation */ 179 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; 180 181 182 /*-******************************************* 183 * Shared functions to include for inlining 184 *********************************************/ 185 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 186 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 187 188 /*! ZSTD_wildcopy() : 189 * custom version of memcpy(), can overwrite up to WILDCOPY_OVERLENGTH bytes (if length==0) */ 190 #define WILDCOPY_OVERLENGTH 8 191 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 192 { 193 const BYTE* ip = (const BYTE*)src; 194 BYTE* op = (BYTE*)dst; 195 BYTE* const oend = op + length; 196 do 197 COPY8(op, ip) 198 while (op < oend); 199 } 200 201 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 */ 202 { 203 const BYTE* ip = (const BYTE*)src; 204 BYTE* op = (BYTE*)dst; 205 BYTE* const oend = (BYTE*)dstEnd; 206 do 207 COPY8(op, ip) 208 while (op < oend); 209 } 210 211 212 /*-******************************************* 213 * Private declarations 214 *********************************************/ 215 typedef struct seqDef_s { 216 U32 offset; 217 U16 litLength; 218 U16 matchLength; 219 } seqDef; 220 221 typedef struct { 222 seqDef* sequencesStart; 223 seqDef* sequences; 224 BYTE* litStart; 225 BYTE* lit; 226 BYTE* llCode; 227 BYTE* mlCode; 228 BYTE* ofCode; 229 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ 230 U32 longLengthPos; 231 U32 rep[ZSTD_REP_NUM]; 232 U32 repToConfirm[ZSTD_REP_NUM]; 233 } seqStore_t; 234 235 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */ 236 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */ 237 238 /* custom memory allocation functions */ 239 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem); 240 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem); 241 void ZSTD_free(void* ptr, ZSTD_customMem customMem); 242 243 244 MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */ 245 { 246 assert(val != 0); 247 { 248 # if defined(_MSC_VER) /* Visual */ 249 unsigned long r=0; 250 _BitScanReverse(&r, val); 251 return (unsigned)r; 252 # elif defined(__GNUC__) && (__GNUC__ >= 3) && __has_builtin(__builtin_clz) /* GCC Intrinsic */ 253 return 31 - __builtin_clz(val); 254 # else /* Software version */ 255 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 }; 256 U32 v = val; 257 v |= v >> 1; 258 v |= v >> 2; 259 v |= v >> 4; 260 v |= v >> 8; 261 v |= v >> 16; 262 return DeBruijnClz[(v * 0x07C4ACDDU) >> 27]; 263 # endif 264 } 265 } 266 267 268 /* ZSTD_invalidateRepCodes() : 269 * ensures next compression will not use repcodes from previous block. 270 * Note : only works with regular variant; 271 * do not use with extDict variant ! */ 272 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */ 273 274 275 typedef struct { 276 blockType_e blockType; 277 U32 lastBlock; 278 U32 origSize; 279 } blockProperties_t; 280 281 /*! ZSTD_getcBlockSize() : 282 * Provides the size of compressed block from block header `src` */ 283 /* Used by: decompress, fullbench (does not get its definition from here) */ 284 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, 285 blockProperties_t* bpPtr); 286 287 #if defined (__cplusplus) 288 } 289 #endif 290 291 #endif /* ZSTD_CCOMMON_H_MODULE */ 292