Project Alice
Loading...
Searching...
No Matches
zstd_compress_superblock.c
Go to the documentation of this file.
1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
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 /*-*************************************
12 * Dependencies
13 ***************************************/
15
16#include "../common/zstd_internal.h" /* ZSTD_getSequenceLength */
17#include "hist.h" /* HIST_countFast_wksp */
18#include "zstd_compress_internal.h" /* ZSTD_[huf|fse|entropy]CTablesMetadata_t */
21
41static size_t
42ZSTD_compressSubBlock_literal(const HUF_CElt* hufTable,
43 const ZSTD_hufCTablesMetadata_t* hufMetadata,
44 const BYTE* literals, size_t litSize,
45 void* dst, size_t dstSize,
46 const int bmi2, int writeEntropy, int* entropyWritten)
47{
48 size_t const header = writeEntropy ? 200 : 0;
49 size_t const lhSize = 3 + (litSize >= (1 KB - header)) + (litSize >= (16 KB - header));
50 BYTE* const ostart = (BYTE*)dst;
51 BYTE* const oend = ostart + dstSize;
52 BYTE* op = ostart + lhSize;
53 U32 const singleStream = lhSize == 3;
54 symbolEncodingType_e hType = writeEntropy ? hufMetadata->hType : set_repeat;
55 size_t cLitSize = 0;
56
57 DEBUGLOG(5, "ZSTD_compressSubBlock_literal (litSize=%zu, lhSize=%zu, writeEntropy=%d)", litSize, lhSize, writeEntropy);
58
59 *entropyWritten = 0;
60 if (litSize == 0 || hufMetadata->hType == set_basic) {
61 DEBUGLOG(5, "ZSTD_compressSubBlock_literal using raw literal");
62 return ZSTD_noCompressLiterals(dst, dstSize, literals, litSize);
63 } else if (hufMetadata->hType == set_rle) {
64 DEBUGLOG(5, "ZSTD_compressSubBlock_literal using rle literal");
65 return ZSTD_compressRleLiteralsBlock(dst, dstSize, literals, litSize);
66 }
67
68 assert(litSize > 0);
69 assert(hufMetadata->hType == set_compressed || hufMetadata->hType == set_repeat);
70
71 if (writeEntropy && hufMetadata->hType == set_compressed) {
72 ZSTD_memcpy(op, hufMetadata->hufDesBuffer, hufMetadata->hufDesSize);
73 op += hufMetadata->hufDesSize;
74 cLitSize += hufMetadata->hufDesSize;
75 DEBUGLOG(5, "ZSTD_compressSubBlock_literal (hSize=%zu)", hufMetadata->hufDesSize);
76 }
77
78 { int const flags = bmi2 ? HUF_flags_bmi2 : 0;
79 const size_t cSize = singleStream ? HUF_compress1X_usingCTable(op, (size_t)(oend-op), literals, litSize, hufTable, flags)
80 : HUF_compress4X_usingCTable(op, (size_t)(oend-op), literals, litSize, hufTable, flags);
81 op += cSize;
82 cLitSize += cSize;
83 if (cSize == 0 || ERR_isError(cSize)) {
84 DEBUGLOG(5, "Failed to write entropy tables %s", ZSTD_getErrorName(cSize));
85 return 0;
86 }
87 /* If we expand and we aren't writing a header then emit uncompressed */
88 if (!writeEntropy && cLitSize >= litSize) {
89 DEBUGLOG(5, "ZSTD_compressSubBlock_literal using raw literal because uncompressible");
90 return ZSTD_noCompressLiterals(dst, dstSize, literals, litSize);
91 }
92 /* If we are writing headers then allow expansion that doesn't change our header size. */
93 if (lhSize < (size_t)(3 + (cLitSize >= 1 KB) + (cLitSize >= 16 KB))) {
94 assert(cLitSize > litSize);
95 DEBUGLOG(5, "Literals expanded beyond allowed header size");
96 return ZSTD_noCompressLiterals(dst, dstSize, literals, litSize);
97 }
98 DEBUGLOG(5, "ZSTD_compressSubBlock_literal (cSize=%zu)", cSize);
99 }
100
101 /* Build header */
102 switch(lhSize)
103 {
104 case 3: /* 2 - 2 - 10 - 10 */
105 { U32 const lhc = hType + ((U32)(!singleStream) << 2) + ((U32)litSize<<4) + ((U32)cLitSize<<14);
106 MEM_writeLE24(ostart, lhc);
107 break;
108 }
109 case 4: /* 2 - 2 - 14 - 14 */
110 { U32 const lhc = hType + (2 << 2) + ((U32)litSize<<4) + ((U32)cLitSize<<18);
111 MEM_writeLE32(ostart, lhc);
112 break;
113 }
114 case 5: /* 2 - 2 - 18 - 18 */
115 { U32 const lhc = hType + (3 << 2) + ((U32)litSize<<4) + ((U32)cLitSize<<22);
116 MEM_writeLE32(ostart, lhc);
117 ostart[4] = (BYTE)(cLitSize >> 10);
118 break;
119 }
120 default: /* not possible : lhSize is {3,4,5} */
121 assert(0);
122 }
123 *entropyWritten = 1;
124 DEBUGLOG(5, "Compressed literals: %u -> %u", (U32)litSize, (U32)(op-ostart));
125 return (size_t)(op-ostart);
126}
127
128static size_t
129ZSTD_seqDecompressedSize(seqStore_t const* seqStore,
130 const seqDef* sequences, size_t nbSeqs,
131 size_t litSize, int lastSubBlock)
132{
133 size_t matchLengthSum = 0;
134 size_t litLengthSum = 0;
135 size_t n;
136 for (n=0; n<nbSeqs; n++) {
137 const ZSTD_sequenceLength seqLen = ZSTD_getSequenceLength(seqStore, sequences+n);
138 litLengthSum += seqLen.litLength;
139 matchLengthSum += seqLen.matchLength;
140 }
141 DEBUGLOG(5, "ZSTD_seqDecompressedSize: %u sequences from %p: %u literals + %u matchlength",
142 (unsigned)nbSeqs, (const void*)sequences,
143 (unsigned)litLengthSum, (unsigned)matchLengthSum);
144 if (!lastSubBlock)
145 assert(litLengthSum == litSize);
146 else
147 assert(litLengthSum <= litSize);
148 (void)litLengthSum;
149 return matchLengthSum + litSize;
150}
151
162static size_t
163ZSTD_compressSubBlock_sequences(const ZSTD_fseCTables_t* fseTables,
164 const ZSTD_fseCTablesMetadata_t* fseMetadata,
165 const seqDef* sequences, size_t nbSeq,
166 const BYTE* llCode, const BYTE* mlCode, const BYTE* ofCode,
167 const ZSTD_CCtx_params* cctxParams,
168 void* dst, size_t dstCapacity,
169 const int bmi2, int writeEntropy, int* entropyWritten)
170{
171 const int longOffsets = cctxParams->cParams.windowLog > STREAM_ACCUMULATOR_MIN;
172 BYTE* const ostart = (BYTE*)dst;
173 BYTE* const oend = ostart + dstCapacity;
174 BYTE* op = ostart;
175 BYTE* seqHead;
176
177 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (nbSeq=%zu, writeEntropy=%d, longOffsets=%d)", nbSeq, writeEntropy, longOffsets);
178
179 *entropyWritten = 0;
180 /* Sequences Header */
181 RETURN_ERROR_IF((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead*/,
182 dstSize_tooSmall, "");
183 if (nbSeq < 128)
184 *op++ = (BYTE)nbSeq;
185 else if (nbSeq < LONGNBSEQ)
186 op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
187 else
188 op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
189 if (nbSeq==0) {
190 return (size_t)(op - ostart);
191 }
192
193 /* seqHead : flags for FSE encoding type */
194 seqHead = op++;
195
196 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (seqHeadSize=%u)", (unsigned)(op-ostart));
197
198 if (writeEntropy) {
199 const U32 LLtype = fseMetadata->llType;
200 const U32 Offtype = fseMetadata->ofType;
201 const U32 MLtype = fseMetadata->mlType;
202 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (fseTablesSize=%zu)", fseMetadata->fseTablesSize);
203 *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
204 ZSTD_memcpy(op, fseMetadata->fseTablesBuffer, fseMetadata->fseTablesSize);
205 op += fseMetadata->fseTablesSize;
206 } else {
207 const U32 repeat = set_repeat;
208 *seqHead = (BYTE)((repeat<<6) + (repeat<<4) + (repeat<<2));
209 }
210
211 { size_t const bitstreamSize = ZSTD_encodeSequences(
212 op, (size_t)(oend - op),
213 fseTables->matchlengthCTable, mlCode,
214 fseTables->offcodeCTable, ofCode,
215 fseTables->litlengthCTable, llCode,
216 sequences, nbSeq,
217 longOffsets, bmi2);
218 FORWARD_IF_ERROR(bitstreamSize, "ZSTD_encodeSequences failed");
219 op += bitstreamSize;
220 /* zstd versions <= 1.3.4 mistakenly report corruption when
221 * FSE_readNCount() receives a buffer < 4 bytes.
222 * Fixed by https://github.com/facebook/zstd/pull/1146.
223 * This can happen when the last set_compressed table present is 2
224 * bytes and the bitstream is only one byte.
225 * In this exceedingly rare case, we will simply emit an uncompressed
226 * block, since it isn't worth optimizing.
227 */
228#ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
229 if (writeEntropy && fseMetadata->lastCountSize && fseMetadata->lastCountSize + bitstreamSize < 4) {
230 /* NCountSize >= 2 && bitstreamSize > 0 ==> lastCountSize == 3 */
231 assert(fseMetadata->lastCountSize + bitstreamSize == 3);
232 DEBUGLOG(5, "Avoiding bug in zstd decoder in versions <= 1.3.4 by "
233 "emitting an uncompressed block.");
234 return 0;
235 }
236#endif
237 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (bitstreamSize=%zu)", bitstreamSize);
238 }
239
240 /* zstd versions <= 1.4.0 mistakenly report error when
241 * sequences section body size is less than 3 bytes.
242 * Fixed by https://github.com/facebook/zstd/pull/1664.
243 * This can happen when the previous sequences section block is compressed
244 * with rle mode and the current block's sequences section is compressed
245 * with repeat mode where sequences section body size can be 1 byte.
246 */
247#ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
248 if (op-seqHead < 4) {
249 DEBUGLOG(5, "Avoiding bug in zstd decoder in versions <= 1.4.0 by emitting "
250 "an uncompressed block when sequences are < 4 bytes");
251 return 0;
252 }
253#endif
254
255 *entropyWritten = 1;
256 return (size_t)(op - ostart);
257}
258
263static size_t ZSTD_compressSubBlock(const ZSTD_entropyCTables_t* entropy,
264 const ZSTD_entropyCTablesMetadata_t* entropyMetadata,
265 const seqDef* sequences, size_t nbSeq,
266 const BYTE* literals, size_t litSize,
267 const BYTE* llCode, const BYTE* mlCode, const BYTE* ofCode,
268 const ZSTD_CCtx_params* cctxParams,
269 void* dst, size_t dstCapacity,
270 const int bmi2,
271 int writeLitEntropy, int writeSeqEntropy,
272 int* litEntropyWritten, int* seqEntropyWritten,
273 U32 lastBlock)
274{
275 BYTE* const ostart = (BYTE*)dst;
276 BYTE* const oend = ostart + dstCapacity;
277 BYTE* op = ostart + ZSTD_blockHeaderSize;
278 DEBUGLOG(5, "ZSTD_compressSubBlock (litSize=%zu, nbSeq=%zu, writeLitEntropy=%d, writeSeqEntropy=%d, lastBlock=%d)",
279 litSize, nbSeq, writeLitEntropy, writeSeqEntropy, lastBlock);
280 { size_t cLitSize = ZSTD_compressSubBlock_literal((const HUF_CElt*)entropy->huf.CTable,
281 &entropyMetadata->hufMetadata, literals, litSize,
282 op, (size_t)(oend-op),
283 bmi2, writeLitEntropy, litEntropyWritten);
284 FORWARD_IF_ERROR(cLitSize, "ZSTD_compressSubBlock_literal failed");
285 if (cLitSize == 0) return 0;
286 op += cLitSize;
287 }
288 { size_t cSeqSize = ZSTD_compressSubBlock_sequences(&entropy->fse,
289 &entropyMetadata->fseMetadata,
290 sequences, nbSeq,
291 llCode, mlCode, ofCode,
292 cctxParams,
293 op, (size_t)(oend-op),
294 bmi2, writeSeqEntropy, seqEntropyWritten);
295 FORWARD_IF_ERROR(cSeqSize, "ZSTD_compressSubBlock_sequences failed");
296 if (cSeqSize == 0) return 0;
297 op += cSeqSize;
298 }
299 /* Write block header */
300 { size_t cSize = (size_t)(op-ostart) - ZSTD_blockHeaderSize;
301 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3);
302 MEM_writeLE24(ostart, cBlockHeader24);
303 }
304 return (size_t)(op-ostart);
305}
306
307static size_t ZSTD_estimateSubBlockSize_literal(const BYTE* literals, size_t litSize,
308 const ZSTD_hufCTables_t* huf,
309 const ZSTD_hufCTablesMetadata_t* hufMetadata,
310 void* workspace, size_t wkspSize,
311 int writeEntropy)
312{
313 unsigned* const countWksp = (unsigned*)workspace;
314 unsigned maxSymbolValue = 255;
315 size_t literalSectionHeaderSize = 3; /* Use hard coded size of 3 bytes */
316
317 if (hufMetadata->hType == set_basic) return litSize;
318 else if (hufMetadata->hType == set_rle) return 1;
319 else if (hufMetadata->hType == set_compressed || hufMetadata->hType == set_repeat) {
320 size_t const largest = HIST_count_wksp (countWksp, &maxSymbolValue, (const BYTE*)literals, litSize, workspace, wkspSize);
321 if (ZSTD_isError(largest)) return litSize;
322 { size_t cLitSizeEstimate = HUF_estimateCompressedSize((const HUF_CElt*)huf->CTable, countWksp, maxSymbolValue);
323 if (writeEntropy) cLitSizeEstimate += hufMetadata->hufDesSize;
324 return cLitSizeEstimate + literalSectionHeaderSize;
325 } }
326 assert(0); /* impossible */
327 return 0;
328}
329
330static size_t ZSTD_estimateSubBlockSize_symbolType(symbolEncodingType_e type,
331 const BYTE* codeTable, unsigned maxCode,
332 size_t nbSeq, const FSE_CTable* fseCTable,
333 const U8* additionalBits,
334 short const* defaultNorm, U32 defaultNormLog, U32 defaultMax,
335 void* workspace, size_t wkspSize)
336{
337 unsigned* const countWksp = (unsigned*)workspace;
338 const BYTE* ctp = codeTable;
339 const BYTE* const ctStart = ctp;
340 const BYTE* const ctEnd = ctStart + nbSeq;
341 size_t cSymbolTypeSizeEstimateInBits = 0;
342 unsigned max = maxCode;
343
344 HIST_countFast_wksp(countWksp, &max, codeTable, nbSeq, workspace, wkspSize); /* can't fail */
345 if (type == set_basic) {
346 /* We selected this encoding type, so it must be valid. */
347 assert(max <= defaultMax);
348 cSymbolTypeSizeEstimateInBits = max <= defaultMax
349 ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, countWksp, max)
350 : ERROR(GENERIC);
351 } else if (type == set_rle) {
352 cSymbolTypeSizeEstimateInBits = 0;
353 } else if (type == set_compressed || type == set_repeat) {
354 cSymbolTypeSizeEstimateInBits = ZSTD_fseBitCost(fseCTable, countWksp, max);
355 }
356 if (ZSTD_isError(cSymbolTypeSizeEstimateInBits)) return nbSeq * 10;
357 while (ctp < ctEnd) {
358 if (additionalBits) cSymbolTypeSizeEstimateInBits += additionalBits[*ctp];
359 else cSymbolTypeSizeEstimateInBits += *ctp; /* for offset, offset code is also the number of additional bits */
360 ctp++;
361 }
362 return cSymbolTypeSizeEstimateInBits / 8;
363}
364
365static size_t ZSTD_estimateSubBlockSize_sequences(const BYTE* ofCodeTable,
366 const BYTE* llCodeTable,
367 const BYTE* mlCodeTable,
368 size_t nbSeq,
369 const ZSTD_fseCTables_t* fseTables,
370 const ZSTD_fseCTablesMetadata_t* fseMetadata,
371 void* workspace, size_t wkspSize,
372 int writeEntropy)
373{
374 size_t const sequencesSectionHeaderSize = 3; /* Use hard coded size of 3 bytes */
375 size_t cSeqSizeEstimate = 0;
376 if (nbSeq == 0) return sequencesSectionHeaderSize;
377 cSeqSizeEstimate += ZSTD_estimateSubBlockSize_symbolType(fseMetadata->ofType, ofCodeTable, MaxOff,
378 nbSeq, fseTables->offcodeCTable, NULL,
379 OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff,
380 workspace, wkspSize);
381 cSeqSizeEstimate += ZSTD_estimateSubBlockSize_symbolType(fseMetadata->llType, llCodeTable, MaxLL,
382 nbSeq, fseTables->litlengthCTable, LL_bits,
383 LL_defaultNorm, LL_defaultNormLog, MaxLL,
384 workspace, wkspSize);
385 cSeqSizeEstimate += ZSTD_estimateSubBlockSize_symbolType(fseMetadata->mlType, mlCodeTable, MaxML,
386 nbSeq, fseTables->matchlengthCTable, ML_bits,
387 ML_defaultNorm, ML_defaultNormLog, MaxML,
388 workspace, wkspSize);
389 if (writeEntropy) cSeqSizeEstimate += fseMetadata->fseTablesSize;
390 return cSeqSizeEstimate + sequencesSectionHeaderSize;
391}
392
393typedef struct {
397static EstimatedBlockSize ZSTD_estimateSubBlockSize(const BYTE* literals, size_t litSize,
398 const BYTE* ofCodeTable,
399 const BYTE* llCodeTable,
400 const BYTE* mlCodeTable,
401 size_t nbSeq,
402 const ZSTD_entropyCTables_t* entropy,
403 const ZSTD_entropyCTablesMetadata_t* entropyMetadata,
404 void* workspace, size_t wkspSize,
405 int writeLitEntropy, int writeSeqEntropy)
406{
408 ebs.estLitSize = ZSTD_estimateSubBlockSize_literal(literals, litSize,
409 &entropy->huf, &entropyMetadata->hufMetadata,
410 workspace, wkspSize, writeLitEntropy);
411 ebs.estBlockSize = ZSTD_estimateSubBlockSize_sequences(ofCodeTable, llCodeTable, mlCodeTable,
412 nbSeq, &entropy->fse, &entropyMetadata->fseMetadata,
413 workspace, wkspSize, writeSeqEntropy);
414 ebs.estBlockSize += ebs.estLitSize + ZSTD_blockHeaderSize;
415 return ebs;
416}
417
418static int ZSTD_needSequenceEntropyTables(ZSTD_fseCTablesMetadata_t const* fseMetadata)
419{
420 if (fseMetadata->llType == set_compressed || fseMetadata->llType == set_rle)
421 return 1;
422 if (fseMetadata->mlType == set_compressed || fseMetadata->mlType == set_rle)
423 return 1;
424 if (fseMetadata->ofType == set_compressed || fseMetadata->ofType == set_rle)
425 return 1;
426 return 0;
427}
428
429static size_t countLiterals(seqStore_t const* seqStore, const seqDef* sp, size_t seqCount)
430{
431 size_t n, total = 0;
432 assert(sp != NULL);
433 for (n=0; n<seqCount; n++) {
434 total += ZSTD_getSequenceLength(seqStore, sp+n).litLength;
435 }
436 DEBUGLOG(6, "countLiterals for %zu sequences from %p => %zu bytes", seqCount, (const void*)sp, total);
437 return total;
438}
439
440#define BYTESCALE 256
441
442static size_t sizeBlockSequences(const seqDef* sp, size_t nbSeqs,
443 size_t targetBudget, size_t avgLitCost, size_t avgSeqCost,
444 int firstSubBlock)
445{
446 size_t n, budget = 0, inSize=0;
447 /* entropy headers */
448 size_t const headerSize = (size_t)firstSubBlock * 120 * BYTESCALE; /* generous estimate */
449 assert(firstSubBlock==0 || firstSubBlock==1);
450 budget += headerSize;
451
452 /* first sequence => at least one sequence*/
453 budget += sp[0].litLength * avgLitCost + avgSeqCost;
454 if (budget > targetBudget) return 1;
455 inSize = sp[0].litLength + (sp[0].mlBase+MINMATCH);
456
457 /* loop over sequences */
458 for (n=1; n<nbSeqs; n++) {
459 size_t currentCost = sp[n].litLength * avgLitCost + avgSeqCost;
460 budget += currentCost;
461 inSize += sp[n].litLength + (sp[n].mlBase+MINMATCH);
462 /* stop when sub-block budget is reached */
463 if ( (budget > targetBudget)
464 /* though continue to expand until the sub-block is deemed compressible */
465 && (budget < inSize * BYTESCALE) )
466 break;
467 }
468
469 return n;
470}
471
479static size_t ZSTD_compressSubBlock_multi(const seqStore_t* seqStorePtr,
480 const ZSTD_compressedBlockState_t* prevCBlock,
481 ZSTD_compressedBlockState_t* nextCBlock,
482 const ZSTD_entropyCTablesMetadata_t* entropyMetadata,
483 const ZSTD_CCtx_params* cctxParams,
484 void* dst, size_t dstCapacity,
485 const void* src, size_t srcSize,
486 const int bmi2, U32 lastBlock,
487 void* workspace, size_t wkspSize)
488{
489 const seqDef* const sstart = seqStorePtr->sequencesStart;
490 const seqDef* const send = seqStorePtr->sequences;
491 const seqDef* sp = sstart; /* tracks progresses within seqStorePtr->sequences */
492 size_t const nbSeqs = (size_t)(send - sstart);
493 const BYTE* const lstart = seqStorePtr->litStart;
494 const BYTE* const lend = seqStorePtr->lit;
495 const BYTE* lp = lstart;
496 size_t const nbLiterals = (size_t)(lend - lstart);
497 BYTE const* ip = (BYTE const*)src;
498 BYTE const* const iend = ip + srcSize;
499 BYTE* const ostart = (BYTE*)dst;
500 BYTE* const oend = ostart + dstCapacity;
501 BYTE* op = ostart;
502 const BYTE* llCodePtr = seqStorePtr->llCode;
503 const BYTE* mlCodePtr = seqStorePtr->mlCode;
504 const BYTE* ofCodePtr = seqStorePtr->ofCode;
505 size_t const minTarget = ZSTD_TARGETCBLOCKSIZE_MIN; /* enforce minimum size, to reduce undesirable side effects */
506 size_t const targetCBlockSize = MAX(minTarget, cctxParams->targetCBlockSize);
507 int writeLitEntropy = (entropyMetadata->hufMetadata.hType == set_compressed);
508 int writeSeqEntropy = 1;
509
510 DEBUGLOG(5, "ZSTD_compressSubBlock_multi (srcSize=%u, litSize=%u, nbSeq=%u)",
511 (unsigned)srcSize, (unsigned)(lend-lstart), (unsigned)(send-sstart));
512
513 /* let's start by a general estimation for the full block */
514 if (nbSeqs > 0) {
515 EstimatedBlockSize const ebs =
516 ZSTD_estimateSubBlockSize(lp, nbLiterals,
517 ofCodePtr, llCodePtr, mlCodePtr, nbSeqs,
518 &nextCBlock->entropy, entropyMetadata,
519 workspace, wkspSize,
520 writeLitEntropy, writeSeqEntropy);
521 /* quick estimation */
522 size_t const avgLitCost = nbLiterals ? (ebs.estLitSize * BYTESCALE) / nbLiterals : BYTESCALE;
523 size_t const avgSeqCost = ((ebs.estBlockSize - ebs.estLitSize) * BYTESCALE) / nbSeqs;
524 const size_t nbSubBlocks = MAX((ebs.estBlockSize + (targetCBlockSize/2)) / targetCBlockSize, 1);
525 size_t n, avgBlockBudget, blockBudgetSupp=0;
526 avgBlockBudget = (ebs.estBlockSize * BYTESCALE) / nbSubBlocks;
527 DEBUGLOG(5, "estimated fullblock size=%u bytes ; avgLitCost=%.2f ; avgSeqCost=%.2f ; targetCBlockSize=%u, nbSubBlocks=%u ; avgBlockBudget=%.0f bytes",
528 (unsigned)ebs.estBlockSize, (double)avgLitCost/BYTESCALE, (double)avgSeqCost/BYTESCALE,
529 (unsigned)targetCBlockSize, (unsigned)nbSubBlocks, (double)avgBlockBudget/BYTESCALE);
530 /* simplification: if estimates states that the full superblock doesn't compress, just bail out immediately
531 * this will result in the production of a single uncompressed block covering @srcSize.*/
532 if (ebs.estBlockSize > srcSize) return 0;
533
534 /* compress and write sub-blocks */
535 assert(nbSubBlocks>0);
536 for (n=0; n < nbSubBlocks-1; n++) {
537 /* determine nb of sequences for current sub-block + nbLiterals from next sequence */
538 size_t const seqCount = sizeBlockSequences(sp, (size_t)(send-sp),
539 avgBlockBudget + blockBudgetSupp, avgLitCost, avgSeqCost, n==0);
540 /* if reached last sequence : break to last sub-block (simplification) */
541 assert(seqCount <= (size_t)(send-sp));
542 if (sp + seqCount == send) break;
543 assert(seqCount > 0);
544 /* compress sub-block */
545 { int litEntropyWritten = 0;
546 int seqEntropyWritten = 0;
547 size_t litSize = countLiterals(seqStorePtr, sp, seqCount);
548 const size_t decompressedSize =
549 ZSTD_seqDecompressedSize(seqStorePtr, sp, seqCount, litSize, 0);
550 size_t const cSize = ZSTD_compressSubBlock(&nextCBlock->entropy, entropyMetadata,
551 sp, seqCount,
552 lp, litSize,
553 llCodePtr, mlCodePtr, ofCodePtr,
554 cctxParams,
555 op, (size_t)(oend-op),
556 bmi2, writeLitEntropy, writeSeqEntropy,
557 &litEntropyWritten, &seqEntropyWritten,
558 0);
559 FORWARD_IF_ERROR(cSize, "ZSTD_compressSubBlock failed");
560
561 /* check compressibility, update state components */
562 if (cSize > 0 && cSize < decompressedSize) {
563 DEBUGLOG(5, "Committed sub-block compressing %u bytes => %u bytes",
564 (unsigned)decompressedSize, (unsigned)cSize);
565 assert(ip + decompressedSize <= iend);
566 ip += decompressedSize;
567 lp += litSize;
568 op += cSize;
569 llCodePtr += seqCount;
570 mlCodePtr += seqCount;
571 ofCodePtr += seqCount;
572 /* Entropy only needs to be written once */
573 if (litEntropyWritten) {
574 writeLitEntropy = 0;
575 }
576 if (seqEntropyWritten) {
577 writeSeqEntropy = 0;
578 }
579 sp += seqCount;
580 blockBudgetSupp = 0;
581 } }
582 /* otherwise : do not compress yet, coalesce current sub-block with following one */
583 }
584 } /* if (nbSeqs > 0) */
585
586 /* write last block */
587 DEBUGLOG(5, "Generate last sub-block: %u sequences remaining", (unsigned)(send - sp));
588 { int litEntropyWritten = 0;
589 int seqEntropyWritten = 0;
590 size_t litSize = (size_t)(lend - lp);
591 size_t seqCount = (size_t)(send - sp);
592 const size_t decompressedSize =
593 ZSTD_seqDecompressedSize(seqStorePtr, sp, seqCount, litSize, 1);
594 size_t const cSize = ZSTD_compressSubBlock(&nextCBlock->entropy, entropyMetadata,
595 sp, seqCount,
596 lp, litSize,
597 llCodePtr, mlCodePtr, ofCodePtr,
598 cctxParams,
599 op, (size_t)(oend-op),
600 bmi2, writeLitEntropy, writeSeqEntropy,
601 &litEntropyWritten, &seqEntropyWritten,
602 lastBlock);
603 FORWARD_IF_ERROR(cSize, "ZSTD_compressSubBlock failed");
604
605 /* update pointers, the nb of literals borrowed from next sequence must be preserved */
606 if (cSize > 0 && cSize < decompressedSize) {
607 DEBUGLOG(5, "Last sub-block compressed %u bytes => %u bytes",
608 (unsigned)decompressedSize, (unsigned)cSize);
609 assert(ip + decompressedSize <= iend);
610 ip += decompressedSize;
611 lp += litSize;
612 op += cSize;
613 llCodePtr += seqCount;
614 mlCodePtr += seqCount;
615 ofCodePtr += seqCount;
616 /* Entropy only needs to be written once */
617 if (litEntropyWritten) {
618 writeLitEntropy = 0;
619 }
620 if (seqEntropyWritten) {
621 writeSeqEntropy = 0;
622 }
623 sp += seqCount;
624 }
625 }
626
627
628 if (writeLitEntropy) {
629 DEBUGLOG(5, "Literal entropy tables were never written");
630 ZSTD_memcpy(&nextCBlock->entropy.huf, &prevCBlock->entropy.huf, sizeof(prevCBlock->entropy.huf));
631 }
632 if (writeSeqEntropy && ZSTD_needSequenceEntropyTables(&entropyMetadata->fseMetadata)) {
633 /* If we haven't written our entropy tables, then we've violated our contract and
634 * must emit an uncompressed block.
635 */
636 DEBUGLOG(5, "Sequence entropy tables were never written => cancel, emit an uncompressed block");
637 return 0;
638 }
639
640 if (ip < iend) {
641 /* some data left : last part of the block sent uncompressed */
642 size_t const rSize = (size_t)((iend - ip));
643 size_t const cSize = ZSTD_noCompressBlock(op, (size_t)(oend - op), ip, rSize, lastBlock);
644 DEBUGLOG(5, "Generate last uncompressed sub-block of %u bytes", (unsigned)(rSize));
645 FORWARD_IF_ERROR(cSize, "ZSTD_noCompressBlock failed");
646 assert(cSize != 0);
647 op += cSize;
648 /* We have to regenerate the repcodes because we've skipped some sequences */
649 if (sp < send) {
650 const seqDef* seq;
651 repcodes_t rep;
652 ZSTD_memcpy(&rep, prevCBlock->rep, sizeof(rep));
653 for (seq = sstart; seq < sp; ++seq) {
654 ZSTD_updateRep(rep.rep, seq->offBase, ZSTD_getSequenceLength(seqStorePtr, seq).litLength == 0);
655 }
656 ZSTD_memcpy(nextCBlock->rep, &rep, sizeof(rep));
657 }
658 }
659
660 DEBUGLOG(5, "ZSTD_compressSubBlock_multi compressed all subBlocks: total compressed size = %u",
661 (unsigned)(op-ostart));
662 return (size_t)(op-ostart);
663}
664
666 void* dst, size_t dstCapacity,
667 const void* src, size_t srcSize,
668 unsigned lastBlock)
669{
670 ZSTD_entropyCTablesMetadata_t entropyMetadata;
671
675 &zc->appliedParams,
676 &entropyMetadata,
677 zc->entropyWorkspace, ENTROPY_WORKSPACE_SIZE /* statically allocated in resetCCtx */), "");
678
679 return ZSTD_compressSubBlock_multi(&zc->seqStore,
682 &entropyMetadata,
683 &zc->appliedParams,
684 dst, dstCapacity,
685 src, srcSize,
686 zc->bmi2, lastBlock,
687 zc->entropyWorkspace, ENTROPY_WORKSPACE_SIZE /* statically allocated in resetCCtx */);
688}
#define STREAM_ACCUMULATOR_MIN
Definition: bitstream.h:49
#define DEBUGLOG(l,...)
Definition: debug.h:108
#define assert(condition)
Definition: debug.h:74
#define ERROR(name)
Definition: error_private.h:55
#define FORWARD_IF_ERROR(err,...)
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:58
#define RETURN_ERROR_IF(cond, err,...)
unsigned FSE_CTable
Definition: fse.h:124
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:154
size_t HIST_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:140
@ HUF_flags_bmi2
Definition: huf.h:90
size_t HUF_CElt
Definition: huf.h:62
size_t HUF_compress4X_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int flags)
size_t HUF_estimateCompressedSize(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:793
size_t HUF_compress1X_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int flags)
unsigned char U8
Definition: mem.h:59
unsigned char BYTE
Definition: mem.h:58
MEM_STATIC void MEM_writeLE16(void *memPtr, U16 val)
Definition: mem.h:298
MEM_STATIC void MEM_writeLE32(void *memPtr, U32 val32)
Definition: mem.h:328
unsigned int U32
Definition: mem.h:69
MEM_STATIC void MEM_writeLE24(void *memPtr, U32 val)
Definition: mem.h:314
unsigned short U16
Definition: mem.h:64
constexpr dcon::demographics_key total(0)
void send(sys::state &state, element_base *parent, T value)
#define MAX(a, b)
ZSTD_CCtx_params appliedParams
ZSTD_blockState_t blockState
ZSTD_compressedBlockState_t * prevCBlock
ZSTD_compressedBlockState_t * nextCBlock
ZSTD_hufCTablesMetadata_t hufMetadata
ZSTD_fseCTablesMetadata_t fseMetadata
FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]
FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]
FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]
BYTE fseTablesBuffer[ZSTD_MAX_FSE_HEADERS_SIZE]
HUF_CElt CTable[HUF_CTABLE_SIZE_ST(255)]
BYTE hufDesBuffer[ZSTD_MAX_HUF_HEADER_SIZE]
BYTE * litStart
BYTE * ofCode
BYTE * llCode
seqDef * sequencesStart
BYTE * mlCode
seqDef * sequences
const char * ZSTD_getErrorName(size_t code)
Definition: zstd_common.c:40
size_t ZSTD_buildBlockEntropyStats(const seqStore_t *seqStorePtr, const ZSTD_entropyCTables_t *prevEntropy, ZSTD_entropyCTables_t *nextEntropy, const ZSTD_CCtx_params *cctxParams, ZSTD_entropyCTablesMetadata_t *entropyMetadata, void *workspace, size_t wkspSize)
MEM_STATIC size_t ZSTD_noCompressBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 lastBlock)
MEM_STATIC void ZSTD_updateRep(U32 rep[ZSTD_REP_NUM], U32 const offBase, U32 const ll0)
#define ENTROPY_WORKSPACE_SIZE
size_t ZSTD_noCompressLiterals(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
size_t ZSTD_compressRleLiteralsBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
size_t ZSTD_crossEntropyCost(short const *norm, unsigned accuracyLog, unsigned const *count, unsigned const max)
size_t ZSTD_fseBitCost(FSE_CTable const *ctable, unsigned const *count, unsigned const max)
size_t ZSTD_encodeSequences(void *dst, size_t dstCapacity, FSE_CTable const *CTable_MatchLength, BYTE const *mlCodeTable, FSE_CTable const *CTable_OffsetBits, BYTE const *ofCodeTable, FSE_CTable const *CTable_LitLength, BYTE const *llCodeTable, seqDef const *sequences, size_t nbSeq, int longOffsets, int bmi2)
#define BYTESCALE
size_t ZSTD_compressSuperBlock(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned lastBlock)
#define ZSTD_memcpy(d, s, l)
Definition: zstd_deps.h:36
#define KB
Definition: zstd_internal.h:71
#define MINMATCH
#define MaxLL
#define MaxML
#define ZSTD_isError
Definition: zstd_internal.h:48
@ bt_compressed
Definition: zstd_internal.h:90
#define LONGNBSEQ
symbolEncodingType_e
Definition: zstd_internal.h:98
@ set_repeat
Definition: zstd_internal.h:98
@ set_basic
Definition: zstd_internal.h:98
@ set_compressed
Definition: zstd_internal.h:98
@ set_rle
Definition: zstd_internal.h:98
#define MaxOff
#define DefaultMaxOff
MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const *seqStore, seqDef const *seq)