HuffmanTree.cs 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311
  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. // See the LICENSE file in the project root for more information.
  4. using System.Diagnostics;
  5. using System.IO;
  6. namespace SharpCompress.Compressors.Deflate64
  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. internal sealed class HuffmanTree
  23. {
  24. internal const int MAX_LITERAL_TREE_ELEMENTS = 288;
  25. internal const int MAX_DIST_TREE_ELEMENTS = 32;
  26. internal const int END_OF_BLOCK_CODE = 256;
  27. internal const int NUMBER_OF_CODE_LENGTH_TREE_ELEMENTS = 19;
  28. private readonly int _tableBits;
  29. private readonly short[] _table;
  30. private readonly short[] _left;
  31. private readonly short[] _right;
  32. private readonly byte[] _codeLengthArray;
  33. #if DEBUG
  34. private uint[] _codeArrayDebug;
  35. #endif
  36. private readonly int _tableMask;
  37. // huffman tree for static block
  38. public static HuffmanTree StaticLiteralLengthTree { get; } = new HuffmanTree(GetStaticLiteralTreeLength());
  39. public static HuffmanTree StaticDistanceTree { get; } = new HuffmanTree(GetStaticDistanceTreeLength());
  40. public HuffmanTree(byte[] codeLengths)
  41. {
  42. Debug.Assert(
  43. codeLengths.Length == MAX_LITERAL_TREE_ELEMENTS ||
  44. codeLengths.Length == MAX_DIST_TREE_ELEMENTS ||
  45. codeLengths.Length == NUMBER_OF_CODE_LENGTH_TREE_ELEMENTS,
  46. "we only expect three kinds of Length here");
  47. _codeLengthArray = codeLengths;
  48. if (_codeLengthArray.Length == MAX_LITERAL_TREE_ELEMENTS)
  49. {
  50. // bits for Literal/Length tree table
  51. _tableBits = 9;
  52. }
  53. else
  54. {
  55. // bits for distance tree table and code length tree table
  56. _tableBits = 7;
  57. }
  58. _tableMask = (1 << _tableBits) - 1;
  59. _table = new short[1 << _tableBits];
  60. // I need to find proof that left and right array will always be
  61. // enough. I think they are.
  62. _left = new short[2 * _codeLengthArray.Length];
  63. _right = new short[2 * _codeLengthArray.Length];
  64. CreateTable();
  65. }
  66. // Generate the array contains huffman codes lengths for static huffman tree.
  67. // The data is in RFC 1951.
  68. private static byte[] GetStaticLiteralTreeLength()
  69. {
  70. byte[] literalTreeLength = new byte[MAX_LITERAL_TREE_ELEMENTS];
  71. for (int i = 0; i <= 143; i++)
  72. literalTreeLength[i] = 8;
  73. for (int i = 144; i <= 255; i++)
  74. literalTreeLength[i] = 9;
  75. for (int i = 256; i <= 279; i++)
  76. literalTreeLength[i] = 7;
  77. for (int i = 280; i <= 287; i++)
  78. literalTreeLength[i] = 8;
  79. return literalTreeLength;
  80. }
  81. private static byte[] GetStaticDistanceTreeLength()
  82. {
  83. byte[] staticDistanceTreeLength = new byte[MAX_DIST_TREE_ELEMENTS];
  84. for (int i = 0; i < MAX_DIST_TREE_ELEMENTS; i++)
  85. {
  86. staticDistanceTreeLength[i] = 5;
  87. }
  88. return staticDistanceTreeLength;
  89. }
  90. // Calculate the huffman code for each character based on the code length for each character.
  91. // This algorithm is described in standard RFC 1951
  92. private uint[] CalculateHuffmanCode()
  93. {
  94. uint[] bitLengthCount = new uint[17];
  95. foreach (int codeLength in _codeLengthArray)
  96. {
  97. bitLengthCount[codeLength]++;
  98. }
  99. bitLengthCount[0] = 0; // clear count for length 0
  100. uint[] nextCode = new uint[17];
  101. uint tempCode = 0;
  102. for (int bits = 1; bits <= 16; bits++)
  103. {
  104. tempCode = (tempCode + bitLengthCount[bits - 1]) << 1;
  105. nextCode[bits] = tempCode;
  106. }
  107. uint[] code = new uint[MAX_LITERAL_TREE_ELEMENTS];
  108. for (int i = 0; i < _codeLengthArray.Length; i++)
  109. {
  110. int len = _codeLengthArray[i];
  111. if (len > 0)
  112. {
  113. code[i] = FastEncoderStatics.BitReverse(nextCode[len], len);
  114. nextCode[len]++;
  115. }
  116. }
  117. return code;
  118. }
  119. private void CreateTable()
  120. {
  121. uint[] codeArray = CalculateHuffmanCode();
  122. #if DEBUG
  123. _codeArrayDebug = codeArray;
  124. #endif
  125. short avail = (short)_codeLengthArray.Length;
  126. for (int ch = 0; ch < _codeLengthArray.Length; ch++)
  127. {
  128. // length of this code
  129. int len = _codeLengthArray[ch];
  130. if (len > 0)
  131. {
  132. // start value (bit reversed)
  133. int start = (int)codeArray[ch];
  134. if (len <= _tableBits)
  135. {
  136. // If a particular symbol is shorter than nine bits,
  137. // then that symbol's translation is duplicated
  138. // in all those entries that start with that symbol's bits.
  139. // For example, if the symbol is four bits, then it's duplicated
  140. // 32 times in a nine-bit table. If a symbol is nine bits long,
  141. // it appears in the table once.
  142. //
  143. // Make sure that in the loop below, code is always
  144. // less than table_size.
  145. //
  146. // On last iteration we store at array index:
  147. // initial_start_at + (locs-1)*increment
  148. // = initial_start_at + locs*increment - increment
  149. // = initial_start_at + (1 << tableBits) - increment
  150. // = initial_start_at + table_size - increment
  151. //
  152. // Therefore we must ensure:
  153. // initial_start_at + table_size - increment < table_size
  154. // or: initial_start_at < increment
  155. //
  156. int increment = 1 << len;
  157. if (start >= increment)
  158. {
  159. throw new InvalidDataException("Deflate64: invalid Huffman data");
  160. }
  161. // Note the bits in the table are reverted.
  162. int locs = 1 << (_tableBits - len);
  163. for (int j = 0; j < locs; j++)
  164. {
  165. _table[start] = (short)ch;
  166. start += increment;
  167. }
  168. }
  169. else
  170. {
  171. // For any code which has length longer than num_elements,
  172. // build a binary tree.
  173. int overflowBits = len - _tableBits; // the nodes we need to respent the data.
  174. int codeBitMask = 1 << _tableBits; // mask to get current bit (the bits can't fit in the table)
  175. // the left, right table is used to repesent the
  176. // the rest bits. When we got the first part (number bits.) and look at
  177. // tbe table, we will need to follow the tree to find the real character.
  178. // This is in place to avoid bloating the table if there are
  179. // a few ones with long code.
  180. int index = start & ((1 << _tableBits) - 1);
  181. short[] array = _table;
  182. do
  183. {
  184. short value = array[index];
  185. if (value == 0)
  186. {
  187. // set up next pointer if this node is not used before.
  188. array[index] = (short)-avail; // use next available slot.
  189. value = (short)-avail;
  190. avail++;
  191. }
  192. if (value > 0)
  193. {
  194. // prevent an IndexOutOfRangeException from array[index]
  195. throw new InvalidDataException("Deflate64: invalid Huffman data");
  196. }
  197. Debug.Assert(value < 0, "CreateTable: Only negative numbers are used for tree pointers!");
  198. if ((start & codeBitMask) == 0)
  199. {
  200. // if current bit is 0, go change the left array
  201. array = _left;
  202. }
  203. else
  204. {
  205. // if current bit is 1, set value in the right array
  206. array = _right;
  207. }
  208. index = -value; // go to next node
  209. codeBitMask <<= 1;
  210. overflowBits--;
  211. } while (overflowBits != 0);
  212. array[index] = (short)ch;
  213. }
  214. }
  215. }
  216. }
  217. //
  218. // This function will try to get enough bits from input and
  219. // try to decode the bits.
  220. // If there are no enought bits in the input, this function will return -1.
  221. //
  222. public int GetNextSymbol(InputBuffer input)
  223. {
  224. // Try to load 16 bits into input buffer if possible and get the bitBuffer value.
  225. // If there aren't 16 bits available we will return all we have in the
  226. // input buffer.
  227. uint bitBuffer = input.TryLoad16Bits();
  228. if (input.AvailableBits == 0)
  229. { // running out of input.
  230. return -1;
  231. }
  232. // decode an element
  233. int symbol = _table[bitBuffer & _tableMask];
  234. if (symbol < 0)
  235. { // this will be the start of the binary tree
  236. // navigate the tree
  237. uint mask = (uint)1 << _tableBits;
  238. do
  239. {
  240. symbol = -symbol;
  241. if ((bitBuffer & mask) == 0)
  242. symbol = _left[symbol];
  243. else
  244. symbol = _right[symbol];
  245. mask <<= 1;
  246. } while (symbol < 0);
  247. }
  248. int codeLength = _codeLengthArray[symbol];
  249. // huffman code lengths must be at least 1 bit long
  250. if (codeLength <= 0)
  251. {
  252. throw new InvalidDataException("Deflate64: invalid Huffman data");
  253. }
  254. //
  255. // If this code is longer than the # bits we had in the bit buffer (i.e.
  256. // we read only part of the code), we can hit the entry in the table or the tree
  257. // for another symbol. However the length of another symbol will not match the
  258. // available bits count.
  259. if (codeLength > input.AvailableBits)
  260. {
  261. // We already tried to load 16 bits and maximum length is 15,
  262. // so this means we are running out of input.
  263. return -1;
  264. }
  265. input.SkipBits(codeLength);
  266. return symbol;
  267. }
  268. }
  269. }