histogram_enc.h (5139B)
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_ENC_H_ 15 #define WEBP_ENC_HISTOGRAM_ENC_H_ 16 17 #include "src/enc/backward_references_enc.h" 18 #include "src/webp/encode.h" 19 #include "src/webp/format_constants.h" 20 #include "src/webp/types.h" 21 22 #ifdef __cplusplus 23 extern "C" { 24 #endif 25 26 // Not a trivial literal symbol. 27 #define VP8L_NON_TRIVIAL_SYM ((uint16_t)(0xffff)) 28 29 // A simple container for histograms of data. 30 typedef struct { 31 // 'literal' contains green literal, palette-code and 32 // copy-length-prefix histogram 33 uint32_t* literal; // Pointer to the allocated buffer for literal. 34 uint32_t red[NUM_LITERAL_CODES]; 35 uint32_t blue[NUM_LITERAL_CODES]; 36 uint32_t alpha[NUM_LITERAL_CODES]; 37 // Backward reference prefix-code histogram. 38 uint32_t distance[NUM_DISTANCE_CODES]; 39 int palette_code_bits; 40 // The following members are only used within VP8LGetHistoImageSymbols. 41 42 // Index of the unique value of a histogram if any, VP8L_NON_TRIVIAL_SYM 43 // otherwise. 44 uint16_t trivial_symbol[5]; 45 uint64_t bit_cost; // Cached value of total bit cost. 46 // Cached values of entropy costs: literal, red, blue, alpha, distance 47 uint64_t costs[5]; 48 uint8_t is_used[5]; // 5 for literal, red, blue, alpha, distance 49 uint16_t bin_id; // entropy bin index. 50 } VP8LHistogram; 51 52 // Collection of histograms with fixed capacity, allocated as one 53 // big memory chunk. Can be destroyed by calling WebPSafeFree(). 54 typedef struct { 55 int size; // number of slots currently in use 56 int max_size; // maximum capacity 57 VP8LHistogram** histograms; 58 } VP8LHistogramSet; 59 60 // Create the histogram. 61 // 62 // The input data is the PixOrCopy data, which models the literals, stop 63 // codes and backward references (both distances and lengths). Also: if 64 // palette_code_bits is >= 0, initialize the histogram with this value. 65 void VP8LHistogramCreate(VP8LHistogram* const h, 66 const VP8LBackwardRefs* const refs, 67 int palette_code_bits); 68 69 // Set the palette_code_bits and reset the stats. 70 // If init_arrays is true, the arrays are also filled with 0's. 71 void VP8LHistogramInit(VP8LHistogram* const h, int palette_code_bits, 72 int init_arrays); 73 74 // Collect all the references into a histogram (without reset) 75 // The distance modifier function is applied to the distance before 76 // the histogram is updated. It can be NULL. 77 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 78 int (*const distance_modifier)(int, int), 79 int distance_modifier_arg0, 80 VP8LHistogram* const histo); 81 82 // Free the memory allocated for the histogram. 83 void VP8LFreeHistogram(VP8LHistogram* const histo); 84 85 // Free the memory allocated for the histogram set. 86 void VP8LFreeHistogramSet(VP8LHistogramSet* const histo); 87 88 // Allocate an array of pointer to histograms, allocated and initialized 89 // using 'cache_bits'. Return NULL in case of memory error. 90 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits); 91 92 // Set the histograms in set to 0. 93 void VP8LHistogramSetClear(VP8LHistogramSet* const set); 94 95 // Allocate and initialize histogram object with specified 'cache_bits'. 96 // Returns NULL in case of memory error. 97 // Special case of VP8LAllocateHistogramSet, with size equals 1. 98 VP8LHistogram* VP8LAllocateHistogram(int cache_bits); 99 100 static WEBP_INLINE int VP8LHistogramNumCodes(int palette_code_bits) { 101 return NUM_LITERAL_CODES + NUM_LENGTH_CODES + 102 ((palette_code_bits > 0) ? (1 << palette_code_bits) : 0); 103 } 104 105 // Builds the histogram image. pic and percent are for progress. 106 // Returns false in case of error (stored in pic->error_code). 107 int VP8LGetHistoImageSymbols(int xsize, int ysize, 108 const VP8LBackwardRefs* const refs, int quality, 109 int low_effort, int histogram_bits, int cache_bits, 110 VP8LHistogramSet* const image_histo, 111 VP8LHistogram* const tmp_histo, 112 uint32_t* const histogram_symbols, 113 const WebPPicture* const pic, int percent_range, 114 int* const percent); 115 116 // Returns the entropy for the symbols in the input array. 117 uint64_t VP8LBitsEntropy(const uint32_t* const array, int n); 118 119 // Estimate how many bits the combined entropy of literals and distance 120 // approximately maps to. 121 uint64_t VP8LHistogramEstimateBits(const VP8LHistogram* const h); 122 123 #ifdef __cplusplus 124 } 125 #endif 126 127 #endif // WEBP_ENC_HISTOGRAM_ENC_H_