BaseTools: Copy Brotli algorithm 3rd party source code for tool

[mirror_edk2.git] / BaseTools / Source / C / BrotliCompress / enc / entropy_encode.h

diff --git a/BaseTools/Source/C/BrotliCompress/enc/entropy_encode.h b/BaseTools/Source/C/BrotliCompress/enc/entropy_encode.h
new file mode 100644 (file)
index 0000000..0a9c354
--- /dev/null
+++ b/BaseTools/Source/C/BrotliCompress/enc/entropy_encode.h
@@ -0,0 +1,122 @@
+/* Copyright 2010 Google Inc. All Rights Reserved.\r
+\r
+   Distributed under MIT license.\r
+   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
+*/\r
+\r
+/* Entropy encoding (Huffman) utilities. */\r
+\r
+#ifndef BROTLI_ENC_ENTROPY_ENCODE_H_\r
+#define BROTLI_ENC_ENTROPY_ENCODE_H_\r
+\r
+#include "../common/types.h"\r
+#include "./port.h"\r
+\r
+#if defined(__cplusplus) || defined(c_plusplus)\r
+extern "C" {\r
+#endif\r
+\r
+/* A node of a Huffman tree. */\r
+typedef struct HuffmanTree {\r
+  uint32_t total_count_;\r
+  int16_t index_left_;\r
+  int16_t index_right_or_value_;\r
+} HuffmanTree;\r
+\r
+static BROTLI_INLINE void InitHuffmanTree(HuffmanTree* self, uint32_t count,\r
+    int16_t left, int16_t right) {\r
+  self->total_count_ = count;\r
+  self->index_left_ = left;\r
+  self->index_right_or_value_ = right;\r
+}\r
+\r
+/* Returns 1 is assignment of depths succeded, otherwise 0. */\r
+BROTLI_INTERNAL BROTLI_BOOL BrotliSetDepth(\r
+    int p, HuffmanTree* pool, uint8_t* depth, int max_depth);\r
+\r
+/* This function will create a Huffman tree.\r
+\r
+   The (data,length) contains the population counts.\r
+   The tree_limit is the maximum bit depth of the Huffman codes.\r
+\r
+   The depth contains the tree, i.e., how many bits are used for\r
+   the symbol.\r
+\r
+   The actual Huffman tree is constructed in the tree[] array, which has to\r
+   be at least 2 * length + 1 long.\r
+\r
+   See http://en.wikipedia.org/wiki/Huffman_coding */\r
+BROTLI_INTERNAL void BrotliCreateHuffmanTree(const uint32_t *data,\r
+                                             const size_t length,\r
+                                             const int tree_limit,\r
+                                             HuffmanTree* tree,\r
+                                             uint8_t *depth);\r
+\r
+/* Change the population counts in a way that the consequent\r
+   Huffman tree compression, especially its rle-part will be more\r
+   likely to compress this data more efficiently.\r
+\r
+   length contains the size of the histogram.\r
+   counts contains the population counts.\r
+   good_for_rle is a buffer of at least length size */\r
+BROTLI_INTERNAL void BrotliOptimizeHuffmanCountsForRle(\r
+    size_t length, uint32_t* counts, uint8_t* good_for_rle);\r
+\r
+/* Write a Huffman tree from bit depths into the bitstream representation\r
+   of a Huffman tree. The generated Huffman tree is to be compressed once\r
+   more using a Huffman tree */\r
+BROTLI_INTERNAL void BrotliWriteHuffmanTree(const uint8_t* depth,\r
+                                            size_t num,\r
+                                            size_t* tree_size,\r
+                                            uint8_t* tree,\r
+                                            uint8_t* extra_bits_data);\r
+\r
+/* Get the actual bit values for a tree of bit depths. */\r
+BROTLI_INTERNAL void BrotliConvertBitDepthsToSymbols(const uint8_t *depth,\r
+                                                     size_t len,\r
+                                                     uint16_t *bits);\r
+\r
+/* Input size optimized Shell sort. */\r
+typedef BROTLI_BOOL (*HuffmanTreeComparator)(\r
+    const HuffmanTree*, const HuffmanTree*);\r
+static BROTLI_INLINE void SortHuffmanTreeItems(HuffmanTree* items,\r
+    const size_t n, HuffmanTreeComparator comparator) {\r
+  static const size_t gaps[] = {132, 57, 23, 10, 4, 1};\r
+  if (n < 13) {\r
+    /* Insertion sort. */\r
+    size_t i;\r
+    for (i = 1; i < n; ++i) {\r
+      HuffmanTree tmp = items[i];\r
+      size_t k = i;\r
+      size_t j = i - 1;\r
+      while (comparator(&tmp, &items[j])) {\r
+        items[k] = items[j];\r
+        k = j;\r
+        if (!j--) break;\r
+      }\r
+      items[k] = tmp;\r
+    }\r
+    return;\r
+  } else {\r
+    /* Shell sort. */\r
+    int g = n < 57 ? 2 : 0;\r
+    for (; g < 6; ++g) {\r
+      size_t gap = gaps[g];\r
+      size_t i;\r
+      for (i = gap; i < n; ++i) {\r
+        size_t j = i;\r
+        HuffmanTree tmp = items[i];\r
+        for (; j >= gap && comparator(&tmp, &items[j - gap]); j -= gap) {\r
+          items[j] = items[j - gap];\r
+        }\r
+        items[j] = tmp;\r
+      }\r
+    }\r
+  }\r
+}\r
+\r
+#if defined(__cplusplus) || defined(c_plusplus)\r
+}  /* extern "C" */\r
+#endif\r
+\r
+#endif  /* BROTLI_ENC_ENTROPY_ENCODE_H_ */\r