1// Copyright 2010 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Entropy encoding (Huffman) utilities.
16
17#ifndef BROTLI_ENC_ENTROPY_ENCODE_H_
18#define BROTLI_ENC_ENTROPY_ENCODE_H_
19
20#include <stdint.h>
21#include <string.h>
22#include "./histogram.h"
23#include "./prefix.h"
24
25namespace brotli {
26
27// This function will create a Huffman tree.
28//
29// The (data,length) contains the population counts.
30// The tree_limit is the maximum bit depth of the Huffman codes.
31//
32// The depth contains the tree, i.e., how many bits are used for
33// the symbol.
34//
35// See http://en.wikipedia.org/wiki/Huffman_coding
36void CreateHuffmanTree(const int *data,
37                       const int length,
38                       const int tree_limit,
39                       uint8_t *depth);
40
41// Change the population counts in a way that the consequent
42// Hufmann tree compression, especially its rle-part will be more
43// likely to compress this data more efficiently.
44//
45// length contains the size of the histogram.
46// counts contains the population counts.
47int OptimizeHuffmanCountsForRle(int length, int* counts);
48
49
50// Write a huffman tree from bit depths into the bitstream representation
51// of a Huffman tree. The generated Huffman tree is to be compressed once
52// more using a Huffman tree
53void WriteHuffmanTree(const uint8_t* depth, const int length,
54                      uint8_t* tree,
55                      uint8_t* extra_bits_data,
56                      int* huffman_tree_size);
57
58// Get the actual bit values for a tree of bit depths.
59void ConvertBitDepthsToSymbols(const uint8_t *depth, int len, uint16_t *bits);
60
61template<int kSize>
62struct EntropyCode {
63  // How many bits for symbol.
64  uint8_t depth_[kSize];
65  // Actual bits used to represent the symbol.
66  uint16_t bits_[kSize];
67  // How many non-zero depth.
68  int count_;
69  // First four symbols with non-zero depth.
70  int symbols_[4];
71};
72
73template<int kSize>
74void BuildEntropyCode(const Histogram<kSize>& histogram,
75                      const int tree_limit,
76                      const int alphabet_size,
77                      EntropyCode<kSize>* code) {
78  memset(code->depth_, 0, sizeof(code->depth_));
79  memset(code->bits_, 0, sizeof(code->bits_));
80  memset(code->symbols_, 0, sizeof(code->symbols_));
81  code->count_ = 0;
82  if (histogram.total_count_ == 0) return;
83  for (int i = 0; i < kSize; ++i) {
84    if (histogram.data_[i] > 0) {
85      if (code->count_ < 4) code->symbols_[code->count_] = i;
86      ++code->count_;
87    }
88  }
89  if (alphabet_size >= 50 && code->count_ >= 16) {
90    int counts[kSize];
91    memcpy(counts, &histogram.data_[0], sizeof(counts[0]) * kSize);
92    OptimizeHuffmanCountsForRle(alphabet_size, counts);
93    CreateHuffmanTree(counts, alphabet_size, tree_limit, &code->depth_[0]);
94  } else {
95    CreateHuffmanTree(&histogram.data_[0], alphabet_size, tree_limit,
96                      &code->depth_[0]);
97  }
98  ConvertBitDepthsToSymbols(&code->depth_[0], alphabet_size, &code->bits_[0]);
99}
100
101static const int kCodeLengthCodes = 18;
102
103// Literal entropy code.
104typedef EntropyCode<256> EntropyCodeLiteral;
105// Prefix entropy codes.
106typedef EntropyCode<kNumCommandPrefixes> EntropyCodeCommand;
107typedef EntropyCode<kNumDistancePrefixes> EntropyCodeDistance;
108typedef EntropyCode<kNumBlockLenPrefixes> EntropyCodeBlockLength;
109// Context map entropy code, 256 Huffman tree indexes + 16 run length codes.
110typedef EntropyCode<272> EntropyCodeContextMap;
111// Block type entropy code, 256 block types + 2 special symbols.
112typedef EntropyCode<258> EntropyCodeBlockType;
113
114}  // namespace brotli
115
116#endif  // BROTLI_ENC_ENTROPY_ENCODE_H_
117