Файл: Programming Microcontrollers in C, 2-nd edit (Ted Van Sickle, 2001).pdf

230 Chapter 5 Programming Large 8-Bit Systems

optimization operation to skip over all variables that can be changed by the hardware portion of the system without knowledge of the program.

Sorting Programs

You might not expect that sorting routines would be important when programming microcontrollers, but there have been several instances in my experience where sorting of a list of data was needed in a microcontroller application. Therefore, let’s examine some sorting routines that can be used with a microcontroller and determine which of several popular approaches is best for use in a microcontroller program.

There are several sorting routines that are popular with program­ mers. The three most-used routines are named the entry sort, the Shell sort, and the quick sort. The entry sort is a routine that is thor­ oughly discredited because it is extremely slow when compared with the other routines. An entry sort orders the contents of an array in place. The first entry in the array is compared with the remaining entries and, if any array entry is smaller than the first, these values are swapped. This operation is then repeated for the second entry in the array followed by the third entry in the array until all entries in the array are compared with all others. When this sequence is com­ pleted, the array is sorted. If there are n entries in the array, the first scan involves n compares, the second involves n-1 compares, the third n-2 and so forth. Therefore, the total number of compares is

n+(n-1)+(n-2)+...1

The value of this sum is n*(n-1)/2. In other words, the entry sort requires on the order of n2 compares.

The Shell sort was discovered in 1959 by D. L. Shell. Like the entry sort, the Shell sort orders the contents of an array in place. The Shell sort splits the n-element array into two halves. The contents of these two halves are compared entry-by-entry and, if the value in the one half is larger than that in the other, the entries are swapped. These arrays are then split again, and the contents of the four arrays are scanned and ordered two at a time as above. Then the four arrays are split into eight arrays and the scan and ordering operation is repeated again. This operation of splitting the arrays and ordering the contents is repeated until there are n/2 arrays of 2 elements each. After this last scan and sort operation, the array is ordered.

Sorting Programs 231

There are n/2 compares completed each scan of the array. However, the sort will be completed after the logarithm based-2 of n times through the array, because log2 n is the number of times that an array that contains n entries can be cut in half. Therefore, the time to execute a Shell sort of an array of n items will be nearly proportional to n*log (n). For even medium-sized arrays, this time is

2

significantly shorter than for the entry sort. For example, an array of 1000 entries requires time on the order of 1000000 to execute an entry sort and 10000 to execute a Shell sort.

Another sort is the quick sort developed by C. A. R. Hoare in 1962. This sort is a recursive routine. It sorts an array in place. Assume that the array runs from left to right and we want to sort the array in ascending values from left to right. An array scan will place at least one of the array values in the proper final array location. This entry is called the pivot entry. As the scan is completed, all entries larger than the pivot value are swapped to the right end of the array and smaller values are placed in the left end of the array. When this operation is completed, the two portions of the array—excluding the pivot entry—are again quick sorted and the result of this recursive operation is that the final result is sorted. This sorting operation also requires time proportional to n*ln(n)/2.

The question now arises whether we should use a Shell sort or a quick sort when writing code for a microcontroller. Let’s examine these functions. The code for a Shell sort is as follows:

/* shell_sort(int v[ ], int i): sort the array v of i things into ascending order */

void swap ( int *, int *);

void shell_sort(int v[ ], int i)

{

int split,m,n;

for( split = i/2 ; split > 0; split /=2 ) for( m = split ; m < i ; m++)

for ( n = m-split; n >=0 &&

v[n] > v[n+split]; n -= split) swap(v+n,v+n+split);

}

232 Chapter 5 Programming Large 8-Bit Systems

The outer loop in the preceding routine controls the way that the array is split. It first splits the array in half and then shrinks the arrays by halves until the sub arrays become zero in width. The second loop steps along the elements of the arrays, and the third loop compares the elements that are separated by split and swaps them when necessary.

The quick sort is:

/* quick_sort( int v[ ], int left, int right) : sort the array v into ascending order */

void quick_sort(int v[ ], int left, int right)

{

int i,pivot; if(right > left)

{

swap(v+left, v+(right+left)/2); /* chose the value at center to pivot on */

pivot = left;

for(i=left+1; i<=right; i++) if(v[i] < v[left])

swap(v+(++pivot), v+i); swap(v+left, v+pivot); /* put the partition

element in place*/ quick_sort(v,left, pivot-1); quick_sort(v,pivot+1,right);

}

}

The swap routine for both of these sorts is the same:

/* swap(int *, int *) : swap two integers in an array */

void swap(int *i, int *j)

{

int temp; temp = *i; *i=*j; *j=temp;

}

One of the nice things about both of these programs is that the swap operation is not built into the program. Therefore, you can swap values

Sorting Programs 233

