11

PROGRAMMING EXAMPLES-II

CHAPTER OBJECTIVES

In the last three chapters, we have discussed about MCS-51 instructions related to subroutines, logical operations and Boolean variable operations. In this chapter, we will study a few example programs dealing with their applications. After completion of the chapter, the reader should be able to understand

• Application areas of subroutines.
• Application techniques of logical and Boolean instructions.
• Some important solution techniques such as packing and unpacking of BCD numbers and bubble sorting.

11.1 | Introduction

As we have discussed about most of the instructions of MCS-51, it would be appropriate now to solve few more example problems highlighting applications of these instruction set. Problems in this chapter are little more complex than those presented earlier in Chapter 7. After presenting the problem, basic solution techniques are discussed followed by the algorithm or flowchart. Complete program listing is placed thereafter with adequate comment statements for easier understanding of the programming logic.

11.2 | Count 1s in a Byte

Example 11.1

Purpose: Application of rotate instruction.

Problem

Find out number of 1s in a byte, available in internal data memory location 30H. Store the result in the accumulator itself.

Solution

We can use either RRC A or RLC A instruction to count number of 1s (or even 0s) in any byte. The LSB (or MSB, as the case might be) would be shifted to the carry (CY) flag helping the program to decide whether the bit is 0 or 1 (Fig. 11.1). The byte must be loaded in the accumulator for this purpose. We are to use one register as a counter for rotating the byte eight times. A second register is necessary for storing the result.

Figure 11.1 Schematic of set bit counting using RLC A instruction

Algorithm

Step 1: Initialize by loading the accumulator with the target byte, R7 by bit counter, that is 8, and clear R6 to store the result.

Step 2: Rotate the accumulator left through carry. Bit 7 (MSB) is shifted from the accumulator to the CY flag.

Step 3: If CY is 0 then go to Step 5.

Step 4: Increment R6 by 1.

Step 5: Decrement R7 by 1. If R7 is not 0 then go to Step 2, otherwise return.

; Subroutine to count number of 1s in a byte.

; First three instructions complete the initialization procedure.

; Iteration to count number of 1s in the accumulator starts from here.

; Iteration complete. Result in R6. Copy it to the accumulator.

MOV	A, R6	; result in the accumulator
RET

C-version

#include <regx51.h>

void main(void)

{

              register unsigned char *n, i = 0, count = 0, *acc;

              unsigned char number, mask;

              n = 0x30;

              number = *n;

              mask = 0x01;

              acc = 0xE0;                 // address of accumulator is E0H

                         for (i = 8; i > 0; i --)

                         {

                                     if (number & mask)

                                     count++;

                                     number = number >>1;

                         }

              *acc = count;

}

11.3 | Unpack a BCD Number

Example 11.2

Purpose: How to unpack a BCD number and an application of ANL and rotate instructions.

Problem

A packed BCD number is in location 30H. After unpacking, store it in R6 (lower digit) and R7 (higher digit).

Solution

BCD numbers vary from zero to nine, and they always occupy 4 bits. Therefore, two BCD numbers may be accommodated within a byte. The upper and lower nibbles (4 bits) of the byte may be separated by using AND operation. There should always be a leading zero before any unpacked BCD number (Fig. 11.2). Note that 9 of 95 (BCD MS digit) become 09 after unpacking.

Figure 11.2 Packed and unpacked BCD numbers

Algorithm

Step 1: Load the accumulator by packed BCD number to be unpacked.

Step 2: Take out LS BCD digit by ANDing the accumulator with 0FH. Store it in R6.

Step 3: Reload the accumulator by packed BCD number.

Step 4: Take out MS BCD digit by ANDing the accumulator with F0H.

Step 5: Rotate the accumulator four times to shift the digit to lower nibble.

Step 6: Store it in R7 and return.

; Subroutine to unpack a BCD number.

C-version

#include <regx51.h>

void main(void)

{

              unsigned char *pPackedBcdNum;

              unsigned char lowerDigit, higherDigit;

              // initialize

              pPackedBcdNum = 0x30;

              lowerDigit = *pPackedBcdNum & 0x0F;

              higherDigit = (*pPackedBcdNum & 0xF0)>>4;

              while(1);

}

11.4 | Pack BCD Digits

Example 11.3

Purpose: How to pack two BCD digits and application of ORL and rotate instructions.

Problem

Two unpacked BCD digits are available in location 30H (MS digit) and 31H (LS digit). Write a program to pack these two and store in R7.

Solution

The method to be adopted is just opposite of the method adopted in the previous example.

Algorithm

Step 1: Load pointer by address of MS BCD digit.

