#!/usr/bin/perl

###
# Includes
###
use GD;
use Math::FFT;
use Math::MatrixReal;

my @Yvals;
my @CbVals;
my @CrVals;
my $walking = 1;
my $cs = `clear`;
print $cs if $walking;



### 
# Grab image info
###
my $pic = 'kblock.png';
my $truecolor = '1';
my $img = GD::Image->newFromPng($pic, $truecolor);
my ($width, $height) = $img->getBounds();
my $wblock = ($width / 8);
my $hblock = ($height / 8);
my $blocks = ($wblock * $hblock);
my $ct = 0;


###
# Here we do the conversion from RGB to YUV
# Colorspace. We're performing the level shift
# right away to make things smoother. 
###
for ($x = 0; $x != $width; $x++)
        {
        for ($y = 0; $y != $height; $y++)
                {
                my ($r,$g,$b) = $img->rgb($img->getPixel($x,$y));
                $YVals ->[$ct] = (( 0.299  * $r +   0.587 * $g + 0.114  * $b +   0) - 128);
                $CbVals->[$ct] = ((-0.1687 * $r - 0.03313 * $g + 0.5    * $b + 128) - 128);
                $CrVals->[$ct] = (( 0.5    * $r - 0.4187  * $g - 0.0813 * $b + 128) - 128);
		$ct++;	
               }
        }

walkthrough(1) if $walking;

####
# Here's where we run the DCT, creating and
# destroying the FFT objects as we go to 
# keep things clean
####
my $fft  = new Math::FFT($YVals );
my $Ydct = $fft->ddct();
undef $fft;

my $fft   = new Math::FFT($CbVals);
my $Cbdct = $fft->ddct();
undef $fft;

my $fft   = new Math::FFT($CrVals);
my $Crdct = $fft->ddct();
undef $fft;

###
# Grab the DCT-Coeffecients
# of each block for use 
# later.
###
$YCoeff  = $Ydct ->[0];
$CbCoeff = $Cbdct->[0];
$CrCoeff = $Crdct->[0];

walkthrough(2) if $walking;




#####
# Define the Luminance and Chrominance
# quantization tables here. These are the 
# standard jpeg quantization tables set forth 
# by the itu-t81 jpeg standard. 
#####


my @LuminanceQT = qw (
                     16  11  10  16  24   40   51   61 
                     12  12  14  19  26   58   60   55
                     14  13  16  24  40   57   69   56
                     14  17  22  29  51   87   80   62
                     18  22  37  56  68   109  103  77
                     24  35  55  64  81   104  113  92
                     49  64  78  87  103  121  120  101
                     72  92  95  98  112  100  103  99
	  	     );
                     
			
my $ChrominanceQT = qw (
			17 18 24 47 99 99 99 99
			18 21 26 66 99 99 99 99
			24 26 56 99 99 99 99 99
			47 56 99 99 99 99 99 99
			99 99 99 99 99 99 99 99
		        99 99 99 99 99 99 99 99
		        99 99 99 99 99 99 99 99
		        99 99 99 99 99 99 99 99
		       );
	


my @YQuantized;
my @CbQuantized;
my @CrQuantized;
for ($ct = 0; $ct != 64; $ct++)
	{
	 push (@YQuantized,  (($Ydct ->[$ct]) / ($LuminanceQT[$ct]   + 0.5)));
	 push (@CbQuantized, (($Cbdct->[$ct]) / ($ChrominanceQT[$ct] + 0.5)));
	 push (@CrQuantized, (($Crdct->[$ct]) / ($ChrominanceQT[$ct] + 0.5)));
	}

walkthrough(3) if $walking;

####
# Here we're bulding a zig-zag array that we
# use to place everything in it's correct space
# in the sorted array.
###
@ZigSort = qw( 0  1  5  6  14 15 27 28 
               2  4  7  13 16 26 29 42 
               3  8  12 17 25 30 41 43 
               9  11 18 24 31 40 44 53 
               10 19 23 32 39 45 52 54 
               20 22 33 38 46 51 55 60 
               21 34 37 47 50 56 59 61 
               35 36 48 49 57 58 62 63
	      );


for ($ct = 0; $ct != 64; $ct++)
	{
	$YZigged ->[$ct] = $YQuantized[$ZigSort[$ct]];
	$CbZigged->[$ct] = $CbQuantized[$ZigSort[$ct]];
	$CrZigged->[$ct] = $CrQuantized[$ZigSort[$ct]];
	}

