rbthuff.h File Reference

Huffman code generated from a red-black tree. More...

#include "rbtree.h"

Typedefs
typedef void *(*	rbthuff_alloc_fn) (size_t size, void *alloc_data)
	Function type called to allocate memory for Huffman code structures. More...
typedef void(*	rbthuff_free_fn) (void *what, size_t size, void *alloc_data)
	Function type called to free memory allocated for Huffman code structures. More...
typedef struct huffcode	HUFFCODE
	An opaque Huffman code structure. More...

Functions
RBT_ROOT *	rbt_huff_init (void *data, rbt_alloc_fn alloc_fn, rbt_free_fn free_fn, rbt_compare_keys_fn compare_keys, size_t key_length)
	Initialise a new Red-Black tree representing an alphabet that will be Huffman coded. More...
uint32	rbthuff_get_seqnum (RBT_NODE *node)
	Accessor for a sequence number for a Huffman tree node. More...
HqBool	rbthuff_make_code (RBT_ROOT *root, HUFFCODE **hcode, rbthuff_alloc_fn alloc_fn, rbthuff_free_fn free_fn, void *alloc_data)
	Given a Red-Black tree, in which each node represents a character in the alphabet to be encoded and contains its frequency (exact probability, if you like), construct a Huffman code structure to represent the alphabet. More...
size_t	rbthuff_code_size (HUFFCODE *hcode)
	Returns to overall memory size of a Huffman code structure. More...
void	rbthuff_free_code (HUFFCODE *hcode, rbthuff_free_fn free_fn, void *alloc_data)
	Frees a Huffman code structure previously allocated by rbthuff_make_code(). More...
void	rbthuff_encode (RBT_NODE *node, uint8 *buf, uint32 *bitcount)
	Huffman encode the single character represented by a node in the tree. More...
void	rbthuff_encodebit (HqBool flag, uint8 *buf, uint32 *bitcount)
	Encode a single bit representing a boolean flag into the stream. More...
uint32	rbthuff_decode (uint8 *buf, uint32 *bitcount, HUFFCODE *hcode)
	Decode a single Huffman-encoded character from the given bit stream buf, starting at position *bitcount. More...
HqBool	rbthuff_decodebit (uint8 *buf, uint32 *bitcount)
	Extract exactly one bit from the encoded stream, representing a boolean flag stored by rbthuff_encodebit(). More...
HqBool	rbthuff_increment_char (RBT_ROOT *root, uintptr_t key)
	Increment the frequency count for the character identified by the given key. More...
uint32	rbthuff_get_char_count (RBT_NODE *node)
	Get the current count for a given node. More...
void	rbthuff_set_char_count (RBT_NODE *node, uint32 count)
	Set the current count for a given node. More...
HqBool	rbthuff_count_bits (RBT_ROOT *root, RBT_NODE *node, void *walk_data)
	Tree walking callback function to count the bits which will be used in the compressed output. More...

Detailed Description

Huffman code generated from a red-black tree.

For generating a very compact representation of a data set using a red-black tree as the intermediate representation of its alphabet. Since the exact frequency of each character in the alphabet is known at the time of the creation of the code, the Huffman code ought to be exactly optimal.

Note

The use of 'character' in the descriptions of the Huffman tree describe any object represented by an equivalence key with an associated frequency count. This is in the technical sense of the reference literature, not in the C type system. Objects of any type whose key can be compared equal by reference or by value can be stored and encoded in the Huffman tree.

Copyright (C) 2023 Global Graphics Software Ltd. All rights reserved. This source code contains the confidential and trade secret information of Global Graphics Software Ltd. It may not be used, copied or distributed for any reason except as set forth in the applicable Global Graphics license agreement.

Typedef Documentation

HUFFCODE

typedef struct huffcode HUFFCODE

An opaque Huffman code structure.

Huffman code structures are created by rbthuff_make_code() and destroyed by rbthuff_destroy_code(). Allocations for the Huffman code structure are managed using callback functions of the rbthuff_alloc_fn and rbthuff_free_fn types, as passed to rbthuff_make_code().

rbthuff_alloc_fn

typedef void*(* rbthuff_alloc_fn) (size_t size, void *alloc_data)

Function type called to allocate memory for Huffman code structures.

Parameters

size	The number of bytes to allocate
alloc_data	The private opaque data pointer from the Huffman code node.

Returns

A newly-allocated block of memory, or NULL if none is available.

rbthuff_free_fn