Step 2: Load MS BCD digit in the accumulator.

Step 3: Increment pointer by 1 to target LS BCD digit.

Step 4: Rotate the accumulator left four times to shift MS BCD digit to upper nibble.

Step 5: OR accumulator with LS BCD digit as pointed by the pointer.

Step 6: Store the accumulator in R7 and return.

; Subroutine to pack two BCD digits.

C-version

unsigned char msDigit _at_ 0x30;

unsigned char lsDigit _at_ 0x31;

#include <regx51.h>

void main(void)

{

              unsigned char packedBcdNum;

              packedBcdNum = (msDigit<<4) | (lsDigit);

              while(1);

}

11.5 | Pack Array of Unpacked BCD Digits

Example 11.4

Purpose: How to handle multiple arrays using only one pointer.

Problem

Using only one pointer, R0, pack two arrays of BCD digits to create a third array. The higher digits are available from 30H to 3FH. Lower digits are available from 40H to 4FH. Packed BCD numbers are to be stored from 50H to 5FH.

Solution

As this problem deals with the three arrays, three different pointers are generally expected. However, even with a single pointer it may be solved easily as some symmetry exists in the data structure of this problem.

Fig. 11.3 illustrates the problem with a few sample inputs and outputs. As an example case, we may indicate that 08 to be taken from address 30H and 02 may be copied from address 40H. After packing these two, the packed number 82 is to be saved in the location 50H. It may be observed that last 4 bits of all these three addresses are identical (30H, 40H, 50H). Only MS 4 bits are changing as 3, 4 and 5. Utilizing this special case, we may develop the program using only one pointer, R0. The algorithm and complete program would be as follows.

Figure 11.3 Problem definition of Example 11.4

Algorithm

Step 1: Select bank #0, load pointer by 30H and counter by 16d (10H).

Step 2: Load higher digit in the accumulator through the pointer. Shift it to the higher nibble.

Step 3: Change MS digit of pointer to 4.

Step 4: Logically OR accumulator with lower digit through the pointer.

Step 5: Change MS digit of the pointer to 5.

Step 6: Save packed BCD number from the accumulator to its storage location as pointed by the pointer.

Step 7: Restore MS digit of the pointer to 3.

Step 8: Increment the pointer by 1.

Step 9: Decrement counter by 1. If counter is not 0 then go to Step 2. Otherwise return.

; Program to pack two arrays of unpacked BCD digits using only one pointer (R0).

; Source address varies from 30H to 3FH for MS digits and 40H to 4FH for LS digits.

; Destination address for packed BCD digits varies from 50H to 5FH.

; First three instructions complete the initialization process.

; Iterative procedure for packing BCD digits starts.

; To start packing of next digit, the loop should start from here.

; Now process the pointer to target the next array of same LS address nibble.

; This is done by the following two logical operations with R0 of bank #0.

