CSCI 255 Lab

Lab 9 -- Assembly Language Programming: The Syracuse Sequence

(This lab was inspired by a laboratory exercise presented in ECE3724: Microprocessors developed by Jones, Reese and Bruce and offered at Mississippi State University.)

Part 0: Overview & Review

In this lab, you will convert a C program into PIC24 assembly language. The C program generates the syracuse sequence, a subject of interest in number theory. The sequence is generated by a very simple algorithm. Take any number as an input, and divide it by 2 if that number is even, or multiply by 3 and add 1 if that number is odd. The conjecture is that, no matter what number you start with as an input, if you apply the algorithm repetitively to each number generated, the output will be a sequence of numbers terminating in1. However, this is still an open question, and no one has proven this conjecture.

The new programming tasks required in this lab are:

Mapping Flow control statements to assembly language

There are 2 main steps required to implement a flow control statement in assembly language:

  1. Set the status register bits based on the value of the test expression. This step requires that you evaluate the test expression.
  2. Branch to a statement label based on the value of the status register set in step 1.

Here's an example:

while (i < 10) { ... }

A partial translation of this loop structure into assembly language is:

MOV #10, W0 ; setup to evaluate the test expression
CP i ; set status register bits by comparing i to 10 ; specifically calculate (i-10)
BRA GEU, end_loop ; branch if (i-10) is greater than or equal to 0 ; this means the loop test is not true

Note that (1) a compare instruction (CP) can be used to set the status register bits, and (2) there are many forms of the branch instruction (BRA), one for each possible comparison outcome. See the PIC 24 instruction set for variations of the CP and BRA instructions.

Refer to your class lecture notes for more assembly language programming examples.


 

Part 1: Write syracuse.c in assembly language

As in Lab 7, begin by opening the mptst_word.mcp project which can be found in the chap 3 directory of the PIC24 code archive downloaded in Lab 7.

Use Project -> Save Project As and save the mptst_word project as a new project named syracuse. Save the mptst_word.s file as syracuse.s. Right-click on the mptst_word.s file in the left-hand workspace window and use the Remove option to remove it from the syracuse project. Right click on the Source Files and use Add Files to add the syracuse.s file to the project. Edit the syracuse.s file and remove all of the instructions between the comment, ";User Code starts here" and the "done:" statement label. You can now use this file as the start of a new program.

The program syracuse.c contains several statements such as a prompt for user input, a call to main(), and a return statement, that we will not translate to assembly code. The relevant portion of the program is follows:

int count, num ;
num = 6;           ;              // added to replace user input
count = 0 ;
while (num != 1) {
printf("%8d\n", num) ; // don't translate to assembly if (num%2==0) { num = num/2 ; } else { num = 3*num + 1 ; } ++count ; } printf("%8d\n\n", num) ; // don't translate to assembly
printf("iterations: %d\n", count) ; // don't translate to assembly

Your job is to translate the code above (minus the printf statements) into an assembly language program that calculates the same values for num and count. The output of the program above is:

syracuse
  6
  3
  10
  5
  16
  8
  4
  2
  1

iterations: 8

You should verify that your assembly language program calculates these values by watching memory. Use the watch window to monitor the values of the variables num and count, and any registers you use, such as WREG and SR (the status register). Also, use the data memory window to monitor the memory locations of the variables. Write your program, simulate it, and verify that you are producing the correct results at each iteration of the while loop.

Checkoff

Begin the simulation and show your instructor two iterations of your while loop as well as the source code.  

Recommended Approach

You should not try to ‘optimize’ away any statements – you should implement the C code exactly as shown. You must place a comment on a line by itself giving the line of C code followed by the assembly instructions which implement this C code. In addition, you should place comments to the right of assembly instructions which clarify their purpose. The required comments are demonstrated below.

  
; i = avalue;      
mov #avalue, W0  ; W0 = 100
mov WREG,i       ; i = 100

; i = i + 1;
inc i              ; i = i + 1
 
; j = i
mov i,WREG         ; W0 = i
mov WREG,j         ; j = W0

Implement your assembly language solution one step at a time:

  1. Get variable initialization working correctly.
  2. Implement the loop with an empty body and verify that the loop executes correctly the first time.
  3. Trace the C code to determine which if-else clause is executed the first time through the loop. Implement that if-else clause with an empty body for the other clause, then test execution through the loop one time, verifying that you get correct values.
  4. Implement the other clause to complete your implementation. Trace variable values each time through the loop, and debug problems when you see a deviation from the C output.