1 /* 2 * Copyright (c) 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 /*-************************************* 12 * Dependencies 13 ***************************************/ 14 #include "zstd_compress_superblock.h" 15 16 #include "../common/zstd_internal.h" /* ZSTD_getSequenceLength */ 17 #include "hist.h" /* HIST_countFast_wksp */ 18 #include "zstd_compress_internal.h" 19 #include "zstd_compress_sequences.h" 20 #include "zstd_compress_literals.h" 21 22 /*-************************************* 23 * Superblock entropy buffer structs 24 ***************************************/ 25 /* ZSTD_hufCTablesMetadata_t : 26 * Stores Literals Block Type for a super-block in hType, and 27 * huffman tree description in hufDesBuffer. 28 * hufDesSize refers to the size of huffman tree description in bytes. 29 * This metadata is populated in ZSTD_buildSuperBlockEntropy_literal() */ 30 typedef struct { 31 symbolEncodingType_e hType; 32 BYTE hufDesBuffer[ZSTD_MAX_HUF_HEADER_SIZE]; 33 size_t hufDesSize; 34 } ZSTD_hufCTablesMetadata_t; 35 36 /* ZSTD_fseCTablesMetadata_t : 37 * Stores symbol compression modes for a super-block in {ll, ol, ml}Type, and 38 * fse tables in fseTablesBuffer. 39 * fseTablesSize refers to the size of fse tables in bytes. 40 * This metadata is populated in ZSTD_buildSuperBlockEntropy_sequences() */ 41 typedef struct { 42 symbolEncodingType_e llType; 43 symbolEncodingType_e ofType; 44 symbolEncodingType_e mlType; 45 BYTE fseTablesBuffer[ZSTD_MAX_FSE_HEADERS_SIZE]; 46 size_t fseTablesSize; 47 size_t lastCountSize; /* This is to account for bug in 1.3.4. More detail in ZSTD_compressSubBlock_sequences() */ 48 } ZSTD_fseCTablesMetadata_t; 49 50 typedef struct { 51 ZSTD_hufCTablesMetadata_t hufMetadata; 52 ZSTD_fseCTablesMetadata_t fseMetadata; 53 } ZSTD_entropyCTablesMetadata_t; 54 55 56 /* ZSTD_buildSuperBlockEntropy_literal() : 57 * Builds entropy for the super-block literals. 58 * Stores literals block type (raw, rle, compressed, repeat) and 59 * huffman description table to hufMetadata. 60 * @return : size of huffman description table or error code */ 61 static size_t ZSTD_buildSuperBlockEntropy_literal(void* const src, size_t srcSize, 62 const ZSTD_hufCTables_t* prevHuf, 63 ZSTD_hufCTables_t* nextHuf, 64 ZSTD_hufCTablesMetadata_t* hufMetadata, 65 const int disableLiteralsCompression, 66 void* workspace, size_t wkspSize) 67 { 68 BYTE* const wkspStart = (BYTE*)workspace; 69 BYTE* const wkspEnd = wkspStart + wkspSize; 70 BYTE* const countWkspStart = wkspStart; 71 unsigned* const countWksp = (unsigned*)workspace; 72 const size_t countWkspSize = (HUF_SYMBOLVALUE_MAX + 1) * sizeof(unsigned); 73 BYTE* const nodeWksp = countWkspStart + countWkspSize; 74 const size_t nodeWkspSize = wkspEnd-nodeWksp; 75 unsigned maxSymbolValue = 255; 76 unsigned huffLog = HUF_TABLELOG_DEFAULT; 77 HUF_repeat repeat = prevHuf->repeatMode; 78 79 DEBUGLOG(5, "ZSTD_buildSuperBlockEntropy_literal (srcSize=%zu)", srcSize); 80 81 /* Prepare nextEntropy assuming reusing the existing table */ 82 ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf)); 83 84 if (disableLiteralsCompression) { 85 DEBUGLOG(5, "set_basic - disabled"); 86 hufMetadata->hType = set_basic; 87 return 0; 88 } 89 90 /* small ? don't even attempt compression (speed opt) */ 91 # define COMPRESS_LITERALS_SIZE_MIN 63 92 { size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN; 93 if (srcSize <= minLitSize) { 94 DEBUGLOG(5, "set_basic - too small"); 95 hufMetadata->hType = set_basic; 96 return 0; 97 } 98 } 99 100 /* Scan input and build symbol stats */ 101 { size_t const largest = HIST_count_wksp (countWksp, &maxSymbolValue, (const BYTE*)src, srcSize, workspace, wkspSize); 102 FORWARD_IF_ERROR(largest, "HIST_count_wksp failed"); 103 if (largest == srcSize) { 104 DEBUGLOG(5, "set_rle"); 105 hufMetadata->hType = set_rle; 106 return 0; 107 } 108 if (largest <= (srcSize >> 7)+4) { 109 DEBUGLOG(5, "set_basic - no gain"); 110 hufMetadata->hType = set_basic; 111 return 0; 112 } 113 } 114 115 /* Validate the previous Huffman table */ 116 if (repeat == HUF_repeat_check && !HUF_validateCTable((HUF_CElt const*)prevHuf->CTable, countWksp, maxSymbolValue)) { 117 repeat = HUF_repeat_none; 118 } 119 120 /* Build Huffman Tree */ 121 ZSTD_memset(nextHuf->CTable, 0, sizeof(nextHuf->CTable)); 122 huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue); 123 { size_t const maxBits = HUF_buildCTable_wksp((HUF_CElt*)nextHuf->CTable, countWksp, 124 maxSymbolValue, huffLog, 125 nodeWksp, nodeWkspSize); 126 FORWARD_IF_ERROR(maxBits, "HUF_buildCTable_wksp"); 127 huffLog = (U32)maxBits; 128 { /* Build and write the CTable */ 129 size_t const newCSize = HUF_estimateCompressedSize( 130 (HUF_CElt*)nextHuf->CTable, countWksp, maxSymbolValue); 131 size_t const hSize = HUF_writeCTable_wksp( 132 hufMetadata->hufDesBuffer, sizeof(hufMetadata->hufDesBuffer), 133 (HUF_CElt*)nextHuf->CTable, maxSymbolValue, huffLog, 134 nodeWksp, nodeWkspSize); 135 /* Check against repeating the previous CTable */ 136 if (repeat != HUF_repeat_none) { 137 size_t const oldCSize = HUF_estimateCompressedSize( 138 (HUF_CElt const*)prevHuf->CTable, countWksp, maxSymbolValue); 139 if (oldCSize < srcSize && (oldCSize <= hSize + newCSize || hSize + 12 >= srcSize)) { 140 DEBUGLOG(5, "set_repeat - smaller"); 141 ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf)); 142 hufMetadata->hType = set_repeat; 143 return 0; 144 } 145 } 146 if (newCSize + hSize >= srcSize) { 147 DEBUGLOG(5, "set_basic - no gains"); 148 ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf)); 149 hufMetadata->hType = set_basic; 150 return 0; 151 } 152 DEBUGLOG(5, "set_compressed (hSize=%u)", (U32)hSize); 153 hufMetadata->hType = set_compressed; 154 nextHuf->repeatMode = HUF_repeat_check; 155 return hSize; 156 } 157 } 158 } 159 160 /* ZSTD_buildSuperBlockEntropy_sequences() : 161 * Builds entropy for the super-block sequences. 162 * Stores symbol compression modes and fse table to fseMetadata. 163 * @return : size of fse tables or error code */ 164 static size_t ZSTD_buildSuperBlockEntropy_sequences(seqStore_t* seqStorePtr, 165 const ZSTD_fseCTables_t* prevEntropy, 166 ZSTD_fseCTables_t* nextEntropy, 167 const ZSTD_CCtx_params* cctxParams, 168 ZSTD_fseCTablesMetadata_t* fseMetadata, 169 void* workspace, size_t wkspSize) 170 { 171 BYTE* const wkspStart = (BYTE*)workspace; 172 BYTE* const wkspEnd = wkspStart + wkspSize; 173 BYTE* const countWkspStart = wkspStart; 174 unsigned* const countWksp = (unsigned*)workspace; 175 const size_t countWkspSize = (MaxSeq + 1) * sizeof(unsigned); 176 BYTE* const cTableWksp = countWkspStart + countWkspSize; 177 const size_t cTableWkspSize = wkspEnd-cTableWksp; 178 ZSTD_strategy const strategy = cctxParams->cParams.strategy; 179 FSE_CTable* CTable_LitLength = nextEntropy->litlengthCTable; 180 FSE_CTable* CTable_OffsetBits = nextEntropy->offcodeCTable; 181 FSE_CTable* CTable_MatchLength = nextEntropy->matchlengthCTable; 182 const BYTE* const ofCodeTable = seqStorePtr->ofCode; 183 const BYTE* const llCodeTable = seqStorePtr->llCode; 184 const BYTE* const mlCodeTable = seqStorePtr->mlCode; 185 size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart; 186 BYTE* const ostart = fseMetadata->fseTablesBuffer; 187 BYTE* const oend = ostart + sizeof(fseMetadata->fseTablesBuffer); 188 BYTE* op = ostart; 189 190 assert(cTableWkspSize >= (1 << MaxFSELog) * sizeof(FSE_FUNCTION_TYPE)); 191 DEBUGLOG(5, "ZSTD_buildSuperBlockEntropy_sequences (nbSeq=%zu)", nbSeq); 192 ZSTD_memset(workspace, 0, wkspSize); 193 194 fseMetadata->lastCountSize = 0; 195 /* convert length/distances into codes */ 196 ZSTD_seqToCodes(seqStorePtr); 197 /* build CTable for Literal Lengths */ 198 { U32 LLtype; 199 unsigned max = MaxLL; 200 size_t const mostFrequent = HIST_countFast_wksp(countWksp, &max, llCodeTable, nbSeq, workspace, wkspSize); /* can't fail */ 201 DEBUGLOG(5, "Building LL table"); 202 nextEntropy->litlength_repeatMode = prevEntropy->litlength_repeatMode; 203 LLtype = ZSTD_selectEncodingType(&nextEntropy->litlength_repeatMode, 204 countWksp, max, mostFrequent, nbSeq, 205 LLFSELog, prevEntropy->litlengthCTable, 206 LL_defaultNorm, LL_defaultNormLog, 207 ZSTD_defaultAllowed, strategy); 208 assert(set_basic < set_compressed && set_rle < set_compressed); 209 assert(!(LLtype < set_compressed && nextEntropy->litlength_repeatMode != FSE_repeat_none)); /* We don't copy tables */ 210 { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_LitLength, LLFSELog, (symbolEncodingType_e)LLtype, 211 countWksp, max, llCodeTable, nbSeq, LL_defaultNorm, LL_defaultNormLog, MaxLL, 212 prevEntropy->litlengthCTable, sizeof(prevEntropy->litlengthCTable), 213 cTableWksp, cTableWkspSize); 214 FORWARD_IF_ERROR(countSize, "ZSTD_buildCTable for LitLens failed"); 215 if (LLtype == set_compressed) 216 fseMetadata->lastCountSize = countSize; 217 op += countSize; 218 fseMetadata->llType = (symbolEncodingType_e) LLtype; 219 } } 220 /* build CTable for Offsets */ 221 { U32 Offtype; 222 unsigned max = MaxOff; 223 size_t const mostFrequent = HIST_countFast_wksp(countWksp, &max, ofCodeTable, nbSeq, workspace, wkspSize); /* can't fail */ 224 /* We can only use the basic table if max <= DefaultMaxOff, otherwise the offsets are too large */ 225 ZSTD_defaultPolicy_e const defaultPolicy = (max <= DefaultMaxOff) ? ZSTD_defaultAllowed : ZSTD_defaultDisallowed; 226 DEBUGLOG(5, "Building OF table"); 227 nextEntropy->offcode_repeatMode = prevEntropy->offcode_repeatMode; 228 Offtype = ZSTD_selectEncodingType(&nextEntropy->offcode_repeatMode, 229 countWksp, max, mostFrequent, nbSeq, 230 OffFSELog, prevEntropy->offcodeCTable, 231 OF_defaultNorm, OF_defaultNormLog, 232 defaultPolicy, strategy); 233 assert(!(Offtype < set_compressed && nextEntropy->offcode_repeatMode != FSE_repeat_none)); /* We don't copy tables */ 234 { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_OffsetBits, OffFSELog, (symbolEncodingType_e)Offtype, 235 countWksp, max, ofCodeTable, nbSeq, OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff, 236 prevEntropy->offcodeCTable, sizeof(prevEntropy->offcodeCTable), 237 cTableWksp, cTableWkspSize); 238 FORWARD_IF_ERROR(countSize, "ZSTD_buildCTable for Offsets failed"); 239 if (Offtype == set_compressed) 240 fseMetadata->lastCountSize = countSize; 241 op += countSize; 242 fseMetadata->ofType = (symbolEncodingType_e) Offtype; 243 } } 244 /* build CTable for MatchLengths */ 245 { U32 MLtype; 246 unsigned max = MaxML; 247 size_t const mostFrequent = HIST_countFast_wksp(countWksp, &max, mlCodeTable, nbSeq, workspace, wkspSize); /* can't fail */ 248 DEBUGLOG(5, "Building ML table (remaining space : %i)", (int)(oend-op)); 249 nextEntropy->matchlength_repeatMode = prevEntropy->matchlength_repeatMode; 250 MLtype = ZSTD_selectEncodingType(&nextEntropy->matchlength_repeatMode, 251 countWksp, max, mostFrequent, nbSeq, 252 MLFSELog, prevEntropy->matchlengthCTable, 253 ML_defaultNorm, ML_defaultNormLog, 254 ZSTD_defaultAllowed, strategy); 255 assert(!(MLtype < set_compressed && nextEntropy->matchlength_repeatMode != FSE_repeat_none)); /* We don't copy tables */ 256 { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_MatchLength, MLFSELog, (symbolEncodingType_e)MLtype, 257 countWksp, max, mlCodeTable, nbSeq, ML_defaultNorm, ML_defaultNormLog, MaxML, 258 prevEntropy->matchlengthCTable, sizeof(prevEntropy->matchlengthCTable), 259 cTableWksp, cTableWkspSize); 260 FORWARD_IF_ERROR(countSize, "ZSTD_buildCTable for MatchLengths failed"); 261 if (MLtype == set_compressed) 262 fseMetadata->lastCountSize = countSize; 263 op += countSize; 264 fseMetadata->mlType = (symbolEncodingType_e) MLtype; 265 } } 266 assert((size_t) (op-ostart) <= sizeof(fseMetadata->fseTablesBuffer)); 267 return op-ostart; 268 } 269 270 271 /* ZSTD_buildSuperBlockEntropy() : 272 * Builds entropy for the super-block. 273 * @return : 0 on success or error code */ 274 static size_t 275 ZSTD_buildSuperBlockEntropy(seqStore_t* seqStorePtr, 276 const ZSTD_entropyCTables_t* prevEntropy, 277 ZSTD_entropyCTables_t* nextEntropy, 278 const ZSTD_CCtx_params* cctxParams, 279 ZSTD_entropyCTablesMetadata_t* entropyMetadata, 280 void* workspace, size_t wkspSize) 281 { 282 size_t const litSize = seqStorePtr->lit - seqStorePtr->litStart; 283 DEBUGLOG(5, "ZSTD_buildSuperBlockEntropy"); 284 entropyMetadata->hufMetadata.hufDesSize = 285 ZSTD_buildSuperBlockEntropy_literal(seqStorePtr->litStart, litSize, 286 &prevEntropy->huf, &nextEntropy->huf, 287 &entropyMetadata->hufMetadata, 288 ZSTD_disableLiteralsCompression(cctxParams), 289 workspace, wkspSize); 290 FORWARD_IF_ERROR(entropyMetadata->hufMetadata.hufDesSize, "ZSTD_buildSuperBlockEntropy_literal failed"); 291 entropyMetadata->fseMetadata.fseTablesSize = 292 ZSTD_buildSuperBlockEntropy_sequences(seqStorePtr, 293 &prevEntropy->fse, &nextEntropy->fse, 294 cctxParams, 295 &entropyMetadata->fseMetadata, 296 workspace, wkspSize); 297 FORWARD_IF_ERROR(entropyMetadata->fseMetadata.fseTablesSize, "ZSTD_buildSuperBlockEntropy_sequences failed"); 298 return 0; 299 } 300 301 /* ZSTD_compressSubBlock_literal() : 302 * Compresses literals section for a sub-block. 303 * When we have to write the Huffman table we will sometimes choose a header 304 * size larger than necessary. This is because we have to pick the header size 305 * before we know the table size + compressed size, so we have a bound on the 306 * table size. If we guessed incorrectly, we fall back to uncompressed literals. 307 * 308 * We write the header when writeEntropy=1 and set entropyWritten=1 when we succeeded 309 * in writing the header, otherwise it is set to 0. 310 * 311 * hufMetadata->hType has literals block type info. 312 * If it is set_basic, all sub-blocks literals section will be Raw_Literals_Block. 313 * If it is set_rle, all sub-blocks literals section will be RLE_Literals_Block. 314 * If it is set_compressed, first sub-block's literals section will be Compressed_Literals_Block 315 * If it is set_compressed, first sub-block's literals section will be Treeless_Literals_Block 316 * and the following sub-blocks' literals sections will be Treeless_Literals_Block. 317 * @return : compressed size of literals section of a sub-block 318 * Or 0 if it unable to compress. 319 * Or error code */ 320 static size_t ZSTD_compressSubBlock_literal(const HUF_CElt* hufTable, 321 const ZSTD_hufCTablesMetadata_t* hufMetadata, 322 const BYTE* literals, size_t litSize, 323 void* dst, size_t dstSize, 324 const int bmi2, int writeEntropy, int* entropyWritten) 325 { 326 size_t const header = writeEntropy ? 200 : 0; 327 size_t const lhSize = 3 + (litSize >= (1 KB - header)) + (litSize >= (16 KB - header)); 328 BYTE* const ostart = (BYTE*)dst; 329 BYTE* const oend = ostart + dstSize; 330 BYTE* op = ostart + lhSize; 331 U32 const singleStream = lhSize == 3; 332 symbolEncodingType_e hType = writeEntropy ? hufMetadata->hType : set_repeat; 333 size_t cLitSize = 0; 334 335 (void)bmi2; /* TODO bmi2... */ 336 337 DEBUGLOG(5, "ZSTD_compressSubBlock_literal (litSize=%zu, lhSize=%zu, writeEntropy=%d)", litSize, lhSize, writeEntropy); 338 339 *entropyWritten = 0; 340 if (litSize == 0 || hufMetadata->hType == set_basic) { 341 DEBUGLOG(5, "ZSTD_compressSubBlock_literal using raw literal"); 342 return ZSTD_noCompressLiterals(dst, dstSize, literals, litSize); 343 } else if (hufMetadata->hType == set_rle) { 344 DEBUGLOG(5, "ZSTD_compressSubBlock_literal using rle literal"); 345 return ZSTD_compressRleLiteralsBlock(dst, dstSize, literals, litSize); 346 } 347 348 assert(litSize > 0); 349 assert(hufMetadata->hType == set_compressed || hufMetadata->hType == set_repeat); 350 351 if (writeEntropy && hufMetadata->hType == set_compressed) { 352 ZSTD_memcpy(op, hufMetadata->hufDesBuffer, hufMetadata->hufDesSize); 353 op += hufMetadata->hufDesSize; 354 cLitSize += hufMetadata->hufDesSize; 355 DEBUGLOG(5, "ZSTD_compressSubBlock_literal (hSize=%zu)", hufMetadata->hufDesSize); 356 } 357 358 /* TODO bmi2 */ 359 { const size_t cSize = singleStream ? HUF_compress1X_usingCTable(op, oend-op, literals, litSize, hufTable) 360 : HUF_compress4X_usingCTable(op, oend-op, literals, litSize, hufTable); 361 op += cSize; 362 cLitSize += cSize; 363 if (cSize == 0 || ERR_isError(cSize)) { 364 DEBUGLOG(5, "Failed to write entropy tables %s", ZSTD_getErrorName(cSize)); 365 return 0; 366 } 367 /* If we expand and we aren't writing a header then emit uncompressed */ 368 if (!writeEntropy && cLitSize >= litSize) { 369 DEBUGLOG(5, "ZSTD_compressSubBlock_literal using raw literal because uncompressible"); 370 return ZSTD_noCompressLiterals(dst, dstSize, literals, litSize); 371 } 372 /* If we are writing headers then allow expansion that doesn't change our header size. */ 373 if (lhSize < (size_t)(3 + (cLitSize >= 1 KB) + (cLitSize >= 16 KB))) { 374 assert(cLitSize > litSize); 375 DEBUGLOG(5, "Literals expanded beyond allowed header size"); 376 return ZSTD_noCompressLiterals(dst, dstSize, literals, litSize); 377 } 378 DEBUGLOG(5, "ZSTD_compressSubBlock_literal (cSize=%zu)", cSize); 379 } 380 381 /* Build header */ 382 switch(lhSize) 383 { 384 case 3: /* 2 - 2 - 10 - 10 */ 385 { U32 const lhc = hType + ((!singleStream) << 2) + ((U32)litSize<<4) + ((U32)cLitSize<<14); 386 MEM_writeLE24(ostart, lhc); 387 break; 388 } 389 case 4: /* 2 - 2 - 14 - 14 */ 390 { U32 const lhc = hType + (2 << 2) + ((U32)litSize<<4) + ((U32)cLitSize<<18); 391 MEM_writeLE32(ostart, lhc); 392 break; 393 } 394 case 5: /* 2 - 2 - 18 - 18 */ 395 { U32 const lhc = hType + (3 << 2) + ((U32)litSize<<4) + ((U32)cLitSize<<22); 396 MEM_writeLE32(ostart, lhc); 397 ostart[4] = (BYTE)(cLitSize >> 10); 398 break; 399 } 400 default: /* not possible : lhSize is {3,4,5} */ 401 assert(0); 402 } 403 *entropyWritten = 1; 404 DEBUGLOG(5, "Compressed literals: %u -> %u", (U32)litSize, (U32)(op-ostart)); 405 return op-ostart; 406 } 407 408 static size_t ZSTD_seqDecompressedSize(seqStore_t const* seqStore, const seqDef* sequences, size_t nbSeq, size_t litSize, int lastSequence) { 409 const seqDef* const sstart = sequences; 410 const seqDef* const send = sequences + nbSeq; 411 const seqDef* sp = sstart; 412 size_t matchLengthSum = 0; 413 size_t litLengthSum = 0; 414 while (send-sp > 0) { 415 ZSTD_sequenceLength const seqLen = ZSTD_getSequenceLength(seqStore, sp); 416 litLengthSum += seqLen.litLength; 417 matchLengthSum += seqLen.matchLength; 418 sp++; 419 } 420 assert(litLengthSum <= litSize); 421 if (!lastSequence) { 422 assert(litLengthSum == litSize); 423 } 424 return matchLengthSum + litSize; 425 } 426 427 /* ZSTD_compressSubBlock_sequences() : 428 * Compresses sequences section for a sub-block. 429 * fseMetadata->llType, fseMetadata->ofType, and fseMetadata->mlType have 430 * symbol compression modes for the super-block. 431 * The first successfully compressed block will have these in its header. 432 * We set entropyWritten=1 when we succeed in compressing the sequences. 433 * The following sub-blocks will always have repeat mode. 434 * @return : compressed size of sequences section of a sub-block 435 * Or 0 if it is unable to compress 436 * Or error code. */ 437 static size_t ZSTD_compressSubBlock_sequences(const ZSTD_fseCTables_t* fseTables, 438 const ZSTD_fseCTablesMetadata_t* fseMetadata, 439 const seqDef* sequences, size_t nbSeq, 440 const BYTE* llCode, const BYTE* mlCode, const BYTE* ofCode, 441 const ZSTD_CCtx_params* cctxParams, 442 void* dst, size_t dstCapacity, 443 const int bmi2, int writeEntropy, int* entropyWritten) 444 { 445 const int longOffsets = cctxParams->cParams.windowLog > STREAM_ACCUMULATOR_MIN; 446 BYTE* const ostart = (BYTE*)dst; 447 BYTE* const oend = ostart + dstCapacity; 448 BYTE* op = ostart; 449 BYTE* seqHead; 450 451 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (nbSeq=%zu, writeEntropy=%d, longOffsets=%d)", nbSeq, writeEntropy, longOffsets); 452 453 *entropyWritten = 0; 454 /* Sequences Header */ 455 RETURN_ERROR_IF((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead*/, 456 dstSize_tooSmall, ""); 457 if (nbSeq < 0x7F) 458 *op++ = (BYTE)nbSeq; 459 else if (nbSeq < LONGNBSEQ) 460 op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2; 461 else 462 op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3; 463 if (nbSeq==0) { 464 return op - ostart; 465 } 466 467 /* seqHead : flags for FSE encoding type */ 468 seqHead = op++; 469 470 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (seqHeadSize=%u)", (unsigned)(op-ostart)); 471 472 if (writeEntropy) { 473 const U32 LLtype = fseMetadata->llType; 474 const U32 Offtype = fseMetadata->ofType; 475 const U32 MLtype = fseMetadata->mlType; 476 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (fseTablesSize=%zu)", fseMetadata->fseTablesSize); 477 *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2)); 478 ZSTD_memcpy(op, fseMetadata->fseTablesBuffer, fseMetadata->fseTablesSize); 479 op += fseMetadata->fseTablesSize; 480 } else { 481 const U32 repeat = set_repeat; 482 *seqHead = (BYTE)((repeat<<6) + (repeat<<4) + (repeat<<2)); 483 } 484 485 { size_t const bitstreamSize = ZSTD_encodeSequences( 486 op, oend - op, 487 fseTables->matchlengthCTable, mlCode, 488 fseTables->offcodeCTable, ofCode, 489 fseTables->litlengthCTable, llCode, 490 sequences, nbSeq, 491 longOffsets, bmi2); 492 FORWARD_IF_ERROR(bitstreamSize, "ZSTD_encodeSequences failed"); 493 op += bitstreamSize; 494 /* zstd versions <= 1.3.4 mistakenly report corruption when 495 * FSE_readNCount() receives a buffer < 4 bytes. 496 * Fixed by https://github.com/facebook/zstd/pull/1146. 497 * This can happen when the last set_compressed table present is 2 498 * bytes and the bitstream is only one byte. 499 * In this exceedingly rare case, we will simply emit an uncompressed 500 * block, since it isn't worth optimizing. 501 */ 502 #ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 503 if (writeEntropy && fseMetadata->lastCountSize && fseMetadata->lastCountSize + bitstreamSize < 4) { 504 /* NCountSize >= 2 && bitstreamSize > 0 ==> lastCountSize == 3 */ 505 assert(fseMetadata->lastCountSize + bitstreamSize == 3); 506 DEBUGLOG(5, "Avoiding bug in zstd decoder in versions <= 1.3.4 by " 507 "emitting an uncompressed block."); 508 return 0; 509 } 510 #endif 511 DEBUGLOG(5, "ZSTD_compressSubBlock_sequences (bitstreamSize=%zu)", bitstreamSize); 512 } 513 514 /* zstd versions <= 1.4.0 mistakenly report error when 515 * sequences section body size is less than 3 bytes. 516 * Fixed by https://github.com/facebook/zstd/pull/1664. 517 * This can happen when the previous sequences section block is compressed 518 * with rle mode and the current block's sequences section is compressed 519 * with repeat mode where sequences section body size can be 1 byte. 520 */ 521 #ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 522 if (op-seqHead < 4) { 523 DEBUGLOG(5, "Avoiding bug in zstd decoder in versions <= 1.4.0 by emitting " 524 "an uncompressed block when sequences are < 4 bytes"); 525 return 0; 526 } 527 #endif 528 529 *entropyWritten = 1; 530 return op - ostart; 531 } 532 533 /* ZSTD_compressSubBlock() : 534 * Compresses a single sub-block. 535 * @return : compressed size of the sub-block 536 * Or 0 if it failed to compress. */ 537 static size_t ZSTD_compressSubBlock(const ZSTD_entropyCTables_t* entropy, 538 const ZSTD_entropyCTablesMetadata_t* entropyMetadata, 539 const seqDef* sequences, size_t nbSeq, 540 const BYTE* literals, size_t litSize, 541 const BYTE* llCode, const BYTE* mlCode, const BYTE* ofCode, 542 const ZSTD_CCtx_params* cctxParams, 543 void* dst, size_t dstCapacity, 544 const int bmi2, 545 int writeLitEntropy, int writeSeqEntropy, 546 int* litEntropyWritten, int* seqEntropyWritten, 547 U32 lastBlock) 548 { 549 BYTE* const ostart = (BYTE*)dst; 550 BYTE* const oend = ostart + dstCapacity; 551 BYTE* op = ostart + ZSTD_blockHeaderSize; 552 DEBUGLOG(5, "ZSTD_compressSubBlock (litSize=%zu, nbSeq=%zu, writeLitEntropy=%d, writeSeqEntropy=%d, lastBlock=%d)", 553 litSize, nbSeq, writeLitEntropy, writeSeqEntropy, lastBlock); 554 { size_t cLitSize = ZSTD_compressSubBlock_literal((const HUF_CElt*)entropy->huf.CTable, 555 &entropyMetadata->hufMetadata, literals, litSize, 556 op, oend-op, bmi2, writeLitEntropy, litEntropyWritten); 557 FORWARD_IF_ERROR(cLitSize, "ZSTD_compressSubBlock_literal failed"); 558 if (cLitSize == 0) return 0; 559 op += cLitSize; 560 } 561 { size_t cSeqSize = ZSTD_compressSubBlock_sequences(&entropy->fse, 562 &entropyMetadata->fseMetadata, 563 sequences, nbSeq, 564 llCode, mlCode, ofCode, 565 cctxParams, 566 op, oend-op, 567 bmi2, writeSeqEntropy, seqEntropyWritten); 568 FORWARD_IF_ERROR(cSeqSize, "ZSTD_compressSubBlock_sequences failed"); 569 if (cSeqSize == 0) return 0; 570 op += cSeqSize; 571 } 572 /* Write block header */ 573 { size_t cSize = (op-ostart)-ZSTD_blockHeaderSize; 574 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3); 575 MEM_writeLE24(ostart, cBlockHeader24); 576 } 577 return op-ostart; 578 } 579 580 static size_t ZSTD_estimateSubBlockSize_literal(const BYTE* literals, size_t litSize, 581 const ZSTD_hufCTables_t* huf, 582 const ZSTD_hufCTablesMetadata_t* hufMetadata, 583 void* workspace, size_t wkspSize, 584 int writeEntropy) 585 { 586 unsigned* const countWksp = (unsigned*)workspace; 587 unsigned maxSymbolValue = 255; 588 size_t literalSectionHeaderSize = 3; /* Use hard coded size of 3 bytes */ 589 590 if (hufMetadata->hType == set_basic) return litSize; 591 else if (hufMetadata->hType == set_rle) return 1; 592 else if (hufMetadata->hType == set_compressed || hufMetadata->hType == set_repeat) { 593 size_t const largest = HIST_count_wksp (countWksp, &maxSymbolValue, (const BYTE*)literals, litSize, workspace, wkspSize); 594 if (ZSTD_isError(largest)) return litSize; 595 { size_t cLitSizeEstimate = HUF_estimateCompressedSize((const HUF_CElt*)huf->CTable, countWksp, maxSymbolValue); 596 if (writeEntropy) cLitSizeEstimate += hufMetadata->hufDesSize; 597 return cLitSizeEstimate + literalSectionHeaderSize; 598 } } 599 assert(0); /* impossible */ 600 return 0; 601 } 602 603 static size_t ZSTD_estimateSubBlockSize_symbolType(symbolEncodingType_e type, 604 const BYTE* codeTable, unsigned maxCode, 605 size_t nbSeq, const FSE_CTable* fseCTable, 606 const U32* additionalBits, 607 short const* defaultNorm, U32 defaultNormLog, U32 defaultMax, 608 void* workspace, size_t wkspSize) 609 { 610 unsigned* const countWksp = (unsigned*)workspace; 611 const BYTE* ctp = codeTable; 612 const BYTE* const ctStart = ctp; 613 const BYTE* const ctEnd = ctStart + nbSeq; 614 size_t cSymbolTypeSizeEstimateInBits = 0; 615 unsigned max = maxCode; 616 617 HIST_countFast_wksp(countWksp, &max, codeTable, nbSeq, workspace, wkspSize); /* can't fail */ 618 if (type == set_basic) { 619 /* We selected this encoding type, so it must be valid. */ 620 assert(max <= defaultMax); 621 cSymbolTypeSizeEstimateInBits = max <= defaultMax 622 ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, countWksp, max) 623 : ERROR(GENERIC); 624 } else if (type == set_rle) { 625 cSymbolTypeSizeEstimateInBits = 0; 626 } else if (type == set_compressed || type == set_repeat) { 627 cSymbolTypeSizeEstimateInBits = ZSTD_fseBitCost(fseCTable, countWksp, max); 628 } 629 if (ZSTD_isError(cSymbolTypeSizeEstimateInBits)) return nbSeq * 10; 630 while (ctp < ctEnd) { 631 if (additionalBits) cSymbolTypeSizeEstimateInBits += additionalBits[*ctp]; 632 else cSymbolTypeSizeEstimateInBits += *ctp; /* for offset, offset code is also the number of additional bits */ 633 ctp++; 634 } 635 return cSymbolTypeSizeEstimateInBits / 8; 636 } 637 638 static size_t ZSTD_estimateSubBlockSize_sequences(const BYTE* ofCodeTable, 639 const BYTE* llCodeTable, 640 const BYTE* mlCodeTable, 641 size_t nbSeq, 642 const ZSTD_fseCTables_t* fseTables, 643 const ZSTD_fseCTablesMetadata_t* fseMetadata, 644 void* workspace, size_t wkspSize, 645 int writeEntropy) 646 { 647 size_t sequencesSectionHeaderSize = 3; /* Use hard coded size of 3 bytes */ 648 size_t cSeqSizeEstimate = 0; 649 cSeqSizeEstimate += ZSTD_estimateSubBlockSize_symbolType(fseMetadata->ofType, ofCodeTable, MaxOff, 650 nbSeq, fseTables->offcodeCTable, NULL, 651 OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff, 652 workspace, wkspSize); 653 cSeqSizeEstimate += ZSTD_estimateSubBlockSize_symbolType(fseMetadata->llType, llCodeTable, MaxLL, 654 nbSeq, fseTables->litlengthCTable, LL_bits, 655 LL_defaultNorm, LL_defaultNormLog, MaxLL, 656 workspace, wkspSize); 657 cSeqSizeEstimate += ZSTD_estimateSubBlockSize_symbolType(fseMetadata->mlType, mlCodeTable, MaxML, 658 nbSeq, fseTables->matchlengthCTable, ML_bits, 659 ML_defaultNorm, ML_defaultNormLog, MaxML, 660 workspace, wkspSize); 661 if (writeEntropy) cSeqSizeEstimate += fseMetadata->fseTablesSize; 662 return cSeqSizeEstimate + sequencesSectionHeaderSize; 663 } 664 665 static size_t ZSTD_estimateSubBlockSize(const BYTE* literals, size_t litSize, 666 const BYTE* ofCodeTable, 667 const BYTE* llCodeTable, 668 const BYTE* mlCodeTable, 669 size_t nbSeq, 670 const ZSTD_entropyCTables_t* entropy, 671 const ZSTD_entropyCTablesMetadata_t* entropyMetadata, 672 void* workspace, size_t wkspSize, 673 int writeLitEntropy, int writeSeqEntropy) { 674 size_t cSizeEstimate = 0; 675 cSizeEstimate += ZSTD_estimateSubBlockSize_literal(literals, litSize, 676 &entropy->huf, &entropyMetadata->hufMetadata, 677 workspace, wkspSize, writeLitEntropy); 678 cSizeEstimate += ZSTD_estimateSubBlockSize_sequences(ofCodeTable, llCodeTable, mlCodeTable, 679 nbSeq, &entropy->fse, &entropyMetadata->fseMetadata, 680 workspace, wkspSize, writeSeqEntropy); 681 return cSizeEstimate + ZSTD_blockHeaderSize; 682 } 683 684 static int ZSTD_needSequenceEntropyTables(ZSTD_fseCTablesMetadata_t const* fseMetadata) 685 { 686 if (fseMetadata->llType == set_compressed || fseMetadata->llType == set_rle) 687 return 1; 688 if (fseMetadata->mlType == set_compressed || fseMetadata->mlType == set_rle) 689 return 1; 690 if (fseMetadata->ofType == set_compressed || fseMetadata->ofType == set_rle) 691 return 1; 692 return 0; 693 } 694 695 /* ZSTD_compressSubBlock_multi() : 696 * Breaks super-block into multiple sub-blocks and compresses them. 697 * Entropy will be written to the first block. 698 * The following blocks will use repeat mode to compress. 699 * All sub-blocks are compressed blocks (no raw or rle blocks). 700 * @return : compressed size of the super block (which is multiple ZSTD blocks) 701 * Or 0 if it failed to compress. */ 702 static size_t ZSTD_compressSubBlock_multi(const seqStore_t* seqStorePtr, 703 const ZSTD_compressedBlockState_t* prevCBlock, 704 ZSTD_compressedBlockState_t* nextCBlock, 705 const ZSTD_entropyCTablesMetadata_t* entropyMetadata, 706 const ZSTD_CCtx_params* cctxParams, 707 void* dst, size_t dstCapacity, 708 const void* src, size_t srcSize, 709 const int bmi2, U32 lastBlock, 710 void* workspace, size_t wkspSize) 711 { 712 const seqDef* const sstart = seqStorePtr->sequencesStart; 713 const seqDef* const send = seqStorePtr->sequences; 714 const seqDef* sp = sstart; 715 const BYTE* const lstart = seqStorePtr->litStart; 716 const BYTE* const lend = seqStorePtr->lit; 717 const BYTE* lp = lstart; 718 BYTE const* ip = (BYTE const*)src; 719 BYTE const* const iend = ip + srcSize; 720 BYTE* const ostart = (BYTE*)dst; 721 BYTE* const oend = ostart + dstCapacity; 722 BYTE* op = ostart; 723 const BYTE* llCodePtr = seqStorePtr->llCode; 724 const BYTE* mlCodePtr = seqStorePtr->mlCode; 725 const BYTE* ofCodePtr = seqStorePtr->ofCode; 726 size_t targetCBlockSize = cctxParams->targetCBlockSize; 727 size_t litSize, seqCount; 728 int writeLitEntropy = entropyMetadata->hufMetadata.hType == set_compressed; 729 int writeSeqEntropy = 1; 730 int lastSequence = 0; 731 732 DEBUGLOG(5, "ZSTD_compressSubBlock_multi (litSize=%u, nbSeq=%u)", 733 (unsigned)(lend-lp), (unsigned)(send-sstart)); 734 735 litSize = 0; 736 seqCount = 0; 737 do { 738 size_t cBlockSizeEstimate = 0; 739 if (sstart == send) { 740 lastSequence = 1; 741 } else { 742 const seqDef* const sequence = sp + seqCount; 743 lastSequence = sequence == send - 1; 744 litSize += ZSTD_getSequenceLength(seqStorePtr, sequence).litLength; 745 seqCount++; 746 } 747 if (lastSequence) { 748 assert(lp <= lend); 749 assert(litSize <= (size_t)(lend - lp)); 750 litSize = (size_t)(lend - lp); 751 } 752 /* I think there is an optimization opportunity here. 753 * Calling ZSTD_estimateSubBlockSize for every sequence can be wasteful 754 * since it recalculates estimate from scratch. 755 * For example, it would recount literal distribution and symbol codes everytime. 756 */ 757 cBlockSizeEstimate = ZSTD_estimateSubBlockSize(lp, litSize, ofCodePtr, llCodePtr, mlCodePtr, seqCount, 758 &nextCBlock->entropy, entropyMetadata, 759 workspace, wkspSize, writeLitEntropy, writeSeqEntropy); 760 if (cBlockSizeEstimate > targetCBlockSize || lastSequence) { 761 int litEntropyWritten = 0; 762 int seqEntropyWritten = 0; 763 const size_t decompressedSize = ZSTD_seqDecompressedSize(seqStorePtr, sp, seqCount, litSize, lastSequence); 764 const size_t cSize = ZSTD_compressSubBlock(&nextCBlock->entropy, entropyMetadata, 765 sp, seqCount, 766 lp, litSize, 767 llCodePtr, mlCodePtr, ofCodePtr, 768 cctxParams, 769 op, oend-op, 770 bmi2, writeLitEntropy, writeSeqEntropy, 771 &litEntropyWritten, &seqEntropyWritten, 772 lastBlock && lastSequence); 773 FORWARD_IF_ERROR(cSize, "ZSTD_compressSubBlock failed"); 774 if (cSize > 0 && cSize < decompressedSize) { 775 DEBUGLOG(5, "Committed the sub-block"); 776 assert(ip + decompressedSize <= iend); 777 ip += decompressedSize; 778 sp += seqCount; 779 lp += litSize; 780 op += cSize; 781 llCodePtr += seqCount; 782 mlCodePtr += seqCount; 783 ofCodePtr += seqCount; 784 litSize = 0; 785 seqCount = 0; 786 /* Entropy only needs to be written once */ 787 if (litEntropyWritten) { 788 writeLitEntropy = 0; 789 } 790 if (seqEntropyWritten) { 791 writeSeqEntropy = 0; 792 } 793 } 794 } 795 } while (!lastSequence); 796 if (writeLitEntropy) { 797 DEBUGLOG(5, "ZSTD_compressSubBlock_multi has literal entropy tables unwritten"); 798 ZSTD_memcpy(&nextCBlock->entropy.huf, &prevCBlock->entropy.huf, sizeof(prevCBlock->entropy.huf)); 799 } 800 if (writeSeqEntropy && ZSTD_needSequenceEntropyTables(&entropyMetadata->fseMetadata)) { 801 /* If we haven't written our entropy tables, then we've violated our contract and 802 * must emit an uncompressed block. 803 */ 804 DEBUGLOG(5, "ZSTD_compressSubBlock_multi has sequence entropy tables unwritten"); 805 return 0; 806 } 807 if (ip < iend) { 808 size_t const cSize = ZSTD_noCompressBlock(op, oend - op, ip, iend - ip, lastBlock); 809 DEBUGLOG(5, "ZSTD_compressSubBlock_multi last sub-block uncompressed, %zu bytes", (size_t)(iend - ip)); 810 FORWARD_IF_ERROR(cSize, "ZSTD_noCompressBlock failed"); 811 assert(cSize != 0); 812 op += cSize; 813 /* We have to regenerate the repcodes because we've skipped some sequences */ 814 if (sp < send) { 815 seqDef const* seq; 816 repcodes_t rep; 817 ZSTD_memcpy(&rep, prevCBlock->rep, sizeof(rep)); 818 for (seq = sstart; seq < sp; ++seq) { 819 rep = ZSTD_updateRep(rep.rep, seq->offset - 1, ZSTD_getSequenceLength(seqStorePtr, seq).litLength == 0); 820 } 821 ZSTD_memcpy(nextCBlock->rep, &rep, sizeof(rep)); 822 } 823 } 824 DEBUGLOG(5, "ZSTD_compressSubBlock_multi compressed"); 825 return op-ostart; 826 } 827 828 size_t ZSTD_compressSuperBlock(ZSTD_CCtx* zc, 829 void* dst, size_t dstCapacity, 830 void const* src, size_t srcSize, 831 unsigned lastBlock) { 832 ZSTD_entropyCTablesMetadata_t entropyMetadata; 833 834 FORWARD_IF_ERROR(ZSTD_buildSuperBlockEntropy(&zc->seqStore, 835 &zc->blockState.prevCBlock->entropy, 836 &zc->blockState.nextCBlock->entropy, 837 &zc->appliedParams, 838 &entropyMetadata, 839 zc->entropyWorkspace, ENTROPY_WORKSPACE_SIZE /* statically allocated in resetCCtx */), ""); 840 841 return ZSTD_compressSubBlock_multi(&zc->seqStore, 842 zc->blockState.prevCBlock, 843 zc->blockState.nextCBlock, 844 &entropyMetadata, 845 &zc->appliedParams, 846 dst, dstCapacity, 847 src, srcSize, 848 zc->bmi2, lastBlock, 849 zc->entropyWorkspace, ENTROPY_WORKSPACE_SIZE /* statically allocated in resetCCtx */); 850 } 851