7.2 Tömbök és indexelt elérés assemblyben

7.2.1 Miért számít az elemméret?

Egy képfeldolgozó rutin, ellenőrzőösszeg-számítás vagy protokollfeldolgozó rendszer gyakran tömbökön dolgozik. C-ben az a[i] kifejezés elrejti az elemmérettel történő szorzást. Assemblyben ezt nekünk kell helyesen kifejeznünk: a processzor memóriacíme bájtot jelöl, nem tömbelemet.

Ebben az alfejezetben az egydimenziós indexeléstől eljutunk a sorfolytonos kétdimenziós tömbig és egy önellenőrző összegző programig. Előfeltétel a Load/store címzési módok ismerete.

Profil: minden alábbi utasítás és regiszter az A64 ISA, AArch64, ARMv8-A környezetéhez tartozik. Az assemblydirektívák GNU as szintaxisúak, AArch64 ELF célhoz. A labor little-endian, Linux alatt, qemu-aarch64 user-mode emulációval fut. Cortex-M-kódot itt nem használunk.

7.2.2 Az indexből bájteltolás lesz

A skálázott indexelés (scaled indexing) az elemindexet az elemmérettel megszorozva alakítja bájteltolássá.

Legyen:

• $B$ a tömb első elemének bájtcíme;
• $i$ az előjel nélküli elemindex, dimenzió nélküli egész;
• $s$ az elemméret, bájt/elem egységben.

Ekkor:

$$\operatorname{cím}(a[i]) = B + i \cdot s$$

A képlet használatának előfeltétele, hogy i a tömb határain belül legyen, és a címképzés ne csorduljon túl. A hardver nem ismeri a C-tömb hosszát: egy hozzáférhető cím még nem feltétlenül a megfelelő objektumhoz tartozik.

Levezetés: ha az elemméret $s=2^k$, akkor az $i \cdot s$ szorzás az index $k$ bites balra tolásával állítható elő. Az A64 regisztereltolásos memóriautasítása ezt külön szorzóutasítás nélkül is kifejezheti.

Az A64 címzésbe épített eltolás tehát nem tetszőleges shift. Négybájtos hozzáférésnél például a LSL #1 nem kódolható ebben a címzési formában.

Ha az A64 X1 regiszter egy uint32_t tömb báziscíme, az X2 pedig az előjel nélküli index:

