src/utils/huffman_utils.c - webm/libwebp - Git at Google

 // Copyright 2012 Google Inc. All Rights Reserved.
 //
 // Use of this source code is governed by a BSD-style license
 // that can be found in the COPYING file in the root of the source
 // tree. An additional intellectual property rights grant can be found
 // in the file PATENTS. All contributing project authors may
 // be found in the AUTHORS file in the root of the source tree.
 // -----------------------------------------------------------------------------
 //
 // Utilities for building and looking up Huffman trees.
 //
 // Author: Urvang Joshi (urvang@google.com)

 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>
 #include "src/utils/huffman_utils.h"
 #include "src/utils/utils.h"
 #include "src/webp/format_constants.h"

 // Huffman data read via DecodeImageStream is represented in two (red and green)
 // bytes.
 #define MAX_HTREE_GROUPS    0x10000

 HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
   HTreeGroup* const htree_groups =
       (HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups));
   if (htree_groups == NULL) {
     return NULL;
   }
   assert(num_htree_groups <= MAX_HTREE_GROUPS);
   return htree_groups;
 }

 void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) {
   if (htree_groups != NULL) {
     WebPSafeFree(htree_groups);
   }
 }

 // Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the
 // bit-wise reversal of the len least significant bits of key.
 static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) {
   uint32_t step = 1 << (len - 1);
   while (key & step) {
     step >>= 1;
   }
   return step ? (key & (step - 1)) + step : key;
 }

 // Stores code in table[0], table[step], table[2*step], ..., table[end].
 // Assumes that end is an integer multiple of step.
 static WEBP_INLINE void ReplicateValue(HuffmanCode* table,
                                        int step, int end,
                                        HuffmanCode code) {
   assert(end % step == 0);
   do {
     end -= step;
     table[end] = code;
   } while (end > 0);
 }

 // Returns the table width of the next 2nd level table. count is the histogram
 // of bit lengths for the remaining symbols, len is the code length of the next
 // processed symbol
 static WEBP_INLINE int NextTableBitSize(const int* const count,
                                         int len, int root_bits) {
   int left = 1 << (len - root_bits);
   while (len < MAX_ALLOWED_CODE_LENGTH) {
     left -= count[len];
     if (left <= 0) break;
     ++len;
     left <<= 1;
   }
   return len - root_bits;
 }

 // sorted[code_lengths_size] is a pre-allocated array for sorting symbols
 // by code length.
 static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
                              const int code_lengths[], int code_lengths_size,
                              uint16_t sorted[]) {
   HuffmanCode* table = root_table;  // next available space in table
   int total_size = 1 << root_bits;  // total size root table + 2nd level table
   int len;                          // current code length
   int symbol;                       // symbol index in original or sorted table
   // number of codes of each length:
   int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
   // offsets in sorted table for each length:
   int offset[MAX_ALLOWED_CODE_LENGTH + 1];

   assert(code_lengths_size != 0);
   assert(code_lengths != NULL);
   assert((root_table != NULL && sorted != NULL) ||
          (root_table == NULL && sorted == NULL));
   assert(root_bits > 0);

   // Build histogram of code lengths.
   for (symbol = 0; symbol < code_lengths_size; ++symbol) {
     if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
       return 0;
     }
     ++count[code_lengths[symbol]];
   }

   // Error, all code lengths are zeros.
   if (count[0] == code_lengths_size) {
     return 0;
   }

   // Generate offsets into sorted symbol table by code length.
   offset[1] = 0;
   for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) {
     if (count[len] > (1 << len)) {
       return 0;
     }
     offset[len + 1] = offset[len] + count[len];
   }

   // Sort symbols by length, by symbol order within each length.
   for (symbol = 0; symbol < code_lengths_size; ++symbol) {
     const int symbol_code_length = code_lengths[symbol];
     if (code_lengths[symbol] > 0) {
       if (sorted != NULL) {
         sorted[offset[symbol_code_length]++] = symbol;
       } else {
         offset[symbol_code_length]++;
       }
     }
   }

   // Special case code with only one value.
   if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
     if (sorted != NULL) {
       HuffmanCode code;
       code.bits = 0;
       code.value = (uint16_t)sorted[0];
       ReplicateValue(table, 1, total_size, code);
     }
     return total_size;
   }

   {
     int step;              // step size to replicate values in current table
     uint32_t low = 0xffffffffu;        // low bits for current root entry
     uint32_t mask = total_size - 1;    // mask for low bits
     uint32_t key = 0;      // reversed prefix code
     int num_nodes = 1;     // number of Huffman tree nodes
     int num_open = 1;      // number of open branches in current tree level
     int table_bits = root_bits;        // key length of current table
     int table_size = 1 << table_bits;  // size of current table
     symbol = 0;
     // Fill in root table.
     for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
       num_open <<= 1;
       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;
         code.bits = (uint8_t)len;
         code.value = (uint16_t)sorted[symbol++];
         ReplicateValue(&table[key], step, table_size, code);
         key = GetNextKey(key, len);
       }
     }

     // Fill in 2nd level tables and add pointers to root table.
     for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;
          ++len, step <<= 1) {
       num_open <<= 1;
       num_nodes += num_open;
       num_open -= count[len];
       if (num_open < 0) {
         return 0;
       }
       for (; count[len] > 0; --count[len]) {
         HuffmanCode code;
         if ((key & mask) != low) {
           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;
           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);
         }
         key = GetNextKey(key, len);
       }
     }

     // Check if tree is full.
     if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
       return 0;
     }
   }

   return total_size;
 }

 // Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_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(HuffmanTables* const root_table, int root_bits,
                           const int code_lengths[], int code_lengths_size) {
   const int total_size =
       BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
   assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
   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];
     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;
     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;
   }
 }
	// Copyright 2012 Google Inc. All Rights Reserved.
	//
	// Use of this source code is governed by a BSD-style license
	// that can be found in the COPYING file in the root of the source
	// tree. An additional intellectual property rights grant can be found
	// in the file PATENTS. All contributing project authors may
	// be found in the AUTHORS file in the root of the source tree.
	// -----------------------------------------------------------------------------
	//
	// Utilities for building and looking up Huffman trees.
	//
	// Author: Urvang Joshi (urvang@google.com)

	#include <assert.h>
	#include <stdlib.h>
	#include <string.h>
	#include "src/utils/huffman_utils.h"
	#include "src/utils/utils.h"
	#include "src/webp/format_constants.h"

	// Huffman data read via DecodeImageStream is represented in two (red and green)
	// bytes.
	#define MAX_HTREE_GROUPS 0x10000

	HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
	HTreeGroup* const htree_groups =
	(HTreeGroup)WebPSafeMalloc(num_htree_groups, sizeof(htree_groups));
	if (htree_groups == NULL) {
	return NULL;
	}
	assert(num_htree_groups <= MAX_HTREE_GROUPS);
	return htree_groups;
	}

	void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) {
	if (htree_groups != NULL) {
	WebPSafeFree(htree_groups);
	}
	}

	// Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the
	// bit-wise reversal of the len least significant bits of key.
	static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) {
	uint32_t step = 1 << (len - 1);
	while (key & step) {
	step >>= 1;
	}
	return step ? (key & (step - 1)) + step : key;
	}

	// Stores code in table[0], table[step], table[2*step], ..., table[end].
	// Assumes that end is an integer multiple of step.
	static WEBP_INLINE void ReplicateValue(HuffmanCode* table,
	int step, int end,
	HuffmanCode code) {
	assert(end % step == 0);
	do {
	end -= step;
	table[end] = code;
	} while (end > 0);
	}

	// Returns the table width of the next 2nd level table. count is the histogram
	// of bit lengths for the remaining symbols, len is the code length of the next
	// processed symbol
	static WEBP_INLINE int NextTableBitSize(const int* const count,
	int len, int root_bits) {
	int left = 1 << (len - root_bits);
	while (len < MAX_ALLOWED_CODE_LENGTH) {
	left -= count[len];
	if (left <= 0) break;
	++len;
	left <<= 1;
	}
	return len - root_bits;
	}

	// sorted[code_lengths_size] is a pre-allocated array for sorting symbols
	// by code length.
	static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
	const int code_lengths[], int code_lengths_size,
	uint16_t sorted[]) {
	HuffmanCode* table = root_table; // next available space in table
	int total_size = 1 << root_bits; // total size root table + 2nd level table
	int len; // current code length
	int symbol; // symbol index in original or sorted table
	// number of codes of each length:
	int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
	// offsets in sorted table for each length:
	int offset[MAX_ALLOWED_CODE_LENGTH + 1];

	assert(code_lengths_size != 0);
	assert(code_lengths != NULL);
	assert((root_table != NULL && sorted != NULL) \|\|
	(root_table == NULL && sorted == NULL));
	assert(root_bits > 0);

	// Build histogram of code lengths.
	for (symbol = 0; symbol < code_lengths_size; ++symbol) {
	if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
	return 0;
	}
	++count[code_lengths[symbol]];
	}

	// Error, all code lengths are zeros.
	if (count[0] == code_lengths_size) {
	return 0;
	}

	// Generate offsets into sorted symbol table by code length.
	offset[1] = 0;
	for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) {
	if (count[len] > (1 << len)) {
	return 0;
	}
	offset[len + 1] = offset[len] + count[len];
	}

	// Sort symbols by length, by symbol order within each length.
	for (symbol = 0; symbol < code_lengths_size; ++symbol) {
	const int symbol_code_length = code_lengths[symbol];
	if (code_lengths[symbol] > 0) {
	if (sorted != NULL) {
	sorted[offset[symbol_code_length]++] = symbol;
	} else {
	offset[symbol_code_length]++;
	}
	}
	}

	// Special case code with only one value.
	if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
	if (sorted != NULL) {
	HuffmanCode code;
	code.bits = 0;
	code.value = (uint16_t)sorted[0];
	ReplicateValue(table, 1, total_size, code);
	}
	return total_size;
	}

	{
	int step; // step size to replicate values in current table
	uint32_t low = 0xffffffffu; // low bits for current root entry
	uint32_t mask = total_size - 1; // mask for low bits
	uint32_t key = 0; // reversed prefix code
	int num_nodes = 1; // number of Huffman tree nodes
	int num_open = 1; // number of open branches in current tree level
	int table_bits = root_bits; // key length of current table
	int table_size = 1 << table_bits; // size of current table
	symbol = 0;
	// Fill in root table.
	for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
	num_open <<= 1;
	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;
	code.bits = (uint8_t)len;
	code.value = (uint16_t)sorted[symbol++];
	ReplicateValue(&table[key], step, table_size, code);
	key = GetNextKey(key, len);
	}
	}

	// Fill in 2nd level tables and add pointers to root table.
	for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;
	++len, step <<= 1) {
	num_open <<= 1;
	num_nodes += num_open;
	num_open -= count[len];
	if (num_open < 0) {
	return 0;
	}
	for (; count[len] > 0; --count[len]) {
	HuffmanCode code;
	if ((key & mask) != low) {
	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;
	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);
	}
	key = GetNextKey(key, len);
	}
	}

	// Check if tree is full.
	if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
	return 0;
	}
	}

	return total_size;
	}

	// Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_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(HuffmanTables* const root_table, int root_bits,
	const int code_lengths[], int code_lengths_size) {
	const int total_size =
	BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
	assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
	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];
	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;
	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;
	}
	}