9.2 Shift és rotate: LSL/LSR/ASR/ROR gyakorlati mintázatok

9.2.1 Motiváció: bájtokból adat, indexből eltolás

Egy bináris rekord feldolgozásakor gyakran kell biteket más helyi értékre mozgatni: egy bájtot kiemelni, két mezőt összecsomagolni, vagy egy tömbindexből bájteltolást számítani. Ezekhez nem feltétlenül szorzás vagy osztás szükséges. A biteltolás (bit shift) közvetlenül a bitpozíciókat módosítja; a bitforgatás (bit rotation) pedig a kieső biteket a másik oldalon visszahelyezi.

Az előfeltétel a Logikai alapműveletek és bitmaszkolás ismerete. Ebben az alfejezetben minden assembly utasítás és regiszter A64 ISA, AArch64, I. rész kontextusú. A labor ARMv8-A alapprofilú, little-endian Linux-program, amely qemu-aarch64 alatt fut. A GNU assembler direktívái az ehhez tartozó ELF-eszközlánc részei, nem processzorutasítások.

A fő kérdés nem az, hogy „hogyan kell jobbra tolni”, hanem az, hogy mit jelentenek a bitek, mi kerül a megüresedő helyekre, és elveszhet-e információ.

9.2.2 A négy művelet pontos jelentése

Legyen $n$ a műveleti szélesség bitben: A64-ben Wn operandusokkal 32, Xn operandusokkal 64. Legyen $k$ az eltolás bitszáma, egyelőre $0\leq k<n$ .

A64 művelet	Mozgatás	Megüresedő helyek	Kieső bitek
`LSL` — logical shift left	balra	alul nullák	elvesznek
`LSR` — logical shift right	jobbra	felül nullák	elvesznek
`ASR` — arithmetic shift right	jobbra	felül az eredeti előjelbit másolatai	elvesznek
`ROR` — rotate right	körkörösen jobbra	alulról kieső bitek kerülnek felülre	megmaradnak

Az utasítás nem tudja, milyen C-típust szántunk az adatnak. A megfelelő művelet kiválasztása a programozó feladata.

9.2.2.1 Balra tolás: szorzás, rögzített szélességen

A64: LSL X2, X1, #3 három bitpozícióval balra tolja az X1 tartalmát. Az előjel nélküli eredmény levezetése:

$r=(u\cdot 2^k)\bmod 2^n.$

Itt $u$ és $r$ dimenzió nélküli egész értékek. Minden megmaradó bit helyi értéke $2^k$ -szorosára nő; az $n$ bites tartományon túli bitek elvesznek.

Ezért 13 három bites balra tolása 104. A szorzás azonban csak akkor pontos, ha nincs eldobott, értékes felső bit. Például 32 bites előjel nélküli olvasatban a 0x80000000 egybites balra tolása nulla, nem pedig egy 33 bites eredmény.

Előjeles kettes komplemens értéknél ugyanaz a bitművelet használható szorzásra, ha a matematikai eredmény reprezentálható. Ez nem azonos a C << teljes szabályrendszerével: a laborhoz viszonyításként használt C11/C17-ben negatív előjeles operandus balra tolása nem definiált viselkedés.

9.2.2.2 Logikai jobbra tolás: előjel nélküli osztás

A64: LSR X2, X1, #3 felül nullákat léptet be. Előjel nélküli olvasatban:

$r=\left\lfloor\frac{u}{2^k}\right\rfloor.$

A kieső alsó $k$ bit az osztási maradékot hordozta. Így 107 három bites logikai jobbra tolásának eredménye 13.

Negatív előjeles értékhez ez rendszerint rossz választás: a nullákkal feltöltött felső rész pozitív eredményt hoz létre, nem tartja meg az előjelet.

9.2.2.3 Aritmetikai jobbra tolás: előjelmegőrzés, eltérő kerekítés

A64: ASR X2, X1, #1 a felső helyeket az eredeti 63. bit másolataival tölti ki. Kettes komplemens, előjeles olvasatban:

$r=\left\lfloor\frac{s}{2^k}\right\rfloor.$

Ez negatív végtelen felé kerekít, míg a C előjeles egész osztása nulla felé csonkol:

Művelet	Várt, előjeles eredmény
C: `-7 / 2`	-3
A64: -7 aritmetikai jobbra tolása 1 bittel	-4
A64: -8 aritmetikai jobbra tolása 1 bittel	-4

Negatív, pontosan osztható értéknél nincs különbség. Egyébként korrekció kell. $1\leq k<n$ esetén:

$q= \left\lfloor \frac{s+\begin{cases} 2^k-1,&s<0,\\ 0,&s\geq0 \end{cases}} {2^k} \right\rfloor.$

A hozzáadott korrekció (bias) a negatív értékek kerekítését nulla felé módosítja. Például $(-7+1)/2=-3$ .

