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
28extern "C" {
29#endif
30
31// A simple container for histograms of data.
32typedef 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().
50typedef 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.
61void 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.
66int VP8LGetHistogramSize(int palette_code_bits);
67
68// Set the palette_code_bits and reset the stats.
69void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits);
70
71// Collect all the references into a histogram (without reset)
72void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs,
73                            VP8LHistogram* const histo);
74
75// Free the memory allocated for the histogram.
76void VP8LFreeHistogram(VP8LHistogram* const histo);
77
78// Free the memory allocated for the histogram set.
79void 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.
83VP8LHistogramSet* 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.
88VP8LHistogram* VP8LAllocateHistogram(int cache_bits);
89
90// Accumulate a token 'v' into a histogram.
91void 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.
96double 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.
100double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p);
101
102static 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.
108int 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