C Programming for Embedded System

Introduction

Now for embedded system development people are using operating system to add more features and at the same time reduce the development time of a complex system. This article gives a simple & understandable overview of scheduling technique of embedded system programming for beginners and intermediate programmers. I am considering “C” as the programming language and an application running in a dedicated hardware/device without operating system. The binary output (*.bin file) can be directly running from the device after Power on. In this case, the time scheduling is an important part of system development. We should ensure that the right task should execute at the right time.

What is Embedded System?

An embedded system is some combination of computer hardware and software, either fixed in capability or programmable - it is specifically designed for a particular kind of application device. Or in short we can say, an embedded system is a special-purpose computer system designed to perform one or a few dedicated functions.

All embedded systems need not be a real time system. Real Time systems are those in which timeliness is as important as the correctness of the outputs. Performance estimation and reduction are crucial in real time system. By definition, we can say a real time system is a system that must satisfy explicit (bounded) response time constraints or risk severe consequences, including failure.

Embedded system plays an important part in our daily lives. Most of the people around the globe are highly dependent on different types of gadgets like mobile phones, iPods and many more. The embedded systems used in industrial machines, automobiles, medical equipment, airplanes, and vending machines have to be real time.

I thought of sharing my experience in Embedded systems. This is my first ever article on CodeProject, so I am expecting your valuable feedback and suggestions for betterment.

Background

People are using operating system (RTOS) for complex devices to make it more flexible, add more features and minimize the development time. But it will increase the cost of the device for a small application. So for small application firmware development without operating system is very much popular.

Time scheduling is an important aspect of real-time system. Real time software are executed in response to external events. This event may be periodic, in which case an appropriate scheduling of events and related task is required to guarantee performance. The scheduling strategy also depends on scheduling facilities that the chosen RTOS offers. This article emphasis on the event based technique when there was no operating system running in the device.

Scheduling

Two kinds of scheduling techniques are used in Real-Time system:

1. Static Scheduling
2. Dynamic Scheduling

Static Scheduling

This involves analyzing the tasks statically and determining their timing properties. This timing property can be used to create a fixed scheduling table, according to which tasks will be dispatched for execution at run time. Thus the order of execution of the task is fixed, and it is assumed that their execution time is also fixed.

Round-Robin Scheduling

Round Robin scheduling by Time Slicing is one of the ways to achieve static scheduling. Round robin is one of the simplest and most widely used scheduling algorithms; in which a small unit of time known as time slice is defined. Schedulers go around the queue of ready-to-run processes and allocate a time slice to each such process.

Scheduling with Priority

Priority indicates the urgency or importance assigned to a task. There are two approaches of scheduling based on priority based execution – when the processor is idle, the ready task with the highest priority is chosen for execution; once chosen, the task is run to completion.

Pre-Emptive Scheduling

Preemptive Priority based execution is when the processor is idle, the ready task with highest priority is chosen for execution; at any time, the execution of a task can be preempted if a task of higher priority becomes ready. Thus, at all times, the processor is idle or executing the ready task with the highest priority.

Dynamic Scheduling

Another kind of scheduling mechanism is known as Dynamic Scheduling – In this case, a real-time program requires a sequence of decisions to be taken during execution of the assignment of resource to transactions. Here each decision must be taken without prior knowledge of the needs of future tasks. Dynamic scheduling is not in the scope of this article, so I am not discussing it in detail here. Perhaps we can discuss it in another article.

Code Snippet

Let us take a example of a Master-Slave communication system. Master system is connected to n number of slave systems over serial port (RS 485 network) in multi-drop architecture. Figure 1 shows the typical configuration of this system. Here only one system can talk at a time and others are in listen mode. The Master controls the communication.

Main Routine

Hide   Copy Code

void main(void)
{
    /* Initialise all register of processor and the peripheral devices */
    InitMain();

    /* Register the event handler */
    RegisterTask(MainEventHandler);

    RegisterTask(CheckDataIntegrity);
    ..............

    /* Turn on all the leds for 1 sec as lamp test */
    TurnOnLed(LED, 1000);

    /* Call the application event manager - no return */
    EventManager();
}

