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