CVE-2023-4863: Out-of-bounds Write (CWE-787)
value: Heap buffer overflow in libwebp in Google Chrome prior to 116.0.5845.187 and libwebp 1.3.2 allowed a remote attacker to perform an out of bounds memory write via a crafted HTML page. (Chromium security severity: Critical)
CWE description: The product writes data past the end, or before the beginning, of the intended buffer.
CVSS v3 base score: 8.8
Published: 2023-09-12T15:15Z
Repository: https://github.com/webmproject/libwebp
Language: C
Files changed: src/dec/vp8l_dec.c, src/dec/vp8li_dec.h, src/utils/huffman_utils.c, src/utils/huffman_utils.h
Commit date: 2023-09-07 21:16:03 +0200
Commit message: Fix OOB write in BuildHuffmanTable.

First, BuildHuffmanTable is called to check if the data is valid.
If it is and the table is not big enough, more memory is allocated.

This will make sure that valid (but unoptimized because of unbalanced
codes) streams are still decodable.

Bug: chromium:1479274
Change-Id: I31c36dbf3aa78d35ecf38706b50464fd3d375741

Diff: diff --git a/src/dec/vp8l_dec.c b/src/dec/vp8l_dec.c
index 45012162..5ab34f56 100644
--- a/src/dec/vp8l_dec.c
+++ b/src/dec/vp8l_dec.c
@@ -260,15 +260,15 @@ static int ReadHuffmanCodeLengths(
   int ok = 0;
   VP8LBitReader* const br = &dec->br_;
   int symbol;
   int max_symbol;
   int prev_code_len = DEFAULT_CODE_LENGTH;
-  HuffmanCode table[1 << LENGTHS_TABLE_BITS];
+  HuffmanTables tables;
 
-  if (!VP8LBuildHuffmanTable(table, LENGTHS_TABLE_BITS,
-                             code_length_code_lengths,
-                             NUM_CODE_LENGTH_CODES)) {
+  if (!VP8LHuffmanTablesAllocate(1 << LENGTHS_TABLE_BITS, &tables) ||
+      !VP8LBuildHuffmanTable(&tables, LENGTHS_TABLE_BITS,
+                             code_length_code_lengths, NUM_CODE_LENGTH_CODES)) {
     goto End;
   }
 
   if (VP8LReadBits(br, 1)) {    // use length
     const int length_nbits = 2 + 2 * VP8LReadBits(br, 3);
@@ -284,11 +284,11 @@ static int ReadHuffmanCodeLengths(
   while (symbol < num_symbols) {
     const HuffmanCode* p;
     int code_len;
     if (max_symbol-- == 0) break;
     VP8LFillBitWindow(br);
-    p = &table[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];
+    p = &tables.curr_segment->start[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];
     VP8LSetBitPos(br, br->bit_pos_ + p->bits);
     code_len = p->value;
     if (code_len < kCodeLengthLiterals) {
       code_lengths[symbol++] = code_len;
       if (code_len != 0) prev_code_len = code_len;
@@ -307,18 +307,20 @@ static int ReadHuffmanCodeLengths(
     }
   }
   ok = 1;
 
  End:
+  VP8LHuffmanTablesDeallocate(&tables);
   if (!ok) return VP8LSetError(dec, VP8_STATUS_BITSTREAM_ERROR);
   return ok;
 }
 
 // 'code_lengths' is pre-allocated temporary buffer, used for creating Huffman
 // tree.
 static int ReadHuffmanCode(int alphabet_size, VP8LDecoder* const dec,
-                           int* const code_lengths, HuffmanCode* const table) {
+                           int* const code_lengths,
+                           HuffmanTables* const table) {
   int ok = 0;
   int size = 0;
   VP8LBitReader* const br = &dec->br_;
   const int simple_code = VP8LReadBits(br, 1);
 
@@ -365,21 +367,24 @@ static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize,
   int i, j;
   VP8LBitReader* const br = &dec->br_;
   VP8LMetadata* const hdr = &dec->hdr_;
   uint32_t* huffman_image = NULL;
   HTreeGroup* htree_groups = NULL;
-  HuffmanCode* huffman_tables = NULL;
-  HuffmanCode* huffman_table = NULL;
+  HuffmanTables* huffman_tables = &hdr->huffman_tables_;
   int num_htree_groups = 1;
   int num_htree_groups_max = 1;
   const int max_alphabet_size =
       kAlphabetSize[0] + ((color_cache_bits > 0) ? 1 << color_cache_bits : 0);
   int* code_lengths = NULL;
   const int table_size = kTableSize[color_cache_bits];
   int* mapping = NULL;
   int ok = 0;
 
+  // Check the table has been 0 initialized (through InitMetadata).
+  assert(huffman_tables->root.start == NULL);
+  assert(huffman_tables->curr_segment == NULL);
+
   if (allow_recursion && VP8LReadBits(br, 1)) {
     // use meta Huffman codes.
     const int huffman_precision = VP8LReadBits(br, 3) + 2;
     const int huffman_xsize = VP8LSubSampleSize(xsize, huffman_precision);
     const int huffman_ysize = VP8LSubSampleSize(ysize, huffman_precision);
@@ -427,20 +432,19 @@ static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize,
 
   if (br->eos_) goto Error;
 
   code_lengths = (int*)WebPSafeCalloc((uint64_t)max_alphabet_size,
                                       sizeof(*code_lengths));
-  huffman_tables = (HuffmanCode*)WebPSafeMalloc(num_htree_groups * table_size,
-                                                sizeof(*huffman_tables));
   htree_groups = VP8LHtreeGroupsNew(num_htree_groups);
 
-  if (htree_groups == NULL || code_lengths == NULL || huffman_tables == NULL) {
+  if (htree_groups == NULL || code_lengths == NULL ||
+      !VP8LHuffmanTablesAllocate(num_htree_groups * table_size,
+                                 huffman_tables)) {
     VP8LSetError(dec, VP8_STATUS_OUT_OF_MEMORY);
     goto Error;
   }
 
-  huffman_table = huffman_tables;
   for (i = 0; i < num_htree_groups_max; ++i) {
     // If the index "i" is unused in the Huffman image, just make sure the
     // coefficients are valid but do not store them.
     if (mapping != NULL && mapping[i] == -1) {
       for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) {
@@ -461,23 +465,24 @@ static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize,
       int total_size = 0;
       int is_trivial_literal = 1;
       int max_bits = 0;
       for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) {
         int alphabet_size = kAlphabetSize[j];
-        htrees[j] = huffman_table;
         if (j == 0 && color_cache_bits > 0) {
           alphabet_size += (1 << color_cache_bits);
         }
-        size = ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_table);
+        size =
+            ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_tables);
+        htrees[j] = huffman_tables->curr_segment->curr_table;
         if (size == 0) {
           goto Error;
         }
         if (is_trivial_literal && kLiteralMap[j] == 1) {
-          is_trivial_literal = (huffman_table->bits == 0);
+          is_trivial_literal = (htrees[j]->bits == 0);
         }
-        total_size += huffman_table->bits;
-        huffman_table += size;
+        total_size += htrees[j]->bits;
+        huffman_tables->curr_segment->curr_table += size;
         if (j <= ALPHA) {
           int local_max_bits = code_lengths[0];
           int k;
           for (k = 1; k < alphabet_size; ++k) {
             if (code_lengths[k] > local_max_bits) {
@@ -508,18 +513,17 @@ static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize,
 
   // All OK. Finalize pointers.
   hdr->huffman_image_ = huffman_image;
   hdr->num_htree_groups_ = num_htree_groups;
   hdr->htree_groups_ = htree_groups;
-  hdr->huffman_tables_ = huffman_tables;
 
  Error:
   WebPSafeFree(code_lengths);
   WebPSafeFree(mapping);
   if (!ok) {
     WebPSafeFree(huffman_image);
-    WebPSafeFree(huffman_tables);
+    VP8LHuffmanTablesDeallocate(huffman_tables);
     VP8LHtreeGroupsFree(htree_groups);
   }
   return ok;
 }
 
@@ -1350,11 +1354,11 @@ static void InitMetadata(VP8LMetadata* const hdr) {
 
 static void ClearMetadata(VP8LMetadata* const hdr) {
   assert(hdr != NULL);
 
   WebPSafeFree(hdr->huffman_image_);
-  WebPSafeFree(hdr->huffman_tables_);
+  VP8LHuffmanTablesDeallocate(&hdr->huffman_tables_);
   VP8LHtreeGroupsFree(hdr->htree_groups_);
   VP8LColorCacheClear(&hdr->color_cache_);
   VP8LColorCacheClear(&hdr->saved_color_cache_);
   InitMetadata(hdr);
 }
@@ -1664,11 +1668,11 @@ int VP8LDecodeImage(VP8LDecoder* const dec) {
   VP8Io* io = NULL;
   WebPDecParams* params = NULL;
 
   if (dec == NULL) return 0;
 
-  assert(dec->hdr_.huffman_tables_ != NULL);
+  assert(dec->hdr_.huffman_tables_.root.start != NULL);
   assert(dec->hdr_.htree_groups_ != NULL);
   assert(dec->hdr_.num_htree_groups_ > 0);
 
   io = dec->io_;
   assert(io != NULL);
diff --git a/src/dec/vp8li_dec.h b/src/dec/vp8li_dec.h
index 72b2e861..32540a4b 100644
--- a/src/dec/vp8li_dec.h
+++ b/src/dec/vp8li_dec.h
@@ -49,11 +49,11 @@ typedef struct {
   int             huffman_subsample_bits_;
   int             huffman_xsize_;
   uint32_t*       huffman_image_;
   int             num_htree_groups_;
   HTreeGroup*     htree_groups_;
-  HuffmanCode*    huffman_tables_;
+  HuffmanTables   huffman_tables_;
 } VP8LMetadata;
 
 typedef struct VP8LDecoder VP8LDecoder;
 struct VP8LDecoder {
   VP8StatusCode    status_;
diff --git a/src/utils/huffman_utils.c b/src/utils/huffman_utils.c
index 90c2fbf7..cf73abd4 100644
--- a/src/utils/huffman_utils.c
+++ b/src/utils/huffman_utils.c
@@ -175,25 +175,28 @@ static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
       num_nodes += num_open;
       num_open -= count[len];
       if (num_open < 0) {
         return 0;
       }
-      if (root_table == NULL) continue;
       for (; count[len] > 0; --count[len]) {
         HuffmanCode code;
         if ((key & mask) != low) {
-          table += table_size;
+          if (root_table != NULL) table += table_size;
           table_bits = NextTableBitSize(count, len, root_bits);
           table_size = 1 << table_bits;
           total_size += table_size;
           low = key & mask;
-          root_table[low].bits = (uint8_t)(table_bits + root_bits);
-          root_table[low].value = (uint16_t)((table - root_table) - low);
+          if (root_table != NULL) {
+            root_table[low].bits = (uint8_t)(table_bits + root_bits);
+            root_table[low].value = (uint16_t)((table - root_table) - low);
+          }
+        }
+        if (root_table != NULL) {
+          code.bits = (uint8_t)(len - root_bits);
+          code.value = (uint16_t)sorted[symbol++];
+          ReplicateValue(&table[key >> root_bits], step, table_size, code);
         }
-        code.bits = (uint8_t)(len - root_bits);
-        code.value = (uint16_t)sorted[symbol++];
-        ReplicateValue(&table[key >> root_bits], step, table_size, code);
         key = GetNextKey(key, len);
       }
     }
 
     // Check if tree is full.
@@ -209,27 +212,85 @@ static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
 // More commonly, the value is around ~280.
 #define MAX_CODE_LENGTHS_SIZE \
   ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES)
 // Cut-off value for switching between heap and stack allocation.
 #define SORTED_SIZE_CUTOFF 512
-int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
+int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
                           const int code_lengths[], int code_lengths_size) {
-  int total_size;
+  const int total_size =
+      BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
   assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
-  if (root_table == NULL) {
-    total_size = BuildHuffmanTable(NULL, root_bits,
-                                   code_lengths, code_lengths_size, NULL);
-  } else if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
+  if (total_size == 0 || root_table == NULL) return total_size;
+
+  if (root_table->curr_segment->curr_table + total_size >=
+      root_table->curr_segment->start + root_table->curr_segment->size) {
+    // If 'root_table' does not have enough memory, allocate a new segment.
+    // The available part of root_table->curr_segment is left unused because we
+    // need a contiguous buffer.
+    const int segment_size = root_table->curr_segment->size;
+    struct HuffmanTablesSegment* next =
+        (HuffmanTablesSegment*)WebPSafeMalloc(1, sizeof(*next));
+    if (next == NULL) return 0;
+    // Fill the new segment.
+    // We need at least 'total_size' but if that value is small, it is better to
+    // allocate a big chunk to prevent more allocations later. 'segment_size' is
+    // therefore chosen (any other arbitrary value could be chosen).
+    next->size = total_size > segment_size ? total_size : segment_size;
+    next->start =
+        (HuffmanCode*)WebPSafeMalloc(next->size, sizeof(*next->start));
+    if (next->start == NULL) {
+      WebPSafeFree(next);
+      return 0;
+    }
+    next->curr_table = next->start;
+    next->next = NULL;
+    // Point to the new segment.
+    root_table->curr_segment->next = next;
+    root_table->curr_segment = next;
+  }
+  if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
     // use local stack-allocated array.
     uint16_t sorted[SORTED_SIZE_CUTOFF];
-    total_size = BuildHuffmanTable(root_table, root_bits,
-                                   code_lengths, code_lengths_size, sorted);
-  } else {   // rare case. Use heap allocation.
+    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
+                      code_lengths, code_lengths_size, sorted);
+  } else {  // rare case. Use heap allocation.
     uint16_t* const sorted =
         (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted));
     if (sorted == NULL) return 0;
-    total_size = BuildHuffmanTable(root_table, root_bits,
-                                   code_lengths, code_lengths_size, sorted);
+    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
+                      code_lengths, code_lengths_size, sorted);
     WebPSafeFree(sorted);
   }
   return total_size;
 }
+
+int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) {
+  // Have 'segment' point to the first segment for now, 'root'.
+  HuffmanTablesSegment* const root = &huffman_tables->root;
+  huffman_tables->curr_segment = root;
+  // Allocate root.
+  root->start = (HuffmanCode*)WebPSafeMalloc(size, sizeof(*root->start));
+  if (root->start == NULL) return 0;
+  root->curr_table = root->start;
+  root->next = NULL;
+  root->size = size;
+  return 1;
+}
+
+void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) {
+  HuffmanTablesSegment *current, *next;
+  if (huffman_tables == NULL) return;
+  // Free the root node.
+  current = &huffman_tables->root;
+  next = current->next;
+  WebPSafeFree(current->start);
+  current->start = NULL;
+  current->next = NULL;
+  current = next;
+  // Free the following nodes.
+  while (current != NULL) {
+    next = current->next;
+    WebPSafeFree(current->start);
+    WebPSafeFree(current);
+    current = next;
+  }
+}
diff --git a/src/utils/huffman_utils.h b/src/utils/huffman_utils.h
index 13b7ad1a..98415c53 100644
--- a/src/utils/huffman_utils.h
+++ b/src/utils/huffman_utils.h
@@ -41,10 +41,33 @@ typedef struct {
                     // or an impossible value if not a literal code.
   uint32_t value;   // 32b packed ARGB value if literal,
                     // or non-literal symbol otherwise
 } HuffmanCode32;
 
+// Contiguous memory segment of HuffmanCodes.
+typedef struct HuffmanTablesSegment {
+  HuffmanCode* start;
+  // Pointer to where we are writing into the segment. Starts at 'start' and
+  // cannot go beyond 'start' + 'size'.
+  HuffmanCode* curr_table;
+  // Pointer to the next segment in the chain.
+  struct HuffmanTablesSegment* next;
+  int size;
+} HuffmanTablesSegment;
+
+// Chained memory segments of HuffmanCodes.
+typedef struct HuffmanTables {
+  HuffmanTablesSegment root;
+  // Currently processed segment. At first, this is 'root'.
+  HuffmanTablesSegment* curr_segment;
+} HuffmanTables;
+
+// Allocates a HuffmanTables with 'size' contiguous HuffmanCodes. Returns 0 on
+// memory allocation error, 1 otherwise.
+int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables);
+void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables);
+
 #define HUFFMAN_PACKED_BITS 6
 #define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS)
 
 // Huffman table group.
 // Includes special handling for the following cases:
@@ -76,13 +99,11 @@ void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups);
 // Builds Huffman lookup table assuming code lengths are in symbol order.
 // The 'code_lengths' is pre-allocated temporary memory buffer used for creating
 // the huffman table.
 // Returns built table size or 0 in case of error (invalid tree or
 // memory error).
