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 57 /** 58 * Return the specified error if the condition evaluates to true. 59 * 60 * In debug modes, prints additional information. In order to do that 61 * (particularly, printing the conditional that failed), this can't just wrap 62 * RETURN_ERROR(). 63 */ 64 #define RETURN_ERROR_IF(cond, err, ...) \ 65 if (cond) { \ 66 RAWLOG(3, "%s:%d: ERROR!: check %s failed, returning %s", __FILE__, __LINE__, ZSTD_QUOTE(cond), ZSTD_QUOTE(ERROR(err))); \ 67 RAWLOG(3, ": " __VA_ARGS__); \ 68 RAWLOG(3, "\n"); \ 69 return ERROR(err); \ 70 } 71 72 /** 73 * Unconditionally return the specified error. 74 * 75 * In debug modes, prints additional information. 76 */ 77 #define RETURN_ERROR(err, ...) \ 78 do { \ 79 RAWLOG(3, "%s:%d: ERROR!: unconditional check failed, returning %s", __FILE__, __LINE__, ZSTD_QUOTE(ERROR(err))); \ 80 RAWLOG(3, ": " __VA_ARGS__); \ 81 RAWLOG(3, "\n"); \ 82 return ERROR(err); \ 83 } while(0); 84 85 /** 86 * If the provided expression evaluates to an error code, returns that error code. 87 * 88 * In debug modes, prints additional information. 89 */ 90 #define FORWARD_IF_ERROR(err, ...) \ 91 do { \ 92 size_t const err_code = (err); \ 93 if (ERR_isError(err_code)) { \ 94 RAWLOG(3, "%s:%d: ERROR!: forwarding error in %s: %s", __FILE__, __LINE__, ZSTD_QUOTE(err), ERR_getErrorName(err_code)); \ 95 RAWLOG(3, ": " __VA_ARGS__); \ 96 RAWLOG(3, "\n"); \ 97 return err_code; \ 98 } \ 99 } while(0); 100 101 102 /*-************************************* 103 * Common constants 104 ***************************************/ 105 #define ZSTD_OPT_NUM (1<<12) 106 107 #define ZSTD_REP_NUM 3 /* number of repcodes */ 108 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1) 109 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 }; 110 111 #define KB *(1 <<10) 112 #define MB *(1 <<20) 113 #define GB *(1U<<30) 114 115 #define BIT7 128 116 #define BIT6 64 117 #define BIT5 32 118 #define BIT4 16 119 #define BIT1 2 120 #define BIT0 1 121 122 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10 123 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 }; 124 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 }; 125 126 #define ZSTD_FRAMEIDSIZE 4 /* magic number size */ 127 128 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */ 129 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE; 130 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e; 131 132 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ 133 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ 134 135 #define HufLog 12 136 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e; 137 138 #define LONGNBSEQ 0x7F00 139 140 #define MINMATCH 3 141 142 #define Litbits 8 143 #define MaxLit ((1<<Litbits) - 1) 144 #define MaxML 52 145 #define MaxLL 35 146 #define DefaultMaxOff 28 147 #define MaxOff 31 148 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ 149 #define MLFSELog 9 150 #define LLFSELog 9 151 #define OffFSELog 8 152 #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog) 153 154 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 155 0, 0, 0, 0, 0, 0, 0, 0, 156 1, 1, 1, 1, 2, 2, 3, 3, 157 4, 6, 7, 8, 9,10,11,12, 158 13,14,15,16 }; 159 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 160 2, 2, 2, 2, 2, 1, 1, 1, 161 2, 2, 2, 2, 2, 2, 2, 2, 162 2, 3, 2, 1, 1, 1, 1, 1, 163 -1,-1,-1,-1 }; 164 #define LL_DEFAULTNORMLOG 6 /* for static allocation */ 165 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; 166 167 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 168 0, 0, 0, 0, 0, 0, 0, 0, 169 0, 0, 0, 0, 0, 0, 0, 0, 170 0, 0, 0, 0, 0, 0, 0, 0, 171 1, 1, 1, 1, 2, 2, 3, 3, 172 4, 4, 5, 7, 8, 9,10,11, 173 12,13,14,15,16 }; 174 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 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, 1, 1, 1, 178 1, 1, 1, 1, 1, 1, 1, 1, 179 1, 1, 1, 1, 1, 1,-1,-1, 180 -1,-1,-1,-1,-1 }; 181 #define ML_DEFAULTNORMLOG 6 /* for static allocation */ 182 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; 183 184 static const S16 OF_defaultNorm[DefaultMaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 185 2, 1, 1, 1, 1, 1, 1, 1, 186 1, 1, 1, 1, 1, 1, 1, 1, 187 -1,-1,-1,-1,-1 }; 188 #define OF_DEFAULTNORMLOG 5 /* for static allocation */ 189 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; 190 191 192 /*-******************************************* 193 * Shared functions to include for inlining 194 *********************************************/ 195 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 196 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 197 198 /*! ZSTD_wildcopy() : 199 * custom version of memcpy(), can overwrite up to WILDCOPY_OVERLENGTH bytes (if length==0) */ 200 #define WILDCOPY_OVERLENGTH 8 201 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 202 { 203 const BYTE* ip = (const BYTE*)src; 204 BYTE* op = (BYTE*)dst; 205 BYTE* const oend = op + length; 206 do 207 COPY8(op, ip) 208 while (op < oend); 209 } 210 211 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 */ 212 { 213 const BYTE* ip = (const BYTE*)src; 214 BYTE* op = (BYTE*)dst; 215 BYTE* const oend = (BYTE*)dstEnd; 216 do 217 COPY8(op, ip) 218 while (op < oend); 219 } 220 221 222 /*-******************************************* 223 * Private declarations 224 *********************************************/ 225 typedef struct seqDef_s { 226 U32 offset; 227 U16 litLength; 228 U16 matchLength; 229 } seqDef; 230 231 typedef struct { 232 seqDef* sequencesStart; 233 seqDef* sequences; 234 BYTE* litStart; 235 BYTE* lit; 236 BYTE* llCode; 237 BYTE* mlCode; 238 BYTE* ofCode; 239 size_t maxNbSeq; 240 size_t maxNbLit; 241 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ 242 U32 longLengthPos; 243 } seqStore_t; 244 245 /** 246 * Contains the compressed frame size and an upper-bound for the decompressed frame size. 247 * Note: before using `compressedSize`, check for errors using ZSTD_isError(). 248 * similarly, before using `decompressedBound`, check for errors using: 249 * `decompressedBound != ZSTD_CONTENTSIZE_ERROR` 250 */ 251 typedef struct { 252 size_t compressedSize; 253 unsigned long long decompressedBound; 254 } ZSTD_frameSizeInfo; /* decompress & legacy */ 255 256 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */ 257 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */ 258 259 /* custom memory allocation functions */ 260 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem); 261 void* ZSTD_calloc(size_t size, ZSTD_customMem customMem); 262 void ZSTD_free(void* ptr, ZSTD_customMem customMem); 263 264 265 MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */ 266 { 267 assert(val != 0); 268 { 269 # if defined(_MSC_VER) /* Visual */ 270 unsigned long r=0; 271 _BitScanReverse(&r, val); 272 return (unsigned)r; 273 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */ 274 return 31 - __builtin_clz(val); 275 # else /* Software version */ 276 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 }; 277 U32 v = val; 278 v |= v >> 1; 279 v |= v >> 2; 280 v |= v >> 4; 281 v |= v >> 8; 282 v |= v >> 16; 283 return DeBruijnClz[(v * 0x07C4ACDDU) >> 27]; 284 # endif 285 } 286 } 287 288 289 /* ZSTD_invalidateRepCodes() : 290 * ensures next compression will not use repcodes from previous block. 291 * Note : only works with regular variant; 292 * do not use with extDict variant ! */ 293 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */ 294 295 296 typedef struct { 297 blockType_e blockType; 298 U32 lastBlock; 299 U32 origSize; 300 } blockProperties_t; /* declared here for decompress and fullbench */ 301 302 /*! ZSTD_getcBlockSize() : 303 * Provides the size of compressed block from block header `src` */ 304 /* Used by: decompress, fullbench (does not get its definition from here) */ 305 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, 306 blockProperties_t* bpPtr); 307 308 /*! ZSTD_decodeSeqHeaders() : 309 * decode sequence header from src */ 310 /* Used by: decompress, fullbench (does not get its definition from here) */ 311 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr, 312 const void* src, size_t srcSize); 313 314 315 #if defined (__cplusplus) 316 } 317 #endif 318 319 #endif /* ZSTD_CCOMMON_H_MODULE */ 320