Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 1 | // Copyright 2013 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 | // Functions to estimate the bit cost of Huffman trees. |
| 16 | |
| 17 | #ifndef BROTLI_ENC_BIT_COST_H_ |
| 18 | #define BROTLI_ENC_BIT_COST_H_ |
| 19 | |
| 20 | #include <stdint.h> |
| 21 | |
| 22 | #include "./entropy_encode.h" |
| 23 | #include "./fast_log.h" |
| 24 | |
| 25 | namespace brotli { |
| 26 | |
| 27 | static const int kHuffmanExtraBits[kCodeLengthCodes] = { |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 28 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 29 | }; |
| 30 | |
| 31 | static inline int HuffmanTreeBitCost(const int* counts, const uint8_t* depth) { |
| 32 | int nbits = 0; |
| 33 | for (int i = 0; i < kCodeLengthCodes; ++i) { |
| 34 | nbits += counts[i] * (depth[i] + kHuffmanExtraBits[i]); |
| 35 | } |
| 36 | return nbits; |
| 37 | } |
| 38 | |
| 39 | static inline int HuffmanTreeBitCost( |
| 40 | const Histogram<kCodeLengthCodes>& histogram, |
| 41 | const EntropyCode<kCodeLengthCodes>& entropy) { |
| 42 | return HuffmanTreeBitCost(&histogram.data_[0], &entropy.depth_[0]); |
| 43 | } |
| 44 | |
| 45 | static inline int HuffmanBitCost(const uint8_t* depth, int length) { |
| 46 | int max_depth = 1; |
| 47 | int histogram[kCodeLengthCodes] = { 0 }; |
| 48 | int tail_start = 0; |
| 49 | // compute histogram of compacted huffman tree |
| 50 | for (int i = 0; i < length;) { |
| 51 | const int value = depth[i]; |
| 52 | if (value > max_depth) { |
| 53 | max_depth = value; |
| 54 | } |
| 55 | int reps = 1; |
| 56 | for (int k = i + 1; k < length && depth[k] == value; ++k) { |
| 57 | ++reps; |
| 58 | } |
| 59 | i += reps; |
| 60 | if (value == 0) { |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 61 | if (reps < 3) { |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 62 | histogram[0] += reps; |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 63 | } else { |
| 64 | reps -= 3; |
| 65 | while (reps >= 0) { |
| 66 | ++histogram[17]; |
| 67 | reps >>= 3; |
| 68 | --reps; |
| 69 | } |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 70 | } |
| 71 | } else { |
| 72 | tail_start = i; |
| 73 | ++histogram[value]; |
| 74 | --reps; |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 75 | if (reps < 3) { |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 76 | histogram[value] += reps; |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 77 | } else { |
| 78 | reps -= 3; |
| 79 | while (reps >= 0) { |
| 80 | ++histogram[16]; |
| 81 | reps >>= 2; |
| 82 | --reps; |
| 83 | } |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 84 | } |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | // create huffman tree of huffman tree |
| 89 | uint8_t cost[kCodeLengthCodes] = { 0 }; |
| 90 | CreateHuffmanTree(histogram, kCodeLengthCodes, 7, cost); |
| 91 | // account for rle extra bits |
| 92 | cost[16] += 2; |
| 93 | cost[17] += 3; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 94 | |
| 95 | int tree_size = 0; |
Zoltan Szabadka | cbd5cb5 | 2014-02-14 15:04:23 +0100 | [diff] [blame] | 96 | int bits = 6 + 2 * max_depth; // huffman tree of huffman tree cost |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 97 | for (int i = 0; i < kCodeLengthCodes; ++i) { |
| 98 | bits += histogram[i] * cost[i]; // huffman tree bit cost |
| 99 | tree_size += histogram[i]; |
| 100 | } |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 101 | return bits; |
| 102 | } |
| 103 | |
| 104 | template<int kSize> |
| 105 | double PopulationCost(const Histogram<kSize>& histogram) { |
| 106 | if (histogram.total_count_ == 0) { |
Zoltan Szabadka | b89f3be | 2013-12-17 17:17:57 +0100 | [diff] [blame] | 107 | return 12; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 108 | } |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 109 | int count = 0; |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 110 | for (int i = 0; i < kSize && count < 5; ++i) { |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 111 | if (histogram.data_[i] > 0) { |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 112 | ++count; |
| 113 | } |
| 114 | } |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 115 | if (count == 1) { |
Zoltan Szabadka | b89f3be | 2013-12-17 17:17:57 +0100 | [diff] [blame] | 116 | return 12; |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 117 | } |
| 118 | if (count == 2) { |
Zoltan Szabadka | b89f3be | 2013-12-17 17:17:57 +0100 | [diff] [blame] | 119 | return 20 + histogram.total_count_; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 120 | } |
| 121 | uint8_t depth[kSize] = { 0 }; |
| 122 | CreateHuffmanTree(&histogram.data_[0], kSize, 15, depth); |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 123 | int bits = 0; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 124 | for (int i = 0; i < kSize; ++i) { |
| 125 | bits += histogram.data_[i] * depth[i]; |
| 126 | } |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 127 | if (count == 3) { |
Zoltan Szabadka | b89f3be | 2013-12-17 17:17:57 +0100 | [diff] [blame] | 128 | bits += 28; |
| 129 | } else if (count == 4) { |
| 130 | bits += 37; |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 131 | } else { |
| 132 | bits += HuffmanBitCost(depth, kSize); |
| 133 | } |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 134 | return bits; |
| 135 | } |
| 136 | |
| 137 | } // namespace brotli |
| 138 | |
| 139 | #endif // BROTLI_ENC_BIT_COST_H_ |