Funkce vestavěné v GCC pro nízkoúrovňové bitové operace a rotace

Obsah

1. Funkce vestavěné v GCC pro provádění nízkoúrovňových bitových operací a rotací

2. Bitová rotace doprava i doleva

3. Způsob překladu operace rotace doleva do strojového kódu

4. Překlad volání funkce __builtin_stdc_rotate_left pro platformu x86–64

5. Analýza vygenerovaného strojového kódu pro platformu x86–64

6. Překlad volání funkce __builtin_stdc_rotate_left pro 32bitové ARMy

7. Analýza vygenerovaného strojového kódu pro platformu ARM32

8. Překlad volání funkce __builtin_stdc_rotate_left pro 64bitové ARMy (AArch64)

9. Analýza vygenerovaného strojového kódu pro platformu AArch64

10. Rozdíl mezi operací rotace doleva a doprava

11. Překlad operace rotace doprava pro všechny analyzované platformy

12. Funkce pro výpočet parity v bajtu či vícebajtovém slovu

13. Volání vestavěných funkcí __builtin_parity, __builtin_parityl a __builtin_parityll

14. Realizace výpočtu parity na platformě x86–64

15. Realizace výpočtu parity na platformě ARM32

16. Realizace výpočtu parity na platformě ARM64 (AArch64)

17. Výpočet parity a celočíselné datové typy se znaménkem

18. Další bitové operace podporované vestavěnými funkcemi GCC

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Funkce vestavěné v GCC pro provádění nízkoúrovňových bitových operací a rotací

Na předchozí dvojici článků o funkcích vestavěných do GCC, které slouží k provádění nízkoúrovňových operací [1] [2] dnes navážeme. Prozatím jsme si popsali realizace operace součtů s přenosem (carry), které jsou relativně často používány v praxi. Ve druhém článku jsme se zmínili o funkcích, které interně volají instrukce RDSEED a RDRAND, jež přistupují k vestavěnému generátoru náhodných čísel (což je specifikum platformy x86–64). Ovšem podobných nízkoúrovňových operací existuje celá řada. Dnes se zaměříme na dvě skupiny takových operací. V první skupině se nachází operace pro provedení bitové rotace (nikoli posunu) doleva či doprava o specifikovaný počet bitů. A ve skupině druhé nalezneme operace pro výpočet parity předaného bajtu či vícebajtového slova.

Přitom nás nebude zajímat pouze způsob volání těchto operací (to je ve skutečnosti triviální), ale i to, jak jsou tyto operace přeloženy do strojového kódu. Zaměříme se na platformu x86–64, ARM32 (tedy původní ARMy) a AArch64 (64bitová architektura). Zajímavé bude například zjištění, že pro výpočet parity se na architektuře AArch64 musí volat „vektorové“ (SIMD) operace a na platformě ARM32 se namísto volání specializované instrukce volá systémová subrutina. A taktéž bude zajímavé zjistit způsob realizace bitových rotací pro „nenativní“ bitové šířky u architektur ARM32 i AArch64 (jedná se o rotace bajtů, šestnáctibitových slov a u ARM32 i rotace 64bitových slov).

2. Bitová rotace doprava i doleva

Pro realizaci některých nízkoúrovňových operací, ale i například v oblasti kryptografie nebo při generování pseudonáhodných hodnot, se setkáme s nutností provedení bitové rotace doprava nebo doleva. Od běžných bitových posunů se rotace liší tím, že bity, které z rotovaného bajtu nebo slova vysouváme ven, jsou přidány na druhou stranu rotovaného operandu. Na některých platformách jsou ještě k dispozici operace pro bitovou rotaci s přidaným bitem, který je typicky ukládán do příznaku přenosu carry, takže výsledkem je vlastně jakýsi hybrid mezi skutečnou bitovou rotací a bitovým posunem. Nicméně se vraťme k operaci rotace. Na rozdíl od logických bitových posunů, které jsou v jazyku C dobře podporovány operátory << a >>, neexistují ve standardním jazyku C operátory pro rotace (ale ani pro aritmetický posun či pro posuny hodnot se znaménkem).

GCC ale i některé další překladače jazyka C, namísto toho nabízí vestavěné (builtin) funkce, které rotace umožňují provést. Jedná se o generické funkce, protože za type1 nebo type2 lze dosadit libovolný celočíselný typ (ovšem druhá hodnota musí být nezáporná, jinak není chování definováno):

type1 __builtin_stdc_rotate_left(type1 arg1, type2 arg2)
type1 __builtin_stdc_rotate_right(type1 arg1, type2 arg2)

3. Způsob překladu operace rotace doleva do strojového kódu

V dnešním prvním demonstračním příkladu je volána vestavěná funkce nazvaná __builtin_stdc_rotate_left, která je určena pro rotaci svého prvního parametru doleva o takový počet bitů, který je uložen ve druhém parametru. První parametr musí být typu celé číslo bez znaménka (unsigned), druhý parametr může být i typu celé číslo se znaménkem (signed) i bez znaménka. Ovšem chování této funkce není definováno pro záporné hodnoty druhého parametru! V demonstračním příkladu postupně provádíme rotaci bajtu, 16bitového slova, 32bitového slova i 64bitového slova:

#include <stdint.h>
 
uint8_t rotate_left_8bit(uint8_t x, uint8_t y) {
    uint8_t z;
    z = __builtin_stdc_rotate_left(x, y);
    return z;
}
 
uint16_t rotate_left_16bit(uint16_t x, uint16_t y) {
    uint16_t z;
    z = __builtin_stdc_rotate_left(x, y);
    return z;
}
 
uint32_t rotate_left_32bit(uint32_t x, uint32_t y) {
    uint32_t z;
    z = __builtin_stdc_rotate_left(x, y);
    return z;
}
 