as was done above, but also, you can swap pointers from an array of pointers to order a set of data that would be difficult to swap. For example, if you had a collection of words, you could use a srtcmp() routine to determine whether one word was lexically larger than the other and then write a swap routine that merely swapped the pointers to these words rather than swapping the words themselves. This approach to sorting a list of words is relatively simple. On the other hand, it would be extremely difficult—nearly impossible, in fact— to sort a list of words that are packed into memory.

The following program is used to test the performance of the above sort routines. The program simply makes an array of 11 entries and sorts the array by both the Shell sort and the quick sort. The result of this program is printed out below.

#include <stdio.h> main()

{

int v[]={81,99,23,808,3,77,18,27,128,360,550}; int i,k[11];

for (i=0;i<11;i++) k[i]=v[i]; shell_sort(k,11); for( i=0;i<11;i++)

printf (“%d “,k[i]); printf(“\n”); quick_sort(v, 0,11 -1); for( i=0; i<11; i++)

printf(“%d “,v[i]); printf(“\n”);

}

The original array is not printed out by the program, but the order of the array is seen in the above listing. The two sort programs sort the values correctly.

3 18 23 27 77 81 99 128 360 505 808

3 18 23 27 77 81 99 128 360 505 808

The quick sort routine is not the best example of recursive programming. Usually, the use of recursion results in a program that is significantly shorter than would be expected with conventional

234 Chapter 5 Programming Large 8-Bit Systems

linear programming. Here, the Shell sort requires fewer lines of C code and, as we will see, the Shell sort has a smaller assembly language program. You would not expect the linear program to be shorter in either C or assembly language. These two programs were compiled and the results analyzed.

The Shell sort requires 0x78 (120) bytes of code while the quick sort needs 0xaa (170) bytes of code. This amount of extra code would not be a serious cost if that were the end of the costs. However, each time a recursive routine calls itself it must establish an argument set that contains all of the variables to be passed to the function. When the quick_sort routine calls itself, it must pass three parameters. These parameters are usually passed in either the stack or in computer registers. When quick_sort returns control to the calling program, the stack pointer must be corrected. quick_sort will continue calling itself repeatedly while the value of the parameter right is greater than the value of the parameter left when the function is entered. Each time the function is called, the program will create a new stack frame which must be made available from RAM. Unfortunately, RAM is usually a more precious commodity than ROM to a microcontroller.

It is possible to get an idea about how much RAM is needed to do a quick sort. The stack frame consisting of six bytes—four bytes for parameters plus two bytes for the return address—must be created each time quick sort is entered. You can count the maximum number of times recursive routine calls itself. The maximum depth is the number of times the function is called before a normal return to the calling function is executed. The depth is found by incrementing a count each time the function is entered. Whenever control is passed back to the calling function through the normal return sequence at the end of the function, the depth will be evaluated to determine if it is the largest value seen so far, and then the depth will be returned to zero. The two listings below incorporate these modifications.

/* quick_sort( int v[ ], int left, int right) : sort the array v into ascending order */ void quick_sort(int v[ ], int left, int right)

{

int i,value;

extern int calls, depth, max_depth;

Sorting Programs 235

calls++; /* count the number of times called */ depth++;

if(right > left)

{

swap(v+left, v+(right+left)/2); /* chose the value at center to partition on */

value = left;

for(i=left+1; i<=right; i++) if(v[i] < v[left])

swap(v+(++value), v+i); swap(v+left, v+value); /* put the partition

element in place*/ quick_sort(v,left, value-1); quick_sort(v,value+1,right);

}

if(depth>max_depth) max_depth=depth; depth=0;

}

void swap ( int *, int *);

void quick_sort(int v[ ], int left, int right) ; #include <stdio.h>

int calls, depth, max_depth; main()

{

int v[11]={81,99,23,808,3,77,18,27,128,360,550}; int i;

quick_sort(v, 0,11 -1); for( i=0; i<11; i++)

printf(“%d “,v[i]); printf(“\n”);

printf(“calls=%d\nmax_depth=%d\n”,calls,max_depth);

}

Note that the global variables calls and depth are incremented each time quick_sort() is entered. When quick_sort() is exited through its normal return procedure at the end of the routine, depth is examined to determine if it is greater than max_depth .

236 Chapter 5 Programming Large 8-Bit Systems

If it is, max_depth is replaced by depth. depth is reset to zero prior to returning through the end of the quick_sort() routine. The result of this program is as follows:

3 18 23 27 77 81 99 128 360 550 808 calls=15

max_depth=4

To sort the above 11 element array, the program called quick_sort() 15 times and the maximum number of stack frames that were created at one time was four. Each stack frame consists of four bytes for data and two bytes for the return address. Therefore, at one time in the execution of this program, the sort routine required 24 bytes of stack space in addition to the memory area required to hold the array being sorted. This is distressing when you remember that the array is 22 bytes long!

