Torre di Hanoi - soluzione ricorsiva
Pubblicato da syscalo il 31/07/2000
Livello intermedio

Introduzione

Tutorial sulla programmazione in assembly in linux, usando la sintassi AT&T.
Ho scritto un programma per risolvere in modo ricorsivo il problema della Torre di Hanoi; tramite questo esempio, diciamo "ludico", possiamo vedere alcune cose relative alla programmazione assembly, come chiamate di funzioni, passaggio dei parametri, uso dello stack ecc.

Programmi usati

• gcc:

Iniziamo

Spiegazione del problema della torre di Hanoi:
Il problema della torre di Hanoi consiste nello spostare n dischi da un piolo ad un altro, avendo a disposizione 3 pioli; in pratica dobbiamo passare da una situazione di questo tipo (esempio con 2 dischi)

       __|__           |             |
     _|_____|_         |             |
 ___|_________|________|_____________|_______

         |           __|__           |
         |         _|_____|_         |
 ________|________|_________|________|_______

• si puo' spostare un solo disco alla volta da un piolo all'altro
• non si puo' appoggiare un disco su uno più piccolo

Ecco alcune indicazioni per capire meglio il codice sorgente e i commenti:

• le scritte "in..." "da..." "attraverso..." stanno ad indicare "in quale piolo voglio spostare...", "da quale piolo voglio spostare..." e "attraverso quale piolo voglio spostare..." il disco.
• gli offset per recuperare i parametri dallo stack devono partire da 8 perchè sono già presenti due valori sullo stack partendo da %ebp.
• dopo ogni chiamata a procedura è necessario pulire lo stack dai parametri passati alla procedura stessa.
• notate che nel programma vengono utilizzati diversi metodi di indirizzamento; ritengo sia poco utile spiegarli qui, in quanto sono facilmente reperibili su un testo che spiega la sintassi AT&T.
• è importante salvare i registri come indicato (sia a cura della procedura chiamata, sia quelli a cura della procedura chiamante) per non incorrere in errori di Segmentation fault.

# sezione dati
.data

Intestazione:
.asciz "\n\
###                                          ###\n\
#                                              #\n\
#      Soluzione ricorsiva torre di Hanoi      #\n\
#                                              #\n\
#              Scritto da syscalo              #\n\
#                                              #\n\
# file: hanoi.S                                #\n\
# compilare con: gcc -o hanoi hanoi.S          #\n\
#                                              #\n\
###                                          ###\n\
\n"

Movimenti:
.asciz "Muovi %d da %c a %c\n"

NumeroMosse:
.asciz "\nCon %d dischi sono necessarie %d mosse\n\n"

LeggiN:
.asciz "Quanti sono i dischi?"

d:
.ascii "%d"
# contatore numero di mosse da effettuare
Contatore:
.long 0

# numero di dischi
N:
.byte 0

## sezione codice
.text
.global main

main:

### salvataggio registri a cura della procedura chiamata ###
### %ebp, %ebx, %esi, %edi ###

  pushl %ebp
  movl %esp, %ebp     #allocazione stack frame
  pushl %ebx
  pushl %esi
  pushl %edi
 #visualizzazione Intestazione
  pushl $Intestazione
  call puts
  addl $4, %esp      #pulisce stack dai parametri
 #acquisizione numero dischi
  pushl $LeggiN
  call puts
  addl $4, %esp
  pushl $N
  pushl $d
  call scanf
  addl $8, %esp

 #passaggio parametri alla procedura hanoi
  pushl $'C'  #attraverso...
  pushl $'B'  #in...
  pushl $'A'  #da...
  pushl (N)   #numero dischi
  call hanoi
  addl $16, %esp

 #visualizzazione numero di mosse necessarie
  pushl (Contatore)
  pushl (N)
  pushl $NumeroMosse
  call printf
  addl $12, %esp

 #valore di ritorno in %eax: 0==tutto ok
  xorl %eax, %eax

 #ripristino registri
  popl %edi
  popl %esi
  popl %ebx
  movl %ebp, %esp     #disallocazione stack frame
  popl %ebp
  ret


 ###                     ###
 # Procedura hanoi         #
 #                         #
 # Chiamata ricorsivamente #
 ###                     ###


 hanoi:
  pushl %ebp          #salvataggio registro %ebp
  movl %esp, %ebp     #allocazione stack frame

 ### non salvo gli altri registri perchè non vengono usati ###


 #test sul numero di dischi
 #se c'è 1 disco esegue la singola mossa e termina

  cmpl $1, 8(%ebp)    #8(%ebp) contiene il numero di dischi
  jg piuDi1

 #visualizza il movimento da effettuare
  pushl 16(%ebp)      #in...
  pushl 12(%ebp)      #da...
  pushl 8(%ebp)       #numero disco
  pushl $Movimenti
  call printf
  addl $16, %esp
  incl Contatore
  jmp fine

 piuDi1:
 #chiama la procedura hanoi per un numero di dischi pari a n-1
  pushl 16(%ebp)      #in...
  pushl 20(%ebp)      #attraverso...
  pushl 12(%ebp)      #da...
  pushl 8(%ebp)       #numero disco:
  decl (%esp)         #n-1
  call hanoi
  addl $16, %esp

 #visualizza il movimento da effettuare
  pushl 16(%ebp)      #in...
  pushl 12(%ebp)      #da...
  pushl 8(%ebp)       #numero disco
  pushl $Movimenti
  call printf
  incl Contatore
  addl $16, %esp

 #chiama la procedura hanoi per un numero di dischi pari a n-1
  pushl 12(%ebp)      #da...
  pushl 16(%ebp)      #in...
  pushl 20(%ebp)      #attraverso...
  pushl 8(%ebp)       #numero disco:
  decl (%esp)         #n-1
  call hanoi
  addl $16, %esp

 fine:
  movl %ebp, %esp     #disallocazione stack frame
  popl %ebp           #ripristino registro %ebp
  ret

Conclusioni

That's all!