-// If root_table is NULL, it returns 0 if a lookup cannot be built, something
-// > 0 otherwise (but not the table size).
-int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
+int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
                           const int code_lengths[], int code_lengths_size);
 
 #ifdef __cplusplus
 }    // extern "C"
 #endif

Vulnerable code:   HuffmanCode table[1 << LENGTHS_TABLE_BITS];
  if (!VP8LBuildHuffmanTable(table, LENGTHS_TABLE_BITS,
                             code_length_code_lengths,
                             NUM_CODE_LENGTH_CODES)) {
    p = &table[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];
                           int* const code_lengths, HuffmanCode* const table) {
  HuffmanCode* huffman_tables = NULL;
  HuffmanCode* huffman_table = NULL;
  huffman_tables = (HuffmanCode*)WebPSafeMalloc(num_htree_groups * table_size,
                                                sizeof(*huffman_tables));
  if (htree_groups == NULL || code_lengths == NULL || huffman_tables == NULL) {
  huffman_table = huffman_tables;
        htrees[j] = huffman_table;
        size = ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_table);
          is_trivial_literal = (huffman_table->bits == 0);
        total_size += huffman_table->bits;
        huffman_table += size;
  hdr->huffman_tables_ = huffman_tables;
    WebPSafeFree(huffman_tables);
  WebPSafeFree(hdr->huffman_tables_);
  assert(dec->hdr_.huffman_tables_ != NULL);
  HuffmanCode*    huffman_tables_;
      if (root_table == NULL) continue;
          table += table_size;
          root_table[low].bits = (uint8_t)(table_bits + root_bits);
          root_table[low].value = (uint16_t)((table - root_table) - low);
        code.bits = (uint8_t)(len - root_bits);
        code.value = (uint16_t)sorted[symbol++];
        ReplicateValue(&table[key >> root_bits], step, table_size, code);
int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
  int total_size;
  if (root_table == NULL) {
    total_size = BuildHuffmanTable(NULL, root_bits,
                                   code_lengths, code_lengths_size, NULL);
  } else if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
    total_size = BuildHuffmanTable(root_table, root_bits,
                                   code_lengths, code_lengths_size, sorted);
  } else {   // rare case. Use heap allocation.
    total_size = BuildHuffmanTable(root_table, root_bits,
                                   code_lengths, code_lengths_size, sorted);
// If root_table is NULL, it returns 0 if a lookup cannot be built, something
// > 0 otherwise (but not the table size).
int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
Fixed code:   HuffmanTables tables;
  if (!VP8LHuffmanTablesAllocate(1 << LENGTHS_TABLE_BITS, &tables) ||
      !VP8LBuildHuffmanTable(&tables, LENGTHS_TABLE_BITS,
                             code_length_code_lengths, NUM_CODE_LENGTH_CODES)) {
    p = &tables.curr_segment->start[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];
  VP8LHuffmanTablesDeallocate(&tables);
                           int* const code_lengths,
                           HuffmanTables* const table) {
  HuffmanTables* huffman_tables = &hdr->huffman_tables_;
  // Check the table has been 0 initialized (through InitMetadata).
  assert(huffman_tables->root.start == NULL);
  assert(huffman_tables->curr_segment == NULL);

  if (htree_groups == NULL || code_lengths == NULL ||
      !VP8LHuffmanTablesAllocate(num_htree_groups * table_size,
                                 huffman_tables)) {
        size =
            ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_tables);
        htrees[j] = huffman_tables->curr_segment->curr_table;
          is_trivial_literal = (htrees[j]->bits == 0);
        total_size += htrees[j]->bits;
        huffman_tables->curr_segment->curr_table += size;
    VP8LHuffmanTablesDeallocate(huffman_tables);
  VP8LHuffmanTablesDeallocate(&hdr->huffman_tables_);
  assert(dec->hdr_.huffman_tables_.root.start != NULL);
  HuffmanTables   huffman_tables_;
          if (root_table != NULL) table += table_size;
          if (root_table != NULL) {
            root_table[low].bits = (uint8_t)(table_bits + root_bits);
            root_table[low].value = (uint16_t)((table - root_table) - low);
          }
        }
        if (root_table != NULL) {
          code.bits = (uint8_t)(len - root_bits);
          code.value = (uint16_t)sorted[symbol++];
          ReplicateValue(&table[key >> root_bits], step, table_size, code);
int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
  const int total_size =
      BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
  if (total_size == 0 || root_table == NULL) return total_size;

  if (root_table->curr_segment->curr_table + total_size >=
      root_table->curr_segment->start + root_table->curr_segment->size) {
    // If 'root_table' does not have enough memory, allocate a new segment.
    // The available part of root_table->curr_segment is left unused because we
    // need a contiguous buffer.
    const int segment_size = root_table->curr_segment->size;
    struct HuffmanTablesSegment* next =
        (HuffmanTablesSegment*)WebPSafeMalloc(1, sizeof(*next));
    if (next == NULL) return 0;
    // Fill the new segment.
    // We need at least 'total_size' but if that value is small, it is better to
    // allocate a big chunk to prevent more allocations later. 'segment_size' is
    // therefore chosen (any other arbitrary value could be chosen).
    next->size = total_size > segment_size ? total_size : segment_size;
    next->start =
        (HuffmanCode*)WebPSafeMalloc(next->size, sizeof(*next->start));
    if (next->start == NULL) {
      WebPSafeFree(next);
      return 0;
    }
    next->curr_table = next->start;
    next->next = NULL;
    // Point to the new segment.
    root_table->curr_segment->next = next;
    root_table->curr_segment = next;
  }
  if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
                      code_lengths, code_lengths_size, sorted);
  } else {  // rare case. Use heap allocation.
    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
                      code_lengths, code_lengths_size, sorted);

