zstd/compress/huf_compress.c

287  * Enforces maxNbBits on the Huffman tree described in huffNode.
293  *                    where largestBits == huffNode[lastNonNull].nbBits.
297  * @param huffNode    The Huffman tree modified in place to enforce maxNbBits.
305 static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits)
307     const U32 largestBits = huffNode[lastNonNull].nbBits;
320         while (huffNode[n].nbBits > maxNbBits) {
321             totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
322             huffNode[n].nbBits = (BYTE)maxNbBits;
325         /* n stops at huffNode[n].nbBits <= maxNbBits */
326         assert(huffNode[n].nbBits <= maxNbBits);
328         while (huffNode[n].nbBits == maxNbBits) --n;
345                     if (huffNode[pos].nbBits >= currentNbBits) continue;
346                     currentNbBits = huffNode[pos].nbBits;   /* < maxNbBits */
363                     {   U32 const highTotal = huffNode[highPos].count;
364                         U32 const lowTotal = 2 * huffNode[lowPos].count;
375                 huffNode[rankLast[nBitsToDecrease]].nbBits++;
394                     if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
410                     while (huffNode[n].nbBits == maxNbBits) n--;
411                     huffNode[n+1].nbBits--;
417                 huffNode[ rankLast[1] + 1 ].nbBits--;
470 /* Returns 0 if the huffNode array is not sorted by descending count */
471 MEM_STATIC int HUF_isSorted(nodeElt huffNode[], U32 const maxSymbolValue1) {
474         if (huffNode[i].count > huffNode[i-1].count) {
482 HINT_INLINE void HUF_insertionSort(nodeElt huffNode[], int const low, int const high) {
485     huffNode += low;
487         nodeElt const key = huffNode[i];
489         while (j >= 0 && huffNode[j].count < key.count) {
490             huffNode[j + 1] = huffNode[j];
493         huffNode[j + 1] = key;
541  * @param[out] huffNode       Sorted symbols by decreasing count. Only members `.count` and `.byte` are filled.
547 static void HUF_sort(nodeElt huffNode[], const unsigned count[], U32 const maxSymbolValue, rankPos rankPosition[]) {
577         huffNode[pos].count = c;
578         huffNode[pos].byte  = (BYTE)n;
587             HUF_simpleQuickSort(huffNode + bucketStartIdx, 0, bucketSize-1);
591     assert(HUF_isSorted(huffNode, maxSymbolValue1));
601  * Takes the huffNode array sorted by HUF_sort() and builds an unlimited-depth Huffman tree.
603  * @param huffNode        The array sorted by HUF_sort(). Builds the Huffman tree in this array.
607 static int HUF_buildTree(nodeElt* huffNode, U32 maxSymbolValue)
609     nodeElt* const huffNode0 = huffNode - 1;
616     while(huffNode[nonNullRank].count == 0) nonNullRank--;
618     huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count;
619     huffNode[lowS].parent = huffNode[lowS-1].parent = (U16)nodeNb;
621     for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30);
626         int const n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
627         int const n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
628         huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count;
629         huffNode[n1].parent = huffNode[n2].parent = (U16)nodeNb;
634     huffNode[nodeRoot].nbBits = 0;
636         huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
638         huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
645  * Build the CTable given the Huffman tree in huffNode.
648  * @param      huffNode       The Huffman tree.
653 static void HUF_buildCTableFromTree(HUF_CElt* CTable, nodeElt const* huffNode, int nonNullRank, U32 maxSymbolValue, U32 maxNbBits)
662         nbPerRank[huffNode[n].nbBits]++;
671         HUF_setNbBits(ct + huffNode[n].byte, huffNode[n].nbBits);   /* push nbBits per symbol, symbol order */
681     nodeElt* const huffNode = huffNode0+1;
693     HUF_sort(huffNode, count, maxSymbolValue, wksp_tables->rankPosition);
696     nonNullRank = HUF_buildTree(huffNode, maxSymbolValue);
699     maxNbBits = HUF_setMaxHeight(huffNode, (U32)nonNullRank, maxNbBits);
702     HUF_buildCTableFromTree(CTable, huffNode, nonNullRank, maxSymbolValue, maxNbBits);