1// Copyright 2012 Google Inc. All Rights Reserved. 2// 3// Use of this source code is governed by a BSD-style license 4// that can be found in the COPYING file in the root of the source 5// tree. An additional intellectual property rights grant can be found 6// in the file PATENTS. All contributing project authors may 7// be found in the AUTHORS file in the root of the source tree. 8// ----------------------------------------------------------------------------- 9// 10// Author: Jyrki Alakuijala (jyrki@google.com) 11// 12// Models the histograms of literal and distance codes. 13 14#ifndef WEBP_ENC_HISTOGRAM_H_ 15#define WEBP_ENC_HISTOGRAM_H_ 16 17#include <assert.h> 18#include <stddef.h> 19#include <stdlib.h> 20#include <stdio.h> 21#include <string.h> 22 23#include "./backward_references.h" 24#include "webp/format_constants.h" 25#include "webp/types.h" 26 27#ifdef __cplusplus 28extern "C" { 29#endif 30 31// A simple container for histograms of data. 32typedef struct { 33 // literal_ contains green literal, palette-code and 34 // copy-length-prefix histogram 35 uint32_t* literal_; // Pointer to the allocated buffer for literal. 36 uint32_t red_[NUM_LITERAL_CODES]; 37 uint32_t blue_[NUM_LITERAL_CODES]; 38 uint32_t alpha_[NUM_LITERAL_CODES]; 39 // Backward reference prefix-code histogram. 40 uint32_t distance_[NUM_DISTANCE_CODES]; 41 int palette_code_bits_; 42 double bit_cost_; // cached value of VP8LHistogramEstimateBits(this) 43 double literal_cost_; // Cached values of dominant entropy costs: 44 double red_cost_; // literal, red & blue. 45 double blue_cost_; 46} VP8LHistogram; 47 48// Collection of histograms with fixed capacity, allocated as one 49// big memory chunk. Can be destroyed by calling WebPSafeFree(). 50typedef struct { 51 int size; // number of slots currently in use 52 int max_size; // maximum capacity 53 VP8LHistogram** histograms; 54} VP8LHistogramSet; 55 56// Create the histogram. 57// 58// The input data is the PixOrCopy data, which models the literals, stop 59// codes and backward references (both distances and lengths). Also: if 60// palette_code_bits is >= 0, initialize the histogram with this value. 61void VP8LHistogramCreate(VP8LHistogram* const p, 62 const VP8LBackwardRefs* const refs, 63 int palette_code_bits); 64 65// Return the size of the histogram for a given palette_code_bits. 66int VP8LGetHistogramSize(int palette_code_bits); 67 68// Set the palette_code_bits and reset the stats. 69void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits); 70 71// Collect all the references into a histogram (without reset) 72void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 73 VP8LHistogram* const histo); 74 75// Free the memory allocated for the histogram. 76void VP8LFreeHistogram(VP8LHistogram* const histo); 77 78// Free the memory allocated for the histogram set. 79void VP8LFreeHistogramSet(VP8LHistogramSet* const histo); 80 81// Allocate an array of pointer to histograms, allocated and initialized 82// using 'cache_bits'. Return NULL in case of memory error. 83VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits); 84 85// Allocate and initialize histogram object with specified 'cache_bits'. 86// Returns NULL in case of memory error. 87// Special case of VP8LAllocateHistogramSet, with size equals 1. 88VP8LHistogram* VP8LAllocateHistogram(int cache_bits); 89 90// Accumulate a token 'v' into a histogram. 91void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, 92 const PixOrCopy* const v); 93 94// Estimate how many bits the combined entropy of literals and distance 95// approximately maps to. 96double VP8LHistogramEstimateBits(const VP8LHistogram* const p); 97 98// This function estimates the cost in bits excluding the bits needed to 99// represent the entropy code itself. 100double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p); 101 102static WEBP_INLINE int VP8LHistogramNumCodes(int palette_code_bits) { 103 return NUM_LITERAL_CODES + NUM_LENGTH_CODES + 104 ((palette_code_bits > 0) ? (1 << palette_code_bits) : 0); 105} 106 107// Builds the histogram image. 108int VP8LGetHistoImageSymbols(int xsize, int ysize, 109 const VP8LBackwardRefs* const refs, 110 int quality, int histogram_bits, int cache_bits, 111 VP8LHistogramSet* const image_in, 112 uint16_t* const histogram_symbols); 113 114#ifdef __cplusplus 115} 116#endif 117 118#endif // WEBP_ENC_HISTOGRAM_H_ 119