EE2028 Assignment 1

bubble_sort.s

/*
 * bubble_sort.s
 *
 *  Created on: 4/8/2022
 *      Author: Shankar
 */
   .syntax unified
	.cpu cortex-m4
	.fpu softvfp
	.thumb

		.global bubble_sort

@ Start of executable code
.section .text

@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort arr in decending order

@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng

@ You could create a look-up table of registers here:

@ 	R0 contains the address of the first element in the array
@ 	R1 contains the literal value 6
@	R2 i; outer loop counter
@	R3 j; inner loop counter
@	R4 len(array) - 1
@	R5 temporary register
@	R6 temporary register
@	R7 temporary register
@	R8 Global Swap Counter


@ write your program from here:
bubble_sort:

	PUSH {R2-R8}

	@Initialise the registers here
	LDR R2, =#0 @ i value; outer loop
	LDR R3, =#0 @ j value; inner loop
	SUB R4, R1, #1 @ R4 = N(Number of elements)-1
	LDR R5, =#0 @ temporary register
	LDR R6, =#0 @ temporary register
	LDR R7, =#0 @ temporary register
	LDR R8, =#0 @ Swap Counter

	PUSH {R14}
	@ START
	@B SUBROUTINE -- Backup Plan
FUNCTION1:

	@ Reset the variables
	LDR R3, =#0 @ j value; inner loop
	LDR R5, =#0 @ temporary register
	LDR R6, =#0 @ temporary register
	LDR R7, =#0 @ temporary register

	@PUSH {R14} @ Store the return address value to Stack register safely!

	CMP R2, R4 @ check if R2 == 5; if its equal ...
	ITTTT EQ @ Set the equal flag when R2 - R4 = 0
	MOVEQ R0, R8
	POPEQ {R14}
	POPEQ {R2-R8}
	BXEQ LR @if the loop has finished, end the loop.

	PUSH {R0}

	BL LOOP
	@ <After LOOP ends, come here>
	POP {R0}

	ADD R2, #1 @ Increment the outer loop counter

	@POP {R14}

	B FUNCTION1
	@ END

	@ Should not execute HERE!!!
	@ BX LR

@ Backup Plan
SUBROUTINE:
	CMP R2, R4 @ check if R2 == 5; if its equal ...
	IT EQ @ Set the equal flag when R2 - R4 = 0
	BXEQ LR @if the loop has finished, end the loop.

	PUSH {R0}

	B LOOP
	@ <come here>
	POP {R0}

	ADD R2, #1 @ Increment the outer loop counter

	B SUBROUTINE @ Loop SUBROUTINE
	@ BX LR
