libwebp: update snapshot to v0.3.0-rc6

third_party/libwebp/enc/vp8l.c

 // Copyright 2012 Google Inc. All Rights Reserved.
 //
 // This code is licensed under the same terms as WebM:
 //  Software License Agreement:  http://www.webmproject.org/license/software/
 //  Additional IP Rights Grant:  http://www.webmproject.org/license/additional/
 // -----------------------------------------------------------------------------
 //
 // main entry for the lossless encoder.
 //
 // Author: Vikas Arora (vikaas.arora@gmail.com)
@@ skipping 11 matching lines @@
 #include "../utils/huffman_encode.h"
 #include "../utils/utils.h"
 #include "../webp/format_constants.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
 #define PALETTE_KEY_RIGHT_SHIFT   22  // Key for 1K buffer.
 #define MAX_HUFF_IMAGE_SIZE       (16 * 1024 * 1024)
+#define MAX_COLORS_FOR_GRAPH      64
 
 // -----------------------------------------------------------------------------
 // Palette
 
 static int CompareColors(const void* p1, const void* p2) {
   const uint32_t a = *(const uint32_t*)p1;
   const uint32_t b = *(const uint32_t*)p2;
-  return (a < b) ? -1 : (a > b) ? 1 : 0;
+  assert(a != b);
+  return (a < b) ? -1 : 1;
 }
 
 // If number of colors in the image is less than or equal to MAX_PALETTE_SIZE,
 // creates a palette and returns true, else returns false.
 static int AnalyzeAndCreatePalette(const WebPPicture* const pic,
                                    uint32_t palette[MAX_PALETTE_SIZE],
                                    int* const palette_size) {
   int i, x, y, key;
   int num_colors = 0;
   uint8_t in_use[MAX_PALETTE_SIZE * 4] = { 0 };
@@ skipping 41 matching lines @@
       palette[num_colors] = colors[i];
       ++num_colors;
     }
   }
 
   qsort(palette, num_colors, sizeof(*palette), CompareColors);
   *palette_size = num_colors;
   return 1;
 }
 
