QccENTHuffmanTablePrint.3

NAME

QccENTHuffmanTable - data structure QccENTHuffmanTable and corresponding HUF file format for Huffman encoding and decoding

int QccENTHuffmanTableInitialize(QccENTHuffmanTable *table);
int QccENTHuffmanTableAlloc(QccENTHuffmanTable *table);
void QccENTHuffmanTableFree(QccENTHuffmanTable *table);
int QccENTHuffmanTablePrint(const QccENTHuffmanTable *table);
int QccENTHuffmanTableRead(QccENTHuffmanTable *table);
int QccENTHuffmanTableWrite(QccENTHuffmanTable *table);

DESCRIPTION

QccPack provides data structure QccENTHuffmanTable for representing the Huffman code table to use in Huffman encoding and decoding.

The main component of a QccENTHuffmanTable is an array of QccENTHuffmanTableEntry entries (see below). Each of these entries contain a source symbol (an integer) and its correspoding Huffman codeword.

DATA STRUCTURE

The QccENTHuffmanTable data structure is defined as:

typedef struct
{
QccString filename;
QccString magic_num;
int major_version;
int minor_version;
int table_type;
int table_length;
QccENTHuffmanTableEntry *table;
int *num_codewords_list;
int num_codewords_list_length;
int *symbol_list;
int symbol_list_length;
int codeword_max[QCCENTHUFFMAN_MAXCODEWORDLEN];
int codeword_min[QCCENTHUFFMAN_MAXCODEWORDLEN];
int codeword_ptr[QCCENTHUFFMAN_MAXCODEWORDLEN];
} QccENTHuffmanTable;

The fields of QccENTHuffmanTable are as follows:

filename: For tables associated with a file, this is the name of the file.
magic_num, major_version, minor_version: For tables associated with a file, these are the magic number and version of the file.
table_type: the type of the table, QCCENTHUFFMAN_DECODETABLE for a decoding table, QCCENTHUFFMAN_ENCODETABLE for an encoding table.
table_length: the number of entries in the table
table: the table of symbols and codewords
num_codewords_list, num_codewords_list_length,: symbol_list, symbol_list_length arrays and array lengths used for creating the Huffman table; see QccENTHuffmanTableCreateDecodeTable(3)
codeword_max, codeword_min, codeword_ptr: auxiliary arrays used for QCCENTHUFFMAN_DECODETABLE type tables for the Huffman decoding process (for internal QccPack use only)

The QccENTHuffmanTableEntry data structure, used to hold source symbols and their corresponding codewords is defined as:

typedef struct
{
int symbol;
QccENTHuffmanCodeword codeword;
} QccENTHuffmanTableEntry;

The fields of QccENTHuffmanTableEntry are as follows:

symbol: the source symbol represented as an integer greater than or equal to 0 and less than or equal to QCCENTHUFFMAN_MAXSYMBOL
codeword: the Huffman codeword

The QccENTHuffmanCodeword data structure, used to hold the Huffman codeword itself, is defined as:

typedef struct
{
int length;
int codeword;
} QccENTHuffmanCodeword;

The fields of
QccENTHuffmanCodeword are as follows:

length: the length, in bits, of the codeword
codeword: the actual Huffman codeword, stored in the least-significant
length bits of the
codeword integer; the most-significant bit of the Huffman codeword (i.e.,
at the "root" of the Huffman tree and the first bit to be output
during the encoding of the corresponding symbol) is stored in the
left-most position

FILE FORMAT

For reading and writing structures of type QccENTHuffmanTable, QccPack provides the HUF file format. This file format starts with an ASCII header followed by ASCII data. The ASCII header consists of magic-number/revision information followed by any amount of white space (space, `\t' (tab), `\n' (newline), `\r' (return)) and/or comments lines (lines starting with `#'). Following this white space, additional ASCII header information is given, separated by blanks and newlines. ASCII data follows this ASCII header information.

The HUF file format consists of the following information:

HUFX.X
<white space>
num_codewords_list_length
symbol_list_length
num_codewords_list
.
.
.
symbol_list
.
.
.

where HUF is the magic number, X.X is the version number, <white space> is white space and/or comment lines, num_codewords_list_length is the length of the num_codewords_list to appear later in the file, and symbol_list_length is the length of the symbol_list to appear later in the file. num_codewords_list is the list of the number of codewords, starting with length 1. symbol_list is the list of symbols (in decimal integers) corresponding to the codewords.

For example, if the Huffman table has the following symbols and codewords,

Symbol Codeword Length Codeword
-------------------------------------------
'a' 2 00
'b' 2 01
'c' 3 100
'd' 4 1010
'e' 4 1011

the corresponding HUF-format file would be:

HUFX.X
# Optional comment(s) here
4
5
0 <----- Start with length = 1
2
1
2
97 <----- Decimal integer representation of symbols
98
99
100
101

Note: the stuff starting with the "<----" arrows is merely an annotation and is not actually a legal part of the file.

ROUTINES

QccENTHuffmanTableInitialize() should be called before any use of a QccENTHuffmanTable structure. QccENTHuffmanTableInitialize() initializes the fields of table to the following values:

table_type: QCCENTHUFFMAN_DECODETABLE
table: NULL
table_length: 0

QccENTHuffmanTableAlloc() allocates the Huffman table. table_length must be set before calling QccENTHuffmanTableAlloc().

QccENTHuffmanTableFree() frees the table array.

QccENTHuffmanTablePrint() prints the contents of table to stdout.

QccENTHuffmanTableRead() reads a Huffman table from a HUF-format file. table is returned as either a decoding or encoding table; set table->table_type to either QCCENTHUFFMAN_ENCODETABLE or QCCENTHUFFMAN_DECODETABLE, respectively, before calling QccENTHuffmanTableRead(). QccENTHuffmanTableRead() reads the list of numbers of codewords and the list of symbols from the file whose name is given by table->filename (must be set before calling QccENTHuffmanTableRead()) and then calls either QccENTHuffmanTableCreateEncodeTable(3) or QccENTHuffmanTableCreateDecodeTable(3) , as appropriate, to generate the actual table, table->table, of Huffman codewords.

QccENTHuffmanTableWrite() writes the Huffman table, table, to the HUF-format file whose name is given in table->filename. Usually, table will be either an encoding table (table->table_type = QCCENTHUFFMAN_ENCODETABLE) or a decoding table (table->table_type = QCCENTHUFFMAN_DECODETABLE) that was created by a call to QccENTHuffmanDesign(3) .

RETURN VALUE

These routines return 0 on success, and 1 on failure.

AUTHOR

Table of Contents

NAME
SYNOPSIS
DESCRIPTION
DATA STRUCTURE
FILE FORMAT
ROUTINES
RETURN VALUE
SEE ALSO
AUTHOR