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 | |
27 | extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); |
28 | extern int VP8LDistanceToPlaneCode(int xsize, int dist); |
29 | extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, |
30 | const PixOrCopy v); |
31 | |
32 | typedef 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 | |
40 | static 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 | |
61 | static 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 | |
95 | static 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 | |
102 | static 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 | |
107 | static WEBP_INLINE double GetLengthCost(const CostModel* const m, |
108 | uint32_t length) { |
109 | int code, ; |
110 | VP8LPrefixEncodeBits(length, &code, &extra_bits); |
111 | return m->literal_[VALUES_IN_BYTE + code] + extra_bits; |
112 | } |
113 | |
114 | static WEBP_INLINE double GetDistanceCost(const CostModel* const m, |
115 | uint32_t distance) { |
116 | int code, ; |
117 | VP8LPrefixEncodeBits(distance, &code, &extra_bits); |
118 | return m->distance_[code] + extra_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 | 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. |
163 | typedef struct CostInterval CostInterval; |
164 | struct 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. |
174 | typedef 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 |
185 | typedef 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 | |
202 | static void CostIntervalAddToFreeList(CostManager* const manager, |
203 | CostInterval* const interval) { |
204 | interval->next_ = manager->free_intervals_; |
205 | manager->free_intervals_ = interval; |
206 | } |
207 | |
208 | static 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 | |
214 | static 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 | |
222 | static 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 | |
233 | static 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 | |
250 | static 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. |
321 | static 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. |
334 | static 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'. |
342 | static 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. |
355 | static 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. |
374 | static 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. |
395 | static 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. |
419 | static 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. |
459 | static 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 | |
563 | static 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_; |
678 | Error: |
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] |
689 | static 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 | |
705 | static 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. |
757 | extern 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); |
761 | int 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 | |