Arkitektur og operativsystemer (dArkOS)

Besvarelse af ugeopgave, uge 37

Per Abrahamsen, 20001358, 3,
Mads Peter Lindberg, 20001990, 3,
Søren S. Munk, 20001614, 3.

Towers of Hanoi i Java

Et Java program til løsning af Towers of Hanoi svarende til SCO figur 5-40, ser således ud:
public class Hanoi { public static void main(String[] args) { towers(3, 1, 3); } private static void towers(int n, int i, int j) { int k; if(n==1) System.out.println("move a disk from "+i+ " to "+j); else{ k=6-i-j; towers(n-1, i, k); towers(1, i, j); towers(n-1, k, j); } } }
Kørsel med towers(3,1,3) gav resultatet:
move a disk from 1 to 3 move a disk from 1 to 2 move a disk from 3 to 2 move a disk from 1 to 3 move a disk from 2 to 1 move a disk from 2 to 3 move a disk from 1 to 3
Alle dele af programmet køres. Den forklarer hvordan man flytter skiverne fra 1 til 3. Alle dele af programmet bruges, da if-sætningen i første omgang evaluerer til false og else-delen udføres. Da towers kaldes med n-1 bliver towers på et eller andet tidspunkt kaldt med n==1 og derfor udføres if-delen. Da main ikke indeholder nogen kontrolstrukturer afvilkes alle liner og towers kaldes.

Det oversatte Java program i symbolsk bytecode udgave ser således ud:

Compiled from Hanoi.java public class Hanoi extends java.lang.Object { public Hanoi(); public static void main(java.lang.String[]); } Method Hanoi() 0 aload_0 1 invokespecial #1 <Method java.lang.Object()> 4 return Method void main(java.lang.String[]) 0 iconst_3 1 iconst_1 2 iconst_3 3 invokestatic #2 <Method void towers(int, int, int)> 6 return Method void towers(int, int, int) 0 iload_0 1 iconst_1 2 if_icmpne 42 5 getstatic #3 <Field java.io.PrintStream out> 8 new #4 <Class java.lang.StringBuffer> 11 dup 12 invokespecial #5 <Method java.lang.StringBuffer()> 15 ldc #6 <String "move a disk from "> 17 invokevirtual #7 <Method java.lang.StringBuffer append(java.lang.String)> 20 iload_1 21 invokevirtual #8 <Method java.lang.StringBuffer append(int)> 24 ldc #9 <String " to "> 26 invokevirtual #7 <Method java.lang.StringBuffer append(java.lang.String)> 29 iload_2 30 invokevirtual #8 <Method java.lang.StringBuffer append(int)> 33 invokevirtual #10 <Method java.lang.String toString()> 36 invokevirtual #11 <Method void println(java.lang.String)> 39 goto 71 42 bipush 6 44 iload_1 45 isub 46 iload_2 47 isub 48 istore_3 49 iload_0 50 iconst_1 51 isub 52 iload_1 53 iload_3 54 invokestatic #2 <Method void towers(int, int, int)> 57 iconst_1 58 iload_1 59 iload_2 60 invokestatic #2 <Method void towers(int, int, int)> 63 iload_0 64 iconst_1 65 isub 66 iload_3 67 iload_2 68 invokestatic #2 <Method void towers(int, int, int)> 71 return
Sætningen k=6-i-j oversættes til:
42 bipush 6 //stack = 6 44 iload_1 //stack = 6, i 45 isub //stack = 6-i 46 iload_2 //stack = 6-i, j 47 isub //stack = 6-i-j 48 istore_3 //stack = Ø, k = 6-i-j
Ud for de enkelte ordrer er angivet relevante dele af stakkens udseende efter udførelsen af den pågældende ordre.

Towers of Hanoi i C

Et C-program til løsning af Towers of Hanoi svarende til SCO figur 5-40, ser således ud:
#include <stdio.h> void towers(int n, int i, int j) { int k; if(n==1) printf("move a disk from %d to %d\n",i,j); else{ k=6-i-j; towers(n-1, i, k); towers(1, i, j); towers(n-1, k, j); } } int main() { towers(3, 1, 3); return 0; }
Kørsel med towers(3,1,3) gav resultatet:
move a disk from 1 to 3 move a disk from 1 to 2 move a disk from 3 to 2 move a disk from 1 to 3 move a disk from 2 to 1 move a disk from 2 to 3 move a disk from 1 to 3

Det oversatte C-program i symbolsk maskinsprogsudgave til MIPS R10000 ser således ud:

(herover er der en god del .byte vi ikke mener er spændende) towers: .LFB1: .frame $fp,64,$31 # vars= 16, regs= 3/0, args= 0, extra= 16 .mask 0xd0000000,-16 .fmask 0x00000000,0 subu $sp,$sp,64 .LCFI0: sd $31,48($sp) .LCFI1: sd $fp,40($sp) .LCFI2: sd $28,32($sp) .LCFI3: move $fp,$sp .LCFI4: .set noat lui $1,%hi(%neg(%gp_rel(towers))) addiu $1,$1,%lo(%neg(%gp_rel(towers))) daddu $gp,$1,$25 .set at sw $4,16($fp) sw $5,20($fp) sw $6,24($fp) lw $2,16($fp) li $3,1 # 0x1 bne $2,$3,.L3 la $4,.LC0 lw $5,20($fp) lw $6,24($fp) la $25,printf jal $31,$25 b .L4 .L3: li $2,6 # 0x6 lw $3,24($fp) subu $2,$2,$3 lw $3,20($fp) subu $2,$2,$3 sw $2,28($fp) lw $3,16($fp) addu $2,$3,-1 move $4,$2 lw $5,20($fp) lw $6,28($fp) la $25,towers jal $31,$25 li $4,1 # 0x1 lw $5,20($fp) lw $6,24($fp) la $25,towers jal $31,$25 lw $3,16($fp) addu $2,$3,-1 move $4,$2 lw $5,28($fp) lw $6,24($fp) la $25,towers jal $31,$25 .L4: .L2: move $sp,$fp ld $31,48($sp) ld $fp,40($sp) ld $28,32($sp) addu $sp,$sp,64 j $31 .LFE1: .end towers .align 2 .globl main .ent main main: .LFB2: .frame $fp,48,$31 # vars= 0, regs= 3/0, args= 0, extra= 16 .mask 0xd0000000,-16 .fmask 0x00000000,0 subu $sp,$sp,48 .LCFI5: sd $31,32($sp) .LCFI6: sd $fp,24($sp) .LCFI7: sd $28,16($sp) .LCFI8: move $fp,$sp .LCFI9: .set noat lui $1,%hi(%neg(%gp_rel(main))) addiu $1,$1,%lo(%neg(%gp_rel(main))) daddu $gp,$1,$25 .set at li $4,3 # 0x3 li $5,1 # 0x1 li $6,3 # 0x3 la $25,towers jal $31,$25 move $2,$0 b .L5 .L5: move $sp,$fp ld $31,32($sp) ld $fp,24($sp) ld $28,16($sp) addu $sp,$sp,48 j $31 .LFE2: .end main
Sætningen k=6-i-j oversættes til:
li $2,6 # $2=6 lw $3,24($fp) # $3=j j ligger 24 bytes over fp subu $2,$2,$3 # $2=6-j lw $3,20($fp) # $3=i i ligger så 20 bytes over fp subu $2,$2,$3 # $2=6-j-i sw $2,28($fp) # k =6-j-i gemmes i k 28 over fp
Ud for de enkelte ordrer er angivet de relevante registres indhold efter udførelsen af den pågældende ordre.