<?php 

/* 
Project:         Huffen met php v1.21 
Genre:            Compressie class gebaseeerd op de basis van David A.Huffman 
Requirements:    Php 5.1 of hoger 
Programming:     Danny Roelofs 
E-Mail:          dannyroelofs[AT]gmail[DOT]com 


Wijzigingen ten opzichte van v1.21 tot versie v1.2: 

1. Twee nieuwe functie's, ConvertToHex en ConvertToBin om biniare data om 
   te zetten naar hexadecimale gegevens zodat Huffen ook kan worden gebruikt 
   om betrouwbaarder informatie in een my(sql) database te plaatsen of om 
   gecomprimeerde data in een php script te stoppen (zie voorbeeld: #4) 
    

Wijzigingen ten opzichte van v1.2 tot de vorige versie: 

1. De decoding tabel welke benodigd is om de inhoud te decoderen is nu zelf ook 
   gecomprimeert en neemt nu minder ruimte in waardoor de drempel lager komt te 
   liggen om een betere compressie ratio te bereiken 
    
2. De decoding tabel en compressed data hebben vanaf nu een definitieve structuur 
   en zal in de toekomstige versie's altijd compatible blijven indien er vernieuw- 
   ende factoren er bij komen. 
    
3. Functie's om naar een bestand te schrijven zijn op dit moment verwijderd gezien 
   ik de class aan het verbeteren ben om interne functie's herbruikbaar te maken 
   onder diverse omstandigheden. 

4. Nieuwe functie's zijn Compress en Decompress welke geen statische functie's zijn 
   en nu als een object methode moeten worden aangesproken 

Opmerkingen: 

Ik werk op dit moment aan een pagina op mijn website om voorbeelden te geven hoe de 
class gebruikt dient te worden. Een ervaren OOPér zal gebaseerd op de functie uitleg 
wel weten hoe dit kan worden toegepast. 

*/  


/*======================================================================================================== 

[1]------------------------------------------------------------------------------------------------------- 
Function:    $object->Compress()                // Compressing your input. 
Required:    $object->input                    // <string> insert your text in here from a resource. 
Returns:    $object->table                    // <biniary> contains compressed decoding table. 
            $object->data                    // <biniary> contains compressed content. 
---------------------------------------------------------------------------------------------------------- 

[2]------------------------------------------------------------------------------------------------------- 
Function:    $object->Decompress()            // Decompressing your data to its original content. 
Required:    $object->table                    // <biniary> insert compressed decoding table. 
            $object->data                    // <biniary> insert compressed content. 
Returns:    $object->output                    // <string>    contains decompressed (original) content. 
---------------------------------------------------------------------------------------------------------- 

[3]------------------------------------------------------------------------------------------------------- 
Function:    $object->ConvertToHex            // Converts biniary table and data to hex. 
Required:    $object->table                    // <biniary> insert compressed decoding table. 
            $object->data                    // <biniary> insert compressed content. 
Returns:    $object->hextable                // <string> Biniary table converted to Hex. 
            $object->hexdata                // <string>    Biniary data converted to Hex. 
---------------------------------------------------------------------------------------------------------- 

[4]------------------------------------------------------------------------------------------------------- 
Function:    $object->ConvertToBin            // Converts hex table and data to biniary. 
Required:    $object->hextable                // <string> Hex table. 
            $object->hexdata                // <string>    Hex data. 
Returns:    $object->table                    // <biniary> Hex table converted back to biniary. 
            $object->data                    // <biniary> Hex data converted back to biniary. 
---------------------------------------------------------------------------------------------------------- 

========================================================================================================*/ 

//========================================================================================================= 
// Voorbeeld: #1 
// 
// In deze voorbeeld nemen we een stukje tekst, deze tekst is bij lange na niet bijzonder genoeg om 
// een grote compressie ratio te verkrijgen maar ondanks dat is het verschil toch circa 16% 
// 
// We gaan nu deze tekst comprimeren 

echo "<br><h2>Voorbeeld: #1</h2>"; 
// Voorbereidend werk c.q Required input: 
$een = new Huffen(); 
$een->input = "De compressie ratio hangt af van het aantal karakters en hun frequentie en zal gemiddeld".  
              "de informatie verkleinen tot 70% maar naast uitschieters van zelfs tot 50% zullen er ook".  
              "situatie's kunnen ontstaan dat de compressie ratio lager ligt. Zoals in dit geval is er".  
              "te weinig tekst om te comprimeren tot een hogere ratio maar levert toch ca 16% winst op.";  
