[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home] [volume] [parte]


Capitolo 562.   Esempi con gli array

In questo capitolo vengono mostrati alcuni esempi elementari di scansione di array, adatti alla compilazione con GNU AS e NASM. Si dà per scontato che si sappia utilizzare GDB per ispezionare la memoria e leggere, in particolare, il contenuto degli array stessi.

Negli esempi viene usata la direttiva .equ, o equ, per associare una sigla al livello in cui si trovano i dati nella pila (più precisamente nello stack frame).

Tutti gli esempi sono mostrati con listati a coppie: uno valido per GNU AS e l'altro per NASM.

562.1   Ricerca sequenziale

Viene mostrato un esempio di programma contenente una funzione che esegue una ricerca sequenziale all'interno di un array di interi, senza segno. Il metodo utilizzato si rifà a quanto descritto in pseudocodifica nella sezione 543.3.1. Il risultato della scansione viene emesso attraverso il valore restituito dal programma; ciò che si ottiene è precisamente l'indice dell'elemento trovato, oppure -1 se nessun elemento corrisponde.

# Ricerca sequenziale.
#
.section .data
lista:  .int    1, 4, 3, 7, 9, 10, 22, 44, 11, 23       # Interi senza segno.
a:      .int    0                                       # Indice minimo.
z:      .int    9                                       # Indice massimo.
#
.section .text
.globl _start
#
# Main.
#
_start:
    push  z                # f_rs ($lista, $7, a, z) ==> EAX
    push  a                # Si cerca il valore 7 nell'array
    push  $7               # «lista», tra gli indici «a» e «z».
    push  $lista           # Viene restituito l'indice dell'elemento
    call  f_rs             # trovato, oppure -1 se non è presente.
    add   $16, %esp        #
bp1:
    mov   %eax, %ebx       # Restituisce l'indice trovato,
    mov   $1, %eax         # ammesso che sia abbastanza piccolo
    int   $0x80            # da poter essere rappresentato come
                           # valore di uscita.
#
# Ricerca sequenziale all'interno di una lista di valori.
# f_rs (lista, x, a, z) ==> EAX
# Al termine EAX contiene l'indice del valore trovato,
# oppure -1 se questo non c'è.
#
f_rs:
    enter $4, $0
    pusha
    .equ  rs_i,     -4           # Gli si associa EAX.
    .equ  rs_lista,  8           # Gli si associa ESI.
    .equ  rs_x,     12           # Gli si associa EDX.
    .equ  rs_a,     16
    .equ  rs_z,     20
    #
    mov   rs_lista(%ebp), %esi   # ESI contiene l'indirizzo dell'array.
    mov   rs_x(%ebp),     %edx   # EDX contiene il valore cercato.
    #
    mov   rs_a(%ebp),     %eax   # EAX viene usato come indice di scansione.
f_rs_loop:
    cmp   rs_z(%ebp),     %eax   # Se EAX è maggiore dell'indice massimo,
    ja    f_rs_non_trovato       # l'elemento cercato non c'è.
    #
    cmp   (%esi,%eax,4),  %edx   # Se il valore cercato corrisponde a quello
    je    f_rs_trovato           # dell'indice corrente, termina la scansione.
    #
    inc   %eax                   # Incrementa l'indice di scansione e
    jmp   f_rs_loop              # salta all'inizio del ciclo.
    #
f_rs_non_trovato:
    popa                   # Conclude la funzione con EAX = -1.
    mov $-1, %eax          #
    leave                  #
    ret                    #
f_rs_trovato:
    mov %eax, rs_i(%ebp)   # Salva EAX nella variabile locale prevista.
    popa                   # Conclude la funzione con EAX pari
    mov rs_i(%ebp), %eax   # al valore salvato nella variabile
    leave                  # locale.
    ret                    #
; Ricerca sequenziale.
;
section .data
lista:  dd      1, 4, 3, 7, 9, 10, 22, 44, 11, 23       ; Interi senza segno.
a:      dd      0                                       ; Indice minimo.
z:      dd      9                                       ; Indice massimo.
;
section .text
global _start
;
; Main.
;
_start:
    push  long [z]         ; f_rs ($lista, $7, a, z) ==> EAX
    push  long [a]         ; Si cerca il valore 7 nell'array
    push  long 7           ; «lista», tra gli indici «a» e «z».
    push  lista            ; Viene restituito l'indice dell'elemento
    call  f_rs             ; trovato, oppure -1 se non è presente.
    add   esp, 16          ;
