diff options
Diffstat (limited to 'src/3rdparty/libwebp/src/enc/histogram_enc.c')
-rw-r--r-- | src/3rdparty/libwebp/src/enc/histogram_enc.c | 349 |
1 files changed, 201 insertions, 148 deletions
diff --git a/src/3rdparty/libwebp/src/enc/histogram_enc.c b/src/3rdparty/libwebp/src/enc/histogram_enc.c index 808b6f7..056a972 100644 --- a/src/3rdparty/libwebp/src/enc/histogram_enc.c +++ b/src/3rdparty/libwebp/src/enc/histogram_enc.c @@ -10,16 +10,16 @@ // Author: Jyrki Alakuijala (jyrki@google.com) // #ifdef HAVE_CONFIG_H -#include "../webp/config.h" +#include "src/webp/config.h" #endif #include <math.h> -#include "./backward_references_enc.h" -#include "./histogram_enc.h" -#include "../dsp/lossless.h" -#include "../dsp/lossless_common.h" -#include "../utils/utils.h" +#include "src/enc/backward_references_enc.h" +#include "src/enc/histogram_enc.h" +#include "src/dsp/lossless.h" +#include "src/dsp/lossless_common.h" +#include "src/utils/utils.h" #define MAX_COST 1.e38 @@ -76,7 +76,7 @@ void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, VP8LHistogram* const histo) { VP8LRefsCursor c = VP8LRefsCursorInit(refs); while (VP8LRefsCursorOk(&c)) { - VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos); + VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos, NULL, 0); VP8LRefsCursorNext(&c); } } @@ -138,7 +138,9 @@ VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits) { // ----------------------------------------------------------------------------- void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, - const PixOrCopy* const v) { + const PixOrCopy* const v, + int (*const distance_modifier)(int, int), + int distance_modifier_arg0) { if (PixOrCopyIsLiteral(v)) { ++histo->alpha_[PixOrCopyLiteral(v, 3)]; ++histo->red_[PixOrCopyLiteral(v, 2)]; @@ -152,7 +154,13 @@ void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, int code, extra_bits; VP8LPrefixEncodeBits(PixOrCopyLength(v), &code, &extra_bits); ++histo->literal_[NUM_LITERAL_CODES + code]; - VP8LPrefixEncodeBits(PixOrCopyDistance(v), &code, &extra_bits); + if (distance_modifier == NULL) { + VP8LPrefixEncodeBits(PixOrCopyDistance(v), &code, &extra_bits); + } else { + VP8LPrefixEncodeBits( + distance_modifier(distance_modifier_arg0, PixOrCopyDistance(v)), + &code, &extra_bits); + } ++histo->distance_[code]; } } @@ -473,7 +481,7 @@ static void HistogramBuild( while (VP8LRefsCursorOk(&c)) { const PixOrCopy* const v = c.cur_pos; const int ix = (y >> histo_bits) * histo_xsize + (x >> histo_bits); - VP8LHistogramAddSinglePixOrCopy(histograms[ix], v); + VP8LHistogramAddSinglePixOrCopy(histograms[ix], v, NULL, 0); x += PixOrCopyLength(v); while (x >= xsize) { x -= xsize; @@ -523,11 +531,12 @@ static void HistogramAnalyzeEntropyBin(VP8LHistogramSet* const image_histo, // Compact image_histo[] by merging some histograms with same bin_id together if // it's advantageous. -static VP8LHistogram* HistogramCombineEntropyBin( - VP8LHistogramSet* const image_histo, - VP8LHistogram* cur_combo, - const uint16_t* const bin_map, int bin_map_size, int num_bins, - double combine_cost_factor, int low_effort) { +static void HistogramCombineEntropyBin(VP8LHistogramSet* const image_histo, + VP8LHistogram* cur_combo, + const uint16_t* const bin_map, + int bin_map_size, int num_bins, + double combine_cost_factor, + int low_effort) { VP8LHistogram** const histograms = image_histo->histograms; int idx; // Work in-place: processed histograms are put at the beginning of @@ -593,14 +602,13 @@ static VP8LHistogram* HistogramCombineEntropyBin( UpdateHistogramCost(histograms[idx]); } } - return cur_combo; } +// Implement a Lehmer random number generator with a multiplicative constant of +// 48271 and a modulo constant of 2^31 − 1. static uint32_t MyRand(uint32_t* const seed) { - *seed = (*seed * 16807ull) & 0xffffffffu; - if (*seed == 0) { - *seed = 1; - } + *seed = (uint32_t)(((uint64_t)(*seed) * 48271u) % 2147483647u); + assert(*seed > 0); return *seed; } @@ -641,57 +649,75 @@ static int HistoQueueInit(HistoQueue* const histo_queue, const int max_index) { static void HistoQueueClear(HistoQueue* const histo_queue) { assert(histo_queue != NULL); WebPSafeFree(histo_queue->queue); + histo_queue->size = 0; + histo_queue->max_size = 0; } -static void SwapHistogramPairs(HistogramPair *p1, - HistogramPair *p2) { - const HistogramPair tmp = *p1; - *p1 = *p2; - *p2 = tmp; +// Pop a specific pair in the queue by replacing it with the last one +// and shrinking the queue. +static void HistoQueuePopPair(HistoQueue* const histo_queue, + HistogramPair* const pair) { + assert(pair >= histo_queue->queue && + pair < (histo_queue->queue + histo_queue->size)); + assert(histo_queue->size > 0); + *pair = histo_queue->queue[histo_queue->size - 1]; + --histo_queue->size; } -// Given a valid priority queue in range [0, queue_size) this function checks -// whether histo_queue[queue_size] should be accepted and swaps it with the -// front if it is smaller. Otherwise, it leaves it as is. -static void UpdateQueueFront(HistoQueue* const histo_queue) { - if (histo_queue->queue[histo_queue->size].cost_diff >= 0) return; - - if (histo_queue->queue[histo_queue->size].cost_diff < - histo_queue->queue[0].cost_diff) { - SwapHistogramPairs(histo_queue->queue, - histo_queue->queue + histo_queue->size); +// Check whether a pair in the queue should be updated as head or not. +static void HistoQueueUpdateHead(HistoQueue* const histo_queue, + HistogramPair* const pair) { + assert(pair->cost_diff < 0.); + assert(pair >= histo_queue->queue && + pair < (histo_queue->queue + histo_queue->size)); + assert(histo_queue->size > 0); + if (pair->cost_diff < histo_queue->queue[0].cost_diff) { + // Replace the best pair. + const HistogramPair tmp = histo_queue->queue[0]; + histo_queue->queue[0] = *pair; + *pair = tmp; } - ++histo_queue->size; - - // We cannot add more elements than the capacity. - // The allocation adds an extra element to the official capacity so that - // histo_queue->queue[histo_queue->max_size] is read/written within bound. - assert(histo_queue->size <= histo_queue->max_size); } -// ----------------------------------------------------------------------------- - -static void PreparePair(VP8LHistogram** histograms, int idx1, int idx2, - HistogramPair* const pair) { - VP8LHistogram* h1; - VP8LHistogram* h2; +// Create a pair from indices "idx1" and "idx2" provided its cost +// is inferior to "threshold", a negative entropy. +// It returns the cost of the pair, or 0. if it superior to threshold. +static double HistoQueuePush(HistoQueue* const histo_queue, + VP8LHistogram** const histograms, int idx1, + int idx2, double threshold) { + const VP8LHistogram* h1; + const VP8LHistogram* h2; + HistogramPair pair; double sum_cost; + assert(threshold <= 0.); if (idx1 > idx2) { const int tmp = idx2; idx2 = idx1; idx1 = tmp; } - pair->idx1 = idx1; - pair->idx2 = idx2; + pair.idx1 = idx1; + pair.idx2 = idx2; h1 = histograms[idx1]; h2 = histograms[idx2]; sum_cost = h1->bit_cost_ + h2->bit_cost_; - pair->cost_combo = 0.; - GetCombinedHistogramEntropy(h1, h2, sum_cost, &pair->cost_combo); - pair->cost_diff = pair->cost_combo - sum_cost; + pair.cost_combo = 0.; + GetCombinedHistogramEntropy(h1, h2, sum_cost + threshold, &pair.cost_combo); + pair.cost_diff = pair.cost_combo - sum_cost; + + // Do not even consider the pair if it does not improve the entropy. + if (pair.cost_diff >= threshold) return 0.; + + // We cannot add more elements than the capacity. + assert(histo_queue->size < histo_queue->max_size); + histo_queue->queue[histo_queue->size++] = pair; + HistoQueueUpdateHead(histo_queue, &histo_queue->queue[histo_queue->size - 1]); + + return pair.cost_diff; } +// ----------------------------------------------------------------------------- + // Combines histograms by continuously choosing the one with the highest cost // reduction. static int HistogramCombineGreedy(VP8LHistogramSet* const image_histo) { @@ -714,13 +740,11 @@ static int HistogramCombineGreedy(VP8LHistogramSet* const image_histo) { clusters[i] = i; for (j = i + 1; j < image_histo_size; ++j) { // Initialize positions array. - PreparePair(histograms, i, j, &histo_queue.queue[histo_queue.size]); - UpdateQueueFront(&histo_queue); + HistoQueuePush(&histo_queue, histograms, i, j, 0.); } } while (image_histo_size > 1 && histo_queue.size > 0) { - HistogramPair* copy_to; const int idx1 = histo_queue.queue[0].idx1; const int idx2 = histo_queue.queue[0].idx2; HistogramAdd(histograms[idx2], histograms[idx1], histograms[idx1]); @@ -733,31 +757,22 @@ static int HistogramCombineGreedy(VP8LHistogramSet* const image_histo) { } --image_histo_size; - // Remove pairs intersecting the just combined best pair. This will - // therefore pop the head of the queue. - copy_to = histo_queue.queue; - for (i = 0; i < histo_queue.size; ++i) { + // Remove pairs intersecting the just combined best pair. + for (i = 0; i < histo_queue.size;) { HistogramPair* const p = histo_queue.queue + i; if (p->idx1 == idx1 || p->idx2 == idx1 || p->idx1 == idx2 || p->idx2 == idx2) { - // Do not copy the invalid pair. - continue; - } - if (p->cost_diff < histo_queue.queue[0].cost_diff) { - // Replace the top of the queue if we found better. - SwapHistogramPairs(histo_queue.queue, p); + HistoQueuePopPair(&histo_queue, p); + } else { + HistoQueueUpdateHead(&histo_queue, p); + ++i; } - SwapHistogramPairs(copy_to, p); - ++copy_to; } - histo_queue.size = (int)(copy_to - histo_queue.queue); // Push new pairs formed with combined histogram to the queue. for (i = 0; i < image_histo_size; ++i) { if (clusters[i] != idx1) { - PreparePair(histograms, idx1, clusters[i], - &histo_queue.queue[histo_queue.size]); - UpdateQueueFront(&histo_queue); + HistoQueuePush(&histo_queue, histograms, idx1, clusters[i], 0.); } } } @@ -777,90 +792,130 @@ static int HistogramCombineGreedy(VP8LHistogramSet* const image_histo) { return ok; } -static void HistogramCombineStochastic(VP8LHistogramSet* const image_histo, - VP8LHistogram* tmp_histo, - VP8LHistogram* best_combo, - int quality, int min_cluster_size) { +// Perform histogram aggregation using a stochastic approach. +// 'do_greedy' is set to 1 if a greedy approach needs to be performed +// afterwards, 0 otherwise. +static int HistogramCombineStochastic(VP8LHistogramSet* const image_histo, + int min_cluster_size, + int* const do_greedy) { int iter; - uint32_t seed = 0; + uint32_t seed = 1; int tries_with_no_success = 0; int image_histo_size = image_histo->size; - const int iter_mult = (quality < 25) ? 2 : 2 + (quality - 25) / 8; - const int outer_iters = image_histo_size * iter_mult; - const int num_pairs = image_histo_size / 2; + const int outer_iters = image_histo_size; const int num_tries_no_success = outer_iters / 2; - int idx2_max = image_histo_size - 1; - int do_brute_dorce = 0; VP8LHistogram** const histograms = image_histo->histograms; + // Priority queue of histogram pairs. Its size of "kCostHeapSizeSqrt"^2 + // impacts the quality of the compression and the speed: the smaller the + // faster but the worse for the compression. + HistoQueue histo_queue; + const int kHistoQueueSizeSqrt = 3; + int ok = 0; + if (!HistoQueueInit(&histo_queue, kHistoQueueSizeSqrt)) { + goto End; + } // Collapse similar histograms in 'image_histo'. ++min_cluster_size; - for (iter = 0; - iter < outer_iters && image_histo_size >= min_cluster_size; + for (iter = 0; iter < outer_iters && image_histo_size >= min_cluster_size && + ++tries_with_no_success < num_tries_no_success; ++iter) { - double best_cost_diff = 0.; + double best_cost = + (histo_queue.size == 0) ? 0. : histo_queue.queue[0].cost_diff; int best_idx1 = -1, best_idx2 = 1; int j; - int num_tries = - (num_pairs < image_histo_size) ? num_pairs : image_histo_size; - // Use a brute force approach if: - // - stochastic has not worked for a while and - // - if the number of iterations for brute force is less than the number of - // iterations if we never find a match ever again stochastically (hence - // num_tries times the number of remaining outer iterations). - do_brute_dorce = - (tries_with_no_success > 10) && - (idx2_max * (idx2_max + 1) < 2 * num_tries * (outer_iters - iter)); - if (do_brute_dorce) num_tries = idx2_max; - - seed += iter; - for (j = 0; j < num_tries; ++j) { - double curr_cost_diff; - // Choose two histograms at random and try to combine them. - uint32_t idx1, idx2; - if (do_brute_dorce) { - // Use a brute force approach. - idx1 = (uint32_t)j; - idx2 = (uint32_t)idx2_max; - } else { - const uint32_t tmp = (j & 7) + 1; - const uint32_t diff = - (tmp < 3) ? tmp : MyRand(&seed) % (image_histo_size - 1); - idx1 = MyRand(&seed) % image_histo_size; - idx2 = (idx1 + diff + 1) % image_histo_size; - if (idx1 == idx2) { - continue; - } - } + const uint32_t rand_range = (image_histo_size - 1) * image_histo_size; + // image_histo_size / 2 was chosen empirically. Less means faster but worse + // compression. + const int num_tries = image_histo_size / 2; - // Calculate cost reduction on combining. - curr_cost_diff = HistogramAddEval(histograms[idx1], histograms[idx2], - tmp_histo, best_cost_diff); - if (curr_cost_diff < best_cost_diff) { // found a better pair? - HistogramSwap(&best_combo, &tmp_histo); - best_cost_diff = curr_cost_diff; - best_idx1 = idx1; - best_idx2 = idx2; + for (j = 0; j < num_tries; ++j) { + double curr_cost; + // Choose two different histograms at random and try to combine them. + const uint32_t tmp = MyRand(&seed) % rand_range; + const uint32_t idx1 = tmp / (image_histo_size - 1); + uint32_t idx2 = tmp % (image_histo_size - 1); + if (idx2 >= idx1) ++idx2; + + // Calculate cost reduction on combination. + curr_cost = + HistoQueuePush(&histo_queue, histograms, idx1, idx2, best_cost); + if (curr_cost < 0) { // found a better pair? + best_cost = curr_cost; + // Empty the queue if we reached full capacity. + if (histo_queue.size == histo_queue.max_size) break; } } - if (do_brute_dorce) --idx2_max; - - if (best_idx1 >= 0) { - HistogramSwap(&best_combo, &histograms[best_idx1]); - // swap best_idx2 slot with last one (which is now unused) - --image_histo_size; - if (idx2_max >= image_histo_size) idx2_max = image_histo_size - 1; - if (best_idx2 != image_histo_size) { - HistogramSwap(&histograms[image_histo_size], &histograms[best_idx2]); - histograms[image_histo_size] = NULL; - } - tries_with_no_success = 0; + if (histo_queue.size == 0) continue; + + // Merge the two best histograms. + best_idx1 = histo_queue.queue[0].idx1; + best_idx2 = histo_queue.queue[0].idx2; + assert(best_idx1 < best_idx2); + HistogramAddEval(histograms[best_idx1], histograms[best_idx2], + histograms[best_idx1], 0); + // Swap the best_idx2 histogram with the last one (which is now unused). + --image_histo_size; + if (best_idx2 != image_histo_size) { + HistogramSwap(&histograms[image_histo_size], &histograms[best_idx2]); } - if (++tries_with_no_success >= num_tries_no_success || idx2_max == 0) { - break; + histograms[image_histo_size] = NULL; + // Parse the queue and update each pair that deals with best_idx1, + // best_idx2 or image_histo_size. + for (j = 0; j < histo_queue.size;) { + HistogramPair* const p = histo_queue.queue + j; + const int is_idx1_best = p->idx1 == best_idx1 || p->idx1 == best_idx2; + const int is_idx2_best = p->idx2 == best_idx1 || p->idx2 == best_idx2; + int do_eval = 0; + // The front pair could have been duplicated by a random pick so + // check for it all the time nevertheless. + if (is_idx1_best && is_idx2_best) { + HistoQueuePopPair(&histo_queue, p); + continue; + } + // Any pair containing one of the two best indices should only refer to + // best_idx1. Its cost should also be updated. + if (is_idx1_best) { + p->idx1 = best_idx1; + do_eval = 1; + } else if (is_idx2_best) { + p->idx2 = best_idx1; + do_eval = 1; + } + if (p->idx2 == image_histo_size) { + // No need to re-evaluate here as it does not involve a pair + // containing best_idx1 or best_idx2. + p->idx2 = best_idx2; + } + assert(p->idx2 < image_histo_size); + // Make sure the index order is respected. + if (p->idx1 > p->idx2) { + const int tmp = p->idx2; + p->idx2 = p->idx1; + p->idx1 = tmp; + } + if (do_eval) { + // Re-evaluate the cost of an updated pair. + GetCombinedHistogramEntropy(histograms[p->idx1], histograms[p->idx2], 0, + &p->cost_diff); + if (p->cost_diff >= 0.) { + HistoQueuePopPair(&histo_queue, p); + continue; + } + } + HistoQueueUpdateHead(&histo_queue, p); + ++j; } + + tries_with_no_success = 0; } image_histo->size = image_histo_size; + *do_greedy = (image_histo->size <= min_cluster_size); + ok = 1; + +End: + HistoQueueClear(&histo_queue); + return ok; } // ----------------------------------------------------------------------------- @@ -925,7 +980,7 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize, int quality, int low_effort, int histo_bits, int cache_bits, VP8LHistogramSet* const image_histo, - VP8LHistogramSet* const tmp_histos, + VP8LHistogram* const tmp_histo, uint16_t* const histogram_symbols) { int ok = 0; const int histo_xsize = histo_bits ? VP8LSubSampleSize(xsize, histo_bits) : 1; @@ -933,7 +988,6 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize, const int image_histo_raw_size = histo_xsize * histo_ysize; VP8LHistogramSet* const orig_histo = VP8LAllocateHistogramSet(image_histo_raw_size, cache_bits); - VP8LHistogram* cur_combo; // Don't attempt linear bin-partition heuristic for // histograms of small sizes (as bin_map will be very sparse) and // maximum quality q==100 (to preserve the compression gains at that level). @@ -948,7 +1002,6 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize, // Copies the histograms and computes its bit_cost. HistogramCopyAndAnalyze(orig_histo, image_histo); - cur_combo = tmp_histos->histograms[1]; // pick up working slot if (entropy_combine) { const int bin_map_size = orig_histo->size; // Reuse histogram_symbols storage. By definition, it's guaranteed to be ok. @@ -958,10 +1011,9 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize, HistogramAnalyzeEntropyBin(orig_histo, bin_map, low_effort); // Collapse histograms with similar entropy. - cur_combo = HistogramCombineEntropyBin(image_histo, cur_combo, - bin_map, bin_map_size, - entropy_combine_num_bins, - combine_cost_factor, low_effort); + HistogramCombineEntropyBin(image_histo, tmp_histo, bin_map, bin_map_size, + entropy_combine_num_bins, combine_cost_factor, + low_effort); } // Don't combine the histograms using stochastic and greedy heuristics for @@ -970,10 +1022,11 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize, const float x = quality / 100.f; // cubic ramp between 1 and MAX_HISTO_GREEDY: const int threshold_size = (int)(1 + (x * x * x) * (MAX_HISTO_GREEDY - 1)); - HistogramCombineStochastic(image_histo, tmp_histos->histograms[0], - cur_combo, quality, threshold_size); - if ((image_histo->size <= threshold_size) && - !HistogramCombineGreedy(image_histo)) { + int do_greedy; + if (!HistogramCombineStochastic(image_histo, threshold_size, &do_greedy)) { + goto Error; + } + if (do_greedy && !HistogramCombineGreedy(image_histo)) { goto Error; } } |