godot/thirdparty/libwebp/src/utils/palette.c

// Copyright 2023 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.
// -----------------------------------------------------------------------------
//
// Utilities for palette analysis.
//
// Author: Vincent Rabaud ([email protected])

#include "src/utils/palette.h"

#include <assert.h>
#include <stdlib.h>

#include "src/dsp/lossless_common.h"
#include "src/utils/color_cache_utils.h"
#include "src/utils/utils.h"
#include "src/webp/encode.h"
#include "src/webp/format_constants.h"

// -----------------------------------------------------------------------------

// Palette reordering for smaller sum of deltas (and for smaller storage).

static int PaletteCompareColorsForQsort(const void* p1, const void* p2) { … }

static WEBP_INLINE uint32_t PaletteComponentDistance(uint32_t v) { … }

// Computes a value that is related to the entropy created by the
// palette entry diff.
//
// Note that the last & 0xff is a no-operation in the next statement, but
// removed by most compilers and is here only for regularity of the code.
static WEBP_INLINE uint32_t PaletteColorDistance(uint32_t col1, uint32_t col2) { … }

static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) { … }

int SearchColorNoIdx(const uint32_t sorted[], uint32_t color, int num_colors) { … }

void PrepareMapToPalette(const uint32_t palette[], uint32_t num_colors,
                         uint32_t sorted[], uint32_t idx_map[]) { … }

//------------------------------------------------------------------------------

#define COLOR_HASH_SIZE …
#define COLOR_HASH_RIGHT_SHIFT …

int GetColorPalette(const WebPPicture* const pic, uint32_t* const palette) { … }

#undef COLOR_HASH_SIZE
#undef COLOR_HASH_RIGHT_SHIFT

// -----------------------------------------------------------------------------

// The palette has been sorted by alpha. This function checks if the other
// components of the palette have a monotonic development with regards to
// position in the palette. If all have monotonic development, there is
// 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(const uint32_t* const palette,
                                         int num_colors) { … }

static void PaletteSortMinimizeDeltas(const uint32_t* const palette_sorted,
                                      int num_colors, uint32_t* const 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) { … }

// Builds the cooccurrence matrix
static int CoOccurrenceBuild(const WebPPicture* const pic,
                             const uint32_t* const palette, uint32_t num_colors,
                             uint32_t* cooccurrence) { … }

struct Sum { … };

static int PaletteSortModifiedZeng(const WebPPicture* const pic,
                                   const uint32_t* const palette_in,
                                   uint32_t num_colors,
                                   uint32_t* const palette) { … }

// -----------------------------------------------------------------------------

int PaletteSort(PaletteSorting method, const struct WebPPicture* const pic,
                const uint32_t* const palette_sorted, uint32_t num_colors,
                uint32_t* const palette) { … }