walkthrough(4)if $walking;

###
# Now we do the Zero Runlength Encoding
###

my @YRounded;
my @CbRounded;
my @CrRounded;

####
# First we round off the 63 AC coeffecients
####
for ($ct = 1; $ct != 64; $ct++)
	{
	push (@YRounded,  sprintf("%.f", $YQuantized[$ct]));
	push (@CbRounded, sprintf("%.f", $CbQuantized[$ct]));
	push (@CrRounded, sprintf("%.f", $CrQuantized[$ct]));
	}
my $zcount = 0;
my @YRunZeroes; 
my @YRunValues;


foreach (@YRounded)
	{
	# If the current value is zero, 
	# up the zero counter and move 
	# on to the next one;
	if ($_ == 0) 
		{ 
		$zcount++; 
		}
	# If we have 16 consecutive
	# zeroes, put a (15, 0) entry
	# into the arrays. 
	elsif ($zcount == 16)
		{
		push (@YRunZeroes, 15);
		push (@YRunValues, 0);
		}
	# Otherwise, stick the value and the
	# number of zeroes preceding it into
	# parallel arrays
	else 
		{
		push (@YRunZeroes, $zcount);
		push (@YRunValues, $_);
		$zcount = 0;
		}
	}
$lines = 0;
$vals  = @YRunZeroes;				


####
# Now we get to convert the values
# into binary. The Jpeg standard fakes
# signed integers for this, which makes
# everything smaller. That means the first
# thing we have to do for each value is see
# if it's negative, and if so, make it positive
# for the purpose of binary representation, 
# and remember that it's negative
####
my @YRunCategory;
foreach (@YRunValues)
	{

	# If the number is negative, take note
	# and make it positive.
	$val = ($_ * -1) and $IsNeg = 1 if ($_ < 0);
	$val = $_ and $IsNeg = 0 if ($_ > 0);

	# Convert the number into binary. Wrap it
	# in the int operator to get rid of the 
	# unwanted leading zeros
	$_ = int(unpack("B*", pack("n", $val)));

	# If the number was negative, invert
	# the binary, this in combination with
	# the value categories allows compact
	# storage of negative numbers 
	s/0/a/g if ($IsNeg == 1); 
	s/1/b/g if ($IsNeg == 1);
	s/a/1/g if ($IsNeg == 1);
	s/b/0/g if ($IsNeg == 1);

	# Determine the category of this number
	# based on the number of bits used to 
	# describe it. For some reason trying to push
	# the result directly onto the category array
	# doesn't work. Not a big deal to do it after 
	# the fact though...
	for ($ct = 0; $ct != 16; $ct++)
		{
		$category = $ct if /(\w{$ct,})/;
		}
	push (@YRunCategory, $category);
	}

	
walkthrough(5) if $walking;

