9.4 Gyakorlati bitmanipulációs feladatok: popcount, parity, bitfordítás

9.4.1 Három művelet, három különböző kérdés

Egy jogosultságokat tároló bitmaszkból szeretnénk megtudni, hány engedély aktív. Egy adatátviteli kerethez egyszerű hibajelző bitet számítunk. Egy algoritmus pedig a bemenet bitjeit fordított sorrendben várja. Mindhárom feladat bitmanipuláció, de eltérő eredményt és eltérő implementációt igényel.

Ebben az alfejezetben 32 bites, előjel nélküli értékeken dolgozunk. A profil A64 ISA, ARMv8-A, little-endian Linux; minden alábbi assemblyutasítás és regiszter ebben a környezetben értendő. Az előfeltétel a bitmezőkezelés, valamint a korábban megismert elágazás és függvényhívási szerződés.

Legyen $x_i$ az előjel nélküli $x$ érték $i$ indexű bitje; a legkisebb helyi értékű bit indexe 0.

A paritás itt 1, ha páratlan számú bit van beállítva. Ez a bit egy adatmezőhöz hozzáfűzve páros összparitást ad.

9.4.2 Popcount: mindig egyetlen beállított bitet törlünk

A popcount hasznos bitkészletek elemszámának meghatározására. Két azonos szélességű bitsorozat eltérő pozícióinak száma, a Hamming-távolság (Hamming distance), az XOR-eredmény popcountja.

A legegyszerűbb algoritmus 32 alkalommal megvizsgálja az alsó bitet, majd jobbra tol. Ritka bitmaszknál azonban célszerűbb közvetlenül a beállított biteket eltávolítani:

x = x & (x - 1)

Levezetés. Ha $x\ne0$, a legalacsonyabb beállított bit alatti bitek mind nullák. Az 1 kivonása ezt a beállított bitet nullára, az alatta álló nullákat egyesekre változtatja. A magasabb bitek változatlanok. Az eredeti értékkel végzett AND ezért pontosan a legalacsonyabb beállított bitet törli.

Például, előjel nélküli olvasattal:

A ciklus tehát pontosan annyiszor fut, amennyi a popcount. A nulla bemenetet a ciklus előtt kezeljük. A módszer gyakran Brian Kernighan algoritmusa néven szerepel.

Fontos következmény: a végrehajtási útvonal adatfüggő. Titkos értékek feldolgozásakor ez önmagában elegendő ok arra, hogy ne tekintsük automatikusan állandó idejű megoldásnak.

9.4.3 Parity: XOR-összecsukás

Az XOR asszociatív és kommutatív, továbbá egy bit önmagával vett XOR-ja nulla. A paritás ezért fokozatos XOR-összecsukással (XOR folding) számítható.

Az előjel nélküli értéket először a 16 bittel jobbra tolt másolatával XOR-oljuk össze. Az alsó 16 pozíció ekkor már két-két eredeti bit XOR-ját tartalmazza. Ezután következik a 8, 4, 2 és 1 bites eltolás.

Az utolsó lépés után csak a legalsó bitet használjuk. A többi eredménybit nem feltétlenül nulla, ezért szükséges az 1 értékű maszkkal végzett AND.

Az A64 EOR eltolt regiszteroperandusa egyetlen utasításban fejezi ki az XOR-t és a forrás logikai jobbra tolását.

A paritás egyszerű hibajelzés: minden páratlan számú bitváltozást észlel, de páros számú bitváltozás észrevétlen maradhat. Nem helyettesít általános ellenőrző összeget vagy hibajavító kódot.

9.4.4 Bitfordítás: az alsó bitből építjük az eredményt

A bitfordításnál egy nulláról induló akkumulátort használunk. Minden lépés:

1. kiemeli a bemenet alsó bitjét;
2. balra tolja az akkumulátort egy bittel;
3. beilleszti a kiemelt bitet az akkumulátor alsó pozíciójába;
4. logikailag jobbra tolja a bemenetet.

Ciklusinvariáns: $j$ lépés után az akkumulátor alsó $j$ bitje az eredeti bemenet alsó $j$ bitjének fordított sorrendű sorozata. A feldolgozatlan bemenetrész közben $j$ bittel jobbra tolódott.

Pontosan 32 lépés szükséges. Az előjel nélküli 0x00000001 fordítottja 0x80000000, nem 0x00000001: a vezető nullák is a rögzített szélességű bitsorozat részei.

Ez nem bájtsorrendcsere. A regiszterérték bitfordítása nem függ attól, milyen bájtsorrenddel tároljuk az értéket a memóriában. Az A64 REV bájtsorrendet cserél, az A64 RBIT pedig biteket fordít.

9.4.5 Kidolgozott példa: három algoritmus és egy natív referencia

