libwebp: update snapshot to v0.3.0-rc6

third_party/libwebp/utils/huffman_encode.c

 // Copyright 2011 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/
 // -----------------------------------------------------------------------------
 //
 // Author: Jyrki Alakuijala (jyrki@google.com)
 //
 // Entropy encoding (Huffman) for webp lossless.
@@ skipping 120 matching lines @@
 // A comparer function for two Huffman trees: sorts first by 'total count'
 // (more comes first), and then by 'value' (more comes first).
 static int CompareHuffmanTrees(const void* ptr1, const void* ptr2) {
   const HuffmanTree* const t1 = (const HuffmanTree*)ptr1;
   const HuffmanTree* const t2 = (const HuffmanTree*)ptr2;
   if (t1->total_count_ > t2->total_count_) {
     return -1;
   } else if (t1->total_count_ < t2->total_count_) {
     return 1;
   } else {
-    if (t1->value_ < t2->value_) {
-      return -1;
-    }
-    if (t1->value_ > t2->value_) {
-      return 1;
-    }
-    return 0;
+    assert(t1->value_ != t2->value_);
+    return (t1->value_ < t2->value_) ? -1 : 1;
   }
 }
 
 static void SetBitDepths(const HuffmanTree* const tree,
                          const HuffmanTree* const pool,
                          uint8_t* const bit_depths, int level) {
   if (tree->pool_index_left_ >= 0) {
     SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1);
     SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1);
   } else {
@@ skipping 28 matching lines @@
   HuffmanTree* tree;
   int tree_size_orig = 0;
   int i;
 
   for (i = 0; i < histogram_size; ++i) {
     if (histogram[i] != 0) {
       ++tree_size_orig;
     }
   }
 
+  if (tree_size_orig == 0) {   // pretty optimal already!
+    return 1;
+  }
+
   // 3 * tree_size is enough to cover all the nodes representing a
   // population and all the inserted nodes combining two existing nodes.
   // The tree pool needs 2 * (tree_size_orig - 1) entities, and the
   // tree needs exactly tree_size_orig entities.
   tree = (HuffmanTree*)WebPSafeMalloc(3ULL * tree_size_orig, sizeof(*tree));
   if (tree == NULL) return 0;
   tree_pool = tree + tree_size_orig;
 
   // For block sizes with less than 64k symbols we never need to do a
   // second iteration of this loop.
@@ skipping 21 matching lines @@
     // Build the Huffman tree.
     qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees);
 
     if (tree_size > 1) {  // Normal case.
       int tree_pool_size = 0;
       while (tree_size > 1) {  // Finish when we have only one root.
         int count;
         tree_pool[tree_pool_size++] = tree[tree_size - 1];
         tree_pool[tree_pool_size++] = tree[tree_size - 2];
         count = tree_pool[tree_pool_size - 1].total_count_ +
-            tree_pool[tree_pool_size - 2].total_count_;
+                tree_pool[tree_pool_size - 2].total_count_;
         tree_size -= 2;
         {
           // Search for the insertion point.
           int k;
           for (k = 0; k < tree_size; ++k) {
             if (tree[k].total_count_ <= count) {
               break;
             }
           }
           memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree));
@@ skipping 182 matching lines @@
     return 0;
   }
   if (!GenerateOptimalTree(histogram, num_symbols,
                            tree_depth_limit, tree->code_lengths)) {
     return 0;
   }
   // Create the actual bit codes for the bit lengths.
   ConvertBitDepthsToSymbols(tree);
   return 1;
 }