bp1:
    mov   ebx, eax         ; Restituisce l'indice trovato,
    mov   eax, 1           ; ammesso che sia abbastanza piccolo
    int   0x80             ; da poter essere rappresentato come
                           ; valore di uscita.
;
; Ricerca sequenziale all'interno di una lista di valori.
; f_rs (lista, x, a, z) ==> EAX
; Al termine EAX contiene l'indice del valore trovato,
; oppure -1 se questo non c'è.
;
f_rs:
    enter 4, 0
    pusha
    rs_i     equ -4              ; Gli si associa EAX.
    rs_lista equ  8              ; Gli si associa ESI.
    rs_x     equ 12              ; Gli si associa EDX.
    rs_a     equ 16
    rs_z     equ 20
    ;
    mov   esi, [rs_lista+ebp]    ; ESI contiene l'indirizzo dell'array.
    mov   edx, [rs_x+ebp]        ; EDX contiene il valore cercato.
    ;
    mov   eax, [rs_a+ebp]        ; EAX viene usato come indice di scansione.
f_rs_loop:
    cmp   eax, [rs_z+ebp]        ; Se EAX è maggiore dell'indice massimo,
    ja    f_rs_non_trovato       ; l'elemento cercato non c'è.
    ;
    cmp   edx, [esi+eax*4]       ; Se il valore cercato corrisponde a quello
    je    f_rs_trovato           ; dell'indice corrente, termina la scansione.
    ;
    inc   eax                    ; Incrementa l'indice di scansione e
    jmp   f_rs_loop              ; salta all'inizio del ciclo.
    ;
f_rs_non_trovato:
    popa                   ; Conclude la funzione con EAX = -1.
    mov eax, -1            ;
    leave                  ;
    ret                    ;
f_rs_trovato:
    mov [rs_i+ebp], eax    ; Salva EAX nella variabile locale prevista.
    popa                   ; Conclude la funzione con EAX pari
    mov eax, [rs_i+ebp]    ; al valore salvato nella variabile
    leave                  ; locale.
    ret                    ;

562.2   Ricerca binaria

Viene mostrato un esempio di programma contenente una funzione che esegue una ricerca binaria all'interno di un array ordinato, di interi con segno. Il metodo utilizzato si rifà a quanto descritto in pseudocodifica nella sezione 543.3.2. Il risultato della scansione viene emesso attraverso il valore restituito dal programma; ciò che si ottiene è precisamente l'indice dell'elemento trovato, oppure -1 se nessun elemento corrisponde.

# Ricerca binaria.
#
.section .data
lista:  .int    1, 3, 4, 7, 9, 10, 11, 22, 23, 44       # Interi con segno.
a:      .int    0                                       # Indice minimo.
z:      .int    9                                       # Indice massimo.
#
.section .text
.globl _start
#
# Main.
#
_start:
    push  z                # f_rb ($lista, $7, a, z) ==> EAX
    push  a                # Si cerca il valore 7 nell'array ordinato
    push  $7               # «lista», tra gli indici «a» e «z».
    push  $lista           # Viene restituito l'indice dell'elemento
    call  f_rb             # trovato, oppure -1 se non è presente.
    add   $16, %esp        #
bp1:
    mov   %eax, %ebx       # Restituisce l'indice trovato,
    mov   $1, %eax         # ammesso che sia abbastanza piccolo
    int   $0x80            # da poter essere rappresentato come
                           # valore di uscita.
