A simple video codec.
/*
runhuf.cpp
Contains functions for Huffman and run-level encoding and decoding.
See http://www.webkinesia.com/games/vcompress8.php
*/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <set>
#include "fbitios.h"
#include "runhuf.h"
//for zig zag reordering
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
};
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];
}
/*
Input: 8x8 sample block in Y[]
Output: 3D run-level codewords in runs[]
*/
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; Note: no codeword is a prefix of another
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++;
}
}
/*
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, hypothetical here )
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;
}