Funkce vestavěné v GCC pro provádění nízkoúrovňových bitových operací a rotací (dokončení)

Obsah

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

2. Zjištění minimálního počtu bitů nutných pro uložení hodnoty

3. Překlad vestavěné funkce __builtin_stdc_bit_width do strojového kódu

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

5. Překlad volání funkce __builtin_stdc_bit_width pro 32bitové ARMy

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

7. Bitová šířka pro hodnoty se znaménkem

8. Funkce __builtin_stdc_bit_floor

9. Překlad vestavěné funkce __builtin_stdc_bit_floor do strojového kódu

10. Překlad volání funkce __builtin_stdc_bit_floor pro platformu x86–64

11. Překlad volání funkce __builtin_stdc_bit_floor pro 32bitové ARMy

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

13. Funkce __builtin_stdc_bit_ceil

14. Překlad vestavěné funkce __builtin_stdc_bit_ceil do strojového kódu

15. Překlad volání funkce __builtin_stdc_bit_ceil pro platformu x86–64

16. Překlad volání funkce __builtin_stdc_bit_ceil pro 32bitové ARMy

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

18. Závěr

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í (dokončení)

V závěrečném článku o vestavěných funkcích (builtins) určených pro nízkoúrovňové operace, které vývojářům nabízí překladač GCC, si popíšeme funkce, které na základě předané hodnoty dokážou zjistit minimální počet bitů potřebných pro uložení této hodnoty, funkce vracející nejbližší nižší nebo vyšší mocninu dvojky k zadané hodnotě atd. Na rozdíl od podpory výpočtů s přenosem (carry) nebo operací pro bitové rotace se v tomto případě jedná o méně často používané operace, ovšem i tak je vhodné alespoň vědět o jejich existenci.

Pro připomenutí si ještě naposledy vypišme vestavěné funkce, které jsme si již popsali nebo které si popíšeme dnes:

bool __builtin_add_overflow(type1 a, type2 b, type3 *res)
bool __builtin_sadd_overflow(int a, int b, int *res)
bool __builtin_saddl_overflow(long int a, long int b, long int *res)
bool __builtin_saddll_overflow(long long int a, long long int b, long long int *res)
bool __builtin_uadd_overflow(unsigned int a, unsigned int b, unsigned int *res)
bool __builtin_uaddl_overflow(unsigned long int a, unsigned long int b, unsigned long int *res)
bool __builtin_uaddll_overflow(unsigned long long int a, unsigned long long int b, unsigned long long int *res)
bool __builtin_sub_overflow(type1 a, type2 b, type3 *res)
bool __builtin_ssub_overflow(int a, int b, int *res)
bool __builtin_ssubl_overflow(long int a, long int b, long int *res)
bool __builtin_ssubll_overflow(long long int a, long long int b, long long int *res)
bool __builtin_usub_overflow(unsigned int a, unsigned int b, unsigned int *res)
bool __builtin_usubl_overflow(unsigned long int a, unsigned long int b, unsigned long int *res)
bool __builtin_usubll_overflow(unsigned long long int a, unsigned long long int b, unsigned long long int *res)
bool __builtin_mul_overflow(type1 a, type2 b, type3 *res)
bool __builtin_smul_overflow(int a, int b, int *res)
bool __builtin_smull_overflow(long int a, long int b, long int *res)
bool __builtin_smulll_overflow(long long int a, long long int b, long long int *res)
bool __builtin_umul_overflow(unsigned int a, unsigned int b, unsigned int *res)
bool __builtin_umull_overflow(unsigned long int a, unsigned long int b, unsigned long int *res)
bool __builtin_umulll_overflow(unsigned long long int a, unsigned long long int b, unsigned long long int *res)
bool __builtin_add_overflow_p(type1 a, type2 b, type3 c)
bool __builtin_sub_overflow_p(type1 a, type2 b, type3 c)
bool __builtin_mul_overflow_p(type1 a, type2 b, type3 c)
unsigned int __builtin_addc(unsigned int a, unsigned int b, unsigned int carry_in, unsigned int *carry_out)
unsigned long int __builtin_addcl(unsigned long int a, unsigned long int b, unsigned int carry_in, unsigned long int *carry_out)
unsigned long long int __builtin_addcll(unsigned long long int a, unsigned long long int b, unsigned long long int carry_in, unsigned long long int *carry_out)
unsigned int __builtin_subc(unsigned int a, unsigned int b, unsigned int carry_in, unsigned int *carry_out)
unsigned long int __builtin_subcl(unsigned long int a, unsigned long int b, unsigned int carry_in, unsigned long int *carry_out)
unsigned long long int __builtin_subcll(unsigned long long int a, unsigned long long int b, unsigned long long int carry_in, unsigned long long int *carry_out)
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)
type1 __builtin_stdc_rotate_left(type1 arg1, type2 arg2)
type1 __builtin_stdc_rotate_right(type1 arg1, type2 arg2)

