kc3-lang/brotli/enc/bit_cost.h

• Show log

  Commit

• Hash : c6b9c7c5
  Author :
  Date : 2013-11-15T19:02:17
  

  Updates to Brotli compression format, decoder and encoder
  
  This commit contains a batch of changes that were made to the Brotli
  compression algorithm in the last three weeks. Most important changes:
  
    * Added UTF8 context model for good text compression.
    * Simplified context modeling by having only 4 context modes.
    * Per-block context mode selection.
    * Faster backward copying and bit reading functions.
    * More efficient histogram coding.
    * Streaming support for the decoder and encoder.
  

Download

• enc/bit_cost.h

• // Copyright 2013 Google Inc. All Rights Reserved.
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  // http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  //
  // Functions to estimate the bit cost of Huffman trees.
  
  #ifndef BROTLI_ENC_BIT_COST_H_
  #define BROTLI_ENC_BIT_COST_H_
  
  #include <stdint.h>
  
  #include "./entropy_encode.h"
  #include "./fast_log.h"
  
  namespace brotli {
  
  static const int kHuffmanExtraBits[kCodeLengthCodes] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7,
  };
  
  static inline int HuffmanTreeBitCost(const int* counts, const uint8_t* depth) {
    int nbits = 0;
    for (int i = 0; i < kCodeLengthCodes; ++i) {
      nbits += counts[i] * (depth[i] + kHuffmanExtraBits[i]);
    }
    return nbits;
  }
  
  static inline int HuffmanTreeBitCost(
      const Histogram<kCodeLengthCodes>& histogram,
      const EntropyCode<kCodeLengthCodes>& entropy) {
    return HuffmanTreeBitCost(&histogram.data_[0], &entropy.depth_[0]);
  }
  
  static inline int HuffmanBitCost(const uint8_t* depth, int length) {
    int max_depth = 1;
    int histogram[kCodeLengthCodes] = { 0 };
    int tail_start = 0;
    // compute histogram of compacted huffman tree
    for (int i = 0; i < length;) {
      const int value = depth[i];
      if (value > max_depth) {
        max_depth = value;
      }
      int reps = 1;
      for (int k = i + 1; k < length && depth[k] == value; ++k) {
        ++reps;
      }
      i += reps;
      if (value == 0) {
        while (reps > 10) {
          ++histogram[18];
          reps -= 138;
        }
        if (reps > 2) {
          ++histogram[17];
        } else if (reps > 0) {
          histogram[0] += reps;
        }
      } else {
        tail_start = i;
        ++histogram[value];
        --reps;
        while (reps > 2) {
          ++histogram[16];
          reps -= 6;
        }
        if (reps > 0) {
          histogram[value] += reps;
        }
      }
    }
  
    // create huffman tree of huffman tree
    uint8_t cost[kCodeLengthCodes] = { 0 };
    CreateHuffmanTree(histogram, kCodeLengthCodes, 7, cost);
    // account for rle extra bits
    cost[16] += 2;
    cost[17] += 3;
    cost[18] += 7;
  
    int tree_size = 0;
    int bits = 6 + 3 * max_depth;  // huffman tree of huffman tree cost
    for (int i = 0; i < kCodeLengthCodes; ++i) {
      bits += histogram[i] * cost[i];  // huffman tree bit cost
      tree_size += histogram[i];
    }
    // bit cost adjustment for long trailing zero sequence
    int tail_size = length - tail_start;
    int tail_bits = 0;
    while (tail_size >= 1) {
      if (tail_size < 3) {
        tail_bits += tail_size * cost[0];
        tree_size -= tail_size;
        break;
      } else if (tail_size < 11) {
        tail_bits += cost[17];
        --tree_size;
        break;
      } else {
        tail_bits += cost[18];
        tail_size -= 138;
        --tree_size;
      }
    }
    if (tail_bits > 12) {
      bits += ((Log2Ceiling(tree_size - 1) + 1) & ~1) + 3 - tail_bits;
    }
    return bits;
  }
  
  template<int kSize>
  double PopulationCost(const Histogram<kSize>& histogram) {
    if (histogram.total_count_ == 0) {
      return 11;
    }
    int count = 0;
    for (int i = 0; i < kSize && count < 5; ++i) {
      if (histogram.data_[i] > 0) {
        ++count;
      }
    }
    if (count == 1) {
      return 11;
    }
    if (count == 2) {
      return 19 + histogram.total_count_;
    }
    uint8_t depth[kSize] = { 0 };
    CreateHuffmanTree(&histogram.data_[0], kSize, 15, depth);
    int bits = 0;
    for (int i = 0; i < kSize; ++i) {
      bits += histogram.data_[i] * depth[i];
    }
    if (count == 3) {
      bits += 27;
    } else {
      bits += HuffmanBitCost(depth, kSize);
    }
    return bits;
  }
  
  }  // namespace brotli
  
  #endif  // BROTLI_ENC_BIT_COST_H_
  

Download