uint64_t rotate_left_64bit(uint64_t x, uint64_t y) {
    uint64_t z;
    z = __builtin_stdc_rotate_left(x, y);
    return z;
}

4. Překlad volání funkce __builtin_stdc_rotate_left pro platformu x86–64

Překlad výše uvedeného příkladu pro platformu x86–64 bez povolení optimalizací dopadne následovně (projekt v Compiler Exploreru):

rotate_left_8bit:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     BYTE PTR [rbp-20], dl
        mov     BYTE PTR [rbp-24], al
        movzx   edx, BYTE PTR [rbp-20]
        movzx   eax, BYTE PTR [rbp-24]
        movzx   eax, al
        and     eax, 7
        mov     ecx, eax
        rol     dl, cl
        mov     eax, edx
        mov     BYTE PTR [rbp-1], al
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
        ret
 
rotate_left_16bit:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     WORD PTR [rbp-20], dx
        mov     WORD PTR [rbp-24], ax
        movzx   edx, WORD PTR [rbp-20]
        movzx   eax, WORD PTR [rbp-24]
        movzx   eax, ax
        and     eax, 15
        mov     ecx, eax
        rol     dx, cl
        mov     eax, edx
        mov     WORD PTR [rbp-2], ax
        movzx   eax, WORD PTR [rbp-2]
        pop     rbp
        ret
 
rotate_left_32bit:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        mov     DWORD PTR [rbp-24], esi
        mov     edx, DWORD PTR [rbp-20]
        mov     eax, DWORD PTR [rbp-24]
        and     eax, 31
        mov     ecx, eax
        rol     edx, cl
        mov     eax, edx
        mov     DWORD PTR [rbp-4], eax
        mov     eax, DWORD PTR [rbp-4]
        pop     rbp
        ret
 
rotate_left_64bit:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     QWORD PTR [rbp-32], rsi
        mov     rdx, QWORD PTR [rbp-24]
        mov     rax, QWORD PTR [rbp-32]
        and     eax, 63
        mov     ecx, eax
        rol     rdx, cl
        mov     rax, rdx
        mov     QWORD PTR [rbp-8], rax
        mov     rax, QWORD PTR [rbp-8]
        pop     rbp
        ret

Naopak, pokud při překladu povolíme plné optimalizace, dosáhneme následujícího výsledku, který je již velmi dobře čitelný a pochopitelný:

rotate_left_8bit:
        mov     eax, edi
        mov     ecx, esi
        rol     al, cl
        ret
 
rotate_left_16bit:
        mov     eax, edi
        mov     ecx, esi
        rol     ax, cl
        ret
 
rotate_left_32bit:
        mov     eax, edi
        mov     ecx, esi
        rol     eax, cl
        ret
 
rotate_left_64bit:
        mov     rax, rdi
        mov     ecx, esi
        rol     rax, cl
        ret

5. Analýza vygenerovaného strojového kódu pro platformu x86–64

Již od začátku existence platformy x86 byly v její instrukční sadě realizovány instrukce určené pro bitové rotace a posuny. Jedná se konkrétně o následujících osm instrukcí:

Bitové posuny (shift) jsou využity při realizaci céčkovských operátorů << a >>, a to (opět na platformě x86 a x86–64) i pro posun operandu se znaménkem (signed), což je obecně v jazyku C nedefinovaná operace.

Nás však budou nyní zajímat pouze první čtyři instrukce, tj. rotace a nikoli posuny. Instrukce ROL a ROR provádí rotaci celého operandu (8, 16, 32, 64bitů) doleva resp. doprava, a to buď o jeden bit, o CL bitů nebo o počet bitů zadaný v instrukčním kódu (konstanta). A instrukce RCL a RCR provádí rotaci operandu+jednoho bitu navíc (jeden bit je získán z příznaku CF a jiný uložen do tohoto příznaku), tj. jedná se o rotace 9, 17, 33 nebo 65 bitů.

Jak je z demonstračního příkladu přeloženého do assembleru zřejmé, díky tomu, že je počet bitů, které se mají rotovat, proměnný (předaný v parametru), použila se instrukce ROL, přičemž druhým operandem je vždy registr CL. To je logické, protože vlastně vyšší bity rotace nemají žádný význam. Zvyšuje se pouze bitová šířka prvního (rotovaného) operandu a samozřejmě i bitová šířka výsledku:

rol     al, cl
 
rol     ax, cl
 
rol     eax, cl
 
rol     rax, cl

6. Překlad volání funkce __builtin_stdc_rotate_left pro 32bitové ARMy

Nyní se podívejme na způsob překladu stejného céčkovského zdrojového kódu se stejnou funkcí __builtin_stdc_rotate_left (třetí kapitola), nyní ovšem pro 32bitovou architekturu ARM (minimálně ARMv7, což je dnes již naprostý standard). Při povolení optimalizací bude výsledek vypadat takto:

rotate_left_8bit:
        and     r1, r1, #7
        rsb     r3, r1, #0
        and     r3, r3, #7
        lsr     r3, r0, r3
        orr     r0, r3, r0, lsl r1
        and     r0, r0, #255
        bx      lr
 
rotate_left_16bit:
        and     r1, r1, #15
        rsb     r3, r1, #0
        and     r3, r3, #15
        lsr     r3, r0, r3
        orr     r0, r3, r0, lsl r1
        lsl     r0, r0, #16
        lsr     r0, r0, #16
        bx      lr
 
rotate_left_32bit:
        and     r1, r1, #31
        rsb     r1, r1, #32
        ror     r0, r0, r1
        bx      lr
 
