1 // Copyright 2012 Google Inc. All Rights Reserved.
2 //
3 // This code is licensed under the same terms as WebM:
4 // Software License Agreement: http://www.webmproject.org/license/software/
5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/
6 // -----------------------------------------------------------------------------
7 //
8 // Author: Jyrki Alakuijala (jyrki@google.com)
9 //
10 // Models the histograms of literal and distance codes.
11
12 #ifndef WEBP_ENC_HISTOGRAM_H_
13 #define WEBP_ENC_HISTOGRAM_H_
14
15 #include <assert.h>
16 #include <stddef.h>
17 #include <stdlib.h>
18 #include <stdio.h>
19 #include <string.h>
20
21 #include "./backward_references.h"
22 #include "webp/format_constants.h"
23 #include "webp/types.h"
24
25 #if defined(__cplusplus) || defined(c_plusplus)
26 extern "C" {
27 #endif
28
29 // A simple container for histograms of data.
30 typedef struct {
31 // literal_ contains green literal, palette-code and
32 // copy-length-prefix histogram
33 int literal_[PIX_OR_COPY_CODES_MAX];
34 int red_[256];
35 int blue_[256];
36 int alpha_[256];
37 // Backward reference prefix-code histogram.
38 int distance_[NUM_DISTANCE_CODES];
39 int palette_code_bits_;
40 double bit_cost_; // cached value of VP8LHistogramEstimateBits(this)
41 } VP8LHistogram;
42
43 // Collection of histograms with fixed capacity, allocated as one
44 // big memory chunk. Can be destroyed by simply calling 'free()'.
45 typedef struct {
46 int size; // number of slots currently in use
47 int max_size; // maximum capacity
48 VP8LHistogram** histograms;
49 } VP8LHistogramSet;
50
51 // Create the histogram.
52 //
53 // The input data is the PixOrCopy data, which models the literals, stop
54 // codes and backward references (both distances and lengths). Also: if
55 // palette_code_bits is >= 0, initialize the histogram with this value.
56 void VP8LHistogramCreate(VP8LHistogram* const p,
57 const VP8LBackwardRefs* const refs,
58 int palette_code_bits);
59
60 // Set the palette_code_bits and reset the stats.
61 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits);
62
63 // Collect all the references into a histogram (without reset)
64 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs,
65 VP8LHistogram* const histo);
66
67 // Allocate an array of pointer to histograms, allocated and initialized
68 // using 'cache_bits'. Return NULL in case of memory error.
69 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits);
70
71 // Accumulate a token 'v' into a histogram.
72 void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo,
73 const PixOrCopy* const v);
74
75 // Estimate how many bits the combined entropy of literals and distance
76 // approximately maps to.
77 double VP8LHistogramEstimateBits(const VP8LHistogram* const p);
78
79 // This function estimates the cost in bits excluding the bits needed to
80 // represent the entropy code itself.
81 double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p);
82
VP8LHistogramAdd(VP8LHistogram * const p,const VP8LHistogram * const a)83 static WEBP_INLINE void VP8LHistogramAdd(VP8LHistogram* const p,
84 const VP8LHistogram* const a) {
85 int i;
86 for (i = 0; i < PIX_OR_COPY_CODES_MAX; ++i) {
87 p->literal_[i] += a->literal_[i];
88 }
89 for (i = 0; i < NUM_DISTANCE_CODES; ++i) {
90 p->distance_[i] += a->distance_[i];
91 }
92 for (i = 0; i < 256; ++i) {
93 p->red_[i] += a->red_[i];
94 p->blue_[i] += a->blue_[i];
95 p->alpha_[i] += a->alpha_[i];
96 }
97 }
98
VP8LHistogramNumCodes(const VP8LHistogram * const p)99 static WEBP_INLINE int VP8LHistogramNumCodes(const VP8LHistogram* const p) {
100 return 256 + NUM_LENGTH_CODES +
101 ((p->palette_code_bits_ > 0) ? (1 << p->palette_code_bits_) : 0);
102 }
103
104 // Builds the histogram image.
105 int VP8LGetHistoImageSymbols(int xsize, int ysize,
106 const VP8LBackwardRefs* const refs,
107 int quality, int histogram_bits, int cache_bits,
108 VP8LHistogramSet* const image_in,
109 uint16_t* const histogram_symbols);
110
111 #if defined(__cplusplus) || defined(c_plusplus)
112 }
113 #endif
114
115 #endif // WEBP_ENC_HISTOGRAM_H_
116