Funkce, které jsme si doposud nepopsali:

int __builtin_clrsb(int x)
int __builtin_popcount(unsigned int x)
int __builtin_clrsbl(long)
int __builtin_popcountl(unsigned long)
int __builtin_clrsbll(long long)
int __builtin_popcountll(unsigned long long)
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_has_single_bit(type arg)

2. Zjištění minimálního počtu bitů nutných pro uložení hodnoty

První vestavěnou funkcí, s níž se v dnešním článku seznámíme, je funkce nazvaná __builtin_stdc_bit_width. Tato funkce akceptuje libovolnou celočíselnou hodnotu bez znaménka (unsigned) a vrátí nejmenší počet bitů nutných pro uložení takové hodnoty. Podívejme se na jednoduchý příklad, a to pro vstupní hodnoty 7 a 8:

vstup   binární podoba  počet bitů
----------------------------------
7       00000111        3
8       00001000        4

Tuto funkci si můžeme snadno otestovat po překladu a spuštění dnešního prvního demonstračního příkladu:

#include <stdio.h>
#include <stdint.h>
 
uint8_t bit_width_8bit(uint8_t x) {
    uint8_t z;
    z = __builtin_stdc_bit_width(x);
    return z;
}
 
void print_bin(uint8_t x) {
    int i;
 
    for (i = 7; i >= 0; i--) {
        printf("%d", (x >> i) & 1);
    }
}
 
void test_bit_width(uint8_t x) {
    printf("%u \t", x);
    print_bin(x);
    printf("\t%d\n", bit_width_8bit(x));
}
 
int main(void) {
    uint8_t i;
 
    for (i=0; i<=17; i++) {
        test_bit_width(i);
    }
 
    test_bit_width(0xff);
}

Výsledky by měly vypadat následovně. Povšimněte si, že jsme skutečně získali hodnoty podle očekávaní, tj. nejmenší počet bitů nutných pro uložení vstupní hodnoty:

0       00000000        0
1       00000001        1
2       00000010        2
3       00000011        2
4       00000100        3
5       00000101        3
6       00000110        3
7       00000111        3
8       00001000        4
9       00001001        4
10      00001010        4
11      00001011        4
12      00001100        4
13      00001101        4
14      00001110        4
15      00001111        4
16      00010000        5
17      00010001        5
255     11111111        8

3. Překlad vestavěné funkce __builtin_stdc_bit_width do strojového kódu

V první třetině dnešního článku si ukážeme, jakým způsobem se vlastně vestavěná funkce __builtin_stdc_bit_width přeloží do strojového kódu sledovaných mikroprocesorových platforem, tj. x86–64, ARM32 (ARMv7) a AArch64. Překládat budeme následující jednoduchý zdrojový kód, ve kterém se vestavěná funkce volá s různými typy operandů; ovšem vždy se jedná o bezznaménkové (unsigned) typy:

#include <stdint.h>
 
int bit_width_8bit(uint8_t x) {
    return __builtin_stdc_bit_width(x);
}
 
int bit_width_16bit(uint16_t x) {
    return __builtin_stdc_bit_width(x);
}
 
int bit_width_32bit(uint32_t x) {
    return __builtin_stdc_bit_width(x);
}
 
int bit_width_64bit(uint64_t x) {
    return __builtin_stdc_bit_width(x);
}

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