rotate_left_64bit:
        push    {r4, lr}
        mov     lr, r1
        and     r2, r2, #63
        sub     r4, r2, #32
        rsb     r3, r2, #0
        lsl     r1, r1, r2
        and     r3, r3, #63
        orr     r1, r1, r0, lsl r4
        rsb     ip, r2, #32
        orr     r1, r1, r0, lsr ip
        rsb     r4, r3, #32
        lsr     ip, r0, r3
        orr     r1, r1, lr, lsr r3
        orr     ip, ip, lr, lsl r4
        sub     r3, r3, #32
        orr     ip, ip, lr, lsr r3
        orr     r0, ip, r0, lsl r2
        pop     {r4, lr}
        bx      lr

7. Analýza vygenerovaného strojového kódu pro platformu ARM32

Podívejme se nyní na způsob překladu realizace operace rotace doleva na 32bitových platformách ARM. Na této platformě je k dispozici jediná instrukce rotace, a to konkrétně instrukce ROR provádějící rotaci doprava. Do této skupiny instrukcí navíc spadají i logické posuny LSL a LSR i instrukce pro aritmetický posun ASR. Bitovou rotaci instrukcí ROR lze provádět buď o počet bitů stanovený konstantou (ovšem s omezeními), nebo o počet bitů uložených v jiném pracovním registru.

Jak se ovšem provede rotace doleva, kterou vyžadujeme? Je to jednoduché – postačuje provést rotaci doprava, ovšem počet bitů bude vypočten tak, aby výsledkem byla hodnota odpovídající rotaci doleva. Přesně takto je rotace implementována pro 32bitové hodnoty (RSB znamená reverse subtract, tj. v tomto případě odečtení obsahu registru R1 od konstanty 32):

and     r1, r1, #31
rsb     r1, r1, #32
ror     r0, r0, r1

Při rotaci osmibitové hodnoty se ovšem postupuje odlišně. Provede se bitový posun a následně se do nejnižších bitů výsledku přidají ty bity, který sem byly přesunuty v případě skutečné rotace. Ilustrujme si celý postup při rotaci osmibitové hodnoty o jeden bit doleva:

                           ; R0    R1    R3
                           ; x     1     ?
and     r1, r1, #7         ; x     1     ?
rsb     r3, r1, #0         ; x     1     -1 (0b11111111)
and     r3, r3, #7         ; x     1     7  (0b111)
lsr     r3, r0, r3         ; x     1     x>>7 (bitový posun doprava, získáme nejnižší bit výsledku)
orr     r0, r3, r0, lsl r1 ; x>>7 || x<<1 (přidali jsme nejvyšších sedm bitů výsledku)
and     r0, r0, #255

Podobným způsobem je realizována rotace šestnáctibitové hodnoty. U hodnoty 64bitové je rotace taktéž nahrazena instrukcemi pro bitový posun, protože na 32bitových ARMech nejsou přímo podporovány 64bitové operace. Rotaci tedy musíme nasimulovat posunem obsahu dvou 32bitových hodnot a přenesením nejnižších bitů do výsledku.

8. Překlad volání funkce __builtin_stdc_rotate_left pro 64bitové ARMy (AArch64)

Pro mikroprocesory a mikrořadiče s architekturou AArch64 je překlad proveden zcela odlišným způsobem, než je tomu u 32bitových ARMů. Je to ostatně patrné i při pohledu na výsledek překladu, který bude (v případě povolení optimalizací) vypadat následovně:

rotate_left_8bit:
        and     w1, w1, 7
        and     w0, w0, 255
        neg     w2, w1
        and     w2, w2, 7
        lsl     w1, w0, w1
        lsr     w0, w0, w2
        orr     w0, w1, w0
        ret
 
rotate_left_16bit:
        and     w1, w1, 15
        and     w0, w0, 65535
        neg     w2, w1
        and     w2, w2, 15
        lsl     w1, w0, w1
        lsr     w0, w0, w2
        orr     w0, w1, w0
        ret
 
rotate_left_32bit:
        neg     w1, w1
        ror     w0, w0, w1
        ret
 
rotate_left_64bit:
        neg     w1, w1
        ror     x0, x0, x1
        ret

9. Analýza vygenerovaného strojového kódu pro platformu AArch64

Množina instrukcí navržených pro provedení operací aritmetického či bitového (logického) posunu a rotace je na architektuře AArch64 celkem přehledná. Povšimněte si navíc poslední instrukce ROR určené pro bitovou rotaci – ta nás vlastně zajímá nejvíc. Neexistuje zde rotace vlevo, protože ta samozřejmě odpovídá rotaci vpravo, ovšem o odlišnou hodnotu (odečtenou od 63 či 31, resp. postačí změna znaménka):

U všech předchozích instrukcí byl posun specifikován konstantou, zatímco u dalších čtyř instrukcí je posun uložen v registru (druhý vstupní operand). Hodnota tohoto registru však není použita přímo, protože se v úvahu bere jen posledních pět či šest bitů podle toho, zda se jedná o 32bitovou či 64bitovou operaci:

Jak to vypadá v našich konkrétních příkladech? Nejjednodušší je situace u rotace 32bitového a 64bitového operandu. Zde se používá instrukce ROR (nikoli neexistující ROL), ovšem počet bitů, o které se má rotace provést, je nejdříve znegován:

rotate_left_32bit            rotate_left_64bit:
        neg     w1, w1             neg     w1, w1
        ror     w0, w0, w1         ror     x0, x0, x1
        ret                        ret

U rotace osmibitového nebo šestnáctibitového operandu je tomu jinak. Nejprve je s využitím operace AND zaručeno, že rotace bude provedena o maximálně sedm resp. patnáct bitů. Následně se zajistí, že velikost rotovaného operandu nepřesáhne rozsah jednoho bajtu resp. dvou bajtů. Poté je do registru W2 uložena vypočtená hodnota počtu bitů pro rotaci doprava, kterou získáme nejnižší bit. Samotná rotace doleva, která se má provést, je simulována posunem doleva (do nejnižšího bitu je nasunuta nula) následovaná přidáním korektní hodnoty nejnižšího bitu (nebo bitů) operací OR:

