Tutorial 1: Basic Assembly and Branching

Note

This is for practice, not for marks. Treat this as additional study material to help you develop your knowledge and skills on these topics. During the tutorial session, the TA will explain how to solve these problems.

For this tutorial, we will use basic RISC operations as seen in the Lecture 1 (Computer Technology and Abstractions).

Question 1

Write an assembly program for pop-counting a 32-bit register. Pop counting is counting the “1” bits in a binary number. Assume that we need to pop-count Register R1, where R1 has the value of 0x000000F5. The result of the pop-count should be stored in Register R2. Accordingly, after the execution of the program, R2 should have ‘6’. That is because 0x000000F5 has 6 “1” bits when converted to binary.

Hint

You will need to use the LSR instruction to logically-shift the binary number to the right and the AND instruction to test for the presence of the ‘1’ bits. The definition of LSR and AND operations are given below. You can write a version without any branches, as well as a version with banches to make your code more elegant.

  • AND performs a bit-wise and binary operation on each bits. For instance, if R2 holds 0000 0000 0000 0110 and R3 holds 0000 0000 0000 0011, the following instruction AND R1, R2, R3 will produce 0000 0000 0000 0010 in R1.

  • LSR logically-shift the binary number to the right, padding the left-most bit with a 0. For instance, if R2 holds 1100 0010 1010 0110, the following instruction LSR R1, R2, #1 will produce 0110 0001 0101 0011 in R1.

Question 2

Trace the following assembly program, report the final value of R6 and try to guess what the program does. Make sure to read the full explainations below before starting answering the question.

.global _start  // tell the program where to start from.

// data section starts
section .data
LIST .word  2, 4, -3, 0, -5, 8, 0, 1
NUM .word 7

// text (code) section starts
section .txt
_start:
      LOAD R0, =NUM         // Load NUM memory address in R0.
      LOAD R1, [R0]         // R1 now has the value at the address NUM, which is 7.
      MOV  R0, #0           // Initialize loop counter.
      MOV  R6, #0           // Initialize a counter for zero occurrences.
      LOAD R3, =LIST        // Load the memory address of the first number in R3.
start_over:
      SUB  R4, R0, R1
      BGE  R4, end          // The process should  go as long as counter (R0) is less than  NUM (R1)
      LOAD R5, [R3]         // get a value from the list.
      BEQ  R5, increment    // if R5 is equal to zero, then go to 'increment'.
get_the_next_number:
      ADD R0, R0, #1        // increment loop counter
      ADD R3, R3, #4        // getting the address of the next number in the list.
      B start_over          // branch unconditionally to 'start_over'.
increment:
      ADD R6, R6, #1        // increment zero occurences counter
      B get_the_next_number // branch unconditionally to 'get_the_next_number'.

 end

.global _start informs that assembler/linker that there is a label _start that will be used to start the program. This will be covered in more details in the labs and future lectures.

section .data is a section of the Memory where the initialized static variables are stored. The size of .data section is determined by the variables in the program and does not change during run-time. However, the values of the variables can be changed during runtime. The Memory has other sections like .text where the instructions are (i.e. the code).

LIST and NUM are actually not variables. They are memory addresses of the variables. Think of them as pointers. LIST is a memory address that has the first value of our list. Accordingly, LIST is actually the memory location/address where the number 2 (the first number of our list) resides. Likewise, NUM is NOT equal to 7. It is the memory address where the number 7 resides. In order to use a variable, we need first to know where it resides.

If we want to use the value 7, we should first get its address NUM. This is done by LOAD R0, =NUM which puts the address in R0 (when the right operand starts with =, this instruction is not really loading from memory, but simply copying the address after = to the destination register). After that, we use LOAD to load the value residing in the address contained in R0. This is done by LOAD R1, [R0], where R1 now has the value 7.

You might ask why we don’t directly use LOAD R1, [NUM]. Well, it is because immediate memory addressing is not supported in assembly languages. All memory addressing should be first loaded into registers using LOAD. The reasons behind this will be come clearer after you will have studied how the instructions are actually encoded in Lecture 2 (Instruction Set Architecture).