-static int AnalyzeEntropy(const WebPPicture* const pic,
+static int AnalyzeEntropy(const uint32_t* argb,
+                          int width, int height, int argb_stride,
                           double* const nonpredicted_bits,
                           double* const predicted_bits) {
   int x, y;
-  const uint32_t* argb = pic->argb;
   const uint32_t* last_line = NULL;
   uint32_t last_pix = argb[0];    // so we're sure that pix_diff == 0
 
   VP8LHistogram* nonpredicted = NULL;
   VP8LHistogram* predicted =
       (VP8LHistogram*)malloc(2 * sizeof(*predicted));
   if (predicted == NULL) return 0;
   nonpredicted = predicted + 1;
 
   VP8LHistogramInit(predicted, 0);
   VP8LHistogramInit(nonpredicted, 0);
-  for (y = 0; y < pic->height; ++y) {
-    for (x = 0; x < pic->width; ++x) {
+  for (y = 0; y < height; ++y) {
+    for (x = 0; x < width; ++x) {
       const uint32_t pix = argb[x];
       const uint32_t pix_diff = VP8LSubPixels(pix, last_pix);
       if (pix_diff == 0) continue;
       if (last_line != NULL && pix == last_line[x]) {
         continue;
       }
       last_pix = pix;
       {
         const PixOrCopy pix_token = PixOrCopyCreateLiteral(pix);
         const PixOrCopy pix_diff_token = PixOrCopyCreateLiteral(pix_diff);
         VP8LHistogramAddSinglePixOrCopy(nonpredicted, &pix_token);
         VP8LHistogramAddSinglePixOrCopy(predicted, &pix_diff_token);
       }
     }
     last_line = argb;
-    argb += pic->argb_stride;
+    argb += argb_stride;
   }
   *nonpredicted_bits = VP8LHistogramEstimateBitsBulk(nonpredicted);
   *predicted_bits = VP8LHistogramEstimateBitsBulk(predicted);
   free(predicted);
   return 1;
 }
 
 static int VP8LEncAnalyze(VP8LEncoder* const enc, WebPImageHint image_hint) {
   const WebPPicture* const pic = enc->pic_;
   assert(pic != NULL && pic->argb != NULL);
 
-  enc->use_palette_ = (image_hint == WEBP_HINT_GRAPH) ? 0 :
+  enc->use_palette_ =
       AnalyzeAndCreatePalette(pic, enc->palette_, &enc->palette_size_);
+
+  if (image_hint == WEBP_HINT_GRAPH) {
+    if (enc->use_palette_ && enc->palette_size_ < MAX_COLORS_FOR_GRAPH) {
+      enc->use_palette_ = 0;
+    }
+  }
+
   if (!enc->use_palette_) {
-    if (image_hint == WEBP_HINT_DEFAULT) {
+    if (image_hint == WEBP_HINT_PHOTO) {
+      enc->use_predict_ = 1;
+      enc->use_cross_color_ = 1;
+    } else {
       double non_pred_entropy, pred_entropy;
-      if (!AnalyzeEntropy(pic, &non_pred_entropy, &pred_entropy)) {
+      if (!AnalyzeEntropy(pic->argb, pic->width, pic->height, pic->argb_stride,
+                          &non_pred_entropy, &pred_entropy)) {
         return 0;
       }
-
       if (pred_entropy < 0.95 * non_pred_entropy) {
         enc->use_predict_ = 1;
+        // TODO(vikasa): Observed some correlation of cross_color transform with
+        // predict. Need to investigate this further and add separate heuristic
+        // for setting use_cross_color flag.
         enc->use_cross_color_ = 1;
       }
-    } else if (image_hint == WEBP_HINT_PHOTO) {
-      enc->use_predict_ = 1;
-      enc->use_cross_color_ = 1;
     }
   }
+
   return 1;
 }
 
 static int GetHuffBitLengthsAndCodes(
     const VP8LHistogramSet* const histogram_image,
     HuffmanTreeCode* const huffman_codes) {
   int i, k;
   int ok = 1;
   uint64_t total_length_size = 0;
   uint8_t* mem_buf = NULL;
@@ skipping 27 matching lines @@
     for (i = 0; i < 5 * histogram_image_size; ++i) {
       const int bit_length = huffman_codes[i].num_symbols;
       huffman_codes[i].codes = codes;
       huffman_codes[i].code_lengths = lengths;
       codes += bit_length;
       lengths += bit_length;
     }
   }
 
   // Create Huffman trees.
-  for (i = 0; i < histogram_image_size; ++i) {
+  for (i = 0; ok && (i < histogram_image_size); ++i) {
     HuffmanTreeCode* const codes = &huffman_codes[5 * i];
     VP8LHistogram* const histo = histogram_image->histograms[i];
     ok = ok && VP8LCreateHuffmanTree(histo->literal_, 15, codes + 0);
     ok = ok && VP8LCreateHuffmanTree(histo->red_, 15, codes + 1);
     ok = ok && VP8LCreateHuffmanTree(histo->blue_, 15, codes + 2);
     ok = ok && VP8LCreateHuffmanTree(histo->alpha_, 15, codes + 3);
     ok = ok && VP8LCreateHuffmanTree(histo->distance_, 15, codes + 4);
   }
 
  End:
-  if (!ok) free(mem_buf);
+  if (!ok) {
+    free(mem_buf);
+    // If one VP8LCreateHuffmanTree() above fails, we need to clean up behind.
+    memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes));
+  }
   return ok;
 }
 
 static void StoreHuffmanTreeOfHuffmanTreeToBitMask(
     VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) {
   // RFC 1951 will calm you down if you are worried about this funny sequence.
   // This sequence is tuned from that, but more weighted for lower symbol count,
   // and more spiking histograms.
   static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = {
     17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
@@ skipping 154 matching lines @@
     if (count == 2) {
       VP8LWriteBits(bw, 8, symbols[1]);
     }
     return 1;
   } else {
     return StoreFullHuffmanCode(bw, huffman_code);
   }
 }
 
 static void WriteHuffmanCode(VP8LBitWriter* const bw,
-                             const HuffmanTreeCode* const code, int index) {
-  const int depth = code->code_lengths[index];
-  const int symbol = code->codes[index];
+                             const HuffmanTreeCode* const code,
+                             int code_index) {
+  const int depth = code->code_lengths[code_index];
+  const int symbol = code->codes[code_index];
   VP8LWriteBits(bw, depth, symbol);
 }
 
 static void StoreImageToBitMask(
     VP8LBitWriter* const bw, int width, int histo_bits,
     const VP8LBackwardRefs* const refs,
     const uint16_t* histogram_symbols,
     const HuffmanTreeCode* const huffman_codes) {
   // x and y trace the position in the image.
   int x = 0;
@@ skipping 100 matching lines @@
       VP8LAllocateHistogramSet(histogram_image_xysize, 0);
   int histogram_image_size = 0;
   size_t bit_array_size = 0;
   HuffmanTreeCode* huffman_codes = NULL;
   VP8LBackwardRefs refs;
   uint16_t* const histogram_symbols =
       (uint16_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize,
                                 sizeof(*histogram_symbols));
   assert(histogram_bits >= MIN_HUFFMAN_BITS);
   assert(histogram_bits <= MAX_HUFFMAN_BITS);
-  if (histogram_image == NULL || histogram_symbols == NULL) goto Error;
+
+  if (histogram_image == NULL || histogram_symbols == NULL) {
+    free(histogram_image);
+    free(histogram_symbols);
+    return 0;
+  }
 
   // Calculate backward references from ARGB image.
   if (!VP8LGetBackwardReferences(width, height, argb, quality, cache_bits,
                                  use_2d_locality, &refs)) {
     goto Error;
   }
   // Build histogram image and symbols from backward references.
   if (!VP8LGetHistoImageSymbols(width, height, &refs,
                                 quality, histogram_bits, cache_bits,
                                 histogram_image,
                                 histogram_symbols)) {
     goto Error;
   }
   // Create Huffman bit lengths and codes for each histogram image.
   histogram_image_size = histogram_image->size;
   bit_array_size = 5 * histogram_image_size;
   huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size,
                                                    sizeof(*huffman_codes));
   if (huffman_codes == NULL ||
       !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) {
     goto Error;
   }
+  // Free combined histograms.
+  free(histogram_image);
+  histogram_image = NULL;
 
   // Color Cache parameters.
   VP8LWriteBits(bw, 1, use_color_cache);
   if (use_color_cache) {
     VP8LWriteBits(bw, 4, cache_bits);
   }
 
   // Huffman image + meta huffman.
   {
     const int write_histogram_image = (histogram_image_size > 1);
     VP8LWriteBits(bw, 1, write_histogram_image);
     if (write_histogram_image) {
       uint32_t* const histogram_argb =
           (uint32_t*)WebPSafeMalloc((uint64_t)histogram_image_xysize,
                                     sizeof(*histogram_argb));
       int max_index = 0;
       uint32_t i;
       if (histogram_argb == NULL) goto Error;
       for (i = 0; i < histogram_image_xysize; ++i) {
-        const int index = histogram_symbols[i] & 0xffff;
-        histogram_argb[i] = 0xff000000 | (index << 8);
-        if (index >= max_index) {
-          max_index = index + 1;
+        const int symbol_index = histogram_symbols[i] & 0xffff;
+        histogram_argb[i] = 0xff000000 | (symbol_index << 8);
+        if (symbol_index >= max_index) {
+          max_index = symbol_index + 1;
         }
       }
       histogram_image_size = max_index;
 
       VP8LWriteBits(bw, 3, histogram_bits - 2);
       ok = EncodeImageNoHuffman(bw, histogram_argb,
                                 VP8LSubSampleSize(width, histogram_bits),
                                 VP8LSubSampleSize(height, histogram_bits),
                                 quality);
       free(histogram_argb);
       if (!ok) goto Error;
     }
   }
 
   // Store Huffman codes.
   {
     int i;
     for (i = 0; i < 5 * histogram_image_size; ++i) {
       HuffmanTreeCode* const codes = &huffman_codes[i];
       if (!StoreHuffmanCode(bw, codes)) goto Error;
       ClearHuffmanTreeIfOnlyOneSymbol(codes);
     }
   }
-  // Free combined histograms.
-  free(histogram_image);
-  histogram_image = NULL;
 
   // Store actual literals.
   StoreImageToBitMask(bw, width, histogram_bits, &refs,
                       histogram_symbols, huffman_codes);
   ok = 1;
 
  Error:
-  if (!ok) free(histogram_image);
+  free(histogram_image);
 
   VP8LClearBackwardRefs(&refs);
   if (huffman_codes != NULL) {
     free(huffman_codes->codes);
     free(huffman_codes);
   }
   free(histogram_symbols);
   return ok;
 }
 
@@ skipping 77 matching lines @@
   VP8LWriteBits(bw, 3, ccolor_transform_bits - 2);
   if (!EncodeImageNoHuffman(bw, enc->transform_data_,
                             transform_width, transform_height, quality)) {
     return 0;
   }
   return 1;
 }
 
 // -----------------------------------------------------------------------------
 
-static void PutLE32(uint8_t* const data, uint32_t val) {
-  data[0] = (val >>  0) & 0xff;
-  data[1] = (val >>  8) & 0xff;
-  data[2] = (val >> 16) & 0xff;
-  data[3] = (val >> 24) & 0xff;
-}
-
 static WebPEncodingError WriteRiffHeader(const WebPPicture* const pic,
                                          size_t riff_size, size_t vp8l_size) {
   uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = {
     'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P',
     'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE,
   };
   PutLE32(riff + TAG_SIZE, (uint32_t)riff_size);
   PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size);
   if (!pic->writer(riff, sizeof(riff), pic)) {
     return VP8_ENC_ERROR_BAD_WRITE;
@@ skipping 74 matching lines @@
   mem += image_size;
   enc->argb_scratch_ = mem;
   mem += argb_scratch_size;
   enc->transform_data_ = mem;
   enc->current_width_ = width;
 
  Error:
   return err;
 }
 
-// Bundles multiple (2, 4 or 8) pixels into a single pixel.
-// Returns the new xsize.
-static void BundleColorMap(const WebPPicture* const pic,
-                           int xbits, uint32_t* bundled_argb, int xs) {
-  int y;
-  const int bit_depth = 1 << (3 - xbits);
-  uint32_t code = 0;
-  const uint32_t* argb = pic->argb;
-  const int width = pic->width;
-  const int height = pic->height;
-
-  for (y = 0; y < height; ++y) {
-    int x;
+// Bundles multiple (1, 2, 4 or 8) pixels into a single pixel.
+static void BundleColorMap(const uint8_t* const row, int width,
+                           int xbits, uint32_t* const dst) {
+  int x;
+  if (xbits > 0) {
+    const int bit_depth = 1 << (3 - xbits);
+    const int mask = (1 << xbits) - 1;
+    uint32_t code = 0xff000000;
     for (x = 0; x < width; ++x) {
-      const int mask = (1 << xbits) - 1;
       const int xsub = x & mask;
       if (xsub == 0) {
-        code = 0;
+        code = 0xff000000;
       }
-      // TODO(vikasa): simplify the bundling logic.
-      code |= (argb[x] & 0xff00) << (bit_depth * xsub);
-      bundled_argb[y * xs + (x >> xbits)] = 0xff000000 | code;
+      code |= row[x] << (8 + bit_depth * xsub);
+      dst[x >> xbits] = code;
     }
-    argb += pic->argb_stride;
+  } else {
+    for (x = 0; x < width; ++x) dst[x] = 0xff000000 | (row[x] << 8);
   }
 }
 
 // Note: Expects "enc->palette_" to be set properly.
 // Also, "enc->palette_" will be modified after this call and should not be used
 // later.
 static WebPEncodingError ApplyPalette(VP8LBitWriter* const bw,
                                       VP8LEncoder* const enc, int quality) {
   WebPEncodingError err = VP8_ENC_OK;
   int i, x, y;
   const WebPPicture* const pic = enc->pic_;
-  uint32_t* argb = pic->argb;
+  uint32_t* src = pic->argb;
+  uint32_t* dst;
   const int width = pic->width;
   const int height = pic->height;
   uint32_t* const palette = enc->palette_;
   const int palette_size = enc->palette_size_;
+  uint8_t* row = NULL;
+  int xbits;
 
   // Replace each input pixel by corresponding palette index.
+  // This is done line by line.
+  if (palette_size <= 4) {
+    xbits = (palette_size <= 2) ? 3 : 2;
+  } else {
+    xbits = (palette_size <= 16) ? 1 : 0;
+  }
+
+  err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height);
+  if (err != VP8_ENC_OK) goto Error;
+  dst = enc->argb_;
+
+  row = WebPSafeMalloc((uint64_t)width, sizeof(*row));
+  if (row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY;
+
   for (y = 0; y < height; ++y) {
     for (x = 0; x < width; ++x) {
-      const uint32_t pix = argb[x];
+      const uint32_t pix = src[x];
       for (i = 0; i < palette_size; ++i) {
         if (pix == palette[i]) {
-          argb[x] = 0xff000000u | (i << 8);
+          row[x] = i;
           break;
         }
       }
     }
-    argb += pic->argb_stride;
+    BundleColorMap(row, width, xbits, dst);
+    src += pic->argb_stride;
+    dst += enc->current_width_;
   }
 
   // Save palette to bitstream.
   VP8LWriteBits(bw, 1, TRANSFORM_PRESENT);
   VP8LWriteBits(bw, 2, COLOR_INDEXING_TRANSFORM);
   assert(palette_size >= 1);
   VP8LWriteBits(bw, 8, palette_size - 1);
   for (i = palette_size - 1; i >= 1; --i) {
     palette[i] = VP8LSubPixels(palette[i], palette[i - 1]);
   }
   if (!EncodeImageNoHuffman(bw, palette, palette_size, 1, quality)) {
     err = VP8_ENC_ERROR_INVALID_CONFIGURATION;
     goto Error;
   }
 
-  if (palette_size <= 16) {
-    // Image can be packed (multiple pixels per uint32_t).
-    int xbits = 1;
-    if (palette_size <= 2) {
-      xbits = 3;
-    } else if (palette_size <= 4) {
-      xbits = 2;
-    }
-    err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height);
-    if (err != VP8_ENC_OK) goto Error;
-    BundleColorMap(pic, xbits, enc->argb_, enc->current_width_);
-  }
-
  Error:
+  free(row);
   return err;
 }
 
 // -----------------------------------------------------------------------------
 
 static int GetHistoBits(const WebPConfig* const config,
                         const WebPPicture* const pic) {
   const int width = pic->width;
   const int height = pic->height;
-  const size_t hist_size = sizeof(VP8LHistogram);
+  const uint64_t hist_size = sizeof(VP8LHistogram);
   // Make tile size a function of encoding method (Range: 0 to 6).
   int histo_bits = 7 - config->method;
   while (1) {
-    const size_t huff_image_size = VP8LSubSampleSize(width, histo_bits) *
-                                   VP8LSubSampleSize(height, histo_bits) *
-                                   hist_size;
+    const uint64_t huff_image_size = VP8LSubSampleSize(width, histo_bits) *
+                                     VP8LSubSampleSize(height, histo_bits) *
+                                     hist_size;
     if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break;
     ++histo_bits;
   }
   return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS :
          (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits;
 }
 
 static void InitEncParams(VP8LEncoder* const enc) {
   const WebPConfig* const config = enc->config_;
   const WebPPicture* const picture = enc->pic_;
@@ skipping 48 matching lines @@
   // Analyze image (entropy, num_palettes etc)
 
   if (!VP8LEncAnalyze(enc, config->image_hint)) {
     err = VP8_ENC_ERROR_OUT_OF_MEMORY;
     goto Error;
   }
 
   if (enc->use_palette_) {
     err = ApplyPalette(bw, enc, quality);
     if (err != VP8_ENC_OK) goto Error;
+    // Color cache is disabled for palette.
     enc->cache_bits_ = 0;
   }
 
   // In case image is not packed.
   if (enc->argb_ == NULL) {
     int y;
     err = AllocateTransformBuffer(enc, width, height);
     if (err != VP8_ENC_OK) goto Error;
     for (y = 0; y < height; ++y) {
       memcpy(enc->argb_ + y * width,
@@ skipping 154 matching lines @@
     return 0;
   }
   return 1;
 }
 
 //------------------------------------------------------------------------------
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    // extern "C"
 #endif