Na platformě x86–64 je výpočet prováděný vestavěnou funkcí __builtin_stdc_bit_width postaven na instrukci BSR (Bit Scan Reverse), se kterou jsme se již seznámili v předchozích článcích. Připomeňme si, že tato instrukce nalezne index nejvyššího nenulového bitu. V případě, že takový bit neexistuje, tj. když jsou všechny bity nulové, nastaví se příznak Zero Flag, který je možné testovat. A z indexu nejvyššího nenulového bitu lze přímo odvodit bitovou šířku operandu.

Pro osmibitové a šestnáctibitové hodnoty je nejdříve provedeno maskování na nejvyšší možnou osmibitovou resp. šestnáctibitovou hodnotu (bez znaménka). Následně je otestováno, jestli je vstup nulový. Pokud tomu tak je, vrátí se přímo nula (registr EAX), jinak se vrátí výsledek volání výše zmíněné instrukce BSR zvýšený o jedničku:

bit_width_8bit:
        xor     eax, eax
        and     edi, 255
        je      .L1
        bsr     edi, edi
        lea     eax, [rdi+1]
.L1:
        ret
 
bit_width_16bit:
        xor     eax, eax
        and     edi, 65535
        je      .L6
        bsr     edi, edi
        lea     eax, [rdi+1]
.L6:
        ret

Pro 32bitové a 64bitové vstupy je výpočet nepatrně odlišný, protože se neprovádí maskování, ale ihned se zavolá instrukce BSR. K vypočtené hodnotě je přičtena jednička, ovšem pokud je vstup nulový, vrátí se vždy nula (TEST následovaný CMOVE). Jedná se tedy pouze o stejný, ovšem jinak strukturovaný výpočet:

bit_width_32bit:
        bsr     eax, edi
        xor     edx, edx
        add     eax, 1
        test    edi, edi
        cmove   eax, edx
        ret
 
bit_width_64bit:
        bsr     rax, rdi
        xor     edx, edx
        add     eax, 1
        test    rdi, rdi
        cmove   eax, edx
        ret

5. Překlad volání funkce __builtin_stdc_bit_width pro 32bitové ARMy

Na 32bitových ARMech (v7) se namísto specializované instrukce volá subrutina nazvaná __clzsi2. Výsledek se odečte od konstanty 32 nebo 64 (podle bitové šířky) a rozdíl je z kódu vrácen zpět volající funkci. Všechny důležité výpočty jsou tedy v tomto případě „schovány“ ve zmíněné subrutině __clzsi2:

bit_width_8bit:
        subs    r3, r0, #0
        beq     .L3
        push    {r4, lr}
        bl      __clzsi2
        pop     {r4, lr}
        rsb     r0, r0, #32
        bx      lr
.L3:
        mov     r0, r3
        bx      lr
 
bit_width_16bit:
        subs    r3, r0, #0
        beq     .L11
        push    {r4, lr}
        bl      __clzsi2
        pop     {r4, lr}
        rsb     r0, r0, #32
        bx      lr
.L11:
        mov     r0, r3
        bx      lr
 
bit_width_32bit:
        subs    r3, r0, #0
        beq     .L18
        push    {r4, lr}
        bl      __clzsi2
        pop     {r4, lr}
        rsb     r0, r0, #32
        bx      lr
.L18:
        mov     r0, r3
        bx      lr
 
bit_width_64bit:
        orrs    r3, r0, r1
        beq     .L25
        push    {r4, lr}
        bl      __clzdi2
        pop     {r4, lr}
        rsb     r0, r0, #64
        bx      lr
.L25:
        mov     r0, #0
        bx      lr

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

V případě překladu pro architekturu AArch64 můžeme vidět volání instrukce CLZ, která získá délku sekvence nulových bitů, přičemž se začíná od bitu nejvyššího. Vypočtenou hodnotu odečteme od konstanty 32 nebo 64 (podle šířky vstupního operandu) a relativně snadno tak získáme potřebný počet bitů. Navíc se provádí úpravy výsledků pro osmibitové nebo šestnáctibitové vstupy (u 32bitových a 64bitových variant to není nutné):

bit_width_8bit:
        ands    w0, w0, 255
        mov     w1, 32
        clz     w2, w0
        sub     w0, w1, w2
        csel    w0, w0, wzr, ne
        ret
 
bit_width_16bit:
        ands    w0, w0, 65535
        mov     w1, 32
        clz     w2, w0
        sub     w0, w1, w2
        csel    w0, w0, wzr, ne
        ret
 