A64-ben a 63 bites ASR 64 bites operanduson nulla vagy csupa egyes bitmintát állít elő: ez az előjelmaszk (sign mask). A labor ezt maszkolja egyre, majd hozzáadja az osztandóhoz.

C11/C17-ben negatív előjeles érték jobbra tolása implementációfüggő; ezért a C / helyettesítését ne pusztán egy C >> kifejezés látványa alapján igazold.

9.2.3 Forgatás és mezőkezelés

A64: a ROR W7, W6, #8 utasítás 32 bites körön forgat:

Állapot	32 bites bitminta, hexadecimálisan
Bemenet	`0x11223344`
Jobbra forgatás 8 bittel	`0x44112233`
Az eredmény alsó bájtja	`0x33`

Ez bájtok körkörös átrendezése, nem általános bájtsorrend-megfordítás. A forgatás önmagában nem emel ki mezőt: a többi bitet is megtartja. A labor ezért utána A64 AND művelettel megtartja az alsó bájtot.

Ha kizárólag az eredeti 8–15. bit kell, az A64 LSR és maszkolás általában közvetlenebb megoldás. A forgatás akkor hasznos, ha a többi bitet is meg kell őrizni, vagy a mező a szóhatáron körbeforduló elrendezés része.

Két bájt csomagolására például az A64 ORR W2, W0, W1, LSL #8 alkalmas, ha mindkét bemeneti regiszterben csak az alsó nyolc bit lehet nem nulla. Ellenkező esetben előzetes maszkolás szükséges. A speciális mezőutasításokat a Bitfield-utasítások: BFI/UBFX/SBFX és csomagolt adatszerkezetek tárgyalja.

A regiszteren belüli bitpozíciók jelentése nem függ a memória bájtsorrendjétől. A little-endian sorrend akkor válik fontossá, amikor ezeket a regiszterértékeket memóriába írjuk vagy onnan olvassuk.

9.2.4 Kódolási korlátok és beágyazott eltolás

A64 immediate-alakok: mind a négy műveletnél a közvetlen eltolás Wn operandusokkal 0–31, Xn operandusokkal 0–63. A teljes szélességgel való immediate-eltolás nem kódolható ezekben az alakokban.

A64 regiszteres alakok: az eltolásszám alsó öt, illetve hat bitje számít. A LSL W2, W1, W3 tehát a W3 értékét modulo 32 használja. Ha W3 értéke 32, az effektív eltolás nulla, nem 32.

Ez lényegesen eltér a C-től: ott a negatív, illetve az egészérték-promóció utáni bal operandus szélességét elérő eltolásszám nem definiált viselkedést okoz.

A64 szélességi szabály: a Wn célregiszter írása a megfelelő Xn felső 32 bitjét nullázza. Egy 32 bites ASR tehát nem végez automatikus, 64 bitre történő előjel-kiterjesztést.

A beágyazott eltolás (shifted operand) egy másik utasítás bemenetét módosítja. Például A64-ben:

ADD X12, X10, X11, LSL #3

jelentése: X12 = X10 + 8 × X11, 64 bites moduláris aritmetikával. Nyolcbájtos tömbelemnél ez az indexből származó eltolás hozzáadása az alaphoz.

Az A64 ADD eltolt regiszteres alakja LSL, LSR vagy ASR módot fogad, ROR módot nem. A tartomány itt is 0–31 vagy 0–63. Az A64 logikai utasítások, például az ORR, eltolt regiszteres alakjában ROR is megengedett.

Kevesebb utasítás nem jelent garantáltan kisebb késleltetést: ez mikroarchitektúra- és függőségfüggő kérdés. QEMU alatt nem állapítható meg hardverhű abszolút ciklusszám.

Végül: az A64 LSL, LSR, ASR és ROR nem módosítja az NZCV állapotjelzőket, és nem teszi a kieső bitet a C jelzőbe.

9.2.5 Kidolgozott példa: önellenőrző shift-labor

Munkakönyvtár: ~/arm-labor/a64/a033/ — 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/a033
cd ~/arm-labor/a64/a033

A lab-shift.s hét ellenőrzési csoportot tartalmaz. Siker esetén nulla, hibánál az érintett csoport száma a kilépési állapot. Nincs szöveges programkimenet.

A64 ISA, ARMv8-A; GNU assembler, AArch64 ELF:

.arch armv8-a
.text
.global _start
.type _start, %function