Munkakönyvtár: ~/arm-labor/a64/a035/ — az alfejezet minden laborfájlja ide kerül, és minden parancs innen futtatandó (a könyvtárrendet a Labor-alapkörnyezet alfejezet írja le).

mkdir -p ~/arm-labor/a64/a035
cd ~/arm-labor/a64/a035

Az alábbi négy levélfüggvény (leaf function) az AAPCS64 szerződését követi: a bemenet és az eredmény az A64 W0 regiszterben van. Csak hívó által mentendő munkaregisztereket módosítanak; nem hívnak más függvényt, ezért veremkeret sem szükséges.

Az A64 Wn célregiszter írása a hozzá tartozó Xn felső 32 bitjét nullázza. Itt ez összhangban áll a uint32_t interfésszel.

A lab-bits.S teljes tartalma:

// A64 ISA, ARMv8-A, little-endian Linux.
// Minden utasítás és regiszter A64; a direktívák GNU as direktívák.
.arch armv8-a
.text
.p2align 2

.global lab_popcount32
.type lab_popcount32, %function
lab_popcount32:
    mov     w1, wzr
    cbz     w0, .Lpc_done
.Lpc_loop:
    sub     w2, w0, #1
    and     w0, w0, w2
    add     w1, w1, #1
    cbnz    w0, .Lpc_loop
.Lpc_done:
    mov     w0, w1
    ret
.size lab_popcount32, .-lab_popcount32

.global lab_parity32
.type lab_parity32, %function
lab_parity32:
    eor     w0, w0, w0, lsr #16
    eor     w0, w0, w0, lsr #8
    eor     w0, w0, w0, lsr #4
    eor     w0, w0, w0, lsr #2
    eor     w0, w0, w0, lsr #1
    and     w0, w0, #1
    ret
.size lab_parity32, .-lab_parity32

.global lab_reverse32
.type lab_reverse32, %function
lab_reverse32:
    mov     w1, wzr
    mov     w2, #32
.Lrev_loop:
    and     w3, w0, #1
    lsl     w1, w1, #1
    orr     w1, w1, w3
    lsr     w0, w0, #1
    subs    w2, w2, #1
    b.ne    .Lrev_loop
    mov     w0, w1
    ret
.size lab_reverse32, .-lab_reverse32

.global lab_reverse32_native
.type lab_reverse32_native, %function
lab_reverse32_native:
    rbit    w0, w0
    ret
.size lab_reverse32_native, .-lab_reverse32_native

.section .note.GNU-stack,"",%progbits