bit_width_32bit:
        clz     w0, w0
        mov     w1, 32
        sub     w0, w1, w0
        ret
 
bit_width_64bit:
        clz     x0, x0
        mov     w1, 64
        sub     w0, w1, w0
        ret

7. Bitová šířka pro hodnoty se znaménkem

Vzhledem k poněkud složité (resp. spíše nejasné) sémantice není možné vestavěné funkci __builtin_stdc_bit_width předat hodnotu se znaménkem. To si ostatně můžeme velmi snadno otestovat pokusem o překlad tohoto zdrojového kódu:

#include <stdint.h>
 
int bit_width_8bit(int8_t x) {
    return __builtin_stdc_bit_width(x);
}
 
int bit_width_16bit(int16_t x) {
    return __builtin_stdc_bit_width(x);
}
 
int bit_width_32bit(int32_t x) {
    return __builtin_stdc_bit_width(x);
}
 
int bit_width_64bit(int64_t x) {
    return __builtin_stdc_bit_width(x);
}

Překladač GCC v takovém případě bude detekovat chyby, protože předávané hodnoty musí být bez znaménka (unsigned):

bit_width_signed.c: In function ‘bit_width_8bit’:
bit_width_signed.c:4:12: error: argument 1 in call to function ‘__builtin_stdc_bit_width’ has signed type
    4 |     return __builtin_stdc_bit_width(x);
      |            ^~~~~~~~~~~~~~~~~~~~~~~~
bit_width_signed.c: In function ‘bit_width_16bit’:
bit_width_signed.c:8:12: error: argument 1 in call to function ‘__builtin_stdc_bit_width’ has signed type
    8 |     return __builtin_stdc_bit_width(x);
      |            ^~~~~~~~~~~~~~~~~~~~~~~~
bit_width_signed.c: In function ‘bit_width_32bit’:
bit_width_signed.c:12:12: error: argument 1 in call to function ‘__builtin_stdc_bit_width’ has signed type
   12 |     return __builtin_stdc_bit_width(x);
      |            ^~~~~~~~~~~~~~~~~~~~~~~~
bit_width_signed.c: In function ‘bit_width_64bit’:
bit_width_signed.c:16:12: error: argument 1 in call to function ‘__builtin_stdc_bit_width’ has signed type
   16 |     return __builtin_stdc_bit_width(x);
      |            ^~~~~~~~~~~~~~~~~~~~~~~~

8. Funkce __builtin_stdc_bit_floor

Předposlední vestavěná funkce, o které se zmíníme, se jmenuje __builtin_stdc_bit_floor. Tato funkce opět jako svůj parametr akceptuje celočíselnou hodnotu a vrací jinou celočíselnou hodnotu. Konkrétně se vrátí mocnina čísla 2, která je menší nebo rovna vstupu. Ukažme si chování této funkce na čtveřici vstupních hodnot 2, 3, 4 a 5:

vstup   binárně         výsledek
--------------------------------
2   00000010    2
3   00000011    2
4   00000100    4
5   00000101    4

Chování vestavěné funkce __builtin_stdc_bit_floor si otestujeme následujícím demonstračním příkladem:

#include <stdio.h>
#include <stdint.h>
 
uint8_t bit_floor_8bit(uint8_t x) {
    uint8_t z;
    z = __builtin_stdc_bit_floor(x);
    return z;
}
 
void print_bin(uint8_t x) {
    int i;
 
    for (i = 7; i >= 0; i--) {
        printf("%d", (x >> i) & 1);
    }
}
 
void test_bit_floor(uint8_t x) {
    printf("%u \t", x);
    print_bin(x);
    printf("\t%d\n", bit_floor_8bit(x));
}
 
int main(void) {
    uint8_t i;
 
    for (i=0; i<=17; i++) {
        test_bit_floor(i);
    }
 
    test_bit_floor(0xff);
}

Výsledkem by měla být tato tabulka, ze které je chování funkce patrné:

0   00000000    0
1   00000001    1
2   00000010    2
3   00000011    2
4   00000100    4
5   00000101    4
6   00000110    4
7   00000111    4
8   00001000    8
9   00001001    8
10  00001010    8
11  00001011    8
12  00001100    8
13  00001101    8
14  00001110    8
15  00001111    8
16  00010000    16
17  00010001    16
255     11111111    128

