Aktív témák

• #1 P.H. senior tag

  2008-10-14 00:40:45 #1

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  P.H.

  senior tag

  Blog.

  Magamnak.

  Sok dolog elveszett már az elmúlt évek alatt.

  Tehát mondjuk online archiválok. Mondjuk ide. Próba szerencse.

  Adott egy feladat: talán kétrétegű rajzolás lehetne a neve. Adott egy NxM pixel méretű 32 bites kép, amelyre rajzolni kell, de csak bizonyos mintában, amelyet egy 8x4 bites érték ír le: minden sorhoz egy 8 bites minta tartozik, amely ahol 1, az adott pixelen felül kell írni az eredeti képet a layeren lévő rajzzal, hacsak az nem egy előre kijelölt 'háttérszín'; és minden 4 sorhoz tartozik egy ismétlődő minta.

  A megvalósítási ötlet szerint mivel egy kép nem tartalmazhat 32 bites negatív pixel értéket (32 bites megjelenítés megkövetelt, ez alatt nincs értelme a SETDIBITSTODEVICE forrásadatában negatív értéket megadni), így a kisegítő layer (amire első körben a rajzolás történik) háttérszíne tetszőleges negatív szám lehet. A kisegítő layer legyen ugyancsak NxM-es tömb, erre lefutnak a módosítás nélküli rajzolási eljárások a kívánt pixeleket felülírva benne a megfelelő színre, ezután fésüljük össze a két 'képet' az adott minta szerint.

  pushad
  mov ecx,{képszélesség}
  mov ebx,{rajzolási maszk}
  mov esi,{layer címe}
  push {képmagasság}
  shl ecx,02h
  mov edi,{célkép címe}
  mov edx,ecx
  mov ebp,ebx
  @inner:
  sub ecx,04h
  js @outer
  ror bl,01h
  mov eax,[esi+ecx]
  mov dword ptr [esi+ecx],-1
  jnc @inner
  test eax,eax
  jl @inner
  mov [edi+ecx],eax
  jmp @inner
  @outer:
  ror ebp,08h
  add edi,edx
  add esi,edx
  sub dword ptr [esp],01h
  mov ecx,edx
  mov ebx,ebp
  jnz @inner
  @exit:
  add esp,04h
  popad
  ret

  Több ponton is bele lehet kötni a fentiekbe:
  - a Core 2 processzorok LSD-je 4x16 byte-nyi utasítást tud tárolni, benne legfejlebb 4 ugró utasítással, ret nélkül; a fenti @inner ciklus az @outer ciklussal együtt is bőven beleférne a 64 byte-ba, viszont 5 ugró utasítás van benne; ha egyet eliminálni lehetne, akkor a szükséges adatok egyszeri beolvasása után sosem kell a teljes kép feldolgozása során az L1 I-cache-hez fordulni.
  - a K8 CPU-k optimalizálási leírását bogarászva kitűnik, hogy a hardware prefetcher-e a cache-vonalakat csak növekvő sorrendben tudja előbetölteni, a fenti eljárás viszont egy adott képsoron visszafelé halad, mivel az @inner ciklusban az offszet (ecx) csökken.

  pushad
  mov ecx,{képszélesség}
  xor edx,edx
  mov ebx,{rajzolási maszk}
  mov esi,{layer címe}
  push {képmagasság}
  shl ecx,02h
  mov edi,{célkép címe}
  not ebx
  sub edx,ecx
  mov ebp,ebx
  @outer:
  sub edi,edx
  sub esi,edx
  sub dword ptr [esp],01h
  mov ebx,ebp
  lea ecx,[edx-04h]
  ror ebp,08h
  js @exit
  @inner:
  or eax,-1
  add ecx,04h
  jns @outer
  xor eax,[esi+ecx]
  mov dword ptr [esi+ecx],-1
  ror bl,01h
  jbe @inner
  not eax
  mov [edi+ecx],eax
  jmp @inner
  @exit:
  add esp,04h
  popad
  ret

  A következő változások történtek:
  - a korábbi "a layer háttérszíne tetszőleges negatív szám lehet" feltétel szűkült arra, hogy csakis -1 lehet
  - az @outer ciklus is elöltesztelős lett: átlép a következő sor elejére, így az @inner 0 felé egyre közelítő negatív offszettel fér a két tömb pixeleihez.
  - az @inner ciklusban eggyel kevesebb ugrás található, viszont miután az XOR -1,x utáni ROR reg,01h nem változtatja a ZF-et (sem, csak az OF-et és CF-et), így a JBE (jump if below or equal = jump if CF = 1 or ZF = 1) mindkét feltételt egyszerre kezeli; ehhez viszont bit-negálni kell a maszkot a ciklusok előtt.
  Ilyen jellegű megoldás nem létezik magas szintű programozási nyelvekben.

  A következőkben nem történt változás:
  - a 8 használható regiszter közül csak háromnak változik az értéke az @inner ciklusban, ezért képsoronként egyszer a Core 2 belefut az @outer ciklus elején a registerfile-olvasási korlátjába, mivel EDI, ESI, EDX, ESP és EBP is 'befagyott' register-nek tekinthető.
  - ha lenne még egy szabad register, amelyben a -1 konstans tárolható lenne, akkor 1+1+2 byte-tal kisebb lenne a két ciklus kódja, ez x64 alatt megoldható lenne.

  Az elméleti nyereség:
  - bármilyen egyszerű hardware prefetcher-rel ellátott microarchitecture esetén a két tömbön végigmenni minimális L1/L2 cache-tévesztéssel jár (az is nagyrészt csak a 4 KB-os lapok miatt van)
  - teljesen üres layer esetén csakis a jns @outer ugrásánál lehet téveszteni (soronként egyszer)
  - teljesen kitöltött layer esetén a ror bl,01h bizonyos, 8 esetenként ismétlődő minta szerint dolgozik, amit a többszintű ugrás-előrejelzőknek illik lekezelni
  - az algoritmus jól kezeli a layer folyamatos huzamosabb háttér- ill. előtér sorozatait, viszont a gyakori váltásokat nem (ott jobban teljesít az első algoritmus).

  A gyakorlati nyereség: K8 és két, különböző (Kb. 80% és 10%) kitöltöttségű ~2 megapixeles kép+layer esetén TSC-rel kimérve 25M/33M-ról 15M/24M órajel.

  [ Szerkesztve ]

  Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙

Aktív témák