typedef void( * rbthuff_free_fn) ( void *what, size_t size, void *alloc_data)

Function type called to free memory allocated for Huffman code structures.

Parameters

what	Pointer to a memory block previously allocated through the tree's rbthuff_alloc_fn.
size	The size of the memory block, as initially requested from the tree's rbthuff_alloc_fn.
alloc_data	The private opaque data pointer from the Huffman code node.

Function Documentation

rbt_huff_init()

RBT_ROOT* rbt_huff_init	(	void *	data,
		rbt_alloc_fn	alloc_fn,
		rbt_free_fn	free_fn,
		rbt_compare_keys_fn	compare_keys,
		size_t	key_length
	)

Initialise a new Red-Black tree representing an alphabet that will be Huffman coded.

Parameters

data	An opaque data pointer passed to the callback functions.
alloc_fn	A callback function to allocate memory for the tree nodes, keys, and data.
free_fn	A callback function to free memory for the tree nodes, keys, and data.
compare_keys	A callback function to compare keys.
key_length	The size of the node keys. If this is zero, keys are stored by reference (and therefore if keys are pointers to objects, they must have lifetimes at least as long as the nodes they are used for are stored in the tree). If non-zero, keys will be copied into storage allocated in the tree nodes.

Returns

A new tree root, or NULL if the allocations failed.

rbthuff_code_size()

size_t rbthuff_code_size

(

HUFFCODE *

hcode

)

Returns to overall memory size of a Huffman code structure.

Parameters

hcode

The Huffman code structure to calculate the size of.

Returns

The size in bytes of hcode.

This function is provided for memory accounting and low memory actions. The Huffman code structure represented in hcode is not stored contiguously in memory.

rbthuff_count_bits()

HqBool rbthuff_count_bits	(	RBT_ROOT *	root,
		RBT_NODE *	node,
		void *	walk_data
	)

Tree walking callback function to count the bits which will be used in the compressed output.

Parameters

root	The root of the Huffman tree.
node	The node in the tree being traversed.
walk_data	A pointer to a uint32 count, used to accumulate the code length for the characters in the alphabet multiplied by the occurrence count of the characters.

This function should be used as the callback function to rbt_walk(), to calculate the total number of bits required to encode the nodes counted by the Huffman tree. e.g.,

uint32 totalbits = 0 ;
uint8 *buffer ;
if ( rbt_walk(huffroot, rbthuff_count_bits, &totalbits) &&
     (buffer = malloc((totalbits + 7) / 8)) != NULL ) {
  uint32 bitcount = 0 ;
  ...repeated calls to rbthuff_encode(node, buf, &bitcount)...
  HQASSERT(bitcount == totalbits, "Frequency mismatch for Huffman tree");
} else {
  ...handle malloc() failure: rbt_walk() will not fail.
}

rbthuff_decode()

uint32 rbthuff_decode	(	uint8 *	buf,
		uint32 *	bitcount,
		HUFFCODE *	hcode
	)

Decode a single Huffman-encoded character from the given bit stream buf, starting at position *bitcount.

Parameters

[in]	buf	A buffer of bytes, containing the bitstream to be decoded.
[in,out]	bitcount	A pointer to the current bit index in buf. This will be updated with a new bit index on exit.
[in]	hcode	The Huffman code table generated by rbthuff_make_code() for the alphabet encoded in buf.

Returns

Returns the index of the character into the lookup table associated with hcode, and updates *bitcount appropriately.

Note

It is the caller's responsibility to ensure that the stream is long enough.

rbthuff_decodebit()

HqBool rbthuff_decodebit	(	uint8 *	buf,
		uint32 *	bitcount
	)

Extract exactly one bit from the encoded stream, representing a boolean flag stored by rbthuff_encodebit().

Parameters

[in]	buf	A buffer of bytes, containing the bitstream to be decoded.
[in,out]	bitcount	A pointer to the current bit index in buf. This will be updated with a new bit index on exit.

This is not strictly part of any Huffman code, but is designed as a shortcut for interleaving Booleans with encoded characters.

rbthuff_encode()

void rbthuff_encode	(	RBT_NODE *	node,
		uint8 *	buf,
		uint32 *	bitcount
	)

Huffman encode the single character represented by a node in the tree.

Parameters

	node	The tree node representing the character to encode.
[in,out]	buf	An output buffer to receive bits representing the encoded node's character.
[in,out]	bitcount	A pointer to the current bit count in buf. This will be updated with a new bit count on exit.

