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 | |
28 | extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); |
29 | extern int VP8LDistanceToPlaneCode(int xsize, int dist); |
30 | extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, |
31 | const PixOrCopy v); |
32 | |
33 | typedef 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 | |
41 | static 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 | |
62 | static 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 | |
96 | static 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 | |
103 | static 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 | |
108 | static WEBP_INLINE float GetLengthCost(const CostModel* const m, |
109 | uint32_t length) { |
110 | int code, ; |
111 | VP8LPrefixEncodeBits(length, &code, &extra_bits); |
112 | return m->literal_[VALUES_IN_BYTE + code] + extra_bits; |
113 | } |
114 | |
115 | static WEBP_INLINE float GetDistanceCost(const CostModel* const m, |
116 | uint32_t distance) { |
117 | int code, ; |
118 | VP8LPrefixEncodeBits(distance, &code, &extra_bits); |
119 | return m->distance_[code] + extra_bits; |
120 | } |
121 | |
122 | static 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. |
164 | typedef struct CostInterval CostInterval; |
165 | struct 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. |
175 | typedef 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 |
186 | typedef 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 | |
203 | static void CostIntervalAddToFreeList(CostManager* const manager, |
204 | CostInterval* const interval) { |
205 | interval->next_ = manager->free_intervals_; |
206 | manager->free_intervals_ = interval; |
207 | } |
208 | |
209 | static 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 | |
215 | static 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 | |
223 | static 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 | |
234 | static 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 | |
251 | static 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. |
327 | static 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. |
340 | static 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'. |
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 | 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. |
465 | static 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 | |
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(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] |
694 | static 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 | |
710 | static 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. |
762 | extern 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); |
766 | int 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 | |