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 // Models the histograms of literals, commands and distance codes. 16 17 #ifndef BROTLI_ENC_HISTOGRAM_H_ 18 #define BROTLI_ENC_HISTOGRAM_H_ 19 20 #include <stdint.h> 21 #include <string.h> 22 #include <vector> 23 #include <utility> 24 #include "./command.h" 25 #include "./fast_log.h" 26 #include "./prefix.h" 27 28 namespace brotli { 29 30 class BlockSplit; 31 32 // A simple container for histograms of data in blocks. 33 template<int kDataSize> 34 struct Histogram { HistogramHistogram35 Histogram() { 36 Clear(); 37 } ClearHistogram38 void Clear() { 39 memset(data_, 0, sizeof(data_)); 40 total_count_ = 0; 41 } AddHistogram42 void Add(int val) { 43 ++data_[val]; 44 ++total_count_; 45 } RemoveHistogram46 void Remove(int val) { 47 --data_[val]; 48 --total_count_; 49 } 50 template<typename DataType> AddHistogram51 void Add(const DataType *p, size_t n) { 52 total_count_ += n; 53 n += 1; 54 while(--n) ++data_[*p++]; 55 } AddHistogramHistogram56 void AddHistogram(const Histogram& v) { 57 total_count_ += v.total_count_; 58 for (int i = 0; i < kDataSize; ++i) { 59 data_[i] += v.data_[i]; 60 } 61 } EntropyBitCostHistogram62 double EntropyBitCost() const { 63 double retval = total_count_ * FastLog2(total_count_); 64 for (int i = 0; i < kDataSize; ++i) { 65 retval -= data_[i] * FastLog2(data_[i]); 66 } 67 return retval; 68 } 69 70 int data_[kDataSize]; 71 int total_count_; 72 double bit_cost_; 73 }; 74 75 // Literal histogram. 76 typedef Histogram<256> HistogramLiteral; 77 // Prefix histograms. 78 typedef Histogram<kNumCommandPrefixes> HistogramCommand; 79 typedef Histogram<kNumDistancePrefixes> HistogramDistance; 80 typedef Histogram<kNumBlockLenPrefixes> HistogramBlockLength; 81 // Context map histogram, 256 Huffman tree indexes + 16 run length codes. 82 typedef Histogram<272> HistogramContextMap; 83 // Block type histogram, 256 block types + 2 special symbols. 84 typedef Histogram<258> HistogramBlockType; 85 86 static const int kLiteralContextBits = 6; 87 static const int kDistanceContextBits = 2; 88 89 void BuildHistograms( 90 const std::vector<Command>& cmds, 91 const BlockSplit& literal_split, 92 const BlockSplit& insert_and_copy_split, 93 const BlockSplit& dist_split, 94 const uint8_t* ringbuffer, 95 size_t pos, 96 size_t mask, 97 const std::vector<int>& context_modes, 98 std::vector<HistogramLiteral>* literal_histograms, 99 std::vector<HistogramCommand>* insert_and_copy_histograms, 100 std::vector<HistogramDistance>* copy_dist_histograms); 101 102 void BuildLiteralHistogramsForBlockType( 103 const std::vector<Command>& cmds, 104 const BlockSplit& literal_split, 105 const uint8_t* ringbuffer, 106 size_t pos, 107 size_t mask, 108 int block_type, 109 int context_mode, 110 std::vector<HistogramLiteral>* histograms); 111 112 } // namespace brotli 113 114 #endif // BROTLI_ENC_HISTOGRAM_H_ 115