vp8l.c revision 5821806d5e7f356e8fa4b058a389a808ea183019
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2012 Google Inc. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This code is licensed under the same terms as WebM: 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Software License Agreement: http://www.webmproject.org/license/software/ 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// main entry for the lossless encoder. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Vikas Arora (vikaas.arora@gmail.com) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <assert.h> 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h> 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h> 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "./backward_references.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "./vp8enci.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "./vp8li.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../dsp/lossless.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../utils/bit_writer.h" 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../utils/huffman_encode.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../utils/utils.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../webp/format_constants.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(__cplusplus) || defined(c_plusplus) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)extern "C" { 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define PALETTE_KEY_RIGHT_SHIFT 22 // Key for 1K buffer. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MAX_HUFF_IMAGE_SIZE (16 * 1024 * 1024) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Palette 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int CompareColors(const void* p1, const void* p2) { 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t a = *(const uint32_t*)p1; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t b = *(const uint32_t*)p2; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (a < b) ? -1 : (a > b) ? 1 : 0; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If number of colors in the image is less than or equal to MAX_PALETTE_SIZE, 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// creates a palette and returns true, else returns false. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int AnalyzeAndCreatePalette(const WebPPicture* const pic, 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t palette[MAX_PALETTE_SIZE], 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int* const palette_size) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i, x, y, key; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_colors = 0; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t in_use[MAX_PALETTE_SIZE * 4] = { 0 }; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t colors[MAX_PALETTE_SIZE * 4]; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint32_t kHashMul = 0x1e35a7bd; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* argb = pic->argb; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int width = pic->width; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int height = pic->height; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0] 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (y = 0; y < height; ++y) { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (x = 0; x < width; ++x) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (argb[x] == last_pix) { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_pix = argb[x]; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key = (kHashMul * last_pix) >> PALETTE_KEY_RIGHT_SHIFT; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (1) { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!in_use[key]) { 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) colors[key] = last_pix; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) in_use[key] = 1; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++num_colors; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (num_colors > MAX_PALETTE_SIZE) { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (colors[key] == last_pix) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The color is already there. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Some other color sits there. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Do linear conflict resolution. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++key; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key &= (MAX_PALETTE_SIZE * 4 - 1); // key mask for 1K buffer. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) argb += pic->argb_stride; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(skal): could we reuse in_use[] to speed up ApplyPalette()? 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_colors = 0; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < (int)(sizeof(in_use) / sizeof(in_use[0])); ++i) { 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (in_use[i]) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) palette[num_colors] = colors[i]; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++num_colors; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) qsort(palette, num_colors, sizeof(*palette), CompareColors); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *palette_size = num_colors; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int AnalyzeEntropy(const WebPPicture* const pic, 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double* const nonpredicted_bits, 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double* const predicted_bits) { 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int x, y; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* argb = pic->argb; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* last_line = NULL; 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t last_pix = argb[0]; // so we're sure that pix_diff == 0 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogram* nonpredicted = NULL; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogram* predicted = 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (VP8LHistogram*)malloc(2 * sizeof(*predicted)); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (predicted == NULL) return 0; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nonpredicted = predicted + 1; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramInit(predicted, 0); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramInit(nonpredicted, 0); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (y = 0; y < pic->height; ++y) { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (x = 0; x < pic->width; ++x) { 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t pix = argb[x]; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t pix_diff = VP8LSubPixels(pix, last_pix); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (pix_diff == 0) continue; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last_line != NULL && pix == last_line[x]) { 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_pix = pix; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PixOrCopy pix_token = PixOrCopyCreateLiteral(pix); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PixOrCopy pix_diff_token = PixOrCopyCreateLiteral(pix_diff); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramAddSinglePixOrCopy(nonpredicted, &pix_token); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramAddSinglePixOrCopy(predicted, &pix_diff_token); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_line = argb; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) argb += pic->argb_stride; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *nonpredicted_bits = VP8LHistogramEstimateBitsBulk(nonpredicted); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *predicted_bits = VP8LHistogramEstimateBitsBulk(predicted); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(predicted); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int VP8LEncAnalyze(VP8LEncoder* const enc, WebPImageHint image_hint) { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const pic = enc->pic_; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(pic != NULL && pic->argb != NULL); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->use_palette_ = (image_hint == WEBP_HINT_GRAPH) ? 0 : 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AnalyzeAndCreatePalette(pic, enc->palette_, &enc->palette_size_); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!enc->use_palette_) { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (image_hint == WEBP_HINT_DEFAULT) { 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double non_pred_entropy, pred_entropy; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!AnalyzeEntropy(pic, &non_pred_entropy, &pred_entropy)) { 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (pred_entropy < 0.95 * non_pred_entropy) { 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->use_predict_ = 1; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->use_cross_color_ = 1; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (image_hint == WEBP_HINT_PHOTO) { 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->use_predict_ = 1; 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->use_cross_color_ = 1; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int GetHuffBitLengthsAndCodes( 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const VP8LHistogramSet* const histogram_image, 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* const huffman_codes) { 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i, k; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ok = 1; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t total_length_size = 0; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t* mem_buf = NULL; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int histogram_image_size = histogram_image->size; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterate over all histograms and get the aggregate number of codes used. 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < histogram_image_size; ++i) { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const VP8LHistogram* const histo = histogram_image->histograms[i]; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (k = 0; k < 5; ++k) { 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int num_symbols = (k == 0) ? VP8LHistogramNumCodes(histo) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : (k == 4) ? NUM_DISTANCE_CODES 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : 256; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codes[k].num_symbols = num_symbols; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) total_length_size += num_symbols; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate and Set Huffman codes. 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint16_t* codes; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t* lengths; 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size, 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(*lengths) + sizeof(*codes)); 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (mem_buf == NULL) { 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = 0; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto End; 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codes = (uint16_t*)mem_buf; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lengths = (uint8_t*)&codes[total_length_size]; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < 5 * histogram_image_size; ++i) { 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int bit_length = huffman_codes[i].num_symbols; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_codes[i].codes = codes; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_codes[i].code_lengths = lengths; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codes += bit_length; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lengths += bit_length; 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create Huffman trees. 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < histogram_image_size; ++i) { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogram* const histo = histogram_image->histograms[i]; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = ok && VP8LCreateHuffmanTree(histo->literal_, 15, codes + 0); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = ok && VP8LCreateHuffmanTree(histo->red_, 15, codes + 1); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = ok && VP8LCreateHuffmanTree(histo->blue_, 15, codes + 2); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = ok && VP8LCreateHuffmanTree(histo->alpha_, 15, codes + 3); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = ok && VP8LCreateHuffmanTree(histo->distance_, 15, codes + 4); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) End: 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ok) free(mem_buf); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ok; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void StoreHuffmanTreeOfHuffmanTreeToBitMask( 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // RFC 1951 will calm you down if you are worried about this funny sequence. 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This sequence is tuned from that, but more weighted for lower symbol count, 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and more spiking histograms. 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = { 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Throw away trailing zeros: 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int codes_to_store = CODE_LENGTH_CODES; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; codes_to_store > 4; --codes_to_store) { 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 4, codes_to_store - 4); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < codes_to_store; ++i) { 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 3, code_length_bitdepth[kStorageOrder[i]]); 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void ClearHuffmanTreeIfOnlyOneSymbol( 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* const huffman_code) { 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int k; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count = 0; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (k = 0; k < huffman_code->num_symbols; ++k) { 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (huffman_code->code_lengths[k] != 0) { 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++count; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (count > 1) return; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (k = 0; k < huffman_code->num_symbols; ++k) { 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_code->code_lengths[k] = 0; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_code->codes[k] = 0; 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void StoreHuffmanTreeToBitMask( 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw, 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeToken* const tokens, const int num_tokens, 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeCode* const huffman_code) { 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < num_tokens; ++i) { 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int ix = tokens[i].code; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int extra_bits = tokens[i].extra_bits; 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, huffman_code->code_lengths[ix], huffman_code->codes[ix]); 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (ix) { 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 16: 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 2, extra_bits); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 17: 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 3, extra_bits); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 18: 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 7, extra_bits); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int StoreFullHuffmanCode(VP8LBitWriter* const bw, 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeCode* const tree) { 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ok = 0; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 }; 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 }; 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int max_tokens = tree->num_symbols; 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_tokens; 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode huffman_code; 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeToken* const tokens = 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (HuffmanTreeToken*)WebPSafeMalloc((uint64_t)max_tokens, sizeof(*tokens)); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (tokens == NULL) return 0; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_code.num_symbols = CODE_LENGTH_CODES; 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_code.code_lengths = code_length_bitdepth; 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_code.codes = code_length_bitdepth_symbols; 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, 0); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens); 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int histogram[CODE_LENGTH_CODES] = { 0 }; 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < num_tokens; ++i) { 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++histogram[tokens[i].code]; 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LCreateHuffmanTree(histogram, 7, &huffman_code)) { 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto End; 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int trailing_zero_bits = 0; 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int trimmed_length = num_tokens; 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int write_trimmed_length; 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int length; 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i = num_tokens; 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (i-- > 0) { 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int ix = tokens[i].code; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ix == 0 || ix == 17 || ix == 18) { 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --trimmed_length; // discount trailing zeros 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trailing_zero_bits += code_length_bitdepth[ix]; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ix == 17) { 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trailing_zero_bits += 3; 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (ix == 18) { 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trailing_zero_bits += 7; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12); 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) length = write_trimmed_length ? trimmed_length : num_tokens; 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, write_trimmed_length); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (write_trimmed_length) { 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int nbits = VP8LBitsLog2Ceiling(trimmed_length - 1); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2; 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 3, nbitpairs - 1); 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(trimmed_length >= 2); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, nbitpairs * 2, trimmed_length - 2); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code); 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = 1; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) End: 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(tokens); 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ok; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int StoreHuffmanCode(VP8LBitWriter* const bw, 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeCode* const huffman_code) { 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count = 0; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int symbols[2] = { 0, 0 }; 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int kMaxBits = 8; 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int kMaxSymbol = 1 << kMaxBits; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check whether it's a small tree. 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (huffman_code->code_lengths[i] != 0) { 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (count < 2) symbols[count] = i; 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++count; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (count == 0) { // emit minimal tree for empty cases 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 4, 0x01); 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) { 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, count - 1); 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (symbols[0] <= 1) { 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, 0); // Code bit for small (1 bit) symbol value. 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, symbols[0]); 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, 1); 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 8, symbols[0]); 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (count == 2) { 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 8, symbols[1]); 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return StoreFullHuffmanCode(bw, huffman_code); 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void WriteHuffmanCode(VP8LBitWriter* const bw, 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeCode* const code, int index) { 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int depth = code->code_lengths[index]; 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int symbol = code->codes[index]; 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, depth, symbol); 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void StoreImageToBitMask( 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw, int width, int histo_bits, 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const VP8LBackwardRefs* const refs, 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint16_t* histogram_symbols, 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeCode* const huffman_codes) { 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // x and y trace the position in the image. 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int x = 0; 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int y = 0; 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < refs->size; ++i) { 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PixOrCopy* const v = &refs->refs[i]; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int histogram_ix = histogram_symbols[histo_bits ? 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (y >> histo_bits) * histo_xsize + 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (x >> histo_bits) : 0]; 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const HuffmanTreeCode* const codes = huffman_codes + 5 * histogram_ix; 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PixOrCopyIsCacheIdx(v)) { 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int code = PixOrCopyCacheIdx(v); 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int literal_ix = 256 + NUM_LENGTH_CODES + code; 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WriteHuffmanCode(bw, codes, literal_ix); 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (PixOrCopyIsLiteral(v)) { 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int order[] = { 1, 2, 0, 3 }; 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int k; 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (k = 0; k < 4; ++k) { 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int code = PixOrCopyLiteral(v, order[k]); 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WriteHuffmanCode(bw, codes + k, code); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int bits, n_bits; 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int code, distance; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrefixEncode(v->len, &code, &n_bits, &bits); 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WriteHuffmanCode(bw, codes, 256 + code); 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, n_bits, bits); 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) distance = PixOrCopyDistance(v); 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrefixEncode(distance, &code, &n_bits, &bits); 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WriteHuffmanCode(bw, codes + 4, code); 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, n_bits, bits); 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x += PixOrCopyLength(v); 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (x >= width) { 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x -= width; 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++y; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int EncodeImageNoHuffman(VP8LBitWriter* const bw, 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* const argb, 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, int height, int quality) { 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ok = 0; 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBackwardRefs refs; 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } }; 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramSet* const histogram_image = VP8LAllocateHistogramSet(1, 0); 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (histogram_image == NULL) return 0; 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Calculate backward references from ARGB image. 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LGetBackwardReferences(width, height, argb, quality, 0, 1, &refs)) { 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Build histogram image and symbols from backward references. 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramStoreRefs(&refs, histogram_image->histograms[0]); 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create Huffman bit lengths and codes for each histogram image. 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(histogram_image->size == 1); 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No color cache, no Huffman image. 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, 0); 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Store Huffman codes. 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < 5; ++i) { 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* const codes = &huffman_codes[i]; 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!StoreHuffmanCode(bw, codes)) { 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ClearHuffmanTreeIfOnlyOneSymbol(codes); 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Store actual literals. 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreImageToBitMask(bw, width, 0, &refs, histogram_symbols, huffman_codes); 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = 1; 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(histogram_image); 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LClearBackwardRefs(&refs); 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(huffman_codes[0].codes); 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ok; 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int EncodeImageInternal(VP8LBitWriter* const bw, 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* const argb, 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, int height, int quality, 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int cache_bits, int histogram_bits) { 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ok = 0; 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int use_2d_locality = 1; 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int use_color_cache = (cache_bits > 0); 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t histogram_image_xysize = 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LSubSampleSize(width, histogram_bits) * 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LSubSampleSize(height, histogram_bits); 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramSet* histogram_image = 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LAllocateHistogramSet(histogram_image_xysize, 0); 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int histogram_image_size = 0; 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t bit_array_size = 0; 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* huffman_codes = NULL; 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBackwardRefs refs; 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint16_t* const histogram_symbols = 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (uint16_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize, 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(*histogram_symbols)); 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(histogram_bits >= MIN_HUFFMAN_BITS); 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(histogram_bits <= MAX_HUFFMAN_BITS); 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (histogram_image == NULL || histogram_symbols == NULL) goto Error; 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Calculate backward references from ARGB image. 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LGetBackwardReferences(width, height, argb, quality, cache_bits, 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) use_2d_locality, &refs)) { 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Build histogram image and symbols from backward references. 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LGetHistoImageSymbols(width, height, &refs, 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) quality, histogram_bits, cache_bits, 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_image, 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_symbols)) { 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create Huffman bit lengths and codes for each histogram image. 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_image_size = histogram_image->size; 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bit_array_size = 5 * histogram_image_size; 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size, 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(*huffman_codes)); 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (huffman_codes == NULL || 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Color Cache parameters. 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, use_color_cache); 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (use_color_cache) { 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 4, cache_bits); 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Huffman image + meta huffman. 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int write_histogram_image = (histogram_image_size > 1); 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, write_histogram_image); 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (write_histogram_image) { 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t* const histogram_argb = 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (uint32_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize, 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(*histogram_argb)); 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_index = 0; 5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t i; 5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (histogram_argb == NULL) goto Error; 5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < histogram_image_xysize; ++i) { 5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int index = histogram_symbols[i] & 0xffff; 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_argb[i] = 0xff000000 | (index << 8); 5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index >= max_index) { 5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_index = index + 1; 5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_image_size = max_index; 5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 3, histogram_bits - 2); 5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = EncodeImageNoHuffman(bw, histogram_argb, 5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LSubSampleSize(width, histogram_bits), 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LSubSampleSize(height, histogram_bits), 5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) quality); 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(histogram_argb); 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ok) goto Error; 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Store Huffman codes. 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < 5 * histogram_image_size; ++i) { 5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeCode* const codes = &huffman_codes[i]; 5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!StoreHuffmanCode(bw, codes)) goto Error; 5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ClearHuffmanTreeIfOnlyOneSymbol(codes); 5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Free combined histograms. 5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(histogram_image); 5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_image = NULL; 5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Store actual literals. 5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreImageToBitMask(bw, width, histogram_bits, &refs, 5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) histogram_symbols, huffman_codes); 5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok = 1; 5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ok) free(histogram_image); 6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LClearBackwardRefs(&refs); 6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (huffman_codes != NULL) { 6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(huffman_codes->codes); 6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(huffman_codes); 6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(histogram_symbols); 6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ok; 6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Transforms 6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Check if it would be a good idea to subtract green from red and blue. We 6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// only impact entropy in red/blue components, don't bother to look at others. 6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int EvalAndApplySubtractGreen(VP8LEncoder* const enc, 6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, int height, 6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw) { 6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!enc->use_palette_) { 6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* const argb = enc->argb_; 6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double bit_cost_before, bit_cost_after; 6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogram* const histo = (VP8LHistogram*)malloc(sizeof(*histo)); 6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (histo == NULL) return 0; 6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramInit(histo, 1); 6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < width * height; ++i) { 6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t c = argb[i]; 6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++histo->red_[(c >> 16) & 0xff]; 6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++histo->blue_[(c >> 0) & 0xff]; 6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bit_cost_before = VP8LHistogramEstimateBits(histo); 6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LHistogramInit(histo, 1); 6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < width * height; ++i) { 6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t c = argb[i]; 6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int green = (c >> 8) & 0xff; 6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++histo->red_[((c >> 16) - green) & 0xff]; 6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++histo->blue_[((c >> 0) - green) & 0xff]; 6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bit_cost_after = VP8LHistogramEstimateBits(histo); 6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(histo); 6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check if subtracting green yields low entropy. 6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->use_subtract_green_ = (bit_cost_after < bit_cost_before); 6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_subtract_green_) { 6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 2, SUBTRACT_GREEN); 6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); 6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int ApplyPredictFilter(const VP8LEncoder* const enc, 6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, int height, int quality, 6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw) { 6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int pred_bits = enc->transform_bits_; 6585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int transform_width = VP8LSubSampleSize(width, pred_bits); 6595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int transform_height = VP8LSubSampleSize(height, pred_bits); 6605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LResidualImage(width, height, pred_bits, enc->argb_, enc->argb_scratch_, 6625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->transform_data_); 6635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 6645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 2, PREDICTOR_TRANSFORM); 6655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(pred_bits >= 2); 6665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 3, pred_bits - 2); 6675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!EncodeImageNoHuffman(bw, enc->transform_data_, 6685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) transform_width, transform_height, quality)) { 6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 6725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int ApplyCrossColorFilter(const VP8LEncoder* const enc, 6755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, int height, int quality, 6765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw) { 6775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int ccolor_transform_bits = enc->transform_bits_; 6785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int transform_width = VP8LSubSampleSize(width, ccolor_transform_bits); 6795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int transform_height = VP8LSubSampleSize(height, ccolor_transform_bits); 6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int step = (quality == 0) ? 32 : 8; 6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LColorSpaceTransform(width, height, ccolor_transform_bits, step, 6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->argb_, enc->transform_data_); 6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 2, CROSS_COLOR_TRANSFORM); 6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(ccolor_transform_bits >= 2); 6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 3, ccolor_transform_bits - 2); 6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!EncodeImageNoHuffman(bw, enc->transform_data_, 6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) transform_width, transform_height, quality)) { 6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 6935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 6965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void PutLE32(uint8_t* const data, uint32_t val) { 6985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data[0] = (val >> 0) & 0xff; 6995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data[1] = (val >> 8) & 0xff; 7005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data[2] = (val >> 16) & 0xff; 7015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data[3] = (val >> 24) & 0xff; 7025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static WebPEncodingError WriteRiffHeader(const WebPPicture* const pic, 7055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t riff_size, size_t vp8l_size) { 7065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = { 7075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P', 7085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE, 7095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 7105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PutLE32(riff + TAG_SIZE, (uint32_t)riff_size); 7115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size); 7125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!pic->writer(riff, sizeof(riff), pic)) { 7135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return VP8_ENC_ERROR_BAD_WRITE; 7145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return VP8_ENC_OK; 7165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int WriteImageSize(const WebPPicture* const pic, 7195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw) { 7205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int width = pic->width - 1; 7215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int height = pic->height - 1; 7225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION); 7235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, width); 7255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, height); 7265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !bw->error_; 7275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) { 7305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, has_alpha); 7315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, VP8L_VERSION_BITS, VP8L_VERSION); 7325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !bw->error_; 7335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static WebPEncodingError WriteImage(const WebPPicture* const pic, 7365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw, 7375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t* const coded_size) { 7385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingError err = VP8_ENC_OK; 7395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8_t* const webpll_data = VP8LBitWriterFinish(bw); 7405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t webpll_size = VP8LBitWriterNumBytes(bw); 7415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size; 7425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t pad = vp8l_size & 1; 7435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad; 7445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = WriteRiffHeader(pic, riff_size, vp8l_size); 7465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) goto Error; 7475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!pic->writer(webpll_data, webpll_size, pic)) { 7495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_BAD_WRITE; 7505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 7515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (pad) { 7545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8_t pad_byte[1] = { 0 }; 7555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!pic->writer(pad_byte, 1, pic)) { 7565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_BAD_WRITE; 7575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 7585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *coded_size = CHUNK_HEADER_SIZE + riff_size; 7615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return VP8_ENC_OK; 7625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 7645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return err; 7655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 7685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Allocates the memory for argb (W x H) buffer, 2 rows of context for 7705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// prediction and transform data. 7715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc, 7725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, int height) { 7735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingError err = VP8_ENC_OK; 7745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int tile_size = 1 << enc->transform_bits_; 7755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t image_size = width * height; 7765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t argb_scratch_size = tile_size * width + width; 7775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t transform_data_size = 7785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (uint64_t)VP8LSubSampleSize(width, enc->transform_bits_) * 7795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (uint64_t)VP8LSubSampleSize(height, enc->transform_bits_); 7805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t total_size = 7815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) image_size + argb_scratch_size + transform_data_size; 7825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem)); 7835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (mem == NULL) { 7845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 7855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 7865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->argb_ = mem; 7885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem += image_size; 7895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->argb_scratch_ = mem; 7905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem += argb_scratch_size; 7915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->transform_data_ = mem; 7925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->current_width_ = width; 7935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 7955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return err; 7965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Bundles multiple (2, 4 or 8) pixels into a single pixel. 7995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the new xsize. 8005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void BundleColorMap(const WebPPicture* const pic, 8015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int xbits, uint32_t* bundled_argb, int xs) { 8025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int y; 8035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int bit_depth = 1 << (3 - xbits); 8045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t code = 0; 8055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t* argb = pic->argb; 8065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int width = pic->width; 8075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int height = pic->height; 8085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (y = 0; y < height; ++y) { 8105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int x; 8115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (x = 0; x < width; ++x) { 8125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int mask = (1 << xbits) - 1; 8135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int xsub = x & mask; 8145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (xsub == 0) { 8155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) code = 0; 8165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(vikasa): simplify the bundling logic. 8185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) code |= (argb[x] & 0xff00) << (bit_depth * xsub); 8195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bundled_argb[y * xs + (x >> xbits)] = 0xff000000 | code; 8205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) argb += pic->argb_stride; 8225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 8245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note: Expects "enc->palette_" to be set properly. 8265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Also, "enc->palette_" will be modified after this call and should not be used 8275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// later. 8285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static WebPEncodingError ApplyPalette(VP8LBitWriter* const bw, 8295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LEncoder* const enc, int quality) { 8305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingError err = VP8_ENC_OK; 8315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i, x, y; 8325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const pic = enc->pic_; 8335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t* argb = pic->argb; 8345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int width = pic->width; 8355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int height = pic->height; 8365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t* const palette = enc->palette_; 8375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int palette_size = enc->palette_size_; 8385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Replace each input pixel by corresponding palette index. 8405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (y = 0; y < height; ++y) { 8415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (x = 0; x < width; ++x) { 8425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t pix = argb[x]; 8435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < palette_size; ++i) { 8445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (pix == palette[i]) { 8455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) argb[x] = 0xff000000u | (i << 8); 8465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 8475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) argb += pic->argb_stride; 8515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Save palette to bitstream. 8545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 8555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 2, COLOR_INDEXING_TRANSFORM); 8565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(palette_size >= 1); 8575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 8, palette_size - 1); 8585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = palette_size - 1; i >= 1; --i) { 8595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); 8605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!EncodeImageNoHuffman(bw, palette, palette_size, 1, quality)) { 8625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 8635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 8645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (palette_size <= 16) { 8675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Image can be packed (multiple pixels per uint32_t). 8685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int xbits = 1; 8695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (palette_size <= 2) { 8705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xbits = 3; 8715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (palette_size <= 4) { 8725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xbits = 2; 8735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height); 8755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) goto Error; 8765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BundleColorMap(pic, xbits, enc->argb_, enc->current_width_); 8775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 8805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return err; 8815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 8825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 8845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int GetHistoBits(const WebPConfig* const config, 8865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const pic) { 8875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int width = pic->width; 8885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int height = pic->height; 8895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t hist_size = sizeof(VP8LHistogram); 8905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make tile size a function of encoding method (Range: 0 to 6). 8915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int histo_bits = 7 - config->method; 8925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (1) { 8935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t huff_image_size = VP8LSubSampleSize(width, histo_bits) * 8945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LSubSampleSize(height, histo_bits) * 8955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hist_size; 8965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break; 8975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++histo_bits; 8985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : 9005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; 9015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 9025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void InitEncParams(VP8LEncoder* const enc) { 9045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPConfig* const config = enc->config_; 9055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const picture = enc->pic_; 9065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int method = config->method; 9075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const float quality = config->quality; 9085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->transform_bits_ = (method < 4) ? 5 : (method > 4) ? 3 : 4; 9095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->histo_bits_ = GetHistoBits(config, picture); 9105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->cache_bits_ = (quality <= 25.f) ? 0 : 7; 9115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 9125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 9145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// VP8LEncoder 9155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config, 9175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const picture) { 9185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LEncoder* const enc = (VP8LEncoder*)calloc(1, sizeof(*enc)); 9195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc == NULL) { 9205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY); 9215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 9225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->config_ = config; 9245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->pic_ = picture; 9255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return enc; 9265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 9275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void VP8LEncoderDelete(VP8LEncoder* enc) { 9295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(enc->argb_); 9305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free(enc); 9315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 9325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 9345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Main call 9355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, 9375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const picture, 9385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter* const bw) { 9395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingError err = VP8_ENC_OK; 9405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int quality = (int)config->quality; 9415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int width = picture->width; 9425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int height = picture->height; 9435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LEncoder* const enc = VP8LEncoderNew(config, picture); 9445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t byte_position = VP8LBitWriterNumBytes(bw); 9455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc == NULL) { 9475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 9485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 9495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InitEncParams(enc); 9525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 9545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Analyze image (entropy, num_palettes etc) 9555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LEncAnalyze(enc, config->image_hint)) { 9575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 9585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 9595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_palette_) { 9625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = ApplyPalette(bw, enc, quality); 9635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) goto Error; 9645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->cache_bits_ = 0; 9655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In case image is not packed. 9685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->argb_ == NULL) { 9695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int y; 9705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = AllocateTransformBuffer(enc, width, height); 9715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) goto Error; 9725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (y = 0; y < height; ++y) { 9735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(enc->argb_ + y * width, 9745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) picture->argb + y * picture->argb_stride, 9755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) width * sizeof(*enc->argb_)); 9765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enc->current_width_ = width; 9785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 9815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Apply transforms and write transform data. 9825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!EvalAndApplySubtractGreen(enc, enc->current_width_, height, bw)) { 9845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 9855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 9865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_predict_) { 9895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ApplyPredictFilter(enc, enc->current_width_, height, quality, bw)) { 9905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 9915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 9925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_cross_color_) { 9965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ApplyCrossColorFilter(enc, enc->current_width_, height, quality, bw)) { 9975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 9985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 9995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LWriteBits(bw, 1, !TRANSFORM_PRESENT); // No more transforms. 10035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 10055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Estimate the color cache size. 10065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->cache_bits_ > 0) { 10085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LCalculateEstimateForCacheSize(enc->argb_, enc->current_width_, 10095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) height, &enc->cache_bits_)) { 10105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 10115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 10125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 10165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Encode and write the transformed image. 10175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!EncodeImageInternal(bw, enc->argb_, enc->current_width_, height, 10195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) quality, enc->cache_bits_, enc->histo_bits_)) { 10205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 10215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 10225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (picture->stats != NULL) { 10255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPAuxStats* const stats = picture->stats; 10265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->lossless_features = 0; 10275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_predict_) stats->lossless_features |= 1; 10285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_cross_color_) stats->lossless_features |= 2; 10295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_subtract_green_) stats->lossless_features |= 4; 10305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (enc->use_palette_) stats->lossless_features |= 8; 10315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->histogram_bits = enc->histo_bits_; 10325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->transform_bits = enc->transform_bits_; 10335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->cache_bits = enc->cache_bits_; 10345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->palette_size = enc->palette_size_; 10355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position); 10365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 10395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LEncoderDelete(enc); 10405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return err; 10415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 10425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int VP8LEncodeImage(const WebPConfig* const config, 10445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WebPPicture* const picture) { 10455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int width, height; 10465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int has_alpha; 10475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t coded_size; 10485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int percent = 0; 10495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingError err = VP8_ENC_OK; 10505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriter bw; 10515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (picture == NULL) return 0; 10535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (config == NULL || picture->argb == NULL) { 10555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_NULL_PARAMETER; 10565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingSetError(picture, err); 10575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 10585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) width = picture->width; 10615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) height = picture->height; 10625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!VP8LBitWriterInit(&bw, (width * height) >> 1)) { 10635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 10645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 10655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WebPReportProgress(picture, 1, &percent)) { 10685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UserAbort: 10695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_USER_ABORT; 10705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 10715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Reset stats (for pure lossless coding) 10735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (picture->stats != NULL) { 10745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPAuxStats* const stats = picture->stats; 10755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(stats, 0, sizeof(*stats)); 10765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->PSNR[0] = 99.f; 10775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->PSNR[1] = 99.f; 10785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->PSNR[2] = 99.f; 10795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->PSNR[3] = 99.f; 10805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats->PSNR[4] = 99.f; 10815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Write image size. 10845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WriteImageSize(picture, &bw)) { 10855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 10865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 10875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) has_alpha = WebPPictureHasTransparency(picture); 10905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Write the non-trivial Alpha flag and lossless version. 10915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WriteRealAlphaAndVersion(&bw, has_alpha)) { 10925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 10935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto Error; 10945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort; 10975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Encode main image stream. 10995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = VP8LEncodeStream(config, picture, &bw); 11005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) goto Error; 11015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(skal): have a fine-grained progress report in VP8LEncodeStream(). 11035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort; 11045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Finish the RIFF chunk. 11065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err = WriteImage(picture, &bw, &coded_size); 11075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) goto Error; 11085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort; 11105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Save size. 11125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (picture->stats != NULL) { 11135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) picture->stats->coded_size += (int)coded_size; 11145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) picture->stats->lossless_size = (int)coded_size; 11155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 11165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (picture->extra_info != NULL) { 11185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int mb_w = (width + 15) >> 4; 11195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int mb_h = (height + 15) >> 4; 11205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info)); 11215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 11225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Error: 11245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 11255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VP8LBitWriterDestroy(&bw); 11265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err != VP8_ENC_OK) { 11275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WebPEncodingSetError(picture, err); 11285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 11295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 11305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 11315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 11325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//------------------------------------------------------------------------------ 11345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(__cplusplus) || defined(c_plusplus) 11365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // extern "C" 11375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1138