// Comprimeren starten: 
$een->Compress(); 

// We tonen nu de lengtes van het origineel en de gecomprimeerde versie 
$lengte_origineel  = strlen($een->input); 
$lengte_compressed = strlen($een->table) + strlen($een->data); 
echo "<br>Originele lengte is    ".$lengte_origineel." tekens<br>"; 
echo "Gecomprimeerde lengte is    ".$lengte_compressed." <br>"; 
//========================================================================================================= 


//========================================================================================================= 
// Voorbeeld: #2 
// 
// We hergebruiken de gegevens die net via voorbeeld #1 zijn gecreert om de gecomprimeerde data weer 
// te decomprimeren zodat we weer de originele inhoud te zien krijgen: 

echo "<br><h2>Voorbeeld: #2</h2>"; 
// Voorbereidend werk c.q Required input: 
$twee = new Huffen(); 
$twee->table = $een->table; 
$twee->data  = $een->data; 
// Decomprimeren 
$twee->Decompress(); 
echo "<br>Originele inhoud is:<br><br>"; 
echo $twee->output; 
//========================================================================================================= 

//========================================================================================================= 
// Voorbeeld: #3 
// 
// Er kunnen situatie's ontstaan dat je informatie wil opslaan in my(sql) of in een installatie script en 
// dat je niet zit te wachten op de negatieve effecten welke biniare data zou kunnen creeeren in bepaalde 
// omstandigheden. 
// 
// Het is mogelijk om gecomprimeerde biniare data om te zetten naar hexadecimale waarden zodat de gegevens 
// weer als <string> te behandelen zijn. 

echo "<br><h2>Voorbeeld: #3</h2>"; 
// Voorbereidend werk c.q Required input: 
$drie = new Huffen(); 
// We verwijzen gemakshalve naar informatie van de eerste voorbeeld 
$drie->table  = $een->table; 
$drie->data      = $een->data; 
// Converteren naar hexadecimale'n 
$drie->ConvertToHex(); 
echo "<br><br><b>Table: Wat biniare was is nu hexadecimaal:</b><br><br>"; 
echo $drie->hextable; 
echo "<br><br><b>Data:: Wat biniare was is nu hexadecimaal:</b><br><br>"; 
echo $drie->hexdata; 


// Voorbeeld: #4 
// 
// In deze voorbeeld hebben we van te voren een <string> gecomprimeerd en omgezet naar hexadecimale formaat 
// en dit wordt nu weer terug geconverteert en gedecomprimeert. De inhoud is zodanig kort dat er echter geen 
// positieve compressie ratio is te verkrijgen en dient alleen maar als voorbeeld: 

echo "<br><h2>Voorbeeld: #4</h2>"; 
$table = "6513022013046114026914016e14077214066415066d15016f150049151f62151e63151d66151". 
         "c67151b68151a6b15196c15187315177415167615157715147815072121213139302323230a"; 
$data  = "fe650af2a9bc06da782f0ca691c8cba212c282fc0304ac28"; 

// Voorbereidend werk c.q Required input: 
$vier                   = new Huffen(); 
$vier->hexdata        = $data; 
$vier->hextable       = $table; 
// Inhoud omzetten naar biniarey informatie: 
$vier->ConvertToBin(); 
// Biniare inhoud decomprimeren: 
$vier->Decompress(); 
// Orignele informatie weergeven: 
echo "<br><br><b>Dit stond in de hexadecimale gegevens:</b><br><br>"; 
echo $vier->output; 
//========================================================================================================= 


class Huffen 
{ 

     
    const Tag_Empty    ='1';  
    const Tag_Leaf    ='2'; 
    const Tag_Root    ='2'; 
    const Tag_Node    ='3'; 
    const Tag_NoUse    ='5'; 
     
    public function ConvertToHex() 
    { 
        $counter=0; 
        while($counter<strlen($this->table)) 
        { 

            $hex = dechex(ord(substr($this->table,$counter,1))); 
            if (strlen($hex)==1) 
            { 
                $hex = "0".$hex; 
            } 
            $hex_table = $hex_table . $hex; 
            $counter++; 
        } 
        $counter=0; 
        while($counter<strlen($this->data)) 
        { 
            $hex = dechex(ord(substr($this->data,$counter,1))); 
            if (strlen($hex)==1) 
            { 
                $hex = "0".$hex; 
            } 
            $hex_data = $hex_data . $hex; 
            $counter++; 
        } 
        $this->hextable = $hex_table; 
        $this->hexdata  = $hex_data; 
        return $this; 
    } 

