Osm bitů v sedmi - Builder.cz - Informacni server o programovani

Navigace:  » Úvodní stránka  » Rubriky  » C/C++  

17. března 2003, 00.00 | V tomto článku si ukážeme malý trik jenž můžeme použít nejen při kompresi malých čísel, ale taky při dekódování potažmo enkódování dat (SMS) z a do formátu PDU, jenž se se používá v mobilních telefonech.

    Dnes malinko odbočíme od tématu grafické  komprese a povíme si  něco, co jsem tak trochu načal v předchozím článku, a co se nám může někdy v budoucnu  hodit. V minulém článku jsme si ukázali možnosti doplňkové komprese některých koeficientů DCT -matice, menších jak 7 bitů (číslo v desítkové soustavě menší jak 127) pomocí zápisu do sedmibitoveho formátu. Samozřejmě tento způsob je jen nejjednodušší možností,  taky je možný ukládat 6 bitová nebo 9 bitová čísla stačí mít na paměti kolik bitů jsme použili pro ten který koeficient čili mít standard. Jedná se o zcela jednoduchý úkon, který je možné udělat mnoha způsoby, třeba přímým přístupem k jednotlivým bitům, ale taky jednoduchým matematickým přepočtem jenž si ukážeme. Využít tohoto triku můžeme nejen při kompresi malých čísel, ale taky při dekódování potažmo enkódování dat(SMS) z a do formátu PDU, jenž se se používá v mobilních telefonech. 

   Nejdříve koeficienty (dále jen čísla) převedeme do dvojkové - binární soustavy a uložíme do pole nebo do řetězce. Standardní zápis 8 bitů vypadá v dvojkovém formátu nasledovně: číslo 6 = 0x1⁸ + 0x1⁷ + ... + 1x2² + 1x2¹ + 0x2⁰. 

Matematicky se převod do dvojkové soustavy dělá celočíselným dělením vstupu až po nulu. Zbytky po dělení dávají řetězec dvojkového zápisu. Vlevo je všeobecný formát kde červené šipky znázorňují celočíselné dělení modré zbytek ... binární zápis se čte od spodu nahoru. T.j. šestka vpravo je 110.

Jednotlivá osmibitová vyjádření čísel spojíme do jednoho řetězce odstraníme první nulu a znovu spojíme. Z výsledného řetězce pak vždy po osmi bitech vypočítáme výslednou 8-bitovou hodnotu.

 

Takhle z osmi vstupních čísel získáme sedm, což představuje účinnost komprese přibližně 88%. Chtěl bych zde upozornit, že toto je jen taková doplňková komprese. Všeobecně se používaji víc VLC nebo Huffmanovo kódovaní (pro zajímavost je z roku přibl. 1955), kde se nahrazují nejčastěji se vyskytujíci čísla nejmenšími znaky. 

Teď jak na to prakticky: 

char * intto8bin(int inpt) //prevod int na 8 prvkove pole bitu {   char * poutp = new char[8];   int rest, binar, pos;   rest = inpt;   pos = 0;   while (rest>1)    {     binar = rest % 2;//nejdriv se pocita zbytek     rest = rest / 2;// pak se deli celociselne dvema     poutp[7-pos]=int(binar);//bity se musi ukladat od konce     pos++;   }//while   poutp[7-pos]=1;   int ii;   for (ii=(pos+1); ii<=7;ii++) poutp[7-ii]=0;// zbytek do 8 bitu se vyplni nulou   return poutp; }

Následujíci funkce ze zadaného 56 prvkového pole bitů vrací pole 7 nebo 8 čísel podle hodnoty outputsize a taky podle něho dělí vstupní pole na 7 nebo 8 prvkové části.

int * calcint(char inpt2[],int outputsize) {   int * poutp = new int[outputsize];   char inpt[56];   int ii,jj;   for (ii=0;ii<56;ii++) inpt[ii]=inpt2[ii];   for (jj=0;jj<outputsize;jj++) {     poutp[jj]=0;     int cut;     cut = 56 / outputsize;     for (ii=jj*cut;ii<=jj*cut+cut-1;ii++){       poutp[jj]=poutp[jj]*2+int(inpt[ii]);     }// for ii   }// for jj   return poutp; }

Na to abychom kompresi ovšem taky udělali na disku je potřeba získaná čísla zapisovat do souboru v binárním formátu. 

Co to je binární formát? Data se obvykle ukládají do paměti ve dvouch formátech textovém a binárním. V textovém se vše ukládá jako text (překvápko že? :-) to jest také čísla. Např. číslo 125 se uloží jako znak "1", znak "2" a znak "5". V binární podobě se uloží jako sekvence bitů 01111101. I když to tak nevypadá ale binární způsob přístupu k datům má také své nevýhody, ale o nich teď mluvit nebudeme. Je ale jasné, že binární způsob  zabírá většinou méně místa, je přesnější protože ukládá přesnou vnitřní reprezentaci hodnoty čísel a všeobecně ukladání dat může být rychlejší protože nedochází ke konverzím čísel na znaky. 

Tak víme co je binární formát a teď jak s ním pracovat. Úplně stejně jak s textovým až na pár vyjímek. První je, že musíme procesoru říct že chceme číst byty a ne znaky to jest otevřeme soubor v binárním formátu a druhá je že musíme uvést kolik bytů ukládáme : 

void saving(int inpt3[]) {   ofstream fout;   fout.open("c:/builder.bld",ios_base::binary);// otevreni v binarnim modu   int *ppoutp = new int[7];   int ii;   for (ii=0;ii<7;ii++) {//ukladame po jednotlivych bytech     ppoutp[ii]=inpt3[ii];     fout.write((char *) &ppoutp[ii],1);   }   fout.close(); }

Následujíci funkci berte jenom jako pomůcku, načítá obsah souboru do pole 7 bytů (tedy proměnných char) ..

int * reading() {   ifstream fin;   fin.open("c:/builder.bld",ios_base::binary);   unsigned char ch;   int * outp = new int[7];   int pos=0;   if (fin.is_open())   {     cout <<"Numbers stored in the file : \n";     while (fin.read((char*) &ch,1)){       outp[pos] = ch;       pos++;     }// while   }//if   fin.close();   return outp; }

Tak celý zdroják najdete tady(1,2kB) a taky je k dispozici zdroják pro Delphi(4,8kB).

Dodatek: Jestli máte rádi hádanky tady je 7 čísel jenž reprezentují 8 bytových čísel. Každé z osmi čísel pak odpovída znaku v ASCII sadě. Když tedy zjistíte, která čísla to jsou dozvíte se odkaz jenž nesou. :-) 

[125, 54, 13, 74, 82, 108, 60]

Zdroje:
http://www.dreamfabric.com/sms/
http://www.learnbinary.com/binary.html
S.Prata - Mistrovství v C++