1 | // Copyright 2012 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 | // Author: Jyrki Alakuijala (jyrki@google.com) |
11 | // |
12 | |
13 | #include "src/enc/backward_references_enc.h" |
14 | |
15 | #include <assert.h> |
16 | #include <float.h> |
17 | #include <math.h> |
18 | |
19 | #include "src/dsp/dsp.h" |
20 | #include "src/dsp/lossless.h" |
21 | #include "src/dsp/lossless_common.h" |
22 | #include "src/enc/histogram_enc.h" |
23 | #include "src/enc/vp8i_enc.h" |
24 | #include "src/utils/color_cache_utils.h" |
25 | #include "src/utils/utils.h" |
26 | #include "src/webp/encode.h" |
27 | |
28 | #define MIN_BLOCK_SIZE 256 // minimum block size for backward references |
29 | |
30 | #define MAX_ENTROPY (1e30f) |
31 | |
32 | // 1M window (4M bytes) minus 120 special codes for short distances. |
33 | #define WINDOW_SIZE ((1 << WINDOW_SIZE_BITS) - 120) |
34 | |
35 | // Minimum number of pixels for which it is cheaper to encode a |
36 | // distance + length instead of each pixel as a literal. |
37 | #define MIN_LENGTH 4 |
38 | |
39 | // ----------------------------------------------------------------------------- |
40 | |
41 | static const uint8_t plane_to_code_lut[128] = { |
42 | 96, 73, 55, 39, 23, 13, 5, 1, 255, 255, 255, 255, 255, 255, 255, 255, |
43 | 101, 78, 58, 42, 26, 16, 8, 2, 0, 3, 9, 17, 27, 43, 59, 79, |
44 | 102, 86, 62, 46, 32, 20, 10, 6, 4, 7, 11, 21, 33, 47, 63, 87, |
45 | 105, 90, 70, 52, 37, 28, 18, 14, 12, 15, 19, 29, 38, 53, 71, 91, |
46 | 110, 99, 82, 66, 48, 35, 30, 24, 22, 25, 31, 36, 49, 67, 83, 100, |
47 | 115, 108, 94, 76, 64, 50, 44, 40, 34, 41, 45, 51, 65, 77, 95, 109, |
48 | 118, 113, 103, 92, 80, 68, 60, 56, 54, 57, 61, 69, 81, 93, 104, 114, |
49 | 119, 116, 111, 106, 97, 88, 84, 74, 72, 75, 85, 89, 98, 107, 112, 117 |
50 | }; |
51 | |
52 | extern int VP8LDistanceToPlaneCode(int xsize, int dist); |
53 | int VP8LDistanceToPlaneCode(int xsize, int dist) { |
54 | const int yoffset = dist / xsize; |
55 | const int xoffset = dist - yoffset * xsize; |
56 | if (xoffset <= 8 && yoffset < 8) { |
57 | return plane_to_code_lut[yoffset * 16 + 8 - xoffset] + 1; |
58 | } else if (xoffset > xsize - 8 && yoffset < 7) { |
59 | return plane_to_code_lut[(yoffset + 1) * 16 + 8 + (xsize - xoffset)] + 1; |
60 | } |
61 | return dist + 120; |
62 | } |
63 | |
64 | // Returns the exact index where array1 and array2 are different. For an index |
65 | // inferior or equal to best_len_match, the return value just has to be strictly |
66 | // inferior to best_len_match. The current behavior is to return 0 if this index |
67 | // is best_len_match, and the index itself otherwise. |
68 | // If no two elements are the same, it returns max_limit. |
69 | static WEBP_INLINE int FindMatchLength(const uint32_t* const array1, |
70 | const uint32_t* const array2, |
71 | int best_len_match, int max_limit) { |
72 | // Before 'expensive' linear match, check if the two arrays match at the |
73 | // current best length index. |
74 | if (array1[best_len_match] != array2[best_len_match]) return 0; |
75 | |
76 | return VP8LVectorMismatch(array1, array2, max_limit); |
77 | } |
78 | |
79 | // ----------------------------------------------------------------------------- |
80 | // VP8LBackwardRefs |
81 | |
82 | struct PixOrCopyBlock { |
83 | PixOrCopyBlock* next_; // next block (or NULL) |
84 | PixOrCopy* start_; // data start |
85 | int size_; // currently used size |
86 | }; |
87 | |
88 | extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); |
89 | void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs) { |
90 | assert(refs != NULL); |
91 | if (refs->tail_ != NULL) { |
92 | *refs->tail_ = refs->free_blocks_; // recycle all blocks at once |
93 | } |
94 | refs->free_blocks_ = refs->refs_; |
95 | refs->tail_ = &refs->refs_; |
96 | refs->last_block_ = NULL; |
97 | refs->refs_ = NULL; |
98 | } |
99 | |
100 | void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs) { |
101 | assert(refs != NULL); |
102 | VP8LClearBackwardRefs(refs); |
103 | while (refs->free_blocks_ != NULL) { |
104 | PixOrCopyBlock* const next = refs->free_blocks_->next_; |
105 | WebPSafeFree(refs->free_blocks_); |
106 | refs->free_blocks_ = next; |
107 | } |
108 | } |
109 | |
110 | // Swaps the content of two VP8LBackwardRefs. |
111 | static void BackwardRefsSwap(VP8LBackwardRefs* const refs1, |
112 | VP8LBackwardRefs* const refs2) { |
113 | const int point_to_refs1 = |
114 | (refs1->tail_ != NULL && refs1->tail_ == &refs1->refs_); |
115 | const int point_to_refs2 = |
116 | (refs2->tail_ != NULL && refs2->tail_ == &refs2->refs_); |
117 | const VP8LBackwardRefs tmp = *refs1; |
118 | *refs1 = *refs2; |
119 | *refs2 = tmp; |
120 | if (point_to_refs2) refs1->tail_ = &refs1->refs_; |
121 | if (point_to_refs1) refs2->tail_ = &refs2->refs_; |
122 | } |
123 | |
124 | void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size) { |
125 | assert(refs != NULL); |
126 | memset(refs, 0, sizeof(*refs)); |
127 | refs->tail_ = &refs->refs_; |
128 | refs->block_size_ = |
129 | (block_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : block_size; |
130 | } |
131 | |
132 | VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs) { |
133 | VP8LRefsCursor c; |
134 | c.cur_block_ = refs->refs_; |
135 | if (refs->refs_ != NULL) { |
136 | c.cur_pos = c.cur_block_->start_; |
137 | c.last_pos_ = c.cur_pos + c.cur_block_->size_; |
138 | } else { |
139 | c.cur_pos = NULL; |
140 | c.last_pos_ = NULL; |
141 | } |
142 | return c; |
143 | } |
144 | |
145 | void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c) { |
146 | PixOrCopyBlock* const b = c->cur_block_->next_; |
147 | c->cur_pos = (b == NULL) ? NULL : b->start_; |
148 | c->last_pos_ = (b == NULL) ? NULL : b->start_ + b->size_; |
149 | c->cur_block_ = b; |
150 | } |
151 | |
152 | // Create a new block, either from the free list or allocated |
153 | static PixOrCopyBlock* BackwardRefsNewBlock(VP8LBackwardRefs* const refs) { |
154 | PixOrCopyBlock* b = refs->free_blocks_; |
155 | if (b == NULL) { // allocate new memory chunk |
156 | const size_t total_size = |
157 | sizeof(*b) + refs->block_size_ * sizeof(*b->start_); |
158 | b = (PixOrCopyBlock*)WebPSafeMalloc(1ULL, total_size); |
159 | if (b == NULL) { |
160 | refs->error_ |= 1; |
161 | return NULL; |
162 | } |
163 | b->start_ = (PixOrCopy*)((uint8_t*)b + sizeof(*b)); // not always aligned |
164 | } else { // recycle from free-list |
165 | refs->free_blocks_ = b->next_; |
166 | } |
167 | *refs->tail_ = b; |
168 | refs->tail_ = &b->next_; |
169 | refs->last_block_ = b; |
170 | b->next_ = NULL; |
171 | b->size_ = 0; |
172 | return b; |
173 | } |
174 | |
175 | // Return 1 on success, 0 on error. |
176 | static int BackwardRefsClone(const VP8LBackwardRefs* const from, |
177 | VP8LBackwardRefs* const to) { |
178 | const PixOrCopyBlock* block_from = from->refs_; |
179 | VP8LClearBackwardRefs(to); |
180 | while (block_from != NULL) { |
181 | PixOrCopyBlock* const block_to = BackwardRefsNewBlock(to); |
182 | if (block_to == NULL) return 0; |
183 | memcpy(block_to->start_, block_from->start_, |
184 | block_from->size_ * sizeof(PixOrCopy)); |
185 | block_to->size_ = block_from->size_; |
186 | block_from = block_from->next_; |
187 | } |
188 | return 1; |
189 | } |
190 | |
191 | extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, |
192 | const PixOrCopy v); |
193 | void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, |
194 | const PixOrCopy v) { |
195 | PixOrCopyBlock* b = refs->last_block_; |
196 | if (b == NULL || b->size_ == refs->block_size_) { |
197 | b = BackwardRefsNewBlock(refs); |
198 | if (b == NULL) return; // refs->error_ is set |
199 | } |
200 | b->start_[b->size_++] = v; |
201 | } |
202 | |
203 | // ----------------------------------------------------------------------------- |
204 | // Hash chains |
205 | |
206 | int VP8LHashChainInit(VP8LHashChain* const p, int size) { |
207 | assert(p->size_ == 0); |
208 | assert(p->offset_length_ == NULL); |
209 | assert(size > 0); |
210 | p->offset_length_ = |
211 | (uint32_t*)WebPSafeMalloc(size, sizeof(*p->offset_length_)); |
212 | if (p->offset_length_ == NULL) return 0; |
213 | p->size_ = size; |
214 | |
215 | return 1; |
216 | } |
217 | |
218 | void VP8LHashChainClear(VP8LHashChain* const p) { |
219 | assert(p != NULL); |
220 | WebPSafeFree(p->offset_length_); |
221 | |
222 | p->size_ = 0; |
223 | p->offset_length_ = NULL; |
224 | } |
225 | |
226 | // ----------------------------------------------------------------------------- |
227 | |
228 | static const uint32_t kHashMultiplierHi = 0xc6a4a793u; |
229 | static const uint32_t kHashMultiplierLo = 0x5bd1e996u; |
230 | |
231 | static WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE |
232 | uint32_t GetPixPairHash64(const uint32_t* const argb) { |
233 | uint32_t key; |
234 | key = argb[1] * kHashMultiplierHi; |
235 | key += argb[0] * kHashMultiplierLo; |
236 | key = key >> (32 - HASH_BITS); |
237 | return key; |
238 | } |
239 | |
240 | // Returns the maximum number of hash chain lookups to do for a |
241 | // given compression quality. Return value in range [8, 86]. |
242 | static int GetMaxItersForQuality(int quality) { |
243 | return 8 + (quality * quality) / 128; |
244 | } |
245 | |
246 | static int GetWindowSizeForHashChain(int quality, int xsize) { |
247 | const int max_window_size = (quality > 75) ? WINDOW_SIZE |
248 | : (quality > 50) ? (xsize << 8) |
249 | : (quality > 25) ? (xsize << 6) |
250 | : (xsize << 4); |
251 | assert(xsize > 0); |
252 | return (max_window_size > WINDOW_SIZE) ? WINDOW_SIZE : max_window_size; |
253 | } |
254 | |
255 | static WEBP_INLINE int MaxFindCopyLength(int len) { |
256 | return (len < MAX_LENGTH) ? len : MAX_LENGTH; |
257 | } |
258 | |
259 | int VP8LHashChainFill(VP8LHashChain* const p, int quality, |
260 | const uint32_t* const argb, int xsize, int ysize, |
261 | int low_effort, const WebPPicture* const pic, |
262 | int percent_range, int* const percent) { |
263 | const int size = xsize * ysize; |
264 | const int iter_max = GetMaxItersForQuality(quality); |
265 | const uint32_t window_size = GetWindowSizeForHashChain(quality, xsize); |
266 | int remaining_percent = percent_range; |
267 | int percent_start = *percent; |
268 | int pos; |
269 | int argb_comp; |
270 | uint32_t base_position; |
271 | int32_t* hash_to_first_index; |
272 | // Temporarily use the p->offset_length_ as a hash chain. |
273 | int32_t* chain = (int32_t*)p->offset_length_; |
274 | assert(size > 0); |
275 | assert(p->size_ != 0); |
276 | assert(p->offset_length_ != NULL); |
277 | |
278 | if (size <= 2) { |
279 | p->offset_length_[0] = p->offset_length_[size - 1] = 0; |
280 | return 1; |
281 | } |
282 | |
283 | hash_to_first_index = |
284 | (int32_t*)WebPSafeMalloc(HASH_SIZE, sizeof(*hash_to_first_index)); |
285 | if (hash_to_first_index == NULL) { |
286 | return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY); |
287 | } |
288 | |
289 | percent_range = remaining_percent / 2; |
290 | remaining_percent -= percent_range; |
291 | |
292 | // Set the int32_t array to -1. |
293 | memset(hash_to_first_index, 0xff, HASH_SIZE * sizeof(*hash_to_first_index)); |
294 | // Fill the chain linking pixels with the same hash. |
295 | argb_comp = (argb[0] == argb[1]); |
296 | for (pos = 0; pos < size - 2;) { |
297 | uint32_t hash_code; |
298 | const int argb_comp_next = (argb[pos + 1] == argb[pos + 2]); |
299 | if (argb_comp && argb_comp_next) { |
300 | // Consecutive pixels with the same color will share the same hash. |
301 | // We therefore use a different hash: the color and its repetition |
302 | // length. |
303 | uint32_t tmp[2]; |
304 | uint32_t len = 1; |
305 | tmp[0] = argb[pos]; |
306 | // Figure out how far the pixels are the same. |
307 | // The last pixel has a different 64 bit hash, as its next pixel does |
308 | // not have the same color, so we just need to get to the last pixel equal |
309 | // to its follower. |
310 | while (pos + (int)len + 2 < size && argb[pos + len + 2] == argb[pos]) { |
311 | ++len; |
312 | } |
313 | if (len > MAX_LENGTH) { |
314 | // Skip the pixels that match for distance=1 and length>MAX_LENGTH |
315 | // because they are linked to their predecessor and we automatically |
316 | // check that in the main for loop below. Skipping means setting no |
317 | // predecessor in the chain, hence -1. |
318 | memset(chain + pos, 0xff, (len - MAX_LENGTH) * sizeof(*chain)); |
319 | pos += len - MAX_LENGTH; |
320 | len = MAX_LENGTH; |
321 | } |
322 | // Process the rest of the hash chain. |
323 | while (len) { |
324 | tmp[1] = len--; |
325 | hash_code = GetPixPairHash64(tmp); |
326 | chain[pos] = hash_to_first_index[hash_code]; |
327 | hash_to_first_index[hash_code] = pos++; |
328 | } |
329 | argb_comp = 0; |
330 | } else { |
331 | // Just move one pixel forward. |
332 | hash_code = GetPixPairHash64(argb + pos); |
333 | chain[pos] = hash_to_first_index[hash_code]; |
334 | hash_to_first_index[hash_code] = pos++; |
335 | argb_comp = argb_comp_next; |
336 | } |
337 | |
338 | if (!WebPReportProgress( |
339 | pic, percent_start + percent_range * pos / (size - 2), percent)) { |
340 | WebPSafeFree(hash_to_first_index); |
341 | return 0; |
342 | } |
343 | } |
344 | // Process the penultimate pixel. |
345 | chain[pos] = hash_to_first_index[GetPixPairHash64(argb + pos)]; |
346 | |
347 | WebPSafeFree(hash_to_first_index); |
348 | |
349 | percent_start += percent_range; |
350 | if (!WebPReportProgress(pic, percent_start, percent)) return 0; |
351 | percent_range = remaining_percent; |
352 | |
353 | // Find the best match interval at each pixel, defined by an offset to the |
354 | // pixel and a length. The right-most pixel cannot match anything to the right |
355 | // (hence a best length of 0) and the left-most pixel nothing to the left |
356 | // (hence an offset of 0). |
357 | assert(size > 2); |
358 | p->offset_length_[0] = p->offset_length_[size - 1] = 0; |
359 | for (base_position = size - 2; base_position > 0;) { |
360 | const int max_len = MaxFindCopyLength(size - 1 - base_position); |
361 | const uint32_t* const argb_start = argb + base_position; |
362 | int iter = iter_max; |
363 | int best_length = 0; |
364 | uint32_t best_distance = 0; |
365 | uint32_t best_argb; |
366 | const int min_pos = |
367 | (base_position > window_size) ? base_position - window_size : 0; |
368 | const int length_max = (max_len < 256) ? max_len : 256; |
369 | uint32_t max_base_position; |
370 | |
371 | pos = chain[base_position]; |
372 | if (!low_effort) { |
373 | int curr_length; |
374 | // Heuristic: use the comparison with the above line as an initialization. |
375 | if (base_position >= (uint32_t)xsize) { |
376 | curr_length = FindMatchLength(argb_start - xsize, argb_start, |
377 | best_length, max_len); |
378 | if (curr_length > best_length) { |
379 | best_length = curr_length; |
380 | best_distance = xsize; |
381 | } |
382 | --iter; |
383 | } |
384 | // Heuristic: compare to the previous pixel. |
385 | curr_length = |
386 | FindMatchLength(argb_start - 1, argb_start, best_length, max_len); |
387 | if (curr_length > best_length) { |
388 | best_length = curr_length; |
389 | best_distance = 1; |
390 | } |
391 | --iter; |
392 | // Skip the for loop if we already have the maximum. |
393 | if (best_length == MAX_LENGTH) pos = min_pos - 1; |
394 | } |
395 | best_argb = argb_start[best_length]; |
396 | |
397 | for (; pos >= min_pos && --iter; pos = chain[pos]) { |
398 | int curr_length; |
399 | assert(base_position > (uint32_t)pos); |
400 | |
401 | if (argb[pos + best_length] != best_argb) continue; |
402 | |
403 | curr_length = VP8LVectorMismatch(argb + pos, argb_start, max_len); |
404 | if (best_length < curr_length) { |
405 | best_length = curr_length; |
406 | best_distance = base_position - pos; |
407 | best_argb = argb_start[best_length]; |
408 | // Stop if we have reached a good enough length. |
409 | if (best_length >= length_max) break; |
410 | } |
411 | } |
412 | // We have the best match but in case the two intervals continue matching |
413 | // to the left, we have the best matches for the left-extended pixels. |
414 | max_base_position = base_position; |
415 | while (1) { |
416 | assert(best_length <= MAX_LENGTH); |
417 | assert(best_distance <= WINDOW_SIZE); |
418 | p->offset_length_[base_position] = |
419 | (best_distance << MAX_LENGTH_BITS) | (uint32_t)best_length; |
420 | --base_position; |
421 | // Stop if we don't have a match or if we are out of bounds. |
422 | if (best_distance == 0 || base_position == 0) break; |
423 | // Stop if we cannot extend the matching intervals to the left. |
424 | if (base_position < best_distance || |
425 | argb[base_position - best_distance] != argb[base_position]) { |
426 | break; |
427 | } |
428 | // Stop if we are matching at its limit because there could be a closer |
429 | // matching interval with the same maximum length. Then again, if the |
430 | // matching interval is as close as possible (best_distance == 1), we will |
431 | // never find anything better so let's continue. |
432 | if (best_length == MAX_LENGTH && best_distance != 1 && |
433 | base_position + MAX_LENGTH < max_base_position) { |
434 | break; |
435 | } |
436 | if (best_length < MAX_LENGTH) { |
437 | ++best_length; |
438 | max_base_position = base_position; |
439 | } |
440 | } |
441 | |
442 | if (!WebPReportProgress(pic, |
443 | percent_start + percent_range * |
444 | (size - 2 - base_position) / |
445 | (size - 2), |
446 | percent)) { |
447 | return 0; |
448 | } |
449 | } |
450 | |
451 | return WebPReportProgress(pic, percent_start + percent_range, percent); |
452 | } |
453 | |
454 | static WEBP_INLINE void AddSingleLiteral(uint32_t pixel, int use_color_cache, |
455 | VP8LColorCache* const hashers, |
456 | VP8LBackwardRefs* const refs) { |
457 | PixOrCopy v; |
458 | if (use_color_cache) { |
459 | const uint32_t key = VP8LColorCacheGetIndex(hashers, pixel); |
460 | if (VP8LColorCacheLookup(hashers, key) == pixel) { |
461 | v = PixOrCopyCreateCacheIdx(key); |
462 | } else { |
463 | v = PixOrCopyCreateLiteral(pixel); |
464 | VP8LColorCacheSet(hashers, key, pixel); |
465 | } |
466 | } else { |
467 | v = PixOrCopyCreateLiteral(pixel); |
468 | } |
469 | VP8LBackwardRefsCursorAdd(refs, v); |
470 | } |
471 | |
472 | static int BackwardReferencesRle(int xsize, int ysize, |
473 | const uint32_t* const argb, |
474 | int cache_bits, VP8LBackwardRefs* const refs) { |
475 | const int pix_count = xsize * ysize; |
476 | int i, k; |
477 | const int use_color_cache = (cache_bits > 0); |
478 | VP8LColorCache hashers; |
479 | |
480 | if (use_color_cache && !VP8LColorCacheInit(&hashers, cache_bits)) { |
481 | return 0; |
482 | } |
483 | VP8LClearBackwardRefs(refs); |
484 | // Add first pixel as literal. |
485 | AddSingleLiteral(argb[0], use_color_cache, &hashers, refs); |
486 | i = 1; |
487 | while (i < pix_count) { |
488 | const int max_len = MaxFindCopyLength(pix_count - i); |
489 | const int rle_len = FindMatchLength(argb + i, argb + i - 1, 0, max_len); |
490 | const int prev_row_len = (i < xsize) ? 0 : |
491 | FindMatchLength(argb + i, argb + i - xsize, 0, max_len); |
492 | if (rle_len >= prev_row_len && rle_len >= MIN_LENGTH) { |
493 | VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(1, rle_len)); |
494 | // We don't need to update the color cache here since it is always the |
495 | // same pixel being copied, and that does not change the color cache |
496 | // state. |
497 | i += rle_len; |
498 | } else if (prev_row_len >= MIN_LENGTH) { |
499 | VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(xsize, prev_row_len)); |
500 | if (use_color_cache) { |
501 | for (k = 0; k < prev_row_len; ++k) { |
502 | VP8LColorCacheInsert(&hashers, argb[i + k]); |
503 | } |
504 | } |
505 | i += prev_row_len; |
506 | } else { |
507 | AddSingleLiteral(argb[i], use_color_cache, &hashers, refs); |
508 | i++; |
509 | } |
510 | } |
511 | if (use_color_cache) VP8LColorCacheClear(&hashers); |
512 | return !refs->error_; |
513 | } |
514 | |
515 | static int BackwardReferencesLz77(int xsize, int ysize, |
516 | const uint32_t* const argb, int cache_bits, |
517 | const VP8LHashChain* const hash_chain, |
518 | VP8LBackwardRefs* const refs) { |
519 | int i; |
520 | int i_last_check = -1; |
521 | int ok = 0; |
522 | int cc_init = 0; |
523 | const int use_color_cache = (cache_bits > 0); |
524 | const int pix_count = xsize * ysize; |
525 | VP8LColorCache hashers; |
526 | |
527 | if (use_color_cache) { |
528 | cc_init = VP8LColorCacheInit(&hashers, cache_bits); |
529 | if (!cc_init) goto Error; |
530 | } |
531 | VP8LClearBackwardRefs(refs); |
532 | for (i = 0; i < pix_count;) { |
533 | // Alternative#1: Code the pixels starting at 'i' using backward reference. |
534 | int offset = 0; |
535 | int len = 0; |
536 | int j; |
537 | VP8LHashChainFindCopy(hash_chain, i, &offset, &len); |
538 | if (len >= MIN_LENGTH) { |
539 | const int len_ini = len; |
540 | int max_reach = 0; |
541 | const int j_max = |
542 | (i + len_ini >= pix_count) ? pix_count - 1 : i + len_ini; |
543 | // Only start from what we have not checked already. |
544 | i_last_check = (i > i_last_check) ? i : i_last_check; |
545 | // We know the best match for the current pixel but we try to find the |
546 | // best matches for the current pixel AND the next one combined. |
547 | // The naive method would use the intervals: |
548 | // [i,i+len) + [i+len, length of best match at i+len) |
549 | // while we check if we can use: |
550 | // [i,j) (where j<=i+len) + [j, length of best match at j) |
551 | for (j = i_last_check + 1; j <= j_max; ++j) { |
552 | const int len_j = VP8LHashChainFindLength(hash_chain, j); |
553 | const int reach = |
554 | j + (len_j >= MIN_LENGTH ? len_j : 1); // 1 for single literal. |
555 | if (reach > max_reach) { |
556 | len = j - i; |
557 | max_reach = reach; |
558 | if (max_reach >= pix_count) break; |
559 | } |
560 | } |
561 | } else { |
562 | len = 1; |
563 | } |
564 | // Go with literal or backward reference. |
565 | assert(len > 0); |
566 | if (len == 1) { |
567 | AddSingleLiteral(argb[i], use_color_cache, &hashers, refs); |
568 | } else { |
569 | VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len)); |
570 | if (use_color_cache) { |
571 | for (j = i; j < i + len; ++j) VP8LColorCacheInsert(&hashers, argb[j]); |
572 | } |
573 | } |
574 | i += len; |
575 | } |
576 | |
577 | ok = !refs->error_; |
578 | Error: |
579 | if (cc_init) VP8LColorCacheClear(&hashers); |
580 | return ok; |
581 | } |
582 | |
583 | // Compute an LZ77 by forcing matches to happen within a given distance cost. |
584 | // We therefore limit the algorithm to the lowest 32 values in the PlaneCode |
585 | // definition. |
586 | #define WINDOW_OFFSETS_SIZE_MAX 32 |
587 | static int BackwardReferencesLz77Box(int xsize, int ysize, |
588 | const uint32_t* const argb, int cache_bits, |
589 | const VP8LHashChain* const hash_chain_best, |
590 | VP8LHashChain* hash_chain, |
591 | VP8LBackwardRefs* const refs) { |
592 | int i; |
593 | const int pix_count = xsize * ysize; |
594 | uint16_t* counts; |
595 | int window_offsets[WINDOW_OFFSETS_SIZE_MAX] = {0}; |
596 | int window_offsets_new[WINDOW_OFFSETS_SIZE_MAX] = {0}; |
597 | int window_offsets_size = 0; |
598 | int window_offsets_new_size = 0; |
599 | uint16_t* const counts_ini = |
600 | (uint16_t*)WebPSafeMalloc(xsize * ysize, sizeof(*counts_ini)); |
601 | int best_offset_prev = -1, best_length_prev = -1; |
602 | if (counts_ini == NULL) return 0; |
603 | |
604 | // counts[i] counts how many times a pixel is repeated starting at position i. |
605 | i = pix_count - 2; |
606 | counts = counts_ini + i; |
607 | counts[1] = 1; |
608 | for (; i >= 0; --i, --counts) { |
609 | if (argb[i] == argb[i + 1]) { |
610 | // Max out the counts to MAX_LENGTH. |
611 | counts[0] = counts[1] + (counts[1] != MAX_LENGTH); |
612 | } else { |
613 | counts[0] = 1; |
614 | } |
615 | } |
616 | |
617 | // Figure out the window offsets around a pixel. They are stored in a |
618 | // spiraling order around the pixel as defined by VP8LDistanceToPlaneCode. |
619 | { |
620 | int x, y; |
621 | for (y = 0; y <= 6; ++y) { |
622 | for (x = -6; x <= 6; ++x) { |
623 | const int offset = y * xsize + x; |
624 | int plane_code; |
625 | // Ignore offsets that bring us after the pixel. |
626 | if (offset <= 0) continue; |
627 | plane_code = VP8LDistanceToPlaneCode(xsize, offset) - 1; |
628 | if (plane_code >= WINDOW_OFFSETS_SIZE_MAX) continue; |
629 | window_offsets[plane_code] = offset; |
630 | } |
631 | } |
632 | // For narrow images, not all plane codes are reached, so remove those. |
633 | for (i = 0; i < WINDOW_OFFSETS_SIZE_MAX; ++i) { |
634 | if (window_offsets[i] == 0) continue; |
635 | window_offsets[window_offsets_size++] = window_offsets[i]; |
636 | } |
637 | // Given a pixel P, find the offsets that reach pixels unreachable from P-1 |
638 | // with any of the offsets in window_offsets[]. |
639 | for (i = 0; i < window_offsets_size; ++i) { |
640 | int j; |
641 | int is_reachable = 0; |
642 | for (j = 0; j < window_offsets_size && !is_reachable; ++j) { |
643 | is_reachable |= (window_offsets[i] == window_offsets[j] + 1); |
644 | } |
645 | if (!is_reachable) { |
646 | window_offsets_new[window_offsets_new_size] = window_offsets[i]; |
647 | ++window_offsets_new_size; |
648 | } |
649 | } |
650 | } |
651 | |
652 | hash_chain->offset_length_[0] = 0; |
653 | for (i = 1; i < pix_count; ++i) { |
654 | int ind; |
655 | int best_length = VP8LHashChainFindLength(hash_chain_best, i); |
656 | int best_offset; |
657 | int do_compute = 1; |
658 | |
659 | if (best_length >= MAX_LENGTH) { |
660 | // Do not recompute the best match if we already have a maximal one in the |
661 | // window. |
662 | best_offset = VP8LHashChainFindOffset(hash_chain_best, i); |
663 | for (ind = 0; ind < window_offsets_size; ++ind) { |
664 | if (best_offset == window_offsets[ind]) { |
665 | do_compute = 0; |
666 | break; |
667 | } |
668 | } |
669 | } |
670 | if (do_compute) { |
671 | // Figure out if we should use the offset/length from the previous pixel |
672 | // as an initial guess and therefore only inspect the offsets in |
673 | // window_offsets_new[]. |
674 | const int use_prev = |
675 | (best_length_prev > 1) && (best_length_prev < MAX_LENGTH); |
676 | const int num_ind = |
677 | use_prev ? window_offsets_new_size : window_offsets_size; |
678 | best_length = use_prev ? best_length_prev - 1 : 0; |
679 | best_offset = use_prev ? best_offset_prev : 0; |
680 | // Find the longest match in a window around the pixel. |
681 | for (ind = 0; ind < num_ind; ++ind) { |
682 | int curr_length = 0; |
683 | int j = i; |
684 | int j_offset = |
685 | use_prev ? i - window_offsets_new[ind] : i - window_offsets[ind]; |
686 | if (j_offset < 0 || argb[j_offset] != argb[i]) continue; |
687 | // The longest match is the sum of how many times each pixel is |
688 | // repeated. |
689 | do { |
690 | const int counts_j_offset = counts_ini[j_offset]; |
691 | const int counts_j = counts_ini[j]; |
692 | if (counts_j_offset != counts_j) { |
693 | curr_length += |
694 | (counts_j_offset < counts_j) ? counts_j_offset : counts_j; |
695 | break; |
696 | } |
697 | // The same color is repeated counts_pos times at j_offset and j. |
698 | curr_length += counts_j_offset; |
699 | j_offset += counts_j_offset; |
700 | j += counts_j_offset; |
701 | } while (curr_length <= MAX_LENGTH && j < pix_count && |
702 | argb[j_offset] == argb[j]); |
703 | if (best_length < curr_length) { |
704 | best_offset = |
705 | use_prev ? window_offsets_new[ind] : window_offsets[ind]; |
706 | if (curr_length >= MAX_LENGTH) { |
707 | best_length = MAX_LENGTH; |
708 | break; |
709 | } else { |
710 | best_length = curr_length; |
711 | } |
712 | } |
713 | } |
714 | } |
715 | |
716 | assert(i + best_length <= pix_count); |
717 | assert(best_length <= MAX_LENGTH); |
718 | if (best_length <= MIN_LENGTH) { |
719 | hash_chain->offset_length_[i] = 0; |
720 | best_offset_prev = 0; |
721 | best_length_prev = 0; |
722 | } else { |
723 | hash_chain->offset_length_[i] = |
724 | (best_offset << MAX_LENGTH_BITS) | (uint32_t)best_length; |
725 | best_offset_prev = best_offset; |
726 | best_length_prev = best_length; |
727 | } |
728 | } |
729 | hash_chain->offset_length_[0] = 0; |
730 | WebPSafeFree(counts_ini); |
731 | |
732 | return BackwardReferencesLz77(xsize, ysize, argb, cache_bits, hash_chain, |
733 | refs); |
734 | } |
735 | |
736 | // ----------------------------------------------------------------------------- |
737 | |
738 | static void BackwardReferences2DLocality(int xsize, |
739 | const VP8LBackwardRefs* const refs) { |
740 | VP8LRefsCursor c = VP8LRefsCursorInit(refs); |
741 | while (VP8LRefsCursorOk(&c)) { |
742 | if (PixOrCopyIsCopy(c.cur_pos)) { |
743 | const int dist = c.cur_pos->argb_or_distance; |
744 | const int transformed_dist = VP8LDistanceToPlaneCode(xsize, dist); |
745 | c.cur_pos->argb_or_distance = transformed_dist; |
746 | } |
747 | VP8LRefsCursorNext(&c); |
748 | } |
749 | } |
750 | |
751 | // Evaluate optimal cache bits for the local color cache. |
752 | // The input *best_cache_bits sets the maximum cache bits to use (passing 0 |
753 | // implies disabling the local color cache). The local color cache is also |
754 | // disabled for the lower (<= 25) quality. |
755 | // Returns 0 in case of memory error. |
756 | static int CalculateBestCacheSize(const uint32_t* argb, int quality, |
757 | const VP8LBackwardRefs* const refs, |
758 | int* const best_cache_bits) { |
759 | int i; |
760 | const int cache_bits_max = (quality <= 25) ? 0 : *best_cache_bits; |
761 | float entropy_min = MAX_ENTROPY; |
762 | int cc_init[MAX_COLOR_CACHE_BITS + 1] = { 0 }; |
763 | VP8LColorCache hashers[MAX_COLOR_CACHE_BITS + 1]; |
764 | VP8LRefsCursor c = VP8LRefsCursorInit(refs); |
765 | VP8LHistogram* histos[MAX_COLOR_CACHE_BITS + 1] = { NULL }; |
766 | int ok = 0; |
767 | |
768 | assert(cache_bits_max >= 0 && cache_bits_max <= MAX_COLOR_CACHE_BITS); |
769 | |
770 | if (cache_bits_max == 0) { |
771 | *best_cache_bits = 0; |
772 | // Local color cache is disabled. |
773 | return 1; |
774 | } |
775 | |
776 | // Allocate data. |
777 | for (i = 0; i <= cache_bits_max; ++i) { |
778 | histos[i] = VP8LAllocateHistogram(i); |
779 | if (histos[i] == NULL) goto Error; |
780 | VP8LHistogramInit(histos[i], i, /*init_arrays=*/ 1); |
781 | if (i == 0) continue; |
782 | cc_init[i] = VP8LColorCacheInit(&hashers[i], i); |
783 | if (!cc_init[i]) goto Error; |
784 | } |
785 | |
786 | // Find the cache_bits giving the lowest entropy. The search is done in a |
787 | // brute-force way as the function (entropy w.r.t cache_bits) can be |
788 | // anything in practice. |
789 | while (VP8LRefsCursorOk(&c)) { |
790 | const PixOrCopy* const v = c.cur_pos; |
791 | if (PixOrCopyIsLiteral(v)) { |
792 | const uint32_t pix = *argb++; |
793 | const uint32_t a = (pix >> 24) & 0xff; |
794 | const uint32_t r = (pix >> 16) & 0xff; |
795 | const uint32_t g = (pix >> 8) & 0xff; |
796 | const uint32_t b = (pix >> 0) & 0xff; |
797 | // The keys of the caches can be derived from the longest one. |
798 | int key = VP8LHashPix(pix, 32 - cache_bits_max); |
799 | // Do not use the color cache for cache_bits = 0. |
800 | ++histos[0]->blue_[b]; |
801 | ++histos[0]->literal_[g]; |
802 | ++histos[0]->red_[r]; |
803 | ++histos[0]->alpha_[a]; |
804 | // Deal with cache_bits > 0. |
805 | for (i = cache_bits_max; i >= 1; --i, key >>= 1) { |
806 | if (VP8LColorCacheLookup(&hashers[i], key) == pix) { |
807 | ++histos[i]->literal_[NUM_LITERAL_CODES + NUM_LENGTH_CODES + key]; |
808 | } else { |
809 | VP8LColorCacheSet(&hashers[i], key, pix); |
810 | ++histos[i]->blue_[b]; |
811 | ++histos[i]->literal_[g]; |
812 | ++histos[i]->red_[r]; |
813 | ++histos[i]->alpha_[a]; |
814 | } |
815 | } |
816 | } else { |
817 | int code, , ; |
818 | // We should compute the contribution of the (distance,length) |
819 | // histograms but those are the same independently from the cache size. |
820 | // As those constant contributions are in the end added to the other |
821 | // histogram contributions, we can ignore them, except for the length |
822 | // prefix that is part of the literal_ histogram. |
823 | int len = PixOrCopyLength(v); |
824 | uint32_t argb_prev = *argb ^ 0xffffffffu; |
825 | VP8LPrefixEncode(len, &code, &extra_bits, &extra_bits_value); |
826 | for (i = 0; i <= cache_bits_max; ++i) { |
827 | ++histos[i]->literal_[NUM_LITERAL_CODES + code]; |
828 | } |
829 | // Update the color caches. |
830 | do { |
831 | if (*argb != argb_prev) { |
832 | // Efficiency: insert only if the color changes. |
833 | int key = VP8LHashPix(*argb, 32 - cache_bits_max); |
834 | for (i = cache_bits_max; i >= 1; --i, key >>= 1) { |
835 | hashers[i].colors_[key] = *argb; |
836 | } |
837 | argb_prev = *argb; |
838 | } |
839 | argb++; |
840 | } while (--len != 0); |
841 | } |
842 | VP8LRefsCursorNext(&c); |
843 | } |
844 | |
845 | for (i = 0; i <= cache_bits_max; ++i) { |
846 | const float entropy = VP8LHistogramEstimateBits(histos[i]); |
847 | if (i == 0 || entropy < entropy_min) { |
848 | entropy_min = entropy; |
849 | *best_cache_bits = i; |
850 | } |
851 | } |
852 | ok = 1; |
853 | Error: |
854 | for (i = 0; i <= cache_bits_max; ++i) { |
855 | if (cc_init[i]) VP8LColorCacheClear(&hashers[i]); |
856 | VP8LFreeHistogram(histos[i]); |
857 | } |
858 | return ok; |
859 | } |
860 | |
861 | // Update (in-place) backward references for specified cache_bits. |
862 | static int BackwardRefsWithLocalCache(const uint32_t* const argb, |
863 | int cache_bits, |
864 | VP8LBackwardRefs* const refs) { |
865 | int pixel_index = 0; |
866 | VP8LColorCache hashers; |
867 | VP8LRefsCursor c = VP8LRefsCursorInit(refs); |
868 | if (!VP8LColorCacheInit(&hashers, cache_bits)) return 0; |
869 | |
870 | while (VP8LRefsCursorOk(&c)) { |
871 | PixOrCopy* const v = c.cur_pos; |
872 | if (PixOrCopyIsLiteral(v)) { |
873 | const uint32_t argb_literal = v->argb_or_distance; |
874 | const int ix = VP8LColorCacheContains(&hashers, argb_literal); |
875 | if (ix >= 0) { |
876 | // hashers contains argb_literal |
877 | *v = PixOrCopyCreateCacheIdx(ix); |
878 | } else { |
879 | VP8LColorCacheInsert(&hashers, argb_literal); |
880 | } |
881 | ++pixel_index; |
882 | } else { |
883 | // refs was created without local cache, so it can not have cache indexes. |
884 | int k; |
885 | assert(PixOrCopyIsCopy(v)); |
886 | for (k = 0; k < v->len; ++k) { |
887 | VP8LColorCacheInsert(&hashers, argb[pixel_index++]); |
888 | } |
889 | } |
890 | VP8LRefsCursorNext(&c); |
891 | } |
892 | VP8LColorCacheClear(&hashers); |
893 | return 1; |
894 | } |
895 | |
896 | static VP8LBackwardRefs* GetBackwardReferencesLowEffort( |
897 | int width, int height, const uint32_t* const argb, |
898 | int* const cache_bits, const VP8LHashChain* const hash_chain, |
899 | VP8LBackwardRefs* const refs_lz77) { |
900 | *cache_bits = 0; |
901 | if (!BackwardReferencesLz77(width, height, argb, 0, hash_chain, refs_lz77)) { |
902 | return NULL; |
903 | } |
904 | BackwardReferences2DLocality(width, refs_lz77); |
905 | return refs_lz77; |
906 | } |
907 | |
908 | extern int VP8LBackwardReferencesTraceBackwards( |
909 | int xsize, int ysize, const uint32_t* const argb, int cache_bits, |
910 | const VP8LHashChain* const hash_chain, |
911 | const VP8LBackwardRefs* const refs_src, VP8LBackwardRefs* const refs_dst); |
912 | static int GetBackwardReferences(int width, int height, |
913 | const uint32_t* const argb, int quality, |
914 | int lz77_types_to_try, int cache_bits_max, |
915 | int do_no_cache, |
916 | const VP8LHashChain* const hash_chain, |
917 | VP8LBackwardRefs* const refs, |
918 | int* const cache_bits_best) { |
919 | VP8LHistogram* histo = NULL; |
920 | int i, lz77_type; |
921 | // Index 0 is for a color cache, index 1 for no cache (if needed). |
922 | int lz77_types_best[2] = {0, 0}; |
923 | float bit_costs_best[2] = {FLT_MAX, FLT_MAX}; |
924 | VP8LHashChain hash_chain_box; |
925 | VP8LBackwardRefs* const refs_tmp = &refs[do_no_cache ? 2 : 1]; |
926 | int status = 0; |
927 | memset(&hash_chain_box, 0, sizeof(hash_chain_box)); |
928 | |
929 | histo = VP8LAllocateHistogram(MAX_COLOR_CACHE_BITS); |
930 | if (histo == NULL) goto Error; |
931 | |
932 | for (lz77_type = 1; lz77_types_to_try; |
933 | lz77_types_to_try &= ~lz77_type, lz77_type <<= 1) { |
934 | int res = 0; |
935 | float bit_cost = 0.f; |
936 | if ((lz77_types_to_try & lz77_type) == 0) continue; |
937 | switch (lz77_type) { |
938 | case kLZ77RLE: |
939 | res = BackwardReferencesRle(width, height, argb, 0, refs_tmp); |
940 | break; |
941 | case kLZ77Standard: |
942 | // Compute LZ77 with no cache (0 bits), as the ideal LZ77 with a color |
943 | // cache is not that different in practice. |
944 | res = BackwardReferencesLz77(width, height, argb, 0, hash_chain, |
945 | refs_tmp); |
946 | break; |
947 | case kLZ77Box: |
948 | if (!VP8LHashChainInit(&hash_chain_box, width * height)) goto Error; |
949 | res = BackwardReferencesLz77Box(width, height, argb, 0, hash_chain, |
950 | &hash_chain_box, refs_tmp); |
951 | break; |
952 | default: |
953 | assert(0); |
954 | } |
955 | if (!res) goto Error; |
956 | |
957 | // Start with the no color cache case. |
958 | for (i = 1; i >= 0; --i) { |
959 | int cache_bits = (i == 1) ? 0 : cache_bits_max; |
960 | |
961 | if (i == 1 && !do_no_cache) continue; |
962 | |
963 | if (i == 0) { |
964 | // Try with a color cache. |
965 | if (!CalculateBestCacheSize(argb, quality, refs_tmp, &cache_bits)) { |
966 | goto Error; |
967 | } |
968 | if (cache_bits > 0) { |
969 | if (!BackwardRefsWithLocalCache(argb, cache_bits, refs_tmp)) { |
970 | goto Error; |
971 | } |
972 | } |
973 | } |
974 | |
975 | if (i == 0 && do_no_cache && cache_bits == 0) { |
976 | // No need to re-compute bit_cost as it was computed at i == 1. |
977 | } else { |
978 | VP8LHistogramCreate(histo, refs_tmp, cache_bits); |
979 | bit_cost = VP8LHistogramEstimateBits(histo); |
980 | } |
981 | |
982 | if (bit_cost < bit_costs_best[i]) { |
983 | if (i == 1) { |
984 | // Do not swap as the full cache analysis would have the wrong |
985 | // VP8LBackwardRefs to start with. |
986 | if (!BackwardRefsClone(refs_tmp, &refs[1])) goto Error; |
987 | } else { |
988 | BackwardRefsSwap(refs_tmp, &refs[0]); |
989 | } |
990 | bit_costs_best[i] = bit_cost; |
991 | lz77_types_best[i] = lz77_type; |
992 | if (i == 0) *cache_bits_best = cache_bits; |
993 | } |
994 | } |
995 | } |
996 | assert(lz77_types_best[0] > 0); |
997 | assert(!do_no_cache || lz77_types_best[1] > 0); |
998 | |
999 | // Improve on simple LZ77 but only for high quality (TraceBackwards is |
1000 | // costly). |
1001 | for (i = 1; i >= 0; --i) { |
1002 | if (i == 1 && !do_no_cache) continue; |
1003 | if ((lz77_types_best[i] == kLZ77Standard || |
1004 | lz77_types_best[i] == kLZ77Box) && |
1005 | quality >= 25) { |
1006 | const VP8LHashChain* const hash_chain_tmp = |
1007 | (lz77_types_best[i] == kLZ77Standard) ? hash_chain : &hash_chain_box; |
1008 | const int cache_bits = (i == 1) ? 0 : *cache_bits_best; |
1009 | float bit_cost_trace; |
1010 | if (!VP8LBackwardReferencesTraceBackwards(width, height, argb, cache_bits, |
1011 | hash_chain_tmp, &refs[i], |
1012 | refs_tmp)) { |
1013 | goto Error; |
1014 | } |
1015 | VP8LHistogramCreate(histo, refs_tmp, cache_bits); |
1016 | bit_cost_trace = VP8LHistogramEstimateBits(histo); |
1017 | if (bit_cost_trace < bit_costs_best[i]) { |
1018 | BackwardRefsSwap(refs_tmp, &refs[i]); |
1019 | } |
1020 | } |
1021 | |
1022 | BackwardReferences2DLocality(width, &refs[i]); |
1023 | |
1024 | if (i == 1 && lz77_types_best[0] == lz77_types_best[1] && |
1025 | *cache_bits_best == 0) { |
1026 | // If the best cache size is 0 and we have the same best LZ77, just copy |
1027 | // the data over and stop here. |
1028 | if (!BackwardRefsClone(&refs[1], &refs[0])) goto Error; |
1029 | break; |
1030 | } |
1031 | } |
1032 | status = 1; |
1033 | |
1034 | Error: |
1035 | VP8LHashChainClear(&hash_chain_box); |
1036 | VP8LFreeHistogram(histo); |
1037 | return status; |
1038 | } |
1039 | |
1040 | int VP8LGetBackwardReferences( |
1041 | int width, int height, const uint32_t* const argb, int quality, |
1042 | int low_effort, int lz77_types_to_try, int cache_bits_max, int do_no_cache, |
1043 | const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs, |
1044 | int* const cache_bits_best, const WebPPicture* const pic, int percent_range, |
1045 | int* const percent) { |
1046 | if (low_effort) { |
1047 | VP8LBackwardRefs* refs_best; |
1048 | *cache_bits_best = cache_bits_max; |
1049 | refs_best = GetBackwardReferencesLowEffort( |
1050 | width, height, argb, cache_bits_best, hash_chain, refs); |
1051 | if (refs_best == NULL) { |
1052 | return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY); |
1053 | } |
1054 | // Set it in first position. |
1055 | BackwardRefsSwap(refs_best, &refs[0]); |
1056 | } else { |
1057 | if (!GetBackwardReferences(width, height, argb, quality, lz77_types_to_try, |
1058 | cache_bits_max, do_no_cache, hash_chain, refs, |
1059 | cache_bits_best)) { |
1060 | return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY); |
1061 | } |
1062 | } |
1063 | |
1064 | return WebPReportProgress(pic, *percent + percent_range, percent); |
1065 | } |
1066 | |