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é.

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);
}

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.