1a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Copyright 2012 Google Inc. All Rights Reserved. 2a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 30406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Use of this source code is governed by a BSD-style license 40406ce1417f76f2034833414dcecc9f56253640cVikas Arora// that can be found in the COPYING file in the root of the source 50406ce1417f76f2034833414dcecc9f56253640cVikas Arora// tree. An additional intellectual property rights grant can be found 60406ce1417f76f2034833414dcecc9f56253640cVikas Arora// in the file PATENTS. All contributing project authors may 70406ce1417f76f2034833414dcecc9f56253640cVikas Arora// be found in the AUTHORS file in the root of the source tree. 8a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 9a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 10a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// main entry for the lossless encoder. 11a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 12a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Author: Vikas Arora (vikaas.arora@gmail.com) 13a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 14a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 15a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <assert.h> 16a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <stdio.h> 17a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <stdlib.h> 18a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 19a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./backward_references.h" 20a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./vp8enci.h" 21a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./vp8li.h" 22a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../dsp/lossless.h" 23a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../utils/bit_writer.h" 24a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../utils/huffman_encode.h" 25a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../utils/utils.h" 26a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "webp/format_constants.h" 27a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 28a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#define PALETTE_KEY_RIGHT_SHIFT 22 // Key for 1K buffer. 29a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#define MAX_HUFF_IMAGE_SIZE (16 * 1024 * 1024) 30a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#define MAX_COLORS_FOR_GRAPH 64 31a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 32a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 33a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Palette 34a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 35a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int CompareColors(const void* p1, const void* p2) { 36a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t a = *(const uint32_t*)p1; 37a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t b = *(const uint32_t*)p2; 381e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora assert(a != b); 391e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora return (a < b) ? -1 : 1; 40a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 41a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 42a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// If number of colors in the image is less than or equal to MAX_PALETTE_SIZE, 43a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// creates a palette and returns true, else returns false. 44a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int AnalyzeAndCreatePalette(const WebPPicture* const pic, 45a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t palette[MAX_PALETTE_SIZE], 46a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int* const palette_size) { 47a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i, x, y, key; 48a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int num_colors = 0; 49a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t in_use[MAX_PALETTE_SIZE * 4] = { 0 }; 50a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t colors[MAX_PALETTE_SIZE * 4]; 51a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora static const uint32_t kHashMul = 0x1e35a7bd; 52a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t* argb = pic->argb; 53a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int width = pic->width; 54a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int height = pic->height; 55a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0] 56a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 57a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (y = 0; y < height; ++y) { 58a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (x = 0; x < width; ++x) { 59a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (argb[x] == last_pix) { 60a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora continue; 61a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 62a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora last_pix = argb[x]; 63a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora key = (kHashMul * last_pix) >> PALETTE_KEY_RIGHT_SHIFT; 64a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (1) { 65a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!in_use[key]) { 66a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora colors[key] = last_pix; 67a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora in_use[key] = 1; 68a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++num_colors; 69a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (num_colors > MAX_PALETTE_SIZE) { 70a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 71a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 72a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 73a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (colors[key] == last_pix) { 74a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // The color is already there. 75a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 76a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 77a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Some other color sits there. 78a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Do linear conflict resolution. 79a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++key; 80a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora key &= (MAX_PALETTE_SIZE * 4 - 1); // key mask for 1K buffer. 81a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 82a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 83a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 84a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora argb += pic->argb_stride; 85a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 86a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 870406ce1417f76f2034833414dcecc9f56253640cVikas Arora // TODO(skal): could we reuse in_use[] to speed up EncodePalette()? 88a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora num_colors = 0; 89a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < (int)(sizeof(in_use) / sizeof(in_use[0])); ++i) { 90a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (in_use[i]) { 91a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora palette[num_colors] = colors[i]; 92a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++num_colors; 93a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 94a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 95a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 96a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora qsort(palette, num_colors, sizeof(*palette), CompareColors); 97a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora *palette_size = num_colors; 98a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 99a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 100a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 101a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int AnalyzeEntropy(const uint32_t* argb, 102a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int width, int height, int argb_stride, 103a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double* const nonpredicted_bits, 104a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double* const predicted_bits) { 105a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int x, y; 106a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t* last_line = NULL; 107a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t last_pix = argb[0]; // so we're sure that pix_diff == 0 108a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 109af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHistogramSet* const histo_set = VP8LAllocateHistogramSet(2, 0); 110af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (histo_set == NULL) return 0; 111af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 112a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (y = 0; y < height; ++y) { 113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (x = 0; x < width; ++x) { 114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t pix = argb[x]; 115a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t pix_diff = VP8LSubPixels(pix, last_pix); 116a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (pix_diff == 0) continue; 117a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (last_line != NULL && pix == last_line[x]) { 118a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora continue; 119a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora last_pix = pix; 121a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 122a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const PixOrCopy pix_token = PixOrCopyCreateLiteral(pix); 123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const PixOrCopy pix_diff_token = PixOrCopyCreateLiteral(pix_diff); 124af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHistogramAddSinglePixOrCopy(histo_set->histograms[0], &pix_token); 125af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHistogramAddSinglePixOrCopy(histo_set->histograms[1], 126af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora &pix_diff_token); 127a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 128a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora last_line = argb; 130a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora argb += argb_stride; 131a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 132af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora *nonpredicted_bits = VP8LHistogramEstimateBitsBulk(histo_set->histograms[0]); 133af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora *predicted_bits = VP8LHistogramEstimateBitsBulk(histo_set->histograms[1]); 134af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LFreeHistogramSet(histo_set); 135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 137a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 138af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic int AnalyzeAndInit(VP8LEncoder* const enc, WebPImageHint image_hint) { 139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const WebPPicture* const pic = enc->pic_; 140af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int width = pic->width; 141af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int height = pic->height; 142af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int pix_cnt = width * height; 143af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // we round the block size up, so we're guaranteed to have 144af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // at max MAX_REFS_BLOCK_PER_IMAGE blocks used: 145af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int refs_block_size = (pix_cnt - 1) / MAX_REFS_BLOCK_PER_IMAGE + 1; 146a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(pic != NULL && pic->argb != NULL); 147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 148a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_palette_ = 149a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora AnalyzeAndCreatePalette(pic, enc->palette_, &enc->palette_size_); 150a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 151a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (image_hint == WEBP_HINT_GRAPH) { 152a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_palette_ && enc->palette_size_ < MAX_COLORS_FOR_GRAPH) { 153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_palette_ = 0; 154a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 155a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 156a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!enc->use_palette_) { 158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (image_hint == WEBP_HINT_PHOTO) { 159a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_predict_ = 1; 160a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_cross_color_ = 1; 161a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 162a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double non_pred_entropy, pred_entropy; 163af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride, 164a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora &non_pred_entropy, &pred_entropy)) { 165a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 166a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 167a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (pred_entropy < 0.95 * non_pred_entropy) { 168a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_predict_ = 1; 169a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_cross_color_ = 1; 170a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 171a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 172a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 173af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!VP8LHashChainInit(&enc->hash_chain_, pix_cnt)) return 0; 174af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 175af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // palette-friendly input typically uses less literals 176af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // -> reduce block size a bit 177af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (enc->use_palette_) refs_block_size /= 2; 178af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefsInit(&enc->refs_[0], refs_block_size); 179af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefsInit(&enc->refs_[1], refs_block_size); 180a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 181a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 182a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 183a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 184af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// Returns false in case of memory error. 185a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int GetHuffBitLengthsAndCodes( 186a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const VP8LHistogramSet* const histogram_image, 187a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const huffman_codes) { 188a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i, k; 189af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int ok = 0; 190a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint64_t total_length_size = 0; 191a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* mem_buf = NULL; 192a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int histogram_image_size = histogram_image->size; 193af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int max_num_symbols = 0; 194af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora uint8_t* buf_rle = NULL; 195af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTree* huff_tree = NULL; 196a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 197a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Iterate over all histograms and get the aggregate number of codes used. 198a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < histogram_image_size; ++i) { 199a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const VP8LHistogram* const histo = histogram_image->histograms[i]; 200a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 201a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < 5; ++k) { 202af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int num_symbols = 203af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (k == 0) ? VP8LHistogramNumCodes(histo->palette_code_bits_) : 204af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (k == 4) ? NUM_DISTANCE_CODES : 256; 205a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora codes[k].num_symbols = num_symbols; 206a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora total_length_size += num_symbols; 207a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 208a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 209a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 210a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Allocate and Set Huffman codes. 211a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 212a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint16_t* codes; 213a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* lengths; 214a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size, 215a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sizeof(*lengths) + sizeof(*codes)); 216af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (mem_buf == NULL) goto End; 217af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 218a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora codes = (uint16_t*)mem_buf; 219a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora lengths = (uint8_t*)&codes[total_length_size]; 220a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < 5 * histogram_image_size; ++i) { 221a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int bit_length = huffman_codes[i].num_symbols; 222a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_codes[i].codes = codes; 223a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_codes[i].code_lengths = lengths; 224a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora codes += bit_length; 225a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora lengths += bit_length; 226af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (max_num_symbols < bit_length) { 227af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora max_num_symbols = bit_length; 228af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 229a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 230a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 231a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 232af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora buf_rle = (uint8_t*)WebPSafeMalloc(1ULL, max_num_symbols); 233af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * max_num_symbols, 234af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora sizeof(*huff_tree)); 235af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (buf_rle == NULL || huff_tree == NULL) goto End; 236af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 237a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Create Huffman trees. 238af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora for (i = 0; i < histogram_image_size; ++i) { 239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogram* const histo = histogram_image->histograms[i]; 241af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LCreateHuffmanTree(histo->literal_, 15, buf_rle, huff_tree, codes + 0); 242af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LCreateHuffmanTree(histo->red_, 15, buf_rle, huff_tree, codes + 1); 243af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LCreateHuffmanTree(histo->blue_, 15, buf_rle, huff_tree, codes + 2); 244af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LCreateHuffmanTree(histo->alpha_, 15, buf_rle, huff_tree, codes + 3); 245af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LCreateHuffmanTree(histo->distance_, 15, buf_rle, huff_tree, codes + 4); 246a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 247af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora ok = 1; 248a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora End: 249af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(huff_tree); 250af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(buf_rle); 2511e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (!ok) { 252af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(mem_buf); 2531e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes)); 2541e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } 255a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return ok; 256a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 257a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 258a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void StoreHuffmanTreeOfHuffmanTreeToBitMask( 259a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) { 260a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // RFC 1951 will calm you down if you are worried about this funny sequence. 261a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // This sequence is tuned from that, but more weighted for lower symbol count, 262a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // and more spiking histograms. 263a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = { 264a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 265a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora }; 266a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 267a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Throw away trailing zeros: 268a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int codes_to_store = CODE_LENGTH_CODES; 269a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (; codes_to_store > 4; --codes_to_store) { 270a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { 271a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 272a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 273a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 274a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 4, codes_to_store - 4); 275a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < codes_to_store; ++i) { 276a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 3, code_length_bitdepth[kStorageOrder[i]]); 277a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 278a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 279a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 280a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void ClearHuffmanTreeIfOnlyOneSymbol( 281a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const huffman_code) { 282a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 283a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int count = 0; 284a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < huffman_code->num_symbols; ++k) { 285a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (huffman_code->code_lengths[k] != 0) { 286a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++count; 287a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (count > 1) return; 288a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 289a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 290a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < huffman_code->num_symbols; ++k) { 291a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_code->code_lengths[k] = 0; 292a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_code->codes[k] = 0; 293a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 294a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 295a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 296a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void StoreHuffmanTreeToBitMask( 297a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter* const bw, 298a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTreeToken* const tokens, const int num_tokens, 299a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTreeCode* const huffman_code) { 300a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 301a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < num_tokens; ++i) { 302a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int ix = tokens[i].code; 303a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int extra_bits = tokens[i].extra_bits; 304a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, huffman_code->code_lengths[ix], huffman_code->codes[ix]); 305a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora switch (ix) { 306a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora case 16: 307a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 2, extra_bits); 308a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 309a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora case 17: 310a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 3, extra_bits); 311a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 312a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora case 18: 313a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 7, extra_bits); 314a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 315a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 316a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 317a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 318a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 319af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// 'huff_tree' and 'tokens' are pre-alloacted buffers. 320af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic void StoreFullHuffmanCode(VP8LBitWriter* const bw, 321af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTree* const huff_tree, 322af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTreeToken* const tokens, 323af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const HuffmanTreeCode* const tree) { 324a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 }; 325a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 }; 326a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int max_tokens = tree->num_symbols; 327a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int num_tokens; 328a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode huffman_code; 329a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_code.num_symbols = CODE_LENGTH_CODES; 330a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_code.code_lengths = code_length_bitdepth; 331a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_code.codes = code_length_bitdepth_symbols; 332a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 333a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, 0); 334a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens); 335a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 336af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora uint32_t histogram[CODE_LENGTH_CODES] = { 0 }; 337af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora uint8_t buf_rle[CODE_LENGTH_CODES] = { 0 }; 338a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 339a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < num_tokens; ++i) { 340a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histogram[tokens[i].code]; 341a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 342a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 343af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LCreateHuffmanTree(histogram, 7, buf_rle, huff_tree, &huffman_code); 344a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 345a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 346a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth); 347a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code); 348a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 349a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int trailing_zero_bits = 0; 350a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int trimmed_length = num_tokens; 351a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int write_trimmed_length; 352a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int length; 353a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i = num_tokens; 354a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (i-- > 0) { 355a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int ix = tokens[i].code; 356a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (ix == 0 || ix == 17 || ix == 18) { 357a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora --trimmed_length; // discount trailing zeros 358a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora trailing_zero_bits += code_length_bitdepth[ix]; 359a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (ix == 17) { 360a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora trailing_zero_bits += 3; 361a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (ix == 18) { 362a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora trailing_zero_bits += 7; 363a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 364a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 365a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora break; 366a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 367a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 368a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12); 369a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora length = write_trimmed_length ? trimmed_length : num_tokens; 370a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, write_trimmed_length); 371a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (write_trimmed_length) { 372a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int nbits = VP8LBitsLog2Ceiling(trimmed_length - 1); 373a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2; 374a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 3, nbitpairs - 1); 375a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(trimmed_length >= 2); 376a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, nbitpairs * 2, trimmed_length - 2); 377a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 378a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code); 379a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 380a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 381a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 382af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// 'huff_tree' and 'tokens' are pre-alloacted buffers. 383af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic void StoreHuffmanCode(VP8LBitWriter* const bw, 384af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTree* const huff_tree, 385af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTreeToken* const tokens, 386af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const HuffmanTreeCode* const huffman_code) { 387a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 388a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int count = 0; 389a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int symbols[2] = { 0, 0 }; 390a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int kMaxBits = 8; 391a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int kMaxSymbol = 1 << kMaxBits; 392a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 393a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Check whether it's a small tree. 394a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) { 395a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (huffman_code->code_lengths[i] != 0) { 396a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (count < 2) symbols[count] = i; 397a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++count; 398a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 399a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 400a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 401a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (count == 0) { // emit minimal tree for empty cases 402a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0 403a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 4, 0x01); 404a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) { 405a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. 406a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, count - 1); 407a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (symbols[0] <= 1) { 408a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, 0); // Code bit for small (1 bit) symbol value. 409a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, symbols[0]); 410a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 411a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, 1); 412a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 8, symbols[0]); 413a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 414a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (count == 2) { 415a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 8, symbols[1]); 416a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 417a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 418af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora StoreFullHuffmanCode(bw, huff_tree, tokens, huffman_code); 419a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 420a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 421a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 422a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void WriteHuffmanCode(VP8LBitWriter* const bw, 4231e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora const HuffmanTreeCode* const code, 4241e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora int code_index) { 4251e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora const int depth = code->code_lengths[code_index]; 4261e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora const int symbol = code->codes[code_index]; 427a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, depth, symbol); 428a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 429a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 430af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic WebPEncodingError StoreImageToBitMask( 431a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter* const bw, int width, int histo_bits, 432af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefs* const refs, 433a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint16_t* histogram_symbols, 434a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTreeCode* const huffman_codes) { 435a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // x and y trace the position in the image. 436a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int x = 0; 437a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int y = 0; 438a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; 439af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LRefsCursor c = VP8LRefsCursorInit(refs); 440af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora while (VP8LRefsCursorOk(&c)) { 441af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const PixOrCopy* const v = c.cur_pos; 442a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int histogram_ix = histogram_symbols[histo_bits ? 443a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (y >> histo_bits) * histo_xsize + 444a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (x >> histo_bits) : 0]; 445a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTreeCode* const codes = huffman_codes + 5 * histogram_ix; 446a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (PixOrCopyIsCacheIdx(v)) { 447a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int code = PixOrCopyCacheIdx(v); 448a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int literal_ix = 256 + NUM_LENGTH_CODES + code; 449a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WriteHuffmanCode(bw, codes, literal_ix); 450a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else if (PixOrCopyIsLiteral(v)) { 451a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora static const int order[] = { 1, 2, 0, 3 }; 452a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int k; 453a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (k = 0; k < 4; ++k) { 454a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int code = PixOrCopyLiteral(v, order[k]); 455a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WriteHuffmanCode(bw, codes + k, code); 456a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 457a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 458a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int bits, n_bits; 459a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int code, distance; 460a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 4618b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora VP8LPrefixEncode(v->len, &code, &n_bits, &bits); 462a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WriteHuffmanCode(bw, codes, 256 + code); 463a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, n_bits, bits); 464a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 465a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora distance = PixOrCopyDistance(v); 4668b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora VP8LPrefixEncode(distance, &code, &n_bits, &bits); 467a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WriteHuffmanCode(bw, codes + 4, code); 468a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, n_bits, bits); 469a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 470a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora x += PixOrCopyLength(v); 471a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (x >= width) { 472a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora x -= width; 473a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++y; 474a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 475af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LRefsCursorNext(&c); 476a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 477af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return bw->error_ ? VP8_ENC_ERROR_OUT_OF_MEMORY : VP8_ENC_OK; 478a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 479a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 480a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31 481af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic WebPEncodingError EncodeImageNoHuffman(VP8LBitWriter* const bw, 482af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const uint32_t* const argb, 483af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHashChain* const hash_chain, 484af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefs refs_array[2], 485af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int width, int height, 486af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int quality) { 487a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 488af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int max_tokens = 0; 489af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPEncodingError err = VP8_ENC_OK; 490af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefs* refs; 491af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTreeToken* tokens = NULL; 492a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } }; 493a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol 494a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramSet* const histogram_image = VP8LAllocateHistogramSet(1, 0); 495af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc( 496af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree)); 497af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (histogram_image == NULL || huff_tree == NULL) { 498af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 499af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora goto Error; 500af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 501a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 502a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Calculate backward references from ARGB image. 503af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora refs = VP8LGetBackwardReferences(width, height, argb, quality, 0, 1, 504af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora hash_chain, refs_array); 505af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (refs == NULL) { 506af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 507a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 508a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 509a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Build histogram image and symbols from backward references. 510af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHistogramStoreRefs(refs, histogram_image->histograms[0]); 511a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 512a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Create Huffman bit lengths and codes for each histogram image. 513a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(histogram_image->size == 1); 514a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 515af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 516a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 517a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 518a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 519a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // No color cache, no Huffman image. 520a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, 0); 521a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 522af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // Find maximum number of symbols for the huffman tree-set. 523a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < 5; ++i) { 524a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const codes = &huffman_codes[i]; 525af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (max_tokens < codes->num_symbols) { 526af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora max_tokens = codes->num_symbols; 527a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 528af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 529af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 530af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens)); 531af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (tokens == NULL) { 532af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 533af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora goto Error; 534af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 535af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 536af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // Store Huffman codes. 537af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora for (i = 0; i < 5; ++i) { 538af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTreeCode* const codes = &huffman_codes[i]; 539af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora StoreHuffmanCode(bw, huff_tree, tokens, codes); 540a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ClearHuffmanTreeIfOnlyOneSymbol(codes); 541a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 542a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 543a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Store actual literals. 544af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = StoreImageToBitMask(bw, width, 0, refs, histogram_symbols, 545af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora huffman_codes); 546a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 547a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 548af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(tokens); 549af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(huff_tree); 550af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LFreeHistogramSet(histogram_image); 551af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(huffman_codes[0].codes); 552af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return err; 553a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 554a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 555af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, 556af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const uint32_t* const argb, 557af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHashChain* const hash_chain, 558af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefs refs_array[2], 559af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int width, int height, int quality, 560af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int cache_bits, 561af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int histogram_bits) { 562af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPEncodingError err = VP8_ENC_OK; 563a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int use_2d_locality = 1; 564a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int use_color_cache = (cache_bits > 0); 565a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t histogram_image_xysize = 566a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LSubSampleSize(width, histogram_bits) * 567a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LSubSampleSize(height, histogram_bits); 568a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramSet* histogram_image = 569af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LAllocateHistogramSet(histogram_image_xysize, cache_bits); 570a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int histogram_image_size = 0; 571a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t bit_array_size = 0; 572af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTree* huff_tree = NULL; 573af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTreeToken* tokens = NULL; 574a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* huffman_codes = NULL; 575a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBackwardRefs refs; 576af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefs* best_refs; 577a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint16_t* const histogram_symbols = 578af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (uint16_t*)WebPSafeMalloc(histogram_image_xysize, 579a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sizeof(*histogram_symbols)); 580a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(histogram_bits >= MIN_HUFFMAN_BITS); 581a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(histogram_bits <= MAX_HUFFMAN_BITS); 5821e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora 583af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefsInit(&refs, refs_array[0].block_size_); 5841e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (histogram_image == NULL || histogram_symbols == NULL) { 585af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LFreeHistogramSet(histogram_image); 586af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(histogram_symbols); 5871e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora return 0; 5881e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } 589a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 590af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // 'best_refs' is the reference to the best backward refs and points to one 591af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // of refs_array[0] or refs_array[1]. 592a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Calculate backward references from ARGB image. 593af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora best_refs = VP8LGetBackwardReferences(width, height, argb, quality, 594af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora cache_bits, use_2d_locality, 595af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora hash_chain, refs_array); 596af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (best_refs == NULL || !VP8LBackwardRefsCopy(best_refs, &refs)) { 597a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 598a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 599a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Build histogram image and symbols from backward references. 600a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!VP8LGetHistoImageSymbols(width, height, &refs, 601a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora quality, histogram_bits, cache_bits, 602a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora histogram_image, 603a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora histogram_symbols)) { 604a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 605a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 606a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Create Huffman bit lengths and codes for each histogram image. 607a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora histogram_image_size = histogram_image->size; 608a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_array_size = 5 * histogram_image_size; 609a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size, 610a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sizeof(*huffman_codes)); 611a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (huffman_codes == NULL || 612a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 613a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 614a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 6150406ce1417f76f2034833414dcecc9f56253640cVikas Arora // Free combined histograms. 616af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LFreeHistogramSet(histogram_image); 6170406ce1417f76f2034833414dcecc9f56253640cVikas Arora histogram_image = NULL; 618a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 619a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Color Cache parameters. 620a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, use_color_cache); 621a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (use_color_cache) { 622a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 4, cache_bits); 623a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 624a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 625a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Huffman image + meta huffman. 626a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 627a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int write_histogram_image = (histogram_image_size > 1); 628a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, write_histogram_image); 629a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (write_histogram_image) { 630a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t* const histogram_argb = 631af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (uint32_t*)WebPSafeMalloc(histogram_image_xysize, 632a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora sizeof(*histogram_argb)); 633a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int max_index = 0; 634a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t i; 635a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (histogram_argb == NULL) goto Error; 636a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < histogram_image_xysize; ++i) { 6371e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora const int symbol_index = histogram_symbols[i] & 0xffff; 6381e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora histogram_argb[i] = 0xff000000 | (symbol_index << 8); 6391e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (symbol_index >= max_index) { 6401e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora max_index = symbol_index + 1; 641a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 642a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 643a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora histogram_image_size = max_index; 644a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 645a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 3, histogram_bits - 2); 646af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = EncodeImageNoHuffman(bw, histogram_argb, hash_chain, refs_array, 647af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LSubSampleSize(width, histogram_bits), 648af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LSubSampleSize(height, histogram_bits), 649af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora quality); 650af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(histogram_argb); 651af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (err != VP8_ENC_OK) goto Error; 652a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 653a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 654a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 655a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Store Huffman codes. 656a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora { 657a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 658af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int max_tokens = 0; 659af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * CODE_LENGTH_CODES, 660af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora sizeof(*huff_tree)); 661af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (huff_tree == NULL) goto Error; 662af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // Find maximum number of symbols for the huffman tree-set. 663af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora for (i = 0; i < 5 * histogram_image_size; ++i) { 664af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTreeCode* const codes = &huffman_codes[i]; 665af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (max_tokens < codes->num_symbols) { 666af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora max_tokens = codes->num_symbols; 667af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 668af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 669af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, 670af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora sizeof(*tokens)); 671af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (tokens == NULL) goto Error; 672a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < 5 * histogram_image_size; ++i) { 673a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeCode* const codes = &huffman_codes[i]; 674af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora StoreHuffmanCode(bw, huff_tree, tokens, codes); 675a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ClearHuffmanTreeIfOnlyOneSymbol(codes); 676a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 677a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 678a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 679a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Store actual literals. 680af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = StoreImageToBitMask(bw, width, histogram_bits, &refs, 681af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora histogram_symbols, huffman_codes); 682a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 683a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 684af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(tokens); 685af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(huff_tree); 686af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LFreeHistogramSet(histogram_image); 687af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefsClear(&refs); 688a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (huffman_codes != NULL) { 689af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(huffman_codes->codes); 690af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(huffman_codes); 691a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 692af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(histogram_symbols); 693af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return err; 694a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 695a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 696a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 697a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Transforms 698a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 699a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Check if it would be a good idea to subtract green from red and blue. We 700a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// only impact entropy in red/blue components, don't bother to look at others. 701af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic WebPEncodingError EvalAndApplySubtractGreen(VP8LEncoder* const enc, 702af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int width, int height, 703af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBitWriter* const bw) { 704a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!enc->use_palette_) { 705a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 706a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t* const argb = enc->argb_; 707a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora double bit_cost_before, bit_cost_after; 708af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // Allocate histogram with cache_bits = 1. 709af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHistogram* const histo = VP8LAllocateHistogram(1); 710af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (histo == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; 711a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < width * height; ++i) { 712a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t c = argb[i]; 713a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->red_[(c >> 16) & 0xff]; 714a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->blue_[(c >> 0) & 0xff]; 715a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 716a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_cost_before = VP8LHistogramEstimateBits(histo); 717a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 718a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LHistogramInit(histo, 1); 719a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < width * height; ++i) { 720a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint32_t c = argb[i]; 721a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int green = (c >> 8) & 0xff; 722a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->red_[((c >> 16) - green) & 0xff]; 723a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo->blue_[((c >> 0) - green) & 0xff]; 724a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 725a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bit_cost_after = VP8LHistogramEstimateBits(histo); 726af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LFreeHistogram(histo); 727a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 728a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Check if subtracting green yields low entropy. 729a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->use_subtract_green_ = (bit_cost_after < bit_cost_before); 730a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_subtract_green_) { 731a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 732a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 2, SUBTRACT_GREEN); 733a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); 734a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 735a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 736af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return VP8_ENC_OK; 737a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 738a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 739af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic WebPEncodingError ApplyPredictFilter(const VP8LEncoder* const enc, 740af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int width, int height, int quality, 741af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBitWriter* const bw) { 742a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int pred_bits = enc->transform_bits_; 743a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int transform_width = VP8LSubSampleSize(width, pred_bits); 744a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int transform_height = VP8LSubSampleSize(height, pred_bits); 745a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 746a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LResidualImage(width, height, pred_bits, enc->argb_, enc->argb_scratch_, 747a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->transform_data_); 748a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 749a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 2, PREDICTOR_TRANSFORM); 750a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(pred_bits >= 2); 751a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 3, pred_bits - 2); 752af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return EncodeImageNoHuffman(bw, enc->transform_data_, 753af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (VP8LHashChain*)&enc->hash_chain_, 754af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (VP8LBackwardRefs*)enc->refs_, // cast const away 755af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora transform_width, transform_height, 756af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora quality); 757a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 758a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 759af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic WebPEncodingError ApplyCrossColorFilter(const VP8LEncoder* const enc, 760af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int width, int height, 761af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int quality, 762af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBitWriter* const bw) { 763a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int ccolor_transform_bits = enc->transform_bits_; 764a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int transform_width = VP8LSubSampleSize(width, ccolor_transform_bits); 765a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int transform_height = VP8LSubSampleSize(height, ccolor_transform_bits); 766a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 767af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LColorSpaceTransform(width, height, ccolor_transform_bits, quality, 768a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->argb_, enc->transform_data_); 769a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 770a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 2, CROSS_COLOR_TRANSFORM); 771a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(ccolor_transform_bits >= 2); 772a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 3, ccolor_transform_bits - 2); 773af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return EncodeImageNoHuffman(bw, enc->transform_data_, 774af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (VP8LHashChain*)&enc->hash_chain_, 775af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (VP8LBackwardRefs*)enc->refs_, // cast const away 776af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora transform_width, transform_height, 777af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora quality); 778a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 779a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 780a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 781a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 782a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic WebPEncodingError WriteRiffHeader(const WebPPicture* const pic, 783a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t riff_size, size_t vp8l_size) { 784a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = { 785a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P', 786a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE, 787a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora }; 788a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora PutLE32(riff + TAG_SIZE, (uint32_t)riff_size); 789a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size); 790a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!pic->writer(riff, sizeof(riff), pic)) { 791a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return VP8_ENC_ERROR_BAD_WRITE; 792a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 793a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return VP8_ENC_OK; 794a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 795a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 796a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int WriteImageSize(const WebPPicture* const pic, 797a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter* const bw) { 798a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int width = pic->width - 1; 799a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int height = pic->height - 1; 800a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION); 801a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 802a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, width); 803a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, height); 804a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return !bw->error_; 805a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 806a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 807a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) { 808a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, has_alpha); 809a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, VP8L_VERSION_BITS, VP8L_VERSION); 810a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return !bw->error_; 811a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 812a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 813a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic WebPEncodingError WriteImage(const WebPPicture* const pic, 814a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter* const bw, 815a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t* const coded_size) { 816a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingError err = VP8_ENC_OK; 817a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint8_t* const webpll_data = VP8LBitWriterFinish(bw); 818a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t webpll_size = VP8LBitWriterNumBytes(bw); 819a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size; 820a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t pad = vp8l_size & 1; 821a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad; 822a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 823a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = WriteRiffHeader(pic, riff_size, vp8l_size); 824a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (err != VP8_ENC_OK) goto Error; 825a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 826a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!pic->writer(webpll_data, webpll_size, pic)) { 827a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_BAD_WRITE; 828a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 829a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 830a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 831a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (pad) { 832a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint8_t pad_byte[1] = { 0 }; 833a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!pic->writer(pad_byte, 1, pic)) { 834a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_BAD_WRITE; 835a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 836a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 837a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 838a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora *coded_size = CHUNK_HEADER_SIZE + riff_size; 839a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return VP8_ENC_OK; 840a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 841a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 842a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return err; 843a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 844a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 845a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 846a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 847a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Allocates the memory for argb (W x H) buffer, 2 rows of context for 848a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// prediction and transform data. 849a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc, 850a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int width, int height) { 851a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingError err = VP8_ENC_OK; 852a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int tile_size = 1 << enc->transform_bits_; 853a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint64_t image_size = width * height; 854a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint64_t argb_scratch_size = tile_size * width + width; 855af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int transform_data_size = 856af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LSubSampleSize(width, enc->transform_bits_) * 857af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LSubSampleSize(height, enc->transform_bits_); 858a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint64_t total_size = 859af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora image_size + argb_scratch_size + (uint64_t)transform_data_size; 860a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem)); 861a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (mem == NULL) { 862a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 863a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 864a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 865a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->argb_ = mem; 866a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora mem += image_size; 867a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->argb_scratch_ = mem; 868a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora mem += argb_scratch_size; 869a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->transform_data_ = mem; 870a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->current_width_ = width; 871a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 872a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 873a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return err; 874a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 875a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 8760406ce1417f76f2034833414dcecc9f56253640cVikas Arorastatic void ApplyPalette(uint32_t* src, uint32_t* dst, 8770406ce1417f76f2034833414dcecc9f56253640cVikas Arora uint32_t src_stride, uint32_t dst_stride, 8780406ce1417f76f2034833414dcecc9f56253640cVikas Arora const uint32_t* palette, int palette_size, 8790406ce1417f76f2034833414dcecc9f56253640cVikas Arora int width, int height, int xbits, uint8_t* row) { 8800406ce1417f76f2034833414dcecc9f56253640cVikas Arora int i, x, y; 8810406ce1417f76f2034833414dcecc9f56253640cVikas Arora int use_LUT = 1; 8820406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (i = 0; i < palette_size; ++i) { 8830406ce1417f76f2034833414dcecc9f56253640cVikas Arora if ((palette[i] & 0xffff00ffu) != 0) { 8840406ce1417f76f2034833414dcecc9f56253640cVikas Arora use_LUT = 0; 8850406ce1417f76f2034833414dcecc9f56253640cVikas Arora break; 8860406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 8870406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 8880406ce1417f76f2034833414dcecc9f56253640cVikas Arora 8890406ce1417f76f2034833414dcecc9f56253640cVikas Arora if (use_LUT) { 8908b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora uint8_t inv_palette[MAX_PALETTE_SIZE] = { 0 }; 8910406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (i = 0; i < palette_size; ++i) { 8920406ce1417f76f2034833414dcecc9f56253640cVikas Arora const int color = (palette[i] >> 8) & 0xff; 8930406ce1417f76f2034833414dcecc9f56253640cVikas Arora inv_palette[color] = i; 8940406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 8950406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (y = 0; y < height; ++y) { 8960406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (x = 0; x < width; ++x) { 8970406ce1417f76f2034833414dcecc9f56253640cVikas Arora const int color = (src[x] >> 8) & 0xff; 8980406ce1417f76f2034833414dcecc9f56253640cVikas Arora row[x] = inv_palette[color]; 899a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 9000406ce1417f76f2034833414dcecc9f56253640cVikas Arora VP8LBundleColorMap(row, width, xbits, dst); 9010406ce1417f76f2034833414dcecc9f56253640cVikas Arora src += src_stride; 9020406ce1417f76f2034833414dcecc9f56253640cVikas Arora dst += dst_stride; 903a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 9041e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } else { 9050406ce1417f76f2034833414dcecc9f56253640cVikas Arora // Use 1 pixel cache for ARGB pixels. 9060406ce1417f76f2034833414dcecc9f56253640cVikas Arora uint32_t last_pix = palette[0]; 9070406ce1417f76f2034833414dcecc9f56253640cVikas Arora int last_idx = 0; 9080406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (y = 0; y < height; ++y) { 9090406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (x = 0; x < width; ++x) { 9100406ce1417f76f2034833414dcecc9f56253640cVikas Arora const uint32_t pix = src[x]; 9110406ce1417f76f2034833414dcecc9f56253640cVikas Arora if (pix != last_pix) { 9120406ce1417f76f2034833414dcecc9f56253640cVikas Arora for (i = 0; i < palette_size; ++i) { 9130406ce1417f76f2034833414dcecc9f56253640cVikas Arora if (pix == palette[i]) { 9140406ce1417f76f2034833414dcecc9f56253640cVikas Arora last_idx = i; 9150406ce1417f76f2034833414dcecc9f56253640cVikas Arora last_pix = pix; 9160406ce1417f76f2034833414dcecc9f56253640cVikas Arora break; 9170406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 9180406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 9190406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 9200406ce1417f76f2034833414dcecc9f56253640cVikas Arora row[x] = last_idx; 9210406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 9220406ce1417f76f2034833414dcecc9f56253640cVikas Arora VP8LBundleColorMap(row, width, xbits, dst); 9230406ce1417f76f2034833414dcecc9f56253640cVikas Arora src += src_stride; 9240406ce1417f76f2034833414dcecc9f56253640cVikas Arora dst += dst_stride; 9250406ce1417f76f2034833414dcecc9f56253640cVikas Arora } 926a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 927a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 928a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 929a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Note: Expects "enc->palette_" to be set properly. 930a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Also, "enc->palette_" will be modified after this call and should not be used 931a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// later. 9320406ce1417f76f2034833414dcecc9f56253640cVikas Arorastatic WebPEncodingError EncodePalette(VP8LBitWriter* const bw, 9330406ce1417f76f2034833414dcecc9f56253640cVikas Arora VP8LEncoder* const enc, int quality) { 934a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingError err = VP8_ENC_OK; 9350406ce1417f76f2034833414dcecc9f56253640cVikas Arora int i; 936a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const WebPPicture* const pic = enc->pic_; 9371e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora uint32_t* src = pic->argb; 9381e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora uint32_t* dst; 939a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int width = pic->width; 940a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int height = pic->height; 941a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint32_t* const palette = enc->palette_; 942a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int palette_size = enc->palette_size_; 9431e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora uint8_t* row = NULL; 9441e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora int xbits; 945a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 946a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Replace each input pixel by corresponding palette index. 9471e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora // This is done line by line. 9481e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (palette_size <= 4) { 9491e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora xbits = (palette_size <= 2) ? 3 : 2; 9501e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } else { 9511e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora xbits = (palette_size <= 16) ? 1 : 0; 9521e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora } 9531e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora 9541e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height); 9551e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (err != VP8_ENC_OK) goto Error; 9561e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora dst = enc->argb_; 9571e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora 958af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora row = (uint8_t*)WebPSafeMalloc(width, sizeof(*row)); 9591e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora if (row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; 9601e7bf8805bd030c19924a5306837ecd72c295751Vikas Arora 9610406ce1417f76f2034833414dcecc9f56253640cVikas Arora ApplyPalette(src, dst, pic->argb_stride, enc->current_width_, 9620406ce1417f76f2034833414dcecc9f56253640cVikas Arora palette, palette_size, width, height, xbits, row); 963a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 964a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Save palette to bitstream. 965a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 966a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 2, COLOR_INDEXING_TRANSFORM); 967a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(palette_size >= 1); 968a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 8, palette_size - 1); 969a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = palette_size - 1; i >= 1; --i) { 970a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); 971a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 972af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = EncodeImageNoHuffman(bw, palette, &enc->hash_chain_, enc->refs_, 973af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora palette_size, 1, quality); 974a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 975a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 976af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(row); 977a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return err; 978a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 979a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 980a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 981a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 9820406ce1417f76f2034833414dcecc9f56253640cVikas Arorastatic int GetHistoBits(int method, int use_palette, int width, int height) { 983af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int hist_size = VP8LGetHistogramSize(MAX_COLOR_CACHE_BITS); 984a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Make tile size a function of encoding method (Range: 0 to 6). 9850406ce1417f76f2034833414dcecc9f56253640cVikas Arora int histo_bits = (use_palette ? 9 : 7) - method; 986a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (1) { 987af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int huff_image_size = VP8LSubSampleSize(width, histo_bits) * 988af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LSubSampleSize(height, histo_bits); 989af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if ((uint64_t)huff_image_size * hist_size <= MAX_HUFF_IMAGE_SIZE) break; 990a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++histo_bits; 991a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 992a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : 993a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; 994a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 995a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 996af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic int GetTransformBits(int method, int histo_bits) { 997af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5; 998af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits; 999af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora} 1000af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 1001af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic int GetCacheBits(float quality) { 1002af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return (quality <= 25.f) ? 0 : 7; 1003af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora} 1004af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 10050406ce1417f76f2034833414dcecc9f56253640cVikas Arorastatic void FinishEncParams(VP8LEncoder* const enc) { 1006a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const WebPConfig* const config = enc->config_; 10070406ce1417f76f2034833414dcecc9f56253640cVikas Arora const WebPPicture* const pic = enc->pic_; 1008a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int method = config->method; 1009a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const float quality = config->quality; 10100406ce1417f76f2034833414dcecc9f56253640cVikas Arora const int use_palette = enc->use_palette_; 10110406ce1417f76f2034833414dcecc9f56253640cVikas Arora enc->histo_bits_ = GetHistoBits(method, use_palette, pic->width, pic->height); 1012af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora enc->transform_bits_ = GetTransformBits(method, enc->histo_bits_); 1013af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora enc->cache_bits_ = GetCacheBits(quality); 1014a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 1015a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1016a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 1017a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// VP8LEncoder 1018a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1019a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config, 1020a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const WebPPicture* const picture) { 1021af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LEncoder* const enc = (VP8LEncoder*)WebPSafeCalloc(1ULL, sizeof(*enc)); 1022a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc == NULL) { 1023a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY); 1024a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return NULL; 1025a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1026a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->config_ = config; 1027a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->pic_ = picture; 10288b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 10298b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora VP8LDspInit(); 10308b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 1031a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return enc; 1032a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 1033a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1034a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void VP8LEncoderDelete(VP8LEncoder* enc) { 1035af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (enc != NULL) { 1036af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHashChainClear(&enc->hash_chain_); 1037af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefsClear(&enc->refs_[0]); 1038af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LBackwardRefsClear(&enc->refs_[1]); 1039af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(enc->argb_); 1040af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(enc); 1041af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 1042a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 1043a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1044a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 1045a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Main call 1046a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1047a2415724fb3466168b2af5b08bd94ba732c0e753Vikas AroraWebPEncodingError VP8LEncodeStream(const WebPConfig* const config, 1048a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const WebPPicture* const picture, 1049a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter* const bw) { 1050a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingError err = VP8_ENC_OK; 1051a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int quality = (int)config->quality; 1052a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int width = picture->width; 1053a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int height = picture->height; 1054a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LEncoder* const enc = VP8LEncoderNew(config, picture); 1055a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t byte_position = VP8LBitWriterNumBytes(bw); 1056a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1057a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc == NULL) { 1058a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1059a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1060a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1061a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1062a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // --------------------------------------------------------------------------- 1063a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Analyze image (entropy, num_palettes etc) 1064a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1065af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!AnalyzeAndInit(enc, config->image_hint)) { 1066a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1067a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1068a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1069a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 10700406ce1417f76f2034833414dcecc9f56253640cVikas Arora FinishEncParams(enc); 10710406ce1417f76f2034833414dcecc9f56253640cVikas Arora 1072a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_palette_) { 10730406ce1417f76f2034833414dcecc9f56253640cVikas Arora err = EncodePalette(bw, enc, quality); 1074a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (err != VP8_ENC_OK) goto Error; 1075a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Color cache is disabled for palette. 1076a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->cache_bits_ = 0; 1077a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1078a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1079a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // In case image is not packed. 1080a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->argb_ == NULL) { 1081a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int y; 1082a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = AllocateTransformBuffer(enc, width, height); 1083a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (err != VP8_ENC_OK) goto Error; 1084a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (y = 0; y < height; ++y) { 1085a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memcpy(enc->argb_ + y * width, 1086a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora picture->argb + y * picture->argb_stride, 1087a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora width * sizeof(*enc->argb_)); 1088a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1089a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora enc->current_width_ = width; 1090a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1091a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1092a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // --------------------------------------------------------------------------- 1093a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Apply transforms and write transform data. 1094a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1095af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = EvalAndApplySubtractGreen(enc, enc->current_width_, height, bw); 1096af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (err != VP8_ENC_OK) goto Error; 1097a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1098a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_predict_) { 1099af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = ApplyPredictFilter(enc, enc->current_width_, height, quality, bw); 1100af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (err != VP8_ENC_OK) goto Error; 1101a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1102a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1103a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_cross_color_) { 1104af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = ApplyCrossColorFilter(enc, enc->current_width_, height, quality, bw); 1105af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (err != VP8_ENC_OK) goto Error; 1106a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1107a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1108a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LWriteBits(bw, 1, !TRANSFORM_PRESENT); // No more transforms. 1109a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1110a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // --------------------------------------------------------------------------- 1111a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Estimate the color cache size. 1112a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->cache_bits_ > 0) { 1114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!VP8LCalculateEstimateForCacheSize(enc->argb_, enc->current_width_, 1115af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora height, quality, &enc->hash_chain_, 1116af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora &enc->refs_[0], &enc->cache_bits_)) { 1117af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1118a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1119a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1121a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1122a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // --------------------------------------------------------------------------- 1123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Encode and write the transformed image. 1124a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1125af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora err = EncodeImageInternal(bw, enc->argb_, &enc->hash_chain_, enc->refs_, 1126af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora enc->current_width_, height, quality, 1127af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora enc->cache_bits_, enc->histo_bits_); 1128af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (err != VP8_ENC_OK) goto Error; 1129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1130a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (picture->stats != NULL) { 1131a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPAuxStats* const stats = picture->stats; 1132a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->lossless_features = 0; 1133a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_predict_) stats->lossless_features |= 1; 1134a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_cross_color_) stats->lossless_features |= 2; 1135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_subtract_green_) stats->lossless_features |= 4; 1136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (enc->use_palette_) stats->lossless_features |= 8; 1137a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->histogram_bits = enc->histo_bits_; 1138a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->transform_bits = enc->transform_bits_; 1139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->cache_bits = enc->cache_bits_; 1140a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->palette_size = enc->palette_size_; 1141a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position); 1142a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1143a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1144a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 1145a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LEncoderDelete(enc); 1146a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return err; 1147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 1148a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1149a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LEncodeImage(const WebPConfig* const config, 1150a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const WebPPicture* const picture) { 1151a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int width, height; 1152a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int has_alpha; 1153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t coded_size; 1154a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int percent = 0; 1155af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int initial_size; 1156a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingError err = VP8_ENC_OK; 1157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriter bw; 1158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1159a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (picture == NULL) return 0; 1160a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1161a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (config == NULL || picture->argb == NULL) { 1162a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_NULL_PARAMETER; 1163a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingSetError(picture, err); 1164a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 1165a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1166a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1167a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora width = picture->width; 1168a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora height = picture->height; 1169af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // Initialize BitWriter with size corresponding to 16 bpp to photo images and 1170af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // 8 bpp for graphical images. 1171af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora initial_size = (config->image_hint == WEBP_HINT_GRAPH) ? 1172af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora width * height : width * height * 2; 1173af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!VP8LBitWriterInit(&bw, initial_size)) { 1174a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1175a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1176a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1177a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1178a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!WebPReportProgress(picture, 1, &percent)) { 1179a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora UserAbort: 1180a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_USER_ABORT; 1181a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1182a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1183a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Reset stats (for pure lossless coding) 1184a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (picture->stats != NULL) { 1185a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPAuxStats* const stats = picture->stats; 1186a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memset(stats, 0, sizeof(*stats)); 1187a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->PSNR[0] = 99.f; 1188a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->PSNR[1] = 99.f; 1189a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->PSNR[2] = 99.f; 1190a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->PSNR[3] = 99.f; 1191a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora stats->PSNR[4] = 99.f; 1192a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1193a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1194a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Write image size. 1195a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!WriteImageSize(picture, &bw)) { 1196a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1197a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1198a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1199a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1200a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora has_alpha = WebPPictureHasTransparency(picture); 1201a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Write the non-trivial Alpha flag and lossless version. 1202a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!WriteRealAlphaAndVersion(&bw, has_alpha)) { 1203a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1204a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto Error; 1205a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1206a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1207a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort; 1208a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1209a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Encode main image stream. 1210a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = VP8LEncodeStream(config, picture, &bw); 1211a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (err != VP8_ENC_OK) goto Error; 1212a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1213a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // TODO(skal): have a fine-grained progress report in VP8LEncodeStream(). 1214a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort; 1215a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1216a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Finish the RIFF chunk. 1217a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora err = WriteImage(picture, &bw, &coded_size); 1218a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (err != VP8_ENC_OK) goto Error; 1219a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1220a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort; 1221a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1222a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Save size. 1223a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (picture->stats != NULL) { 1224a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora picture->stats->coded_size += (int)coded_size; 1225a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora picture->stats->lossless_size = (int)coded_size; 1226a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1227a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1228a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (picture->extra_info != NULL) { 1229a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int mb_w = (width + 15) >> 4; 1230a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int mb_h = (height + 15) >> 4; 1231a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info)); 1232a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1233a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1234a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora Error: 1235a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1236a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8LBitWriterDestroy(&bw); 1237a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (err != VP8_ENC_OK) { 1238a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora WebPEncodingSetError(picture, err); 1239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 1240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 1241a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 1242a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 1243a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1244a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora//------------------------------------------------------------------------------ 1245