rotate_left_8bit             rotate_left_16bit:
        and     w1, w1, 7          and     w1, w1, 15
        and     w0, w0, 255        and     w0, w0, 65535
        neg     w2, w1             neg     w2, w1
        and     w2, w2, 7          and     w2, w2, 15
        lsl     w1, w0, w1         lsl     w1, w0, w1
        lsr     w0, w0, w2         lsr     w0, w0, w2
        orr     w0, w1, w0         orr     w0, w1, w0
        ret                        ret

Ilustrujme si to na rotaci osmibitové hodnoty o jeden bit doleva:

                        ; W0    W1    W2
                        ; x     1     ?
and     w1, w1, 7       ; x     1     ?
and     w0, w0, 255     ; x     1     ?
neg     w2, w1          ; x     1     -1 (0b11111111)
and     w2, w2, 7       ; x     1     7  (0b111)
lsl     w1, w0, w1      ; x     x<<1  7  (bitový posun doleva)
lsr     w0, w0, w2      ; x>>7  x<<1  ?  (ve W0 bude jen nejnižší bit odpovídající původnímu sedmému bitu)
orr     w0, w1, w0      ; x>>7 || x<<1   (W1 a W2 nás již nezajímá)

10. Rozdíl mezi operací rotace doleva a doprava

Prozatím jsme si ukázali, jakým způsobem je přeložena vestavěná funkce __builtin_stdc_rotate_left. Jen pro úplnost se podívejme na prakticky totožný příklad, který ovšem nyní bude volat vestavěnou funkci určenou pro rotaci doprava, tedy funkci __builtin_stdc_rotate_right. Tuto funkci opět budeme volat s celočíselnými operandy bez znaménka s různou bitovou šířkou:

#include <stdint.h>
 
uint8_t rotate_right_8bit(uint8_t x, uint8_t y) {
    uint8_t z;
    z = __builtin_stdc_rotate_right(x, y);
    return z;
}
 
uint16_t rotate_right_16bit(uint16_t x, uint16_t y) {
    uint16_t z;
    z = __builtin_stdc_rotate_right(x, y);
    return z;
}
 
uint32_t rotate_right_32bit(uint32_t x, uint32_t y) {
    uint32_t z;
    z = __builtin_stdc_rotate_right(x, y);
    return z;
}
 
uint64_t rotate_right_64bit(uint64_t x, uint64_t y) {
    uint64_t z;
    z = __builtin_stdc_rotate_right(x, y);
    return z;
}

11. Překlad operace rotace doprava pro všechny analyzované platformy

Rotace doprava přeložená pro platformu x86–64 bez povolení optimalizací. Výsledné kódy sice nejsou příliš přehledné, ale vždy zde nalezneme instrukci ROR:

rotate_right_8bit:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     BYTE PTR [rbp-20], dl
        mov     BYTE PTR [rbp-24], al
        movzx   edx, BYTE PTR [rbp-20]
        movzx   eax, BYTE PTR [rbp-24]
        movzx   eax, al
        and     eax, 7
        mov     ecx, eax
        ror     dl, cl
        mov     eax, edx
        mov     BYTE PTR [rbp-1], al
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
        ret
 
rotate_right_16bit:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     WORD PTR [rbp-20], dx
        mov     WORD PTR [rbp-24], ax
        movzx   edx, WORD PTR [rbp-20]
        movzx   eax, WORD PTR [rbp-24]
        movzx   eax, ax
        and     eax, 15
        mov     ecx, eax
        ror     dx, cl
        mov     eax, edx
        mov     WORD PTR [rbp-2], ax
        movzx   eax, WORD PTR [rbp-2]
        pop     rbp
        ret
 
rotate_right_32bit:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        mov     DWORD PTR [rbp-24], esi
        mov     edx, DWORD PTR [rbp-20]
        mov     eax, DWORD PTR [rbp-24]
        and     eax, 31
        mov     ecx, eax
        ror     edx, cl
        mov     eax, edx
        mov     DWORD PTR [rbp-4], eax
        mov     eax, DWORD PTR [rbp-4]
        pop     rbp
        ret
 
rotate_right_64bit:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     QWORD PTR [rbp-32], rsi
        mov     rdx, QWORD PTR [rbp-24]
        mov     rax, QWORD PTR [rbp-32]
        and     eax, 63
        mov     ecx, eax
        ror     rdx, cl
        mov     rax, rdx
        mov     QWORD PTR [rbp-8], rax
        mov     rax, QWORD PTR [rbp-8]
        pop     rbp
        ret

Po povolení optimalizací je již prováděný postup zcela zřejmý – ve všech případech je provedena rotace doprava instrukcí ROR o počet bitů uložených v registru CL (nezávisle na bitové šířce prvního operandu):

rotate_right_8bit:
        mov     eax, edi
        mov     ecx, esi
        ror     al, cl
        ret
 
rotate_right_16bit:
        mov     eax, edi
        mov     ecx, esi
        ror     ax, cl
        ret
 
rotate_right_32bit:
        mov     eax, edi
        mov     ecx, esi
        ror     eax, cl
        ret
 
rotate_right_64bit:
        mov     rax, rdi
        mov     ecx, esi
        ror     rax, cl
        ret

Na 32bitové platformě ARM je instrukce ROR použita jen u 32bitové rotace. Pro rotace osmibitových bajtů nebo šestnáctibitových slov je nutné rotaci simulovat dvojicí bitových posunů se složením výsledku pomocí OR, což je postup, který jsme si vysvětlili u rotace doleva:

