1a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Copyright 2011 Google Inc. All Rights Reserved. 2a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 30406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Use of this source code is governed by a BSD-style license 40406ce1417f76f2034833414dcecc9f56253640cVikas Arora// that can be found in the COPYING file in the root of the source 50406ce1417f76f2034833414dcecc9f56253640cVikas Arora// tree. An additional intellectual property rights grant can be found 60406ce1417f76f2034833414dcecc9f56253640cVikas Arora// in the file PATENTS. All contributing project authors may 70406ce1417f76f2034833414dcecc9f56253640cVikas Arora// be found in the AUTHORS file in the root of the source tree. 8a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 9a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 10a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Author: Jyrki Alakuijala (jyrki@google.com) 11a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 12a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Entropy encoding (Huffman) for webp lossless. 13a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 14a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <assert.h> 15a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <stdlib.h> 16a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <string.h> 17fa39824bb690c5806358871f46940d0450973d8aJames Zern#include "./huffman_encode_utils.h" 180912efc2528d03c59d45dd9bdc9ff9ec800a3fc1James Zern#include "./utils.h" 199e80ee991168a0a6c2a906dd2c17c5e17df4566eJames Zern#include "../webp/format_constants.h" 20a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 21a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 22a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Util function to optimize the symbol map for RLE coding 23a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 24a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Heuristics for selecting the stride ranges to collapse. 25a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int ValuesShouldBeCollapsedToStrideAverage(int a, int b) { 26a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return abs(a - b) < 4; 27a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 28a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 29a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Change the population counts in a way that the consequent 308b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Huffman tree compression, especially its RLE-part, give smaller output. 3133f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void OptimizeHuffmanForRle(int length, uint8_t* const good_for_rle, 3233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t* const counts) { 33a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 1) Let's make the Huffman code more compatible with rle encoding. 34a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 35a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (; length >= 0; --length) { 36a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (length == 0) { 3733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return; // All zeros. 38a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 39a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (counts[length - 1] != 0) { 40a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Now counts[0..length - 1] does not have trailing zeros. 41a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 42a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 43a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 44a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 2) Let's mark all population counts that already can be encoded 45a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // with an rle code. 46a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 47a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Let's not spoil any of the existing good rle codes. 48a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Mark any seq of 0's that is longer as 5 as a good_for_rle. 49a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Mark any seq of non-0's that is longer as 7 as a good_for_rle. 5033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t symbol = counts[0]; 51a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int stride = 0; 52a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < length + 1; ++i) { 53a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i == length || counts[i] != symbol) { 54a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if ((symbol == 0 && stride >= 5) || 55a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (symbol != 0 && stride >= 7)) { 56a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 57a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < stride; ++k) { 58a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora good_for_rle[i - k - 1] = 1; 59a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 60a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 61a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stride = 1; 62a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i != length) { 63a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora symbol = counts[i]; 64a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 65a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 66a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++stride; 67a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 68a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 69a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 70a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 3) Let's replace those population counts that lead to more rle codes. 71a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 7233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t stride = 0; 7333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t limit = counts[0]; 7433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t sum = 0; 75a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < length + 1; ++i) { 76a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i == length || good_for_rle[i] || 77a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (i != 0 && good_for_rle[i - 1]) || 78a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora !ValuesShouldBeCollapsedToStrideAverage(counts[i], limit)) { 79a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (stride >= 4 || (stride >= 3 && sum == 0)) { 8033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t k; 81a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // The stride must end, collapse what we have, if we have enough (4). 8233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t count = (sum + stride / 2) / stride; 83a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (count < 1) { 84a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora count = 1; 85a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 86a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (sum == 0) { 87a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Don't make an all zeros stride to be upgraded to ones. 88a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora count = 0; 89a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 90a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < stride; ++k) { 91a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // We don't want to change value at counts[i], 92a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // that is already belonging to the next stride. Thus - 1. 93a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora counts[i - k - 1] = count; 94a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 95a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 96a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stride = 0; 97a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sum = 0; 98a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i < length - 3) { 99a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // All interesting strides have a count of at least 4, 100a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // at least when non-zeros. 101a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = (counts[i] + counts[i + 1] + 102a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora counts[i + 2] + counts[i + 3] + 2) / 4; 103a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (i < length) { 104a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = counts[i]; 105a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 106a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = 0; 107a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 108a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 109a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++stride; 110a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i != length) { 111a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sum += counts[i]; 112a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (stride >= 4) { 113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = (sum + stride / 2) / stride; 114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 115a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 116a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 117a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 118a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 119a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// A comparer function for two Huffman trees: sorts first by 'total count' 121a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// (more comes first), and then by 'value' (more comes first). 122a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int CompareHuffmanTrees(const void* ptr1, const void* ptr2) { 123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTree* const t1 = (const HuffmanTree*)ptr1; 124a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTree* const t2 = (const HuffmanTree*)ptr2; 125a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (t1->total_count_ > t2->total_count_) { 126a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return -1; 127a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (t1->total_count_ < t2->total_count_) { 128a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 1301e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora assert(t1->value_ != t2->value_); 1311e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora return (t1->value_ < t2->value_) ? -1 : 1; 132a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 133a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 134a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void SetBitDepths(const HuffmanTree* const tree, 136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTree* const pool, 137a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* const bit_depths, int level) { 138a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree->pool_index_left_ >= 0) { 139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1); 140a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1); 141a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 142a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_depths[tree->value_] = level; 143a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 144a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 145a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 146a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Create an optimal Huffman tree. 147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 148a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// (data,length): population counts. 149a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// tree_limit: maximum bit depth (inclusive) of the codes. 150a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// bit_depths[]: how many bits are used for the symbol. 151a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 152a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Returns 0 when an error has occurred. 153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 154a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// The catch here is that the tree cannot be arbitrarily deep 155a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 156a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// count_limit is the value that is to be faked as the minimum value 157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// and this minimum value is raised until the tree matches the 158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// maximum length requirement. 159a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 160a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// This algorithm is not of excellent performance for very long data blocks, 161a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// especially when population counts are longer than 2**tree_limit, but 162a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// we are not planning to use this with extremely long blocks. 163a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 164a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// See http://en.wikipedia.org/wiki/Huffman_coding 16533f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void GenerateOptimalTree(const uint32_t* const histogram, 16633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int histogram_size, 16733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HuffmanTree* tree, int tree_depth_limit, 16833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint8_t* const bit_depths) { 16933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t count_min; 170a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTree* tree_pool; 171a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_size_orig = 0; 172a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 173a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 174a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < histogram_size; ++i) { 175a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (histogram[i] != 0) { 176a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tree_size_orig; 177a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 178a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 179a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1801e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (tree_size_orig == 0) { // pretty optimal already! 18133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return; 1821e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } 1831e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora 184a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_pool = tree + tree_size_orig; 185a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 186a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // For block sizes with less than 64k symbols we never need to do a 187a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // second iteration of this loop. 188a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // If we actually start running inside this loop a lot, we would perhaps 189a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // be better off with the Katajainen algorithm. 190a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree_size_orig <= (1 << (tree_depth_limit - 1))); 191a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (count_min = 1; ; count_min *= 2) { 192a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_size = tree_size_orig; 193a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // We need to pack the Huffman tree in tree_depth_limit bits. 194a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // So, we try by faking histogram entries to be at least 'count_min'. 195a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int idx = 0; 196a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int j; 197a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (j = 0; j < histogram_size; ++j) { 198a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (histogram[j] != 0) { 19933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t count = 200a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (histogram[j] < count_min) ? count_min : histogram[j]; 201a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].total_count_ = count; 202a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].value_ = j; 203a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].pool_index_left_ = -1; 204a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].pool_index_right_ = -1; 205a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++idx; 206a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 207a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 208a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 209a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Build the Huffman tree. 210a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees); 211a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 212a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree_size > 1) { // Normal case. 213a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_pool_size = 0; 214a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (tree_size > 1) { // Finish when we have only one root. 21533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t count; 216a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_pool[tree_pool_size++] = tree[tree_size - 1]; 217a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_pool[tree_pool_size++] = tree[tree_size - 2]; 218a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora count = tree_pool[tree_pool_size - 1].total_count_ + 2191e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora tree_pool[tree_pool_size - 2].total_count_; 220a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_size -= 2; 221a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 222a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Search for the insertion point. 223a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 224a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < tree_size; ++k) { 225a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree[k].total_count_ <= count) { 226a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 227a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 228a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 229a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree)); 230a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].total_count_ = count; 231a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].value_ = -1; 232a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 233a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].pool_index_left_ = tree_pool_size - 1; 234a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].pool_index_right_ = tree_pool_size - 2; 235a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_size = tree_size + 1; 236a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 237a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 238a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora SetBitDepths(&tree[0], tree_pool, bit_depths, 0); 239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (tree_size == 1) { // Trivial case: only one element. 240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_depths[tree[0].value_] = 1; 241a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 242a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 243a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 244a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Test if this Huffman tree satisfies our 'tree_depth_limit' criteria. 245a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int max_depth = bit_depths[0]; 246a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (j = 1; j < histogram_size; ++j) { 247a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (max_depth < bit_depths[j]) { 248a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora max_depth = bit_depths[j]; 249a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 250a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 251a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (max_depth <= tree_depth_limit) { 252a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 253a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 254a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 255a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 256a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 257a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 258a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 259a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Coding of the Huffman tree values 260a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 261a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic HuffmanTreeToken* CodeRepeatedValues(int repetitions, 262a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens, 263a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int value, int prev_value) { 264a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(value <= MAX_ALLOWED_CODE_LENGTH); 265a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (value != prev_value) { 266a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = value; 267a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0; 268a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 269a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora --repetitions; 270a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 271a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (repetitions >= 1) { 272a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (repetitions < 3) { 273a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 274a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < repetitions; ++i) { 275a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = value; 276a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0; 277a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 278a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 279a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 280a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (repetitions < 7) { 281a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 16; 282a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = repetitions - 3; 283a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 284a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 285a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 286a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 16; 287a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 3; 288a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 289a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora repetitions -= 6; 290a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 291a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 292a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return tokens; 293a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 294a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 295a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic HuffmanTreeToken* CodeRepeatedZeros(int repetitions, 296a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens) { 297a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (repetitions >= 1) { 298a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (repetitions < 3) { 299a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 300a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < repetitions; ++i) { 301a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 0; // 0-value 302a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0; 303a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 304a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 305a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 306a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (repetitions < 11) { 307a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 17; 308a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = repetitions - 3; 309a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 310a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 311a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (repetitions < 139) { 312a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 18; 313a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = repetitions - 11; 314a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 315a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 316a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 317a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 18; 318a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0x7f; // 138 repeated 0s 319a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 320a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora repetitions -= 138; 321a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 322a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 323a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return tokens; 324a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 325a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 326a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, 327a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens, int max_tokens) { 328a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* const starting_token = tokens; 329a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* const ending_token = tokens + max_tokens; 330a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int depth_size = tree->num_symbols; 331a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int prev_value = 8; // 8 is the initial value for rle. 332a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i = 0; 333a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tokens != NULL); 334a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (i < depth_size) { 335a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int value = tree->code_lengths[i]; 336a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k = i + 1; 337a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int runs; 338a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (k < depth_size && tree->code_lengths[k] == value) ++k; 339a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora runs = k - i; 340a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (value == 0) { 341a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens = CodeRepeatedZeros(runs, tokens); 342a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 343a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens = CodeRepeatedValues(runs, tokens, value, prev_value); 344a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora prev_value = value; 345a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 346a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora i += runs; 347a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tokens <= ending_token); 348a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 349a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (void)ending_token; // suppress 'unused variable' warning 350a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (int)(tokens - starting_token); 351a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 352a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 353a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 354a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 355a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Pre-reversed 4-bit values. 356a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic const uint8_t kReversedBits[16] = { 357a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 358a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf 359a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora}; 360a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 361a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic uint32_t ReverseBits(int num_bits, uint32_t bits) { 362a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t retval = 0; 363a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i = 0; 364a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (i < num_bits) { 365a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora i += 4; 366a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora retval |= kReversedBits[bits & 0xf] << (MAX_ALLOWED_CODE_LENGTH + 1 - i); 367a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bits >>= 4; 368a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 369a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora retval >>= (MAX_ALLOWED_CODE_LENGTH + 1 - num_bits); 370a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return retval; 371a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 372a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 373a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Get the actual bit values for a tree of bit depths. 374a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void ConvertBitDepthsToSymbols(HuffmanTreeCode* const tree) { 375a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 0 bit-depth means that the symbol does not exist. 376a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 377a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int len; 378a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t next_code[MAX_ALLOWED_CODE_LENGTH + 1]; 379a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int depth_count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 380a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 381a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree != NULL); 382a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora len = tree->num_symbols; 383a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < len; ++i) { 384a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int code_length = tree->code_lengths[i]; 385a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(code_length <= MAX_ALLOWED_CODE_LENGTH); 386a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++depth_count[code_length]; 387a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 388a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora depth_count[0] = 0; // ignore unused symbol 389a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora next_code[0] = 0; 390a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 391a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t code = 0; 392a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 1; i <= MAX_ALLOWED_CODE_LENGTH; ++i) { 393a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora code = (code + depth_count[i - 1]) << 1; 394a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora next_code[i] = code; 395a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 396a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 397a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < len; ++i) { 398a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int code_length = tree->code_lengths[i]; 399a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->codes[i] = ReverseBits(code_length, next_code[code_length]++); 400a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 401a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 402a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 403a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 404a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Main entry point 405a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 40633f74dabbc7920a65ed435d7417987589febdc16Vikas Aroravoid VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit, 40733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint8_t* const buf_rle, 40833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HuffmanTree* const huff_tree, 40933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HuffmanTreeCode* const huff_code) { 41033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int num_symbols = huff_code->num_symbols; 41133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora memset(buf_rle, 0, num_symbols * sizeof(*buf_rle)); 41233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora OptimizeHuffmanForRle(num_symbols, buf_rle, histogram); 41333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora GenerateOptimalTree(histogram, num_symbols, huff_tree, tree_depth_limit, 41433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora huff_code->code_lengths); 415a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Create the actual bit codes for the bit lengths. 41633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora ConvertBitDepthsToSymbols(huff_code); 417a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 418