    public function ConvertToBin() 
    { 
        $counter=0; 
        while($counter<strlen($this->hextable)) 
        { 

            $bin = chr(hexdec(substr($this->hextable,$counter,2))); 
            $bin_table = $bin_table . $bin; 
            $counter=$counter+2; 
        } 
        $counter=0; 
        while($counter<strlen($this->hexdata)) 
        { 
            $bin = chr(hexdec(substr($this->hexdata,$counter,2))); 
            $bin_data = $bin_data . $bin; 
            $counter=$counter+2; 
        } 
        $this->table = $bin_table; 
        $this->data  = $bin_data; 
        return $this; 
    } 

     
    public function Compress() 
    { 
        $nodelist             = array(); 
        $newtable             = array(); 
        $nodelist             = Huffen::ArrayInit(); 
        $nodelist             = Huffen::CharCountSortInputAndAddToNode($nodelist,$this->input); 
        $nodelist             = Huffen::CreateNodeList($nodelist); 
        $newtable             = Huffen::CreateTable($nodelist); 
        $newtable             = Huffen::NWTAble($newtable); 
        $converted_data        = Huffen::_convertchartobin($newtable,$this->input); 
        $compressed_table    = Huffen::_compresstable($newtable,strlen($converted_data)); 
        $howmanybitstofill    = 8 - ( strlen( $converted_data ) - ( floor(strlen( $converted_data ) /8 ) * 8) ); 
        $converted_data        = $converted_data . substr("00000000",0,$howmanybitstofill); 
        $compressed_data    = Huffen::_compressdata($converted_data); 
        $this->table         = $compressed_table; 
        $this->data         = $compressed_data; 
        return $this; 
    } 

    public function Decompress() 
    { 

        $data=$this->table.$this->data; 
        $break        = 0; 
        $result        = 0; 
        $result2    = 0; 
        $pos        = 0; 
        $prevpos    = 0; 
        $counter    = 0; 

        $TableAll    = array(); 
        $Table_Char = array(); 
        $Table_Bin    = array(); 
        $Table_Len    = array(); 

        $pos         = strpos($data,"!!!"); 
        $table         = substr($data,0,$pos); 
        $posnext     = strpos($data,"###",$pos+3); 
        $length     = substr($data,$pos+3,$posnext-($pos+3)); 
        $data         = substr($data,$posnext+4,strlen($data)-($posnext+4)); 

     
          $fillbits = new Huffen(); 
        $counter = 0; 
        $array_counter    =0; 
     
        while($counter<strlen($table)) 
        { 
            $codecounter = 0; 
            $bincodes=''; 
            $char = substr($table,$counter,1); 
            $Table_Char[$array_counter]=$char; 
            $infobyte = decbin(ord(substr($table,$counter+1,1))); 
            $fillbits->FillBits($infobyte,8); 
            $infobyte = $fillbits->string; 
            $codebytes = bindec(substr($infobyte,0,4)); 
            $lengthcodebytes = bindec(substr($infobyte,4,4)); 
            for ($codelength=0;$codelength<$codebytes;$codelength++) 
            { 
                $bincode =  decbin(ord(substr($table,$counter+2+$codelength,1))); 
                $fillbits->FillBits($bincode,8); 
                $bincode = $fillbits->string; 
                $codecounter++; 
                $bincodes = $bincodes . $bincode; 
            } 
            $counter=$counter+2+$codecounter; 
            $test=substr($bincodes,strlen($bincodes)-$lengthcodebytes,$lengthcodebytes); 
            $Table_Bin[$array_counter]=$test; 
            $Table_Len[$array_counter]=strlen(substr($bincodes,strlen($bincodes)-$lengthcodebytes,$lengthcodebytes)); 
            $array_counter++; 

        }             

        array_multisort($Table_Len,SORT_DESC,SORT_NUMERIC,$Table_Bin,$Table_Char); 
        foreach ($Table_Len as $key => $val) 
        { 
            $TableAll[$key][0]=$Table_Char[$key]; 
            $TableAll[$key][1]=$Table_Bin[$key]; 
            $TableAll[$key][2]=$Table_Len[$key]; 
        } 
        $counter    = 0; 
        $bindata    = ''; 
        $bin        = ''; 
         
        while(strlen($result=substr($data,$counter,1))==1) 
        { 
            $biniar = decbin(ord($result)); 
            if (strlen($biniar)==8) 
            { 
                $biniar2 = $biniar; 
            } 
            else 
            { 
                $biniar2 = substr("00000000",0,8-strlen($biniar)). $biniar; 
            } 
            $bindata = $bindata.$biniar2; 

            $counter++; 

        } 

        $bindata    = substr($bindata,0,$length); 
        $decompressed=''; 
        while (strlen($bindata)>0) 
        { 
            $break=0; 
            foreach($TableAll as $key => $val) 
            { 
                if (!strcmp(substr($bindata,0,$TableAll[$key][2]),$TableAll[$key][1])) 
                { 
                    $bindata=substr($bindata,$TableAll[$key][2],strlen($bindata)-$TableAll[$key][2]); 
                    $decompressed = $decompressed . $TableAll[$key][0]; 
                    $break=1; 
                } 
                if ($break==1){break;} 
            } 
        } 

        $this->output=$decompressed; 
        return $this; 
     
    } 