9. Překlad vestavěné funkce __builtin_stdc_bit_floor do strojového kódu

Opět se podíváme na to, jakým způsobem je vestavěná funkce nazvaná __builtin_stdc_bit_floor přeložena do strojového kódu, a to na platformách x86–64, ARM 32 (v7) i AArch64. Tuto funkci budeme opět volat s předáním operandů (bez znaménka) různých typů. Překládaný zdrojový kód vypadá následovně:

#include <stdint.h>
 
int bit_floor_8bit(uint8_t x) {
    return __builtin_stdc_bit_floor(x);
}
 
int bit_floor_16bit(uint16_t x) {
    return __builtin_stdc_bit_floor(x);
}
 
int bit_floor_32bit(uint32_t x) {
    return __builtin_stdc_bit_floor(x);
}
 
int bit_floor_64bit(uint64_t x) {
    return __builtin_stdc_bit_floor(x);
}

10. Překlad volání funkce __builtin_stdc_bit_floor pro platformu x86–64

Realizace funkce __builtin_stdc_bit_floor pro architekturu x86–64 a pro osmibitové i šestnáctibitové vstupní hodnoty vypadá následovně:

bit_floor_8bit:
        xor     eax, eax
        test    dil, dil
        je      .L1
        movzx   edi, dil
        mov     eax, 1
        bsr     ecx, edi
        sal     eax, cl
        movzx   eax, al
.L1:
        ret
 
bit_floor_16bit:
        xor     eax, eax
        test    di, di
        je      .L5
        movzx   edi, di
        mov     eax, 1
        bsr     ecx, edi
        sal     eax, cl
        movzx   eax, ax
.L5:
        ret

Tyto dvě implementace se od sebe odlišují pouze tím, zda se zpracovává hodnota v registru DIL nebo DI. Nejprve je proveden test na nulovou vstupní hodnotu (potom se vrací nula). V opačném případě se volá nám již známá instrukce BSR ukládající index jedničkového bitu do registru CL. Poté je jen provedena operace 1 << CL a vypočtený výsledek je vrácen:

Zajímavé je, že pro 32bitové a 64bitové hodnoty se namísto operace 1 << CL provádí bitový posun doprava; ovšem posunovaná hodnota je odlišná (jednička v nejvyšším bitu) a navíc se hodnota v registru ECX upravuje (negují se spodní bity):

bit_floor_32bit:
        mov     eax, edi
        test    edi, edi
        je      .L9
        bsr     ecx, edi
        mov     eax, -2147483648
        xor     ecx, 31
        shr     eax, cl
.L9:
        ret

bit_floor_64bit:
        xor     eax, eax
        test    rdi, rdi
        je      .L13
        movabs  rax, -9223372036854775808
        bsr     rcx, rdi
        xor     rcx, 63
        shr     rax, cl
.L13:
        ret

11. Překlad volání funkce __builtin_stdc_bit_floor pro 32bitové ARMy

Pro 32bitovou architekturu ARM je překlad zcela odlišný, protože se namísto instrukce pro vyhledání sekvence jedniček či nul volá subrutina __clzsi2. S výsledkem této subrutiny se již provádí podobné operace, z nichž nejdůležitější je bitový (logický) posun doleva resp. doprava (záleží na šířce vstupního operandu – v tomto ohledu není instrukční sada ortogonální):

bit_floor_8bit:
        subs    r3, r0, #0
        beq     .L3
        push    {r4, lr}
        bl      __clzsi2
        mov     r3, #1
        rsb     r0, r0, #31
        lsl     r0, r3, r0
        and     r0, r0, #255
        pop     {r4, lr}
        bx      lr
.L3:
        mov     r0, r3
        bx      lr
 
bit_floor_16bit:
        subs    r3, r0, #0
        beq     .L11
        push    {r4, lr}
        bl      __clzsi2
        mov     r3, #65536
        rsb     r0, r0, #31
        lsl     r0, r3, r0
        lsr     r0, r0, #16
        pop     {r4, lr}
        bx      lr
.L11:
        mov     r0, r3
        bx      lr
 
