summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/libwebp/src/enc/histogram_enc.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/libwebp/src/enc/histogram_enc.c')
-rw-r--r--src/3rdparty/libwebp/src/enc/histogram_enc.c349
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;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-09 18:38:02 +0000