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 (at) google.com) 11 // 12 #ifdef HAVE_CONFIG_H 13 #include "config.h" 14 #endif 15 16 #include <math.h> 17 18 #include "./backward_references.h" 19 #include "./histogram.h" 20 #include "../dsp/lossless.h" 21 #include "../utils/utils.h" 22 23 #define MAX_COST 1.e38 24 25 // Number of partitions for the three dominant (literal, red and blue) symbol 26 // costs. 27 #define NUM_PARTITIONS 4 28 // The size of the bin-hash corresponding to the three dominant costs. 29 #define BIN_SIZE (NUM_PARTITIONS * NUM_PARTITIONS * NUM_PARTITIONS) 30 31 static void HistogramClear(VP8LHistogram* const p) { 32 uint32_t* const literal = p->literal_; 33 const int cache_bits = p->palette_code_bits_; 34 const int histo_size = VP8LGetHistogramSize(cache_bits); 35 memset(p, 0, histo_size); 36 p->palette_code_bits_ = cache_bits; 37 p->literal_ = literal; 38 } 39 40 static void HistogramCopy(const VP8LHistogram* const src, 41 VP8LHistogram* const dst) { 42 uint32_t* const dst_literal = dst->literal_; 43 const int dst_cache_bits = dst->palette_code_bits_; 44 const int histo_size = VP8LGetHistogramSize(dst_cache_bits); 45 assert(src->palette_code_bits_ == dst_cache_bits); 46 memcpy(dst, src, histo_size); 47 dst->literal_ = dst_literal; 48 } 49 50 int VP8LGetHistogramSize(int cache_bits) { 51 const int literal_size = VP8LHistogramNumCodes(cache_bits); 52 const size_t total_size = sizeof(VP8LHistogram) + sizeof(int) * literal_size; 53 assert(total_size <= (size_t)0x7fffffff); 54 return (int)total_size; 55 } 56 57 void VP8LFreeHistogram(VP8LHistogram* const histo) { 58 WebPSafeFree(histo); 59 } 60 61 void VP8LFreeHistogramSet(VP8LHistogramSet* const histo) { 62 WebPSafeFree(histo); 63 } 64 65 void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, 66 VP8LHistogram* const histo) { 67 VP8LRefsCursor c = VP8LRefsCursorInit(refs); 68 while (VP8LRefsCursorOk(&c)) { 69 VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos); 70 VP8LRefsCursorNext(&c); 71 } 72 } 73 74 void VP8LHistogramCreate(VP8LHistogram* const p, 75 const VP8LBackwardRefs* const refs, 76 int palette_code_bits) { 77 if (palette_code_bits >= 0) { 78 p->palette_code_bits_ = palette_code_bits; 79 } 80 HistogramClear(p); 81 VP8LHistogramStoreRefs(refs, p); 82 } 83 84 void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits) { 85 p->palette_code_bits_ = palette_code_bits; 86 HistogramClear(p); 87 } 88 89 VP8LHistogram* VP8LAllocateHistogram(int cache_bits) { 90 VP8LHistogram* histo = NULL; 91 const int total_size = VP8LGetHistogramSize(cache_bits); 92 uint8_t* const memory = (uint8_t*)WebPSafeMalloc(total_size, sizeof(*memory)); 93 if (memory == NULL) return NULL; 94 histo = (VP8LHistogram*)memory; 95 // literal_ won't necessary be aligned. 96 histo->literal_ = (uint32_t*)(memory + sizeof(VP8LHistogram)); 97 VP8LHistogramInit(histo, cache_bits); 98 return histo; 99 } 100 101 VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits) { 102 int i; 103 VP8LHistogramSet* set; 104 const size_t total_size = sizeof(*set) 105 + sizeof(*set->histograms) * size 106 + (size_t)VP8LGetHistogramSize(cache_bits) * size; 107 uint8_t* memory = (uint8_t*)WebPSafeMalloc(total_size, sizeof(*memory)); 108 if (memory == NULL) return NULL; 109 110 set = (VP8LHistogramSet*)memory; 111 memory += sizeof(*set); 112 set->histograms = (VP8LHistogram**)memory; 113 memory += size * sizeof(*set->histograms); 114 set->max_size = size; 115 set->size = size; 116 for (i = 0; i < size; ++i) { 117 set->histograms[i] = (VP8LHistogram*)memory; 118 // literal_ won't necessary be aligned. 119 set->histograms[i]->literal_ = (uint32_t*)(memory + sizeof(VP8LHistogram)); 120 VP8LHistogramInit(set->histograms[i], cache_bits); 121 // There's no padding/alignment between successive histograms. 122 memory += VP8LGetHistogramSize(cache_bits); 123 } 124 return set; 125 } 126 127 // ----------------------------------------------------------------------------- 128 129 void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, 130 const PixOrCopy* const v) { 131 if (PixOrCopyIsLiteral(v)) { 132 ++histo->alpha_[PixOrCopyLiteral(v, 3)]; 133 ++histo->red_[PixOrCopyLiteral(v, 2)]; 134 ++histo->literal_[PixOrCopyLiteral(v, 1)]; 135 ++histo->blue_[PixOrCopyLiteral(v, 0)]; 136 } else if (PixOrCopyIsCacheIdx(v)) { 137 const int literal_ix = 138 NUM_LITERAL_CODES + NUM_LENGTH_CODES + PixOrCopyCacheIdx(v); 139 ++histo->literal_[literal_ix]; 140 } else { 141 int code, extra_bits; 142 VP8LPrefixEncodeBits(PixOrCopyLength(v), &code, &extra_bits); 143 ++histo->literal_[NUM_LITERAL_CODES + code]; 144 VP8LPrefixEncodeBits(PixOrCopyDistance(v), &code, &extra_bits); 145 ++histo->distance_[code]; 146 } 147 } 148 149 static WEBP_INLINE double BitsEntropyRefine(int nonzeros, int sum, int max_val, 150 double retval) { 151 double mix; 152 if (nonzeros < 5) { 153 if (nonzeros <= 1) { 154 return 0; 155 } 156 // Two symbols, they will be 0 and 1 in a Huffman code. 157 // Let's mix in a bit of entropy to favor good clustering when 158 // distributions of these are combined. 159 if (nonzeros == 2) { 160 return 0.99 * sum + 0.01 * retval; 161 } 162 // No matter what the entropy says, we cannot be better than min_limit 163 // with Huffman coding. I am mixing a bit of entropy into the 164 // min_limit since it produces much better (~0.5 %) compression results 165 // perhaps because of better entropy clustering. 166 if (nonzeros == 3) { 167 mix = 0.95; 168 } else { 169 mix = 0.7; // nonzeros == 4. 170 } 171 } else { 172 mix = 0.627; 173 } 174 175 { 176 double min_limit = 2 * sum - max_val; 177 min_limit = mix * min_limit + (1.0 - mix) * retval; 178 return (retval < min_limit) ? min_limit : retval; 179 } 180 } 181 182 static double BitsEntropy(const uint32_t* const array, int n) { 183 double retval = 0.; 184 uint32_t sum = 0; 185 int nonzeros = 0; 186 uint32_t max_val = 0; 187 int i; 188 for (i = 0; i < n; ++i) { 189 if (array[i] != 0) { 190 sum += array[i]; 191 ++nonzeros; 192 retval -= VP8LFastSLog2(array[i]); 193 if (max_val < array[i]) { 194 max_val = array[i]; 195 } 196 } 197 } 198 retval += VP8LFastSLog2(sum); 199 return BitsEntropyRefine(nonzeros, sum, max_val, retval); 200 } 201 202 static double BitsEntropyCombined(const uint32_t* const X, 203 const uint32_t* const Y, int n) { 204 double retval = 0.; 205 int sum = 0; 206 int nonzeros = 0; 207 int max_val = 0; 208 int i; 209 for (i = 0; i < n; ++i) { 210 const int xy = X[i] + Y[i]; 211 if (xy != 0) { 212 sum += xy; 213 ++nonzeros; 214 retval -= VP8LFastSLog2(xy); 215 if (max_val < xy) { 216 max_val = xy; 217 } 218 } 219 } 220 retval += VP8LFastSLog2(sum); 221 return BitsEntropyRefine(nonzeros, sum, max_val, retval); 222 } 223 224 static double InitialHuffmanCost(void) { 225 // Small bias because Huffman code length is typically not stored in 226 // full length. 227 static const int kHuffmanCodeOfHuffmanCodeSize = CODE_LENGTH_CODES * 3; 228 static const double kSmallBias = 9.1; 229 return kHuffmanCodeOfHuffmanCodeSize - kSmallBias; 230 } 231 232 // Finalize the Huffman cost based on streak numbers and length type (<3 or >=3) 233 static double FinalHuffmanCost(const VP8LStreaks* const stats) { 234 double retval = InitialHuffmanCost(); 235 retval += stats->counts[0] * 1.5625 + 0.234375 * stats->streaks[0][1]; 236 retval += stats->counts[1] * 2.578125 + 0.703125 * stats->streaks[1][1]; 237 retval += 1.796875 * stats->streaks[0][0]; 238 retval += 3.28125 * stats->streaks[1][0]; 239 return retval; 240 } 241 242 // Trampolines 243 static double HuffmanCost(const uint32_t* const population, int length) { 244 const VP8LStreaks stats = VP8LHuffmanCostCount(population, length); 245 return FinalHuffmanCost(&stats); 246 } 247 248 static double HuffmanCostCombined(const uint32_t* const X, 249 const uint32_t* const Y, int length) { 250 const VP8LStreaks stats = VP8LHuffmanCostCombinedCount(X, Y, length); 251 return FinalHuffmanCost(&stats); 252 } 253 254 // Aggregated costs 255 static double PopulationCost(const uint32_t* const population, int length) { 256 return BitsEntropy(population, length) + HuffmanCost(population, length); 257 } 258 259 static double GetCombinedEntropy(const uint32_t* const X, 260 const uint32_t* const Y, int length) { 261 return BitsEntropyCombined(X, Y, length) + HuffmanCostCombined(X, Y, length); 262 } 263 264 // Estimates the Entropy + Huffman + other block overhead size cost. 265 double VP8LHistogramEstimateBits(const VP8LHistogram* const p) { 266 return 267 PopulationCost(p->literal_, VP8LHistogramNumCodes(p->palette_code_bits_)) 268 + PopulationCost(p->red_, NUM_LITERAL_CODES) 269 + PopulationCost(p->blue_, NUM_LITERAL_CODES) 270 + PopulationCost(p->alpha_, NUM_LITERAL_CODES) 271 + PopulationCost(p->distance_, NUM_DISTANCE_CODES) 272 + VP8LExtraCost(p->literal_ + NUM_LITERAL_CODES, NUM_LENGTH_CODES) 273 + VP8LExtraCost(p->distance_, NUM_DISTANCE_CODES); 274 } 275 276 double VP8LHistogramEstimateBitsBulk(const VP8LHistogram* const p) { 277 return 278 BitsEntropy(p->literal_, VP8LHistogramNumCodes(p->palette_code_bits_)) 279 + BitsEntropy(p->red_, NUM_LITERAL_CODES) 280 + BitsEntropy(p->blue_, NUM_LITERAL_CODES) 281 + BitsEntropy(p->alpha_, NUM_LITERAL_CODES) 282 + BitsEntropy(p->distance_, NUM_DISTANCE_CODES) 283 + VP8LExtraCost(p->literal_ + NUM_LITERAL_CODES, NUM_LENGTH_CODES) 284 + VP8LExtraCost(p->distance_, NUM_DISTANCE_CODES); 285 } 286 287 // ----------------------------------------------------------------------------- 288 // Various histogram combine/cost-eval functions 289 290 static int GetCombinedHistogramEntropy(const VP8LHistogram* const a, 291 const VP8LHistogram* const b, 292 double cost_threshold, 293 double* cost) { 294 const int palette_code_bits = a->palette_code_bits_; 295 assert(a->palette_code_bits_ == b->palette_code_bits_); 296 *cost += GetCombinedEntropy(a->literal_, b->literal_, 297 VP8LHistogramNumCodes(palette_code_bits)); 298 *cost += VP8LExtraCostCombined(a->literal_ + NUM_LITERAL_CODES, 299 b->literal_ + NUM_LITERAL_CODES, 300 NUM_LENGTH_CODES); 301 if (*cost > cost_threshold) return 0; 302 303 *cost += GetCombinedEntropy(a->red_, b->red_, NUM_LITERAL_CODES); 304 if (*cost > cost_threshold) return 0; 305 306 *cost += GetCombinedEntropy(a->blue_, b->blue_, NUM_LITERAL_CODES); 307 if (*cost > cost_threshold) return 0; 308 309 *cost += GetCombinedEntropy(a->alpha_, b->alpha_, NUM_LITERAL_CODES); 310 if (*cost > cost_threshold) return 0; 311 312 *cost += GetCombinedEntropy(a->distance_, b->distance_, NUM_DISTANCE_CODES); 313 *cost += VP8LExtraCostCombined(a->distance_, b->distance_, 314 NUM_DISTANCE_CODES); 315 if (*cost > cost_threshold) return 0; 316 317 return 1; 318 } 319 320 // Performs out = a + b, computing the cost C(a+b) - C(a) - C(b) while comparing 321 // to the threshold value 'cost_threshold'. The score returned is 322 // Score = C(a+b) - C(a) - C(b), where C(a) + C(b) is known and fixed. 323 // Since the previous score passed is 'cost_threshold', we only need to compare 324 // the partial cost against 'cost_threshold + C(a) + C(b)' to possibly bail-out 325 // early. 326 static double HistogramAddEval(const VP8LHistogram* const a, 327 const VP8LHistogram* const b, 328 VP8LHistogram* const out, 329 double cost_threshold) { 330 double cost = 0; 331 const double sum_cost = a->bit_cost_ + b->bit_cost_; 332 cost_threshold += sum_cost; 333 334 if (GetCombinedHistogramEntropy(a, b, cost_threshold, &cost)) { 335 VP8LHistogramAdd(a, b, out); 336 out->bit_cost_ = cost; 337 out->palette_code_bits_ = a->palette_code_bits_; 338 } 339 340 return cost - sum_cost; 341 } 342 343 // Same as HistogramAddEval(), except that the resulting histogram 344 // is not stored. Only the cost C(a+b) - C(a) is evaluated. We omit 345 // the term C(b) which is constant over all the evaluations. 346 static double HistogramAddThresh(const VP8LHistogram* const a, 347 const VP8LHistogram* const b, 348 double cost_threshold) { 349 double cost = -a->bit_cost_; 350 GetCombinedHistogramEntropy(a, b, cost_threshold, &cost); 351 return cost; 352 } 353 354 // ----------------------------------------------------------------------------- 355 356 // The structure to keep track of cost range for the three dominant entropy 357 // symbols. 358 // TODO(skal): Evaluate if float can be used here instead of double for 359 // representing the entropy costs. 360 typedef struct { 361 double literal_max_; 362 double literal_min_; 363 double red_max_; 364 double red_min_; 365 double blue_max_; 366 double blue_min_; 367 } DominantCostRange; 368 369 static void DominantCostRangeInit(DominantCostRange* const c) { 370 c->literal_max_ = 0.; 371 c->literal_min_ = MAX_COST; 372 c->red_max_ = 0.; 373 c->red_min_ = MAX_COST; 374 c->blue_max_ = 0.; 375 c->blue_min_ = MAX_COST; 376 } 377 378 static void UpdateDominantCostRange( 379 const VP8LHistogram* const h, DominantCostRange* const c) { 380 if (c->literal_max_ < h->literal_cost_) c->literal_max_ = h->literal_cost_; 381 if (c->literal_min_ > h->literal_cost_) c->literal_min_ = h->literal_cost_; 382 if (c->red_max_ < h->red_cost_) c->red_max_ = h->red_cost_; 383 if (c->red_min_ > h->red_cost_) c->red_min_ = h->red_cost_; 384 if (c->blue_max_ < h->blue_cost_) c->blue_max_ = h->blue_cost_; 385 if (c->blue_min_ > h->blue_cost_) c->blue_min_ = h->blue_cost_; 386 } 387 388 static void UpdateHistogramCost(VP8LHistogram* const h) { 389 const double alpha_cost = PopulationCost(h->alpha_, NUM_LITERAL_CODES); 390 const double distance_cost = 391 PopulationCost(h->distance_, NUM_DISTANCE_CODES) + 392 VP8LExtraCost(h->distance_, NUM_DISTANCE_CODES); 393 const int num_codes = VP8LHistogramNumCodes(h->palette_code_bits_); 394 h->literal_cost_ = PopulationCost(h->literal_, num_codes) + 395 VP8LExtraCost(h->literal_ + NUM_LITERAL_CODES, 396 NUM_LENGTH_CODES); 397 h->red_cost_ = PopulationCost(h->red_, NUM_LITERAL_CODES); 398 h->blue_cost_ = PopulationCost(h->blue_, NUM_LITERAL_CODES); 399 h->bit_cost_ = h->literal_cost_ + h->red_cost_ + h->blue_cost_ + 400 alpha_cost + distance_cost; 401 } 402 403 static int GetBinIdForEntropy(double min, double max, double val) { 404 const double range = max - min + 1e-6; 405 const double delta = val - min; 406 return (int)(NUM_PARTITIONS * delta / range); 407 } 408 409 // TODO(vikasa): Evaluate, if there's any correlation between red & blue. 410 static int GetHistoBinIndex( 411 const VP8LHistogram* const h, const DominantCostRange* const c) { 412 const int bin_id = 413 GetBinIdForEntropy(c->blue_min_, c->blue_max_, h->blue_cost_) + 414 NUM_PARTITIONS * GetBinIdForEntropy(c->red_min_, c->red_max_, 415 h->red_cost_) + 416 NUM_PARTITIONS * NUM_PARTITIONS * GetBinIdForEntropy(c->literal_min_, 417 c->literal_max_, 418 h->literal_cost_); 419 assert(bin_id < BIN_SIZE); 420 return bin_id; 421 } 422 423 // Construct the histograms from backward references. 424 static void HistogramBuild( 425 int xsize, int histo_bits, const VP8LBackwardRefs* const backward_refs, 426 VP8LHistogramSet* const image_histo) { 427 int x = 0, y = 0; 428 const int histo_xsize = VP8LSubSampleSize(xsize, histo_bits); 429 VP8LHistogram** const histograms = image_histo->histograms; 430 VP8LRefsCursor c = VP8LRefsCursorInit(backward_refs); 431 assert(histo_bits > 0); 432 // Construct the Histo from a given backward references. 433 while (VP8LRefsCursorOk(&c)) { 434 const PixOrCopy* const v = c.cur_pos; 435 const int ix = (y >> histo_bits) * histo_xsize + (x >> histo_bits); 436 VP8LHistogramAddSinglePixOrCopy(histograms[ix], v); 437 x += PixOrCopyLength(v); 438 while (x >= xsize) { 439 x -= xsize; 440 ++y; 441 } 442 VP8LRefsCursorNext(&c); 443 } 444 } 445 446 // Copies the histograms and computes its bit_cost. 447 static void HistogramCopyAndAnalyze( 448 VP8LHistogramSet* const orig_histo, VP8LHistogramSet* const image_histo) { 449 int i; 450 const int histo_size = orig_histo->size; 451 VP8LHistogram** const orig_histograms = orig_histo->histograms; 452 VP8LHistogram** const histograms = image_histo->histograms; 453 for (i = 0; i < histo_size; ++i) { 454 VP8LHistogram* const histo = orig_histograms[i]; 455 UpdateHistogramCost(histo); 456 // Copy histograms from orig_histo[] to image_histo[]. 457 HistogramCopy(histo, histograms[i]); 458 } 459 } 460 461 // Partition histograms to different entropy bins for three dominant (literal, 462 // red and blue) symbol costs and compute the histogram aggregate bit_cost. 463 static void HistogramAnalyzeEntropyBin( 464 VP8LHistogramSet* const image_histo, int16_t* const bin_map) { 465 int i; 466 VP8LHistogram** const histograms = image_histo->histograms; 467 const int histo_size = image_histo->size; 468 const int bin_depth = histo_size + 1; 469 DominantCostRange cost_range; 470 DominantCostRangeInit(&cost_range); 471 472 // Analyze the dominant (literal, red and blue) entropy costs. 473 for (i = 0; i < histo_size; ++i) { 474 VP8LHistogram* const histo = histograms[i]; 475 UpdateDominantCostRange(histo, &cost_range); 476 } 477 478 // bin-hash histograms on three of the dominant (literal, red and blue) 479 // symbol costs. 480 for (i = 0; i < histo_size; ++i) { 481 int num_histos; 482 VP8LHistogram* const histo = histograms[i]; 483 const int16_t bin_id = (int16_t)GetHistoBinIndex(histo, &cost_range); 484 const int bin_offset = bin_id * bin_depth; 485 // bin_map[n][0] for every bin 'n' maintains the counter for the number of 486 // histograms in that bin. 487 // Get and increment the num_histos in that bin. 488 num_histos = ++bin_map[bin_offset]; 489 assert(bin_offset + num_histos < bin_depth * BIN_SIZE); 490 // Add histogram i'th index at num_histos (last) position in the bin_map. 491 bin_map[bin_offset + num_histos] = i; 492 } 493 } 494 495 // Compact the histogram set by moving the valid one left in the set to the 496 // head and moving the ones that have been merged to other histograms towards 497 // the end. 498 // TODO(vikasa): Evaluate if this method can be avoided by altering the code 499 // logic of HistogramCombineEntropyBin main loop. 500 static void HistogramCompactBins(VP8LHistogramSet* const image_histo) { 501 int start = 0; 502 int end = image_histo->size - 1; 503 VP8LHistogram** const histograms = image_histo->histograms; 504 while (start < end) { 505 while (start <= end && histograms[start] != NULL && 506 histograms[start]->bit_cost_ != 0.) { 507 ++start; 508 } 509 while (start <= end && histograms[end]->bit_cost_ == 0.) { 510 histograms[end] = NULL; 511 --end; 512 } 513 if (start < end) { 514 assert(histograms[start] != NULL); 515 assert(histograms[end] != NULL); 516 HistogramCopy(histograms[end], histograms[start]); 517 histograms[end] = NULL; 518 --end; 519 } 520 } 521 image_histo->size = end + 1; 522 } 523 524 static void HistogramCombineEntropyBin(VP8LHistogramSet* const image_histo, 525 VP8LHistogram* const histos, 526 int16_t* const bin_map, int bin_depth, 527 double combine_cost_factor) { 528 int bin_id; 529 VP8LHistogram* cur_combo = histos; 530 VP8LHistogram** const histograms = image_histo->histograms; 531 532 for (bin_id = 0; bin_id < BIN_SIZE; ++bin_id) { 533 const int bin_offset = bin_id * bin_depth; 534 const int num_histos = bin_map[bin_offset]; 535 const int idx1 = bin_map[bin_offset + 1]; 536 int n; 537 for (n = 2; n <= num_histos; ++n) { 538 const int idx2 = bin_map[bin_offset + n]; 539 const double bit_cost_idx2 = histograms[idx2]->bit_cost_; 540 if (bit_cost_idx2 > 0.) { 541 const double bit_cost_thresh = -bit_cost_idx2 * combine_cost_factor; 542 const double curr_cost_diff = 543 HistogramAddEval(histograms[idx1], histograms[idx2], 544 cur_combo, bit_cost_thresh); 545 if (curr_cost_diff < bit_cost_thresh) { 546 HistogramCopy(cur_combo, histograms[idx1]); 547 histograms[idx2]->bit_cost_ = 0.; 548 } 549 } 550 } 551 } 552 HistogramCompactBins(image_histo); 553 } 554 555 static uint32_t MyRand(uint32_t *seed) { 556 *seed *= 16807U; 557 if (*seed == 0) { 558 *seed = 1; 559 } 560 return *seed; 561 } 562 563 static void HistogramCombine(VP8LHistogramSet* const image_histo, 564 VP8LHistogramSet* const histos, int quality) { 565 int iter; 566 uint32_t seed = 0; 567 int tries_with_no_success = 0; 568 int image_histo_size = image_histo->size; 569 const int iter_mult = (quality < 25) ? 2 : 2 + (quality - 25) / 8; 570 const int outer_iters = image_histo_size * iter_mult; 571 const int num_pairs = image_histo_size / 2; 572 const int num_tries_no_success = outer_iters / 2; 573 const int min_cluster_size = 2; 574 VP8LHistogram** const histograms = image_histo->histograms; 575 VP8LHistogram* cur_combo = histos->histograms[0]; // trial histogram 576 VP8LHistogram* best_combo = histos->histograms[1]; // best histogram so far 577 578 // Collapse similar histograms in 'image_histo'. 579 for (iter = 0; 580 iter < outer_iters && image_histo_size >= min_cluster_size; 581 ++iter) { 582 double best_cost_diff = 0.; 583 int best_idx1 = -1, best_idx2 = 1; 584 int j; 585 const int num_tries = 586 (num_pairs < image_histo_size) ? num_pairs : image_histo_size; 587 seed += iter; 588 for (j = 0; j < num_tries; ++j) { 589 double curr_cost_diff; 590 // Choose two histograms at random and try to combine them. 591 const uint32_t idx1 = MyRand(&seed) % image_histo_size; 592 const uint32_t tmp = (j & 7) + 1; 593 const uint32_t diff = 594 (tmp < 3) ? tmp : MyRand(&seed) % (image_histo_size - 1); 595 const uint32_t idx2 = (idx1 + diff + 1) % image_histo_size; 596 if (idx1 == idx2) { 597 continue; 598 } 599 600 // Calculate cost reduction on combining. 601 curr_cost_diff = HistogramAddEval(histograms[idx1], histograms[idx2], 602 cur_combo, best_cost_diff); 603 if (curr_cost_diff < best_cost_diff) { // found a better pair? 604 { // swap cur/best combo histograms 605 VP8LHistogram* const tmp_histo = cur_combo; 606 cur_combo = best_combo; 607 best_combo = tmp_histo; 608 } 609 best_cost_diff = curr_cost_diff; 610 best_idx1 = idx1; 611 best_idx2 = idx2; 612 } 613 } 614 615 if (best_idx1 >= 0) { 616 HistogramCopy(best_combo, histograms[best_idx1]); 617 // swap best_idx2 slot with last one (which is now unused) 618 --image_histo_size; 619 if (best_idx2 != image_histo_size) { 620 HistogramCopy(histograms[image_histo_size], histograms[best_idx2]); 621 histograms[image_histo_size] = NULL; 622 } 623 tries_with_no_success = 0; 624 } 625 if (++tries_with_no_success >= num_tries_no_success) { 626 break; 627 } 628 } 629 image_histo->size = image_histo_size; 630 } 631 632 // ----------------------------------------------------------------------------- 633 // Histogram refinement 634 635 // Find the best 'out' histogram for each of the 'in' histograms. 636 // Note: we assume that out[]->bit_cost_ is already up-to-date. 637 static void HistogramRemap(const VP8LHistogramSet* const orig_histo, 638 const VP8LHistogramSet* const image_histo, 639 uint16_t* const symbols) { 640 int i; 641 VP8LHistogram** const orig_histograms = orig_histo->histograms; 642 VP8LHistogram** const histograms = image_histo->histograms; 643 for (i = 0; i < orig_histo->size; ++i) { 644 int best_out = 0; 645 double best_bits = 646 HistogramAddThresh(histograms[0], orig_histograms[i], MAX_COST); 647 int k; 648 for (k = 1; k < image_histo->size; ++k) { 649 const double cur_bits = 650 HistogramAddThresh(histograms[k], orig_histograms[i], best_bits); 651 if (cur_bits < best_bits) { 652 best_bits = cur_bits; 653 best_out = k; 654 } 655 } 656 symbols[i] = best_out; 657 } 658 659 // Recompute each out based on raw and symbols. 660 for (i = 0; i < image_histo->size; ++i) { 661 HistogramClear(histograms[i]); 662 } 663 664 for (i = 0; i < orig_histo->size; ++i) { 665 const int idx = symbols[i]; 666 VP8LHistogramAdd(orig_histograms[i], histograms[idx], histograms[idx]); 667 } 668 } 669 670 static double GetCombineCostFactor(int histo_size, int quality) { 671 double combine_cost_factor = 0.16; 672 if (histo_size > 256) combine_cost_factor /= 2.; 673 if (histo_size > 512) combine_cost_factor /= 2.; 674 if (histo_size > 1024) combine_cost_factor /= 2.; 675 if (quality <= 50) combine_cost_factor /= 2.; 676 return combine_cost_factor; 677 } 678 679 int VP8LGetHistoImageSymbols(int xsize, int ysize, 680 const VP8LBackwardRefs* const refs, 681 int quality, int histo_bits, int cache_bits, 682 VP8LHistogramSet* const image_histo, 683 uint16_t* const histogram_symbols) { 684 int ok = 0; 685 const int histo_xsize = histo_bits ? VP8LSubSampleSize(xsize, histo_bits) : 1; 686 const int histo_ysize = histo_bits ? VP8LSubSampleSize(ysize, histo_bits) : 1; 687 const int image_histo_raw_size = histo_xsize * histo_ysize; 688 689 // The bin_map for every bin follows following semantics: 690 // bin_map[n][0] = num_histo; // The number of histograms in that bin. 691 // bin_map[n][1] = index of first histogram in that bin; 692 // bin_map[n][num_histo] = index of last histogram in that bin; 693 // bin_map[n][num_histo + 1] ... bin_map[n][bin_depth - 1] = un-used indices. 694 const int bin_depth = image_histo_raw_size + 1; 695 int16_t* bin_map = NULL; 696 VP8LHistogramSet* const histos = VP8LAllocateHistogramSet(2, cache_bits); 697 VP8LHistogramSet* const orig_histo = 698 VP8LAllocateHistogramSet(image_histo_raw_size, cache_bits); 699 700 if (orig_histo == NULL || histos == NULL) { 701 goto Error; 702 } 703 704 // Don't attempt linear bin-partition heuristic for: 705 // histograms of small sizes, as bin_map will be very sparse and; 706 // Higher qualities (> 90), to preserve the compression gains at those 707 // quality settings. 708 if (orig_histo->size > 2 * BIN_SIZE && quality < 90) { 709 const int bin_map_size = bin_depth * BIN_SIZE; 710 bin_map = (int16_t*)WebPSafeCalloc(bin_map_size, sizeof(*bin_map)); 711 if (bin_map == NULL) goto Error; 712 } 713 714 // Construct the histograms from backward references. 715 HistogramBuild(xsize, histo_bits, refs, orig_histo); 716 // Copies the histograms and computes its bit_cost. 717 HistogramCopyAndAnalyze(orig_histo, image_histo); 718 719 if (bin_map != NULL) { 720 const double combine_cost_factor = 721 GetCombineCostFactor(image_histo_raw_size, quality); 722 HistogramAnalyzeEntropyBin(orig_histo, bin_map); 723 // Collapse histograms with similar entropy. 724 HistogramCombineEntropyBin(image_histo, histos->histograms[0], 725 bin_map, bin_depth, combine_cost_factor); 726 } 727 728 // Collapse similar histograms by random histogram-pair compares. 729 HistogramCombine(image_histo, histos, quality); 730 731 // Find the optimal map from original histograms to the final ones. 732 HistogramRemap(orig_histo, image_histo, histogram_symbols); 733 734 ok = 1; 735 736 Error: 737 WebPSafeFree(bin_map); 738 VP8LFreeHistogramSet(orig_histo); 739 VP8LFreeHistogramSet(histos); 740 return ok; 741 } 742
