Bulgarian Solitaire ARM Assembly Solution Guide

Instructions

Objective

Write a Assembly language assignment program to play Bulgarian solitaire.

Requirements and Specifications

In this assignment, you will practise implementing and processing arrays in ARM Assembly by modelling the game of Bulgarian Solitaire. The game starts with 45 cards. (They need not be playing cards. Unmarked index cards work just as well.). Randomly divide them into some number of piles of random size. For example, you might start with piles of sizes 20, 5, 1, 9, and 10. In each round, you take one card from each pile, forming a new pile with these cards. For example, the sample starting configuration would be transformed into piles of sizes 19, 4, 8, 9, and 5. The solitaire is over when the piles have sizes 1, 2, 3, 4, 5, 6, 7, 8, and 9, in some order. (It can be shown that you always end up with such a configuration.) In your ARM assembler program, produce a random starting configuration and print it. Then keep applying the solitaire step and print the result. Stop when the solitaire final configuration is reached. I will leave the design of the program completely up to you but make sure that you use functions for all major tasks and keep the main function very simple .

(use it primarily to call your functions).

Screenshots of output

Source Code

.arch armv7 .cpu cortex-a53 .data piles: .space 180 @ space to save the size of at most 45 piles startMsg: .asciz "Initial pile configuration: " nextMsg: .asciz "Next pile configuration: " .text .global main main: push {fp,lr} @ save used registers mov r0,#0 @ set arg to zero bl time @ call time(0) bl srand @ call srand(time(0)) to initialize random seed ldr r0, =piles @ pass pile address to function bl genPiles @ generate card piles ldr r0, =startMsg @ print initial message bl printf ldr r0, =piles @ pass pile address to function bl printPiles @ print initial piles b checkLast @ check if we generated the last config or loop mainLoop: ldr r0, =piles @ pass pile address to function bl newPile @ generate new card pile ldr r0, =nextMsg @ print next message bl printf ldr r0, =piles @ pass pile address to function bl printPiles @ print piles checkLast: ldr r0, =piles @ pass pile address to function bl isLastConfig @ check if it's last configuration cmp r0, #0 @ if not beq mainLoop @ try again mov r0, #0 @ return 0 pop {fp,lr} @ restore used registers bx lr @ Generate piles using 45 cards @ On entry: @ R0 = pile address genPiles: push {r4-r5,fp,lr} @ save used registers mov r4, r0 @ save address in r4 mov r5, #45 @ initially we have 45 cards genLoop: bl rand @ generate a random number udiv r1, r0, r5 @ divide random number by number of cards mul r3, r1, r5 @ multiply result by number of cards sub r0, r0, r3 @ subtract random number - multiplication to get remainder add r0, r0, #1 @ increment to get number between 1 and number of cards str r0, [r4], #4 @ save random number in pile, advance to next one sub r5, r5, r0 @ remove random number from number of cards cmp r5,#0 @ if there are still cards bne genLoop @ generate more str r5, [r4] @ save a zero to indicate end of piles pop {r4-r5,fp,lr} @ restore used registers bx lr @ return to caller @ Print the current pile configuration @ On entry: @ R0 = pile address .data numFmt: .asciz "%-3d" nline: .asciz "\n" .text printPiles: push {r4,fp,lr} @ save used registers mov r4, r0 @ save address in r4 printLoop: ldr r1, [r4], #4 @ load number from pile and advance to next one cmp r1, #0 @ if this is the last pile beq endPrint @ end printing ldr r0, =numFmt @ print number bl printf b printLoop @ repeat loop endPrint: ldr r0, =nline @ print newline bl printf pop {r4,fp,lr} @ restore used registers bx lr @ return to caller @ Generate new pile @ On entry: @ R0 = pile address newPile: push {fp,lr} @ save used registers mov r1, #0 @ new pile size is zero newLoop: ldr r2, [r0] @ load number from pile cmp r2, #0 @ if this is the last pile beq endNew @ end creating pile add r1, r1, #1 @ increment new pile size sub r2, r2, #1 @ decrement current pile size str r2, [r0] @ save updated size cmp r2, #0 @ see if pile has disappeared bne skip @ if not, skip bl compactPiles @ else, compact piles, removing this zero b newLoop @ loop reusing this position skip: add r0, r0, #4 @ advance to next pile b newLoop @ repeat loop endNew: str r1, [r0], #4 @ save new pile at the last position and advance str r2, [r0] @ save zero to indicate end of piles pop {fp,lr} @ restore used registers bx lr @ return to caller @ Compact piles by moving all piles down to the initial position, thus removing @ the initial one @ On entry: @ R0 = pile address to remove compactPiles: push {r4-r5,fp,lr} @ save used registers mov r4, r0 @ save address in r4 compactLoop: ldr r5, [r4, #4] @ load next number from pile str r5, [r4] @ save in current position cmp r5, #0 @ if this is the last pile beq endCompact @ end compacting pile add r4, r4, #4 @ advance to next pile b compactLoop @ repeat loop endCompact: pop {r4-r5,fp,lr} @ restore used registers bx lr @ return to caller @ Check if last configuration was reached @ On entry: @ R0 = pile address @ Returns: @ R0 = 1 if it's last, 0 if not isLastConfig: push {fp,lr} @ save used registers mov r1, #0 @ save mask in zero lastLoop: ldr r2, [r0] @ load number from pile cmp r2, #0 @ if this is the last pile beq checkMask @ end checking pile cmp r2, #9 @ check if number is valid bgt notLast @ if > 9, this is not the last config mov r3, #1 @ else, load 1 lsl r3, r3, r2 @ move to bit position n (1-9) orr r1, r1, r3 @ add to mask add r0, r0, #4 @ advance to next pile b lastLoop @ repeat loop checkMask: ldr r0, =0x3FE @ load mask with bit positions 1-9 set to 1 cmp r1, r0 @ if the positions 1-9 are filled bne notLast @ if not, is not the last mov r0, #1 @ else, it's the last b endCheck @ end notLast: mov r0, #0 @ not last endCheck: pop {fp,lr} @ restore used registers bx lr @ return to caller