// A64 ISA: X1 = báziscím, X2 = elemindex.
ldr w3, [x1, x2, lsl #2]   // W3 = a[i]
str w3, [x1, x2, lsl #2]   // a[i] = W3

A hozzáférés négybájtos, a bázisregiszter változatlan marad. Az A64 LDR W3 a hozzá tartozó X3 felső 32 bitjét nullázza.

Ha az index 32 bites előjel nélküli érték az A64 W2 regiszterben, a megfelelő címzési alak például LDR W3, [X1, W2, UXTW #2]: előbb nullakiterjesztés történik 64 bitre, majd skálázás. Az index előjelkezelése és a betöltött adat előjelkezelése két külön kérdés.

7.2.3 Soros bejárás post-index címzéssel

Ha minden elemet sorrendben dolgozunk fel, nem szükséges minden iterációban újra előállítani a báziscím és az index összegét. Fenntarthatunk egy aktuális mutatót, amely minden feldolgozás után a következő elemre lép.

A következő C-függvény a labor összegző szakaszának szemantikai referenciája:

#include <stddef.h>
#include <stdint.h>

uint64_t sum_u32(const uint32_t *p, size_t n)
{
    uint64_t sum = 0;

    while (n != 0) {
        sum += *p++;
        --n;
    }
    return sum;
}

A megfelelő A64 post-index betöltés:

// A64 ISA: előbb olvasás az eredeti X1 címről, majd X1 += 4.
ldr w3, [x1], #4

A #4 bájteltolás, nem négy elem. A post-index immediate előjeles, 9 bites, ezért −256 és 255 bájt közötti érték lehet; a négybájtos lépés belefér.

A ciklus állapotát három mennyiség írja le:

1. az aktuális elem címe;
2. a hátralévő elemszám;
3. az eddigi összeg.

A ciklusinvariáns szerint $k$ feldolgozott elem után a mutató $B+4k$ bájtcímet tartalmaz, a számláló $n-k$, az akkumulátor pedig az első $k$ elem összege. Ez egyszerre segíti a program megírását és a hibakeresést.

Az üres bemenetet az első betöltés előtt kell felismerni. Ha a nulla számlálót előbb csökkentjük, az A64 64 bites regiszterében 0xffffffffffffffff keletkezik; ettől egy „nem nulla” feltételű ciklus nem fog helyesen leállni.

7.2.4 Kétdimenziós tömb: sorfolytonos elrendezés

A C valódi kétdimenziós tömbje, például a uint32_t m[2][3], sorfolytonos elrendezésű (row-major layout): először az első sor elemei következnek, majd a második soré.

Ha $K$ az oszlopszám, $r$ a sorindex, $c$ az oszlopindex, akkor:

$$\operatorname{cím}(m[r][c]) = B + (rK+c)\cdot s$$

Itt $r$, $c$ és $K$ dimenzió nélküli egész, $s$ az elemméret bájtban; feltétel a $0\le r<R$ és $0\le c<K$ tartomány, ahol $R$ a sorok száma.

Háromoszlopos, négybájtos elemekből álló tömbnél:

Az A64 MADD előállíthatja az $rK+c$ kifejezést, majd a skálázott betöltés elvégzi a bájteltolássá alakítást. Soronkénti feldolgozáskor a belső ciklus négybájtos post-index lépésekkel járhatja be az adott sort; a következő sor kezdete 12 bájttal később található.

Ez nem ugyanaz, mint a uint32_t **: a mutatótömb sorai külön memóriaterületeken is lehetnek, elérésükhöz további mutatóbetöltés szükséges.

7.2.5 Kidolgozott példa: indexelés, tárolás és összegzés

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

Mentsük a következő teljes programot lab-array.s néven. Három műveletet ellenőriz:

• az egydimenziós tömb 3-as indexű elemének betöltését és másik tömbbe tárolását;
• a mátrix m[1][2] elemének elérését;
• az első LAB_N elem összegzését.

A LAB_N fordításkor megadható, értéke 0–5 lehet. Az A64 X1 a két indexelt művelet során változatlan tömbbázis marad, majd az összegzés aktuális mutatója lesz.

// A64 ISA, GNU as, AArch64 Linux, little-endian.
.ifndef LAB_N
.equ LAB_N, 5
.endif

.if (LAB_N < 0) || (LAB_N > 5)
.error "LAB_N must be in 0..5"
.endif

.equ LAB_EXPECTED, 5 * LAB_N * (LAB_N + 1)

.section .text
.global _start
.type _start, %function

_start:
    adrp x1, lab_array
    add  x1, x1, :lo12:lab_array

    // lab_output[3] = lab_array[3]
    mov  x2, #3
    ldr  w3, [x1, x2, lsl #2]

    adrp x4, lab_output
    add  x4, x4, :lo12:lab_output
    str  w3, [x4, x2, lsl #2]
    ldr  w5, [x4, x2, lsl #2]
    cmp  w5, #40
    b.ne lab_fail

    // lab_matrix[1][2], három oszloppal.
    adrp x4, lab_matrix
    add  x4, x4, :lo12:lab_matrix
    mov  x5, #1
    mov  x6, #2
    mov  x7, #3
    madd x6, x5, x7, x6
    ldr  w3, [x4, x6, lsl #2]
    cmp  w3, #6
    b.ne lab_fail

    // Az első LAB_N elem összege.
    mov  x0, #0
    mov  x2, #LAB_N
    cbz  x2, lab_done

lab_loop:
    ldr  w3, [x1], #4
    add  x0, x0, x3
    subs x2, x2, #1
    cbnz x2, lab_loop

lab_done:
    cmp  x0, #LAB_EXPECTED
    b.ne lab_fail
    mov  x0, #0
    b    lab_exit

lab_fail:
    mov  x0, #1

lab_exit:
    mov  x8, #93
    svc  #0

.size _start, .-_start

.section .data
.balign 4
lab_array:
    .word 10, 20, 30, 40, 50
lab_array_end:
lab_guard:
    .word 99

lab_output:
    .word 0, 0, 0, 0, 0

lab_matrix:
    .word 1, 2, 3
    .word 4, 5, 6

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

A GNU as .word direktívája itt 32 bites elemeket helyez el; a .balign 4 négybájtos igazítást biztosít. A lab_guard külön őrszó, nem része az ötelemű logikai tömbnek.

A MOV, ADD, SUBS és CMP konstansai mind kódolhatók (lásd az A64 immediate-korlátok összefoglalóját). A címképző ADRP 4 KiB-os lapot választ; az utána következő ADD a cím alsó 12 bitjét adja hozzá. A szimbólumokra történő címképzést a linker oldja fel, nem kézzel választott memóriacímeket használunk.

Az A64 LDR W3 nullakiterjesztése miatt az ADD X0, X0, X3 a uint32_t elemet helyesen adja a 64 bites előjel nélküli összeghez. Általános bemenetnél ez az összeg modulo $2^{64}$ értendő; a labor kis számainál nincs túlcsordulás.

A kilépés a korábban tanult Linux syscall-konvenciót követi: a 93-as hívásszám Linux AArch64 ABI-előírás, nem az A64 ISA része.

7.2.6 Összeállítás és várt állapot

Cél: qemu-user, AArch64 little-endian Linux; host: Ubuntu 24.04 x86_64.

aarch64-linux-gnu-as -EL -march=armv8-a -g \
  --defsym LAB_N=5 -o lab-array.o lab-array.s
aarch64-linux-gnu-ld -EL -e _start -o lab-array lab-array.o
qemu-aarch64 ./lab-array
printf 'exit=%d\n' "$?"

Várt, nem itt mért kimenet: exit=0. A program maga nem ír a terminálra; eltéréskor 1-es állapottal lép ki.

A lab_done címkénél, még az ellenőrzés előtt:

Az elvárt összeg levezetése: az elemek $10,20,\ldots,10n$, ezért összegük $10n(n+1)/2=5n(n+1)$. Ezt számolja ki összeállításkor a LAB_EXPECTED szimbólum.

Az üres eset külön buildje, ugyanezen qemu-user célhoz:

aarch64-linux-gnu-as -EL -march=armv8-a -g \
  --defsym LAB_N=0 -o lab-empty.o lab-array.s
aarch64-linux-gnu-ld -EL -e _start -o lab-empty lab-empty.o
qemu-aarch64 ./lab-empty
printf 'exit=%d\n' "$?"

Itt is exit=0 várható. Az összegző szakasz nem olvas memóriát; az előtte álló indexelési önellenőrzések továbbra is lefutnak.

7.2.7 Tipikus hibák és célzott ellenpróbák

Hiányzó skálázás. Ha az A64 LDR W3, [X1, X2, LSL #2] helyett eltolás nélküli alakot írunk, az index bájteltolássá válik. A 3-as index ekkor nem 12, hanem 3 bájttal lép előre. Ez nem feltétlenül okoz szegmentálási hibát: hozzáférhető, de hibás helyről olvashatunk.

Rossz hozzáférési szélesség. Az A64 LDR X3, [X1], #4 nyolc bájtot olvasna, miközben csak négy bájttal léptet. A következő hozzáférés átfedne az előzővel. Előbb a betöltés szélességét, utána a lépésközt ellenőrizzük.

Előjeles adat nullakiterjesztése. int32_t elemek 64 bites előjeles összegzéséhez az A64 LDRSW X3, [X1], #4 adja a szükséges előjelkiterjesztést. A ciklusszerkezet ettől még változatlan lehet.

Egy elemmel túlfutó ciklus (off-by-one error). A program a tömb utáni őrszót is elérheti, ezért a sikeres memóriahozzáférés nem igazolja a helyes ciklushatárt.

A hibakeresés menete: tünet → hipotézis → adatgyűjtés → egyetlen módosítás → új ellenőrzés. Például hibás összeg esetén előbb állapítsuk meg, hány bájttal mozdult el a mutató.

Cél: a qemu-user labor disassembly-vizsgálata és távoli hibakeresése. Az első terminálban:

aarch64-linux-gnu-objdump -d lab-array
qemu-aarch64 -g 1234 ./lab-array

A második terminálban:

gdb-multiarch -q lab-array \
  -ex 'target remote :1234' \
  -ex 'break lab_done' \
  -ex 'continue' \
  -ex 'info registers x0 x1 x2' \
  -ex 'p/d $x1 - (unsigned long)&lab_array' \
  -ex 'x/6uw &lab_array' \
  -ex 'x/5uw &lab_output'

Öt elemnél a mutató különbségének várt értéke 20 bájt. A hat kiolvasott szó rendre 10, 20, 30, 40, 50, 99; az utolsó a szándékosan elhelyezett őrszó. A GDB continue parancsával a helyes program 0 állapottal befejeződik.

7.2.8 Feladatok

1. (magyarázó, alapszint — cél: megértés-ellenőrzés) Egy uint64_t a[7] tömbben mekkora az a[5] bájteltolása? Milyen skálázás kell az A64 regisztereltolásos betöltéshez? Miért nem használható hozzá LSL #2?

2. (implementációs, középszint — cél: rutinépítés) Készíts lab-array-u64.s változatot kizárólag a post-index összegzéshez, öt uint64_t elemmel: 10, 20, 30, 40, 50. Módosítsd az adatelhelyezést, az igazítást és a betöltést. A fenti qemu-user munkafolyamattal, lab-array-u64.o és lab-array-u64 nevekkel ellenőrizd a nulla-, egy- és ötelemű esetet.

3. (hibakeresési, középszint — cél: rutinépítés) Másold a programot lab-offby.s névre. Kizárólag az A64 CBNZ X2, lab_loop utasítást cseréld B.PL lab_loop utasításra. Öt elemre fordítsd lab-offby.o és lab-offby néven. A lab_done ponton vizsgáld meg az összeget, a mutatóeltolást és a számlálót. Miért nem szükségszerű a szegmentálási hiba?

7.2.9 Megoldások

1. megoldás — Segítség. Nézd meg a fejezet táblázatát: nyolcbájtos elemnél melyik LSL eltolások megengedettek a regisztereltolásos címzésben?

1. megoldás — Teljes megoldás. Az eltolás $5\cdot8=40$ bájt. A megfelelő A64 alak LDR X3, [X1, X2, LSL #3]. Nyolcbájtos hozzáférésnél a címzésben megengedett eltolás 0 vagy 3 bit; a #2 nem egyszerűen hibás elemméretet jelent, hanem ebben az alakban nem kódolható.

2. megoldás — Segítség. Csak az adatdirektívát (nyolcbájtos elemhez), az igazítást és a betöltés szélességét kell nyolcbájtosra cserélni — a ciklusvezérlés logikája változatlan maradhat.

2. megoldás — Teljes megoldás. A GNU as adatdirektíva .xword, az igazítás .balign 8. A ciklus betöltése A64 LDR X3, [X1], #8. A 64 bites akkumulátor és a számláló kezelése változatlan. Nulla, egy, illetve öt elem után a várt összeg 0, 10 és 150, a mutatóeltolás pedig 0, 8 és 40 bájt. Mindhárom esetben 0 kilépési állapot várható. A nyolcbájtos lépés belefér a post-index előjeles 9 bites immediate mezőjébe.

3. megoldás — Segítség. A B.PL nem ugyanazt a feltételt vizsgálja, mint a CBNZ — mi történik, ha a számláló előjeles olvasatban még “nem negatív”, de ténylegesen már 0xffffffffffffffff?

3. megoldás — Teljes megoldás. A SUBS után az A64 B.PL az N=0 feltételt vizsgálja. Az ötödik elem után a számláló nulla, tehát N=0, és még egy iteráció következik. Ez beolvassa a 99 értékű őrszót. A várt összeg 249, a mutatóeltolás 24 bájt, a számláló 0xffffffffffffffff. Az utolsó csökkentés már N=1 állapotot eredményez, így a ciklus kilép. Az önellenőrzés 1-es kilépési állapotot ad. Nem szükségszerű a memóriahiba, mert az őrszó a labor saját, hozzáférhető adatblokkjában található. A javítás a hátralévő elemszám nemnulla feltételének visszaállítása.

7.2.10 Rövid összefoglaló

A tömbindex elemben, a memóriacímzés bájtban értendő; a kettőt az elemméret kapcsolja össze. Az A64 skálázott regisztereltolása a hozzáférés méretéhez igazodó címképzést egy memóriautasításba sűríti, de nem végez határellenőrzést. Sorrendi feldolgozásnál a post-index betöltés egyszerre olvassa az aktuális elemet és lépteti a mutatót. Az üres bemenetet az első olvasás előtt kell kezelni. Kétdimenziós C-tömbnél az oszlopszám határozza meg a sor lépésközét. A helyességet az eredmény mellett a mutató és a számláló végállapota is ellenőrzi.

• Skálázott indexelés: elemindex átalakítása bájteltolássá az elemmérettel.
• Sorfolytonos elrendezés: egy sor elemei egymás mellett, a sorok egymás után helyezkednek el.
• Ciklusinvariáns: az iterációk azonos pontján fennálló állítás a feldolgozás állapotáról.

7.2.11 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 regisztereltolásos és post-index memóriautasítások. 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, adatdirektívák, kifejezések és --defsym. Tartalmilag ellenőrizve: a jelenlegi kiadás binutils 2.47.
• GNU GDB kézikönyv — távoli kapcsolat, töréspontok, regiszter- és memóriavizsgálat. Tartalmilag ellenőrizve, de verzió-megjegyzéssel: a „current” fejlesztői pillanatkép (közös verziókorlát).

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: a programokat itt nem állítottuk össze és nem futtattuk. A közölt eredmények levezetett, várt állapotok. Az Ubuntu 24.04 alatt telepített konkrét binutils-, GDB- és QEMU-csomagverziót, valamint a teljes laborfutást a hallgatói környezetben kell rögzíteni és ellenőrizni.