Assembly language programming project in Legv8 ARM language.

Filling in this template: Should have three stacks and complete the game. There is C code that basically needs to be written in ARM

// // cyclicHanoi.s // // Cyclic Tower of Hanoi game // // return the number of steps in x2

eor x2, x2, x2

// x19, x20, x21 are stack pointers for stacks A, B, C // stacks A, B, C grow upwards

addi x19, xzr, #0 // x19 = 0x0000 addi x20, xzr, #0x80 // x20 = 0x0080 addi x21, xzr, #0x100 // x21 = 0x0100

// place a very large disk of size 255 at the bottom of each stack

addi x15, xzr, #0xff // size of very large disk stur x15, [x19, #0] stur x15, [x20, #0] stur x15, [x21, #0]

// place disks n..1 on stack A

addi x4, xzr, #10 // n = 10 add x15, xzr, x4 loop: addi x19, x19, #8 stur x15, [x19, #0] subi x15, x15, #1 cbnz x15, loop

bl chanoi stop

chanoi:

//////////////////////////////////// // // Your code // ////////////////////////////////////

error: subi x2, xzr, #1 // return -1 if error br lr

ECE 30 Programming Project Winter 2020 Cyclic Hanoi due 6 pm Friday, March 13, 2020 The Tower of Hanoi is a mathematical game for moving a set of n disks stacked in the order of decreasing size from one pile to another (using a spare pile) one disk at a time without ever placing a larger disk on top of a smaller disk. The Cyclic Hanoi is derived from the Tower of Hanoi with a couple of restrictions: 1. There are 3 piles arranged in a circular fashion. 2. Disks can only be moved in a clockwise direction. Pile A (Source) Pile C (Spare) Pile B (Destination) 1 The algorithm for moving n disks can best be described in a recursive manner as described below: 1. Move the top n 1 disks to a spare pile. 2. Move the largest disk to the destination. 3. Move the n 1 disks from the spare pile to the destination. The algorithm becomes a bit more complex for the Cyclic Hanoi because of the second restriction: disks must be moved clockwise. Assuming that the disks are labeled from 1 to N from the smallest to the largest, to move n disks clockwise from pile A to pile B: 1. Move the top n 1 disks counterclockwise to pile C. 2. Move disk N clockwise to pile B. 3. Move the n 1 disks on pile C counterclockwise to pile B. Note that moving of n1 disks counterclockwise is figurative: individual disks can never be moved counterclockwise. To move n 1 disks counterclockwise to the adjacent pile: 1. Move the top n 2 disks counterclockwise to the target pile 2. Move disk N 1 one step clockwise 3. Move the n 2 disks clockwise to the start pile 4. Move disk N 1 one step clockwise 5. Move the n 2 disks counterclockwise to the target pile The project consists of two parts: (1) to determine the minimum number of moves necessary to move n disks from pile A to pile B; (2) to simulate the game (the details of which will be discussed in class).

The number of moves it takes to complete a Tower of Hanoi game in the minimum number of steps can be calculated in a recursive manner as shown below. int hanoi (int n) { if (n == 1) return 1; else return 2 * hanoi(n - 1) + 1; } The simulation of a Cyclic Hanoi game can be set up using the following two procedures: move cw and move ccw for moving n disks from src pile to dst pile, clockwise and counterclockwise respectively. /* dst = srcs neighbor clockwise */ void move_cw (int n, int src, int dst) { if (n > 1) { move_ccw (n - 1, src, tmp); move_cw (1, src, dst); move_ccw (n - 1, tmp, dst); } else if (n == 1) { /* move one disk clockwise from src to dst */ } } /* dst = srcs neighbor counterclockwise */ void move_ccw (int n, int src, int dst) { if (n > 1) { move_ccw (n - 1, src, dst); /* remainder of the algorithm intentionally left incomplete */ ... ... ... ... } else if (n == 1) { move_cw (1, src, tmp); move_cw (1, tmp, dst); } } 3 Let the numbers of steps it takes to move n disks clockwise and counterclockwise be cw(n) and ccw(n) respectively. Then cw(1) = 1 (1) ccw(1) = 2 (2) cw(n) = 2 ccw(n 1) + 1 (3) ccw(n) = 2 ccw(n 1) + cw(n 1) + 2 (4) n cw ccw 1 1 2 2 5 7 3 15 21 4 43 59 5 119 163