int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) {
  // Have 'segment' point to the first segment for now, 'root'.
  HuffmanTablesSegment* const root = &huffman_tables->root;
  huffman_tables->curr_segment = root;
  // Allocate root.
  root->start = (HuffmanCode*)WebPSafeMalloc(size, sizeof(*root->start));
  if (root->start == NULL) return 0;
  root->curr_table = root->start;
  root->next = NULL;
  root->size = size;
  return 1;
}

void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) {
  HuffmanTablesSegment *current, *next;
  if (huffman_tables == NULL) return;
  // Free the root node.
  current = &huffman_tables->root;
  next = current->next;
  WebPSafeFree(current->start);
  current->start = NULL;
  current->next = NULL;
  current = next;
  // Free the following nodes.
  while (current != NULL) {
    next = current->next;
    WebPSafeFree(current->start);
    WebPSafeFree(current);
    current = next;
  }
}
// Contiguous memory segment of HuffmanCodes.
typedef struct HuffmanTablesSegment {
  HuffmanCode* start;
  // Pointer to where we are writing into the segment. Starts at 'start' and
  // cannot go beyond 'start' + 'size'.
  HuffmanCode* curr_table;
  // Pointer to the next segment in the chain.
  struct HuffmanTablesSegment* next;
  int size;
} HuffmanTablesSegment;

// Chained memory segments of HuffmanCodes.
typedef struct HuffmanTables {
  HuffmanTablesSegment root;
  // Currently processed segment. At first, this is 'root'.
  HuffmanTablesSegment* curr_segment;
} HuffmanTables;

// Allocates a HuffmanTables with 'size' contiguous HuffmanCodes. Returns 0 on
// memory allocation error, 1 otherwise.
int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables);
void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables);

int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,