_start:
    movz    w0, #1
    movz    x1, #13
    lsl     x2, x1, #3
    cmp     x2, #104
    b.ne    lab_exit

    movz    w0, #2
    lsr     x6, x2, #3
    cmp     x6, x1
    b.ne    lab_exit

    movz    w0, #3
    movn    x3, #6               // X3 = ~6 = -7
    asr     x4, x3, #1
    cmn     x4, #4               // -4 + 4 == 0?
    b.ne    lab_exit

    movz    w0, #4
    asr     x5, x3, #63          // előjelmaszk
    and     x5, x5, #1           // negatívhoz 1, különben 0
    add     x5, x3, x5
    asr     x5, x5, #1
    cmn     x5, #3               // -3 + 3 == 0?
    b.ne    lab_exit

    movz    w0, #5
    movz    w6, #0x3344
    movk    w6, #0x1122, lsl #16
    ror     w7, w6, #8
    movz    w15, #0x2233
    movk    w15, #0x4411, lsl #16
    cmp     w7, w15
    b.ne    lab_exit
    and     w9, w7, #0xff
    cmp     w9, #0x33
    b.ne    lab_exit

    movz    w0, #6
    movz    x10, #100
    movz    x11, #7
    add     x12, x10, x11, lsl #3
    cmp     x12, #156
    b.ne    lab_exit

    movz    w0, #7
    movz    w13, #32
    lsl     w14, w1, w13
    cmp     w14, w1
    b.ne    lab_exit

lab_done:
    movz    x0, #0

lab_exit:
    movz    x8, #93              // Linux AArch64: exit
    svc     #0

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

A 100 itt egész tesztadat, nem memóriacím; a program nem dereferálja.

A kiegészítő A64 immediate-ok is kódolhatók: a MOVZ/MOVN/MOVK 16 bites mezőt fogad; Wn esetén a fél szó eltolása 0 vagy 16, Xn esetén 0, 16, 32 vagy 48. A CMP/CMN itt használt konstansai beleférnek az eltolatlan 12 bites immediate-ba; ezek az alakok opcionális 12 bites balra tolást is engednek. Az AND maszkjai összefüggő egyesekből álló, kódolható logikai immediate-ok. Az SVC immediate-mezője 16 bites.

Build és futtatás — Ubuntu 24.04 x86_64 host, cél: AArch64 qemu-user, little-endian:

aarch64-linux-gnu-as -march=armv8-a -EL -g \
    -o lab-shift.o lab-shift.s
aarch64-linux-gnu-ld -EL -e _start \
    -o lab-shift lab-shift.o
qemu-aarch64 ./lab-shift
printf 'Kilépési állapot: %d\n' "$?"

Várt, levezetett kimenet: Kilépési állapot: 0. A példa itt nem került futtatásra.

A lab_done címkénél várható A64-regiszterállapot:

Regiszter	Várt tartalom	Olvasat
`X2`	104	előjel nélküli
`X3`	`0xfffffffffffffff9`	előjeles: -7
`X4`	`0xfffffffffffffffc`	előjeles: -4
`X5`	`0xfffffffffffffffd`	előjeles: -3
`W6`	`0x11223344`	bitminta
`W7`	`0x44112233`	bitminta
`W9`	`0x33`	előjel nélküli bájtérték
`X12`	156	előjel nélküli
`W14`	13	effektív eltolás: nulla

9.2.6 Hibák és ellenpróbák

A hibakeresés menete: tünet → hipotézis → adatgyűjtés → egy változtatás → új ellenőrzés.

Negatív osztásnál egyesével eltérő eredmény: valószínűleg hiányzik a korrekció. Próbáld az előjeles -8, -7, 0 és 7 értékeket; a puszta ASR hibája csak bizonyos negatív bemeneteken látszik.
Szélességnyi eltolás után változatlan érték: regiszteres eltolásnál a számláló maszkolása lehet az ok. Ellenőrizd a számlálót és a Wn/Xn szélességet.
Hibás feltételes ugrás: a shift nem állította az NZCV-t. Tegyél közvetlen eredmény-összehasonlítást az elágazás elé.
Váratlan mnemonic a visszafejtésben: az immediate-alakok álnevek (aliases): A64 LSL/LSR mögött UBFM, ASR mögött SBFM, ROR mögött EXTR állhat. Ez nem fordítási hiba.

A qemu-user célprogram visszafejtése; a parancsok várt kilépési állapota 0:

aarch64-linux-gnu-objdump -d lab-shift
aarch64-linux-gnu-objdump -d -M no-aliases lab-shift

Regiszterellenőrzés, cél: qemu-user. Első terminál:

qemu-aarch64 -g 1234 ./lab-shift

Második terminál; siker esetén a fenti táblázat állapota, majd normál kilépés várható:

gdb-multiarch -q ./lab-shift \
    -ex 'target remote localhost:1234' \
    -ex 'break lab_done' \
    -ex 'continue' \
    -ex 'info registers x2 x3 x4 x5 x6 x7 x9 x12 x14' \
    -ex 'continue' \
    -ex 'quit'

Hibás változatnál a lab_done nem feltétlenül érhető el: ilyenkor a töréspontot lab_exit címkére helyezd.

