src/third_party/libwebp/enc/vp8l.c

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