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 } 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
VP8LHistogramNumCodes(int palette_code_bits)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