2006/12/13

河內塔 in TOY Assembly

首先是 JK-extended 版:

PROC hanoi
; parameters
; [RB + 2]   number of disks
; [RB + 3]   source peg
; [RB + 4]   intermediate peg
; [RB + 5]   destination peg

        ; base case
        ldi  RD, RB + 2
        bz   RD, end

        ; first recursive call
        ldi  RD, RB + 4
        push RD
        ldi  RD, RB + 5
        push RD
        ldi  RD, RB + 3
        push RD
        ldi  RD, RB + 2
        sub  RD, RD, RF
        push RD
        call hanoi
        sub  RE, RB, RF

        ; output
        ldi  RD, RB + 3
        shl  RD, RD, 4
        ldi  RC, RB + 5
        add  RD, RD, RC
        st   RD, 0xFF

        ; second recursive call
        ldi  RD, RB + 5
        push RD
        ldi  RD, RB + 3
        push RD
        ldi  RD, RB + 4
        push RD
        ldi  RD, RB + 2
        sub  RD, RD, RF
        push RD
        call hanoi

end     ret
ENDPROC

lda  RC, 2
push RC
lda  RC, 1
push RC
lda  RC, 0
push RC
ld   RC, 0xFF
push RC
call hanoi
add  RE, RE, 4

人工轉譯為 classical 版:

        lda RE, 0xFE    ; initialization
        lda RF, 1

        lda RC, 2
        sti RC, RE      ; push RC
        sub RE, RE, RF
        lda RC, 1
        sti RC, RE      ; push RC
        sub RE, RE, RF
        lda RC, 0
        sti RC, RE      ; push RC
        sub RE, RE, RF
        ld  RC, 0xFF
        sti RC, RE      ; push RC
        sub RE, RE, RF
        jl  RF, hanoi   ; call hanoi
        lda RF, 1       ; redundant
        lda RF, 4       ; add RE, RE, 4
        add RE, RE, RF
        lda RF, 1       ; redundant
        hlt

hanoi   sti RF, RE      ; PROC
        lda RF, 1
        sub RE, RE, RF
        sti RB, RE
        add RB, RE, R0
        sub RE, RE, RF
        lda RF, 2       ; ldi RD, RB + 2
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1       ; redundant
        bz  RD, end
        lda RF, 4       ; ldi RD, RB + 4
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sti RD, RE      ; push RD
        sub RE, RE, RF
        lda RF, 5       ; ldi RD, RB + 5
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sti RD, RE      ; push RD
        sub RE, RE, RF
        lda RF, 3       ; ldi RD, RB + 3
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sti RD, RE      ; push RD
        sub RE, RE, RF
        lda RF, 2       ; ldi RD, RB + 2
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sub RD, RD, RF
        sti RD, RE      ; push RD
        sub RE, RE, RF
        jl  RF, hanoi   ; call hanoi
        lda RF, 1
        sub RE, RB, RF
        lda RF, 3       ; ldi RD, RB + 3
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1       ; redundant
        lda RF, 4
        shl RD, RD, RF
        lda RF, 1       ; redundant
        lda RF, 5       ; ldi RC, RB + 5
        add RF, RB, RF
        ldi RC, RF
        lda RF, 1       ; redundant
        add RD, RD, RC
        st  RD, 0xFF
        lda RF, 5       ; ldi RD, RB + 5
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sti RD, RE      ; push RD
        sub RE, RE, RF
        lda RF, 3       ; ldi RD, RB + 3
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sti RD, RE      ; push RD
        sub RE, RE, RF
        lda RF, 4       ; ldi RD, RB + 4
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sti RD, RE      ; push RD
        sub RE, RE, RF
        lda RF, 2       ; ldi RD, RB + 2
        add RF, RB, RF
        ldi RD, RF
        lda RF, 1
        sub RD, RD, RF
        sti RD, RE      ; push RD
        sub RE, RE, RF
        jl  RF, hanoi   ; call hanoi
        lda RF, 1
end     add RE, RB, R0  ; ret
        ldi RB, RE
        add RE, RE, RF
        ldi RF, RE
        jr  RF

最後是 cyy 組譯器產出的 machine code:

10: 7EFE
11: 7F01
12: 7C02
13: BC0E
14: 2EEF
15: 7C01
16: BC0E
17: 2EEF
18: 7C00
19: BC0E
1A: 2EEF
1B: 8CFF
1C: BC0E
1D: 2EEF
1E: FF24
1F: 7F01
20: 7F04
21: 1EEF
22: 7F01
23: 0000
24: BF0E
25: 7F01
26: 2EEF
27: BB0E
28: 1BE0
29: 2EEF
2A: 7F02
2B: 1FBF
2C: AD0F
2D: 7F01
2E: CD73
2F: 7F04
30: 1FBF
31: AD0F
32: 7F01
33: BD0E
34: 2EEF
35: 7F05
36: 1FBF
37: AD0F
38: 7F01
39: BD0E
3A: 2EEF
3B: 7F03
3C: 1FBF
3D: AD0F
3E: 7F01
3F: BD0E
40: 2EEF
41: 7F02
42: 1FBF
43: AD0F
44: 7F01
45: 2DDF
46: BD0E
47: 2EEF
48: FF24
49: 7F01
4A: 2EBF
4B: 7F03
4C: 1FBF
4D: AD0F
4E: 7F01
4F: 7F04
50: 5DDF
51: 7F01
52: 7F05
53: 1FBF
54: AC0F
55: 7F01
56: 1DDC
57: 9DFF
58: 7F05
59: 1FBF
5A: AD0F
5B: 7F01
5C: BD0E
5D: 2EEF
5E: 7F03
5F: 1FBF
60: AD0F
61: 7F01
62: BD0E
63: 2EEF
64: 7F04
65: 1FBF
66: AD0F
67: 7F01
68: BD0E
69: 2EEF
6A: 7F02
6B: 1FBF
6C: AD0F
6D: 7F01
6E: 2DDF
6F: BD0E
70: 2EEF
71: FF24
72: 7F01
73: 1EB0
74: AB0E
75: 1EEF
76: AF0E
77: EF00

其中有一些 redundant instructions,可以想想組譯時如何消除。估計跑 16 個盤子沒問題,堆疊不會爆。

--
JK-extended assembler 當然沒那麼快寫好 XD。

Labels: ,