Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Oznaka asemblerskog jezika

ASM LABOva 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.

  1. 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)

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

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

  4. 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 >>)

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

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

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

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

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

  10. 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)


    So

    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.

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


  12. 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)

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

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


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




Published (Last edited): 16-09-2012 , source: http://www.azillionmonkeys.com/qed/asmexample.html