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 (at) google.com) 11 // 12 // Models the histograms of literal and distance codes. 13 14 #ifndef WEBP_ENC_HISTOGRAM_ENC_H_ 15 #define WEBP_ENC_HISTOGRAM_ENC_H_ 16 17 #include <string.h> 18 19 #include "src/enc/backward_references_enc.h" 20 #include "src/webp/format_constants.h" 21 #include "src/webp/types.h" 22 23 #ifdef __cplusplus 24 extern "C" { 25 #endif 26 27 // Not a trivial literal symbol. 28 #define VP8L_NON_TRIVIAL_SYM (0xffffffff) 29 30 // A simple container for histograms of data. 31 typedef struct { 32 // literal_ contains green literal, palette-code and 33 // copy-length-prefix histogram 34 uint32_t* literal_; // Pointer to the allocated buffer for literal. 35 uint32_t red_[NUM_LITERAL_CODES]; 36 uint32_t blue_[NUM_LITERAL_CODES]; 37 uint32_t alpha_[NUM_LITERAL_CODES]; 38 // Backward reference prefix-code histogram. 39 uint32_t distance_[NUM_DISTANCE_CODES]; 40 int palette_code_bits_; 41 uint32_t trivial_symbol_; // True, if histograms for Red, Blue & Alpha 42 // literal symbols are single valued. 43 double bit_cost_; // cached value of bit cost. 44 double literal_cost_; // Cached values of dominant entropy costs: 45 double red_cost_; // literal, red & blue. 46 double blue_cost_; 47 } VP8LHistogram; 48 49 // Collection of histograms with fixed capacity, allocated as one 50 // big memory chunk. Can be destroyed by calling WebPSafeFree(). 51 typedef struct { 52 int size; // number of slots currently in use 53 int max_size; // maximum capacity 54 VP8LHistogram** histograms; 55 } VP8LHistogramSet; 56 57 // Create the histogram. 58 // 59 // The input data is the PixOrCopy data, which models the literals, stop 60 // codes and backward references (both distances and lengths). Also: if 61 // palette_code_bits is >= 0, initialize the histogram with this value. 62 void VP8LHistogramCreate(VP8LHistogram* const p, 63 const VP8LBackwardRefs* const refs, 64 int palette_code_bits); 65 66 // Return the size of the histogram for a given palette_code_bits. 67 int VP8LGetHistogramSize(int palette_code_bits); 68 69 // Set the palette_code_bits and reset the stats. 70 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits); 71 72 // Collect all the references into a histogram (without reset) 73 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 74 VP8LHistogram* const histo); 75 76 // Free the memory allocated for the histogram. 77 void VP8LFreeHistogram(VP8LHistogram* const histo); 78 79 // Free the memory allocated for the histogram set. 80 void VP8LFreeHistogramSet(VP8LHistogramSet* const histo); 81 82 // Allocate an array of pointer to histograms, allocated and initialized 83 // using 'cache_bits'. Return NULL in case of memory error. 84 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits); 85 86 // Allocate and initialize histogram object with specified 'cache_bits'. 87 // Returns NULL in case of memory error. 88 // Special case of VP8LAllocateHistogramSet, with size equals 1. 89 VP8LHistogram* VP8LAllocateHistogram(int cache_bits); 90 91 // Accumulate a token 'v' into a histogram. 92 void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, 93 const PixOrCopy* const v, 94 int (*const distance_modifier)(int, int), 95 int distance_modifier_arg0); 96 97 static WEBP_INLINE int VP8LHistogramNumCodes(int palette_code_bits) { 98 return NUM_LITERAL_CODES + NUM_LENGTH_CODES + 99 ((palette_code_bits > 0) ? (1 << palette_code_bits) : 0); 100 } 101 102 // Builds the histogram image. 103 int VP8LGetHistoImageSymbols(int xsize, int ysize, 104 const VP8LBackwardRefs* const refs, 105 int quality, int low_effort, 106 int histogram_bits, int cache_bits, 107 VP8LHistogramSet* const image_in, 108 VP8LHistogram* const tmp_histo, 109 uint16_t* const histogram_symbols); 110 111 // Returns the entropy for the symbols in the input array. 112 // Also sets trivial_symbol to the code value, if the array has only one code 113 // value. Otherwise, set it to VP8L_NON_TRIVIAL_SYM. 114 double VP8LBitsEntropy(const uint32_t* const array, int n, 115 uint32_t* const trivial_symbol); 116 117 // Estimate how many bits the combined entropy of literals and distance 118 // approximately maps to. 119 double VP8LHistogramEstimateBits(const VP8LHistogram* const p); 120 121 #ifdef __cplusplus 122 } 123 #endif 124 125 #endif // WEBP_ENC_HISTOGRAM_ENC_H_ 126