bit_floor_32bit:
        subs    r3, r0, #0
        beq     .L22
        push    {r4, lr}
        bl      __clzsi2
        mov     r3, #-2147483648
        lsr     r3, r3, r0
        mov     r0, r3
        pop     {r4, lr}
        bx      lr
.L22:
        mov     r0, r3
        bx      lr
 
bit_floor_64bit:
        orrs    r3, r0, r1
        beq     .L27
        push    {r4, lr}
        bl      __clzdi2
        mov     r1, #-2147483648
        rsb     r3, r0, #32
        sub     r2, r0, #32
        lsl     r0, r1, r3
        orr     r0, r0, r1, lsr r2
        pop     {r4, lr}
        bx      lr
.L27:
        mov     r0, #0
        bx      lr

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

Strojový kód určený pro architekturu mikroprocesorů AArch64 se do určité míry podobá kódu pro zcela odlišnou architekturu x86–64. Zpracování opět můžeme rozdělit na osmibitovou a šestnáctibitovou variantu na jedné straně a 32bitovou a 64bitovou variantu na straně druhé. Základ zpracování je postaven na instrukci CLZ (count leading zeros), operaci 1 << w3 (na x86–64 se používal jiný registr) a testu, zda není výsledkem nejvyšší možná hodnota (255/65535), potom by se totiž vracela nula:

bit_floor_8bit:
        ands    w0, w0, 255
        mov     w2, 31
        clz     w3, w0
        mov     w1, 1
        sub     w2, w2, w3
        lsl     w0, w1, w2
        and     w0, w0, 255
        csel    w0, w0, wzr, ne
        ret
 
bit_floor_16bit:
        ands    w0, w0, 65535
        mov     w2, 31
        clz     w3, w0
        mov     w1, 1
        sub     w2, w2, w3
        lsl     w0, w1, w2
        and     w0, w0, 65535
        csel    w0, w0, wzr, ne
        ret

U 32bitových a 64bitových vstupů můžeme vidět „trik“ s posunem hodnoty s nastaveným nejvyšším bitem doprava instrukcí LSR, tj. prakticky totožnou sekvenci instrukcí, jako u konkurenční architektury x86–64:

bit_floor_32bit:
        clz     w2, w0
        cmp     w0, 0
        mov     w1, -2147483648
        lsr     w1, w1, w2
        csel    w0, w1, w0, ne
        ret
 
bit_floor_64bit:
        clz     x2, x0
        cmp     x0, 0
        mov     x1, -9223372036854775808
        lsr     x0, x1, x2
        csel    w0, w0, wzr, ne
        ret

13. Funkce __builtin_stdc_bit_ceil

Poslední vestavěnou funkcí, kterou si v dnešním článku popíšeme, je funkce nazvaná __builtin_stdc_bit_ceil. Ta provádí podobný výpočet jako výše zmíněná funkce __builtin_stdc_bit_floor, ovšem s tím rozdílem, že je vrácena druhá mocnina dvojky, která je rovna nebo větší než zadaná hodnota. Opět se podívejme, jaké výsledky tato funkce vrátí pro vstupní hodnoty 2, 3, 4 a 5:

vstup   binárně         výsledek
--------------------------------
2   00000010    2
3   00000011    4
4   00000100    4
5   00000101    8

Chování této funkce si otestujeme tímto příkladem:

#include <stdio.h>
#include <stdint.h>
 
uint8_t bit_ceil_8bit(uint8_t x) {
    uint8_t z;
    z = __builtin_stdc_bit_ceil(x);
    return z;
}
 
void print_bin(uint8_t x) {
    int i;
 
    for (i = 7; i >= 0; i--) {
        printf("%d", (x >> i) & 1);
    }
}
 
void test_bit_ceil(uint8_t x) {
    printf("%u \t", x);
    print_bin(x);
    printf("\t%d\n", bit_ceil_8bit(x));
}
 
int main(void) {
    uint8_t i;
 
    for (i=0; i<=17; i++) {
        test_bit_ceil(i);
    }
 
    test_bit_ceil(0xff);
}

S výsledky:

0   00000000    1
1   00000001    1
2   00000010    2
3   00000011    4
4   00000100    4
5   00000101    8
6   00000110    8
7   00000111    8
8   00001000    8
9   00001001    16
10  00001010    16
11  00001011    16
12  00001100    16
13  00001101    16
14  00001110    16
15  00001111    16
16  00010000    16
17  00010001    32
255     11111111    0

