1a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Copyright 2012 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#ifdef HAVE_CONFIG_H 13a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "config.h" 14a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#endif 15a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 16a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <math.h> 17a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 18a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./backward_references.h" 19a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./histogram.h" 20a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../dsp/lossless.h" 21a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../utils/utils.h" 22a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 2333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora#define MAX_COST 1.e38 2433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 2533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Number of partitions for the three dominant (literal, red and blue) symbol 2633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// costs. 2733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora#define NUM_PARTITIONS 4 2833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// The size of the bin-hash corresponding to the three dominant costs. 2933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora#define BIN_SIZE (NUM_PARTITIONS * NUM_PARTITIONS * NUM_PARTITIONS) 3033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 31a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void HistogramClear(VP8LHistogram* const p) { 3233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t* const literal = p->literal_; 3333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int cache_bits = p->palette_code_bits_; 3433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int histo_size = VP8LGetHistogramSize(cache_bits); 3533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora memset(p, 0, histo_size); 3633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora p->palette_code_bits_ = cache_bits; 3733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora p->literal_ = literal; 3833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 3933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 4033f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramCopy(const VP8LHistogram* const src, 4133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* const dst) { 4233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t* const dst_literal = dst->literal_; 4333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int dst_cache_bits = dst->palette_code_bits_; 4433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int histo_size = VP8LGetHistogramSize(dst_cache_bits); 4533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(src->palette_code_bits_ == dst_cache_bits); 4633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora memcpy(dst, src, histo_size); 4733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora dst->literal_ = dst_literal; 4833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 4933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 5033f74dabbc7920a65ed435d7417987589febdc16Vikas Aroraint VP8LGetHistogramSize(int cache_bits) { 5133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int literal_size = VP8LHistogramNumCodes(cache_bits); 5233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const size_t total_size = sizeof(VP8LHistogram) + sizeof(int) * literal_size; 5333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(total_size <= (size_t)0x7fffffff); 5433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return (int)total_size; 5533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 5633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 5733f74dabbc7920a65ed435d7417987589febdc16Vikas Aroravoid VP8LFreeHistogram(VP8LHistogram* const histo) { 5833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(histo); 5933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 6033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 6133f74dabbc7920a65ed435d7417987589febdc16Vikas Aroravoid VP8LFreeHistogramSet(VP8LHistogramSet* const histo) { 6233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(histo); 63a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 64a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 65a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroravoid VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 66a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogram* const histo) { 6733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LRefsCursor c = VP8LRefsCursorInit(refs); 6833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (VP8LRefsCursorOk(&c)) { 6933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos); 7033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LRefsCursorNext(&c); 71a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 72a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 73a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 74a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroravoid VP8LHistogramCreate(VP8LHistogram* const p, 75a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const VP8LBackwardRefs* const refs, 76a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int palette_code_bits) { 77a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (palette_code_bits >= 0) { 78a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora p->palette_code_bits_ = palette_code_bits; 79a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 80a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HistogramClear(p); 81a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramStoreRefs(refs, p); 82a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 83a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 84a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroravoid VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits) { 85a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora p->palette_code_bits_ = palette_code_bits; 86a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HistogramClear(p); 87a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 88a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 8933f74dabbc7920a65ed435d7417987589febdc16Vikas AroraVP8LHistogram* VP8LAllocateHistogram(int cache_bits) { 9033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* histo = NULL; 9133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int total_size = VP8LGetHistogramSize(cache_bits); 9233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint8_t* const memory = (uint8_t*)WebPSafeMalloc(total_size, sizeof(*memory)); 9333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (memory == NULL) return NULL; 9433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histo = (VP8LHistogram*)memory; 9533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // literal_ won't necessary be aligned. 9633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histo->literal_ = (uint32_t*)(memory + sizeof(VP8LHistogram)); 9733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramInit(histo, cache_bits); 9833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return histo; 9933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 10033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 101a2415724fb3466168b2af5b08bd94ba732c0e753Vikas AroraVP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits) { 102a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 103a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramSet* set; 10433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const size_t total_size = sizeof(*set) 10533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + sizeof(*set->histograms) * size 10633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + (size_t)VP8LGetHistogramSize(cache_bits) * size; 107a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* memory = (uint8_t*)WebPSafeMalloc(total_size, sizeof(*memory)); 108a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (memory == NULL) return NULL; 109a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 110a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora set = (VP8LHistogramSet*)memory; 111a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memory += sizeof(*set); 112a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora set->histograms = (VP8LHistogram**)memory; 113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memory += size * sizeof(*set->histograms); 114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora set->max_size = size; 115a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora set->size = size; 116a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < size; ++i) { 11733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora set->histograms[i] = (VP8LHistogram*)memory; 11833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // literal_ won't necessary be aligned. 11933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora set->histograms[i]->literal_ = (uint32_t*)(memory + sizeof(VP8LHistogram)); 120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramInit(set->histograms[i], cache_bits); 12133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // There's no padding/alignment between successive histograms. 12233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora memory += VP8LGetHistogramSize(cache_bits); 123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 124a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return set; 125a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 126a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 127a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 128a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroravoid VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, 130a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const PixOrCopy* const v) { 131a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (PixOrCopyIsLiteral(v)) { 132a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->alpha_[PixOrCopyLiteral(v, 3)]; 133a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->red_[PixOrCopyLiteral(v, 2)]; 134a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->literal_[PixOrCopyLiteral(v, 1)]; 135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->blue_[PixOrCopyLiteral(v, 0)]; 136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (PixOrCopyIsCacheIdx(v)) { 13733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int literal_ix = 13833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora NUM_LITERAL_CODES + NUM_LENGTH_CODES + PixOrCopyCacheIdx(v); 139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->literal_[literal_ix]; 140a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 1418b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int code, extra_bits; 1428b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora VP8LPrefixEncodeBits(PixOrCopyLength(v), &code, &extra_bits); 14333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora ++histo->literal_[NUM_LITERAL_CODES + code]; 1448b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora VP8LPrefixEncodeBits(PixOrCopyDistance(v), &code, &extra_bits); 145a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->distance_[code]; 146a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 148a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 14933f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic WEBP_INLINE double BitsEntropyRefine(int nonzeros, int sum, int max_val, 15033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double retval) { 151a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double mix; 152a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (nonzeros < 5) { 153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (nonzeros <= 1) { 154a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 155a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 156a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Two symbols, they will be 0 and 1 in a Huffman code. 157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Let's mix in a bit of entropy to favor good clustering when 158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // distributions of these are combined. 159a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (nonzeros == 2) { 160a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0.99 * sum + 0.01 * retval; 161a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 162a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // No matter what the entropy says, we cannot be better than min_limit 163a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // with Huffman coding. I am mixing a bit of entropy into the 164a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // min_limit since it produces much better (~0.5 %) compression results 165a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // perhaps because of better entropy clustering. 166a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (nonzeros == 3) { 167a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora mix = 0.95; 168a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 169a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora mix = 0.7; // nonzeros == 4. 170a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 171a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 172a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora mix = 0.627; 173a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 174a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 175a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 176a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double min_limit = 2 * sum - max_val; 177a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora min_limit = mix * min_limit + (1.0 - mix) * retval; 178a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (retval < min_limit) ? min_limit : retval; 179a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 180a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 181a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 18233f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double BitsEntropy(const uint32_t* const array, int n) { 18333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double retval = 0.; 18433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t sum = 0; 18533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int nonzeros = 0; 18633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t max_val = 0; 18733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int i; 18833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < n; ++i) { 18933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (array[i] != 0) { 19033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora sum += array[i]; 19133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora ++nonzeros; 19233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval -= VP8LFastSLog2(array[i]); 19333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (max_val < array[i]) { 19433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora max_val = array[i]; 195a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 196a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 197a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 19833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval += VP8LFastSLog2(sum); 19933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return BitsEntropyRefine(nonzeros, sum, max_val, retval); 20033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 20133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 20233f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double BitsEntropyCombined(const uint32_t* const X, 20333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t* const Y, int n) { 20433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double retval = 0.; 20533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int sum = 0; 20633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int nonzeros = 0; 20733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int max_val = 0; 20833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int i; 20933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < n; ++i) { 21033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int xy = X[i] + Y[i]; 21133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (xy != 0) { 21233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora sum += xy; 21333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora ++nonzeros; 21433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval -= VP8LFastSLog2(xy); 21533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (max_val < xy) { 21633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora max_val = xy; 21733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 21833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 219a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 22033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval += VP8LFastSLog2(sum); 22133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return BitsEntropyRefine(nonzeros, sum, max_val, retval); 22233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 22333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 22433f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double InitialHuffmanCost(void) { 22533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Small bias because Huffman code length is typically not stored in 22633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // full length. 22733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora static const int kHuffmanCodeOfHuffmanCodeSize = CODE_LENGTH_CODES * 3; 22833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora static const double kSmallBias = 9.1; 22933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return kHuffmanCodeOfHuffmanCodeSize - kSmallBias; 23033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 23133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 23233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Finalize the Huffman cost based on streak numbers and length type (<3 or >=3) 23333f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double FinalHuffmanCost(const VP8LStreaks* const stats) { 23433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double retval = InitialHuffmanCost(); 23533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval += stats->counts[0] * 1.5625 + 0.234375 * stats->streaks[0][1]; 23633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval += stats->counts[1] * 2.578125 + 0.703125 * stats->streaks[1][1]; 23733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval += 1.796875 * stats->streaks[0][0]; 23833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora retval += 3.28125 * stats->streaks[1][0]; 239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return retval; 240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 241a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 24233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Trampolines 24333f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double HuffmanCost(const uint32_t* const population, int length) { 24433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const VP8LStreaks stats = VP8LHuffmanCostCount(population, length); 24533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return FinalHuffmanCost(&stats); 24633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 24733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 24833f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double HuffmanCostCombined(const uint32_t* const X, 24933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t* const Y, int length) { 25033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const VP8LStreaks stats = VP8LHuffmanCostCombinedCount(X, Y, length); 25133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return FinalHuffmanCost(&stats); 25233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 25333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 25433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Aggregated costs 25533f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double PopulationCost(const uint32_t* const population, int length) { 2560406ce1417f76f2034833414dcecc9f56253640cVikas Arora return BitsEntropy(population, length) + HuffmanCost(population, length); 257a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 258a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 25933f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double GetCombinedEntropy(const uint32_t* const X, 26033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t* const Y, int length) { 26133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return BitsEntropyCombined(X, Y, length) + HuffmanCostCombined(X, Y, length); 2620406ce1417f76f2034833414dcecc9f56253640cVikas Arora} 2630406ce1417f76f2034833414dcecc9f56253640cVikas Arora 2640406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Estimates the Entropy + Huffman + other block overhead size cost. 265a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroradouble VP8LHistogramEstimateBits(const VP8LHistogram* const p) { 26633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return 26733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora PopulationCost(p->literal_, VP8LHistogramNumCodes(p->palette_code_bits_)) 26833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + PopulationCost(p->red_, NUM_LITERAL_CODES) 26933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + PopulationCost(p->blue_, NUM_LITERAL_CODES) 27033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + PopulationCost(p->alpha_, NUM_LITERAL_CODES) 27133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + PopulationCost(p->distance_, NUM_DISTANCE_CODES) 27233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + VP8LExtraCost(p->literal_ + NUM_LITERAL_CODES, NUM_LENGTH_CODES) 27333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + VP8LExtraCost(p->distance_, NUM_DISTANCE_CODES); 2740406ce1417f76f2034833414dcecc9f56253640cVikas Arora} 2750406ce1417f76f2034833414dcecc9f56253640cVikas Arora 2760406ce1417f76f2034833414dcecc9f56253640cVikas Aroradouble VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p) { 27733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return 27833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora BitsEntropy(p->literal_, VP8LHistogramNumCodes(p->palette_code_bits_)) 27933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + BitsEntropy(p->red_, NUM_LITERAL_CODES) 28033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + BitsEntropy(p->blue_, NUM_LITERAL_CODES) 28133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + BitsEntropy(p->alpha_, NUM_LITERAL_CODES) 28233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + BitsEntropy(p->distance_, NUM_DISTANCE_CODES) 28333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + VP8LExtraCost(p->literal_ + NUM_LITERAL_CODES, NUM_LENGTH_CODES) 28433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora + VP8LExtraCost(p->distance_, NUM_DISTANCE_CODES); 2850406ce1417f76f2034833414dcecc9f56253640cVikas Arora} 2860406ce1417f76f2034833414dcecc9f56253640cVikas Arora 2870406ce1417f76f2034833414dcecc9f56253640cVikas Arora// ----------------------------------------------------------------------------- 2880406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Various histogram combine/cost-eval functions 2890406ce1417f76f2034833414dcecc9f56253640cVikas Arora 29033f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic int GetCombinedHistogramEntropy(const VP8LHistogram* const a, 29133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const VP8LHistogram* const b, 29233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double cost_threshold, 29333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double* cost) { 29433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int palette_code_bits = a->palette_code_bits_; 29533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(a->palette_code_bits_ == b->palette_code_bits_); 29633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += GetCombinedEntropy(a->literal_, b->literal_, 29733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramNumCodes(palette_code_bits)); 29833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += VP8LExtraCostCombined(a->literal_ + NUM_LITERAL_CODES, 29933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora b->literal_ + NUM_LITERAL_CODES, 30033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora NUM_LENGTH_CODES); 30133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (*cost > cost_threshold) return 0; 30233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 30333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += GetCombinedEntropy(a->red_, b->red_, NUM_LITERAL_CODES); 30433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (*cost > cost_threshold) return 0; 30533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 30633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += GetCombinedEntropy(a->blue_, b->blue_, NUM_LITERAL_CODES); 30733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (*cost > cost_threshold) return 0; 30833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 30933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += GetCombinedEntropy(a->alpha_, b->alpha_, NUM_LITERAL_CODES); 31033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (*cost > cost_threshold) return 0; 31133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 31233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += GetCombinedEntropy(a->distance_, b->distance_, NUM_DISTANCE_CODES); 31333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *cost += VP8LExtraCostCombined(a->distance_, b->distance_, 31433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora NUM_DISTANCE_CODES); 31533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (*cost > cost_threshold) return 0; 31633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 31733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return 1; 318a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 319a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 3200406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Performs out = a + b, computing the cost C(a+b) - C(a) - C(b) while comparing 3210406ce1417f76f2034833414dcecc9f56253640cVikas Arora// to the threshold value 'cost_threshold'. The score returned is 3220406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Score = C(a+b) - C(a) - C(b), where C(a) + C(b) is known and fixed. 3230406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Since the previous score passed is 'cost_threshold', we only need to compare 3240406ce1417f76f2034833414dcecc9f56253640cVikas Arora// the partial cost against 'cost_threshold + C(a) + C(b)' to possibly bail-out 3250406ce1417f76f2034833414dcecc9f56253640cVikas Arora// early. 3260406ce1417f76f2034833414dcecc9f56253640cVikas Arorastatic double HistogramAddEval(const VP8LHistogram* const a, 3270406ce1417f76f2034833414dcecc9f56253640cVikas Arora const VP8LHistogram* const b, 3280406ce1417f76f2034833414dcecc9f56253640cVikas Arora VP8LHistogram* const out, 3290406ce1417f76f2034833414dcecc9f56253640cVikas Arora double cost_threshold) { 3300406ce1417f76f2034833414dcecc9f56253640cVikas Arora double cost = 0; 3310406ce1417f76f2034833414dcecc9f56253640cVikas Arora const double sum_cost = a->bit_cost_ + b->bit_cost_; 3320406ce1417f76f2034833414dcecc9f56253640cVikas Arora cost_threshold += sum_cost; 3330406ce1417f76f2034833414dcecc9f56253640cVikas Arora 33433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (GetCombinedHistogramEntropy(a, b, cost_threshold, &cost)) { 33533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramAdd(a, b, out); 33633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora out->bit_cost_ = cost; 33733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora out->palette_code_bits_ = a->palette_code_bits_; 3380406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 3390406ce1417f76f2034833414dcecc9f56253640cVikas Arora 3400406ce1417f76f2034833414dcecc9f56253640cVikas Arora return cost - sum_cost; 3410406ce1417f76f2034833414dcecc9f56253640cVikas Arora} 3420406ce1417f76f2034833414dcecc9f56253640cVikas Arora 3430406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Same as HistogramAddEval(), except that the resulting histogram 3440406ce1417f76f2034833414dcecc9f56253640cVikas Arora// is not stored. Only the cost C(a+b) - C(a) is evaluated. We omit 3450406ce1417f76f2034833414dcecc9f56253640cVikas Arora// the term C(b) which is constant over all the evaluations. 3460406ce1417f76f2034833414dcecc9f56253640cVikas Arorastatic double HistogramAddThresh(const VP8LHistogram* const a, 3470406ce1417f76f2034833414dcecc9f56253640cVikas Arora const VP8LHistogram* const b, 3480406ce1417f76f2034833414dcecc9f56253640cVikas Arora double cost_threshold) { 3490406ce1417f76f2034833414dcecc9f56253640cVikas Arora double cost = -a->bit_cost_; 35033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora GetCombinedHistogramEntropy(a, b, cost_threshold, &cost); 35133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return cost; 35233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 3530406ce1417f76f2034833414dcecc9f56253640cVikas Arora 35433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// ----------------------------------------------------------------------------- 3550406ce1417f76f2034833414dcecc9f56253640cVikas Arora 35633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// The structure to keep track of cost range for the three dominant entropy 35733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// symbols. 35833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// TODO(skal): Evaluate if float can be used here instead of double for 35933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// representing the entropy costs. 36033f74dabbc7920a65ed435d7417987589febdc16Vikas Aroratypedef struct { 36133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double literal_max_; 36233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double literal_min_; 36333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double red_max_; 36433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double red_min_; 36533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double blue_max_; 36633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double blue_min_; 36733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} DominantCostRange; 36833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 36933f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void DominantCostRangeInit(DominantCostRange* const c) { 37033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->literal_max_ = 0.; 37133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->literal_min_ = MAX_COST; 37233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->red_max_ = 0.; 37333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->red_min_ = MAX_COST; 37433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->blue_max_ = 0.; 37533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->blue_min_ = MAX_COST; 37633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 3770406ce1417f76f2034833414dcecc9f56253640cVikas Arora 37833f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void UpdateDominantCostRange( 37933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const VP8LHistogram* const h, DominantCostRange* const c) { 38033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (c->literal_max_ < h->literal_cost_) c->literal_max_ = h->literal_cost_; 38133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (c->literal_min_ > h->literal_cost_) c->literal_min_ = h->literal_cost_; 38233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (c->red_max_ < h->red_cost_) c->red_max_ = h->red_cost_; 38333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (c->red_min_ > h->red_cost_) c->red_min_ = h->red_cost_; 38433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (c->blue_max_ < h->blue_cost_) c->blue_max_ = h->blue_cost_; 38533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (c->blue_min_ > h->blue_cost_) c->blue_min_ = h->blue_cost_; 3860406ce1417f76f2034833414dcecc9f56253640cVikas Arora} 3870406ce1417f76f2034833414dcecc9f56253640cVikas Arora 38833f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void UpdateHistogramCost(VP8LHistogram* const h) { 38933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double alpha_cost = PopulationCost(h->alpha_, NUM_LITERAL_CODES); 39033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double distance_cost = 39133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora PopulationCost(h->distance_, NUM_DISTANCE_CODES) + 39233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LExtraCost(h->distance_, NUM_DISTANCE_CODES); 39333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int num_codes = VP8LHistogramNumCodes(h->palette_code_bits_); 39433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora h->literal_cost_ = PopulationCost(h->literal_, num_codes) + 39533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LExtraCost(h->literal_ + NUM_LITERAL_CODES, 39633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora NUM_LENGTH_CODES); 39733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora h->red_cost_ = PopulationCost(h->red_, NUM_LITERAL_CODES); 39833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora h->blue_cost_ = PopulationCost(h->blue_, NUM_LITERAL_CODES); 39933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora h->bit_cost_ = h->literal_cost_ + h->red_cost_ + h->blue_cost_ + 40033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora alpha_cost + distance_cost; 40133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 4020406ce1417f76f2034833414dcecc9f56253640cVikas Arora 40333f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic int GetBinIdForEntropy(double min, double max, double val) { 40433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double range = max - min + 1e-6; 40533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double delta = val - min; 40633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return (int)(NUM_PARTITIONS * delta / range); 40733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 40833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 40933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// TODO(vikasa): Evaluate, if there's any correlation between red & blue. 41033f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic int GetHistoBinIndex( 41133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const VP8LHistogram* const h, const DominantCostRange* const c) { 41233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int bin_id = 41333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora GetBinIdForEntropy(c->blue_min_, c->blue_max_, h->blue_cost_) + 41433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora NUM_PARTITIONS * GetBinIdForEntropy(c->red_min_, c->red_max_, 41533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora h->red_cost_) + 41633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora NUM_PARTITIONS * NUM_PARTITIONS * GetBinIdForEntropy(c->literal_min_, 41733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora c->literal_max_, 41833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora h->literal_cost_); 41933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(bin_id < BIN_SIZE); 42033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return bin_id; 42133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 42233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 42333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Construct the histograms from backward references. 42433f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramBuild( 42533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int xsize, int histo_bits, const VP8LBackwardRefs* const backward_refs, 42633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const image_histo) { 427a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int x = 0, y = 0; 428a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int histo_xsize = VP8LSubSampleSize(xsize, histo_bits); 42933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 43033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LRefsCursor c = VP8LRefsCursorInit(backward_refs); 431a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(histo_bits > 0); 43233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Construct the Histo from a given backward references. 43333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (VP8LRefsCursorOk(&c)) { 43433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const PixOrCopy* const v = c.cur_pos; 435a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int ix = (y >> histo_bits) * histo_xsize + (x >> histo_bits); 436a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramAddSinglePixOrCopy(histograms[ix], v); 437a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora x += PixOrCopyLength(v); 438a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (x >= xsize) { 439a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora x -= xsize; 440a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++y; 441a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 44233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LRefsCursorNext(&c); 443a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 444a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 445a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 44633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Copies the histograms and computes its bit_cost. 44733f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramCopyAndAnalyze( 44833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const orig_histo, VP8LHistogramSet* const image_histo) { 44933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int i; 45033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int histo_size = orig_histo->size; 45133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const orig_histograms = orig_histo->histograms; 45233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 45333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < histo_size; ++i) { 45433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* const histo = orig_histograms[i]; 45533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora UpdateHistogramCost(histo); 45633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Copy histograms from orig_histo[] to image_histo[]. 45733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCopy(histo, histograms[i]); 45833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 45933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 46033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 46133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Partition histograms to different entropy bins for three dominant (literal, 46233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// red and blue) symbol costs and compute the histogram aggregate bit_cost. 46333f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramAnalyzeEntropyBin( 46433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const image_histo, int16_t* const bin_map) { 46533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int i; 46633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 46733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int histo_size = image_histo->size; 46833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int bin_depth = histo_size + 1; 46933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora DominantCostRange cost_range; 47033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora DominantCostRangeInit(&cost_range); 47133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 47233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Analyze the dominant (literal, red and blue) entropy costs. 47333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < histo_size; ++i) { 47433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* const histo = histograms[i]; 47533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora UpdateDominantCostRange(histo, &cost_range); 47633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 47733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 47833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // bin-hash histograms on three of the dominant (literal, red and blue) 47933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // symbol costs. 48033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < histo_size; ++i) { 48133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int num_histos; 48233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* const histo = histograms[i]; 48333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int16_t bin_id = (int16_t)GetHistoBinIndex(histo, &cost_range); 48433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int bin_offset = bin_id * bin_depth; 48533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // bin_map[n][0] for every bin 'n' maintains the counter for the number of 48633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // histograms in that bin. 48733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Get and increment the num_histos in that bin. 48833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora num_histos = ++bin_map[bin_offset]; 48933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(bin_offset + num_histos < bin_depth * BIN_SIZE); 49033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Add histogram i'th index at num_histos (last) position in the bin_map. 49133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bin_map[bin_offset + num_histos] = i; 49233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 49333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 49433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 49533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Compact the histogram set by moving the valid one left in the set to the 49633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// head and moving the ones that have been merged to other histograms towards 49733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// the end. 49833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// TODO(vikasa): Evaluate if this method can be avoided by altering the code 49933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// logic of HistogramCombineEntropyBin main loop. 50033f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramCompactBins(VP8LHistogramSet* const image_histo) { 50133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int start = 0; 50233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int end = image_histo->size - 1; 50333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 50433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (start < end) { 50533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (start <= end && histograms[start] != NULL && 50633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histograms[start]->bit_cost_ != 0.) { 50733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora ++start; 50833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 50933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (start <= end && histograms[end]->bit_cost_ == 0.) { 51033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histograms[end] = NULL; 51133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora --end; 51233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 51333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (start < end) { 51433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(histograms[start] != NULL); 51533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(histograms[end] != NULL); 51633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCopy(histograms[end], histograms[start]); 51733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histograms[end] = NULL; 51833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora --end; 51933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 52033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 52133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora image_histo->size = end + 1; 52233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 52333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 52433f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramCombineEntropyBin(VP8LHistogramSet* const image_histo, 52533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* const histos, 52633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int16_t* const bin_map, int bin_depth, 52733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double combine_cost_factor) { 52833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int bin_id; 52933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* cur_combo = histos; 53033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 53133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 53233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (bin_id = 0; bin_id < BIN_SIZE; ++bin_id) { 53333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int bin_offset = bin_id * bin_depth; 53433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int num_histos = bin_map[bin_offset]; 53533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int idx1 = bin_map[bin_offset + 1]; 53633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int n; 53733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (n = 2; n <= num_histos; ++n) { 53833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int idx2 = bin_map[bin_offset + n]; 53933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double bit_cost_idx2 = histograms[idx2]->bit_cost_; 54033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (bit_cost_idx2 > 0.) { 54133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double bit_cost_thresh = -bit_cost_idx2 * combine_cost_factor; 54233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double curr_cost_diff = 54333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramAddEval(histograms[idx1], histograms[idx2], 54433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora cur_combo, bit_cost_thresh); 54533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (curr_cost_diff < bit_cost_thresh) { 54633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCopy(cur_combo, histograms[idx1]); 54733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histograms[idx2]->bit_cost_ = 0.; 54833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 54933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 55033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 55133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 55233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCompactBins(image_histo); 55333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 55433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 555a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic uint32_t MyRand(uint32_t *seed) { 556a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora *seed *= 16807U; 557a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (*seed == 0) { 558a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora *seed = 1; 559a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 560a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return *seed; 561a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 562a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 56333f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramCombine(VP8LHistogramSet* const image_histo, 56433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const histos, int quality) { 56533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int iter; 566a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t seed = 0; 567a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int tries_with_no_success = 0; 56833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int image_histo_size = image_histo->size; 56933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int iter_mult = (quality < 25) ? 2 : 2 + (quality - 25) / 8; 57033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int outer_iters = image_histo_size * iter_mult; 57133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int num_pairs = image_histo_size / 2; 57233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int num_tries_no_success = outer_iters / 2; 5731e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora const int min_cluster_size = 2; 57433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 57533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* cur_combo = histos->histograms[0]; // trial histogram 57633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram* best_combo = histos->histograms[1]; // best histogram so far 57733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 57833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Collapse similar histograms in 'image_histo'. 57933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (iter = 0; 58033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora iter < outer_iters && image_histo_size >= min_cluster_size; 58133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora ++iter) { 582a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double best_cost_diff = 0.; 5830406ce1417f76f2034833414dcecc9f56253640cVikas Arora int best_idx1 = -1, best_idx2 = 1; 584a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int j; 58533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int num_tries = 58633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora (num_pairs < image_histo_size) ? num_pairs : image_histo_size; 587a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora seed += iter; 5881e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora for (j = 0; j < num_tries; ++j) { 589a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double curr_cost_diff; 590a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Choose two histograms at random and try to combine them. 59133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t idx1 = MyRand(&seed) % image_histo_size; 5920406ce1417f76f2034833414dcecc9f56253640cVikas Arora const uint32_t tmp = (j & 7) + 1; 59333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t diff = 59433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora (tmp < 3) ? tmp : MyRand(&seed) % (image_histo_size - 1); 59533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint32_t idx2 = (idx1 + diff + 1) % image_histo_size; 596a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (idx1 == idx2) { 597a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora continue; 598a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 59933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 600a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Calculate cost reduction on combining. 60133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora curr_cost_diff = HistogramAddEval(histograms[idx1], histograms[idx2], 6020406ce1417f76f2034833414dcecc9f56253640cVikas Arora cur_combo, best_cost_diff); 6030406ce1417f76f2034833414dcecc9f56253640cVikas Arora if (curr_cost_diff < best_cost_diff) { // found a better pair? 604a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { // swap cur/best combo histograms 605a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogram* const tmp_histo = cur_combo; 606a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora cur_combo = best_combo; 607a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora best_combo = tmp_histo; 608a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 609a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora best_cost_diff = curr_cost_diff; 610a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora best_idx1 = idx1; 611a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora best_idx2 = idx2; 612a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 613a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 614a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 6150406ce1417f76f2034833414dcecc9f56253640cVikas Arora if (best_idx1 >= 0) { 61633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCopy(best_combo, histograms[best_idx1]); 617a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // swap best_idx2 slot with last one (which is now unused) 61833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora --image_histo_size; 61933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (best_idx2 != image_histo_size) { 62033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCopy(histograms[image_histo_size], histograms[best_idx2]); 62133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora histograms[image_histo_size] = NULL; 622a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 623a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tries_with_no_success = 0; 624a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 6251e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (++tries_with_no_success >= num_tries_no_success) { 626a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 627a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 628a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 62933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora image_histo->size = image_histo_size; 630a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 631a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 632a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 633a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Histogram refinement 634a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 635a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Find the best 'out' histogram for each of the 'in' histograms. 636a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Note: we assume that out[]->bit_cost_ is already up-to-date. 63733f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic void HistogramRemap(const VP8LHistogramSet* const orig_histo, 63833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const VP8LHistogramSet* const image_histo, 639a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint16_t* const symbols) { 640a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 64133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const orig_histograms = orig_histo->histograms; 64233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogram** const histograms = image_histo->histograms; 64333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < orig_histo->size; ++i) { 644a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int best_out = 0; 6450406ce1417f76f2034833414dcecc9f56253640cVikas Arora double best_bits = 64633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramAddThresh(histograms[0], orig_histograms[i], MAX_COST); 647a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 64833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (k = 1; k < image_histo->size; ++k) { 649a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const double cur_bits = 65033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramAddThresh(histograms[k], orig_histograms[i], best_bits); 651a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (cur_bits < best_bits) { 652a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora best_bits = cur_bits; 653a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora best_out = k; 654a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 655a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 656a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora symbols[i] = best_out; 657a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 658a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 659a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Recompute each out based on raw and symbols. 66033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < image_histo->size; ++i) { 66133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramClear(histograms[i]); 662a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 66333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 66433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora for (i = 0; i < orig_histo->size; ++i) { 66533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int idx = symbols[i]; 66633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramAdd(orig_histograms[i], histograms[idx], histograms[idx]); 667a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 668a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 669a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 67033f74dabbc7920a65ed435d7417987589febdc16Vikas Arorastatic double GetCombineCostFactor(int histo_size, int quality) { 67133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora double combine_cost_factor = 0.16; 67233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (histo_size > 256) combine_cost_factor /= 2.; 67333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (histo_size > 512) combine_cost_factor /= 2.; 67433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (histo_size > 1024) combine_cost_factor /= 2.; 67533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (quality <= 50) combine_cost_factor /= 2.; 67633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return combine_cost_factor; 67733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 67833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 679a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LGetHistoImageSymbols(int xsize, int ysize, 680a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const VP8LBackwardRefs* const refs, 681a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int quality, int histo_bits, int cache_bits, 68233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const image_histo, 683a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint16_t* const histogram_symbols) { 684a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int ok = 0; 685a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int histo_xsize = histo_bits ? VP8LSubSampleSize(xsize, histo_bits) : 1; 686a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int histo_ysize = histo_bits ? VP8LSubSampleSize(ysize, histo_bits) : 1; 68733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int image_histo_raw_size = histo_xsize * histo_ysize; 68833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 68933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // The bin_map for every bin follows following semantics: 69033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // bin_map[n][0] = num_histo; // The number of histograms in that bin. 69133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // bin_map[n][1] = index of first histogram in that bin; 69233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // bin_map[n][num_histo] = index of last histogram in that bin; 69333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // bin_map[n][num_histo + 1] ... bin_map[n][bin_depth - 1] = un-used indices. 69433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int bin_depth = image_histo_raw_size + 1; 69533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int16_t* bin_map = NULL; 69633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const histos = VP8LAllocateHistogramSet(2, cache_bits); 69733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LHistogramSet* const orig_histo = 69833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LAllocateHistogramSet(image_histo_raw_size, cache_bits); 69933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 70033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (orig_histo == NULL || histos == NULL) { 701a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 702a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 70333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 70433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Don't attempt linear bin-partition heuristic for: 70533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // histograms of small sizes, as bin_map will be very sparse and; 70633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Higher qualities (> 90), to preserve the compression gains at those 70733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // quality settings. 70833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (orig_histo->size > 2 * BIN_SIZE && quality < 90) { 70933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const int bin_map_size = bin_depth * BIN_SIZE; 71033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bin_map = (int16_t*)WebPSafeCalloc(bin_map_size, sizeof(*bin_map)); 71133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (bin_map == NULL) goto Error; 71233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 71333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 71433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Construct the histograms from backward references. 71533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramBuild(xsize, histo_bits, refs, orig_histo); 71633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Copies the histograms and computes its bit_cost. 71733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCopyAndAnalyze(orig_histo, image_histo); 71833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 71933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (bin_map != NULL) { 72033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const double combine_cost_factor = 72133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora GetCombineCostFactor(image_histo_raw_size, quality); 72233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramAnalyzeEntropyBin(orig_histo, bin_map); 72333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Collapse histograms with similar entropy. 72433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCombineEntropyBin(image_histo, histos->histograms[0], 72533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bin_map, bin_depth, combine_cost_factor); 72633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 72733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 72833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Collapse similar histograms by random histogram-pair compares. 72933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramCombine(image_histo, histos, quality); 73033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 731a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Find the optimal map from original histograms to the final ones. 73233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HistogramRemap(orig_histo, image_histo, histogram_symbols); 73333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 734a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ok = 1; 735a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 73633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora Error: 73733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(bin_map); 73833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LFreeHistogramSet(orig_histo); 73933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora VP8LFreeHistogramSet(histos); 740a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return ok; 741a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 742