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_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 #if defined(__cplusplus) || defined(c_plusplus) 28 extern "C" { 29 #endif 30 31 // A simple container for histograms of data. 32 typedef struct { 33 // literal_ contains green literal, palette-code and 34 // copy-length-prefix histogram 35 int literal_[PIX_OR_COPY_CODES_MAX]; 36 int red_[256]; 37 int blue_[256]; 38 int alpha_[256]; 39 // Backward reference prefix-code histogram. 40 int distance_[NUM_DISTANCE_CODES]; 41 int palette_code_bits_; 42 double bit_cost_; // cached value of VP8LHistogramEstimateBits(this) 43 } VP8LHistogram; 44 45 // Collection of histograms with fixed capacity, allocated as one 46 // big memory chunk. Can be destroyed by simply calling 'free()'. 47 typedef struct { 48 int size; // number of slots currently in use 49 int max_size; // maximum capacity 50 VP8LHistogram** histograms; 51 } VP8LHistogramSet; 52 53 // Create the histogram. 54 // 55 // The input data is the PixOrCopy data, which models the literals, stop 56 // codes and backward references (both distances and lengths). Also: if 57 // palette_code_bits is >= 0, initialize the histogram with this value. 58 void VP8LHistogramCreate(VP8LHistogram* const p, 59 const VP8LBackwardRefs* const refs, 60 int palette_code_bits); 61 62 // Set the palette_code_bits and reset the stats. 63 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits); 64 65 // Collect all the references into a histogram (without reset) 66 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 67 VP8LHistogram* const histo); 68 69 // Allocate an array of pointer to histograms, allocated and initialized 70 // using 'cache_bits'. Return NULL in case of memory error. 71 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits); 72 73 // Accumulate a token 'v' into a histogram. 74 void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, 75 const PixOrCopy* const v); 76 77 // Estimate how many bits the combined entropy of literals and distance 78 // approximately maps to. 79 double VP8LHistogramEstimateBits(const VP8LHistogram* const p); 80 81 // This function estimates the cost in bits excluding the bits needed to 82 // represent the entropy code itself. 83 double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p); 84 85 static WEBP_INLINE int VP8LHistogramNumCodes(const VP8LHistogram* const p) { 86 return 256 + NUM_LENGTH_CODES + 87 ((p->palette_code_bits_ > 0) ? (1 << p->palette_code_bits_) : 0); 88 } 89 90 // Builds the histogram image. 91 int VP8LGetHistoImageSymbols(int xsize, int ysize, 92 const VP8LBackwardRefs* const refs, 93 int quality, int histogram_bits, int cache_bits, 94 VP8LHistogramSet* const image_in, 95 uint16_t* const histogram_symbols); 96 97 #if defined(__cplusplus) || defined(c_plusplus) 98 } 99 #endif 100 101 #endif // WEBP_ENC_HISTOGRAM_H_ 102