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 <float.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
26#define VALUES_IN_BYTE 256
27
28extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs);
29extern int VP8LDistanceToPlaneCode(int xsize, int dist);
30extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs,
31 const PixOrCopy v);
32
33typedef struct {
34 float alpha_[VALUES_IN_BYTE];
35 float red_[VALUES_IN_BYTE];
36 float blue_[VALUES_IN_BYTE];
37 float distance_[NUM_DISTANCE_CODES];
38 float* literal_;
39} CostModel;
40
41static void ConvertPopulationCountTableToBitEstimates(
42 int num_symbols, const uint32_t population_counts[], float output[]) {
43 uint32_t sum = 0;
44 int nonzeros = 0;
45 int i;
46 for (i = 0; i < num_symbols; ++i) {
47 sum += population_counts[i];
48 if (population_counts[i] > 0) {
49 ++nonzeros;
50 }
51 }
52 if (nonzeros <= 1) {
53 memset(output, 0, num_symbols * sizeof(*output));
54 } else {
55 const float logsum = VP8LFastLog2(sum);
56 for (i = 0; i < num_symbols; ++i) {
57 output[i] = logsum - VP8LFastLog2(population_counts[i]);
58 }
59 }
60}
61
62static int CostModelBuild(CostModel* const m, int xsize, int cache_bits,
63 const VP8LBackwardRefs* const refs) {
64 int ok = 0;
65 VP8LRefsCursor c = VP8LRefsCursorInit(refs);
66 VP8LHistogram* const histo = VP8LAllocateHistogram(cache_bits);
67 if (histo == NULL) goto Error;
68
69 // The following code is similar to VP8LHistogramCreate but converts the
70 // distance to plane code.
71 VP8LHistogramInit(histo, cache_bits, /*init_arrays=*/ 1);
72 while (VP8LRefsCursorOk(&c)) {
73 VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos, VP8LDistanceToPlaneCode,
74 xsize);
75 VP8LRefsCursorNext(&c);
76 }
77
78 ConvertPopulationCountTableToBitEstimates(
79 VP8LHistogramNumCodes(histo->palette_code_bits_), histo->literal_,
80 m->literal_);
81 ConvertPopulationCountTableToBitEstimates(
82 VALUES_IN_BYTE, histo->red_, m->red_);
83 ConvertPopulationCountTableToBitEstimates(
84 VALUES_IN_BYTE, histo->blue_, m->blue_);
85 ConvertPopulationCountTableToBitEstimates(
86 VALUES_IN_BYTE, histo->alpha_, m->alpha_);
87 ConvertPopulationCountTableToBitEstimates(
88 NUM_DISTANCE_CODES, histo->distance_, m->distance_);
89 ok = 1;
90
91 Error:
92 VP8LFreeHistogram(histo);
93 return ok;
94}
95
96static WEBP_INLINE float GetLiteralCost(const CostModel* const m, uint32_t v) {
97 return m->alpha_[v >> 24] +
98 m->red_[(v >> 16) & 0xff] +
99 m->literal_[(v >> 8) & 0xff] +
100 m->blue_[v & 0xff];
101}
102
103static WEBP_INLINE float GetCacheCost(const CostModel* const m, uint32_t idx) {
104 const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx;
105 return m->literal_[literal_idx];
106}
107
108static WEBP_INLINE float GetLengthCost(const CostModel* const m,
109 uint32_t length) {
110 int code, extra_bits;
111 VP8LPrefixEncodeBits(length, &code, &extra_bits);
112 return m->literal_[VALUES_IN_BYTE + code] + extra_bits;
113}
114
115static WEBP_INLINE float GetDistanceCost(const CostModel* const m,
116 uint32_t distance) {
117 int code, extra_bits;
118 VP8LPrefixEncodeBits(distance, &code, &extra_bits);
119 return m->distance_[code] + extra_bits;
120}
121
122static WEBP_INLINE void AddSingleLiteralWithCostModel(
123 const uint32_t* const argb, VP8LColorCache* const hashers,
124 const CostModel* const cost_model, int idx, int use_color_cache,
125 float prev_cost, float* const cost, uint16_t* const dist_array) {
126 float cost_val = prev_cost;
127 const uint32_t color = argb[idx];
128 const int ix = use_color_cache ? VP8LColorCacheContains(hashers, color) : -1;
129 if (ix >= 0) {
130 // use_color_cache is true and hashers contains color
131 const float mul0 = 0.68f;
132 cost_val += GetCacheCost(cost_model, ix) * mul0;
133 } else {
134 const float mul1 = 0.82f;
135 if (use_color_cache) VP8LColorCacheInsert(hashers, color);
136 cost_val += GetLiteralCost(cost_model, color) * mul1;
137 }
138 if (cost[idx] > cost_val) {
139 cost[idx] = cost_val;
140 dist_array[idx] = 1; // only one is inserted.
141 }
142}
143
144// -----------------------------------------------------------------------------
145// CostManager and interval handling
146
147// Empirical value to avoid high memory consumption but good for performance.
148#define COST_CACHE_INTERVAL_SIZE_MAX 500
149
150// To perform backward reference every pixel at index index_ is considered and
151// the cost for the MAX_LENGTH following pixels computed. Those following pixels
152// at index index_ + k (k from 0 to MAX_LENGTH) have a cost of:
153// cost_ = distance cost at index + GetLengthCost(cost_model, k)
154// and the minimum value is kept. GetLengthCost(cost_model, k) is cached in an
155// array of size MAX_LENGTH.
156// Instead of performing MAX_LENGTH comparisons per pixel, we keep track of the
157// minimal values using intervals of constant cost.
158// An interval is defined by the index_ of the pixel that generated it and
159// is only useful in a range of indices from start_ to end_ (exclusive), i.e.
160// it contains the minimum value for pixels between start_ and end_.
161// Intervals are stored in a linked list and ordered by start_. When a new
162// interval has a better value, old intervals are split or removed. There are
163// therefore no overlapping intervals.
164typedef struct CostInterval CostInterval;
165struct CostInterval {
166 float cost_;
167 int start_;
168 int end_;
169 int index_;
170 CostInterval* previous_;
171 CostInterval* next_;
172};
173
174// The GetLengthCost(cost_model, k) are cached in a CostCacheInterval.
175typedef struct {
176 float cost_;
177 int start_;
178 int end_; // Exclusive.
179} CostCacheInterval;
180
181// This structure is in charge of managing intervals and costs.
182// It caches the different CostCacheInterval, caches the different
183// GetLengthCost(cost_model, k) in cost_cache_ and the CostInterval's (whose
184// count_ is limited by COST_CACHE_INTERVAL_SIZE_MAX).
185#define COST_MANAGER_MAX_FREE_LIST 10
186typedef struct {
187 CostInterval* head_;
188 int count_; // The number of stored intervals.
189 CostCacheInterval* cache_intervals_;
190 size_t cache_intervals_size_;
191 float cost_cache_[MAX_LENGTH]; // Contains the GetLengthCost(cost_model, k).
192 float* costs_;
193 uint16_t* dist_array_;
194 // Most of the time, we only need few intervals -> use a free-list, to avoid
195 // fragmentation with small allocs in most common cases.
196 CostInterval intervals_[COST_MANAGER_MAX_FREE_LIST];
197 CostInterval* free_intervals_;
198 // These are regularly malloc'd remains. This list can't grow larger than than
199 // size COST_CACHE_INTERVAL_SIZE_MAX - COST_MANAGER_MAX_FREE_LIST, note.
200 CostInterval* recycled_intervals_;
201} CostManager;
202
203static void CostIntervalAddToFreeList(CostManager* const manager,
204 CostInterval* const interval) {
205 interval->next_ = manager->free_intervals_;
206 manager->free_intervals_ = interval;
207}
208
209static int CostIntervalIsInFreeList(const CostManager* const manager,
210 const CostInterval* const interval) {
211 return (interval >= &manager->intervals_[0] &&
212 interval <= &manager->intervals_[COST_MANAGER_MAX_FREE_LIST - 1]);
213}
214
215static void CostManagerInitFreeList(CostManager* const manager) {
216 int i;
217 manager->free_intervals_ = NULL;
218 for (i = 0; i < COST_MANAGER_MAX_FREE_LIST; ++i) {
219 CostIntervalAddToFreeList(manager, &manager->intervals_[i]);
220 }
221}
222
223static void DeleteIntervalList(CostManager* const manager,
224 const CostInterval* interval) {
225 while (interval != NULL) {
226 const CostInterval* const next = interval->next_;
227 if (!CostIntervalIsInFreeList(manager, interval)) {
228 WebPSafeFree((void*)interval);
229 } // else: do nothing
230 interval = next;
231 }
232}
233
234static void CostManagerClear(CostManager* const manager) {
235 if (manager == NULL) return;
236
237 WebPSafeFree(manager->costs_);
238 WebPSafeFree(manager->cache_intervals_);
239
240 // Clear the interval lists.
241 DeleteIntervalList(manager, manager->head_);
242 manager->head_ = NULL;
243 DeleteIntervalList(manager, manager->recycled_intervals_);
244 manager->recycled_intervals_ = NULL;
245
246 // Reset pointers, count_ and cache_intervals_size_.
247 memset(manager, 0, sizeof(*manager));
248 CostManagerInitFreeList(manager);
249}
250
251static int CostManagerInit(CostManager* const manager,
252 uint16_t* const dist_array, int pix_count,
253 const CostModel* const cost_model) {
254 int i;
255 const int cost_cache_size = (pix_count > MAX_LENGTH) ? MAX_LENGTH : pix_count;
256
257 manager->costs_ = NULL;
258 manager->cache_intervals_ = NULL;
259 manager->head_ = NULL;
260 manager->recycled_intervals_ = NULL;
261 manager->count_ = 0;
262 manager->dist_array_ = dist_array;
263 CostManagerInitFreeList(manager);
264
265 // Fill in the cost_cache_.
266 // Has to be done in two passes due to a GCC bug on i686
267 // related to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323
268 for (i = 0; i < cost_cache_size; ++i) {
269 manager->cost_cache_[i] = GetLengthCost(cost_model, i);
270 }
271 manager->cache_intervals_size_ = 1;
272 for (i = 1; i < cost_cache_size; ++i) {
273 // Get the number of bound intervals.
274 if (manager->cost_cache_[i] != manager->cost_cache_[i - 1]) {
275 ++manager->cache_intervals_size_;
276 }
277 }
278
279 // With the current cost model, we usually have below 20 intervals.
280 // The worst case scenario with a cost model would be if every length has a
281 // different cost, hence MAX_LENGTH but that is impossible with the current
282 // implementation that spirals around a pixel.
283 assert(manager->cache_intervals_size_ <= MAX_LENGTH);
284 manager->cache_intervals_ = (CostCacheInterval*)WebPSafeMalloc(
285 manager->cache_intervals_size_, sizeof(*manager->cache_intervals_));
286 if (manager->cache_intervals_ == NULL) {
287 CostManagerClear(manager);
288 return 0;
289 }
290
291 // Fill in the cache_intervals_.
292 {
293 CostCacheInterval* cur = manager->cache_intervals_;
294
295 // Consecutive values in cost_cache_ are compared and if a big enough
296 // difference is found, a new interval is created and bounded.
297 cur->start_ = 0;
298 cur->end_ = 1;
299 cur->cost_ = manager->cost_cache_[0];
300 for (i = 1; i < cost_cache_size; ++i) {
301 const float cost_val = manager->cost_cache_[i];
302 if (cost_val != cur->cost_) {
303 ++cur;
304 // Initialize an interval.
305 cur->start_ = i;
306 cur->cost_ = cost_val;
307 }
308 cur->end_ = i + 1;
309 }
310 assert((size_t)(cur - manager->cache_intervals_) + 1 ==
311 manager->cache_intervals_size_);
312 }
313
314 manager->costs_ = (float*)WebPSafeMalloc(pix_count, sizeof(*manager->costs_));
315 if (manager->costs_ == NULL) {
316 CostManagerClear(manager);
317 return 0;
318 }
319 // Set the initial costs_ high for every pixel as we will keep the minimum.
320 for (i = 0; i < pix_count; ++i) manager->costs_[i] = FLT_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.
327static WEBP_INLINE void UpdateCost(CostManager* const manager, int i,
328 int position, float 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.
340static WEBP_INLINE void UpdateCostPerInterval(CostManager* const manager,
341 int start, int end, int position,
342 float 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'.
348static 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.
361static 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.
380static 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.
401static 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.
425static WEBP_INLINE void InsertInterval(CostManager* const manager,
426 CostInterval* const interval_in,
427 float 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.
465static WEBP_INLINE void PushInterval(CostManager* const manager,
466 float 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 float 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 float 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
569static 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(float) * (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 float offset_cost = -1.f;
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_ = (float*)(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, 0, use_color_cache,
612 0.f, cost_manager->costs_, dist_array);
613
614 for (i = 1; i < pix_count; ++i) {
615 const float prev_cost = cost_manager->costs_[i - 1];
616 int offset, len;
617 VP8LHashChainFindCopy(hash_chain, i, &offset, &len);
618
619 // Try adding the pixel as a literal.
620 AddSingleLiteralWithCostModel(argb, &hashers, cost_model, i,
621 use_color_cache, prev_cost,
622 cost_manager->costs_, dist_array);
623
624 // If we are dealing with a non-literal.
625 if (len >= 2) {
626 if (offset != offset_prev) {
627 const int code = VP8LDistanceToPlaneCode(xsize, offset);
628 offset_cost = GetDistanceCost(cost_model, code);
629 first_offset_is_constant = 1;
630 PushInterval(cost_manager, prev_cost + offset_cost, i, len);
631 } else {
632 assert(offset_cost >= 0);
633 assert(len_prev >= 0);
634 assert(first_offset_is_constant == 0 || first_offset_is_constant == 1);
635 // Instead of considering all contributions from a pixel i by calling:
636 // PushInterval(cost_manager, prev_cost + offset_cost, i, len);
637 // we optimize these contributions in case offset_cost stays the same
638 // for consecutive pixels. This describes a set of pixels similar to a
639 // previous set (e.g. constant color regions).
640 if (first_offset_is_constant) {
641 reach = i - 1 + len_prev - 1;
642 first_offset_is_constant = 0;
643 }
644
645 if (i + len - 1 > reach) {
646 // We can only be go further with the same offset if the previous
647 // length was maxed, hence len_prev == len == MAX_LENGTH.
648 // TODO(vrabaud), bump i to the end right away (insert cache and
649 // update cost).
650 // TODO(vrabaud), check if one of the points in between does not have
651 // a lower cost.
652 // Already consider the pixel at "reach" to add intervals that are
653 // better than whatever we add.
654 int offset_j, len_j = 0;
655 int j;
656 assert(len == MAX_LENGTH || len == pix_count - i);
657 // Figure out the last consecutive pixel within [i, reach + 1] with
658 // the same offset.
659 for (j = i; j <= reach; ++j) {
660 VP8LHashChainFindCopy(hash_chain, j + 1, &offset_j, &len_j);
661 if (offset_j != offset) {
662 VP8LHashChainFindCopy(hash_chain, j, &offset_j, &len_j);
663 break;
664 }
665 }
666 // Update the cost at j - 1 and j.
667 UpdateCostAtIndex(cost_manager, j - 1, 0);
668 UpdateCostAtIndex(cost_manager, j, 0);
669
670 PushInterval(cost_manager, cost_manager->costs_[j - 1] + offset_cost,
671 j, len_j);
672 reach = j + len_j - 1;
673 }
674 }
675 }
676
677 UpdateCostAtIndex(cost_manager, i, 1);
678 offset_prev = offset;
679 len_prev = len;
680 }
681
682 ok = !refs->error_;
683 Error:
684 if (cc_init) VP8LColorCacheClear(&hashers);
685 CostManagerClear(cost_manager);
686 WebPSafeFree(cost_model);
687 WebPSafeFree(cost_manager);
688 return ok;
689}
690
691// We pack the path at the end of *dist_array and return
692// a pointer to this part of the array. Example:
693// dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232]
694static void TraceBackwards(uint16_t* const dist_array,
695 int dist_array_size,
696 uint16_t** const chosen_path,
697 int* const chosen_path_size) {
698 uint16_t* path = dist_array + dist_array_size;
699 uint16_t* cur = dist_array + dist_array_size - 1;
700 while (cur >= dist_array) {
701 const int k = *cur;
702 --path;
703 *path = k;
704 cur -= k;
705 }
706 *chosen_path = path;
707 *chosen_path_size = (int)(dist_array + dist_array_size - path);
708}
709
710static int BackwardReferencesHashChainFollowChosenPath(
711 const uint32_t* const argb, int cache_bits,
712 const uint16_t* const chosen_path, int chosen_path_size,
713 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs) {
714 const int use_color_cache = (cache_bits > 0);
715 int ix;
716 int i = 0;
717 int ok = 0;
718 int cc_init = 0;
719 VP8LColorCache hashers;
720
721 if (use_color_cache) {
722 cc_init = VP8LColorCacheInit(&hashers, cache_bits);
723 if (!cc_init) goto Error;
724 }
725
726 VP8LClearBackwardRefs(refs);
727 for (ix = 0; ix < chosen_path_size; ++ix) {
728 const int len = chosen_path[ix];
729 if (len != 1) {
730 int k;
731 const int offset = VP8LHashChainFindOffset(hash_chain, i);
732 VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len));
733 if (use_color_cache) {
734 for (k = 0; k < len; ++k) {
735 VP8LColorCacheInsert(&hashers, argb[i + k]);
736 }
737 }
738 i += len;
739 } else {
740 PixOrCopy v;
741 const int idx =
742 use_color_cache ? VP8LColorCacheContains(&hashers, argb[i]) : -1;
743 if (idx >= 0) {
744 // use_color_cache is true and hashers contains argb[i]
745 // push pixel as a color cache index
746 v = PixOrCopyCreateCacheIdx(idx);
747 } else {
748 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
749 v = PixOrCopyCreateLiteral(argb[i]);
750 }
751 VP8LBackwardRefsCursorAdd(refs, v);
752 ++i;
753 }
754 }
755 ok = !refs->error_;
756 Error:
757 if (cc_init) VP8LColorCacheClear(&hashers);
758 return ok;
759}
760
761// Returns 1 on success.
762extern int VP8LBackwardReferencesTraceBackwards(
763 int xsize, int ysize, const uint32_t* const argb, int cache_bits,
764 const VP8LHashChain* const hash_chain,
765 const VP8LBackwardRefs* const refs_src, VP8LBackwardRefs* const refs_dst);
766int VP8LBackwardReferencesTraceBackwards(int xsize, int ysize,
767 const uint32_t* const argb,
768 int cache_bits,
769 const VP8LHashChain* const hash_chain,
770 const VP8LBackwardRefs* const refs_src,
771 VP8LBackwardRefs* const refs_dst) {
772 int ok = 0;
773 const int dist_array_size = xsize * ysize;
774 uint16_t* chosen_path = NULL;
775 int chosen_path_size = 0;
776 uint16_t* dist_array =
777 (uint16_t*)WebPSafeMalloc(dist_array_size, sizeof(*dist_array));
778
779 if (dist_array == NULL) goto Error;
780
781 if (!BackwardReferencesHashChainDistanceOnly(
782 xsize, ysize, argb, cache_bits, hash_chain, refs_src, dist_array)) {
783 goto Error;
784 }
785 TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size);
786 if (!BackwardReferencesHashChainFollowChosenPath(
787 argb, cache_bits, chosen_path, chosen_path_size, hash_chain,
788 refs_dst)) {
789 goto Error;
790 }
791 ok = 1;
792 Error:
793 WebPSafeFree(dist_array);
794 return ok;
795}
796