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