Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(387)

Unified Diff: third_party/brotli/enc/entropy_encode.h

Issue 2537133002: Update brotli to v1.0.0-snapshot. (Closed)
Patch Set: Fixed typo Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « third_party/brotli/enc/encode_parallel.cc ('k') | third_party/brotli/enc/entropy_encode.c » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: third_party/brotli/enc/entropy_encode.h
diff --git a/third_party/brotli/enc/entropy_encode.h b/third_party/brotli/enc/entropy_encode.h
index 090f9546c1b6196a5ee13793600df62280746cf0..812d0094f86fbe2f033e5946a7f81a2712e1ac22 100644
--- a/third_party/brotli/enc/entropy_encode.h
+++ b/third_party/brotli/enc/entropy_encode.h
@@ -4,101 +4,119 @@
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/
-// Entropy encoding (Huffman) utilities.
+/* Entropy encoding (Huffman) utilities. */
#ifndef BROTLI_ENC_ENTROPY_ENCODE_H_
#define BROTLI_ENC_ENTROPY_ENCODE_H_
-#include <string.h>
-#include "./histogram.h"
-#include "./prefix.h"
-#include "./types.h"
+#include <brotli/types.h>
+#include "./port.h"
-namespace brotli {
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
-// A node of a Huffman tree.
-struct HuffmanTree {
- HuffmanTree() {}
- HuffmanTree(uint32_t count, int16_t left, int16_t right)
- : total_count_(count),
- index_left_(left),
- index_right_or_value_(right) {
- }
+/* A node of a Huffman tree. */
+typedef struct HuffmanTree {
uint32_t total_count_;
int16_t index_left_;
int16_t index_right_or_value_;
-};
-
-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.
-//
-// The actual Huffman tree is constructed in the tree[] array, which has to
-// be at least 2 * length + 1 long.
-//
-// See http://en.wikipedia.org/wiki/Huffman_coding
-void CreateHuffmanTree(const uint32_t *data,
- const size_t length,
- const int tree_limit,
- HuffmanTree* tree,
- 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.
-// good_for_rle is a buffer of at least length size
-void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts,
- uint8_t* good_for_rle);
-
-// 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,
- size_t* tree_size,
- uint8_t* tree,
- 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_
+} HuffmanTree;
+
+static BROTLI_INLINE void InitHuffmanTree(HuffmanTree* self, uint32_t count,
+ int16_t left, int16_t right) {
+ self->total_count_ = count;
+ self->index_left_ = left;
+ self->index_right_or_value_ = right;
+}
+
+/* Returns 1 is assignment of depths succeeded, otherwise 0. */
+BROTLI_INTERNAL BROTLI_BOOL BrotliSetDepth(
+ int p, HuffmanTree* pool, uint8_t* depth, int max_depth);
+
+/* 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.
+
+ The actual Huffman tree is constructed in the tree[] array, which has to
+ be at least 2 * length + 1 long.
+
+ See http://en.wikipedia.org/wiki/Huffman_coding */
+BROTLI_INTERNAL void BrotliCreateHuffmanTree(const uint32_t *data,
+ const size_t length,
+ const int tree_limit,
+ HuffmanTree* tree,
+ 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.
+ good_for_rle is a buffer of at least length size */
+BROTLI_INTERNAL void BrotliOptimizeHuffmanCountsForRle(
+ size_t length, uint32_t* counts, uint8_t* good_for_rle);
+
+/* Write a Huffman tree from bit depths into the bit-stream representation
+ of a Huffman tree. The generated Huffman tree is to be compressed once
+ more using a Huffman tree */
+BROTLI_INTERNAL void BrotliWriteHuffmanTree(const uint8_t* depth,
+ size_t num,
+ size_t* tree_size,
+ uint8_t* tree,
+ uint8_t* extra_bits_data);
+
+/* Get the actual bit values for a tree of bit depths. */
+BROTLI_INTERNAL void BrotliConvertBitDepthsToSymbols(const uint8_t *depth,
+ size_t len,
+ uint16_t *bits);
+
+/* Input size optimized Shell sort. */
+typedef BROTLI_BOOL (*HuffmanTreeComparator)(
+ const HuffmanTree*, const HuffmanTree*);
+static BROTLI_INLINE void SortHuffmanTreeItems(HuffmanTree* items,
+ const size_t n, HuffmanTreeComparator comparator) {
+ static const size_t gaps[] = {132, 57, 23, 10, 4, 1};
+ if (n < 13) {
+ /* Insertion sort. */
+ size_t i;
+ for (i = 1; i < n; ++i) {
+ HuffmanTree tmp = items[i];
+ size_t k = i;
+ size_t j = i - 1;
+ while (comparator(&tmp, &items[j])) {
+ items[k] = items[j];
+ k = j;
+ if (!j--) break;
+ }
+ items[k] = tmp;
+ }
+ return;
+ } else {
+ /* Shell sort. */
+ int g = n < 57 ? 2 : 0;
+ for (; g < 6; ++g) {
+ size_t gap = gaps[g];
+ size_t i;
+ for (i = gap; i < n; ++i) {
+ size_t j = i;
+ HuffmanTree tmp = items[i];
+ for (; j >= gap && comparator(&tmp, &items[j - gap]); j -= gap) {
+ items[j] = items[j - gap];
+ }
+ items[j] = tmp;
+ }
+ }
+ }
+}
+
+#if defined(__cplusplus) || defined(c_plusplus)
+} /* extern "C" */
+#endif
+
+#endif /* BROTLI_ENC_ENTROPY_ENCODE_H_ */
« no previous file with comments | « third_party/brotli/enc/encode_parallel.cc ('k') | third_party/brotli/enc/entropy_encode.c » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698