webhostinggeeks.com

ASM LAB Ova stranica je uglavnom namenjena osobama koje su već upoznate sa asemblerom i sa C implementacijom da bi videle zašto je često veoma korisno da se koristi direktna asemblerska implementacija u odnosu na primenu čiste C implementacije. Postoje, po mom mišljenju, previše programera koji jednostavno ne znaju koju razliku čine ručno kodirani asembleri. Nadam se da ću pomoći da se popravi ova situacija. Ako imate druge primere, ili ulazne jedinice (ili izazove) koje se tiču ove stranice, ne oklevajte da me kontaktirate.

GCD

Na comp.lang.asm.x86, Jon Kirwan je zatražio izlazni kompajler za "najveći zajednički delilac" funkciju iz sledeće C implementacije:

unsigned int gcd (unsigned int a, unsigned int b)
{
    if (a == 0 &&b == 0)
        b = 1;
    else if (b == 0)
        b = a;
    else if (a != 0)
        while (a != b)
            if (a <b)
                b -= a;
            else
                a -= b;

    return b;
}

Ovo je moj omiljeni C kompajler sa /OS/s opcijama (optimizacija za veličinu, ne koristite nikakvu proveru steka, druge optimizacione opcije nisu mnogo pomogle) naspram ljudske (tj. mene) implementacije:

; WATCOM C/C++ v10.0a output

gcd:   mov     ebx,eax
        mov     eax,edx
        test    ebx,ebx
        jne     L1
        test    edx,edx
        jne     L1
        mov     eax,1
        ret
L1:    test    eax,eax
        jne     L2
        mov     eax,ebx
        ret
L2:    test    ebx,ebx
        je      L5
L3;    cmp     ebx,eax
        je      L5
        jae     L4
        sub     eax,ebx
        jmp     L3
L4:    sub     ebx,eax
        jmp     L3
L5:    ret

; Author: Paul Hsieh

gcd:   neg     eax
        je      L3
L1:    neg     eax
        xchg    eax,edx
L2:    sub     eax,edx
        jg      L2
        jne     L1
L3:    add     eax,edx
        jne     L4
        inc     eax
L4:    ret

Posebna slabost ovog kompajlera je da nije sigurno sa kakvim registratorima treba početi. Ali uprkos tome fali veliki broj optimizacionih mogućnosti kada se uporedi sa ljudskom implementacijom. Nema poređenja da li je u pitanju brzina ili veličina. Naravno, kao čovek, imam ogromnu prednost, jer vidim matematičke odnose koji su izgubljeni od strane svih C kompajlera.

Iako xchg nije posebno brzo Intelovo uputstvo, pomaže da ga uradite veoma dobro, i verovatno ne zahteva više od off ciklusa za optimalno obavljanje. Glavna petlja rutine pronalazi se u potpunosti preko instrukcije pre-fetch buffer (16 bajtova).

Koliko god želeo, besmisleno je pokušati i opisati tačne performanse iznad datih algoritama. Oni gotovo u potpunosti imaju ograničene performanse od strane branch mis-prediction penalties and branch taken clocks.

Ažuriranje: Sa pojavom modernih procesora kao što su Alpha, Pentium-II ili Athlon koji imaju duboke kanale i odgovarajuće kazne za loše predviđanje grananja, logično je ukloniti grane preko "predviđanja". U ovom slučaju možemo koristiti min() i max() funkcije da uklonimo unutrašnji most if() iskaz u originalnoj petlji:

        x = min (a,b);
        y = max(a,b);
        while( y!= 0 ) {
            x = min(x,y-x);     // min (x,y-x)
            y - = x;             // (y-x)+(x) - min(x,y-x)
        }

Ali na 32-bitnoj mašini:
min(x,y) = y+((x-y)>>31)&(x-y)
Tako stavljajući odgovarajuću zamenu i pojednostavljajući po potrebi dolazimo do:

int gcd(int x, int y) {
int t;

    y += x;
    if(y==0)
        y=1;
    else do {
        x += x;
        t = y- x;            // (y-x) - (x)
        x >>= 1;
        x += (t>>31)&t;     // min(y-x,x)
        y - = x;             // (y-x)+(x)-min(x,y-x) == max(x,y-x)
    } while(x!=0);

    return y;
}

Ponovo, uzimamo Pepsi izazov i dobijamo:

; WATCOM C/C++ v10.0a output

gcd: add     edx,eax
      jne     L1
      mov     eax,1
      jmp     L2
L1:  mov     ebx,edx ; 1 dep: edx
      add     eax,eax ; 1
      sub     ebx,eax ; 2 dep: eax
      mov     ecx,ebx ; 3 dep: ebx
      sar     ecx,1fH ; 4 dep: ecx
      sar     eax,1   ; 4/5 shifters
      and     ebx,ecx ; 5 dep: ecx
      add     eax,ebx ; 6 dep: ebx
      sub     edx,eax ; 7 dep: eax
      test    eax,eax ; 7
      jne     L1      ; 7
      mov     eax,edx
L2:

; Author: Paul Hsieh

gcd: add     edx,eax
      jne     L1
      mov     eax,1
      jmp     L2
L1:  mov     ebx,edx ; 1 dep: edx
      add     eax,eax ; 1
      sub     ebx,eax ; 2 dep: eax
      shr     eax,1   ; 2
      mov     ecx,ebx ; 3 dep: ebx
      sar     ebx,1fH ; 3
      and     ebx,ecx ; 4 dep: ecx
      add     eax,ebx ; 5 dep: ebx
      sub     edx,eax ; 6 dep: eax
      test    eax,eax ; 6
      jne     L1      ; 6
      mov     eax,edx
L2:

Ja sam još uvek ispred, ali u teoriji prilično dobar kompajler bi trebalo da je dobio jednake rezultate. Za razliku od prve petlje, performansa ove petlje je karakterizovana

Ažuriranje: Čuvena knjiga od Michael Abrash "The Zen of Code Optimization" zapravo govori da je metod prostog oduzimanja prespor (ovo je u suprotnosti sa testom koji sam ja izveo). Takođe sam dobio povratnu informaciju od ljudi koji insistiraju da je deljenje bolje za specifične slučajeve ili velike brojeve. I konačno šlag na torti je da u "Priručniku primenjene kriptografije" (ISBN 0-8493-8523-7), se nudi "divide out powers of two" algoritam koji izgleda kao da je dobar kompromis (ali još uvek pati od kazni za pogrešno predviđena grananja) Ja ću morati da istražim ovo malo dublje, i možda ću morati da pregledam ove rezultate. Dodatna analiza je dobrodošla.

Ažuriranje: Samo kao pitanje potpunosti, ja vam predstavljam šta sam pronašao do sada. Korišćenje onog što je očigledno klasičan pristup, radije nego korišćenjem deljenja ili oduzimanja, mi oduzimamo powers of 2 puta manju vrednost od veće. Pored toga, umesto da sledimo GCD algoritam celim putem, kada budemo imali dovoljno male vrednosti za a i b, samo radimo pronalaženje tabela (popunjavanja tabela nisu pokazana ovde.)

#define SLIM (64)

static unsigned smallGcds[SLIM][SLIM];

