Reputation: 51
What am I doing wrong in this Microblaze assembly bubble sort?
I am working on a program for a Basys 3 Microblaze in its assembly language. However, the language is quite different from anything I can find online. I have documentation for it here, with the assembly commands available to me starting in chapter 4 (page 65).
The code I have takes 10 characters input from the terminal, and after each input it checks the switches on the Basys and changes the 7-segment displays. But I'm not worried about that. The part I am having trouble with is that these 10 single character inputs are stored in an array. I need to go through and bubble sort this array of characters and then spit them back out again. I have a sort function that is supposed to do this but I just cannot get it to work. If anyone can please help me figure out what I am doing wrong, I will be grateful. I have been up all night trying to figure this out. I use the Xilinx SDK from Vivado 2019.1 (and below as the SDK was removed in 2019.2).
Here is my code:
#Equates
.set NUMLOOPS, 10
.set SWITCH_DATA, 0x40000000
.set SEV_SEG_DATA, 0x40010000
.set UART, 0x40600000
#Memory Section
$msgBegin:
.asciz "\r\n Program Start.\r\n"
.text
.align 2
$msgWithChar:
.asciz "Character %d - %c\r\n"
.text
.align 2
$Nums:
.fill 10, 4, 65
.data
.align 4
$msgLoop:
.asciz "\r\n Embedded Systems Loop #%2d.\r\n"
.text
.align 2
$msgEnd:
.asciz "\r\n Program Stop.\r\n"
.text
.align 2
$msgTest1:
.asciz "\r\n Test 1."
.text
.align 2
$msgTest2:
.asciz "\r\n Test 2."
.text
.align 2
$msgTest3:
.asciz "\r\n Test 3."
.text
.align 2
$msgSpace:
.asciz "\r\n"
.text
.align 2
#Main Program
.globl main
main:
addi r5, r0, $msgBegin # Store string to print
addi r1, r1, -4 # Push r15 onto stack
swi r15,r1, 0
brlid r15,xil_printf # Call print func; retn addr in r15
nop # Unfilled delay slot
lwi r15,r1, 0 # Pop r15 off the stack
addi r1, r1, 4
addi r19, r0, NUMLOOPS # Initialize R19 to NUMLOOPS
addi r20, r0, 1 # Initialize R20 to one
addi r22, r0, 0 # Initialize R22 to 0
.globl loop
loop:
beqi r19, sort # If R19==0, branch to done; stop program
nop
rsub r19,r20,r19 # Decrement loop counter (R19) by 1 (R20)
lwi r11, r0, SWITCH_DATA # Read data from switches
swi r11, r0, SEV_SEG_DATA # Write switch data to 7-segment disp
addi r5, r0, UART # Set R5 arg to UART memory address
addi r1, r1, -4 # Push r15 onto stack
swi r15, r1, 0
brlid r15, XUartLite_RecvByte # Call UART Receive function
nop
lwi r15, r1, 0 # Pop r15 off stack
addi r1, r1, 4
swi r3, r22, $Nums # Store value into $Nums array at offset R22
add r6, r0, r3 # Move char R3 into R6 to display to UART
addi r1, r1, -4 # Push r15 on stack
swi r15, r1, 0
brlid r15, XUartLite_SendByte # Call Uart Send function
nop
lwi r15, r1, 0 # Pop r15 off stack
addi r1, r1, 4
addi r22, r22, 4 # Increment R22 by 4 bytes
bri loop
nop
.globl sort
sort:
addi r23, r0, 10 # Initialize R23 for outer loop counter
addi r24, r0, 10 # Initialize R24 for inner loop counter
addi r22, r0, 0 # Reinitialize R22 to zero
addi r29, r0, 0 # Initialize R29 for address offset of a[0]
for1:
#Print Test
addi r5, r0, $msgTest1 # Store string to print
addi r1, r1, -4 # Push r15 onto stack
swi r15,r1, 0
brlid r15,xil_printf # Call print func; retn addr in r15
nop # Unfilled delay slot
lwi r15,r1, 0 # Pop r15 off the stack
addi r1, r1, 4
beqid r23, disp # If R23==0, branch to disp
nop
addi r23, r23, -1 # Decrement outer loop counter (R23) by 1
addi r24, r0, 10 # Initialize R24 for inner loop counter
addi r24, r24, -1 # Subtract 1 from R24 (since we are comparing i and i+1)
for2:
#Print Test
addi r5, r0, $msgTest2 # Store string to print
addi r1, r1, -4 # Push r15 onto stack
swi r15,r1, 0
brlid r15,xil_printf # Call print func; retn addr in r15
nop # Unfilled delay slot
lwi r15,r1, 0 # Pop r15 off the stack
addi r1, r1, 4
beqid r24, for1 # If R24==0, branch to for1
nop
addi r24, r24, -1 # Decrement inner loop counter (R24) by 1
addi r25, r0, 0 # Initialize R25 for address offset of a[i]
muli r25, r24, 4 # Calculate address offset for a[i]
lwi r26, r25, $Nums # Load a[i] into R26
addi r25, r25, 4 # Increment R25 for address offset of a[i+1]
lwi r27, r25, $Nums # Load a[i+1] into R27
addi r28, r0, 0
cmp r28, r26, r27
bgtid r28, for2 # If a[i] > a[i+1], skip the swap
nop
swap:
#Print Test
addi r5, r0, $msgTest3 # Store string to print
addi r1, r1, -4 # Push r15 onto stack
swi r15,r1, 0
brlid r15,xil_printf # Call print func; retn addr in r15
nop # Unfilled delay slot
lwi r15,r1, 0 # Pop r15 off the stack
addi r1, r1, 4
swi r26, r25, $Nums # Store R26 (a[i]) into a[i+1] location
swi r27, r25, $Nums # Store R27 (a[i+1]) into a[i] location (using R25 - ARRAY_OFFSET)
rsubi r25, r25, -4
bri for2
nop
.globl disp
disp:
addi r19, r0, NUMLOOPS # Reinitialize R19 to NUMLOOPS
addi r22, r0, 0 # Reinitialize R22 to zero
addi r5, r0, $msgSpace # 1st arg R5 is format string
add r6, r0, r22 # 2nd arg R6 is address offset
lwi r7, r22, $Nums # 3rd arg R7 is array value at this offset
addi r1, r1, -4 # Push r15 on stack
swi r15, r1, 0
brlid r15, xil_printf # Call printf
nop
lwi r15, r1, 0 # Pop r15 off stack
addi r1, r1, 4
.globl loop2
loop2:
beqi r19, done # If R19==0, branch to done; stop program
nop
rsub r19,r20,r19 # Decrement loop counter (R19) by 1 (R20)
addi r5, r0, $msgWithChar # 1st arg R5 is format string
add r6, r0, r22 # 2nd arg R6 is address offset
lwi r7, r22, $Nums # 3rd arg R7 is array value at this offset
addi r1, r1, -4 # Push r15 on stack
swi r15, r1, 0
brlid r15, xil_printf # Call printf
nop
lwi r15, r1, 0 # Pop r15 off stack
addi r1, r1, 4
addi r22, r22, 4 # Increment R22 by 4 bytes
bri loop2
.globl done
done:
addi r5, r0, $msgEnd # Store string to print
addi r1, r1, -4 # Push r15 onto stack
swi r15,r1, 0
brlid r15,xil_printf # Call print func; retn addr in r15
nop # Unfilled delay slot
lwi r15,r1, 0 # Pop r15 off the stack
addi r1, r1, 4
Upvotes: 1
Views: 105
Answers (1)
Reputation: 39676
beqi r19, sort # If R19==0, branch to done; stop program
Should become beqi r19, done
swi r26, r25, $Nums # Store R26 (a[i]) into a[i+1] location swi r27, r25, $Nums # Store R27 (a[i+1]) into a[i] location (using R25 - ARRAY_OFFSET) rsubi r25, r25, -4 bri for2 nop
You are not swapping the values. Both stores go to the same address.
swi r26, r25, $Nums # Store R26 (a[i]) into a[i+1] location
addi r25, r25, -4
swi r27, r25, $Nums # Store R27 (a[i+1]) into a[i] location
bri for2
nop
Currently your code is processing all the array elements for every iteration of the outer loop. In BubbleSort you are supposed to reduce the array by 1 element on every iteration of the outer loop. The max/min (depending ascending/descending) will have moved ('bubbled') to an extremity and you should no longer have to deal with it.
Because you bubble towards the beginning of the array (how odd...) it would be that first element that you would no longer need to consider as soon as the inner loop has run once.
It will be easier to write the correct code if you remove:
- those temporary outputs that you wrote for verification purposes only
- instructions that are redundant like setting up R22 and R29 that remain unused
A possible solution
.globl sort
sort:
addi r23, r0, 9 # Initialize R23 for outer loop counter
for1:
beqid r23, disp # If R23==0, branch to disp
nop
addi r24, r23, 0 # Initialize R24 for inner loop counter (ever smaller)
addi r23, r23, -1 # Decrement outer loop counter (R23) by 1
addi r25, r0, -4 # Initialize R25 for address offset of a[i]
for2:
beqid r24, for1 # If R24==0, branch to for1
nop
addi r24, r24, -1 # Decrement inner loop counter (R24) by 1
addi r25, r25, 4 # Calculate address offset for a[i]
addi r26, r25, 4 # Calculate address offset for a[i+1]
lwi r27, r25, $Nums # Load a[i] into R27
lwi r28, r26, $Nums # Load a[i+1] into R28
addi r29, r0, 0
cmp r29, r27, r28
bgtid r29, for2 # If a[i] > a[i+1], skip the swap
nop
swap:
swi r27, r26, $Nums # Store R27 (a[i]) into a[i+1]
swi r28, r25, $Nums # Store R28 (a[i+1]) into a[i]
bri for2
nop
.globl disp
disp:
Upvotes: 0