9.2.7 Feladatok

(magyarázó, alapszint — cél: megértés-ellenőrzés) Számítsd ki 32 bites A64 műveletekkel a 0x80000001 egybites LSL, LSR, ASR és ROR eredményét. Miért egyezik két eredmény, és miért nem általános ez?
(implementációs, középszint — cél: rutinépítés) Módosítsd a labor negyedik csoportját úgy, hogy az előjeles X3 értéket nyolccal ossza, a C nulla felé csonkolásával. Tesztelj -9, -8, -7, 0, 7 és 8 bemenetet.
(hibakeresési, középszint — cél: rutinépítés) A hetedik csoportban kizárólag a számlálót változtasd 32-ről 31-re. Mi lesz a kilépési állapot és a W14 tartalma? Ezután külön ellenpróbaként próbálj immediate LSL W14, W1, #32 utasítást összeszerelni.

9.2.8 Megoldások

1. megoldás — Segítség. A 0x80000001 legfelső és legalsó bitje is 1 — melyik két művelet viselkedik ekkor azonosan, és milyen bemenetnél derülne ki a különbség?

1. megoldás — Teljes megoldás. A64, 32 bites eredmények:

Művelet	Eredmény
`LSL #1`	`0x00000002`
`LSR #1`	`0x40000000`
`ASR #1`	`0xc0000000`
`ROR #1`	`0xc0000000`

Az utolsó kettő azért egyezik, mert az eredeti előjelbit és az alsó bit egyaránt egy. A 0x80000000 ellenpélda: aritmetikai jobbra tolása 0xc0000000, forgatása 0x40000000.

2. megoldás — Segítség. Az ASR-rel történő osztás lefelé kerekít, nem nulla felé — negatív bemenetnél szükség van egy korrekciós tagra, mielőtt az eltolás megtörténne. Gondold át, mekkora korrekció kell -9-nél és mekkora 0-nál.

2. megoldás — Teljes megoldás. A labor negyedik csoportjának számítási részét cseréld erre. A64 ISA; a meglévő teljes laborba illesztendő:

asr     x5, x3, #63
and     x5, x5, #7
add     x5, x3, x5
asr     x5, x5, #3

A #7 kódolható logikai immediate. A korrekció negatív bemenetnél hét, különben nulla. A várt előjeles eredmények rendre -1, -1, 0, 0, 0, 1. A csoport összehasonlítását is az adott várt értékhez kell igazítani; a build- és futtatási parancsok változatlanok.

3. megoldás — Segítség. Egy 32 bites regiszterben 31 bites balra tolás után hány bit marad az eredeti mintából? Az immediate eltolásmező hány bitet tud kódolni?

3. megoldás — Teljes megoldás. Várt: kilépési állapot 7, W14 = 0x80000000. A 13 bitmintájából 31 bites balra toláskor csak a legalacsonyabb egyes bit marad meg a felső pozícióban. Az immediate #32 viszont 32 bites alakban nem kódolható: assemblerhibát és sikertelen assemble-lépést várunk. A regiszteres számláló maszkolása nem vonatkozik az immediate szintaxisára.

9.2.9 Rövid összefoglaló

A bitmozgatás helyességét a műveleti szélesség, az előjeles vagy előjel nélküli értelmezés és a kieső bitek szerepe határozza meg. A balra tolás moduláris szorzás, a logikai jobbra tolás előjel nélküli osztás. Az aritmetikai jobbra tolás megőrzi az előjelet, de negatív értékeknél eltérhet a C osztásának kerekítésétől. A forgatás nem veszít biteket, ezért mezőkiemeléskor maszkolás is kellhet. A beágyazott eltolás egyszerűsítheti a címzési és csomagolási számításokat, gyorsulását azonban külön kell mérni. Mindig ellenőrizd a szélső eltolásszámokat.

Logikai eltolás: nullákat beléptető bitmozgatás.
Aritmetikai jobbra tolás: az eredeti előjelbitet másoló eltolás.
Forgatás: a kieső biteket a másik oldalon visszahelyező bitmozgatás.

9.2.10 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ó — DDI0487; A64 eltolások, forgatások és eltolt regiszteres operandusok. 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 operandusszintaxis és direktívák. Tartalmilag ellenőrizve: a jelenlegi kiadás binutils 2.47.
GNU objdump kézikönyv — visszafejtés és disassembler-beállítások. Ugyanaz a binutils 2.47-es kiadás.

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: a programot és a parancsokat itt nem futtattuk. A helyi Ubuntu 24.04 csomagverziókat, az assembler pontos hibaüzenetét és az álnevek tényleges megjelenítését a laborban kell ellenőrizni. A közölt eredmények ISA-szabályokból levezetett várakozások, nem mérési adatok.