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 (at) google.com) 11 // 12 13 #include "./delta_palettization.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. 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 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. 281 static WEBP_INLINE int Square(int x) { 282 return x * x; 283 } 284 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 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 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 325 static WEBP_INLINE int AddSubtractComponentFullWithCoefficient( 326 int a, int b, int c) { 327 return Clip255(a + ((b - c) >> 2)); 328 } 329 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. 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 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 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_[] 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 450 WebPEncodingError WebPSearchOptimalDeltaPalette(VP8LEncoder* const enc) { 451 (void)enc; 452 return VP8_ENC_ERROR_INVALID_CONFIGURATION; 453 } 454 455 #endif // WEBP_EXPERIMENTAL_FEATURES 456
