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