C++ zápis/načítání jednotlivých bitů

Normalne sa to robi tak ze si drzis 1 byte v premennej a 8x ho rotujes a prichadzajuci bit stale davas na poziciu bitu 0. T.j. x = x<<1 | in; pricom in je 0 alebo 1
Stejnym sposobom sa posiela, posielas stale bit0 alebo bit7 (t.j. x & 0x01 alebo x & 0x80) a nasledne urobis x>>1 resp x<<1

P.S. najefektivnejsie sa take veci robia v assembleri. A ne cez OOP fcie pre kazdy bit, to je 10x pomalsie.

Díky, udělal jsem to podle rady, možná se to mírně zrychlilo.
Měl bych tyto funkce vyjmout ze třídy a nechat zvlášť?

Je jedno ze je to v triede, neni jedno ze volas funkce pre kazdy bit, a if-ujes to tam zbytocne furt apod.
P.S> na optimalizaciu takych veci su vyhodne aj SIMD instrukcie napr. SSE apod., tak mozem rotovat 4 veci naraz, a robit s nimi aj dalsie operacie naraz apod. Je nutne robit detekciu CPU, snad to vdia nejake compilery ked sa to nastavi, ja so to robil raz rucne (len pre seba)
P.S.2. ale principialne to mas designovane IMHO naopak, mas stat nad datami a robit sekvencne co je nutne a ne volat si daj mi bit. Optimalizacia sa zacina u designu.

P.S.3. a nikto netvrdi ze ti to spomaluje tato funkcia, odstranit jedno if a call ta uz asi z biedy nevytrhne, zober casti celeho algoritmu a zmeraj si kolko co trva (napr. tak ze to das len nejaku cast do slucky milionkrat a precitas si nejaky presny timer pred a po, alebo v existujucom si na roznych miestach precitas TSC, len neviem ci na to mas fciu, ptz cpat asm sekciu do fcie odstavi niektore optimalizacia kompilera v tej fcii)

Pracovat s bity je bohužel nutné. Používám Golom. Riceův kodér, viz. např.
http://cs.wikipedia.org/wiki/Golombovo_k%C3%B3dov% C3%A1n%C3%AD
Při kódování potřebuju zapisovat bity a při dekódování zase číst..
Čas určitě změřím.

         for (int i = 0 ; i < q; i++)
             bitwriter.putBit(true);   // zapíše q jedniček
         bitwriter.putBit(false);      // zapíše jednu nulu

sa da kompletne prerobit, keby som mal poziciu aktualneho zapisovaneho bitu (alebo lepsie pocet bitov ostavajuich v bajte) v x, tak si urobim napr.
while(q>=x) {
*pzapis |= tabulka[x]; // tabulka pre 0-7 zbyvajucich bitov nastavenych na 1
pzapis++;
q-=x;
x=8;
}
apod. Neni to maximalne optimalne ale ako priklad, da sa to este optimalizovat.

 bitwriter.putBit(false);      // zapíše jednu nulu

je len if(--x==0) {x=8; pzapis++;} ptz to pole na zapis som si predtym vynuloval napriklad. Alebo uplne hardcore optimalizacia je ze napisem algoritmus pre kazde x osobitne t.j. budem mat 8 roznych vetiev pre x=0 az 7 a na zaciatku urobim if ze ktora vetva a potom vo vetve to ide uplne bez ifov natvrdo. Apod. Moznosti je milion, fantazii sa medze nekladu

Díky za tipy, zkusím to předělat. Určitě to má smysl, protože jeden student co toto dělal před x lety došel k závěru, že nejvíc času zabírá jeho funkce put_bit() (má napsané v BP že 44,33 %).