14. Překlad vestavěné funkce __builtin_stdc_bit_ceil do strojového kódu

Pro otestování způsobu překladu vestavěné funkce __builtin_stdc_bit_ceil do strojového kódu testovaných platforem použijeme následující demonstrační příklad, který se (až na odlišnou volanou funkci) podobá příkladu, který jsme používali pro funkci __builtin_stdc_bit_floor:

#include <stdint.h>
 
int bit_ceil_8bit(uint8_t x) {
    return __builtin_stdc_bit_ceil(x);
}
 
int bit_ceil_16bit(uint16_t x) {
    return __builtin_stdc_bit_ceil(x);
}
 
int bit_ceil_32bit(uint32_t x) {
    return __builtin_stdc_bit_ceil(x);
}
 
int bit_ceil_64bit(uint64_t x) {
    return __builtin_stdc_bit_ceil(x);
}

15. Překlad volání funkce __builtin_stdc_bit_ceil pro platformu x86–64

Vzhledem k podobnosti funkcí __builtin_stdc_bit_ceil a __builtin_stdc_bit_floor pravděpodobně nebude větším překvapením, že i způsob překladu do strojového kódu bude velmi podobný, pouze některé vrácené hodnoty budou o jednu mocninu dvojky vyšší (1 pro nulový vstup atd.). Tomu odpovídá i nepatrně odlišný výsledný strojový kód, který je nyní pro všechny bitové šířky operandů prakticky totožný – BSR následovaná posunem doleva instrukcí SAL:

bit_ceil_8bit:
        mov     eax, 1
        cmp     dil, 1
        jbe     .L1
        lea     ecx, [rdi-1]
        mov     eax, 2
        movzx   ecx, cl
        bsr     ecx, ecx
        sal     eax, cl
        movzx   eax, al
.L1:
        ret
 
bit_ceil_16bit:
        mov     eax, 1
        cmp     di, 1
        jbe     .L5
        lea     ecx, [rdi-1]
        mov     eax, 2
        movzx   ecx, cx
        bsr     ecx, ecx
        sal     eax, cl
        movzx   eax, ax
.L5:
        ret
 
bit_ceil_32bit:
        mov     eax, 1
        cmp     edi, 1
        jbe     .L9
        sub     edi, 1
        mov     eax, 2
        bsr     ecx, edi
        sal     eax, cl
.L9:
        ret
 
bit_ceil_64bit:
        mov     eax, 1
        cmp     rdi, 1
        jbe     .L11
        sub     rdi, 1
        mov     eax, 2
        bsr     rcx, rdi
        sal     rax, cl
.L11:
        ret

16. Překlad volání funkce __builtin_stdc_bit_ceil pro 32bitové ARMy

Ani u překladu pro 32bitové ARMy nedojde k většímu překvapení – stále se volá subrutina __clzsi2 a výsledek se vypočte s využitím logického posunu doleva instrukcí LSL. Zásadněji se změnil jen kód určený pro vrácení jedničky pro nulový vstup:

bit_ceil_8bit:
        cmp     r0, #1
        bls     .L3
        sub     r0, r0, #1
        push    {r4, lr}
        and     r0, r0, #255
        bl      __clzsi2
        mov     r3, #2
        rsb     r0, r0, #31
        lsl     r0, r3, r0
        and     r0, r0, #255
        pop     {r4, lr}
        bx      lr
.L3:
        mov     r0, #1
        bx      lr
 
bit_ceil_16bit:
        cmp     r0, #1
        bls     .L11
        sub     r0, r0, #1
        lsl     r0, r0, #16
        push    {r4, lr}
        lsr     r0, r0, #16
        bl      __clzsi2
        mov     r3, #131072
        rsb     r0, r0, #31
        lsl     r0, r3, r0
        lsr     r0, r0, #16
        pop     {r4, lr}
        bx      lr
.L11:
        mov     r0, #1
        bx      lr
 
bit_ceil_32bit:
        cmp     r0, #1
        bls     .L18
        push    {r4, lr}
        sub     r0, r0, #1
        bl      __clzsi2
        mov     r3, #2
        rsb     r0, r0, #31
        lsl     r0, r3, r0
        pop     {r4, lr}
        bx      lr
