BGAFC Vendégkönyv

Σ: 1 post

TCH (statz)

#1, Főfasz (10443)

9061 | #2f11 | ^ | Idézet | Sun, 23 Nov 2014 20:41:53 +01

46.139.*.*

*.catv.pool.telekom.hu

Boldog május elsejét minden kecskekúrógépnek.
Mai témánk az RGB komponensek kiterjesztése, illetve összezsugorítása.

Széleskörben elterjedt téveszme az, hogy az RGB komponensek kiterjesztése, ill zsugorítása pofonegyszerűen megoldható egyetlen sima shifteléssel: ha 4 bitről 8-ra terjesztünk ki, vagy 8-ról 4-re zsugorítunk, akkor az 4 bit eltolás balra vagy jobbra, ha 8-ról bővítünk 16-ra, vagy 16-ról 8-ra, akkor az 8 bit eltolás egyik vagy másik irányba.
Ez egyébként valóban működik így...csak épp szarul. Ez a probléma jelen volt már Amigán is (amikor megjelent az AGA és az addig 12-bites RGB kódokat 24-bitesre kellett kiterjeszteni), de jelen van még ma is, amikor pl. olyan PNG-vel dolgozik az ember, amiben a komponensek nem 8-bitesek, hanem 16.
Mi is ezzel módszerrel a baj? Az, hogy nem pontos. Minden sötétebb lesz, mint kéne, hogy legyen. Nézzük csak végig, hogy miért. Először a 4/8-as párt.

Ha egy 4-bites komponenst kiterjesztünk sima 16-os szorzással (4-bites eltolás), akkor valami ilyesmi fog történni: 0x5 => 0x50
Miért nem jó ez? Azért, mert a 4-bites skálán az 0x5 az baromira nem ugyanaz a fényerő, mint a 8-bitesen az 0x50. Ezzel az értékkel annyira nem egyértelmű, de nézzük meg egy másikkal! 0xf => 0xf0
Ugye, hogy baromira nem stimmel valami? 4 biten az 0xf a maximum fényerőt jelenti, míg 8-biten az 0xf0 közel sincs hozzá, ami azt illeti, 4 bitre visszavezetve, arányaiban közelebb áll az 0xe-hez, mint az 0xf-hez!
A miértje egyszerű ennek a dolognak: a konvertálás lépésköze nem stimmel, mert az nem 16. Az arányos lépésközt pedig úgy lehet kiszámítani, hogy a két skála lépéseinek számát elosztjuk egymással. Ha a 4-bites komponenst nézzük, akkor ott a nulla után 15 db lépés van 0xf-ig. Ha a 8-bitest, akkor 255 lépés van 0xff-ig. 255 / 15 = 17. Ergo a 4/8-bites konverzióknál 17 az arányos lépésköz és nem 16. Tehát 0x5-ből nem 0x50 lesz, hanem 0x55 és 0xf-ből sem 0xf0, hanem 0xff. 17-tel kell szorozni vagy osztani, nem 16-tal. És ugyanez a szabály vonatkozik a 8/16-bites konverzióra. 65535 / 255 = 257, tehát ott pedig 257 a lépésköz.

A zsugorítás már egy picit trükkösebb. Ott ugyanis nem elég a lépésközzel leosztani az értéket, mert pl. 0xed / 17 = 13 azaz 0xc lesz, holott az 0xed-ből ugyanúgy 0xe kéne, hogy legyen, mint az 0xee-ből. A trükk persze nem agysebészet: kerekíteni kell. Persze egy komponens zsugorításánál orbitális baromság lenne lebegőpontos műveleteket végezni; erre való a maradékos osztás: ha a maradék nagyobb, mint a lépésköz fele, akkor inkrementálni kell a normál osztás végeredményét.

Ennek megfelelően:
4=>8: c * 17
8=>16: c * 257
8=>4: (c / 17) + (c % 17 > 8)
16=>8: (c / 257) + (c % 257 > 128)
Ez persze nem kicsit lassabb, mint a 16-al/256-al való szorzás-osztás, ami gyakorlatilag 4/8 bittel való tologatás. Nade, lehet optimalizálni.

A szorzást gyerekjáték. x * (2ⁿ + 1) = (x << n) + x

Az osztást már szopatósabb, főleg, mivel kétféle osztás is van benne. Ami azt illeti, modern procin nincs is értelme lebontani más, egyszerűbb műveletekre, mert lassabb lesz, mint maga az osztás lenne. (A szorzásra ez nem vonatkozik, az egy shift és egy összeadás modern gépen is gyorsabb lesz, mint az egy szorzás.) Régi procin (pl. 68000-esen) viszont már van értelme.
Egyik optim. módszer a táblás verzió. (Az egyébként még a szorzáson is gyorsítana, a tábla gyorsabb, mint a shift + összeadás.) Viszont a táblával a 16-bites komponens zsugorításánál lesz egy "kis" gond. Az, hogy rohadtul 64 kB hosszú lesz. A másik három tábla nem olyan nagy (4=>8: 16 byte, 8=>16: 512 byte, 8=>4: 256 byte), együttesen sem foglalnak le 1 kB-t, de a negyedik az bazinagy lenne. A helytöbblet sokszorosa a sebességtöbbletnek. (Modern gépen, ahol egy osztás már 3-4 ciklus, ott többezerszerese, régi gépen, ahol az osztás még több mint 100 ciklus volt, ott többtízszerese.) Modern gépen kurwára értelmetlen, régi gépen meg kurwára nem fér el.

