15a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Copyright 2012 Google Inc. All Rights Reserved. 25a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// 35a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// This code is licensed under the same terms as WebM: 45a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Software License Agreement: http://www.webmproject.org/license/software/ 55a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 65a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// ----------------------------------------------------------------------------- 75a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// 85a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Author: Jyrki Alakuijala (jyrki@google.com) 95a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// 105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include <assert.h> 125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include <math.h> 135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include <stdio.h> 145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include "./backward_references.h" 165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include "./histogram.h" 175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include "../dsp/lossless.h" 185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include "../utils/color_cache.h" 195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#include "../utils/utils.h" 205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define VALUES_IN_BYTE 256 225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define HASH_BITS 18 245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define HASH_SIZE (1 << HASH_BITS) 255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define HASH_MULTIPLIER (0xc6a4a7935bd1e995ULL) 265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// 1M window (4M bytes) minus 120 special codes for short distances. 285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define WINDOW_SIZE ((1 << 20) - 120) 295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Bounds for the match length. 315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define MIN_LENGTH 2 325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora#define MAX_LENGTH 4096 335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 345a50414796e9a458925c7a13a15055d02406bf43Vikas Aroratypedef struct { 355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Stores the most recently added position with the given hash value. 365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int32_t hash_to_first_index_[HASH_SIZE]; 375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // chain_[pos] stores the previous position with the same hash value 385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // for every pixel in the image. 395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int32_t* chain_; 405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} HashChain; 415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// ----------------------------------------------------------------------------- 435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 445a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic const uint8_t plane_to_code_lut[128] = { 455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 96, 73, 55, 39, 23, 13, 5, 1, 255, 255, 255, 255, 255, 255, 255, 255, 465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 101, 78, 58, 42, 26, 16, 8, 2, 0, 3, 9, 17, 27, 43, 59, 79, 475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 102, 86, 62, 46, 32, 20, 10, 6, 4, 7, 11, 21, 33, 47, 63, 87, 485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 105, 90, 70, 52, 37, 28, 18, 14, 12, 15, 19, 29, 38, 53, 71, 91, 495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 110, 99, 82, 66, 48, 35, 30, 24, 22, 25, 31, 36, 49, 67, 83, 100, 505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 115, 108, 94, 76, 64, 50, 44, 40, 34, 41, 45, 51, 65, 77, 95, 109, 515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 118, 113, 103, 92, 80, 68, 60, 56, 54, 57, 61, 69, 81, 93, 104, 114, 525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 119, 116, 111, 106, 97, 88, 84, 74, 72, 75, 85, 89, 98, 107, 112, 117 535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora}; 545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 555a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int DistanceToPlaneCode(int xsize, int dist) { 565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int yoffset = dist / xsize; 575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int xoffset = dist - yoffset * xsize; 585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (xoffset <= 8 && yoffset < 8) { 595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return plane_to_code_lut[yoffset * 16 + 8 - xoffset] + 1; 605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else if (xoffset > xsize - 8 && yoffset < 7) { 615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return plane_to_code_lut[(yoffset + 1) * 16 + 8 + (xsize - xoffset)] + 1; 625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return dist + 120; 645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 665a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE int FindMatchLength(const uint32_t* const array1, 675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const array2, 685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int max_limit) { 695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int match_len = 0; 705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora while (match_len < max_limit && array1[match_len] == array2[match_len]) { 715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++match_len; 725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return match_len; 745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 755a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// ----------------------------------------------------------------------------- 775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// VP8LBackwardRefs 785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 795a50414796e9a458925c7a13a15055d02406bf43Vikas Aroravoid VP8LInitBackwardRefs(VP8LBackwardRefs* const refs) { 805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (refs != NULL) { 815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs = NULL; 825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = 0; 835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->max_size = 0; 845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 875a50414796e9a458925c7a13a15055d02406bf43Vikas Aroravoid VP8LClearBackwardRefs(VP8LBackwardRefs* const refs) { 885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (refs != NULL) { 895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(refs->refs); 905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LInitBackwardRefs(refs); 915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 945a50414796e9a458925c7a13a15055d02406bf43Vikas Aroraint VP8LBackwardRefsAlloc(VP8LBackwardRefs* const refs, int max_size) { 955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(refs != NULL); 965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = 0; 975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->max_size = 0; 985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs = (PixOrCopy*)WebPSafeMalloc((uint64_t)max_size, 995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora sizeof(*refs->refs)); 1005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (refs->refs == NULL) return 0; 1015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->max_size = max_size; 1025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return 1; 1035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 1045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// ----------------------------------------------------------------------------- 1065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Hash chains 1075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1085a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE uint64_t GetPixPairHash64(const uint32_t* const argb) { 1095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint64_t key = ((uint64_t)(argb[1]) << 32) | argb[0]; 1105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora key = (key * HASH_MULTIPLIER) >> (64 - HASH_BITS); 1115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return key; 1125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 1135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1145a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int HashChainInit(HashChain* const p, int size) { 1155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 1165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora p->chain_ = (int*)WebPSafeMalloc((uint64_t)size, sizeof(*p->chain_)); 1175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (p->chain_ == NULL) { 1185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return 0; 1195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < size; ++i) { 1215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora p->chain_[i] = -1; 1225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < HASH_SIZE; ++i) { 1245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora p->hash_to_first_index_[i] = -1; 1255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return 1; 1275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 1285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1295a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic void HashChainDelete(HashChain* const p) { 1305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (p != NULL) { 1315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(p->chain_); 1325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(p); 1335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 1355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Insertion of two pixels at a time. 1375a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic void HashChainInsert(HashChain* const p, 1385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, int pos) { 1395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint64_t hash_code = GetPixPairHash64(argb); 1405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora p->chain_[pos] = p->hash_to_first_index_[hash_code]; 1415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora p->hash_to_first_index_[hash_code] = pos; 1425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 1435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1445a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int HashChainFindCopy(const HashChain* const p, 1455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int quality, int index, int xsize, 1465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, int maxlen, 1475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int* const distance_ptr, 1485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int* const length_ptr) { 1495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint64_t hash_code = GetPixPairHash64(&argb[index]); 1505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int prev_length = 0; 1515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int64_t best_val = 0; 1525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int best_length = 0; 1535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int best_distance = 0; 1545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb_start = argb + index; 1555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int iter_min_mult = (quality < 50) ? 2 : (quality < 75) ? 4 : 8; 1565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int iter_min = -quality * iter_min_mult; 1575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int iter_cnt = 10 + (quality >> 1); 1585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int min_pos = (index > WINDOW_SIZE) ? index - WINDOW_SIZE : 0; 1595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int pos; 1605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 1615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(xsize > 0); 1625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (pos = p->hash_to_first_index_[hash_code]; 1635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora pos >= min_pos; 1645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora pos = p->chain_[pos]) { 1655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int64_t val; 1665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int curr_length; 1675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (iter_cnt < 0) { 1685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (iter_cnt < iter_min || best_val >= 0xff0000) { 1695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora break; 1705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora --iter_cnt; 1735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (best_length != 0 && 1745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora argb[pos + best_length - 1] != argb_start[best_length - 1]) { 1755a50414796e9a458925c7a13a15055d02406bf43Vikas Arora continue; 1765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora curr_length = FindMatchLength(argb + pos, argb_start, maxlen); 1785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (curr_length < prev_length) { 1795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora continue; 1805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora val = 65536 * curr_length; 1825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Favoring 2d locality here gives savings for certain images. 1835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (index - pos < 9 * xsize) { 1845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int y = (index - pos) / xsize; 1855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int x = (index - pos) % xsize; 1865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (x > xsize / 2) { 1875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora x = xsize - x; 1885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (x <= 7 && x >= -8) { 1905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora val -= y * y + x * x; 1915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 1925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora val -= 9 * 9 + 9 * 9; 1935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 1955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora val -= 9 * 9 + 9 * 9; 1965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 1975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (best_val < val) { 1985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora prev_length = curr_length; 1995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora best_val = val; 2005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora best_length = curr_length; 2015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora best_distance = index - pos; 2025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (curr_length >= MAX_LENGTH) { 2035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora break; 2045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if ((best_distance == 1 || best_distance == xsize) && 2065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora best_length >= 128) { 2075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora break; 2085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *distance_ptr = best_distance; 2125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *length_ptr = best_length; 2135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return (best_length >= MIN_LENGTH); 2145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 2155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 2165a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE void PushBackCopy(VP8LBackwardRefs* const refs, int length) { 2175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int size = refs->size; 2185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora while (length >= MAX_LENGTH) { 2195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[size++] = PixOrCopyCreateCopy(1, MAX_LENGTH); 2205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora length -= MAX_LENGTH; 2215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (length > 0) { 2235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[size++] = PixOrCopyCreateCopy(1, length); 2245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = size; 2265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 2275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 2285a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic void BackwardReferencesRle(int xsize, int ysize, 2295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, 2305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs* const refs) { 2315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int pix_count = xsize * ysize; 2325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int match_len = 0; 2335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 2345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = 0; 2355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora PushBackCopy(refs, match_len); // i=0 case 2365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[0]); 2375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 1; i < pix_count; ++i) { 2385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (argb[i] == argb[i - 1]) { 2395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++match_len; 2405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 2415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora PushBackCopy(refs, match_len); 2425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora match_len = 0; 2435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[i]); 2445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora PushBackCopy(refs, match_len); 2475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 2485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 2495a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int BackwardReferencesHashChain(int xsize, int ysize, 2505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, 2515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cache_bits, int quality, 2525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs* const refs) { 2535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 2545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 2555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cc_init = 0; 2565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int use_color_cache = (cache_bits > 0); 2575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int pix_count = xsize * ysize; 2585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChain* const hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 2595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCache hashers; 2605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 2615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (hash_chain == NULL) return 0; 2625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 2635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cc_init = VP8LColorCacheInit(&hashers, cache_bits); 2645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!cc_init) goto Error; 2655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 2675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!HashChainInit(hash_chain, pix_count)) goto Error; 2685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 2695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = 0; 2705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < pix_count; ) { 2715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Alternative#1: Code the pixels starting at 'i' using backward reference. 2725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int offset = 0; 2735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int len = 0; 2745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i < pix_count - 1) { // FindCopy(i,..) reads pixels at [i] and [i + 1]. 2755a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int maxlen = pix_count - i; 2765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (maxlen > MAX_LENGTH) { 2775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora maxlen = MAX_LENGTH; 2785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainFindCopy(hash_chain, quality, i, xsize, argb, maxlen, 2805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora &offset, &len); 2815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (len >= MIN_LENGTH) { 2835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Alternative#2: Insert the pixel at 'i' as literal, and code the 2845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // pixels starting at 'i + 1' using backward reference. 2855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int offset2 = 0; 2865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int len2 = 0; 2875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int k; 2885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i], i); 2895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i < pix_count - 2) { // FindCopy(i+1,..) reads [i + 1] and [i + 2]. 2905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int maxlen = pix_count - (i + 1); 2915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (maxlen > MAX_LENGTH) { 2925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora maxlen = MAX_LENGTH; 2935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 2945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainFindCopy(hash_chain, quality, 2955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i + 1, xsize, argb, maxlen, &offset2, &len2); 2965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (len2 > len + 1) { 2975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t pixel = argb[i]; 2985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Alternative#2 is a better match. So push pixel at 'i' as literal. 2995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) { 3005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int ix = VP8LColorCacheGetIndex(&hashers, pixel); 3015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix); 3025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 3035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel); 3045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++refs->size; 3065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel); 3075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i++; // Backward reference to be done for next pixel. 3085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora len = len2; 3095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora offset = offset2; 3105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (len >= MAX_LENGTH) { 3135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora len = MAX_LENGTH - 1; 3145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size++] = PixOrCopyCreateCopy(offset, len); 3165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 3175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 0; k < len; ++k) { 3185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCacheInsert(&hashers, argb[i + k]); 3195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Add to the hash_chain (but cannot add the last pixel). 3225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora { 3235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i; 3245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 1; k < last; ++k) { 3255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i + k], i + k); 3265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i += len; 3295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 3305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t pixel = argb[i]; 3315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) { 3325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // push pixel as a PixOrCopyCreateCacheIdx pixel 3335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int ix = VP8LColorCacheGetIndex(&hashers, pixel); 3345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix); 3355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 3365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel); 3375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++refs->size; 3395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel); 3405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i + 1 < pix_count) { 3415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i], i); 3425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++i; 3445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 3475a50414796e9a458925c7a13a15055d02406bf43Vikas AroraError: 3485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cc_init) VP8LColorCacheClear(&hashers); 3495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainDelete(hash_chain); 3505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 3515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 3525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// ----------------------------------------------------------------------------- 3545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3555a50414796e9a458925c7a13a15055d02406bf43Vikas Aroratypedef struct { 3565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double alpha_[VALUES_IN_BYTE]; 3575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double red_[VALUES_IN_BYTE]; 3585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double literal_[PIX_OR_COPY_CODES_MAX]; 3595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double blue_[VALUES_IN_BYTE]; 3605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double distance_[NUM_DISTANCE_CODES]; 3615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} CostModel; 3625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3635a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int BackwardReferencesTraceBackwards( 3645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int xsize, int ysize, int recursive_cost_model, 3655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, int cache_bits, VP8LBackwardRefs* const refs); 3665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3675a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic void ConvertPopulationCountTableToBitEstimates( 3685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int num_symbols, const int population_counts[], double output[]) { 3695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int sum = 0; 3705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int nonzeros = 0; 3715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 3725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < num_symbols; ++i) { 3735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora sum += population_counts[i]; 3745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (population_counts[i] > 0) { 3755a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++nonzeros; 3765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (nonzeros <= 1) { 3795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora memset(output, 0, num_symbols * sizeof(*output)); 3805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 3815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const double logsum = VP8LFastLog2(sum); 3825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < num_symbols; ++i) { 3835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora output[i] = logsum - VP8LFastLog2(population_counts[i]); 3845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 3865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 3875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3885a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int CostModelBuild(CostModel* const m, int xsize, int ysize, 3895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int recursion_level, const uint32_t* const argb, 3905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cache_bits) { 3915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 3925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogram histo; 3935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs refs; 3945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int quality = 100; 3955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize)) goto Error; 3975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 3985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (recursion_level > 0) { 3995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!BackwardReferencesTraceBackwards(xsize, ysize, recursion_level - 1, 4005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora argb, cache_bits, &refs)) { 4015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 4025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 4035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 4045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!BackwardReferencesHashChain(xsize, ysize, argb, cache_bits, quality, 4055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora &refs)) { 4065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 4075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 4085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 4095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramCreate(&histo, &refs, cache_bits); 4105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ConvertPopulationCountTableToBitEstimates( 4115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramNumCodes(&histo), histo.literal_, m->literal_); 4125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ConvertPopulationCountTableToBitEstimates( 4135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VALUES_IN_BYTE, histo.red_, m->red_); 4145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ConvertPopulationCountTableToBitEstimates( 4155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VALUES_IN_BYTE, histo.blue_, m->blue_); 4165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ConvertPopulationCountTableToBitEstimates( 4175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VALUES_IN_BYTE, histo.alpha_, m->alpha_); 4185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ConvertPopulationCountTableToBitEstimates( 4195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora NUM_DISTANCE_CODES, histo.distance_, m->distance_); 4205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 4215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora Error: 4235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs); 4245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 4255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 4265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4275a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) { 4285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return m->alpha_[v >> 24] + 4295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora m->red_[(v >> 16) & 0xff] + 4305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora m->literal_[(v >> 8) & 0xff] + 4315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora m->blue_[v & 0xff]; 4325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 4335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4345a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) { 4355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx; 4365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return m->literal_[literal_idx]; 4375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 4385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4395a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE double GetLengthCost(const CostModel* const m, 4405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint32_t length) { 4415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int code, extra_bits_count, extra_bits_value; 4425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora PrefixEncode(length, &code, &extra_bits_count, &extra_bits_value); 4435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return m->literal_[VALUES_IN_BYTE + code] + extra_bits_count; 4445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 4455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4465a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic WEBP_INLINE double GetDistanceCost(const CostModel* const m, 4475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint32_t distance) { 4485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int code, extra_bits_count, extra_bits_value; 4495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora PrefixEncode(distance, &code, &extra_bits_count, &extra_bits_value); 4505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return m->distance_[code] + extra_bits_count; 4515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 4525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4535a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int BackwardReferencesHashChainDistanceOnly( 4545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int xsize, int ysize, int recursive_cost_model, const uint32_t* const argb, 4555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cache_bits, uint32_t* const dist_array) { 4565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 4575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 4585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cc_init = 0; 4595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int quality = 100; 4605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int pix_count = xsize * ysize; 4615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int use_color_cache = (cache_bits > 0); 4625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double* const cost = 4635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora (double*)WebPSafeMalloc((uint64_t)pix_count, sizeof(*cost)); 4645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora CostModel* cost_model = (CostModel*)malloc(sizeof(*cost_model)); 4655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 4665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCache hashers; 4675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const double mul0 = (recursive_cost_model != 0) ? 1.0 : 0.68; 4685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const double mul1 = (recursive_cost_model != 0) ? 1.0 : 0.82; 4695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cost == NULL || cost_model == NULL || hash_chain == NULL) goto Error; 4715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!HashChainInit(hash_chain, pix_count)) goto Error; 4735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 4755a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cc_init = VP8LColorCacheInit(&hashers, cache_bits); 4765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!cc_init) goto Error; 4775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 4785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!CostModelBuild(cost_model, xsize, ysize, recursive_cost_model, argb, 4805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cache_bits)) { 4815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 4825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 4835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < pix_count; ++i) cost[i] = 1e100; 4855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 4865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // We loop one pixel at a time, but store all currently best points to 4875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // non-processed locations from this point. 4885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora dist_array[0] = 0; 4895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < pix_count; ++i) { 4905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double prev_cost = 0.0; 4915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int shortmax; 4925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i > 0) { 4935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora prev_cost = cost[i - 1]; 4945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 4955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (shortmax = 0; shortmax < 2; ++shortmax) { 4965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int offset = 0; 4975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int len = 0; 4985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i < pix_count - 1) { // FindCopy reads pixels at [i] and [i + 1]. 4995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int maxlen = shortmax ? 2 : MAX_LENGTH; 5005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (maxlen > pix_count - i) { 5015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora maxlen = pix_count - i; 5025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainFindCopy(hash_chain, quality, i, xsize, argb, maxlen, 5045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora &offset, &len); 5055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (len >= MIN_LENGTH) { 5075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int code = DistanceToPlaneCode(xsize, offset); 5085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const double distance_cost = 5095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora prev_cost + GetDistanceCost(cost_model, code); 5105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int k; 5115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 1; k < len; ++k) { 5125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const double cost_val = 5135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora distance_cost + GetLengthCost(cost_model, k); 5145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cost[i + k] > cost_val) { 5155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cost[i + k] = cost_val; 5165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora dist_array[i + k] = k + 1; 5175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // This if is for speedup only. It roughly doubles the speed, and 5205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // makes compression worse by .1 %. 5215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (len >= 128 && code < 2) { 5225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Long copy for short distances, let's skip the middle 5235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // lookups for better copies. 5245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // 1) insert the hashes. 5255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 5265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 0; k < len; ++k) { 5275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCacheInsert(&hashers, argb[i + k]); 5285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // 2) Add to the hash_chain (but cannot add the last pixel) 5315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora { 5325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int last = (len < pix_count - 1 - i) ? len 5335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora : pix_count - 1 - i; 5345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 0; k < last; ++k) { 5355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i + k], i + k); 5365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // 3) jump. 5395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i += len - 1; // for loop does ++i, thus -1 here. 5405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto next_symbol; 5415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i < pix_count - 1) { 5455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i], i); 5465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora { 5485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // inserting a literal pixel 5495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double cost_val = prev_cost; 5505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { 5515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int ix = VP8LColorCacheGetIndex(&hashers, argb[i]); 5525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cost_val += GetCacheCost(cost_model, ix) * mul0; 5535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 5545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cost_val += GetLiteralCost(cost_model, argb[i]) * mul1; 5555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cost[i] > cost_val) { 5575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cost[i] = cost_val; 5585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora dist_array[i] = 1; // only one is inserted. 5595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 5615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora next_symbol: ; 5635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Last pixel still to do, it can only be a single step if not reached 5655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // through cheaper means already. 5665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 5675a50414796e9a458925c7a13a15055d02406bf43Vikas AroraError: 5685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cc_init) VP8LColorCacheClear(&hashers); 5695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainDelete(hash_chain); 5705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(cost_model); 5715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(cost); 5725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 5735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 5745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 5755a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int TraceBackwards(const uint32_t* const dist_array, 5765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int dist_array_size, 5775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint32_t** const chosen_path, 5785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int* const chosen_path_size) { 5795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 5805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Count how many. 5815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int count = 0; 5825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = dist_array_size - 1; i >= 0; ) { 5835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int k = dist_array[i]; 5845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(k >= 1); 5855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++count; 5865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i -= k; 5875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 5885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Allocate. 5895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *chosen_path_size = count; 5905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *chosen_path = 5915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora (uint32_t*)WebPSafeMalloc((uint64_t)count, sizeof(**chosen_path)); 5925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (*chosen_path == NULL) return 0; 5935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 5945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Write in reverse order. 5955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = dist_array_size - 1; i >= 0; ) { 5965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int k = dist_array[i]; 5975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(k >= 1); 5985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora (*chosen_path)[--count] = k; 5995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i -= k; 6005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return 1; 6025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 6035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 6045a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int BackwardReferencesHashChainFollowChosenPath( 6055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int xsize, int ysize, const uint32_t* const argb, int cache_bits, 6065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const chosen_path, int chosen_path_size, 6075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs* const refs) { 6085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int quality = 100; 6095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int pix_count = xsize * ysize; 6105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int use_color_cache = (cache_bits > 0); 6115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int size = 0; 6125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i = 0; 6135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int k; 6145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ix; 6155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 6165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cc_init = 0; 6175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 6185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCache hashers; 6195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 6205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (hash_chain == NULL || !HashChainInit(hash_chain, pix_count)) { 6215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 6225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 6245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cc_init = VP8LColorCacheInit(&hashers, cache_bits); 6255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!cc_init) goto Error; 6265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 6285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = 0; 6295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (ix = 0; ix < chosen_path_size; ++ix, ++size) { 6305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int offset = 0; 6315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int len = 0; 6325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int maxlen = chosen_path[ix]; 6335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (maxlen != 1) { 6345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainFindCopy(hash_chain, quality, 6355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i, xsize, argb, maxlen, &offset, &len); 6365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(len == maxlen); 6375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[size] = PixOrCopyCreateCopy(offset, len); 6385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 6395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 0; k < len; ++k) { 6405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCacheInsert(&hashers, argb[i + k]); 6415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora { 6445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i; 6455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 0; k < last; ++k) { 6465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i + k], i + k); 6475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora i += len; 6505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 6515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { 6525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // push pixel as a color cache index 6535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int idx = VP8LColorCacheGetIndex(&hashers, argb[i]); 6545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[size] = PixOrCopyCreateCacheIdx(idx); 6555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 6565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[size] = PixOrCopyCreateLiteral(argb[i]); 6575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 6595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (i + 1 < pix_count) { 6605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainInsert(hash_chain, &argb[i], i); 6615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ++i; 6635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(size <= refs->max_size); 6665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->size = size; 6675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 6685a50414796e9a458925c7a13a15055d02406bf43Vikas AroraError: 6695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cc_init) VP8LColorCacheClear(&hashers); 6705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora HashChainDelete(hash_chain); 6715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 6725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 6735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 6745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Returns 1 on success. 6755a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int BackwardReferencesTraceBackwards(int xsize, int ysize, 6765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int recursive_cost_model, 6775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, 6785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cache_bits, 6795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs* const refs) { 6805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 6815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int dist_array_size = xsize * ysize; 6825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint32_t* chosen_path = NULL; 6835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int chosen_path_size = 0; 6845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint32_t* dist_array = 6855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora (uint32_t*)WebPSafeMalloc((uint64_t)dist_array_size, sizeof(*dist_array)); 6865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 6875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (dist_array == NULL) goto Error; 6885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 6895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!BackwardReferencesHashChainDistanceOnly( 6905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora xsize, ysize, recursive_cost_model, argb, cache_bits, dist_array)) { 6915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 6925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!TraceBackwards(dist_array, dist_array_size, 6945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora &chosen_path, &chosen_path_size)) { 6955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 6965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 6975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(dist_array); // no need to retain this memory any longer 6985a50414796e9a458925c7a13a15055d02406bf43Vikas Arora dist_array = NULL; 6995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!BackwardReferencesHashChainFollowChosenPath( 7005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora xsize, ysize, argb, cache_bits, chosen_path, chosen_path_size, refs)) { 7015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 7025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 7045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora Error: 7055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(chosen_path); 7065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(dist_array); 7075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 7085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 7095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7105a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic void BackwardReferences2DLocality(int xsize, 7115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs* const refs) { 7125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 7135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < refs->size; ++i) { 7145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (PixOrCopyIsCopy(&refs->refs[i])) { 7155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int dist = refs->refs[i].argb_or_distance; 7165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int transformed_dist = DistanceToPlaneCode(xsize, dist); 7175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora refs->refs[i].argb_or_distance = transformed_dist; 7185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 7215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7225a50414796e9a458925c7a13a15055d02406bf43Vikas Aroraint VP8LGetBackwardReferences(int width, int height, 7235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const uint32_t* const argb, 7245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int quality, int cache_bits, int use_2d_locality, 7255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs* const best) { 7265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 7275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int lz77_is_useful; 7285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs refs_rle, refs_lz77; 7295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int num_pix = width * height; 7305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefsAlloc(&refs_rle, num_pix); 7325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefsAlloc(&refs_lz77, num_pix); 7335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LInitBackwardRefs(best); 7345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (refs_rle.refs == NULL || refs_lz77.refs == NULL) { 7355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora Error1: 7365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs_rle); 7375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs_lz77); 7385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto End; 7395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!BackwardReferencesHashChain(width, height, argb, cache_bits, quality, 7425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora &refs_lz77)) { 7435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto End; 7445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7455a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Backward Reference using RLE only. 7465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora BackwardReferencesRle(width, height, argb, &refs_rle); 7475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora { 7495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double bit_cost_lz77, bit_cost_rle; 7505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogram* const histo = (VP8LHistogram*)malloc(sizeof(*histo)); 7515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (histo == NULL) goto Error1; 7525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Evaluate lz77 coding 7535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramCreate(histo, &refs_lz77, cache_bits); 7545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora bit_cost_lz77 = VP8LHistogramEstimateBits(histo); 7555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Evaluate RLE coding 7565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramCreate(histo, &refs_rle, cache_bits); 7575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora bit_cost_rle = VP8LHistogramEstimateBits(histo); 7585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Decide if LZ77 is useful. 7595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora lz77_is_useful = (bit_cost_lz77 < bit_cost_rle); 7605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora free(histo); 7615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // Choose appropriate backward reference. 7645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (lz77_is_useful) { 7655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // TraceBackwards is costly. Run it for higher qualities. 7665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int try_lz77_trace_backwards = (quality >= 75); 7675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *best = refs_lz77; // default guess: lz77 is better 7685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs_rle); 7695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (try_lz77_trace_backwards) { 7705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int recursion_level = (num_pix < 320 * 200) ? 1 : 0; 7715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs refs_trace; 7725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!VP8LBackwardRefsAlloc(&refs_trace, num_pix)) { 7735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto End; 7745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7755a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (BackwardReferencesTraceBackwards( 7765a50414796e9a458925c7a13a15055d02406bf43Vikas Arora width, height, recursion_level, argb, cache_bits, &refs_trace)) { 7775a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs_lz77); 7785a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *best = refs_trace; 7795a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7805a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7815a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 7825a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs_lz77); 7835a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *best = refs_rle; 7845a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7855a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7865a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_2d_locality) BackwardReferences2DLocality(width, best); 7875a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7885a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 7895a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7905a50414796e9a458925c7a13a15055d02406bf43Vikas Arora End: 7915a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!ok) { 7925a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(best); 7935a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 7945a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 7955a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 7965a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 7975a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Returns 1 on success. 7985a50414796e9a458925c7a13a15055d02406bf43Vikas Arorastatic int ComputeCacheHistogram(const uint32_t* const argb, 7995a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int xsize, int ysize, 8005a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const VP8LBackwardRefs* const refs, 8015a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cache_bits, 8025a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogram* const histo) { 8035a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int pixel_index = 0; 8045a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int i; 8055a50414796e9a458925c7a13a15055d02406bf43Vikas Arora uint32_t k; 8065a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCache hashers; 8075a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int use_color_cache = (cache_bits > 0); 8085a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cc_init = 0; 8095a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 8105a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 8115a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cc_init = VP8LColorCacheInit(&hashers, cache_bits); 8125a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!cc_init) return 0; 8135a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8145a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 8155a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (i = 0; i < refs->size; ++i) { 8165a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const PixOrCopy* const v = &refs->refs[i]; 8175a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (PixOrCopyIsLiteral(v)) { 8185a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache && 8195a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCacheContains(&hashers, argb[pixel_index])) { 8205a50414796e9a458925c7a13a15055d02406bf43Vikas Arora // push pixel as a cache index 8215a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const int ix = VP8LColorCacheGetIndex(&hashers, argb[pixel_index]); 8225a50414796e9a458925c7a13a15055d02406bf43Vikas Arora const PixOrCopy token = PixOrCopyCreateCacheIdx(ix); 8235a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramAddSinglePixOrCopy(histo, &token); 8245a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 8255a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramAddSinglePixOrCopy(histo, v); 8265a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8275a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } else { 8285a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramAddSinglePixOrCopy(histo, v); 8295a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8305a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (use_color_cache) { 8315a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (k = 0; k < PixOrCopyLength(v); ++k) { 8325a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LColorCacheInsert(&hashers, argb[pixel_index + k]); 8335a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8345a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8355a50414796e9a458925c7a13a15055d02406bf43Vikas Arora pixel_index += PixOrCopyLength(v); 8365a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8375a50414796e9a458925c7a13a15055d02406bf43Vikas Arora assert(pixel_index == xsize * ysize); 8385a50414796e9a458925c7a13a15055d02406bf43Vikas Arora (void)xsize; // xsize is not used in non-debug compilations otherwise. 8395a50414796e9a458925c7a13a15055d02406bf43Vikas Arora (void)ysize; // ysize is not used in non-debug compilations otherwise. 8405a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cc_init) VP8LColorCacheClear(&hashers); 8415a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return 1; 8425a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 8435a50414796e9a458925c7a13a15055d02406bf43Vikas Arora 8445a50414796e9a458925c7a13a15055d02406bf43Vikas Arora// Returns how many bits are to be used for a color cache. 8455a50414796e9a458925c7a13a15055d02406bf43Vikas Aroraint VP8LCalculateEstimateForCacheSize(const uint32_t* const argb, 8465a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int xsize, int ysize, 8475a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int* const best_cache_bits) { 8485a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int ok = 0; 8495a50414796e9a458925c7a13a15055d02406bf43Vikas Arora int cache_bits; 8505a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double lowest_entropy = 1e99; 8515a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LBackwardRefs refs; 8525a50414796e9a458925c7a13a15055d02406bf43Vikas Arora static const double kSmallPenaltyForLargeCache = 4.0; 8535a50414796e9a458925c7a13a15055d02406bf43Vikas Arora static const int quality = 30; 8545a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize) || 8555a50414796e9a458925c7a13a15055d02406bf43Vikas Arora !BackwardReferencesHashChain(xsize, ysize, argb, 0, quality, &refs)) { 8565a50414796e9a458925c7a13a15055d02406bf43Vikas Arora goto Error; 8575a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8585a50414796e9a458925c7a13a15055d02406bf43Vikas Arora for (cache_bits = 0; cache_bits <= MAX_COLOR_CACHE_BITS; ++cache_bits) { 8595a50414796e9a458925c7a13a15055d02406bf43Vikas Arora double cur_entropy; 8605a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogram histo; 8615a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LHistogramInit(&histo, cache_bits); 8625a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ComputeCacheHistogram(argb, xsize, ysize, &refs, cache_bits, &histo); 8635a50414796e9a458925c7a13a15055d02406bf43Vikas Arora cur_entropy = VP8LHistogramEstimateBits(&histo) + 8645a50414796e9a458925c7a13a15055d02406bf43Vikas Arora kSmallPenaltyForLargeCache * cache_bits; 8655a50414796e9a458925c7a13a15055d02406bf43Vikas Arora if (cache_bits == 0 || cur_entropy < lowest_entropy) { 8665a50414796e9a458925c7a13a15055d02406bf43Vikas Arora *best_cache_bits = cache_bits; 8675a50414796e9a458925c7a13a15055d02406bf43Vikas Arora lowest_entropy = cur_entropy; 8685a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8695a50414796e9a458925c7a13a15055d02406bf43Vikas Arora } 8705a50414796e9a458925c7a13a15055d02406bf43Vikas Arora ok = 1; 8715a50414796e9a458925c7a13a15055d02406bf43Vikas Arora Error: 8725a50414796e9a458925c7a13a15055d02406bf43Vikas Arora VP8LClearBackwardRefs(&refs); 8735a50414796e9a458925c7a13a15055d02406bf43Vikas Arora return ok; 8745a50414796e9a458925c7a13a15055d02406bf43Vikas Arora} 875