In the above case, the RegisterTast() and EventManager() are two important functions. For any application, we have number of tasks and a function represents the entry point of a task, like 'CheckDataIntegrity' . When a device receives a complete data packet, it goes for data checking. RegisterTask() function creates a link-list of function pointers where each node represents a single task. Here I have passed the function pointerMainEventHandler or CheckDataIntegrity as an argument.

Main.h should have the following lines:

Hide   Copy Code

/* Application event handler function pointer */
typedef void (*tEventHandler)(unsigned short *);

/* Link-list definition */
typedef struct TaskRecord
{
    tEventHandler EventHandler;
    struct TaskRecord *pNext;
}tTaskRecord;

static tTaskRecord *mpTaskList = NULL;

Here mpTaskList represents a link-list of function pointers. Considering each node of link list as a entry point of a task, this will execute one by one in EventManager() function. Below is the definition of RegisterTask()function which adds the function pointer into the link-list.

Hide   Shrink    Copy Code

void RegisterTask(tEventHandler EventHandlerFunc)
{
    tTaskRecord *pNewTask;

    /* Create a new task record */
    pNewTask = malloc(sizeof(tTaskRecord));
    if(pNewTask != NULL)
    {
        /* Assign the event handler function to the task */
        pNewTask->EventHandler = EventHandlerFunc;
        pNewTask->pNext = NULL;

        if(mpTaskList == NULL)
        {
            /* Store the address of the first task in the task list */
            mpTaskList = pNewTask;
        }
        else
        {
            /* Move to the last task in the list */
            mpActiveTask = mpTaskList;
            while(mpActiveTask->pNext != NULL)
            {
                mpActiveTask = mpActiveTask->pNext;
            }

            /* Add the new task to the end of the list */
            mpActiveTask->pNext = pNewTask;
        }
    }
}

For this type of application, after initialization there should be an infinite loop for continuous execution. The function EventManager() at the end of the main which is nothing but a infinite loop always checks for active tasks or events. If any event occurs, then it passes that event flag as an argument of the function which is already added into the mpTaskList. So EventManager() function calls MainEventHandler() function with eventIDas an argument. MainEventHandler will check the eventId and do the necessary action or execute the corresponding code. Here the event should be unique for each event-handler function, i.e. two event-handler functions should not check the same eventID.

Definition of EventManager Function

Hide   Shrink    Copy Code

void EventManager(void)
{
    unsigned short AllEvents;
    tTaskRecord pActiveTask

    /* No return */
    while(1)
    {
        /* Read application events */
        AllEvents = mEventID;

        /* Process any application events */
        pActiveTask = mpTaskList;
        while((AllEvents != 0) && (pActiveTask != NULL))
        {
            if(pActiveTask->EventHandler != NULL)
            {
                /* Call the task's event handler function */
                (mpActiveTask->EventHandler)(&AllEvents);

                /* Read application events */
                AllEvents = mEventID;
            }

            /* Move to the next event handler */
            pActiveTask = pActiveTask->pNext;
        }
    }
}

Event can be generated from interrupt service routine or by checking the status of an input pin in polling mode.SerialReceiveISR function generates an event after receiving the complete packet. Since the variablemEventID is modified in the interrupt service routine, it is recommended to disable interrupt while reading.

Hide   Copy Code

#pragma interrupt_level 0
void interrupt IService(void)
{
    /* Receive bit is set when a byte is received */
    if(Receivebit == 1)
    {
        SerialReceiveISR()
    }
    ...........
    /* code for other interrupt */
}

SerialReceiveISR Function

Hide   Copy Code

#pragma inline SerialReceiveISR
void SerialReceiveISR(void)
{    
    static char RxMsgDataCount;
    
    /* If a framing or overrun error occurs then clear the error */
    if(Error == 1)
    {
        /* Indicate a problem was seen */
        mEventID = mEventID | ATTENTION_REQ_FLG;
    }
    else if( RxMsgCount == DataLength)
    {
        /* Packet receive complete */
        mEventID = mEventID | DATA_RECEIVE_COMPLETE;
    }
    else
    {
        /* Store data in memory */
        Store(RxByte);
        RxMsgCount++;
    }
}

