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 "./delta_palettization_enc.h"
14
15 #ifdef WEBP_EXPERIMENTAL_FEATURES
16 #include "../webp/types.h"
17 #include "../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.
29 static 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.
AddPixelsEq(uint32_t * a,uint32_t b)265 static 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
Clip255(uint32_t a)271 static 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.
Square(int x)281 static WEBP_INLINE int Square(int x) {
282 return x * x;
283 }
284
Intensity(uint32_t a)285 static 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
CalcDist(uint32_t predicted_value,uint32_t actual_value,uint32_t palette_entry)292 static 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
Predict(int x,int y,uint32_t * image)311 static 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
AddSubtractComponentFullWithCoefficient(int a,int b,int c)325 static WEBP_INLINE int AddSubtractComponentFullWithCoefficient(
326 int a, int b, int c) {
327 return Clip255(a + ((b - c) >> 2));
328 }
329
ClampedAddSubtractFullWithCoefficient(uint32_t c0,uint32_t c1,uint32_t c2)330 static 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.
FindBestPaletteEntry(uint32_t src,uint32_t predicted_value,const uint32_t palette[],int palette_size)351 static 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
ApplyBestPaletteEntry(int x,int y,uint32_t new_value,uint32_t palette_value,uint32_t * src,int src_stride,uint32_t * new_image)366 static 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
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)386 static 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_[]
WebPSearchOptimalDeltaPalette(VP8LEncoder * const enc)428 WebPEncodingError 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
WebPSearchOptimalDeltaPalette(VP8LEncoder * const enc)450 WebPEncodingError WebPSearchOptimalDeltaPalette(VP8LEncoder* const enc) {
451 (void)enc;
452 return VP8_ENC_ERROR_INVALID_CONFIGURATION;
453 }
454
455 #endif // WEBP_EXPERIMENTAL_FEATURES
456