1 // SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause
6  * This source code is licensed under both the BSD-style license (found in the
9  * You may select, at your option, one of the above-listed licenses.
12  /*-*************************************
18  * -log2(x / 256) lookup table for x in [0, 256).
20  * Else: Return floor(-log2(x / 256) * 256)
44     5,    4,    2,    1,
55  * Returns true if we should use ncount=-1 else we should
74     BYTE wksp[FSE_NCOUNTBOUND];  in ZSTD_NCountCost()
116         DEBUGLOG(5, "Repeat FSE_CTable has maxSymbolValue %u < %u",  in ZSTD_fseBitCost()
127             DEBUGLOG(5, "Repeat FSE_CTable has Prob[%u] == 0", s);  in ZSTD_fseBitCost()
138  * norm must be valid for every symbol with non-zero probability in count.
143     unsigned const shift = 8 - accuracyLog;  in ZSTD_crossEntropyCost()
148         unsigned const normAcc = (norm[s] != -1) ? (unsigned)norm[s] : 1;  in ZSTD_crossEntropyCost()
171              * since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.  in ZSTD_selectEncodingType()
174             DEBUGLOG(5, "Selected set_basic");  in ZSTD_selectEncodingType()
177         DEBUGLOG(5, "Selected set_rle");  in ZSTD_selectEncodingType()
183             size_t const mult = 10 - strategy;  in ZSTD_selectEncodingType()
185 …Seq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog;  /* 28-36 for offset, 56-72 for lengt…  in ZSTD_selectEncodingType()
186             assert(defaultNormLog >= 5 && defaultNormLog <= 6);  /* xx_DEFAULTNORMLOG */  in ZSTD_selectEncodingType()
190                 DEBUGLOG(5, "Selected set_repeat");  in ZSTD_selectEncodingType()
194               || (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {  in ZSTD_selectEncodingType()
195                 DEBUGLOG(5, "Selected set_basic");  in ZSTD_selectEncodingType()
218         DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",  in ZSTD_selectEncodingType()
221             DEBUGLOG(5, "Selected set_basic");  in ZSTD_selectEncodingType()
227             DEBUGLOG(5, "Selected set_repeat");  in ZSTD_selectEncodingType()
233     DEBUGLOG(5, "Selected set_compressed");  in ZSTD_selectEncodingType()
247                 const BYTE* codeTable, size_t nbSeq,  in ZSTD_buildCTable()
252     BYTE* op = (BYTE*)dst;  in ZSTD_buildCTable()
253     const BYTE* const oend = op + dstCapacity;  in ZSTD_buildCTable()
258         FORWARD_IF_ERROR(FSE_buildCTable_rle(nextCTable, (BYTE)max), "");  in ZSTD_buildCTable()
266 …defaultNormLog, entropyWorkspace, entropyWorkspaceSize), "");  /* note : could be pre-calculated */  in ZSTD_buildCTable()
272         if (count[codeTable[nbSeq-1]] > 1) {  in ZSTD_buildCTable()
273             count[codeTable[nbSeq-1]]--;  in ZSTD_buildCTable()
274             nbSeq_1--;  in ZSTD_buildCTable()
279 …FORWARD_IF_ERROR(FSE_normalizeCount(wksp->norm, tableLog, count, nbSeq_1, max, ZSTD_useLowProbCoun…  in ZSTD_buildCTable()
281 …{   size_t const NCountSize = FSE_writeNCount(op, (size_t)(oend - op), wksp->norm, max, tableLog);…  in ZSTD_buildCTable()
283 …ORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, wksp->norm, max, tableLog, wksp->wksp, sizeof(wks…  in ZSTD_buildCTable()
294             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,  in ZSTD_encodeSequences_body()
295             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,  in ZSTD_encodeSequences_body()
296             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,  in ZSTD_encodeSequences_body()
308                 (int)(blockStream.endPtr - blockStream.startPtr),  in ZSTD_encodeSequences_body()
312     FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);  in ZSTD_encodeSequences_body()
313     FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);  in ZSTD_encodeSequences_body()
314     FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);  in ZSTD_encodeSequences_body()
315     BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);  in ZSTD_encodeSequences_body()
317     BIT_addBits(&blockStream, sequences[nbSeq-1].mlBase, ML_bits[mlCodeTable[nbSeq-1]]);  in ZSTD_encodeSequences_body()
320         U32 const ofBits = ofCodeTable[nbSeq-1];  in ZSTD_encodeSequences_body()
321         unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);  in ZSTD_encodeSequences_body()
323             BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, extraBits);  in ZSTD_encodeSequences_body()
326         BIT_addBits(&blockStream, sequences[nbSeq-1].offBase >> extraBits,  in ZSTD_encodeSequences_body()
327                     ofBits - extraBits);  in ZSTD_encodeSequences_body()
329         BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, ofCodeTable[nbSeq-1]);  in ZSTD_encodeSequences_body()
334         for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */  in ZSTD_encodeSequences_body()
335             BYTE const llCode = llCodeTable[n];  in ZSTD_encodeSequences_body()
336             BYTE const ofCode = ofCodeTable[n];  in ZSTD_encodeSequences_body()
337             BYTE const mlCode = mlCodeTable[n];  in ZSTD_encodeSequences_body()
341             DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",  in ZSTD_encodeSequences_body()
351             if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))  in ZSTD_encodeSequences_body()
358                 unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);  in ZSTD_encodeSequences_body()
364                             ofBits - extraBits);                            /* 31 */  in ZSTD_encodeSequences_body()
369             DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));  in ZSTD_encodeSequences_body()
388             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,  in ZSTD_encodeSequences_default()
389             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,  in ZSTD_encodeSequences_default()
390             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,  in ZSTD_encodeSequences_default()
406             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,  in ZSTD_encodeSequences_bmi2()
407             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,  in ZSTD_encodeSequences_bmi2()
408             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,  in ZSTD_encodeSequences_bmi2()
422             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,  in ZSTD_encodeSequences()
423             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,  in ZSTD_encodeSequences()
424             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,  in ZSTD_encodeSequences()
427     DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);  in ZSTD_encodeSequences()