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 #include "src/utils/palette.h"
15*b2055c35SXin Li
16*b2055c35SXin Li #include <assert.h>
17*b2055c35SXin Li #include <stdlib.h>
18*b2055c35SXin Li
19*b2055c35SXin Li #include "src/dsp/lossless_common.h"
20*b2055c35SXin Li #include "src/utils/color_cache_utils.h"
21*b2055c35SXin Li #include "src/utils/utils.h"
22*b2055c35SXin Li #include "src/webp/encode.h"
23*b2055c35SXin Li #include "src/webp/format_constants.h"
24*b2055c35SXin Li
25*b2055c35SXin Li // -----------------------------------------------------------------------------
26*b2055c35SXin Li
27*b2055c35SXin Li // Palette reordering for smaller sum of deltas (and for smaller storage).
28*b2055c35SXin Li
PaletteCompareColorsForQsort(const void * p1,const void * p2)29*b2055c35SXin Li static int PaletteCompareColorsForQsort(const void* p1, const void* p2) {
30*b2055c35SXin Li const uint32_t a = WebPMemToUint32((uint8_t*)p1);
31*b2055c35SXin Li const uint32_t b = WebPMemToUint32((uint8_t*)p2);
32*b2055c35SXin Li assert(a != b);
33*b2055c35SXin Li return (a < b) ? -1 : 1;
34*b2055c35SXin Li }
35*b2055c35SXin Li
PaletteComponentDistance(uint32_t v)36*b2055c35SXin Li static WEBP_INLINE uint32_t PaletteComponentDistance(uint32_t v) {
37*b2055c35SXin Li return (v <= 128) ? v : (256 - v);
38*b2055c35SXin Li }
39*b2055c35SXin Li
40*b2055c35SXin Li // Computes a value that is related to the entropy created by the
41*b2055c35SXin Li // palette entry diff.
42*b2055c35SXin Li //
43*b2055c35SXin Li // Note that the last & 0xff is a no-operation in the next statement, but
44*b2055c35SXin Li // removed by most compilers and is here only for regularity of the code.
PaletteColorDistance(uint32_t col1,uint32_t col2)45*b2055c35SXin Li static WEBP_INLINE uint32_t PaletteColorDistance(uint32_t col1, uint32_t col2) {
46*b2055c35SXin Li const uint32_t diff = VP8LSubPixels(col1, col2);
47*b2055c35SXin Li const int kMoreWeightForRGBThanForAlpha = 9;
48*b2055c35SXin Li uint32_t score;
49*b2055c35SXin Li score = PaletteComponentDistance((diff >> 0) & 0xff);
50*b2055c35SXin Li score += PaletteComponentDistance((diff >> 8) & 0xff);
51*b2055c35SXin Li score += PaletteComponentDistance((diff >> 16) & 0xff);
52*b2055c35SXin Li score *= kMoreWeightForRGBThanForAlpha;
53*b2055c35SXin Li score += PaletteComponentDistance((diff >> 24) & 0xff);
54*b2055c35SXin Li return score;
55*b2055c35SXin Li }
56*b2055c35SXin Li
SwapColor(uint32_t * const col1,uint32_t * const col2)57*b2055c35SXin Li static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) {
58*b2055c35SXin Li const uint32_t tmp = *col1;
59*b2055c35SXin Li *col1 = *col2;
60*b2055c35SXin Li *col2 = tmp;
61*b2055c35SXin Li }
62*b2055c35SXin Li
SearchColorNoIdx(const uint32_t sorted[],uint32_t color,int num_colors)63*b2055c35SXin Li int SearchColorNoIdx(const uint32_t sorted[], uint32_t color, int num_colors) {
64*b2055c35SXin Li int low = 0, hi = num_colors;
65*b2055c35SXin Li if (sorted[low] == color) return low; // loop invariant: sorted[low] != color
66*b2055c35SXin Li while (1) {
67*b2055c35SXin Li const int mid = (low + hi) >> 1;
68*b2055c35SXin Li if (sorted[mid] == color) {
69*b2055c35SXin Li return mid;
70*b2055c35SXin Li } else if (sorted[mid] < color) {
71*b2055c35SXin Li low = mid;
72*b2055c35SXin Li } else {
73*b2055c35SXin Li hi = mid;
74*b2055c35SXin Li }
75*b2055c35SXin Li }
76*b2055c35SXin Li assert(0);
77*b2055c35SXin Li return 0;
78*b2055c35SXin Li }
79*b2055c35SXin Li
PrepareMapToPalette(const uint32_t palette[],uint32_t num_colors,uint32_t sorted[],uint32_t idx_map[])80*b2055c35SXin Li void PrepareMapToPalette(const uint32_t palette[], uint32_t num_colors,
81*b2055c35SXin Li uint32_t sorted[], uint32_t idx_map[]) {
82*b2055c35SXin Li uint32_t i;
83*b2055c35SXin Li memcpy(sorted, palette, num_colors * sizeof(*sorted));
84*b2055c35SXin Li qsort(sorted, num_colors, sizeof(*sorted), PaletteCompareColorsForQsort);
85*b2055c35SXin Li for (i = 0; i < num_colors; ++i) {
86*b2055c35SXin Li idx_map[SearchColorNoIdx(sorted, palette[i], num_colors)] = i;
87*b2055c35SXin Li }
88*b2055c35SXin Li }
89*b2055c35SXin Li
90*b2055c35SXin Li //------------------------------------------------------------------------------
91*b2055c35SXin Li
92*b2055c35SXin Li #define COLOR_HASH_SIZE (MAX_PALETTE_SIZE * 4)
93*b2055c35SXin Li #define COLOR_HASH_RIGHT_SHIFT 22 // 32 - log2(COLOR_HASH_SIZE).
94*b2055c35SXin Li
GetColorPalette(const WebPPicture * const pic,uint32_t * const palette)95*b2055c35SXin Li int GetColorPalette(const WebPPicture* const pic, uint32_t* const palette) {
96*b2055c35SXin Li int i;
97*b2055c35SXin Li int x, y;
98*b2055c35SXin Li int num_colors = 0;
99*b2055c35SXin Li uint8_t in_use[COLOR_HASH_SIZE] = {0};
100*b2055c35SXin Li uint32_t colors[COLOR_HASH_SIZE] = {0};
101*b2055c35SXin Li const uint32_t* argb = pic->argb;
102*b2055c35SXin Li const int width = pic->width;
103*b2055c35SXin Li const int height = pic->height;
104*b2055c35SXin Li uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0]
105*b2055c35SXin Li assert(pic != NULL);
106*b2055c35SXin Li assert(pic->use_argb);
107*b2055c35SXin Li
108*b2055c35SXin Li for (y = 0; y < height; ++y) {
109*b2055c35SXin Li for (x = 0; x < width; ++x) {
110*b2055c35SXin Li int key;
111*b2055c35SXin Li if (argb[x] == last_pix) {
112*b2055c35SXin Li continue;
113*b2055c35SXin Li }
114*b2055c35SXin Li last_pix = argb[x];
115*b2055c35SXin Li key = VP8LHashPix(last_pix, COLOR_HASH_RIGHT_SHIFT);
116*b2055c35SXin Li while (1) {
117*b2055c35SXin Li if (!in_use[key]) {
118*b2055c35SXin Li colors[key] = last_pix;
119*b2055c35SXin Li in_use[key] = 1;
120*b2055c35SXin Li ++num_colors;
121*b2055c35SXin Li if (num_colors > MAX_PALETTE_SIZE) {
122*b2055c35SXin Li return MAX_PALETTE_SIZE + 1; // Exact count not needed.
123*b2055c35SXin Li }
124*b2055c35SXin Li break;
125*b2055c35SXin Li } else if (colors[key] == last_pix) {
126*b2055c35SXin Li break; // The color is already there.
127*b2055c35SXin Li } else {
128*b2055c35SXin Li // Some other color sits here, so do linear conflict resolution.
129*b2055c35SXin Li ++key;
130*b2055c35SXin Li key &= (COLOR_HASH_SIZE - 1); // Key mask.
131*b2055c35SXin Li }
132*b2055c35SXin Li }
133*b2055c35SXin Li }
134*b2055c35SXin Li argb += pic->argb_stride;
135*b2055c35SXin Li }
136*b2055c35SXin Li
137*b2055c35SXin Li if (palette != NULL) { // Fill the colors into palette.
138*b2055c35SXin Li num_colors = 0;
139*b2055c35SXin Li for (i = 0; i < COLOR_HASH_SIZE; ++i) {
140*b2055c35SXin Li if (in_use[i]) {
141*b2055c35SXin Li palette[num_colors] = colors[i];
142*b2055c35SXin Li ++num_colors;
143*b2055c35SXin Li }
144*b2055c35SXin Li }
145*b2055c35SXin Li qsort(palette, num_colors, sizeof(*palette), PaletteCompareColorsForQsort);
146*b2055c35SXin Li }
147*b2055c35SXin Li return num_colors;
148*b2055c35SXin Li }
149*b2055c35SXin Li
150*b2055c35SXin Li #undef COLOR_HASH_SIZE
151*b2055c35SXin Li #undef COLOR_HASH_RIGHT_SHIFT
152*b2055c35SXin Li
153*b2055c35SXin Li // -----------------------------------------------------------------------------
154*b2055c35SXin Li
155*b2055c35SXin Li // The palette has been sorted by alpha. This function checks if the other
156*b2055c35SXin Li // components of the palette have a monotonic development with regards to
157*b2055c35SXin Li // position in the palette. If all have monotonic development, there is
158*b2055c35SXin Li // no benefit to re-organize them greedily. A monotonic development
159*b2055c35SXin Li // would be spotted in green-only situations (like lossy alpha) or gray-scale
160*b2055c35SXin Li // images.
PaletteHasNonMonotonousDeltas(const uint32_t * const palette,int num_colors)161*b2055c35SXin Li static int PaletteHasNonMonotonousDeltas(const uint32_t* const palette,
162*b2055c35SXin Li int num_colors) {
163*b2055c35SXin Li uint32_t predict = 0x000000;
164*b2055c35SXin Li int i;
165*b2055c35SXin Li uint8_t sign_found = 0x00;
166*b2055c35SXin Li for (i = 0; i < num_colors; ++i) {
167*b2055c35SXin Li const uint32_t diff = VP8LSubPixels(palette[i], predict);
168*b2055c35SXin Li const uint8_t rd = (diff >> 16) & 0xff;
169*b2055c35SXin Li const uint8_t gd = (diff >> 8) & 0xff;
170*b2055c35SXin Li const uint8_t bd = (diff >> 0) & 0xff;
171*b2055c35SXin Li if (rd != 0x00) {
172*b2055c35SXin Li sign_found |= (rd < 0x80) ? 1 : 2;
173*b2055c35SXin Li }
174*b2055c35SXin Li if (gd != 0x00) {
175*b2055c35SXin Li sign_found |= (gd < 0x80) ? 8 : 16;
176*b2055c35SXin Li }
177*b2055c35SXin Li if (bd != 0x00) {
178*b2055c35SXin Li sign_found |= (bd < 0x80) ? 64 : 128;
179*b2055c35SXin Li }
180*b2055c35SXin Li predict = palette[i];
181*b2055c35SXin Li }
182*b2055c35SXin Li return (sign_found & (sign_found << 1)) != 0; // two consequent signs.
183*b2055c35SXin Li }
184*b2055c35SXin Li
PaletteSortMinimizeDeltas(const uint32_t * const palette_sorted,int num_colors,uint32_t * const palette)185*b2055c35SXin Li static void PaletteSortMinimizeDeltas(const uint32_t* const palette_sorted,
186*b2055c35SXin Li int num_colors, uint32_t* const palette) {
187*b2055c35SXin Li uint32_t predict = 0x00000000;
188*b2055c35SXin Li int i, k;
189*b2055c35SXin Li memcpy(palette, palette_sorted, num_colors * sizeof(*palette));
190*b2055c35SXin Li if (!PaletteHasNonMonotonousDeltas(palette_sorted, num_colors)) return;
191*b2055c35SXin Li // Find greedily always the closest color of the predicted color to minimize
192*b2055c35SXin Li // deltas in the palette. This reduces storage needs since the
193*b2055c35SXin Li // palette is stored with delta encoding.
194*b2055c35SXin Li for (i = 0; i < num_colors; ++i) {
195*b2055c35SXin Li int best_ix = i;
196*b2055c35SXin Li uint32_t best_score = ~0U;
197*b2055c35SXin Li for (k = i; k < num_colors; ++k) {
198*b2055c35SXin Li const uint32_t cur_score = PaletteColorDistance(palette[k], predict);
199*b2055c35SXin Li if (best_score > cur_score) {
200*b2055c35SXin Li best_score = cur_score;
201*b2055c35SXin Li best_ix = k;
202*b2055c35SXin Li }
203*b2055c35SXin Li }
204*b2055c35SXin Li SwapColor(&palette[best_ix], &palette[i]);
205*b2055c35SXin Li predict = palette[i];
206*b2055c35SXin Li }
207*b2055c35SXin Li }
208*b2055c35SXin Li
209*b2055c35SXin Li // -----------------------------------------------------------------------------
210*b2055c35SXin Li // Modified Zeng method from "A Survey on Palette Reordering
211*b2055c35SXin Li // Methods for Improving the Compression of Color-Indexed Images" by Armando J.
212*b2055c35SXin Li // Pinho and Antonio J. R. Neves.
213*b2055c35SXin Li
214*b2055c35SXin Li // Finds the biggest cooccurrence in the matrix.
CoOccurrenceFindMax(const uint32_t * const cooccurrence,uint32_t num_colors,uint8_t * const c1,uint8_t * const c2)215*b2055c35SXin Li static void CoOccurrenceFindMax(const uint32_t* const cooccurrence,
216*b2055c35SXin Li uint32_t num_colors, uint8_t* const c1,
217*b2055c35SXin Li uint8_t* const c2) {
218*b2055c35SXin Li // Find the index that is most frequently located adjacent to other
219*b2055c35SXin Li // (different) indexes.
220*b2055c35SXin Li uint32_t best_sum = 0u;
221*b2055c35SXin Li uint32_t i, j, best_cooccurrence;
222*b2055c35SXin Li *c1 = 0u;
223*b2055c35SXin Li for (i = 0; i < num_colors; ++i) {
224*b2055c35SXin Li uint32_t sum = 0;
225*b2055c35SXin Li for (j = 0; j < num_colors; ++j) sum += cooccurrence[i * num_colors + j];
226*b2055c35SXin Li if (sum > best_sum) {
227*b2055c35SXin Li best_sum = sum;
228*b2055c35SXin Li *c1 = i;
229*b2055c35SXin Li }
230*b2055c35SXin Li }
231*b2055c35SXin Li // Find the index that is most frequently found adjacent to *c1.
232*b2055c35SXin Li *c2 = 0u;
233*b2055c35SXin Li best_cooccurrence = 0u;
234*b2055c35SXin Li for (i = 0; i < num_colors; ++i) {
235*b2055c35SXin Li if (cooccurrence[*c1 * num_colors + i] > best_cooccurrence) {
236*b2055c35SXin Li best_cooccurrence = cooccurrence[*c1 * num_colors + i];
237*b2055c35SXin Li *c2 = i;
238*b2055c35SXin Li }
239*b2055c35SXin Li }
240*b2055c35SXin Li assert(*c1 != *c2);
241*b2055c35SXin Li }
242*b2055c35SXin Li
243*b2055c35SXin Li // Builds the cooccurrence matrix
CoOccurrenceBuild(const WebPPicture * const pic,const uint32_t * const palette,uint32_t num_colors,uint32_t * cooccurrence)244*b2055c35SXin Li static int CoOccurrenceBuild(const WebPPicture* const pic,
245*b2055c35SXin Li const uint32_t* const palette, uint32_t num_colors,
246*b2055c35SXin Li uint32_t* cooccurrence) {
247*b2055c35SXin Li uint32_t *lines, *line_top, *line_current, *line_tmp;
248*b2055c35SXin Li int x, y;
249*b2055c35SXin Li const uint32_t* src = pic->argb;
250*b2055c35SXin Li uint32_t prev_pix = ~src[0];
251*b2055c35SXin Li uint32_t prev_idx = 0u;
252*b2055c35SXin Li uint32_t idx_map[MAX_PALETTE_SIZE] = {0};
253*b2055c35SXin Li uint32_t palette_sorted[MAX_PALETTE_SIZE];
254*b2055c35SXin Li lines = (uint32_t*)WebPSafeMalloc(2 * pic->width, sizeof(*lines));
255*b2055c35SXin Li if (lines == NULL) {
256*b2055c35SXin Li return 0;
257*b2055c35SXin Li }
258*b2055c35SXin Li line_top = &lines[0];
259*b2055c35SXin Li line_current = &lines[pic->width];
260*b2055c35SXin Li PrepareMapToPalette(palette, num_colors, palette_sorted, idx_map);
261*b2055c35SXin Li for (y = 0; y < pic->height; ++y) {
262*b2055c35SXin Li for (x = 0; x < pic->width; ++x) {
263*b2055c35SXin Li const uint32_t pix = src[x];
264*b2055c35SXin Li if (pix != prev_pix) {
265*b2055c35SXin Li prev_idx = idx_map[SearchColorNoIdx(palette_sorted, pix, num_colors)];
266*b2055c35SXin Li prev_pix = pix;
267*b2055c35SXin Li }
268*b2055c35SXin Li line_current[x] = prev_idx;
269*b2055c35SXin Li // 4-connectivity is what works best as mentioned in "On the relation
270*b2055c35SXin Li // between Memon's and the modified Zeng's palette reordering methods".
271*b2055c35SXin Li if (x > 0 && prev_idx != line_current[x - 1]) {
272*b2055c35SXin Li const uint32_t left_idx = line_current[x - 1];
273*b2055c35SXin Li ++cooccurrence[prev_idx * num_colors + left_idx];
274*b2055c35SXin Li ++cooccurrence[left_idx * num_colors + prev_idx];
275*b2055c35SXin Li }
276*b2055c35SXin Li if (y > 0 && prev_idx != line_top[x]) {
277*b2055c35SXin Li const uint32_t top_idx = line_top[x];
278*b2055c35SXin Li ++cooccurrence[prev_idx * num_colors + top_idx];
279*b2055c35SXin Li ++cooccurrence[top_idx * num_colors + prev_idx];
280*b2055c35SXin Li }
281*b2055c35SXin Li }
282*b2055c35SXin Li line_tmp = line_top;
283*b2055c35SXin Li line_top = line_current;
284*b2055c35SXin Li line_current = line_tmp;
285*b2055c35SXin Li src += pic->argb_stride;
286*b2055c35SXin Li }
287*b2055c35SXin Li WebPSafeFree(lines);
288*b2055c35SXin Li return 1;
289*b2055c35SXin Li }
290*b2055c35SXin Li
291*b2055c35SXin Li struct Sum {
292*b2055c35SXin Li uint8_t index;
293*b2055c35SXin Li uint32_t sum;
294*b2055c35SXin Li };
295*b2055c35SXin Li
PaletteSortModifiedZeng(const WebPPicture * const pic,const uint32_t * const palette_in,uint32_t num_colors,uint32_t * const palette)296*b2055c35SXin Li static int PaletteSortModifiedZeng(const WebPPicture* const pic,
297*b2055c35SXin Li const uint32_t* const palette_in,
298*b2055c35SXin Li uint32_t num_colors,
299*b2055c35SXin Li uint32_t* const palette) {
300*b2055c35SXin Li uint32_t i, j, ind;
301*b2055c35SXin Li uint8_t remapping[MAX_PALETTE_SIZE];
302*b2055c35SXin Li uint32_t* cooccurrence;
303*b2055c35SXin Li struct Sum sums[MAX_PALETTE_SIZE];
304*b2055c35SXin Li uint32_t first, last;
305*b2055c35SXin Li uint32_t num_sums;
306*b2055c35SXin Li // TODO(vrabaud) check whether one color images should use palette or not.
307*b2055c35SXin Li if (num_colors <= 1) return 1;
308*b2055c35SXin Li // Build the co-occurrence matrix.
309*b2055c35SXin Li cooccurrence =
310*b2055c35SXin Li (uint32_t*)WebPSafeCalloc(num_colors * num_colors, sizeof(*cooccurrence));
311*b2055c35SXin Li if (cooccurrence == NULL) {
312*b2055c35SXin Li return 0;
313*b2055c35SXin Li }
314*b2055c35SXin Li if (!CoOccurrenceBuild(pic, palette_in, num_colors, cooccurrence)) {
315*b2055c35SXin Li WebPSafeFree(cooccurrence);
316*b2055c35SXin Li return 0;
317*b2055c35SXin Li }
318*b2055c35SXin Li
319*b2055c35SXin Li // Initialize the mapping list with the two best indices.
320*b2055c35SXin Li CoOccurrenceFindMax(cooccurrence, num_colors, &remapping[0], &remapping[1]);
321*b2055c35SXin Li
322*b2055c35SXin Li // We need to append and prepend to the list of remapping. To this end, we
323*b2055c35SXin Li // actually define the next start/end of the list as indices in a vector (with
324*b2055c35SXin Li // a wrap around when the end is reached).
325*b2055c35SXin Li first = 0;
326*b2055c35SXin Li last = 1;
327*b2055c35SXin Li num_sums = num_colors - 2; // -2 because we know the first two values
328*b2055c35SXin Li if (num_sums > 0) {
329*b2055c35SXin Li // Initialize the sums with the first two remappings and find the best one
330*b2055c35SXin Li struct Sum* best_sum = &sums[0];
331*b2055c35SXin Li best_sum->index = 0u;
332*b2055c35SXin Li best_sum->sum = 0u;
333*b2055c35SXin Li for (i = 0, j = 0; i < num_colors; ++i) {
334*b2055c35SXin Li if (i == remapping[0] || i == remapping[1]) continue;
335*b2055c35SXin Li sums[j].index = i;
336*b2055c35SXin Li sums[j].sum = cooccurrence[i * num_colors + remapping[0]] +
337*b2055c35SXin Li cooccurrence[i * num_colors + remapping[1]];
338*b2055c35SXin Li if (sums[j].sum > best_sum->sum) best_sum = &sums[j];
339*b2055c35SXin Li ++j;
340*b2055c35SXin Li }
341*b2055c35SXin Li
342*b2055c35SXin Li while (num_sums > 0) {
343*b2055c35SXin Li const uint8_t best_index = best_sum->index;
344*b2055c35SXin Li // Compute delta to know if we need to prepend or append the best index.
345*b2055c35SXin Li int32_t delta = 0;
346*b2055c35SXin Li const int32_t n = num_colors - num_sums;
347*b2055c35SXin Li for (ind = first, j = 0; (ind + j) % num_colors != last + 1; ++j) {
348*b2055c35SXin Li const uint16_t l_j = remapping[(ind + j) % num_colors];
349*b2055c35SXin Li delta += (n - 1 - 2 * (int32_t)j) *
350*b2055c35SXin Li (int32_t)cooccurrence[best_index * num_colors + l_j];
351*b2055c35SXin Li }
352*b2055c35SXin Li if (delta > 0) {
353*b2055c35SXin Li first = (first == 0) ? num_colors - 1 : first - 1;
354*b2055c35SXin Li remapping[first] = best_index;
355*b2055c35SXin Li } else {
356*b2055c35SXin Li ++last;
357*b2055c35SXin Li remapping[last] = best_index;
358*b2055c35SXin Li }
359*b2055c35SXin Li // Remove best_sum from sums.
360*b2055c35SXin Li *best_sum = sums[num_sums - 1];
361*b2055c35SXin Li --num_sums;
362*b2055c35SXin Li // Update all the sums and find the best one.
363*b2055c35SXin Li best_sum = &sums[0];
364*b2055c35SXin Li for (i = 0; i < num_sums; ++i) {
365*b2055c35SXin Li sums[i].sum += cooccurrence[best_index * num_colors + sums[i].index];
366*b2055c35SXin Li if (sums[i].sum > best_sum->sum) best_sum = &sums[i];
367*b2055c35SXin Li }
368*b2055c35SXin Li }
369*b2055c35SXin Li }
370*b2055c35SXin Li assert((last + 1) % num_colors == first);
371*b2055c35SXin Li WebPSafeFree(cooccurrence);
372*b2055c35SXin Li
373*b2055c35SXin Li // Re-map the palette.
374*b2055c35SXin Li for (i = 0; i < num_colors; ++i) {
375*b2055c35SXin Li palette[i] = palette_in[remapping[(first + i) % num_colors]];
376*b2055c35SXin Li }
377*b2055c35SXin Li return 1;
378*b2055c35SXin Li }
379*b2055c35SXin Li
380*b2055c35SXin Li // -----------------------------------------------------------------------------
381*b2055c35SXin Li
PaletteSort(PaletteSorting method,const struct WebPPicture * const pic,const uint32_t * const palette_sorted,uint32_t num_colors,uint32_t * const palette)382*b2055c35SXin Li int PaletteSort(PaletteSorting method, const struct WebPPicture* const pic,
383*b2055c35SXin Li const uint32_t* const palette_sorted, uint32_t num_colors,
384*b2055c35SXin Li uint32_t* const palette) {
385*b2055c35SXin Li switch (method) {
386*b2055c35SXin Li case kSortedDefault:
387*b2055c35SXin Li // Nothing to do, we have already sorted the palette.
388*b2055c35SXin Li memcpy(palette, palette_sorted, num_colors * sizeof(*palette));
389*b2055c35SXin Li return 1;
390*b2055c35SXin Li case kMinimizeDelta:
391*b2055c35SXin Li PaletteSortMinimizeDeltas(palette_sorted, num_colors, palette);
392*b2055c35SXin Li return 1;
393*b2055c35SXin Li case kModifiedZeng:
394*b2055c35SXin Li return PaletteSortModifiedZeng(pic, palette_sorted, num_colors, palette);
395*b2055c35SXin Li case kUnusedPalette:
396*b2055c35SXin Li case kPaletteSortingNum:
397*b2055c35SXin Li break;
398*b2055c35SXin Li }
399*b2055c35SXin Li
400*b2055c35SXin Li assert(0);
401*b2055c35SXin Li return 0;
402*b2055c35SXin Li }
403