Here ATTENTION_REQ_FLAG & DATA_RECEIVE_COMPLETE flags are two bits of a Global variable mEventID, which is 16 bits and each bit triggers the corresponding event when set.

Hide   Copy Code

#define ATTENTION_REQ_FLAG  0x0008
#define DATA_RECEIVE_COMPLETE  0x0001

When the flag is set, the EventManager will call all the registered functions with the eventID as argument.

Hide   Copy Code

void MainEventHandler(unsigned short *Event)
{
    if(*Event & DATA_RECEIVE_COMPLETE)
    {
        /* Do the corresponding action */
        .........
        /* Reset the flag */
        *Event &= ~DATA_RECEIVE_COMPLETE; 
    }
}

Now we can change the variable type to increase the number of flags. If you want to generate multiple number of events, then use a structure rather than a single variable.

C Binary Tree with an Example C Code (Search, Delete, Insert Nodes)

Binary tree is the data structure to maintain data into memory of program. There exists many data structures, but they are chosen for usage on the basis of time consumed in insert/search/delete operations performed on data structures.

Binary tree is one of the data structures that are efficient in insertion and searching operations. Binary tree works on O (logN) for insert/search/delete operations.

Binary tree is basically tree in which each node can have two child nodes and each child node can itself be a small binary tree. To understand it, below is the example figure of binary tree.

Binary tree works on the rule that child nodes which are lesser than root node keep on the left side and child nodes which are greater than root node keep on the right side. Same rule is followed in child nodes as well that are itself sub-trees. Like in above figure, nodes (2, 4, 6) are on left side of root node (9) and nodes (12, 15, 17) are on right side of root node (9).

We will understand binary tree through its operations. We will cover following operations.

• Create binary tree
• Search into binary tree
• Delete binary tree
• Displaying binary tree

Creation of binary tree

Binary tree is created by inserting root node and its child nodes. We will use a C programming language for all the examples. Below is the code snippet for insert function. It will insert nodes.

11 void insert(node ** tree, int val) {
12 node *temp = NULL;
13 if(!(*tree)) {
14   temp = (node *)malloc(sizeof(node));
15   temp->left = temp->right = NULL;
16   temp->data = val;
17   *tree = temp;
18   return;
19 }
20
21 if(val < (*tree)->data) {
22      insert(&(*tree)->left, val);
23   } else if(val > (*tree)->data) {
24     insert(&(*tree)->right, val);
25   }
26 }

This function would determine the position as per value of node to be added and new node would be added into binary tree. Function is explained in steps below and code snippet lines are mapped to explanation steps given below.

[Lines 13-19] Check first if tree is empty, then insert node as root.

[Line 21] Check if node value to be inserted is lesser than root node value, then

• a. [Line 22] Call insert() function recursively while there is non-NULL left node
• b. [Lines 13-19] When reached to leftmost node as NULL, insert new node.

[Line 23] Check if node value to be inserted is greater than root node value, then

• a. [Line 24] Call insert() function recursively while there is non-NULL right node
• b. [Lines 13-19] When reached to rightmost node as NULL, insert new node.

Searching into binary tree

Searching is done as per value of node to be searched whether it is root node or it lies in left or right sub-tree. Below is the code snippet for search function. It will search node into binary tree.

46 node* search(node ** tree, int val) {
47 if(!(*tree)) {
48   return NULL;
49  }
50 if(val == (*tree)->data) {
51   return *tree;
52  } else if(val < (*tree)->data) {
53    search(&((*tree)->left), val);
54  } else if(val > (*tree)->data){
55    search(&((*tree)->right), val);
56  }
57 }

This search function would search for value of node whether node of same value already exists in binary tree or not. If it is found, then searched node is returned otherwise NULL (i.e. no node) is returned. Function is explained in steps below and code snippet lines are mapped to explanation steps given below.

1. [Lines 47-49] Check first if tree is empty, then return NULL.
2. [Lines 50-51] Check if node value to be searched is equal to root node value, then return node
3. [Lines 52-53] Check if node value to be searched is lesser than root node value, then call search() function recursively with left node
4. [Lines 54-55] Check if node value to be searched is greater than root node value, then call search() function recursively with right node
5. Repeat step 2, 3, 4 for each recursion call of this search function until node to be searched is found.