rotate_right_8bit:
        and     r1, r1, #7
        rsb     r3, r1, #0
        and     r3, r3, #7
        lsl     r3, r0, r3
        orr     r0, r3, r0, lsr r1
        and     r0, r0, #255
        bx      lr
 
rotate_right_16bit:
        and     r1, r1, #15
        rsb     r3, r1, #0
        and     r3, r3, #15
        lsl     r3, r0, r3
        orr     r0, r3, r0, lsr r1
        lsl     r0, r0, #16
        lsr     r0, r0, #16
        bx      lr
 
rotate_right_32bit:
        and     r1, r1, #31
        ror     r0, r0, r1
        bx      lr
 
rotate_right_64bit:
        push    {r4, lr}
        mov     lr, r0
        and     r2, r2, #63
        rsb     r4, r2, #32
        rsb     r3, r2, #0
        lsr     r0, r0, r2
        and     r3, r3, #63
        orr     r0, r0, r1, lsl r4
        sub     ip, r2, #32
        orr     r0, r0, r1, lsr ip
        sub     r4, r3, #32
        lsl     ip, r1, r3
        orr     r0, r0, lr, lsl r3
        orr     ip, ip, lr, lsl r4
        rsb     r3, r3, #32
        orr     ip, ip, lr, lsr r3
        orr     r1, ip, r1, lsr r2
        pop     {r4, lr}
        bx      lr

A konečně se podívejme na způsob překladu pro 64bitovou platformu AArch64. Zde je „nativní“ instrukce ROR volána pouze v případě 32bitových a 64bitových rotací. Pro kratší operandy je opět nutná simulace rotace bitovými posuny:

rotate_right_8bit:
        and     w1, w1, 7
        and     w0, w0, 255
        neg     w2, w1
        and     w2, w2, 7
        lsr     w1, w0, w1
        lsl     w0, w0, w2
        orr     w0, w1, w0
        ret
 
rotate_right_16bit:
        and     w1, w1, 15
        and     w0, w0, 65535
        neg     w2, w1
        and     w2, w2, 15
        lsr     w1, w0, w1
        lsl     w0, w0, w2
        orr     w0, w1, w0
        ret
 
rotate_right_32bit:
        ror     w0, w0, w1
        ret
 
rotate_right_64bit:
        ror     x0, x0, x1
        ret

12. Funkce pro výpočet parity v bajtu či vícebajtovém slovu

Ve druhé polovině dnešního článku se budeme zabývat vestavěnými funkcemi sloužícími pro výpočet parity, tj. počtu jedničkových bitů v bajtu či vícebajtovém slovu. I s tímto výpočtem se lze relativně často setkat, ovšem programovací jazyk C nenabízí pro výpočet parity žádné speciální operátory. Namísto toho můžeme volat vestavěné funkce, které mají následující hlavičku:

int __builtin_parity(unsigned int x)
int __builtin_parityl(unsigned long)
int __builtin_parityll(unsigned long long)

V novějších verzích překladače GCC je nabízena ještě generická varianta výše uvedených funkcí, která má tuto hlavičku (za … lze dosadit libovolný celočíselný typ bez znaménka):

int __builtin_parityg(...)

A jak je parita spočítána interně? Nejjednodušší je to na platformě x86–64, protože zde existuje paritní bit PF. Ten je (po příslušné testovací či aritmetické operaci) nastaven na jedničku v případě, že má výsledek sudou paritu (a pochopitelně je vynulován při liché paritě). A navíc platforma x86–64 obsahuje instrukce SETcc, které dokážou nastavit hodnotu ve zvoleném pracovním registru na nulu, pokud je splněna podmínka specifikovaná v cc. A touto podmínkou může být test paritního bitu PF na nulu nebo na jedničku:

SETP  cílový_registr
SETNP cílový_registr

13. Volání vestavěných funkcí __builtin_parity, __builtin_parityl a __builtin_parityll

V dalším demonstračním příkladu, který si posléze přeložíme pro všechny sledované platformy, jsou volány vestavěné funkce __builtin_parity, __builtin_parityl a __builtin_parityll. Na rozdíl od bitových rotací, v nichž jsem použil datové typy uint??_t a int??_t, nyní použiji původní označení typů v jazyku C, protože i vestavěné funkce pro výpočet parity tyto datové typy mají ve své signatuře (a mapování mezi těmito dvěma skupinami typů je platformově závislé):

int parity_char(unsigned char x) {
    return __builtin_parity(x);
}

int parity_int(unsigned int x) {
    return __builtin_parity(x);
}

int parity_long(unsigned long x) {
    return __builtin_parityl(x);
}

int parity_long_long(unsigned long long x) {
    return __builtin_parityll(x);
}

14. Realizace výpočtu parity na platformě x86–64

Překlad výše uvedeného příkladu pro platformu x86–64 bez povolení optimalizací dopadne následovně (projekt v Compiler Exploreru):

parity_char:
        push    rbp
        mov     rbp, rsp
        mov     eax, edi
        mov     BYTE PTR [rbp-4], al
        movzx   eax, BYTE PTR [rbp-4]
        mov     edx, eax
        shr     edx, 16
        xor     eax, edx
        xor     al, ah
        setnp   al
        movzx   eax, al
        pop     rbp
        ret
 
parity_int:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        mov     edx, eax
        shr     edx, 16
        xor     eax, edx
        xor     al, ah
        setnp   al
        movzx   eax, al
        pop     rbp
        ret
 
parity_long:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        mov     rdx, rax
        shr     rdx, 32
        xor     eax, edx
        mov     edx, eax
        shr     edx, 16
        xor     eax, edx
        xor     al, ah
        setnp   al
        movzx   eax, al
        pop     rbp
        ret
 
