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_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 #ifdef __cplusplus
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 uint32_t* literal_; // Pointer to the allocated buffer for literal.
36 uint32_t red_[NUM_LITERAL_CODES];
37 uint32_t blue_[NUM_LITERAL_CODES];
38 uint32_t alpha_[NUM_LITERAL_CODES];
39 // Backward reference prefix-code histogram.
40 uint32_t distance_[NUM_DISTANCE_CODES];
41 int palette_code_bits_;
42 double bit_cost_; // cached value of VP8LHistogramEstimateBits(this)
43 double literal_cost_; // Cached values of dominant entropy costs:
44 double red_cost_; // literal, red & blue.
45 double blue_cost_;
46 } VP8LHistogram;
47
48 // Collection of histograms with fixed capacity, allocated as one
49 // big memory chunk. Can be destroyed by calling WebPSafeFree().
50 typedef struct {
51 int size; // number of slots currently in use
52 int max_size; // maximum capacity
53 VP8LHistogram** histograms;
54 } VP8LHistogramSet;
55
56 // Create the histogram.
57 //
58 // The input data is the PixOrCopy data, which models the literals, stop
59 // codes and backward references (both distances and lengths). Also: if
60 // palette_code_bits is >= 0, initialize the histogram with this value.
61 void VP8LHistogramCreate(VP8LHistogram* const p,
62 const VP8LBackwardRefs* const refs,
63 int palette_code_bits);
64
65 // Return the size of the histogram for a given palette_code_bits.
66 int VP8LGetHistogramSize(int palette_code_bits);
67
68 // Set the palette_code_bits and reset the stats.
69 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits);
70
71 // Collect all the references into a histogram (without reset)
72 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs,
73 VP8LHistogram* const histo);
74
75 // Free the memory allocated for the histogram.
76 void VP8LFreeHistogram(VP8LHistogram* const histo);
77
78 // Free the memory allocated for the histogram set.
79 void VP8LFreeHistogramSet(VP8LHistogramSet* const histo);
80
81 // Allocate an array of pointer to histograms, allocated and initialized
82 // using 'cache_bits'. Return NULL in case of memory error.
83 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits);
84
85 // Allocate and initialize histogram object with specified 'cache_bits'.
86 // Returns NULL in case of memory error.
87 // Special case of VP8LAllocateHistogramSet, with size equals 1.
88 VP8LHistogram* VP8LAllocateHistogram(int cache_bits);
89
90 // Accumulate a token 'v' into a histogram.
91 void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo,
92 const PixOrCopy* const v);
93
94 // Estimate how many bits the combined entropy of literals and distance
95 // approximately maps to.
96 double VP8LHistogramEstimateBits(const VP8LHistogram* const p);
97
98 // This function estimates the cost in bits excluding the bits needed to
99 // represent the entropy code itself.
100 double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p);
101
VP8LHistogramNumCodes(int palette_code_bits)102 static WEBP_INLINE int VP8LHistogramNumCodes(int palette_code_bits) {
103 return NUM_LITERAL_CODES + NUM_LENGTH_CODES +
104 ((palette_code_bits > 0) ? (1 << palette_code_bits) : 0);
105 }
106
107 // Builds the histogram image.
108 int VP8LGetHistoImageSymbols(int xsize, int ysize,
109 const VP8LBackwardRefs* const refs,
110 int quality, int histogram_bits, int cache_bits,
111 VP8LHistogramSet* const image_in,
112 uint16_t* const histogram_symbols);
113
114 #ifdef __cplusplus
115 }
116 #endif
117
118 #endif // WEBP_ENC_HISTOGRAM_H_
119