    // 
    // Private functions dedicated to the larger functions and are not required to be 
    // used outside the class. 
    // 
     
     
    //Converting the table array to a string containing compressed data 
    private static function _compresstable($array,$bitslength) 
    { 
        $fillbits          = new Huffen(); 
        foreach($array as $key => $val) 
        { 
            $for_counter      = 0; 
            $byte_counter      = 0; 
            $combine_lfbrfb   = ''; 
            $temp_data          = ''; 

            $compressed_table = $compressed_table . $array[$key][0]; 

            for ($for_counter=0;$for_counter<(strlen( $array[$key][1] ) /8 );$for_counter++) 
            { 
                $temp_data = $temp_data . chr( bindec( substr( $array[$key][1],($for_counter*8),8 ) ) ); 
                $byte_counter++; 
            } 

            $fillbits->FillBits( decbin( $byte_counter     ) ,4);    $ffbits        = $fillbits->string; 
            $fillbits->FillBits( decbin( $array[$key][2] ) ,4);    $lfbits        = $fillbits->string; 
            $combine_lfbrfb        = $ffbits . $lfbits; 
            $compressed_table    = $compressed_table . chr( bindec($combine_lfbrfb) ) . $temp_data; 
        } 

        $compressed_table     = $compressed_table . "!!!".$bitslength."###\n"; 
         
        return $compressed_table; 
    } 
     
    // converting ascii content to biniary 
    private static function _convertchartobin($array,$string) 
    {                 
        while (strlen($result=substr($string,$counter,1))>0) 
        { 
         foreach($array as $key => $val) 
         { 
          if (!strcmp($array[$key][0],$result)) 
          { 
           $compressing_data = $compressing_data . substr( $array[$key][1] , strlen($array[$key][1])-$array[$key][2], $array[$key][2] ); 
          } 
         } 
         $counter++; 
        } 
        return $compressing_data; 
    } 
     
    // Complete incomplete bytes by adding bits till a prefered $length (common sence : 4 or 8) 
    private function FillBits($string,$length) 
    { 
         $fillbits        = $length - (strlen($string) - (floor(strlen($string)/$length) * $length)); 
       if ($fillbits==$length){$fillbits=0;} 
       $string             = substr("00000000",0,$fillbits).$string; 
       $this->string    = $string; 
       $this->fillbits    = $fillbits; 
       return $this; 
    } 
     
    private static function _compressdata($converted_data) 
    { 
        $while_counter            = 0; 
        $compressed_data         = ''; 
        while(strlen(substr($converted_data,($while_counter*8),8))==8) 
        { 
            $compressed_data = $compressed_data . chr(bindec(substr($converted_data,($while_counter*8),8))); 
            $while_counter++; 
        } 
        return $compressed_data; 
    } 
     
     private static function NWTable($array) 
     { 
        $fillbits = new Huffen(); 
        foreach($array as $key => $val) 
        { 
            $fillbits->FillBits($array[$key][1],8);    $array[$key][2]=strlen($array[$key][1]); $array[$key][1]=$fillbits->string; 
        } 
        return $array; 
     } 

     private static function CharCountSortInputAndAddToNode($array,$string) 
     { 
         $counter=0; foreach (count_chars($string, 1) as $k => $a) { $y[$counter]=chr($k); $z[$counter] =$a; $counter++; } 
         array_multisort($z,SORT_DESC,SORT_NUMERIC,$y); 
         foreach($z as $key => $val) 
         { 
            $array[$key+1][0][0][0]=Huffen::Tag_Leaf; $array[$key+1][0][0][1]=$y[$key]; $array[$key+1][0][0][2]=$z[$key]; 
         } 
        return $array; 
     } 

