Home | History | Annotate | Download | only in enc 
      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] = {
     28   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3,
     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   int prev_value = 8;
     50   // compute histogram of compacted huffman tree
     51   for (int i = 0; i < length;) {
     52     const int value = depth[i];
     53     if (value > max_depth) {
     54       max_depth = value;
     55     }
     56     int reps = 1;
     57     for (int k = i + 1; k < length && depth[k] == value; ++k) {
     58       ++reps;
     59     }
     60     i += reps;
     61     if (i == length && value == 0)
     62       break;
     63     if (value == 0) {
     64       if (reps < 3) {
     65         histogram[0] += reps;
     66       } else {
     67         reps -= 2;
     68         while (reps > 0) {
     69           ++histogram[17];
     70           reps >>= 3;
     71         }
     72       }
     73     } else {
     74       tail_start = i;
     75       if (value != prev_value) {
     76         ++histogram[value];
     77         --reps;
     78       }
     79       prev_value = value;
     80       if (reps < 3) {
     81         histogram[value] += reps;
     82       } else {
     83         reps -= 2;
     84         while (reps > 0) {
     85           ++histogram[16];
     86           reps >>= 2;
     87         }
     88       }
     89     }
     90   }
     91 
     92   // create huffman tree of huffman tree
     93   uint8_t cost[kCodeLengthCodes] = { 0 };
     94   CreateHuffmanTree(histogram, kCodeLengthCodes, 7, cost);
     95   // account for rle extra bits
     96   cost[16] += 2;
     97   cost[17] += 3;
     98 
     99   int tree_size = 0;
    100   int bits = 18 + 2 * max_depth;  // huffman tree of huffman tree cost
    101   for (int i = 0; i < kCodeLengthCodes; ++i) {
    102     bits += histogram[i] * cost[i];  // huffman tree bit cost
    103     tree_size += histogram[i];
    104   }
    105   return bits;
    106 }
    107 
    108 template<int kSize>
    109 double PopulationCost(const Histogram<kSize>& histogram) {
    110   if (histogram.total_count_ == 0) {
    111     return 12;
    112   }
    113   int count = 0;
    114   for (int i = 0; i < kSize && count < 5; ++i) {
    115     if (histogram.data_[i] > 0) {
    116       ++count;
    117     }
    118   }
    119   if (count == 1) {
    120     return 12;
    121   }
    122   if (count == 2) {
    123     return 20 + histogram.total_count_;
    124   }
    125   uint8_t depth[kSize] = { 0 };
    126   CreateHuffmanTree(&histogram.data_[0], kSize, 15, depth);
    127   int bits = 0;
    128   for (int i = 0; i < kSize; ++i) {
    129     bits += histogram.data_[i] * depth[i];
    130   }
    131   if (count == 3) {
    132     bits += 28;
    133   } else if (count == 4) {
    134     bits += 37;
    135   } else {
    136     bits += HuffmanBitCost(depth, kSize);
    137   }
    138   return bits;
    139 }
    140 
    141 }  // namespace brotli
    142 
    143 #endif  // BROTLI_ENC_BIT_COST_H_
    144