1*b2055c35SXin Li // Copyright 2023 Google Inc. All Rights Reserved. 2*b2055c35SXin Li // 3*b2055c35SXin Li // Use of this source code is governed by a BSD-style license 4*b2055c35SXin Li // that can be found in the COPYING file in the root of the source 5*b2055c35SXin Li // tree. An additional intellectual property rights grant can be found 6*b2055c35SXin Li // in the file PATENTS. All contributing project authors may 7*b2055c35SXin Li // be found in the AUTHORS file in the root of the source tree. 8*b2055c35SXin Li // ----------------------------------------------------------------------------- 9*b2055c35SXin Li // 10*b2055c35SXin Li // Utilities for palette analysis. 11*b2055c35SXin Li // 12*b2055c35SXin Li // Author: Vincent Rabaud ([email protected]) 13*b2055c35SXin Li 14*b2055c35SXin Li #ifndef WEBP_UTILS_PALETTE_H_ 15*b2055c35SXin Li #define WEBP_UTILS_PALETTE_H_ 16*b2055c35SXin Li 17*b2055c35SXin Li #include "src/webp/types.h" 18*b2055c35SXin Li 19*b2055c35SXin Li struct WebPPicture; 20*b2055c35SXin Li 21*b2055c35SXin Li // The different ways a palette can be sorted. 22*b2055c35SXin Li typedef enum PaletteSorting { 23*b2055c35SXin Li kSortedDefault = 0, 24*b2055c35SXin Li // Sorts by minimizing L1 deltas between consecutive colors, giving more 25*b2055c35SXin Li // weight to RGB colors. 26*b2055c35SXin Li kMinimizeDelta = 1, 27*b2055c35SXin Li // Implements the modified Zeng method from "A Survey on Palette Reordering 28*b2055c35SXin Li // Methods for Improving the Compression of Color-Indexed Images" by Armando 29*b2055c35SXin Li // J. Pinho and Antonio J. R. Neves. 30*b2055c35SXin Li kModifiedZeng = 2, 31*b2055c35SXin Li kUnusedPalette = 3, 32*b2055c35SXin Li kPaletteSortingNum = 4 33*b2055c35SXin Li } PaletteSorting; 34*b2055c35SXin Li 35*b2055c35SXin Li // Returns the index of 'color' in the sorted palette 'sorted' of size 36*b2055c35SXin Li // 'num_colors'. 37*b2055c35SXin Li int SearchColorNoIdx(const uint32_t sorted[], uint32_t color, int num_colors); 38*b2055c35SXin Li 39*b2055c35SXin Li // Sort palette in increasing order and prepare an inverse mapping array. 40*b2055c35SXin Li void PrepareMapToPalette(const uint32_t palette[], uint32_t num_colors, 41*b2055c35SXin Li uint32_t sorted[], uint32_t idx_map[]); 42*b2055c35SXin Li 43*b2055c35SXin Li // Returns count of unique colors in 'pic', assuming pic->use_argb is true. 44*b2055c35SXin Li // If the unique color count is more than MAX_PALETTE_SIZE, returns 45*b2055c35SXin Li // MAX_PALETTE_SIZE+1. 46*b2055c35SXin Li // If 'palette' is not NULL and the number of unique colors is less than or 47*b2055c35SXin Li // equal to MAX_PALETTE_SIZE, also outputs the actual unique colors into 48*b2055c35SXin Li // 'palette' in a sorted order. Note: 'palette' is assumed to be an array 49*b2055c35SXin Li // already allocated with at least MAX_PALETTE_SIZE elements. 50*b2055c35SXin Li int GetColorPalette(const struct WebPPicture* const pic, 51*b2055c35SXin Li uint32_t* const palette); 52*b2055c35SXin Li 53*b2055c35SXin Li // Sorts the palette according to the criterion defined by 'method'. 54*b2055c35SXin Li // 'palette_sorted' is the input palette sorted lexicographically, as done in 55*b2055c35SXin Li // PrepareMapToPalette. Returns 0 on memory allocation error. 56*b2055c35SXin Li int PaletteSort(PaletteSorting method, const struct WebPPicture* const pic, 57*b2055c35SXin Li const uint32_t* const palette_sorted, uint32_t num_colors, 58*b2055c35SXin Li uint32_t* const palette); 59*b2055c35SXin Li 60*b2055c35SXin Li #endif // WEBP_UTILS_PALETTE_H_ 61