Category: Data Structure using C

Posted on by — Leave a comment

Merge Sort is bad for Embedded System

Merge sort is good if your system has plenty of memory to accommodate the temporary array.

Embedded systems have very limited memory and it is often fixed.

If the system has some other function that also runs concurrently. Then that memory also gets shortened.

Merge sort is good for a bigger system like the personal computer and business computer which have the bigger memory in which all the temporary array can reside.

The advantage of merge sort is that it is stable.

Since it takes a lot of space it is not useful for an embedded system, as they have a very small memory sometimes it is just KilloByte.
example:
ATmega328p = 2KB SRAM
ATtiny85 = 512B SRAM

Code for STM32F429ZIT6

This code redirects the printf statements towards the asynchronous UART.
As the size of input array for merge sort increases the space required to store temporary element increases, which eventually leads to stalling of the program.
/* USER CODE BEGIN Header */
/**
  ******************************************************************************
  * @file           : main.c
  * @brief          : Main program body
  ******************************************************************************
  * @attention
  *
  * Copyright (c) 2023 STMicroelectronics.
  * All rights reserved.
  *
  * This software is licensed under terms that can be found in the LICENSE file
  * in the root directory of this software component.
  * If no LICENSE file comes with this software, it is provided AS-IS.
  *
  ******************************************************************************
  */
/* USER CODE END Header */
/* Includes ------------------------------------------------------------------*/
#include "main.h"

/* Private includes ----------------------------------------------------------*/
/* USER CODE BEGIN Includes */
#include "stdio.h"
#include "stdlib.h"
/* USER CODE END Includes */

/* Private typedef -----------------------------------------------------------*/
/* USER CODE BEGIN PTD */

/* USER CODE END PTD */

/* Private define ------------------------------------------------------------*/
/* USER CODE BEGIN PD */
/* USER CODE END PD */

/* Private macro -------------------------------------------------------------*/
/* USER CODE BEGIN PM */

/* USER CODE END PM */

/* Private variables ---------------------------------------------------------*/
UART_HandleTypeDef huart1;

/* USER CODE BEGIN PV */

/* USER CODE END PV */

/* Private function prototypes -----------------------------------------------*/
void SystemClock_Config(void);
static void MX_GPIO_Init(void);
static void MX_USART1_UART_Init(void);
/* USER CODE BEGIN PFP */

/* USER CODE END PFP */

/* Private user code ---------------------------------------------------------*/
/* USER CODE BEGIN 0 */
/*
* Function Name: _write
* Function Description: Redirect the printf() statement towards the UART using the HAL_UART_Transmit
Author: Abhay

*/
int _write(int fd, char* ptr, int len) {
    HAL_UART_Transmit(&huart1, (uint8_t *) ptr, len, HAL_MAX_DELAY);
 //   HAL_UART_Transmit(&huart1, ptr, len, Timeout)
    return len;
}

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;

	/* create temp arrays */
	int L[n1], R[n2];

	/* Copy data to temp arrays L[] and R[] */
	for (i = 0; i < n1; i++)
		L[i] = arr[l + i];
	for (j = 0; j < n2; j++)
		R[j] = arr[m + 1 + j];

	/* Merge the temp arrays back into arr[l..r]*/
	i = 0; // Initial index of first subarray
	j = 0; // Initial index of second subarray
	k = l; // Initial index of merged subarray
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	/* Copy the remaining elements of L[], if there
	are any */
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}

	/* Copy the remaining elements of R[], if there
	are any */
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
	if (l < r) {
		// Same as (l+r)/2, but avoids overflow for
		// large l and h
		int m = l + (r - l) / 2;

		// Sort first and second halves
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);

		merge(arr, l, m, r);
	}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", A[i]);
	printf("\n");
}

/* USER CODE END 0 */

/**
  * @brief  The application entry point.
  * @retval int
  */
int main(void)
{
  /* USER CODE BEGIN 1 */

  /* USER CODE END 1 */

  /* MCU Configuration--------------------------------------------------------*/

  /* Reset of all peripherals, Initializes the Flash interface and the Systick. */
  HAL_Init();

  /* USER CODE BEGIN Init */

  /* USER CODE END Init */

  /* Configure the system clock */
  SystemClock_Config();

  /* USER CODE BEGIN SysInit */

  /* USER CODE END SysInit */

  /* Initialize all configured peripherals */
  MX_GPIO_Init();
  MX_USART1_UART_Init();
  /* USER CODE BEGIN 2 */
  int arr[] = { 12, 11, 13, 5, 6, 7,12};
        int arr_size = sizeof(arr) / sizeof(arr[0]);

//        for( int temp=0; temp<1023;temp++){
//  	arr[temp] = rand()*1000;
//  }
        printf("Given array is \n");
        printArray(arr, arr_size);

        mergeSort(arr, 0, arr_size - 1);

        printf("\nSorted array is \n");
        printArray(arr, arr_size);
     //   return 0;
  /* USER CODE END 2 */

  /* Infinite loop */
  /* USER CODE BEGIN WHILE */
  while (1)
  {
    /* USER CODE END WHILE */

    /* USER CODE BEGIN 3 */
  }
  /* USER CODE END 3 */
}