Viszont valami beugrott, ahogy keresgettem, hogy hogy lehet kiegyszerűsíteni a 257-el való osztást. (Egyébként semmit nem találtam rá.) A 255-el való osztásra egyszer már találtam valami (félig-meddig) megfelelő megoldást. Az a képlet úgy szólt, hogy x / 255 = (x * 257) / 65536 (kivéve ha a maradék nulla). Ami nem volt teljesen igaz, mert 10 milliomodos nagyságrendű eltérés van a két képlet között. Na, az 16 bitre még bőven jó. 8-ra meg főleg. Na, most mivel a 255 meg a 257 pont ugyanakkora távra vannak a 256-tól, így gondoltam fel lehet őket cserélni, amúgy ugyanaz a megoldás (modulóstul):
(((x << 8) - x) >> 16) + (x % 257 == 0 && x != 0)
Írtam egy rövid C programot, ami az x / 257-et 0-tól 65535-ig összehasonlította ezzel a képlettel. 100%-os találat volt, vagyis az elgondolásom a 255<->257 cserélhetőségről jó volt.
A modulótól persze még nem szabadultunk meg, de közben ki akartam próbálni, hogy működik-e eggyel lejjebb is, 15<->17 felállásban:
(((x << 4) - x) >> 8) + (x % 17 == 0 && x != 0)
Ez is egyezett az x / 17 összes lehetséges eredményével. Na persze, még korai az öröm, a moduló még mindig ott kolbászol, rohaggyonmeg és úgy meg nem sok értelme van kiegyszerűsíteni egy osztást, ha lesz benne helyette egy másik.
Poénból kipróbáltam, hogy mi lesz, ha a % 17-et kicserélem bitmaszkra (& 15, ez tkp. a % 15 megfelelője). Nem vártam tőle semmit, de az eredményen néztem egyet, mert 256-ból 241 így is helyes eredményt adott ki, viszont ami igazán széppé tette az egészet az az, hogy csak ott nem stimmelt, ahol x alsó és fölső 4 bitje megegyezett (értsd: 0x11, 0x22, 0x33, ...). Sz*rk: Közben leesett, hogy ennek magyarázata abban rejlik, amit fentebb vezettem le, hogy x * 17 = (x << 4) + x, azaz a 17 szorzatainál az alsó és a felső 4 bit mindig ugyanaz. Magyarán az x % 17 == 0 felírható így is:
(x >> 4) == (x & 15)
Úgyhogy ebből már gyerekjáték volt kirakni a képlet végét:
(((x << 4) - x) >> 8) + (uint8_t)(((x >> 4) == (x & 15)) && (x != 0))
Tehát így lehet felírni a 17-el való osztást. És ennek megfelelően a 257-el való osztást meg így:
(((x << 8) - x) >> 16) + (uint16_t)(((x >> 8) == (x & 255)) && (x != 0))
És egyben akkor általános képlet gyanánt is leírható, hogy (16 biten!!!)
x / (2ⁿ + 1) = (((x << (n / 2)) - x) >> n) + (((x >> (n / 2)) == (x & (2ⁿ - 1))) && (x != 0))

No, eddig igazán kurwa jók vagyunk, csak az a baj, hogy a felezős moduló még mindig ott rohad. :P Viszont fel és alá kísérletezgetés közben leesett, hogy bazzeg a moduló, az maradék, hát ha az egész osztás eredményét visszaszorozzuk, akkor annak az eredménye és az eredeti szám különbsége az a maradék! (Ne röhögjetek, kurwa szar vagyok matekból!)
Azaz érthetőbben x % y == x - ((x / y) * y) Ebben ugyan megint van egy szorzás, de azt mint fentebb már kitrágyaltuk, x * 2ⁿ+1 esetén azt picsafasz kiegyszerűsíteni. Tehát (c / 17) + (c % 17 > 8) helyett:

tmp = (((x << 4) - x) >> 8) + (uint8_t)(((x >> 4) == (x & 15)) && (x != 0));
result = tmp + (x - (uint8_t)(((tmp << 4) + tmp) > 8));

És (c / 257) + (c % 257 > 128) helyett:

tmp = (((x << 8) - x) >> 16) + (uint16_t)(((x >> 8) == (x & 255)) && (x != 0));
result = tmp + (uint16_t)(x - (uint16_t)(((tmp << 8) + tmp) > 128));

Ennek megfelelően valahogy így lehet felírni a dolgokat:

#define component4_extend(c, r) (r) = ((c) << 4) + (c)
#define component8_extend(c, r) (r) = ((c) << 8) + (c)

#ifdef EZ_EGY_REGI_PROCI
#define component8_shrink(c, r, tmp) tmp = ((((c) << 4) - (c)) >> 8) + (uint8_t)((((c) >> 4) == ((c) & 15)) && ((c) != 0)); r = tmp + ((c) - (uint8_t)(((tmp << 4) + tmp) > 8))
#define component16_shrink(c, r, tmp) tmp = ((((c) << 8) - (c)) >> 16) + (uint16_t)((((c) >> 8) == ((c) & 255)) && ((c) != 0)); r = tmp + ((c) - (uint16_t)(((tmp << 8) + tmp) > 128))
#else
#define component8_shrink(c, r, tmp) r = ((c) / 17) + (uint8_t)((c) % 17 > 8)
#define component16_shrink(c, r, tmp) r = ((c) / 257) + (uint16_t)((c) % 257 > 128)
#endif

Huh, bazdmeg. Az elején nem gondoltam volna, hogy sikerül a 17-el és 257-el való osztásokat kiegyszerűsíteni. Ezért nem szabad soha feladni. :P
Viszont mégegyszer mondom, hogy modern procin nincs értelme kiegyszerűsíteni az zsugorítóst, ergo ott nem kell definiálni az EZ_EGY_REGI_PROCI makrót.

Köszönöm a figyelmetlenséget, belétek is bazdmeg. Továbbá bikacsököt bilgécnek és a kurwa anyját a mikrofosnak.