The piles should be implemented as stacks (that grow upward from lower memory address to higher). The capacity of each stack is 128 bytes (or 16 long integers). The base addresses of stacks A (source), B (destination), and C (temporary) are 0x000, 0x080, and 0x100 respectively. X19, X20, and X21 should be used as the stack pointer registers for stacks A, B, and C respectively. Each element of a stack represents the size of a disk: 1 for the smallest disk, 2 for the next larger one, etc. If the total number of disks to be moved is 10, the largest disk size is 10. The bottom of each stack is initialized with 255 to represent a disk with size 255, which is present for the purpose of size comparison when a disk is moved to an empty stack but is never meant to be moved. In addition, stack A is initialized with disks of size 1 to 10 as shown below. SPA (X19) 255 2 3 1 4 5 10 6 7 8 9 0x000 SPB (X20) 0x080 255 SPC (X21) 0x100 255 When the Cyclic Tower of Hanoi game is completed, the stacks should look as below. SPA (X19) 255 2 3 1 4 5 10 6 7 8 9 0x000 SPB (X20) 255 0x080 SPC (X21) 0x100

ECE 30 Programming Project Winter 2020 Cyclic Hanoi due 6 pm Friday, March 13, 2020 The Tower of Hanoi is a mathematical game for moving a set of n disks stacked in the order of decreasing size from one pile to another (using a spare pile) one disk at a time without ever placing a larger disk on top of a smaller disk. The Cyclic Hanoi is derived from the Tower of Hanoi with a couple of restrictions: 1. There are 3 piles arranged in a circular fashion. 2. Disks can only be moved in a clockwise direction. Pile A (Source) Pile B (Destination) Pile C (Spare) The algorithm for moving n disks can best be described in a recursive manner as described below: 1. Move the top n - 1 disks to a spare pile. 2. Move the largest disk to the destination. 3. Move the n - 1 disks from the spare pile to the destination. The algorithm becomes a bit more complex for the Cyclic Hanoi because of the second restriction: disks must be moved clockwise. Assuming that the disks are labeled from 1 to N from the smallest to the largest, to move n disks clockwise from pile A to pile B: 1. Move the top n - 1 disks counterclockwise to pile C. 2. Move disk N clockwise to pile B. 3. Move the n - 1 disks on pile C counterclockwise to pile B. Note that moving of n-1 disks counterclockwise is figurative: individual disks can never be moved counterclockwise. To move n - 1 disks counterclockwise to the adjacent pile: 1. Move the top n - 2 disks counterclockwise to the target pile 2. Move disk N - 1 one step clockwise 3. Move the n - 2 disks clockwise to the start pile 4. Move disk N - 1 one step clockwise 5. Move the n - 2 disks counterclockwise to the target pile The project consists of two parts: (1) to determine the minimum number of moves necessary to move n disks from pile A to pile B; (2) to simulate the game (the details of which will be discussed in class). The number of moves it takes to complete a Tower of Hanoi game in the minimum number of steps can be calculated in a recursive manner as shown below. int hanoi (int n) if (n == 1) return 1; else return 2 * hanoi (n - 1) + 1; The simulation of a Cyclic Hanoi game can be set up using the following two proce- dures: move.cw and move.ccw for moving n disks from src pile to dst pile, clockwise and counterclockwise respectively. /* dst = src's neighbor clockwise */ void move_cw (int n, int src, int dst) if (n > 1) { move_ccw (n - 1, src, tmp); move_cw (1, src, dst); move_ccw (n - 1, tmp, dst); } else if (n == 1) { /* move one disk clockwise from src to dst */ /* dst - sre's neighbor counterclockwise */ void move_cow (int n, int src, int dst) if (n > 1) { move_ccw (n - 1, src, dst); /* remainder of the algorithm intentionally left incomplete */ } else if (n == 1) { move_cw (1, src, tmp); move_cw (1, tmp, dst); Let the numbers of steps it takes to move n disks clockwise and counterclockwise be cw(n) and cow(n) respectively. Then cw(1) = 1 ccw(1) = 2 cw(n) = 2 ccwan 1) + 1 ccw(n) = 2 ccw(n 1)+cw(n 1) +2 E QE n cw cow 1 12