static unsigned uintGcd (unsigned a, unsigned b) {
unsigned c, d;

    /* Divide out low powers of 2 if we can (to decrease a, b) */

    d = 1;
    while (((a|b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        d <=>
    }

    goto start;

    do {
        /* Find largest 2^t*b, less than a */
        c = b;
        do { c += c; } while (c <=>

        /* a -= 2^t*b */
        a -= (c >> 1);

        start:;

        /* Make sure a > b, and b != 0 */
        if (a < b)="" {="">
            if (a == 0) return d * b;
            c = a; a = b; b = c;
        }
    } while (a >= SLIM);

    /* Return with precalculated small gcds */
    return d * smallGcds[a][b];
}

Očigledno, neki slučajevi (a,b) inputa moraju biti provereni (a=0, b=0 šalje program u beskonačnu petlju.)

Verujem da je moguće da se ovo poboljša tako što se obavi pronalaženje tabela na nekoliko bitova od svakog operanda odjednom što bi trebalo da obezbedi glavne linearne faktore koji bi mogli da se iskoriste da bi se smanjili operandi za nekoliko koraka u jednom pokušaju. Tako da se suzdržavam od obavljanja analize jezičkog asemblera dok ne rešim ovo.

Ažuriranje: Postoje brojni podnesci koji su mi privukli pažnju. Prvi je iz Pat D:

; int gcdAsm(int a, int b)
;
; computes gcd(a,b) according to:
; 1. a even, b   even: gcd(a,b) = 2 * gcd(a/2,b/2),
;    and remember how often this happened
; 2. a even, b uneven: gcd(a,b) = gcd(a/2,b)
; 3. a uneven, b   even: gcd(a,b) = gcd(a,b/2)
; 4. a uneven, b uneven: a>b ? a -= b : b -= a,
;    i.e. gcd(a,b) = gcd(min(a,b),max(a,b) - min(a,b))
; do 1., repeat 2. - 4. until a = 0 or b = 0
; return (a + b) corrected by the remembered value from 1.

    BITS 32
    GLOBAL _gcdAsm

    SECTION .text
_gcdAsm:
    push ebp
    mov ebp,esp
    push ebx
    push ecx
    push edx
    push edi
    mov eax,[ebp + 8]   ; eax = a (0 <= a <= 2^31 - 1)
    mov ebx,[ebp + 12]   ; ebx = b (0 <= b <= 2^31 - 1)
    ; by definition: gcd(a,0) = a, gcd(0,b) = b, gcd(0,0) = 1 !
    mov ecx,eax
    or ecx,ebx
    bsf ecx,ecx         ; greatest common power of 2 of a and b
    jnz notBoth0
    mov eax,1           ; if a = 0 and b = 0, return 1
    jmp done
notBoth0:
    mov edi,ecx
    test eax,eax
    jnz aNot0
    mov eax,ebx         ; if a = 0, return b
    jmp done
aNot0:
    test ebx,ebx
    jz done             ; if b = 0, return a    bsf ecx,eax         ; "simplify" a as much as possible
    shr eax,cl
    bsf ecx,ebx         ; "simplify" b as much as possible
    shr ebx,cl
mainLoop:
    mov ecx,ebx
    sub ecx,eax         ; b - a
    sbb edx,edx         ; edx = 0 if b >= a or - 1 if a > b
    and ecx,edx         ; ecx = 0 if b >= a or b - a if a > b
    add eax,ecx         ; a-new = min(a,b)
    sub ebx,ecx         ; b- new = max(a,b)
    sub ebx,eax         ; the difference is >= 0
    bsf ecx,eax         ; "simplify" as much as possible by 2
    shr eax,cl
    bsf ecx,ebx         ; "simplify" as much as possible by 2
    shr ebx,cl
    jnz mainLoop        ; keep looping until ebx = 0
    mov ecx,edi         ; shift back with common power of 2    shl eax,cl
done:
    pop edi
    pop edx
    pop ecx
    pop ebx
    mov esp,ebp
    pop ebp
    ret                 ; eax = gcd(a,b)

Drugi podnesak je od Ville Miettinen koji radi (ili je radio) za hybrid graphics koristeći uputstva cmovCC:

/*---------------------------------------------------//*!
* brief   Computes GCD of two 32- bit unsigned integers
* param   x First unsigned integer
* param   y Second unsigned integer
* return  gcd(x,y)
* note    gcd(x,0) -> x, gcd(0,y) -> y
* note    Implemented in x86 assembler (PentiumPro and
*         above only as cmov instructions are used)
* note    Send all comments/whines to wili@hybrid.fi
* todo    [wili 021026] Implement another version that
*         uses sbb trickery rather than cmov
*         instructions
*-----------------------------------------------------*/
#pragma warning(disable:4035) // no missing return value
inline unsigned int gcd (Uint32 x, Uint32 y) {
  __asm {
    mov   ecx, dword ptr [y]
    mov   edx, dword ptr [x]
    test  ecx, ecx
    mov   eax, edx
    je    done               ;// if (y = 0) -> return x
    test  eax, eax
    mov   eax, ecx
    je    done               ;// if (x = 0) -> return y
    push  edi
    bsf   ebx, eax           ;// ebx = trailingZeroes(y)
    bsf   ecx, edx           ;// ecx = trailingZeroes(x)
    cmp   ebx, ecx
    mov   edi, ecx
    cmovl edi, ebx           ;// edi = min(ebx,ecx)
    shr   edx, cl            ;// x >>= trailingzeroes (x)
    mov   ecx, ebx
    shr   eax, cl            ;// y >>= trailingzeroes (y)
    align 8
  mainloop:                  ;// for (;;)
    cmp   eax, edx
    mov   ecx, eax
    je    skiploop           ;// if (x == y) - > break
    cmovb eax, edx
    cmovb edx, ecx           ;// if (y > x) swap(x,y)
    sub   eax, edx           ;// x -= y
    bsf   ecx, eax
    shr   eax, cl            ;// x >>= trailingzeroes (x)
    jmp   mainloop
    align 8
  skiploop:
    mov   ecx, edi
    shl   eax, cl            ;// return x<<finalShiftLeft
    pop   edi
  done:                      ;// return value&n bsp;in eax
  }
}
#pragma warning(default:4035)

Opseg skeniranja strukture pakovanja za ključ bez nule

Pretpostavimo da želimo da skeniramo niz struktura kako bi ustanovili da li neka ima vrednosti bez nule kao poseban unos. To jest, pretpostavimo da želite da implementirate sledeću funkciju:

unsigned int existnzkey (struct foobar * table, unsigned int tablelength)
{
    int i;

    for(i=0;i<tablelength;i++)
        if( table[i].key !=0 ) return table[i].key;

    return 0;
}

U svom sadašnjem obliku, ovaj kod pati od previše problema potrebnih za neodložnu analizu na asemblerskom nivou. Primenjujući genijalnosti i neke standardne trikove kao što je opisano na mojoj optimizovanoj strani dolazim do:

static unsigned int existnzkey (unsigned int tablelength, struct foobar * table)
{
    int i,c,d;

    d=i=0;
    c=tablelength;

    goto Start;
    do {
        d = table[i].key;
        if( d !=0 ) return d;
        i++;
        c--;
Start:;
    } while( c!=0 );

    return d;
}

Iako deluje znatno duže i izgleda da dodaje nepotrebnu kompleksnost, zapravo pomaže kompajleru praktično dajući mu promenljivu da bi registrovao mapu. Sada mnogi mogu komentarisati da je upotreba idi na i oznaka loša i da dovodi do toga da kompajleri gase optimizacije ili šta god. Pa, moj kompajler ne izgleda da ima problem sa tim, što je razlog zašto sam ga koristio.

Pod pretpostavkom da imamo:

struct foobar {
    unsigned int key;
    void * content;
};

ovde je asemblerski izlaz kompajlera naspram mog ručnog kodiranja

; compiler

    xor     eax,eax
    test    ecx,ecx
    je      L2
L1: mov     eax,[esi]   ; 1 U -
    test    eax,eax     ; 2 U
    jne     L2          ; 2   V
    add     esi,8       ; 3 U
    dec     ecx         ; 3 V
    jne     L1          ; 5 - V +1brt
L2:

; by Pisen Chiang and Paul Hsieh

    xor     eax,eax
    test    ecx,ecx
    je      L2
    sub     esi,8
L1: add     esi,8       ; 1 U
    sub     ecx,1       ; 1   V
    sbb     eax,eax     ; 2 U -
    or      eax,[esi]   ; 3 U
    jz      L1          ; 4   V +1brt
    mov     eax,[esi]
L2:

Kompajler osvaja takmičenje u veličini, ali moje je mnogo brže, jer sam izbegao dodatni test i grane u unutrašnjoj petlji. Kao što je prikazano u komentarima, moja petlja štedi vreme (na Pentium-u.)

Impresionirani? Pa, nemojte biti previše impresionirani. U izvesnom smislu sve ovo bi trebalo da bude akademsko. Pravi problem ovde je da mi pristupamo raspoređenim elementima pored niza upakovanih struktura. Ako je niz značajan u veličini, onda na kraju gubimo sve dodatno unete podatke (keš može samo da unese susedne linije podataka.) Cepanje strukture na paralelne nizove podataka, koji imaju lokalitet reference (npr. svi elementi su učitani/upisani u odgovarajućim unutrašnjim petljama) će težiti da učini više za performansu od ovih vrsta optimizacije. Ali čak i u toj situaciji ne mislim da će većina kompajlera koristiti repz scasd.

Ipak, u ovim situacijama u kojima se pridržavate lošeg dizajna niza strukture (kao što je vertex buffer korišćen u microsoft's Direct 3D API) iznad pomenuti kod je primenjiv.

63 bitni LFSR

Jeste tipičan cyclic redundancy check algoritam kalkulacija. To je u suštini deterministički korak iteracija funkcije koja koristi 63-bitni ulaz, skrembluje bitove na neki ravnomerni pseudo-slučajni način, i zatim vraća te 63 bitove. Takvi algoritmi mogu biti korišćeni za šifrovanje visokih performansi (ali niske bezbednosti), pseudo-slučajnih brojeva, za testiranje integriteta podataka ili hash funkcija.

typedef unsigned long UINT;

void TestC(UINT &b0, UINT &b1)
{
UINT L1, L2, L3;
UINT H1, H2;

// x = (x>>31)^(x>>30)^(x<<32) (mod 2^63)

        L1 = (b1<<1)|(b0>>31);
        L2 = (b1<<2)|(b0>>30);
        H1 = (b1>>31);
        H2 = (b1>>30);
        b1 = H1^H2^b0 &0x7FFFFFFF;
        b0 = L1^L2;

}

Ja sam implementirao ovo pomoću 63 od 64 bita u paru od 32 bitnih poziva promenljivih referenci. (Moj kompajler ne podržava 64-bitni tip.)

; compiler

lea     esi,[edx*2]     ; 1 U -
shr     ebx,31          ; 2 U -
or      esi,ebx         ; 3 U -
mov     ebx,eax         ; 4 U -
lea     ecx,[edx*4]     ; 5 U
shr     ebx,30          ; 5   V
or      ebx,ecx         ; 7 U - +agi
mov     ecx,edx         ; 8 U -
shr     ecx,31          ; 9 U -
shr     edx,30          ;10 U -
xor     edx,ecx         ;11 U -
xor     edx,eax         ;12 U -
mov     eax,esi         ;13 U
and     edx,07FFFFFFFh  ;13   V
xor     eax,ebx         ;14 U

; by Paul Hsieh and Pisen Chiang

mov     esi,edx         ; 1 U
xor     cl,cl           ; 1   V
shld    edx,eax,1       ; 5 NP  +4c*
shld    esi,eax,2       ; 9 NP  +4c
adc     cl,0            ;10 U
xor     edx,esi         ;10   V
xchg    eax,edx         ;12 NP  +2c
xor     dl,cl           ;13 U

Ovde ciklusni broj je blizu onom na Pentium MMX (*zapravo pre-MMX CPUs procesori dovode ova dva do nerešenog rezultata s tim da prvi SHLD koristi dodatni sat da bi dekodirao.) Ovo je uglavnom zbog iznenađujuće sporih SHLD instrukcija. Na Pentium Pro/II, K6 and 6x86MX procesorima, SHLD ima značajno poboljšana performanse što ovo čini još ubedljivijem rešenjem baziranom na veličini i brzini.

On je optimizovan samo za rad na Pentium procesorima

; by hand for Pentiums

mov     esi,edx         ; 1 U
xor     cl,cl           ; 1   V
shl     esi,2           ; 2 U
mov     ebx,eax         ; 2   V
adc     cl,0            ; 3 U
lea     edx,[edx*2]     ; 3   V
shr     ebx,30          ; 4 U
xor     edx,esi         ; 4   V
xor     edx,ebx         ; 5 U
xor     al,cl           ; 5   V
shr     ebx,1           ; 6 U -
xchg    eax,edx         ; 8 NP  +2c
xor     eax,ebx         ; 9 U

Brzo i dirty bubble sortiranje

Andrew Howe, iz Core Designs (proizvođači Tomb Raider-a), poslao mi je izuzetno kratko sortiranu petlju. Prevashodno napisana za WATCOM C/C++, ja sam uklonio cruft da bi vi mogli da vidite to ovde u njenom najoptimalnijem obliku.

; by Andrew Howe

outerloop:  lea     ebx,[edi+ecx*4]
            mov     eax,[edi]
cmploop:    sub     ebx,4
            cmp     eax,[ebx]
            jle     notyet
            xchg    eax,[ebx]
notyet:     cmp     ebx,edi
            jnz     cmploop
            stosd
            loop    outerloop

Obratite pažnju na upotrebu xchg, stosd, i petlje, jer je to nešto što nećete videti od C kompajlera. Nisam se trudio da razradim vremenski raspored ove rutine. Imajte na umu da za neke aplikacije, balon sortiranje će nadmašiti neke od sofisticiranijih algoritama za sortiranje. Na primer, 3D aplikacije kojima je potrebno Z-sortiranje, ali koje mogu da se oslone na temporalno lokaliranje da bi uvek održavali uglavnom sortiranu listu. (Za drugo zanimljivo odstupanje duž ove linije vidite Sortiranje sa manje od svih činjenica >>)

Brza implementacija strlen-a ()

Nedavno, neko mi je pisao i poslao komentar da strlen() se obično naziva funkcijom, i kao takav je bio zainteresovan za eventualna poboljšanja performansi za njega. U početku, bez mnogo razmišljanja o tome, nisam video da postoji mogućnost da se značajno poboljša algoritam. Bio sam u pravu, ali dokle god je nizak nivo kontrole algoritama u pitanju, postoje mnogobrojne mogućnosti. U osnovi, algoritam je baziran na bajt skeniranju, i kao tipična stvar koju će C verzija da uradi pogrešno je da propusti priliku da smanji teret redundancije.

; compiler

    mov     edx,ebx
    cmp     byte ptr [ebx],0
    je      l2
l1: mov     ah,[ebx+1]       ; U
    inc     ebx              ;   V
    test    ah,ah            ; U
    jne     l1               ;   V +1brt
l2: sub     ebx,edx

; by Paul Hsieh

    lea     ecx,[ebx-1]
l1: inc     ecx
    test    ecx,3
    jz      l2
    cmp     byte ptr [ecx],0
    jne     l1
    jmp     l6
l2: mov     eax,[ecx]        ; U
    add     ecx,4            ;   V
    test    al,al            ; U
    jz      l5               ;   V
    test    ah,ah            ; U
    jz      l4               ;   V
    test    eax,0ff0000h     ; U
    jz      l3               ;   V
    test    eax,0ff000000h   ; U
    jnz     l2               ;   V +1brt
    inc     ecx
l3: inc     ecx
l4: inc     ecx
l5: sub     ecx,4
l6: sub     ecx,ebx

Ja sam ovde žrtvovao veličinu u korist performanse, tako što sam suštinski odvio petlju 4 puta. Ako su ulazne veze dovoljno duge (tada će performanse biti bitne) na Pentium-u, ASM kod će to izvršiti po stopi od 1,5 klokova po bajtu, dok je C kompajleru potrebno 3 klokova po bajtu. Ako veze nisu dovoljno duge, slabo predviđanje grananja može učiniti ovo rešenje gorim nego ono napred.

Ažuriranje!

Prilikom rasprave o sprite kopiranju podataka (pogledajte sledeći primer) shvatio sam da postoji značajno poboljšanje za 32-bit x86's koji imaju sporo grananje (P-IIs and Athlon.)

; by Paul Hsieh

    lea     ecx,[ebx-1]
l1: inc     ecx
    test    ecx,3
    jnz     l3
l2: mov     edx,[ecx]        ; U
    mov     eax,07F7F7F7Fh   ;   V
    and     eax,edx          ; U
    add     ecx,4            ;   V
    add     eax,07F7F7F7Fh   ; U
    or      eax,edx          ; U
    and     eax,080808080h   ; U
    cmp     eax,080808080h   ; U
    je      l2               ;   V +1brt
    sub     ecx,4
l3: cmp     byte ptr [ecx],0
    jne     l1
    sub     ecx,ebx

Mislim da će ovaj kod raditi bolje u celini za sve 32 bitne x86s zbog manjeg grananja. 16 bitni k 86 očigledno mogu da iskoriste sličnu ideju, ali treba da bude veoma jasno da će biti najmanje duplo sporiji. (Stvarno počinjem da mi se sviđa ovaj trik maskiranja bitova! Videti sledeći primer) Hvala Zi Bin Yang koji je ukazao na grešku u mom kodu.

Ovde je C verzija iste stvari:

int fstrlen(char *s) {
char *p;
int d;

#define M1 (0x7f7f7f7f)
#define M2 (0x80808080)
#define SW (sizeof(int)/sizeof(char))

    p=s-1;
    do {
        p++;
        if( (((int)p)&(SW-1))==0 ) {
            do {
                d = *((int *)p);
                p += SW;
                d = (((d&M1)+M1)|d) &M2;
            } while( d==M2 );
            p -= SW;
        }
    } while( *p!=0 );
    return p-s;
}

Ona sastavlja suštinski istu stvar (na P6 bi trebalo da ima isti učinak) ali ima nekih problema sa njim. Nije previše prenosiv u druge veličine int-a (brojevi 0x7f7f7f7f i0x80808080 trebaju biti skraćeni ili produženi, i bacanje p sa pokazivača na skalar nije garantovano da će raditi) i nije ništa više razumljivije od skupljanja.

Obratite pažnju da iako ravnanje tumačenja nije potrebno na modernim x86's ovde je izvršeno, kao sredstvo da se izbegne neuspeh učitavanja memorije. To se može desiti kao rezultat čitanja na kraju niske, ali pod pretpostavkom da se dodela memorije poravnava barem u DWORD granicama.

Ažuriranje!

Rajan Mek je poslao verziju MMX verziju ovog grananja:

; MMX version by Ryan Mack
; Roughly 13 + 3n + BRANCH clocks on a P-II

const unsigned __int64 STRINGTBL[8] = {0, 0xff,
        0xffff, 0xffffff, 0xffffffff, 0xffffffffff,
        0xffffffffffff, 0xffffffffffffff}

/* ... */

    pxor     mm1, mm1
    mov      ecx, eax
    mov      edx, eax
    and      ecx, -8
    and      eax, 7
    movq     mm0, [ecx]
    por      mm0, [STRINGTBL+eax*8]
MAIN:
    add      ecx, 8
    pcmpeqb  mm0, mm1
    packsswb mm0, mm0
    movd     eax, mm0
    movq     mm0, [ecx]
    test     eax, eax
    jz       MAIN

    bsf      eax, eax
    shr      eax, 2
    lea      ecx, [ecx+eax-8]
    sub      ecx, edx

Individualne petlje iteracija ne zavise jedne od drugih, tako da na modernom pokvarenom procesoru ovo je samo ograničen upitni problem. Na P-II imamo 6 ALU microops + 1 load microop, koji bi trebalo da prebaci na 3 klokova po 8 bajtova protoka. Na AMD procesorima postoje 7 riscops što je 3 klokova na jednom Athlon-u i 4 klokova na K6 po 8 bajtova protoka.

Merenja performansi na Athlon-u pokazuju (ignorisanjem lošeg predviđanja grananja) da za duge veze ovaj 64 bitni metod je do 55% brži od prethodnog 32-bitnog metoda (koji je, opet, 22% brže od WATCOM clib implementacije.) Međutim, za veoma kratke veze, ovaj metod je čak 3 puta sporiji od prethodnog metoda (koji je otprilike iste brzine kao i WATCOM clib implementacija). Ali zapamtite da ako su vaše veze su kraće, the branch mispredicts (koji nisu bili na mojim testovima) iskoristiće znatno više vremena. Međutim, ako nameravate da koristite jednu od ovih alternativa, trebalo bi da procenite njihove performanse da vidite koja je najbolja za vaše aplikacije.

Ažuriranje!

Norbert Juffa mi je pisao da me obavesti o starom triku koji predstavlja značajno poboljšanje u odnosu na uređaje koje sam otkrio:

Nakon nekoliko minuta istraživanja ispalo je da je početno otkrivanje nultog bajta od strane Alan Mycroft-a superiornije u odnosu na formulu na jednom vašem sajtu jer ima kratke lance zavisnosti. Na PIII, strcpy() performanse su skočile skoro 20% nakon zamene jednog sa drugim. Mycroft's macro je

#define has_nullbyte_(x) ((x - 0x01010101) & ~x & 0x80808080)

prikazao ovo kao:

mov edx, eax
not eax
sub edx, 0x01010101
and eax, 0x80808080
and eax, edx
; cycle 1

; cycle 2

; cycle 3

Uostalom, jedna od originalnih poruka Mycroft-a o ovom macro se može naći na Deja. Poruka datira iz 27-04-1987!

Uradio sam malu pretragu i zaista možete naći staru nit diskusije o ovome na google grupama. Evo implementacije u C:

#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)
#define SW (sizeof (int) / sizeof (char))

int xstrlen (const char *s) {
const char *p;
int d;

    p = s - 1;
    do {
        p++;
        if ((((int) p) & (SW - 1)) == 0) {
            do {
                d  = *((int *) p);
                p += SW;
            } while (!hasNulByte (d));
            p -= SW;
        }
    } while (*p != 0);
    return p - s;
}

Upoređeno sa drugim rešenjima na Athlon-u, ovo je zaista najbrže rešenje za veze do 32 karaktera (MMX rešenje je brže za duže veze). Ova funkcija uveliko nadmašuje strlen većine biblioteka.

Sprite kopiranje podataka

Često pitanje koje se postavlja programerima koji su zainteresovani za renderovanje sprite grafike (npr. programeri video igara) je kako da naprave sprite blitter visokih performansi. U nedavnom razgovoru na rec.games.programmer, ispitivač je imao uslov da niz piksela iz jednog niza bude kopiran u odredišni niz osim ako je vrednost piksela nula (predstavlja transparenciju). Kod za pokretanje izgleda otprilike ovako:

char * scrptr;
char * destptr;

/* ... */

/* copy scanline except where transparent. */

for(x=x0;x<xl;x++) {
if( srcptr[x]!=0 ) destptr[x]=srcptr[x];
}

Naravno, ovaj kod ima nekoliko problema: (1) Sadrži predviđanje grananja unutrašnje petlje koji će verovatno da propada vrlo često i (2) Memorija se učitava jedan po jedan bajt i pri tom troši memorijski propusni opseg i previše povećava petlju.

S tim rečeno, ovo rešenje je zapravo dobro ako memorijska jedinica ima "write combine" i "write mask" mogućnosti i ako memorija upisuje pristup do odredišta koje je više prepreka nego predviđanje grananja, preveliko povećanje petlje ili izvor učitavanja. (Ovo je tačno ukoliko je odredište VRAM, ili je procesor veoma klokovani P-II).

Međutim, ukoliko učitavanje destinacije nije problem (ako je odredište sistemski memorijski buffer), onda učitavanje 4 bajta odjednom i izgradnja maske nije loše rešenje, pod uslovom da možete izgraditi jedan bez korišćenja uslovnih grananja (inače ne bi ste ništa dobili). Russ Williams je smislio direktno orijentisan pristup koristeći carry flag (koji je optimizovan za Pentium):

; by Russ Williams

pushad
mov esi,[pbSrc]
mov ecx,[w]
shr ecx,2
mov edi,[pbDest]
sub edi,esi

looptop:
xor ebx,ebx
mov eax,[esi]
add esi,4
mov edx,eax
ror edx,16
add al,255              ; cf =  1 if al!=0 or 0 if al==0
sbb bl,0                ; bl = -1 if al!=0 or 0 if al==0
add ah,255
sbb bh,0
mov eax,edx
shl ebx,16
add al,255
sbb bl,0
add ah,255
sbb bh,0
mov eax,[edi]
ror edx,16
and eax,ebx             ; dest &bg.mask (P6: PRS)
or  eax,edx             ; merge with src
dec ecx
mov [edi+esi],eax
jnz looptop

popad

Petlja iznad funkcioniše odlično za Pentium-e i nije dostupna za C kompajlere zbog upotrebe carry flag-a. Međutim P-II ne voli delimičan registarski pristup (a non-overlappable 7 clock penalty). Posle kraće diskusije motivisane komentarom Christer Ericson-a, sledeći trik je primenjen:

(((D &0x7F7F7F7F) + 0x7F7F7F7F) | D) &0x80808080

Izraz iznad će generisati bitmasku pri visokim bitovima svakog bajta, 00h ukazuje na nulti bajt, i 80h ukazuje na bez-nulti bajt. Sa direktnim trikovima možete da okrenete ovo u 00h za nulti i FFH za bez-nulti, dajući nam željenu masku. Ovde je kod u asemblerskom jeziku:

; by Paul Hsieh

sub esi,edi
looptop:
mov eax,[esi+edi]       ; read sprite source bits
mov ebx,7f7f7f7fh
and ebx,eax
add ebx,7f7f7f7fh
or  ebx,eax             ; 80808080 bits have non-zero status of bytes.
and ebx,80808080h
shr ebx,7               ; move to 01010101 bits.
add ebx,7f7f7f7fh       ; 80==on or 7f==off values in each byte.
and ebx,7f7f7f7fh       ; 00==on or 7f==off masks.
lea eax,[ebx+ebx]       ; eax has 00==on or fe==off masks. (P5: AGI stall)
or  eax,ebx             ; eax has 00==on or ff==off masks.
mov ebx,eax
not ebx                 ; ebx has 00==off or ff==on masks.
and eax,[edi]           ; background bits
or  eax,[esi+edi]       ; merge with sprite bits for final result
mov [edi],eax           ; draw!
add edi,4
dec ecx
jnz looptop

Naravno navedena petlja nije posebno pogodna za Pentium-e jer praktično cela petlja je zavisna od podataka, a tu je AGI stall. Ovi problemi mogu biti rešeni odmotavanjem petlje jednom i korišćenjem običnih dodataka umesto Lea (EDKS i EBP registri su vam na raspolaganju za ovo).

Ipak, P-II će pokušati da "prirodno" odmota ovu petlju, i neće patiti od AGI stall-ova i stoga će daleko manje da ima koristi od ručnog planiranja ove petlje (mada verovatno neće smetati). Međutim, pošto je petlja je 22 mikro-OPS (što je za 2 više od P-II preuređivačkog bafer limita) ne može u potpunosti da bude odmotana.

K6 takođe mogu delimično da "odmotaju" ovu petlju jer sadrži više od 6 dekodirajućih klokova.

Zapravo, sa pravim izvorom, C kompajleri bi trebalo da imaju malo poteškoća u dodiru sa izvorom iznad (ili sa nečim veoma sličnim), Ali nisam siguran kako da ubedite svoj C kompajler da treba da se odmota jednom.

Ažuriranje:Nakon nekog razmišljanja, očigledno je da algoritam iznad može i treba da se vrši pomoću MMX i neki novih SSE instrukcija (movntq posebno). Možda ovo i implementiram kasnije.

Druga ideja, koja dolazi od Terje Mathisen, je da koristite P-II kombinovanih upisnih funkcija u vezi sa minimiziranjem kazni za loše predviđanje grananja. Ideja je da koristite masku da bira između dve odredišne adrese za upisne bajtove:

; Idea from Terje Mathisen, implemented by Sean T. Barrett

sub  esi,edi
mov  edx,temp
sub  edx,edi            ; edx = (temp-edi)
...
loop:
mov  al,[esi+edi]       ; al=src
cmp  al,1               ; cf  =  1 if src==0,         0 if src!=0
sbb  ebx,ebx            ; ebx = -1 if src==0,         0 if src!=0
and  ebx,edx            ; ebx = (temp-edi) if src==0, 0 if src! =0
mov  [ebx+edi],al       ; store to dest (edi) or garbage (temp)
inc  edi
dec  ecx
jnz  loop               ; well predicted branch

Naravno, temp je reiskorišćena sistemska matrica namenjena samo kao kanta za transparentnosti upisa. Spoljašnja petlja postaje komplikovana, ali u idealnim situacijama, to će omogućiti bolje iskorišćenje P-II čipset funkcija bez posledica od kazni za loše predviđanje grananja. Carry flag trik još uvek izmiče modernim C kompajlerima. (Naravno, ova petlja bi trebalo da se malo odmota da bi poboljšali performanse).

Ipak, kao i problem gore navedenog skeniranja ključa svi ove može biti akademsko. Za većinu sprajtova koji su renderovani jednom korišćeni iznova i iznova, transparencije i čvrsti izvorni pikseli obično traju dugo. Dakle korišćenjem alternativnog dekodiranja koji daje transparenciju nasuprot ne-transparenciji pokretanja će biti mnogo efikasnija. Blitting transparencija bi došla do toga da dodaje konstante pokazivačima, i blitting čvrstih boja bi bio trenutan bez vršenja ispitivanja izvora.

Ažuriranje: Paolo Bonzini je upisao sa mnogo efikasnijom unutrašnjom petljom Ideja je da se primeni maska na xor razlici izvora i destinacije.

; by Paolo Bonzini

mov eax, [esi+edi] ; read sprite source
mov ebx, [edi]      ; source
mov ecx, eax
and ecx, 7f7f7f7fh
add ecx, 7f7f7f7fh ; set bit 7 set if bits 6-0 nonzero
or  ecx, eax       ; set bit 7 if byte nonzero
and ecx, 80808080h ; 80 == on or 00 == off
xor eax, ebx       ; eax = dest ^ source
shr ecx, 7         ; 01010101 bits set if byte nonzero
add ecx, 7f7f7f7fh ; 80 == on or 7f == off
xor ecx, 7f7f7f7fh ; ff == on or 00 == off
and eax, ecx       ; d^s== on or 00 == off
xor ebx, eax       ; set to source if on
mov [edi], ebx     ; set to source if on

Paolo je takođe poslao jednu banalnu MMX petlju

movq    mm1, [esi+edi]
pxor    mm0, mm0
movq    mm2, [edi]
pcmpeqb mm0, mm1       ; mm0 = 0 if on, ff if off
pand    mm2, mm0       ; mm2 = 0 if on, d if off
por     mm2, mm1       ; mm2 = s if on, d if off
movq    [edi], mm2

Sada je vreme za MMX

Na sandpile DS je pitao kako da uradimo sledeće:

64-bitni MMX reg ima korisne vrednosti samo na byte7 and byte3 (AXXXBXXX, gde A/B-korisno, X-beskorisno). Želim da kopiram byte7 u byte6, byte5, byte4; i da kopiram copy byte3 u byte2, byte1, byte0.

Smislio sam dva načina:

psrld     mm0, 24                     ; 0 0 0 A 0 0 0 B
packssdw mm0, mm0                    ; 0 A 0 B 0 A 0 B
punpckhwd mm0, mm0                    ; 0 A 0 A 0 B 0 B
pmullw    mm0, Const_0101010101010101 ; A A A A B B B B

ili

psrld     mm0, 24  ; 0 0 0 A 0 0 0 B
packssdw  mm0, mm0 ; 0 A 0 B 0 A 0 B
packuswb  mm0, mm0 ; A B A B A B A B
punpcklbw mm0, mm0 ; A A B B A A B B
punpcklbw mm0, mm0 ; A A A A B B B B

Prvo ima manje instrukcija, ali veću latenciju što je idealno za procesore kao što je Athlon. Drugi ima više instrukcija ali kraću latenciju, što je korisno za procesore kao što su K6, Cyrix or P55C. Nisam siguran koja je petlja bolja za P6 arhitekture.

Naravno kada uđemo u oblast MMX-a, siromašni C kompajler nema ništa da ponudi.

.Generalizovana promena

Norbert Juffa je proučavao Compaq Visual Fortran kompajler i mislio je da bi generalized shift mogla da bude poboljšana. U Fortran jeziku generalized shift je uvek levi shift, ali može da uzme negativnu promenu vrednosti (što je desni shift) i shift vrednosti izvan veličine reči (u bilo kom smeru) u bitovima iznosi 0. Ovde je algoritam koji sam smislio:

unsigned long gensh(unsigned long v, int x) {
int a, b;
    a = (v << x) & -(((unsigned int)x) < 32);
    x = -x;
    b = (v >> x) & -(((unsigned int)x) < 32);
    return a| b;
}

ANSI C standard, zahteva da koristimo unsigned int kada koristimo desni shift zbog neodređenog "definisane implementacije" statusa ili korišćenjem desnog shifta na dodeljenim brojevima. Ako se pitate zašto ovo pominjem - to je zato što ovo nije dovoljno poznato, i može da dovede do pogrešnih rezultata. Ovaj put sam uključio i microsoft Visual C++:

; by Paul Hsieh

mov ebx, eax ; 1
shl eax, cl  ; 1
cmp ecx, 32  ; 1
sbb edx, edx ; 2 dep: CF
neg ecx      ; 2 issue
and eax, edx ; 3 dep: edx
cmp ecx, 32  ; 3 dep: ecx
sbb edx, edx ; 4 dep: CF
shr ebx, cl  ; 3 dep: ecx
and ebx, edx ; 5 dep: edx
or  eax, ebx ; 6 dep:

; Microsoft Visual C++

cmp ecx, 32  ; 1
mov esi, eax ; 1
sbb edx, edx ; 2 dep: CF
shl esi, cl  ; 2 dep: esi
neg edx      ; 3 dep: edx ??
neg edx      ; 4 dep: edx ??
neg ecx      ; 1
and edx, esi ; 5 dep: edx
cmp ecx, 32  ; 2 dep: ecx
sbb esi, esi ; 3 dep: CF
sar eax, cl  ; 3 issue (ANSI)
neg esi      ; 4 dep: esi ??
neg esi      ; 5 dep: esi ??
and eax, esi ; 6 dep: esi
or  eax, edx ; 7 dep:

; WATCOM C/C++

cmp  edx, 32  ; 1
setb cl       ; 2 dep: CF
mov  ebx, ecx ; 4 dep: ecx, size
mov  esi, eax ; 1
and  ebx, 255 ; 5 dep: ebx
mov  cl, dl   ; 1 rename cl
neg  ebx      ; 6 dep: ebx
shl  esi, cl  ; 2 dep: esi,cl
neg  edx      ; 2 issue
mov  ecx, esi ; 3 dep: esi
and  ebx, esi ; 7 dep: ebx
cmp  edx, 32  ; 3 dep: edx
setb dh       ; 4 dep: CF
xor  ecx, esi ; 4 dep: ecx ??
mov  cl, dh   ; 5 dep: dh
mov  esi, ecx ; 7 dep: ecx, size
mov  cl, dl   ; 3 dep: edx
neg  esi      ; 8 dep: esi
sar  eax, cl  ; 5 issue (ANSI)
and  eax, esi ; 9 dep: esi
or   eax, ebx ; 10 dep:

Zapažanja ukazuju na klok na kojem bi idealna 3-way out-of-order x86 mašina (na primer, Athlon) mogao da izvršava ova uputstva. Obratite pažnju da pitanje stoji za svaku od ovih kodovnih sekvenci. To znači da bi mogao da postoji slučaj kada bi x86 procesori išli sa 4-smernim instrukcijama dekodiranja i pitanja u budućnosti. U svakom slučaju, MSVC++ izgleda da se snalazi prilično dobro u pogledu konačnog učinka, ali nije u mogućnosti da se pojednostavi back to back neg reg0 instrukcije. Standardna softversko registraciono preimenovana tehnika za izbegavanje zavisnosti stall-a (posle mov esi, eax ulogu dva registra može i treba da se zameni - dva registra će biti identična posle ove instrukcije osim što je jedan od njih dostupan jedan klok kasnije) se takođe nekoristi. WATCOM C/C++ ima problema sa registrom pogrešne veličine, i nijje svestan standardnog sbb reb, reg trika.

64-bitni BCD dodatak

Norbert Juffa mi je dao đavolski pametan kod za upotrebu 64 bit BCD dodatka.

  ; by Norbert Juffa

  mov   eax, dword ptr [x]   ; x (lo)
  mov   ebx, dword ptr [y]   ; y (lo)
  mov   edx, dword ptr [x+4] ; x (hi)
  mov   ecx, dword ptr [y+4] ; y (hi)

  ; here: EDX:EAX = augend, ECX:EBX = addend

  mov   esi, eax             ; x
  lea   edi, [eax+66666666h] ; x + 0x66666666
  xor   esi, ebx             ; x ^ y
  add   eax, ebx             ; x + y
  shr   esi, 1               ; t1 = (x ^ y) >> 1
  add   edi, ebx             ; x + y + 0x66666666
  sbb   ebx, ebx             ; capture carry
  rcr   edi, 1               ; t2 = (x + y + 0x66666666) >> 1
  xor   esi, edi             ; t1 ^ t2
  and   esi, 88888888h       ; t3 = (t1 ^ t2) & 0x88888888
  add   eax, esi             ; x + y + t3
  shr   esi, 2               ; t3 >> 2
  sub   eax, esi             ; x + y + t3 - (t3 >> 2)

  sub   edx, ebx             ; propagate carry
  mov   esi, edx             ; x
  lea   edi, [edx+66666666h] ; x + 0x66666666
  xor   esi, ecx             ; x ^ y
  add   edx, ecx             ; x + y
  shr   esi, 1               ; t1 = (x ^ y) >> 1
  add   edi, ecx             ; x + y + 0x66666666
;;sbb   esi, esi             ; capture carry
  rcr   edi, 1               ; t2 = (x + y + 0x66666666) >> 1
  xor   esi, edi             ; t1 ^ t2
  and   esi, 88888888h       ; t3 = (t1 ^ t2) & 0x88888888
  add   edx, esi             ; x + y + t3
  shr   esi, 2               ; t3 >> 2
  sub   edx, esi             ; x + y + t3 - (t3 >> 2)

  ; here EDX:EAX = sum

  mov   edi, z
  mov   [edi], eax
  mov   [edi+4], edx

Upotreba carries and rcr instrukcija nasuprot njihovim C ekvivalentima (otprilike) pokazuje da su ogromna pojednostavljenja moguća u asemblaciji koja nije ponuđena u C.

Možete naći više informacija na BCD aritmetici ovde na sajtu Douglas W. Jones-a

Piksel "bashing"

“Gordi" je radio na softverski zasnovanoj grafičkoj biblioteci i zatražio preko USENET-a optimizovane putanje za više zajedničkih pixel bashing rutina. Ovde su neka od rešenja koje sam ja predstavio.

Prva je MMX rutina za kompresovanje 4 bita po pikselu do 1 bita po pikselu po određenom redu. Prevod piksela jednostavno uzima donji bit od svakog zalogaja. Redosled originalnih zalogaja za datu qword je: 21436587 (ne pitajte me - to je Gordy-jeva biblioteka). Pretpostavljamo da su zalogaji bitova zamaskirani (na primer, drugi bitovi su 0).

MagicConst dd 48124812h,48124812h
;....
    movq     mm7, MagicConst
    pcmpeqb  mm6, mm6        ; 1111111111111111
    psllw    mm6, 12         ; 1111000000000000
@quads:
    movq     mm0, [esi]      ; 0006000500080007
    movq     mm1, mm6        ; XXXX000000000000
    pmullw   mm0, mm7        ; 8765705800870070
    pand     mm1, mm0        ; 8765000000000000
    psrld    mm0, 28         ; 0000000000004321
    psrlw    mm1, 8          ; 0000000087650000
    por      mm0, mm1        ; 0000000087654321
    packuswb mm0, mm0        ; [?B?A?B?A]
    packuswb mm0, mm0        ; [BABABABA]
    movd     eax, mm0
    mov      [edi],ax
    add      esi, 8
    add      edi, 2
    dec      ecx
    jnz      @quads

Pošto su bitovi izolovani, niz promena i ors-a mogu biti zamenjeni sekvencom promena i dodataka. Ali sekvenca promena i dodataka može da se pretvori u jednu možinu. Sa tačke gledišta performanse ovo je dobar kompromis pošto je pmullw potpuno kanalisana instrukcija i u modernom x86, mnoge unutrašnje instance ove petlje bi trebalo da budu u stanju da se izvršavaju paralelno. Ovo rešenje koristi 64 bajtovni izvor u samo nekoliko klokova - obrasci zasnovani na C verovatno ne bi ni bili blizu.

Drugi je bio za prosečne tokove bajtova zajedno (i zaokruživanje naniže). Gordi je tražio rešenje za pre-K6-2 MMX/3DNow! (koji nije imao pavgusb ili pavb instrukcije) kao i pravo rešenje. Ovde su rešenja koja sam ja predložio: Ova rešenja koriste sledeća posmatranja:

; Integer Solution by Paul Hsieh

LTop:
mov     eax, [esi]
mov     ebx, [edx]
mov     ebp, eax
and     eax, ebx
xor     ebx, ebp
shr     ebx, 1
and     ebx, 7F7F7F7Fh
add     eax, ebx
mov     [edi], eax
dec     ecx
jnz     LTop

; MMX Solution by Paul Hsieh

LTop:
movq    mm0, [esi]
movq    mm1, [edx]
movq    mm2, mm0
pand    mm0, mm1
pxor    mm1, mm2
psrlb   mm1, 1
paddb   mm0, mm1
movq    [edi], mm0
dec     ecx
jnz     LTop

Ova resenja upotrebite za pracenje :

A + B = (A and B) * 2 + (A xor B)

And therefore:

(A + B)/2 = (A and B) + (A xor B)/2

Dok originalni (A + B) dodatak se može prepuniti, dodatak (A i B) + (A xor B)/2 ne može.

Treća rutina je bila potrebna za izvođenje saturacionog dodatka. Koristeći MMX koji je samo trivijalna aplikacija paddusb instrukcije. (kako je "Gordi" naglasio), ali šta je celom rezervnom rutinom? Smislio sam sledeću celu rutinu:

; Integer solution by Paul Hsieh

mov eax, [esi]      ; src0
mov ebx, [edi]      ; src1
mov ecx, eax
mov edx, ebx
and ecx, ebx        ; first bit carry
xor edx, eax        ; first bit add (mod 2)
and eax, 0xFEFEFEFE
and ebx, 0xFEFEFEFE
add eax, ebx        ; Add top 7 bits (A&0xFE)+(B&0xFE)
sar eax, 1          ; >>= 1 to capture carry bits
and ecx, 0x01010101 ; Is there a carry to the second bit?
add eax, ecx        ; (...)>>1
mov ecx, eax
and edx, 0x01010101 ; first bit
and eax, 0x7F7F7F7F
shr ecx, 7
shl eax, 1          ; (...)&0xFE
and ecx, 0x01010101 ; overflows
or  eax, edx        ; ((...)&0xFE) + (((A&0x01)+(B&0x01))&1)
xor ecx, 0x81818181 ; blockers
sub ecx, 0x01010101 ; 0->80, 1->7F
and ecx, 0x7F7F7F7F ; 0->00, 1->7F
or  eax, ecx
shl ecx, 1
or  eax, ecx

Ovaj put odvajamo donje bite da bi smo bili sigurni da možemo izvršiti paralelne dodatke sa samo 8 bita radnog opsega u jednom trenutku.

A = (A&0xFE) + (A&0x01)
B = (B&0xFE) + (B&0x01)

A + B	= ((A&0xFE)+(B&0xFE)) + ((A&0x01)+(B&0x01))
	*= ((A&0xFE)+(B&0xFE)) + ((A&B&0x01)2 + ((A xor B)&0x01))**

Prenošenje u 9 bit je prevedeno u 0x00 ili 0x7F masku. Od or-ing u maski u destinaciju zatim pomeren u levo za jedan, to postiže isti efekat kao da maska sadrži 0x00 ili 0xFF vrednosti.

Ovog puta, pošto je carry flag zarobljen i korišćen u prvom dodatku, C kompajler ne može duplirati ovu rutinu.

Ažuriranje: Oliver Weichhold je istaknuo zanimljivo pitanje u comp.lang.asm.x86: duplicate this routine.

Update: Oliver Weichhold posted an interesting question in comp.lang.asm.x86:

Moram da konvertujem vrednost boja (u stvari tekel preuzet iz A4R4G4B4 teksture) u A15R15G15B15 vrednost boje održane u MMX registrima.

Iako neko može instiktivno da traži pametnije načine vršenja brojnih promena i maskiranja koje mogu izgledati da su potrebne, to zaista nije potrebno. Uzmite u obzir da što stvarno želite jeste mapiranje 16 ulaznih bitova koje želite da postavite u neke izlazne pozicije, gde svaki ulazni bit je nezavisan od drugih.

To samo vrišti "Potražite tabele" i stvarno to vodi do nekih jednostavnih kodova:

movzx     eax, word ptr input_A4R4G4B4
movzx     ebx, al
shr       eax, 8
movd      mm0, dword ptr Table_G4B4_to_G15B15 [ebx*4]
movd      mm1, dword ptr Table_A4R4_to_A15R15 [eax*4]
punpckldq mm0, mm1

Tabele se mogu konfigurisati sa jednostavnim C kodom u vreme inicijalizacije.

Konvertovanje Velikih slova

Konvencionalna mudrost kaže da bi brzo konvertovali ASCII vezu u velika slova, treba da koristite tabelu za konverziju svakog slova. Problem je što adresa režima x86 procesora zahteva 32 (ili 16) bitne registre, pa neka vrsta bajt -> DVORD (ili reč) konverzija se dešava. To dovodi do delimične konverzije registra koja je kažnjena na AMD procesorima i razorna je po Intel procesore.

Dakle šta je naša alternativa? Pa, ako možemo da amortizujemo naše performanse pomoću SIMD-a, onda šta mi u stvari pokušavamo da uradimo jeste da prevedemo interval [61h, 7Ah] u [41h,5AH]. Pristup koji sam smislio je bio da iskoristim činjenicu da je ASCII definisan dobro samo u intervalu [00h, 7Fh] okretanjem intervala i maskiranja, zatim rotiranjem i hvatanjem srednjeg intervala u 5-om bitu i oduzimajući to od 4 ulaznih bajtova:

; Integer SIMD uppercase(string) by Paul Hsieh

mov  eax, src[esi]
mov  ebx, 7f7f7f7fh
mov  edx, 7f7f7f7fh
and  ebx, eax        ; 61-7a | 00-60,7b-7f
add  ebx, 05050505h  ; 66-7f | 05-65,80-84
and  ebx, edx        ; 66-7f | 00-65
add  ebx, 1a1a1a1ah  ; 80-99 | 1a-7f
shr  ebx, 2
and  ebx, 20202020h  ;    20 | 00
sub  eax, ebx        ; 41-5a | 00-60,7b-7f

Ova rutina se nalazi u opsegu svih modernih C kompajlera. (Ostanite nakačeni na C verziju). Letimičan pogled, međutim, pokazuje da se ova rutina lako konvertuje u MMX.

Ažuriranje: Potreba da bude u stanju da podrži ne-ASCII (npr. uključuje interval [80h, FFh]) mi je pala na pamet. Jedan od bonusa koji se dobija kada je u stanju da uradi kompletan interval je da UTF-8 encoded unicode može da se direktno prevede na ovaj način. U svakom slučaju, to je samo mala promena, koja nažalost košta ciklus na kritičnom putu.

; Integer SIMD uppercase(string) on UTF-8 data by Paul Hsieh

mov  eax, src[esi]
mov  ebx, 0x7f7f7f7f
mov  edx, 0x7f7f7f7f
and  ebx, eax          ; 61-7a | 00-60,7b-7f
mov  ecx, eax
add  ebx, 0x05050505   ; 66-7f | 05-65,80-84
not  ecx               ; flip top bits
and  ebx, edx          ; 66-7f | 00-65
add  ebx, 0x1a1a1a1a   ; 80-99 | 1a-7f
and  ebx, ecx          ; turn off top bit for non-ASCII
shr  ebx, 2
and  ebx, 0x20202020   ; 20 | 00
sub  eax, ebx

Ažuriranje: Norbert Juffa mi je pisao da me obavesti da kao deo Sun otvaranja iz Solaris izvornog koda su upotrebili neke od njegovih izvora koršćenih za neke C string funkcije, uključujući poređenja i tolower-a dostupnih javnosti. Možete da vidite izvor ovde.

Ažuriranje: Ja sam dizajnirao alternativnu funkciju koja se bavi sa celim UTF-8 opsegom, ali je takođe više paralelan i samim tim treba da se izvrši nešto brže:

; Integer SIMD uppercase(string) on UTF-8 data v2 by Paul Hsieh

mov  eax, src[esi]
mov  ebx, 0x80808080
mov  edx, eax          ; src
or   ebx, eax          ; (0x80808080 | src)
mov  ecx, ebx
sub  ebx, 0x7b7b7b7b   ; (0x80808080 | src) - 0x7b7b7b7b
sub  ecx, 0x61616161   ; c = (0x80808080 | src) - 0x61616161
not  ebx               ; d = ~((0x80808080 | src) - 0x7b7b7b7b)
not  edx               ; ~src
and  ebx, ecx          ; c & d
and  edx, 0x80808080   ; ~src & 0x80808080
and  ebx, edx          ; e = (c & d) & (~src & 0x80808080)
shr  ebx, 2            ; e >> 2
sub  eax, ebx          ; src - (e >> 2);

C kod je sasvim uporediv:

; Integer SIMD uppercase(string) on UTF-8 data v2 by Paul Hsieh

uint32_t upperCaseSIMD (uint32_t x) {
uint32_t b = 0x80808080ul | x;
uint32_t c = b - 0x61616161ul;
uint32_t d = ~(b - 0x7b7b7b7bul);
uint32_t e = (c & d) & (~x & 0x80808080ul);
return x - (e >> 2);
}

Premeštanje bitova

Norbert Juffa nastavlja da proučava Compaq Visual Fortran kompajler (uskoro će postati Intel Fortran kompajler) ovaj put gledajući na MVBITS komandu. Opis funkcije može se naći Ovde .

MVBITS (FROM, FROMPOS, LEN, TO, TOPOS)
Opis: Kopira sekvencu bitova (bit polje) sa jedne lokacije na drugu.
Klasa: Elementarna podrutina
Argumenti: Postoje pet argumenata:

FROM	Može biti bilo koji celoviti tip; Predstavlja lokaciju sa koje je bit polja premešteno.
FROMPOS	Može biti bilo koji celoviti tip; Ne sme da bude negativan. On identifikuje prvu poziciju bita u polju prebačenom iz FROM. FROMPOS + LEN mora biti manji ili jednak BIT_SIZE (FROM.
LEN	Može biti bilo koji celoviti tip; Ne sme da bude negativan. Ovo identifikuje dužinu polje premeštenog iz FROM.
TO	Može biti bilo koji celoviti tip, ali mora da ima iste vrste parametara kao FROM. Predstavlja lokaciju gde je bit polje prenešeno. TO je postavljeno kopiranjem niza bitova dužine LEN, sa početkom u poziciji FROMPOS of FROM do pozicije TOPOS of TO. Nijedan drugi bit iz TO nije izmenjen. Po njegovom povratku, LEN bitovi iz TO (koji počinju u TOPOS) su jednaki vrednosti koju LEN bitovi iz FROM (startuju iz FROMPOS) imaju na ulazu.
TOPOS	Može biti bilo koji celoviti tip; ne sme biti negativan. On identifikuje startnu poziciju (u okviru TO) za bitove koji se prenose. TOPOS + LEN mora biti manji ili jednak BIT_SIZE (TO).

; Solution by Norbert Juffa

mov ecx, [LEN]    ; len
mov eax, [FROM]   ; from
cmp ecx, 32       ; (len < 32)="" cy="" :="">
sbb edx, edx      ; (len < 32)="" ~0="" :="">
shl edx, cl       ; (len < 32)="" ((~0)="" <<="" len)="" :="">
mov ecx, [FROMPOS]; frompos
not edx           ; mask = (len < 32)="" ~((~0)="" <<="" len)="" :="">
shr eax, cl       ; from >> frompos
mov ecx, [TOPOS]  ; topos
and eax, edx      ; (from >> frompos) & mask
shl edx, cl       ; mask << topos
shl eax, cl       ; bits << topos
not edx           ; ~(mask << topos)
and edx, [TO]     ; to & ~(mask << topos)
or eax, edx      ; to=(to&~(mask<<topos)|((from>>frompos)&mask)

Slajdovanje registara, promena registara

Norbert Juffa, koji je gledao neki 64-bitni kod za promene (za 32bitne x86 registre) smanjio je problem pronalaženjem dobrog rešenja:

if (ECX == 0) {
    EAX = EDX
    EDX = 0
} else { /* ECX == 0xFFFFFFFF */
    EAX = EAX
    EDX = EDX
}

pod pretpostavkom da ecx je 0 ili FFFFFFFF. Nakon što smo oboje petljali oko toga i išli u pogrešnom pravcu, Norbert je dobio odličnu ideju:

; Solution by Norbert Juffa

sub eax, edx    ; a - d
and eax, ecx    ; c ? a - d : 0
add eax, edx    ; c ? a : d
and edx, ecx    ; c ? d : 0

Norbert je umesto toga potržio prosto rešenje zasnovano na grananju, kombinovano sa cmovcc rešenjem za novije procesore koji imaju ovu instrukciju:

; Solution by Norbert Juffa

__declspec (naked) __int64 __stdcall
MYLSHIFT64 (const __int64 *i, const int *sh)
{
  __asm {
     mov     ecx, [esp+8] ; &sh
     mov     eax, [esp+4] ; &i
     mov     ecx, [ecx]   ; sh
     mov     edx, [eax+4] ; i_hi
     mov     eax, [eax]   ; i_lo

     shld    edx, eax, cl ; sll (i,sh & 0x1f)
     shl     eax, cl      ;
#if (CPU == i386)
     test    ecx, 32      ; sh >= 32 ?
     jz      $lshift_done ; nope, done
     mov     edx, eax     ; sll (i,32)
     xor     eax, eax     ;
   $lshift_done:
     cmp     ecx, 64      ; (sh>=64)||(sh<>
     sbb     ecx, ecx     ; (sh>=64)||(sh<0) 0="" :="">
     and     eax, ecx     ; (sh>=64)||(sh<0) 0="" :="" sll="">
     and     edx, ecx     ;
#else /* Athlon, P6+ */
     test    ecx, -64     ; (sh>=64)||(sh<0) nz="" :="">
     ror     ecx, 6       ; (64>sh>=32) ? CY : NC(ZF safe)
     mov     ecx, 0       ; 0
     cmovc   edx, eax     ; i=(64>sh>=32) ? sll(i,32) : i
     cmovc   eax, ecx     ;
     cmovnz  edx, ecx     ; (sh>=64)||(sh<0) 0="" :="" sll="">
     cmovnz  eax, ecx     ;
#endif
     ret     8            ; pop two DWORD parms and ret
  }
}

SHLD, cmovcc, i ror nije verovatno da će se pojaviti u izlazu bilo kog poznatog kompajlera.

Pitanje 64 bitno celih brojeva

Phil Carmody (poznati haker za pretragu primarnih brojeva) poslao je na alt.lang.asm sledeće pitanje:

Imam 2 64-bitna (nikad iznad 2^40, za napomenu) celih brojeva u C, radim sledeće:

/* multiply tpow (in 1..p-1) by 2, modulo p */
tpow <<= 1;
if (tpow > p) { tpow -= p; }

Kompajler sada okreće promenu u SHL i SHLD, sa kojim nemam problem. Međutim, if izjava je renderovana korišćenjem cmps i jumps, koja, pošto je vrednost veoma nepredvidiva, me izaziva da uzmem malo od performanse.

Šta će predložena 64-bitna bez granata bit vrteška da uradi gore? Znam da je 32-bitni ekvivalent neka fanki kombinacija subs, sbbs, ands, drugih i stvari, ali da li se konvertujei u 64 -bita? Da li postoji uopšte verzija cmovcc?

Dao sam sledeći odgovor:

Pa, to izgleda kao da želiš nešto ovako:

tpow <<= 1;
tpow -= p & -(tpow > p);

Dakle, kako da uradimo to - (tpow > p) u potpuno predikatnom načinu? Da vidimo ovo je isto kao -(p - tpow < 0),="" tako="" da="" želimo="" da="" izvršimo="" 64="" bita="" oduzimanje="" od="" tpow="" od="" p="" i="" da="" uhvatimo="" carry,="" i="" onda="" ga="" iskoristimo="" kao="" masku="" i="" protiv="" p="" i="" zatim="" oduzmemo="" od="" tpow.="">

mov esi, tpow[0]
mov edi, tpow[4]
add esi, esi
adc edi, edi ; tpow << 1; -- Don't use SHLD.

mov eax, p[0]
mov edx, p[4]
sub eax, esi
sbb edx, edi ; p - tpow
sbb ebx, ebx ; -(p - tpow <>

mov eax, negp[0]
mov edx, negp[4]
and eax, ebx
and edx, ebx ; p & -(p - tpow < 0)

sub esi, eax
sbb edi, edx ; tpow - (p & -(p - tpow < 0))

mov tpow[0], esi
mov tpow[4], edi ; tpow -= p & -(p - tpow < 0)="">

Voila! U redu, mislim da bi cmovCC trebalo da bude još lakši.Vaš kod je ekvivalentan:

tpow <<= 1;
tpow = (tpow - p >= 0) ? tpow - p : tpow;

Tako da ćemo samo izračunati samo tpow - p, uhvatiti CF zastave, zatim uslovno zameniti tpow:

mov esi, tpow[0]
mov edi, tpow[4]
add esi, esi
adc edi, edi ; tpow << 1; -- Don't use SHLD.

mov eax, esi
mov edx, edi ; Annoying dependency.

sub eax, p[0]
sbb edx, p[4] ; tpow - p

cmovnb esi, eax
cmovnb edi, edx ; (tpow - p >= 0) ? tpow - p : tpow

mov tpow[0], esi
mov tpow[4], edi ; tpow = (tpow - p >= 0) ? tpow - p : tpow

63 bitni atomski brojač

Na comp.lang.asm, Matt Taylor je poslao da je u potrazi za "lockless 63-bit counter" koristeći 32 bitni kod (naravno korišćenje AMD-ovog novog AMD64 seta instrukcija bi učinilo ovo nevažnim, ali Matt je ograničen na 32-bitni kod). Npr., samo lokacija memorije i sekvenca koda koja može da izvrši povećanje i da učitava čak i u multiprocesorskim situacijama. Jedno od problema je činjenica da su većina memorijskih operacija prekinuta duž magistrale jer individualno učitava i upisuje tako da ALU + memorijska operacije neće biti atomska - međutim to se može tretirati sa kodnom bravom. Pravi problem je što je nemoguće napraviti dva 32-bitni memorijska pristupa da budu zaista atomska.

Prvo iskoristimo vreme da pokažemo rešenje koje ne funkcioniše:

     mov  eax, 1
lock add [counter], eax   ; [[1]]
     mov  eax, 0
lock adc [counter+4], eax ; [[2]]

Problema je što između [[1]] i [[2]] vaša nit može biti predupređena sa drugom niti koja pokušava da primeni isti kod. To znači da bilo koji dati ciklus 64-bitne vrednosti [brojač] može lako da bude neprecizan, pa čak i tako puno. To je ono što je poznato kao race condition. Postoji beskonačan broj netačnih pokušaja da se da zakrpi ovaj tip koda, što može zahtevati analize za otkrivanje mana. Ja ću preskočiti sve što možete/i treba da naučite o njima na nivou časova na koledžu.

; Eighth generation (64bit) x86 code.
mov rax, 1
lock xadd [counter], rax
inc rax

Ovo opisuje semantiku koju tražimo -- želimo da povećamo i da se vratimo sa povećanom vrednošću poštujući lokalni kontekst. Dakle, ne samo da moramo da uradimo to za 64-bita, već moramo da dobijemo učitavanje iza brojača na način koji odražava tu vrednost pre nego što bilo koja druga tema poveća brojač. Naravno, uzimajući da je AMD64 nov set instrukcija, trebalo bi da prođe malo vremena pre nego što budemo mogli da implementiramo ovo rešenje naširoko.

Ali startujući sa Pentium Pro setom instrukcija, čak 32 bit x86s imaju bitk86s imaju pristup 64-bitnom testu i setu instrukcija: CMPXCHG8B:

retry: mov        eax, dword ptr [counter]    ; [[1]]
       mov        edx, dword ptr [counter+4] ; [[2]]
       mov        ebx, eax
       mov        ecx, edx
       add        ebx, 1
       adc        ecx, 0
  lock cmpxchg8b  qword ptr [counter]         ; [[3]]
       jnz        retry

Dakle ideja je da se spekulativno nadamo da će brojač ostati netaknut od strane drugih tema iz [[1]] do [[3]]. CMPXCHG8B instrukcija nam omogućava da proverimo ovo pre angažujemo operaciju povećanja. prirastu Ako postoji bilo koja nedoslednost (uključujući neslaganja između [[1]] i [[2]] kao rezultat interventnih operacija povećanja) onda se vraćamo na kraj reda čekajućih povećavanja i ponovo pokrećemo operaciju.

Već možemo da vidimo da sa ovim rešenjem smo ušli u prostor gde teorija počinje da se mršti na naše pretpostavke. Ne postoji garancija da će bilo koja tema na kraju da se završi zato što može da se zaglavi u ovoj ponovo pokušanoj petlji za određeno vreme. U stvari, kada je Matt ovo merio benchmark-u (verovatno je mislio da će zaista pobediti mnoge teme i višestruke procesore) saznao je da su performanse ovog koda bile veoma nezadovoljavajuće iz jednog razloga -- dakle ima praktičnih posledica takođe.

"63-bitni brojač", dolazi od ideje da koristeći jedan od bita kao nekakvu zastavu koja ukazuje da se obmotavanje desilo. Možemo pretpostaviti da većinu vremena, povećanje će uticati na samo nekoliko, otprilike 30-bitova, i da samo treba da se konkretno bavimo konkretnim slučajevima obmotavanja. Uz malu pomoć Terje Mathisen i Matt Taylor, smislio sam sledeći kod (baziranim na XADD instrukciji koji je dostupan još od 80486 procesora):

; by Paul Hsieh, Matt Taylor and Terje Mathisen
incrementCounterAndRead:
     mov   eax, 1
     ;;cli
     mov   edx, [counter+4] ; [[1]]
lock xadd  [counter], eax
     cmp   eax, 07FFFFFFFh
     jne   incrDone
     inc   edx
     mov   [counter+4],edx  ; [[2]]
     mov   ebx, 080000000h
lock add   [counter], ebx   ; [[3]]
     ;;sti
     jmp   readDone

incrDone:
     ;;sti
     jb    noLockBit
retry:
     cmp   edx, [counter+4] ; Early correction.
     jne   topIsUpToDate
     mov   ebx, [counter]
     cmp   ebx, 07FFFFFFFh
     ja    retry            ; Wait for "lock bit"&nb sp;to reset.
topIsUpToDate:
     mov   edx, [counter+4]
     jmp   readDone

noLockBit:
     mov   ebx, [counter+4]
     cmp   edx, ebx
     je    readDone
     cmp   eax, 040000000h  ; bit 30 on -> before wrap.
     jae   readDone
     mov   edx, ebx         ; after wrap.
readDone:
     lea   eax, [2*eax+1]   ; previous low + 1.
     shrd  eax, edx, 1
     shr   edx, 1

Glavna ideja je da su niži 31 bitovi samo nižii 31 bitovi brave, 31 bit pokazuje da se odmotavanje desilo, i 30 bit takođe može da ukaže ukoliko se neka protivrečnost u visokim 32 bitovima desila zbog odmotavanja.

Sa pretpostavkom.da će se ne više od 30 bitova od (oko milijardu) povećanja desiti tokom spora mi se ne nalazimo više u nečemu sličnome teorijskoj teritoriji. Na primer, postoji očigledna uslovna trka između [[1]] i [[2]] ako, ustvari, postoji 4.3 milijardi povećanja iz prethodnih tema između dve operacije zbog prisvojenja. Međutim, imajući milijardu teme koje preduzimaju akciju između nekoliko instrukcija nije realan scenario, pa bi ovo u praksi trebalo da radi prilično dobro.

Atomic primitives koji vole ovo su uvek lukavi, pa vredi probati videti zašto radi. (Rečeno na drugi način, ne treba verovati ovom kodu, ili bilo čijem, osim ako ne razumete kako radi).

Ok, korišćenjem XADD na nižim 32 bitovima, zaista ne postoji mogućnost da će niži 31 bitovi krenuti naopako. I kada se 31 bitno obmotavanje desi, tačna nit gde se obmotavanje desilo predstavlja jedinu nit koja pokušava da ispravi visoku reč. Kada je visoka reč netačna, to je samo jedna manje od njene tačne vrednosti i "lock bit" (31 bit od niže reči) biće postavljen. Tako možete videti da akcija uvećavanja drži bitove u stanju dobro definisanom i determinističkom stanju.

O specifičnom slučaju čitanja ormara obmotavanja se vodi posebno računa, pa pretpostavimo da smo mi jedan od drugih tema. Kada se učitava, ako je viša polovina u skladu sa nižom polovinom (na primer, ubacivanjem niže polovinu učitavanja između dve visoke polovine učitavanja) i ne postoji set brava bitova, onda smo spremni. Ako postoji bilo koja nedoslednost to je zato što su neke druge teme umotane. Mi onda možemo ispitati naš 30 bit da vidimo da li treba budemo poruka ili unapred obmotavanje koje nam govori da li treba da izvršimo kasnije ili ranije čitanje više polovine.

Konačno, ako je brava bitova spremna, znamo smo posle povećanja, i samo čekamo da se brava ukloni ili da se viša polovine promeni i onda samo ponovo učitamo višu polovinu.

Prokomentarisne CLI i STI instrukcije pokazuju gde bi ove instrukcije trebalo da idu da pokušaju da smanje izloženu regiju neizvesnosti u zaključanoj vrednosti (navodeći druge teme da se okreću). U sistemu jednog procesora one su dovoljne da spreče bilo kakavo zadržavanje, a u multiprocesorskom sistemu bi dale neku vrstu garancije koja se tiče iznosa vremena u kojem brojač ne bi bio u trivijalnom stanju. Ali naravno potreban vam je prsten 0 pristup da izvrši ove instrukcije, i one nisu neophodne za funkcionalnu ispravnost.

A u C? Nije neki igrač bojim se. Čak i sa podrškom operativnog sistema, jezik ne može da se takmiči sa ovim tipom pristupa niskog nivoa.

Ostanite priključeni za više ...

Oznaka asemblerskog jezika