Immediate-ok: a példa konstansai (#1, #32, a 0–31 közötti eltolások) mind kódolhatók; a szabályokat az A64 immediate-korlátok összefoglalója adja. Az AND #1 azért megengedett, mert az 1 érvényes logikai (bitmaszk-) immediate.

A tesztprogram, lab-bits-test.c, ismert eredmények mellett összefüggéseket is ellenőriz:

/* C tesztharness; cél: AArch64 Linux, little-endian. */
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

extern uint32_t lab_popcount32(uint32_t);
extern uint32_t lab_parity32(uint32_t);
extern uint32_t lab_reverse32(uint32_t);
extern uint32_t lab_reverse32_native(uint32_t);

int main(void)
{
    static const struct {
        uint32_t x, count, parity, reversed;
    } cases[] = {
        {0x00000000u,  0, 0, 0x00000000u},
        {0x00000001u,  1, 1, 0x80000000u},
        {0x80000000u,  1, 1, 0x00000001u},
        {0x80000001u,  2, 0, 0x80000001u},
        {0xffffffffu, 32, 0, 0xffffffffu},
        {0xaaaaaaaau, 16, 0, 0x55555555u},
        {0x01234567u, 12, 0, 0xe6a2c480u},
        {0x00010000u,  1, 1, 0x00008000u}
    };

    for (size_t i = 0; i < sizeof cases / sizeof cases[0]; ++i) {
        uint32_t x = cases[i].x;
        uint32_t p = lab_popcount32(x);
        uint32_t q = lab_parity32(x);
        uint32_t r = lab_reverse32(x);

        if (p != cases[i].count ||
            q != cases[i].parity ||
            r != cases[i].reversed ||
            q != (p & 1u) ||
            r != lab_reverse32_native(x) ||
            lab_reverse32(r) != x) {
            printf("FAIL: x=0x%08" PRIx32
                   " count=%" PRIu32 " parity=%" PRIu32
                   " reversed=0x%08" PRIx32 "\n", x, p, q, r);
            return 1;
        }
    }

    puts("OK: 8 tesztvektor");
    return 0;
}

A kétszeri bitfordítás az eredeti értéket adja. Ez hasznos ellenőrzés, de önmagában kevés: az identitásfüggvény is teljesítené. Ezért használunk ismert eredményeket és külön A64 RBIT-referenciát is.

9.4.6 Assemble–link–run és ellenőrzés

Az alábbi munkafolyamat az Ubuntu 24.04 laborprofil cross-eszközláncát és a célrendszer statikus C-könyvtárát feltételezi.

# Target: qemu-user, AArch64 Linux, ARMv8-A, little-endian.
# Assemble:
aarch64-linux-gnu-gcc -march=armv8-a -g \
    -c lab-bits.S -o lab-bits.o

# C-fordítás:
aarch64-linux-gnu-gcc -march=armv8-a -std=c11 -O2 -g \
    -Wall -Wextra -c lab-bits-test.c -o lab-bits-test.o

# Link:
aarch64-linux-gnu-gcc -static \
    lab-bits-test.o lab-bits.o -o lab-bits

# Run:
qemu-aarch64 ./lab-bits
printf 'kilepesi_allapot=%d\n' "$?"

Várt, nem ténylegesen mért kimenet: OK: 8 tesztvektor, majd kilepesi_allapot=0. Algoritmushiba esetén a tesztprogram FAIL: kezdetű sort ír és 1 állapottal lép ki. A fordítási vagy betöltési hiba ettől külön kezelendő.

A létrejött utasítások ellenőrzése:

# A qemu-user célprogram hostoldali, statikus vizsgálata; nincs futtatás.
aarch64-linux-gnu-objdump -d --disassemble=lab_popcount32 lab-bits
aarch64-linux-gnu-objdump -d --disassemble=lab_parity32 lab-bits
aarch64-linux-gnu-objdump -d --disassemble=lab_reverse32 lab-bits

Az objdump eltérő aliasnevet is kiírhat ugyanarra a kódolásra. Nem pusztán a szöveget, hanem az operandusszélességet és a művelet jelentését ellenőrizzük.

9.4.7 Teljesítmény-előzetes: utasításszám nem egyenlő ciklusszámmal

A konkrét függvények dinamikus utasításszáma egyszerűen levezethető. Az alábbi értékek a visszatérést tartalmazzák, a hívó utasítását nem.

A popcountban négy ciklusutasítás jut minden beállított bitre, továbbá négy utasítás a cikluson kívüli részre. Így nulla bemenetre 4, minden bitet beállítva 132 utasítás adódik.

Ezek nem ciklusszámok. Az eredmény elkészülési késleltetése (latency), az időegységenként feldolgozható műveletek száma (throughput), az adatfüggőségek és az elágazásbecslés mikroarchitektúra-függők. Még a rögzített utasításszám sem bizonyít önmagában állandó futási időt.

Bitfordításnál az A64 RBIT az ARMv8-A alapprofil része, ezért valódi implementációban általában ezt keressük először. A ciklus tanulási és referenciaértéke ettől megmarad.

Popcountnál az ARMv8-A alapprofil általános A64 Wn/Xn regisztereire nincs egyetlen skaláris popcountutasítás. Az A64 Advanced SIMD/NEON CNT viszont bájtonként megszámolja a beállított biteket. Egy teljes szó popcountjához a bájtonkénti eredményeket még összegezni kell.

Egyetlen értéknél a regiszterek közötti adatmozgatás és az összegzés költsége is számít. Hosszú tömbnél ezek a költségek több elemre oszthatók el; különösen indokolt a natív lehetőségek vizsgálata, ha az adat már SIMD-regiszterben van. Ezt a NEON regiszterkészleténél és a gyorsulás mérésénél bontjuk ki.

QEMU-ban a szemantika ellenőrizhető, de az ottani futásidő nem hardverhű abszolút ciklusszám. Fizikai AArch64 gépen külön mérés szükséges; itt nem közlünk mért gyorsulást.

9.4.8 Tipikus hibák és ellenpróbák

A hibakeresési sorrend: konkrét hibás bemenet rögzítése, hipotézis megfogalmazása, disassembly gyűjtése, egyetlen változtatás, majd teljes újrafordítás és regressziós teszt.

A 64 bites változatnál nem elég az A64 Wn neveket Xn nevekre cserélni: a paritáshoz 32 bites első összecsukás, a bitfordításhoz 64 iteráció szükséges.

9.4.9 Feladatok

1. (magyarázó, alapszint — cél: megértés-ellenőrzés) Mi a popcount, a paritás és a 32 bites bitfordítás eredménye az előjel nélküli 0x00000010 értékre? Miért lenne hibás öt bit feldolgozása után leállítani a bitfordítást?

2. (implementációs, középszint — cél: rutinépítés) Rövidítsd a bitfordítás ciklustörzsét hatról öt A64 utasításra az eltolt regiszteroperandusú ORR használatával. Az interfész és a teszteredmények ne változzanak. Vezesd le az új utasításszámot!

3. (hibakeresési, középszint — cél: rutinépítés) Kontrollált hibaként töröld a paritás első, 16 bites eltolást használó A64 EOR utasítását. Futtasd újra a teljes buildet és tesztet. Magyarázd meg a 0x00010000 ellenpéldát, ellenőrizd a disassemblyt, majd állítsd vissza az utasítást.

9.4.10 Megoldások

1. megoldás — Segítség. 0x00000010 egyetlen beállított bitje a 4. indexen van — hová kerül ez a bitfordítás $31-i$ szabálya szerint, és miért nem elég öt lépés, ha a cél index 27?

1. megoldás — Teljes megoldás. A popcount 1, a paritás 1. A beállított bit indexe 4, ezért a bitfordításban a $31-4=27$ indexre kerül: az eredmény 0x08000000. Öt lépés után az akkumulátor még csak 0x00000001; a további 27 lépés helyezi át a bitet a megfelelő pozícióba.

2. megoldás — Segítség. Az ORR eltolt regiszteroperandusa egy lépésben végzi el, amit most két külön utasítás (LSL majd ORR) csinál — a kiemelt bit melyik operandusba kerüljön, hogy ne kelljen előtte külön eltolni?

2. megoldás — Teljes megoldás. Az eredeti A64 LSL és ORR pár helyére ez az egyetlen utasítás kerül:

// A64 ISA, ARMv8-A; a lab_reverse32 ciklustörzsében.
// W3 az előző AND által kiemelt 0 vagy 1.
orr     w1, w3, w1, lsl #1

Az eltolás immediate értéke a 32 bites alak 0–31 tartományába esik. Az eltolt akkumulátor alsó bitje nulla, ezért az OR pontosan beilleszti a kiemelt bitet. Az új számított utasításszám $32\cdot5+4=164$. Az eredeti assemble–link–run lépésekkel továbbra is a nyolc teszt sikerét várjuk; gyorsulást ebből még nem mértünk.

3. megoldás — Segítség. A maradék négy összecsukás (8,4,2,1 eltolás) együtt legfeljebb mekkora távolságra tud egy bitet lefelé mozgatni — eléri-e ez a 16. indextől a 0. pozíciót?

3. megoldás — Teljes megoldás. A megmaradó 8, 4, 2 és 1 bites eltolások összesen legfeljebb 15 pozícióval továbbíthatják lefelé az eredeti bit hozzájárulását. A 16 indexű bit így nem jut el a nulladik pozícióba: a hibás eredmény 0, a helyes paritás 1. Az objdumpban az első összecsukás hiánya látható. Visszaállítás és újraépítés után ismét 0 kilépési állapotot várunk.

9.4.11 Rövid összefoglaló

A három algoritmus ugyanazt a bitsorozatot más szempontból dolgozza fel. A ciklusos popcount minden lépésben egy beállított bitet töröl, ezért munkamennyisége adatfüggő. A paritás öt XOR-összecsukással számítható, de a végén csak az alsó bit érvényes eredmény. A bitfordításnál a rögzített szélesség miatt a vezető nullákat is fel kell dolgozni. A64-en az RBIT közvetlen alternatíva; a NEON CNT használatához további összegzés kell. Az utasításszám algoritmus-összehasonlításra alkalmas, hardveres futásidőt azonban nem helyettesít. A tesztelésben ismert eredmények és algebrai összefüggések egyaránt szükségesek.

• Popcount: a beállított bitek száma.
• Paritás: a popcount maradéka 2-vel osztva.
• Bitfordítás: a rögzített szélességű bitsorozat sorrendjének megfordítása.

9.4.12 Források és ellenőrzési hiányok

A linkek és a dokumentumverziók közös állapota az Olvasói útmutató forrásállapot-táblájában van; itt csak az alfejezet saját megállapításai szerepelnek.

• Arm A-profile architektúra-dokumentáció — A64 RBIT, eltolt logikai operandusok és Advanced SIMD CNT. Ellenőrizve: a link él (a fejezetszám és a kiadásbetű az Arm-oldalak közös korlátja miatt nem ellenőrzött).
• GNU assembler kézikönyv — AArch64 szintaxis, aliasok és direktívák. Tartalmilag ellenőrizve: a jelenlegi kiadás binutils 2.47.
• AAPCS64 — argumentumátadás, visszatérési értékek és regisztermegőrzés. Tartalmilag ellenőrizve: aktuális kiadás 2025Q4 (2026-01-23), Release minőségű.

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: a kód itt nem lett összeállítva vagy futtatva. A telepített Ubuntu-csomagverziókat, a statikus linkelés rendelkezésre állását és a várt eredményeket a hallgatói laborban kell ellenőrizni. Natív teljesítményadat és aktuális, alapprofilon túli utasításkiterjesztés-támogatás nem lett vizsgálva.