1 | /* NOLINT(build/header_guard) */ |
2 | /* Copyright 2015 Google Inc. All Rights Reserved. |
3 | |
4 | Distributed under MIT license. |
5 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
6 | */ |
7 | |
8 | /* template parameters: FN */ |
9 | |
10 | #define HistogramType FN(Histogram) |
11 | |
12 | /* Greedy block splitter for one block category (literal, command or distance). |
13 | */ |
14 | typedef struct FN(BlockSplitter) { |
15 | /* Alphabet size of particular block category. */ |
16 | size_t alphabet_size_; |
17 | /* We collect at least this many symbols for each block. */ |
18 | size_t min_block_size_; |
19 | /* We merge histograms A and B if |
20 | entropy(A+B) < entropy(A) + entropy(B) + split_threshold_, |
21 | where A is the current histogram and B is the histogram of the last or the |
22 | second last block type. */ |
23 | double split_threshold_; |
24 | |
25 | size_t num_blocks_; |
26 | BlockSplit* split_; /* not owned */ |
27 | HistogramType* histograms_; /* not owned */ |
28 | size_t* histograms_size_; /* not owned */ |
29 | |
30 | /* The number of symbols that we want to collect before deciding on whether |
31 | or not to merge the block with a previous one or emit a new block. */ |
32 | size_t target_block_size_; |
33 | /* The number of symbols in the current histogram. */ |
34 | size_t block_size_; |
35 | /* Offset of the current histogram. */ |
36 | size_t curr_histogram_ix_; |
37 | /* Offset of the histograms of the previous two block types. */ |
38 | size_t last_histogram_ix_[2]; |
39 | /* Entropy of the previous two block types. */ |
40 | double last_entropy_[2]; |
41 | /* The number of times we merged the current block with the last one. */ |
42 | size_t merge_last_count_; |
43 | } FN(BlockSplitter); |
44 | |
45 | static void FN(InitBlockSplitter)( |
46 | MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size, |
47 | size_t min_block_size, double split_threshold, size_t num_symbols, |
48 | BlockSplit* split, HistogramType** histograms, size_t* histograms_size) { |
49 | size_t max_num_blocks = num_symbols / min_block_size + 1; |
50 | /* We have to allocate one more histogram than the maximum number of block |
51 | types for the current histogram when the meta-block is too big. */ |
52 | size_t max_num_types = |
53 | BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1); |
54 | self->alphabet_size_ = alphabet_size; |
55 | self->min_block_size_ = min_block_size; |
56 | self->split_threshold_ = split_threshold; |
57 | self->num_blocks_ = 0; |
58 | self->split_ = split; |
59 | self->histograms_size_ = histograms_size; |
60 | self->target_block_size_ = min_block_size; |
61 | self->block_size_ = 0; |
62 | self->curr_histogram_ix_ = 0; |
63 | self->merge_last_count_ = 0; |
64 | BROTLI_ENSURE_CAPACITY(m, uint8_t, |
65 | split->types, split->types_alloc_size, max_num_blocks); |
66 | BROTLI_ENSURE_CAPACITY(m, uint32_t, |
67 | split->lengths, split->lengths_alloc_size, max_num_blocks); |
68 | if (BROTLI_IS_OOM(m)) return; |
69 | self->split_->num_blocks = max_num_blocks; |
70 | BROTLI_DCHECK(*histograms == 0); |
71 | *histograms_size = max_num_types; |
72 | *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size); |
73 | self->histograms_ = *histograms; |
74 | if (BROTLI_IS_OOM(m)) return; |
75 | /* Clear only current histogram. */ |
76 | FN(HistogramClear)(&self->histograms_[0]); |
77 | self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0; |
78 | } |
79 | |
80 | /* Does either of three things: |
81 | (1) emits the current block with a new block type; |
82 | (2) emits the current block with the type of the second last block; |
83 | (3) merges the current block with the last block. */ |
84 | static void FN(BlockSplitterFinishBlock)( |
85 | FN(BlockSplitter)* self, BROTLI_BOOL is_final) { |
86 | BlockSplit* split = self->split_; |
87 | double* last_entropy = self->last_entropy_; |
88 | HistogramType* histograms = self->histograms_; |
89 | self->block_size_ = |
90 | BROTLI_MAX(size_t, self->block_size_, self->min_block_size_); |
91 | if (self->num_blocks_ == 0) { |
92 | /* Create first block. */ |
93 | split->lengths[0] = (uint32_t)self->block_size_; |
94 | split->types[0] = 0; |
95 | last_entropy[0] = |
96 | BitsEntropy(histograms[0].data_, self->alphabet_size_); |
97 | last_entropy[1] = last_entropy[0]; |
98 | ++self->num_blocks_; |
99 | ++split->num_types; |
100 | ++self->curr_histogram_ix_; |
101 | if (self->curr_histogram_ix_ < *self->histograms_size_) |
102 | FN(HistogramClear)(&histograms[self->curr_histogram_ix_]); |
103 | self->block_size_ = 0; |
104 | } else if (self->block_size_ > 0) { |
105 | double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_, |
106 | self->alphabet_size_); |
107 | HistogramType combined_histo[2]; |
108 | double combined_entropy[2]; |
109 | double diff[2]; |
110 | size_t j; |
111 | for (j = 0; j < 2; ++j) { |
112 | size_t last_histogram_ix = self->last_histogram_ix_[j]; |
113 | combined_histo[j] = histograms[self->curr_histogram_ix_]; |
114 | FN(HistogramAddHistogram)(&combined_histo[j], |
115 | &histograms[last_histogram_ix]); |
116 | combined_entropy[j] = BitsEntropy( |
117 | &combined_histo[j].data_[0], self->alphabet_size_); |
118 | diff[j] = combined_entropy[j] - entropy - last_entropy[j]; |
119 | } |
120 | |
121 | if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES && |
122 | diff[0] > self->split_threshold_ && |
123 | diff[1] > self->split_threshold_) { |
124 | /* Create new block. */ |
125 | split->lengths[self->num_blocks_] = (uint32_t)self->block_size_; |
126 | split->types[self->num_blocks_] = (uint8_t)split->num_types; |
127 | self->last_histogram_ix_[1] = self->last_histogram_ix_[0]; |
128 | self->last_histogram_ix_[0] = (uint8_t)split->num_types; |
129 | last_entropy[1] = last_entropy[0]; |
130 | last_entropy[0] = entropy; |
131 | ++self->num_blocks_; |
132 | ++split->num_types; |
133 | ++self->curr_histogram_ix_; |
134 | if (self->curr_histogram_ix_ < *self->histograms_size_) |
135 | FN(HistogramClear)(&histograms[self->curr_histogram_ix_]); |
136 | self->block_size_ = 0; |
137 | self->merge_last_count_ = 0; |
138 | self->target_block_size_ = self->min_block_size_; |
139 | } else if (diff[1] < diff[0] - 20.0) { |
140 | /* Combine this block with second last block. */ |
141 | split->lengths[self->num_blocks_] = (uint32_t)self->block_size_; |
142 | split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2]; |
143 | BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1); |
144 | histograms[self->last_histogram_ix_[0]] = combined_histo[1]; |
145 | last_entropy[1] = last_entropy[0]; |
146 | last_entropy[0] = combined_entropy[1]; |
147 | ++self->num_blocks_; |
148 | self->block_size_ = 0; |
149 | FN(HistogramClear)(&histograms[self->curr_histogram_ix_]); |
150 | self->merge_last_count_ = 0; |
151 | self->target_block_size_ = self->min_block_size_; |
152 | } else { |
153 | /* Combine this block with last block. */ |
154 | split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_; |
155 | histograms[self->last_histogram_ix_[0]] = combined_histo[0]; |
156 | last_entropy[0] = combined_entropy[0]; |
157 | if (split->num_types == 1) { |
158 | last_entropy[1] = last_entropy[0]; |
159 | } |
160 | self->block_size_ = 0; |
161 | FN(HistogramClear)(&histograms[self->curr_histogram_ix_]); |
162 | if (++self->merge_last_count_ > 1) { |
163 | self->target_block_size_ += self->min_block_size_; |
164 | } |
165 | } |
166 | } |
167 | if (is_final) { |
168 | *self->histograms_size_ = split->num_types; |
169 | split->num_blocks = self->num_blocks_; |
170 | } |
171 | } |
172 | |
173 | /* Adds the next symbol to the current histogram. When the current histogram |
174 | reaches the target size, decides on merging the block. */ |
175 | static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) { |
176 | FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol); |
177 | ++self->block_size_; |
178 | if (self->block_size_ == self->target_block_size_) { |
179 | FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE); |
180 | } |
181 | } |
182 | |
183 | #undef HistogramType |
184 | |