1// Copyright 2015 Google Inc. All Rights Reserved.
2//
3// Use of this source code is governed by a BSD-style license
4// that can be found in the COPYING file in the root of the source
5// tree. An additional intellectual property rights grant can be found
6// in the file PATENTS. All contributing project authors may
7// be found in the AUTHORS file in the root of the source tree.
8// -----------------------------------------------------------------------------
9//
10// Author: Mislav Bradac (mislavm@google.com)
11//
12
13#include "src/enc/delta_palettization_enc.h"
14
15#ifdef WEBP_EXPERIMENTAL_FEATURES
16#include "src/webp/types.h"
17#include "src/dsp/lossless.h"
18
19#define MK_COL(r, g, b) (((r) << 16) + ((g) << 8) + (b))
20
21// Format allows palette up to 256 entries, but more palette entries produce
22// bigger entropy. In the future it will probably be useful to add more entries
23// that are far from the origin of the palette or choose remaining entries
24// dynamically.
25#define DELTA_PALETTE_SIZE 226
26
27// Palette used for delta_palettization. Entries are roughly sorted by distance
28// of their signed equivalents from the origin.
29static const uint32_t kDeltaPalette[DELTA_PALETTE_SIZE] = {
30  MK_COL(0u, 0u, 0u),
31  MK_COL(255u, 255u, 255u),
32  MK_COL(1u, 1u, 1u),
33  MK_COL(254u, 254u, 254u),
34  MK_COL(2u, 2u, 2u),
35  MK_COL(4u, 4u, 4u),
36  MK_COL(252u, 252u, 252u),
37  MK_COL(250u, 0u, 0u),
38  MK_COL(0u, 250u, 0u),
39  MK_COL(0u, 0u, 250u),
40  MK_COL(6u, 0u, 0u),
41  MK_COL(0u, 6u, 0u),
42  MK_COL(0u, 0u, 6u),
43  MK_COL(0u, 0u, 248u),
44  MK_COL(0u, 0u, 8u),
45  MK_COL(0u, 248u, 0u),
46  MK_COL(0u, 248u, 248u),
47  MK_COL(0u, 248u, 8u),
48  MK_COL(0u, 8u, 0u),
49  MK_COL(0u, 8u, 248u),
50  MK_COL(0u, 8u, 8u),
51  MK_COL(8u, 8u, 8u),
52  MK_COL(248u, 0u, 0u),
53  MK_COL(248u, 0u, 248u),
54  MK_COL(248u, 0u, 8u),
55  MK_COL(248u, 248u, 0u),
56  MK_COL(248u, 8u, 0u),
57  MK_COL(8u, 0u, 0u),
58  MK_COL(8u, 0u, 248u),
59  MK_COL(8u, 0u, 8u),
60  MK_COL(8u, 248u, 0u),
61  MK_COL(8u, 8u, 0u),
62  MK_COL(23u, 23u, 23u),
63  MK_COL(13u, 13u, 13u),
64  MK_COL(232u, 232u, 232u),
65  MK_COL(244u, 244u, 244u),
66  MK_COL(245u, 245u, 250u),
67  MK_COL(50u, 50u, 50u),
68  MK_COL(204u, 204u, 204u),
69  MK_COL(236u, 236u, 236u),
70  MK_COL(16u, 16u, 16u),
71  MK_COL(240u, 16u, 16u),
72  MK_COL(16u, 240u, 16u),
73  MK_COL(240u, 240u, 16u),
74  MK_COL(16u, 16u, 240u),
75  MK_COL(240u, 16u, 240u),
76  MK_COL(16u, 240u, 240u),
77  MK_COL(240u, 240u, 240u),
78  MK_COL(0u, 0u, 232u),
79  MK_COL(0u, 232u, 0u),
80  MK_COL(232u, 0u, 0u),
81  MK_COL(0u, 0u, 24u),
82  MK_COL(0u, 24u, 0u),
83  MK_COL(24u, 0u, 0u),
84  MK_COL(32u, 32u, 32u),
85  MK_COL(224u, 32u, 32u),
86  MK_COL(32u, 224u, 32u),
87  MK_COL(224u, 224u, 32u),
88  MK_COL(32u, 32u, 224u),
89  MK_COL(224u, 32u, 224u),
90  MK_COL(32u, 224u, 224u),
91  MK_COL(224u, 224u, 224u),
92  MK_COL(0u, 0u, 176u),
93  MK_COL(0u, 0u, 80u),
94  MK_COL(0u, 176u, 0u),
95  MK_COL(0u, 176u, 176u),
96  MK_COL(0u, 176u, 80u),
97  MK_COL(0u, 80u, 0u),
98  MK_COL(0u, 80u, 176u),
99  MK_COL(0u, 80u, 80u),
100  MK_COL(176u, 0u, 0u),
101  MK_COL(176u, 0u, 176u),
102  MK_COL(176u, 0u, 80u),
103  MK_COL(176u, 176u, 0u),
104  MK_COL(176u, 80u, 0u),
105  MK_COL(80u, 0u, 0u),
106  MK_COL(80u, 0u, 176u),
107  MK_COL(80u, 0u, 80u),
108  MK_COL(80u, 176u, 0u),
109  MK_COL(80u, 80u, 0u),
110  MK_COL(0u, 0u, 152u),
111  MK_COL(0u, 0u, 104u),
112  MK_COL(0u, 152u, 0u),
113  MK_COL(0u, 152u, 152u),
114  MK_COL(0u, 152u, 104u),
115  MK_COL(0u, 104u, 0u),
116  MK_COL(0u, 104u, 152u),
117  MK_COL(0u, 104u, 104u),
118  MK_COL(152u, 0u, 0u),
119  MK_COL(152u, 0u, 152u),
120  MK_COL(152u, 0u, 104u),
121  MK_COL(152u, 152u, 0u),
122  MK_COL(152u, 104u, 0u),
123  MK_COL(104u, 0u, 0u),
124  MK_COL(104u, 0u, 152u),
125  MK_COL(104u, 0u, 104u),
126  MK_COL(104u, 152u, 0u),
127  MK_COL(104u, 104u, 0u),
128  MK_COL(216u, 216u, 216u),
129  MK_COL(216u, 216u, 40u),
130  MK_COL(216u, 216u, 176u),
131  MK_COL(216u, 216u, 80u),
132  MK_COL(216u, 40u, 216u),
133  MK_COL(216u, 40u, 40u),
134  MK_COL(216u, 40u, 176u),
135  MK_COL(216u, 40u, 80u),
136  MK_COL(216u, 176u, 216u),
137  MK_COL(216u, 176u, 40u),
138  MK_COL(216u, 176u, 176u),
139  MK_COL(216u, 176u, 80u),
140  MK_COL(216u, 80u, 216u),
141  MK_COL(216u, 80u, 40u),
142  MK_COL(216u, 80u, 176u),
143  MK_COL(216u, 80u, 80u),
144  MK_COL(40u, 216u, 216u),
145  MK_COL(40u, 216u, 40u),
146  MK_COL(40u, 216u, 176u),
147  MK_COL(40u, 216u, 80u),
148  MK_COL(40u, 40u, 216u),
149  MK_COL(40u, 40u, 40u),
150  MK_COL(40u, 40u, 176u),
151  MK_COL(40u, 40u, 80u),
152  MK_COL(40u, 176u, 216u),
153  MK_COL(40u, 176u, 40u),
154  MK_COL(40u, 176u, 176u),
155  MK_COL(40u, 176u, 80u),
156  MK_COL(40u, 80u, 216u),
157  MK_COL(40u, 80u, 40u),
158  MK_COL(40u, 80u, 176u),
159  MK_COL(40u, 80u, 80u),
160  MK_COL(80u, 216u, 216u),
161  MK_COL(80u, 216u, 40u),
162  MK_COL(80u, 216u, 176u),
163  MK_COL(80u, 216u, 80u),
164  MK_COL(80u, 40u, 216u),
165  MK_COL(80u, 40u, 40u),
166  MK_COL(80u, 40u, 176u),
167  MK_COL(80u, 40u, 80u),
168  MK_COL(80u, 176u, 216u),
169  MK_COL(80u, 176u, 40u),
170  MK_COL(80u, 176u, 176u),
171  MK_COL(80u, 176u, 80u),
172  MK_COL(80u, 80u, 216u),
173  MK_COL(80u, 80u, 40u),
174  MK_COL(80u, 80u, 176u),
175  MK_COL(80u, 80u, 80u),
176  MK_COL(0u, 0u, 192u),
177  MK_COL(0u, 0u, 64u),
178  MK_COL(0u, 0u, 128u),
179  MK_COL(0u, 192u, 0u),
180  MK_COL(0u, 192u, 192u),
181  MK_COL(0u, 192u, 64u),
182  MK_COL(0u, 192u, 128u),
183  MK_COL(0u, 64u, 0u),
184  MK_COL(0u, 64u, 192u),
185  MK_COL(0u, 64u, 64u),
186  MK_COL(0u, 64u, 128u),
187  MK_COL(0u, 128u, 0u),
188  MK_COL(0u, 128u, 192u),
189  MK_COL(0u, 128u, 64u),
190  MK_COL(0u, 128u, 128u),
191  MK_COL(176u, 216u, 216u),
192  MK_COL(176u, 216u, 40u),
193  MK_COL(176u, 216u, 176u),
194  MK_COL(176u, 216u, 80u),
195  MK_COL(176u, 40u, 216u),
196  MK_COL(176u, 40u, 40u),
197  MK_COL(176u, 40u, 176u),
198  MK_COL(176u, 40u, 80u),
199  MK_COL(176u, 176u, 216u),
200  MK_COL(176u, 176u, 40u),
201  MK_COL(176u, 176u, 176u),
202  MK_COL(176u, 176u, 80u),
203  MK_COL(176u, 80u, 216u),
204  MK_COL(176u, 80u, 40u),
205  MK_COL(176u, 80u, 176u),
206  MK_COL(176u, 80u, 80u),
207  MK_COL(192u, 0u, 0u),
208  MK_COL(192u, 0u, 192u),
209  MK_COL(192u, 0u, 64u),
210  MK_COL(192u, 0u, 128u),
211  MK_COL(192u, 192u, 0u),
212  MK_COL(192u, 192u, 192u),
213  MK_COL(192u, 192u, 64u),
214  MK_COL(192u, 192u, 128u),
215  MK_COL(192u, 64u, 0u),
216  MK_COL(192u, 64u, 192u),
217  MK_COL(192u, 64u, 64u),
218  MK_COL(192u, 64u, 128u),
219  MK_COL(192u, 128u, 0u),
220  MK_COL(192u, 128u, 192u),
221  MK_COL(192u, 128u, 64u),
222  MK_COL(192u, 128u, 128u),
223  MK_COL(64u, 0u, 0u),
224  MK_COL(64u, 0u, 192u),
225  MK_COL(64u, 0u, 64u),
226  MK_COL(64u, 0u, 128u),
227  MK_COL(64u, 192u, 0u),
228  MK_COL(64u, 192u, 192u),
229  MK_COL(64u, 192u, 64u),
230  MK_COL(64u, 192u, 128u),
231  MK_COL(64u, 64u, 0u),
232  MK_COL(64u, 64u, 192u),
233  MK_COL(64u, 64u, 64u),
234  MK_COL(64u, 64u, 128u),
235  MK_COL(64u, 128u, 0u),
236  MK_COL(64u, 128u, 192u),
237  MK_COL(64u, 128u, 64u),
238  MK_COL(64u, 128u, 128u),
239  MK_COL(128u, 0u, 0u),
240  MK_COL(128u, 0u, 192u),
241  MK_COL(128u, 0u, 64u),
242  MK_COL(128u, 0u, 128u),
243  MK_COL(128u, 192u, 0u),
244  MK_COL(128u, 192u, 192u),
245  MK_COL(128u, 192u, 64u),
246  MK_COL(128u, 192u, 128u),
247  MK_COL(128u, 64u, 0u),
248  MK_COL(128u, 64u, 192u),
249  MK_COL(128u, 64u, 64u),
250  MK_COL(128u, 64u, 128u),
251  MK_COL(128u, 128u, 0u),
252  MK_COL(128u, 128u, 192u),
253  MK_COL(128u, 128u, 64u),
254  MK_COL(128u, 128u, 128u),
255};
256
257#undef MK_COL
258
259//------------------------------------------------------------------------------
260// TODO(skal): move the functions to dsp/lossless.c when the correct
261// granularity is found. For now, we'll just copy-paste some useful bits
262// here instead.
263
264// In-place sum of each component with mod 256.
265static WEBP_INLINE void AddPixelsEq(uint32_t* a, uint32_t b) {
266  const uint32_t alpha_and_green = (*a & 0xff00ff00u) + (b & 0xff00ff00u);
267  const uint32_t red_and_blue = (*a & 0x00ff00ffu) + (b & 0x00ff00ffu);
268  *a = (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu);
269}
270
271static WEBP_INLINE uint32_t Clip255(uint32_t a) {
272  if (a < 256) {
273    return a;
274  }
275  // return 0, when a is a negative integer.
276  // return 255, when a is positive.
277  return ~a >> 24;
278}
279
280// Delta palettization functions.
281static WEBP_INLINE int Square(int x) {
282  return x * x;
283}
284
285static WEBP_INLINE uint32_t Intensity(uint32_t a) {
286  return
287      30 * ((a >> 16) & 0xff) +
288      59 * ((a >>  8) & 0xff) +
289      11 * ((a >>  0) & 0xff);
290}
291
292static uint32_t CalcDist(uint32_t predicted_value, uint32_t actual_value,
293                         uint32_t palette_entry) {
294  int i;
295  uint32_t distance = 0;
296  AddPixelsEq(&predicted_value, palette_entry);
297  for (i = 0; i < 32; i += 8) {
298    const int32_t av = (actual_value >> i) & 0xff;
299    const int32_t pv = (predicted_value >> i) & 0xff;
300    distance += Square(pv - av);
301  }
302  // We sum square of intensity difference with factor 10, but because Intensity
303  // returns 100 times real intensity we need to multiply differences of colors
304  // by 1000.
305  distance *= 1000u;
306  distance += Square(Intensity(predicted_value)
307                     - Intensity(actual_value));
308  return distance;
309}
310
311static uint32_t Predict(int x, int y, uint32_t* image) {
312  const uint32_t t = (y == 0) ? ARGB_BLACK : image[x];
313  const uint32_t l = (x == 0) ? ARGB_BLACK : image[x - 1];
314  const uint32_t p =
315      (((((t >> 24) & 0xff) + ((l >> 24) & 0xff)) / 2) << 24) +
316      (((((t >> 16) & 0xff) + ((l >> 16) & 0xff)) / 2) << 16) +
317      (((((t >>  8) & 0xff) + ((l >>  8) & 0xff)) / 2) <<  8) +
318      (((((t >>  0) & 0xff) + ((l >>  0) & 0xff)) / 2) <<  0);
319  if (x == 0 && y == 0) return ARGB_BLACK;
320  if (x == 0) return t;
321  if (y == 0) return l;
322  return p;
323}
324
325static WEBP_INLINE int AddSubtractComponentFullWithCoefficient(
326    int a, int b, int c) {
327  return Clip255(a + ((b - c) >> 2));
328}
329
330static WEBP_INLINE uint32_t ClampedAddSubtractFullWithCoefficient(
331    uint32_t c0, uint32_t c1, uint32_t c2) {
332  const int a = AddSubtractComponentFullWithCoefficient(
333      c0 >> 24, c1 >> 24, c2 >> 24);
334  const int r = AddSubtractComponentFullWithCoefficient((c0 >> 16) & 0xff,
335                                                       (c1 >> 16) & 0xff,
336                                                       (c2 >> 16) & 0xff);
337  const int g = AddSubtractComponentFullWithCoefficient((c0 >> 8) & 0xff,
338                                                       (c1 >> 8) & 0xff,
339                                                       (c2 >> 8) & 0xff);
340  const int b = AddSubtractComponentFullWithCoefficient(
341      c0 & 0xff, c1 & 0xff, c2 & 0xff);
342  return ((uint32_t)a << 24) | (r << 16) | (g << 8) | b;
343}
344
345//------------------------------------------------------------------------------
346
347// Find palette entry with minimum error from difference of actual pixel value
348// and predicted pixel value. Propagate error of pixel to its top and left pixel
349// in src array. Write predicted_value + palette_entry to new_image. Return
350// index of best palette entry.
351static int FindBestPaletteEntry(uint32_t src, uint32_t predicted_value,
352                                const uint32_t palette[], int palette_size) {
353  int i;
354  int idx = 0;
355  uint32_t best_distance = CalcDist(predicted_value, src, palette[0]);
356  for (i = 1; i < palette_size; ++i) {
357    const uint32_t distance = CalcDist(predicted_value, src, palette[i]);
358    if (distance < best_distance) {
359      best_distance = distance;
360      idx = i;
361    }
362  }
363  return idx;
364}
365
366static void ApplyBestPaletteEntry(int x, int y,
367                                  uint32_t new_value, uint32_t palette_value,
368                                  uint32_t* src, int src_stride,
369                                  uint32_t* new_image) {
370  AddPixelsEq(&new_value, palette_value);
371  if (x > 0) {
372    src[x - 1] = ClampedAddSubtractFullWithCoefficient(src[x - 1],
373                                                       new_value, src[x]);
374  }
375  if (y > 0) {
376    src[x - src_stride] =
377        ClampedAddSubtractFullWithCoefficient(src[x - src_stride],
378                                              new_value, src[x]);
379  }
380  new_image[x] = new_value;
381}
382
383//------------------------------------------------------------------------------
384// Main entry point
385
386static WebPEncodingError ApplyDeltaPalette(uint32_t* src, uint32_t* dst,
387                                           uint32_t src_stride,
388                                           uint32_t dst_stride,
389                                           const uint32_t* palette,
390                                           int palette_size,
391                                           int width, int height,
392                                           int num_passes) {
393  int x, y;
394  WebPEncodingError err = VP8_ENC_OK;
395  uint32_t* new_image = (uint32_t*)WebPSafeMalloc(width, sizeof(*new_image));
396  uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row));
397  if (new_image == NULL || tmp_row == NULL) {
398    err = VP8_ENC_ERROR_OUT_OF_MEMORY;
399    goto Error;
400  }
401
402  while (num_passes--) {
403    uint32_t* cur_src = src;
404    uint32_t* cur_dst = dst;
405    for (y = 0; y < height; ++y) {
406      for (x = 0; x < width; ++x) {
407        const uint32_t predicted_value = Predict(x, y, new_image);
408        tmp_row[x] = FindBestPaletteEntry(cur_src[x], predicted_value,
409                                          palette, palette_size);
410        ApplyBestPaletteEntry(x, y, predicted_value, palette[tmp_row[x]],
411                              cur_src, src_stride, new_image);
412      }
413      for (x = 0; x < width; ++x) {
414        cur_dst[x] = palette[tmp_row[x]];
415      }
416      cur_src += src_stride;
417      cur_dst += dst_stride;
418    }
419  }
420 Error:
421  WebPSafeFree(new_image);
422  WebPSafeFree(tmp_row);
423  return err;
424}
425
426// replaces enc->argb_ by a palettizable approximation of it,
427// and generates optimal enc->palette_[]
428WebPEncodingError WebPSearchOptimalDeltaPalette(VP8LEncoder* const enc) {
429  const WebPPicture* const pic = enc->pic_;
430  uint32_t* src = pic->argb;
431  uint32_t* dst = enc->argb_;
432  const int width = pic->width;
433  const int height = pic->height;
434
435  WebPEncodingError err = VP8_ENC_OK;
436  memcpy(enc->palette_, kDeltaPalette, sizeof(kDeltaPalette));
437  enc->palette_[DELTA_PALETTE_SIZE - 1] = src[0] - 0xff000000u;
438  enc->palette_size_ = DELTA_PALETTE_SIZE;
439  err = ApplyDeltaPalette(src, dst, pic->argb_stride, enc->current_width_,
440                          enc->palette_, enc->palette_size_,
441                          width, height, 2);
442  if (err != VP8_ENC_OK) goto Error;
443
444 Error:
445  return err;
446}
447
448#else  // !WEBP_EXPERIMENTAL_FEATURES
449
450WebPEncodingError WebPSearchOptimalDeltaPalette(VP8LEncoder* const enc) {
451  (void)enc;
452  return VP8_ENC_ERROR_INVALID_CONFIGURATION;
453}
454
455#endif  // WEBP_EXPERIMENTAL_FEATURES
456