To sa mi zas nezda, ale da sa to robit aj bez funkce, urobit si bajtovu fukciu alebo dokonca 32bitovu to je este optimalnejsie (najprv ladujem bity do 32bitovej premennej priamo v hlavnej slucke a az ked som dosiahol 32 tak zavolam zapisdword(premenna). Nezabudnut potom nakonci zapisat ciastkovy dword (nemusi byt plny ked si na konci dat)

A jak ten např. 32-bit unsigned long potom zapíšu do pole unsigned char (4 bajty za sebou)?

A
data[data_i++] = complete_byte; // ulozeni hotoveho bajtu
rob radsej ako
*smernik++ = complete_byte;

Udrzuj si smernik niekde v privatnej premennen namiesto data_i (to je zbytocna kravina). A nepredavaj zbytocne furt aj smernik na pole do kazdej bitfunkcie, to nema vyznam. V privatnych premennych si udrzuj aktualny pointer a bitmask. Bit nastavuj len ked je 1, complete_byte si stale vynuluj ked zvysis pointer. Ked je bit 0 tak len zrotujes masku a otestujes ci neni 0, ak ano zapisujes bajt a maska = 0x80.

T.j.

void JKvideocodec::store_bit(int bit)
{
  if(bit) complete_byte |= w_mask;
  w_mask >>= 1;
  if (!w_mask)
  {// zapsal se posledni bit
    w_mask = 0x80; // inicializace indexu
    *p_writedata++ = complete_byte; // ulozeni hotoveho bajtu
  }
}

parameter je int bit aby to nemusel prekladac konvertovat furt zbytocne (stejne to ja testujem oproti 0 a ty tam davas integer z volajucej fcie v tom 2.cykle)

bool JKvideocodec::next_bit()
{
  if (!r_mask)
  {// Nacist dalsi byte
    one_byte = *p_readdata++;
    r_mask = 0x80;
  }

  return (one_byte & r_mask);
}

O kolko sa to zrychlilo?

P.S> v konstruktore resp. pri inicializacii pola pre zapis nezabudni nastavit w_mask = 0x80, complete_byte=0; p_writedata = buffer.
A pri inicializacii pola pre citanie nastavit r_mask = 0 a p_readdata = buffer.

Neměla by se r_mask taky posunovat?

Ano mala sorry :) V principe by som to dal na zaciatok fcie
r_mask>>=1;

Este skus tie bitove funkcie deklarovat ako inline aj ked to moze prekladac robit aj sam v zavislosti na optimalizacii. Prekladaj v nastaveni release, ne debug (v debug profile su vypnute optimalizacie)

Tak kódování běží o 1 až 1,5 fps rychleji. Funkce označené inline, překládáno jako release. Ovšem přehrávání padne okamžitě po spuštění. Nějaká chyba ještě pořeším to. Ale i za ten drobný posun díky.

edit: po zápisu complete_byte do pole se musí vynulovat. V tom to bylo.

edit 2: při kódování videa s menším rozlišením je rozdíl mohem větší, 5 - 10 fps navíc.

skus to este prerobit na 32bit, mask = 0x80000000, a drzat si unsigned int, a zapisat 4bajty naraz ked !mask
Fciu SetBit() mas dufam urobenu extra nech sa usetri to if(bit)
P.S. a snazit sa optimalizovat aj tu hlavnu slucku, tam by sa dalo asi usetrit dost. Neviem jak presne to mas naprogramovane

Předělání na 32-bit přineslo zatím největší nárůst výkonu . Zatím to mám jen na straně kodéru. Prosím o příklad, jak to udělat v dekodéru - jak naskládat 4 bajty do dword. Nejsem si jistý těmi posuny.

edit: Už dobré.

U citania to asi moc neprinesie, mozno to dokonca aj spomali ptz to tam zbytocne musi ladovat do toho dwordu, ale u citania sa da optimalizovat samotny dekodovaci algoritmus, ptz ten standardny to je hrozne neefektivna haluz.

Skus to takto

     while (bitreader.hasLeft())
     {
         nr = 0;
         while (bitreader.getBit()) nr+=M;
         for (mask = 1; mask < M; mask<<=1)
             if(bitreader.getBit())
                 nr |= mask;
         intwriter.putInt(nr);
     }

P.S. a aj tie hasLeft funkcie u bitreaderu a bytereaderu mozu mat vplyv ak su nejake neefektivne. Ale snad tam mas len jedno if s 2 testami (test aktualny pointer oproti pointru konca buffra alebo (pointer-buffer < length) a test r_mask != 0 u bitreaderu)

Funkci pro dekódování jednoho symbolu mám takto:

int JKvideocodec::decode_symbol(int M, int K)
{
  int num = 0, remain = 0;

  while (next_bit()) // Cislo
    num += M;

  for (int i = 0; i < K; i++) // Zbytek
    remain = remain << 1 | next_bit();

  return num + remain; // Vrati soucet
}

U tvého návrhu si nejsem jistý tím for cyklem. Má se načíst K bitů, které představují zbytek.
M a K musím předávat, protože mohou být u každého symbolu jiné.

moj cyklus je spravny :)