Careful analysis of the program will show that the expected maximum number of stack frames for the quick sort is proportional to ln2n. Therefore, the stack frame performance will get better when the size of the array is larger. The main problem with the use of any recursive routine is that you do not know exactly the number of stack frames needed and therefore you must always analyze the maximum stack frame depth and allow that amount of stack for execution of the function.

The quick sort is faster than the Shell sort under most—but not all—circumstances. Let’s take the example of having a quick sort and a Shell sort compiled to run under the same host computer. If larger arrays are used to do the measurement and random arrays are used, we will find that the sort time for both quick sort and Shell sort depends on the array. The reason for this difference is the number of swap routines that must be executed during the sort operation. Therefore, there will be some arrays that the Shell sort will sort quicker that the quick sort. However, the quick sort is usually faster than the Shell sort.

The Shell sort is every bit as flexible as the quick sort and can be used to sort different types, character strings, and swap pointers rather than swap the objects being sorted. Therefore, in a microcontroller application where memory is always limited, you should use a Shell sort rather than a quick sort because the Shell sort has no funny memory requirements that will always occur with a recursive routine like the quick sort.

Data Compression 237

The purpose of the above discussion is to demonstrate that the programmer must exercise much more care in the details of program design for a microcontroller than is necessary for a larger machine. The above sorting routine would be of no concern for a typical desktop machine because RAM is usually of no consideration with such machines. It might not be a problem for some microcontroller applications, but in a case where RAM is limited and needed, it might make the difference between being able to get the program to run or not.

In most instances, the elegance of recursive code has a cost of RAM. Usually a recursive program will be slower than the equivalent linear program. The microcontroller programmer must examine each instance of code to determine if the elegant recursive program has hidden side effects that end up costing more in computer resources than is gained in small code size.

EXERCISES

1.Write a program to run on a host computer that will test the time required to execute both a quick sort and a Shell sort on random large arrays. Make the array sizes selectable from the keyboard.

2.Test both the quick sort and Shell sort for various array sizes. Ex­ amine the time required to execute the sorts for several random arrays. Explain what is happening when arrays of 4090, 4095, and 4096 entries are sorted.

Data Compression

Another program problem that can arise with microcontroller applications is handling displays in which there are many phrases and names each consisting of several letters. The question that must be considered is the most efficient method of storing these phrases and names, in memory so that they can be recalled for display. The oldest, and yet very effective, method of compressing the data for storage is to use a Huffman code. This code is developed based on the statistical occurrence of each letter in the alphabet. A letter that occurs frequently will be given a short code sequence. A letter that is seen infrequently can be assigned a long code, which will not appreciably affect the number of bits per letter in the message.

238 Chapter 5 Programming Large 8-Bit Systems

Huffman codes are self-synchronizing. A long string of characters can be represented as a series of bits, and the decoding program can find each character in the sequence without any special flags to designate the end of each character. Messages stored as ASCII characters require at least 7 bits per character, and because of the nature of storage in a computer, 8 bits are usually assigned to each character. With a Huffman code, it is possible to reduce the average number of bits per character for the whole English language to about 4.5 bits per character. Sometimes even fewer bits are needed with limited messages.

The programmer does all of the Huffman encoding and the computer must decode the messages for display. Huffman decoding requires extensive bit manipulation, so C is an ideal language to decode the messages.

A Huffman decoding scheme can be represented by a strictly binary tree. A binary tree is comprised of a collection of nodes. Each node has two descendents, often called the right and left descendents (thus the term binary tree). The terminating node in a tree is called a leaf. In a strictly binary tree, every nonleaf node has both a right and left descendent. If a strictly binary tree has n leafs, it has a total of 2n – 1 nodes.

The Huffman code is decoded in this manner. The sequence always starts at the root node. The code sequence to be decoded is examined a bit at a time. If the bit is a 0, move to the left node. If the bit is a 1, move to the right node. The tree is traversed until a leaf is found which contains the desired character. The sequence is then restarted at the root node. If the tree is not known, the sequence of bits is bewildering. Usually it is found that the occurrence of ones and zeros is about equally likely, so no statistical analysis can be applied to decode the sequence easily. A disadvantage is that if a single bit in the sequence is lost, the remainder of the code stream is undecipherable. Of course, the advantage to the Huffman code is that it takes somewhere between one-quarter and one-half the number of bits to represent a message as is required by the ASCII code. A Huffman Code tree is shown in Figure 5-1. The bit sequence 111111100101111010100000 as decoded by this tree is seen to spell the word “committee.” This sequence requires 23 bits, and the ASCII code needed to represent committee is 72 bits long. Of course, this tree was designed specifically for the word “committee,” but try to encode other words that can be made of these same letters such as “tic,” “me,” “come,” “tom,” “mite,” etc., and you will find that every word that can be derived from this tree requires fewer bits than the corresponding ASCII sequence would need.