libwebp: update to 0.4.1

third_party/libwebp/utils/huffman.c

Index: third_party/libwebp/utils/huffman.c
diff --git a/third_party/libwebp/utils/huffman.c b/third_party/libwebp/utils/huffman.c
index 8c5739f633d4377abf4ae629eca21630ecca0516..c4c16d9e6ce2bb4b7ec2e7afe875e9f19e2ed406 100644
--- a/third_party/libwebp/utils/huffman.c
+++ b/third_party/libwebp/utils/huffman.c
@@ -22,6 +22,9 @@
 // (might be faster on some platform)
 // #define USE_LUT_REVERSE_BITS
 
+// Huffman data read via DecodeImageStream is represented in two (red and green)
+// bytes.
+#define MAX_HTREE_GROUPS    0x10000
 #define NON_EXISTENT_SYMBOL (-1)
 
 static void TreeNodeInit(HuffmanTreeNode* const node) {
@@ -46,17 +49,25 @@ static void AssignChildren(HuffmanTree* const tree,
   TreeNodeInit(children + 1);
 }
 
+// A Huffman tree is a full binary tree; and in a full binary tree with L
+// leaves, the total number of nodes N = 2 * L - 1.
+static int HuffmanTreeMaxNodes(int num_leaves) {
+  return (2 * num_leaves - 1);
+}
+
+static int HuffmanTreeAllocate(HuffmanTree* const tree, int num_nodes) {
+  assert(tree != NULL);
+  tree->root_ =
+      (HuffmanTreeNode*)WebPSafeMalloc(num_nodes, sizeof(*tree->root_));
+  return (tree->root_ != NULL);
+}
+
 static int TreeInit(HuffmanTree* const tree, int num_leaves) {
   assert(tree != NULL);
   if (num_leaves == 0) return 0;
-  // We allocate maximum possible nodes in the tree at once.
-  // Note that a Huffman tree is a full binary tree; and in a full binary tree
-  // with L leaves, the total number of nodes N = 2 * L - 1.
-  tree->max_nodes_ = 2 * num_leaves - 1;
+  tree->max_nodes_ = HuffmanTreeMaxNodes(num_leaves);
   assert(tree->max_nodes_ < (1 << 16));   // limit for the lut_jump_ table
-  tree->root_ = (HuffmanTreeNode*)WebPSafeMalloc((uint64_t)tree->max_nodes_,
-                                                 sizeof(*tree->root_));
-  if (tree->root_ == NULL) return 0;
+  if (!HuffmanTreeAllocate(tree, tree->max_nodes_)) return 0;
   TreeNodeInit(tree->root_);  // Initialize root.
   tree->num_nodes_ = 1;
   memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_));
@@ -64,17 +75,41 @@ static int TreeInit(HuffmanTree* const tree, int num_leaves) {
   return 1;
 }
 
-void HuffmanTreeRelease(HuffmanTree* const tree) {
+void VP8LHuffmanTreeFree(HuffmanTree* const tree) {
   if (tree != NULL) {
-    free(tree->root_);
+    WebPSafeFree(tree->root_);
     tree->root_ = NULL;
     tree->max_nodes_ = 0;
     tree->num_nodes_ = 0;
   }
 }
 
-int HuffmanCodeLengthsToCodes(const int* const code_lengths,
-                              int code_lengths_size, int* const huff_codes) {
+HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
+  HTreeGroup* const htree_groups =
+      (HTreeGroup*)WebPSafeCalloc(num_htree_groups, sizeof(*htree_groups));
+  assert(num_htree_groups <= MAX_HTREE_GROUPS);
+  if (htree_groups == NULL) {
+    return NULL;
+  }
+  return htree_groups;
+}
+
+void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups) {
+  if (htree_groups != NULL) {
+    int i, j;
+    for (i = 0; i < num_htree_groups; ++i) {
+      HuffmanTree* const htrees = htree_groups[i].htrees_;
+      for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) {
+        VP8LHuffmanTreeFree(&htrees[j]);
+      }
+    }
+    WebPSafeFree(htree_groups);
+  }
+}
+
+int VP8LHuffmanCodeLengthsToCodes(
+    const int* const code_lengths, int code_lengths_size,
+    int* const huff_codes) {
   int symbol;
   int code_len;
   int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
@@ -193,9 +228,10 @@ static int TreeAddSymbol(HuffmanTree* const tree,
   return 1;
 }
 
-int HuffmanTreeBuildImplicit(HuffmanTree* const tree,
-                             const int* const code_lengths,
-                             int code_lengths_size) {
+int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree,
+                                 const int* const code_lengths,
+                                 int* const codes,
+                                 int code_lengths_size) {
   int symbol;
   int num_symbols = 0;
   int root_symbol = 0;
@@ -219,47 +255,43 @@ int HuffmanTreeBuildImplicit(HuffmanTree* const tree,
   if (num_symbols == 1) {  // Trivial case.
     const int max_symbol = code_lengths_size;
     if (root_symbol < 0 || root_symbol >= max_symbol) {
-      HuffmanTreeRelease(tree);
+      VP8LHuffmanTreeFree(tree);
       return 0;
     }
     return TreeAddSymbol(tree, root_symbol, 0, 0);
   } else {  // Normal case.
     int ok = 0;
+    memset(codes, 0, code_lengths_size * sizeof(*codes));
 
-    // Get Huffman codes from the code lengths.
-    int* const codes =
-        (int*)WebPSafeMalloc((uint64_t)code_lengths_size, sizeof(*codes));
-    if (codes == NULL) goto End;
-
-    if (!HuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, codes)) {
+    if (!VP8LHuffmanCodeLengthsToCodes(code_lengths, code_lengths_size,
+                                       codes)) {
       goto End;
     }
 
     // Add symbols one-by-one.
     for (symbol = 0; symbol < code_lengths_size; ++symbol) {
       if (code_lengths[symbol] > 0) {
-        if (!TreeAddSymbol(tree, symbol, codes[symbol], code_lengths[symbol])) {
+        if (!TreeAddSymbol(tree, symbol, codes[symbol],
+                           code_lengths[symbol])) {
           goto End;
         }
       }
     }
     ok = 1;
  End:
-    free(codes);
     ok = ok && IsFull(tree);
-    if (!ok) HuffmanTreeRelease(tree);
+    if (!ok) VP8LHuffmanTreeFree(tree);
     return ok;
   }
 }
 
-int HuffmanTreeBuildExplicit(HuffmanTree* const tree,
-                             const int* const code_lengths,
-                             const int* const codes,
-                             const int* const symbols, int max_symbol,
-                             int num_symbols) {
+int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree,
+                                 const int* const code_lengths,
+                                 const int* const codes,
+                                 const int* const symbols, int max_symbol,
+                                 int num_symbols) {
   int ok = 0;
   int i;
-
   assert(tree != NULL);
   assert(code_lengths != NULL);
   assert(codes != NULL);
@@ -282,7 +314,6 @@ int HuffmanTreeBuildExplicit(HuffmanTree* const tree,
   ok = 1;
  End:
   ok = ok && IsFull(tree);
-  if (!ok) HuffmanTreeRelease(tree);
+  if (!ok) VP8LHuffmanTreeFree(tree);
   return ok;
 }
-