parity_long_long:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        mov     rdx, rax
        shr     rdx, 32
        xor     eax, edx
        mov     edx, eax
        shr     edx, 16
        xor     eax, edx
        xor     al, ah
        setnp   al
        movzx   eax, al
        pop     rbp
        ret

Výsledek získaný po povolení všech optimalizací vypadá následovně. Zde je již patrné, že se skutečně využívá instrukce setnp. U 16bitových, 32bitových a 64bitových operandů jsou jednotlivé části nejdříve smíchány instrukcí XOR, která nemá na výsledek výpočtu parity žádný vliv. Postupně tedy získáme pouze osmibitový mezivýsledek, na který je již možné instrukci setnp aplikovat:

parity_char:
        xor     eax, eax
        test    dil, dil
        setnp   al
        ret
 
parity_int:
        mov     eax, edi
        shr     eax, 16
        xor     eax, edi
        xor     al, ah
        setnp   al
        movzx   eax, al
        ret
 
parity_long:
        mov     rax, rdi
        shr     rax, 32
        xor     eax, edi
        mov     edx, eax
        shr     edx, 16
        xor     eax, edx
        xor     al, ah
        setnp   al
        movzx   eax, al
        ret
 
parity_long_long:
        mov     rax, rdi
        shr     rax, 32
        xor     eax, edi
        mov     edx, eax
        shr     edx, 16
        xor     eax, edx
        xor     al, ah
        setnp   al
        movzx   eax, al
        ret

15. Realizace výpočtu parity na platformě ARM32

Na 32bitové platformě ARM není výpočet parity realizován jednou instrukcí, ale podprogramem (subrutinou). Zde tedy můžeme předpokládat relativně pomalé výpočty této operace:

parity_char:
        push    {r4, lr}
        bl      __paritysi2
        pop     {r4, lr}
        bx      lr
 
parity_int:
        push    {r4, lr}
        bl      __paritysi2
        pop     {r4, lr}
        bx      lr
 
parity_long:
        push    {r4, lr}
        bl      __paritysi2
        pop     {r4, lr}
        bx      lr
 
parity_long_long:
        push    {r4, lr}
        bl      __paritydi2
        pop     {r4, lr}
        bx      lr

16. Realizace výpočtu parity na platformě ARM64 (AArch64)

Nejzajímavější a nejkrkolomnější je způsob překladu výpočtu parity na platformě AArch64. Zde se totiž využívá instrukce cnt, která zjistí počet jedničkových bitů. Ovšem zajímavé je, že tato instrukce pracuje s „vektorovými“ registry Vxx a nikoli s běžnými celočíselnými pracovními registry. Takže si nejdříve uveďme, s jakými registry se vlastně na této platformě pracuje.

Původních patnáct pracovních registrů pojmenovaných R0 až R14, které známe z klasických 32bitových procesorů ARM, bylo rozšířeno na 31 registrů, z nichž každý má šířku 64 bitů. Z tohoto důvodu muselo dojít k úpravě pojmenování registrů způsobem, který je naznačený v následující tabulce:

Další sada registrů je používána při operacích s typy single/float a double (tedy s operandy reprezentovanými v systému plovoucí řádové čárky), u SIMD operací a taktéž kryptografickým modulem:

Pro SIMD operace, tj. operace pracující s vektory, se registry vn rozdělují takto:

Povšimněte si, že – na rozdíl od mnoha jiných architektur – nedochází k tomu, že by se například dva single registry mapovaly do jednoho double registru atd.

Vraťme se nyní k výpočtu parity. Nejprve je testovaná vstupní hodnota instrukcí FMOV přenesena do registru s31 nebo d31. Následně je instrukcí CNT zjištěn počet bitů nastavených na jedničku (povšimněte si, že se používá rozdělení vektorového registru po osmi bitech). Instrukcí ADDV jsou jednotlivé prvky registru sečteny a výsledek je převeden zpět do celočíselného registru W0. Nás ovšem nezajímá počet jedničkových bitů, ale to, zda je tento počet sudý nebo lichý. A přesně tuto operaci zajistí poslední instrukce AND:

parity_char:
        and     x0, x0, 255
        fmov    d31, x0
        cnt     v31.8b, v31.8b
        addv    b31, v31.8b
        fmov    w0, s31
        and     w0, w0, 1
        ret
 
parity_int:
        fmov    s31, w0
        cnt     v31.8b, v31.8b
        addv    b31, v31.8b
        fmov    w0, s31
        and     w0, w0, 1
        ret
 
parity_long:
        fmov    d31, x0
        cnt     v31.8b, v31.8b
        addv    b31, v31.8b
        fmov    x0, d31
        and     w0, w0, 1
        ret
 
parity_long_long:
        fmov    d31, x0
        cnt     v31.8b, v31.8b
        addv    b31, v31.8b
        fmov    x0, d31
        and     w0, w0, 1
        ret

17. Výpočet parity a celočíselné datové typy se znaménkem

Vestavěné funkce __builtin_parity, __builtin_parityl a __builtin_parityll jsou definovány pro parametry typu celé číslo bez znaménka (unsigned), protože pro typy se znaménkem je výpočet poněkud nejasný především ze sémantického pohledu (operace pracují s vektorem bitů, zatímco záporné hodnoty mají různé způsoby vyjádření). Teoreticky by nás tedy měl překladač jazyka C varovat, pokud se pokusíme o překlad tohoto kódu:

int parity_char(signed char x) {
    return __builtin_parity(x);
}
 
int parity_int(signed int x) {
    return __builtin_parity(x);
}
 
int parity_long(signed long x) {
    return __builtin_parityl(x);
}
 
int parity_long_long(signed long long x) {
    return __builtin_parityll(x);
}

