Home | History | Annotate | Download | only in enc 
      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 (at) 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 <string.h>
     18 
     19 #include "./backward_references.h"
     20 #include "../webp/format_constants.h"
     21 #include "../webp/types.h"
     22 
     23 #ifdef __cplusplus
     24 extern "C" {
     25 #endif
     26 
     27 // Not a trivial literal symbol.
     28 #define VP8L_NON_TRIVIAL_SYM (0xffffffff)
     29 
     30 // A simple container for histograms of data.
     31 typedef struct {
     32   // literal_ contains green literal, palette-code and
     33   // copy-length-prefix histogram
     34   uint32_t* literal_;         // Pointer to the allocated buffer for literal.
     35   uint32_t red_[NUM_LITERAL_CODES];
     36   uint32_t blue_[NUM_LITERAL_CODES];
     37   uint32_t alpha_[NUM_LITERAL_CODES];
     38   // Backward reference prefix-code histogram.
     39   uint32_t distance_[NUM_DISTANCE_CODES];
     40   int palette_code_bits_;
     41   uint32_t trivial_symbol_;  // True, if histograms for Red, Blue & Alpha
     42                              // literal symbols are single valued.
     43   double bit_cost_;          // cached value of bit cost.
     44   double literal_cost_;      // Cached values of dominant entropy costs:
     45   double red_cost_;          // literal, red & blue.
     46   double blue_cost_;
     47 } VP8LHistogram;
     48 
     49 // Collection of histograms with fixed capacity, allocated as one
     50 // big memory chunk. Can be destroyed by calling WebPSafeFree().
     51 typedef struct {
     52   int size;         // number of slots currently in use
     53   int max_size;     // maximum capacity
     54   VP8LHistogram** histograms;
     55 } VP8LHistogramSet;
     56 
     57 // Create the histogram.
     58 //
     59 // The input data is the PixOrCopy data, which models the literals, stop
     60 // codes and backward references (both distances and lengths).  Also: if
     61 // palette_code_bits is >= 0, initialize the histogram with this value.
     62 void VP8LHistogramCreate(VP8LHistogram* const p,
     63                          const VP8LBackwardRefs* const refs,
     64                          int palette_code_bits);
     65 
     66 // Return the size of the histogram for a given palette_code_bits.
     67 int VP8LGetHistogramSize(int palette_code_bits);
     68 
     69 // Set the palette_code_bits and reset the stats.
     70 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits);
     71 
     72 // Collect all the references into a histogram (without reset)
     73 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs,
     74                             VP8LHistogram* const histo);
     75 
     76 // Free the memory allocated for the histogram.
     77 void VP8LFreeHistogram(VP8LHistogram* const histo);
     78 
     79 // Free the memory allocated for the histogram set.
     80 void VP8LFreeHistogramSet(VP8LHistogramSet* const histo);
     81 
     82 // Allocate an array of pointer to histograms, allocated and initialized
     83 // using 'cache_bits'. Return NULL in case of memory error.
     84 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits);
     85 
     86 // Allocate and initialize histogram object with specified 'cache_bits'.
     87 // Returns NULL in case of memory error.
     88 // Special case of VP8LAllocateHistogramSet, with size equals 1.
     89 VP8LHistogram* VP8LAllocateHistogram(int cache_bits);
     90 
     91 // Accumulate a token 'v' into a histogram.
     92 void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo,
     93                                      const PixOrCopy* const v);
     94 
     95 static WEBP_INLINE int VP8LHistogramNumCodes(int palette_code_bits) {
     96   return NUM_LITERAL_CODES + NUM_LENGTH_CODES +
     97       ((palette_code_bits > 0) ? (1 << palette_code_bits) : 0);
     98 }
     99 
    100 // Builds the histogram image.
    101 int VP8LGetHistoImageSymbols(int xsize, int ysize,
    102                              const VP8LBackwardRefs* const refs,
    103                              int quality, int low_effort,
    104                              int histogram_bits, int cache_bits,
    105                              VP8LHistogramSet* const image_in,
    106                              VP8LHistogramSet* const tmp_histos,
    107                              uint16_t* const histogram_symbols);
    108 
    109 // Returns the entropy for the symbols in the input array.
    110 // Also sets trivial_symbol to the code value, if the array has only one code
    111 // value. Otherwise, set it to VP8L_NON_TRIVIAL_SYM.
    112 double VP8LBitsEntropy(const uint32_t* const array, int n,
    113                        uint32_t* const trivial_symbol);
    114 
    115 // Estimate how many bits the combined entropy of literals and distance
    116 // approximately maps to.
    117 double VP8LHistogramEstimateBits(const VP8LHistogram* const p);
    118 
    119 #ifdef __cplusplus
    120 }
    121 #endif
    122 
    123 #endif  // WEBP_ENC_HISTOGRAM_H_
    124