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