Sample program for testing Huffman encoding of DCT coefficients.
/*
test_huf.cpp
For testing the use of pre-caculated Huffman codewords to encode and decode
3D run-level tuples.
Compile: g++ -o test_huf test_huf.cpp fbitios.o
Execute:
./test_huf
This reads in DCT coefficients from "sample_video.dct", quantizes, reorders, run-level encodes
and Huffman encodes. The Huffman-encoded bitstream is saved in "sample_video.huf".
./test_huf d
This reads in encoded bitstream from "sample_video.huf", Huffman decodes, run-level decodes,
reverses reordering, inverse quantizes and saves the decoded data in "sample_video.dec".
./test_huf t
Similar to "d" but decodes block by block interactively and prints out the decoded DCT blocks.
See http://www.webkinesia.com/games/vcompress7.php
*/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <set>
#include "fbitios.h"
#define NSymbols 256
using namespace std;
short Qstep = 12;
typedef struct {
unsigned char run;
short level;
char last;
} run3D;
class RunHuff {
public:
run3D r;
unsigned int codeword;
char hlen; //length of Huffman code
short index; //table index where codeword saved
RunHuff() {} //constructors
RunHuff ( run3D a, unsigned c, char len, short idx ) { r = a, codeword = c, hlen = len; index = idx; }
//'<' operator is to order run-level tuples so that they can be saved in a binary tree ( set )
friend bool operator < ( RunHuff left, RunHuff right ) {
if ( left.r.run < right.r.run )
return true;
if ( left.r.run > right.r.run )
return false;
//run equals
if ( left.r.level < right.r.level )
return true;
if ( left.r.level > right.r.level )
return false;
//both run and level equal
if ( left.r.last > right.r.last )
return true;
return false; //so, the left object is not smaller than the right
}
};
unsigned char zigzag[64] = {
0, 1, 8, 16, 9, 2, 3, 10,
17, 24, 32, 25, 18, 11, 4, 5,
12, 19, 26, 33, 40, 48, 41, 34,
27, 20, 13, 6, 7, 14, 21, 28,
35, 42, 49, 56, 57, 50, 43, 36,
29, 22, 15, 23, 30, 37, 44, 51,
58, 59, 52, 45, 38, 31, 39, 46,
53, 60, 61, 54, 47, 55, 62, 63
};
short get64 ( short Y[], FILE *fp )
{
short n;
n = fread ( Y, 2, 64, fp );
return n;
}
short put64 ( short Y[], FILE *fp )
{
short n;
n = fwrite ( Y, 2, 64, fp );
return n;
}
void print_block ( short s[] )
{
short k = 0;
for ( short i = 0; i < 8; ++i ) {
printf("\n");
for ( short j = 0; j < 8; ++j ) {
printf("%6d", s[k++] );
}
}
printf("\n");
}
void quantize_block ( short coef[] )
{
for ( short k = 0; k < 64; ++k ) {
coef[k] = ( short ) round ( (double)coef[k] / Qstep );
}
}
void inverse_quantize_block ( short coef[] )
{
for ( short k = 0; k < 64; ++k ) {
coef[k] = coef[k] * Qstep;
}
}
void reorder ( short Y[], short Yr[] )
{
for ( short k = 0; k < 64; ++k ) {
Yr[k] = Y[zigzag[k]];
}
}
void reverse_reorder ( short Yr[], short Y[] )
{
for ( short k = 0; k < 64; ++k ) {
Y[zigzag[k]] = Yr[k];
}
}
void run_block ( short Y[], run3D runs[] )
{
short run_length = 0, k = 0;
for ( short i = 0; i < 64; ++i ) {
if ( Y[i] == 0 ) {
run_length++;
continue;
}
//Y[i] != 0
runs[k].run = (unsigned char) run_length;
runs[k].level = Y[i];
runs[k].last = 0;
run_length = 0;
k++;
} //for i
if ( k > 0 )
runs[k-1].last = 1; //last nonzero element
else { //whole block 0
runs[0].run = 64;
runs[0].level = 0;
runs[0].last = 1;
}
}
void print_run( run3D runs[] )
{
short k = 0, len = 0, count = 0;
while ( len < 64 ) {
if ( count % 4 == 0 ) printf("\n");
printf( "(%2d, %4d, %1d) ", runs[k].run, runs[k].level, runs[k].last );
len += runs[k].run;
++len;
if ( runs[k].last ) break;
count++;
k++;
}
printf("\n");
}
void run_decode ( run3D runs[], short Y[] )
{
short i, j, k = 0;
i = 0;
while ( i < 64 ) {
for ( j = 0; j < runs[k].run; ++j )
Y[i++] = 0;
if ( i < 64 )
Y[i++] = runs[k].level;
if ( runs[k].last ) break;
k++;
}
//run of 0s to end
if ( i < 64 ) {
bzero ( Y + i, sizeof(Y[0]) * ( 64-i) );
}
}
//use a set ( htable ) to collect all pre-calculated run-level and Huffman codewords
void build_htable ( set<RunHuff> &htable )
{
short i, j, k, N = 10; //N is the number of pre-calculated codewords of positive levels
char hlen[] = { 2, 3, 4, 4, 4, 5, 5, 5, 6, 7 }; //lengths of Huffman codewords ( not including sign-bit )
//Huffman codewords, 0x60 is ESC
unsigned short hcode[] = { 0x01, 0x3, 0x7, 0xf, 0xe, 0x16, 0x6, 0x1a, 0x2a, 0x60 };
unsigned char runs[] = { 0, 1, 2, 0, 0, 3, 4, 5, 0, 255 }; //255 signifies ESC
short levels[] = { 1, 1, 1, 2, 1, 1, 1, 1, 3, 0 }; //level of 3D run-level tuple
char lasts[] = { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }; //last of 3D run-level tuple
run3D r; //a 3D run-level codeword ( tuple )
RunHuff rf[128]; //table containing RunHuff objects
k = 0; j = 0;
for ( i = 0; i < N; ++i ) {
r.run = runs[i];
r.level = levels[i];
r.last = lasts[i];
rf[k++] = RunHuff ( r, hcode[i] << 1, hlen[i], j++ ); //construct a RunHuff object, positive level, so sign=0
r.level = -r.level; //do the same thing for negative level
rf[k++] = RunHuff ( r, (hcode[i]<<1) | 1, hlen[i], j++ ); //level negative, so sign = 1
}
k = 2 * N; //insert all 2N ( positive and negative levels ) RunHuff objects into htable
for ( i = 0; i < k; ++i )
htable.insert ( rf[i] );
}
void print_htable ( set<RunHuff> &htable )
{
set<RunHuff>::iterator itr;
short i;
printf("\n(run, level, last), \tCodeword\tHuff Code Length, index");
for ( i = 0; i < htable.size(); ++i ) {
for ( itr = htable.begin(); itr != htable.end(); ++itr ) {
if ( itr->index == i )
break;
}
printf("\n(%4d, %4d, %d), \t%8x, %x\t%12d,\t%12d", itr->r.run, itr->r.level, itr->r.last,
itr->codeword, itr->codeword >> 1, itr->hlen, itr->index );
}
}
void escape_encode ( bitFileIO &outputs, run3D &r )
{
if ( r.level < 0 ) { //value of level negative
outputs.outputBit ( 1 ); //output sign-bit first
r.level = -r.level; //change level value to positive
} else
outputs.outputBit ( 0 ); //value of level negative
outputs.outputBits ( 0x60, 7 ); //ESCAPE code
if ( r.run == 64 ) r.run = 63; //r.level differentiates between if last element nonzero
outputs.outputBits ( r.run, 6 ); //6 bits for run value
outputs.outputBits ( r.level, 8 ); //8 bits for level value
outputs.outputBit ( r.last ); //1 bit for last value
}
/*
Inputs: htable contains all the pre-calculated Huffman codewords of 3D run-level tuples
runs[] contains the 3D run-level tuples of a macroblock of quantized DCT coefficients
Outputs:bitstreams of codewords ( Huffman + sign or ESCAPE + 3D run-level ) to bitFileIO outputs
*/
void huff_encode ( set<RunHuff> &htable, run3D runs[], bitFileIO &outputs )
{
short i, j, k;
k = 0;
set<RunHuff>::iterator itr; //iterator to traverse htable
i = 0;
while ( i < 64 ) { //a macroblock has at most 64 samples
RunHuff rf ( runs[k], 0, 0, 0 ); //construct a RunHuff object; only runs[k] is relevant
//as it is used for searching ( we've defined '<' in RunHuff class )
if ( (itr = htable.find ( rf )) != htable.end() ) //found
outputs.outputBits ( itr->codeword, itr->hlen + 1);
else //not found
escape_encode( outputs, rf.r ); //need to 'escape encode' the 3D run-level tuple
if ( runs[k].last ) break; //end of run-level codewords
i += ( runs[k].run + 1 ); //for handling the special case of whole block of run being 0
k++;
}
}
class Dtables {
public:
short huf_tree[1024]; //table containing Huffman Tree
run3D run_table[512]; //table containing run-level codewords
};
/*
Input: htable, a set containing all pre-calculated Huffman codewords of 3D run-level tuples
Outputs: d.huf_tree[], the Huffman tree containing pointers and indices pointing to run-level tuples
d.run_table[], the table that contains the run-level tuples ( codewords )
*/
void build_huff_tree ( set<RunHuff> &htable, Dtables &d )
{
set<RunHuff>::iterator itr; //iterator to traverse set htable
short i, j, n0, free_slot, loc, loc0, root, ntotal;
unsigned int mask, hcode;
n0 = NSymbols; //number of symbols ( = number of leaves in tree )
ntotal = 2 * n0 - 1; //Huffman tree has n0 - 1 internal nodes
root = 3 * n0 - 3; //location of root ( see section 21 ), offset n0 has been added
free_slot = root - 2; //next free table entry for filing in with a pointer or an index
// ( note: root has root_left, root_right )
for ( i = 0; i < ntotal; ++i ) //initialize the table
d.huf_tree[i] = -1; //all entries empty
for ( itr = htable.begin(); itr != htable.end(); ++itr ) { //consider all codewords in the set htable
if ( itr->r.level < 0 ) continue; //only save positive levels of run-level codeword
d.run_table[itr->index/2]=itr->r; //save run-level codeword; index divided by 2 as only postive levels saved
loc = root; //always start from root
mask = 0x01; //for examining bits of Huffman codeword
hcode = itr->codeword >> 1; //the rightmost bit is sign-bit, not part of Huffman
for ( i = 0; i < itr->hlen; ++i ){ //traverse the Huffman codeword
loc0 = loc - n0; //everything shifted by offset n0
if ( i == ( itr->hlen - 1 ) ){ //last bit, should point to leaf
if ( (mask & hcode) == 0 ) //a 0, save it at 'left' leaf
d.huf_tree[loc0] = itr->index/2;
else //a 1, save it at 'right' leaf
d.huf_tree[loc0-1] = itr->index/2;
continue; //get out of for i for loop, consider next codeword
}
if ( (mask & hcode) == 0 ){ //a 0 ( go left )
if (d.huf_tree[loc0] == -1){ //slot empty
d.huf_tree[loc0] = free_slot; //point to left new child
free_slot -= 2; //next free table entry
} //else : already has left child
loc = d.huf_tree[loc0]; //follow the left child
} else { //a 1 ( go right )
if (d.huf_tree[loc0-1]== -1){ //slot empty
d.huf_tree[loc0-1]=free_slot;//point to right new child
free_slot -= 2;
} //else: already has right child
loc = d.huf_tree[loc0-1]; //follow the right child
}
mask <<= 1; //consider next bit
} //for i
} //for itr
} //build_huff_tree()
/*
Inputs: bf, the encoded bitstream to be decoded
d.huf_tree[], table containing the Huffman tree
d.run_table[], table containing the actual run-level codewords
Output: runs[], table containing the run-level tuples of a macroblock
*/
short huff_decode( bitFileIO &bf, Dtables &d, run3D runs[] )
{
short n0, loc, loc0, root, k;
char c, sign;
bool done = false;
run3D r;
n0 = NSymbols; //number of symbols
root = 3 * n0 - 3; //points to root of tree
k = 0;
while ( !done ) {
loc = root; //starts from root
sign = bf.inputBit(); //sign-bit
do {
loc0 = loc - n0;
c = bf.inputBit(); //read one bit
if (c < 0) {done = true; break;} //no more data, done
if ( c == 0 ) //a 0, go left
loc = d.huf_tree[loc0];
else //a 1, go right
loc = d.huf_tree[loc0-1];
} while ( loc >= n0 ); //traverse until reaches leaf
r = d.run_table[loc];
if ( r.run == 255 ) { //ESCAPE code, read actual run-level tuple
r.run = bf.inputBits ( 6 ); //read 6 bits for run
r.level = bf.inputBits ( 8 ); //read 8 bits for level
r.last = bf.inputBit(); //read 1 bit for last
if ( sign ) //if sign is 1, level should be negative
r.level = -r.level;
} else { //not ESCAPE code
if ( sign ) //1 => negative
r.level = -r.level;
}
if ( (r.run == 63) && (r.level == 0) ) r.run = 64; //whole block 0
runs[k++] = r; //save tuple in table runs[]
if ( r.last ) //end of macroblock
break;
} //while
if ( done ) return -1; //if ( done ) => no more data
else return 1;
}
int main( int argc, char *argv[] )
{
FILE *fp;
set <RunHuff> htable;
run3D runs[64];
short Y[64], Yr[64];
bool tracing = false;
if ( argc > 1 ) { //decoding or tracing
if ( strcmp ( argv[1], "t" ) == 0 )
tracing = true;
else if ( strcmp ( argv[1], "d" ) ) {
printf("\nUsage: test_huf [d|t]\n");
return 1;
}
//decoding
FILE *fpo = fopen ( "sample_video.dec", "wb" );
if ( fpo == NULL ) {
printf("\nError opening file\n");
return 1;
}
build_htable ( htable );
if ( tracing )
print_htable ( htable );
Dtables decode_tables; //tables used in decoding process
bitFileIO bf("sample_video.huf",1); //construct bitstream for input
build_huff_tree ( htable, decode_tables );
while ( huff_decode( bf, decode_tables, runs ) > 0 ){
run_decode ( runs, Yr );
reverse_reorder ( Yr, Y );
inverse_quantize_block ( Y );
put64 ( Y, fpo );
if ( tracing ) {
print_block ( Y );
printf("\nDo you want another block? ( y/n) ");
char c1;
scanf ( "%c", &c1 );
if ( c1 == 'n' ) break;
}
}
bf.closeInput();
fclose ( fpo );
return 0;
}
//encoding
fp = fopen ( "sample_video.dct", "rb" );
if ( fp == NULL ) {
printf("\nError opening file\n");
return 1;
}
bitFileIO outputs ( "sample_video.huf", 0 ); //construct bitstream for output
while ( get64 ( Y, fp ) > 0 ) {
quantize_block ( Y );
reorder ( Y, Yr );
run_block ( Yr, runs );
huff_encode ( htable, runs, outputs ); //encode and save
}
fclose ( fp );
outputs.closeOutput();
}