Funkce vestavěné v GCC pro provádění nízkoúrovňových aritmetických operací

Obsah

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

2. Operace součtu s detekcí přetečení

3. Způsob překladu operací součtu do strojového kódu

4. Funkce __builtin_add_overflow se shodnými typy sčítanců i výsledku součtu

5. Překlad volání funkce __builtin_add_overflow na platformě x86–64

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

7. Překlad volání funkce __builtin_add_overflow pro 32bitové ARMy

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

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

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

11. Chování funkce __builtin_add_overflow, pokud mají sčítance i výsledek součtu odlišné typy

12. Demonstrační příklad: součet s využitím různých kombinací hodnot typu char a int

13. Operace rozdílu s detekcí přetečení

14. Demonstrační příklad: volání funkce __builtin_sub_overflow

15. Překlad volání funkce __builtin_sub_overflow na platformě x86–64

16. Operace součinu s detekcí přetečení

17. Vestavěné funkce realizující součet tří hodnot s přetečením a rozdíl tří hodnot s výpůjčkou

18. Demonstrační příklad: operace součtu tří hodnot a operace rozdílu tří hodnot

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 aritmetických operací

Na stránkách Roota jsme se již několikrát setkali s takzvanými builtins, což jsou funkce, typicky různé nízkoúrovňové funkce, podporované přímo překladači jazyka C. Dnes se zaměříme na známý překladač GCC, který obsahuje podporu pro relativně velké množství funkcí určených pro nízkoúrovňové aritmetické operace. Na tomto místě se vývojáři mohou ptát k čemu je to dobré, vždyť samotný jazyk C je dostatečně nízkoúrovňový. Ve skutečnosti tomu tak není (alespoň ne za všech okolností), protože například není zcela snadné realizovat základní aritmetické operace s detekcí přetečení výsledků. Navíc starší normy céčka explicitně říkají, že způsob realizace přetečení u celočíselných datových typů se znaménkem (signed) je nedefinovaná operace a překladač céčka se tedy může chovat prakticky libovolným způsobem – v závislosti na zvolené architektuře, přepínačích použitých při překladu, nebo (zcela jistě nejčastěji) podle fáze Měsíce nebo prostředí, ve kterém aplikace běží (korektně na testovacím prostředí, nekorektně u zákazníka).

U dále popsaných funkcí si ukážeme jak jejich základní způsoby volání, tak i způsob jejich překladu do strojového kódu. Mnohdy jsou totiž takové funkce přeložené do jediné strojové instrukce nebo relativně malého množství strojových instrukcí a využívají se zde příznakové bity (které nejsou přímo v C dostupné).

2. Operace součtu s detekcí přetečení

První skupinou funkcí vestavěných do překladače GCC, s níž se dnes seznámíme, jsou funkce určené pro provedení operace součtu, ovšem s tím, že je navíc korektně detekováno i přetečení výsledků, a to i pro hodnoty se znaménkem. Těchto funkcí existuje celkem sedm: tři funkce pro součet hodnot bez znaménka (unsigned), tři funkce pro součet hodnot se znaménkem (signed) a „univerzální“ funkce, jejíž parametry mohou být různého typu. Povšimněte si, že všech sedm funkcí má stejný počet i význam parametrů (které jsou ovšem různého typu) i stejný typ návratové hodnoty. Tato návratová hodnota pouze signalizuje, že došlo k přetečení; samotný výsledek součtu je vrácen (přes ukazatel, resp. referenci) v posledním předaném parametru:

3. Způsob překladu operací součtu do strojového kódu

V programovacím jazyce C je pochopitelně možné všechny funkce zmíněné v předchozí kapitole naprogramovat, i když v případě celočíselných typů se znaménkem je implementace (resp. přesněji řečeno přenositelná implementace) dosti komplikovaná. Ovšem výhoda vestavěných funkcí by měla být v tom, že je překladač jazyka C přeloží nebo by alespoň měl přeložit do optimálního a rychlého strojového kódu, protože na většině mikroprocesorových platforem je detekce přetečení většinou poměrně snadná až triviální (paradoxně v čistém C se jedná o mnohem složitější úlohu, protože nám zde chybí příslušné sémantické konstrukce). Typicky jsou vestavěné funkce přeloženy bez nutnosti použití CALL+RETURN; výsledkem bývá sekvence dvou až pěti strojových instrukcí. O tom, jakým způsobem je překlad prováděn, se přesvědčíme v demonstračních příkladech popsaných v navazujících kapitolách.