; Results are available in the directly addressed location (R0 of bank #0).

; Note that the content of the pointer R0 is changed from 3x to 4x by these two instructions.

 

ANL	00H, #0FH	; clear the MS nibble keeping lower unchanged
ORL	00H, #40H	; insert 4 in the MS nibble

; Now pointer is targeting the second array. Use the pointed number.

 

ORL

A, @R0

; the accumulator has packed number

; Now process the pointer to target the third array, for storage (make 4x as 5x).

 

ANL	00H, #0FH	; clear MS nibble
ORL	00H, #50H	; insert 5 in it

; Pointer is now showing the saving location. Save the packed number from the accumulator.

 

MOV

@R0, A

; store the packed number

; Process the pointer to target the first array (change 5x to 3x).

ANL	00H, #0FH	; clear the MS nibble
ORL	00H, #30H	; restore 3 in it

; Increment pointer to target next location of the first array. Then continue packing.

INC	R0	; update pointer to target next higher digit
DJNZ	R7, LOOP	; continue for all digits
RET		; over

C-version

#include <regx51.h>

void main(void)

{

              unsigned char *pMsDigit, *pLsDigit, *pPackedBcdNum;

              unsigned char i;

              // initialize

              pMsDigit = 0x30;

              pLsDigit = 0x40;

              pPackedBcdNum = 0x50;

              i = 0;

              for(i=0; i<=0x0F; i++)

              {

                        pPackedBcdNum[i] = (pMsDigit[i]<>4 | (pLsDigit[i]);

              }

              while(1);

}

11.6 | Find Largest and Smallest Integers of an Array

Example 11.5

Purpose: How to implement multiple operations in a single pass.

Problem

Find the largest and smallest from N unsigned integers. Assume the value of N to be available in the internal data memory location 30H. The array starts from location 31H. Store the maximum integer in R4 and minimum in R3.

Solution

Both maximum and minimum values of any array may be identified by a single pass. To start with, register R4 is loaded with the worst maximum integer that is 00H. Similarly, R3 is initialized as FFH to represent the worst minimum integer. Register bank # is selected as 0 only to use direct addressing for registers. CJNE instructions are used to get the status of the comparison reflected in the CY flag. If the present integer is larger than the integer stored in R4 then R4 is replaced by the current integer. In identical manner, the minimum number is selected in R3. R7 works as a counter. The flowchart is shown in Fig. 11.4. The program listing is given below.

Figure 11.4 Flowchart of Example 11.5

; Program to find the maximum and minimum numbers within an array.

; First five instructions complete the initialization procedure.

; The pass to find largest and smallest unsigned integers starts from here.

; To check the next integer of the array, the procedure must start from here.

; Following five instructions check and store the maximum integer, so far.

; The term is still in the accumulator, unchanged.

; Following three instructions check and store the minimum integer, so far.

; Checking of one term is over. Point to the next term and loop on, if necessary.

C-version

#include <regx51.h>

void main(void)

{

              unsigned char *pLocN, *pArray, i;

              unsigned char maxNum, minNum;

              // initialize

              pLocN = 0x30;

              pArray = 0x31;

              maxNum = *pArray;

              minNum = *pArray

              if(*pLocN > 0)

              {

                          for(i=0; i<*pLocN; i++)

                          {

                                      if(pArray[i]>maxNum

                                      {

                                                 maxNum = pArray[i];

                                      }

                                      else if (pArray[i]<minNum)

                                      {

                                                 minNum = pArray[i];

                                      }

                          }

              // store results if needed

              }

              while(1);

}

11.7 | Bubble Sorting

Example 11.6

Purpose: Example of nested loops.

Problem

A few unsigned integers are stored from the location 31H onwards of the internal data memory area. Arrange these integers in ascending order. The number of terms of the array is available in the location 30H. Store the arranged integers from 31H itself.

Solution

The term ascending order means larger number should be in higher address and smaller number in lower address. In MCS-51, generally higher addresses are shown at the top with respect to the lower addresses. However, for the sake of easier understanding, in the following three illustrations, higher addresses are shown at lower levels.

One of the many methods to rearrange a random array of integers in ascending or descending order is known as ‘bubble sorting’ technique. If there are N integers then there should be N–1 passes, and in every pass there should be one or more comparison and interchanging of places if not found in order. Using a set of four integers, this method is illustrated through the following three diagrams.

Fig. 11.5(a) shows the initial condition of an array, which is to be arranged in the ascending order. To start with, the top two integers, namely F6H and 94H, are checked for correct order. As they are not, their positions are interchanged, which is shown in Fig. 11.5(b). Now the next two integers, namely F6H and 48H, are checked for the correct order. As they are not, their positions are interchanged (known as swapping) and their condition was achieved as shown in Fig. 11.5(c). The third and the final comparison takes place between the last two numbers, i.e., F6H and 07H. As they are not in the correct order, they are also swapped, and the final position after the first pass is achieved as shown in Fig. 11.5(d).

Figure 11.5 Pass 1 steps (a) first, (b) second, (c) third comparisons and (d) final condition

The second pass starts with the condition shown in Fig. 11.6(a). After comparing first two numbers and swapping (they were not in correct order), the position at which it arrives is shown in Fig. 11.6(b). Similarly, the second checking takes place, and we arrive at the condition shown in Fig. 11.6(c). At this stage, the third comparison indicates that the numbers are in the correct order. Therefore, they were left as they were, and we arrive at the final position of the second pass shown in Fig. 11.6(d).

Figure 11.6 Pass 2 steps (a) first, (b) second, (c) third comparisons and (d) final condition

Fig. 11.7(a) presents the starting condition of pass #3. After checking the order, first two integers were interchanged within their places, and the condition of the array becomes as shown in Fig. 11.7(b). However, the remaining two comparisons find the numbers that are in order resulting in no change of their respective positions. Fig. 11.7(d) shows the final condition of the array at the end of pass 3. Here, we find that all four integers are properly ordered in their respective places to indicate an ascending order list.

Figure 11.7 Pass 3 steps (a) first, (b) second, (c) third comparisons and (d) final condition

If it is observed then we may find that more the iteration progresses, lesser would be the number of comparisons required. For example, in Fig. 11.6(c) we find that the last comparison is not necessary, and in Figs 11.7(b) and (c), the last two comparisons may be avoided. As a matter of fact, the number of comparisons required is inverse of the pass number, which decreases continuously.

Although the description of the procedure takes larger space, when this programming logic is implemented, it does not make the program too long. Flowchart of the technique is shown in Fig. 11.8 and the program listing would be as follows.

; Program for bubble sorting for ascending order.

; First three instructions complete the initialization process.

; Iteration for sorting starts. To start the next pass, control must come here.

; Comparison for the present pair of integers (and eventual swapping) starts from here.

; Compared integers are not in order. Interchange their places.

MOV	A, @R0	; get the second term in A
DEC	R0	; point to the first term’s location
MOV	@R0, A	; store the second term there
INC	R0	; point the second term’s location
MOV	@R0, 04H	; store the first term there

; Following instruction checks for remaining numbers of the comparison necessary.

; Following instruction checks whether any more pass is pending.

DJNZ	R7, PASS	; continue, if necessary
	RET	; sorting complete.

Figure 11.8 Flowchart using bubble sorting for ascending order

11.8 | Find the Sum of Factorials

Example 11.7

Purpose: Example of nested subroutines.

Problem

A few random unsigned integers are stored from the internal data memory location 31H onwards. Number of terms (N) is available in location 30H. Assuming that none of these numbers is greater than 5, find the factorials of these integers and then find their sum. Assume that the sum would not exceed 8-bit value.

Solution

Factorial of any integer, say X, is calculated by multiplying all integers from X to 1. Although MCS-51 offers instruction for multiplication, that is MUL AB, we are yet to discuss about this instruction, which would be done in Chapter 12. However, multiplication may also be done by repeated addition, as we have discussed in Example 8.1. So, without using MUL instruction, a subroutine may be developed to find the product of the two integers by repeated additions.

Another subroutine may be planned for calculating the factorial of any integer. The main program is to call this subroutine and calculate the sum of factorial of the random integers of the array. The flowchart of the main program is shown in Fig. 11.9.

Figure 11.9 Flowchart for the main program (sum of factorials)

; Program to calculate the sum of factorials of the random integers of an array.

; At return, the sum would be in R2.

; Registers (bank #0) used:

; R0 = pointer to stored integers

; R2 = sum of factorials of the integers

; R7 = integer counter

; A = computed results

Flowchart of the subroutine FACTO to calculate factorial is given in Fig. 11.10. Note that both R4 and R3 were used for this purpose. R3 is decremented in steps of 1 to get the next lower integer, which was multiplied with the product, in R4. At return, result would be in the accumulator.

Figure 11.10 Flowchart of subroutine for calculating factorial

; Name:	FACTO
; Function:	Calculates factorial of an integer (less than 6)
; Input:	A contains the integer
; Output:	A contains the factorial value
; Calls:	PRODCT
; Uses:	A, R3, R4

Fig. 11.11 shows the flowchart of the subroutine to multiply two integers by repeated additions. The subroutine is placed after that.

Figure 11.11 Flowchart of the subroutine for multiplying two integers

; Name:	PRODCT
; Function:	Calculates the product of the two unsigned integers by multiple additions.
; Input:	R3 and R4 having two integers
; Output:	Product available in the accumulator. R3 remains unchanged. R4 cleared.
; Calls:	None
; Uses:	A, R3, R4

PRODCT:	CLR	A
ADDIT:	ADD	A, R3
	DJNZ	R4, ADDIT
	RET

11.9 | Sort Out Numbers Divisible by 4

Example 11.8

Purpose: To substitute division operation by the logical operation in special cases.

Problem

Create a new array by removing only those integers that are perfectly divisible by 4 from an array, starting from 31H. Location 30H contains number of terms of this array. The new array is to be created from the location 60H. At return, the accumulator should indicate number of terms found. Original locations with digits divisible by 4 should be replaced by null.

Solution

For an unsigned integer to be divisible by 4, bits 0 and 1 must be zero. The algorithm to solve this problem is given below.

Algorithm

Step 1: Initialize by loading counter (R7) by N value from the location 30H. Load pointer R0 by the starting address of source array (31H). Load pointer R1 by the starting address of the destination array (60H). Clear the term counter (R6).

Step 2: Get the term pointed by R0 in the accumulator. Logically AND it with 03H to clear MS 6 bits.

Step 3: If the accumulator is not zero then go to Step 5.

Step 4: Load the term again in the accumulator using R0. Then store it using R1. Increment both R1 and R6 by one. Clear the location pointed by R0.

Step 5: Increment R0 and decrement R7 by one. If R7 is not zero then go to Step 2.

Step 6: Load the accumulator from R6 and return.

; Program to find terms divisible by four.

SUMMARY

Eight example programs dealing with the applications of logical instructions, Boolean instructions and subroutine calls were discussed in this chapter. Examples are taken from the counting number of set bits in any byte, packing and unpacking BCD numbers, finding maximum and minimum terms of any random integer array, bubble sorting method, calculation of factorials and finding out numbers divisible by 4.

POINTS TO REMEMBER

• After unpacking the MS BCD digit, it must be shifted to the lower nibble of the byte.
• An easier way to multiply or divide an unsigned integer by 2, 4, 8 etc. is to rotate the byte left or right, respectively.

REVIEW QUESTIONS

Evaluate Yourself

1. In Example 11.1, if the location 30H contained 57H then at return the accumulator would contain
   1. 05H
   2. 03H
   3. 57H
   4. none of these
2. What would happen if the RRC A replaces the fourth instruction of Example 11.1?
   1. Count no. of 0s
   2. No change
   3. Count both 1s and 0s
   4. None of these
3. If a packed BCD number, say 28, is unpacked, which of the following would be its unpacked most significant digit?
   1. 02
   2. 0002
   3. Either of these
   4. None of these
4. In Example 11.5, what would be the value of the third byte of the first CJNE instruction?
   1. 04H
   2. 02H
   3. 00H
   4. None of these
5. In Example 11.7, if the stack pointer was initialized at 07H, what would be its value during execution of the subroutine PRODCT?
   1. 0CH
   2. 0BH
   3. 009H
   4. None of these
6. What would be the hexadecimal value of the factorial of 4?
   1. 05H
   2. 0AH
   3. 18H
   4. None of these
7. What would be the characteristics of any integer perfectly divisible by 8?
   1. LS 3 bits 0
   2. LS bit 0
   3. LS 4 bits 1000
   4. None of these
8. To change 33H to 53H, we should AND 33H with
   1. FFH and then OR with 53H
   2. 0FH and then OR with 50H
   3. F0H and then OR with 50H
   4. none of these
9. If the bubble sorting technique is applied to an array with four integers then in the worst case, the total number of comparisons would be
   1. 6
   2. 9
   3. 10
   4. none of these
10. In Example 11.7, if four integers of the array were one, two, three and four then what would be the value of the accumulator at the end of the main program?
    1. 18H
    2. 33H
    3. 21H
    4. None of these

Search for Answers

1. Apart from the accumulator, does any other register offers the option of rotating it circular or through the CY flag?
2. Make a list of all instructions capable of counting the cleared bits in a byte.
3. What is the difference between the packed and the unpacked BCD numbers?
4. In Example 11.5, what is the reason to store 00H in the place where the maximum number would be placed?
5. What is meant by the term ‘pass’ in the case of sorting?
6. What is meant by the term ‘swapping’? In which example it was implemented?
7. If an array of randomly placed 50 integers are to be sorted for descending order, what should be the maximum number of passes required in the bubble sort method?
8. Is it possible to develop a routine which would jump to a relative address if the accumulator is having even parity? Justify your answer.
9. How is it possible to extend the program in Example 11.8 so that after completion of deletion the deleted array may be compacted?
10. Find a method to generate prime numbers up to 50d.

Think and Solve

1. Is it possible to regain the original accumulator content by repeated execution of the RLC A instruction? If yes, then how many times it should be executed?
2. What modifications are necessary in the program given in Example 11.1 so that it is able to count number of 0s in a byte?
3. Is it possible to solve Example 11.4 using only one pointer if the addresses of the three arrays are changed to 30H to 3FH, 42H to 51H and 55H to 64H, respectively? Justify your answer.
4. Is it possible to solve Example 11.7 without using subroutine calls? Assume that MUL instruction may be used for the multiplication of any two integers.
5. In Example 11.4, the pointer was changed for other array by first AND followed by OR operations. What would happen if these operations were interchanged in sequence?
6. In Example 11.5, is it possible to calculate the average value of all numbers without using any extra pass?
7. In Example 11.7, if the array was in the ascending order in the beginning then also N–1 passes were executed by the program. Is there any method to reduce the number of redundant passes in such cases?
8. Find out another method of sorting, and compare its efficiency with the bubble sorting method.
9. Develop a subroutine to check whether any given unsigned integer is perfectly divisible by 7 or not. Using this subroutine, write a program to delete all integers divisible by 7 from a given array starting from 31H. Location 30H stores the number of terms of the array. At the end of the program, R7 should contain the number of deleted terms.
10. An array from 30H to 3FH contains unpacked MS digits, and the corresponding unpacked LS digits are stored from 40H to 4FH. Write a program to pack the BCD numbers and store them from 50H to 5FH. Then call a subroutine to arrange these packed BCD numbers in descending order.