summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/libwebp/src/enc
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/libwebp/src/enc')
-rw-r--r--src/3rdparty/libwebp/src/enc/alpha_enc.c8
-rw-r--r--src/3rdparty/libwebp/src/enc/histogram_enc.c10
-rw-r--r--src/3rdparty/libwebp/src/enc/histogram_enc.h6
-rw-r--r--src/3rdparty/libwebp/src/enc/picture_rescale_enc.c61
-rw-r--r--src/3rdparty/libwebp/src/enc/syntax_enc.c2
-rw-r--r--src/3rdparty/libwebp/src/enc/vp8i_enc.h5
-rw-r--r--src/3rdparty/libwebp/src/enc/vp8l_enc.c342
-rw-r--r--src/3rdparty/libwebp/src/enc/vp8li_enc.h2
8 files changed, 327 insertions, 109 deletions
diff --git a/src/3rdparty/libwebp/src/enc/alpha_enc.c b/src/3rdparty/libwebp/src/enc/alpha_enc.c
index dce9ca9..0b54f3e 100644
--- a/src/3rdparty/libwebp/src/enc/alpha_enc.c
+++ b/src/3rdparty/libwebp/src/enc/alpha_enc.c
@@ -303,7 +303,7 @@ static int EncodeAlpha(VP8Encoder* const enc,
int ok = 1;
const int reduce_levels = (quality < 100);
- // quick sanity checks
+ // quick correctness checks
assert((uint64_t)data_size == (uint64_t)width * height); // as per spec
assert(enc != NULL && pic != NULL && pic->a != NULL);
assert(output != NULL && output_size != NULL);
@@ -361,7 +361,7 @@ static int EncodeAlpha(VP8Encoder* const enc,
//------------------------------------------------------------------------------
// Main calls
-static int CompressAlphaJob(void* arg1, void* dummy) {
+static int CompressAlphaJob(void* arg1, void* unused) {
VP8Encoder* const enc = (VP8Encoder*)arg1;
const WebPConfig* config = enc->config_;
uint8_t* alpha_data = NULL;
@@ -375,13 +375,13 @@ static int CompressAlphaJob(void* arg1, void* dummy) {
filter, effort_level, &alpha_data, &alpha_size)) {
return 0;
}
- if (alpha_size != (uint32_t)alpha_size) { // Sanity check.
+ if (alpha_size != (uint32_t)alpha_size) { // Soundness check.
WebPSafeFree(alpha_data);
return 0;
}
enc->alpha_data_size_ = (uint32_t)alpha_size;
enc->alpha_data_ = alpha_data;
- (void)dummy;
+ (void)unused;
return 1;
}
diff --git a/src/3rdparty/libwebp/src/enc/histogram_enc.c b/src/3rdparty/libwebp/src/enc/histogram_enc.c
index edc6e4f..38a0ceb 100644
--- a/src/3rdparty/libwebp/src/enc/histogram_enc.c
+++ b/src/3rdparty/libwebp/src/enc/histogram_enc.c
@@ -1171,13 +1171,15 @@ static void RemoveEmptyHistograms(VP8LHistogramSet* const image_histo) {
int VP8LGetHistoImageSymbols(int xsize, int ysize,
const VP8LBackwardRefs* const refs,
int quality, int low_effort,
- int histo_bits, int cache_bits,
+ int histogram_bits, int cache_bits,
VP8LHistogramSet* const image_histo,
VP8LHistogram* const tmp_histo,
uint16_t* const histogram_symbols) {
int ok = 0;
- const int histo_xsize = histo_bits ? VP8LSubSampleSize(xsize, histo_bits) : 1;
- const int histo_ysize = histo_bits ? VP8LSubSampleSize(ysize, histo_bits) : 1;
+ const int histo_xsize =
+ histogram_bits ? VP8LSubSampleSize(xsize, histogram_bits) : 1;
+ const int histo_ysize =
+ histogram_bits ? VP8LSubSampleSize(ysize, histogram_bits) : 1;
const int image_histo_raw_size = histo_xsize * histo_ysize;
VP8LHistogramSet* const orig_histo =
VP8LAllocateHistogramSet(image_histo_raw_size, cache_bits);
@@ -1193,7 +1195,7 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize,
if (orig_histo == NULL || map_tmp == NULL) goto Error;
// Construct the histograms from backward references.
- HistogramBuild(xsize, histo_bits, refs, orig_histo);
+ HistogramBuild(xsize, histogram_bits, refs, orig_histo);
// Copies the histograms and computes its bit_cost.
// histogram_symbols is optimized
HistogramCopyAndAnalyze(orig_histo, image_histo, &num_used,
diff --git a/src/3rdparty/libwebp/src/enc/histogram_enc.h b/src/3rdparty/libwebp/src/enc/histogram_enc.h
index 54c2d21..c3428b5 100644
--- a/src/3rdparty/libwebp/src/enc/histogram_enc.h
+++ b/src/3rdparty/libwebp/src/enc/histogram_enc.h
@@ -64,8 +64,8 @@ void VP8LHistogramCreate(VP8LHistogram* const p,
const VP8LBackwardRefs* const refs,
int palette_code_bits);
-// Return the size of the histogram for a given palette_code_bits.
-int VP8LGetHistogramSize(int palette_code_bits);
+// Return the size of the histogram for a given cache_bits.
+int VP8LGetHistogramSize(int cache_bits);
// Set the palette_code_bits and reset the stats.
// If init_arrays is true, the arrays are also filled with 0's.
@@ -110,7 +110,7 @@ int VP8LGetHistoImageSymbols(int xsize, int ysize,
const VP8LBackwardRefs* const refs,
int quality, int low_effort,
int histogram_bits, int cache_bits,
- VP8LHistogramSet* const image_in,
+ VP8LHistogramSet* const image_histo,
VP8LHistogram* const tmp_histo,
uint16_t* const histogram_symbols);
diff --git a/src/3rdparty/libwebp/src/enc/picture_rescale_enc.c b/src/3rdparty/libwebp/src/enc/picture_rescale_enc.c
index 58a6ae7..a75f5d9 100644
--- a/src/3rdparty/libwebp/src/enc/picture_rescale_enc.c
+++ b/src/3rdparty/libwebp/src/enc/picture_rescale_enc.c
@@ -164,22 +164,25 @@ int WebPPictureCrop(WebPPicture* pic,
//------------------------------------------------------------------------------
// Simple picture rescaler
-static void RescalePlane(const uint8_t* src,
- int src_width, int src_height, int src_stride,
- uint8_t* dst,
- int dst_width, int dst_height, int dst_stride,
- rescaler_t* const work,
- int num_channels) {
+static int RescalePlane(const uint8_t* src,
+ int src_width, int src_height, int src_stride,
+ uint8_t* dst,
+ int dst_width, int dst_height, int dst_stride,
+ rescaler_t* const work,
+ int num_channels) {
WebPRescaler rescaler;
int y = 0;
- WebPRescalerInit(&rescaler, src_width, src_height,
- dst, dst_width, dst_height, dst_stride,
- num_channels, work);
+ if (!WebPRescalerInit(&rescaler, src_width, src_height,
+ dst, dst_width, dst_height, dst_stride,
+ num_channels, work)) {
+ return 0;
+ }
while (y < src_height) {
y += WebPRescalerImport(&rescaler, src_height - y,
src + y * src_stride, src_stride);
WebPRescalerExport(&rescaler);
}
+ return 1;
}
static void AlphaMultiplyARGB(WebPPicture* const pic, int inverse) {
@@ -222,25 +225,28 @@ int WebPPictureRescale(WebPPicture* pic, int width, int height) {
// If present, we need to rescale alpha first (for AlphaMultiplyY).
if (pic->a != NULL) {
WebPInitAlphaProcessing();
- RescalePlane(pic->a, prev_width, prev_height, pic->a_stride,
- tmp.a, width, height, tmp.a_stride, work, 1);
+ if (!RescalePlane(pic->a, prev_width, prev_height, pic->a_stride,
+ tmp.a, width, height, tmp.a_stride, work, 1)) {
+ return 0;
+ }
}
// We take transparency into account on the luma plane only. That's not
// totally exact blending, but still is a good approximation.
AlphaMultiplyY(pic, 0);
- RescalePlane(pic->y, prev_width, prev_height, pic->y_stride,
- tmp.y, width, height, tmp.y_stride, work, 1);
+ if (!RescalePlane(pic->y, prev_width, prev_height, pic->y_stride,
+ tmp.y, width, height, tmp.y_stride, work, 1) ||
+ !RescalePlane(pic->u,
+ HALVE(prev_width), HALVE(prev_height), pic->uv_stride,
+ tmp.u,
+ HALVE(width), HALVE(height), tmp.uv_stride, work, 1) ||
+ !RescalePlane(pic->v,
+ HALVE(prev_width), HALVE(prev_height), pic->uv_stride,
+ tmp.v,
+ HALVE(width), HALVE(height), tmp.uv_stride, work, 1)) {
+ return 0;
+ }
AlphaMultiplyY(&tmp, 1);
-
- RescalePlane(pic->u,
- HALVE(prev_width), HALVE(prev_height), pic->uv_stride,
- tmp.u,
- HALVE(width), HALVE(height), tmp.uv_stride, work, 1);
- RescalePlane(pic->v,
- HALVE(prev_width), HALVE(prev_height), pic->uv_stride,
- tmp.v,
- HALVE(width), HALVE(height), tmp.uv_stride, work, 1);
} else {
work = (rescaler_t*)WebPSafeMalloc(2ULL * width * 4, sizeof(*work));
if (work == NULL) {
@@ -252,11 +258,12 @@ int WebPPictureRescale(WebPPicture* pic, int width, int height) {
// the premultiplication afterward (while preserving the alpha channel).
WebPInitAlphaProcessing();
AlphaMultiplyARGB(pic, 0);
- RescalePlane((const uint8_t*)pic->argb, prev_width, prev_height,
- pic->argb_stride * 4,
- (uint8_t*)tmp.argb, width, height,
- tmp.argb_stride * 4,
- work, 4);
+ if (!RescalePlane((const uint8_t*)pic->argb, prev_width, prev_height,
+ pic->argb_stride * 4,
+ (uint8_t*)tmp.argb, width, height,
+ tmp.argb_stride * 4, work, 4)) {
+ return 0;
+ }
AlphaMultiplyARGB(&tmp, 1);
}
WebPPictureFree(pic);
diff --git a/src/3rdparty/libwebp/src/enc/syntax_enc.c b/src/3rdparty/libwebp/src/enc/syntax_enc.c
index a9e5a6c..e18cf65 100644
--- a/src/3rdparty/libwebp/src/enc/syntax_enc.c
+++ b/src/3rdparty/libwebp/src/enc/syntax_enc.c
@@ -349,7 +349,7 @@ int VP8EncWrite(VP8Encoder* const enc) {
(enc->alpha_data_size_ & 1);
riff_size += CHUNK_HEADER_SIZE + padded_alpha_size;
}
- // Sanity check.
+ // RIFF size should fit in 32-bits.
if (riff_size > 0xfffffffeU) {
return WebPEncodingSetError(pic, VP8_ENC_ERROR_FILE_TOO_BIG);
}
diff --git a/src/3rdparty/libwebp/src/enc/vp8i_enc.h b/src/3rdparty/libwebp/src/enc/vp8i_enc.h
index 0e35562..67e9509 100644
--- a/src/3rdparty/libwebp/src/enc/vp8i_enc.h
+++ b/src/3rdparty/libwebp/src/enc/vp8i_enc.h
@@ -32,7 +32,7 @@ extern "C" {
// version numbers
#define ENC_MAJ_VERSION 1
#define ENC_MIN_VERSION 2
-#define ENC_REV_VERSION 0
+#define ENC_REV_VERSION 1
enum { MAX_LF_LEVELS = 64, // Maximum loop filter level
MAX_VARIABLE_LEVEL = 67, // last (inclusive) level with variable cost
@@ -286,8 +286,7 @@ int VP8IteratorNext(VP8EncIterator* const it);
// save the yuv_out_ boundary values to top_/left_ arrays for next iterations.
void VP8IteratorSaveBoundary(VP8EncIterator* const it);
// Report progression based on macroblock rows. Return 0 for user-abort request.
-int VP8IteratorProgress(const VP8EncIterator* const it,
- int final_delta_percent);
+int VP8IteratorProgress(const VP8EncIterator* const it, int delta);
// Intra4x4 iterations
void VP8IteratorStartI4(VP8EncIterator* const it);
// returns true if not done.
diff --git a/src/3rdparty/libwebp/src/enc/vp8l_enc.c b/src/3rdparty/libwebp/src/enc/vp8l_enc.c
index 0b44ebe..e330e71 100644
--- a/src/3rdparty/libwebp/src/enc/vp8l_enc.c
+++ b/src/3rdparty/libwebp/src/enc/vp8l_enc.c
@@ -65,25 +65,22 @@ static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) {
*col2 = tmp;
}
-static void GreedyMinimizeDeltas(uint32_t palette[], int num_colors) {
- // Find greedily always the closest color of the predicted color to minimize
- // deltas in the palette. This reduces storage needs since the
- // palette is stored with delta encoding.
- uint32_t predict = 0x00000000;
- int i, k;
- for (i = 0; i < num_colors; ++i) {
- int best_ix = i;
- uint32_t best_score = ~0U;
- for (k = i; k < num_colors; ++k) {
- const uint32_t cur_score = PaletteColorDistance(palette[k], predict);
- if (best_score > cur_score) {
- best_score = cur_score;
- best_ix = k;
- }
+static WEBP_INLINE int SearchColorNoIdx(const uint32_t sorted[], uint32_t color,
+ int num_colors) {
+ int low = 0, hi = num_colors;
+ if (sorted[low] == color) return low; // loop invariant: sorted[low] != color
+ while (1) {
+ const int mid = (low + hi) >> 1;
+ if (sorted[mid] == color) {
+ return mid;
+ } else if (sorted[mid] < color) {
+ low = mid;
+ } else {
+ hi = mid;
}
- SwapColor(&palette[best_ix], &palette[i]);
- predict = palette[i];
}
+ assert(0);
+ return 0;
}
// The palette has been sorted by alpha. This function checks if the other
@@ -92,7 +89,8 @@ static void GreedyMinimizeDeltas(uint32_t palette[], int num_colors) {
// no benefit to re-organize them greedily. A monotonic development
// would be spotted in green-only situations (like lossy alpha) or gray-scale
// images.
-static int PaletteHasNonMonotonousDeltas(uint32_t palette[], int num_colors) {
+static int PaletteHasNonMonotonousDeltas(const uint32_t* const palette,
+ int num_colors) {
uint32_t predict = 0x000000;
int i;
uint8_t sign_found = 0x00;
@@ -115,28 +113,215 @@ static int PaletteHasNonMonotonousDeltas(uint32_t palette[], int num_colors) {
return (sign_found & (sign_found << 1)) != 0; // two consequent signs.
}
+static void PaletteSortMinimizeDeltas(const uint32_t* const palette_sorted,
+ int num_colors, uint32_t* const palette) {
+ uint32_t predict = 0x00000000;
+ int i, k;
+ memcpy(palette, palette_sorted, num_colors * sizeof(*palette));
+ if (!PaletteHasNonMonotonousDeltas(palette_sorted, num_colors)) return;
+ // Find greedily always the closest color of the predicted color to minimize
+ // deltas in the palette. This reduces storage needs since the
+ // palette is stored with delta encoding.
+ for (i = 0; i < num_colors; ++i) {
+ int best_ix = i;
+ uint32_t best_score = ~0U;
+ for (k = i; k < num_colors; ++k) {
+ const uint32_t cur_score = PaletteColorDistance(palette[k], predict);
+ if (best_score > cur_score) {
+ best_score = cur_score;
+ best_ix = k;
+ }
+ }
+ SwapColor(&palette[best_ix], &palette[i]);
+ predict = palette[i];
+ }
+}
+
+// Sort palette in increasing order and prepare an inverse mapping array.
+static void PrepareMapToPalette(const uint32_t palette[], uint32_t num_colors,
+ uint32_t sorted[], uint32_t idx_map[]) {
+ uint32_t i;
+ memcpy(sorted, palette, num_colors * sizeof(*sorted));
+ qsort(sorted, num_colors, sizeof(*sorted), PaletteCompareColorsForQsort);
+ for (i = 0; i < num_colors; ++i) {
+ idx_map[SearchColorNoIdx(sorted, palette[i], num_colors)] = i;
+ }
+}
+
// -----------------------------------------------------------------------------
-// Palette
+// Modified Zeng method from "A Survey on Palette Reordering
+// Methods for Improving the Compression of Color-Indexed Images" by Armando J.
+// Pinho and Antonio J. R. Neves.
+
+// Finds the biggest cooccurrence in the matrix.
+static void CoOccurrenceFindMax(const uint32_t* const cooccurrence,
+ uint32_t num_colors, uint8_t* const c1,
+ uint8_t* const c2) {
+ // Find the index that is most frequently located adjacent to other
+ // (different) indexes.
+ uint32_t best_sum = 0u;
+ uint32_t i, j, best_cooccurrence;
+ *c1 = 0u;
+ for (i = 0; i < num_colors; ++i) {
+ uint32_t sum = 0;
+ for (j = 0; j < num_colors; ++j) sum += cooccurrence[i * num_colors + j];
+ if (sum > best_sum) {
+ best_sum = sum;
+ *c1 = i;
+ }
+ }
+ // Find the index that is most frequently found adjacent to *c1.
+ *c2 = 0u;
+ best_cooccurrence = 0u;
+ for (i = 0; i < num_colors; ++i) {
+ if (cooccurrence[*c1 * num_colors + i] > best_cooccurrence) {
+ best_cooccurrence = cooccurrence[*c1 * num_colors + i];
+ *c2 = i;
+ }
+ }
+ assert(*c1 != *c2);
+}
-// If number of colors in the image is less than or equal to MAX_PALETTE_SIZE,
-// creates a palette and returns true, else returns false.
-static int AnalyzeAndCreatePalette(const WebPPicture* const pic,
- int low_effort,
- uint32_t palette[MAX_PALETTE_SIZE],
- int* const palette_size) {
- const int num_colors = WebPGetColorPalette(pic, palette);
- if (num_colors > MAX_PALETTE_SIZE) {
- *palette_size = 0;
- return 0;
+// Builds the cooccurrence matrix
+static WebPEncodingError CoOccurrenceBuild(const WebPPicture* const pic,
+ const uint32_t* const palette,
+ uint32_t num_colors,
+ uint32_t* cooccurrence) {
+ uint32_t *lines, *line_top, *line_current, *line_tmp;
+ int x, y;
+ const uint32_t* src = pic->argb;
+ uint32_t prev_pix = ~src[0];
+ uint32_t prev_idx = 0u;
+ uint32_t idx_map[MAX_PALETTE_SIZE] = {0};
+ uint32_t palette_sorted[MAX_PALETTE_SIZE];
+ lines = (uint32_t*)WebPSafeMalloc(2 * pic->width, sizeof(*lines));
+ if (lines == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY;
+ line_top = &lines[0];
+ line_current = &lines[pic->width];
+ PrepareMapToPalette(palette, num_colors, palette_sorted, idx_map);
+ for (y = 0; y < pic->height; ++y) {
+ for (x = 0; x < pic->width; ++x) {
+ const uint32_t pix = src[x];
+ if (pix != prev_pix) {
+ prev_idx = idx_map[SearchColorNoIdx(palette_sorted, pix, num_colors)];
+ prev_pix = pix;
+ }
+ line_current[x] = prev_idx;
+ // 4-connectivity is what works best as mentioned in "On the relation
+ // between Memon's and the modified Zeng's palette reordering methods".
+ if (x > 0 && prev_idx != line_current[x - 1]) {
+ const uint32_t left_idx = line_current[x - 1];
+ ++cooccurrence[prev_idx * num_colors + left_idx];
+ ++cooccurrence[left_idx * num_colors + prev_idx];
+ }
+ if (y > 0 && prev_idx != line_top[x]) {
+ const uint32_t top_idx = line_top[x];
+ ++cooccurrence[prev_idx * num_colors + top_idx];
+ ++cooccurrence[top_idx * num_colors + prev_idx];
+ }
+ }
+ line_tmp = line_top;
+ line_top = line_current;
+ line_current = line_tmp;
+ src += pic->argb_stride;
+ }
+ WebPSafeFree(lines);
+ return VP8_ENC_OK;
+}
+
+struct Sum {
+ uint8_t index;
+ uint32_t sum;
+};
+
+// Implements the modified Zeng method from "A Survey on Palette Reordering
+// Methods for Improving the Compression of Color-Indexed Images" by Armando J.
+// Pinho and Antonio J. R. Neves.
+static WebPEncodingError PaletteSortModifiedZeng(
+ const WebPPicture* const pic, const uint32_t* const palette_sorted,
+ uint32_t num_colors, uint32_t* const palette) {
+ uint32_t i, j, ind;
+ uint8_t remapping[MAX_PALETTE_SIZE];
+ uint32_t* cooccurrence;
+ struct Sum sums[MAX_PALETTE_SIZE];
+ uint32_t first, last;
+ uint32_t num_sums;
+ // TODO(vrabaud) check whether one color images should use palette or not.
+ if (num_colors <= 1) return VP8_ENC_OK;
+ // Build the co-occurrence matrix.
+ cooccurrence =
+ (uint32_t*)WebPSafeCalloc(num_colors * num_colors, sizeof(*cooccurrence));
+ if (cooccurrence == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY;
+ if (CoOccurrenceBuild(pic, palette_sorted, num_colors, cooccurrence) !=
+ VP8_ENC_OK) {
+ WebPSafeFree(cooccurrence);
+ return VP8_ENC_ERROR_OUT_OF_MEMORY;
+ }
+
+ // Initialize the mapping list with the two best indices.
+ CoOccurrenceFindMax(cooccurrence, num_colors, &remapping[0], &remapping[1]);
+
+ // We need to append and prepend to the list of remapping. To this end, we
+ // actually define the next start/end of the list as indices in a vector (with
+ // a wrap around when the end is reached).
+ first = 0;
+ last = 1;
+ num_sums = num_colors - 2; // -2 because we know the first two values
+ if (num_sums > 0) {
+ // Initialize the sums with the first two remappings and find the best one
+ struct Sum* best_sum = &sums[0];
+ best_sum->index = 0u;
+ best_sum->sum = 0u;
+ for (i = 0, j = 0; i < num_colors; ++i) {
+ if (i == remapping[0] || i == remapping[1]) continue;
+ sums[j].index = i;
+ sums[j].sum = cooccurrence[i * num_colors + remapping[0]] +
+ cooccurrence[i * num_colors + remapping[1]];
+ if (sums[j].sum > best_sum->sum) best_sum = &sums[j];
+ ++j;
+ }
+
+ while (num_sums > 0) {
+ const uint8_t best_index = best_sum->index;
+ // Compute delta to know if we need to prepend or append the best index.
+ int32_t delta = 0;
+ const int32_t n = num_colors - num_sums;
+ for (ind = first, j = 0; (ind + j) % num_colors != last + 1; ++j) {
+ const uint16_t l_j = remapping[(ind + j) % num_colors];
+ delta += (n - 1 - 2 * (int32_t)j) *
+ (int32_t)cooccurrence[best_index * num_colors + l_j];
+ }
+ if (delta > 0) {
+ first = (first == 0) ? num_colors - 1 : first - 1;
+ remapping[first] = best_index;
+ } else {
+ ++last;
+ remapping[last] = best_index;
+ }
+ // Remove best_sum from sums.
+ *best_sum = sums[num_sums - 1];
+ --num_sums;
+ // Update all the sums and find the best one.
+ best_sum = &sums[0];
+ for (i = 0; i < num_sums; ++i) {
+ sums[i].sum += cooccurrence[best_index * num_colors + sums[i].index];
+ if (sums[i].sum > best_sum->sum) best_sum = &sums[i];
+ }
+ }
}
- *palette_size = num_colors;
- qsort(palette, num_colors, sizeof(*palette), PaletteCompareColorsForQsort);
- if (!low_effort && PaletteHasNonMonotonousDeltas(palette, num_colors)) {
- GreedyMinimizeDeltas(palette, num_colors);
+ assert((last + 1) % num_colors == first);
+ WebPSafeFree(cooccurrence);
+
+ // Re-map the palette.
+ for (i = 0; i < num_colors; ++i) {
+ palette[i] = palette_sorted[remapping[(first + i) % num_colors]];
}
- return 1;
+ return VP8_ENC_OK;
}
+// -----------------------------------------------------------------------------
+// Palette
+
// These five modes are evaluated and their respective entropy is computed.
typedef enum {
kDirect = 0,
@@ -149,6 +334,13 @@ typedef enum {
} EntropyIx;
typedef enum {
+ kSortedDefault = 0,
+ kMinimizeDelta = 1,
+ kModifiedZeng = 2,
+ kUnusedPalette = 3,
+} PaletteSorting;
+
+typedef enum {
kHistoAlpha = 0,
kHistoAlphaPred,
kHistoGreen,
@@ -362,11 +554,14 @@ typedef struct {
} CrunchSubConfig;
typedef struct {
int entropy_idx_;
+ PaletteSorting palette_sorting_type_;
CrunchSubConfig sub_configs_[CRUNCH_SUBCONFIGS_MAX];
int sub_configs_size_;
} CrunchConfig;
-#define CRUNCH_CONFIGS_MAX kNumEntropyIx
+// +2 because we add a palette sorting configuration for kPalette and
+// kPaletteAndSpatial.
+#define CRUNCH_CONFIGS_MAX (kNumEntropyIx + 2)
static int EncoderAnalyze(VP8LEncoder* const enc,
CrunchConfig crunch_configs[CRUNCH_CONFIGS_MAX],
@@ -386,9 +581,15 @@ static int EncoderAnalyze(VP8LEncoder* const enc,
int do_no_cache = 0;
assert(pic != NULL && pic->argb != NULL);
- use_palette =
- AnalyzeAndCreatePalette(pic, low_effort,
- enc->palette_, &enc->palette_size_);
+ // Check whether a palette is possible.
+ enc->palette_size_ = WebPGetColorPalette(pic, enc->palette_sorted_);
+ use_palette = (enc->palette_size_ <= MAX_PALETTE_SIZE);
+ if (!use_palette) {
+ enc->palette_size_ = 0;
+ } else {
+ qsort(enc->palette_sorted_, enc->palette_size_,
+ sizeof(*enc->palette_sorted_), PaletteCompareColorsForQsort);
+ }
// Empirical bit sizes.
enc->histo_bits_ = GetHistoBits(method, use_palette,
@@ -398,6 +599,8 @@ static int EncoderAnalyze(VP8LEncoder* const enc,
if (low_effort) {
// AnalyzeEntropy is somewhat slow.
crunch_configs[0].entropy_idx_ = use_palette ? kPalette : kSpatialSubGreen;
+ crunch_configs[0].palette_sorting_type_ =
+ use_palette ? kSortedDefault : kUnusedPalette;
n_lz77s = 1;
*crunch_configs_size = 1;
} else {
@@ -418,13 +621,28 @@ static int EncoderAnalyze(VP8LEncoder* const enc,
// a palette.
if ((i != kPalette && i != kPaletteAndSpatial) || use_palette) {
assert(*crunch_configs_size < CRUNCH_CONFIGS_MAX);
- crunch_configs[(*crunch_configs_size)++].entropy_idx_ = i;
+ crunch_configs[(*crunch_configs_size)].entropy_idx_ = i;
+ if (use_palette && (i == kPalette || i == kPaletteAndSpatial)) {
+ crunch_configs[(*crunch_configs_size)].palette_sorting_type_ =
+ kMinimizeDelta;
+ ++*crunch_configs_size;
+ // Also add modified Zeng's method.
+ crunch_configs[(*crunch_configs_size)].entropy_idx_ = i;
+ crunch_configs[(*crunch_configs_size)].palette_sorting_type_ =
+ kModifiedZeng;
+ } else {
+ crunch_configs[(*crunch_configs_size)].palette_sorting_type_ =
+ kUnusedPalette;
+ }
+ ++*crunch_configs_size;
}
}
} else {
// Only choose the guessed best transform.
*crunch_configs_size = 1;
crunch_configs[0].entropy_idx_ = min_entropy_ix;
+ crunch_configs[0].palette_sorting_type_ =
+ use_palette ? kMinimizeDelta : kUnusedPalette;
if (config->quality >= 75 && method == 5) {
// Test with and without color cache.
do_no_cache = 1;
@@ -432,6 +650,7 @@ static int EncoderAnalyze(VP8LEncoder* const enc,
if (min_entropy_ix == kPalette) {
*crunch_configs_size = 2;
crunch_configs[1].entropy_idx_ = kPaletteAndSpatial;
+ crunch_configs[1].palette_sorting_type_ = kMinimizeDelta;
}
}
}
@@ -1283,22 +1502,6 @@ static WebPEncodingError MakeInputImageCopy(VP8LEncoder* const enc) {
// -----------------------------------------------------------------------------
-static WEBP_INLINE int SearchColorNoIdx(const uint32_t sorted[], uint32_t color,
- int hi) {
- int low = 0;
- if (sorted[low] == color) return low; // loop invariant: sorted[low] != color
- while (1) {
- const int mid = (low + hi) >> 1;
- if (sorted[mid] == color) {
- return mid;
- } else if (sorted[mid] < color) {
- low = mid;
- } else {
- hi = mid;
- }
- }
-}
-
#define APPLY_PALETTE_GREEDY_MAX 4
static WEBP_INLINE uint32_t SearchColorGreedy(const uint32_t palette[],
@@ -1333,17 +1536,6 @@ static WEBP_INLINE uint32_t ApplyPaletteHash2(uint32_t color) {
(32 - PALETTE_INV_SIZE_BITS);
}
-// Sort palette in increasing order and prepare an inverse mapping array.
-static void PrepareMapToPalette(const uint32_t palette[], int num_colors,
- uint32_t sorted[], uint32_t idx_map[]) {
- int i;
- memcpy(sorted, palette, num_colors * sizeof(*sorted));
- qsort(sorted, num_colors, sizeof(*sorted), PaletteCompareColorsForQsort);
- for (i = 0; i < num_colors; ++i) {
- idx_map[SearchColorNoIdx(sorted, palette[i], num_colors)] = i;
- }
-}
-
// Use 1 pixel cache for ARGB pixels.
#define APPLY_PALETTE_FOR(COLOR_INDEX) do { \
uint32_t prev_pix = palette[0]; \
@@ -1571,7 +1763,8 @@ static int EncodeStreamHook(void* input, void* data2) {
enc->use_predict_ = (entropy_idx == kSpatial) ||
(entropy_idx == kSpatialSubGreen) ||
(entropy_idx == kPaletteAndSpatial);
- if (low_effort) {
+ // When using a palette, R/B==0, hence no need to test for cross-color.
+ if (low_effort || enc->use_palette_) {
enc->use_cross_color_ = 0;
} else {
enc->use_cross_color_ = red_and_blue_always_zero ? 0 : enc->use_predict_;
@@ -1603,6 +1796,19 @@ static int EncodeStreamHook(void* input, void* data2) {
// Encode palette
if (enc->use_palette_) {
+ if (crunch_configs[idx].palette_sorting_type_ == kSortedDefault) {
+ // Nothing to do, we have already sorted the palette.
+ memcpy(enc->palette_, enc->palette_sorted_,
+ enc->palette_size_ * sizeof(*enc->palette_));
+ } else if (crunch_configs[idx].palette_sorting_type_ == kMinimizeDelta) {
+ PaletteSortMinimizeDeltas(enc->palette_sorted_, enc->palette_size_,
+ enc->palette_);
+ } else {
+ assert(crunch_configs[idx].palette_sorting_type_ == kModifiedZeng);
+ err = PaletteSortModifiedZeng(enc->pic_, enc->palette_sorted_,
+ enc->palette_size_, enc->palette_);
+ if (err != VP8_ENC_OK) goto Error;
+ }
err = EncodePalette(bw, low_effort, enc);
if (err != VP8_ENC_OK) goto Error;
err = MapImageFromPalette(enc, use_delta_palette);
@@ -1767,6 +1973,8 @@ WebPEncodingError VP8LEncodeStream(const WebPConfig* const config,
enc_side->palette_size_ = enc_main->palette_size_;
memcpy(enc_side->palette_, enc_main->palette_,
sizeof(enc_main->palette_));
+ memcpy(enc_side->palette_sorted_, enc_main->palette_sorted_,
+ sizeof(enc_main->palette_sorted_));
param->enc_ = enc_side;
}
// Create the workers.
diff --git a/src/3rdparty/libwebp/src/enc/vp8li_enc.h b/src/3rdparty/libwebp/src/enc/vp8li_enc.h
index 94210ce..00de489 100644
--- a/src/3rdparty/libwebp/src/enc/vp8li_enc.h
+++ b/src/3rdparty/libwebp/src/enc/vp8li_enc.h
@@ -69,6 +69,8 @@ typedef struct {
int use_palette_;
int palette_size_;
uint32_t palette_[MAX_PALETTE_SIZE];
+ // Sorted version of palette_ for cache purposes.
+ uint32_t palette_sorted_[MAX_PALETTE_SIZE];
// Some 'scratch' (potentially large) objects.
struct VP8LBackwardRefs refs_[4]; // Backward Refs array for temporaries.
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-04 15:00:51 +0000