1 // Copyright 2012 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 // main entry for the lossless encoder. 11 // 12 // Author: Vikas Arora (vikaas.arora (at) gmail.com) 13 // 14 15 #include <assert.h> 16 #include <stdlib.h> 17 18 #include "./backward_references.h" 19 #include "./histogram.h" 20 #include "./vp8enci.h" 21 #include "./vp8li.h" 22 #include "../dsp/lossless.h" 23 #include "../utils/bit_writer.h" 24 #include "../utils/huffman_encode.h" 25 #include "../utils/utils.h" 26 #include "../webp/format_constants.h" 27 28 #include "./delta_palettization.h" 29 30 #define PALETTE_KEY_RIGHT_SHIFT 22 // Key for 1K buffer. 31 // Maximum number of histogram images (sub-blocks). 32 #define MAX_HUFF_IMAGE_SIZE 2600 33 34 // Palette reordering for smaller sum of deltas (and for smaller storage). 35 36 static int PaletteCompareColorsForQsort(const void* p1, const void* p2) { 37 const uint32_t a = WebPMemToUint32(p1); 38 const uint32_t b = WebPMemToUint32(p2); 39 assert(a != b); 40 return (a < b) ? -1 : 1; 41 } 42 43 static WEBP_INLINE uint32_t PaletteComponentDistance(uint32_t v) { 44 return (v <= 128) ? v : (256 - v); 45 } 46 47 // Computes a value that is related to the entropy created by the 48 // palette entry diff. 49 // 50 // Note that the last & 0xff is a no-operation in the next statement, but 51 // removed by most compilers and is here only for regularity of the code. 52 static WEBP_INLINE uint32_t PaletteColorDistance(uint32_t col1, uint32_t col2) { 53 const uint32_t diff = VP8LSubPixels(col1, col2); 54 const int kMoreWeightForRGBThanForAlpha = 9; 55 uint32_t score; 56 score = PaletteComponentDistance((diff >> 0) & 0xff); 57 score += PaletteComponentDistance((diff >> 8) & 0xff); 58 score += PaletteComponentDistance((diff >> 16) & 0xff); 59 score *= kMoreWeightForRGBThanForAlpha; 60 score += PaletteComponentDistance((diff >> 24) & 0xff); 61 return score; 62 } 63 64 static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) { 65 const uint32_t tmp = *col1; 66 *col1 = *col2; 67 *col2 = tmp; 68 } 69 70 static void GreedyMinimizeDeltas(uint32_t palette[], int num_colors) { 71 // Find greedily always the closest color of the predicted color to minimize 72 // deltas in the palette. This reduces storage needs since the 73 // palette is stored with delta encoding. 74 uint32_t predict = 0x00000000; 75 int i, k; 76 for (i = 0; i < num_colors; ++i) { 77 int best_ix = i; 78 uint32_t best_score = ~0U; 79 for (k = i; k < num_colors; ++k) { 80 const uint32_t cur_score = PaletteColorDistance(palette[k], predict); 81 if (best_score > cur_score) { 82 best_score = cur_score; 83 best_ix = k; 84 } 85 } 86 SwapColor(&palette[best_ix], &palette[i]); 87 predict = palette[i]; 88 } 89 } 90 91 // The palette has been sorted by alpha. This function checks if the other 92 // components of the palette have a monotonic development with regards to 93 // position in the palette. If all have monotonic development, there is 94 // no benefit to re-organize them greedily. A monotonic development 95 // would be spotted in green-only situations (like lossy alpha) or gray-scale 96 // images. 97 static int PaletteHasNonMonotonousDeltas(uint32_t palette[], int num_colors) { 98 uint32_t predict = 0x000000; 99 int i; 100 uint8_t sign_found = 0x00; 101 for (i = 0; i < num_colors; ++i) { 102 const uint32_t diff = VP8LSubPixels(palette[i], predict); 103 const uint8_t rd = (diff >> 16) & 0xff; 104 const uint8_t gd = (diff >> 8) & 0xff; 105 const uint8_t bd = (diff >> 0) & 0xff; 106 if (rd != 0x00) { 107 sign_found |= (rd < 0x80) ? 1 : 2; 108 } 109 if (gd != 0x00) { 110 sign_found |= (gd < 0x80) ? 8 : 16; 111 } 112 if (bd != 0x00) { 113 sign_found |= (bd < 0x80) ? 64 : 128; 114 } 115 predict = palette[i]; 116 } 117 return (sign_found & (sign_found << 1)) != 0; // two consequent signs. 118 } 119 120 // ----------------------------------------------------------------------------- 121 // Palette 122 123 // If number of colors in the image is less than or equal to MAX_PALETTE_SIZE, 124 // creates a palette and returns true, else returns false. 125 static int AnalyzeAndCreatePalette(const WebPPicture* const pic, 126 int low_effort, 127 uint32_t palette[MAX_PALETTE_SIZE], 128 int* const palette_size) { 129 int i, x, y, key; 130 int num_colors = 0; 131 uint8_t in_use[MAX_PALETTE_SIZE * 4] = { 0 }; 132 uint32_t colors[MAX_PALETTE_SIZE * 4]; 133 static const uint32_t kHashMul = 0x1e35a7bd; 134 const uint32_t* argb = pic->argb; 135 const int width = pic->width; 136 const int height = pic->height; 137 uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0] 138 139 for (y = 0; y < height; ++y) { 140 for (x = 0; x < width; ++x) { 141 if (argb[x] == last_pix) { 142 continue; 143 } 144 last_pix = argb[x]; 145 key = (kHashMul * last_pix) >> PALETTE_KEY_RIGHT_SHIFT; 146 while (1) { 147 if (!in_use[key]) { 148 colors[key] = last_pix; 149 in_use[key] = 1; 150 ++num_colors; 151 if (num_colors > MAX_PALETTE_SIZE) { 152 return 0; 153 } 154 break; 155 } else if (colors[key] == last_pix) { 156 // The color is already there. 157 break; 158 } else { 159 // Some other color sits there. 160 // Do linear conflict resolution. 161 ++key; 162 key &= (MAX_PALETTE_SIZE * 4 - 1); // key mask for 1K buffer. 163 } 164 } 165 } 166 argb += pic->argb_stride; 167 } 168 169 // TODO(skal): could we reuse in_use[] to speed up EncodePalette()? 170 num_colors = 0; 171 for (i = 0; i < (int)(sizeof(in_use) / sizeof(in_use[0])); ++i) { 172 if (in_use[i]) { 173 palette[num_colors] = colors[i]; 174 ++num_colors; 175 } 176 } 177 *palette_size = num_colors; 178 qsort(palette, num_colors, sizeof(*palette), PaletteCompareColorsForQsort); 179 if (!low_effort && PaletteHasNonMonotonousDeltas(palette, num_colors)) { 180 GreedyMinimizeDeltas(palette, num_colors); 181 } 182 return 1; 183 } 184 185 // These five modes are evaluated and their respective entropy is computed. 186 typedef enum { 187 kDirect = 0, 188 kSpatial = 1, 189 kSubGreen = 2, 190 kSpatialSubGreen = 3, 191 kPalette = 4, 192 kNumEntropyIx = 5 193 } EntropyIx; 194 195 typedef enum { 196 kHistoAlpha = 0, 197 kHistoAlphaPred, 198 kHistoGreen, 199 kHistoGreenPred, 200 kHistoRed, 201 kHistoRedPred, 202 kHistoBlue, 203 kHistoBluePred, 204 kHistoRedSubGreen, 205 kHistoRedPredSubGreen, 206 kHistoBlueSubGreen, 207 kHistoBluePredSubGreen, 208 kHistoPalette, 209 kHistoTotal // Must be last. 210 } HistoIx; 211 212 static void AddSingleSubGreen(uint32_t p, uint32_t* r, uint32_t* b) { 213 const uint32_t green = p >> 8; // The upper bits are masked away later. 214 ++r[((p >> 16) - green) & 0xff]; 215 ++b[(p - green) & 0xff]; 216 } 217 218 static void AddSingle(uint32_t p, 219 uint32_t* a, uint32_t* r, uint32_t* g, uint32_t* b) { 220 ++a[p >> 24]; 221 ++r[(p >> 16) & 0xff]; 222 ++g[(p >> 8) & 0xff]; 223 ++b[(p & 0xff)]; 224 } 225 226 static int AnalyzeEntropy(const uint32_t* argb, 227 int width, int height, int argb_stride, 228 int use_palette, 229 EntropyIx* const min_entropy_ix, 230 int* const red_and_blue_always_zero) { 231 // Allocate histogram set with cache_bits = 0. 232 uint32_t* const histo = 233 (uint32_t*)WebPSafeCalloc(kHistoTotal, sizeof(*histo) * 256); 234 if (histo != NULL) { 235 int i, x, y; 236 const uint32_t* prev_row = argb; 237 const uint32_t* curr_row = argb + argb_stride; 238 for (y = 1; y < height; ++y) { 239 uint32_t prev_pix = curr_row[0]; 240 for (x = 1; x < width; ++x) { 241 const uint32_t pix = curr_row[x]; 242 const uint32_t pix_diff = VP8LSubPixels(pix, prev_pix); 243 if ((pix_diff == 0) || (pix == prev_row[x])) continue; 244 prev_pix = pix; 245 AddSingle(pix, 246 &histo[kHistoAlpha * 256], 247 &histo[kHistoRed * 256], 248 &histo[kHistoGreen * 256], 249 &histo[kHistoBlue * 256]); 250 AddSingle(pix_diff, 251 &histo[kHistoAlphaPred * 256], 252 &histo[kHistoRedPred * 256], 253 &histo[kHistoGreenPred * 256], 254 &histo[kHistoBluePred * 256]); 255 AddSingleSubGreen(pix, 256 &histo[kHistoRedSubGreen * 256], 257 &histo[kHistoBlueSubGreen * 256]); 258 AddSingleSubGreen(pix_diff, 259 &histo[kHistoRedPredSubGreen * 256], 260 &histo[kHistoBluePredSubGreen * 256]); 261 { 262 // Approximate the palette by the entropy of the multiplicative hash. 263 const int hash = ((pix + (pix >> 19)) * 0x39c5fba7) >> 24; 264 ++histo[kHistoPalette * 256 + (hash & 0xff)]; 265 } 266 } 267 prev_row = curr_row; 268 curr_row += argb_stride; 269 } 270 { 271 double entropy_comp[kHistoTotal]; 272 double entropy[kNumEntropyIx]; 273 EntropyIx k; 274 EntropyIx last_mode_to_analyze = 275 use_palette ? kPalette : kSpatialSubGreen; 276 int j; 277 // Let's add one zero to the predicted histograms. The zeros are removed 278 // too efficiently by the pix_diff == 0 comparison, at least one of the 279 // zeros is likely to exist. 280 ++histo[kHistoRedPredSubGreen * 256]; 281 ++histo[kHistoBluePredSubGreen * 256]; 282 ++histo[kHistoRedPred * 256]; 283 ++histo[kHistoGreenPred * 256]; 284 ++histo[kHistoBluePred * 256]; 285 ++histo[kHistoAlphaPred * 256]; 286 287 for (j = 0; j < kHistoTotal; ++j) { 288 entropy_comp[j] = VP8LBitsEntropy(&histo[j * 256], 256, NULL); 289 } 290 entropy[kDirect] = entropy_comp[kHistoAlpha] + 291 entropy_comp[kHistoRed] + 292 entropy_comp[kHistoGreen] + 293 entropy_comp[kHistoBlue]; 294 entropy[kSpatial] = entropy_comp[kHistoAlphaPred] + 295 entropy_comp[kHistoRedPred] + 296 entropy_comp[kHistoGreenPred] + 297 entropy_comp[kHistoBluePred]; 298 entropy[kSubGreen] = entropy_comp[kHistoAlpha] + 299 entropy_comp[kHistoRedSubGreen] + 300 entropy_comp[kHistoGreen] + 301 entropy_comp[kHistoBlueSubGreen]; 302 entropy[kSpatialSubGreen] = entropy_comp[kHistoAlphaPred] + 303 entropy_comp[kHistoRedPredSubGreen] + 304 entropy_comp[kHistoGreenPred] + 305 entropy_comp[kHistoBluePredSubGreen]; 306 // Palette mode seems more efficient in a breakeven case. Bias with 1.0. 307 entropy[kPalette] = entropy_comp[kHistoPalette] - 1.0; 308 309 *min_entropy_ix = kDirect; 310 for (k = kDirect + 1; k <= last_mode_to_analyze; ++k) { 311 if (entropy[*min_entropy_ix] > entropy[k]) { 312 *min_entropy_ix = k; 313 } 314 } 315 *red_and_blue_always_zero = 1; 316 // Let's check if the histogram of the chosen entropy mode has 317 // non-zero red and blue values. If all are zero, we can later skip 318 // the cross color optimization. 319 { 320 static const uint8_t kHistoPairs[5][2] = { 321 { kHistoRed, kHistoBlue }, 322 { kHistoRedPred, kHistoBluePred }, 323 { kHistoRedSubGreen, kHistoBlueSubGreen }, 324 { kHistoRedPredSubGreen, kHistoBluePredSubGreen }, 325 { kHistoRed, kHistoBlue } 326 }; 327 const uint32_t* const red_histo = 328 &histo[256 * kHistoPairs[*min_entropy_ix][0]]; 329 const uint32_t* const blue_histo = 330 &histo[256 * kHistoPairs[*min_entropy_ix][1]]; 331 for (i = 1; i < 256; ++i) { 332 if ((red_histo[i] | blue_histo[i]) != 0) { 333 *red_and_blue_always_zero = 0; 334 break; 335 } 336 } 337 } 338 } 339 free(histo); 340 return 1; 341 } else { 342 return 0; 343 } 344 } 345 346 static int GetHistoBits(int method, int use_palette, int width, int height) { 347 // Make tile size a function of encoding method (Range: 0 to 6). 348 int histo_bits = (use_palette ? 9 : 7) - method; 349 while (1) { 350 const int huff_image_size = VP8LSubSampleSize(width, histo_bits) * 351 VP8LSubSampleSize(height, histo_bits); 352 if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break; 353 ++histo_bits; 354 } 355 return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : 356 (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; 357 } 358 359 static int GetTransformBits(int method, int histo_bits) { 360 const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5; 361 return (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits; 362 } 363 364 static int AnalyzeAndInit(VP8LEncoder* const enc) { 365 const WebPPicture* const pic = enc->pic_; 366 const int width = pic->width; 367 const int height = pic->height; 368 const int pix_cnt = width * height; 369 const WebPConfig* const config = enc->config_; 370 const int method = config->method; 371 const int low_effort = (config->method == 0); 372 // we round the block size up, so we're guaranteed to have 373 // at max MAX_REFS_BLOCK_PER_IMAGE blocks used: 374 int refs_block_size = (pix_cnt - 1) / MAX_REFS_BLOCK_PER_IMAGE + 1; 375 assert(pic != NULL && pic->argb != NULL); 376 377 enc->use_cross_color_ = 0; 378 enc->use_predict_ = 0; 379 enc->use_subtract_green_ = 0; 380 enc->use_palette_ = 381 AnalyzeAndCreatePalette(pic, low_effort, 382 enc->palette_, &enc->palette_size_); 383 384 // TODO(jyrki): replace the decision to be based on an actual estimate 385 // of entropy, or even spatial variance of entropy. 386 enc->histo_bits_ = GetHistoBits(method, enc->use_palette_, 387 pic->width, pic->height); 388 enc->transform_bits_ = GetTransformBits(method, enc->histo_bits_); 389 390 if (low_effort) { 391 // AnalyzeEntropy is somewhat slow. 392 enc->use_predict_ = !enc->use_palette_; 393 enc->use_subtract_green_ = !enc->use_palette_; 394 enc->use_cross_color_ = 0; 395 } else { 396 int red_and_blue_always_zero; 397 EntropyIx min_entropy_ix; 398 if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride, 399 enc->use_palette_, &min_entropy_ix, 400 &red_and_blue_always_zero)) { 401 return 0; 402 } 403 enc->use_palette_ = (min_entropy_ix == kPalette); 404 enc->use_subtract_green_ = 405 (min_entropy_ix == kSubGreen) || (min_entropy_ix == kSpatialSubGreen); 406 enc->use_predict_ = 407 (min_entropy_ix == kSpatial) || (min_entropy_ix == kSpatialSubGreen); 408 enc->use_cross_color_ = red_and_blue_always_zero ? 0 : enc->use_predict_; 409 } 410 411 if (!VP8LHashChainInit(&enc->hash_chain_, pix_cnt)) return 0; 412 413 // palette-friendly input typically uses less literals 414 // -> reduce block size a bit 415 if (enc->use_palette_) refs_block_size /= 2; 416 VP8LBackwardRefsInit(&enc->refs_[0], refs_block_size); 417 VP8LBackwardRefsInit(&enc->refs_[1], refs_block_size); 418 419 return 1; 420 } 421 422 // Returns false in case of memory error. 423 static int GetHuffBitLengthsAndCodes( 424 const VP8LHistogramSet* const histogram_image, 425 HuffmanTreeCode* const huffman_codes) { 426 int i, k; 427 int ok = 0; 428 uint64_t total_length_size = 0; 429 uint8_t* mem_buf = NULL; 430 const int histogram_image_size = histogram_image->size; 431 int max_num_symbols = 0; 432 uint8_t* buf_rle = NULL; 433 HuffmanTree* huff_tree = NULL; 434 435 // Iterate over all histograms and get the aggregate number of codes used. 436 for (i = 0; i < histogram_image_size; ++i) { 437 const VP8LHistogram* const histo = histogram_image->histograms[i]; 438 HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 439 for (k = 0; k < 5; ++k) { 440 const int num_symbols = 441 (k == 0) ? VP8LHistogramNumCodes(histo->palette_code_bits_) : 442 (k == 4) ? NUM_DISTANCE_CODES : 256; 443 codes[k].num_symbols = num_symbols; 444 total_length_size += num_symbols; 445 } 446 } 447 448 // Allocate and Set Huffman codes. 449 { 450 uint16_t* codes; 451 uint8_t* lengths; 452 mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size, 453 sizeof(*lengths) + sizeof(*codes)); 454 if (mem_buf == NULL) goto End; 455 456 codes = (uint16_t*)mem_buf; 457 lengths = (uint8_t*)&codes[total_length_size]; 458 for (i = 0; i < 5 * histogram_image_size; ++i) { 459 const int bit_length = huffman_codes[i].num_symbols; 460 huffman_codes[i].codes = codes; 461 huffman_codes[i].code_lengths = lengths; 462 codes += bit_length; 463 lengths += bit_length; 464 if (max_num_symbols < bit_length) { 465 max_num_symbols = bit_length; 466 } 467 } 468 } 469 470 buf_rle = (uint8_t*)WebPSafeMalloc(1ULL, max_num_symbols); 471 huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * max_num_symbols, 472 sizeof(*huff_tree)); 473 if (buf_rle == NULL || huff_tree == NULL) goto End; 474 475 // Create Huffman trees. 476 for (i = 0; i < histogram_image_size; ++i) { 477 HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 478 VP8LHistogram* const histo = histogram_image->histograms[i]; 479 VP8LCreateHuffmanTree(histo->literal_, 15, buf_rle, huff_tree, codes + 0); 480 VP8LCreateHuffmanTree(histo->red_, 15, buf_rle, huff_tree, codes + 1); 481 VP8LCreateHuffmanTree(histo->blue_, 15, buf_rle, huff_tree, codes + 2); 482 VP8LCreateHuffmanTree(histo->alpha_, 15, buf_rle, huff_tree, codes + 3); 483 VP8LCreateHuffmanTree(histo->distance_, 15, buf_rle, huff_tree, codes + 4); 484 } 485 ok = 1; 486 End: 487 WebPSafeFree(huff_tree); 488 WebPSafeFree(buf_rle); 489 if (!ok) { 490 WebPSafeFree(mem_buf); 491 memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes)); 492 } 493 return ok; 494 } 495 496 static void StoreHuffmanTreeOfHuffmanTreeToBitMask( 497 VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) { 498 // RFC 1951 will calm you down if you are worried about this funny sequence. 499 // This sequence is tuned from that, but more weighted for lower symbol count, 500 // and more spiking histograms. 501 static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = { 502 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 503 }; 504 int i; 505 // Throw away trailing zeros: 506 int codes_to_store = CODE_LENGTH_CODES; 507 for (; codes_to_store > 4; --codes_to_store) { 508 if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { 509 break; 510 } 511 } 512 VP8LPutBits(bw, codes_to_store - 4, 4); 513 for (i = 0; i < codes_to_store; ++i) { 514 VP8LPutBits(bw, code_length_bitdepth[kStorageOrder[i]], 3); 515 } 516 } 517 518 static void ClearHuffmanTreeIfOnlyOneSymbol( 519 HuffmanTreeCode* const huffman_code) { 520 int k; 521 int count = 0; 522 for (k = 0; k < huffman_code->num_symbols; ++k) { 523 if (huffman_code->code_lengths[k] != 0) { 524 ++count; 525 if (count > 1) return; 526 } 527 } 528 for (k = 0; k < huffman_code->num_symbols; ++k) { 529 huffman_code->code_lengths[k] = 0; 530 huffman_code->codes[k] = 0; 531 } 532 } 533 534 static void StoreHuffmanTreeToBitMask( 535 VP8LBitWriter* const bw, 536 const HuffmanTreeToken* const tokens, const int num_tokens, 537 const HuffmanTreeCode* const huffman_code) { 538 int i; 539 for (i = 0; i < num_tokens; ++i) { 540 const int ix = tokens[i].code; 541 const int extra_bits = tokens[i].extra_bits; 542 VP8LPutBits(bw, huffman_code->codes[ix], huffman_code->code_lengths[ix]); 543 switch (ix) { 544 case 16: 545 VP8LPutBits(bw, extra_bits, 2); 546 break; 547 case 17: 548 VP8LPutBits(bw, extra_bits, 3); 549 break; 550 case 18: 551 VP8LPutBits(bw, extra_bits, 7); 552 break; 553 } 554 } 555 } 556 557 // 'huff_tree' and 'tokens' are pre-alloacted buffers. 558 static void StoreFullHuffmanCode(VP8LBitWriter* const bw, 559 HuffmanTree* const huff_tree, 560 HuffmanTreeToken* const tokens, 561 const HuffmanTreeCode* const tree) { 562 uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 }; 563 uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 }; 564 const int max_tokens = tree->num_symbols; 565 int num_tokens; 566 HuffmanTreeCode huffman_code; 567 huffman_code.num_symbols = CODE_LENGTH_CODES; 568 huffman_code.code_lengths = code_length_bitdepth; 569 huffman_code.codes = code_length_bitdepth_symbols; 570 571 VP8LPutBits(bw, 0, 1); 572 num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens); 573 { 574 uint32_t histogram[CODE_LENGTH_CODES] = { 0 }; 575 uint8_t buf_rle[CODE_LENGTH_CODES] = { 0 }; 576 int i; 577 for (i = 0; i < num_tokens; ++i) { 578 ++histogram[tokens[i].code]; 579 } 580 581 VP8LCreateHuffmanTree(histogram, 7, buf_rle, huff_tree, &huffman_code); 582 } 583 584 StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth); 585 ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code); 586 { 587 int trailing_zero_bits = 0; 588 int trimmed_length = num_tokens; 589 int write_trimmed_length; 590 int length; 591 int i = num_tokens; 592 while (i-- > 0) { 593 const int ix = tokens[i].code; 594 if (ix == 0 || ix == 17 || ix == 18) { 595 --trimmed_length; // discount trailing zeros 596 trailing_zero_bits += code_length_bitdepth[ix]; 597 if (ix == 17) { 598 trailing_zero_bits += 3; 599 } else if (ix == 18) { 600 trailing_zero_bits += 7; 601 } 602 } else { 603 break; 604 } 605 } 606 write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12); 607 length = write_trimmed_length ? trimmed_length : num_tokens; 608 VP8LPutBits(bw, write_trimmed_length, 1); 609 if (write_trimmed_length) { 610 const int nbits = VP8LBitsLog2Ceiling(trimmed_length - 1); 611 const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2; 612 VP8LPutBits(bw, nbitpairs - 1, 3); 613 assert(trimmed_length >= 2); 614 VP8LPutBits(bw, trimmed_length - 2, nbitpairs * 2); 615 } 616 StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code); 617 } 618 } 619 620 // 'huff_tree' and 'tokens' are pre-alloacted buffers. 621 static void StoreHuffmanCode(VP8LBitWriter* const bw, 622 HuffmanTree* const huff_tree, 623 HuffmanTreeToken* const tokens, 624 const HuffmanTreeCode* const huffman_code) { 625 int i; 626 int count = 0; 627 int symbols[2] = { 0, 0 }; 628 const int kMaxBits = 8; 629 const int kMaxSymbol = 1 << kMaxBits; 630 631 // Check whether it's a small tree. 632 for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) { 633 if (huffman_code->code_lengths[i] != 0) { 634 if (count < 2) symbols[count] = i; 635 ++count; 636 } 637 } 638 639 if (count == 0) { // emit minimal tree for empty cases 640 // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0 641 VP8LPutBits(bw, 0x01, 4); 642 } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) { 643 VP8LPutBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. 644 VP8LPutBits(bw, count - 1, 1); 645 if (symbols[0] <= 1) { 646 VP8LPutBits(bw, 0, 1); // Code bit for small (1 bit) symbol value. 647 VP8LPutBits(bw, symbols[0], 1); 648 } else { 649 VP8LPutBits(bw, 1, 1); 650 VP8LPutBits(bw, symbols[0], 8); 651 } 652 if (count == 2) { 653 VP8LPutBits(bw, symbols[1], 8); 654 } 655 } else { 656 StoreFullHuffmanCode(bw, huff_tree, tokens, huffman_code); 657 } 658 } 659 660 static WEBP_INLINE void WriteHuffmanCode(VP8LBitWriter* const bw, 661 const HuffmanTreeCode* const code, 662 int code_index) { 663 const int depth = code->code_lengths[code_index]; 664 const int symbol = code->codes[code_index]; 665 VP8LPutBits(bw, symbol, depth); 666 } 667 668 static WEBP_INLINE void WriteHuffmanCodeWithExtraBits( 669 VP8LBitWriter* const bw, 670 const HuffmanTreeCode* const code, 671 int code_index, 672 int bits, 673 int n_bits) { 674 const int depth = code->code_lengths[code_index]; 675 const int symbol = code->codes[code_index]; 676 VP8LPutBits(bw, (bits << depth) | symbol, depth + n_bits); 677 } 678 679 static WebPEncodingError StoreImageToBitMask( 680 VP8LBitWriter* const bw, int width, int histo_bits, 681 VP8LBackwardRefs* const refs, 682 const uint16_t* histogram_symbols, 683 const HuffmanTreeCode* const huffman_codes) { 684 const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; 685 const int tile_mask = (histo_bits == 0) ? 0 : -(1 << histo_bits); 686 // x and y trace the position in the image. 687 int x = 0; 688 int y = 0; 689 int tile_x = x & tile_mask; 690 int tile_y = y & tile_mask; 691 int histogram_ix = histogram_symbols[0]; 692 const HuffmanTreeCode* codes = huffman_codes + 5 * histogram_ix; 693 VP8LRefsCursor c = VP8LRefsCursorInit(refs); 694 while (VP8LRefsCursorOk(&c)) { 695 const PixOrCopy* const v = c.cur_pos; 696 if ((tile_x != (x & tile_mask)) || (tile_y != (y & tile_mask))) { 697 tile_x = x & tile_mask; 698 tile_y = y & tile_mask; 699 histogram_ix = histogram_symbols[(y >> histo_bits) * histo_xsize + 700 (x >> histo_bits)]; 701 codes = huffman_codes + 5 * histogram_ix; 702 } 703 if (PixOrCopyIsLiteral(v)) { 704 static const int order[] = { 1, 2, 0, 3 }; 705 int k; 706 for (k = 0; k < 4; ++k) { 707 const int code = PixOrCopyLiteral(v, order[k]); 708 WriteHuffmanCode(bw, codes + k, code); 709 } 710 } else if (PixOrCopyIsCacheIdx(v)) { 711 const int code = PixOrCopyCacheIdx(v); 712 const int literal_ix = 256 + NUM_LENGTH_CODES + code; 713 WriteHuffmanCode(bw, codes, literal_ix); 714 } else { 715 int bits, n_bits; 716 int code; 717 718 const int distance = PixOrCopyDistance(v); 719 VP8LPrefixEncode(v->len, &code, &n_bits, &bits); 720 WriteHuffmanCodeWithExtraBits(bw, codes, 256 + code, bits, n_bits); 721 722 // Don't write the distance with the extra bits code since 723 // the distance can be up to 18 bits of extra bits, and the prefix 724 // 15 bits, totaling to 33, and our PutBits only supports up to 32 bits. 725 // TODO(jyrki): optimize this further. 726 VP8LPrefixEncode(distance, &code, &n_bits, &bits); 727 WriteHuffmanCode(bw, codes + 4, code); 728 VP8LPutBits(bw, bits, n_bits); 729 } 730 x += PixOrCopyLength(v); 731 while (x >= width) { 732 x -= width; 733 ++y; 734 } 735 VP8LRefsCursorNext(&c); 736 } 737 return bw->error_ ? VP8_ENC_ERROR_OUT_OF_MEMORY : VP8_ENC_OK; 738 } 739 740 // Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31 741 static WebPEncodingError EncodeImageNoHuffman(VP8LBitWriter* const bw, 742 const uint32_t* const argb, 743 VP8LHashChain* const hash_chain, 744 VP8LBackwardRefs refs_array[2], 745 int width, int height, 746 int quality) { 747 int i; 748 int max_tokens = 0; 749 WebPEncodingError err = VP8_ENC_OK; 750 VP8LBackwardRefs* refs; 751 HuffmanTreeToken* tokens = NULL; 752 HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } }; 753 const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol 754 int cache_bits = 0; 755 VP8LHistogramSet* histogram_image = NULL; 756 HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc( 757 3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree)); 758 if (huff_tree == NULL) { 759 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 760 goto Error; 761 } 762 763 // Calculate backward references from ARGB image. 764 refs = VP8LGetBackwardReferences(width, height, argb, quality, 0, &cache_bits, 765 hash_chain, refs_array); 766 if (refs == NULL) { 767 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 768 goto Error; 769 } 770 histogram_image = VP8LAllocateHistogramSet(1, cache_bits); 771 if (histogram_image == NULL) { 772 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 773 goto Error; 774 } 775 776 // Build histogram image and symbols from backward references. 777 VP8LHistogramStoreRefs(refs, histogram_image->histograms[0]); 778 779 // Create Huffman bit lengths and codes for each histogram image. 780 assert(histogram_image->size == 1); 781 if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 782 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 783 goto Error; 784 } 785 786 // No color cache, no Huffman image. 787 VP8LPutBits(bw, 0, 1); 788 789 // Find maximum number of symbols for the huffman tree-set. 790 for (i = 0; i < 5; ++i) { 791 HuffmanTreeCode* const codes = &huffman_codes[i]; 792 if (max_tokens < codes->num_symbols) { 793 max_tokens = codes->num_symbols; 794 } 795 } 796 797 tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens)); 798 if (tokens == NULL) { 799 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 800 goto Error; 801 } 802 803 // Store Huffman codes. 804 for (i = 0; i < 5; ++i) { 805 HuffmanTreeCode* const codes = &huffman_codes[i]; 806 StoreHuffmanCode(bw, huff_tree, tokens, codes); 807 ClearHuffmanTreeIfOnlyOneSymbol(codes); 808 } 809 810 // Store actual literals. 811 err = StoreImageToBitMask(bw, width, 0, refs, histogram_symbols, 812 huffman_codes); 813 814 Error: 815 WebPSafeFree(tokens); 816 WebPSafeFree(huff_tree); 817 VP8LFreeHistogramSet(histogram_image); 818 WebPSafeFree(huffman_codes[0].codes); 819 return err; 820 } 821 822 static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, 823 const uint32_t* const argb, 824 VP8LHashChain* const hash_chain, 825 VP8LBackwardRefs refs_array[2], 826 int width, int height, int quality, 827 int low_effort, int* cache_bits, 828 int histogram_bits, 829 size_t init_byte_position, 830 int* const hdr_size, 831 int* const data_size) { 832 WebPEncodingError err = VP8_ENC_OK; 833 const uint32_t histogram_image_xysize = 834 VP8LSubSampleSize(width, histogram_bits) * 835 VP8LSubSampleSize(height, histogram_bits); 836 VP8LHistogramSet* histogram_image = NULL; 837 VP8LHistogramSet* tmp_histos = NULL; 838 int histogram_image_size = 0; 839 size_t bit_array_size = 0; 840 HuffmanTree* huff_tree = NULL; 841 HuffmanTreeToken* tokens = NULL; 842 HuffmanTreeCode* huffman_codes = NULL; 843 VP8LBackwardRefs refs; 844 VP8LBackwardRefs* best_refs; 845 uint16_t* const histogram_symbols = 846 (uint16_t*)WebPSafeMalloc(histogram_image_xysize, 847 sizeof(*histogram_symbols)); 848 assert(histogram_bits >= MIN_HUFFMAN_BITS); 849 assert(histogram_bits <= MAX_HUFFMAN_BITS); 850 assert(hdr_size != NULL); 851 assert(data_size != NULL); 852 853 VP8LBackwardRefsInit(&refs, refs_array[0].block_size_); 854 if (histogram_symbols == NULL) { 855 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 856 goto Error; 857 } 858 859 *cache_bits = MAX_COLOR_CACHE_BITS; 860 // 'best_refs' is the reference to the best backward refs and points to one 861 // of refs_array[0] or refs_array[1]. 862 // Calculate backward references from ARGB image. 863 best_refs = VP8LGetBackwardReferences(width, height, argb, quality, 864 low_effort, cache_bits, hash_chain, 865 refs_array); 866 if (best_refs == NULL || !VP8LBackwardRefsCopy(best_refs, &refs)) { 867 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 868 goto Error; 869 } 870 histogram_image = 871 VP8LAllocateHistogramSet(histogram_image_xysize, *cache_bits); 872 tmp_histos = VP8LAllocateHistogramSet(2, *cache_bits); 873 if (histogram_image == NULL || tmp_histos == NULL) { 874 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 875 goto Error; 876 } 877 878 // Build histogram image and symbols from backward references. 879 if (!VP8LGetHistoImageSymbols(width, height, &refs, quality, low_effort, 880 histogram_bits, *cache_bits, histogram_image, 881 tmp_histos, histogram_symbols)) { 882 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 883 goto Error; 884 } 885 // Create Huffman bit lengths and codes for each histogram image. 886 histogram_image_size = histogram_image->size; 887 bit_array_size = 5 * histogram_image_size; 888 huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size, 889 sizeof(*huffman_codes)); 890 // Note: some histogram_image entries may point to tmp_histos[], so the latter 891 // need to outlive the following call to GetHuffBitLengthsAndCodes(). 892 if (huffman_codes == NULL || 893 !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 894 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 895 goto Error; 896 } 897 // Free combined histograms. 898 VP8LFreeHistogramSet(histogram_image); 899 histogram_image = NULL; 900 901 // Free scratch histograms. 902 VP8LFreeHistogramSet(tmp_histos); 903 tmp_histos = NULL; 904 905 // Color Cache parameters. 906 if (*cache_bits > 0) { 907 VP8LPutBits(bw, 1, 1); 908 VP8LPutBits(bw, *cache_bits, 4); 909 } else { 910 VP8LPutBits(bw, 0, 1); 911 } 912 913 // Huffman image + meta huffman. 914 { 915 const int write_histogram_image = (histogram_image_size > 1); 916 VP8LPutBits(bw, write_histogram_image, 1); 917 if (write_histogram_image) { 918 uint32_t* const histogram_argb = 919 (uint32_t*)WebPSafeMalloc(histogram_image_xysize, 920 sizeof(*histogram_argb)); 921 int max_index = 0; 922 uint32_t i; 923 if (histogram_argb == NULL) { 924 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 925 goto Error; 926 } 927 for (i = 0; i < histogram_image_xysize; ++i) { 928 const int symbol_index = histogram_symbols[i] & 0xffff; 929 histogram_argb[i] = (symbol_index << 8); 930 if (symbol_index >= max_index) { 931 max_index = symbol_index + 1; 932 } 933 } 934 histogram_image_size = max_index; 935 936 VP8LPutBits(bw, histogram_bits - 2, 3); 937 err = EncodeImageNoHuffman(bw, histogram_argb, hash_chain, refs_array, 938 VP8LSubSampleSize(width, histogram_bits), 939 VP8LSubSampleSize(height, histogram_bits), 940 quality); 941 WebPSafeFree(histogram_argb); 942 if (err != VP8_ENC_OK) goto Error; 943 } 944 } 945 946 // Store Huffman codes. 947 { 948 int i; 949 int max_tokens = 0; 950 huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * CODE_LENGTH_CODES, 951 sizeof(*huff_tree)); 952 if (huff_tree == NULL) { 953 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 954 goto Error; 955 } 956 // Find maximum number of symbols for the huffman tree-set. 957 for (i = 0; i < 5 * histogram_image_size; ++i) { 958 HuffmanTreeCode* const codes = &huffman_codes[i]; 959 if (max_tokens < codes->num_symbols) { 960 max_tokens = codes->num_symbols; 961 } 962 } 963 tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, 964 sizeof(*tokens)); 965 if (tokens == NULL) { 966 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 967 goto Error; 968 } 969 for (i = 0; i < 5 * histogram_image_size; ++i) { 970 HuffmanTreeCode* const codes = &huffman_codes[i]; 971 StoreHuffmanCode(bw, huff_tree, tokens, codes); 972 ClearHuffmanTreeIfOnlyOneSymbol(codes); 973 } 974 } 975 976 *hdr_size = (int)(VP8LBitWriterNumBytes(bw) - init_byte_position); 977 // Store actual literals. 978 err = StoreImageToBitMask(bw, width, histogram_bits, &refs, 979 histogram_symbols, huffman_codes); 980 *data_size = 981 (int)(VP8LBitWriterNumBytes(bw) - init_byte_position - *hdr_size); 982 983 Error: 984 WebPSafeFree(tokens); 985 WebPSafeFree(huff_tree); 986 VP8LFreeHistogramSet(histogram_image); 987 VP8LFreeHistogramSet(tmp_histos); 988 VP8LBackwardRefsClear(&refs); 989 if (huffman_codes != NULL) { 990 WebPSafeFree(huffman_codes->codes); 991 WebPSafeFree(huffman_codes); 992 } 993 WebPSafeFree(histogram_symbols); 994 return err; 995 } 996 997 // ----------------------------------------------------------------------------- 998 // Transforms 999 1000 static void ApplySubtractGreen(VP8LEncoder* const enc, int width, int height, 1001 VP8LBitWriter* const bw) { 1002 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1003 VP8LPutBits(bw, SUBTRACT_GREEN, 2); 1004 VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); 1005 } 1006 1007 static WebPEncodingError ApplyPredictFilter(const VP8LEncoder* const enc, 1008 int width, int height, 1009 int quality, int low_effort, 1010 VP8LBitWriter* const bw) { 1011 const int pred_bits = enc->transform_bits_; 1012 const int transform_width = VP8LSubSampleSize(width, pred_bits); 1013 const int transform_height = VP8LSubSampleSize(height, pred_bits); 1014 1015 VP8LResidualImage(width, height, pred_bits, low_effort, enc->argb_, 1016 enc->argb_scratch_, enc->transform_data_, 1017 enc->config_->exact); 1018 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1019 VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2); 1020 assert(pred_bits >= 2); 1021 VP8LPutBits(bw, pred_bits - 2, 3); 1022 return EncodeImageNoHuffman(bw, enc->transform_data_, 1023 (VP8LHashChain*)&enc->hash_chain_, 1024 (VP8LBackwardRefs*)enc->refs_, // cast const away 1025 transform_width, transform_height, 1026 quality); 1027 } 1028 1029 static WebPEncodingError ApplyCrossColorFilter(const VP8LEncoder* const enc, 1030 int width, int height, 1031 int quality, 1032 VP8LBitWriter* const bw) { 1033 const int ccolor_transform_bits = enc->transform_bits_; 1034 const int transform_width = VP8LSubSampleSize(width, ccolor_transform_bits); 1035 const int transform_height = VP8LSubSampleSize(height, ccolor_transform_bits); 1036 1037 VP8LColorSpaceTransform(width, height, ccolor_transform_bits, quality, 1038 enc->argb_, enc->transform_data_); 1039 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1040 VP8LPutBits(bw, CROSS_COLOR_TRANSFORM, 2); 1041 assert(ccolor_transform_bits >= 2); 1042 VP8LPutBits(bw, ccolor_transform_bits - 2, 3); 1043 return EncodeImageNoHuffman(bw, enc->transform_data_, 1044 (VP8LHashChain*)&enc->hash_chain_, 1045 (VP8LBackwardRefs*)enc->refs_, // cast const away 1046 transform_width, transform_height, 1047 quality); 1048 } 1049 1050 // ----------------------------------------------------------------------------- 1051 1052 static WebPEncodingError WriteRiffHeader(const WebPPicture* const pic, 1053 size_t riff_size, size_t vp8l_size) { 1054 uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = { 1055 'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P', 1056 'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE, 1057 }; 1058 PutLE32(riff + TAG_SIZE, (uint32_t)riff_size); 1059 PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size); 1060 if (!pic->writer(riff, sizeof(riff), pic)) { 1061 return VP8_ENC_ERROR_BAD_WRITE; 1062 } 1063 return VP8_ENC_OK; 1064 } 1065 1066 static int WriteImageSize(const WebPPicture* const pic, 1067 VP8LBitWriter* const bw) { 1068 const int width = pic->width - 1; 1069 const int height = pic->height - 1; 1070 assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION); 1071 1072 VP8LPutBits(bw, width, VP8L_IMAGE_SIZE_BITS); 1073 VP8LPutBits(bw, height, VP8L_IMAGE_SIZE_BITS); 1074 return !bw->error_; 1075 } 1076 1077 static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) { 1078 VP8LPutBits(bw, has_alpha, 1); 1079 VP8LPutBits(bw, VP8L_VERSION, VP8L_VERSION_BITS); 1080 return !bw->error_; 1081 } 1082 1083 static WebPEncodingError WriteImage(const WebPPicture* const pic, 1084 VP8LBitWriter* const bw, 1085 size_t* const coded_size) { 1086 WebPEncodingError err = VP8_ENC_OK; 1087 const uint8_t* const webpll_data = VP8LBitWriterFinish(bw); 1088 const size_t webpll_size = VP8LBitWriterNumBytes(bw); 1089 const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size; 1090 const size_t pad = vp8l_size & 1; 1091 const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad; 1092 1093 err = WriteRiffHeader(pic, riff_size, vp8l_size); 1094 if (err != VP8_ENC_OK) goto Error; 1095 1096 if (!pic->writer(webpll_data, webpll_size, pic)) { 1097 err = VP8_ENC_ERROR_BAD_WRITE; 1098 goto Error; 1099 } 1100 1101 if (pad) { 1102 const uint8_t pad_byte[1] = { 0 }; 1103 if (!pic->writer(pad_byte, 1, pic)) { 1104 err = VP8_ENC_ERROR_BAD_WRITE; 1105 goto Error; 1106 } 1107 } 1108 *coded_size = CHUNK_HEADER_SIZE + riff_size; 1109 return VP8_ENC_OK; 1110 1111 Error: 1112 return err; 1113 } 1114 1115 // ----------------------------------------------------------------------------- 1116 1117 // Allocates the memory for argb (W x H) buffer, 2 rows of context for 1118 // prediction and transform data. 1119 // Flags influencing the memory allocated: 1120 // enc->transform_bits_ 1121 // enc->use_predict_, enc->use_cross_color_ 1122 static WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc, 1123 int width, int height) { 1124 WebPEncodingError err = VP8_ENC_OK; 1125 if (enc->argb_ == NULL) { 1126 const int tile_size = 1 << enc->transform_bits_; 1127 const uint64_t image_size = width * height; 1128 // Ensure enough size for tiles, as well as for two scanlines and two 1129 // extra pixels for CopyImageWithPrediction. 1130 const uint64_t argb_scratch_size = 1131 enc->use_predict_ ? tile_size * width + width + 2 : 0; 1132 const int transform_data_size = 1133 (enc->use_predict_ || enc->use_cross_color_) 1134 ? VP8LSubSampleSize(width, enc->transform_bits_) * 1135 VP8LSubSampleSize(height, enc->transform_bits_) 1136 : 0; 1137 const uint64_t total_size = 1138 image_size + WEBP_ALIGN_CST + 1139 argb_scratch_size + WEBP_ALIGN_CST + 1140 (uint64_t)transform_data_size; 1141 uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem)); 1142 if (mem == NULL) { 1143 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1144 goto Error; 1145 } 1146 enc->argb_ = mem; 1147 mem = (uint32_t*)WEBP_ALIGN(mem + image_size); 1148 enc->argb_scratch_ = mem; 1149 mem = (uint32_t*)WEBP_ALIGN(mem + argb_scratch_size); 1150 enc->transform_data_ = mem; 1151 enc->current_width_ = width; 1152 } 1153 Error: 1154 return err; 1155 } 1156 1157 static void ClearTransformBuffer(VP8LEncoder* const enc) { 1158 WebPSafeFree(enc->argb_); 1159 enc->argb_ = NULL; 1160 } 1161 1162 static WebPEncodingError MakeInputImageCopy(VP8LEncoder* const enc) { 1163 WebPEncodingError err = VP8_ENC_OK; 1164 const WebPPicture* const picture = enc->pic_; 1165 const int width = picture->width; 1166 const int height = picture->height; 1167 int y; 1168 err = AllocateTransformBuffer(enc, width, height); 1169 if (err != VP8_ENC_OK) return err; 1170 for (y = 0; y < height; ++y) { 1171 memcpy(enc->argb_ + y * width, 1172 picture->argb + y * picture->argb_stride, 1173 width * sizeof(*enc->argb_)); 1174 } 1175 assert(enc->current_width_ == width); 1176 return VP8_ENC_OK; 1177 } 1178 1179 // ----------------------------------------------------------------------------- 1180 1181 static void MapToPalette(const uint32_t palette[], int num_colors, 1182 uint32_t* const last_pix, int* const last_idx, 1183 const uint32_t* src, uint8_t* dst, int width) { 1184 int x; 1185 int prev_idx = *last_idx; 1186 uint32_t prev_pix = *last_pix; 1187 for (x = 0; x < width; ++x) { 1188 const uint32_t pix = src[x]; 1189 if (pix != prev_pix) { 1190 int i; 1191 for (i = 0; i < num_colors; ++i) { 1192 if (pix == palette[i]) { 1193 prev_idx = i; 1194 prev_pix = pix; 1195 break; 1196 } 1197 } 1198 } 1199 dst[x] = prev_idx; 1200 } 1201 *last_idx = prev_idx; 1202 *last_pix = prev_pix; 1203 } 1204 1205 // Remap argb values in src[] to packed palettes entries in dst[] 1206 // using 'row' as a temporary buffer of size 'width'. 1207 // We assume that all src[] values have a corresponding entry in the palette. 1208 // Note: src[] can be the same as dst[] 1209 static WebPEncodingError ApplyPalette(const uint32_t* src, uint32_t src_stride, 1210 uint32_t* dst, uint32_t dst_stride, 1211 const uint32_t* palette, int palette_size, 1212 int width, int height, int xbits) { 1213 // TODO(skal): this tmp buffer is not needed if VP8LBundleColorMap() can be 1214 // made to work in-place. 1215 uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row)); 1216 int i, x, y; 1217 int use_LUT = 1; 1218 1219 if (tmp_row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; 1220 for (i = 0; i < palette_size; ++i) { 1221 if ((palette[i] & 0xffff00ffu) != 0) { 1222 use_LUT = 0; 1223 break; 1224 } 1225 } 1226 1227 if (use_LUT) { 1228 uint8_t inv_palette[MAX_PALETTE_SIZE] = { 0 }; 1229 for (i = 0; i < palette_size; ++i) { 1230 const int color = (palette[i] >> 8) & 0xff; 1231 inv_palette[color] = i; 1232 } 1233 for (y = 0; y < height; ++y) { 1234 for (x = 0; x < width; ++x) { 1235 const int color = (src[x] >> 8) & 0xff; 1236 tmp_row[x] = inv_palette[color]; 1237 } 1238 VP8LBundleColorMap(tmp_row, width, xbits, dst); 1239 src += src_stride; 1240 dst += dst_stride; 1241 } 1242 } else { 1243 // Use 1 pixel cache for ARGB pixels. 1244 uint32_t last_pix = palette[0]; 1245 int last_idx = 0; 1246 for (y = 0; y < height; ++y) { 1247 MapToPalette(palette, palette_size, &last_pix, &last_idx, 1248 src, tmp_row, width); 1249 VP8LBundleColorMap(tmp_row, width, xbits, dst); 1250 src += src_stride; 1251 dst += dst_stride; 1252 } 1253 } 1254 WebPSafeFree(tmp_row); 1255 return VP8_ENC_OK; 1256 } 1257 1258 // Note: Expects "enc->palette_" to be set properly. 1259 static WebPEncodingError MapImageFromPalette(VP8LEncoder* const enc, 1260 int in_place) { 1261 WebPEncodingError err = VP8_ENC_OK; 1262 const WebPPicture* const pic = enc->pic_; 1263 const int width = pic->width; 1264 const int height = pic->height; 1265 const uint32_t* const palette = enc->palette_; 1266 const uint32_t* src = in_place ? enc->argb_ : pic->argb; 1267 const int src_stride = in_place ? enc->current_width_ : pic->argb_stride; 1268 const int palette_size = enc->palette_size_; 1269 int xbits; 1270 1271 // Replace each input pixel by corresponding palette index. 1272 // This is done line by line. 1273 if (palette_size <= 4) { 1274 xbits = (palette_size <= 2) ? 3 : 2; 1275 } else { 1276 xbits = (palette_size <= 16) ? 1 : 0; 1277 } 1278 1279 err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height); 1280 if (err != VP8_ENC_OK) return err; 1281 1282 err = ApplyPalette(src, src_stride, 1283 enc->argb_, enc->current_width_, 1284 palette, palette_size, width, height, xbits); 1285 return err; 1286 } 1287 1288 // Save palette_[] to bitstream. 1289 static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, 1290 VP8LEncoder* const enc) { 1291 int i; 1292 uint32_t tmp_palette[MAX_PALETTE_SIZE]; 1293 const int palette_size = enc->palette_size_; 1294 const uint32_t* const palette = enc->palette_; 1295 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1296 VP8LPutBits(bw, COLOR_INDEXING_TRANSFORM, 2); 1297 assert(palette_size >= 1 && palette_size <= MAX_PALETTE_SIZE); 1298 VP8LPutBits(bw, palette_size - 1, 8); 1299 for (i = palette_size - 1; i >= 1; --i) { 1300 tmp_palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); 1301 } 1302 tmp_palette[0] = palette[0]; 1303 return EncodeImageNoHuffman(bw, tmp_palette, &enc->hash_chain_, enc->refs_, 1304 palette_size, 1, 20 /* quality */); 1305 } 1306 1307 #ifdef WEBP_EXPERIMENTAL_FEATURES 1308 1309 static WebPEncodingError EncodeDeltaPalettePredictorImage( 1310 VP8LBitWriter* const bw, VP8LEncoder* const enc, int quality) { 1311 const WebPPicture* const pic = enc->pic_; 1312 const int width = pic->width; 1313 const int height = pic->height; 1314 1315 const int pred_bits = 5; 1316 const int transform_width = VP8LSubSampleSize(width, pred_bits); 1317 const int transform_height = VP8LSubSampleSize(height, pred_bits); 1318 const int pred = 7; // default is Predictor7 (Top/Left Average) 1319 const int tiles_per_row = VP8LSubSampleSize(width, pred_bits); 1320 const int tiles_per_col = VP8LSubSampleSize(height, pred_bits); 1321 uint32_t* predictors; 1322 int tile_x, tile_y; 1323 WebPEncodingError err = VP8_ENC_OK; 1324 1325 predictors = (uint32_t*)WebPSafeMalloc(tiles_per_col * tiles_per_row, 1326 sizeof(*predictors)); 1327 if (predictors == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; 1328 1329 for (tile_y = 0; tile_y < tiles_per_col; ++tile_y) { 1330 for (tile_x = 0; tile_x < tiles_per_row; ++tile_x) { 1331 predictors[tile_y * tiles_per_row + tile_x] = 0xff000000u | (pred << 8); 1332 } 1333 } 1334 1335 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1336 VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2); 1337 VP8LPutBits(bw, pred_bits - 2, 3); 1338 err = EncodeImageNoHuffman(bw, predictors, &enc->hash_chain_, 1339 (VP8LBackwardRefs*)enc->refs_, // cast const away 1340 transform_width, transform_height, 1341 quality); 1342 WebPSafeFree(predictors); 1343 return err; 1344 } 1345 1346 #endif // WEBP_EXPERIMENTAL_FEATURES 1347 1348 // ----------------------------------------------------------------------------- 1349 // VP8LEncoder 1350 1351 static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config, 1352 const WebPPicture* const picture) { 1353 VP8LEncoder* const enc = (VP8LEncoder*)WebPSafeCalloc(1ULL, sizeof(*enc)); 1354 if (enc == NULL) { 1355 WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY); 1356 return NULL; 1357 } 1358 enc->config_ = config; 1359 enc->pic_ = picture; 1360 1361 VP8LEncDspInit(); 1362 1363 return enc; 1364 } 1365 1366 static void VP8LEncoderDelete(VP8LEncoder* enc) { 1367 if (enc != NULL) { 1368 VP8LHashChainClear(&enc->hash_chain_); 1369 VP8LBackwardRefsClear(&enc->refs_[0]); 1370 VP8LBackwardRefsClear(&enc->refs_[1]); 1371 ClearTransformBuffer(enc); 1372 WebPSafeFree(enc); 1373 } 1374 } 1375 1376 // ----------------------------------------------------------------------------- 1377 // Main call 1378 1379 WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, 1380 const WebPPicture* const picture, 1381 VP8LBitWriter* const bw) { 1382 WebPEncodingError err = VP8_ENC_OK; 1383 const int quality = (int)config->quality; 1384 const int low_effort = (config->method == 0); 1385 const int width = picture->width; 1386 const int height = picture->height; 1387 VP8LEncoder* const enc = VP8LEncoderNew(config, picture); 1388 const size_t byte_position = VP8LBitWriterNumBytes(bw); 1389 int use_near_lossless = 0; 1390 int hdr_size = 0; 1391 int data_size = 0; 1392 int use_delta_palettization = 0; 1393 1394 if (enc == NULL) { 1395 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1396 goto Error; 1397 } 1398 1399 // --------------------------------------------------------------------------- 1400 // Analyze image (entropy, num_palettes etc) 1401 1402 if (!AnalyzeAndInit(enc)) { 1403 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1404 goto Error; 1405 } 1406 1407 // Apply near-lossless preprocessing. 1408 use_near_lossless = !enc->use_palette_ && (config->near_lossless < 100); 1409 if (use_near_lossless) { 1410 if (!VP8ApplyNearLossless(width, height, picture->argb, 1411 config->near_lossless)) { 1412 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1413 goto Error; 1414 } 1415 } 1416 1417 #ifdef WEBP_EXPERIMENTAL_FEATURES 1418 if (config->delta_palettization) { 1419 enc->use_predict_ = 1; 1420 enc->use_cross_color_ = 0; 1421 enc->use_subtract_green_ = 0; 1422 enc->use_palette_ = 1; 1423 err = MakeInputImageCopy(enc); 1424 if (err != VP8_ENC_OK) goto Error; 1425 err = WebPSearchOptimalDeltaPalette(enc); 1426 if (err != VP8_ENC_OK) goto Error; 1427 if (enc->use_palette_) { 1428 err = AllocateTransformBuffer(enc, width, height); 1429 if (err != VP8_ENC_OK) goto Error; 1430 err = EncodeDeltaPalettePredictorImage(bw, enc, quality); 1431 if (err != VP8_ENC_OK) goto Error; 1432 use_delta_palettization = 1; 1433 } 1434 } 1435 #endif // WEBP_EXPERIMENTAL_FEATURES 1436 1437 // Encode palette 1438 if (enc->use_palette_) { 1439 err = EncodePalette(bw, enc); 1440 if (err != VP8_ENC_OK) goto Error; 1441 err = MapImageFromPalette(enc, use_delta_palettization); 1442 if (err != VP8_ENC_OK) goto Error; 1443 } 1444 if (!use_delta_palettization) { 1445 // In case image is not packed. 1446 if (enc->argb_ == NULL) { 1447 err = MakeInputImageCopy(enc); 1448 if (err != VP8_ENC_OK) goto Error; 1449 } 1450 1451 // ------------------------------------------------------------------------- 1452 // Apply transforms and write transform data. 1453 1454 if (enc->use_subtract_green_) { 1455 ApplySubtractGreen(enc, enc->current_width_, height, bw); 1456 } 1457 1458 if (enc->use_predict_) { 1459 err = ApplyPredictFilter(enc, enc->current_width_, height, quality, 1460 low_effort, bw); 1461 if (err != VP8_ENC_OK) goto Error; 1462 } 1463 1464 if (enc->use_cross_color_) { 1465 err = ApplyCrossColorFilter(enc, enc->current_width_, 1466 height, quality, bw); 1467 if (err != VP8_ENC_OK) goto Error; 1468 } 1469 } 1470 1471 VP8LPutBits(bw, !TRANSFORM_PRESENT, 1); // No more transforms. 1472 1473 // --------------------------------------------------------------------------- 1474 // Encode and write the transformed image. 1475 err = EncodeImageInternal(bw, enc->argb_, &enc->hash_chain_, enc->refs_, 1476 enc->current_width_, height, quality, low_effort, 1477 &enc->cache_bits_, enc->histo_bits_, byte_position, 1478 &hdr_size, &data_size); 1479 if (err != VP8_ENC_OK) goto Error; 1480 1481 if (picture->stats != NULL) { 1482 WebPAuxStats* const stats = picture->stats; 1483 stats->lossless_features = 0; 1484 if (enc->use_predict_) stats->lossless_features |= 1; 1485 if (enc->use_cross_color_) stats->lossless_features |= 2; 1486 if (enc->use_subtract_green_) stats->lossless_features |= 4; 1487 if (enc->use_palette_) stats->lossless_features |= 8; 1488 stats->histogram_bits = enc->histo_bits_; 1489 stats->transform_bits = enc->transform_bits_; 1490 stats->cache_bits = enc->cache_bits_; 1491 stats->palette_size = enc->palette_size_; 1492 stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position); 1493 stats->lossless_hdr_size = hdr_size; 1494 stats->lossless_data_size = data_size; 1495 } 1496 1497 Error: 1498 VP8LEncoderDelete(enc); 1499 return err; 1500 } 1501 1502 int VP8LEncodeImage(const WebPConfig* const config, 1503 const WebPPicture* const picture) { 1504 int width, height; 1505 int has_alpha; 1506 size_t coded_size; 1507 int percent = 0; 1508 int initial_size; 1509 WebPEncodingError err = VP8_ENC_OK; 1510 VP8LBitWriter bw; 1511 1512 if (picture == NULL) return 0; 1513 1514 if (config == NULL || picture->argb == NULL) { 1515 err = VP8_ENC_ERROR_NULL_PARAMETER; 1516 WebPEncodingSetError(picture, err); 1517 return 0; 1518 } 1519 1520 width = picture->width; 1521 height = picture->height; 1522 // Initialize BitWriter with size corresponding to 16 bpp to photo images and 1523 // 8 bpp for graphical images. 1524 initial_size = (config->image_hint == WEBP_HINT_GRAPH) ? 1525 width * height : width * height * 2; 1526 if (!VP8LBitWriterInit(&bw, initial_size)) { 1527 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1528 goto Error; 1529 } 1530 1531 if (!WebPReportProgress(picture, 1, &percent)) { 1532 UserAbort: 1533 err = VP8_ENC_ERROR_USER_ABORT; 1534 goto Error; 1535 } 1536 // Reset stats (for pure lossless coding) 1537 if (picture->stats != NULL) { 1538 WebPAuxStats* const stats = picture->stats; 1539 memset(stats, 0, sizeof(*stats)); 1540 stats->PSNR[0] = 99.f; 1541 stats->PSNR[1] = 99.f; 1542 stats->PSNR[2] = 99.f; 1543 stats->PSNR[3] = 99.f; 1544 stats->PSNR[4] = 99.f; 1545 } 1546 1547 // Write image size. 1548 if (!WriteImageSize(picture, &bw)) { 1549 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1550 goto Error; 1551 } 1552 1553 has_alpha = WebPPictureHasTransparency(picture); 1554 // Write the non-trivial Alpha flag and lossless version. 1555 if (!WriteRealAlphaAndVersion(&bw, has_alpha)) { 1556 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1557 goto Error; 1558 } 1559 1560 if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort; 1561 1562 // Encode main image stream. 1563 err = VP8LEncodeStream(config, picture, &bw); 1564 if (err != VP8_ENC_OK) goto Error; 1565 1566 // TODO(skal): have a fine-grained progress report in VP8LEncodeStream(). 1567 if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort; 1568 1569 // Finish the RIFF chunk. 1570 err = WriteImage(picture, &bw, &coded_size); 1571 if (err != VP8_ENC_OK) goto Error; 1572 1573 if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort; 1574 1575 // Save size. 1576 if (picture->stats != NULL) { 1577 picture->stats->coded_size += (int)coded_size; 1578 picture->stats->lossless_size = (int)coded_size; 1579 } 1580 1581 if (picture->extra_info != NULL) { 1582 const int mb_w = (width + 15) >> 4; 1583 const int mb_h = (height + 15) >> 4; 1584 memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info)); 1585 } 1586 1587 Error: 1588 if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1589 VP8LBitWriterWipeOut(&bw); 1590 if (err != VP8_ENC_OK) { 1591 WebPEncodingSetError(picture, err); 1592 return 0; 1593 } 1594 return 1; 1595 } 1596 1597 //------------------------------------------------------------------------------ 1598
