zstd/compress/huf_compress.c

287  * Enforces maxNbBits on the Huffman tree described in huffNode.
289  * It sets all nodes with nbBits > maxNbBits to be maxNbBits. Then it adjusts
295  *                    where largestBits is the return value <= maxNbBits.
297  * @param huffNode    The Huffman tree modified in place to enforce maxNbBits.
299  * @param maxNbBits   The maximum allowed number of bits, which the Huffman tree
301  *                    respect maxNbBits.
303  *                    necessarily no more than maxNbBits.
305 static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits)
308     /* early exit : no elt > maxNbBits, so the tree is already valid. */
309     if (largestBits <= maxNbBits) return largestBits;
313         const U32 baseCost = 1 << (largestBits - maxNbBits);
316         /* Adjust any ranks > maxNbBits to maxNbBits.
320         while (huffNode[n].nbBits > maxNbBits) {
322             huffNode[n].nbBits = (BYTE)maxNbBits;
325         /* n stops at huffNode[n].nbBits <= maxNbBits */
326         assert(huffNode[n].nbBits <= maxNbBits);
327         /* n end at index of smallest symbol using < maxNbBits */
328         while (huffNode[n].nbBits == maxNbBits) --n;
330         /* renorm totalCost from 2^largestBits to 2^maxNbBits
333         totalCost >>= (largestBits - maxNbBits);
342             {   U32 currentNbBits = maxNbBits;
346                     currentNbBits = huffNode[pos].nbBits;   /* < maxNbBits */
347                     rankLast[maxNbBits-currentNbBits] = (U32)pos;
394                     if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
406                 /* special case : no rank 1 symbol (using maxNbBits-1);
407                  * let's create one from largest rank 0 (using maxNbBits).
410                     while (huffNode[n].nbBits == maxNbBits) n--;
424     return maxNbBits;
651  * @param      maxNbBits      The exact maximum number of bits used in the Huffman tree.
653 static void HUF_buildCTableFromTree(HUF_CElt* CTable, nodeElt const* huffNode, int nonNullRank, U32 maxSymbolValue, U32 maxNbBits)
665         for (n=(int)maxNbBits; n>0; n--) {
674     CTable[0] = maxNbBits;
677 size_t HUF_buildCTable_wksp (HUF_CElt* CTable, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
687     if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
699     maxNbBits = HUF_setMaxHeight(huffNode, (U32)nonNullRank, maxNbBits);
700     if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC);   /* check fit into table */
702     HUF_buildCTableFromTree(CTable, huffNode, nonNullRank, maxSymbolValue, maxNbBits);
704     return maxNbBits;