src/SDL2/external/libwebp-0.3.0/src/enc/vp8l.c

   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@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 EncodePalette()?
  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   // Free combined histograms.
 567   free(histogram_image);
 568   histogram_image = NULL;
 569
 570   // Color Cache parameters.
 571   VP8LWriteBits(bw, 1, use_color_cache);
 572   if (use_color_cache) {
 573     VP8LWriteBits(bw, 4, cache_bits);
 574   }
 575
 576   // Huffman image + meta huffman.
 577   {
 578     const int write_histogram_image = (histogram_image_size > 1);
 579     VP8LWriteBits(bw, 1, write_histogram_image);
 580     if (write_histogram_image) {
 581       uint32_t* const histogram_argb =
 582           (uint32_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize,
 583                                     sizeof(*histogram_argb));
 584       int max_index = 0;
 585       uint32_t i;
 586       if (histogram_argb == NULL) goto Error;
 587       for (i = 0; i < histogram_image_xysize; ++i) {
 588         const int symbol_index = histogram_symbols[i] & 0xffff;
 589         histogram_argb[i] = 0xff000000 | (symbol_index << 8);
 590         if (symbol_index >= max_index) {
 591           max_index = symbol_index + 1;
 592         }
 593       }
 594       histogram_image_size = max_index;
 595
 596       VP8LWriteBits(bw, 3, histogram_bits - 2);
 597       ok = EncodeImageNoHuffman(bw, histogram_argb,
 598                                 VP8LSubSampleSize(width, histogram_bits),
 599                                 VP8LSubSampleSize(height, histogram_bits),
 600                                 quality);
 601       free(histogram_argb);
 602       if (!ok) goto Error;
 603     }
 604   }
 605
 606   // Store Huffman codes.
 607   {
 608     int i;
 609     for (i = 0; i < 5 * histogram_image_size; ++i) {
 610       HuffmanTreeCode* const codes = &huffman_codes[i];
 611       if (!StoreHuffmanCode(bw, codes)) goto Error;
 612       ClearHuffmanTreeIfOnlyOneSymbol(codes);
 613     }
 614   }
 615
 616   // Store actual literals.
 617   StoreImageToBitMask(bw, width, histogram_bits, &refs,
 618                       histogram_symbols, huffman_codes);
 619   ok = 1;
 620
 621  Error:
 622   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 static void ApplyPalette(uint32_t* src, uint32_t* dst,
 815                          uint32_t src_stride, uint32_t dst_stride,
 816                          const uint32_t* palette, int palette_size,
 817                          int width, int height, int xbits, uint8_t* row) {
 818   int i, x, y;
 819   int use_LUT = 1;
 820   for (i = 0; i < palette_size; ++i) {
 821     if ((palette[i] & 0xffff00ffu) != 0) {
 822       use_LUT = 0;
 823       break;
 824     }
 825   }
 826
 827   if (use_LUT) {
 828     uint8_t inv_palette[MAX_PALETTE_SIZE] = { 0 };
 829     for (i = 0; i < palette_size; ++i) {
 830       const int color = (palette[i] >> 8) & 0xff;
 831       inv_palette[color] = i;
 832     }
 833     for (y = 0; y < height; ++y) {
 834       for (x = 0; x < width; ++x) {
 835         const int color = (src[x] >> 8) & 0xff;
 836         row[x] = inv_palette[color];
 837       }
 838       VP8LBundleColorMap(row, width, xbits, dst);
 839       src += src_stride;
 840       dst += dst_stride;
 841     }
 842   } else {
 843     // Use 1 pixel cache for ARGB pixels.
 844     uint32_t last_pix = palette[0];
 845     int last_idx = 0;
 846     for (y = 0; y < height; ++y) {
 847       for (x = 0; x < width; ++x) {
 848         const uint32_t pix = src[x];
 849         if (pix != last_pix) {
 850           for (i = 0; i < palette_size; ++i) {
 851             if (pix == palette[i]) {
 852               last_idx = i;
 853               last_pix = pix;
 854               break;
 855             }
 856           }
 857         }
 858         row[x] = last_idx;
 859       }
 860       VP8LBundleColorMap(row, width, xbits, dst);
 861       src += src_stride;
 862       dst += dst_stride;
 863     }
 864   }
 865 }
 866
 867 // Note: Expects "enc->palette_" to be set properly.
 868 // Also, "enc->palette_" will be modified after this call and should not be used
 869 // later.
 870 static WebPEncodingError EncodePalette(VP8LBitWriter* const bw,
 871                                        VP8LEncoder* const enc, int quality) {
 872   WebPEncodingError err = VP8_ENC_OK;
 873   int i;
 874   const WebPPicture* const pic = enc->pic_;
 875   uint32_t* src = pic->argb;
 876   uint32_t* dst;
 877   const int width = pic->width;
 878   const int height = pic->height;
 879   uint32_t* const palette = enc->palette_;
 880   const int palette_size = enc->palette_size_;
 881   uint8_t* row = NULL;
 882   int xbits;
 883
 884   // Replace each input pixel by corresponding palette index.
 885   // This is done line by line.
 886   if (palette_size <= 4) {
 887     xbits = (palette_size <= 2) ? 3 : 2;
 888   } else {
 889     xbits = (palette_size <= 16) ? 1 : 0;
 890   }
 891
 892   err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height);
 893   if (err != VP8_ENC_OK) goto Error;
 894   dst = enc->argb_;
 895
 896   row = WebPSafeMalloc((uint64_t)width, sizeof(*row));
 897   if (row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY;
 898
 899   ApplyPalette(src, dst, pic->argb_stride, enc->current_width_,
 900                palette, palette_size, width, height, xbits, row);
 901
 902   // Save palette to bitstream.
 903   VP8LWriteBits(bw, 1, TRANSFORM_PRESENT);
 904   VP8LWriteBits(bw, 2, COLOR_INDEXING_TRANSFORM);
 905   assert(palette_size >= 1);
 906   VP8LWriteBits(bw, 8, palette_size - 1);
 907   for (i = palette_size - 1; i >= 1; --i) {
 908     palette[i] = VP8LSubPixels(palette[i], palette[i - 1]);
 909   }
 910   if (!EncodeImageNoHuffman(bw, palette, palette_size, 1, quality)) {
 911     err = VP8_ENC_ERROR_INVALID_CONFIGURATION;
 912     goto Error;
 913   }
 914
 915  Error:
 916   free(row);
 917   return err;
 918 }
 919
 920 // -----------------------------------------------------------------------------
 921
 922 static int GetHistoBits(int method, int use_palette, int width, int height) {
 923   const uint64_t hist_size = sizeof(VP8LHistogram);
 924   // Make tile size a function of encoding method (Range: 0 to 6).
 925   int histo_bits = (use_palette ? 9 : 7) - method;
 926   while (1) {
 927     const uint64_t huff_image_size = VP8LSubSampleSize(width, histo_bits) *
 928                                      VP8LSubSampleSize(height, histo_bits) *
 929                                      hist_size;
 930     if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break;
 931     ++histo_bits;
 932   }
 933   return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS :
 934          (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits;
 935 }
 936
 937 static void FinishEncParams(VP8LEncoder* const enc) {
 938   const WebPConfig* const config = enc->config_;
 939   const WebPPicture* const pic = enc->pic_;
 940   const int method = config->method;
 941   const float quality = config->quality;
 942   const int use_palette = enc->use_palette_;
 943   enc->transform_bits_ = (method < 4) ? 5 : (method > 4) ? 3 : 4;
 944   enc->histo_bits_ = GetHistoBits(method, use_palette, pic->width, pic->height);
 945   enc->cache_bits_ = (quality <= 25.f) ? 0 : 7;
 946 }
 947
 948 // -----------------------------------------------------------------------------
 949 // VP8LEncoder
 950
 951 static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config,
 952                                    const WebPPicture* const picture) {
 953   VP8LEncoder* const enc = (VP8LEncoder*)calloc(1, sizeof(*enc));
 954   if (enc == NULL) {
 955     WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
 956     return NULL;
 957   }
 958   enc->config_ = config;
 959   enc->pic_ = picture;
 960   return enc;
 961 }
 962
 963 static void VP8LEncoderDelete(VP8LEncoder* enc) {
 964   free(enc->argb_);
 965   free(enc);
 966 }
 967
 968 // -----------------------------------------------------------------------------
 969 // Main call
 970
 971 WebPEncodingError VP8LEncodeStream(const WebPConfig* const config,
 972                                    const WebPPicture* const picture,
 973                                    VP8LBitWriter* const bw) {
 974   WebPEncodingError err = VP8_ENC_OK;
 975   const int quality = (int)config->quality;
 976   const int width = picture->width;
 977   const int height = picture->height;
 978   VP8LEncoder* const enc = VP8LEncoderNew(config, picture);
 979   const size_t byte_position = VP8LBitWriterNumBytes(bw);
 980
 981   if (enc == NULL) {
 982     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
 983     goto Error;
 984   }
 985
 986   // ---------------------------------------------------------------------------
 987   // Analyze image (entropy, num_palettes etc)
 988
 989   if (!VP8LEncAnalyze(enc, config->image_hint)) {
 990     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
 991     goto Error;
 992   }
 993
 994   FinishEncParams(enc);
 995
 996   if (enc->use_palette_) {
 997     err = EncodePalette(bw, enc, quality);
 998     if (err != VP8_ENC_OK) goto Error;
 999     // Color cache is disabled for palette.
1000     enc->cache_bits_ = 0;
1001   }
1002
1003   // In case image is not packed.
1004   if (enc->argb_ == NULL) {
1005     int y;
1006     err = AllocateTransformBuffer(enc, width, height);
1007     if (err != VP8_ENC_OK) goto Error;
1008     for (y = 0; y < height; ++y) {
1009       memcpy(enc->argb_ + y * width,
1010              picture->argb + y * picture->argb_stride,
1011              width * sizeof(*enc->argb_));
1012     }
1013     enc->current_width_ = width;
1014   }
1015
1016   // ---------------------------------------------------------------------------
1017   // Apply transforms and write transform data.
1018
1019   if (!EvalAndApplySubtractGreen(enc, enc->current_width_, height, bw)) {
1020     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1021     goto Error;
1022   }
1023
1024   if (enc->use_predict_) {
1025     if (!ApplyPredictFilter(enc, enc->current_width_, height, quality, bw)) {
1026       err = VP8_ENC_ERROR_INVALID_CONFIGURATION;
1027       goto Error;
1028     }
1029   }
1030
1031   if (enc->use_cross_color_) {
1032     if (!ApplyCrossColorFilter(enc, enc->current_width_, height, quality, bw)) {
1033       err = VP8_ENC_ERROR_INVALID_CONFIGURATION;
1034       goto Error;
1035     }
1036   }
1037
1038   VP8LWriteBits(bw, 1, !TRANSFORM_PRESENT);  // No more transforms.
1039
1040   // ---------------------------------------------------------------------------
1041   // Estimate the color cache size.
1042
1043   if (enc->cache_bits_ > 0) {
1044     if (!VP8LCalculateEstimateForCacheSize(enc->argb_, enc->current_width_,
1045                                            height, &enc->cache_bits_)) {
1046       err = VP8_ENC_ERROR_INVALID_CONFIGURATION;
1047       goto Error;
1048     }
1049   }
1050
1051   // ---------------------------------------------------------------------------
1052   // Encode and write the transformed image.
1053
1054   if (!EncodeImageInternal(bw, enc->argb_, enc->current_width_, height,
1055                            quality, enc->cache_bits_, enc->histo_bits_)) {
1056     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1057     goto Error;
1058   }
1059
1060   if (picture->stats != NULL) {
1061     WebPAuxStats* const stats = picture->stats;
1062     stats->lossless_features = 0;
1063     if (enc->use_predict_) stats->lossless_features |= 1;
1064     if (enc->use_cross_color_) stats->lossless_features |= 2;
1065     if (enc->use_subtract_green_) stats->lossless_features |= 4;
1066     if (enc->use_palette_) stats->lossless_features |= 8;
1067     stats->histogram_bits = enc->histo_bits_;
1068     stats->transform_bits = enc->transform_bits_;
1069     stats->cache_bits = enc->cache_bits_;
1070     stats->palette_size = enc->palette_size_;
1071     stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position);
1072   }
1073
1074  Error:
1075   VP8LEncoderDelete(enc);
1076   return err;
1077 }
1078
1079 int VP8LEncodeImage(const WebPConfig* const config,
1080                     const WebPPicture* const picture) {
1081   int width, height;
1082   int has_alpha;
1083   size_t coded_size;
1084   int percent = 0;
1085   WebPEncodingError err = VP8_ENC_OK;
1086   VP8LBitWriter bw;
1087
1088   if (picture == NULL) return 0;
1089
1090   if (config == NULL || picture->argb == NULL) {
1091     err = VP8_ENC_ERROR_NULL_PARAMETER;
1092     WebPEncodingSetError(picture, err);
1093     return 0;
1094   }
1095
1096   width = picture->width;
1097   height = picture->height;
1098   if (!VP8LBitWriterInit(&bw, (width * height) >> 1)) {
1099     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1100     goto Error;
1101   }
1102
1103   if (!WebPReportProgress(picture, 1, &percent)) {
1104  UserAbort:
1105     err = VP8_ENC_ERROR_USER_ABORT;
1106     goto Error;
1107   }
1108   // Reset stats (for pure lossless coding)
1109   if (picture->stats != NULL) {
1110     WebPAuxStats* const stats = picture->stats;
1111     memset(stats, 0, sizeof(*stats));
1112     stats->PSNR[0] = 99.f;
1113     stats->PSNR[1] = 99.f;
1114     stats->PSNR[2] = 99.f;
1115     stats->PSNR[3] = 99.f;
1116     stats->PSNR[4] = 99.f;
1117   }
1118
1119   // Write image size.
1120   if (!WriteImageSize(picture, &bw)) {
1121     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1122     goto Error;
1123   }
1124
1125   has_alpha = WebPPictureHasTransparency(picture);
1126   // Write the non-trivial Alpha flag and lossless version.
1127   if (!WriteRealAlphaAndVersion(&bw, has_alpha)) {
1128     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1129     goto Error;
1130   }
1131
1132   if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort;
1133
1134   // Encode main image stream.
1135   err = VP8LEncodeStream(config, picture, &bw);
1136   if (err != VP8_ENC_OK) goto Error;
1137
1138   // TODO(skal): have a fine-grained progress report in VP8LEncodeStream().
1139   if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort;
1140
1141   // Finish the RIFF chunk.
1142   err = WriteImage(picture, &bw, &coded_size);
1143   if (err != VP8_ENC_OK) goto Error;
1144
1145   if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort;
1146
1147   // Save size.
1148   if (picture->stats != NULL) {
1149     picture->stats->coded_size += (int)coded_size;
1150     picture->stats->lossless_size = (int)coded_size;
1151   }
1152
1153   if (picture->extra_info != NULL) {
1154     const int mb_w = (width + 15) >> 4;
1155     const int mb_h = (height + 15) >> 4;
1156     memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info));
1157   }
1158
1159  Error:
1160   if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1161   VP8LBitWriterDestroy(&bw);
1162   if (err != VP8_ENC_OK) {
1163     WebPEncodingSetError(picture, err);
1164     return 0;
1165   }
1166   return 1;
1167 }
1168
1169 //------------------------------------------------------------------------------
1170
1171 #if defined(__cplusplus) || defined(c_plusplus)
1172 }    // extern "C"
1173 #endif