Home | History | Annotate | Download | only in enc 
      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 (at) 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)
     26 extern "C" {
     27 #endif
     28 
     29 // A simple container for histograms of data.
     30 typedef 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()'.
     45 typedef 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.
     56 void 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.
     61 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits);
     62 
     63 // Collect all the references into a histogram (without reset)
     64 void 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.
     69 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits);
     70 
     71 // Accumulate a token 'v' into a histogram.
     72 void 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.
     77 double 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.
     81 double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p);
     82 
     83 static WEBP_INLINE void VP8LHistogramAdd(VP8LHistogram* const p,
     84                                          const VP8LHistogram* const a) {
     85   int i;
     86   for (i = 0; i < PIX_OR_COPY_CODES_MAX; ++i) {
     87     p->literal_[i] += a->literal_[i];
     88   }
     89   for (i = 0; i < NUM_DISTANCE_CODES; ++i) {
     90     p->distance_[i] += a->distance_[i];
     91   }
     92   for (i = 0; i < 256; ++i) {
     93     p->red_[i] += a->red_[i];
     94     p->blue_[i] += a->blue_[i];
     95     p->alpha_[i] += a->alpha_[i];
     96   }
     97 }
     98 
     99 static WEBP_INLINE int VP8LHistogramNumCodes(const VP8LHistogram* const p) {
    100   return 256 + NUM_LENGTH_CODES +
    101       ((p->palette_code_bits_ > 0) ? (1 << p->palette_code_bits_) : 0);
    102 }
    103 
    104 // Builds the histogram image.
    105 int VP8LGetHistoImageSymbols(int xsize, int ysize,
    106                              const VP8LBackwardRefs* const refs,
    107                              int quality, int histogram_bits, int cache_bits,
    108                              VP8LHistogramSet* const image_in,
    109                              uint16_t* const histogram_symbols);
    110 
    111 #if defined(__cplusplus) || defined(c_plusplus)
    112 }
    113 #endif
    114 
    115 #endif  // WEBP_ENC_HISTOGRAM_H_
    116