1 // Copyright 2016 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 // Image transform methods for lossless encoder. 11 // 12 // Authors: Vikas Arora (vikaas.arora (at) gmail.com) 13 // Jyrki Alakuijala (jyrki (at) google.com) 14 // Urvang Joshi (urvang (at) google.com) 15 // Vincent Rabaud (vrabaud (at) google.com) 16 17 #include "src/dsp/lossless.h" 18 #include "src/dsp/lossless_common.h" 19 #include "src/enc/vp8li_enc.h" 20 21 #define MAX_DIFF_COST (1e30f) 22 23 static const float kSpatialPredictorBias = 15.f; 24 static const int kPredLowEffort = 11; 25 static const uint32_t kMaskAlpha = 0xff000000; 26 27 // Mostly used to reduce code size + readability 28 static WEBP_INLINE int GetMin(int a, int b) { return (a > b) ? b : a; } 29 30 //------------------------------------------------------------------------------ 31 // Methods to calculate Entropy (Shannon). 32 33 static float PredictionCostSpatial(const int counts[256], int weight_0, 34 double exp_val) { 35 const int significant_symbols = 256 >> 4; 36 const double exp_decay_factor = 0.6; 37 double bits = weight_0 * counts[0]; 38 int i; 39 for (i = 1; i < significant_symbols; ++i) { 40 bits += exp_val * (counts[i] + counts[256 - i]); 41 exp_val *= exp_decay_factor; 42 } 43 return (float)(-0.1 * bits); 44 } 45 46 static float PredictionCostSpatialHistogram(const int accumulated[4][256], 47 const int tile[4][256]) { 48 int i; 49 double retval = 0; 50 for (i = 0; i < 4; ++i) { 51 const double kExpValue = 0.94; 52 retval += PredictionCostSpatial(tile[i], 1, kExpValue); 53 retval += VP8LCombinedShannonEntropy(tile[i], accumulated[i]); 54 } 55 return (float)retval; 56 } 57 58 static WEBP_INLINE void UpdateHisto(int histo_argb[4][256], uint32_t argb) { 59 ++histo_argb[0][argb >> 24]; 60 ++histo_argb[1][(argb >> 16) & 0xff]; 61 ++histo_argb[2][(argb >> 8) & 0xff]; 62 ++histo_argb[3][argb & 0xff]; 63 } 64 65 //------------------------------------------------------------------------------ 66 // Spatial transform functions. 67 68 static WEBP_INLINE void PredictBatch(int mode, int x_start, int y, 69 int num_pixels, const uint32_t* current, 70 const uint32_t* upper, uint32_t* out) { 71 if (x_start == 0) { 72 if (y == 0) { 73 // ARGB_BLACK. 74 VP8LPredictorsSub[0](current, NULL, 1, out); 75 } else { 76 // Top one. 77 VP8LPredictorsSub[2](current, upper, 1, out); 78 } 79 ++x_start; 80 ++out; 81 --num_pixels; 82 } 83 if (y == 0) { 84 // Left one. 85 VP8LPredictorsSub[1](current + x_start, NULL, num_pixels, out); 86 } else { 87 VP8LPredictorsSub[mode](current + x_start, upper + x_start, num_pixels, 88 out); 89 } 90 } 91 92 #if (WEBP_NEAR_LOSSLESS == 1) 93 static WEBP_INLINE int GetMax(int a, int b) { return (a < b) ? b : a; } 94 95 static int MaxDiffBetweenPixels(uint32_t p1, uint32_t p2) { 96 const int diff_a = abs((int)(p1 >> 24) - (int)(p2 >> 24)); 97 const int diff_r = abs((int)((p1 >> 16) & 0xff) - (int)((p2 >> 16) & 0xff)); 98 const int diff_g = abs((int)((p1 >> 8) & 0xff) - (int)((p2 >> 8) & 0xff)); 99 const int diff_b = abs((int)(p1 & 0xff) - (int)(p2 & 0xff)); 100 return GetMax(GetMax(diff_a, diff_r), GetMax(diff_g, diff_b)); 101 } 102 103 static int MaxDiffAroundPixel(uint32_t current, uint32_t up, uint32_t down, 104 uint32_t left, uint32_t right) { 105 const int diff_up = MaxDiffBetweenPixels(current, up); 106 const int diff_down = MaxDiffBetweenPixels(current, down); 107 const int diff_left = MaxDiffBetweenPixels(current, left); 108 const int diff_right = MaxDiffBetweenPixels(current, right); 109 return GetMax(GetMax(diff_up, diff_down), GetMax(diff_left, diff_right)); 110 } 111 112 static uint32_t AddGreenToBlueAndRed(uint32_t argb) { 113 const uint32_t green = (argb >> 8) & 0xff; 114 uint32_t red_blue = argb & 0x00ff00ffu; 115 red_blue += (green << 16) | green; 116 red_blue &= 0x00ff00ffu; 117 return (argb & 0xff00ff00u) | red_blue; 118 } 119 120 static void MaxDiffsForRow(int width, int stride, const uint32_t* const argb, 121 uint8_t* const max_diffs, int used_subtract_green) { 122 uint32_t current, up, down, left, right; 123 int x; 124 if (width <= 2) return; 125 current = argb[0]; 126 right = argb[1]; 127 if (used_subtract_green) { 128 current = AddGreenToBlueAndRed(current); 129 right = AddGreenToBlueAndRed(right); 130 } 131 // max_diffs[0] and max_diffs[width - 1] are never used. 132 for (x = 1; x < width - 1; ++x) { 133 up = argb[-stride + x]; 134 down = argb[stride + x]; 135 left = current; 136 current = right; 137 right = argb[x + 1]; 138 if (used_subtract_green) { 139 up = AddGreenToBlueAndRed(up); 140 down = AddGreenToBlueAndRed(down); 141 right = AddGreenToBlueAndRed(right); 142 } 143 max_diffs[x] = MaxDiffAroundPixel(current, up, down, left, right); 144 } 145 } 146 147 // Quantize the difference between the actual component value and its prediction 148 // to a multiple of quantization, working modulo 256, taking care not to cross 149 // a boundary (inclusive upper limit). 150 static uint8_t NearLosslessComponent(uint8_t value, uint8_t predict, 151 uint8_t boundary, int quantization) { 152 const int residual = (value - predict) & 0xff; 153 const int boundary_residual = (boundary - predict) & 0xff; 154 const int lower = residual & ~(quantization - 1); 155 const int upper = lower + quantization; 156 // Resolve ties towards a value closer to the prediction (i.e. towards lower 157 // if value comes after prediction and towards upper otherwise). 158 const int bias = ((boundary - value) & 0xff) < boundary_residual; 159 if (residual - lower < upper - residual + bias) { 160 // lower is closer to residual than upper. 161 if (residual > boundary_residual && lower <= boundary_residual) { 162 // Halve quantization step to avoid crossing boundary. This midpoint is 163 // on the same side of boundary as residual because midpoint >= residual 164 // (since lower is closer than upper) and residual is above the boundary. 165 return lower + (quantization >> 1); 166 } 167 return lower; 168 } else { 169 // upper is closer to residual than lower. 170 if (residual <= boundary_residual && upper > boundary_residual) { 171 // Halve quantization step to avoid crossing boundary. This midpoint is 172 // on the same side of boundary as residual because midpoint <= residual 173 // (since upper is closer than lower) and residual is below the boundary. 174 return lower + (quantization >> 1); 175 } 176 return upper & 0xff; 177 } 178 } 179 180 // Quantize every component of the difference between the actual pixel value and 181 // its prediction to a multiple of a quantization (a power of 2, not larger than 182 // max_quantization which is a power of 2, smaller than max_diff). Take care if 183 // value and predict have undergone subtract green, which means that red and 184 // blue are represented as offsets from green. 185 #define NEAR_LOSSLESS_DIFF(a, b) (uint8_t)((((int)(a) - (int)(b))) & 0xff) 186 static uint32_t NearLossless(uint32_t value, uint32_t predict, 187 int max_quantization, int max_diff, 188 int used_subtract_green) { 189 int quantization; 190 uint8_t new_green = 0; 191 uint8_t green_diff = 0; 192 uint8_t a, r, g, b; 193 if (max_diff <= 2) { 194 return VP8LSubPixels(value, predict); 195 } 196 quantization = max_quantization; 197 while (quantization >= max_diff) { 198 quantization >>= 1; 199 } 200 if ((value >> 24) == 0 || (value >> 24) == 0xff) { 201 // Preserve transparency of fully transparent or fully opaque pixels. 202 a = NEAR_LOSSLESS_DIFF(value >> 24, predict >> 24); 203 } else { 204 a = NearLosslessComponent(value >> 24, predict >> 24, 0xff, quantization); 205 } 206 g = NearLosslessComponent((value >> 8) & 0xff, (predict >> 8) & 0xff, 0xff, 207 quantization); 208 if (used_subtract_green) { 209 // The green offset will be added to red and blue components during decoding 210 // to obtain the actual red and blue values. 211 new_green = ((predict >> 8) + g) & 0xff; 212 // The amount by which green has been adjusted during quantization. It is 213 // subtracted from red and blue for compensation, to avoid accumulating two 214 // quantization errors in them. 215 green_diff = NEAR_LOSSLESS_DIFF(new_green, value >> 8); 216 } 217 r = NearLosslessComponent(NEAR_LOSSLESS_DIFF(value >> 16, green_diff), 218 (predict >> 16) & 0xff, 0xff - new_green, 219 quantization); 220 b = NearLosslessComponent(NEAR_LOSSLESS_DIFF(value, green_diff), 221 predict & 0xff, 0xff - new_green, quantization); 222 return ((uint32_t)a << 24) | ((uint32_t)r << 16) | ((uint32_t)g << 8) | b; 223 } 224 #undef NEAR_LOSSLESS_DIFF 225 #endif // (WEBP_NEAR_LOSSLESS == 1) 226 227 // Stores the difference between the pixel and its prediction in "out". 228 // In case of a lossy encoding, updates the source image to avoid propagating 229 // the deviation further to pixels which depend on the current pixel for their 230 // predictions. 231 static WEBP_INLINE void GetResidual( 232 int width, int height, uint32_t* const upper_row, 233 uint32_t* const current_row, const uint8_t* const max_diffs, int mode, 234 int x_start, int x_end, int y, int max_quantization, int exact, 235 int used_subtract_green, uint32_t* const out) { 236 if (exact) { 237 PredictBatch(mode, x_start, y, x_end - x_start, current_row, upper_row, 238 out); 239 } else { 240 const VP8LPredictorFunc pred_func = VP8LPredictors[mode]; 241 int x; 242 for (x = x_start; x < x_end; ++x) { 243 uint32_t predict; 244 uint32_t residual; 245 if (y == 0) { 246 predict = (x == 0) ? ARGB_BLACK : current_row[x - 1]; // Left. 247 } else if (x == 0) { 248 predict = upper_row[x]; // Top. 249 } else { 250 predict = pred_func(current_row[x - 1], upper_row + x); 251 } 252 #if (WEBP_NEAR_LOSSLESS == 1) 253 if (max_quantization == 1 || mode == 0 || y == 0 || y == height - 1 || 254 x == 0 || x == width - 1) { 255 residual = VP8LSubPixels(current_row[x], predict); 256 } else { 257 residual = NearLossless(current_row[x], predict, max_quantization, 258 max_diffs[x], used_subtract_green); 259 // Update the source image. 260 current_row[x] = VP8LAddPixels(predict, residual); 261 // x is never 0 here so we do not need to update upper_row like below. 262 } 263 #else 264 (void)max_diffs; 265 (void)height; 266 (void)max_quantization; 267 (void)used_subtract_green; 268 residual = VP8LSubPixels(current_row[x], predict); 269 #endif 270 if ((current_row[x] & kMaskAlpha) == 0) { 271 // If alpha is 0, cleanup RGB. We can choose the RGB values of the 272 // residual for best compression. The prediction of alpha itself can be 273 // non-zero and must be kept though. We choose RGB of the residual to be 274 // 0. 275 residual &= kMaskAlpha; 276 // Update the source image. 277 current_row[x] = predict & ~kMaskAlpha; 278 // The prediction for the rightmost pixel in a row uses the leftmost 279 // pixel 280 // in that row as its top-right context pixel. Hence if we change the 281 // leftmost pixel of current_row, the corresponding change must be 282 // applied 283 // to upper_row as well where top-right context is being read from. 284 if (x == 0 && y != 0) upper_row[width] = current_row[0]; 285 } 286 out[x - x_start] = residual; 287 } 288 } 289 } 290 291 // Returns best predictor and updates the accumulated histogram. 292 // If max_quantization > 1, assumes that near lossless processing will be 293 // applied, quantizing residuals to multiples of quantization levels up to 294 // max_quantization (the actual quantization level depends on smoothness near 295 // the given pixel). 296 static int GetBestPredictorForTile(int width, int height, 297 int tile_x, int tile_y, int bits, 298 int accumulated[4][256], 299 uint32_t* const argb_scratch, 300 const uint32_t* const argb, 301 int max_quantization, 302 int exact, int used_subtract_green, 303 const uint32_t* const modes) { 304 const int kNumPredModes = 14; 305 const int start_x = tile_x << bits; 306 const int start_y = tile_y << bits; 307 const int tile_size = 1 << bits; 308 const int max_y = GetMin(tile_size, height - start_y); 309 const int max_x = GetMin(tile_size, width - start_x); 310 // Whether there exist columns just outside the tile. 311 const int have_left = (start_x > 0); 312 // Position and size of the strip covering the tile and adjacent columns if 313 // they exist. 314 const int context_start_x = start_x - have_left; 315 #if (WEBP_NEAR_LOSSLESS == 1) 316 const int context_width = max_x + have_left + (max_x < width - start_x); 317 #endif 318 const int tiles_per_row = VP8LSubSampleSize(width, bits); 319 // Prediction modes of the left and above neighbor tiles. 320 const int left_mode = (tile_x > 0) ? 321 (modes[tile_y * tiles_per_row + tile_x - 1] >> 8) & 0xff : 0xff; 322 const int above_mode = (tile_y > 0) ? 323 (modes[(tile_y - 1) * tiles_per_row + tile_x] >> 8) & 0xff : 0xff; 324 // The width of upper_row and current_row is one pixel larger than image width 325 // to allow the top right pixel to point to the leftmost pixel of the next row 326 // when at the right edge. 327 uint32_t* upper_row = argb_scratch; 328 uint32_t* current_row = upper_row + width + 1; 329 uint8_t* const max_diffs = (uint8_t*)(current_row + width + 1); 330 float best_diff = MAX_DIFF_COST; 331 int best_mode = 0; 332 int mode; 333 int histo_stack_1[4][256]; 334 int histo_stack_2[4][256]; 335 // Need pointers to be able to swap arrays. 336 int (*histo_argb)[256] = histo_stack_1; 337 int (*best_histo)[256] = histo_stack_2; 338 int i, j; 339 uint32_t residuals[1 << MAX_TRANSFORM_BITS]; 340 assert(bits <= MAX_TRANSFORM_BITS); 341 assert(max_x <= (1 << MAX_TRANSFORM_BITS)); 342 343 for (mode = 0; mode < kNumPredModes; ++mode) { 344 float cur_diff; 345 int relative_y; 346 memset(histo_argb, 0, sizeof(histo_stack_1)); 347 if (start_y > 0) { 348 // Read the row above the tile which will become the first upper_row. 349 // Include a pixel to the left if it exists; include a pixel to the right 350 // in all cases (wrapping to the leftmost pixel of the next row if it does 351 // not exist). 352 memcpy(current_row + context_start_x, 353 argb + (start_y - 1) * width + context_start_x, 354 sizeof(*argb) * (max_x + have_left + 1)); 355 } 356 for (relative_y = 0; relative_y < max_y; ++relative_y) { 357 const int y = start_y + relative_y; 358 int relative_x; 359 uint32_t* tmp = upper_row; 360 upper_row = current_row; 361 current_row = tmp; 362 // Read current_row. Include a pixel to the left if it exists; include a 363 // pixel to the right in all cases except at the bottom right corner of 364 // the image (wrapping to the leftmost pixel of the next row if it does 365 // not exist in the current row). 366 memcpy(current_row + context_start_x, 367 argb + y * width + context_start_x, 368 sizeof(*argb) * (max_x + have_left + (y + 1 < height))); 369 #if (WEBP_NEAR_LOSSLESS == 1) 370 if (max_quantization > 1 && y >= 1 && y + 1 < height) { 371 MaxDiffsForRow(context_width, width, argb + y * width + context_start_x, 372 max_diffs + context_start_x, used_subtract_green); 373 } 374 #endif 375 376 GetResidual(width, height, upper_row, current_row, max_diffs, mode, 377 start_x, start_x + max_x, y, max_quantization, exact, 378 used_subtract_green, residuals); 379 for (relative_x = 0; relative_x < max_x; ++relative_x) { 380 UpdateHisto(histo_argb, residuals[relative_x]); 381 } 382 } 383 cur_diff = PredictionCostSpatialHistogram( 384 (const int (*)[256])accumulated, (const int (*)[256])histo_argb); 385 // Favor keeping the areas locally similar. 386 if (mode == left_mode) cur_diff -= kSpatialPredictorBias; 387 if (mode == above_mode) cur_diff -= kSpatialPredictorBias; 388 389 if (cur_diff < best_diff) { 390 int (*tmp)[256] = histo_argb; 391 histo_argb = best_histo; 392 best_histo = tmp; 393 best_diff = cur_diff; 394 best_mode = mode; 395 } 396 } 397 398 for (i = 0; i < 4; i++) { 399 for (j = 0; j < 256; j++) { 400 accumulated[i][j] += best_histo[i][j]; 401 } 402 } 403 404 return best_mode; 405 } 406 407 // Converts pixels of the image to residuals with respect to predictions. 408 // If max_quantization > 1, applies near lossless processing, quantizing 409 // residuals to multiples of quantization levels up to max_quantization 410 // (the actual quantization level depends on smoothness near the given pixel). 411 static void CopyImageWithPrediction(int width, int height, 412 int bits, uint32_t* const modes, 413 uint32_t* const argb_scratch, 414 uint32_t* const argb, 415 int low_effort, int max_quantization, 416 int exact, int used_subtract_green) { 417 const int tiles_per_row = VP8LSubSampleSize(width, bits); 418 // The width of upper_row and current_row is one pixel larger than image width 419 // to allow the top right pixel to point to the leftmost pixel of the next row 420 // when at the right edge. 421 uint32_t* upper_row = argb_scratch; 422 uint32_t* current_row = upper_row + width + 1; 423 uint8_t* current_max_diffs = (uint8_t*)(current_row + width + 1); 424 #if (WEBP_NEAR_LOSSLESS == 1) 425 uint8_t* lower_max_diffs = current_max_diffs + width; 426 #endif 427 int y; 428 429 for (y = 0; y < height; ++y) { 430 int x; 431 uint32_t* const tmp32 = upper_row; 432 upper_row = current_row; 433 current_row = tmp32; 434 memcpy(current_row, argb + y * width, 435 sizeof(*argb) * (width + (y + 1 < height))); 436 437 if (low_effort) { 438 PredictBatch(kPredLowEffort, 0, y, width, current_row, upper_row, 439 argb + y * width); 440 } else { 441 #if (WEBP_NEAR_LOSSLESS == 1) 442 if (max_quantization > 1) { 443 // Compute max_diffs for the lower row now, because that needs the 444 // contents of argb for the current row, which we will overwrite with 445 // residuals before proceeding with the next row. 446 uint8_t* const tmp8 = current_max_diffs; 447 current_max_diffs = lower_max_diffs; 448 lower_max_diffs = tmp8; 449 if (y + 2 < height) { 450 MaxDiffsForRow(width, width, argb + (y + 1) * width, lower_max_diffs, 451 used_subtract_green); 452 } 453 } 454 #endif 455 for (x = 0; x < width;) { 456 const int mode = 457 (modes[(y >> bits) * tiles_per_row + (x >> bits)] >> 8) & 0xff; 458 int x_end = x + (1 << bits); 459 if (x_end > width) x_end = width; 460 GetResidual(width, height, upper_row, current_row, current_max_diffs, 461 mode, x, x_end, y, max_quantization, exact, 462 used_subtract_green, argb + y * width + x); 463 x = x_end; 464 } 465 } 466 } 467 } 468 469 // Finds the best predictor for each tile, and converts the image to residuals 470 // with respect to predictions. If near_lossless_quality < 100, applies 471 // near lossless processing, shaving off more bits of residuals for lower 472 // qualities. 473 void VP8LResidualImage(int width, int height, int bits, int low_effort, 474 uint32_t* const argb, uint32_t* const argb_scratch, 475 uint32_t* const image, int near_lossless_quality, 476 int exact, int used_subtract_green) { 477 const int tiles_per_row = VP8LSubSampleSize(width, bits); 478 const int tiles_per_col = VP8LSubSampleSize(height, bits); 479 int tile_y; 480 int histo[4][256]; 481 const int max_quantization = 1 << VP8LNearLosslessBits(near_lossless_quality); 482 if (low_effort) { 483 int i; 484 for (i = 0; i < tiles_per_row * tiles_per_col; ++i) { 485 image[i] = ARGB_BLACK | (kPredLowEffort << 8); 486 } 487 } else { 488 memset(histo, 0, sizeof(histo)); 489 for (tile_y = 0; tile_y < tiles_per_col; ++tile_y) { 490 int tile_x; 491 for (tile_x = 0; tile_x < tiles_per_row; ++tile_x) { 492 const int pred = GetBestPredictorForTile(width, height, tile_x, tile_y, 493 bits, histo, argb_scratch, argb, max_quantization, exact, 494 used_subtract_green, image); 495 image[tile_y * tiles_per_row + tile_x] = ARGB_BLACK | (pred << 8); 496 } 497 } 498 } 499 500 CopyImageWithPrediction(width, height, bits, image, argb_scratch, argb, 501 low_effort, max_quantization, exact, 502 used_subtract_green); 503 } 504 505 //------------------------------------------------------------------------------ 506 // Color transform functions. 507 508 static WEBP_INLINE void MultipliersClear(VP8LMultipliers* const m) { 509 m->green_to_red_ = 0; 510 m->green_to_blue_ = 0; 511 m->red_to_blue_ = 0; 512 } 513 514 static WEBP_INLINE void ColorCodeToMultipliers(uint32_t color_code, 515 VP8LMultipliers* const m) { 516 m->green_to_red_ = (color_code >> 0) & 0xff; 517 m->green_to_blue_ = (color_code >> 8) & 0xff; 518 m->red_to_blue_ = (color_code >> 16) & 0xff; 519 } 520 521 static WEBP_INLINE uint32_t MultipliersToColorCode( 522 const VP8LMultipliers* const m) { 523 return 0xff000000u | 524 ((uint32_t)(m->red_to_blue_) << 16) | 525 ((uint32_t)(m->green_to_blue_) << 8) | 526 m->green_to_red_; 527 } 528 529 static float PredictionCostCrossColor(const int accumulated[256], 530 const int counts[256]) { 531 // Favor low entropy, locally and globally. 532 // Favor small absolute values for PredictionCostSpatial 533 static const double kExpValue = 2.4; 534 return VP8LCombinedShannonEntropy(counts, accumulated) + 535 PredictionCostSpatial(counts, 3, kExpValue); 536 } 537 538 static float GetPredictionCostCrossColorRed( 539 const uint32_t* argb, int stride, int tile_width, int tile_height, 540 VP8LMultipliers prev_x, VP8LMultipliers prev_y, int green_to_red, 541 const int accumulated_red_histo[256]) { 542 int histo[256] = { 0 }; 543 float cur_diff; 544 545 VP8LCollectColorRedTransforms(argb, stride, tile_width, tile_height, 546 green_to_red, histo); 547 548 cur_diff = PredictionCostCrossColor(accumulated_red_histo, histo); 549 if ((uint8_t)green_to_red == prev_x.green_to_red_) { 550 cur_diff -= 3; // favor keeping the areas locally similar 551 } 552 if ((uint8_t)green_to_red == prev_y.green_to_red_) { 553 cur_diff -= 3; // favor keeping the areas locally similar 554 } 555 if (green_to_red == 0) { 556 cur_diff -= 3; 557 } 558 return cur_diff; 559 } 560 561 static void GetBestGreenToRed( 562 const uint32_t* argb, int stride, int tile_width, int tile_height, 563 VP8LMultipliers prev_x, VP8LMultipliers prev_y, int quality, 564 const int accumulated_red_histo[256], VP8LMultipliers* const best_tx) { 565 const int kMaxIters = 4 + ((7 * quality) >> 8); // in range [4..6] 566 int green_to_red_best = 0; 567 int iter, offset; 568 float best_diff = GetPredictionCostCrossColorRed( 569 argb, stride, tile_width, tile_height, prev_x, prev_y, 570 green_to_red_best, accumulated_red_histo); 571 for (iter = 0; iter < kMaxIters; ++iter) { 572 // ColorTransformDelta is a 3.5 bit fixed point, so 32 is equal to 573 // one in color computation. Having initial delta here as 1 is sufficient 574 // to explore the range of (-2, 2). 575 const int delta = 32 >> iter; 576 // Try a negative and a positive delta from the best known value. 577 for (offset = -delta; offset <= delta; offset += 2 * delta) { 578 const int green_to_red_cur = offset + green_to_red_best; 579 const float cur_diff = GetPredictionCostCrossColorRed( 580 argb, stride, tile_width, tile_height, prev_x, prev_y, 581 green_to_red_cur, accumulated_red_histo); 582 if (cur_diff < best_diff) { 583 best_diff = cur_diff; 584 green_to_red_best = green_to_red_cur; 585 } 586 } 587 } 588 best_tx->green_to_red_ = green_to_red_best; 589 } 590 591 static float GetPredictionCostCrossColorBlue( 592 const uint32_t* argb, int stride, int tile_width, int tile_height, 593 VP8LMultipliers prev_x, VP8LMultipliers prev_y, 594 int green_to_blue, int red_to_blue, const int accumulated_blue_histo[256]) { 595 int histo[256] = { 0 }; 596 float cur_diff; 597 598 VP8LCollectColorBlueTransforms(argb, stride, tile_width, tile_height, 599 green_to_blue, red_to_blue, histo); 600 601 cur_diff = PredictionCostCrossColor(accumulated_blue_histo, histo); 602 if ((uint8_t)green_to_blue == prev_x.green_to_blue_) { 603 cur_diff -= 3; // favor keeping the areas locally similar 604 } 605 if ((uint8_t)green_to_blue == prev_y.green_to_blue_) { 606 cur_diff -= 3; // favor keeping the areas locally similar 607 } 608 if ((uint8_t)red_to_blue == prev_x.red_to_blue_) { 609 cur_diff -= 3; // favor keeping the areas locally similar 610 } 611 if ((uint8_t)red_to_blue == prev_y.red_to_blue_) { 612 cur_diff -= 3; // favor keeping the areas locally similar 613 } 614 if (green_to_blue == 0) { 615 cur_diff -= 3; 616 } 617 if (red_to_blue == 0) { 618 cur_diff -= 3; 619 } 620 return cur_diff; 621 } 622 623 #define kGreenRedToBlueNumAxis 8 624 #define kGreenRedToBlueMaxIters 7 625 static void GetBestGreenRedToBlue( 626 const uint32_t* argb, int stride, int tile_width, int tile_height, 627 VP8LMultipliers prev_x, VP8LMultipliers prev_y, int quality, 628 const int accumulated_blue_histo[256], 629 VP8LMultipliers* const best_tx) { 630 const int8_t offset[kGreenRedToBlueNumAxis][2] = 631 {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; 632 const int8_t delta_lut[kGreenRedToBlueMaxIters] = { 16, 16, 8, 4, 2, 2, 2 }; 633 const int iters = 634 (quality < 25) ? 1 : (quality > 50) ? kGreenRedToBlueMaxIters : 4; 635 int green_to_blue_best = 0; 636 int red_to_blue_best = 0; 637 int iter; 638 // Initial value at origin: 639 float best_diff = GetPredictionCostCrossColorBlue( 640 argb, stride, tile_width, tile_height, prev_x, prev_y, 641 green_to_blue_best, red_to_blue_best, accumulated_blue_histo); 642 for (iter = 0; iter < iters; ++iter) { 643 const int delta = delta_lut[iter]; 644 int axis; 645 for (axis = 0; axis < kGreenRedToBlueNumAxis; ++axis) { 646 const int green_to_blue_cur = 647 offset[axis][0] * delta + green_to_blue_best; 648 const int red_to_blue_cur = offset[axis][1] * delta + red_to_blue_best; 649 const float cur_diff = GetPredictionCostCrossColorBlue( 650 argb, stride, tile_width, tile_height, prev_x, prev_y, 651 green_to_blue_cur, red_to_blue_cur, accumulated_blue_histo); 652 if (cur_diff < best_diff) { 653 best_diff = cur_diff; 654 green_to_blue_best = green_to_blue_cur; 655 red_to_blue_best = red_to_blue_cur; 656 } 657 if (quality < 25 && iter == 4) { 658 // Only axis aligned diffs for lower quality. 659 break; // next iter. 660 } 661 } 662 if (delta == 2 && green_to_blue_best == 0 && red_to_blue_best == 0) { 663 // Further iterations would not help. 664 break; // out of iter-loop. 665 } 666 } 667 best_tx->green_to_blue_ = green_to_blue_best; 668 best_tx->red_to_blue_ = red_to_blue_best; 669 } 670 #undef kGreenRedToBlueMaxIters 671 #undef kGreenRedToBlueNumAxis 672 673 static VP8LMultipliers GetBestColorTransformForTile( 674 int tile_x, int tile_y, int bits, 675 VP8LMultipliers prev_x, 676 VP8LMultipliers prev_y, 677 int quality, int xsize, int ysize, 678 const int accumulated_red_histo[256], 679 const int accumulated_blue_histo[256], 680 const uint32_t* const argb) { 681 const int max_tile_size = 1 << bits; 682 const int tile_y_offset = tile_y * max_tile_size; 683 const int tile_x_offset = tile_x * max_tile_size; 684 const int all_x_max = GetMin(tile_x_offset + max_tile_size, xsize); 685 const int all_y_max = GetMin(tile_y_offset + max_tile_size, ysize); 686 const int tile_width = all_x_max - tile_x_offset; 687 const int tile_height = all_y_max - tile_y_offset; 688 const uint32_t* const tile_argb = argb + tile_y_offset * xsize 689 + tile_x_offset; 690 VP8LMultipliers best_tx; 691 MultipliersClear(&best_tx); 692 693 GetBestGreenToRed(tile_argb, xsize, tile_width, tile_height, 694 prev_x, prev_y, quality, accumulated_red_histo, &best_tx); 695 GetBestGreenRedToBlue(tile_argb, xsize, tile_width, tile_height, 696 prev_x, prev_y, quality, accumulated_blue_histo, 697 &best_tx); 698 return best_tx; 699 } 700 701 static void CopyTileWithColorTransform(int xsize, int ysize, 702 int tile_x, int tile_y, 703 int max_tile_size, 704 VP8LMultipliers color_transform, 705 uint32_t* argb) { 706 const int xscan = GetMin(max_tile_size, xsize - tile_x); 707 int yscan = GetMin(max_tile_size, ysize - tile_y); 708 argb += tile_y * xsize + tile_x; 709 while (yscan-- > 0) { 710 VP8LTransformColor(&color_transform, argb, xscan); 711 argb += xsize; 712 } 713 } 714 715 void VP8LColorSpaceTransform(int width, int height, int bits, int quality, 716 uint32_t* const argb, uint32_t* image) { 717 const int max_tile_size = 1 << bits; 718 const int tile_xsize = VP8LSubSampleSize(width, bits); 719 const int tile_ysize = VP8LSubSampleSize(height, bits); 720 int accumulated_red_histo[256] = { 0 }; 721 int accumulated_blue_histo[256] = { 0 }; 722 int tile_x, tile_y; 723 VP8LMultipliers prev_x, prev_y; 724 MultipliersClear(&prev_y); 725 MultipliersClear(&prev_x); 726 for (tile_y = 0; tile_y < tile_ysize; ++tile_y) { 727 for (tile_x = 0; tile_x < tile_xsize; ++tile_x) { 728 int y; 729 const int tile_x_offset = tile_x * max_tile_size; 730 const int tile_y_offset = tile_y * max_tile_size; 731 const int all_x_max = GetMin(tile_x_offset + max_tile_size, width); 732 const int all_y_max = GetMin(tile_y_offset + max_tile_size, height); 733 const int offset = tile_y * tile_xsize + tile_x; 734 if (tile_y != 0) { 735 ColorCodeToMultipliers(image[offset - tile_xsize], &prev_y); 736 } 737 prev_x = GetBestColorTransformForTile(tile_x, tile_y, bits, 738 prev_x, prev_y, 739 quality, width, height, 740 accumulated_red_histo, 741 accumulated_blue_histo, 742 argb); 743 image[offset] = MultipliersToColorCode(&prev_x); 744 CopyTileWithColorTransform(width, height, tile_x_offset, tile_y_offset, 745 max_tile_size, prev_x, argb); 746 747 // Gather accumulated histogram data. 748 for (y = tile_y_offset; y < all_y_max; ++y) { 749 int ix = y * width + tile_x_offset; 750 const int ix_end = ix + all_x_max - tile_x_offset; 751 for (; ix < ix_end; ++ix) { 752 const uint32_t pix = argb[ix]; 753 if (ix >= 2 && 754 pix == argb[ix - 2] && 755 pix == argb[ix - 1]) { 756 continue; // repeated pixels are handled by backward references 757 } 758 if (ix >= width + 2 && 759 argb[ix - 2] == argb[ix - width - 2] && 760 argb[ix - 1] == argb[ix - width - 1] && 761 pix == argb[ix - width]) { 762 continue; // repeated pixels are handled by backward references 763 } 764 ++accumulated_red_histo[(pix >> 16) & 0xff]; 765 ++accumulated_blue_histo[(pix >> 0) & 0xff]; 766 } 767 } 768 } 769 } 770 } 771