#
# Ricerca binaria all'interno di una lista ordinata di valori.
# f_rb (lista, x, a, z) ==> EAX
# Al termine EAX contiene l'indice del valore trovato,
# oppure -1 se questo non c'è.
#
f_rb:
    enter $4, $0
    pusha
    .equ  rb_m,     -4           # Gli si associa EAX.
    .equ  rb_lista,  8           # Gli si associa ESI.
    .equ  rb_x,     12           # Gli si associa EDX.
    .equ  rb_a,     16
    .equ  rb_z,     20
    #
    mov   rb_lista(%ebp), %esi   # ESI contiene l'indirizzo dell'array.
    mov   rb_x(%ebp),     %edx   # EDX contiene il valore cercato.
                                 # EAX viene usato come «elemento centrale».
    #
    mov   rb_a(%ebp), %eax       # Calcola l'indice dell'elemento centrale
    add   rb_z(%ebp), %eax       # e lo mette in EAX. Lo scorrimento a
    sar   $1, %eax               # destra serve a dividere per due EAX.
    #
bp2:
    cmp   rb_a(%ebp), %eax       # Se EAX, ovvero l'indice, è minore
    jb    f_rb_non_trovato       # dell'indice minimo, l'elemento non c'è.
    #
    cmp   (%esi,%eax,4), %edx    # Se il valore cercato è minore di quello
    jl    f_rb_minore            # trovato, cerca nella parte inferiore;
    jg    f_rb_maggiore          # se è maggiore cerca in quella superiore;
    je    f_rb_fine              # se è uguale, l'elemento è stato trovato.
    #
f_rb_minore:
    dec   %eax
    push  %eax             # f_rb (lista, x, a, z) ==> EAX
    push  rb_a(%ebp)       # Si cerca il valore nell'array ordinato
    push  %edx             # «lista», tra gli indici «a» e «z».
    push  %esi             # Viene restituito l'indice dell'elemento
    call  f_rb             # trovato, oppure -1 se non è presente.
    add   $16, %esp        #
    jmp   f_rb_fine
    #
f_rb_maggiore:
    inc   %eax
    push  rb_z(%ebp)       # f_rb (lista, x, a, z) ==> EAX
    push  %eax             # Si cerca il valore nell'array ordinato
    push  %edx             # «lista», tra gli indici «a» e «z».
    push  %esi             # Viene restituito l'indice dell'elemento
    call  f_rb             # trovato, oppure -1 se non è presente.
    add   $16, %esp        #
    jmp   f_rb_fine
    #
f_rb_non_trovato:
    mov $-1, %eax          # Conclude la funzione con EAX = -1.
    jmp f_rb_fine
f_rb_fine:
    mov %eax, rb_m(%ebp)   # Salva EAX nella variabile locale prevista.
    popa                   # Conclude la funzione con EAX pari
    mov rb_m(%ebp), %eax   # al valore salvato nella variabile
    leave                  # locale.
    ret                    #
; Ricerca binaria.
;
section .data
lista:  dd      1, 3, 4, 7, 9, 10, 11, 22, 23, 44       ; Interi con segno.
a:      dd      0                                       ; Indice minimo.
z:      dd      9                                       ; Indice massimo.
;
section .text
global _start
;
; Main.
;
_start:
    push  long [z]         ; f_rb ($lista, $7, a, z) ==> EAX
    push  long [a]         ; Si cerca il valore 7 nell'array ordinato
    push  long 7           ; «lista», tra gli indici «a» e «z».
    push  lista            ; Viene restituito l'indice dell'elemento
    call  f_rb             ; trovato, oppure -1 se non è presente.
    add   esp, 16          ;
bp1:
    mov   ebx, eax         ; Restituisce l'indice trovato,
    mov   eax, 1           ; ammesso che sia abbastanza piccolo
    int   0x80             ; da poter essere rappresentato come
                           ; valore di uscita.
;
; Ricerca binaria all'interno di una lista ordinata di valori.
; f_rb (lista, x, a, z) ==> EAX
; Al termine EAX contiene l'indice del valore trovato,
; oppure -1 se questo non c'è.
;
f_rb:
    enter 4, 0
    pusha
    rb_m     equ -4              ; Gli si associa EAX.
    rb_lista equ  8              ; Gli si associa ESI.
    rb_x     equ 12              ; Gli si associa EDX.
    rb_a     equ 16
    rb_z     equ 20
    ;
    mov   esi, [rb_lista+ebp]    ; ESI contiene l'indirizzo dell'array.
    mov   edx, [rb_x+ebp]        ; EDX contiene il valore cercato.
                                 ; EAX viene usato come «elemento centrale».
    ;
    mov   eax, [rb_a+ebp]        ; Calcola l'indice dell'elemento centrale
    add   eax, [rb_z+ebp]        ; e lo mette in EAX. Lo scorrimento a
    sar   eax, 1                 ; destra serve a dividere per due EAX.
    ;