/**
  * @brief System Clock Configuration
  * @retval None
  */
void SystemClock_Config(void)
{
  RCC_OscInitTypeDef RCC_OscInitStruct = {0};
  RCC_ClkInitTypeDef RCC_ClkInitStruct = {0};

  /** Configure the main internal regulator output voltage
  */
  __HAL_RCC_PWR_CLK_ENABLE();
  __HAL_PWR_VOLTAGESCALING_CONFIG(PWR_REGULATOR_VOLTAGE_SCALE3);

  /** Initializes the RCC Oscillators according to the specified parameters
  * in the RCC_OscInitTypeDef structure.
  */
  RCC_OscInitStruct.OscillatorType = RCC_OSCILLATORTYPE_HSI;
  RCC_OscInitStruct.HSIState = RCC_HSI_ON;
  RCC_OscInitStruct.HSICalibrationValue = RCC_HSICALIBRATION_DEFAULT;
  RCC_OscInitStruct.PLL.PLLState = RCC_PLL_NONE;
  if (HAL_RCC_OscConfig(&RCC_OscInitStruct) != HAL_OK)
  {
    Error_Handler();
  }

  /** Initializes the CPU, AHB and APB buses clocks
  */
  RCC_ClkInitStruct.ClockType = RCC_CLOCKTYPE_HCLK|RCC_CLOCKTYPE_SYSCLK
                              |RCC_CLOCKTYPE_PCLK1|RCC_CLOCKTYPE_PCLK2;
  RCC_ClkInitStruct.SYSCLKSource = RCC_SYSCLKSOURCE_HSI;
  RCC_ClkInitStruct.AHBCLKDivider = RCC_SYSCLK_DIV1;
  RCC_ClkInitStruct.APB1CLKDivider = RCC_HCLK_DIV1;
  RCC_ClkInitStruct.APB2CLKDivider = RCC_HCLK_DIV1;

  if (HAL_RCC_ClockConfig(&RCC_ClkInitStruct, FLASH_LATENCY_0) != HAL_OK)
  {
    Error_Handler();
  }
}

/**
  * @brief USART1 Initialization Function
  * @param None
  * @retval None
  */
static void MX_USART1_UART_Init(void)
{

  /* USER CODE BEGIN USART1_Init 0 */

  /* USER CODE END USART1_Init 0 */

  /* USER CODE BEGIN USART1_Init 1 */

  /* USER CODE END USART1_Init 1 */
  huart1.Instance = USART1;
  huart1.Init.BaudRate = 115200;
  huart1.Init.WordLength = UART_WORDLENGTH_8B;
  huart1.Init.StopBits = UART_STOPBITS_1;
  huart1.Init.Parity = UART_PARITY_NONE;
  huart1.Init.Mode = UART_MODE_TX_RX;
  huart1.Init.HwFlowCtl = UART_HWCONTROL_NONE;
  huart1.Init.OverSampling = UART_OVERSAMPLING_16;
  if (HAL_UART_Init(&huart1) != HAL_OK)
  {
    Error_Handler();
  }
  /* USER CODE BEGIN USART1_Init 2 */

  /* USER CODE END USART1_Init 2 */

}

/**
  * @brief GPIO Initialization Function
  * @param None
  * @retval None
  */
static void MX_GPIO_Init(void)
{
  GPIO_InitTypeDef GPIO_InitStruct = {0};

  /* GPIO Ports Clock Enable */
  __HAL_RCC_GPIOA_CLK_ENABLE();
  __HAL_RCC_GPIOG_CLK_ENABLE();

  /*Configure GPIO pin Output Level */
  HAL_GPIO_WritePin(GPIOG, ledg_Pin|ledr_Pin, GPIO_PIN_RESET);

  /*Configure GPIO pins : ledg_Pin ledr_Pin */
  GPIO_InitStruct.Pin = ledg_Pin|ledr_Pin;
  GPIO_InitStruct.Mode = GPIO_MODE_OUTPUT_PP;
  GPIO_InitStruct.Pull = GPIO_NOPULL;
  GPIO_InitStruct.Speed = GPIO_SPEED_FREQ_LOW;
  HAL_GPIO_Init(GPIOG, &GPIO_InitStruct);

}

/* USER CODE BEGIN 4 */

/* USER CODE END 4 */

/**
  * @brief  This function is executed in case of error occurrence.
  * @retval None
  */
void Error_Handler(void)
{
  /* USER CODE BEGIN Error_Handler_Debug */
  /* User can add his own implementation to report the HAL error return state */
  __disable_irq();
  while (1)
  {
  }
  /* USER CODE END Error_Handler_Debug */
}