sub walkthrough 
{
$num = shift;

########################################
if ($num == 1){
my $YMat  = new Math::MatrixReal (8,8);
my $CbMat = new Math::MatrixReal (8,8);
my $CrMat = new Math::MatrixReal (8,8);
$ct = 0;
for ($row = 1; $row != 9; $row++)
        {
        for ($col = 1; $col != 9; $col++)
                {
                $YMat ->assign($row,$col,$YVals ->[$ct]);
                $CbMat->assign($row,$col,$CbVals->[$ct]);
                $CrMat->assign($row,$col,$CrVals->[$ct]);
                $ct++;
                }
        }
        
print <<endofblock;
                  
Initial Luminance Values
-----------------------------------------------
                        
$YMat
    

Initial Chrominance Values
---------------------------------------------
                        
Cb :
$CbMat


Cr :
$CrMat


Now we run the DCT Transforms on these values, Press enter to Continue

endofblock
undef $YMat;
undef $CbMat;
undef $CrMat;
<STDIN>;
print $cs;

}

############################################
############################################

if ($num == 2)
{

my $YMat  = new Math::MatrixReal (8,8);
my $CbMat = new Math::MatrixReal (8,8);
my $CrMat = new Math::MatrixReal (8,8);
$ct = 0;
for ($row = 1; $row != 9; $row++)
        {
        for ($col = 1; $col != 9; $col++)
                {
                $YMat ->assign($row,$col,$Ydct ->[$ct]);
                $CbMat->assign($row,$col,$Cbdct->[$ct]);
                $CrMat->assign($row,$col,$Crdct->[$ct]);
                $ct++;
                }
        }


print <<endofblock;
                  
After the DCT is run, the first value in each block is referred to 
as the DC coeffecient and the other 63 values are referred to as the
AC coeffecients. This doesn't really matter at this point, since 
everything gets quantized, but it comes up later on in the process...
                        
Luminance DCT coeffecients
-----------------------------
$YMat
    
Chrominance DCT coeffecients
------------------------------
                        
Cb:
$CbMat
     
Cr;
$CrMat
     
On to the Quantification.
Press enter to continue...
                        
endofblock
undef $YMat;
undef $CbMat;
undef $CrMat;
<STDIN>;
print $cs;

}

############################################
############################################

if ($num == 3)
{


my $YMat  = new Math::MatrixReal (8,8);
my $CbMat = new Math::MatrixReal (8,8);
my $CrMat = new Math::MatrixReal (8,8);
$ct = 0;
for ($row = 1; $row != 9; $row++)
        {
        for ($col = 1; $col != 9; $col++)
                {
                $YMat ->assign($row,$col,$YQuantized[$ct]);
                $CbMat->assign($row,$col,$CbQuantized[$ct]);
                $CrMat->assign($row,$col,$CrQuantized[$ct]);
                $ct++;
                }
        }
print <<endofblock;
Quantized Luminance Matrix
-------------------------------
$YMat


Quantized Chrominance Matrices
-------------------------------------

Cb :
$CbMat


Cr :
$CrMat

Next step is to re-order each 8x8 block in a zig-zag pattern, the 
DC coeffecient MUST STAY at the upper left-hand corner...

press Enter to continue

endofblock
undef $YMat;
undef $CbMat;
undef $CrMat;
<STDIN>;
print $cs;

}

################################################
################################################

if ($num == 4)
{

my $YMat  = new Math::MatrixReal (8,8);
my $CbMat = new Math::MatrixReal (8,8);
my $CrMat = new Math::MatrixReal (8,8);
$ct = 0;
for ($row = 1; $row != 9; $row++)
        {
        for ($col = 1; $col != 9; $col++)
                {
                $YMat ->assign($row,$col,$YZigged ->[$ct]);
                $CbMat->assign($row,$col,$CbZigged->[$ct]);
                $CrMat->assign($row,$col,$CrZigged->[$ct]);
                $ct++;
                }
        }
        
print <<endofblock;
        
Zigged Luminance Matrix
------------------------------
$YMat

Zigged Chrominance Matrices
------------------------------
Cb :
$CbMat

Cr :
$CrMat

------------------------------
Pulled this off by creating an array \@zigsort :

\@zigsort = qw(
               0  1  5  6  14 15 27 28
               2  4  7  13 16 26 29 42
               3  8  12 17 25 30 41 43
               9  11 18 24 31 40 44 53
               10 19 23 32 39 45 52 54
               20 22 33 38 46 51 55 60
               21 34 37 47 50 56 59 61
               35 36 48 49 57 58 62 63
              )


Then assigned each AC-coeffecient to it's new position. Now we get to do the 
Zero Runlength Encoding...

press enter to continue

endofblock
undef $YMat;
undef $CbMat;
undef $CrMat;
<STDIN>;
print $cs;
}

##############################################
##############################################

if ($num == 5)
{
print <<endofblock;

The Run Length Encoding is a fairly convoluted process. 
First you take all of the AC coeffecients and round them off, 
Then you tally up the zeroes and count them in a less bulky fashion.
after that you have to convert everything to binary and futz with
it a bit. A better explanation of the whole process is definitely
forthcoming, it's a just a lil' too late at night to go into the 
detail right now. However, at the end of the endeavor we end up with
a stream of data to pass to the huffman encoder.

I've just got the Luminance encoding done at this point, because I'm
still a little unsure as to how to combine the Cb and Cr values into
one block of data.
endofblock
$ct = 0;
print "\(Zeroes Preceding Entry,   Number Category   \)   Bit-Representation of Number\n";
print "=========================  ===================   =================================\n";
	
foreach (@YRunValues)
	{
	print "\(     $YRunZeroes[$ct],                     $YRunCategory[$ct]                \)  $_\n"; 
	$ct++;
	}


}



	}
