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 "src/enc/backward_references_enc.h" 19 #include "src/enc/histogram_enc.h" 20 #include "src/enc/vp8i_enc.h" 21 #include "src/enc/vp8li_enc.h" 22 #include "src/dsp/lossless.h" 23 #include "src/dsp/lossless_common.h" 24 #include "src/utils/bit_writer_utils.h" 25 #include "src/utils/huffman_encode_utils.h" 26 #include "src/utils/utils.h" 27 #include "src/webp/format_constants.h" 28 29 // Maximum number of histogram images (sub-blocks). 30 #define MAX_HUFF_IMAGE_SIZE 2600 31 32 // Palette reordering for smaller sum of deltas (and for smaller storage). 33 34 static int PaletteCompareColorsForQsort(const void* p1, const void* p2) { 35 const uint32_t a = WebPMemToUint32((uint8_t*)p1); 36 const uint32_t b = WebPMemToUint32((uint8_t*)p2); 37 assert(a != b); 38 return (a < b) ? -1 : 1; 39 } 40 41 static WEBP_INLINE uint32_t PaletteComponentDistance(uint32_t v) { 42 return (v <= 128) ? v : (256 - v); 43 } 44 45 // Computes a value that is related to the entropy created by the 46 // palette entry diff. 47 // 48 // Note that the last & 0xff is a no-operation in the next statement, but 49 // removed by most compilers and is here only for regularity of the code. 50 static WEBP_INLINE uint32_t PaletteColorDistance(uint32_t col1, uint32_t col2) { 51 const uint32_t diff = VP8LSubPixels(col1, col2); 52 const int kMoreWeightForRGBThanForAlpha = 9; 53 uint32_t score; 54 score = PaletteComponentDistance((diff >> 0) & 0xff); 55 score += PaletteComponentDistance((diff >> 8) & 0xff); 56 score += PaletteComponentDistance((diff >> 16) & 0xff); 57 score *= kMoreWeightForRGBThanForAlpha; 58 score += PaletteComponentDistance((diff >> 24) & 0xff); 59 return score; 60 } 61 62 static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) { 63 const uint32_t tmp = *col1; 64 *col1 = *col2; 65 *col2 = tmp; 66 } 67 68 static void GreedyMinimizeDeltas(uint32_t palette[], int num_colors) { 69 // Find greedily always the closest color of the predicted color to minimize 70 // deltas in the palette. This reduces storage needs since the 71 // palette is stored with delta encoding. 72 uint32_t predict = 0x00000000; 73 int i, k; 74 for (i = 0; i < num_colors; ++i) { 75 int best_ix = i; 76 uint32_t best_score = ~0U; 77 for (k = i; k < num_colors; ++k) { 78 const uint32_t cur_score = PaletteColorDistance(palette[k], predict); 79 if (best_score > cur_score) { 80 best_score = cur_score; 81 best_ix = k; 82 } 83 } 84 SwapColor(&palette[best_ix], &palette[i]); 85 predict = palette[i]; 86 } 87 } 88 89 // The palette has been sorted by alpha. This function checks if the other 90 // components of the palette have a monotonic development with regards to 91 // position in the palette. If all have monotonic development, there is 92 // no benefit to re-organize them greedily. A monotonic development 93 // would be spotted in green-only situations (like lossy alpha) or gray-scale 94 // images. 95 static int PaletteHasNonMonotonousDeltas(uint32_t palette[], int num_colors) { 96 uint32_t predict = 0x000000; 97 int i; 98 uint8_t sign_found = 0x00; 99 for (i = 0; i < num_colors; ++i) { 100 const uint32_t diff = VP8LSubPixels(palette[i], predict); 101 const uint8_t rd = (diff >> 16) & 0xff; 102 const uint8_t gd = (diff >> 8) & 0xff; 103 const uint8_t bd = (diff >> 0) & 0xff; 104 if (rd != 0x00) { 105 sign_found |= (rd < 0x80) ? 1 : 2; 106 } 107 if (gd != 0x00) { 108 sign_found |= (gd < 0x80) ? 8 : 16; 109 } 110 if (bd != 0x00) { 111 sign_found |= (bd < 0x80) ? 64 : 128; 112 } 113 predict = palette[i]; 114 } 115 return (sign_found & (sign_found << 1)) != 0; // two consequent signs. 116 } 117 118 // ----------------------------------------------------------------------------- 119 // Palette 120 121 // If number of colors in the image is less than or equal to MAX_PALETTE_SIZE, 122 // creates a palette and returns true, else returns false. 123 static int AnalyzeAndCreatePalette(const WebPPicture* const pic, 124 int low_effort, 125 uint32_t palette[MAX_PALETTE_SIZE], 126 int* const palette_size) { 127 const int num_colors = WebPGetColorPalette(pic, palette); 128 if (num_colors > MAX_PALETTE_SIZE) { 129 *palette_size = 0; 130 return 0; 131 } 132 *palette_size = num_colors; 133 qsort(palette, num_colors, sizeof(*palette), PaletteCompareColorsForQsort); 134 if (!low_effort && PaletteHasNonMonotonousDeltas(palette, num_colors)) { 135 GreedyMinimizeDeltas(palette, num_colors); 136 } 137 return 1; 138 } 139 140 // These five modes are evaluated and their respective entropy is computed. 141 typedef enum { 142 kDirect = 0, 143 kSpatial = 1, 144 kSubGreen = 2, 145 kSpatialSubGreen = 3, 146 kPalette = 4, 147 kNumEntropyIx = 5 148 } EntropyIx; 149 150 typedef enum { 151 kHistoAlpha = 0, 152 kHistoAlphaPred, 153 kHistoGreen, 154 kHistoGreenPred, 155 kHistoRed, 156 kHistoRedPred, 157 kHistoBlue, 158 kHistoBluePred, 159 kHistoRedSubGreen, 160 kHistoRedPredSubGreen, 161 kHistoBlueSubGreen, 162 kHistoBluePredSubGreen, 163 kHistoPalette, 164 kHistoTotal // Must be last. 165 } HistoIx; 166 167 static void AddSingleSubGreen(int p, uint32_t* const r, uint32_t* const b) { 168 const int green = p >> 8; // The upper bits are masked away later. 169 ++r[((p >> 16) - green) & 0xff]; 170 ++b[((p >> 0) - green) & 0xff]; 171 } 172 173 static void AddSingle(uint32_t p, 174 uint32_t* const a, uint32_t* const r, 175 uint32_t* const g, uint32_t* const b) { 176 ++a[(p >> 24) & 0xff]; 177 ++r[(p >> 16) & 0xff]; 178 ++g[(p >> 8) & 0xff]; 179 ++b[(p >> 0) & 0xff]; 180 } 181 182 static WEBP_INLINE uint32_t HashPix(uint32_t pix) { 183 // Note that masking with 0xffffffffu is for preventing an 184 // 'unsigned int overflow' warning. Doesn't impact the compiled code. 185 return ((((uint64_t)pix + (pix >> 19)) * 0x39c5fba7ull) & 0xffffffffu) >> 24; 186 } 187 188 static int AnalyzeEntropy(const uint32_t* argb, 189 int width, int height, int argb_stride, 190 int use_palette, 191 int palette_size, int transform_bits, 192 EntropyIx* const min_entropy_ix, 193 int* const red_and_blue_always_zero) { 194 // Allocate histogram set with cache_bits = 0. 195 uint32_t* histo; 196 197 if (use_palette && palette_size <= 16) { 198 // In the case of small palettes, we pack 2, 4 or 8 pixels together. In 199 // practice, small palettes are better than any other transform. 200 *min_entropy_ix = kPalette; 201 *red_and_blue_always_zero = 1; 202 return 1; 203 } 204 histo = (uint32_t*)WebPSafeCalloc(kHistoTotal, sizeof(*histo) * 256); 205 if (histo != NULL) { 206 int i, x, y; 207 const uint32_t* prev_row = NULL; 208 const uint32_t* curr_row = argb; 209 uint32_t pix_prev = argb[0]; // Skip the first pixel. 210 for (y = 0; y < height; ++y) { 211 for (x = 0; x < width; ++x) { 212 const uint32_t pix = curr_row[x]; 213 const uint32_t pix_diff = VP8LSubPixels(pix, pix_prev); 214 pix_prev = pix; 215 if ((pix_diff == 0) || (prev_row != NULL && pix == prev_row[x])) { 216 continue; 217 } 218 AddSingle(pix, 219 &histo[kHistoAlpha * 256], 220 &histo[kHistoRed * 256], 221 &histo[kHistoGreen * 256], 222 &histo[kHistoBlue * 256]); 223 AddSingle(pix_diff, 224 &histo[kHistoAlphaPred * 256], 225 &histo[kHistoRedPred * 256], 226 &histo[kHistoGreenPred * 256], 227 &histo[kHistoBluePred * 256]); 228 AddSingleSubGreen(pix, 229 &histo[kHistoRedSubGreen * 256], 230 &histo[kHistoBlueSubGreen * 256]); 231 AddSingleSubGreen(pix_diff, 232 &histo[kHistoRedPredSubGreen * 256], 233 &histo[kHistoBluePredSubGreen * 256]); 234 { 235 // Approximate the palette by the entropy of the multiplicative hash. 236 const uint32_t hash = HashPix(pix); 237 ++histo[kHistoPalette * 256 + hash]; 238 } 239 } 240 prev_row = curr_row; 241 curr_row += argb_stride; 242 } 243 { 244 double entropy_comp[kHistoTotal]; 245 double entropy[kNumEntropyIx]; 246 int k; 247 int last_mode_to_analyze = use_palette ? kPalette : kSpatialSubGreen; 248 int j; 249 // Let's add one zero to the predicted histograms. The zeros are removed 250 // too efficiently by the pix_diff == 0 comparison, at least one of the 251 // zeros is likely to exist. 252 ++histo[kHistoRedPredSubGreen * 256]; 253 ++histo[kHistoBluePredSubGreen * 256]; 254 ++histo[kHistoRedPred * 256]; 255 ++histo[kHistoGreenPred * 256]; 256 ++histo[kHistoBluePred * 256]; 257 ++histo[kHistoAlphaPred * 256]; 258 259 for (j = 0; j < kHistoTotal; ++j) { 260 entropy_comp[j] = VP8LBitsEntropy(&histo[j * 256], 256); 261 } 262 entropy[kDirect] = entropy_comp[kHistoAlpha] + 263 entropy_comp[kHistoRed] + 264 entropy_comp[kHistoGreen] + 265 entropy_comp[kHistoBlue]; 266 entropy[kSpatial] = entropy_comp[kHistoAlphaPred] + 267 entropy_comp[kHistoRedPred] + 268 entropy_comp[kHistoGreenPred] + 269 entropy_comp[kHistoBluePred]; 270 entropy[kSubGreen] = entropy_comp[kHistoAlpha] + 271 entropy_comp[kHistoRedSubGreen] + 272 entropy_comp[kHistoGreen] + 273 entropy_comp[kHistoBlueSubGreen]; 274 entropy[kSpatialSubGreen] = entropy_comp[kHistoAlphaPred] + 275 entropy_comp[kHistoRedPredSubGreen] + 276 entropy_comp[kHistoGreenPred] + 277 entropy_comp[kHistoBluePredSubGreen]; 278 entropy[kPalette] = entropy_comp[kHistoPalette]; 279 280 // When including transforms, there is an overhead in bits from 281 // storing them. This overhead is small but matters for small images. 282 // For spatial, there are 14 transformations. 283 entropy[kSpatial] += VP8LSubSampleSize(width, transform_bits) * 284 VP8LSubSampleSize(height, transform_bits) * 285 VP8LFastLog2(14); 286 // For color transforms: 24 as only 3 channels are considered in a 287 // ColorTransformElement. 288 entropy[kSpatialSubGreen] += VP8LSubSampleSize(width, transform_bits) * 289 VP8LSubSampleSize(height, transform_bits) * 290 VP8LFastLog2(24); 291 // For palettes, add the cost of storing the palette. 292 // We empirically estimate the cost of a compressed entry as 8 bits. 293 // The palette is differential-coded when compressed hence a much 294 // lower cost than sizeof(uint32_t)*8. 295 entropy[kPalette] += palette_size * 8; 296 297 *min_entropy_ix = kDirect; 298 for (k = kDirect + 1; k <= last_mode_to_analyze; ++k) { 299 if (entropy[*min_entropy_ix] > entropy[k]) { 300 *min_entropy_ix = (EntropyIx)k; 301 } 302 } 303 assert((int)*min_entropy_ix <= last_mode_to_analyze); 304 *red_and_blue_always_zero = 1; 305 // Let's check if the histogram of the chosen entropy mode has 306 // non-zero red and blue values. If all are zero, we can later skip 307 // the cross color optimization. 308 { 309 static const uint8_t kHistoPairs[5][2] = { 310 { kHistoRed, kHistoBlue }, 311 { kHistoRedPred, kHistoBluePred }, 312 { kHistoRedSubGreen, kHistoBlueSubGreen }, 313 { kHistoRedPredSubGreen, kHistoBluePredSubGreen }, 314 { kHistoRed, kHistoBlue } 315 }; 316 const uint32_t* const red_histo = 317 &histo[256 * kHistoPairs[*min_entropy_ix][0]]; 318 const uint32_t* const blue_histo = 319 &histo[256 * kHistoPairs[*min_entropy_ix][1]]; 320 for (i = 1; i < 256; ++i) { 321 if ((red_histo[i] | blue_histo[i]) != 0) { 322 *red_and_blue_always_zero = 0; 323 break; 324 } 325 } 326 } 327 } 328 WebPSafeFree(histo); 329 return 1; 330 } else { 331 return 0; 332 } 333 } 334 335 static int GetHistoBits(int method, int use_palette, int width, int height) { 336 // Make tile size a function of encoding method (Range: 0 to 6). 337 int histo_bits = (use_palette ? 9 : 7) - method; 338 while (1) { 339 const int huff_image_size = VP8LSubSampleSize(width, histo_bits) * 340 VP8LSubSampleSize(height, histo_bits); 341 if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break; 342 ++histo_bits; 343 } 344 return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : 345 (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; 346 } 347 348 static int GetTransformBits(int method, int histo_bits) { 349 const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5; 350 const int res = 351 (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits; 352 assert(res <= MAX_TRANSFORM_BITS); 353 return res; 354 } 355 356 // Set of parameters to be used in each iteration of the cruncher. 357 #define CRUNCH_CONFIGS_LZ77_MAX 2 358 typedef struct { 359 int entropy_idx_; 360 int lz77s_types_to_try_[CRUNCH_CONFIGS_LZ77_MAX]; 361 int lz77s_types_to_try_size_; 362 } CrunchConfig; 363 364 #define CRUNCH_CONFIGS_MAX kNumEntropyIx 365 366 static int EncoderAnalyze(VP8LEncoder* const enc, 367 CrunchConfig crunch_configs[CRUNCH_CONFIGS_MAX], 368 int* const crunch_configs_size, 369 int* const red_and_blue_always_zero) { 370 const WebPPicture* const pic = enc->pic_; 371 const int width = pic->width; 372 const int height = pic->height; 373 const WebPConfig* const config = enc->config_; 374 const int method = config->method; 375 const int low_effort = (config->method == 0); 376 int i; 377 int use_palette; 378 int n_lz77s; 379 assert(pic != NULL && pic->argb != NULL); 380 381 use_palette = 382 AnalyzeAndCreatePalette(pic, low_effort, 383 enc->palette_, &enc->palette_size_); 384 385 // Empirical bit sizes. 386 enc->histo_bits_ = GetHistoBits(method, 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 crunch_configs[0].entropy_idx_ = use_palette ? kPalette : kSpatialSubGreen; 393 n_lz77s = 1; 394 *crunch_configs_size = 1; 395 } else { 396 EntropyIx min_entropy_ix; 397 // Try out multiple LZ77 on images with few colors. 398 n_lz77s = (enc->palette_size_ > 0 && enc->palette_size_ <= 16) ? 2 : 1; 399 if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride, use_palette, 400 enc->palette_size_, enc->transform_bits_, 401 &min_entropy_ix, red_and_blue_always_zero)) { 402 return 0; 403 } 404 if (method == 6 && config->quality == 100) { 405 // Go brute force on all transforms. 406 *crunch_configs_size = 0; 407 for (i = 0; i < kNumEntropyIx; ++i) { 408 if (i != kPalette || use_palette) { 409 assert(*crunch_configs_size < CRUNCH_CONFIGS_MAX); 410 crunch_configs[(*crunch_configs_size)++].entropy_idx_ = i; 411 } 412 } 413 } else { 414 // Only choose the guessed best transform. 415 *crunch_configs_size = 1; 416 crunch_configs[0].entropy_idx_ = min_entropy_ix; 417 } 418 } 419 // Fill in the different LZ77s. 420 assert(n_lz77s <= CRUNCH_CONFIGS_LZ77_MAX); 421 for (i = 0; i < *crunch_configs_size; ++i) { 422 int j; 423 for (j = 0; j < n_lz77s; ++j) { 424 crunch_configs[i].lz77s_types_to_try_[j] = 425 (j == 0) ? kLZ77Standard | kLZ77RLE : kLZ77Box; 426 } 427 crunch_configs[i].lz77s_types_to_try_size_ = n_lz77s; 428 } 429 return 1; 430 } 431 432 static int EncoderInit(VP8LEncoder* const enc) { 433 const WebPPicture* const pic = enc->pic_; 434 const int width = pic->width; 435 const int height = pic->height; 436 const int pix_cnt = width * height; 437 // we round the block size up, so we're guaranteed to have 438 // at most MAX_REFS_BLOCK_PER_IMAGE blocks used: 439 const int refs_block_size = (pix_cnt - 1) / MAX_REFS_BLOCK_PER_IMAGE + 1; 440 int i; 441 if (!VP8LHashChainInit(&enc->hash_chain_, pix_cnt)) return 0; 442 443 for (i = 0; i < 3; ++i) VP8LBackwardRefsInit(&enc->refs_[i], refs_block_size); 444 445 return 1; 446 } 447 448 // Returns false in case of memory error. 449 static int GetHuffBitLengthsAndCodes( 450 const VP8LHistogramSet* const histogram_image, 451 HuffmanTreeCode* const huffman_codes) { 452 int i, k; 453 int ok = 0; 454 uint64_t total_length_size = 0; 455 uint8_t* mem_buf = NULL; 456 const int histogram_image_size = histogram_image->size; 457 int max_num_symbols = 0; 458 uint8_t* buf_rle = NULL; 459 HuffmanTree* huff_tree = NULL; 460 461 // Iterate over all histograms and get the aggregate number of codes used. 462 for (i = 0; i < histogram_image_size; ++i) { 463 const VP8LHistogram* const histo = histogram_image->histograms[i]; 464 HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 465 assert(histo != NULL); 466 for (k = 0; k < 5; ++k) { 467 const int num_symbols = 468 (k == 0) ? VP8LHistogramNumCodes(histo->palette_code_bits_) : 469 (k == 4) ? NUM_DISTANCE_CODES : 256; 470 codes[k].num_symbols = num_symbols; 471 total_length_size += num_symbols; 472 } 473 } 474 475 // Allocate and Set Huffman codes. 476 { 477 uint16_t* codes; 478 uint8_t* lengths; 479 mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size, 480 sizeof(*lengths) + sizeof(*codes)); 481 if (mem_buf == NULL) goto End; 482 483 codes = (uint16_t*)mem_buf; 484 lengths = (uint8_t*)&codes[total_length_size]; 485 for (i = 0; i < 5 * histogram_image_size; ++i) { 486 const int bit_length = huffman_codes[i].num_symbols; 487 huffman_codes[i].codes = codes; 488 huffman_codes[i].code_lengths = lengths; 489 codes += bit_length; 490 lengths += bit_length; 491 if (max_num_symbols < bit_length) { 492 max_num_symbols = bit_length; 493 } 494 } 495 } 496 497 buf_rle = (uint8_t*)WebPSafeMalloc(1ULL, max_num_symbols); 498 huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * max_num_symbols, 499 sizeof(*huff_tree)); 500 if (buf_rle == NULL || huff_tree == NULL) goto End; 501 502 // Create Huffman trees. 503 for (i = 0; i < histogram_image_size; ++i) { 504 HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 505 VP8LHistogram* const histo = histogram_image->histograms[i]; 506 VP8LCreateHuffmanTree(histo->literal_, 15, buf_rle, huff_tree, codes + 0); 507 VP8LCreateHuffmanTree(histo->red_, 15, buf_rle, huff_tree, codes + 1); 508 VP8LCreateHuffmanTree(histo->blue_, 15, buf_rle, huff_tree, codes + 2); 509 VP8LCreateHuffmanTree(histo->alpha_, 15, buf_rle, huff_tree, codes + 3); 510 VP8LCreateHuffmanTree(histo->distance_, 15, buf_rle, huff_tree, codes + 4); 511 } 512 ok = 1; 513 End: 514 WebPSafeFree(huff_tree); 515 WebPSafeFree(buf_rle); 516 if (!ok) { 517 WebPSafeFree(mem_buf); 518 memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes)); 519 } 520 return ok; 521 } 522 523 static void StoreHuffmanTreeOfHuffmanTreeToBitMask( 524 VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) { 525 // RFC 1951 will calm you down if you are worried about this funny sequence. 526 // This sequence is tuned from that, but more weighted for lower symbol count, 527 // and more spiking histograms. 528 static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = { 529 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 530 }; 531 int i; 532 // Throw away trailing zeros: 533 int codes_to_store = CODE_LENGTH_CODES; 534 for (; codes_to_store > 4; --codes_to_store) { 535 if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { 536 break; 537 } 538 } 539 VP8LPutBits(bw, codes_to_store - 4, 4); 540 for (i = 0; i < codes_to_store; ++i) { 541 VP8LPutBits(bw, code_length_bitdepth[kStorageOrder[i]], 3); 542 } 543 } 544 545 static void ClearHuffmanTreeIfOnlyOneSymbol( 546 HuffmanTreeCode* const huffman_code) { 547 int k; 548 int count = 0; 549 for (k = 0; k < huffman_code->num_symbols; ++k) { 550 if (huffman_code->code_lengths[k] != 0) { 551 ++count; 552 if (count > 1) return; 553 } 554 } 555 for (k = 0; k < huffman_code->num_symbols; ++k) { 556 huffman_code->code_lengths[k] = 0; 557 huffman_code->codes[k] = 0; 558 } 559 } 560 561 static void StoreHuffmanTreeToBitMask( 562 VP8LBitWriter* const bw, 563 const HuffmanTreeToken* const tokens, const int num_tokens, 564 const HuffmanTreeCode* const huffman_code) { 565 int i; 566 for (i = 0; i < num_tokens; ++i) { 567 const int ix = tokens[i].code; 568 const int extra_bits = tokens[i].extra_bits; 569 VP8LPutBits(bw, huffman_code->codes[ix], huffman_code->code_lengths[ix]); 570 switch (ix) { 571 case 16: 572 VP8LPutBits(bw, extra_bits, 2); 573 break; 574 case 17: 575 VP8LPutBits(bw, extra_bits, 3); 576 break; 577 case 18: 578 VP8LPutBits(bw, extra_bits, 7); 579 break; 580 } 581 } 582 } 583 584 // 'huff_tree' and 'tokens' are pre-alloacted buffers. 585 static void StoreFullHuffmanCode(VP8LBitWriter* const bw, 586 HuffmanTree* const huff_tree, 587 HuffmanTreeToken* const tokens, 588 const HuffmanTreeCode* const tree) { 589 uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 }; 590 uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 }; 591 const int max_tokens = tree->num_symbols; 592 int num_tokens; 593 HuffmanTreeCode huffman_code; 594 huffman_code.num_symbols = CODE_LENGTH_CODES; 595 huffman_code.code_lengths = code_length_bitdepth; 596 huffman_code.codes = code_length_bitdepth_symbols; 597 598 VP8LPutBits(bw, 0, 1); 599 num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens); 600 { 601 uint32_t histogram[CODE_LENGTH_CODES] = { 0 }; 602 uint8_t buf_rle[CODE_LENGTH_CODES] = { 0 }; 603 int i; 604 for (i = 0; i < num_tokens; ++i) { 605 ++histogram[tokens[i].code]; 606 } 607 608 VP8LCreateHuffmanTree(histogram, 7, buf_rle, huff_tree, &huffman_code); 609 } 610 611 StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth); 612 ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code); 613 { 614 int trailing_zero_bits = 0; 615 int trimmed_length = num_tokens; 616 int write_trimmed_length; 617 int length; 618 int i = num_tokens; 619 while (i-- > 0) { 620 const int ix = tokens[i].code; 621 if (ix == 0 || ix == 17 || ix == 18) { 622 --trimmed_length; // discount trailing zeros 623 trailing_zero_bits += code_length_bitdepth[ix]; 624 if (ix == 17) { 625 trailing_zero_bits += 3; 626 } else if (ix == 18) { 627 trailing_zero_bits += 7; 628 } 629 } else { 630 break; 631 } 632 } 633 write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12); 634 length = write_trimmed_length ? trimmed_length : num_tokens; 635 VP8LPutBits(bw, write_trimmed_length, 1); 636 if (write_trimmed_length) { 637 if (trimmed_length == 2) { 638 VP8LPutBits(bw, 0, 3 + 2); // nbitpairs=1, trimmed_length=2 639 } else { 640 const int nbits = BitsLog2Floor(trimmed_length - 2); 641 const int nbitpairs = nbits / 2 + 1; 642 assert(trimmed_length > 2); 643 assert(nbitpairs - 1 < 8); 644 VP8LPutBits(bw, nbitpairs - 1, 3); 645 VP8LPutBits(bw, trimmed_length - 2, nbitpairs * 2); 646 } 647 } 648 StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code); 649 } 650 } 651 652 // 'huff_tree' and 'tokens' are pre-alloacted buffers. 653 static void StoreHuffmanCode(VP8LBitWriter* const bw, 654 HuffmanTree* const huff_tree, 655 HuffmanTreeToken* const tokens, 656 const HuffmanTreeCode* const huffman_code) { 657 int i; 658 int count = 0; 659 int symbols[2] = { 0, 0 }; 660 const int kMaxBits = 8; 661 const int kMaxSymbol = 1 << kMaxBits; 662 663 // Check whether it's a small tree. 664 for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) { 665 if (huffman_code->code_lengths[i] != 0) { 666 if (count < 2) symbols[count] = i; 667 ++count; 668 } 669 } 670 671 if (count == 0) { // emit minimal tree for empty cases 672 // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0 673 VP8LPutBits(bw, 0x01, 4); 674 } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) { 675 VP8LPutBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. 676 VP8LPutBits(bw, count - 1, 1); 677 if (symbols[0] <= 1) { 678 VP8LPutBits(bw, 0, 1); // Code bit for small (1 bit) symbol value. 679 VP8LPutBits(bw, symbols[0], 1); 680 } else { 681 VP8LPutBits(bw, 1, 1); 682 VP8LPutBits(bw, symbols[0], 8); 683 } 684 if (count == 2) { 685 VP8LPutBits(bw, symbols[1], 8); 686 } 687 } else { 688 StoreFullHuffmanCode(bw, huff_tree, tokens, huffman_code); 689 } 690 } 691 692 static WEBP_INLINE void WriteHuffmanCode(VP8LBitWriter* const bw, 693 const HuffmanTreeCode* const code, 694 int code_index) { 695 const int depth = code->code_lengths[code_index]; 696 const int symbol = code->codes[code_index]; 697 VP8LPutBits(bw, symbol, depth); 698 } 699 700 static WEBP_INLINE void WriteHuffmanCodeWithExtraBits( 701 VP8LBitWriter* const bw, 702 const HuffmanTreeCode* const code, 703 int code_index, 704 int bits, 705 int n_bits) { 706 const int depth = code->code_lengths[code_index]; 707 const int symbol = code->codes[code_index]; 708 VP8LPutBits(bw, (bits << depth) | symbol, depth + n_bits); 709 } 710 711 static WebPEncodingError StoreImageToBitMask( 712 VP8LBitWriter* const bw, int width, int histo_bits, 713 const VP8LBackwardRefs* const refs, 714 const uint16_t* histogram_symbols, 715 const HuffmanTreeCode* const huffman_codes) { 716 const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; 717 const int tile_mask = (histo_bits == 0) ? 0 : -(1 << histo_bits); 718 // x and y trace the position in the image. 719 int x = 0; 720 int y = 0; 721 int tile_x = x & tile_mask; 722 int tile_y = y & tile_mask; 723 int histogram_ix = histogram_symbols[0]; 724 const HuffmanTreeCode* codes = huffman_codes + 5 * histogram_ix; 725 VP8LRefsCursor c = VP8LRefsCursorInit(refs); 726 while (VP8LRefsCursorOk(&c)) { 727 const PixOrCopy* const v = c.cur_pos; 728 if ((tile_x != (x & tile_mask)) || (tile_y != (y & tile_mask))) { 729 tile_x = x & tile_mask; 730 tile_y = y & tile_mask; 731 histogram_ix = histogram_symbols[(y >> histo_bits) * histo_xsize + 732 (x >> histo_bits)]; 733 codes = huffman_codes + 5 * histogram_ix; 734 } 735 if (PixOrCopyIsLiteral(v)) { 736 static const uint8_t order[] = { 1, 2, 0, 3 }; 737 int k; 738 for (k = 0; k < 4; ++k) { 739 const int code = PixOrCopyLiteral(v, order[k]); 740 WriteHuffmanCode(bw, codes + k, code); 741 } 742 } else if (PixOrCopyIsCacheIdx(v)) { 743 const int code = PixOrCopyCacheIdx(v); 744 const int literal_ix = 256 + NUM_LENGTH_CODES + code; 745 WriteHuffmanCode(bw, codes, literal_ix); 746 } else { 747 int bits, n_bits; 748 int code; 749 750 const int distance = PixOrCopyDistance(v); 751 VP8LPrefixEncode(v->len, &code, &n_bits, &bits); 752 WriteHuffmanCodeWithExtraBits(bw, codes, 256 + code, bits, n_bits); 753 754 // Don't write the distance with the extra bits code since 755 // the distance can be up to 18 bits of extra bits, and the prefix 756 // 15 bits, totaling to 33, and our PutBits only supports up to 32 bits. 757 VP8LPrefixEncode(distance, &code, &n_bits, &bits); 758 WriteHuffmanCode(bw, codes + 4, code); 759 VP8LPutBits(bw, bits, n_bits); 760 } 761 x += PixOrCopyLength(v); 762 while (x >= width) { 763 x -= width; 764 ++y; 765 } 766 VP8LRefsCursorNext(&c); 767 } 768 return bw->error_ ? VP8_ENC_ERROR_OUT_OF_MEMORY : VP8_ENC_OK; 769 } 770 771 // Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31 772 static WebPEncodingError EncodeImageNoHuffman(VP8LBitWriter* const bw, 773 const uint32_t* const argb, 774 VP8LHashChain* const hash_chain, 775 VP8LBackwardRefs* const refs_tmp1, 776 VP8LBackwardRefs* const refs_tmp2, 777 int width, int height, 778 int quality, int low_effort) { 779 int i; 780 int max_tokens = 0; 781 WebPEncodingError err = VP8_ENC_OK; 782 VP8LBackwardRefs* refs; 783 HuffmanTreeToken* tokens = NULL; 784 HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } }; 785 const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol 786 int cache_bits = 0; 787 VP8LHistogramSet* histogram_image = NULL; 788 HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc( 789 3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree)); 790 if (huff_tree == NULL) { 791 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 792 goto Error; 793 } 794 795 // Calculate backward references from ARGB image. 796 if (!VP8LHashChainFill(hash_chain, quality, argb, width, height, 797 low_effort)) { 798 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 799 goto Error; 800 } 801 refs = VP8LGetBackwardReferences(width, height, argb, quality, 0, 802 kLZ77Standard | kLZ77RLE, &cache_bits, 803 hash_chain, refs_tmp1, refs_tmp2); 804 if (refs == NULL) { 805 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 806 goto Error; 807 } 808 histogram_image = VP8LAllocateHistogramSet(1, cache_bits); 809 if (histogram_image == NULL) { 810 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 811 goto Error; 812 } 813 VP8LHistogramSetClear(histogram_image); 814 815 // Build histogram image and symbols from backward references. 816 VP8LHistogramStoreRefs(refs, histogram_image->histograms[0]); 817 818 // Create Huffman bit lengths and codes for each histogram image. 819 assert(histogram_image->size == 1); 820 if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 821 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 822 goto Error; 823 } 824 825 // No color cache, no Huffman image. 826 VP8LPutBits(bw, 0, 1); 827 828 // Find maximum number of symbols for the huffman tree-set. 829 for (i = 0; i < 5; ++i) { 830 HuffmanTreeCode* const codes = &huffman_codes[i]; 831 if (max_tokens < codes->num_symbols) { 832 max_tokens = codes->num_symbols; 833 } 834 } 835 836 tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens)); 837 if (tokens == NULL) { 838 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 839 goto Error; 840 } 841 842 // Store Huffman codes. 843 for (i = 0; i < 5; ++i) { 844 HuffmanTreeCode* const codes = &huffman_codes[i]; 845 StoreHuffmanCode(bw, huff_tree, tokens, codes); 846 ClearHuffmanTreeIfOnlyOneSymbol(codes); 847 } 848 849 // Store actual literals. 850 err = StoreImageToBitMask(bw, width, 0, refs, histogram_symbols, 851 huffman_codes); 852 853 Error: 854 WebPSafeFree(tokens); 855 WebPSafeFree(huff_tree); 856 VP8LFreeHistogramSet(histogram_image); 857 WebPSafeFree(huffman_codes[0].codes); 858 return err; 859 } 860 861 static WebPEncodingError EncodeImageInternal( 862 VP8LBitWriter* const bw, const uint32_t* const argb, 863 VP8LHashChain* const hash_chain, VP8LBackwardRefs refs_array[3], int width, 864 int height, int quality, int low_effort, int use_cache, 865 const CrunchConfig* const config, int* cache_bits, int histogram_bits, 866 size_t init_byte_position, int* const hdr_size, int* const data_size) { 867 WebPEncodingError err = VP8_ENC_OK; 868 const uint32_t histogram_image_xysize = 869 VP8LSubSampleSize(width, histogram_bits) * 870 VP8LSubSampleSize(height, histogram_bits); 871 VP8LHistogramSet* histogram_image = NULL; 872 VP8LHistogram* tmp_histo = NULL; 873 int histogram_image_size = 0; 874 size_t bit_array_size = 0; 875 HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc( 876 3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree)); 877 HuffmanTreeToken* tokens = NULL; 878 HuffmanTreeCode* huffman_codes = NULL; 879 VP8LBackwardRefs* refs_best; 880 VP8LBackwardRefs* refs_tmp; 881 uint16_t* const histogram_symbols = 882 (uint16_t*)WebPSafeMalloc(histogram_image_xysize, 883 sizeof(*histogram_symbols)); 884 int lz77s_idx; 885 VP8LBitWriter bw_init = *bw, bw_best; 886 int hdr_size_tmp; 887 assert(histogram_bits >= MIN_HUFFMAN_BITS); 888 assert(histogram_bits <= MAX_HUFFMAN_BITS); 889 assert(hdr_size != NULL); 890 assert(data_size != NULL); 891 892 if (histogram_symbols == NULL) { 893 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 894 goto Error; 895 } 896 897 if (use_cache) { 898 // If the value is different from zero, it has been set during the 899 // palette analysis. 900 if (*cache_bits == 0) *cache_bits = MAX_COLOR_CACHE_BITS; 901 } else { 902 *cache_bits = 0; 903 } 904 // 'best_refs' is the reference to the best backward refs and points to one 905 // of refs_array[0] or refs_array[1]. 906 // Calculate backward references from ARGB image. 907 if (huff_tree == NULL || 908 !VP8LHashChainFill(hash_chain, quality, argb, width, height, 909 low_effort) || 910 !VP8LBitWriterInit(&bw_best, 0) || 911 (config->lz77s_types_to_try_size_ > 1 && 912 !VP8LBitWriterClone(bw, &bw_best))) { 913 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 914 goto Error; 915 } 916 for (lz77s_idx = 0; lz77s_idx < config->lz77s_types_to_try_size_; 917 ++lz77s_idx) { 918 refs_best = VP8LGetBackwardReferences( 919 width, height, argb, quality, low_effort, 920 config->lz77s_types_to_try_[lz77s_idx], cache_bits, hash_chain, 921 &refs_array[0], &refs_array[1]); 922 if (refs_best == NULL) { 923 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 924 goto Error; 925 } 926 // Keep the best references aside and use the other element from the first 927 // two as a temporary for later usage. 928 refs_tmp = &refs_array[refs_best == &refs_array[0] ? 1 : 0]; 929 930 histogram_image = 931 VP8LAllocateHistogramSet(histogram_image_xysize, *cache_bits); 932 tmp_histo = VP8LAllocateHistogram(*cache_bits); 933 if (histogram_image == NULL || tmp_histo == NULL) { 934 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 935 goto Error; 936 } 937 938 // Build histogram image and symbols from backward references. 939 if (!VP8LGetHistoImageSymbols(width, height, refs_best, quality, low_effort, 940 histogram_bits, *cache_bits, histogram_image, 941 tmp_histo, histogram_symbols)) { 942 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 943 goto Error; 944 } 945 // Create Huffman bit lengths and codes for each histogram image. 946 histogram_image_size = histogram_image->size; 947 bit_array_size = 5 * histogram_image_size; 948 huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size, 949 sizeof(*huffman_codes)); 950 // Note: some histogram_image entries may point to tmp_histos[], so the 951 // latter need to outlive the following call to GetHuffBitLengthsAndCodes(). 952 if (huffman_codes == NULL || 953 !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 954 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 955 goto Error; 956 } 957 // Free combined histograms. 958 VP8LFreeHistogramSet(histogram_image); 959 histogram_image = NULL; 960 961 // Free scratch histograms. 962 VP8LFreeHistogram(tmp_histo); 963 tmp_histo = NULL; 964 965 // Color Cache parameters. 966 if (*cache_bits > 0) { 967 VP8LPutBits(bw, 1, 1); 968 VP8LPutBits(bw, *cache_bits, 4); 969 } else { 970 VP8LPutBits(bw, 0, 1); 971 } 972 973 // Huffman image + meta huffman. 974 { 975 const int write_histogram_image = (histogram_image_size > 1); 976 VP8LPutBits(bw, write_histogram_image, 1); 977 if (write_histogram_image) { 978 uint32_t* const histogram_argb = 979 (uint32_t*)WebPSafeMalloc(histogram_image_xysize, 980 sizeof(*histogram_argb)); 981 int max_index = 0; 982 uint32_t i; 983 if (histogram_argb == NULL) { 984 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 985 goto Error; 986 } 987 for (i = 0; i < histogram_image_xysize; ++i) { 988 const int symbol_index = histogram_symbols[i] & 0xffff; 989 histogram_argb[i] = (symbol_index << 8); 990 if (symbol_index >= max_index) { 991 max_index = symbol_index + 1; 992 } 993 } 994 histogram_image_size = max_index; 995 996 VP8LPutBits(bw, histogram_bits - 2, 3); 997 err = EncodeImageNoHuffman( 998 bw, histogram_argb, hash_chain, refs_tmp, &refs_array[2], 999 VP8LSubSampleSize(width, histogram_bits), 1000 VP8LSubSampleSize(height, histogram_bits), quality, low_effort); 1001 WebPSafeFree(histogram_argb); 1002 if (err != VP8_ENC_OK) goto Error; 1003 } 1004 } 1005 1006 // Store Huffman codes. 1007 { 1008 int i; 1009 int max_tokens = 0; 1010 // Find maximum number of symbols for the huffman tree-set. 1011 for (i = 0; i < 5 * histogram_image_size; ++i) { 1012 HuffmanTreeCode* const codes = &huffman_codes[i]; 1013 if (max_tokens < codes->num_symbols) { 1014 max_tokens = codes->num_symbols; 1015 } 1016 } 1017 tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens)); 1018 if (tokens == NULL) { 1019 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1020 goto Error; 1021 } 1022 for (i = 0; i < 5 * histogram_image_size; ++i) { 1023 HuffmanTreeCode* const codes = &huffman_codes[i]; 1024 StoreHuffmanCode(bw, huff_tree, tokens, codes); 1025 ClearHuffmanTreeIfOnlyOneSymbol(codes); 1026 } 1027 } 1028 // Store actual literals. 1029 hdr_size_tmp = (int)(VP8LBitWriterNumBytes(bw) - init_byte_position); 1030 err = StoreImageToBitMask(bw, width, histogram_bits, refs_best, 1031 histogram_symbols, huffman_codes); 1032 // Keep track of the smallest image so far. 1033 if (lz77s_idx == 0 || 1034 VP8LBitWriterNumBytes(bw) < VP8LBitWriterNumBytes(&bw_best)) { 1035 *hdr_size = hdr_size_tmp; 1036 *data_size = 1037 (int)(VP8LBitWriterNumBytes(bw) - init_byte_position - *hdr_size); 1038 VP8LBitWriterSwap(bw, &bw_best); 1039 } 1040 // Reset the bit writer for the following iteration if any. 1041 if (config->lz77s_types_to_try_size_ > 1) VP8LBitWriterReset(&bw_init, bw); 1042 WebPSafeFree(tokens); 1043 tokens = NULL; 1044 if (huffman_codes != NULL) { 1045 WebPSafeFree(huffman_codes->codes); 1046 WebPSafeFree(huffman_codes); 1047 huffman_codes = NULL; 1048 } 1049 } 1050 VP8LBitWriterSwap(bw, &bw_best); 1051 1052 Error: 1053 WebPSafeFree(tokens); 1054 WebPSafeFree(huff_tree); 1055 VP8LFreeHistogramSet(histogram_image); 1056 VP8LFreeHistogram(tmp_histo); 1057 if (huffman_codes != NULL) { 1058 WebPSafeFree(huffman_codes->codes); 1059 WebPSafeFree(huffman_codes); 1060 } 1061 WebPSafeFree(histogram_symbols); 1062 VP8LBitWriterWipeOut(&bw_best); 1063 return err; 1064 } 1065 1066 // ----------------------------------------------------------------------------- 1067 // Transforms 1068 1069 static void ApplySubtractGreen(VP8LEncoder* const enc, int width, int height, 1070 VP8LBitWriter* const bw) { 1071 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1072 VP8LPutBits(bw, SUBTRACT_GREEN, 2); 1073 VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); 1074 } 1075 1076 static WebPEncodingError ApplyPredictFilter(const VP8LEncoder* const enc, 1077 int width, int height, 1078 int quality, int low_effort, 1079 int used_subtract_green, 1080 VP8LBitWriter* const bw) { 1081 const int pred_bits = enc->transform_bits_; 1082 const int transform_width = VP8LSubSampleSize(width, pred_bits); 1083 const int transform_height = VP8LSubSampleSize(height, pred_bits); 1084 // we disable near-lossless quantization if palette is used. 1085 const int near_lossless_strength = enc->use_palette_ ? 100 1086 : enc->config_->near_lossless; 1087 1088 VP8LResidualImage(width, height, pred_bits, low_effort, enc->argb_, 1089 enc->argb_scratch_, enc->transform_data_, 1090 near_lossless_strength, enc->config_->exact, 1091 used_subtract_green); 1092 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1093 VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2); 1094 assert(pred_bits >= 2); 1095 VP8LPutBits(bw, pred_bits - 2, 3); 1096 return EncodeImageNoHuffman( 1097 bw, enc->transform_data_, (VP8LHashChain*)&enc->hash_chain_, 1098 (VP8LBackwardRefs*)&enc->refs_[0], // cast const away 1099 (VP8LBackwardRefs*)&enc->refs_[1], transform_width, transform_height, 1100 quality, low_effort); 1101 } 1102 1103 static WebPEncodingError ApplyCrossColorFilter(const VP8LEncoder* const enc, 1104 int width, int height, 1105 int quality, int low_effort, 1106 VP8LBitWriter* const bw) { 1107 const int ccolor_transform_bits = enc->transform_bits_; 1108 const int transform_width = VP8LSubSampleSize(width, ccolor_transform_bits); 1109 const int transform_height = VP8LSubSampleSize(height, ccolor_transform_bits); 1110 1111 VP8LColorSpaceTransform(width, height, ccolor_transform_bits, quality, 1112 enc->argb_, enc->transform_data_); 1113 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1114 VP8LPutBits(bw, CROSS_COLOR_TRANSFORM, 2); 1115 assert(ccolor_transform_bits >= 2); 1116 VP8LPutBits(bw, ccolor_transform_bits - 2, 3); 1117 return EncodeImageNoHuffman( 1118 bw, enc->transform_data_, (VP8LHashChain*)&enc->hash_chain_, 1119 (VP8LBackwardRefs*)&enc->refs_[0], // cast const away 1120 (VP8LBackwardRefs*)&enc->refs_[1], transform_width, transform_height, 1121 quality, low_effort); 1122 } 1123 1124 // ----------------------------------------------------------------------------- 1125 1126 static WebPEncodingError WriteRiffHeader(const WebPPicture* const pic, 1127 size_t riff_size, size_t vp8l_size) { 1128 uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = { 1129 'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P', 1130 'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE, 1131 }; 1132 PutLE32(riff + TAG_SIZE, (uint32_t)riff_size); 1133 PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size); 1134 if (!pic->writer(riff, sizeof(riff), pic)) { 1135 return VP8_ENC_ERROR_BAD_WRITE; 1136 } 1137 return VP8_ENC_OK; 1138 } 1139 1140 static int WriteImageSize(const WebPPicture* const pic, 1141 VP8LBitWriter* const bw) { 1142 const int width = pic->width - 1; 1143 const int height = pic->height - 1; 1144 assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION); 1145 1146 VP8LPutBits(bw, width, VP8L_IMAGE_SIZE_BITS); 1147 VP8LPutBits(bw, height, VP8L_IMAGE_SIZE_BITS); 1148 return !bw->error_; 1149 } 1150 1151 static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) { 1152 VP8LPutBits(bw, has_alpha, 1); 1153 VP8LPutBits(bw, VP8L_VERSION, VP8L_VERSION_BITS); 1154 return !bw->error_; 1155 } 1156 1157 static WebPEncodingError WriteImage(const WebPPicture* const pic, 1158 VP8LBitWriter* const bw, 1159 size_t* const coded_size) { 1160 WebPEncodingError err = VP8_ENC_OK; 1161 const uint8_t* const webpll_data = VP8LBitWriterFinish(bw); 1162 const size_t webpll_size = VP8LBitWriterNumBytes(bw); 1163 const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size; 1164 const size_t pad = vp8l_size & 1; 1165 const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad; 1166 1167 err = WriteRiffHeader(pic, riff_size, vp8l_size); 1168 if (err != VP8_ENC_OK) goto Error; 1169 1170 if (!pic->writer(webpll_data, webpll_size, pic)) { 1171 err = VP8_ENC_ERROR_BAD_WRITE; 1172 goto Error; 1173 } 1174 1175 if (pad) { 1176 const uint8_t pad_byte[1] = { 0 }; 1177 if (!pic->writer(pad_byte, 1, pic)) { 1178 err = VP8_ENC_ERROR_BAD_WRITE; 1179 goto Error; 1180 } 1181 } 1182 *coded_size = CHUNK_HEADER_SIZE + riff_size; 1183 return VP8_ENC_OK; 1184 1185 Error: 1186 return err; 1187 } 1188 1189 // ----------------------------------------------------------------------------- 1190 1191 static void ClearTransformBuffer(VP8LEncoder* const enc) { 1192 WebPSafeFree(enc->transform_mem_); 1193 enc->transform_mem_ = NULL; 1194 enc->transform_mem_size_ = 0; 1195 } 1196 1197 // Allocates the memory for argb (W x H) buffer, 2 rows of context for 1198 // prediction and transform data. 1199 // Flags influencing the memory allocated: 1200 // enc->transform_bits_ 1201 // enc->use_predict_, enc->use_cross_color_ 1202 static WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc, 1203 int width, int height) { 1204 WebPEncodingError err = VP8_ENC_OK; 1205 const uint64_t image_size = width * height; 1206 // VP8LResidualImage needs room for 2 scanlines of uint32 pixels with an extra 1207 // pixel in each, plus 2 regular scanlines of bytes. 1208 // TODO(skal): Clean up by using arithmetic in bytes instead of words. 1209 const uint64_t argb_scratch_size = 1210 enc->use_predict_ 1211 ? (width + 1) * 2 + 1212 (width * 2 + sizeof(uint32_t) - 1) / sizeof(uint32_t) 1213 : 0; 1214 const uint64_t transform_data_size = 1215 (enc->use_predict_ || enc->use_cross_color_) 1216 ? VP8LSubSampleSize(width, enc->transform_bits_) * 1217 VP8LSubSampleSize(height, enc->transform_bits_) 1218 : 0; 1219 const uint64_t max_alignment_in_words = 1220 (WEBP_ALIGN_CST + sizeof(uint32_t) - 1) / sizeof(uint32_t); 1221 const uint64_t mem_size = 1222 image_size + max_alignment_in_words + 1223 argb_scratch_size + max_alignment_in_words + 1224 transform_data_size; 1225 uint32_t* mem = enc->transform_mem_; 1226 if (mem == NULL || mem_size > enc->transform_mem_size_) { 1227 ClearTransformBuffer(enc); 1228 mem = (uint32_t*)WebPSafeMalloc(mem_size, sizeof(*mem)); 1229 if (mem == NULL) { 1230 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1231 goto Error; 1232 } 1233 enc->transform_mem_ = mem; 1234 enc->transform_mem_size_ = (size_t)mem_size; 1235 enc->argb_content_ = kEncoderNone; 1236 } 1237 enc->argb_ = mem; 1238 mem = (uint32_t*)WEBP_ALIGN(mem + image_size); 1239 enc->argb_scratch_ = mem; 1240 mem = (uint32_t*)WEBP_ALIGN(mem + argb_scratch_size); 1241 enc->transform_data_ = mem; 1242 1243 enc->current_width_ = width; 1244 Error: 1245 return err; 1246 } 1247 1248 static WebPEncodingError MakeInputImageCopy(VP8LEncoder* const enc) { 1249 WebPEncodingError err = VP8_ENC_OK; 1250 const WebPPicture* const picture = enc->pic_; 1251 const int width = picture->width; 1252 const int height = picture->height; 1253 1254 err = AllocateTransformBuffer(enc, width, height); 1255 if (err != VP8_ENC_OK) return err; 1256 if (enc->argb_content_ == kEncoderARGB) return VP8_ENC_OK; 1257 1258 { 1259 uint32_t* dst = enc->argb_; 1260 const uint32_t* src = picture->argb; 1261 int y; 1262 for (y = 0; y < height; ++y) { 1263 memcpy(dst, src, width * sizeof(*dst)); 1264 dst += width; 1265 src += picture->argb_stride; 1266 } 1267 } 1268 enc->argb_content_ = kEncoderARGB; 1269 assert(enc->current_width_ == width); 1270 return VP8_ENC_OK; 1271 } 1272 1273 // ----------------------------------------------------------------------------- 1274 1275 static WEBP_INLINE int SearchColorNoIdx(const uint32_t sorted[], uint32_t color, 1276 int hi) { 1277 int low = 0; 1278 if (sorted[low] == color) return low; // loop invariant: sorted[low] != color 1279 while (1) { 1280 const int mid = (low + hi) >> 1; 1281 if (sorted[mid] == color) { 1282 return mid; 1283 } else if (sorted[mid] < color) { 1284 low = mid; 1285 } else { 1286 hi = mid; 1287 } 1288 } 1289 } 1290 1291 #define APPLY_PALETTE_GREEDY_MAX 4 1292 1293 static WEBP_INLINE uint32_t SearchColorGreedy(const uint32_t palette[], 1294 int palette_size, 1295 uint32_t color) { 1296 (void)palette_size; 1297 assert(palette_size < APPLY_PALETTE_GREEDY_MAX); 1298 assert(3 == APPLY_PALETTE_GREEDY_MAX - 1); 1299 if (color == palette[0]) return 0; 1300 if (color == palette[1]) return 1; 1301 if (color == palette[2]) return 2; 1302 return 3; 1303 } 1304 1305 static WEBP_INLINE uint32_t ApplyPaletteHash0(uint32_t color) { 1306 // Focus on the green color. 1307 return (color >> 8) & 0xff; 1308 } 1309 1310 #define PALETTE_INV_SIZE_BITS 11 1311 #define PALETTE_INV_SIZE (1 << PALETTE_INV_SIZE_BITS) 1312 1313 static WEBP_INLINE uint32_t ApplyPaletteHash1(uint32_t color) { 1314 // Forget about alpha. 1315 return ((uint32_t)((color & 0x00ffffffu) * 4222244071ull)) >> 1316 (32 - PALETTE_INV_SIZE_BITS); 1317 } 1318 1319 static WEBP_INLINE uint32_t ApplyPaletteHash2(uint32_t color) { 1320 // Forget about alpha. 1321 return ((uint32_t)((color & 0x00ffffffu) * ((1ull << 31) - 1))) >> 1322 (32 - PALETTE_INV_SIZE_BITS); 1323 } 1324 1325 // Sort palette in increasing order and prepare an inverse mapping array. 1326 static void PrepareMapToPalette(const uint32_t palette[], int num_colors, 1327 uint32_t sorted[], uint32_t idx_map[]) { 1328 int i; 1329 memcpy(sorted, palette, num_colors * sizeof(*sorted)); 1330 qsort(sorted, num_colors, sizeof(*sorted), PaletteCompareColorsForQsort); 1331 for (i = 0; i < num_colors; ++i) { 1332 idx_map[SearchColorNoIdx(sorted, palette[i], num_colors)] = i; 1333 } 1334 } 1335 1336 // Use 1 pixel cache for ARGB pixels. 1337 #define APPLY_PALETTE_FOR(COLOR_INDEX) do { \ 1338 uint32_t prev_pix = palette[0]; \ 1339 uint32_t prev_idx = 0; \ 1340 for (y = 0; y < height; ++y) { \ 1341 for (x = 0; x < width; ++x) { \ 1342 const uint32_t pix = src[x]; \ 1343 if (pix != prev_pix) { \ 1344 prev_idx = COLOR_INDEX; \ 1345 prev_pix = pix; \ 1346 } \ 1347 tmp_row[x] = prev_idx; \ 1348 } \ 1349 VP8LBundleColorMap(tmp_row, width, xbits, dst); \ 1350 src += src_stride; \ 1351 dst += dst_stride; \ 1352 } \ 1353 } while (0) 1354 1355 // Remap argb values in src[] to packed palettes entries in dst[] 1356 // using 'row' as a temporary buffer of size 'width'. 1357 // We assume that all src[] values have a corresponding entry in the palette. 1358 // Note: src[] can be the same as dst[] 1359 static WebPEncodingError ApplyPalette(const uint32_t* src, uint32_t src_stride, 1360 uint32_t* dst, uint32_t dst_stride, 1361 const uint32_t* palette, int palette_size, 1362 int width, int height, int xbits) { 1363 // TODO(skal): this tmp buffer is not needed if VP8LBundleColorMap() can be 1364 // made to work in-place. 1365 uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row)); 1366 int x, y; 1367 1368 if (tmp_row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; 1369 1370 if (palette_size < APPLY_PALETTE_GREEDY_MAX) { 1371 APPLY_PALETTE_FOR(SearchColorGreedy(palette, palette_size, pix)); 1372 } else { 1373 int i, j; 1374 uint16_t buffer[PALETTE_INV_SIZE]; 1375 uint32_t (*const hash_functions[])(uint32_t) = { 1376 ApplyPaletteHash0, ApplyPaletteHash1, ApplyPaletteHash2 1377 }; 1378 1379 // Try to find a perfect hash function able to go from a color to an index 1380 // within 1 << PALETTE_INV_SIZE_BITS in order to build a hash map to go 1381 // from color to index in palette. 1382 for (i = 0; i < 3; ++i) { 1383 int use_LUT = 1; 1384 // Set each element in buffer to max uint16_t. 1385 memset(buffer, 0xff, sizeof(buffer)); 1386 for (j = 0; j < palette_size; ++j) { 1387 const uint32_t ind = hash_functions[i](palette[j]); 1388 if (buffer[ind] != 0xffffu) { 1389 use_LUT = 0; 1390 break; 1391 } else { 1392 buffer[ind] = j; 1393 } 1394 } 1395 if (use_LUT) break; 1396 } 1397 1398 if (i == 0) { 1399 APPLY_PALETTE_FOR(buffer[ApplyPaletteHash0(pix)]); 1400 } else if (i == 1) { 1401 APPLY_PALETTE_FOR(buffer[ApplyPaletteHash1(pix)]); 1402 } else if (i == 2) { 1403 APPLY_PALETTE_FOR(buffer[ApplyPaletteHash2(pix)]); 1404 } else { 1405 uint32_t idx_map[MAX_PALETTE_SIZE]; 1406 uint32_t palette_sorted[MAX_PALETTE_SIZE]; 1407 PrepareMapToPalette(palette, palette_size, palette_sorted, idx_map); 1408 APPLY_PALETTE_FOR( 1409 idx_map[SearchColorNoIdx(palette_sorted, pix, palette_size)]); 1410 } 1411 } 1412 WebPSafeFree(tmp_row); 1413 return VP8_ENC_OK; 1414 } 1415 #undef APPLY_PALETTE_FOR 1416 #undef PALETTE_INV_SIZE_BITS 1417 #undef PALETTE_INV_SIZE 1418 #undef APPLY_PALETTE_GREEDY_MAX 1419 1420 // Note: Expects "enc->palette_" to be set properly. 1421 static WebPEncodingError MapImageFromPalette(VP8LEncoder* const enc, 1422 int in_place) { 1423 WebPEncodingError err = VP8_ENC_OK; 1424 const WebPPicture* const pic = enc->pic_; 1425 const int width = pic->width; 1426 const int height = pic->height; 1427 const uint32_t* const palette = enc->palette_; 1428 const uint32_t* src = in_place ? enc->argb_ : pic->argb; 1429 const int src_stride = in_place ? enc->current_width_ : pic->argb_stride; 1430 const int palette_size = enc->palette_size_; 1431 int xbits; 1432 1433 // Replace each input pixel by corresponding palette index. 1434 // This is done line by line. 1435 if (palette_size <= 4) { 1436 xbits = (palette_size <= 2) ? 3 : 2; 1437 } else { 1438 xbits = (palette_size <= 16) ? 1 : 0; 1439 } 1440 1441 err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height); 1442 if (err != VP8_ENC_OK) return err; 1443 1444 err = ApplyPalette(src, src_stride, 1445 enc->argb_, enc->current_width_, 1446 palette, palette_size, width, height, xbits); 1447 enc->argb_content_ = kEncoderPalette; 1448 return err; 1449 } 1450 1451 // Save palette_[] to bitstream. 1452 static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, int low_effort, 1453 VP8LEncoder* const enc) { 1454 int i; 1455 uint32_t tmp_palette[MAX_PALETTE_SIZE]; 1456 const int palette_size = enc->palette_size_; 1457 const uint32_t* const palette = enc->palette_; 1458 VP8LPutBits(bw, TRANSFORM_PRESENT, 1); 1459 VP8LPutBits(bw, COLOR_INDEXING_TRANSFORM, 2); 1460 assert(palette_size >= 1 && palette_size <= MAX_PALETTE_SIZE); 1461 VP8LPutBits(bw, palette_size - 1, 8); 1462 for (i = palette_size - 1; i >= 1; --i) { 1463 tmp_palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); 1464 } 1465 tmp_palette[0] = palette[0]; 1466 return EncodeImageNoHuffman(bw, tmp_palette, &enc->hash_chain_, 1467 &enc->refs_[0], &enc->refs_[1], palette_size, 1, 1468 20 /* quality */, low_effort); 1469 } 1470 1471 // ----------------------------------------------------------------------------- 1472 // VP8LEncoder 1473 1474 static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config, 1475 const WebPPicture* const picture) { 1476 VP8LEncoder* const enc = (VP8LEncoder*)WebPSafeCalloc(1ULL, sizeof(*enc)); 1477 if (enc == NULL) { 1478 WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY); 1479 return NULL; 1480 } 1481 enc->config_ = config; 1482 enc->pic_ = picture; 1483 enc->argb_content_ = kEncoderNone; 1484 1485 VP8LEncDspInit(); 1486 1487 return enc; 1488 } 1489 1490 static void VP8LEncoderDelete(VP8LEncoder* enc) { 1491 if (enc != NULL) { 1492 int i; 1493 VP8LHashChainClear(&enc->hash_chain_); 1494 for (i = 0; i < 3; ++i) VP8LBackwardRefsClear(&enc->refs_[i]); 1495 ClearTransformBuffer(enc); 1496 WebPSafeFree(enc); 1497 } 1498 } 1499 1500 // ----------------------------------------------------------------------------- 1501 // Main call 1502 1503 typedef struct { 1504 const WebPConfig* config_; 1505 const WebPPicture* picture_; 1506 VP8LBitWriter* bw_; 1507 VP8LEncoder* enc_; 1508 int use_cache_; 1509 CrunchConfig crunch_configs_[CRUNCH_CONFIGS_MAX]; 1510 int num_crunch_configs_; 1511 int red_and_blue_always_zero_; 1512 WebPEncodingError err_; 1513 WebPAuxStats* stats_; 1514 } StreamEncodeContext; 1515 1516 static int EncodeStreamHook(void* input, void* data2) { 1517 StreamEncodeContext* const params = (StreamEncodeContext*)input; 1518 const WebPConfig* const config = params->config_; 1519 const WebPPicture* const picture = params->picture_; 1520 VP8LBitWriter* const bw = params->bw_; 1521 VP8LEncoder* const enc = params->enc_; 1522 const int use_cache = params->use_cache_; 1523 const CrunchConfig* const crunch_configs = params->crunch_configs_; 1524 const int num_crunch_configs = params->num_crunch_configs_; 1525 const int red_and_blue_always_zero = params->red_and_blue_always_zero_; 1526 #if !defined(WEBP_DISABLE_STATS) 1527 WebPAuxStats* const stats = params->stats_; 1528 #endif 1529 WebPEncodingError err = VP8_ENC_OK; 1530 const int quality = (int)config->quality; 1531 const int low_effort = (config->method == 0); 1532 #if (WEBP_NEAR_LOSSLESS == 1) 1533 const int width = picture->width; 1534 #endif 1535 const int height = picture->height; 1536 const size_t byte_position = VP8LBitWriterNumBytes(bw); 1537 #if (WEBP_NEAR_LOSSLESS == 1) 1538 int use_near_lossless = 0; 1539 #endif 1540 int hdr_size = 0; 1541 int data_size = 0; 1542 int use_delta_palette = 0; 1543 int idx; 1544 size_t best_size = 0; 1545 VP8LBitWriter bw_init = *bw, bw_best; 1546 (void)data2; 1547 1548 if (!VP8LBitWriterInit(&bw_best, 0) || 1549 (num_crunch_configs > 1 && !VP8LBitWriterClone(bw, &bw_best))) { 1550 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1551 goto Error; 1552 } 1553 1554 for (idx = 0; idx < num_crunch_configs; ++idx) { 1555 const int entropy_idx = crunch_configs[idx].entropy_idx_; 1556 enc->use_palette_ = (entropy_idx == kPalette); 1557 enc->use_subtract_green_ = 1558 (entropy_idx == kSubGreen) || (entropy_idx == kSpatialSubGreen); 1559 enc->use_predict_ = 1560 (entropy_idx == kSpatial) || (entropy_idx == kSpatialSubGreen); 1561 if (low_effort) { 1562 enc->use_cross_color_ = 0; 1563 } else { 1564 enc->use_cross_color_ = red_and_blue_always_zero ? 0 : enc->use_predict_; 1565 } 1566 // Reset any parameter in the encoder that is set in the previous iteration. 1567 enc->cache_bits_ = 0; 1568 VP8LBackwardRefsClear(&enc->refs_[0]); 1569 VP8LBackwardRefsClear(&enc->refs_[1]); 1570 1571 #if (WEBP_NEAR_LOSSLESS == 1) 1572 // Apply near-lossless preprocessing. 1573 use_near_lossless = (config->near_lossless < 100) && !enc->use_palette_ && 1574 !enc->use_predict_; 1575 if (use_near_lossless) { 1576 err = AllocateTransformBuffer(enc, width, height); 1577 if (err != VP8_ENC_OK) goto Error; 1578 if ((enc->argb_content_ != kEncoderNearLossless) && 1579 !VP8ApplyNearLossless(picture, config->near_lossless, enc->argb_)) { 1580 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1581 goto Error; 1582 } 1583 enc->argb_content_ = kEncoderNearLossless; 1584 } else { 1585 enc->argb_content_ = kEncoderNone; 1586 } 1587 #else 1588 enc->argb_content_ = kEncoderNone; 1589 #endif 1590 1591 // Encode palette 1592 if (enc->use_palette_) { 1593 err = EncodePalette(bw, low_effort, enc); 1594 if (err != VP8_ENC_OK) goto Error; 1595 err = MapImageFromPalette(enc, use_delta_palette); 1596 if (err != VP8_ENC_OK) goto Error; 1597 // If using a color cache, do not have it bigger than the number of 1598 // colors. 1599 if (use_cache && enc->palette_size_ < (1 << MAX_COLOR_CACHE_BITS)) { 1600 enc->cache_bits_ = BitsLog2Floor(enc->palette_size_) + 1; 1601 } 1602 } 1603 if (!use_delta_palette) { 1604 // In case image is not packed. 1605 if (enc->argb_content_ != kEncoderNearLossless && 1606 enc->argb_content_ != kEncoderPalette) { 1607 err = MakeInputImageCopy(enc); 1608 if (err != VP8_ENC_OK) goto Error; 1609 } 1610 1611 // ----------------------------------------------------------------------- 1612 // Apply transforms and write transform data. 1613 1614 if (enc->use_subtract_green_) { 1615 ApplySubtractGreen(enc, enc->current_width_, height, bw); 1616 } 1617 1618 if (enc->use_predict_) { 1619 err = ApplyPredictFilter(enc, enc->current_width_, height, quality, 1620 low_effort, enc->use_subtract_green_, bw); 1621 if (err != VP8_ENC_OK) goto Error; 1622 } 1623 1624 if (enc->use_cross_color_) { 1625 err = ApplyCrossColorFilter(enc, enc->current_width_, height, quality, 1626 low_effort, bw); 1627 if (err != VP8_ENC_OK) goto Error; 1628 } 1629 } 1630 1631 VP8LPutBits(bw, !TRANSFORM_PRESENT, 1); // No more transforms. 1632 1633 // ------------------------------------------------------------------------- 1634 // Encode and write the transformed image. 1635 err = EncodeImageInternal(bw, enc->argb_, &enc->hash_chain_, enc->refs_, 1636 enc->current_width_, height, quality, low_effort, 1637 use_cache, &crunch_configs[idx], 1638 &enc->cache_bits_, enc->histo_bits_, 1639 byte_position, &hdr_size, &data_size); 1640 if (err != VP8_ENC_OK) goto Error; 1641 1642 // If we are better than what we already have. 1643 if (idx == 0 || VP8LBitWriterNumBytes(bw) < best_size) { 1644 best_size = VP8LBitWriterNumBytes(bw); 1645 // Store the BitWriter. 1646 VP8LBitWriterSwap(bw, &bw_best); 1647 #if !defined(WEBP_DISABLE_STATS) 1648 // Update the stats. 1649 if (stats != NULL) { 1650 stats->lossless_features = 0; 1651 if (enc->use_predict_) stats->lossless_features |= 1; 1652 if (enc->use_cross_color_) stats->lossless_features |= 2; 1653 if (enc->use_subtract_green_) stats->lossless_features |= 4; 1654 if (enc->use_palette_) stats->lossless_features |= 8; 1655 stats->histogram_bits = enc->histo_bits_; 1656 stats->transform_bits = enc->transform_bits_; 1657 stats->cache_bits = enc->cache_bits_; 1658 stats->palette_size = enc->palette_size_; 1659 stats->lossless_size = (int)(best_size - byte_position); 1660 stats->lossless_hdr_size = hdr_size; 1661 stats->lossless_data_size = data_size; 1662 } 1663 #endif 1664 } 1665 // Reset the bit writer for the following iteration if any. 1666 if (num_crunch_configs > 1) VP8LBitWriterReset(&bw_init, bw); 1667 } 1668 VP8LBitWriterSwap(&bw_best, bw); 1669 1670 Error: 1671 VP8LBitWriterWipeOut(&bw_best); 1672 params->err_ = err; 1673 // The hook should return false in case of error. 1674 return (err == VP8_ENC_OK); 1675 } 1676 1677 WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, 1678 const WebPPicture* const picture, 1679 VP8LBitWriter* const bw_main, 1680 int use_cache) { 1681 WebPEncodingError err = VP8_ENC_OK; 1682 VP8LEncoder* const enc_main = VP8LEncoderNew(config, picture); 1683 VP8LEncoder* enc_side = NULL; 1684 CrunchConfig crunch_configs[CRUNCH_CONFIGS_MAX]; 1685 int num_crunch_configs_main, num_crunch_configs_side = 0; 1686 int idx; 1687 int red_and_blue_always_zero = 0; 1688 WebPWorker worker_main, worker_side; 1689 StreamEncodeContext params_main, params_side; 1690 // The main thread uses picture->stats, the side thread uses stats_side. 1691 WebPAuxStats stats_side; 1692 VP8LBitWriter bw_side; 1693 const WebPWorkerInterface* const worker_interface = WebPGetWorkerInterface(); 1694 int ok_main; 1695 1696 // Analyze image (entropy, num_palettes etc) 1697 if (enc_main == NULL || 1698 !EncoderAnalyze(enc_main, crunch_configs, &num_crunch_configs_main, 1699 &red_and_blue_always_zero) || 1700 !EncoderInit(enc_main) || !VP8LBitWriterInit(&bw_side, 0)) { 1701 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1702 goto Error; 1703 } 1704 1705 // Split the configs between the main and side threads (if any). 1706 if (config->thread_level > 0) { 1707 num_crunch_configs_side = num_crunch_configs_main / 2; 1708 for (idx = 0; idx < num_crunch_configs_side; ++idx) { 1709 params_side.crunch_configs_[idx] = 1710 crunch_configs[num_crunch_configs_main - num_crunch_configs_side + 1711 idx]; 1712 } 1713 params_side.num_crunch_configs_ = num_crunch_configs_side; 1714 } 1715 num_crunch_configs_main -= num_crunch_configs_side; 1716 for (idx = 0; idx < num_crunch_configs_main; ++idx) { 1717 params_main.crunch_configs_[idx] = crunch_configs[idx]; 1718 } 1719 params_main.num_crunch_configs_ = num_crunch_configs_main; 1720 1721 // Fill in the parameters for the thread workers. 1722 { 1723 const int params_size = (num_crunch_configs_side > 0) ? 2 : 1; 1724 for (idx = 0; idx < params_size; ++idx) { 1725 // Create the parameters for each worker. 1726 WebPWorker* const worker = (idx == 0) ? &worker_main : &worker_side; 1727 StreamEncodeContext* const param = 1728 (idx == 0) ? ¶ms_main : ¶ms_side; 1729 param->config_ = config; 1730 param->picture_ = picture; 1731 param->use_cache_ = use_cache; 1732 param->red_and_blue_always_zero_ = red_and_blue_always_zero; 1733 if (idx == 0) { 1734 param->stats_ = picture->stats; 1735 param->bw_ = bw_main; 1736 param->enc_ = enc_main; 1737 } else { 1738 param->stats_ = (picture->stats == NULL) ? NULL : &stats_side; 1739 // Create a side bit writer. 1740 if (!VP8LBitWriterClone(bw_main, &bw_side)) { 1741 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1742 goto Error; 1743 } 1744 param->bw_ = &bw_side; 1745 // Create a side encoder. 1746 enc_side = VP8LEncoderNew(config, picture); 1747 if (enc_side == NULL || !EncoderInit(enc_side)) { 1748 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1749 goto Error; 1750 } 1751 // Copy the values that were computed for the main encoder. 1752 enc_side->histo_bits_ = enc_main->histo_bits_; 1753 enc_side->transform_bits_ = enc_main->transform_bits_; 1754 enc_side->palette_size_ = enc_main->palette_size_; 1755 memcpy(enc_side->palette_, enc_main->palette_, 1756 sizeof(enc_main->palette_)); 1757 param->enc_ = enc_side; 1758 } 1759 // Create the workers. 1760 worker_interface->Init(worker); 1761 worker->data1 = param; 1762 worker->data2 = NULL; 1763 worker->hook = EncodeStreamHook; 1764 } 1765 } 1766 1767 // Start the second thread if needed. 1768 if (num_crunch_configs_side != 0) { 1769 if (!worker_interface->Reset(&worker_side)) { 1770 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1771 goto Error; 1772 } 1773 #if !defined(WEBP_DISABLE_STATS) 1774 // This line is here and not in the param initialization above to remove a 1775 // Clang static analyzer warning. 1776 if (picture->stats != NULL) { 1777 memcpy(&stats_side, picture->stats, sizeof(stats_side)); 1778 } 1779 #endif 1780 // This line is only useful to remove a Clang static analyzer warning. 1781 params_side.err_ = VP8_ENC_OK; 1782 worker_interface->Launch(&worker_side); 1783 } 1784 // Execute the main thread. 1785 worker_interface->Execute(&worker_main); 1786 ok_main = worker_interface->Sync(&worker_main); 1787 worker_interface->End(&worker_main); 1788 if (num_crunch_configs_side != 0) { 1789 // Wait for the second thread. 1790 const int ok_side = worker_interface->Sync(&worker_side); 1791 worker_interface->End(&worker_side); 1792 if (!ok_main || !ok_side) { 1793 err = ok_main ? params_side.err_ : params_main.err_; 1794 goto Error; 1795 } 1796 if (VP8LBitWriterNumBytes(&bw_side) < VP8LBitWriterNumBytes(bw_main)) { 1797 VP8LBitWriterSwap(bw_main, &bw_side); 1798 #if !defined(WEBP_DISABLE_STATS) 1799 if (picture->stats != NULL) { 1800 memcpy(picture->stats, &stats_side, sizeof(*picture->stats)); 1801 } 1802 #endif 1803 } 1804 } else { 1805 if (!ok_main) { 1806 err = params_main.err_; 1807 goto Error; 1808 } 1809 } 1810 1811 Error: 1812 VP8LBitWriterWipeOut(&bw_side); 1813 VP8LEncoderDelete(enc_main); 1814 VP8LEncoderDelete(enc_side); 1815 return err; 1816 } 1817 1818 #undef CRUNCH_CONFIGS_MAX 1819 #undef CRUNCH_CONFIGS_LZ77_MAX 1820 1821 int VP8LEncodeImage(const WebPConfig* const config, 1822 const WebPPicture* const picture) { 1823 int width, height; 1824 int has_alpha; 1825 size_t coded_size; 1826 int percent = 0; 1827 int initial_size; 1828 WebPEncodingError err = VP8_ENC_OK; 1829 VP8LBitWriter bw; 1830 1831 if (picture == NULL) return 0; 1832 1833 if (config == NULL || picture->argb == NULL) { 1834 err = VP8_ENC_ERROR_NULL_PARAMETER; 1835 WebPEncodingSetError(picture, err); 1836 return 0; 1837 } 1838 1839 width = picture->width; 1840 height = picture->height; 1841 // Initialize BitWriter with size corresponding to 16 bpp to photo images and 1842 // 8 bpp for graphical images. 1843 initial_size = (config->image_hint == WEBP_HINT_GRAPH) ? 1844 width * height : width * height * 2; 1845 if (!VP8LBitWriterInit(&bw, initial_size)) { 1846 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1847 goto Error; 1848 } 1849 1850 if (!WebPReportProgress(picture, 1, &percent)) { 1851 UserAbort: 1852 err = VP8_ENC_ERROR_USER_ABORT; 1853 goto Error; 1854 } 1855 // Reset stats (for pure lossless coding) 1856 if (picture->stats != NULL) { 1857 WebPAuxStats* const stats = picture->stats; 1858 memset(stats, 0, sizeof(*stats)); 1859 stats->PSNR[0] = 99.f; 1860 stats->PSNR[1] = 99.f; 1861 stats->PSNR[2] = 99.f; 1862 stats->PSNR[3] = 99.f; 1863 stats->PSNR[4] = 99.f; 1864 } 1865 1866 // Write image size. 1867 if (!WriteImageSize(picture, &bw)) { 1868 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1869 goto Error; 1870 } 1871 1872 has_alpha = WebPPictureHasTransparency(picture); 1873 // Write the non-trivial Alpha flag and lossless version. 1874 if (!WriteRealAlphaAndVersion(&bw, has_alpha)) { 1875 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1876 goto Error; 1877 } 1878 1879 if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort; 1880 1881 // Encode main image stream. 1882 err = VP8LEncodeStream(config, picture, &bw, 1 /*use_cache*/); 1883 if (err != VP8_ENC_OK) goto Error; 1884 1885 if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort; 1886 1887 // Finish the RIFF chunk. 1888 err = WriteImage(picture, &bw, &coded_size); 1889 if (err != VP8_ENC_OK) goto Error; 1890 1891 if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort; 1892 1893 #if !defined(WEBP_DISABLE_STATS) 1894 // Save size. 1895 if (picture->stats != NULL) { 1896 picture->stats->coded_size += (int)coded_size; 1897 picture->stats->lossless_size = (int)coded_size; 1898 } 1899 #endif 1900 1901 if (picture->extra_info != NULL) { 1902 const int mb_w = (width + 15) >> 4; 1903 const int mb_h = (height + 15) >> 4; 1904 memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info)); 1905 } 1906 1907 Error: 1908 if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1909 VP8LBitWriterWipeOut(&bw); 1910 if (err != VP8_ENC_OK) { 1911 WebPEncodingSetError(picture, err); 1912 return 0; 1913 } 1914 return 1; 1915 } 1916 1917 //------------------------------------------------------------------------------ 1918
