15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2012 Google Inc. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 3eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// Use of this source code is governed by a BSD-style license 4eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// that can be found in the COPYING file in the root of the source 5eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// tree. An additional intellectual property rights grant can be found 6eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// in the file PATENTS. All contributing project authors may 7eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// be found in the AUTHORS file in the root of the source tree. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Jyrki Alakuijala (jyrki@google.com) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Models the histograms of literal and distance codes. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef WEBP_ENC_HISTOGRAM_H_ 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define WEBP_ENC_HISTOGRAM_H_ 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <assert.h> 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stddef.h> 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h> 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h> 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h> 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "./backward_references.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../webp/format_constants.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../webp/types.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(__cplusplus) || defined(c_plusplus) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)extern "C" { 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A simple container for histograms of data. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct { 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // literal_ contains green literal, palette-code and 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // copy-length-prefix histogram 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int literal_[PIX_OR_COPY_CODES_MAX]; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int red_[256]; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int blue_[256]; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int alpha_[256]; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Backward reference prefix-code histogram. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int distance_[NUM_DISTANCE_CODES]; 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int palette_code_bits_; 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double bit_cost_; // cached value of VP8LHistogramEstimateBits(this) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} VP8LHistogram; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collection of histograms with fixed capacity, allocated as one 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// big memory chunk. Can be destroyed by simply calling 'free()'. 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct { 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int size; // number of slots currently in use 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_size; // maximum capacity 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogram** histograms; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} VP8LHistogramSet; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Create the histogram. 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The input data is the PixOrCopy data, which models the literals, stop 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// codes and backward references (both distances and lengths). Also: if 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// palette_code_bits is >= 0, initialize the histogram with this value. 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VP8LHistogramCreate(VP8LHistogram* const p, 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const VP8LBackwardRefs* const refs, 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int palette_code_bits); 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Set the palette_code_bits and reset the stats. 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collect all the references into a histogram (without reset) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogram* const histo); 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Allocate an array of pointer to histograms, allocated and initialized 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// using 'cache_bits'. Return NULL in case of memory error. 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Accumulate a token 'v' into a histogram. 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PixOrCopy* const v); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Estimate how many bits the combined entropy of literals and distance 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// approximately maps to. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double VP8LHistogramEstimateBits(const VP8LHistogram* const p); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This function estimates the cost in bits excluding the bits needed to 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// represent the entropy code itself. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static WEBP_INLINE int VP8LHistogramNumCodes(const VP8LHistogram* const p) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 256 + NUM_LENGTH_CODES + 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((p->palette_code_bits_ > 0) ? (1 << p->palette_code_bits_) : 0); 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Builds the histogram image. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int VP8LGetHistoImageSymbols(int xsize, int ysize, 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const VP8LBackwardRefs* const refs, 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int quality, int histogram_bits, int cache_bits, 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramSet* const image_in, 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint16_t* const histogram_symbols); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(__cplusplus) || defined(c_plusplus) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // WEBP_ENC_HISTOGRAM_H_ 102