< Summary

Information
Class: System.IO.Compression.HuffmanTree
Assembly: System.IO.Compression
File(s): https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.IO.Compression/src/System/IO/Compression/DeflateManaged/HuffmanTree.cs
Line coverage
98%
Covered lines: 158
Uncovered lines: 2
Coverable lines: 160
Total lines: 324
Line coverage: 98.7%
Branch coverage
96%
Covered branches: 48
Total branches: 50
Branch coverage: 96%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity NPath complexity Sequence coverage
.ctor(...)100%66100%
GetStaticLiteralTreeLength()100%11100%
GetStaticDistanceTreeLength()100%11100%
BitReverse(...)75%44100%
CalculateHuffmanCode()100%88100%
CreateTable()95%202096.61%
GetNextSymbol(...)100%1212100%

File(s)

https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.IO.Compression/src/System/IO/Compression/DeflateManaged/HuffmanTree.cs

#LineLine coverage
 1// Licensed to the .NET Foundation under one or more agreements.
 2// The .NET Foundation licenses this file to you under the MIT license.
 3
 4using System.Diagnostics;
 5
 6namespace System.IO.Compression
 7{
 8    // Strictly speaking this class is not a HuffmanTree, this class is
 9    // a lookup table combined with a HuffmanTree. The idea is to speed up
 10    // the lookup for short symbols (they should appear more frequently ideally.)
 11    // However we don't want to create a huge table since it might take longer to
 12    // build the table than decoding (Deflate usually generates new tables frequently.)
 13    //
 14    // Jean-loup Gailly and Mark Adler gave a very good explanation about this.
 15    // The full text (algorithm.txt) can be found inside
 16    // ftp://ftp.uu.net/pub/archiving/zip/zlib/zlib.zip.
 17    //
 18    // Following paper explains decoding in details:
 19    //   Hirschberg and Lelewer, "Efficient decoding of prefix codes,"
 20    //   Comm. ACM, 33,4, April 1990, pp. 449-459.
 21    //
 22
 23    internal sealed class HuffmanTree
 24    {
 25        internal const int MaxLiteralTreeElements = 288;
 26        internal const int MaxDistTreeElements = 32;
 27        internal const int EndOfBlockCode = 256;
 28        internal const int NumberOfCodeLengthTreeElements = 19;
 29
 30        private readonly int _tableBits;
 31        private readonly short[] _table;
 32        private readonly short[] _left;
 33        private readonly short[] _right;
 34        private readonly byte[] _codeLengthArray;
 35#if DEBUG
 36        private uint[]? _codeArrayDebug;
 37#endif
 38
 39        private readonly int _tableMask;
 40
 41        // huffman tree for static block
 400742        public static HuffmanTree StaticLiteralLengthTree { get; } = new HuffmanTree(GetStaticLiteralTreeLength());
 43
 400744        public static HuffmanTree StaticDistanceTree { get; } = new HuffmanTree(GetStaticDistanceTreeLength());
 45
 699046        public HuffmanTree(byte[] codeLengths)
 699047        {
 699048            Debug.Assert(
 699049                codeLengths.Length == MaxLiteralTreeElements ||
 699050                codeLengths.Length == MaxDistTreeElements ||
 699051                codeLengths.Length == NumberOfCodeLengthTreeElements,
 699052                "we only expect three kinds of Length here");
 699053            _codeLengthArray = codeLengths;
 54
 699055            if (_codeLengthArray.Length == MaxLiteralTreeElements)
 195556            {
 57                // bits for Literal/Length tree table
 195558                _tableBits = 9;
 195559            }
 60            else
 503561            {
 62                // bits for distance tree table and code length tree table
 503563                _tableBits = 7;
 503564            }
 699065            _tableMask = (1 << _tableBits) - 1;
 66
 699067            _table = new short[1 << _tableBits];
 68
 69            // I need to find proof that left and right array will always be
 70            // enough. I think they are.
 699071            _left = new short[2 * _codeLengthArray.Length];
 699072            _right = new short[2 * _codeLengthArray.Length];
 73
 699074            CreateTable();
 664075        }
 76
 77        // Generate the array contains huffman codes lengths for static huffman tree.
 78        // The data is in RFC 1951.
 79        private static byte[] GetStaticLiteralTreeLength()
 180        {
 181            byte[] literalTreeLength = new byte[MaxLiteralTreeElements];
 82
 183            literalTreeLength.AsSpan(0, 144).Fill(8);
 184            literalTreeLength.AsSpan(144, 112).Fill(9);
 185            literalTreeLength.AsSpan(256, 24).Fill(7);
 186            literalTreeLength.AsSpan(280, 8).Fill(8);
 187            return literalTreeLength;
 188        }
 89
 90        private static byte[] GetStaticDistanceTreeLength()
 191        {
 192            byte[] staticDistanceTreeLength = new byte[MaxDistTreeElements];
 193            Array.Fill(staticDistanceTreeLength, (byte)5);
 194            return staticDistanceTreeLength;
 195        }
 96
 97        // Reverse 'length' of the bits in code
 98        private static uint BitReverse(uint code, int length)
 26130699        {
 261306100            uint new_code = 0;
 101
 261306102            Debug.Assert(length > 0 && length <= 16, "Invalid len");
 103            do
 2028788104            {
 2028788105                new_code |= (code & 1);
 2028788106                new_code <<= 1;
 2028788107                code >>= 1;
 4057576108            } while (--length > 0);
 109
 261306110            return new_code >> 1;
 261306111        }
 112
 113        // Calculate the huffman code for each character based on the code length for each character.
 114        // This algorithm is described in standard RFC 1951
 115        private unsafe uint[] CalculateHuffmanCode()
 6990116        {
 6990117            Span<uint> bitLengthCount = stackalloc uint[17];
 6990118            bitLengthCount.Clear();
 1381618119            foreach (int codeLength in _codeLengthArray)
 680324120            {
 680324121                bitLengthCount[codeLength]++;
 680324122            }
 6990123            bitLengthCount[0] = 0;  // clear count for length 0
 124
 6990125            Span<uint> nextCode = stackalloc uint[17];
 6990126            nextCode.Clear();
 6990127            uint tempCode = 0;
 237660128            for (int bits = 1; bits <= 16; bits++)
 111840129            {
 111840130                tempCode = (tempCode + bitLengthCount[bits - 1]) << 1;
 111840131                nextCode[bits] = tempCode;
 111840132            }
 133
 6990134            uint[] code = new uint[MaxLiteralTreeElements];
 1374628135            for (int i = 0; i < _codeLengthArray.Length; i++)
 680324136            {
 680324137                int len = _codeLengthArray[i];
 138
 680324139                if (len > 0)
 261306140                {
 261306141                    code[i] = BitReverse(nextCode[len], len);
 261306142                    nextCode[len]++;
 261306143                }
 680324144            }
 6990145            return code;
 6990146        }
 147
 148        private void CreateTable()
 6990149        {
 6990150            uint[] codeArray = CalculateHuffmanCode();
 151#if DEBUG
 6990152            _codeArrayDebug = codeArray;
 153#endif
 154
 6990155            short avail = (short)_codeLengthArray.Length;
 156
 1301492157            for (int ch = 0; ch < _codeLengthArray.Length; ch++)
 644106158            {
 159                // length of this code
 644106160                int len = _codeLengthArray[ch];
 644106161                if (len > 0)
 238118162                {
 163                    // start value (bit reversed)
 238118164                    int start = (int)codeArray[ch];
 165
 238118166                    if (len <= _tableBits)
 163630167                    {
 168                        // If a particular symbol is shorter than nine bits,
 169                        // then that symbol's translation is duplicated
 170                        // in all those entries that start with that symbol's bits.
 171                        // For example, if the symbol is four bits, then it's duplicated
 172                        // 32 times in a nine-bit table. If a symbol is nine bits long,
 173                        // it appears in the table once.
 174                        //
 175                        // Make sure that in the loop below, code is always
 176                        // less than table_size.
 177                        //
 178                        // On last iteration we store at array index:
 179                        //    initial_start_at + (locs-1)*increment
 180                        //  = initial_start_at + locs*increment - increment
 181                        //  = initial_start_at + (1 << tableBits) - increment
 182                        //  = initial_start_at + table_size - increment
 183                        //
 184                        // Therefore we must ensure:
 185                        //     initial_start_at + table_size - increment < table_size
 186                        // or: initial_start_at < increment
 187                        //
 163630188                        int increment = 1 << len;
 163630189                        if (start >= increment)
 0190                        {
 0191                            throw new InvalidDataException(SR.InvalidHuffmanData);
 192                        }
 193
 194                        // Note the bits in the table are reverted.
 163630195                        int locs = 1 << (_tableBits - len);
 3547496196                        for (int j = 0; j < locs; j++)
 1610118197                        {
 1610118198                            _table[start] = (short)ch;
 1610118199                            start += increment;
 1610118200                        }
 163630201                    }
 202                    else
 74488203                    {
 204                        // For any code which has length longer than num_elements,
 205                        // build a binary tree.
 206
 74488207                        int overflowBits = len - _tableBits; // the nodes we need to respent the data.
 74488208                        int codeBitMask = 1 << _tableBits; // mask to get current bit (the bits can't fit in the table)
 209
 210                        // the left, right table is used to repesent the
 211                        // the rest bits. When we got the first part (number bits.) and look at
 212                        // tbe table, we will need to follow the tree to find the real character.
 213                        // This is in place to avoid bloating the table if there are
 214                        // a few ones with long code.
 74488215                        int index = start & ((1 << _tableBits) - 1);
 74488216                        short[] array = _table;
 217
 218                        do
 199244219                        {
 199244220                            short value = array[index];
 221
 199244222                            if (value == 0)
 60910223                            {
 224                                // set up next pointer if this node is not used before.
 60910225                                array[index] = (short)-avail; // use next available slot.
 60910226                                value = (short)-avail;
 60910227                                avail++;
 60910228                            }
 229
 199244230                            if (value > 0)
 292231                            {
 232                                // prevent an IndexOutOfRangeException from array[index]
 292233                                throw new InvalidDataException(SR.InvalidHuffmanData);
 234                            }
 235
 198952236                            Debug.Assert(value < 0, "CreateTable: Only negative numbers are used for tree pointers!");
 237
 198952238                            if ((start & codeBitMask) == 0)
 101948239                            {
 240                                // if current bit is 0, go change the left array
 101948241                                array = _left;
 101948242                            }
 243                            else
 97004244                            {
 245                                // if current bit is 1, set value in the right array
 97004246                                array = _right;
 97004247                            }
 198952248                            index = -value; // go to next node
 249
 198952250                            if (index >= array.Length)
 58251                            {
 252                                // prevent an IndexOutOfRangeException from array[index]
 58253                                throw new InvalidDataException(SR.InvalidHuffmanData);
 254                            }
 255
 198894256                            codeBitMask <<= 1;
 198894257                            overflowBits--;
 397788258                        } while (overflowBits != 0);
 259
 74138260                        array[index] = (short)ch;
 74138261                    }
 237768262                }
 643756263            }
 6640264        }
 265
 266        //
 267        // This function will try to get enough bits from input and
 268        // try to decode the bits.
 269        // If there are no enought bits in the input, this function will return -1.
 270        //
 271        public int GetNextSymbol(InputBuffer input)
 752974272        {
 273            // Try to load 16 bits into input buffer if possible and get the bitBuffer value.
 274            // If there aren't 16 bits available we will return all we have in the
 275            // input buffer.
 752974276            uint bitBuffer = input.TryLoad16Bits();
 752974277            if (input.AvailableBits == 0)
 462278            {    // running out of input.
 462279                return -1;
 280            }
 281
 282            // decode an element
 752512283            int symbol = _table[bitBuffer & _tableMask];
 752512284            if (symbol < 0)
 8536285            {       //  this will be the start of the binary tree
 286                // navigate the tree
 8536287                uint mask = (uint)1 << _tableBits;
 288                do
 13188289                {
 13188290                    symbol = -symbol;
 13188291                    if ((bitBuffer & mask) == 0)
 8850292                        symbol = _left[symbol];
 293                    else
 4338294                        symbol = _right[symbol];
 13188295                    mask <<= 1;
 26376296                } while (symbol < 0);
 8536297            }
 298
 752512299            int codeLength = _codeLengthArray[symbol];
 300
 301            // huffman code lengths must be at least 1 bit long
 752512302            if (codeLength <= 0)
 312303            {
 312304                throw new InvalidDataException(SR.InvalidHuffmanData);
 305            }
 306
 307            //
 308            // If this code is longer than the # bits we had in the bit buffer (i.e.
 309            // we read only part of the code), we can hit the entry in the table or the tree
 310            // for another symbol. However the length of another symbol will not match the
 311            // available bits count.
 752200312            if (codeLength > input.AvailableBits)
 1236313            {
 314                // We already tried to load 16 bits and maximum length is 15,
 315                // so this means we are running out of input.
 1236316                return -1;
 317            }
 318
 750964319            input.SkipBits(codeLength);
 750964320            return symbol;
 752662321        }
 322    }
 323}
 324
Generated by: ReportGenerator 5.5.11.0
10/9/2026 - 4:39:51 PM
GitHub | reportgenerator.io

Methods/Properties

StaticLiteralLengthTree()
StaticDistanceTree()
.ctor(System.Byte[])
GetStaticLiteralTreeLength()
GetStaticDistanceTreeLength()
BitReverse(System.UInt32,System.Int32)
CalculateHuffmanCode()
CreateTable()
GetNextSymbol(System.IO.Compression.InputBuffer)