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 void GetParamsForHashChainFindCopy(int quality, int xsize, 145 int* window_size, int* iter_pos, 146 int* iter_limit) { 147 const int iter_mult = (quality < 27) ? 1 : 1 + ((quality - 27) >> 4); 148 // Limit the backward-ref window size for lower qualities. 149 const int max_window_size = (quality > 50) ? WINDOW_SIZE 150 : (quality > 25) ? (xsize << 8) 151 : (xsize << 4); 152 assert(xsize > 0); 153 *window_size = (max_window_size > WINDOW_SIZE) ? WINDOW_SIZE 154 : max_window_size; 155 *iter_pos = 5 + (quality >> 3); 156 *iter_limit = -quality * iter_mult; 157 } 158 159 static int HashChainFindCopy(const HashChain* const p, 160 int base_position, int xsize, 161 const uint32_t* const argb, int maxlen, 162 int window_size, int iter_pos, int iter_limit, 163 int* const distance_ptr, 164 int* const length_ptr) { 165 const uint64_t hash_code = GetPixPairHash64(&argb[base_position]); 166 int prev_length = 0; 167 int64_t best_val = 0; 168 int best_length = 0; 169 int best_distance = 0; 170 const uint32_t* const argb_start = argb + base_position; 171 const int min_pos = 172 (base_position > window_size) ? base_position - window_size : 0; 173 int pos; 174 175 assert(xsize > 0); 176 for (pos = p->hash_to_first_index_[hash_code]; 177 pos >= min_pos; 178 pos = p->chain_[pos]) { 179 int64_t val; 180 int curr_length; 181 if (iter_pos < 0) { 182 if (iter_pos < iter_limit || best_val >= 0xff0000) { 183 break; 184 } 185 } 186 --iter_pos; 187 if (best_length != 0 && 188 argb[pos + best_length - 1] != argb_start[best_length - 1]) { 189 continue; 190 } 191 curr_length = FindMatchLength(argb + pos, argb_start, maxlen); 192 if (curr_length < prev_length) { 193 continue; 194 } 195 val = 65536 * curr_length; 196 // Favoring 2d locality here gives savings for certain images. 197 if (base_position - pos < 9 * xsize) { 198 const int y = (base_position - pos) / xsize; 199 int x = (base_position - pos) % xsize; 200 if (x > xsize / 2) { 201 x = xsize - x; 202 } 203 if (x <= 7 && x >= -8) { 204 val -= y * y + x * x; 205 } else { 206 val -= 9 * 9 + 9 * 9; 207 } 208 } else { 209 val -= 9 * 9 + 9 * 9; 210 } 211 if (best_val < val) { 212 prev_length = curr_length; 213 best_val = val; 214 best_length = curr_length; 215 best_distance = base_position - pos; 216 if (curr_length >= MAX_LENGTH) { 217 break; 218 } 219 if ((best_distance == 1 || best_distance == xsize) && 220 best_length >= 128) { 221 break; 222 } 223 } 224 } 225 *distance_ptr = best_distance; 226 *length_ptr = best_length; 227 return (best_length >= MIN_LENGTH); 228 } 229 230 static WEBP_INLINE void PushBackCopy(VP8LBackwardRefs* const refs, int length) { 231 int size = refs->size; 232 while (length >= MAX_LENGTH) { 233 refs->refs[size++] = PixOrCopyCreateCopy(1, MAX_LENGTH); 234 length -= MAX_LENGTH; 235 } 236 if (length > 0) { 237 refs->refs[size++] = PixOrCopyCreateCopy(1, length); 238 } 239 refs->size = size; 240 } 241 242 static void BackwardReferencesRle(int xsize, int ysize, 243 const uint32_t* const argb, 244 VP8LBackwardRefs* const refs) { 245 const int pix_count = xsize * ysize; 246 int match_len = 0; 247 int i; 248 refs->size = 0; 249 PushBackCopy(refs, match_len); // i=0 case 250 refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[0]); 251 for (i = 1; i < pix_count; ++i) { 252 if (argb[i] == argb[i - 1]) { 253 ++match_len; 254 } else { 255 PushBackCopy(refs, match_len); 256 match_len = 0; 257 refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[i]); 258 } 259 } 260 PushBackCopy(refs, match_len); 261 } 262 263 static int BackwardReferencesHashChain(int xsize, int ysize, 264 const uint32_t* const argb, 265 int cache_bits, int quality, 266 VP8LBackwardRefs* const refs) { 267 int i; 268 int ok = 0; 269 int cc_init = 0; 270 const int use_color_cache = (cache_bits > 0); 271 const int pix_count = xsize * ysize; 272 HashChain* const hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 273 VP8LColorCache hashers; 274 int window_size = WINDOW_SIZE; 275 int iter_pos = 1; 276 int iter_limit = -1; 277 278 if (hash_chain == NULL) return 0; 279 if (use_color_cache) { 280 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 281 if (!cc_init) goto Error; 282 } 283 284 if (!HashChainInit(hash_chain, pix_count)) goto Error; 285 286 refs->size = 0; 287 GetParamsForHashChainFindCopy(quality, xsize, &window_size, &iter_pos, 288 &iter_limit); 289 for (i = 0; i < pix_count; ) { 290 // Alternative#1: Code the pixels starting at 'i' using backward reference. 291 int offset = 0; 292 int len = 0; 293 if (i < pix_count - 1) { // FindCopy(i,..) reads pixels at [i] and [i + 1]. 294 int maxlen = pix_count - i; 295 if (maxlen > MAX_LENGTH) { 296 maxlen = MAX_LENGTH; 297 } 298 HashChainFindCopy(hash_chain, i, xsize, argb, maxlen, 299 window_size, iter_pos, iter_limit, 300 &offset, &len); 301 } 302 if (len >= MIN_LENGTH) { 303 // Alternative#2: Insert the pixel at 'i' as literal, and code the 304 // pixels starting at 'i + 1' using backward reference. 305 int offset2 = 0; 306 int len2 = 0; 307 int k; 308 HashChainInsert(hash_chain, &argb[i], i); 309 if (i < pix_count - 2) { // FindCopy(i+1,..) reads [i + 1] and [i + 2]. 310 int maxlen = pix_count - (i + 1); 311 if (maxlen > MAX_LENGTH) { 312 maxlen = MAX_LENGTH; 313 } 314 HashChainFindCopy(hash_chain, i + 1, xsize, argb, maxlen, 315 window_size, iter_pos, iter_limit, 316 &offset2, &len2); 317 if (len2 > len + 1) { 318 const uint32_t pixel = argb[i]; 319 // Alternative#2 is a better match. So push pixel at 'i' as literal. 320 if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) { 321 const int ix = VP8LColorCacheGetIndex(&hashers, pixel); 322 refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix); 323 } else { 324 refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel); 325 } 326 ++refs->size; 327 if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel); 328 i++; // Backward reference to be done for next pixel. 329 len = len2; 330 offset = offset2; 331 } 332 } 333 if (len >= MAX_LENGTH) { 334 len = MAX_LENGTH - 1; 335 } 336 refs->refs[refs->size++] = PixOrCopyCreateCopy(offset, len); 337 if (use_color_cache) { 338 for (k = 0; k < len; ++k) { 339 VP8LColorCacheInsert(&hashers, argb[i + k]); 340 } 341 } 342 // Add to the hash_chain (but cannot add the last pixel). 343 { 344 const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i; 345 for (k = 1; k < last; ++k) { 346 HashChainInsert(hash_chain, &argb[i + k], i + k); 347 } 348 } 349 i += len; 350 } else { 351 const uint32_t pixel = argb[i]; 352 if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) { 353 // push pixel as a PixOrCopyCreateCacheIdx pixel 354 const int ix = VP8LColorCacheGetIndex(&hashers, pixel); 355 refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix); 356 } else { 357 refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel); 358 } 359 ++refs->size; 360 if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel); 361 if (i + 1 < pix_count) { 362 HashChainInsert(hash_chain, &argb[i], i); 363 } 364 ++i; 365 } 366 } 367 ok = 1; 368 Error: 369 if (cc_init) VP8LColorCacheClear(&hashers); 370 HashChainDelete(hash_chain); 371 return ok; 372 } 373 374 // ----------------------------------------------------------------------------- 375 376 typedef struct { 377 double alpha_[VALUES_IN_BYTE]; 378 double red_[VALUES_IN_BYTE]; 379 double literal_[PIX_OR_COPY_CODES_MAX]; 380 double blue_[VALUES_IN_BYTE]; 381 double distance_[NUM_DISTANCE_CODES]; 382 } CostModel; 383 384 static int BackwardReferencesTraceBackwards( 385 int xsize, int ysize, int recursive_cost_model, 386 const uint32_t* const argb, int quality, int cache_bits, 387 VP8LBackwardRefs* const refs); 388 389 static void ConvertPopulationCountTableToBitEstimates( 390 int num_symbols, const int population_counts[], double output[]) { 391 int sum = 0; 392 int nonzeros = 0; 393 int i; 394 for (i = 0; i < num_symbols; ++i) { 395 sum += population_counts[i]; 396 if (population_counts[i] > 0) { 397 ++nonzeros; 398 } 399 } 400 if (nonzeros <= 1) { 401 memset(output, 0, num_symbols * sizeof(*output)); 402 } else { 403 const double logsum = VP8LFastLog2(sum); 404 for (i = 0; i < num_symbols; ++i) { 405 output[i] = logsum - VP8LFastLog2(population_counts[i]); 406 } 407 } 408 } 409 410 static int CostModelBuild(CostModel* const m, int xsize, int ysize, 411 int recursion_level, const uint32_t* const argb, 412 int quality, int cache_bits) { 413 int ok = 0; 414 VP8LHistogram histo; 415 VP8LBackwardRefs refs; 416 417 if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize)) goto Error; 418 419 if (recursion_level > 0) { 420 if (!BackwardReferencesTraceBackwards(xsize, ysize, recursion_level - 1, 421 argb, quality, cache_bits, &refs)) { 422 goto Error; 423 } 424 } else { 425 if (!BackwardReferencesHashChain(xsize, ysize, argb, cache_bits, quality, 426 &refs)) { 427 goto Error; 428 } 429 } 430 VP8LHistogramCreate(&histo, &refs, cache_bits); 431 ConvertPopulationCountTableToBitEstimates( 432 VP8LHistogramNumCodes(&histo), histo.literal_, m->literal_); 433 ConvertPopulationCountTableToBitEstimates( 434 VALUES_IN_BYTE, histo.red_, m->red_); 435 ConvertPopulationCountTableToBitEstimates( 436 VALUES_IN_BYTE, histo.blue_, m->blue_); 437 ConvertPopulationCountTableToBitEstimates( 438 VALUES_IN_BYTE, histo.alpha_, m->alpha_); 439 ConvertPopulationCountTableToBitEstimates( 440 NUM_DISTANCE_CODES, histo.distance_, m->distance_); 441 ok = 1; 442 443 Error: 444 VP8LClearBackwardRefs(&refs); 445 return ok; 446 } 447 448 static WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) { 449 return m->alpha_[v >> 24] + 450 m->red_[(v >> 16) & 0xff] + 451 m->literal_[(v >> 8) & 0xff] + 452 m->blue_[v & 0xff]; 453 } 454 455 static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) { 456 const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx; 457 return m->literal_[literal_idx]; 458 } 459 460 static WEBP_INLINE double GetLengthCost(const CostModel* const m, 461 uint32_t length) { 462 int code, extra_bits_count, extra_bits_value; 463 PrefixEncode(length, &code, &extra_bits_count, &extra_bits_value); 464 return m->literal_[VALUES_IN_BYTE + code] + extra_bits_count; 465 } 466 467 static WEBP_INLINE double GetDistanceCost(const CostModel* const m, 468 uint32_t distance) { 469 int code, extra_bits_count, extra_bits_value; 470 PrefixEncode(distance, &code, &extra_bits_count, &extra_bits_value); 471 return m->distance_[code] + extra_bits_count; 472 } 473 474 static int BackwardReferencesHashChainDistanceOnly( 475 int xsize, int ysize, int recursive_cost_model, const uint32_t* const argb, 476 int quality, int cache_bits, uint32_t* const dist_array) { 477 int i; 478 int ok = 0; 479 int cc_init = 0; 480 const int pix_count = xsize * ysize; 481 const int use_color_cache = (cache_bits > 0); 482 float* const cost = 483 (float*)WebPSafeMalloc((uint64_t)pix_count, sizeof(*cost)); 484 CostModel* cost_model = (CostModel*)malloc(sizeof(*cost_model)); 485 HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 486 VP8LColorCache hashers; 487 const double mul0 = (recursive_cost_model != 0) ? 1.0 : 0.68; 488 const double mul1 = (recursive_cost_model != 0) ? 1.0 : 0.82; 489 const int min_distance_code = 2; // TODO(vikasa): tune as function of quality 490 int window_size = WINDOW_SIZE; 491 int iter_pos = 1; 492 int iter_limit = -1; 493 494 if (cost == NULL || cost_model == NULL || hash_chain == NULL) goto Error; 495 496 if (!HashChainInit(hash_chain, pix_count)) goto Error; 497 498 if (use_color_cache) { 499 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 500 if (!cc_init) goto Error; 501 } 502 503 if (!CostModelBuild(cost_model, xsize, ysize, recursive_cost_model, argb, 504 quality, cache_bits)) { 505 goto Error; 506 } 507 508 for (i = 0; i < pix_count; ++i) cost[i] = 1e38f; 509 510 // We loop one pixel at a time, but store all currently best points to 511 // non-processed locations from this point. 512 dist_array[0] = 0; 513 GetParamsForHashChainFindCopy(quality, xsize, &window_size, &iter_pos, 514 &iter_limit); 515 for (i = 0; i < pix_count; ++i) { 516 double prev_cost = 0.0; 517 int shortmax; 518 if (i > 0) { 519 prev_cost = cost[i - 1]; 520 } 521 for (shortmax = 0; shortmax < 2; ++shortmax) { 522 int offset = 0; 523 int len = 0; 524 if (i < pix_count - 1) { // FindCopy reads pixels at [i] and [i + 1]. 525 int maxlen = shortmax ? 2 : MAX_LENGTH; 526 if (maxlen > pix_count - i) { 527 maxlen = pix_count - i; 528 } 529 HashChainFindCopy(hash_chain, i, xsize, argb, maxlen, 530 window_size, iter_pos, iter_limit, 531 &offset, &len); 532 } 533 if (len >= MIN_LENGTH) { 534 const int code = DistanceToPlaneCode(xsize, offset); 535 const double distance_cost = 536 prev_cost + GetDistanceCost(cost_model, code); 537 int k; 538 for (k = 1; k < len; ++k) { 539 const double cost_val = distance_cost + GetLengthCost(cost_model, k); 540 if (cost[i + k] > cost_val) { 541 cost[i + k] = (float)cost_val; 542 dist_array[i + k] = k + 1; 543 } 544 } 545 // This if is for speedup only. It roughly doubles the speed, and 546 // makes compression worse by .1 %. 547 if (len >= 128 && code <= min_distance_code) { 548 // Long copy for short distances, let's skip the middle 549 // lookups for better copies. 550 // 1) insert the hashes. 551 if (use_color_cache) { 552 for (k = 0; k < len; ++k) { 553 VP8LColorCacheInsert(&hashers, argb[i + k]); 554 } 555 } 556 // 2) Add to the hash_chain (but cannot add the last pixel) 557 { 558 const int last = (len + i < pix_count - 1) ? len + i 559 : pix_count - 1; 560 for (k = i; k < last; ++k) { 561 HashChainInsert(hash_chain, &argb[k], k); 562 } 563 } 564 // 3) jump. 565 i += len - 1; // for loop does ++i, thus -1 here. 566 goto next_symbol; 567 } 568 } 569 } 570 if (i < pix_count - 1) { 571 HashChainInsert(hash_chain, &argb[i], i); 572 } 573 { 574 // inserting a literal pixel 575 double cost_val = prev_cost; 576 if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { 577 const int ix = VP8LColorCacheGetIndex(&hashers, argb[i]); 578 cost_val += GetCacheCost(cost_model, ix) * mul0; 579 } else { 580 cost_val += GetLiteralCost(cost_model, argb[i]) * mul1; 581 } 582 if (cost[i] > cost_val) { 583 cost[i] = (float)cost_val; 584 dist_array[i] = 1; // only one is inserted. 585 } 586 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 587 } 588 next_symbol: ; 589 } 590 // Last pixel still to do, it can only be a single step if not reached 591 // through cheaper means already. 592 ok = 1; 593 Error: 594 if (cc_init) VP8LColorCacheClear(&hashers); 595 HashChainDelete(hash_chain); 596 free(cost_model); 597 free(cost); 598 return ok; 599 } 600 601 // We pack the path at the end of *dist_array and return 602 // a pointer to this part of the array. Example: 603 // dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232] 604 static void TraceBackwards(uint32_t* const dist_array, 605 int dist_array_size, 606 uint32_t** const chosen_path, 607 int* const chosen_path_size) { 608 uint32_t* path = dist_array + dist_array_size; 609 uint32_t* cur = dist_array + dist_array_size - 1; 610 while (cur >= dist_array) { 611 const int k = *cur; 612 --path; 613 *path = k; 614 cur -= k; 615 } 616 *chosen_path = path; 617 *chosen_path_size = (int)(dist_array + dist_array_size - path); 618 } 619 620 static int BackwardReferencesHashChainFollowChosenPath( 621 int xsize, int ysize, const uint32_t* const argb, 622 int quality, int cache_bits, 623 const uint32_t* const chosen_path, int chosen_path_size, 624 VP8LBackwardRefs* const refs) { 625 const int pix_count = xsize * ysize; 626 const int use_color_cache = (cache_bits > 0); 627 int size = 0; 628 int i = 0; 629 int k; 630 int ix; 631 int ok = 0; 632 int cc_init = 0; 633 int window_size = WINDOW_SIZE; 634 int iter_pos = 1; 635 int iter_limit = -1; 636 HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain)); 637 VP8LColorCache hashers; 638 639 if (hash_chain == NULL || !HashChainInit(hash_chain, pix_count)) { 640 goto Error; 641 } 642 if (use_color_cache) { 643 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 644 if (!cc_init) goto Error; 645 } 646 647 refs->size = 0; 648 GetParamsForHashChainFindCopy(quality, xsize, &window_size, &iter_pos, 649 &iter_limit); 650 for (ix = 0; ix < chosen_path_size; ++ix, ++size) { 651 int offset = 0; 652 int len = 0; 653 int maxlen = chosen_path[ix]; 654 if (maxlen != 1) { 655 HashChainFindCopy(hash_chain, i, xsize, argb, maxlen, 656 window_size, iter_pos, iter_limit, 657 &offset, &len); 658 assert(len == maxlen); 659 refs->refs[size] = PixOrCopyCreateCopy(offset, len); 660 if (use_color_cache) { 661 for (k = 0; k < len; ++k) { 662 VP8LColorCacheInsert(&hashers, argb[i + k]); 663 } 664 } 665 { 666 const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i; 667 for (k = 0; k < last; ++k) { 668 HashChainInsert(hash_chain, &argb[i + k], i + k); 669 } 670 } 671 i += len; 672 } else { 673 if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) { 674 // push pixel as a color cache index 675 const int idx = VP8LColorCacheGetIndex(&hashers, argb[i]); 676 refs->refs[size] = PixOrCopyCreateCacheIdx(idx); 677 } else { 678 refs->refs[size] = PixOrCopyCreateLiteral(argb[i]); 679 } 680 if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]); 681 if (i + 1 < pix_count) { 682 HashChainInsert(hash_chain, &argb[i], i); 683 } 684 ++i; 685 } 686 } 687 assert(size <= refs->max_size); 688 refs->size = size; 689 ok = 1; 690 Error: 691 if (cc_init) VP8LColorCacheClear(&hashers); 692 HashChainDelete(hash_chain); 693 return ok; 694 } 695 696 // Returns 1 on success. 697 static int BackwardReferencesTraceBackwards(int xsize, int ysize, 698 int recursive_cost_model, 699 const uint32_t* const argb, 700 int quality, int cache_bits, 701 VP8LBackwardRefs* const refs) { 702 int ok = 0; 703 const int dist_array_size = xsize * ysize; 704 uint32_t* chosen_path = NULL; 705 int chosen_path_size = 0; 706 uint32_t* dist_array = 707 (uint32_t*)WebPSafeMalloc((uint64_t)dist_array_size, sizeof(*dist_array)); 708 709 if (dist_array == NULL) goto Error; 710 711 if (!BackwardReferencesHashChainDistanceOnly( 712 xsize, ysize, recursive_cost_model, argb, quality, cache_bits, 713 dist_array)) { 714 goto Error; 715 } 716 TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size); 717 if (!BackwardReferencesHashChainFollowChosenPath( 718 xsize, ysize, argb, quality, cache_bits, chosen_path, chosen_path_size, 719 refs)) { 720 goto Error; 721 } 722 ok = 1; 723 Error: 724 free(dist_array); 725 return ok; 726 } 727 728 static void BackwardReferences2DLocality(int xsize, 729 VP8LBackwardRefs* const refs) { 730 int i; 731 for (i = 0; i < refs->size; ++i) { 732 if (PixOrCopyIsCopy(&refs->refs[i])) { 733 const int dist = refs->refs[i].argb_or_distance; 734 const int transformed_dist = DistanceToPlaneCode(xsize, dist); 735 refs->refs[i].argb_or_distance = transformed_dist; 736 } 737 } 738 } 739 740 int VP8LGetBackwardReferences(int width, int height, 741 const uint32_t* const argb, 742 int quality, int cache_bits, int use_2d_locality, 743 VP8LBackwardRefs* const best) { 744 int ok = 0; 745 int lz77_is_useful; 746 VP8LBackwardRefs refs_rle, refs_lz77; 747 const int num_pix = width * height; 748 749 VP8LBackwardRefsAlloc(&refs_rle, num_pix); 750 VP8LBackwardRefsAlloc(&refs_lz77, num_pix); 751 VP8LInitBackwardRefs(best); 752 if (refs_rle.refs == NULL || refs_lz77.refs == NULL) { 753 Error1: 754 VP8LClearBackwardRefs(&refs_rle); 755 VP8LClearBackwardRefs(&refs_lz77); 756 goto End; 757 } 758 759 if (!BackwardReferencesHashChain(width, height, argb, cache_bits, quality, 760 &refs_lz77)) { 761 goto End; 762 } 763 // Backward Reference using RLE only. 764 BackwardReferencesRle(width, height, argb, &refs_rle); 765 766 { 767 double bit_cost_lz77, bit_cost_rle; 768 VP8LHistogram* const histo = (VP8LHistogram*)malloc(sizeof(*histo)); 769 if (histo == NULL) goto Error1; 770 // Evaluate lz77 coding 771 VP8LHistogramCreate(histo, &refs_lz77, cache_bits); 772 bit_cost_lz77 = VP8LHistogramEstimateBits(histo); 773 // Evaluate RLE coding 774 VP8LHistogramCreate(histo, &refs_rle, cache_bits); 775 bit_cost_rle = VP8LHistogramEstimateBits(histo); 776 // Decide if LZ77 is useful. 777 lz77_is_useful = (bit_cost_lz77 < bit_cost_rle); 778 free(histo); 779 } 780 781 // Choose appropriate backward reference. 782 if (lz77_is_useful) { 783 // TraceBackwards is costly. Don't execute it at lower quality (q <= 10). 784 const int try_lz77_trace_backwards = (quality > 10); 785 *best = refs_lz77; // default guess: lz77 is better 786 VP8LClearBackwardRefs(&refs_rle); 787 if (try_lz77_trace_backwards) { 788 const int recursion_level = (num_pix < 320 * 200) ? 1 : 0; 789 VP8LBackwardRefs refs_trace; 790 if (!VP8LBackwardRefsAlloc(&refs_trace, num_pix)) { 791 goto End; 792 } 793 if (BackwardReferencesTraceBackwards(width, height, recursion_level, argb, 794 quality, cache_bits, &refs_trace)) { 795 VP8LClearBackwardRefs(&refs_lz77); 796 *best = refs_trace; 797 } 798 } 799 } else { 800 VP8LClearBackwardRefs(&refs_lz77); 801 *best = refs_rle; 802 } 803 804 if (use_2d_locality) BackwardReferences2DLocality(width, best); 805 806 ok = 1; 807 808 End: 809 if (!ok) { 810 VP8LClearBackwardRefs(best); 811 } 812 return ok; 813 } 814 815 // Returns 1 on success. 816 static int ComputeCacheHistogram(const uint32_t* const argb, 817 int xsize, int ysize, 818 const VP8LBackwardRefs* const refs, 819 int cache_bits, 820 VP8LHistogram* const histo) { 821 int pixel_index = 0; 822 int i; 823 uint32_t k; 824 VP8LColorCache hashers; 825 const int use_color_cache = (cache_bits > 0); 826 int cc_init = 0; 827 828 if (use_color_cache) { 829 cc_init = VP8LColorCacheInit(&hashers, cache_bits); 830 if (!cc_init) return 0; 831 } 832 833 for (i = 0; i < refs->size; ++i) { 834 const PixOrCopy* const v = &refs->refs[i]; 835 if (PixOrCopyIsLiteral(v)) { 836 if (use_color_cache && 837 VP8LColorCacheContains(&hashers, argb[pixel_index])) { 838 // push pixel as a cache index 839 const int ix = VP8LColorCacheGetIndex(&hashers, argb[pixel_index]); 840 const PixOrCopy token = PixOrCopyCreateCacheIdx(ix); 841 VP8LHistogramAddSinglePixOrCopy(histo, &token); 842 } else { 843 VP8LHistogramAddSinglePixOrCopy(histo, v); 844 } 845 } else { 846 VP8LHistogramAddSinglePixOrCopy(histo, v); 847 } 848 if (use_color_cache) { 849 for (k = 0; k < PixOrCopyLength(v); ++k) { 850 VP8LColorCacheInsert(&hashers, argb[pixel_index + k]); 851 } 852 } 853 pixel_index += PixOrCopyLength(v); 854 } 855 assert(pixel_index == xsize * ysize); 856 (void)xsize; // xsize is not used in non-debug compilations otherwise. 857 (void)ysize; // ysize is not used in non-debug compilations otherwise. 858 if (cc_init) VP8LColorCacheClear(&hashers); 859 return 1; 860 } 861 862 // Returns how many bits are to be used for a color cache. 863 int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb, 864 int xsize, int ysize, 865 int* const best_cache_bits) { 866 int ok = 0; 867 int cache_bits; 868 double lowest_entropy = 1e99; 869 VP8LBackwardRefs refs; 870 static const double kSmallPenaltyForLargeCache = 4.0; 871 static const int quality = 30; 872 if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize) || 873 !BackwardReferencesHashChain(xsize, ysize, argb, 0, quality, &refs)) { 874 goto Error; 875 } 876 for (cache_bits = 0; cache_bits <= MAX_COLOR_CACHE_BITS; ++cache_bits) { 877 double cur_entropy; 878 VP8LHistogram histo; 879 VP8LHistogramInit(&histo, cache_bits); 880 ComputeCacheHistogram(argb, xsize, ysize, &refs, cache_bits, &histo); 881 cur_entropy = VP8LHistogramEstimateBits(&histo) + 882 kSmallPenaltyForLargeCache * cache_bits; 883 if (cache_bits == 0 || cur_entropy < lowest_entropy) { 884 *best_cache_bits = cache_bits; 885 lowest_entropy = cur_entropy; 886 } 887 } 888 ok = 1; 889 Error: 890 VP8LClearBackwardRefs(&refs); 891 return ok; 892 } 893
