histogram.h revision 2a99a7e74a7f215066514fe81d2bfa6639d9eddd 
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)
26extern "C" {
27#endif
28
29// A simple container for histograms of data.
30typedef 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()'.
45typedef 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.
56void 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.
61void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits);
62
63// Collect all the references into a histogram (without reset)
64void 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.
69VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits);
70
71// Accumulate a token 'v' into a histogram.
72void 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.
77double 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.
81double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p);
82
83static WEBP_INLINE int VP8LHistogramNumCodes(const VP8LHistogram* const p) {
84  return 256 + NUM_LENGTH_CODES +
85      ((p->palette_code_bits_ > 0) ? (1 << p->palette_code_bits_) : 0);
86}
87
88// Builds the histogram image.
89int VP8LGetHistoImageSymbols(int xsize, int ysize,
90                             const VP8LBackwardRefs* const refs,
91                             int quality, int histogram_bits, int cache_bits,
92                             VP8LHistogramSet* const image_in,
93                             uint16_t* const histogram_symbols);
94
95#if defined(__cplusplus) || defined(c_plusplus)
96}
97#endif
98
99#endif  // WEBP_ENC_HISTOGRAM_H_
100