Deletion of binary tree

Binary tree is deleted by removing its child nodes and root node. Below is the code snippet for deletion of binary tree.

38 void deltree(node * tree) {
39 if (tree) {
40   deltree(tree->left);
41   deltree(tree->right);
42   free(tree);
43  }
44 }

This function would delete all nodes of binary tree in the manner – left node, right node and root node. Function is explained in steps below and code snippet lines are mapped to explanation steps given below.

[Line 39] Check first if root node is non-NULL, then

• a. [Line 40] Call deltree() function recursively while there is non-NULL left node
• b. [Line 41] Call deltree() function recursively while there is non-NULL right node
• c. [Line 42] Delete the node.

Displaying binary tree

Binary tree can be displayed in three forms – pre-order, in-order and post-order.

• Pre-order displays root node, left node and then right node.
• In-order displays left node, root node and then right node.
• Post-order displays left node, right node and then root node.

Below is the code snippet for display of binary tree.

28 void print_preorder(node * tree) {
29 if (tree) {
30 printf("%d\n",tree->data);
31 print_preorder(tree->left);
32 print_preorder(tree->right);
33 }
34 }
35 void print_inorder(node * tree) {
36 if (tree) {
37 print_inorder(tree->left);
38 printf("%d\n",tree->data);
39 print_inorder(tree->right);
40 }
41 }
42 void print_postorder(node * tree) {
43 if (tree) {
44 print_postorder(tree->left);
45 print_postorder(tree->right);
46 printf("%d\n",tree->data);
47 }
48 }

These functions would display binary tree in pre-order, in-order and post-order respectively. Function is explained in steps below and code snippet lines are mapped to explanation steps given below.

Pre-order display

• a. [Line 30] Display value of root node.
• b. [Line 31] Call print_preorder() function recursively while there is non-NULL left node
• c. [Line 32] Call print_preorder() function recursively while there is non-NULL right node

In-order display

• a. [Line 37]Call print_inorder() function recursively while there is non-NULL left node
• b. [Line38] Display value of root node.
• c. [Line 39] Call print_inorder() function recursively while there is non-NULL right node

Post-order display

• a. [Line 44] Call print_postorder() function recursively while there is non-NULL left node
• b. [Line 45] Call print_postorder() function recursively while there is non-NULL right node
• c. [Line46] Display value of root node.

Working program

It is noted that above code snippets are parts of below C program. This below program would be working basic program for binary tree.

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

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
}

Output of Program:

It is noted that binary tree figure used at top of article can be referred to under output of program and display of binary tree in pre-order, in-order and post-order forms.

$ ./a.out
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
Searched node=4

Implementation of Hamming Code

C program

#include<stdio.h>
#include<conio.h>
void main() {
 int data[7],rec[7],i,c1,c2,c3,c;
 printf("this works for message of 4bits in size \nenter message bit one by one:  ");
 scanf("%d%d%d%d",&data[0],&data[1],&data[2],&data[4]);
 data[6]=data[0]^data[2]^data[4];
 data[5]=data[0]^data[1]^data[4];
 data[3]=data[0]^data[1]^data[2];
 printf("\nthe encoded bits are given below: \n");
 for (i=0;i<7;i++) {
  printf("%d ",data[i]);
 }
 printf("\nenter the received data bits one by one: ");
 for (i=0;i<7;i++) {
  scanf("%d",&rec[i]);
 }
 c1=rec[6]^rec[4]^rec[2]^rec[0];
 c2=rec[5]^rec[4]^rec[1]^rec[0];
 c3=rec[3]^rec[2]^rec[1]^rec[0];
 c=c3*4+c2*2+c1 ;
 if(c==0) {
  printf("\ncongratulations there is no error: ");
 } else {
  printf("\nerron on the postion: %d\nthe correct message is \n",c);
  if(rec[7-c]==0)
      rec[7-c]=1; else
      rec[7-c]=0;
  for (i=0;i<7;i++) {
   printf("%d ",rec[i]);
  }
 }
 getch();
}

Output