V případě, že překlad provedeme například s následujícími přepínači, překladač žádné varování ani chyby nevypíše:

$ gcc -Wall -Werror parity_signed.c

Aby se potenciální problémy s hodnotami se znaménkem detekovaly, je nutné

$ gcc -Wall -Werror -Wconversion parity_signed.c

V tomto případě bude skutečně detekován problém při konverzi hodnot z typu se znaménkem na typ bez znaménka:

parity_signed.c: In function ‘parity_char’:
parity_signed.c:2:29: error: conversion to ‘unsigned int’ from ‘signed char’ may change the sign of the result [-Werror=sign-conversion]
    2 |     return __builtin_parity(x);
      |                             ^
parity_signed.c: In function ‘parity_int’:
parity_signed.c:6:29: error: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Werror=sign-conversion]
    6 |     return __builtin_parity(x);
      |                             ^
parity_signed.c: In function ‘parity_long’:
parity_signed.c:10:30: error: conversion to ‘long unsigned int’ from ‘long int’ may change the sign of the result [-Werror=sign-conversion]
   10 |     return __builtin_parityl(x);
      |                              ^
parity_signed.c: In function ‘parity_long_long’:
parity_signed.c:14:31: error: conversion to ‘long long unsigned int’ from ‘long long int’ may change the sign of the result [-Werror=sign-conversion]
   14 |     return __builtin_parityll(x);
      |                               ^
cc1: all warnings being treated as errors

V případě, že budeme volat modernější vestavěnou funkci __builtin_parityg, budou se problémy hlásit i v případě, že přepínač -Wconversion nepoužijeme. Ověřit si to opět můžeme velmi jednoduchým pokusem:

#include <stdint.h>
 
int parity_8bit(int8_t x) {
    return __builtin_parityg(x);
}
 
int parity_16bit(int16_t x) {
    return __builtin_parityg(x);
}
 
int parity_32bit(int32_t x) {
    return __builtin_parityg(x);
}
 
int parity_64bit(int64_t x) {
    return __builtin_parityg(x);
}

Chybová hlášení vypsaná překladačem GCC by měla vypadat následovně:

parityg_signed.c: In function ‘parity_8bit’:
parityg_signed.c:4:30: error: argument 1 in call to function ‘__builtin_parityg’ has signed type
    4 |     return __builtin_parityg(x);
      |                              ^
parityg_signed.c: In function ‘parity_16bit’:
parityg_signed.c:8:30: error: argument 1 in call to function ‘__builtin_parityg’ has signed type
    8 |     return __builtin_parityg(x);
      |                              ^
parityg_signed.c: In function ‘parity_32bit’:
parityg_signed.c:12:30: error: argument 1 in call to function ‘__builtin_parityg’ has signed type
   12 |     return __builtin_parityg(x);
      |                              ^
parityg_signed.c: In function ‘parity_64bit’:
parityg_signed.c:16:30: error: argument 1 in call to function ‘__builtin_parityg’ has signed type
   16 |     return __builtin_parityg(x);
      |                              ^
parityg_signed.c: In function ‘parity_8bit’:
parityg_signed.c:5:1: error: control reaches end of non-void function [-Werror=return-type]
    5 | }
      | ^
parityg_signed.c: In function ‘parity_16bit’:
parityg_signed.c:9:1: error: control reaches end of non-void function [-Werror=return-type]
    9 | }
      | ^
parityg_signed.c: In function ‘parity_32bit’:
parityg_signed.c:13:1: error: control reaches end of non-void function [-Werror=return-type]
   13 | }
      | ^
parityg_signed.c: In function ‘parity_64bit’:
parityg_signed.c:17:1: error: control reaches end of non-void function [-Werror=return-type]
   17 | }
      | ^
cc1: all warnings being treated as errors

18. Další bitové operace podporované vestavěnými funkcemi GCC

Překladač GCC programátorům nabízí i mnoho dalších vestavěných funkcí provádějících různé bitové operace:

int __builtin_ffs(int x)
int __builtin_clz(unsigned int x)
int __builtin_ctz(unsigned int x)
int __builtin_clrsb(int x)
int __builtin_popcount(unsigned int x)
int __builtin_ffsl(long)
int __builtin_clzl(unsigned long)
int __builtin_ctzl(unsigned long)
int __builtin_clrsbl(long)
int __builtin_popcountl(unsigned long)
int __builtin_ffsll(long long)
int __builtin_clzll(unsigned long long)
int __builtin_ctzll(unsigned long long)
int __builtin_clrsbll(long long)
int __builtin_popcountll(unsigned long long)
int __builtin_ffsg(...)
int __builtin_clzg(...)
int __builtin_ctzg(...)
int __builtin_clrsbg(...)
int __builtin_popcountg(...)
type __builtin_stdc_bit_ceil(type arg)
type __builtin_stdc_bit_floor(type arg)
unsigned int __builtin_stdc_bit_width(type arg)
unsigned int __builtin_stdc_count_ones(type arg)
unsigned int __builtin_stdc_count_zeros(type arg)
unsigned int __builtin_stdc_first_leading_one(type arg)
unsigned int __builtin_stdc_first_leading_zero(type arg)
unsigned int __builtin_stdc_first_trailing_one(type arg)
unsigned int __builtin_stdc_first_trailing_zero(type arg)
unsigned int __builtin_stdc_has_single_bit(type arg)
unsigned int __builtin_stdc_leading_ones(type arg)
unsigned int __builtin_stdc_leading_zeros(type arg)
unsigned int __builtin_stdc_trailing_ones(type arg)
unsigned int __builtin_stdc_trailing_zeros(type arg)

S některými funkcemi vypsanými před tímto odstavcem se seznámíme v navazujícím článku.