#ifdef  USE_FULL_ASSERT
/**
  * @brief  Reports the name of the source file and the source line number
  *         where the assert_param error has occurred.
  * @param  file: pointer to the source file name
  * @param  line: assert_param error line source number
  * @retval None
  */
void assert_failed(uint8_t *file, uint32_t line)
{
  /* USER CODE BEGIN 6 */
  /* User can add his own implementation to report the file name and line number,
     ex: printf("Wrong parameters value: file %s on line %d\r\n", file, line) */
  /* USER CODE END 6 */
}
#endif /* USE_FULL_ASSERT */
Posted on by — Leave a comment

Swapping of two numbers

Before Swapping :
a = 10
b = 2

After Swapping:
a = 2
b = 10

To do the swapping we have different approaches.
1. Swapping using a temporary variable
2. Swapping without using a temporary variable
3. Swapping using pointers

NOTE: We do not use of the second method in embedded system software writing. Because it would have to execute more instructions to perform the same operation with a temporary variable.

Swapping using a temporary variable

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int a = 10;
	int b = 3;
	int temp = 0;
	printf("Before Swapping");
	printf("\na = %d\tb = %d\n",a,b);

	temp = a;
	a = b;
	b = temp;

	printf("After Swapping");
	printf("\na = %d\tb = %d\n",a,b);

	return EXIT_SUCCESS;
}

Swapping without using a temporary variable

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int a = 10;
	int b = 3;
	int temp = 0;
	printf("Before Swapping");
	printf("\na = %d\tb = %d\n",a,b);

	a = a - b;
	b = a + b;
	a = b - a;

	printf("After Swapping");
	printf("\na = %d\tb = %d\n",a,b);

	return 1;
}

Swapping using pointers

When the memory size is very limited we prefer to do this.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int a = 10;
	int b = 3;
	int temp;
	int *x , *y;

	printf("Before Swapping");
	printf("\na = %d\tb = %d\n",a,b);

	x = &a;
	y = &b;
	temp = *x;
	*x = *y;
	*y = temp;

	printf("After Swapping");
	printf("\na = %d\tb = %d\n",a,b);
	
	return 1;
}
Posted on by — Leave a comment

Stack implementation without pointer

Stack is a type of data structure, where data is stored in Last In First Out fashion. In embedded system there are different kind of stacks available.
They are implemented in hardware and software.
The hardware implementation of stack is faster than software stack; but the size of stack in hardware is limited.

There are two types of stack available in hardware implementation:
1. Up-counting
2. Down-counting
Up-counting stack: where the memory location of the top element of stack is incremented from the low memory address;
Down-counting stack where the memory location is decremented from the highest memory address.

The following is a general stack implementation program which is written on x86 machine.


#include <stdio.h>

#define MAX 7

int arr[MAX]; // array of size MAX

int top = -1; //top is the index which stores the location
              // of the last inserted element in stack
/*
isFull Function checks that the top == MAX
isEmpty Function checks that the top == -1
*/
int isFull();
int isEmpty();

/*
push(int num)     To insert a element in stack
pop()             To remove the last inserted element in stack
display()         To display all the element in stack
*/

void pop();
void push(int num);

void display();

int main() {

display();	//display the elements of the stack

    push(32);
    push (1);
    push (26);
    push (64);
    push (127);
    push (-98);
    push (43);
    push (5);
    push (255);
    push (5);
    display();
    pop();

return 0;
}

int isEmpty(){
	if(top == -1){
		return 1;
	}
	else
		return 0;
}

int isFull(){
	if(top == MAX){
		return 1;
	}
	else
		return 0;
}

/*check if the stack is full or not.
If stack full 
write overflow
else 
increment the TOP and write the value.
*/
void push(int num){
	if(isFull()){
	printf("Stack Full OverFlow\n");
	}
	else {
		top++;
		arr[top] = num;
	}
	display();
}
/*check if the stack is empty or not.
If stack empty 
write underflow
else 
decrement the TOP.
*/
void pop(){
	if( isEmpty() ) {
	printf("Stack Full OverFlow\n");
	}
	else {
		top--;
	}
	display();
}

void display(){
	if( isEmpty() ){
		printf("Stack Empty UNDERFLOW\n");
		
	}
	else{
		int temp;
		for(temp = top; temp >= 0 ; temp--){
			printf("%d ",arr[temp]);
		}
		printf("\n");
		/*int *ptr = arr;
		while(ptr <= ((&arr)+MAX) ){
			printf("%d ",*ptr);
			ptr = ptr + 1;
			printf("\n");
		}
		*/
		
	}
}

Output Of the above program


Stack Empty UNDERFLOW

32 

1 32 

26 1 32 

64 26 1 32 

127 64 26 1 32 

-98 127 64 26 1 32 

43 -98 127 64 26 1 32 

5 43 -98 127 64 26 1 32 
Stack Full OverFlow

5 43 -98 127 64 26 1 32 
Stack Full OverFlow

5 43 -98 127 64 26 1 32 

5 43 -98 127 64 26 1 32 

43 -98 127 64 26 1 32