| | | 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 | | |
| | | 4 | | using System.Diagnostics; |
| | | 5 | | |
| | | 6 | | namespace 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 |
| | 5487 | 42 | | public static HuffmanTree StaticLiteralLengthTree { get; } = new HuffmanTree(GetStaticLiteralTreeLength()); |
| | | 43 | | |
| | 5487 | 44 | | public static HuffmanTree StaticDistanceTree { get; } = new HuffmanTree(GetStaticDistanceTreeLength()); |
| | | 45 | | |
| | 8610 | 46 | | public HuffmanTree(byte[] codeLengths) |
| | 8610 | 47 | | { |
| | 8610 | 48 | | Debug.Assert( |
| | 8610 | 49 | | codeLengths.Length == MaxLiteralTreeElements || |
| | 8610 | 50 | | codeLengths.Length == MaxDistTreeElements || |
| | 8610 | 51 | | codeLengths.Length == NumberOfCodeLengthTreeElements, |
| | 8610 | 52 | | "we only expect three kinds of Length here"); |
| | 8610 | 53 | | _codeLengthArray = codeLengths; |
| | | 54 | | |
| | 8610 | 55 | | if (_codeLengthArray.Length == MaxLiteralTreeElements) |
| | 2239 | 56 | | { |
| | | 57 | | // bits for Literal/Length tree table |
| | 2239 | 58 | | _tableBits = 9; |
| | 2239 | 59 | | } |
| | | 60 | | else |
| | 6371 | 61 | | { |
| | | 62 | | // bits for distance tree table and code length tree table |
| | 6371 | 63 | | _tableBits = 7; |
| | 6371 | 64 | | } |
| | 8610 | 65 | | _tableMask = (1 << _tableBits) - 1; |
| | | 66 | | |
| | 8610 | 67 | | _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. |
| | 8610 | 71 | | _left = new short[2 * _codeLengthArray.Length]; |
| | 8610 | 72 | | _right = new short[2 * _codeLengthArray.Length]; |
| | | 73 | | |
| | 8610 | 74 | | CreateTable(); |
| | 8222 | 75 | | } |
| | | 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() |
| | 1 | 80 | | { |
| | 1 | 81 | | byte[] literalTreeLength = new byte[MaxLiteralTreeElements]; |
| | | 82 | | |
| | 1 | 83 | | literalTreeLength.AsSpan(0, 144).Fill(8); |
| | 1 | 84 | | literalTreeLength.AsSpan(144, 112).Fill(9); |
| | 1 | 85 | | literalTreeLength.AsSpan(256, 24).Fill(7); |
| | 1 | 86 | | literalTreeLength.AsSpan(280, 8).Fill(8); |
| | 1 | 87 | | return literalTreeLength; |
| | 1 | 88 | | } |
| | | 89 | | |
| | | 90 | | private static byte[] GetStaticDistanceTreeLength() |
| | 1 | 91 | | { |
| | 1 | 92 | | byte[] staticDistanceTreeLength = Array.CreateFilled<byte>(MaxDistTreeElements, 5); |
| | 1 | 93 | | return staticDistanceTreeLength; |
| | 1 | 94 | | } |
| | | 95 | | |
| | | 96 | | // Reverse 'length' of the bits in code |
| | | 97 | | private static uint BitReverse(uint code, int length) |
| | 355204 | 98 | | { |
| | 355204 | 99 | | uint new_code = 0; |
| | | 100 | | |
| | 355204 | 101 | | Debug.Assert(length > 0 && length <= 16, "Invalid len"); |
| | | 102 | | do |
| | 2822182 | 103 | | { |
| | 2822182 | 104 | | new_code |= (code & 1); |
| | 2822182 | 105 | | new_code <<= 1; |
| | 2822182 | 106 | | code >>= 1; |
| | 5644364 | 107 | | } while (--length > 0); |
| | | 108 | | |
| | 355204 | 109 | | return new_code >> 1; |
| | 355204 | 110 | | } |
| | | 111 | | |
| | | 112 | | // Calculate the huffman code for each character based on the code length for each character. |
| | | 113 | | // This algorithm is described in standard RFC 1951 |
| | | 114 | | private unsafe uint[] CalculateHuffmanCode() |
| | 8610 | 115 | | { |
| | 8610 | 116 | | Span<uint> bitLengthCount = stackalloc uint[17]; |
| | 8610 | 117 | | bitLengthCount.Clear(); |
| | 1607642 | 118 | | foreach (int codeLength in _codeLengthArray) |
| | 790906 | 119 | | { |
| | 790906 | 120 | | bitLengthCount[codeLength]++; |
| | 790906 | 121 | | } |
| | 8610 | 122 | | bitLengthCount[0] = 0; // clear count for length 0 |
| | | 123 | | |
| | 8610 | 124 | | Span<uint> nextCode = stackalloc uint[17]; |
| | 8610 | 125 | | nextCode.Clear(); |
| | 8610 | 126 | | uint tempCode = 0; |
| | 292740 | 127 | | for (int bits = 1; bits <= 16; bits++) |
| | 137760 | 128 | | { |
| | 137760 | 129 | | tempCode = (tempCode + bitLengthCount[bits - 1]) << 1; |
| | 137760 | 130 | | nextCode[bits] = tempCode; |
| | 137760 | 131 | | } |
| | | 132 | | |
| | 8610 | 133 | | uint[] code = new uint[MaxLiteralTreeElements]; |
| | 1599032 | 134 | | for (int i = 0; i < _codeLengthArray.Length; i++) |
| | 790906 | 135 | | { |
| | 790906 | 136 | | int len = _codeLengthArray[i]; |
| | | 137 | | |
| | 790906 | 138 | | if (len > 0) |
| | 355204 | 139 | | { |
| | 355204 | 140 | | code[i] = BitReverse(nextCode[len], len); |
| | 355204 | 141 | | nextCode[len]++; |
| | 355204 | 142 | | } |
| | 790906 | 143 | | } |
| | 8610 | 144 | | return code; |
| | 8610 | 145 | | } |
| | | 146 | | |
| | | 147 | | private void CreateTable() |
| | 8610 | 148 | | { |
| | 8610 | 149 | | uint[] codeArray = CalculateHuffmanCode(); |
| | | 150 | | #if DEBUG |
| | 8610 | 151 | | _codeArrayDebug = codeArray; |
| | | 152 | | #endif |
| | | 153 | | |
| | 8610 | 154 | | short avail = (short)_codeLengthArray.Length; |
| | | 155 | | |
| | 1497772 | 156 | | for (int ch = 0; ch < _codeLengthArray.Length; ch++) |
| | 740664 | 157 | | { |
| | | 158 | | // length of this code |
| | 740664 | 159 | | int len = _codeLengthArray[ch]; |
| | 740664 | 160 | | if (len > 0) |
| | 314710 | 161 | | { |
| | | 162 | | // start value (bit reversed) |
| | 314710 | 163 | | int start = (int)codeArray[ch]; |
| | | 164 | | |
| | 314710 | 165 | | if (len <= _tableBits) |
| | 229064 | 166 | | { |
| | | 167 | | // If a particular symbol is shorter than nine bits, |
| | | 168 | | // then that symbol's translation is duplicated |
| | | 169 | | // in all those entries that start with that symbol's bits. |
| | | 170 | | // For example, if the symbol is four bits, then it's duplicated |
| | | 171 | | // 32 times in a nine-bit table. If a symbol is nine bits long, |
| | | 172 | | // it appears in the table once. |
| | | 173 | | // |
| | | 174 | | // Make sure that in the loop below, code is always |
| | | 175 | | // less than table_size. |
| | | 176 | | // |
| | | 177 | | // On last iteration we store at array index: |
| | | 178 | | // initial_start_at + (locs-1)*increment |
| | | 179 | | // = initial_start_at + locs*increment - increment |
| | | 180 | | // = initial_start_at + (1 << tableBits) - increment |
| | | 181 | | // = initial_start_at + table_size - increment |
| | | 182 | | // |
| | | 183 | | // Therefore we must ensure: |
| | | 184 | | // initial_start_at + table_size - increment < table_size |
| | | 185 | | // or: initial_start_at < increment |
| | | 186 | | // |
| | 229064 | 187 | | int increment = 1 << len; |
| | 229064 | 188 | | if (start >= increment) |
| | 0 | 189 | | { |
| | 0 | 190 | | throw new InvalidDataException(SR.InvalidHuffmanData); |
| | | 191 | | } |
| | | 192 | | |
| | | 193 | | // Note the bits in the table are reverted. |
| | 229064 | 194 | | int locs = 1 << (_tableBits - len); |
| | 4426900 | 195 | | for (int j = 0; j < locs; j++) |
| | 1984386 | 196 | | { |
| | 1984386 | 197 | | _table[start] = (short)ch; |
| | 1984386 | 198 | | start += increment; |
| | 1984386 | 199 | | } |
| | 229064 | 200 | | } |
| | | 201 | | else |
| | 85646 | 202 | | { |
| | | 203 | | // For any code which has length longer than num_elements, |
| | | 204 | | // build a binary tree. |
| | | 205 | | |
| | 85646 | 206 | | int overflowBits = len - _tableBits; // the nodes we need to respent the data. |
| | 85646 | 207 | | int codeBitMask = 1 << _tableBits; // mask to get current bit (the bits can't fit in the table) |
| | | 208 | | |
| | | 209 | | // the left, right table is used to repesent the |
| | | 210 | | // the rest bits. When we got the first part (number bits.) and look at |
| | | 211 | | // tbe table, we will need to follow the tree to find the real character. |
| | | 212 | | // This is in place to avoid bloating the table if there are |
| | | 213 | | // a few ones with long code. |
| | 85646 | 214 | | int index = start & ((1 << _tableBits) - 1); |
| | 85646 | 215 | | short[] array = _table; |
| | | 216 | | |
| | | 217 | | do |
| | 264558 | 218 | | { |
| | 264558 | 219 | | short value = array[index]; |
| | | 220 | | |
| | 264558 | 221 | | if (value == 0) |
| | 69154 | 222 | | { |
| | | 223 | | // set up next pointer if this node is not used before. |
| | 69154 | 224 | | array[index] = (short)-avail; // use next available slot. |
| | 69154 | 225 | | value = (short)-avail; |
| | 69154 | 226 | | avail++; |
| | 69154 | 227 | | } |
| | | 228 | | |
| | 264558 | 229 | | if (value > 0) |
| | 340 | 230 | | { |
| | | 231 | | // prevent an IndexOutOfRangeException from array[index] |
| | 340 | 232 | | throw new InvalidDataException(SR.InvalidHuffmanData); |
| | | 233 | | } |
| | | 234 | | |
| | 264218 | 235 | | Debug.Assert(value < 0, "CreateTable: Only negative numbers are used for tree pointers!"); |
| | | 236 | | |
| | 264218 | 237 | | if ((start & codeBitMask) == 0) |
| | 133854 | 238 | | { |
| | | 239 | | // if current bit is 0, go change the left array |
| | 133854 | 240 | | array = _left; |
| | 133854 | 241 | | } |
| | | 242 | | else |
| | 130364 | 243 | | { |
| | | 244 | | // if current bit is 1, set value in the right array |
| | 130364 | 245 | | array = _right; |
| | 130364 | 246 | | } |
| | 264218 | 247 | | index = -value; // go to next node |
| | | 248 | | |
| | 264218 | 249 | | if (index >= array.Length) |
| | 48 | 250 | | { |
| | | 251 | | // prevent an IndexOutOfRangeException from array[index] |
| | 48 | 252 | | throw new InvalidDataException(SR.InvalidHuffmanData); |
| | | 253 | | } |
| | | 254 | | |
| | 264170 | 255 | | codeBitMask <<= 1; |
| | 264170 | 256 | | overflowBits--; |
| | 528340 | 257 | | } while (overflowBits != 0); |
| | | 258 | | |
| | 85258 | 259 | | array[index] = (short)ch; |
| | 85258 | 260 | | } |
| | 314322 | 261 | | } |
| | 740276 | 262 | | } |
| | 8222 | 263 | | } |
| | | 264 | | |
| | | 265 | | // |
| | | 266 | | // This function will try to get enough bits from input and |
| | | 267 | | // try to decode the bits. |
| | | 268 | | // If there are no enought bits in the input, this function will return -1. |
| | | 269 | | // |
| | | 270 | | public int GetNextSymbol(InputBuffer input) |
| | 1178396 | 271 | | { |
| | | 272 | | // Try to load 16 bits into input buffer if possible and get the bitBuffer value. |
| | | 273 | | // If there aren't 16 bits available we will return all we have in the |
| | | 274 | | // input buffer. |
| | 1178396 | 275 | | uint bitBuffer = input.TryLoad16Bits(); |
| | 1178396 | 276 | | if (input.AvailableBits == 0) |
| | 580 | 277 | | { // running out of input. |
| | 580 | 278 | | return -1; |
| | | 279 | | } |
| | | 280 | | |
| | | 281 | | // decode an element |
| | 1177816 | 282 | | int symbol = _table[bitBuffer & _tableMask]; |
| | 1177816 | 283 | | if (symbol < 0) |
| | 10082 | 284 | | { // this will be the start of the binary tree |
| | | 285 | | // navigate the tree |
| | 10082 | 286 | | uint mask = (uint)1 << _tableBits; |
| | | 287 | | do |
| | 14816 | 288 | | { |
| | 14816 | 289 | | symbol = -symbol; |
| | 14816 | 290 | | if ((bitBuffer & mask) == 0) |
| | 9930 | 291 | | symbol = _left[symbol]; |
| | | 292 | | else |
| | 4886 | 293 | | symbol = _right[symbol]; |
| | 14816 | 294 | | mask <<= 1; |
| | 29632 | 295 | | } while (symbol < 0); |
| | 10082 | 296 | | } |
| | | 297 | | |
| | 1177816 | 298 | | int codeLength = _codeLengthArray[symbol]; |
| | | 299 | | |
| | | 300 | | // huffman code lengths must be at least 1 bit long |
| | 1177816 | 301 | | if (codeLength <= 0) |
| | 324 | 302 | | { |
| | 324 | 303 | | throw new InvalidDataException(SR.InvalidHuffmanData); |
| | | 304 | | } |
| | | 305 | | |
| | | 306 | | // |
| | | 307 | | // If this code is longer than the # bits we had in the bit buffer (i.e. |
| | | 308 | | // we read only part of the code), we can hit the entry in the table or the tree |
| | | 309 | | // for another symbol. However the length of another symbol will not match the |
| | | 310 | | // available bits count. |
| | 1177492 | 311 | | if (codeLength > input.AvailableBits) |
| | 2816 | 312 | | { |
| | | 313 | | // We already tried to load 16 bits and maximum length is 15, |
| | | 314 | | // so this means we are running out of input. |
| | 2816 | 315 | | return -1; |
| | | 316 | | } |
| | | 317 | | |
| | 1174676 | 318 | | input.SkipBits(codeLength); |
| | 1174676 | 319 | | return symbol; |
| | 1178072 | 320 | | } |
| | | 321 | | } |
| | | 322 | | } |