zstd_compress.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308
  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. #ifndef ZSTD_COMPRESS_H
  11. #define ZSTD_COMPRESS_H
  12. /*-*************************************
  13. * Dependencies
  14. ***************************************/
  15. #include "zstd_internal.h"
  16. #ifdef ZSTD_MULTITHREAD
  17. # include "zstdmt_compress.h"
  18. #endif
  19. #if defined (__cplusplus)
  20. extern "C" {
  21. #endif
  22. /*-*************************************
  23. * Constants
  24. ***************************************/
  25. static const U32 g_searchStrength = 8;
  26. #define HASH_READ_SIZE 8
  27. /*-*************************************
  28. * Context memory management
  29. ***************************************/
  30. typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
  31. typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
  32. typedef struct ZSTD_prefixDict_s {
  33. const void* dict;
  34. size_t dictSize;
  35. ZSTD_dictMode_e dictMode;
  36. } ZSTD_prefixDict;
  37. struct ZSTD_CCtx_s {
  38. const BYTE* nextSrc; /* next block here to continue on current prefix */
  39. const BYTE* base; /* All regular indexes relative to this position */
  40. const BYTE* dictBase; /* extDict indexes relative to this position */
  41. U32 dictLimit; /* below that point, need extDict */
  42. U32 lowLimit; /* below that point, no more data */
  43. U32 nextToUpdate; /* index from which to continue dictionary update */
  44. U32 nextToUpdate3; /* index from which to continue dictionary update */
  45. U32 hashLog3; /* dispatch table : larger == faster, more memory */
  46. U32 loadedDictEnd; /* index of end of dictionary */
  47. ZSTD_compressionStage_e stage;
  48. U32 dictID;
  49. ZSTD_CCtx_params requestedParams;
  50. ZSTD_CCtx_params appliedParams;
  51. void* workSpace;
  52. size_t workSpaceSize;
  53. size_t blockSize;
  54. U64 pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
  55. U64 consumedSrcSize;
  56. XXH64_state_t xxhState;
  57. ZSTD_customMem customMem;
  58. size_t staticSize;
  59. seqStore_t seqStore; /* sequences storage ptrs */
  60. optState_t optState;
  61. ldmState_t ldmState; /* long distance matching state */
  62. U32* hashTable;
  63. U32* hashTable3;
  64. U32* chainTable;
  65. ZSTD_entropyCTables_t* entropy;
  66. /* streaming */
  67. char* inBuff;
  68. size_t inBuffSize;
  69. size_t inToCompress;
  70. size_t inBuffPos;
  71. size_t inBuffTarget;
  72. char* outBuff;
  73. size_t outBuffSize;
  74. size_t outBuffContentSize;
  75. size_t outBuffFlushedSize;
  76. ZSTD_cStreamStage streamStage;
  77. U32 frameEnded;
  78. /* Dictionary */
  79. ZSTD_CDict* cdictLocal;
  80. const ZSTD_CDict* cdict;
  81. ZSTD_prefixDict prefixDict; /* single-usage dictionary */
  82. /* Multi-threading */
  83. #ifdef ZSTD_MULTITHREAD
  84. ZSTDMT_CCtx* mtctx;
  85. #endif
  86. };
  87. static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
  88. 8, 9, 10, 11, 12, 13, 14, 15,
  89. 16, 16, 17, 17, 18, 18, 19, 19,
  90. 20, 20, 20, 20, 21, 21, 21, 21,
  91. 22, 22, 22, 22, 22, 22, 22, 22,
  92. 23, 23, 23, 23, 23, 23, 23, 23,
  93. 24, 24, 24, 24, 24, 24, 24, 24,
  94. 24, 24, 24, 24, 24, 24, 24, 24 };
  95. static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
  96. 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
  97. 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
  98. 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
  99. 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
  100. 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
  101. 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
  102. 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
  103. /*! ZSTD_storeSeq() :
  104. Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
  105. `offsetCode` : distance to match, or 0 == repCode.
  106. `matchCode` : matchLength - MINMATCH
  107. */
  108. MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t matchCode)
  109. {
  110. #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG >= 6)
  111. static const BYTE* g_start = NULL;
  112. U32 const pos = (U32)((const BYTE*)literals - g_start);
  113. if (g_start==NULL) g_start = (const BYTE*)literals;
  114. if ((pos > 0) && (pos < 1000000000))
  115. DEBUGLOG(6, "Cpos %6u :%5u literals & match %3u bytes at distance %6u",
  116. pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);
  117. #endif
  118. /* copy Literals */
  119. assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + 128 KB);
  120. ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
  121. seqStorePtr->lit += litLength;
  122. /* literal Length */
  123. if (litLength>0xFFFF) {
  124. seqStorePtr->longLengthID = 1;
  125. seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
  126. }
  127. seqStorePtr->sequences[0].litLength = (U16)litLength;
  128. /* match offset */
  129. seqStorePtr->sequences[0].offset = offsetCode + 1;
  130. /* match Length */
  131. if (matchCode>0xFFFF) {
  132. seqStorePtr->longLengthID = 2;
  133. seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
  134. }
  135. seqStorePtr->sequences[0].matchLength = (U16)matchCode;
  136. seqStorePtr->sequences++;
  137. }
  138. /*-*************************************
  139. * Match length counter
  140. ***************************************/
  141. static unsigned ZSTD_NbCommonBytes (register size_t val)
  142. {
  143. if (MEM_isLittleEndian()) {
  144. if (MEM_64bits()) {
  145. # if defined(_MSC_VER) && defined(_WIN64)
  146. unsigned long r = 0;
  147. _BitScanForward64( &r, (U64)val );
  148. return (unsigned)(r>>3);
  149. # elif defined(__GNUC__) && (__GNUC__ >= 4)
  150. return (__builtin_ctzll((U64)val) >> 3);
  151. # else
  152. static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
  153. 0, 3, 1, 3, 1, 4, 2, 7,
  154. 0, 2, 3, 6, 1, 5, 3, 5,
  155. 1, 3, 4, 4, 2, 5, 6, 7,
  156. 7, 0, 1, 2, 3, 3, 4, 6,
  157. 2, 6, 5, 5, 3, 4, 5, 6,
  158. 7, 1, 2, 4, 6, 4, 4, 5,
  159. 7, 2, 6, 5, 7, 6, 7, 7 };
  160. return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
  161. # endif
  162. } else { /* 32 bits */
  163. # if defined(_MSC_VER)
  164. unsigned long r=0;
  165. _BitScanForward( &r, (U32)val );
  166. return (unsigned)(r>>3);
  167. # elif defined(__GNUC__) && (__GNUC__ >= 3)
  168. return (__builtin_ctz((U32)val) >> 3);
  169. # else
  170. static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
  171. 3, 2, 2, 1, 3, 2, 0, 1,
  172. 3, 3, 1, 2, 2, 2, 2, 0,
  173. 3, 1, 2, 0, 1, 0, 1, 1 };
  174. return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
  175. # endif
  176. }
  177. } else { /* Big Endian CPU */
  178. if (MEM_64bits()) {
  179. # if defined(_MSC_VER) && defined(_WIN64)
  180. unsigned long r = 0;
  181. _BitScanReverse64( &r, val );
  182. return (unsigned)(r>>3);
  183. # elif defined(__GNUC__) && (__GNUC__ >= 4)
  184. return (__builtin_clzll(val) >> 3);
  185. # else
  186. unsigned r;
  187. const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
  188. if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
  189. if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
  190. r += (!val);
  191. return r;
  192. # endif
  193. } else { /* 32 bits */
  194. # if defined(_MSC_VER)
  195. unsigned long r = 0;
  196. _BitScanReverse( &r, (unsigned long)val );
  197. return (unsigned)(r>>3);
  198. # elif defined(__GNUC__) && (__GNUC__ >= 3)
  199. return (__builtin_clz((U32)val) >> 3);
  200. # else
  201. unsigned r;
  202. if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
  203. r += (!val);
  204. return r;
  205. # endif
  206. } }
  207. }
  208. MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
  209. {
  210. const BYTE* const pStart = pIn;
  211. const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
  212. while (pIn < pInLoopLimit) {
  213. size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
  214. if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
  215. pIn += ZSTD_NbCommonBytes(diff);
  216. return (size_t)(pIn - pStart);
  217. }
  218. if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
  219. if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
  220. if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
  221. return (size_t)(pIn - pStart);
  222. }
  223. /** ZSTD_count_2segments() :
  224. * can count match length with `ip` & `match` in 2 different segments.
  225. * convention : on reaching mEnd, match count continue starting from iStart
  226. */
  227. MEM_STATIC size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
  228. {
  229. const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
  230. size_t const matchLength = ZSTD_count(ip, match, vEnd);
  231. if (match + matchLength != mEnd) return matchLength;
  232. return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
  233. }
  234. /*-*************************************
  235. * Hashes
  236. ***************************************/
  237. static const U32 prime3bytes = 506832829U;
  238. static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
  239. MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
  240. static const U32 prime4bytes = 2654435761U;
  241. static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
  242. static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
  243. static const U64 prime5bytes = 889523592379ULL;
  244. static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
  245. static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
  246. static const U64 prime6bytes = 227718039650203ULL;
  247. static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
  248. static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
  249. static const U64 prime7bytes = 58295818150454627ULL;
  250. static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
  251. static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
  252. static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
  253. static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
  254. static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
  255. MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
  256. {
  257. switch(mls)
  258. {
  259. default:
  260. case 4: return ZSTD_hash4Ptr(p, hBits);
  261. case 5: return ZSTD_hash5Ptr(p, hBits);
  262. case 6: return ZSTD_hash6Ptr(p, hBits);
  263. case 7: return ZSTD_hash7Ptr(p, hBits);
  264. case 8: return ZSTD_hash8Ptr(p, hBits);
  265. }
  266. }
  267. #if defined (__cplusplus)
  268. }
  269. #endif
  270. #endif /* ZSTD_COMPRESS_H */