src/third_party/libwebp/enc/histogram.h

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