.L18:
        mov     r0, #1
        bx      lr
 
bit_ceil_64bit:
        cmp     r0, #2
        sbcs    r3, r1, #0
        bcc     .L25
        subs    r0, r0, #1
        push    {r4, lr}
        sbc     r1, r1, #0
        bl      __clzdi2
        mov     r3, #2
        rsb     r0, r0, #63
        lsl     r0, r3, r0
        pop     {r4, lr}
        bx      lr
.L25:
        mov     r0, #1
        bx      lr

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

Na závěr si ještě ukážeme překlad volání funkce __builtin_stdc_bit_ceil do strojového kódu mikroprocesorové architektury AArch64. Překlad lze opět rozdělit do dvou kategorií. Pro osmibitové a šestnáctibitové vstupy je algoritmus založen na instrukci CLZ a logickém posunu doleva LSL. Pro nulový vstup se vrací jednička v samostatné větvi:

bit_ceil_8bit:
        and     w0, w0, 255
        cmp     w0, 1
        bls     .L3
        sub     w0, w0, #1
        mov     w2, 31
        and     w0, w0, 255
        mov     w1, 2
        clz     w0, w0
        sub     w0, w2, w0
        lsl     w0, w1, w0
        and     w0, w0, 255
        ret
.L3:
        mov     w0, 1
        ret
 
bit_ceil_16bit:
        and     w0, w0, 65535
        cmp     w0, 1
        bls     .L7
        sub     w0, w0, #1
        mov     w2, 31
        and     w0, w0, 65535
        mov     w1, 2
        clz     w0, w0
        sub     w0, w2, w0
        lsl     w0, w1, w0
        and     w0, w0, 65535
        ret
.L7:
        mov     w0, 1
        ret

Pro vstupní 32bitové a 64bitové hodnoty je postup poněkud odlišný. Základ zůstává stejný, ovšem dosazení jedničky lze realizovat podmíněnou instrukcí CSINC s předáním nulového registru WZR:

bit_ceil_32bit:
        subs    w2, w0, 1
        mov     w1, 31
        clz     w2, w2
        mov     w0, 2
        sub     w1, w1, w2
        lsl     w0, w0, w1
        csinc   w0, w0, wzr, hi
        ret

bit_ceil_64bit:
        subs    x2, x0, 1
        mov     w1, 63
        clz     x2, x2
        mov     x0, 2
        sub     w1, w1, w2
        lsl     x0, x0, x1
        csinc   w0, w0, wzr, hi
        ret

18. Závěr

Vestavěné funkce nabízené překladačem GCC mohou být pro některé typy aplikací velmi užitečné. Týká se to zejména podpory pro provádění celočíselných aritmetických operací s přenosem, který je možné detekovat a nějakým způsobem na něj reagovat. Užitečná je i podpora pro bitové rotace, která doplňuje standardní céčkovou podporu pro logické posuny. A konečně se jedná o funkce, které umožňují provádění výpočtů založených na výpočtu sekvence nul či naopak jedniček v bitové podobě vstupu. Těchto funkcí existuje celá řada; ostatně jsme jim věnovali jak předchozí článek, tak i celý článek dnešní.

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

Minule jsme si ukazovali některé příklady naprogramované v assembleru, konkrétně v NASMu pro Linux. Odkazy na tyto příklady naleznete v následující tabulce:

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
44. x86 instruction listings
    https://en.wikipedia.org/wi­ki/X86_instruction_listin­gs
45. Odd inline asm code generation with pointless memory operand
    https://github.com/llvm/llvm-project/issues/56789
46. Bit scanning equivalencies
    https://fgiesen.wordpress­.com/2013/10/18/bit-scanning-equivalencies/
47. BSF — Bit Scan Forward
    https://www.felixcloutier.com/x86/bsf
48. BSR — Bit Scan Reverse
    https://www.felixcloutier.com/x86/bsr
49. TZCNT — Count the Number of Trailing Zero Bits
    https://www.felixcloutier­.com/x86/tzcnt
50. LZCNT — Count the Number of Leading Zero Bits
    https://www.felixcloutier­.com/x86/lzcnt
51. Standard library header <stdbit.h> (C23)
    https://en.cppreference.com/w/c/he­ader/stdbit