| OLD | NEW |
|---|
| (Empty) |
| 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 <assert.h> | |
| 14 #include <math.h> | |
| 15 | |
| 16 #include "./backward_references.h" | |
| 17 #include "./histogram.h" | |
| 18 #include "../dsp/lossless.h" | |
| 19 #include "../dsp/dsp.h" | |
| 20 #include "../utils/color_cache.h" | |
| 21 #include "../utils/utils.h" | |
| 22 | |
| 23 #define VALUES_IN_BYTE 256 | |
| 24 | |
| 25 #define MIN_BLOCK_SIZE 256 // minimum block size for backward references | |
| 26 | |
| 27 #define MAX_ENTROPY (1e30f) | |
| 28 | |
| 29 // 1M window (4M bytes) minus 120 special codes for short distances. | |
| 30 #define WINDOW_SIZE_BITS 20 | |
| 31 #define WINDOW_SIZE ((1 << WINDOW_SIZE_BITS) - 120) | |
| 32 | |
| 33 // Bounds for the match length. | |
| 34 #define MIN_LENGTH 2 | |
| 35 // If you change this, you need MAX_LENGTH_BITS + WINDOW_SIZE_BITS <= 32 as it | |
| 36 // is used in VP8LHashChain. | |
| 37 #define MAX_LENGTH_BITS 12 | |
| 38 // We want the max value to be attainable and stored in MAX_LENGTH_BITS bits. | |
| 39 #define MAX_LENGTH ((1 << MAX_LENGTH_BITS) - 1) | |
| 40 #if MAX_LENGTH_BITS + WINDOW_SIZE_BITS > 32 | |
| 41 #error "MAX_LENGTH_BITS + WINDOW_SIZE_BITS > 32" | |
| 42 #endif | |
| 43 | |
| 44 // ----------------------------------------------------------------------------- | |
| 45 | |
| 46 static const uint8_t plane_to_code_lut[128] = { | |
| 47 96, 73, 55, 39, 23, 13, 5, 1, 255, 255, 255, 255, 255, 255, 255, 255, | |
| 48 101, 78, 58, 42, 26, 16, 8, 2, 0, 3, 9, 17, 27, 43, 59, 79, | |
| 49 102, 86, 62, 46, 32, 20, 10, 6, 4, 7, 11, 21, 33, 47, 63, 87, | |
| 50 105, 90, 70, 52, 37, 28, 18, 14, 12, 15, 19, 29, 38, 53, 71, 91, | |
| 51 110, 99, 82, 66, 48, 35, 30, 24, 22, 25, 31, 36, 49, 67, 83, 100, | |
| 52 115, 108, 94, 76, 64, 50, 44, 40, 34, 41, 45, 51, 65, 77, 95, 109, | |
| 53 118, 113, 103, 92, 80, 68, 60, 56, 54, 57, 61, 69, 81, 93, 104, 114, | |
| 54 119, 116, 111, 106, 97, 88, 84, 74, 72, 75, 85, 89, 98, 107, 112, 117 | |
| 55 }; | |
| 56 | |
| 57 static int DistanceToPlaneCode(int xsize, int dist) { | |
| 58 const int yoffset = dist / xsize; | |
| 59 const int xoffset = dist - yoffset * xsize; | |
| 60 if (xoffset <= 8 && yoffset < 8) { | |
| 61 return plane_to_code_lut[yoffset * 16 + 8 - xoffset] + 1; | |
| 62 } else if (xoffset > xsize - 8 && yoffset < 7) { | |
| 63 return plane_to_code_lut[(yoffset + 1) * 16 + 8 + (xsize - xoffset)] + 1; | |
| 64 } | |
| 65 return dist + 120; | |
| 66 } | |
| 67 | |
| 68 // Returns the exact index where array1 and array2 are different. For an index | |
| 69 // inferior or equal to best_len_match, the return value just has to be strictly | |
| 70 // inferior to best_len_match. The current behavior is to return 0 if this index | |
| 71 // is best_len_match, and the index itself otherwise. | |
| 72 // If no two elements are the same, it returns max_limit. | |
| 73 static WEBP_INLINE int FindMatchLength(const uint32_t* const array1, | |
| 74 const uint32_t* const array2, | |
| 75 int best_len_match, int max_limit) { | |
| 76 // Before 'expensive' linear match, check if the two arrays match at the | |
| 77 // current best length index. | |
| 78 if (array1[best_len_match] != array2[best_len_match]) return 0; | |
| 79 | |
| 80 return VP8LVectorMismatch(array1, array2, max_limit); | |
| 81 } | |
| 82 | |
| 83 // ----------------------------------------------------------------------------- | |
| 84 // VP8LBackwardRefs | |
| 85 | |
| 86 struct PixOrCopyBlock { | |
| 87 PixOrCopyBlock* next_; // next block (or NULL) | |
| 88 PixOrCopy* start_; // data start | |
| 89 int size_; // currently used size | |
| 90 }; | |
| 91 | |
| 92 static void ClearBackwardRefs(VP8LBackwardRefs* const refs) { | |
| 93 assert(refs != NULL); | |
| 94 if (refs->tail_ != NULL) { | |
| 95 *refs->tail_ = refs->free_blocks_; // recycle all blocks at once | |
| 96 } | |
| 97 refs->free_blocks_ = refs->refs_; | |
| 98 refs->tail_ = &refs->refs_; | |
| 99 refs->last_block_ = NULL; | |
| 100 refs->refs_ = NULL; | |
| 101 } | |
| 102 | |
| 103 void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs) { | |
| 104 assert(refs != NULL); | |
| 105 ClearBackwardRefs(refs); | |
| 106 while (refs->free_blocks_ != NULL) { | |
| 107 PixOrCopyBlock* const next = refs->free_blocks_->next_; | |
| 108 WebPSafeFree(refs->free_blocks_); | |
| 109 refs->free_blocks_ = next; | |
| 110 } | |
| 111 } | |
| 112 | |
| 113 void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size) { | |
| 114 assert(refs != NULL); | |
| 115 memset(refs, 0, sizeof(*refs)); | |
| 116 refs->tail_ = &refs->refs_; | |
| 117 refs->block_size_ = | |
| 118 (block_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : block_size; | |
| 119 } | |
| 120 | |
| 121 VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs) { | |
| 122 VP8LRefsCursor c; | |
| 123 c.cur_block_ = refs->refs_; | |
| 124 if (refs->refs_ != NULL) { | |
| 125 c.cur_pos = c.cur_block_->start_; | |
| 126 c.last_pos_ = c.cur_pos + c.cur_block_->size_; | |
| 127 } else { | |
| 128 c.cur_pos = NULL; | |
| 129 c.last_pos_ = NULL; | |
| 130 } | |
| 131 return c; | |
| 132 } | |
| 133 | |
| 134 void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c) { | |
| 135 PixOrCopyBlock* const b = c->cur_block_->next_; | |
| 136 c->cur_pos = (b == NULL) ? NULL : b->start_; | |
| 137 c->last_pos_ = (b == NULL) ? NULL : b->start_ + b->size_; | |
| 138 c->cur_block_ = b; | |
| 139 } | |
| 140 | |
| 141 // Create a new block, either from the free list or allocated | |
| 142 static PixOrCopyBlock* BackwardRefsNewBlock(VP8LBackwardRefs* const refs) { | |
| 143 PixOrCopyBlock* b = refs->free_blocks_; | |
| 144 if (b == NULL) { // allocate new memory chunk | |
| 145 const size_t total_size = | |
| 146 sizeof(*b) + refs->block_size_ * sizeof(*b->start_); | |
| 147 b = (PixOrCopyBlock*)WebPSafeMalloc(1ULL, total_size); | |
| 148 if (b == NULL) { | |
| 149 refs->error_ |= 1; | |
| 150 return NULL; | |
| 151 } | |
| 152 b->start_ = (PixOrCopy*)((uint8_t*)b + sizeof(*b)); // not always aligned | |
| 153 } else { // recycle from free-list | |
| 154 refs->free_blocks_ = b->next_; | |
| 155 } | |
| 156 *refs->tail_ = b; | |
| 157 refs->tail_ = &b->next_; | |
| 158 refs->last_block_ = b; | |
| 159 b->next_ = NULL; | |
| 160 b->size_ = 0; | |
| 161 return b; | |
| 162 } | |
| 163 | |
| 164 static WEBP_INLINE void BackwardRefsCursorAdd(VP8LBackwardRefs* const refs, | |
| 165 const PixOrCopy v) { | |
| 166 PixOrCopyBlock* b = refs->last_block_; | |
| 167 if (b == NULL || b->size_ == refs->block_size_) { | |
| 168 b = BackwardRefsNewBlock(refs); | |
| 169 if (b == NULL) return; // refs->error_ is set | |
| 170 } | |
| 171 b->start_[b->size_++] = v; | |
| 172 } | |
| 173 | |
| 174 int VP8LBackwardRefsCopy(const VP8LBackwardRefs* const src, | |
| 175 VP8LBackwardRefs* const dst) { | |
| 176 const PixOrCopyBlock* b = src->refs_; | |
| 177 ClearBackwardRefs(dst); | |
| 178 assert(src->block_size_ == dst->block_size_); | |
| 179 while (b != NULL) { | |
| 180 PixOrCopyBlock* const new_b = BackwardRefsNewBlock(dst); | |
| 181 if (new_b == NULL) return 0; // dst->error_ is set | |
| 182 memcpy(new_b->start_, b->start_, b->size_ * sizeof(*b->start_)); | |
| 183 new_b->size_ = b->size_; | |
| 184 b = b->next_; | |
| 185 } | |
| 186 return 1; | |
| 187 } | |
| 188 | |
| 189 // ----------------------------------------------------------------------------- | |
| 190 // Hash chains | |
| 191 | |
| 192 int VP8LHashChainInit(VP8LHashChain* const p, int size) { | |
| 193 assert(p->size_ == 0); | |
| 194 assert(p->offset_length_ == NULL); | |
| 195 assert(size > 0); | |
| 196 p->offset_length_ = | |
| 197 (uint32_t*)WebPSafeMalloc(size, sizeof(*p->offset_length_)); | |
| 198 if (p->offset_length_ == NULL) return 0; | |
| 199 p->size_ = size; | |
| 200 | |
| 201 return 1; | |
| 202 } | |
| 203 | |
| 204 void VP8LHashChainClear(VP8LHashChain* const p) { | |
| 205 assert(p != NULL); | |
| 206 WebPSafeFree(p->offset_length_); | |
| 207 | |
| 208 p->size_ = 0; | |
| 209 p->offset_length_ = NULL; | |
| 210 } | |
| 211 | |
| 212 // ----------------------------------------------------------------------------- | |
| 213 | |
| 214 #define HASH_MULTIPLIER_HI (0xc6a4a793U) | |
| 215 #define HASH_MULTIPLIER_LO (0x5bd1e996U) | |
| 216 | |
| 217 static WEBP_INLINE uint32_t GetPixPairHash64(const uint32_t* const argb) { | |
| 218 uint32_t key; | |
| 219 key = argb[1] * HASH_MULTIPLIER_HI; | |
| 220 key += argb[0] * HASH_MULTIPLIER_LO; | |
| 221 key = key >> (32 - HASH_BITS); | |
| 222 return key; | |
| 223 } | |
| 224 | |
| 225 // Returns the maximum number of hash chain lookups to do for a | |
| 226 // given compression quality. Return value in range [8, 86]. | |
| 227 static int GetMaxItersForQuality(int quality) { | |
| 228 return 8 + (quality * quality) / 128; | |
| 229 } | |
| 230 | |
| 231 static int GetWindowSizeForHashChain(int quality, int xsize) { | |
| 232 const int max_window_size = (quality > 75) ? WINDOW_SIZE | |
| 233 : (quality > 50) ? (xsize << 8) | |
| 234 : (quality > 25) ? (xsize << 6) | |
| 235 : (xsize << 4); | |
| 236 assert(xsize > 0); | |
| 237 return (max_window_size > WINDOW_SIZE) ? WINDOW_SIZE : max_window_size; | |
| 238 } | |
| 239 | |
| 240 static WEBP_INLINE int MaxFindCopyLength(int len) { | |
| 241 return (len < MAX_LENGTH) ? len : MAX_LENGTH; | |
| 242 } | |
| 243 | |
| 244 int VP8LHashChainFill(VP8LHashChain* const p, int quality, | |
| 245 const uint32_t* const argb, int xsize, int ysize) { | |
| 246 const int size = xsize * ysize; | |
| 247 const int iter_max = GetMaxItersForQuality(quality); | |
| 248 const int iter_min = iter_max - quality / 10; | |
| 249 const uint32_t window_size = GetWindowSizeForHashChain(quality, xsize); | |
| 250 int pos; | |
| 251 uint32_t base_position; | |
| 252 int32_t* hash_to_first_index; | |
| 253 // Temporarily use the p->offset_length_ as a hash chain. | |
| 254 int32_t* chain = (int32_t*)p->offset_length_; | |
| 255 assert(p->size_ != 0); | |
| 256 assert(p->offset_length_ != NULL); | |
| 257 | |
| 258 hash_to_first_index = | |
| 259 (int32_t*)WebPSafeMalloc(HASH_SIZE, sizeof(*hash_to_first_index)); | |
| 260 if (hash_to_first_index == NULL) return 0; | |
| 261 | |
| 262 // Set the int32_t array to -1. | |
| 263 memset(hash_to_first_index, 0xff, HASH_SIZE * sizeof(*hash_to_first_index)); | |
| 264 // Fill the chain linking pixels with the same hash. | |
| 265 for (pos = 0; pos < size - 1; ++pos) { | |
| 266 const uint32_t hash_code = GetPixPairHash64(argb + pos); | |
| 267 chain[pos] = hash_to_first_index[hash_code]; | |
| 268 hash_to_first_index[hash_code] = pos; | |
| 269 } | |
| 270 WebPSafeFree(hash_to_first_index); | |
| 271 | |
| 272 // Find the best match interval at each pixel, defined by an offset to the | |
| 273 // pixel and a length. The right-most pixel cannot match anything to the right | |
| 274 // (hence a best length of 0) and the left-most pixel nothing to the left | |
| 275 // (hence an offset of 0). | |
| 276 p->offset_length_[0] = p->offset_length_[size - 1] = 0; | |
| 277 for (base_position = size - 2 < 0 ? 0 : size - 2; base_position > 0;) { | |
| 278 const int max_len = MaxFindCopyLength(size - 1 - base_position); | |
| 279 const uint32_t* const argb_start = argb + base_position; | |
| 280 int iter = iter_max; | |
| 281 int best_length = 0; | |
| 282 uint32_t best_distance = 0; | |
| 283 const int min_pos = | |
| 284 (base_position > window_size) ? base_position - window_size : 0; | |
| 285 const int length_max = (max_len < 256) ? max_len : 256; | |
| 286 uint32_t max_base_position; | |
| 287 | |
| 288 for (pos = chain[base_position]; pos >= min_pos; pos = chain[pos]) { | |
| 289 int curr_length; | |
| 290 if (--iter < 0) { | |
| 291 break; | |
| 292 } | |
| 293 assert(base_position > (uint32_t)pos); | |
| 294 | |
| 295 curr_length = | |
| 296 FindMatchLength(argb + pos, argb_start, best_length, max_len); | |
| 297 if (best_length < curr_length) { | |
| 298 best_length = curr_length; | |
| 299 best_distance = base_position - pos; | |
| 300 // Stop if we have reached the maximum length. Otherwise, make sure | |
| 301 // we have executed a minimum number of iterations depending on the | |
| 302 // quality. | |
| 303 if ((best_length == MAX_LENGTH) || | |
| 304 (curr_length >= length_max && iter < iter_min)) { | |
| 305 break; | |
| 306 } | |
| 307 } | |
| 308 } | |
| 309 // We have the best match but in case the two intervals continue matching | |
| 310 // to the left, we have the best matches for the left-extended pixels. | |
| 311 max_base_position = base_position; | |
| 312 while (1) { | |
| 313 assert(best_length <= MAX_LENGTH); | |
| 314 assert(best_distance <= WINDOW_SIZE); | |
| 315 p->offset_length_[base_position] = | |
| 316 (best_distance << MAX_LENGTH_BITS) | (uint32_t)best_length; | |
| 317 --base_position; | |
| 318 // Stop if we don't have a match or if we are out of bounds. | |
| 319 if (best_distance == 0 || base_position == 0) break; | |
| 320 // Stop if we cannot extend the matching intervals to the left. | |
| 321 if (base_position < best_distance || | |
| 322 argb[base_position - best_distance] != argb[base_position]) { | |
| 323 break; | |
| 324 } | |
| 325 // Stop if we are matching at its limit because there could be a closer | |
| 326 // matching interval with the same maximum length. Then again, if the | |
| 327 // matching interval is as close as possible (best_distance == 1), we will | |
| 328 // never find anything better so let's continue. | |
| 329 if (best_length == MAX_LENGTH && best_distance != 1 && | |
| 330 base_position + MAX_LENGTH < max_base_position) { | |
| 331 break; | |
| 332 } | |
| 333 if (best_length < MAX_LENGTH) { | |
| 334 ++best_length; | |
| 335 max_base_position = base_position; | |
| 336 } | |
| 337 } | |
| 338 } | |
| 339 return 1; | |
| 340 } | |
| 341 | |
| 342 static WEBP_INLINE int HashChainFindOffset(const VP8LHashChain* const p, | |
| 343 const int base_position) { | |
| 344 return p->offset_length_[base_position] >> MAX_LENGTH_BITS; | |
| 345 } | |
| 346 | |
| 347 static WEBP_INLINE int HashChainFindLength(const VP8LHashChain* const p, | |
| 348 const int base_position) { | |
| 349 return p->offset_length_[base_position] & ((1U << MAX_LENGTH_BITS) - 1); | |
| 350 } | |
| 351 | |
| 352 static WEBP_INLINE void HashChainFindCopy(const VP8LHashChain* const p, | |
| 353 int base_position, | |
| 354 int* const offset_ptr, | |
| 355 int* const length_ptr) { | |
| 356 *offset_ptr = HashChainFindOffset(p, base_position); | |
| 357 *length_ptr = HashChainFindLength(p, base_position); | |
| 358 } | |
| 359 | |
| 360 static WEBP_INLINE void AddSingleLiteral(uint32_t pixel, int use_color_cache, | |
| 361 VP8LColorCache* const hashers, | |
| 362 VP8LBackwardRefs* const refs) { | |
| 363 PixOrCopy v; | |
| 364 if (use_color_cache) { | |
| 365 const uint32_t key = VP8LColorCacheGetIndex(hashers, pixel); | |
| 366 if (VP8LColorCacheLookup(hashers, key) == pixel) { | |
| 367 v = PixOrCopyCreateCacheIdx(key); | |
| 368 } else { | |
| 369 v = PixOrCopyCreateLiteral(pixel); | |
| 370 VP8LColorCacheSet(hashers, key, pixel); | |
| 371 } | |
| 372 } else { | |
| 373 v = PixOrCopyCreateLiteral(pixel); | |
| 374 } | |
| 375 BackwardRefsCursorAdd(refs, v); | |
| 376 } | |
| 377 | |
| 378 static int BackwardReferencesRle(int xsize, int ysize, | |
| 379 const uint32_t* const argb, | |
| 380 int cache_bits, VP8LBackwardRefs* const refs) { | |
| 381 const int pix_count = xsize * ysize; | |
| 382 int i, k; | |
| 383 const int use_color_cache = (cache_bits > 0); | |
| 384 VP8LColorCache hashers; | |
| 385 | |
| 386 if (use_color_cache && !VP8LColorCacheInit(&hashers, cache_bits)) { | |
| 387 return 0; | |
| 388 } | |
| 389 ClearBackwardRefs(refs); | |
| 390 // Add first pixel as literal. | |
| 391 AddSingleLiteral(argb[0], use_color_cache, &hashers, refs); | |
| 392 i = 1; | |
| 393 while (i < pix_count) { | |
| 394 const int max_len = MaxFindCopyLength(pix_count - i); | |
| 395 const int kMinLength = 4; | |
| 396 const int rle_len = FindMatchLength(argb + i, argb + i - 1, 0, max_len); | |
| 397 const int prev_row_len = (i < xsize) ? 0 : | |
| 398 FindMatchLength(argb + i, argb + i - xsize, 0, max_len); | |
| 399 if (rle_len >= prev_row_len && rle_len >= kMinLength) { | |
| 400 BackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(1, rle_len)); | |
| 401 // We don't need to update the color cache here since it is always the | |
| 402 // same pixel being copied, and that does not change the color cache | |
| 403 // state. | |
| 404 i += rle_len; | |
| 405 } else if (prev_row_len >= kMinLength) { | |
| 406 BackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(xsize, prev_row_len)); | |
| 407 if (use_color_cache) { | |
| 408 for (k = 0; k < prev_row_len; ++k) { | |
| 409 VP8LColorCacheInsert(&hashers, argb[i + k]); | |
| 410 } | |
| 411 } | |
| 412 i += prev_row_len; | |
| 413 } else { | |
| 414 AddSingleLiteral(argb[i], use_color_cache, &hashers, refs); | |
| 415 i++; | |
| 416 } | |
| 417 } | |
| 418 if (use_color_cache) VP8LColorCacheClear(&hashers); | |
| 419 return !refs->error_; | |
| 420 } | |
| 421 | |
| 422 static int BackwardReferencesLz77(int xsize, int ysize, | |
| 423 const uint32_t* const argb, int cache_bits, | |
| 424 const VP8LHashChain* const hash_chain, | |
| 425 VP8LBackwardRefs* const refs) { | |
| 426 int i; | |
| 427 int i_last_check = -1; | |
| 428 int ok = 0; | |
| 429 int cc_init = 0; | |
| 430 const int use_color_cache = (cache_bits > 0); | |
| 431 const int pix_count = xsize * ysize; | |
| 432 VP8LColorCache hashers; | |
| 433 | |
| 434 if (use_color_cache) { | |
| 435 cc_init = VP8LColorCacheInit(&hashers, cache_bits); | |
| 436 if (!cc_init) goto Error; | |
| 437 } | |
| 438 ClearBackwardRefs(refs); | |
| 439 for (i = 0; i < pix_count;) { | |
| 440 // Alternative#1: Code the pixels starting at 'i' using backward reference. | |
| 441 int offset = 0; | |
| 442 int len = 0; | |
| 443 int j; | |
| 444 HashChainFindCopy(hash_chain, i, &offset, &len); | |
| 445 if (len > MIN_LENGTH + 1) { | |
| 446 const int len_ini = len; | |
| 447 int max_reach = 0; | |
| 448 assert(i + len < pix_count); | |
| 449 // Only start from what we have not checked already. | |
| 450 i_last_check = (i > i_last_check) ? i : i_last_check; | |
| 451 // We know the best match for the current pixel but we try to find the | |
| 452 // best matches for the current pixel AND the next one combined. | |
| 453 // The naive method would use the intervals: | |
| 454 // [i,i+len) + [i+len, length of best match at i+len) | |
| 455 // while we check if we can use: | |
| 456 // [i,j) (where j<=i+len) + [j, length of best match at j) | |
| 457 for (j = i_last_check + 1; j <= i + len_ini; ++j) { | |
| 458 const int len_j = HashChainFindLength(hash_chain, j); | |
| 459 const int reach = | |
| 460 j + (len_j > MIN_LENGTH + 1 ? len_j : 1); // 1 for single literal. | |
| 461 if (reach > max_reach) { | |
| 462 len = j - i; | |
| 463 max_reach = reach; | |
| 464 } | |
| 465 } | |
| 466 } else { | |
| 467 len = 1; | |
| 468 } | |
| 469 // Go with literal or backward reference. | |
| 470 assert(len > 0); | |
| 471 if (len == 1) { | |
| 472 AddSingleLiteral(argb[i], use_color_cache, &hashers, refs); | |
| 473 } else { | |
| 474 BackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len)); | |
| 475 if (use_color_cache) { | |
| 476 for (j = i; j < i + len; ++j) VP8LColorCacheInsert(&hashers, argb[j]); | |
| 477 } | |
| 478 } | |
| 479 i += len; | |
| 480 } | |
| 481 | |
| 482 ok = !refs->error_; | |
| 483 Error: | |
| 484 if (cc_init) VP8LColorCacheClear(&hashers); | |
| 485 return ok; | |
| 486 } | |
| 487 | |
| 488 // ----------------------------------------------------------------------------- | |
| 489 | |
| 490 typedef struct { | |
| 491 double alpha_[VALUES_IN_BYTE]; | |
| 492 double red_[VALUES_IN_BYTE]; | |
| 493 double blue_[VALUES_IN_BYTE]; | |
| 494 double distance_[NUM_DISTANCE_CODES]; | |
| 495 double* literal_; | |
| 496 } CostModel; | |
| 497 | |
| 498 static int BackwardReferencesTraceBackwards( | |
| 499 int xsize, int ysize, const uint32_t* const argb, int quality, | |
| 500 int cache_bits, const VP8LHashChain* const hash_chain, | |
| 501 VP8LBackwardRefs* const refs); | |
| 502 | |
| 503 static void ConvertPopulationCountTableToBitEstimates( | |
| 504 int num_symbols, const uint32_t population_counts[], double output[]) { | |
| 505 uint32_t sum = 0; | |
| 506 int nonzeros = 0; | |
| 507 int i; | |
| 508 for (i = 0; i < num_symbols; ++i) { | |
| 509 sum += population_counts[i]; | |
| 510 if (population_counts[i] > 0) { | |
| 511 ++nonzeros; | |
| 512 } | |
| 513 } | |
| 514 if (nonzeros <= 1) { | |
| 515 memset(output, 0, num_symbols * sizeof(*output)); | |
| 516 } else { | |
| 517 const double logsum = VP8LFastLog2(sum); | |
| 518 for (i = 0; i < num_symbols; ++i) { | |
| 519 output[i] = logsum - VP8LFastLog2(population_counts[i]); | |
| 520 } | |
| 521 } | |
| 522 } | |
| 523 | |
| 524 static int CostModelBuild(CostModel* const m, int cache_bits, | |
| 525 VP8LBackwardRefs* const refs) { | |
| 526 int ok = 0; | |
| 527 VP8LHistogram* const histo = VP8LAllocateHistogram(cache_bits); | |
| 528 if (histo == NULL) goto Error; | |
| 529 | |
| 530 VP8LHistogramCreate(histo, refs, cache_bits); | |
| 531 | |
| 532 ConvertPopulationCountTableToBitEstimates( | |
| 533 VP8LHistogramNumCodes(histo->palette_code_bits_), | |
| 534 histo->literal_, m->literal_); | |
| 535 ConvertPopulationCountTableToBitEstimates( | |
| 536 VALUES_IN_BYTE, histo->red_, m->red_); | |
| 537 ConvertPopulationCountTableToBitEstimates( | |
| 538 VALUES_IN_BYTE, histo->blue_, m->blue_); | |
| 539 ConvertPopulationCountTableToBitEstimates( | |
| 540 VALUES_IN_BYTE, histo->alpha_, m->alpha_); | |
| 541 ConvertPopulationCountTableToBitEstimates( | |
| 542 NUM_DISTANCE_CODES, histo->distance_, m->distance_); | |
| 543 ok = 1; | |
| 544 | |
| 545 Error: | |
| 546 VP8LFreeHistogram(histo); | |
| 547 return ok; | |
| 548 } | |
| 549 | |
| 550 static WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) { | |
| 551 return m->alpha_[v >> 24] + | |
| 552 m->red_[(v >> 16) & 0xff] + | |
| 553 m->literal_[(v >> 8) & 0xff] + | |
| 554 m->blue_[v & 0xff]; | |
| 555 } | |
| 556 | |
| 557 static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) { | |
| 558 const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx; | |
| 559 return m->literal_[literal_idx]; | |
| 560 } | |
| 561 | |
| 562 static WEBP_INLINE double GetLengthCost(const CostModel* const m, | |
| 563 uint32_t length) { | |
| 564 int code, extra_bits; | |
| 565 VP8LPrefixEncodeBits(length, &code, &extra_bits); | |
| 566 return m->literal_[VALUES_IN_BYTE + code] + extra_bits; | |
| 567 } | |
| 568 | |
| 569 static WEBP_INLINE double GetDistanceCost(const CostModel* const m, | |
| 570 uint32_t distance) { | |
| 571 int code, extra_bits; | |
| 572 VP8LPrefixEncodeBits(distance, &code, &extra_bits); | |
| 573 return m->distance_[code] + extra_bits; | |
| 574 } | |
| 575 | |
| 576 static void AddSingleLiteralWithCostModel(const uint32_t* const argb, | |
| 577 VP8LColorCache* const hashers, | |
| 578 const CostModel* const cost_model, | |
| 579 int idx, int use_color_cache, | |
| 580 double prev_cost, float* const cost, | |
| 581 uint16_t* const dist_array) { | |
| 582 double cost_val = prev_cost; | |
| 583 const uint32_t color = argb[0]; | |
| 584 if (use_color_cache && VP8LColorCacheContains(hashers, color)) { | |
| 585 const double mul0 = 0.68; | |
| 586 const int ix = VP8LColorCacheGetIndex(hashers, color); | |
| 587 cost_val += GetCacheCost(cost_model, ix) * mul0; | |
| 588 } else { | |
| 589 const double mul1 = 0.82; | |
| 590 if (use_color_cache) VP8LColorCacheInsert(hashers, color); | |
| 591 cost_val += GetLiteralCost(cost_model, color) * mul1; | |
| 592 } | |
| 593 if (cost[idx] > cost_val) { | |
| 594 cost[idx] = (float)cost_val; | |
| 595 dist_array[idx] = 1; // only one is inserted. | |
| 596 } | |
| 597 } | |
| 598 | |
| 599 // ----------------------------------------------------------------------------- | |
| 600 // CostManager and interval handling | |
| 601 | |
| 602 // Empirical value to avoid high memory consumption but good for performance. | |
| 603 #define COST_CACHE_INTERVAL_SIZE_MAX 100 | |
| 604 | |
| 605 // To perform backward reference every pixel at index index_ is considered and | |
| 606 // the cost for the MAX_LENGTH following pixels computed. Those following pixels | |
| 607 // at index index_ + k (k from 0 to MAX_LENGTH) have a cost of: | |
| 608 // distance_cost_ at index_ + GetLengthCost(cost_model, k) | |
| 609 // (named cost) (named cached cost) | |
| 610 // and the minimum value is kept. GetLengthCost(cost_model, k) is cached in an | |
| 611 // array of size MAX_LENGTH. | |
| 612 // Instead of performing MAX_LENGTH comparisons per pixel, we keep track of the | |
| 613 // minimal values using intervals, for which lower_ and upper_ bounds are kept. | |
| 614 // An interval is defined by the index_ of the pixel that generated it and | |
| 615 // is only useful in a range of indices from start_ to end_ (exclusive), i.e. | |
| 616 // it contains the minimum value for pixels between start_ and end_. | |
| 617 // Intervals are stored in a linked list and ordered by start_. When a new | |
| 618 // interval has a better minimum, old intervals are split or removed. | |
| 619 typedef struct CostInterval CostInterval; | |
| 620 struct CostInterval { | |
| 621 double lower_; | |
| 622 double upper_; | |
| 623 int start_; | |
| 624 int end_; | |
| 625 double distance_cost_; | |
| 626 int index_; | |
| 627 CostInterval* previous_; | |
| 628 CostInterval* next_; | |
| 629 }; | |
| 630 | |
| 631 // The GetLengthCost(cost_model, k) part of the costs is also bounded for | |
| 632 // efficiency in a set of intervals of a different type. | |
| 633 // If those intervals are small enough, they are not used for comparison and | |
| 634 // written into the costs right away. | |
| 635 typedef struct { | |
| 636 double lower_; // Lower bound of the interval. | |
| 637 double upper_; // Upper bound of the interval. | |
| 638 int start_; | |
| 639 int end_; // Exclusive. | |
| 640 int do_write_; // If !=0, the interval is saved to cost instead of being kept | |
| 641 // for comparison. | |
| 642 } CostCacheInterval; | |
| 643 | |
| 644 // This structure is in charge of managing intervals and costs. | |
| 645 // It caches the different CostCacheInterval, caches the different | |
| 646 // GetLengthCost(cost_model, k) in cost_cache_ and the CostInterval's (whose | |
| 647 // count_ is limited by COST_CACHE_INTERVAL_SIZE_MAX). | |
| 648 #define COST_MANAGER_MAX_FREE_LIST 10 | |
| 649 typedef struct { | |
| 650 CostInterval* head_; | |
| 651 int count_; // The number of stored intervals. | |
| 652 CostCacheInterval* cache_intervals_; | |
| 653 size_t cache_intervals_size_; | |
| 654 double cost_cache_[MAX_LENGTH]; // Contains the GetLengthCost(cost_model, k). | |
| 655 double min_cost_cache_; // The minimum value in cost_cache_[1:]. | |
| 656 double max_cost_cache_; // The maximum value in cost_cache_[1:]. | |
| 657 float* costs_; | |
| 658 uint16_t* dist_array_; | |
| 659 // Most of the time, we only need few intervals -> use a free-list, to avoid | |
| 660 // fragmentation with small allocs in most common cases. | |
| 661 CostInterval intervals_[COST_MANAGER_MAX_FREE_LIST]; | |
| 662 CostInterval* free_intervals_; | |
| 663 // These are regularly malloc'd remains. This list can't grow larger than than | |
| 664 // size COST_CACHE_INTERVAL_SIZE_MAX - COST_MANAGER_MAX_FREE_LIST, note. | |
| 665 CostInterval* recycled_intervals_; | |
| 666 // Buffer used in BackwardReferencesHashChainDistanceOnly to store the ends | |
| 667 // of the intervals that can have impacted the cost at a pixel. | |
| 668 int* interval_ends_; | |
| 669 int interval_ends_size_; | |
| 670 } CostManager; | |
| 671 | |
| 672 static int IsCostCacheIntervalWritable(int start, int end) { | |
| 673 // 100 is the length for which we consider an interval for comparison, and not | |
| 674 // for writing. | |
| 675 // The first intervals are very small and go in increasing size. This constant | |
| 676 // helps merging them into one big interval (up to index 150/200 usually from | |
| 677 // which intervals start getting much bigger). | |
| 678 // This value is empirical. | |
| 679 return (end - start + 1 < 100); | |
| 680 } | |
| 681 | |
| 682 static void CostIntervalAddToFreeList(CostManager* const manager, | |
| 683 CostInterval* const interval) { | |
| 684 interval->next_ = manager->free_intervals_; | |
| 685 manager->free_intervals_ = interval; | |
| 686 } | |
| 687 | |
| 688 static int CostIntervalIsInFreeList(const CostManager* const manager, | |
| 689 const CostInterval* const interval) { | |
| 690 return (interval >= &manager->intervals_[0] && | |
| 691 interval <= &manager->intervals_[COST_MANAGER_MAX_FREE_LIST - 1]); | |
| 692 } | |
| 693 | |
| 694 static void CostManagerInitFreeList(CostManager* const manager) { | |
| 695 int i; | |
| 696 manager->free_intervals_ = NULL; | |
| 697 for (i = 0; i < COST_MANAGER_MAX_FREE_LIST; ++i) { | |
| 698 CostIntervalAddToFreeList(manager, &manager->intervals_[i]); | |
| 699 } | |
| 700 } | |
| 701 | |
| 702 static void DeleteIntervalList(CostManager* const manager, | |
| 703 const CostInterval* interval) { | |
| 704 while (interval != NULL) { | |
| 705 const CostInterval* const next = interval->next_; | |
| 706 if (!CostIntervalIsInFreeList(manager, interval)) { | |
| 707 WebPSafeFree((void*)interval); | |
| 708 } // else: do nothing | |
| 709 interval = next; | |
| 710 } | |
| 711 } | |
| 712 | |
| 713 static void CostManagerClear(CostManager* const manager) { | |
| 714 if (manager == NULL) return; | |
| 715 | |
| 716 WebPSafeFree(manager->costs_); | |
| 717 WebPSafeFree(manager->cache_intervals_); | |
| 718 WebPSafeFree(manager->interval_ends_); | |
| 719 | |
| 720 // Clear the interval lists. | |
| 721 DeleteIntervalList(manager, manager->head_); | |
| 722 manager->head_ = NULL; | |
| 723 DeleteIntervalList(manager, manager->recycled_intervals_); | |
| 724 manager->recycled_intervals_ = NULL; | |
| 725 | |
| 726 // Reset pointers, count_ and cache_intervals_size_. | |
| 727 memset(manager, 0, sizeof(*manager)); | |
| 728 CostManagerInitFreeList(manager); | |
| 729 } | |
| 730 | |
| 731 static int CostManagerInit(CostManager* const manager, | |
| 732 uint16_t* const dist_array, int pix_count, | |
| 733 const CostModel* const cost_model) { | |
| 734 int i; | |
| 735 const int cost_cache_size = (pix_count > MAX_LENGTH) ? MAX_LENGTH : pix_count; | |
| 736 // This constant is tied to the cost_model we use. | |
| 737 // Empirically, differences between intervals is usually of more than 1. | |
| 738 const double min_cost_diff = 0.1; | |
| 739 | |
| 740 manager->costs_ = NULL; | |
| 741 manager->cache_intervals_ = NULL; | |
| 742 manager->interval_ends_ = NULL; | |
| 743 manager->head_ = NULL; | |
| 744 manager->recycled_intervals_ = NULL; | |
| 745 manager->count_ = 0; | |
| 746 manager->dist_array_ = dist_array; | |
| 747 CostManagerInitFreeList(manager); | |
| 748 | |
| 749 // Fill in the cost_cache_. | |
| 750 manager->cache_intervals_size_ = 1; | |
| 751 manager->cost_cache_[0] = 0; | |
| 752 for (i = 1; i < cost_cache_size; ++i) { | |
| 753 manager->cost_cache_[i] = GetLengthCost(cost_model, i); | |
| 754 // Get an approximation of the number of bound intervals. | |
| 755 if (fabs(manager->cost_cache_[i] - manager->cost_cache_[i - 1]) > | |
| 756 min_cost_diff) { | |
| 757 ++manager->cache_intervals_size_; | |
| 758 } | |
| 759 // Compute the minimum of cost_cache_. | |
| 760 if (i == 1) { | |
| 761 manager->min_cost_cache_ = manager->cost_cache_[1]; | |
| 762 manager->max_cost_cache_ = manager->cost_cache_[1]; | |
| 763 } else if (manager->cost_cache_[i] < manager->min_cost_cache_) { | |
| 764 manager->min_cost_cache_ = manager->cost_cache_[i]; | |
| 765 } else if (manager->cost_cache_[i] > manager->max_cost_cache_) { | |
| 766 manager->max_cost_cache_ = manager->cost_cache_[i]; | |
| 767 } | |
| 768 } | |
| 769 | |
| 770 // With the current cost models, we have 15 intervals, so we are safe by | |
| 771 // setting a maximum of COST_CACHE_INTERVAL_SIZE_MAX. | |
| 772 if (manager->cache_intervals_size_ > COST_CACHE_INTERVAL_SIZE_MAX) { | |
| 773 manager->cache_intervals_size_ = COST_CACHE_INTERVAL_SIZE_MAX; | |
| 774 } | |
| 775 manager->cache_intervals_ = (CostCacheInterval*)WebPSafeMalloc( | |
| 776 manager->cache_intervals_size_, sizeof(*manager->cache_intervals_)); | |
| 777 if (manager->cache_intervals_ == NULL) { | |
| 778 CostManagerClear(manager); | |
| 779 return 0; | |
| 780 } | |
| 781 | |
| 782 // Fill in the cache_intervals_. | |
| 783 { | |
| 784 double cost_prev = -1e38f; // unprobably low initial value | |
| 785 CostCacheInterval* prev = NULL; | |
| 786 CostCacheInterval* cur = manager->cache_intervals_; | |
| 787 const CostCacheInterval* const end = | |
| 788 manager->cache_intervals_ + manager->cache_intervals_size_; | |
| 789 | |
| 790 // Consecutive values in cost_cache_ are compared and if a big enough | |
| 791 // difference is found, a new interval is created and bounded. | |
| 792 for (i = 0; i < cost_cache_size; ++i) { | |
| 793 const double cost_val = manager->cost_cache_[i]; | |
| 794 if (i == 0 || | |
| 795 (fabs(cost_val - cost_prev) > min_cost_diff && cur + 1 < end)) { | |
| 796 if (i > 1) { | |
| 797 const int is_writable = | |
| 798 IsCostCacheIntervalWritable(cur->start_, cur->end_); | |
| 799 // Merge with the previous interval if both are writable. | |
| 800 if (is_writable && cur != manager->cache_intervals_ && | |
| 801 prev->do_write_) { | |
| 802 // Update the previous interval. | |
| 803 prev->end_ = cur->end_; | |
| 804 if (cur->lower_ < prev->lower_) { | |
| 805 prev->lower_ = cur->lower_; | |
| 806 } else if (cur->upper_ > prev->upper_) { | |
| 807 prev->upper_ = cur->upper_; | |
| 808 } | |
| 809 } else { | |
| 810 cur->do_write_ = is_writable; | |
| 811 prev = cur; | |
| 812 ++cur; | |
| 813 } | |
| 814 } | |
| 815 // Initialize an interval. | |
| 816 cur->start_ = i; | |
| 817 cur->do_write_ = 0; | |
| 818 cur->lower_ = cost_val; | |
| 819 cur->upper_ = cost_val; | |
| 820 } else { | |
| 821 // Update the current interval bounds. | |
| 822 if (cost_val < cur->lower_) { | |
| 823 cur->lower_ = cost_val; | |
| 824 } else if (cost_val > cur->upper_) { | |
| 825 cur->upper_ = cost_val; | |
| 826 } | |
| 827 } | |
| 828 cur->end_ = i + 1; | |
| 829 cost_prev = cost_val; | |
| 830 } | |
| 831 manager->cache_intervals_size_ = cur + 1 - manager->cache_intervals_; | |
| 832 } | |
| 833 | |
| 834 manager->costs_ = (float*)WebPSafeMalloc(pix_count, sizeof(*manager->costs_)); | |
| 835 if (manager->costs_ == NULL) { | |
| 836 CostManagerClear(manager); | |
| 837 return 0; | |
| 838 } | |
| 839 // Set the initial costs_ high for every pixel as we will keep the minimum. | |
| 840 for (i = 0; i < pix_count; ++i) manager->costs_[i] = 1e38f; | |
| 841 | |
| 842 // The cost at pixel is influenced by the cost intervals from previous pixels. | |
| 843 // Let us take the specific case where the offset is the same (which actually | |
| 844 // happens a lot in case of uniform regions). | |
| 845 // pixel i contributes to j>i a cost of: offset cost + cost_cache_[j-i] | |
| 846 // pixel i+1 contributes to j>i a cost of: 2*offset cost + cost_cache_[j-i-1] | |
| 847 // pixel i+2 contributes to j>i a cost of: 3*offset cost + cost_cache_[j-i-2] | |
| 848 // and so on. | |
| 849 // A pixel i influences the following length(j) < MAX_LENGTH pixels. What is | |
| 850 // the value of j such that pixel i + j cannot influence any of those pixels? | |
| 851 // This value is such that: | |
| 852 // max of cost_cache_ < j*offset cost + min of cost_cache_ | |
| 853 // (pixel i + j 's cost cannot beat the worst cost given by pixel i). | |
| 854 // This value will be used to optimize the cost computation in | |
| 855 // BackwardReferencesHashChainDistanceOnly. | |
| 856 { | |
| 857 // The offset cost is computed in GetDistanceCost and has a minimum value of | |
| 858 // the minimum in cost_model->distance_. The case where the offset cost is 0 | |
| 859 // will be dealt with differently later so we are only interested in the | |
| 860 // minimum non-zero offset cost. | |
| 861 double offset_cost_min = 0.; | |
| 862 int size; | |
| 863 for (i = 0; i < NUM_DISTANCE_CODES; ++i) { | |
| 864 if (cost_model->distance_[i] != 0) { | |
| 865 if (offset_cost_min == 0.) { | |
| 866 offset_cost_min = cost_model->distance_[i]; | |
| 867 } else if (cost_model->distance_[i] < offset_cost_min) { | |
| 868 offset_cost_min = cost_model->distance_[i]; | |
| 869 } | |
| 870 } | |
| 871 } | |
| 872 // In case all the cost_model->distance_ is 0, the next non-zero cost we | |
| 873 // can have is from the extra bit in GetDistanceCost, hence 1. | |
| 874 if (offset_cost_min < 1.) offset_cost_min = 1.; | |
| 875 | |
| 876 size = 1 + (int)ceil((manager->max_cost_cache_ - manager->min_cost_cache_) / | |
| 877 offset_cost_min); | |
| 878 // Empirically, we usually end up with a value below 100. | |
| 879 if (size > MAX_LENGTH) size = MAX_LENGTH; | |
| 880 | |
| 881 manager->interval_ends_ = | |
| 882 (int*)WebPSafeMalloc(size, sizeof(*manager->interval_ends_)); | |
| 883 if (manager->interval_ends_ == NULL) { | |
| 884 CostManagerClear(manager); | |
| 885 return 0; | |
| 886 } | |
| 887 manager->interval_ends_size_ = size; | |
| 888 } | |
| 889 | |
| 890 return 1; | |
| 891 } | |
| 892 | |
| 893 // Given the distance_cost for pixel 'index', update the cost at pixel 'i' if it | |
| 894 // is smaller than the previously computed value. | |
| 895 static WEBP_INLINE void UpdateCost(CostManager* const manager, int i, int index, | |
| 896 double distance_cost) { | |
| 897 int k = i - index; | |
| 898 double cost_tmp; | |
| 899 assert(k >= 0 && k < MAX_LENGTH); | |
| 900 cost_tmp = distance_cost + manager->cost_cache_[k]; | |
| 901 | |
| 902 if (manager->costs_[i] > cost_tmp) { | |
| 903 manager->costs_[i] = (float)cost_tmp; | |
| 904 manager->dist_array_[i] = k + 1; | |
| 905 } | |
| 906 } | |
| 907 | |
| 908 // Given the distance_cost for pixel 'index', update the cost for all the pixels | |
| 909 // between 'start' and 'end' excluded. | |
| 910 static WEBP_INLINE void UpdateCostPerInterval(CostManager* const manager, | |
| 911 int start, int end, int index, | |
| 912 double distance_cost) { | |
| 913 int i; | |
| 914 for (i = start; i < end; ++i) UpdateCost(manager, i, index, distance_cost); | |
| 915 } | |
| 916 | |
| 917 // Given two intervals, make 'prev' be the previous one of 'next' in 'manager'. | |
| 918 static WEBP_INLINE void ConnectIntervals(CostManager* const manager, | |
| 919 CostInterval* const prev, | |
| 920 CostInterval* const next) { | |
| 921 if (prev != NULL) { | |
| 922 prev->next_ = next; | |
| 923 } else { | |
| 924 manager->head_ = next; | |
| 925 } | |
| 926 | |
| 927 if (next != NULL) next->previous_ = prev; | |
| 928 } | |
| 929 | |
| 930 // Pop an interval in the manager. | |
| 931 static WEBP_INLINE void PopInterval(CostManager* const manager, | |
| 932 CostInterval* const interval) { | |
| 933 CostInterval* const next = interval->next_; | |
| 934 | |
| 935 if (interval == NULL) return; | |
| 936 | |
| 937 ConnectIntervals(manager, interval->previous_, next); | |
| 938 if (CostIntervalIsInFreeList(manager, interval)) { | |
| 939 CostIntervalAddToFreeList(manager, interval); | |
| 940 } else { // recycle regularly malloc'd intervals too | |
| 941 interval->next_ = manager->recycled_intervals_; | |
| 942 manager->recycled_intervals_ = interval; | |
| 943 } | |
| 944 --manager->count_; | |
| 945 assert(manager->count_ >= 0); | |
| 946 } | |
| 947 | |
| 948 // Update the cost at index i by going over all the stored intervals that | |
| 949 // overlap with i. | |
| 950 static WEBP_INLINE void UpdateCostPerIndex(CostManager* const manager, int i) { | |
| 951 CostInterval* current = manager->head_; | |
| 952 | |
| 953 while (current != NULL && current->start_ <= i) { | |
| 954 if (current->end_ <= i) { | |
| 955 // We have an outdated interval, remove it. | |
| 956 CostInterval* next = current->next_; | |
| 957 PopInterval(manager, current); | |
| 958 current = next; | |
| 959 } else { | |
| 960 UpdateCost(manager, i, current->index_, current->distance_cost_); | |
| 961 current = current->next_; | |
| 962 } | |
| 963 } | |
| 964 } | |
| 965 | |
| 966 // Given a current orphan interval and its previous interval, before | |
| 967 // it was orphaned (which can be NULL), set it at the right place in the list | |
| 968 // of intervals using the start_ ordering and the previous interval as a hint. | |
| 969 static WEBP_INLINE void PositionOrphanInterval(CostManager* const manager, | |
| 970 CostInterval* const current, | |
| 971 CostInterval* previous) { | |
| 972 assert(current != NULL); | |
| 973 | |
| 974 if (previous == NULL) previous = manager->head_; | |
| 975 while (previous != NULL && current->start_ < previous->start_) { | |
| 976 previous = previous->previous_; | |
| 977 } | |
| 978 while (previous != NULL && previous->next_ != NULL && | |
| 979 previous->next_->start_ < current->start_) { | |
| 980 previous = previous->next_; | |
| 981 } | |
| 982 | |
| 983 if (previous != NULL) { | |
| 984 ConnectIntervals(manager, current, previous->next_); | |
| 985 } else { | |
| 986 ConnectIntervals(manager, current, manager->head_); | |
| 987 } | |
| 988 ConnectIntervals(manager, previous, current); | |
| 989 } | |
| 990 | |
| 991 // Insert an interval in the list contained in the manager by starting at | |
| 992 // interval_in as a hint. The intervals are sorted by start_ value. | |
| 993 static WEBP_INLINE void InsertInterval(CostManager* const manager, | |
| 994 CostInterval* const interval_in, | |
| 995 double distance_cost, double lower, | |
| 996 double upper, int index, int start, | |
| 997 int end) { | |
| 998 CostInterval* interval_new; | |
| 999 | |
| 1000 if (IsCostCacheIntervalWritable(start, end) || | |
| 1001 manager->count_ >= COST_CACHE_INTERVAL_SIZE_MAX) { | |
| 1002 // Write down the interval if it is too small. | |
| 1003 UpdateCostPerInterval(manager, start, end, index, distance_cost); | |
| 1004 return; | |
| 1005 } | |
| 1006 if (manager->free_intervals_ != NULL) { | |
| 1007 interval_new = manager->free_intervals_; | |
| 1008 manager->free_intervals_ = interval_new->next_; | |
| 1009 } else if (manager->recycled_intervals_ != NULL) { | |
| 1010 interval_new = manager->recycled_intervals_; | |
| 1011 manager->recycled_intervals_ = interval_new->next_; | |
| 1012 } else { // malloc for good | |
| 1013 interval_new = (CostInterval*)WebPSafeMalloc(1, sizeof(*interval_new)); | |
| 1014 if (interval_new == NULL) { | |
| 1015 // Write down the interval if we cannot create it. | |
| 1016 UpdateCostPerInterval(manager, start, end, index, distance_cost); | |
| 1017 return; | |
| 1018 } | |
| 1019 } | |
| 1020 | |
| 1021 interval_new->distance_cost_ = distance_cost; | |
| 1022 interval_new->lower_ = lower; | |
| 1023 interval_new->upper_ = upper; | |
| 1024 interval_new->index_ = index; | |
| 1025 interval_new->start_ = start; | |
| 1026 interval_new->end_ = end; | |
| 1027 PositionOrphanInterval(manager, interval_new, interval_in); | |
| 1028 | |
| 1029 ++manager->count_; | |
| 1030 } | |
| 1031 | |
| 1032 // When an interval has its start_ or end_ modified, it needs to be | |
| 1033 // repositioned in the linked list. | |
| 1034 static WEBP_INLINE void RepositionInterval(CostManager* const manager, | |
| 1035 CostInterval* const interval) { | |
| 1036 if (IsCostCacheIntervalWritable(interval->start_, interval->end_)) { | |
| 1037 // Maybe interval has been resized and is small enough to be removed. | |
| 1038 UpdateCostPerInterval(manager, interval->start_, interval->end_, | |
| 1039 interval->index_, interval->distance_cost_); | |
| 1040 PopInterval(manager, interval); | |
| 1041 return; | |
| 1042 } | |
| 1043 | |
| 1044 // Early exit if interval is at the right spot. | |
| 1045 if ((interval->previous_ == NULL || | |
| 1046 interval->previous_->start_ <= interval->start_) && | |
| 1047 (interval->next_ == NULL || | |
| 1048 interval->start_ <= interval->next_->start_)) { | |
| 1049 return; | |
| 1050 } | |
| 1051 | |
| 1052 ConnectIntervals(manager, interval->previous_, interval->next_); | |
| 1053 PositionOrphanInterval(manager, interval, interval->previous_); | |
| 1054 } | |
| 1055 | |
| 1056 // Given a new cost interval defined by its start at index, its last value and | |
| 1057 // distance_cost, add its contributions to the previous intervals and costs. | |
| 1058 // If handling the interval or one of its subintervals becomes to heavy, its | |
| 1059 // contribution is added to the costs right away. | |
| 1060 static WEBP_INLINE void PushInterval(CostManager* const manager, | |
| 1061 double distance_cost, int index, | |
| 1062 int last) { | |
| 1063 size_t i; | |
| 1064 CostInterval* interval = manager->head_; | |
| 1065 CostInterval* interval_next; | |
| 1066 const CostCacheInterval* const cost_cache_intervals = | |
| 1067 manager->cache_intervals_; | |
| 1068 | |
| 1069 for (i = 0; i < manager->cache_intervals_size_ && | |
| 1070 cost_cache_intervals[i].start_ < last; | |
| 1071 ++i) { | |
| 1072 // Define the intersection of the ith interval with the new one. | |
| 1073 int start = index + cost_cache_intervals[i].start_; | |
| 1074 const int end = index + (cost_cache_intervals[i].end_ > last | |
| 1075 ? last | |
| 1076 : cost_cache_intervals[i].end_); | |
| 1077 const double lower_in = cost_cache_intervals[i].lower_; | |
| 1078 const double upper_in = cost_cache_intervals[i].upper_; | |
| 1079 const double lower_full_in = distance_cost + lower_in; | |
| 1080 const double upper_full_in = distance_cost + upper_in; | |
| 1081 | |
| 1082 if (cost_cache_intervals[i].do_write_) { | |
| 1083 UpdateCostPerInterval(manager, start, end, index, distance_cost); | |
| 1084 continue; | |
| 1085 } | |
| 1086 | |
| 1087 for (; interval != NULL && interval->start_ < end && start < end; | |
| 1088 interval = interval_next) { | |
| 1089 const double lower_full_interval = | |
| 1090 interval->distance_cost_ + interval->lower_; | |
| 1091 const double upper_full_interval = | |
| 1092 interval->distance_cost_ + interval->upper_; | |
| 1093 | |
| 1094 interval_next = interval->next_; | |
| 1095 | |
| 1096 // Make sure we have some overlap | |
| 1097 if (start >= interval->end_) continue; | |
| 1098 | |
| 1099 if (lower_full_in >= upper_full_interval) { | |
| 1100 // When intervals are represented, the lower, the better. | |
| 1101 // [**********************************************************] | |
| 1102 // start end | |
| 1103 // [----------------------------------] | |
| 1104 // interval->start_ interval->end_ | |
| 1105 // If we are worse than what we already have, add whatever we have so | |
| 1106 // far up to interval. | |
| 1107 const int start_new = interval->end_; | |
| 1108 InsertInterval(manager, interval, distance_cost, lower_in, upper_in, | |
| 1109 index, start, interval->start_); | |
| 1110 start = start_new; | |
| 1111 continue; | |
| 1112 } | |
| 1113 | |
| 1114 // We know the two intervals intersect. | |
| 1115 if (upper_full_in >= lower_full_interval) { | |
| 1116 // There is no clear cut on which is best, so let's keep both. | |
| 1117 // [*********[*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*]***********] | |
| 1118 // start interval->start_ interval->end_ end | |
| 1119 // OR | |
| 1120 // [*********[*-*-*-*-*-*-*-*-*-*-*-]----------------------] | |
| 1121 // start interval->start_ end interval->end_ | |
| 1122 const int end_new = (interval->end_ <= end) ? interval->end_ : end; | |
| 1123 InsertInterval(manager, interval, distance_cost, lower_in, upper_in, | |
| 1124 index, start, end_new); | |
| 1125 start = end_new; | |
| 1126 } else if (start <= interval->start_ && interval->end_ <= end) { | |
| 1127 // [----------------------------------] | |
| 1128 // interval->start_ interval->end_ | |
| 1129 // [**************************************************************] | |
| 1130 // start end | |
| 1131 // We can safely remove the old interval as it is fully included. | |
| 1132 PopInterval(manager, interval); | |
| 1133 } else { | |
| 1134 if (interval->start_ <= start && end <= interval->end_) { | |
| 1135 // [--------------------------------------------------------------] | |
| 1136 // interval->start_ interval->end_ | |
| 1137 // [*****************************] | |
| 1138 // start end | |
| 1139 // We have to split the old interval as it fully contains the new one. | |
| 1140 const int end_original = interval->end_; | |
| 1141 interval->end_ = start; | |
| 1142 InsertInterval(manager, interval, interval->distance_cost_, | |
| 1143 interval->lower_, interval->upper_, interval->index_, | |
| 1144 end, end_original); | |
| 1145 } else if (interval->start_ < start) { | |
| 1146 // [------------------------------------] | |
| 1147 // interval->start_ interval->end_ | |
| 1148 // [*****************************] | |
| 1149 // start end | |
| 1150 interval->end_ = start; | |
| 1151 } else { | |
| 1152 // [------------------------------------] | |
| 1153 // interval->start_ interval->end_ | |
| 1154 // [*****************************] | |
| 1155 // start end | |
| 1156 interval->start_ = end; | |
| 1157 } | |
| 1158 | |
| 1159 // The interval has been modified, we need to reposition it or write it. | |
| 1160 RepositionInterval(manager, interval); | |
| 1161 } | |
| 1162 } | |
| 1163 // Insert the remaining interval from start to end. | |
| 1164 InsertInterval(manager, interval, distance_cost, lower_in, upper_in, index, | |
| 1165 start, end); | |
| 1166 } | |
| 1167 } | |
| 1168 | |
| 1169 static int BackwardReferencesHashChainDistanceOnly( | |
| 1170 int xsize, int ysize, const uint32_t* const argb, int quality, | |
| 1171 int cache_bits, const VP8LHashChain* const hash_chain, | |
| 1172 VP8LBackwardRefs* const refs, uint16_t* const dist_array) { | |
| 1173 int i; | |
| 1174 int ok = 0; | |
| 1175 int cc_init = 0; | |
| 1176 const int pix_count = xsize * ysize; | |
| 1177 const int use_color_cache = (cache_bits > 0); | |
| 1178 const size_t literal_array_size = sizeof(double) * | |
| 1179 (NUM_LITERAL_CODES + NUM_LENGTH_CODES + | |
| 1180 ((cache_bits > 0) ? (1 << cache_bits) : 0)); | |
| 1181 const size_t cost_model_size = sizeof(CostModel) + literal_array_size; | |
| 1182 CostModel* const cost_model = | |
| 1183 (CostModel*)WebPSafeCalloc(1ULL, cost_model_size); | |
| 1184 VP8LColorCache hashers; | |
| 1185 const int skip_length = 32 + quality; | |
| 1186 const int skip_min_distance_code = 2; | |
| 1187 CostManager* cost_manager = | |
| 1188 (CostManager*)WebPSafeMalloc(1ULL, sizeof(*cost_manager)); | |
| 1189 | |
| 1190 if (cost_model == NULL || cost_manager == NULL) goto Error; | |
| 1191 | |
| 1192 cost_model->literal_ = (double*)(cost_model + 1); | |
| 1193 if (use_color_cache) { | |
| 1194 cc_init = VP8LColorCacheInit(&hashers, cache_bits); | |
| 1195 if (!cc_init) goto Error; | |
| 1196 } | |
| 1197 | |
| 1198 if (!CostModelBuild(cost_model, cache_bits, refs)) { | |
| 1199 goto Error; | |
| 1200 } | |
| 1201 | |
| 1202 if (!CostManagerInit(cost_manager, dist_array, pix_count, cost_model)) { | |
| 1203 goto Error; | |
| 1204 } | |
| 1205 | |
| 1206 // We loop one pixel at a time, but store all currently best points to | |
| 1207 // non-processed locations from this point. | |
| 1208 dist_array[0] = 0; | |
| 1209 // Add first pixel as literal. | |
| 1210 AddSingleLiteralWithCostModel(argb + 0, &hashers, cost_model, 0, | |
| 1211 use_color_cache, 0.0, cost_manager->costs_, | |
| 1212 dist_array); | |
| 1213 | |
| 1214 for (i = 1; i < pix_count - 1; ++i) { | |
| 1215 int offset = 0, len = 0; | |
| 1216 double prev_cost = cost_manager->costs_[i - 1]; | |
| 1217 HashChainFindCopy(hash_chain, i, &offset, &len); | |
| 1218 if (len >= MIN_LENGTH) { | |
| 1219 const int code = DistanceToPlaneCode(xsize, offset); | |
| 1220 const double offset_cost = GetDistanceCost(cost_model, code); | |
| 1221 const int first_i = i; | |
| 1222 int j_max = 0, interval_ends_index = 0; | |
| 1223 const int is_offset_zero = (offset_cost == 0.); | |
| 1224 | |
| 1225 if (!is_offset_zero) { | |
| 1226 j_max = (int)ceil( | |
| 1227 (cost_manager->max_cost_cache_ - cost_manager->min_cost_cache_) / | |
| 1228 offset_cost); | |
| 1229 if (j_max < 1) { | |
| 1230 j_max = 1; | |
| 1231 } else if (j_max > cost_manager->interval_ends_size_ - 1) { | |
| 1232 // This could only happen in the case of MAX_LENGTH. | |
| 1233 j_max = cost_manager->interval_ends_size_ - 1; | |
| 1234 } | |
| 1235 } // else j_max is unused anyway. | |
| 1236 | |
| 1237 // Instead of considering all contributions from a pixel i by calling: | |
| 1238 // PushInterval(cost_manager, prev_cost + offset_cost, i, len); | |
| 1239 // we optimize these contributions in case offset_cost stays the same for | |
| 1240 // consecutive pixels. This describes a set of pixels similar to a | |
| 1241 // previous set (e.g. constant color regions). | |
| 1242 for (; i < pix_count - 1; ++i) { | |
| 1243 int offset_next, len_next; | |
| 1244 prev_cost = cost_manager->costs_[i - 1]; | |
| 1245 | |
| 1246 if (is_offset_zero) { | |
| 1247 // No optimization can be made so we just push all of the | |
| 1248 // contributions from i. | |
| 1249 PushInterval(cost_manager, prev_cost, i, len); | |
| 1250 } else { | |
| 1251 // j_max is chosen as the smallest j such that: | |
| 1252 // max of cost_cache_ < j*offset cost + min of cost_cache_ | |
| 1253 // Therefore, the pixel influenced by i-j_max, cannot be influenced | |
| 1254 // by i. Only the costs after the end of what i contributed need to be | |
| 1255 // updated. cost_manager->interval_ends_ is a circular buffer that | |
| 1256 // stores those ends. | |
| 1257 const double distance_cost = prev_cost + offset_cost; | |
| 1258 int j = cost_manager->interval_ends_[interval_ends_index]; | |
| 1259 if (i - first_i <= j_max || | |
| 1260 !IsCostCacheIntervalWritable(j, i + len)) { | |
| 1261 PushInterval(cost_manager, distance_cost, i, len); | |
| 1262 } else { | |
| 1263 for (; j < i + len; ++j) { | |
| 1264 UpdateCost(cost_manager, j, i, distance_cost); | |
| 1265 } | |
| 1266 } | |
| 1267 // Store the new end in the circular buffer. | |
| 1268 assert(interval_ends_index < cost_manager->interval_ends_size_); | |
| 1269 cost_manager->interval_ends_[interval_ends_index] = i + len; | |
| 1270 if (++interval_ends_index > j_max) interval_ends_index = 0; | |
| 1271 } | |
| 1272 | |
| 1273 // Check whether i is the last pixel to consider, as it is handled | |
| 1274 // differently. | |
| 1275 if (i + 1 >= pix_count - 1) break; | |
| 1276 HashChainFindCopy(hash_chain, i + 1, &offset_next, &len_next); | |
| 1277 if (offset_next != offset) break; | |
| 1278 len = len_next; | |
| 1279 UpdateCostPerIndex(cost_manager, i); | |
| 1280 AddSingleLiteralWithCostModel(argb + i, &hashers, cost_model, i, | |
| 1281 use_color_cache, prev_cost, | |
| 1282 cost_manager->costs_, dist_array); | |
| 1283 } | |
| 1284 // Submit the last pixel. | |
| 1285 UpdateCostPerIndex(cost_manager, i + 1); | |
| 1286 | |
| 1287 // This if is for speedup only. It roughly doubles the speed, and | |
| 1288 // makes compression worse by .1 %. | |
| 1289 if (len >= skip_length && code <= skip_min_distance_code) { | |
| 1290 // Long copy for short distances, let's skip the middle | |
| 1291 // lookups for better copies. | |
| 1292 // 1) insert the hashes. | |
| 1293 if (use_color_cache) { | |
| 1294 int k; | |
| 1295 for (k = 0; k < len; ++k) { | |
| 1296 VP8LColorCacheInsert(&hashers, argb[i + k]); | |
| 1297 } | |
| 1298 } | |
| 1299 // 2) jump. | |
| 1300 { | |
| 1301 const int i_next = i + len - 1; // for loop does ++i, thus -1 here. | |
| 1302 for (; i <= i_next; ++i) UpdateCostPerIndex(cost_manager, i + 1); | |
| 1303 i = i_next; | |
| 1304 } | |
| 1305 goto next_symbol; | |
| 1306 } | |
| 1307 if (len > MIN_LENGTH) { | |
| 1308 int code_min_length; | |
| 1309 double cost_total; | |
| 1310 offset = HashChainFindOffset(hash_chain, i); | |
| 1311 code_min_length = DistanceToPlaneCode(xsize, offset); | |
| 1312 cost_total = prev_cost + | |
| 1313 GetDistanceCost(cost_model, code_min_length) + | |
| 1314 GetLengthCost(cost_model, 1); | |
| 1315 if (cost_manager->costs_[i + 1] > cost_total) { | |
| 1316 cost_manager->costs_[i + 1] = (float)cost_total; | |
| 1317 dist_array[i + 1] = 2; | |
| 1318 } | |
| 1319 } | |
| 1320 } else { // len < MIN_LENGTH | |
| 1321 UpdateCostPerIndex(cost_manager, i + 1); | |
| 1322 } | |
| 1323 | |
| 1324 AddSingleLiteralWithCostModel(argb + i, &hashers, cost_model, i, | |
| 1325 use_color_cache, prev_cost, | |
| 1326 cost_manager->costs_, dist_array); | |
| 1327 | |
| 1328 next_symbol: ; | |
| 1329 } | |
| 1330 // Handle the last pixel. | |
| 1331 if (i == (pix_count - 1)) { | |
| 1332 AddSingleLiteralWithCostModel( | |
| 1333 argb + i, &hashers, cost_model, i, use_color_cache, | |
| 1334 cost_manager->costs_[pix_count - 2], cost_manager->costs_, dist_array); | |
| 1335 } | |
| 1336 | |
| 1337 ok = !refs->error_; | |
| 1338 Error: | |
| 1339 if (cc_init) VP8LColorCacheClear(&hashers); | |
| 1340 CostManagerClear(cost_manager); | |
| 1341 WebPSafeFree(cost_model); | |
| 1342 WebPSafeFree(cost_manager); | |
| 1343 return ok; | |
| 1344 } | |
| 1345 | |
| 1346 // We pack the path at the end of *dist_array and return | |
| 1347 // a pointer to this part of the array. Example: | |
| 1348 // dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232] | |
| 1349 static void TraceBackwards(uint16_t* const dist_array, | |
| 1350 int dist_array_size, | |
| 1351 uint16_t** const chosen_path, | |
| 1352 int* const chosen_path_size) { | |
| 1353 uint16_t* path = dist_array + dist_array_size; | |
| 1354 uint16_t* cur = dist_array + dist_array_size - 1; | |
| 1355 while (cur >= dist_array) { | |
| 1356 const int k = *cur; | |
| 1357 --path; | |
| 1358 *path = k; | |
| 1359 cur -= k; | |
| 1360 } | |
| 1361 *chosen_path = path; | |
| 1362 *chosen_path_size = (int)(dist_array + dist_array_size - path); | |
| 1363 } | |
| 1364 | |
| 1365 static int BackwardReferencesHashChainFollowChosenPath( | |
| 1366 const uint32_t* const argb, int cache_bits, | |
| 1367 const uint16_t* const chosen_path, int chosen_path_size, | |
| 1368 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs) { | |
| 1369 const int use_color_cache = (cache_bits > 0); | |
| 1370 int ix; | |
| 1371 int i = 0; | |
| 1372 int ok = 0; | |
| 1373 int cc_init = 0; | |
| 1374 VP8LColorCache hashers; | |
| 1375 | |
| 1376 if (use_color_cache) { | |
| 1377 cc_init = VP8LColorCacheInit(&hashers, cache_bits); | |
| 1378 if (!cc_init) goto Error; | |
| 1379 } | |
| 1380 | |
| 1381 ClearBackwardRefs(refs); | |
| 1382 for (ix = 0; ix < chosen_path_size; ++ix) { | |
| 1383 const int len = chosen_path[ix]; | |
| 1384 if (len != 1) { | |
| 1385 int k; | |
| 1386 const int offset = HashChainFindOffset(hash_chain, i); | |
| 1387 BackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len)); | |
| 1388 if (use_color_cache) { | |
| 1389 for (k = 0; k < len; ++k) { | |
| 1390 VP8LColorCacheInsert(&hashers, argb[i + k]); | |
| 1391 } | |
| 1392 } | |
| 1393 i += len; | |
| 1394 } else { | |
| 1395 PixOrCopy v; | |
| 1396 if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { | |
| 1397 // push pixel as a color cache index | |
| 1398 const int idx = VP8LColorCacheGetIndex(&hashers, argb[i]); | |
| 1399 v = PixOrCopyCreateCacheIdx(idx); | |
| 1400 } else { | |
| 1401 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); | |
| 1402 v = PixOrCopyCreateLiteral(argb[i]); | |
| 1403 } | |
| 1404 BackwardRefsCursorAdd(refs, v); | |
| 1405 ++i; | |
| 1406 } | |
| 1407 } | |
| 1408 ok = !refs->error_; | |
| 1409 Error: | |
| 1410 if (cc_init) VP8LColorCacheClear(&hashers); | |
| 1411 return ok; | |
| 1412 } | |
| 1413 | |
| 1414 // Returns 1 on success. | |
| 1415 static int BackwardReferencesTraceBackwards( | |
| 1416 int xsize, int ysize, const uint32_t* const argb, int quality, | |
| 1417 int cache_bits, const VP8LHashChain* const hash_chain, | |
| 1418 VP8LBackwardRefs* const refs) { | |
| 1419 int ok = 0; | |
| 1420 const int dist_array_size = xsize * ysize; | |
| 1421 uint16_t* chosen_path = NULL; | |
| 1422 int chosen_path_size = 0; | |
| 1423 uint16_t* dist_array = | |
| 1424 (uint16_t*)WebPSafeMalloc(dist_array_size, sizeof(*dist_array)); | |
| 1425 | |
| 1426 if (dist_array == NULL) goto Error; | |
| 1427 | |
| 1428 if (!BackwardReferencesHashChainDistanceOnly( | |
| 1429 xsize, ysize, argb, quality, cache_bits, hash_chain, | |
| 1430 refs, dist_array)) { | |
| 1431 goto Error; | |
| 1432 } | |
| 1433 TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size); | |
| 1434 if (!BackwardReferencesHashChainFollowChosenPath( | |
| 1435 argb, cache_bits, chosen_path, chosen_path_size, hash_chain, refs)) { | |
| 1436 goto Error; | |
| 1437 } | |
| 1438 ok = 1; | |
| 1439 Error: | |
| 1440 WebPSafeFree(dist_array); | |
| 1441 return ok; | |
| 1442 } | |
| 1443 | |
| 1444 static void BackwardReferences2DLocality(int xsize, | |
| 1445 const VP8LBackwardRefs* const refs) { | |
| 1446 VP8LRefsCursor c = VP8LRefsCursorInit(refs); | |
| 1447 while (VP8LRefsCursorOk(&c)) { | |
| 1448 if (PixOrCopyIsCopy(c.cur_pos)) { | |
| 1449 const int dist = c.cur_pos->argb_or_distance; | |
| 1450 const int transformed_dist = DistanceToPlaneCode(xsize, dist); | |
| 1451 c.cur_pos->argb_or_distance = transformed_dist; | |
| 1452 } | |
| 1453 VP8LRefsCursorNext(&c); | |
| 1454 } | |
| 1455 } | |
| 1456 | |
| 1457 // Returns entropy for the given cache bits. | |
| 1458 static double ComputeCacheEntropy(const uint32_t* argb, | |
| 1459 const VP8LBackwardRefs* const refs, | |
| 1460 int cache_bits) { | |
| 1461 const int use_color_cache = (cache_bits > 0); | |
| 1462 int cc_init = 0; | |
| 1463 double entropy = MAX_ENTROPY; | |
| 1464 const double kSmallPenaltyForLargeCache = 4.0; | |
| 1465 VP8LColorCache hashers; | |
| 1466 VP8LRefsCursor c = VP8LRefsCursorInit(refs); | |
| 1467 VP8LHistogram* histo = VP8LAllocateHistogram(cache_bits); | |
| 1468 if (histo == NULL) goto Error; | |
| 1469 | |
| 1470 if (use_color_cache) { | |
| 1471 cc_init = VP8LColorCacheInit(&hashers, cache_bits); | |
| 1472 if (!cc_init) goto Error; | |
| 1473 } | |
| 1474 if (!use_color_cache) { | |
| 1475 while (VP8LRefsCursorOk(&c)) { | |
| 1476 VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos); | |
| 1477 VP8LRefsCursorNext(&c); | |
| 1478 } | |
| 1479 } else { | |
| 1480 while (VP8LRefsCursorOk(&c)) { | |
| 1481 const PixOrCopy* const v = c.cur_pos; | |
| 1482 if (PixOrCopyIsLiteral(v)) { | |
| 1483 const uint32_t pix = *argb++; | |
| 1484 const uint32_t key = VP8LColorCacheGetIndex(&hashers, pix); | |
| 1485 if (VP8LColorCacheLookup(&hashers, key) == pix) { | |
| 1486 ++histo->literal_[NUM_LITERAL_CODES + NUM_LENGTH_CODES + key]; | |
| 1487 } else { | |
| 1488 VP8LColorCacheSet(&hashers, key, pix); | |
| 1489 ++histo->blue_[pix & 0xff]; | |
| 1490 ++histo->literal_[(pix >> 8) & 0xff]; | |
| 1491 ++histo->red_[(pix >> 16) & 0xff]; | |
| 1492 ++histo->alpha_[pix >> 24]; | |
| 1493 } | |
| 1494 } else { | |
| 1495 int len = PixOrCopyLength(v); | |
| 1496 int code, extra_bits; | |
| 1497 VP8LPrefixEncodeBits(len, &code, &extra_bits); | |
| 1498 ++histo->literal_[NUM_LITERAL_CODES + code]; | |
| 1499 VP8LPrefixEncodeBits(PixOrCopyDistance(v), &code, &extra_bits); | |
| 1500 ++histo->distance_[code]; | |
| 1501 do { | |
| 1502 VP8LColorCacheInsert(&hashers, *argb++); | |
| 1503 } while(--len != 0); | |
| 1504 } | |
| 1505 VP8LRefsCursorNext(&c); | |
| 1506 } | |
| 1507 } | |
| 1508 entropy = VP8LHistogramEstimateBits(histo) + | |
| 1509 kSmallPenaltyForLargeCache * cache_bits; | |
| 1510 Error: | |
| 1511 if (cc_init) VP8LColorCacheClear(&hashers); | |
| 1512 VP8LFreeHistogram(histo); | |
| 1513 return entropy; | |
| 1514 } | |
| 1515 | |
| 1516 // Evaluate optimal cache bits for the local color cache. | |
| 1517 // The input *best_cache_bits sets the maximum cache bits to use (passing 0 | |
| 1518 // implies disabling the local color cache). The local color cache is also | |
| 1519 // disabled for the lower (<= 25) quality. | |
| 1520 // Returns 0 in case of memory error. | |
| 1521 static int CalculateBestCacheSize(const uint32_t* const argb, | |
| 1522 int xsize, int ysize, int quality, | |
| 1523 const VP8LHashChain* const hash_chain, | |
| 1524 VP8LBackwardRefs* const refs, | |
| 1525 int* const lz77_computed, | |
| 1526 int* const best_cache_bits) { | |
| 1527 int eval_low = 1; | |
| 1528 int eval_high = 1; | |
| 1529 double entropy_low = MAX_ENTROPY; | |
| 1530 double entropy_high = MAX_ENTROPY; | |
| 1531 const double cost_mul = 5e-4; | |
| 1532 int cache_bits_low = 0; | |
| 1533 int cache_bits_high = (quality <= 25) ? 0 : *best_cache_bits; | |
| 1534 | |
| 1535 assert(cache_bits_high <= MAX_COLOR_CACHE_BITS); | |
| 1536 | |
| 1537 *lz77_computed = 0; | |
| 1538 if (cache_bits_high == 0) { | |
| 1539 *best_cache_bits = 0; | |
| 1540 // Local color cache is disabled. | |
| 1541 return 1; | |
| 1542 } | |
| 1543 if (!BackwardReferencesLz77(xsize, ysize, argb, cache_bits_low, hash_chain, | |
| 1544 refs)) { | |
| 1545 return 0; | |
| 1546 } | |
| 1547 // Do a binary search to find the optimal entropy for cache_bits. | |
| 1548 while (eval_low || eval_high) { | |
| 1549 if (eval_low) { | |
| 1550 entropy_low = ComputeCacheEntropy(argb, refs, cache_bits_low); | |
| 1551 entropy_low += entropy_low * cache_bits_low * cost_mul; | |
| 1552 eval_low = 0; | |
| 1553 } | |
| 1554 if (eval_high) { | |
| 1555 entropy_high = ComputeCacheEntropy(argb, refs, cache_bits_high); | |
| 1556 entropy_high += entropy_high * cache_bits_high * cost_mul; | |
| 1557 eval_high = 0; | |
| 1558 } | |
| 1559 if (entropy_high < entropy_low) { | |
| 1560 const int prev_cache_bits_low = cache_bits_low; | |
| 1561 *best_cache_bits = cache_bits_high; | |
| 1562 cache_bits_low = (cache_bits_low + cache_bits_high) / 2; | |
| 1563 if (cache_bits_low != prev_cache_bits_low) eval_low = 1; | |
| 1564 } else { | |
| 1565 *best_cache_bits = cache_bits_low; | |
| 1566 cache_bits_high = (cache_bits_low + cache_bits_high) / 2; | |
| 1567 if (cache_bits_high != cache_bits_low) eval_high = 1; | |
| 1568 } | |
| 1569 } | |
| 1570 *lz77_computed = 1; | |
| 1571 return 1; | |
| 1572 } | |
| 1573 | |
| 1574 // Update (in-place) backward references for specified cache_bits. | |
| 1575 static int BackwardRefsWithLocalCache(const uint32_t* const argb, | |
| 1576 int cache_bits, | |
| 1577 VP8LBackwardRefs* const refs) { | |
| 1578 int pixel_index = 0; | |
| 1579 VP8LColorCache hashers; | |
| 1580 VP8LRefsCursor c = VP8LRefsCursorInit(refs); | |
| 1581 if (!VP8LColorCacheInit(&hashers, cache_bits)) return 0; | |
| 1582 | |
| 1583 while (VP8LRefsCursorOk(&c)) { | |
| 1584 PixOrCopy* const v = c.cur_pos; | |
| 1585 if (PixOrCopyIsLiteral(v)) { | |
| 1586 const uint32_t argb_literal = v->argb_or_distance; | |
| 1587 if (VP8LColorCacheContains(&hashers, argb_literal)) { | |
| 1588 const int ix = VP8LColorCacheGetIndex(&hashers, argb_literal); | |
| 1589 *v = PixOrCopyCreateCacheIdx(ix); | |
| 1590 } else { | |
| 1591 VP8LColorCacheInsert(&hashers, argb_literal); | |
| 1592 } | |
| 1593 ++pixel_index; | |
| 1594 } else { | |
| 1595 // refs was created without local cache, so it can not have cache indexes. | |
| 1596 int k; | |
| 1597 assert(PixOrCopyIsCopy(v)); | |
| 1598 for (k = 0; k < v->len; ++k) { | |
| 1599 VP8LColorCacheInsert(&hashers, argb[pixel_index++]); | |
| 1600 } | |
| 1601 } | |
| 1602 VP8LRefsCursorNext(&c); | |
| 1603 } | |
| 1604 VP8LColorCacheClear(&hashers); | |
| 1605 return 1; | |
| 1606 } | |
| 1607 | |
| 1608 static VP8LBackwardRefs* GetBackwardReferencesLowEffort( | |
| 1609 int width, int height, const uint32_t* const argb, | |
| 1610 int* const cache_bits, const VP8LHashChain* const hash_chain, | |
| 1611 VP8LBackwardRefs refs_array[2]) { | |
| 1612 VP8LBackwardRefs* refs_lz77 = &refs_array[0]; | |
| 1613 *cache_bits = 0; | |
| 1614 if (!BackwardReferencesLz77(width, height, argb, 0, hash_chain, refs_lz77)) { | |
| 1615 return NULL; | |
| 1616 } | |
| 1617 BackwardReferences2DLocality(width, refs_lz77); | |
| 1618 return refs_lz77; | |
| 1619 } | |
| 1620 | |
| 1621 static VP8LBackwardRefs* GetBackwardReferences( | |
| 1622 int width, int height, const uint32_t* const argb, int quality, | |
| 1623 int* const cache_bits, const VP8LHashChain* const hash_chain, | |
| 1624 VP8LBackwardRefs refs_array[2]) { | |
| 1625 int lz77_is_useful; | |
| 1626 int lz77_computed; | |
| 1627 double bit_cost_lz77, bit_cost_rle; | |
| 1628 VP8LBackwardRefs* best = NULL; | |
| 1629 VP8LBackwardRefs* refs_lz77 = &refs_array[0]; | |
| 1630 VP8LBackwardRefs* refs_rle = &refs_array[1]; | |
| 1631 VP8LHistogram* histo = NULL; | |
| 1632 | |
| 1633 if (!CalculateBestCacheSize(argb, width, height, quality, hash_chain, | |
| 1634 refs_lz77, &lz77_computed, cache_bits)) { | |
| 1635 goto Error; | |
| 1636 } | |
| 1637 | |
| 1638 if (lz77_computed) { | |
| 1639 // Transform refs_lz77 for the optimized cache_bits. | |
| 1640 if (*cache_bits > 0) { | |
| 1641 if (!BackwardRefsWithLocalCache(argb, *cache_bits, refs_lz77)) { | |
| 1642 goto Error; | |
| 1643 } | |
| 1644 } | |
| 1645 } else { | |
| 1646 if (!BackwardReferencesLz77(width, height, argb, *cache_bits, hash_chain, | |
| 1647 refs_lz77)) { | |
| 1648 goto Error; | |
| 1649 } | |
| 1650 } | |
| 1651 | |
| 1652 if (!BackwardReferencesRle(width, height, argb, *cache_bits, refs_rle)) { | |
| 1653 goto Error; | |
| 1654 } | |
| 1655 | |
| 1656 histo = VP8LAllocateHistogram(*cache_bits); | |
| 1657 if (histo == NULL) goto Error; | |
| 1658 | |
| 1659 { | |
| 1660 // Evaluate LZ77 coding. | |
| 1661 VP8LHistogramCreate(histo, refs_lz77, *cache_bits); | |
| 1662 bit_cost_lz77 = VP8LHistogramEstimateBits(histo); | |
| 1663 // Evaluate RLE coding. | |
| 1664 VP8LHistogramCreate(histo, refs_rle, *cache_bits); | |
| 1665 bit_cost_rle = VP8LHistogramEstimateBits(histo); | |
| 1666 // Decide if LZ77 is useful. | |
| 1667 lz77_is_useful = (bit_cost_lz77 < bit_cost_rle); | |
| 1668 } | |
| 1669 | |
| 1670 // Choose appropriate backward reference. | |
| 1671 if (lz77_is_useful) { | |
| 1672 // TraceBackwards is costly. Don't execute it at lower quality. | |
| 1673 const int try_lz77_trace_backwards = (quality >= 25); | |
| 1674 best = refs_lz77; // default guess: lz77 is better | |
| 1675 if (try_lz77_trace_backwards) { | |
| 1676 VP8LBackwardRefs* const refs_trace = refs_rle; | |
| 1677 if (!VP8LBackwardRefsCopy(refs_lz77, refs_trace)) { | |
| 1678 best = NULL; | |
| 1679 goto Error; | |
| 1680 } | |
| 1681 if (BackwardReferencesTraceBackwards(width, height, argb, quality, | |
| 1682 *cache_bits, hash_chain, | |
| 1683 refs_trace)) { | |
| 1684 double bit_cost_trace; | |
| 1685 // Evaluate LZ77 coding. | |
| 1686 VP8LHistogramCreate(histo, refs_trace, *cache_bits); | |
| 1687 bit_cost_trace = VP8LHistogramEstimateBits(histo); | |
| 1688 if (bit_cost_trace < bit_cost_lz77) { | |
| 1689 best = refs_trace; | |
| 1690 } | |
| 1691 } | |
| 1692 } | |
| 1693 } else { | |
| 1694 best = refs_rle; | |
| 1695 } | |
| 1696 | |
| 1697 BackwardReferences2DLocality(width, best); | |
| 1698 | |
| 1699 Error: | |
| 1700 VP8LFreeHistogram(histo); | |
| 1701 return best; | |
| 1702 } | |
| 1703 | |
| 1704 VP8LBackwardRefs* VP8LGetBackwardReferences( | |
| 1705 int width, int height, const uint32_t* const argb, int quality, | |
| 1706 int low_effort, int* const cache_bits, | |
| 1707 const VP8LHashChain* const hash_chain, VP8LBackwardRefs refs_array[2]) { | |
| 1708 if (low_effort) { | |
| 1709 return GetBackwardReferencesLowEffort(width, height, argb, cache_bits, | |
| 1710 hash_chain, refs_array); | |
| 1711 } else { | |
| 1712 return GetBackwardReferences(width, height, argb, quality, cache_bits, | |
| 1713 hash_chain, refs_array); | |
| 1714 } | |
| 1715 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2651883004:
libwebp-0.6.0-rc1 (Closed)
