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 <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 | uint8_t is_used_[5]; // 5 for literal, red, blue, alpha, distance |
48 | } VP8LHistogram; |
49 | |
50 | // Collection of histograms with fixed capacity, allocated as one |
51 | // big memory chunk. Can be destroyed by calling WebPSafeFree(). |
52 | typedef struct { |
53 | int size; // number of slots currently in use |
54 | int max_size; // maximum capacity |
55 | VP8LHistogram** histograms; |
56 | } VP8LHistogramSet; |
57 | |
58 | // Create the histogram. |
59 | // |
60 | // The input data is the PixOrCopy data, which models the literals, stop |
61 | // codes and backward references (both distances and lengths). Also: if |
62 | // palette_code_bits is >= 0, initialize the histogram with this value. |
63 | void VP8LHistogramCreate(VP8LHistogram* const p, |
64 | const VP8LBackwardRefs* const refs, |
65 | int palette_code_bits); |
66 | |
67 | // Return the size of the histogram for a given palette_code_bits. |
68 | int VP8LGetHistogramSize(int palette_code_bits); |
69 | |
70 | // Set the palette_code_bits and reset the stats. |
71 | // If init_arrays is true, the arrays are also filled with 0's. |
72 | void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits, |
73 | int init_arrays); |
74 | |
75 | // Collect all the references into a histogram (without reset) |
76 | void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, |
77 | VP8LHistogram* const histo); |
78 | |
79 | // Free the memory allocated for the histogram. |
80 | void VP8LFreeHistogram(VP8LHistogram* const histo); |
81 | |
82 | // Free the memory allocated for the histogram set. |
83 | void VP8LFreeHistogramSet(VP8LHistogramSet* const histo); |
84 | |
85 | // Allocate an array of pointer to histograms, allocated and initialized |
86 | // using 'cache_bits'. Return NULL in case of memory error. |
87 | VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits); |
88 | |
89 | // Set the histograms in set to 0. |
90 | void VP8LHistogramSetClear(VP8LHistogramSet* const set); |
91 | |
92 | // Allocate and initialize histogram object with specified 'cache_bits'. |
93 | // Returns NULL in case of memory error. |
94 | // Special case of VP8LAllocateHistogramSet, with size equals 1. |
95 | VP8LHistogram* VP8LAllocateHistogram(int cache_bits); |
96 | |
97 | // Accumulate a token 'v' into a histogram. |
98 | void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, |
99 | const PixOrCopy* const v, |
100 | int (*const distance_modifier)(int, int), |
101 | int distance_modifier_arg0); |
102 | |
103 | static WEBP_INLINE int VP8LHistogramNumCodes(int palette_code_bits) { |
104 | return NUM_LITERAL_CODES + NUM_LENGTH_CODES + |
105 | ((palette_code_bits > 0) ? (1 << palette_code_bits) : 0); |
106 | } |
107 | |
108 | // Builds the histogram image. |
109 | int VP8LGetHistoImageSymbols(int xsize, int ysize, |
110 | const VP8LBackwardRefs* const refs, |
111 | int quality, int low_effort, |
112 | int histogram_bits, int cache_bits, |
113 | VP8LHistogramSet* const image_in, |
114 | VP8LHistogram* const tmp_histo, |
115 | uint16_t* const histogram_symbols); |
116 | |
117 | // Returns the entropy for the symbols in the input array. |
118 | double VP8LBitsEntropy(const uint32_t* const array, int n); |
119 | |
120 | // Estimate how many bits the combined entropy of literals and distance |
121 | // approximately maps to. |
122 | double VP8LHistogramEstimateBits(VP8LHistogram* const p); |
123 | |
124 | #ifdef __cplusplus |
125 | } |
126 | #endif |
127 | |
128 | #endif // WEBP_ENC_HISTOGRAM_ENC_H_ |
129 | |