Jak mas rieseny next_bit() ked to tam rovno or-ujes? Tebe nextbit musi vracat bit na pozicii 0, v tom pripade je lepsie v nextbit bajt rotovat, tam mozes mat neefektivitu. Ked na to nevidim tak nemozem optimalizovat :)

Však next_bit jsme už řešili.

inline bool JKvideocodec::next_bit()
{
  r_mask >>= 1;

  if (!r_mask)
  {// Nacist dalsi dword
    dword = (*(p_readdata + 3)) | (*(p_readdata + 2) << 8) | (*(p_readdata + 1) << 16) | (*p_readdata << 24);
    r_mask = 0x80000000;
    p_readdata += 4;
  }
	
  return (dword & r_mask);
}

tak potom mas dekodovaciu fciu uplne blbo

(jaj uz vidim ty ju mas bool, to je dost blby napad ked optimalizujes tak nerob veci ktore prekladac musi konvertovat a ani nevies na jaku hodnotu. Kolko to je int | bool ? bool TRUE moze byt kludne aj FFFFFFFF). Zmen tu fciu nextbit na unsigned int, a urob to s if jak to mam ja v cykle.

P.S. a este ktomu tebe to dava prvy bit na najvyssiu poziciu a spravne ma byt na najnizsej t.j. pri vyssich M to budes mat uplne zle. Urob to jak som pisal a nextbit zmen na unsigned int nech to nemusi prekladac konvertovat

Změněno, funguje. Díky.

A to
dword = (*(p_readdata + 3)) | (*(p_readdata + 2) << 8) | (*(p_readdata + 1) << 16) | (*p_readdata << 24);
je silne neoptimalne, najoptimalnejsie je:
dword = _byteswap_ulong( *((unsigned int*)preaddata) );
ak pouzivas MSVC a x86 architekturu

Jádro kodeku by mělo být nezávislé na platformě. Budu ho později vkládat i do ffmpeg na linuxu.

Skus este
dword = *p_readdata++;
dword <<= 8;
dword = *p_readdata++;
dword <<= 8;
dword = *p_readdata++;
dword <<= 8;
dword = *p_readdata++;
dword <<= 8;
ci to nebude rychlejsie (zmeraj FPS)

Sorry oprava (copy paste :D), takto:
dword = *p_readdata++;
dword <<= 8;
dword |= *p_readdata++;
dword <<= 8;
dword |= *p_readdata++;
dword <<= 8;
dword |= *p_readdata++;

P.S. malo by to byt takto optimalnejsie lebo menej operacii, ale nie o vela, mozno par CPU cyklov. Mozno to bude aj uplne stejne P.S. mozno aj horsie o par cyklov zavisi na compileri tazko povedat :)

Je to prakticky stejné, rozdíl možná tak o desetiny fps.

Tak este vyhod to for ak M==2 a uz to asi lepsie nejde.

if(M==2)
{ while (bitreader.hasLeft())
     {
         nr = 0;
         while (bitreader.getBit()) nr+=2;
         if(bitreader.getBit())
             nr |= 1;
         intwriter.putInt(nr);
     }
}
else
{ while (bitreader.hasLeft())
     {
         nr = 0;
         while (bitreader.getBit()) nr+=M;
         for (mask = 1; mask < M; mask<<=1)
             if(bitreader.getBit())
                 nr |= mask;
         intwriter.putInt(nr);
     }
}

podobne aj v koderi (neviem jak presne mas momentalne implementovany koder). Tiez neviem kolko uspory to prinesie :) Zavisi od prekladaca.

Potom este sa da urobit to cele multithread pricom toto bude jeden thread a ostatne veci (konverzia farby a predikcie atd) budu dalsie thready, komunikovat to bude cez nejake FIFO buffre (pozor na critical section). To je ale potom uz komplikovanejsie na realizaciu.

A zrus aj tu fciu decodesymbol, to volas z while slucky zas nejaku fciu. Alebo ju aspon urob inline. Uspora sice nic moc, ale ked optimalizujem tak poriadne :D

zrus aj tu fciu decodesymbol, to volas z while slucky zas nejaku fciu

Tyjo ono to fakt pomohlo, zrušil jsem i funkci pro přepočet liché hodnoty na zápornou, všechno je v hlavní smyčce a jsem na 20 fps.

P.S. doufám že ve škole pochopí, že nejsem programátor prase, ale tohle je kvůli výkonu

pozor na critical section

No právě s tím by bylo strašného drbání a výsledek není zaručený. Já si změřím která část programu zabírá nejvíc času, hádám že po optimalizaci už to bude ta hlavní - prediktor. A ani to nemám za úkol dělat multithread.
Za tvou dosavadní pomoc ti děkuji.

