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 <stdio.h> 17 #include <stdlib.h> 18 19 #include "./backward_references.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 #if defined(__cplusplus) || defined(c_plusplus) 29 extern "C" { 30 #endif 31 32 #define PALETTE_KEY_RIGHT_SHIFT 22 // Key for 1K buffer. 33 #define MAX_HUFF_IMAGE_SIZE (16 * 1024 * 1024) 34 #define MAX_COLORS_FOR_GRAPH 64 35 36 // ----------------------------------------------------------------------------- 37 // Palette 38 39 static int CompareColors(const void* p1, const void* p2) { 40 const uint32_t a = *(const uint32_t*)p1; 41 const uint32_t b = *(const uint32_t*)p2; 42 assert(a != b); 43 return (a < b) ? -1 : 1; 44 } 45 46 // If number of colors in the image is less than or equal to MAX_PALETTE_SIZE, 47 // creates a palette and returns true, else returns false. 48 static int AnalyzeAndCreatePalette(const WebPPicture* const pic, 49 uint32_t palette[MAX_PALETTE_SIZE], 50 int* const palette_size) { 51 int i, x, y, key; 52 int num_colors = 0; 53 uint8_t in_use[MAX_PALETTE_SIZE * 4] = { 0 }; 54 uint32_t colors[MAX_PALETTE_SIZE * 4]; 55 static const uint32_t kHashMul = 0x1e35a7bd; 56 const uint32_t* argb = pic->argb; 57 const int width = pic->width; 58 const int height = pic->height; 59 uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0] 60 61 for (y = 0; y < height; ++y) { 62 for (x = 0; x < width; ++x) { 63 if (argb[x] == last_pix) { 64 continue; 65 } 66 last_pix = argb[x]; 67 key = (kHashMul * last_pix) >> PALETTE_KEY_RIGHT_SHIFT; 68 while (1) { 69 if (!in_use[key]) { 70 colors[key] = last_pix; 71 in_use[key] = 1; 72 ++num_colors; 73 if (num_colors > MAX_PALETTE_SIZE) { 74 return 0; 75 } 76 break; 77 } else if (colors[key] == last_pix) { 78 // The color is already there. 79 break; 80 } else { 81 // Some other color sits there. 82 // Do linear conflict resolution. 83 ++key; 84 key &= (MAX_PALETTE_SIZE * 4 - 1); // key mask for 1K buffer. 85 } 86 } 87 } 88 argb += pic->argb_stride; 89 } 90 91 // TODO(skal): could we reuse in_use[] to speed up EncodePalette()? 92 num_colors = 0; 93 for (i = 0; i < (int)(sizeof(in_use) / sizeof(in_use[0])); ++i) { 94 if (in_use[i]) { 95 palette[num_colors] = colors[i]; 96 ++num_colors; 97 } 98 } 99 100 qsort(palette, num_colors, sizeof(*palette), CompareColors); 101 *palette_size = num_colors; 102 return 1; 103 } 104 105 static int AnalyzeEntropy(const uint32_t* argb, 106 int width, int height, int argb_stride, 107 double* const nonpredicted_bits, 108 double* const predicted_bits) { 109 int x, y; 110 const uint32_t* last_line = NULL; 111 uint32_t last_pix = argb[0]; // so we're sure that pix_diff == 0 112 113 VP8LHistogram* nonpredicted = NULL; 114 VP8LHistogram* predicted = 115 (VP8LHistogram*)malloc(2 * sizeof(*predicted)); 116 if (predicted == NULL) return 0; 117 nonpredicted = predicted + 1; 118 119 VP8LHistogramInit(predicted, 0); 120 VP8LHistogramInit(nonpredicted, 0); 121 for (y = 0; y < height; ++y) { 122 for (x = 0; x < width; ++x) { 123 const uint32_t pix = argb[x]; 124 const uint32_t pix_diff = VP8LSubPixels(pix, last_pix); 125 if (pix_diff == 0) continue; 126 if (last_line != NULL && pix == last_line[x]) { 127 continue; 128 } 129 last_pix = pix; 130 { 131 const PixOrCopy pix_token = PixOrCopyCreateLiteral(pix); 132 const PixOrCopy pix_diff_token = PixOrCopyCreateLiteral(pix_diff); 133 VP8LHistogramAddSinglePixOrCopy(nonpredicted, &pix_token); 134 VP8LHistogramAddSinglePixOrCopy(predicted, &pix_diff_token); 135 } 136 } 137 last_line = argb; 138 argb += argb_stride; 139 } 140 *nonpredicted_bits = VP8LHistogramEstimateBitsBulk(nonpredicted); 141 *predicted_bits = VP8LHistogramEstimateBitsBulk(predicted); 142 free(predicted); 143 return 1; 144 } 145 146 static int VP8LEncAnalyze(VP8LEncoder* const enc, WebPImageHint image_hint) { 147 const WebPPicture* const pic = enc->pic_; 148 assert(pic != NULL && pic->argb != NULL); 149 150 enc->use_palette_ = 151 AnalyzeAndCreatePalette(pic, enc->palette_, &enc->palette_size_); 152 153 if (image_hint == WEBP_HINT_GRAPH) { 154 if (enc->use_palette_ && enc->palette_size_ < MAX_COLORS_FOR_GRAPH) { 155 enc->use_palette_ = 0; 156 } 157 } 158 159 if (!enc->use_palette_) { 160 if (image_hint == WEBP_HINT_PHOTO) { 161 enc->use_predict_ = 1; 162 enc->use_cross_color_ = 1; 163 } else { 164 double non_pred_entropy, pred_entropy; 165 if (!AnalyzeEntropy(pic->argb, pic->width, pic->height, pic->argb_stride, 166 &non_pred_entropy, &pred_entropy)) { 167 return 0; 168 } 169 if (pred_entropy < 0.95 * non_pred_entropy) { 170 enc->use_predict_ = 1; 171 // TODO(vikasa): Observed some correlation of cross_color transform with 172 // predict. Need to investigate this further and add separate heuristic 173 // for setting use_cross_color flag. 174 enc->use_cross_color_ = 1; 175 } 176 } 177 } 178 179 return 1; 180 } 181 182 static int GetHuffBitLengthsAndCodes( 183 const VP8LHistogramSet* const histogram_image, 184 HuffmanTreeCode* const huffman_codes) { 185 int i, k; 186 int ok = 1; 187 uint64_t total_length_size = 0; 188 uint8_t* mem_buf = NULL; 189 const int histogram_image_size = histogram_image->size; 190 191 // Iterate over all histograms and get the aggregate number of codes used. 192 for (i = 0; i < histogram_image_size; ++i) { 193 const VP8LHistogram* const histo = histogram_image->histograms[i]; 194 HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 195 for (k = 0; k < 5; ++k) { 196 const int num_symbols = (k == 0) ? VP8LHistogramNumCodes(histo) 197 : (k == 4) ? NUM_DISTANCE_CODES 198 : 256; 199 codes[k].num_symbols = num_symbols; 200 total_length_size += num_symbols; 201 } 202 } 203 204 // Allocate and Set Huffman codes. 205 { 206 uint16_t* codes; 207 uint8_t* lengths; 208 mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size, 209 sizeof(*lengths) + sizeof(*codes)); 210 if (mem_buf == NULL) { 211 ok = 0; 212 goto End; 213 } 214 codes = (uint16_t*)mem_buf; 215 lengths = (uint8_t*)&codes[total_length_size]; 216 for (i = 0; i < 5 * histogram_image_size; ++i) { 217 const int bit_length = huffman_codes[i].num_symbols; 218 huffman_codes[i].codes = codes; 219 huffman_codes[i].code_lengths = lengths; 220 codes += bit_length; 221 lengths += bit_length; 222 } 223 } 224 225 // Create Huffman trees. 226 for (i = 0; ok && (i < histogram_image_size); ++i) { 227 HuffmanTreeCode* const codes = &huffman_codes[5 * i]; 228 VP8LHistogram* const histo = histogram_image->histograms[i]; 229 ok = ok && VP8LCreateHuffmanTree(histo->literal_, 15, codes + 0); 230 ok = ok && VP8LCreateHuffmanTree(histo->red_, 15, codes + 1); 231 ok = ok && VP8LCreateHuffmanTree(histo->blue_, 15, codes + 2); 232 ok = ok && VP8LCreateHuffmanTree(histo->alpha_, 15, codes + 3); 233 ok = ok && VP8LCreateHuffmanTree(histo->distance_, 15, codes + 4); 234 } 235 236 End: 237 if (!ok) { 238 free(mem_buf); 239 // If one VP8LCreateHuffmanTree() above fails, we need to clean up behind. 240 memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes)); 241 } 242 return ok; 243 } 244 245 static void StoreHuffmanTreeOfHuffmanTreeToBitMask( 246 VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) { 247 // RFC 1951 will calm you down if you are worried about this funny sequence. 248 // This sequence is tuned from that, but more weighted for lower symbol count, 249 // and more spiking histograms. 250 static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = { 251 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 252 }; 253 int i; 254 // Throw away trailing zeros: 255 int codes_to_store = CODE_LENGTH_CODES; 256 for (; codes_to_store > 4; --codes_to_store) { 257 if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { 258 break; 259 } 260 } 261 VP8LWriteBits(bw, 4, codes_to_store - 4); 262 for (i = 0; i < codes_to_store; ++i) { 263 VP8LWriteBits(bw, 3, code_length_bitdepth[kStorageOrder[i]]); 264 } 265 } 266 267 static void ClearHuffmanTreeIfOnlyOneSymbol( 268 HuffmanTreeCode* const huffman_code) { 269 int k; 270 int count = 0; 271 for (k = 0; k < huffman_code->num_symbols; ++k) { 272 if (huffman_code->code_lengths[k] != 0) { 273 ++count; 274 if (count > 1) return; 275 } 276 } 277 for (k = 0; k < huffman_code->num_symbols; ++k) { 278 huffman_code->code_lengths[k] = 0; 279 huffman_code->codes[k] = 0; 280 } 281 } 282 283 static void StoreHuffmanTreeToBitMask( 284 VP8LBitWriter* const bw, 285 const HuffmanTreeToken* const tokens, const int num_tokens, 286 const HuffmanTreeCode* const huffman_code) { 287 int i; 288 for (i = 0; i < num_tokens; ++i) { 289 const int ix = tokens[i].code; 290 const int extra_bits = tokens[i].extra_bits; 291 VP8LWriteBits(bw, huffman_code->code_lengths[ix], huffman_code->codes[ix]); 292 switch (ix) { 293 case 16: 294 VP8LWriteBits(bw, 2, extra_bits); 295 break; 296 case 17: 297 VP8LWriteBits(bw, 3, extra_bits); 298 break; 299 case 18: 300 VP8LWriteBits(bw, 7, extra_bits); 301 break; 302 } 303 } 304 } 305 306 static int StoreFullHuffmanCode(VP8LBitWriter* const bw, 307 const HuffmanTreeCode* const tree) { 308 int ok = 0; 309 uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 }; 310 uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 }; 311 const int max_tokens = tree->num_symbols; 312 int num_tokens; 313 HuffmanTreeCode huffman_code; 314 HuffmanTreeToken* const tokens = 315 (HuffmanTreeToken*)WebPSafeMalloc((uint64_t)max_tokens, sizeof(*tokens)); 316 if (tokens == NULL) return 0; 317 318 huffman_code.num_symbols = CODE_LENGTH_CODES; 319 huffman_code.code_lengths = code_length_bitdepth; 320 huffman_code.codes = code_length_bitdepth_symbols; 321 322 VP8LWriteBits(bw, 1, 0); 323 num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens); 324 { 325 int histogram[CODE_LENGTH_CODES] = { 0 }; 326 int i; 327 for (i = 0; i < num_tokens; ++i) { 328 ++histogram[tokens[i].code]; 329 } 330 331 if (!VP8LCreateHuffmanTree(histogram, 7, &huffman_code)) { 332 goto End; 333 } 334 } 335 336 StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth); 337 ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code); 338 { 339 int trailing_zero_bits = 0; 340 int trimmed_length = num_tokens; 341 int write_trimmed_length; 342 int length; 343 int i = num_tokens; 344 while (i-- > 0) { 345 const int ix = tokens[i].code; 346 if (ix == 0 || ix == 17 || ix == 18) { 347 --trimmed_length; // discount trailing zeros 348 trailing_zero_bits += code_length_bitdepth[ix]; 349 if (ix == 17) { 350 trailing_zero_bits += 3; 351 } else if (ix == 18) { 352 trailing_zero_bits += 7; 353 } 354 } else { 355 break; 356 } 357 } 358 write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12); 359 length = write_trimmed_length ? trimmed_length : num_tokens; 360 VP8LWriteBits(bw, 1, write_trimmed_length); 361 if (write_trimmed_length) { 362 const int nbits = VP8LBitsLog2Ceiling(trimmed_length - 1); 363 const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2; 364 VP8LWriteBits(bw, 3, nbitpairs - 1); 365 assert(trimmed_length >= 2); 366 VP8LWriteBits(bw, nbitpairs * 2, trimmed_length - 2); 367 } 368 StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code); 369 } 370 ok = 1; 371 End: 372 free(tokens); 373 return ok; 374 } 375 376 static int StoreHuffmanCode(VP8LBitWriter* const bw, 377 const HuffmanTreeCode* const huffman_code) { 378 int i; 379 int count = 0; 380 int symbols[2] = { 0, 0 }; 381 const int kMaxBits = 8; 382 const int kMaxSymbol = 1 << kMaxBits; 383 384 // Check whether it's a small tree. 385 for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) { 386 if (huffman_code->code_lengths[i] != 0) { 387 if (count < 2) symbols[count] = i; 388 ++count; 389 } 390 } 391 392 if (count == 0) { // emit minimal tree for empty cases 393 // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0 394 VP8LWriteBits(bw, 4, 0x01); 395 return 1; 396 } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) { 397 VP8LWriteBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. 398 VP8LWriteBits(bw, 1, count - 1); 399 if (symbols[0] <= 1) { 400 VP8LWriteBits(bw, 1, 0); // Code bit for small (1 bit) symbol value. 401 VP8LWriteBits(bw, 1, symbols[0]); 402 } else { 403 VP8LWriteBits(bw, 1, 1); 404 VP8LWriteBits(bw, 8, symbols[0]); 405 } 406 if (count == 2) { 407 VP8LWriteBits(bw, 8, symbols[1]); 408 } 409 return 1; 410 } else { 411 return StoreFullHuffmanCode(bw, huffman_code); 412 } 413 } 414 415 static void WriteHuffmanCode(VP8LBitWriter* const bw, 416 const HuffmanTreeCode* const code, 417 int code_index) { 418 const int depth = code->code_lengths[code_index]; 419 const int symbol = code->codes[code_index]; 420 VP8LWriteBits(bw, depth, symbol); 421 } 422 423 static void StoreImageToBitMask( 424 VP8LBitWriter* const bw, int width, int histo_bits, 425 const VP8LBackwardRefs* const refs, 426 const uint16_t* histogram_symbols, 427 const HuffmanTreeCode* const huffman_codes) { 428 // x and y trace the position in the image. 429 int x = 0; 430 int y = 0; 431 const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; 432 int i; 433 for (i = 0; i < refs->size; ++i) { 434 const PixOrCopy* const v = &refs->refs[i]; 435 const int histogram_ix = histogram_symbols[histo_bits ? 436 (y >> histo_bits) * histo_xsize + 437 (x >> histo_bits) : 0]; 438 const HuffmanTreeCode* const codes = huffman_codes + 5 * histogram_ix; 439 if (PixOrCopyIsCacheIdx(v)) { 440 const int code = PixOrCopyCacheIdx(v); 441 const int literal_ix = 256 + NUM_LENGTH_CODES + code; 442 WriteHuffmanCode(bw, codes, literal_ix); 443 } else if (PixOrCopyIsLiteral(v)) { 444 static const int order[] = { 1, 2, 0, 3 }; 445 int k; 446 for (k = 0; k < 4; ++k) { 447 const int code = PixOrCopyLiteral(v, order[k]); 448 WriteHuffmanCode(bw, codes + k, code); 449 } 450 } else { 451 int bits, n_bits; 452 int code, distance; 453 454 PrefixEncode(v->len, &code, &n_bits, &bits); 455 WriteHuffmanCode(bw, codes, 256 + code); 456 VP8LWriteBits(bw, n_bits, bits); 457 458 distance = PixOrCopyDistance(v); 459 PrefixEncode(distance, &code, &n_bits, &bits); 460 WriteHuffmanCode(bw, codes + 4, code); 461 VP8LWriteBits(bw, n_bits, bits); 462 } 463 x += PixOrCopyLength(v); 464 while (x >= width) { 465 x -= width; 466 ++y; 467 } 468 } 469 } 470 471 // Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31 472 static int EncodeImageNoHuffman(VP8LBitWriter* const bw, 473 const uint32_t* const argb, 474 int width, int height, int quality) { 475 int i; 476 int ok = 0; 477 VP8LBackwardRefs refs; 478 HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } }; 479 const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol 480 VP8LHistogramSet* const histogram_image = VP8LAllocateHistogramSet(1, 0); 481 if (histogram_image == NULL) return 0; 482 483 // Calculate backward references from ARGB image. 484 if (!VP8LGetBackwardReferences(width, height, argb, quality, 0, 1, &refs)) { 485 goto Error; 486 } 487 // Build histogram image and symbols from backward references. 488 VP8LHistogramStoreRefs(&refs, histogram_image->histograms[0]); 489 490 // Create Huffman bit lengths and codes for each histogram image. 491 assert(histogram_image->size == 1); 492 if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 493 goto Error; 494 } 495 496 // No color cache, no Huffman image. 497 VP8LWriteBits(bw, 1, 0); 498 499 // Store Huffman codes. 500 for (i = 0; i < 5; ++i) { 501 HuffmanTreeCode* const codes = &huffman_codes[i]; 502 if (!StoreHuffmanCode(bw, codes)) { 503 goto Error; 504 } 505 ClearHuffmanTreeIfOnlyOneSymbol(codes); 506 } 507 508 // Store actual literals. 509 StoreImageToBitMask(bw, width, 0, &refs, histogram_symbols, huffman_codes); 510 ok = 1; 511 512 Error: 513 free(histogram_image); 514 VP8LClearBackwardRefs(&refs); 515 free(huffman_codes[0].codes); 516 return ok; 517 } 518 519 static int EncodeImageInternal(VP8LBitWriter* const bw, 520 const uint32_t* const argb, 521 int width, int height, int quality, 522 int cache_bits, int histogram_bits) { 523 int ok = 0; 524 const int use_2d_locality = 1; 525 const int use_color_cache = (cache_bits > 0); 526 const uint32_t histogram_image_xysize = 527 VP8LSubSampleSize(width, histogram_bits) * 528 VP8LSubSampleSize(height, histogram_bits); 529 VP8LHistogramSet* histogram_image = 530 VP8LAllocateHistogramSet(histogram_image_xysize, 0); 531 int histogram_image_size = 0; 532 size_t bit_array_size = 0; 533 HuffmanTreeCode* huffman_codes = NULL; 534 VP8LBackwardRefs refs; 535 uint16_t* const histogram_symbols = 536 (uint16_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize, 537 sizeof(*histogram_symbols)); 538 assert(histogram_bits >= MIN_HUFFMAN_BITS); 539 assert(histogram_bits <= MAX_HUFFMAN_BITS); 540 541 if (histogram_image == NULL || histogram_symbols == NULL) { 542 free(histogram_image); 543 free(histogram_symbols); 544 return 0; 545 } 546 547 // Calculate backward references from ARGB image. 548 if (!VP8LGetBackwardReferences(width, height, argb, quality, cache_bits, 549 use_2d_locality, &refs)) { 550 goto Error; 551 } 552 // Build histogram image and symbols from backward references. 553 if (!VP8LGetHistoImageSymbols(width, height, &refs, 554 quality, histogram_bits, cache_bits, 555 histogram_image, 556 histogram_symbols)) { 557 goto Error; 558 } 559 // Create Huffman bit lengths and codes for each histogram image. 560 histogram_image_size = histogram_image->size; 561 bit_array_size = 5 * histogram_image_size; 562 huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size, 563 sizeof(*huffman_codes)); 564 if (huffman_codes == NULL || 565 !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { 566 goto Error; 567 } 568 // Free combined histograms. 569 free(histogram_image); 570 histogram_image = NULL; 571 572 // Color Cache parameters. 573 VP8LWriteBits(bw, 1, use_color_cache); 574 if (use_color_cache) { 575 VP8LWriteBits(bw, 4, cache_bits); 576 } 577 578 // Huffman image + meta huffman. 579 { 580 const int write_histogram_image = (histogram_image_size > 1); 581 VP8LWriteBits(bw, 1, write_histogram_image); 582 if (write_histogram_image) { 583 uint32_t* const histogram_argb = 584 (uint32_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize, 585 sizeof(*histogram_argb)); 586 int max_index = 0; 587 uint32_t i; 588 if (histogram_argb == NULL) goto Error; 589 for (i = 0; i < histogram_image_xysize; ++i) { 590 const int symbol_index = histogram_symbols[i] & 0xffff; 591 histogram_argb[i] = 0xff000000 | (symbol_index << 8); 592 if (symbol_index >= max_index) { 593 max_index = symbol_index + 1; 594 } 595 } 596 histogram_image_size = max_index; 597 598 VP8LWriteBits(bw, 3, histogram_bits - 2); 599 ok = EncodeImageNoHuffman(bw, histogram_argb, 600 VP8LSubSampleSize(width, histogram_bits), 601 VP8LSubSampleSize(height, histogram_bits), 602 quality); 603 free(histogram_argb); 604 if (!ok) goto Error; 605 } 606 } 607 608 // Store Huffman codes. 609 { 610 int i; 611 for (i = 0; i < 5 * histogram_image_size; ++i) { 612 HuffmanTreeCode* const codes = &huffman_codes[i]; 613 if (!StoreHuffmanCode(bw, codes)) goto Error; 614 ClearHuffmanTreeIfOnlyOneSymbol(codes); 615 } 616 } 617 618 // Store actual literals. 619 StoreImageToBitMask(bw, width, histogram_bits, &refs, 620 histogram_symbols, huffman_codes); 621 ok = 1; 622 623 Error: 624 free(histogram_image); 625 626 VP8LClearBackwardRefs(&refs); 627 if (huffman_codes != NULL) { 628 free(huffman_codes->codes); 629 free(huffman_codes); 630 } 631 free(histogram_symbols); 632 return ok; 633 } 634 635 // ----------------------------------------------------------------------------- 636 // Transforms 637 638 // Check if it would be a good idea to subtract green from red and blue. We 639 // only impact entropy in red/blue components, don't bother to look at others. 640 static int EvalAndApplySubtractGreen(VP8LEncoder* const enc, 641 int width, int height, 642 VP8LBitWriter* const bw) { 643 if (!enc->use_palette_) { 644 int i; 645 const uint32_t* const argb = enc->argb_; 646 double bit_cost_before, bit_cost_after; 647 VP8LHistogram* const histo = (VP8LHistogram*)malloc(sizeof(*histo)); 648 if (histo == NULL) return 0; 649 650 VP8LHistogramInit(histo, 1); 651 for (i = 0; i < width * height; ++i) { 652 const uint32_t c = argb[i]; 653 ++histo->red_[(c >> 16) & 0xff]; 654 ++histo->blue_[(c >> 0) & 0xff]; 655 } 656 bit_cost_before = VP8LHistogramEstimateBits(histo); 657 658 VP8LHistogramInit(histo, 1); 659 for (i = 0; i < width * height; ++i) { 660 const uint32_t c = argb[i]; 661 const int green = (c >> 8) & 0xff; 662 ++histo->red_[((c >> 16) - green) & 0xff]; 663 ++histo->blue_[((c >> 0) - green) & 0xff]; 664 } 665 bit_cost_after = VP8LHistogramEstimateBits(histo); 666 free(histo); 667 668 // Check if subtracting green yields low entropy. 669 enc->use_subtract_green_ = (bit_cost_after < bit_cost_before); 670 if (enc->use_subtract_green_) { 671 VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 672 VP8LWriteBits(bw, 2, SUBTRACT_GREEN); 673 VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); 674 } 675 } 676 return 1; 677 } 678 679 static int ApplyPredictFilter(const VP8LEncoder* const enc, 680 int width, int height, int quality, 681 VP8LBitWriter* const bw) { 682 const int pred_bits = enc->transform_bits_; 683 const int transform_width = VP8LSubSampleSize(width, pred_bits); 684 const int transform_height = VP8LSubSampleSize(height, pred_bits); 685 686 VP8LResidualImage(width, height, pred_bits, enc->argb_, enc->argb_scratch_, 687 enc->transform_data_); 688 VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 689 VP8LWriteBits(bw, 2, PREDICTOR_TRANSFORM); 690 assert(pred_bits >= 2); 691 VP8LWriteBits(bw, 3, pred_bits - 2); 692 if (!EncodeImageNoHuffman(bw, enc->transform_data_, 693 transform_width, transform_height, quality)) { 694 return 0; 695 } 696 return 1; 697 } 698 699 static int ApplyCrossColorFilter(const VP8LEncoder* const enc, 700 int width, int height, int quality, 701 VP8LBitWriter* const bw) { 702 const int ccolor_transform_bits = enc->transform_bits_; 703 const int transform_width = VP8LSubSampleSize(width, ccolor_transform_bits); 704 const int transform_height = VP8LSubSampleSize(height, ccolor_transform_bits); 705 const int step = (quality == 0) ? 32 : 8; 706 707 VP8LColorSpaceTransform(width, height, ccolor_transform_bits, step, 708 enc->argb_, enc->transform_data_); 709 VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 710 VP8LWriteBits(bw, 2, CROSS_COLOR_TRANSFORM); 711 assert(ccolor_transform_bits >= 2); 712 VP8LWriteBits(bw, 3, ccolor_transform_bits - 2); 713 if (!EncodeImageNoHuffman(bw, enc->transform_data_, 714 transform_width, transform_height, quality)) { 715 return 0; 716 } 717 return 1; 718 } 719 720 // ----------------------------------------------------------------------------- 721 722 static WebPEncodingError WriteRiffHeader(const WebPPicture* const pic, 723 size_t riff_size, size_t vp8l_size) { 724 uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = { 725 'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P', 726 'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE, 727 }; 728 PutLE32(riff + TAG_SIZE, (uint32_t)riff_size); 729 PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size); 730 if (!pic->writer(riff, sizeof(riff), pic)) { 731 return VP8_ENC_ERROR_BAD_WRITE; 732 } 733 return VP8_ENC_OK; 734 } 735 736 static int WriteImageSize(const WebPPicture* const pic, 737 VP8LBitWriter* const bw) { 738 const int width = pic->width - 1; 739 const int height = pic->height - 1; 740 assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION); 741 742 VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, width); 743 VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, height); 744 return !bw->error_; 745 } 746 747 static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) { 748 VP8LWriteBits(bw, 1, has_alpha); 749 VP8LWriteBits(bw, VP8L_VERSION_BITS, VP8L_VERSION); 750 return !bw->error_; 751 } 752 753 static WebPEncodingError WriteImage(const WebPPicture* const pic, 754 VP8LBitWriter* const bw, 755 size_t* const coded_size) { 756 WebPEncodingError err = VP8_ENC_OK; 757 const uint8_t* const webpll_data = VP8LBitWriterFinish(bw); 758 const size_t webpll_size = VP8LBitWriterNumBytes(bw); 759 const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size; 760 const size_t pad = vp8l_size & 1; 761 const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad; 762 763 err = WriteRiffHeader(pic, riff_size, vp8l_size); 764 if (err != VP8_ENC_OK) goto Error; 765 766 if (!pic->writer(webpll_data, webpll_size, pic)) { 767 err = VP8_ENC_ERROR_BAD_WRITE; 768 goto Error; 769 } 770 771 if (pad) { 772 const uint8_t pad_byte[1] = { 0 }; 773 if (!pic->writer(pad_byte, 1, pic)) { 774 err = VP8_ENC_ERROR_BAD_WRITE; 775 goto Error; 776 } 777 } 778 *coded_size = CHUNK_HEADER_SIZE + riff_size; 779 return VP8_ENC_OK; 780 781 Error: 782 return err; 783 } 784 785 // ----------------------------------------------------------------------------- 786 787 // Allocates the memory for argb (W x H) buffer, 2 rows of context for 788 // prediction and transform data. 789 static WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc, 790 int width, int height) { 791 WebPEncodingError err = VP8_ENC_OK; 792 const int tile_size = 1 << enc->transform_bits_; 793 const uint64_t image_size = width * height; 794 const uint64_t argb_scratch_size = tile_size * width + width; 795 const uint64_t transform_data_size = 796 (uint64_t)VP8LSubSampleSize(width, enc->transform_bits_) * 797 (uint64_t)VP8LSubSampleSize(height, enc->transform_bits_); 798 const uint64_t total_size = 799 image_size + argb_scratch_size + transform_data_size; 800 uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem)); 801 if (mem == NULL) { 802 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 803 goto Error; 804 } 805 enc->argb_ = mem; 806 mem += image_size; 807 enc->argb_scratch_ = mem; 808 mem += argb_scratch_size; 809 enc->transform_data_ = mem; 810 enc->current_width_ = width; 811 812 Error: 813 return err; 814 } 815 816 static void ApplyPalette(uint32_t* src, uint32_t* dst, 817 uint32_t src_stride, uint32_t dst_stride, 818 const uint32_t* palette, int palette_size, 819 int width, int height, int xbits, uint8_t* row) { 820 int i, x, y; 821 int use_LUT = 1; 822 for (i = 0; i < palette_size; ++i) { 823 if ((palette[i] & 0xffff00ffu) != 0) { 824 use_LUT = 0; 825 break; 826 } 827 } 828 829 if (use_LUT) { 830 int inv_palette[MAX_PALETTE_SIZE] = { 0 }; 831 for (i = 0; i < palette_size; ++i) { 832 const int color = (palette[i] >> 8) & 0xff; 833 inv_palette[color] = i; 834 } 835 for (y = 0; y < height; ++y) { 836 for (x = 0; x < width; ++x) { 837 const int color = (src[x] >> 8) & 0xff; 838 row[x] = inv_palette[color]; 839 } 840 VP8LBundleColorMap(row, width, xbits, dst); 841 src += src_stride; 842 dst += dst_stride; 843 } 844 } else { 845 // Use 1 pixel cache for ARGB pixels. 846 uint32_t last_pix = palette[0]; 847 int last_idx = 0; 848 for (y = 0; y < height; ++y) { 849 for (x = 0; x < width; ++x) { 850 const uint32_t pix = src[x]; 851 if (pix != last_pix) { 852 for (i = 0; i < palette_size; ++i) { 853 if (pix == palette[i]) { 854 last_idx = i; 855 last_pix = pix; 856 break; 857 } 858 } 859 } 860 row[x] = last_idx; 861 } 862 VP8LBundleColorMap(row, width, xbits, dst); 863 src += src_stride; 864 dst += dst_stride; 865 } 866 } 867 } 868 869 // Note: Expects "enc->palette_" to be set properly. 870 // Also, "enc->palette_" will be modified after this call and should not be used 871 // later. 872 static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, 873 VP8LEncoder* const enc, int quality) { 874 WebPEncodingError err = VP8_ENC_OK; 875 int i; 876 const WebPPicture* const pic = enc->pic_; 877 uint32_t* src = pic->argb; 878 uint32_t* dst; 879 const int width = pic->width; 880 const int height = pic->height; 881 uint32_t* const palette = enc->palette_; 882 const int palette_size = enc->palette_size_; 883 uint8_t* row = NULL; 884 int xbits; 885 886 // Replace each input pixel by corresponding palette index. 887 // This is done line by line. 888 if (palette_size <= 4) { 889 xbits = (palette_size <= 2) ? 3 : 2; 890 } else { 891 xbits = (palette_size <= 16) ? 1 : 0; 892 } 893 894 err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height); 895 if (err != VP8_ENC_OK) goto Error; 896 dst = enc->argb_; 897 898 row = WebPSafeMalloc((uint64_t)width, sizeof(*row)); 899 if (row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; 900 901 ApplyPalette(src, dst, pic->argb_stride, enc->current_width_, 902 palette, palette_size, width, height, xbits, row); 903 904 // Save palette to bitstream. 905 VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); 906 VP8LWriteBits(bw, 2, COLOR_INDEXING_TRANSFORM); 907 assert(palette_size >= 1); 908 VP8LWriteBits(bw, 8, palette_size - 1); 909 for (i = palette_size - 1; i >= 1; --i) { 910 palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); 911 } 912 if (!EncodeImageNoHuffman(bw, palette, palette_size, 1, quality)) { 913 err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 914 goto Error; 915 } 916 917 Error: 918 free(row); 919 return err; 920 } 921 922 // ----------------------------------------------------------------------------- 923 924 static int GetHistoBits(int method, int use_palette, int width, int height) { 925 const uint64_t hist_size = sizeof(VP8LHistogram); 926 // Make tile size a function of encoding method (Range: 0 to 6). 927 int histo_bits = (use_palette ? 9 : 7) - method; 928 while (1) { 929 const uint64_t huff_image_size = VP8LSubSampleSize(width, histo_bits) * 930 VP8LSubSampleSize(height, histo_bits) * 931 hist_size; 932 if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break; 933 ++histo_bits; 934 } 935 return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : 936 (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; 937 } 938 939 static void FinishEncParams(VP8LEncoder* const enc) { 940 const WebPConfig* const config = enc->config_; 941 const WebPPicture* const pic = enc->pic_; 942 const int method = config->method; 943 const float quality = config->quality; 944 const int use_palette = enc->use_palette_; 945 enc->transform_bits_ = (method < 4) ? 5 : (method > 4) ? 3 : 4; 946 enc->histo_bits_ = GetHistoBits(method, use_palette, pic->width, pic->height); 947 enc->cache_bits_ = (quality <= 25.f) ? 0 : 7; 948 } 949 950 // ----------------------------------------------------------------------------- 951 // VP8LEncoder 952 953 static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config, 954 const WebPPicture* const picture) { 955 VP8LEncoder* const enc = (VP8LEncoder*)calloc(1, sizeof(*enc)); 956 if (enc == NULL) { 957 WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY); 958 return NULL; 959 } 960 enc->config_ = config; 961 enc->pic_ = picture; 962 return enc; 963 } 964 965 static void VP8LEncoderDelete(VP8LEncoder* enc) { 966 free(enc->argb_); 967 free(enc); 968 } 969 970 // ----------------------------------------------------------------------------- 971 // Main call 972 973 WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, 974 const WebPPicture* const picture, 975 VP8LBitWriter* const bw) { 976 WebPEncodingError err = VP8_ENC_OK; 977 const int quality = (int)config->quality; 978 const int width = picture->width; 979 const int height = picture->height; 980 VP8LEncoder* const enc = VP8LEncoderNew(config, picture); 981 const size_t byte_position = VP8LBitWriterNumBytes(bw); 982 983 if (enc == NULL) { 984 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 985 goto Error; 986 } 987 988 // --------------------------------------------------------------------------- 989 // Analyze image (entropy, num_palettes etc) 990 991 if (!VP8LEncAnalyze(enc, config->image_hint)) { 992 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 993 goto Error; 994 } 995 996 FinishEncParams(enc); 997 998 if (enc->use_palette_) { 999 err = EncodePalette(bw, enc, quality); 1000 if (err != VP8_ENC_OK) goto Error; 1001 // Color cache is disabled for palette. 1002 enc->cache_bits_ = 0; 1003 } 1004 1005 // In case image is not packed. 1006 if (enc->argb_ == NULL) { 1007 int y; 1008 err = AllocateTransformBuffer(enc, width, height); 1009 if (err != VP8_ENC_OK) goto Error; 1010 for (y = 0; y < height; ++y) { 1011 memcpy(enc->argb_ + y * width, 1012 picture->argb + y * picture->argb_stride, 1013 width * sizeof(*enc->argb_)); 1014 } 1015 enc->current_width_ = width; 1016 } 1017 1018 // --------------------------------------------------------------------------- 1019 // Apply transforms and write transform data. 1020 1021 if (!EvalAndApplySubtractGreen(enc, enc->current_width_, height, bw)) { 1022 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1023 goto Error; 1024 } 1025 1026 if (enc->use_predict_) { 1027 if (!ApplyPredictFilter(enc, enc->current_width_, height, quality, bw)) { 1028 err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 1029 goto Error; 1030 } 1031 } 1032 1033 if (enc->use_cross_color_) { 1034 if (!ApplyCrossColorFilter(enc, enc->current_width_, height, quality, bw)) { 1035 err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 1036 goto Error; 1037 } 1038 } 1039 1040 VP8LWriteBits(bw, 1, !TRANSFORM_PRESENT); // No more transforms. 1041 1042 // --------------------------------------------------------------------------- 1043 // Estimate the color cache size. 1044 1045 if (enc->cache_bits_ > 0) { 1046 if (!VP8LCalculateEstimateForCacheSize(enc->argb_, enc->current_width_, 1047 height, &enc->cache_bits_)) { 1048 err = VP8_ENC_ERROR_INVALID_CONFIGURATION; 1049 goto Error; 1050 } 1051 } 1052 1053 // --------------------------------------------------------------------------- 1054 // Encode and write the transformed image. 1055 1056 if (!EncodeImageInternal(bw, enc->argb_, enc->current_width_, height, 1057 quality, enc->cache_bits_, enc->histo_bits_)) { 1058 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1059 goto Error; 1060 } 1061 1062 if (picture->stats != NULL) { 1063 WebPAuxStats* const stats = picture->stats; 1064 stats->lossless_features = 0; 1065 if (enc->use_predict_) stats->lossless_features |= 1; 1066 if (enc->use_cross_color_) stats->lossless_features |= 2; 1067 if (enc->use_subtract_green_) stats->lossless_features |= 4; 1068 if (enc->use_palette_) stats->lossless_features |= 8; 1069 stats->histogram_bits = enc->histo_bits_; 1070 stats->transform_bits = enc->transform_bits_; 1071 stats->cache_bits = enc->cache_bits_; 1072 stats->palette_size = enc->palette_size_; 1073 stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position); 1074 } 1075 1076 Error: 1077 VP8LEncoderDelete(enc); 1078 return err; 1079 } 1080 1081 int VP8LEncodeImage(const WebPConfig* const config, 1082 const WebPPicture* const picture) { 1083 int width, height; 1084 int has_alpha; 1085 size_t coded_size; 1086 int percent = 0; 1087 WebPEncodingError err = VP8_ENC_OK; 1088 VP8LBitWriter bw; 1089 1090 if (picture == NULL) return 0; 1091 1092 if (config == NULL || picture->argb == NULL) { 1093 err = VP8_ENC_ERROR_NULL_PARAMETER; 1094 WebPEncodingSetError(picture, err); 1095 return 0; 1096 } 1097 1098 width = picture->width; 1099 height = picture->height; 1100 if (!VP8LBitWriterInit(&bw, (width * height) >> 1)) { 1101 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1102 goto Error; 1103 } 1104 1105 if (!WebPReportProgress(picture, 1, &percent)) { 1106 UserAbort: 1107 err = VP8_ENC_ERROR_USER_ABORT; 1108 goto Error; 1109 } 1110 // Reset stats (for pure lossless coding) 1111 if (picture->stats != NULL) { 1112 WebPAuxStats* const stats = picture->stats; 1113 memset(stats, 0, sizeof(*stats)); 1114 stats->PSNR[0] = 99.f; 1115 stats->PSNR[1] = 99.f; 1116 stats->PSNR[2] = 99.f; 1117 stats->PSNR[3] = 99.f; 1118 stats->PSNR[4] = 99.f; 1119 } 1120 1121 // Write image size. 1122 if (!WriteImageSize(picture, &bw)) { 1123 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1124 goto Error; 1125 } 1126 1127 has_alpha = WebPPictureHasTransparency(picture); 1128 // Write the non-trivial Alpha flag and lossless version. 1129 if (!WriteRealAlphaAndVersion(&bw, has_alpha)) { 1130 err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1131 goto Error; 1132 } 1133 1134 if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort; 1135 1136 // Encode main image stream. 1137 err = VP8LEncodeStream(config, picture, &bw); 1138 if (err != VP8_ENC_OK) goto Error; 1139 1140 // TODO(skal): have a fine-grained progress report in VP8LEncodeStream(). 1141 if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort; 1142 1143 // Finish the RIFF chunk. 1144 err = WriteImage(picture, &bw, &coded_size); 1145 if (err != VP8_ENC_OK) goto Error; 1146 1147 if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort; 1148 1149 // Save size. 1150 if (picture->stats != NULL) { 1151 picture->stats->coded_size += (int)coded_size; 1152 picture->stats->lossless_size = (int)coded_size; 1153 } 1154 1155 if (picture->extra_info != NULL) { 1156 const int mb_w = (width + 15) >> 4; 1157 const int mb_h = (height + 15) >> 4; 1158 memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info)); 1159 } 1160 1161 Error: 1162 if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY; 1163 VP8LBitWriterDestroy(&bw); 1164 if (err != VP8_ENC_OK) { 1165 WebPEncodingSetError(picture, err); 1166 return 0; 1167 } 1168 return 1; 1169 } 1170 1171 //------------------------------------------------------------------------------ 1172 1173 #if defined(__cplusplus) || defined(c_plusplus) 1174 } // extern "C" 1175 #endif 1176
