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> 17a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./huffman_encode.h" 18a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../utils/utils.h" 19a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#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 30a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Hufmann tree compression, especially its RLE-part, give smaller output. 31a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int OptimizeHuffmanForRle(int length, int* const counts) { 32a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* good_for_rle; 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) { 37a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; // 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 good_for_rle = (uint8_t*)calloc(length, 1); 47a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (good_for_rle == NULL) { 48a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 49a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 50a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 51a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Let's not spoil any of the existing good rle codes. 52a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Mark any seq of 0's that is longer as 5 as a good_for_rle. 53a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Mark any seq of non-0's that is longer as 7 as a good_for_rle. 54a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int symbol = counts[0]; 55a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int stride = 0; 56a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < length + 1; ++i) { 57a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i == length || counts[i] != symbol) { 58a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if ((symbol == 0 && stride >= 5) || 59a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (symbol != 0 && stride >= 7)) { 60a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 61a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < stride; ++k) { 62a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora good_for_rle[i - k - 1] = 1; 63a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 64a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 65a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stride = 1; 66a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i != length) { 67a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora symbol = counts[i]; 68a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 69a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 70a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++stride; 71a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 72a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 73a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 74a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 3) Let's replace those population counts that lead to more rle codes. 75a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 76a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int stride = 0; 77a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int limit = counts[0]; 78a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int sum = 0; 79a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < length + 1; ++i) { 80a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i == length || good_for_rle[i] || 81a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (i != 0 && good_for_rle[i - 1]) || 82a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora !ValuesShouldBeCollapsedToStrideAverage(counts[i], limit)) { 83a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (stride >= 4 || (stride >= 3 && sum == 0)) { 84a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 85a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // The stride must end, collapse what we have, if we have enough (4). 86a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int count = (sum + stride / 2) / stride; 87a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (count < 1) { 88a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora count = 1; 89a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 90a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (sum == 0) { 91a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Don't make an all zeros stride to be upgraded to ones. 92a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora count = 0; 93a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 94a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < stride; ++k) { 95a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // We don't want to change value at counts[i], 96a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // that is already belonging to the next stride. Thus - 1. 97a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora counts[i - k - 1] = count; 98a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 99a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 100a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stride = 0; 101a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sum = 0; 102a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i < length - 3) { 103a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // All interesting strides have a count of at least 4, 104a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // at least when non-zeros. 105a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = (counts[i] + counts[i + 1] + 106a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora counts[i + 2] + counts[i + 3] + 2) / 4; 107a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (i < length) { 108a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = counts[i]; 109a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 110a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = 0; 111a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 112a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++stride; 114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (i != length) { 115a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sum += counts[i]; 116a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (stride >= 4) { 117a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora limit = (sum + stride / 2) / stride; 118a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 119a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 121a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 122a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora free(good_for_rle); 123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 124a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 125a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 126a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroratypedef struct { 127a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int total_count_; 128a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int value_; 129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int pool_index_left_; 130a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int pool_index_right_; 131a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} HuffmanTree; 132a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 133a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// A comparer function for two Huffman trees: sorts first by 'total count' 134a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// (more comes first), and then by 'value' (more comes first). 135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int CompareHuffmanTrees(const void* ptr1, const void* ptr2) { 136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTree* const t1 = (const HuffmanTree*)ptr1; 137a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTree* const t2 = (const HuffmanTree*)ptr2; 138a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (t1->total_count_ > t2->total_count_) { 139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return -1; 140a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (t1->total_count_ < t2->total_count_) { 141a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 142a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 1431e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora assert(t1->value_ != t2->value_); 1441e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora return (t1->value_ < t2->value_) ? -1 : 1; 145a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 146a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 148a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void SetBitDepths(const HuffmanTree* const tree, 149a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTree* const pool, 150a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* const bit_depths, int level) { 151a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree->pool_index_left_ >= 0) { 152a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1); 153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1); 154a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 155a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_depths[tree->value_] = level; 156a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 159a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Create an optimal Huffman tree. 160a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 161a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// (data,length): population counts. 162a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// tree_limit: maximum bit depth (inclusive) of the codes. 163a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// bit_depths[]: how many bits are used for the symbol. 164a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 165a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Returns 0 when an error has occurred. 166a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 167a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// The catch here is that the tree cannot be arbitrarily deep 168a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 169a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// count_limit is the value that is to be faked as the minimum value 170a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// and this minimum value is raised until the tree matches the 171a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// maximum length requirement. 172a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 173a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// This algorithm is not of excellent performance for very long data blocks, 174a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// especially when population counts are longer than 2**tree_limit, but 175a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// we are not planning to use this with extremely long blocks. 176a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 177a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// See http://en.wikipedia.org/wiki/Huffman_coding 178a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int GenerateOptimalTree(const int* const histogram, int histogram_size, 179a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_depth_limit, 180a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* const bit_depths) { 181a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int count_min; 182a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTree* tree_pool; 183a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTree* tree; 184a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_size_orig = 0; 185a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 186a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 187a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < histogram_size; ++i) { 188a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (histogram[i] != 0) { 189a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tree_size_orig; 190a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 191a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 192a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1931e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (tree_size_orig == 0) { // pretty optimal already! 1941e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora return 1; 1951e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } 1961e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora 197a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 3 * tree_size is enough to cover all the nodes representing a 198a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // population and all the inserted nodes combining two existing nodes. 199a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // The tree pool needs 2 * (tree_size_orig - 1) entities, and the 200a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // tree needs exactly tree_size_orig entities. 201a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree = (HuffmanTree*)WebPSafeMalloc(3ULL * tree_size_orig, sizeof(*tree)); 202a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree == NULL) return 0; 203a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_pool = tree + tree_size_orig; 204a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 205a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // For block sizes with less than 64k symbols we never need to do a 206a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // second iteration of this loop. 207a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // If we actually start running inside this loop a lot, we would perhaps 208a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // be better off with the Katajainen algorithm. 209a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree_size_orig <= (1 << (tree_depth_limit - 1))); 210a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (count_min = 1; ; count_min *= 2) { 211a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_size = tree_size_orig; 212a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // We need to pack the Huffman tree in tree_depth_limit bits. 213a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // So, we try by faking histogram entries to be at least 'count_min'. 214a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int idx = 0; 215a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int j; 216a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (j = 0; j < histogram_size; ++j) { 217a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (histogram[j] != 0) { 218a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int count = 219a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (histogram[j] < count_min) ? count_min : histogram[j]; 220a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].total_count_ = count; 221a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].value_ = j; 222a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].pool_index_left_ = -1; 223a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[idx].pool_index_right_ = -1; 224a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++idx; 225a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 226a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 227a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 228a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Build the Huffman tree. 229a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees); 230a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 231a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree_size > 1) { // Normal case. 232a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tree_pool_size = 0; 233a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (tree_size > 1) { // Finish when we have only one root. 234a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int count; 235a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_pool[tree_pool_size++] = tree[tree_size - 1]; 236a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_pool[tree_pool_size++] = tree[tree_size - 2]; 237a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora count = tree_pool[tree_pool_size - 1].total_count_ + 2381e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora tree_pool[tree_pool_size - 2].total_count_; 239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_size -= 2; 240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 241a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Search for the insertion point. 242a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 243a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < tree_size; ++k) { 244a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree[k].total_count_ <= count) { 245a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 246a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 247a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 248a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree)); 249a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].total_count_ = count; 250a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].value_ = -1; 251a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 252a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].pool_index_left_ = tree_pool_size - 1; 253a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree[k].pool_index_right_ = tree_pool_size - 2; 254a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_size = tree_size + 1; 255a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 256a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 257a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora SetBitDepths(&tree[0], tree_pool, bit_depths, 0); 258a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (tree_size == 1) { // Trivial case: only one element. 259a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_depths[tree[0].value_] = 1; 260a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 261a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 262a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 263a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Test if this Huffman tree satisfies our 'tree_depth_limit' criteria. 264a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int max_depth = bit_depths[0]; 265a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (j = 1; j < histogram_size; ++j) { 266a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (max_depth < bit_depths[j]) { 267a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora max_depth = bit_depths[j]; 268a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 269a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 270a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (max_depth <= tree_depth_limit) { 271a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 272a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 273a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 274a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 275a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora free(tree); 276a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 277a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 278a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 279a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 280a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Coding of the Huffman tree values 281a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 282a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic HuffmanTreeToken* CodeRepeatedValues(int repetitions, 283a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens, 284a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int value, int prev_value) { 285a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(value <= MAX_ALLOWED_CODE_LENGTH); 286a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (value != prev_value) { 287a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = value; 288a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0; 289a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 290a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora --repetitions; 291a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 292a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (repetitions >= 1) { 293a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (repetitions < 3) { 294a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 295a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < repetitions; ++i) { 296a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = value; 297a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0; 298a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 299a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 300a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 301a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (repetitions < 7) { 302a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 16; 303a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = repetitions - 3; 304a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 305a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 306a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 307a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 16; 308a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 3; 309a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 310a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora repetitions -= 6; 311a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 312a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 313a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return tokens; 314a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 315a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 316a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic HuffmanTreeToken* CodeRepeatedZeros(int repetitions, 317a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens) { 318a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (repetitions >= 1) { 319a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (repetitions < 3) { 320a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 321a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < repetitions; ++i) { 322a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 0; // 0-value 323a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0; 324a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 325a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 326a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 327a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (repetitions < 11) { 328a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 17; 329a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = repetitions - 3; 330a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 331a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 332a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (repetitions < 139) { 333a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 18; 334a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = repetitions - 11; 335a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 336a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 337a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 338a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->code = 18; 339a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens->extra_bits = 0x7f; // 138 repeated 0s 340a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++tokens; 341a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora repetitions -= 138; 342a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 343a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 344a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return tokens; 345a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 346a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 347a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, 348a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens, int max_tokens) { 349a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* const starting_token = tokens; 350a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* const ending_token = tokens + max_tokens; 351a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int depth_size = tree->num_symbols; 352a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int prev_value = 8; // 8 is the initial value for rle. 353a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i = 0; 354a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tokens != NULL); 355a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (i < depth_size) { 356a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int value = tree->code_lengths[i]; 357a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k = i + 1; 358a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int runs; 359a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (k < depth_size && tree->code_lengths[k] == value) ++k; 360a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora runs = k - i; 361a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (value == 0) { 362a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens = CodeRepeatedZeros(runs, tokens); 363a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 364a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tokens = CodeRepeatedValues(runs, tokens, value, prev_value); 365a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora prev_value = value; 366a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 367a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora i += runs; 368a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tokens <= ending_token); 369a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 370a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (void)ending_token; // suppress 'unused variable' warning 371a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (int)(tokens - starting_token); 372a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 373a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 374a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 375a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 376a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Pre-reversed 4-bit values. 377a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic const uint8_t kReversedBits[16] = { 378a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 379a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf 380a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora}; 381a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 382a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic uint32_t ReverseBits(int num_bits, uint32_t bits) { 383a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t retval = 0; 384a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i = 0; 385a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (i < num_bits) { 386a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora i += 4; 387a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora retval |= kReversedBits[bits & 0xf] << (MAX_ALLOWED_CODE_LENGTH + 1 - i); 388a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bits >>= 4; 389a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 390a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora retval >>= (MAX_ALLOWED_CODE_LENGTH + 1 - num_bits); 391a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return retval; 392a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 393a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 394a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Get the actual bit values for a tree of bit depths. 395a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void ConvertBitDepthsToSymbols(HuffmanTreeCode* const tree) { 396a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // 0 bit-depth means that the symbol does not exist. 397a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 398a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int len; 399a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t next_code[MAX_ALLOWED_CODE_LENGTH + 1]; 400a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int depth_count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 401a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 402a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree != NULL); 403a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora len = tree->num_symbols; 404a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < len; ++i) { 405a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int code_length = tree->code_lengths[i]; 406a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(code_length <= MAX_ALLOWED_CODE_LENGTH); 407a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++depth_count[code_length]; 408a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 409a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora depth_count[0] = 0; // ignore unused symbol 410a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora next_code[0] = 0; 411a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 412a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t code = 0; 413a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 1; i <= MAX_ALLOWED_CODE_LENGTH; ++i) { 414a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora code = (code + depth_count[i - 1]) << 1; 415a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora next_code[i] = code; 416a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 417a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 418a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < len; ++i) { 419a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int code_length = tree->code_lengths[i]; 420a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->codes[i] = ReverseBits(code_length, next_code[code_length]++); 421a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 422a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 423a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 424a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 425a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Main entry point 426a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 427a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LCreateHuffmanTree(int* const histogram, int tree_depth_limit, 428a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const tree) { 429a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int num_symbols = tree->num_symbols; 430a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!OptimizeHuffmanForRle(num_symbols, histogram)) { 431a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 432a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 433a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!GenerateOptimalTree(histogram, num_symbols, 434a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree_depth_limit, tree->code_lengths)) { 435a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 436a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 437a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Create the actual bit codes for the bit lengths. 438a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ConvertBitDepthsToSymbols(tree); 439a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 440a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 441