     private static function CreateNodeList($array) 
     { 
        foreach($array as $count2 => $max2) 
        { 
            foreach($array as $count => $max) 
            { 
                if ($array[$count][0][0][0]==Huffen::Tag_Empty) 
                { 
                    break; 
                } 
            } 
            $emptynode=$count; 

            for ($runtwice=0;$runtwice<2;$runtwice++) 
            { 
                 $result        = 0; 
                $lowest        = pow(20,20); 
                $position    = 0; 
                 foreach($array as $key => $val) 
                 { 
                     if ($array[$key][0][0][0]==Huffen::Tag_Leaf or $array[$key][0][0][0]==Huffen::Tag_Node) 
                     { 
                         $result = $array[$key][0][0][2]; 
                         if ($result < $lowest) 
                         { 
                            $lowest=$result; 
                            $position=$key; 
                         } 
                     } 
                 } 
                $array[$position][0][0][0]=Huffen::Tag_NoUse; 
                if ($runtwice==0) { $array[$emptynode][1][0][0]=$position; } 
                if ($runtwice==1) { $array[$emptynode][0][1][0]=$position; } 
                $array[$emptynode][0][0][2]= $array[$emptynode][0][0][2] + $array[$position][0][0][2]; 
            } 
            $array[$emptynode][0][0][0]=Huffen::Tag_Leaf; 
            if ($array[$emptynode][1][0][0]=="0" or $array[$emptynode][0][1][0]=="0"){ break;} 
        } 
        return $array; 
    } 

     private static function ArrayInit() 
     { 
        $array= array(); for ($counter=0;$counter<256;$counter++) 
        { 
            $array[$counter][0][0][0]=Huffen::Tag_Empty; 
            $array[$counter][1][0][0]=''; 
            $array[$counter][0][1][0]=''; 
            $array[$counter][0][0][1]=''; 
            $array[$counter][0][0][2]=''; 
        } 
        $array[0][0][0][0]=Huffen::Tag_NoUse; 
        return $array; 
     } 

     private static function ArrayShow($array) 
     { 
        for ($counter=0;$counter<256;$counter++){ 
        echo " Key = ".$counter. 
             " - Tag = ".$array[$counter][0][0][0]. 
             " - LeftLeaf = ".$array[$counter][1][0][0]. 
             " - RightLeaf = ".$array[$counter][0][1][0]. 
             " - Char = ".$array[$counter][0][0][1]. 
             " - Value = ".$array[$counter][0][0][2]. 
             "\n";} 
     } 

     private static function TableShow($array) 
     { 
        foreach($array as $key => $val) 
        { 
            echo $array[$key][0]." = ".$array[$key][1]." = ".$array[$key][2]."\n"; 
        } 
     } 


     
     private static function CreateTable($array) 
     { 
        $array[0][0][0][0]=Huffen::Tag_Empty; 
        $table = array(); 
        $table_counter=0; 
         foreach($array as $count => $max) 
        { 

            if (($array[$count][1][0][0]==0 and $array[$count][0][1][0]==0) ) 
            { 
             if ($array[$count][0][0][0]==Huffen::Tag_NoUse) 
             { 
                $while_break='0'; 
                $biniary=''; 
                $find=$count; 
                while($while_break==0) 
                { 
                     foreach($array as $count2 => $max2) 
                    { 
                      if ($array[$count2][1][0][0]==$find) 
                      { 
                          $biniary= "1" . $biniary; 
                          $find=$count2; 
                      } 

                      if ($array[$count2][0][1][0]==$find) 
                      { 
                          $biniary= "0" . $biniary; 
                          $find=$count2; 
                      } 

                      if ($array[$count2][0][0][0]==Huffen::Tag_Root) 
                      { 
                          $while_break=1; 
                          $biniary=substr($biniary,1,strlen($biniary)); 
                          $table[$table_counter][0]=$array[$count][0][0][1]; 
                          $table[$table_counter][1]=$biniary; 
                          $table_counter++; 
                          $biniary=''; 
                      } 

                       
                    } 
                 
                } 
             } 
            } 
            else 
            { 
                break; 
            } 
        } 
        return $table; 
     } 
} 

?> 
