1 files changed, 102 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/deps/brotli/enc/entropy_encode.h b/web/server/h2o/libh2o/deps/brotli/enc/entropy_encode.h
new file mode 100644
index 00000000..4b674a13
--- /dev/null
+++ b/web/server/h2o/libh2o/deps/brotli/enc/entropy_encode.h
@@ -0,0 +1,102 @@
+/* Copyright 2010 Google Inc. All Rights Reserved.
+
+   Distributed under MIT license.
+   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
+*/
+
+// Entropy encoding (Huffman) utilities.
+
+#ifndef BROTLI_ENC_ENTROPY_ENCODE_H_
+#define BROTLI_ENC_ENTROPY_ENCODE_H_
+
+#include <string.h>
+#include <vector>
+#include "./histogram.h"
+#include "./prefix.h"
+#include "./types.h"
+
+namespace brotli {
+
+// A node of a Huffman tree.
+struct HuffmanTree {
+  HuffmanTree(uint32_t count, int16_t left, int16_t right)
+      : total_count_(count),
+        index_left_(left),
+        index_right_or_value_(right) {
+  }
+  uint32_t total_count_;
+  int16_t index_left_;
+  int16_t index_right_or_value_;
+};
+
+// Sort the root nodes, least popular first.
+inline bool SortHuffmanTree(const HuffmanTree &v0, const HuffmanTree &v1) {
+  return v0.total_count_ < v1.total_count_;
+}
+
+void SetDepth(const HuffmanTree &p, HuffmanTree *pool,
+              uint8_t *depth, uint8_t level);
+
+// This function will create a Huffman tree.
+//
+// The (data,length) contains the population counts.
+// The tree_limit is the maximum bit depth of the Huffman codes.
+//
+// The depth contains the tree, i.e., how many bits are used for
+// the symbol.
+//
+// See http://en.wikipedia.org/wiki/Huffman_coding
+void CreateHuffmanTree(const uint32_t *data,
+                       const size_t length,
+                       const int tree_limit,
+                       uint8_t *depth);
+
+// Change the population counts in a way that the consequent
+// Huffman tree compression, especially its rle-part will be more
+// likely to compress this data more efficiently.
+//
+// length contains the size of the histogram.
+// counts contains the population counts.
+bool OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts);
+
+// Write a Huffman tree from bit depths into the bitstream representation
+// of a Huffman tree. The generated Huffman tree is to be compressed once
+// more using a Huffman tree
+void WriteHuffmanTree(const uint8_t* depth,
+                      size_t num,
+                      std::vector<uint8_t> *tree,
+                      std::vector<uint8_t> *extra_bits_data);
+
+// Get the actual bit values for a tree of bit depths.
+void ConvertBitDepthsToSymbols(const uint8_t *depth,
+                               size_t len,
+                               uint16_t *bits);
+
+template<int kSize>
+struct EntropyCode {
+  // How many bits for symbol.
+  uint8_t depth_[kSize];
+  // Actual bits used to represent the symbol.
+  uint16_t bits_[kSize];
+  // How many non-zero depth.
+  int count_;
+  // First four symbols with non-zero depth.
+  int symbols_[4];
+};
+
+static const int kCodeLengthCodes = 18;
+
+// Literal entropy code.
+typedef EntropyCode<256> EntropyCodeLiteral;
+// Prefix entropy codes.
+typedef EntropyCode<kNumCommandPrefixes> EntropyCodeCommand;
+typedef EntropyCode<kNumDistancePrefixes> EntropyCodeDistance;
+typedef EntropyCode<kNumBlockLenPrefixes> EntropyCodeBlockLength;
+// Context map entropy code, 256 Huffman tree indexes + 16 run length codes.
+typedef EntropyCode<272> EntropyCodeContextMap;
+// Block type entropy code, 256 block types + 2 special symbols.
+typedef EntropyCode<258> EntropyCodeBlockType;
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_ENTROPY_ENCODE_H_