Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(75)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: third_party/libwebp/enc/delta_palettization.c

Issue 2651883004: libwebp-0.6.0-rc1 (Closed)
Patch Set: Created 3 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « third_party/libwebp/enc/delta_palettization.h ('k') | third_party/libwebp/enc/delta_palettization_enc.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: third_party/libwebp/enc/delta_palettization.c
diff --git a/third_party/libwebp/enc/delta_palettization.c b/third_party/libwebp/enc/delta_palettization.c
deleted file mode 100644
index 062e588d79f2db7823d3e5b8b013a5d2be07d367..0000000000000000000000000000000000000000
--- a/third_party/libwebp/enc/delta_palettization.c
+++ /dev/null
@@ -1,455 +0,0 @@
-// Copyright 2015 Google Inc. All Rights Reserved.
-//
-// Use of this source code is governed by a BSD-style license
-// that can be found in the COPYING file in the root of the source
-// tree. An additional intellectual property rights grant can be found
-// in the file PATENTS. All contributing project authors may
-// be found in the AUTHORS file in the root of the source tree.
-// -----------------------------------------------------------------------------
-//
-// Author: Mislav Bradac (mislavm@google.com)
-//
-
-#include "./delta_palettization.h"
-
-#ifdef WEBP_EXPERIMENTAL_FEATURES
-#include "../webp/types.h"
-#include "../dsp/lossless.h"
-
-#define MK_COL(r, g, b) (((r) << 16) + ((g) << 8) + (b))
-
-// Format allows palette up to 256 entries, but more palette entries produce
-// bigger entropy. In the future it will probably be useful to add more entries
-// that are far from the origin of the palette or choose remaining entries
-// dynamically.
-#define DELTA_PALETTE_SIZE 226
-
-// Palette used for delta_palettization. Entries are roughly sorted by distance
-// of their signed equivalents from the origin.
-static const uint32_t kDeltaPalette[DELTA_PALETTE_SIZE] = {
- MK_COL(0u, 0u, 0u),
- MK_COL(255u, 255u, 255u),
- MK_COL(1u, 1u, 1u),
- MK_COL(254u, 254u, 254u),
- MK_COL(2u, 2u, 2u),
- MK_COL(4u, 4u, 4u),
- MK_COL(252u, 252u, 252u),
- MK_COL(250u, 0u, 0u),
- MK_COL(0u, 250u, 0u),
- MK_COL(0u, 0u, 250u),
- MK_COL(6u, 0u, 0u),
- MK_COL(0u, 6u, 0u),
- MK_COL(0u, 0u, 6u),
- MK_COL(0u, 0u, 248u),
- MK_COL(0u, 0u, 8u),
- MK_COL(0u, 248u, 0u),
- MK_COL(0u, 248u, 248u),
- MK_COL(0u, 248u, 8u),
- MK_COL(0u, 8u, 0u),
- MK_COL(0u, 8u, 248u),
- MK_COL(0u, 8u, 8u),
- MK_COL(8u, 8u, 8u),
- MK_COL(248u, 0u, 0u),
- MK_COL(248u, 0u, 248u),
- MK_COL(248u, 0u, 8u),
- MK_COL(248u, 248u, 0u),
- MK_COL(248u, 8u, 0u),
- MK_COL(8u, 0u, 0u),
- MK_COL(8u, 0u, 248u),
- MK_COL(8u, 0u, 8u),
- MK_COL(8u, 248u, 0u),
- MK_COL(8u, 8u, 0u),
- MK_COL(23u, 23u, 23u),
- MK_COL(13u, 13u, 13u),
- MK_COL(232u, 232u, 232u),
- MK_COL(244u, 244u, 244u),
- MK_COL(245u, 245u, 250u),
- MK_COL(50u, 50u, 50u),
- MK_COL(204u, 204u, 204u),
- MK_COL(236u, 236u, 236u),
- MK_COL(16u, 16u, 16u),
- MK_COL(240u, 16u, 16u),
- MK_COL(16u, 240u, 16u),
- MK_COL(240u, 240u, 16u),
- MK_COL(16u, 16u, 240u),
- MK_COL(240u, 16u, 240u),
- MK_COL(16u, 240u, 240u),
- MK_COL(240u, 240u, 240u),
- MK_COL(0u, 0u, 232u),
- MK_COL(0u, 232u, 0u),
- MK_COL(232u, 0u, 0u),
- MK_COL(0u, 0u, 24u),
- MK_COL(0u, 24u, 0u),
- MK_COL(24u, 0u, 0u),
- MK_COL(32u, 32u, 32u),
- MK_COL(224u, 32u, 32u),
- MK_COL(32u, 224u, 32u),
- MK_COL(224u, 224u, 32u),
- MK_COL(32u, 32u, 224u),
- MK_COL(224u, 32u, 224u),
- MK_COL(32u, 224u, 224u),
- MK_COL(224u, 224u, 224u),
- MK_COL(0u, 0u, 176u),
- MK_COL(0u, 0u, 80u),
- MK_COL(0u, 176u, 0u),
- MK_COL(0u, 176u, 176u),
- MK_COL(0u, 176u, 80u),
- MK_COL(0u, 80u, 0u),
- MK_COL(0u, 80u, 176u),
- MK_COL(0u, 80u, 80u),
- MK_COL(176u, 0u, 0u),
- MK_COL(176u, 0u, 176u),
- MK_COL(176u, 0u, 80u),
- MK_COL(176u, 176u, 0u),
- MK_COL(176u, 80u, 0u),
- MK_COL(80u, 0u, 0u),
- MK_COL(80u, 0u, 176u),
- MK_COL(80u, 0u, 80u),
- MK_COL(80u, 176u, 0u),
- MK_COL(80u, 80u, 0u),
- MK_COL(0u, 0u, 152u),
- MK_COL(0u, 0u, 104u),
- MK_COL(0u, 152u, 0u),
- MK_COL(0u, 152u, 152u),
- MK_COL(0u, 152u, 104u),
- MK_COL(0u, 104u, 0u),
- MK_COL(0u, 104u, 152u),
- MK_COL(0u, 104u, 104u),
- MK_COL(152u, 0u, 0u),
- MK_COL(152u, 0u, 152u),
- MK_COL(152u, 0u, 104u),
- MK_COL(152u, 152u, 0u),
- MK_COL(152u, 104u, 0u),
- MK_COL(104u, 0u, 0u),
- MK_COL(104u, 0u, 152u),
- MK_COL(104u, 0u, 104u),
- MK_COL(104u, 152u, 0u),
- MK_COL(104u, 104u, 0u),
- MK_COL(216u, 216u, 216u),
- MK_COL(216u, 216u, 40u),
- MK_COL(216u, 216u, 176u),
- MK_COL(216u, 216u, 80u),
- MK_COL(216u, 40u, 216u),
- MK_COL(216u, 40u, 40u),
- MK_COL(216u, 40u, 176u),
- MK_COL(216u, 40u, 80u),
- MK_COL(216u, 176u, 216u),
- MK_COL(216u, 176u, 40u),
- MK_COL(216u, 176u, 176u),
- MK_COL(216u, 176u, 80u),
- MK_COL(216u, 80u, 216u),
- MK_COL(216u, 80u, 40u),
- MK_COL(216u, 80u, 176u),
- MK_COL(216u, 80u, 80u),
- MK_COL(40u, 216u, 216u),
- MK_COL(40u, 216u, 40u),
- MK_COL(40u, 216u, 176u),
- MK_COL(40u, 216u, 80u),
- MK_COL(40u, 40u, 216u),
- MK_COL(40u, 40u, 40u),
- MK_COL(40u, 40u, 176u),
- MK_COL(40u, 40u, 80u),
- MK_COL(40u, 176u, 216u),
- MK_COL(40u, 176u, 40u),
- MK_COL(40u, 176u, 176u),
- MK_COL(40u, 176u, 80u),
- MK_COL(40u, 80u, 216u),
- MK_COL(40u, 80u, 40u),
- MK_COL(40u, 80u, 176u),
- MK_COL(40u, 80u, 80u),
- MK_COL(80u, 216u, 216u),
- MK_COL(80u, 216u, 40u),
- MK_COL(80u, 216u, 176u),
- MK_COL(80u, 216u, 80u),
- MK_COL(80u, 40u, 216u),
- MK_COL(80u, 40u, 40u),
- MK_COL(80u, 40u, 176u),
- MK_COL(80u, 40u, 80u),
- MK_COL(80u, 176u, 216u),
- MK_COL(80u, 176u, 40u),
- MK_COL(80u, 176u, 176u),
- MK_COL(80u, 176u, 80u),
- MK_COL(80u, 80u, 216u),
- MK_COL(80u, 80u, 40u),
- MK_COL(80u, 80u, 176u),
- MK_COL(80u, 80u, 80u),
- MK_COL(0u, 0u, 192u),
- MK_COL(0u, 0u, 64u),
- MK_COL(0u, 0u, 128u),
- MK_COL(0u, 192u, 0u),
- MK_COL(0u, 192u, 192u),
- MK_COL(0u, 192u, 64u),
- MK_COL(0u, 192u, 128u),
- MK_COL(0u, 64u, 0u),
- MK_COL(0u, 64u, 192u),
- MK_COL(0u, 64u, 64u),
- MK_COL(0u, 64u, 128u),
- MK_COL(0u, 128u, 0u),
- MK_COL(0u, 128u, 192u),
- MK_COL(0u, 128u, 64u),
- MK_COL(0u, 128u, 128u),
- MK_COL(176u, 216u, 216u),
- MK_COL(176u, 216u, 40u),
- MK_COL(176u, 216u, 176u),
- MK_COL(176u, 216u, 80u),
- MK_COL(176u, 40u, 216u),
- MK_COL(176u, 40u, 40u),
- MK_COL(176u, 40u, 176u),
- MK_COL(176u, 40u, 80u),
- MK_COL(176u, 176u, 216u),
- MK_COL(176u, 176u, 40u),
- MK_COL(176u, 176u, 176u),
- MK_COL(176u, 176u, 80u),
- MK_COL(176u, 80u, 216u),
- MK_COL(176u, 80u, 40u),
- MK_COL(176u, 80u, 176u),
- MK_COL(176u, 80u, 80u),
- MK_COL(192u, 0u, 0u),
- MK_COL(192u, 0u, 192u),
- MK_COL(192u, 0u, 64u),
- MK_COL(192u, 0u, 128u),
- MK_COL(192u, 192u, 0u),
- MK_COL(192u, 192u, 192u),
- MK_COL(192u, 192u, 64u),
- MK_COL(192u, 192u, 128u),
- MK_COL(192u, 64u, 0u),
- MK_COL(192u, 64u, 192u),
- MK_COL(192u, 64u, 64u),
- MK_COL(192u, 64u, 128u),
- MK_COL(192u, 128u, 0u),
- MK_COL(192u, 128u, 192u),
- MK_COL(192u, 128u, 64u),
- MK_COL(192u, 128u, 128u),
- MK_COL(64u, 0u, 0u),
- MK_COL(64u, 0u, 192u),
- MK_COL(64u, 0u, 64u),
- MK_COL(64u, 0u, 128u),
- MK_COL(64u, 192u, 0u),
- MK_COL(64u, 192u, 192u),
- MK_COL(64u, 192u, 64u),
- MK_COL(64u, 192u, 128u),
- MK_COL(64u, 64u, 0u),
- MK_COL(64u, 64u, 192u),
- MK_COL(64u, 64u, 64u),
- MK_COL(64u, 64u, 128u),
- MK_COL(64u, 128u, 0u),
- MK_COL(64u, 128u, 192u),
- MK_COL(64u, 128u, 64u),
- MK_COL(64u, 128u, 128u),
- MK_COL(128u, 0u, 0u),
- MK_COL(128u, 0u, 192u),
- MK_COL(128u, 0u, 64u),
- MK_COL(128u, 0u, 128u),
- MK_COL(128u, 192u, 0u),
- MK_COL(128u, 192u, 192u),
- MK_COL(128u, 192u, 64u),
- MK_COL(128u, 192u, 128u),
- MK_COL(128u, 64u, 0u),
- MK_COL(128u, 64u, 192u),
- MK_COL(128u, 64u, 64u),
- MK_COL(128u, 64u, 128u),
- MK_COL(128u, 128u, 0u),
- MK_COL(128u, 128u, 192u),
- MK_COL(128u, 128u, 64u),
- MK_COL(128u, 128u, 128u),
-};
-
-#undef MK_COL
-
-//------------------------------------------------------------------------------
-// TODO(skal): move the functions to dsp/lossless.c when the correct
-// granularity is found. For now, we'll just copy-paste some useful bits
-// here instead.
-
-// In-place sum of each component with mod 256.
-static WEBP_INLINE void AddPixelsEq(uint32_t* a, uint32_t b) {
- const uint32_t alpha_and_green = (*a & 0xff00ff00u) + (b & 0xff00ff00u);
- const uint32_t red_and_blue = (*a & 0x00ff00ffu) + (b & 0x00ff00ffu);
- *a = (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu);
-}
-
-static WEBP_INLINE uint32_t Clip255(uint32_t a) {
- if (a < 256) {
- return a;
- }
- // return 0, when a is a negative integer.
- // return 255, when a is positive.
- return ~a >> 24;
-}
-
-// Delta palettization functions.
-static WEBP_INLINE int Square(int x) {
- return x * x;
-}
-
-static WEBP_INLINE uint32_t Intensity(uint32_t a) {
- return
- 30 * ((a >> 16) & 0xff) +
- 59 * ((a >> 8) & 0xff) +
- 11 * ((a >> 0) & 0xff);
-}
-
-static uint32_t CalcDist(uint32_t predicted_value, uint32_t actual_value,
- uint32_t palette_entry) {
- int i;
- uint32_t distance = 0;
- AddPixelsEq(&predicted_value, palette_entry);
- for (i = 0; i < 32; i += 8) {
- const int32_t av = (actual_value >> i) & 0xff;
- const int32_t pv = (predicted_value >> i) & 0xff;
- distance += Square(pv - av);
- }
- // We sum square of intensity difference with factor 10, but because Intensity
- // returns 100 times real intensity we need to multiply differences of colors
- // by 1000.
- distance *= 1000u;
- distance += Square(Intensity(predicted_value)
- - Intensity(actual_value));
- return distance;
-}
-
-static uint32_t Predict(int x, int y, uint32_t* image) {
- const uint32_t t = (y == 0) ? ARGB_BLACK : image[x];
- const uint32_t l = (x == 0) ? ARGB_BLACK : image[x - 1];
- const uint32_t p =
- (((((t >> 24) & 0xff) + ((l >> 24) & 0xff)) / 2) << 24) +
- (((((t >> 16) & 0xff) + ((l >> 16) & 0xff)) / 2) << 16) +
- (((((t >> 8) & 0xff) + ((l >> 8) & 0xff)) / 2) << 8) +
- (((((t >> 0) & 0xff) + ((l >> 0) & 0xff)) / 2) << 0);
- if (x == 0 && y == 0) return ARGB_BLACK;
- if (x == 0) return t;
- if (y == 0) return l;
- return p;
-}
-
-static WEBP_INLINE int AddSubtractComponentFullWithCoefficient(
- int a, int b, int c) {
- return Clip255(a + ((b - c) >> 2));
-}
-
-static WEBP_INLINE uint32_t ClampedAddSubtractFullWithCoefficient(
- uint32_t c0, uint32_t c1, uint32_t c2) {
- const int a = AddSubtractComponentFullWithCoefficient(
- c0 >> 24, c1 >> 24, c2 >> 24);
- const int r = AddSubtractComponentFullWithCoefficient((c0 >> 16) & 0xff,
- (c1 >> 16) & 0xff,
- (c2 >> 16) & 0xff);
- const int g = AddSubtractComponentFullWithCoefficient((c0 >> 8) & 0xff,
- (c1 >> 8) & 0xff,
- (c2 >> 8) & 0xff);
- const int b = AddSubtractComponentFullWithCoefficient(
- c0 & 0xff, c1 & 0xff, c2 & 0xff);
- return ((uint32_t)a << 24) | (r << 16) | (g << 8) | b;
-}
-
-//------------------------------------------------------------------------------
-
-// Find palette entry with minimum error from difference of actual pixel value
-// and predicted pixel value. Propagate error of pixel to its top and left pixel
-// in src array. Write predicted_value + palette_entry to new_image. Return
-// index of best palette entry.
-static int FindBestPaletteEntry(uint32_t src, uint32_t predicted_value,
- const uint32_t palette[], int palette_size) {
- int i;
- int idx = 0;
- uint32_t best_distance = CalcDist(predicted_value, src, palette[0]);
- for (i = 1; i < palette_size; ++i) {
- const uint32_t distance = CalcDist(predicted_value, src, palette[i]);
- if (distance < best_distance) {
- best_distance = distance;
- idx = i;
- }
- }
- return idx;
-}
-
-static void ApplyBestPaletteEntry(int x, int y,
- uint32_t new_value, uint32_t palette_value,
- uint32_t* src, int src_stride,
- uint32_t* new_image) {
- AddPixelsEq(&new_value, palette_value);
- if (x > 0) {
- src[x - 1] = ClampedAddSubtractFullWithCoefficient(src[x - 1],
- new_value, src[x]);
- }
- if (y > 0) {
- src[x - src_stride] =
- ClampedAddSubtractFullWithCoefficient(src[x - src_stride],
- new_value, src[x]);
- }
- new_image[x] = new_value;
-}
-
-//------------------------------------------------------------------------------
-// Main entry point
-
-static WebPEncodingError ApplyDeltaPalette(uint32_t* src, uint32_t* dst,
- uint32_t src_stride,
- uint32_t dst_stride,
- const uint32_t* palette,
- int palette_size,
- int width, int height,
- int num_passes) {
- int x, y;
- WebPEncodingError err = VP8_ENC_OK;
- uint32_t* new_image = (uint32_t*)WebPSafeMalloc(width, sizeof(*new_image));
- uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row));
- if (new_image == NULL || tmp_row == NULL) {
- err = VP8_ENC_ERROR_OUT_OF_MEMORY;
- goto Error;
- }
-
- while (num_passes--) {
- uint32_t* cur_src = src;
- uint32_t* cur_dst = dst;
- for (y = 0; y < height; ++y) {
- for (x = 0; x < width; ++x) {
- const uint32_t predicted_value = Predict(x, y, new_image);
- tmp_row[x] = FindBestPaletteEntry(cur_src[x], predicted_value,
- palette, palette_size);
- ApplyBestPaletteEntry(x, y, predicted_value, palette[tmp_row[x]],
- cur_src, src_stride, new_image);
- }
- for (x = 0; x < width; ++x) {
- cur_dst[x] = palette[tmp_row[x]];
- }
- cur_src += src_stride;
- cur_dst += dst_stride;
- }
- }
- Error:
- WebPSafeFree(new_image);
- WebPSafeFree(tmp_row);
- return err;
-}
-
-// replaces enc->argb_ by a palettizable approximation of it,
-// and generates optimal enc->palette_[]
-WebPEncodingError WebPSearchOptimalDeltaPalette(VP8LEncoder* const enc) {
- const WebPPicture* const pic = enc->pic_;
- uint32_t* src = pic->argb;
- uint32_t* dst = enc->argb_;
- const int width = pic->width;
- const int height = pic->height;
-
- WebPEncodingError err = VP8_ENC_OK;
- memcpy(enc->palette_, kDeltaPalette, sizeof(kDeltaPalette));
- enc->palette_[DELTA_PALETTE_SIZE - 1] = src[0] - 0xff000000u;
- enc->palette_size_ = DELTA_PALETTE_SIZE;
- err = ApplyDeltaPalette(src, dst, pic->argb_stride, enc->current_width_,
- enc->palette_, enc->palette_size_,
- width, height, 2);
- if (err != VP8_ENC_OK) goto Error;
-
- Error:
- return err;
-}
-
-#else // !WEBP_EXPERIMENTAL_FEATURES
-
-WebPEncodingError WebPSearchOptimalDeltaPalette(VP8LEncoder* const enc) {
- (void)enc;
- return VP8_ENC_ERROR_INVALID_CONFIGURATION;
-}
-
-#endif // WEBP_EXPERIMENTAL_FEATURES
« no previous file with comments | « third_party/libwebp/enc/delta_palettization.h ('k') | third_party/libwebp/enc/delta_palettization_enc.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698