19. Repositář s demonstračními příklady

Demonstrační příklady napsané v jazyku C, které jsou určené pro překlad s využitím překladače gcc, byly uloženy do Git repositáře, který je dostupný na adrese https://github.com/tisnik/8bit-fame. Jednotlivé demonstrační příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý (dnes již poměrně rozsáhlý) repositář:

Všechny demonstrační příklady z článku Funkce vestavěné v GCC pro provádění nízkoúrovňových aritmetických operací jsou vypsány v následující tabulce:

20. Odkazy na Internetu

1. Funkce vestavěné v GCC pro provádění nízkoúrovňových aritmetických operací
   https://www.root.cz/clanky/funkce-vestavene-v-gcc-pro-provadeni-nizkourovnovych-aritmetickych-operaci/
2. Generátor náhodných čísel založený na instrukcích RDSEED a RDRAND
   https://www.root.cz/clanky/generator-nahodnych-cisel-zalozeny-na-instrukcich-rdseed-a-rdrand/
3. Circular shift (Wikipedia)
   https://en.wikipedia.org/wi­ki/Bitwise_operation#Circu­lar_shift
4. Parity bit (Wikipedia)
   https://en.wikipedia.org/wi­ki/Parity_bit
5. Parity function (Wikipedia)
   https://en.wikipedia.org/wi­ki/Parity_function
6. RDRAND (Wikipedia)
   https://en.wikipedia.org/wiki/RDRAND
7. RDRAND instruction
   https://www.felixcloutier­.com/x86/rdrand
8. Random Number Generator
   https://wiki.osdev.org/Ran­dom_Number_Generator
9. GCC documentation: Extensions to the C Language Family
   https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions
10. GCC documentation: Using Vector Instructions through Built-in Functions
    https://gcc.gnu.org/online­docs/gcc/Vector-Extensions.html
11. SSE (Streaming SIMD Extentions)
    http://www.songho.ca/misc/sse/sse­.html
12. Timothy A. Chagnon: SSE and SSE2
    http://www.cs.drexel.edu/~tc365/mpi-wht/sse.pdf
13. CPU design (Wikipedia)
    http://en.wikipedia.org/wi­ki/CPU_design
14. GCC Compiler Intrinsics
    https://iq.opengenus.org/gcc-compiler-intrinsics/
15. Other Built-in Functions Provided by GCC
    https://gcc.gnu.org/online­docs/gcc/Other-Builtins.html
16. GCC: 6.60 Built-in Functions Specific to Particular Target Machines
    https://gcc.gnu.org/online­docs/gcc/Target-Builtins.html#Target-Builtins
17. Additional Builtins for Numeric Operations
    https://gcc.gnu.org/online­docs/gcc/Numeric-Builtins.html
18. Bit Operation Builtins
    https://gcc.gnu.org/onlinedocs/gcc/Bit-Operation-Builtins.html
19. Stránka projektu Compiler Explorer
    https://godbolt.org/
20. The LLVM Compiler Infrastructure
    https://llvm.org/
21. GCC, the GNU Compiler Collection
    https://gcc.gnu.org/
22. Clang
    https://clang.llvm.org/
23. Clang: Assembling a Complete Toolchain
    https://clang.llvm.org/doc­s/Toolchain.html
24. Integer overflow
    https://en.wikipedia.org/wi­ki/Integer_overflow
25. SETcc — Set Byte on Condition
    https://www.felixcloutier­.com/x86/setcc
26. The ARMv8 instruction sets
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/ch05s01.html
27. A64 Instruction Set
    https://developer.arm.com/pro­ducts/architecture/instruc­tion-sets/a64-instruction-set
28. Switching between the instruction sets
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/ch05s01.html
29. The A64 instruction set
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/ch05s01.html
30. Introduction to ARMv8 64-bit Architecture
    https://quequero.org/2014/04/in­troduction-to-arm-architecture/
31. Undefined behavior (Wikipedia)
    https://en.wikipedia.org/wi­ki/Undefined_behavior
32. Is signed integer overflow still undefined behavior in C++?
    https://stackoverflow.com/qu­estions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c
33. Allowing signed integer overflows in C/C++
    https://stackoverflow.com/qu­estions/4240748/allowing-signed-integer-overflows-in-c-c
34. SXTB, SXTH, SXTW
    https://www.scs.stanford.e­du/~zyedidia/arm64/sxtb_z_p_z­.html
35. BX, BXNS
    https://developer.arm.com/do­cumentation/100076/0200/a32-t32-instruction-set-reference/a32-and-t32-instructions/bx–bxns?lang=en
36. Carry and Borrow Principles
    https://www.tpub.com/neet­s/book13/53a.htm
37. In binary subtraction, how do you handle a borrow when there are no bits left to borrow form
    https://stackoverflow.com/qu­estions/68629408/in-binary-subtraction-how-do-you-handle-a-borrow-when-there-are-no-bits-left-to
38. Is there any legitimate use for Intel's RDRAND?
    https://stackoverflow.com/qu­estions/26771329/is-there-any-legitimate-use-for-intels-rdrand
39. Intel® Digital Random Number Generator (DRNG) Software Implementation Guide
    https://www.intel.com/con­tent/www/us/en/developer/ar­ticles/guide/intel-digital-random-number-generator-drng-software-implementation-guide.html
40. Hardware random number generator
    https://en.wikipedia.org/wi­ki/Hardware_random_number_ge­nerator
41. Random number generator attack
    https://en.wikipedia.org/wi­ki/Random_number_generator_at­tack
42. random_r.c (Glibc)
    https://github.com/lattera/glib­c/blob/master/stdlib/random_r­.c#L341
43. Xorshift
    https://en.wikipedia.org/wi­ki/Xorshift