This function must be called after rbthuff_make_code().

It writes bits to the output buffer buf starting at bit *bitcount (whose smallest valid value is zero), and increments *bitcount appropriately. This routine is called repeatedly to encode consecutive characters in a message, but must be preceded by a single initializing call to rbthuff_make_code() to constructs the optimal encoding for the alphabet.

The buffer size required for the counts encoded in the tree can be calculated by calling rbt_walk() with the rbthuff_count_bits() callback function.

See also

rbthuff_count_bits().

rbthuff_encodebit()

void rbthuff_encodebit	(	HqBool	flag,
		uint8 *	buf,
		uint32 *	bitcount
	)

Encode a single bit representing a boolean flag into the stream.

Parameters

	flag	The flag to encode.
[in,out]	buf	An output buffer to receive the encoded flag value.
[in,out]	bitcount	A pointer to the current bit count in buf. This will be updated with a new bit count on exit.

This is not strictly part of a Huffman code, but it's a useful way of interleaving encoded characters with flags in one package.

rbthuff_free_code()

void rbthuff_free_code	(	HUFFCODE *	hcode,
		rbthuff_free_fn	free_fn,
		void *	alloc_data
	)

Frees a Huffman code structure previously allocated by rbthuff_make_code().

Parameters

hcode	A previously allocated Huffman code, constructed by rbthuff_make_code().
free_fn	A deallocator callback function used to destroy the tree tables which represent the code.
alloc_data	An opaque data pointer passed to the deallocator callback function.

rbthuff_get_char_count()

uint32 rbthuff_get_char_count

(

RBT_NODE *

node

)

Get the current count for a given node.

Parameters

node	The node to get the current count of.

Returns

The current value of the count for node.

rbthuff_get_seqnum()

uint32 rbthuff_get_seqnum

(

RBT_NODE *

node

)

Accessor for a sequence number for a Huffman tree node.

Parameters

node	The tree node to get the sequence number for.

Returns

The sequence number of the node.

The sequence number for the node is an ordinal identifying the node uniquely. It can be used as an index into arrays of length rbt_node_count() to compute frequency properties or other characteristics of the alphabet stored in the tree.

rbthuff_increment_char()

HqBool rbthuff_increment_char	(	RBT_ROOT *	root,
		uintptr_t	key
	)

Increment the frequency count for the character identified by the given key.

Parameters

root	The root of the Huffman tree.
key	The key representing this character in the alphabet represented by the tree. This can be stored and compared by reference or by value, according to the key_length and compare_keys parameters passed to rbt_huff_init().

If this is the first reference to this character, add a new node for it in the tree.

This function should be called before rbthuff_make_code() to generate an optimal encoding. The node counts must be correct before rbthuff_count_bits() is used to calculate an accurate total encoding length.

Return values

TRUE	The character count was incremented.
FALSE	The character was not already referenced in the tree, and a new node could not be added to the tree because of a memory allocation failure.

rbthuff_make_code()

HqBool rbthuff_make_code	(	RBT_ROOT *	root,
		HUFFCODE **	hcode,
		rbthuff_alloc_fn	alloc_fn,
		rbthuff_free_fn	free_fn,
		void *	alloc_data
	)

Given a Red-Black tree, in which each node represents a character in the alphabet to be encoded and contains its frequency (exact probability, if you like), construct a Huffman code structure to represent the alphabet.

Parameters

[in]	root	The Red-Black tree containing the alphabet to be encoded.
[out]	hcode	A new allocated Huffman code optimally representing the encoded alphabet.
	alloc_fn	An allocator callback function used to create the tree tables which represent the code.
	free_fn	A deallocator callback function used to destroy the tree tables which represent the code.
	alloc_data	An opaque data pointer passed to the allocator callback function it so the caller can control lifetime etc.

Return values

TRUE	If the function succeeded, and a newly-constructed Huffman code was stored in hcode.
FALSE	if the function failed.

rbthuff_set_char_count()

void rbthuff_set_char_count	(	RBT_NODE *	node,
		uint32	count
	)

Set the current count for a given node.

Parameters

node	The node to set the current count for.
count	The new value for the count in node.

If the Huffman tree is representing objects that are individually encountered, consider using rbthuff_increment_char() instead of this function. This function should be called before rbthuff_make_code() to generate an optimal encoding. The node counts must be correct before rbthuff_count_bits() is used to calculate an accurate total encoding length.