1// Copyright 2012 Google Inc. All Rights Reserved. 2// 3// Use of this source code is governed by a BSD-style license 4// that can be found in the COPYING file in the root of the source 5// tree. An additional intellectual property rights grant can be found 6// in the file PATENTS. All contributing project authors may 7// be found in the AUTHORS file in the root of the source tree. 8// ----------------------------------------------------------------------------- 9// 10// Author: Jyrki Alakuijala (jyrki@google.com) 11// 12 13#include <assert.h> 14#include <math.h> 15 16#include "src/enc/backward_references_enc.h" 17#include "src/enc/histogram_enc.h" 18#include "src/dsp/lossless.h" 19#include "src/dsp/lossless_common.h" 20#include "src/dsp/dsp.h" 21#include "src/utils/color_cache_utils.h" 22#include "src/utils/utils.h" 23 24#define MIN_BLOCK_SIZE 256 // minimum block size for backward references 25 26#define MAX_ENTROPY (1e30f) 27 28// 1M window (4M bytes) minus 120 special codes for short distances. 29#define WINDOW_SIZE ((1 << WINDOW_SIZE_BITS) - 120) 30 31// Minimum number of pixels for which it is cheaper to encode a 32// distance + length instead of each pixel as a literal. 33#define MIN_LENGTH 4 34 35// ----------------------------------------------------------------------------- 36 37static const uint8_t plane_to_code_lut[128] = { 38 96, 73, 55, 39, 23, 13, 5, 1, 255, 255, 255, 255, 255, 255, 255, 255, 39 101, 78, 58, 42, 26, 16, 8, 2, 0, 3, 9, 17, 27, 43, 59, 79, 40 102, 86, 62, 46, 32, 20, 10, 6, 4, 7, 11, 21, 33, 47, 63, 87, 41 105, 90, 70, 52, 37, 28, 18, 14, 12, 15, 19, 29, 38, 53, 71, 91, 42 110, 99, 82, 66, 48, 35, 30, 24, 22, 25, 31, 36, 49, 67, 83, 100, 43 115, 108, 94, 76, 64, 50, 44, 40, 34, 41, 45, 51, 65, 77, 95, 109, 44 118, 113, 103, 92, 80, 68, 60, 56, 54, 57, 61, 69, 81, 93, 104, 114, 45 119, 116, 111, 106, 97, 88, 84, 74, 72, 75, 85, 89, 98, 107, 112, 117 46}; 47 48extern int VP8LDistanceToPlaneCode(int xsize, int dist); 49int VP8LDistanceToPlaneCode(int xsize, int dist) { 50 const int yoffset = dist / xsize; 51 const int xoffset = dist - yoffset * xsize; 52 if (xoffset <= 8 && yoffset < 8) { 53 return plane_to_code_lut[yoffset * 16 + 8 - xoffset] + 1; 54 } else if (xoffset > xsize - 8 && yoffset < 7) { 55 return plane_to_code_lut[(yoffset + 1) * 16 + 8 + (xsize - xoffset)] + 1; 56 } 57 return dist + 120; 58} 59 60// Returns the exact index where array1 and array2 are different. For an index 61// inferior or equal to best_len_match, the return value just has to be strictly 62// inferior to best_len_match. The current behavior is to return 0 if this index 63// is best_len_match, and the index itself otherwise. 64// If no two elements are the same, it returns max_limit. 65static WEBP_INLINE int FindMatchLength(const uint32_t* const array1, 66 const uint32_t* const array2, 67 int best_len_match, int max_limit) { 68 // Before 'expensive' linear match, check if the two arrays match at the 69 // current best length index. 70 if (array1[best_len_match] != array2[best_len_match]) return 0; 71 72 return VP8LVectorMismatch(array1, array2, max_limit); 73} 74 75// ----------------------------------------------------------------------------- 76// VP8LBackwardRefs 77 78struct PixOrCopyBlock { 79 PixOrCopyBlock* next_; // next block (or NULL) 80 PixOrCopy* start_; // data start 81 int size_; // currently used size 82}; 83 84extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); 85void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs) { 86 assert(refs != NULL); 87 if (refs->tail_ != NULL) { 88 *refs->tail_ = refs->free_blocks_; // recycle all blocks at once 89 } 90 refs->free_blocks_ = refs->refs_; 91 refs->tail_ = &refs->refs_; 92 refs->last_block_ = NULL; 93 refs->refs_ = NULL; 94} 95 96void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs) { 97 assert(refs != NULL); 98 VP8LClearBackwardRefs(refs); 99 while (refs->free_blocks_ != NULL) { 100 PixOrCopyBlock* const next = refs->free_blocks_->next_; 101 WebPSafeFree(refs->free_blocks_); 102 refs->free_blocks_ = next; 103 } 104} 105 106void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size) { 107 assert(refs != NULL); 108 memset(refs, 0, sizeof(*refs)); 109 refs->tail_ = &refs->refs_; 110 refs->block_size_ = 111 (block_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : block_size; 112} 113 114VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs) { 115 VP8LRefsCursor c; 116 c.cur_block_ = refs->refs_; 117 if (refs->refs_ != NULL) { 118 c.cur_pos = c.cur_block_->start_; 119 c.last_pos_ = c.cur_pos + c.cur_block_->size_; 120 } else { 121 c.cur_pos = NULL; 122 c.last_pos_ = NULL; 123 } 124 return c; 125} 126 127void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c) { 128 PixOrCopyBlock* const b = c->cur_block_->next_; 129 c->cur_pos = (b == NULL) ? NULL : b->start_; 130 c->last_pos_ = (b == NULL) ? NULL : b->start_ + b->size_; 131 c->cur_block_ = b; 132} 133 134// Create a new block, either from the free list or allocated 135static PixOrCopyBlock* BackwardRefsNewBlock(VP8LBackwardRefs* const refs) { 136 PixOrCopyBlock* b = refs->free_blocks_; 137 if (b == NULL) { // allocate new memory chunk 138 const size_t total_size = 139 sizeof(*b) + refs->block_size_ * sizeof(*b->start_); 140 b = (PixOrCopyBlock*)WebPSafeMalloc(1ULL, total_size); 141 if (b == NULL) { 142 refs->error_ |= 1; 143 return NULL; 144 } 145 b->start_ = (PixOrCopy*)((uint8_t*)b + sizeof(*b)); // not always aligned 146 } else { // recycle from free-list 147 refs->free_blocks_ = b->next_; 148 } 149 *refs->tail_ = b; 150 refs->tail_ = &b->next_; 151 refs->last_block_ = b; 152 b->next_ = NULL; 153 b->size_ = 0; 154 return b; 155} 156 157extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, 158 const PixOrCopy v); 159void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, 160 const PixOrCopy v) { 161 PixOrCopyBlock* b = refs->last_block_; 162 if (b == NULL || b->size_ == refs->block_size_) { 163 b = BackwardRefsNewBlock(refs); 164 if (b == NULL) return; // refs->error_ is set 165 } 166 b->start_[b->size_++] = v; 167} 168 169// ----------------------------------------------------------------------------- 170// Hash chains 171 172int VP8LHashChainInit(VP8LHashChain* const p, int size) { 173 assert(p->size_ == 0); 174 assert(p->offset_length_ == NULL); 175 assert(size > 0); 176 p->offset_length_ = 177 (uint32_t*)WebPSafeMalloc(size, sizeof(*p->offset_length_)); 178 if (p->offset_length_ == NULL) return 0; 179 p->size_ = size; 180 181 return 1; 182} 183 184void VP8LHashChainClear(VP8LHashChain* const p) { 185 assert(p != NULL); 186 WebPSafeFree(p->offset_length_); 187 188 p->size_ = 0; 189 p->offset_length_ = NULL; 190} 191 192// ----------------------------------------------------------------------------- 193 194#define HASH_MULTIPLIER_HI (0xc6a4a793ULL) 195#define HASH_MULTIPLIER_LO (0x5bd1e996ULL) 196 197static WEBP_INLINE uint32_t GetPixPairHash64(const uint32_t* const argb) { 198 uint32_t key; 199 key = (argb[1] * HASH_MULTIPLIER_HI) & 0xffffffffu; 200 key += (argb[0] * HASH_MULTIPLIER_LO) & 0xffffffffu; 201 key = key >> (32 - HASH_BITS); 202 return key; 203} 204 205// Returns the maximum number of hash chain lookups to do for a 206// given compression quality. Return value in range [8, 86]. 207static int GetMaxItersForQuality(int quality) { 208 return 8 + (quality * quality) / 128; 209} 210 211static int GetWindowSizeForHashChain(int quality, int xsize) { 212 const int max_window_size = (quality > 75) ? WINDOW_SIZE 213 : (quality > 50) ? (xsize << 8) 214 : (quality > 25) ? (xsize << 6) 215 : (xsize << 4); 216 assert(xsize > 0); 217 return (max_window_size > WINDOW_SIZE) ? WINDOW_SIZE : max_window_size; 218} 219 220static WEBP_INLINE int MaxFindCopyLength(int len) { 221 return (len < MAX_LENGTH) ? len : MAX_LENGTH; 222} 223 224int VP8LHashChainFill(VP8LHashChain* const p, int quality, 225 const uint32_t* const argb, int xsize, int ysize, 226 int low_effort) { 227 const int size = xsize * ysize; 228 const int iter_max = GetMaxItersForQuality(quality); 229 const uint32_t window_size = GetWindowSizeForHashChain(quality, xsize); 230 int pos; 231 int argb_comp; 232 uint32_t base_position; 233 int32_t* hash_to_first_index; 234 // Temporarily use the p->offset_length_ as a hash chain. 235 int32_t* chain = (int32_t*)p->offset_length_; 236 assert(size > 0); 237 assert(p->size_ != 0); 238 assert(p->offset_length_ != NULL); 239 240 if (size <= 2) { 241 p->offset_length_[0] = p->offset_length_[size - 1] = 0; 242 return 1; 243 } 244 245 hash_to_first_index = 246 (int32_t*)WebPSafeMalloc(HASH_SIZE, sizeof(*hash_to_first_index)); 247 if (hash_to_first_index == NULL) return 0; 248 249 // Set the int32_t array to -1. 250 memset(hash_to_first_index, 0xff, HASH_SIZE * sizeof(*hash_to_first_index)); 251 // Fill the chain linking pixels with the same hash. 252 argb_comp = (argb[0] == argb[1]); 253 for (pos = 0; pos < size - 2;) { 254 uint32_t hash_code; 255 const int argb_comp_next = (argb[pos + 1] == argb[pos + 2]); 256 if (argb_comp && argb_comp_next) { 257 // Consecutive pixels with the same color will share the same hash. 258 // We therefore use a different hash: the color and its repetition 259 // length. 260 uint32_t tmp[2]; 261 uint32_t len = 1; 262 tmp[0] = argb[pos]; 263 // Figure out how far the pixels are the same. 264 // The last pixel has a different 64 bit hash, as its next pixel does 265 // not have the same color, so we just need to get to the last pixel equal 266 // to its follower. 267 while (pos + (int)len + 2 < size && argb[pos + len + 2] == argb[pos]) { 268 ++len; 269 } 270 if (len > MAX_LENGTH) { 271 // Skip the pixels that match for distance=1 and length>MAX_LENGTH 272 // because they are linked to their predecessor and we automatically 273 // check that in the main for loop below. Skipping means setting no 274 // predecessor in the chain, hence -1. 275 memset(chain + pos, 0xff, (len - MAX_LENGTH) * sizeof(*chain)); 276 pos += len - MAX_LENGTH; 277 len = MAX_LENGTH; 278 } 279 // Process the rest of the hash chain. 280 while (len) { 281 tmp[1] = len--; 282 hash_code = GetPixPairHash64(tmp); 283 chain[pos] = hash_to_first_index[hash_code]; 284 hash_to_first_index[hash_code] = pos++; 285 } 286 argb_comp = 0; 287 } else { 288 // Just move one pixel forward. 289 hash_code = GetPixPairHash64(argb + pos); 290 chain[pos] = hash_to_first_index[hash_code]; 291 hash_to_first_index[hash_code] = pos++; 292 argb_comp = argb_comp_next; 293 } 294 } 295 // Process the penultimate pixel. 296 chain[pos] = hash_to_first_index[GetPixPairHash64(argb + pos)]; 297 298 WebPSafeFree(hash_to_first_index); 299 300 // Find the best match interval at each pixel, defined by an offset to the 301 // pixel and a length. The right-most pixel cannot match anything to the right 302 // (hence a best length of 0) and the left-most pixel nothing to the left 303 // (hence an offset of 0). 304 assert(size > 2); 305 p->offset_length_[0] = p->offset_length_[size - 1] = 0; 306 for (base_position = size - 2; base_position > 0;) { 307 const int max_len = MaxFindCopyLength(size - 1 - base_position); 308 const uint32_t* const argb_start = argb + base_position; 309 int iter = iter_max; 310 int best_length = 0; 311 uint32_t best_distance = 0; 312 uint32_t best_argb; 313 const int min_pos = 314 (base_position > window_size) ? base_position - window_size : 0; 315 const int length_max = (max_len < 256) ? max_len : 256; 316 uint32_t max_base_position; 317 318 pos = chain[base_position]; 319 if (!low_effort) { 320 int curr_length; 321 // Heuristic: use the comparison with the above line as an initialization. 322 if (base_position >= (uint32_t)xsize) { 323 curr_length = FindMatchLength(argb_start - xsize, argb_start, 324 best_length, max_len); 325 if (curr_length > best_length) { 326 best_length = curr_length; 327 best_distance = xsize; 328 } 329 --iter; 330 } 331 // Heuristic: compare to the previous pixel. 332 curr_length = 333 FindMatchLength(argb_start - 1, argb_start, best_length, max_len); 334 if (curr_length > best_length) { 335 best_length = curr_length; 336 best_distance = 1; 337 } 338 --iter; 339 // Skip the for loop if we already have the maximum. 340 if (best_length == MAX_LENGTH) pos = min_pos - 1; 341 } 342 best_argb = argb_start[best_length]; 343 344 for (; pos >= min_pos && --iter; pos = chain[pos]) { 345 int curr_length; 346 assert(base_position > (uint32_t)pos); 347 348 if (argb[pos + best_length] != best_argb) continue; 349 350 curr_length = VP8LVectorMismatch(argb + pos, argb_start, max_len); 351 if (best_length < curr_length) { 352 best_length = curr_length; 353 best_distance = base_position - pos; 354 best_argb = argb_start[best_length]; 355 // Stop if we have reached a good enough length. 356 if (best_length >= length_max) break; 357 } 358 } 359 // We have the best match but in case the two intervals continue matching 360 // to the left, we have the best matches for the left-extended pixels. 361 max_base_position = base_position; 362 while (1) { 363 assert(best_length <= MAX_LENGTH); 364 assert(best_distance <= WINDOW_SIZE); 365 p->offset_length_[base_position] = 366 (best_distance << MAX_LENGTH_BITS) | (uint32_t)best_length; 367 --base_position; 368 // Stop if we don't have a match or if we are out of bounds. 369 if (best_distance == 0 || base_position == 0) break; 370 // Stop if we cannot extend the matching intervals to the left. 371 if (base_position < best_distance || 372 argb[base_position - best_distance] != argb[base_position]) { 373 break; 374 } 375 // Stop if we are matching at its limit because there could be a closer 376 // matching interval with the same maximum length. Then again, if the 377 // matching interval is as close as possible (best_distance == 1), we will 378 // never find anything better so let's continue. 379 if (best_length == MAX_LENGTH && best_distance != 1 && 380 base_position + MAX_LENGTH < max_base_position) { 381 break; 382 } 383 if (best_length < MAX_LENGTH) { 384 ++best_length; 385 max_base_position = base_position; 386 } 387 } 388 } 389 return 1; 390} 391 392static WEBP_INLINE void AddSingleLiteral(uint32_t pixel, int use_color_cache, 393 VP8LColorCache* const hashers, 394 VP8LBackwardRefs* const refs) { 395 PixOrCopy v; 396 if (use_color_cache) { 397 const uint32_t key = VP8LColorCacheGetIndex(hashers, pixel); 398 if (VP8LColorCacheLookup(hashers, key) == pixel) { 399 v = PixOrCopyCreateCacheIdx(key); 400 } else { 401 v = PixOrCopyCreateLiteral(pixel); 402 VP8LColorCacheSet(hashers, key, pixel); 403 } 404 } else { 405 v = PixOrCopyCreateLiteral(pixel); 406 } 407 VP8LBackwardRefsCursorAdd(refs, v); 408} 409 410static int BackwardReferencesRle(int xsize, int ysize, 411 const uint32_t* const argb, 412 int cache_bits, VP8LBackwardRefs* const refs) { 413 const int pix_count = xsize * ysize; 414 int i, k; 415 const int use_color_cache = (cache_bits > 0); 416 VP8LColorCache hashers; 417 418 if (use_color_cache && !VP8LColorCacheInit(&hashers, cache_bits)) { 419 return 0; 420 } 421 VP8LClearBackwardRefs(refs); 422 // Add first pixel as literal. 423 AddSingleLiteral(argb[0], use_color_cache, &hashers, refs); 424 i = 1; 425 while (i < pix_count) { 426 const int max_len = MaxFindCopyLength(pix_count - i); 427 const int rle_len = FindMatchLength(argb + i, argb + i - 1, 0, max_len); 428 const int prev_row_len = (i < xsize) ? 0 : 429 FindMatchLength(argb + i, argb + i - xsize, 0, max_len); 430 if (rle_len >= prev_row_len && rle_len >= MIN_LENGTH) { 431 VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(1, rle_len)); 432 // We don't need to update the color cache here since it is always the 433 // same pixel being copied, and that does not change the color cache 434 // state. 435 i += rle_len; 436 } else if (prev_row_len >= MIN_LENGTH) { 437 VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(xsize, prev_row_len)); 438 if (use_color_cache) { 439 for (k = 0; k < prev_row_len; ++k) { 440 VP8LColorCacheInsert(&hashers, argb[i + k]); 441 } 442 } 443 i += prev_row_len; 444 } else { 445 AddSingleLiteral(argb[i], use_color_cache, &hashers, refs); 446 i++; 447 } 448 } 449 if (use_color_cache) VP8LColorCacheClear(&hashers); 450 return !refs->error_; 451} 452 453static int BackwardReferencesLz77(int xsize, int ysize, 454 const uint32_t* const argb, int cache_bits, 455 const VP8LHashChain* const hash_chain, 456 VP8LBackwardRefs* const refs) { 457 int i; 458 int i_last_check = -1; 459 int ok = 0; 460 int cc_init = 0; 461 const int use_color_cache = (cache_bits > 0); 462 const int pix_count = xsize * ysize; 463 VP8LColorCache hashers; 464 465 if (use_color_cache) { 466 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 467 if (!cc_init) goto Error; 468 } 469 VP8LClearBackwardRefs(refs); 470 for (i = 0; i < pix_count;) { 471 // Alternative#1: Code the pixels starting at 'i' using backward reference. 472 int offset = 0; 473 int len = 0; 474 int j; 475 VP8LHashChainFindCopy(hash_chain, i, &offset, &len); 476 if (len >= MIN_LENGTH) { 477 const int len_ini = len; 478 int max_reach = 0; 479 const int j_max = 480 (i + len_ini >= pix_count) ? pix_count - 1 : i + len_ini; 481 // Only start from what we have not checked already. 482 i_last_check = (i > i_last_check) ? i : i_last_check; 483 // We know the best match for the current pixel but we try to find the 484 // best matches for the current pixel AND the next one combined. 485 // The naive method would use the intervals: 486 // [i,i+len) + [i+len, length of best match at i+len) 487 // while we check if we can use: 488 // [i,j) (where j<=i+len) + [j, length of best match at j) 489 for (j = i_last_check + 1; j <= j_max; ++j) { 490 const int len_j = VP8LHashChainFindLength(hash_chain, j); 491 const int reach = 492 j + (len_j >= MIN_LENGTH ? len_j : 1); // 1 for single literal. 493 if (reach > max_reach) { 494 len = j - i; 495 max_reach = reach; 496 if (max_reach >= pix_count) break; 497 } 498 } 499 } else { 500 len = 1; 501 } 502 // Go with literal or backward reference. 503 assert(len > 0); 504 if (len == 1) { 505 AddSingleLiteral(argb[i], use_color_cache, &hashers, refs); 506 } else { 507 VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len)); 508 if (use_color_cache) { 509 for (j = i; j < i + len; ++j) VP8LColorCacheInsert(&hashers, argb[j]); 510 } 511 } 512 i += len; 513 } 514 515 ok = !refs->error_; 516 Error: 517 if (cc_init) VP8LColorCacheClear(&hashers); 518 return ok; 519} 520 521// Compute an LZ77 by forcing matches to happen within a given distance cost. 522// We therefore limit the algorithm to the lowest 32 values in the PlaneCode 523// definition. 524#define WINDOW_OFFSETS_SIZE_MAX 32 525static int BackwardReferencesLz77Box(int xsize, int ysize, 526 const uint32_t* const argb, int cache_bits, 527 const VP8LHashChain* const hash_chain_best, 528 VP8LHashChain* hash_chain, 529 VP8LBackwardRefs* const refs) { 530 int i; 531 const int pix_count = xsize * ysize; 532 uint16_t* counts; 533 int window_offsets[WINDOW_OFFSETS_SIZE_MAX] = {0}; 534 int window_offsets_new[WINDOW_OFFSETS_SIZE_MAX] = {0}; 535 int window_offsets_size = 0; 536 int window_offsets_new_size = 0; 537 uint16_t* const counts_ini = 538 (uint16_t*)WebPSafeMalloc(xsize * ysize, sizeof(*counts_ini)); 539 int best_offset_prev = -1, best_length_prev = -1; 540 if (counts_ini == NULL) return 0; 541 542 // counts[i] counts how many times a pixel is repeated starting at position i. 543 i = pix_count - 2; 544 counts = counts_ini + i; 545 counts[1] = 1; 546 for (; i >= 0; --i, --counts) { 547 if (argb[i] == argb[i + 1]) { 548 // Max out the counts to MAX_LENGTH. 549 counts[0] = counts[1] + (counts[1] != MAX_LENGTH); 550 } else { 551 counts[0] = 1; 552 } 553 } 554 555 // Figure out the window offsets around a pixel. They are stored in a 556 // spiraling order around the pixel as defined by VP8LDistanceToPlaneCode. 557 { 558 int x, y; 559 for (y = 0; y <= 6; ++y) { 560 for (x = -6; x <= 6; ++x) { 561 const int offset = y * xsize + x; 562 int plane_code; 563 // Ignore offsets that bring us after the pixel. 564 if (offset <= 0) continue; 565 plane_code = VP8LDistanceToPlaneCode(xsize, offset) - 1; 566 if (plane_code >= WINDOW_OFFSETS_SIZE_MAX) continue; 567 window_offsets[plane_code] = offset; 568 } 569 } 570 // For narrow images, not all plane codes are reached, so remove those. 571 for (i = 0; i < WINDOW_OFFSETS_SIZE_MAX; ++i) { 572 if (window_offsets[i] == 0) continue; 573 window_offsets[window_offsets_size++] = window_offsets[i]; 574 } 575 // Given a pixel P, find the offsets that reach pixels unreachable from P-1 576 // with any of the offsets in window_offsets[]. 577 for (i = 0; i < window_offsets_size; ++i) { 578 int j; 579 int is_reachable = 0; 580 for (j = 0; j < window_offsets_size && !is_reachable; ++j) { 581 is_reachable |= (window_offsets[i] == window_offsets[j] + 1); 582 } 583 if (!is_reachable) { 584 window_offsets_new[window_offsets_new_size] = window_offsets[i]; 585 ++window_offsets_new_size; 586 } 587 } 588 } 589 590 hash_chain->offset_length_[0] = 0; 591 for (i = 1; i < pix_count; ++i) { 592 int ind; 593 int best_length = VP8LHashChainFindLength(hash_chain_best, i); 594 int best_offset; 595 int do_compute = 1; 596 597 if (best_length >= MAX_LENGTH) { 598 // Do not recompute the best match if we already have a maximal one in the 599 // window. 600 best_offset = VP8LHashChainFindOffset(hash_chain_best, i); 601 for (ind = 0; ind < window_offsets_size; ++ind) { 602 if (best_offset == window_offsets[ind]) { 603 do_compute = 0; 604 break; 605 } 606 } 607 } 608 if (do_compute) { 609 // Figure out if we should use the offset/length from the previous pixel 610 // as an initial guess and therefore only inspect the offsets in 611 // window_offsets_new[]. 612 const int use_prev = 613 (best_length_prev > 1) && (best_length_prev < MAX_LENGTH); 614 const int num_ind = 615 use_prev ? window_offsets_new_size : window_offsets_size; 616 best_length = use_prev ? best_length_prev - 1 : 0; 617 best_offset = use_prev ? best_offset_prev : 0; 618 // Find the longest match in a window around the pixel. 619 for (ind = 0; ind < num_ind; ++ind) { 620 int curr_length = 0; 621 int j = i; 622 int j_offset = 623 use_prev ? i - window_offsets_new[ind] : i - window_offsets[ind]; 624 if (j_offset < 0 || argb[j_offset] != argb[i]) continue; 625 // The longest match is the sum of how many times each pixel is 626 // repeated. 627 do { 628 const int counts_j_offset = counts_ini[j_offset]; 629 const int counts_j = counts_ini[j]; 630 if (counts_j_offset != counts_j) { 631 curr_length += 632 (counts_j_offset < counts_j) ? counts_j_offset : counts_j; 633 break; 634 } 635 // The same color is repeated counts_pos times at j_offset and j. 636 curr_length += counts_j_offset; 637 j_offset += counts_j_offset; 638 j += counts_j_offset; 639 } while (curr_length <= MAX_LENGTH && j < pix_count && 640 argb[j_offset] == argb[j]); 641 if (best_length < curr_length) { 642 best_offset = 643 use_prev ? window_offsets_new[ind] : window_offsets[ind]; 644 if (curr_length >= MAX_LENGTH) { 645 best_length = MAX_LENGTH; 646 break; 647 } else { 648 best_length = curr_length; 649 } 650 } 651 } 652 } 653 654 assert(i + best_length <= pix_count); 655 assert(best_length <= MAX_LENGTH); 656 if (best_length <= MIN_LENGTH) { 657 hash_chain->offset_length_[i] = 0; 658 best_offset_prev = 0; 659 best_length_prev = 0; 660 } else { 661 hash_chain->offset_length_[i] = 662 (best_offset << MAX_LENGTH_BITS) | (uint32_t)best_length; 663 best_offset_prev = best_offset; 664 best_length_prev = best_length; 665 } 666 } 667 hash_chain->offset_length_[0] = 0; 668 WebPSafeFree(counts_ini); 669 670 return BackwardReferencesLz77(xsize, ysize, argb, cache_bits, hash_chain, 671 refs); 672} 673 674// ----------------------------------------------------------------------------- 675 676static void BackwardReferences2DLocality(int xsize, 677 const VP8LBackwardRefs* const refs) { 678 VP8LRefsCursor c = VP8LRefsCursorInit(refs); 679 while (VP8LRefsCursorOk(&c)) { 680 if (PixOrCopyIsCopy(c.cur_pos)) { 681 const int dist = c.cur_pos->argb_or_distance; 682 const int transformed_dist = VP8LDistanceToPlaneCode(xsize, dist); 683 c.cur_pos->argb_or_distance = transformed_dist; 684 } 685 VP8LRefsCursorNext(&c); 686 } 687} 688 689// Evaluate optimal cache bits for the local color cache. 690// The input *best_cache_bits sets the maximum cache bits to use (passing 0 691// implies disabling the local color cache). The local color cache is also 692// disabled for the lower (<= 25) quality. 693// Returns 0 in case of memory error. 694static int CalculateBestCacheSize(const uint32_t* argb, int quality, 695 const VP8LBackwardRefs* const refs, 696 int* const best_cache_bits) { 697 int i; 698 const int cache_bits_max = (quality <= 25) ? 0 : *best_cache_bits; 699 double entropy_min = MAX_ENTROPY; 700 int cc_init[MAX_COLOR_CACHE_BITS + 1] = { 0 }; 701 VP8LColorCache hashers[MAX_COLOR_CACHE_BITS + 1]; 702 VP8LRefsCursor c = VP8LRefsCursorInit(refs); 703 VP8LHistogram* histos[MAX_COLOR_CACHE_BITS + 1] = { NULL }; 704 int ok = 0; 705 706 assert(cache_bits_max >= 0 && cache_bits_max <= MAX_COLOR_CACHE_BITS); 707 708 if (cache_bits_max == 0) { 709 *best_cache_bits = 0; 710 // Local color cache is disabled. 711 return 1; 712 } 713 714 // Allocate data. 715 for (i = 0; i <= cache_bits_max; ++i) { 716 histos[i] = VP8LAllocateHistogram(i); 717 if (histos[i] == NULL) goto Error; 718 if (i == 0) continue; 719 cc_init[i] = VP8LColorCacheInit(&hashers[i], i); 720 if (!cc_init[i]) goto Error; 721 } 722 723 // Find the cache_bits giving the lowest entropy. The search is done in a 724 // brute-force way as the function (entropy w.r.t cache_bits) can be 725 // anything in practice. 726 while (VP8LRefsCursorOk(&c)) { 727 const PixOrCopy* const v = c.cur_pos; 728 if (PixOrCopyIsLiteral(v)) { 729 const uint32_t pix = *argb++; 730 const uint32_t a = (pix >> 24) & 0xff; 731 const uint32_t r = (pix >> 16) & 0xff; 732 const uint32_t g = (pix >> 8) & 0xff; 733 const uint32_t b = (pix >> 0) & 0xff; 734 // The keys of the caches can be derived from the longest one. 735 int key = VP8LHashPix(pix, 32 - cache_bits_max); 736 // Do not use the color cache for cache_bits = 0. 737 ++histos[0]->blue_[b]; 738 ++histos[0]->literal_[g]; 739 ++histos[0]->red_[r]; 740 ++histos[0]->alpha_[a]; 741 // Deal with cache_bits > 0. 742 for (i = cache_bits_max; i >= 1; --i, key >>= 1) { 743 if (VP8LColorCacheLookup(&hashers[i], key) == pix) { 744 ++histos[i]->literal_[NUM_LITERAL_CODES + NUM_LENGTH_CODES + key]; 745 } else { 746 VP8LColorCacheSet(&hashers[i], key, pix); 747 ++histos[i]->blue_[b]; 748 ++histos[i]->literal_[g]; 749 ++histos[i]->red_[r]; 750 ++histos[i]->alpha_[a]; 751 } 752 } 753 } else { 754 // We should compute the contribution of the (distance,length) 755 // histograms but those are the same independently from the cache size. 756 // As those constant contributions are in the end added to the other 757 // histogram contributions, we can safely ignore them. 758 int len = PixOrCopyLength(v); 759 uint32_t argb_prev = *argb ^ 0xffffffffu; 760 // Update the color caches. 761 do { 762 if (*argb != argb_prev) { 763 // Efficiency: insert only if the color changes. 764 int key = VP8LHashPix(*argb, 32 - cache_bits_max); 765 for (i = cache_bits_max; i >= 1; --i, key >>= 1) { 766 hashers[i].colors_[key] = *argb; 767 } 768 argb_prev = *argb; 769 } 770 argb++; 771 } while (--len != 0); 772 } 773 VP8LRefsCursorNext(&c); 774 } 775 776 for (i = 0; i <= cache_bits_max; ++i) { 777 const double entropy = VP8LHistogramEstimateBits(histos[i]); 778 if (i == 0 || entropy < entropy_min) { 779 entropy_min = entropy; 780 *best_cache_bits = i; 781 } 782 } 783 ok = 1; 784Error: 785 for (i = 0; i <= cache_bits_max; ++i) { 786 if (cc_init[i]) VP8LColorCacheClear(&hashers[i]); 787 VP8LFreeHistogram(histos[i]); 788 } 789 return ok; 790} 791 792// Update (in-place) backward references for specified cache_bits. 793static int BackwardRefsWithLocalCache(const uint32_t* const argb, 794 int cache_bits, 795 VP8LBackwardRefs* const refs) { 796 int pixel_index = 0; 797 VP8LColorCache hashers; 798 VP8LRefsCursor c = VP8LRefsCursorInit(refs); 799 if (!VP8LColorCacheInit(&hashers, cache_bits)) return 0; 800 801 while (VP8LRefsCursorOk(&c)) { 802 PixOrCopy* const v = c.cur_pos; 803 if (PixOrCopyIsLiteral(v)) { 804 const uint32_t argb_literal = v->argb_or_distance; 805 const int ix = VP8LColorCacheContains(&hashers, argb_literal); 806 if (ix >= 0) { 807 // hashers contains argb_literal 808 *v = PixOrCopyCreateCacheIdx(ix); 809 } else { 810 VP8LColorCacheInsert(&hashers, argb_literal); 811 } 812 ++pixel_index; 813 } else { 814 // refs was created without local cache, so it can not have cache indexes. 815 int k; 816 assert(PixOrCopyIsCopy(v)); 817 for (k = 0; k < v->len; ++k) { 818 VP8LColorCacheInsert(&hashers, argb[pixel_index++]); 819 } 820 } 821 VP8LRefsCursorNext(&c); 822 } 823 VP8LColorCacheClear(&hashers); 824 return 1; 825} 826 827static VP8LBackwardRefs* GetBackwardReferencesLowEffort( 828 int width, int height, const uint32_t* const argb, 829 int* const cache_bits, const VP8LHashChain* const hash_chain, 830 VP8LBackwardRefs* const refs_lz77) { 831 *cache_bits = 0; 832 if (!BackwardReferencesLz77(width, height, argb, 0, hash_chain, refs_lz77)) { 833 return NULL; 834 } 835 BackwardReferences2DLocality(width, refs_lz77); 836 return refs_lz77; 837} 838 839extern int VP8LBackwardReferencesTraceBackwards( 840 int xsize, int ysize, const uint32_t* const argb, int cache_bits, 841 const VP8LHashChain* const hash_chain, 842 const VP8LBackwardRefs* const refs_src, VP8LBackwardRefs* const refs_dst); 843static VP8LBackwardRefs* GetBackwardReferences( 844 int width, int height, const uint32_t* const argb, int quality, 845 int lz77_types_to_try, int* const cache_bits, 846 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* best, 847 VP8LBackwardRefs* worst) { 848 const int cache_bits_initial = *cache_bits; 849 double bit_cost_best = -1; 850 VP8LHistogram* histo = NULL; 851 int lz77_type, lz77_type_best = 0; 852 VP8LHashChain hash_chain_box; 853 memset(&hash_chain_box, 0, sizeof(hash_chain_box)); 854 855 histo = VP8LAllocateHistogram(MAX_COLOR_CACHE_BITS); 856 if (histo == NULL) goto Error; 857 858 for (lz77_type = 1; lz77_types_to_try; 859 lz77_types_to_try &= ~lz77_type, lz77_type <<= 1) { 860 int res = 0; 861 double bit_cost; 862 int cache_bits_tmp = cache_bits_initial; 863 if ((lz77_types_to_try & lz77_type) == 0) continue; 864 switch (lz77_type) { 865 case kLZ77RLE: 866 res = BackwardReferencesRle(width, height, argb, 0, worst); 867 break; 868 case kLZ77Standard: 869 // Compute LZ77 with no cache (0 bits), as the ideal LZ77 with a color 870 // cache is not that different in practice. 871 res = BackwardReferencesLz77(width, height, argb, 0, hash_chain, worst); 872 break; 873 case kLZ77Box: 874 if (!VP8LHashChainInit(&hash_chain_box, width * height)) goto Error; 875 res = BackwardReferencesLz77Box(width, height, argb, 0, hash_chain, 876 &hash_chain_box, worst); 877 break; 878 default: 879 assert(0); 880 } 881 if (!res) goto Error; 882 883 // Next, try with a color cache and update the references. 884 if (!CalculateBestCacheSize(argb, quality, worst, &cache_bits_tmp)) { 885 goto Error; 886 } 887 if (cache_bits_tmp > 0) { 888 if (!BackwardRefsWithLocalCache(argb, cache_bits_tmp, worst)) { 889 goto Error; 890 } 891 } 892 893 // Keep the best backward references. 894 VP8LHistogramCreate(histo, worst, cache_bits_tmp); 895 bit_cost = VP8LHistogramEstimateBits(histo); 896 if (lz77_type_best == 0 || bit_cost < bit_cost_best) { 897 VP8LBackwardRefs* const tmp = worst; 898 worst = best; 899 best = tmp; 900 bit_cost_best = bit_cost; 901 *cache_bits = cache_bits_tmp; 902 lz77_type_best = lz77_type; 903 } 904 } 905 assert(lz77_type_best > 0); 906 907 // Improve on simple LZ77 but only for high quality (TraceBackwards is 908 // costly). 909 if ((lz77_type_best == kLZ77Standard || lz77_type_best == kLZ77Box) && 910 quality >= 25) { 911 const VP8LHashChain* const hash_chain_tmp = 912 (lz77_type_best == kLZ77Standard) ? hash_chain : &hash_chain_box; 913 if (VP8LBackwardReferencesTraceBackwards(width, height, argb, *cache_bits, 914 hash_chain_tmp, best, worst)) { 915 double bit_cost_trace; 916 VP8LHistogramCreate(histo, worst, *cache_bits); 917 bit_cost_trace = VP8LHistogramEstimateBits(histo); 918 if (bit_cost_trace < bit_cost_best) best = worst; 919 } 920 } 921 922 BackwardReferences2DLocality(width, best); 923 924Error: 925 VP8LHashChainClear(&hash_chain_box); 926 VP8LFreeHistogram(histo); 927 return best; 928} 929 930VP8LBackwardRefs* VP8LGetBackwardReferences( 931 int width, int height, const uint32_t* const argb, int quality, 932 int low_effort, int lz77_types_to_try, int* const cache_bits, 933 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs_tmp1, 934 VP8LBackwardRefs* const refs_tmp2) { 935 if (low_effort) { 936 return GetBackwardReferencesLowEffort(width, height, argb, cache_bits, 937 hash_chain, refs_tmp1); 938 } else { 939 return GetBackwardReferences(width, height, argb, quality, 940 lz77_types_to_try, cache_bits, hash_chain, 941 refs_tmp1, refs_tmp2); 942 } 943} 944