bp2:
    cmp   eax, [rb_a+ebp]        ; Se EAX, ovvero l'indice, è minore
    jb    f_rb_non_trovato       ; dell'indice minimo, l'elemento non c'è.
    ;
    cmp   edx, [esi+eax*4]       ; Se il valore cercato è minore di quello
    jl    f_rb_minore            ; trovato, cerca nella parte inferiore;
    jg    f_rb_maggiore          ; se è maggiore cerca in quella superiore;
    je    f_rb_fine              ; se è uguale, l'elemento è stato trovato.
    ;
f_rb_minore:
    dec   eax
    push  eax              ; f_rb (lista, x, a, z) ==> EAX
    push  long [rb_a+ebp]  ; Si cerca il valore nell'array ordinato
    push  edx              ; «lista», tra gli indici «a» e «z».
    push  esi              ; Viene restituito l'indice dell'elemento
    call  f_rb             ; trovato, oppure -1 se non è presente.
    add   esp, 16          ;
    jmp   f_rb_fine
    ;
f_rb_maggiore:
    inc   eax
    push  long [rb_z+ebp]  ; f_rb (lista, x, a, z) ==> EAX
    push  eax              ; Si cerca il valore nell'array ordinato
    push  edx              ; «lista», tra gli indici «a» e «z».
    push  esi              ; Viene restituito l'indice dell'elemento
    call  f_rb             ; trovato, oppure -1 se non è presente.
    add   esp, 16          ;
    jmp   f_rb_fine
    ;
f_rb_non_trovato:
    mov eax, -1            ; Conclude la funzione con EAX = -1.
    jmp f_rb_fine
f_rb_fine:
    mov [rb_m+ebp], eax    ; Salva EAX nella variabile locale prevista.
    popa                   ; Conclude la funzione con EAX pari
    mov eax, [rb_m+ebp]    ; al valore salvato nella variabile
    leave                  ; locale.
    ret                    ;

562.3   Bubblesort

Viene mostrato un esempio di programma che esegue il riordino di array attraverso l'algoritmo Bubblesort. L'array in question contiene numeri interi con segno. L'algoritmo è descritto in pseudocodifica nella sezione 543.4.1.

# Bubblesort
#
.section .data
lista:  .int    1, 4, 3, 7, 9, 10, 22, 44, 11, 23       # Interi con segno.
a:      .int    0                                       # Indice minimo.
z:      .int    9                                       # Indice massimo.
#
.section .text
.globl _start
#
# Main.
#
_start:
    push  z                # f_bs ($lista, a, z)
    push  a                # Riordina l'array «lista» senza restituire
    push  $lista           # alcun valore.
    call  f_bs             #
    add   $12, %esp        #
bp1:
    mov   $0, %ebx         # Restituisce sempre zero.
    mov   $1, %eax         #
    int   $0x80            #
#
# Riordino con l'algoritmo «bubblesort».
# f_bs (lista, a, z)
#
f_bs:
    enter $0, $0
    pusha
    .equ  bs_lista,  8        # EDX
    .equ  bs_a,     12        #
    .equ  bs_z,     16        #
                              #
    mov bs_lista(%ebp), %edx  # EDX contiene il riferimento alla lista.
                              #
                              # ESI viene usato come indice di scansione.
                              # EDI viene usato come indice di scansione.
                              # EAX viene usato per scambiare i valori.
                              # EBX viene usato per scambiare i valori.
    mov   bs_a(%ebp), %esi    # ESI parte dall'indice iniziale.
f_bs_loop_1:
    cmp   bs_z(%ebp), %esi    # Se ESI >= z, termina.
    jae   f_bs_end_loop_1     #
    #
    mov   %esi, %edi          # EDI := ESI - 1
    inc   %edi                #