LOOP:
	CMP R3, R4 @ check if R3 == 5; if its equal ...
	IT EQ @ Set the equal flag when R2 - R4 = 0
	BXEQ LR @if the loop has finished, end the loop.

	LDR R5, [R0, #0] @ 34 --> 32
	LDR R6, [R0, #4] @ 32 --> 34

	CMP R6, R5 @ R6 - R5
	ITTTT MI @ if the result is negative, conduct the swap operation
	MOVMI R7, R5 @ Swap the bigger value to temp R7
	MOVMI R5, R6 @ Swap the smaller value to R5
	MOVMI R6, R7 @ Swap the value in temp R7 R6
	STRMI R5, [R0]
	@ Extension of the above code; when the result is negative
	ITTT MI @ if the result is negative, conduct the swap operation
	ADDMI R0, 4 @ Postman Walking to next address
	STRMI R6, [R0]
	AddMI R8, #1 @ Add the total_swap counter, if swap is done

	IT PL @ If dont need to swap, come here
	ADDPL R0, 4

	ADD R3, #1 @ Increment the inner loop counter

	B LOOP


@ Store result in SRAM (4 bytes), static random access memory
@.lcomm	ADDRESS	4
.end

main.c

/**
 ******************************************************************************
 * @project        : EE2028 Assignment 1 Program Template
 * @file           : main.c
 * @author         : Shankar, Wei Heng
 * @brief          : Main program body
 ******************************************************************************
 * @attention
 *
 * <h2><center>&copy; Copyright (c) 2021 STMicroelectronics.
 * All rights reserved.</center></h2>
 *
 * This software component is licensed by ST under BSD 3-Clause license,
 * the "License"; You may not use this file except in compliance with the
 * License. You may obtain a copy of the License at:
 *                        opensource.org/licenses/BSD-3-Clause
 *
 ******************************************************************************
 */

#include "stdio.h"

#define M 6	 // No. of numbers in array
// #define M 2	 // No. of numbers in array

// Necessary function to enable printf() using semihosting
extern void initialise_monitor_handles(void);

// Functions to be written
extern int bubble_sort(int* arg1, int arg2);

int main(void)
{
	// Necessary function to enable printf() using semihosting
	initialise_monitor_handles();

	int arr[M] = {18, 34, 32, 75, 11, 97};
	// int arr[M] = {18, 9};
	int swap,i;  // no. of total swaps

	// Bubble sort with bubble_sort.s
	swap = bubble_sort((int*)arr, (int)M);
	printf("After %d rounds of swap, the array is sorted as: \n{ ", swap);

	// int *p = 0x20017FE4;
	// printf("%d \n", *p);

	for (i=0; i<M; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("}\n");

	// Infinite loop
	while(1){}

}

/*
 * bubble_sort.s
 *
 *  Created on: 4/8/2022
 *      Author: Shankar
 * 		Author: Wei Heng
 */
   .syntax unified
	.cpu cortex-m4
	.fpu softvfp
	.thumb

		.global bubble_sort

@ Start of executable code
.section .text

@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort arr in decending order

@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng

@ You could create a look-up table of registers here:

@ 	R0 contains the address of the first element in the array
@ 	R1 contains the literal value 6
@	R2 i; outer loop counter
@	R3 j; inner loop counter
@	R4 len(array) - 1
@	R5 temporary register used to swap elements
@	R6 temporary register used to swap elements
@	R7 temporary register used to swap elements
@	R8 Total Swap Counter; increment by 1 if a swap operation is perfomed
@ 	R9 Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function}


@ write your program from here:
bubble_sort:

	PUSH {R2-R9} @ Help us preserve the "marking" when we navigate back to main function in main.c

	@Initialise the registers here -- Only Execute for the first time
	LDR R2, =#0 @ i value; outer loop
	LDR R3, =#0 @ j value; inner loop
	SUB R4, R1, #1 @ R4 = N(Number of elements)-1
	LDR R5, =#0 @ temporary register used to swap elements
	LDR R6, =#0 @ temporary register used to swap elements
	LDR R7, =#0 @ temporary register used to swap elements
	LDR R8, =#0 @ Total Swap Counter; increment by 1 if a swap operation is perfomed
	LDR R9, =#0 @ ++1st Additions(4)++ @ Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function}

	PUSH {R14} @ Store the return address value to Stack Register safely used to navigate back to main function in main.c

	@B SUBROUTINE -- Backup Plan
FUNCTION1:

	CMP R2, R4 @ check if outer loop counter == 5; if its equal, we have gone through the max no. of iterations
	ITTTT EQ @ Set the equal flag when R2 - R4 = 0
	MOVEQ R0, R8
	POPEQ {R14}
	POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
	BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file

	CMP R9, R4 @ ++2nd Additions(4)++ @ check if local swap counter == 5; if its equal meaning no swap took place, the array is sorted.
	ITTTT EQ @ Set the equal flag when R9 - R4 = 0
	MOVEQ R0, R8
	POPEQ {R14}
	POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
	BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file


	@ Reset the variables after every ith iteration (every outer loop iteration)
	LDR R3, =#0 @ j value; inner loop
	LDR R5, =#0 @ temporary register used to swap elements
	LDR R6, =#0 @ temporary register used to swap elements
	LDR R7, =#0 @ temporary register used to swap elements
	LDR R9, =#0 @ ++3rd Additions (4)++ @ set local swap counter to 0

	PUSH {R0}
	BL LOOP
	@ <After LOOP ends, come here>
	POP {R0} @ Reset the R0 pointer back to the memory address pointing to the first element in the array
	ADD R2, #1 @ Increment the outer loop counter

	B FUNCTION1 @ Loop back to the start of FUNCTION1 subroutine

@ Backup Plan
SUBROUTINE:
	CMP R2, R4 @ check if R2 == 5; if its equal ...
	IT EQ @ Set the equal flag when R2 - R4 = 0
	BXEQ LR @if the loop has finished, end the loop.

	PUSH {R0}

	B LOOP
	@ <come here>
	POP {R0}

	ADD R2, #1 @ Increment the outer loop counter

	B SUBROUTINE @ Loop SUBROUTINE
	@ BX LR

LOOP:
	CMP R3, R4 @ check if inner_loop_counter == 5; if its equal, we have completed 1 iteration
	IT EQ @ Set the equal flag when R2 - R4 = 0
	BXEQ LR @ if the loop has finished, end the loop.

	LDR R5, [R0, #0] @ De-Reference the memory address in (R0 + 0) ... (R0 + 4)
	LDR R6, [R0, #4] @ De-Reference the memory address in (R0 + 4) ... (R0 + 8)

	CMP R6, R5 @ CMP performs R6 - R5
	ITTTT MI @ if the result of the above operation is negative, perform the swap operation
	MOVMI R7, R5 @ Swap the bigger value to temp R7
	MOVMI R5, R6 @ Swap the smaller value to R5
	MOVMI R6, R7 @ Swap the value in temp R7 R6
	STRMI R5, [R0]
	@ Extension of the above code; when the result is negative
	ITTT MI @ if the result is negative, perform the swap operation
	ADDMI R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
	STRMI R6, [R0]
	ADDMI R8, #1 @ Increment the total_swap counter by 1, if swap is done

	ITT PL @ If dont need to swap, come here
	ADDPL R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
	ADDPL R9, #1 @ ++4th Additions(4)++ @ Increment the local swap counter

	ADD R3, #1 @ Increment the inner loop counter

	B LOOP @ Loop back to the start of LOOP subroutine

.end

Changes

Additions

• More comments added
• Cleaned up whitespace
• Added local swap counter; meaning if no swaps took place; array is sorted and end the asm function; go back to main

Deletions

• NIL

CMP R9,R4 executes when innerloop completed with R9 == R4 number of times of no swap required.

/*
 * bubble_sort.s
 *
 *  Created on: 4/8/2022
 *      Author: Shankar
 * 	Author: Wei Heng
 */
   .syntax unified
	.cpu cortex-m4
	.fpu softvfp
	.thumb

		.global bubble_sort

@ Start of executable code
.section .text

@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort arr in decending order

@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng

@ You could create a look-up table of registers here:

@ 	R0 contains the address of the first element in the array
@ 	R1 contains the literal value 6
@	R2 i; outer loop counter
@	R3 j; inner loop counter
@	R4 len(array) - 1
@	R5 temporary register used to swap elements
@	R6 temporary register used to swap elements
@	R7 temporary register used to swap elements
@	R8 Total Swap Counter; increment by 1 if a swap operation is perfomed
@ 	R9 Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function} else {set to 0}


@ write your program from here:
bubble_sort:

	PUSH {R2-R9} @ Help us preserve the "marking" when we navigate back to main function in main.c

	@Initialise the registers here -- Only Execute for the first time
	LDR R2, =#0 @ i value; outer loop
	LDR R3, =#0 @ j value; inner loop
	SUB R4, R1, #1 @ R4 = N(Number of elements)-1
	LDR R5, =#0 @ temporary register used to swap elements
	LDR R6, =#0 @ temporary register used to swap elements
	LDR R7, =#0 @ temporary register used to swap elements
	LDR R8, =#0 @ Total Swap Counter; increment by 1 if a swap operation is perfomed
	LDR R9, =#0 @ ++1st Additions(4)++ @ Zero Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function}

	PUSH {R14} @ Store the return address value to Stack Register safely used to navigate back to main function in main.c

OUTER_LOOP:

	CMP R2, R4 @ check if outer loop counter == 5; if its equal, we have gone through the max no. of iterations
	ITTTT EQ @ Set the equal flag when R2 - R4 = 0
	MOVEQ R0, R8
	POPEQ {R14}
	POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
	BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file

	CMP R9, R4 @ ++2nd Additions(4)++ @ check if zero swap counter == 5; if its equal meaning no swap took place, the array is sorted.
	ITTTT EQ @ Set the equal flag when R9 - R4 = 0
	MOVEQ R0, R8
	POPEQ {R14}
	POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
	BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file


	@ Reset the variables after every ith iteration (every outer loop iteration)
	LDR R3, =#0 @ j value; inner loop
	LDR R5, =#0 @ temporary register used to swap elements
	LDR R6, =#0 @ temporary register used to swap elements
	LDR R7, =#0 @ temporary register used to swap elements
	LDR R9, =#0 @ ++3rd Additions (4)++ @ set zero swap counter to 0

	PUSH {R0}
	BL INNER_LOOP
	@ <After INNER_LOOP ends, come here>
	POP {R0} @ Reset the R0 pointer back to the memory address pointing to the first element in the array
	ADD R2, #1 @ Increment the outer loop counter

	B OUTER_LOOP @ Loop back to the start of OUTER_LOOP subroutine

INNER_LOOP:
	CMP R3, R4 @ check if inner_loop_counter == 5; if its equal, we have completed 1 iteration
	IT EQ @ Set the equal flag when R2 - R4 = 0
	BXEQ LR @ if the loop has finished, end the loop.

	LDR R5, [R0, #0] @ De-Reference the memory address in (R0 + 0) ... (R0 + 4)
	LDR R6, [R0, #4] @ De-Reference the memory address in (R0 + 4) ... (R0 + 8)

	CMP R6, R5 @ CMP performs R6 - R5
	ITTTT MI @ if the result of the above operation is negative, perform the swap operation
	MOVMI R7, R5 @ Swap the bigger value to temp R7
	MOVMI R5, R6 @ Swap the smaller value to R5
	MOVMI R6, R7 @ Swap the value in temp R7 R6
	STRMI R5, [R0]
	@ Extension of the above code; when the result is negative
	ITTT MI @ if the result is negative, perform the swap operation
	ADDMI R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
	STRMI R6, [R0]
	ADDMI R8, #1 @ Increment the total_swap counter by 1, if swap is done

	ITT PL @ If dont need to swap, come here
	ADDPL R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
	ADDPL R9, #1 @ ++4th Additions(4)++ @ Increment the zero swap counter

	ADD R3, #1 @ Increment the inner loop counter

	B INNER_LOOP @ Loop back to the start of INNER_LOOP subroutine

.end

/**
 ******************************************************************************
 * @project        : EE2028 Assignment 1 Program Template
 * @file           : main.c
 * @author         : Shankar, Wei Heng
 * @brief          : Main program body
 ******************************************************************************
 * @attention
 *
 * <h2><center>&copy; Copyright (c) 2021 STMicroelectronics.
 * All rights reserved.</center></h2>
 *
 * This software component is licensed by ST under BSD 3-Clause license,
 * the "License"; You may not use this file except in compliance with the
 * License. You may obtain a copy of the License at:
 *                        opensource.org/licenses/BSD-3-Clause
 *
 ******************************************************************************
 */

#include "stdio.h"

// #define M 6	 // No. of numbers in array
// #define M 3	 // No. of numbers in array

// Necessary function to enable printf() using semihosting
extern void initialise_monitor_handles(void);

// Function Definitions
extern int bubble_sort(int *arg1, int arg2);
int BubbleSort(int arr[], int size);

int main(void) {
	// Necessary function to enable printf() using semihosting
	initialise_monitor_handles();

	int arr[] = { -18, -34, -32, -75, 11, 97 };
	int arr_for_c[] = { -18, -34, -32, -75, 11, 97 };
	int swap, i;  // no. of total swaps

	int M = sizeof(arr) / sizeof(int);
	printf("Length of the array = %d \n", M);

	// Bubble sort with bubble_sort.s
	swap = bubble_sort((int*)arr, (int)M);
	printf("After %d rounds of swap, the array is sorted as: \n{ ", swap);

	for (i = 0; i < M; i++) {
		printf("%d ", arr[i]);
	}
	printf("}\n");

	// Bubble sort implemented in C
	swap = BubbleSort(arr_for_c, (int) M);
	printf("\n It took %d rounds of swap for the array to be sorted. \n{ ", swap);

	// Infinite loop
	while (1) {
	}

}

int BubbleSort(int arr[], int size) {
	int i, j, temp, flag = 0;
	int total_swap_counter = 0;

	for (i = 0; i < size; i++) {
		flag = 0;

		for (j = 0; j < size - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				flag = 1;
				temp = arr[j + 1]; // Swap operation
				arr[j + 1] = arr[j];
				arr[j] = temp;
				total_swap_counter += 1;
			}
		}
		if (flag == 0) { // array is already sorted
			// printf("\n Array is already Sorted!!");
			printf("\n The array Sorted in ascending order is :\n");
			printf("{");
			for (i = 0; i < size; i++) {
				printf(" %d ", arr[i]);
			}
			printf("}");
			return total_swap_counter;
		}
	}
	return total_swap_counter;
}

Changes

• Subroutine names updated
• Removed subroutine SUBROUTINE
• can also sort negative numbers
• added bubble sort c to main.c file

Author : Wei Heng

/*
 * bubble_sort.s
 *
 *  Created on: 4/8/2022
 *      Author: Shankar
 * 		Author: Wei Heng
*/
   .syntax unified
	.cpu cortex-m4
	.fpu softvfp
	.thumb

		.global bubble_sort

@ Start of executable code
.section .text

@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort array in ascending order

@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng

@ You could create a look-up table of registers here:

@ 	R0 contains the address of the first element in the array
@ 	R1 contains the literal value 6

@	R2 i; outer loop counter and j; inner loop counter 
@	R3 number of elements - 1
@	R4 temporary register used to swap elements
@	R5 temporary register used to swap elements
@	R6 Total Swap Counter; increment by 1 if a swap operation is perfomed
@ 	R7 Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function} else {set to 0}

bubble_sort:

	PUSH {R2-R7} @ Help us preserve the "marking" when we navigate back to main function in main.c
	PUSH {R14} @ Store the return address value to Stack Register safely used to navigate back to main function in main.c

	@ Initialize the registers here -- Execute this portion for the first time ONLY
	LDR R2, =#0 @ Set Loops counter to 0
	SUB R3, R1, #1 @ R3 = N(Number of elements)-1
	LDR R4, =#0 @ temporary register used to swap elements
	LDR R5, =#0 @ temporary register used to swap elements
	LDR R6, =#0 @ Total Swap Counter; increment by 1 if a swap operation is perfomed
	LDR R7, =#0 @ Zero Swap Counter

	B OUTER_LOOP @ Branch to OUTER_LOOP

OUTER_LOOP:
	CMP R2, R3 @ check if outer loop counter == 5; if its equal, we have gone through the max no. of iterations
	ITTTT EQ @ Set the equal flag when R2 - R3 = 0
	MOVEQ R0, R6 @ Move R6 total swap counter value to R0 to return back to the main function in main.c
	POPEQ {R14}
	POPEQ {R2-R7} @ Set the R2-R7 registers back to the original values
	BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file

	CMP R7, R3 @ Check if zero swap counter == 5; if its equal, meaning the array is already sorted.
	ITTTT EQ @ Set the equal flag when R7 - R3 = 0
	MOVEQ R0, R6 @ Move R6 total swap counter value to R0 to return back to the main function in main.c
	POPEQ {R14}
	POPEQ {R2-R7} @ Set the R2-R7 registers back to the original values
	BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file

	PUSH {R2} @ Retaining OUTER_LOOP counter
	PUSH {R0} @ Retaining array 1st address

	@ Reset the variables after every ith iteration (every outer loop iteration)
	LDR R2, =#0 @ initialise counter for INNER_LOOP usage
	LDR R4, =#0 @ temporary register used to store elements; not necessary to perform this instruction
	LDR R5, =#0 @ temporary register used to store elements; not necessary to perform this instruction
	LDR R7, =#0 @ set zero swap counter to 0

	BL INNER_LOOP

	@ After INNER_LOOP completed, execute the following:
	POP {R0} @ Reset the R0 pointer back to the memory address pointing to the first element in the array
	POP {R2} @ Retrieving previous OUTER_LOOP counter
	ADD R2, #1 @ OUTER_LOOP counter increment

	B OUTER_LOOP @ Loop back to the start of OUTER_LOOP subroutine

INNER_LOOP:
	CMP R2, R3 @ check if inner_loop_counter == 5; if its equal, we have completed 1 iteration
	IT EQ @ Executes when R2 - R3 = 0
	BXEQ LR @ If the loop has finished, links back to OUTER_LOOP.

	LDR R4, [R0, #0] @ De-Reference the memory address in (R0 + 0) ... (R0 + 4)
	LDR R5, [R0, #4] @ De-Reference the memory address in (R0 + 4) ... (R0 + 8)

	CMP R5, R4 @ CMP performs R5 - R4
	ITTTT MI @ If the result of the above operation is negative, perform the swap operation
	STRMI R5, [R0] @ Storing smaller value to address R0
	ADDMI R0, #4 @ Increment R0 pointer by 4
	STRMI R4, [R0] @ Storing larger values to next address
	ADDMI R6, #1 @ Add swap count

	ITT PL @ If dont need to swap, come here
	ADDPL R0, #4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
	ADDPL R7, #1 @ Increments the zero swap counter by 1

	ADD R2, #1 @ Increment the INNER_LOOP counter

	B INNER_LOOP @ Loop back to INNER_LOOP subroutine

.end

Changes

• Optimized assembly code to 6 registers
• Tested and debug the code
• Peer Reviewed
• Modified comments by changing to the appropriate register values