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
24extern "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.
31typedef 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().
52typedef 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.
63void 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.
68int 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.
72void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits,
73 int init_arrays);
74
75// Collect all the references into a histogram (without reset)
76void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs,
77 VP8LHistogram* const histo);
78
79// Free the memory allocated for the histogram.
80void VP8LFreeHistogram(VP8LHistogram* const histo);
81
82// Free the memory allocated for the histogram set.
83void 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.
87VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits);
88
89// Set the histograms in set to 0.
90void 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.
95VP8LHistogram* VP8LAllocateHistogram(int cache_bits);
96
97// Accumulate a token 'v' into a histogram.
98void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo,
99 const PixOrCopy* const v,
100 int (*const distance_modifier)(int, int),
101 int distance_modifier_arg0);
102
103static 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.
109int 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.
118double 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.
122double VP8LHistogramEstimateBits(VP8LHistogram* const p);
123
124#ifdef __cplusplus
125}
126#endif
127
128#endif // WEBP_ENC_HISTOGRAM_ENC_H_
129