Ok este posledna pripomienka - ked si to zmenil na dwordy, tak musis davat pozor ked data nie su alignovane na 4byty, aby si tam nezasahoval niekde za koniec buffra alebo co (buffer alokovat vacsi jak data t.j. bud na pocetdat+4 alebo alignovat nahor) a aj tie testy ci este je nejaky bajt musia byt na urvoni poctu bajtov alebo bitov, nie dwordove. A ked zapisujes do buffra tak tiez nevidim test ci sa dosiahol koniec buffra, to by tam malo byt, neviem jak to mas riesene, to necham na teba :)

.. a pri zapisovani nezabudnut dozapisovat aj ten dword ak v nom su nejake bity. V zavislosti na tom jak mas definovany alignment v tom tvojom subore, ak na konci ostanu napr. 3bity apod. tak zapisat bajt(y) toho dwordu ktore obsahuju nejake bity.

I přehrávání je výrazně rychlejší. 720p video předtím 11 fps, teď 17 fps.

while(intreader.hasLeft())
{
int num = intreader.getInt();
int q = num / M;
for (int i = 0 ; i < q; i++)
bitwriter.putBit(true); // zapíše q jedniček
bitwriter.putBit(false); // zapíše jednu nulu
// int v = 1;
for (int i = 0 ; i < log2(M); i++)
{
bitwriter.putBit( num & 0x01);
num >> 1;
}
}

Nasledne kedze putbit dostane vzdy hodnotu na bite 0, mozes vyhodit to if z funkcie putbit, a rovno tam urobit OR s paramterom.

Alebo cela ta druha cast sa da zoptimalizovat ptz je to len principialne nahod do bitsreamu spodnych i bitov z num, ak by si si drzal poziciu bitu a pracoval bajtovo naraz (jak som uz pisal na zaciatku ten iny pristup) tak si drzim nejaky QWORD a ulozim naraz qword |= ((num & maska[log2M]) << aktualnapoziciabitu), vyhodne je to ak je to M vyysie. Pri M=2 to nema nezmysel.

P.S pripadne este pred tym while(intreader.hasLeft()) si testovat ci M neni 2 a ak je tak to urobit uplne bez cyklu "for (int i = 0 ; i < log2(M); i++)" a bez rotacie num>>1 ptz to nema vyznam ak M=2. Tu prvu cast num / M zmenis na num/2 (optimalnejsie). A potom do else vetvy (pre M>2) to urobit normalne alebo este rozdelit pre M==4 nerobit for ale len 2x za sebou nieco, a az pre vyssie M v dalsom else robit potom cykly apod.

Vyšší M není moc výhodné. Kódují se hodnoty, mezi kterými je suveréně nejvíc nul. Dokonce jsou situace, kdy je vhodné nastavit M=1 a kódovat v podstatě run-length.

Tohle je třeba histogram z jednoho snímku. Ty hodnoty se ještě posunou tak, aby ze záporných čísel byly kladné liché a z kladných byly kladné sudé. Nuly ale zůstanou stejné.

Ja to kodovanie moc nechapem podla mna je to nezmysel (jaky ma vyznam zapisat namiesto cisla 100 nejakych 50jedniciek (8bajtov namiesto 1 bajtu), ale nemam cas to studovat teraz. Len pisem jak sa to optimalizuje - ak mi vnutri cyklu nieco zavisi na nejakom nemennom M, tak to if(M dam mimo cyklu a v programe bude ten samy cyklus trebars 10x, vzdy optimalny pre ine M, a vnutri cyklu uz nebude to M vobec figurovat. Ptz pre M==2 je nezmysel robit tam cykly for i=0;i<1;i++, da sa to zrychlit mozno aj na 2nasobok ak tam nemam to M v cykle apod :)

Jo rozumím, díky.
Jen stručně ke kódování: Mám pixel s hodnotou 125 a 3 okolní pixely, např. 130, 115, 140 a já odhadnu, že následující pixel bude 120. Pak tento odhad porovnám se skutečnou hodnotou a vypočtu chybu, o kolik jsem se seknul, tj. v tomto případě o 5. No a tuto chybu zakóduju třeba s parametrem M=2 na 1101. Tady je úspora poloviční. Když se trefím na 100% a chyba je 0, tak je výsledek 01. Úspora 4x. Stojí to celé na vhodné predikci.