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