1 // Copyright 2012 Google Inc. All Rights Reserved. 2 // 3 // This code is licensed under the same terms as WebM: 4 // Software License Agreement: http://www.webmproject.org/license/software/ 5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 6 // ----------------------------------------------------------------------------- 7 // 8 // Author: Jyrki Alakuijala (jyrki (at) google.com) 9 // 10 11 #include <assert.h> 12 #include <math.h> 13 #include <stdio.h> 14 15 #include "./backward_references.h" 16 #include "./histogram.h" 17 #include "../dsp/lossless.h" 18 #include "../utils/color_cache.h" 19 #include "../utils/utils.h" 20 21 #define VALUES_IN_BYTE 256 22 23 #define HASH_BITS 18 24 #define HASH_SIZE (1 << HASH_BITS) 25 #define HASH_MULTIPLIER (0xc6a4a7935bd1e995ULL) 26 27 // 1M window (4M bytes) minus 120 special codes for short distances. 28 #define WINDOW_SIZE ((1 << 20) - 120) 29 30 // Bounds for the match length. 31 #define MIN_LENGTH 2 32 #define MAX_LENGTH 4096 33 34 typedef struct { 35 // Stores the most recently added position with the given hash value. 36 int32_t hash_to_first_index_[HASH_SIZE]; 37 // chain_[pos] stores the previous position with the same hash value 38 // for every pixel in the image. 39 int32_t* chain_; 40 } HashChain; 41 42 // ----------------------------------------------------------------------------- 43 44 static const uint8_t plane_to_code_lut[128] = { 45 96, 73, 55, 39, 23, 13, 5, 1, 255, 255, 255, 255, 255, 255, 255, 255, 46 101, 78, 58, 42, 26, 16, 8, 2, 0, 3, 9, 17, 27, 43, 59, 79, 47 102, 86, 62, 46, 32, 20, 10, 6, 4, 7, 11, 21, 33, 47, 63, 87, 48 105, 90, 70, 52, 37, 28, 18, 14, 12, 15, 19, 29, 38, 53, 71, 91, 49 110, 99, 82, 66, 48, 35, 30, 24, 22, 25, 31, 36, 49, 67, 83, 100, 50 115, 108, 94, 76, 64, 50, 44, 40, 34, 41, 45, 51, 65, 77, 95, 109, 51 118, 113, 103, 92, 80, 68, 60, 56, 54, 57, 61, 69, 81, 93, 104, 114, 52 119, 116, 111, 106, 97, 88, 84, 74, 72, 75, 85, 89, 98, 107, 112, 117 53 }; 54 55 static int DistanceToPlaneCode(int xsize, int dist) { 56 const int yoffset = dist / xsize; 57 const int xoffset = dist - yoffset * xsize; 58 if (xoffset <= 8 && yoffset < 8) { 59 return plane_to_code_lut[yoffset * 16 + 8 - xoffset] + 1; 60 } else if (xoffset > xsize - 8 && yoffset < 7) { 61 return plane_to_code_lut[(yoffset + 1) * 16 + 8 + (xsize - xoffset)] + 1; 62 } 63 return dist + 120; 64 } 65 66 static WEBP_INLINE int FindMatchLength(const uint32_t* const array1, 67 const uint32_t* const array2, 68 const int max_limit) { 69 int match_len = 0; 70 while (match_len < max_limit && array1[match_len] == array2[match_len]) { 71 ++match_len; 72 } 73 return match_len; 74 } 75 76 // ----------------------------------------------------------------------------- 77 // VP8LBackwardRefs 78 79 void VP8LInitBackwardRefs(VP8LBackwardRefs* const refs) { 80 if (refs != NULL) { 81 refs->refs = NULL; 82 refs->size = 0; 83 refs->max_size = 0; 84 } 85 } 86 87 void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs) { 88 if (refs != NULL) { 89 free(refs->refs); 90 VP8LInitBackwardRefs(refs); 91 } 92 } 93 94 int VP8LBackwardRefsAlloc(VP8LBackwardRefs* const refs, int max_size) { 95 assert(refs != NULL); 96 refs->size = 0; 97 refs->max_size = 0; 98 refs->refs = (PixOrCopy*)WebPSafeMalloc((uint64_t)max_size, 99 sizeof(*refs->refs)); 100 if (refs->refs == NULL) return 0; 101 refs->max_size = max_size; 102 return 1; 103 } 104 105 // ----------------------------------------------------------------------------- 106 // Hash chains 107 108 static WEBP_INLINE uint64_t GetPixPairHash64(const uint32_t* const argb) { 109 uint64_t key = ((uint64_t)(argb[1]) << 32) | argb[0]; 110 key = (key * HASH_MULTIPLIER) >> (64 - HASH_BITS); 111 return key; 112 } 113 114 static int HashChainInit(HashChain* const p, int size) { 115 int i; 116 p->chain_ = (int*)WebPSafeMalloc((uint64_t)size, sizeof(*p->chain_)); 117 if (p->chain_ == NULL) { 118 return 0; 119 } 120 for (i = 0; i < size; ++i) { 121 p->chain_[i] = -1; 122 } 123 for (i = 0; i < HASH_SIZE; ++i) { 124 p->hash_to_first_index_[i] = -1; 125 } 126 return 1; 127 } 128 129 static void HashChainDelete(HashChain* const p) { 130 if (p != NULL) { 131 free(p->chain_); 132 free(p); 133 } 134 } 135 136 // Insertion of two pixels at a time. 137 static void HashChainInsert(HashChain* const p, 138 const uint32_t* const argb, int pos) { 139 const uint64_t hash_code = GetPixPairHash64(argb); 140 p->chain_[pos] = p->hash_to_first_index_[hash_code]; 141 p->hash_to_first_index_[hash_code] = pos; 142 } 143 144 static int HashChainFindCopy(const HashChain* const p, 145 int quality, int index, int xsize, 146 const uint32_t* const argb, int maxlen, 147 int* const distance_ptr, 148 int* const length_ptr) { 149 const uint64_t hash_code = GetPixPairHash64(&argb[index]); 150 int prev_length = 0; 151 int64_t best_val = 0; 152 int best_length = 0; 153 int best_distance = 0; 154 const uint32_t* const argb_start = argb + index; 155 const int iter_min_mult = (quality < 50) ? 2 : (quality < 75) ? 4 : 8; 156 const int iter_min = -quality * iter_min_mult; 157 int iter_cnt = 10 + (quality >> 1); 158 const int min_pos = (index > WINDOW_SIZE) ? index - WINDOW_SIZE : 0; 159 int pos; 160 161 assert(xsize > 0); 162 for (pos = p->hash_to_first_index_[hash_code]; 163 pos >= min_pos; 164 pos = p->chain_[pos]) { 165 int64_t val; 166 int curr_length; 167 if (iter_cnt < 0) { 168 if (iter_cnt < iter_min || best_val >= 0xff0000) { 169 break; 170 } 171 } 172 --iter_cnt; 173 if (best_length != 0 && 174 argb[pos + best_length - 1] != argb_start[best_length - 1]) { 175 continue; 176 } 177 curr_length = FindMatchLength(argb + pos, argb_start, maxlen); 178 if (curr_length < prev_length) { 179 continue; 180 } 181 val = 65536 * curr_length; 182 // Favoring 2d locality here gives savings for certain images. 183 if (index - pos < 9 * xsize) { 184 const int y = (index - pos) / xsize; 185 int x = (index - pos) % xsize; 186 if (x > xsize / 2) { 187 x = xsize - x; 188 } 189 if (x <= 7 && x >= -8) { 190 val -= y * y + x * x; 191 } else { 192 val -= 9 * 9 + 9 * 9; 193 } 194 } else { 195 val -= 9 * 9 + 9 * 9; 196 } 197 if (best_val < val) { 198 prev_length = curr_length; 199 best_val = val; 200 best_length = curr_length; 201 best_distance = index - pos; 202 if (curr_length >= MAX_LENGTH) { 203 break; 204 } 205 if ((best_distance == 1 || best_distance == xsize) && 206 best_length >= 128) { 207 break; 208 } 209 } 210 } 211 *distance_ptr = best_distance; 212 *length_ptr = best_length; 213 return (best_length >= MIN_LENGTH); 214 } 215 216 static WEBP_INLINE void PushBackCopy(VP8LBackwardRefs* const refs, int length) { 217 int size = refs->size; 218 while (length >= MAX_LENGTH) { 219 refs->refs[size++] = PixOrCopyCreateCopy(1, MAX_LENGTH); 220 length -= MAX_LENGTH; 221 } 222 if (length > 0) { 223 refs->refs[size++] = PixOrCopyCreateCopy(1, length); 224 } 225 refs->size = size; 226 } 227 228 static void BackwardReferencesRle(int xsize, int ysize, 229 const uint32_t* const argb, 230 VP8LBackwardRefs* const refs) { 231 const int pix_count = xsize * ysize; 232 int match_len = 0; 233 int i; 234 refs->size = 0; 235 PushBackCopy(refs, match_len); // i=0 case 236 refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[0]); 237 for (i = 1; i < pix_count; ++i) { 238 if (argb[i] == argb[i - 1]) { 239 ++match_len; 240 } else { 241 PushBackCopy(refs, match_len); 242 match_len = 0; 243 refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[i]); 244 } 245 } 246 PushBackCopy(refs, match_len); 247 } 248 249 static int BackwardReferencesHashChain(int xsize, int ysize, 250 const uint32_t* const argb, 251 int cache_bits, int quality, 252 VP8LBackwardRefs* const refs) { 253 int i; 254 int ok = 0; 255 int cc_init = 0; 256 const int use_color_cache = (cache_bits > 0); 257 const int pix_count = xsize * ysize; 258 HashChain* const hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 259 VP8LColorCache hashers; 260 261 if (hash_chain == NULL) return 0; 262 if (use_color_cache) { 263 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 264 if (!cc_init) goto Error; 265 } 266 267 if (!HashChainInit(hash_chain, pix_count)) goto Error; 268 269 refs->size = 0; 270 for (i = 0; i < pix_count; ) { 271 // Alternative#1: Code the pixels starting at 'i' using backward reference. 272 int offset = 0; 273 int len = 0; 274 if (i < pix_count - 1) { // FindCopy(i,..) reads pixels at [i] and [i + 1]. 275 int maxlen = pix_count - i; 276 if (maxlen > MAX_LENGTH) { 277 maxlen = MAX_LENGTH; 278 } 279 HashChainFindCopy(hash_chain, quality, i, xsize, argb, maxlen, 280 &offset, &len); 281 } 282 if (len >= MIN_LENGTH) { 283 // Alternative#2: Insert the pixel at 'i' as literal, and code the 284 // pixels starting at 'i + 1' using backward reference. 285 int offset2 = 0; 286 int len2 = 0; 287 int k; 288 HashChainInsert(hash_chain, &argb[i], i); 289 if (i < pix_count - 2) { // FindCopy(i+1,..) reads [i + 1] and [i + 2]. 290 int maxlen = pix_count - (i + 1); 291 if (maxlen > MAX_LENGTH) { 292 maxlen = MAX_LENGTH; 293 } 294 HashChainFindCopy(hash_chain, quality, 295 i + 1, xsize, argb, maxlen, &offset2, &len2); 296 if (len2 > len + 1) { 297 const uint32_t pixel = argb[i]; 298 // Alternative#2 is a better match. So push pixel at 'i' as literal. 299 if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) { 300 const int ix = VP8LColorCacheGetIndex(&hashers, pixel); 301 refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix); 302 } else { 303 refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel); 304 } 305 ++refs->size; 306 if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel); 307 i++; // Backward reference to be done for next pixel. 308 len = len2; 309 offset = offset2; 310 } 311 } 312 if (len >= MAX_LENGTH) { 313 len = MAX_LENGTH - 1; 314 } 315 refs->refs[refs->size++] = PixOrCopyCreateCopy(offset, len); 316 if (use_color_cache) { 317 for (k = 0; k < len; ++k) { 318 VP8LColorCacheInsert(&hashers, argb[i + k]); 319 } 320 } 321 // Add to the hash_chain (but cannot add the last pixel). 322 { 323 const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i; 324 for (k = 1; k < last; ++k) { 325 HashChainInsert(hash_chain, &argb[i + k], i + k); 326 } 327 } 328 i += len; 329 } else { 330 const uint32_t pixel = argb[i]; 331 if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) { 332 // push pixel as a PixOrCopyCreateCacheIdx pixel 333 const int ix = VP8LColorCacheGetIndex(&hashers, pixel); 334 refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix); 335 } else { 336 refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel); 337 } 338 ++refs->size; 339 if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel); 340 if (i + 1 < pix_count) { 341 HashChainInsert(hash_chain, &argb[i], i); 342 } 343 ++i; 344 } 345 } 346 ok = 1; 347 Error: 348 if (cc_init) VP8LColorCacheClear(&hashers); 349 HashChainDelete(hash_chain); 350 return ok; 351 } 352 353 // ----------------------------------------------------------------------------- 354 355 typedef struct { 356 double alpha_[VALUES_IN_BYTE]; 357 double red_[VALUES_IN_BYTE]; 358 double literal_[PIX_OR_COPY_CODES_MAX]; 359 double blue_[VALUES_IN_BYTE]; 360 double distance_[NUM_DISTANCE_CODES]; 361 } CostModel; 362 363 static int BackwardReferencesTraceBackwards( 364 int xsize, int ysize, int recursive_cost_model, 365 const uint32_t* const argb, int cache_bits, VP8LBackwardRefs* const refs); 366 367 static void ConvertPopulationCountTableToBitEstimates( 368 int num_symbols, const int population_counts[], double output[]) { 369 int sum = 0; 370 int nonzeros = 0; 371 int i; 372 for (i = 0; i < num_symbols; ++i) { 373 sum += population_counts[i]; 374 if (population_counts[i] > 0) { 375 ++nonzeros; 376 } 377 } 378 if (nonzeros <= 1) { 379 memset(output, 0, num_symbols * sizeof(*output)); 380 } else { 381 const double logsum = VP8LFastLog2(sum); 382 for (i = 0; i < num_symbols; ++i) { 383 output[i] = logsum - VP8LFastLog2(population_counts[i]); 384 } 385 } 386 } 387 388 static int CostModelBuild(CostModel* const m, int xsize, int ysize, 389 int recursion_level, const uint32_t* const argb, 390 int cache_bits) { 391 int ok = 0; 392 VP8LHistogram histo; 393 VP8LBackwardRefs refs; 394 const int quality = 100; 395 396 if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize)) goto Error; 397 398 if (recursion_level > 0) { 399 if (!BackwardReferencesTraceBackwards(xsize, ysize, recursion_level - 1, 400 argb, cache_bits, &refs)) { 401 goto Error; 402 } 403 } else { 404 if (!BackwardReferencesHashChain(xsize, ysize, argb, cache_bits, quality, 405 &refs)) { 406 goto Error; 407 } 408 } 409 VP8LHistogramCreate(&histo, &refs, cache_bits); 410 ConvertPopulationCountTableToBitEstimates( 411 VP8LHistogramNumCodes(&histo), histo.literal_, m->literal_); 412 ConvertPopulationCountTableToBitEstimates( 413 VALUES_IN_BYTE, histo.red_, m->red_); 414 ConvertPopulationCountTableToBitEstimates( 415 VALUES_IN_BYTE, histo.blue_, m->blue_); 416 ConvertPopulationCountTableToBitEstimates( 417 VALUES_IN_BYTE, histo.alpha_, m->alpha_); 418 ConvertPopulationCountTableToBitEstimates( 419 NUM_DISTANCE_CODES, histo.distance_, m->distance_); 420 ok = 1; 421 422 Error: 423 VP8LClearBackwardRefs(&refs); 424 return ok; 425 } 426 427 static WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) { 428 return m->alpha_[v >> 24] + 429 m->red_[(v >> 16) & 0xff] + 430 m->literal_[(v >> 8) & 0xff] + 431 m->blue_[v & 0xff]; 432 } 433 434 static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) { 435 const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx; 436 return m->literal_[literal_idx]; 437 } 438 439 static WEBP_INLINE double GetLengthCost(const CostModel* const m, 440 uint32_t length) { 441 int code, extra_bits_count, extra_bits_value; 442 PrefixEncode(length, &code, &extra_bits_count, &extra_bits_value); 443 return m->literal_[VALUES_IN_BYTE + code] + extra_bits_count; 444 } 445 446 static WEBP_INLINE double GetDistanceCost(const CostModel* const m, 447 uint32_t distance) { 448 int code, extra_bits_count, extra_bits_value; 449 PrefixEncode(distance, &code, &extra_bits_count, &extra_bits_value); 450 return m->distance_[code] + extra_bits_count; 451 } 452 453 static int BackwardReferencesHashChainDistanceOnly( 454 int xsize, int ysize, int recursive_cost_model, const uint32_t* const argb, 455 int cache_bits, uint32_t* const dist_array) { 456 int i; 457 int ok = 0; 458 int cc_init = 0; 459 const int quality = 100; 460 const int pix_count = xsize * ysize; 461 const int use_color_cache = (cache_bits > 0); 462 double* const cost = 463 (double*)WebPSafeMalloc((uint64_t)pix_count, sizeof(*cost)); 464 CostModel* cost_model = (CostModel*)malloc(sizeof(*cost_model)); 465 HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 466 VP8LColorCache hashers; 467 const double mul0 = (recursive_cost_model != 0) ? 1.0 : 0.68; 468 const double mul1 = (recursive_cost_model != 0) ? 1.0 : 0.82; 469 470 if (cost == NULL || cost_model == NULL || hash_chain == NULL) goto Error; 471 472 if (!HashChainInit(hash_chain, pix_count)) goto Error; 473 474 if (use_color_cache) { 475 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 476 if (!cc_init) goto Error; 477 } 478 479 if (!CostModelBuild(cost_model, xsize, ysize, recursive_cost_model, argb, 480 cache_bits)) { 481 goto Error; 482 } 483 484 for (i = 0; i < pix_count; ++i) cost[i] = 1e100; 485 486 // We loop one pixel at a time, but store all currently best points to 487 // non-processed locations from this point. 488 dist_array[0] = 0; 489 for (i = 0; i < pix_count; ++i) { 490 double prev_cost = 0.0; 491 int shortmax; 492 if (i > 0) { 493 prev_cost = cost[i - 1]; 494 } 495 for (shortmax = 0; shortmax < 2; ++shortmax) { 496 int offset = 0; 497 int len = 0; 498 if (i < pix_count - 1) { // FindCopy reads pixels at [i] and [i + 1]. 499 int maxlen = shortmax ? 2 : MAX_LENGTH; 500 if (maxlen > pix_count - i) { 501 maxlen = pix_count - i; 502 } 503 HashChainFindCopy(hash_chain, quality, i, xsize, argb, maxlen, 504 &offset, &len); 505 } 506 if (len >= MIN_LENGTH) { 507 const int code = DistanceToPlaneCode(xsize, offset); 508 const double distance_cost = 509 prev_cost + GetDistanceCost(cost_model, code); 510 int k; 511 for (k = 1; k < len; ++k) { 512 const double cost_val = 513 distance_cost + GetLengthCost(cost_model, k); 514 if (cost[i + k] > cost_val) { 515 cost[i + k] = cost_val; 516 dist_array[i + k] = k + 1; 517 } 518 } 519 // This if is for speedup only. It roughly doubles the speed, and 520 // makes compression worse by .1 %. 521 if (len >= 128 && code < 2) { 522 // Long copy for short distances, let's skip the middle 523 // lookups for better copies. 524 // 1) insert the hashes. 525 if (use_color_cache) { 526 for (k = 0; k < len; ++k) { 527 VP8LColorCacheInsert(&hashers, argb[i + k]); 528 } 529 } 530 // 2) Add to the hash_chain (but cannot add the last pixel) 531 { 532 const int last = (len < pix_count - 1 - i) ? len 533 : pix_count - 1 - i; 534 for (k = 0; k < last; ++k) { 535 HashChainInsert(hash_chain, &argb[i + k], i + k); 536 } 537 } 538 // 3) jump. 539 i += len - 1; // for loop does ++i, thus -1 here. 540 goto next_symbol; 541 } 542 } 543 } 544 if (i < pix_count - 1) { 545 HashChainInsert(hash_chain, &argb[i], i); 546 } 547 { 548 // inserting a literal pixel 549 double cost_val = prev_cost; 550 if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { 551 const int ix = VP8LColorCacheGetIndex(&hashers, argb[i]); 552 cost_val += GetCacheCost(cost_model, ix) * mul0; 553 } else { 554 cost_val += GetLiteralCost(cost_model, argb[i]) * mul1; 555 } 556 if (cost[i] > cost_val) { 557 cost[i] = cost_val; 558 dist_array[i] = 1; // only one is inserted. 559 } 560 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 561 } 562 next_symbol: ; 563 } 564 // Last pixel still to do, it can only be a single step if not reached 565 // through cheaper means already. 566 ok = 1; 567 Error: 568 if (cc_init) VP8LColorCacheClear(&hashers); 569 HashChainDelete(hash_chain); 570 free(cost_model); 571 free(cost); 572 return ok; 573 } 574 575 static int TraceBackwards(const uint32_t* const dist_array, 576 int dist_array_size, 577 uint32_t** const chosen_path, 578 int* const chosen_path_size) { 579 int i; 580 // Count how many. 581 int count = 0; 582 for (i = dist_array_size - 1; i >= 0; ) { 583 int k = dist_array[i]; 584 assert(k >= 1); 585 ++count; 586 i -= k; 587 } 588 // Allocate. 589 *chosen_path_size = count; 590 *chosen_path = 591 (uint32_t*)WebPSafeMalloc((uint64_t)count, sizeof(**chosen_path)); 592 if (*chosen_path == NULL) return 0; 593 594 // Write in reverse order. 595 for (i = dist_array_size - 1; i >= 0; ) { 596 int k = dist_array[i]; 597 assert(k >= 1); 598 (*chosen_path)[--count] = k; 599 i -= k; 600 } 601 return 1; 602 } 603 604 static int BackwardReferencesHashChainFollowChosenPath( 605 int xsize, int ysize, const uint32_t* const argb, int cache_bits, 606 const uint32_t* const chosen_path, int chosen_path_size, 607 VP8LBackwardRefs* const refs) { 608 const int quality = 100; 609 const int pix_count = xsize * ysize; 610 const int use_color_cache = (cache_bits > 0); 611 int size = 0; 612 int i = 0; 613 int k; 614 int ix; 615 int ok = 0; 616 int cc_init = 0; 617 HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 618 VP8LColorCache hashers; 619 620 if (hash_chain == NULL || !HashChainInit(hash_chain, pix_count)) { 621 goto Error; 622 } 623 if (use_color_cache) { 624 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 625 if (!cc_init) goto Error; 626 } 627 628 refs->size = 0; 629 for (ix = 0; ix < chosen_path_size; ++ix, ++size) { 630 int offset = 0; 631 int len = 0; 632 int maxlen = chosen_path[ix]; 633 if (maxlen != 1) { 634 HashChainFindCopy(hash_chain, quality, 635 i, xsize, argb, maxlen, &offset, &len); 636 assert(len == maxlen); 637 refs->refs[size] = PixOrCopyCreateCopy(offset, len); 638 if (use_color_cache) { 639 for (k = 0; k < len; ++k) { 640 VP8LColorCacheInsert(&hashers, argb[i + k]); 641 } 642 } 643 { 644 const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i; 645 for (k = 0; k < last; ++k) { 646 HashChainInsert(hash_chain, &argb[i + k], i + k); 647 } 648 } 649 i += len; 650 } else { 651 if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { 652 // push pixel as a color cache index 653 const int idx = VP8LColorCacheGetIndex(&hashers, argb[i]); 654 refs->refs[size] = PixOrCopyCreateCacheIdx(idx); 655 } else { 656 refs->refs[size] = PixOrCopyCreateLiteral(argb[i]); 657 } 658 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 659 if (i + 1 < pix_count) { 660 HashChainInsert(hash_chain, &argb[i], i); 661 } 662 ++i; 663 } 664 } 665 assert(size <= refs->max_size); 666 refs->size = size; 667 ok = 1; 668 Error: 669 if (cc_init) VP8LColorCacheClear(&hashers); 670 HashChainDelete(hash_chain); 671 return ok; 672 } 673 674 // Returns 1 on success. 675 static int BackwardReferencesTraceBackwards(int xsize, int ysize, 676 int recursive_cost_model, 677 const uint32_t* const argb, 678 int cache_bits, 679 VP8LBackwardRefs* const refs) { 680 int ok = 0; 681 const int dist_array_size = xsize * ysize; 682 uint32_t* chosen_path = NULL; 683 int chosen_path_size = 0; 684 uint32_t* dist_array = 685 (uint32_t*)WebPSafeMalloc((uint64_t)dist_array_size, sizeof(*dist_array)); 686 687 if (dist_array == NULL) goto Error; 688 689 if (!BackwardReferencesHashChainDistanceOnly( 690 xsize, ysize, recursive_cost_model, argb, cache_bits, dist_array)) { 691 goto Error; 692 } 693 if (!TraceBackwards(dist_array, dist_array_size, 694 &chosen_path, &chosen_path_size)) { 695 goto Error; 696 } 697 free(dist_array); // no need to retain this memory any longer 698 dist_array = NULL; 699 if (!BackwardReferencesHashChainFollowChosenPath( 700 xsize, ysize, argb, cache_bits, chosen_path, chosen_path_size, refs)) { 701 goto Error; 702 } 703 ok = 1; 704 Error: 705 free(chosen_path); 706 free(dist_array); 707 return ok; 708 } 709 710 static void BackwardReferences2DLocality(int xsize, 711 VP8LBackwardRefs* const refs) { 712 int i; 713 for (i = 0; i < refs->size; ++i) { 714 if (PixOrCopyIsCopy(&refs->refs[i])) { 715 const int dist = refs->refs[i].argb_or_distance; 716 const int transformed_dist = DistanceToPlaneCode(xsize, dist); 717 refs->refs[i].argb_or_distance = transformed_dist; 718 } 719 } 720 } 721 722 int VP8LGetBackwardReferences(int width, int height, 723 const uint32_t* const argb, 724 int quality, int cache_bits, int use_2d_locality, 725 VP8LBackwardRefs* const best) { 726 int ok = 0; 727 int lz77_is_useful; 728 VP8LBackwardRefs refs_rle, refs_lz77; 729 const int num_pix = width * height; 730 731 VP8LBackwardRefsAlloc(&refs_rle, num_pix); 732 VP8LBackwardRefsAlloc(&refs_lz77, num_pix); 733 VP8LInitBackwardRefs(best); 734 if (refs_rle.refs == NULL || refs_lz77.refs == NULL) { 735 Error1: 736 VP8LClearBackwardRefs(&refs_rle); 737 VP8LClearBackwardRefs(&refs_lz77); 738 goto End; 739 } 740 741 if (!BackwardReferencesHashChain(width, height, argb, cache_bits, quality, 742 &refs_lz77)) { 743 goto End; 744 } 745 // Backward Reference using RLE only. 746 BackwardReferencesRle(width, height, argb, &refs_rle); 747 748 { 749 double bit_cost_lz77, bit_cost_rle; 750 VP8LHistogram* const histo = (VP8LHistogram*)malloc(sizeof(*histo)); 751 if (histo == NULL) goto Error1; 752 // Evaluate lz77 coding 753 VP8LHistogramCreate(histo, &refs_lz77, cache_bits); 754 bit_cost_lz77 = VP8LHistogramEstimateBits(histo); 755 // Evaluate RLE coding 756 VP8LHistogramCreate(histo, &refs_rle, cache_bits); 757 bit_cost_rle = VP8LHistogramEstimateBits(histo); 758 // Decide if LZ77 is useful. 759 lz77_is_useful = (bit_cost_lz77 < bit_cost_rle); 760 free(histo); 761 } 762 763 // Choose appropriate backward reference. 764 if (lz77_is_useful) { 765 // TraceBackwards is costly. Run it for higher qualities. 766 const int try_lz77_trace_backwards = (quality >= 75); 767 *best = refs_lz77; // default guess: lz77 is better 768 VP8LClearBackwardRefs(&refs_rle); 769 if (try_lz77_trace_backwards) { 770 const int recursion_level = (num_pix < 320 * 200) ? 1 : 0; 771 VP8LBackwardRefs refs_trace; 772 if (!VP8LBackwardRefsAlloc(&refs_trace, num_pix)) { 773 goto End; 774 } 775 if (BackwardReferencesTraceBackwards( 776 width, height, recursion_level, argb, cache_bits, &refs_trace)) { 777 VP8LClearBackwardRefs(&refs_lz77); 778 *best = refs_trace; 779 } 780 } 781 } else { 782 VP8LClearBackwardRefs(&refs_lz77); 783 *best = refs_rle; 784 } 785 786 if (use_2d_locality) BackwardReferences2DLocality(width, best); 787 788 ok = 1; 789 790 End: 791 if (!ok) { 792 VP8LClearBackwardRefs(best); 793 } 794 return ok; 795 } 796 797 // Returns 1 on success. 798 static int ComputeCacheHistogram(const uint32_t* const argb, 799 int xsize, int ysize, 800 const VP8LBackwardRefs* const refs, 801 int cache_bits, 802 VP8LHistogram* const histo) { 803 int pixel_index = 0; 804 int i; 805 uint32_t k; 806 VP8LColorCache hashers; 807 const int use_color_cache = (cache_bits > 0); 808 int cc_init = 0; 809 810 if (use_color_cache) { 811 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 812 if (!cc_init) return 0; 813 } 814 815 for (i = 0; i < refs->size; ++i) { 816 const PixOrCopy* const v = &refs->refs[i]; 817 if (PixOrCopyIsLiteral(v)) { 818 if (use_color_cache && 819 VP8LColorCacheContains(&hashers, argb[pixel_index])) { 820 // push pixel as a cache index 821 const int ix = VP8LColorCacheGetIndex(&hashers, argb[pixel_index]); 822 const PixOrCopy token = PixOrCopyCreateCacheIdx(ix); 823 VP8LHistogramAddSinglePixOrCopy(histo, &token); 824 } else { 825 VP8LHistogramAddSinglePixOrCopy(histo, v); 826 } 827 } else { 828 VP8LHistogramAddSinglePixOrCopy(histo, v); 829 } 830 if (use_color_cache) { 831 for (k = 0; k < PixOrCopyLength(v); ++k) { 832 VP8LColorCacheInsert(&hashers, argb[pixel_index + k]); 833 } 834 } 835 pixel_index += PixOrCopyLength(v); 836 } 837 assert(pixel_index == xsize * ysize); 838 (void)xsize; // xsize is not used in non-debug compilations otherwise. 839 (void)ysize; // ysize is not used in non-debug compilations otherwise. 840 if (cc_init) VP8LColorCacheClear(&hashers); 841 return 1; 842 } 843 844 // Returns how many bits are to be used for a color cache. 845 int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb, 846 int xsize, int ysize, 847 int* const best_cache_bits) { 848 int ok = 0; 849 int cache_bits; 850 double lowest_entropy = 1e99; 851 VP8LBackwardRefs refs; 852 static const double kSmallPenaltyForLargeCache = 4.0; 853 static const int quality = 30; 854 if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize) || 855 !BackwardReferencesHashChain(xsize, ysize, argb, 0, quality, &refs)) { 856 goto Error; 857 } 858 for (cache_bits = 0; cache_bits <= MAX_COLOR_CACHE_BITS; ++cache_bits) { 859 double cur_entropy; 860 VP8LHistogram histo; 861 VP8LHistogramInit(&histo, cache_bits); 862 ComputeCacheHistogram(argb, xsize, ysize, &refs, cache_bits, &histo); 863 cur_entropy = VP8LHistogramEstimateBits(&histo) + 864 kSmallPenaltyForLargeCache * cache_bits; 865 if (cache_bits == 0 || cur_entropy < lowest_entropy) { 866 *best_cache_bits = cache_bits; 867 lowest_entropy = cur_entropy; 868 } 869 } 870 ok = 1; 871 Error: 872 VP8LClearBackwardRefs(&refs); 873 return ok; 874 } 875