f_bs_loop_2:
    cmp   bs_z(%ebp), %edi    # Se EDI > z, termina.
    ja    f_bs_end_loop_2     #
    #
    mov   (%edx,%esi,4), %eax # Se EBX < EAX scambia i valori
    mov   (%edx,%edi,4), %ebx #
    cmp   %eax, %ebx          #
    jl    f_bs_scambio        #
f_bs_loop_2_inc_edi:
    inc   %edi                # EDI++
    jmp   f_bs_loop_2         #
f_bs_scambio:
    mov   %eax, (%edx,%edi,4) # lista[ESI] :==: lista[EDI]
    mov   %ebx, (%edx,%esi,4) #
    jmp   f_bs_loop_2         #
f_bs_end_loop_2:
    inc   %esi                # ESI++
    jmp   f_bs_loop_1         #
f_bs_end_loop_1:
    popa
    leave
    ret
; Bubblesort
;
section .data
lista:  dd      1, 4, 3, 7, 9, 10, 22, 44, 11, 23       ; Interi con segno.
a:      dd      0                                       ; Indice minimo.
z:      dd      9                                       ; Indice massimo.
;
section .text
global _start
;
; Main.
;
_start:
    push  long [z]         ; f_bs ($lista, a, z)
    push  long [a]         ; Riordina l'array «lista» senza restituire
    push  long lista       ; alcun valore.
    call  f_bs             ;
    add   esp, 12          ;
bp1:
    mov   ebx, 0           ; Restituisce sempre zero.
    mov   eax, 1           ;
    int   0x80             ;
;
; Riordino con l'algoritmo «bubblesort».
; f_bs (lista, a, z)
;
f_bs:
    enter 0, 0
    pusha
    bs_lista equ  8           ; EDX
    bs_a     equ 12           ;
    bs_z     equ 16           ;
                              ;
    mov   edx, [bs_lista+ebp] ; EDX contiene il riferimento alla lista.
                              ;
                              ; ESI viene usato come indice di scansione.
                              ; EDI viene usato come indice di scansione.
                              ; EAX viene usato per scambiare i valori.
                              ; EBX viene usato per scambiare i valori.
    mov   esi, [bs_a+ebp]     ; ESI parte dall'indice iniziale.
f_bs_loop_1:
    cmp   esi, [bs_z+ebp]     ; Se ESI >= z, termina.
    jae   f_bs_end_loop_1     ;
    ;
    mov   edi, esi            ; EDI := ESI - 1
    inc   edi                 ;
f_bs_loop_2:
    cmp   edi, [bs_z+ebp]     ; Se EDI > z, termina.
    ja    f_bs_end_loop_2     ;
    ;
    mov   eax, [edx+esi*4]    ; Se EBX < EAX scambia i valori.
    mov   ebx, [edx+edi*4]    ;
    cmp   ebx, eax            ;
    jl    f_bs_scambio        ;
f_bs_loop_2_inc_edi:
    inc   edi                 ; EDI++
    jmp   f_bs_loop_2         ;
f_bs_scambio:
    mov   [edx+edi*4], eax    ; lista[ESI] :==: lista[EDI]
    mov   [edx+esi*4], ebx    ;
    jmp   f_bs_loop_2         ;
f_bs_end_loop_2:
    inc   esi                 ; ESI++
    jmp   f_bs_loop_1         ;
f_bs_end_loop_1:
    popa
    leave
    ret

Per verificare il funzionamento del programma si deve usare necessariamente GDB. Inizialmente, prima di mettere in esecuzione il programma, si vede l'array nel suo stato originale:

(gdb) print (int[10])lista[Invio]

$1 = {1, 4, 3, 7, 9, 10, 22, 44, 11, 23}

Si fissa quindi uno stop e si avvia il programma:

(gdb) break bp1[Invio]

(gdb) run[Invio]

Quando il programma viene sospeso in corrispondenza di bp1, l'array è ordinato:

(gdb) print (int[10])lista[Invio]

$1 = {1, 3, 4, 7, 9, 10, 11, 22, 23, 44}

Appunti di informatica libera 2008 --- Copyright © 2000-2008 Daniele Giacomini -- <appunti2 (ad) gmail·com>


Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome esempi_con_gli_array.htm

[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home]

Valid ISO-HTML!

CSS validator!

Gjlg Metamotore e Web Directory