backward_references_cost_enc.c (29637B)
1 // Copyright 2017 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 // Improves a given set of backward references by analyzing its bit cost. 11 // The algorithm is similar to the Zopfli compression algorithm but tailored to 12 // images. 13 // 14 // Author: Vincent Rabaud (vrabaud@google.com) 15 // 16 17 #include <assert.h> 18 #include <string.h> 19 20 #include "src/dsp/lossless_common.h" 21 #include "src/enc/backward_references_enc.h" 22 #include "src/enc/histogram_enc.h" 23 #include "src/utils/color_cache_utils.h" 24 #include "src/utils/utils.h" 25 #include "src/webp/format_constants.h" 26 #include "src/webp/types.h" 27 28 #define VALUES_IN_BYTE 256 29 30 extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); 31 extern int VP8LDistanceToPlaneCode(int xsize, int dist); 32 extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, 33 const PixOrCopy v); 34 35 typedef struct { 36 uint32_t alpha[VALUES_IN_BYTE]; 37 uint32_t red[VALUES_IN_BYTE]; 38 uint32_t blue[VALUES_IN_BYTE]; 39 uint32_t distance[NUM_DISTANCE_CODES]; 40 uint32_t* literal; 41 } CostModel; 42 43 static void ConvertPopulationCountTableToBitEstimates( 44 int num_symbols, const uint32_t population_counts[], uint32_t output[]) { 45 uint32_t sum = 0; 46 int nonzeros = 0; 47 int i; 48 for (i = 0; i < num_symbols; ++i) { 49 sum += population_counts[i]; 50 if (population_counts[i] > 0) { 51 ++nonzeros; 52 } 53 } 54 if (nonzeros <= 1) { 55 memset(output, 0, num_symbols * sizeof(*output)); 56 } else { 57 const uint32_t logsum = VP8LFastLog2(sum); 58 for (i = 0; i < num_symbols; ++i) { 59 output[i] = logsum - VP8LFastLog2(population_counts[i]); 60 } 61 } 62 } 63 64 static int CostModelBuild(CostModel* const m, int xsize, int cache_bits, 65 const VP8LBackwardRefs* const refs) { 66 int ok = 0; 67 VP8LHistogram* const histo = VP8LAllocateHistogram(cache_bits); 68 if (histo == NULL) goto Error; 69 70 // The following code is similar to VP8LHistogramCreate but converts the 71 // distance to plane code. 72 VP8LHistogramInit(histo, cache_bits, /*init_arrays=*/ 1); 73 VP8LHistogramStoreRefs(refs, VP8LDistanceToPlaneCode, xsize, histo); 74 75 ConvertPopulationCountTableToBitEstimates( 76 VP8LHistogramNumCodes(histo->palette_code_bits), histo->literal, 77 m->literal); 78 ConvertPopulationCountTableToBitEstimates( 79 VALUES_IN_BYTE, histo->red, m->red); 80 ConvertPopulationCountTableToBitEstimates( 81 VALUES_IN_BYTE, histo->blue, m->blue); 82 ConvertPopulationCountTableToBitEstimates( 83 VALUES_IN_BYTE, histo->alpha, m->alpha); 84 ConvertPopulationCountTableToBitEstimates( 85 NUM_DISTANCE_CODES, histo->distance, m->distance); 86 ok = 1; 87 88 Error: 89 VP8LFreeHistogram(histo); 90 return ok; 91 } 92 93 static WEBP_INLINE int64_t GetLiteralCost(const CostModel* const m, 94 uint32_t v) { 95 return (int64_t)m->alpha[v >> 24] + m->red[(v >> 16) & 0xff] + 96 m->literal[(v >> 8) & 0xff] + m->blue[v & 0xff]; 97 } 98 99 static WEBP_INLINE int64_t GetCacheCost(const CostModel* const m, 100 uint32_t idx) { 101 const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx; 102 return (int64_t)m->literal[literal_idx]; 103 } 104 105 static WEBP_INLINE int64_t GetLengthCost(const CostModel* const m, 106 uint32_t length) { 107 int code, extra_bits; 108 VP8LPrefixEncodeBits(length, &code, &extra_bits); 109 return (int64_t)m->literal[VALUES_IN_BYTE + code] + 110 ((int64_t)extra_bits << LOG_2_PRECISION_BITS); 111 } 112 113 static WEBP_INLINE int64_t GetDistanceCost(const CostModel* const m, 114 uint32_t distance) { 115 int code, extra_bits; 116 VP8LPrefixEncodeBits(distance, &code, &extra_bits); 117 return (int64_t)m->distance[code] + 118 ((int64_t)extra_bits << LOG_2_PRECISION_BITS); 119 } 120 121 static WEBP_INLINE void AddSingleLiteralWithCostModel( 122 const uint32_t* const argb, VP8LColorCache* const hashers, 123 const CostModel* const cost_model, int idx, int use_color_cache, 124 int64_t prev_cost, int64_t* const cost, uint16_t* const dist_array) { 125 int64_t cost_val = prev_cost; 126 const uint32_t color = argb[idx]; 127 const int ix = use_color_cache ? VP8LColorCacheContains(hashers, color) : -1; 128 if (ix >= 0) { 129 // use_color_cache is true and hashers contains color 130 cost_val += DivRound(GetCacheCost(cost_model, ix) * 68, 100); 131 } else { 132 if (use_color_cache) VP8LColorCacheInsert(hashers, color); 133 cost_val += DivRound(GetLiteralCost(cost_model, color) * 82, 100); 134 } 135 if (cost[idx] > cost_val) { 136 cost[idx] = cost_val; 137 dist_array[idx] = 1; // only one is inserted. 138 } 139 } 140 141 // ----------------------------------------------------------------------------- 142 // CostManager and interval handling 143 144 // Empirical value to avoid high memory consumption but good for performance. 145 #define COST_CACHE_INTERVAL_SIZE_MAX 500 146 147 // To perform backward reference every pixel at index 'index' is considered and 148 // the cost for the MAX_LENGTH following pixels computed. Those following pixels 149 // at index 'index' + k (k from 0 to MAX_LENGTH) have a cost of: 150 // cost = distance cost at index + GetLengthCost(cost_model, k) 151 // and the minimum value is kept. GetLengthCost(cost_model, k) is cached in an 152 // array of size MAX_LENGTH. 153 // Instead of performing MAX_LENGTH comparisons per pixel, we keep track of the 154 // minimal values using intervals of constant cost. 155 // An interval is defined by the 'index' of the pixel that generated it and 156 // is only useful in a range of indices from 'start' to 'end' (exclusive), i.e. 157 // it contains the minimum value for pixels between start and end. 158 // Intervals are stored in a linked list and ordered by 'start'. When a new 159 // interval has a better value, old intervals are split or removed. There are 160 // therefore no overlapping intervals. 161 typedef struct CostInterval CostInterval; 162 struct CostInterval { 163 int64_t cost; 164 int start; 165 int end; 166 int index; 167 CostInterval* previous; 168 CostInterval* next; 169 }; 170 171 // The GetLengthCost(cost_model, k) are cached in a CostCacheInterval. 172 typedef struct { 173 int64_t cost; 174 int start; 175 int end; // Exclusive. 176 } CostCacheInterval; 177 178 // This structure is in charge of managing intervals and costs. 179 // It caches the different CostCacheInterval, caches the different 180 // GetLengthCost(cost_model, k) in cost_cache and the CostInterval's (whose 181 // 'count' is limited by COST_CACHE_INTERVAL_SIZE_MAX). 182 #define COST_MANAGER_MAX_FREE_LIST 10 183 typedef struct { 184 CostInterval* head; 185 int count; // The number of stored intervals. 186 CostCacheInterval* cache_intervals; 187 size_t cache_intervals_size; 188 // Contains the GetLengthCost(cost_model, k). 189 int64_t cost_cache[MAX_LENGTH]; 190 int64_t* costs; 191 uint16_t* dist_array; 192 // Most of the time, we only need few intervals -> use a free-list, to avoid 193 // fragmentation with small allocs in most common cases. 194 CostInterval intervals[COST_MANAGER_MAX_FREE_LIST]; 195 CostInterval* free_intervals; 196 // These are regularly malloc'd remains. This list can't grow larger than than 197 // size COST_CACHE_INTERVAL_SIZE_MAX - COST_MANAGER_MAX_FREE_LIST, note. 198 CostInterval* recycled_intervals; 199 } CostManager; 200 201 static void CostIntervalAddToFreeList(CostManager* const manager, 202 CostInterval* const interval) { 203 interval->next = manager->free_intervals; 204 manager->free_intervals = interval; 205 } 206 207 static int CostIntervalIsInFreeList(const CostManager* const manager, 208 const CostInterval* const interval) { 209 return (interval >= &manager->intervals[0] && 210 interval <= &manager->intervals[COST_MANAGER_MAX_FREE_LIST - 1]); 211 } 212 213 static void CostManagerInitFreeList(CostManager* const manager) { 214 int i; 215 manager->free_intervals = NULL; 216 for (i = 0; i < COST_MANAGER_MAX_FREE_LIST; ++i) { 217 CostIntervalAddToFreeList(manager, &manager->intervals[i]); 218 } 219 } 220 221 static void DeleteIntervalList(CostManager* const manager, 222 const CostInterval* interval) { 223 while (interval != NULL) { 224 const CostInterval* const next = interval->next; 225 if (!CostIntervalIsInFreeList(manager, interval)) { 226 WebPSafeFree((void*)interval); 227 } // else: do nothing 228 interval = next; 229 } 230 } 231 232 static void CostManagerClear(CostManager* const manager) { 233 if (manager == NULL) return; 234 235 WebPSafeFree(manager->costs); 236 WebPSafeFree(manager->cache_intervals); 237 238 // Clear the interval lists. 239 DeleteIntervalList(manager, manager->head); 240 manager->head = NULL; 241 DeleteIntervalList(manager, manager->recycled_intervals); 242 manager->recycled_intervals = NULL; 243 244 // Reset pointers, 'count' and 'cache_intervals_size'. 245 memset(manager, 0, sizeof(*manager)); 246 CostManagerInitFreeList(manager); 247 } 248 249 static int CostManagerInit(CostManager* const manager, 250 uint16_t* const dist_array, int pix_count, 251 const CostModel* const cost_model) { 252 int i; 253 const int cost_cache_size = (pix_count > MAX_LENGTH) ? MAX_LENGTH : pix_count; 254 255 manager->costs = NULL; 256 manager->cache_intervals = NULL; 257 manager->head = NULL; 258 manager->recycled_intervals = NULL; 259 manager->count = 0; 260 manager->dist_array = dist_array; 261 CostManagerInitFreeList(manager); 262 263 // Fill in the 'cost_cache'. 264 // Has to be done in two passes due to a GCC bug on i686 265 // related to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323 266 for (i = 0; i < cost_cache_size; ++i) { 267 manager->cost_cache[i] = GetLengthCost(cost_model, i); 268 } 269 manager->cache_intervals_size = 1; 270 for (i = 1; i < cost_cache_size; ++i) { 271 // Get the number of bound intervals. 272 if (manager->cost_cache[i] != manager->cost_cache[i - 1]) { 273 ++manager->cache_intervals_size; 274 } 275 } 276 277 // With the current cost model, we usually have below 20 intervals. 278 // The worst case scenario with a cost model would be if every length has a 279 // different cost, hence MAX_LENGTH but that is impossible with the current 280 // implementation that spirals around a pixel. 281 assert(manager->cache_intervals_size <= MAX_LENGTH); 282 manager->cache_intervals = (CostCacheInterval*)WebPSafeMalloc( 283 manager->cache_intervals_size, sizeof(*manager->cache_intervals)); 284 if (manager->cache_intervals == NULL) { 285 CostManagerClear(manager); 286 return 0; 287 } 288 289 // Fill in the 'cache_intervals'. 290 { 291 CostCacheInterval* cur = manager->cache_intervals; 292 293 // Consecutive values in 'cost_cache' are compared and if a big enough 294 // difference is found, a new interval is created and bounded. 295 cur->start = 0; 296 cur->end = 1; 297 cur->cost = manager->cost_cache[0]; 298 for (i = 1; i < cost_cache_size; ++i) { 299 const int64_t cost_val = manager->cost_cache[i]; 300 if (cost_val != cur->cost) { 301 ++cur; 302 // Initialize an interval. 303 cur->start = i; 304 cur->cost = cost_val; 305 } 306 cur->end = i + 1; 307 } 308 assert((size_t)(cur - manager->cache_intervals) + 1 == 309 manager->cache_intervals_size); 310 } 311 312 manager->costs = 313 (int64_t*)WebPSafeMalloc(pix_count, sizeof(*manager->costs)); 314 if (manager->costs == NULL) { 315 CostManagerClear(manager); 316 return 0; 317 } 318 // Set the initial 'costs' to INT64_MAX for every pixel as we will keep the 319 // minimum. 320 for (i = 0; i < pix_count; ++i) manager->costs[i] = WEBP_INT64_MAX; 321 322 return 1; 323 } 324 325 // Given the cost and the position that define an interval, update the cost at 326 // pixel 'i' if it is smaller than the previously computed value. 327 static WEBP_INLINE void UpdateCost(CostManager* const manager, int i, 328 int position, int64_t cost) { 329 const int k = i - position; 330 assert(k >= 0 && k < MAX_LENGTH); 331 332 if (manager->costs[i] > cost) { 333 manager->costs[i] = cost; 334 manager->dist_array[i] = k + 1; 335 } 336 } 337 338 // Given the cost and the position that define an interval, update the cost for 339 // all the pixels between 'start' and 'end' excluded. 340 static WEBP_INLINE void UpdateCostPerInterval(CostManager* const manager, 341 int start, int end, int position, 342 int64_t cost) { 343 int i; 344 for (i = start; i < end; ++i) UpdateCost(manager, i, position, cost); 345 } 346 347 // Given two intervals, make 'prev' be the previous one of 'next' in 'manager'. 348 static WEBP_INLINE void ConnectIntervals(CostManager* const manager, 349 CostInterval* const prev, 350 CostInterval* const next) { 351 if (prev != NULL) { 352 prev->next = next; 353 } else { 354 manager->head = next; 355 } 356 357 if (next != NULL) next->previous = prev; 358 } 359 360 // Pop an interval in the manager. 361 static WEBP_INLINE void PopInterval(CostManager* const manager, 362 CostInterval* const interval) { 363 if (interval == NULL) return; 364 365 ConnectIntervals(manager, interval->previous, interval->next); 366 if (CostIntervalIsInFreeList(manager, interval)) { 367 CostIntervalAddToFreeList(manager, interval); 368 } else { // recycle regularly malloc'd intervals too 369 interval->next = manager->recycled_intervals; 370 manager->recycled_intervals = interval; 371 } 372 --manager->count; 373 assert(manager->count >= 0); 374 } 375 376 // Update the cost at index i by going over all the stored intervals that 377 // overlap with i. 378 // If 'do_clean_intervals' is set to something different than 0, intervals that 379 // end before 'i' will be popped. 380 static WEBP_INLINE void UpdateCostAtIndex(CostManager* const manager, int i, 381 int do_clean_intervals) { 382 CostInterval* current = manager->head; 383 384 while (current != NULL && current->start <= i) { 385 CostInterval* const next = current->next; 386 if (current->end <= i) { 387 if (do_clean_intervals) { 388 // We have an outdated interval, remove it. 389 PopInterval(manager, current); 390 } 391 } else { 392 UpdateCost(manager, i, current->index, current->cost); 393 } 394 current = next; 395 } 396 } 397 398 // Given a current orphan interval and its previous interval, before 399 // it was orphaned (which can be NULL), set it at the right place in the list 400 // of intervals using the 'start' ordering and the previous interval as a hint. 401 static WEBP_INLINE void PositionOrphanInterval(CostManager* const manager, 402 CostInterval* const current, 403 CostInterval* previous) { 404 assert(current != NULL); 405 406 if (previous == NULL) previous = manager->head; 407 while (previous != NULL && current->start < previous->start) { 408 previous = previous->previous; 409 } 410 while (previous != NULL && previous->next != NULL && 411 previous->next->start < current->start) { 412 previous = previous->next; 413 } 414 415 if (previous != NULL) { 416 ConnectIntervals(manager, current, previous->next); 417 } else { 418 ConnectIntervals(manager, current, manager->head); 419 } 420 ConnectIntervals(manager, previous, current); 421 } 422 423 // Insert an interval in the list contained in the manager by starting at 424 // 'interval_in' as a hint. The intervals are sorted by 'start' value. 425 static WEBP_INLINE void InsertInterval(CostManager* const manager, 426 CostInterval* const interval_in, 427 int64_t cost, int position, int start, 428 int end) { 429 CostInterval* interval_new; 430 431 if (start >= end) return; 432 if (manager->count >= COST_CACHE_INTERVAL_SIZE_MAX) { 433 // Serialize the interval if we cannot store it. 434 UpdateCostPerInterval(manager, start, end, position, cost); 435 return; 436 } 437 if (manager->free_intervals != NULL) { 438 interval_new = manager->free_intervals; 439 manager->free_intervals = interval_new->next; 440 } else if (manager->recycled_intervals != NULL) { 441 interval_new = manager->recycled_intervals; 442 manager->recycled_intervals = interval_new->next; 443 } else { // malloc for good 444 interval_new = (CostInterval*)WebPSafeMalloc(1, sizeof(*interval_new)); 445 if (interval_new == NULL) { 446 // Write down the interval if we cannot create it. 447 UpdateCostPerInterval(manager, start, end, position, cost); 448 return; 449 } 450 } 451 452 interval_new->cost = cost; 453 interval_new->index = position; 454 interval_new->start = start; 455 interval_new->end = end; 456 PositionOrphanInterval(manager, interval_new, interval_in); 457 458 ++manager->count; 459 } 460 461 // Given a new cost interval defined by its start at position, its length value 462 // and distance_cost, add its contributions to the previous intervals and costs. 463 // If handling the interval or one of its subintervals becomes to heavy, its 464 // contribution is added to the costs right away. 465 static WEBP_INLINE void PushInterval(CostManager* const manager, 466 int64_t distance_cost, int position, 467 int len) { 468 size_t i; 469 CostInterval* interval = manager->head; 470 CostInterval* interval_next; 471 const CostCacheInterval* const cost_cache_intervals = 472 manager->cache_intervals; 473 // If the interval is small enough, no need to deal with the heavy 474 // interval logic, just serialize it right away. This constant is empirical. 475 const int kSkipDistance = 10; 476 477 if (len < kSkipDistance) { 478 int j; 479 for (j = position; j < position + len; ++j) { 480 const int k = j - position; 481 int64_t cost_tmp; 482 assert(k >= 0 && k < MAX_LENGTH); 483 cost_tmp = distance_cost + manager->cost_cache[k]; 484 485 if (manager->costs[j] > cost_tmp) { 486 manager->costs[j] = cost_tmp; 487 manager->dist_array[j] = k + 1; 488 } 489 } 490 return; 491 } 492 493 for (i = 0; i < manager->cache_intervals_size && 494 cost_cache_intervals[i].start < len; 495 ++i) { 496 // Define the intersection of the ith interval with the new one. 497 int start = position + cost_cache_intervals[i].start; 498 const int end = position + (cost_cache_intervals[i].end > len 499 ? len 500 : cost_cache_intervals[i].end); 501 const int64_t cost = distance_cost + cost_cache_intervals[i].cost; 502 503 for (; interval != NULL && interval->start < end; 504 interval = interval_next) { 505 interval_next = interval->next; 506 507 // Make sure we have some overlap 508 if (start >= interval->end) continue; 509 510 if (cost >= interval->cost) { 511 // When intervals are represented, the lower, the better. 512 // [**********************************************************[ 513 // start end 514 // [----------------------------------[ 515 // interval->start interval->end 516 // If we are worse than what we already have, add whatever we have so 517 // far up to interval. 518 const int start_new = interval->end; 519 InsertInterval(manager, interval, cost, position, start, 520 interval->start); 521 start = start_new; 522 if (start >= end) break; 523 continue; 524 } 525 526 if (start <= interval->start) { 527 if (interval->end <= end) { 528 // [----------------------------------[ 529 // interval->start interval->end 530 // [**************************************************************[ 531 // start end 532 // We can safely remove the old interval as it is fully included. 533 PopInterval(manager, interval); 534 } else { 535 // [------------------------------------[ 536 // interval->start interval->end 537 // [*****************************[ 538 // start end 539 interval->start = end; 540 break; 541 } 542 } else { 543 if (end < interval->end) { 544 // [--------------------------------------------------------------[ 545 // interval->start interval->end 546 // [*****************************[ 547 // start end 548 // We have to split the old interval as it fully contains the new one. 549 const int end_original = interval->end; 550 interval->end = start; 551 InsertInterval(manager, interval, interval->cost, interval->index, 552 end, end_original); 553 interval = interval->next; 554 break; 555 } else { 556 // [------------------------------------[ 557 // interval->start interval->end 558 // [*****************************[ 559 // start end 560 interval->end = start; 561 } 562 } 563 } 564 // Insert the remaining interval from start to end. 565 InsertInterval(manager, interval, cost, position, start, end); 566 } 567 } 568 569 static int BackwardReferencesHashChainDistanceOnly( 570 int xsize, int ysize, const uint32_t* const argb, int cache_bits, 571 const VP8LHashChain* const hash_chain, const VP8LBackwardRefs* const refs, 572 uint16_t* const dist_array) { 573 int i; 574 int ok = 0; 575 int cc_init = 0; 576 const int pix_count = xsize * ysize; 577 const int use_color_cache = (cache_bits > 0); 578 const size_t literal_array_size = 579 sizeof(*((CostModel*)NULL)->literal) * VP8LHistogramNumCodes(cache_bits); 580 const size_t cost_model_size = sizeof(CostModel) + literal_array_size; 581 CostModel* const cost_model = 582 (CostModel*)WebPSafeCalloc(1ULL, cost_model_size); 583 VP8LColorCache hashers; 584 CostManager* cost_manager = 585 (CostManager*)WebPSafeCalloc(1ULL, sizeof(*cost_manager)); 586 int offset_prev = -1, len_prev = -1; 587 int64_t offset_cost = -1; 588 int first_offset_is_constant = -1; // initialized with 'impossible' value 589 int reach = 0; 590 591 if (cost_model == NULL || cost_manager == NULL) goto Error; 592 593 cost_model->literal = (uint32_t*)(cost_model + 1); 594 if (use_color_cache) { 595 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 596 if (!cc_init) goto Error; 597 } 598 599 if (!CostModelBuild(cost_model, xsize, cache_bits, refs)) { 600 goto Error; 601 } 602 603 if (!CostManagerInit(cost_manager, dist_array, pix_count, cost_model)) { 604 goto Error; 605 } 606 607 // We loop one pixel at a time, but store all currently best points to 608 // non-processed locations from this point. 609 dist_array[0] = 0; 610 // Add first pixel as literal. 611 AddSingleLiteralWithCostModel(argb, &hashers, cost_model, /*idx=*/0, 612 use_color_cache, /*prev_cost=*/0, 613 cost_manager->costs, dist_array); 614 615 for (i = 1; i < pix_count; ++i) { 616 const int64_t prev_cost = cost_manager->costs[i - 1]; 617 int offset, len; 618 VP8LHashChainFindCopy(hash_chain, i, &offset, &len); 619 620 // Try adding the pixel as a literal. 621 AddSingleLiteralWithCostModel(argb, &hashers, cost_model, i, 622 use_color_cache, prev_cost, 623 cost_manager->costs, dist_array); 624 625 // If we are dealing with a non-literal. 626 if (len >= 2) { 627 if (offset != offset_prev) { 628 const int code = VP8LDistanceToPlaneCode(xsize, offset); 629 offset_cost = GetDistanceCost(cost_model, code); 630 first_offset_is_constant = 1; 631 PushInterval(cost_manager, prev_cost + offset_cost, i, len); 632 } else { 633 assert(offset_cost >= 0); 634 assert(len_prev >= 0); 635 assert(first_offset_is_constant == 0 || first_offset_is_constant == 1); 636 // Instead of considering all contributions from a pixel i by calling: 637 // PushInterval(cost_manager, prev_cost + offset_cost, i, len); 638 // we optimize these contributions in case offset_cost stays the same 639 // for consecutive pixels. This describes a set of pixels similar to a 640 // previous set (e.g. constant color regions). 641 if (first_offset_is_constant) { 642 reach = i - 1 + len_prev - 1; 643 first_offset_is_constant = 0; 644 } 645 646 if (i + len - 1 > reach) { 647 // We can only be go further with the same offset if the previous 648 // length was maxed, hence len_prev == len == MAX_LENGTH. 649 // TODO(vrabaud), bump i to the end right away (insert cache and 650 // update cost). 651 // TODO(vrabaud), check if one of the points in between does not have 652 // a lower cost. 653 // Already consider the pixel at "reach" to add intervals that are 654 // better than whatever we add. 655 int offset_j, len_j = 0; 656 int j; 657 assert(len == MAX_LENGTH || len == pix_count - i); 658 // Figure out the last consecutive pixel within [i, reach + 1] with 659 // the same offset. 660 for (j = i; j <= reach; ++j) { 661 VP8LHashChainFindCopy(hash_chain, j + 1, &offset_j, &len_j); 662 if (offset_j != offset) { 663 VP8LHashChainFindCopy(hash_chain, j, &offset_j, &len_j); 664 break; 665 } 666 } 667 // Update the cost at j - 1 and j. 668 UpdateCostAtIndex(cost_manager, j - 1, 0); 669 UpdateCostAtIndex(cost_manager, j, 0); 670 671 PushInterval(cost_manager, cost_manager->costs[j - 1] + offset_cost, 672 j, len_j); 673 reach = j + len_j - 1; 674 } 675 } 676 } 677 678 UpdateCostAtIndex(cost_manager, i, 1); 679 offset_prev = offset; 680 len_prev = len; 681 } 682 683 ok = !refs->error; 684 Error: 685 if (cc_init) VP8LColorCacheClear(&hashers); 686 CostManagerClear(cost_manager); 687 WebPSafeFree(cost_model); 688 WebPSafeFree(cost_manager); 689 return ok; 690 } 691 692 // We pack the path at the end of *dist_array and return 693 // a pointer to this part of the array. Example: 694 // dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232] 695 static void TraceBackwards(uint16_t* const dist_array, 696 int dist_array_size, 697 uint16_t** const chosen_path, 698 int* const chosen_path_size) { 699 uint16_t* path = dist_array + dist_array_size; 700 uint16_t* cur = dist_array + dist_array_size - 1; 701 while (cur >= dist_array) { 702 const int k = *cur; 703 --path; 704 *path = k; 705 cur -= k; 706 } 707 *chosen_path = path; 708 *chosen_path_size = (int)(dist_array + dist_array_size - path); 709 } 710 711 static int BackwardReferencesHashChainFollowChosenPath( 712 const uint32_t* const argb, int cache_bits, 713 const uint16_t* const chosen_path, int chosen_path_size, 714 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs) { 715 const int use_color_cache = (cache_bits > 0); 716 int ix; 717 int i = 0; 718 int ok = 0; 719 int cc_init = 0; 720 VP8LColorCache hashers; 721 722 if (use_color_cache) { 723 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 724 if (!cc_init) goto Error; 725 } 726 727 VP8LClearBackwardRefs(refs); 728 for (ix = 0; ix < chosen_path_size; ++ix) { 729 const int len = chosen_path[ix]; 730 if (len != 1) { 731 int k; 732 const int offset = VP8LHashChainFindOffset(hash_chain, i); 733 VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len)); 734 if (use_color_cache) { 735 for (k = 0; k < len; ++k) { 736 VP8LColorCacheInsert(&hashers, argb[i + k]); 737 } 738 } 739 i += len; 740 } else { 741 PixOrCopy v; 742 const int idx = 743 use_color_cache ? VP8LColorCacheContains(&hashers, argb[i]) : -1; 744 if (idx >= 0) { 745 // use_color_cache is true and hashers contains argb[i] 746 // push pixel as a color cache index 747 v = PixOrCopyCreateCacheIdx(idx); 748 } else { 749 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 750 v = PixOrCopyCreateLiteral(argb[i]); 751 } 752 VP8LBackwardRefsCursorAdd(refs, v); 753 ++i; 754 } 755 } 756 ok = !refs->error; 757 Error: 758 if (cc_init) VP8LColorCacheClear(&hashers); 759 return ok; 760 } 761 762 // Returns 1 on success. 763 extern int VP8LBackwardReferencesTraceBackwards( 764 int xsize, int ysize, const uint32_t* const argb, int cache_bits, 765 const VP8LHashChain* const hash_chain, 766 const VP8LBackwardRefs* const refs_src, VP8LBackwardRefs* const refs_dst); 767 int VP8LBackwardReferencesTraceBackwards(int xsize, int ysize, 768 const uint32_t* const argb, 769 int cache_bits, 770 const VP8LHashChain* const hash_chain, 771 const VP8LBackwardRefs* const refs_src, 772 VP8LBackwardRefs* const refs_dst) { 773 int ok = 0; 774 const int dist_array_size = xsize * ysize; 775 uint16_t* chosen_path = NULL; 776 int chosen_path_size = 0; 777 uint16_t* dist_array = 778 (uint16_t*)WebPSafeMalloc(dist_array_size, sizeof(*dist_array)); 779 780 if (dist_array == NULL) goto Error; 781 782 if (!BackwardReferencesHashChainDistanceOnly( 783 xsize, ysize, argb, cache_bits, hash_chain, refs_src, dist_array)) { 784 goto Error; 785 } 786 TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size); 787 if (!BackwardReferencesHashChainFollowChosenPath( 788 argb, cache_bits, chosen_path, chosen_path_size, hash_chain, 789 refs_dst)) { 790 goto Error; 791 } 792 ok = 1; 793 Error: 794 WebPSafeFree(dist_array); 795 return ok; 796 }