4. Funkce __builtin_add_overflow se shodnými typy sčítanců i výsledku součtu

V dnešním prvním demonstračním příkladu je několikrát volána vestavěná funkce nazvaná __builtin_add_overflow, které jsou předány parametry různého typu, konkrétně typu char, short, int a long, a to ve variantách se znaménkem a bez znaménka. V dalších kapitolách si ukážeme způsob překladu těchto funkcí:

#include <stdbool.h>
 
bool add_overflow_signed_char(signed char x, signed char y) {
    signed char z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_unsigned_char(unsigned char x, unsigned char y) {
    unsigned char z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_signed_short(signed short x, signed short y) {
    signed short z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_unsigned_short(unsigned short x, unsigned short y) {
    unsigned short z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_signed_int(signed int x, signed int y) {
    signed int z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_unsigned_int(unsigned int x, unsigned int y) {
    unsigned int z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_signed_long(signed long x, signed long y) {
    signed long z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_unsigned_long(unsigned long x, unsigned long y) {
    unsigned long z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}

5. Překlad obecné funkce __builtin_add_overflow na platformě x86–64

Nejprve se pokusíme první demonstrační příklad přeložit pro platformu x86–64. Zvolíme dvě strategie překladu: zcela bez optimalizací a naopak s povolenými optimalizacemi:

$ gcc -S -O0 -masm=intel add_overflow.c
 
$ gcc -S -O9 -masm=intel add_overflow.c

Kvůli použití přepínače -S bude výsledkem překladu nikoli objektový kód, ale kód v assembleru, který byl navíc pro účely článku očištěn od zbytečných informací a přepínačů.

V případě, že jsou optimalizace zakázány, budou funkce z demonstračního příkladu přeloženy do této (skutečně neoptimální) podoby:

add_overflow_signed_char:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     BYTE PTR [rbp-20], dl
        mov     BYTE PTR [rbp-24], al
        movsx   edx, BYTE PTR [rbp-20]
        movsx   eax, BYTE PTR [rbp-24]
        mov     ecx, 0
        add     al, dl
        jno     .L2
        mov     ecx, 1
.L2:
        mov     BYTE PTR [rbp-2], al
        mov     eax, ecx
        and     eax, 1
        mov     BYTE PTR [rbp-1], al
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_unsigned_char:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     BYTE PTR [rbp-20], dl
        mov     BYTE PTR [rbp-24], al
        movzx   eax, BYTE PTR [rbp-20]
        movzx   edx, BYTE PTR [rbp-24]
        mov     ecx, 0
        add     al, dl
        jnc     .L6
        mov     ecx, 1
.L6:
        mov     BYTE PTR [rbp-2], al
        mov     eax, ecx
        and     eax, 1
        mov     BYTE PTR [rbp-1], al
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_signed_short:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     WORD PTR [rbp-20], dx
        mov     WORD PTR [rbp-24], ax
        movsx   edx, WORD PTR [rbp-20]
        movsx   eax, WORD PTR [rbp-24]
        mov     ecx, 0
        add     ax, dx
        jno     .L10
        mov     ecx, 1
.L10:
        mov     WORD PTR [rbp-4], ax
        mov     eax, ecx
        mov     BYTE PTR [rbp-1], al
        and     BYTE PTR [rbp-1], 1
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_unsigned_short:
        push    rbp
        mov     rbp, rsp
        mov     edx, edi
        mov     eax, esi
        mov     WORD PTR [rbp-20], dx
        mov     WORD PTR [rbp-24], ax
        movzx   eax, WORD PTR [rbp-20]
        movzx   edx, WORD PTR [rbp-24]
        mov     ecx, 0
        add     ax, dx
        jnc     .L14
        mov     ecx, 1
.L14:
        mov     WORD PTR [rbp-4], ax
        mov     eax, ecx
        mov     BYTE PTR [rbp-1], al
        and     BYTE PTR [rbp-1], 1
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_signed_int:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        mov     DWORD PTR [rbp-24], esi
        mov     ecx, 0
        mov     edx, DWORD PTR [rbp-20]
        mov     eax, DWORD PTR [rbp-24]
        add     eax, edx
        jno     .L18
        mov     ecx, 1
.L18:
        mov     DWORD PTR [rbp-8], eax
        mov     eax, ecx
        mov     BYTE PTR [rbp-1], al
        and     BYTE PTR [rbp-1], 1
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_unsigned_int:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        mov     DWORD PTR [rbp-24], esi
        mov     ecx, 0
        mov     eax, DWORD PTR [rbp-20]
        mov     edx, DWORD PTR [rbp-24]
        add     eax, edx
        jnc     .L22
        mov     ecx, 1
.L22:
        mov     DWORD PTR [rbp-8], eax
        mov     eax, ecx
        mov     BYTE PTR [rbp-1], al
        and     BYTE PTR [rbp-1], 1
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_signed_long:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     QWORD PTR [rbp-32], rsi
        mov     ecx, 0
        mov     rdx, QWORD PTR [rbp-24]
        mov     rax, QWORD PTR [rbp-32]
        add     rax, rdx
        jno     .L26
        mov     ecx, 1
.L26:
        mov     QWORD PTR [rbp-16], rax
        mov     rax, rcx
        mov     BYTE PTR [rbp-1], al
        and     BYTE PTR [rbp-1], 1
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret
 
add_overflow_unsigned_long:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     QWORD PTR [rbp-32], rsi
        mov     ecx, 0
        mov     rax, QWORD PTR [rbp-24]
        mov     rdx, QWORD PTR [rbp-32]
        add     rax, rdx
        jnc     .L30
        mov     ecx, 1
.L30:
        mov     QWORD PTR [rbp-16], rax
        mov     rax, rcx
        mov     BYTE PTR [rbp-1], al
        and     BYTE PTR [rbp-1], 1
        movzx   eax, BYTE PTR [rbp-1]
        pop     rbp
 
        ret

Překlad s povolenými optimalizacemi dopadne o mnoho lépe:

add_overflow_signed_char:
        add     dil, sil
        seto    al
        ret
 
add_overflow_unsigned_char:
        add     sil, dil
        setc    al
        ret
 
add_overflow_signed_short:
        add     di, si
        seto    al
        ret
 
add_overflow_unsigned_short:
        add     si, di
        setc    al
        ret
 
add_overflow_signed_int:
        add     edi, esi
        seto    al
        ret
 
add_overflow_unsigned_int:
        add     edi, esi
        setc    al
        ret
 
add_overflow_signed_long:
        add     rdi, rsi
        seto    al
        ret
 
add_overflow_unsigned_long:
        add     rdi, rsi
        setc    al
        ret

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

Popišme si ve stručnosti, jaké instrukce jsou vlastně v přeloženém strojovém kódu použity. U neoptimalizovaného kódu nalezneme tuto sekvenci instrukcí:

add_overflow_signed_char:
        ...
        add     al, dl
        jno     .L2
        ...
 
add_overflow_unsigned_char:
        ...
        add     al, dl
        jnc     .L6
        ...
 
add_overflow_signed_short:
        ...
        add     ax, dx
        jno     .L10
        ...
 
add_overflow_unsigned_short:
        ...
        add     ax, dx
        jnc     .L14
        ...
 
add_overflow_signed_int:
        ...
        add     eax, edx
        jno     .L18
        ...
 
add_overflow_unsigned_int:
        ...
        add     eax, edx
        jnc     .L22
        ...

Vzor je tedy vždy stejný – nejdříve se provede běžný součet založený na instrukci ADD, pokaždé pochopitelně s různými typy registrů (8 bitů, 16 bitů, 32 bitů). A po součtu následuje rozeskok realizovaný instrukcí JNO (Jump if Not Overflow) nebo JNC (Jump if Not Carry). Při realizaci podmíněného rozeskoku se tedy testuje příznakový bit overflow u hodnot se znaménkem nebo příznakový bit carry u hodnot bez znaménka. Naprosto stejnou operaci by provedl i programátor v assembleru.

Při překladu se zapnutými optimalizacemi se ovšem žádný rozeskok neprovádí, protože zde ihned za instrukcí součtu následuje instrukce seto (součet hodnot se znaménkem) nebo setc (součet hodnot bez znaménka). Instrukce SETcc přitom na platformě x86–64 existuje ve více variantách, ovšem provádí vždy stejnou operaci – do cílového registru nebo místa paměti dosadí hodnotu 1, pokud je splněna zvolená podmínka. V opačném případě dosadí hodnotu 0:

7. Překlad obecné funkce __builtin_add_overflow 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_add_overflow, nyní ovšem pro 32bitovou architekturu ARM (minimálně ARMv7, což je dnes již naprostý standard):

add_overflow_signed_char:
        add     r0, r0, r1
        sxtb    r3, r0
        subs    r0, r0, r3
        it      ne
        movne   r0, #1
        bx      lr
 
add_overflow_unsigned_char:
        add     r0, r0, r1
        lsrs    r0, r0, #8
        bx      lr
 
add_overflow_signed_short:
        add     r0, r0, r1
        sxth    r3, r0
        subs    r0, r0, r3
        it      ne
        movne   r0, #1
        bx      lr
 
add_overflow_unsigned_short:
        add     r0, r0, r1
        lsrs    r0, r0, #16
        bx      lr
 
add_overflow_signed_int:
        adds    r0, r0, r1
        ite     vs
        movvs   r0, #1
        movvc   r0, #0
        bx      lr
 
add_overflow_unsigned_int:
        cmn     r0, r1
        ite     cs
        movcs   r0, #1
        movcc   r0, #0
        bx      lr
 
add_overflow_signed_long:
        adds    r0, r0, r1
        ite     vs
        movvs   r0, #1
        movvc   r0, #0
        bx      lr
 
add_overflow_unsigned_long:
        cmn     r0, r1
        ite     cs
        movcs   r0, #1
        movcc   r0, #0
        bx      lr

Pro operace s osmibitovými hodnotami bez znaménka se ihned po operaci součtu volá instrukce LSRS neboli logický posun doprava o zadaný počet bitů s nastavením příznaků. Ovšem důležitější je, že po posunu o osm resp. 16 bitů doprava bude v registru RO uložena skutečně jen hodnota 0 nebo 1, tedy příznak přetečení:

add     r0, r0, r1                add     r0, r0, r1
lsrs    r0, r0, #8                lsrs    r0, r0, #16
bx      lr                        bx      lr

Nejsložitější je situace u osmibitových a 16bitových hodnot se znaménkem, které vyžadují konverzi pomocí SXTB resp. SXTH, provedení operace rozdílu a následný rozeskok realizovaný opět pomocí prefixu IT.

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

Pokud se podíváme na strojový kód uvedený v předchozí kapitole zjistíme, že se většinou šablonovitě provádí tato sekvence operací:

     add ...
     nastavení registru r0 na 0 nebo 1
     bx lr

První instrukce slouží k získání informace o přetečení, dalších několik instrukcí vloží do registru R0 hodnotu 0 nebo 1 na základě toho, zda k přetečení došlo či nikoli a poslední instrukce BX (Branch and eXchange) slouží k návratu z funkce s tím, že výsledek bude uložen právě v registru R0.

Na platformě ARM32 je zajímavé, že je na rozdíl od x86–64 orientována převážně na provádění 32bitových operací, takže operace s osmibitovými operandy je většinou nutné řešit specifickými způsoby, typicky jejich konverzí na plných 32 bitů.

Podívejme se nejdříve na řešení použité u operací s typy int a long (bez rozdílu), a to jak se znaménkem, tak i bez znaménka. Je zde využit instrukční prefix IT Tento prefix může být aplikován na jednu až čtyři instrukce následující za prefixem. Ihned za prefixem IT se (bez mezery) udává, zda má být daná instrukce provedena při splnění podmínky (T – then) či naopak při jejím nesplnění (E – else). U první instrukce je automaticky předpokládáno T, tudíž se uvádí maximálně tři kombinace znaků T/E. Samozřejmě je taktéž nutné zapsat i testovanou podmínku – může se jednat o kódy používané jak u podmíněných skoků, tak i v podmínkových bitech.

V našem konkrétním případě je vždy využit prefix ITE a testuje se buď nastavení příznaku Carry nebo Overflow. Pro hodnoty bez znaménka:

cmn     r0, r1   ; porovnání s negovanou hodnotou
ite     cs       ; provedení třetí nebo čtvrté instrukce na základě příznaku Carry
movcs   r0, #1
movcc   r0, #0

Se znaménkem:

cmn     r0, r1   ; porovnání s negovanou hodnotou
ite     vs       ; provedení třetí nebo čtvrté instrukce na základě příznaku Overflow
movcs   r0, #1
movcc   r0, #0

9. Překlad obecné funkce __builtin_add_overflow 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ě:

add_overflow_signed_char:
        sxtb    w1, w1
        sxtb    w0, w0
        add     w2, w0, w1
        eon     w0, w0, w1
        eor     w1, w1, w2
        and     w0, w1, w0
        ubfx    w0, w0, 7, 1
        ret
 
add_overflow_unsigned_char:
        and     w0, w0, 255
        add     w1, w0, w1
        cmp     w0, w1, uxtb
        cset    w0, hi
        ret
 
add_overflow_signed_short:
        sxth    w1, w1
        sxth    w0, w0
        add     w2, w0, w1
        eon     w0, w0, w1
        eor     w1, w1, w2
        and     x0, x1, x0
        ubfx    x0, x0, 15, 1
        ret
 
add_overflow_unsigned_short:
        and     w0, w0, 65535
        add     w1, w0, w1
        cmp     w0, w1, uxth
        cset    w0, hi
        ret
 
add_overflow_signed_int:
        cmn     w0, w1
        cset    w0, vs
        ret
 
add_overflow_unsigned_int:
        adds    w0, w0, w1
        cset    w0, cs
        ret
 
add_overflow_signed_long:
        cmn     x0, x1
        cset    w0, vs
        ret
 
add_overflow_unsigned_long:
        cmn     x0, x1
        cset    w0, cs
        ret

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

Jak je z předchozího výpisu patrné, umožňuje instrukční sada AArch64 provedení odlišných operací, které jsou v případě 32bitových a 64bitových hodnot kratší a efektivnější, než je tomu na architektuře ARM32.

První zcela novou instrukcí uvedenou až na architektuře AArch64, je instrukce nazvaná CSET neboli Conditional Set. Tato instrukce vlastně přímo odpovídá požadavkům kladeným na datový typ boolean v mnoha programovacích jazycích, v nichž je hodnota true interně reprezentována jedničkou a hodnota false nulou. Tato instrukce existuje ve dvou variantách, přičemž první varianta pracuje s 32bitovým a druhá varianta s 64bitovým operandem):

CSET Wd, condition
CSET Xd, condition

Například:

CSET W3, EQ
CSET W4, MI
CSET X5, HI

Tato instrukce pracuje následujícím způsobem – v případě, že je podmínka zapsaná ve druhém operandu cond splněna, uloží se do cílového registru Wd či do registru Xd hodnota 1. Pokud podmínka naopak splněna není, uloží se do registru Wd či Xd hodnota 0:

cíl = condition ? 1 : 0;

Ve skutečnosti se v případě CSET jedná o alias pro instrukci CSINC popsanou dále (podmínka ovšem musí být v tomto případě negována):

CSINC Wd, WZR, WZR, invert(condition)
CSINC Xd, XZR, XZR, invert(condition)

Díky tomu je možné přímo detekovat přetečení u 32bitových a 64bitových hodnot se znaménkem či bez znaménka. Šablona je stále stejná, liší se jen první instrukce (porovnání s opačným operandem nebo přímý součet s nastavením příznaků) a to, zda jsou použity 32bitové či 64bitové registry:

cmn     w0, w1        adds    w0, w0, w1        cmn     x0, x1        cmn     x0, x1
cset    w0, vs        cset    w0, cs            cset    w0, vs        cset    w0, cs
ret                   ret                       ret                   ret

U hodnot osmibitových a šestnáctibitových se opět objevuje nutnost použití konverzních instrukcí SXTB a SXTH, v případě 16bitových porovnání se znaménkem se navíc používá bitový posun UBFX.

sxtb    w1, w1         ; znaménkové rozšíření na 32 bitů
sxtb    w0, w0         ; znaménkové rozšíření na 32 bitů
add     w2, w0, w1     ; součet nyní 32bitových hodnot s uložením výsledku do registru W2
eon     w0, w0, w1     ; operace XOR s negovaným operandem (důležitý bude osmý bit zprava)
eor     w1, w1, w2     ; operace XOR (důležitý bude opět osmý bit zprava)
and     w0, w1, w0     ; bitový součin mezivýsledků předchozích operací
ubfx    w0, w0, 7, 1   ; bitový posun, zajímat nás bude osmý bit zprava
ret

11. Chování funkce __builtin_add_overflow, pokud mají sčítance i výsledek součtu odlišné typy

Ještě jednou se podívejme na hlavičku vestavěné funkce nazvané __builtin_add_overflow:

bool __builtin_add_overflow(type1 a, type2 b, type3 *res)

za povšimnutí stojí především fakt, že datové typy parametrů a, b a *res nejsou totožné, tedy nikde není řečeno, že se například ve všech třech případech musí jednat o unsigned char nebo o signed long. Je tomu vlastně přesně naopak, protože tato funkce akceptuje parametry libovolných celočíselných numerických typů (popř. v posledním případě odkaz/ukazatel na libovolný celočíselný numerický typ). To ovšem znamená, že například můžeme libovolným způsobem zkombinovat například typy unsigned char a unsigned int, což je ostatně ukázáno v dalším demonstračním příkladu, ve kterém je implementováno všech osm možných kombinací:

#include <stdbool.h>
 
bool add_overflow_ccc(unsigned char x, unsigned char y) {
    unsigned char z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_cci(unsigned char x, unsigned char y) {
    unsigned int z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_cic(unsigned char x, unsigned int y) {
    unsigned char z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_cii(unsigned char x, unsigned int y) {
    unsigned int z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_icc(unsigned char x, unsigned char y) {
    unsigned char z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_ici(unsigned int x, unsigned char y) {
    unsigned int z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_iic(unsigned int x, unsigned int y) {
    unsigned char z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}
 
bool add_overflow_iii(unsigned int x, unsigned int y) {
    unsigned int z;
    bool overflow = __builtin_add_overflow(x, y, &z);
    return overflow;
}

12. Demonstrační příklad: součet s využitím různých kombinací hodnot typu char a int

Podívejme se nyní na způsob překladu výše uvedeného demonstračního příkladu do strojového kódu pro platformu x86–64. Překlad je vlastně poměrně přímočarý, minimálně ve většině případů:

add_overflow_ccc:
        add     sil, dil
        setc    al
        ret
 
add_overflow_cci:
        xor     eax, eax
        ret
 
add_overflow_cic:
        mov     esi, esi
        movzx   edi, dil
        add     rdi, rsi
        test    rdi, -256
        setne   al
        ret
 
add_overflow_cii:
        movzx   edi, dil
        add     edi, esi
        setc    al
        ret
 
add_overflow_icc:
        add     sil, dil
        setc    al
        ret
 
add_overflow_ici:
        movzx   esi, sil
        add     esi, edi
        setc    al
        ret
 
add_overflow_iic:
        mov     esi, esi
        mov     edi, edi
        add     rdi, rsi
        test    rdi, -256
        setne   al
        ret
 
add_overflow_iii:
        add     edi, esi
        setc    al
        ret

Pojďme si jednotlivé případy blíže vysvětlit. Variantu char+char→char již známe, stejně jako variantu int+int→int, takže si je již nebudeme znovu popisovat (za povšimnutí stojí jen pojmenování osmibitových částí registrů SI a DI):

add_overflow_ccc:
        add     sil, dil
        setc    al
        ret
 
add_overflow_iii:
        add     edi, esi
        setc    al
        ret

Součet char+char→int nemůže nikdy vést k přetečení, a z tohoto důvodu se vždy vrací nula:

add_overflow_cci:
        xor     eax, eax
        ret

Varianty char+int→int a int+char→int jsou pochopitelně shodné, až na opačné pořadí vstupních operandů:

add_overflow_cii:
        movzx   edi, dil
        add     edi, esi
        setc    al
        ret
 
add_overflow_ici:
        movzx   esi, sil
        add     esi, edi
        setc    al
        ret

Varianta int+char→char musí kontrolovat přetečení, tedy příznakový bit Carry:

add_overflow_icc:
        add     sil, dil
        setc    al
        ret

Nejsložitější jsou varianty char+int→char a int+int→char, v nichž se porovnává výsledek s hodnotou –256 ve dvojkovém doplňku a na základě relace NE (not equal) se nastavuje výsledná hodnota:

add_overflow_cic:
        mov     esi, esi
        movzx   edi, dil
        add     rdi, rsi
        test    rdi, -256
        setne   al
        ret
 
add_overflow_iic:
        mov     esi, esi
        mov     edi, edi
        add     rdi, rsi
        test    rdi, -256
        setne   al
        ret

13. Operace rozdílu s detekcí přetečení

Ve druhé kapitole jsme si představili skupinu sedmi vestavěných funkcí určených pro provádění operací součtu s detekcí přetečení. Podobně – i kvůli zachování symetrie – existuje i sedm obdobných funkcí, které tentokrát své operandy odečtou a opět detekují stav, kdy dochází k přetečení. Jedná se o tyto funkce:

V praxi to například znamená, že funkce __builtin_ssub_overflow vrací pro operandy 2, 1 hodnotu 0 (bez přetečení) a pro operandy 1, 2 hodnotu 1 (s přetečením resp. lépe řečeno s výpůjčkou).

14. Demonstrační příklad: volání funkce __builtin_sub_overflow

Podobně, jako jsme si ukázali demonstrační příklad s voláním funkce __builtin_add_overflow, si ukážeme podobný příklad, který ovšem nyní bude volat funkci __builtin_sub_overflow s různými typy vstupních parametrů i s návratovým typem funkce:

#include <stdbool.h>
 
bool sub_overflow_signed_char(signed char x, signed char y) {
    signed char z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_unsigned_char(unsigned char x, unsigned char y) {
    unsigned char z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_signed_short(signed short x, signed short y) {
    signed short z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_unsigned_short(unsigned short x, unsigned short y) {
    unsigned short z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_signed_int(signed int x, signed int y) {
    signed int z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_unsigned_int(unsigned int x, unsigned int y) {
    unsigned int z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_signed_long(signed long x, signed long y) {
    signed long z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}
 
bool sub_overflow_unsigned_long(unsigned long x, unsigned long y) {
    unsigned long z;
    bool overflow = __builtin_sub_overflow(x, y, &z);
    return overflow;
}

15. Překlad volání funkce __builtin_sub_overflow na platformě x86–64

Překlad do strojového kódu opět využívá rozdíl popř. porovnání hodnot následovaný instrukcí SETcc s vhodně nastavenou podmínkou. Konkrétně se setkáme s těmito třemi variantami:

Strojový kód vypadá následovně:

sub_overflow_signed_char:
        sub     dil, sil
        seto    al
        ret
 
sub_overflow_unsigned_char:
        cmp     sil, dil
        seta    al
        ret
 
sub_overflow_signed_short:
        sub     di, si
        seto    al
        ret
 
sub_overflow_unsigned_short:
        cmp     si, di
        seta    al
        ret
 
sub_overflow_signed_int:
        sub     edi, esi
        seto    al
        ret
 
sub_overflow_unsigned_int:
        cmp     edi, esi
        setb    al
        ret
 
sub_overflow_signed_long:
        sub     rdi, rsi
        seto    al
        ret
 
sub_overflow_unsigned_long:
        cmp     rdi, rsi
        setb    al
        ret

16. Operace součinu s detekcí přetečení

Poslední sedmice vestavěných funkcí se dvěma vstupními operandy a detekcí přetečení se týká operace součinu, a to jak hodnot se znaménkem, tak i hodnot bez znaménka. Způsob pojmenování funkcí je stále zachován (s-signed, u-unsigned, l-long, ll-long long):

17. Vestavěné funkce realizující součet tří hodnot s přetečením a rozdíl tří hodnot s výpůjčkou

Posledních šest vestavěných funkcí, s nimiž se dnes alespoň ve stručnosti seznámíme, jsou funkce, které provádí součet či rozdíl tří hodnot, přičemž třetí hodnotou bývá příznak přetečení nebo výpůjčky z předchozí operace. Díky tomu je možné volání těchto funkcí zřetězit a implementovat tak aritmetické operace s velkým počtem bajtů (bitů), například 512 bitů atd.:

U operací součtu se sečtou všechny tři operandy, zatímco u operace rozdílu se provádí výpočet a-b-carry_in (poslední znaménko je důležité).

18. Demonstrační příklad: operace součtu tří hodnot a operace rozdílu tří hodnot

Výše popsané funkce, konkrétně funkce __builtin_addc a __builtin_subc, si otestujeme v následujícím demonstračním příkladu:

#include <limits.h>
#include <stdio.h>
 
void add_with_carry(unsigned int x, unsigned int y, unsigned int carry_in) {
    unsigned int carry_out;
    unsigned int result;
 
    result = __builtin_addc(x, y, carry_in, &carry_out);
    printf("%u + %u + %u = (%u)%u\n", x, y, carry_in, carry_out, result);
}
 
void sub_with_carry(unsigned int x, unsigned int y, unsigned int carry_in) {
    unsigned int carry_out;
    unsigned int result;
 
    result = __builtin_subc(x, y, carry_in, &carry_out);
    printf("%u - %u - %u = (%u)%u\n", x, y, carry_in, carry_out, result);
}
 
int main(void) {
    add_with_carry(0, 0, 0);
    add_with_carry(0, 0, 1);
    add_with_carry(1, 2, 0);
    add_with_carry(1, 2, 1);
 
    add_with_carry(UINT_MAX, 0, 0);
    add_with_carry(UINT_MAX, 0, 1);
    add_with_carry(UINT_MAX, 1, 0);
    add_with_carry(UINT_MAX, 1, 1);
 
    putchar('\n');
 
    sub_with_carry(0, 0, 0);
    sub_with_carry(0, 0, 1);
    sub_with_carry(2, 1, 0);
    sub_with_carry(2, 1, 1);
    sub_with_carry(2, 2, 0);
    sub_with_carry(2, 2, 1);
}

Nejprve sčítáme dvě malé hodnoty s přidáním příznaku přetečení (ten je nastaven na hodnotu 0 nebo 1). Výsledek je zobrazen formou (nový příznak přetečení)výsledek:

0 + 0 + 0 = (0)0
0 + 0 + 1 = (0)1
1 + 2 + 0 = (0)3
1 + 2 + 1 = (0)4

Předchozí čtyři součty pochopitelně nevedly k přetečení. Podívejme se nyní na mezní případy – přičtení nuly či jedničky k hodnotě UINT_MAX společně s přičtením příznaku přetečení. Ve třech posledních případech došlo podle očekávání k přetečení:

4294967295 + 0 + 0 = (0)4294967295
4294967295 + 0 + 1 = (1)0
4294967295 + 1 + 0 = (1)0
4294967295 + 1 + 1 = (1)1

Podobně si můžeme otestovat operaci rozdílu. Výsledky jsou pochopitelné – při přechodu přes hodnotu 0 je hlášeno přetečení (resp. přesněji řečeno výpůjčka):

0 - 0 - 0 = (0)0
0 - 0 - 1 = (1)4294967295
2 - 1 - 0 = (0)1
2 - 1 - 1 = (0)0
2 - 2 - 0 = (0)0
2 - 2 - 1 = (1)4294967295

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ář:

20. Odkazy na Internetu

1. GCC documentation: Extensions to the C Language Family
   https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions
2. GCC documentation: Using Vector Instructions through Built-in Functions
   https://gcc.gnu.org/online­docs/gcc/Vector-Extensions.html
3. SSE (Streaming SIMD Extentions)
   http://www.songho.ca/misc/sse/sse­.html
4. Timothy A. Chagnon: SSE and SSE2
   http://www.cs.drexel.edu/~tc365/mpi-wht/sse.pdf
5. CPU design (Wikipedia)
   http://en.wikipedia.org/wi­ki/CPU_design
6. GCC Compiler Intrinsics
   https://iq.opengenus.org/gcc-compiler-intrinsics/
7. Other Built-in Functions Provided by GCC
   https://gcc.gnu.org/online­docs/gcc/Other-Builtins.html
8. GCC: 6.60 Built-in Functions Specific to Particular Target Machines
   https://gcc.gnu.org/online­docs/gcc/Target-Builtins.html#Target-Builtins
9. Stránka projektu Compiler Explorer
   https://godbolt.org/
10. The LLVM Compiler Infrastructure
    https://llvm.org/
11. GCC, the GNU Compiler Collection
    https://gcc.gnu.org/
12. Clang
    https://clang.llvm.org/
13. Clang: Assembling a Complete Toolchain
    https://clang.llvm.org/doc­s/Toolchain.html
14. Integer overflow
    https://en.wikipedia.org/wi­ki/Integer_overflow
15. SETcc — Set Byte on Condition
    https://www.felixcloutier­.com/x86/setcc
16. The ARMv8 instruction sets
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/ch05s01.html
17. A64 Instruction Set
    https://developer.arm.com/pro­ducts/architecture/instruc­tion-sets/a64-instruction-set
18. Switching between the instruction sets
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/ch05s01.html
19. The A64 instruction set
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/ch05s01.html
20. Introduction to ARMv8 64-bit Architecture
    https://quequero.org/2014/04/in­troduction-to-arm-architecture/
21. Undefined behavior (Wikipedia)
    https://en.wikipedia.org/wi­ki/Undefined_behavior
22. Is signed integer overflow still undefined behavior in C++?
    https://stackoverflow.com/qu­estions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c
23. Allowing signed integer overflows in C/C++
    https://stackoverflow.com/qu­estions/4240748/allowing-signed-integer-overflows-in-c-c
24. SXTB, SXTH, SXTW
    https://www.scs.stanford.e­du/~zyedidia/arm64/sxtb_z_p_z­.html
25. BX, BXNS
    https://developer.arm.com/do­cumentation/100076/0200/a32-t32-instruction-set-reference/a32-and-t32-instructions/bx–bxns?lang=en
26. Carry and Borrow Principles
    https://www.tpub.com/neet­s/book13/53a.htm
27. 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