Obsah
1. Funkce vestavěné v GCC pro provádění nízkoúrovňových bitových operací a rotací (2. část)
2. Vyhledání prvního nebo posledního bitu se zadanou hodnotou vs. hledání sekvence stejných bitů
3. Důležitá odbočka: instrukce pro hledání bitů dostupné na architektuře x86–64
4. Základní použití instrukcí BSF a BSR
5. Realizace výpočtů pozice nejvyššího a nejnižšího bitu s jedničkovou hodnotou pro vstupy 0 až 16
6. Chování instrukcí BSF a BSR v případě, že je vstup nulový
9. Zjištění počtu nulových bitů na začátku nebo konci testované hodnoty
10. Příklad použití instrukce LZCNT
11. Příklad použití instrukce TZCNT
14. Volání vestavěné funkce __builtin_stdc_first_trailing_one
15. Překlad funkce __builtin_stdc_first_trailing_one do strojového kódu
17. Překlad pro platformu AArch64
18. Příloha: soubor Makefile pro překlad příkladů napsaných v assembleru NASM
19. Repositář s demonstračními příklady
1. Funkce vestavěné v GCC pro provádění nízkoúrovňových bitových operací a rotací (2. část)
Na předchozí článek o podpoře bitových rotací a výpočtu parity dnes navážeme. Ukážeme si některé další funkce vestavěné do GCC, které slouží pro realizaci nízkoúrovňových operací. Zaměříme se na funkce, které dokážou ve vstupní hodnotě nalézt délku sekvence nulových bitů, přičemž se tato sekvence hledá od nejvyššího bitu nebo naopak od bitu nejnižšího. Tyto operace se označují zkratkami clz (count leading zeros) a ctz (count trailing zeros). Existují ještě podobné operace ffs (find first set) a fls (find last set), které hledají index prvního nebo posledního bitu nastaveného na jedničku.
Ukážeme si, jak jsou tyto operace realizovány na architektuře x86–64, která k tomuto účelu nabízí hned čtyři instrukce.
Jen pro úplnost si vypišme všechny vestavěné funkce nabízené překladačem GCC, které jsou určeny pro provádění nízkoúrovňových operací. Velká část těchto funkcí realizuje operace popsané v úvodním odstavci:
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)
2. Vyhledání prvního nebo posledního bitu se zadanou hodnotou vs. hledání sekvence stejných bitů
První čtveřice vestavěných funkcí slouží pro nalezení prvního bitu se zadanou hodnotou (nula či jedna). Vyhledávání prvního bitu může začínat od nejnižšího či naopak od nejvyššího bitu a korektně se reaguje i na situace, kdy žádný z bitů nenabývá hledané hodnoty (tj. hledáme jedničkový bit v hodnotě 0×0000 či nulový bit v hodnotě 0×ffff):
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)
Další funkce hledají sekvenci bitů se stejnou hodnotou, a to opět od nejnižšího nebo od nejvyššího bitu. Opět se pochopitelně jedná o čtveřici funkcí:
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)
Existují ještě starší funkce s podobným významem, které ovšem nemají definovanou hodnotu v případě, že nebyl bit nalezen. A navíc se bity indexují od nuly a nikoli od jedničky:
int __builtin_ffs(int x) int __builtin_ffsl(long) int __builtin_ffsll(long long) int __builtin_clz(unsigned int x) int __builtin_clzl(unsigned long) int __builtin_clzll(unsigned long long) int __builtin_ctz(unsigned int x) int __builtin_ctzl(unsigned long) int __builtin_ctzll(unsigned long long)
Modernější varianty těchto funkcí jsou generické (první operand je jakéhokoli celočíselného typu) a jako druhý operand akceptují hodnotu vrácenou v případě, že bit s hledanou hodnotou není nalezen (můžeme například předat –1 atd.):
int __builtin_ffsg(...) int __builtin_clzg(...) int __builtin_ctzg(...)
3. Důležitá odbočka: instrukce pro hledání bitů dostupné na architektuře x86–64
Ještě předtím, než si ukážeme způsob použití a překladu vestavěných funkcí určených pro nalezení nulových či naopak nenulových bitů, je užitečné, poučné a zajímavé se podívat, jaké instrukce, které tuto činnost provádí, jsou vlastně k dispozici a jak se chovají. Zaměřme se na platformu x86–64, která vychází z platformy x86. Zde máme k dispozici hned čtyři instrukce, které mají odlišnou historii vzniku a taktéž (značně) odlišné chování:
| Instrukce | Operandy | Význam zkratky | Chování | Chování pro nulový vstup |
|---|---|---|---|---|
| BSF | 16bit, 32bit, 64bit | Bit Scan Forward | index prvního bitu nastaveného na jedničku (hledání od nejnižšího bitu) | ZF=1 |
| BSR | 16bit, 32bit, 64bit | Bit Scan Reverse | index prvního bitu nastaveného na jedničku (hledání od nejvyššího bitu) | ZF=1 |
| LZCNT | 16bit, 32bit, 64bit | Count Leading Zeros | délka sekvence nulových bitů (hledání od nejvyššího bitu) | CF=1 |
| TZCNT | 16bit, 32bit, 64bit | Count Trailing Zeros | délka sekvence nulových bitů (hledání od nejnižšího bitu) | CF=1 |
Délka sekvence nulových bitů ovšem neodpovídá indexu prvního jedničkového bitu, a to ani při hledání od nejnižšího bitu.
4. Základní použití instrukcí BSF a BSR
Vyzkoušejme si nyní, jaké výsledky získáme, pokud instrukcím BSF a BSR předáme bitovou hodnotu 0b01000010. Nezávisle na bitové šířce operandu (16 bitů, 32 bitů či 64 bitů) by měla instrukce BSF vrátit hodnotu 1, protože první jedničkový bit hledaný zprava (od nejnižšího bitu) má index roven jedné. Instrukce BSR vrátí hodnotu 6, protože první jedničkový bit hledaný zleva (od nejvyššího bitu) má index roven právě šesti.
Použití instrukce BSF:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
mov eax, 0x42 ; == 0b01000010
bsf edx, eax ; zjisteni indexu nejvyssiho nenuloveho bitu
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
exit ; ukonceni procesu
%include "hex2string.asm"
Výsledek:
00000001
Použití instrukce BSR:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
mov eax, 0x42 ; == 0b01000010
bsr edx, eax ; zjisteni indexu nejvyssiho nenuloveho bitu
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
exit ; ukonceni procesu
%include "hex2string.asm"
Výsledek:
00000006
5. Realizace výpočtů pozice nejvyššího a nejnižšího bitu s jedničkovou hodnotou pro vstupy 0 až 16
Předchozí demonstrační příklady si nepatrně upravíme, a to tak, že si necháme vypsat indexy bitů získaných instrukcemi BSF a BSR pro vstupní hodnoty 0 až 16, tj. binárně 0×00000000 až 0×00010000. Pro realizaci počítané smyčky použijeme pracovní registr ECX, který bude fungovat jako počitadlo a současně i vstup do instrukce BSF nebo BSR.
První z příkladů vypíše indexy nejnižšího jedničkového bitu:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
xor ecx, ecx ; pocitadlo
repeat:
bsf edx, ecx ; zjisteni indexu prvniho nenuloveho bitu
push ecx
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
pop ecx
inc ecx ; zvysit hodnotu pocitadla
cmp ecx, 17 ; test na konec pocitane smycky
jne repeat ; for-loop
exit ; ukonceni procesu
%include "hex2string.asm"
Druhý z příkladů vypíše indexy nejvyššího jedničkového bitu:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
xor ecx, ecx ; pocitadlo
repeat:
bsr edx, ecx ; zjisteni indexu nejvyssiho nenuloveho bitu
push ecx
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
pop ecx
inc ecx ; zvysit hodnotu pocitadla
cmp ecx, 17 ; test na konec pocitane smycky
jne repeat ; for-loop
exit ; ukonceni procesu
%include "hex2string.asm"
Výsledky obou příkladů (bez úprav):
00000000 00000000 00000001 00000000 00000002 00000000 00000001 00000000 00000003 00000000 00000001 00000000 00000002 00000000 00000001 00000000 00000004
00000000 00000000 00000001 00000001 00000002 00000002 00000002 00000002 00000003 00000003 00000003 00000003 00000003 00000003 00000003 00000003 00000004
Vysvětlení výsledků je patrné z následující tabulky:
| Dec | Bin | BSF | BSR |
|---|---|---|---|
| 0 | 00000 | 0 | 0 |
| 1 | 00001 | 0 | 0 |
| 2 | 00010 | 1 | 1 |
| 3 | 00011 | 0 | 1 |
| 4 | 00100 | 2 | 2 |
| 5 | 00101 | 0 | 2 |
| 6 | 00110 | 1 | 2 |
| 7 | 00111 | 0 | 2 |
| 8 | 01000 | 3 | 3 |
| 9 | 01001 | 0 | 3 |
| 10 | 01010 | 1 | 3 |
| 11 | 01011 | 0 | 3 |
| 12 | 01100 | 2 | 3 |
| 13 | 01101 | 0 | 3 |
| 14 | 01110 | 1 | 3 |
| 15 | 01111 | 0 | 3 |
| 16 | 10000 | 4 | 4 |
6. Chování instrukcí BSF a BSR v případě, že je vstup nulový
V předchozím textu jsme si řekli, že instrukce BSF a BSR hledají ve vstupním bajtu či vícebajtovém slovu první bit, který je nastavený na jedničku. Ovšem v tomto případě je nutné myslet i na mezní případ, kdy vstupní data obsahují jen nulové bity. Mikroprocesor tento stav pochopitelně kontroluje a pokud je vstup nulový, nastaví se příznak ZF (Zero Flag) a hodnota uložená (nebo neuložená) do výsledného registru není definována. To tedy znamená, že v praxi je prakticky vždy nutné testovat i hodnotu příznakového bitu ZF, a to například následujícím způsobem:
bsf edx, ecx ; zjisteni indexu prvniho nenuloveho bitu
jnz zf_reset ; vse v poradku, byl nalezen index bitu
zf_set: ; ZF je nastaven - vstupni operand byl nulovy
...
...
...
zf_reset:
...
...
...
7. Upravené příklady pro výpočty pozice nejvyššího a nejnižšího bitu s jedničkovou hodnotou pro vstupy 0 až 16
Oba demonstrační příklady z páté kapitoly upravíme takovým způsobem, že kromě výsledků získaných instrukcemi BSF a BSR vypíšeme i stav příznakového bitu ZF, což se provede s využitím podmíněného skoku.
Varianta demonstračního příkladu s instrukcí BSF vypadá následovně:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
zf_set_message:
db "ZF set "
zf_set_message_length equ $ - zf_set_message
zf_reset_message:
db "ZF reset "
zf_reset_message_length equ $ - zf_reset_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
xor ecx, ecx ; pocitadlo
repeat:
bsf edx, ecx ; zjisteni indexu prvniho nenuloveho bitu
push ecx
push edx
jnz zf_reset
zf_set:
print_string zf_set_message, zf_set_message_length
jmp continue
zf_reset:
print_string zf_reset_message, zf_reset_message_length
continue:
pop edx
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
pop ecx
inc ecx ; zvysit hodnotu pocitadla
cmp ecx, 17 ; test na konec pocitane smycky
jne repeat ; for-loop
exit ; ukonceni procesu
%include "hex2string.asm"
Varianta demonstračního příkladu s instrukcí BSR vypadá následovně:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
zf_set_message:
db "ZF set "
zf_set_message_length equ $ - zf_set_message
zf_reset_message:
db "ZF reset "
zf_reset_message_length equ $ - zf_reset_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
xor ecx, ecx ; pocitadlo
repeat:
bsr edx, ecx ; zjisteni indexu nejvyssiho nenuloveho bitu
push ecx
push edx
jnz zf_reset
zf_set:
print_string zf_set_message, zf_set_message_length
jmp continue
zf_reset:
print_string zf_reset_message, zf_reset_message_length
continue:
pop edx
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
pop ecx
inc ecx ; zvysit hodnotu pocitadla
cmp ecx, 17 ; test na konec pocitane smycky
jne repeat ; for-loop
exit ; ukonceni procesu
%include "hex2string.asm"
8. Vypočtené výsledky
Podívejme se nyní na vypočtené výsledky, které prozradí, za jakých okolností se nastavuje příznak ZF. První tabulka ukazuje výsledky získané instrukcí BSF. Podle očekávání je příznak ZF nastaven pouze v případě, že vstupem je nulová hodnota, přesněji řečeno hodnota, která má všechny své bity nulové a instrukce tedy nenašla žádný jedničkový bit:
ZF set 00000000 ZF reset 00000000 ZF reset 00000001 ZF reset 00000000 ZF reset 00000002 ZF reset 00000000 ZF reset 00000001 ZF reset 00000000 ZF reset 00000003 ZF reset 00000000 ZF reset 00000001 ZF reset 00000000 ZF reset 00000002 ZF reset 00000000 ZF reset 00000001 ZF reset 00000000 ZF reset 00000004
Instrukce BSR sice pro některé vstupy vrací odlišné indexy bitů (což je očekávané chování), ovšem příznak ZF nastavuje naprosto stejným způsobem, jako je tomu u instrukce BSF. To je ostatně patrné z následující tabulky:
ZF set 00000000 ZF reset 00000000 ZF reset 00000001 ZF reset 00000001 ZF reset 00000002 ZF reset 00000002 ZF reset 00000002 ZF reset 00000002 ZF reset 00000003 ZF reset 00000003 ZF reset 00000003 ZF reset 00000003 ZF reset 00000003 ZF reset 00000003 ZF reset 00000003 ZF reset 00000003 ZF reset 00000004
9. Zjištění počtu nulových bitů na začátku nebo konci testované hodnoty
Instrukce BSF a BSR jsou podporovány (z pohledu moderního IT) celou věčnost, protože byly přidány již do instrukční sady mikroprocesorů Intel 80386 (1985). V moderních mikroprocesorech s architekturou x86–64 jsou tyto instrukce stále podporovány, ovšem navíc mají vývojáři k dispozici dvě další instrukce nazvané LZCNT a TZCNT. Instrukce LZCNT vrací délku sekvence nulových bitů, přičemž tato sekvence musí začínat nejvyšším bitem. Instrukce TZCNT taktéž vrací délku sekvence nulových bitů, ovšem nyní tato sekvence začíná nejnižším bitem.
Do jistém míry tedy tedy instrukce nahrazují BSF a BSR, ovšem je nutné myslet na odlišné chování:
- Jsou vráceny délky sekvencí nulových bitů a nikoli indexy nenulových bitů – tj. hodnota bude shodná, ovšem jen pokud začínáme od nejnižšího bitu. A pokud naopak začínáme od bitu nejvyššího, je hodnota zcela odlišná (závisí na bitové šířce operandu).
- Pokud je délka nalezené sekvence nulová (tj. první nalezený bit má hodnotu 1), nastavuje se příznak ZF.
- Pokud odpovídá délka sekvence bitové šířce vstupu, nastavuje se příznakCF.
10. Příklad použití instrukce LZCNT
Základní chování instrukce LZCNT si ověříme na demonstračním příkladu, ve kterém této instrukci opět předáme hodnotu 0×42, kterou je možné v binární podobě vyjádřit jako 0b01000010:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
mov eax, 0x42 ; == 0b01000010
lzcnt edx, eax
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
exit ; ukonceni procesu
%include "hex2string.asm"
Po překladu a spuštění by se měla vypsat hodnota:
00000019
Proč tomu tak je? Ve skutečnosti pracujeme s 32bitovým registrem a vypsaná hodnota 0×19 decimálně odpovídá hodnotě 25. A pokud se podíváme na binární vyjádření vstupu, tak zjistíme, že plná 32bitová hodnota 0b00000000000000000000000001000010 má na začátku dvacet pět nul.
11. Příklad použití instrukce TZCNT
V dalším demonstračním příkladu naprogramovaném v assembleru zavoláme instrukci TZCNT:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
mov eax, 0x42 ; == 0b01000010
tzcnt edx, eax
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
exit ; ukonceni procesu
%include "hex2string.asm"
Nyní se vypíše:
00000001
To taktéž odpovídá očekávání, protože (počítáno od nejnižšího bitu) končí analyzovaná 32bitová hodnota přesně jedním nulovým bitem.
12. LZCNT == REP BSR
Instrukce LZCNT do jisté míry odpovídá chování instrukce BSR, i když vrácené hodnoty a nastavované příznaky jsou odlišné. Při zavádění této (relativně nové) instrukce do instrukční sady byl proto zvolen malý trik – instrukční kód LZCNT je totožný s instrukčním kódem instrukce BSR, ovšem s přidaným prefixem REP, jenž u BSR vlastně nemá žádný význam (teoreticky by měl znamenat opakování instrukce se změnou ukazatelů/adres, což je ovšem definováno pouze pro instrukce MOVS, STOS, CMPS, LODS a SCAS). Instrukci tak bylo možné přidat, aniž by zabírala další (drahou) pozici v sadě dostupných operačních kódů.
Ostatně můžeme si otestovat, zda je to pravda, úpravou existujícího demonstračního příkladu (viz podtrženou část kódu):
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
mov eax, 0x42 ; == 0b01000010
rep bsr edx, eax
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
exit ; ukonceni procesu
%include "hex2string.asm"
Výsledkem bude:
00000019
Totožné kódování je patrné i při pohledu na kontrolní výpisy generované assemblerem NASM při použití přepínače -l:
0FBDD0 bsr edx, eax ; BSR bez prefixu F30FBDD0 lzcnt edx, eax ; LZCNT má totožné kódování s přidaným prefixem REP F30FBDD0 rep bsr edx, eax ; naprosto stejný instrukční kód
13. TZCNT == REP BSF
Prakticky stejnou vlastností „trpí“ i instrukce TZCNT, která je přeložena do stejné sekvence bajtů, jako instrukce REP BSF. Taktéž si to ověříme na upraveném demonstračním příkladu:
[bits 32]
%include "linux_macros.asm"
;-----------------------------------------------------------------------------
section .data
hex_message:
times 8 db '?'
db 0x0a
hex_message_length equ $ - hex_message
;-----------------------------------------------------------------------------
section .bss
;-----------------------------------------------------------------------------
section .text
global _start ; tento symbol ma byt dostupny i linkeru
_start:
mov eax, 0x42 ; == 0b01000010
rep bsf edx, eax
mov ebx, hex_message ; buffer, ktery se zaplni hexa cislicemi
call hex2string ; zavolani prislusne subrutiny
print_string hex_message, hex_message_length ; tisk hexadecimalni hodnoty
exit ; ukonceni procesu
%include "hex2string.asm"
Po překladu a spuštění takto upraveného příkladu se korektně vypíše hodnota 1:
00000001
Porovnání operačních kódů instrukcí:
0FBCD0 bsf edx, eax ; BSF bez prefixu F30FBCD0 tzcnt edx, eax ; TZCNT má totožné kódování s přidaným prefixem REP F30FBCD0 rep bsf edx, eax ; naprosto stejný instrukční kód
14. Volání vestavěné funkce __builtin_stdc_first_trailing_one
Nyní od assembleru přejdeme zpět k jazyku C, konkrétně k překladači GCC. Ukážeme si použití vestavěné funkce __builtin_stdc_first_trailing_one, která nalezne index prvního jedničkového bitu. Indexy jsou počítány od jedničky (nikoli od nuly) a nulová výsledná hodnota je vyhrazena pro ty případy, v nichž není jedničkový bit vůbec nalezen, tj. pro nulový vstup. Příklad navíc vytiskne i binární hodnotu, ve které jedničkový bit hledáme, aby se dala ověřit korektní funkcionalita:
#include <stdio.h>
#include <stdint.h>
uint8_t bsf_8bit(uint8_t x) {
uint8_t z;
z = __builtin_stdc_first_trailing_one(x);
return z;
}
void print_bin(uint8_t x) {
int i;
for (i = 7; i >= 0; i--) {
printf("%d", (x >> i) & 1);
}
}
void test_bsf(uint8_t x) {
printf("%u \t", x);
print_bin(x);
printf("\t%d\n", bsf_8bit(x));
}
int main(void) {
uint8_t i;
for (i=0; i<=17; i++) {
test_bsf(i);
}
test_bsf(0xff);
}
Z vypsaných výsledků je patrné, že indexy skutečně začínají jedničkou a nula je vrácena pouze pro vstup 0×00:
0 00000000 0 1 00000001 1 2 00000010 2 3 00000011 1 4 00000100 3 5 00000101 1 6 00000110 2 7 00000111 1 8 00001000 4 9 00001001 1 10 00001010 2 11 00001011 1 12 00001100 3 13 00001101 1 14 00001110 2 15 00001111 1 16 00010000 5 17 00010001 1 255 11111111 1
15. Překlad funkce __builtin_stdc_first_trailing_one do strojového kódu
Dále nás bude zajímat, jakým způsobem se vlastně vestavěná funkce __builtin_stdc_first_trailing_one přeloží do strojového kódu mikroprocesorů s architekturou x86–84. Vyzkoušíme si chování pro různé typy argumentů (8, 16, 32 a 64 bitů):
#include <stdint.h>
uint8_t bsf_8bit(uint8_t x) {
uint8_t z;
z = __builtin_stdc_first_trailing_one(x);
return z;
}
uint16_t bsf_16bit(uint16_t x) {
uint16_t z;
z = __builtin_stdc_first_trailing_one(x);
return z;
}
uint32_t bsf_32bit(uint32_t x) {
uint32_t z;
z = __builtin_stdc_first_trailing_one(x);
return z;
}
uint64_t bsf_64bit(uint64_t x) {
uint64_t z;
z = __builtin_stdc_first_trailing_one(x);
return z;
}
16. Analýza přeloženého kódu
Podívejme se nyní na způsob překladu demonstračního příkladu uvedeného v předchozí kapitole do strojového kódu. Je patrné, že se ve všech čtyřech variantách využívá instrukce TZCNT, která získá délku sekvence nulových bitů (po které následuje bit jedničkový). Z tohoto důvodu je výsledek vypočtený instrukcí zvýšen o jedničku. Navíc se testuje situace, kdy je vstup nulový (tedy neexistují v něm jedničkové bity). V takovém případě se vrací nulová hodnota přečtená z registru EDX, který je vynulován operací xor (příznaky nelze použít, protože jsou ovlivněny instrukcí ADD).
Varianta s osmibitovým vstupem musí provést převod vstupu na 16 nebo 32 bitů, protože instrukce TZCNT nepodporuje osmibitový vstup:
bsf_8bit:
movzx edi, dil
xor eax, eax
xor edx, edx
rep bsf eax, edi
add eax, 1
test edi, edi
cmove eax, edx
ret
Šestnáctibitová varianta s převodem vstupu na 32 bitů:
bsf_16bit:
movzx edi, di
xor eax, eax
xor edx, edx
rep bsf eax, edi
add eax, 1
test edi, edi
cmove eax, edx
ret
Nejjednodušší je 32bitová varianta:
bsf_32bit:
xor eax, eax
xor edx, edx
rep bsf eax, edi
add eax, 1
test edi, edi
cmove eax, edx
ret
64bitová varianta musí opět provádět konverzi, tentokrát výsledku:
bsf_64bit:
xor eax, eax
rep bsf rax, rdi
add eax, 1
test rdi, rdi
cdqe
cmove rax, rdi
ret
17. Překlad pro platformu AArch64
Na závěr se alespoň ve stručnosti podíváme na způsob překladu téhož demonstračního příkladu, nyní ovšem pro platformu AArch64, která má zcela odlišnou instrukční sadu, než x86–64. I postup je do značné míry odlišný, protože je k dispozici jen instrukce CLZ určená pro získání sekvence nulových bitů, přičemž se začíná od nejvyššího bitu. Před voláním této instrukce je tedy nutné obsah vstupu otočit (nejvyšší bit zaměnit s nejnižším bitem atd.). A pochopitelně se musí pracovat i se stavem, kdy je vstup nulový a musí se tedy vracet nula. Ukážeme si ho na příkladu 16bitového vstupu:
ands w0, w0, 65535 ; maskování vstupu na 16 bitů rbit w1, w0 ; otočení všech bitů v registru clz w1, w1 ; spočítání sekvence nulových bitů, začíná se od nejvyššího bitu csinc w0, wzr, w1, eq ; podmíněné přičtení jedničky v případě, že je vstup nulový ret ; návrat ze subrutiny
bsf_8bit:
ands w0, w0, 255
rbit w1, w0
clz w1, w1
csinc w0, wzr, w1, eq
ret
bsf_16bit:
ands w0, w0, 65535
rbit w1, w0
clz w1, w1
csinc w0, wzr, w1, eq
ret
bsf_32bit:
rbit w1, w0
cmp w0, 0
clz w1, w1
csinc w0, wzr, w1, eq
ret
bsf_64bit:
rbit x1, x0
cmp x0, 0
clz x1, x1
csinc x0, x0, x1, eq
ret
18. Příloha: soubor Makefile pro překlad příkladů napsaných v assembleru NASM
Všechny výše uvedené demonstrační příklady naprogramované v assembleru NASM je možné přeložit s využitím souboru Makefile, jehož obsah je vypsán níže. Postačuje zadat příkaz make all:
ASM=nasm
LINKER=ld
execs := bsf1 bsr1 bsf2 bsr2 bsf3 bsr3 lzcnt1 lzcnt2 tzcnt1 tzcnt2
all: $(execs)
clean:
rm -f *.o $(execs)
.PHONY: all clean
%.o: %.asm linux_macros.asm hex2string.asm
${ASM} -f elf $< -o $@
bsf1: bsf1.o
ld -melf_i386 $< -o $@
bsr1: bsr1.o
ld -melf_i386 $< -o $@
bsf2: bsf2.o
ld -melf_i386 $< -o $@
bsr2: bsr2.o
ld -melf_i386 $< -o $@
bsf3: bsf3.o
ld -melf_i386 $< -o $@
bsr3: bsr3.o
ld -melf_i386 $< -o $@
lzcnt1: lzcnt1.o
ld -melf_i386 $< -o $@
lzcnt2: lzcnt2.o
ld -melf_i386 $< -o $@
tzcnt1: tzcnt1.o
ld -melf_i386 $< -o $@
tzcnt2: tzcnt2.o
ld -melf_i386 $< -o $@
19. Repositář s demonstračními příklady
kontrolní výpis výsledku překladu: instrukční kód instrukce BSFDemonstrač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ář:
| # | Příklad | Stručný popis | Adresa |
|---|---|---|---|
| 1 | rotate_left.c | volání vestavěné funkce v C (GCC) realizující rotaci doleva | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_left.c |
| 2 | rotate_left_x86_00.asm | překlad volání funkce __builtin_stdc_rotate_left na platformě x86–64 bez aplikace optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_left_x86_00.asm |
| 3 | rotate_left_x86_09.asm | překlad volání funkce __builtin_stdc_rotate_left na platformě x86–64 s aplikací optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_left_x86_09.asm |
| 4 | rotate_left_arm32.asm | překlad volání funkce __builtin_stdc_rotate_left pro 32bitové ARMy | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_left_arm32.asm |
| 5 | rotate_left_arm64.asm | překlad volání funkce __builtin_stdc_rotate_left pro 64bitové ARMy (AArch64) | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_left_arm64.asm |
| 6 | rotate_right.c | volání vestavěné funkce v C (GCC) realizující rotaci doleva | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_right.c |
| 7 | rotate_right_x86_00.asm | překlad volání funkce __builtin_stdc_rotate_right na platformě x86–64 bez aplikace optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_right_x86_00.asm |
| 8 | rotate_right_x86_09.asm | překlad volání funkce __builtin_stdc_rotate_right na platformě x86–64 s aplikací optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_right_x86_09.asm |
| 9 | rotate_right_arm32.asm | překlad volání funkce __builtin_stdc_rotate_right pro 32bitové ARMy | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_right_arm32.asm |
| 10 | rotate_right_arm64.asm | překlad volání funkce __builtin_stdc_rotate_right pro 64bitové ARMy (AArch64) | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rotate_right_arm64.asm |
| 11 | parity_unsigned.c | volání vestavěných funkcí __builtin_parity, __builtin_parityl a __builtin_parityll | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parity_unsigned.c |
| 12 | parity_unsigned_x86_00.asm | překlad volání funkcí __builtin_parity* na platformě x86–64 bez aplikace optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parity_unsigned_x86_00.asm |
| 13 | parity_unsigned_x86_09.asm | překlad volání funkcí __builtin_parity* na platformě x86–64 s aplikací optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parity_unsigned_x86_09.asm |
| 14 | parity_unsigned_arm32.asm | překlad volání funkcí __builtin_parity* pro 32bitové ARMy | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parity_unsigned_arm32.asm |
| 15 | parity_unsigned_arm64.asm | překlad volání funkcí __builtin_parity* pro 64bitové ARMy (AArch64) | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parity_unsigned_arm64.asm |
| 16 | parityg_unsigned.c | volání vestavěné funkce __builtin_parityg | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parityg_unsigned.c |
| 17 | parityg_unsigned_arm32.asm | překlad volání funkce __builtin_parityg na platformě x86–64 bez aplikace optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parityg_unsigned_arm32.asm |
| 18 | parityg_unsigned_arm64.asm | překlad volání funkce __builtin_parityg na platformě x86–64 s aplikací optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parityg_unsigned_arm64.asm |
| 19 | parityg_unsigned_x86_00.asm | překlad volání funkce __builtin_parityg pro 32bitové ARMy | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parityg_unsigned_x86_00.asm |
| 20 | parityg_unsigned_x86_09.asm | překlad volání funkce __builtin_parityg pro 64bitové ARMy (AArch64) | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parityg_unsigned_x86_09.asm |
| 21 | parity_signed.c | výpočet parity celočíselných hodnot se znaménkem: realizace pomocí vestavěných funkcí __builtin_parity, __builtin_parityl a __builtin_parityll | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parity_signed.c |
| 22 | parityg_signed.c | výpočet parity celočíselných hodnot se znaménkem: realizace pomocí vestavěné funkce __builtin_parityg | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/parityg_signed.c |
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:
| # | Příklad | Stručný popis | Adresa |
|---|---|---|---|
| 1 | add_overflow.c | volání vestavěné funkce __builtin_add_overflow s předáním operandů různých typů | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_overflow.c |
| 2 | add_overflow_x86_64_O0.asm | překlad volání funkce __builtin_add_overflow na platformě x86–64 bez aplikace optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_overflow_x86_64_O0.asm |
| 3 | add_overflow_x86_64_Os.asm | překlad volání funkce __builtin_add_overflow na platformě x86–64 s aplikací optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_overflow_x86_64_Os.asm |
| 4 | add_overflow_arm32.asm | překlad volání funkce __builtin_add_overflow pro 32bitové ARMy | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_overflow_arm32.asm |
| 5 | add_overflow_arm64.asm | překlad volání funkce __builtin_add_overflow pro 64bitové ARMy (AArch64) | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_overflow_arm64.asm |
| 6 | add_diff_types.c | součet s využitím různých kombinací hodnot typu char a int | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_diff_types.c |
| 7 | add_diff_types_x86_64.asm | překlad volání funkce __builtin_add_overflow na platformě x86–64 s aplikací optimalizací | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_diff_types_x86_64.asm |
| 8 | add_diff_types_arm32.asm | překlad volání funkce __builtin_add_overflow pro 32bitové ARMy | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_diff_types_arm32.asm |
| 9 | add_diff_types_arm64.asm | překlad volání funkce __builtin_add_overflow pro 64bitové ARMy (AArch64) | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/add_diff_types_arm64.asm |
| 10 | sub_overflow.c | operace rozdílu s využitím funkce __builtin_sub_overflow | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/sub_overflow.c |
| 11 | sub_overflow.asm | překlad volání funkce __builtin_sub_overflow na platformě x86–64 | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/sub_overflow.asm |
| 12 | addc_subc.c | operace součtu tří hodnot a operace rozdílu: s výpůjčkou nebo s přetečením | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/addc_subc.asm |
| # | Příklad | Stručný popis | Adresa |
|---|---|---|---|
| 1 | rdrand_support.asm | test, jestli je instrukce RDRAND mikroprocesorem podporována | https://github.com/tisnik/8bit-fame/blob/master/pc-linux/rdrand_support.asm |
| 2 | rdrand_read.asm | přečtení jedné 32bitové hodnoty instrukcí RDRAND | https://github.com/tisnik/8bit-fame/blob/master/pc-linux/rdrand_read.asm |
| 3 | rdrand_read_loop.asm | přečtení sekvence 32bitových hodnot instrukcí RDRAND | https://github.com/tisnik/8bit-fame/blob/master/pc-linux/rdrand_read_loop.asm |
| 4 | rdrand_read.c | přečtení náhodné 32bitové hodnoty, realizace s využitím vestavěné funkce GCC | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rdrand_read.c |
| 5 | rdrand_read.asm | výsledek překladu předchozího zdrojového kódu do assembleru | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rdrand_read.asm |
| 6 | rand_gen.c | vygenerování binárního souboru s pseudonáhodnými 32bitovými hodnotami | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rand_gen.c |
| 7 | rdrand_gen.c | vygenerování binárního souboru s hodnotami vrácenými instrukcí RDRAND | https://github.com/tisnik/8bit-fame/blob/master/gcc-builtins/rdrand_gen.c |
20. Odkazy na Internetu
- 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/ - 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/ - Circular shift (Wikipedia)
https://en.wikipedia.org/wiki/Bitwise_operation#Circular_shift - Parity bit (Wikipedia)
https://en.wikipedia.org/wiki/Parity_bit - Parity function (Wikipedia)
https://en.wikipedia.org/wiki/Parity_function - RDRAND (Wikipedia)
https://en.wikipedia.org/wiki/RDRAND - RDRAND instruction
https://www.felixcloutier.com/x86/rdrand - Random Number Generator
https://wiki.osdev.org/Random_Number_Generator - GCC documentation: Extensions to the C Language Family
https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions - GCC documentation: Using Vector Instructions through Built-in Functions
https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html - SSE (Streaming SIMD Extentions)
http://www.songho.ca/misc/sse/sse.html - Timothy A. Chagnon: SSE and SSE2
http://www.cs.drexel.edu/~tc365/mpi-wht/sse.pdf - CPU design (Wikipedia)
http://en.wikipedia.org/wiki/CPU_design - GCC Compiler Intrinsics
https://iq.opengenus.org/gcc-compiler-intrinsics/ - Other Built-in Functions Provided by GCC
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html - GCC: 6.60 Built-in Functions Specific to Particular Target Machines
https://gcc.gnu.org/onlinedocs/gcc/Target-Builtins.html#Target-Builtins - Additional Builtins for Numeric Operations
https://gcc.gnu.org/onlinedocs/gcc/Numeric-Builtins.html - Bit Operation Builtins
https://gcc.gnu.org/onlinedocs/gcc/Bit-Operation-Builtins.html - Stránka projektu Compiler Explorer
https://godbolt.org/ - The LLVM Compiler Infrastructure
https://llvm.org/ - GCC, the GNU Compiler Collection
https://gcc.gnu.org/ - Clang
https://clang.llvm.org/ - Clang: Assembling a Complete Toolchain
https://clang.llvm.org/docs/Toolchain.html - Integer overflow
https://en.wikipedia.org/wiki/Integer_overflow - SETcc — Set Byte on Condition
https://www.felixcloutier.com/x86/setcc - The ARMv8 instruction sets
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch05s01.html - A64 Instruction Set
https://developer.arm.com/products/architecture/instruction-sets/a64-instruction-set - Switching between the instruction sets
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch05s01.html - The A64 instruction set
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch05s01.html - Introduction to ARMv8 64-bit Architecture
https://quequero.org/2014/04/introduction-to-arm-architecture/ - Undefined behavior (Wikipedia)
https://en.wikipedia.org/wiki/Undefined_behavior - Is signed integer overflow still undefined behavior in C++?
https://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c - Allowing signed integer overflows in C/C++
https://stackoverflow.com/questions/4240748/allowing-signed-integer-overflows-in-c-c - SXTB, SXTH, SXTW
https://www.scs.stanford.edu/~zyedidia/arm64/sxtb_z_p_z.html - BX, BXNS
https://developer.arm.com/documentation/100076/0200/a32-t32-instruction-set-reference/a32-and-t32-instructions/bx–bxns?lang=en - Carry and Borrow Principles
https://www.tpub.com/neets/book13/53a.htm - In binary subtraction, how do you handle a borrow when there are no bits left to borrow form
https://stackoverflow.com/questions/68629408/in-binary-subtraction-how-do-you-handle-a-borrow-when-there-are-no-bits-left-to - Is there any legitimate use for Intel's RDRAND?
https://stackoverflow.com/questions/26771329/is-there-any-legitimate-use-for-intels-rdrand - Intel® Digital Random Number Generator (DRNG) Software Implementation Guide
https://www.intel.com/content/www/us/en/developer/articles/guide/intel-digital-random-number-generator-drng-software-implementation-guide.html - Hardware random number generator
https://en.wikipedia.org/wiki/Hardware_random_number_generator - Random number generator attack
https://en.wikipedia.org/wiki/Random_number_generator_attack - random_r.c (Glibc)
https://github.com/lattera/glibc/blob/master/stdlib/random_r.c#L341 - Xorshift
https://en.wikipedia.org/wiki/Xorshift - x86 instruction listings
https://en.wikipedia.org/wiki/X86_instruction_listings - Odd inline asm code generation with pointless memory operand
https://github.com/llvm/llvm-project/issues/56789 - Bit scanning equivalencies
https://fgiesen.wordpress.com/2013/10/18/bit-scanning-equivalencies/ - BSF — Bit Scan Forward
https://www.felixcloutier.com/x86/bsf - BSR — Bit Scan Reverse
https://www.felixcloutier.com/x86/bsr - TZCNT — Count the Number of Trailing Zero Bits
https://www.felixcloutier.com/x86/tzcnt - LZCNT — Count the Number of Leading Zero Bits
https://www.felixcloutier.com/x86/lzcnt
